PaperlayerView exact revision on arXiv

Source-linked AI summary

The Landscape of Empirical Risk for Non-convex Losses

Song Mei, Yu Bai, Andrea Montanari

arXiv:1607.06534v3stat.ML

TL;DR

Non-convex empirical-risk methods are poorly understood, and uniform convergence alone does not ensure efficient computation. The paper relates empirical and population risk landscapes, showing stationary-point correspondence under a strong-Morse condition and examining sparse and application-specific settings.

  • Problem

    Uniform convergence of empirical risk does not rule out multiple local minima, so it does not by itself provide a computationally practical way to compute the estimator.

    Source: §1 · p. 3, §2 · p. 5

  • Method

    The paper studies empirical-risk stationary points through their correspondence with population-risk stationary points, and gives a generalized gradient-linearity condition for a unique local minimum in a sparse setting.

    Source: §1 · pp. 3–4

  • Results

    For a strongly Morse population risk, n ≳ p log p yields one-to-one correspondence between empirical- and population-risk stationary points with the same index; binary classification and robust regression also have unique local minima under stated sample-size conditions.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    In the stated binary-classification and robust-regression settings, the unique local minimum can also be a global minimum or be found efficiently by gradient descent.

    Source: §1 · p. 4

    Related local-optimization analyses may reach only a statistical neighborhood, lack guaranteed convergence to a fixed point, and are typically case-by-case.

    Source: §2 · pp. 5–6

Abstract

from arXiv · show

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.

1 Introduction

The paper studies non-convex M-estimation because uniform convergence of empirical risk alone does not ensure that its stationary points are computationally tractable. It links empirical-risk landscapes to population-risk structure and extends the analysis to sparse, very high-dimensional settings.

1 Introduction

  • When the population risk is strongly Morse, for n ≳ p log p its empirical-risk stationary points correspond one-to-one and have the same index.Weaker conditions can ensure correspondence for local minima alone.Source: §1 · p. 3
  • For sparse parameters, generalized gradient linearity yields a unique local minimum of the ℓ1-regularized problem when n ≳ s0 log p.The paper calls this scaling nearly optimal because consistent estimation is impossible when n ≲ s0.Source: §1 · p. 4
  • Binary classification and robust regression have unique local minima for n ≳ d log d; their sparse versions have unique local minima for n ≳ s0 log d.The classification minimum is also global, and gradient descent converges to it exponentially; robust regression results require technical conditions on the loss and noise.Source: §1 · p. 4
  • For two equally weighted Gaussians, the empirical risk has two component-swapped global minima connected by saddles, and random initialization lets trust-region optimization converge to one.The minima are within nearly optimal statistical error of the true centers.Source: §1 · p. 4

1.1 Notations

  • The paper uses normal font for scalars and boldface for vectors, and generally uses uppercase for random variables and lowercase for deterministic values.Source: §1.1 · pp. 4–5

2 Related literature

Prior work establishes uniform risk convergence and statistical guarantees for local optimization, but these results do not fully characterize empirical-risk landscapes or always provide practical stopping guidance. The paper positions its contribution as a landscape-focused complement to those approaches.

2 Related literature

  • Uniform convergence of risk can imply M-estimator guarantees, but for non-convex losses it does not rule out multiple local minima or by itself provide a computationally practical method.Source: §2 · p. 5
  • Some local-optimization analyses guarantee only a statistical neighborhood, leave open whether a better local minimum improves error, and lack a clear stopping criterion when fixed-point convergence is unproved.These analyses also rely on restricted strong convexity without providing a general tool to establish it.Source: §2 · p. 5
  • The paper contrasts its sparse-regime result with Loh [Loh15], which requires n ≳ s0^2, while its approach requires n ≳ s0 log d.Source: §2 · pp. 5–6
  • Hybrid methods use a smart initialization followed by local refinement, but their analyses are often case-by-case and sometimes prove convergence only to a statistical neighborhood.Source: §2 · p. 6

3 Uniform convergence results

The section develops uniform-convergence tools for empirical-risk derivatives in both high-dimensional and sparse very-high-dimensional regimes. It uses derivative control to relate empirical and population landscapes, including their critical-point structure under strong-Morse conditions.

3.1 High-dimensional regime

  • Discrete losses such as 0–1 loss fall outside the derivative assumptions, though differentiable approximations may make little or no practical difference.Source: §3.1 · p. 7
  • Under Assumptions 1–3, the sample gradient and Hessian converge uniformly to their population counterparts in Euclidean and operator norms, respectively.Source: §3.1 · p. 7
  • When the population risk is (ε,η)-strongly Morse and the sample-size condition holds, the empirical risk is (ε/2,η/2)-strongly Morse, with critical points paired one-to-one and indices preserved.Source: §3.1 · p. 8
  • A weaker condition—near-critical Hessian eigenvalues having either sign but remaining bounded away from zero—can still characterize empirical-risk local minima.Source: §3.1 · p. 8

