For any positive integer k, there exist neural networks with Θ(k 3 ) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers unless they are exponentially large -they must possess Ω(2 k ) nodes. This result is proved here for a class of nodes termed semi-algebraic gates which includes the common choices of ReLU, maximum, indicator, and piecewise polynomial functions, therefore establishing benefits of depth against not just standard networks with ReLU gates, but also convolutional networks with ReLU and maximization gates, sum-product networks, and boosted decision trees (in this last case with a stronger separation: Ω(2 k 3 ) total tree nodes are required). Keywords: Neural networks, representation, approximation, depth hierarchy. A neural network is a model of real-valued computation defined by a connected directed graph as follows. Nodes await real numbers on their incoming edges, thereafter computing a function of these reals and transmitting it along their outgoing edges. Root nodes apply their computation to a vector provided as input to the network, whereas internal nodes apply their computation to the output of other nodes. Different nodes may compute different functions, two common choices being the maximization gate v → max i v i (where v is the vector of values on incoming edges), and the standard ReLU gate v → σ R ( a, v + b) where σ R (z) := max{0, z} is called the ReLU (rectified linear unit), and the parameters a and b may vary from node to node. Graphs in the present work are acyclic, and there is exactly one node with no outgoing edges whose computation is the output of the network. Neural networks distinguish themselves from many other function classes used in machine learning by possessing multiple layers, meaning the output is the result of composing together an arbitrary number of (potentially complicated) nonlinear operations; by contrast, the functions computed by boosted decision stumps and SVMs can be written as neural networks with a constant number of layers. The purpose of the present work is to show that standard types of networks always gain in representation power with the addition of layers. Concretely: it is shown that for every positive integer k, there exist neural networks with Θ(k 3 ) layers, Θ(1) nodes per layer, and Θ(1) distinct parameters which can not be approximated by networks with O(k) layers and o(2 k ) nodes. Before stating the main result, a few choices and pieces of notation deserve explanation. First, the target many-layered function uses standard ReLU gates; this is by no means necessary, and a more general statement can be found in Theorem 3.12. Secondly, the notion of approximation is the L 1 c 2016 M. Telgarsky. TELGARSKY distance: given two functions f and g, their pointwise disagreement |f (x) − g(x)| is averaged over the cube [0, 1] d . Here as well, the same proofs allow flexibility (cf. Theorem 3.12). Lastly, the shallower networks used for approximation use semi-algebraic gates, which generalize the earlier maximization and standard ReLU gates, and allow for analysis of not just standard networks with ReLU gates, but convolutional networks with ReLU and maximization gates (Krizhevsky et al., 2012) , sum-product networks (where nodes compute polynomials) (Poon and Domingos, 2011), and boosted decision trees; the full definition of semi-algebraic gates appears in Section 2. Theorem 1.1 Let any integer k ≥ 1 and any dimension d ≥ 1 be given. There exists f : R d → R computed by a neural network with standard ReLU gates in 2k 3 + 8 layers, 3k 3 + 12 total nodes, and 4 + d distinct parameters so that where C is the union of the following two sets of functions. • Functions computed by networks of (t, α, β)-semi-algebraic gates in ≤ k layers and ≤ 2 k /(tαβ) nodes. (E.g., as with standard ReLU networks or with convolutional neural networks with standard ReLU and maximization gates; cf. Section 2.) • Functions computed by linear combinations of ≤ t decision trees each with ≤ 2 k 3 /t nodes. (E.g., the function class used by boosted decision trees; cf. Section 2.) Analogs to Theorem 1.1 for boolean circuits -which have boolean inputs routed through {and, or, not} gates -have been studied extensively by the circuit complexity community, where they are called depth hierarchy theorems. The seminal result, due to Håstad (1986), establishes the inapproximability of the parity function by shallow circuits (unless their size is exponential). Standard neural networks appear to have received less study; closest to the present work is an investigation by Eldan and Shamir (2015) analyzing the case k = 2 when the dimension d is large, showing an exponential separation between 2-and 3-layer networks, a regime not handled by Theorem 1.1. Further bibliographic notes and open problems may be found in Section 5. The proof of Theorem 1.1 (and of the more general Theorem 3.12) occupies Section 3. The key idea is that just a few function compositions (layers) suffice to construct a highly oscillatory function, whereas function addition (adding nodes but keeping depth fixed) gives a function with few oscillations. Thereafter, an elementary counting argument suffices to show that low-oscillation functions can not approximate high-oscillation functions. Theorem 1.1 only provides the existence of one network (for each k) which can not be approximated by a network with many fewer layers. It is natural to wonder if there are many such special functions. The following bound indicates their population is in fact quite modest. Specifically, the construction behind Theorem 1.1, as elaborated in Theorem 3.12, can be seen as exhibiting O(2 k 3 ) points, and a fixed labeling of these points, upon which a shallow network hardly improves upon random guessing. The forthcoming Theorem 1.2 similarly shows that even on the more simpler task of fitting O(k 9 ) points, the earlier class of networks is useless on most random labellings. In order to state the result, a few more definitions are in order. Firstly, for this result, the notion of neural network is more restrictive. Let a neural net graph G denote not only the graph structure (nodes and edges), but also an assignment of gate functions to nodes, of edges to the inputs of gates, and an assignment of free parameters w ∈ R p to the parameters of the gates. Let N (G) denote the class of functions obtained by varying the free parameters; this definition is fairly standard, and is discussed in more detail in Section 2. As a final piece of notation, given a function f : Theorem 1.2 Let any neural net graph G be given with ≤ p parameters in ≤ l layers and ≤ m total (t, α, β)-semi-algebraic nodes. Then for any δ > 0 and any n ≥ 8pl 2 ln(8emtαβp(l + 1)) + 4 ln(1/δ) points (x i ) n i=1 , with probability ≥ 1 − δ over uniform random labels This proof is a direct corollary of the VC dimension of semi-algebraic networks, which in turn can be proved by a small modification of the VC dimension proof for piecewise polynomial networks (Anthony and Bartlett, 1999, Theorem 8.8). Moreover, the core methodology for VC dimension bounds of neural networks is due to Warren, whose goal was an analog of Theorem 1.2 for polynomials (Warren, 1968, Theorem 7). Lemma 1.3 (Simplification of Lemma 4.2) Let any neural net graph G be given with ≤ p parameters in ≤ l layers and ≤ m total nodes, each of which is (t, α, β)-semi-algebraic. Then VC(N (G)) ≤ 6p(l + 1) ln(2p(l + 1)) + ln(8emtα) + l ln(β) . The proof of Theorem 1.2 and Lemma 1.3 may be found in Section 4. The argument for the VC dimension is very close to the argument for Theorem 1.1 that a network with few layers has few oscillations; see Section 4 for further discussion of this relationship. The definition of a semi-algebraic gate is unfortunately complicated; it is designed to capture a few standard nodes in a single abstraction without degrading the bounds. Note that the name semialgebraic set is standard (Bochnak et al., 1998, Definition 2.1.4), and refers to a set defined by unions and intersections of polynomial inequalities (and thus the name is somewhat abused here). where U j and L j are subsets of [t] (where [t] := {1, . . . , t}) and p j is a polynomial of degree ≤ β, such that A notable trait of the definition is that the number of terms m does not need to enter the name as it does not affect any of the complexity estimates herein (e.g., Theorem 1.1 or Theorem 1.2). Distinguished special cases of semi-algebraic gates are as follows in Lemma 2.3. The standard piecewise polynomial gates generalize the ReLU and have received a fair bit of attention in the theoretical community (Anthony and Bartlett, 1999, Chapter 8); here a function σ : R → R is (t, α)-poly if R can be partitioned into ≤ t intervals so that σ is a polynomial of degree ≤ α within each piece. The maximization and minimization gates have become popular due to their use in convolutional networks (Krizhevsky et al., 2012) , which will be discussed more in Section 2.1. Lastly, decision trees and boosted decision trees are practically successful classes usually viewed as competitors to neural networks (Caruana and Niculescu-Mizil, 2006), and have the following structure. Definition 2.2 A k-dt (decision tree with k nodes) is defined recursively as follows. If k = 1, it is a constant function. If k > 1, it first evaluates x → 1[ a, x − b ≥ 0], and thereafter conditionally evaluates either a left l-dt or a right r-dt where l + r < k. A (t, k)-bdt (boosted decision tree) evaluates x → t i=1 c i g i (x) where each c i ∈ R and each g i is a k-dt. 1. If σ : R → R is (t, β)-poly and q : R d → R is a polynomial of degree α, then the standard piecewise polynomial gate σ • q is (t, α, αβ)-sa. In particular, the standard ReLU gate v → σ R ( a, v + b) is (1, 1, 1)-sa. 2. Given polynomials (p i ) r i=1 of degree ≤ α, the standard (r, α)-min and -max gates φ min (v) := min i∈[r] p i (v) and φ max (v) := max i∈[r] q i (v) are (r(r − 1), α, α)-sa. 3. Every k-dt is (k, 1, 0)-sa, and every (t, k)-bdt is (tk, 1, 0).
REF shows that there is a ReLU network with L layers and U = Θ(L) units such that any network approximating it with only O(L 1/3 ) layers must have Ω(2 L 1/3 ) units; this phenomenon holds even for real-valued functions.
Benefits of depth in neural networks
ArXiv
ArXiv
Mathematics Computer Science