Research map / Learning theory and algorithms / Kernels and regression theory
How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a covering-number generalization bound for compositions of shallow ReLU networks (Accordion Networks) via F1-norms and Lipschitz constants, and shows DNNs can learn compositions of Sobolev functions at rates that break the curse of dimensionality, supported by synthetic Matérn-GP experiments.
Problem
Generalization of deep networks is poorly explained by existing norm-based bounds, which are loose and blow up with depth; it is unclear when DNNs can learn compositional functions without the curse of dimensionality.
Approach
Extends F1-norm (Barron-type) shallow-network covering-number bounds to compositions of shallow nets (Accordion Networks, equivalent to rank-constrained FCNNs), giving a complexity measure that is width-independent, linear in depth, and uses Lipschitz constants instead of operator norms; combined with Sobolev approximation this yields rates governed by the largest ratio d/nu across layers.
Key results
- Generalization bound for AccNets depends on F1-norms and Lipschitz constants, is independent of width and grows roughly linearly in depth, with a bound about 10^7 looser than observed error but matching log-log scaling slopes.
- Global minimizers of regularized loss achieve rate O(N^{-2/(2+r_max)}) for compositions of Sobolev functions, avoiding the curse of dimensionality when intermediate dimensions and regularities are favorable.
- Empirical test-error scaling on compositional GP data shows phase transitions depending on whether g or h is harder, consistent with the predicted min{2nu_g/(2nu_g+d_in), 2nu_h/(2nu_h+d_mid)} exponent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use deep networks instead of kernel methods or shallow networks | compositional synthetic tasks · synthetic compositional tasks | test error scaling law | Helped |
| use Lipschitz constants instead of operator norms in the complexity bound | generalization bounds for compositional tasks · synthetic composition of two functions, (2,2) differentiabilities | bound scaling with N | Helped |
Surprising findings
- The theory predicts a fundamental limitation that norm-based bounds cannot yield rates faster than N^{-1/2}, so easy tasks with fast rates are not captured.
- Operator-norm-based bounds can be arbitrarily suboptimal for compositions, while Lipschitz-based bounds remain near optimal.
Limitations
- Global minimum of the regularized loss is assumed to be recoverable, which is hard in general (NP-hard for shallow networks with F1 regularization).
- Approximation proof requires infinite width; finite-width approximation with preserved F1-norm and Lipschitz constant is not proven.
- Bounds are orders of magnitude too loose in absolute value; cannot yield fast rates faster than N^{-1/2}.
Experimental setup
Datasets: synthetic Matérn GP compositions MNIST WESAD
Benchmarks: synthetic Matérn GP composition dataset MNIST WESAD
Metrics: test error log-log scaling slope generalization bound value
Baselines: kernel methods shallow networks fully connected DNNs operator-norm based bounds (2,1)-norm based bounds
Builds on: F1-norm shallow network bounds Barron norm covering number bounds for deep networks Matérn Gaussian processes
Closest papers by meaning
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.90)
- Synergy and Symmetry in Deep Learning: Interactions between the Data, Model, and Inference Algorithm (ICML 2022 · similarity 0.88)
- Symmetries in Overparametrized Neural Networks: A Mean Field View (NeurIPS 2024 · similarity 0.86)
- Nuclear Norm Regularization for Deep Learning (NeurIPS 2024 · similarity 0.86)
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.85)
- Investigating the Overlooked Hessian Structure: From CNNs to LLMs (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.