Small nonlinearities in activation functions create bad local minima in neural networks

1 INTRODUCTION

• Nonlinear-network optimality remains difficult to characterize, while deep linear networks have no nonlinear activation and have established results on when local minima are global.The paper frames whether those linear-network properties extend to nonlinear networks as an open challenge.Source: §1 · p. 1

1.1 WHAT IS KNOWN SO FAR?

• Prior nonlinear-network results either use restrictive assumptions such as Gaussian inputs and realizability or give isolated counterexamples rather than generic-dataset guarantees.The paper instead studies empirical risk without assuming Gaussianity or realizability, under the condition that linear models cannot fit the data.Source: §1 · p. 1, §1.1 · p. 2

1.2 CONTRIBUTIONS AND SUMMARY OF RESULTS

• For a realizable dataset, the paper gives an architecture and squared-loss counterexample with a bad local minimum for activations including sigmoid, tanh, arctan, and ReLU.The authors note that this is one counterexample, not a generic-dataset result.Source: §1.2 · p. 3
• The paper’s deep-linear result characterizes critical-point types, and under its stated loss condition the empirical risk has only global minima and saddles.It also gives a condition to distinguish global minima from saddles and subsumes several prior results.Source: §1.2 · p. 3

2.1 MAIN RESULTS AND DISCUSSION 

• For ReLU-like activations, if linear models cannot fit the data, the paper constructs infinitely many spurious local minima, a result applying to almost all practical datasets.The constructed minima have the risk of linear least squares; even a slight nonlinearity suffices.Source: §1.2 · p. 3, §2.1 · p. 4

2.2 ANALYSIS OF THEOREM 1

• A two-step construction first makes hidden-node inputs positive to create a locally linear minimum, then changes their signs to obtain strictly lower empirical risk.This proves the constructed minimum is spurious.Source: §2.2 · pp. 5–6

3.1 MAIN RESULTS AND DISCUSSION

• Activations satisfying (C2.1)–(C2.7) yield a spurious local minimum even though the global minimum has zero empirical risk.The dataset is realizable by the network, so a zero-risk fit coexists with a bad local minimum.Source: §3.1 · p. 7
• The required conditions include sigmoid, tanh, arctan, quadratic, ELU, and SELU activations.The conditions require existence of certain real numbers, rather than global properties of the activation function.Source: §3.1 · p. 7
• Theorem 2 and Corollary 3 provide one counterexample, not a result about generic datasets.The authors suggest the problem could be worse on non-realizable datasets, but present that as a possibility rather than a result.Source: §3.1 · p. 7
• For ReLU-like activations, even the slightest nonlinearity permits a zero-risk global minimum alongside a bad local minimum matching linear least-squares performance.The appendix establishes the result despite these activations violating some conditions used in Theorem 2.Source: §3.1 · p. 7

4 GLOBAL OPTIMALITY IN LINEAR NETWORKS

• Deep linear networks use multilinear parameterization, and the section characterizes how this parameterization relates to the loss evaluated at the product of weight matrices.The network output is formed by multiplying the layer weight matrices and the data matrix.Source: §4 · p. 7

4.1 MAIN RESULTS AND DISCUSSION

• The theorem applies when hidden layers are wide enough for the weight product to attain full rank and the loss on that product is differentiable.A sufficient condition for the theorem's rank condition is that the product has full rank.Source: §4.1 · p. 8
• At a network critical point, a nonzero gradient of the loss at the weight-matrix product implies a saddle; under the stated rank condition, the product is stationary and critical-point types match.The matching covers local minima, local maxima, and saddles.Source: §4.1 · p. 8
• If every critical point of the differentiable loss on the weight-matrix product is a global minimum, the deep linear network has only global minima and saddle points.The result also supplies a checkable condition for distinguishing global minima from saddles.Source: §4.1 · p. 8

Discussion and future work

• Theorems 1 and 2 establish spurious local minima for nonlinear networks on almost all datasets and for a wide class of activations.Theorem 4 gives a general result on critical points in multilinearly parametrized functions, unifying existing results on linear networks.Source: §5 · p. 9
• Future work includes measuring how far local minima are from global minima and how network size affects that gap.The paper also proposes studying loss surfaces under parameter-space restrictions such as regularization, and analyzing gradient-descent trajectories.Source: §5 · p. 9
• The results establish existence across the whole parameter space, but the paper notes that behavior may differ in restricted parameter sets.Regularizers are given as an example of a restriction.Source: §5 · p. 9

A1 NOTATION

