Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations

By Boris Hanin. 2017

395 citations recorded by the source corpus.

This article concerns the expressive power of depth in neural nets with ReLU activations and a bounded width. We are particularly interested in the following questions: What is the minimal width w min ( d ) so that ReLU nets of width w min ( d ) (and arbitrary depth) can approximate any continuous function on the unit cube [ 0 , 1 ] d arbitrarily well? For ReLU nets near this minimal width, what can one say about the depth necessary to approximate a given function? We obtain an essentially complete answer to these questions for convex functions. Our approach is based on the observation that, due to the convexity of the ReLU activation, ReLU nets are particularly well suited to represent convex functions. In particular, we prove that ReLU nets with width d + 1 can approximate any continuous convex function of d variables arbitrarily well. These results then give quantitative depth estimates for the rate of approximation of any continuous scalar function on the d-dimensional cube [ 0 , 1 ] d by ReLU nets with width d + 3 .

Subfields: Artificial Intelligence

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

Citations in the corpus

Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, positive): “Using recent results (Mhaskar and Poggio, 2016b; Hanin, 2017; Yarotsky, 2018) we can establish the following result for very deep MLPs.”
Continual learning with hypernetworks (2019, methodology): “For the following proof, we assume the existence of one form of the universal approximation theorem (UAT) for neural networks (Leshno & Schocken, 1993; Hanin, 2017).”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “For example, a series 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 ”
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).”
DEEP NEURAL NETWORKS FOR ESTIMATION AND INFERENCE (2020, result): “Using recent results (Mhaskar and Poggio (2016), Hanin (2019), Yarotsky (2018)), we can establish the following rate for very deep, fixed-width MLPs. COROLLARY 2—Fixed Width Networks: Let the conditions of Theorem 1 hold, with β≥ 1 in Assumption 2.”
Deep Multiscale Model Learning (2018, background): “Many researches have focused on learning the expressivity of deep neural nets theoretically [20, 33, 19, 47, 44, 29].”
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).”
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.”
Strong mixed-integer programming formulations for trained neural networks (2018, background): “Moreover, they can approximate any continuous, non-linear function to an arbitrary precision under a bounded width [36].”
Artificial intelligence and machine learning for medical imaging: A technology review. (2021, neutral): “Deep NNs are obviously also universal approximators [121,122].”
A Review of Deep Learning with Special Emphasis on Architectures, Applications and Recent Trends (2019, background): “1: The Perceptron Learning Model an ANN provided that it has a sufﬁcient number of neurons in a sufﬁcient number of layers with a speciﬁc activation function [10] [11] [12] [13].”
Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness (2019, background): “As neural networks have been shown to be expressive both theoretically [18, 4, 15] and empirically [47], in this work we study to what extent standard neural networks predictors can be made invariant to small rotations and translations.”
Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, background): “See for instance (Hanin, 2019) and (Arora et al., 2018) Deﬁnition 5.”
The Expressive Power of a Class of Normalizing Flow Models (2020, background): “There is a body of work on analyzing the approximation properties of neural networks [Cybenko, 1989, Hornik et al., 1989, Hornik, 1991, Montufar et al., 2014, Telgarsky, 2015, Lu et al., 2017, Hanin, 2017, Raghu et al., 2017].”
Neural network approximation (2020, methodology): “A result along these lines was proven in (Hanin 2019), where it was shown that the output of any ReLU network can be generated by a sufficiently deep ReLU network with fixed width W = d+ 3.”
Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators (2019, background): “For example, there have not been any theoretical results of network size for operator approximation, similar to the bounds of width and depth for function approximation [10].”
Understanding Deep Neural Networks with Rectified Linear Units (2016, background): “(2014), deep belief networks Hinton et al. (2006), and deep Boltzmann machines Salakhutdinov & Hinton (2009). In addition, deep architectures based on new non-saturating activation functions have been suggested to be more effectively trainable – the most successful and widely popular of these is the”