Smoothed-SGDmax: A Stability-Inspired Algorithm to Improve Adversarial Generalization
Authors: Jiancong Xiao
Jiawei Zhang
Zhi-Quan Luo
Asuman E. Ozdaglar
Venue: Submitted to ICLR 2023 (2023)
Keywords: Adversarial Training
Robust Overfitting
Generalization Bound

Abstract: Unlike standard training, deep neural networks can suffer from serious overfitting problems in adversarial settings, which is studied extensively by empirical papers. Recent research (e.g., Xing et al. (2021); Xiao et al. (2022)) show that SGDmax-based adversarial training algorithms with $1/s(T)$ training loss incurs a stability-based generalization bound in $\Theta(c+s(T)/n)$. Here $T$ is the number of iterations, $n$ is the number of samples, $s(T)\rightarrow \infty$ as $T\rightarrow \infty$, and $c$ is a $n$-independent term. This reveals that adversarial training can have nonvanishing generalization errors even if the sample size $n$ goes to infinity. A natural question arises: can we eliminate the nonvanishing term $c$ by designing a more generalizable algorithm? We give an affirmative answer in this paper. First, by an adaptation of information-theoretical lower bound on the complexity of solving Lipschitz-convex problems using randomized algorithms, we show that a minimax lower bound for adversarial generalization gap is $\Omega(s(T)/n)$ given training loss $1/s(T)$. This implies that SGDmax does not achieve the lower bound. Next, by observing that the nonvanishing generalization error term for SGDmax comes from the non-smoothness of the adversarial loss function, we employ a smoothing technique to smooth the adversarial loss function. Based on the smoothed loss function, we design a smoothed SGDmax algorithm achieving generalization bound $\mathcal{O}(s(T)/n)$, which matches the minimax lower bound. Experimentally, we show that our algorithm improves adversarial generalization on common datasets.

Under review as a conference paper at ICLR 2023
SMOOTHED-SGDMAX: A STABILITY-INPPIEED AL- GORITHM TO IMPROVE ADVERSARIAL GENERALIZA- TION
Anonymous authors Paper under double-bling brind review
ABSTRACT
Unlike standard training, deep neural networks can suffer from serious overfitting
problems in adversarial settings. Recent research (Xing et al. 202 lb
Xiao et al.
2022 suggested that adversarial training can have nonvanishing generalization er- ror even if the sample size goes to infinity. A natural question arises: can we climinate the generalization error floor in adversarial training? This paper gives an affirmative answer. First, by adaptation of information theoreeeall lower bound on the complexity of solving Lipschitz-convex problems using randomized algo- rithms, we establish minimax lower bound ()s((T)/)) given training loss of 1/s(T") for the generalization gap in non-smooth settings, where 7 is the number of iterations, and s(T) +00 T - +00. Next, by observing that the nonvan- ishing generalization eπror of existing adversarial training algorithms comes from the -on-smoothness of the adversarial loss function, we employ a smoothing tech- nique to smooth the adversarial loss function. Based on the smoothed loss fune- tion, we prove that a smoothed version of SGDmax algorithm can achieve gen- eralization bound (ss(T)/m)) /n), which eliminates the generalization error floor and matches the minimax lower bound. Experimentally, we show that the Smoothed- SGDmax algorithm improves adversarial generalization common datasets.
INTRODUCTION
Deep neural networks (DNNs) (Krizhevsky et al. 2012, Hochreiter Schmidhuber 1997) is suc- cessful and rarely suffered overfittigg issues (Zhang et al.) 2021). This phenomenon is also called benign overfitting, well-trained neural network model can generalize well to the test data. How- ever, in adversarial machine learning, overfitting becomes serious issue (Rice et al. 2020). Before the training algorithms converge, the robust test error starts to increase. This special type of overfit- ting is called robust overfitting and can be observed in the experiments common datasets. See Fig. [ orange curve. Therefore, mitigating the robust overfitting is important to increase the adversarial robustness of a DNN model. Several recent works tried figure out the causes of robust overfitting and designed methods to mitigate it. See the discussion in Sec. 2
A recent line of work (Xing et al. 2021b Xiao al. 2022) studied the robust overfitting issue of adversarial training from a theoretical perspective, using the notion of uniform algorithmic stabil- ity. Uniform algorithmic stability (UAS) (Bousquet & Elisseefi 2002) was introduced to bound the generalization gap in machine learning problems. It provides algorith-sppccin bounds instead of algorithm free generalization bounds such as classical results on VC-dimension (Vapnik & Chervonenkis, 2015) and Rademacher complexity (Bartlett & Mendelson 2002).. Such stability- generalization bounds provide insight into understanding the generalization ability of neural network models trained by different algorithms.
generalization
Traditional adversarial training is to perform stochastic gradient descent (SGD) on the max function of the standard counterpart, which is also called SGDmax (Farnia & Ozdaglar 2021). We will not distinguish two algorithms, "SGDmax" and "adversarial training (AT)", in the paper. The work of Xing et al. 2021b; Xiao al.) (222)) both showed that SGDmax incurs stability- based general- ization bound in (c(T)) + +(T") nn). Here T is the number of iterations, n is the number of samples,
sT) is a function satisfies s(T) 400 as T - 400, and c(T) is sample size-independent

---

