We present a simple proof for the benefit of depth in multi-layer feedforward network with rectifed activation (``"depth separation"). Specifically we present a sequence of classification problems f_i such that (a) for any fixed depth rectified network we can find an index m such that problems with index > m require exponential network width to fully represent the function f_m; and (b) for any problem f_m in the family, we present a concrete neural network with linear depth and bounded width that fully represents it.

 While there are several previous work showing similar results, our proof uses substantially simpler tools and techniques, and should be accessible to undergraduate students in computer science and people with similar backgrounds. We present a simple, geometric proof of the benefit of depth in deep neural networks. We prove that there exist a set of functions indexed by m, each of which can be efficiently represented by a depth m rectified MLP network requiring O(m) parameters. However, for any bounded depth rectified MLP network, there is a function f m in this set that representing it will require an exponential number of parameters in m. More formally, let G d be the set of multi-layer perceptron (MLP) networks with rectified activation and d hidden layers, and let g Θ be such an MLP with parameters Θ. We will prove the following theorem: Theorem 1 (Depth Separation). There exists a set of functions f 1 , f 2 , ..., f i : R 2 → {−1, 1} such that: While this is not a novel result, a main characteristic of our proof is its simplicity. In contrast to previous work, our proof uses only basic algebra, geometry and simple combinatorial arguments. As such, it can be easily read and understood by newcomers and practitioners, or taught in an undergraduate class, without requiring extensive background. Tailoring to these crowds, our presentation style is more verbose then is usual in papers of this kind, attempting to spell out all steps explicitly. We also opted to trade generality for proof simplicity, remaining in input space R 2 rather than the more general R n , thus allowing us to work with lines rather than hyperplanes. Beyond being easy to visualize, it also results in simple proofs of the different lemmas.
ReLU MLP depth seperation proof with gemoteric arguments A proof that deeper networks need less units than shallower ones for a family of problems. 