A Provably Correct Algorithm for Deep Learning that Actually Works

By Eran Malach, Shai Shalev-Shwartz. 2018

39 citations recorded by the source corpus.

We describe a layer-by-layer algorithm for training deep convolutional networks, where each step involves gradient updates for a two layer network followed by a simple clustering algorithm. Our algorithm stems from a deep generative model that generates mages level by level, where lower resolution images correspond to latent semantic classes. We analyze the convergence rate of our algorithm assuming that the data is indeed generated according to this model (as well as additional assumptions). While we do not pretend to claim that the assumptions are realistic for natural images, we do believe that they capture some true properties of real data. Furthermore, we show that our algorithm actually works in practice (on the CIFAR dataset), achieving results in the same ballpark as that of vanilla convolutional neural networks that are being trained by stochastic gradient descent. Finally, our proof techniques may be of independent interest.

Subfields: Artificial Intelligence, Statistical Learning Theory, Algorithms & Complexity

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 Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Why Should We Add Early Exits to Neural Networks? (2020, methodology): “, through boosting [17, 24], clustering [44], and kernel similarity [33].”
Greedy Layerwise Learning Can Scale to ImageNet (2018, background): “…works have shown that networks based on sequential 1-hidden layer training can have a variety of guarantees under certain assumptions (Huang et al., 2017; Malach & Shalev-Shwartz, 2018; Arora et al., 2014): greedy layerwise methods could permit to cascade those results to bigger architectures.”
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…”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, methodology): “Such algorithm is used in theoretical works such as [45].”
Training Neural Networks with Local Error Signals (2019, methodology): “Using supervised layer-wise loss functions, without ﬁne-tuning, has also been explored previously (Mostafa et al., 2017; Malach & Shalev-Shwartz, 2018; Mar-a quez et al., 2018).”