summaries: In the manuscript, the authors propose SQuant, which is a data-free quantization method that can apply post-training quantization (PTQ) without any backpropagation.  Specifically, 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.  The authors show many experimental results to validate the effectiveness of SQuant.

summaries: 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.

summaries: 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.

summaries: 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.

abstractText: 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 framework1.

authors:
Ron Banner
Yury Nahshan
Elad Hoffer
Daniel Soudry

title: Post-training 4-bit quantization of convolution networks for rapid-deployment

venue: arXiv preprint arXiv:1810.05723,

authors:
Yaohui Cai
Zhewei Yao
Zhen Dong
Amir Gholami
Michael W Mahoney
Kurt Keutzer

title: Zeroq: A novel zero shot quantization framework

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Yoojin Choi
Jihwan Choi
Mostafa El-Khamy
Jungwon Lee

title: Data-free network quantization with adversarial knowledge distillation

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Yoni Choukroun
Eli Kravchik
Fan Yang
Pavel Kisilev

title: Low-bit quantization of neural networks for efficient inference

venue: In ICCV Workshops,

authors:
Xin Dong
Shangyu Chen
Sinno Jialin Pan

title: Learning to prune deep neural networks via layer-wise optimal brain surgeon

venue: arXiv preprint arXiv:1705.07565,

authors:
Zhen Dong
Zhewei Yao
Yaohui Cai
Daiyaan Arfeen
Amir Gholami
Michael W Mahoney
Kurt Keutzer

title: Hawq-v2: Hessian aware trace-weighted quantization of neural networks

venue: arXiv preprint arXiv:1911.03852,

authors:
Zhen Dong
Zhewei Yao
Amir Gholami
Michael W Mahoney
Kurt Keutzer

title: Hawq: Hessian aware quantization of neural networks with mixed-precision

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
William Fedus
Barret Zoph
Noam Shazeer

title: Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity

venue: arXiv preprint arXiv:2101.03961,

authors:
Trevor Gale
Matei Zaharia
Cliff Young
Erich Elsen

title: Sparse gpu kernels for deep learning

venue: In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis,

authors:
Amir Gholami
Kiseok Kwon
Bichen Wu
Zizheng Tai
Xiangyu Yue
Peter Jin
Sicheng Zhao
Kurt Keutzer

title: Squeezenext: Hardware-aware neural network design

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops,

authors:
Ashish Gondimalla
Noah Chesnut
Mithuna Thottethodi
TN Vijaykumar

title: Sparten: A sparse tensor accelerator for convolutional neural networks

venue: In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture,

authors:
Yue Guan
Jingwen Leng
Chao Li
Quan Chen
Minyi Guo

title: How far does bert look at: Distance-based clustering and analysis of bert’s attention

venue: In Proceedings of the 28th International Conference on Computational Linguistics,

authors:
Yue Guan
Zhengyi Li
Jingwen Leng
Zhouhan Lin
Minyi Guo
Yuhao Zhu

title: Block-skim: Efficient question answering for transformer

venue: arXiv preprint arXiv:2112.08560,

authors:
Cong Guo
Bo Yang Hsueh
Jingwen Leng
Yuxian Qiu
Yue Guan
Zehuan Wang
Xiaoying Jia
Xipeng Li
Minyi Guo
Yuhao Zhu

title: Accelerating sparse dnn models without hardware-support via tile-wise sparsity

venue: In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis,

authors:
Cong Guo
Yangjie Zhou
Jingwen Leng
Yuhao Zhu
Zidong Du
Quan Chen
Chao Li
Bin Yao
Minyi Guo

title: Balancing efficiency and flexibility for dnn acceleration via temporal gpu-systolic array integration

venue: In 2020 57th ACM/IEEE Design Automation Conference (DAC),

authors:
Suyog Gupta
Ankur Agrawal
Kailash Gopalakrishnan
Pritish Narayanan

title: Deep learning with limited numerical precision

venue: In International conference on machine learning,

authors:
Song Han
Huizi Mao
William J Dally

title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding

venue: arXiv preprint arXiv:1510.00149,

authors:
Song Han
Jeff Pool
John Tran
William J Dally

title: Learning both weights and connections for efficient neural networks

venue: arXiv preprint arXiv:1506.02626,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Itay Hubara
Yury Nahshan
Yair Hanani
Ron Banner
Daniel Soudry

title: Improving post training neural quantization: Layer-wise calibration and integer programming

venue: arXiv preprint arXiv:2006.10518,

authors:
Benoit Jacob
Skirmantas Kligys
Bo Chen
Menglong Zhu
Matthew Tang
Andrew Howard
Hartwig Adam
Dmitry

title: Kalenichenko. Quantization and training of neural networks for efficient integer-arithmetic-only inference

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: Imagenet classification with deep convolutional neural networks

venue: Advances in neural information processing systems,

authors:
Yuhang Li
Ruihao Gong
Xu Tan
Yang Yang
Peng Hu
Qi Zhang
Fengwei Yu
Wei Wang
Shi Gu

title: Brecq: Pushing the limit of post-training quantization by block reconstruction

venue: arXiv preprint arXiv:2102.05426,

authors:
Yuang Liu
Wei Zhang
Jun Wang

title: Zero-shot adversarial quantization

authors:
Markus Nagel
Mart van Baalen
Tijmen Blankevoort
Max Welling

title: Data-free quantization through weight equalization and bias correction

authors:
Markus Nagel
Rana Ali Amjad
Mart Van Baalen
Christos Louizos
Tijmen Blankevoort

