mlsanityData to 7 Oct 2026

Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications

arXiv 2102.01046 ↗First posted 1 Feb 2021cs.LG cs.CCcited by 52

Not on the map. Why?

Abstract (arXiv)

We resolve the long-standing "impossible tuning" issue for the classic expert problem and show that, it is in fact possible to achieve regret Oleft(√(ln d)sumt ℓt,i2right) simultaneously for all expert i in a T-round d-expert problem where ℓt,i is the loss for expert i in round t. Our algorithm is based on the Mirror Descent framework with a correction term and a weighted entropy regularizer. While natural, the algorithm has not been studied before and requires a careful analysis. We also generalize the bound to Oleft(√(ln d)sumt (ℓt,i-mt,i)2right) for any prediction vector mt that the learner receives, and recover or improve many existing results by choosing different mt. Furthermore, we use the same framework to create a master algorithm that combines a set of base algorithms and learns the best one with little overhead. The new guarantee of our master allows us to derive many new results for both the expert problem and more generally Online Linear Optimization.

Key facts. Cited by 52 papers in the map (data through 7 Oct 2026). Builds on 19 of its 35 references that are in the map. First posted on arXiv 1 Feb 2021.

Builds on

19 of 35 references.

References · 19

  1. 2013Optimization, Learning, and Games with Predictable Sequencescited by 187
  2. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  3. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2015Strongly Adaptive Online Learningcited by 102
  6. 2014A Second-order Bound with Excess Lossescited by 91
  7. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  8. 2015Second-order Quantile Methods for Experts and Combinatorial Gamescited by 47
  9. 2016MetaGrad: Multiple Learning Rates in Online Learningcited by 46
  10. 2019Lipschitz Adaptivity with Multiple Learning Rates in Online Learningcited by 36
  11. 2014Optimal learning with Bernstein Online Aggregationcited by 35
  12. 2017Tracking the Best Expert in Non-stationary Stochastic Environmentscited by 35
7 more
  1. 2017Parameter-free online learning via model selectioncited by 34
  2. 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
  3. 2019Combining Online Learning Guaranteescited by 22
  4. 2020Online Linear Optimization with Many Hintscited by 15
  5. 2016Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learningcited by 13
  6. 2017Multi-scale Online Learning and its Applications to Online Auctionscited by 8
  7. 2019Adaptive and Efficient Algorithms for Tracking the Best Expertcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 12; 2023: 10; 2024: 6; 2025: 9; 2026: 11.

52 papers.

Sort:

  1. 2022Parameter-free Mirror Descentcited by 45
  2. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  3. 2022No-Regret Learning in Time-Varying Zero-Sum Gamescited by 36
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  6. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
  7. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  8. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  9. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  10. 2023Mechanic: A Learning Rate Tunercited by 20
  11. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  12. 2023Best of Both Worlds Policy Optimizationcited by 17
38 more
  1. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  2. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  3. 2022Policy Optimization for Stochastic Shortest Pathcited by 13
  4. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  5. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  6. 2021Logarithmic Regret from Sublinear Hintscited by 11
  7. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  8. 2024Calibration Error for Decision Makingcited by 11
  9. 2024Gradient-Variation Online Learning under Generalized Smoothnesscited by 11
  10. 2024Fully Unconstrained Online Learningcited by 10
  11. 2022Optimal Comparator Adaptive Online Learning with Switching Costcited by 9
  12. 2023Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approachcited by 9
  13. 2022Implicit Parameter-free Online Learning with Truncated Linear Modelscited by 8
  14. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8
  15. 2022Leveraging Initial Hints for Free in Stochastic Linear Banditscited by 7
  16. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
  17. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  18. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  19. 2021Isotuning With Applications To Scale-Free Online Learningcited by 4
  20. 2025Efficient Swap Multicalibration of Elicitable Propertiescited by 4
  21. 2025Sparsity-Based Interpolation of External, Internal and Swap Regretcited by 3
  22. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  23. 2025Parameter-free Algorithms for the Stochastically Extended Adversarial Modelcited by 3
  24. 2026An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimizationcited by 3
  25. 2025Comparator-Adaptive Phi-Regret: Improved Bounds, Simpler Algorithms, and Applications to Gamescited by 2
  26. 2025An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPscited by 2
  27. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 2
  28. 2026Near-optimal Swap Regret Minimization for Convex Lossescited by 2
  29. 2025Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applicationscited by 1
  30. 2026Scale-Invariant Fast Convergence in Gamescited by 1
  31. 2026Online Learning with Gradient-Variation Interval Regretcited by 1
  32. 2022Parameter-free Online Linear Optimization with Side Information via Universal Coin Bettingcited by 0
  33. 2025Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variationscited by 0
  34. 2025When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Lossescited by 0
  35. 2026High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batchcited by 0
  36. 2026Efficient Opportunistic Approachabilitycited by 0
  37. 2026Instance-Adaptive Online Multicalibrationcited by 0
  38. 2026Agile Online Model Selection: Resolving Adaptation Lag via Safeguarded Large Learning Ratescited by 0

50 most cited of 52 All 52 (JSON)