On the Benefit of Width for Neural Networks: Disappearance of Bad Basins

1 Introduction

• The paper targets the unresolved benefit of width: optimization, rather than representation alone, may explain why narrow networks perform worse despite having good global optima.Prior ultra-wide analyses generally require widths far beyond practice and do not directly compare wide with narrow networks.Source: §1 · pp. 1–2

1.1 Main Contributions

• Weakly global functions have no sub-optimal set-wise strict local minima, excluding bounded spurious regions surrounded by barriers while permitting flat local-minimum regions.The paper uses this geometric property as its notion of having no bad basin.Source: §1.1 · pp. 2–3
• For fully connected networks with at least N neurons in the last hidden layer, any continuous activation yields a weakly global loss function, with the result obtained through Property PT.Property PT requires that every point can be perturbed toward a strictly decreasing path to a global minimum.Source: §1.1 · p. 3
• A related extension gives weakly global empirical loss when any one layer has at least N neurons, under additional structural and activation assumptions.This broadens the positive result beyond requiring the last hidden layer to be wide.Source: §1.1 · p. 3
• For a large class of activations, some one-hidden-layer networks with fewer than N neurons have bad strict local minima, establishing a narrow-to-wide phase transition in basin behavior.The paper contrasts this negative result with the absence of bad basins in the wide setting.Source: §1.1 · pp. 2–3

Practical motivation and implication

• The paper suggests that small-network training difficulty is at least partly due to bad basins, whereas wide networks do not suffer from them in the studied setting.Empirical barriers between solutions from different training methods are cited as evidence that basins can occur in small networks.Source: §2 · p. 4

Theoretical impact

• The paper’s landscape result for overparameterized deep networks can support analyses of other neural-network problems, as illustrated by combining it with function-space results for GANs.Generalization-error work is described as orthogonal to optimization-landscape analysis.Source: §2 · pp. 4, 6

Results on shallow networks

• Unlike prior shallow-network studies, the work differentiates narrow and wide networks while allowing arbitrary depth and broad activation coverage.Earlier shallow analyses often imposed strong assumptions on data or activations.Source: §2 · pp. 4–5

Results on deep linear networks

• Prior deep-linear results show no sub-optimal local minima but do not reveal a width effect because all considered linear networks are treated as equally good.The paper instead studies nonlinear neural networks used in practice.Source: §2 · p. 4

Algorithmic analysis

• Algorithmic convergence analyses can prove stronger rates but typically require widths such as O(N^2), exceeding practical widths and not comparing narrow with wide networks.Some results reduce width under separability and large-margin conditions, but difficult datasets may still require very large or infinite parameter counts.Source: §2 · pp. 4–5

3.1 Positive Results

• Property PT requires an arbitrarily small perturbation from any non-global point after which a strictly decreasing path reaches the global infimum, and it implies weak globality.Weak globality excludes sub-optimal basins while allowing some non-strict local minima or unbounded sub-optimal infima.Source: §3.1 · pp. 7–8
• The positive theorem requires nonzero distinct inputs, a loss convex in predictions, and continuous activations, while leaving the widths of other hidden layers unrestricted.The assumptions are described as mild; the wide-layer condition is that the relevant layer has at least as many neurons as training samples.Source: §3.1 · p. 7
• For fully connected networks with at least N neurons in the last hidden layer, continuous activations yield no sub-optimal set-wise strict local minima.This is Theorem 2, obtained by establishing Property PT and using its implication that the loss is weakly global.Source: §3.1 · pp. 8–9
• The positive result extends beyond the last hidden layer: a sufficiently wide intermediate layer can also eliminate sub-optimal basins when additional pyramid-structure and activation assumptions hold.Theorem 3 retains weak globality after adding a pyramid architecture after the wide layer.Source: §3.1 · pp. 9–10

3.2 Negative Results

