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 {\em 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 $\frac12k^{k+1}-1$ total nodes. Finally, for the family of $\R^n\to \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 \emph{smoothly parameterized} family of functions attaining this scaling. Our construction utilizes the theory of zonotopes from polyhedral theory. Deep neural networks (DNNs) provide an excellent family of hypotheses for machine learning tasks such as classification. Neural networks with a single hidden layer of finite size can represent any continuous function on a compact subset of R n arbitrary well. The universal approximation result was first given by Cybenko in 1989 for sigmoidal activation function BID4 , and later generalized by Hornik to an arbitrary bounded and nonconstant activation function BID15 . Furthermore, neural networks have finite VC dimension (depending polynomially on the number of edges in the network), and therefore, are PAC (probably approximately correct) learnable using a sample of size that is polynomial in the size of the networks BID1 . However, neural networks based methods were shown to be computationally hard to learn BID1 and had mixed empirical success. Consequently, DNNs fell out of favor by late 90s.to address the issue of efficiently training DNNs. These include heuristics such as dropouts BID39 , but also considering alternate deep architectures such as convolutional neural networks BID33 , deep belief networks BID14 , and deep Boltzmann machines BID31 . 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 rectified linear unit (ReLU) activation, i.e., σ(x) = max{0, x}, which is the focus of study in this paper.In this paper, we formally study deep neural networks with rectified linear units; we refer to these deep architectures as ReLU DNNs. Our work is inspired by these recent attempts to understand the reason behind the successes of deep learning, both in terms of the structure of the functions represented by DNNs, Telgarsky (2015; ; BID17 ; BID36 , as well as efforts which have tried to understand the non-convex nature of the training problem of DNNs better BID18 ; BID10 . Our investigation of the function space represented by ReLU DNNs also takes inspiration from the classical theory of circuit complexity; we refer the reader to BID2 ; BID37 ; BID16 ; BID32 ; BID0 for various surveys of this deep and fascinating field. In particular, our gap results are inspired by results like the ones by BID12 , BID27 and BID38 which show a strict separation of complexity classes. We make progress towards similar statements with deep neural nets with ReLU activation. The running time of the algorithm that we give in this work to find the exact global minima of a two layer ReLU-DNN is exponential in the input dimension n and the number of hidden nodes w. The exponential dependence on n can not be removed unless P = N P ; see BID35 ; BID3 ; BID6 . However, we are not aware of any complexity results which would rule out the possibility of an algorithm which trains to global optimality in time that is polynomial in the data size and/or the number of hidden nodes, assuming that the input dimension is a fixed constant. Resolving this dependence on network size would be another step towards clarifying the theoretical complexity of training ReLU DNNs and is a good open question for future research, in our opinion. Perhaps an even better breakthrough would be to get optimal training algorithms for DNNs with two or more hidden layers and this seems like a substantially harder nut to crack. It would also be a significant breakthrough to get gap results between consecutive constant depths or between logarithmic and constant depths.
This paper 1) characterizes functions representable by ReLU DNNs, 2) formally studies the benefit of depth in such architectures,  3) gives an algorithm to implement empirical risk minimization to global optimality for two layer ReLU nets.
{"src": "scitldr-AIC_train", "paper_id": "B1J_rgWRW"}