PaperlayerView exact revision on arXiv

Source-linked AI summary

No bad local minima: Data independent training error guarantees for multilayer neural networks

Daniel Soudry, Yair Carmon

arXiv:1605.08361v2stat.MLcs.LGcs.NE

TL;DR

The paper asks why local optimization can avoid bad minima in non-convex MNN training under practical over-parametrization. It uses smoothed analysis of piecewise-linear, scalar-output MNNs with quadratic loss and dropout-like noise, proving zero training error at differentiable local minima under stated width conditions.

  • Problem

    The paper addresses whether practical, finite-width MNNs can have high-training-error local minima despite SGD converging to stable local minima of a non-convex loss.

  • Method

    The paper applies smoothed analysis to piecewise-linear, single-output MNNs with quadratic loss and multiplicative dropout-like noise, analyzing differentiable local minima.

  • Results

    Zero training error occurs at every differentiable local minimum for one hidden layer when N ≤ d0d1, while deeper networks receive a perturbation-based guarantee when N ≤ dL−2dL−1.

  • Takeaways & Limitations

    The guarantees suggest a theoretical explanation for why local updates such as SGD can optimize these highly non-convex MNN losses effectively.

  • Takeaways & Limitations

    The analysis focuses on empirical training error at differentiable local minima and does not yet fully use all parameters in the deeper-network result.

Abstract

from arXiv · show

We use smoothed analysis techniques to provide guarantees on the training loss of Multilayer Neural Networks (MNNs) at differentiable local minima. Specifically, we examine MNNs with piecewise linear activation functions, quadratic loss and a single output, under mild over-parametrization. We prove that for a MNN with one hidden layer, the training error is zero at every differentiable local minimum, for almost every dataset and dropout-like noise realization. We then extend these results to the case of more than one hidden layer. Our theoretical guarantees assume essentially nothing on the training data, and are verified numerically. These results suggest why the highly non-convex loss of such MNNs can be easily optimized using local updates (e.g., stochastic gradient descent), as observed empirically.

1 Introduction

The paper addresses why SGD can succeed on highly non-convex MNN losses despite possible bad local minima. It seeks training-error guarantees under practical over-parametrization, using smoothed analysis with dropout-like noise.

  • SGD is guaranteed to converge only to critical points or stable local minima, leaving open why it avoids minima with high training error.
  • Extremely wide networks can yield low training error at local minima, but may require too many parameters and create overfitting concerns.
  • Modern state-of-the-art MNNs are often deep and over-parametrized, while their apparent under-fitting makes training error a potential performance bottleneck.
  • The paper proves zero training error at every differentiable local minimum for one-hidden-layer MNNs when N ≤ d0d1.
  • For L ≥ 3 layers, potentially bad differentiable local minima can be averted by a small weight perturbation and fixing all but the last two weight layers when N ≤ dL−2dL−1.
  • Smoothed analysis establishes these guarantees almost everywhere over datasets and dropout-like noise, requiring essentially no structure in the input data.

2 Related work

Prior explanations of benign MNN optimization rely on very wide networks, qualitative analogies, or restrictive data assumptions. Their relevance to realistic finite networks and datasets therefore remains uncertain.

  • Highly non-convex MNN losses contain multiple local minima, motivating concern that SGD could become trapped at minima with high training error.
  • Making the last hidden layer wider than the sample count can achieve zero training error, but requires many weights and can cause strong overfitting.
  • Empirical studies report smooth descent paths without barriers and local-minimum training error similar to global-minimum error in narrower MNNs.
  • Statistical-mechanics explanations may not transfer directly to realistic MNNs because they use qualitative analogies, implausible assumptions, or infinite-width limits.
  • Earlier theoretical guarantees often assume linearly separable data, d0 > N, class clustering, or particular input distributions.

3 Preliminaries