• For widths below N, a one-hidden-layer network can be constructed with a sub-optimal basin for generic input data, establishing the negative side of the phase transition.Theorem 4 uses any m < N and suitable outputs; Theorem 6 gives a single-neuron result under differentiability and nonzero derivatives at zero.Source: §3.2 · pp. 10–11
• The transition is activation-dependent: piecewise-linear activations also admit bad basins under specified data conditions, whereas positive homogeneous activations have none at any width.The paper defines transition width as the smallest width eliminating all sub-optimal basins for any depth and generic input data.Source: §3.2 · p. 11, Table 1 · p. 11

4.1 First Idea: Property PT Holds for Many Activations

• For wide one-hidden-layer networks, full-rank hidden representations enable strictly decreasing paths to global minima, preventing bad local minima.When the post-activation matrix has rank N, the output-layer problem is convex and can attain zero loss; perturbations are used to reach this condition.Source: §4.1 · p. 12

4.2 Extending to Any Continuous Activation

• Property PT is stronger than weak globality, but it is not preserved by compact approximation; weak globality is the property used in the limiting argument.A sequence with Property PT can converge to a function containing a spurious valley, so the proof relies on closedness of weak globality instead.Source: §4.1 · p. 12

4.1 First Idea: Property PT Holds for Many Activations

• Full-rank reachability requires sufficient nonlinearity: analytic activations with N non-vanishing derivatives at zero in an arithmetic order satisfy Property PT, whereas monomial activations do not.For monomial activations, the hidden output is always rank-deficient, so no weight matrix can produce full column rank.Source: §4.1 · p. 13

4.2 Extending to Any Continuous Activation

• The proof extends from special analytic activations to every continuous activation by density and closedness of the weakly global property.The three steps are: establish Property PT for analytic functions, approximate continuous functions uniformly by them, and preserve weak globality in the limit.Source: §4.2 · p. 13, Figure 2 · p. 14

5 Formal Proof of Positive Results

• The section’s proof organization assigns Step 1 to Theorem 1, while Steps 2 and 3 establish Theorem 2.This passage identifies the role of the present proof section within the paper’s three-step argument.Source: §5 · p. 14

5.1 Proof of Theorem 1 (Step 1)

• Analytic activations provide the needed separation: their relevant matrices are nonsingular for distinct nonzero inputs, while equality sets of distinct analytic responses have measure zero.The proof invokes the zero-set theorem for real analytic functions [82] and derives the full-rank property from a Vandermonde construction under Assumption 2.Source: §5.1 · p. 15
• The induction proving generic rank combines nonzero, distinct activations with analytic determinant arguments, showing that rank-deficient or duplicate/zero-column outputs form measure-zero sets at every layer.The base case uses Lemmas 2–4 and a Vandermonde-matrix contradiction; the induction then transfers the measure-zero property through successive hidden layers.Source: §5.1 · pp. 16, 18
• For networks with d_H ≥ N, the last hidden-layer output T_H has full column rank for almost all hidden-layer weights under Assumptions 1 and 2.The exceptional set where rank(T_H) < N is shown to have measure zero, and the result is stronger because the hidden-layer output also generically satisfies Assumption A1.Source: §5.1 · pp. 16, 18
• A convex loss admits a continuous path with strictly decreasing values from any non-global point to its global infimum.Lemma 5 constructs the path by joining a decreasing sequence with line segments while preserving strict decrease through convexity and continuity.Source: §5.1 · pp. 18–19
• After perturbing arbitrarily close to any weights, one can obtain full-rank T_H and then optimize the final-layer weights along a strictly decreasing path.With the first H layers fixed, the empirical loss is convex in W_{H+1}; full column rank lets W_{H+1} realize any output matrix.Source: §5.1 · pp. 19–20
• Thus, the constructed path decreases the empirical loss toward inf_W E(W), establishing the optimization-landscape claim needed for Theorem 1.The argument combines generic full rank with final-layer convexity to connect arbitrarily nearby weights to the global infimum through strict descent.Source: §5.1 · p. 20
• A contradiction using boundary-value separation and strictly decreasing paths proves that the loss has no sub-optimal set-wise strict local minima.The argument starts from a hypothetical compact sub-optimal minimum, then shows any decreasing path to the global infimum must cross a boundary whose loss is strictly higher.Source: §5.1 · p. 20

