Adversarial Self-Training Improves Robustness and Generalization for Gradual Domain Adaptation
Authors: Lianghe Shi
Weiwei Liu
Venue: NeurIPS 2023 poster (2023)
Keywords: learning theory

Abstract: Gradual Domain Adaptation (GDA), in which the learner is provided with additional intermediate domains, has been theoretically and empirically studied in many contexts. Despite its vital role in security-critical scenarios, the adversarial robustness of the GDA model remains unexplored. In this paper, we adopt the effective gradual self-training method and replace vanilla self-training with adversarial self-training (AST). AST first predicts labels on the unlabeled data and then adversarially trains the model on the pseudo-labeled distribution. Intriguingly, we find that gradual AST improves not only adversarial accuracy but also clean accuracy on the target domain. We reveal that this is because adversarial training (AT) performs better than standard training when the pseudo-labels contain a portion of incorrect labels. Accordingly, we first present the generalization error bounds for gradual AST in a multiclass classification setting. We then use the optimal value of the Subset Sum Problem to bridge the standard error on a real distribution and the adversarial error on a pseudo-labeled distribution. The result indicates that AT may obtain a tighter bound than standard training on data with incorrect pseudo-labels. We further present an example of a conditional Gaussian distribution to provide more insights into why gradual AST can improve the clean accuracy for GDA.

