Elimination of All Bad Local Minima in Deep Learning

Motivation

• Non-convexity and high dimensionality make it unclear whether training avoids arbitrarily poor local minima.Theoretical guarantees remain difficult despite deep neural networks’ empirical success.Source: §1 · p. 1

Prior work

• Existing theory often relies on significant over-parameterization, model simplification, strong assumptions, or restricted settings.Prior positive results include restrictions involving shallow networks, Gaussian inputs, and special architectures or losses.Source: §1 · pp. 1–2
• Earlier neuron-augmentation results handled only single-output binary classification with a special smoothed hinge loss.Removing the single-output and special-loss restrictions remained an open problem.Source: §1 · pp. 1–2

Contribution

• Adding one neuron per output unit eliminates all suboptimal local minima for deep networks in multi-class classification, binary classification, and regression with arbitrary loss functions.The result applies without significant over-parameterization or model simplification, except for the added neurons.Source: §1 · p. 2
• The perturbable gradient basis condition provides a proof technique for studying local-minimum elimination and broader objective-function transformations.The paper presents PGB as a source of new insight beyond this specific construction.Source: §1 · p. 2

Limitation

• Eliminating suboptimal local minima does not immediately guarantee efficient optimization of general neural networks.The paper characterizes a failure mode affecting gradient-based optimization methods.Source: §1 · p. 2

2.2 Result for arbitrary datasets

• Adding one neuron per output unit yields a modified objective whose every local minimum has original-network parameters achieving a global minimum of the original objective.The result applies to arbitrary datasets under differentiable convex per-example losses, including squared, cross-entropy, and smoothed hinge losses.Source: §2.2 · p. 2
• The added neurons automatically vanish at every local minimum, so the modified network equals the original network for all inputs.Source: §2.2 · p. 2
• The guarantees remain applicable to many common tasks because the stronger loss assumption covers standard squared, cross-entropy, and smoothed hinge losses.Source: §2.2 · p. 2

2.3 Result for realizable datasets

• For realizable datasets, weaker loss assumptions plus label consistency additionally ensure each training prediction is a global minimum of its per-example loss.With an appropriate classification loss, this implies correct classification of all training data points at every local minimum.Source: §2.3 · p. 3

2.4 Non-vacuousness, consistency, and effect of over-parameterization

• The theorems are consistent even when no local minimum exists, and other local-minimum cases occur without sample-wise global minima or weak over-parameterization.Example 5 is cited as such a case.Source: §2.4 · p. 3
• The modified objective has local minima under weak dataset-specific over-parameterization, unlike prior results requiring significant over-parameterization for all datasets.The paper states that its requirement is ˜Ω(1) parameters, compared with prior requirements of ˜Ω(H12n8) or ˜Ω(n).Source: §2.4 · p. 3

3 PGB necessary condition beyond elimination of local minima

• The condition is formulated under differentiability and convexity assumptions on component functions, together with a perturbation-preserving vector set and scaling relation.The vector set V[z, ϵ] contains bounded perturbations preserving the relevant functions, and equality holds when ρ = 1.Source: §3 · pp. 3–4
• The PGB condition states that every local minimum of an objective Q globally minimizes a transformed objective built from perturbable gradient basis functions.This applies whether Q is convex or non-convex and for sufficiently small perturbations.Source: §3 · p. 4
• For linear component functions, the PGB condition recovers the known result that every local minimum is a global minimum of the original objective.The condition also extends prior results for deep linear and nonlinear residual networks and supports analysis of objective transformations and regularization.Source: §3 · p. 4
• Geometrically, the output at a local minimum is globally optimal within the span of tangent spaces generated by perturbed parameter points.This translates local optimality in parameter space into global optimality in an output-space subspace.Source: §3 · p. 4

4 Application of PGB necessary condition for elimination of local minima