The preliminaries specify a finite-sample MNN with scalar outputs, layer weights, piecewise-linear activations, quadratic loss, and multiplicative dropout-like noise. Results are formulated using almost-everywhere measure-theoretic guarantees.

  • Model: The model is optimized on a finite training set with inputs x^(1), ..., x^(N) and scalar target outputs y^(1), ..., y^(N).
  • Model: The network has L layers, weight matrices W_l, and layer widths d_l; biases are ignored for simplicity.
  • Activations: Piecewise-linear activations, including leaky ReLU and related functions, are represented through matrix-product forms with activation slopes.
  • Noise: The multiplicative noise matrices E_l act like dropout noise, and continuous noise distributions such as Gaussian are covered by the analysis.
  • Measure-theoretic terminology: A property holding almost everywhere fails only on a measure-zero set; with Gaussian noise, the stated results hold with probability 1.
  • Loss function: The loss uses output error e = v_L − y and mean squared error evaluated through the empirical expectation over training samples.

4 Single Hidden layer

For one-hidden-layer MNNs, rank conditions at differentiable local minima force zero training error almost everywhere under mild over-parametrization.

  • Setup: The analysis studies differentiable local minima of the MSE because SGD asymptotically converges to such points under mild conditions.The model is considered in the common over-parametrized setting.
  • Method: Reparameterizing the second-layer weights into the first-layer notation preserves the MSE and transfers local-minimum constraints to the simplified formulation.The actual network weights and activation slopes are not changed by this notational simplification.
  • Rank argument: At a differentiable local minimum, the error vector lies in the right nullspace of G1, so rank(G1) = N implies zero error.The nullspace dimension is N − rank(G1), leaving only e = 0 when G1 has full row rank.
  • Rank argument: For N ≤ d1d0, rank(G1) = rank(A1 ◦ X) = N simultaneously for every w almost everywhere over the data and noise.The proof handles the dependence of A1 on X by considering all finitely many possible activation-sign patterns.
  • Result: Therefore, all differentiable local minima are global minima with MSE = 0 whenever N ≤ d1d0, almost everywhere in (X, E1).The width threshold is tight: d1 = ⌈N/d0⌉ is also the minimal width needed to implement any dichotomy for inputs in general position.

5 Multiple Hidden Layers

For deeper MNNs, the last two layers provide enough generic linear constraints to force zero-loss local minima, while small perturbations can remove fragile bad minima.

  • Gradient constraints: For each weight layer, differentiating the MSE yields linear constraints on the training-error vector, which can be combined into a gradient matrix G.If G has rank N, these constraints imply e = 0.
  • Theorem 5: For N ≤ dL−2dL−1, fixing the first L−2 layers makes every differentiable local minimum over the last two layers a global minimum with MSE = 0 almost everywhere.This holds for almost every dataset, dropout-like noise realization, and fixed configuration of the earlier layers.
  • Theorem 5: The two-layer adjustment requires more than N weights in WL−1, whereas optimizing only the final layer generally requires the much wider condition dL−1 ≥ N.The paper contrasts the resulting parameter requirements with the single-last-layer strategy.
  • Extensions: Theorem 5 extends to architectures with convolutional lower layers and remains valid with modified noise assumptions, though fixing EL−2 weakens the width condition.With EL−2 fixed, the condition becomes N ≤ dL−1 minl≤L−2 dl.
  • Corollary 6: A small random perturbation of all weights makes bad differentiable local minima avoidable when N ≤ dL−2dL−1, after which the first L−2 layers are held fixed.With probability 1 over the perturbation, all remaining differentiable local minima over the last two layers are global minima.
  • Hessian and fragility: At the zero-weight critical point for L ≥ 3, the Hessian is zero rather than a strict-saddle certificate, but the point is fragile under perturbation.Positive-semidefinite Hessian constraints otherwise generically push the error toward small values.

6 Numerical Experiments

The experiments test the theoretical guarantees on synthetic and MNIST data, finding low or zero training error in the predicted over-parametrized regimes and numerical evidence for differentiable local minima.

  • Without dropout, the results are not guaranteed when GL−1 lacks full rank, including networks whose weights are all negative.The experiments therefore assess conditions under which the activation matrix is sufficiently variable.
  • For one hidden layer, the error reaches zero when the non-redundant parameter-to-sample ratio satisfies d2/N ≥1, as predicted by Theorem 4.For two hidden layers, the same threshold shows a looser but similar pattern.
  • Figure 6.1 evaluates one- and two-hidden-layer ReLU MNNs without dropout on synthetic random data and MNIST subsets using mean classification error over 30 repetitions.Zero mean classification error occurred in all 30 repetitions at a data point.
  • The experiments used Adam with random dataset permutations, He-style initialization, and dataset- and architecture-specific learning rates and mini-batch sizes.Training in Figure 6.1 lasted no more than 4000 epochs and stopped when MCE reached zero.

