Research map / Learning theory and algorithms / Kernels and regression theory

Position: A Theory of Deep Learning Must Include Compositional Sparsity

ICML 2025 · Learning theory and algorithms › Kernels and regression theory · approach: Generalization theory of deep networks

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.

Position paper arguing that a theory of deep learning must include compositional sparsity, proving that all efficiently Turing-computable functions are compositionally sparse and linking this to approximation, optimization, CoT and open questions.

Problem

Explaining how deep networks avoid the curse of dimensionality in approximation, optimization and generalization for high-dimensional target functions.

Approach

Argues that compositional sparsity (functions expressible as polynomially many constituent functions each depending on a constant number of variables) is shared by all FP-computable functions, so it is the key structural property enabling DNNs to escape the curse of dimensionality; it connects this to chain-of-thought as a decomposition into sparse subproblems.

Key results

• Proves that any efficiently Turing-computable function (FP) is compositionally sparse via a polynomial-size fan-in-2 Boolean circuit construction.
• States that deep networks mimicking the compositional DAG achieve complexity O(d eps^-2) versus O(eps^-d) for shallow networks (cited result).
• Argues autoregressive next-token training with chain-of-thought decomposes hard problems into sparse subproblems, a conjecture not empirically tested.

Limitations

• Mostly relies on cited theorems; the conjecture on chain-of-thought is not empirically validated.
• Equates efficient Turing-computability with FP and uses informal theorem statements.
• Learnability and optimization of general compositionally sparse functions remain open, and worst-case cryptographic hardness applies.

Experimental setup

Builds on: hierarchically local compositional functions Malach autoregressive universality multi-index model

Closest papers by meaning

• How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning (ICLR 2025 · similarity 0.90)
• Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.89)
• Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory (ICLR 2025 · similarity 0.88)
• A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.88)
• Scaling can lead to compositional generalization (NeurIPS 2025 · similarity 0.87)
• Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks (NeurIPS 2025 · similarity 0.87)