🤖 machine learning

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

This paper argues that when approximation efficiency is evaluated through computational bit complexity rather than parameter count, no method fundamentally surpasses the intrinsic limits set by metric entropy, revealing that perceived neural network advantages often stem from differences in function class complexity rather than architectural superiority, and reframing the traditional "curse of dimensionality" as a more fundamental "curse of bit complexity."

Original authors: Tong Mao, Jinchao Xu

Published 2026-08-04

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Tong Mao, Jinchao Xu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe a complex, high-dimensional object—like a swirling galaxy or a multi-layered cake—to a friend who can only understand simple, flat drawings. In the world of computer science and mathematics, this is known as a "high-dimensional approximation problem." For decades, scientists have been fighting a notorious enemy called the "curse of dimensionality." The name sounds scary, but the idea is simple: as the number of variables (or dimensions) in a problem grows, the amount of information needed to describe it accurately explodes. It's like trying to paint a picture of a 100-dimensional object; the number of brushstrokes required seems to grow so fast that it becomes impossible to finish the job.

For a long time, the standard way to measure how well a computer solves these problems was by counting "parameters." Think of parameters as the knobs, dials, and settings on a machine. If a method uses fewer knobs to get the same result, it's considered more efficient. Recently, neural networks (the AI systems that power things like image recognition and language models) have been celebrated because they seem to break this curse. They appear to solve high-dimensional problems with a number of knobs that doesn't explode as the dimensions grow, leading many to believe they have found a magic key to unlock the most complex problems in science.

However, there is a catch that often gets overlooked in the excitement. In the real world, computers don't store numbers with infinite precision; they store them as strings of 0s and 1s, or "bits." Every knob on that machine needs to be encoded into a specific number of bits to be stored and calculated. This paper asks a fundamental question: If we stop counting just the knobs and start counting the actual bits of information required to store them, do neural networks still look like magic? The authors, Tong Mao and Jinchao Xu, dive deep into this question, using a concept called "metric entropy" (which essentially measures the minimum amount of information needed to describe a shape or function) to see if neural networks truly beat the curse or if they are just hiding the cost in a different way.

The Great Bit-Counting Heist

The authors of this paper, Tong Mao and Jinchao Xu, decided to put on their detective hats and look at the "curse of dimensionality" from a new angle. Instead of just counting how many parameters (knobs) a method uses, they asked: "How many bits of memory does it actually take to store those knobs and get a good answer?"

To understand their investigation, imagine you are trying to describe a smooth, rolling hill to a robot.

The Old Way (Counting Parameters): You might say, "I need 100 points to describe this hill." If you switch to a new method, like a neural network, and say, "I only need 10 points," you feel like you've won. You've beaten the curse!
The New Way (Counting Bits): But wait. What if those 10 points are incredibly sensitive? What if to describe the shape of the hill accurately, each of those 10 points needs to be stored with extreme precision—like needing 1,000 bits for each point? Suddenly, you aren't using 10 units of information; you are using 10,000. Meanwhile, the old method used 100 points, but each only needed 10 bits. In the end, the "old" method actually used fewer total bits.

The paper argues that for a long time, we've been fooled by the "parameter count." We saw neural networks using fewer knobs and assumed they were more efficient. But when the authors measured the efficiency in terms of bits (the actual currency of computation), the story changed.

The "Magic" That Isn't So Magic

The researchers looked at two main types of "magic" that neural networks were famous for:

Dimension-Independent Rates: Some studies claimed that neural networks could approximate certain complex functions without their performance getting worse as the number of dimensions increased. It sounded like they had found a way to ignore the size of the problem entirely.
Superconvergence: This is the idea that deep neural networks (networks with many layers) can approximate smooth functions much faster than traditional methods like polynomials or finite elements. It looked like they were zooming past the competition.

The authors' investigation revealed that these "superpowers" are largely an illusion created by how we measure things.

When they analyzed the metric entropy—a fancy term for the intrinsic complexity of the function class being approximated—they found that the functions neural networks are good at approximating (like those in "Barron spaces") are actually just simpler than the functions traditional methods struggle with. It's not that the neural network is a better artist; it's that the painting it's asked to copy is less detailed than the one the traditional artist was trying to copy. The "dimension-independent" speed isn't because the network is special; it's because the target was easy to begin with.

The Deep Network Trap

The most surprising finding concerns deep neural networks. These are the networks with many layers that have been getting all the hype. The paper shows that while deep networks can indeed achieve a faster error rate when measured by the number of parameters (the "knobs"), this speed comes with a hidden tax.

