Lower bounds over Boolean inputs for deep neural networks with ReLU
  gates
  Motivated by the resurgence of neural networks in being able to solve complex
learning tasks we undertake a study of high depth networks using ReLU gates
which implement the function $x \mapsto \max\{0,x\}$. We try to understand the
role of depth in such neural networks by showing size lowerbounds against such
network architectures in parameter regimes hitherto unexplored. In particular
we show the following two main results about neural nets computing Boolean
functions of input dimension $n$,
  1. We use the method of random restrictions to show almost linear,
$\Omega(\epsilon^{2(1-\delta)}n^{1-\delta})$, lower bound for completely weight
unrestricted LTF-of-ReLU circuits to match the Andreev function on at least
$\frac{1}{2} +\epsilon$ fraction of the inputs for $\epsilon >
\sqrt{2\frac{\log^{\frac {2}{2-\delta}}(n)}{n}}$ for any $\delta \in (0,\frac 1
2)$
  2. We use the method of sign-rank to show exponential in dimension lower
bounds for ReLU circuits ending in a LTF gate and of depths upto $O(n^{\xi})$
with $\xi < \frac{1}{8}$ with some restrictions on the weights in the bottom
most layer. All other weights in these circuits are kept unrestricted. This in
turns also implies the same lowerbounds for LTF circuits with the same
architecture and the same weight restrictions on their bottom most layer.
  Along the way we also show that there exists a $\mathbb{R}^ n\rightarrow
\mathbb{R}$ Sum-of-ReLU-of-ReLU function which Sum-of-ReLU neural nets can
never represent no matter how large they are allowed to be.
