Theoretical Performance Guarantees for Partial Domain Adaptation via Partial Optimal Transport

We thank the reviewer for their comprehensive evaluation and helpful suggestions.

Questions for authors: Given that solving the partial optimal transport problem is computationally expensive, how does WARMPOT compare in training time to previous approaches?

Indeed, solving the optimal transport problem is generally computationally expensive. One common way to circumvent this problem is via mini-batch approaches. We follow this approach. Specifically, in the numerical experiments reported in the paper, we use the mini-batch partial optimal transport framework proposed in Improving mini-batch optimal transport via partial transportation by Nguyen et al. (2022). The most well-performing algorithms in the literature, including PWAN and ARPM, also require one to solve optimal transport problems as part of their algorithms.

We would also highlight that different weighting strategies come with different computational costs. In WARMPOT, the weights, which need to be computed per mini-batch, are obtained directly from the solution of the partial optimal transport problem without any additional overhead. On the contrary, a weight update in both the BA3US and the ARPM weighting strategy involves the entire dataset. Additionally, we see from the tables inserted below (see final comment for further details) that there is a trade-off between performance and computational cost for these weighting strategies. Such a trade-off is not present in WARMPOT.

Claims and Evidence: Additional sensitivity analyses on weight selection would further strengthen the claims.

We have added sensitivity analyses for the $\alpha_{max}$ and $\beta$ parameters on ImageNet $\rightarrow$ Caltech (see response to QCqK).

Weakness 1: Limited exploration of additional datasets beyond Office-Home.

We have added results for ImageNet $\rightarrow$ Caltech (see response to 9cQ1 for details).

Weakness 2: Lack of error bars to support experimental results.

In order to address this point, we have re-run our experiments using additional random seeds for OfficeHome (6 seeds) and computed average and standard deviation. We have also conducted a weighting-scheme comparison on ImageNet $\rightarrow$ Caltech using 3 random seeds. In the tables shown below, we considered for BA$^3$US and ARPM the weight update interval (in epochs) indicated in the parentheses. We see from the table that the performance of BA$^3$US depends on the update interval (the smaller the interval, the better the performance) Gu et al., 2024 recommend using 500 and 2000 as update interval for ARPM on OfficeHome and ImageNet $\rightarrow$ Caltech, respectively. Adopting the same update interval for BA$^3$US, to maintain a fair comparison, we see that, as claimed in the paper, WARMPOT results in better performance than MPOT and ARPM(500), and yields performance comparable to BA$^3$US(500) (overlapping confidence intervals) on both datasets.

Also, the confidence intervals of the best performing algorithms in Table 2 reported in the paper (ARPM and ARPM+our weights) overlap.

We thank the reviewer for their careful reading and helpful comments.

Methods and Weaknesses: While the authors provide a comprehensive comparison with the state-of-the-art, they do so in a single benchmark, i.e., the Office-Home benchmark. In my view the authors should complete their experiments with at least other benchmark (preferably Imagenet $\rightarrow$ Caltech or VisDA2017, which are more complex and large scale than Office 31).

We have now benchmarked our algorithm on ImageNet $\rightarrow$ Caltech. The test accuracy of WARMPOT for this data set is 84.8%, while ARPM+our weights achieves 85.1%. For reference, the test accuracy of ARPM is 84.1%. Hence, this additional experiment provides further indication that WARMPOT, and specifically its weights, provides a robust approach for PDA tasks.

Essential References: The authors do a good job summarizing partial Optimal Transport. However, this is not the only way of tackling partial DA. Especially, the authors do not discuss, nor compare the use of unbalanced Optimal Transport (Fatras et al., 2021) for partial domain adaptation

In Table 4 of Nguyen et al. (2022), a comparison is made between their MPOT approach and a mini-batch unbalanced OT (UOT) approach. The results indicate that the POT-based approach works better. We have revised the paper to extend the discussion of UOT approaches and include numerical comparisons.

Comment 1: The term $L_f$ looks like $\lambda$ in (Redko et al., 2017) and other theoretical DA works. Could the authors provide additional discussion on the potential similarities?

$L_f$ indeed plays a similar role as, e.g., $\lambda$ in Redko et al. (2017) and admits the same interpretation, in the sense that it is related to the difficulty of the domain adaptation problem. However, while $\lambda$ is the smallest achievable sum of population losses, $L_f$ is the smallest achievable loss maximized over the empirical source and target set. Meanwhile, $\tilde L_f$ relates to the minimal achievable target loss, and $\Xi$ measures the performance gap between considering source and target tasks jointly or separately.

