InfoOT: Information Maximizing Optimal Transport
Authors: Ching-Yao Chuang
Stefanie Jegelka
David Alvarez-Melis
Venue: Submitted to ICLR 2023 (2023)
Keywords: Optimal Transport
Unsupervised Alignment
Domain Adaptation
Mutual Information

Abstract: Optimal transport aligns samples across distributions by minimizing the transportation cost between them, e.g., the geometric distances. Yet, it ignores coherence structure in the data such as clusters, does not handle outliers well, and cannot integrate new data points. To address these drawbacks, we propose InfoOT, an information-theoretic extension of optimal transport that maximizes the mutual information between domains while minimizing geometric distances. The resulting objective can still be formulated as a (generalized) optimal transport problem, and can be efficiently solved by projected gradient descent. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples. Empirically, InfoOT improves the quality of alignments across benchmarks in domain adaptation, cross-domain retrieval, and single-cell alignment.

Under review as a conference paper at ICLR 2023
INFOOT: INFORMATION MAXIMIZING OPTIMAL TRANSPORT
Anonymous authors Paper under double-blind review
ABSTRACT
Optimal transport aligns samples across distributions by minimizing the trans- portation cost between them, e.g., the geometric distances. Yet, ignores coher- ence structure in the data such as clusters, does not handle outliers well, and can- not integrate new data points. To address these drawbacks, we propose InfoOT, an informatiiontheorcctii extension of optimal transport that maximizes the mutual in- formation between domains while minimizing geometric distances. The resulting objective still be formulated a (generalized) optimal transport problem, and can be efficiently solved by projected gradient descent. This formulation yields new projection method that is robust to outliers and generalizes unseen sam- ples. Empirically, InfoOT improves the quality of alignments across benchmarks domain adaptation, cross-domain retrieval, and single-cell alignment.
INTRODUCTION
Optimal Transport (OT) provides general framework with strong theoretical foundation com- pare probability distributions based on the geometry of their underlying spaces (Villani, 2009). Be- sides its funddmental role mathematics, OT has increasingly received attention in machine learn- ing due to its wide range of applications in domain adaptation (Courty et al., 2017; Redko et al., 2019; Xu al., 2020), generative modeling (Arjovsky et al., 2017; Bousquet et al., 2017), represen- tation learning (Ozair et al., 2019; Chuang et al., 2022), and generalization bounds (Chuang et al., 2021). The development of efficient algorithms (Cuturi, 2013; Peyré et al., 2016) has significantly accelerated the adoption of optimal transport in these applications.
Computationally, the discrete formulation of OT seeks a matrix, also called transportation plan, that minimizes the total geometric transportation cost between two sets of samples drawn from the source and target distributions. The transportation plan implicitly defines (soft) correspondences across these samples, but provides no mechanism to relate newly-drawn data points. Aligning these requires solving new OT problem from scratch. This limits the applicability of OT, e.g., to stream- ing settings where the samples arrive in sequence, very large datasets where can only solve OT on subset. In this case, the current solution cannot be used on future data. To overcome this fundamental constraint, a line of work proposes to directly estimate a mapping, the pushforward from source to target, that minimizes the transportation cost (Perrot et al., 2016; Seguy et al.. 2017). Nevertheless, the resulting mapping highly dependent on the complexity of the mapping function (Galanti et al., 2021).
OT could also yield alignments that ignore the intrinsic coherence structure of the data. In particular, by relying exclusively on pairwise geometric distances, two nearby source samples could be mapped disparate target samples, as Figure 1, which undesirable in some settings. For instance, when applying OT for domain adaptation, source samples with the same class should ideally be mapped to similar target samples. To mitigate this, prior work has sought to impose structural priors on the OT objective, e.g., via submodular cost functions (Alvarez-Melis et al., 2018) or Gromov- Wasserstein regularizer ( (Vayer et al., 201 8b;a). However, these methods still suffer from sensitivity to outliers (Mukherjee al., 2021) and imbalanced data (Hsu et al., 2015; Tan al., 2020).
This work presents Information Maximization Optimal Transport (InfoOT), an information- theoretic extension of the optimal transport problem that generalizes the usual formulation by infusing it with global structure in form of mutual information. In particular, InfoOT seeks alignments that maxi- mize mutual information, informmtioon-hhoneti measure of dependence, between domains. To

---

Under review as a conference paper at ICLR 2023
OT
InfoOT
InfoOT w/ Barycentric
InfoOT w/ Conditional
Source
Source Target
Souree
Scuace
Targtt
Target
Target
Pig
the Shunus
Soutliers
Figure 1: Illustration of InfoOT on 2D point cloud. Compared to classic OT, InfoOT preserves the cluster structure, where the source points from the same cluster are mapped to the same target cluster. For projec- tion estimation (dashed lines), the new conditional projection improves barycentric projection with better outlier robustness and -ample generalization.
do so, we treat the pairs selected by the transportation plan as samples drawn from the joint distribu- tion and estimate the mutual information with kernel density estimation based on the paired samples (Moon et al., 1995). Interestingly, this results in an OT problem where the cost is the log ratio between the estimated joint and marginal distributions fxy (z, ()x show that using cost combining mutual information with geometric distances yields better align- ments across different applications. Moreover, akin to Gromov- Wasssestennn (Mémoli, 2011), the mutual information estimator only relies on intra-domain distances, which -unlike the standard OT formulation- makes it suitable for aligning distributions whose supports lie in different met- ric spaces, e.g., supports with different modalities or dimensionality (Alvarez-Melis & Fusi, 2020; Demetci et al., 2020).
Empirically, we
By estimating a joint density, InfoOT naturally yields a novel method for out-of-sample transporta- tion by taking an expectation over the estimated densities conditioned on the source samples, which refer conditional projection. Typically, samples are mapped via barycentric projection (Ferradans et al., 2014; Flamary et al., 2016). which corresponds to the weighted average of target samples, where the weights are determined by the transportation plan. The barycentric projection inherits the disadvantages of standard OT: sensitivity to outliers and failing to generalize to new samples. In contrast, our proposed conditional projection is robust to outliers and cross-domain class-ime imsalancdd data (Figure and 4) by averaging over samples with importance sampling, where the weight is, again, the ratio between the estimated joint and marginal densities. Furthermore, this projection is well-defined even for unseen samples, which widens the applicability of OT in streaming or large-scale settings where solving OT for the complete dataset prohibitive.
In short, this work makes the following contributions:
We propose InfoOT, information--heorreii extension to the optimal transport that regularizes alignments by maximizing mutual information;
We develop conditional projection, new projection method for OT that is robust to outliers and class imbalance in data, and generalizes new samples;
We evaluate our approach via experiments in domain adaptation, cross-domain retrieval, and single-cell alignment.
2 RELATED WORKS
Optimal Transport Optimal transport provides elegant framework compare and align distri- butions. The discrete formulation, also called Earth Mover's Distance (EMD), finds an optimal cou- pling between empirical samples by solving linear programming problem (Bonneel et al., 2011), To speed up the computation, Cuturi (2013) propose the Sinkhorn distance, an entropic regularized version of EMD that can be solved more efficiently via the Sinkhom-Knoop algorithm (Knight, 2008). Compared to EMD, this regularized formulation typically yields denser transportation plans, where samples can be associated with multiple target points. Various extensions of OT have been proposed to impose stronger priors, e.g., Alvarez-Melis et al. (2018) incorporate additional structure by leveraging a submodular transportation cost, while Flamary et al. (2016) induce class coherence (GW) distance (Mémoli, 2011) is a variant of OT in which the transportation cost is defined upon intra-domain pairwise distances. Therefore, GW has been adopted to align 'incomparable spaces' (Alvarez-Melis & Jaakkola, 2018; Demetci et al., 2020) as the source and target domains do not need to lie in the same space. Since the GW objective is no longer linear program, it is typically optimized using projected gradient
through group-sparsity regularizer. The Cromov-Wassereee
2

---

Under review as a conference paper at ICLR 2023
descent (Peyré et al., 2016; Solomon et al., 2016). The Fused-GW, which combines the OT and GW objectives, was proposed by Vayer et al. (2018a) to measure graph distances.
Mutual Information and OT The proposed InfoOT extends the standard OT formulation by max- imizing a kernel density estimated mutual information. Recent works (Bai et al., 2020; Khan & Zhang, 2022) also explore the connection between OT and information theory. Liu al. (2021) consider a semi-supervised setting for estimating a variant of mutual information, where the un- paired samples are leveraged minimize the estimation error. Ozair et al. (2019) replace the KL divergence in mutual information with Wasserstein distance and develop loss function for repre- sentation learning. In comparison, the objective of InfoOT is to seek alignments that maximize the mutual information while being fully unsupervised by parameterizing the joint densities with the transportation plan. Another line of work also combines OT with kernel density estimation (Canas & Rosasco, 2012; Mokrov al., 2021), but focuses on different applications.
BACKGROUND ON OT AND KDE
Optimal Transport Let { E X" and {yA l E ym be the empirical samples and Raxm be the transportation cost for each pair, e.g. Euclidean cost Ci ||=; Mjll Given two sets of weights over samples p E R7 and q E RT where Ex= P: -in= qi = 1, and a cost matrix C, Kantorovich's 's formulation of optimal transport solves
min (T,C), I[p, q) {T E R 11 P. P. 1, -), rell(p.q)
where 11(p.q q) is of transportation plans that satisfies the flow constraint. In practice, the Sinkhorn distance (Cuturi, 2013), an entropic regularized version of OT, can be solved more efficiently via the Sinkhorn- Knopp algorithm. In particular, the Sinkhorn distance solves minre)((p.a) -I,)) where (TT) - -En Pij log ij is the entropic regularizer that smooths the transportation plan.
-
Kernel Density Estimation Kernel Density Estimation (KDE) is a non- non-parametric density esti- mation method based on kernel smoothing (Parzen, 1962; Rosenblatt, 1956). Here, we consider generalized KDE for metric spaces (X,dx) dx) and (V, dyy (Li et al., 2020; Pelletier, 2005). In partic- ular, given paired dataset {x4, 3 E {x",, )²" sampled i.i.d. from an unknown joint density fxY and kernel function K : + R. KDE estimates the marginals and the joint density as
Knn fx(x) ' Kn, (dx(x,x))); fxy(2, 1 E Kn, xx.) Krn, (dx(v. w)), (1)
n
where (!( /Z and the normalizing constant 7, makes equation integrate to one. The bandwidth param- eter h controls the smoothness of the estimated densities. Figure 2 illustrates
0.4
bander
No100 points
035
bandwrdh 0.5
0:30
Randwrdth =
Imput distribuiin
example of KDE on ID data. In this work, we do not need to estimate the normalizing con- stant as only the ratio between joint and marginal densities fxy y)/ (fx fx)fy(()) (y)) considered while estimating the mutual information. For all the presented experiments, we adopt the Gaussian kernel:
0:30
6.13
8:10
8:20
Figure Example KDE. The
1 Zn
cxp (-
dx(sr,x))2 2h?0²
KA (dx(x,
bandwidth affect the smoothness.
where x² controls the variance. The Gaussian kernel has been successfully adopted for KDE be- yond the Euclidean space (Li et al., 2020; Said al., 2017), and found it to work well in our experiments. For simplicity, we also set hj = h2 = for all the experiments.
4 INFORMATION MAXIMIZING OT
Optimal transport captures the geometry of the underlying space through the ground metric in its objective. Additional information not directly captured in this metric -such as coherence structure- will therefore be ignored when solving the problem. This is undesirable in applications
3

---

Under review as a conference paper at ICLR 2023
High MI
Low MI
Source
Torget
Plan 1'
Plan
Joint Density of
Joint Density of
(a) One-to-one Mappings
(b) Joint Density estimated with KDE
Figure 3: Measuring Structure with Mutual information. (a) The Po and To are two one-to-one mappings where l. preserves the cluster structure and Ia is random permutation; (b) The estimated joint density of I' more concentrated than the one To, which also leads to higher mutual information under KDE.
where this additional structure matters, for instance in domain adaptation, where class coherence is crucial. As concrete example, the cluster structure in the dataset in Figure is ignored by classic OT. Intuitively, the reason for this issue is that the classic OT is too local: the transportation cost considers each sample separately, without respecting coherence across close-by samples. Next, we show that mutual information estimated with KDE can introduce global structure into OT maps.
4.1 MEASURING GLOBAL STRUCTURE WITH MUTUAL INFORMATION
Formally, mutual information measures the statistical dependence of two random variables X,
I(x,)) = J, fx.x (x. log
fxy (2. (x dxdy
(2)
(x(2))v(u)
where fxY is joint density and Sy are marginal probability density functions. For paired datasets, various mutual information estimators have been defined (Belghazi et al., 2018; Moon al., 1995; Poole al., 2019). In contrast, are interested in the inverse: given umpaired samples {8y J
{z, 1
can we find alignments that maximize the mutual information?
Discrete v.s. Continuous. An immediate idea is to treat the discrete transportation plan T as the joint distribution between X and Y. and write the mutual information as Σij L'g log(nml';s) = log(nm) - HT). this case, maximizing mutual information would be equivalent to minimizing the entropic regularizer HT) introduced by (Cuturi, 2013). For finite set of samples, this mutual information estimator is trivially maximized for any one-to-one mapping as then H(T) 0. Figure (a) illustrates two one-to-one mappings a and I's between points sampled from multi-mode Gaus- sian distributions, where I' preserves the cluster structure and I is simply a random permutation. They both maximize the mutual information estimate above, yet Fa is better alignment with high coherence. In short, directly using the transportation plan estimated from finite samples the joint distribution to estimate mutual information between continuous random variables is problematic. In contrast, joint distributions estimated with KDE tend to be smoother, such as I in Figure 3 (b). This suggests that KDE may lead better objective for the alignment problem.
4.2 INFOOT: MAXIMIZING MUTUAL INFORMATION WITH KDE
Instead of directly interpreting the OT plan the joint distribution for the mutual information, we use it to inform the definition of a different one. particular, we treat Fs as the weight of pair (Ia, Br) within the empirical samples drawn from the unknown joint distribution with density fxy. Intuitively, F defines what empirical samples we obtain by sampling from the joint distribution. Given transportation plan r, the kernelized joint density in equation can be rewritten as
fr(,,w) EEE PiyKn (dx(a, Kr. ()((M))))
The 1/n factor is dropped the plan I' is already normalized Eie Dij 1). Specifically, replace the prespecified paired samples in equation with the ones selected by the plan r.
4

---

Under review as a conference paper at ICLR 2023
Definition (Kernelized Mutual Information). The KDE estimated mutual information reads
(X,Y)) = Σ Tig log (1)) f(x)f(w))
am Ex, Ka (dx(1,,zx)) Kn. (dy(us: 91) En (dx(2t, Σ, Kn (dy (dy(y) 31))
Ery
ray log 6
The estimation has two folds: (1) approximating the joint distribution with KDE, and (2) estimating the integral in equation 2 with paired empirical sample (r, Mj) weighted by Túj. The normaliz- ing constant Z in equation (1) cancels out while calculating the ratio between joint and marginal probability densities. To maximize the empirical mutual information (r(X, Y), the plan has to map close-by points i, & to close-by points j.l. Maximizing this information can be interpreted as an optimal transport problem:
Σre log (Han)f()) Fr(me,y)) u5)
(InfoOT)
max Tell(p.q)
(x(,Y)= = min
relKp.q)
Instead of pairwise (Euclidean) distances, the transportation cost is now the log ratio between the estimated marginal and joint densities. The following lemma illustrates the asymptotic relation between the kernel estimated mutual information and the entropic regularizer.
Lemma 2. When - 0 and (-) is the Gaussian kernel, we have (X, Y) - H(T) +ogg log(mm))
When the bandwidth h goes to zero, the estimated density is the of delta functions centered at the samples, and the estimated mutual information degenerates back to the standard entropic regularizer (Cuturi, 2013).
Note that the formulation of InfoOT does not require the support of X and to be comparable. Sim- ilar to Gromov- Wasserstein (Mémoli, 2011), InfoOT only relies on intra-domain distances, which makes it an appropriate objective for aligning distributions when the supports do not lie in the same metric space, e.g., supports with different modalities or dimensionalities, as section 6.4 shows.
Fused InfoOT: Incorporating the Geometry. When the geometry between domains is infor- mative, the mutual information can act as regularizer that refines the alignment. Along with weighting parameter X, we define the Fused InfoOT as
Σre (Cr (Co) + x log 1.
(fla))
fr(e, vn)) )
(F-InfoOT)
min rell(p.q)
(T,C) (xx,)) min rell(p.g)
The transportation cost becomes the weighted sum between the pairwise distances C and the log ratio of joint and marginals densities. As Figure iillustrates, the mutual information regularizer ex- cludes alignments that destroy the cluster structure while minimizing the pairwise distances. Prac- tically, we found F-InfoOT suitable for general OT applications such as unsupervised domain adap- tation (Flamary et al., 2016) and color transfer (Ferradans al., 2014) where the geometry between source and target is informative.
4.3 NUMERICAL OPTIMIZATION
As the transportation cost is dependent on r, the objective is no longer linear I and cannot be solved with linear programming. Instead, we adopt the projected gradient descent introduced in (Peyré et al., 2016). In particular, Benamou et al. (2015) show that the projection can be done by simply solving the Sinkhorn distance (Cuturi, 2013) if the non-linear objective is augmented with the entropic regularizer (I'), For instance, we can augment F-InfoOT as follows:
min rell
(T,C)
eT)))
In this case, the update of projected gradient descent reads
(I, (I,C- - (x, -eH))) Tefl(p.q)
T++1 + arg min
(5)
The update is done by solving the sinkhorn distance (Cuturi, 2013), where the cost function is the gradient to the objective of I-foOO... We provide detailed derivation of (5) in Appendix A.2.
5

