Abstract
This paper investigates the theoretical limits of function reconstruction within the Fourier-analytic Barron space, a function class central to the study of shallow neural networks. By analyzing $L^p$ sampling numbers ($s_m$), the research establishes that functions in this space can be recovered from a finite set of point samples without succumbing to the "curse of dimensionality," provided the error is measured in an $L^p$ norm for $p < \infty$. The study further demonstrates that achieving these dimension-independent rates necessitates non-linear reconstruction methods, as linear algorithms are shown to be fundamentally limited by the dimensionality of the input space.
Introduction
In high-dimensional machine learning, the "curse of dimensionality" typically dictates that the number of samples required to approximate a function grows exponentially with the number of input dimensions ($d$). However, certain function classes—most notably Barron spaces—exhibit properties that allow neural networks to bypass this limitation. While previous research has focused on the approximation capabilities of neural networks (how well a network can represent a function), this paper addresses the sampling complexity: the fundamental limit of how accurately a function can be reconstructed using $m$ optimal point samples and an optimal reconstruction algorithm.
Problem Formulation
The study focuses on the Fourier-analytic Barron space, where functions are represented as integrals of plane waves. The central object of study is the $m$-th sampling number, $s_m$, defined as the worst-case reconstruction error over the unit ball of the Barron space:
$$s_m(L^p) = \inf_{\{x_1, \dots, x_m\}} \inf_{\phi} \sup_{\|f\|_{\mathcal{B}} \le 1} \|f - \phi(f(x_1), \dots, f(x_m))\|_{L^p}$$
Here, the goal is to determine the decay rate of $s_m$ as $m$ increases, specifically looking for rates where the dependence on $d$ is minimized.
Methodology
The author employs a multi-faceted approach combining harmonic analysis, compressive sensing, and information-based complexity to derive sharp upper and lower bounds.
1. Upper Bounds: Local-to-Global Reconstruction
To establish the possibility of efficient reconstruction, the author utilizes a "patching" strategy. The function is localized to small cubes using smooth cutoff functions. The author proves that these localized versions possess a "nearly sparse" Fourier expansion. By leveraging non-linear recovery techniques from compressive sensing—specifically $\ell^1$-minimization—the localized functions can be reconstructed from a relatively small number of samples. These local reconstructions are then aggregated to form a global approximation.
2. Lower Bounds: The Bump Function Construction
To determine the limits of reconstruction, the author constructs a family of "bump functions" that exist within the Barron space but vanish at all chosen sampling points. If a reconstruction algorithm cannot distinguish a significant "bump" from a zero function, the worst-case error is necessarily high. This construction provides the necessary theoretical floor for the sampling numbers.
3. Linear vs. Non-linear Analysis
A critical distinction is made between linear reconstruction (where the output is a linear combination of the samples, such as in kernel methods) and non-linear reconstruction (such as $\ell^1$-minimization or neural network training). The paper evaluates whether the choice of algorithm type impacts the ability to escape the curse of dimensionality.
Key Insights and Results
Escaping the Curse in $L^p$
The primary finding is that for any $p \in [1, \infty)$, the reconstruction error decays at a rate that includes a dimension-free term. Up to logarithmic factors, the error behaves as:
$$s_m \approx m^{-\left(\frac{1}{\max\{p,2\}} + \frac{\sigma}{d}\right)}$$
As the dimension $d$ becomes very large, the $\sigma/d$ term (representing the traditional curse) vanishes, but the $1/\max\{p,2\}$ term remains. This confirms that learning in Barron spaces is feasible in high dimensions when the error is measured in $L^p$.
The $L^\infty$ Barrier
The research highlights a significant threshold: the curse of dimensionality returns if one demands a small error across the entire domain (the $L^\infty$ norm). In this case, the decay rate is dominated by $m^{-\sigma/d}$, which slows down drastically as $d$ increases. This suggests that while we can learn Barron functions "on average" or in aggregate, uniform reconstruction remains computationally difficult in high dimensions.
The Necessity of Non-linearity
A pivotal result of the paper is the proof that linear reconstruction methods cannot escape the curse of dimensionality. For linear methods, the error is bounded below by $C \cdot m^{-\sigma/d}$, regardless of the $L^p$ norm used. This implies that the "magic" of Barron spaces—and by extension, the success of shallow neural networks—is fundamentally tied to the non-linear nature of the learning process.
Conclusion and Future Work
This work provides a near-complete characterization of the sampling complexity of the Fourier-analytic Barron space. It mathematically validates why non-linear models like neural networks are uniquely suited for high-dimensional tasks where linear methods fail.
However, several avenues for future research remain. The author notes that while the rate is dimension-free, the constants involved may still depend on $d$, potentially requiring very large sample sizes ($m$) before the dimension-free behavior manifests. Additionally, the performance of randomly chosen points—as opposed to the optimally chosen points studied here—remains an open question of high practical relevance to the machine learning community.
Summary updated