mlsanityData to 7 Oct 2026

Black-Box Reductions for Parameter-free Online Learning in Banach Spaces

arXiv 1802.06293 ↗First posted 17 Feb 2018cs.LG math.OC stat.MLcited by 124

Not on the map. Why?

Abstract (arXiv)

We introduce several new black-box reductions that significantly improve the design of adaptive and parameter-free online learning algorithms by simplifying analysis, improving regret guarantees, and sometimes even improving runtime. We reduce parameter-free online learning to online exp-concave optimization, we reduce optimization in a Banach space to one-dimensional optimization, and we reduce optimization over a constrained domain to unconstrained optimization. All of our reductions run as fast as online gradient descent. We use our new techniques to improve upon the previously best regret bounds for parameter-free learning, and do so for arbitrary norms.

Key facts. Cited by 124 papers in the map (data through 7 Oct 2026). First posted on arXiv 17 Feb 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 15; 2022: 24; 2023: 24; 2024: 15; 2025: 23; 2026: 23.

124 papers.

Sort:

By area:

  1. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  2. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  3. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  4. 2021Impossible Tuning Made Possible: A New Expert Algorithm and Its Applicationscited by 52
  5. 2022Making SGD Parameter-Freecited by 50
  6. 2022Parameter-free Mirror Descentcited by 45
  7. 2021Tight Concentrations and Confidence Sequences from the Regret of Universal Portfoliocited by 42
  8. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  9. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 41
  10. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  11. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  12. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
38 more
  1. 2022PDE-Based Optimal Strategy for Unconstrained Online Learningcited by 27
  2. 2022Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyondcited by 27
  3. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  4. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  5. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  6. 2023Auditing Fairness by Bettingcited by 24
  7. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  8. 2023Sequential Predictive Two-Sample and Independence Testingcited by 20
  9. 2023Mechanic: A Learning Rate Tunercited by 20
  10. 2023Normalized Gradients for Allcited by 18
  11. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  12. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  13. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  14. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  15. 2021Off-policy Confidence Sequencescited by 15
  16. 2022Sequential Kernelized Independence Testingcited by 15
  17. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  18. 2021Adversarial Tracking Control via Strongly Adaptive Online Learning with Memorycited by 14
  19. 2021Pareto Optimal Model Selection in Linear Banditscited by 14
  20. 2024Active, anytime-valid risk controlling prediction setscited by 14
  21. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  22. 2022Scale-free Unconstrained Online Learning for Curved Lossescited by 13
  23. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  24. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  25. 2025SGD with Adaptive Preconditioning: Unified Analysis and Momentum Accelerationcited by 12
  26. 2021Logarithmic Regret from Sublinear Hintscited by 11
  27. 2023Unconstrained Dynamic Regret via Sparse Codingcited by 11
  28. 2023Tuning-Free Maximum Likelihood Training of Latent Variable Models via Coin Bettingcited by 11
  29. 2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
  30. 2024Online Detection of LLM-Generated Texts via Sequential Hypothesis Testing by Bettingcited by 11
  31. 2022Exploiting the Curvature of Feasible Sets for Faster Projection-Free Online Learningcited by 10
  32. 2024Fully Unconstrained Online Learningcited by 10
  33. 2022Optimal Comparator Adaptive Online Learning with Switching Costcited by 9
  34. 2022Quasi-Newton Steps for Efficient Online Exp-Concave Optimizationcited by 9
  35. 2023On the near-optimality of betting confidence sets for bounded meanscited by 9
  36. 2024An Equivalence Between Static and Dynamic Regret Minimizationcited by 9
  37. 2022Implicit Parameter-free Online Learning with Truncated Linear Modelscited by 8
  38. 2023Coin Sampling: Gradient-Based Bayesian Inference without Learning Ratescited by 8

50 most cited of 124 All 124 (JSON)