# Online Linear Optimization with Many Hints

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

## Built on by (most cited first, 16 of 16)

- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Algorithms with Prediction Portfolios](https://mlsanity.com/paper/2210.12438/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [Learning-Augmented Algorithms with Explicit Predictors](https://mlsanity.com/paper/2403.07413/) (2024)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games](https://mlsanity.com/paper/2505.17277/) (2025)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Parameter-free Gradient Temporal Difference Learning](https://mlsanity.com/paper/2105.04129/) (2021)
- [Gradient-Variation Regret Bounds for Unconstrained Online Learning](https://mlsanity.com/paper/2604.11151/) (2026)
- [Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting](https://mlsanity.com/paper/2202.02406/) (2022)
- [The Value of Information in Resource-Constrained Pricing](https://mlsanity.com/paper/2603.24974/) (2026)

## Abstract (arXiv)

We study an online linear optimization (OLO) problem in which the learner is provided access to K "hint" vectors in each round prior to making a decision. In this setting, we devise an algorithm that obtains logarithmic regret whenever there exists a convex combination of the K hints that has positive correlation with the cost vectors. This significantly extends prior work that considered only the case K=1. To accomplish this, we develop a way to combine many arbitrary OLO algorithms to obtain regret only a logarithmically worse factor than the minimum regret of the original algorithms in hindsight; this result is of independent interest.