mlsanityData to 7 Oct 2026

SGD Learns the Conjugate Kernel Class of the Network

arXiv 1702.08503 ↗First posted 27 Feb 2017cs.LG cs.DS stat.MLcited by 54

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 11; 2023: 16; 2024: 9; 2025: 5; 2026: 2.

54 papers.

Sort:

By area:

  1. 2022Diverse Weight Averaging for Out-of-Distribution Generalizationcited by 148
  2. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 106
  3. 2022Vision Transformers provably learn spatial structurecited by 92
  4. 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
  5. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  6. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  7. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  8. 2023Precise Asymptotic Analysis of Deep Random Feature Modelscited by 22
  9. 2022On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Biascited by 21
  10. 2024Provably learning a multi-head attention layercited by 21
  11. 2022Infinite-width limit of deep linear neural networkscited by 20
  12. 2022Learning Neural Contextual Bandits Through Perturbed Rewardscited by 17
38 more
  1. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  2. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  3. 2021Fundamental Tradeoffs in Distributionally Adversarial Trainingcited by 12
  4. 2021Implicit Bias of Linear RNNscited by 11
  5. 2022Sobolev Acceleration and Statistical Optimality for Learning Elliptic Equations via Gradient Descentcited by 11
  6. 2023A Scalable Walsh-Hadamard Regularizer to Overcome the Low-degree Spectral Bias of Neural Networkscited by 10
  7. 2023On the average-case complexity of learning output distributions of quantum circuitscited by 9
  8. 2024Neural Lineagecited by 9
  9. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  10. 2024SHAP values via sparse Fourier representationcited by 8
  11. 2021Recent Advances in Large Margin Learningcited by 7
  12. 2021A spectral-based analysis of the separation between two-layer neural networks and linear methodscited by 7
  13. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  14. 2024NTK-Guided Few-Shot Class Incremental Learningcited by 7
  15. 2022Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithmcited by 6
  16. 2021Double-descent curves in neural networks: a new perspective using Gaussian processescited by 5
  17. 2022Early Stage Convergence and Global Convergence of Training Mildly Parameterized Neural Networkscited by 5
  18. 2023Structured and Fast Optimization: The Kronecker SGD Algorithmcited by 5
  19. 2023Neural Hilbert Ladders: Multi-Layer Neural Networks in Function Spacecited by 5
  20. 2021Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Netscited by 4
  21. 2022Optimal Activation Functions for the Random Features Regression Modelcited by 4
  22. 2023Deep Reinforcement Learning for Traffic Light Control in Intelligent Transportation Systemscited by 3
  23. 2024Regularized Gauss-Newton for Optimizing Overparameterized Neural Networkscited by 3
  24. 2025LLM Priors for ERM over Programscited by 3
  25. 2021Infinitely Wide Tensor Networks as Gaussian Processcited by 2
  26. 2023Most Neural Networks Are Almost Learnablecited by 2
  27. 2026Deep Networks Learn Deep Hierarchical Modelscited by 2
  28. 2022Learning Neural Ranking Models Online from Implicit User Feedbackcited by 1
  29. 2023Gradient Descent in Neural Networks as Sequential Learning in RKBScited by 1
  30. 2023Applying statistical learning theory to deep learningcited by 1
  31. 2024RedEx: Beyond Fixed Representation Methods via Convex Optimizationcited by 1
  32. 2025Understanding Inverse Reinforcement Learning under Overparameterization: Non-Asymptotic Analysis and Global Optimalitycited by 1
  33. 2025Thompson Sampling in Function Spaces via Neural Operatorscited by 1
  34. 2021Nonlinear Weighted Directed Acyclic Graph and A Priori Estimates for Neural Networkscited by 0
  35. 2023A Simple Algorithm For Scaling Up Kernel Methodscited by 0
  36. 2023The L^∞ Learnability of Reproducing Kernel Hilbert Spacescited by 0
  37. 2024Weak Correlations as the Underlying Principle for Linearization of Gradient-Based Learning Systemscited by 0
  38. 2024Novel Kernel Models and Exact Representor Theory for Neural Networks Beyond the Over-Parameterized Regimecited by 0

50 most cited of 54 All 54 (JSON)