# Poly-time universality and limitations of deep learning

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2020.

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

- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency](https://mlsanity.com/paper/2410.05459/) (2024)
- [The effective noise of Stochastic Gradient Descent](https://mlsanity.com/paper/2112.10852/) (2021)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/2307.06887/) (2023)
- [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)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [How Neural Networks Learn the Support is an Implicit Regularization Effect of SGD](https://mlsanity.com/paper/2406.11110/) (2024)
- [Hardness of Learning Fixed Parities with Neural Networks](https://mlsanity.com/paper/2501.00817/) (2025)
- [Intrinsic dimensionality and generalization properties of the R-norm inductive bias](https://mlsanity.com/paper/2206.05317/) (2022)
- [The Theoretical Expressiveness of Maxpooling](https://mlsanity.com/paper/2203.01016/) (2022)
- [Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models](https://mlsanity.com/paper/2406.05660/) (2024)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Unlearnable phases of matter](https://mlsanity.com/paper/2602.11262/) (2026)
- [Regularization by Misclassification in ReLU Neural Networks](https://mlsanity.com/paper/2111.02154/) (2021)
- [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026)
- [Practically Solving LPN in High Noise Regimes Faster Using Neural Networks](https://mlsanity.com/paper/2303.07987/) (2023)

## Abstract (arXiv)

The goal of this paper is to characterize function distributions that deep learning can or cannot learn in poly-time. A universality result is proved for SGD-based deep learning and a non-universality result is proved for GD-based deep learning; this also gives a separation between SGD-based deep learning and statistical query algorithms: (1) it Deep learning with SGD is efficiently universal. Any function distribution that can be learned from samples in poly-time can also be learned by a poly-size neural net trained with SGD on a poly-time initialization with poly-steps, poly-rate and possibly poly-noise. Therefore deep learning provides a universal learning paradigm: it was known that the approximation and estimation errors could be controlled with poly-size neural nets, using ERM that is NP-hard; this new result shows that the optimization error can also be controlled with SGD in poly-time. The picture changes for GD with large enough batches: (2) it Result (1) does not hold for GD: Neural nets of poly-size trained with GD (full gradients or large enough batches) on any initialization with poly-steps, poly-range and at least poly-noise cannot learn any function distribution that has super-polynomial it cross-predictability, where the cross-predictability gives a measure of ``average'' function correlation -- relations and distinctions to the statistical dimension are discussed. In particular, GD with these constraints can learn efficiently monomials of degree k if and only if k is constant. Thus (1) and (2) point to an interesting contrast: SGD is universal even with some poly-noise while full GD or SQ algorithms are not (e.g., parities).