Solving Discrete (Semi) Unbalanced Optimal Transport with Equivalent Transformation Mechanism and KKT-Multiplier Regularization

• W1: The algorithms are provided in the appendix which should have appeared in the main text.

A1: We will add the algorithm 1-2 into the main text in the camera-ready version.

• Q1: "Free boundaries in optimal transport and Monge-Ampère obstacle problems" (Paper A) by L. Caffarelli and R. J. McCann, an unbalanced formulation of optimal transport is transformed into a classical optimal transport problem. Is there any connection between that approach and the one taken in the article under review?

QA1: We read through Paper A above and we notice that there are several differences between Paper A and ours: (1) Paper A focuses on the free-boundary optimal transport problem where only a fraction of the mass is transported. Indeed, the free-boundary optimal transport problem (i.e., does not involve KL-divergence) is different from SemiUOT and UOT as we investigate in our paper; (2) Paper A adopts the Monge-Ampère equation to solve the problem in the continuous space, meanwhile our paper focuses on solving SemiUOT and UOT in the discrete space with newly proposed ETM and MROT method.

• Q2: The classical unbalanced problem typically includes marginal constraints. These are not included in the formulation of the UOT problem in the paper. Is there a particular reason for omitting them?

QA2: Let us kindly make some clarification here. Classical unbalanced problem was first introduced in [1], and it does not include marginal constraints such as $\pi1_{N} \le a$ and $\pi^T1_{M}\le b$. Meanwhile optimal transport with $\pi1_{N} \le a$ and $\pi^T1_{M}\le b$ constraints is defined as partial optimal transport which was first investigated in [2] as shown:

$$\min_{\pi} J = \langle {C}, \pi \rangle \quad \quad s.t. \pi1_{N} \le a, \pi^T1_{M}\le b, 1_{M}^{T}\pi1_{N} = S$$

[2] has transformed partial optimal transport into a classical optimal transport problem. However, we want to highlight that SemiUOT/UOT and partial optimal transport are completely different problems since the latter does not involve KL-Divergence during the computation.

Ref:

[1] On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

[2] Partial Optimal Transport with Applications on Positive-Unlabeled Learning

• Q3: Proposition 1 is the first key result. However, the notation is not fully clear at that point in the article. Could the authors clarify the use of the star symbol * in expressions like $f^{*}$? (A similar comment applies to Proposition 3.)

QA3: Thank you for your comment. The star symbol (*) in expressions denotes the optimal solution for $f$ and $\zeta$. We apologize for any confusion and will clarify this in the revised manuscript to ensure that the notation is clearer.

• Q4: Regarding the statement of Proposition 1: I suggest rephrasing it as, "Given the SemiUOT functional with KL divergence ${J}_{SemiUOT}$..." A similar revision could be applied to Proposition 3.

QA4: Thank you for your helpful suggestion. We agree with your proposed rephrasing and will revise the statement of Proposition 1 to: "Given the SemiUOT functional with KL divergence ${J}_{SemiUOT}$...". A similar revision will also be applied to Proposition 3 for consistency. We appreciate your input and will incorporate this change in the revised manuscript.

• Q5: Do the new marginals $\alpha$ and $\beta$ represent vectors encoding the weights of discrete probability measures? That is, do their coefficients add to 1?

QA5: Thank you for your question. In fact, the new marginals $\alpha$ and $\beta$ represent marginal weights. The coefficients of $\alpha$ and $\beta$ do not necessarily sum to 1. However, it is important to note that the sum of $\alpha$ and $\beta$ is equal (i.e, $\sum_{i=1}^M \alpha_i = \sum_{j=1}^N \beta_j$), ensuring consistency between the two marginals. We hope this clarifies the notation, and we will make sure to explain this more clearly in the revised manuscript.

• Q6: I did not understand the first sentence on line 180. Could the authors clarify it?

QA6: Thank you for your comment. The first sentence on line 180 refers to the procedure in Equation (11). Specifically, we first fix $\zeta = 0$, and then follow the procedure outlined in line 129. We use the LBFSGS algorithm to optimize the variable $u$ in $L_U$ and iteratively solve for the optimal solution of $u$. We will clarify this in the revised manuscript to ensure better understanding.

• S1: Corollary 1 is not formally stated, so I would suggest presenting it as a Remark instead.

SA1: Thank you for your valuable suggestion. We agree that Corollary 1 is not formally stated, and we will revise it to be presented as a Remark in the revised manuscript, as you suggested.

• S2: While not necessary, a brief discussion of the advantages and disadvantages of SemiUOT compared to UOT would enrich the paper.

