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

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.

arXiv commentYuling Jiao and Guohao Shen contributed equally to this work. Co-corresponding authors: Yuanyuan Lin (Email: [email protected]) and Jian Huang (Email: [email protected])

References in corpus (17)

• A Convergence Theory for Deep Learning via Over-Parameterization
• The Power of Depth for Feedforward Neural Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Deep Network Approximation for Smooth Functions
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Why Deep Neural Networks for Function Approximation?
• Optimal approximation of continuous functions by very deep ReLU networks
• The Expressive Power of Neural Networks: A View from the Width
• Local polynomial regression on unknown manifolds
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• Optimal Approximation Rate of ReLU Networks in terms of Width and Depth
• Nonlinear Approximation via Compositions
• k-NN Regression Adapts to Local Intrinsic Dimension
• Deep ReLU network approximation of functions on a manifold
• Dimensionality compression and expansion in Deep Neural Networks
• A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks
• Estimation of a function of low local dimensionality by deep neural networks

Cited by in corpus (5)

• Robust Nonparametric Regression with Deep Neural Networks
• Deep Dimension Reduction for Supervised Representation Learning
• A Deep Generative Approach to Conditional Sampling
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• Stationary Density Estimation of Itô Diffusions Using Deep Learning