Formalizing Generalization and Robustness of Neural Networks to Weight Perturbations
Authors: Yu-Lin Tsai
Chia-Yi Hsu
Chia-Mu Yu
Pin-Yu Chen
Venue:  (2021)
Keywords: Generalization
Robustness
Neural Network
Weight Perturbation
Rademacher complexity

Abstract: Studying the sensitivity of weight perturbation in neural networks and its impacts on model performance, including generalization and robustness, is an active research topic due to its implications on a wide range of machine learning tasks such as model compression, generalization gap assessment, and adversarial attacks. In this paper, we provide the first formal analysis for feed-forward neural networks with non-negative monotone activation functions against norm-bounded weight perturbations, in terms of the robustness in pairwise class margin functions and the Rademacher complexity for generalization. We further design a new theory-driven loss function for training generalizable and robust neural networks against weight perturbations. Empirical experiments are conducted to validate our theoretical analysis. Our results offer fundamental insights for characterizing the generalization and robustness of neural networks against weight perturbations.

Under review as a conference paper at ICLR 2021
FORMALIZING GENERALIZATION AND ROBUSTNESS OF NEURAL NETWORKS TO WEIGHT PERTURBATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Studying the sensitivity of weight perturbation in neural networks and its impacts on model performance, including generalization and robustness, is an active re- search topic due to its implications a wide range of machine learning tasks such as model compression, generalization gap assessment, and adversarial at- tacks. In this paper, we provide the first formal analysis for feed-forward neural networks with non-negative monotone activation functions against norm- nern-buuded weight perturbations, in terms of the robustness in pairwise class margin fune- tions and the Rademacher complexity for generalization. We further design a new theory-driven loss function for training generalizable and robust neural networks against weight perturbations. Empirical experiments are conducted to validate our theoretical analysis. Our results offer fundamental insights for characterizing the generalization and robustness of neural networks against weight perturbations.
INTRODUCTION
Neural network is currently the statc-of-the-at machine learning model in a variety of tasks, includ- ing computer vision, natural language processing, and game-playing, name few. In particular, feed-forward neural networks consists of layers of trainable model weights and activation functions with the premise of learning informative data representations and the complex mapping between data samples and the associated labels. Albeit attaining superior performance, the need for studying the sensitivity of neural networks to weight perturbations is also intensifying owing several practical motivations. For instance, in model compression, the robustness to weight quantification is crucial for reducing memory storage while retaining model performance (Hubara et al.) 2017 Weng al.) 2020). The notion of weight perturbation sensitivity is also used as a metric to evaluate the general- ization gap at local minima (Keskar et al., 2017 Neyshabur et al.) (017). In adversarial robustness vulnerability for fault injection and causing
and security, weight sensitivity can be leveraged erroneous prediction (Liu et al. 2017 Zhao et al. 2019). However, while weight sensitivity plays an important role in many machine learning tasks and problem setups, theoretical characterization of its impacts on generalization and robustness of neural networks remains elusive.
This paper bridges this gap by developing novel theoretical framework for understanding the gen- eralization gap (through Rademacher complexity) and the robustness (through classification margin) of neural networks against norm-hounded weight perturbations. Specifically, consider the multi- class classification problem setup and multi-layer feed-forward neural networks with non-negative monotonic activation functions. Our analysis offers fundamental insights into how weight pertur- bation affects the generalization gap and the pairwise class margin. To the best of our knowledge, this study the first work that provides a comprehensive theoretical characterization of the interplay between weight perturbation, robustness in classification margin, and generalization gap. Moreover, based on our analysis, we propose a theory-driven loss function for training generalizable and ro- bust neural networks against norm-bounded weight perturbations. We validate its effectiveness via empirical experiments. We summarize our main contributions as follows.
We study the robustness (worst-case bound) of the pairwise class margin function against weight perturbations in neural networks, including the analysis of single-layer (Theorem []. all-layer (Theorem 2). and selected-layer (Theorem 3) weight perturbations.
We characterize the generalization behavior of robust surrogate loss for neural networks under weight perturbations (Section 3.4) through Rademacher complexity (Theorem

---

Under review as a conference paper at ICLR 2021
We propose theory-driven loss design for training generalizable and robust neural networks (Section 3.5) The empirical results in Section validate our theoretical analysis and demonstrate the effectiveness of improving generalization and robustness against weight perturbations.
2 RELATED WORKS
In model compression, the robustness to weight quantization is critical to reducing memory size and accesses for wwwrrccision inference and training (Hubara et al., 2017). [Weng et al. (2020) showed that incorporating weight perturbation sensitivity into training can better retain model per- formance (standard accuracy) after quantization. For studying the generalization of neural networks, Keskar et al. (2017) proposed a metric called sharpness (or weight sensitivity) by perturbing the learned model weights around the local minima of the loss landscape for generalization assess- ment while An (196) introduced weight noise into the training process and concluded that random noise training improves the overall generalization. Neyshabur et al. (2017) made connection be- tween sharpness and PAC-Bayes theory and found that some combination of sharpness and norms on the model weights may capture the generalization behavior of neural networks. Additionally, Bartlett et al. (017) discovered normalized margin measure to be useful towards quantifying gener- alization property and bound was therefore constructed to give quantitative description on the generalization gap. Moreover, Golowich et al. (2019) incorporated additional assumptions to offer tighter and size-independent bounds from the setting of (Neyshabur al. 2015) and (Bartlett al.) 2017) respectively. Despite development of various generalization bounds, empirical observations in (Nagarajan & Kolter 2019) showed that once the size of the training dataset grows, generalization bounds proposed in (Neyshabur et al. 2017) and (Bartlett et al. (2017) will enlarge thus become vac- uous. Discussions on the relation between (Nagarajan & Kolter 2019) and our works can found at Appendix non-vacuous. On the other hand, Barron & Klusowski (2018) and Theisen et al. (2019) applied several techniques in tandem with probabilistic method named path sampling to construct rep- resenting set of given neural networks for approximating and studying the generalization property. Another approach considered by Petzkk et al. (2020) consists of segmenting the neural networks into two functions, predictor and feature selection respectively where two measures (representa- tiveness and feature robustness) concerning these aforementioned functions were later combined to offer a meaningful generalization bound. However, these works only focused on the generalization behavior of the local minima and did not consider the generalization and robustness under weight perturbations. |Weng et al. (2020) proposed a certification method for weight perturbation retaining consistent model prediction. While the certification bound can be used to train robust models with interval bound propagation (Gowal et al.) 2019). it requires additional optimization subroutine and computation costs when comparing to our approach. Moreover, the convoluted nature of certification bound complicates the analysis when studying generalization, which is one of our main objectives. In adversarial robustness, fault-injection attacks are known to inject errors to model weights at the inference phase and causing erroneous model prediction (Liu et al. 2017 Zhao et al. 2019), which can be realized at the hardware level by changing or flipping the logic values of the corresponding bits and thus modifying the model parameters saved in memory (Barenghi et al. 2012] Van Der Veen et al. 2016). ZZho et al. (020)) proposed to use the mode connectivity of the model parameters in the loss landscape for mitigating such reiight-ertuurbation-be
F. where we show that in our studied setting the associated generalization bounds are
adversarial attacks.
Although, to the best of our knowledge, theoretical characterization of generalization and robustness for neural networks against weight perturbations remains elusive, recent works have studied these properties under another scenario - the impul perturbations. Both empirical and theoretical evidence have been given the existence of a fundamental trade-off between generalization and robustness against norm-bounded input perturbations (Xu & Mannor 2012 [Su et al.) (0188) ZZhan et al.] 2019]] Tsipras et al., 2019). The adversarial training proposed (Madry et al. 2018) a popular training strategy for training robust models against input perturbations, where a min-max optimization prin- ciple is used to minimize the worst-case input perturbations of a data batch during model parameter updates. For adversarial training with input perturbations, Wang et al. (2019) proved its convergence and Yin et al. (2019) derived bounds on its Rademacher complexity for generalization. Different from the case of input perturbation. subject to weight perturbation is not straightforward, as the minimization and maximization steps both taken on the model parameters. In this paper, we disentangle the min-max formulation for
note that min-max optimization
neural network training
2

---