• For integers a ≤ b, [a,b] denotes the integers in that range; [b] abbreviates [1,b], and [v]_i and [v]_[i] denote a vector entry and its first i components.The notation 1_d and 0_d denotes all-ones and all-zeros column vectors, respectively.Source: A1 NOTATION · p. 12
• For matrices, [A]_{i,j} denotes an entry and [A]_{·,j} a column; σ_max and σ_min are the extreme singular values, while row, col, rank, and the Frobenius norm denote standard matrix properties.The passage also defines null(A), leftnull(A), and tr(A) for square matrices.Source: A1 NOTATION · p. 12
• The matrix inner product is defined as ⟨A,B⟩ = tr(A^T B), equivalently tr(AB^T), and 0_{d×m} denotes the zero matrix..Source: A1 NOTATION · p. 12

A2 PROOF OF THEOREM 1, STEP 2, CASE 2

• When duplicate fitted values include incorrect predictions, at least one duplicate group contains two or more data points whose fitted values differ from their targets.The construction selects a duplicate value and perturbs the linear least-squares solution to break the tie among affected points.Source: A2 PROOF OF THEOREM 1, STEP 2, CASE 2 · p. 12
• If all fitted values are distinct, J = ∅ would imply that the linear model fits every target exactly, contradicting the assumption that linear models cannot perfectly fit Y.The proof also analyzes incorrect non-duplicate fitted values and tied duplicate values to identify the relevant indices for perturbation.Source: A2 PROOF OF THEOREM 1, STEP 2, CASE 2 · p. 12
• The perturbation uses a scaled input vector chosen from the relevant indices, with its scale bounded using the minimum gap between distinct fitted values and the largest input norm.This keeps the order of distinct fitted values unchanged while changing the ordering within the selected tied group.Source: A2 PROOF OF THEOREM 1, STEP 2, CASE 2 · p. 13
• The proof adjusts network parameters so that the resulting squared-error risk is strictly smaller than at the candidate local minimum for sufficiently small α.The loss expression is evaluated using the perturbation and the least-squares residual relation.Source: A2 PROOF OF THEOREM 1, STEP 2, CASE 2 · p. 15
• The constructed point is therefore a spurious local minimum when linear models cannot perfectly fit the targets..Source: A2 PROOF OF THEOREM 1, STEP 2, CASE 2 · p. 15

A3.1 PROOF OF PART 1

• Under conditions (C2.1) and (C2.2), parameter values can be chosen to produce output [0 0 1] and perfectly fit Y..Source: A3.1 PROOF OF PART 1 · p. 16

A3.2 PROOF OF PART 2

• Under conditions (C2.3)–(C2.7), the proof constructs a local minimum whose network output matches the linear least-squares model.Small parameter perturbations are used to establish local minimality.Source: A3.2 PROOF OF PART 2 · p. 16
• If the Part 1 conditions also hold, the Part 2 local minimum is strictly inferior to the global one..Source: A3.2 PROOF OF PART 2 · p. 16

A4 PROOF OF LEMMA A.3

• The empirical risk sums contributions from three training examples, and Taylor expansion with algebraic manipulation is used to derive equation (A.7).The risk expression includes two displayed squared terms for examples and is described as having three terms overall.Source: A4 PROOF OF LEMMA A.3 · p. 17
• The auxiliary polynomial p_n has terms of degree exactly n − 2, with p_2(a, b) = 1.The lemma’s proof is verified by expanding both sides; its remaining algebra is omitted.Source: A4 PROOF OF LEMMA A.3 · p. 18
• A second expansion identity factors terms using (a − b)^2, (c − d)^2, and their cross product, with specified polynomial degrees.The q and r polynomials have degree n1 + n2 − 2; for n1 = n2 = 1, q1,1 = 0 and r1,1 = 1.Source: A4 PROOF OF LEMMA A.3 · p. 18
• The cross-term analysis splits t into t1 and t2, with t1 collecting constant and first-order perturbation terms.The proof uses Lemmas A.4 and A.5 to simplify the cross and squared terms.Source: A4 PROOF OF LEMMA A.3 · p. 18
• Derivative bounds ensure the Taylor-series summation converges for sufficiently small perturbations, while higher-degree polynomial terms diminish as perturbations shrink.The proof assumes |h^(n)(v1)| ≤ c^n n! and notes that terms in p_n for n ≥ 3 have degree at least one.Source: A4 PROOF OF LEMMA A.3 · pp. 19–20

2. In a similar way,

• Substituting equations (A.10), (A.11), and (A.17) into (A.9) gives equation (A.7).The passage identifies (A.7) as the proof’s original target.Source: §2 · p. 21

A5 PROOF OF COROLLARY 3

• The proof presents real-number choices for the listed activation functions to satisfy assumptions (C2.1)–(C2.7).The functions listed are sigmoid, tanh, arctan, quadratic, ELU, and SELU.Source: A5 PROOF OF COROLLARY 3 · p. 22

A5.1 SIGMOID

