# Online Learning Without Prior Information

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Mar 2017.

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

- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Which LLM to Play? Convergence-Aware Online Model Selection with Time-Increasing Bandits](https://mlsanity.com/paper/2403.07213/) (2024)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Fully Unconstrained Online Learning](https://mlsanity.com/paper/2405.20540/) (2024)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Implicit Parameter-free Online Learning with Truncated Linear Models](https://mlsanity.com/paper/2203.10327/) (2022)
- [Never Start from Scratch: Expediting On-Device LLM Personalization via Explainable Model Selection](https://mlsanity.com/paper/2504.13938/) (2025)
- [Universal Online Convex Optimization with 1 Projection per Round](https://mlsanity.com/paper/2405.19705/) (2024)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)
- [Optimistic Optimisation of Composite Objective with Exponentiated Update](https://mlsanity.com/paper/2208.04065/) (2022)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [LightSAM: Parameter-Agnostic Sharpness-Aware Minimization](https://mlsanity.com/paper/2505.24399/) (2025)
- [Parameter-free projected gradient descent](https://mlsanity.com/paper/2305.19605/) (2023)

## Abstract (arXiv)

The vast majority of optimization and online learning algorithms today require some prior information about the data (often in the form of bounds on gradients or on the optimal parameter value). When this information is not available, these algorithms require laborious manual tuning of various hyperparameters, motivating the search for algorithms that can adapt to the data with no prior information. We describe a frontier of new lower bounds on the performance of such algorithms, reflecting a tradeoff between a term that depends on the optimal parameter value and a term that depends on the gradients' rate of growth. Further, we construct a family of algorithms whose performance matches any desired point on this frontier, which no previous algorithm reaches.