In classical numerical analysis, approximating a function in high dimensions is a losing battle. If you want to approximate a smooth function with an error $\epsilon$ in $d$ dimensions using traditional methods like splines or polynomials, the number of parameters required typically scales as $O(\epsilon^{-d/s})$, where $s$ is the smoothness. As $d$ increases, this "Curse of Dimensionality" (CoD) makes high-dimensional tasks—like image recognition or physical simulations—computationally impossible.
Yet, deep neural networks routinely solve these problems. A growing body of theoretical research explains this success not as a lucky break, but as a fundamental property of neural architectures that exploit specific structures in data to bypass the exponential wall.
From Sobolev to Barron Spaces
The first step in understanding why neural networks work is realizing that they don't operate in the same "function spaces" as classical methods. Traditional methods often assume functions belong to Sobolev spaces, which are defined by their derivatives. In these spaces, the CoD is mathematically unavoidable.
However, as Weinan E, Chao Ma, and Lei Wu argue in Barron Spaces and the Compositional Function Spaces for Neural Network Models, neural networks are better understood through Barron spaces. Unlike Sobolev spaces, which require a fixed grid of basis functions, Barron spaces are defined by functions that can be represented as an integral of simple "ridge functions" (like a single neuron).
Because neural networks can adaptively choose the "directions" of these ridge functions, they can approximate functions in Barron spaces with an error rate that is independent of the dimension $d$. This shift from fixed bases to adaptive bases is why Jonathan W. Siegel and Jinchao Xu found that approximation rates for neural networks remain efficient across a wide variety of activation functions.
Compositionality and the Power of Depth
If Barron spaces explain why shallow networks can sometimes work, compositionality explains why deep networks are superior. Many real-world functions are hierarchical: an image is made of parts, which are made of edges.
Tomaso Poggio, Hrushikesh N. Mhaskar, and Lorenzo Rosasco demonstrate in Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review that deep networks can mirror this hierarchical structure. By decomposing a high-dimensional function into a sequence of low-dimensional compositions, deep networks require exponentially fewer parameters than shallow ones. While a shallow network might need $O(2^d)$ neurons to learn a compositional function, a deep network can achieve the same result with $O(d)$ parameters.
This efficiency is further refined in architectures like ResNets. Chenghao Liu and Minghua Chen show in Characterizing ResNet's Universal Approximation Capability that ResNets reach the theoretical lower bound for optimal approximation, using a factor of $d$ fewer parameters than standard feedforward networks.
Exploiting the Manifold Hypothesis
Another reason the curse is broken is that high-dimensional data often isn't actually high-dimensional. It usually sits on a low-dimensional "manifold" embedded within the high-dimensional space.
In Deep ReLU network approximation of functions on a manifold, Johannes Schmidt-Hieber proves that deep ReLU networks can approximate functions at a rate determined by the intrinsic dimension ($d^*$) of the manifold, rather than the ambient dimension ($d$). If you are classifying images of faces, the network only needs to "pay" for the degrees of freedom in a face (pose, lighting, expression), not the millions of pixels in the image.
Specialized Mechanisms for Complex Tasks
Beyond standard architectures, researchers are finding that specific mechanisms can "soften" the curse in even more difficult domains:
- Mixture of Experts (MoE): Anastasis Kratsios and colleagues have shown that MoE architectures soften the curse of dimensionality in operator learning by distributing complexity across experts, allowing per-expert parameters to scale linearly with accuracy.
- Novel Activations: Yuling Jiao and Xiliang Lu introduced ReLU-Sine-Exponential activations, proving they can break the curse for Hölder continuous functions by combining the localizing power of ReLU with the oscillatory efficiency of Sines.
- Quantum Circuits: In the quantum realm, Qiuhao Chen and Xin Wang demonstrate that Parameterized Quantum Circuits can be exponentially smaller than classical networks when approximating smooth multivariate functions.
The Frontier: Operator Learning
The most recent challenge is Operator Learning—learning mappings between infinite-dimensional function spaces (e.g., mapping a force field to a fluid flow). While Andrew M. Stuart and Samuel Lanthaler proved that learning general smooth operators still suffers from a curse of complexity, they also showed that physics-informed architectures like HJ-Net can defeat it by leveraging the underlying structure of the equations they solve.
By moving from rigid, grid-based approximation to adaptive, compositional, and manifold-aware architectures, deep learning has turned the "curse" of high dimensions into a manageable engineering problem.