Unified (Semi) Unbalanced and Classic Optimal Transport with Equivalent Transformation Mechanism and KKT-Multiplier Regularization

• Comment 1: The differences/novelty between this paper and Theorem 3.3 in [Choi] should be highlighted.

Response 1: Theorem 3.3 in [Choi] and our proposed ETM differ significantly in several aspects:

(1) Theorem 3.3 mainly considers the continuous case and does not involve the translation invariant term $ζ$. As we shown in Appendix M, without $ζ$, the transformed marginal probability will not be equal in the practice and therefore [Choi] cannot guarantee SemiUOT/UOT can be transformed into classic OT, making it impractical in the discrete scenario.

(2) [Choi] primarily discusses UOT and does not explore SemiUOT. Our proposed ETM method specifically addresses the discrete case by directly calculating the exact value on dual Lagrange multipliers (e.g., $f$ and $u$ in SemiUOT/UOT) for data reweighting and finding $π$, a topic not covered by [Choi].

In summary, our proposed ETM method ensures that the transformed marginal probability is equal in the discrete scenario, making the equivalent transformation practical for further obtaining $π$ with KKT regularization.

• Comment 2: Descriptions in section 5.3 are not clear.

Response 2: We conduct solver comparison on synthetic datasets in Fig.3. That is, we sample 90% data from $P_X$ and $P_Z$ accordingly while also randomly sampling 10% outlier data for $P_{X}$ and $P_{Z}$ to create synthetic dataset and conduct the experiments w.r.t. other methods.

• Comment 3: The domain adaptation results may rely on additional factors.

Response 3: We follow the same framework, loss functions and experimental settings as the famous models JUMBOT/MOT and only replace UOT/SemiUOT solver with ETM as detailed in line 372-379. That is, we control the variants of these additional factors in the experiments.

• Comment 4: ETM+MROT vs. ETM+other classic OT methods are missing.

Response 4: The results for ETM combined with Entropy and Norm under SemiUOT/UOT scenarios, using 500 synthetic data, are presented below:

Both ETM+Entropy and ETM+Norm performs poorly when $η_{G}=0$ comparing with the results in Fig.3(c)-(d) due to insufficient guidance from the KKT conditions. It also reflects the visualization results in Fig.6 in our paper.

• Comment 5: Some similar related work should be added.

Response 5: We will add these references into our main paper with discussions.

• Comment 6: Is it possible to MROT for any classic OT problem when reweighing is not needed?

Response 6: No, MROT requires multipliers $s$ via the ETM method for data sample reweighting, tailored for SemiUOT/UOT. The multipliers $s$ cannot be derived without the reweighing step, rendering MROT incapable of addressing classic OT problems. Determining $s$ for classic OT problems presents its own challenges and falls outside the scope of this paper. Our paper primarily focuses on solving $\pi$ for SemiUOT/UOT, and we have provided ample experiments to validate our proposed KKT-multiplier regularization term, which yields more precise matching results.

• Comment 7: The performance of Ent-UOT should be provided.

Response 7: We provide the experimental results (i.e., time consumption and absolute error) of Ent-UOT in Table A and Table B respectively.

Table A: The time consumption of Ent-UOT where $\tau = 1$ with synthetic data.

Table B: The absolute error of Ent-UOT with synthetic data.

We can observe that Ent-UOT could lead to coarse output matching results and it further illustrates the efficacy of our proposed ETM method.

• Comment 8: What is the computational complexity of your algorithms?

Response 8: The computation complexity of ETM-Approx/ETM-Refine with MROT-Ent is $O(NM)$ which has the same BigO magnitude as the Sinkhorn algorithm. Empirically, ETM-Approx with MROT-Ent and Ent-UOT (Sinkhorn in UOT) have roughly comparable running times while less absolute error as reported in Response 7 Table A-B.

• Comment 1: The time complexity is not provided.