SA2: Thank you for your helpful suggestion. While providing a direct, intuitive comparison between SemiUOT and UOT is challenging due to their distinct problem formulations, we appreciate your point that discussing their differences could enrich the paper.

SemiUOT and UOT differ in several important aspects. Specifically, SemiUOT and UOT are equipped with different marginal constraints. UOT relaxes both of the marginal constraints while SemiUOT still keeps one marginal constraint. Therefore, SemiUOT and UOT can be skilled for different scenarios. That is, SemiUOT obtains SOTA in partial UDA meanwhile UOT can be more suitable in UDA and universal UDA tasks, which is reflected in our empirical studies.

We will add a brief discussion of these differences in the revised manuscript to clarify the distinct contexts and applications of SemiUOT and UOT.

• S3: In the Related Works section, I suggest including a citation of the paper [Y. Bai et al., "Linear Optimal Partial Transport Embedding," ICML, 2023], as it presents an alternative approach to addressing the computational complexity of unbalanced optimal transport problems, without relying on the addition of regularization terms.

SA3: Thank you for your suggestion. We appreciate your recommendation to include the paper by Y. Bai et al., "Linear Optimal Partial Transport Embedding," ICML, 2023. We agree that it presents an interesting alternative approach to addressing the computational complexity of unbalanced optimal transport problems. We will include this citation in the Related Works section in the revised manuscript.

• S4: I suggest referencing Algorithms 1 and 2 explicitly in the main text, even if only briefly, to guide the reader.

SA4: Thank you for your suggestion. We agree that referencing Algorithms 1 and 2 explicitly in the main text would help guide the reader. We will make sure to include brief references to these algorithms in the relevant sections of the revised manuscript.

• Typos1: Line 44: After "i.e.," I suggest using a lowercase letter and not capitalizing the following word.

TA1: Thank you for your valuable feedback. We will make the necessary correction and use a lowercase letter after "i.e." as suggested.

• Typos2: Lines 179, 180, and the paragraph between lines 193 and 199: Add commas after "Hence," "Then," and "After that," respectively.

TA2: Thank you for your helpful suggestion. We will add the commas after "Hence," "Then," and "After that," as recommended.

We hope that we have sufficiently addressed your concerns. If there is anything else we can answer or explain or discuss further, kindly do let us know. We really appreciate your encouragement for our paper.

Kind regards, Authors

• Q1: In line 133, 'We iteratively update $L_{U}$ to reach the optimal solutions'. It seems that $L_{U}$ doesn't appear before this sentence.

QA1: Thank you for your careful review. We apologize for the typographical error in line 133. The term "$L_{U}$" should indeed be "$L_{P}$". We will correct this mistake in the revised manuscript.

• Q2: In line 162, 'Since $\hat{f}^{*}$ is close to $f^{*}$'. Is there a theoretical bound for this?

QA2: Thank you for your insightful comment. To start with, we consider the analysis between optimal results of $f^o$ and $\hat{f}^o$ and thus we set $\zeta = 0$ in SemiUOT. Then we define $E_{P}(f)= L_{P}({f})$ and $S_{P}(\hat{f}) = \hat{L}_{P}(\hat{f}) - \epsilon \log M$.

Hence we have the following relationships: (1) $S_P(f^o) \le E_P(f^o) \le E_P(\hat{f}^o) \le S_P(\hat{f}^o) + \epsilon \log M$, (2) $S_P(\hat{f}^o) \le S_P(f^o) \le E_P(f^o) \le S_P(f^o) + \epsilon \log M$ and thus it shows $| S_{P}(f^o) - S_{P}(\hat{f}^o)| \le \epsilon \log M$ [1]. Moreover we have:

$$|E_{P}(f^o) - S_{P}(\hat{f}^o)| \le |E_{P}(f^o) - S_{P}(f^o)| + |S_{P}(f^o) - S_{P}(\hat{f}^o)| \le 2\epsilon \log M$$

Therefore we can observe that $f^o$ and $\hat{f}^o$ will get closer with smaller $\epsilon$. Note that this coincides with the approximation written in line 138. Likewise we consider the optimal results of $u^o$ and $\hat{u}^o$ with $\zeta = 0$ in UOT by $E_{U}(f)= L^u_{U}({u})$ and $S_{U}(\hat{u}) = \hat{L}^u_{U}(\hat{u}) - \epsilon \log M$. The definition of $L^u_{U}({u})$ and $\hat{L}^u_{U}(\hat{u})$ is given in Eq.(52) and Eq.(53). We can also have $| S_{U}(u^o) - S_{U}(\hat{u}^o)| \le \epsilon \log M$ and $|E_{U}(u^o) - S_{U}(\hat{u}^o)| \le 2\epsilon \log M$ accordingly. In conclusion, the solution on ETM-Approx will be relatively close to the exact solution provided by ETM-Exact with smaller $\epsilon$.

