Compression is a key step to deploy large neural networks on resource-constrained platforms. As a popular compression technique, quantization constrains the number of distinct weight values and thus reducing the number of bits required to represent and store each weight. In this paper, we study the representation power of quantized neural networks. First, we prove the universal approximability of quantized ReLU networks on a wide class of functions. Then we provide upper bounds on the number of weights and the memory size for a given approximation error bound and the bit-width of weights for function-independent and function-dependent structures. Our results reveal that, to attain an approximation error bound of $\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 than the lower bound of the number of weights needed for the error bound, supporting the empirical success of various quantization techniques. To the best of our knowledge, this is the first in-depth study on the complexity bounds of quantized neural networks. Various deep neural networks deliver state-of-the-art performance on many tasks such as object recognition and natural language processing using new learning strategies and architectures BID11 Kumar et al., 2016; Ioffe & Szegedy, 2015; Vaswani et al., 2017) . Their prevalence has extended to embedded or mobile devices for edge intelligence, where security, reliability or latency constraints refrain the networks from running on servers or in clouds. However, large network sizes with the associated expensive computation and memory consumption make edge intelligence even more challenging BID2 Sandler et al., 2018) .In response, as will be more detailed in Section 2, substantial effort has been made to reduce the memory consumption of neural networks while minimizing the accuracy loss. The memory consumption of neural networks can be reduced by either directly reducing the number of weights or decreasing the number of bits (bit-width) needed to represent and store each weight, which can be employed on top of each other BID3 . The number of weights can be reduced by pruning BID9 , weight sparsifying (Liu et al., 2015) , structured sparsity learning BID14 and low rank approximation BID5 . The bit-width is reduced by quantization that maps data to a smaller set of distinct levels (Sze et al., 2017) . Note that while quantization may stand for linear quantization only (Li et al., 2017; BID7 or nonlinear quantization only BID8 BID3 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 (Hubara et al., 2016; BID20 BID22 . 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 BID15 . We follow the idea from BID16 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 λ and a target function f , we construct a network that can approximate f with an arbitrarily small error bound to prove the universal approximability. The memory size of this network then naturally serves as an upper bound for the minimal network size.The high-level idea of our approach is to replace basic units in an unquantized network with quantized sub-networks 1 that approximate these basic units. For example, we can approximate a connection with any weight in an unquantized network by a quantized sub-network that only uses a finite number of given weight values. Even though the approximation of a single unit can be made arbitrarily accurate in principle with unlimited resources (such as increased network depth), in practice, there exists some inevitable residual error at every approximation, all of which could propagate throughout the entire network. The challenge becomes, however, how to mathematically prove that we can still achieve the end-to-end arbitrary small error bound even if these unavoidable residual errors caused by quantization can be propagated throughout the entire network. This paper finds a solution to solve the above challenge. In doing so, we have to propose a number of new ideas to solve related challenges, including judiciously choosing the proper finite weight values, 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 , the number of weights needed by a quantized network is no more than O log 5 (1/ ) 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-ofthe-art quantization schemes work well in 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 2 reviews related works. Section 3 lays down the models and assumptions of our analysis. We prove the universal approximability and the upper bounds with function-independent structure in Section 4 and extend it to function-dependent structure in Section 5. We analyze the bound-based optimal bit-width in Section 6. Finally , Section 7 discusses the results and gets back to the questions raised above. In this section, we further discuss the bound of nonlinear quantization with a function-independent structure as the generality of nonlinear quantization. The availability of unquantized functionindependent structures in literature also makes it an excellent reference for comparison.Comparison with the Upper Bound: The quality of an upper bound lies on its tightness. Compared with the most recent work on unquantized ReLU networks BID16 , where the upper bound on the number of weights to attain an approximation error is given by O log(1/ ) (1/ ) d n , our result for a quantized ReLU network is given by O λ log DISPLAYFORM0 , which translates to an increase by a factor of λ log 1 λ−1 (1/ ) . Loosely speaking, this term reflects the loss of expressive power because of weight quantization, which decreases quickly as λ increases.
This paper proves the universal  approximability of quantized ReLU neural networks and puts forward the complexity bound given arbitrary error.
{"src": "scitldr-AIC_train", "paper_id": "SJe9rh0cFX"}