Year: 2019

Abstract:
Quantizing weights and activations of deep neural networks results in significant improvement in inference efficiency at the cost of lower accuracy. A source of the accuracy gap between full precision and quantized models is the quantization error. In this work, we focus on the binary quantization, in which values are mapped to -1 and 1. We introduce several novel quantization algorithms: optimal 1-bit, ternary, 2-bits, and greedy. Our quantization algorithms can be implemented efficiently on the hardware using bitwise operations. We present proofs to show that our proposed methods are optimal, and also provide empirical error analysis. We conduct experiments on the ImageNet dataset and show a reduced accuracy gap when using the proposed optimal quantization algorithms.

heading: 1 INTRODUCTION
text: A major challenge in the deployment of Deep Neural Networks (DNNs) is their high computational cost. Finding effective methods to improve run-time efficiency is still an area of research. We can group various approaches taken by researchers into the following three categories.
Hardware optimization: Specifically designed hardwares are deployed to efficiently perform computations in ML tasks. Compiler optimization: Compression and fusion techniques coupled with efficient hardware-aware implementations, such as dense and sparse matrix-vector multiplication, are used. Model optimization: Run-time performance can also be gained by modifying the model structure and the underlying arithmetic operations. While hardware and compiler optimization are typically lossless (i.e. incur no loss in model accuracy), model optimization trades-off computational cost (memory, runtime, or power) for model accuracy. For example, by scaling the width of the network (Zagoruyko & Komodakis, 2016). The goal of model optimization is to improve the trade-off between computational cost and model accuracy. This work falls into this category.

heading: 1.1 ARCHITECTURE OPTIMIZATION
text: One strategy to construct efficient DNNs is to define a template from which efficient computational blocks can be generated. Multiple instantiations of these blocks are then chained together to form a DNN. SqueezeNet (Iandola et al., 2016), MobileNets (Howard et al., 2017; Sandler et al., 2018), ShuffleNets (Zhang et al., 2018b; Ma et al., 2018), and ESPNets (Mehta et al., 2018; 2019) fall into this category. Complementary to these methods, NASNet (Zoph et al., 2018) and EfficientNet (Tan & Le, 2019) search for an optimal composition of blocks restricted to a computational budget (e.g., FLOPS) by changing the resolution, depth, width, or other parameters of each layer.

heading: 1.2 PRUNING AND COMPRESSION
text: Several methods have been proposed to improve runtime performance by detecting and removing computational redundancy. Methods in this category include low-rank acceleration (Jaderberg et al., 2014), the use of depth-wise convolution in Inception (Szegedy et al., 2015), sparsification of kernels in deep compression (Han et al., 2015), re-training redundant neurons in DSD (Han et al., 2016b), depth-wise separable convolution in Xception (Chollet, 2017), pruning redundant filters in PFA (Suau et al., 2018), finding an optimal sub-network in lottery ticket hypothesis (Frankle & Carbin, 2018), and separating channels based on the features resolution in octave convolution (Chen et al.,
2019). While some of these compression methods can be applied to a trained network, most add training-time constraints to create a computationally efficient model.