Comment 2: The cost in (10) looks a lot with the cost of the joint cost proposed in (Courty et al., 2017; reference in the main paper). I think the authors could add some discussion about the similarities as well. This discussion could also make links between the feature importance factor $\zeta\gamma$ weighting the features in the ground-cost.

The cost in (10) is indeed the same as the one proposed in Courty et al., 2017. We will make this point clearer in the revised version of the manuscript. From a theoretical perspective, the factor $\zeta\gamma$ (which appears both in our cost and the one of Courty et al., 2017) corresponds to Lipschitz parameters that are generally not available (see below). Hence, from a practical point of view, we treat it as a hyperparameter in our algorithm.

Comment 3: Given the practical applications of their work, I think the authors could comment on the restrictiveness of their hypothesis. For instance, they assume 1) the encoder $g$ is $\gamma$-Lipschitz, 2) the label loss function is a distance, and $\zeta$-Lipschitz. In common DA practice, neither of these 2 hypothesis are met. For instance, since WGANs, we know that enforcing $\gamma$-Lipschitzness on neural nets is tricky. Furthermore, neural nets are often trained with the cross-entropy loss, which is not a metric on $\mathcal Y$.

Indeed, the Lipschitz assumptions required for our theoretical results are often not satisfied for loss functions used to train neural nets in practice. Such Lipschitz assumptions are commonly invoked in the literature to obtain generalization bounds that depend on Wasserstein distances. Mathematically, the Lipschitz assumption allows one to relate the loss function to the cost appearing in the Wasserstein metric (see Lemma A.4). Note that, in our numerical experiments, we consider loss functions that do not necessarily conform to the theoretical assumptions. The fact that we still observe good performance indicates that these assumptions are not critical for the general insights obtained from our theoretical results to hold.

We thank the reviewer for their careful reading of the paper, relevant references, and constructive comments.

C1 and Essential References:

We thank the reviewer for pointing out these relevant references. While all of them are relevant, consider similar settings and techniques, and deserve to be reviewed in the introduction, there are a few key differences between our work and the mentioned papers. First, to the extent that the mentioned papers present bounds in terms of a weighted source loss, they all rely on classwise weights defined in terms of unknown data distributions. These are then estimated using a method based on Detecting and correcting for label shift with black box predictors by Lipton et al. (2018). However, these estimates are only guaranteed to be accurate if GLS holds exactly, i.e., if the feature representation $Z=g(X)$ of the input $X$ is such that $P(Z|Y=y)=Q(Z|Y=y)$ for source $P$ and target $Q$. Our results require no such assumptions, and yield explicitly computable weights from only the observed data. Additional differences are detailed below.

1. The results in [r1] that contain the weighted source loss are bounds on distribution discrepancies, and not target loss. Furthermore, the weights therein are class-level weights that depend on the unknown underlying distributions, and the domain discrepancy is measured in terms of Jensen-Shannon divergence. In [r2], the same kind of weights are used, and domain discrepancy is measured in terms of metrics like the total variation. Finally, the risk bound in [r3] does not include source loss weights, and depends on the 1-Wasserstein distance rather than its partial counterpart considered in our paper.
2. While [r4] considers a more general setting, aiming for, e.g., private class discovery, the proposed algorithm is not accompanied by any theoretical analysis. Furthermore, as pointed out by the reviewer, they use unbalanced rather than partial optimal transport, and consider binary rather than soft weights.

In summary: the listed references are very relevant, and we have updated the discussion of related work to include them. However, our theoretical results provide test risk bounds in terms of empirically computable weights and apply without any assumptions on the specific form of distribution shift. We have updated our stated contributions to clarify these points and avoid overclaiming the merits of our work relative to prior art.

C2, C3, and Q2:

First, note that we assume $\beta\in(0,1]$. Hence, the mass of the scaled source distribution is always at least $1$. When $\alpha=1$ and all entries of $Q_{\tilde X}$ equal $1/n_t$, the condition below Eq. (4)

$\mathbf{1}^T_{n_s}\Pi\mathbf{1}_{n_t}=1$

requires the $n_t$ column sums of $\Pi$ to add up to $1$, whereas the condition

$\Pi^T \mathbf 1_{n_s} \leq Q_{\tilde X}$

limits each row sum to be $1/n_t$ at most. Combined, they imply that $q_j=1/n_t$.

