Depth creates no more spurious local minima

1.1 Related work

• Prior work established special cases, including two-layer quadratic-loss networks, deep networks [10], and no-bottleneck convex-loss networks.The present work targets bottlenecked networks excluded by.Source: §1 · p. 2, §1.1 · p. 3

1 Introduction

• For any convex differentiable loss, a deep linear network has no spurious local minima iff its corresponding two-layer network has none.The reduction is instance-specific because the loss function depends on both the data and the loss.Source: §1 · p. 2
• Any spurious local minimum must have full rank when the network is broken at its bottleneck.In the two-layer case, this excludes rank-deficient spurious minima and simplifies their analysis.Source: §1 · p. 2
• For quadratic loss, the result gives an unconditional proof that deep linear networks have no spurious local minima.This removes the assumptions used in earlier results [10] via.Source: §1 · p. 2
• The same reduction extends to multi-tower linear networks: absence of spurious minima is equivalent to the corresponding bottlenecked two-layer network, and holds automatically when b ≥ m, n.A multi-tower network is the sum of multiple deep linear towers.Source: §1 · p. 3
• The proof splits a bottlenecked network into two parameterized super-layers and uses a rank-one perturbation to reduce critical points to the two-layer case.The perturbation applies unless the solution is already globally optimal.Source: §1 · p. 3

Definitions

• A deep linear network maps Φ(x) = M_k · · · M_1x, with depth k and narrowest width d = min_i d_i.Source: §2 · p. 4
• A bottleneck occurs when the narrowest width is strictly smaller than both input and output dimensions.Source: §2 · p. 4

Empirical loss

• Training losses can be written as L(M_1, ..., M_k) = f(M_k · · · M_1), where convex differentiable example losses induce a convex differentiable f.Source: §2 · p. 4

Local minima

• A local minimum is defined by minimal loss within an open Frobenius-norm neighborhood, and differentiability makes every local minimum a critical point.Source: §2 · p. 5

Prior theorem

• For convex differentiable f, if the network has no bottleneck, every local minimum is a global minimum.Source: §2 · p. 5

Full-rank lemma

• At an interior bottleneck, the main technical lemma states that a local minimum has either f′(AB) = 0 or both bottleneck factors A and B have rank d.The proof treats the no-bottleneck case separately using the recalled theorem.Source: §3 · pp. 5–6

Theorem 1

• The theorem follows because full-rank factors allow every sufficiently small perturbation of the two super-layers to be realized by perturbing the original end layers.A norm bound transfers local minimality between the deep and two-layer parameterizations.Source: §3 · pp. 5–6
• Every spurious local minimum of a deep linear network maps, by splitting at the bottleneck, to a spurious local minimum of the corresponding two-layer network.The reverse direction follows by factoring arbitrary two-layer matrices through the bottleneck.Source: §3 · pp. 5–6

Perturbation argument

• Assuming rank deficiency, carefully chosen low-rank perturbations preserve the network output while forcing a row of the perturbed factor outside the relevant subspace, contradicting local minimality.The construction proceeds inductively across the layers and yields the contradiction that establishes full rank.Source: §3 · pp. 6–7

Multi-tower extension

• The same proof pattern handles multi-tower networks by splitting each tower at its bottleneck and concatenating the resulting factors into a single two-layer representation.If the combined bottleneck width is at least the input or output dimension, the no-bottleneck theorem gives global optimality.Source: §3 · p. 8

• The reduction applies to deep linear networks with depth at least three and also extends to multi-tower linear networks.The analysis reduces spurious-local-minimum questions to the two-layer case.Source: §4 · p. 8
• A non-degeneracy property of local minima supports the reduction and removes the rank-deficient case from two-layer analysis.Source: §4 · p. 8
• The proof uses a novel perturbation argument without requiring heavy mathematical machinery.Source: §4 · p. 8
• Determining when spurious local minima are absent beyond quadratic loss remains an open question.Source: §4 · p. 8
• Whether a similar phenomenon holds for nonlinear networks also remains open.Source: §4 · p. 8