CoChat
Sign Up
Cited by 1Neural Networks and ApplicationsStochastic Gradient Optimization TechniquesMachine Learning and Algorithms

On the Non-Universality of Deep Learning: Quantifying the Cost of Symmetry

Open access
Abbe, Emmanuel, Boix-Adsera, Enric·2022·Advances in Neural Information Processing Systems 35
DOI 10.52202/068431-1250
Open this paper in CoChat — free accountOpen PDF

Abstract

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

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.52202/068431-1250

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Symmetries of learners have been used in the past to construct similar lower bounds in the statistical setting.

    “Unsurprisingly, symmetries of learners have been used in the past to construct similar lower bounds in the statistical setting (e.g., Malach and Shalev-Shwartz, 2021; Abbe and Boix-Adserà, 2022; Abbe et al., 2022)”

    From Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence (2025) · cites this paper as Abbe and Boix-Adserà, 2022

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 52

  1. [ABB + 21] E. Abbe, E. Boix-Adsera, M. S. Brennan, G. Bresler, and D. Nagaraj. The staircase property: How hierarchical structure can guide deep learning. Advances in Neural Information Processing Systems , 34:26989-27002, 2021.
  2. [ABM22] E. Abbe, E. Boix-Adsera, and T. Misiakiewicz. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. arXiv preprint arXiv:2202.08658 , 2022. · arXiv
  3. [ACHM22] E. Abbe, E. Cornacchia, J. Hązła, and C. Marquis. An initial alignment between neural network and target is needed for gradient descent to learn. arXiv preprint arXiv:2202.12846 , 2022. · arXiv
  4. [AKM + 21] E. Abbe, P. Kamath, E. Malach, C. Sandon, and N. Srebro. On the power of differentiable learning versus PAC and SQ learning. In Advances in Neural Information Processing Systems , volume 34, 2021.
  5. [AL19] Z. Allen-Zhu and Y. Li. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems , 32, 2019.
  6. [AL20] Z. Allen-Zhu and Y. Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04413 , 2020. · arXiv
  7. [Ale03] M. Alekhnovich. More on average case vs approximation complexity. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. , pages 298-307. IEEE, 2003.
  8. [AS20] E. Abbe and C. Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.02992 , 2020. · arXiv
  9. [BAO + 20] A. Bogatskiy, B. Anderson, J. Offermann, M. Roussi, D. Miller, and R. Kondor. Lorentz group equivariant neural network for particle physics. In International Conference on Machine Learning , pages 992-1002. PMLR, 2020.
  10. [Bar93] A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory , 39(3):930-945, 1993.
  11. [BBCV21] M. M. Bronstein, J. Bruna, T. Cohen, and P. Veli c ković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478 , 2021. · arXiv
  12. [BBH18] M. Brennan, G. Bresler, and W. Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory , pages 48-166. PMLR, 2018.
  13. [BCB14] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473 , 2014. · arXiv
  14. [BF02] N. H. Bshouty and V. Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research , 2(Feb):359-395, 2002.
  15. [BIK90] S. Ben-David, A. Itai, and E. Kushilevitz. Learning by distances. In COLT , pages 232-245, 1990.
  16. [BKW03] A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM) , 50(4):506-519, 2003.
  17. [BVB21] A. Bietti, L. Venturi, and J. Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems , 34, 2021.
  18. [BZSL13] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203 , 2013. · arXiv
  19. [Ele21] B. Elesedy. Provably strict generalisation benefit for invariance in kernel methods. Advances in Neural Information Processing Systems , 34, 2021.
  20. [Ele22] B. Elesedy. Group symmetry in pac learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning , 2022.
  21. [EZ21] B. Elesedy and S. Zaidi. Provably strict generalisation benefit for equivariant models. In International Conference on Machine Learning , pages 2959-2969. PMLR, 2021.
  22. [GMMM21] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics , 49(2):1029-1054, 2021.
  23. [GMS05] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE international joint conference on neural networks , volume 2, pages 729-734, 2005.
  24. [HSSV21] D. Hsu, C. Sanford, R. A. Servedio, and E. Vlatakis-Gkaragkounis. On the approximation power of two-layer networks of random relus. arXiv preprint arXiv:2102.02336 , 2021. · arXiv
  25. [HZRS16] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition , pages 770-778, 2016.
  26. [JGH18] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems , 31, 2018.
  27. [Kea98] M. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) , 45(6):983-1006, 1998.
  28. [KMS20] P. Kamath, O. Montasser, and N. Srebro. Approximate is good enough: Probabilistic variants of dimensional and margin complexity. In Conference on Learning Theory , pages 2236-2262. PMLR, 2020.
  29. [Kna96] A. W. Knapp. Lie groups beyond an introduction , volume 140. Springer, 1996.
  30. [KSH12] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems , 25, 2012.
  31. [LB + 95] Y. LeCun, Y. Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks , 3361(10):1995, 1995.
  32. [LCC + 22] Y. Li, D. Choi, J. Chung, N. Kushman, J. Schrittwieser, R. Leblond, T. Eccles, J. Keeling, F. Gimeno, A. D. Lago, et al. Competition-level code generation with alphacode. arXiv preprint arXiv:2203.07814 , 2022. · arXiv
  33. [LKF10] Y. LeCun, K. Kavukcuoglu, and C. Farabet. Convolutional networks and applications in vision. In Proceedings of 2010 IEEE international symposium on circuits and systems , pages 253-256. IEEE, 2010.
  34. [LZA21] Z. Li, Y. Zhang, and S. Arora. Why are convolutional nets more sample-efficient than fullyconnected nets? In International Conference on Learning Representations , 2021.
  35. [Mis22] T. Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204.10425 , 2022. · arXiv
  36. [MM21] T. Misiakiewicz and S. Mei. Learning with convolution and pooling operations in kernel methods. arXiv preprint arXiv:2111.08308 , 2021. · arXiv
  37. [MMM21] S. Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory , pages 3351-3418. PMLR, 2021.
  38. [MS20] E. Malach and S. Shalev-Shwartz. Computational separation between convolutional and fullyconnected networks. arXiv preprint arXiv:2010.01369 , 2020. · arXiv
  39. [Ng04] A. Y. Ng. Feature selection, l 1 vs. l 2 regularization, and rotational invariance. In Proceedings of the twenty-first international conference on Machine learning , page 78, 2004.
  40. [NY21] I. Nachum and A. Yehudayoff. On symmetry and initialization for neural networks. In Latin American Symposium on Theoretical Informatics , pages 401-412. Springer, 2021.
  41. [O'D14] R. O'Donnell. Analysis of boolean functions . Cambridge University Press, 2014.
  42. [Rey20] L. Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557 , 2020. · arXiv
  43. [Ser77] J.-P. Serre. Linear representations of finite groups , volume 42. Springer, 1977.
  44. [Sha18] O. Shamir. Distribution-specific hardness of learning neural networks. The Journal of Machine Learning Research , 19(1):1135-1163, 2018.
  45. [SHS + 18] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science , 362(6419):1140-1144, 2018.
  46. [SNPP19] S. Schubert, P. Neubert, J. Pöschmann, and P. Protzel. Circular convolutional neural networks for panoramic images and laser data. In 2019 IEEE Intelligent Vehicles Symposium (IV) , pages 653-660. IEEE, 2019.
  47. [SSS17] S. Shalev-Shwartz, O. Shamir, and S. Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning , pages 3067-3075. PMLR, 2017.
  48. [Sta90] D. Stanton. An introduction to group representations and orthogonal polynomials. In Orthogonal Polynomials , pages 419-433. Springer, 1990.
  49. [Val84] L. G. Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134-1142, 1984.
  50. [VSP + 17] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems , 30, 2017.
  51. [WLLM19] C. Wei, J. D. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems , 32, 2019.
  52. [ZHSJ19] J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.11881 , 2019. · arXiv

Cited by

Sorted by citations

Authors
Abbe, E., & Boix-Adsera, E.
ORCID
Abbe, Emmanuel
Venue
Advances in Neural Information Processing Systems 35
Publisher
Neural Information Processing Systems Foundation, Inc. (NeurIPS)
Published
2022
Pages
17188-17201
ISSN
1049-5258 (ISSN-L)
DOI
10.52202/068431-1250
OpenAlex
W7133185724
Cited by
1
References
0
Citations by year
2026: 1
FWCI
0.00
Type
conference paper
Language
en
Open access
Locations
  • neural information processing systems (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Infoscience (Ecole Polytechnique Fédérale de Lausanne) (submittedVersion, cc-by-nc-nd)
  • arXiv (Cornell University)
Funders
  • National Science Foundation
  • École Polytechnique Fédérale de Lausanne
  • Simons Institute for the Theory of Computing, University of California Berkeley
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Keywords
symmetry, deep neural network, expressivity

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review