Regarding guaranteeing that outliers are ignored: The parameter $\beta$ needs to be chosen to be small enough to enable the algorithm to ignore outliers. In particular, if $\alpha=1$, $\beta$ can at most equal the outlier proportion. However, this still does not guarantee that outliers are ignored. In the same way, while the approach of [r4] is designed to avoid outliers, there is also no guarantee that this works. Empirically, as shown in Fig. 1, WARMPOT does significantly downweight outlier samples in practice.

The essential advantages of WARMPOT for PDA compared to the approach of [r4] are: (a): WARMPOT is endowed with theoretical guarantees, (b): the transport plan for POT is more interpretable than the one for unbalanced OT, and (c): our soft weights enable different samples of the same class to have different influence on the final hypothesis.

Q1:

As the reviewer notes, Thm. 3.2 includes only a feature cost whereas Thm. 3.3 additionally incorporates a label cost. Intuitively, one would expect the feature-only approach to suffice when the distribution shift is restricted to covariate shift and a setting where the supports of the input distributions mostly overlap. However, in cases of label shift, incorporating the label cost may be helpful. The factor 2 in Thm. 3.2 essentially compensates for the absence of the label loss, and stems from the use of Lemma A.4 (where we need to use triangle inequality twice). A similar point applies to the uncomputable terms that capture the difficulty of the specific task ($L_f$ and $\tilde L_f$). Whether or not one of the bounds leads to better performance is a largely empirical question, and our experiments indicate that, for the tasks under consideration, it is generally beneficial to include a label cost.

Q3:

We have added results for ImageNet $\rightarrow$ Caltech (see response to 9cQ1 for details).

Other:

We now use $\tilde p_i$ and $\tilde q_j$ for the weights in Thm. 3.3 to avoid confusion, and clarify the difference compared to $p_i$ and $q_j$.

We thank the reviewer for their helpful and constructive comments.

Q1. For the ground distance in the label space the loss should be a metric, but this is not specified. Is a metric actually required for $\ell$? For instance, cross-entropy/log loss/KL divergence doesn't satisfy the requirements for a metric.

The theoretical derivations require the loss function to be symmetric in the model prediction and true label, and that the triangle inequality holds. Note, though, that in our numerical experiments we consider loss functions that do not necessarily conform to the theoretical assumptions. The fact that we still observe good performance indicates that these assumptions are not critical for the general insights obtained from our theoretical results to hold.

Q2. Line 820 "Through a parameter search," on what dataset and what performance metric? Especially in a dataset that is claimed to be unsupervised, this could be 'information leakage' from the test set performance. Generally, the percent of outliers is unknown.

In order to assess the impact of this hyperparameter selection, we have conducted a sensitivity analysis for the $\alpha_{max}$ and $\beta$ parameters on ImageNet $\rightarrow$ Caltech dataset. We set the following values for hyperparameters: $\eta_1 = 0.92$, $\eta_2 = 5.47$, $\varepsilon = 5.59$. In the experiment on $\alpha_{max}$, we set $\beta = 0.72$ and in the experiment on $\beta$, we set $\alpha_{max} = 0.08$ (see Appendix E in our paper for the notation used).

As seen in Figure 1, the impact of varying $\beta$ is not large (about 2%) over the entire range of $0<\beta\le 1$. Similarly, in Figure 2, when $0<\alpha_{max}\le 0.1$, the performance difference is not large (about 3%). However, for $\alpha_{max}>0.1$ there is a significant drop which is due to the large number of outliers in source sample. Using a larger value of $\alpha_{max}$ results in a positive weight over outlier instances thus degrading the performance. The results indicate that the specific choice of these parameters has a minor impact over a range of reasonable values.

Furthermore, note that for the ARPM+our-weights algorithm, we use the same parameters as the original ARPM algorithm.

Q3. Although empirical measures are used, the results would appear to be for the whole sample not the mini-batch. The implications of the reduced sample size from the mini-batch isn't clear in the bounds. Is there an effect?

As the reviewer notes, we solve the mini-batch partial optimal transport problem during training rather than the full-data transport problem due to computational considerations. To study the effect that this has on the resulting weights, we compared:

(i): the average weights applied to each sample during training that arise from the mini-batch partial optimal transport problem.

(ii): the weights arising from the full-data transport problem at the end of training;

The results indicate that the two approaches lead to very similar weight distributions, and in particular, the weight proportion assigned to shared samples is 86.37% with mini-batch weights and 90.54% with full-sample weights. This aligns with discussions in Improving mini-batch optimal transport via partial transportation by Nguyen et al. (2022) regarding the possibility of using mini-batches to approximate full-data transport problems.