Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization
Authors: seyed amir hossein saberi
Amir Najafi
Amin Behjati
Ala Emrani
Yasaman Zolfimoselo
Mahdi Shadrooy
Abolfazl Motahari
Babak Khalaj
Venue: NeurIPS 2024 poster (2024)
Keywords: Gradual Domain Adaptation
Distributionally Robust Optimization
Generalization Bound
Error Propagation Characterization
Primary area: learning_theory
TL;DR: We propose a DRO-based method for gradual domain adaptation with theoretical generalization guarantees. We also introduce a new complexity measure that independently characterizes the dynamics of error propagation in gradual domain adaptation.

Abstract: The aim of this paper is to address the challenge of gradual domain adaptation within a class of manifold-constrained data distributions. In particular, we consider a sequence of $T\ge2$ data distributions $P_1,\ldots,P_T$ undergoing a gradual shift, where each pair of consecutive measures $P_i,P_{i+1}$ are close to each other in Wasserstein distance. We have a supervised dataset of size $n$ sampled from $P_0$, while for the subsequent distributions in the sequence, only unlabeled i.i.d. samples are available. Moreover, we assume that all distributions exhibit a known favorable attribute, such as (but not limited to) having intra-class soft/hard margins. In this context, we propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. We theoretically show that this method guarantees the classification error across all $P_i$s can be suitably bounded. Our bounds rely on a newly introduced {\it {compatibility}} measure, which fully characterizes the error propagation dynamics along the sequence. Specifically, for inadequately constrained distributions, the error can exponentially escalate as we progress through the gradual shifts. Conversely, for appropriately constrained distributions, the error can be demonstrated to be linear or even entirely eradicated. We have substantiated our theoretical findings through several experimental results.

Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization
Amirhossein S
Amir Najafi!
Amin Behjati
Ala Emrani Babak H. Khalaj*
Yasaman Zolfit
Mahdi Shadrooyf
Abolfazl Motaharit
Department of Electrical Engineering. Department of Computer Engineering.
Sharif Center for Information Systems and Data Science, Sharif University of Technology, Tehran, Iran
Abstract
The aim of this paper is to address the challenge of gradual domain adaptation within a class of manifold-constrainee data distributions. In particular, con- sider a sequence of T 2 2 data distributions PI..... Py undergoing a gradual shift, where each pair of consecutive measures P:, P++1 are close each other in Wasserstein distance. We have a supervised dataset of size n sampled from Po. while for the subsequent distributions in the sequence, only unlabeled i.i.d. samples are available. Moreover, we assume that all distributions exhibit known favorable attribute, such as (but limited to) having intra-class soft/hard mar- gins. In this context, we propose a methodology rooted in Distributionally Robust Optimization (DRO) with an adaptive Wasserstein radius. We theoretically show that this method guarantees the classification error across all P,s can be suitably bounded. Our bounds rely on newly introduced compatibility measure, which fully characterizes the eтrоr propagation dynamics along the sequence. Specifically, for inadequately constrained distributions, the error can exponentially escalate as we progress through the gradual shifts. Conversely, for appropriately constrained distributions, the error can be demonstrated to linear or even entirely eradi- cated. We have substantiated our theoretical findings through several experimental results.
Introduction
Gradual domain adaptation addresses a critical challenge in machine learning: the high cost and impracticality of continually preparing labeled datasets for training ML models. Once initial labeled dataset is obtained through costly labor, machine learning models can use it to automatically label future unlabeled datasets-a procedure called self-training. However, as these future datasets experience gradual domain shifts from the original one, the initial dataset may become less effective, necessitating renewed human effort. Gradual domain adaptation has been proposed mitigate this issue by learning a model on the initial dataset and then gradually adapting it to the future unlabeled data sequential manner. Formally, we consider a sequence of datasets modeled via empirical measures Po.... Pr, where Po represents the initial labeled dataset and the remaining P; are unlabeled. Here, T' denotes the length of the sequence, and each P; is an empirical estimate of an unknown distribution P; based n; i.i.d. samples. We assume that consecutive measures P. and
Emails: sah, saberi@ee. sharif.ed famir majafi, motahari, khalaj Baharif. (t) Authors with equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Pi+1 are within a bounded Wasserstein distance from each other to make the problem theoretically approachable.
Recent research in this field has proposed various methods, each with distinct advantages and disadvantages. Theoretical advancements aim to bound the generalization error, provide robustness certificates as the model adapts to successive datasets, and, importantly, quantify the eπrоr propagation dynamics along the sequence. Naive approaches often lead exponentially increasing errors with respect to 'I' for the model performance on the most recent dataset. For some problem families, this exponential increase is conjectured to be inevitable. However, for appropriately restricted problem sets, such as linear classifiers and distributions with hard/soft margins, novel methodologies can control error propagation [KML20). To date, no work has fully established cases where error propagation remains fixed or increases sublinearly, and a comprehensive theoretical characterization of problems in this context is still lacking.
We aim to address these challenges with a novel approach leveraging distributionally robust optimiza- tion (DRO) for gradual domain adaptation. Our core idea based on the limited knowledge that the unknown labeled version of distribution Ps+1. or empirically, the unlabeled measure P. together with its latent labels, is within a bounded proximity of P; in distributional sense. Using DRO on P. (or its empirical version P.) with carefully chosen and adaptive adversarial radius, we provide theoretical guarantees on P.+1- Furthermore, when distributions exhibit favorable properties- succh as lying on manifold of margin-basee based measures- across domains can be established. In order to do so, we introduce a new complexity measure, the "compatibility function," which depends on the classifier hypothesis set θ, the properties of the manifold for Pis, and the Wasserstein distance between consecutive distributions P. and Pi+1- This measure effectively bounds error propagation and identifies scenarios where errors remain bounded. Our analysis also extends to non-asymptotic cases where only empirical estimates of the distributions available, showing that error terms decrease with [min, m
demonstrate that certified bounds generalization
We apply our method theoretically to two examples: (i) a toy example involving linear classifiers and Gaussian mixture model data with two components, which has been central in previous studies on DRO and gradual domain adaptation, and (ii) a more general class of distributions (referred to as "expandable" distributions) with learnable classifiers. In the former case, we demonstrate that accounting for Gaussian structural information eliminates error propagation in the statistical sense in the asymptotic regime. Additionally, in the non-asymptotic scenario, having 2 df log T samples per dataset leads to the same result. Conversely, neglecting manifold information results in exponentially growing error, anticipated. For expandable distributions and learnable classifiers, we provide theoretical bounds on sample complexity and error propagation dynamics based on newer notions of adversarial robustness. Once again, we identify rather general scenario where DRO completely eliminates error propagation. We further validate our theoretical findings through a series of experiments.
The rest of the paper is organized as follows: Section 1.T reviews related work. Our methodology is discussed in Section where we present our main theorems. Section 3 details our results for the Gaussian setting, while a broader class of problems, termed expandable distributions and smooth classifier families, are analyzed in Section 4 including their non-asymptotic analysis in subsection section we will be discussing our experimental results. We conclude in Section 6
1.1 Previous Works
Classic unsupervised domain adaptation aims to align feature distributions between labeled source domain and an unlabeled target domain. Generating intermediate domains can facilitate smoother adaptation, transforming the process into gradual domain adaptation. However, these intermediate domains are often unavailable. Sagawa et al. SH22] address this by using normalizing flows to learn transformations from the target domain to Gaussian mixture distribution through the source domain. Zhuang et al. [ZZW23 propose Gradient Flow (GGF) to generate intermediate domains, leveraging the Wasserstein gradient flow to transition from the source to the target domain, minimizing a composite energy function.
Kumar et al. KML.20 propose gradual self-training algorithm, adapting the initial classifier using pseudo-labels from intermediate domains. They show the importance of leveraging the gradual shift structure, regularization, and label sharpening, providing a generalization bound for target domain

---

error. This bound given by e (co + 0 OVnn=olg'' log where eo is source domain error, and is each domain's s data size. Wang et al. [WLZ22] improve this approach, achieving a significantly better generalization bound co O (TA + Tn-1/2 + (nT)-11/3), where A is the average distance of consecutive domain distributions, and propose an optimal strategy for constructing intermediate domain paths. He et al. [HWLZ23) suggest placing intermediate domains uniformly along the Wasserstein distance between the source and target domains to minimize generalization error. The GOAT framework, based on this insight, uses optimal transport to generate intermediate domains and applies gradual self self-nrainn Similarly, Abnar et al. [ABG* 21] introduce GIFT, which creates virtual samples from intermediate distributions by interpolating representations of examples from source and target domains. Zhang et al. [ZDIZ2T] propose the AuxSelfTrain framework, generating combination of source and target data in different proportions, gradually incorporating more target data, and employing a self-training procedure.
Unsupervised domain adaptation can be viewed as a Generalized Target Shift problem. Xiao et al. [ZLL233] introduce a discriminative energy-based method for test sample adaptation in domain generalization, modeling the joint distribution of input features and labels on source domains. Kirchmeyer et al. [ propose the OSTAR method, using optimal transport to align pre- trained representations without enforcing domain invariance, reweighting source samples, and training a classifier on the target domain. Generative Adversarial Networks (GANs) [GPAM + 14) inspire domain adaptation methods that use a feature extractor and a classifier to generate class responses, processed by a discriminator to distinguish between source and target domains. Cui et al. (CWZ"20) introduce the Gradually Vanishing Bridge (GVB) framework reduce domain-specifie characteristics and balance adversarial training, enhancing domain-invarian representations.
1.2 Notations and Definition
Consider X' as a measurable space for features and let y = [-1, represent the set of possible labels in a binary classification scenario. In this regard, Z = X' y encompasses the entire space of feature-label pairs. We use .M (2) to denote the set of all probability measures supported on 2. For any p 2 1, let I|- denote the fn-norm. Additionally, for probability measure notation Px refers the marginal distribution of on X. get consider a natural number n E N. We define the composition of g repeated times as follows:
. (2), the + E be given function, and
(0"()) (g go......... g) (-), (n times).
In order to assess the distance between any two measures P. P.Q (Z), we use the Wasserstein metric. For P. Q E MM (2). X 2 0 and p. 2 1, the X-weighted fy. Wasserstein distance between P and Q is defined as
W P.d (P)Q) &
=||x-xX1 E - X'I + (1 (EC(P.Q)
inf
(2)
where C (P.Q) denotes the set of all couplings μ E x Z, ensuring that / (, 2) P and
(2, = Q. Also, let é: y x y + Rzo be legitimate loss function, where for most of the paper we simply consider it to be loss for simplicity in the results.
2 The Proposed Method: Gradual Domain Adaptation via Hanifold-Constrainee DRO
Let's consider the distribution set G C. MM()) denote class, manifold, of distributions characterized by favorable properties, such as, but not restricted to, having soft or hard margins between class-conditional measures. Throughout this paper, presume that all measures P, belong to such a class with a known property. Failing to acknowledge this assumption could render the error propagation dynamics uncontrollable (see Theorem 3.2) Before proceeding further, let us introduce the following definitions:
Definition 2.1 (Restricted Wasserstein Ball), Assume fixed parameters p.q 2 1 and 0. For N 0, g C M (X' )) and Po E G, let us define
B, (Polg) A { WA, (P, 5m
(3)
G-restricted Wasserstein ball of radius 77.
3

---

Algorithm 1: DRO-based Domain Adaptation (DRODA)
Params: ..,9, S.p.4. and 1)
Input :o, (fixxx
Initialize:
Pg P Po
Eg 6 7)
A:: 0 -
min, argmin) BE BEO
sup PEB (Pols)
Ep (v, (X))..
for i
, T - do
P. Pix (X) y hoz (x)), ((X E z
6 - \A;11 +
4
min, argmin BEB AEO
sup PEB,, (P.10)
[e (v, ho (X))
Result: 0" 07-1
Building upon the above definition, we introduce our method formally outlined in Algorithm The essence of our approach lies in conducting DRO on pseudo-labeles version of P; (or its empirical estimate Pt), followed by leveraging the model to assign pseudo-labed labels to the subsequent unlabeled distribution. However, two crucial considerations emerge: i) the adaptive adjustment of the Wasserstein radius (also known as the adversarial power of DRO) based on the robust loss incurred in the preceding stage, and ii) post iseudo-labeling distributions implicitly constrained to the manifold G. This latter aspect serves as the primary mechanism for controlling error propagation within appropriately restricted scenarios.
Before delving into the theoretical guarantees, let us introduce our new complexity measure, which quantifies the relationship between family of binary classifiers H = {ha }} and the distribution family G. The compatibility function, essentially a bound on the manifold-constrained adversarial loss of H. on G, plays pivotal role in error propagation, as elucidated in Theorem 2.3
Definition 2.2 (Compatibilityy between G and H). Consider the classifier set H. & {hal 0 E }].
distribution manifold & S M (Z), and Wasserstein metric W p.a (---) for p, q 2 1 and À 2 0. We
say H and G are compatible according to function (x(+)= R20 + R20. if for 17 > 0 and VPP g the following bound holds:
9A (n) inf sup lE0 (P
Ep [E (y, he (X))).
(4)
As can be seen, (0) represents an upper bound on the minimum achievable non-robust error rate across all measures within G. Mathematically, this is expressed as:
gx(0) Z sup inf Ep (y. ho (X)) Peg ece
We declare that H and are perfectly compatible if the lower bound on the r.h.s. of ( and consequently (O), is zero. This means for any P E G, at least a classifier in H can perform a perfect non-robust classification.
We believe the concept of "compatibility" as defined above is natural and can uniquely characterize the applicability of GDA to problem set. For example, assume all measures in G exhibit some level of "cluster assumption" or have hard margins, and that H is rich enough to robustly classify all P (with some margin). Then, there exists dg > 0 such that 9x (6) 0 for all 8 < 6g. We will soon see that such a property can perfectly eliminate error propagation, as long as consecutive chosen close enough
unlabeled measures theorem provides a general bound on the propagation of generalization error as a function of the compatibility measure in the asymptotic case where min; n4 30.
function of óg- More generally, the following
Theorem 2.3. For > and p. q 2 1, assume classifier set H A (hol E O) and distribution family G C .M (Z) are compatible according to the Wasserstein metric W (2.(.:)) and positive

---

function (-). Additionally, for T 2 1 assume a finite sequence of distributions Po. Pi....,Pr in G, where W P.A (P.) S 17 for
O.....T' T and a given 1j 2 O. The initial measure Po is assumed be known, however for 2 L, we only have access to the marginals P.x. Then, Algorithm (DRODA) with parameters H. 9, p. X, and 1) outputs 0 = al (Po. (Pix hrT) which satisfies the Jollowing bound:
Ep [e (y, ha- (X)) S 19X (2X + n))
Ep [e (y, he (X)]i OEO (P
inf
sup
where OT implies composition of function u (2)u + 17) on the imput for T times. The input is the restricted robust loss on Po for Wasserstein radius of 17-
The proof can be found in the Appendix (supplementary material). As inferred from the bound, the shape of g사 determines the behavior of the generalization error the last measure. For example, g increases linearly. i.e., if the robust loss increases linearly with the adversarial radius with a coefficient greater than or equal to 1/(2,,, it implies exponential growth in the generalization error. However, if the manifold structure on Ç causes to grow linearly with a smaller coefficient, or behave similarly to saturating (or at least sublinear) function, error propagation In this regard, the following corollary specifies the conditions under which our algorithm provides a bounded error regardless of T. Proof of Corollary (244]2222cnn be found inside the Appendix section.
be kept bounded.
Corollary 2.4 (Elimination of Error Propagation), Consider the setting described in Theorem 2.3 For given hypothesis set H. distribution manifold G. X < and p, q 1, assume the compatibility function 9x satisfies:
9x (T) S "
bU 122 0,
(6)
3X
where 2 0 can be any fixed value. Then, for any T E N we have:
Epy [e (y, hg- (x)) 3
a+
max W P.A (P:...P))
3λ
ie(T)
which is independent of as long as consecutive pairs remain distributionally close.
Theoretical Guarantees on Gaussian Generative Models
In the following two sections, we investigate practical and theoretically useful cases of potentially compatible pairs and H. to achieve mathematically explicit bounds. We first focus on the well- known and celebrated example of two-component Gaussian mixture model, which has been the focus of various previous studies [MLL20 20 CRS 19 AUH+19 19). One main reason that our results can be easily compared with those of prior works.
Mathematically, suppose that the set of features and labels, denoted as (X, E Rd 10, originates from a Gaussian generative model. For some L > 0, we have:
{
-1y= X (ypuoo2)
with |
This setting implies that the class- canssconndiiinal density of feature vectors consists of two Gaussians with equal covariance matrices r² and mean vectors and -14, respectively. The fz-norm of la is lower-bounded by some T, > 0 to prevent the optimal Bayes' error from converging toward 1, thus the classification remains meaningful. Throughout this section, the distribution manifold G, = (T)) refers to this class, with the vector μ as its only degree of freedoo. In this context, our goal is to find the compatibility function 9A (-) when linear classifiers are employed. The following theorem presents one of our main results for this purpose:
Theorem 3.1. For I. > and any X 2 O, consider the distribution manifold Gg (L). Then, the compatibility function between Gn (w.rt. Wasserstein metric wh and the set of linear binary classifiers as H satisfies this bound:
L2
9A (n) Se
Vn E [0, L/3].
Also, for any T E N and any sequence of distributions .i...., Pr G, with WA, (P,, P.+1)= < L/3. DRODA guarantees the following error bound on the last unlabeled measure:
any
Epp [e (y. ha- (X))) < 1802
(10)
5

---

Proof can be found in Appendix Note that there are no enror propagation, and the guaranteed error term is close to the Bayes' optimal error. In fact, can become arbitrarily close with more sophisticated mathematics, which goes beyond the scope of this work. The condition S L/3 is necessary to prevent the two Gaussians from swapping, as tracking them becomes impossible if that happens.
important question consider is what happens gA to the manifold G.- In other words, assume we set Gn to be the entire space of measures and not the restricted Gaussian manifold considered so far. We will show that the manifold constraint key property that provides us with the desirable result of Theorem 3.1 and losing this assumption can have catastrophic consequences.
does restrict the Wasserstein ball
Theorem 3.2 (Potentials for Error Propagation). For L > consider the Gaussian manifold Gg (L) versus the set of linear classifiers X. Also, assume Wasserstein metric W12x being employed, for any X N O. By 9X (-), let us denote the compatibility function when manifold constraint is taken into account similar to Theorem 3.1 while g% represents the unconstrained compatibility function when there are no manifold constraints, i.e., Gg (Z). Then,
UC 20) 9x (1) Se (120(0 E L/3), and 9X
12
m/e
Vq 2 0.
Proof can be found in Appendix section A We already know the generalization eroo from the manifold constrained version of DRODA does not propagate after T' iterations. However, the error term stemming from the unconstrained version can be shown to be bounded by
Eny [e (y, ha- (x)) so ((2xett))
-1 , 222
(11)
which shows significant potential for error propagation.
The results far are in the statistical sense, meaning that have assumed min; n,, co. A slight variation of our bounds still applies to the asymtttpioiic case, where we can propose PAC-like generalization guarantees. The following theorem is, fact, the non-asymptotic version of Theorem 3.1 (proof is given in Appendix A
Theorem 3.3 (Non-asymptotic Generalization Guarantee). In the setting Theorem 3.1 with some > and any À 2 O, suppose we have no labeled samples from distribution Po and n, unlabeled samples from distribution P. for E [T]. T can be unbounded, but consecutive pairs P.. P.+1 must have a Wasserstein distance Wh 2.X bounded by L/3. For any E (0, 1] and using algorithm DRODA, the error in the last (most recent) domain with probability at least
is bounded by:
L2
dllog 27
4L
L2
A < 2e 20
1802
(12)
Tl
Corollary 3.4 (Elimination of Error Propagation in Non-asymptotic Regime). In the setting of 1la (e.g., each component of mean vectors μ and -u are larger than 11a/ /d). Also, assume each dataset P; i has at least unlabeled data points, where
Theorem 3.3 assume
2 O dlog T
for some è > 0. Then, the following bound holds for D1 regardless ofT 2 2:
2
A
2e
26
(13)
&
which means error propagation is perfectly eradicated.
Corollary 3.4 can be directly proved from the result of Theorem
3.3

---

Expandable Distribution Manifolds and Learnable Classifiers
The class of isotropic Gaussians, while a well-known theoretical benchmark, is still a very stringent and impractical case to study. In this section, we investigate a much more general class of distribution manifold/classifeer pair families and provide both asymptotic and non-asymptotic guarantees for this regime. Before introducing our target regime, let define some required concepts. Assume (X, Σ) a measurable space, and let P be a distribution supported over X. For r 2 O, the r-neighborhood of point X E X. denoted by (X) ), is defined as:
(x) {x' ||
X'12 r)
(14)
Similarly, the r-neighborhood of a Borel set A S X (i.c., A E 2) is defined as:
(A) (x' ]x E A such that | - X' sr),
(15)
we also define the 5-neighborhood of a Borel set A C X, for IR as:
(A(A) {x' =X E A, a S 1 such that X' X +
(16)
Following [WSCM20) we define the expansion property as: Definition 4.1 ((C1, C2) expansion). For fixed 0 < a S < 1 and given C1, C2 consider A [A X a < P(A) & a}. Then, we say a distribution P has (C1, (2) -2xxaaniiooonn property if ( (A))
P(N, (A)) ACA P(A)
sup ACA
S1+Cr ((A)
inf
2 1 + C2r,
for sufficiently small 2 0.
This definition extends the (a, -xxxaanssoo property defined by [WSCM2]]. A (Ci, expendadd distribution is required to have continuous support and avoid singularity, aligning with the majority of practical measures. Expandable distributions can be further restricted to have additional theoretical properties, such as e-smoothness, defined as follows:
Definition 4.2 (c smoothness). We say that distribution P supported on a feature-label space Rd {+1} satisfies the e-smoothness property if for all A E A, there exists constant C which depends only P(A), where the class-conditional measures of P, i... pt (X) and P (X). satisfy the following for sufficiently small r 2 0:
1 P ( -1) CA(L+E), v ( 8 E 11812 ST. (P
-
(17)
(A(A)
Another necessary definition ensures that classifier family H is inherently capable of achieving low classification еπгог on distribution, i.c., a low bias for H. and simultancously a small Bayes' error for P.
Definition 4.3 (a- separation). For 2 0, distribution P supported on feature-label set TRd (+1) has the a seperation property with respect to a binary classification hypothesis set H. if
inf (yh (X) S 0) S a. NCH
(18)
We can now explain our proposed setting for the expandable distribution manifold G. which consists of expandable distributions (in both senses of (C,, -ex-essnn and e-smoothness, which are slight variations of each other). The core idea is to use the dual formulation of [BM19] and [GK23 for (non-man mon-maaifold constrained) Wasserstein DRO, which can be stated as follows:
sup Ep [e(0; Z) inf { (m Ep. sup (P))(P))
{ 720
{ z
(19)
To add the manifold constraint, we propose restricting the space of adversarial examples Z' to be generated from predetermined function class F. where for É J we have f Z. Each f is fixed mapping from the feature-lahel space to itself. By controlling the complexity of F, one can limit the adversarial budget of the DRO and effectively simulate the condition of optimizing within
7

---

Wasserstein ball in addition to some kind of "manifold constraint." " Mathematicallyy, we can replace the original dual form with the following (more restricted) formulation:
sup Ep (0; Z)] inf sup (F31)
mr + Eps [te (0: - 70 (c
(20)
720 /EF
There exists (potentially intricate) mathematical relationship between the distributional manifold g on the left-hand side and the mapping function class FF on the right-hand side of the above formulation. Our main contribution in this part can be informally stated as follows:
We theoretically show that restricting the distributional manifold g to include only expand- able distributions, as defined in Definitions 4. and 4.2 is equivalent to restricting the dual optimization formulation such that the mapping class F consists only of "smooth" mappings.
Note that if we do not impose any constraints on F, and f could be any function, there is no difference between the quantities in Equations (19) and (20).
Theorem 4.4 (Transportabilityy of --mooohh Measures). For some 6 > O, let us consider two data distributions Pi and Pz. both of which are e-smooth according to Definition 4.2 Let I and f represent the optimal transport (Monge) mappings between PJ + P and P1 - Pz. respectively. These mappings are also known as push-forward functions, which transform one measure into another. Let J and J represent the respective x Jacobian matrices of the mappings, where dim(X). Then, the eigenvalues of the Jacobian matrices satisfy the following conditions:
1 1 2e < 11+ Vi [d], & (+1).
(21)
Proof is given in Appendix A Essentially, the theorem states that each pair of e-smooth class- conditional measures can be optimally transported into each other via highly-smooth mappings, where the Jacobian of the mapping resembles the identity matrix. At this point, we can present theorem that provides an upper bound for the compatibility function between a distribution class G with expansion properties and hypothesis set of learnable binary classifiers:
Theorem 4.5. For C1. a, O, consider distribution manifold G where its distributions satisfy the (G,, -2)--anunnnonn a-separation with respect to a hypothesis set H. and e-smoothness properties as defined in Definitions 4.7 through 4.3 Hypothesis set H is general up a-separation property. For X, 2 O and T E N, consider the GDA setting of Theorem [23 with a distributional sequence Po....,Py Pr E G where the pairwise distance between consecutive measures satisfies W2,x (P., S v,. Moreover, make the following assumptions: i) assume all of the mass of Po falls inside a hypersphere with radius at most R. ii) assume e S TÂR. and iii) X > n) Then the compatibility function between G and H. has the following upper bound:
9x (n) < O ((1 + C1 (4Rc + 27)) a)
(22)
Proof can be found in Appendix A Based on the bound on the compatibility function, using Theorem 2.3 it can be easily shown that modified version of Algorithm DRODA, presented in Appendix A in Algorithm 3 guarantees generalization error of at most O(a + 1)) on the last (most recent)
distribution Pr, which is irrespective of T, thereby entirely eliminating error propagation.
4.1 Non-Asymptotic Analysis of Manifold-Constrrinee DRO on Expandable Distributional Manifold
This section explores the non-asymptotic amalysis of cranifold-constrainne DRO the expandable distribution manifold. We assume empirical estimates from Pt's, where each empirical measure P. is obtained via n, i.i.d. samples from P.. For simplicity in our results, we assume n4 = n for all i (0, 1,,,,,, T... First, let redefine the loss in its dual format:
R (0; Po) sup Eps. [[ (0: (Z)) - 70 (2. (()))(
(23)
JEF
Assuming R(0; Po) is the empirical version of R (8: Po), let the minimizer of R(0: Po) be denoted as O. For simplicity, we only consider the class of linear binary classifiers and Gaussian mixture models. However, the main distinction between the setting of Theorem 3.3 and this section lies in the
8

---

Fil
Loss
fp
fc
Figure 1: A schematic view of the proposed procedure for our ceterfool--onstaainee DRO, A restricted adversarial block, modeled by fp. tries to perturb the source distribution each step to prepare the algorithm for the worst possible distribution in step + 1. Meanwhile, a classifier fc tries to learn classifier based on the perturbed distribution.
fact that we assume no prior knowledge regarding the Gaussian assumption; only the expandable distribution assumption is considered. other words, there are no implicit or explicit projection onto the manifold of Gaussian mixture models any more. At this point, we present our main theorems, which provide the generalization bound for DRODA algorithm:
Theorem 4.6 (Generalization Bound for DRODA in the Non- Non-asymptotic Regime). Consider the class of linear classifiers as O, and the zero-one loss function as f. The rest of the setting similar to Theorem 4.3 Assume limit F the displacement functions and let Po be Gaussian generative model with mean au and covariance matrix o² Ia as defined in (8) then for e, we have the following gemeralization bound with probahility at least 1 8:
R (0: min R (0: Po) 64,
d log
R
n3
(24)
8
where n is the number of i.i.d. samples from Po and d the dimension of the feature space.
Proof can be found in Appendix A As demonstrated, not only error propagation eliminated, but the generalization error also decreases with increasing
The polynomial-tine convergence Wasserstein-basel DRO programs have been extensively stud- ied (see [SNVD17). Given sufficient assumptions on the smoothness of our loss functions and transportation costs in the Wasserstein metric, the convergence rate of (1/e²) iterations (for any 0) in order to get to the E-proximity of the optimal solution is already guaranteed.
5 Experimental Results
In this section we present our experimental results. should be noted that several existing works have already experimentally validated the first part of the paper which concerns Gaussian mixture models. Hence, our contributions for those parts are mainly theoretical. In this section, we mainly focus the second part of our contributions, i.e., Section
In figure D we illustrate the workings of our method to generate adaptive mappings between consecu- tive distributions and the following projection onto the manifold, which is mathematically modeled by the function space in our formulations. As depicted, the ith step, we perturb the data samples (X, j, (yy;),, E [m:] from P: using parametric function class, denoted as fp, and penalize the extent of perturbation using the following term
(x, - X,l12.
(25)
These perturbed samples are then classified using classifier. Let Le (fp; X1. X represent the cross-entropy loss of the classifier on the perturbed samples. Our objective is to solve the following program:
min max fcec JPEP
La (fp:X.... X,.)
Ifr(X,) - -xyll
(26)
n j=1

---

100%
80%
Accuracy
GDA
Proposed Method
40%
D0
D1
D2
D3
Domain
Figure 2: Comparison of the performance of our proposed method with the GDA [KML20) on rotating MNIST dataset.
which is minimization with respect to the parametric classifier family fc E C, while simultaneously maximizing it with respect to the parametric family of generator function fP E P. In our experiments, 5 kernel in the second
we employed a two-layer CNN with a 7 kernel the first layer and layer for P. We also utilized affine grid and grid sample function in PyTorch, following the approach introduced in 15]. For the classifier family C, we used a three-layer CNN with max pooling and fully connected layer, applying dropout with rate of 0.5 in the fully connected layer. A standard Stochastic Gradient Descent (SGD) procedure has been used for the min-max optimization procedure described in (26).
We implemented this method on the "Rotating MNIST" dataset, similar to [KML,20] In particular, sampled 6 batches, each with size of 4200, without replacement from the MNIST dataset, and labeled these batches as Do, ....... D4. which represent the datasets obtained from Po. ....... , respectively. The images in dataset D, were then rotated by i x 15 degrees, with Do serving as the source dataset and D4 as the target dataset. We provided the source dataset with labels and left D1, D2, D3. and D unlabeled for algorithm. We then tested the accuracy of 0% .8 the outputs of our algorithm at each step-on on D1, D2, D3. and D1, respectively.
For comparison, we implemented the GDA method exactly as described in [KL220) We compared our method to the GDA and detailed the results Figure Additionally, we reported the accuracy of 67 on Do as an example of in-domain accuracy. Our results show that our method outperforms GDA by a significant margin of percent in the last domain D4.
6 Conclusions
In conclusion, have introduced novel approach gradual domain adaptation leveraging distri- butionally robust optimization (DRO). Our methodology provides theoretical guarantees on model adaptation across successive datasets by bounding the Wasserstein distance between consecutive distributions and ensuring that distributions lie on manifold with favorable properties. Through theoretical analysis and experimental validation, we have demonstrated the efficacy of our approach in controlling error propagation and improving generalization across domains. A key tool for achieving this is our newly introduced complexity measure, termed the "compatibility function."
We have investigated two theoretical settings: i) a two-component Gaussian mixture model, well- known theoretical benchmark, and ii) a more general class of distributions termed "expandable" distributions, along with general expressive (low-bias) classifier families. Theoretical analyses show that our method completely eliminates error propagation in both scenarios, and also both asymptotic and non-asymptotic cases. These findings contribute to a better understanding of gradual domain adaptation and provide practical insights for developing robust machine learning models in real-worde situations.
10

---

References
[ABG* BABG+21] Samira Abnar, Rianne van den Berg, Golnaz Ghiasi, Mostafa Dehghani, Nal Kalch- brenner, and Hanie Sedghi. Gradual domain adaptation in the wild: When intermediate distributions are absent. arXiv preprint arXiv22106.60086 2021.
[AUH*19 19] Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stan- forth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? Advances in Neural Information Processing Systems, 32, 2019.
[BM19] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565-600, 2019.
[CRS* * 19] Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Perey S Liang. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32, 2019.
[CWZ+20] Shuhao Cui, Shuhui Wang, Junbao Zhuo, Chi Su, Qingming Huang, and Qi Tian. Gradually vanishing bridge for adversarial domain adaptation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12455-12464, 2020.
[GK23] Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with wassenstein distance. Mathematics of Operations Research, 48(2):603-655, 20233.
[GPAM* + 14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farde Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
[HJ14] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classi- fiers and pac-bayes finite-sample guarantees. In Artificial Intelligence and Statistics, pages 384 392. PMLR, 2014.
[HWLZ23] Yifei He, Haoxiang Wang, Bo Li, and Han Zhao, Gradual domain adaptation: Theory and algorithms. arXiv preprint arXiv:2310. 13852, 2023.
[5) Max Jaderberg, Karen Simonyan, Andrew Zisserman, al. Spatial transformer networks. Advances in newral information processing systems, 28, 2015.
[KML20] Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self trainini for gradual domain adaptation. In International conference on machine learning, pages 5468-5479. PMLR, 2020.
[KRdBG21] Matthieu Kirchmeyer, Alain Rakotomamonjy. Emmanuel de Bezenac, and Patrick Gallinari. Mapping conditional distributions for domain adaptation under generalized target shift. arXiv preprint arXiv:2110.15005 2021.
[SH22] Shogo Sagawa and Hideitsu Hino. Gradual domain adaptation via normalizing flows arXiv preprint arXiv:2206.1 1492, 2022.
[SNVD17] Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint
170:51770000571,,2000
[Wai19] Martin J Wainwright. High-dimensiooal statistics: A non-asymptotic viewpoint, vol- ume 48. Cambridge university press, 2019.
[WLZ22] Haoxiang Wang, Bo Li, and Han Zhao. Understanding gradual domain adaptation: Improved analysis, optimal path and beyond. In International Conference on Machine Learning, pages 22784-22801. PMLR, 2022.
[WSCM20] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2020.

---

[XZLS23] Zehao Xiao, Xiantong Zhen, Shengeai Liao, and Cees GM Snoek. Energy-based test sample adaptation for domain generalization. arXiv preprint arXiv:2302.11215, 2023.
[ZDIZ21] Yabin Zhang, Bin Deng, Kui Jia, and Lei Zhang. Gradual domain adaptation via 2021.
self-training of auxiliary models. arXiv preprint
[ZZW233 Zhan Zhuang, Yu Zhang, and Ying Wei. Gradual domain adaptation via gradient flow.
In The Twelfth International Conference Learning Representations, 2023.
A Proofs for the Theorems and Corollaries
Proof of Theorem 2.3 The proof follows an inductive approach, relying the steps outlined in Algorithm| I (DRODA) To enhance clarity, we initially delve into step component of the induction. Subsequently, we proceed to establish the base case.
,, i, assume hog guarantees an error rate of at most Aj-1 on Pj. Then, our aim in this part of the proof is to show that:
Step: For all j l....,
hog also guarantees an error rate of at most A on P.+1-
We have A S 9A (2 +
Recall that for all = 0, ,,....22 the marginals of P. and P. on X are the same by definition. Hence, we have
W3 (P.x, Pix) 0.
The conditional distribution of label given feature vector X according to P; is denoted as P: (-IX). However, again according to the definition DRODA the conditional distribution of labels given feature vector X for P. is
1 t= 1-= h (X)).
Let us define Q as the set of all couplings between the two above-mentioned conditionals, i.c., P. (+IX) and 1 hæ: (x) In this regard, we have
WH P,, Wy (Pxx:
inf Ep.y E, (1 x < AA WE
(27)
Due to the triangle inequality for Wasserstein metrics, have W P.A P.+1) s Wa P.d (P.. + W (P,, P+1) S AA; + Consequently, having defined E, A 1 + 77 as in the algorithm, and noting the fact that due to the theorem's assumptions we have P.+1 E G, guarantees that P.+1 E Be, (P.ls). Therefore, we have
(28)
Ep... (yy, ha: (x)) < A;
(29)
On the other hand, we have the following useful inequality for the Wasserstein balls centered on P and P,, respectively:
BAA (P11)) C Be (P.g)),
(30)
which again directly results from triangle inequality. Therefore, we have
inf BEE
sup
Ep (y, ho (X))
B + (P(18)
< inf 0E
sup (P.11))
Ep _e (y. (X))
< ga (2A4;-) n))
(31)
and thus A 9x (2A11 +1) which completes the step part of the induction.
12

---

Base: After the initialization step, B represents robust classifier that is guaranteed to have an expected enror rate of A S 9사 (1) on all probability measures inside Wasserstein ball of radius r) centered on Po. This also includes P1, since we have
W P.A Po) S 7
According to DRODA, P1 denotes a measure supported over Z whose marginal on is the same as that of P1. However, and similar to the arguments in the previous part of the proof, the conditional Plyix has total variation distance of at most ^Â from that of P,. Recall that the centure-oonditioned distribution for labels in P1 is deterministic rule represented by heg X + y. In mathematical terms, the error rate on P1 is guaranteed to satisfy the following upper-bounds
Ex, [e (v. hog (x)) = A - 9A (n).
(32)
which completes the base part.
End induction
Combining the base with the step, one can conclude that:
inf Ep (2, he (x)) S 9 (214 + +1),
AE
A T-1 S 9 22
A - inf BEG (P
sup
Ep [e (y, ho (X)))
(33)
Additionally, ga (.) is increasing function which directly results from its definition according to Definition 2.2 This completes the whole proof.
Proof of Corollary 2.4 Recall that a represents value independent of n,, which in fact indicates the loss of the best standard (non-robust) classifier. In general, assume we have
91 (n) S Bm + a.
for any fixed a, B 2 0. Then, it can be simply seen that we have
gA (2)gx(1) + r) S g사 (2 - + 2Aa)
dx ((1 + 22,3) 2Aa))
< 81 + 2x,) + (1 2A3) a.
(34)
By induction, and assuming 2X8- < 1, we have
[ox (2A (-) + Or)
OT (n) 5
Σ (2A3))
(37)
1=0
(2X,)²
(B1) + a)
1 -2x
Bn + a
(35)
2A/3"
Substituting with 3 = 1/ (3X), and considering 17 as a bound on the distance between consecutive distribution pairs, the result of Theorem 2.3 gives us the inequality and completes the proof.
Proof of Theorem 3.7
To prove this theorem, we first need to determine the restricted Wasserstein ball for any distribution in this class. The following lemma provides super-set for this ball:
Lemma A.1. Consider distribution Po E Gy with parameter Ho- Based on Definition 2.7 we have
By (PolOn) C (Pp || Polla S 2n V 1| + Halla S 2n)
(36)
where Py is Gaussian generative model with parameter μ.
13

---

To prove this lemma we need the following lemma:
Lemma A.2. Consider two arbitrary (and not necessarily Gaussian) distributions P and Q on Z with respective densities fi and f2. Also, assume P(y = =) Quy 1) 1/2. Let e: X² - R be a proper and lower semi-continuous transportation cost defined in the space of features, i.., X. For any X 2 0, let us define è : 2² + R
8 X. x' =)))))((XXXx) + +1 {y
(37)
Then, the following lower-bound holds for the Wasserstein distance between P and Q with respect transportation cost i:
We (P. Q) 2 We (2)
min EE(#)) sE(=1)
max
We (fi (t) 1))
(38)
The proof' for the above lemmas can be found in section B
Now, we aim to find an upper bound for the compatibility function gx (-) between the class of Gaussian generative distributions and linear classifiers.
9x (1) = max S 05iST
max inf sup 0SiST BEO (P.1())))))
Ep (v, ho (X))
< max inf OS DEG Pullly- 2|
sup
Ep, (v, ha (X))
(39)
we consider the (0 - 1o-soss function and the set of linear classifiers with d-dimensional vector
w, where ||w||2 1, then we have:
L E he (X)) = 1 (y(w, X) S 0)
(40)
hence we can write
E pp (e hg (X)) Pa (ulws X) s 50) PA x)w, =0) x(w.X) N (wwrett,
(41)
We know that (X, v)
PH then
Therefore we can extend
inequalities in (39 as follows:
9 (n) S inf
sup
Ep, [e (y, ho (X))
1E Paella Moll $2
(w (w: p1)
sup ( m:ll w:llu--oll1:20
inf
Q
(w, (w.Ho)
(w, v)
inf WER':||W
sup
vER
S2n
σ
|Poll2 l|2
|
sup
||10l22 l2
21j
(lleally_20 2n)3
<e
2
(42)
where the last inequality is true we have:
|
r S
(43)
2
Due to the above inequalities we have that 1 1 then we have the following:
22
9x (n) S 1877
(44)
14

---

Based on the above results if we use Algorithm I (DRODA) when the distribution class G, is the class of labeled Gaussian generative model we have:
Ep, [e (y. hg. (x)) - Lax (2x() )) (n) Se 18x2
12
(45)
where the last inequality holds we have:
L
22
2
12
We know that the error of the Bayes classifier in the target domain in the scenario of this example is equal ee
lar
There a point here that we should note. According to Lemma A.2, the last inequality in 33 is not entirely correct because it is possible for the labels of all samples to be multiplied by -1. To address this problem, we slightly modify our algorithm and replace the risk function as follows:
R (P, 0) Er (y, ho (x))) R (P,0) min {Er-(e [E (v, ho (X) (X)), Ep (- (x)()())) (46)
we change the risk function as the above equation, we have:
9 (n) inf sup (Polg)
(P,0)
inf sup Pu:l|p-- $2nV ||tt 2g
R (PP.::)
inf max
sup
R (Piu.. 0)
VE0 16(-1,11) 1-..1.11Pppplllle Ppllisp-MM11 212
min {o ((u..it)) ) e (-(o--j)) }
inf
max
sup
WER": | 1|2 LE 1-1,11 Pa:llip pel 1111
(w..11))
inf
sup
WER":|WWll 1|2
Paille
(1.))--9.)3 262
<6"
(47)
The above inequality means that the result of the algorithm DRODA, with this new risk function, on the ith distribution has error less than 9 either P.+1 P.-. Here, P refers to the distribution P: with its labels flipped. On the other hand, from the definition of Wasserstein distance in for the class of distributions here, have:
W P.A (P;, P.+1) = W P.d
(48)
Based on the above statements the error of the output of the algorithm in the target domain can be described as follows:
12
min Er,, [e (y, ha- (X)) E,,, (e(-y, ho- (X))) S
1802,
(49)
This implies that if we consider the labeling by the algorithm or multiply this labeling by -1, one of these two will have an error bound as described above in the target domain. If we have one sample in the target domain, we can choose the better classifier between these two with high probability.
Proof of Theorem 3.2
For the constrained version, the proof is similar to the one in Theorem 3.1 Here, we present the proof for the unconstrained version of the compatibility function.
Due to [M19 and [GK23 know that the following holds for conntinuous & and
sup Ep le (P))(PP)
(e,E,, (y, he (X)) = inf
77 + Ep.
{E hi (X)) - >||x X'112 Arly - 2/11 X'.v'
sup
720
On the other hand If we set À = oo it will give a lower bound for the above quantity.
sup le ho (x)) inf (Po)
?37 + Ep
sup {f (X)) >||x X'112]
(50)
720
x"
15

---

The Problem is that the (0 -loss is not continuous. To Address this problem, we introduce modified version of the (0-11)-oss, function. Let us define the (0 1]-loss function for the class of linear classifiers as follows:
e (y. ho (x)) (yhg (X) - 0) = (v X) = 0)
(51)
Now, we define the modified version of the (0- -losss function, La,s, as follows:
(1)) max -- -0, e (2) = min(fa,p }}. a (y. ho (X)) Pa. ()).
a
(52)
From the above definitions, it can be seen that la--a is continuous and always less than or equal to the (0- - I--ssss function. To provide a lower bound for gx we consider the scenario where À = oo and replace the (0 ll-loss function with fa.-a for some small positive a.
UC (n) inf sup gx
Ex le (3, ho (x))
0E PP
> inf WEe (P,)
sup
Ep la (y, ho (X))
}
= inf inf #EB x20
717 + Ep,
max X"
{ {la,-a (y, ho (X)) - (x)
(53)
Now suppose that (X, x') = || X'112 and 7 S 1. then we can continue the above inequalities as follows:
UC (n) 2 inf inf
7!) + Ep
max X
(la,-a (v, ho (X)) - vcll - x11a)]
OEA 720
inf inf AE0 720
?!l) + Ep, [f1/7-- (U. ho (x))
inf +20
+
+
20
4
[1ully (a))
20
E
(54)
The above inequality holds for all zero. On the other hand if in some step i we have 14, = then we have:
27
Therefore, the bound is valid as we let a approach
Anj
(1)
+ 1
(55)
A very important point of Theorem 3.2 is that, constraining the Wasserstein ball could significantly improve the compatibility function gx. For example, if we do not constrain the Wasserstein ball and use g for the gradual domain adaptation, we can not guarantee a good upper-bound for the expected loss in the target domain, and if we use the proposed algorithm in this situation apper-bound will be worse than the following in the target domain:
Epp [e (y, hi- (x)) < [o (2X + + OT
inf sup 8E0 (PB)
Ep [e (v. he (x))
12 (2xe
L2
0
n2 + e20
(56)
16

---

Algorithm 2: Non-asymplotie DRO-based Domain Adaptation (DRODA)
Params: G 9.9.1 S.p.4 and
Input :o, (r(Pixhee
Initialize:
Eg 8 7)
Po P. [
4g 0 ー
min, argmin lee DEG
sup P=N PuNuu Taa) 11w-Ball SEo
Ep le (v, he (x))).
for i
T ,,...,
do
P: - Pix (x) y= hoz (x)), ((X E
i0; -- pp [y
dlogg
11,13 20
6 11 Vo n4
+ oe
(1+A7-) 17-1)
A, min, argmin Wee
sup
Ep [e (y. ho (X))].
P=N P=NNuNO''
|| $5
Result: 8" x- 07-1
where, by increasing T' the upper bound will be independent of 17. On the other hand if we constrain the Wasserstein ball and use 9 for the gradual domain adaptation, we can guarantee an upper-bound good the following for the expected loss in the target domain:
Ep, [e (y. ha- (X))
S [o (2X + +)] OT
inf 1E0 (PB)(Po)
sup
Ep le (y. he (x))
Illu 201 20
$ 0
(57)
And the proof is complete.
Proof of Theorem 3.3 To prove this theorem, first present the non non-asymptotic version of Algo- rithm DRODA in 2 As can be seen, we have made some modifications to the algorithm in [ to make suitable for the non-asymptotic regime. The main idea that, since we know the class of distributions are Gaussian generative models with different means, in each step we define ball in which the mean of the distribution P. contained. To do this we first bound the distance between jú: and μe; is the mean of ith distribution.
and n. Where ū. is defined in the algorithm
li M,l12 11 EP [dd + Ep,x [R.]] 14,12
$ 11; Ep,
[ lla + ||P,, [7, 14112
II.
(58)
To give an upper bound for I and II in the above inequality, we should first analyze the distribution (. v) P.x. 1g he: (X)). According to the theorem, P. is Gaussian generative model with mean μ4 Thus, if (X,y) ~ P., we have w = yx ~ N(,,, o² Ia). Also, we know that hag is a linear classifier with parameter 0- and error A, We know that, म. = Ep, [y E [A.].
17

---

Therefore, we have:
i4 Exx (sign (10 x)) X]
1
ENiM, (sign
Isign (1 x)) x] + BNi BNI-n, sign (10) x)) x
2
2 RNii, sign (107-1: x)) X] + 2
BNiu sign (107 (-x))) (-x)
BB sign (0) x)) X
Ex((, sign (10 (H4 + ou)}) (Ms: ou)l
p4 L.) (sign (00 (14: ou)))) laig (10i-1: (14; + ou))) u]. (59)
where for the first term in the last line of the above equations have:
Ex(o, [sign (0 (M4 + ou)))] = EN(H, (sign (,
PM. (10) X) > 0) PM. (107-1: <0)
1 2P', (10 X) < <0)
1 2P. (v(0f-1, x) <0) 1 2Ai,
(60)
where in the above equations PA., a Gaussian probability distribution with mean μ4; and Covariance matrix I² Now we should compute the the second term in the last line of equations 59 We know that mean Isotropic Gaussian random vector with identity covariance matrix is rotation invariant, therefore we can write u ug67 + ug. where ug N(, 1) and us N Ia-1)) where 0- is vector with norm 1 in the direction of 07-1 and ug belongs to the subspace perpendicular to the - and up is independent from ug Now for the second term in the last line of equations 59 we have:
Ex (sign (10711 (M, ou)))) u] -E [sign (107-1) + tua) ui]
ETLIE |sign (0 m4) + oug) usl 1) Ex (sign (10) H4) ous) us
0 1 (0 14) + ouo) uol
E (sign ((0 (4) + owa) |NN 1) |ut]
0 E Isign (0) m4) + oug)
ugl + 0
(0%-1.14)
up
ug ug 1
0; EN(O,1)
197_1 .4.2
0
(61)
where in the last line the fact that if ug has normal distribution its conditional distribution Ug > (01)) and ug < (02-1111)) has truncated Gaussian distribution. Now we can continue
equations in 59 as follows:
2a²
2
3. 14 (1, (1-11-20 (1-24r) -
(62))
and for in equation 58 we have:
189 199))
20a
V
20
j. H:ll2 -4, 22,11144112
(63)
1 -
A
18

---

Now we try to compute I in equation 58
For μi we have:
74 T4 sign (()= x
1
n1
P.
(64)
n4
j=1
where Xj ~ Pix come from mixture of two Gaussian distribution where their means are in H4 and - Ms On the other hand distribution of sign ((==1: X; is not different when we have X, ~ .V' (Hi, (2 from when X; ~ -V (-H, oa.). Therefore distribution of Zj = sign (107_1, x))) X; when X js are come from Pax is not different from when x,s are come from N (14, o² TaTa). For simplicity in the rest of the proof we will drop the subscript j and use Z, X instead of Zj, x respectively. Now for the variable we have:
PP Z 10 > 0) = X 10 X) 200 0)
= TP (1 + oul (0 14) + a (0 4) > 20)
(65)
Now suppose that we rotate the space such that the 07 align to the first dimension of the space. We know that the zero mean isotropic Gaussian is rotation invariant, therefore by this rotation distribution of u doesn't change. So we have:
P Z 1) > 0)= = P + oul oulue1 p01 tuu > 0),
(66)
where H4g the rotated version of μ., and Joi and U1 are the first dimension of f4 and u respectively. Due to the above equation if we name the random vector with distribution (Hg + ou (fo1 + duu > 0), o. its first dimension is a truncated random variable and its other dimensions are normal random variable and all of them are independent from each other. Therefore due to (HJ14) and [Wai19] 7 [o0] |12 is a sub exponential random variable with parameters
(8v do 40²) With the same method the random variable with distribution P (0;-1, X) 0)
sub exponential random variable with parameters (8vdo?, 400) Therefore we have:
Z = (1 A-)
(0 1 > o| AE [ A1 2 (0 X) < 0
(67)
and 2 - E [2] 12 is sub exponential with parameters (8vao2, So with probability more
than 1-6 8 we have:
d
1 z
114 Epix [
112
<B
[|[;:
Ex,x
[7.] [12]
+ 0
log
14
2o²
1
0²
log
x)
(68)
and therefore:
(0) 144
d
1/2
202
2n²
11 - Hill2 S Vo
+
o
log x
+ 22 1111
nTi
1 A;
log 1
1/2 + +20,11m411 +
202 122
o
e i02
n44
(69)
Based on the Algorithm
2 we have:
A = min
sup
Ep [e (2, ho (X))]
dEB
P=N
|| R.l
min
sup
Ep [e (3, ho (x))
0E0
P=N(
|| 1M- S5,+E
1? <e 1807
2L
d
d
1 ]
1
-
12
1
V n;
+
log
+
22
+
(70)
ni
19

---

Therefore for the error in the target domain we have:
1/ Σ
L2 dlog
27
4L2
L2 1857
A
2e 20
(71)
74
σ²
i=1
And the proof is complete.
Proof of Theorem 4.4 Since the proofs for both f and f are the same, we ignore the superscript and denote both functions simply by f. It should be noted that f X - X. and we have dim (X) d.
for any given point Xo E X' and E [d]. let u, (Xo) denote the unitary direction vector of the ith eigenvector (without any particular order) of the Jacobian matrix of at position X Also, let X, (Xo) represent its corresponding eigenvalue. We drop the input argument 2g throughout the remainder of the proof, for the sake of simplicity.
For sufficiently small A > O, we consider a d-dimensional Parallelepiped that has the following properties: i) it contains Xu, ii) its edges aligned with u, (Xo)s for i [d], and iii) the probability mass inside the Parallelepiped according to P1 is A. Let us call this Parallelepiped A (Xu). Again, we drop Xu for simplicity throughout the remainder of the proof.
Hence, for j (1, the probability mass of with respect to Pj can be written as:
(A) P (1x X E A)) = -))=
a, (x(xxx
(72)
where dj represents the density function of P, with respect to Lebesgue measure. Suppose Ā the image of A under the function f. For P1 and P2 satisfying the e-smoothness property and vector E X' with | I r (for sufficiently small r > 0), we have
(NLIA) (xX))X 15 ((
C(A)
SA di (X)dX
())) (NS(Z) dx(X)dX
(xd2(X) - -ISC(A)(+orr
(73)
On the other hand, due to the fact that P2 f4Pi the following holds:
JASC dx(X)XX = - di (X)dX (r²) v6 X,
| Sr.
(74)
In the above inequality, the first order of appears in the volume over which the integral calculated. This incquality directly results into the following bounds:
SNG(T)do de (x))x
(1-
dad2(X)dx
(A) di di(X)dXX
-1+
SA (X)xX
A
2
SC(A) (1+ +o
(A) di(X)dX -1
C(A)(1-
JAd1(X)dX
SNG(A) dx(X)
-1+0
(x
A
p
3 <C(A) +err +0
(75)
A
Now based on Equations
73 and 75)
we have the following:
2c
^
r
51+ O
Vi (1.....d).
(76)
20

---

If we set r = Ac² then we have:
1- 5 2e, Vie (I...,,., dd
(77)
And the proof is complete.
Based on the result of Theorem 4.4 we know that if Po and P1 both have the e-smoothness property and P1 f+ Pu. then the eigenvalues of the Jacobian matrix of f should not be far from 1. Therefore, if we define F as the class of functions with such Jacobian matrices, then we have:
Proof of Theorem 4.5
sup Ep le (v. h (X)) (Pol))
sup
Ep [e (y, (X)),,
(78)
(P
where B, (PolF) is defined mathematically as follows:
B, (Po1F) 2 { P F,W4 P.A (P.P) sm]
(79)
Now suppose that for point Xo R we have |Xo (Xo) 1 A. In this case, we have the following lemma:
Lemma A.3. Suppose that is fanction where the eigenvalues of its Jacobian matrix have the following property:
1 1 2e S A S 1 + 2e, Vi E ff....,,yy d},
(80)
and there exists some point Xo E RRd where | - (X 0) 112 A, then we have the followings:
[f (X) X] 112 こΔ 2cE ||| Xol22]
(X) X < + 2Rs, vX |X -Xoll
2 - R
(x) - X AΔ 28c, VX XX- -Xole $ R.
(81)
Now based on the result of Lemma A.3 if we have E [||X - Xolla] S R, then we have the followings:
A 2R < [B
X] l|2 S
max inf +E(+1,-1) MEC(P- Q*)
IE [ Y11
(82)
where Q is the distribution of Y f (X), and ps P ( yy 5).
On the other-hand due
Auxiliary lemma
A.2 if > 77 then we have:
1 max
inf
E E[ - -
< inf MEC(P.O)
B[J Y 5 Sn
(83)
2 2x((1 (EC(P..
Therefore we have
A 2m + 4Rc
(84)
Now suppose that h² is the classifier with minimum standard error If we assume the region of the space where this classifier misclassify as A and the distribution has the (C1, C2) expansion then we have
inf sup Ep [e (y, h (X)) SPo (Namar (A))
NEH (P.1)
< A P(A)
I (1 + C (ARe + +2m)) a.
(85)
And the proof complete.
LC (Pl (, 9) is a function that changes the label of a set whose measure, according to P, is at most A, so that the resulting measure falls into the G class
21

---

Algorithm 3: DRO-based Domain Adaptation For Expandable and Smooth Distributions
Params: : :0,9. 8,p,4.4 and
Input : Po (xx J1:T
1:T
Initialize:
8o 6 7)
P
Po
A: 0
min, argmin) BE DEA
sup (P
Ep [e ho (X)))-
for i
1,..., T - 1 do
P; - Pix (X) y = hoz (x)). ((X,0) E z
P, - LC 1
6 2A +1
0;,0;
min, argmin BEB IE0
sup (P.12)
Ep le (y, ho (X)))
Result: 07-1
We show for each 0 O, RCDRL (0: PP) is converging RCDRL (0: Po)- Assume F is the family of displacement functions; i.e. each f E F is moving all the points within fixed vector 8. suppose we have n empirical samples from Po named 21, #2,...; 2n- Also Suppose S+ contains indices of positive class samples and S similarly for negative class samples. Then
Proof of Theorem 4.6
RCDRI. (0:Po)
sup JEF
fg. 0) yo(2,, fu. (x.))
1=1
sup
Σ NEst
((0,61 + x;)) 0) --1152 l1
b
Σ ((06) +2,)) > 0) - >1662
+ sup
n
JES-
Now just focus on positive class samples and we know the underlying distribution for each sample is according to Gaussian distribution with parameters (n, I2). It is obvious that for each 6, the supremum maximized when d is in the same direction A. Then without loss of generality assume ||0]|2 = 1 and define m == | and == (z,, 0). Also assume m = 2 with high probability. Hence we have:
1 m
sup Σ 1(0,0+ <) >|10|12
suu 120
# (p: t)
71
(86)
m
NiES-
Now we consider RDRLL (0; Po) for positive class samples the above expression would become:
sup Pol X²) < - yt 120
Note (0, X,) is one dimensional Gaussian distribution with parameters ((0, (i),o²) and we denote it's CDF with (x)). Using derivatives we have at the maximization point:
(t - ())
exp(
2
202
Then the maximization point is:
= (0. + g0 2log
22

---

Note /. = (0, - -a / 7V2nσ doesn't make the expression maximum because that point
increasing / will increase the expression. Also note y >
V2m02 the supremum doesn't exist which
means the optimum case is not moving any point.
Now we can use the uniform convergence of (x( and (X)). We have with probability at least
1 8:
#p: < Pol(0, X,) <d S VV
log(m + 1)
2
2 6
2
4m
sup 120
+
log
41
log
m
m
m
m
8
Then for fixed 0, with probability least 1
we conclude:
# (111,00 0) < 1) - x6)
2
4m
sup (20
sup (0, X;) r] -1)
<8
log
m
120
m
Therefore we can conclude for fixed 0, with probability at least 28:
RDDR (o) RCDRL (0: Pu) 32
1
log
2n
n
Now we can extend this bound for all A E ④ via quantization on 0. Assume that all of data points are inside R-Be R-Baall with high probability. if ||0 - 02ll < e, [Z, 01) (x,, 02) < ef and the close-fomm answer of suptzo (Po (0, X,) < t] - yt) differs most μe S eR. Hence, with e-covering of O we conclude with probability 26 for each 0 E O:
AA E O: CDDL (0; Po) RCDRL (0: Po)
< 4cR + V
1
dog
1 + 2
log
2n
d
R
n
64
log
d
11
B Proofs for the Lemmas
proof Lemma A.7 To establish this theorem, must show that we have two Gaussian generative
models, PH, and Pay. with densities f1 and f2. where 1|,, *22l2 2 Ç, and || + #2ll2 2 Ç. then the Wasserstein distance between these distributions has non-zero lower bound. Building the result of Lemma A.2 if we set = 2 and = 1, for any À 2 0, we have:
W. (fi
min WA (fix f2x11=1)
2 Ajj(-1,.
2 min (1lm, 12112, + Hallat
(87)
2
This concludes the proof.
Proof of Lemma A.2 The Wasserstein distance between two distributions P and Q which are both supported over is defined as
Wa (P.Q) 2
inf PER(P.Q)
B(x,,,x' X'
(88)
where Q(P, Q) denotes the set of couplings joint joint distributions) on 22 that have P and Q as their respective marginals. Based the above definition, the distance between Pas and Put, can be
23

---

attained via the following formula:
E VX ddxxxx
We Pp,)
inf pEl(fe.f2)
(89)
inf pen(fitta)
Σ
6(X,
1)xxxx
+ 1 Σ /
-1; -1,'' x/ --
where due to the definition of Pu., we have that (x is the density function of Gaussian distribution with mean 7/41 and covariance matrix I²I. (89). we have the following set of constraints:
I. Regarding the density function in equation
1) f2(X' 1/)
p(x', 3 xx 1)dX
+ 2 / p(x
= - 1)dX, VX',
(90)
11)
Σ
,(x 'X x =1, XX.
(91)
VE(+1)
ii)
Σ
p(XX' xxxx:x/x.y==)jxx'' VX.
(92)
vE
Let us define non-negative function أ as follows:
,X, X' 2/) A 1 p
X,
+ "X'''' D''' X .y= 1).
(93)
fi
should be noted that أ may not even be probability density since it may integrate into one over all possible values of X, X' and y'. In any case, for this function (i.c., p), we have:
(x) /
1)dx = f2(X', v/),
VX'.
(94)
/ X s/dx' ( 1+
fi y 1) fi(X -1) VX
(**)
Σ VE(+1)"
(95)
Therefore, if there exists joint density p that satisfies the set of constraints i). ii) and iii) (respectively defined in (90), (9.), and (92). then there also exists a function ý that satisfies the set of constraints in (+) and (**) as defined in (44 and (95, respectively. Additionally, since we know that fi is non-negative function, we can further relax the conditions as follows:
J (XXXXX'1))11XX 1)dx 2 ((X','), VX'. 1 > 2' VX.
(96)
Σ 8'E(1))
/ |(xx X'X,X',8)dd
(97)
Therefore, the constraints in 166 and 97 are relaxed versions of the constraints in 90 and 192b. Let us denote the set of all non negative functions á that satisfy the (newer versions of)
9T)
24

---

conditions (*) and (**) with II. Then, we have:
We (Pr,, Prn))
inf p)(( 2
1
Σ
-)dxxxx 1)dx
y/
1
- -Ixxxxx
1)dxax
2
inf pES(J1N(2)
1 2
1
Σ
/
x/ 1)xxxxx
Σ/ / x/,,x//XXx -Idxxxx
2 V
A
(olv' = -1/y = 1) + p/u = 11y -1))
2
inf pe((Je.ta)
1
Σ
/ c(x,
2
y'
1 2
Σ
/ (XXXX'))(( xx,= -1) -Iddxx''
which due to the definition of II and its discussed properties imply the following bound on the Wasserstein distance between f1 and fz:
We (PH Pm2)
We (fi, f2)
E/ /
inf pell
= 1Jxxax'
/ ((xxxx)) Exxx, 11X 11dxxx
inf AEll
/ xxx
inf
(98)
Aen
where ,(X, X') is defined as
XX,X') & Σ _x(xx'1)
(99)
The rest of the proof proceeds by trying find proper structure for IT. In order to do so, let us define @h as the following set:
r A
Σ
Σ is (155))
p1, E II
c RXXX
(100)
(E(1.2)
Then, can be readily seen that the following bound can be established:
Wa (PM, Pw.)) 2 We f2)
I fxxxx's(xxx)xxxxx 1)dxdx'.
> inf cetTo
(101)
25

---

Also, we should keep in mind that each ( in II has the following properties:
A<Ell & + +2,,002 :I: ((x,X)
E Ex vx, (102)
ve(+1)
1) / (xx
Σ (xi 12) + + (x.X 1)dx 2X'),'), AX',
D'E(11)
ii) f((x
/ (x) V'((1)
Σ
+ (x.
AX,
which hold due to (96) and 197. Now, we define two more sets, denoted by II_,II II, C R according to the following definitions. For {+}, let us define:
vy E II, E E (X.X')
Σ ,(x,'')))
V'([=))
E 8" V"E(+1)
X(X X', ,'" (1)[(((()))) 1)dx 12('' A
Σ ('E(1))
p(X,X'
x dx 21, AX.
(103)
What remains to do is to show that for any in 11 there exists at least pair {-- E x II,
such that Ç 2 (E- + ++)+ 22 everywhere in X². This can be easily verified by seeing that since
have:
2f2 2x²) = f2 X f2 (X' (X'ly= = -1)
(104)
the constraints for Ç E @ which are derived in (T02) always hold for average between any two members of the due (11), Therefore, we can further bound the Wasserstein distance between fi and f2 via the following chain of inequalities:
Wa (PM, PwL) 2 W. (2)
(105)
/ [( XX), 1)dxxx
- inf pen
1 inf
/ XXXXX')X(X X (X
2 CElle
1 inf
f /(xx,') X') ( Xxx,, fi(1 1)dxax
2 (+T(TT=)
2 sE(=1) selt. / x(xx,'' X') l)dxdx'
1 min inf
For any E {+1). E, (X', X) acts surrogate for p [X' |X|X, yy=11,y =) where P 9 (21,
However, the marginal and normalization equality constraints, i.c..
f 1, =) fi 1)dX f2 (x'lw'
( 1,
(106)
have been relaxed and, in fact, replaced by inequalities. However, since the optimization problem
infçen, linear program with both linear objective and constraints, the optimal point (if exists) always occurs at the boundaries of the feasible set where constraints are active. The objective is
26

---

non-negative and thus bounded below, thus the optimal point exists. On the other hand, neither of the constraints are degenerate and hence they all become active. Therefore, we have
(1w0'=))) = =)) (107) / fo(x, XxXX 1)pdd = = (fi (-ly 1- 12 f2
inf gell.
and as a result, we have
We f2)
2 min ( = We (filly 12, = -1))) (108)
Also, it should be noted that the whole proof can be re-written from the start with fi(-Ww = -1) instead of conditioning on = 1. Therefore, the final bound can written as
min We (fi (lv f2 f-1 = =)), Wa (Ji, f2) 2 2 sE(11) jE(11)
max
(109)
which completes the proof.
Proof of Lemma A.3 We write the Mean value theorem for the function f around Xo we have:
(Xx / (Xo) , (x') (X - Xo).
(110)
where J (X') the Jacobian matrix of f in X', and X' a point between X, and X. From the properties of J f in the lemma, we can continue the above inequalities as follows:
(X) X = (Xo) Xo + (J, (x') Ia) (X Xo).
(111)
where L is the d x identity matrix. Now we have:
[x] - x 2l 2 (Xx) Xol2 E [J, [x) -xo]] l22
2 A 2cE ||| Xol12].
(112)
We also continue equation
follows:
(x) X||2 S /|ʃ (Xo) Xoll2 + 2e| X - Xoll2
$ + 2Re,
(x) - 2 2 (Xo) -Xoll2 20 Xoll2
> A 2Rc
(113)
Which completes the proof.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide our theoretical and experimental results in Sections
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals not attained by the paper.
27

---

2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations and conditions under which our results are valid in each section separately.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specinf well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e-g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:
[Yes]
Justification:
We present the assumptions needed for our results in Sections 2 and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
28

---

Answer: [Yes]
Justification:
We provide this information in Section S
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Ye]]
Justification: Our supplemental material includes all our codes, and we cite the data we used for our experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips cc/
public/ wwblic/guides/ httae//ggiiiee/ooeuubmiisssee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //ipps.ccppul http:pppwwippupieeeeeeeeeeeaaaaa
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
29

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We provide sufficient amount of information about these details in the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We provide this information in Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide these information in section
30

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics atttps://neurii httprrpp....pbb..c//.cccccaeeee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
31

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We cite the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
32

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "7RCKfSXWSO", "reviewer": "Reviewer_FbyN", "summary": "The paper presents a new approach to gradual domain adaptation using distributionally robust optimization (DRO). This approach provides theoretical guarantees for model adaptation across successive datasets by bounding the Wasserstein distance between consecutive distributions and requiring that these distributions lie on a manifold. The theoretical analysis demonstrates that the proposed approach controls the error propagation and improves generalization across domains. Additionally, the analysis of two specific settings shows that the proposed approach eliminates the error propagation completely.", "questions": "- Could the authors discuss possible extensions to non-binary settings and settings where the domain shift is applied to the joint distribution (Z) rather than the marginal (X)?", "limitations": "- The limitations appear only in the form of the assumptions required for the theoretical results to hold. Discussing the implications of these assumptions would enhance the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is well-written.\n- The considered problem is timely and important.\n- To the best of my knowledge, the proposed approach and the presented theoretical analysis are new.\n- The presented theoretical results, especially those on error propagation, are significant and have potential practical implications.", "weaknesses": "- Although this is a theoretical paper, the experimental study is very limited and hidden in Appendix D.\n- The relationship to existing work, both the classical theory of domain adaptation (e.g., [*]) and on gradual domain adaptation, could be clarified. Specifically, the only work mentioned on gradual DA is [KML20].\n- The paper could benefit from thorough proofreading. For example, there are broken links and missing references (e.g., lines 126 and 186).\n\n[*] Ben-David et al. A theory of learning from different domains. Machine Learning, 79(1):151–175, 2010.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive feedback. We have addressed the remaining concerns as follows:\n\n**Weaknesses**:\n\n- **Although this is a theoretical paper, the experimental study is very limited**: We have expanded the experimental section significantly (please refer to the global rebuttal and the attached PDF). We tested our method on a real-world dataset used in the [KML20] paper and achieved superior results. These additional experiments and comparisons will be included in the camera-ready version.\n\n- **The relationship to classical theory of domain adaptation (e.g., Ben-David et al.) and on gradual domain adaptation, could be clarified. Specifically, the only work mentioned on gradual DA is [KML20].**: In addition to [KML20], we also discussed other relevant works, such as [WLZ22, HWLZ23, WSCM20], among others. To better position our work within the literature, we have expanded our discussion on these methods as well as the classical work of Ben-David et al. (as mentioned by the reviewer). This will be detailed further in the camera-ready version.\n\n- **The paper could benefit from thorough proofreading**: We agree that some phrases were rushed. We have carefully revised the paper to address this issue and assure the reviewer that all typos and rushed phrasing have been corrected.\n\n------------------\n\n**Questions**:\n\n- **Could the authors discuss possible extensions to non-binary settings and settings where the domain shift is applied to the joint distribution (Z) rather than the marginal (X)?**: In our work, as shown in Equation (2), the domain shift is indeed applied to the joint distribution $\\mathcal{Z}=\\mathcal{X}\\times\\mathcal{Y}$, not just the marginal distributions, thus addressing the second concern raised by the reviewer. Regarding the extension to non-binary settings, generalizing our method (including Theorem 2.3 and Corollary 2.4) is straightforward. However, examples involving Gaussian distributions and manifold assumptions require further statistical analysis, which we consider a valuable direction for future work. Thank you for this suggestion, we will ensure that this topic is discussed in more detail in the camera-ready version.\n\n\n- **The limitations appear only in the form of the assumptions required for the theoretical results to hold. Discussing the implications of these assumptions would enhance the paper.**: The assumptions in our paper are, in essence, quite similar to those in [WSCM20] and [KML20]. These references have already discussed and experimentally validated the relevance of such assumptions in real-world datasets. We will elaborate on this issue further in the camera-ready version.\n\n----------------\n\nWe hope these revisions address the majority of the reviewer’s concerns. Once again, thank you for your timely and thorough review of our work.", "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": "", "extra_scores": {}}, {"review_id": "rJVDjjp5uo", "reviewer": "Reviewer_BZqU", "summary": "This paper proposes an optimization paradigm for gradual domain adaptation by iteratively performing manifold-constrained Wasserstein DRO and pseudo-labeling on the sequence of domains. The error propagation is theoretically investigated by a compatibility measure $g(\\eta)$ between the manifold of distributions and the class of classifiers. It is shown that with sub-linear $g(\\eta)$, the error propagation will be bounded by Wasserstein distance between adjacent domains, which is independent of the steps of adaptation. The theory is applied to analyze both gaussian generative models and a more general class of distributions characterized by an expansion property.", "questions": "1. Typos: L126, reference missing. L186, citation missing. L228, $P_i$. \n2. Is definition 4.1 correctly presented? The left hand side of the inequality is independent of the Borel set A, while the right hand side is dependent on A.", "limitations": "The author has not explicitly addressed the limitations of the work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper makes good contribution in obtaining the first error bound for gradual domain adaptation that does not scale with $T$, blocking error propagation. The manifold assumption is natural and prevalent. And by the measure of compatibility, the author manages to associate the error propagation rate with complexity of the manifold structure. An exact threshold for error propagation is also obtained as a linear compatibility function. And the classic setting of mixture gaussian models for binary classification is also solved without error propagation.", "weaknesses": "1. At the end of proof of theorem 3.1, the author says that one can only upper bound $\\min \\\\{  \\mathbb E[\\ell(x,y)], 1-\\mathbb E[\\ell(x,y)] \\\\}$, which is much a weaker result. Should the conclusion of theorem 3.1 be revised accordingly? Also can the minimum form be improved?\n2. Theorem 3.1 is not tight in the current form for small distances between adjacent domains. Consider $\\eta=0$ and $\\lambda = 0$,  \nthe error should always be that of Bayes optimal across domains, which is smaller than the current constant upper bound.\n3. Theorem 3.2 is not tight for $\\eta > 1$, in which case it is actually saying the upper bound of error rate will shrink.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their positive feedback. We have addressed the remaining concerns as follows:\n\n**Weaknesses**:\n\n- **At the end of proof of theorem 3.1, the author says that one can only upper bound $\\min\\\\{\\mathbb{E}[\\ell(x, y)], 1- \\mathbb{E}[\\ell(x, y)]\\\\}$, which is much a weaker result. Should the conclusion of theorem 3.1 be revised accordingly? Also can the minimum form be improved?**: This limitation arises specifically in Theorem 3.1, where we consider the $(0-1)$-loss function. In this case, $1 - \\mathbb{E}[\\ell(x, y)]$ represents the expected loss of our classifier on $(x, -y)$. Essentially, this indicates that our classifier can separate the two classes very well, though it’s possible that the labels are flipped. Such guarantees are not uncommon in the literature, as discussed in [WSCM20]. Additionally, it should be noted that a few number of labeled data point from $P_T$ can always correct this label flipping.\n\n- **Theorem 3.1 is not tight in the current form for small distances between adjacent domains. Consider $\\eta = 0, \\lambda = 0$, the error should always be that of Bayes optimal across domains, which is smaller than the current constant upper bound.**: Theorem 3.1 was originally presented for cases where $\\eta > 0$ and $\\lambda \\neq 0$. However, as the reviewer suggested, when $\\eta = 0$, the error indeed corresponds to the exact Bayes error. To elaborate: as seen from the first line of inequalities in (37), when $\\eta=0$, we have:\n\n$$\ng_{\\lambda}^0(\\eta)\n\\leq \\\\, \\inf_{\\theta\\in\\Theta} \\\\, \\sup_{P_{\\mu}: \\Vert \\mu - \\mu_0\\Vert \\leq 2\\eta} E_{P_{\\mu}} \\\\, [\\ell(y,h_{\\theta}(X))]\n= \\inf_{\\theta\\in\\Theta} E_{P_0} [\\ell( y , h_{\\theta} (\\boldsymbol{X}))]\n= E_{\\text{Bayes}},\n$$\n\nwhere $E_{\\text{Bayes}}$ denotes the Bayes error. (We apologize for the cumbersome formulation, but this was necessary to work within the constraints of OpenReview). We will ensure that these edge cases are discussed in more detail in the camera-ready version.\n\n- **Theorem 3.2 is not tight for $\\eta > 1$, in which case it is actually saying the upper bound of error rate will shrink.**: The reviewer is correct. As seen in the proof of Theorem 3.2, our analysis primarily focuses on cases where $\\eta$ is not too large, which aligns with the typical scope of gradual domain adaptation research. When $\\lambda$ is chosen moderately, $\\eta \\geq 1$ can significantly diminish the information of labels. For larger values of $\\eta$, which were not the primary focus of this paper, alternative bounds and methodologies may be required to obtain more appropriate results.\n\n\n---------------------\n\n**Questions**:\n\n- **Typos...**: We have carefully revised the paper to address this issue and assure the reviewer that all typos and rushed phrasing have been corrected.\n\n- **Is definition 4.1 correctly presented? The left hand side of the inequality is independent of the Borel set A, while the right hand side is dependent on A.**:  Thank you for highlighting this issue. Our intention was to show that for all Borel sets $A \\in \\mathcal{A}$, the two conditions hold. We will correct this by removing the $\\inf$ and $\\sup$, and explicitly stating that the conditions apply for $\\forall A$.\n\n\n------------------\n\n**Limitations: The author has not explicitly addressed the limitations of the work.**: We appreciate the reviewer’s input on this point. We will include a discussion of the limitations of our work, taking the reviewer's comments into careful consideration.\n\n-------------------\n\nWe hope these revisions address the majority of the reviewer’s concerns. Once again, thank you for your timely and thorough review of our work.", "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": "", "extra_scores": {}}, {"review_id": "XYbKWVg5wF", "reviewer": "Reviewer_C19w", "summary": "This paper studies the theoretical aspect of gradual domain adaptation (GDA), where the knowledge of labeled source domains is supposed to be transferred to a sequence of target domains. The main results show that the gradual adaptation process can be well characterized by the distributionally robust optimization (DRO) framework, where the domain gaps between the source domain and multiple target domains are gradually captured by the robustness of the model within a pre-set region, i.e., a ball w.r.t. Wasserstein metric over probability space. Finally, the distribution shift is guaranteed to be mitigated with the DRO algorithm.", "questions": "Q1. As discussed in the previous work section, there are already several theoretical works for GDA, e.g., [WLZ22] and [HWLZ23]. However, the differences between the derived results and these works are not discussed in either *previous work section* or *main result section*. It should be clarified that what new insights are provided in the derived results.\n\nQ2. The basic framework, i.e., DRO, is presented in Algorithm 1 directly, while there are no insights provided for it. Though there are plenty of results derived based on DRO, it is hard to understand the working mechanism of the DRO algorithm. \n\nQ3. The bond in Theorem 2.3 shows that the target error can be dominated by the source risk with the factor $g_\\lambda (\\cdot)^{\\circ T}$. Though Corollary 2.4 provides an analytic bound for $g_\\lambda$, it would be more interesting to show the monotonicity of $g$ w.r.t. the composition operator. Furthermore, can the factor $g_\\lambda (\\cdot)^{\\circ T}$ can be monotonically reduced by the increase of $T$? i.e., the factor of error can be reduced with the gradual adaptation process.\n\nQ4. In literature [WLZ22], the main result of Theorem 1 shows that the target error is bounded by the source risk and accumulated error w.r.t. domain number $T$, which is induced by gradual adaptation process. Note that the main result in submission show the accumulated error is a factor of source risk, which implies this result could be loose when the factor is large. Some comparison between the tightness of these bounds are highly appreciated.\n\n\nMinor: 1) Line 126, reference of Theorem; 2) Line 140, notations $\\theta$ and $\\Theta$ are used without definitions; 3) Line 186, previous studies [].", "limitations": "The theoretical analysis for gradual domain adaptation seems to have no potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The motivation of employing DRO as a theoretical framework to address gradual domain adaptation is clear and reasonable.\n+ The extensive theoretical results seem to be solid.", "weaknesses": "- The clarity should be improved, where the advantages or improvements w.r.t. related theory for GDA is not discussed, which leads to unclear contributions.\n- The presentation should be improved, e.g., the DRO algorithm is provided without justification while the main results closely depend on this algorithm.\n- There are many typos and the readability is fair.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their feedback. The reviewer's main concern was the lack of sufficient discussion on certain aspects of the paper, which we have addressed in the revised/camera-ready version. Below, we provide detailed responses to each of the reviewer's comments and concerns:\n\n**Weaknesses**:\n\n- **Clarity needs improvement, especially in discussing the advantages or improvements related to GDA theory, leading to unclear contributions.**: We have enhanced the clarity and presentation of our work in the revised version. To provide a brief summary: as noted by other reviewers, our method has a significant advantage over GDA and other competing methods, where the error propagation in GDA grows exponentially with the number of intermediate domains $T$. Recent works [WLZ22, HWLZ23] have achieved linear error propagation, although the rate of growth remains constant even when the initial error is small. In contrast, our method can control error propagation to be independent of $T$, given certain assumptions on the distributions.\n\n- **The presentation should be improved, e.g., the DRO algorithm is provided without justification, despite the main results relying on this algorithm.**: We would like to clarify that DRO is a well-established technique and is not our original contribution. It has been extensively studied (see [1]) and previously applied in domain adaptation [2]. In our work, we propose adaptive robustness radii, and then utilize DRO by constraining the Wasserstein ball to a specific manifold of distributions, and analyze its performance in the context of gradual domain adaptation, both theoretically and experimentally (please refer to the global rebuttal for details on the new experiments).\n\n[1] Sinha et al., (2018). Certifying Some Distributional Robustness with Principled Adversarial Training. In International Conference on Learning Representations.\n\n[2] Lee et al. (2018). Minimax statistical learning with wasserstein distances. Advances in Neural Information Processing Systems, 31.\n\n- **Typos...**: We have carefully revised the paper to address this issue and assure the reviewer that all typos and rushed phrasing have been corrected.\n\n-------------------\n\n**Questions**:\n\n- **There are several theoretical works on GDA, e.g., [WLZ22] and [HWLZ23]. However, the differences between these works and the results in this paper are not discussed. It should be clarified what new insights are provided by the derived results.**: This question is addressed in our response to the first weakness. We will also highlight our contributions and the advantages of our method over previous methods in a dedicated subsection in the camera-ready version.\n\n- **The basic framework, i.e., DRO, is presented in Algorithm 1 directly, with no insights provided for it. Though there are plenty of results derived based on DRO, it is hard to understand the working mechanism of the DRO algorithm.**:  Theorem 1 (main theorem) demonstrates that using our DRO-based Algorithm 1, the error propagation can be uniquely and solely determined by a newly introduced complexity measure, $g_{\\lambda}(\\cdot)$. The rest of the paper is dedicated to obtaining $g(\\cdot)$ for various settings and showing how error propagation can be entirely mitigated.\n\n- **Theorem 2.3 shows that the target error can be dominated by a factor of $g_{\\lambda}(.)^{oT}$. Corollary 2.4 provides an analytic bound for $g_{\\lambda}$, but it would be more interesting to show the monotonicity of $g$ with respect to the composition operator. Furthermore, can the factor $g_{\\lambda}(.)^{oT}$ be monotonically reduced by increasing $T$?**: From Equation (4), we know that $g_{\\lambda}$ is an increasing function. It is important to note that $g_{\\lambda}$ is not simply composed with itself; as stated in line 166 of Theorem 2.3, it is composed in a specific manner. For example, after one composition, we have $g(2\\lambda g_{\\lambda}(\\eta) + \\eta)$, which is greater than $g_{\\lambda}(\\eta)$ because $2\\lambda g_{\\lambda}(\\eta) + \\eta > \\eta$, and $g_{\\lambda}$ is increasing. Repeating this process shows that the composition $[g(2\\lambda(.) + \\eta)]^{oT}$ always increases (or at least remains constant) with respect to $T$. Also, it is not intuitively plausible for the error to reduce as it propagates.\n\n- **In [WLZ22], Theorem 1 shows that the target error is bounded by the source risk and accumulated error w.r.t. domain number $T$, which is induced by gradual adaptation process. Note that the main result in submission show the accumulated error is a factor of source risk, which implies this result could be loose when the factor is large. Some comparison between the tightness of these bounds are highly appreciated.**: The reviewer is correct in noting this, and analyzing the tightness of these bounds and providing a lower bound for the error propagation would indeed be a valuable contribution. However, this analysis is beyond the scope of the current paper. We will address this in the future work section of the camera-ready version. Additionally, it is worth noting that in the opposite scenario, where the initial error is low, our bounds—even under linear error propagation—are still better than those in [WLZ22], as their rate of increase is independent of the initial error.\n\n- **Minor issues**: Thank you for pointing out these minor issues. All have been corrected in the revised version.\n\n------------------\n\nWe hope these revisions address the majority of the reviewer’s concerns and lead to a favorable reassessment. Once again, thank you for your timely and thorough review of our work.", "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": "", "extra_scores": {}}, {"review_id": "31sDeD49YO", "reviewer": "Reviewer_1exJ", "summary": "This paper introduces a novel approach to gradual domain adaptation using distributionally robust optimization (DRO). The core idea is to adapt models across successive datasets by controlling the Wasserstein distance between distributions and ensuring they lie on a favorable manifold.  The authors  apply  the method  theoretically to two examples and  provide theoretical  guarantees for generalization error. Furthermore, the authors also validate the  theoretical findings through a series of experiments.", "questions": "+ My main concern is that theoretical results rely on relatively toy data distributions and stringent properties, which could lead to limited practical applicability.\n\n+ What are the challenges in extending theoretical results to multi-class data distributions?", "limitations": "see weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The theoretical contributions are substantial, providing rigorous guarantees on model adaptation and generalization errors across domains.  The algorithm provides a  bounded error regardless of  $T$​,  For appropriately constrained  distributions, the error can be demonstrated to be linear or even entirely eradicated.\n\n+  This paper extend the theoretical results to   a more general class of distributions (referred  to as \"expandable\" distributions)  with learnable classifiers.\n+ Furthermore,  The authors demonstrate the polynomial-time convergence of the algorithm.\n\n* The paper is well-written and structured, effectively communicating complex theoretical concepts in a clear and organized manner. It employs rigorous mathematical formalism while maintaining readability, making it accessible to readers", "weaknesses": "1.  It seems that the proof of the theoretical results requires overly stringent conditions, e.g., the assumption of expandable distributions,  the use of smooth mappings and the requirement of   distribution  characterized by  favorable properties.  And it  might not generalize well to real-world data distributions encountered in practice.\n\n2. Both  Gaussian mixture model data distributions  and  \"expandable\" distributions are relatively toy data distributions,  which are somewhat different from the data distribution of real tasks.\n\n3. The paper primarily focuses on the error within the domain $P_T$. However, the error of $\\theta^*$ in the previous domains $P_1, \\cdots, P_{T-1}$ remains uncertain.\n\n4.  How to effectively compute the following WDRO problem **under the manifold constraint** $G$**?\n\n$\\Delta_i^*, \\theta_i^* \\longleftarrow \\{\\min _{\\theta \\in \\Theta}, \\underset{\\theta \\in \\Theta}{\\operatorname{argmin}}\\} \\sup *{P \\in \\mathcal{B}*{\\varepsilon_i}\\left(\\widehat{P}_i \\mid \\mathcal{G}\\right)} \\mathbb{E}*P\\left[\\ell\\left(y, h*\\theta(\\boldsymbol{X})\\right)\\right].$\n\n5. This is related to the theoretical analysis of the Self-Training method in a semi-supervised scenario, where pseudo-labels are assigned to unlabeled data for training [1]. It seems to extend the transformation from $P_{labeled} \\rightarrow P_{unlabel}$ ,  in this scenario to  $P_{labeled}^1 \\rightarrow P_{unlabel}^2\\rightarrow P_{unlabel}^3\\rightarrow P_{unlabel}^4 ...\\rightarrow P_{unlabel}^T$ and uses WDRO to capture the changes in Domain $P^1$ to $P^T$ (in Definition 4.1-4.3). The authors should discuss more about the Assumptions.\n\n6. When estimate the WDRO radius $\\epsilon_i \\longleftarrow \\lambda \\Delta_{i-1}^*+\\eta$. It appears that the $\\Delta_i^*$ is meaningful only if the loss $\\ell$ is the zero-one loss. This is because the definition of $\\mathcal{W}_{p, \\lambda}^q(P, Q)$  (as shown in Eq.(2) in the paper) is related to the zero-one loss $\\mathbb{1}\\left\\{y \\neq y^{\\prime}\\right\\}$.\n\n[1] Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In *International Conference on Learning Representations*, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their feedback. The reviewer's main concern is the applicability of our method in real-world tasks which we have addressed in the camera-ready version. Below, we provide detailed responses to each of the reviewer's comments and concerns:\n\n----\n\n**Weaknesses**:\n\n- **The proof of the theoretical results require stringent conditions, such as the assumption of expandability, the use of smooth mappings, and the requirement for distributions characterized by favorable properties. This may limit the generalizability of the results to real-world data distributions.**: These assumptions and toy examples were introduced to facilitate the theoretical analysis of our algorithm. However, the algorithm is robust and can be applied to real-world data without issues. Please refer to the global rebuttal and the attached PDF for more details, including results on real-world datasets commonly used in gradual domain adaptation literature, where our method outperforms competitors.\n\n- **Both GMM and \"expandable\" distributions are relatively toy examples, which are different from the real data distributions.**: As mentioned in our previous response, we have tested our algorithm on real-world datasets, and the results are available in the global response. These results will be included in the camera-ready version. Furthermore, our notion of expandability is closely related to the one used in previous work [WSCM20], where it has already been validated on datasets such as CIFAR-100.\n\n- **The paper focuses on the error within the domain $P_T$. However, the error of $\\theta_T$ in the previous domains $P_1, ...,P_{{T-1}}$ remains uncertain.**: In our approach, we identify a $\\theta^{\\*}_i$ for each domain $P_i$ ($i \\geq 1$) and provide guarantees for the error associated with $\\theta^{\\*}_i$ within its respective domain. $\\theta^{\\*}_T$ is specifically optimized for $P_T$, as each prior distribution has its own optimal solution.\n\n- **How to compute the WDRO problem under the manifold constraint of $\\mathcal{G}$?**: \nWe considered two scenarios: In the first, $\\mathcal{G}$ is the family of Gaussian distributions, which is parameterizable, meaning we only need to tune the parameters while remaining on the manifold. This simplifies the problem to finding $P = P_\\mu$, where $\\Vert \\mu - \\mu_i \\Vert_2 \\leq \\varepsilon_i$. In the second scenario, we assume that distributions can be generated from one another by applying an unknown but sufficiently smooth function. For example, $P_{i+1}$ models the distribution of $f(X)$, where $X \\sim P_i$ and $f$ belongs to a general but smooth function family $\\mathcal{F}$ (this condition is not overly restrictive in practice). In this case, we replace $P \\in \\mathcal{B}_{\\varepsilon_i}(\\widehat{P}_i | \\mathcal{G})$ \n\nwith $P = f_{\\\\#} P_i$ for $f \\in \\mathcal{F}$. Practically, we consider a parametric family of functions for $\\mathcal{F}$ and maximize the loss within this class using gradient ascent, while penalizing the function to ensure it does not deviate significantly from real samples.\n\n\n- **Regarding the analysis of Self-Training method in a semi-supervised scenario, where pseudo-labels are assigned to unlabeled data [WSCM20]. It seems to extend the transformation from $P_{l} \\to P_{ul}$, in this scenario to $P^1_{l} \\to P^2_{ul}  \\to \\ldots \\to P^T_{ul} $and uses WDRO to capture the changes in Domain $P^1$ to $P^T$ (in Definition 4.1-4.3). The authors should discuss more about the Assumptions.**: Our work differs from [WSCM20] in several key aspects. In [WSCM20], the authors assume the availability of two potentially distant distributions over the feature space, with an unknown but shared labeling rule. They also assume access to a pseudo-labeler from the first distribution, which can be used to assign labels to unlabeled data from the second distribution. Additionally, it is assumed that both distributions and the unknown ground truth labeler satisfy certain robustness properties. In contrast, our work focuses on gradual domain adaptation, where consecutive distributions are assumed to be close. However, we make no assumptions about the labeling rule or the availability of the true distributions.\n\n\n- **When estimate the WDRO radius, it appears that the $ \\Delta^{*}$ is meaningful only if the loss $ \\ell $ is the zero-one loss. This is because the definition of distance (as shown in Eq.(2) in the paper) is related to the zero-one loss ${1}\\\\{y \\neq y^{\\prime}\\\\}$.**: The reviewer is correct that this result is directly applicable to the zero-one loss. However, it can be generalized to cases where $\\ell$ or a scaled version of it, such as $\\alpha \\ell$, is greater than the (0,1)-loss. In this scenario, the estimation would be modified to $\\epsilon_i \\longleftarrow \\alpha \\lambda \\Delta^*_{i-1} + \\eta$. We will discuss this generalization in the camera-ready version.\n    \n----\n\n**Questions**:\n\n- **My main concern is that theoretical results rely on relatively toy data distributions and stringent properties, which could lead to limited practical applicability.** To address this concern, we implemented our method on a number of real-world datasets and achieved superior results compared to existing methods. Please refer to the global rebuttal for detailed results.\n\n- **What are the challenges in extending theoretical results to multi-class data distributions?**: As we mentioned in our response to Reviewer FbyN, our method, including Theorem 2.3 and Corollary 2.4, can be extended to multi-class settings. However, extending the examples involving Gaussian distributions and manifold assumptions would require additional statistical analysis, which we plan to address in future work. This will be discussed further in the camera-ready version.\n\n----\n\nWe hope these revisions address the majority of the reviewer’s concerns and lead to a favorable reassessment. Once again, thank you for your timely and thorough review of our work.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to express our gratitude to all the reviewers for their thoughtful comments and feedback. As some questions and concerns were raised by multiple reviewers, we have provided a global response.

Some reviewers expressed concerns regarding the implementability of our method and its performance on real-world data, particularly under the manifold assumption. To address this, we have included a schematic in Figure 1 of the attached PDF, illustrating the workings of our method. As depicted, at the $i$th step, we perturb the data samples $(X_j,y_j),~j \in [n_i]$ from $P_i$ using a parametric function class, denoted as $f_P$, and penalize the extent of perturbation using the following term:

$$\frac{\gamma}{n_i}\sum_{j=1}^{n_i}{\Vert f_P(X_j) - X_j\Vert_2}.$$ 

These perturbed samples are then classified using a classifier. Let $L_C(f_P;X_1,\ldots,X_{n_i})$ represent the cross-entropy loss of the classifier on the perturbed samples. Our objective is to minimize $L_C(f_P;X_1,\ldots,X_{n_i}) -  \frac{\gamma}{n_i} \sum_{j=1}^{n_i}\Vert f_P(X_j) - X_j\Vert_2$ with respect to the parameters of the classifier $f_C$, while simultaneously maximizing it with respect to the parameters of $f_P$.

Our experimental details are as follows:

- We implemented this method on the 'Rotating MNIST' dataset, similar to [KML20]. In particular, we sampled 6 batches, each with a size of 4200, without replacement from the MNIST dataset, and labeled these batches as $D_0, D_1, \ldots, D_4$, which represent the datasets obtained from $P_0, P_1, \ldots, P_4$. The images in dataset $D_i$ were then rotated by $i \times 15$ degrees, with $D_0$ serving as the source dataset and $D_4$ as the target dataset. We provided the source dataset with labels and left $D_1, D_2, D_3$, and $D_4$ unlabeled for our algorithm. We then tested the accuracy of $\theta^*_0, \ldots, \theta^*_3$—the outputs of our algorithm at each step—on $D_1, D_2, D_3$, and $D_4$, respectively.

- We also implemented the GDA method exactly as described in [KML20]. For our method, we employed a 2-layer CNN with a $7\times 7$ kernel in the first layer and a $5\times 5$ kernel in the second layer. We also utilized an affine grid and grid sample function in PyTorch for $f_P$, following the approach introduced in [1]. For the classifier $f_C$, we used a 3-layer CNN with max pooling and a fully connected layer, applying dropout with a rate of 0.5 in the fully connected layer.

We compared our method to the GDA method presented in [KML20] and detailed the results in Figure 2 of the PDF. Additionally, we reported the accuracy of $\theta^*_0$ on $D_0$ as an example of in-domain accuracy. Our results show that our method outperforms GDA by a significant margin of 8 percent in the last domain.

[1] Jaderberg, M., Simonyan, K., & Zisserman, A. (2015). Spatial transformer networks. Advances in Neural Information Processing Systems, 28.

Meta-review: The paper presents a new approach for gradual domain adaptation based on distributionally robust optimization. Some theoretical guarantees are provided with notably a bound showing that the error can be controlled and generalization improved. 

In the original assessment, reviewers were positive but raised some issues on different aspects of the contributions.  
During rebuttal, authors have addressed all the points mentioned by the reviewers. 
In the discussion, all the reviewers provided a rather positive feedback on the paper.  
A reviewer notably mentioned that the contribution provides the first establish a non-expansive error bound for an increasing number of domains.  

Overall, all reviewers were positives, I recommend thus acceptance.  

Nevertheless, I strongly recommend the authors to take into account all the feedbacks and include the additional elements provided in the rebuttal, as well as correcting the different typos.
Decision: Accept (poster)