Response 1: The computation complexity of ETM-Approx is $O(NM\log (1/\varepsilon_a))$ where $\varepsilon_a$ denotes the error tolerance (e.g., $ε_a = || \hat{f} - \hat{f}_o||_∞$ in SemiUOT and $ε_a = || \hat{u} - \hat{u}_o ||_∞$ in UOT, $\hat{f}_o$ and $\hat{u}_o$ denote the optimal solution on SemiUOT and UOT respectively). When the initial solution is sufficiently close to the optimal solution, quasi-Newton optimization procedure [1] can achieve super-linear convergence rate [1]. Thus, the time complexity for ETM-Refine is given as $O(NM\log (1/ε_a) + MN D_T)$ where $D_T$ denotes the number of iterations.

• Comment 2: How the method performs with larger datasets.

Response 2: We solve the optimization problem on the GPU. We have conducted the experiments on the large transfer learning datasets, such as Office-Home. Specifically, Office-Home contains approximately 15,500 images, covering 65 categories, with images collected from office and home scenes. In our experiments, we set the batch size to 512. It takes approximately 3.7 seconds to perform one UOT computation, while one execution of ETM-Refine + MROT-Ent takes about 4.1 seconds.

• Comment 3: Could you elaborate more on how sensitive your approach is to hyperparameters?

Response 3: We have conducted the parameter sensitivity in Section 5.3 by varying $\epsilon$ and reported the results in Fig.4. Moreover, we also vary the hyper parameter of $\eta_G$ in Appendix L and report the results in Fig.6. Based on your valuable comment, we collect $\epsilon = (0.01, 0.1, 1)$ and report the number of iterations with $τ = (0.1,1)$ shown in the following Table A.

Table A. Number of iterations to convergence on SemiUOT/UOT

Furthermore, we vary $η_G = (0, 1, 100)$ for SemiUOT/UOT with ETM + MROT-Entropy and ETM + MROT-Norm, where $τ = 1$, $\eta_{\rm Reg} = 0.1$ and $N = 500$, and reported the absolute error $e = \sum_{i,j} ||\pi_{ij} - \pi^*_{ij}||_1$ in the Table B:

Table B. The absolute error on SemiUOT/UOT

Moreover we conduct the experiments with $\epsilon = (0.01, 0.1, 1)$ and $\eta_G = (0, 1, 100)$ on UDA in Office-Home with $τ = 1$ following JUMBOT (i.e., sensitivity analysis on $τ$ has been investigated in JUMBOT) and report the average classification below:

From this, we observe that a smaller value of $\epsilon=0.01$ provides a more accurate smoothness approximation [4], resulting in fewer iterations needed for refinement. Meanwhile we can observe that a larger value on $η_G$ (e.g., $η_G = 100$) can provide more useful KKT-multiplier regularization and boost the model performance as also reflected in Fig. 6.

• Comment 4: Given the sequential nature of L-BFGS, do you see viable approaches for parallelizing or adapting your algorithm for GPU implementations?

Response 4: We leverage code from [1, 3] to optimize L-BFGS, though directly applying it to ETM-Exact may lack efficiency. Our key contribution in this paper is using fixed-point iteration in ETM-Approx to efficiently generate reliable initial solutions for ETM-Refine, achieving superlinear convergence as noted in [1, 4]. Parallelizing L-BFGS exceeds our current scope but is planned for future research.

• Comment 5: Readability should be improved.

Response 5: Thanks for your advice. We will first introduce the important notations at the beginning of our method in the final version to make the paper more readable.

Reference:

[1] A quasi-Newton approach to non-smooth convex optimization

[2] Smooth minimization of non-smooth functions.

[3] PyTorch: An Imperative Style, High-Performance Deep Learning Library

[4] Optimization: Modeling, Algorithm and Theory

• Comment 1: The time complexity is not given in the convergence rate.

