# Uniform Stability for First-Order Empirical Risk Minimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 33 references that are in the map.
- First posted on arXiv 17 Jul 2022.

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

- [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)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Stability and Convergence Trade-off of Iterative Optimization Algorithms](https://mlsanity.com/paper/1804.01619/) (2018)
- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back](https://mlsanity.com/paper/1608.04414/) (2016)
- [A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent](https://mlsanity.com/paper/1709.06617/) (2017)
- [Algorithmic Instabilities of Accelerated Gradient Descent](https://mlsanity.com/paper/2102.02167/) (2021)
- [Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch-Prox](https://mlsanity.com/paper/1702.06269/) (2017)
- [Fast Rates for Empirical Risk Minimization of Strict Saddle Problems](https://mlsanity.com/paper/1701.04271/) (2017)
- [Stochastic Optimization with Laggard Data Pipelines](https://mlsanity.com/paper/2010.13639/) (2020)

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

- [Differentially Private Stochastic Convex Optimization in (Non)-Euclidean Space Revisited](https://mlsanity.com/paper/2303.18047/) (2023)
- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [Beyond Real Data: Synthetic Data through the Lens of Regularization](https://mlsanity.com/paper/2510.08095/) (2025)
- [Convex SGD: Generalization Without Early Stopping](https://mlsanity.com/paper/2401.04067/) (2024)
- [Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapes](https://mlsanity.com/paper/2511.17399/) (2025)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)
- [Auditing Machine Unlearning: A Systematic Research on Whether Models Truly Forget](https://mlsanity.com/paper/2606.16110/) (2026)

## Abstract (arXiv)

We consider the problem of designing uniformly stable first-order optimization algorithms for empirical risk minimization. Uniform stability is often used to obtain generalization error bounds for optimization algorithms, and we are interested in a general approach to achieve it. For Euclidean geometry, we suggest a black-box conversion which given a smooth optimization algorithm, produces a uniformly stable version of the algorithm while maintaining its convergence rate up to logarithmic factors. Using this reduction we obtain a (nearly) optimal algorithm for smooth optimization with convergence rate widetildeO(1/T2) and uniform stability O(T2/n), resolving an open problem of Chen et al. (2018); Attia and Koren (2021). For more general geometries, we develop a variant of Mirror Descent for smooth optimization with convergence rate widetildeO(1/T) and uniform stability O(T/n), leaving open the question of devising a general conversion method as in the Euclidean case.