In conclusion, the solution on ETM-Approx will be relatively close to the exact solution provided by ETM-Exact with a smaller $\epsilon$.

Ref: [1] Smooth minimization of non-smooth functions.

• Q3: Figure 4 shows that the choice of $\epsilon$ significantly affects the convergence behavior of ETM-Approx and ETM-Refine. For larger values (e.g., $\epsilon = 0.1$), the algorithm fails to recover accurate marginals. However, the paper does not provide guidance on how to choose $\epsilon$ in practice. Could the authors clarify whether there is a principled way to select or adapt $\epsilon$ especially for varying values of $\tau$ or under different data scales?

QA3: Thank you for your valuable comment. As suggested, the choice of $\epsilon$ plays an important role in the convergence behavior of both ETM-Approx and ETM-Refine. Based on the error bound, i.e., $\left| \epsilon \log \left[ \sum_{k=1}^{M} e^{\frac{f_k - C_{kj}}{\epsilon}} \right] - \sup_{k \in [M]} \left[ f_k - C_{kj} \right] \right| \leq \epsilon \log M$, provided in line 138 of the paper, smaller values of $\epsilon$ generally lead to better approximation results. In practice, we typically select $\epsilon = 0.01$, as it strikes a good balance between performance and convergence stability. Therefore, we recommend using this value in most scenarios, but depending on the specific problem or data scale, slight adjustments may be necessary.

• Q4: Since the ETM framework reformulates UOT and SemiUOT problems as classic OT with new marginal weights derived from KKT conditions, could the authors explain more clearly how and why these new weights lead to better performance under noisy or mismatched data? Specifically, in what sense does solving OT with reweighted marginals provide robustness or accuracy improvements over applying classic OT directly to the original noisy distributions?

QA4: Thank you for your insightful comment. To address your question, we provide the following explanations: (1) We will assign small weights to the noise and outlier data via ETM-based method for obtaining new marginal weights. (2) In solving for the new marginal weights, our method introduces an additional term, $s_{ij}$, which adheres to the KKT conditions. This term provides useful information that classical OT with a regularization term (e.g., Sinkhorn) with reweighted marginals does not account for. The inclusion of $s_{ij}$ offers valuable guidance in solving the complete coupling matrix, helping to achieve a more precise solution. Traditional OT with regularization terms (e.g., Sinkhorn), without considering these guiding prior conditions, may lead to less accurate and dense matching results. Our approach incorporates a KKT multiplier regularization term into the optimization problem, enhancing the clarity of the matching process while minimizing the risk of incorrect pairings.

We hope that we mainly addressed your concerns sufficiently. If there is anything else we can answer or explain or discuss further, kindly do let us know. We really appreciate your encouragement for our paper.

Kind regards, Authors

• W1.1: Theoretically, coherence and completeness of this paper should be improved.

A1.1: We first highlight that our propositions are technically sound and correct. c-transform is the basic knowledge of optimal transport, and we have illustrated all implicit conditions and conclusions in our theoretical analysis. Please directly indicate the questions you are concerned about. We are willing to clarify them and further polish the writing in the camera-ready version.

• W1.2: There is a lack of detailed proof and analysis of the convergence rate.

A1.2: We HAVE provided the detailed proof and analysis of the convergence rate (shown in Remark 1, line 158-159) of our proposed ETM-Approx for SemiUOT as $\mathcal{O}(NM\log(1/\varepsilon_{\rm err}))$. The proof is shown on page 19 (line 668-673). The time complexity for ETM-Refine is $O(NM\log (1/ε_{err}) + MN (\log M) D_T)$ where $D_T = \log \log (1/ε_{err})$ denotes the number of iterations with super-linear convergence rate. In terms of MROT, the convergence speed on MROT is determined by different kinds of regularization terms. For instance, MROT-Ent has the same convergence rate as Sinkhorn and ETM-Refine + MROT-Ent has the computation complexity as $O(NM\log (1/ε_{\rm err}) + NM (\log M) D_T + NM/ε_p^2)$ where $ε_p$ denotes the error between $Tr(C^T\pi)$ and $Tr(C^T\pi^*)$.

• W2.1: The organization and layout seems disordered, and the inclusion of numerous detailed explanations in the main text hinders the understanding.

A2.1: We must highlight that we never change the paper layout and format. The detailed mathematical explanations will be shown as formulas in the camera-ready version.