heading: 1.3 LOW-PRECISION ARITHMETIC AND QUANTIZATION
text: Another avenue to improve runtime performance (and the focus of this work) is to use low-precision arithmetic. The idea is to use fewer bits to represent weights and activations. Some instances of these strategies already exist in AI compilers, where it is common to cast weights of a trained model from 32 bits to 16 or 8 bits. However, in general, post-training quantization reduces the model accuracy. This can be addressed by incorporating lower-precision arithmetic into the training process (during-training quantization), allowing the resulting model to better adapt to the lower precision. For example, in Gupta et al. (2015); Jacob et al. (2018) the authors use 16 and 8 bits fixed-point representation to train DNNs.
Using fewer bits results in dramatic memory savings. This has motivated research into methods that use a single bit to represent a scalar weight: In Courbariaux et al. (2015) the authors train models with weights quantized to the values in {−1, 1}. While this results in a high level of compression, model accuracy can drop significantly. Li et al. (2016) and Zhu et al. (2016) reduce the accuracy gap between full precision and quantized models by considering ternary quantization (using the values in {−1, 0, 1}), at the cost of slightly less compression. To further improve the computational efficiency, the intermediate activation tensors (feature maps) can also be quantized. When this is the case, an implementation can use high-performance operators that act on quantized inputs, for example a convolutional block depicted in Figure 1(left). This idea has been explored in (Courbariaux et al., 2016; Rastegari et al., 2016; Zhou et al., 2016; Hubara et al., 2017; Mishra et al., 2017; Lin et al., 2017; Cai et al., 2017; Ghasemzadeh et al., 2018; Zhang et al., 2018a; Choi et al., 2018), and many other works.
We call a mapping from a tensor with full precision entries to a tensor with the same shape but with values in {−1, 1} a binary quantization. When both weights and activations of a DNN are quantized using binary quantization, called Binary Neural Network (BNN), fast and power-efficient kernels which use bitwise operations can be implemented. Observe that the inner-product between two vectors with entries in {−1, 1} can be written as bitwise XNor operations followed by bitcounting (Courbariaux et al., 2016). However, the quantization of both weights and activations further reduces the model accuracy. In this work, we focus on improving the accuracy of the quantized model through improved quantization. The computational cost remains similar to the previous BNNs (Rastegari et al., 2016; Hubara et al., 2017).

heading: 1.4 MAIN CONTRIBUTIONS
text: In this work, we analyze the accuracy of binary quantization when applied to both weights and activations of a DNN, and propose methods to improve the quantization accuracy:
• We present an analysis of the quantization error and show that scaled binary quantization is a good approximation (Section 2).
• We derive the optimal 1-bit (Section 3.1.1), 2-bits (Section 3.2.2), and ternary (Section 3.2.3) scaled binary quantization algorithms. • We propose a greedy k-bits quantization algorithm (Section 3.2.4). • Experiments on the ImageNet dataset show that the optimal algorithms have reduced quan-
tization error, and lead to improved classification accuracy (Section 5).