title: Up or down? adaptive rounding for post-training quantization

venue: In International Conference on Machine Learning,

authors:
Adam Paszke
Sam Gross
Francisco Massa
Adam Lerer
James Bradbury
Gregory Chanan
Trevor Killeen
Zeming Lin
Natalia Gimelshein
Luca Antiga

title: Pytorch: An imperative style, high-performance deep learning library

authors:
Xu Qian
Victor Li
Crews Darren

title: Channel-wise hessian aware trace-weighted quantization of neural networks

venue: arXiv preprint arXiv:2008.08284,

authors:
Haotong Qin
Yifu Ding
Xiangguo Zhang
Aoyu Li
Jiakai Wang
Xianglong Liu
Jiwen Lu

title: Diverse sample generation: Pushing the limit of data-free quantization

venue: arXiv preprint arXiv:2109.00212,

authors:
Yuxian Qiu
Jingwen Leng
Cong Guo
Quan Chen
Chao Li
Minyi Guo
Yuhao Zhu

title: Adversarial defense through network profiling based path extraction

authors:
Sheng Shen
Zhen Dong
Jiayu Ye
Linjian Ma
Zhewei Yao
Amir Gholami
Michael W Mahoney
Kurt Keutzer

title: Q-bert: Hessian based ultra low precision quantization of bert

venue: In Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

authors:
Yang Wang
Chen Zhang
Zhiqiang Xie
Cong Guo
Yunxin Liu
Jingwen Leng

title: Dual-side sparse tensor core

venue: In Proceedings of the 48th Annual International Symposium on Computer Architecture,

authors:
Ziwei Wang
Jiwen Lu
Chenxin Tao
Jie Zhou
Qi Tian

title: Learning channel-wise interactions for binary convolutional neural networks

authors:
Yikai Wu
Xingyu Zhu
Chenwei Wu
Annie Wang
Rong Ge

title: Dissecting hessian: Understanding common structure of hessian in neural networks

venue: arXiv preprint arXiv:2010.04261,

authors:
Shoukai Xu
Haokun Li
Bohan Zhuang
Jing Liu
Jiezhang Cao
Chuangrun Liang
Mingkui Tan

title: Generative low-bitwidth data free quantization

venue: In European Conference on Computer Vision,

authors:
Zhewei Yao
Zhen Dong
Zhangcheng Zheng
Amir Gholami
Jiali Yu
Eric Tan
Leyuan Wang
Qijing Huang
Yida Wang
Michael Mahoney

title: Hawq-v3: Dyadic neural network quantization

authors:
Shixing Yu
Zhewei Yao
Amir Gholami
Zhen Dong
Michael W Mahoney
Kurt Keutzer

title: Hessian-aware pruning and optimal neural implant

venue: arXiv preprint arXiv:2101.08940,

authors:
Xiangguo Zhang
Haotong Qin
Yifu Ding
Ruihao Gong
Qinghua Yan
Renshuai Tao
Yuhang Li
Fengwei Yu
Xianglong Liu

title: Diversifying sample generation for accurate data-free quantization

authors:
Xiangyu Zhang
Xinyu Zhou
Mengxiao Lin
Jian Sun

title: Shufflenet: An extremely efficient convolutional neural network for mobile devices

authors:
Zhekai Zhang
Hanrui Wang
Song Han
William J Dally

title: Sparch: Efficient architecture for sparse matrix multiplication

venue: IEEE International Symposium on High Performance Computer Architecture (HPCA),

authors:
Ritchie Zhao
Yuwei Hu
Jordan Dotzel
Chris De Sa
Zhiru Zhang

title: Improving neural network quantization without retraining using outlier channel splitting

authors:
Bohan Zhuang
Mingkui Tan
Jing Liu
Lingqiao Liu
Ian Reid
Chunhua Shen

title: Effective training of convolutional neural networks with low-bitwidth weights and activations

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

heading: 1 INTRODUCTION

text:
With the widespread application of DNN, more and more DNN models are deployed on both computation-constrained and memory-constrained environments, e.g., smartphones, IoT devices, and self-driving cars. The desire for lightweight and energy-efficient DNN deployment solutions is increasing. Quantization is one of the most promising techniques to convert weights and activations to lower bit formats and simultaneously 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 et al., 2021). 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 et 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. 1https://github.com/clevercool/SQuant
In contrast, data-free quantization (DFQ) has recently been presented as a 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., 2021; Choi et al., 2020). From a deployment perspective, DFQ is the most attractive quantization method since we can apply it to any trained models as a black box postprocessing step. However, current DFQ methods cannot achieve high accuracy and fast processing time simultaneously. Traditionally, DFQ (Nagel et al., 2019) uses rounding quantization, leading to the rounding-to-nearest strategy. Such a strategy causes significant accuracy loss, especially in low-bit settings. To bridge the accuracy gap between data-free and data-driven quantization, researchers propose a series of data-generative DFQ methods. They use gradient-based methods to 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., 2021).
To solve this dilemma, we propose SQuant, a 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 a 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 to a single or a 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 a 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 a layer and the overall network of ResNet18, respectively. As it does not require back-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 state-of-the-art DFQ methods, SQuant achieves higher accuracy on all evaluated models under the 4/6/8-bit settings. SQuant only introduces 0.1% accuracy loss on 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 a new frontier.

heading: 2 PRELIMINARIES

heading: 2.1 NOTATIONS

