Approximation and Estimation for High-Dimensional Deep Learning Networks

Andrew R. Barron, Jason M. KlusowskiarXiv 2018 · arXiv

Introduction

In classical statistical learning theory, the "curse of dimensionality" suggests that the amount of data required to train a model grows exponentially with the number of input features. However, modern deep learning practice frequently contradicts this principle. Large-scale neural networks, often possessing millions more parameters than available data points, consistently demonstrate remarkable generalization capabilities. This "overfitting paradox" challenges traditional complexity measures, such as VC dimension, which typically produce risk bounds that scale linearly with the number of parameters.

In "Approximation and Estimation for High-Dimensional Deep Learning Networks," Barron and Klusowski provide a theoretical breakthrough that resolves this tension. By shifting the focus from the raw count of parameters to the structural variation of weights, they prove that deep neural networks can achieve high accuracy even when the input dimension $d$ is far greater than the sample size $n$.

Beyond Parameter Counting: The Role of Weight Variation

The authors focus on multi-layer networks employing ramp activation functions, commonly known as Rectified Linear Units (ReLUs). The core of their argument is that the complexity of a network is governed not by its volume (the number of neurons), but by the "total flow" or variation of weights across the network's paths.

To quantify this, they utilize $\ell^1$-type constraints on the products of weights. This approach allows for a "sparse covering" of the function space. Even if a network is technically dense—meaning most weights are non-zero—it can behave like a sparse model if the overall variation is controlled. This perspective aligns with the empirical observation that many weights in trained networks are small or redundant.

Methodological Innovations

The paper introduces several key technical components to derive these tighter bounds:

  1. Probabilistic Sampling and Representer Tricks: To demonstrate that a complex network can be approximated by a simpler one, the authors use a sampling strategy. They show that by drawing sparse parameters at random, one can construct a "sparse covering" that approximates any network within their defined class.
  2. Markov Chain Interpretation: The authors treat the sequence of weights along a path from input to output as a Markov chain. This allows them to apply probabilistic tools to bound the average variation across layers, effectively managing the complexity as it propagates through the network.
  3. Canonical Scaling: Leveraging the homogeneity of ReLU functions, the authors identify a "canonical form" for networks. Since weights can be rescaled between layers without altering the output function, they define a scaling that balances weight flow, which is essential for minimizing complexity bounds.
  4. Metric Entropy and Covering Numbers: The authors calculate the "covering number" of the function space—a measure of how many prototypical networks are needed to approximate any possible network within a specific error tolerance. Their results provide a significantly tighter bound than previous methods that relied on the product of spectral norms.

Key Results: The Power of Logarithms

The most significant finding of this work is the derivation of a new statistical risk bound (mean squared predictive error). The authors show that the risk is upper bounded by: $$\sqrt{\frac{L^3 \log d}{n}}$$ where $L$ represents the network depth, $d$ is the input dimension, and $n$ is the sample size.

This formula has profound implications:

  • Logarithmic Scaling: Because the risk depends only on $\log d$, the input dimension can be increased by orders of magnitude with only a marginal increase in the required sample size. This explains why deep learning excels in high-dimensional tasks like image recognition or natural language processing.
  • Polynomial Depth Dependence: While previous theories suggested that complexity might grow exponentially with depth ($L$), this work demonstrates that under appropriate constraints, the dependence is a manageable low-order polynomial ($L^3$).
  • Minimax Optimality: The authors establish that this risk rate is close to the best possible rate (minimax optimal) for this class of functions, suggesting that their bounds are not just improvements, but are nearing the fundamental limits of learning.

Limitations and Future Directions

While this work provides a robust theoretical framework, it also highlights areas for further research. The theory relies on $\ell^1$-type constraints, which are not always explicitly enforced by standard Stochastic Gradient Descent (SGD), though techniques like weight decay or Lasso-style regularization provide approximations. Additionally, the authors note a potential "statistical bias" introduced by the nonlinearity of ReLU functions during sampling, suggesting that more refined strategies could yield even tighter bounds. Finally, while the $1/2$ exponent in the risk bound is a major advancement, specific architectures (like two-layer networks) may allow for even faster rates, indicating that the depth-dependent constants could be further optimized.

Conclusion

Barron and Klusowski’s work provides a vital mathematical bridge between the empirical success of deep learning and statistical theory. By identifying weight variation as the true driver of complexity, they demonstrate that high-dimensional learning is not only possible but theoretically sound, provided the underlying target functions exhibit controlled structural variation.

Summary updated

BibTeX
@misc{barron2018approximation,
  author = {Andrew R. Barron and Jason M. Klusowski},
  title = {{Approximation and Estimation for High-Dimensional Deep Learning Networks}},
  year = {2018},
  eprint = {1809.03090},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.03090},
}
Figure