---

Under review as a conference paper at ICLR 2023
Matrix Computation Practically, the optimization can be efficiently computed with matrix mul- tiplications. The gradient with respect to the transportation plan I is
0l((X,Y) log f(.)) ir
((( Σ k.
Kv (dx( xx)) Kn (dy(us, (,),).))
Mw
fr(mn,
Let Kx and Ky be the kernel matrices where (Kx)i = Kn (dx - xz)), (Ky)is =
Kr ([dy(y: 7₁)). The gradient has the following matrix form:
1) = log (KxTK) @ Mx + Kx (T (TOKxITT) KY
where (Mx)s = fx.). (My); = f(vi) are the marginal density vectors and @ denotes element- wise division. The gradient can be computed with matrix multiplications in On m + nm²).
CONDITIONAL PROJECTION WITH INFOOT
Many applications of optimal transport involve mapping source points target domain. For in- stance, when applying OT for domain adaptation, the classifiers are trained on projected source sam- ples that are mapped to the target domain. When X' y. given a transportation plan r, a barycentric projection maps source samples to the target domain by minimizing the weighted cost to target sam- ples (Flamary et al., 2016; Perrot et al., 2016). The mapping is equivalent to the weighted average of the target samples when the cost function is the squared Euclidean distance c(z, v) || y/l²:
m
m
T3 + arg min NEV
Σ Toylly 11 2==1
T Te j=1
(6)
Despite its simplicity, the barycentric projection fails when (a) aligning data with outliers, (b) imbal- anced data, and (c) mapping new samples. For instance, if sample x, mostly mapped to outlier yj. then its projection will be close to y/, Similar problems occur when applying OT for domain adaptation. If the size of same class differs between domains, false alignments would emerge due to the flow constraint of OT as Figure 4 illustrates, which worsen the subsequent projections.
Since the barycentric projection relies the transportation plan to calculate the weights, any new source sample requires re-computing OT to obtain the transportation plan for it. This can be compu- tationally prohibitive in large-scale settings. In the next section, we show that the densities estimated via InfoOT can be leveraged to compute the conditional expectation, which leads to new mapping approach that is both robust and generalizable.
5.1 CONDITIONAL EXPECTATION VIA KDE
When treating the transportation plan probability mass function in the right-hand hand side of (equa- tion 6), the barycentric projection resembles the conditional expectation F|Y|X = z). Indeed, the classic definition of barycentric projection (Ambrosio al., 2005) is defined the integral over the conditional distribution. But, this again faces the issues discussed in section 4. Instead, equipped with the densities estimated via KDE and InfoOT, the conditional expectation can be better estimated with classical Monte-Carke importance sampling using samples from the marginal Py:
E [v] E [ y
E, (x
1 fr(z, ~ Z fx())
Pr|X=2 y- fv(
v-r (
y5
where Z z= Em fr (z, 1/)/ (v₂)) is the normalizing constant. Compared to the barycen- tric projection, the importance weight for each yi is the ratio between the joint and the marginal densities. To distinguish the KDE conditional expectation with barycentric projection, we will refer to the proposed mapping conditional projection.
Robustness against Noisy Data. By definition in equation 3, the joint density fr(x, y) measures the similarity of (x.y) to all other pairs selected by the transportation plan I. Even if x is aligned with outliers or wrong clusters, as long as the points near x are mostly aligned with the correct samples, the conditional projection will project similar samples as they upweighted by the joint density in (7). This makes the mapping much less sensitive to outliers and imbalanced datasets. See Figure 1 and Figure 4 for illustrations.

---

Under review as a conference paper at ICLR 2023
(Barycentric)
h= 0.1
h=
h = 0.5
Torget
Pro Source
Figure 4: Projection under imbalanced samples. When the cluster sizes mismatch between source and target, barycentric projection wrongly projects samples to the incorrect cluster. contrast, increasing the bandwidth of conditional projection gradually improves the robustness and yields better projection.
Out-of-sample Mapping. The conditional projection is well-defined for any E X. and natu- rally generalizes to new samples without recomputing the OT. Importantly, the importance weight fr(z, (fx fx) (v)) can be interpreted as a similarity score between (I, y). which is useful for retrieval tasks as section 6.3 shows.
The conditional projection tends to cluster points together with larger bandwidths that lead to more averaging. We found that using a smaller bandwidth (e.g., = 0.1) for the conditional projection improves the diversity of the projection when the dataset is less noisy, e-g., the data in Figure 1. For noisy or imbalanced datasets, the same bandwidth used for optimizing InfoOT works well. Note that analogous to Lemma 2, when the bandwidth h - O, the conditional projection converges to the barycentric projection, making the barycentric projection a special case the conditional projection (Figure 4).
EXPERIMENTS
We now evaluate InfoOT with experiments in point cloud matching, domain adaptation, cross- domain retrieval, and single-cell aligmment. All the optimal transport approaches are implemented or adopted from the POT library (Flamary et al., 2021). Detailed experimental settings and additional experiments can be found in the appendix.
6.1 POINT CLOUD MATCHING
We begin with 2D toy example, where both source and target samples are drawn from a Gaussian distribution with 2 modes, but the latter is rotated and has two outliers added to it, as Figure shows. We compare the behavior of different variants of OT and mappings this data. Perhaps not surprisingly, standard OT maps the source points the same cluster to two different target clusters, overlooking the intrinsic structure of the data. In comparison, the alignment of InfoOT retains the cluster structure. On the right hand side, the barycentric projection maps two source points wrongly to the target outliers, while the conditional projection is not affected by the outliers. Lastly, demonstrate an out-of-sample mapping with the conditional projection, where newly sampled points are correctly mapped clusters.
Figure depicts an class-imbalanced setting, where the corresponding clusters in source and target have different numbers of samples. Therefore, the barycentric projection wrongly maps samples from the same source cluster to different target clusters. When increasing the bandwidth in the con- ditional projection, the smoothing effect of KDE gradually corrects the mapping and yields more concentrated projections. In appendix 1, we further demonstrate that InfoOT improves the base- lines color transfer task, where pixels are treated as points RGB space.
6.2 DOMAIN ADAPTATION
Next, we apply the fused version of InfoOT two domain adaptation benchmarks: MNIST-USPS and the Effice-Caltech dataset (Gong et al., 2012). The MNIST (M) and USPS (U) are digit classifi- cation datasets, and the Office-Caltech dataset contains domains: Amazon (A), Dslr (D), Webcam (W) and Caltech10 10 (C), with images labeled one of 10 classes. For MNIST and USPS, the raw images are directly used to compute the distances, while we adopt decaf6 features (Donahue et al., 2014) extracted from pretrained neural networks for Office-Caltech. Following previous works on OT for domain adaptation (Alvarez-Melh) et al., 2018; Flamary et al., 2016; Perrot et al., 2016), the source samples are first mapped to the target, and 1-NN classifiers are then trained the pro- jected samples with source labels. The barycentric projection is adopted for all the baselines, while InfoOOOT is tested with both barycentric and conditional projection.
7

---

Under review as a conference paper at ICLR 2023
Raw Data
Sinkhorn
F-InfoOT Barycentric
F-InfoOT Conditional
Figure 5: tSNE visualization of projections. We show the t-SNE visualization of projectrd source samples (circles) along target samples (triangles) on A-C. Classes are indicated by colors.
OT
Sinkhorn
GL-OT
FGW
Linear
F-InfoOT
F-InfoOT*
MNIST-USPS
M-+U
46.6:11.2 48.111.11
62.7:12.0
63.0
49.6.17.3
60.811..3
69.913.1
61.1
U-M
58.6100.9
58.8
37.81:..3
1.051
6..1
57.0
Office-Caltech
C-D
10.3
11.9
16.9+18.6
60.3
18.1
78. 13.1
87.5+7.8
C-W
64.0+7.0
66.019.3
66.7+9.4
64,0+7.0
62.0+7.4
79.7=
81.0+6.77
C-A
78.6+4.7
77.3+4.8
83.3#6.1
79.0+4.5
77.9+6.7
87.0=3.7
90.6+2.0
D-W
90.7+L3.8
90.71:4.77
93.714.33
90.7+13.8
89.0.1..3
91.011.11
93.3
D->A
73.8+:4.5
73.41:2.9
84.4:12.9
73.8+44.5
72.74:3.9
83.6114.3
8.8
D->
67.0+33.0
66.4133.8
76.5+12.9
67.04:3.0
67.5+-4.1
70.2+:3.7
1.8
W-D
81.347.8
80.6=10.4
85.6:110.6
81.37788
79.417.2
79.418.9
89,4
WHC
64.8+4..6
65.8:1..1
73.5#:..4
64.811.66
65.5::4.5
75.813.33
74.4=13.7
W A
67.314.9
69.315..4
79.613.0
67.314.9
70.514..8
85.5
89.3:12.3
A 73.1+10.6
68.84-8.8
76.3+882
73.1+10.6
66.947.8
80.6+7.5
81.3++9.8
WW 64.7+6..
70.0
70.0+7.0
64.7+66.3
69.3+6666
82.0+7.2
87.0+t4.6
C 65.4+5..3
69.3+6.0
79.8+5588
65.5++5.7
66.9+-4.5
74.4+3.4
81,2++3.6
AVG
71.02.55
72.433.7
78.914.5
71.012.5
70.512.4
80.613..3
8..6
Table Optimal Transport for Domain Adaptation. The Fused-InfoOT conditional projection (F- InfoOT") performs significantly better than the barycentric counterpart (F-InfoOT) and the other baselines when the dataset exhibit class imbalance, c.g., Office-Caltech.
Office-Caltech P@5
ImageCLEF P@5
P@
P@ 15
P@1
P@
L2-NN
13.9
62.9.114.0
13.
80.41:1055
77.6-19.5
71.7:19.3
Sinkhom++N
19.6
65.1-16.4
58.0:16.9
81.9-10.2
81.1111.6
79.2
FGW+NN
69.6
65.6116.6
58.5#7.0
81.9+10.4
81.2+10.6
79.3
F-InfoOT
7..4=9.0
75.1-19.1
70.4++10.6
81.2++9.3
81.9-19.8
80.0++10.7
Table 2: Optimal Transport for Cross- -Doman Retrieval. With conditional projection, InfoOT is capable to perform alignment for unseen samples without any modification.
Following Flamary al. (2016), present the results over 10 independent trials. In each trial of Office-Caltech, the target data is divided into 90%/10% train-test split, where OT and I-NN classi- fiers are only computed
the training set. For MNIST-USPS, only 2000 samples from the source and target training set are used, while the original test sets are used. The strength of the entropy regularizer is set for every entropic regularized OT, and the À of F-InfoOT set to 100 for all the experiments. The bandwidth for each benchmark is selected from {0.2, 0.3, ............ 0.8} with the cir- cular validation procedure (Bruzzone Marconcini, 2009; Perrot al., 2016; Zhong et al., 2010) on M-SU and A A-D which is 0.4 and 0.5, respectively. We compare I-InfoOT with Sinkhorn dis- tance (Cuturi, 2013), group-lasso regularized OT (Flamary et al., 2016), fused Cromov-Wassersee (FGW) (Vayer et al., 2019), and linear- minparg OT (Perrot et al., 2016). For OTs involving intra- domain distances such as I-InfoOT and FGW, we adopt the following class-conditional distance for the source: ||z; - æ, 5000 11(m:)) f(x,) where the second term is penalty class mismatch (Alvarez-Men) Melis Fusi, 2020; Yurochkin et al., 2019) and f is the labeling function. As Table shows, OnInfOOT with barycentric projection outperforms the baselines in both benchmarks, demon-
8

---

Under review as a conference paper at ICLR 2023
strating that mutual information captures the intrinsic structure of the datasets. In Office- Cafite-Caltech, many datasets exhibit the class-imbass caas-immalaace problem, which makes F-InfoOT with conditional projec- tion significantly outperform the barycentric projection and the other baselines. Figure 5 visualizes the projected source and target samples with tSNE (Van der Maaten & Hinton, 2008). The barycen- tric projection tends to produce one-to-one alignments, which suffer from class-inbalanced data. In contrast, conditional projection yields concentrated projections that preserves the class structure.
cap
scGEM
SNAREseq
FOS,
Acc,
FOS.
Acc..
d24T+
UnionCom
0.210
58.2
0.265
42.3
MMD-MA
0.201
58.8
0.150
94.2
d16T+
SCOT (GW)
0.190
57.6
0.150
98.2
d8
InfoOT 0.178
68.9
0.156
98.8
Taiget wampiic
Scarce curgRs
BJ
Table 3: Single-Cell Alignment Performance. Similar GW, InfoOT also performs well in cross-domain alignment.
Figure 6: scGEM alignment with InfoOT The cell types are indicated by colors.
6.3 CROSS-DOMAIN RETRIEVAL
We now consider unsupervised cross-domain image retrieval, where given a source sample, the algo- rithms have to determine the top-k similar target samples. Given fixed source and target samples, this can be formulated as an optimal transport problem, where the transportation plan I gives the simi- larity score between the candidate source sample 2; and target samples y/- Nevertheless, this formu- lation fails when new source samples come. For standard OT, one has to solve the OT problem again
to obtain the alignment for new samples. In contrast, the importance weight fr (fx (x) fy (v)) defined in conditional projection (7) naturally provides the similarity score between the candidate x and each target sample y. We test InfoOT on the Office-Caltede (Gong et al., 2012) and ImageClef datasets (Caputo et al., 2014), where we adopt the same hyperparameter for Office-Caltech from the previous section. In the unsupervised setting, the in-domain transportation cost for the source is the Euclidean distance instead of the class- conditional distance. To compare with standard OTs, we adopt& nearest neighbor approach for the baselines: (I) retrieve the nearest source sample given an unseen sample, and (2) use the transportation plan of the nearest source sample to retrieve target samples. Along with a simple nearest neighbor retrieval baseline (L.2-NN), the average top-k preci- sion over 10 trials is shown in Table 2. The fuesed InfoOT significantly outperforms the baselines on Office-Caltech across different choices of k.
6.4 SINGLE CELL ALIGNMENT
Finally, we examine InfoOT in unsupervised alignment between incomparable spaces with the single-cell multi-omics dataset from (Demetci et al., 2020). Recent techniques allow to obtain differ- ent cellular features at the single-cell resolution (Buenrostro et al., 2015; Chen al., 2019; Stocckius et al., 2017). Nevertheless, different features are typically collected from different sets of cells, and aligning them is crucial for unified data analysis. We examine InfoOT with the sc- sc-GEM (Cheow et al., 2016) and SNARE-seq (Chen et al., 2019) dataset provided by (Demetci et al., 2020) and follow the same data preprocessing steps, distance calculation, and evaluation setup. Here, two eval- uation metrics are considered: "fraction of samples closer than the true match" (FOSCTTM) (Liu al., 2019) and the label transfer accuracy (Cao al., 2020). We compare InfoOT with UnionCom (Cao et al., 2020), MMD-MA (Liu et al., 2019), and SCOT (Demetci et al., 2020), where SCOT is an optimal transport baseline with Prrmov-Wassersee
distance. Similarly, the bandwidth for each dataset is selected from (0.2, 0.3. .... 0.8} with the circular validation procedure. As Table 3 shows, InfoOT significantly improves the baselines on the sc- sc-GEM dataset, while being comparable on the SNARE-seq dataset, demonstrating the applicability of InfoOT cross-domain alignment. Figure further visualizes the barycentric projection with InfoOT, where we can see that cells with the same type are well aligned.
7 CONCLUSION
In this work, we propose InfoOT, information-thherrtii extension of optimal transport. InfoOT produces smoother, coherent alignments by maximizing the mutual information estimated with KDE. InfoOT leads to new mapping method, conditional projection, that is robust to class im- balance and generalizes to unseen samples. We extensively demonstrate the applicability of InfoOT across benchmarks in different modalities.

---

Under review as a conference paper at ICLR 2023
REFERENCES
David Alvarez-Melis and Nicolo Fusi. Geometric dataset distances via optimal transport. Advances in Neural Information Processing Systems, 33:21428 218829,4,, 2020.
David Alvarez-Melis and Tommi Jaakkola. Gromov-wasserstein alignment of word embedding spaces. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1881-1890, 2018.
David Alvarez-Melis, Tommi Jaakkola, and Stefanic Jegelka. Structured optimal transport. In International Conference on Artificial Intelligence and Statistics, pp. 1771-1780. PMLR, 2018.
David Alvarez-Melis, Stefanie Jegelka, and Tommi S Jaakkola. Towards optimal transport with global invariances. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1870-1879. PMLR, 2019.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Yikun Bai, Xiugang Wu, and Ayfer Özgür. Information constrained optimal transport: From tala- grand, to marton, to cover. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2210-2215. IEBE, 2020.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International conference on machine learning, pp. 531-540. PMLR, 2018.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Com- puting, A111):AI111AA1 2015.
Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia con- ference, pp. 1-12, 2011.
Olivier Bousquet, Sylvain Gelly, Ilya Tolstikhin, Carl-Johann Simon-Gabriel, and Bernhard Schoelkopf. From optimal transport to generative modeling: the vegan cookbook. arXiv preprint arXiv:1705.07642. 2017.
Lorenzo Bruzzone and Mattia Marconeini. Domain adaptation problems: A dasvm classification technique and a circular validation strategy. IEEE transactions on pattern analysis and machine intelligence, 32(5) 2009.
Jason D Bucnrostro, Beijing Wu, Howard Y Chang, and William Greenleaf. Atac-seq: a method for assaying chromatin accessibility genome-wide. Current protocols in molecular biology, 109 (1):21-29, 2015.
Guillermo Canas and Lorenzo Rosasco. Learning probability measures with respect to optimal transport metrics. Advances in Neural Information Processing Systems, 25, 2012.
Kai Cao, Xiangqi Bai, Yiguang Hong, and Lin Wan. Unsupervised topological alignment for single- cell multi-omics integration. Bioinformatics. 36(Supplement 1):i48-i56. 2020.
Barbara Caputo, Henning Müller, Jesus Martinez-Gomeez, Mauricio Villegas, Burak Acar, Novi Patricia, Neda Marvasti, Suzan Üsküdarlı, Roberto Paredes, Miguel Cazorla, et al. Imageclef 2014: Overview and analysis of the results. In International Conference of the Cross-Language Evaluation Forum for European Languages, pp. 192-211. Springer, 2014.
Song Chen, Blue B Lake, and Kun Zhang. High-thie throughput sequencing of the transcriptome and chromatin accessibility in the same cell. Nature biotechnology. 37512):1452-145, 2019.
10

