Understanding Deep Neural Networks with Rectified Linear Units

By Raman Arora, Amitabh Basu, Poorya Mianjy, Anirbit Mukherjee. 2016

740 citations recorded by the source corpus.

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give an algorithm to train a ReLU DNN with one hidden layer to *global optimality* with runtime polynomial in the data size albeit exponential in the input dimension. Further, we improve on the known lower bounds on size (from exponential to super exponential) for approximating a ReLU deep net function by a shallower ReLU net. Our gap theorems hold for smoothly parametrized families of "hard" functions, contrary to countable, discrete families known in the literature. An example consequence of our gap theorems is the following: for every natural number $k$ there exists a function representable by a ReLU DNN with $k^2$ hidden layers and total size $k^3$, such that any ReLU DNN with at most $k$ hidden layers will require at least $\frac{1}{2}k^{k+1}-1$ total nodes. Finally, for the family of $\mathbb{R}^n\to \mathbb{R}$ DNNs with ReLU activations, we show a new lowerbound on the number of affine pieces, which is larger than previous constructions in certain regimes of the network architecture and most distinctively our lowerbound is demonstrated by an explicit construction of a *smoothly parameterized* family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory.

Subfields: Artificial Intelligence, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Being Bayesian, Even Just a Bit, Fixes Overconfidence in ReLU Networks (2020, methodology): “ReLU networks are networks that result in piecewise affine classifier functions (Arora et al., 2018), which include networks with fully-connected, convolutional, and residual layers where just ReLU or leaky-ReLU are used as activation functions and max or average pooling are used in convolution laye”
On the Spectral Bias of Neural Networks (2018, background): “Remarkably, the converse is also true: every CPWL function can be represented by a ReLU network (Arora et al., 2018, Theorem 2.1), which in turn endows ReLU networks with universal approximation properties.”
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.”
Model complexity of deep learning: a survey (2021, background): “The family of piecewise linear functions is dense in the family of compactly supported continuous functions, and the family of compactly supported continuous functions is dense in Lebesgue space L p(Rd) [3,23].”
Shallow Learning For Deep Networks (2018, background): “Moreover, Arora et al. (2018); Ge et al. (2017); Du & Goel (2018); Bach (2014) proposed provable optimization strategies for this case.”
Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations (2017, neutral): “1 in [2] (see Theorem 2), we may write: fε = gε − hε,”
How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks (2020, background): “MLPs have ﬁnitely many linear regions (Arora et al., 2018; Hanin & Rolnick, 2019; Hein et al., 2019).”
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “Superior expressiveness of deeper networks, long suspected, is now conﬁrmed by theory, albeit for fairly limited learning problems (Eldan & Shamir, 2015; Raghu et al., 2016; Lee et al., 2017; Cohen et al., 2017; Daniely, 2017; Arora et al., 2018).”
Reliably Learning the ReLU in Polynomial Time (2016, background): “[2] considers the complexity of training depth-2 networks of ReLUs with k hidden units on a sample of size m but when the dimension n = 1.”
A randomized gradient-free attack on ReLU networks (2018, methodology): “In this paper we propose a new method for the generation of adversarial inputs for ReLU feedforward neural networks which exploits only the underlying geometric structure of the classifier which are well known to result in continuous piecewise affine functions [1].”
Depth Creates No Bad Local Minima (2017, neutral): “Kawaguchi, 2016; Swirszcz et al., 2016; Arora et al., 2016; Freeman & Bruna, 2016; Soudry & Hoffer, 2017).”
Relu Deep Neural Networks and Linear Finite Elements (2018, methodology): “In [14], it is shown that piecewise linear functions can be written as ReLU DNNs, which will be discussed in details later.”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, methodology): “For instance, Arora et al. (2016) gives an algorithm with O(nd) running time to minimize the empirical risk of a two-layer neural network. A closer analysis of the generalization bounds required in this algorithm for PAC learning is given in Manurangsi and Reichman (2018), which gives a 2poly(k/ )po”
Variational Physics-Informed Neural Networks For Solving Partial Differential Equations (2019, background): “It was also shown in [1] that a one-to-one correspondence between the class of ReLU DNNs and piecewise linear (PWL) functions can be established, which shows that any PWL function can be representable by a ReLU DNN. DNNs are generally comprised of input, output, and hidden layer(s), where each…”
Anomaly Detection using One-Class Neural Networks (2018, methodology): “Per the success of the Batch Normalization architecture [21] and Exponential Linear Units [14], we have found that convolutional+batch-normalization+elu layers provide a better representation of convolutional filters.”