To understand why deep neural networks are so remarkably effective, we must first confront a fundamental mathematical barrier: the curse of dimensionality. If we attempt to learn an arbitrary continuous function $f: \mathbb{R}^d \to \mathbb{R}$ without any structural assumptions, the number of samples or parameters required to achieve a target accuracy $\epsilon$ scales exponentially as $O(\epsilon^{-d})$. For high-dimensional inputs like images or text where $d$ is in the thousands, learning should be statistically impossible.
Yet, deep networks succeed. The core insight explaining this triumph is hierarchical function decomposition (or compositional function modeling). Instead of treating a high-dimensional task as a single monolithic mapping, the underlying target functions of the real world can often be broken down into a nested tree of simpler, low-dimensional sub-functions.
The Geometry of Compositionality
Imagine computing a complex multivariate product or a highly nested interaction. A shallow network with a single hidden layer must approximate the entire global function simultaneously. To do this, it requires an astronomical number of parameters because it tries to represent the function as a massive sum of parts.
In contrast, a deep network can perform recursive local approximation. As explained by Tomaso Poggio et al. in Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review, a hierarchically local compositional function maps variables through a directed acyclic graph (DAG) or tree structure. For instance, a function of eight variables might be decomposed into four functions of two variables, whose outputs are fed into two functions of two variables, and so on. By matching this inherent tree-like architecture of real-world data, deep networks can approximate complex mappings using a parameter count that scales linearly rather than exponentially with the input dimension $d$, as reviewed by Tomaso Poggio et al. in Why and when can deep-but not shallow-networks avoid the curse of dimensionality: A review.
To see this intuition in action, consider a simple product of $n$ variables. David Rolnick demonstrated in The power of deeper networks for expressing natural functions that while a shallow network requires an exponential number of neurons to represent a multivariate product, a deep network can efficiently compute it by calculating products of pairs layer by layer. Similarly, Amit Deshpande et al. showed in Depth separation and weight-width trade-offs for sigmoidal neural networks that depth-3 sigmoidal networks are exponentially more efficient than depth-2 networks because they decompose complex target functions into simpler multivariate and univariate components across multiple layers.
Bypassing the Curse of Dimensionality
When a target function is structured as a hierarchy of low-dimensional operations, the statistical difficulty of the learning problem shifts. The convergence rate of the model no longer depends on the global input dimension $d$, but rather on the maximum dimension of its constituent sub-functions.
This structural assumption provides a rigorous foundation across various domains:
- Nonparametric Regression: Gitta Kutyniok et al. argue in Discussion of: “Nonparametric regression using deep neural networks with ReLU activation function” that representing high-dimensional mappings as a hierarchy of simpler, low-dimensional sub-functions allows deep neural networks to achieve optimal minimax convergence rates.
- Time-Series Analysis: Even when data independence is violated, Mingliang Ma et al. proved in Theoretical analysis of deep neural networks for temporally dependent observations that modeling target functions as compositions of smooth Hölder-class functions allows networks to mitigate the curse of dimensionality for temporally dependent observations.
- Classification: In multiclass classification, Thijs Bos et al. in Convergence rates of deep ReLU networks for multiclass classification and Zihan Zhang et al. in Classification with Deep Neural Networks and Logistic Loss demonstrated that deep ReLU networks trained with logistic loss achieve optimal learning rates by exploiting the composite structure of conditional class probabilities, even when those probabilities are extreme.
- Non-Smooth Function Spaces: Kyeongwon Lee et al. showed in Posterior Contraction for Sparse Neural Networks in Besov Spaces with Intrinsic Dimensionality that sparse Bayesian neural networks achieve optimal posterior contraction rates in complex Besov spaces by leveraging low-dimensional intrinsic compositions.
How Architectures Implement the Decomposition
How exactly do different neural network architectures realize this mathematical decomposition?
To formalize this, Parikshit Ram et al. proposed a framework in How Compositional is a Model? where a compositional function is explicitly defined by a token encoder, a computation DAG, a span processor, and a read-out function. This perspective aligns with classic mathematical theory: Johannes Schmidt-Hieber revisited the Kolmogorov-Arnold representation theorem in The Kolmogorov-Arnold representation theorem revisited, showing that deep architectures are uniquely suited to representing the complex, often non-smooth interior functions of multivariate decompositions through iterative layer-by-layer processing.
In practice, networks assign specific mathematical sub-tasks to different layers. For example, Shirin Jalali et al. proved in Efficient Deep Approximation of GMMs that a network can efficiently approximate Gaussian Mixture Models (GMMs) by isolating quadratic components in the first layer and exponential transformations in the second. Similarly, Zihao Wang et al. showed in Learning Hierarchical Polynomials with Three-Layer Neural Networks that a three-layer architecture with a bottleneck and residual connections naturally separates an inner polynomial feature from the non-linear link function that maps it to the output.
This hierarchical decomposition also fundamentally changes how networks optimize and represent information:
- Residual Networks: Michael Munn et al. mathematically demonstrated in On residual network depth that ResNets can be unraveled into a hierarchical sum of functional paths, acting as an ensemble of increasingly complex sub-models rather than a single monolithic structure.
- Optimization Shortcuts: Chengxi Ye et al. designed architectures based on wavelet multiresolution analysis in Evenly Cascaded Convolutional Networks, showing that persistent feature streams decompose mappings into additive, hierarchical sub-functions that create natural optimization shortcuts for gradients.
- Backward Feature Correction: A key mystery of deep learning is how joint training succeeds over layerwise training. Yuanzhi Li et al. proved in Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning that when a function is represented as a composition of simple, low-degree functions, training via SGD allows higher layers to perform "backward feature correction," fixing errors in lower-level features dynamically.
This structural decomposition isn't limited to standard feedforward networks; it explains the convergence of Transformer encoders (Iryna Gurevych et al. in On the rate of convergence of a classifier based on a Transformer encoder), the query complexity bounds of quantum function approximation in Sobolev spaces (Stefan Heinrich in Quantum Approximation II. Sobolev Embeddings), and can even be used recursively to bound the expressive power of decision trees (Jean-Samuel Leboeuf et al. in Decision trees as partitioning machines to characterize their generalization properties).
By breaking a high-dimensional problem into a nested sequence of low-dimensional operations, hierarchical function decomposition provides the fundamental blueprint for why deep architectures can learn the complex structure of our world efficiently.
Key Foundational Work
Quantum Approximation II. Sobolev Embeddings (2003) — contributed 1 concept elements to this direction.
Learning Internal Representations (1995) — contributed 1 concept elements to this direction.