training of quantized neural networks has been analyzed theoretically, but not the network capacity [@li2017training; @choi2016towards].

**Universal Approximability and Complexity Bounds:** The universal approximability of ReLU networks is proved in [@mhaskar1992approximation] and revisited in [@sonoda2017neural]. Recently, [@hanin2017universal] discusses the expressive power of ReLU networks with bounded width and proves that a ReLU network with width $d+1$ can approximate any continuous convex function of $d$ variables arbitrarily well. [@shaham2016provable] construct a sparsely-connected depth-4 ReLU network and prove its error bound. [@liang2016deep] prove that, for a large class of piecewise smooth functions, a network with ReLU and binary step units can provide an error bound $\epsilon$ with $\mathcal{O}(1/\epsilon)$ layers and $\mathcal{O}(\text{poly}\log(1/\epsilon))$ neurons. The universal approximation property of low displacement rank (LDR) neural networks has been proved by [@zhao2017theoretical] under a mild condition on the displacement operator, which is the result of another effective technique of neural network compression.

Models and Assumptions {#sec:models}
======================

Throughout this paper, we define ReLU networks as feedforward neural networks with the ReLU activation function $\sigma(x)=\text{max}(0,x)$. The ReLU network considered includes multiple input units, a number of hidden units, and one output unit. Without loss of generality, each unit can only connect to units in the next layer. 