3.2 Very high-dimensional regime

  • For p≫n, the analysis uses ℓ1-penalized risk and requires bounded gradients plus generalized gradient linearity, illustrated for binary classification and robust regression.Source: §3.2 · pp. 8–9
  • At n≥C2 s0 log(np), sample directional gradients and restricted Hessians converge uniformly for any s0≤p.Source: §3.2 · p. 9

4 Applications

Across binary classification and robust regression, the applications characterize non-convex empirical-risk minima and optimization behavior, including sparse settings where parameters outnumber samples. For a two-component Gaussian mixture, the empirical landscape has two exchange-related minima and a trust-region convergence guarantee.

4.1 Binary linear classification: High dimensional regime

  • With nonlinear square loss, n≥C1d log d yields a unique global minimizer and exponentially convergent gradient descent, requiring O(log(1/ε)) iterations independent of n and d.The result is stated with probability at least 1−δ under the theorem's assumptions.Source: §4.1 · pp. 10–11

4.2 Binary linear classification: Very high-dimensional regime

  • For sparse θ0, the ℓ2-constrained ℓ1-regularized risk has a unique global minimizer when n≥Cn s0 log²d and the theorem's stated error condition holds.The authors leave open whether a fast algorithm finds this minimizer.Source: §4.2 · pp. 11–12

4.3 Robust regression: High-dimensional regime

  • Under the theorem's assumptions and n≥C1d log d, robust regression has a unique local minimizer, and fixed-step gradient descent converges exponentially fast.The stated assumptions include conditions on the score function, noise, and feature distribution.Source: §4.3 · p. 13

4.4 Robust regression: Very high-dimensional regime

  • For sparse robust regression, the theorem gives a unique local minimizer that is also global when n is sufficiently large, including n≥Cn s0 log²d, and its stated error condition holds.The setup uses an ℓ2-constrained, ℓ1-regularized risk.Source: §4.4 · p. 14

4.5 Gaussian mixture model

  • For equal-weight two-Gaussian mixtures, n≥C1d log d yields two exchange-related local minima near the saddle, and trust-region converges from any initialization in that neighborhood.The sample-size guarantee holds with probability at least 1−δ.Source: §4.5 · p. 15

5 Numerical experiments

Numerical experiments test the paper’s landscape and algorithmic predictions in simulated and real-data settings. Across the studied models, descent methods show convergence behavior consistent with the theory, while the real-data illustrations emphasize computational viability rather than predictive accuracy.

5.1 Binary linear classification: high-dimensional regime

  • In binary classification, success rises sharply near n of order d log d; estimation error follows Θ(d/n), and convergence appears exponential.The iteration count decreases as n/d grows and converges to a constant.Source: §5.1 · pp. 16–17

5.2 Binary linear classification: very high-dimensional regime

  • In very high-dimensional binary classification, proximal-gradient iterates converge to a unique local minimizer, with exponential convergence when n ≫ k log^2(d).The standard deviation across random initializations decays exponentially toward zero.Source: §5.2 · p. 18

5.3 Robust linear regression

  • For robust regression, iterates converge exponentially across initializations, and Tukey regression is fairly insensitive to outliers while least-squares error deteriorates.The exponential convergence rate remains under large contamination fractions.Source: §5.3 · p. 18

5.4 Gaussian mixture model

  • In the Gaussian mixture experiment, gradient descent converges to one of only two local minimizers, with statistical-error behavior consistent with Theorem 8.Source: §5.4 · p. 21

5.5 Australian credit data

  • On Australian credit data, the non-convex estimator’s variability across initializations decreases exponentially, suggesting a unique local minimum.The comparison with logistic regression is framed around computational viability, not predictive accuracy.Source: §5.5 · p. 21

5.6 Colon cancer data

  • On colon cancer data, the non-convex approach shows exponentially decreasing initialization variability, and most selected covariates also appear in logistic Lasso.The authors describe the resulting model as comparable to the ℓ1-regularized logistic regression model.Source: §5.6 · p. 22

A Some useful tools

  • The appendix collects standard sub-Gaussian and sub-exponential probability tools and ε-cover bounds used in the proofs.Source: §A.1 · p. 23, §A.2 · p. 25

B.1 Proof of Theorem 1.(a): Uniform convergence of gradient

