mlsanityData to 7 Oct 2026

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

arXiv 2208.03113 ↗First posted 5 Aug 2022cs.LGcited by 17

Not on the map. Why?

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).

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

Builds on

32 of 73 references.

References · 32

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2017Graph Attention Networkscited by 8,854
  4. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  6. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  8. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  9. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  10. 2019Linearized two-layers neural networks in high dimensioncited by 155
  11. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 141
  12. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
20 more
  1. 2020Lorentz Group Equivariant Neural Network for Particle Physicscited by 120
  2. 2019What Can ResNet Learn Efficiently, Going Beyond Kernels?cited by 91
  3. 2021Provably Strict Generalisation Benefit for Equivariant Modelscited by 90
  4. 2021Learning with invariances in random features and kernel modelscited by 89
  5. 2017Failures of Gradient-Based Deep Learningcited by 79
  6. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  7. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 42
  8. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  9. 2020Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?cited by 32
  10. 2021On the Approximation Power of Two-Layer Networks of Random ReLUscited by 29
  11. 2021Provably Strict Generalisation Benefit for Invariance in Kernel Methodscited by 29
  12. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
  13. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 27
  14. 2020Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexitycited by 25
  15. 2020Poly-time universality and limitations of deep learningcited by 23
  16. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 21
  17. 2021Learning with convolution and pooling operations in kernel methodscited by 21
  18. 2020Computational Separation Between Convolutional and Fully-Connected Networkscited by 19
  19. 2022An initial alignment between neural network and target is needed for gradient descent to learncited by 12
  20. 2019On Symmetry and Initialization for Neural Networkscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 6; 2024: 6; 2025: 4; 2026: 1.

17 papers.

Sort:

By area:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  2. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  3. 2024Why Do You Grok? A Theoretical Analysis of Grokking Modular Additioncited by 34
  4. 2025Symmetry in Neural Network Parameter Spacescited by 31
  5. 2023When can transformers reason with abstract symbols?cited by 23
  6. 2023Provable Advantage of Curriculum Learning on Parity Targets with Mixed Inputscited by 22
  7. 2023Theoretical Analysis of Inductive Biases in Deep Convolutional Networkscited by 21
  8. 2023A Mathematical Model for Curriculum Learning for Paritiescited by 19
  9. 2024Towards a theory of model distillationcited by 14
  10. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 13
  11. 2024The Belief State Transformercited by 12
  12. 2025Hardness of Learning Fixed Parities with Neural Networkscited by 7
5 more
  1. 2025Beyond Statistical Learning: Exact Learning Is Essential for General Intelligencecited by 6
  2. 2023Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methodscited by 5
  3. 2025Rao-Blackwell Gradient Estimators for Equivariant Denoising Diffusioncited by 4
  4. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  5. 2024Noise misleads rotation invariant algorithms on sparse targetscited by 0