Under review as a conference paper at ICLR 2023
Comparison of stability-based generalization bounds of adversarial generalization gap- e1 (T) and e2 (T) are sample size-independent terms. Details of the form of s('), c1 (T), (2( are discussed in Sec. 4 and Sec.
Table 1:
Worst-case
Achieves minimax lower bound ((s(("))n))
Upper Bounds
Lower Bounds
SGDmax Smoothed-SGDmax
((c + +0) m)))
(Tc2(T) + +())
X
00 ((T))
2 ((7(7)
term and increase with T. Details of the form of s(T), e(T) discussed in Sec. 4 and Sec. They also provided the matching lower bounds to show that the sample size-independent term is un- avoidable for SGDmax-base
adversarial training algorithms. It provides possible explanation of robust overfitting: even though we have arbitrarily large number of training samples, the adversarial generalization gap still does not vanish. The first question arises: what is the lower bound of the gen- eralization gap for algorithms in adversarial machine learning settings? To answer this question, we develop a minimax lower bound, (T(s(T)/n), for the generalization gap in non non- smoothitthigg settings when the training loss is (Ts( Clearly, SGDmax does not achieve the lower bound. Therefore, we are motivated to design algorithms reduce the non-vanishing sample size-independent term. The following main question of our paper arises:
Can we eliminate the error floor in generalization bounds of adversarial generalization gap?
We call the term c(T) as generalization error floor. It is observed that the term c(T) comes from the non-smoothness the adversarial loss. Hence, stability analysis on some smoothed algorithms has been studied recently. It includes noise-SGD and differential privacy-SGD (Basiily et al. 2020), adding noise weight and data (Xing 2021b), stochastic weight averaging, and cyclic learning rate (Xiao et al. 2022). Unfortunately. these smoothed algorithms cannot eliminate the generaliza- tion error floor.
In this paper, we employ smoothing technique using tools from Moreau envelope function to smooth the ad- versarial loss and perform gradient descent to this smooth surrogate. Following the name SGDmax. we refer the smoothed version of SGDmax which improves adversarial generalization. We prove that Smoothed-SGDDmt has the same training loss 1/)(T)
Jeteet Aoc marloy.aetur.
Smootthed-SGDma
adversarial loss. Most importantly. Smoothed-SGDmax eliminates the generalization error floor and achieves the minimax lower bound ((=(T)/1) of the generalization gap. The comparison of the stability-bai bbased generalization upper bound and lower bound of our proposed algorithm with the SGDmax- based adversarial training algorithm is given in Table [ Additionally, our proposed algorithm can be viewed as a general form of stochastic weight averaging (SWA (Izmailov et al. 2018)). As by-product, we provide understanding of SWA in our framework, see more discussion in Sec. 5.4 In Fig. T we show the training procedure of our proposed algorithm as well as adversarial trainnn CIFAR-10.
25
125
175
Figure 1: Experiments of adversar- ial training and Smoothed-SGDmax on CIFAR-10.
The contributions of our work are listed as follows:
1. Main result: we prove that the generalization error floor in non-smooth loss minimization can be eliminated by properly designed algorithm, which we called Smoothed-SGDmax.
We develop the minimax lower bound of the generalization gap in non-smooth loss minimization. Specifically, we show that an algorithm has at least (ss())n)) generalization gap if the training eтror training loss is (Ts( Smoothed-SGDDaal achieves the minimax lower bound.
3. Experiments on common datasets verify the thcoretical results and show the effectiveness of our proposed algorithm in practice.
2

---

Under review as a conference paper at ICLR 2023
2
RELATED WORK
Adversarial Robustness. Starting from the work of (Szegedy et al., 2013). it has now been well known that deep neural networks trained via standard gradient descent based algorithms are highly susceptible to imperceptible corruptions to the input data (Goodfellow et al. 2014] Chen et al.) 2017 Carlini & Wagner 2017). Adversarial training and its variants are proposed to improve the adversarial robustness of DNNs (Madry et al.] [2017: Wu et al. 2020; Gowal et al. 2020). Robust Overfitting. Starting from the work of (Rice et al., 2020), a series of work studied the causes of robust overfitting. (Yu al. 2022) studied robust overfitting from the perspective of adversarial distribution. (Chen et al. 2021 leveraged knowledge distillation and self-training to mitigate robust overfitting.
Learning Theory for Adversarial Generalization. Classical learning theory. The work of (At- tias et al. 2021 Montasser et al.] 2019) explained generalization in adversarial settings using VC- dimension. The work of (Yin et al. 2019 Khim & Loh 2018) studied the poor generalization of adversarial training using tools from Rademacher complexity. However, VC-dimension and bounds for generalization. They cannot reveal the effect of algorithms on generalization. Other theoretical analysis. (Sinha et al., (017) study the generalization of an adversarial training algorithm in terms of distributional robustness. The work of (Xing et al. [ Javanmard et al. 2020) studied the generalization properties in the setting of linear regression. Gaussian mixture models are used to analyze adversarial generalization (Taheri al. 2020 Javanmard et al. 2020; Dan et al., 2020). The work of (Allen-Zie Zhu & Li 2020) explains adversarial generalization through the lens of feature purification.
Rademacher complexity are algorithm-independee
Uniform Stability. Stability can be traced back to the work of (Rogers Wagner 1978). In
statistical learning problems, it well developed in analyzing the algorithm-based generalization bounds (Bousquet & Elisseeff. (2002). These bounds have been significantly improved in a recent sequence of works (Feldman & Vondrak 2018 2019). The work of (Chen al., 2018) discussed the optimal trade-off between stability and convergence. (Bassily et al. 2020) studied the stability of SGD non-smooth loss. They proved that the generalization bound contains sample size- independent term. The work of (Xing et al. [021b Xiao et al. (2022) showed that adversarial loss is non-smooth and SGDmax-brad based adversarial training algorithms will incur the generalization error floor.
PRELIMINARIES: STABILITY ANALYSIS FOR GENERALIZATION GAP
Let D be an unknown distribution in the sample space Z. Let {zi...., .,, D be an sample dataset drawn i..d. according to DD Our goal is to find a model w with small population risk, defindd as:
(p(w) E.-ph(w, 2),
where h(-,) -) is the loss function. Since we cannot minimize the objective RD(w) directly, we instead minimize the empirical risk, defined as
Rs(w)
Σ hww, 2;). 1=1
Let be the optimal solution of Rs(w). Then, for the algorithm output à A(S), we define the expected generalization gap
Egen (A, h. n, D) = ESwD= ((DD(A(S)) Rs (s(S))
(3.1)
We define the the expected optimization gap
Eoptl ( A, h, n. D) = (Rs - Rs(w)).
(3.2)
We use Egen and Eopt as short hand notations of the above definition. To bound the generalization gap of a model = A(S) trained by a randomized algorithm A, we employ the following notion of uniform stability.
3

---

Under review as a conference paper at ICLR 2023
Definition 3.1. A randomized algorithm A is e-uniformly stable for all data sets S,S' 2" such that and S' differ in at most one example, we have sup A [b(A(S);=) - - s.
(3.3)
The following theorem shows that expected generalization gap can be attained from uniform stabil- ity.
Theorem 3,1 (Generalization in expectation (Hardt et al. 2016)). Let A be s-uniformly stable. Then,
the expected generalization gap satisfies
Egenl [R (RDAA())(A(S)] [ s.
Uniform Argument Stability (UAS). If h is L-Lipschitz, i.e,, [h(w1;2) - h(w2: 2) S L|[u1 well, we can use UAS= (S) A(S) measure the generalization gap.
3.1
SGDMAX INCURS GENERALIZATION ERROR FLOOR
Adversarial Loss. In adversarial training, we consider the following adversarial loss h(w; 2)
max SS
g( w; z²),
(3.4)
where g(w;2 z) is the loss function of the standard counterpart. In practice, is usually the parameter of neural networks.
Generalization Error Floor. As discussed in (Xing et al. 2021b Xiao al. 2022). even if is smooth function, h is not necessarily smooth. They assumed h to be generally non-smooth or g-approximately smooth, which is subset of non-smooth functions. Under both assumptions, there exist non-vanishing terms in the bounds of UAS:
LTa
LTa
ci (T)
S UAS S (2)
(3.5)
where the forms of cj (I') and 02 (T') are listed in Table refer ej (T)) and 02 (T) as generalization error floors.
Table 2: Generalization error floor in previous studies.
Assumption on h
Upper Bounds eı (7)
Lower Bounds c2(7)
Xing et al. 2021b
non-smooth n-approx-smoothh
(LayTT) (Prop. 1)
M(avTT) (Thm. 1) ((nayT) (Thm. 5.2)
Xiao et al.
2022
OmjTT (Thm 5.1)
MINIMAX LOWER BOUND
Following the work of (Xing al. 2021b), we mainly consider the following function class of convex, non-smooth, and Lipschitz functions throughout the paper.
H = (h: W Z + is convex, L-Lipshitz in w. |W| Dw }.
(4.1)
L-Lipschitz is standard assumption in uniform stability analysis since (Hardt et al. assumption of convexity is to compare with the existing results and to develop the following the minimax lower bound.
2016 The
Definition 4.1 (Training Loss). We say an algorithm class A has training loss 1/s(T) on function class H. if for all E A and H. running A on h for iterations, we have
Eom A, D) <
where tom (T) 400.
4

---

Under review as a conference paper at ICLR 2023
Proposition 4.1 (Minimax lower bound of generalization gap). Let H. be the function class defined in Eq. (4.1). Let A be the class of randomized algorithms using n. samples with training loss 1/ (T)(T) on H. For all n, there exists T, s.t. the following lower bound holds.
s(T)
min max Egen (A, n. D) 2 AEA D
(4.2)
n
The proof of Prop. is based on a lower bound of the complexity of Lipschitz-conex problems (Nemirovskij & Yudin 1983), Ch.4), see Appendix A.T
Clearly, SGDmax can not achieve the minimax lower bound.
SMOOTHED-SGDMMX: ELIMINATING GENERALIZATION ERROR FLOOR
In this section, we will design an algorithm satisfying the following two properties:
1. It has the same training loss as the SGDmax algorithm;
2. Suppose achieves (T) training loss after iterations. Then, the generalization bound is bounded by /n.)
5.1 SMOOTH SURROGATE ADVERSARIAL LOSS
The non-smoothness of h leads to a poor generalization bound. This motivates us to construct smooth surrogate loss functions to improve adversarial generalization. Inspired by the work of (Zhang & Luo, 2020), we use the Moreau envelope function to smooth the adversarial loss. Let
2 K(w, 2) hww; 2) 2 I| u11
(5.1)
If is t-weakly convex, we can choose p I to insure that K(w, 2) strongly convex with respect to In the that h is convex, we only need p > O. We define the Moreau envelope function:
M(;
HKww,ur u) min K K(w, 5) = min weW
(5.2)
wEW #ES
ww;; arg min Kw,,u:) weW
(5.3)
Then, (w; is smooth function. Formally, we state the theoretical results as follows.
Lemma 5.1. Assume that h is I-weakly convex. Let l. Then, M Muu; S) satisfies
1. min, M(;; S) has the same global solutions min (s(w).
The gradient of M M(; S) V.M = p(u w(w: S)).
M (u; S) is pl (p 1)- weaklyy convex.
4. M (w; S) is (2p² pl) (p gragdeie Lipxchitz continuous.
M (w; 8) has bounded gradient norm
The proof of Lemma A.1 We focus on the case where h is convex in the main text. Then, Lemma 5.1.3 and 5.1.4 reduce to (u; S) is convex and 2p-gradient Lipschitz. Lemma 5.1 is stated in general (-weakly convex cases for further theoretical studies. Since M (u; S) has the same global solutions Rs(w), we can do adversarial training using this smooth objective M S). A natural way is to perform gradient descent to (u; S). By Lemma 5.1 the estimate of the gradient requires the estimate of the solution of the minimization problem mnn,. K(w, u; S). Depending on whether we solve the subproblems exactly not, have the exact approach and inexact approach.
Remark:
due to (Rockafellar 1976) and also provided Appendix
(.1.3.5.1.3
5

---

Under review as a conference paper at ICLR 2023
5.2 EXACT APPROACH
We first consider the exact approach, which is the gradient descent to (u; S). Theorem 5.1. Assume h is convex, L-Lipschitz function. Suppose run GD the smoothed surrogate adversarial loss M (w; S) defined in Eq. (5.2) with fixed stepsize S 1/ V for T 4p² steps. Then, the optimization and generalization gap satisfies
21,Ta 2016
Eopt S 0(1/To) and Egen
(5.4)
n
Remark: Thm. 5.1 not obtained from the work of Hardt al.
Notice that
M(; S)
min wEW n2
((w, +
n Σ
min K(w, u; 2).
wEW
min, (u; S) is not finite sum problem. However, the analysis in (Hardt et al. 2016) can only be applied to finite sum problems. Thm. 5.1 requires a different proof. In summary, there are two steps: 1) Build the recursion from l|us u's:|l to ||us u || 2) Unwind the recursion. The main challenge comes from the first step. To this end, develop new enror bound and different decomposition to build the recursion. Details are deferred to Appendix A.3] Thm. [.. is
first main result. It shows that the exact approach achieves the minimax lower bounds of the generalization gap. The extension to weakly-convex cases is provided in Appendix
However, the exact approach requires the exact minimization of K(w, u; 5), which is sometimes computationally intractable. To address this issue, we consider the inexact approach below.
5.3 THE INEXACT APPROACH
The inexact approach is estimate V (u: S) by inexactly solving min K(w, u, S). To this aim, we perform multiple steps of SGD to the subproblem min K (w, u; S), attaining an estimate (u)) of the true w(u), and then use (u)) estimate V.M ();
Algo Algorithm Smoothed-SGiDMax
1: Initialize w w
2: Choose stepsize cf > 0 and 04 0;
3: for 1. 0, 2,,,.,,, do
4: Let w/ w":
5: for s 0, 1, 2, N do
6:
Draw a sample 2 from S uniformly; w
7:
(w: et V K 2();;
8:
end for
9:
w(+1 w/y:
(+1 u² + +oppputt u²);
11: end for
In Step in Alg. we run SGD on K(w, S) wet to find solution given u. step 10, we run GD on K(w, S) w.rt u. To provide the upper bounds of the optimization gap and generalization gap of Alg. 1 we need the following Lemma for the inner optimization.
Lemma 5.1. Given and u', suppose we run SGD on K(w, u',S) w.rl. w with stepsize dg s 1/(p- for N steps. w'y is approximately the minimizer with an error C7/ Cg/N,E i.e.
Ellw'y w( Cf
N
where C (LLL+DDw//p--
In convex case, i.e., = O, we have C1 = L/p Dw Lemma 5.1 provides the optimization error of the inner loop. In words, if smoothed loss [w;; S). Below we provide the training loss and uniform stability of Smoothed- SGDmax with sufficient steps for the inner loop.
the inner loop for sufficient steps, can approximate the

---

Under review as a conference paper at ICLR 2023
Theorem 5.2 (training loss of Smoothed-SGDDaaz Suppose h is convex and L-Lipschitz In Alg. if we choose inner stepsize c¹, S 1/ps. number of steps in inner loop N T, outer stepsize 1/VTT T Ap², the optimization gap satisfies
1 u 12 + 2pC2 Dw + DDW) C2 Ta
Eopt S
(5.5)
2Ta
where C2 = 1100 u² 11 DW + (L + pDww)
Theorem 5.3 (Generalization bound of Mmoothed-SGDDaat Assume that h is convex and L- Lipschitz. Alg. [ if we choose inner stepsize c² I 1/ps, number of steps inner loop N n? outer stepsize oa, S 1/VT. T 2 Av², the generulization gap satisfies
(2Cip
2L n
C3 n
Egen S L
Σ a2
04
(5.6)
where C3 L(AL 2pDw).
Thm. 5.2 and 5.3 are the main results of our paper. For fixed stepsize 04 = or, it shows that Alg. has training loss (1)TTa) and has optimal generalization bound in O(Ta/n).
Interpretation of Number of Steps. In practice, if batch size 1 and go through the whole dataset in each epoch, T can be viewed as the number of epochs, and N can be viewed as the number of samples. Let Ta V C2n/Cs. we obtain the optimal excess risk with respect to 7 and o, ie..
Eopt + Egen 2
CaCa
5.4
FURTHER COMPARISON WITH EXISTING ALGORITIIMS
In Alg. Step 7 is just to run SGD on K(w, u; 2) = h(w; 2) pl u22//2 instead of h(w; z). The additional term can be viewed averaging step similar to stochastic weight averaging (SWA). We compare Mmoothed-SGDDian with some existing algorithms in detail. The summary of the comparison is provided in Table 3 We can see that only Smoothed-SGDmin can reduce the generalization error floor.
regularization term similar to weight decay. Step 10 is model
Comparison of SGDmax, weight decay, proximal update, stochastic weight averaging, and Smoothed-SGDmaxx Only Smoothed-SGDmax reduces the error floor in the generalization bound.
Table 3:
Operation on w
Operation on u No eтror floor
SGDmax
Minimize (s(w)
No operation Set
X
Weight decay
Minimize w on K (w, 5)
X
Proximal update
Minimize w on (s(w)
Update rule in Eq. 5.8
X
SWA
Minimize w on (s(w)
Minimize a on K(w, uE; 5)
X
SoootthedSSGDmas
Minimize w on K ((w, u;; S)
Minimize u on K(w, Wz; S)
Weight Decay. Weight decay (WD) is to add a l regularization to the empirical loss. The loss function with WD is h(w; 2) + p|l 12/2. Therefore, we replace Step 10 by u 0 in Alg. ] Emoothed-SGDmal reduces to a simple weight decay regularization technique. Following the anal- ysis in Table 2 it is easy to see that adversarial training with weight decay incurs generalization bound in
Egen S 2L(L + L/n)Ta,
(5.7)
where the step size a < 1/(Lw p). Therefore, weight decay is not guaranteed to reduce the additional sample size-independent term.
Proximal Update.
The proximal update to apply an update rule,
(w) = arg min w|l w||2 + af()),
(5.8)

---

Under review as a conference paper at ICLR 2023
after stochastic gradient update. Both proximal update and Smoothed-SGDmax the Moreau envelope function, but the algorithms are different. The stability analysis of the proximal update is given in (Hardt et al. 2016), Def. 4.5 and Lemma 4.6. It is proved that the proximal update is 1-expansive if / is convex. Therefore, the generalization bound of the proximal update is no larger than that of SGD. In non-smooth cases, SGD incurs an error floor. The proximal update is not guaranteed to eliminate the еттоr floor.
Stochastic Weight Averaging. Stochastic weight averaging suggests using the weighted average of the iterates rather than the final one for inference. The update rules of SWA is u u = 7 r'u² + (1 r) In the work of (Xiao et al. 2022), they provide a generalization bound for SWA in the case that is the average of the iterates, which is equivalent to using the step size u = (t 1)/t. The generalization bound in this case is
Egen (SW A) S (LLge 2L /n)Ta.
(5.9)
The sample size- intepeendeeen term is one-half of the one without SWA. However, the additional term still unavoidable in the analysis. SWA is still not guaranteed to achieve the minimax lower bound in this analysis.
Optimal Generalization Bound of SWA in our Regime. In Alg. if denote 7' 1 a' Step 10 can be view as a weight averaging step. In Thm. 5.3 it required that a' v 1 1/2p. Then, r' = (1 a²p) 2 1/2. Therefore, by fixing a'p to be constant and letting p + O, our proposed algorithm is reduced to SWA. In other words, our proposed algorithm can be viewed as general form of SWA. Also, we provide an optimal generalization bound of SWA in the regime that E [1/2, 1] and p + O.
6 EXPERIMENTS
Training Procedure of Smoothed-SGDmax. To have a first glance of how Smoothed-SGD -maxxxxxx mitigates robust overfitting, consider the experiments on CIFAR-10, CIFAR-100, and SVHN to plot the training procedure.
lightweight model, PreActResNet-18,
Training Settings. For the attack algorithms, we use loo PGD-10 (Madry al. 2017 8/255. The step size is set to be e/4. For adversarial training. we use piece-wise learning rates, which equal to 0.1, 0.01, 0.001 for epochs to 100, 101 to 150, and 151 200, respectively. For Smoothed-SGDman we keep the piece-wist wise learning rate (for the choice of c in Alg. for com- parison. Because of the similarity of & regularization term of weight decay and the proximal term in ((w, u; =), we set = 5 x 10 which is a common choice of weight decay. The step size or of updating u is set be 50, then 1 opp 0.995.
labust accursyy swin
Rebust acursey, 4far1200
Trankng Jober, Acc 500
Pobcol Seeetred5O0ees
677
Traiiigg Ribul AOLAT
1.2
Test Mot.Jobrr...c... ACLAT
Traiting /abuttttttte Smeetre 550me
0.1
Eports
(a)
(b)
Figure 2: Robust test accuracy of adversarial training and Smoothed -Ganeexxd--aaxxxxmmmm on SVHN and CFAR- 100.
The training procedure of the experiments CIFAR-IO is already provided in Introduction, Fig. The experiments on SVHN and CIFAR- are provided in Fig. [ For adversarial training, the robust test accuracy starts to decrease at around the 100th epoch, which is called robust overfitting the robust overfitting issue is much milder. These ex-
(Rice et al.] 2020). Using Emmotth-SGDman periments verify the generalization bounds. The bound of Smoothed-SGDDmax (which is O(T//n)) is much better than the bound of adversarial training (O + Ta/n)).
8

---

Under review as a conference paper at ICLR 2023
Sample Complexity. Secondly, we study the sample complexity provided in Thm. 5.3 We use Wide-ResNet-25 x 10 with Swish activation function for better test accuracy instead of ResNet- 18. The training setting mainly follows the work of (Gowal et al. 2020). We consider two losses, adversarial loss (Madry et al. 2017) and TRADES loss (Zhang et al. (020) for the choice of h (w; =). The total number of epochs is 400. Other training settings are similar to the experiments ResNet- 18.
hobust nst Accurad using Smoothed S0Dmax CIFAh 10
Adrursafia Generaliation Cap Using Smoothed ScDmax CIFRR11
0.60
Adverarat Las
0.52
Aleravil ineetted kibona Lew Srythee-2CDmee Adenarll Law, Zamniin
0.50
(b)
Figure 3: Robust test accuracy and generalization gap in the experiments of training CIFAR-10 using Smoothed-SGDmax.
Adversarial Generalization Gap. CIFAR-10 only contains 50K training samples. We adopt the pseudo-label data introduced in (Carmon et al. 2019 to study the sample complexity. Increasing the percentage of pseudo-label data is an approximation of increasing the training data. In Fig. 3 we show the robust test accuracy (a) and adversarial generalization gap (b). The results are consistent with the theorem that Smoothed-SGiin -mDxxxx reduces a term in the generalization bounds.
Table 4: Robust test accuracy of our proposed algorithm. 8/255. Model: Wede x 10 with Swish activation function. Training data: Labeled to unlabeled data ratio: 3:7. Dataset
Loss
Algorithm
Clean
AutoAttack
SGDmax
90.93+0.259
58.41+0.25%
AT Loss
Smooth-SGDmax
91.51+0.20%
59. 59.1440.11 18%
CIFAR-10
SGDmax
88.36%
59.45%
TRADES Loss
SmoothhSGDDmin
85,33+0. 13%
62.41+0.1194 11%
SGDmax
59.38%
26.07%
CIFAR-100 TRADES Loss
Smooth-SGDmax
59.25+0.22%%
28.54
In Table 4 we provide the robust test performance of our proposed algorithms. The baseline per- formance CIFAR-10 reported in (Gowal al.] 2020). We can that the performance of our proposed algorithms is comparable in the same settings used in (Gowal et al. 2020). Notice that the state-of-the-art performance of adversarial robustness obtained using large models (e.g., WideResNet-100 x 16) and DDPM-generated data (Rebutti et al. (021). We do not have enough resources run large models.
CONCLUSION
In this paper, we study question: can we design an algorithm eliminate the generalization error floor of the adversarial generalization gap? By using tools from Moreau envelopes, we consider a smoothed version of SGDmax. We prove that has the same convergence guarantee as SGDmax and attains the minimax lower bound of the generalization gap in non-smooth loss minimization. Most importantly, Smoothed-SGDmin can eliminate the generalization error floor. We hope our work can lead to better understanding of adversarial machine learning theory.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. 10190, 2020.
Idan Attias, Arych Kontorovich, and Yishay Mansour. Improved generalization bounds for adver- sarially robust learning. 2021.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):46334822 2002.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. arXiv preprint arXiv:2006.06914, 2020.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-522 526, 2002.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium security and privacy (sp), pp. 39-57. IEFE, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pp. 11190-11 1201, 2019.
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26, 2017.
Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Robust overfitting may be mitigated by properly learned smoothening. In International Conference on Learning Representations, 2021. URL https:ttt////c.t..ttt httpps:://perreeeeer..cco
httpt//ooommmmmi//moeeeem q2zy5ur2w2
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 1804.0161, 2018
Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially ro- bust gaussian classification. In International Conference on Machine Learning, pp. 2345-2355. PMLR, 2020.
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient- based minimax learners. In International Conference on Machine Learning, pp. 3174-3185. PMLR, 2021.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. arXiv preprint arXhv:1812.09855) 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable al- gorithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279, PMLR, 2019.
Ian J Goodfellow, Jonathon Shlens. and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint crXiv:1412.6577 2014.
Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Uncovering the limits of adversarial training against norm-bounded adversarial examples. arXiv preprint arXiv:2010.03593 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
10

---

Under review as a conference paper at ICLR 2023
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wil- son. Averaging weights leads to wider optima and better generalization. arXiv preprint 0rXYv:18803.055072200 2018.
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani. Precise tradeoffs in adversarial training for linear regression. In Conference on Learning Theory, pp. 2034-2078. PMLR, 2020.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint
wrXiv:1810.09511 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:/706.0608. 2017.
Omar Montasser, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly Iearnable, but only improperly. Conference on Learning Theory, pp. 2512-2530. PMLR, 2019.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 1954) 1609, 2009.
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Sylvestre-Alvise Rebuffi, Sven Gowal, Dan A Calian, Florian Stimberg, Olivia Wiles, and Tim- othy Mann. Fixing data augmentation improve adversarial robustness. arXiv preprint arXiv:2103.01946, 2021.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference Machine Learning, pp. 8093-8104. PMLR, 2020.
Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM j. control optim., 14(5):877-898, August 1976.
William H Rogers and Terry J Wagner. A finite sample distribution free performance bound for local discrimination rules. The Annals of Statistics, pp. 306-514, 1978.
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifiable distributional robustness with principled adversarial training. arXiv preprini arXiv: 10571, 2017.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Asymptotic behavior of adversarial training binary classification. arXiv preprint arXiv:2010.13275: 2020.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Dongxian Wu, Shu-Tao Xia, and Yisen Wang. Adversarial weight perturbation helps robust gener- alization. arXiv preprint arXiv:2004. N008:2004000884. 2020.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun. Jue Wang, and Zhi-quan Luo. Stability analysis and gener- alization bounds of adversarial training. In Thirty-Sixti Conference on Neural Information Pro- cessing Systems, 2022. URL https::: /ttpp//:///ppneiii..m.m htt.eeeww.eeeeeoeeeeeeeeeeeeeeee htt.aa/rrreeeetteeoooooomaaaaa-a
Yue Xing, Qifan Song, and Guang Cheng. On the generalization properties adversarial training. In International Conference on Artificial Intelligence and Statistics, pp. 505-513, PMLR, 2021a.

---

Under review as a conference paper at ICLR 2023
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training.
In Thirty-Fifth Conference on Neural Information Processing Systems, 2021b. URL https:
Yue Xing, Ruizhi Zhang, and Guang Cheng. Adversarially robust estimate and risk analysis in linear regression. In International Conference on Artificial Intelligence and Statistics, pp. 514- 522. PMLR, 2021c.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. In International Conference Machine Learning, pp. 7085-7094, PMLR, 2019.
Chaojian Yu, Bo Han, Li Shen, Jun Yu, Chen Gong, Mingming Gong, and Tongliang Liu. Under- standing robust overfitting of adversarial training and beyond. In International Conference Machine Learning, pp. 25595-25610. PMLR, 2022.
Chiyuan Zhang, Samy Bengio. Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115, 2021.
Jiawei Zhang and Zhi-Quar Luo. A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM Journal on Optimization, 30(3):227--233 2020.
Yonggang Zhang, Xinmei Tian, Ya Li, Xinchao Wang, and Dacheng Tao. Principal component adversarial example. IEEE Transactions Image Processing, 44804-4815, 2020.
12

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREMS
A. PROOF OF PROPOSITION 4.1
The proof adopted from the proof of minimax lower bound of optimization error from the work of (Chen et al. 2018). We define the excess risk as (D(w) min Rp(w). A minimax lower bound the excess risk for the function class is given in (Nemirovskij & Yudin 1983):
LDw Cayn'
min max BS-D= (Ro(w) min Ro(w))
(A.1)
weW
where C4 is universal constant. By the excess risk decomposition, we have ES-Dr (S>DD((D(w)) min
weW RD(w)] S (wpe(w) + Eope
(A.2)
Let A E A and w the algorithm output of A, we have Eapt (
(((()s(T))
Then,
LDw
1 1
min max Egen(vu) (w 220 Ω AEA D
(A.3)
vn
s(T)
Complete the square, we have
LDw Vn
LDW v s(T)
La s(T)(TT)
-
(A.4)
sTT)
(T)
2n
4n
LDw (T)) Therefore,
Since sT) too to0, can choose T s.t.
is close
Vs(T)
there exists T,
(5(((()) (())
min max Egen 2 AEA D
(A.5)
A.2 PROOF OF LEMMA 5.1
To simplify the notation, we use M (u) as a short hand notation of M (u: S). Similar to h(w), K(u), and w(u).
1. Let w E arg min Rsw). We have
Rs(w*) K(w", u S)) 2 ((w(u), u w², (u w²))
Then, the equality holds. Therefore, min, M S).
w" is the optimal solution of both min.. Rs(w) and
Since K(w, u) is (p ()strooglly convex function, w(u) is unique. Then
M(u) ((w(w)) 2 (w(()) wll².
By taking the derivative of (u) with respect to u, we have
1ww(u))
T
V (w)))((((w))++ + Dwluu)
-1] 11 -(((()) u). (A.6)
(u)
Du
Iu
(w) du
(ntu) + p(w(u) u)) - p(u -w(u) (A.7)
Since wu) is the optimal solution of K [[w, u), have
V (w(w) ((w(u), u) V ve(w))(((u)) + p(w(u) - u) 0.
(A.8)
Therefore, the first term in A.7 is equal to zero. We have V.M(u) p(u w((u).
13

---

Under review as a conference paper at ICLR 2023
3. In Eq. (A.8). take the derivatives with respect both sides, have (ww(w)
@w(())
V (u)((w) + pl
-) = =.
(A.9)
du
du
Organizing the terms, we have
Owr(u) T (Vih(w) + pf) = pl.
(A.10)
du
Since h(w) is l-wekkly convex, Vih + pl is positive definite. Then,
(2)(2)
(A.11)
8u
p p-1
Then,
M2,(() = 0
@dw(u)
8u p(u u(u))] p(u-m(u))] p(I
) p(1
p I
(A.12)
du
Therefore, (u) is a pl/(1 1)- wwekky convex function. By Eq. (A.II). we have
[VM(u (w2)) pl|u1 w(u)) u2 w(u2))l S p(1 + _ - 1| -
u2ll.
(A.13)
Therefore, M (w; S) is (2p² - pplpppppppppppppppppppppp ()-gradient Lipschitz continuous.
By Eq. A.8).
Mu)ll = Ip( w()))ll = v.h(w)ll L.
(A.14)
L
A.3 PROOF OF THM. 5.1
The training loss is standard result of runing GD on smooth objective function.
We focus on the proof of generalization bounds. Thm. 5.1 al. 2016). Notice that
is not obtained from the work of (Hardt
M(u; S) = min K(w, u; 2)
Σ
min K (ww u; z).
weW n
wEW
ZES
2ES
min, (u; 5) is not a finite sum problem. The analysis in (Hardt et al. 2016) can only be applied finite sum problems. Thm. 5.1 requires different proof. In summary, there are two steps:
1. Build the recursion from |luss - u's:ll to I| - ugg 1++1p ||:
2. Unwind the recursion.
The main challenge comes from the first step, since the problem not in the form of finite sum To this end, we develop new error bound and different decomposition. We first introduce the following error bound.
Lemma A.1. In weakly-conven case. for neighbouring S and S', we have [[w[u S) ww; S' S 2L/ f)).
Proof. By the (p- 1)- ()-strongly convexity of K (w, u; S), we have (p [)][ S) w(u; S')ll
A K(w(u; 5), u; 8) VK(w(u; S') u; S)
V KK(((;;
VK(w(u u²), u S')
(h(w(u; S'), =1 +
= Vh(w(u; x)]l
Vh(w(u V)) S'),011
2L
14

---

Under review as a conference paper at ICLR 2023
where the second inequality is due to the definition of K K(w, u; S), the third one is due to the first- order optimally condition, and the last inequality is because of the bounded gradient of h(w; 2). C
Next, we move to the proof of Thm.
Step
lug [+1
1+11
Jus ugg 04 (M - S'))l
|uug ug. ag (VM (M 5)) + az ( (M
Ju's ugg/ || + a VM (u
|lus ugrl || a a'pllu's u'g w(u 5) (()
2La
- |lul u +
n2
where the second inequality is due to the non-expansive property of convex function, the last in- equality due Lemma A.
Step Unwinding the recursion, we have
||u5 u 5 Ei=1
2L ET
71
A.4 PROOF OF LEMMA 5.1
Lemma 5.1 can be obtained from classical strong-conven optimization results. Since
K,, u; =)1l V hww 2) p(w u) L pDw,
K(w, u; 2) has bounded gradient LK + pDw. By (eemrovvski et al.) 2009), running SGD on K (w, u; 8) with stepsize C, 1/s(p 1) iccurs an optimization error in
El|wx - ww)ll s Cf
where C1 = (Dw+pDDw)/
A.5 PROOF OF THM.
5.2
Proof. Let A 2 11 u² 1|2 and a++1 = - 1²1122
Act1
2 | +1 122
Iu' as V. K (w u'; u²1
1
A, + - L -a ",,KK''''' K(''. ; u² u²)
2
= A, + 07 o ar (V M. (u': 5) u' =²)
2
+a, (a VwK(w' w² S), u² u²
By taking the expectation on both sides and Rearranging the terms, have
(rE()(u')) MM("))
$ at - 0++1 + _ + M(A:s) (f
u): -2) u²) (A.15)
15

---

Under review as a conference paper at ICLR 2023
Since
E(V ((, V (,,K
ut; S), u² - u²)
IV M(, V. (uK( u²; ;)][Blluu u²)
PC Dw
VN
Eq. A.15 becomes
ag M - M(n')]
OspC, Dw
x at a-1 + 2 g0iLk +
VN
Let N 2 T. Take the summation over t. We obtain that
( M("")
E appCi Dw VT
a0 L
There exists S T, such that
40 + 1 ΣE= a T. +
E. app.DD
B[M(w') M(w))]
VT
Σim at
Considering constant step a S 1/VT, we have a S 1//Ta and T 1. Therefore,
200 + Ta? + 22a 1PC1Dw
- -
2Ta
1/00 u² u²112+ T.3 2pCrDup Dw
2Ta
C2 Ta
Since M(u; S) and (w) have the same global solutions, we can use both of them to measure the optimization error. Above is the optimization enror defined in Mu; S). Below we provide the optimization error defined in Rs(w).
C2 Ta
E ([ss(w(n') Rs(w") s B[M(w') M(n')
Notice that the choices of algorithm output are slightly different. Therefore, we have
C2
Eopt I Ta
where C2 = 1/u00 w/1///2 DD
A.6 PROOF OF THM.
5.3
Proof. We decompose ||ug-1
Ugg
[+1
||
as
El 1+1
u 1+1|
Ellu's at v. (o.K(ww,ss. u'; uly. + at ugr S')
u a, V. (u': S) u'g. + + V.. S')ll
20, V. (w s: U/gi 8) (.M(u S)
2La; + 20tpElluby - w(u') ||
Ellu's uلو, ||
E u u/-11l + 2La + 200p
C1
VN
16

---

Under review as a conference paper at ICLR 2023
Let N 2 n². Unwind the recursion and let u² be the output of the algorithm. We have
Egen
LEI u II
L(2L + 2C1P) E az
C3 Σi= att
n
If we choose w(u²) be the algorithm output, have
Egen I
LEIlw(u (u:;
w(u
LB
M uss
-
1 A
(us; S'))
p
p
21.²
LBIlu5 - u +
np
[[2T 2C1p)
Et= 0t
2T,
n
np
-t=1 at
(A.16)
where the first equality is due to (M; = p(u w(u)), the second inequality is due to the non-expansive propertiy of M (u; S).
B WEAKLY-CONVEX CASES
Our main result can be extended to weakly convex cases.
weakly-convex, I.-Lipschitz function. Suppose we run GD on the smoothed surrogate adversarial loss Mw:; 5) defined in Eq. (5.2) with diminishing stepsize s 1)p(2222p - pl)t for steps. Then, the generalization gap satisfies
Theorem B.1. Assume
Ege o
2L2T
(B.1)
(2p l)n
In this case, the bound also does not contain a non-vanishing term. The proof based on the error bound (Lemma and the decomposition in the proof of Thm. 5.1
Proof:
Step 1.
||ust ++1 us:
1+1
Iluss u 04 (VM( VM(ul:; S'))ll
Iluss u/s. 0z V (1 VM("{;; + o.l V VM(us S)
llus w/s || a. (M.g [M + + [V
VM(uly;
(1 + 3l1 u + + ( a (
(B.2)
where the first and second incqualities are due to triangular inequality. The last inequality is due to the gradient Lipschitz of (u; 8) and (2p² pl)/(p (p l). Then,
a' M (M S)
a a'pllus- - u'y. w(u'g, S) + w(u S') 2Lpor
(B.3)
(p l)n'
where the first inequality is due to the form of V (M; S), the last equality is due to Lemma A.1
17

---

Under review as a conference paper at ICLR 2023
Combining Eq. (B.2) and (B.)) have
luus u
2Lpor
s (1 + 0+,3)lluss - - + (p- l)m
(B.4)
Step 2.
Let ar (p (p-1)/(2p) pl)t.
llus - usg
1+1
2L
< exp(1/4)llu5 - -''rll +
(B.5)
(2p 1)m
Then, following the proof, for example, of Xiao et (2022)
we have
Egen ( (2p - 1)m
2
18


Reviews:
[{"review_id": "yWUpddtAbW", "reviewer": "Reviewer_Kcyd", "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": "The paper studies the generalization problem in adversarial training. Specifically, it presents a minimax lower bound of the generalization gap, proposes Smoothed-SGDMax that achieves the bound. Connection to stochastic weight averaging (SWA) is also presented. ", "summary_of_the_review": "Overall the paper is mostly well written with novel results towards better understanding of an important problem (robust overfitting) in deep learning, although the results are built on strong assumptions, rather distant from practice.", "strength_and_weaknesses": "**Strength**\n\n* Despite robust overfitting has been observed for quite some time and efforts have been spent to understand its root cause, the problem remain mostly open. This paper is a new effort towards solving this important problem, namely, understanding the generalization behaviour of the SGDMax algorithm in adversarial training.\n\n* The paper provides novel perspectives (a lower bound) in characterizing the generalization gap with respect to the optimization gap. The proposed Smoothed-SGD algorithm is intuitively sensible, theoretically justified and empirically validated. \n\n* The theoretical analysis appears solid. \n\n** Weakness **\n\n* Requiring the functions in class ${\\cal H}$ to be convex significantly limits the applicability of the developed results. \n* Comparing with SGDMax, Smoothed-SGDMax does show improved generalization. However even with Smoothed-SGDMax, there still appears a significant gap between training and test robust accuracies (e.g., green and red curves in Figure 1). Such a gap appears much larger than its counter-part in (regular) training.  Then it seems that non-smoothness can not fully explain robust overfitting.   \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e0PFhuRjf_N", "reviewer": "Reviewer_xxrH", "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": "This paper studied the generalization performance of adversarial training from the stability perspective. They first derived the minimax lower bound of generalization gap for convex Lipschitz functions, which identifies the gap compared to existing generalization results of SGDmax; then authors proposed Smoothed-SGDmax which shares the same convergence guarantee while achieves the aforementioned (vanishing) minimax lower bound, i.e., fix the gap.", "summary_of_the_review": "Generally I don't have immediate questions to ask.\n\nSome typos:\n1. Theorem 4.2, $\\alpha_t$ and $\\alpha$, do you suggest that you are always using constant stepsize $\\alpha_t\\equiv\\alpha$?", "strength_and_weaknesses": "Strength:\n1. The paper is well-written and the flow is clear\n2. The proposed algorithm successfully overcomes the nonvanishing generalization errors in existing SGDmax results, while still share the same convergence guarantee\n\nWeakness:\n1. The tools in algorithm building are not that novel.\n2. The problem setting is the convex regime, which is a bit restricted (to be a bit picky)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Yxy-A46_Qse", "reviewer": "Reviewer_rzkp", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors investigate the generalization error in optimizing the expected adversarial loss. They utilize the generalization-optimization decomposition and techniques from stability analyses to reveal the minimax optimal optimization algorithm for the adversarial loss. For the lower bound, they show that any algorithm with the convergence rate $s(T)$ suffers from the generalization gap at least $s(T)/n$, where n is the sample size. For the upper bound, they develop an optimization algorithm employing the Moreau envelope to smoothen the adversarial loss function so that the SGD is stabilized. They show that it achieves the optimal generalization gap with $s(T)=T$. Also, they analyzed the optimization algorithm with the approximated Moreau envelope, which gives the same optimal rate. The empirical evaluations demonstrate that their algorithm can avoid robust overfitting.\n", "summary_of_the_review": "The minimax optimality of the adversarial loss minimization is a well-motivated and interesting direction. However, I found some issues or low originality in most results. Also, while their main idea is to employ the Moreau envelope, it is not original, as Hardt et al. discuss it as a way to control stability. I thus recommend the rejection.", "strength_and_weaknesses": "Strength:\n- The minimax optimality in the adversarial loss minimization is crucial for understanding adversarial robustness.\n- The inexact version of the proposed algorithm is novel.\nWeakness:\n- The minimax lower bound result has issues in its originality and correctness.\n- The exact version of their algorithm has an originality issue.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-ZQZtdKsGx9", "reviewer": "Reviewer_9aTN", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This work studies the effect of using adversarially robust on generalization\nerror.  In particular they show that the generalization error achieved by\nSGDmax contains a constant term that does not tend to 0 as the sample size\nincreases.  They show that they can remove this constant term in the error by\nusing a smooth variant of SGDmax.\n\n", "summary_of_the_review": "Overall, I found the paper not well-written and I believe that it would benefit\na lot by careful proofreading. I do not think that in its current state this\nwork is ready for publication.   Perhaps after a revision, the contributions of\nthis would also become clearer.  Given the fact that the paper is not\nwell-written and the contributions do not seem very exciting, I am currently\ninclined towards rejection but I am willing to reconsider if the authors and/or\nother reviewers can prove otherwise.", "strength_and_weaknesses": "Strengths\n\n1. The paper studies the important and well-motivated problem of adversarial\ntraining and proposes a new method that improves generalization.\n\nWeaknesses\n\n1. The paper is hard to parse and follow and there are numerous typos and\ninconsistencies in the notation.  One of the main results of this work (Theorem\n4.1) seems to be a direct corollary of prior work but still the proof provided\nin Appendix A.1 is hard to follow.\n\n2. I did not find the Smoothed-SGDMax method proposed by the authors\nparticularly novel since approximating non-smooth terms with their\ncorresponding Moreau envelopes is pretty standard.\n\n\nTypos and other Issues\n\nTheorem 4.2 does not show that SGDmax does not achieve the minimax lower bound.\nIt only gives an upper bound for the generalization error of SGD that does\nnot match the lower bound of Theorem 4.1.\n\nPage 2, next to Figure 1. \"By contrast, Our approach\"\n\nPage 3, First paragraph of Related Work. \"This has led to a series of work aimed at training...\"\n\nPage 13, Proof of Theorem 4.1. \"Where $C_4$ is a universal constant\". There is no constant $C_4$ in the expression (A.2).\n\nPage 13, Proof of Lemma 5.1. The sentence in Element 1 of the proof does not parse.\n\nPage 13, \"Then, take the derivative of $M(u)$ with respect to $u$, we have\"\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject