SGD Learns the Conjugate Kernel Class of the Network

By Amit Daniely. 2017

188 citations recorded by the source corpus.

We show that the standard stochastic gradient decent (SGD) algorithm is guaranteed to learn, in polynomial time, a function that is competitive with the best function in the conjugate kernel space of the network, as defined in Daniely, Frostig and Singer. The result holds for log-depth networks from a rich family of architectures. To the best of our knowledge, it is the first polynomial-time guarantee for the standard neural network learning algorithm for networks of depth more that two. As corollaries, it follows that for neural networks of any depth between 2 and log(n), SGD is guaranteed to learn, in polynomial time, constant degree polynomials with polynomially bounded coefficients. Likewise, it follows that SGD on large enough networks can learn any continuous function (not in polynomial time), complementing classical expressivity results.

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

In Computer Vision and Pattern Recognition

In Optimization & Training

In Scaling & Learning Theory

Citations in the corpus

Wide neural networks of any depth evolve as linear models under gradient descent (2019, methodology): “Daniely [17] uses the same kernel perspective to study stochastic gradient descent (SGD) training of neural networks.”
The large learning rate phase of deep learning: the catapult mechanism (2020, background): “1 0 Learning rate 0.60 A recent body of work has investigated the gradient descent dynamics of deep networks in the limit of inﬁnite width (Daniely, 2017; Jacot et al., 2018; Lee et al., 2019; Du et al., 2019; Zou et al., 2018; Allen-Zhu et al., 2019; Li & Liang, 2018; Chizat et al., 2019; Mei et…”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, background): “(12)This can be more meaningful than training all the layers together, in which if one is not careful with parameter choices, the training process can degenerate as if only the last layer is trained [11].”
A Convergence Theory for Deep Learning via Over-Parameterization (2018, neutral): “The result of Daniely [14] applies to multi-layer neural network with ReLU activation, but is about the convex training process only with respect to the last layer.”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “Daniely [2017] built connection between neural networks with kernel methods and showed stochastic gradient descent can learn a function that is competitive with the best function in the conjugate kernel space of the network.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “Lastly, our work is related to kernel methods, especially recent discoveries of the connection between deep learning and kernels (Jacot et al., 2018; Chizat & Bach, 2018b; Daniely et al., 2016; Daniely, 2017).”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “Daniely et al. [2016] proposed a general framework to transform a neural network to a compositional kernel and later Daniely [2017] showed for suﬃciently wide neural networks, stochastic gradient descent can learn functions that lie in the corresponding reproducing kernel Hilbert space.”
Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “As a comparison, [15] studies the regime where the changes in hidden layers are negligible thus can not show how to learn this concept class with a three-layer network.”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “In particular, existing work only demonstrate that gradient descent works under the same situations as kernel methods and random feature methods (Daniely, 2017; Li & Liang, 2018; Allen-Zhu et al., 2018a; Arora et al., 2019).”
On the Convergence Rate of Training Recurrent Neural Networks (2018, background): “Some study the convex task of training essentially only the last layer of the network [13].”
A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics (2019, background): “For this reason, there has been a lot of recent theoretical work centered on these issues [15, 16, 12, 11, 2, 8, 10, 31, 29, 28, 25, 27].”
Disentangling trainability and generalization in deep learning (2019, background): “Recently, there has been renewed interest in studying random, inﬁnite, networks starting with concurrent work on “conjugate kernels” (Daniely et al., 2016; Daniely, 2017) and “mean-ﬁeld theory” (Poole et al., 2016; Schoenholz et al., 2017).”
Kernel and Rich Regimes in Overparametrized Models (2019, background): “They observe that, in a certain regime, networks trained with gradient descent behave as kernel methods [6, 7, 15].”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “Recently, a spate of papers (such as [4, 11, 14, 2, 23, 15, 9, 3, 1]) provided positive results for training and learning with over-parameterized neural networks.”
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks (2018, background): “Representation theorems analogous to our own were also proved in [3], and a very general analysis of gradient descent is given in [8].”
Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem (2018, background): “Recently, there have been numerous works that provide guarantees for gradient-based methods in general settings (Daniely, 2017; Li & Liang, 2018; Du et al., 2018c;a; Allen-Zhu et al., 2018).”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “For the generalization of DNNs, a number of authors (Daniely, 2017; Cao & Gu, 2019; 2020; Arora et al., 2019; Chen et al., 2019) show that by using (stochastic) gradient descent, the parameters of a DNN are located in a particular regime and the generalization bound of DNNs can be characterized by…”