SQuant: On-the-Fly Data-Free Quantization via Diagonal Hessian Approximation
Authors: Cong Guo
Yuxian Qiu
Jingwen Leng
Xiaotian Gao
Chen Zhang
Yunxin Liu
Fan Yang
Yuhao Zhu
Minyi Guo
Venue: ICLR 2022 Poster (2022)
Keywords: Data-Free Quantization
Hessian Matrix
Approximation

Abstract: Quantization of deep neural networks (DNN) has been proven effective for compressing and accelerating DNN models. Data-free quantization (DFQ) is a promising approach without the original datasets under privacy-sensitive and confidential scenarios. However, current DFQ solutions degrade accuracy, need synthetic data to calibrate networks, and are time-consuming and costly. This paper proposes an on-the-fly DFQ framework with sub-second quantization time, called SQuant, which can quantize networks on inference-only devices with low computation and memory requirements. With the theoretical analysis of the second-order information of DNN task loss, we decompose and approximate the Hessian-based optimization objective into three diagonal sub-items, which have different areas corresponding to three dimensions of weight tensor: element-wise, kernel-wise, and output channel-wise. Then, we progressively compose sub-items and propose a novel data-free optimization objective in the discrete domain,  minimizing Constrained Absolute Sum of Error (or CASE in short), which surprisingly does not need any dataset and is even not aware of network architecture. We also design an efficient algorithm without back-propagation to further reduce the computation complexity of the objective solver. Finally, without fine-tuning and synthetic datasets, SQuant accelerates the data-free quantization process to a sub-second level with >30% accuracy improvement over the existing data-free post-training quantization works, with the evaluated models under 4-bit quantization. We have open-sourced the SQuant framework at https://github.com/clevercool/SQuant.

Published as a conference paper at ICLR 2022
SQUANT: ON-THE-FLY DATA-FREE QUANTIZATION VIA DIAGONAL HESSIAN APPROXIMATION
Cong Guo Yuxian Qiu Jingwen Leng 12, Xiaotian Gao?, Chen Zhang', Yunxin Liu?,
Fan Yang', Yuhao Zhu & Minyi Guo 1.2.
Shanghai Jiao Tong University, 2 Shanghai Qi Zhi Institute
3 Microsoft Research, 4 DAMO Academy, Alibaba Group
5 Institute for Al Industry Research (AIR), Tsinghua University, University of Rochester {guocong, qiuyuxian,
junggja]essju.eede
(xiaotian.gao, fanyangJemicrosoft.. mingchong wewaaeeaaaaaaaiiianaaaiaaaa com, liuyunxin@air eeteaarrtsiiiiie tsinghua edu. yzhu@rochester.edae edu, wtt.:myscsssss.eeee.....
ABSTRACT
Quantization of deep neural networks (DNN) has been proven effective for com- pressing and accelerating DNN models. Data-free quantization (DFQ) a promis- ing approach without the original datasets under privacy-sensn seracysseesstive and confidential scemarios. However, current DFQ solutions degrade accuracy, need synthetic data to calibrate networks, and are time-consuming and costly. This paper proposes an on-the-fly DFQ framework with sub-second quantization time, called SQuant, which quantize networks and memory requirements. With the theoretical analysis the second-order in- formation of DNN task loss, we decompose and approximate the fessian-based optimization objective into three diagonal sub-items, which have different areas corresponding to three dimensions of weight tensor: element-wise, kernel-wise, and output channel-wise. Then, we progressively compose sub-items and pro- pose novel data-free optimization objective the discrete domain, minimizing Constrained Absolute Sum of Error (or CASE in short). which surprisingly does not need any dataset and is even not aware of network architecture. We also design an efficient algorithm without pack-propagation to further reduce the computa- tion complexity the objective solver. Finally, without fine-tuning and synthetic datasets, SQuant accelerates the data-free quantization process to sub-sccond level with > 30% accuracy improvement over the existing data-free post-training quantization works, with the evaluated models under 4-bit quantization. We have open-sourced the SQuant framework
inference-only devices with low computation
INTRODUCTION
With the widespread application of DNN, more and more DNN models are deployed on both computation-constaainel and reemory-oonsrriinet environments, e.g., smartphones, IoT devices, and self-driving cars. The desire for lightweight and energy-efficien DNN deployment solutions is increasing. Quantization is one of the most promising techniques to convert weights and activations to lower bit formats and simultancously reduce computational time and memory consumption. There are two kinds of quantization: Post-training quantization (PTQ) (Banner et al. 2018, Choukroun
et al. 2019 Zhao et al./ 2019 Nagel et al. 2020) and Quantization aware training (QAT) (Gupta et al. 2015 Jacob et al.) 2018 Wang et al. 2019 Zhuang al., 202T). QAT requires to simulate quantization in the training process, which invokes time-consuming retraining and hyper-parameter tuning. In contrast, PTQ directly quantizes well-trained models without retraining. However, they still need training datasets to calibrate (Nagel al.) 2020) quantized models but are often unavailable due to privacy and security issues, such as medical and confidential scenarios.
"Jingwen Leng and Minyi Guo are corresponding authors of this paper. http::/ggithhb.ommmeeeee///////

---

Published as a conference paper at ICLR 2022
In contrast, data-free quantization (DFQ) has recently been presented promising way to quantize models without original datasets (Nagel et al. 2019] Cai et al. 2020 Zhang et al., 2021 Xu et al. 2020 Liu et al. 2021 Qin et al. [021] Choi et al. (020). From deployment perspective, DFQ is the most attractive quantization method since we can apply it to any trained models as a black box post- processing step. However, current DFQ methods cannot achieve high accuracy and fast processing time simultancously. Traditionally, DFQ (Nagel et al.) 2019) uses rounding quantization, leading to the rounding-to-neee to-nerrest strategy. Such strategy causes significant accuracy loss, especially in low-bit settings. To bridge the accuracy gap between data-free and data-driven quantization, methods to
researchers propose series of data-generative DFQ methods. They use gradient- generate fake datasets for trained models. With the synthetic data, they can employ a data-driven calibration and fine-tuning strategy to improve accuracy. However, data generation typically adopts the time-consuming gradient-based methods, which require multiple iterations to generate each input. For example, prior works often spend hours generating a calibration dataset and fine-tuning the network (Xu et al. 2020: Liu et al. 2021 Zhang et al., 202T).
To solve this dilemma, we propose SQuant, fast and accurate data-free quantization framework for convolutional neural networks, employing the constrained absolute sum of error (CASE) of weights as the rounding metric. By leveraging Hessian information of network loss due to quantization, we propose novel diagonal Hessian approximation, which decomposes the optimization objective into three data-free sub-items: element-wise, kernel-wise, and output channel-wise, each of which corresponds a single set of dimensions of the weight tensor. We progressively compose and optimize these three sub-items in the discrete space. The final approximate objective eliminates the requirement of data generation. We propose progressive algorithm with linear complexity to solve the optimization objective, further accelerating DFQ time to a sub-second level. For example, SQuant only needs an average of 4 ms and 84 ms for quantizing layer and the overall network of ResNet18, 8, respectively. As it does not require baok-propagation nor fine-tuning, SQuant can run on inference-only devices with limited computation and memory resources on the fly. That opens up new opportunities and scenarios for adopting quantization.
Compared with tfateof-the-at DFQ methods, SQuant achieves higher accuracy on all evaluated models under the 4/6/8-bit settings. SQuant only introduces 0.1% accuracy loss average under the 8-bit setting. Under fewer bit precisions, the advantage of SQuant further expands. SQuant only introduces 1.8% accuracy loss on average under the 6-bit setting. Under the 4-bit setting, SQuant can achieve more than 30% accuracy improvement compared with data-free PTQ methods. In a word, SQuant pushes the accuracy and processing time of DFQ to new frontier.
PRELIMINARIES
2.1 NOTATIONS
We specifically use x, y and w to denote the input, output, and weight variables, respectively. Constant and scalar are denoted by italic letters, e.g., M. Column vector and flattened matrix are denoted by bold lowercase letters, e.g., W, and matrices (or tensors) represented by uppercase letters, e.g., W. The subscript and superscript can further represent the element indices and the layer of a network, respectively, e.g., W E|:] denotes the expectation operator, and the network loss function represented by (-). For convenience in this paper, we call the row of FC (fully connected layer) weight as the output channel and the column of FC weight as the input channel, which are the counterparts to Conv (convolution layer) weight. We use M, N, and K to denote output channel size, input channel size, and kernel height x kernel width, respectively. Specifically, FC has the shape of (M,N, 1).
2.2
QUANTIZATION
Most previous works adopt the rounding-to to-earestt approach for quantizing deep neural networks by rounding elements w to the nearest quantization grid values with fixed-point data type. The quanti- zation and dequantization for a quantized element w can be described as w w s c [1 m.,)) where denotes the quantization scale parameter and, min and max are the lower and upper thresholds for the clipping function clip(.). The operator L-1 represents the rounding-te coddinngtt-nearess. i.c., minimizing the mean squared error (MSE) between the quantized and the original value.
2

