Source-linked AI summary
Depth Creates No Bad Local Minima
Haihao Lu, Kenji Kawaguchi
TL;DR
The paper asks whether depth alone creates bad local minima despite making the loss surface non-convex. It proves that local minima of deep linear models correspond to local minima of shallow rank-constrained models, yielding global minima under full-row-rank assumptions and broader loss conditions. The analysis also extends to a deep linear matrix-completion parameterization, whose local minima are global with high probability.
Problem
Depth creates non-convex loss surfaces, but it is unclear whether depth alone creates bad local minima during deep-model training.
Source: §1 · pp. 1–2Method
The paper reduces local-minimum analysis for deep linear parameterizations to an equivalent rank-constrained shallow model and develops a simpler proof.
Source: §1 · p. 2, §3.1 · p. 5Results
If X and Y have full row rank, all local minima of feedforward deep linear neural networks with square loss are global minima.
Source: §2 · p. 3Takeaways & Limitations
The reduction extends beyond square loss whenever the loss satisfies Theorem 3.2 and applies to deep linear matrix completion, where local minima are global with high probability.
Source: §2 · p. 2, §4 · p. 9The stated generalization beyond square loss requires the loss function to satisfy Theorem 3.2, and the main theorem assumes full row rank for X and Y.
Source: §2 · pp. 2–3
Abstract
from arXiv · showhide
In deep learning, \textit{depth}, as well as \textit{nonlinearity}, create non-convex loss surfaces. Then, does depth alone create bad local minima? In this paper, we prove that without nonlinearity, depth alone does not create bad local minima, although it induces non-convex loss surface. Using this insight, we greatly simplify a recently proposed proof to show that all of the local minima of feedforward deep linear neural networks are global minima. Our theoretical results generalize previous results with fewer assumptions, and this analysis provides a method to show similar results beyond square loss in deep linear models.
1 Introduction
Deep learning’s expressive model classes can generalize well, but training remains difficult because deep models produce high-dimensional non-convex optimization problems. This paper focuses on whether depth alone creates bad local minima and introduces a direct reduction from deep linear models to shallow ones.
1 Introduction
- Deep learning’s practical success is associated with expressive model classes that learn features from data while maintaining generalization properties.The introduction contrasts this with overly flexible shallow networks and overly powerful kernel methods.Source: §1 · p. 1
- Training deep models is difficult to characterize because non-convexity combines with high-dimensional weight parameters, despite practical evidence that deep models can be trained efficiently.Worst-case analysis shows general neural-network training is NP-hard, but this does not tightly capture observed practice.Source: §1 · p. 1
- Prior work studied the training of deep models through theoretical and practical analyses of their non-convex optimization landscapes.The cited literature includes analyses of deep linear and nonlinear networks, saddle points, and optimization geometry.Source: §1 · pp. 1–2
- Depth and nonlinearity both induce non-convexity; depth alone creates highly non-convex optimization problems through weight-space symmetries.These symmetries yield distinct parameter settings with the same function and loss, producing many global optima and non-convex epigraphs and sublevel sets.Source: §1 · p. 2
- The paper directly proves that every local minimum of a deep linear model corresponds to a local minimum of a shallow model.This reduction supports a simpler proof of the no-bad-local-minima result and extends under the loss conditions of Theorem 3.2.Source: §1 · p. 2
2 Main Result
The main result analyzes deep linear networks through an equivalent rank-constrained shallow model. Under full-row-rank assumptions, local minima are inherited from the shallow problem and are therefore global for square loss, with broader applicability under Theorem 3.2.
2 Main Result
- The analysis applies beyond Frobenius loss whenever the loss function satisfies Theorem 3.2.Under that condition, local minima of the deep model correspond to local minima of the shallow model.Source: §2 · p. 2
- Every local minimum of the deep parameterization corresponds to a local minimum of the rank-constrained shallow model.The deep product has rank at most the smallest layer width, while the shallow problem has the same global minimum value; deep parameterization remains non-convex even when the shallow problem is convex.Source: §2 · p. 2
- The rank-constrained shallow model has no bad local minima when X has full row rank.This theorem supplies the second step needed to transfer the global-minimum property back to the deep model.Source: §2 · p. 3
- Under full row rank for X and Y, all local minima of the deep linear square-loss problem are global minima.This is Theorem 2.3 and follows by combining the reduction from deep to shallow local minima with the shallow model’s global-minimum property.Source: §2 · pp. 2–3
- Theorem 2.3 generalizes Kawaguchi (2016) by removing the assumption that Y X^T (XX^T)^−1 X Y^T has distinct eigenvalues.The earlier result also used stronger assumptions for related deep-network conclusions.Source: §2 · p. 3
3 Proof
This section develops perturbation, rank-preserving, and projection-matrix arguments for deep linear factorizations. These proofs characterize local minima by ruling out feasible descent directions and establish that every analyzed local minimum is global.
3.1 Proof of Theorem 2.1
- Under the rank condition, perturbations of a matrix product can be realized by perturbing each factor, via SVD continuity and induction on depth.The proof uses singular-value and singular-space perturbation results, with a two-factor base case and an inductive decomposition for deeper products.Source: §3.1 · pp. 3–5
- Every local minimum can be replaced by an equal-valued nearby local minimum whose factors are full rank and whose product satisfies rank(WH · · · W1) = dp.The construction perturbs individual factors through convex least-squares subproblems, then applies the product-perturbation result to obtain the rank-constrained representative.Source: §3.1 · pp. 5–6
3.2 Proof of Theorem 2.2
- For Theorem 2.2, rotational invariance reduces the problem to identity inputs and diagonal targets, where local minima become block-diagonal symmetric matrices built from eigenspace projection matrices.The proof then shows these projections select eigenspaces associated with the largest possible eigenvalues, yielding the same function value as global minima.Source: §3.1 · p. 7, §3.2 · p. 8
- The proof excludes rank-one perturbations and eigenvector rotations that would preserve rank while monotonically decreasing H(T), contradicting local minimality.At a local minimum, adding a rank-one matrix corresponding to a positive eigenvalue or constructing the specified rotation would provide a descent direction.Source: §3.2 · pp. 8–9
- Every local minimum T* is a global minimum.The argument uses the block-diagonal structure of T*, reduces to square matrices without loss of generality, and derives a contradiction whenever a descent direction exists.Source: §3.2 · pp. 8–9
3.3 Proof of Theorem 2.3
- Theorem 2.3 follows from Theorems 2.1 and 2.2.The supplied proof concludes the theorem by invoking those two preceding results.Source: §3.3 · p. 9
4 Conclusion
The analysis shows that depth creates a non-convex loss surface without introducing bad local minima, and extends this conclusion beyond square loss and to deep matrix-completion parameterizations.
4 Conclusion
- Depth creates no new bad local minima: all local minima of feedforward deep linear neural networks are global minima.This result follows despite the non-convexity induced by depth.Source: §4 · p. 9
- For losses satisfying Theorem 3.2, every local minimum of the deep parameterization corresponds to a local minimum of the rank-constrained shallow problem.The result is not restricted to least-squares loss.Source: §4 · p. 9
- The analysis directly extends asymmetric matrix-completion results to deep linear parameterizations, with every local minimum global with high probability.The extension applies to the observed-entry objective h(W).Source: §4 · p. 9