# How Free is Parameter-Free Stochastic Optimization?

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 46 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 29 of 29)

- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [A new regret analysis for Adam-type algorithms](https://mlsanity.com/paper/2003.09729/) (2020)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [On the Convergence Proof of AMSGrad and a New Version](https://mlsanity.com/paper/1904.03590/) (2019)
- [Better Parameter-free Stochastic Optimization with ODE Updates for Coin-Betting](https://mlsanity.com/paper/2006.07507/) (2020)
- [Online Convex Optimization with Unconstrained Domains and Losses](https://mlsanity.com/paper/1703.02622/) (2017)

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

- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Gradient-Variation Online Learning under Generalized Smoothness](https://mlsanity.com/paper/2408.09074/) (2024)
- [AutoSGD: Automatic Learning Rate Selection for Stochastic Gradient Descent](https://mlsanity.com/paper/2505.21651/) (2025)
- [A General Reduction for High-Probability Analysis with General Light-Tailed Distributions](https://mlsanity.com/paper/2403.02873/) (2024)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batching](https://mlsanity.com/paper/2408.07503/) (2024)
- [Online Learning-guided Learning Rate Adaptation via Gradient Alignment](https://mlsanity.com/paper/2506.08419/) (2025)
- [The Sample Complexity of Parameter-Free Stochastic Convex Optimization](https://mlsanity.com/paper/2506.11336/) (2025)
- [AutoGD: Automatic Learning Rate Selection for Gradient Descent](https://mlsanity.com/paper/2510.09923/) (2025)
- [Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning](https://mlsanity.com/paper/2606.14970/) (2026)
- [Clipping the Price of Adaptivity at the Tail](https://mlsanity.com/paper/2606.22669/) (2026)

## Abstract (arXiv)

We study the problem of parameter-free stochastic optimization, inquiring whether, and under what conditions, do fully parameter-free methods exist: these are methods that achieve convergence rates competitive with optimally tuned methods, without requiring significant knowledge of the true problem parameters. Existing parameter-free methods can only be considered ``partially'' parameter-free, as they require some non-trivial knowledge of the true problem parameters, such as a bound on the stochastic gradient norms, a bound on the distance to a minimizer, etc. In the non-convex setting, we demonstrate that a simple hyperparameter search technique results in a fully parameter-free method that outperforms more sophisticated state-of-the-art algorithms. We also provide a similar result in the convex setting with access to noisy function values under mild noise assumptions. Finally, assuming only access to stochastic gradients, we establish a lower bound that renders fully parameter-free stochastic convex optimization infeasible, and provide a method which is (partially) parameter-free up to the limit indicated by our lower bound.