heading: 2 LOW-RANK BINARY QUANTIZATION
text: Binary quantization (that maps entries of a tensor to {−1, 1}) of weights and activation tensors of a neural network can significantly reduce the model accuracy. A remedy to retrieve this accuracy loss is to scale the binarized tensors with few full precision values. For example, Hubara et al. (2017) learn a scaling for each channel from the parameters of batch-normalization, and Rastegari et al. (2016) scale the quantized activation tensors using the channel-wise average of pixel values.
In this section, using low-rank matrix analysis, we analyze different scaling strategies. We conclude that multiplying the quantized tensor by a single scalar, which is computationally the most efficient option, has approximately the same accuracy as the more expensive alternatives.
We introduce the rank-1 binary quantization– an approximation to a matrix X ∈ Rm×n: X 'X1 S, (1)
where X1 ∈ Rm×n is a rank-1 matrix, S ∈ {−1, 1}m×n, and is element-wise multiplication (Hadamard product). Note that this approximation is also defined for tensors, after appropriate reshaping. For example, for an image classification task, we can reshape the output of a layer of a DNN with shape h × w × n, where h, w, and n are height, width, and number of channels, respectively, into an m× n matrix with m = hw rows and one column per channel. We define the error of a rank-1 binary quantization as ‖X−X1 S‖F , where ‖ ‖F is the Frobenius norm. Entries of S are in {−1, 1}, therefore, the quantization error is equal to ‖X S−X1‖F . Note that ‖X S‖2F (the total energy), which is equal to sum of the squared singular values, is the same for any S. Different choices of S change the distribution of the total energy among components of the Singular Value Decomposition (SVD) of X S. The optimal rank-1 binary quantization is achieved when most of the energy of X S is in its first component. In Rastegari et al. (2016), the authors proposed to quantize the activations by applying the sign function and scale them by their channel-wise average. We can formulate this scaling strategy as a special rank-1 binary quantization X ' a1> sign(X), where
ai = ∑n j=1 |Xi,j | n for 1 ≤ i ≤ m , sign(x) = {−1 if x < 0 1 if x ≥ 0 , (2)
and 1 is an n-dimensional vector with all entries 1.
In Appendix A we show that the optimal rank-1 binary quantization is given by S = sign(X) and X1 = truncated1-SVD(|X|), where sign(X) is the element-wise sign of X , and truncated1-SVD(|X|) = σ1u1v>1 is the first component of the SVD of X sign(X) = |X|. Moreover, we empirically analyze the accuracy of the optimal rank-1 binary quantization for a random matrix X , where its entries are i.i.d. ∼ N (0, 1). This is a relevant example since after the application of Batch Normalization (BN) (Ioffe & Szegedy, 2015) activation tensors are expected to have a similar distribution. The first singular value of |X| captures most of the energy σ21(|X|)/‖X‖2F ' 0.64, and the first left and right singular vectors are almost constant vectors. Therefore, a scalar multiple of sign(X) approximates X well: X ' σ1u1v>1 sign(X) ' v 11> sign(X) = vsign(X), where v ∈ R≥0. We use this computationally efficient approximation called scaled binary quantization.

heading: 3 SCALED BINARY QUANTIZATION
text: In Section 2 we showed that scaled binary quantization is a good approximation to activation and weight tensors of a DNN. Next we show how we can further improve the accuracy of scaled binary quantization using more bits. To simplify the presentation (1) we flatten matrix X ∈ Rm×n in to
a vector x ∈ RN with N = mn, and (2) we assume the entries of x are different realizations of a random variable x with an underlying probability distribution p(x). In practice, we compute all statistics using their unbiased estimators from vector x (e.g., ∑ i xi/N is an unbiased estimator of Ex∼p[x]). Furthermore, for f : R → R, we denote entrywise application of f to x by f(x). The quantized approximation of x is denoted by xq , and the error (loss) of quantization is ‖x − xq‖2. All optimal solutions are with respect to this error and hold for an arbitrary distribution p(x).

heading: 3.1 1-BIT QUANTIZATION
text: A 1-bit scaled binary quantization of x is:
x ' xq = vs(x), (3) which is determined by a scalar v ∈ R≥0 and a function s : R→ {−1, 1}. Finding the optimal 1-bit scaled binary quantization can be formulated as the following optimization problem:
minimize v,s ∫ +∞ −∞ p(x)(vs(x)− x)2dx
s.t. s : R→ {−1, 1}, v ∈ R≥0 (4)

heading: 3.1.1 OPTIMAL 1-BIT ALGORITHM
text: The solution of problem (4) is given by v = Ex∼p[|x|] and s(x) = sign(x) (for the proofs see Appendix B). Therefore, for a vector x the optimal scaled binary quantization is given by
x ' xq = ∑
i |xi| N sign(x), (5)
where ∑
i |xi| N is an unbiased estimator of Ex∼p[|x|].
3.2 k-BITS QUANTIZATION
We can further improve the accuracy of scaled binary quantization by adding more terms to the approximation (3). A k-bits scaled binary quantization of x is
x ' xq = k∑
i=1
visi(x), (6)
which is determined by a set of k pairs of scalars vi’s and functions si : R → {−1, 1}. Observe that any permutation of (vi, si)’s results in the same quantization. To remove ambiguity, we assume v1 ≥ . . . ≥ vk ≥ 0. When both weights, w, and activations, x, are quantized using scaled binary quantization (6), their inner-product can be written as:
〈xq,wq〉 = ka∑ i=1 kw∑ j=1 vai v w j 〈sai , swj 〉, (7)
where xq = ∑ka
i=1 v a i s a i and w
q = ∑kw
j=1 v w j s w i are quantized activations and weights with k a and kw bits, respectively, sai = s a i (x), and s w j = s w j (w). This inner-product can be computed efficiently using bitwise XNors followed by bit-counting (see Figure 1(right) with ka = 2 and kw = 1).
Finding the optimal k-bits scaled binary quantization can be formulated as:
minimize si,vi ∫ +∞ −∞ p(x) (( k∑
i=1
visi(x)
) − x )2 dx
s.t. ∀ 1 ≤ i ≤ k si : R→ {−1, 1}, v1 ≥ v2 ≥ . . . ≥ vk ≥ 0 (8)
This is an optimization problem with a non-convex domain for all k ≥ 1. We solve the optimization for k = 1 in Section 3.1 and k = 2 in Section 3.2.2 for arbitrary distribution p(x). We also provide an approximate solution to (8) in Section 3.2.4 using a greedy algorithm.
Discussion: A general k-bits quantizer maps full precision values to an arbitrary set of 2k numbers, not necessarily in the form of (6). The optimal quantization in this case can be computed using the Lloyd’s algorithm (Lloyd, 1982). While a general k-bits quantization has more representation power compared to k-bits scaled binary quantization, it does not allow an efficient implementation based on bitwise operations. Fixed-point representation (as opposed to floating point) is also in the form of (6) with an additional constant term. However, fixed-point quantization uniformly quantizes the space, therefore, it can be significantly inaccurate for small values of k.

heading: 3.2.1 FOLDABLE QUANTIZATION
text: In this section, we introduce a special family of k-bits scaled binary quantizations that allow fast computation of the quantized values. We name this family of quantizations foldable. A k-bits scaled binary quantization given by (vi, si)’s is foldable if the following conditions are satisfied:
si(x) = sign(x− i−1∑ j=1 vjsj(x)) for 1 ≤ i ≤ k (9)
When the foldable condition is satisfied, given vi’s, we can compute the si(x)’s in (6) efficiently by applying the sign function.

heading: 3.2.2 OPTIMAL 2-BITS ALGORITHM
text: In this section, we present the optimal 2-bits binary quantization algorithm, the solution of (8) for k = 2. In Appendix C we show that the optimal 2-bits binary quantization is foldable and the scalars v1 and v2 should satisfy the following optimality conditions:
v1 = 1
2 (Ex∼p[|x| | |x| > v1] + Ex∼p[|x| | |x| ≤ v1]) (10)
v2 = 1
2 (Ex∼p[|x| | |x| > v1]− Ex∼p[|x| | |x| ≤ v1]) (11)
In Figure 2 we visualize the conditional expectations that show up in (10) for a random variable x with standard normal distribution. The optimal v1 lies on the intersection of the identity line and average of the conditional expectations in (10).
For a given vector x ∈ RN we can solve for v1 in (10) efficiently. We substitute the conditional expectations in (10) by conditional average operators as their unbiased estimators. (10) implies that for the optimal v1, the average of the entries in |x| smaller than v1 (an estimator of Ex∼p[|x| | |x| ≤ v1] ) and the average of the entries greater than v1 (an estimator of Ex∼p[|x| | |x| > v1]) should be equidistant form v1. Note that (10) may have more than one solution, which are local minima of the objective function in (8). We find all the values that satisfy this condition in O(N logN) time. We first sort entries of x based on their absolute value and compute their cumulative sum. Then with one pass we can check whether (10) is satisfied for each element of x. We evaluate the objective function in (8) for each local minima, and retain the best. After v1 is calculated v2 is simply computed from (11). As explained in Section 4, this process is only done during the training. In our experiments, finding the optimal 2-bits quantization increased the training time by 35% compared to the 2-bits greedy algorithm (see Section 3.2.4). Sine the optimal 2-bits binary quantization is foldable, after recovering v1 and v2, we have s1(x) = sign(x) and s2(x) = sign(x− v1sign(x)).

heading: 3.2.3 OPTIMAL TERNARY ALGORITHM
text: The optimization domain of (8) for k = 2 over the scalars is illustrated in Figure 2(right). The boundaries of the domain, v2 = 0 and v1 = v2 = v, correspond to 1-bit binary and ternary (Li et al., 2016) quantizations, respectively. The scaled ternary quantization maps each full precision value x to {−2v, 0, 2v}. Ternary quantization needs 2-bits for representation. However, when a hardware with sparse calculation support is available, for example as in EIE (Han et al., 2016a), using ternary quantization can be more efficient compared to general 2-bits quantization. In Appendix D we show that the optimal scaled ternary quantization is foldable and the scalar v should satisfy:
v = 1
2 Ex∼p[|x| | |x| > v] (12)
The process of solving for v in (12) is similar to that of solving for v1 in (10) as described above.
3.2.4 k-BITS GREEDY ALGORITHM
In this section, we propose a greedy algorithm to compute k-bits scaled binary quantization, which we call Greedy Foldable (GF). It is given in Algorithm 1.
Algorithm 1: k-bits Greedy Foldable (GF) binary quantization: compute xq given x r ← x for i← 1 to k do
vi← mean(abs(r)) si ← sign(r) // element-wise sign. For gradient of sign use STE. r← r − visi // compute new residual.
end return x− r
In GF algorithm we compute a sequence of residuals. At each step, we greedily find the best si and vi for the current residual using the optimal 1-bit binary quantization (5). Note that for k = 1 the GF is the same as the optimal 1-bit binary quantization.
Few of the other papers that have tackled the k-bits binary quantization to train quantized DNNs are as follows. In ReBNet (Ghasemzadeh et al., 2018), the authors proposed an algorithm similar to Algorithm 1, but considered vi’s as trainable parameters to be learned by back-propagation. Lin et al. (2017) and Zhang et al. (2018a) find k-bits binary quantization via alternating optimization for si’s and vi’s. Note that, all these methods produce sub-optimal solutions.

heading: 4 TRAINING BINARY NETWORKS
text: The loss functions in our quantized neural networks are non-differentiable due to the sign function in the quantizers. To address this challenge we use the training algorithm proposed in Courbariaux et al. (2015). To compute the gradient of the sign function we use the Straight Through Estimator (STE) (Bengio et al., 2013): d/dx sign(x) = 1|x|≤1. During the training we keep the full precision weights and use Stochastic Gradient Descent (SGD) to gradually update them in back-propagation. In the forward-pass, only the quantized weights are used.
During the training we compute quantizers (for both weights and activations) using the online statistics, i.e., the scalars in a k-bits scaled binary quantization (6) are computed based on the observed values. During the training we also store the running average of these scalars. During inference we use the stored quantized scalars to improve the efficiency. This procedure is similar to the update of the batch normalization parameters in a standard DNN training (Ioffe & Szegedy, 2015).

heading: 5 EXPERIMENTS
text: We conduct experiments on the ImageNet dataset (Deng et al., 2009) using the ResNet-18 architecture (He et al., 2016). The details of the architecture and training are provided in Appendix E.
We conduct three sets of experiments: (1) evaluate quantization error of activations of a pre-trained DNN, (2) evaluate the quantization error based on the classification accuracy of a post-training quantized network, and (3) evaluate the classification accuracy of during-training quantized networks. We report the quantization errors of the proposed binary quantization algorithms (optimal 1-bit, 2- bits, ternary, and the greedy foldable quantizations) and compare with the state-of-the-art algorithms BWN-Net (Rastegari et al., 2016), XNor-Net (Rastegari et al., 2016), TWN-Net (Li et al., 2016), DoReFa-Net (Zhou et al., 2016), ABC-Net (Lin et al., 2017), and LQ-Net (Zhang et al., 2018a).

heading: 5.1 QUANTIZATION ERROR OF ACTIVATIONS
text: To quantify the errors of the introduced binary quantization algorithms we adopt the analysis performed by Anderson & Berg (2017). They show that the angle between x and xq can be used as a measure of the accuracy of a quantization scheme. They prove that when xq = sign(x) and elements of x are i.i.d. ∼ N (0, 1), ∠(x,xq) converges to ∼ 37 degrees for large N . Here we use the real data distribution. We trained a full precision network. We compute the activation tensors at each layer for a set of 128 images. In Figure 3 we show the angle between the full precision and quantized activations for different layers. When the optimal quantization is used, a significant reduction in the angle is observed compared to the greedy algorithm. The optimal 2-bits quantization is even better than the greedy 4-bits quantization for later layers of the network, for which activation tensors have more skewed distribution, make it harder for quantization in form of (6). Furthermore, the accuracy of the optimal quantization has less variance with respect to different input images and different layers of the network.

heading: 5.2 POST-TRAINING QUANTIZATION
text: In this section we apply post-training quantization to the weights of a pre-trained full precision network. We then use the quantized network for inference and report the classification accuracy. This procedure can result in an acceptable accuracy for a moderate number of bits (e.g., 16 or 8). However, the error significantly grows with a lower number of bits, which is the case in this experiment. Therefore, we only care about the relative differences between different quantization strategies. This experiment demonstrates the effect of quantization errors on the accuracy of the quantized DNNs.
The results are shown in the top half of Table 1. When the optimal 2-bits quantization is used, significant accuracy improvement (more than one order of magnitude) is observed compared to the greedy 2-bits quantization, which illustrate the effectiveness of the optimal quantization.

heading: 5.3 DURING-TRAINING QUANTIZATION
text: To achieve higher accuracy we apply quantization during the training, so that the model can adapt to the quantized weights and activations. In the bottom half of Table 1, we report the accuracies of the during-training quantized DNNs, all trained with the same setup. We use 1-bit binary quantization for weights, and use different quantization algorithms for activations. When quantization is applied during-training, significantly higher accuracies are achieved. Similar to the previous experiments the optimal quantization algorithm achieves a better accuracy compared to the greedy.
In Table 2 we report results from the related works in which ResNet-18 architecture with quantized weights and/or activations is trained on the ImageNet dataset for the classification task. We report the mean and standard deviation of the model accuracy over 5 runs when our algorithms are used. Note that for 1-bit quantization the Greedy Foldable (GF) algorithm is the same with the optimal 1-bit binary quantization. In Opt* we used 2× larger batch-size compared to Opt but with the same number of optimization steps. As shown in the Table 2 the proposed quantization algorithms match or improve the accuracies of the state-of-the-art BNNs.
aThis result is taken from (Zhang et al., 2018a).

heading: 6 CONCLUSION
text: In this work, we analyze the accuracy of binary quantization to train DNNs with quantized weights and activations. We discuss methods to improve the accuracy of quantization, namely scaling and using more bits.
We introduce the rank-1 binary quantization, as a general scaling scheme. Based on a singular value analysis we motivate using the scaled binary quantization, a computationally efficient scaling strategy. We define a general k-bits scaled binary quantization. We provide provably optimal 1-bit, 2-bits, and ternary quantizations. In addition, we propose a greedy k-bits quantization algorithm. We show results for post and during-training quantization, and demonstrate significant improvement in accuracy when optimal quantization is used. We compare the proposed quantization algorithms with state-of-the-art BNNs on the ImageNet dataset and show improved classification accuracies.

heading: A OPTIMAL RANK-1 BINARY QUANTIZATION
text: In this section, we find the optimal rank-1 binary quantization of an m by n matrix X that is discussed in Section 2:
minimize X1,S ‖X −X1 S‖F
s.t. S ∈ {−1, 1}m×n
X1 ∈ Rm×n rank(X1) = 1
(13)
First, observe that the element-wise multiplication by −1 and +1 does not change the Frobenius norm. Therefore:
min S,X1 = ‖X −X1 S‖F = min S,X1 = ‖(X −X1 S) S‖F = min S,X1 ‖X S −X1‖F (14)
Furthermore, note that min S,X1 ‖X S −X1‖2F = σ22(X S) + . . .+ σ2r(X S) (15)
Here σi(X S) is the i’th singular value of X S and r is its rank. In addition for any S: r∑
i=1
σ2i (X S) = ‖X S‖2F = ‖X‖2F (16)
Hence, to minimize the sum in (15) we need to find an S for which σ21(X S) is maximized: min S,X1 ‖X S −X1‖2F = ‖X‖2F −max S σ21(X S) (17)
σ1(X S) = ‖X S‖2 is the 2-norm of X S. Therefore: max S σ21(X S) = max S max ‖r‖2=1 ‖(X S)r‖22 (18) For any S and r ∈ Rn we have ‖(X S)r‖22 ≤ ‖ |X| |r| ‖22 since for 1 ≤ i ≤ m we have |∑j Si,jXi,jrj | ≤ ∑j |Xi,j | |rj |. Here |X| = X sign(X) is the element-wise absolute value of X . Note that for S = sign(X) and r with positive values the inequality becomes an equality. Therefore:
max S max ‖r‖2=1 ‖(X S)r‖22 = max‖r‖2=1 ‖|X||r|‖22 (19)
Observe that the element-wise absolute value does not change the vector norm, i.e. ‖|r|‖2 = ‖r‖2, and hence |r| is a unit vector when r is. Also for any r we have ‖|X|r‖22 ≤ ‖|X| |r|‖22 since for 1 ≤ i ≤ m we have |∑j |Xi,j |rj | ≤∑j |Xi,j ||rj |. So we have
max ‖r‖2=1 ‖|X||r|‖22 = max‖r‖2=1 ‖|X|r‖22 = σ21(|X|) (20)
Therefore, we showed that S = sign(X) and X1 equal to the best rank-1 approximation of |X| (i.e. the first term in its SVD) is a solution of (13).
For an X with i.i.d. ∼ N (0, 1) entries we show the singular values and first left and right singular vectors of |X| in Figure 4. Observe that the first singular value of |X| captures most of the energy σ21(|X|)/‖X‖2F ' 0.64. The fraction of energy captured by the first component of SVD converges to the squared mean of the standard folded normal distribution (2/π) for large square matrices. Also note that the first left and right singular vectors are almost constant, i.e., they can be written as α1 for some α ∈ R.

heading: B OPTIMAL SCALED BINARY QUANTIZATION
text: In this section, we solve the following optimization problem corresponding to the optimal 1-bit scaled binary quantization as discussed in Section 3.1:
minimize v,s ∫ +∞ −∞ p(x)(vs(x)− x)2dx
s.t. s : R→ {−1, 1} v ∈ R≥0
(21)
Here p is a probability distribution function. First, observe that:
∀x ∈ R : (v − x)2 < (−v − x)2 iff x > 0 (22) Therefore, the optimal choice for function s is s(x) = sign(x). So we can rewrite (21) as follows:
minimize v ∫ +∞ −∞ p(x)(v − |x|)2dx
s.t. v ∈ R≥0 (23)
Setting the gradient of the objective function in (23) with respect to v to zero, we get:
v = ∫ +∞ −∞ p(x)|x|dx∫ +∞ −∞ p(x)dx = Ex∼p[|x|] (24)
Hence, we showed that the optimal 1-bit scaled binary quantization maps x to Ex∼p[|x|] sign(x).

heading: C OPTIMAL 2-BITS BINARY QUANTIZATION
text: In this section, we solve the following optimization problem corresponding to the optimal 2-bits binary quantization as discussed in Section 3.2.2:
minimize v1,v2,s1,s2 ∫ +∞ −∞ p(x) (v1s1(x) + v2s2(x)− x)2 dx
s.t. s1, s2 : R→ {−1, 1} v1 ≥ v2 ≥ 0
(25)
First, we show that the optimal 2-bits binary quantization is foldable, i.e., ∀x ∈ R s1(x) = sign(x) and s2(x) = sign(x− v1s1(x)). Observe that
f(x) = (v1s1(x) + v2s2(x)− x)2 = v21 ( 1 +
v2 v1 s1(x)s2(x)− s1(x)x v1
)2 ≥
v21
( 1 +
v2 v1 s1(x)s2(x)− |s1(x)x| v1
)2 = g(x)
(26)
The inequality in (26) holds because v1 ≥ v2, and therefore, 1 + v2v1 s1(x)s2(x) ≥ 0. The objective function in (25) is a weighted average of f(x) with non-negative weights. For x ∈ R the inequality is strict if s1(x) 6= sign(x). In that case, flipping the value of both s1(x) and s2(x) reduces f(x) to a strictly smaller value g(x). Hence, the optimal solution of (25) should satisfy s1(x) = sign(x) for all x ∈ R.
For any v1 and s1 if we consider y = x − v1s1(x), the problem reduces to the 1-bit binary quantization for y. Based on the result showed in Appendix B for the optimal solution we have s2(x) = sign(y) = sign(x − v1s1(x)). This completes the proof to show that the optimal 2-bits binary quantization is foldable.
Next, we find the optimal values for v1 and v2. If we substitute s1(x) = sign(x) and s2(x) = sign(x− v1s1(x)) in (25) we can decompose R into four segments and write:
e(v1, v2) = ∫ +∞ −∞
p(x) (v1s1(x) + v2s2(x)− x)2 dx =∫ −v1 −∞ p(x)(x+ v1 + v2) 2dx + ∫ 0 −v1
p(x)(x+ v1 − v2)2dx +∫ v1 0 p(x)(x− v1 + v2)2dx + ∫ +∞ v1
p(x)(x− v1 − v2)2dx =∫ v1 0 q(x)(x− v1 + v2)2dx + ∫ +∞ v1 q(x)(x− v1 − v2)2dx
(27)
Here e(v1, v2) is the error as a function of v1 and v2, and q(x) = p(−x) + p(x) is the folded distribution function. Assuming the optimal point occurs in the interior of the domain, it should satisfy the zero gradient condition: ∂e/∂v1 = ∂e/∂v2 = 0. Taking derivative from (27) with respect to v1 and v2 and set it to zero we get:
v1 = ∫ v1 0 xq(x)dx + ∫ +∞ v1 xq(x)dx +v2 (∫ v1 0 q(x)dx− ∫ +∞ v1 q(x)dx ) v2 = − ∫ v1 0 xq(x)dx+ ∫ +∞ v1 xq(x)dx +v1 (∫ v1 0 q(x)dx− ∫ +∞ v1 q(x)dx
) (28) We can simplify (28) and rewrite v1 and v2 in terms of the following conditional expectations:
v1 = 1
2 (Ex∼p[|x| | |x| > v1] + Ex∼p[|x| | |x| ≤ v1])
v2 = 1
2 (Ex∼p[|x| | |x| > v1]− Ex∼p[|x| | |x| ≤ v1])
(29)
Hence, the optimal values of v1 and v2 can be obtained by solving for v1 and v2 in (29). The optimization domain has two boundaries. One is when v2 = 0. This reduces the problem to 1- bit binary quantization. The optimal solution in that case is discussed in Appendix B. The other boundary is when v1 = v2. This results in the ternary quantization. The optimal solution in this case is discussed in Appendix D.

heading: D OPTIMAL TERNARY QUANTIZATION
text: In this section, we find the optimal symmetric ternary quantization, that is to map a full precision value x to a discrete set {−2v, 0, 2v} as discussed in Section 3.2.3. Finding the optimal mapping can be formulated as the following optimization problem:
minimize v,s1,s2 ∫ +∞ −∞ p(x) (vs1(x) + vs2(x)− x)2 dx
s.t. s1, s2 : R→ {−1, 1} v ≥ 0
(30)
First, the above form is a special case of (25), hence, using the same argument as in Appendix C we can show that there is a foldable optimal solution: s1(x) = sign(x) and s2(x) = sign(x− vs1(x)). Then the total error as a function of v can be written as:
e(v) = ∫ v 0 q(x)x2dx + ∫ +∞ v q(x)(x− 2v)2dx (31)
where q(x) is the folded probability distribution function. Taking derivative from (31) and setting it to zero, we get:
v =
∫ +∞ v xq(x)dx
2 ∫ +∞ v q(x)dx = 1 2 Ex∼p[|x| | |x| > v] (32)

heading: E DETAILS OF TRAINING RESNET ON IMAGENET
text: In this section, we explain the details of how the DNN results reported in this paper are produced. All results correspond to the ResNet-18 architecture trained on the ImageNet dataset for the classification task. We use the standard training and validation splits of the ImageNet dataset. We followed a similar architecture as XNor-Net (Rastegari et al., 2016). The convolutional block that we use is depicted in Figure 1(left). We use ReLU non-linearity before the batch normalization as suggested by (Rastegari et al., 2016). Also, we find it important to use bounded dynamic range, and therefore clip the values to [−d, d]. We use d = 2, 3, 5, and 8 for k = 1, 2, 3, and 4 bits quantizations, respectively. Similar to the other BNNs for the first and last layers we use full precision. Also, as suggested by Choi et al. (2018) we use full precision short-cuts in ResNet architecture, which adds a small computational/memory overhead. We quantize weights per filter and activations per layer. As Cai et al. (2017) we use first-order polynomial learning-rate annealing schedule (from 10−1 to 10−4) and train for 120 epochs. We do not use weight decay. For the data augmentation we use the standard methods used to train full precision ResNet architecture. For training we apply random resize and crop to 224×224, followed by random horizontal flipping, color jittering, and lightening. For test we resize the images to 256×256 followed by a center cropping to 224×224.

Review summaries:
This paper proposes a new family of quantized neural networks, where the weights are quantized based on fixed precisions. The authors proposed the optimal 1-bit/2-bit/ternary quantization schemes based on minimizing the L_2 loss. The authors proposed a greedy algorithm to approximate the optimal k-bit quantization.  The authors showed through extensive experiments on real DNNs that the proposed optimal quantization (Opt in the tables) can give better generalization as compared to several state-of-the-art alternative methods.