Source-linked AI summary
Adding One Neuron Can Eliminate All Bad Local Minima
Shiyu Liang, Ruoyu Sun, Jason D. Lee, R. Srikant
TL;DR
Non-convex neural-network losses can contain bad local minima, making their optimization landscape difficult to analyze. The paper adds a special neuron and regularizer to binary-classification networks and proves that every local minimum is global, while the added neuron is inactive at such minima. The result extends to adding one special neuron per layer, subject to stated assumptions and architectural limitations.
Problem
Non-convex neural-network losses may have bad local minima, while existing landscape results often rely on strong assumptions or weaker guarantees.
Source: §1 · pp. 1–2Method
The paper augments a binary-classification network with an exponential neuron and positive quadratic regularizer, or one special neuron per layer.
Source: §1.1 · p. 2, §3.2 · p. 4, §4.1 · p. 5Results
Every local minimum of the augmented loss is global, achieves minimum loss and misclassification rate, and leaves the original network’s output unchanged.
Source: §3.2 · p. 4Takeaways & Limitations
A network can be made free of bad local minima by adding one special neuron, with the augmentation inactive at every local minimum.
Source: §3.2 · p. 4, §6 · p. 10The result assumes a twice-differentiable loss and, for the layerwise extension, excludes non-smooth activations such as ReLU and Leaky ReLU.
Source: §3.1 · p. 3, §4.1 · p. 6
Abstract
from arXiv · showhide
One of the main difficulties in analyzing neural networks is the non-convexity of the loss function which may have many bad local minima. In this paper, we study the landscape of neural networks for binary classification tasks. Under mild assumptions, we prove that after adding one special neuron with a skip connection to the output, or one special neuron per layer, every local minimum is a global minimum.
1 Introduction
The paper targets the difficulty of proving global landscape guarantees for nonlinear neural networks, where existing results often require strong assumptions or cover only subsets of local minima. It shows that adding one special neuron and regularizer yields an architecture whose every local minimum is globally optimal.
1 Introduction
- Existing analyses often require linear activations, independence, substantial overparameterization, or other strong assumptions, and many do not cover all local minima.The paper frames a result covering every local minimum under milder architectural and dataset assumptions.Source: §1 · pp. 1–2
1.1 Our Contributions
- For binary classification with smooth hinge loss, adding a special neuron and quadratic regularizer removes bad local minima and makes every local minimum achieve minimum misclassification error.The special neuron can be exponential.Source: §1.1 · p. 2
- The added neuron can be implemented as a skip connection from input to output or replaced by one special neuron in each layer.The skip connection is therefore not essential to the stated extension.Source: §1.1 · p. 2
- The contribution is presented as the first no-spurious-local-minima result for a wide class of deep nonlinear networks.The authors characterize networks with one special neuron as one neuron away from a “good” network.Source: §1.1 · p. 2
2 Preliminaries
The preliminaries define a general L-layer feed-forward network for binary classification and introduce its parameters, outputs, empirical loss, training error, and tensor-product notation.
Preliminaries
- The feed-forward model uses weight matrices and bias vectors between successive layers, followed by an output weight vector and bias scalar.The input dimension is d, with M0 = d.Source: §2 · p. 2
- For binary classification, each sample has a feature vector and label yi ∈ {−1, 1}, and the empirical loss averages ℓ over network outputs on the dataset.Training error is defined as the dataset misclassification rate.Source: §2 · pp. 2–3
- The notation also defines tensor products of vectors and componentwise tensor contraction with indexed vectors.These definitions support later expressions involving higher-order tensors.Source: §2 · p. 3
3 Main Result
Under smooth loss and realizability assumptions, the paper augments an arbitrary neural network with an exponential neuron and regularizer, then proves that every augmented local minimum is globally optimal while preserving the original network’s output.
3.1 Assumptions
- The loss must be twice differentiable and non-decreasing, with all critical points globally minimizing and global minimizers occurring at negative arguments.Polynomial hinge loss with p ≥ 3 is given as an example.Source: §3.1 · p. 3
- The realizability assumption requires some parameter setting that correctly classifies every sample, although convex losses allow the main result without this assumption.The paper relates this assumption to observed zero training misclassification in neural networks.Source: §3.1 · p. 3
3.2 Main Result
- The construction adds an exponential-neuron output to the original network and adds a positive quadratic regularizer on its coefficient.The regularizer is intended to make the exponential neuron inactive at every local minimum.Source: §3.2 · p. 4
- Every local minimum of the augmented empirical loss is global, and its original-network parameters attain both minimum loss and minimum misclassification rate.This is Theorem 1 under Assumptions 1 and 2.Source: §3.2 · p. 4
- At every local minimum, the augmented and original networks are equivalent, so the added exponential neuron does not change the represented function.The augmentation improves the loss landscape without changing the original network’s representing power.Source: §3.2 · p. 4
- The regularizer is necessary for the result on arbitrary datasets, and the skip-connection theorem’s extension excludes non-smooth activations such as ReLU and Leaky ReLU.Without the regularizer, prior work found bad local minima for some datasets; the architectural extension requires differentiable activations.Source: §3.2 · p. 4
4 Extensions
The extensions preserve the paper’s local-to-global landscape result across alternative architectures, neuron types, inconsistent labels, and higher-order stationary points, with assumptions adjusted by setting.
4.1 Eliminating the Skip Connection
- Adding one exponential neuron per layer preserves global optimality: every local minimum is global, and the original network attains minimum loss and misclassification rate.The augmented network is equivalent to the original at every local minimum because all exponential neurons are inactive.Source: §4.1 · pp. 5–6
- The per-layer construction requires differentiable activation functions, so it excludes non-smooth neurons such as ReLUs and Leaky ReLUs.Source: §4.1 · p. 6
4.2 Neurons
- An augmented monomial neuron also removes bad local minima when its degree p is at least the degree t of a polynomial that classifies the dataset.This result applies to arbitrary neural architectures and activation functions defined on R; p ≥ n always suffices for n distinct samples.Source: §4.2 · p. 6
4.3 Allowing Random Labels
- With convex loss, the local-to-global result extends to datasets where identical feature vectors can have different labels, although the minimum misclassification rate may be nonzero.Proposition 2 states that every local minimum is global and achieves both minimum loss and minimum misclassification rate.Source: §4.3 · p. 7
4.4 High-order Stationary Points
- If a degree-p polynomial classifies the data, every k-th order stationary point with k ≥2p is global and achieves minimum training error.For linearly separable data, second-order stationary points suffice; otherwise the result covers fourth- or higher-order stationary points.Source: §4.4 · p. 7
5 Proof Idea
The proof establishes that the augmented network’s local minima satisfy restrictive structural conditions, then uses tensor identities and polynomial interpolation to show they are global minima that also minimize training error.
5.1 Important Lemmas
- Lemma 1 shows that the added exponential neuron is inactive at every local minimum, with a*=0, and imposes moment equations for every non-negative order p.Part (i) follows from first-order conditions, while part (ii) uses high-order perturbations and induction.Source: §5.1 · p. 8, §5.2 · pp. 8–9
5.3 Proof Sketch of Lemma 2
- The tensor lemma converts vanishing diagonal tensor evaluations into a zero tensor using the equality between diagonal and multilinear spectral maxima.The argument also uses the symmetry of the tensors Tk and results from reference.Source: §5.1 · p. 8, §5.2 · p. 8, §5.3 · p. 9
5.2 Proof Sketch of Lemma 1
- The Lemma 1 proof uses exponentially small output perturbations and small weight perturbations, expands the loss, and extracts higher-order constraints by taking ε→0.The perturbation sets |δa|=e^-1/ε and δw=εu, while the Taylor remainder is controlled by a dataset- and minimizer-dependent constant.Source: §5.2 · pp. 8–9
5.4 Proof Sketch of Theorem 1
- Lagrangian interpolation supplies a polynomial with margin at least one on the dataset, which combines with the lemmas and monotone loss assumptions to force global optimality.The proof assumes every loss critical point is globally minimizing and that critical points satisfy z<0, yielding correct sample labels.Source: §5.4 · p. 9
- Every local minimum simultaneously minimizes the augmented loss, the original empirical loss, and the training error.The theorem’s proof derives zero loss derivatives on all samples, global optimality for both parameterizations, and correct training classification.Source: §5.4 · p. 9
6 Conclusions
The paper concludes that adding a special neuron and regularizer removes bad local minima while leaving the original network’s representational behavior unchanged. It also extends this result to multilayer, polynomial-neuron, and non-realizable-label settings.
6 Conclusions
- Adding a special neuron with a quadratic regularizer makes every local minimum globally optimal for binary classification.The construction applies to any neural network and uses an exponential neuron as the special unit.Source: §6 · p. 10
- At every local minimum, the exponential neuron is inactive, so the augmented model does not alter the original network’s representing power.The proof establishes a∗=0 through first-order conditions and higher-order local-minimum information.Source: §6 · p. 10, §A.1 · p. 13, §A.2 · p. 15
- The same no-spurious-minima result holds with one special neuron per layer, with polynomial neurons of data-dependent degree, and when one feature vector has both labels.These extensions preserve the paper’s central landscape guarantee across the stated architectural and data variations.Source: §6 · p. 10
A.1 Proof of Lemma 1(i)
- The first-order conditions directly force the special neuron’s output coefficient to zero when the regularization parameter satisfies λ>0.Differentiating with respect to the neuron’s output weight and bias yields λa∗2=0.Source: §A.1 · p. 13
A.2 Proof of Lemma 1(ii)
- The proof uses exponentially small perturbations of the special neuron’s output weight and its input parameters, followed by limits and induction over tensor orders.The perturbations set |δa|=exp(−1/ε) and δw=εu, allowing local minimality to constrain every relevant tensor equation.Source: §A.2 · p. 13
B Proof of Lemma 2
Lemma 2 converts the local-minimum conditions into vanishing higher-order tensor constraints. Symmetry then reduces the tensor verification to diagonal unit-vector evaluations.
B Proof of Lemma 2
- The tensor is symmetric, so its maximum multilinear value over unit vectors equals its maximum diagonal value.The proof invokes Theorem 1 of reference to replace maximization over u1,...,uk with maximization over a single repeated vector.Source: B Proof of Lemma 2 · p. 15
- At a local minimum, every nonnegative-order tensor defined from the loss derivatives and data is the zero tensor.The result is stated as a consequence of Lemmas 1 and 2 and supplies the key algebraic condition used later.Source: B Proof of Lemma 2 · p. 15
C Proof of Theorem 1
Theorem 1 uses polynomial interpolation and the tensor constraints to show that any local minimum minimizes both the augmented loss and the original network’s training error.
C Proof of Theorem 1
- Polynomial interpolation provides a classifier with margin at least one on every sample, enabling the tensor conditions to force zero loss derivatives at a local minimum.The interpolating polynomial satisfies yiP(xi)≥1 for all samples, and the loss’s monotonicity then yields ℓ′(−yif(xi;θ∗))=0.Source: C Proof of Theorem 1 · p. 16
- Every local minimum of the augmented loss simultaneously minimizes the original empirical loss and the training error.The augmented parameters minimize ˜Ln, while the original parameters θ∗ minimize Ln and Rn.Source: C Proof of Theorem 1 · p. 16
- Because every critical point of the scalar loss is globally minimizing and has negative argument, each local minimum achieves the minimum misclassification rate.The resulting condition yif(xi;θ∗)>0 implies correct classification on every training sample under the theorem’s assumptions.Source: C Proof of Theorem 1 · p. 16
D Proof of Corollary 1
The corollary and multilayer extension show that special neurons become inactive at local minima, reducing the augmented architectures to the original network while preserving the landscape result.
D Proof of Corollary 1
- At a local minimum of the skip-connected model, the special neuron has zero output weight, making the augmented and original networks equivalent.With a∗=0, ˜f(x;˜θ∗)=f(x;θ∗) for every input x.Source: D Proof of Corollary 1 · p. 16
E.1 Notations and Important Lemmas
- In the multilayer construction, every exponential neuron is inactive at every local minimum and therefore contributes nothing to the final output.The architecture in Fig. 2(a) reduces to Fig. 2(b) because the relevant interlayer weights vanish.Source: §E.1 · p. 17
E.2 Proof of Lemma 3
- The multilayer proof first forces the output-layer exponential weight to zero, then inductively forces all connections into exponential neurons to vanish.The induction establishes w(l)∗=0 for l=2,...,L and all corresponding neuron indices.Source: §E.2 · pp. 17–19, §E.3 · p. 22
E.3 Proof of Lemma 4
- After these weights vanish, the exponential-neuron chain has α1=...=αL=0 and the augmented network reduces to the original network’s computation.The proof separates the original parameters from the exponential-chain parameters before analyzing perturbations of the latter.Source: §E.3 · p. 20
- The multilayer argument analyzes exponentially small parameter perturbations and uses Taylor expansion, continuity, and induction to establish the required derivative identities.The perturbations scale interlayer weights as exp(−1/ε), the final connection as exp(−(L+1)/ε), and other parameters as εu and εv.Source: §E.3 · pp. 21–22
E.4 Proof of Theorem 2
The proof shows that the added exponential neuron is inactive at every local minimum, reducing the augmented network to the original one and yielding global optimality under the stated assumptions.
E.4 Proof of Theorem 2
- A polynomial interpolant with margin at least one makes every training sample attain a global minimum of the loss.This uses the existence of a polynomial P satisfying y_iP(x_i) ≥1 together with the loss assumptions.Source: §E.4 · p. 27
- Consequently, every local minimum of the augmented loss is a global minimum, and the corresponding original parameters globally minimize the original empirical loss.The equivalence of the two networks transfers global optimality from the augmented objective to the original objective.Source: §E.4 · pp. 27–28
- Under the stated loss assumptions, every critical point θ∗ satisfies yi = sgn(f(xi; θ∗)) for every training sample, and θ∗ simultaneously minimizes the empirical loss and training error.Source: §E.4 · p. 28
F.1 Important Lemmas
- At every local minimum, the added neuron's coefficient satisfies a*=0, so the augmented and original networks are equivalent.The proof derives a*=0 from first-order conditions and then uses higher-order perturbations to establish the required lemma.Source: §F.1 · p. 29
F.2 Proof of Proposition 1
The proposition proof constructs a margin-separating polynomial and combines it with the inactive-neuron result to establish global optimality for both augmented and original objectives.
F.2 Proof of Proposition 1
- A Lagrangian interpolating polynomial can classify every sample with margin at least one, enabling the loss derivative to vanish at the relevant parameters.The argument invokes Lemmas 5 and 2 after constructing the polynomial P.Source: §F.2 · p. 31
- The augmented parameters minimize the augmented loss, while the original parameters simultaneously minimize empirical loss and training error.The added exponential neuron is inactive at the minimizing point, so the result transfers to the original network.Source: §F.2 · p. 31
G Proof of Proposition 2
The proposition extends the landscape result beyond fully realizable data by analyzing separable, polynomially representable, and intrinsically conflicting cases.
G Proof of Proposition 2
- When the network itself can classify the dataset, the proof reuses the earlier theorem to establish global optimality of local minima.This is case (1) in the proposition's three-case analysis.Source: G Proof of Proposition 2 · p. 32
- When a polynomial can classify the data but the network cannot, the augmented objective has no local minimum; its critical points are saddle points.The contradiction follows from the assumption that a local minimum exists despite the network's inability to separate the samples.Source: G Proof of Proposition 2 · p. 32
- When identical features carry conflicting labels, the data are partitioned by feature vector and the network predicts each group's majority label.Convexity of the loss makes the resulting prediction minimize misclassification within every group and therefore across the dataset.Source: G Proof of Proposition 2 · pp. 32–33
- In the conflicting-label case, the original network achieves the minimum misclassification rate and the augmented parameters still attain a global minimum of the augmented loss.The proof then compares the augmented objective with arbitrary parameters to establish global optimality.Source: G Proof of Proposition 2 · p. 33
H.1 Important Lemma
- For higher-order stationary points, the added neuron's coefficient is zero and the proof derives directional equalities through perturbation bounds and induction.Lemma 6 establishes a*=0 and an equation for orders q up to floor(k/2), using perturbations with |δa|=ε^((k+1)/2).Source: §H.1 · p. 34
H.2 Proof of Proposition 3
The proof uses a degree-p polynomial interpolant and shows that sufficiently high-order stationarity forces global optimality and minimum training error.
H.2 Proof of Proposition 3
- A degree-p polynomial separates every sample with margin at least one, and the proof requires k≥2p so the higher-order stationary conditions capture its monomials.The condition is equivalent to p≤floor(k/2).Source: §H.2 · p. 36
- Every k-th order stationary point has an inactive added neuron and is therefore a global minimum of both augmented and original empirical losses.The same conclusion also gives minimum training error under the loss assumptions.Source: §H.2 · p. 36