Source-linked AI summary
Deep linear neural networks with arbitrary loss: All local minima are global
Thomas Laurent, James von Brecht
TL;DR
The paper asks whether adding depth to deep linear networks creates sub-optimal local minima. It gives a short, elementary proof that under specified width hypotheses, every local minimum is global, while showing differentiability is essential because non-differentiable convex Lipschitz losses can admit sub-optimal local minima.
Problem
The paper studies whether the loss of convexity caused by adding depth to deep linear networks creates sub-optimal local minimizers.
Method
The authors reduce the deep linear problem to optimization of a differentiable function of a product of matrices and provide a short, elementary proof based on this formulation.
Results
Under the stated hypotheses, deep linear networks have no sub-optimal minimizers, while a convex Lipschitz non-differentiable loss can produce sub-optimal local minimizers.
Takeaways & Limitations
For the covered width conditions and differentiable convex losses, analyzing local minima suffices because every local minimum is global.
Takeaways & Limitations
Without additional structural assumptions on the product-matrix objective, a deep linear minimizer may satisfy first-order optimality without being globally optimal.
Abstract
from arXiv · showhide
We consider deep linear networks with arbitrary convex differentiable loss. We provide a short and elementary proof of the fact that all local minima are global minima if the hidden layers are either 1) at least as wide as the input layer, or 2) at least as wide as the output layer. This result is the strongest possible in the following sense: If the loss is convex and Lipschitz but not differentiable then deep linear networks can have sub-optimal local minima.
1. Introduction
Deep linear networks provide simplified models for studying whether depth and the resulting nonconvexity create sub-optimal local minima. The paper resolves this question for arbitrary convex differentiable losses under width conditions, while showing differentiability is essential.
- Motivation: Deep linear networks simplify analysis of loss surfaces but become nonconvex with multiple layers, motivating the study of sub-optimal local minima.With one layer the loss is convex; with multiple layers, depth removes convexity.
- Main result: The paper resolves the local-minima question for arbitrary convex differentiable losses under two hidden-layer width hypotheses.The relevant condition is that the thinnest layer is either the input or output layer.
- Main result: Any local minimum is global when the stated hypotheses hold, so the deep linear problem has no sub-optimal minimizers.These hypotheses commonly apply to losses such as mean squared error, logistic, and cross-entropy loss, and in classification when hidden layers exceed the number of classes.
- Proof approach: The authors give a short, transparent proof accessible with basic singular value decomposition knowledge and without sophisticated optimization or linear-algebra machinery.The theorem follows from a more general result about optimizing differentiable functions over products of matrices.
- Limitation: Differentiability is essential: convex Lipschitz losses that are not differentiable can produce sub-optimal local minimizers.Thus the local-equals-global guarantee has a hard boundary at nondifferentiable losses.
- Relation to prior work: The result improves on prior analyses by requiring no assumptions on data or targets and allowing any differentiable convex loss.The proof is also described as shorter and more elementary than earlier treatments.
2. Proof of Theorem 1
The proof reduces deep linear optimization to optimizing a differentiable function of the full matrix product, then shows every local minimizer induces a critical point of that function. Under the width condition, convexity makes the induced critical point globally minimizing.
- Product-matrix reduction: Theorem 3 treats objectives of the form F(W1, ..., WL) = f(WL · · · W1) and assumes the structural condition dk ≥ d0.The deep linear problem is viewed as optimization over matrices realized by an L-fold product.
- Product-matrix reduction: Theorem 1 follows because the loss depends on the full product through a convex differentiable function f(A), while the width hypothesis ensures the structural condition.The total loss is written as L(W1, . . . , WL) = f(WL · · · W1).
- Conclusion: Because f is convex, the resulting critical point is necessarily a global minimum, so every local minimum of the deep linear objective is global.The argument applies after showing the perturbed factorization remains a local minimizer while preserving the full product.
- Critical-point argument: At a local minimum, vanishing layerwise partial derivatives and the perturbation argument imply that the full-product gradient vanishes at A = WL · · · W1.The proof handles nontrivial kernels by constructing nearby factorizations that preserve the overall product.
- Critical-point argument: The singular-value decomposition identifies a zero least singular value in the rank-deficient truncated products, enabling product-preserving perturbations through the available width.For dk ≥ d0, each truncated product has more rows than columns; when its kernel is nontrivial, its least singular value is zero.
3. Concluding Remarks
The concluding analysis identifies the assumptions needed for the deep-linear correspondence and shows how relaxing them produces failure modes, including sub-optimal local minima under non-differentiable convex losses. It also explains why the structural width condition is necessary and why nonconvex objectives provide weaker guarantees.
- Limits of the theorem: For L ≥ 3, the all-zero weights always form a critical point, so saddle points can coexist with the property that all local optima are global.Theorem 3 concerns local minimizers rather than all critical points.
- Limits of the theorem: Convex, globally Lipschitz but non-differentiable losses can produce sub-optimal local minima in deep linear problems.The paper gives this as the sharp limitation of the differentiability assumption.
- Counterexample: The counterexample uses a two-layer network and establishes a strict sub-optimal local minimizer through a neighborhood inequality around the candidate point.The construction shows that nearby parameterizations have no lower objective, except when they represent the same product.
- Limits of the theorem: The theorem’s proof depends on a single-valued gradient at the optimum, whereas the counterexample’s convex objective has a multi-valued subdifferential there.This pinpoints non-differentiability as the mechanism behind the failure.
- Limits of the theorem: If a hidden layer is narrower than both the input and output layers, the parametrization cannot recover full-rank matrices, so the structural theorem fails.The argument uses functions whose gradients vanish only at full-rank matrices.
- Limits of the theorem: Without convexity, a deep-linear local minimizer need not correspond to a minimizer of the original matrix problem, although it still satisfies first-order optimality.The paper illustrates this with a nonconvex objective whose origin is a saddle point while the deep parametrization has a local minimizer.