# SGD Learns the Conjugate Kernel Class of the Network

arXiv: https://arxiv.org/abs/1702.08503 · HTML: https://mlsanity.com/paper/1702.08503/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2017.

## Built on by (most cited first, 30 of 54)

- [Diverse Weight Averaging for Out-of-Distribution Generalization](https://mlsanity.com/paper/2205.09739/) (2022)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Vision Transformers provably learn spatial structure](https://mlsanity.com/paper/2210.09221/) (2022)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Precise Asymptotic Analysis of Deep Random Feature Models](https://mlsanity.com/paper/2302.06210/) (2023)
- [On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias](https://mlsanity.com/paper/2205.09072/) (2022)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Infinite-width limit of deep linear neural networks](https://mlsanity.com/paper/2211.16980/) (2022)
- [Learning Neural Contextual Bandits Through Perturbed Rewards](https://mlsanity.com/paper/2201.09910/) (2022)
- [Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations](https://mlsanity.com/paper/2107.10209/) (2021)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Fundamental Tradeoffs in Distributionally Adversarial Training](https://mlsanity.com/paper/2101.06309/) (2021)
- [Implicit Bias of Linear RNNs](https://mlsanity.com/paper/2101.07833/) (2021)
- [Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descent](https://mlsanity.com/paper/2205.07331/) (2022)
- [A Scalable Walsh-Hadamard Regularizer to Overcome the Low-degree Spectral Bias of Neural Networks](https://mlsanity.com/paper/2305.09779/) (2023)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [Neural Lineage](https://mlsanity.com/paper/2406.11129/) (2024)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [Recent Advances in Large Margin Learning](https://mlsanity.com/paper/2103.13598/) (2021)
- [A spectral-based analysis of the separation between two-layer neural networks and linear methods](https://mlsanity.com/paper/2108.04964/) (2021)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [NTK-Guided Few-Shot Class Incremental Learning](https://mlsanity.com/paper/2403.12486/) (2024)
- [Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithm](https://mlsanity.com/paper/2207.04612/) (2022)
- [Double-descent curves in neural networks: a new perspective using Gaussian processes](https://mlsanity.com/paper/2102.07238/) (2021)
- [Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networks](https://mlsanity.com/paper/2206.02139/) (2022)
- [Structured and Fast Optimization: The Kronecker SGD Algorithm](https://mlsanity.com/paper/2305.08001/) (2023)

## Abstract (arXiv)

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.