---

Under review as a conference paper at ICLR 2023
Lih Feng Cheow, Elise T Courtois, Yuliana Tan, Ramya Viswanathan, Qiaorui Xing, Rui Zhen Tan, Daniel SW Tan, Paul Robson, Yuin-Har han Loh, Stephen R Quake, et al. Single-cell multimodal profiling reveals cellular epigenetic heterogeneity. Nature methods, ((100)833-836 2016.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Xavier Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314):2533-2669, 2018.
Ching-Yas Yao Chuang, Youssef' Mrouch, Kristjan Greenewald, Antonio Torralba, and Stefanie Jegelka. Measuring generalization with optimal transport. Advances in Neural Information Processing Systems, 34:8294 8306, 2021.
Ching- Bao Chuang, R Devon Hjelm, Xin Wang. Vibhav Vineet, Neel Joshi, Antonio Torralba, Ste- fanie Jegelka, and Yale Song. Robust contrastive learning against noisy views. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16670-16681, 2022.
Alexis Conneau, Guillaume Lample, Mare' Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. Word translation without parallel data. arXiv preprint arXiv:1710.04088, 2017
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution op- timal transportation for domain adaptation. Advances in Neural Information Processing Systems, 30, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Pinar Demetci, Rehecca Santorella, Björ Sandstede, William Stafford Noble, and Ritambhara Singh. Gromov-wasserstein optimal transport align single-cell multi-omics data. BioRxiv, 2020.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In Inter- national conference machine learning, pp. 647-655. PMLR, 2014.
Sira Ferradans, Nicolas Papadakis, Gabriel Peyré, and Jean-François Aujol. Regularized discrete optimal transport. SIAM Journal on Imaging Sciences, 783):155311882, 2014.
Flamary, N Courty, Tuia, and A Rakotomamonjy. Optimal transport for domain adaptation.
IEEE Trans. Pattern Anal. Mach. Intell, 2016.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanis- las Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): .5mmmm1111....mm.m.m.
1-8, 2021. httptpp:/
jml r. org
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learn- ing with a wasserstein loss. Advances in neural information processing systems, 28, 2015.
Tomer Galanti, Sagie Benaim, and Lior Wolf. Risk bounds for unsupervised cross-domain mapping with ipms. J. Mach. Learn. Res., 22:90-1, 2021.
Muhammad Ghifary, David Balduzzi, W Bastiaan Kleijn, and Mengjie Zhang. Scatter component analysis: A unified framework for domain adaptation and domain generalization. IEEE transac- tions on pattern analysis and machine intelligence, 39(7):1414-1430 2016.
Boqing Gong, Yuan Shi, Fei Sha, and Kristen Grauman. Geodesic flow kemel for unsupervised domain adaptation. In 2012 IEEE conference on computer vision and pattern recognition, pp. 2066-2073. IEEE, 2012.
Tzu Ming Harry Hsu, Wei Yu Chen, Cheng-An An Hou, Yao-Hung Hubert Tsai, Yi-Ren Yeh, and Yu- Chiang Frank Wang. Unsupervised domain adaptation with imbalanced cross-domain data. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4121-4129 2015.
11

