Optimal approximation of continuous functions by very deep ReLU networks

By Dmitry Yarotsky. 2018

339 citations recorded by the source corpus.

We consider approximations of general continuous functions on finite-dimensional cubes by general deep ReLU neural networks and study the approximation rates with respect to the modulus of continuity of the function and the total number of weights $W$ in the network. We establish the complete phase diagram of feasible approximation rates and show that it includes two distinct phases. One phase corresponds to slower approximations that can be achieved with constant-depth networks and continuous weight assignments. The other phase provides faster approximations at the cost of depths necessarily growing as a power law $L\sim W^{\alpha}, 0<\alpha\le 1,$ and with necessarily discontinuous weight assignments. In particular, we prove that constant-width fully-connected networks of depth $L\sim W$ provide the fastest possible approximation rate $\|f-\widetilde f\|_\infty = O(\omega_f(O(W^{-2/\nu})))$ that cannot be achieved with less deep networks.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Model Architectures

Citations in the corpus

A Constructive Prediction of the Generalization Error Across Scales (2019, background): “While fully engaging with this literature is beyond our scope, we note that recent studies have derived bounds involving power-law dependencies in both model (Yarotsky, 2018) and data size (Liang et al., 2019).”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, background): “Yarotsky (2017, 2018) and Bartlett, Harvey, Liaw, and Mehrabian (2017) are important building blocks for our results.”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…of work tries to understand how the expressive power of deep neural networks are related to their architecture, including the width of each layer and depth of the network (Telgarsky, 2015, 2016; Lu et al., 2017; Liang and Srikant, 2016; Yarotsky, 2017, 2018; Hanin, 2017; Hanin and Sellke, 2017).”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “A line of research has shown that deeper neural networks have higher expressive power (Telgarsky, 2015, 2016; Lu et al., 2017; Liang and Srikant, 2016; Yarotsky, 2017, 2018; Hanin, 2017; Hanin and Sellke, 2017) than shallow neural networks.”
Neural Contextual Bandits with UCB-based Exploration (2019, background): “Neural Networks Substantial progress has been made to understand the expressive power of DNNs, in connection to the network depth (Telgarsky, 2015; 2016; Liang & Srikant, 2016; Yarotsky, 2017; 2018; Hanin, 2017), as well as network width (Lu et al., 2017; Hanin & Sellke, 2017).”
The Kolmogorov-Arnold representation theorem revisited (2020, background): “Combined with the general result on function approximation by deep ReLU networks in [29], a rate is derived that depends on the smoothness of the outer function via the function class K C ([0 , 1] d ; R ), see p.4 in [22] for a deﬁnition.”
DEEP NEURAL NETWORKS FOR ESTIMATION AND INFERENCE (2020, methodology): “Yarotsky (2017, 2018) and Bartlett, Harvey, Liaw, and Mehrabian (2017) are important building blocks for our results.”
Neural network approximation (2020, methodology): “The initial results were given in (Yarotsky 2018) for the model classes U(Lip α), 0 < α ≤ 1 on Ω = [0, 1]d, and were later extended to more general model classes U(Cs(Ω)), s > 0, in (Lu et al.”
Deep Network Approximation for Smooth Functions (2020, background): “paper function class width depth #parameter accuracy Lp([0,1]d)-norm tightness valid for [21] polynomial O(ln 1ε) O(ln 1ε) ε p =∞ small ε > 0 this paper polynomial O(N) O(L) O(N−L) p =∞ any N,L ∈ N+ [20] Lip([0,1]d) O(N) 3 O(N−2/d) p ∈ [1,∞) nearly tight in N any N ∈ N+ [22] Lip([0,1]d) 2d + 10 O(L)”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, background): “So an interesting question is whether the robust expressivity of neural networks can adapt to structures such as low latent dimension of the data mechanism [17, 50], thereby reducing the approximation bound.”
Nonparametric regression using deep neural networks with ReLU activation function (2017, background): “In [77], it has been observed that for such extremely deep networks, one needs discontinuous weight assignments to achieve the best possible approximation rate.”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, background): “Forexample,aseriesofworktriestounderstandhowthe expressivepowerofdeepneuralnetworksarerelatedtotheirarchitecture,includingthewidth of each layer and depth of the network (Telgarsky 2015, 2016; Lu et al. 2017; Liang and Srikant 2016; Yarotsky 2017, 2018; Hanin 2017; Hanin and Sellke 2017).”
ResNet with one-neuron hidden layers is a Universal Approximator (2018, methodology): “This dependence is suboptimal in the exponent, and it may be possible to improve it using a similar strategy as [34].”