Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

Traditional approximation theory often evaluates the efficiency of numerical methods by the number of parameters (degrees of freedom) required to achieve a target accuracy. In high-dimensional spaces, this leads to the well-known "curse of dimensionality," where the required parameters grow exponentially with the dimension. Recent literature has suggested that neural networks might bypass this limitation, exhibiting dimension-independent rates or superconvergence. This paper challenges that interpretation by shifting the focus from parameter counts to computational bit complexity.

The authors introduce a framework based on metric entropy, which quantifies the minimum number of bits required to represent a function within a specific class to a given accuracy. By treating approximation as a digital encoding problem, the authors show that metric entropy provides a scheme-independent measure of complexity. This approach allows for a direct comparison between classical methods (such as polynomial approximation and finite elements) and neural networks on equal footing.

The study finds that when neural networks are evaluated under a fixed bit budget, their apparent advantages—such as superconvergence in Sobolev spaces—often stem from differences in the underlying function class complexity rather than intrinsic architectural superiority. The authors argue that the "curse of dimensionality" is better understood as a "curse of bit complexity." Because neural networks often require more bits to represent their parameters compared to classical basis functions for the same target class, their performance is constrained by the same fundamental information-theoretic limits that govern all approximation methods.