• W2.2: The paper lacks a diagram or concise algorithm pseudocode.

A2.2: We respectfully but firmly disagree with the reviewer’s statement. We HAVE provided the concise pseudocode as Alg.1 and Alg.2 on page 20 and 24. Moreover, we HAVE provided the code in the supplementary material.

• W2.3: Some typos exist.

A2.3: (1) $u$ and $v$ should be $f$ and $g$ respectively in Eq.(20). (2) We will delete the inner product symbol inside the KL-Divergence.

• W3: Design a customized optimization algorithm for solving the OT problem rather than directly applying L-BFGS is better. How about the convergence behavior?

A3: Let us kindly point out the factual misunderstanding that we HAVE provided a customized optimization algorithm as ETM-Approx and ETM-Refine (our core contribution) for solving UOT/SemiUOT. The convergence analysis can be found in A1.2, that is, ETM-Exact is $O(NM \log M \log (1/ε_{err}))$ and ETM-Approx is $O(NM\log (1/ε_{err}))$ and ETM-Refine is $O(NM\log (1/ε_{err}) + MN (\log M) \log \log (1/ε_{err}))$.

• W4 and Q5: It would be positive if the authors demonstrate the adaptability of this method to outliers and out-of-distribution samples.

A4 and QA5: We respectfully but firmly disagree with the reviewer’s statement. We HAVE conducted the outliers experiments in the main paper. (1) We add 20% outliers in the synthetic datasets and report the visualization results in Fig.1-4. (2) OOD samples are also considered on real-world datasets as partial UDA and universal UDA (Table 1-6). Our proposed ETM-based method can achieve much better results by tackling outliers or domain adaptation with OOD samples.

• W5: The novelty may be somewhat limited.

A5: We strongly disagree with this comment. Theorem in [Choi] and our proposed ETM differ significantly in several aspects:

(1) [Choi] mainly considers the continuous case and does not involve the translation invariant term $\zeta$. As we showed in Appendix M, without $\zeta$, the transformed marginal probability will not be equal in 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 of $\boldsymbol{\pi}$, a topic not covered by [Choi], and considering the case when $\tau \rightarrow \infty$.

(3) We provide time complexity and convergence analysis for the proposed method which [Choi] did not provide. In summary, our proposed ETM method ensures that the transformed marginal probability is equal, making the equivalent transformation practical for further obtaining $\boldsymbol{\pi}$ with KKT regularization as MROT. Although MROT shares the same calculation procedure as standard regularized OT solvers, it first proposes KKT regularization term, which leads to more precise results. Last but not least, we HAVE concluded this in our paper in line 70-73.

• Q1: In (27), $f^∗$ seems also relative to the $\tau$?

QA1: NO, $f^∗$ can be ignored and the final result is correct. Let us point out the factual misunderstanding here. Indeed, we can consider $\tau \rightarrow \infty$ in Eq.(5) by remembering $\lim_{\tau \rightarrow +\infty} \tau \exp \left( -\frac{f_i }{\tau } \right) = -f_i$ and set $\zeta = 0$:

$$\min_{f} L_{\rm P}= - \sum_{i=1}^M a_i f_i - \sum_{j=1}^N \left[ \inf\limits_{k \in [M]} \left[ C_{kj} - f_k \right] \right] b_j$$

Therefore, $f^∗$ will not involve $\tau$ when $\tau \rightarrow \infty$. This relationship is also first proposed in this paper, while previous work in [Choi] did not point out.

• Q2: Could numerical instability arise for ETM when $\epsilon \rightarrow 0$?

QA2: We conduct the experiments by setting $\epsilon = \\{ 0.01, 0.1\\}$ shown in line 276 and Fig.4 and the proposed ETM method can provide stable output results. Note that $\epsilon = 0.01$ is relatively close to zero [1, 2] (i.e., see Fig.4.9 in [2]). Our proposed method can still reach stable output when $\epsilon=0.001$ and the results are almost the same as $\epsilon=0.01$. Moreover, we involve the log-sum-exp mechanism which can make the computation more stable according to the previous works (e.g., Chapter 3.3 in [1]).

Ref:

[1] Deriving the Gradients of Some Popular Optimal Transport Algorithms

[2] Computational Optimal Transport: With Applications to Data Science

• Q3: What is the theoretical validity for this design of MROT, and how does it affect optimization stability or convergence?

