lies on its tightness. Compared with the most recent work on unquantized ReLU networks [@yarotsky2017error], where the upper bound on the number of weights to attain an approximation error $\epsilon$ is given by $\mathcal{O}\left(\log(1/\epsilon)\left(1/\epsilon\right)^{\frac{d}{n}}\right)$, our result for a quantized ReLU network is given by $\mathcal{O}\left(\lambda \left(\log^{\frac{1}{\lambda-1}+1}(1/\epsilon)\right)\left(1/\epsilon\right)^{\frac{d}{n}}\right)$, which translates to an increase by a factor of $\lambda \left(\log^{\frac{1}{\lambda-1}}(1/\epsilon)\right)$. Loosely speaking, this term reflects the loss of expressive power because of weight quantization, which decreases quickly as $\lambda$ increases.

**Comparison with the Lower Bound:** We also compare our bound with the lower bound of the number of weights needed to attain an error bound of $\epsilon$ to have a better understanding on the tightness of the bound. We use the lower bound for unquantized ReLU networks from [@yarotsky2017error], as it is also a natural lower bound for quantized ReLU networks. Under the same growth rate of depth, the lower bound is given by $\Omega(\log^{-3}(1/\epsilon)\left(1/\epsilon\right)^{d/n})$, while our upper bound is, within a polylog factor when $\lambda$ is a constant, $\mathcal{O}(\lambda\log^{\frac{1}{\lambda-1}+1}(1/\epsilon)(1/\epsilon)^{d/n})$. The comparison validates the good tightness of our upper bound.

**The Upper Bound of Overhead:** More importantly, the above comparison yields an upper bound on the possible overhead induced by quantization. By comparing 