quantization that maps data to a smaller set of distinct levels [@sze2017efficient]. Note that while quantization may stand for linear quantization only [@li2017training; @gysel2016hardware] or nonlinear quantization only [@han2015deep; @choi2016towards] in different works, our discussion will cover both cases.

However, as of today quantization is still only empirically shown to be robust and effective to compress various neural network architectures [@hubara2016quantized; @zhou2017adaptive; @zhuang2017towards]. Its theoretical foundation still remains mostly missing. Specifically, many important questions remain unanswered. For example:

-   Why even binarized networks, those most extremely quantized with bit-width down to one, still work well in some cases?

-   To what extent will quantization decrease the expressive power of a network? Alternatively, what is the overhead induced by weight quantization in order to maintain the same accuracy?

In this paper, we provide some insights into these questions from a theoretical perspective. We focus on ReLU networks, which is among the most widely used in deep neural networks [@xu2015empirical]. We follow the idea from [@yarotsky2017error] to prove the complexity bound by constructing a network, but with new and additional construction components essential for quantized networks. Specifically, given the number of distinct weight values $\lambda$ and a target function $f$, we construct 