mlsanityData to 14 Oct 2026

On the hardness of learning under symmetries

arXiv 2401.01869 ↗First posted 3 Jan 2024cs.LG cs.DS math.STcited by 13

Not on the map. Why?

Abstract (arXiv)

We study the problem of learning equivariant neural networks via gradient descent. The incorporation of known symmetries ("equivariance") into neural nets has empirically improved the performance of learning pipelines, in domains ranging from biology to computer vision. However, a rich yet separate line of learning theoretic research has demonstrated that actually learning shallow, fully-connected (i.e. non-symmetric) networks has exponential complexity in the correlational statistical query (CSQ) model, a framework encompassing gradient descent. In this work, we ask: are known problem symmetries sufficient to alleviate the fundamental hardness of learning neural nets with gradient descent? We answer this question in the negative. In particular, we give lower bounds for shallow graph neural networks, convolutional networks, invariant polynomials, and frame-averaged networks for permutation subgroups, which all scale either superpolynomially or exponentially in the relevant input dimension. Therefore, in spite of the significant inductive bias imparted via symmetry, actually learning the complete classes of functions represented by equivariant neural networks via gradient descent remains hard.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 48 of its 110 references that are in the map. First posted on arXiv 3 Jan 2024.

Builds on

48 of 110 references.

References · 48

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  4. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  5. 2020Benchmarking Graph Neural Networkscited by 680
  6. 2020The Pitfalls of Simplicity Bias in Neural Networkscited by 351
  7. 2020Can Graph Neural Networks Count Substructures?cited by 236
  8. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  9. 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 183
  10. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  11. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  12. 2021Learning with invariances in random features and kernel modelscited by 89
36 more
  1. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 85
  2. 2020A Unifying View on Implicit Bias in Training Linear Neural Networkscited by 75
  3. 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 64
  4. 2022Theory for Equivariant Quantum Neural Networkscited by 62
  5. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  6. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  7. 2019Generalization bounds for deep convolutional neural networkscited by 59
  8. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 58
  9. 2022Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networkscited by 52
  10. 2020Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalentcited by 51
  11. 2023Approximation-Generalization Trade-offs under (Approximate) Group Equivariancecited by 46
  12. 2022Representation Theory for Geometric Quantum Machine Learningcited by 40
  13. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  14. 2022Training invariances and the low-rank phenomenon: beyond linear networkscited by 33
  15. 2021Provably Strict Generalisation Benefit for Invariance in Kernel Methodscited by 30
  16. 2017Bayesian estimation from few samples: community detection and related problemscited by 28
  17. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 28
  18. 2023The Exact Sample Complexity Gain from Invariances for Kernel Regressioncited by 28
  19. 2020Learning Deep ReLU Networks Is Fixed-Parameter Tractablecited by 26
  20. 2020Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Casecited by 24
  21. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 22
  22. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  23. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  24. 2021Implicit Bias of Linear Equivariant Networkscited by 19
  25. 2017On the Complexity of Learning Neural Networkscited by 18
  26. 2022A PAC-Bayesian Generalization Bound for Equivariant Networkscited by 18
  27. 2021Generalization bounds for graph convolutional neural networks via Rademacher complexitycited by 17
  28. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  29. 2017Learning Non-overlapping Convolutional Neural Networks with Multiple Kernelscited by 14
  30. 2023Learning Narrow One-Hidden-Layer ReLU Networkscited by 14
  31. 2023On the Implicit Bias of Linear Equivariant Steerable Networkscited by 7
  32. 2023A faster and simpler algorithm for learning shallow networkscited by 7
  33. 2018End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decompositioncited by 6
  34. 2018Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlapscited by 6
  35. 2019On the Learnability of Deep Random Networkscited by 4
  36. 2023Most Neural Networks Are Almost Learnablecited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 5; 2025: 4; 2026: 4.

13 papers.

Sort:

  1. 2024Lie Algebra Canonicalization: Equivariant Neural Operators under arbitrary Lie Groupscited by 24
  2. 2024Equivariance via Minimal Frame Averaging for More Symmetries and Efficiencycited by 19
  3. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  4. 2024Unitary convolutions for learning on graphs and groupscited by 8
  5. 2025Achieving Approximate Symmetry Is Exponentially Easier than Exact Symmetrycited by 7
  6. 2025Learning with Exact Invariances in Polynomial Timecited by 6
  7. 2024Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginalscited by 5
  8. 2026Data Augmentation: A Fourier Analysis Perspectivecited by 4
  9. 2026Efficient Learning and Symmetry Discovery under Exact Invariancescited by 3
  10. 2025Performance Heterogeneity in Graph Neural Networks: Lessons for Architecture Design and Preprocessingcited by 2
  11. 2025Towards Non-Euclidean Foundation Models: Advancing AI Beyond Euclidean Frameworkscited by 1
  12. 2026Sparse Data Augmentation for Optimization with Provable Guaranteescited by 1
1 more
  1. 2026Towards Distillation Guarantees under Algorithmic Alignment for Combinatorial Optimizationcited by 0