QA3: The theoretical insight lies in the complementary KKT conditions as $s_{ij}\pi_{ij} = 0$ and we HAVE written it line 242-244 and line 248-251. Adding multiplier regularization term will not affect optimization stability or convergence. That is, adding the KKT-multiplier regularization term $\mathcal{G}({\pi}, {s}) = \langle {\pi}, {s} \rangle$ is equivalent to change the cost matrix from $C_{ij}$ to $C_{ij} + \eta s_{ij}$ shown in line 239. For instance, MROT-Ent has the same optimization stability and convergence against Sinkhorn.

• Q4: What is the relationship between the optimal solution and optimal value of ETM-Exact and ETM-Approx?

QA4: To start with, we consider the analysis between optimal results of $f^o$ and $\hat{f}^o$ and thus we set $\zeta = 0$ in SemiUOT. Then we define $E_{P}(f)= L_{P}({f})$ and $S_{P}(\hat{f}) = \hat{L}_{P}(\hat{f}) - \epsilon \log M$.

Hence we have the following relationships: (1) $S_P(f^o) \le E_P(f^o) \le E_P(\hat{f}^o) \le S_P(\hat{f}^o) + \epsilon \log M$, (2) $S_P(\hat{f}^o) \le S_P(f^o) \le E_P(f^o) \le S_P(f^o) + \epsilon \log M$ and thus it shows $| S_{P}(f^o) - S_{P}(\hat{f}^o)| \le \epsilon \log M$ [1]. Moreover we have:

$$|E_{P}(f^o) - S_{P}(\hat{f}^o)| \le |E_{P}(f^o) - S_{P}(f^o)| + |S_{P}(f^o) - S_{P}(\hat{f}^o)| \le 2\epsilon \log M$$

Therefore we can observe that $f^o$ and $\hat{f}^o$ will get closer with smaller $\epsilon$. Note that this coincides with the approximation written in line 138. Likewise we consider the optimal results of $u^o$ and $\hat{u}^o$ with $\zeta = 0$ in UOT by $E_{U}(f)= L^u_{U}({u})$ and $S_{U}(\hat{u}) = \hat{L}^u_{U}(\hat{u}) - \epsilon \log M$. The definition of $L^u_{U}({u})$ and $\hat{L}^u_{U}(\hat{u})$ is given in Eq.(52) and Eq.(53). We can also have $| S_{U}(u^o) - S_{U}(\hat{u}^o)| \le \epsilon \log M$ and $|E_{U}(u^o) - S_{U}(\hat{u}^o)| \le 2\epsilon \log M$ accordingly. In conclusion, the solution on ETM-Approx will be relatively close to the exact solution provided by ETM-Exact with smaller $\epsilon$.

Ref: [1] Smooth minimization of non-smooth functions.

• Q6:If obtained $u$ and $v$ are inexact due to the computational error, will Corollary 2 and Proposition 4 still hold?

QA6: We answer this question with two aspects.

(1) Corollary 2 is strictly held when $u$ and $v$ (or $f$ and $g$) are the optimal solutions.

(2) According to the response QA4, we show that the solution on ETM-Approx will be relatively close to the exact solution provided by ETM-Exact with smaller $\epsilon$. Therefore, ETM-Approx can also provide an approximate result on ${s}$ with an inexact but approximate solution on $u$ and $v$ (or $f$ and $g$). We also conduct the corresponding experiments as ETM-Approx + MROT-Ent and report the results in Fig.3(b) - (d). From that we can observe that ETM-Approx + MROT-Ent can also reduce the absolute error in SemiUOT. Moreover we conduct the ETM-Approx + MROT-Ent on UOT with $\tau=0.1$ and $N=500$ samples for synthetic datasets and report the absolute error below:

The above results indicate that one can still adopt MROT to find $\pi$ even if $u$ and $v$ (or $f$ and $g$) are just approximate/inexact solutions.

We hope that we addressed mainly of your concerns sufficiently, and if you agree, we would kindly request for updating the review in light of this response. If there is anything else we can answer or explain or discuss further, kindly do let us know.

Kind regards, Authors

Response to A1.1 Even though the c-transform is basic knowledge in optimal transport, it is still suggested to provide a rigorous definition in advance. For example, Choi et al. first specified that the dual multipliers are Lebesgue integrable with respect to the measure. The authors have claimed that the discrete case is different, which makes it even more important to include this part of the definition to help readers understand the distinction between the discrete and continuous settings. A rigorous definition does not conflict with the soundness of the theory.

Response to A1.2 It would be better to complete the paper with the rebuttal explanation on ETM-Refine convergence. There are also concerns on the convergence of $\hat{f}^\*$, which it is claimed to be a super-linear convergence rate [41,42,77,101,35].

