# On the Local Minima of the Empirical Risk

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2018.

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

- [Towards Efficient and Scalable Sharpness-Aware Minimization](https://mlsanity.com/paper/2203.02714/) (2022)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Tackling benign nonconvexity with smoothing and stochastic gradients](https://mlsanity.com/paper/2202.09052/) (2022)
- [Spectral Regularization Allows Data-frugal Learning over Combinatorial Spaces](https://mlsanity.com/paper/2210.02604/) (2022)
- [Federated Learning for distribution skewed data using sample weights](https://mlsanity.com/paper/2401.02586/) (2024)
- [Complex fractal trainability boundary can arise from trivial non-convexity](https://mlsanity.com/paper/2406.13971/) (2024)
- [Helen: Optimizing CTR Prediction Models with Frequency-wise Hessian Eigenvalue Regularization](https://mlsanity.com/paper/2403.00798/) (2024)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [A Derandomization Framework for Structure Discovery: Applications in Neural Networks and Beyond](https://mlsanity.com/paper/2510.19382/) (2025)

## Abstract (arXiv)

Population risk is always of primary interest in machine learning; however, learning algorithms only have access to the empirical risk. Even for applications with nonconvex nonsmooth losses (such as modern deep networks), the population risk is generally significantly more well-behaved from an optimization point of view than the empirical risk. In particular, sampling can create many spurious local minima. We consider a general framework which aims to optimize a smooth nonconvex function F (population risk) given only access to an approximation f (empirical risk) that is pointwise close to F (i.e., |F-f|∞ ≤ nu). Our objective is to find the ε-approximate local minima of the underlying function F while avoiding the shallow local minima---arising because of the tolerance nu---which exist only in f. We propose a simple algorithm based on stochastic gradient descent (SGD) on a smoothed version of f that is guaranteed to achieve our goal as long as nu ≤ O(ε1.5/d). We also provide an almost matching lower bound showing that our algorithm achieves optimal error tolerance nu among all algorithms making a polynomial number of queries of f. As a concrete example, we show that our results can be directly used to give sample complexities for learning a ReLU unit.