---

Under review as a conference paper at ICLR 2023
Gabriel Khan and Jun Zhang. When optimal transport meets information geometry. Information Geometry, pp. 1-32, 2022.
Philip A Knight. The sinkhorn knopp algorithm: convergence and applications. SIAM Journal on Matrix Analysis and Applications, (0M()):211222))) 2008.
Didong Li, Yulong Lu, Emmanuel Chevallier, and David B Dunson. Density estimation and model- ing on symmetric spaces. arXiv preprint arXiv:2009.01983, 2020.
Jie Liu, Yuanhao Huang, Ritambhara Singh, Jean-Philippe Vert, and William Stafford Noble. Jointly embedding multiple single-cell omies measurements. Algorithms bioinformatics.... Inter- national Workshop, WABI..,, proceedings. WABI (Workshop), volume 143. NIH Public Access, 2019.
Yanbin Liu, Makoto Yamada, Yao-Hung Hubert Tsai, Tam Le, Ruslan Salakhutdinov, and Yi Yang. Lsmi-sinkhorn: Semi-supervised mutual information estimation with optimal transport. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 655- 670. Springer, 2021.
Mingsheng Long, Jianmin Wang, Guiguang Ding, Jiaguang Sun, and Philip S Yu. Transfer feature learning with joint distribution adaptation. In Proceedings of the IEEE international conference on computer vision, pp. 2200-2207, 2013.
Mingsheng Long, Jianmin Wang, Guiguang Ding, Jiaguang Sun, and Philip Yu. Transfer joint matching for unsupervised domain adaptation. In Proceedings of the IEEE conference com- puter vision and pattern recognition, pp. 1410-1417, 2014a.
Mingsheng Long, Jianmin Wang, Jiaguang Sun, and S Yu Philip. Domain invariant transfer kernel learning. IEEE Transactions on Knowledge and Data Engineering, 2766):111-11522 2014b.
Facundo Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Foun- dations of computational mathematics, 114):417-487, 2011.
Petr Mokrov, Alexander Korotin, Lingxiao Li, Aude Genevay, Justin M Solomon, and Evgeny Bur- naev, Large-scale wasserstein gradient flows. Advances in Neural Information Processing Sys- tems, 34:15243-15256 2021.
Young-Il Il Moon, Balaji Rajagopalan, and Upmanu Lall. Estimation of mutual information using kernel density estimators. Physical Review E, 52(3):3318, 1995.
Debarghya Mukherjee, Aritra Guha, Justin M Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlier-robust optimal transport. In International Conference on Machine Learning, pp. 7850- 7860. PMLR, 2021.
Khai Nguyen, Dang Nguyen, Tung Pham, Nhat Ho, et al. Improving mini-batch optimal transport via partial transportation. In International Conference on Machine Leurning, pp. 16656-16690. PMLR, 2022.
Sherjil Ozair, Corey Lynch, Yoshua Bengio, Aaron Van den Oord, Sergey Levine, and Pierre Ser- manet. Wasserstein dependency measure for representation learning. Advances in Neural Infor- mation Processing Systems, 32, 2019.
Emanuel Parzen. On estimation of probability density function and mode. The annals of mathe- matical statistics, 165-)16 1962.
Bruno Pelletier. Kernel density estimation on riemannian manifolds. Statistics & probability letters, 73(3):97-304, 2005.
Michaël Perrot, Nicolas Courty, Rémi Flamary, and Amaury Habrard. Mapping estimation for discrete optimal transport. Advances in Neural Information Processing Systems, 29, 2016.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. wasserewa averaging of kernel and distance matrices. International Conference on Machine Learning, pp. 2664-267 2672. PMLR, 2016.
12

