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

arXiv: https://arxiv.org/abs/2608.01357 · HTML: https://mlsanity.com/paper/2608.01357/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 79 references that are in the map.
- First posted on arXiv 2 Aug 2026.

## Builds on (most cited first, 15 of 15)

- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Optimal approximation of continuous functions by very deep ReLU networks](https://mlsanity.com/paper/1802.03620/) (2018)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [Deep Network Approximation Characterized by Number of Neurons](https://mlsanity.com/paper/1906.05497/) (2019)
- [Optimal Approximation Rate of ReLU Networks in terms of Width and Depth](https://mlsanity.com/paper/2103.00502/) (2021)
- [The phase diagram of approximation rates for deep neural networks](https://mlsanity.com/paper/1906.09477/) (2019)
- [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021)
- [Approximation by Combinations of ReLU and Squared ReLU Ridge Functions with  ℓ1  and  ℓ0  Controls](https://mlsanity.com/paper/1607.07819/) (2016)
- [Neural Network Approximation: Three Hidden Layers Are Enough](https://mlsanity.com/paper/2010.14075/) (2020)
- [Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces](https://mlsanity.com/paper/2211.14400/) (2022)
- [Characterization of the Variation Spaces Corresponding to Shallow Neural Networks](https://mlsanity.com/paper/2106.15002/) (2021)
- [Deep Network Approximation: Achieving Arbitrary Accuracy with Fixed Number of Neurons](https://mlsanity.com/paper/2107.02397/) (2021)
- [Kernel based analysis of massive data](https://mlsanity.com/paper/2003.13226/) (2020)
- [Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks](https://mlsanity.com/paper/2307.15285/) (2023)
- [Expressivity and Approximation Properties of Deep Neural Networks with ReLUk Activation](https://mlsanity.com/paper/2312.16483/) (2023)

## Built on by (most cited first, 1 of 1)

- [Sharp Approximation Rates for Neural Networks with Affine Latent Parameterizations](https://mlsanity.com/paper/2608.31157/) (2026)

## Abstract (arXiv)

Traditional approximation theory measures convergence rates in terms of the number of parameters or degrees of freedom. However, practical computation operates under finite precision: parameters must be encoded using a finite number of bits. Therefore, approximation efficiency should be evaluated in terms of computational bit complexity, which is intrinsically connected to the metric entropy of the underlying function class. In this work, we develop a unified approximation framework based on binary encoding and metric entropy. We analyze classical methods (including polynomial approximation, sparse grids, and finite elements) as well as shallow and deep neural networks, and compare their approximation rates for function classes with comparable metric entropy. We observe that, when evaluated in terms of bits, most classical methods are in general suboptimal relative to the intrinsic limits dictated by metric entropy, while neural network methods may exhibit different behaviors. We show that when complexity is measured in bits rather than parameters, no method fundamentally exceeds the approximation order achieved by classical approaches. Our results also indicate that many seeming advantages of neural networks, including dimension-independent rates and superconvergence phenomena, stem from differences in function class complexity rather than intrinsic architectural superiority. In this sense, the traditional curse of dimensionality can be misleading; the fundamental limitation is instead a curse of bit complexity, governed by metric entropy.