7 Discussion

The paper concludes that mildly over-parametrized MNNs have zero training error at differentiable local minima under its stated conditions, while highlighting overfitting and several scope boundaries.

  • Theorem 4 proves that, almost everywhere, one-hidden-layer MNNs have zero MSE at every differentiable local minimum when d0d1 > N.The proof uses local similarity between the MNN loss and linear regression.
  • For deeper MNNs, Theorem 5 uses a perturbation and fixes some weights so that, when N ≤dL−2dL−1, differentiable local minima are global minima with MSE = 0.The guarantee focuses on the last two weight layers rather than all network parameters.
  • Zero training error is not necessarily the intended practical objective because it may encourage overfitting.The discussion suggests reducing model size or increasing effective sample count to obtain relatively small error in a mildly under-parameterized regime.
  • The non-asymptotic smoothed-analysis argument studies slight random perturbations of worst-case inputs and dropout, while experiments suggest similar behavior without dropout.The paper does not claim that dropout itself has merit in the excerpted discussion.
  • Future work includes multi-output networks, other convex losses, stable non-differentiable critical points, improved use of deeper-layer parameters, and combining training-error with generalization guarantees.

Appendix

The appendix introduces activation slopes and activation patterns, then uses an almost-everywhere intersection fact to organize the proof analysis.

  • Each layer, data instance, and index has an activation slope a(n),l that takes one of two values.
  • The matrices A1 through AL−1 encode activation slopes across layers and data instances.
  • There are at most P = 2^N∑L−1_l=1 d_l distinct activation-pattern values, indexed by p.
  • For each activation pattern p, A^p_l denotes the corresponding value of A_l.
  • If finitely many properties hold almost everywhere, their intersection also holds almost everywhere.

A Single hidden layer — proof of Lemma 3

For a single hidden layer, the proof establishes full row rank for the relevant gradient matrix almost everywhere, which forces zero error at differentiable local minima.

  • For L = 2 and N ≤ d1d0, rank(G1) = rank(A1 ◦ X) = N simultaneously for every w almost everywhere.
  • The proof fixes an activation pattern and applies the rank identity to that pattern-specific gradient matrix.
  • Repeating the argument over all 2^Nd1 activation patterns and using the intersection fact yields the rank guarantee for every weight configuration.

B Multiple Hidden Layers — proof of theorem 5

For multiple hidden layers, the proof combines a generic polynomial rank argument with activation-pattern enumeration to show that local minima over the final two layers have zero MSE almost everywhere.

  • B Multiple Hidden Layers — proof of theorem 5: Lemma 8 states that a polynomial matrix with one full-column-rank instance has full column rank for almost every parameter value.
  • B Multiple Hidden Layers — proof of theorem 5: For N ≤ dL−2dL−1, every differentiable local minimum over WL−1 and WL is global with MSE = 0, while earlier weights remain fixed.
  • B Multiple Hidden Layers — proof of theorem 5: The argument normalizes the final-layer weights by absorbing them into the preceding weight layer and keeps activation slopes unchanged under the simplified notation.
  • B Multiple Hidden Layers — proof of theorem 5: The proof applies this lemma to each fixed activation pattern after constructing one parameter choice with rank N.
  • B Multiple Hidden Layers — proof of theorem 5: Enumerating all activation patterns and intersecting their almost-everywhere guarantees gives rank(GL−1) = N simultaneously for every WL−1.
  • B Multiple Hidden Layers — proof of theorem 5: The resulting condition means a small weight perturbation followed by optimizing the final two layers can avert potentially bad differentiable local minima.
Loading 1605.08361v2…