Year: 2020

Abstract:
We analyze the effect of quantizing weights and activations of neural networks on their loss and derive a simple regularization scheme that improves robustness against post-training quantization. By training quantization-ready networks, our approach enables storing a single set of weights that can be quantized ondemand to different bit-widths as energy and memory requirements of the application change. Unlike quantization-aware training using the straight-through estimator that only targets a specific bit-width and requires access to training data and pipeline, our regularization-based method paves the way for “on the fly” posttraining quantization to various bit-widths. We show that by modeling quantization as a `∞-bounded perturbation, the first-order term in the loss expansion can be regularized using the `1-norm of gradients. We experimentally validate the effectiveness of our regularization scheme on different architectures on CIFAR-10 and ImageNet datasets.

heading: 1 INTRODUCTION
text: Deep neural networks excel across a variety of tasks, but their size and computational requirements often hinder their real-world deployment. The problem is more challenging for mobile phones, embedded systems, and IoT devices, where there are stringent requirements in terms of memory, compute, latency, and energy consumption. Quantization of parameters and activations is often used to reduce the energy and computational requirements of neural networks. Quantized neural networks allow for more speed and energy efficiency compared to floating-point models by using fixed-point arithmetic.
However, naive quantization of pre-trained models often results in severe accuracy degradation, especially when targeting bit-widths below eight (Krishnamoorthi, 2018). Performant quantized models can be obtained via quantization-aware training or fine-tuning, i.e., learning full-precision shadow weights for each weight matrix with backpropagation using the straight-through estimator (STE) (Bengio et al., 2013), or using other approximations (Louizos et al., 2018). Alternatively, there have been successful attempts to recover the lost model accuracy without requiring a training pipeline (Banner et al., 2018; Meller et al., 2019; Choukroun et al., 2019; Zhao et al., 2019) or representative data (Nagel et al., 2019).
But these methods are not without drawbacks. The shadow weights learned through quantizationaware fine-tuning often do not show robustness when quantized to bit-widths other than the one they were trained for (see Table 1). In practice, the training procedure has to be repeated for each quantization target. Furthermore, post-training recovery methods require intimate knowledge of the relevant architectures. While this may not be an issue for the developers training the model in the first ∗Work done during internship at Qualcomm AI Research †Qualcom AI Research is an initiative of Qualcomm Technologies, Inc.
place, it is a difficult step for middle parties that are interested in picking up models and deploying them to users down the line, e.g., as part of a mobile app. In such cases, one might be interested in automatically constraining the computational complexity of the network such that it conforms to specific battery consumption requirements, e.g. employ a 4-bit variant of the model when the battery is less than 20% but the full precision one when the battery is over 80%. Therefore, a model that can be quantized to a specific bit-width “on the fly” without worrying about quantization aware fine-tuning is highly desirable.
In this paper, we explore a novel route, substantially different from the methods described above. We start by investigating the theoretical properties of noise introduced by quantization and analyze it as a `∞-bounded perturbation. Using this analysis, we derive a straightforward regularization scheme to control the maximum first-order induced loss and learn networks that are inherently more robust against post-training quantization. We show that applying this regularization at the final stages of training, or as a fine-tuning step after training, improves post-training quantization across different bit-widths at the same time for commonly used neural network architectures.

heading: 2 FIRST-ORDER QUANTIZATION-ROBUST MODELS
text: In this section, we propose a regularization technique for robustness to quantization noise. We first propose an appropriate model for quantization noise. Then, we show how we can effectively control the first-order, i.e., the linear part of the output perturbation caused by quantization. When the linear approximation is adequate, our approach guarantees the robustness towards various quantization bit-widths simultaneously.
We use the following notation throughout the paper. The `p-norm of a vector x in Rn is denoted by ‖x‖p and defined as ‖x‖p := ( ∑n i=1 |xi|p)1/p for p ∈ [1,∞). At its limit we obtain the `∞-norm defined by ‖x‖∞ := maxi |xi|. The inner product of two vectors x and y is denoted by 〈x,y〉.
2.1 ROBUSTNESS ANALYSIS UNDER `p-BOUNDED ADDITIVE NOISE
The error introduced by rounding in the quantization operation can be modeled as a generic additive perturbation. Regardless of which bit-width is used, the quantization perturbation that is added to each value has bounded support, which is determined by the width of the quantization bins. In other words, the quantization noise vector of weights and activations in neural networks has entries that are bounded. Denote the quantization noise vector by ∆. If δ is the width of the quantization bin, the vector ∆ satisfies ‖∆‖∞ ≤ δ/2. Therefore we model the quantization noise as a perturbation bounded in the `∞-norm. A model robust to `∞-type perturbations would also be robust to quantization noise.
To characterize the effect of perturbations on the output of a function, we look at its tractable approximations. To start, consider the first-order Taylor-expansion of a real valued-function f(w+∆) around w: f(w + ∆) = f(w) + 〈∆,∇f(w)〉+R2, (1) where R2 refers to the higher-order residual error of the expansion. We set R2 aside for the moment and consider the output perturbation appearing in the first-order term 〈∆,∇f(w)〉. The maximum of the first-order term among all `∞-bounded perturbations ∆ is given by:
max ‖∆‖∞≤δ 〈∆,∇f(w)〉 = δ ‖∇f(w)‖1 . (2)
To prove this, consider the inner product of ∆ and an arbitrary vector x given by ∑n i=1 nixi. Since |ni| is assumed to be bounded by δ, each nixi is bounded by δ|xi|, which yields the result. The maximum in Equation 2 is obtained indeed by choosing ∆ = δ sign(∇f(w)). Equation 2 comes with a clear hint. We can guarantee that the first-order perturbation term is small if the `1-norm of the gradient is small. In this way, the first-order perturbation can be controlled efficiently for various values of δ, i.e. for various quantization bit-widths. In other words, an effective way for controlling the quantization robustness, up to first-order perturbations, is to control the `1-norm of the gradient. As we will shortly argue, this approach yields models with the best robustness.
This conclusion is based on worst-case analysis since it minimizes the upper bound of the first-order term, which is realized by the worst-case perturbation. Its advantage, however, lies in simultaneous control of the output perturbation for all δs and all input perturbations. In the context of quantization, this implies that the first-order robustness obtained in this way would hold regardless of the adopted quantization bit-width or quantization scheme.
The robustness obtained in this way would persist even if the perturbation is bounded in other `pnorms. This is because the set of `∞-bounded perturbations includes all other bounded perturbations, as for all p ∈ [1,∞), ‖x‖p ≤ δ implies ‖x‖∞ ≤ δ (see Figure 8) . The robustness to `∞-norm perturbations is, therefore, the most stringent one among other `p-norms, because a model should be robust to a broader set of perturbations. Controlling the `1-norm of the gradient guarantees robustness to `∞-perturbations and thereby to all other `p-bounded perturbations.
In what follows, we propose regularizing the `1-norm of the gradient to promote robustness to bounded norm perturbations and in particular bounded `∞-norm perturbations. These perturbations arise from quantization of weights and activations of neural networks.
2.2 ROBUSTNESS THROUGH REGULARIZATION OF THE `1-NORM OF THE GRADIENT
We focused on weight quantization in our discussions so far, but we can equally apply the same arguments for activation quantization. Although the activations are not directly learnable, their quantization acts as an additive `∞-bounded perturbation on their outputs. The gradient of these outputs is available. It therefore suffices to accumulate all gradients along the way to form a large vector for regularization.
Suppose that the loss function for a deep neural network is given byLCE(W,Y;x) where W denotes the set of all weights, Y denotes the set of outputs of each activation and x the input. We control the `1-norm of the gradient by adding the regularization term∑
Wl∈W ‖∇WlLCE(W,Y;x)‖1 + ∑ yl∈Y ‖∇ylLCE(W,Y;x)‖1
to the loss, yielding an optimization target L(W;x) = LCE(W,Y;x) + λw ∑
Wl,∈W ‖∇WlLCE(W,Y;x)‖1 + λy ∑ yl∈Y ‖∇ylLCE(W,Y;x)‖1 ,
(3) where λw and λy are weighing hyper-parameters.
2.3 ALTERNATIVES TO THE `1-REGULARIZATION
The equivalence of norms in finite-dimensional normed spaces implies that all norms are within a constant factor of one another. Therefore, one might suggest regularizing any norm to control other norms. Indeed some works attempted to promote robustness to quantization noise by controlling the `2-norm of the gradient (Hoffman et al., 2019). However, an argument related to the curse of dimensionality can show why this approach will not work. The equivalence of norms for `1 and `2 in n-dimensional space is stated by the inequality:
‖x‖2 ≤ ‖x‖1 ≤ √ n ‖x‖2 .
Although the `2-norm bounds the `1-norm from above, it is vacuous if it does not scale with 1/ √ n. Imposing such a scaling is demanding when n, which is the number of trainable parameters, is large. Figure 1 shows that there is a large discrepancy between these norms in a conventionally trained network, and therefore small `2-norm does not adequately control the `1-norm. A very similar argument can be provided from a theoretical perspective (see the supplementary materials).
To guarantee robustness, the `2-norm of the gradient, therefore, should be pushed as small as Θ(1/ √ n). We experimentally show in Section 4 that this is a difficult task. We therefore directly control the `1-norm in this paper. Note that small `1-norm is guaranteed to control the first orderperturbation for all types of quantization noise with bounded support. This includes symmetric and asymmetric quantization schemes.
Another concern is related to the consistency of the first-order analysis. We neglected the residual term R2 in the expansion. Figure 3 compares the induced loss after perturbation with its first-order approximation. The approximation shows a strong correlation with the induced loss. We will see in the experiments that the quantization robustness can be boosted by merely controlling the first-order term. Nonetheless, a higher-order perturbation analysis can probably provide better approximations. Consider the second-order perturbation analysis:
f(w + ∆) = f(w) + 〈∆,∇f(w)〉+ 1 2 ∆T∇2f(w)∆ +R3.
Computing the worst-case second-order term for `∞-bounded perturbations is hard. Even for convex functions where ∇2f(w) is positive semi-definite, the problem of computing worst-case secondorder perturbation is related to the mixed matrix-norm computation, which is known to be NPhard. There is no polynomial-time algorithm that approximates this norm to some fixed relative precision (Hendrickx & Olshevsky, 2010). For more discussions, see the supplementary materials. It is unclear how this norm should be controlled via regularization.

heading: 3 RELATED WORK
text: A closely related line of work to ours is the analysis of the robustness of the predictions made by neural networks subject to an adversarial perturbation in their input. Quantization can be seen as a similar scenario where non-adversarial perturbations are applied to weights and activations instead. Cisse et al. (2017) proposed a method for reducing the network’s sensitivity to small perturbations
by carefully controlling its global Lipschitz. The Lipschitz constant of a linear layer is equal to the spectral norm of its weight matrix, i.e., its largest singular value. The authors proposed regularizing weight matrices in each layer to be close to orthogonal: ∑ Wl∈W ∥∥WTl Wl − I∥∥2. All singular values of orthogonal matrices are one; therefore, the operator does not amplify perturbation (and input) in any direction. Lin et al. (2019) studied the effect of this regularization in the context of quantized networks. The authors demonstrate the extra vulnerability of quantized models to adversarial attacks and show how this regularization, dubbed “Defensive Quantization”, improves the robustness of quantized networks. While the focus of Lin et al. (2019) is on improving the adversarial robustness, the authors report limited results showing accuracy improvements of posttraining quantization.
The idea of regularizing the norm of the gradients has been proposed before (Gulrajani et al., 2017) in the context of GANs, as another way to enforce Lipschitz continuity. A differentiable function is 1-Lipschitz if and only if it has gradients with `2-norm of at most 1 everywhere, hence the authors penalize the `2-norm of the gradient of the critic with respect to its input. This approach has a major advantage over the methods mentioned above. Using weight regularization is only well-defined for 2D weight matrices such as in fully-connected layers. The penalty term is often approximated for convolutional layers by reshaping the weight kernels into 2D matrices. Sedghi et al. (2018) showed that the singular values found in this weight could be very different from the actual operator norm of the convolution. Some operators, such as nonlinearities, are also ignored. Regularizing Lipschitz constant through gradients does not suffer from these shortcomings, and the operator-norm is regularized directly. Guo et al. (2018) demonstrated that there exists an intrinsic relationship between sparsity in DNNs and their robustness against `∞ and `2 attacks. For a binary linear classifier, the authors showed that they could control the `∞ robustness, and its relationship with sparsity, by regularizing the `1 norm of the weight tensors. In the case of a linear classifier, this objective is, in fact, equivalent to our proposed regularization penalty.
Finally, another line of work related to ours revolves around quantization-aware training. This can, in general, be realized in two ways: 1) regularization and 2) mimicking the quantization procedure during the forward pass of the model. In the first case, we have methods (Yin et al., 2018; Achterhold et al., 2018) where there are auxiliary terms introduced in the objective function such that the optimized weights are encouraged to be near, under some metric, to the quantization grid points, thus alleviating quantization noise. In the second case, we have methods that rely on either the STE (Courbariaux et al., 2015; Rastegari et al., 2016; Jacob et al., 2018), stochastic rounding (Gupta et al., 2015; Gysel, 2016), or surrogate objectives and gradients (Louizos et al., 2018; Shayer et al., 2017). While all of the methods above have been effective, they still suffer from a major limitation; they target one-specific bit-width. In this way, they are not appropriate for use-cases where we want to be able to choose the bit-width “on the fly”.

heading: 4 EXPERIMENTS
text: In this section we experimentally validate the effectiveness of our regularization method on improving post-training quantization. We use the well-known classification tasks of CIFAR-10 with ResNet-18 (He et al., 2016) and VGG-like (Simonyan & Zisserman, 2014) and of ImageNet with ResNet-18. We compare our results for various bit-widths against (1) unregularized baseline networks (2) Lipschitz regularization methods (Lin et al., 2019; Gulrajani et al., 2017) and (3) quantization-aware fine-tuned models. Note that Gulrajani et al. (2017) control the Lipschitz constant under an `2 metric by explicitly regularizing the `2-norm of the gradient, while Lin et al. (2019) essentially control an upper bound on the `2-norm of the gradient. Comparing against these baselines thus gives insight into how our method of regularizing the `1-norm of the gradient compares against regularization of the `2-norm of the gradient.