The proof controls uniform deviations of the empirical gradient and Hessian, then uses structural lemmas to relate critical points of nearby functions. These steps support the claimed correspondence between population and empirical risk landscapes.

B.1 Proof of Theorem 1.(a): Uniform convergence of gradient

  • ε-covers, concentration bounds, and the stated assumptions yield uniform gradient convergence when n ≥ C1 p log p.The proof decomposes bad events and bounds their probabilities to establish the sample-size condition.Source: §B.1 · pp. 25, 26, 28

B.2 Proof of Theorem 1.(b): Uniform convergence of Hessian

  • The Hessian proof uses ε-covers and Bernstein bounds to obtain uniform Hessian convergence under the same n ≥ C1 p log p condition.Source: §B.2 · pp. 28, 29, 31

C.1 Two structural lemmas

  • The structural lemmas show that boundary-compatible gradient fields preserve critical-point counts and indices, while each connected small-gradient region contains at most one critical point.The latter follows because a second critical point would require a saddle contradicting Hessian non-degeneracy.Source: §C.1 · pp. 31–33

C.2 Proof of Theorem 2

The proof partitions regions of small population gradient and uses uniform gradient and Hessian control to match their critical points with empirical ones. It also bounds how far corresponding estimators can lie apart.

C.2 Proof of Theorem 2

  • The proof uses Theorem 1’s uniform convergence event to transfer the population landscape’s local structure to the empirical risk.Source: §C.2 · p. 33
  • Each small-gradient component containing a population critical point has one empirical critical point with the same Hessian index; components without one have none.Source: §C.2 · p. 33
  • Corresponding empirical and population critical points lie in the same component, whose radius is bounded by 2εn/η.Source: §C.2 · p. 34

D.1 Proof of Theorem 3.(a): Uniform convergence of directional gradient

The sparse-regime proof controls directional-gradient deviations through localized regions and concentration, then establishes a separate uniform bound for the restricted Hessian. The latter requires a sample size scaling with sparsity.

D.1 Proof of Theorem 3.(a): Uniform convergence of directional gradient

  • Outside a small ball around θ0, the directional-gradient proof partitions the domain into regions and bounds deviations with symmetrization, contraction, and concentration.The resulting bound is stated for all regions in the partition.Source: §D.1 · pp. 35–36
  • Inside the small ball, the proof uses Hessian convergence to control discretization and complete the directional-gradient bound.Source: §D.1 · p. 37

D.2 Proof of Theorem 3.(b): Uniform of convergence of restricted Hessian

  • The restricted-Hessian proof uses sparse ε-covers and concentration, with the stated condition n ≥ C2 s0 log(np).Source: §D.2 · pp. 38–39

E.1.1 Landscape of population risk

The population risk has a unique minimizer at θ0 and no other stationary points. Its local Hessian and gradient bounds characterize the landscape around and away from that minimizer.

E.1.1 Landscape of population risk

  • The population risk is minimized at θ0 and has no other stationary points.This conclusion holds under the stated assumptions, including ∥θ0∥2 ≤ r/3.Source: §E.1.1 · p. 40
  • Within a neighborhood of θ0, the Hessian has lower and upper bounds, with the neighborhood and curvature constants independent of d and the distribution of X.The Hessian perturbation is bounded relative to its minimum eigenvalue when ∥θ − θ0∥2 ≤ ε0.Source: §E.1.1 · pp. 40–42
  • Outside the ε0-neighborhood of θ0 but within Bd(0, r), the analysis gives a distribution-free lower bound on the gradient.The preceding gradient lower bound depends on the distribution of X; part (c) supplies a distribution-free bound.Source: §E.1.1 · p. 42

E.1.2 Landscape of empirical risk

With n ≥ C d log d, the empirical risk has a unique minimizer near θ0 and a landscape that supports exponential convergence of gradient descent. The section also outlines the stationary-point analysis used for the very high-dimensional regime.

E.1.2 Landscape of empirical risk

  • With probability at least 1 − δ, the empirical risk is minimized at a unique point θ̂n within Bd(θ0, C d log n/n), given n ≥ C d log d.The empirical risk is strongly convex inside Bd(θ0, ε0), and the argument rules out local minima elsewhere in Bd(0, r).Source: §E.1.2 · pp. 42–45

E.1.3 Gradient descent algorithm

  • With probability at least 1 − δ, gradient descent with a fixed step size h ≤ hmax converges exponentially to the global minimizer from any initialization in Bd(θ0, 2r/3), when n ≥ C d log d.The proof combines exponential convergence outside the strongly convex neighborhood with exponential convergence inside it.Source: §E.1.3 · p. 45

