Provable Bounds for Learning Some Deep Representations

By Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma. 2013

342 citations recorded by the source corpus.

We give algorithms with provable guarantees that learn a class of deep nets in the generative model view popularized by Hinton and others. Our generative model is an n node multilayer network that has degree at most nγ for some γ < 1 and each edge has a random edge weight in [-1, 1]. Our algorithm learns almost all networks in this class with polynomial running time. The sample complexity is quadratic or cubic depending upon the details of the model. The algorithm uses layerwise learning. It is based upon a novel idea of observing correlations among features and using these to infer the underlying edge structure via a global graph recovery procedure. The analysis of the algorithm reveals interesting structure of neural nets with random edge weights.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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

In Computer Vision and Pattern Recognition

In Scaling & Learning Theory

Citations in the corpus

Going deeper with convolutions (2014, background): “In general, one can view the Inception model as a logical culmination of [12] while taking inspiration and guidance from the theoretical work by Arora et al [2].”
Deep Compression: Compressing Deep Neural Network with Pruning, Trained Quantization and Huffman Coding (2015, positive): “The empirical success in this paper is consistent with the theoretical study of random-like sparse networks with +1/0/-1 weights (Arora et al., 2014), which have been proved to enjoy nice properties (e.g. reversibility), and to allow a provably polynomial time algorithm for training.”
XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks (2016, background): “[30] proposed a provably polynomial time algorithm for training a sparse networks with +1/0/ − 1 weights.”
Convergent Learning: Do different neural networks learn the same representations? (2015, background): “Many recent studies have focused on understanding deep neural networks from both a theoretical perspective (Arora et al., 2014; Neyshabur & Panigrahy, 2013; Montavon et al., 2011; Paul & Venkatasubramanian, 2014; Goodfellow et al., 2014) and from an empirical perspective (Erhan et al., 2009; Eigen…”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “The fourth takes the generative point of view (e.g. [Arora et al., 2014, 2015]), assuming that the data actually comes from a particular network and then attempting to recover it.”
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].”
On the Computational Efficiency of Training Neural Networks (2014, background): “On a related note, [4] recently showed positive results on learning from data generated by a neural network of a certain architecture and randomly connected weights.”
On the Convergence Rate of Training Recurrent Neural Networks (2018, methodology): “Instead of using randomly initialized weights like this paper, there is a line of work proposing algorithms using weights generated from some “tensor initialization” process [4, 26, 48, 55, 61].”
Learning One-hidden-layer Neural Networks with Landscape Design (2017, background): “3 RELATED WORK The work of Arora et al. (2014) is one of the early results on provable algorithms for learning deep neural networks, where the authors give an algorithm for learning deep generative models with sparse weights. Livni et al. (2014), Zhang et al.”
SGD Learns the Conjugate Kernel Class of the Network (2017, background): “Various recent papers show that poly-time learning is possible in the case that the the learnt function can be realized by a neural network with certain (usually fairly strong) restrictions on the weights [23, 34, 33, 35], or under the assumption that the data is generated by a generative model that”
ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time (2015, methodology): “Under this assumption, Arora et al. [2] study the recovery of denoising auto-encoders which are represented by multi-layer neural networks.”
Gradient Descent with Identity Initialization Efficiently Learns Positive-Definite Linear Transformations by Deep Residual Networks (2018, background): “in polynomial time; this class includes constant-degree polynomials with polynomially bounded coeﬃcients. Other theoretical treatments of neural network learning algorithms include Lee et al. (1996); Arora et al. (2014); Livni et al. (2014); Janzamin et al. (2015); Safran & Shamir (2016); Zhang ”
Shallow Learning For Deep Networks (2018, background): “2, previous attempts at supervised layerwise training (Fahlman & Lebiere, 1990a; Arora et al., 2014; Huang et al., 2017; Malach & Shalev-Shwartz, 2018), which rely solely on sequential solving of shallow problems have yielded performance well below that of typical deep learning models on the CIFAR…”
Interpretable R-CNN (2017, background): “It is difficult to analyze why state-of-the-art deep neural networks work or fail due to the lack of theoretical underpinnings at present [1].”
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds (2018, methodology): “Earlier work gave combinatorial methods to learn random networks [2], guarantees for learning linear dynamical systems by GD [19] and ReLU networks with more restrictive assumptions [24].”