# Parameter-free Stochastic Optimization of Variationally Coherent Functions

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 30 Jan 2021.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [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)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [A Modular Analysis of Adaptive (Non-)Convex Optimization: Optimism, Composite Objectives, and Variational Bounds](https://mlsanity.com/paper/1709.02726/) (2017)
- [Online mirror descent and dual averaging: keeping pace in the dynamic case](https://mlsanity.com/paper/2006.02585/) (2020)
- [Minimax Optimal Algorithms for Unconstrained Linear Optimization](https://mlsanity.com/paper/1302.2176/) (2013)
- [Unifying mirror descent and dual averaging](https://mlsanity.com/paper/1910.13742/) (2019)

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

- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [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 Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Early-stopped neural networks are consistent](https://mlsanity.com/paper/2106.05932/) (2021)
- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Normalized Gradients for All](https://mlsanity.com/paper/2308.05621/) (2023)
- [Discounted Adaptive Online Learning: Towards Better Regularization](https://mlsanity.com/paper/2402.02720/) (2024)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Implicit Parameter-free Online Learning with Truncated Linear Models](https://mlsanity.com/paper/2203.10327/) (2022)
- [Strongly-polynomial time and validation analysis of policy gradient methods](https://mlsanity.com/paper/2409.19437/) (2024)
- [Dynamic Regret Reduces to Kernelized Static Regret](https://mlsanity.com/paper/2507.05478/) (2025)
- [Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization](https://mlsanity.com/paper/2507.09823/) (2025)
- [Generalized Implicit Follow-The-Regularized-Leader](https://mlsanity.com/paper/2306.00201/) (2023)
- [Auto-exploration for online reinforcement learning](https://mlsanity.com/paper/2512.06244/) (2025)
- [Parameter-free projected gradient descent](https://mlsanity.com/paper/2305.19605/) (2023)
- [A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2506.01052/) (2025)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimization](https://mlsanity.com/paper/2503.09411/) (2025)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)
- [A Perturbation Approach to Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.28201/) (2026)
- [Parameter-Free and Group Conditional Online Conformal Prediction](https://mlsanity.com/paper/2606.00419/) (2026)
- [Large-scale empirical tuning and comparison of default optimizers for variational inference](https://mlsanity.com/paper/2606.07841/) (2026)

## Abstract (arXiv)

We design and analyze an algorithm for first-order stochastic optimization of a large class of functions on ℝd. In particular, we consider the variationally coherent functions which can be convex or non-convex. The iterates of our algorithm on variationally coherent functions converge almost surely to the global minimizer boldsymbolx^*. Additionally, the very same algorithm with the same hyperparameters, after T iterations guarantees on convex functions that the expected suboptimality gap is bounded by widetildeO(|boldsymbolx^* - boldsymbolx0| T-1/2+ε) for any ε>0. It is the first algorithm to achieve both these properties at the same time. Also, the rate for convex functions essentially matches the performance of parameter-free algorithms. Our algorithm is an instance of the Follow The Regularized Leader algorithm with the added twist of using rescaled gradients and time-varying linearithmic regularizers.