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

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

## 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 (most cited first, 30 of 43)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss](https://mlsanity.com/paper/2002.04486/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [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)
- [Scaling description of generalization with number of parameters in deep learning](https://mlsanity.com/paper/1901.01608/) (2019)
- [Deep ReLU network approximation of functions on a manifold](https://mlsanity.com/paper/1908.00695/) (2019)
- [Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recovery](https://mlsanity.com/paper/1908.01842/) (2019)
- [Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation](https://mlsanity.com/paper/1905.03684/) (2019)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [The jamming transition as a paradigm to understand the loss landscape of deep neural networks](https://mlsanity.com/paper/1809.09349/) (2018)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [The Barron Space and the Flow-induced Function Spaces for Neural Network Models](https://mlsanity.com/paper/1906.08039/) (2019)
- [Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network](https://mlsanity.com/paper/1909.11274/) (2019)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime](https://mlsanity.com/paper/2006.12297/) (2020)

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

- [Shallow diffusion networks provably learn hidden low-dimensional structure](https://mlsanity.com/paper/2410.11275/) (2024)
- [On the Local Complexity of Linear Regions in Deep ReLU Networks](https://mlsanity.com/paper/2412.18283/) (2024)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)
- [Quantifying uncertainty in climate projections with conformal ensembles](https://mlsanity.com/paper/2408.06642/) (2024)
- [A Framework for Feature Discovery in Intracranial Pressure Monitoring Data Using Neural Network Attention](https://mlsanity.com/paper/2601.07691/) (2026)
- [Hierarchical Compositionality for An Assistive AI Agent](https://mlsanity.com/paper/2608.10330/) (2026)

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