Solving Discrete (Semi) Unbalanced Optimal Transport with Equivalent Transformation Mechanism and KKT-Multiplier Regularization
Authors: Weiming Liu
Xinting Liao
Jun Dan
Fan Wang
Hua Yu
Junhao Dong
Shunjie Dong
Lianyong Qi
Yew-Soon Ong
Venue: NeurIPS 2025 poster ()
Keywords: Discrete Semi-Unbalanced Optimal Transport; Domain Adaptation with Applications
Primary area: optimization
TL;DR: We propose Equivalent Transformation Mechanism with KKT-Multiplier Regularization for solving SemiUOT and UOT

Abstract: Semi-Unbalanced Optimal Transport (SemiUOT) shows great promise in matching two probability measures by relaxing one of the marginal constraints. Previous solvers often incorporate an entropy regularization term, which can result in inaccurate matching solutions. To address this issue, we focus on determining the marginal probability distribution of SemiUOT with KL divergence using the proposed Equivalent Transformation Mechanism (ETM) approach. Furthermore, we extend the ETM-based method into exploiting the marginal probability distribution of Unbalanced Optimal Transport (UOT) with KL divergence for validating its generalization. Once the marginal probabilities of UOT/SemiUOT are determined, they can be transformed into a classical Optimal Transport (OT) problem. Moreover, we propose a KKT-Multiplier regularization term combined with Multiplier Regularized Optimal Transport (MROT) to achieve more accurate matching results. We conduct several numerical experiments to demonstrate the effectiveness of our proposed methods in addressing UOT/SemiUOT problems.

Solving Discrete (Semi) Unbalanced Optimal Transport with Equivalent Transformation Mechanism and KKTTMultippler Regularization
Weiming Liu', Xinting Liao?;Jun Dan", Fan Wang", Hua Yu',
Junhao Dong', Shunjie Dong', Lianyong Qi Yew-Soon Ong"
ByteDance Inc., Zhejiang University,
College of Computing and Data Science, Nanyang Technological University, Singapore, 4 Shanghai Jiao Tong University, 5 China University of Petroleum (East China),
6 "Shandong Key Laboratory of Intelligent Oil & Gas Industrial Software,
Centre for Frontier AI Research, Institute of High Performance Computing, Agency for Science, Technology and Research, Singapore 1xming95@gmail.comm fxintingliao, danjun, fanvang97 edu cn, (junhao003, yu_hua, asysong) @ntu. @ntu.edu.ss........eeeee sg, sjdongesjtu. edu. cn, saanonngi@@maal... com
Abstract
Semi-Unbalanced Optimal Transport (SemiUOT) shows great promise in matching two discrete probability measures by relaxing one of the marginal constraints. Pre- vious SemiUOT solvers often incorporate an entropy regularization term, inevitably resulting in inaccurate matching solutions. To address this issue, propose Equivalent Transformation Mechanism (ETM) approach to determine the marginal probability distributions of SemiUOT with KL divergence. Furthermore, date the generalization capability ETM by exploiting the marginal probability distributions of Unbalanced Optimal Transport (UOT). ETM is able to determine the exact marginal probabilities both SemiUOT and UOT, based on which we transform the Semi into classic Optimal Transport (OT) problem. Moreover, we propose a KKT-Multiplier regularization term combined with Multi- plier Regularized Optimal Transport (MROT) to achieve more accurate matching results. We conduct extensive experiments to demonstrate the effectiveness our proposed methods in addressing SemiUOT and UOT problems
vali-
Introduction
Optimal Transport (OT) technique is a powerful tool for matching and discerning two distinct probability distributions. Nowadays, OT has multiple successful applications traditional machine
learning (37
33
212
22
85 62]. unsupervised clustering [4. 15), domain adaptation [25] 23 84
60 61), diffusion [49] (6), generative modeling (50] 79
and many others. Nevertheless, directly solving OT distances could have relatively high computation cost with around super-cubic time. Although one can adopt entropy-base based Sinkhorn algorithm 24 for solving OT efficiently,
still suffers from the dilemma of dense and inaccurate solutions [58 63 31). Morcover, classic OT
strictly assumes that the probability masses on both source and target domains should be equal. further hurdles the generalization of OT when the data samples inherit noise outliers.
"Coresponding author.
"The demo code is provided: https://gituu..comXeeee wtt.://////......./M.......
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