Adversarial Self-Training Improves Robustness and Generalization for Gradual Domain Adaptation
Lianghe Shi
Weiwei Liu"
School of Computer Science, Wuhan University National Engineering Research Center for Multimedia Software, Wuhan University Institute of Artificial Intelligence, Wuhan University Hubei Key Laboratory of Multimedia and Network Communication Engineering, Wuhan University
Abstract
Gradual Domain Adaptation (GDA), in which the learner is provided with ad- ditional intermediate domains, has been theoretically and empirically studied many contexts. Despite its vital role in security scenarios, the adversarial robustness of the GDA model remains unexplored. In this paper, we adopt the effective gradual self-training method and replace vanilla self-training with adver- sarial self-training (AST). AST first predicts labels on the unlabeled data and then adversarially trains the model on the pseudo-labeled distribution. Intriguingly, we find that gradual AST improves not only adversarial accuracy but also clean accu- racy on the target domain. We reveal that this is because adversarial training (AT) performs better than standard training when the pscudo-labels contain portion of incorrect labels. Accordingly, we first present the generalization error bounds for gradual AST in a multiclass classification setting. We then use the optimal value of the Subset Sum Problem bridge the standard error on a real distribution and the adversarial error on pseudo-labeled distribution. The result indicates that AT may obtain tighter bound than standard training on data with incorrect pseudo-labels, We further present example of conditional Gaussian distribution to provide more insights into why gradual AST can improve the clean accuracy for GDA.
Introduction
The key assumption of classical machine learning -hat training and test data come from the same
-tha distribution- may not always hold in many real-world applications [5]. A data distribution typically evolves due to changes in conditions: for example, changing weather in vehicle identification [14],
sensor aging in sensor measurement [43, the evolution of road conditions in self-driving [6), etc.
To address this problem, Unsupervised Domain Adaptation (UDA) has been developed to train model that performs well on an unlabeled target domain by leveraging labeled data from similar yet distinct source domain.
53 34 theoretically demonstrate that the generalization error can be controlled by the domain discrepancy. Hence, the domain shift between the source domain and the target domain is expected to be small [15]. However, in some applications, the domain shift is substantial, leading to a sharp drop in the performance of the UDA method (26 Furthermore, since changes in real-world data are more often gradual than abrupt [16], there are many intermediate domains between the source domain and the target domain. To get better solution the gradually shifting data, some recent works have focused on the Gradual Domain Adaptation (GDA) problem, where the learner is additionally provided with unlabeled intermediate domains. The large gap between the source and target domains is then divided up into multiple small shifts between the
Various works in UDA 5
"Correspondence to: Weiwei Liu <liuweiwei863 @maill.ommamm
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

intermediate domains. Recently, the celebrated work [26] proposes gradual self-training, which iteratively applies the self- self-training method to adapt the model along the intermediate domains. Empirically, the gradual self-training method greatly improves the target domain's 's accuracy compared to the traditional direct domain adaptation. After that, remarkable theoretical 455 and algorithmic [ advances have been achieved in GDA. However, the adversarial robustness of the GDA model remains unexplored, despite its vital role in security-critical scenarios. Adversarial robustness refers to the invariance of model to small perturbations of its input [39], while adversarial accuracy refers to model's prediction accuracy on adversarial examples generated by an attacker. Numerous works 49 have shown that very small perturbations, even those imperceptible to humans, can successfully deceive deep neural network (DNN) models, resulting in erroneous predictions.
B3
One popular and effective method of improving robustness is Adversarial Training (AT), which adds adversarial examples to the training data. Due to the lack of labels in the target domain, it difficult to directly generate adversarial examples. Accordingly, this paper replaces self-training with Adversarial Self- Self-Training (AST), which first generates pseudo-labes labels on the unlabeled data and then adversarially trains the model based on these pseudo-labeled data. We conduct comprehensive experiments to validate the effectiveness of gradual AST in Section 3 Compared to the gradual self-training method, the proposed gradual AST method delivers great improvement in adversarial accuracy, from 6. 6.00% to 90.44% on the Rotating MNIST dataset. More interestingly, we find that the clean accuracy of gradual AST on the target domain also increases from 90.06% to 97.15%. This is surprising result, since many prior works [52] 38) demonstrate that AT may hurt generalization; in other words, there is a trade-off between clean accuracy and adversarial accuracy. We then empirically investigate the reason why AST improves clean accuracy in GDA and find that the adversarially trained model has better clean accuracy than the standardly trained model when the generated pseudo-labels contain proportion of incorrect labels.
In Section 4 we present novel generalization error bounds for the proposed gradual AST. The results show that if we have a model f with low adversarial margin loss on the source domain and the distribution shifts slightly, gradual AST can generate a new model f' that is also adversarially robust on the target domain. To explain why gradual AST achieves better clean accuracy than vanilla gradual self-training,
the optimal value of the Subset Sum Problem (3) to bridge the standard error on a real distribution and the adversarial error on a pseudo-labeled distribution. The result shows that AT may yield tighter generalization guarantee than standard training on pseudo-labeled training data. We further provide an example of a conditional Gaussian distribution to illustrate why AT outperforms standard training when a proportion of the labels in the training data are incorrect.
We summarize our contributions as below:
We are the first to apply the AST method in GDA. The proposed gradual AST method can not only improve the adversarial robustness but also the clean accuracy for GDA, which is an appealing and nontrivial result, considering that many prior works demonstrate that adversarial training may hurt generalization.
We empirically explore the reason for the improvements in clean accuracy and find that adversarial training performs better than standard training when the aseudo-labeled training set contains a proportion of incorrect labels.
From the theoretical perspective, we provide the generalization error bounds for gradual AST, which explain why the trained model adversarially robust on the target domain. We provide an error bound and toy example of Gaussian distribution to provide some intuitions for the improvements in clean accuracy.
2 Preliminaries
2.1 Multiclass Classification Learning Framework
Let Z X' y be a measurable instance space, where X' and y' denote the input space and label space, respectively. The input space X' is subset of a d-dimensional space, X' C Rd. In this work, we focus on multiclass classification, and the label space ) is (1,... k). where k is the number of classes. Following the notations used in [5) domain is envisioned as a tuple (P, hp), consisting of a distribution P on input space X' and a labeling function hp : X V. In practice, the true distribution P is unknown to the learner, which has access only to the training data S drawn

---

independent and identically distributed (i.i.d.) according to the true distribution P. We use P to denote the empirical distribution of P according to the training data S. Moreover, following the notations used in [35. we consider the class F [ X - R*} of scoring functions f. We use (a) to indicate the output of f associated with the data point a on the y-th dimension; the output indicates the confidence of the prediction. The label with the largest score is the predicted
label of æ. We use H,= = [(h(+) = arg m-) : f E F} to denote the labeling function yEY
class induced by F. The expected risk and the empirical risk of a classifier h E H. with respect
to a labeling function h on distribution P' are defined as Rp(h, ht) & IE 1 [h(x) o H [x)) and x~P
Rp(h, & E (1(x)) + h'(z)), respectively, where 11 is the indicator function. We use (p)h)
and (h) to abbreviate Ry (h, hr) and R (h, hr) respectively. Furthermore, the 0-1 loss is non- differentiable and cannot be minimized directly. Thus, margin theory for multiclass classification was developed by (25]. that replaces the 0-1 loss with the margin loss. The margin of scoring function I E F for labeled data (I,, is defined PJ (2,3) fz(()) max (zz). And the expected margin
y'
loss of a scoring function f E F with respect to another scoring function f E F on distribution P is defined as R. (J, - E Op pr( (x)), where @,(m) min max 10.111111. m//))
amP
is the ramp loss. Similarly, we use 12 (f) and R/ (f) to abbreviate R2S²) (f. fP) and R2 (f. fP) respectively. Note that Rp(h hp) S R(P) (f, since the 0-1 loss is upper bounded by the margin loss.
2.2 Gradual Domain Adaptation
Under the standard GDA settings 26 45 the learner is sequentially trained T domains with gradual shifts. The corresponding data distributions are Po. Pi..... Pr. where Po is the distribution of the source domain, Pr is the distribution of the target domain, and Pt...., Pr- are the distributions of the intermediate domains. For simplicity, we assume that the number of data points in each domain is the same: namely, each domain / has from P.. denoted as Sy. Recently, [26] proposes gradual self- self-training method for GDA, which successively applies self-training to each of the intermediate domains. The self-training method adapts pre-trained model trained on the previous domain to the current domain using unlabeled data drawn from the current distribution. Specifically, given a pre-trained model f and an unlabeled data set S, the model first predicts the labels of the unlabeled data, then trains f with empirical risk minimization (ERM) over these pseudo-labeles data, i.e.,
of n data drawn i.i.d.
I' = ST arg arg min ( arg min 1 (r, fer
fer P.ES
In gradual self- teff-traaning, the model is first pre-trained the labeled source domain and then succes- sively self-trained on the unlabeled dataset of each of the intermediate domains, i.c.,
Jt = ST L E (1,...,T)
Since the domain shifts between the consecutive domains are assumed to be small [10 26 45 the accuracy of the pscudo-labels is expected to be high at each step. The gradual self-training method aims output final trained classifier f with low expected risk in the target domain.
2.3 Adversarial Self-Training
Given a classifier h and a data point (x,, y). we can generate the corresponding adversarial example (xadu, y) by adversarially perturbing x in a small neighborhood Bx(x) of x, as follows: an arg (ax O py(a', y). In this paper, we focus on the f, adversarial perturbation Bx A {a' E X || 2ll, < e Z 1}. which is referred to as fa-attcck in the AT context and has been widely studied in existing works. Given a vector x E Rd, we define the fg-norm of x as || A (I |=(()l)) 1/9
for q E oo), where Z(() the i-th dimension of a; for q = oo, we detine ||0]|oo A max [o)-- Similar to the definition of the standard risk Rp h²), we 15i5d
3

---

define the adversarial risk on distribution P for any two classifiers h, h¹' as follows: (h h') - E max [2 + 6) * h² (z)]. We also define the expected adversarial margin loss for any two Sr
scoring functions f f on distribution P follows:
RSp (')
E max 6 p5(x + + (x)) z0P S
Although the expected adversarial margin loss is asymmetrical, it satisfies the triangle inequality (see proof in Appendix [. The empirical adversarial risk and the empirical adversarial margin loss can be defined similarly. We use R (f) and R/ (f) abbreviate 12p2 (f) and R (f, SP) respectively. To train a robust model with resistance the adversarial examples, AT aims to find a classifier y that yields the minimal adversarial margin loss, i.e., arg minl?? (f). However, we FEF
cannot adversarially train the model directly on the unlabeled target domain because the conventional AT method requires labeled data. Instead, adapt the self-training method the adversarial self-training (AST) method by generating adversarial examples over the pseudo-labels, i.c.,
S' = AST(1.))
arg -arg min feer
( R(0) (J',)) = arg min- fEr 2.88
1 Σ
max 11 p pp + t (x())))
3 Empirical Exploration
In this section, we propose a gradual AST method to improve adversarial robustness. Surprisingly, we find that the gradual AST improves not only adversarial robustness but also clean accuracy. Our code available at https//giitubbcoo//wwuusooo/////
__GAA]
Datasets. We run experiments on two datasets that are widely used in GDA 26 45 Rotating MNIST is semi-synthetic dataset generated by rotating each MNIST image an angle between 0 and 60 degrees. The 50,00 1,,000 training set images are divided into three parts: a source domain of 5000 images (0-5 degrees), 21 intermediate domains of 42,000 images (5-60 degrees), and a set of validation data. The rotating degree gradually increases along the domain sequence. The 10,000 test set images are rotated by 55-60 degrees, representing the target domain. Portraits [8] a real dataset consisting portraits of American high school students across a century. The model aims to classify gender. The dataset split into a source domain the first 2000 images, seven intermediate domains of the next 14,000 images, and target domain of the next 2000 images.
Methods. The standard gradual self self-training method (26] successively adapts the model to the next domain via self-training. To improve the adversarial robustness, we replace the vanilla self- training with AST. We implement multiple gradual AST methods with different starting domains }} where we begin to use AST, i.e.,
E (O...., T
St), A-T
1S1ŠT-1 STTT
fc f
In particular, if O, then the model is adversarially trained throughout; if T + then the model is standardly trained throughout. Note that T 21 Rotating MNIST and T = Portraits.
Implementation Details. We implement our methods using PyTorch 37 two Nvidia GeForce RTX 3090 Ti GPUs Following (26), we use a 3-layer convolutional network with dropout (0.5) and BatchNorm on the last layer. We use mini-batch stochastic gradient descent (SGD) with momentum 0.9 and weight decay 0.001. The batch size 32 and the learning rate is 0.001. We train the model for 40 epochs in each domain. We set the radius of the bounded perturbation be 0.1 [51] for Rotating MNIST and 0.031 for Portraits. Following [33], we use PGD-20 with a single step size of 0.01 the adversarial attacker.
3.1 Results
The results of the different methods on Rotating MNIST are shown Figure a). The numbers in the abscissa represent different starting domains of various methods. From Figure T(a). we can see that the vanilla gradual self-training method (r = 22) achieves a clean accuracy of 90.06% and adversarial accuracy of 6.00% on the target domain. Notably, the gradual AST method that uses AST

---

throughout (r = 0) improves the adversarial accuracy to 83.54% (+77.54%). More interestingly. we find that the clean accuracy is also slightly improved by 0.53%. Furthermore. the results of varying the starting domains 7 indicate that the performance will be further improved if we use the vanilla self-training method for the first few domains and then use AST from an intermediate domain. We utilize the validation set of the target domain to choose the optimal starting time т. Experimentally, the best choice of starting time for Rotating MNIST is T = 9, which achieves clean accuracy of 96.66% (+6.6%) and adversarial accuracy of 88.86% (+82.86%) We find that AST not only improves adversarial robustness but also clean accuracy with a large step. The results of the different methods Portraits shown in Figure bb). We find similar results to those on Rotating MNIST: the vanilla gradual self-training method (T = 22) achieves a clean accuracy of 82.03% and adversarial accuracy of 40.23%, while the gradual AST method (r = 0) improves the clean accuracy by 2. 7.%% and the adversarial accuracy by 37.40%. We provide more experimental results of different
e, domain numbers, and neural networks in Appendix B
3.2 Why Does Gradual AST Improve Clean Accuracy in GDA?
is widely believed that AT would hurt generalization [22 38 and decrease clean accuracy; thus it is surprising that the proposed gradual AST method improves the clean accuracy of the trained model in the GDA setting. In this section, we speculate on the reasons for this. Recently, some works have revealed that adversarially pre-trained model tends to improve the target model's s accuracy in transfer learning. We accordingly investigate whether the adversarially trained model has better clean accuracy on the next domain and thus generates more accurate pseudo-labels. However, by comparing the gradual AST methods with T = 0 and T = 1 on Rotating MNIST. we find that the model standardly trained on the source domain achieves clean accuracy of 97. 97.30% on the next domain, while the model adversarially trained on the source domain achieves a clean accuracy of 96.95% on the next domain. On the other hand, given that the pseudo-labels contain a small portion of incorrect labels, we wonder whether the ad adversarially trained model has better clean performance than the standardly trained model if trained on such noisy training set. Since we set a fixed random seed for all gradual AST methods with varying starting domains, given To E {0...... 7). the gradual AST method with r = To and that with = To + have the same training processes before domain To and the same pscudo-label set on domain To- The difference between the gradual AST method with T = To and that with 7 = To + 1 is whether we adversarially train the model on the domain TO- We compare the clean accuracy of these two methods on domain in Figure As we can observe from the figure, the adversarially trained model (r = Ta) has higher clean accuracy on domain To than the standardly trained model (r To 1). Note that there are two exceptions in which AT hurts clean performance when the accuracy of pseudo-labels is very high (Tu = 0, 1), which explains why using AST from intermediate domain is better than using AST throughout. Besides, we find that the adversarially trained model predicts more accurate pseudo-labels in the next domain than the standardly trained model when the current training set contains proportion of incorrect labels. We then conclude that AT benefits the clean accuracy of GDA from two perspectives:
39
For the intermediate domains, AT improves the accuracy of the pseudo-labels in the next domain. So the learner can fine-tune the model on a more accurate dataset.
For the target domain, when the pscudo-labels contain a proportion of incorrect labels, the adversarially trained model has higher clean accuracy on the target domain than the standardly trained model.
3.3 Sensitivity of Filtration Ratio Ç
for each step of self-training, we filter out portion of images for which the model's prediction is least confident. In Figure the ratio ( is set to 0.1 as in the work of [26]. We further conduct more experiments with varying Ç. With smaller Ç, more data will be included for the next domain's 's training, but the accuracy of the pseudo-labels will decrease. Due to the page limit, we attach the detailed results of methods with different values of r and ( in Appendix B We find that when Ç decreases, the performance of the standard gradual self-training also decreases. However, the gradual AST method prefers smaller Ç even though more incorrect pseudo-labels are included in the training set. For example, when we set Ç = 0.05, the gradual AST with the optimal starting domain 7 = 9 (chosen using the validation set) achieves clean accuracy of 97. 15% (77.0%% and adversarial accuracy of 90.44% (+84. 4444%) on Rotating MNIST.
Following the standard experimental strategy 26 45
5

---

[a]
results on Rotating MNIST varying starting domains
(b) The results on Portraits for varying starting domains
100
90
70
50
0 1
2
3
4
5 6 8
9
10
11
12 13 14 15 16 17 18 19 20
1
2
7
clean accuracy
adversarial accuracy
clean accuracy
adversarial accuracy
[c]
accuracy of models pseudo-labeled distribution
100
96
90
88
2 3
5
9
10 training
12
13
15
16
18 19 20
standard training
accuracy pseudo-labels
Figure 1: (a) shows the results of gradual AST methods with varying starting domains Rotating MNIST, The abscissa indicates different methods with varying starting domains т. The blue and red bars represent the clean accuracy and adversarial accuracy respectively of the trained model the target domain. (b) shows the result of gradual AST methods with varying starting domains on Portraits. (c) compares the effect of adversarial training and standard training under pseudo-labeled distributions on Rotating MNIST. We use blue and red bars to represent the clean accuracy of the standardly trained model and the adversarially trained model, respectively. The gray bar indicates the correct rate of the pscudo-labels.
When we set 0.05, the gradual AST with the optimal starting domain achieves clean accuracy of 86.04% (+4.01%) and adversarial accuracy of 77 77.25% (+37.02%) on Portraits.
3.4 Training with Labeled Intermediate Domains
In the setting of GDA, the learner is provided with unlabeled intermediate domains, and the model predicts pseudo-labels on an unlabeled data set in each iteration. The pseudo-labels contain a small proportion of incorrect labels, leading performance degradation of the trained model. In this section, we conduct experiments to investigate the optimal performance of the model trained with ground-truth labels. In other words, the learner is provided with labeled intermediate data. Although the learner has access to the ground-troe trutt intermediate labels, we still retain the filtering process, since we need to maintain the same data size to ensure fair comparison. We present the results of the models with varying r in Table 19 Appendix B). Since the results in Section 3.3 show that ( = 0.05 is the optimal filtration ratio for gradual AST methods, we set < = 0.05 in this section. From Table is provided with labeled intermediate domains, the vanilla gradual self-training method (r = 22) achieves clean accuracy of 98.44%
and and Table 20 (due to space limitations, we attach the tables in
that if the learner
Rotating MNIST. Recall the results in Table 9 showing that the proposed gradual AST method (r = 9) achieves clean accuracy 97. 15%. The performance (97.15%) of the proposed gradual AST is close to the optimal performance (98.44%) of the gradual self-training where the learner is provided with labeled intermediate domains.
Theoretical Analysis
In this section, we theoretically analyze the experimental phenomena identified in Section B and explain the efficacy of gradual AST. In Section 4.1 we provide the adversarial error bound for gradual AST. Section 4.2 we provide some theoretical insights about why AT outperforms standard training. In Section
further present example of conditional Gaussian distribution to

---

show the error correction effect of AT on the incorrect labels. Our theory thus supports the excellent performance of gradual AST shown in Section 3
4.1 Generalization Error Bounds for Gradual AST
We introduce the Margin Disparity Discrepancy (MDD) measure the domain shifts, as below.
Definition 4.1 (MDD (53). Let P and Q be two distributions over X. Given scoring function class F and a specific scoring function / E F, the MDD between P and Q is defined as
(f a sup PEr
( (f' (f((( (f))))
(2)
When the domain shift is slight, the MDD between the domains is small. The MDD is well-defined and can empirically estimated by the training data [33] where the estimation error can be bounded by Rademacher complexity. We next present the definition of Rademacher complexity, which is
widely used in generalization theory to measure the complexity of a hypothesis class.
Definition 4.2 (Rademacher Complexity X. For a fixed collection S of n data points, the empirical Rademacher complexity of G is defined as
44 ). Let be a of real-valued functions defined over
2
Rs( a
E
sup gEG
sag(az))
RSES
The expectation is taken over = (Si...., Sn). where a. E fI....,n.) are independent uniform random variables taking values in {-1, +11.
We next introduce an adversarial margin hypothesis class PFF.
Definition 4.3 (Adversarial Margin Hypothesis Class). Given a scoring function class F, the adver- sarial margin hypothesis class is defined
PFF
max px + &, f.S EF. [
Having defined the Rademacher complexity and the MDD, we now focus on pair of arbitrary consecutive domains. The following result shows that AST returns a new model f with bounded adversarial margin loss if the domain shifts gradually. The proof can be found in Appendix A.2
Theorem 4.4 (Adversarial Error Bound for AST). Let (P, and (Q. fq) be two domains with gradual shifts. Suppose we have a scoring function f pre-trained on domain (P, fP), and a data set S of n unlabeled data points drawn i..d according to distribution Q. I' is the adapted scoring function by generated by the AST algorithm over S, i.e., I' AST (T. S). Then, for any a 2 0, the following holds with probability of at least 1 over data points S:
2 RRs + +61 & ( + +.xxxdd/F(PPOO djF((P,Q)
log 4
2n
where 7"t min ((0) PEF Q (f, and X min
JEF { R
( (f) + (F)
Remark 4.5. Theorem 4.4 indicates that if we have model f with low adversarial margin loss on the domain (P, fr) and the distribution shifts slightly, AST generates new model f' that is also adversarially robust on the domain fo). The term is widely used in domain adaptation theory (4) to implicitly characterize the conditional distribution shift. In the setting of GDA, assume that the domain shifts only slightly, i.c., x and (F, Q) are relatively low.
Based on the error bounds for AST, we can apply this argument inductively and sum these error differences along the domain sequence obtain the following corollary. See proofs in Appendix A.3
Corollary 4.6 (Error Bounds for Gradual AST). Given sequence of domains (Pt, SP.), (O.... T} with gradual shifts, each intermediate domain has an unlabeled data set St drawn i.i.d. from Pt. The model is successively trained by the AST method, i.e fo (f)),
7

---

{l...., .T....TT. Then, for any 2 O, the following holds with probability of at least 1 - a over data points {8.)==
Rr (1fz) - R(p) R (fo)
+
Σ .e+
2T +
(s( + 67 +67
log 4T
P
2n
1=1
where K4 =
R P. (f+ fi-1)
min R (f) ( R (n)
FEF
JEF
Remark 4.7. Our bound indicates that the adversarial risk on target domain can be controlled by the adversarial margin loss on the source domain and the discrepancy [53] between the intermediate domains. We also consider the standard risk and find that the standard risk of AST can be bounded similarly. We provide the bounds in Appendix A.4
Comparison with Previous Work. Both of the works of [26] and 45 focus binary classification and standard self-training, while our results non-trivially extend the error bounds into the setting of adversarial GDA and multiclass classification. Furthermore, (26) sets linear hypotheses their training models, while we consider a more general hypothesis class that can be implemented by neural networks. 45 makes assumption that the new model can always fit the pseudo-labels without error. As we can observe from the experiments, the training error tends to be small but never equal O. Compared to [45), we don't need the assumption, our setting is more consistent with real experiments.
4.2 Adversarial Training Improves Clean Accuracy for Self- Self-Training
AT is generally considered harmful to the clean accuracy of the model 52 38 However, the experimental results in Section 3 indicate that AT unexpectedly improves both the clean accuracy and adversarial accuracy of the model trained on the pseudo-labels. In this section, we provide some theoretical insights showing that when the training data contains small portion of incorrect labels, the adversarially trained model may have tighter generalization guarantee than the standardly trained model. Our theorem is based on the following optimization problem.
Definition 4.8. Given two fixed vectors p and p' with all positive coordinates and fixed N- dimensional 0-1 vector e, i.e., E (0, 1)A, IT is a fixed subset of [1, The variant of the Subset Sum Problem 3 can be defined follows:
p - x¹x c/ stt 2; = 8E(0.1)
min
e (I, (l..,, NTAI.
We use (p' P. IT) to denote the optimal value of the problem. Given two fixed vectors p' and the value of the term y is therefore constant. The optimization problem can be viewed as of selecting subset of p such that the sum of its elements is close as possible to p Intuitively, the set II adjusts the difficulty of this optimization problem. For two sets II, C II,, we have V (p', p, e, II) V" e, II2) since we can optimize é on more coordinates.
With a little abuse of notations, in this subsection, we consider a discrete real distribution Pndd+ a discrete noisy pseudo-labeled distribution P., over X' x V. We denote the corresponding prob- ability mass functions as p and Py respectively.
and Pn can be viewed as two vectors, i.c., p: p(z,, 31), (I; M)) E X x V.i E {l..... I yl.. The standard risk the real data distribution is defined as (h) = E (xx))xxx p(x v) (1((())) + y) and the adversarial risk on the
laeule-labeled data distribution is defined as Rp, (h) E( (x, y) max 1 [1(x++)) + s].
|
The next result uses the optimal value V " Pr e, II) to bound the difference between these two risks. The proof can be found in Appendix A.5
Theorem 4.9. Given distributions P and P., over X y with the corresponding probability mass vectors and ptp the following bound holds for any classifier h E H,F
(h(h) S Rp,, (h) + 4² (p, Pm: e, 1le),
where is the risk vector e 11b(,,)) # vıl. and 11. {i: 1116111 S Se,h(x, + +8) h(x:))
8

---

W badv
W b badv
b badv W
Figure 2: The visualization of the adversarially trained classifier for a conditional Gaussian distribu- tion. AT consistently moves the threshold badv close the optimal threshold b 0, leading better generalization on the real data distribution. Best viewed in color.
By setting O, V (p, Po, Mo). By the definition of the set II, the larger the perturbation radius the larger the size of Ih, i.e., To C Ih We then have V (p: Py, e, II,) S VV Py, e, IT). Theorem 4.9
derive the error bound for standard training: Ry(h) I Rp, (h)
implies that if the adversarial risk Rp, (h) on the pseudo-labeled distribution is well controlled by AT, then AT may yield a tighter generalization guarantee than standard training.
4.3 A Toy Example of Conditional Gaussian Distribution
We further provide an example of a conditional Gaussian distribution show the efficacy of AT under incorrect pscudo-labels.
and the label space y/ = [-1, +1}. For simplicity, we assume that the two classes have symmetrical mean parameters {-H, + and the same standard deviations distribution P can then be defined as a distribution over X' x y = R x {-1,+1}. where the conditional distribution of X given Y is X|Y = y ~ N o²) and the marginal distribution of 1/2. We consider threshold hypothesis class, i.e., - {ar + sgn(æ - b) : IRJ, where sgn is the sign function. We denote the hypothesis with threshold b as hi. In the setting of self- self-training, we have a labeling function hww which is the model trained on the previous domain. The threshold # 0, since there is distribution shift. The function h. assigns y = -1 to the data points where x < w and assigns y = +1 to the data points where We denote the pseudo-labeled data distribution over X' x y as P. We use Rp, (h) and Rp, (h) respectively denote the standard 0-1 risk and adversarial 0-1 risk on the pseudo-labeled data distribution P,. We assume |w| < μa and < j4, since the domain shift is slight and the adversarial perturbation is subtle. We also assume μ > a, which means that most samples can be well separated. The learner is provided with infinite samples. Under these assumptions. we provide the following results to demonstrate the efficacy AT. The proof can be found in Appendix A.6
Example 4.10 (Conditional Gaussian Distribution). We consider the input space
The (p. or) >cnnditional Gaussian
is (1-1)- = (r((-11)
w.
Theorem 4.11. For the real data distribution P defined in Example 4.10 the optimal classifier that minimizes the standard risk Rp(h) and adversarial risk (p)h) is ho(.) sgn(.). For the labeled distribution P., defined in Example 4.10 the standardly trained classifier hatd that minimizes the standard risk Rp,, (h) is hard hwo the adversarially trained classifier hado that
minimizes the adversarial risk Rr, (h) has the following corresponding threshold badu.
+ e, O,
if w <
bado
if - E < <E
w E,
w >
Remark 4.12. Theorem 4.11 shows that the adversarially trained model hado consistently moves the threshold close to the optimal threshold 0. leading to a smaller generalization error. We visually represent the adversarially trained model in Figure 2
5 Related Work
Self-Training. series of works have achieved significant progress using self-training in semi- supervised learning [29 40) and domain adaptation [56). The recent work [9] has proposed robust

---

self-training (RST) to leverage additional unlabeled data for robustness 2 36]. While RST [9]
focuses on utilizing additional unlabeled data drawn from the same distribution improve adversarial robustness, our work investigates the different effects of vanilla self-training and adversarial self- training on clean accuracy.
Gradual Domain Adaptation. Unlike the UDA problem, GDA has intermediate domains between the source domain and target domain of UDA. Some works [22 17 48
propose various algorithms to handle these evolving domains in a computer vision context. The recent work 126 adopts the self-training method and proposes gradual self-training, which iteratively adapts the model along the domain sequence. Moreover, (26] provides the first learning theory for GDA and investigates when and why the gradual structure helps. [45] further improves the generalization error bound in [26) and reveals the influence of the number of intermediate domains on the error bound. [TO] investigates a more difficult setting in which the learner provided with set of unordered intermediate data. The authors propose TDOL. framework that generates synthetic domains by indexing the intermediate data. However, the aforementioned works pay insufficient attention the adversarial robustness of the model in GDA context. In the field of UDA, the work of [I]] constructs synthetic intermediate domains by creating Grassmannian manifolds between the source and the target. Another line of work instead uses generative network, such as cycle generative adversarial network X to generate the intermediate data.
Adversarial Training, After 41 shows that DNNs are fragile to adversarial attacks, large amount
of works have proposed various attack methods [33 g and defense methods 47 19 51
BT
20 24 30.
Adversarial training [19] is one of the popular and effective methods that improves adversarial robustness by adding adversarial examples to the training dataset. From the theoretical
perspective, some works focus on the sample complexity (50) 54 12 and the generalization of
adversarial training. [32 investigates the trade-off between robustness and fairness. [46] (55 study
adversarial robustness under self-supervised learning.
6 Conclusion
In this work, we empirically demonstrate that gradual AST improves both the clean accuracy and the adversarial accuracy the GDA model. We reveal that the reason for this performance improvement is that AT outperforms standard training when the training data contains incorrect pseudo-labels. We first provide generalization error bounds for gradual AST a multiclass setting. We then construct the Subset Sum Problem to connect the adversarial error and the standard error, providing theoretical insights into the superiority of AST in GDA. The example conditional Gaussian distribution is further provided give additional insights into the efficacy of AT pseudo-labeled training data.
Acknowledgements
This work is supported by the National Natural Science Foundation of China under Grant 61976161, the Fundamental Research Funds for the Central Universities under Grant 2042022rc0016.
References
[1] Samira Abnar, Rianne van den Berg, Golnaz Ghiasi, Mostafa Dehghani, Nal Kalchbrenner, and Hanie Sedghi. Gradual domain adaptation in the wild: When intermediate distributions are absent. arXiv preprini 2rXiv:2 106.06080, 2021.
[2] Jean-Baptiae Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth. and Pushmeet Kohli. Are labels required for improving adversarial robustness? In NeurIPS, pages 12192-12202, 2019.
[3] Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelhöfer, and Miklos Santha. Classical and quantum algorithms for variants of subset-sum via dynamic programming. In European Symposium on Algorithms, pages 6:1-6:18, 2022.
[4] Peter I.. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-488 2002.
10

---

[5] Shai nen-David, John Blitzer. Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine Learning. 79:151-175, 2010.
[6] Andreea Bobu, Eric Tzeng, Judy Hoffman, and Trevor Darrell. Adapting to continuously shifting domains. In ICLR, 2018.
[7] Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. university press, 2004.
Cambridge
[8] Nicholas Carlini and David A. Wagner. Towards evaluating the robustness neural networks. In SP, pages 39-57, 2017.
[9] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C. Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. In NeurlPS, pages 11190-112 12011, 2019.
[10] Hong- You Chen and Wei-Lun Chao. Gradual domain adaptation without indexed intermediate domains. NeurIPS, pages 8201-8214, 2021.
[11] Zhen Cui, Wen Li, Dong Xu, Shiguang Shan, Xilin Chen, and Xuelong Li. Flowing on riemannian manifold: Domain adaptation by shifting covariance. IEEE Transactions Cybermetics, 44:2264 2273, 2014.
[12] Daniel Cullina, Arjun Nitin Bhagoji, and Prateek Mittal. Pac-learning in the presence of adversaries. In NeurIPS, pages 228-239, 2018.
[13] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
[14] Özgür Erkent and Christian Laugier. Semantic segmentation with unsupervised domain adapta- tion under varying weather conditions for autonomous vehicles. IEEE Robotics and Automation Letters, 3:3580-3587, 2020.
[15] Abolfazl Farahani, Sahar Voghoei, Khaled Rasheed, and Hamid R. Arabnia. brief review of domain adaptation. arXiv preprint arXivv2010.03998. 2020.
[16] Ali Farshchian, Juan Alvaro Gallego, Joseph Paul Cohen, Yoshua Bengio, Lee E. Miller, and Sara A. Solla. Adversarial domain adaptation for stable crain-machine interfaces. ICLR, 2019.
[17] Michael Gadermayr, Dennis Eschweiler, Barbara Mara Klinkhammer, Peter Boor, and Dorit Merhof. Gradual domain adaptation for segmenting whole slide images showing pathological variability. ICISP, pages 461-469, 2018.
[18] Shiry Ginosar, Kate Rakelly, Sarah Sachs, Brian Yin, Crystal Lee, Philipp Krähenbühl, and Alexei A. Efros. A century of portraits: A visual historical record of american high school yearbooks. IEEE Trunsactions on Computational Imaging, 3:421-431 2017.
[19] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. In ICLR, 2015.
[20] Sven Gowal, Sylvestre-Alvise Rebuffi, Olivia Wiles, Florian Stimberg, Dan Andrei Calian, and Timothy A. Mann. Improving robustness using generated data. In NeurlPS, pages 4218 4233,, 2021.
[21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[22] Judy Hoffman, Trevor Darrell, and Kate Saenko. Continuous manifold based adaptation for evolving visual domains. In CVPR, pages 867-874, 2014.
[23] Han-Kai Hsu, Chun-Han Yao, Yi-Hsuan Tsai, Wei-Chih Hung, Hung- Yu Tseng, Maneesh Singh, and Ming- Yang. Progressive domain adaptation for object detection. In CVPR, pages 749-757, 2020.
11

---

[24] Qiyu Kang. Yang Song, Qinxu Ding, and Wee Peng Tay, Stable neural ODE with Iyapunov- stable equilibrium points for defending against adversarial attacks. In NewrIPS, pages 14925- 14937, 2021.
[25] Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30:1-50, 2002.
[26] Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In ICML, pages 5468-5479, 2020.
[27] Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. Adversarial examples in the physical world. In ICLR, 2017.
[28] Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. 1991.
[29] Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, JCML, page 896, 2013.
[30] Boqi Li and Weiwei Liu. WAT: improve the worst-class robustness in adversarial training, In AAAI, pages 14982-14990,, 2023.
[31] Xiyuan Li, Zou Xin, and Weiwei Liu. Defending against adversarial attacks via neural dynamic system. In NeurlPS, 2022.
[32] Xinsong Ma. Zekai Wang, and Weiwei Liu. On the tradeoff between robustness and fairness. In NeurlPS, 2022.
[33] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
[34] Yishay Mansour. Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT, 2009.
[35] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.
[36] Amir Najafi, Shin-ichi Maeda, Masanori Koyama, and Takeru Miyato. Robustness to adversarial perturbations in learning from incomplete data. In NeurIPS, pages 5542-5552 2019.
[37] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zachary Vito Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In NeurlPS, pages 8024-8035, 2019.
[38] Aditi Raghunathan, Sang Michael Xie, Fanny Yang. John C. Duchi, and Percy Liang. Adversar- ial training can hurt generalization. arXiv preprint arXiv:/906. 06002, 2019.
[39] Hadi Salman, Andrew Ilyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In NeurIPS, 2020.
[40] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raf- fel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervised learning with consistency and confidence. pages 596-608, 2020.
[41] Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
[42] Francisco Utrera, Evan Kravitz, N. Benjamin Erichson, Rajiv Khanna, and Michael W. Mahoney. Adversarially-trrinedd deep nets transfer better: Illustration on image classification. ICLR, 2021.
12

---

[43] Alexander Vergara, Shankar Vembu, Tuba Ayhan, Margaret A Ryan, Margie L Homer, and Ramón Huerta. Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical, 166:320-329, 2012.
[44] Martin J Wainwright. Iligh-dimensional statistics; A non-asymptotic viewpoint, volume 48. 2019.
[45] Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. In ICML, pages
2022.
[46] Zekai Wang and Weiwei Liu. Robustness verification for contrastive learning. In ICML, pages 22865-22883, 2022.
[47] Zekai Wang, Tianyu Pang, Chao Du, Min Lin, Weiwei Liu, and Shuicheng Yan. Better diffusion models further improve adversarial training. ICMI,, pages 86246-36263 2023.
[48] Markus Wulfmeier, Alex Bewley, and Ingmar Posner. Incremental adversarial domain adaptation for continually changing environments. In ICRA, pages 4489 4495, 2018.
[49] Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. In NeurlPS, 2022.
[50] Dong Yin, Kannan Ramchandran, and Peter I.. Bartlett. Rademacher complexity for adversari- ally robust generalization. In ICML, volume 97, pages 7085-7094, 2019.
[51] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing. Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. In ICML, pages 7472-7482, 2019.
[52] Jingfeng Zhang, Xilie Xu, Bo Han, Gang Niu, Lizhen Cui, Masashi Sugiyama, and Mohan S. Kankanhalli. Attacks which not kill training make adversarial learning stronger. In ICML, pages 11278-10 11287, 2020.
[53] Yuchen Zhang, Tianle Liu, Mingsheng Long, and Michael I. Jordan. Bridging theory and algorithm for domain adaptation. In ICML, pages 7404-7413, 2019.
[54] Zhengyu Zhou and Weiwei Liu. Sample complexity for distributionally robust learning under chi-square divergence. Journal of Machine Learning Research, pages 1-27, 2023.
[55] Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, pages 11::1-114:54 2023.
(56) Yang Zou, Zhiding Yu, Xiaofeng Liu, BVK Kumar, and Jinsong Wang. Confidence regularized self self-training. ICCV, pages 5982-5991, 2019.
13


Reviews:
[{"review_id": "UXJpkh9WYQ", "reviewer": "Reviewer_gQtX", "summary": "In this paper, the authors analyze the adversarial robustness of the gradual self-training method with adversarial self-training (AST). AST first predicts labels on the unlabeled data and then adversarially trains the model on the pseudo-labeled distribution. The authors introduce an adversarial self-training for gradual unsupervised domain adaptation in a multi-class problem. They show that when there is a little domain shift between consecutive intermediate domains, their adversarial self-training works better in performance and generality (more robust in the case of missed or bad pseudo-labeled) in comparison to vanilla gradual self-training.\nThey present the generalization error bounds for gradual AST in a multiclass classification setting and then use the optimal value of the Subset Sum Problem to bridge the standard error on a real distribution and the adversarial error on a pseudo-labeled distribution. Results indicate that AT may obtain a tighter bound than standard training on data with incorrect pseudo-labels. We further present an example of a conditional Gaussian distribution to provide more insights into why gradual AST can improve the clean accuracy for GDA.\n\n", "questions": "None. Please comment on the points described in the weaknesses.", "limitations": "Lack of comparison with other SOA domain adaptation methods.  Refer to the weaknesses for details.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper is clearly written and organized, and the key concepts and experimental results are described with enough details to understand. There is a clear discussion on the shortcomings and risks of unsupervised gradual domain adaptation on multi-target classification problems. \n+ The authors tackle an important and challenging problem. They propose using adversarial self-training for pseudo-labeling in the context of gradual domain adaptation. In particular, the authors show analytically that ℓq adversarial perturbation for sampling in unlabeled intermediate domains has lower error bounds compared to standard self-training. \n+ The supplementary material provides many additional proofs and experimental results that help support the paper.  Also, since the codes are also provided in supplementary material, there is less concern that the results in this paper would be difficult for a reader to reproduce.  The paper includes some information that would make it possible to reproduce the methods and experiments.  ", "weaknesses": "- When comparing to other methods in the literature, the authors claim that their method is based on milder assumptions. They should provide a more detailed discussion of the implications of such assumptions. \n- The experimental validation is limited in some respects. Authors show that gradual AST improves both the clean accuracy and adversarial accuracy of the GDA model. Validation is mostly performed on Rotating MNIST and Portraits datasets. However, experiments should assess in more detail the impact on the performance of growing the number of intermediate domains, using different backbones, and different larger datasets with more classes and class imbalance. \n- There should be an analysis of time and memory complexity for the proposed and SOA methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and constructive comments.\n\n**Q1: They should provide a more detailed discussion of the implications of the milder assumptions.**\n\n**A1:** Thank you for your constructive suggestion. In the work of [A], the authors assume that the new model can always fit the pseudo-labels without error, which can greatly simplify their analysis. On the contrary, we don't need this strong assumption in our work (Maybe it is better to say \"we don't need this assumption\" instead of \"our results are based on milder assumptions\"). **Our assumption is more consistent with real experiments.** The assumption in [A] means that the training error (fitting error) on each intermediate domain should equal to $0$, which does not correspond to the real situation. As we can observe from the experiments, the training error tends to be small but never equal to $0$. And the training error depends on the complexity of the hypothesis class. We will include this more detailed discussion in the revision.\n\n**Q2: The impact on the performance of growing the number of intermediate domains, using different backbones, and different larger datasets with more classes and class imbalance.**\n\n**A2:** Thank you for raising the concern. We have conducted more detailed experiments with different numbers of intermediate domains, different backbones, and different datasets as you suggested (the results can be found in the pdf file in the common response). \n* Larger number of intermediate domains: We split the Rotating MNIST and the portraits datasets with different lengths of interval and conduct an ablation study. For MNIST, we set the numbers of intermediate domains to be 24, 30, and 42 respectively; for portraits, we set the numbers of intermediate domains to be 8, 10, and 14 respectively. As we can observe in Tables 1 and 3, **the gradual AST method consistently improves performance compared to the vanilla gradual self-training method.** The clean accuracy of gradual AST on MNIST falls into a small range of $97.0\\\\%$ to $97.5\\\\%$, regardless of the choice of the number of intermediate domains. The results are not sensitive to the number of intermediate domains.\n* Different backbones: We use ResNet-18 and ResNet-50 as the backbones. The results in Tables 2 and 4 show that **with larger ResNet models, the clean and adversarial accuracy are consistently improved**, which shows the effectiveness of our gradual AST method using various backbones. For example, the clean and adversarial accuracy on portraits using ResNet18 is improved by $0.52\\\\%$ and $52.08\\\\%$ respectively.\n* Different datasets: We train the model on CIFAR-10 and CIFAR-100 datasets using ResNet-50 as the backbone. Similar to Rotating MNIST, we generate the dataset by rotating each CIFAR image at an angle between $0$ and $10$ degrees. The $50,000$ training set images are divided into three parts: a source domain of $12,000$ images, 3 intermediate domains of $36,000$ images, and a set of validation set. From Table 7, we can see that the gradual AST method improves the clean accuracy and the adversarial accuracy on CIFAR-10 by $1.30\\\\%$ and $33.85\\\\%$ respectively. **The effectiveness of the gradual AST method is also validated on larger datasets.**\n\n**Q3: There should be an analysis of time and memory complexity for the proposed and SOA methods.**\n\n**A3:** Thank you for raising the concern. The complexity depends on several factors, such as the size of the dataset $n$, the training epoch number $p$, and the number of iterations used in the PGD attack $k$. \n* Time Complexity: There are two main parts in the training process: predicting pseudo-labels and adapting (retraining) the model. **For the first part, both of these two methods have the same complexity $\\mathcal{O}(n)$.** For the second part, the gradual AST method is more time-consuming compared to the vanilla gradual self-training method, since the gradual AST method involves additional adversarial example generation. The model needs to be forward-passed and backpropagated $k$ times to generate adversarial examples in each epoch. **In this period, the time complexities of the gradual AST method and vanilla gradual self-training method are $\\mathcal{O}((k+1)pn)$ and $\\mathcal{O}(pn)$ respectively.** The complexities between these two methods are of the same order, just one constant time different. And the benefits of greatly improved performance can justify the extra computational cost. Experimentally, for our experiments on an Nvidia GeForce RTX 2080 GPU, **the gradual AST method ($\\tau=0$) takes less than one hour to train a model on Rotating MNIST.**\n* Memory Complexity: During the training process of the neural network, the computation graph [C] occupies the major portion of memory. **Both the gradual AST method and vanilla gradual self-training method have the same size of computation graph. The additional memory consumption for storing the adversarial perturbations is almost negligible.** For our experiments on Rotating MNIST with a 3-layer convolutional neural network, the memory consumption for both methods are only 920 MB, which is an affordable cost for most GPUs.\n\n\n**References:**\n\n[A]: Haoxiang Wang et.al, Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. ICML, 2022.\n\n[B]: Shai Ben-David et.al, Understanding machine learning: From theory to algorithms.\n\n[C]: How Computational Graphs are Constructed in PyTorch. https://pytorch.org/blog/computational-graphs-constructed-in-pytorch/ "}, {"review_id": "aECxSLOyYo", "reviewer": "Reviewer_QQok", "summary": "This paper proposes adversarial self-training (AST) that incorporates adversarial training with gradual self-training. Empirical results validate that AST can enhance both adversarial robustness and generalization ability in the scenario of the gradual unsupervised domain adaption. The authors provide empirical and theoretical analyses to interpret this surprising phenomenon.", "questions": "\n1. Please refer to the comments in the Weaknesses.\n\n2. What kind of adversarial attacks did you use when evaluating adversarial robustness?\n\n3. How can you choose the perturbation bound during AST? What is the performance if using different perturbation bounds?\n", "limitations": "The authors did not discuss the limitations. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well-organized and well-written.\n\n2. The empirical observation, that AST can improve robust and natural test accuracy simultaneously in gradual domain adaptation, is interesting and surprising. The natural test accuracy achieved by AST is even close to the optimal results, which validates the significance of the empirical results.\n\n3. The authors provide comprehensive empirical analyses to explain the phenomenon that AST improves natural accuracy.\n\n4. The authors present comprehensive theoretical analyses of AST, including the error bound of (gradual) AST and the connection between natural risk and adversarial risk. The theoretical analyses further help to explain the effectiveness of AST. \n", "weaknesses": "1. The experiments are conducted on a simple network. What if the results were evaluated on a more complex network say ResNet18?\n\n2. I am a bit confused about the term “gradual shifts”. Does this term mean that the test distribution is different from all the training distributions? If so, I am interested in the performance evaluated on the previous training distributions achieved by AST as well to check whether there is a forgetting issue.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments and positive assessment. We are glad that you find the empirical observation interesting and surprising.\n\n**Q1: What if the results were evaluated on a more complex network say ResNet18?**\n\n**A1:** Thank you for raising the concern. As per your suggestion, we have included additional experiments on ResNet18 and ResNet50. The results can be found in the pdf file in the common response. As Tables 2 and 4 show, **the proposed gradual AST method consistently improves the clean accuracy and adversarial accuracy on large ResNet models**. For example, the clean accuracy on portraits using ResNet18 is improved by $0.52\\\\%$. And the accuracy achieved by ResNet is higher than that of a 3-layer convolutional neural network. We will include these positive results in the revision paper.\n\n**Q2: Does the term \"gradual shifts\" mean that the test distribution is different from all the training distributions? If so, I am interested in the performance evaluated on the previous training distributions achieved by AST as well to check whether there is a forgetting issue.**\n\n**A2:** Yes, the term \"gradual shifts\" means that the distributions of the domains change gradually along the domain sequence and the shift between two adjacent domains is slight. Hence the test distribution is different from the training distributions. As the algorithm of the gradual AST method shows (sections 2.2 and 3), the model is first pre-trained on the source domain and then successively self-trained on the intermediate domains. We record the accuracy of our method on the source domain during the training process. As Fig. 1 shows, when the model is finetuned along the domain sequence, the accuracy on the source domain gradually decreases. **This forgetting phenomenon is foreseeable considering the domain shift and widely studied in the field of continue learning** [A-D]. However, in the (gradual) domain adaptation setting, researchers [E,F] mainly focus on the performance on the target domain where the model is expected to be applied, rather than the performance on the source domain. **We believe the forgetting issue is a matter of concern in some scenarios, but not the focus of the (gradual) domain adaptation setting [E,F].**\n\n[A]: Gido M. van de Ven et.al, Three scenarios for continual learning. arxiv:1904.07734.\n\n[B]: Pietro Buzzega et.al, Dark Experience for General Continual Learning: a Strong, Simple Baseline. NeurIPS 2020.\n\n[C]: Ronald Kemker et.al, Measuring Catastrophic Forgetting in Neural Networks. AAAI 2018.\n\n[D]: Sang-Woo Lee et.al, Overcoming Catastrophic Forgetting by Incremental Moment Matching. NeurIPS 2017.\n\n[E]: Garrett Wilson et.al, A Survey of Unsupervised Deep Domain Adaptation. ACM Transactions on Intelligent Systems and Technology.\n\n[F]: Mingsheng Long et.al, Conditional Adversarial Domain Adaptation. NeurIPS 2018.\n\n**Q3: What kind of adversarial attacks did you use when evaluating adversarial robustness?**\n\n**A3:** We use the **PGD-20** [G] attack to evaluate the adversarial robustness. PGD-20 attack is widely used in many works [G][H] of adversarial training.\n\n**Q4: How can you choose the perturbation bound during AST? What is the performance if using different perturbation bounds?**\n\n**A4:** Following the work of [H], we choose $\\epsilon=0.1$ and $\\epsilon=0.031$ in the main body for MNIST and portraits respectively. To validate the effectiveness of the gradual AST method using different perturbation bounds, we conduct experiments on MNIST using $\\epsilon=0.15, 0.2, 0.3$ and conduct experiments on portraits using $\\epsilon=0.01,0.02,0.04,0.05$. As Tables 5 and 6 show, **the gradual AST method can consistently improve the clean accuracy and adversarial robustness using various $\\epsilon$ values**. \n\n[G]: Aleksander Madry et.al, Towards Deep Learning Models Resistant to Adversarial Attacks. ICLR 2018.\n\n[H]: Hongyang Zhang et.al, Theoretically principled trade-off between robustness and accuracy. ICML 2019."}, {"review_id": "HJJpOiCxJM", "reviewer": "Reviewer_z2iW", "summary": "The paper proposes an Adversarial Self-Training method to improve the robustness and clean accuracy under the scenario of gradual domain adaptation. More specifically, the paper uses networks to generate pesudo label for gradually changing domain and update the model with the pesudo label. Experiments on Rotating MNIST and Portraits show that the proposed paper large improves the robustness of the network. Additionally, it can also improves the clean accuracy. The paper also perform theoretical analysis of their method, providing error bound of AST and provide a toy example demonstrating why AST achieves better clean performance.", "questions": "1. Can the authors give high level intuition of Definition 4.3? What does Adversarial Margin Hypothesis Class mean?", "limitations": "See Weakness.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper proposes a simple but effective method to achieve robustness under the scenario of gradual domain adaptation.\n2. Both theoretical and empirical results are present to show the effectiveness of AST. Particularly, the theoretical analysis in Section 4.1 is clear and useful.\n3. Generally, the paper is easy to follow with clear motivation and good presentation.", "weaknesses": "1. The proposed method, AST, seems to be an application of [1, 2] under the scenario of gradual domain adaptation, which lacks of novelty.\n2. The experiment is also weak. MNIST is too small and simple to prove the effectiveness of AST in practical applications. I will recommend the authors to perform more experiments in the following aspects:\n\n    1). Perform one experiments on gradual domain shift for natural images like CIFAR10.\n\n    2). Enlarging $\\epsilon$ to see whether clean accuracy is still improved for larger adversarial budget.\n3. Theorem 4.9 seems to imply strong assumption that only if adversarial risk is well controlled, then standard training is dominated by adversarial training. But the paper does not give how well should the adversarial risk gets controlled.\n\n[1] Yair Carmon et.al., Unlabeled data improves adversarial robustness, NeurIPS 2019\n\n[2] Jonathan Uesato et.al., Are Labels Required for Improving Adversarial Robustness?, NeurIPS 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback on our work.\n\n**Q1: The proposed method, AST, seems to be an application of [1,2] under the scenario of gradual domain adaptation (GDA), which lacks of novelty.**\n\n**A1:** Thank you for raising the concern. As you mentioned, some AST similar methods were previously used in [1,2] to improve the adversarial robustness. However, our work is the **first** to apply the AST in GDA and propose gradual AST to improve the performance in the GDA setting. **And most importantly**, we find that gradual AST can not only improve the adversarial robustness but also the **clean accuracy. Other reviewers also agree that this is an appealing and nontrivial result**, considering many prior works demonstrate that adversarial training (AT) may hurt generalization. Novelly, to explore the reason for the improvements in clean accuracy, we empirically find that **AT performs better than standard training when the pseudo-labeled training set contains a proportion of incorrect labels**. From the theoretical perspective, we provide the **generalization error bounds for gradual AST**, which explain why the model is adversarially robust on the target domain. Our results novelly extend the error bounds into the setting of adversarial GDA and multiclass classification. And we provide **an error bound and a toy example of Gaussian distribution** to theoretically explain the reason for the improvements in clean accuracy.\n\nOur work has different focuses on the AST method: the work of [1, 2] focuses on the importance of unlabeled data and shows that the unlabeled data can be incorporated into the training process by the AST method to improve the robustness; while in our work, we point out the gradual AST performs better than the vanilla gradual self-training and the reason of the superiority.\n\nTo sum up, the proposed method is only a small part of our contribution, but the surprising and appealing performance improvement (especially for the clean accuracy) and the theoretical and empirical exploration of the reason for the improvements constitute the main contribution of the paper.\n\n**Q2: I will recommend the authors to perform more experiments in the following aspects: ...**\n\n**A2:** Thanks for your important suggestion. We have conducted more experiments for datasets CIFAR10 and CIFAR100 and various perturbation values $\\epsilon$. Please refer to the Common Response.\n\n**Q3: Theorem 4.9 seems to imply strong assumption that only if adversarial risk is well controlled, then standard training is dominated by adversarial training. But the paper does not give how well should the adversarial risk gets controlled.**\n\n**A3:** Thank you for raising this excellent concern. To answer this question, we need to take a closer look at the upper bound of Theorem 4.9:\n$\\widetilde{R} _{P _\\eta}(h)+\\Psi^*(p,p _\\eta,e,\\epsilon).$\nFor standard training, where $\\epsilon=0$, the upper bound is:\n$R _{P _\\eta}(h)+\\Psi^*(p,p _\\eta,e,0).$ Comparing these two upper bounds, we can conclude that if $\\widetilde{R} _{P _\\eta}(h)-R _{P _\\eta}(h)\\le\\Psi^*(p,p _\\eta,e,0)-\\Psi^*(p,p _\\eta,e,\\epsilon)$, then AT yields a tighter generalization bound than standard training. The term $\\widetilde{R} _{P _\\eta}(h)-R _{P _\\eta}(h)$ is referred to as \"smoothness loss\" in some works of AT [2,3], which reflects the smoothness of the model $h$. And AT has an implicit smoothness regularization [2,3] which reduces the smoothness loss. If the smoothness loss is well controlled by AT to be less than $\\Psi^*(p,p _\\eta,e,0)-\\Psi^*(p,p _\\eta,e,\\epsilon)$, then AT may improve the clean accuracy as we observed in the experiments. \n\nIn our toy example presented in Section 4.3, the smoothness loss is well controlled by AT. When $w<-\\epsilon$, the smoothness loss of $h _{adv}$ equals $0$, i.e., $\\widetilde{R} _{P _\\eta}(h _{adv})=R _{P _\\eta}(h _{adv})$. And $\\Psi^*(p,p _\\eta,e,0)-\\Psi^*(p,p _\\eta,e,\\epsilon)$ is positive. In this case, AT yields a tighter generalization guarantee than standard training.\n\n**Q4: Can the authors give high level intuition of Definition 4.3? What does Adversarial Margin Hypothesis Class mean?**\n\n**A4:** Thanks for raising the concern. Given a fixed pair of score functions $f,f'$, the composed function in the class $\\widetilde{\\rho_\\mathcal{F}\\mathcal{F}}$ reflects how well $f'$ fits $f$ under the adversarial perturbation. \n\nWe can analyze this complex hypothesis class step by step. In a standard learning scenario, supervised multi-class classification problem, classical generalization bounds are based on the Rademacher complexity of a composed hypothesis class, which is composed by the loss function and the predictor class. Given a score-based predictor class $\\mathcal{F}\\triangleq\\\\{f:\\mathcal{X}\\to R^{|\\mathcal{Y}|}\\\\}$, and a margin loss $\\rho _f(x,y)\\triangleq f _y(x)-\\underset{y'\\neq y}{max}f _{y'}(x)$, then the composed hypothesis class can be defined as \n$$\\rho _\\mathcal{F}\\triangleq\\\\{(x,y)\\to \\rho _{f}(x,y):f\\in\\mathcal{F}\\\\}=\\\\{(x,y)\\to f _y(x)-\\underset{y'\\neq y}{max}f _{y'}(x):f\\in\\mathcal{F}\\\\}.$$\n\nFor GDA, **the label function is not fixed**: during the training process, the pseudo-labels on the current domain are predicted by the model trained on the last domain. Hence, we adapt the composed hypothesis class with an unfixed label function:\n$$\\rho _\\mathcal{F}\\mathcal{F}\\triangleq\\\\{x\\to \\rho _{f'}(x,h _f(x)):f,f'\\in\\mathcal{F}\\\\}.$$\n\nFinally, we add a perturbation to the input $x$ and we have the Adversarial Margin Hypothesis Class:\n$$\\widetilde{\\rho _\\mathcal{F}\\mathcal{F}}\\triangleq\\\\{x\\to \\max _{\\|\\delta\\| _q\\le\\epsilon}\\rho _{f'}(x+\\delta,h _f(x)):f,f'\\in\\mathcal{F}\\\\}.$$\n\n**References:**\n\n[1] Yair Carmon et.al., Unlabeled data improves adversarial robustness, NeurIPS 2019.\n\n[2] Jonathan Uesato et.al., Are Labels Required for Improving Adversarial Robustness?, NeurIPS 2019.\n\n[3]: Hongyang Zhang et.al, Theoretically Principled Trade-off between Robustness and Accuracy. ICML 2019."}, {"review_id": "oRsGYgQ8TW", "reviewer": "Reviewer_oh7v", "summary": "This paper investigates the adversarial gradual domain adaptation. The authors apply adversarial learning in the self-training approaches in gradual domain adaptation, forming the adversarial self-training approach (AST). Empirically, the authors show that AST improves both adversarial accuracy and clean accuracy on MNIST and Portraits, and further experimentally explore the reason for the improvements in clean accuracy. Theoretically, new bounds of the empirical risk based on Margin Disparity Discrepancy are developed, providing a tighter bound for adversarial self-training than standard self-training and partially explaining the superiority of AST over standard self-training for gradual domain adaptation.", "questions": "Line 46, labeling -> labels.\n\nWhy should we prove the two inequalities in Lemma A.1? Is it because $\\tilde{R}_{P}^{(\\rho)}(f_1,f_2)$ (I abbreviate it as $R12$) is asymmetric? If so, do we need to prove the other two inequalities: $R12 \\leq R31 + R32$ and $R12 \\leq R31 + R23$.", "limitations": "Limitations are encouraged to be included.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "It is appealing that adversarial self-training can improve clean accuracy, for which the authors provide theoretical and empirical analysis. \n\nThe theoretical bounds and analysis are new to me.\n\nThe paper is well-written and the method is easy to follow.\n", "weaknesses": "In the Introduction, the contributions could be better summarized. To my understanding, the main contributions are the experimental findings on the performance improvements by AST, and the theoretical bounds and analysis, which should be clearly summarized.\n\nThe paper assumes the distribution shifts slightly, which could not be realistic. \n\nMNIST and Portraits seem to be simple. Experiments on more challenging datasets are encouraged.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments and positive assessment. We are glad that the empirical improvement and theoretical analysis are appealing to you.\n\n**Q1: In the Introduction, the contributions could be better summarized.**\n\n**A1:** Thank you for this important suggestion. The novelty and contribution of our work are mainly focused on:\n* We are the **first** to apply the AST method in gradual domain adaptation and propose gradual AST to improve performance in the gradual domain adaptation setting. (Section 3)\n* The proposed gradual AST method can not only improve the adversarial robustness **but also the clean accuracy** for gradual domain adaptation, which is an **appealing and nontrivial** result, considering that many prior works demonstrate that adversarial training may hurt generalization. (Section 3.1)\n* We empirically explore **the reason for the improvements in clean accuracy**: We find that adversarial training performs better than standard training when the pseudo-labeled training set contains a proportion of incorrect labels. (Section 3.2)\n* We provide the generalization error bounds for gradual AST, which **explain why the trained model is adversarially robust on the target domain**. (Section 4.1)\n* We provide an error bound and a toy example of Gaussian distribution to theoretically **explain the reason for the improvements in clean accuracy**. (Sections 4.2, 4.3)\n\nThanks again for raising this concern, and we will include a clear summary of our contributions in the revision.\n\n**Q2: The paper assumes the distribution shifts slightly, which could not be realistic.**\n\n**A2:** Thanks for raising this concern. We want to make a clarification that **we only assume that the shift between two adjacent domains is slight, rather than the shift between the source and the target**. In this paper, we assume the learner is provided with a source domain, multiple intermediate domains, and a target domain, and the distribution shifts gradually along the domain sequence. **This is a mild assumption widely accepted in prior works** [A-C]. And there are **many cases in real-world scenarios that satisfy such an assumption**. For example, the sensor measurements shift gradually over time due to sensor aging [D]; the road condition evolves as the car running [E]; and neural signals received by brain-machine interfaces change within the span of a day [F].\n\n[A]: Ananya Kumar et.al, Understanding Self-Training for Gradual Domain Adaptation. ICML 2020.\n\n[B]: Haoxiang Wang et.al, Understanding Gradual Domain Adaptation: Improved Analysis, Optimal Path and Beyond. ICML 2022.\n\n[C]: Hong-You Chen et.al, Gradual Domain Adaptation without Indexed Intermediate Domains. NeurIPS 2021.\n\n[D]: Alexander Vergara et.al, Chemical gas sensor drift compensation using classifier ensembles. Sensors and Actuators B: Chemical.\n\n[E]: Andreea Bobu et.al, Adapting to Continuously Shifting Domains. ICLR 2018.\n\n[F]: Ali Farshchian et.al, Adversarial Domain Adaptation for Stable Brain-Machine Interfaces. ICLR 2019.\n\n**Q3: Experiments on more challenging datasets are encouraged.**\n\n**A3:** Thank you for this constructive suggestion. We train the model on CIFAR-10 and CIFAR-100 datasets using ResNet-50 as the backbone.  From Table 7, we can see that **the gradual AST method consistently improves the clean accuracy and the adversarial accuracy on CIFAR-10 and CIFAR-100 datasets**. Hence, the effectiveness of the gradual AST method is also validated on the larger datasets. We will include these results in the revision.\n\n**Q4: Line 46, labeling -> labels.**\n\n**A4:** We have fixed the typos. Thanks for catching them.\n\n**Q5: Why should we prove the two inequalities in Lemma A.1? Is it because $R_{12}$ is asymmetric? If so, do we need to prove the other two inequalities: $R_{12}\\le R_{31}+R_{32}$ and $R_{12}\\le R_{31}+R_{23}$?**\n\n**A5:** We prove Lemma A.1 in order to be able to decompose the error in Lemma A.4 (in Eq. (9)). Actually, we just need to use the second inequality in Lemma A.1 and we can remove the first inequality. As for the other two inequalities: $R_{12}\\le R_{31}+R_{32}$ and $R_{12}\\le R_{31}+R_{23}$, **we don't need to prove them, because the proof of our theory is not based on these two inequalities**."}]

Author rebuttal:
## Common Response (Additional Experiments)
We thank all the reviewers for their detailed and constructive comments. As per suggestions from the reviewers, we include some additional experiments here. **The results can be found in the attached PDF file**.

* **Larger number of intermediate domains**: We split the Rotating MNIST dataset with different lengths of interval and conduct an ablation study. For MNIST, the numbers of intermediate domains are 24, 30, and 42, respectively; for portraits, the numbers of intermediate domains are 8, 10, and 14, respectively. The results can be found in Tables 1 and 3, which show that our gradual AST method is nonsensitive to the choice of the number of intermediate domains.
* **Different backbones**: We use ResNet-18 and ResNet-50 as the backbones. The results can be found in Tables 2 and 4, which validate that the gradual AST method consistently improves performance on large models compared to the vanilla self-training method. For example, the clean and adversarial accuracy on portraits using ResNet18 is improved by $0.52\\%$ and $52.08\\%$ respectively.
* **Different datasets**: We train the model on the CIFAR-10 and CIFAR-100 datasets using ResNet-50 as the backbone. Similar to Rotating MNIST, we generate the dataset by rotating each CIFAR image at an angle between $0$ and $10$ degrees. The $50,000$ training set images are divided into three parts: a source domain of $12,000$ images, 3 intermediate domains of $36,000$ images, and a set of validation set. From Table 7, we can see that the gradual AST method improves the clean accuracy and the adversarial accuracy on CIFAR-10 by $1.30\\%$ and $33.85\\%$ respectively. Hence, the gradual AST method can also improve performance on larger datasets.
* **Different perturbation bound $\epsilon$**: To validate the effectiveness of the gradual AST method using different perturbation bounds, we conduct experiments on MNIST using $\epsilon=0.15, 0.2, 0.3$ and on portraits using $\epsilon=0.01,0.02,0.04,0.05$. The gradual AST method can consistently improve clean accuracy and adversarial robustness using various $\epsilon$ values. Please refer to Tables 5 and 6.

Meta-review: In this paper, the authors propose using adversarial self-training (AST) in gradual self-training for domain adaptation and show that it improves not only adversarial accuracy but also clean accuracy on the target domain in an empirical analysis. The authors reveal that this is because the proposed AST is more robust when the pseudo-labels obtained on the new domain contain a portion of incorrect labels. They further present the generalization error bounds for gradual AST.

The paper received unanimously positive reviews. The reviewers, in general, found the tackled problem of gradual domain adaptation to be important, and the empirical finding that AST can improve both robust and clean accuracy in such a setting to be interesting and a meaningful contribution. They also found the explanation of this phenomenon and the theoretical analysis to be comprehensive and useful, and the paper to be well-written.

However, there were concerns regarding the results obtained with smaller networks on simple datasets, a lack of complexity analysis, a lack of novelty, and strong assumptions in the theoretical analysis. Nevertheless, they were less critical, and the authors' responses with additional experimental results cleared away most of the concerns. Thus, the reviewers maintained their positive ratings even after the rebuttal, reaching a consensus to accept the paper.
Decision: Accept (poster)