A Proofs

Although we do not allow bias in the output neuron, the additive term B can be implemented by adding a hidden neuron with fan-in 0 and bias 1, that is connected to the output neuron with weight B. Note that E We will prove the following two lemmas: Lemma A.1. Then, combining Lemmas A.1 and A.2 with Eq. 1 and 2, we have ˆN f A.1.1 Proof of Lemma A.1 We start with an intuitive explanation, and then turn to the formal proof. We show that for each step, w.h.p., the change in N Since there are only poly(d) intervals and intervals with large derivatives are small, then by using the fact that µ has an almost-bounded conditional density, we are able to show that w.h.p. the interval between x We show that w.h.p. we obtain g Proof of Lemma A.2 The network ˆN consists of three parts. First, it transforms with high probability the input x to a binary representation of x. Then, it simulates N( x) by using arithmetic operations on binary vectors.