Deep Learning without Poor Local Minima

Kenji Kawaguchi

Source-linked AI summary

Deep Learning without Poor Local Minima

Kenji Kawaguchi

arXiv:1605.07110v3May 23, 2016stat.MLcs.LGmath.OC

TL;DR

The paper studies whether deep-network optimization is tractable despite non-convexity and incomplete prior theory. It proves landscape properties for deep linear networks and partially extends them to deep nonlinear networks under weaker assumptions, showing global local minima but also bad saddles in deeper models.

Problem
Deep models require non-convex optimization, while prior work left key conjectures and an open problem about their loss landscapes unresolved.
Method
The paper analytically studies squared-loss deep linear networks of arbitrary depth and width, then reduces deep nonlinear networks to a deep linear model under independence assumptions.
Results
Every local minimum is global and every non-global critical point is a saddle; for deeper than three-layer networks, some saddles have no negative Hessian eigenvalue, while three-layer saddles do not.
Takeaways & Limitations
The results advance optimization theory for deep learning while indicating that deeper models can contain bad saddle points and that training theory remains separated from practice.
Takeaways & Limitations
The nonlinear theory does not yet directly apply to practical settings and still relies on assumptions inherited from previous work.

Abstract

from arXiv · show

In this paper, we prove a conjecture published in 1989 and also partially address an open problem announced at the Conference on Learning Theory (COLT) 2015. With no unrealistic assumption, we first prove the following statements for the squared loss function of deep linear neural networks with any depth and any widths: 1) the function is non-convex and non-concave, 2) every local minimum is a global minimum, 3) every critical point that is not a global minimum is a saddle point, and 4) there exist "bad" saddle points (where the Hessian has no negative eigenvalue) for the deeper networks (with more than three layers), whereas there is no bad saddle point for the shallow networks (with three layers). Moreover, for deep nonlinear neural networks, we prove the same four statements via a reduction to a deep linear model under the independence assumption adopted from recent work. As a result, we present an instance, for which we can answer the following question: how difficult is it to directly train a deep model in theory? It is more difficult than the classical machine learning models (because of the non-convexity), but not too difficult (because of the nonexistence of poor local minima). Furthermore, the mathematically proven existence of bad saddle points for deeper models would suggest a possible open problem. We note that even though we have advanced the theoretical foundations of deep learning and non-convex optimization, there is still a gap between theory and practice.

1 Introduction

The paper studies whether deep-learning optimization can be theoretically tractable despite non-convexity, proving broader results for deep linear networks and addressing an open problem for deep nonlinear networks.

Motivation: Deep learning has achieved practical success, but training deep models typically requires non-convex optimization.The difficulty is tied to the general challenge of finding global minima for non-convex functions.
Contributions: The paper proves a conjecture for deep linear networks and addresses an open problem for deep nonlinear networks.The authors state that both results are more general and tighter than earlier statements.
Contributions: The results advance theoretical foundations for deep learning and non-convex optimization.

2 Deep linear neural networks

For deep linear networks, the paper establishes a general loss-surface theory: non-convexity coexists with global local minima, while saddle-point behavior depends on depth.

Background: Deep linear networks remain theoretically relevant because their loss functions are non-convex even though their represented functions are linear in the inputs.
Main results: The paper proves that, under full-rank data and distinct-eigenvalue assumptions, the loss results hold for any depth, layer widths, and input-output dimensions.
Main results: The loss is non-convex and non-concave, every local minimum is global, and every non-global critical point is a saddle point.
Effect of depth: Three-layer networks have a negative Hessian eigenvalue at every saddle point, whereas deeper networks can have saddle points without any negative eigenvalue.
Generality: The theorem removes several restrictions used in prior work, including invertibility of XY^T, p < dx, p < dy, and dy = dx.
Optimization implications: The absence of poor local minima makes saddle points the main remaining tractability concern for direct optimization.

3 Deep nonlinear neural networks

The paper analyzes deep nonlinear networks by reducing their expected squared-loss function to a deep linear model under two independence-related assumptions. This yields a loss-surface characterization that rules out poor local minima under fewer assumptions than prior work.

Model: The analysis uses rectified-linear activations, with the final activation often taken to be the identity without invalidating the theoretical results.The network output is defined through layerwise nonlinear transformations and path activations.
Reduction: Under A1p-m and A5u-m with q = ρ^-1, the deep nonlinear loss reduces to the corresponding deep linear loss.The assumptions model activation indicators as identically distributed Bernoulli variables independent of inputs and parameters.
Results: The nonlinear model is non-convex and non-concave, every local minimum is global, and every non-global critical point is a saddle point.Its saddle points also inherit the properties established for the deep linear model.
Comparison with prior work: Compared with prior work, the result discards assumptions A2p, A3p, A4p, A6u, and A7p while giving the tighter conclusion that poor local minima do not exist.The analyzed model class is strictly more general than the earlier model class.