---

Published as a conference paper at ICLR 2022
2.3 BESSIAN-BASEES OPTIMIZATION FOR NEURAL NETWORKS
The Hessian-based approach is one of the most promising optimizations to further improve the
quantization (Dong al. 20T9b Nagel al. 2020 Shen al. 2020 Qian al. 2020 Wu et al.)
2020 Hubara et al. 2020; Li et al. 2021 Yao et al. 2021) and pruning Yu et al. [021]] performance
for DNN models. Some those works exploit the Hessian matrix to approximate loss degradation due to the quantization perturbation of weight, AW, by
E| (X AW) 2XX =WWW " 2A H AW").
(I)
where the equation comes from second-order Taylor series expansion, g is the gradient and H is the full network Hessian matrix w.r.t. original weight, W. Since a well-trained model has already converged, the gradient term will be close 0 and thus can be safely ignored. However, computing H" is infeasible because of the large memory overhead and computation complexity. To tackle this problem, we approximate HW
layer-wise Hessian matrix HW under the assumption of
cross-layer independence Dong et al. 2017 Nagel et al. 2020), i.c., HW xx'x'"
V2 V, where
y
denotes Kronecker product of two matrices, V is the Hessian of the task loss w.r.t. y²
For the m-th output channel of Conv or FC, H can be approximatively simplified into output channel-wise (Nagel et al. 2020 Yu et al. 2021 Wu al. 2020 Qian et al. 2020).
H HW Lmm
In
(2)
where V. is approximately a diagonal matrix. Then the final optimization objective is
AW
arg min
AW
E JAW m.
(3)
m.
m.
AW
arrg
AW
E
X AAWE
arg min (AW x )
(4)
AW
AW
which is the MSE between the output activation produced from original and quantized weights. Each sub-problem deals with single output channel AW m... We will further approximate Eq. (4) to remove any input data dependency from the optimization objective in Sec. 3.2
3
METHODOLOGY
3.1 OVERVIEW
Although we can obtain good quantization strategy by minimizing MSE for each output channel, is an NP-hard combinatorial optimization problem. Even approaching acceptable local minimum requires significant effort and involves input activations without the data-free promise.
To avoid the combinatorial optimization problem and eliminate the requirement of data, we propose the SQuant framework. First, SQuant approximates Eq. 4 with three diagonal Hessian matrices corresponding the dimensions of weight, in Sec. 3.2 Due the quantization with fixed-poin data type, SQuant transforms the problem into a data- optimization problem the discrete domain. SQuant dedicates to optimizing each layer's weight employing flipping approach (Nagel al.) 2020) without any input activation. To achieve our proposed optimization objective, minimizing CASE (Constrained Absolute Sum of Error), SQuant progressively composes three approximate sub-items under constraint relaxation, introduced in Sec. 3.3) Finally, SQuant needs to work out flipping set f to minimize the CASE of each kernel and output channel. We design an efficient algorithm with a linear computation complexity to find proper I' based on Eq. (8), in Sec. 3.4
3.2 DIAGONAL HESSIAN APPROXIMATION
In this work, we propose new approximation of the Hessian matrix to cover non non-diagonal elements and decompose Eq. 44h into three sub-items that correspond to the three dimensions of the weight
3

---

