# Optimal Rates for Multi-pass Stochastic Gradient Methods

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2016.

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

- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [Stability and Generalization for Markov Chain Stochastic Gradient Methods](https://mlsanity.com/paper/2209.08005/) (2022)
- [High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noise](https://mlsanity.com/paper/2208.08567/) (2022)
- [Optimality of Robust Online Learning](https://mlsanity.com/paper/2304.10060/) (2023)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descent](https://mlsanity.com/paper/2407.02322/) (2024)
- [Optimal Rates for Generalization of Gradient Descent Methods with Deep Neural Networks](https://mlsanity.com/paper/2606.06764/) (2026)
- [Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees](https://mlsanity.com/paper/2608.25513/) (2026)

## Abstract (arXiv)

We analyze the learning properties of the stochastic gradient method when multiple passes over the data and mini-batches are allowed. We study how regularization properties are controlled by the step-size, the number of passes and the mini-batch size. In particular, we consider the square loss and show that for a universal step-size choice, the number of passes acts as a regularization parameter, and optimal finite sample bounds can be achieved by early-stopping. Moreover, we show that larger step-sizes are allowed when considering mini-batches. Our analysis is based on a unifying approach, encompassing both batch and stochastic gradient methods as special cases. As a byproduct, we derive optimal convergence results for batch gradient methods (even in the non-attainable cases).