---

Under review as a conference paper at ICLR 2023
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds mutual information. In International Conference on Machine Learning, pp. 5171- 5180. PMLR. 2019.
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 Intelli- gence and Statistics, pp. 849- 858. PMLR, 2019.
Murray Rosenblatt. Remarks
nonparametric estimates of density function. The annals of mathematical statistics, pp. 832-82 827, 1956.
Salem Said, Lionel Bombrun, Yannick Berthoumicu, and Jonathan H Manton. Riemannian gaus- sian distributions the space of symmetric positive definite matrices. IEEE Transactions Information Theory, 6354)2213,,2170, 2017.
Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. arXiv preprint
arXiv: 2017.
Justin Solomon, Gabriel Peyré, Vladimir G Kim, and Suvrit Sra. Entropic metric alignment for correspondence problems. ACM Transactions on Graphics (ToG), 35(4):1-13, 2016.
Marlon Stoeckius, Christoph Hafemeister, William Stephenson, Brian Houck-Loomis, Pratip K Chattopadhyay, Harold Swerdlow, Rahul Satija, and Peter Smibert. Simultaneous epitope and transcriptome measurement in single cells. Nature methods, 14(9):665-868, 2017.
Baochen Sun, Jiashi Feng, and Kate Saenko. Return of frustratingly easy domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Shuhan Tan, Xingchao Peng, and Kate Saenko. Class-imbalanced domain adaptation: An empirical odyssey. In European Conference on Computer Vision, pp. 585-602. Springer, 2020.
Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint arXiv: 2014.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(1)), 2008.
Titouan Vayer, Laetita Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Fused gromov-wasserstein distance for structured objects: theoretical foundations and mathematical properties. arXiv preprint arXiv: 1,02834, 2018a.
Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Optimal transport for structured data with application on graphs. arXiv preprint arXiv: 08005.09144 14,114477 2018b.
Titouan Vayer, Lactitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Optimal transport for structured data with application graphs. In ICML 2019-36th International Con- ference on Machine Learning, pp. 1-16, 2019.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Jindong Wang, Wenjie Feng, Yiqiang Chen, Han Yu, Meiyu Huang, and Philip Yu. Visual domain adaptation with manifold embedded distribution alignment. In Proceedings of the 26th ACM international conference on Multimedia, pp. 402-410, 2018.
Renjun Xu, Pelen Liu, Liyan Wang, Chao Chen, and Jindong Wang. Reliable weighted optimal transport for unsupervised domain adaptation. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 4394 4403, 2020.
Mikhail Yurochkin, Amanda Bower, and Yuckai Sun. Training individually fair ml models with sensitive subspace robustness. arXiv preprint arXiv: /907, 00020, 2019.
Erheng Zhong, Wei Fan, Qiang Yang, Olivier Verscheure, and Jiangtao Ren. Cross validation frame- work to choose amongst models and datasets for transfer learning. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 547-562. Springer, 2010.
13