Published as a conference paper at ICLR 2022
NXK
H-E: H-E: SQuant-E
H-K: SQuant-K
K
W
AW
Elxx']
H-C: SQuant-C
Figure AW m: B[xx"]AW,,,. m. T. SQaunt-E, SQaunt-K, K, and SQuant-C are three approximate sub- items, which cover H-E, H-K and H-C, respectively.
tensor as illustrated in Fig. SQuant-E for element-wise optimization covers the diagonal elements of H (H-E); SQuant-K for kernel-wise optimization covers the diagonal blocks of H (H-K); SQuant-C for output channel-wise optimization covers the whole H (H-C).
The xxxxx() can be approximated by the following equation:
E
~ K+CCC
(5)
where C = CmJNKK
JiJx
Tei.1
K
and E
kyJK
eN.K
In the above equations, JAK is an all-one matrix with the dimension of N x K (denoted as NK), and Gn constant value for m-th output channel. K is diagonal block matrix, where Jg represents an all-one matrix with the dimension of K x K. The n-th diagonal block corresponds to n-th kernel in convolution and has own constant value kn. E is diagonal matrix with the diagonal elements of enji each of which is constant value corresponding to i-th element of n-th kernel.
Eq. (5) provides an approximation that preserves as much information from three different levels of Exx'x"" as possible, which we explain in Appendix A.1 The matrix C catches the common component the Hessian matrix, while the matrix E reserves the individual components in the diagonal line of the Hessian matrix. In addition, we consider kernel-wise approximation for convo- lution layers by using matrix For each inference, the weights of a kernel, W Wm.. scan the same feature map. As result, the corresponding x has nearly the same expectation values in the center area, with small perturbation in the marginal area due to padding. Therefore, k, K as a kernel-wise
approximation achieves low approximate eπror for convolution. For any E ("
always find a decomposition that satisfies en,i kn,Cm Cm > 0, for which we present the decomposition method in Appendix A.2 Substituting Eq. (5) into Eq. 44 yields the following equation.
AW m.
JWW m.
Σ n.
AW. m.nd
Σ ky AW J JRA m.n.; + +m JugAWt (6)
3.3 DATA-FREE OPTIMIZATION
To achieve the data-free optimization objective, we omit the coefficients (en.1. k, and cm.) in Eq. (6). which leads to the approximate objective in Eq. (8) optimized by our fast SQuant framework. We present the omitting process and empirically verify that the approximation does almost not influence the performance in Appendix A.2 and Appendix A.3 It can easily found that there are no training samples needed to minimize,
arg min
Σ
Aw JAAw
+AW JNKAW
m.ni
AW:
n
aar min AW m:
Aw m.n.i
2 Σ E
AW
Aw E
(8)
m.nil
m.nj.
n.
4

---

Published as a conference paper at ICLR 2022
Next, transform the overall objective Eq. & in the discrete space and explain how to compose and optimize the three approximated sub-items in order. Without loss of generality, we assume all weights have been scaled with the scale parameter Sm for W m.
Sub-item Analysis For the element wise item, i.c., the first item in Eq. (8) to the following objective, which call SQuant-E.
the problem is reduced
AW
arg min
Eaw m...i
arg min JAW mind < VAW
AW
m.n S.. = 0.5, (9)
AW
AW m,01
SQuant-E is essentially the rounding method when r, = 0.5. Rounding does not introduce any approximate error and has 0(1) complexity for each weight element. However, as many previous works pointed out (Nagel et al. 2020 rounding-to-nearest is not optimal because it only considers while ignores the rest majority elements.
the diagonal elements the matrix E[
For kernel-wise item (the second item in Eq. (D), we have the following objective called SQuant-K,
AW arg min Σ( mad))
arg min
Law m.n.
<VAW
AAW mmnd
0.5, (10)
AW,.
AW.
where AAWW" m.nil is the Absolute Sum of Error (ASE) of each kernel-wise weight matrix in the convolution and r equals 0.5 because of the discrete quantization. In other words, SQuant is based on the insight of Sum of (Signed) error instead of the accumulation of absolute (unsigned) error.
Similarly, for the output channel-wise item (the third item in Eq. (8)). we have SQuant-C,
A AW
arg min EAW mmm)) WAW
LAW Aawma m S Sre 0.5.
(11)
AW
R.
Relaxation Obviously, re = 0.5 against rx = 0.5 because rounding (r.- = 0.5) only guarantees the upper-bound r = 0.5K for SQuant-K. Some elements need to relax the constraint to larger number, such as 1.0, to satisfy r2 = 0.5. Similarly, SQuant-C also needs to relax rx = 1.0.
CASE Flipping We adopt the flipping approach (Nagel et al.) 2020) to minimize the ASE. Due to the discrete quantization, rounded elements can be flipped (from rounding up to rounding down and vice versa) with 11 integer mutation. Formally, we need to work out flipping set fm to satisfy the overall objective Eq. (8) by composing these three sub-items in order (SQuant-E + SQuant-K SQuant-C) with constraints relaxation. After optimization, the f, will be
V(m,n.i & fm. JAW A S 0.5; V(m,n. j) E fm: 0.5 S (AW < 1.0,
(12)
where fn is the index of flipped elements for m-th output channel. Specifically, we need to flip k [ASE] elements, whose perturbation has the same sign as AWW m.n.i- We prove the equivalence for Eq. 10 and Eq. 11 by illustrating the transformation process to a discrete problem Appendix B.
However, any k elements satisfy Eq. (I0) leading to large search space. Fortunately, based on Eq. (9). SQuant-K can select specific & elements with the top-k largest perturbation because they will have the smallest perturbation after flipping under the constraint of SQuant-E. Therefore, adopt the Constrained ASE (CASE) to optimize the SQuant-E& composition via the top-k perturbation algorithm, which is the only solution for minimizing the CASE proven in Appendix B.2 Obviously, SQuant-E&K&C needs to "flip" the "SQuanted"' kernel after SQuant-E&K. Notice that we can only flip one element for kernel to satisfy the constraint r 1.0.
The following section will introduce an efficient SQuant algorithm with a linear computation com- plexity for CASE flipping.
3.4 ON-THE-E FLY SQUANT
Progressive Algorithm We design a progressive algorithm illustrated in algorithm to meet our stated optimization objective, i.e., minimizing the CASE of weight perturbation. The erttical insight of the progressive algorithm is to gradually calibrate the deviation from the optimal global solution introduced by the fine-grained diagonal sub-item. To calibrate the SQuant-E. SQuant-K K flips certain rounded elements. After the SQuant-K calibration, SQuant-C then further flips SQuanted kernels.
5

---

Published as a conference paper at ICLR 2022
We start by rounding the weight and updating its perturbation to satisfy Te 0.5 (Line 4-5). Then we rum the SQuant-K (Line 6) to flip specific elements under 7.- = 1.0, satisfy F = 0.5, and update kernel perturbation (Line 7). The follow-up SQuant-C (Line 8) further flips specific kernels under = 1.0 and satisfy re = 0.5. Finally, we derive the quantized weights (Line)) 9).
Algorithm 1: Progressive SQuant Algorithm.
Input: Weight tensor W of layer f, scale factor of layer L.
Output: Quantized weight tensor C of layer
foreach E [I....M] do // sQuant-C: SQuant M output channels.
foreach n E [1, ...N do // SQuant-K: squant kernels.
foreach i E ,..., K] do // SQuant-E: Round K elements,
Em = W mmni/ Sm // Scale and SQuant-E (Rounding).
AE mm.i Bm,,. W mnn // Element perturbation.
Kmn: SQuantFlip(E.,.... AEma:)// SQuant-K.
// Kernel perturbation. Cm.: SQuantFli(KKm: AKm.). Sm// sQuant-C.
AKmn. -Updaceerrurtaation(AMM.
return C
Flip Algorithm SQuant-K and SQuant-C can utilize the same flip function. The goal of the flip
algorithm is find proper element f to flip and minimize the CASE depicted in algorithm 2 First, we need to compute the accumulated perturbation (e) (Line 2). We select weights with positive
perturbation to decrease the positive and vice versa for negative e. Therefore, we set 0 for the elements with a different sign (Line 3) to disable them. Obviously, we need only k == [|el] elements and reduce le| < Fạ = 0.5 (Line 4). Finally, we flip & weights with the largest |p] (Line 5-6). For now, we have SQuanted the kernel and tuned kernel CASE to le| S 0.5. Specifically, for FC and Conv with kernel size of 1). we can skip the SQuant-K. As mentioned in Section 3.3 SQuant-C flips only one element in each kernel. Therefore, update the kernel perturbation (Line of algorithm II for SQuant-C to flip kernel illustrated Appendix B.3 As a result, SQuant successfully identifies the optimum combination under low computation complexity, which we analyze in Appendix B.4
Algorithm 2: SQuant Flip Algorithm.
Input: Rounded/SQuanted Weight w:
Weight perturbation p.
Output: Updated Quantized Weight w.
def SQuantFlip (w, p)
e = E.pp// Accumulated perturbation.
ple p < 0] 0 Disable Elements/kernell with different siga from
k= [|e]] // Flip k eLements//ernels based on the CASE.
f= TopK( pl. k).indices/// Indices of 1argest perturbation.
w[f]= = Flip (f)// Flip k elements/kernell with same sign as e.
return
On-the-Fly Framework From the overall perspective of the optimization, SQuant-K has MN sub- problems, while SQuant-C has M sub-problems. Because of the independence of sub-problems, SQuant is friendly for DNN accelerators. e.g., GPU, allowing each sub-problem to be accelerated in parallel. Without the requirement of propaaaopnn nor fine-tuning. SQuant can run on inference- only devices with constrained computation and memory resources on the fly. That provides new opportunities for optimizing weight quantization. In the next section, we demonstrate the impressive efficiency and accuracy of SQuant.
EXPERIMENTS
For demonstrating the strength of SQuant, we evaluate the SQuant as well as four SOTA methods, DFQ (Nagel al. 2019), ZeroQ (Cai al. 2020). DSG (Zhang et al. 2021 Qin et al. 2021 and

---

Published as a conference paper at ICLR 2022
Arch
Method No BP No FT
W-bit
A-bit Top-1
Arch
Method No BP No FT W-bit A-bit Top-1
Baseline
32
32
71.47
Baseline
32
32
78.81
DFQ
4
4
0.10
ZeroQ
4
4
4
18.20
ZeroQ
X
4
4
19.09
GDFQ
X
4
4
70.39
DSG
X
<
4
4
34.53
SQuant
/
4
73.26 4
GDFQ
X
X
4
4
60.60
SQuant
V
4
66.14 4
Inception
ZeroQ
6
6
74.94
DFQ
V
6
6
67.30
V3
GDFQ
x
6
6
77.20
ResNet18
ZeroQ
X
V
6
69.84
SQuant
78.30 6
6
DSG
X
6
6
70.46
ZeroQ
/
8
8
78.78
GDFQ
X
X
6
6
70.13
SQuant
70.74 6
GDFQ
x
78.62
SQuant
8
78.79 8
DFQ
8
8
69.70
ZeroQ
X
8
71.43
Baseline
32
32
69.38
GDFQ
X
X
8
8
70.68
ZeroQ
/
4
4
0.09
SQuant
8
8
71.47
GDFQ
x
28.93
Baseline
32
32
77.74
SQuant
/
4
43.45 4
ZeroQ
x
4
4
7.75
Squeeze
ZeroQ
/
16.54
DSG
X
4
4
23.10
Next
GDFQ
x
6
6
65.46
GDFQ
X
4
55.65
SQuant
6
67.34 6
SQuant
70.80 4
ResNet50
ZeroQ
X
6
6
72.93
ZeroQ
/
8
8
68.18
DSG
x
6
6
76.07
GDFQ
x
x
8
8
68.22
GDFQ
x
X
6
6
76.59
SQuant
8
69.22 8
SQuant
6
6
77.05
Baseline
32
32
65.07
ZeroQ
DSG
X
X
V
V
8
8
8
8
77.65
77.68
ZeroQ
/
6
6
35.21
GDFQ
X
X
8
8
77.51
Shuffle
GDFQ
x
6
6
60.12
SQuant
8
8
77.71
Net
SQuant
60.25 6
ZeroQ
8
8
64.34
Table 1: Results of data-free methods with ResNet18 and ResNet50. "No BP" means that no back-propagation algorithm is used to generate data, "No FT means no fine-tuning (retraining) for weight quantization.
GDFQ
X
8
8
64.03
SQuant
8
64.68
Table 2: Results of data-free methods with Incep- tionV3, SqueezeNext, and ShuffleNet.
GDFQ (Xu et al. 2020p, with different CNN models including ResNet- 18 & 50 (He al. 2016). Inception V3 (Szegedy et al.) (016)), SqueezeNext (Gholami al., 2018) and ShuffleNet (Zhang ct al. 2018) on the golden standard dataset ImageNet (Krizhevsky et al. 2012).
In our experiments, SQuant is dedicated to weight quantization, including setting quantization range and selecting the grid point with per-channel quantization, which is friendly for hardware accelerators. With the BN-based approach, we adopt a simple rounding method and a wide quantization range for activation suggested by DFQ (Nagel et al. 2019) without breaking the data-free premise. We clip activation tensors in layerwise manner (per-tensor). We utilize uniform distribution as the initialization for the activation quantization range. All DFQ algorithms are implemented with PyTorch (Paszke al., 2019) and evaluated Nvidia GPU A100-40GB. Unless otherwise stated, employ both weight and activation quantization in all experiments. Also, uniform quantization grids used in all experiments, and sypper-paramtters. e.g., Fe r 1.0 and r. 0.5, for all SQuant experiments are the same.
4.1 COMPARISON SOTA METHODS
Table T and Table show the results the ImageNet datasets for various bit-width choices, comparing our SQuant against other data-free methods. Among these methods, ZeroQ, DSG, and GDFQ are data-generative approaches with back- peck-propagation The former two PTQ methods, while the last a QAT method, which retrains the network with the synthetic data. DFQ is the only true data-free free method with weight equalization and bias correction.
Experiments show that SQuant significantly outperforms all other SOTA DFQ methods, even with synthetic dataset calibrating their networks. The 8-bit quantization preserves better network accuracy
7

---

Published as a conference paper at ICLR 2022
Arch
ResNet18
ResNet50
Inception V3
SqueezeNext
ShuffleNet
Layers
21
54
95
112
50
SQuant Time (ms)
84
188
298
272
121
ZeroQ Time
38
92
136
109
38
GDFQ Time (hour)
1.7
3.1
5.7
4.8
1.9
Table 3: SQuant, ZeroQ and GDFQ 4-bit quantization time on GPU A100
than the lower-bit quantization does because of higher precision. The benefit of SQuant becomes more prominent the bit width decreases. SQuant outperforms the PTQ methods, i.e., DFQ. ZeroQ, and DSG, more than 30% on all models with 4-bit quantization. It is noteworthy that SQuant surpasses GDFQ in all cases and surpasses more than 15% in ResNet50 under 4-bit quantization, although GDFQ is quantization-aware training method.
Table 1 and Table show that GDFQ significantly outperforms ZeroQ and DSG under lower-bit settings (e.g., 4-bit). Since we use the same activation quantization method for evaluating these methods, the results indicate that the weight quantization plays critical role in the overall model quantization. However, GDFQ requires fine-tuning (FT) with back poek-propagation (BP). In contrast, SQuant adopts direct optimization objective of weight perturbation, which does not require fine- tuning nor BP, and still outperforms GDFQ in the 4-bit setting. These results clearly illustrate the advantages of SQuant, a CASE-based optimization framework, which minimize the CASE of weight perturbation.
4.2 SQUANT EFFICIENCY
The trade-off between efficiency and accuracy is challenging for previous DFQ methods. Before SQuant, DFQ the fastest one since does not require back-propagation and fine-tuning, performs poorly, especially in low-bit cases. GDFQ performs relatively well but takes hours to complete 400 epochs that produce synthetic data from weights and fine-tune the network. SQuant employs the direct optimization objective, minimizing the CASE of weight perturbation, pushes the quantization procedure to sub-second level. Table 3 shows the 4-bit quantization time of the five models using SQuant, ZeroQ, and GDFQ. The efficient algorithm design also contributes the surprising results. Note that the SQuant results in Table 3 are the sum of all layer quantization time, and it will be faster if quantize layers parallel. A single layer takes SQuant just milliseconds on average because SQuant does not involve complex algorithmss, such as back teek---pppgation and fine-tuning. That means we can implement the SQuant algorithm on inference-only devices such as smartphones and IoT devices and quantize the network on the fly.
4.3 ABLATION STUDY
SQuant Granularity We decouple the effect of SQuant-K and SQuant-C, which have different granularities to optimize CASE, As shown in Table their accuracies both outperform SQuant-E
Method
W-bit
A-bit
Top-1
Method
No BP No SD
W-bit
A-bit
Top-1
Baseline
32
32
71.47
Baseline
32
32
71.47
SQuant-E
3
32
2.05
ZeroQ AdaRound
X
x
3
32
49.86
DSG AdaRound
X
x
3
32
56.09
SQuant-E&e E&C
3
32
40.87
SQuant
7
/
3
32
60.78
SQaattEE&K
3
32
52.07
SQuant-Ee E& K&C
3
32
60.78
ZeroQ AdaRound
X
63.86
DSG AdaRound
x
4
32
66.87
SQuant-E
4
32
48.15
SQuant
69.75 4
32
SQuant-Eac E&C
4
32
67.14
ZeroQ + AdaRound
X
x
32
68.39
SQuant-E&K
4
32
68.07
DSG AdaRound
X
68.97
SQuant E&K&C SQua
4
69.75
SQuant
71.19
Table 4: SQuant ablation results with
Table 5: ResNet1 8 results of SQuant, ZeroQ and DSG with AdaRound. "No SD" means synthetic data.
ResNet18.
8

---

Published as a conference paper at ICLR 2022
(i.e.. rounding), and combining them leads to higher accuracy for ResNet18. SQuant-E&t has lower accuracy than SQuant-E&&K because SQuant-C has a more significant approximation error than SQuant-K. On the other hand. SQuant-E alone is not optimal because it uses a smaller granularity and ignores a large amount of Hessian information as we analyze in Section 3 This ablation study shows that SQuant-F&K&& achieves the best accuracy by exploiting the most Hessian information (H-C), and SQuant-E&K also achieves a higher accuracy with H-K than SQuant-E with H-E.
Comparison to Data-free AdaRound AdaRound (Nagel al., 2020 is novel data-driven PTQ method, which also utilizes the Hessian-based approach to round-up or round-down the weights with an approximation assumption. Under the data-free premise. we augment ZeroQ and DSG with the AdaRound by feeding their generated synthetic data to AdaRound. Results in Table 5 show that SQuant has better accuracy than data-free AdaRound because SQuant directly optimizes the CASE objective instead of the MSE of the output activation adopted by AdaRound. It is hard for DSG+ AdaRound to find the optimal solution with an excessively long optimization path and gradient-based approaches. Even though AdaRound tries a shorter way to fine-tune the weights in the layer-wise fashion, SQuant still outperforms AdaRound in quantization time and accuracy.
5 RELATED WORK
Compression is a promising method to reduce the DNN model's ' memory and computation cost.
Pruning (Han et al., 2015b|a a) one of the effective approaches to exploit the inherent redundancy
of DNN. However, pruning will cause sparse irregular memory accesses. Therefore, pruning needs
software (Gale al. 2020 Guan al., 2020 Qiu et al. 2019 Guo al.
2020a Guan al. 202T
Fedus et al. 2021 and hardware (Gondimalla et al. 2019: Guo et al.
2020b Zhang et al.
2020
Wang al. 2021 D optimization to accelerate.
Quantization is more practical because it can be supported directly by existing accelerators. Quantization-awee training (QAT) (Gupta et al. 2015) Jacob et al.) 2018: Wang et al., [219]]
Zhuang et al. 2021) is one of the most promising techniques to retrain networks and mitigate the accuracy drop introduced by quantization. However, the training procedure is time-consuming and
costly. Therefore, post-training quantization (PTQ) (Banner et al., 2018 Choukroun et al.) 2019 Zhao et al. 2019; Nagel et al. 2020) has earned lots of attention due to the absence of any fine-tuning or retraining process, at the expense of accuracy.
Recently, several methods for CNN quantization without the original training datasets have been proposed. These methods are known data-free quantization (DFQ), including PTQ (Nagel et al. 2019 Cai et al. 2020; Zhang et al.) (021)) and QAT (Xu et al.) 2020 Liu et al., [202 Qin et al. 202T Choi et al. (202)). DFQ (Nagel et al. 2019) and ACIQ (Nagel et al. (2119) rely on weight
equalization or bias correction without requiring synthetic data. Other works synthesize the data to
calibrate or fine-tune the network based the batch normalization statistics (Cai et al. 2020
adversarial knowledge distillation techniques (Liu et al. 2021 Choi et al. 2020)).
6 CONCLUSION
This paper approximates and composes the original Hessian optimization objective into the CASE of weight perturbation with data-free premise. Surprisingly, CASE only involves the weight perturbation and requires no knowledge of any datasets network architecture. Based on that, we proposed the on-the-fly SQuant framework. We used a progressive algorithm to minimize CASE directly and significantly improve accuracy than other DFQ methods. SQuant considerably reduces optimization complexity and accelerates the data-free quantization procedure, which previously requires mack-propagation with massive computation and memory resources consumption seen in other works. In summary, SQuant outperforms other data-free quantization approaches in terms of accuracy and pushes the quantization processing time sub-second level.
ACKNOWLEDGMENNS
We would like to thank the anonymous reviewers for their constructive feedback. This work was supported by the National Key R&D Program of China under Grant 2021ZD0110100 10104, and the National Natural Science Foundation of China (NSFC) grant (U21B2017, 62072297, and 61832006).

---

Published as a conference paper at ICLR 2022
REFERENCES
Ron Banner, Yury Nahshan, Elad Hoffer, and Daniel Soudry. Post-training 4-bit quantization of convolution networks for rapid-deployment. arXiv preprint arXiv://80005523, 2018.
Yaohui Cai, Zhewei Yao, Zhen Dong, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Zeroq:
A novel zero shot quantization framework. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13169-13178, 2020.
Yoojin Choi, Jihwan Choi, Mostafa El-Khamy, and Jungwon Lee. Data-free network quantization with adversarial knowledge distillation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition Workshops, pp. 710-711, 2020.
Yoni Choukroun, Eli Kravchik, Fan Yang, and Pavel Kisilev. Low-bit quantization of neural networks for efficient inference. In ICCV Workshops, pp. 3009-3018, 2019.
Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer-wise optimal brain surgeon. arXiv preprint arXiv:1705.07565 2017.
Zhen Dong, Zhewei Yao, Yaohui Cai, Daiyaan Arfeen, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. -2 Hessian aware trace-weighted quantization of neural networks. arXiv preprint arXiv:1911.03853 1.08552, 2019a.
Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Hawq: Hessian aware quantization of neural networks with mixed precision.... Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 293 -02-,02,22 2019b.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2 2021.
Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEEE, 2020.
Amir Gholami, Kiscok Kwon, Bichen Wu, Zizheng Tai, Xiangyu Yue, Peter Jin, Sicheng Zhao, and Kurt Keutzer. Squeezenext: Hardware- aware neural network design. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition Workshops, pp. 1638-1647, 2018.
Ashish Gondimalla, Noah Chesnut, Mithuna Thottethodi, and TN Vijaykumar. Sparten: A sparse
tensor accelerator for convolutional neural networks. In Proceedings the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pp. 151-165, 2019.
Yue Guan, Jingwen Leng, Chao Li, Quan Chen, and Minyi Guo. How far does bert look at: Distance-based clustering and analysis of bert's attention. In Proceedings of the 28th International Conference on Computational Linguistics, pp. 3853-3860, 2020.
Yue Guan, Zhengyi Li, Jingwen Leng, Zhouhan Lin, Minyi Guo, and Yuhao Zhu. Block-skim: Efficient question answering for transformer. arXiv preprint arXiv:21 2021.
Cong Guo, Bo Yang Hsuch, Jingwen Leng, Yuxian Qiu, Yue Guan, Zehuan Wang, Xiaoying Jia, Xipeng Li, Minyi Guo, and Yuhao Zhu. Accelerating sparse dnn models without hardware- sardware-support via tile-wise sparsity. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-15, 2020a.
Cong Guo, Yangjie Zhou, Jingwen Leng, Yuhao Zhu, Zidong Du, Quan Chen, Chao Li, Bin Yao, and Minyi Guo. Balancing efficiency and flexibility for dnn acceleration via temporal gpu-systolic array integration. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020b.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learning with limited numerical precision. International conference on machine learning, pp. 1737-1746. PMLR, 2015.
10

---

Published as a conference paper at ICLR 2022
Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149 2015a.
Song Han, Jeff Pool, John Tran, and William J Dally. Learning both weights and connections for efficient neural networks. arXiv preprint 1rXiv:1506.02000 2015b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry. Improving post training neural quantization: Layer-wise calibration and integer programming. arXiv preprint arXiv:2006. 10518, 2020.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 2704-2713, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 15:1097-1105, 2012.
Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang. Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang, and Shi Gu. Breeq: Pushing the limit of post-training quantization by block reconstruction. arXiv preprint arXiv:2102.05426, 2021.
Yuang Liu, Wei Zhang, and Jun Wang. Zero-shot adversarial quantization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1512-1521, 2021.
Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling. Data-free quantization through weight equalization and bias correction. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 1325-1334, 2019.
Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization. In International Conference on Machine Learning, pp. 7197-7206. PMLR, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Xu Qian, Victor L.,, and Crews Darren. Channel-wise hessian aware trace-weighted quantization of neural networks. arXiv preprint Sitv:20008.82844 2020.
Haotong Qin, Yifu Ding, Xiangguo Zhang, Aoyu Li, Jiakai Wang, Xianglong Liu, and Jiwen Lu. Diverse sample generation: Pushing the limit of data-free quantization. arXiv preprint 1.Xii:2/099002/22 2021.
Yuxian Qiu, Jingwen Leng, Cong Guo, Quan Chen, Chao Li, Minyi Guo, and Yuhao Zhu. Adver- sarial defense through network profiling based path extraction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4777-4786, 2019.
Sheng Shen, Zhen Dong. Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-bert: Hessian based ultra low precision quantization of bert. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 8815-8821, 2020.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818-2822 2016.

---

Published as a conference paper at ICLR 2022
Yang Wang, Chen Zhang, Zhiqiang Xie, Cong Guo, Yunxin Liu, and Jingwen Leng. Dual-side sparse tensor core. In Proceedings of the 48th Annual International Symposium on Computer Architecture, ISCA 221, pp. 1083-1095, 2021.
Ziwei Wang, Jiwen Lu, Chenxin Tao, Jie Zhou, and Qi Tian. Learning channel-wise interactions for binary convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 568-577, 2019.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arXiv:2010.04261, 2020.
Shoukai Xu, Haokun Li, Bohan Zhuang, Jing Liu, Jiezhang Cao, Chuangrun Liang, and Mingkui Tan. Generative low-bitwidth data free quantization. In European Conference on Computer Vision, pp. 1-17. Springer, 2020.
Zhewei Yao, Zhen Dong, Zhangcheng Zheng, Amir Gholami, Jiali Yu, Eric Tan, Leyuan Wang, Qijing Huang, Yida Wang, Michael Mahoney, et al. H3wq-v3: Dyadic neural network quantization. In International Conference on Machine Learning, pp. 11875-1 1886. PMLR, 2021.
Shixing Yu, Zhewei Yao, Amir Gholami, Zhen Dong, Michael W Mahoney, and Kurt Keutzer. Hessian- awaare pruning and optimal neural implant. arXiv preprint arXiv:2101.08944 2021.
Xiangguo Zhang, Haotong Qin, Yifu Ding, Ruihao Gong, Qinghua Yan, Renshuai Tao, Yuhang Li, Fengwei Yu, and Xianglong Liu. Diversifying sample generation for accurate data-free quantization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp.
15658-15667, 2021.
Xiangyu Zhang. Xinyu Zhou, Mengxiao Lin, and Jian Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 6848 6856, 2018
Zhekai Zhang, Hanrui Wang. Song Han, and William Dally. Sparch: Efficient architecture for sparse matrix multiplication. In 2020 IEEE International Symposium High Performance Computer Architecture (HPCA), pp. 261-274. IEEE, 2020.
Ritchie Zhao, Yuwei Hu, Jordan Dotzel, Chris De Sa, and Zhiru Zhang. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pp. 7543-7552. PMLR, 2019.
Bohan Zhuang, Mingkui Tan, Jing Liu, Lingqiao Liu, lan Reid, and Chunhua Shen. Effective training of convolutional neural networks with low- bitwidhth weights and activations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
A APPROXIMATION AND DECOMPOSITION
A.1 APPROXIMATED HESSIAN MATRIX FOR DATA-FREE QUANTIZATION
The quantization loss function for the entire network is
L(AW) = AW AWE HWWW
(13)
Consider convolution layer defined as
Y Ym...w
Σ W Ammijxxmh-ii--pp n...)
(14)
Here, Y has three dimensions, output channel, output feature map height, and output feature map width, i.e., (M x OH x OW) indexing by (m, h,)),,)) w). W has four dimensions, output channel, input channel, kernel height, kernel width, i.e., (M x N x KH KW) indexing by im, and X has three dimensions, input channel, input feature map height, and input feature map width, ie.. (N IH x /W) indexing by (n,h- i,w j). Ignoring the interaction between layers and output
12