Under review as a conference paper at ICLR 2021
weight perturbation by developing bounds for the inner maximization step and provide quantifiable metrics for training generalization and robust neural networks against weight perturbations.
MAIN RESULTS
We provide overview of the presentation flow for our main results as follows. First, we introduce the mathematical notations and preliminary information in Section 3.1 In Section 3.2 we establish our weight perturbation analysis on a simplified case of single-layer perturbation. We then use the single-layer analysis as building block and extend the results to the multi-layer perturbation setting in Section 3.3] In Section (34] we define the framework of robust training with surrogate loss and study the generalization property using Rademacher complexity. Finally, we propose theory-driven loss toward training robust and generalizable neural networks in Section 3.5
3.1 NOTATION AND PRELIMINARIES
Notation We start by introducing the mathematical notations used in this paper. We define the For any two non-empty sets A, B, F A-+B denotes the set of all functions from A to B. We mark the indicator function of an event E as 1(E), which is 1 if E holds and 0 otherwise. We use sgm(-) to denote element-wise sign function that outputs 1 when input is nonnegative and -I otherwise. Boldface lowercase letters used denote vectors (e.g., x), and the i-th element is denoted as [x]s. Matrices are presented as boldface uppercase letters, say W. Given a matrix W E Rkxd we write its i-th row, j-th column and (i.j) element as W..,. 5. and Wa respectively. Moreover, we write its transpose matrix as (W)". The matrix (p, q) norm is defined || | p.o : || I1 .... a.l for any p. 9 1. For convenience, we have [ = || and write the spectral norm and Frobenius norm as || and | respectively. We mark one matrix norm commonly used in this paper the matrix (1, oo) norm.
set [L] == (1.,..... L).
With matrix W, we express its matrix (o) norm as Wil...o. which is defined as || maxy [Walll, and ||W*|l,,0 = max; | We use IBW (e) to express element-wise foc.
norm ball of matrix W within radius e, i.., BW (E) [W] [
We,l S e, Vi [k].] E [d]].
Preliminaries In order to formally explain our thcoretical results, we introduce the considered learning problem, neural network model and complexity definition. Let X' and Y be the feature space and label space, respectively. We place the assumption that all data are drawn from an unknown distribution D over X' x )/ and each data point is generated under i.i.d condition. In this paper, we specifically consider the feature space X' as a subset of dddiimensional Euclidean space, i.e., X C CRd We denote the symbol F C F Fx to be the hypothesis class which use to make predictions. Furthermore, we consider a loss function é X' x y - [] and compose it with the hypothesis class make function family written as lf == {(x. y) - {(f(x), f E F}. The optimal solution of this learning problem is a function f E F such that it minimizes the population risk R(f) E((.y)) (x)) y/]. However, since the underlying data distribution generally unknown, one typically aims at reducing the empirical risk evaluated by set of training data {(x, })) which can be expressed as RJ( = - >m (xx(xx), w:). The generalization error is the gap between population and empirical risk, which could serve an indicator of model's performance under unseen data from identical distribution D.
To study the generalization error, one would explore the learning capacity of a certain hypothesis class. In this paper, we adopt the notion of Rademacher complexity as a measure of learning capac-
ity, which is widely used in statistical machine learning literature (Mohri et al. 2018). The empirical Rademacher complexity of a function class F given a set of samples
[xx, 91) 1=
Rs((r) = [sup
Σ (x:)((ss) v:)]
(I)
JEF
where [u:),2_ is set of i.i.d Rademacher random variables with P(u; - P(,
The empirical Rademacher complexity measures on average how well a function class F correlates with random noises on dataset S. Thus, a richer or more complex family could better correlate with random noise on average. With Rademacher complexity as a toolkit, one can develop the follow- ing relationship between generalization error and complexity measure. Specifically, it is shown in
3

---

Under review as a conference paper at ICLR 2021
Mohri al. 2018) that given set of training samples S and assumee that the range of loss function
(x))) U. Then for any (0,1), with at least probability 1 - å we have V.f
log 2
R(O (a) + 2Rs +
(2)
2m
Note that when the Rademacher complexity is small, it is then viable to learn the hypothesis class F by minimizing the empirical risk and thus effectively reducing the generalization gap.
Finally, we define the structure of neural networks and introduce a few related quantities. The problem studied in this paper is a multi-class classification task with the number of classes being K. Consider an input vector x X S R4, an L-layer neural network is defined
(3) with W being the set containing all weight matrices, i.e., W = ( E [T]]] and the notation p(-) is used to express any non-negative monotone activation function and we further assume that p(-) is I-Lipschitz, which includes popular activation functions such ReLU ap- plied element-wic wise on vector. Moreover, the i-th component of neural networks' output is written as fw (x) = [fw (x)]; and pairwise margin between i-th and j-th class, denoted as (W(x) (x) = Sw (x) - (x), is said to be the difference between two classes in output of the neural network. Lastly, we use the notion of z and y² to represent the output vector of the k-th layer (k E [L - 1) under natural and weight perturbed settings respectively, which are where W E (es) denotes the perturbed weight matrix bounded by its element-wise -norm with radius e, for some i [k].
[w(x) = ("....p x)...) ) E F X--R
z (..P((''''x) and zh (..pp (W
x)...),, (..)...),
3.2 BUILDING BLOCK: SINGLE-LAYER WEIGHT PERTURBATION
We study the sensitivity of neural network to weight perturbations through the pairwise margin bound fw (x). Specifically, when i and j corresponds to the top-1 and the second-top class pre- diction of x, respectively, the margin can be used as an indicator of robust prediction under weight first consider simple example with a three-layer
perturbation to W. For ease of understanding, neural network and explain the bound through the error propagation incurred by weight perturbation.
We define the neural network as fw (x) w p(W2 P (W x)) with w being the weight matrix of the i-th layer and assume that one could only perturb any element in the first weight matrix within an
too norm ball of radius e, i.e., W E B (E). We also define an error vector as e,, which stands for the entry-wise error after propagating through the i-th layer. Since no perturbations happened prior to the first layer, we would directly take input vector x and derive an upper bound on the entry-wise error While every element in the first weight matrix is allowed to change its magnitude by at most e, the maximum error for any entry by matrix-vector multiplication becomes
[e.): = IW W S Σ - W
[x]
S Σ
cl [[|>]] = =<|[>]]
(4)
Since the following layer weight is not subject to perturbation, we simply take the magnitude of each element in the subsequent weight matrix to calculate the next error vector. In this case, have the next layer's eтror with 2 as jez). = E, [W [eil, with error propagation over layers, we arrive at the final layer and are able to assess the maximum change of any entry in output value. By recalling the pairwise class margin f (x), we would like to inspect the relative change in error between any two classes. Specifically, we derive an upper bound on the pairwise margin between any two classes and B. In the above example, the difference in entry-wise maximum error can be deduced the following manner:
||x|| Σ, IW? Eventually,
[es]. - [es]s- =
Σ ( ( -WW
JeaJa
Σ (IW W&.eDe [|x//1 Σ WW2.1
(5)
|||||| mark |
w [|xIl,|((w) [W3)]]| |W -
|Ix|],
(6)

---

Under review as a conference paper at ICLR 2021
where inequality (i) comes from triangle inequality and inequality (it) results from taking the row in W² with maximum l norm. It is worth noting that there exist possible scenarios for the above inequalities to hold and therefore achieving the worst-case error. Specifically, using the example in Section 322 as we trace down the associated inequality bound in (i), see that the first inequality can be achieved when the final weight layer possesses all positive weights and that the row associated with label is greater than label 3 in all individual entries. Furthermore, weight matrix W has equal & norm throughout all rows, we can then tighten the bound to give the worst-case error in (ii). Nevertheless, we could see from the above example that the difference of maximum eπror between entries in output would be propagating at the rate of weight matrices' (o) norm. By utilizing this essential concept, we introduce the first theorem our results, which provides an upper bound on the pairwise margin under single-layer weight perturbation.
long the second
Theorem (N-th layer weight perturbation (N + L)) Let fw(x) W ((.. denote an L-layer neural network and let f = (... ...p(Wxx)..). with W [ + I, denote the corresponding network subject to N-th layer perturbation. For any set of perturbed and unperturbed pairwise margin f (x) and fw (x), we have
# (x) S (x) (x) W W -|=0~1|| -
where 2 p (...(
Proof: See Appendix
Since the final layer does not have any activation function, the margin bound on the margin difference when only perturbing the final layer can be simply derived, which is given in the following lemma.
Lemma (Final-layer weight perturbation) Consider the case N = L in Theorem we have pit (x) & (x)
(x) + 2e ||---|||, || where ---1 is the output of the (L - 1) -th layer.
Proof: See Appendix A.1
3.3 GENERAL SETTING: MULTI-LAYER WEIGHT PERTURBATION
With the developed single-layer analysis Section 3.2 as a building block, we now extend our analysis to the general setting of multi-layer weight perturbation, which is further divided into two cases: (i) the case of perturbing all L layers; and (ii) the case of perturbing I out of L layers.
3.3.1 PERTURBING ALL LAYERS
Once equipped with the concept of error propagation over subsequent layers, we consider the sce- nario where every layer in a neural network is subject to weight perturbation. We denote the model under this circumstance the all-perturbed setting. The following theorem states an upper bound on the pairwise margin between the natural (unperturbed) and all all-perturbed settings.
Theorem (all-layer perturbation) Let fx W ('.....p (...p(W'x).... x).)) denote L-layer (natural) neural network and les Iw (x) = (.WW" ...p( W x)...) with W E BBpp (e)), Vm E [T.], denote its perturbed version. For any set of pairwise margin fif (x) and fif (x). we have w
(x) + W!: W.lll, { ||x|]] 1// (
N (x) S (2)
+
1,00
Inpur Layer
ex+1 xx*
+ -e
2FL.
Ereor loyer Lol
Ernor of
Evenr from loyer 1 L-2
Wm -W? cm. Vi.j and Vm [L] (1)
where =² pl p(W p(W'" x) with Wmn defined as
W = W.,, + (gn((x))) E1, Vi.j
5

---

Under review as a conference paper at ICLR 2021
Proof: See Appendix A.2.2
Here, we provide some intuition on deriving the upper bound of the margin in the all-perturbed setting. The scheme behind this all-perturbed scenario be viewed error propagation. Specifically, we can choose any perturbed layer as the commencement point of propagation, then fix any other weight matrices' values and further calculate the propagation of error from that layer using the concept in Section 3.2] In such manner, after iterating through all these weight matrices subject to weight perturbation, one could obtain the final change in output value and therefore establish the pairwise margin bound. A close inspection of the bound shows that the propagation of error causes the first term since the input layer and the rest of the terms are errors propagating since the i-th layer in the neural network, where i E [L].
inductive layer- layer-wise
3.3.2 PERTURBING MULTIPLE LAYERS
The all-perturbed setting is a special case of perturbing layers from an index set when / = [b]. We extend our analysis to the general multi-layer weight perturbation setting with I [Z.] which includes the single-layer setting (1 = {N and all-perturbed setting (1 = [L) as special cases.
Theorem (multiple-layer perturbation) Let L-Layer neural network be written fw (x) W4 (...p((W)))) (W.))...) Given an index set [L), we define the perturbed neural network as
W = W., Vi [L] W W. W VE)
fw (x) Wh (...." ...p(W (W'x))xx))))))))) x)... with
for any pairwise margin between fo (x) and füv (x) we have
1 (x) 1. (x) I| - Wifhl, EEErrCLL-1I ce 1 (1/=2+1 |I(')) 1(L 1
MEL-I -| 11
+ +1 1)2EL
| |
= SW (x) (x
wherex* = -PW""" x)
WT + Emi Vi,J Vm [T]ON
W!y²"
WHJ Vi,J Vm (4] (T)
with Wmn defined
and z"
[:l + (gn(()))))) Vi.j ifEel
Wh. =
W Vi.j otherwise
Proof: See Appendix A.2.3
3.4
SURROGATE LOSS AND GENERALIZATION BOUND
3.4.1
CONSTRUCTION OF ROBUST SURROGATE LOSS ON PAIRWISE MARGIN
We aim to construct a surrogate loss function based on a standard loss function and study its behavior against weight perturbations. Specifically, given perturbation radius and the original loss function (x), v). robust training aims to minimize the following objective function:
ě(fw (x), u) (ua)) EBBQ ( 20 (x).
which we call it as the robustness (worst-case) loss. Even for a single data point (x, y). it is hard to assess the exact robustness loss since it requires the maximization of non-concave function over a norm ball. To make the problem of robust training against weight perturbations more computation- ally tractable, we aim to design a surrogate loss as an upper bound on the worst-case loss.
We focus on the construction of surrogate loss by means of pairwise margin bound in Section 3.3 We first define mathematically two popular loss functions in the classification problem, ramp loss and cross entropy, and derive their surrogate versions. Define the margin function M (fw (x),
M (fw (x), y) = min ffw (x))x - [x)())) [fw (x)], v zv
max fw (x)]g²
(8)

---

Under review as a conference paper at ICLR 2021
The ramp loss for a given data point (x, y) and neural network fw (-) (+) is written as famp (fw (x).
(,M (x), y)). where the function Φ R + [0, 1] is defined as (y(t) = 1 if I 0, o, (t) = if 2 7, and (t)
1 - ク/4 if E [0, 7]. Since the ramp loss is a piece-wise linear function, its surrogate loss can be directly obtained with the pairwise margin bound in Section 3.3 The cross entropy is written as CE((ww(X) (x), y) = - In([fw (x)ly). where fw (x) represents a neural network
expl/w (0),
with its output passing through a softmax layer. That is, (x)]; = Eec(k "xpllwtlll""
For ease of demonstration, we will be using ramp loss and its pairwise margin under single-layer per- turbation in the following lemma. The surrogate loss analysis for cross entropy and robust surrogate
loss for multiple-layer perturbation is given in Appendix B
Lemma (robust surrogate ramp loss) Let N E
[L] denote the perturbed layer index and let
((fw v) = ont (x) max kE|K]
W
IT
||*||
1,00
morgis
worstscuse ervOr
Then we have upper and lower bounds of é in terms of 0-1 losses expressed as
max W WN (6) [v e arg max, e(K] (x)1,/ } S ((Sw(xx))))
1 1(M - 2 ma [W -=== I"'l,, -= N-1 ||
11 | S 57}-
Proof: Please see Appendix B.1
One could observe in the formula that the margin function (JW((x),)) serves as an accuracy objective similar to the standard training process while the latter term could be conceived as the worst-case eπror caused by weight perturbation that should be suppressed. Therefore, by training under such an objective, we can simulate the scenario of robust training. Another intuition on the surrogate loss function is that the surrogate loss also implies the difficulty of training robust and generalizable models against large weight perturbations. Since error caused by perturbations would be surging rapidly through layers, only small perturbations can be applied in training and practice, permitting the worst-case error term to be smaller than the margin term. However, one follow-up question that naturally arises is whether not the generalization gap will be widened when training with the robust surrogate loss. The following section investigates the generalization property while conducting robust training and provides some theoretical insights training toward a generalizable and robust model under weight perturbation.
3.4.2 GENERALIZZTION GAP FOR ROBUST SURROGATE LOSS
We consider the robust surrogate loss established in Lemma and study its generalization bound via Rademacher complexity in Theorem 4 where S = {xx, Vi F denotes the set of i.ddd training samples, X : X2,,2,,.. X.. E Rdx= denotes the matrix composed of training data samples, and dmax= max dl, .., dr} denotes the maximum dimension among all weight matrices.
Theorem (generalization gap for robust surrogate loss) With Lemma consider the neural network hypothesis class F (fw(x)) (W", W ...., W²), W lla S sh, (T 1lll. S
bn, h E [L]]. For any > O, with probability at least - ō, we have for all (
((. (WW
IB (e) a.t. y # arg max max [((x S Ei 1 (fww(x)) S
max, un. (xx)) + max W|: [T | 1,00 ThE N || (WLL |kxills )
7
l0lgg()) (2g
|||||
11 )
Iten (2t)
3/2
+
supuperr
1,00 11
-
log (WL begr I |x112,2 + 33
complesity trrm coused by pabust traitinn
7

---

Under review as a conference paper at ICLR 2021
Proof: Please see Appendix C.1
As highlighted in the bracket term of Theorem 4 if the product of multiple weight norm bounds is not well confined, the model will suffer from notable generalization gap. Consequently, our analysis suggests a solution to reduce the generalization gap by imposing norm penalty functions on all weight matrices for training generalizable neural networks subject to weight perturbations.
3.5 THEORY-DRIVEN LOSS TOWARD ROBUSTNESS AND GENERALIZATION
With our theoretical insights, we now propose a robust and generalizable loss function. Standard neural network classifier training uses classification loss Eds (x), y) that aims to widen the pairwise margin so as raise accuracy. but won't 't necessarily be able to curb the error in output once weight perturbation is imposed. address this issue, we propose to train under a mixed and regularized objective given a data sample (x, y). which would, in turn, balance the tradeoff between standard accuracy, robustness, and generalization. The designed loss takes the form:
tu- Σ (/(W I
(ffw(x)) = (ca((f +A 5'
max max(nW" (x
(9)
1,00
standard loss
rolustness loss from Thmn H
peneraization regularizaiion from Thm
The first term in the proposed loss function originates from standard classification problem for task- specific accuracy, while the second term results from the maximum error on pairwise margin (the term 7/ (x< ) defined in Theorem 3) induced by weight perturbation. Finally, we contribute the last term to the theoretical findings in Theorem [ where imposing norm constraints on weight matrices could benefit generalization and prevent the generalization gap from widening.
NUMERICAL VALIDATION
We validate our theoretical results and the designed loss function in (9) through two sets of exper- iments: empirical generalization gap with matrix norm regularization and robust accuracy against adversarial weight perturbations.
Experiment setup We used the MNIST dataset comprised of gray-scale images of hand-written digits with categories. We trained neural network models in (3) with four dense layers (number of neurons are 128-64-32-10) and the ReLU activation function without the bias term. We used the loss function e in (9) with all-layer perturbation bound (i.e., I [Z], identical weight perturbation radius e (or évain), cross entropy as the standard classification loss Écte, and batch size of 32 with 20 epochs. Stochastic gradient descent with momentum is used for training, with the learning rate set to be 0.01. For the generalization experiment, we follow the same setting in (Yin et al.) 2019), which uses 1000 data samples to train the neural network with 100 epochs. All experiments were conducted using an Intel Xeon E5-2620v4 CPU, 125 GB RAM, and an NVIDIA TITAN Xp GPU with 12 GB RAM. For reproducibility, our codes are given in the supplementary material.
Empirical generalization gap Figure (a) shows the empirical generalization gap (training accu- racy- test accuracy) with respect to the matrix norm regularization coefficient defined in (9. As indicated Theorem increasing μ effectively suppresses the Rademacher complexity and thus reduces the generalization gaps, which are consistently observed on neural networks trained with different weight perturbation level c.
Robustness against adversarial weight perturbation To evaluate the robustness against weight perturbations, we modified the projected gradient descent (PGD) attack originally designed for input perturbation (Madry et al. 20118), which we call as weight PGD attack. Starting from a trained neural network weight W, the perturbed weight W is crafted by iterative gradient ascent using the signed gradient of the standard loss denoted as sgn( ( Wastsfff (x), v)), followed by an element-wise clipping centered at W. The attack iteration with the step size is expressed as
W (0)
W. (++1) Clipw.
W + a sga( Vwlete (f (x), (x).
(10)
8

---

Under review as a conference paper at ICLR 2021
70-
0.01
30
prll. aut 37.80%
0.05
03, sucu27 221122
0.1
0125, auow
uno
50
3666 C1 COR2ORROCM DEBS not DoporEAncCenaA 30220004 odon Eo0 2002 Weggh perturbation lovel (6)
(a) Empirical generalization gap
(b) Robust accuracy under adversarial perturbation
Figure 1: (a) Empirical generalization gaps when varying the matrix norm regularization coefficient I in (9). Consistent with the theoretical results, the gap reduces as increases for every value used for training. (b) Comparison of test accuracy of neural networks trained with different coefficients À and l under weight PGD attack (200 steps) with é perturbation level. AUC refers to the area under curve score. Joint training with the two theory-driver terms described in (9) indeed yields more generalizable and robust neural networks against weight perturbations.
We trained neural networks with different combinations of the coefficients À and μ in (9) using Euain 0.01. [ (b) shows the test accuracy under different weight perturbation level e (i.e., the robust accuracy) with 200 attack steps. The standard model (A = μ = 0) fragile to weight PGD) attack. On the other hand, neural networks trained only with the robustness loss (A > 0 and 0 and μ > 0) can improve the robust accuracy due
0)
or the generalization gap regularization to improved generalization and classification margin. Moreover, joint training using the proposed loss with proper coefficients can further boost model performance (e.g., (A, 1)) (0.0125, 0.01)), as seen by the significantly improved area under curve (AUC) score of robust accuracy over all tested e values. The AUC of the best model is about 2 larger than that of the standard model. Similar results be concluded for the attack with 100 steps (see Appendix D) In Appendix [D. we conduct additional experiments on the coefficients À and and discuss their tradeoffs. We also report the run-time analysis Appendix Training with our loss function has comparable per- epoch run time when comparing to standard training.
CONCLUSION
In this paper, we developed a formal analysis of the robustness of the pairwise class margin for neural networks against weight perturbations. We also characterized its generalization gap through Rademacher complexity. A theory-driven loss function was proposed, and the empirical results showed significantly improved performance in generalization and robustness. Our analysis offers theoretical insights and training loss design principles for studying the generalization and robustness of neural networks subject to weight perturbations.
REFERENCES
Guozhong An. The effects of adding noise during backpropagation training on a generalization performance. Neural computation, 8(3):643-674) 1996.
Alessandro Barenghi, Luca Breveglieri, Israel Koren, and David Naccache. Fault injection attacks cryptographic devices: Theory, practice, and countermeasures. Proceedings of the IEEE, 100 (11):3056-3076, 2012.
Andrew R Barron and Jason M Klusowski. Approximation and estimation for high- -iseesiimnsi deep learning networks. arXiv preprint arXiv: 2018
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normaliinn margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249) 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks, 2019.

---

Under review as a conference paper at ICLR 2021
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic. Timothy Mann. and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE International Conference Computer Vision pp. 4842-4851, 2019.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Yaniv, and Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. The Jour- nal of Machine Learning Research, 18(1):6869-689) 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. Inter- national Conference on Learning Representations, 2017.
Yannan Liu, Lingxiao Wei, Bo Luo, and Qiang Xu. Fault injection attack on deep neural network. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 131-138, 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. To- wards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning- MIT' press, 2018.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generaliza- tion in deep learning. In Advances in Neural Information Processing Systems, pp. 11615-11626,
2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theorr, pp. 1376-1401,200 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general-
ization deep learning. In Advances in neural information processing systems, pp. 5947-5956, 2017.
Henning Petzka, Linara Adilova, Michael Kamp, and Cristian Sminchisescu. Feature-robustness, flatness and generalization error for deep neural networks. arXiv preprint 20X0092001.00939, 2020.
Dong Su, Huan Zhang, Hongge Chen, Jinfeng Yi, Pin-Yu Chen, and Yupeng Gao. Is robustness the cost of accuracy?-a comprehensive study the robustness of 18 deep image classification models. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 631-648, 2018.
Ryan Theisen, Jason M Klusowski, Huan Wang, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. Global capacity measures for deep relu networks via path sampling. arXiv preprint 1rXiv:1910.10245 2019.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be odds with accuracy. In International Conference on Learning Representa- tions, 2019.
Victor Van Der Veen, Yanick Fratantonio, Martina Lindorfer, Daniel Gruss, Clémentine Maurice, Giovanni Vigna, Herbert Bos, Kavch Razavi, and Cristiano Giuffrida. Drammer: Deterministic rowhammer attacks mobile platforms. In ACM SIGSAC conference on computer and commu- nications security, pp. 1675-1689, 2016.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In International Conference on Machine Learning, volume 1, pp. 2, 2019.
Tsui- Wei Weng, Pu Zhao, Sijia Liu, Pin- Yu Chen, Xue Lin, and Luca Daniel. Towards certifi- cated model robustness against weight perturbations. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 6356-6363, 2020.
10

---

Under review as a conference paper at ICLR 2021
Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391 -22,,, 2012.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International Conference on Machine Learning, pp. 7085-7094, 2019.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P Xing, Laurent El Ghaoui, and Michael I Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, 2019.
Pu Zhao, Siyue Wang, Cheng Gongye, Yanzhi Wang, Yunsi Fei, and Xue Lin. Fault sneaking attack: A stealthy framework for misleading deep neural networks. In ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2019.
Pu Zhao, Pin- Yu Chen, Payel Das, Karthikeyan Natesan Ramamurthy, and Xue Lin. Bridging mode connectivity in loss landscapes and adversarial robustness. In International Conference Learning Representations, 2020.
A MARGIN BOUND
A. SINGLE-LAYER BOUND
We shall first prove when N * and follow similar reasoning to prove the case when = L. Consider the difference between set of pairwise margin زi (x) fW (z)), we have
1 (x) (x)
(W! W
(26-1 -
(11)
W 2 2) P(W
(12)
W w W (2 1 x1-2)
(13)
(21-
(14)
[ W (W 1)- ||
(w"
w- )z N-1
(15)
|| W | D W
(16)
where inequality (a) results from applying Hölder inequality, and inequality (b) comes from the contractive property (I-Lipschitz) activation function p(.). Inequality (c) and (d) come from
triangle inequality applied element-wise on vector w/-1(22- 2 combined with induction
while incquality (e) simply comes from the fact that every element in matrix W W has at most in magnitude.
With similar reasoning, we proof the scenario when = L as following
(x) (x)
w
(
W W 1 -WW! C
(17)
(0)
$ 2e 1 TT- T-11
(18)
2c
(19)
where inequality (i) comes from problem definition (within element-wise Ex norm ball) and since the activation function p(-) is non-negative, we could transform the inner product to its & norm.

---

Under review as a conference paper at ICLR 2021
A.2 MULTI-LAYER SCENARIO
A.2.1 KEY PREREQUISITE
Before going through the proof for all-perturbed bound, shall be introducing maximization problem and search for its solution. Recall that we have defined in Section 3.T the notion of output vector under weight perturbation setting, now consider maximizing its ε norm over given perturbed matrix set W and give the following solution. Using the notation in Section 3.1 we have 2" as the output vector under perturbation setting and write the optimal vector that achieve its maximum norm as z We then obtain the following solution
|| 111
2 ;
max W
(W.)
W + em, Vi,j Vm E {2, L} W Why + (x))()) Vi,j
where zt p((W (W" x) with
The reasoning behind uses the non-negative property of activation function, for any element in a matrix W, the choice to maximize it's & norm matrix-vector product is to go in the direction identical to the sign of the vector's element-wise value since the activation function is applied after the first layer, we would then obtain the solution above.
A.2.2 ALL-PERTURRED BOUND
In the following proof for Theorem 2 we apply similar steps in Appendix I and consider the dif-
ference between set of pairwise margin under natural and weight perturbation setting, recall in The-
defined that fw (x) wh (..WW. ....p( -.p(('x)x.. x)...) and (x) w (..W"..... ...pp.. (W x)...)
orem 2
Thus for any set of pairwise margin w (x) and fw (x), we have
w (x) (x)
[ W -W: W/
(20)
||W! W//:l,1 ( -- 2) - p(W (W'--12" ( + 22
(21)
|// wfllll { || (2) -z 2|// + +|(
1---1
+ Zel
(22)
||W Whilh (1((W2-1)2)
1.00 | 26 pl (26-226-3)
+ +
|
3/ 11-11
+ 2e7.
(23)
(d)
|
W l
c ||x|] 11/=12
(WL-1)7
)ct
2
22 | }
+ +
+ 211
(24)
(5)
| - WHill
1
(I
1,00
1,00
+
L-3
In k= |((*))²
11, )es41
|
+ + ||
1
2 1-11
2cz.
(25)
In the above proof, inequality (a) comes from the problem definition (perturbation of final layer within e1) and inequality (b) results from the contractive property of p(-) (1-Lipschitz) combined with the use of triangle inequality. Inequality (c) was achieved through triangle inequality applied
on elements of W zL-2) and using the fact that W 4-1 w has every element less
12

---

Under review as a conference paper at ICLR 2021
than equal to CL-1 in magnitude. By the process of induction and maximizing the & norm of perturbed output under weight perturbation z", arrive inequality (d) and (e).
A.2.3 MULTI-LAYER BOUND
We now proceed to utilize similar reasoning to establish the multi-layer bound when weight pertur- bation is imposed according to an index set
[x()) (x)
(W W (W -W W
(26)
I W - 21 (WW--2z
+ +1(L 12
(27)
I! w {
12 -
+ || w
+ 1(L E 1)2c1 11-111
(28)
$ <| - W ( (1( p(W 2t
p(WL-22
+ +1(L 1 E 1)er.-1 | 1(L 1)2E1. 12--11
(29)
|! Whill { 1111 D) | 1
(W
1(L 1
I)EL-1
1
L-3
Σ
1(j + 1
( ) |
1( 1)2e1
|
(30)
1-1
<|
W
Σ
(I ((*)) )ee |---111
BE/11LL-11
+
2
x
+ 1( 1)2c, 1
(31)
The proof for multi-layer bound follows same reasoning from the all-perturbed setting except in- dicator function was added to check whether certain layer m in the index set and at last rewrite the expression using the members of set I.
B SURROGATE LOSS
B. CASE ON RAMP LOSS
We now provide proof for Lemma 2 Recall the definition of ramp function in Section 3.4. we have that ramp loss for a given data point (x, y) and neural network fw(-) written as w)). where the function o. R + [0, 1] is defined as
Cramp (w((x, dy
1
if
t 5
(1)
0
if
t 27
(32)
if
E [0,
13

---

Under review as a conference paper at ICLR 2021
Then for any (x, y), using ReLU activation function, we have
max
(1y + arg maggmx(ss (x)
W
(o)
0 (min (f (x),
(33)
w
Φ, (min minls (x)]u - 1 (x)lbr
(34)
y' W
(9
0, min (x)]y (fw y'yy y" W || IIN---
maxe|
8'
1,00
(35)
In
0, [min[fw (x)ls (xw -2 max kE[K]
ell || || 11
1,20
y'
(36)
g) 2y (M(f (x),)) max e
W ||
11
||
11 II--N-11
(WT--k)7
(37)
KE[K]
1,00
2 (M(((()))))) - max
[ ki:
||x||| -T
|||
(WLL-))T]
1,00
kE[K]
(38)
i(fw(x) (x).8)
(39)
2 (fw - max
<l
[|x||] MT
[
11,00
I---N-1 k=1
(WL-
1,00 S $7),
KE[K]
(40)
where inequality (a) is due to the property of ramp loss while inequality (b) is by the definition of margin and inequality (c) comes from applying Theorem Inequality (d) results from using triangle
inequality and taking its maximum, inequality (e) is by the definition of margin and inequality (f)
comes from the fact that with ReLU we have [Ip(Ax)] I ||A|]] Lastly, inequality (g) direct consequence from property of ramp loss.
B.1.1 RAMP LOss ON MULTIPLE LAYER BOUND
We now follow similar course and prove robust ramp loss using the multi-layer bound in Theorem We consider the robust loss form proposed in Section 3.4.1 and have that,
max frmm (Sw (x), 1/)
W
(0)
Φ, (min M w (x).
(41)
w
(6)
S
Φ, min [f (x)ly [fw
max 2 (x(1))
(42)
8'
V'7y
(
$ 2 (M((((x)) (x).0)
max vdy
Mp (x(T)) ((fw(x),)))
(43)
B.2 CROSS ENTROPY
We further consider the case of cross entropy and prove upper bound for it. We denote the loss function CFF(),, and during training, hard label applied. Recall the definition of fw in
14

---

Under review as a conference paper at ICLR 2021
Section 3.4.1 we have the difference of loss function between natural and perturbation settings as,
(x( (E((w(x),
= =-yln W (x)l, (x)
(44)
(x),
(45)
(x)s
Inn (el/w((0)o- (x),, Σne[Ka els (0)l.
Σxe[K] elfw(())a (x)le
(46)
(a)
(f (w)u ellw -Uw)))
(47)
V'zy
(b)
In In(e (e maxy p 1x (x)
(48)
max v/u VW (x({);
(49)
y'
where inequality (a) comes from taking the maximum in the set of all ratios { Uw 001a
al and in-
equality (b) comes from monotonicity of exponential function. Finally, the last expression (c) can be referred Theorem Thus with the above proof, could establish the following robust surro- gate loss for cross entropy, denoted as CE(Jw(x), u))
CB(Sw(x). = CE(Sw (x), y) + maxy "W (x)T)
C GENERALIZATION BOUND ON RADEMACHER COMPLEXITY
C.I PROOF ON SINGLE LAYER BOUND
To show the Rademacher complexity and generalization gap on single layer robust surrogate loss, we first introduce a result proven in (Bartlett et al. 2017) and another classical result in statistical leamning theory and proceed to give proof on Theorem 4 Given set S {(x,, (:) u))= of i.i.d training samples, denote X := [x1, X2,....... , X,] E Rdx= the matrix composed of training data and let dmax = max(d, (d, di.... ........................ d as the maximum dimension among all weight matrices.
Lemma (Mohri et al. (2018)) Assume that the range of loss function E(-) is [0,1]. Then, for any 5 E (0, 1), with probability least - 8, we have for all E F
R(f) Rn(F) + 2R((=) 3v log 7
where R(f) and Rf) stand for population risk and empirical risk, respectively.
Lemma (Bartlett et al. (2017) Consider the neural network hypothesis class,
F= (x) w (wl w2
W s sn. || 2.1 S by h E [L]}
We have upper bound on the Rademacher complexity.
||||| (
(2))218) 3/2
R(F) 26log(n) log(22mar)
We now study the Rademacher Complexity of the function class
è = [(x((xx) ((Sw(x).)) SE
15

---

Under review as a conference paper at ICLR 2021
where {(:) is denoted in Lemma 2 and let My {(x, v) + (x), f E F}. Then could obtain.
R(()) 1 (R(Ms)) + E. sup " JEF
2e
Us
max kE(K]
- -= |[
1,00
|xxilli)),
(50)
where the inequality was achieved by using the Ledoux- Ledoux-Talagrand contraction inequality and the convexity of the supreme operation. Consider the second term, we have that
2c
Eg (sup FEF
1/ max W kE[K]
II-N-- || - kW 1
1,00 | 11,,00
(51)
(a) 2e
sup max
W
-- (WW-h)) 11 Exll Σ 1/
||xll] I]
(52)
n
feF kE[K]
(b)
sup I= [ JeF
|| 1,
1
(53)
where inequality (a) achieved by separating neural network related parameters and inequality (b) is result of applying Khintchine's ' inequality.
Thus, combined with Lemma 4
we have that
R((x) ~
1
4
60 log(n) log (2dmaw)
|X||
1h
by
2/3
3/2
31322
7
8j
+
2c
sup xI
II k=o
N-1
[[
(54)
n
/EF
Once we have calculated an upper bound for R(fF), then Theorem is a direct consequence of Lemma 2 and
C.2 EXTENSION TO MULTIPLE LAYER BOUND
In this section, we consider the robust surrogate loss under multi-layer bound and study its Rademacher complexity, We first give the expression of the robust surrogate loss then give an result on generalization bound.
Lemma Define the robust loss function {(fw (x), v) as
((fw(x). Φn (f(fw(x).V)
2 max kE[K]
| Σ
El (1
w
1,00 )
(1ff
|1( ||x||]
(E/V(L,L-1)
||x|| }
+1(L 11LL-11 D)-- (I
1(L
1)2ez
(11
W
)
||x|| (55)
1,00
1,00
We would have that
max
1(y F arg max (x)))) S ((fw(x).))
w
$ 51(M (M(M(f(())))) - max KE[K]
W {
Σ
cT( ;=1
Wi
|I(
||x||
1,00
+ 1E
wi
||ا|| } 1(L E 1)2El (11
wi
) ||~|||
1,00
1,00
Using the above loss, we could further establish an upper bound on robust surrogate loss and provide statements generalization bound. Given the following function class
16

---

Under review as a conference paper at ICLR 2021
E ((x, y) - ((((())
We have that,
R({x) S _ (R())) + -E, Ey
2
sup LEEF i=1
Vi max
{
Σ
c w 11,00 )x
n
kE[R]
(11=241 |( 000
|xx||1 + 1(L - 1E ( 1-
Wo
1,00 | }
+ n
Ey
sup Σ
Wi
) ||x||1
(56)
LEFF i=1
1,00
which the second term can be bounded as,
Ev
sup SEF
V max KE[K]
Whill1 {
E
(
6
IT
=1
W
1
)x
1,00
(EI((LL-1>
(T/ (I ||xil] + 1[ -1 I)eL
1 W
)
[[xel11]]
(57)
1,00
2 sup max { [1
Σ
(1 w
(mf
n fet kE[K]
(EA((1,111)
+ +1LL DeL- (
2
w
E}}
Σ
us ||x||
(58)
1,000
2 S sup max { (1WWkl { n kE[]
Σ
Ee
w
(
(I(w))
1,00 )} |
(EM/LLL-11
1 - (
w
(59)
1.00
while the last term can well be bounded as,
2 Fv
sup fEF
wi
||
||xi|l1
(60)
1,00
2 sup 1(L E I)EZ (u -
ww
1,00
Exl
Σ
|
(61)
21(L E f)ez sur (u
W
1,00
(62)
With all of the upper bounds above and Lemma we have the following theorem,
Theorem (generalization gap for robust surrogate loss) With Lemma 5 consider the neural
network hypothesis class F [fw (x) =(W2, W w..... wT), w lla I sn. (w.)l(""TT 12,1 S bn, h E [L]} For any y > 0, with probability at least - 5, we have for all f-)() EF
P(RN) (3W s.t. y + arg max [fw (x)), v E[K]]
< 1 Σ
[fw(x:) S 77 max ifw (x:)),, + 2 max Au:
n
kE[K]
x {
c <1')
W
|1
(w>)²
(aleEDee + 1(L 1E D) (1
b- w 11 } | ll
1,000
(EAILLL-1)
21(L E I)EL 1-11
(1
w" )
||x:|||
+ 1
1/
+
60 60)g((1) log( (oggaamaa)) |||||
n3/2
n
2 sup max KE]]
|Wwtl {
Σ
(1 w"
||
) (1اiatt || 1,00
+ -1 - E ( w ||
}} + 21 E (1
w || } |1 1x
+ +3/ 2m
log 2
(63)
17

---

Under review as a conference paper at ICLR 2021
D ADDITIONAL EXPERIMENTS
D.1 SUPPLEMENT OF FIGURE 1 (A)
For completeness, Figure adds the curve of (the standard generalization setting) in Figure
(a). The generalization gap is obviously lower than others when O, but its trend with respect to regularization is similar to the setting when of
E
E 0.01
-
E 0.05
0.1
Train Acc. TTst Acc (%)
0.2
Regularization (μ)
Figure 2: Empirical generalization gaps when altering the matrix norm regularization coefficient j
in
D.2 WEIGHT PGD ATTACK (100 STEPS) ON MNIST
Figure shows the accuracy and AUC score of different models against weight PGD attack with 100 iterations.
100
λ= μ=0, auc=17.78%
λ=O, p=0.01, auc=27.57%
80
>=0.015, μ=0.01, auc=26.43%
>=0.0125, p=0.01, auc=35.59%
Accuracy (%)
A=0.01, 0=0.01, auc=31.3%
>=0.001, 4=0.01, auc=24.25%
A=0.01, μ=0,, 26c-26.69%
40
20
0.0 0.002 0.004 0.006 a.da a.01 0.122 0.014 0016 0.018 0.22 0.022 0.024 0.026 0.028 0.03 0.032
Weight perturbation
Figure 3: Comparison of test accuracy of neural networks trained with different coefficients À and against weight PGD attack (100 steps) with perturbation level c.
18

---

Under review as a conference paper at ICLR 2021
D.3
MORE DETAILS ON THE TRADE-OFF BETWEEN AND f
9.7
9.0
3,03
3.9
10
20
38
38
21
19
12
13
18
32
1.2
9.8
10
10
8.9
98
9.7
9.7
9.8
32
30
37
29
3.7
23
29
18
10
6.9
19
27
9.7
8
8.9
16
602
1:5
24
10
24
038
10
28
30
20
20
16
166
0
15
20
19
19
31
24
8.7
S
S.7
20
10
11
10
10
38
9
9.7
7.9
4.5
0.24
37
26
18
20
9.7
21
10
11
25
9.7
9.6
8.9
4.9
8.9
8
0242
5.6
8
1.6
18
11
21
6
9.8
0:3
3.005
M. 00125 5013 0..25
(a) weight PGD (e = 0.01)
(b) weight PGD (c 0.02)
Figure 4: Comparison of test accuracy (%) trained with different coefficients À and μ against weight PGD attack (200 steps) with 0.01 and 0.02. The experiment setting follows Figure Tb).
Figure shows the trade-off with a fine grid search between coefficients À and accuracy under weight PGD attack using perturbation radius (e 0.01 and 0.02) with different combinations of À (from 0.01 to 0.015) and (from 0 to 0.05). We find that there is indeed sweet spot with proper values of À and μ leading to significantly better robust accuracy. When both À and are too large too small, the robustness of the model will decrease.
present test
D.4 ALTERNATIVE ROBUST LOSS FUNCTION
In addition to the proposed loss function in equation one can consider an alternative general- ization gap regularization term derived from Theorem which is Σ (log (II(W")) Il1,s0) + log (I| (l..oll.)))).. We compare its performance following the same experiment setting as in Figure (b) with finetuned coefficients À and It can be observed that this alternative loss function also yields robust models with comparable (sometimes slightly better) performance those in Figure
D (b), verifying the effectiveness in using theory-driven insights to reduce the generalization gap against weight perturbation.
100
λ= μ=0, auc=17.78%
0=0.00,, 1=0.1, auc=32.88%
80
A=0,00, p=0.1, auc=28.52%
>=0.00125, p=0.1, auc=35.889 88%
Accuracy (%)
A=0.00175, 1=0.1, 39.0%
>=0.0011, p=0.1, auc=38.1%
λ=0, p=0.1, auc=33.96%
40
20
0.0 0.002 0.004 0.006 0.008 0.01 0.122 0.014 0016 0.018 0.2 0022 0.024 0.026 0.028 0.03 0.032
Weight perturbation level
Figure 5: Test accuracy under different weight perturbation level with 200 attack steps. The models are trained using the alternative loss described in Section D.4
19

---

Under review as a conference paper at ICLR 2021
E ON THE VACUITY OF GENERALIZATION BOUND
In (Nagarajan & Kolter 2019), empirical observations were made to point out the fact that when given increase in the size of the training data, the error bound proposed in (Bartlett al. 2017) grows rapidly, loosing the ability to describe generalization gap and thus becomes vacuous. How- ever, we note that under our settings with models trained using the loss function in Section 3.5 the bound would not grow in polynomial rate and instead shows decreasing trend. We conducted experiments and presented results under the same setting as (Nagarajan & Kolter Kolter[2019) in Figure Here we verify two existing generalization bounds from different literature, one from (Bartlett et al. 2017 while another one from (Barron & Klusowski 2018) which the former one is composed mainly of product of weight matrices' norm and the latter is comprised of the norm of matrices' product. Empirical results in Figure [ a) show that under the standard settings the main components of generalization bound in (Bartlett al.. 2017) and Barron & Klusowski (2018) both grows rapidly with respect to the increase in size of the training dataset, as confirmed in (Nagarajan & Kolter 2019). Another empirical finding in the last column of F shows that the multiplicative dif- ference between bounds in (Bartlett et al. (217)) and (Barron & Klusowski] 2018) exhibit a constant rate, demonstrating the vacuity of both bounds. However, when measuring the same component under our setting in Figure bb), new results showed decreasing bounds as the size of the training
dataset increases, concluding the non-vacuity of the associated generalization bounds in our settings.
log (Test emrr))
[eg(||Ee Wallo))
+0000.00 005
[W
4.5
+0100.11
--0.02 02
3.6
0.5
-3
3.5
2.5
512
2048
0192
32788
812
2048
8182
32788
512
2048
8182 32788
512
2048
8192
32788
Training Set Size
Training Set Size
Training Set Size
Training Set Size
(a) Standard Model (A = 0, / = 0)
log (Tss error)
Soo01 (- [ la)
2.8
c0000 D1
toot (uC
0.5
02
2.8
log
2.4
312
2048
8192
32708
26
512
2048
8192
32768
2812
2048
8192
32768
512
2048
8152 32768
Training Set Size
Training Set Size
Training Set Size
Training Set Size
(b) Robust Model (A 14 0.01)
Figure 6: Statistics associated with generalization bounds for standard model and robust model trained using equation The experiment setting follows Figure a In the first column, we present test eтrоr under weight PGD attack with perturbation level The curve with = 0 (no weight perturbation) corresponds to the standard generalization setting. In the second column, we present the product of spectral norms of the weights matrices, related to bounds in (Bartlett et al.) 2017]. In the third column, we show spectral norm of the product of the weight matrices, related to bounds in (Barron& & Klusowski 2018). In the fourth column, of the weights matrices divided by the spectral norm of the product of the weight matrices. Notably, we present each value into the logarithm function. For the standard model, both types of bound increase with respect to training set size and are shown to be vacuous, consistent with the results in (Nagarajan & Kolter 2019). For the robust model, both types of bound exhibit same decreasing trend as the test error and therefore are non-vacuous. Moreover, these two bounds demonstrate similar scaling behavior (nearly constant log ratio) in both standard and robust models.
show the product of spectral norms
20

---

Under review as a conference paper at ICLR 2021
As ablation study, Figure shows the performance of the robust model with (A 0.01, 1t That is, training a neural network without the generalization regularization term in equation 9 Unlike the standard model, it is observed that the generalization bounds still show decreasing trend with the test error. This is due to the fact that the robustness term in equation ( which is induced from our analysis of the worst-case in regularizing the network weights, and therefore making the resulting generalization bound non- vacuous.
propagation from weight perturbation, also plays role
109 erron)
(LLE (|WWlll)
3.2
Dt mnvile loot WAh
3:16
000
311
0.66
3.05
512 1580 2046 3072 8192 10800
812
1980 2048 3072 8182 10600
512 1960 2048 3072 8192 10600
512 1560 2048 5072 8182 10600 Training Set
Training Set
Training
Training Set
Figure 7: Ablation study of the robust model with (A 0.01, 0). The experiment setting is the same as Figure 6 In the absence of the generalization regularization term in equation (9), the generalization bounds still show decreasing trend with the test error.
F RUN TIME ANALYSIS
Table reports the per-epoch run time of the models trained with the standard model (A = 0, 0)
and the robust model (A = 0.01, 0.1) using equation (9). We train both models with 20 epochs and use the same hyperparameters, including setting the SGD optimizer with learning rate 0.01, and setting the batch size as 32. The cost of training both models are comparable.
Standard model (A = 0, f 0) Robust model (A = 0.01, /r = 0.01)
Avg. per-epoch run time
5.125 sec.
6.69 sec.
Table 1: Per-epoch run time (in seconds) averaged over 20 epochs with the same hyperparameters for the models trained with (A 0. f 0) and (A 0.01, l 0.1) based on equation
21


Reviews:
[{"review_id": "stYefE1yobu", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper investigates the effects of weight perturbations on the output margin for multiclass classifcation problems. The paper shows that robustness to weight perturbations can be bounded using the (1,\\infty)-norm of the weight matrices. The paper then suggests that a low (1,\\infty)-norm of the weight matrices leads to better generalization. Moreover, the robustness against weight perturbation implied by low (1,\\infty)-norms of weight matrices should increase the robustness against adversarial perturbations. To support these claims, the paper presents a generalization bound using the (1,\\infty)-norm of weight matrices as well as an empirical evaluation using a novel surrogate loss function that, when used in training, is empirically shown to reduce the generalization gap and increase the robustness against adversarial perturbations.\n\nThe paper is very well written and the theoretical analysis is sound. My only concern is that the generalization bound derived in theorem 4 might not be very informative or conclusive. The reason is that the Rademacher complexity becomes uninformative in the interpolation regime (i.e., neural network architectures that are complex enough to fit any practical training set perfectly). Since the generalization bound presented here relies on an upper bound on the Rademacher complexity using the already not too tight upper bound of Bartlett, 2017, it could be vacuous. In earlier works on input robustness [1], obtaining meaningful bounds required some covering of the input space with examples rather than a uniform bound over the model space. Since uniform bounds, such as uniform convergence, might not be meaningful at all in the interpolation regime [2] (and thus for most of deep learning), this could imply that the results in Thm. 4 in this paper are not conclusive. In [3], the robustness to weight perturbation was also used as a building block for a potentially non-vacuous generalization bound, so it might be worthwhile to discuss the relation to that paper.\n\nAnother line of work that might be worthwhile to discuss is weight noise injection during the training process, which leads to better generalization (e.g., [4]). That is, I would imagine the surrogate loss function is a more effective tool to improve generalization and robustness than random noise injection.  \n \nLastly, it should be discussed how practically applicable the surrogate loss function is. For that, at least a runtime analysis should be provided. \n \nIn summary, the paper presents interesting theoretical findings and a potentially practically useful surrogate loss function. The paper is lacking some discussion, but overall I would argue that the paper makes a valid contribution. Thus, I tend to vote for acceptance. \n\n[1] Xu and Mannor. Robustness and generalization. Machine Learning, 2012.\n[2] Nagarajan, et al. Uniform convergence may be unable to explain generalization in deep learning. NeurIPS, 2019.\n[3] Petzka, et al. Relative Flatness and Generalization in the Interpolation Regime. arxiv preprint, 2020.\n[4] An. The effects of adding noise during backpropagation training on generalization performance. Neural computation, 1996.\n\n\n‐------------ After Discussion ---------\nI am still of the opinion that the manuscript is not without flaws: the theoretical result is quite messy, the empirical evaluation is still limited, and the generalization bound could still be vacuous.\n\nHowever, the authors provided new experiments that indicate that the bound might not be vacuous in the considered setting, though. The authors also provide a preliminary runtime analysis that suggests the costs for using the surrogate loss do not explode (please include a proper runtime analysis in any future version of this paper). Since the authors furthermore did address my main points in my review during the discussion, I have increased my score to 7.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ObrtE1T1Hhz", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The draft proposes to bound the model generalization by controlling the adversarial perturbation of the model weights. If the weights in the neural network are bounded and the activation function is Lipschitz, the change of output of the network, as well as the Rademacher complexity of the hypothesis class, can be easily controlled. \n\nConnecting perturbation with the generalization is not something new no matter in theory or in practice. This is another draft formulating the network perturbation and generalization so that a norm product bound is derived. There are plenty of previous works on this already, e.g., the work by Neyshabur et. al. (perturb the parameters), and Bartlett et. al. (norm product bound). \n\nThe generalization bound proposed in this work is a trivial application of Bartlett’s norm product bound. Perturbing the weights and directly applying norm product leads to a bound not as tight, to some extent, it is mostly vacuous. \n\nFrankly, the method gives a pessimistic norm product bound and ignores all the effects caused by the “alignment” between the internal coefficient matrix and the input vectors, which is crucial in terms of understanding how input signals are handled throughout the network. I would encourage the authors to read some recent work by Barron et.al. which reduces the generalization bound from norm product to product norm. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "3w_p5ueOKg2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper discusses learning neural network models under weight parameter perturbations. In particular the paper motivates the use of a new loss function (equation 9) based on the analysis of neural network robustness (Section 3.2, 3.3) and generalization properties (Section 3.4) to perturbations of the weight parameters. Section 4 has experiments supporting the theory that the loss function in equation 9 is robust and has good generalization properties to weight perturbations.\n\nReview: I think the loss function in equation 9 is well motivated and clearly explained. Also the experimental results can be reproduced as the code has been included as part of the submission. Overall the paper is well-written.\n\nBut I do have a few concerns regarding the comparison and interpretation of the results with prior work on generalization properties of neural networks. Firstly, the work does not cite some relevant papers to the topic a couple of which I list below:\n\na.\tV. Nagarajan and J.Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. In NeurIPS 2019.\nb.\tN. Golowich, A. Rakhlin, and 0. Shamir. Size-independent sample complexity of neural networks. In COLT 2018.\n\nI believe the discussion in Section 2 of Nagarajan and Kolter, 2019 is very relevant to the results in the paper. Nagarajan and Kolter, 2019 show that the norm bounds of the weight matrices increases with the number of samples and hence conclude that the generalization bound results in Bartlett et. al., 2017 are vacuous. The current paper uses the results in Bartlett et. al., 2017 to derive generalization error bounds and additionally has another term dependent on the norms of the weight matrices due to perturbation. Given the discussion in Section 2 of Nagarajan and Kolter, 2018 I am concerned if the bounds obtained in Section 3.2-3.5 are vacuous. I will like to see a discussion and experimental results in light of the observations in Nagarajan and Kolter, 2019.\n\nIn the experimental section, I am interested in also knowing the results for the case $\\epsilon = 0$ in Figure 1(a). Also, if possible can the authors include a discussion or guidance on the sensitivity of the results to the hyper parameters $\\mu$ and $\\lambda$? For example the performance seems to get worse when moving from $\\lambda = 0.01, 0.125$ to $\\lambda = 0.015$ in Figure 1(b). \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0uQPAbVCYZk", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nIn this work, the authors theoretically analyze the robustness against weight perturbations in neural networks. Upper bounds of the pairwise class margin for single-layer, all-layer, and selected-layer perturbation are established. Based on the analysis, the authors propose novel robust surrogate loss functions for 0-1 loss and cross-entropy.  Furthermore,  the authors analyze the Rademacher complexity of the perturbated network with the proposed loss, which leads to generalization bounds based on (Mohri et al. (2018)) and (Bartlett et al. (2017)). \n\nPros\n1.  I think the theoretical analysis part is clear and systematic. Efforts of each term in the bounds are well explained. \n\n2. The analysis is useful for a better understanding of the robustness of networks against weight perturbation. \n\n3. The proposed loss is also interesting.  The explicit upper bound reduces the computation of the maximization step in adversary training of weight perturbations.\n\n\nCons\n1. The product form in the bounds may grow fast and become loose.  I am not sure about the tightness since quite a few relaxations that rely on triangle inequality and maximum are used during the derivation.  It is better to report the value of each term in the bound in Theorem 2 or 3  for a better understanding of the bound.  The authors can employ the same experiment's setup in Figure 1.  \n\n2. Similarly,  I concern about the worst-case error term in the proposed loss in Lemma 2.  If the value of this term is large, the margin term minus the worst-case error will always be negative. Thus, the loss will remain a constant one, which is very harmful to training and optimization. \n\n3. In the experiments, only a simple MNIST dataset is evaluated.  I concern about the performance of the proposed loss in more practical cases. As stated above,  I think the proposed loss may be challenging for optimization.  This phenomenon may become more significant in difficult datasets.\n\n4. In Theorem 1, the definition of z^{N-1} is not given.  It is better to state it clearly to be self-contained.  In Theorem 2, the definition of W* is not given. The definition should be included in the main paper instead of in the appendix.\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study empirically and theoretically the behavior of neural networks under $l_\infty$-perturbations on the weight matrix.
For this purpose they first derive bounds on the logit-layer of the neural networks under perturbuations of a single or all layers. Then they propose to merge this bound (which depends on the product of the weight matrices) into a margin-based loss function/cross-entropy-loss and suggest to optimize this bound while simultaneously penalizing the 1,infty-norm of the weight matrices (which appears in the bound). Furthermore they derive a generalization bound for the robust error under weight perturbations.

There was a discussion among the reviewers over this paper. While several ones appreciated the setting, there was concern about that the bound is potentially vacuous and that the theoretical results are "messy". One reviewer criticized heavily the bound as not very useful and overly pessimistic.

This paper is in my point of view borderline but I argue for rejection. There are several reasons for this
- the motivation for this paper remains unclear. While the authors argue that a network could be attacked by changing logical values, this seems at the moment unrealistic as if the attacker has already hacked into the system much more harm can be caused in a much easier way e.g. by directly changing the output of the network. But even if one considers adversarial bit error attacks to be realistic, then the threat model would be completely different from $l_\infty$ and would rather be like $l_0$ (with potential unbounded changes if the network is not quantized). If the target is to study that more flat minima generalize better, then the target would not be a bound on the robust error but a bound on the normal test error which integrates an upper bound which measures "flatness" of the function. As the derived Theorem 4 contains a term where one has to take the supremum over the product of matrices over all functions in the derived function class, this is not true for the derived bound.
Thus I don't see why this bound is related to either of these two motivating topics.

- the bound is incomplete in the sense that it contains the sup_f of the product of 1,infty norms of the weight matrices. Why
did the authors not try to upper bound this term over the chosen function class? Even better would clearly to derive a bound on the Rademacher complexity in terms of the norms which are actually appearing in the bound. In the current way the terms in the bound and the chosen function class are mis-aligned.

- From a practical perspective the resulting loss is not useful for training deeper models (in the experiments a four layer network is used) as the product of the norm of the weight matrices grows exponentially in depth. Moreover, as pointed out the IBP bounds of Weng et al (2020) are much tighter than the bounds derived in this paper (and even IBP bounds are loose) 

- The experiments suggests that one gets a minor improvement in robustness while having to suffer from a significant drop in test accuracy (Figure 1b). Regarding the achieved robustness for epsilon=0.01 (it remains completely unclear how this noise model relates to the normal size of the model weights) one gets a robust error of around 30% on MNIST. This is much worse than what has been achieved for MNIST with much larger input perturbations (epsilon=0.3)

- The authors are missing an assumption on the activation function. With just non-negativity, monotonicity and 1-Lipschitz
the upper bound in A.2.1 (original version) cannot be derived. I guess you are implicitly assuming that rho(0)=0 but this assumption is not stated. There are other typos in the main text. In fact in the original version Theorem 4 did not contain the term
depending on b_h and s_j - this term was added in the revised version but not highlighted as all other changes.

In total there are too many open issues here. While I appreciate the hard work the authors put into the author rebuttal, I think that this paper needs a major revision before it can be published.


Decision: Reject