# Online to Offline Conversions, Universality and Adaptive Minibatch Sizes

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2017.

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

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization](https://mlsanity.com/paper/2111.11309/) (2021)
- [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)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration](https://mlsanity.com/paper/2209.14827/) (2022)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Loss Landscape Characterization of Neural Networks without Over-Parametrization](https://mlsanity.com/paper/2410.12455/) (2024)
- [Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Data](https://mlsanity.com/paper/2203.15797/) (2022)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles](https://mlsanity.com/paper/2403.11925/) (2024)
- [Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workers](https://mlsanity.com/paper/2402.02951/) (2024)
- [Prediction-Powered Semi-Supervised Learning with Online Power Tuning](https://mlsanity.com/paper/2510.22586/) (2025)
- [Gradient-Variation Online Adaptivity for Accelerated Optimization with H"older Smoothness](https://mlsanity.com/paper/2511.02276/) (2025)
- [AdaLoss: A computationally-efficient and provably convergent adaptive gradient method](https://mlsanity.com/paper/2109.08282/) (2021)
- [Adaptive Accelerated (Extra-)Gradient Methods with Variance Reduction](https://mlsanity.com/paper/2201.12302/) (2022)
- [DropCompute: simple and more robust distributed synchronous training via compute variance reduction](https://mlsanity.com/paper/2306.10598/) (2023)
- [Generative Minimization Networks: Training GANs Without Competition](https://mlsanity.com/paper/2103.12685/) (2021)
- [A Stochastic Bundle Method for Interpolating Networks](https://mlsanity.com/paper/2201.12678/) (2022)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [LightSAM: Parameter-Agnostic Sharpness-Aware Minimization](https://mlsanity.com/paper/2505.24399/) (2025)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [When to use what Schatten-p norm in deep learning?](https://mlsanity.com/paper/2606.15268/) (2026)
- [Towards Stability of Parameter-Free Optimization](https://mlsanity.com/paper/2405.04376/) (2024)
- [Online Learning-guided Learning Rate Adaptation via Gradient Alignment](https://mlsanity.com/paper/2506.08419/) (2025)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)

## Abstract (arXiv)

We present an approach towards convex optimization that relies on a novel scheme which converts online adaptive algorithms into offline methods. In the offline optimization setting, our derived methods are shown to obtain favourable adaptive guarantees which depend on the harmonic sum of the queried gradients. We further show that our methods implicitly adapt to the objective's structure: in the smooth case fast convergence rates are ensured without any prior knowledge of the smoothness parameter, while still maintaining guarantees in the non-smooth setting. Our approach has a natural extension to the stochastic setting, resulting in a lazy version of SGD (stochastic GD), where minibathces are chosen adaptively depending on the magnitude of the gradients. Thus providing a principled approach towards choosing minibatch sizes.