Source-linked AI summary
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
Itay Safran, Ohad Shamir
TL;DR
The paper asks whether simple ReLU neural-network objectives can avoid spurious local minima under Gaussian inputs and realizable, orthonormal targets. It combines a computer-assisted proof with experiments, finding such minima for 6 ≤ k ≤ 20 and frequent optimization entrapment, while mild over-parameterization sharply reduces them.
Problem
The paper investigates whether neural-network training objectives can have no spurious local minima under assumptions that would make gradient-based optimization reliable.
Method
The authors use gradient descent to locate candidate suboptimal stationary points and computer-assisted formal verification to certify strict local minima, supplemented by experiments.
Results
Spurious local minima exist for 6 ≤ k ≤ 20 even in arbitrarily high dimensions with orthonormal target parameters, and their observed attraction probability increases with network size.
Takeaways & Limitations
Mild over-parameterization appears to mitigate the issue: experiments found fewer minima for n = k + 1 and none for n ≥ k + 2 at tested sizes up to 20.
Takeaways & Limitations
The theorem was verified only up to k, n ≤ 20, and the authors did not rule out local minima at larger sizes.
Abstract
from arXiv · showhide
We consider the optimization problem associated with training simple ReLU neural networks of the form $\mathbf{x}\mapsto \sum_{i=1}^{k}\max\{0,\mathbf{w}_i^\top \mathbf{x}\}$ with respect to the squared loss. We provide a computer-assisted proof that even if the input distribution is standard Gaussian, even if the dimension is arbitrarily large, and even if the target values are generated by such a network, with orthonormal parameter vectors, the problem can still have spurious local minima once $6\le k\le 20$. By a concentration of measure argument, this implies that in high input dimensions, \emph{nearly all} target networks of the relevant sizes lead to spurious local minima. Moreover, we conduct experiments which show that the probability of hitting such local minima is quite high, and increasing with the network size. On the positive side, mild over-parameterization appears to drastically reduce such local minima, indicating that an over-parameterization assumption is necessary to get a positive result in this setting.
1 Introduction
The paper challenges the expectation that simple Gaussian-input ReLU training problems avoid spurious local minima, using computer-assisted analysis and experiments to characterize when they occur and how over-parameterization affects them.
- Motivation: Spurious local minima can make gradient-based methods fail on non-convex neural-network objectives.The paper frames the question of which assumptions might mitigate these optimization problems.
- Setting: The study analyzes simple two-layer ReLU networks trained with expected squared loss under standard Gaussian inputs and realizable targets.The target network uses the same general architecture, with parameter vectors defining the ReLU units.
- Main result: The paper proves that spurious local minima exist for network sizes 6 ≤ k ≤ 20, even with unrestricted dimension and orthonormal target parameters.In high dimensions, concentration and robustness imply that nearly all randomly chosen target networks of these sizes exhibit such minima.
- Proof strategy: The proof runs randomly initialized gradient descent to find suboptimal approximate stationary points with positive-definite Hessians, then formally verifies the conditions computationally.This establishes the existence of strict local minima without requiring analytical formulas for all stationary points.
- Over-parameterization: Mild over-parameterization substantially reduces observed local minima: n = k + 1 yields fewer cases, while none were found for n ≥ k + 2 in tested sizes up to 20.The authors conjecture that sufficiently larger n may permit a no-bad-local-minima result, while noting that larger sizes were not tested.
- Relation to prior work: The work extends prior empirical observations by proving existence and quantifying how local-minimum behavior changes with network size.Earlier positive and negative results generally relied on different settings, restricted parameter regions, favorable initialization, or stronger over-parameterization.
2 Main Result and Proof Technique
The paper proves spurious local minima exist for specified two-layer ReLU objectives and develops a computer-assisted route for certifying them. The result extends to higher dimensions and random approximately orthogonal targets with high probability.
- Main result: Theorem 1 establishes spurious local minima for orthogonal unit target vectors when n = k ranges from 6 through 20, with additional mildly over-parameterized cases.The verified additional cases include (k,n) = (8,9), (10,11), and (11,12) through (19,20).
- Scope: The verification is limited below k = 6 and above network sizes 20, while the authors report that larger sizes are suggested but not established by their theorem.For k,n smaller than 6, the proof technique did not find local minima; the stated theorem is verified only up to k,n ≤ 20.
- Proof technique: The proof seeks a point with small gradient, positive-semidefinite Hessian, and positive objective value, thereby certifying a nearby non-global local minimum.A Taylor-expansion lemma turns approximate stationarity and Hessian curvature into existence of a nearby local minimum; a Lipschitz argument rules out global optimality.
- Proof technique: Gradient descent with random initialization supplies approximate stationary points, while Taylor expansion converts them into nearby local minima despite exact roots being difficult to characterize analytically.The approach is computer-assisted because closed-form roots of the objective’s gradient are not readily available.
- Extensions: The result persists in any input dimension d > k, and Gaussian-random target vectors satisfy the theorem with probability at least 1 − exp(−Ω(d)).The higher-dimensional argument pads parameter vectors with zeros and uses concentration of measure to obtain approximate orthogonality.
3 Experiments
The experiments combine randomized gradient descent with rigorous verification to measure how often it reaches spurious local minima across network sizes. They find frequent minima near n=k, rapidly increasing with size, while mild over-parameterization greatly reduces them.
- Experimental setup: 1000 gradient-descent runs were performed for each architecture, with candidate points filtered by objective value and verified using rigorous local-minimum conditions.Verification included gradient, Hessian, remainder, and Lipschitz bounds, plus checks that enclosing balls contain no singular points.
- Observed minima: The probability of converging to a spurious local minimum increases rapidly with k and n when n≈k.The detected minima were strict, and only a tiny fraction of candidate points could not be verified.
- Over-parameterization: No local minima were found for n≥k+2 with n≤20, while minima for n=k+1 were much scarcer than for n=k.The authors caution that larger values of k and n may behave differently.
- Objective values: Larger architectures both increase the chance of converging to local minima and tend to produce worse objective values at those minima.Figure 1 displays the empirical distribution of attained objective values over 1000 instantiations for several architectures.
- Examples: For n=k=6, three of 1000 runs converged near essentially identical minima with objective value at least 0.02508.Each suspicious point was within distance 1.12·10^-7 of a local minimum.
- Examples: For k=8 and n=9, one of 1000 runs converged to a verified local minimum with objective value at least 0.02056.The detected point was within distance 7.8·10^-8 of a local minimum.
4 Proofs
The proofs use standard matrix notation and invoke Weyl’s inequality to control how perturbations affect eigenvalues. This supplies a spectral tool for the later local-minimum verification.
- Notation: The proof section defines notation for vectors, normalized vectors, matrices, index sets, and spectral norms.For a matrix M, ||M||sp denotes its spectral norm, and [k] abbreviates {1,…,k}.
- Spectral perturbation: Weyl’s inequality bounds eigenvalue deviations between two symmetric matrices by the spectral norm of their difference.The theorem compares ordered eigenvalues of A and B when A−B=P and ||P||sp≤ϵ.
- Spectral perturbation: The matrix perturbation result provides the proof framework for controlling spectral quantities under approximation.This role is directly reflected in the theorem’s comparison of eigenvalues under a bounded perturbation.
4.1 Proof of Thm. 1
The proof of Theorem 1 reduces the problem to orthogonal target vectors, derives closed-form objective derivatives, and rigorously certifies numerically discovered candidate minima. Symbolic error bounds control the Hessian spectrum and higher-order terms.
- Reduction: It suffices to analyze standard-basis target vectors because orthogonal choices are related by rotations or reflections that preserve local-minimum structure.The proof therefore fixes a particular orthogonal configuration without loss of generality.
- Closed-form analysis: The objective, gradient, and Hessian are written in closed form and used throughout the verification procedure.The closed-form representation removes the expectation from the expressions evaluated by the proof code.
- Certification: Candidate points from random gradient descent are certified by bounding gradient norms, lower-bounding the smallest Hessian eigenvalue, controlling the remainder, and proving Lipschitzness.These bounds establish that a numerically found stationary point lies near a genuine local minimum.
- Certified computation: The proof uses variable precision arithmetic and symbolic computations to avoid relying on unqualified floating-point accuracy.The implementation uses MATLAB’s VPA package for guaranteed numerical accuracy.
- Spectral certification: The eigenvalue procedure combines floating-point spectral decomposition with symbolic bounds on approximation and orthogonality errors.Weyl’s inequality then bounds the deviation between the computed and true spectra.
- Remainder control: The higher-order remainder bound is handled by fixing a radius first and checking that the resulting enclosing radius is smaller than that initial choice.This resolves the circular dependence between the radius and the third-order bound.
4.2 Proof of Corollary 1
The proof extends a constructed non-global local minimum from a finite-dimensional setting to arbitrary higher dimensions, then uses concentration and rotational symmetry to cover random target networks.
- Embedding into higher dimensions: The construction embeds parameters and targets into R^(k+m) by appending zero coordinates, preserving the relevant derivative and Lipschitz bounds.The same constants allow the simulation-based argument to apply in every optimization space R^(n(k+m)) for natural m ≥ 0.
- Boundary case: The m = 0 case may alter the eigenvalue lower-bound constant, but this can only strengthen the lower bound and does not invalidate the experiments with m = 1.The qualification is isolated in a footnote to the higher-dimensional extension.
- Random target networks: For random target vectors, concentration makes all pairwise inner products small with probability at least 1 − exp(−Ω(d)) when the dimension is sufficiently large.This permits an orthogonal transformation and positive scaling that place the random vectors within ϵ of standard basis vectors.
- Transfer by symmetry: Gaussian rotational symmetry and ReLU positive homogeneity preserve local minima under the corresponding scaling and rotation, reducing the random case to the constructed case.The transformed objective has the same local minima, so existence for the approximate basis vectors follows from stability of the finite-dimensional construction.
- Non-global local minimum: The embedded construction retains a local minimum that is strictly worse than the global optimum, so the minimum is non-global.The proof identifies a minimizer inside a ball whose boundary has larger objective value and whose interior excludes global minima.
4.3 Technical Proofs
The technical proofs characterize Hessian blocks and their spectra, supplying spectral-norm formulas used to control the objective and establish the local-minimum construction.
- Hessian structure: The Hessian is organized into n × n blocks of size d × d, with diagonal and off-diagonal blocks determined by derivatives of the pairwise functions.This block structure enables the spectral analysis of the objective's second derivatives.
- Spectral norms: The spectral norm of h1(w,v) is sin(θw,v)||v||/(π||w||), while the spectral norm of h2(w,v) is (π − θw,v + sin(θw,v))/(2π).These formulas summarize the spectra computed for the two Hessian-related blocks.
- Spectrum of h1: The largest eigenvalue of h1 is π||w||.The calculation also identifies zero as an eigenvalue in the normalized direction considered.
- Spectrum of h2: The largest eigenvalue of h2 is (π − θw,v + sin(θw,v))/(2π).The remaining eigenvalues arise from symmetric and antisymmetric combinations of normalized vectors.