Deep neural networks learn smooth functions efficiently in high dimensions
Minimax rates for learning spectral Barron functions by deep ReLU neural networks
Machine Learning
Summary
Some kinds of smooth mathematical functions, called spectral Barron functions, can be learned and approximated by neural networks without becoming too complicated as the number of dimensions grows. The authors show that deep networks with ReLU activations can approximate these functions well, with a specific rate related to the network size and function smoothness. They also prove that learning these functions from data with a deep network can be done nearly as quickly as is theoretically possible. Their results provide a mathematical guarantee on how well deep learning can capture this class of functions.
What this means in practice
- •For machine learning engineers: Design neural networks that efficiently approximate smooth high-dimensional functions with guaranteed error rates tied to network size and data amount.
- •For algorithm designers: Select model architectures and training sample sizes knowing the proven optimal rates for learning spectral Barron functions.
A theory result. No direct application yet.
Authors
Songqiu Ma, Yunfei Yang
Abstract
We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that $d$-dimensional spectral Barron functions with smoothness index $s>0$ can be approximated by deep ReLU neural networks with approximation rate $\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})$, where $S$ denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate $n^{-\frac{d+2s}{2d+2s}}$ with $n$ training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.