Classical approximation methods like splines, wavelets, or Fourier series suffer from a fundamental geometric bottleneck: the curse of dimensionality. If you want to approximate a smooth function over a $d$-dimensional space with an accuracy of $\epsilon$, classical methods typically require a number of grid points or basis functions that scales as $O(\epsilon^{-d})$. In a 50-dimensional space, even a coarse grid becomes completely intractable.
Neural networks, however, routinely break this curse. The core intuition behind why they succeed lies in a mathematical loophole similar to Monte Carlo integration.
The Monte Carlo Loophole and Barron Spaces
In Monte Carlo integration, we approximate an integral by averaging random samples. Crucially, the variance (and thus the approximation error) decreases at a rate of $O(1/\sqrt{m})$, where $m$ is the number of samples—regardless of the dimension of the space.
We can view a neural network as a form of Monte Carlo approximation if the target function belongs to a specific class known as a Barron space. Functions in a Barron space can be represented as an integral or expectation over a continuum of "ridge functions" (which look exactly like hidden neurons):
$$f(x) = \int a(\omega) \sigma(\omega \cdot x + b) d\mu(\omega)$$
When a function admits this representation, a shallow neural network with $m$ hidden units is simply a finite, discrete sample of this integral. As shown by Yang et al., the approximation error scales at a rate of $O(1/\sqrt{m})$, completely bypassing the input dimension's complexity, even when mapping from infinite-dimensional functional spaces.
This insight explains why neural networks excel at high-dimensional physical problems. For instance, E et al. demonstrated that solutions to certain high-dimensional partial differential equations (PDEs) naturally inherit this integral structure, allowing networks to approximate them without exponential scaling. Similarly, in generative modeling, Cole et al. proved that constraining the log-relative density of a distribution to a Barron space allows score-based generative models to learn high-dimensional sub-Gaussian distributions efficiently.
Restricting Complexity via Variation Spaces
To guarantee that a network actually finds a solution within these well-behaved spaces during training, we must restrict its complexity. This is achieved through norm constraints and weight decay, which confine the network's optimization path to specific variation spaces (such as Radon $BV^2$).
Parhi et al. demonstrated that shallow ReLU networks trained with weight decay act as nonlinear estimators that achieve near-minimax optimal rates. While traditional linear methods (like kernels) see their performance degrade toward zero in high dimensions, these regularized networks maintain a stable error rate that approaches a constant power of the sample size.
Furthermore, Liu et al. showed that norm-constrained, over-parameterized two-layer networks inhabit function spaces where complexity scales linearly—rather than exponentially—with input dimensions, allowing them to outperform kernel methods using significantly fewer samples. This dimension-independence also scales to complex multi-output tasks; Shenouda et al. proved that the approximation error in vector-valued variation spaces depends primarily on the number of neurons, completely independent of both input and output dimensions. In active learning scenarios, Zhu et al. showed that exploiting Radon $BV^2$ spaces allows ReLU networks to maintain high learning efficiency with fewer labels in high-dimensional settings.
Adaptive Projections and Noise Filtering
Another reason neural networks escape the curse of dimensionality is their ability to perform adaptive representation learning. Instead of treating all dimensions equally, they learn to project high-dimensional data onto low-dimensional subspaces where the target function varies most.
Consider a Single-Index Model (SIM), where a function depends on a high-dimensional input only through a single hidden direction. Bietti et al. proved that shallow networks optimizing via gradient flow can achieve generalization performance independent of the ambient input dimension, as the required capacity scales only with the smoothness of the underlying 1D link function.
This concept traces back to projection-based architectures. Zhao et al. showed that Projection Pursuit Learning Networks bypass the curse of dimensionality by learning their own activation functions from data, shifting the bottleneck from input dimensionality to the complexity of the learned representation itself. Similarly, Hush et al. introduced the Sweeping Hinge Algorithm, demonstrating that constructive architectures using hinging sigmoids achieve error rates scaling inversely with the number of hidden units, independent of the input space dimensionality.
This capacity to isolate relevant structures allows networks to act as powerful noise filters. For example, Zhou et al. proved that deep ReLU networks classifying Gaussian Mixture Models achieve non-asymptotic convergence rates independent of the input dimension, effectively filtering out high-dimensional noise to identify underlying decision boundaries.
Architectural Super-Convergence
While shallow networks provide the foundational intuition for dimension independence, deeper and more specialized architectures can accelerate these convergence rates dramatically.
DeVore et al. observed that deep ReLU networks can achieve "super-convergence" rates far superior to classical wavelets or splines while maintaining consistent error rates regardless of input dimensions, though this power introduces numerical optimization challenges.
To optimize this scaling, Shen et al. designed Floor-Exponential-Step (FLES) networks that achieve approximation rates growing exponentially with network width but only polynomially with the input dimension, mitigating performance degradation in high dimensions. Taking a structural approach, Zhang et al. introduced Nested Networks (NestNets), which replace standard activation functions with recursive sub-networks. By scaling the nesting depth relative to the input dimension, the authors showed that the approximation error rate becomes entirely independent of that dimension, scaling at a constant rate of $O(n^{-1})$.
Finally, Li et al. developed a shallow variant of XNet using basis functions derived from the Cauchy integral formula, achieving near-exponential approximation rates that preserve efficiency and accuracy across wide input scales without slowing down as dimensions increase.
Key Foundational Work
Function Approximation with the Sweeping Hinge Algorithm (1997) — contributed 1 concept elements to this direction.
Some Approximation Properties of Projection Pursuit Learning Networks (1991) — contributed 1 concept elements to this direction.