mlsanityData to 14 Oct 2026

Position: A Theory of Deep Learning Must Include Compositional Sparsity

arXiv 2507.02550 ↗First posted 3 Jul 2025cs.LG cs.AIcited by 14

Not on the map. Why?

Abstract (arXiv)

Overparametrized Deep Neural Networks (DNNs) have demonstrated remarkable success in a wide variety of domains too high-dimensional for classical shallow networks subject to the curse of dimensionality. However, open questions about fundamental principles, that govern the learning dynamics of DNNs, remain. In this position paper we argue that it is the ability of DNNs to exploit the compositionally sparse structure of the target function driving their success. As such, DNNs can leverage the property that most practically relevant functions can be composed from a small set of constituent functions, each of which relies only on a low-dimensional subset of all inputs. We show that this property is shared by all efficiently Turing-computable functions and is therefore highly likely present in all current learning problems. While some promising theoretical insights on questions concerned with approximation and generalization exist in the setting of compositionally sparse functions, several important questions on the learnability and optimization of DNNs remain. Completing the picture of the role of compositional sparsity in deep learning is essential to a comprehensive theory of artificial, and even general, intelligence.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 32 of its 70 references that are in the map. First posted on arXiv 3 Jul 2025.

Builds on

32 of 70 references.

References · 32

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,599
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  6. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  7. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
  8. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  9. 2022Transformers Learn Shortcuts to Automatacited by 268
  10. 2019Analyzing the Structure of Attention in a Transformer Language Modelcited by 243
  11. 2016Deep Learning without Poor Local Minimacited by 234
  12. 2016Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Reviewcited by 155
20 more
  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  2. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  3. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  4. 2023How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Modelcited by 71
  5. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  6. 2019Superposition of many models into onecited by 64
  7. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  8. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  9. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 46
  10. 2022Characterizing Intrinsic Compositionality in Transformers with Tree Projectionscited by 41
  11. 2023The Impact of Depth on Compositional Generalization in Transformer Language Modelscited by 38
  12. 2023Symmetry Induces Structure and Constraint of Learningcited by 25
  13. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  14. 2024How Sparse Attention Approximates Exact Attention? Your Attention is Naturally nC-Sparsecited by 17
  15. 2022Learning Invariant Weights in Neural Networkscited by 16
  16. 2025Survey on Algorithms for multi-index modelscited by 15
  17. 2024How Diffusion Models Learn to Factorize and Composecited by 13
  18. 2023Fast Feedforward Networkscited by 11
  19. 2024How Neural Networks Learn the Support is an Implicit Regularization Effect of SGDcited by 8
  20. 2024On the Power of Decision Trees in Auto-Regressive Language Modelingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 11.

14 papers.

Sort:

By area:

  1. 2025Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNetscited by 5
  2. 2026Towards Worst-Case Guarantees with Scale-Aware Interpretabilitycited by 3
  3. 2026Learning Sparse Compositional Functions with Norm-Constrained Neural Networkscited by 3
  4. 2025The Advantage of Fine-Grained Trainingcited by 1
  5. 2025A Compositional Kernel Model for Feature Learningcited by 1
  6. 2026A Deep Risk Estimator for Known Operator Learningcited by 1
  7. 2026From Mechanistic to Compositional Interpretabilitycited by 1
  8. 2026Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximationcited by 1
  9. 2026Tool Use Reduces Depth-Induced Collapse in OOD Reasoningcited by 0
  10. 2026Compositional Sparsity as an Inductive Bias for Neural Architecture Designcited by 0
  11. 2026Compositionality Emerges in a Narrow Depth-Connectivity Regime: Architecture Constraints and Solution Manifoldscited by 0
  12. 2026Hierarchical Compositionality for An Assistive AI Agentcited by 0
2 more
  1. 2026An Investigation of the NeurIPS and ICML 2025 Position Trackscited by 0
  2. 2026Transfer Learning in Nonparametric Regression with Deep ReLU Networkscited by 0