practice.

-   We demonstrate how a theoretical complexity bound can be used to estimate an optimal bit-width, which in turn enables the best cost-effectiveness for a given task.

The remainder of the paper is organized as follows. Section \[sec:related\] reviews related works. Section \[sec:models\] lays down the models and assumptions of our analysis. We prove the universal approximability and the upper bounds with function-independent structure in Section \[sec:independent\] and extend it to function-dependent structure in Section \[sec:dependent\]. We analyze the bound-based optimal bit-width in Section \[sec:bitwidth\]. Finally, Section \[sec:comparison\] discusses the results and gets back to the questions raised above.

Related Works {#sec:related}
=============

**Quantized Neural Networks:** There are rich literatures on how to obtain quantized networks, either by linear quantization or nonlinear quantization [@zhou2017incremental; @leng2017extremely; @shayar2017learning]. Linear quantization does mapping with a same distance between contiguous quantization levels and is usually implemented by storing weights as fixed-point numbers with reduced bit-width [@li2017training; @gysel2016hardware]. Nonlinear quantization maps the data to quantization levels that are not uniformly distributed and can be either preselected or learned from training. Then the weights are stored using lossless binary coding (the index to a lookup table) instead of the actual values [@han2015deep; @choi2016towards]. It is 