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.

本文研究使用带有 ReLU 的深度神经网络能够代表的函数家族，提供了一个训练一个 ReLU 深度神经网络的一种算法，同时提高了在将 ReLU 神经网络函数逼近为浅层 ReLU 网络时已知下限的上界，并证明了这些间隙定理。