Response to A2.1 To improve clarity, would it be helpful to summarize the derivations and conclusions into a few lemmas?

Response to A2.2 It is suggested that the algorithm pseudocode is shown or referenced in the main text instead of Appendix for better understanding the paper.

Response to A3 The "factual misunderstanding" mentioned by the authors might be incorrect. In Alg 1 and Alg 2, L-BFGS is indeed used on ETM-Exact, and ETM-Refine calls ETM-Exact as well. This is essentially a non-smooth optimization problem—wouldn't it be natural to expect the use of a customized algorithm in such a case? For ETM-Refine, the final convergence of $f^*$ is achieved by L-BFGS and the convergence of L-BFGS is analyzed for general functions, not specifically for this OT problem.

Response to A4 The comment highlights a theoretical limitation in robustness to outliers, whereas the authors’ rebuttal addresses only the experimental results. The authors may wish to consult the discussion in Lemma 1 of [1].

Response to A5 It would be helpful to add a clarification in the paper addressing the conceptual gap between this work and prior work, as suggested in the review.

Response to QA1 In (27), $f_i$ is the component of $f^\*$, the optimal solution of (16)

f^\*,g^\*,\zeta^\* =\arg \min_{f,g,\zeta} \left[\tau\sum_{i=1}^Ma_i\exp\left(-\frac{f_i+\zeta}{\tau}-\sum_{j=1}^Nb_j(g_j-\zeta)\right)\right]. $$ Hence, $f_i(\tau)$ is relative to the parameter $\tau$. When $\tau\to \infty$, the authors should first analyze the relationship between $f_i(\tau)$ and $\tau$. Please show a rigorous proof for the readers. **Response to QA3** Since regularizers like Entropy and L2 do not encourage the sparsity, it is more solid to give a mathematical theorem to explain the sparsity from KKT multipliers instead of the insight that has been written. **Response to QA4** This is a promising result. Could we leverage the convergence properties of ETM-exact to determine an optimal trade-off point with minimal computational cost? [1] Fatras, Kilian, et al. "Unbalanced minibatch optimal transport; applications to domain adaptation." International conference on machine learning. PMLR, 2021.

Reply to A1.1 A 2.1, A2.2 and A5 We will improve the clarity as suggested.

Reply to A 1.2 We adopt LBFGS [101] to optimize ETM-Approx and ETM-Refine. LBFGS-based optimizers (e.g., sub-LBFGS [101]) can tackle the non-smooth convex optimization problem. ETM-Refine provides a close optimum point initialization, therefore it has indeed a super-linear convergence rate according to [101] (in page 16 [101]).

Reply to A3 There are still factual misunderstandings, i.e., ETM-Refine calls ETM-Exact as well. Indeed, ETM-Refine is completely different from ETM-Exact. It can be easily verified in Algo.1 and Algo.2. Indeed, ETM-Exact directly adopts LBFGS [101] for the optimization. Meanwhile LBFGS is indeed used on ETM-Refine by taking the approximate solution obtained by ETM-Approx as the initial point rather than using random initialization. Therefore, the convergence rate of ETM-Refine is provided as $\mathcal{O}\left(NM \log\left(\frac{1}{\varepsilon_{\text{err}}}\right) + MN (\log M) \log\log\left(\frac{1}{\varepsilon_{\text{err}}}\right)\right)$, which is exactly customized for OT problem. Meanwhile the time complexity of ETM-Exact is $O(NM\log M \log (1/ε_{err}))$. We can observe that ETM-Refine could be faster than ETM-Exact.

Reply to A4 We read through the Lemma1 provided in [1] and it shows that traditional OT cannot address outliers since the marginal weights are fixed. In other words, UOT relaxed the marginal constraints to overcome the outliers. Indeed, in our paper, we definitely show that the UOT can adjust the data sample weights (see in Proposition 3) to enhance the model robustness against outliers which coincided with Lemma1 in [1]. That is, outliers will be assigned lower marginal weights to avoid getting matched as shown in Fig.1-2.

Reply to QA1 To start with, let us kindly point out the errors in your comment. That is, the optimization problem should be indeed written as below:

$$\min_{{f}, \zeta}L_{\rm P}= \tau \sum_{i=1}^M a_i \exp \left( -\frac{f_i + \zeta}{\tau} \right) - \sum_{j=1}^N \left[ \inf\limits_{k \in [M]} \left[ C_{kj} - f_k \right] - \zeta \right] b_j$$

According to the Algo.1, $\zeta$ will not affect the value of $f^*$. Therefore, it is reasonable to set $\zeta = 0$ to simplify the problem. (We also set $\zeta = 0$ shown in line 129 for initialization). Then the problem turns out to be:

