# Optimal Rates for Random Order Online Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 29 Jun 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)

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

- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [A Batch-to-Online Transformation under Random-Order Model](https://mlsanity.com/paper/2306.07163/) (2023)
- [Online Learning in the Random Order Model](https://mlsanity.com/paper/2510.02820/) (2025)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

We study online convex optimization in the random order model, recently proposed by citetgarber2020online, where the loss functions may be chosen by an adversary, but are then presented to the online algorithm in a uniformly random order. Focusing on the scenario where the cumulative loss function is (strongly) convex, yet individual loss functions are smooth but might be non-convex, we give algorithms that achieve the optimal bounds and significantly outperform the results of citetgarber2020online, completely removing the dimension dependence and improving their scaling with respect to the strong convexity parameter. Our analysis relies on novel connections between algorithmic stability and generalization for sampling without-replacement analogous to those studied in the with-replacement i.i.d.~setting, as well as on a refined average stability analysis of stochastic gradient descent.