# Anytime Online-to-Batch Conversions, Optimism, and Acceleration

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

## Key facts

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

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

- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Reevaluating Theoretical Analysis Methods for Optimization in Deep Learning](https://mlsanity.com/paper/2407.01825/) (2024)
- [Oblivious Stochastic Composite Optimization](https://mlsanity.com/paper/2306.17470/) (2023)

## Abstract (arXiv)

A standard way to obtain convergence guarantees in stochastic convex optimization is to run an online learning algorithm and then output the average of its iterates: the actual iterates of the online learning algorithm do not come with individual guarantees. We close this gap by introducing a black-box modification to any online learning algorithm whose iterates converge to the optimum in stochastic scenarios. We then consider the case of smooth losses, and show that combining our approach with optimistic online learning algorithms immediately yields a fast convergence rate of O(L/T3/2+σ/√T) on L-smooth problems with σ2 variance in the gradients. Finally, we provide a reduction that converts any adaptive online algorithm into one that obtains the optimal accelerated rate of tilde O(L/T2 + σ/√T), while still maintaining tilde O(1/√T) convergence in the non-smooth setting. Importantly, our algorithms adapt to L and σ automatically: they do not need to know either to obtain these rates.