$$\min_{{f}}L_{\rm P}= \tau \sum_{i=1}^M a_i \exp \left( -\frac{f_i}{\tau} \right) - \sum_{j=1}^N \left[ \inf\limits_{k \in [M]} \left[ C_{kj} - f_k \right] \right] b_j$$

We can show that $f_i$ is not relative to $\tau$ when $\tau \rightarrow \infty$.

First we should review the Taylor expansion as $\lim_{\tau \rightarrow +\infty} \tau \exp \left( -\frac{f_i }{\tau } \right) = \tau (1-f_i/\tau) = \tau - f_i$. Therefore the optimization problem can be viewed as:

$$\min_{f} L_{\rm P}= \tau \sum_{i=1}^M a_i - \sum_{i=1}^M a_i f_i - \sum_{j=1}^N \left[ \inf\limits_{k \in [M]} \left[ C_{kj} - f_k \right] \right] b_j$$

Note that $\tau \sum_{i=1}^M a_i$ can be neglected in the optimization problem. Thus it is equivalent to the following problem:

$$\min_{f} L_{\rm P}= - \sum_{i=1}^M a_i f_i - \sum_{j=1}^N \left[ \inf\limits_{k \in [M]} \left[ C_{kj} - f_k \right] \right] b_j$$

It is quite apparently that $f^*$ does not involve $\tau$ when $\tau \to \infty$ and therefore our proposition is definitely correct. In our opinion, it is not difficult to verify them by using the basic knowledge of calculus and convex optimization. Please kindly point out any incorrect parts and we will be happy to discuss them further constructively.

Reply to QA3 The proposed MROT based on KKT multipliers is used to solve SemiUOT and UOT efficiently and accurately. We HAVE written in the line 242-257 with detailed illustrations. When $\pi_{ij} = 0$ it leads to $s_{ij} > 0$. Using MROT-Ent as an example, $\lim_{\eta_G \to \infty} \exp(-\eta_G s_{ij}/\eta_{Reg}) = 0$ and thus our method can provide sparse results. So the main insight is rigidly consistent with our original paper, i.e., we use KKT multipliers to solve the matching problem with more precise solutions.

Reply to QA4 Firstly, we analyze the error bound between the exact solution solved by ETM-Exact and the approximate solution solved by ETM-Approx in QA4, rather than the convergence properties of ETM-Exact. The time complexity of ETM-Exact is $O(NM\log M \log (1/ε_{err}))$. In fact, we set $ε_{err} = 10^{-6}$ during the computation. Smaller $ε_{err}$ could lead to almost the same results reported in paper with more computation time.

In conclusion, we would like to clarify the relationships among three ETM methods, and emphasize that our primary contribution is to propose ETM-Refine, as detailed in our main paper. Specifically, ETM-Exact is the method derived from L-BFGS [101], which can achieve the optimal solution but costs an overwhelming computation time. ETM-Approx is the efficient approximation method proposed by us, which can accelerate the computation by benefiting from the indicators ${s}$. However, our main contribution is to propose ETM-Refine, which takes the advantages of both ETM-Exact and ETM-Approx. ETM-Refine firstly finds the approximate results close to the optimal solution (ETM-Approx), and achieves the exact results with the superlinear convergence (ETM-Exact). We kindly ask that you consider this context when reviewing our work, particularly in terms of evaluating its contribution and computational benefits.

We hope that we addressed mainly of your concerns sufficiently, and if you agree, we would kindly request for updating the review in light of this response. If there is anything else we can answer or explain or discuss further, kindly do let us know.

Kind regards, Authors

• W1.1: The experimental evaluations, in terms of accuracy, offer relatively modest improvements over the existing approaches.

A1.1: The experiment design aims to validate the efficacy of our proposed method among different tasks. Our improvement is consistent but significant on multiple tasks, including UDA, partial UDA, and universal UDA. For instance, our proposed method boosts model performance by 5.71% on Office-Home for partial UDA and 3.50% on Office-Home for universal UDA.

• W1.2: I would like to clearly see a comparison of Big-O time complexities of the approaches.

A1.2: The time complexity of the proposed method can be analyzed via the following procedure:

(1) To start with, we would like the highlight that we provide the details of ETM-Approx whose time complexity is $\mathcal{O}(NM\log(1/ε_{err}))$ with bounded iteration shown in page 19 (line 668-673) and convergence rate (shown in Remark 1, line 158-159).

