SGD Learns the Conjugate Kernel Class of the Network

Abstract

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.

Cited by in corpus (58)

• A Convergence Theory for Deep Learning via Over-Parameterization
• On Exact Computation with an Infinitely Wide Neural Net
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• On the Convergence Rate of Training Recurrent Neural Networks
• A Priori Estimates of the Population Risk for Two-layer Neural Networks
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• The large learning rate phase of deep learning: the catapult mechanism
• Kernel and Rich Regimes in Overparametrized Models
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Asymptotics of Wide Networks from Feynman Diagrams
• Finite Versus Infinite Neural Networks: an Empirical Study
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Sequential Training of Neural Networks with Gradient Boosting
• Mathematical Models of Overparameterized Neural Networks
• On the Power and Limitations of Random Features for Understanding Neural Networks
• Deep Reinforcement Learning for Unmanned Aerial Vehicle-Assisted Vehicular Networks
• Universality Laws for High-Dimensional Learning with Random Features
• Analysis of the Gradient Descent Algorithm for a Deep Neural Network Model with Skip-connections
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• On Convergence and Generalization of Dropout Training
• Asymptotics of Wide Convolutional Neural Networks
• Towards NNGP-guided Neural Architecture Search
• Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks
• Taylorized Training: Towards Better Approximation of Neural Network Training at Finite Width
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Decoupling Gating from Linearity
• Learning Parities with Neural Networks
• Computational Separation Between Convolutional and Fully-Connected Networks
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• The Local Elasticity of Neural Networks
• On the Global Convergence of Training Deep Linear ResNets
• Deep Learning is Singular, and That's Good
• How Powerful are Shallow Neural Networks with Bandlimited Random Weights?
• Generalized Leverage Score Sampling for Neural Networks
• Memorizing Gaussians with no over-parameterizaion via gradient decent on neural networks
• Benign Overfitting and Noisy Features
• Can Temporal-Difference and Q-Learning Learn Representation? A Mean-Field Theory
• Theory III: Dynamics and Generalization in Deep Networks
• Infinitely Wide Tensor Networks as Gaussian Process
• A Deep Conditioning Treatment of Neural Networks
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• Wider Networks Learn Better Features
• Generalization Error of Generalized Linear Models in High Dimensions
• Fundamental Tradeoffs in Distributionally Adversarial Training
• Implicit Bias of Linear RNNs
• Learning Boolean Circuits with Neural Networks
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• On Symmetry and Initialization for Neural Networks
• Recent Advances in Large Margin Learning
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines