Title: OPTIMAL BINARY QUANTIZATION FOR DEEP NEURAL NETWORKS

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.

1. INTRODUCTION:

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.

1.1. ARCHITECTURE OPTIMIZATION:

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.

1.2. PRUNING AND COMPRESSION:

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.

1.3. LOW-PRECISION ARITHMETIC AND QUANTIZATION:

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) .

ReLU BN Clip:

Quantizer Quantizer

x w

Conv +1 -1 -1 +1 ... v v v +1 -1 -1 +1 ... + x +1 -1 -1 +1 ...

XNor Conv:

XNor Conv The convolutional block used in this paper. Right: When both weights and activations are quantized using binary quantization, the convolution can be implemented efficiently using bitwise XNor and bit-counting operations. See Section 3.2 for more details.

1.4. MAIN CONTRIBUTIONS:

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 quantization error, and lead to improved classification accuracy (Section 5).

2 LOW-RANK BINARY QUANTIZATION 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 ∈ R m×n :

EQUATION

where X 1 ∈ R m×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 -X 1 S F , where F is the Frobenius norm. Entries of S are in {-1, 1}, therefore, the quantization error is equal to X S-X 1 F . Note that X S 2 F (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

EQUATION

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 X 1 = truncated 1 -SVD(|X|), where sign(X) is the element-wise sign of X, and

truncated 1 -SVD(|X|) = σ 1 u 1 v 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 σ 2 1 (|X|)/ X 2 F 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 σ 1 u 1 v 1 sign(X) v 11 sign(X) = vsign(X)

, where v ∈ R ≥0 . We use this computationally efficient approximation called scaled binary quantization.

3. SCALED BINARY QUANTIZATION:

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 ∈ R m×n in to a vector x ∈ R N 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 x i /N is an unbiased estimator of E x∼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 x q , and the error (loss) of quantization is xx q 2 . All optimal solutions are with respect to this error and hold for an arbitrary distribution p(x).

3.1. 1-BIT QUANTIZATION:

A 1-bit scaled binary quantization of x is:

EQUATION

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)(v s(x) -x) 2 dx s.t. s : R → {-1, 1}, v ∈ R ≥0 (4) 3.1.1 OPTIMAL 1-BIT ALGORITHM

The solution of problem ( 4) is given by v = E x∼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

EQUATION

where

i |xi| N is an unbiased estimator of E x∼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

EQUATION

which is determined by a set of k pairs of scalars v i 's and functions s i : R → {-1, 1}. Observe that any permutation of (v i , s i )'s results in the same quantization. To remove ambiguity, we assume

v 1 ≥ . . . ≥ v k ≥ 0.

When both weights, w, and activations, x, are quantized using scaled binary quantization (6), their inner-product can be written as:

EQUATION

where

x q = k a i=1 v a i s a i and w q = k w

j=1 v w j s w i are quantized activations and weights with k a and k w bits, respectively, s a i = 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 k a = 2 and k w = 1).

Finding the optimal k-bits scaled binary quantization can be formulated as:

minimize si,vi +∞ -∞ p(x) k i=1 v i s i (x) -x 2 dx s.t. ∀ 1 ≤ i ≤ k s i : R → {-1, 1}, v 1 ≥ v 2 ≥ . . . ≥ v k ≥ 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 2 k 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.

3.2.1. FOLDABLE QUANTIZATION:

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 (v i , s i )'s is foldable if the following conditions are satisfied:

s i (x) = sign(x - i-1 j=1 v j s j (x)) for 1 ≤ i ≤ k (9)

When the foldable condition is satisfied, given v i 's, we can compute the s i (x)'s in (6) efficiently by applying the sign function.

3.2.2. OPTIMAL 2-BITS ALGORITHM:

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 v 1 and v 2 should satisfy the following optimality conditions:

EQUATION

EQUATION

In Figure 2 we visualize the conditional expectations that show up in (10) for a random variable x with standard normal distribution. The optimal v 1 lies on the intersection of the identity line and average of the conditional expectations in (10).

For a given vector x ∈ R N we can solve for v 1 in (10) efficiently. We substitute the conditional expectations in (10) by conditional average operators as their unbiased estimators. (10) implies that for the optimal v 1 , the average of the entries in |x| smaller than v 1 (an estimator of

E x∼p [|x| | |x| ≤ v 1 ]

) and the average of the entries greater than v 1 (an estimator of

E x∼p [|x| | |x| > v 1 ]

) should be equidistant form v 1 . 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 log N ) 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 v 1 is calculated v 2 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 v 1 and v 2 , we have s 1 (x) = sign(x) and s 2 (x) = sign(xv 1 sign(x)).

3.2.3. OPTIMAL TERNARY ALGORITHM:

The optimization domain of (8) for k = 2 over the scalars is illustrated in Figure 2 (right). The boundaries of the domain, v 2 = 0 and v 1 = v 2 = 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:

EQUATION

The process of solving for v in ( 12) is similar to that of solving for v 1 in (10) as described above.

0.0 0 .5 1 .0 1 .5 2 .0 2 .5 v 0 1 2 3 E l = E[|x| | |x| < v] E r = E[|x| | |x| > v] (E l + E r )/2 v v 1 v = v ( T e r n a r y Q u a n t iz a t io n ) v = 0 (1-bit Quantization) v > v > 0 (2-bits Quantization) v v

Figure 2 : Left: The conditional expectations in (10) for a random variable x with standard normal distribution. The optimal value for 2-bits quantization is shown with a solid dot. Right: Optimization domain of (8) for k=2. The boundaries correspond to 1-bit and ternary quantizations.

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 x q given x r ← x for i ← 1 to k do v i ← mean(abs(r)) s i ← sign(r) // element-wise sign. For gradient of sign use STE.

r ← r -v i s i // compute new residual. end return x -r

In GF algorithm we compute a sequence of residuals. At each step, we greedily find the best s i and v i 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 v i '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 s i 's and v i 's. Note that, all these methods produce sub-optimal solutions.

4. TRAINING BINARY NETWORKS:

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) .

5. EXPERIMENTS:

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, 2bits, 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) .

5.1. QUANTIZATION ERROR OF ACTIVATIONS:

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 x q can be used as a measure of the accuracy of a quantization scheme. They prove that when x q = sign(x) and elements of x are i.i.d. ∼ N (0, 1), ∠(x, x q ) 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. are number of bits to quantize activations and weights, respectively. T, Opt, GF, and FP refer to ternary, optimal, Greedy Foldable, and full precision, respectively.

5.2. POST-TRAINING QUANTIZATION:

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.

5.3. DURING-TRAINING QUANTIZATION:

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 a This result is taken from (Zhang et al., 2018a) .

6. CONCLUSION:

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. 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) follows:

EQUATION

Setting the gradient of the objective function in ( 23) with respect to v to zero, we get:

EQUATION

Hence, we showed that the optimal 1-bit scaled binary quantization maps x to E x∼p [|x|] sign(x).

C OPTIMAL 2-BITS BINARY QUANTIZATION:

In this section, we solve the following optimization problem corresponding to the optimal 2-bits binary quantization as discussed in Section 3.2.2:

EQUATION

First, we show that the optimal 2-bits binary quantization is foldable, i.e., ∀x ∈ R s 1 (x) = sign(x) and s 2 (x) = sign(xv 1 s 1 (x)). Observe that

EQUATION

