constructing the approximation sub-networks as efficient as possible (to have a tight upper bound), and striking a good balance among the complexities of different approximation steps.

Based on the bounds derived, we compare them with the available results on unquantized neural networks and discuss its implications. In particular, the main contributions of this paper include:

-   We prove that even the most extremely quantized ReLU networks using two distinct weight values are capable of representing a wide class of functions with arbitrary accuracy.

-   Given the number of distinct weights and the desired approximation error bound, we provide upper bounds on the number of weights and the memory size. We further show that our upper bounds have good tightness by comparing them with the lower bound of unquantized ReLU networks established in the literature.

-   We show that, to attain the same approximation error bound $\epsilon$, the number of weights needed by a quantized network is no more than $\mathcal{O}\left(\log^5(1/\epsilon)\right)$ times that of an unquantized network. This overhead is of much lower order compared with even the lower bound of the number of weights needed for the error bound. This partially explains why many state-of-the-art quantization schemes work well in 