The landscape of empirical risk for nonconvex losses

Mei Song, Yu Bai, Andrea Montanari

Abstract

Most high-dimensional estimation methods propose to minimize a cost function (empirical risk) that is a sum of losses associated to each data point. In this paper, we focus on the case of nonconvex losses. Classical empirical process theory implies uniform convergence of the empirical risk to the population risk, which ensures statistical consistency but does not guarantee that the estimator can be computed efficiently. To capture the complexity of computing M-estimators, we study the landscape of the empirical risk—specifically its stationary points and their properties. We establish uniform convergence of the gradient and Hessian of the empirical risk to their population counterparts as soon as the number of samples $n$ exceeds the number of parameters $p$ (modulo logarithmic factors). Consequently, the favorable properties of the population risk landscape are transferred to the empirical risk, establishing a one-to-one correspondence of their stationary points. We demonstrate that in problems such as nonconvex binary classification, robust regression, and Gaussian mixture models, this result implies a complete characterization of the empirical risk landscape and the convergence of descent algorithms. We further extend this analysis to the very high-dimensional setting ($p \gg n$), providing a characterization of the landscape under nearly information-theoretically minimal conditions based on parameter sparsity.

Introduction

In modern machine learning and statistics, the standard approach to parameter estimation is Empirical Risk Minimization (ERM). While the statistical properties of ERM are well-understood for convex losses, many contemporary applications—ranging from robust regression to deep learning—rely on nonconvex loss functions. For these problems, traditional statistical theory guarantees that the empirical risk will eventually converge to the population risk, but it remains silent on whether we can actually find the global minimum in a computationally efficient manner.

Nonconvex optimization is generally NP-hard. However, in practice, simple first-order methods like gradient descent often succeed. This paper provides a theoretical bridge between statistical consistency and computational efficiency by analyzing the "landscape" of the empirical risk. The authors show that for a broad class of problems, the empirical risk function inherits the benign optimization properties of the population risk as soon as the sample size is sufficiently large.

The Geometry of Risk Landscapes

The core challenge in nonconvex optimization is the presence of "nasty" stationary points—local minima, maxima, and saddle points—that can trap optimization algorithms. Standard empirical process theory proves that the empirical risk $R_n(\theta)$ converges to the population risk $R(\theta)$ in value. However, two functions can be very close in value while having radically different derivatives, meaning the empirical risk could be riddled with local minima that do not exist in the population risk.

To address this, the authors establish uniform convergence of derivatives. They prove that under regularity conditions (such as sub-Gaussian noise and Lipschitz Hessians), the gradient $\nabla R_n(\theta)$ and Hessian $\nabla^2 R_n(\theta)$ converge uniformly to their population counterparts.

Topology Transfer and Morse Theory

By leveraging tools from differential topology, specifically Morse Theory, the paper demonstrates a "topology transfer." If the population risk is a "strongly Morse" function—meaning its stationary points are non-degenerate—there exists a one-to-one correspondence between the stationary points of the population risk and those of the empirical risk. This ensures that if the population risk has a simple landscape (e.g., a unique global minimum and only "strict" saddles), the empirical risk will share this structure.

High-Dimensional Scaling

The paper establishes precise sample complexity bounds for this landscape preservation:

  1. High-Dimensional Regime ($n \gtrsim p \log p$): The landscape of the empirical risk becomes well-behaved once the number of samples $n$ scales linearly with the number of parameters $p$ (up to logarithmic factors).
  2. Very High-Dimensional Regime ($p \gg n$): For problems where the number of parameters exceeds the sample size, the authors analyze $\ell_1$-regularized nonconvex problems. They show that if the underlying parameter vector is $s_0$-sparse, the landscape remains tractable provided $n \gtrsim s_0 \log p$. This is a nearly information-theoretically minimal condition for recovery.

Applications and Empirical Validation

The theoretical framework is applied to several classic nonconvex problems:

  • Binary Classification: Using a nonconvex nonlinear square loss, the authors prove the empirical risk has a unique local minimum (which is also the global minimum). Gradient descent is guaranteed to converge to this point exponentially fast.
  • Robust Regression: Using Tukey’s bisquare loss, which is designed to ignore outliers, the authors show the landscape remains easy to optimize even in the presence of contaminated data.
  • Gaussian Mixture Models (GMM): For a mixture of two Gaussians, the paper characterizes the landscape as having exactly two global minima (due to symmetry) and proves that standard algorithms will converge to one of them.

While primarily theoretical, the authors validate these findings using synthetic simulations and the Colon Cancer Dataset ($p=2000, n=62$). The real-world data application demonstrates that nonconvex approaches in high dimensions can be as viable and stable as standard regularized logistic regression when the landscape is properly understood.

Key Insights

  • Derivatives Matter More Than Values: For optimization, the convergence of the first and second derivatives is the critical factor that prevents the appearance of spurious local minima.
  • The "Strict Saddle" Property: Many nonconvex problems are computationally tractable because their only stationary points are either local minima or "strict saddles" (where the Hessian has at least one significant negative eigenvalue). Gradient descent can naturally escape these saddles.
  • Efficiency Meets Consistency: The requirements for a "clean" optimization landscape are essentially the same as the requirements for statistical consistency, suggesting that if a problem is statistically solvable, it is often computationally solvable as well.

Limitations and Future Directions

While this work provides a rigorous foundation for understanding nonconvex landscapes, some gaps remain. The theory relies on the population risk being "strongly Morse," a property that is provable for simple models but difficult to verify for complex architectures like deep neural networks. Additionally, while the landscape is shown to be benign, some results still assume a reasonable initialization. Extending these characterizations to multi-layer neural networks remains the "holy grail" of this research trajectory.

Summary updated

Abstract

Most high-dimensional estimation methods propose to minimize a cost function (empirical risk) that is a sum of losses associated to each data point (each example). In this paper, we focus on the case of nonconvex losses. Classical empirical process theory implies uniform convergence of the empirical (or sample) risk to the population risk. While under additional assumptions, uniform convergence implies consistency of the resulting M-estimator, it does not ensure that the latter can be computed efficiently. In order to capture the complexity of computing M-estimators, we study the landscape of the empirical risk, namely its stationary points and their properties. We establish uniform convergence of the gradient and Hessian of the empirical risk to their population counterparts, as soon as the number of samples becomes larger than the number of unknown parameters (modulo logarithmic factors). Consequently, good properties of the population risk can be carried to the empirical risk, and we are able to establish one-to-one correspondence of their stationary points. We demonstrate that in several problems such as nonconvex binary classification, robust regression and Gaussian mixture model, this result implies a complete characterization of the landscape of the empirical risk, and of the convergence properties of descent algorithms. We extend our analysis to the very high-dimensional setting in which the number of parameters exceeds the number of samples, and provides a characterization of the empirical risk landscape under a nearly information-theoretically minimal condition. Namely, if the number of samples exceeds the sparsity of the parameters vector (modulo logarithmic factors), then a suitable uniform convergence result holds. We apply this result to nonconvex binary classification and robust regression in very high-dimension.
BibTeX
@article{song2018landscape,
  author = {Mei Song and Yu Bai and Andrea Montanari},
  title = {{The landscape of empirical risk for nonconvex losses}},
  journal = {The Annals of Statistics},
  year = {2018},
  doi = {10.1214/17-aos1637},
}
Figure