4 Proof Idea and Important lemmas

The proof develops critical-point and Hessian conditions for deep linear networks, then combines rank-based case analysis with arbitrarily small loss-preserving perturbations. These arguments establish the loss-surface properties and explain why deeper networks can have non-strict saddle points.

Critical-point conditions: The proof first derives necessary conditions for critical points and local minima using gradients and Hessian semidefiniteness.The critical-point condition is expressed layer by layer, while the Hessian is organized in block form using Kronecker products.
Rank-based analysis: Rank and range constraints force either sufficient network rank or zero residual-related products at critical points with semidefinite Hessians.These constraints are formalized through range inclusions and rank inequalities involving products of layer matrices.
Global-minimum proof: By case analysis, every point satisfying local-minimum conditions is shown to be a global minimum, including cases where the optimal map is an eigenvector-based projection.Arbitrarily small perturbations can increase intermediate ranks without changing the loss, enabling induction across layers.
Loss-surface conclusions: The Hessian is indefinite at uncountably many points, and every non-global critical point is a saddle rather than a local maximum.The no-local-maximum argument uses increasing directions or arbitrarily small loss-preserving perturbations.

5 Conclusion

The paper advances theory for deep linear and nonlinear networks, proving broad loss-surface results while acknowledging that the assumptions still leave a gap from theory to practice. It identifies activation mechanisms and architectures as relevant to training difficulty.

Contributions: For deep linear networks, the paper proves the conjecture and obtains more general, detailed statements than earlier work.The theory allows weaker assumptions and broader relationships among dimensions and layer widths.
Nonlinear networks: For deep nonlinear networks, the results use strictly weaker assumptions than prior work and characterize the loss surface through the deep-linear reduction.The paper discards most of the assumptions used in the earlier analysis.
Interpretation: The analysis suggests that bad local minima in deep nonlinear models arise only as an effect of adding nonlinear activations to corresponding deep linear models.The paper presents this as a theoretical fact derived from its understanding of deep linear models.
Limitations: The theory does not yet directly apply to practical settings, and future work must discard remaining assumptions to narrow the gap between theory and practice.The conclusion preserves the paper’s scope boundary rather than claiming a complete training guarantee.

A.5 Proof of Corollary 4.5

The proof of Corollary 4.5 converts Hessian range conditions into a rank inequality for products of layer matrices, with an alternative residual condition.

Proof mechanism: The proof applies the necessary range conditions to a principal Hessian submatrix and uses the Schur complement.These steps establish the relevant column-space inclusion before taking ranks.
Rank implication: A semidefinite-Hessian condition implies rank(WH+1 · · · Wk) ≥ rank(Wk−1 · · · W2), unless XrWH+1 · · · Wk+1 = 0.The argument uses range containment and the rank bound for matrix products.

Proof

The proofs analyze critical points through generalized inverses, range and projection identities, Schur complements, and Hessian conditions. These reductions constrain the relevant eigenspaces and characterize when a critical point can have a positive-semidefinite Hessian.

Proof: Range and projection identities reduce the analysis to the eigenspaces selected by the matrix C.The proof establishes R(C)=R(U_Īp) and represents the associated projection as U_ĪpU_Īp^T.
Proof: When Xr≠0, the selected index set Īp must correspond to the p largest eigenvalues.The Schur-complement condition yields the required eigenvalue inequalities.
Proof: A positive-semidefinite Hessian forces either Xr=0 or C(C^T C)^−C^T=U_ĪpU_Īp^T at a critical point.This is the summary condition obtained after the case analysis and Hessian reductions.
Proof: The proof uses generalized inverses of Kronecker products, without requiring the chosen generalized inverse to be unique.A tensor product of generalized inverses satisfies the generalized-inverse identity, and any such choice suffices for the necessary conditions.
Proof: The argument relies on necessary conditions for local minima, which are not sufficient by themselves to establish local minimality.The proof explicitly distinguishes necessary conditions from sufficient conditions.

B.1 Proof of Theorem 2.3 (ii)

The proof shows that every local minimum is global by analyzing Hessian conditions and reducing the relevant cases to convex linear regression or global-minimum expressions.

B.1 Proof of Theorem 2.3 (ii): Any point satisfying the local-minimum definition and its necessary conditions is shown, by case analysis, to be a global minimum.This is the central conclusion of the proof of Theorem 2.3(ii).
B.1 Proof of Theorem 2.3 (ii): When Xr=0, the corresponding linear model is convex, so the critical point achieves the global minimum.The deep model’s product can be represented by a linear model without hidden layers.
B.1 Proof of Theorem 2.3 (ii): When rank(W_H⋯W_2)=p and d_y≤p, a critical point with positive-semidefinite Hessian is a global minimum.The proof establishes this case directly from the Hessian condition.
B.1 Proof of Theorem 2.3 (ii): For rank(W_H⋯W_2)=p, the fitted product projects onto the subspace of the p largest eigenvectors after ordinary least-squares regression.The resulting expression is identified as a global minimum.
B.1 Proof of Theorem 2.3 (ii): When rank(W_H⋯W_2)<p, arbitrarily small loss-preserving perturbations can increase intermediate ranks until the previously analyzed global-minimum case applies.The induction constructs perturbations that raise rank without changing the loss.

