mlsanityData to 14 Oct 2026

Scale-Free Online Learning

arXiv 1601.01974 ↗First posted 8 Jan 2016cs.LGcited by 85

Not on the map. Why?

Abstract (arXiv)

We design and analyze algorithms for online linear optimization that have optimal regret and at the same time do not need to know any upper or lower bounds on the norm of the loss vectors. Our algorithms are instances of the Follow the Regularized Leader (FTRL) and Mirror Descent (MD) meta-algorithms. We achieve adaptiveness to the norms of the loss vectors by scale invariance, i.e., our algorithms make exactly the same decisions if the sequence of loss vectors is multiplied by any positive constant. The algorithm based on FTRL works for any decision set, bounded or unbounded. For unbounded decisions sets, this is the first adaptive algorithm for online linear optimization with a non-vacuous regret bound. In contrast, we show lower bounds on scale-free algorithms based on MD on unbounded domains.

Key facts. Cited by 85 papers in the map (data through 14 Oct 2026). First posted on arXiv 8 Jan 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 15; 2022: 11; 2023: 15; 2024: 17; 2025: 10; 2026: 17.

85 papers.

Sort:

By area:

  1. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  2. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  3. 2023Improved Online Conformal Prediction via Strongly Adaptive Online Learningcited by 78
  4. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  5. 2022Understanding AdamW through Proximal Methods and Scale-Freenesscited by 46
  6. 2022Parameter-free Mirror Descentcited by 45
  7. 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
  8. 2023Optimal Algorithms for Online Convex Optimization with Adversarial Constraintscited by 34
  9. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  10. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
  11. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 26
  12. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
38 more
  1. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
  2. 2024Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approachcited by 23
  3. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  4. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  5. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  6. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 19
  7. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 18
  8. 2022No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separationcited by 17
  9. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  10. 2023Efficient Methods for Non-stationary Online Learningcited by 15
  11. 2024Kernel-based Optimally Weighted Conformal Time-Series Predictioncited by 15
  12. 2021Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimizationcited by 14
  13. 2021Beyond Bandit Feedback in Online Multiclass Classificationcited by 14
  14. 2026Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimizationcited by 14
  15. 2021A closer look at temporal variability in dynamic online learningcited by 13
  16. 2022Scale-free Unconstrained Online Learning for Curved Lossescited by 13
  17. 2021Scale Free Adversarial Multi Armed Banditscited by 12
  18. 2024Discounted Adaptive Online Learning: Towards Better Regularizationcited by 12
  19. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  20. 2024Gradient-Variation Online Learning under Generalized Smoothnesscited by 11
  21. 2021On the Last Iterate Convergence of Momentum Methodscited by 10
  22. 2024An Equivalence Between Static and Dynamic Regret Minimizationcited by 9
  23. 2023Improving Adaptive Online Learning Using Refined Discretizationcited by 8
  24. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  25. 2024Multi-model Ensemble Conformal Prediction in Dynamic Environmentscited by 8
  26. 2022A gradient estimator via L1-randomization for online zero-order optimization with two point feedbackcited by 7
  27. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  28. 2023Levin Tree Search with Context Modelscited by 7
  29. 2022Online Learning to Transport via the Minimal Selection Principlecited by 6
  30. 2024No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimizationcited by 6
  31. 2024Universal Online Convex Optimization with 1 Projection per Roundcited by 6
  32. 2025Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offscited by 6
  33. 2025Exploring the Noise Robustness of Online Conformal Predictioncited by 5
  34. 2025On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruningcited by 5
  35. 2021Universal Online Convex Optimization Meets Second-order Boundscited by 4
  36. 2021Robust Online Convex Optimization in the Presence of Outlierscited by 4
  37. 2021Isotuning With Applications To Scale-Free Online Learningcited by 4
  38. 2026Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizercited by 4

50 most cited of 85 All 85 (JSON)