Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks

Abstract

We study the problem of estimating an unknown function from noisy data using shallow ReLU neural networks. The estimators we study minimize the sum of squared data-fitting errors plus a regularization term proportional to the squared Euclidean norm of the network weights. This minimization corresponds to the common approach of training a neural network with weight decay. We quantify the performance (mean-squared error) of these neural network estimators when the data-generating function belongs to the second-order Radon-domain bounded variation space. This space of functions was recently proposed as the natural function space associated with shallow ReLU neural networks. We derive a minimax lower bound for the estimation problem for this function space and show that the neural network estimators are minimax optimal up to logarithmic factors. This minimax rate is immune to the curse of dimensionality. We quantify an explicit gap between neural networks and linear methods (which include kernel methods) by deriving a linear minimax lower bound for the estimation problem, showing that linear methods necessarily suffer the curse of dimensionality in this function space. As a result, this paper sheds light on the phenomenon that neural networks seem to break the curse of dimensionality.

arXiv commentIEEE Transactions on Information Theory (in press)

References in corpus (15)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Approximation and learning by greedy algorithms
• Breaking the Curse of Dimensionality with Convex Neural Networks
• Nonparametric regression using deep neural networks with ReLU activation function
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• The Role of Neural Network Activation Functions
• Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality
• The Finite Neuron Method and Convergence Analysis
• Splines are Universal Solutions of Linear Inverse Problems with Generalized-TV regularization
• Sharp Bounds on the Approximation Rates, Metric Entropy, and $n$-widths of Shallow Neural Networks
• What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory
• Banach Space Representer Theorems for Neural Networks and Ridge Splines
• On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces
• Characterization of the Variation Spaces Corresponding to Shallow Neural Networks
• Optimal Learning

Cited by in corpus (7)

• Deep Learning Meets Sparse Regularization: A Signal Processing Perspective
• Optimal rates of approximation by shallow ReLU${}^k$ neural networks and applications to nonparametric regression
• Spectral Barron space for deep neural network approximation
• Weighted variation spaces and approximation by shallow ReLU networks
• Distributional Extension and Invertibility of the $k$-Plane Transform and Its Dual
• MARS via LASSO
• Function-Space Optimality of Neural Architectures with Multivariate Nonlinearities