• The PGB model is expressive enough that its global minimum equals the global minimum of the original model, eliminating all suboptimal local minima.Geometrically, the perturbed tangent-space span contains the output directions needed to optimize the original network.Source: §4 · pp. 4–5
• The proof fixes the original parameter vector θ and treats the added-neuron parameters as the variables of the PGB objective.The construction identifies the auxiliary output and regularization components used in the PGB framework.Source: §4 · p. 5
• At a local minimum, stationarity in the added-neuron parameters forces every added output coefficient a_k to zero, so the modified objective equals the original objective.The auxiliary neurons therefore vanish at local minima.Source: §4 · p. 5
• Perturbations preserving the auxiliary outputs generate a full-rank exponential matrix across distinct input points, enabling the PGB model to represent the needed changes in original-network outputs.Analyticity ensures a sufficiently small perturbation with nonzero determinant, after which coefficients α can realize the required values.Source: §4 · p. 5
• Consequently, for any alternative original parameter vector θ′, the loss at θ is no larger than the loss at θ′, proving that θ is globally optimal.This establishes the main theorem’s global-minimum conclusion.Source: §4 · p. 5

5 Failure mode of eliminating suboptimal local minima

• The paper presents this as a novel failure mode that also applies to prior local-minimum-elimination results.The authors state that earlier work did not discuss this failure mode.Source: §5 · p. 6
• Theorem 4 states that if θ is not globally optimal for L, the modified objective has no local minimum over the added-neuron parameters.The theorem also constructs settings exhibiting this behavior.Source: §5 · p. 6
• The main theorem guarantees global optimization only if an algorithm successfully finds a local minimum of the modified objective.Thus, local-minimum elimination is a conditional optimization guarantee rather than an efficient-solution guarantee.Source: §5 · p. 6
• Under gradient descent, trajectories moving toward a modified-objective local minimum either reach a global minimum of L or drive the added parameters’ norm toward infinity.Monitoring the auxiliary-parameter norm can detect this failure mode and motivate hybrid local-global optimization.Source: §5 · p. 6

6 Examples

• The examples establish both ‘good’ cases where ˜L helps train the original network and ‘bad’ cases where it does not.The section combines numerical and analytical illustrations of these outcomes.Source: §6 · p. 6, §6.1 · p. 6

6.1 Numerical examples

• In the numerical example, ˜L has global minima near θ = 0.8, while gradient-based optimization initialized near θ = 0.2 can still converge suboptimally or diverge.The plotted objective fixes other parameters at solutions for each given (θ, b).Source: §6.1 · p. 6, Figure 1 · p. 7
• The numerical construction uses a one-sample objective with an extra parameter whose effect disappears because x1 = 0.This provides the setting for the failure-mode illustration.Source: §6.1 · p. 6
• The numerical example also highlights that compactness required by a classical Weierstrass existence argument can fail for the auxiliary optimization subspace.Lower semicontinuity holds, but the relevant sublevel set is not compact.Source: §6.1 · p. 6

6.2 Analytical examples

• The analytical examples show that auxiliary parameters may have no finite local minimum when θ is suboptimal, with objective values approached as a → 0− and b → ∞.For the one-point squared-loss case, ˜L approaches 0 without attaining a solution in the finite parameter space.Source: §6.2 · pp. 6–7
• With two distinct data points, a = 0 is likewise not a local minimum because arbitrarily small perturbations can reduce ˜L.The construction uses unequal exponential responses and perturbations of w when they initially match.Source: §6.2 · p. 7
• When the two inputs coincide, a global minimum of L can instead make a = 0 a local minimum of ˜L, illustrating a contrasting analytical case.The modified objective is bounded below by 2 + ϕ(a2) in this setting.Source: §6.2 · p. 7

• The analysis addresses the regime without significant over-parameterization or model simplification, unlike much prior work.Source: §7 · p. 8
• Compared with Liang et al. (2018), the results cover multiple output units, common loss functions, multi-class classification, regression, and standard binary-classification losses.Source: §7 · p. 8
• Theorem 4 and analytical examples establish a failure mode in which adding a neuron can still leave the resulting network subject to problematic optimization behavior.Source: §7 · p. 8
• The paper introduces a concise PGB-based proof, alongside an elementary proof, and explains why the perturbable gradient basis reaches the global minimum value of L(θ).The PGB condition may also analyze models and objective-function modifications beyond local-minimum elimination.Source: §7 · p. 8
• The proofs differ from prior one-dimensional analyses because this paper permits high-dimensional outputs, rank-deficient nonzero output matrices, and losses lacking twice differentiability.Source: §7 · p. 8

8 Conclusion

