mlsanityData to 14 Oct 2026

How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning

arXiv 2407.05664 ↗First posted 8 Jul 2024stat.ML cs.AI cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We show that deep neural networks (DNNs) can efficiently learn any composition of functions with bounded F1-norm, which allows DNNs to break the curse of dimensionality in ways that shallow networks cannot. More specifically, we derive a generalization bound that combines a covering number argument for compositionality, and the F1-norm (or the related Barron norm) for large width adaptivity. We show that the global minimizer of the regularized loss of DNNs can fit for example the composition of two functions f*=hcirc g from a small number of observations, assuming g is smooth/regular and reduces the dimensionality (e.g. g could be the quotient map of the symmetries of f*), so that h can be learned in spite of its low regularity. The measures of regularity we consider is the Sobolev norm with different levels of differentiability, which is well adapted to the F1 norm. We compute scaling laws empirically and observe phase transitions depending on whether g or h is harder to learn, as predicted by our theory.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 43 of its 62 references that are in the map. First posted on arXiv 8 Jul 2024.

Builds on

43 of 62 references.

References · 43

  1. 2020Scaling Laws for Neural Language Modelscited by 6,586
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  4. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  5. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  6. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  7. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  8. 2019Fantastic Generalization Measures and Where to Find Themcited by 513
  9. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  10. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  11. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  12. 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
31 more
  1. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  2. 2017Size-Independent Sample Complexity of Neural Networkscited by 290
  3. 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 268
  4. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  5. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 224
  6. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  7. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  8. 2019Scaling description of generalization with number of parameters in deep learningcited by 83
  9. 2019Deep ReLU network approximation of functions on a manifoldcited by 74
  10. 2019Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recoverycited by 73
  11. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  12. 2023How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Modelcited by 71
  13. 2018The jamming transition as a paradigm to understand the loss landscape of deep neural networkscited by 62
  14. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  15. 2019The Barron Space and the Flow-induced Function Spaces for Neural Network Modelscited by 39
  16. 2019Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural networkcited by 39
  17. 2022Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functionscited by 38
  18. 2020Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regimecited by 35
  19. 2021Generalization bounds via distillationcited by 34
  20. 2023Implicit bias of SGD in L2-regularized linear DNNs: One-way jumps from high to low rankcited by 29
  21. 2023Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoffcited by 17
  22. 2019Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variationcited by 16
  23. 2022The Role of Linear Layers in Nonlinear Interpolating Networkscited by 16
  24. 2022On Rademacher Complexity-based Generalization Bounds for Deep Learningcited by 16
  25. 2015A theoretical framework for calibration in computer models: parametrization, estimation and convergence propertiescited by 12
  26. 2023A path-norm toolkit for modern networks: consequences, promises and challengescited by 10
  27. 2022On Measuring Excess Capacity in Neural Networkscited by 9
  28. 2024Which Frequencies do CNNs Need? Emergent Bottleneck Structure in Feature Learningcited by 9
  29. 2022On the inability of Gaussian process regression to optimally learn compositional functionscited by 7
  30. 2023Norm-based Generalization Bounds for Compositionally Sparse Neural Networkscited by 7
  31. 2023On Size-Independent Sample Complexity of ReLU Networkscited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 2.

6 papers.

  1. 2024Shallow diffusion networks provably learn hidden low-dimensional structurecited by 12
  2. 2024On the Local Complexity of Linear Regions in Deep ReLU Networkscited by 9
  3. 2025Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNetscited by 5
  4. 2024Quantifying uncertainty in climate projections with conformal ensemblescited by 2
  5. 2026A Framework for Feature Discovery in Intracranial Pressure Monitoring Data Using Neural Network Attentioncited by 0
  6. 2026Hierarchical Compositionality for An Assistive AI Agentcited by 0