# Scale-Free Algorithms for Online Linear Optimization

arXiv: https://arxiv.org/abs/1502.05744 · HTML: https://mlsanity.com/paper/1502.05744/

## Key facts

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

## Built on by (most cited first, 30 of 30)

- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Understanding AdamW through Proximal Methods and Scale-Freeness](https://mlsanity.com/paper/2202.00089/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Online Learning with Optimism and Delay](https://mlsanity.com/paper/2106.06885/) (2021)
- [Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization](https://mlsanity.com/paper/2101.11075/) (2021)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Protected Test-Time Adaptation via Online Entropy Matching: A Betting Approach](https://mlsanity.com/paper/2408.07511/) (2024)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers](https://mlsanity.com/paper/2110.14804/) (2021)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descent](https://mlsanity.com/paper/2110.04961/) (2021)
- [Online Learning to Transport via the Minimal Selection Principle](https://mlsanity.com/paper/2202.04732/) (2022)
- [Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solving](https://mlsanity.com/paper/2105.13203/) (2021)
- [AdaLoss: A computationally-efficient and provably convergent adaptive gradient method](https://mlsanity.com/paper/2109.08282/) (2021)
- [Solving optimization problems with Blackwell approachability](https://mlsanity.com/paper/2202.12277/) (2022)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [Generalized Implicit Follow-The-Regularized-Leader](https://mlsanity.com/paper/2306.00201/) (2023)
- [Improved Algorithms for Adversarial Bandits with Unbounded Losses](https://mlsanity.com/paper/2310.01756/) (2023)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [How to Set β1, β2 in Adam: An Online Learning Perspective](https://mlsanity.com/paper/2510.03478/) (2025)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)
- [Adaptivity via a Parallel Architecture for Stochastic Gradient Methods](https://mlsanity.com/paper/2607.28902/) (2026)
- [Formal guarantees for heuristic optimization algorithms used in machine learning](https://mlsanity.com/paper/2208.00502/) (2022)
- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization](https://mlsanity.com/paper/2407.05704/) (2024)
- [The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems](https://mlsanity.com/paper/2608.08826/) (2026)

## 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.