heading: 4.1 EXPERIMENTAL SETUP
text: Implementation and complexity Adding the regularization penalty from Equation 3 to the training objective requires higher-order gradients. This feature is available in the latest versions of frameworks such as Tensorflow and PyTorch (of which we have used the latter for all our experiments). Computing∇w‖∇wL‖1 using automatic differentiation requires O(2×C×E) extra computations, where E is the number of elementary operations in the original forward computation graph, and C
is a fixed constant (Baydin et al., 2018). This can be seen from the fact that ‖∇wL‖1 is a function R|w| → R, where |w| denotes the number of weights and the computation of the gradient w.r.t. the loss contains E elementary operations, as many as the forward pass. In practice, enabling regularization increased time-per-epoch time on CIFAR10 from 14 seconds to 1:19 minutes for VGG, and from 24 seconds to 3:29 minutes for ResNet-18. On ImageNet epoch-time increased from 33:20 minutes to 4:45 hours for ResNet-18. The training was performed on a single NVIDIA RTX 2080 Ti GPU.
However, in our experiments we observed that it is not necessary to enable regularization from the beginning, as the `1-norm of the gradients decreases naturally up to a certain point as the training progresses (See Appendix D for more details). We therefore only enable regularization in the last 15 epochs of training or as an additional fine-tuning phase. We experimented with tuning λw and λy in Equation 3 separately but found no benefit. We therefore set λw = λy = λ for the remainder of this section.
We use a grid-search to find the best setting for λ. Our search criteria is ensuring that the performance of the unquantized model is not degraded. In order to choose a sensible range of values we first track the regularization and cross-entropy loss terms and then choose a range of λ that ensures their ratios are in the same order of magnitude. We do not perform any quantization for validation purposes during the training.
Quantization details We use uniform symmetric quantization (Jacob et al., 2018; Krishnamoorthi, 2018) in all our experiments unless explicitly specified otherwise. For the CIFAR 10 experiments we fix the activation bit-widths to 4 bits and then vary the weight bits from 8 to 4. For the Imagenet experiments we use the same bit-width for both weights and activations. For the quantization-aware fine-tuning experiments we employ the STE on a fixed (symmetric) quantization grid. In all these experiments we perform a hyperparameter search over learning rates for each of the quantization bit-widths and use a fixed weight decay of 1e− 4. For our experiments with defensive quantization (Lin et al., 2019) we perform a hyperparameter search over the scaling parameters of the regularizer and the learning rate. We limit the search over the scaling parameters to those mentioned in (Lin et al., 2019) and do not use weight decay. When applying post-training quantization we set the activation ranges using the batch normalization parameters as described in (Nagel et al., 2019).
When a model is fine-tuned to a target bit-width and evaluated on a higher bit-width, we can trivially represent the original quantized weights and activations by ignoring the higher-order bits, or quantize using the higher bit-width. As using the higher bit-width to quantize shadow weights and activations introduces noise to the model and might yield lower results, we try both approaches and only report a result if quantization using the higher bit-width gives better results.

heading: 4.2 EFFECTS OF REGULARIZATION
text: In order to get a better understanding of our proposed regularizer, we first adopt the visualization method from Hoffman et al. (2019) and illustrate the effects that the quantization in general, and our method in particular, have on the trained classifier’s decision boundaries. The result can be seen in Figure 5, where we empirically observe that the regularized networks “expands” its decision cells.
Secondly, we investigate in Figure 1 the `1- and `2-norms of the gradients for all CIFAR-10 test batches on the VGG-like model. We can observe that while the `2-norms of the gradient are small in the unregularized model, the `1-norms are orders of magnitude larger. Consequently, when finetuning the same model with our method, we see a strong decrease of the `1-norm.
Finally, we investigate how the predictive distribution of the floating point model, p(y|x), changes when we quantize either an unregularized baseline or a model regularized with our method, thus obtaining q(y|x). We measure this discrepancy using the KL-divergence of the original predictive when using the predictive distribution of the quantized model, i.e. DKL(p(y|x)||q(y|x)), averaged over each test batch. Since our method improves robustness of the loss gradient against small perturbations, we would expect the per-class probabilities to be more robust to perturbations as well, and thus more stable under quantization noise. The result can be seen in Figure 2, where we indeed observe that the gap is smaller when quantizing our regularized model.

