# On the Power of Differentiable Learning versus PAC and SQ Learning

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 10 of 10)

- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Learning Parities with Neural Networks](https://mlsanity.com/paper/2002.07400/) (2020)
- [Stochastic Gradient Descent on Separable Data: Exact Convergence with a Fixed Learning Rate](https://mlsanity.com/paper/1806.01796/) (2018)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [Computational Separation Between Convolutional and Fully-Connected Networks](https://mlsanity.com/paper/2010.01369/) (2020)

## Built on by (most cited first, 28 of 28)

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks](https://mlsanity.com/paper/2204.02892/) (2022)
- [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Random Feature Amplification: Feature Learning and Generalization in Neural Networks](https://mlsanity.com/paper/2202.07626/) (2022)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [A Mathematical Model for Curriculum Learning for Parities](https://mlsanity.com/paper/2301.13833/) (2023)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures](https://mlsanity.com/paper/2205.13647/) (2022)
- [RL for Reasoning by Adaptively Revealing Rationales](https://mlsanity.com/paper/2506.18110/) (2025)
- [On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries](https://mlsanity.com/paper/2407.05622/) (2024)
- [Butterfly Effects of SGD Noise: Error Amplification in Behavior Cloning and Autoregression](https://mlsanity.com/paper/2310.11428/) (2023)
- [An initial alignment between neural network and target is needed for gradient descent to learn](https://mlsanity.com/paper/2202.12846/) (2022)
- [Hardness of Learning Fixed Parities with Neural Networks](https://mlsanity.com/paper/2501.00817/) (2025)
- [Learning ReLU networks to high uniform accuracy is intractable](https://mlsanity.com/paper/2205.13531/) (2022)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach](https://mlsanity.com/paper/2510.04115/) (2025)
- [To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models](https://mlsanity.com/paper/2510.14826/) (2025)
- [Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training](https://mlsanity.com/paper/2511.07372/) (2025)
- [LLM Priors for ERM over Programs](https://mlsanity.com/paper/2510.14331/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms](https://mlsanity.com/paper/2209.00735/) (2022)
- [Unlearnable phases of matter](https://mlsanity.com/paper/2602.11262/) (2026)
- [The Power of Random Features and the Limits of Distribution-Free Gradient Descent](https://mlsanity.com/paper/2505.10423/) (2025)
- [Benign Loss Landscapes Can Coexist with Worst-Case Hardness](https://mlsanity.com/paper/2609.13057/) (2026)
- [Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy](https://mlsanity.com/paper/2610.02749/) (2026)

## Abstract (arXiv)

We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms. We show that SGD and GD can always simulate learning with statistical queries (SQ), but their ability to go beyond that depends on the precision ρ of the gradient calculations relative to the minibatch size b (for SGD) and sample size m (for GD). With fine enough precision relative to minibatch size, namely when b ρ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for b=1. Similarly, with fine enough precision relative to the sample size m, GD can also simulate any sample-based learning algorithm based on m samples. In particular, with polynomially many bits of precision (i.e. when ρ is exponentially small), SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when b ρ2 is large enough, the power of SGD is equivalent to that of SQ learning.