---

Published as a conference paper at ICLR 2022
channels following Nagel et al. (2020), for specific convolution layer and output channel m, the elements of corresponding output thasnel-wise Hessian H
LL
(15)
2w m.j.j.
2 mnn' mnn'd
d
dL
m.w
Σ
(16)
aw m.ni how
m.h
0
dL
E
X
XnA-inw-1 iw-
(17)
WWmai how
m.h
d
dL
Σ
Xndi-lw-1
(18)
m.hw Y
mil
h,w
d
Σ
Xnh-iww-
(19)
②Y m.ww
mml
d.G. L
X h.h-ww Lw- joHt -e
(20)
④Y m.
V
m.H
Assuming v V. is diagonal matrix yields Eq. (30) in (Ngel et al. 2020
22
Σ
X i-- Nn Pw
(21)
mhhw
To make Eq. (13 get irrelevant to training samples, assume that input feature maps auto-correlate with each other in a similar way, resulting in
H ai
E Σ
X Xn - X- Rs Cm
(22)
πY2 h.w m.hw
for all n,i,j,n', j and j', where Cn is constant. It should be noted that Eq. (2 is strong assumption. For more accurate approximation, we further look into each input channel (i.e., n = n', i i", and + i'), and find
26
E
=
Σ
E
av2 m..w
Xn -in--i Fo km.n
(23)
i, j. 7., and j', where km. a constant. is generally true because the kernel size is usually much smaller than the size of feature maps, the shift introduced by different f', and j' is w small perturbation of [ i. compared with the summation over the entire feature map. Finally, we focus on each diagonal element of Hessian matrix (i.e., = =nn, =i,, and j = j') and denote
J. mady E
x2
n.h -.h--w--] = Cmmii.j
(24)
11.10 m.k.
where Cmni. is constant. Please note that the output channel-wise expected Hessian matrix Wt. ii F.f is principle submatrix of EE [H, it must positive semi-define. Therefore, set Cmni.j kmx > () to ensure the approximation to B H wf
H
ni F.)) is also positive semi-define get the
and nontrivial. Considering Eq. (22 Eq. and Eq. (24) at the same time, approximation to expected Hessian shown in Eq. (5). Extending the discussion to fully connected layer is straightforward thus omitted here.
13

---

Published as a conference paper at ICLR 2022
A.2 DECOMPOSITION
In this section, we present the decomposition method for H H Ex e algorithm First, construct three matrices with the shape of NNK,NK), C' JyK.
illustrated in the
JK
K'
and E'
Jk
Here, JNK is all-one matrix with dimension NK N K and Jk represents all-one matrix with dimension K. The n-th diagonal block corresponds to n-th kernel in convolution and has the same constant kn E is diagonal matrix whose diagonal elements are 1.
Algorithm 3: E(x !7
Decomposition.
Input: E[x'x"") H;
Channel-wise matrix, C'.
Kernel-wise matrix, K' Element-wise matrix, E'.
Output: Matrix E,K, and C.
H'
Cm 8) min(H')) // output channcl-wise.
C= Cm C
foreach E [I....NN do kernel-wise. mn+K mo+K Cm)
kn = (1 5n) min H
Kn.: kn Kn
foreach i E [l....,KK do // Element-wise, en.l H nxK+i, nxK+i Cm mon-Ke kn
Em,i En
return K,K,C
In algorithm 0 < E,9' < and we can get the matrices E, K. and C. Evidently, algorithm 3 can
make Cm kip and en >> 0 for any Exx'x" | E+CC.
A.3 APPROXIMATION ERROR ANALYSIS
To achieve the data-fres optimization objective, omit the coefficients (en.d, k, and Cma) in Eq. (6) which leads to the approximate objective in Eq. (8) optimized by our fast SQuant framework. We approximate Eq. ( Eq. (8) enable fast data-free quantization. The approximation error is insignificant as our comprehensive results have shown the high accuracy of the final quantized model in Table I and Tf the manuscript. The intuition behind the approximation is that use an iterative process which progressively reduces each term of Eq. (6). Because each term's 's coefficient (en.is kn and cm) is positive, the reduction of each term would generally lead to the reduction of the precise objective in Eq. (6) In this section, we provide an empirical analysis of the approximation error between Eq.
6 andEq. (8)
In this empirical experiment, we use the real dataset to generate the precise coefficients of enii kn and Cm in Eq. (6). quantify the approximation error in our SQuant framework, we evaluate metric called approximation precision and show that achieve nearly 95% approximation precision.
Since SQuant uses the flipping-based iterative optimization framework to minimize Eq. 8 we define an element correctly flipped if its flipping leads to the decrease of the precise objective Eq. (6) and
approximate objective Eq. (8). The approximation precision (AP) is the ratio the correct element
based data-fre Eq. compared to data-driven Eq. (6). i.e.,
Number of correct elements AP
Number of flipped elements
14

---

Published as a conference paper at ICLR 2022
Layers
Squant-E&K
SquantEE&K&C
Flipped
Correct
AP
Flipped
Correct
AP
2346
2346
100,00 %
123
123
100.0 %
2
2683
2594
96.68 %
97
97
100.0 %
2662
2653
99.66
100
100
100.0
2698
2630
97.48 %
107
107
100.0 %
5
230
220
95.7 %
6
5349
5339
99.81 %
223
223
100.0 %
7
10782
10676
99.02 %
332
332
100.0 %
10777
10633
98.66
342
342
100.0
10655
10424
97.83 %
348
348
100.0 %
10
649
619
95.4 %
11
21371
21173
99.07 %
663
663
100.0 %
12
43116
41561
96.39
906
906
100.0 %
13
42976
41402
96.34
932
100.0
14
43321
41315
95.37 %
918
918
100.0 %
15
1988
1639
82.4 %
16
86010
83070
96.58 %
1846
1846
100.0 %
17
171344
161358
94.17 %
2629
2629
100.0 %
18
172071
158066
91.86
2602
2602
100.0
19
172623
154536
89.52 %
2504
2504
100.0 %
Total
800784
749776 93.6 %
17539
17150
97.8 %
Acc.
68.07
69.75
Table 6: ResNet18 results under 4-bit weight-only quantization. "Flipped" is the number of the Flipped elements after SQuant optimization. "Correct" number of elements has the same optimization direction as the precise objective. AP is the approximation precision.
We perform the above approximation error analysis ResNet18 with Image under 4-bit weight- only quantization. We evaluate the SQuanted weight on the inference datasets. We compute the coefficients en kn, and Cm with 1000 samples. Table 6 the results, which clearly show that SQuant-E&K&C achieves nearly 100% approximation precision. In other words, nearly all flipped elements can indeed reduce the precise objective in Eq. (6). Based on this empirical study, we show that the approximation from Eq. (6) to Eq. (8) is effective for our data-free quantization.
B SQUANT ALGORITHM
B.1 DISCRETE OPTIMIZATION PROBLEM
We introduce the transformation the discrete optimization problem. We know that the quantization round the scaled elements to the integer grid. Each quantization step has rounding directions, rounding up and down, with step size of 1. We have the quantization example within [0, 1] shown in Fig. 2
Clearly, the element 0.7 (0.4) can be rounded up (down) to 1.0 (0.0) with +0.3 (-0.4) orignal perturbation and flipped to 0.0 (1.0) with -0.7 (+0.6) flipped perturbation with -1 (+1) mutation. Each flipping operation leads to a +1 integer mutation and increases the perturbation to [0.5, 1.0]. We prove that always find k AW?
elements flip and reduce AW m S 0.5.
15

---

Published as a conference paper at ICLR 2022
0
0.5
0.4
Aw 0,4
Flipped Aw = 0.6
Down
UP
Flipped Áw - 0.7
Aw 0.3
0.7
Quantization Step
Figure 2: The flipping approach.
Proof. Assume nith kernel has K elements, a rounded up elements with index set fa have positive perturbation, b rounded down elements with index set fo have negative perturbation, and K + b. Then, we have
Aww mund =
LAww mny
Σ EJAW
/ E
jE Lb
(25)
<max
Aw
E AAW ammmn)l E jeb
(26)
Without loss of generality, let A.W. mns
Ej Awmn.
max Σ Aw
ElAW ma,
- Law mas I E jeb
(27)
mnn
-0.5.a.
(28)
Therefore, we can always find k = AW mnnll S [0.5 aa elements in f, with size of to flip
down and make AWW. m.nii < 0.5. For example, if A, m.n.i = 3.2, we need to flip 3 elements with positive perturbation (rounding up) to negative (rounding down) with -3.0 mutation. Then, we have
arg min
E
Aw m2nj)
+
LAW m.nd
E m.nyl
(29)
AW mun:
For each kernel AW sufficiency of Eq. 10 has been proven:
m.n.i 2 O, AW m.nii
has the minimum value k- - Σ; AW m.ni
S 0.5. The
AW
arg Aww m AAA We
AW minil S 0.5
(30)
AW
mm:
When = K,b b = 0 and all perturbation = 0.5, original Σ, AwW maxi have the upper bound 0.5 K.
Proof.
If flip
+ elements for n-th kernel, the Aw mund reduce to
k
E AW mnil and
k Aw m.n.i
respectively. Obviously,
k
Aw Σ
Σ Aw m.ni
-1 Σ
Aw
> 0.5,
(31)
m.R.i
mund
k 1
Σ AW
mni
| AW mmnil
+1
Aw muna
0.5.
(32)
With other numbers + k, only one value, i.c., the minimum value, with k flipped elements satisfy the Eq. (10). The necessity of Eq. (10) has been proven:
also draw the same conclusions. Therefore, when r3 0.5, there is
arg min AW ? WAW m.n.y
Aw
mad I =
(33)
AW MuA.
Similarly, extend all conclusions SQuant-C.
16

---

Published as a conference paper at ICLR 2022
For SQuant, only consider the flipping operation in one quantization step and select the elements whose sign is the same as E, m.ni
m.n.i because flipping with more quantization steps (e.g., flip 0.7 to -1.0) and the elements with different perturbation signs will cause a more significant perturbation and will violate the Eq. ( We explain that in the next section.
B.2 PROOF OF TOK-k k PERTURBATION ALGORITHM
Proof. We will prove the SQuant-F&K will lead to the top-k algorithm. We have the composition SQuant-E and SQuant-K optimization objective for n-th kernel,
arg min
Σ (AW ?
+
(L m.n.
(34)
AW
which is the first two items of Eq.
Without loss of generality, we assume c = A,W > 0, then SQuant needs to flip k = [e] elements with perturbation > 0 to transform E, m... e k and is still constant e k regardless of which & elements are. Therefore, the k elements are only determined by the first item of Eq. (34b. Σ, (AW: m. We denote as the index set of the flipped elements and
8
m.n
the original perturbation O AW. m.n.: for n-th kernel. Therefore, O, > 0, j ef. Substituting f and O
Eq. 34 we have the optimization objective for f Fffee flipping elements,
argmin
Σ(0.1)
14 j ff 0,
(35)
-argmin
[(.))
[ [10)1) (000))=[((10001 (1-10,1) jEf, 0,>0
(36)
arg min
[[11-10,)2-
0,
(37)
argmin
E11-200)), 1ef.0,>0
(38)
arg max
E(0,)). jef. 0 >0
(39)
Therefore, the Eq. 33) is essentially the top-k perturbation algorithm. We can easily extend the top-k algorithm in SQuant-C and design the perturbation update algorithm in B.3
B.3 PERTURBATION UPDATE ALGORITHM
SQuant-K initializes all rounded elements as flip candidates. After SQuant-K, we update the flip candidates for SQuant-C as shown in algorithm based on the insight of top-k perturbation algorithm B.2))
Over SQuant First we define the situation of k > lel as "Over SQuant" (line 6). For example, if we have kernel with e = + 1.6,, we need to SQuant it to -0.4 to satisfy in (-0.5, 0.5) with flipping k= 2 elements (2.6, 2.7] to (2, Obviously, when SQuant-C needs this kernel to calibrate, the last element 2.7 should be the first and the only candidate (line 7,8) to flip back to the original rounded number 3 to make the +0.6, due to it has the largest element perturbation in the k fliped elements and the smallest element perturbation (1 0.3| < 0.5) after it flips back. It is vice versa for < 0.
Under SQuant For " "Under SQuant" (line 9), need to make the first un- un-flipped element the flip candidate (line 10, 11) for SQuant-C, and will lead the kernel to "Over SQuant" with absolute kernel perturbation in (0.5, 1.0) when SQuant-C flips this element of the kemnl.
Finally, each kernel has only one candidate flip element for SQuant-C to satisfy Eq. 8 In practice, it is easy to fuse the perturbation update algorithm with the flip algorithm without extra overhead.
B.4 COMPLEXITY ANALYSIS
The original optimization problem described by Eq. 4 is NP-hard with (M-22N) Based on the SQuant approximation, the new optimization objective is to minimize CASE whose complexity is
17

---

Published as a conference paper at ICLR 2022
Algorithm 4: Perturbation Update Algorithm.
Input: Weight perturbation p:
Output: Updated weight perturbation
def opoatsserrturbatiioo (p)
e= LtPp// Accumulated perturbation (signed CASE)
ple p < =0 Disable Elementss/ernell with different sign from e.
== [|e]] // Flip k clements/kernels based the CASE.
f= TopK( pl. k)indices/// Indices of largest perturbation.
k lel then // Over SQuant.
i f // The k-th (last) element of f. p: // 0.5 S 1.0
else // Under SQuant.
i = pp. ( I).idddccss((+1)/// The (k+1)-th largest element of p.
10
p; // 0.5
12
0 /// Disable all elements.
13
pj = v // The only flip olement candidate of the kernel for sQuant-C.
return p
O(M-27 2 for SQuant-C, OMN-2 for SQuant-K and O(MNK) for SQuant-E. SQuant is optimized top-k algorithm with significant complexity reduction O(n-log(ke for each sub- problem. Our experiments show that after SQuant-K pre-optimization, SQuant-C only requires a tiny top-k number, such = 32, to satisfy all cases. For 3 x kernel with 9 elements, SQuant-K K only needs k = 4 because the kernel CASE is always < 0.5K 4.5. Finally, their complexity can reduce to linear, O(M-N 5) for SQuant-C and OMN 9 2) for SQuant-K.
18


Reviews:
[{"review_id": "l71WZZ0Im6o", "reviewer": "Reviewer_hK2m", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written and well-motivated. After a successful approximation of the Hessian-based approach, the authors discuss how to minimize the necessity of activation distribution information in Section 3 (assuming that input feature maps auto-correlate with each other in a similar way). The experimental results are impressive in Section 4.\n\n(1) What are the limitations of this work? The quality of the proposed method would depend on the validity of the assumptions to ignore activation distribution. If a summary of limitations and assumptions of input distribution is provided, it would be helpful to understand why this work is only limited to certain CNN models as written in the paper. Since Transformers and MLPs are increasingly utilized for the area that has been dominated by CNN models, it would be necessary to describe which dataset or model architecture is best performed by the proposed method.\n\n(2) The flipping approach is limited to up or down with a step size of 1. Is there any chance to improve the accuracy further if we increase the step size (i.e., allowing wider flipping approaches)?\n\n(3) Flipping approach has been introduced to a few previous PTQ techniques (while such techniques usually assume that a calibration set is provided). How close is the proposed work to those previous flipping-based PTQ methods in terms of model accuracy? If the difference is marginal, does it mean that investigating input data distribution is inherently less important for CNN models? Is there any chance such a difference (between data-free PTQ and calibration-based PTQ) can be larger depending on the characteristics of the dataset? Since all experimental data in this paper is given for ImageNet only, this paper might present an impression that the proposed method might be optimized for ImageNet-like datasets.", "summary_of_the_paper": "This paper proposes a new data-free quantization method that does not require back-propagation nor fine-tuning. The key idea is adopting Hessian-based optimization that can be decomposed into three parts (SQuant-E, K, and C) corresponding to the three dimensions of the weight tensor (using a few approximations, such as cross-layer independence to simplify the optimization). Then, instead of MSE, the authors introduce CASE (constrained ASE) of weight perturbation. The experimental results show that the proposed DFQ method outperforms even GDFQ that is basically a kind of QAT. The proposed technique is especially useful for a low-bit quantization.", "summary_of_the_review": "This paper introduces a few reasonable assumptions to alleviate the efforts to estimate the input data distribution. Successful approximations lead to improved model accuracy even with a very small number of bits to represent weights.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UTCj5-P2cXD", "reviewer": "Reviewer_cncj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. I think the paper is very well written, with good illustrations.\n2. The related work section is thorough.\n3. The notations in Section 2.1 are necessary and helpful, so as the Algorithm 1 and 2. Otherwise, the notion of blocks, layers, elements, input/output channels, kernels will make the math become super confusing.\n4. The experimental results are state-of-the-art, with evaluations on various neural networks.\n5. I go through the math and find them generally correct. The decomposition/approximation idea is decent.\n\nWeaknesses:\n1. SQuant is for weight and activation quantization. I think the weight quantization part is well supported, but there lacks discussion about activation quantization. Especially, how it affects the accuracy of approximations/Hessian representations used in SQuant.\n2. Extra clarifications are needed for Equation 7 to 8. As I understand it, equation 7 to 8 works well for SQuant because of its iterative optimization on the three components. But generally, those two are not equivalent.\n3. How is the quantization range (min, max) determined in SQuant? Would SQuant work better if combined with other orthogonal PTQ methods?\n4. For completeness, I wonder about 4-bit quantization results of Shufflenet?\n\nSmall Issues:\n1. In supp A, extra W\n\n======Post Rebuttal======\n\nI think the rebuttal from the authors makes sense and can address my concerns (excluding non-technical issues such as novelty and potential influence). As a result, I maintain my score tending to accept.", "summary_of_the_paper": "In the manuscript, the authors propose SQuant, which is a data-free quantization method that can apply post-training quantization (PTQ) without any backpropagation.\n\nSpecifically, SQuant is taking advantage of approximated Hessian information. Based on the assumptions and deductions in the paper, SQuant tries to optimize constrained absolute sum of error (CASE) instead of MSE.\n\nThe authors show many experimental results to validate the effectiveness of SQuant.", "summary_of_the_review": "I think the manuscript is technically sound with a solid understanding of the PTQ problem. The experimental results are quite good. Since there are still clarifications to be made, and the fact that similar deductions and flipping methods exist in previous works, I recommend a weak acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ShnxR5qstNi", "reviewer": "Reviewer_uKzc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is overall clearly structured and written. The proposed method is well-motivated, and the resultant flipping solution is novel as far as I know. This paper provides a brilliant way to directly use discrete optimization for quantization instead of conventional training with gradient backpropagation. However, the following points still require some more clarifications.\n- It is not clear why the first-order term is omitted in equation (1).\n- It is not clear why the scaling parameters like e_{n,i}, k_n and c_m\nare omitted in equation (7). The solution from the proposed progressive optimization is not the only solution, and other solutions may still depend on these scaling parameters.", "summary_of_the_paper": "This paper proposes a data-free quantization method based on the second-order Taylor expansion of  loss, where the Hessian matrix is approximated with different levels: element-wise, kernel-wise and channel-wise. The authors progressively determine the quantized weights from element-wise to kernel-wise and then to channel-wise. The derivation and solution of the quantization are novel. Empirical results show that the proposed method outperforms recent data-free methods.\n\n", "summary_of_the_review": "This paper is well written, and the proposed method is novel.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "APnCac9qNWz", "reviewer": "Reviewer_xprS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: The main strength of this paper is the introduction of multi-scale approximation of Hessian matrix. Due to the scalability issue, it is impossible to store the entire matrix. Traditional methods usually only keep track of the diagonal terms. Inspired by matrix decomposition ideas, this paper adopt a diagonal + block-wise diagonal +  low rank approximation, which is a good idea. Experiment results also show that the matrix decomposition idea work well.\n\nWeakness: I think there are some flaws in the derivation of the optimization objective.\n\n1. In formula (2), H^{W_m^l} = l_m x^l (x^l)^T. But from formula (3) to formula (4), E[H^{W_m^l}] is replaced by E[x^l (x^l)^T], where l_m disappears. Why this step hold true?\n2. In formula (7), the objective is \\sum_{n, i} e_{n, i} (\\Delta W_{m,n,i}^l)^2 + \\sum_n k_n \\Delta W_{m,n,:}^l J_k \\Delta W_{m,n,:}^l^T + c_m \\Delta W_{m,:}^l J_NK W_{m,:}^l^T, but in formula (8), the coefficients e_{n, i}, k_n and c_m disappear. I understand that all the coefficients are positive from Appendix A.2., but as long as they are not all equal, the objective should be different without these coefficients. I don't quite understand how we get (8) from (7). ", "summary_of_the_paper": "In this paper, the authors propose a data-free quantization algorithm of deep neural networks called SQuant. The main idea of SQuant is to decompose the Hessian-based optimization objective into three components: element-wise, kernel-wise and channel-wise components. In order to jointly optimize these three objective functions, a constrained absolute sum of error (CASE) is studied and a progressive algorithm is used. Experiment results show that SQuant algorithm is able to keep higher accuracy with the same number of bits, compared to several baseline algorithms.", "summary_of_the_review": "The motivation to decompose the Hessian matrix into diagonal, block-wise diagonal and low-rank components is the crucial contribution of this paper. Experiment results show that the multi-scale optimization objective lead to good performance after quantization. I don't follow some steps in the derivations of the optimization objective. This paper will be better if the authors can illustrate these steps well.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a data-free quantization method that can be applied post-training quantization without backpropagation.  The method takes advantage of approximate Hessian information in a certain scalable approximate way. Based on the assumptions and deductions in the paper, SQuant tries to optimize constrained absolute sum of error (CASE) instead of MSE.  There are good empirical results showing the effectiveness of the method, and the paper is well written, and the method should be of broad interest.
Decision: Accept (Poster)