(2) The time complexity of ETM-Exact is $O(NM\log M \log (1/ε_{err}))$. The time complexity for ETM-Refine is $O(NM\log (1/ε_{err}) + MN (\log M) D_T)$ where $D_T = \log \log (1/ε_{err})$ denotes the number of iterations with super-linear convergence rate.

(3) In terms of MROT, the convergence speed on MROT is determined by different kinds of regularization terms. For instance, MROT-Ent has the same convergence rate as Sinkhorn and ETM-Refine + MROT-Ent has the computation complexity as $O(NM\log (1/ε_{\rm err}) + NM (\log M) \log \log (1/ε_{err}) + NM/ε_p^2)$ where $ε_p$ denotes the error between $Tr(C^T\pi)$ and $Tr(C^T\pi^*)$. Likewise, ETM-Approx + MROT-Ent has the computation complexity as $O(NM\log (1/ε_{\rm err}) + NM/ε_p^2)$.

(4) Ent-UOT has the time complexity of $\mathcal{O}(NM/ε_u)$ where $ε_u$ denotes the error between $J_{UOT}(\pi)$ and $J_{UOT}(\pi^*)$ which is slightly faster than ETM-Approx and ETM-Approx+MROT-Ent. Meanwhile, GEMUOT has the time complexity of $O(NM\kappa\log(1/ε_u))$ where $\kappa = \max(N,M)$ with cubic order which could be time-consuming. Our proposed method is competitive among existing methods, i.e., Ent-UOT and GEMUOT.

• Q1: Is it not true that Semi-UOT is a special case of UOT, since you can always set the hyperparameter coefficient of one distribution to 0? Why can’t existing UOT approaches apply to Semi-OT directly?

QA1: Setting either $\tau_a$ or $\tau_b$ to 0 does not transform UOT into SemiUOT, as SemiUOT retains the marginal constraint $\pi^T \mathbf{1}_M = b$. Fundamentally, SemiUOT is a constrained optimization problem, whereas UOT is an unconstrained one. Consequently, most existing UOT methods, such as MMUOT with mirror gradient descent or GEMUOT, may be challenging to adapt for solving the SemiUOT problem.

• Q2: All variants of “state of the art + UOT(some other solver that’s not yours)” are omitted.

QA2: We omit the variants of “state-of-the-art+UOT” since their performance can be slightly better than state-of-the-art without UOT but significantly less than the proposed method, i.e., ETM-refine + MROT.

We are willing to add more experimental results below. The experiment results on ImageCLEF for partial UDA (Table 2) are given below:

The experiment results on Office-Home for universal UDA (Table 5) are given below:

The experiment results on Office-31 for universal UDA (Table 6) are given below:

From that, we can observe that our proposed method can still consistently achieve the best performance against some other solvers.

• Q3.1: Time complexity analysis should be provided.

QA3.1: Please kindly refer to A1.2.

• Q3.2: How fast is your approach when $N = 1000$?

QA3.2: We have done the time consumption experiments on SemiUOT/UOT in Fig.3 when $N = 1000$. The detailed experimental results are given below:

From the results, we can easily find that ETM+ MROT improves efficiency when the amount of points is large.

• Q4: How about the results if the experiment were repeated?

A4: We would like to highlight that our method is robust to repetition. We repeat for 20 experiments and report the mean and variance results below.

(1) Results on Office-Home and VisDA (UDA)

(2) Results on Office-Home and ImageCLEF (Partial UDA)

(3) Results on Office-Home and Office-31 (Universal UDA)

From that we can observe that our proposed method can still achieve stable and the best performance.

• Q5.1: Some typos (e.g., charts/labels swap and color not consistent) here.

QA5.1: We will fix them in the camera-ready version.

• Q5.2: Running time versus accuracy should be discussed.

A5.2: We mainly report the results on Office-Home with the UDA task. In our experiments, we set the batch size to 512.

From this, we can conclude that ETM-Refine + MROT-Ent achieves the best performance with a slight increase of execution time.

• Q5.3: Running time on different values of $\tau$ should be provided.

A5.3: We conduct the experiments with $N=1000$ samples in synthetic data for $\tau = \{10, 100\}$ and report the computation time:

We can observe that our proposed ETM-based method can still run efficiently for larger $\tau$.

• Comment: Some corrections.

Response: (1) Line 34-35 should be “Meanwhile, adding additional entropy terms will lead to dense and inaccurate matching solutions.” (2) Line 58 should be “We first innovatively propose multiplier constraint terms to establish MROT for achieving more accurate results.”

We hope that we addressed your concerns sufficiently, and if you agree, we would kindly request for updating the review in light of this response. If there is anything else we can answer or explain, or discuss further, kindly do let us know.

Kind regards, Authors