mlsanityData to 14 Oct 2026

Optimal Rates for Random Order Online Optimization

arXiv 2106.15207 ↗First posted 29 Jun 2021cs.LG math.OC stat.MLcited by 9

Not on the map. Why?

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.

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

13 of 25 references.

References · 13

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2014Convex Optimization: Algorithms and Complexitycited by 575
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  6. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  7. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  8. 2019How Good is SGD with Random Shuffling?cited by 64
  9. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  10. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  11. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  12. 2020Closing the convergence gap of SGD without replacementcited by 57
1 more
  1. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 3; 2024: 0; 2025: 2; 2026: 2.

9 papers.

  1. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  2. 2022Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothnesscited by 21
  3. 2022Benign Underfitting of Stochastic Gradient Descentcited by 19
  4. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  5. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  6. 2023A Batch-to-Online Transformation under Random-Order Modelcited by 2
  7. 2025Online Learning in the Random Order Modelcited by 2
  8. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 2
  9. 2026From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Modelcited by 0