text: 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., c,M. Column vector and flattened matrix are denoted by bold lowercase letters, e.g., w, and matrices (or tensors) are 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`i, j. E[·] denotes the expectation operator, and the network loss function is represented by L (·). 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 × kernel width, respectively. Specifically, FC has the shape of (M,N,1).

heading: 2.2 QUANTIZATION

text: Most previous works adopt the rounding-to-nearest approach for quantizing deep neural networks by rounding elements w to the nearest quantization grid values with a fixed-point data type. The quantization and dequantization for a quantized element ŵ can be described as ŵ = s · clip(bws e,min,max), where s denotes the quantization scale parameter and, min and max are the lower and upper thresholds for the clipping function clip(·). The operator b·e represents the rounding-to-nearest, i.e., minimizing the mean squared error (MSE) between the quantized and the original value.

heading: 2.3 HESSIAN-BASED OPTIMIZATION FOR NEURAL NETWORKS

text:
The Hessian-based approach is one of the most promising optimizations to further improve the quantization (Dong et al., 2019b;a; Nagel et al., 2020; Shen et al., 2020; Qian et al., 2020; Wu et al., 2020; Hubara et al., 2020; Li et al., 2021; Yao et al., 2021) and pruning (Yu et al., 2021) performance for DNN models. Some of those works exploit the Hessian matrix to approximate loss degradation due to the quantization perturbation of weight, ∆W, by
E[L (X,Y,W+∆W)−L (X,Y,W)]≈E[∆W ·gW + 1 2 ∆W ·HW ·∆WT ], (1)
where the equation comes from second-order Taylor series expansion, gW is the gradient and HW 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 to 0 and thus can be safely ignored. However, computing HW is infeasible because of the large memory overhead and computation complexity. To tackle this problem, we approximate HW as a layer-wise Hessian matrix HW` under the assumption of cross-layer independence (Dong et al., 2017; Nagel et al., 2020), i.e., HW` = x`x`T ⊗∇2y`L , where ⊗ denotes Kronecker product of two matrices, ∇2y`L is the Hessian of the task loss w.r.t. y `.
For the m-th output channel of Conv or FC, HW` can be approximatively simplified into output channel-wise (Nagel et al., 2020; Yu et al., 2021; Wu et al., 2020; Qian et al., 2020),
HW ` m ≈ ∇2y`Lm,m ·x `x`T = lm ·x`x` T , (2)
where ∇2y`L is approximately a diagonal matrix. Then the final optimization objective is
∆Ŵ`m,: =argmin ∆W`m,: ∆W`m,:E[HW ` m ]∆W`m,: T (3)
=argmin ∆W`m,:
∆W`m,:E[x`x` T ]∆W`m,: T = argmin ∆W`m,: E[(∆W`m,:x`)2], (4)
which is the MSE between the output activation produced from original and quantized weights. Each sub-problem deals with a single output channel ∆W`m,:. We will further approximate Eq. (4) to remove any input data dependency from the optimization objective in Sec. 3.2.

heading: 3 METHODOLOGY

heading: 3.1 OVERVIEW

