The Landscape of Empirical Risk for Non-convex Losses

Mei Song, Yu Bai, Andrea Montanari

Abstract

Most high-dimensional estimation and prediction methods minimize an empirical risk function—a sum of losses associated with individual data points. While the case of convex losses is well-understood, non-convex losses are practically prevalent yet theoretically challenging. Classical empirical process theory ensures the consistency of M-estimators via the uniform convergence of empirical risk to population risk, but it fails to guarantee efficient computation. This paper characterizes the complexity of M-estimation by studying the landscape of the empirical risk, specifically its stationary points. We establish that the gradient and Hessian of the empirical risk converge uniformly to their population counterparts when the number of samples $n$ exceeds the number of parameters $p$ (modulo logarithmic factors). This correspondence allows properties of the population risk to be transferred to the empirical risk, ensuring that stationary points match one-to-one. We extend this analysis to the high-dimensional sparse regime ($n \ll p$), demonstrating that the empirical risk landscape remains tractable under nearly information-theoretically minimal conditions.

Introduction: The Convexity Myth

In high-dimensional statistics and machine learning, convexity has long been treated as the gold standard for tractability. If a loss function is convex, any local minimum is a global minimum, making optimization via gradient descent straightforward. However, many modern applications—ranging from robust regression to neural network training—rely on non-convex loss functions. While these functions often perform better in practice, they introduce the theoretical risk of "bad" local minima and saddle points that could trap optimization algorithms.

"The Landscape of Empirical Risk for Non-convex Losses" provides a theoretical bridge between non-convex practice and rigorous guarantees. The research suggests that the "messy" empirical risk landscape derived from finite data converges to a "clean" population landscape as the sample size increases. If enough data is available, the geometric features of the empirical risk—its peaks, valleys, and saddles—align with the theoretical ideal, allowing simple descent algorithms to find global solutions.

Beyond Value Convergence: Mapping the Landscape

Standard M-estimation theory typically relies on Empirical Process Theory to show that the value of the empirical risk $R_n(\theta)$ converges to the population risk $R(\theta)$. However, value convergence does not prevent the empirical risk from being "jagged," with numerous local minima that do not exist in the population limit.

To address this, the authors establish the uniform convergence of the gradient and the Hessian. By ensuring that the derivatives converge, they prove that the shape of the function is preserved. Using tools from Morse Theory, they demonstrate that if the population risk is a "well-behaved" (strongly Morse) function, the empirical risk will possess an identical number of stationary points. Crucially, these points maintain their character: a local minimum in the population risk remains a local minimum in the empirical risk, rather than splitting into multiple spurious traps.

Scaling Regimes and Sample Complexity

The paper analyzes two primary regimes of dimensionality:

  1. High-Dimensional ($n \gtrsim p$): When the number of samples $n$ is at least proportional to the number of parameters $p$ (specifically $n \gtrsim p \log p$), the empirical landscape becomes a faithful representation of the population landscape.
  2. Very High-Dimensional Sparse ($n \ll p$): In cases where parameters outnumber samples but the underlying signal is sparse, the authors show that the landscape remains well-behaved under the condition $n \gtrsim s_0 \log p$, where $s_0$ is the sparsity level. This is nearly the information-theoretic limit, suggesting that the landscape simplifies as soon as the problem becomes statistically solvable.

Applications in Non-Convex Estimation

The theoretical framework is applied to several classic non-convex problems, providing new insights into their optimization:

  • Binary Classification: Using non-linear square loss, the authors prove that the empirical risk possesses a unique local minimum (which is also the global minimum) once $n$ is sufficiently large.
  • Robust Regression: Non-convex "robust" losses (such as Tukey’s bisquare loss) are often used to mitigate the influence of outliers. The paper shows these are as easy to optimize as convex losses, provided the noise distribution is reasonable, as the empirical risk avoids spurious local minima.
  • Gaussian Mixture Models (GMM): In clustering problems, symmetry often creates multiple global minima (e.g., swapping cluster labels). The paper proves these are the only minima and that they are connected by predictable saddle points, ensuring that gradient-based methods can navigate to a valid solution.

Conclusion and Implications

This research offers a "green light" for the use of non-convex objectives in high-dimensional settings. It demonstrates that the difficulty of non-convex optimization is often not an inherent curse of the loss function itself, but a function of sample complexity. When the data volume is sufficient relative to the model's complexity, the empirical landscape simplifies, and the "jaggedness" that plagues low-data regimes disappears.

While the theory currently requires smooth (three-times differentiable) loss functions and certain initialization conditions, it lays the groundwork for understanding why simple algorithms like gradient descent are so effective at solving complex, non-convex problems in modern machine learning.

Summary updated

Abstract

Most high-dimensional estimation and prediction methods propose to minimize a cost function (empirical risk) that is written as a sum of losses associated to each data point. In this paper we focus on the case of non-convex losses, which is practically important but still poorly understood. Classical empirical process theory implies uniform convergence of the empirical risk to the population risk. While 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 propose to 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 can establish one-to-one correspondence of their stationary points. We demonstrate that in several problems such as non-convex 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 provide 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 unknown parameters vector (modulo logarithmic factors), then a suitable uniform convergence result takes place. We apply this result to non-convex 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 Non-convex Losses}},
  journal = {The Annals of Statistics},
  year = {2018},
  doi = {10.1214/17-aos1637},
}
Figure