# Characterization of Excess Risk for Locally Strongly Convex Population Risk

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

## Key facts

- Cited by 5 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 4 Dec 2020.

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

- [On the Generalization of Diffusion Model](https://mlsanity.com/paper/2305.14712/) (2023)
- [Towards a Theoretical Understanding to the Generalization of RLHF](https://mlsanity.com/paper/2601.16403/) (2026)
- [Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)](https://mlsanity.com/paper/2410.09766/) (2024)
- [TANDEM: Bi-Level Data Mixture Optimization with Twin Networks](https://mlsanity.com/paper/2606.04401/) (2026)
- [Continuous-time Riemannian SGD and SVRG Flows on Wasserstein Probabilistic Space](https://mlsanity.com/paper/2401.13530/) (2024)

## Abstract (arXiv)

We establish upper bounds for the expected excess risk of models trained by proper iterative algorithms which approximate the local minima. Unlike the results built upon the strong globally strongly convexity or global growth conditions e.g., PL-inequality, we only require the population risk to be locally strongly convex around its local minima. Concretely, our bound under convex problems is of order tildecO(1/n). For non-convex problems with d model parameters such that d/n is smaller than a threshold independent of n, the order of tildecO(1/n) can be maintained if the empirical risk has no spurious local minima with high probability. Moreover, the bound for non-convex problem becomes tildecO(1/√n) without such assumption. Our results are derived via algorithmic stability and characterization of the empirical risk's landscape. Compared with the existing algorithmic stability based results, our bounds are dimensional insensitive and without restrictions on the algorithm's implementation, learning rate, and the number of iterations. Our bounds underscore that with locally strongly convex population risk, the models trained by any proper iterative algorithm can generalize well, even for non-convex problems, and d is large.