On the Computational Efficiency of Training Neural Networks

By Roi Livni, Shai Shalev-Shwartz, Ohad Shamir. 2014

501 citations recorded by the source corpus.

It is well-known that neural networks are computationally hard to train. On the other hand, in practice, modern day neural networks are trained efficiently using SGD and a variety of tricks that include different activation functions (e.g. ReLU), over-specification (i.e., train networks which are larger than needed), and regularization. In this paper we revisit the computational complexity of training neural networks from a modern perspective. We provide both positive and negative results, some of them yield new provably efficient and practical algorithms for training certain types of neural networks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression, Optimization & Training

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

In Computer Vision and Pattern Recognition

In Efficiency & Compression

In Optimization & Training

Citations in the corpus

A Convergence Theory for Deep Learning via Over-Parameterization (2018, background): “Stronger hardness results have been proved over the last decade (Daniely, 2016; Daniely & Shalev-Shwartz, 2016; Goel et al., 2017; Klivans & Sherstov, 2009; Livni et al., 2014; Manurangsi & Reichman, 2018; Song et al., 2017).”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “It is also observed that overparameterization and proper random initialization can help the optimization [28, 12, 26, 18], but it is also not well understood why a particular initialization can improve learning.”
Understanding deep learning requires rethinking generalization (2016, background): “A previous construction due to Livni et al. (2014) achieved a similar result with far more parameters, namely, O ( dn ) .”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “In fact, we can drive the exponent arbitrarily close to 1/2 while preserving the non-convexity of the problem.”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “…certain theoretical guarantees for nonconvex optimization, and in particular for training deep neural networks, were recently suggested in various works, for example Ge et al. (2015); Agarwal et al. (2017); Carmon et al. (2016); Janzamin et al. (2015); Livni et al. (2014) and references therein.”
Deep Learning without Poor Local Minima (2016, background): “In addition to its practical success, theoretical results have shown that deep learning is attractive in terms of its generalization properties ( Livni et al., 2014; Mhaskaret al., 2016).”
PPINN: Parareal Physics-Informed Neural Network for time-dependent PDEs (2019, methodology): “Meanwhile, the architecture for the fine PINN in each subdomain is [1] + [20]× 2 + [1] for the first two cases (i.”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “For each k ∈ [ l ] , denote by n k the maximum number of nodes in layer k .”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “Most previous results on learning neural network are negative [39, 28, 38], or positive but with algorithms other than SGD [23, 43, 37, 14, 15, 16], or with strong assumptions on the model [1, 2].”
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): “While discussing quadratic activations we would like to mention the interesting paper [33].”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, methodology): “We acknowledge a different line of research using kernels as improper learners to learn the concept class of neural networks [22, 23, 36, 54].”
Breaking the Curse of Dimensionality with Convex Neural Networks (2014, background): “This implies that the results from Livni et al. (2014), which state that for the quadratic activation function, the incremental problems is equivalent to an eigendecomposition (and hence solvable in polynomial time), do not apply.”
Generalization in Deep Learning (2017, background): “From the viewpoint of compact representation related to small capacity, it has been shown that deep model classes have an exponential advantage to represent certain natural target functions when compared to shallow model classes (Pascanu et al., 2014; Montufar et al., 2014; Livni et al., 2014; Telga”
CryptoDL: Deep Neural Networks over Encrypted Data (2017, background): “Livni et al. analyzed the performance of polynomial as an activation function in neural networks [20].”
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs (2017, background): “Such over-specified networks have been considered (Andoni et al., 2014; Livni et al., 2014) and it was shown that gradient descent can globally learn them in some cases (Andoni et al.”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, methodology): “For example, over-parameterization (Livni et al., 2014), batch-normalization (Ioffe & Szegedy, 2015), and residual networks (He et al.”