Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization

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.

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. + This paper extend the theoretical results to a more general class of distributions (referred to as "expandable" distributions) with learnable classifiers. + Furthermore, The authors demonstrate the polynomial-time convergence of the algorithm. * 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. 2. 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. 3. 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. 4. How to effectively compute the following WDRO problem **under the manifold constraint** $G$**? $\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].$ 5. 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. 6. 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\}$. [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.

Questions

+ My main concern is that theoretical results rely on relatively toy data distributions and stringent properties, which could lead to limited practical applicability. + What are the challenges in extending theoretical results to multi-class data distributions?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

see weaknesses.

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.

Strengths

+ The motivation of employing DRO as a theoretical framework to address gradual domain adaptation is clear and reasonable. + 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. - The presentation should be improved, e.g., the DRO algorithm is provided without justification while the main results closely depend on this algorithm. - There are many typos and the readability is fair.

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. Q2. 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. Q3. 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. Q4. 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. Minor: 1) Line 126, reference of Theorem; 2) Line 140, notations $\theta$ and $\Theta$ are used without definitions; 3) Line 186, previous studies [].

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The theoretical analysis for gradual domain adaptation seems to have no potential negative societal impact.

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.

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? 2. Theorem 3.1 is not tight in the current form for small distances between adjacent domains. Consider $\eta=0$ and $\lambda = 0$, the error should always be that of Bayes optimal across domains, which is smaller than the current constant upper bound. 3. Theorem 3.2 is not tight for $\eta > 1$, in which case it is actually saying the upper bound of error rate will shrink.

Questions

1. Typos: L126, reference missing. L186, citation missing. L228, $P_i$. 2. 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.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

The author has not explicitly addressed the limitations of the work.

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.

Strengths

- The paper is well-written. - The considered problem is timely and important. - To the best of my knowledge, the proposed approach and the presented theoretical analysis are new. - 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. - 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]. - The paper could benefit from thorough proofreading. For example, there are broken links and missing references (e.g., lines 126 and 186). [*] Ben-David et al. A theory of learning from different domains. Machine Learning, 79(1):151–175, 2010.

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

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

4

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.

Concerns are addressed.

I thank the authors for their detailed responses. In the previous round review, my main concerns are the (theoretical) comparison with existing GDA theory and the tightness of bounds. In rebuttal, I found that 1) the advantages and weaknesses of derived bound over existing works are properly discussed; 2) the implications from derived results, e.g., Thm. 2.3 and Cor. 2.4, are further provided. Therefore, considering the modifications and improvements above, I'm satisfied with the responses and willing to improve the score.

Appreciate

I appreciate the author's responses, and carefully read the comments from other reviewers. I agree with most of the reviewers that the paper presents a nice work. So I would like to raise my grade.