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

• URL: http://arxiv.org/abs/2608.01357v1
• Date: Sun, 02 Aug 2026 16:20:19 GMT
• Title: Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View
• Abstract summary: We develop a unified approximation framework based on binary encoding and metric entropy.<n>We show that when complexity is measured in bits rather than parameters, no method fundamentally exceeds the approximation order achieved by classical approaches.
• Score: 3.8969433233965205
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation [15.78691543310587]
  We show that neural networks should be viewed as flexible basis functions, and as models of computation.<n>We show that any definable NN model satisfying a natural parallelization condition is a universal approximator if and only if it contains a non-affine nonlinearity.<n>The scope of our theory is illustrated by deducing universal approximation guarantees for continuous functions, minimax-optimal approximation guarantees for Besov classes, logarithmic-error complexity for holomorphic functions, and by showing that NNs can emulate numerical algorithms such as Newton-Raphson root finding and power computation.
  arXiv  Detail & Related papers  (2026-06-25T07:34:20Z)
• The Error of Deep Operator Networks Is the Sum of Its Parts: Branch-Trunk and Mode Error Decompositions [45.88028371034407]
  Operator learning has the potential to strongly impact scientific computing by learning solution operators for differential equations.<n>Despite proven universal approximation properties, deep operator networks (DeepONets) often exhibit limited accuracy and generalization in practice.<n>This work analyzes performance limitations of the classical DeepONet architecture.
  arXiv  Detail & Related papers  (2026-02-25T13:38:08Z)
• A Scalable Quantum Neural Network for Approximate SRBB-Based Unitary Synthesis [1.3108652488669736]
  A scalable quantum neural network is introduced as a means to approximate any unitary evolution.<n>The SRBB-based synthesis algorithm is also tested on real hardware.
  arXiv  Detail & Related papers  (2024-12-04T07:21:23Z)
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
  We introduce a method to efficiently approximate tensor network contractions using low-rank approximations.<n>The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations.
  arXiv  Detail & Related papers  (2024-06-14T07:13:52Z)
• Structure-preserving neural networks for the regularized entropy-based closure of the Boltzmann moment system [3.437372707846067]
  Main challenge of large-scale numerical simulation of radiation transport is the high memory and computation time requirements. In this work, we derive and investigate a neural network-based approximation to the entropy closure method. Our numerical experiments demonstrate that the method has a much lower memory footprint than traditional methods with competitive times and simulation accuracy.
  arXiv  Detail & Related papers  (2024-04-22T16:16:06Z)
• Guaranteed Approximation Bounds for Mixed-Precision Neural Operators [83.64404557466528]
  We build on intuition that neural operator learning inherently induces an approximation error. We show that our approach reduces GPU memory usage by up to 50% and improves throughput by 58% with little or no reduction in accuracy.
  arXiv  Detail & Related papers  (2023-07-27T17:42:06Z)
• A comparison of rational and neural network based approximations [0.0]
  We compare the efficiency of function approximation using rational approximation, neural network and their combinations. It was found that rational approximation is superior to neural network based approaches with the same number of decision variables.
  arXiv  Detail & Related papers  (2023-03-08T08:31:06Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• A Functional Perspective on Learning Symmetric Functions with Neural Networks [48.80300074254758]
  We study the learning and representation of neural networks defined on measures. We establish approximation and generalization bounds under different choices of regularization. The resulting models can be learned efficiently and enjoy generalization guarantees that extend across input sizes.
  arXiv  Detail & Related papers  (2020-08-16T16:34:33Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.