• For sigmoid, the proof gives choices for assumptions (C2.1)–(C2.2) and (C2.3)–(C2.7), citing real analyticity for (C2.4)–(C2.5).The cited real-analyticity reference is Krantz & Parks (2002).Source: A5.1 SIGMOID · p. 22

A5.2 TANH

• For tanh, the proof gives choices for the two assumption groups and attributes (C2.4)–(C2.5) to real analyticity.Source: A5.2 TANH · p. 22

A5.3 ARCTAN

• For arctan, the proof gives choices for both assumption groups and states that real analyticity supports (C2.4)–(C2.5).Source: A5.3 ARCTAN · p. 23

A5.4 QUADRATIC

• For the quadratic activation, the proof gives choices for both assumption groups and states that real analyticity supports (C2.4)–(C2.5).Source: A5.4 QUADRATIC · p. 23

A5.5 ELU AND SELU

• For ELU and SELU, the proof specifies parameterized choices for the assumption groups and states that h is real analytic at v1 and v2.The passage distinguishes ELU by λ = 1 and SELU by λ > 1, with α > 0.Source: A5.5 ELU AND SELU · p. 23

A6 PROOF OF THEOREM 2 FOR “RELU-LIKE” ACTIVATION FUNCTIONS.

• The theorem’s statements are proved for the piecewise linear nonnegative homogeneous activation family with s+ > 0, s− ≥ 0, and s+ ≠ s−.Source: A6 PROOF OF THEOREM 2 FOR “RELU-LIKE”… · p. 23

A6.1 PROOF OF PART 1

• When s− > 0, the assumptions (C2.1)–(C2.2) are satisfied by the stated choices, and the remaining proof follows Theorem 2.1’s Appendix A3 argument.Source: A6.1 PROOF OF PART 1 · p. 24

A6.2 PROOF OF PART 2

• For part 2, the proof computes the network output at a proposed parameter setting and tests whether small parameter perturbations keep the risk at least as large.The perturbed parameters include changes to weights and biases, all stipulated to be sufficiently small.Source: A6.2 PROOF OF PART 2 · p. 24

• The proof introduces partial derivatives computable by straightforward matrix calculus for all j ∈ [H + 1].Source: A7 PROOF OF THEOREM 4 · p. 25

A7.1 PROOF OF PART 1, IF dy ≥dx

• When nested null spaces differ, endpoint perturbations create an ascent direction; when they coincide, the proof locates the first change and chooses a small parameter to keep a matrix product nonzero.The nonzero product provides the direction used to increase the loss in the equal-space case.Source: A7.1 PROOF OF PART 1, IF dy ≥dx · pp. 25, 26, 28
• For every ε > 0, perturbations produce loss values both above and below the critical point, so it is neither a local minimum nor a local maximum.The proof uses differentiability to ensure the constructed ascent and descent directions yield the required loss inequalities for sufficiently small steps.Source: A7.1 PROOF OF PART 1, IF dy ≥dx · pp. 26, 29
• The dual construction uses nested left-null spaces: it perturbs endpoints when the spaces differ, or identifies the first differing layer when they coincide.Rank deficiency supplies nontrivial left-null spaces for the construction.Source: A7.1 PROOF OF PART 1, IF dy ≥dx · pp. 28–30
• When d_y ≥ d_x, a sufficiently small perturbation yields nonzero product change and opposing ascent and descent directions for the reduced loss.The argument selects a nonzero matrix entry and scales the perturbation to keep it nonzero, then applies differentiability to the resulting perturbations.Source: A7.1 PROOF OF PART 1, IF dy ≥dx · p. 31

A7.3 PROOF OF PART 2(A)

• A local minimum of the end-to-end matrix loss with zero gradient implies a local minimum of the deep-network loss.The proof bounds the change in the product of perturbed factors and uses the end-to-end loss’s local-minimum neighborhood; the local-maximum case is similar.Source: A7.3 PROOF OF PART 2(A) · pp. 31–32

A7.4 PROOF OF PART 2(B)

• With d_j ≥ min{d_x, d_y}, global minima of the deep-network loss correspond exactly to global minima of the end-to-end matrix loss.The proof constructs a factorization for any matrix R by placing R in an end layer and using identity entries in the other layers; the global-maximum case follows similarly.Source: A7.4 PROOF OF PART 2(B) · p. 32

A7.5 PROOF OF PART 3 AND 3(A)

• If a factor matrix product has a local minimum, full row rank above and full column rank below a layer imply the end-to-end matrix loss is also locally minimized.The proof uses a nearby-matrix factorization that perturbs only the intermediate layer, with perturbation size controlled by the two minimum singular values; the local-maximum case is analogous.Source: A7.5 PROOF OF PART 3 AND 3(A) · p. 33