Global Optimality in Tensor Factorization, Deep Learning, and Beyond

By Benjamin David Haeffele, René Vidal. 2015

151 citations recorded by the source corpus.

Techniques involving factorization are found in a wide range of applications and have enjoyed significant empirical success in many fields. However, common to a vast majority of these problems is the significant disadvantage that the associated optimization problems are typically non-convex due to a multilinear form or other convexity destroying transformation. Here we build on ideas from convex relaxations of matrix factorizations and present a very general framework which allows for the analysis of a wide range of non-convex factorization problems - including matrix factorization, tensor factorization, and deep neural network training formulations. We derive sufficient conditions to guarantee that a local minimum of the non-convex optimization problem is a global minimum and show that if the size of the factorized variables is large enough then from any initialization it is possible to find a global minimizer using a purely local descent algorithm. Our framework also provides a partial theoretical justification for the increasingly common use of Rectified Linear Units (ReLUs) in deep neural networks and offers guidance on deep network architectures and regularization strategies to facilitate efficient optimization.

Subfields: Computational Mathematics, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

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

In Computational Mathematics

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

Robust Large Margin Deep Neural Networks (2016, background): “Optimization aspects of DNNs are studied from the perspective of tensor factorization in [18] where it is shown that if a network is large, then it is possible to find the global minima from any initialization with a gradient descent algorithm.”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “However, such wide networks are easy to optimize, since by training the last layer we get to a global minimum (zero training error) from almost every random initialization [11, 16, 23].”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Several publications study the effect of over-parametrization on the training of neural networks [19], [37], [39].”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “…functions [Soudry and Hoffer, 2017, Safran and Shamir, 2018, 2016, Zhou and Liang, 2017, Freeman and Bruna, 2016, Hardt and Ma, 2016, Nguyen and Hein, 2017, Kawaguchi, 2016, Venturi et al., 2018, Soudry and Carmon, 2016, Du and Lee, 2018, Soltanolkotabi et al., 2018, Haeffele and Vidal, 2015].”
Spurious Local Minima are Common in Two-Layer ReLU Neural Networks (2017, background): “…if the network is over-parameterized, and large enough compared to the data size, then there are no local minima [Poston et al., 1991, Livni et al., 2014, Haeffele and Vidal, 2015, Zhang et al., 2016, Soudry and Carmon, 2016, Soltanolkotabi et al., 2017, Nguyen and Hein, 2017, Boob and Lan, 2017].”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “…optimization landscapes of neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Du and Lee, 2018, Hardt and Ma, 2016, Bartlett et al., 2018, Haeffele and Vidal, 2015, Freeman and Bruna, 2016, Vidal et al., 2017, Safran and Shamir, 2016, Zhou and Feng, 2017, Nguyen and Hein, 2017a,b, Zhou…”
Stochastic Conditional Generative Networks with Basis Decomposition (2019, background): “Works on studying the relationship between local and global minima of deep networks [9, 26] also suggest the non-uniqueness of optimal parameters of a deep network.”
Tensor Regression Networks (2017, background): “Haeﬀele and Vidal (2015) derive suﬃcient conditions for global optimality and optimization of non-convex factorization problems, including tensor factorization and deep neural network training.”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Many studies (Haeffele and Vidal, 2015; Kawaguchi, 2016; Freeman and Bruna, 2016; Hardt and Ma, 2016; Safran and Shamir, 2017; Xie et al., 2017; Nguyen and Hein, 2017; Soltanolkotabi et al., 2017; Zhou and Liang, 2017; Yun et al., 2017; Du and Lee, 2018; Venturi et al., 2018) investigated the…”
The non-convex geometry of low-rank matrix optimization (2016, methodology): “We finally note that compared with [28], our result (Theorem 2) does not depend on the existence of zero columns at the critical points and hence can provide guarantees for many local-search algorithms.”
Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods (2017, background): “Haeffele and Vidal (2015) provide a general framework for characterizing when local optima become global in deep learning and other scenarios.”
The Effect of Gradient Noise on the Energy Landscape of Deep Networks (2015, background): “This paper is in the spirit of results that analyze algorithms for training deep networks using knowledge of the landscape of the cost function, e.g., Dauphin et al. (2014); Haeffele and Vidal (2015); Janzamin et al. (2015).”
When is a Convolutional Filter Easy To Learn? (2017, background): “…2017].2 This motivates the research of studying the landscape of neural networks [Kawaguchi, 2016, Choromanska et al., 2015, Hardt and Ma, 2016, Haeffele and Vidal, 2015, Mei et al., 2016, Freeman and Bruna, 2016, Safran and Shamir, 2016, Zhou and Feng, 2017] However, these results cannot be…”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “This motivates the research of studying the landscape of neural networks (Kawaguchi, 2016; Choromanska et al., 2015; Freeman and Bruna, 2016; Zhou and Feng, 2017; Nguyen and Hein, 2017a;b; Ge et al., 2017; Safran and Shamir, 2017; Soltanolkotabi et al., 2017; Poston et al., 1991; Haeffele and Vidal,”