96 59 and Semi- Unbalanceddddd Optimal Transport (SemiUOT) [52] have become more attractive in adapting outliers since they allow relaxing
Recently, Unbalanced Optimal Transport (UOT) 6 19 93
92
marginal constraints for transportation results. This advantage makes SemiUOT and UOT powerfully
applicable in transfer learning [01]] 73
80 29 2d 28), computer vision p 30 21
74
16 67
structure data exploration [90]. natural language processing H and other areas. SemiUOT and UOT
relax the strict OT mass equality constraints by introducing relaxation terms defined by Kullback- Leibler (KL) divergence [83] & norm [10], or l2 norm [8) whose effects are controlled by coefficient т. Meanwhile, KL divergence is the most commonly-used commonly-used in real practice [95]. Previous solvers always involves extra regularization terms, i.e., entropy regularization term and proximal point term [4], for tackling Semi and UOT problems. Mcanwhile adding additional entropy terms will lead to dense and inaccurate matching solutions. Latest, [17] and [78 further reconsider solving UOT problem with majority maximization algorithm without the requirements of regularization terms. However, these methods sensitive the choice of т, i.e., providing sparse and accurate matching solutions when r is small, but unsatisfying solutions when is large. Therefore, it is quite challenging to efficiently achieve accurate matching solutions for both SemiUOT and UOT problems.
In this paper, we propose a new method, i.c., Equivalent Transformation Mechanism (ETM), which directly finds the exact marginal probabilities of discrete SemiUOT and UOT with KL divergence. Specifically, ETM first finds the marginal probability distributions for SemiUOT and UOT problems based on Karush-Kuth Mucherr (KKT) conditions and their dual forms. This induces a new insight for understanding SemiUOT and UOT problems, i.c., We can transform SemiUOT and UOT problems into classic OT problems based on adjusting initial marginal weights via ETM. We propose Eee-Refine to achieve exact marginal probabilities without needing overwhelming computation. Specifically, ETM-Refine first seeks the approximate results of marginal distributions via the fixed-point iteration with the smoothness function, and applies quasi-Newton based iterative methods to obtain exact results within quite few steps. This competitively reduces the computation burden to obtain accurate matching results on SemiUOT/UOT. Beyond solving the marginal distribution, we also discover that the KKT multipliers provide valuable guidance for addressing the OT problem, which is transformed from the SemiUOT or UOT problem with adjusted marginal weights. Therefore we further propose Multiplier Regularized Optimal Transport (MROT) for achieving more sparse and accurate OT matching solutions. We summarize our contributions: (1) To our best knowledge, we first propose both exact and approximate solutions for ETM on two problems, i.e., SemiUOT and UOT. After optimizing these problems, one can obtain the sample marginal probabilities and transfer SemiUOT/UOT into standard optimal transport problems. (2) We first innovatively propose multiplier constraint terms to establish MROT for achieving more accurate results. (3) We conduct extensive experiments on both synthetic and real-world datasets to evaluate the performance of proposed ETM.
2 Preliminary
We first provide a brief introduction of SemiUOT and UOT. Let us consider two sets of data samples X E XD and Z E RNND in source and target domains, where M, N denote the number of samples and D denotes the data dimension. Samples in each domain have corresponding prior-given mass weights, i.e., a E RMx1 for source domain and b E Nx for target domain. The semi- unbalanced optimal transport problem is set to measure the minimum cost among data samples X and Z, meanwhile filtering out the noise and outliers by relaxing one of marginal constraints:
min JsemiUOT = (C, TT) + 7KL (TIN/la), s.t. π 1M T = b.
(1)
Buy 20
where C' E MxN denotes the pairwise distance matrix. Meanwhile π E RMXN denotes the coupling matching matrix among the data samples X and Z. denotes the hyper parameter and (.) denotes the commonly-used KI. divergence. SemiUOT relaxes the constraint π Ily * a and keep the constraint π Iy b. Likewise, the unbalanced optimal transport problem 83 further relaxes both two marginal constraints, i.e., TlN # a and π 1 # b as shown:
min Juor (C,T) + T. KL (TIN lIa) + TTKL(TT 1 1[)), 20
(2)
where and π. denote the balanced hyper parameters. Previous researches always add an entropy regularization term to enhance the scalability of solving л of SemiUOT and UOT. However, it still suffers from the dense and inaccurate solution dilemma in real practice.

---

3
Methodology
In this section, will first introduce Equivalent Transformation Mechanism (ETM), which inves- tigates the problem of SemiUOT/UOT from the perspective of marginal probability distribution. Then we illustrate the effect of Multiplier Regularized Optimal Transport (MROT) that finds out the accurate solutions of π for SemiUOT and UOT, with the guidance of KKT-Multiplier Regularization.
3.1 Equivalent Transformation Mechanism
ETM aims to seek the exact marginal distributions with satisfyingly efficient computation. Previous methods [83 20] always directly adopted entropy-based regularization term into tackling SemiUOT and UOT problems. Although such approaches can provide fast computation speed, it will lead to relatively ambiguous and dense solutions that does not match most of the situations in real practice [55] 19]. In this section, we propose ETM- based methods determine the marginal probabilities of source data samples in SemiUOT, accompanied by detailed illustrations. We then extend the ETM-based method to address the more complex UOT problem.
ETM for SemiUOT. To start with, illustrate the ETM for transforming SemiUOT classic OT, and introduce three types of ETM--based methods, i.e., ETM--xact, ETM-Approx, and ETM-Reeine, for determining the marginal probability distributions. Specificallyy, ETM-Exact directly computes the dual variables via iterative methods, e.g., LBFGS, achieving the exact results with an overwhelming computation burden. While ETM--pprrx is variant of ETM for SemiUOT by replacing the infimum with its smoothness approximation. Then we newly propose a fixed-point iteration method to solve the optimization problem efficiently. To further figure out the exact results, ETM-Refine applies ETM-Exact with quite few iterations to solve the exact SemiUOT, by taking the approximate results as starting points. ETM- CTM-Refiie shows competitive performance while maintaining efficient computation. By utilizing the methods above, one can transform SemiUOT into classic optimal transport problem by adjusting initial marginal weights. In the following, we will introduce the deduction and optimization details for the proposed CTTM-base method on SemiUOT.
Proposition 1. (Principles of Equivalent Transformation Mechanism for SemiUOT) Given SemiUOT with KL-Divergence JSemiUOT, one can obtain its Fenchel-Lagrunee multipliers form as:
M
exp (- (
min f.g.c
Σ وواي
-
s.t. fo + 9j + 8ij = Caj. Sij 2 0.
1=1
where f. 9. and Ç denote Lagrange multipliers. Moreover, SemiUOT problem can be further transformed into the form of optimal transport with marginal constraints as follows:
(- =a. π 1 = b.
f -(+
min Jp = (C, s.t. = a exp #20
(4)
When T 0c, the source marginal probability is given TlN Wra and wr. (b. (,)) 1m).
The proof of Proposition can found in Appendix We can observe that transforming SemiUOT into classic OT is to elementally adjust the initial weights of data samples by exp(-(f"+5'/))) To further simplify the calculation by reducing variable g. we set g, = infke[as] (Cks fx) according to the c-transform theorem [103]. Hence only need to optimize f and Ç without additional constraints:
M a. exp
(-i+t) T
N inf (Cks [x] -c0--(o KE[M]
Σ
min Lp 8.5
(5)
We refer to Lp as the newly proposed Exact SemiUOr Equation. To solve this exact SemiUOT in Eg (5) we initialize Ç= for the optimization and introduce an iterative method derived from LBFGS first fix Ç then adopting LBFGS method reach optimal results of f and M of inf (Ckz ff at the ê-th iteration. Then we optimize Ç = r[log [M 1 a, exp((ff/7)))
109 Specifically,
log( ビ b;)] which is obtained by considering Ve 0 and it guarantees ΣM age - (ff+
Σ by. We iteratively update Lu to reach the optimal solutions on Ç*, f and g". We refer to the entire optimization scheme ETM-Exact approach for 55.
3

---

Input Synthetic Data
Ground Truth
Robust SemiSinkhorn
ETM- Rew.ine--no--------
ETM-Refine- Mirioee-MOTT-ooorr
(6) Somitrr with 100 (o) Senittoo with 0.1
Way camp
Tagt sarpin
Figure The SemiUOT matching solutions on when = 0.1 or among the Robust- SemiSinkhom [52] and our proposed ETM-Refine + MROT-Ent, ETM-Refine + MROT-Norm with Vc 10 and e 10-2 We set T/Reg = 0.1 for entropy or L2-norm regularization term.
Although Lp is convex and has unique solutions, the presence of inf(-) renders it a non-smooth function, preventing it from efficient optimization [ To further accelerate the optimization pro- cess, we consider making a smooth approximation on replacing inf(-) with LogSumExp(.)) as fz Ckg
since E <olo|E 1k Ckz
[Cf ful x -elogiE k=1 e
-uPxe( lfx -kyy] <
log M following 775 Here é > 0 denotes the balanced hyperparameter between accuracy and
function smoothness. Smaller (e.g., E - 0) could lead more accurate but less smooth solutions.
Then we can obtain the proposed Approximate SemiUOT Equation as Lp by replacing inf(.) with the smoothness term for f:
M Σ 1=1
Fi+5
N
M
Ckd C
Fn
] +
min f.
Tp
d4 exp
-
bj
llog
exp
(6)
kk
Proposition 2. (Calculation for Approximate SemiUOT Equation) Given Approximate SemiUOT equation Lp, it can be optimized via Equivalent Transformation Mechanism with Approximation (ETM-Approx) That is, ETM-Approx aims to solve the following equation for each fa:
oLp -a, exp
Fo +
fo
by exp
C22
+ exp
of.
Pu-Chi
En
R= exp
Specifically, can adopt fixed-point iteration method for solving 77. at the l-th iteration:
)] vs E [1,
Pt-1 = log exp (-5) log
by
Cas
Σ
exp
Wes
(8)
where v TE/(T + E) for simplification and We.j denotes the corresponding calculation as shown (cr(ft) Ehr exp(( Ck))/e). The proposed procedure can converge with theoretical guarantee. Finally, updating variable Ç by further considering V V r[log(E 0g exp((-t:/7)) loggoo finally achieving optimal results f and C*
via Ç =
The proof Proposition 2 can be found in Appendix C Generally, Proposition 2 outlines the optimization procedure using the newly proposed ETM- approach for addressing the Ap- proximate Semi-UOT Equation. We can observe that the ETM-Approx approach is easy to compute and implement, while avoiding complex caleulations (c.g.. searching the descent direction and finding the step size) and not requiring a large amount of storage space against previous methods. Therefore, the ETM-Approx approach is an efficient method for determining the result of f* and 97 -cllog/MM exp((ft Cx))/e)), transforming SemiUOT into the optimal transport problem.

---

Remark 1. ETM-Approx can reach the linear convergence rate via the fixed-point iteration shown as O(NM log(1/Eer)) where Eerr Ilf loo and f denotes the optimal solution.
Moreover, we can finally figure out the exact optimal solution f* via the approximate optimal solution f on Lp using Proposition 2. That is, if we directly optimize Lp from a randomly initial point, we could spend more time on quasi-Newton gradient descent (e.g., LBFGS) for reaching f" Since f is close to f" it should be more efficient to use f as the initial guess for optimizing f via ETM-Exact which has super-linear convergence rate [46] 47 86 109, 39]. And we regard the whole procedure as ETM-Refine method with time complexity of ( log(1 err)) + N (log M)dr) where dr denotes the number of iterations. ETM-Refing utilizes the strength of ETM-Approx in efficient computation for the exact results. In summary, we can utilize ETM-based methods transform SemiUOT into classic OT problem. We illustrate the optimization details Alg. and Appendix
Algorithm The algorithm of ETM- Based method on SemiUOT
Input: C: cost matrix; a. b: initial marginal probability; e: Hyper parameters.
Randomly initialize the value of finit,
Choose ETM-Exact, ETM-Approx or ETM-Refine on SemiUOT for optimization.
(1) Function:
ETM-Exact on SemiUOT(C, a, b, T, fi=U finit)
Optimize f via L-BFGS algorithm on Lp.
Optimize 9 via 9j = inf - - M
Optimize via Ç 7 /log(
Σ
i-1 ag exp(-fi/7)
log ( bj)l.
Return: The optimal solutions of f" and Ç*
(2) Function: ETM-Approx on SemiUOT(C, a, b, T, pi= = finit) Optimize f via Proposition 2 on Lp. Optimize 9 via 9, = -c log DiI
k=1 exp((fe - Cxj)/c))- log Ej bj)l.
Optimize via ( 7 (llog(E== as (xxp(fi//1)
Return: The optimal solutions of f.. 9 and Ç*,
(3) Function: ETM-Refine on SemiUOT(C,, a, T, fizu= fimit)
Obtain f Amproxx on SemiUOT(C,, a, b, r, f = ff finit).
Obtain f ETM-Exact on SemiUOT(C, a, b, T, ft== = f*)
Return: The optimal solutions of f", g" and Ç"
We have obtained the marginal probability of SemiUOT via tackling Proposition 1 with proposed ETM-based method. In this section, we will further extend ETM for solving the marginal probability on UOT, which is also a commonly existing optimization problem.
ETM for UOT.
Proposition 3. (Principles of Equivalent Transformation Mechanism for UOT) Given UOT with KL-Divergence JUOT, its Fenchel- Lagrange multipliers,for form is given:
exp (- (-
-..+5 +
1/3 (
(----))
[1 + Uj + 8 = Cijs
min 3.,9CC
by exp
s.l.
(9)
8ig 2 0.
where u, U. and Ç denote Lagrange multipliers. Moreover, UOT problem can also be transformed into classic optimal transport as follows:
min To = (C, s.t. Tly = =a n 20
a 2 exp
(---t- = π 1 b exp
2 w²+
(- 0"
-0- 3
To
(10)
Note that when Tos To + 0o, the source and target marginal probabilities can be determined as TIy- = fwaa and π 1M /oo, where w1, = (b,1n)/ 1x) respectively.
The proof of Proposition can be found in Appendix E Likewise, we V, infxe[M (Ckz ux) by the c-transform theorem [103] to simplify the calculation. Hence we obtain Exact UOT Equation:
min Le = Ta
Σ 1=1
M
a exp
u4 (-"+
[ + Tb exp
S
N by exp
SuPRR|M] (ux Cki)
(11)
Ta
Tb
1=1
We first fix then adopting LBFGS approach to optimize Lu on u. Then we futher optimize < x[log(E E exp(-u,/rT)) bog( by exp(-of/no) /.)]] at the f-th iteration where uz.
M
5

---

Syntharir Bata
Ground Touth
Tni-U0T
MI--UOT
GEMIOTT
ETM TT--lellin AIROT Merm
100 (o) to) with
30
(0) 00)007 with
Figure 2: Results of nt on UOT when To = 0.1 or Ta = 7b = 100 among Ent-UOT 83
MM-UOT (17), GEMUOT 78 and ETM-Refne-MROT-NNo with B|G 102 and V/Reg 0.1.
(nf u and above process as the ETM-Exact approach for solving UOT problem. Note that the non-smooth function sup(-) will result in inefficient optimization. However, if we directly apply a similar function approximation to replace sup(.) following (o) the optimization problem becomes quite complex, making it relatively difficult to determine the iterative solutions. Meanwhile, Proposition 2 enlightens us with a completely new ETM-Approx approach for optimizing UOT.
TT + 7b) by considering VeLu O. Here regard the
Optimization 1. (Calculation of ETM--pprrx approach for UOT) Since the optimization problem in (q. is convex, we can also utilize block gradient descent optimize the problem. Specifically, we first fix e and optimize variable 7 at the 1-th iteration by replacing the original marginal probability in Eq. with @ exp( (6 - <)/T)) = 3 accordingly to transform UOT into SemiUOT problem:
M
T. + +
M
Cky
)]
min Ly =
exp
+
83
log
Σ
exp
+
(12)
Ta
j=1
LK=1
It is equivalent solve the equation by taking the differentiation w.r.t. on üg over DV and set it O:
oLu Fü,
aa exp (- (--.-- Ta
T. + (0x+t)
By exp
Coj
exp
0.
(13)
M
14 -Ci
exp
Obviously, equivalent to replace b with 33 (q.(7) for solving Eq. 13). Then we can utilize the iteration step shown in (8) to obtain h'+1_ After that we fix ++ and optimize variable ø
Ck))/e)) We can achieve the optimal solution û' and 6* via iteratively computing via the above procedure accordingly. Finally, (log( a, exp(-út /Ta)) log( Σ j=1 by exp(-0; (r))) via considering Ç = (TT + Due to the space limits, the deduction details are provided in Appendix F Moreover, it has the time complexity of (NN M log(1/Een)) where Earr l ū
via o/+1 - log > k=1 exp(( (o(+1
update variable N
11oo with the linear convergence rate.
In summary, Optimization I for solving the UOT can be seen an extension of Proposition applied to SemiUOT, demonstrating the robust generalization capability of the proposed ETM method. Likewise,
utilize ū" and O' as the initial guess for solving Exact UOT Equation Eq (II) via STTM-Refine Hence, ETM- based methods (i..., Exaeet ETM-Approx and ETM-Refine) transform UOT into classic optimal transport via computing the exact marginal distributions.
3.2 Multiplier Regularized Optimal Transport Induced by KKT-Multiplier Regularization
According the Proposition 1-3 that discussed in Section 3.1, we have figured out the marginal probability distributions on both SemiUOT and UOT with commonly used KL Divergence via proposed ETM-based methods. Motivated by this, we can observe that the core mechanism of UOT/SemiUOT is carefully reweighting the weights of different samples accordingly. If the samples are noise or outliers, the corresponding weights will much smaller than the corresponding weights among similar data samples. Therefore, UOT/SemiUOT has better adaptability than traditional OT that commonly treats all data samples equally. In this section, we will further exploit the matching results of π for SomiUOT and UOT using the following corollary:

---

Corollary 1. Given any UOT/SemiUOT with KL divergence, we can transfer the original problem into classic optimal transport via adopting proposed ETM approach flexibly. We can further utilize existing OT solver for solving xt" (UOT, SemiUOT)
ETM Method, OT Solver π..
This observation provides us with entirely new unified insight into solving the matching results of r for SemiUOT and UOT. It is essential to utilize the proposed ETM-based method, as it offers a variety of OT solvers that yield more efficient and accurate results than directly optimizing UOT or SemiUOT. In general, one can further adopt Sinkhorn [24] [4], 2--norm term [ or some other sparsification OT solver [58 41 with different regularization terms to achieve the transportation π.
Although some OT solvers (e.g., Sinkhorn (24)
could figure out т efficiently comparing to the linear
programming with cubic time complexity 48 they often provide ambiguous results that may deviate
significantly from the correct solutions 72 58 Hence it remains challenge to efficiently find an accurate result for πτ' Recalling the whole process of ETM method, we not only obtain the marginal probabilities, but also derive multipliers which can be further utilized as guidance.
Corollary 2. Given the optimal u² and v" in UOT via ETM-based method, one can obtain on UOT by 8új max(O, Cij u, 15 Likewise, the multipliers on SemiUOT can be obtained via ETM-based method as Sig- max(0, Caj f - 93). Multipliers indicate the value of π., i.e., (case 1) 8ij > 0 when Tij = O and (case 2) 8ij = 0 when mij > 0 according to the KKT conditions.
The Corollary 2 demonstrates that the value of Tij can be reflected via sij. This observation inspires us to further utilize such useful information in accurately calculating matching results π..
Proposition 4. (The Definition and Usage of KKT-Multiplier Regularization) Given any OT with multiplier s, one can obtain accurate solution π via proposed KKT KKT-multipliir regularization term ((T,8) = (TT, s), which formulates Multiplier Regularized Optimal Transport (MROT):
min JG (C, + (T( + "RegCReg(T)) s.t. mlx==x=- a. π T11== 220
(14)
where Reeg( T denotes the regularization term on a, 3 denote the final marginal probabilities obtained by ETM-based method, while Teeg and ng denote the hyperparameters. Ideally, nG should be set as a relatively large number. Meanwhile the dual form of MROT is given as:
max LG ((x, 1b) + (B, ()) "Mee Reg (1/: 03- Ciig)/ 4.6
(15)
where Č.j Cij=Cis + 7a88 & and r/ denote the Lagrange multipliers for MROT. ( denotes the conjugate function of Lnag() (-) and one can figure out the matching results of π via solving the following equation Vnr, (T(,) (v:s + Φ5 CCt))/BBeg
We provide the deduction of MROT in Appendix H That is, minimizing SiyMay to 0 could re- sult in StyTij = O. which not only aligns with the KKT complementary condition, but also reweights the matching for more accurate results. Generally, MROT orthogonal to adopting different kinds of regularization term Leee( (-) for efficient optimization. For instance, one can use the widely adopted entropy regularization term CReg(T) (T) = - (TT, log(T) - 1) to formulate Entropic Multiplier Regularized Optimal Transport (MROT-Ent), whose matching results satisfy /T)ee) exp((ts ((t: + o- - Cig)///eez! Obviously, involving the multipliers infor-
Ty = mation has achieved more accurate solutions. Specifically, the non- non-matching samples pairs will get lower value on Tiy since G(T,, 8) = (T,, 8) avoids rigorous results. Otherwise, the matching results Tij will mainly be determined by the transportation cost. Similarly, one can also adopt L2 Le-norm regularization term (Re((T) 1 (TT, TT) to formulate Sparse Multiplier Regularized Opti- mal Transport (MROT-Norm) with similar characteristics. The time complexity of MROT depends on the regularization term LReg(T) (T), that is. MROT-Ent and MROT-Norm have a complexity of Md) where d, is the number of iterations. In conclusion, we can integrate the (TTM-based methods with MROT method solve the SemiUOT and UOT problems, achieving accurate results for both marginal probabilities and the matching solution Tij-
4 Experiments
4.1 Experimental setup
Datasets. We conduct experiments on both synthetic and real-world datasets to evaluate the methods. (1) Synthetic Datasets. We first conduct the experiments on the synthetic datasets. That is, we set
7

---

Table 1: Classification accuracy (%) on Office- Office-Home for UDA and Partial UDA
Methed for UDA
Ar-+CI Ar-Py Ar-Rw Cl+AAr Cl-iP- Cl-Rw
Pr-AAr
Pt-CI
Pr-Ro Ru-AAr Rw-iCI
Ru--Pr
Arg
[3
31.2
Deep
50.7
68.6
26.4
59.9
65.8
68.1
55.3
15.5
65.0
50.9
78.3
63.5
ROT 53
47-2
71.8
75.4
58.6
68.1
70.2
56.5
45.0
75.8
69.4
52.1
90.6
64.3
JUMBOT E4]
55.2
75.5
50.8
65.5
74.4
74.9
05.2
52.7
79.2
73.0
59.9
$3.4
70.0
JUMBOT UOF:MM LOT
56.3
76.2
816
66.0
75.3
75.1
66.4
32.9
79.3
23.8
60.7
84.1
70.6
JUMROTT EXI (D))
$7.5
774
82.7
67.3
76.0
75.6
19.
82.5
80.3
14.9
61.8
85.3
71.6
L
76.7
66.1
74-5
05.9
60.6
83.3
70-7
JUMBOT
Salver)
8233
75.8
39.1
75.4
JUMBOT + -OOTTETM-Reiii + EMD
59.0
78.5
63.4
68.7
27.1
77.6
58.3
52.2
62.4
76-3
62.5
86.4
73.1
TUMBOT- -IOT: M--iiee + MROT-Norm)
59.4
78.7
84.1
68.5
77.3
78.5
68.6
57.9
82.8
76.3
62.5
86.5
73.4
Method for Purial UDA
Ar-CC1
Ar-Pt
Ar-RW
CI-AAr
CI-PP
CI-RR
Pr-1Ar Pt-+CI
Pt
Rw-AAr
Rw
Rw-+Bt
Ang
ResNerLE JUMBOIRKE AR 1=
67.5
75.9
50
59.0
63.7
41 8
67.4
48.2
74.2
61/4
50.2
68.3
14.11
62.7
72.5
84.4
76.0
73.3
80.5
74.7
60.3
85. 1
80.0
68. 5
83.0
75.5
67.4
77
70.6
85.2
70
8
89
8001
16 2
H0.0
87.2
78.0
MOT [S
63.1
86.1
92.3
76.7
85.4
89.6
70.8
62.3
89.7
63.8
67.00
69.6
80,6
MR(IT-Fu))
65.2
79.5
91.0
MOT UOTCCTM MROT Norm)
38,0
93.1
86.2
64.9
91.3
64.9
68.3
90.7
82.1
MOT + Sho...t..o.sseemiiiii
66.0
88.2
03.0
80.5
56.8
91.5
61.
65 2
91.6
85.0
68
90.9
82.4
Semit-OT1E Xeline
59.5
71.8
MRrT-Norm))
90.7
94.0
67.9
94.4
85.2
Spenn
UNI, tw1
2.5
LDT
SerrUCT
Sanshoo ETHiactire hoen
CTpaurr MaSTho
Betre PISTAAa bent
12 2.0
Bcfin INPOTT
12.0
ETTP Ens atworcpy
ETH Ree Cobioo sert.
ETh-Approw
DEPLOT
CSH CC
ETN nefreehant
0.5
6.3
150
Nurter of Data Semple
Numbbe of Dala Sampples [b) The time consumption Uor
(4) The time consuraption on Semstor
[c] Theaatttttee orror UOT
[d) The abootute arree Somittiir
Figure 3: The time consumption and computation error analysis on UOT and SemiUOT.
the source and target domain distributions as Pxx = N ([=]- D) and Pz = > [-b.s 1
following previous works [6 17. For the SemiUOT scenario, we set target distribution as Fz then we sample 80% data from Px with 20% outlier data to generate the source distribution. For the UOT scenario, we sample 80% data from Ixx and IP accordingly while randomly sampling 20% outlier
data for both IPx and IPz. (2) Real-world Datasets. We conduct the domain adaptation tasks on
Office-31 [88), Office-Honeee Home [02]. and ImageCLEF [3]. More details are provided in Appendix ППk
Baselines. We first compare the proposed ETM-Refine with MROT method with the following state- of-the-art UOT/SemiUOT solvers on the synthetic datasets. (1) Ent-UOT [83] utilizes the entropy regularization term on tackling UOT problem.
(2) MM-UOT [7] adopts majority maximization algorithm for solving UOT. (3) GEMUOT (8) adopts εg-norm term for reaching transport solutions on UOT which is the state-of-the-ee art approach. (4) Robust-SemiSinkhort
[52] adopts the entropy
regularization term for solving SemiUOT problem. We also involve DeepJDOT (25), ROT (5).
JUMBOT 34 ETN 12). AR 42), m-POT (77), MOT (65) as the model baselines for the real- world domain adaptation task. These model details are provided in Appendix J
Implemented details. For both synthetic and real- datasets, we set = 0.01 on both Yu and Lp. We set JJ = 102 and Meeg = 0.1 for MROT in the calculation. The initial value of ()) and f() as set as zero vectors. The initial sample weights are set to be equal, i.e., a, MM and b, = I/N. And we adopt square Fuclidean distance for the cost Cij. Besides, we adopt the same framework and experimental settings of the UDA model JUMBOT 34 for unsupervised domain adaptation and the partial UDA model MOT (65) for partial unsupervised domain adaptation with the fair comparison. For all the experiments, we perform five random experiments and report the average results.
4.2 Performance and Extensive Analysis on Synthetic and Real-World Datasets
Performance on Synthetic Datasets. We sample 50 data samples on both source and target distributions for finding π on UOT/SemiUOT. We first set 7 = 10.1, 100} on SemiUOT and the matching solutions are shown in Fig I a)) Note that we randomly sample 20% of noise in the source datasets. We can observe that previous method Robust-SemiSinkhorn could lead to ambiguous matching results. Our proposed ETM-Refine with MROT+Ent can reach relatively accurate results even if T is large (e.g., 7 = 100). More importantly, ETM-Refine with MROT-N Norm can achieve more precise results comparing with ETM-Refine with MROT-Ent shown Fig Then we also set From that we can observe: (1) Ent-UOT could merely provide dense matching solutions which are inaccurate. (2) MM-UOT obtains relatively accurate solutions when is small. However, MM-UOT
T = {0.1, 100} on UOT and the matching solutions are shown in aa)
8

---

0.35
0.70
UOT, Tu63
0.00
ETM Exctbact
0.20
0.30
ETM kofiee X 2.11
0.65
ETM Retine It- 6.31
0.25
9:25
STM-Awtte y 2.81
0.50
ETleketire Je 6.81)
0.10
0.015
10020
Tw c-0
0.15
0.35
0.02
0.01
0:10
0.50
0.05
20
40
20
69
Number of tereltoms
Number of teralion
Fpom
Fpoch
compatatiion Scnito07
computatiion
Figure 4: The effects on tuning different e = {0.01, 0.1} with the loss descent curve and computation eπror Ea = l| ax
aooo for ETM-Appros method on solving SemiUOT and UOT problems.
Table 2: Classification accuracy (%) on Office-31 and ImageCLEF for partial UDA
Method
A-W
D W
W-ID
A-D
D-1A
W-+A
Avg
I
P-1l
I-C
C-41
C--P
P-SC.
Avg
96.3
98.1
83.4
87.1
18.3
86.9
91.0
72.5
91.5
ETN [2]
84.7
97.4
99.2
91.3
90.2
92.8
92.6
79.6
88.5
92.9
87.2
74,1
93.4
86.0
JUMBOT 34
90.2
96.9
99.3
94.5
93.8
93.4
95.0
80.1
91.3
93.6
90.9
75.7
94,2
87.6
99.7
96.8
96.0
96.9
94.5
76.3
89.0
m-POT
96.2
99.5
100.0
97.6
94.4
95.3
97.2
82.6
94.1
96.3
94.7
78.5
96.2
90.4
MOT [65]
99.3
100.0
100.0
98.7
96.1
96.4
98.4
87.7
95.0
98.0
95.0
57.0
98.7
93.6
MOT+ UOTTETM-Refin: + MROT-Ent)
99.4
100,0
100,0
98.9
96.8
97.3
98.7
88.3
95.6
98.4
95.3
87.6
99.0
94,0
MOT LOT Refine MROT Narm)
99.6
100.0
100.0
99.2
97.3
97.7
99.0
88.7
95.9
98.7
95.8
88.0
99.1
94.4
MOT SemitiO11/T + M-Reiee MROI--Fat)
99.7
100.0
100.0
99.4
97.8
98.4
99.2
89.1
96
99.2
96.1
94.8
MOT + ScmiUOO + MROT-Norm)
99.8
106.0
100.0
99.7
98.4
98.8
99.5
89.6
96.7
99.4
96.5
89.1
99.6
95.2
cannot better handle the case when T large (e.g.- r = 100) due to the deterioration of majority
maximization algorithm. (3) GEMUOT can even reach more sparse matching solution against Ent-UOT and MM-UOT with the aid of f2-norm term. However, the matching results obtained from GEMUOT remain coarse and ambiguous, especially when is large. (4) Benefiting from multipliers 8, E'TM-Refine with MROT-Norm achieves the most accurate results among existing UOT methods.
Performance on Real-World Datasets. We further conduct the experiments on the real-world datasets to validate our proposed method. The experimental UDA task results on Office-Home are shown in Table We also directly adopt fn-nrrm [8] and sparse solver [58] on solving Ju- Meanwhile, proposed ETM-Refine with MROT-Norm obtains the best performance, which indicates its efficacy for finding more accurate matching results on UDA. Then we adopt the same experimental setting as MOT to evaluate the partial UDA task where target label space is subset of source label space. This makes it more challenging than classic UDA task [1 66). The partial UDA results on Office- Hofeee Office-31 31 and ILageCLEF are also shown in Table I and Table 2 We can easily observe that all methods using EMT-Refine with MROT-Norm or MROT- significantly improve the performance on partial UDA task. Especially, MOT SemiUOT (ETM-Refine + MROT-Norm) achieves the best performance, benefiting from its powerful matching capability. UOT relaxes the dual transportation constraints, causing some target samples cannot be transported the source domain. However, SemiUOT overcomes the mentioned issue while avoiding negative transfer in partial UDA, which boosts the model performance. We also conduct more domain adaptation experiments to verify the effects of ETM-Refine with MROT-Norm in Appendix J K
Solver Comparison Analysis. To further analyze the proposed ETM-based methods with MROT, we conduct the solver comparison in terms of computation time and computation error. We first sample the same number of source/target data samples from Pxx and IPz, respectively. As shown in Fig we conduct the experiments on both UOT and SemiUOT with Ta = n 7 1. We can conclude that ETM--Exact with MROT-Norm is most time-consuming. due to directly seeking the optimum from random initial point. Meanwhile, ETM-Reefiee reaches a similar computation time with ETM-Approx, validating that it accelerates the process of finding the optimal u" f by utilizing â' or f". Moreover, calculate the absolute computation error between matching solution π learned by ETM with MROT and the standard UOT/SemiUOT solution with CVXPY n², i.e., Ei, TT T|y ||1- We sample 500 number of data samples ranging from Ta = = {0.01, 0.1, 1, 10, 100} for calculation and the results are shown in Fig (c)(())))))))))))) We can observe that although ETM-Approx with MROT-Ent has the fastest computation speed, the provided results π still have the highest error compared the ground truth πτ. Meanwhile ETM- Refine with MROT-Norm can further reach more accurate solutions against MROT-Ent. Though regularization terms, e.g., entropy and norm, can be directly used in SemiUOT and UOT, they bring larger computation errors without the guidance of KKT-multiplier 8. Sobust-Semiiinkhon causes the largest computation error solving SemiUOT. We also find that all existing UOT methods, i.c., Ent-UOT, MM-UOT, and GEMUOT, not only underperform in matching, but also cost more
9

---

computation time. We can observe that ETM-Reeine method achieves much better results, especially when J is relatively large, which is consistent with our discovery in F
Parameter sensitivity Analysis. We finally study the effects of hyper-parameters on model perfor- mance. We tune in range of c E (0.01, 0.1} and show the results in Fig We can observe that smaller could provide good approximation on UOT/SemiUO1,, reducing the iteration steps for optimizing Ly and Lp. Although could hardly affect the performance value on e could consume more iteration steps for solving Lu and Lp since the initial values are more random. Additionally, we collect the computation error Ea ||@ ax" a=llao. which measures the discrepancy between the marginal probability learned via E'TM-Approx â and the ground truth a". Larger values of may fail reduce the computation error ca when compared to smaller values of c. Hence we set e = 0.01 empirically and more experimental results can be found in Appendix M
ETM-Refine, larger
Related Works
Unbalanced and Semi- Coni-Unbalanced Optimal Transport. (1) Related works on UOT: UOT with
KI. divergence has been widely investigated for dealing with diverse applications [2] 30, 94 [11
40, 32 [06 (64). Different types of UOT solutions can distinguished
terms of using entropy regularization term not. Involving entropy in UOT can enhance the model scalability, yet resulting in dense matching results [98] 5). Latest, [17 further considers UOT without entropy terms by
Majorization- coaeiiaationMinnnizatton (MM) 20 99 or regularization path methods 68 69 57]. However, the
nature of MM algorithm inherits inexact proximal point of KL term [005. which still causes dense mapping when becomes larger. Meanwhile regularization path methods could be quite slow in computation, especially when т + +oo. Furthermore, as the number of samples increases, it can lead to high storage space consumption, which be problematic. Recently, (21) discovers similar transformation between continuous UOT and classic OT problem. However, this discovery cannot directly extend to SemiUOT and UOT in discrete scenarios, and provides hint compute the exact marginal distributions and corresponding matching т. (2) Related works on SemiUOT: SemiUOT with KL divergence only relaxes one of the marginal constraints comparing with UOT. (52) first fully investigated the corresponding problem and proposed Semiii-Semi algorithm. Nevertheless, it still suffers from inaccurate matching solutions with entropy regularization term. Currently, there are only extremely few works for solving SemiUOT (71.. Therefore, how to efficiently provide accurate matching solutions on both discrete SemiUOT and UOT is still challenging problem.
6 Conclusion
In this paper, we propose Equivalent Transformation Mechanism (ETM) approach with ETM-Exact, ETM-Approx, and ETM-Refine solve the marginal probabilities of SemiUOT and UOT. We illustrate that the essence of SemiUOT/UOT is reweighting data samples accordingly and thus SemiUOT/UOT problem can be transformed into standard optimal transport. Moreover, propose KKT-Multiplier Regularization with Multiplier Regularized Optimal Transport (MROT) to obtain more accurate solutions. We conduct extensive experiments to show the superior performance of ETM with MROT, on both synthetic and real-world datasets of different tasks and applications..
Acknowledgments and Disclosure of Funding
This work was supported by the National Natural Science Foundation of China (No. 62572486), Natural Science Foundation Shandong Province (No. ZR2023MF007). This work is also partly sup- ported by the National Research Foundation (NRF), Singapore, through the Al Singapore Programme under the project titled "Al-based Urban Cooling Technology Development" (Award No. AISG3-TC- 2024-014-SGKE
partly supported by the National Research Foundation (NRF). Singapore, through the AI Singapore Programme under the project titled "Learning Assisted Human-AL AI Collaboration for Lcage-scale Practical Combinatorial Optimization" (AISG Award No: AISG3-RP-2022-031
References
[1] Dongsheng An, Na Lei, Xiaoyin Xu, and Xianfeng Gu. Efficient optimal transport algorithm by accelerated gradient descent. In Proceedings of the AAAI Conference on Artificial Intelligence.
10

---

volume 36, pages 10119-012,, 2022.
[2] Joshua D Angrist and Guido W Imbens. Two-stage least squares estimation of average
causal effects in models with variable treatment intensity. Journal of the American statistical Association, 90(430):431-44) 1995.
[3] Yuki Arase, Han Bao, and Sho Yokoi. Unbalanced optimal transport for unbalanced word alignment. ACL, 2023.
[4] Yuki Markus Asano, Christian Rupprecht, and Andrea Vedaldi. Self- via simultancous clustering and representation learning. arXiv preprint arXiv:1911.08 1.0371. 2019. [5] Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing
Systems, 33: 13934-122944 2020.
[6] Jean-David Benamou. Numerical resolution of an "unbalanced" mass transport problem
ESAIM: Mathematical Modelling and Numerical Analysis, 37(5):851-868, 2003.
[7] Artem Betlei, Eustache Diemert, and Massih- -eza Amini. Uplift modeling with generalization guarantees. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 55-65, 2021.
[8] Mathieu Blondel, Vivien Seguy, and Antoine Rolet. Smooth and sparse optimal transport. In International conference on artificial intelligence and statistics, pages 880-889, PMLR, 2018.
[9] Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transac-
tions on Graphics (TOG), 38(4):1-13,200 2019.
[10] Luis A Caffarelli and Robert McCann. Free boundaries in optimal transport and monge-
ampere obstacle problems. Annals of mathematics, pages 673-730, 2010.
[11] Zhangjie Cao, Lijia Ma, Mingsheng Long, and Jianmin Wang. Partial adversarial domain adaptation. In Proceedings of the European conference on computer vision (ECCV), pages
135-150. 2018.
[12] Zhangjie Cao, Kaichao You, Mingsheng Long, Jianmin Wang. and Qiang Yang. Learning to transfer examples for partial domain adaptation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2985-29944 2019.
[13] Barbara Caputo, Henning Müller, Jesus Martinez-Gomer Mauricio Villegas, Burak Acar, Novi Patricia, Neda Marvasti, Suzan Üsküdarl,, Roberto Paredes, Miguel Cazorla, al. Imageclef 2014: Overview and analysis of the results. In Information Access Evaluation. Multilinguality, Multimodality, and Interaction: 5th International Conference of the CLEF Initiative, CLEF 2014, Sheffield. UK, September 15-18, 2014. Proceedings 5, pages 192-211. Springer, 2014, [14] Guillaume Carlier. On the linear convergence of the multimarginal sinkhorn algorithm. SIAM
Journal on Optimization. 32(2):786-794, 2022.
[15] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912-9924, 2020.
[16] Wanxing Chang, Ye Shi, Hoang Tuan, and Jingya Wang. Unified optimal transport frame- work for universal domain adaptation. Advances in Neural Information Processing Systems,
35:29512-29524, 2022.
[17] Laetitia Chapel, Rémi Flamary, Haoran Wu, Cédric Févotte, and Gilles Gasso. Unbalanced optimal transport through non-negative penalized linear regression. Advances in Neural Information Processing Systems, 34:23270-23282, 2021.
[18] Liang Chen, Yihang Lou, Jianzhong He, Tao Bai, and Minghua Deng. Evidential neighborhood contrastive learning for universal domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 2267, 2022.
[19] Lenaic Chizat. Unbalanced optimal transport: Models, numerical methods, applications. PhD
thesis, Université Paris sciences et lettres, 2017.
[20] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xani Xavier Vialard. Scaling algo-
rithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2563-
2609, 2018
[21] Jaemoo Choi, Jaewoong Choi, and Myungioo Kang. Generative modeling through the semi-
dual formulation of unbalanced optimal transport. NeurIPS, 2023.
[22] Ching-Yas Yao Chuang. Stefanie Jegelka, and David Alvars Infoot: Information maximiz-
ing optimal transport. In International Conference on Machine Learning, pages 0228-6242. PMLR, 2023.
[23] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. Advances in neural information processing systems, 30, 2017.
11

---

[24] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[25] Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Proceedings of the European conference on computer vision (ECCV), pages 447-463, 2018. [26] Jun Dan, Weiming Liu, Mushui Liu, Chunfeng Xie, Shunjie Dong. Guofang Ma, Yanchao Tan, and Jiazheng Xing. Hogda: Boosting supervised graph domain adaptation via high-order structure- guructureguuided adaptive feature alignment. In Proceedings of the 32nd ACM International Conference on Multimedia, pages 11 109-11111 11118, 2024.
[27] Jun Dan, Weiming Liu, Xie Xie, Hua Yu, Shunjie Dong, and Yanchao Tan. Tfgda: Exploring topology and feature alignment in semi-supervised graph domain adaptation through robust clustering. Advances in Neural Information Processing Systems, 37:50230-50255
2024. [28] Jun Dan, Yang Liu, Jiankang Deng, Haoyu Xie, Siyuan Li, Baigui Sun, and Shan Luo. Topofr:
A closer look at topology alignment on face recognition. Advances Neural Information 2024.
Processing Systems, 37:37213-
[29] Jun Dan, Yang Liu, Haoyu Xie, Jiankang Deng, Haoran Xie, Xuansong Xie, and Baigui Sun. Transface: Calibrating transformer training for face recognition from a data-centric perspective. In Proceedings of the IEEE/CVF international conference computer vision, pages 20642-20653, 2023.
[30] Henri De Plaen, Vierre-François De Plaen, Johan AK Suykens, Mare Proesmans, Tinne Tuytelaars, and Lue Van Gool. Unbalanced optimal transport: A unified framework for object detection. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 3198-3207, 2023.
[31] Arnaud Dessein, Nicolas Papadakis, and Jean-Luc Rouas. Regularized optimal transport and the rot mover's distance. The Journal of Machine Learning Research, 191))5590-642, 2018. [32] Luca Eyring, Dominik Klein, Théo Uscidda, Giovanni Palla, Niki Kilbertus, Zeynep Akata, and Fabian J Theis. Unbalancedness in neural monge maps improves unpaired domain translation.
In The Twelfth International Conference on Learning Representations, 2023.
[33] Abolfazl Farahani, Sahar Voghoei, Khaled Rasheed, and Hamid R Arabnia. A brief review of domain adaptation. Advances in data science and information engineering: proceedings from ICDATA 2020 and IKE 2020, pages 877-894, 2021.
[34] Kilian Fatras, Thibault Séjourné, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch optimal transport; applications to domain adaptation. International Conference on Machine
Learning, pages 3186-3197. PMLR, 2021.
[35] Jean Feydy, Thibault Séjourné, Frangois-Xavier Vialard, Shun-ichi Amari, Alain Trouvé, and Gabriel Peyré. Interpolating between optimal transport and mmd using sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2681- 2690. PMLR, 2019.
[36] Rémi Flamary, Nicolas Courty. Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal transport. The Journal of Machine Leurning Research, 22(1):3571-3577
2021.
[37] Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with wasserstein loss. Advances in neural information processing systems, 28,
2015.
[38] Bo Fu, Zhangjie Cao, Mingsheng Long, and Jianmin Wang. Learning to detect open classes for universal domain adaptation. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XV 16, pages 567-583. Springer, 2020. [39] Zhan Gao, Aryan Mokhtari, and Alec Koppel. Limited-memory greedy quasi-newton method with non-asymptotic superlinear convergence rate. arXiv preprint 23X, 15444, 2023, [40] Milena Gazdieva, Arip Asadulaev, Evgeny Burnaev, and Aleksandr Korotin. Light unbalanced optimal transport. Advances in Neural Information Processing Systems, 37:93907-93953 2024.
[41] Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large-scale optimal transport. Advances in neural information processing systems, 29, 2016.
[42] Xiang Gu, Xi Yu, Jian Sun, Zongben Xu, et al. Adversarial reweighting for partial domain adaptation. Advances in Neural Information Processing Systems, 34:1 18860-14772, 2021. [43] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEFE conference computer vision and pattern recognition, pages 770-778, 2016
12

---

[44] Yu Hua, Weiming Liu, Gui Xu, Yaqing Hou, Yew-Soon Ong, and Qiang Zhang. Deterministic- to-stochastic diverse latent feature mapping for human motion synthesis. In Proceedings of the Computer Vision and Puttern Recognition Conference, pages 22724-22734, 2025.
[45] J. Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis & Machine Intelligence, 16(5):550-554 2002.
[46] Qiujiang Jin and Aryan Mokhtari. Exploiting local convergence of quasi-newton methods globally: adaptive sample size approach. Advances in Neural Information Processing Systems,
34:3824-3835, 2021.
[47] Qiujiang Jin and Aryan Mokhtari. Non-asymptotic superlinear convergence of standard quasi-newton methods. Mathematical Programming, 200( (00(1):42) 1):425 2023.
[48] Jeff L Kennington and Richard V Helgason. Algorithms for network programming. John Wiley & Sons, Inc.. 1980.
[49] Valentin Khrulkov, Gleb Ryzhakov, Andrei Chertkov, and Ivan Oseledets. Understanding
ddpm latent codes through optimal transport. ICLR, 2023.
[50] Alexander Korotin, Daniil Sclikhanovych, and Evgeny Burnaev. Neural optimal transport.
ICLR, 2023.
[51] Khang Le. Huy Nguyen, Khai Nguyen, Tung Pham, and Nhat Ho. On multimarginal partial op- timal transport: Equivalent forms and computational complexity. In International Conference Artificial Intelligence and Statistics, pages 4397-4413 PMLR, 2022.
[52] Khang Le. Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and barycenter computation. Advances in Neural Information Processing Systems. 34:21947-21959, 2021.
[53] Y. L. Lecun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. proc ieee. Proceedings of the IEEE, 1998.
[54] Guangrui Li, Guoliang Kang, Yi Zhu, Yunchao Wei, and Yi Yang. Domain consensus clustering for universal domain adaptation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9757-9766, 2021. [55] Mengyu Li, Jun Yu, Tao Li, and Cheng Meng. Importance sparsification for sinkhorn algorithm.
arXiv preprint arXiv:2306. 06581, 2023.
[56] Yaron Lipman, Ricky TQ Chen, Heli Ben-Hamu, Maximilian Nickel, and Matt Le. Flow matching for generative modeling. ICLR, 2023.
[57] Dong Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimiza- tion. Mathemutical programming, 45(1-3):503-528 1989.
[58] Tianlin Liu, Joan Puigcerver, and Mathieu Blondel. Sparsity-constrained optimal transport. ICLR, 2023.
[59] Weiming Liu, Chaochao Chen, Xinting Liao, Mengling Hu, Jiajie Su, Yanchao Tan, and Fan Wang. User distribution mapping modelling with collaborative filtering for cross domain recommendation. In Proceedings of the ACM Web Conference 2024, pages 334-343, 2024. [60] Weiming Liu, Jun Dan, Fan Wang, Xinting Liao, Junhao Dong, Hua Yu, Shunjie Dong, and Lianyong Qi. Distinguish then exploit: Source-free open set domain adaptation via weight barcode estimation and sparse label assignment. In Proceedings of the Computer Vision and Pattern Recognition Conference, pages 4927-4938, 2025.
[61] Weiming Liu, Xiaolin Zheng, Chaochao Chen, Jiajie Su, Xinting Liao, Mengling Hu, and Yanchao Tan. Joint internal multi-interest exploration and external domain alignment for cross domain sequential recommendation. In Proceedings of the ACM web conference 2023, pages 383-394, 2023.
[62] Weiming Liu, Xiaolin Zheng, Chaochao Chen, Jiahe Xu, Xinting Liao, Fan Wang, Yanchao Tan, and Yew-Soon Ong. Reducing item discrepancy via differentially private robust embedding alignment for privacy-presevving cross domain recommendation. In Forty-first International Conference on Machine Learning, 2024.
[63] Dirk A Lorenz, Paul Manns, and Christian Meyer. Quadratically regularized optimal transport. Applied Mathematics & Optimizution, 83(3): 1919-1999 2021.
[64] Frederike Lübeck, Charlotte Bunne, Gabriele Gut, Jacobo Sarabia del Castillo, Lucas Pelkmans, and David Alvarez-Melis. Neural unbalanced optimal transport via cycle-consistent semi- couplings. arXiv preprint arXiv:2209. /5621, 2022.
[65] Koi Luo and Chuan-Xian Ren. Mot: Masked optimal transport for partial domain adaptation. In 2023 IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 3531-3540. IEEE, 2023.
[66] You-Wer Luo, Chuan- Xian Ren, Dao-Qing Dai, and Hong Yan. Unsupervised domain adap- tation via discriminative manifold propagation. IEEE transactions on pattern analysis and
13

---

machine intelligence. 44(3):1653-1669, 2020.
[67]
Zhiheng Ma, Xing Wei, Xiaopeng Hong, Hui Lin, Yunfeng Qiu, and Yihong Gong. Learning to count via unbalanced optimal transport. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 2319-2327, 2021.
[68]
Julien Mairal and Bin Yu. Complexity analysis of the lasso regularization path. JCML, 2012. Mathurin Massias, Alexandre Gramfort, and Joseph Salmon. Celer: a fast solver for the lasso with dual extrapolation. In International Conference on Machine Learning, pages 3315-3324.
[69]
PMLR, 2018.
[70] JH Mathews. Numerical methods using matlab, 2004.
[71]
Eduardo Fernandes Montesuma, Fred Maurice Ngole Mboula, and Antoine Souloumiac. Recent advances in optimal transport for machine learning. IEEE Transactions on Puttern
Analysis and Machine Intelligence, 2024.
[72] Eduardo Fernandes Montesuma, Fred Ngole Mboula, and Antoine Souloumiac. Recent advances in optimal transport for machine learning. arXiv preprint arXiv:2306. 2023,
[73] Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlier-robust optimal transport. International Conference on Machine Learning, pages
7850-7860. PMLR, 2021.
[74] Kirill Neklyudov, Rob Brekelmans, Alexander Tong, Lazar Atanackovic, Qiang Liu, and Alireza Makhzani. A computational framework for solving wasserstein lagrangian flows.
arXiv preprint arXiv:2310. 2023.
[75] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical programming,
103:127-152, 2005.
[76] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. Nips Workshop on Deep Learning & Unsupervised Feature Learning, 2011.
[77] Khai Nguyen, Dang Nguyen, Tung Pham, Nhat Ho, et al. Improving mini-batch optimal transport via partial transportation. In International Conference on Machine Learning, pages 16656-16690. PMLR, 2022.
[78] Quang Minh Nguyen, Hoang H Nguyen, Yi Zhou, and Lam M Nguyen. On unbalanced optimal transport: Gradient methods, sparsity and approximation error. JMLR, 2023. [79] Derek Onken, Samy Wu Fung, Xingjian Li, and Lars Ruthotto. Ot-flow: Fast and accurate continuous normalizing flows via optimal transport. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9223-9232, 2021.
[80] Matteo Pariset, Ya-Ping Hsieh, Charlotte Bunne, Andreas Krause, and Valentin De Bortoli. Unbalanced diffusion schr\"" " odinger bridge. arXiv preprint arXiv:2306. 09099, 2023. [81] Xingchao Peng, Ben Usman, Neela Kaushik, Dequan Wang. Judy Hoffman, and Kate Saenko. Visda: A synthetic-to-real benchmark for visual domain adaptation. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition Workshops, pages 2021-2026, 2018.
[82] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11 (556)333556677 2019.
[83] Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui. On unbalanced optimal transport: An analysis of sinkhorn algorithm. In International Conference on Machine Learning. pages 7673-7682. PMLR, 2020.
[84] levgen Redko, Nicolas Courty, Rémi Flamary, and Devis Tuia. Optimal transport for multi- source domain adaptation under target shift. In The 22nd International Conference on artificial intelligence and statistics, pages
PMLR, 2019.
[85] Bilal Riaz, Yuksel Karahan, and Austin Brockmeier. Partial optimal transport for support
subset selection. Transactions on Machine Learning Research, 2023.
[86] Anton Rodomanov and Yurii Nesterov. Rates of superlinear convergence for classical quasi- newton methods. Mathematical Programming, pages 1 1-32, 2021.
[87] Paul R Rosenbaum and Donald B Rubin. The central role of the propensity score in observa-
tional studies for causal effects. Biometrika, 70(1):41 1-5155, 1983.
[88] Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models to new domains. In Computer ECCv 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part IV 11, pages 213-226. Springer, 2010.
[89] Kuniaki Saito, Shohei Yamamoto, Yoshitaka Ushiku, and Tatsuya Harada. Open set domain adaptation by backpropagation. In Proceedings of the European conference on computer vision (ECCV), pages 153-168, 2018
14

---

Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on tree. Advances in neural information processing systems, 1et19993-99511 2020. Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank sinkhorn factorization. In International Conference on Machine Learning, pages 9344-9354 PMLR, 2021. [92] Meyer Scetbon, Michal Klein, Giovanni Palla, and Marco Cuturi. Unbalanced low-rank optimal transport solvers. NewrIPS, 2023.
[90]
[91]
[93] Thibault Séjourné, Clément Bonet, Kilian Fatras, Kimia Nadjahi, and Nicolas Courty. Unbal- arXiv preprint arXiv:2306.0711 2023. Thibault Séjourné, Jean Feydy, François- Xavier Vialard, Alain Trouvé, and Gabriel Peyré.
anced optimal transport meets bliced-wasserse
[94]
Sinkhorn divergences for unbalanced optimal transport. 2019.
[95]
Vialard. Unbalanced optimal transport, Thibault Séjourné, Gabriel Peyré, and François-Xave
from theory to numerics. arXiv preprint arXiv:2211. 22..02751..77.. 2022.
[96]
Thibault Séjourné, Xravee Vialard, and Gabriel Peyré. Faster unbalanced optimal Translation invariant sinkhorn and 1-d frank-wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4995-5021. PMLR, 2022.
transport:
[97]
Uri Shalit, Fredrik D) Johansson, and David Sontag. Estimating individual treatment effect: generalization bounds and algorithms. In International conference on machine learning, pages 3076-3085, PMLR, 2017.
[98] Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics. 21(2):343-348, 1967.
[99] Ying Sun, Prabhu Babu, and Daniel P Palomar. Majorization-miniiizatti algorithms in signal processing, communications, and machine learning.
IEEE Transactions on Signal
Processing, 65(3))994-816, 2016.
[100] Alexander Tong. Nikolay Malkin, Guillaume Huguet, Yanlei Zhang. Jarrid Rector-Brooks: Kil- ian Fatras, Guy Wolf, and Yoshua Bengio. Improving and generalizing flow-based generative models with minibatch optimal transport. In ICML Workshop on New Frontiers in Learning, Control, and Dynamical Systems, 2023.
[101] Quang Huy Tran, Hicham Janati, Nicolas Courty, Rémi Flamary, levgen Redko, Pinar Demetci, and Ritambhara Singh. Unbalanced co-optimal transport. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pages 10006-10016, 2023.
[102] Hemanth Venkateswara, Jose Eusebio, Shayok Chakraborty, and Sethuraman Panchanathan.
Deep hashing network for unsupervised domain adaptation. CoRR, abs// 075222 2017.
[103] Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
[104] Hao Wang, Zhichao Chen, Jiajun Fan, Haoxuan Li, Tianqiao Liu, Weiming Liu, Quanyu Dai, Yichao Wang, Zhenhua Dong, and Ruiming Tang. Optimal transport for treatment effect estimation. arXiv preprini arXiv:2310, 18286, 2023.
[105] Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A fast proximal point method for computing exact wasserstein distance. Uncertainty in artificial intelligence, pages 433-453. PMLR, 2020.
[106) Karren D Yang and Caroline Uhler. Scalable unbalanced optimal transport using generative adversarial networks. arXiv preprint arXiv: 1447, 2018.
[107] Liuyi Yao, Sheng Li, Yaliang Li, Mengdi Huai, Jing Gao, and Aidong Zhang. Representa- tion learning for treatment effect estimation from observational data. Advances in neural information processing systems, 31, 2018
[108) Kaichao You, Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I Jordan. Universal domain adaptation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2720-2729, 2019.
[109] Jin Yu, SVN Vishwanathan, Simon Günter, and Nicol N Schraudolph. quasi-newton approach to non-smooth convex optimization. In Proceedings of the 25th international conference on Machine learning, pages 1216-1223, 2008
[110] Fangneng Zhan, Yingchen Yu, Kaiwen Cui, Gongjie Zhang, Shijian Lu, Jianxiong Pan, Changgong Zhang, Feiying Ma, Xuansong Xie, and Chunyan Miao. Unbalanced feature transport for exemplar-based image translation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 15028-15038. 2021.
[111] Lei Zhang and Xinbo Gao. Transfer adaptation learning: A decade survey. IEEE Transactions Neural Networks and Leurning Systems, 2022.
[112] Yubo Zhuang, Xiaohui Chen, and Yun Yang. Wasserstein k-means for clustering probability distributions. Advances in Neural Information Processing Systems, 33:11382-11 11132-13995 2022.
15

---

Appendix
Notation Table
We provide the important notations and their descriptions for clarification on Table
Symbol
Description
X RMx
Source domain data matrix
Z
RNXD
Target domain data matrix Number of source samples Number of target samples
M
N
D
Data dimension
a E RM
Source marginal probability vector
RN
Target marginal probability vector
E
R MXN
Coupling matching matrix (transport plan)
C E MMN
Cost (distance) matrix
T
KL. divergence coefficient for SemiUOT
KL divergence coefficient for source (UOT)
7B
KL divergence coefficient for target (UOT)
a
Adjusted source marginal (via ETM)
3
Adjusted target marginal (via ETM)
f
Dual variable (SemiUOT, source)
9
Dual variable (SemiUOT, target)
Dual variable (UOT, source)
V
Dual variable (UOT, target)
Scalar dual variable (shared)
8
KKT multiplier variable Scaling factor:
(b.1)
[a,1]
LogSumExp smoothing parameter
V
Update step: v re
r+r
JemiUoT JUOT
Objective function of SemiUOT
Objective function of UOT Exact SemiUOT Equation
Lp
Lp
Approximate SemiUOT Equation Exact UOT Equation
Lu
Lo
Approximate UOT Equation
G(T,8) 8)
KKTTmultiplier regularization term: (π, 8)
LReg( (T))
Regularization term for OT (e.g. entropy (2) Regularization weight for multiplier term Regularization weight (entropy or E2)
NG
mee
Cij
Adjusted cost: Cty C2z + SGs Dual variable in MROT (source side) Dual variable in MROT (target side)
tb
Table 3: Important notations
B Proof of Proposition 1
Proposition 1. (Principles of Equivalent Transformation Mechanism for SemiUOT) Given SemiUOT with KL-Divergence JSemiUOT, one can obtain its Fenchel- Lagrang- multipliers form as:
M
fs
N
min f.g.
Σ a exp
- و5ا - 5)
(16)
1=1
1=1
s.t. f + gj + sij
= Ciji
8ij 2
16

---

where f. and Ç denote Lagrange multipliers. Moreover, SemiUOT problem can be further transformed into the form of optimal transport with marginal constraints as follows:
min Jp = ,C,T), 220
s.t. Tly= - exp ( 5 = T 1 b. T
(-++)==
(17)
When T oc, the source marginal probability is given as TlN wLa and wi (b. (b,1n)/(a,
1m)
Proof. To start with, we first review the definition of SemiUOT as shown below:
min SemiUOT (C, π)) 7KL (TIx|la)
2
(18)
s.t. π 1M
Then we can rewrite the optimization problem:
min J = (T) + rLL (TIN|
(Constrraint): π 71MM
(19)
s.t.
(Optional): NlN =
Note that we do not need know the exact value of beforehand. We adopt this optional constraint only for simplifying the following deduction. The Lagrange multipliers of SemiUOT with KL- Divergence is given as:
max min TSmitOOT = rKI. (T (la) (f + S. m) + (g S. b) +
f20 #20
(20)
(C- f 1 1M x T),
where f. g, 8 and Ç are dual variables. By taking the differentiation on Tij we have:
N
iJsmiUOT
T log
==
+ fi
+ C
+ (Cij - St - -9j 8.j)
OTgj
ai
(21)
N
Σ
Tij
= CG + r log
1=1
+ C - 9j - 88s
0.
Therefore, we can obtain the results as:
fi (-
Tij a; exp
T
(22)
Tij bj
im1
Ci fi - 9j 81j
After that, we can take these back into KL-Divergence simplify the calculation:
7KL (TIN|(a) + (f + C.
f + C |la + ( (f (fft.aen axp
f f
7KL
a exxp
(- fitt
Si li+
exp
[
1i+t
Oj exp
log
a; exp
aj
Σ
(Jz + () exp
0;
T
7
M
Si 1i+5 )
Ta2 exp
+ Ta
(23)
17

---

Therefore we can obtain its Fenchel- Lagrange multipliers form of SemiUOT as:
min JemiUUO -rKL (TIN|Ia) f
(f + (g S, 1
Txx (-+)
exp (-=) (g b) + O
(24)
s.1. Ji + 9j S Cij.
where Coust = =- E ra, and we can neglect it during the following calculation. Once we obtain the optimal solution on f g" and (*, will discover that:
||a (-5++*)
f -
rLL (TIN la) rKL
exxp exp
a.
Const.
(25)
Hence SemiUOT problem can be transformed into classic optimal transport problem accordingly.
Finally we can obtain the optimal solution on by considering @Jsamitior = 0 as below:
-=
log
Σ i=1
M
a. exp
(-
(-+)) - log
Σ
N
bj
(26)
Once we set + oo, the results of the limitation will be shown as:
lim a exp (-5) 04 T-++00
(b, 1N1
lim 0g exp T-++00
(27)
(a, 1
Therefore conclude the proof of the Proposition
C Proof of Proposition 2
Proposition 2. (Calculation for Approximate SemiUOT Equation) Given Approximate SemiUOT
equation Lp, it can be optimized via Equivalent Transformation Mechanism with Approximation (ETM-Approx). That is, ETM-Approx aims to solve the following equation for each fs:
by exp (-Cai
Coi
9hp -a, exp
(- J. 1.+5) exp T
0.
(28)
05.
[2-C22
k=1 exp
Specifically, we can adopt fixed-point iteration method for solving Eq. (88 at the l-th iteration as follows:
(--)) -4))-1op log
bj
(-Ci
Cij
7+1 log
exp
exp
W (ei(P()
(29)
JM
Ft+
log
a. exp
(-5) log
exp
(pp(-co
Cari
W (er(fe)
where v = Te/(T + e) for simplification and We,g (ft) denotes the corresponding calculation:
Ph -Cki -kC e
We,
exp
(30)
The proposed procedure can be convergent with a theoretical guarantee. Finally, updating the Lagrange multiplier& Ç by further considering VeLp = 0 via Ç = r[log(EM" a, exp((ff/77)
log(E> (2)= b,)]. One can achieve the optimal results on f and Ç* via iterative computing accordingly.
18

---

Proof. We first review the proposed Approximate SemiUOT Equation Lp as below:
M
N
M
Cki
min
Lp =
age
bj
log
+
(31)
8.
1=1
k=1
Then we consider optimizing Fo as follows:
oLp
age age- $
0
exp
fo
of.
TE
exp((-Co1/0)
(32)
Wes(f)
where (f) is defined as (0) At that time we adopt fixed-poine iteration method to optimize f accordingly:
30
]1
bee Cuslc
Pe+1
log
(aie=f) log
Fi (f........ Pin)
Wesh Wess
bie bye-
7e+1
log (ase- log
Σ
Fo (...... J33))
(33)
Wes(fe)
)1 Fis (R....,
N
bee Cye-Cargle
log (ame=a $)
log
We,
where v
Ie T+C.
By taking the gradient on F. (f:) w.r.t P3 we can observe that:
cxp (- Cas
OF.(P.)
TE
i
bi
0f.
T +
exp
Soi
Of?
W (fc)
bj
(P)
N
by exp
(Cry)
Cig
exp
L2 C-
(34)
T
exp
Coi
1=1
Wes
(es(f()
Wes(tt)
<.
Likewise we can obtain the result:
(F)
OF.(f²)
aF.
F. Ri. ...
01%
2 OS & Cet
Ru-Cuu
N
by exp
M
exp
T
Σ
T +
Wes(F
Wes (o)
b 1=1
u=1
1=1
7
< 1.
(35)
19

---

We can easily conclude that:
81 Pi..... Par) <1
F Pi..... 3b
<
(36)
FM f ..M
<1
Therefore, we can conclude that the proposed Approox method guarantees convergence according to Theorem 2.9 in [70].
Remark ETM-Approx can reach the linear convergence rate via the fixed-point iteration shown as O(N 1og(1//ecc) where Een = ||f f oc and f denotes the optimal solution.
Proof. We can formulate the whole optimization process for Proposition 2 as below
+++1 = Fi (f...... ,
fat = Fo
(A+t....
Pxt
F Fupdase (fi...., Phr)
(37)
7 FM Ph
According to the above discussion, we have the following results:
pet
Fupdate
f Fupdato
(
f
(38)
7
7
fe+1
gr
7
ge+z
T
Therefore the error between the solution given as:
fe+ at the (l + 1) iteration and the optimal results f
is
++E) Fr ) 800
+
(39)
Hence ETM-Approx can be linear convergence via the fixed-point iteration shown as ONN log(1/Eer)) where Eerr = |lf f* oooo and f denotes the optimal solution. L
D Algorithm for ETM-Based Method on SemiUOT
We also provide the pseudo algorithm of the proposed ETM-Based approachs (e.g., ETM-Exact, ETM-Approx, and ETM-Refine) for solving SemiUOT in Alg [ make clearer illustration.
E Proof of Proposition 3
Proposition (Principles of Equivalent Transformation Mechanism for UOT) Given UOT with Kl.-Divergence JUOT, its Fenchel-Lagrane multipliers form is given:
M
N
min
Σ
age
"itc Ta
+
bge
7h
(40)
1=1
j=1
s.t. U; + Ui + 8ij = Cijs
Sij 2 0,
20

---

where u, v, and Ç denote Lagrange multipliers. Moreover. UOT problem can also be transformed into classic optimal transport as follows:
min Tu = (x 220
u + +
TIN - a exp
a
(41)
Ta
s.t.
π 1M o exp
=
Note that when > the source and larget marginal probabilities can be determined as T TIN a and 1M = bj yur where wL = (b, (o,1x)/(0)) 1 respectively.
Proof. To start with, we first rewrite the optimization problem as below:
min J = (C, π. + Ta KL (TIx |a) + r,KL( 1 (bb) 200
(42)
s.L. (Optional) TlN = a, π MM B.
where and [3 denote the marginal probabilities for source and target domains respectively. Note that we do not need the true value fo a and / beforehand. That is, the constraints here are optional for the following UOT deduction. The Lagrange multipliers of UOT with KL-Divergence is given as:
max min JUOT KL (TN] 200 #20
(u + S, Alr) TTKL(T 1M|16) + (v S, 1m) GUOT,
(43)
where GUoT = Ei, (Ciz - 8 3.y) (C u & N - 1M @ v s,, π) and ut and
are dual variables. By taking the differentiation on Tty we have:
N
Σ
Tij
Σ Tij
OJuor
Ta log
+ Ui
+ S
+
Tb log
+ Vi C
+ (Cis - u - 11 -8j)
bj
N
Σ
Tij
Σ Tij
1=1
= Cij + Ta log
+ To log
8ij = O.
by
(44)
Then we can obtain the results:
U4 + S
Σ Tij 04 exp
Ta
J=1
M
(45)
Dj - S
Σ Tij = by exp
Tb
1=1
Ci - u, - 0j - =
By taking the above results into KL-Divergence, can further simplify the results:
M
- Toas exp (-iets)
T.KL (TINIla) + (u m.T) = Σ
+ Ta
(46)
(_9 (-)-5) + 7obs
7&LL [11
1m](b) + (v S. 1m) Σ
Toby exp
To
Therefore we can obtain its Fenchel-Lagrange multipliers form of UOT as:
min Juor - KL (TiN|la) (u + T.ll) - I2KL 1 (bb) - (1 G, T 1mm u.o.c
(-5)
a, exp (-m)
u ) + TO exp
S To
b, exp (-") v )) O Const
= Ta exp
exp
8... Us + 0y S Cijs
(47)
21

---

where Const = - Taa: - Toby. and we can neglect it during the following calculation. Once we obtain the optimal solution on u", v" and (* the KL-Divergence will turn out to be constants and therefore the original optimization problem can be transformed into classic optimal transport. Finally can obtain the optimal solution by considering ü.Toor
0 as below:
d
<=
Ta Ta Tb
log exp
-
log (b
b,exp exp
(--)
(48)
Once we set Ta and To + co, the results of the limitation will be shown as:
(-5
(b 1,)
lim
a; exp
lim
a; exp
=V
VWLai
Ta +0
Ta
Ta
a. 1ar)
Vj
)
5
(0.1M)
1
lim
bj exp
lim +00,7
by exp
by
by.
Tb
Tb
(b, 1,)
Vwz.
(49)
Therefore we conclude the proof of the Proposition 3.
-
F Illustrations of Optimization 1
Optimization 1. (Calculation of ETM-Approx approach for UOT) To start with, we first review the Exact UOT Equation defined as:
min Lu uiS
Fa
M
Gj exp
U4 +
+ To exp
(5)
5
Σ j=1
by
exp
1jj
Ta
T6
Tb
(50)
M
uu+5
SUPPRE[M] (ux Cks)
0g exp
+ To exp
by exp
Ta
Tb
where Uy -SUPpe[MM (uk Cky) meanwhile the marginal probabilities are set as Tl a O exp (-(u + ()/Ta) a and π 1M = b c exp (xp(-(v-)/m)) = B. Since the optimization problem in (9) is convex, we can also utilize block gradient descent optimize the problem. Specifically, we first fix o' and optimize variable u' at the 1-th iteration by replacing the original marginal probability in (q. with f accordingly to transform UOT into SemiUOT problem:
min Jú = (C, T) + T KL (TIN|la), z20
--- 5 3
(Constraint): : π 1' = exp
exp
(51)
Tbb
s.t.
uut a
(Optional): tiy = a 0
At that time, the Fenchel-Lagrange multipliers form of Eq. 51) is given via the Proposition 1:
ū. +
min T
Ta
exp
B -))
Ta
1=1
J=1
(52)
M
N
Ta
04 exp
Us +
inf kE[M]
[Ckj - ux] -S) B3-
J=1
Note that ñ and D denote the Lagrange multiplier for Eq. 51 while we have iy infRe[M] [C2y - un] = Uy and u u. To further accelerate the optimization process, we consider to make smooth approximation on replacing inf(.) as infRetaT|C&s -u] ~ -e loggE -y Ty. Therefore, first fix e! and optimize variable et the 1-th iteration solve the following
22

---

equation on Lú accordingly:
N
M
min Lú Ta at exp
Ug +
Σ
e log
by Chi
+
1=1
-k=1
üg +
Új
Fa a4 exp
bj exp
clog
+
Ta
Tb
(53)
The optimization objective shares a similar formulation as Eq 31 iteration method to optimize ú accordingly based on the Proposition
At that time we adopt fixed-point
]
Bye Cigle We,
x(+1
Tat Ta +
log (aie - 5.) -0=))) log
U1 (ui, Thhs)
B Casle
Tat
log 0ge (age- x2) - log
Σ
Us (ūi (MM)
(54)
Ta +
We, 77
]
B Byc-Cuasoo
7f+1 M
Tae Ta +
log (asse"
log
Σ
Uy (uf, '. T25s)
We,
The iteration process can be shown to converge efficiently based on Proposition 2. After that we fix and optimize variable 0 via 03 = - colog/E cxp( (ūş Ckj)/c))- We can achieve the optimal solution û' and 0" via iteratively computing via the above procedure accordingly. Finally, N update via Ç = (TaTt/(T (lo) 0, exp((-ū; /Ta)) log وド=10 by exp( (-66/1/))))
G Algorithm for ETM-Based Method on UOT
We also provide the pseudo algorithm of the proposed -TM--asedd approachs (e.g., ETM-Exact, ETM-Approx and ETM--eefie) for solving UOT in Alg.2 to make more clear illustration.
H Proof of Proposition
Proposition 4. (The Definition and Usage of KKT-Multiplier Regularization) Given any OT with multiplier& 8, one can obtain accurate solution π via proposed KKT-multiplier regularization term G (TT, s), which formulates Multiplier Regularized Optimal Transport (MROT):
min JG (C, π +n (TT, Megg (T))
(55)
s.t. Tl a. 1 3
where LReg (T)) denotes the regularization term on π. a, 33rm denote the final marginal probabilities obtained by ETM ETM-based method, while MeRg TG denotes the hyper parameter, Ideally, nGG should be set as a relatively large number. Meanwhile the dual form of MROT given as:
w + o Ö.s
1b) + (B, Φ) -Meeg max = (a, 66
(56)
T|Reg
where Ü, = Ciz + TGSij & and 2b denote the Lagrange multipliers for MROT. (.) denotes and one can figure out the matching results of π via solving the the functionn of CHey() following equation V V..g CReg (TT) (v' + o3 Ezy) /TReg.
23

---

Algorithm 2 The algorithm of ETM-Based method on UOT
Input: C: cost matrix; a. b: initial marginal probability; Tas Tb, Hyper parameters.
Randomly initialize the value of init.
Choose ETTM-Exact ETM-Approx or ETM-Refine UOT for optimization.
(1) Function: ETM-Exact on UOT(C, a, b, Ta, Tb, u 1== uil) Optimize L-BFGS algorithm optimize Lu as:
M
ag exp (- 14 +
5 Tb
suPkE(M) (us: Cks)
min Lu Ta
+ Tb exp
by exp
Ta
Tb
Optimize via 0j
inf (Ckj - kc[M]
Optimize via Ç
Inln_ +a+t
log a, exp (- 26
log (b. exp (-x) as shown in Eq.448)
(b.exp/
Return: The optimal solutions of u²" v² and C" (2) Function: ETM-Approx UOT(C, a b, Ta, Tb, T0=0 wnil)) Randomly initialize the value of 6" for = to T" do Optimize पt via Proposition 2 to optimize Lt as:
min Lú
Ta
M
aj exp (-
Ug +
+
N
by exp
Bi (3)5))
c
clog
M
Ri
Cki
+
To
i=1
==1
Optimize o via oy end for
- log
M
k= exp(( Cki)/e)].
Optimize ( via Ç Th log a, exp (-2)
@
log (b (xe (-2) as shown in Eq.(48
TT+
Return:
The optimal solutions of u 6" and Ç
(3) Function: ETM-Refine on UOT(C, a, b, To, u T0 init)
Obtain प Epprox on UOT(C, a, b, Tay Tb. ū== u lnit).
Obtain a = ETM-Exact on UOT(C, b, Ta, Tb, === = it).
Return: The optimal solutions of u and C*.
Proof. We first provide the Lagrange multiplier of MROT as:
max min JMROT (C, TT) n,( 8) + CReg (TT) (zb, TlN - -a) -0, 1IM -3)
2. #20
Cis + nGS1J - U4 Ojj Tij + C (Tis))
(ax, vb) + (B, Φ) + Reg inf
1/Reg
tis + Øj Ois Tzj Liag (Trig)
(ax, 1b) + (B, Φ) Mag sup a
Σ
Meg
2.j
1/ + Φj Tzs
(a,, vb) + 1,, Φ) mReg Fitg
1)Reg
(57)
At that time we have the following results:
OJMROT = 0
V Vy. CReg
wh + 0j Ozj
Olş
Oyi OJMROT 0 0Φ,
T/Rez
(58)
1/ + Oj O2s
Voy CRex
= B3
MReE
By taking the differentiation on Tij we have:
OJMROT C.s + (Reg V Vany fReg (Tes) 1/ 1b
(59)
Omg
24

---

For instance, when Regg(T) - - denotes as the entropy regularization term, the dual form of MROT-Ent shown as;
4 + Ø3 Cij
max JMROT-Eat = =ox, + (B, Φ) - RReg Σ
exp
4.
RReg
1.
(60)
1/s + 0j Czs
Tij exp
MRReg
When Leeg (T) (TT, x2/2 denotes the square-norm regularization term, the dual form of MROT- Norm is shown as:
db. + Φ - Cij
7Reg
max JMROT-NNAN -Nom (a, 26) + (B, () 4..0
2 3
neeg
(61)
w/ Φj Coj
Asj
TRee
Therefore we conclude the proof of Proposition 4.
Extensions. MROT can be even extended to solve classic optimal transport problem. That is, the classic optimal transport problem and its dual form can be represented as below:
max Jor = ( ) (g g
J = arg min π.: C) #
9j 84) Cifs
8Gj
(62)
s.t. TlN a, 11=B 3
s.t.
inf (Cas - f kE[M]
9j
where f 0 and represent the dual variables. To solve the dual form of the classic OT problem, unconstrained optimization techniques, such as L-BFGS or the Sinkhorn algorithm, can be employed to optimize for Then one can further adopts MROT to solve for classic optimal transport.
In summary, the time complexity of the proposed ETM-AAprox+-MRRTTEEE or -RM--O Norm method is provided as O (NM log (1/Eere) + N where d, denotes the number of itera- tions on MROT. Meanwhile, the time complexity the proposed ETM--eeine-MRRT-EEn or ETM- Refine+MROT-Nom method is provided O (N M log (1/Earr) + N M (log M dd + N Md,) where dr denotes the number of iterations on ETM-Refine
I Experiments on Domain Adaptations
We conduct the unsupervised domain adaptation tasks on Digits, Office-Home, and VisDA. Digits is the classic dataset for digit classification which contains three standard digit classification datasets: MNIST [53], USPS[45) and SVHN [76]. Each dataset consists of 10 classes of digits, ranging from to 9. Office-Home [12 is a standard benchmark dataset which includes 15,500 images in 65 object classes in office and home settings, forming four dissimilar domains: Artistic images (Ar), Clip Art (CI), Product images (Pr), and World (Rw). VisDA [8T] a large-scale computer vision dataset two domains, i.c., Synthetic and Real with 280K images in 12 classes.
Datasets.
Performance. We also conduct the UDA domain adaptation tasks Digits and VisDA and the results are shown in Table We can observe that the proposed ETM-Refine with MROT-Norm on SemiUOT achieves state-of-the-art performance on Digits and VisDA.
J Experiments on Partial Domain Adaptations
Datasets. We further conduct the domain adaptation tasks on new datasets, i.e., Office-3/ 88 and ImageCLEF [3]. Office-31 is the commonly-used computer vision dataset for domain adaptation
25

---

Table 4: Classification accuracy (%) on Digits (Source: LeNet) and VisDA dataset (Source:ResNet500
for UDA (unsupervised domain adaptation) task
Method
S-MM
M M-+U
U-M
Avg
VisDA
Source
68.3=0.3
65.3+0.5
66.2-022
66.6
52.4
DeepJDOT
25
95.4=0.1
95.620.4
96,4=0.3
95.8
68.0
JUMBOT
98.9=0.1
96.7+0.5
98.2-0.1
97.9
72.5
JUMBOT UOT M--ffinn-- MROT-Ent)
99.4=0.1
98.7=0.3
99.2=0.1
99.1
73.6
JUMBOT UOT Refine MROT-Norm)
99.7=0.11
99.3+0.2
99.6=0.1
99.5
74.2
Table 5: H-score (%) on Office- Office-Home Home for universal unsupervised domain adaptation
Method
Ar-CCI Ar-
A -K Cl-AA
C1-1it
Cl-Kw Pr-AAr Pt-+CI Pr- Kw-tAr
Kw-+CI
Rw-iPt
Avg
09
45.45
0SBP 103
19.59
45.08
16.17
45.20
45:34
46.15
45.26
10.54
45.75
45.08
41.63
46.90
44.46
BAN 1ni
51.64
51.70
$4.30
61.14
$7.63
61886
50.38
47,62
61445
02.87
$2.61
65.19
56.58
DCC 131
$7.97
$4.05
58.01
71.64
70.62
77.53
64.34
73.60
71,95
80.96
75.13
90.36
70.16
TNT [K4
61.90
74.00
80.20
73.50
71.40
79.00
74.20
69.50
82
77.
70.10
$1.20
76.70
UniOT Ld
67:27
36.05
73.51
77.33
75.54
63.35
77.77
65.37
81.02
76.57
UnKO UUTTETM
MROT
08.65
81.77
87.994
75.88
79.03
86.21
77.29
68.77
78.59
73.62
52.85
78.97
UniOI + UOTEETM Refiee MRDE-NNraa
69.02
$1.95
88.36
76.12
79.36
86.49
77.03
09.25
$7.30
78,93
74.18
82.96
79.25
with 4,652 images from three different domains: Amazon (A), Webcam (W) and DSLR (D). Target
domain has the first 10 classes (alphabetical order) following (IT). ImageCLEF contains 3 domains
with 12 classes, i.c., Caltech (C), ImageNer (I) and Pascal (P). Target domain has the first 6 classes
(alphabetical order) following [66].
Baselines. We involve DeepJDOT 25 ROT [5], JUMBOT 34 ETN [2]. AR m-POT
(77] MOT [65]. as the model baselines for the domain adaptation task. (1) DeepJDOT 25 first adopts optimal transport into solving domain adaptation problem with deep learning framework.
(2) ROT [5] adopts robust optimal transport into adversarial training for domain adaptation. (3)
JUMBOT adopts mini-batch unbalanced optimal transport method for domain adaptation. (4)
ETN 12 utilizes example transfer network to jointly learn domain-invariant representations and
the progressive weighting scheme. (5) AR 42 adopts adversarial reweighting strategy on source
domain data for alignment. (6) m-POT 7 adopts partial optimal transport method in the mini-batch settings for domain adaptation. (7) MOT (65) adopts masked unbalanced optimal transport technique
on considering label information for PDA tasks.
K Experiments on Universal Domain Adaptations
We further conduct the experiments on universal domain adaptations. That is, there are shared labels between the source and target domains. Additionally, there are private labels specific to each domain [33 IT.. We conduct the universal domain adaptations on both Office-31 and Office-Home. Specifically, set the first 10 classes in alphabetical order the common label set, the next 10 classes as source private label and the rest 1l classes as target private label for Office-31. Likewise, we set the first 10 classes in alphabetical order the common label set, the next 5 classes as source private label and the rest 55 classes as target private label for -ffice-Home. We involve the following models as baselines: (1) OSBP [9 adopts domain adversarial learning for open-set domain adaptation, (2)
UAN [08] utilizes transferability criterion for universal domain adaptation, (3) CMU (38] learns to
detect open classes with uncertainty estimation, (4) DCC (54) adopts domain consensus clustering
for adaptation, (5) TNT [8] adopts evidential neighborhood contrastive learning for adaptation, (6)
UniOT [16] adopts unbalanced optimal transport with adaptive filtering for transferring.
We adopt the same experimental settings as UniOT [6]. We utilize the commonly-usee H-score [38) to validate the final results as shown in Table 5
6 Note that UniOT + UOT(ETM MROT)
only replaces the entropic UOT in UniOT with our proposed
method with MROT. From MROT-Norm) reaches the best performance, indicating that UOT with ETM + MROT can provide more accurate matching results.
that, we observe that UniOT UOT
L Experiments on Treatment Effect Estimation
Datasets for Treatment Effect Estimation, We further conduct Refine on treatment effect
estimation with two semi-synthetic datasets IHDP (97 and ACIC [10]. IHDP set to estimate the effect of specialist home visits infants" potential cognitive scores and it contains 747 observations and 25 covariates. ACIC includes 4802 observations and 58 covariates, which comes from the collaborative perinatal project.
26

---

Table 6: H-Score (%) on 31 for universal unsupervised domain adaptation
Method
A-+
A-W
D-*A
W-+
W-=D
Avg
ResNet
43
49.78
47.92
48.48
54,94
48.96
55.60
50.94
OSBP
39
51.14
50.23
49.75
55.53
50.16
57.20
52, 34
UAN
59.68
60.11
70.62
60.34
71.42
63.46
CMU 38
68.11
67.33
71.42
79.32
72.23
80.42
73.14
DCC
88.50
78.54
70.18
79,29
75.87
88.58
80.16
TNT
18
85,70
80.40
83,80
92.00
79.10
91.20
85.37
UniOT
[6
86.97
48
88.35
98.83
87.60
96.57
91.13
UniOT L:OTTTTMM Refine MROT-Fntt
89.47
89.
97.94
92.31
UniOT UOT(ETM-Reeine MROT-Norm)
88.67
90.14
90.03
99,58
89.42
98.46
92.72
Table 7: Experimental results on Treatment Effect Estimation tasks,
(PEHE)
ACIC (AULUC)
IHDP (PEHF)
IHDP (AULUC)
In-Sample
Out-Sample
In-Sample Out-Sample
In-Sample
Out-Sample
In-Sample
Out-Sample
OLS
3.749
4.340
0.843
0.496
3.856
5.674
0.652
0.492
TARNer 91
3,236
3:254
0.886
0.662
0.749
1.788
0.654
0.711
PSM K7
5.228
5 5.094
0.884
0.745
3.219
4.634
0.740
0.681
CFR-WA SS 97
3.128
3 3,207
0.873
0.669
0.657
1.701
0.656
0.715
ESCFR 10-1
2,252
2.316
0.796
0,754
0.502
1,282
0.665
0.719
ESCFR + UOTIETM- Retine MROT-EEN Ent)
2.327
2.261
0.839
0.814
0.197
1.275
0.769
0.763
ESCTR UOTEETM Refine MROT MROT-Nem)
2,104
2,216
0,883
0,839
0.475
1.146
0.798
0.802
Results. We involve the following models as baselines: (1) OLS 2 utilizes least square regression with treatment as covariates, (2) TARNet (97] adopts integral orobability metries for adaptation, (3) PSM (87) adopts propensity score for causal effects, (4) CASS (87 utilizes standard optimal transport for adaptation, (5) ESCFR [104] further utilizes unbalanced optimal transport for adaptation. We adopt the same experimental settings as ESCFR [04]. We utilize Precision in Estimation of Heterogeneous Effect (PEHE) 97 and Area Under the Uplift Curve (AUUC) 77 for the evaluation. Note that ESCFR + -OT + MROT-Ent) only replaces the entropic UOT in ESCFR with our proposed approximate-to
ETM-Refine + MROT-Norm. The experimental results are shown in Table 7 From that, we can observe that ESCFR + UOT(ETM-RRefi best performance, indicating the efficacy of our proposed ETM-R- --R-eeinne method.
MROT-Norm) achieves the
M More Experimental Results
Parameter sensitivity. We tune TąG on SemiUOT via ETM-Refine with MROT-Norm in range of niG E {0, 1, 100} using the same data samples shown in Fig I and show the results in 5 We can observe that when 7G is smaller (e.g., nJ or 1/G I). the proposed KKT-multiplier regularization term G(T, s) = (π. s) may struggle to play a significant role during the optimization process. Meanwhile when 7c 100, ETM-Refine with MROT-Norm can achieve more accurate matching results. We can conclude that choosing a larger value of nJ can fully utilize the knowledge provided by KKT multiplier and enhance the final results. Moreover, we conduct the experiments for the absolute error when UOT and report the results in Fig (b). Larger value on `JG can provide more useful KKT- multiplier information and boost the model performance and therefore we set 7/G = 100 empirically. Furthermore, we conduct the hyper parameter experiments by varying = (0.01, 0.05, 0.1, 0.5, 1] on UDA task in Office-Home and report the results in F() We can observe that smaller value of e can provide a more accurate approximation with higher accuracy and thus we set c 0.01.
1 with N 500 synthetic data samples on both SemiUOT and
ETM + Norm (To- 0)
ETM MROT-Norm (11 1)
ETM MROT-Norm (1c- 100)
Ground Truth
10
10
10
20
20
20
30
30
1.0
30
10
20
30
40
10
20
30
40
10
20
30
40
Figure 5: The matching results on ETM + MROT-Nore SemiUOT with different values of NG = {0, 1, 100).
27

---

Hyper fg
Hyper
Office-Home
EntSemlUGT) ETM ETM-NROT (M0T-NooM/5emUO)
1.5
1.5
ETMy MROTNoM(UOT)
73.5
1.0
1.0
72.5
Ererr
0.5
Error
Classilic
72.0
71.5
JUMBCT+UOTIE MOTTIETMMROTEE
JUMBOT+UOTIETH JOTTTTT-TTTTT
71.0
1
10
100
0
10
100
0.01
0.05
0.1
0.5
f1 on SemiUUT (Synthetic Dataset)
(b) fl, (Syathetic Dataset)
(c) on UOT (UDA Home)
Figure 6: The hyper parameters on fJG and
SemiUOT
UOT
0.825
0.082
0.820
0.080
0.815
<
0.078
0.810
0.076
0.805
0.074
ETM-Approx,
ETM-Approx,
0.800
20
40
20
40
80
Epoch
Epoch
(a) The result on SemiUOT
(b) The result on UOT
Figure 7: The results of Ç and Lp on UOT and SemiUOT.
Miscellaneous Discussions
N.1 The role of ( in ETM-based method
We first discuss why we should involve translation invariant Ç in both Lu and Lp. Specifically, we first analyze the case of SemiUOT, The Fenchel-Lagrange conjugate form of SemiUOT without translation invariant mechanism is given as:
M
Ji
N
min f.g.C
Og exp
by9j
(63)
1=1
j=1
s.t. fi + 9j S Cij-
We adopt c-transform Eq. 63 obtain the unconstrained optimization problem as:
min Lp
Σ a exp
inf [Cks fulby,,
(64)
kE[M]
We adopt L-BFGS to optimize Lp using the same data samples as shown in Fig. with 7 = Meanwhile, the translation invariant term Ç in SemiUOT should be calculated follows:
M
(-A)
) log
N
Ç = T log
aj exp
b
(65)
Ideally, Ç should equals to 0 since ΣM a, exp
44) Σn by. However, observe that
<> >> 0 during the iteration epoch on optimizing Lp as shown in Fig aa) Therefore we can conclude that is indispensable during the calculation SemiUOT. Likewise, the Fenchel-Lagrange conjugate form of UOT without translation invariant mechanism is given as:
(-")
) + To exp (--)
min v.u
Ta a, exp
s.t. 0s + U2 S Cij-
(66)
28

---

Here we can adopt c-transform on (66) to obtain the unconstrained optimization problem as:
min LU Ta a4 exp
Uy
N
by exp
sup M k=
(u+ Cks)
(67)
Ta
Th
We also adopt L-BFGS optimize Lu using the same data samples shown in Fig.2 with Ta = 1. Meanwhile, the translation invariant term in UOT should be calculated as follows:
=
Tb
log
a. exp exp
(---)
Fa (-m))
u
log
b,
exp exp
(-o) Tb
(68)
Ta + To
Ideally, should equals to 0 since
[a, exp
(- 2 exp exp
(- However, we can observe
that Ç > during the iteration epoch on optimizing Lu as shown in Fig 7b). Therefore we can conclude that indispensable during the calculation
UOT. In conclusion, the concept of translation invariant was first proposed in 196. However, [96] only utilizes translation invariant for entropic UOT. We highlight that, in this paper, we further extend translation invariant for standard UOT/SemiUOT scenario. We illustrate that translation invariant is essential solving UOT and SemiUOT problems.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction sections reflect the paper's contributions and scope in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper focuses exclusively on discrete Semi-UOT and UOT problems. Other types of optimal transport problems, such as GW-based Semi-UOT and UOT, are beyond the scope of this work and remain promising directions for future research.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification: All theoretical claims are correctly induced with reasonable assumptions and correct proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide the details of experimental implementation and algorithms in Section 5 main paper and Appendix D, G, J, K, for reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
31

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the code in appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/ubblicgguudee CoodeSumeeieeeeee ssi iessonPolll molyicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide full experimental details with the code, in the main paper and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report our results with five times of repetitions and show the significant
results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
32

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide both computation complexity and computation time in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, we do.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
This work has no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
35

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
36


Reviews:
[{"review_id": "jcTkYT4K3Q", "reviewer": "Reviewer_PbZU", "summary": "This paper provides a new technique for solving the unbalanced-OT (UOT) and semi unbalanced-OT (semi-UOT) problems. Both problems allow for partial optimal transport solutions (where not all mass is transported). In addition to the cost of the transport plan, an additional penalty function is added, which contributes to the objective function based on the amount of untransported mass. (In semi-OT, only one distribution is considered in this additional penalty function, while UOT considers both sides, with possibly different coefficients). Different variants of this “untransported mass” penalty function have been considered, but this paper specifically uses KL divergence.\n\nThe key contribution of this technique is a transformation, where any instance of the UOT or semi-UOT problem (under KL-divergence) can be transformed into an instance of the regular OT problem, in such a way that the solution to this regular OT problem instance provides a solution to the original UOT or semi-UOT problem. This transformation is named the “Equivalent Transformation Mechanism” (ETM). Furthermore, multiple variants of ETM are presented, offering tradeoffs in computation time and accuracy – these are named ETMExact, ETMApprox, and ETMRefine.\n\nAs both the semi-UOT problem and UOT problem have been investigated before, this paper seeks to differentiate itself in terms of quality, with a specific emphasis on not using entropy regularization like most previous methods, resulting in sparser solutions. The paper also provides extensive experimental evaluation on real and synthetic data. These include multiple variations of ETM, multiple prior work methods / baselines, and some different penalty functions for the untransported mass.", "questions": "Questions:\n-\tJust a question : Is it not true that Semi-OT is a special case of UOT, since you can always set the hyperparameter coefficient of one distribution to 0? I ask this because, one of your selling points is that your approach works for both. Why can’t existing UOT approaches apply to Semi-OT directly?\n\n-\tUnder table 1, you take the best approach without UOT, called JUMBOT, and you add to it various methods of computing UOT, such as MM-UOT, GEM-UOT, $\\ell_2$ norm solver, and sparse solver. All of these UOT approaches offer a modest improvement over JUMBOT. Then, you show that your ETM + MROT approach improves upon the previous UOT approaches for this task by an additional modest amount. However, I find it odd that, for all of your other similar tables, including Tables 2, 4, 5, 6, 7, you omit all variants of “state of the art + UOT(some other solver that’s not yours)”, and instead only consider your approach for the UOT component. Based on the trend in Table 1, it seems as if all UOT variants, yours or not, seem to improve upon the baseline “state of the art” without UOT. That’s not so important for your paper. Instead, your burden of proof is to illustrate that your variant of UOT specifically outperforms other existing variants of UOT in practice. Otherwise, what’s the role of the experiments here?\n\n-\tPlease detail how your approach compares to the existing UOT approaches with regards to time complexity and practical performance. The only clear discussion I saw of this is Figure 3, which doesn’t quite clear things up for me. The thorough treatment of running time seems lacking in both the theory as well, since the iteration count is not bounded. Furthermore, when I see sizes like N = 50 for the experiments, I start to wonder why you can’t bring N higher. Often, OT is fine with N = 1000 or more without an issue. How fast is your approach?\n\n-\tLine 282 : You performed 5 experiments, but that is not a very large sample. How sure can you be that, if the experiment were repeated, the average would be comparable to what you have here? \n\n-\tFigure 3 : You have a couple of charts / labels swapped here. Please address this. I would also recommend adding a consistent color scheme for the plots across UOT and semi-UOT charts respectively. Furthermore, the list of variants of your algorithm between (b) and (c) are different. What I would really like to see is an accuracy versus runtime comparison of your approach(es) versus existing approaches. Finally, the only running times given here are for $\\tau = 1$, which you stated in your introduction other approaches work well for. So, why not give your efficiency for large $\\tau$?\n\nCorrections : \n\nLine 34 – 35 : Grammar : “While … solutions” is an incomplete sentence. Reword.\n\nLine 58 : Did you mean “MROT”, not “MGOT”?\nAlso, see comments about Figure 3 above.", "limitations": "Nothing to note.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths : \n-\tVery extensive experimental evaluation, which shows an improvement over existing in terms of accuracy when applied to real-world applications.\n\n-\tThorough treatment of technical details. \n\n-\tThe technique is flexible in that any OT solver can be used along with ETM, and it can be easily applied to UOT and Semi-OT. In some sense, ETM seems to act as a “booster” of sorts when added to some existing approaches, based on the experimental results.\n\nWeaknesses : \n-\tThe experimental evaluations, in terms of accuracies, offer relatively modest improvements over the existing approaches, usually a couple percentage points (although this improvement is quite consistent). I have some concern about the experimental design.\n\n-\tSome parts of the complexity analysis of the ETM approach seem unclear in relation to other work. I would like to clearly see a comparison of Big-O time complexities of the approaches and steps of this work as well as descriptions of Big-O time complexities of other work. I want to be sure that the solution-time tradeoff of your approach is comparable to existing approaches.\n\n-\tI have a few questions about the experiments, which might be easily addressable in the author response.", "was_revised": true, "final_justification": "Thank you authors for your response. After reviewing your rebuttal, as well as the discussion from the other reviewers, I have increased my rating accordingly. I would recommend, in the final version, that the discussion of convergence analysis be highlighted more clearly in the main body of the paper.", "rebuttal": "- W1.1: The experimental evaluations, in terms of accuracy, offer relatively modest improvements over the existing approaches.\n\nA1.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.\n\n- W1.2: I would like to clearly see a comparison of Big-O time complexities of the approaches. \n\n\nA1.2: The time complexity of the proposed method can be analyzed via the following procedure:\n\n(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).  \n\n(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. \n\n(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)$.\n\n(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. \n\n- 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?\n\nQA1: 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.\n\n- Q2: All variants of “state of the art + UOT(some other solver that’s not yours)” are omitted.\n\nQA2: 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. \n\nWe are willing to add more experimental results below. The experiment results on ImageCLEF for partial UDA (Table 2) are given below:\n\n| Method | I->P | P->I | I->C | C->I | C->P | P->C | Avg |\n|-|-|-|-|-|-|-|-|\n| MOT | 87.7 | 95.0 | 98.0 | 95.0 | 87.0 | 98.7 | 93.6 |\n| MOT + UOT (MMUOT) | 87.8 | 95.2 | 98.1 | 95.0 | 87.2 | 98.7 | 93.7 |\n| MOT + UOT (GEMUOT) | 87.9 | 95.4 | 98.1 | 95.2 | 87.3 | 98.8 | 93.7 |\n| MOT + UOT (Sparse Solver) | 88.0 | 95.4 | 98.2 | 95.1 | 87.3 | 98.8 | 93.8 |\n| MOT + UOT (ETM-Refine + MROT-Ent) | 88.3 | 95.6 | 98.4 | 95.3 | 87.6 | 99.0 | 94.0 |\n| MOT + UOT (ETM-Refine + MROT-Norm) | 88.7 | 95.9 | 98.7 | 95.8 | 88.0 | 99.1 | 94.4 |\n| MOT + SemiUOT(Robust-SemiSinkhorn) | 88.4 | 95.3 | 98.5 | 95.5 | 87.3 | 98.7 | 93.9 |\n| MOT + SemiUOT(ETM-Refine + MROT-Ent)| 89.1 | 96.2 | 99.2 | 96.1 | 88.5 | 99.4 | 94.8 |\n| MOT + SemiUOT(ETM-Refine + MROT-Norm)| 89.6 | 96.7 | 99.4 | 96.5 | 89.1 | 99.6 | 95.2 |\n\nThe experiment results on Office-Home for universal UDA (Table 5) are given below:\n\n| Method | Ar->Cl | Ar->Pr | Ar->Rw | Cl->Ar | Cl->Rw | Cl->Rw | Pr->Ar | Pr->Cl | Pr->Rw | Rw->Ar | Rw->Cl | Rw->Pr | Avg |\n|-|-|-|-|-|-|-|-|-|-|-|-|-|-|\n| UniOT  | 67.27  | 80.54  | 86.03  | 73.51  | 77.33  | 84.28  | 75.54  | 63.33  | 85.99  | 77.77  | 65.37  | 81.92  | 76.57 |\n| UniOT + UOT (MMUOT)  | 67.45  | 80.69  | 86.32  | 73.84  | 77.86  | 84.68  | 75.91  | 64.62  | 86.13  | 77.95  | 68.06  | 82.25  | 77.15 |\n| UniOT + UOT (GEMUOT)  | 67.97  | 81.06  | 86.81  | 74.43  | 78.25  | 85.30   | 76.58  | 65.69  | 86.72  | 78.14  | 70.34  | 82.51  | 77.82 |\n| UniOT + UOT (Sparse Solver) | 67.71  | 80.95  | 86.64  | 74.22  | 78.13  | 84.89  | 76.37  | 65.11  | 86.48  | 78.06  | 69.53  | 82.44  | 77.54 | \n| UniOT + UOT (ETM-Refine + MROT-Ent) | 68.63  | 81.72  | 87.94  | 75.88  | 79.03  | 86.21  | 77.29  | 68.77  | 87.14  | 78.59  | 73.62  | 82.83  | 78.97 |\n| UniOT + UOT (ETM-Refine + MROT-Norm)| 69.02  | 81.95  | 88.36  | 76.12  | 79.36  | 86.49  | 77.03  | 69.25  | 87.30   | 78.93  | 74.18  | 82.96  | 79.25 |\n\nThe experiment results on Office-31 for universal UDA (Table 6) are given below:\n\n| Method   | A->D  | A->W  | D->A  | D->W  | W->A  | W->D  | Avg |\n|-|-|-|-|-|-|-|-|\n| UniOT  | 86.97 | 88.48 | 88.35 | 98.83 | 87.60  | 96.57 | 91.13 |\n| UniOT + UOT (MMUOT)   | 87.12 | 88.79 | 88.54 | 98.95 | 88.08 | 96.62 | 91.35   |\n| UniOT + UOT (GEMUOT)  | 87.43 | 89.18 | 89.02 | 99.19 | 88.34 | 97.31 | 91.74  |\n| UniOT + UOT (Sparse Solver)  | 87.26 | 89.05 | 88.93 | 99.12 | 88.26 | 97.23 | 91.64 |\n| UniOT + UOT (ETM-Refine + MROT-Ent) | 88.25 | 89.62 | 89.47 | 99.48 | 89.10  | 97.94 | 92.31  |\n| UniOT + UOT (ETM-Refine + MROT-Norm)| 88.67 | 90.14 | 90.03 | 99.58 | 89.42 | 98.46 | 92.72 |\n\nFrom that, we can observe that our proposed method can still consistently achieve the best performance against some other solvers.\n\n- Q3.1: Time complexity analysis should be provided.\n\nQA3.1: Please kindly refer to A1.2.\n\n- Q3.2: How fast is your approach when $N = 1000$? \n\nQA3.2: We have done the time consumption experiments on SemiUOT/UOT in Fig.3 when $N = 1000$. The detailed experimental results are given below:\n\n| Method | Time (for UOT) | Time (for SemiUOT) |\n|-|-|-|\n| GEMUOT | 29.54s  | - |\n| ETM-Approx + MROT-Ent | 17.45s | 23.29s |\n| ETM-Refine + MROT-Ent  | 19.90s | 24.13s |\n| ETM-Refine + MROT-Norm | 22.78s | 28.62s |\n\nFrom the results, we can easily find that ETM+ MROT improves efficiency when the amount of points is large. \n\n- Q4: How about the results if the experiment were repeated?\n\nA4: 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.\n\n(1) Results on Office-Home and VisDA (UDA)\n\n| Method for UDA  | Avg on Office-Home | Avg on VisDA  |\n|-|-|-|\n| JUMBOT + UOT (ETM-Refine + MROT-Ent) | 73.12 ± 0.16 | 73.59 ± 0.20 |\n| JUMBOT + UOT (ETM-Refine + MROT-Norm)| 73.43 ± 0.11   | 74.22 ± 0.15 |\n\n(2) Results on Office-Home and ImageCLEF (Partial UDA)\n\n| Method for Partial UDA  | Avg on Office-Home | Avg on ImageCLEF |\n|-|-|-|\n| MOT + UOT (ETM-Refine + MROT-Ent)  | 81.78 ± 0.22  | 94.03 ± 0.10  |\n| MOT + UOT (ETM-Refine + MROT-Norm)  | 82.11 ± 0.15 | 94.38 ± 0.08  |\n| MOT + SemiUOT (ETM-Refine + MROT-Ent) | 84.83 ± 0.13  | 94.82 ± 0.08 |\n| MOT + SemiUOT (ETM-Refine + MROT-Norm)  | 85.22 ± 0.09  | 95.19 ± 0.05 |\n\n(3) Results on Office-Home and Office-31 (Universal UDA)\n\n| Method for Universal UDA  | Avg on Office-Home | Avg on Office-31 |\n|-|-|-|\n| UniOT + UOT (ETM-Refine + MROT-Ent) | 78.95 ± 0.32  | 92.28 ± 0.27  |\n| UniOT + UOT (ETM-Refine + MROT-Norm)  | 79.22 ± 0.25  | 92.70 ± 0.22  |\n\nFrom that we can observe that our proposed method can still achieve stable and the best performance. \n\n\n- Q5.1: Some typos (e.g., charts/labels swap and color not consistent) here.\n\nQA5.1: We will fix them in the camera-ready version. \n\n- Q5.2: Running time versus accuracy should be discussed.\n\nA5.2: We mainly report the results on Office-Home with the UDA task.  In our experiments, we set the batch size to 512.  \n\n|Method|Average Time (s) for one execution |Accuracy|\n|-|-|-|\n|JUMBOT with UOT|3.3s| 70.0  |\n|JUMBOT + GEMUOT|5.2s| 71.6 |\n|JUMBOT + ETM-Approx + MROT-Ent|3.7s| 72.3 |\n|JUMBOT + ETM-Refine + MROT-Ent |4.1s| 73.1 |\n|JUMBOT + ETM-Refine + MROT-Norm |4.6s| 73.4 |\n\nFrom this, we can conclude that ETM-Refine + MROT-Ent achieves the best performance with a slight increase of execution time. \n\n- Q5.3: Running time on different values of $\\tau$ should be provided.\n\nA5.3: We conduct the experiments with $N=1000$ samples in synthetic data for $\\tau = \\{10, 100\\}$ and report the computation time:\n\n| Method  | $\\tau$ = 10 (UOT) | $\\tau$ = 100 (UOT) | $\\tau$ = 10 (SemiUOT) | $\\tau$ = 100 (SemiUOT) |\n|-|-|-|-|-|\n| GEMUOT | 37.08s | 46.64s | -  | -  |\n| ETM-Approx + MROT-Ent  | 19.26s | 25.35s  | 24.04s  | 32.19s |\n| ETM-Refine + MROT-Ent  | 25.12s  | 31.75s | 28.78s  | 39.45s |\n| ETM-Refine + MROT-Norm | 32.94s  | 38.71s | 36.52s  | 47.36s |\n\nWe can observe that our proposed ETM-based method can still run efficiently for larger $\\tau$.\n\n- Comment: Some corrections.\n\nResponse: (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.”\n\nWe 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.\n\nKind regards,\nAuthors"}, {"review_id": "5z8JpfyAux", "reviewer": "Reviewer_FSeC", "summary": "This paper addresses the challenge of accurately solving discrete SemiUOT and UOT problems. They propose an Equivalent Transformation Mechanism (ETM) approach to determine the marginal probability distributions of SemiUOT with KL divergence. A KKT-Multiplier regularization term is proposed with Multi plier Regularized Optimal Transport (MROT) to achieve more accurate matching results. Extensive experiments demonstrate the effectiveness of our proposed methods in addressing SemiUOT and UOT problems. Overall, this paper contributes a practically effective framework for solving SemiUOT and UOT.", "questions": "1.\tIn (27), $f^*$ seems also relative to the $\\tau$ and it is ignored when setting $\\tau \\to \\infty$.\n2.\tThere are many computations of the form $\\exp(\\frac{\\cdot}{\\epsilon})$ in ETM+MROT-ENT. Could numerical instability arise when $\\epsilon\\to 0$?\n3.\tIn MROT, KKT multipliers are used as a regularization mechanism to induce sparsity. What is the theoretical validity for this design, and how does it affect optimization stability or convergence?\n4.\tWhat is the relationship between the optimal solution and optimal value of ETM-Exact and ETM-Approx? A theoretical explanation is  recommended.\n5.\tIt would be positive if the authors demonstrate the adaptability of this method to outliers.\n6.\tIf $u^*$ and $v^*$ are inexact due to the computational error, will the Corollary 2 and Proposition 4 still hold?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The SemiUOT and UOT problems are clarified explicitly as relaxations of classical OT. The ETM formulation allows the exact and approximate solutions and reduces the complexity of solving these problems. It is effective to use the solved marginal distributions for the transfer to standard OT problems.\n2. This method balances the trade-off between computing exact solutions and improving efficiency in ETM, and further leverages the obtained exact multipliers for regularization, resulting in sparser and more accurate transport matching.\n3. The comprehensive experiments demonstrate the effectiveness of ETM+MROT, which consistently yields state-of-the-art results across a diverse set of metrics in many applications.\n\nWeaknesses:\n\n1.\tTheoretically, coherence and completeness of this paper should be improved.  On one hand, the authors should first state assumptions, such as the existence of a c-transform and other implicit conditions used in the proofs, and summarize the conclusion in a theorem. On the other hand, there is a lack of detailed proof and analysis of the convergence rate.\n2.\tThe writing and organization could be improved to enhance clarity. The organization and layout seems disordered, and the inclusion of numerous detailed explanations in the main text hinders the understanding of the conclusions. Moreover, the paper lacks a diagram or concise pseudocode illustrating the overall algorithm overview. Typos, such as the incorrect notation in equation (20) and the misuse of inner product symbols in equations (23) and (25), further affect the readability of the paper.\n3.\tA better approach would be to design a customized optimization algorithm tailored for solving the OT problem, rather than directly applying L-BFGS. On one hand, leveraging the inherent structure of the problem may lead to faster computation. On the other hand, we are also concerned with the convergence behavior of the optimization algorithm for this specific problem.\n4.\tOne potential theoretical weakness is the lack of discussion on robustness to outliers. In real-world datasets, noisy or out-of-distribution samples can degrade OT performance. It would be valuable for the authors to either empirically or theoretically analyze how their approach behaves under such perturbations.\n5.\tThe novelty of the proposed approach may be somewhat limited. ETM resembles the discrete form of Equation (9) in Choi et al. (2023) under KL regularization, and MROT adapts standard regularized OT solvers with an additional multiplier. Clarifying the conceptual gap from prior work would strengthen the perceived contribution.", "was_revised": true, "final_justification": "I suggest borderline accept. The authors have resolved most of my concerns.", "rebuttal": "- W1.1:  Theoretically, coherence and completeness of this paper should be improved. \n\nA1.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.\n\n- W1.2: There is a lack of detailed proof and analysis of the convergence rate.\n\nA1.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^*)$.  \n\n- W2.1: The organization and layout seems disordered, and the inclusion of numerous detailed explanations in the main text hinders the understanding.\n\nA2.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.\n\n- W2.2: The paper lacks a diagram or concise algorithm pseudocode.\n\nA2.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. \n\n- W2.3: Some typos exist.\n\nA2.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. \n\n- W3: Design a customized optimization algorithm for solving the OT problem rather than directly applying L-BFGS is better. How about the convergence behavior?\n\nA3: 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}))$.\n\n- W4 and Q5: It would be positive if the authors demonstrate the adaptability of this method to outliers and out-of-distribution samples.\n \nA4 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.   \n\n- W5: The novelty may be somewhat limited.\n\nA5: **We strongly disagree with this comment.** Theorem in [Choi] and our proposed ETM differ significantly in several aspects:\n\n(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. \n\n(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$. \n\n(3) We provide time complexity and convergence analysis for the proposed method which [Choi] did not provide.\nIn 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.\n\n- Q1: In (27), $f^∗$ seems also relative to the $\\tau$?  \n\nQA1: 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$:\n$$\n\\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\n$$\nTherefore, $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.\n\n- Q2: Could numerical instability arise for ETM when $\\epsilon \\rightarrow 0$?\n\nQA2: 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]).\n\nRef:\n\n[1] Deriving the Gradients of Some Popular Optimal Transport Algorithms\n\n[2] Computational Optimal Transport: With Applications to Data Science\n\n- Q3: What is the theoretical validity for this design of MROT, and how does it affect optimization stability or convergence?\n\nQA3: 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. \n\n- Q4: What is the relationship between the optimal solution and optimal value of ETM-Exact and ETM-Approx?\n\nQA4: 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 $. \n\nHence 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:\n\n$$\n|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\n$$\n\nTherefore 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$.\n\nRef: [1] Smooth minimization of non-smooth functions.\n\n- Q6:If obtained $u$ and $v$ are inexact due to the computational error, will Corollary 2 and Proposition 4 still hold?\n\nQA6: We answer this question with two aspects. \n\n(1) Corollary 2 is strictly held when $u$ and $v$ (or $f$ and $g$) are the optimal solutions. \n\n(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:\n\n| Method | ε=0.001 | ε=0.01 | ε=0.1 | ε=1 | \n|-|-|-|-|-|\n| ETM-Approx + MROT-Ent | 0.14 | 0.15 | 0.21 | 0.34 |\n| ETM-Refine + MROT-Ent | 0.10 | 0.11 | 0.14 | 0.22 | \n\nThe 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.\n\nWe 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.\n\nKind regards,\nAuthors"}, {"review_id": "CLmAmnMM1P", "reviewer": "Reviewer_teoF", "summary": "This paper proposes a new framework for solving discrete Semi-Unbalanced Optimal Transport (SemiUOT) and Unbalanced Optimal Transport (UOT) problems. Existing methods often rely on entropy regularization, which leads to dense and inaccurate transport plans. To address this, the authors introduce the Equivalent Transformation Mechanism (ETM), which reformulates SemiUOT and UOT problems into classic optimal transport problems. The authors develop three variants: ETM-Exact, ETM-Approx, and ETM-Refine.\n\nThe paper also proposes Multiplier Regularized Optimal Transport (MROT), which uses KKT multipliers to guide the transport plan and improve solution quality. \n\nExperiments on synthetic data, domain adaptation benchmarks, and treatment effect estimation show that ETM combined with MROT improves accuracy and efficiency over existing methods.", "questions": "1. In line 133, 'We iteratively update $L_U$ to reach the optimal solutions'. It seems that $L_U$ doesn't appear before this sentence. \n\n2. In line 162, 'Since $\\hat{f}^\\star$ is close to $f^\\star$'. Is there a theoretical bound for this?\n\n3. 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?\n\n4. 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?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Quality: The paper presents a solid and well-justified theoretical contribution. The proposed Equivalent Transformation Mechanism (ETM) is rigorously derived, and its variants (ETM-Exact, ETM-Approx, ETM-Refine) are grounded in convex analysis and KKT conditions. The integration with Multiplier Regularized Optimal Transport (MROT) provides a framework to enhance the sparsity and accuracy of transport plans. The empirical evaluation is extensive, covering both synthetic and real-world datasets across domain adaptation and treatment effect estimation tasks. \n\nOriginality: The paper introduces a new perspective by transforming discrete SemiUOT and UOT problems into classic OT through reweighted marginals. The use of KKT multipliers as a regularization term in MROT appears to be an interesting idea that improves transport plan quality. \n\nSignificance: This proposed method has potential impact on applications where interpretability and sparsity are important, such as domain adaptation, generative modeling, and causal inference.\n\nClarity: The paper is generally clear and well-organized. The connection between the ETM variants and standard OT is carefully explained. The derivations are detailed, and algorithmic procedures are summarized in pseudocode, which aids reproducibility.", "was_revised": true, "final_justification": "The only concern I have is about the choice of the hyperparameter $\\epsilon$. The numerical experiments suggest that the convergence relies largely on $\\epsilon$ and the selection of this parameter in the paper (and the rebuttal) is mostly heuristic. While a smaller $\\epsilon$ is advocated by the theoretical analysis, it may cause numerical issues. \n\nOverall, the paper is solid. I champion the final acceptance of the paper.", "rebuttal": "- 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.\n\nQA1: 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.\n\n- Q2: In line 162, 'Since $\\hat{f}^{*}$ is close to $f^{*}$'. Is there a theoretical bound for this?\n\nQA2: 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 $. \n\nHence 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:\n\n$$\n|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\n$$\n\nTherefore 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$.\n\nIn conclusion, the solution on ETM-Approx will be relatively close to the exact solution provided by ETM-Exact with a smaller $\\epsilon$.\n\nRef: [1] Smooth minimization of non-smooth functions.\n\n\n- 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?\n\n\nQA3: 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, \ni.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. \nIn practice, we typically select $\\epsilon = 0.01$, as it strikes a good balance between performance and convergence stability. \nTherefore, we recommend using this value in most scenarios, but depending on the specific problem or data scale, slight adjustments may be necessary.\n\n\n- 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?\n\n\nQA4: 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.\n\nWe 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. \n\nKind regards,\nAuthors"}, {"review_id": "RYv0d1KuMq", "reviewer": "Reviewer_ETJd", "summary": "This paper tackles the problem of efficiently obtaining exact solutions for the Unbalanced Optimal Transport and Semi-Unbalanced Optimal Transport problems. The proposed method, called the Equivalent Transformation Mechanism (ETM), enables the determination of marginal probabilities on which a classical Optimal Transport optimization can be performed.", "questions": "Questions:\n\n1) In the well-known article \"Free boundaries in optimal transport and Monge-Ampère obstacle problems\" 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?\n\n2) The classical unbalanced problem typically includes constraints such as $\\pi 1_N \\leq a$ and $\\pi^T 1_M \\leq b$. These are not included in the formulation of the UOT problem in the paper. Is there a particular reason for omitting them?\n\n3) 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 $\\ast$ in expressions like $f^\\ast$ and $\\zeta^\\ast$? (A similar comment applies to Proposition 3.)\n\n4) Regarding the statement of Proposition 1: I suggest rephrasing it as, \"Given the SemiUOT functional with KL divergence $J_{\\text{SemiUOT}}$...\" A similar revision could be applied to Proposition 3.\n\n5) Do the new marginals $\\alpha$ and $\\beta$ represent vectors encoding the weights of discrete probability measures? That is, do their coefficients add to 1?\n\n6) I did not understand the first sentence on line 180. Could the authors clarify it?\n\nSuggestions:\n\n1) Corollary 1 is not formally stated, so I would suggest presenting it as a Remark instead.\n\n2) While not necessary, a brief discussion of the advantages and disadvantages of SemiUOT compared to UOT would enrich the paper.\n\n3) 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.\n\n4) I suggest referencing Algorithms 1 and 2 explicitly in the main text, even if only briefly, to guide the reader.\n\nTypos and Minor Comments:\n\n1) Line 44: After \"i.e.,\" I suggest using a lowercase letter and not capitalizing the following word.\n\n2) Lines 179, 180, and the paragraph between lines 193 and 199: Add commas after \"Hence,\" \"Then,\" and \"After that,\" respectively.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The article addresses a fundamental problem in the optimal transport community. Rather than relying on popular regularization terms in the UOT and Semi-UOT problems—which allow for efficient computations but yield inexact and dense solutions—the authors propose a novel idea: transforming these problems into classical optimal transport problems by computing the exact marginal probability distributions that participate in the transport process. Moreover, for the Semi-UOT version, the authors propose a way to smooth out the $L_p$ functional, highlighting its usefulness to get a good initialization for the main method of interest. In addition, the proposed ETM approach presented in Section 4.1 allows for the computation of a so-called multiplier \"s\" (Corollary 2), which is used to formulate a new regularized version of the optimal transport problem (Section 4.2).\n- Experiments were conducted with synthetic and real-world datsets. \n\nWeaknesses: \nThe algorithms are provided in the appendix, but the methodology is somewhat convoluted to follow in the main text, even though the authors include all the necessary components. I understand that space limitations can make it difficult to fully detail the steps that a reader would ultimately need to follow.", "was_revised": true, "final_justification": "I thank all the authors for your answers, clarifications and comments. I decide to keep my score (Accept).", "rebuttal": "- W1: The algorithms are provided in the appendix which should have appeared in the main text.\n\nA1: We will add the algorithm 1-2 into the main text in the camera-ready version.\n\n- 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?\n\nQA1: 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. \n\n- 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?\n\nQA2: 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:\n\n$$\n\\min_{\\pi} J = \\langle {C}, \\pi \\rangle  \\quad \\quad\ns.t.   \\pi1_{N} \\le a, \\pi^T1_{M}\\le b, 1_{M}^{T}\\pi1_{N} = S\n$$\n\n[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.\n\nRef: \n\n[1] On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm\n\n[2] Partial Optimal Transport with Applications on Positive-Unlabeled Learning\n\n- 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.)\n\nQA3: 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. \n \n- 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.\n\nQA4: Thank you for your helpful suggestion. \nWe agree with your proposed rephrasing and will revise the statement of Proposition 1 to: \"Given the SemiUOT functional with KL divergence ${J}_{SemiUOT}$...\". \nA similar revision will also be applied to Proposition 3 for consistency.\nWe appreciate your input and will incorporate this change in the revised manuscript.\n\n- 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?\n\nQA5: 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.\n\n\n- Q6: I did not understand the first sentence on line 180. Could the authors clarify it?\n\nQA6: 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.\n\n\n- S1: Corollary 1 is not formally stated, so I would suggest presenting it as a Remark instead.\n\nSA1: 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.\n\n\n- S2: While not necessary, a brief discussion of the advantages and disadvantages of SemiUOT compared to UOT would enrich the paper.\n\nSA2: 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.\n\nSemiUOT 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.\n\nWe will add a brief discussion of these differences in the revised manuscript to clarify the distinct contexts and applications of SemiUOT and UOT.\n\n\n- 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.\n\nSA3: 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.\n\n\n- S4: I suggest referencing Algorithms 1 and 2 explicitly in the main text, even if only briefly, to guide the reader.\n\nSA4: 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.\n\n\n- Typos1: Line 44: After \"i.e.,\" I suggest using a lowercase letter and not capitalizing the following word.\n\nTA1: Thank you for your valuable feedback. We will make the necessary correction and use a lowercase letter after \"i.e.\" as suggested.\n\n\n- Typos2: Lines 179, 180, and the paragraph between lines 193 and 199: Add commas after \"Hence,\" \"Then,\" and \"After that,\" respectively.\n\nTA2: Thank you for your helpful suggestion. We will add the commas after \"Hence,\" \"Then,\" and \"After that,\" as recommended.\n\nWe 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. \n\nKind regards,\nAuthors"}]

Author rebuttal:

Meta-review: The paper presents a novel technique for solving unbalanced optimal transport and semi-unbalanced optimal transport.
Its main technical contribution is the Equivalent Transformation Mechanism (ETM), which converts UOT and SemiUOT problems (with KL divergence) into a classical Optimal Transport (OT) problem. This allows for the use of existing, efficient OT solvers. 

Based on the  positive consensus among all reviewers, the  technical merit and novelty of the proposed  methods 
and the responses to all reviewer questions, I recommend acceptance of this paper.
Decision: Accept (poster)