E.2 Proof of Theorem 5: Very high-dimensional regime

  • The very high-dimensional proof first applies uniform convergence, then excludes stationary points outside a cone-shaped neighborhood, bounds their support size, and uses restricted Hessian convergence to establish uniqueness.The neighborhood is centered at θ0 with radius rs; the cone and statistical radius are specified in the proof outline.Source: §E.2 · p. 48

E.2.1 Technical lemmas

The technical lemmas establish conditions for the very high-dimensional binary-classification analysis and constrain where stationary points can occur, how sparse they are, and when they are unique.

E.2.1 Technical lemmas

  • For the very high-dimensional binary-classification model, Assumptions 4 and 5 hold with T* = T0 · M and L* = L0 · M under Assumptions 7 and 8.T0 and L0 depend on τ2, Lσ, Cσ, and r.Source: §E.2.1 · p. 48
  • With probability at least 1 − δ, both stated events hold: Ln has no stationary point in B2(r) ∩ Cc or in C \ B2(θ0, rs).The radius is rs = C0 (M2s0 log d)/n + s0λ2n.Source: §E.2.1 · p. 49
  • With probability at least 1 − δ, stationary points in C ∩ B2(θ0, rs) have support size at most C3 s0 log d.The stated result assumes the lemma’s sample-size condition and defines rs using C0.Source: §E.2.1 · p. 50
  • When n ≥ c1 s0 log d, the proof bounds the support size of any stationary point by n.The argument uses the subgradient condition and linear independence of the design rows on sufficiently large supports.Source: §E.2.1 · pp. 51–52
  • With probability at least 1 − δ, the regularized empirical risk cannot have two stationary points in B2(θ0, ε0) ∩ B0(r0/2) when n ≥ C1 s0 log2 d.Restricted strong convexity on the relevant sparse region rules out two distinct stationary points.Source: §E.2.1 · p. 54

E.2.2 Proof of the main theorem

Under the theorem’s conditions, stationary points are restricted to a sparse neighborhood of θ0, where the regularized empirical risk has at most one stationary point.

E.2.2 Proof of the main theorem

  • Under the theorem’s conditions, no stationary point lies outside the specified neighborhood of θ0.The proof combines the exclusion result of Lemma 12 with the theorem’s sample-size and regularization conditions.Source: §E.2.2 · p. 55
  • If the statistical radius is at most ε0, the only possible stationary point lies in C ∩ B2(θ0, ε0) ∩ B0(Csps0 log d), and it is unique when n ≥ Cn s0 log2 d.The proof combines the stationary-point support bound with the uniqueness result of Lemma 14.Source: §E.2.2 · p. 55

F.1 Landscape of population risk

The population risk has a unique stationary point at the true parameter, while the empirical-risk analysis establishes a matching landscape for robust regression and convergence of gradient descent.

F.1 Landscape of population risk

  • The population risk is minimized at θ0 and has no other stationary points.Source: §F.1 · p. 55
  • The population Hessian and gradient have global upper bounds κ0 and L0, respectively.Source: §F.1 · pp. 56–57

F.2 Landscape of empirical risk

  • For robust regression, n = Ω(d log d) suffices for the empirical risk to have the properties established for binary linear classification.The robust-regression constants depend on model parameters listed in the passage.Source: §F.2 · p. 57

F.3 Gradient descent algorithm

  • For robust regression, gradient descent converges exponentially fast to the empirical-risk global minimum when n = Ω(d log d).Source: §F.3 · p. 58

G.1 Landscape of population risk

For the two-component Gaussian mixture, the population risk has two minima and a saddle, and the empirical risk retains this structure with enough samples. The trust-region iteration converges to an empirical global minimum from any initialization in the stated region.

G.1 Landscape of population risk

  • The population risk has exactly three stationary points: minima at θ+ and θ−, and a saddle at θs.Source: §G.1 · p. 58
  • At θ+ and θ− the population-risk Hessian is positive definite, while at θs it has a negative eigenvalue.Source: §G.1 · p. 60

G.2 Landscape of empirical risk

  • With n ≥ C d log d, the empirical risk has two local minima near the population minima, saddle points but no local minima near the population saddle, and no other critical points.The result holds with probability at least 1 − δ, for constants depending on (D, δ).Source: §G.2 · pp. 61–62

G.3 Trust region algorithm

  • For n ≥ C1 d log d, trust-region iteration converges to an empirical global minimum from any initialization in T2d(θs, C2).Source: §G.3 · p. 64

Related papers

Loading 1607.06534v3…