The landscape of empirical risk for nonconvex losses

By Song Mei, Yu Bai, Andrea Montanari. 2016

333 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

When do neural networks outperform kernel methods? (2020, background): “For instance, if the target is a single neuron f∗(x) = σ(〈w∗,x〉), then training a neural network with one hidden neuron learns the target efficiently from approximately d log d samples [22], while the corresponding RKHS has test error bounded away from zero for every sample size polynomial in d [32,”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, background): “And the behaviour of the two quantities may be drastically different (for a recent analysis on provable estimates see [Mei et al., 2016]).”
Robust and Communication-Efficient Collaborative Learning (2019, background): “Under the assumption that the gradient of loss is sub-Gaussian, it has been shown that with high probability the gap between the gradients of expected risk and empirical risk is bounded by √ (Mei et al., 2018).”
Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “Similar ideas have been used recently in the work [21], which studies the stationary points of the empirical risk function.”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “For a neural network with zero hidden units and a single output with a monotonic activation function σ , numerous authors [20], [23], [24], [34], [44] have shown that gradientbased methods converge to the global optimum under various assumptions and models.”
An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysis (2017, background): “(Mei et al., 2016) shows the global convergence for a single nonlinear node whose derivatives of activation σ (cid:48) , σ (cid:48)(cid:48) , σ (cid:48)(cid:48)(cid:48) are bounded and σ (cid:48) > 0 .”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “It is likely that measure concentration results can be used to get similar results to those we had for the population risk (e.g., see Mei et al., 2016; Xu et al., 2016, for use of such tools).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “This motivates the research of studying the landscape of neural networks (Kawaguchi, 2016; Choromanska et al., 2015; Hardt & Ma, 2016; Haeffele & Vidal, 2015; Mei et al., 2016; Freeman & Bruna, 2016; Safran & Shamir, 2016; Zhou & Feng, 2017; Nguyen & Hein, 2017a;b; Ge et al., 2017b; Zhou & Feng, 201”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, background): “At a high level, many machine learning problems are solved by minimizing certain appropriate risk (cost) function using gradient descent [MBM16].”
Universal statistics of Fisher information in deep neural networks: mean field approach (2018, background): “For instance, the loss landscape without spurious local minima is important for easier optimization and theoretically guaranteed in single-layer models [15], shallow piecewise linear ones [16], and extremely wide deep networks with the number of training samples smaller than the width [17].”
Learning Compact Neural Networks with Regularization (2018, background): “…are closely related to the recent works on provably learning shallow neural nets (Zhong et al., 2017b; Tian, 2017; Soltanolkotabi, 2017; Panigrahy et al., 2018; Ge et al., 2017; Oymak & Soltanolkotabi, 2018; Zhong et al., 2017a; Safran & Shamir, 2017; Arora et al., 2014; Mei et al., 2016).”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “A specific counterexample is given in [25]: if the function to be learnt is a single neuron f∗(x) = σ(〈w∗,x〉) then gradient descent (in the space of neural networks with N = 1 neurons) efficiently learns it [20]; on the other hand, RF or NT require a number of neurons exponential in the dimension to”
When is a Convolutional Filter Easy To Learn? (2017, background): “…the research of studying the landscape of neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Hardt and Ma, 2016, Haeffele and Vidal, 2015, Mei et al., 2016, Freeman and Bruna, 2016, Safran and Shamir, 2016, Zhou and Feng, 2017] However, these results cannot be directly applied to…”
The Landscape of the Spiked Tensor Model (2017, background): “The general picture that emerges from theses studies, as formalized in [31], is that nonconvex losses can sometimes be “benign” and allow for nearly optimal statistical estimation using gradient-descent-type optimization algorithms.”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, neutral): “We have |N| ≤ 5 d and for any vector w ∈ R d that (cid:107) w 2 ≤ 2 sup v ∈N ( v (cid:62) w ) (see e.g. (Mei et al., 2018a, Section A).)”