Deep Learning without Poor Local Minima
By Kenji Kawaguchi. 2016
1,010 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Scaling & Learning Theory
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
- Yoshua Bengio
- Sergey Levine
- Ruslan Salakhutdinov
- Quoc V. Le
- Percy Liang
- Mohit Bansal
- Dacheng Tao
- Jianfeng Gao
In Computational Mechanics
- Jason D. Lee
- Zeyuan Allen-Zhu
- Peter Richtárik
- Michael I. Jordan
- Simon Lacoste-Julien
- Simon Shaolei Du
- Tengyu Ma
- Ohad Shamir
In Optimization & Training
- Jason D. Lee
- Yuanzhi Li
- Zeyuan Allen-Zhu
- Simon Shaolei Du
- Tengyu Ma
- Simon Lacoste-Julien
- Quanquan Gu
- Yoshua Bengio
In Scaling & Learning Theory
- Yuanzhi Li
- Jason D. Lee
- Quanquan Gu
- Tengyu Ma
- Simon Shaolei Du
- Zeyuan Allen-Zhu
- Wei Hu
- M. Soltanolkotabi
Citations in the corpus
- A Closer Look at the Optimization Landscapes of Generative Adversarial Networks (2019, background): “This success has motivated many studies of their non-convex loss landscape (Choromanska et al., 2015; Kawaguchi, 2016; Li et al., 2018b), which, in turn, has led to many improvements, such as better initialization and optimization methods (Glorot and Bengio, 2010; Kingma and Ba, 2015).”
- Coulomb GANs: Provably Optimal Nash Equilibria via Potential Fields (2017, background): “Even though these are strong assumptions, recent research indicates that the effect of local minima in deep learning vanishes with increasing depth [9, 7, 25], while capacity increases with network size.”
- Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “Most of existing works (1) only focus on the case when the training data is spherical Gaussian [28–43], and some of them require heavy initialization using tensor decomposition, which might fail to capture the specific structure of the input and the property of a random initialization; or (2) only c”
- A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Besides the already cited references (Arora et al., 2018a; Bartlett et al., 2018; Hardt & Ma, 2017; Kawaguchi, 2016), there are a number of works that study linear dynamical systems, which can be viewed as the linear version of recurrent neural networks or reinforcement learning.”
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “There also exists a large body of work that analyzes the optimization landscape of learning neural networks [13, 26, 30, 10, 25, 29, 6, 32, 17, 5].”
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “For other activation functions, some previous works showed the landscape does have the desired geometric properties (Du and Lee, 2018; Soltanolkotabi et al., 2018; Nguyen and Hein, 2017; Kawaguchi, 2016; Haeffele and Vidal, 2015; Andoni et al., 2014; Venturi et al., 2018; Yun et al., 2018a).”
- On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “We respond to this hurdle by focusing on linear neural networks ( cf. Saxe et al. (2013); Goodfellow et al. (2016); Hardt & Ma (2016); Kawaguchi (2016)).”
- Explainable Artificial Intelligence (XAI): Concepts, Taxonomies, Opportunities and Challenges toward Responsible AI (2019, neutral): “Contrarily, it is not possible to understand it in deep architectures as the loss landscape might be opaque [172,173] since it cannot be fully observed and the solution has to be approximated through heuristic optimization (e.g. through stochastic gradient descent).”
- Visualizing the Loss Landscape of Neural Nets (2017, background): “These assumptions have been relaxed by Kawaguchi (2016) and Lu & Kawaguchi (2017), although some assumptions (e.g., of the loss functions) are still required.”
- Entropy-SGD: biasing gradient descent into wide valleys (2016, neutral): “…good generalization error, however, is challenging: complex architectures are sensitive to initial conditions and learning rates (Sutskever et al., 2013) and even linear networks (Kawaguchi, 2016) may have degenerate and hard to escape saddle points (Ge et al., 2015; Anandkumar & Ge, 2016).”
- Representation Learning on Graphs with Jumping Knowledge Networks (2018, methodology): “With a randomization assumption of the ReLU activations similar to that in (Kawaguchi, 2016; Choromanska et al., 2015), we can draw connections between GCNs and random walks: Theorem 1.”
- Geometric Deep Learning: Going beyond Euclidean data (2016, background): “Understanding the structure of the optimization problems (10) and finding efficient strategies for its solution is an active area of research in deep learning [60], [61], [62], [63].”
- BatchEnsemble: An Alternative Approach to Efficient Ensemble and Lifelong Learning (2020, background): “…networks, combined with the fact that there is a wide variety of local minima solutions in high dimensional optimization problem (Ge et al., 2015; Kawaguchi, 2016; Wen et al., 2019), results in the following observation: deep neural networks trained with different random seeds can converge to…”
- A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “While condition (i) does not always hold ( cf. Safran and Shamir (2018)), it has been established for various simple settings ( e.g. Soudry and Carmon (2016); Kawaguchi (2016)).”
- Essentially No Barriers in Neural Network Energy Landscape (2018, background): “…and non-convex loss functions are few or based on strong assumptions such as the eigenvalues of the Hessian at critical points being random (Dauphin et al., 2014), linear activations (Choro-manska et al., 2014; Kawaguchi, 2016) or wide hidden layers (Soudry & Carmon, 2016; Nguyen & Hein, 2017).”
- Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, methodology): “Moreover, previous analyses either ignore the nonlinear activations and thus consider linear model [36, 24, 19], or directly [5, 24] or indirectly [41]1 assume that the activations are independent.”
- Identity Matters in Deep Learning (2016, background): “Residual networks, and subsequent architectures that use the same parameterization, have since then consistently achieved state-of-the-art results on various computer vision benchmarks such as CIFAR10 and ImageNet.”