Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors

Yuling Jiao, Guohao Shen, Yuanyuan Lin, Jian Huang

Abstract

This paper investigates the theoretical properties of nonparametric least squares regression using deep neural networks (DNNs). The authors derive non-asymptotic upper bounds for the prediction error of the empirical risk minimizer (ERM) in feedforward deep neural regression. These bounds achieve minimax optimal rates and significantly improve upon existing literature by demonstrating a polynomial, rather than exponential, dependence on the predictor's dimension. By assuming the predictor is supported on an approximate low-dimensional manifold or a set with low Minkowski dimension, the study shows how neural regression circumvents the "curse of dimensionality." Additionally, the paper introduces the concept of Network Relative Efficiency (NRE) to quantitatively evaluate different network architectures and provides a novel approximation error bound for Hölder smooth functions using ReLU-activated networks.

Introduction

In classical statistics, nonparametric regression is notoriously difficult in high-dimensional settings due to the curse of dimensionality. For a target function with smoothness $\beta$ and input dimension $d$, the optimal error rate is typically $n^{-2\beta/(2\beta+d)}$. As $d$ increases, the amount of data $n$ required to maintain accuracy grows exponentially. While deep learning has seen immense empirical success on high-dimensional data (e.g., images and text), theoretical explanations have often lagged behind.

Previous theoretical bounds for DNNs often included mathematical constants (prefactors) that grew exponentially with $d$ (e.g., $2^d$). For high-dimensional inputs like ImageNet ($d \approx 150,000$), a prefactor of $2^d$ renders the theoretical bound practically meaningless. This paper addresses this gap by proving that for data with intrinsic low-dimensional structures, DNNs can achieve error bounds where the prefactor depends only polynomially on $d$.

Theoretical Framework and Methods

The study focuses on Least Squares Regression using feedforward neural networks with ReLU activation functions. The researchers utilize several key theoretical innovations to refine existing error bounds:

1. Novel Approximation Bounds

The authors derive a new method for bounding how effectively a ReLU network can approximate Hölder smooth functions. These are functions that are locally well-behaved and possess bounded derivatives. By employing a refined Taylor expansion-based proof technique, they demonstrate that the approximation error can be controlled with much tighter constants than previously thought.

2. Manifold and Dimensionality Assumptions

To explain why DNNs perform well on data like images, the paper analyzes three specific data structures:

  • Approximate Manifolds: Data that lies within a small distance $\rho$ of a low-dimensional Riemannian manifold.
  • Exact Manifolds: Data supported exactly on a low-dimensional manifold.
  • Low Minkowski Dimension: A general measure of "low-dimensionality" that encompasses fractal-like sets.

These assumptions are motivated by real-world benchmarks. For instance, while MNIST has an ambient dimension of 784, its intrinsic dimension is estimated to be between 9 and 43. CIFAR-10 and ImageNet exhibit similar properties, where the meaningful information resides on a much lower-dimensional subspace.

3. Network Relative Efficiency (NRE)

The authors introduce Network Relative Efficiency as a quantitative metric to compare different architectures. NRE measures the total number of parameters required by one network type versus another to achieve the same target error rate. This provides a formal way to evaluate the merits of depth versus width.

Key Insights

Circumventing the Curse of Dimensionality

The primary breakthrough is the transition from exponential to polynomial prefactors. By showing that the constant depends on $d^k$ rather than $2^d$, the bounds become "non-asymptotic," meaning they provide meaningful insights even for finite, high-dimensional samples.

Adaptation to Intrinsic Dimension

The paper proves that DNNs are adaptive. If the data lies on a manifold of dimension $d_M$, the convergence rate effectively replaces the ambient dimension $d$ with $d_M$ (or $d_M \log d$ in the case of approximate manifolds). Under the exact manifold assumption, the error bound prefactor depends only linearly on the ambient dimension $d$.

The Efficiency of Depth

Using the NRE metric, the authors demonstrate that deep networks are significantly more efficient than wide, shallow networks. Specifically, a deep network requires far fewer total parameters to reach the same error bound as a wide counterpart. The theory suggests an optimal design strategy: maintain a width polynomial in $d$ (specifically $O(d^{\lfloor \beta \rfloor + 1})$) while allowing the depth to grow with the square root of the sample size ($\sqrt{n}$).

Conclusion and Future Work

This research provides a rigorous mathematical foundation for the empirical success of deep learning in high dimensions. It shows that DNNs are uniquely suited to exploit the low-dimensional manifold structure inherent in many real-world datasets.

However, the study notes certain limitations. The results assume the ability to find the Empirical Risk Minimizer (ERM), ignoring the "optimization error" introduced by algorithms like Gradient Descent. Furthermore, the bounds are specifically tailored to ReLU activations. Future work may extend these polynomial prefactor results to other architectures, such as GANs or Diffusion models, and explore the implications for different activation functions like Swish or GeLU.

Summary updated

Abstract

We study the properties of nonparametric least squares regression using deep neural networks. We derive non-asymptotic upper bounds for the prediction error of the empirical risk minimizer of feedforward deep neural regression. Our error bounds achieve minimax optimal rate and significantly improve over the existing ones in the sense that they depend polynomially on the dimension of the predictor, instead of exponentially on dimension. We show that the neural regression estimator can circumvent the curse of dimensionality under the assumption that the predictor is supported on an approximate low-dimensional manifold or a set with low Minkowski dimension. We also establish the optimal convergence rate under the exact manifold support assumption. We investigate how the prediction error of the neural regression estimator depends on the structure of neural networks and propose a notion of network relative efficiency between two types of neural networks, which provides a quantitative measure for evaluating the relative merits of different network structures. To establish these results, we derive a novel approximation error bound for the Hölder smooth functions with a positive smoothness index using ReLU activated neural networks, which may be of independent interest. Our results are derived under weaker assumptions on the data distribution and the neural network structure than those in the existing literature.
BibTeX
@article{jiao2023deep,
  author = {Yuling Jiao and Guohao Shen and Yuanyuan Lin and Jian Huang},
  title = {{Deep Nonparametric Regression on Approximate Manifolds: Non-Asymptotic Error Bounds with Polynomial Prefactors}},
  journal = {The Annals of Statistics},
  year = {2023},
  doi = {10.1214/23-aos2266},
}
Figure