5.2 Proof of Theorem 2 (Step 2 and Step 3)

• Lemma 6 shows that functions satisfying Assumption 2 are uniformly dense in the space of continuous functions.The proof combines density in analytic functions with density of analytic functions in continuous functions, using a sequence construction.Source: §5.2 · pp. 21–22
• Uniform convergence of inner functions and compact convergence of outer functions imply uniform convergence of their compositions on compact domains.This composition result enables approximation to propagate through the successive layers of a neural network.Source: §5.2 · pp. 22–23
• Proposition 3 establishes that compact limits of weakly global functions remain weakly global.The proof constructs a strict local minimum for an approximating function from any assumed sub-optimal strict local minimum of the limit, yielding a contradiction.Source: §5.2 · pp. 23–24
• Property PT is not preserved under compact convergence, unlike weak globality.The supplied counterexample converges compactly to a function containing an unbounded spurious valley that violates Property PT.Source: §5.2 · p. 23
• Approximating each continuous activation uniformly produces networks whose hidden-layer outputs and empirical losses converge compactly to those of the original network.The hidden-layer convergence is proved inductively, and arbitrary compact parameter subsets establish compact convergence of the empirical losses.Source: §5.2 · pp. 24–25
• Because every approximating network has a weakly global loss, compact convergence and Proposition 3 imply that the original continuous-activation loss is weakly global.This completes the proof of Theorem 2 for arbitrary continuous activation functions.Source: §5.2 · pp. 23–25

6.1 Proof of Negative Results

• Narrow one-hidden-layer networks satisfying Proposition 4’s conditions can have a sub-optimal strict local minimum, and hence a bad basin.The result assumes m < N and a twice continuously differentiable activation, with specified linear-independence conditions; sufficiently large M makes the constructed minimum sub-optimal.Source: §6.1 · pp. 26, 28
• The proof constructs the minimum by choosing an orthogonal vector a, setting output weights from second-derivative features, and scaling by a sufficiently large positive M.The construction first establishes strict local minimality for every M > 0, then compares against another parameter point to show sub-optimality for sufficiently large M.Source: §6.1 · pp. 26, 28
• Theorem 4 follows by designing a twice continuously differentiable activation and data labels so Proposition 4’s conditions hold, producing a bad basin.Distinct inner products permit interpolation of activation values and derivatives, after which the hidden-feature span is chosen below dimension N.Source: §6.1 · p. 28
• For positive-homogeneous activations, empirical loss has no set-wise strict local minimum because scaling symmetries generate constant-loss paths that contradict compactness.If output weights vanish, hidden weights can vary arbitrarily; otherwise simultaneous inverse scaling of output and hidden weights makes the output weights unbounded while preserving loss.Source: §6.1 · pp. 28–29
• A one-hidden-neuron network also admits a sub-optimal basin under the Proposition 4 construction, using a full-row-rank Vandermonde-related matrix and a nearby auxiliary feature.The proof sets w = 0, verifies the rank and independence conditions, and then invokes Proposition 4.Source: §6.1 · p. 29
• Piecewise-linear activations flat at the origin admit explicit sub-optimal strict local minima for positive-measure ordered input sets satisfying x1/xN < (t0 + δ)/t0.The construction assigns weights wi = u2i+1 and vi = 1, yielding hidden-output patterns that support local minimality; a large-M comparison establishes sub-optimality.Source: §6.1 · pp. 29, 30, 32

6.2 Computational Construction of Sub-Optimal Basins

