mlsanityData to 7 Oct 2026

Scale-Free Algorithms for Online Linear Optimization

arXiv 1502.05744 ↗First posted 19 Feb 2015cs.LG math.OCcited by 30

Not on the map. Why?

Abstract (arXiv)

We design 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. We achieve adaptiveness to norms of 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. Our algorithms work for any decision set, bounded or unbounded. For unbounded decisions sets, these are the first truly adaptive algorithms for online linear optimization.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 Feb 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 8; 2023: 6; 2024: 6; 2025: 2; 2026: 2.

30 papers.

Sort:

  1. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  2. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  3. 2022Understanding AdamW through Proximal Methods and Scale-Freenesscited by 46
  4. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  5. 2021Online Learning with Optimism and Delaycited by 33
  6. 2021Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimizationcited by 27
  7. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  8. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  9. 2024Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approachcited by 22
  10. 2023Normalized Gradients for Allcited by 18
  11. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  12. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
18 more
  1. 2021Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizerscited by 8
  2. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  3. 2021Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descentcited by 7
  4. 2022Online Learning to Transport via the Minimal Selection Principlecited by 6
  5. 2021Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solvingcited by 4
  6. 2022Solving optimization problems with Blackwell approachabilitycited by 4
  7. 2021AdaLoss: A computationally-efficient and provably convergent adaptive gradient methodcited by 3
  8. 2022A Stochastic Bundle Method for Interpolating Networkscited by 3
  9. 2023Generalized Implicit Follow-The-Regularized-Leadercited by 3
  10. 2023Improved Algorithms for Adversarial Bandits with Unbounded Lossescited by 3
  11. 2025How to Set β1, β2 in Adam: An Online Learning Perspectivecited by 2
  12. 2023Online Resource Allocation: Bandits feedback and Advice on Time-varying Demandscited by 1
  13. 2026Adaptivity via a Parallel Architecture for Stochastic Gradient Methodscited by 1
  14. 2022Formal guarantees for heuristic optimization algorithms used in machine learningcited by 0
  15. 2024The SMART approach to instance-optimal online learningcited by 0
  16. 2024Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimizationcited by 0
  17. 2025When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Lossescited by 0
  18. 2026The Cost of Adaptivity: Matching Lower Bounds Across Learning Problemscited by 0