Because deep networks are so complex and sensitive, the numbers inside them (the weights and biases) need to be stored with much higher precision to avoid errors. The authors proved that the number of bits required to store these parameters grows explosively as the network gets deeper.

Think of it like this: A shallow network is like a sturdy wooden bridge. It takes a lot of planks (parameters), but each plank is easy to measure and store. A deep network is like a glass bridge. It uses fewer planks, but each plank is so fragile and precise that you need a laser scanner to measure it. If you try to build the glass bridge with a standard tape measure (finite precision), it collapses.

The paper demonstrates that when you count the total bits needed to build that glass bridge, the "efficiency" vanishes. The extra bits needed to keep the deep network stable cancel out the advantage of having fewer parameters. In fact, for many standard problems, deep networks end up requiring just as many bits, or even more, than classical methods like polynomials or finite elements.

The Verdict: It's a Bit of a Curse

So, do neural networks beat the curse of dimensionality? According to Mao and Xu, the answer is no, at least not in the way we thought.

The "curse" isn't really about the number of dimensions. It's about the bit complexity. The fundamental limit of how well you can approximate a function is determined by how much information (bits) that function actually contains. This is governed by "metric entropy."

If a function is complex, it requires many bits to describe, no matter what tool you use.
If a function is simple, it requires fewer bits.

Neural networks don't change the rules of the game; they just change the way we count the score. When we look at the game through the lens of bits rather than parameters, the "superiority" of neural networks often disappears. The apparent advantages, like dimension-independent rates or superconvergence, are often just because the neural networks are being tested on function classes that are inherently less complex (have lower metric entropy) than the ones traditional methods are tested on.

Why This Matters

This paper doesn't say neural networks are useless. It says we need to be smarter about how we evaluate them. In the real world, computers have finite memory. They can't store infinite precision. If a method looks great on paper because it uses fewer parameters, but requires a massive amount of memory to store those parameters accurately, it might not be the best choice for a real-world application.

The authors suggest that the "curse of dimensionality" is actually a "curse of bit complexity." The true limit isn't how many dimensions you have, but how many bits you need to describe the problem. By shifting our focus from counting knobs to counting bits, we get a much clearer, more realistic picture of what these powerful tools can and cannot do. It's a reminder that in the world of high-dimensional math, the devil is always in the details—and those details are measured in bits.

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

1. Problem Statement

High-dimensional approximation is a central challenge in scientific computing and machine learning, traditionally hindered by the "curse of dimensionality." In classical approximation theory, the number of degrees of freedom ( $N$ ) required to achieve a prescribed accuracy often grows exponentially with the dimension ( $d$ ). For instance, in Sobolev spaces $H^r([0,1]^d)$ , the optimal convergence rate for classical methods (polynomials, finite elements) scales as $O(N^{-r/d})$ , where the exponent deteriorates as $d$ increases.

Recent literature suggests that neural networks (both shallow and deep) may overcome this curse, exhibiting dimension-independent rates or "superconvergence" (e.g., achieving $O(N^{-2r/d})$ for deep ReLU networks in Sobolev spaces). However, these results are typically measured in terms of the number of parameters ( $N$ ).

The paper identifies a critical gap: practical computation operates under finite precision. Parameters must be encoded using a finite number of bits. The authors argue that measuring efficiency solely by parameter count is misleading because it ignores the bit-complexity required to represent those parameters with sufficient accuracy. The central problem is to re-evaluate approximation rates through the lens of computational bit complexity and metric entropy to determine if neural networks truly possess an intrinsic advantage over classical methods.

2. Methodology

The authors develop a unified approximation framework based on binary encoding and metric entropy.

2.1 Metric Entropy and Bit-Complexity

The core theoretical tool is the metric entropy (or dyadic entropy number) $\epsilon_m(K)_X$ , defined as the minimal radius $\epsilon$ such that a compact set $K$ in a Banach space $X$ can be covered by $2^m$ balls of radius $\epsilon$ .

Proposition 2 establishes that $\epsilon_m(K)_X$ is quantitatively equivalent to the optimal approximation error achievable with $m$ bits. Thus, metric entropy characterizes the intrinsic information content (bit-complexity) of a function class.
The paper distinguishes between parameter-based rates (convergence in terms of $N$ ) and bit-based rates (convergence in terms of $N_b$ , the total number of bits).

2.2 Encoding Analysis