text:
Although we can obtain a good quantization strategy by minimizing MSE for each output channel, it is an NP-hard combinatorial optimization problem. Even approaching an 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 to the dimensions of weight, in Sec. 3.2. Due to the quantization with a fixed-point data type, SQuant transforms the problem into a data-free optimization problem in the discrete domain. SQuant dedicates to optimizing each layer’s weight employing a flipping approach (Nagel et 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 a 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 a proper f based on Eq. (8), in Sec. 3.4.

heading: 3.2 DIAGONAL HESSIAN APPROXIMATION

text:
In this work, we propose a new approximation of the Hessian matrix to cover non-diagonal elements and decompose Eq. (4) into three sub-items that correspond to the three dimensions of the weight
tensor as illustrated in Fig. 1: SQuant-E for element-wise optimization covers the diagonal elements of Hw`m (H-E); SQuant-K for kernel-wise optimization covers the diagonal blocks of Hw`m (H-K); SQuant-C for output channel-wise optimization covers the whole Hw`m (H-C).
The E[x`x` T ] can be approximated by the following equation:
E[x`x` T ]≈ E+K+C, (5)
where C = cmJNK ,
K = k1JK . . . kNJK  , and E = e1,1 . . . eN,K  . In the above equations, JNK is an all-one matrix with the dimension of N×K (denoted as NK), and cm is a constant value for m-th output channel. K is a diagonal block matrix, where JK represents an all-one matrix with the dimension of K×K. The n-th diagonal block corresponds to n-th kernel in convolution and has its own constant value kn. E is a diagonal matrix with the diagonal elements of en,i, each of which is a 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 E[x`x` T ] as possible, which we explain in Appendix A.1. The matrix C catches the common component of 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 convolution layers by using matrix K. For each inference, the weights of a kernel, W`m,n,:, scan the same feature map. As a result, the corresponding x has nearly the same expectation values in the center area, with a small perturbation in the marginal area due to padding. Therefore, knJK as a kernel-wise approximation achieves a low approximate error for convolution. For any E[x`x` T ], we can always find a decomposition that satisfies en,i,kn,cm > 0, for which we present the decomposition method in Appendix A.2. Substituting Eq. (5) into Eq. (4) yields the following equation.
∆W`m,:E[x`x` T ]∆W`m,: T ≈∑ n,i en,i∆W`m,n,i 2 +∑ n kn∆W`m,n,:JK∆W ` m,n,: T + cm∆W`m,:JNK∆W ` m,: T . (6)

heading: 3.3 DATA-FREE OPTIMIZATION

text:
To achieve the data-free optimization objective, we omit the coefficients (en,i, kn 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 be easily found that there are no training samples needed to minimize,
argmin ∆W`m,: ∑ n,i
∆W`m,n,i 2 +∑
n ∆W`m,n,:JK∆W ` m,n,:
T +∆W`m,:JNK∆W ` m,: T (7)
=argmin ∆W`m,: ∑ n,i
∆W`m,n,i 2 +∑
n (∑ i ∆W`m,n,i)
2 +(∑
n,i ∆W`m,n,i)
2 . (8)
Next, we transform the overall objective Eq. (8) 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.e., the first item in Eq. (8), the problem is reduced to the following objective, which we call SQuant-E.
∆Ŵ`m,: = argmin ∆W`m,: ∑ n,i
∆W`m,n,i 2 = argmin
∆W`m,n,i
|∆W`m,n,i| ⇔ ∀∆Ŵ`m,n,i, |∆Ŵ`m,n,i| ≤ re = 0.5, (9)
SQuant-E is essentially the rounding method when re = 0.5. Rounding does not introduce any approximate error and has O(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 the diagonal elements the matrix E[x`x` T ] while ignores the rest majority elements.
For kernel-wise item (the second item in Eq. (8)), we have the following objective called SQuant-K,
∆Ŵ`m,: = argmin ∆W`m,: ∑ n (∑ i ∆W`m,n,i)
2 = argmin
∆W`m,n,: |∑ i ∆W`m,n,i| ⇔∀∆Ŵ`m,n,:, |∑ i ∆Ŵ`m,n,i| ≤ rk = 0.5, (10)
where |∑i ∆W`m,n,i| is the Absolute Sum of Error (ASE) of each kernel-wise weight matrix in the convolution and rk 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,
∆Ŵ`m,: = argmin ∆W`m,: (∑ n,i ∆W`m,n,i) 2⇔∀∆Ŵ`m,:, |∑ n,i ∆Ŵ`m,n,i| ≤ rc = 0.5. (11)
Relaxation Obviously, re = 0.5 is against rk = 0.5 because rounding (re = 0.5) only guarantees the upper-bound ṙk = 0.5K for SQuant-K. Some elements need to relax the constraint re to a larger number, such as 1.0, to satisfy rk = 0.5. Similarly, SQuant-C also needs to relax rk = 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 ±1 integer mutation. Formally, we need to work out a 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 fm will be
∀(m,n, i) /∈ fm, |∆W`m,n,i| ≤ 0.5; ∀(m,n, j) ∈ fm, 0.5≤ |∆W`m,n, j|< 1.0, (12)
where fm is the index set of flipped elements for m-th output channel. Specifically, we need to flip k = bASEe elements, whose perturbation has the same sign as ∑i ∆W`m,n,i. We prove the equivalence for Eq. (10) and Eq. (11) by illustrating the transformation process to a discrete problem in Appendix B.1.
However, any k elements can satisfy Eq. (10) leading to large search space. Fortunately, based on Eq. (9), SQuant-K can select specific k elements with the top-k largest perturbation because they will have the smallest perturbation after flipping under the constraint of SQuant-E. Therefore, we adopt the Constrained ASE (CASE) to optimize the SQuant-E&K 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 a kernel to satisfy the constraint rk = 1.0.
The following section will introduce an efficient SQuant algorithm with a linear computation complexity for CASE flipping.

heading: 3.4 ON-THE-FLY SQUANT

text:
Progressive Algorithm We design a progressive algorithm illustrated in algorithm 1 to meet our stated optimization objective, i.e., minimizing the CASE of weight perturbation. The critical 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 flips certain rounded elements. After the SQuant-K calibration, SQuant-C then further flips SQuanted kernels.
We start by rounding the weight and updating its perturbation to satisfy re = 0.5 (Line 4-5). Then we run the SQuant-K (Line 6) to flip specific elements under re = 1.0, satisfy rk = 0.5, and update kernel perturbation (Line 7). The follow-up SQuant-C (Line 8) further flips specific kernels under rk = 1.0 and satisfy rc = 0.5. Finally, we derive the quantized weights (Line 9).
Algorithm 1: Progressive SQuant Algorithm. Input: Weight tensor W of layer `, scale factor s of layer `. Output: Quantized weight tensor C of layer `.
1 foreach m ∈ [1, ..,M] do // SQuant-C: SQuant M output channels. 2 foreach n ∈ [1, ..,N] do // SQuant-K: SQuant N kernels. 3 foreach i ∈ [1, ...,K] do // SQuant-E: Round K elements. 4 Em,n,i = bWm,n,i/sme // Scale and SQuant-E (Rounding). 5 ∆Em,n,i = Em,n,i−Wm,n,i // Element perturbation. 6 Km,n,: = SQuantFlip(Em,n,:, ∆Em,n,:)// SQuant-K. 7 ∆Km,n,: =UpdatePerturbation(∆Em,n,:) // Kernel perturbation. 8 Cm,: = SQuantFlip(Km,:, ∆Km,:) · sm// SQuant-C. 9 return C
Flip Algorithm SQuant-K and SQuant-C can utilize the same flip function. The goal of the flip algorithm is to find a proper element set 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 e 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 = b|e|e elements and reduce |e|< rk = 0.5 (Line 4). Finally, we flip k weights with the largest |p| (Line 5-6). For now, we have SQuanted the kernel and tuned kernel CASE to |e| ≤ rk = 0.5. Specifically, for FC and Conv with a kernel size of (1,1), we can skip the SQuant-K. As mentioned in Section 3.3, SQuant-C flips only one element in each kernel. Therefore, we update the kernel perturbation (Line 7 of algorithm 1) for SQuant-C to flip kernel illustrated in Appendix B.3. As a result, SQuant successfully identifies the optimum combination f under a 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.
1 def SQuantFlip(w, p): 2 e = ∑i pi// Accumulated perturbation. 3 p[e ·p < 0] = 0 // Disable Elements/kernels with different sign from e. 4 k = b|e|e // Flip k elements/kernels based on the CASE. 5 f = TopK(|p|, k).indices// Indices of k largest perturbation. 6 w[f] = Flip(w[f])// Flip k elements/kernels with same sign as e. 7 return w
On-the-Fly Framework From the overall perspective of the optimization, SQuant-K has MN subproblems, 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 back-propagation nor fine-tuning, SQuant can run on inferenceonly 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.

heading: 4 EXPERIMENTS

text:
For demonstrating the strength of SQuant, we evaluate the SQuant as well as four SOTA methods, DFQ (Nagel et al., 2019), ZeroQ (Cai et al., 2020), DSG (Zhang et al., 2021; Qin et al., 2021), and
Arch Method No BP No FT W-bit A-bit Top-1
ResNet18
Baseline – – 32 32 71.47
DFQ X X 4 4 0.10 ZeroQ 7 X 4 4 19.09 DSG 7 X 4 4 34.53 GDFQ 7 7 4 4 60.60 SQuant X X 4 4 66.14 DFQ X X 6 6 67.30 ZeroQ 7 X 6 6 69.84 DSG 7 X 6 6 70.46 GDFQ 7 7 6 6 70.13 SQuant X X 6 6 70.74 DFQ X X 8 8 69.70 ZeroQ 7 X 8 8 71.43 GDFQ 7 7 8 8 70.68 SQuant X X 8 8 71.47
ResNet50
Baseline – – 32 32 77.74
ZeroQ 7 X 4 4 7.75 DSG 7 X 4 4 23.10 GDFQ 7 7 4 4 55.65 SQuant X X 4 4 70.80 ZeroQ 7 X 6 6 72.93 DSG 7 X 6 6 76.07 GDFQ 7 7 6 6 76.59 SQuant X X 6 6 77.05 ZeroQ 7 X 8 8 77.65 DSG 7 X 8 8 77.68 GDFQ 7 7 8 8 77.51 SQuant X X 8 8 77.71
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.
Arch Method No BP No FT W-bit A-bit Top-1
Inception V3
Baseline – – 32 32 78.81
ZeroQ 7 X 4 4 18.20 GDFQ 7 7 4 4 70.39 SQuant X X 4 4 73.26
ZeroQ 7 X 6 6 74.94 GDFQ 7 7 6 6 77.20 SQuant X X 6 6 78.30
ZeroQ 7 X 8 8 78.78 GDFQ 7 7 8 8 78.62 SQuant X X 8 8 78.79
Squeeze Next
Baseline – – 32 32 69.38
ZeroQ 7 X 4 4 0.09 GDFQ 7 7 4 4 28.93 SQuant X X 4 4 43.45
ZeroQ 7 X 6 6 16.54 GDFQ 7 7 6 6 65.46 SQuant X X 6 6 67.34
ZeroQ 7 X 8 8 68.18 GDFQ 7 7 8 8 68.22 SQuant X X 8 8 69.22
Shuffle Net
Baseline – – 32 32 65.07
ZeroQ 7 X 6 6 35.21 GDFQ 7 7 6 6 60.12 SQuant X X 6 6 60.25
ZeroQ 7 X 8 8 64.34 GDFQ 7 7 8 8 64.03 SQuant X X 8 8 64.68
Table 2: Results of data-free methods with InceptionV3, SqueezeNext, and ShuffleNet.
GDFQ (Xu et al., 2020), with 5 different CNN models including ResNet-18 & 50 (He et al., 2016), Inception V3 (Szegedy et al., 2016), SqueezeNext (Gholami et al., 2018) and ShuffleNet (Zhang et 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 a layerwise manner (per-tensor). We utilize a uniform distribution as the initialization for the activation quantization range. All DFQ algorithms are implemented with PyTorch (Paszke et al., 2019) and evaluated on Nvidia GPU A100-40GB. Unless otherwise stated, we employ both weight and activation quantization in all experiments. Also, uniform quantization grids are used in all experiments, and hyper-parameters, e.g., re = rk = 1.0 and rc = 0.5, for all SQuant experiments are the same.

heading: 4.1 COMPARISON TO SOTA METHODS

text:
Table 1 and Table 2 show the results on 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-propagation. The former two are PTQ methods, while the last is a QAT method, which retrains the network with the synthetic data. DFQ is the only true data-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
than the lower-bit quantization does because of higher precision. The benefit of SQuant becomes more prominent as 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 even surpasses more than 15% in ResNet50 under 4-bit quantization, although GDFQ is a quantization-aware training method.
Table 1 and Table 2 also 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 a critical role in the overall model quantization. However, GDFQ requires fine-tuning (FT) with back-propagation (BP). In contrast, SQuant adopts a direct optimization objective of weight perturbation, which does not require finetuning 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 is to minimize the CASE of weight perturbation.

heading: 4.2 SQUANT EFFICIENCY

text: The trade-off between efficiency and accuracy is challenging for previous DFQ methods. Before SQuant, DFQ is the fastest one since it does not require back-propagation and fine-tuning, but it 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 a 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 to 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 we quantize layers in parallel. A single layer takes SQuant just 3 milliseconds on average because SQuant does not involve complex algorithms, such as back-propagation 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.

heading: 4.3 ABLATION STUDY

text:
SQuant Granularity We decouple the effect of SQuant-K and SQuant-C, which have different granularities to optimize CASE. As shown in Table 4, their accuracies both outperform SQuant-E
(i.e., rounding), and combining them leads to higher accuracy for ResNet18. SQuant-E&C has a 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-E&K&C 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 et al., 2020) is a 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.

heading: 5 RELATED WORK

text:
Compression is a promising method to reduce the DNN model’s memory and computation cost. Pruning (Han et al., 2015b;a) is 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 et al., 2020; Guan et al., 2020; Qiu et al., 2019; Guo et al., 2020a; Guan et al., 2021; Fedus et al., 2021) and hardware (Gondimalla et al., 2019; Guo et al., 2020b; Zhang et al., 2020; Wang et al., 2021) optimization to accelerate.
Quantization is more practical because it can be supported directly by existing accelerators. Quantization-aware training (QAT) (Gupta et al., 2015; Jacob et al., 2018; Wang et al., 2019; 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 as data-free quantization (DFQ), including PTQ (Nagel et al., 2019; Cai et al., 2020; Zhang et al., 2021) and QAT (Xu et al., 2020; Liu et al., 2021; Qin et al., 2021; Choi et al., 2020). DFQ (Nagel et al., 2019) and ACIQ (Nagel et al., 2019) rely on weight equalization or bias correction without requiring synthetic data. Other works synthesize the data to calibrate or fine-tune the network based on the batch normalization statistics (Cai et al., 2020) or adversarial knowledge distillation techniques (Liu et al., 2021; Choi et al., 2020).

heading: 6 CONCLUSION

text: This paper approximates and composes the original Hessian optimization objective into the CASE of weight perturbation with a data-free premise. Surprisingly, CASE only involves the weight perturbation and requires no knowledge of any datasets or 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 back-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 to a sub-second level.

heading: ACKNOWLEDGMENTS

text: 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 2021ZD0110104, and the National Natural Science Foundation of China (NSFC) grant (U21B2017, 62072297, and 61832006).

heading: A APPROXIMATION AND DECOMPOSITION

text:
A.1 APPROXIMATED HESSIAN MATRIX FOR DATA-FREE QUANTIZATION
The quantization loss function for the entire network is
L (∆W) = ∆WE[H]∆WT . (13)
Consider a convolution layer defined as
Ym,h,w = ∑ n,i, j Wm,n,i, jXn,h−i,w− j. (14)
Here, Y has three dimensions, output channel, output feature map height, and output feature map width, i.e., (M×OH×OW ) indexing by (m,h,w), W has four dimensions, output channel, input channel, kernel height, kernel width, i.e., (M×N ×KH ×KW ) indexing by (m,n, i, j), and X has three dimensions, input channel, input feature map height, and input feature map width, i.e., (N× IH × IW ) indexing by (n,h− i,w− j). Ignoring the interaction between layers and output
channels following Nagel et al. (2020), for a specific convolution layer l and output channel m, the elements of corresponding output channel-wise Hessian HW`m is
HW ` m n,i, j,n′,i′, j′ = ∂ 2L
∂Wm,n,i, j∂Wm,n′,i′, j′ (15)
= ∂ ∂Wm,n,i, j ∑h,w ∂L ∂Ym,h,w ∂Ym,h,w ∂Wm,n,i, j (16)
= ∂ ∂Wm,n,i, j ∑h,w ∂L ∂Ym,h,w Xn,h−i,w− j (17)
=∑ h,w
( ∂
∂Ym,h,w ∂L ∂Ym,h′,w′
) Xn,h−i,w− j (18)
=∑ h,w
( ∂
∂Ym,h,w ∑h′,w′ ∂L ∂Ym,h′,w′ Xn′,h′−i′,w′− j′
) Xn,h−i,w− j (19)
=∑ h,w ∑ h′,w′ ∂ 2L ∂Ym,h,w∂Ym,h′,w′ Xn,h−i,w− jXn′,h′−i′,w′− j′ (20)
Assuming ∇2y`L is a diagonal matrix yields Eq. (30) in (Nagel et al., 2020)
HW ` m
n,i, j,n′,i′, j′ ≈∑ h,w ∂ 2L ∂Y2m,h,w Xn,h−i,w− jXn,h−i′,w− j′ . (21)
To make Eq. (13) get irrelevant to training samples, we assume that input feature maps auto-correlate with each other in a similar way, resulting in
E[HW ` m
n,i, j,n′,i′, j′ ] =E[∑ h,w ∂ 2L ∂Y2m,h,w Xn,h−i,w− jXn′,h−i′,w− j′ ]≈ cm (22)
for all n, i, j,n′, i′ and j′, where cm is a constant. It should be noted that Eq. (22) is a strong assumption. For more accurate approximation, we further look into each input channel (i.e., n = n′, i 6= i′, and j 6= j′), and find
E[H W`m,n i, j,i′, j′ ] =E[∑
h,w ∂ 2L ∂Y2m,h,w Xn,h−i,w− jXn,h−i′,w− j′ ]≈ km,n, (23)
for all i, j, i′, and j′, where km,n is a constant. It is generally true because the kernel size is usually much smaller than the size of feature maps, so the shift introduced by different i, j, i′, and j′ is a small perturbation of E[H W`m,n i, j,i′, j′ ] compared with the summation over the entire feature map. Finally, we focus on each diagonal element of Hessian matrix (i.e., n = n′, i = i′, and j = j′) and denote
E[HW ` m,n,i, j ] =E[∑
h,w ∂ 2L ∂Y2m,h,w X2n,h−i,w− j] = em,n,i, j, (24)
where em,n,i, j is a constant. Please note that the output channel-wise expected Hessian matrix E[HW ` m
n,i, j,n′,i′, j′ ] is a principle submatrix of E[H], so it must positive semi-define. Therefore, we set em,n,i, j > km,n > cm > 0 to ensure the approximation to E[H W`m n,i, j,n′,i′, j′ ] is also positive semi-define and nontrivial. Considering Eq. (22), Eq. (23), and Eq. (24) at the same time, we can get the approximation to expected Hessian shown in Eq. (5). Extending the discussion to fully connected layer is straightforward thus omitted here.
A.2 DECOMPOSITION
In this section, we present the decomposition method for HW`m = lmE[x`x` T ] illustrated in the algorithm 3. First, we construct three matrices with the shape of (NK,NK), C′ = JNK ,
K′ = JK . . . JK  , and E′ = 1 . . . 1  . Here, JNK is an all-one matrix with dimension NK = N×K and JK represents an 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 a diagonal matrix whose diagonal elements are 1.
Algorithm 3: E[x`x` T ] Decomposition.
Input: E[x`x` T ], H;
Channel-wise matrix, C′. Kernel-wise matrix, K′. Element-wise matrix, E′.
Output: Matrix E,K, and C. 1 H′ = |H| 2 cm = (1− ε) ·min(H′) // Output channel-wise. 3 C = cmC′ 4 foreach n ∈ [1, ...,N] do // Kernel-wise. 5 kn = (1− ε ′n) ·min(H′n:n+K, n:n+K− cm) 6 Kn,: = knK′n,: 7 foreach i ∈ [1, ...,K] do // Element-wise. 8 en,i = H′n×K+i, n×K+i− cm− kn 9 En,i = en,iE′n,i
10 return E,K,C
In algorithm 3, 0 < ε,ε ′ < 1, and we can get the matrices E,K, and C. Evidently, algorithm 3 can make cm > 0, kn > 0, and en,i > 0 for any E[x`x` T ]≈ E+K+C.
A.3 APPROXIMATION ERROR ANALYSIS
To achieve the data-free optimization objective, we omit the coefficients (en,i, kn and cm) in Eq. (6), which leads to the approximate objective in Eq. (8) optimized by our fast SQuant framework. We approximate Eq. (6) to Eq. (8) to 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 1 and Table 2 of the manuscript. The intuition behind the approximation is that we use an iterative process which progressively reduces each term of Eq. (6). Because each term’s coefficient (en,i, 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 en,i, kn, and cm in Eq. (6). To quantify the approximation error in our SQuant framework, we evaluate a metric called approximation precision and show that we achieve a nearly 95% approximation precision.
Since SQuant uses the flipping-based iterative optimization framework to minimize Eq. (8), we define an element as 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 of the correct element based on data-free Eq. (8) compared to data-driven Eq. (6), i.e.,
AP = Number of correct elements Number of flipped elements .
We perform the above approximation error analysis on ResNet18 with ImageNet under 4-bit weightonly quantization. We evaluate the SQuanted weight on the inference datasets. We compute the coefficients en,i, kn, and cm with 1000 samples. Table 6 shows 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.

heading: B SQUANT ALGORITHM

text:
B.1 DISCRETE OPTIMIZATION PROBLEM
We introduce the transformation of the discrete optimization problem. We know that the quantization is to round the scaled elements to the integer grid. Each quantization step has two rounding directions, rounding up and down, with a 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 we can always find k = b|∑i ∆W`m,n,i|e elements to flip and reduce |∑i ∆Ŵ`m,n,i| ≤ 0.5.
Proof. Assume n-th kernel has K elements, a rounded up elements with index set fa have positive perturbation, b rounded down elements with index set fb have negative perturbation, and K = a+b. Then, we have
|∑ i
∆W`m,n,i|= ∣∣∣∑
t ∆W`m,n,t −∑ j |∆W`m,n, j| ∣∣∣, t ∈ fa, j ∈ fb (25) ≤max(∑
t ∆W`m,n,t , ∑ j |∆W`m,n, j|), t ∈ fa, j ∈ fb (26)
Without loss of generality, let ∑t ∆W`m,n,t > ∑ j |∆W`m,n, j|,
max(∑ t ∆W`m,n,t , ∑ j |∆W`m,n, j|) =∑ t ∆W`m,n,t t ∈ fa, j ∈ fb (27)
≤0.5 ·a. (28) Therefore, we can always find k = b|∑i ∆W`m,n,i|e ≤ b0.5 · ae elements in fa with size of a to flip down and make |∑i ∆Ŵ`m,n,i| ≤ 0.5. For example, if ∑i ∆W`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
∆Ŵ`m,n: = argmin ∆W`m,n,: (∑ i ∆W`m,n,i) 2⇒ |∑ i ∆Ŵ`m,n,i|= ∣∣∣k−|∑ i ∆W`m,n,i| ∣∣∣. (29)
For each kernel |∑i ∆W`m,n,i| ≥ 0, ∑i ∆Ŵ`m,n,i has the minimum value ∣∣∣k−|∑i ∆W`m,n,i|∣∣∣≤ 0.5. The
sufficiency of Eq. (10) has been proven:
∆Ŵ`m,: = argmin ∆W`m,n,: (∑ i ∆W`m,n,i) 2⇒∀∆Ŵ`m,n,:, |∑ i ∆Ŵ`m,n,i| ≤ rk = 0.5 (30)
When a = K,b = 0 and all perturbation = 0.5, original ∑i ∆W`m,n,i have the upper bound 0.5 ·K. Proof. If we flip k− 1 or k + 1 elements for n-th kernel, the ∑i ∆Ŵ`m,n,i can reduce to ∣∣∣k− 1−
|∑i ∆W`m,n,i| ∣∣∣ and ∣∣∣k+1−|∑i ∆W`m,n,i|∣∣∣, respectively. Obviously,∣∣∣k−1−|∑
i ∆W`m,n,i| ∣∣∣= ∣∣∣b|∑ i ∆W`m,n,i|e−1−|∑ i ∆W`m,n,i| ∣∣∣> 0.5, (31)∣∣∣k+1−|∑
i ∆W`m,n,i| ∣∣∣= ∣∣∣b|∑ i ∆W`m,n,i|e+1−|∑ i ∆W`m,n,i| ∣∣∣> 0.5. (32)
With other numbers 6= k, we can also draw the same conclusions. Therefore, when rk ≤ 0.5, there is only one value, i.e., the minimum value, with k flipped elements satisfy the Eq. (10). The necessity of Eq. (10) has been proven:
argmin ∆W`m,n,: (∑ i ∆W`m,n,i) 2⇔∀∆Ŵ`m,n,:, |∑ i ∆Ŵ`m,n,i| ≤ rk = 0.5 (33)
Similarly, we can extend all conclusions to SQuant-C.
For SQuant, we only consider the flipping operation in one quantization step and select the elements whose sign is the same as ∑i ∆W`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. (8). We explain that in the next section.
B.2 PROOF OF TOK-k PERTURBATION ALGORITHM
Proof. We will prove the SQuant-E&K will lead to the top-k algorithm. We have the composition SQuant-E and SQuant-K optimization objective for n-th kernel,
argmin ∆W`m,n,: ∑ i (∆W`m,n,i) 2 +(∑ i ∆W`m,n,i) 2, (34)
which is the first two items of Eq. (8). Without loss of generality, we assume e = ∑i ∆W`m,n,i > 0, then SQuant needs to flip k = bee elements with perturbation > 0 to transform ∑i ∆W`m,n,i to e− k and is still constant e− k regardless of which k elements are. Therefore, the k elements are only determined by the first item of Eq. (34), ∑i (∆W`m,n,i)2. We denote f as the index set of the k flipped elements and the original perturbation O = ∆W`m,n,: for n-th kernel. Therefore, O j > 0, j ∈ f. Substituting f and O in Eq. (34), we have the optimization objective for f after flipping k elements,
argmin f ∑ t (|Ot |)2 +∑ j (1−|O j|)2 +(e− k)2, t /∈ f, j ∈ f, O j > 0 (35)
=argmin f ∑ i (|Oi|)2−∑ j (|O j|)2 +∑ j (1−|O j|)2, j ∈ f, O j > 0 (36)
=argmin f ∑ j [(1−|O j|)2−|O j|2], j ∈ f, O j > 0 (37)
=argmin f ∑ j (1−2|O j|), j ∈ f, O j > 0 (38)
=argmax f ∑ j (|O j|), j ∈ f, O j > 0. (39)
Therefore, the Eq. (39) 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 4 based on the insight of top-k perturbation algorithm ( B.2).
Over SQuant First we define the situation of k > |e| as “Over SQuant” (line 6). For example, if we have a 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,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 e =+0.6, due to it has the largest element perturbation in the k fliped elements and the smallest element perturbation (|−0.3|< 0.5) after it flips back. It is vice versa for e < 0. Under SQuant For “Under SQuant” (line 9), we need to make the first un-flipped element as 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 kernel.
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 O(M ·2NK). Based on the SQuant approximation, the new optimization objective is to minimize CASE whose complexity is
Algorithm 4: Perturbation Update Algorithm. Input: Weight perturbation p; Output: Updated weight perturbation p;
1 def UpdatePerturbation(p): 2 e = ∑i pi// Accumulated perturbation (signed CASE). 3 p[e ·p < 0] = 0 // Disable Elements/kernels with different sign from e. 4 k = b|e|e // Flip k elements/kernels based on the CASE. 5 f = TopK(|p|, k).indices// Indices of k largest perturbation. 6 if k > |e| then // Over SQuant. 7 i = fk // The k-th (last) element of f. 8 v = pi // 0.5≤ |v|< 1.0 9 else // Under SQuant.
10 i = TopK(|p|, k+1).indices[k+1] // The (k+1)-th largest element of p. 11 v = pi // |v| ≤ 0.5 12 p = 0 // Disable all elements. 13 pi = v // The only flip element candidate of the kernel for SQuant-C. 14 return p
O(M ·2N) for SQuant-C, O(MN ·2K) for SQuant-K and O(MNK) for SQuant-E. SQuant is optimized to a top-k algorithm with a significant complexity reduction to O(n · log(k)) for each sub-problem. Our experiments show that after SQuant-K pre-optimization, SQuant-C only requires a tiny top-k number, such as k = 32, to satisfy all cases. For a 3×3 kernel with 9 elements, SQuant-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 O(MN ·9 ·2) for SQuant-K.

title: SQUANT: ON-THE-FLY DATA-FREE QUANTIZATION VIA DIAGONAL HESSIAN APPROXIMATION