B.2 Proof of Theorem 2.3 (i)

The proof establishes non-convexity and non-concavity by exhibiting critical-point configurations that fail the Hessian semidefiniteness condition.

B.2 Proof of Theorem 2.3 (i): The loss is non-convex and non-concave because an uncountable set of critical points violates the necessary Hessian semidefiniteness condition.The proof gives points with W_H+1=W_1=0 and arbitrary W_H as an example.

B.3 Proof of Theorem 2.3 (iii)

The proof shows that every critical point that is not global is a saddle point by ruling out local maxima and identifying strictly increasing directions near candidate maxima.

B.3 Proof of Theorem 2.3 (iii): If W_H+1⋯W_2≠0, the Hessian has a strictly positive direction with respect to W_1 at a critical point.Positive semidefiniteness follows from the Kronecker product of positive-semidefinite matrices, with XX^T full rank.
B.3 Proof of Theorem 2.3 (iii): If W_H+1⋯W_2=0, arbitrarily small loss-preserving perturbations can make this product nonzero.The proof constructs such perturbations inductively across the layers.
B.3 Proof of Theorem 2.3 (iii): The rank and range conditions used in the induction connect the products A_k with the range of C.This relationship drives the contradiction needed to construct the perturbations.
B.3 Proof of Theorem 2.3 (iii): At any candidate local maximum, these perturbations create a strictly increasing direction in an arbitrarily small neighborhood.Therefore, the loss has no local maximum at such a critical point.

B.4 Proof of Theorem 2.3 (iv)

When the intermediate product has full rank p, any critical point that is not globally optimal has a Hessian with a negative eigenvalue and is therefore a saddle point.

If rank(W_H · · · W_2) = p, a critical point with positive-semidefinite Hessian is a global minimum.
Because non-global critical points are not local minima, they are saddle points.
Under the same rank condition, any non-global critical point has a Hessian containing a negative eigenvalue.

C.1 Proof of Corollary 2.4

The proof constructs critical points with all hidden-layer matrices zero, shows they are not global minima, and establishes that their Hessian is the zero matrix. Thus, for networks deeper than three layers, these points are bad saddle points.

Shallow case: For H = 1, the theorem’s rank condition is automatically satisfied because the sole hidden-layer width equals the smallest hidden width p.This immediately yields the shallow-network corollary rather than requiring the deeper zero-matrix construction.
Construction: For H ≥ 2, setting W_H = ··· = W_1 = 0 produces an uncountable set of critical points while W_{H+1} can vary freely.The construction follows from the critical-point characterization and permits W_{H+1} ∈ R^{d_y×d_H}.
Nonoptimality: These critical points are not global minima because the loss admits a strictly lower value than the value attained when the residual is r = Y^T.The compared loss value is 1/2 tr(YY^T), under the stated nonzero-rank conditions.
Saddle classification: The non-global critical points are therefore saddle points by the theorem characterizing every non-global critical point as a saddle point.The argument combines the strict loss comparison with Theorem 2.3(ii) and (iii).
Hessian: At these points, every diagonal and off-diagonal Hessian element is zero, so the Hessian is a zero matrix with no negative eigenvalue.This is the defining bad-saddle behavior established for the deeper-network construction.

D Discussion of the 1989 conjecture

The discussion revisits the 1989 conjecture that deeper linear networks inherit the landscape of a collapsed one-hidden-layer model. The paper confirms the conjecture more generally, while showing why the collapse argument itself is incomplete.

Conjecture: The 1989 conjecture concerned one-hidden-layer networks with p < d_y = d_x and proposed key landscape properties including globality of every local minimum.The conjecture’s second feature was that every local minimum is a global minimum.
Prior progress: Earlier work proved convexity in each matrix when the other matrix is fixed, but left the global-local-minimum claim for future work.The convexity feature was established for both real- and complex-valued cases.
Collapse argument: A proposed extension collapses deeper networks into two factors A := W_{H+1}···W_{i+1} and B := W_i···W_1, preserving representational possibilities and rank restrictions.This reasoning would identify local minima of the deep model with local minima of the collapsed model.
Breakdown: The collapse reasoning is incomplete because deeper critical-point conditions contain an additional factor C, which generally cannot equal A unless i = 1.Consequently, the critical and Hessian conditions differ from those of the one-hidden-layer model.
Resolution: The paper nevertheless proves the conjecture with greater generality, without assuming p < d_y = d_x, and adds saddle-point results involving negative-eigenvalue information.The result extends beyond the original dimensional restriction and provides more detailed analytical statements.