# On the non-universality of deep learning: quantifying the cost of symmetry

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 73 references that are in the map.
- First posted on arXiv 5 Aug 2022.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [Lorentz Group Equivariant Neural Network for Particle Physics](https://mlsanity.com/paper/2006.04780/) (2020)
- [What Can ResNet Learn Efficiently, Going Beyond Kernels?](https://mlsanity.com/paper/1905.10337/) (2019)
- [Provably Strict Generalisation Benefit for Equivariant Models](https://mlsanity.com/paper/2102.10333/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?](https://mlsanity.com/paper/2010.08515/) (2020)
- [Provably Strict Generalisation Benefit for Invariance in Kernel Methods](https://mlsanity.com/paper/2106.02346/) (2021)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Distribution-Specific Hardness of Learning Neural Networks](https://mlsanity.com/paper/1609.01037/) (2016)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Poly-time universality and limitations of deep learning](https://mlsanity.com/paper/2001.02992/) (2020)
- [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [Computational Separation Between Convolutional and Fully-Connected Networks](https://mlsanity.com/paper/2010.01369/) (2020)

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

- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad](https://mlsanity.com/paper/2406.06467/) (2024)
- [Why Do You Grok? A Theoretical Analysis of Grokking Modular Addition](https://mlsanity.com/paper/2407.12332/) (2024)
- [Symmetry in Neural Network Parameter Spaces](https://mlsanity.com/paper/2506.13018/) (2025)
- [When can transformers reason with abstract symbols?](https://mlsanity.com/paper/2310.09753/) (2023)
- [Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputs](https://mlsanity.com/paper/2306.16921/) (2023)
- [Theoretical Analysis of Inductive Biases in Deep Convolutional Networks](https://mlsanity.com/paper/2305.08404/) (2023)
- [A Mathematical Model for Curriculum Learning for Parities](https://mlsanity.com/paper/2301.13833/) (2023)
- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries](https://mlsanity.com/paper/2407.05622/) (2024)
- [The Belief State Transformer](https://mlsanity.com/paper/2410.23506/) (2024)
- [Hardness of Learning Fixed Parities with Neural Networks](https://mlsanity.com/paper/2501.00817/) (2025)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Rao-Blackwell Gradient Estimators for Equivariant Denoising Diffusion](https://mlsanity.com/paper/2502.09890/) (2025)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Noise misleads rotation invariant algorithms on sparse targets](https://mlsanity.com/paper/2403.02697/) (2024)
- [On (not) learning the M"obius function](https://mlsanity.com/paper/2604.23427/) (2026)

## Abstract (arXiv)

We prove limitations on what neural networks trained by noisy gradient descent (GD) can efficiently learn. Our results apply whenever GD training is equivariant, which holds for many standard architectures and initializations. As applications, (i) we characterize the functions that fully-connected networks can weak-learn on the binary hypercube and unit sphere, demonstrating that depth-2 is as powerful as any other depth for this task; (ii) we extend the merged-staircase necessity result for learning with latent low-dimensional structure [ABM22] to beyond the mean-field regime. Under cryptographic assumptions, we also show hardness results for learning with fully-connected networks trained by stochastic gradient descent (SGD).