mlsanityData to 7 Oct 2026

Online Linear Optimization with Many Hints

arXiv 2010.03082 ↗First posted 6 Oct 2020cs.LGcited by 15

Not on the map. Why?

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.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 3; 2023: 2; 2024: 1; 2025: 3; 2026: 1.

15 papers.

Sort:

  1. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  2. 2022Online Algorithms with Multiple Predictionscited by 22
  3. 2022Algorithms with Prediction Portfolioscited by 19
  4. 2023Sorting with Predictionscited by 14
  5. 2023Mixing predictions for online metric algorithmscited by 12
  6. 2021Logarithmic Regret from Sublinear Hintscited by 11
  7. 2024Learning-Augmented Algorithms with Explicit Predictorscited by 8
  8. 2021Linear Bandits on Uniformly Convex Setscited by 6
  9. 2021Local and Global Uniform Convexity Conditionscited by 4
  10. 2025Learning to Price with Resource Constraints: From Full Information to Machine-Learned Pricescited by 3
  11. 2025Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Gamescited by 2
  12. 2025Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictorscited by 2
3 more
  1. 2021Parameter-free Gradient Temporal Difference Learningcited by 1
  2. 2026Gradient-Variation Regret Bounds for Unconstrained Online Learningcited by 1
  3. 2022Parameter-free Online Linear Optimization with Side Information via Universal Coin Bettingcited by 0