heading: 4.3 CIFAR-10 & IMAGENET RESULTS
text: The classification results from our CIFAR-10 experiments for the VGG-like and ResNet18 networks are presented in Table 1, whereas the result from our Imagenet experiments for the ResNet18 network can be found in Table 2. Both tables include all results relevant to the experiment, including results on our method, Defensive Quantization regularization, L2 gradient regularization and finetuning using the STE.
Comparison to “Defensive Quantization” As explained in Section 3, Defensive Quantization (Lin et al., 2019) aims to regularize each layer’s Lipschitz constant to be close to 1. Since the
regularization approach taken by the authors is similar to our method, and the authors suggest that their method can be applied as a regularization for quantization robustness, we compare their method to ours. As the experiments from the original paper differ methodologically from ours in that we quantize both weights and activations, all results on defensive quantization reported in this paper are produced by us. We were able to show improved quantization results using defensive quantization for CIFAR-10 on VGG-like, but not on any of the experiments on ResNet18. We attribute this behavior to too stringent regularization in their approach: the authors regularize all singular values of their (reshaped) convolutional weight tensors to be close to one, using a regularization term that is essentially a fourth power regularization of the singular values of the weight tensors (see Appendix C). This regularization likely inhibits optimization.
Comparison to explicit `2-norm gradient regularization We consider the `2 regularization of the gradient, as proposed by Gulrajani et al. (2017), as a generalization of the DQ regularization. Such regularization has two key benefits over DQ: 1) we can regularize the singular values without reshaping the convolutional kernels and 2) we impose a less stringent constraint as we avoid enforcing all singular values to be close to one. By observing the results at Table 1 and 2, we see that the `2 regularization indeed improves upon DQ. Nevertheless, it provides worse results compared to our `1 regularization, an effect we can explain by the analysis of Section 2.
Comparison to quantization-aware fine-tuning While in general we cannot expect our method to outperform models to which quantization-aware fine-tuning is applied on their target bit-widths, as in this case the model can adapt to that specific quantization noise, we do see that our model performs on par or better when comparing to bit-widths lower than the target bit-width. This is in line with our expectations: the quantization-aware fine-tuned models are only trained to be robust to a specific noise distribution. However, our method ensures first-order robustness regardless of bit-
width or quantization scheme, as explained in Section 2. The only exception is the 4 bit results on ImageNet. We hypothesize that this is caused by the fact that we tune the regularization strength λ to the highest value that does not hurt full-precision results. While stronger regularization would harm full-precision performance, it would also most likely boost 4 bit results, due to imposing robustness to a larger magnitude, i.e. δ, of quantization noise. Table 1 includes results for a higher value of δ that is in line with this analysis.