• The proof’s existential construction extends computationally to a specified network and dataset, rather than only asserting that some bad basin exists.For Swish, the authors use the Proposition 4 procedure on a one-hidden-layer single-neuron network with x = (0.1, 2, 3)^T and w = v = 1.Source: §6.2 · p. 33
• For the Swish example, a feasible vector a ≈ (1, 0.0294, −0.0365)^T yields labels y ≈ (−99.9475, −1.1766, 6.5060)^T after scaling by 100.These values instantiate the computational construction for the chosen three-sample network.Source: §6.2 · p. 33
• A constructed neural network has a sub-optimal strict local minimum at (v, w) = (1, 1), visualized in Figure 3.This provides the computational construction of a bad basin.Source: §6.2 · p. 33
• Theorem 6 and Example 2 choose specific output data y to ensure bad basins for given activation functions.These constructions do not establish the phenomenon for arbitrary fixed activation functions and output data.Source: §6.2 · p. 33
• Whether bad basins exist for general narrow networks with fixed activation functions and output data remains open.[84] suggests that spurious valleys may be virtually unavoidable for certain deep networks when mild activation assumptions hold and some vectors are unrealizable.Source: §6.2 · p. 33

• If the last hidden layer has at least as many neurons as samples, any continuous activation yields a weakly global loss with no sub-optimal basins.Here, weakly global means the loss has no set-wise strict local minima.Source: §7 · pp. 33, 35
• For most analytic activations, every point can be slightly perturbed to admit a strictly decreasing path toward the global infimum.Source: §7 · p. 35
• The results construct sub-optimal strict local minima in narrow one-hidden-layer networks, establishing a narrow-to-wide phase transition for a broad activation class.Source: §7 · p. 35
• Large width eliminates bad basins but does not necessarily produce a perfect landscape for deep neural networks.Source: §7 · p. 35

• Pruning evidence suggests small networks can represent the data well, but optimization from random initialization may fail to find their good global optima.Source: A More Discussions · p. 41
• Small models matter for mobile and IoT devices and for researchers constrained by the substantial computing resources required by large models.Source: A More Discussions · p. 42
• Training small networks remains difficult, and the paper presents theoretical understanding as an important first step rather than an immediate training method.Source: A More Discussions · p. 42
• Eliminating bad basins addresses one major optimization concern, although it does not resolve convergence to local minima or other training issues.Source: A More Discussions · p. 42
• The authors recommend further convergence analysis for wide networks but caution against currently pursuing global-convergence proofs for narrow networks.Source: A More Discussions · p. 43
• The possible existence of bad basins suggests a target for methods that eliminate, avoid, or escape them, while detailed basin geometry remains future work.Source: A More Discussions · p. 43

• Theorem 3 extends the argument to a network with one wide hidden layer, under additional structural and activation assumptions.Its proof is an extension of Theorem 2 and uses extra techniques.Source: B Formal Proof of Theorem 3 · p. 43
• Continuous monotone activations are approximated on compact sets by continuous strictly monotone, onto functions satisfying the stronger assumptions.Source: B Formal Proof of Theorem 3 · pp. 43, 47, 48
• For the specific activation class, the proof perturbs any initial weight to a dense full-rank set and constructs a continuous path whose loss strictly decreases toward the global infimum.Source: B Formal Proof of Theorem 3 · p. 44
• The path changes only the weights entering the layer after the wide layer, while continuity and inverse or rank conditions preserve the required hidden-layer outputs.Source: B Formal Proof of Theorem 3 · pp. 44–45
• The endpoint of the constructed path is a global minimum, and the loss cannot contain a sub-optimal set-wise strict local minimum; contradiction proves weak globality.Source: B Formal Proof of Theorem 3 · pp. 45–47
• Replacing each activation by its approximant yields weakly global losses, and compact convergence of these losses transfers weak globality to the original network.Source: B Formal Proof of Theorem 3 · pp. 44, 48, 49