Deep Linear Networks with Arbitrary Loss: All Local Minima Are Global

By Thomas Laurent, James von Brecht. 2017

149 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Simon Shaolei Du
2. Wei Hu
3. Sanjeev Arora
4. Tengyu Ma
5. Jason D. Lee
6. Ohad Shamir
7. Yuanzhi Li
8. Yuandong Tian

In Computational Mechanics

1. Simon Shaolei Du
2. Ohad Shamir
3. Wei Hu
4. Sanjeev Arora
5. Nadav Cohen
6. Surya Ganguli
7. Mathieu Salzmann
8. José Manuel Álvarez

Citations in the corpus

• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “ (e.g. Choromanska et al. (2015); Kawaguchi (2016); Hardt and Ma (2016); Soudry and Carmon (2016); Haeffele and Vidal (2017); Nguyen and Hein (2017); Safran and Shamir (2018); Nguyen and Hein (2018); Laurent and Brecht (2018)), have focused on the validity of these properties in different deep learn”
• Understanding self-supervised Learning Dynamics without Contrastive Pairs (2021, background): “Note that deep linear networks have provided a useful tractable theoretical model of nonconvex loss landscapes (Kawaguchi, 2016; Du & Hu, 2019; Laurent & Brecht, 2018) and nonlinear learning dynamics (Saxe et al., 2013; 2019; Lampinen & Ganguli, 2018; Arora et al., 2018) in these landscapes,…”
• Understanding Generalization through Visualizations (2019, unknown): “As a result, an optimizer can reliably fit an over-parameterized network to training data and achieve near zero loss (Laurent and Brecht, 2018; Kawaguchi, 2016).”
• Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, background): “A series of recent papers analyzed landscape of the deep linear network optimization problem (Kawaguchi, 2016; Hardt & Ma, 2016; Lu & Kawaguchi, 2017; Yun et al., 2017; Zhou & Liang, 2018; Laurent & Brecht, 2018).”
• Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks (2018, background): “(1) has no local minima except global ones (see Laurent and Brecht [2018] and references therein).”
• Truth or Backpropaganda? An Empirical Investigation of Deep Learning Theory (2019, background): “Note that our theoretical and experimental results do not contradict theoretical guarantees for deep linear networks (Kawaguchi, 2016; Laurent & Brecht, 2018) which show that all local minima are global.”
• ExpandNets: Linear Over-parameterization to Train Compact Convolutional Networks (2018, background): “While the use of successive linear layers appears in the literature, existing work [5, 6, 25, 29, 50, 63] has been mostly confined to fully-connected networks without any nonlinearities and to the theoretical study of their behavior under fairly unrealistic statistical assumptions.”