heading: 5 CONCLUSION
text: In this work, we analyzed the effects of the quantization noise on the loss function of neural networks. By modelling quantization as an `∞-bounded perturbation, we showed how we can control the first-order term of the Taylor expansion of the loss by a straightforward regularizer that encourages the `1-norm of the gradients to be small. We empirically confirmed its effectiveness, demonstrating that standard post-training quantization to such regularized networks can maintain good performance under a variety of settings for the bit-width of the weights and activations. As a result, our method paves the way towards quantizing floating-point models “on the fly” according to bit-widths that are appropriate for the resources currently available.

heading: ACKNOWLEDGMENTS
text: We would like to thank Markus Nagel, Rana Ali Amjad, Matthias Reisser, and Jakub Tomczak for their helpful discussions and valuable feedback.

heading: A ROBUSTNESS ANALYSIS FOR QUANTIZATION PERTURBATIONS
text: In this section, we address two questions in more details, first regarding regularization of the `2-norm of gradient and second regarding non-uniform quantization schemes.
We argued above that regularizing the `2-norm of gradient cannot achieve the same level of robustness as regularization of the `1-norm of gradient. We provide here another, more theoretical, argument. The following inequality shows how the `2-norm of gradient controls the first-order perturbation: 〈∆,∇f(w)〉 ≤ ‖∆‖2 ‖∇f(w)‖2 . This is a simple Cauchy-Shwartz inequality. Therefore, if the `2-norm of the gradient is inversely proportional to the power of the perturbation, the first-order term is adequately controlled. However, using a theoretical argument, we show that the power of the `∞-bounded perturbation can blow up with the dimension as a vector ∆ in Rn with ‖∆‖∞ = δ can reach an `2-norm of approximately√ nδ. In other words, the length of the quantization noise behaves with high probability as Θ( √ n), which implies that the the `2-norm of the gradient should be as small as Θ(1/ √ n).
We show that this can indeed occur with high probability for any random quantization noise with the bounded support. Note that for symmetric uniform quantization schemes, quantization noise can be approximated well by a uniform distribution over [−δ/2, δ/2] where δ is the width of the quantization bin. See Figures 6 for the empirical distribution of quantization noise on the weights of a trained network. Our argument, however, works for any distribution supported over [−δ/2, δ/2], and, therefore, it includes asymmetric quantization schemes over a uniform quantization bin.
Consider a vector x = (x1, . . . , xn)T ∈ Rn with entries xi randomly and independently drawn from a distribution supported on [−δ/2, δ/2]. We would like to show that ‖x‖22 is well concentrated around its expected values. To do that we are going to write down the above norm as the sum of independent zero-mean random variables. See that:
E ( ‖x‖22 ) = E ( n∑ i=1 x2i ) = nE ( x21 ) = nδ2 12 .
Besides, note that x2i ∈ [0, δ2/4]. Therefore x2i − δ2/12 is a zero-mean random variable that lies in the interval [−δ2/12, δ2/6]. We can now use Hoeffding’s inequality. To be self-contained, we include the theorem below. Theorem A.1 (Hoeffding’s inequality, (Hoeffding, 1963)). Let X1, . . . , Xn be a sequence of independent zero-mean random variables such that Xi is almost surely supported on [ai, bi] for
i ∈ {1, . . . , n}. Then, for all t > 0, it holds that
P ( n∑ i=1 Xi ≥ t ) ≤ exp ( − 2t 2∑n i=1(bi − ai)2 ) (4)
P (∣∣∣∣∣ n∑ i=1 Xi ∣∣∣∣∣ ≥ t ) ≤ 2 exp ( − t 2∑n i=1(bi − ai)2 ) (5)
Applying Theorem A.1 to our setting, we obtain: P (∣∣∣‖x‖22 − nδ2/12∣∣∣ ≥ t) ≤ 2 exp(− 2t2n(δ2/4)2 ) .
So with probability 1− , we have:∣∣∣‖x‖22 − nδ2/12∣∣∣ ≤ (nδ432 log(2/ ) )1/2 .
Therefore, if the quantization noise ∆ has entries randomly drawn from a distribution over [−δ/2, δ/2], then with probability 1 − , the squared `2-norm of ∆, i.e., ‖∆‖22, lies in the interval[ nδ2
12 − √ nδ4 32 log(2/ ), nδ2 12 + √ nδ4 32 log(2/ ) ] . In other words, the length of the vector behaves with high probability as Θ( √ n). This result holds for any quantization noise with bounded support.
If the quantization bins are non-uniformly chosen, and if the weights can take arbitrarily large values, the quantization noise is no-longer bounded in general. As long as the quantization noise has a Gaussian tail, i.e., it is a subgaussian random variable, one can use Hoeffding’s inequality for subgaussian random variables to show a similar concentration result as above. The power of the perturbation will, therefore, behave with Θ( √ n), and the `2-norm of the gradient cannot effectively control the gradient. Note that nonuniform quantization schemes are not commonly used for hardware implementations, hence, our focus on uniform cases. Besides, the validity of this assumption about nonuniform quantization noise requires further investigation, which is relegated to our future works.

