Position: A Theory of Deep Learning Must Include Compositional Sparsity

Aug 6, 2026

Upload by Aria

Overparametrized deep neural networks (DNNs) succeed in high-dimensional domains where classical shallow models struggle with the curse of dimensionality, yet core principles governing their learning dynamics remain unclear. This position paper argues that success is driven by compositional sparsity: target functions can be built from a small set of constituent functions, each depending only on low-dimensional input subsets. The property is shown to hold for all efficiently Turing-computable functions and is likely present in current learning problems; significant open questions persist for learnability and optimization, motivating a more complete theory of deep learning and intelligence.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

AccessFree to download

Introduction

Approximation, Optimization, and Generalization

Compositional sparsity and the curse of dimensionality

POLITECNICO DI TORINO Repository ISTITUZIONALE Position: A Theory of Deep Learning Must Include Compositional Sparsity Original Position: A Theory of Deep Learning Must Include Compositional Sparsity / Danhofer, David A. ; D'Ascenzo, Davide; Dubach, Rafael; Poggio, Tomaso. -ELETTRONICO. -267:(2025), pp. 81199-81210. ( Forty-second International Conference on Machine Learning Position Vancouver (CAN) July 13th-19th, 2025) . Availability: This version is available at: 11583/3001665 since: 2025-10-24T12:01:30Z Publisher: PMLR Published DOI: Terms of use: This article is made available under terms and conditions as specified in the corresponding bibliographic description in the repository Publisher copyright (Article begins on next page) 21 February 2026 Position: A Theory of Deep Learning Must Include Compositional Sparsity David A. Danhofer * 1 2 Davide D’Ascenzo * 1 3 4 Rafael Dubach * 1 5 Tomaso Poggio * 1 Abstract 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. 1. Introduction Deep Neural Networks (DNNs) have achieved remarkable breakthroughs across numerous domains, including computer vision, playing games (Silver et al., 2016a), protein structure prediction (Jumper et al., 2021 ; Abramsonet al., 2024), natural language usage, and complex reasoning (Romera-Paredes et al., 2023 ; Trinh et al., 2024 ; *Equal contribution 1 Center for Brains, Minds and Machines (CBMM), MIT, Cambridge, MA, USA 2ETH Zurich, Zurich, Switzerland 3Politecnico di Torino, Torino, Italy 4University of Milan, Milan, Italy 5University of Zurich, Zurich, Switzerland. Correspondence to: Davide D’Ascenzo <[davide.dascenzo@unimi.it](davide.dascenzo@unimi.it) >. Proceedings of the 42 nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025 . Copyright 2025 by the author(s) . DeepSeek-AI et al., 2025) . Despite their rapidly growing set of achievements, our understanding of DNNs still lags behind their empirical success. Without deeper theoretical insights, it remains unclear why certain architectures scale so well to high-dimensional tasks, or how to pinpoint the limits of Deep Learning (DL) paradigms. Historically, many attempts to build intelligent systems relied on logical or rule-based approaches (Newell & Simon, 1976 ; Hayes-Roth et al., 1983) . In contrast, the rise of DNNs from around 2012 onward ushered in learning-based architectures that surpass traditional algorithms in numerous domains. For several years, the focus has been on pushing performance boundaries: from high-dimensional image recognition (AlexNet (Krizhevsky et al., 2012), ResNet (He et al., 2015)) to playing strategic games (AlphaGo (Silver et al., 2016b), AlphaZero (Silver et al., 2018)) . More recently, Large Language Models (LLMs) such as the GPT

FAQs

What key principle does the paper propose for why deep neural networks work well?

It proposes that DNN success is driven by compositional sparsity in the target function, enabling efficient representation, learning, and generalization in high dimensions.

What does compositional sparsity mean in this context?

Most relevant functions can be composed from a small set of constituent functions, where each constituent relies only on a low-dimensional subset of all inputs.

Which open theoretical questions remain despite the compositional sparsity explanation?

The paper notes unresolved issues about learnability and optimization of DNNs, even though compositional sparsity helps explain approximation and generalization.

Aug 6, 2026

Upload by Aria