The methodology involves analyzing how classical and neural network approximations translate into finite-bit representations:

Parameter Representation: An approximation method maps a function $f$ to a set of parameters $\Theta \in \mathbb{R}^N$ .
Quantization: Parameters are quantized to $\tau$ bits each, resulting in a total bit budget $N_b = N\tau$ .
Stability Analysis: The authors analyze the Lipschitz constant (sensitivity) of the reconstruction map $\tilde{S}_N$ . If the reconstruction is highly sensitive to parameter perturbations, a larger $\tau$ (more bits per parameter) is required to maintain a specific error tolerance.
Lower Bounds: Using Lemma 2, the paper derives lower bounds for approximation errors based on the difference between the metric entropy of the target function class and the metric entropy of the approximation class.

3. Key Contributions and Results

3.1 Classical Methods (Polynomials, FEM, Sparse Grids)

The paper analyzes classical methods (polynomial approximation, finite elements, sparse grids) under the bit-complexity framework.

Result: For classical methods approximating Sobolev spaces $H^r$ , the parameter-based rate is $O(N^{-r/d})$ . When converted to bit-based rates, the convergence becomes $O((N_b / \log N_b)^{-r/d})$ .
Suboptimality: The authors show that these methods are generally suboptimal relative to the intrinsic metric entropy limits of the function classes. The metric entropy of $H^r$ decays as $m^{-r/d}$ , but classical methods often fail to achieve this rate when bit constraints are considered, particularly due to the logarithmic overhead in encoding parameters.

3.2 Neural Networks: Shallow and Deep

The paper re-evaluates the performance of neural networks (ReLU and ReLU $^k$ ) on Barron spaces and Sobolev spaces.

Shallow Networks on Barron Spaces:
- Shallow networks achieve parameter-based rates of $O(N^{-1/2 - (2k+1)/2d})$ on Barron spaces.
- Bit-Complexity View: When accounting for bit encoding, the rate remains comparable to the metric entropy of the Barron space. The "dimension-independent" appearance is attributed to the low metric entropy of the Barron space itself, not an architectural superiority. The target class is simply less complex than the Sobolev space.
Deep Networks and Superconvergence:
- Deep ReLU networks have been shown to achieve "superconvergence" rates of $O(N^{-2r/d})$ in Sobolev spaces, seemingly doubling the exponent compared to classical methods.
- Bit-Complexity View: The authors demonstrate that this improvement is an artifact of parameter counting. Lemma 1 proves that the reconstruction map for deep networks exhibits exponential sensitivity to parameter perturbations (Lipschitz constant grows as $(n+1)(W+1)^{n+1}M^{n+1}$ ).
- To maintain the same accuracy, the required precision (bits per parameter) grows polynomially with the network size. Consequently, the bit-based rate for deep networks degrades to $O(N_b^{-2r/3d})$ (or similar, depending on constants), which does not surpass the classical $O(N_b^{-r/d})$ rate. The "superconvergence" is offset by the massive bit cost required for stable finite-precision representation.

3.3 Lower Bounds and Optimality

Using the metric entropy framework, the paper establishes fundamental lower bounds:

No method can fundamentally exceed the approximation order dictated by the metric entropy of the target function class.
Many apparent advantages of neural networks (dimension independence, superconvergence) stem from analyzing function classes with lower intrinsic complexity (e.g., Barron spaces) or from ignoring the bit cost of stability (in the case of deep networks).

4. Significance and Conclusions

The paper concludes that the "curse of dimensionality" is not an intrinsic property of high-dimensional approximation but rather a curse of bit complexity governed by metric entropy.

Reframing the Curse: The fundamental limitation is not the dimension $d$ itself, but the metric entropy of the function class being approximated. If a function class has low metric entropy (like Barron spaces), it can be approximated efficiently regardless of dimension.
Neural Network Limitations: Neural networks do not possess an intrinsic architectural advantage that allows them to bypass the limits set by metric entropy.
- Their success on specific classes (Barron) is due to the low complexity of those classes.
- Their "superconvergence" in deep networks is a parameter-count illusion that vanishes when finite-precision constraints (bit complexity) are applied.
Practical Implication: In practical, finite-precision computation, the bit cost of representing parameters is the true bottleneck. Methods that appear superior in parameter count may be inferior in bit complexity due to instability.

The authors assert that a unified view based on metric entropy and bit complexity provides a more accurate and realistic benchmark for evaluating approximation methods, revealing that traditional classical methods and neural networks are subject to the same fundamental information-theoretic limits.