heading: B SECOND-ORDER PERTURBATION ANALYSIS
text: We start by writing the approximation of f(·) up to the second-order term:
f(w + ∆) = f(w) + 〈∆,∇f(w)〉+ 1 2 ∆T∇2f(w)∆ +R3.
The worst-case second-order term under `∞-bounded perturbations is given by
max ‖n‖∞≤δ
∆T∇2f(w)∆.
The above value is difficult to quantify for general case. We demonstrate this difficulty by considering some special cases.
Let’s start with convex functions, for which the Hessian ∇2f(w) is positive semi-definite. In this case, the Hessian matrix admits a square root, and the second-order term can be written as:
∆T∇2f(w)∆ = ∆T (∇2f(w))1/2(∇2f(w))1/2∆ = ∥∥∥(∇2f(w))1/2∆∥∥∥2
2 .
Therefore the worst-case analysis of the second-term amounts to
max ‖n‖∞≤δ ∆T∇2f(w)∆ = max ‖n‖∞≤δ ∥∥∥(∇2f(w))1/2∆∥∥∥2 2 .
The last term is the mixed∞→ 2-norm of (∇2f(w))1/2. As a reminder, the p→ q-matrix norm is defined as
‖A‖p→q := max‖x‖p≤1 ‖A‖q = max‖x‖p≤1
‖y‖q∗≤1
〈y,Ax〉 =: ∥∥AT∥∥
q∗→p∗
where p∗, q∗ denote the dual norms of p and q, i.e. satisfying 1/p+ 1/p∗ = 1/q + 1/q∗ = 1.
The worst case second-order perturbation is given by:
max ‖n‖∞≤δ
∆T∇2f(w)∆ = δ2 ∥∥∥(∇2f(w))1/2∥∥∥2
∞→2 .
Unfortunately the ∞ → 2-norm is known to be NP-hard ((Hendrickx & Olshevsky, 2010); see Bhattiprolu et al. (2018) for a more recent study). As a matter of fact, if f(·) is positive semidefinite, and hence the function is convex, the problem above corresponds to maximization of convex functions, which is difficult as well.
For a general Hessian, the problem is still difficult to solve. First note that:
max ‖n‖∞≤δ ∆T∇2f(w)∆ = max ‖n‖∞≤δ
Tr ( ∇2f(w)∆∆T ) .
We can therefore replace ∆∆T with a positive semi-defintite matrix of rank 1 denoted by N . The worst case second-order perturbation can be obtained by solving the following problem:
max N∈Rn×n
Tr ( ∇2f(w)N ) (6)
subject to N 0 Nii ≤ δ2 for i ∈ {1, . . . , n} rank(N) = 1.
The last constraint, namely the rank constraint, is a discrete constraint. The optimization problem above is therefore NP-hard to solve. To sum up, the worst case second-order perturbation cannot be efficiently computed, which poses difficulty for controlling the second-order robustness.
There are, however, approximations available in the literature. A common approximation, which is widely known for the Max-Cut and community detection problems, consists of dropping the rankconstraint from the above optimization problem to get the following semi-definite program:
max N∈Rn×n
Tr ( ∇2f(w)N ) (7)
subject to N 0 Nii ≤ δ2 for i ∈ {1, . . . , n}
Unfortunately this approximation, apart from being costly to solve for large n, does not provide a regularization parameter that can be included in the training of the model.
It is not clear how we can control the second-order term through a tractable term.

heading: C DEFENSIVE QUANTIZATION IMPOSES A 4TH POWER CONSTRAINT ON
text: SINGULAR VALUES
From basic linear algebra we have that ‖W ‖22 = Tr(W TW ) = ∑ i σ2i (W ),
i.e., the Frobenius norm is equal to sum of the squared singular values of W . From this we can conclude that the regularization term ‖W TW − I‖22 introduced by Lin et al. (2019) thus equals
‖W TW − I‖22 = ∑ i σ2i (W TW − I) = ∑ i ∣∣σ2i (W )− 1∣∣2 , and therefore imposes a 4th power regularization term on the singular values of W . A softer regularization can be introduced by regularizing Tr(W TW − I) instead.

heading: D GRADIENT-PENALTY PROGRESSION IN NON-REGULARIZED NETWORKS
text: Optimizing our regularization penalty requires computing gradients of the gradients. While this is easily done by double-backpropagation in modern software frameworks it introduces overhead (as discussed in Section 4.1) and makes training slower. However, as the training progresses, the gradients in unregularized networks tend to become smaller as well, which is inline with our regularization objective. It is therefore not necessary to apply the regularization from the beginning of training. In Figure 7 we show examples of how the regularization objective naturally decreases during training. We also show how turning the regularization on in the final epochs where the regularization objective is oscillating can push the loss further down towards zero.

heading: E `∞-BOUNDED PERTURBATIONS INCLUDE OTHER BOUNDED-NORM PERTURBATIONS
text: Figure 8 show that the `∞-bounded perturbations include all other bounded-norm perturbations.

Review summaries:
the authors propose a regularization scheme that is applied during regular training to ease the pose-training quantization of a network. Modeling the quantization noise as an additive perturbation bounded in \ell_\inf norm, they bound from above the first-order term of the perturbations applied to the network by the \ell_1 norm of the gradients. Their claims are also supported by experiments and qualitative illustrations.