Response 1: The computation complexity of ETM-Approx is $O(NM\log (1/\varepsilon_a))$ where $\varepsilon_a$ denotes the error tolerance (e.g., $ε_a = || \hat{f} - \hat{f}_o||_∞$ in SemiUOT and $ε_a = || \hat{u} - \hat{u}_o ||_∞$ in UOT, $\hat{f}_o$ and $\hat{u}_o$ denote the optimal solution on SemiUOT and UOT respectively). When the initial solution is sufficiently close to the optimal solution, quasi-Newton optimization procedure [1] can achieve super-linear convergence rate [1]. Thus, the time complexity for ETM-Refine is given as $O(NM\log (1/\varepsilon_a) + MN D_T)$ where $D_T$ denotes the number of iterations.

Moreover, the convergence speed on MROT is determined by different kinds of regularization terms (e.g., entropy or norm regularization). For instance, ETM-Approx + MROT-Ent or ETM-Approx + MROT-Norm has the computation complexity as $O(NM\log (1/\varepsilon_a) + NMD_{\pi})$ where $D_{\pi}$ denotes the number of iteration. Likewise, ETM-Refine + MROT-Ent or ETM-Refine + MROT-Norm has the computation complexity as $O(NM\log (1/\varepsilon_a) + MN D_T + NMD_{\pi})$.

• Comment 2: A detailed description of parameter selection should be provided.

Response 2: We adopt the parameter sensitivity analysis on $\epsilon$ and report the results in Fig.4. Moreover, we provide more detailed results by varying $\epsilon = (0.01, 0.1, 1)$ and report the number of iterations with $\tau = (0.1,1)$ and report in Response 3 for Reviewer JNNS (Table A) due to the space limit.

From this, we observe that a smaller value of $\epsilon=0.01$ provides a more accurate smoothness approximation [2], resulting in fewer iterations needed for refinement. Moreover, we also vary the hyper parameter of $\eta_G$ in Appendix L and report the results in Fig.6. We provide more detailed result by varying $\eta_G = (0, 1, 100)$ for SemiUOT/UOT with ETM + MROT-Entropy and ETM + MROT-Norm, where $\tau = 1$, $\eta_{\rm Reg} = 0.1$ and $N = 500$, and reported the absolute error $e = \sum_{i,j} || \pi_{ij} - \pi^*_{ij} ||_1$ in Response 3 for Reviewer JNNS (Table B) due to the space limit.

From that we can observe that a larger value on $\eta_G$ (e.g., $\eta_G = 100$) can provide more useful KKT-multiplier regularization and boost the model performance as also reflected in Fig. 6. Therefore we set $\epsilon=0.01$ to provide a more accurate smoothness function approximation and $\eta_G = 100$ to provide better KKT regularization in our experiments.

• Comment 3: Other computational methods like linear programming should be reported.

Response 3: Thank you for highlighting this important point. Following your advice, we present the detailed experimental results of the linear programming (LP) method combined with our proposed approach, as shown in the following table A.

Table A. The time consumption (s) on synthetic data with $\tau = 1$

We also conduct ETM-Exact + LP for domain adaptation tasks as shown in Table B.

Table B. Classification accuracy on Office-Home for UDA

From that we can observe ETM + LP can provide more accurate results and boost the model performance. However, ETM-Exact + LP could be severely time-consuming compared with other methods (e.g., ETM-Exact + MROT-Norm).

• Comment 4: It's questionable how the authors plan to use it in semiUOT for partial domain adaptation.

Response 4: We adopt KL-divergence between the weights on data samples and the uniform distributions. SemiUOT can select and reweight the most similar data samples with higher values. We also conduct a toy example shown in Fig.1 where source and target domains are definitely non-overlapped. However, SemiUOT can still figure out outliers (the irrelevant data) and therefore it is reasonable to adopt SemiUOT to solve partial domain adaptation problems.

Reference:

[1] A quasi-Newton approach to non-smooth convex optimization

[2] Smooth minimization of non-smooth functions.