# Adaptive scale-invariant online algorithms for learning linear models

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

## Key facts

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

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

- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Unconstrained Online Learning with Unbounded Losses](https://mlsanity.com/paper/2306.04923/) (2023)
- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Logarithmic Regret from Sublinear Hints](https://mlsanity.com/paper/2111.05257/) (2021)
- [Online Linear Regression in Dynamic Environments via Discounting](https://mlsanity.com/paper/2405.19175/) (2024)
- [Implicit Parameter-free Online Learning with Truncated Linear Models](https://mlsanity.com/paper/2203.10327/) (2022)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [SANIA: Polyak-type Optimization Framework Leads to Scale Invariant Stochastic Algorithms](https://mlsanity.com/paper/2312.17369/) (2023)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [Optimistic Optimisation of Composite Objective with Exponentiated Update](https://mlsanity.com/paper/2208.04065/) (2022)
- [Towards Simple and Provable Parameter-Free Adaptive Gradient Methods](https://mlsanity.com/paper/2412.19444/) (2024)
- [Clustering and classification of low-dimensional data in explicit feature map domain: intraoperative pixel-wise diagnosis of adenocarcinoma of a colon in a liver](https://mlsanity.com/paper/2203.03636/) (2022)
- [The Sample Complexity of Parameter-Free Stochastic Convex Optimization](https://mlsanity.com/paper/2506.11336/) (2025)
- [Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization](https://mlsanity.com/paper/2605.18999/) (2026)
- [Locally Optimal Descent for Dynamic Stepsize Scheduling](https://mlsanity.com/paper/2311.13877/) (2023)

## Abstract (arXiv)

We consider online learning with linear models, where the algorithm predicts on sequentially revealed instances (feature vectors), and is compared against the best linear function (comparator) in hindsight. Popular algorithms in this framework, such as Online Gradient Descent (OGD), have parameters (learning rates), which ideally should be tuned based on the scales of the features and the optimal comparator, but these quantities only become available at the end of the learning process. In this paper, we resolve the tuning problem by proposing online algorithms making predictions which are invariant under arbitrary rescaling of the features. The algorithms have no parameters to tune, do not require any prior knowledge on the scale of the instances or the comparator, and achieve regret bounds matching (up to a logarithmic factor) that of OGD with optimally tuned separate learning rates per dimension, while retaining comparable runtime performance.