Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization

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:

Weaknesses:

• 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.

• 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.

• 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.

• How to compute the WDRO problem under the manifold constraint of $\mathcal{G}$?: We 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})$

with 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.

• 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.

• 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.

Questions:

• 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.

• 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.

We 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.

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:

Weaknesses:

• 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.

• 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).

[1] Sinha et al., (2018). Certifying Some Distributional Robustness with Principled Adversarial Training. In International Conference on Learning Representations.

[2] Lee et al. (2018). Minimax statistical learning with wasserstein distances. Advances in Neural Information Processing Systems, 31.

• Typos...: We have carefully revised the paper to address this issue and assure the reviewer that all typos and rushed phrasing have been corrected.

Questions:

• 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.

• 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.

• 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.

• 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.

• Minor issues: Thank you for pointing out these minor issues. All have been corrected in the revised version.

We 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.

We would like to thank the reviewer for their positive feedback. We have addressed the remaining concerns as follows:

Weaknesses:

• 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.

• 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:

where $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.

• 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.

Questions:

• Typos...: We have carefully revised the paper to address this issue and assure the reviewer that all typos and rushed phrasing have been corrected.

• 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$.

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.

We hope these revisions address the majority of the reviewer’s concerns. Once again, thank you for your timely and thorough review of our work.

I acknowledge and thank the author for their response. Overall, I believe this paper significantly contributes to the existing theoretical analysis of gradual domain adaptation, being the first, as far as I know, to obtain a non-expansive error bound as the number of domains T increases. Despite some limitations in the practical validation of the algorithm, I maintain my support for its acceptance.

I would appreciate it if the author could improve the clarity of the paper by revising the statement of Theorem 3.1 and Definition 4.1, discussing the limitations explicitly, as well as thoroughly checking for any other typos.

We would like to thank the reviewer for their positive feedback. We have addressed the remaining concerns as follows:

Weaknesses:

• 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.

• 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.

• 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.

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)?: 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.

• 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.

We hope these revisions address the majority of the reviewer’s concerns. Once again, thank you for your timely and thorough review of our work.