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

arXiv: https://arxiv.org/abs/2202.02406 · HTML: https://mlsanity.com/paper/2202.02406/

## Key facts

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

## Builds on (most cited first, 17 of 17)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Online Learning with Imperfect Hints](https://mlsanity.com/paper/2002.04726/) (2020)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [Adaptive Online Learning](https://mlsanity.com/paper/1508.05170/) (2015)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Online Linear Optimization with Many Hints](https://mlsanity.com/paper/2010.03082/) (2020)
- [Online Learning for Changing Environments using Coin Betting](https://mlsanity.com/paper/1711.02545/) (2017)
- [Minimax Optimal Algorithms for Unconstrained Linear Optimization](https://mlsanity.com/paper/1302.2176/) (2013)
- [Locally-Adaptive Nonparametric Online Learning](https://mlsanity.com/paper/2002.01882/) (2020)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)

## 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.