---

Under review as a conference paper at ICLR 2023
A PROOFS
A.1 PROOF OF LEMMA 2
Proof. In the limit when h O, the Gaussian kernel converges to
1
ift = 0
K₂. (1)
0
otherwise.
Therefore, the kernel K2 (dx xx)) will only have non-zero value when 2; = z),, which implies that the kernelized mutual information will converge as follows:
n² Ek., Tu (1x, xk)) Kr.
lim (x)
lim
Σ
Ts log
h-+0
Es (dx(xs))x)) E, Kb. (dy()) u1)
n² .Tij/Zh
Σ W
ii log
1/2
Σ
Ti log iij + 2 log(n)
4
(T) 2 log(n))
A.2 PROJECTED GRADIENT DESCENT
The classic mirror descent iteration is written as:
1++1 f- arg min (T(V/(m)), x) + D(
When (yyl( is the KL divergence: (KL E. yi log nn the update has the following form:
(I++1); = dog(ts) (z.),e-
In our case, before the projection, the update reads
1'41 OT. 71-A,,,,--,,,,,,,,00-----
Next, we solve the following projection w.r.t KL metric:
P++1 = arg min (T] rell(p.a)
As Benamou et al. (2015) shows, the KL projection is equivalent to solving the entropic regularized optimal transport problem, which is usually refer to the sinkhorn distance (Cuturi, 2013). Following (Peyré et al., 2016), we set the stepsize 1/c to simplify the iterations and reach the following update rule:
T++1 + arg min (V. -H(()..
rell(p.g)
B ADDITIONAL EXPERIMENTS
B. COLOR TRANSFER
Color transfer aims to transfer the colors of the target images into the source image. Optimal trans- port achieves this by treating pixels as points in the RGB space, and maps the source pixels to the target ones. Here, 500 pixels are sampled from each image compute the OT, then the barycentric projection is applied to map all the source pixels to target. We compare fused InfoOT with standard OT, Sinkhom distance (Cuturi, 2013), and linear mapping estimation (Perrot et al., 2016) and show the results in Figure We can see that InfoOT produces a sharper results than the baselines while decently recovering the colors in the target image.
14

---

Under review as a conference paper at ICLR 2023
Source
Target
OT
Sinkhom
Lincar
F-InfoOT
Figure 7: Color Transfer via Optimal Transport. Fused InfoOT produces sharper results while preserving the target color compared to the baselines.
EN-ES
EN-FR
EN-DE
EN-IT
EN-RU
Supervision
PROCRUSTES
5K Words
81.2
82.3
81.2
82.2
73.6
71.9
76.3
75.5
51.7
63.7
Ady-NN
None
81.7
83.3
82.3
82.1
74.0
72.2
77.4
76.1
52.4
61.4
InvOT
None
81.3
81.8
82.9
81.6
73.8
71.1
77.7
77.7
41.7
55.4
InfoOT (h=0.55)
None
81.6
78.5
82.4
80.5
75.4
74.2
78.6
75.7
48.1
52.9
GW
None
84.3
83.2
84.8
83.6
77.4
75.2
82.5
79.8
52.0
61.4
Table 4: Cross-lingual Word Alignment. The InfoOT achieves comparable performance GW, demonstrat- ing its potential recovering cross-lingual correspondence.
B.2 WORD EMREDDING ALIGNMENT
Here, we explore the possibility of applying InfoOT for unsupervised word embedding alignment. We follow the setup in (Alvarez-Melis Jaakkola, 2018), where the goal is recover cross-lingual correspondences with word embedding in different languages. In this case, the pairwise distance between domains might not be meaningful, the word embedding models are trained separately. Previous works suggest that cross-lingual word vector spaces are approximately isometric, which makes Moooov-Wasserstein an ideal choice due to its ability to align isometric spaces. Here, we treat GW the oracle, and show that InfoOT Jaakkola, 2018) and other baselines such as InvOT (Alvarez-Melle et al., 2019). Adv-NN (Conneau al., 2017), and supervised PROCRUSTES. We report the results the dataset of Conneau et al. (2017) Table 4, where both GW and InfoOT are trained with 12000 words and refined with Cross-Domain Similarity Scaling (CSLS) (Conneau al., 2017). The entropy regularizer 0.0001 and 0.02 for GW and InfoOT, respectively. We can see that InfoOT performs comparably with the baselines and GW, demonstrating its applicability in recovering cross-lingual correspondence.
perform comparably
GW (Alvarez-Melis &
B.3 DIFFERENT HYPERPARAMETER FOR INFOOT
F-InfoOT
UOT
Here, we report the performance of InfoOT with different weights for entropic regularizer and mutual information on do- main adaptation. As Table 6 shows. Fused-InfoOT performs consistently well across different hyperparameter selections.
CDD
87.5
81,9+1119
C-W
81.0++6.7
77.3+66.4
C-A
90.6+2.0
87.8++3.5
D W
93.3114.7
93.3.15.7
D
89.8.1..9
87.8113.2
B.4 ADDITIONAL BASELINE: UNBALANCE OT
DCCC
80.8
78.8.12.7
WD
89.4-11.8
98.8.12.6
In this section, additional include the results of unbalanced OT (UOT) Chizat et al. (2018); Frogner et al. (2015), which solves the following constrain optimization problem with gen- eralized Sinkhorn- Knopp matrix scaling algorithm:
W-+C
74.4+3.7
76.7+t4.3
W-+A
89.3+2233
80.1+3..3
A-D
81.319.8
76,3+882
A-W
87.0-1..6
69.3-48.6
A-
81.2-13.6
77.4+-3.7
min (T.C) 6m DKL (1,p)) cm (T" 1, cT( rell(p.q)
AVG
85.6+5.66
82.1+88.3
We show the best results of UOT in Table 5 by selecting and en within 51 10) and (0.5, 1, 10). We can see that InfoOT still outperform UOT by non-trivial margin.
Table 5: Unbalanced OT.
15

---

Under review as a conference paper at ICLR 2023
(),e)
(100, 1)
(100, 10)
(100, 20)
(10,
(200, 1)
C-+D
87.5.1.88
86.318.7
83.018.9
87.517.8
86.918.0
C-+
81.0=6.7
86.7+7.7
88.0#5.9
80.0=6.1
81.7=7.2
C-A
90.6#2.0
90.5+2.1
90.7+2211
89,42244
90.6=2.0
D-W
93.3=t477
92.7+6.0
91.3+
93.3=5.7
94.0=t.44
D
89.8+1.9
89.9422.1
89.61119
89.6
89.
D-FC
8..8
81.2++19
81.5+11.6
80.7
8..6+
W-
89.4+11.8
86.94-10.4
83.8+11.5
91.9=11.2
90.0+111.9
W-C
74.4+3.77
74.2+33.7
74.0+13.4
74.2+-4.6
74.4-1388
W-A
89.3=2233
89.3+2.0
89.312.0
86.412.8
89.3=22.3
A-D
81.3-9.8
80.619.5
82.5+11.7
81.91104
82.5=9.2
A-W
87.0-1..6
83.316.3
83.016.0
83.816.5
87.0=1..6
A-C 81.2+3.6
80.8+4.0
80.2+:399
81.2+3.3
82.2+2.7
AVG
85.6.1..6
85.21553
84.915.1
8..0.1.66
85.7
Table InfoOT with different hyperparameters. test Fused-InfoOT with conditional projection by varying the regularizer weights (A, c). Note that Table the main paper shows the results of (A = 100, = 1).
1-NN
5-NN
10-NN
20-NN
Linear
OT
71.018.8
77.0=6.4
78.314.8
77.
77,8
Sinkhorn
72.4.7.33
76.0-5.3
76.311..0
75.2.16.3
76.7119.8
GL-OT
78.917..
80.7-5.3
80.5.4..3
78.2.7..1
78.119.77
FGW
71.0=t..8
76.9=6.5
78.3+44.8
77.5=6.8
77.5+7.9
Linear
70.5+8.4
75.9=6.2
77.445.4
77.5=7.1
76,7+7.55
InfoOOT
80.6+:.77
814=5.8
79.7#5..0
76.4=7.1
82.9-7.0
F-InfoOT
85.5115.66
5.5
85.4..5.55
81.7-17.2
81.4.15.3
Table 7: Results beyond 1-NN. We evaluate the performance with K-NN classifiers and linear classifiers.
GFK
CORAL
SCA
JDA
TJM
DDC
DAN
MEDA
F-InfoOT
C++D
86.6
84.7
87.9
89.8
84.7
88.8
89.3
91.1
87.9
C-W
77.6
80.0
85.4
85.1
81.4
85.4
90.6
95.6
85,8
C-A
88.2
92.0
89.5
89.6
88.8
91.9
92.0
93.4
91.1
D WW
99.3
99.3
98.6
99.7
99.3
98.2
98.5
97.6
97.3
D-
90.0
91.7
90.3
89.5
90.0
93.2
91.3
D-*C
71.4
76.8
78.1
85.5
83.8
81.1
80.3
87.5
82.9
W-D
100
100
100
100
100
100
100
99.4
96.2
WC
69.8
75.5
74.8
84.8
83.0
78.0
81.2
93.2
80.3
W
86.1
90.3
84.9
92.1
99.4
90.0
AD 82.2
84.1
85.4
80.3
76.4
89.0
91.7
88.1
81.5
A-W
70.9
74.6
75.9
78.3
71.9
86.1
91.8
88.1
85.4
C
79.2
83.2
78.8
83.6
84.3
85.0
84.1
87.4
82.5
AVG
81.5
84.7
85.9
88.2
86.0
88.2
90.1
92.8
87.7
Table 8: Baselines beyond OT.
B.5 EXPERIMENTS BEYOND I-NN CLASSIFIER
We report the performances InfoOT and baselines with general k-NN classifiers and linear SVM classifiers in Table 7. We can see that fused-InfoOT consistently outperforms the baselines beyond I-NN classifiers on Office-Caltech domain adaptation benchmark. addition, compared to baselines, the performance of InfoOT is more robust to the choice of the number of neighbors k.
B.6 BASELINES BEYOND OPTIMAL TRANSPORT
We compare InfoOT with the following non-OT baselines: Geodesic Flow Kernel (GFK) (Gong et al., 2012). CORrelation Alignment (CORAL) (Sun et al., 2016), Scatter Component Analysis (SCA) (Ghifary et al., 2016), Joint distribution alignment (JDA) (Long al., 2013). Transfer Joint
16

---

Under review as a conference paper at ICLR 2023
Matching (TJM) (Long et al., 2014a), Deep Domain Confusion (DDC) (Tzeng al., 2014), Deep Adaptation Network (DAN) (Long et al., 2014b), and Manifold Embedded Distribution Alignment (MEDA) (Wang et al., 2018). For fair comparison, calculated with full source and target dataset instead of the 10-fold setting in the main context. As Table 8 shows, InfoOT performs comparably many baselines without training finetuning neural networks.
report the performance of Fused-InfoOf
C LIMITATIONS
While we have illustrated successful applications of InfoOT, there are limitations. One could expect InfoOT to perform worse when the geometry of input spaces provides little information. In partic- ular, for raw inputs such as image datasets, InfoOT would not perform well without pre-extracted features. is also non-trivial directly apply InfoOT to very large-scale problems with millions of data points. Computational-effica 2022) should be considered to apply InfoOT large-scale datasets.
extensions such as mini-batch optimal transport (Nguyen et al.,
17


Reviews:
[{"review_id": "VH1Y_faYSas", "reviewer": "Reviewer_pBFH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed to improve the quality of optimal transport via simultaneously encouraging the mutual information (MI). This is justified by establishing the equivalence between the MI and the standard entropy regularization used in the Sinkhorn algorithm. Empirical results showed that when implemented with kernel density estimation, the proposed InfoOT better captures the cluster structure in data and works better on serval domain transfer tasks. An alternative view on the smoothness regularization is also given.  The author(s) further presented a conditional projection scheme for the OT mapping. ", "summary_of_the_review": "This paper is well-written. My major reservation is due to the lack of technical novelty and practical significance. KDE is a well-establish technique and it does not scale well, also for the problems considered in the experiments there should be better alternative solutions without applying OT (especially for the domain adaptation). I am open to reconsider my decision should more convincing argument or empirical results surface during the rebuttal phase. ", "strength_and_weaknesses": "\n### Strength\n* Calling out the equivalence between entropy regularization and the proposed MI optimization makes an interesting point. \n* The smoothness argument to preserve cluster structure makes good sense. \n* Reported empirical gains on domain adaption and cross-domain retrieval are very encouraging\n\n### Weakness\n* As a criticism applies all kernel methods, the main concern is scalability of the method. First, the computation scales quadratically, and to ensure good performance, heavy parameter tuning is typically needed. Integration and end-to-end optimization with need neural nets (which is known to perform strongly even without the kernel trick), is often impractical with kernel-based components. \n* There are existing work on the neural estimation of the transport plan and non-parametric estimation of MI (e.g., InfoNCE, NWJ, etc.). While integrating these two directions as a generalized version of the proposed solution seems to be out-of-scope, I would love to see some technical discussions at least. \n* While I appreciate the the cluster-preserving idea, this is merely a flaky heuristic assumption and may not hold universally. Also some ablation study using alternative, more direct penalties to enforce smooth transport should be considered (e.g., the distance between nearby source points in the transported target space). \n* For the domain adaption experiment, while I understand the author(s) followed the experiment setup from prior works, but 1-NN classification is usually considered unreliable. Numbers with alternative classification schemes should be reported (e.g., 5-NN, linear, simple neural net, etc.)\n* There is no discussion on the limitations of the proposed method\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OxqVDmZ5iv", "reviewer": "Reviewer_BdbM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose InfoOT which maximizes the mutual information between domains and minimize distances between input distributions. The proposed InfoOT address several drawbacks of OT, e.g., coherence structure (clustering, outliers) and easy to integrate new data points. Empirically, the authors evaluate the proposed method on domain adaption, cross-domain retrieval and single-cell alignment.", "summary_of_the_review": "The proposed method is interesting. The proposed methods address several drawbacks of OT.", "strength_and_weaknesses": "Strength\n+ The proposed InfoOT address several drawbacks of OT \n+ The proposed method works well in applications.\n\nWeaknesses\n+ The advantage of the proposed method (using kernel density estimation for continuous setting) is not clear enough over discrete ones (e.g., entropic regularization in Sinkhorn), especially in the case input distributions are discrete (empirical distributions). It will be a plus if the authors elaborate this points with more details.\n+ It is unclear how many samples are required for the kernel density estimation used in InfoOT", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6ePjWHeK987", "reviewer": "Reviewer_EHDZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a dynamic cost function for OT (see below on whether this is a valid OT objective or not) that attempts to maximize the mutual information of the projections using kernel density estimates---which depend on the coupling distribution.\nThis can be seen as a generalization of entropic regularization.\nThe InfoOT formulation can be merged with the standard OT problem and can then be solved via a sequence of entropic OT problems.\nEmpirically, this is shown to preserve cluster structure in 2D examples and qualitative t-SNE projections.\nFurthermore, the paper proposes a mapping method based on the kernel density estimates called conditional projection that is more robust to projecting outliers.\n", "summary_of_the_review": "Overall, I found the paper to address two interesting empirical problems related to using OT in ML: Preserving cluster structure and outliers. The technical descriptions were a bit vague but the overall idea of adding a mutual information regularizer seems interesting. However, I do have some concerns about the use of KDEs because they can break down in high dimensions, the experimental setup, and some technical points. I hope that at least some of these can be addressed by the author response.\n", "strength_and_weaknesses": "*Strengths*\n- The proposed training method can maintain cluster structure when learning a mapping.\n\n- The proposed mapping method can be more robust to outliers than barycentric proojection.\n\n- The algorithm simplifies to a sequence of entropic OT problems.\n\n- The results show improved performance compared to standard OT baselines across several tasks.\n\n*Weaknesses*\n- Kernel densities are known to breakdown in higher dimensions and suffer from the curse of dimensionality. This presents a key limitation and problem with the proposed approach. Why would this not be a problem here?  While there are experiments on MNIST for domain adaptation, it is unclear what is actually going on. \n\n- The baselines for all external tasks seem to be OT-based. What about non-OT methods for these tasks?  For example, what about GAN-based methods for domain adaptation (e.g., [Ganin et al. 2016]) or Wasserstein dual formulations for learning OT maps via convex functions (e.g., [Makkuva et al., 2020])? There are also flow-based methods for alignment that could be used for domain adaptation [Grover et al. 2020, Usman et al., 2020]. I am unfamiliar with the sota methods for retrieval but it seems there would also be methods here. While I understand that you are comparing to other OT-based methods, the key motivation for this estimator seems to be for empirical reasons.  It is unclear that there is theoretic or \"intrinsic\" motivation for the proposed OT formulation. Thus, to demonstrate it's usefulness more broadly, it would be helpful to compare to sota methods for these tasks and/or do more intrinsic evaluation.\n\n- Definition 1 seems odd or incorrect. It seems that Definition 1 is using two approximations that should be distinguished and explained. First, you approximate the joint distribution over x,y using a kernel density estimate.  If you were to use a plug-in estimator, this would still require an expectation using the kernel density for the expectation.  However, then you replace this expectation over the kernel density, with a psuedo-sample approximation that treats each possible pair of inputs (x,y) as a weighted empirical sample from this kernel density. Thus, the expectation turns into a weighted average with $\\Gamma$ defininig the weights of each pairing.  I believe this is how you simplify to only using $\\Gamma$ as the weights for the outer summation in Definition 1. Again, these two approximations should be discussed and distinguished as it was not clear from the original exposition.\n\n- Using 1-NN in the source domain as the target predictor for domain adaptation and using KNN in the retrieval experiment are unlikely to do well in high dimensions and may be biased towards KDE-based non-parametric approaches. A standard CNN or fully-connected network could be used in evaluating domain adaptation. In particular, a KNN classifier may be unfairly biased towards KDE-like approaches as they are both non-parametric methods based on geometric distances.\n\n- I'm not sure it is reasonable to have $\\Gamma$ in the \"cost\" function of OT at least theoretically. It's unclear if it's actually OT anymore if $\\Gamma$ is in the cost function itself.  Could  you explain why this is still OT if the cost function is now a function of the map itself? \n\nGanin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., ... & Lempitsky, V. (2016). Domain-adversarial training of neural networks. The journal of machine learning research, 17(1), 2096-2030.\n\nMakkuva, A., Taghvaei, A., Oh, S., & Lee, J. (2020, November). Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning (pp. 6672-6681). PMLR.\n\nGrover, A., Chute, C., Shu, R., Cao, Z., & Ermon, S. (2020, April). Alignflow: Cycle consistent learning from multiple domains via normalizing flows. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 34, No. 04, pp. 4028-4035).\n\nUsman, B., Sud, A., Dufour, N., & Saenko, K. (2020). Log-likelihood ratio minimizing flows: Towards robust and quantifiable neural distribution alignment. Advances in Neural Information Processing Systems, 33, 21118-21129.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject