mlsanityData to 13 Oct 2026

Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting

arXiv 2202.02406 ↗First posted 4 Feb 2022cs.IT cs.LG math.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and P'al (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Builds on 17 of its 45 references that are in the map. First posted on arXiv 4 Feb 2022.

Builds on

17 of 45 references.

References · 17

  1. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 412
  2. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  3. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  4. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 47
  5. 2014Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximationscited by 46
  6. 2020Online Learning with Imperfect Hintscited by 37
  7. 2017Online Learning Without Prior Informationcited by 36
  8. 2018The Many Faces of Exponential Weights in Online Learningcited by 33
  9. 2019Parameter-Free Online Convex Optimization with Sub-Exponential Noisecited by 28
  10. 2014Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learningcited by 27
  11. 2015Adaptive Online Learningcited by 23
  12. 2019Combining Online Learning Guaranteescited by 22
5 more
  1. 2020Online Linear Optimization with Many Hintscited by 15
  2. 2013Minimax Optimal Algorithms for Unconstrained Linear Optimizationcited by 12
  3. 2017Online Learning for Changing Environments using Coin Bettingcited by 12
  4. 2020Locally-Adaptive Nonparametric Online Learningcited by 8
  5. 2021Universal Online Convex Optimization Meets Second-order Boundscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization
  2. 2019Continuous Online Learning and New Insights to Online Imitation Learning
  3. 2026Offline Local Search for Online Stochastic Bandits
  4. 2026Offline-to-Online Learning in Linear Bandits
  5. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
  6. 2020Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
  7. 2025KL-regularization Itself is Differentially Private in Bandits and RLHF
  8. 2020Statistical Inference for Online Decision Making via Stochastic Gradient Descent