• If an algorithm finds a local minimum of ˜L, it recovers a global minimum of the original objective L.The conclusion also proposes monitoring the added-parameter norm within a hybrid local–global optimization approach.Source: §8 · p. 8
• The theory reduces getting stuck near an arbitrarily poor local minimum to detecting divergence of the norm of (a, b, W).Source: §8 · p. 8
• The paper extends theoretical understanding in a regime less studied than significant over-parameterization or model simplification and introduces PGB for broader objective analyses.Source: §8 · p. 8

A Proofs of Theorem 3

• Theorem 3’s proof uses local-minimum perturbations, differentiability, and first-order necessary conditions to constrain nearby perturbable directions.Source: A Proofs of Theorem 3 · pp. 11–12
• Theorem 3’s algebraic substitutions establish the claimed equality through bounds over finite perturbation sets and coefficient choices.Source: A Proofs of Theorem 3 · p. 12

B Proofs of eliminating local minima

• The elementary proofs first identify candidate local minima with a = 0, then use small perturbations, rearrangements, and interpolation to prove the desired global-minimum result.Source: B Proofs of eliminating local minima · p. 12
• The proofs keep θ arbitrary so the same construction can establish the later failure mode for eliminating suboptimal local minima.Source: B Proofs of eliminating local minima · p. 12

B.1 Proof of Theorem 1 without the PGB necessary condition

• For Theorem 1, differentiability makes the restricted modified objective stationary at every local minimum over the added-neuron parameters.Source: §B.1 · p. 12
• This representation proves L(θ′) ≥ L(θ) for any θ′, so θ is a global minimizer, while the added-neuron coefficients vanish at the local minimum.Source: §B.1 · pp. 12, 15
• Perturbations around a local minimum with a = 0 produce constraints on the added-neuron responses through differentiability of the loss.Source: §B.1 · pp. 12–13
• The construction uses tensor products of input vectors and asserts that, for any θ′, there exist an order p and vectors ut,k indexed by t = 0, …, p and k = 1, …, dy.Source: §B.1 · p. 14

B.2 Proof of Theorem 2

• Theorem 2 extends the argument under weaker loss assumptions and an additional dataset assumption, yielding zero loss gradients at every training point.Source: §B.2 · p. 15

• For any θ, every local minimum over the added parameters implies that θ is a global minimum of L; therefore suboptimal θ admits no such local minimum.Source: C Proof of Theorem 4 · pp. 15–16
• The failure mode is characterized by a suboptimal θ whose loss-gradient vector lies in the null space of A[θ] and remains there after adding g(·; a, b, W).Source: C Proof of Theorem 4 · p. 16

D Additional numerical examples for good cases

• Figure 3 compares standard training-loss histograms for original networks, modified networks, and modified networks with failure-mode monitoring.The experiments used the Semeion handwritten-digit dataset and the KMNIST Japanese-letter dataset.Source: Figure 3 · p. 16, D Additional numerical examples for… · p. 16
• The elimination of local minima helped a gradient-based method for Semeion but did not help much for KMNIST.The comparison used 1000 random trials for Semeion and 100 random trials for KMNIST under identical settings.Source: D Additional numerical examples for… · p. 16
• For KMNIST, monitoring the added parameters’ norms detected the failure mode and triggered optimizer restarts to search a better subspace.The detector restarted training when ∥a∥2 + ∥b∥2 + ∥W∥2 ≥7.Source: D Additional numerical examples for… · p. 16

E Additional numerical and analytical examples to illustrate the failure mode

• With squared loss, the failure mode from Theorem 4 is reproduced in an analytically identical setting to Figure 1.Figure 4 uses a single sample with y1 = f(x1; 0.8) and squared loss.Source: E Additional numerical and analytical… · p. 17, Figure 4 · p. 17
• Examples 6 and 7 show the same failure phenomena under a smoothed hinge loss instead of squared loss.Example 6 uses one data point, while Example 7 uses two data points.Source: E Additional numerical and analytical… · p. 17
• For Example 6, no finite auxiliary-parameter local minimum exists when the original network is at a non-global minimum.A perturbation with sufficiently small positive a lowers the modified objective from 8.Source: E Additional numerical and analytical… · p. 17
• Example 7 likewise has no auxiliary-parameter local minimum, with a construction in which a, b, and ∥w∥ diverge as ϵ →0.The example uses two distinct data points and reports the same non-attainment behavior in R × R × R^dx.Source: E Additional numerical and analytical… · p. 17