A Proofs A.1 Proof of Theorem 3.1

Then, combining Lemmas A.1 and A.2 with Eq. 1 and 2, we have null ˆ N f null We start with an intuitive explanation, and then turn to the formal proof. We show that w.h.p. we obtain We use the standard two's complement binary By Lemma A.4, there is = The weights in layers 2,...,k are all in { 1, 1} . We extend this result to real-valued functions. We now turn to the formal proof. Thus, this inequality is linear.