# Empirical Risk Minimization for Stochastic Convex Optimization: O(1/n)- and O(1/n2)-type of Risk Bounds

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2017.

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

- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [Towards a Theoretical Understanding to the Generalization of RLHF](https://mlsanity.com/paper/2601.16403/) (2026)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)
- [On the Stability and Generalization of Triplet Learning](https://mlsanity.com/paper/2302.09815/) (2023)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses](https://mlsanity.com/paper/2505.09432/) (2025)
- [Explaining Fast Improvement in Online Imitation Learning](https://mlsanity.com/paper/2007.02520/) (2020)
- [Why Does Multi-Epoch Training Help?](https://mlsanity.com/paper/2105.06015/) (2021)
- [Towards Sharper Risk Bounds for Minimax Problems](https://mlsanity.com/paper/2410.08497/) (2024)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)
- [Learning Rates for Nonconvex Pairwise Learning](https://mlsanity.com/paper/2111.05232/) (2021)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [R-divergence for Estimating Model-oriented Distribution Discrepancy](https://mlsanity.com/paper/2310.01109/) (2023)

## Abstract (arXiv)

Although there exist plentiful theories of empirical risk minimization (ERM) for supervised learning, current theoretical understandings of ERM for a related problem---stochastic convex optimization (SCO), are limited. In this work, we strengthen the realm of ERM for SCO by exploiting smoothness and strong convexity conditions to improve the risk bounds. First, we establish an widetildeO(d/n + √F_*/n) risk bound when the random function is nonnegative, convex and smooth, and the expected function is Lipschitz continuous, where d is the dimensionality of the problem, n is the number of samples, and F_* is the minimal risk. Thus, when F_* is small we obtain an widetildeO(d/n) risk bound, which is analogous to the widetildeO(1/n) optimistic rate of ERM for supervised learning. Second, if the objective function is also λ-strongly convex, we prove an widetildeO(d/n + kappa F_*/n ) risk bound where kappa is the condition number, and improve it to O(1/[λ n2] + kappa F_*/n) when n=widetildeOmega(kappa d). As a result, we obtain an O(kappa/n2) risk bound under the condition that n is large and F_* is small, which to the best of our knowledge, is the first O(1/n2)-type of risk bound of ERM. Third, we stress that the above results are established in a unified framework, which allows us to derive new risk bounds under weaker conditions, e.g., without convexity of the random function and Lipschitz continuity of the expected function. Finally, we demonstrate that to achieve an O(1/[λ n2] + kappa F_*/n) risk bound for supervised learning, the widetildeOmega(kappa d) requirement on n can be replaced with Omega(kappa2), which is dimensionality-independent.