The inequality in (26) holds because v 1 ≥ v 2 , and therefore, 1 + v2 v1 s 1 (x)s 2 (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 s 1 (x) = sign(x). In that case, flipping the value of both s 1 (x) and s 2 (x) reduces f (x) to a strictly smaller value g(x). Hence, the optimal solution of (25) should satisfy s 1 (x) = sign(x) for all x ∈ R.

For any v 1 and s 1 if we consider y = xv 1 s 1 (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 s 2 (x) = sign(y) = sign(xv 1 s 1 (x)). This completes the proof to show that the optimal 2-bits binary quantization is foldable.

Next, we find the optimal values for v 1 and v 2 . If we substitute s 1 (x) = sign(x) and s 2 (x) = sign(xv 1 s 1 (x)) in ( 25) we can decompose R into four segments and write:

e(v 1 , v 2 ) = +∞ -∞ p(x) (v 1 s 1 (x) + v 2 s 2 (x) -x) 2 dx = -v1 -∞ p(x)(x + v 1 + v 2 ) 2 dx + 0 -v1 p(x)(x + v 1 -v 2 ) 2 dx + v1 0 p(x)(x -v 1 + v 2 ) 2 dx + +∞ v1 p(x)(x -v 1 -v 2 ) 2 dx = v1 0 q(x)(x -v 1 + v 2 ) 2 dx + +∞ v1 q(x)(x -v 1 -v 2 ) 2 dx (27)

Here e(v 1 , v 2 ) is the error as a function of v 1 and v 2 , 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/∂v 1 = ∂e/∂v 2 = 0. Taking derivative from ( 27) with respect to v 1 and v 2 and set it to zero we get: 

We can simplify (28) and rewrite v 1 and v 2 in terms of the following conditional expectations:

EQUATION

Hence, the optimal values of v 1 and v 2 can be obtained by solving for v 1 and v 2 in (29). The optimization domain has two boundaries. One is when v 2 = 0. This reduces the problem to 1bit binary quantization. The optimal solution in that case is discussed in Appendix B. The other boundary is when v 1 = v 2 . This results in the ternary quantization. The optimal solution in this case is discussed in Appendix D.

D OPTIMAL TERNARY QUANTIZATION:

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: 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: s 1 (x) = sign(x) and s 2 (x) = sign(xvs 1 (x)).

Then the total error as a function of v can be written as:

EQUATION

)

where q(x) is the folded probability distribution function. Taking derivative from (31) and setting it to zero, we get:

EQUATION

:



Figures and Tables:

Figure1: Left: The convolutional block used in this paper. Right: When both weights and activations are quantized using binary quantization, the convolution can be implemented efficiently using bitwise XNor and bit-counting operations. See Section 3.2 for more details.

Figure 3: The angle between the full precision and the quantized activations for different layers of a trained full precision ResNet-18 architecture on ImageNet. The 95% confidence interval over different input images is shown.

Figure 4: Left: Distribution of energy for |X|, where X ∈ R 30×30 is a standard normal random matrix. Right: Entries of the first left and right singular vectors of |X| (shown in green and blue) are almost constant.

Validation accuracy of a quantizedResNet-18 trained on ImageNet. k a and k w

Table content: <table><tr><td>5</td></tr></table>

Table 2 the proposed quantization algorithms match or improve the accuracies of the state-of-the-art BNNs. Comparison with state-of-the-art quantization. Opt and GF are the proposed optimal and greedy foldable quantization algorithms, respectively. T and FP refer to ternary and full precision network, respectively.

Table content: <table><tr><td colspan="5">Method (ResNet-18 on ImageNet) k a k w Val. top-1 Val. top-5</td></tr><tr><td>XNor-Net (Rastegari et al., 2016)</td><td>1</td><td>1</td><td>51.2</td><td>73.2</td></tr><tr><td>Opt Opt DoReFa-Net (Zhou et al., 2016) a</td><td>1 T 2</td><td>1 1 1</td><td colspan="2">54.3 ± 0.2 77.4 ± 0.2 58.3 ± 0.1 80.6 ± 0.0 53.4 -</td></tr><tr><td>LQ-Net (Zhang et al., 2018a)</td><td>2</td><td>1</td><td>62.6</td><td>84.3</td></tr><tr><td>HWGQ-Net (Cai et al., 2017)</td><td>2</td><td>1</td><td>59.6</td><td>82.2</td></tr><tr><td>GF Opt Opt* GF ABC-Net (Lin et al., 2017)</td><td>2 2 2 3 3</td><td>1 1 1 1 3</td><td colspan="2">59.7 ± 0.2 81.7 ± 0.1 60.4 ± 0.2 82.2 ± 0.1 62.4 ± 0.1 83.6 ± 0.1 61.1 ± 0.1 82.7 ± 0.1 61.0 83.2</td></tr><tr><td>DoReFa-Net (Zhou et al., 2016)</td><td>4</td><td>1</td><td>59.2</td><td>81.5</td></tr><tr><td colspan="3">GF BWN-Net (Rastegari et al., 2016) 32 1 4 1</td><td colspan="2">61.3 ± 0.2 82.8 ± 0.1 60.8 83.0</td></tr><tr><td>Opt TWN-Net (Li et al., 2016)</td><td colspan="2">32 1 32 T</td><td colspan="2">64.2 ± 0.4 85.2 ± 0.1 61.8 84.2</td></tr><tr><td>Opt FP</td><td colspan="4">32 T 32 32 69.6 64.4 ± 0.1 85.4 ± 0.1 89.2</td></tr></table>

Peer review (iclr2020):
this paper looks at different quantization schemes (replace values of vector in R to, basically, plus or minus v, for well chosen v). Different schemes are considered, namely the low rank binary quantization (a matrix is approximated by the componentwise product of a low rank matrix and a +/-1 matrix) and k-bit binary quantization. Finding the best quantization ends up in solving a program, which is convex and quite straightforward fo k=1 and 2, and unfortunately (apparently) non-convex for k>2. So the authors suggest a greedy approach for k>2. The motivation of this work is DNN, arguing that quantized vectors should improve computations cost, hence some experiments are provide on DNN, yet they only illustrate the fact that quantization does not deteriorate too much the learning & test error. The main criticisms is therefore the lack of concrete evidences that those schemes are actually helpful and, on the other hand, the relative simplicity (so the theoretical part of the paper are not sufficient by itself)