Lune

Abstract

We consider a variant of the classical online linear optimization problem in which at every step, the online player receives a "hint" vector before choosing the action for that round. Rather surprisingly, it was shown that if the hint vector is guaranteed to have a positive correlation with the cost vector, then the online player can achieve a regret of O(log⁡T)O(\log T), thus significantly improving over the O(T)O(\sqrt{T}) regret in the general setting. However, the result and analysis require the correlation property at all time steps, thus raising the natural question: can we design online learning algorithms that are resilient to bad hints? In this paper we develop algorithms and nearly matching lower bounds for online learning with imperfect directional hints. Our algorithms are oblivious to the quality of the hints, and the regret bounds interpolate between the always-correlated hints case and the no-hints case. Our results also generalize, simplify, and improve upon previous results on optimistic regret bounds, which can be viewed as an additive version of hints.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

26 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Robustification of Online Graph Exploration Methods cites Near-Optimal Bounds for Online Caching with Machine Learned Advice
  • Robustification of Online Graph Exploration Methods cites Online Scheduling via Learned Weights
  • Learning Online Algorithms with Distributional Advice cites Near-Optimal Bounds for Online Caching with Machine Learned Advice
  • Learning Online Algorithms with Distributional Advice cites Online Scheduling via Learned Weights
  • A Regression Approach to Learning-Augmented Online Algorithms cites Near-Optimal Bounds for Online Caching with Machine Learned Advice
  • A Regression Approach to Learning-Augmented Online Algorithms cites Online Scheduling via Learned Weights
  • Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms cites Near-Optimal Bounds for Online Caching with Machine Learned Advice
  • Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms cites Online Scheduling via Learned Weights
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers26

  1. Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online AlgorithmsAlexander Wei, Fred ZhangNeurIPS 2020 · 129 citations
  2. DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size ScheduleMaor Ivgi, Oliver Hinder, Yair CarmonICML 2023 · 98 citations
  3. Learning Online Algorithms with Distributional AdviceIlias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian et al.ICML 2021 · 44 citations
  4. A Regression Approach to Learning-Augmented Online AlgorithmsKeerti Anand, Rong Ge, Amit Kumar, Debmalya PanigrahiNeurIPS 2021 · 29 citations
  5. Robustification of Online Graph Exploration MethodsFranziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke et al.AAAI 2022 · 25 citations

Builds on3

  1. Near-Optimal Bounds for Online Caching with Machine Learned AdviceDhruv RohatgiSODA 2020 · 88 citations
  2. Online Scheduling via Learned WeightsSilvio Lattanzi, Thomas Lavastida, Benjamin Moseley, Sergei VassilvitskiiSODA 2020 · 83 citations
  3. Interleaved Caching with Access GraphsRavi Kumar, Manish Purohit, Zoya Svitkina, Erik VeeSODA 2020 · 8 citations

Related papers

  1. Logarithmic Regret from Sublinear HintsAditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish PurohitNeurIPS 2021 · 23 citations
  2. Online Linear Optimization with Many HintsAditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish PurohitNeurIPS 2020 · 21 citations
  3. Bandit Online Linear Optimization with Hints and QueriesAditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish PurohitICML 2023 · 4 citations
  4. Augment Online Linear Optimization with Arbitrarily Bad Machine-Learned PredictionsDacheng Wen, Yupeng Li, Francis C. M. LauINFOCOM 2024 · 5 citations
  5. Alternation makes the adversary weaker in two-player gamesVolkan Cevher, Ashok Cutkosky, Ali Kavis, Georgios Piliouras et al.NeurIPS 2023 · 8 citations
Dusk over the sea between two cliffs drawn in fine vertical lines