Slicing Unbalanced Optimal Transport
Authors: Clément Bonet
Kimia Nadjahi
Thibault Sejourne
Kilian FATRAS
Nicolas Courty
Venue: Accepted by TMLR ()

Abstract: Optimal transport (OT) is a powerful framework to compare probability measures, a fundamental task in many statistical and machine learning problems. Substantial advances have been made in designing OT variants which are either computationally and statistically more efficient or robust. Among them, sliced OT distances have been extensively used to mitigate optimal transport's cubic algorithmic complexity and curse of dimensionality. In parallel, unbalanced OT was designed to allow comparisons of more general positive measures, while being more robust to outliers. In this paper, we bridge the gap between those two concepts and develop a general framework for efficiently comparing positive measures. We notably formulate two different versions of sliced unbalanced OT, and study the associated topology and statistical properties. We then develop a GPU-friendly Frank-Wolfe like algorithm to compute the corresponding loss functions, and show that the resulting methodology is modular as it encompasses and extends prior related work.  We finally conduct an empirical analysis of our loss functions and methodology on both synthetic and real datasets, to illustrate their computational efficiency, relevance and applicability to real-world scenarios including geophysical data.

Published in Transactions on Machine Learning Research (12/2024)
Slicing Unbalanced Optimal Transport
Clément Bonet"
Clement.bonet@eeeee..ee
CREST, ENSAE, IP Paris, Palaiseau, France
Kimia Nadjahi"
kimia.nadjahi@ena.
CNRS, ENS, Paris, France
Thibault Séjourné'
LTS4, EPFL, Lausanne, Switzerland
Kilian Fatras
Sltia..fatras@mmill.. euebee
Mila, McGill University, Montreal, Canada
Nicolas Courty
nicolas, nicoolas www.sssccrtttyyiiiicoo.
IRISA, Université Bretagne-Sud, Vannes, France
Reviewed on OpenReview: https: openreview. net/ forum? id= AJJTSMo58
Abstract
Optimal transport (OT) is powerful framework to compare probability measures, funda- mental task in many statistical and machine learning problems. Substantial advances have been made in designing OT variants which are either computationally and statistically more efficient or robust. Among them, sliced OT distances have been extensively used to mitigate optimal transport's 's cubic algorithmic complexily and curse dimensionality. In parallel, unbalanced OT was designed to allow comparisons more general positive measures, while being more robust to outlicrs. In this paper, we bridge the gap between those two concepts and develop general framework for efficiently comparing positive measures. We notably formulate two different versions of sliced unbalanced OT, and study the associated topol- ogy and statistical properties. We then develop GPU-friendly Frank- Wolfe like algorithm to compute the corresponding loss functions, and show that the resulting methodology is modular as encompasses and extends prior related work. We finally conduct an empiri- cal analysis of our loss functions and methodology on both synthetic and real datasets, to illustrate their computational efficiency, relevance and applicability to real-world scenarios including geophysical data.
1 Introduction
Many machine learning tasks involve aligning objects such as images, graphs, datasets their representations after transformations. This is particularly relevant in transfer learning tasks like domain adaptation (Fatras et al., 2021) or multimodal machine learning (Baltrušaitis et al., 2018). These objects can be conveniently represented as positive measures, i.e., a set of samples associated with non-negative weights. Aligning then consists in minimizing a distance or discrepancy between two measures. It is crucial to choose a meaningful discrepancy that has desirable statistical, robustness and computational properties. In particular, settings require comparing arbitrary positive measures, i.e., measures whose total mass have arbitrary value, opposed to probability distributions whose total mass is equal to 1. In cell biology, for instance, measures are used to represent and compare gene expressions of cell populations, and the total mass corresponds to the population size (Schiebinger et al., 2019).
Equal contribution

---

Published in Transactions on Machine Learning Research (12/2024)
(Unbalanced) Optimal Transport. Optimal transport (OT) has been frequently chosen as a loss function to align objects. OT defines a distance between two positive measures and / of the same mass (m(a) = m(3) by moving the mass of a toward the mass of / with the least possible effort. However, in some applications, the mass equality constraint is not satisfied, i.e., m(a) * m(3). It can still be enforced by a re-normalization of the mass, which is potentially spurious and makes the problem less interpretable. This sctting has motivated the development of a new OT framework, called unbalanced OT (UOT); that can naturally compare measures of different masses by softly relaxing the mass conservation constraints (Kondratyev et al., 2016; Liero et al., 2018; Chizat et al., 2018b). An appealing outcome of this new OT variant is its robustness to outliers which is achieved by discarding them before transporting a to B. UOT has been useful for many theoretical and practical applications, e.g., theory of deep learning (Chizat & Bach, 2018; Rotskoff et. al., 2019), biology (Schiebinger et al., 2019; Demetci et al., 2022) and domain adaptation (Fatras et al., 2021). We refer to (Séjourné et al., 2022a) for an extensive survey of UOT. Computing UOT roquires to solve linear program whose complexity (Pele& & Werman, 2009; Peyré et al., 2019). Besides, accurately estimating UOT distances through empirical distributions is challenging as they suffer from the curse of dimension (Dudley, 1969). A common workaround is to rely on variants with lower complexities and better statistical properties. Among the most popular, we can list entropic OT (Cuturi, 2013; Pham et al., 2020) or minibatch OT (Fatras et al., 2020; 2021). In this paper, we focus on developing sliced UOT approaches.
cubical in the number n of samples (O(n logn))
Sliced Optimal Transport. Sliced OT (SOT) defines an alternative metric by leveraging the closed-form solution of OT between univariate measures (Rabin et al., 2012; Bonneel et al., 2015). It averages the OT cost between projections of (a, (9) on 1D subspaces of IRd. For 1D data, the OT solution can be computed through sort algorithm, leading to an appealing O(n log(n)) complexity (Peyré et al., 2019). Furthermore, it has been shown to lift useful topological and statistical properties of OT from I-dimensional to multi-dinennsioall settings (Nadjahi et al., 2020b; Bayraktar & Guo, 2021; Goldfeld & Greenewald, 2021). It therefore helps to mitigate the curse of dimensionality making SOT-based algorithms theoretically grounded, statistically efficient, and practical to solve even on large-scale settings. These appealing properties motivated the development of several variants and generalizations, e-g-: by considering different. types or distributions of projections (Kolouri et al., 2019; Deshpande et al., 2019; Nguyen et al., 2020; Ohana et al., 2023; Nguyen et al., 2023) or manifold data (Bonet et al., 2023a;b;c). Fast computations of partial OT (a particular case of UOT) between univariale measures (Bonneel & Coeurjolly, 2019; Bai et al., 2023) or more generally on trees (Sato et al., 2020; Le & Nguyen, 2021), have been developed, so that slicing partial OT benefits from these efficient implementations and allows to compare large unnormalized measures. However, while (sliced) partial OT allows to compare measures with different masses, it assumes that each input measure is discrete and supported on points that all share the same mass (typically 1). In contrast, the Gaussian-Hellnnger Kantorovich (GHK) distance (Liero et al., 2018), another popular formulation of UOT, allows to compare measures with different masses and supported on points with varying masses, and has not been studied jointly with slicing.
Contributions. In this paper, we present the first general framework combining UOT and slicing between arbitrary distributions. Our main contribution is the introduction ion of two novel sliced variants of UOT, called Sliced UOT (SUOT) and Unbalanced Sliced OT (USOT). SUOT and USOT are both defined as regularized OT problems which leverage onc-dimensional projections, but differ on how they relax the mass preservation constraint: USOT essentially performs a global reweighting of the inputs measures (a, B), while SUOT reweights each projection of (o,18). We provide a theoretical analysis of SUOT and USOT, which reveals that they share topological properties with UOT while being statistically more efficient in high-dimensional regimes, thanks to the slicing operation. Additionally, we propose fast and GPU-friendly algorithms to compute SUOT and USOT, based on the (non-trivial) dual derivation of our SUOT and USOT losses and a Frank- Wolfe strategy (Séjourné et al., 2022b). Finally, we illustrate the efficiency of our framework on various experiments: we deploy SUOT and USOT to compare distributions on non-Euclidean hyperbolic manifolds, classify documents, transfer image colors and aggregate large-scale geophysical data, and discuss their advantages over existing approaches.
Outline. In Section 2, we provide background knowledge on unbalanced OT and sliced OT. In Section 3, we introduce our new loss functions (SUOT and USOT) and prove their metric, topological, statistical and
2

---

Published in Transactions on Machine Learning Research (12/2024)
duality properties in wide generality. We then explain in Section how to compute SUOT and USOT via Frank-Wol Soan-Wolfe-baseee approach. We finally analyze the performance of SUOT and USOT on different practical tasks in Section 5.
2
Background
In this section, we first state our notations. Then, we provide the necessary background on unbalancod optimal transport and sliced optimal transport.
2.1 Notations
In what follows, (R*)) denotes the set of all positive Radon measures of finite mass on R.. For any a E (TRO), supp(a) the support of a, and m(a) = Se da(x)) < +00 is the mass of a. For a E M_ and a map T: Rd + IR", Tææ is the pushforward measure of a by T, defined for all A C Rd as (yp(A) = p(T (A)). Let 5₂ be the Dirac measure at & and for n 2 1, define the empirical measure å, = =E w,dz, where (Z+) are independent and identically distributed (i.i.d.) samples from a MM and w; > For any convex function @ R R U {+oo}, we denote by yp its Legendre transform, i.e., for x R, (x(x) supy20 zy -ly)- We will also use the notation (
--x' For a, E (R @ B
is the product measure, and for f.g Rd + R, denote by f ② g Rd x Rdd -> R the mapping defined as
(ʃ (/og) (1,, y) = ((x)+(())) for all y Rdd gd-1 a E Rd ||0]] = 1} is the unit sphere, and for 0 gd-1
0* Rdd - R is the mapping defined (x) (0,z) for all E Rdd
2.2 Unbalanced Optimal Transport
We recall the static formulation of unbalanced OT proposed by Liero et al. (2018), which uses e-diveegencee penalty terms.
Definition 2.1 (p-divergencees. Let (a, B) (R x (R Let p: R + RR U {+oo} be entropy
function, i.e., &p is convex, lower semicontinuous, dom(pp) for E R, p(x) < too} c [0, +oo) and (o()) = 0.
Denote &/2o & 1im p(x), The g-divergence between a and B
da zd d3
df(x) + 6'c / da- (x),
(p(a A
(r)
(1)
where a is defined as a dg + +
Definition 2.2 (Unbalanced OT (Liero et al., 2018)). Let (p1: be a pair of entropy funclions and Ca Rd x Idd + I a cost function. The unbalanced OT problem between (), (T MMRR)) reads
/ Cula. ()d(()) v) +D (TI + (T2l3))
UOT(a, 3)
e inf =EM+
(2)
where and T2 denote the marginal distributions of with respect to (w.r.t.) the first and second variable respectively.
When &1 = 22 and (z(x) = 0 for x = 1, (z(x) = too otherwise, (2) boils down to the Kantorovich formulation of OT (or balanced OT), denoted by OT(a, 3). Indeed, that case, Dep (Tz (ax = D ( B) if mi = a and π² = B, De, (mı (a) Da (T218) +00 otherwise.
Under other suitable choices of entropy functions 11 and p2, UOT(a, B) is more robust than OT B), since it can discard outliers and compare and 8 with different masses. We refer to (Séjourné et al., 2022a, Section 4.2) for detailed discussion on the choice of entropics and its consequences on the transport plan computed by UOT. Two common choices are (xx(x) = x - 1| and (x) = p(x log(x) x + 1), where > 0 is a characteristic radius w.r.t. Ca- They respectively correspond to D.p. = pTV (total variation distance divergence), and operate differently: KL smooths
(Chizat et al., 2018a)) and Dj:: = pKL (Kullback-Leiil out geometric outliers, while TV either keeps or removes samples (Séjourné et al., 2022a). The GHK distance corresponds to (2) with Ca(r,y) y) || y/l and Dyp- = KT (Tiero et al., 2018).
3

---

Published in Transactions on Machine Learning Research (12/2024)
One can obtain equivalent formulation of UOT by deriving the dual of (2) and proving strong duality. We recall this result. below.
Proposition 2.3 (Corollary 4.12 in (Liero et al,, 2018)). The UOT problem (2) can equivalently be written UOT B) sup sagssa D(f.g: a, B), with
D(S.ga, - (i((()))dd(()) + (3(((()))BB())
(3)
(-(x --(=) with (x) _ sup, sup zy - pv(() the Legendre transform of Ppa and f S Ca meons that for (z,y) a @ 3, f(z) ( - Ca(2,)) y).
where for i {1,2), (7(x)
When clear from the context, we will omit the dependence on (a, 8) and write D(,g) instead of a The Legendre transform of yo well known for typical choices p--divergences. For example, De. = p;KL, then (x) = pi(e#/p 1).
Based on Proposition 2.3, one can compute (O, 3) by optimizing pair of contimuou functions (f.g). However, (O /3) is known to be computationally intensive (Pham et al., 2020), which motivates the de- velopment of methods able to scale to the large dimensions and sample sizes encountered in ML applications.
2.3 Sliced Optimal Transport
Among the many workarounds that have been proposed to overcome the OT computational bottleneck (Peyré et al., 2019), Sliced OT (Rabin et al., 2012) has attracted lot of attention due to its computational benefits and theoretical guarantees.
Definition 2.4 (Sliced OT). Let S & E Rd ||0|| = 1} be the unit sphere in Rd. For 6 E s denote by 0r : R the linear map such that for x E Rd, (x) over gd-1, Consider (a, E (RR) x (R.).. The Sliced OT problem is defined as
a (0, Let a be the uniform probability
{ OT(Oaa, (2))
SOT(a, B) A Jgt
(4)
where for any measurable function and any measurable set A C R, frE(A) & E(f (A)), f (A) a fz E Rd: f(x)= A}.
g È M+ fit is the push-forwart mcasure of & by f, i.c., for
is defined in terms of a cost function C RRR + R, and can be efficiently computed. Therefore, SOT(a, 3) can provide significant computational advantages over OT(a, 3) in large-scale settings. In practice, a Σ agdg, and B Σ B,d are discrete mcasures, the standard procedure for approximating SOT 3) consists in sampling i.i.d. samples [0,17= from o, then computing OT (T((f)) ra, (8)) for j =1,,.., 1,.... m. This second step involves sorting the n support points of a and 3 (Peyré et al., 2019, Section 2.6), thus involves On log n) operations per 0j.
Since (0 9) are two mcasures supported on R, OT( p. 07v)
SOT(a, 3) relies on the Kantorovich formulation of OT, thus SOT(a, B) < too only when m(a) m(3,, and may not provide meaningful comparisons presence of outliers. To overcome such limitations, prior works have proposed slicing a particular instance of UOT that is partial OT (Bonneel & Coeurjolly, 2019; Bai et al., 2023), for which D. is the total variation distance. More precisely, noting POT the UOT problem with D pTV, they consider for a, B (RR) the problem
SPOT(a, A / (3
8d-1
For the 1D partial OT problem, Bonneel & Coeurjolly (2019) solve one dimensional injective partial assignment in quasilinear complexity, but which does not allow for mass destruction in the source measure, while Bai et al. (2023) proposed an efficient procedure with a quadratic worst case complexity. However, their algorithms only apply to measures whose samples have constant mass (e.g., a, = 3, = 1). In the next section, we generalize their line of work and propose a new way of combining sliced OT and unbalanced OT.
4

---

Published in Transactions on Machine Learning Research (12/2024)
3 Sliced Unbalanced OT and Unbalanced Sliced OT
We present two new scalable and robust OT problems, by combining the unbalanced and slicing strategies in two different ways. We conduct a theoretical analysis of both strategies and provide a comparison of the two. For ease of exposition, all proofs of the results in this section are provided in Appendix A.
First, we propose to slice the unbalanced OT problem: we average the UOT problem over different projections of the compared measures, similar to the approach of sliced partial OT (Bonneel & Coeurjolly, 2019; Bai et al., 2023). We refer to this problem Sliced Unbalanced OT (SUOT) and introduce it in Section 3.1. Next, we explore the reverse strategy, i.e., unbalonce the sliced OT problem: the weights of SUOT are penalized to introduce imbalance, analogous to how UOT relates to OT. We call this method Unbalanced Sliced OT (USOT) and present it. in Section 3.2.
3.1 Sliced Unbalanced Optimal Transport
Our first strategy consists in slicing the unbalanced OT problem and leads to the following definition. Definition 3.1 (Sliced Unbalanced OT). Let (P11)22) be pair of entropy functions and C1 R x R R cost function. The sliced unbalanced OT problem between (a, MM (R.) x M_(RR) reads
{ gg--
SUOT(a, &
UOT(era,6)p))) ()do
(6)
where for 0 ~ o, UOT(O 07 M, SEXR C1 Ci ( v) p. ((T))) +D ((TO)2 1078) with (Te)1, (TT)2 the marginal distributions of ma.
By definition, SUOT is a specific instance of the class of sliced probability divergences (Nadjahi et al., 2020a), where the base divergence is chosen as UOT. SUOT can also be interpreted as a general expression of the sliced partial OT problem (Bonneel & Coeurjolly, 2019; Bai et al., 2023): while the latter imposes P.p P,TV, SUOT allows for the use of arbitrary p-divergences.
In the following, we establish set of theoretical properties for SUOT with different choices of g-divergences and cost functions Cj. First, we identify sufficient conditions for which the solution of (6) exists.
Proposition 3.2 (SUOT: Existence of solutions). Assume that C1 is lower-semiiontiimuuus and that either (i) &1.00 = 422,00 +xc, (ti) C₁ has compact sublevels on R x R and 4/,,0 + 122.00 + inf C1 > 0. Then, the solution of SUOT(a, B) erists, in the sense that for any 0 ~ a, there caists Tă E M (R x TR) attaining the infimum in UOT(0)a,023
The assumptions of Proposition 3.2 are met for some settings of interest, including D = D = KL (since f'x = +00), or Dap = D2p = TV and Ci y) = lo - y/P (p 2 1) (since & = =)) see (Séjourné et al., 2022a, Section 2.1) for more details.
Next, we show some topological properties of SUOT. the metric properties of UOT, which is consistent with (Nadjahi et al., 2020a, Proposition 1). In Section 3.3, we study the metrization of the weak"-topology with SUOT.
In the next proposition, we prove that SUOT preserves
Proposition 3.3 (SUOT: Metric properties). Suppose UOT is non-negative, symmettrc and/or defonite (R) x (R). Then, SUOT is respectively non-negative, symmetric and/or orr definite M+ x M,(IR) If there erists p (1,+ s.t. for any a, 3, E (K)), UOT s UOT + COTT/P(y,)) 8), then SUOTT/P B) < SUOT*/P(a, 7) + (P,T
By Proposition 3.3, establishing the metric axioms of UOT between univariate measures (as detailed in (Séjourné et al., 2022a, Section 3.3.1)) is sufficient to prove the metric properties of SUOT between mul- tivariate measures. For example, since GHK is a metric for the order p 2 (Liero et al., 2018), so is the induced SUOT.
We move to the statistical aspects and study the sample complexity of SUOT. For (a, E M_ (Rd) x Mf (Rd), we establish the speed of convergence of SUOT(ân,, Ba)) toward SUOT(a, B)), where &n, Bn denote
5

---

Published in Transactions on Machine Learning Research (12/2024)
the empirical measures supported on independent samples from a, 3 respectively (as defined in Section 2.1). We prove below that SUOT extends the sample complexity of UOT from one-dimensional settings to multi- dimensional ones,
Theorem 3.4 (SUOT: Sample complexity). (i) Assume for (1, v) E MxM with M C (R), COT(An; Px)) V k(n). Then, for (a, M M with M - in E M+ A0 E s o E M),
E|SUOT(a, B) - ( Bw)1 S x(n).
(ii) Assume for E M with M C (B),,, EIUOT(N, S E(n). Then, for E M with M & {m (RR) : v0 E gd-1, nin E M), EJSUOT(a, â.))l s {(n).
Note that the expectations in Theorem 3.4 are taken with respect to the samples of the empirical measures, which are random. Theorem 3.4 shows that SUOT enjoys dimension-free sample complexity, even when comparing multivariate measures. This advantage is recurrent sliced divergences (Nadjahí et al., 2020b) and further motivates their use on high-dimensional settings. The sample complexity rates x(n) or E(n) can be deduced from the literature on UOT for univariate measures. For instance, the GHK setting, the rate is given by x(n) n n-1/2 for mcasures with compact, convex support and contimuously differentiable densities (Vacher & Vialard, 2023, Corollary 3.4), and a suitable class M can be defined.
Finally, we derive the dual formulation of SUOT and prove that strong duality holds. This result has impor- tant practical implications, as we will leverage in Section 4 to develop a methodology for computing SUOT. Note that the computation of SUOT involves integration with respect to σ, which generally cannot be done in closed from, as the case for most sliced divergences. Since our goal to develop a practical and imple- mentable method, we will consider the Monte Carlo approximation commonly used by practitioners to com- pute sliced divergences (Nadjahi et al., 2020a): approximate (UOT 3) as fga-, UOT(0) 8 3)d where dx is a discrete distribution supported on K i.i.d. samples drawn from σ.
Theorem 3.5 (SUOT: Strong duality). For E {1,2}, let pi be an entropy function such that dom( (p] nRR is non-empty, and either 0 E dom((pi) or m(a), m() E dom((p;). Let E a ((Foggo)eesuppee, 40 e supp(ōk), @ go S C.J. Then,
sup [ (Jo.0) JSm-
SU)
D(fo, go:
(8).
(7)
3.2 Unbalanced Sliced Optimal Transport
As second strategy to make unbalanced OT scalable, we propose to unbalance sliced OT. To this end, we start with the following formulation of UOT (Liero et al., 2018),
inf UOT(a, (MI.))) OT(m1,7)) - Do, (m1la) - Deo, (m218),
(8)
and we replace UOT by its sliced counterpart, SOT. This yields the following definition: Definition 3.6 (Unbalanced Sliced OT). Let (491, (22) be pair of entropy functions. The unbalanced sliced OT problem between (a, 3) MM (IEd) x M+ (IRd) reads
USOT(a, A (M
inf
SOT(T) + D. (Tila) + Des (m)
(9)
This approach is entirely novel since, to the best of our knowledge, it has never been studied in prior work, even for specific choices of entropy. To gain a better grasp of this new object, USOT, we examine how the thcoretical propertics discussed in the previous section apply here.
We first prove that the solution of (9) exists under the same conditions as those for SUOT outlined in Proposition 3.2.
Proposition 3.7 (USOT: Existence of solutions). Assume that C₁ is lonerr-semioontinooas and that either (i) P'..0 = -2 +0C, or (ii) C1 has compact sublevels on R x R and 41,00 + t22,00 + inf C1 > 0. Then, the solution of USOT(a, (8) exists: there erists (मī, E M+ (Rd) ) x M+MTT allaining the infemum in (9).

---

Published in Transactions on Machine Learning Research (12/2024)
Drrections Source data Torget dito
1307 9-120 9 50" ( 00-00 0 10:300
0t 30
UF 120 10:00000 010 90 02 00
Original distributions
SUOT P. =000
USOT Pi 1
Figure 1: Toy illustration on the behaviors of SUOT and USOT. (left) Original 2D samples and slices used for illustration. KDE density estimations of the projected samples: grey, original distributions, colored, distributions reweighed by SUOT (center), and reweighed by USOT (right).
We then review the conditions under which USOT is (pseudo-)metrit) and we prove that strong duality holds. Similar to SUOT, the dual formulation that we derive will enable the design of an algorithm for effectively computing USOT in practice.
Proposition 3.8 (USOT: Metric properties). For any (a, (R4) x (R USOT(a, 3) 2 0. If = P2, USOT is symmetric. If Di, and Dep, are definite, then USOT is definite. If C1 = lz and D2, = D2p = pTV, then, USOT satisfies the triangle inequality.
Theorem 3.9 (USOT: Strong duality). For i E (1, 2}, , let yi be an entropy function such that ( 0 nT__ is non-emply, and either 0 E dom(pp)) or m(a)), m(3) E dom((p,). Let E 2 (00esuppoo))) v0 E supp(áx), Jo ① go C. Then,
D f 500 / 3a- go 0 (0)
USOT(a, sup (E.
(10)
Since USOT does belong to the class of sliced divergences, establishing its sample complexity is more challenging compared to SUOT. Based on the literature, standard technique involves deriving covering number bounds the space of the dual potentials of USOT. This theoretical question is highly non-trivial given the complex structure of &, and as such is out of the scope of this paper. Nevertheless, we investigate the sample complexity on empirical settings: our experimental results presented in Appendix C.5 suggest that USOT might also enjoy a dimension rate.
3.3 Comparative Analysis of Sliced Unbalanced and Unbalanced Sliced Optimal Transport
In addition to the theorctical analysis previously conducted for SUOT and USOT independently, this section provides further insights to better grasp the differences between these two strategies.
First, by comparing Definition 3.1 with Definition 3.6, SUOT and USOT clearly differ the conceptual level. Specifically, SUOT(a, 3) penalizes the marginals of He for 0 ~ or where нe is the coupling that transports mass from 0 to B. In contrast, USOT(a, 3) directly regularizes the marginals of the coupling between a and B. To illustrate this difference, we consider (a,33) E M4(R3)) (R²) x M+ with a contaminatod by outliers, then compute SUOT(a, B) and USOT(a, 3). We plot (a,8) and the sampled projections (0x)s. (Figure left), the marginals of (mTa ) obtained with SUOT(a, B) (Figure 1, center), and the marginals of ((0));;)) with USOT(a, 3) (Figure 1, right). We observe that the source outliers in a have been successfully removed by USOT(a, B) for all 02, while they may still appear with SUOT(a, 3) (e.g., Figure 1, center: note the bimodal marginal in blue for 0 = 120%). This difference is due to the marignal penalization terms in USOT(a, B), which operate directly w.r.t. (a, B) rather than their projections (0īa, ()3), unlike SUÓT 88).
A question of particular interest regarding probability divergences how they relate each other, specifically whether they yield equivalent topologies. We explore this question for SUOT and USOT. To do so, we
7

---

Published in Transactions on Machine Learning Research (12/2024)
consider notion of equivalence that is frequently studied in the literature, as in (Bayraktar & Guo, 2021, Theorem 2.3.(i).
We start by proving a first set of inequalities that relate SUOT, USOT and UOT: our next theorem shows that USOT is always greater than SUOT and that, for appropriate choices of cost functions, USOT is upper-bounded by UOT.
Theorem 3.10. For any (a, E (R() x M+(R9)
SUOT 3) S USOT(a, B).
(11)
e Moreover, suppose that, V(r,y) E Rdd Rd 40 E s6-1 (1), & Ca(r,y). Then, for any (a. () (R x M+
SUOT(a, 3) V (a B) z UOT(a, B).
(12)
In particular, Theorem 3.10 holds for the following common choice of costs: V(s,t) R2, Ci(s,t) = tlp and V(z, y) E Rd x RR, Ca(z,y) || vll", with p [1, +oo).
Next, we prove that UOT(a, 9) can be upper-bounded by functional of SUOT 3) when (a,3) have compact supports, by adapting the reasoning from Bonnotte (2013, Lemma 5.1.4) to our setting and con- sidering the duals of UOT (Proposition 2.3) and SUOT (Theorem 3.5) instead of the dual of OT and SOT. Most arguments in (Bonnotte, 2013) adapt well to our setting, but establishing a Lipschitz condition on the integrand of the dual required a more technical approach. To this end, we prove Lemma A.13, which results in different constant value, denoted as c(m((a), m(3), R.).
Theorem 3.11. Let X C Rd be compact set with radius R. Define the cost functions Ci(s,t) Is 8/", (s, IR?,, and v) = || -ull,, (z. E Rd x Rd, with p E [1, to0). Assume either, (i) D. = Dop = PKL; or (ii) p = 1 and Dd, = Dip = pTV. Then, for any (a, M+(X) x M+(X),
UOT B) S c(m((), m(3), p, R) SUOT(a, B)ah,,
where c(m(a), m(3), P, R) is a conslant depending on m(a), R, which is non-decreasing in m(a) and m(3).
We show the equivalence of SUOT, USOT and UOT by combining Theorem 3.11 and Theorem 3.10, assuming that the constant c(m(a), m(3), p. R) does not depend on m(a), m(3). This occurs, for example, when the masses of and 3 are uniformly bounded; that is, there exists M E E4, such that m(a)) S M and m(3) S M.
The equivalence of SUOT, USOT and UOT is a key result for proving that SUOT and USOT metrize weak* convergence, provided that UOT docs (as in the GHK setting (Licro et al., 2018, Thcorem 7.25)). Recall that a sequence of positive measures (an )nen converges weakly to a E MM (denoted by an - a) if, for any continuous and bounded f Rd + R. lim J fda,, f fda.
Theorem 3.12 (Metrizability of the weak" topology by SUOT, USOT). Assume the conditions in The- orem 3.11 are met. Let (an)nEN- be a sequence of measures in MM and a E M4(X), where X C Rd is a compact set with radius R. Then, SUOT and USOT metrize the weak" convergence, i.e., On a + lim SUOT(a,, = O, and an - + lom a)) =
The metrizability of weak" convergence was not studied in related work, including in existing instances of our framework, such as partial OT (Bonneel & Coeurjolly, 2019; Bai et al., 2023). In addition to complementing prior work, our result paves the way for other rescarch directions. For instance, it can be used to justify unbalanced Wasserstein gradient flow (Ambrosio et al., 2005) using
the well-posedness of approxinating SUOT, as done for SOT in (Candau-Tiie Tilh, 2020; Bonet et al., 2022). Unbalanced Wasserstein gradient flows have been a key tool in deep learning thcory, e.g., to prove global convergence of onc-hidden layer neural networks (Chizat & Bach, 2018; Rotskoff et al., 2019).
4 Computing SUOT and USOT with Wolfe algorithms
In this section, we propose two algorithms to compute SUOT and USOT in practice. The resulting procedures are given in Algorithms 2 and 3 respectively, and require smooth penalty terms (Dy1s Dyp)). This condition
8

---

Published in Transactions on Machine Learning Research (12/2024)
is satisfied in the GHK setting (Dp; p,KL), but not for sliced partial OT (D,, PVTV, Bai et al. (2023)). Our strategy is inspired by Séjourné et al. (2022b), where they proposed to solve the unbalanced OT problem between univariate measures using the Frank- algorithm (as recalled in Appendix B.2). More precisely, we apply FW to optimize translation-invarine forms the dual problems derived in Theorems 3.5 and 3.9.
4.1 Background: Frank-Wolfe Algorithm and Application to One- mne-Dimensional Unbalanced OT
FW is popular iterative first-order optimization algorithm for solving max H(z), where & is compact convex set and H & - IR concave, differentiable function. The procedure consists in maximizing a linear approximation of H at each iteration: given the current iterate It, FW solves the linear oracle T4+1 E arg max,ee (VH(x;), r), then performs 21+1 = (1 7+11) + 7417744 with stepsize "n-1 typically chosen as 7t+ = 1+1-1 We refer to this step as FWStep and report the pseudo-code in Appendix B.2.
Séjourné al. (2022b) apply FW to solve translation-invariant formulation of the dual of UOT(a, () for (a, 3) (R) x M (R), and show that the linear oracle in FWStep is the dual of OT 3c) where (a 3,) are normalized versions of (a, 3), i.e., m(aa) = m(3) = 1. Therefore, computing UOT amounts to solve a sequence of OT problems, which can efficiently be donc since (at, are univariate probability mcasures. The expression of (at,,3e) 3e) depend on the input measures (a, the current iterates (fe,9t and the penally coefficients (21.
4.2 Foank-Wolfe Solvers for Sliced Unbalanced and Unbalanced Sliced OT
Translation-invariant duals. We compute SUOT(a, B) and USOT B) for any (a, e M4(R)) x (IR.) by solving translation-invariant formulations of their duals with FW. By Theorems 3.5 and 3.9, and adapting the reasoning of Séjourné et al. (2022b), we prove that
SUOT(a, = sup (So.0)EE [ H(fa.go go: a (0o,033)e (z3)dōk(0),
(13)
100 / go 0 0' (o)x())
USOT(a,3)
sup H (So.go)EE
(14)
where H(f, gi a, 3) A supxes D(f + X, - 3). These alternative duals are translation-invann = H(, If (ff, (E) are smooth and strictly concave, then the maximizer H. denoted by (f. exists and unique. In particular, when De, = KL and Dip- *22KL, (f admits an analytical expression, which is given in the normalization routine (Algorithm 1). This is convenient as it avoids the need for approximate solvers to compute H(f,g;,,
since,
for any X E R, + - X;
Frank-Wolf iterations. We then apply FW to solve (13) and (14). We show that each itcration consists in solving a particular sliced OT problem between probability measures that depend on the input (a, and the iterates. To clarify this point, we present below the updates of FWStep tailored for each problem, starting with SUOT.
Algorithm Norm(a, B, f. Pl, P2)
Input: a, B, J. 9, P2 Output: Normalized measures (ō, 8)
x .102 log Pstp2
(((0)=
Proposition 4.1 (Frank-Wor Wolfe iterations for SUOT). Let (0,3) E M+ (IR.) (R and consider solving (13) with FW. Assume that (pf, are smooth and strictly concave. Given current it- erales (oogh)ees (b))ssppp((x))
ā + (a(v)-
α
B x-
P2
B
Return (a. B)
ε, the solutions of the linear oracle (r),, s))0esupp(áx) are the dual potentials of Sga-1 OT(Ofa) 07 ()))), where (a (8) are measures given by at V (Jh + + (T))gg)))a and B3 = (gh (Fbbgh))
Proposition 4.1 shows that each FW iteration for solving the translation-in roduces to solving a balanced sliced OT problem: by (Séjourné et al., 2022b, Proposition 1), the measures (ag.5%) have the same mass, i.e., m(ag) = m(3)). When using Ka-based penalty terms, the procedure for computing (ah (8) is detailed in Algorithm 1, and reports the closed-form expression of X X* gf).
dual of SUOT(a, B)
9

---

Published in Transactions on Machine Learning Research (12/2024)
Algorithm 2 SUOT
Algorithm 3 USOT
Input: a, 8, F, (0u) pl, P2 Output: SUOT(a, (9) g0)
Input: a, 3, F, (0%)k=I pl, p2 Output: USOT(a, (favg: Savg)
(fv,go) + (0,0)
favg
+ 0,
for t 0.,,... 1 do
for 0, 0,,,,,.... 1 do
for 0 E (0x) L- do
for 0 E (0x) do
(as, Me) - ao a, 3. go. pr, P2)
(MI, π2)
- Norm B, fa goug: Pl, p2)
(ra, S6) t SlicedDual 9e)
(re, Se)
< SlicedDual (0; Tı, 02 m2)
fo +- (1 7a)oo + paro (FWStep)
end for
go 4- (1 7)90 + 7680 (FWStep)
(Tavgy Savg) < R - ro R k== 80,
end for
fang + (1 - "/) + Yrrn (FWStep)
end for Return SUOT(a, (fo. 90) as in (7)
Jasg + (1 "))aav + yesyy (FWStep)
end for
Return USOT(a, 3), (Saugs Govy) as in (10)
Each iteration requires computing the dual potentials of sliced OT problem, which is non-trivial: previous implementations related to sliced OT only output the value of the loss, SOT (3), typically in the context of training generative models (Deshpande et al., 2019; Nguyen et al., 2020). We thus desigu two novel implementations in PyTorch (Paszke et al., 2019) to compute the dual potentials of sliced OT. The first one leverages that the gradient of (T w.r.t. (0 are optimal g), which allows to backpropagate OT () w.r.t. (a, 3) to obtain (re. sp). The second one computes them in parallel on GPUs using their closed form, which to the best of our knowledge, a new sliced algorithm. We call SlicedDual(a, (3) the step returning optimal (re, s9) solving OT(Ofa, a 07 for all 0 E supp(ōk), and refer Appendix B.3 for the algorithms.
Building on Proposition 4.1 and the discussion above, we develop the FW methodology to compute SUOT(a, B) and detail it in Algorithm 2. Next, we derive the FW iterates for USOT(a, 3).
Proposition 4.2 Wolfe itcrations for USOT). Let (a, (R (R.) and consider solving (14) with FW. Assume that (4i, (2) are smooth and strictly concave. Given current iterates (fb. (b)ebbesuppp(k)) SOT(a", 3)) where Be), are measures given by ãi V + X* (Javgrgaog))a and B, = ( X'aaug:9an 3,, with fang(x) a f6 (z))(=)) (uvg(y) & fg--1 I (v))dd (f).
E, the solutions of the linear oracle (r), s()oeappp(dk) are the dual potentials of
The resulting FW methodology, detailed in Algorithm 3, also leverages the Norm and SlicedDual routines. The key difference from SUOT(a, 9) is in where the integral over I E supp(ox) is performed, leading to a different balanced sliced OT problem to solve.
Marginals of UOT/USOT. The optimal primal marginals of UOT and USOT are geometric normal- izations of inputs (a. with discarded outliers. Their computation involves the Norm routine detailed in Algorithum 1, using optimal dual patentials. This how we compute marginals in Figure and in the experiments of Section 5: see Appendix B.4 for more details.
4.3 Convergence Properties and Complexity
Convergence and stochastic Frank-Wore Wolfe. Our theoretical setting verifies the assumptions of (Lacoste- Julien & Jaggi, 2015, Theorem 8), thus ensuring fast convergence of our methods. The mumber of FW iterations needed to converge remains low in our experiments. We give in Appendix B.5 empirical evidences that few iterations of FW (F < 20) suffice to reach numerical precision.
Formally, the preceding algorithams assume that the functional H. is given through integrals over the hyper- sphere, describing the set of all possible directions 0. However, in practice, SOT computed by Monto-Carlo approximations, i.e., drawing fixed number K of directions (B&) and solving independently the different ID OT problems. In the specific case of SUOT, this does not change much: K FW procedures are
10

---

Published in Transactions on Machine Learning Research (12/2024)
Table Accuracy on document classification
BBCSpprt
Goodreads
Accuracy
0.30
(-10-%s
Arc (genm)
Acc (like)
t (-10-%)
SOT
OT
94.55
3.12g1.61
55.22
71.00
440.30g30
USOT
DOT
96.73
242239
SUOT
SinkhUOT
95.45
46.2222.17
53.55
67.81
2021.68
0.00
SOT
89. 79.39
1.80
30.09
65 20
1.49
10
10
10
10
SUOT
90.12 10.12
13.9
30.15
10.32
14. 14.32
p
USOT
93.52 93.52220.04 04
14.37g1.3
32.67.0.0z
67.78.0.30
14.45
SUOT (CV
90.00=0059
49.67
66.43
Figure 2: Ablation on BBCSport of
USOT (CV
92.61_20.55
32.0617.80
66.611am7
independently (eventually parallel) over the fixed set of directions. The case of USOT relies on a global FW scheme, where faug: Goeg are computed w.r.t. a fixed distribution Ôx (1/K) 50, This empirical distribution of directions can be considered fixed throughout the FW iterations, or can be drawn indepen- dently for each iteration of the FW procedure. This actually corresponds to Stochastic FW algorithm, which also converges as our setting verifies the assumptions of (Hazan & Luo, 2016, Theorem 3). We call this procedure Stochastic USOT, which corresponds to Algorithm except that (0%) sampled at cach iteration. Since this procedure performs well in our experiments (e.g., Table 4) and Eg o, this suggests the dual in Theorem 3.9 holds for a.
A Algorithmic complexity. FW algorithms and its variants have been widely studied theoretically. Com- puting SlicedDual has theoretically a complexity O(KN N), where N is the number of samples, and K the number of projections ő-- However, we note that the sorting operation, which yiclds the super linear complexity, can be computed once for all FW iterations. Consequently, the overall complexity of SUOT and USOT is thus O(KN log N + FN), where F is the number of FW iterations needed to reach convergence, with O(N) complexity. Thus, our formulation enjoy similar complexity than SOT, which is particularly appealing. However, Stochastic USOT is more costly, as each iteration requires sorting data projected along newly-sampled (0+))=1- Its complexity is therefore O(K FN log N). We finally note that due to the independent nature of the treatments of every projections, computing both Norm and SlicedDual operations can be done in parallel, leveraging GPU computations when available.
Extension to non-Euclidean settings. Interestingly, algorithms offer great modularity, in the they can easily be used to compute unbalanced versions of existing variants of SOT. Indeed, while such variants differ in the one-dinensional representations of a and B they use, they all consist in solving ID OT problems to compare and 8, which our FW strategy can solve. To illustrate this point, we combined our FW routine with hyperbolic SOT (Bonet et al., 2023c) to compare measures supported on hyperbolic spaces: see Appendix C.3.
5 Experiments
This section presents a set of numerical experiments, which illustrate the effectiveness, robustness and computational efficiency of USOT" We first showcase the benefit of USOT over SUOT and SOT on a document classification task. Then, we consider experiments in very large scale scttings such as color transfer on every pixels and the compulation of barycenters of geophysical datasets.
5.1 Document classification
We first consider a document classification problem (Kusner et al., 2015). Documents are represented distributions of words embedded with word2vec (Mikolov et al., 2013) in dimension d = 300. Let Dù be the k-th document and zf...., x E &d be the set of words in DE. Then, D₁ Σn, 5 where wf is the frequency of &t in Dj normalized s.t. E1H, w = Given loss function L, the document classification task is solved by computing the matrix (L(DR, D()) k.e" then using k-nearest neighbor classifter. The aim
The code available at https://github: wtt.:lccccmccaaaa/aeeeeceee www.c//aaee//aaeaaacacaaccaaaa/a /Slicnntt/Siiinn... Unbalanced Optimmal_pppm__mmmm Transport
11

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 3: Color transfer between a source and a target image (first and second columns). We compare SOT gradient flows operated the color space (third column) and the same procedure with reweighing of the distributions by USOT (fourth columm). The last column shows percentage of mass change given by USOT, i.., (mg-8) where red indicates mass creation and blue mass destruction.
of this experiment is to show that by discarding possible outliers using well chosen parameter p, USOT is able lo outperform SOT and SUOT on this lask. Since word lypically appears several times in document, the measures are not uniform and sliced partial OT (Bonneel & Coeurjolly, 2019; Bai et al., 2023) cannot be used in this sctting. We detail in Appendix C additional experiments without normalizing histograms to compare with (Bai et al., 2023) (í.e., Σ w is the sentence length). We consider the BBCSport dataset (Kusner al., 2015), a standard benchmark with small documents for which OT can be used effectively, and the Goodreads dataset (Maharjan et al., 2017) on two tasks (genre and likability predictions), a dataset with large-scale documents for which the computational burden of performing OT and UOT is substantial. We report on Table the accuracy and average runtimes of OT, UOT computed with the majorization minimization algorithm (Chapel et al., 2021) or approximated with the Sinkhorn algorithm (SinkhUOT) (Pham et al., 2020), as well as SOT, SUOT and USOT. All the benchmark met are computed using the Python OT library (Flamary et al., 2021) on a Nvidia Tesla V100 GPU. For sliced methods, we average over computations of the loss matrix and report the standard deviation Table The number of neighbors was selected via cross validation. The results for UOT, SinkhUOT, SUOT and USOT are reported for p yielding the best, accuracy among grid (see Appendix C.1 for more details), and we display ablation of this parameter on the BBCSport dataset in Figure 2. We also add on Table the results obtained with cross validation (CV) on for USOT and SUOT. Our findings demonstrate that our approaches surpass SOT in performance, incurring only a minor computational overhead. Moreover, our methods closely rival the performance OT, while being 40 times faster on large-scale datasets. This highlight their practical significance, particularly when OT computationally unfeasible.
5.2 Color transfer
Color transfer is a long-standing problem in OT, which dates back to the seminal work of Rabin et al. (2010). It consists in aligning the color distributions of two images. While previous works, e.g. (Ferradans et al., 2013; Bonneel et al., 2016), considered color palettes to deal with the complexity OT, we illustrate the scalability of our methods by considering here the full distributions of pixels within images, in a way similar (Bonneel & Coeurjolly, 2019). We express the color transfer a gradient flow, where every pixel is sample in the 3D RGB color space. Formally, let a(t) = N E Sx,(t), B 1
Mf Σe δy,, where a (resp. 5) represents the color distribution of the source (resp. target) image. The SOT gradient flow performing color transfer consists in iterating the following scheme: X(++ ( (t))~Vv v -)S((((()))))) 8), where a(t) is the color distribution of the source image at iterations i, supported by pixels from X(I). One of the major
12

---

Published in Transactions on Machine Learning Research (12/2024)
Model 1
Model 2
Model 3
Model 4
0.0006
0.0005
TMQ (Precipitabie Water)
0.0004
0.0003
0
0.0002
0.0001
L2 Mean
SOT
USOT
Figure 4: Barycenter of geophysical data. (First row) Simulated output of 4 different climate models depicting different scenarios for the evolution of tropical cyclone (Second row) Results of different aggre- gation strategies.
problem is color bleeding: potential color artefacts are likely to appear since the object proportions between images likely to differ. We propose correct this issue in two steps procedure, relying on USOT: i) first obtain optimal marginals (œi. mg) by solving (9) and using the Norm routine, then ti) solve the classical SOT gradient flow with the measures (Tī, mT)
We present results on 300 x 300 images produced by the generative model Midjourney (Mid, 2023). The images correspond to two landscapes and photo-realistic portraits of two women (see first and second column of Figure 3). For every results, we ilerate the gradient flow for 100 ilerations, and the learning rate y is set to 10-2. The computation of the final result produced in less than one minute with commodity GPU, while it is out of reach for OT UOT solvers this distributions size (90K pixels). The third column shows the color transfer using SOT. It reveals instances of color bleeding: green clouds appear in the sky of landscape scenes, and red superimposed logo results in unwanted red pixels in the portrait. Contrasting, the fourth column displays the outcomes achieved through our approach, effectively addressing the color bleeding issue. We chose P1 = 10 and P2 = 0.02 for this task and we observe the resulting change in mass distribution on the larget image in the last column of Figure darkened landscape in the first case and the removal of the logo in the second), which only possible when all the pixels are considered in the transfer.
provides insight ful indications of the discarded colors (the
5.3 Barycenter of geophysical data
OT barycenters are an important topic of interest (Le et al., 2021) for their ability to capture mass changes and spatial deformations over several reference measures. In order to compute barycenters under the USOT geometry on fixed grid, we employ a mirror-descent strategy similar to (Cuturi & Doucet, 2014a, Algorithm (1)) and described more in depth in Appendix C. We compute unbalanced sliced OT barycenter for climate model data. Ensembles of multiple models are commonly employed to reduce biases and evaluate uncer- tainties climate projections (Sanderson al., 2015; Thao al., 2022). The commonly used Multi-Model Mean approach assumes models are centered around true values and averages the ensemble with equal varying weights. However, spatial averaging may fail in capturing specific characteristics of the physical system at stake, and we propose to use USOT barycenter instcad. We use the ClimateNet datasct (Prabhat et al., 2021), and more specifically the TMQ (precipitable water) indicator. The ClimateNet dataset is a semman--xperr-labelle curated dataset which captures tropical cyclones (TCs), among other things. To simulate the output of several climate models, we take a specific instant (first date of 2011) and apply the clastic deformation from TorchVision (Paszke et al., 2019) in an area close the castern part of the U.S.A.
As result, obtain 4 different TCs, shown in the first row of Figure 4. The classical L.2 spatial mean is
13

---

Published in Transactions on Machine Learning Research (12/2024)
displayed the second row of Figure 4 and reveals different TCs centers/modes, which is undesirable. As the total TMQ mass in the considered zone varies between the different models, direct application of SOT is impossible, or requires a normalization of the mass that has undesired effect as can be seen on the second row. Finally, we show the result of the USOT barycenter with p1 = =lel (related to the data) and Pz = le4 (related to the barycenter). This barycenter has only one apparent mode, which is the expected behaviour. The considered measures have a size of 100 x 200, and we run the barycenter algorithm for 500 iterations (with K 64 projections), which takes minutes problems are intractable, and to the best of our knowledge, our experiment is the very first instance where unbalanced OT barycenters can be computed on such large scale.
a commodity GPU. UOT barycenters for this size of
6 Conclusion
We proposed two losses merging unbalanced and sliced OT, with theoretical guarantees and an efficient and modular Frank- Wolfe algorithm. We illustrate the performance improvement over SOT on varions experiments, and described novel applications of unbalanced OT barycenters of positive measures, with a new case study on geophysical data. These novel results and algorithms pave the way to numerous new applications of sliced variants of OT, and we believe that our contributions will motivate practitioners further explore their use in general ML applications, without the cumbersome task of pre pre-processing probability measures.
Acknowledgments
We thank the anonymous reviewers for their valuable comments. KF was supported by NSERC Discovery grant (RGPIN-2019-0611) and a Samsung grant. CB was supported by project DynaTearn from Labex CominLabs and Région Bretagne ARED DLearuMe, and by the ANR PEPR PDE-AL. NC was supported by the ANR AI Chair OTTOPIA ANR-20-CHIA-0030
References
Midjourney, 2023. URL "https://docs" midj junjjoouney..ooo... com.////cccommma////e/eee (Cited on p. 13)
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2005. (Cited on p. 8)
Yikun Bai, Bernhard Schmitzer, Malthew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13681-13690, 2023. (Cited on 2, 4, 5, 8, 9, 12, 39)
Tadas Baltrusaitis, Chaitanya Ahuja, and Louis-Philippe Morency. Multimodal machine learning: A survey and taxonomy. IEEE transactions pallern analysis and machine intelligence, 41(2):423 443, 2018.
(Cited on 1) 1)
Erhan Bayraktar and Gaoyue Guo. Strong equivalence between metrics of Wasserstein type. Electronic Commanications in Probabilily, 26(none):1 - 13, 2021. doi: 10. 10.1214/21-FCC338. (Cited on p. 2)
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, (13) 2003. (Cited on p. 41)
Vladimir Tgorevich Bogachev and Maria Aparecida Soares Ruas. Measure theory, volume 1. Springer, 2007. (Cited on 23)
Clément Bonet, Benoît Malézieux, Alain Rakotomamonjy, Lucas Drumetz, Thomas Moreau, Matthieu
Kowalski, and Nicolas Courty. In Proceedings of the 40th International Conference on Machine Learning. 2023a. (Cited on 2)
on symmetric positive definite matrices for m/eeg signals.
Clément Bonet, Nicolas Courty, François Septier, and Lucas Drumetz. Efficient gradient flows in sliced- wasserstein space. Transactions Machine Learning Research, 2022. (Cited p. 8)
14

---

Published in Transactions on Machine Learning Research (12/2024)
Clément Bonet, Paul Berg, Nicolas Courty, Frangois Septier, Lucas Drumetz, and Minh-Tan Pham. Spherical slioed-wasserstein. Tn The Fleventh International Conference on Learning Represenlations, 2023b. (Cited
on 2)
Clément Bonet, Laetitia Chapel, Lucas Drumetz, and Nicolas Courty. Hyperbolic wasserseannn via geodesic and horospherical projections. In Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), pp. 334-370 PMLR, 2023c. (Cited on p. 11, 41)
Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions Graphics (TOG), 38(4):1-13, 2019. (Cited on p. 2, 4, 5, 8, 12)
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycen- ters of measures. Journal of Mathematical Imaging and Vision, 51:22-45, 2015. (Cited on p. 2)
Nicolas Bonneel, Gabriel Peyré, and Marco Cuturi. Wasserstein barycentric coordinates: histogram regres- sion using optimal transport. ACM Trans. Graph., 35(4), jul 2016. (Cited on p. 12)
Nicolas Bonnotte. Unidimensional and evolution methods for optimal transportation. PhD thesis, Université Paris Sud-Paris XI; Scuola normale superiore (Pise, Italic), 2013. (Cited on p. 8, 25, 26)
Jules Candau-Tin Tilh. Wasserstein and sliced-wasserstedd distances. Master's thesis, Université Pierre et Marie Curie, 2020. (Cited on p. 8)
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-2333 23282, 2021. (Cited on p. 12, 37)
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over parapaarmeterzee models using optimal transport. Advances in neural information processing systems, 31, 2018. (Cited on p. 2, 8)
Lenaic Chizat, Gabriel Poyré, Bernhard Schmitzer, and LaançiisXavvicn Vialard. An interpolating distance between optimal transport and fisher rao metrics. Foundations of Compulational Mothematics, 18:1 44, 2018a. (Cited on p. 3)
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavs Xavier Vialard. Unbalanced optimal trans- port: Dynamic and kantorovich formulations. Journal of Functional Analysis, 274(11):3000 3123, 2018b. (Cited on p. 2)
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances neural information processing systems, 26, 2013. (Cited on p.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In Eric P. Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 685 693, Bejing, China, 22 24 Jun 2014a. PMLR. (Cited
on p. 13)
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. Tn International conference on machine learning, pp. 685 693. PMLR, 2014b. (Cited on p. 41)
Pinar Demetci, Rebecca Santorella, Manav Chakravarthy, Bjorn Sandstede, and Ritambhara Singh. Scotv2:
Single-cell multionic aligument with disproportionate cell-type representation. Journal of Compulational Biology, 29(11):1213-15 1228, 2022. (Cited on p. 2)
Ishan Deshpande, Yuan-Tim Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander G Schwing. Max-slicod wasserstein distance and its use for gans. In Proceedings of the IEEE/CY /CVF Conference on Computer Vision and Pattern Recognition, pp. 10648-10656, 2019. (Cited p. 2, 10)
15

---

Published in Transactions on Machine Learning Research (12/2024)
Richard Mansfield Dudley. The speed of mean gelvenko-cantelll convergence. The Annals of Mathematical Stalistics, (0(1):40-50 50, 1969. (Cited on 2)
Kilian Fatras, Younes Zine, Rémi Flamary, Remi Gribonval, and Nicolas Courty. Learning with minibatch wasserstein asympiotic and gradient properties. In Silvia Chiappa and Roberto Calandra (eds.), Pro- ceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2131-2141, Online, 26-28 Aug 2020. PMLR. (Cited on p. 2)
Kilian Fatras, Thibault Sejourne, Rémi Flamary, and Nicolas Courty. Unbalanced minibatch optimal trans- port; applications to domain adaptation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3186 3197. PMLR, 18 24 Jul 2021. (Cited on p. 2)
Sira Ferradans, Nicolas Papadakis, Julien Rabin, Gabriel Poyré, and Jean-François Aujol. Regularized discrete optimal transport. In Scale Space and Variational Methods in Computer Vision, pp. 428-439, 2013. (Cited p. 12)
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Alaya, Aurélic Boisbunon, Stanislas Cham- bon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, el al. Pot: Python optimal trans- port. The Journal of Machine Learning Research, 22(1):3571-355 2021. (Cited on p. 12)
Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd international conference on artificial intelligence and statistics, pp. 1574 1583. PMLR, 2019, (Cited on p. 30)
Ziv Goldfeld and Kristjan Greenewald.
Sliced mutual information: A scalable measure of statistical depen- dence. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 17567-17578. Curran Associates, Inc., 2021. (Cited on p. 2)
Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In International Conference on Machine Learning, pp. 1263-1277 PMLR, 2016. (Cited on 11)
Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized sliced wasserstein distances. Advances in neural information processing systems, 32, 2019. (Cited on p. 2)
Stanislav Kondratyev, Léonard Monsaingeon, and Dmitry Vorotnikov. A filness-driven cross-diffusion system from population dynamics as a gradient flow. Journal of Differential Equations, 261(5))2784 2808, 2016. (Cited on p. 2)
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document dis- tances. In International conference on machine learning, pp. 957 966. PMLR, 2015. (Cited on p. 11, 12, 37)
Simon Lacoste-Julien and Martin Jaggi. On the global linear convergence of frank-wolfe optimization variants. Advances in neural information processing systems, 28, 2015. (Cited on p. 10)
Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho. On robust optimal transport: Computational complexity and baryeenter computation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 21947-21959, 2021. (Cited on p. 13)
Tam Le and Truyen Nguyen. Entropy partial transport with tree metrics: Theory and practice. In Inter- national Conference on Artificial Intelligence and Statistics, pp. 3835-3843. PMLR, 2021. (Cited on p.
2)
Matthias Licro, Alexander Mielke, and Giusoppe Savaré. Optimal entropy-transport problems and new hellinger-kant kantorovich distance between positive measures. Inventiones mathematicae, 211(():969-111)) 2018. (Cited p. 2, 3, 4, 5, 6, 8, 19, 21, 29, 30, 36)
16

---

Published in Transactions on Machine Learning Research (12/2024)
Suraj Maharjan, John Arevalo, Manuel Montes, Fabio A González, and Thamar Solorio. A multi-task approach to predict likability of books. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 1217 1227, 2017. (Cited on p. 12, 37)
Tomas Mikolov, 1yya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013. (Cited on p. 11, 37)
Kimia Nadjahi, Alain Durmus, Lénaïc Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Simsekli. Statistical and topological properties of sliced probability divergences. In H. Larochelle, M. Ranzato, R. Hadsoll, M. F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, vol- une 33, pp. 20802 20812. Curran Associates, Inc., 2020a. (Cited on p. 5, 6)
Kimia Nadjahi, Alain Durmus, Lénaïc Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Simsckli. Statistical and topological propertics of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802 20812, 2020b. (Cited on p. 2, 6, 24, 32)
Yoshihiro Nagano, Shoichiro Yamaguchi, Yasuhiro Fujita, and Masanori Koyama. wrapped normal distri- bution on hyperbolic space for gradient-based learning. In International Conference Machine Learning, pp. 4693 4702. PMLR, 2019. (Cited on p. 41)
Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Distributional sliced-wasserstein and applications to generative modeling. arXiv preprint ar arXiv22022 27770770007367, 2020. (Cited on p. 2, 10)
Khai Nguyen, Tongzheng Ren, Huy Nguyen, Litu Rout, Tan Minh Nguyen, and Nhat Ho. Hierarchical sliced wasserstein distance. In The Fleventh International Conference on Learning Represendations, 2023. (Cited
on p. 2)
Ruben Ohana, Kimia Nadjahi, Alain Rakotomamonjy, and Liva Ralaivola. Shedding pac-bayesian light adaptive
distances. In Proceedings of the 40th International Conference Machine Learning, 2023. (Cited on p. 2)
Bo Pang, Lillian Lee, and Shivakumar Vaithyanathan. Thumbs up? sentiment classification using machine learning techniques. In Proceedings of EMNLP, pp. 79 86, 2002. (Cited on p. 37)
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, el al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019. (Cited on p. 10, 13)
Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In 2009 IEEE 12th international conference computer vision, pp. 460-467. TEEE, 2009. (Cited on p.2)
Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trendso in Machine Learning, 11(5-6):3555 -355-607, 2019. (Cited on p. 2, 4)
Khiem Pham, Khang Le, Nhat Ho, Tung Pham, and Hung Bui. On unbalanced optimal transport: An analysis of Sinkhorn algorithm. In Hal Daumé IIT and Aarti Singh (eds.), Proceedings of the 37th Inter- national Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. PMLR, 13 18 Jul 2020. (Cited on p. 2, 4, 12)
Benodetto Piccoli and Francesco Rossi. Generalized wasserstein distance and its application to transport equations with source. Archive for Rational Mechanics and Analysis, 211:335 358, 2014. (Cited on p. 30)
Prabhat, K. Kashinath, M. Mudigonda, S. Kim, L. Kapp-Schwocrer, A. Graubner, E. Karaismailoghı, L. von Kleist, T. Kurth, A. Greiner, A. Mahesh, K. Yang, C. Lewis, J. Chen, A. Lou, S. Chandran, B. Toms, W. Chapman, K. Dagon, C. A. Shields, T. O'Brien, M. Wehner, and W. Collins, Climatenet: an expert-labeled open datasct and deep learning architecture for enabling weather. Geoscientific Model Development, 14(1):107-DB 2021. doi: 10.5194/gmm gmd 14- 107-2021. (Cited on p. 13)
analyses of extreme
17

---

Published in Transactions on Machine Learning Research (12/2024)
Julien Rabin, Julie Delon, and Yann Gousscan. Regularization of transportation maps for color and contrast transfer. In International Conference on Image Processing, pp. 1933-1936, 2010. (Cited p. 12)
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its application texture mixing. In Scale Space and Variational Methods in Computer Vision: Third International Conference, SSVM 2011, Ein-Gedi, Israel, May 29-June 2, 2011, Revised Selected Papers 3, pp. 435-446. Springer, 2012. (Cited on p. 2, 4)
Grant Rotskoff, Samy Jelassi, Joan Bruna, and Eric Hunden-Eijnden Global convergence of neuron birth- death dynamics. arXiv preprint
2019. (Cited on p. 2, 8)
Benjamin M Sanderson, Reto Knutti, and Peter Caldwell. A representative democracy to reduce interde- pendency in a multimodel ensemble. Journal of Climate, 28(13):5171-511 5194, 2015. (Cited on p. 13)
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94, 2015. (Cited on p. 19, 23, 29, 31, 34, 35)
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on a tree. Advances in neural information processing systems, 33:19039-19051, 2020. (Cited p.
Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, et al. Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming. Cell, 176(4):928 943, 2019. (Cited on p. 1, 2)
Thibault Séjourné, Jean Feydy, François-Xave Xavier Vialard, Alain Trouvé, and Gabriel Peyré. Sinkhorn diver- gences for unbalanced optimal transport. arXiv preprint 0rXiv:1910.12955 2019. (Cited on p. 21)
Thibault Séjourné, Gabriel Peyré, and Frangois-Xaviee Xavier Vialard. Unbalanced optimal transport, from theory to numerics. XrXiv preprint arXiv:2211.00 1.00775 2022a. (Cited on p. 2, 3, 5)
Thibault Séjourné, Frangois-Xavier Xavier Vialard, and Gabriel Peyré. Faster unbalanced optimal transport: Trans- lation invariant sinkhorn and 1-d frank-wolfe. In International Conference on Artificial Intelligence and Statistics, pp. 4925-5021. PMLR, 2022b. (Cited p. 2, 9, 23, 29, 34)
Stephen Simons. Minimar and monotonicity. Springer, 2006. (Cited on p. 21)
Soulivanh Thao, Mats Garvik, Gregoire Maricthoz, and Mathicu Vrac. Combining global climate models using graph cuts. Climate Dynamics, 59:2345-2388 23661, 2022. (Cited on 13)
Adrien Vacher and François-Xavier Vialard. Semi-dual unbalanced quadratic optimal transport: fast statis- tical rates and convergent algorithm. In International Conference Machine Learning, pp. 34734-34758. PMLR, 2023. (Cited on p. 6)
Jiaqi Xi and Jonathan Niles Weed. Distributional convergence of the sliced wasserstein process. arXiv preprint ar Xfo: 00156, 2022. (Cited on p. 23)
18

---

Published in Transactions on Machine Learning Research (12/2024)
A Postponed proofs for Section 3
A.1 Existence of minimizers: Proof of Proposition 3.2 and Proposition 3.7
We provide the formal statement and detailed proof on the existence of solution for both SUOT and USOT, as mentioned in Section 3.
Proposition A.1. (Existence of minimizers) Assume that C₁ is lower-semicontinuuus and that either (i) f1.00 42..00 = +00, or (ii) C1 has compact sublevels on TR x RR and PL..0 + 122.00 + inf C1 > 0. Then the solution of SUOT(a, 3) and USOT(a, B) exist, i.e., the infimum in (6) and (9) is attained. More precisely, there crists (Ti, which ottains the infimum for USOT(a, B) (see Equation 9). Concerning SUOT(a, 3), there erists for any 0 supp(or) plan ne attaining the infimum in UOT(0 87 (see Equation 2).
Proof. We leverage (Liero el al., 2018, Theorem 3.3) to prove this proposition. In the setting of SUOT, if such assumptions (i) or (ii) are satisfied for (a, 8), then they also hold for 00/a,030 for any 0 E S Hence, U 8) admits a solution T².
Concerning USOT, note that one necessarily has m((11) m(T2), otherwise SOT(MI to0. From (Liero et al., 2018, Equation (3.10)), for any admissible (x1, 22, T) one has
USOT(a, 2 m(r) inf C1 m(a)) (aa) m m(3)p2( (
In both settings the above bounds implies coercivity of the functional of USOT w.r.t. the masses of the measures (M,, T2, TT). Thus there exists M > 0 such that m(x1) = m(T2) = m(x) < M, otherwise USOT(a, B) = +o0. By the Banach-Alaoglu theorem, the set of bounded measures (TI, T2) is compact, and the set of plans π with such marginals is also compact because R' is Polish and C₁ is seiioonniios (Santambrogio, 2015, Theorem 1.7). Because the functional of USOT is sover-semioontiuuus in (T1 72, x) and we can restrict optimization over a compact sct, we have existence of minimizers for USOT by standard proofs of calculus of variations.
A.2 Strong duality: Proof of Theorem 3.5 and Theorem 3.9
Note that the result for SUOT (Theorem 3.5) is proved in Lemma A.4. Thus we focus on the proof of duality for USOT.
Proof of Theorem 3.9. We start from the definition of USOT, reformulate it to apply the strong duality result of Proposition A.2 and obtain our reformulation. We first have that
inf USOT(a, = (BL (R4ga (SOT(T1,T2) T2) + D (mIla) + Des(
sup So4g.SC; /
fad(0?+T)+ + / god(0772)) dox(1)
inf (Bdd)
8d-1
/
(i([(r))da(a)) - / [(x))dT(()))
+ sup FEE(RA)
(3((()))(3()) - / ((w)dtro())
+ sup gEE(2d)
[ fod(0mm))+ + / mz)) dōx(()
inf (m (s
sup S0 Jo
/ (i(((=))daa()) - / f(x)dm
+ sup fEE(RO))
(((0(1))330)) - ((0)dTz(())
+ sup (EE(
19

---

Published in Transactions on Machine Learning Research (12/2024)
where E(R)) denotes set of lover-semicontimoons functions, and the last equality holds thanks to Lemma A.3.
We focus now on verifying that Proposition A.2 holds, so that we can swap the infimum and the supremum. Define the functional
[/ fod(0fm1) + [fodl072))
[(( ((fe)e, (go)e, f.)))
f
god(() dõ dōxx(0)
ga
+ / (il(()))da(z)) - / [(x)dT((x)
/ (((0()))(8(M)
/ ((y)dma(y)
One has that,
For any ((fo)e (g))o:
f. f.9), C is linear (thus convex) and lower-semioontinnons.
For any (T, C is concave in ((o)u, (go) í. because of is concave and thus L is sum of linear or concave functions.
Furthermore, since we assumed that 0 E dom(pp) then
sup
inf L < USOT(a, 8) s (0)m((()) + p2(00)m(3)
((folo.(0o)o.F.. F.)) (M.
because the marginals (T T2) (0.0) are admissible and suboptimal. If we consider instead that (m(a),m(B) dom(p), then we take the marginals म1 = aam((a) and πΣ 3/m(B)) which yiclds an upper- bound by m(a)p11( mm(a)) + mm)))p2(( m)) Then consider anchor dual point b" ((fe)e, (go)e, f.9) to bound L over a compact set. We take fe = O, go = 0, which are always admissible since we take Cr y) 2 0. Then, since we assume there exists p: I in dom(y?), we take pr and ğ = p2. For these potentials one has:
C((TI1T2))b)) = (p))m((() - p1m(m1) + 2 (p2) - p2m((T2.
Note that the functional at this point only depends on the masses of the marginals (III 12). Since (PI, 2 0 the set of (2) such that [((T1, T2), b*) S (0((0))(a) (20)m)) is non-empty (at least in a neighbour- hood of (mi, 72) = (0, O), and that (m(x1), m(T2)) are uniformly bounded by some constant > 0. By the Banach- Banach-Alaoglu theorem, such set of measures compact for the weak topology.
Therefore, Proposition A.2 holds and we have strong duality, i.e.,
USOT(a, =
sup fe e < C E
inf (m..a))EM (R4j² [((TI, m2), ((Jo)o, (g0)a, J.9)).
{
To achieve the proof, note that laking the infimum in (πI, (for fixed dual variables) reads
/ (Jer, fo(o (x))dx dmm(()) - f(x))d((())
inf m0.9920
/ (Js go (O))) (0) dmalw) ) ff ((g)dma(s)
Note that we applied Fubini's theorem here, which holds here because all measures have compact support, thus all quantitics are finite. It allows to rephrase the minimization over Tı, T2 2 0 as the following constraint
JSm, fo(0 2 f(x),
foL (1) (w) (0) 2 g(y),
20

---

Published in Transactions on Machine Learning Research (12/2024)
otherwise the infirmum is -00. However, the function 8 is non-decreasing (see (Séjourné et al., 2019, Proposition 2)). Thus the maximization in (f.ğ) is optimal when the above inequality is actually equality, i.e.,
J (z) f(x), Jon go(( = =(y)-
Plugging the above relation in the functional L yields the desired result on the dual of USOT and ends the proof.
We mention a strong duality result which is very general and which we use in the proof of Theorem 3.9. This result. is laken from (Liero al., 2018, Theorem 2.4) which itself takes it from (Simons, 2006).
Proposition A.2. (Liero et al., 2018, Theorem 2.4) Consider two sets A and B be nonemply conver sels of some vector spaces. Assume A is endowed with Hausdorff topology. Let L A B R be function such that
1. + b) is conver and lower-semicontimnou on A, for every E B 2. b L(a,), b) is concuve B, for every E A.
If there erists b, B and x > suptem infaed L(a, b) such that the set {a A, L(a, b.) < R} is compact in A, then
inf sup L(a, b) sup inf L(a,b)
a bEB
BEBaEA
We also consider the following to swap the supremum the integral which defines sliced-UOT (and in particular sliced-OT). In what follows we note sliced potentials as functions fo(z) with (0,z) E Sd-1 x R, such that
SUOT(a, B) = 8) = sup 100gssc
Sod00a(())))+ + / 4" god dō (0)
Sod(Oja)
Note that with the above definition, 2 ++ Sa(z) continuous for any 0, but 0 - fo(=) is only ā meaasuuueblle. Lemma A.3. Consider two sets X and Y, a mensure a such that oX) +o0. Assume Y compact. Consider a function X Y + Assume there exists sequence (yn) in Y such that F(,ya) supyey F(,y) uniformly. Then one has
sup / F(z, v)) vEY
/ sup F(z, y))((). weY
Proof. Define G(x) = supyer F(p y) and H(x,y) v) 2 G(x) - F(x, One has H. 2 by definition, and the desired equality can be rewritten
sup / F(a, F(I,))do(x)) f sup F(x, ()do()) yeY
yEY /
wEY inf / H(x, (z)
Since the integral involving H. is non-negative, the infinum zero and only if we have a sequence (yn) such that fx H(: yn )do -> 0. By assumption, one has F(., yn) - sup,ey F(. y) uniformly, ú.e., ||H((, yn)ll -> This implics thanks to Holder's incquality that
0 5 / M(s.n)de S { Br)
21

---

Published in Transactions on Machine Learning Research (12/2024)
Thus by assumption one has fx F(: Vn)do - fx Gdo, which indeed means that have the desired permu- tation between supremum and integral.
Lemma A.4. Let p E [1, +oo) and assume that Ci -x - Consider two positive measures (ax, B) with compact support. Assume that the measure ōK is discrete, i.e., ōx t E ôø, with 0; E gd-1, == 1.....n. n. Then, one can swap the integral over the sphere and the supremum in the dual formulation of SUOT, such that
J I 00 fod(0fa) / x0 god
SU)T(a,
sup feev SC,
( dāx(())
In porticular, this result is valid for SOT.
Proof. The proof consists in applying Lemma A.3 for (X,Y) chosen as X supp(ok) c Sd-1 and
Y = (40 E supp(ōx), fo R + R, R + R, fa(œ) go(v) S Ci
The functions in Y are dual potentials, and by definition are continuous for any 0. Let F XXX + R be the functional defined as
F: (fooo foo((faa) god(0)3).
Since the measures (a. have compact support, then by Lemma A.5, the supremum is attained over subset of dual potentials of Y such that for any fixed 0 E X, (Se, go) are Lipschitzzcontinooor and bounded, thus uniformly equicontinuous functions (with constants independent of 0). By the Ascoli-Arzela theorem, the set of uniformly equicontinoous functions is compact for the uniform convergence. Hence, for any 0 E X, there exists sequence of dual potentials (fo.n. n0.n) which uniformly converges to optimal dual potentials (fo. (o) (up to rxcticn of subsequence). Besides, we have OT(Oaa, 02.3) F(0, fo. go) and F(0, (Jo,n)o (ga,n)a) OT () n + +oc. Denote (0) A F(0, (fe.n)o (go.n)o) and OT(#) & OT(#7a, 87.). In order to apply Lemina A.3, we need to prove that the convergence of (F)()) to OT(03a, a 07 B) is uniform w.r.t. 0, i.e., supoex (0) OT(Ø)) + as n +00.
First, note that for any X,
FF - OT(0)) N m(a)llJo,, - Solloo + m(3)llgo,n - go lla.
Since for a fixed A E X, (fe. nen uniformly converge to (fe.ga): this means that
vO E X, Ve 0 3N(e,0), 0) Vn N(e,0), m(a)llSo,. sallx + m())lggon - loo < E.
Since we assume that is supported on a discrete set, then the cardinal of X finite and one can define N(e) & maxaex N(e, This yiclds,
Ve 0,00, 0, EN(E), Vn 2 N(e), sup (F, - -T((0) < oex
which means that supsex (0) OT(O)) + 0, thus concludes the proof.
Lemma A.5. Let p E [1, +00) and C, C1 (z. - y/P. Consider two positive measures (a, (Rd) whose support such that Ca(a.y) = I 1--- generality the problem UOT(B; 3) as supremum over dual potentials satisfying fo(x)+go(v) S Ci(x,)) v), uniformly bounded by M and uniformly T.-Tipschitz, where M and L do not depend 0.
bl S R. Then for any 0 E gd-1, one can restrict without loss of
22

---

Published in Transactions on Machine Learning Research (12/2024)
Proof. We adapt the proof of (Santambrogio, 2015, Proposition 1.11), and focus showing that the uniform boundedness and Tipschitz constant are independent of 0 E 86-1 in this setting. Here we consider the connslationinvaaiian
formulation of UOT from (Séjourné et al., 2022b), i.e., UOT(a, 9) = seysc H(f.9) g), where H(f.g) g) = supeeR D(f + X, g - A). It is proved in (Séjourné et al., 2022b, Proposition 9) that the above problem has the same primal and is thus equivalent to optimize D. By definition one has H(S.9) = H(f + g - A) for any À E R, i.e., this formulation shares the same invariance as Balancod OT. Thus we can reuse all arguments from (Santambrogio, 2015, Proposition 1.11), such that for UOT(a, B), one can use the constraint f(x) + ( & y) and the assumption Ca y) I R to prove that without loss of generality, can restrict to potentials such that f(x) e [0, R] and g(v) E [ R. Rj. Furthermore if the cost satisfies in gd
Ca(a,,)) Ca(a', s')l S E[||= - z'1l 11y Il).,
then one can also restrict w.l.o.g. to potentials which are L-Lipschitz. For the cost Ca(z. y) = || y/I with p 2 1, this holds with constant == pRP-1 because the support is bounded and the gradient of Ca is radially non-decreasing.
Regarding (f 073), the bounds (Ms Le) could be refined by considering the dependence in 0 E s However we prove now these constants can be upper-bounded by a finite constant independent of 0. In this setting we consider the cost
(1(0))), = (0,
10. - 12 ||011||2 vll S | v11",
by Cauchy-Schwarz inequality. Therefore, if (a. have supports such that ||. vll R, then ( also have supports bounded by R in R. Similarly note that the derivative of h(x)) = xx is non-decreasing for 2 1. Hence the cost C₁ (0*(),,, 0 (v)) has bounded derivative, which reads
pl (0, x v) p-1 1|0011~11|> v11=-1 s p/æ -111-1 S PR
Thus on the supports of (8ja, 8) one can also bound the Lipschitz constant of the cost C1 v) |r w/2 by the same constant L.
Remark: Extending Theorem 3.9. We conjecture that Theorem 3.9 also holds when or is the uniform measures over gd-1, since the above holds for any N E No and σN converges weakly* to a. Proving this result would require that potentials (fa.ge) are also regular (f.e., Lipschitz and bounded) w.r.t 0 E gd-1, This regularity is proved in (Xi & Niles-Weed, 2022) assuming (a, 3) have densities, but remains unknown for discrete measures. Since discretizing corresponds to the computational approach, assume it to be discrete, so that no additional assumption than bouneddness on (a, is required. For instance, such result remains valid for semi-discrete UOT computation.
A.3 Metric properties: Proof of Proposition 3.3 and Proposition 3.8
Proof of Proposilion 3.3. Metric properties of SUOT. Symmetry and non-negativity are immedi- ate. Assume SUOT(a, 3) = 0. Since o is the uniform distribution on gd-1, then for any 0 e Sd-1 COT 9) 0, and since UOT is assumed to be definite, then 0/a = 033. By (Bogachev & Ruas, 2007, Proposition 3.8.6), this implies that a and have the same Fourier transform. By injectivity of the Fourier transform, conclude that a B, hence SUOT is definite. The triangle inequality results from applying
-
23

---

Published in Transactions on Machine Learning Research (12/2024)
the Minkowski incquality then the triangle incquality for UOT for p too): for any a, 3,3.y M+
/UOT)/((aB)))
(1o.. (00(00a.003))do000)
1/8
1/P
(gm.. ga-1
[UOT 077) + UOT UOT (11))
((,)) "(,,
1/8
1/2
[UOTT/P(OTa 0(>)) (do(0))))))) + (0030
Proof of Proposilion 3.8. Metric properties of USOT. Let (a, 3) E (Rd).. Non-negativity is imme- diate, as USOT is defined as a program minimizing a sum positive terms. SOT is symmetric, thus when F1 = 922, we obtain symmetry of the functional w.r.t. (a,3). Assume D definite, í.e., Dz(a]3) 0 implies a B. Assume now that USOT(a, 3) 0, and denote by (T1, the optimal marginals altaining the infimum in (9). USOT(a, B) 0 implies that SOT(11, #2) 0, D2(())a)= 0 and (x2 0. These three terms are definite, which yields गI T22 B, hence the definiteness of USOT. The Partial OT setting (i.e., D& pTV) is treated in Appendix A.7.
A.4 Sample complexity: Proof of Theorem 3.4
Theorem 3.4 is obtained by adapting (Nadjahi et al., 2020b, Theorems 4 and 5). We provide the detailed derivations below.
Proof of Theorem 3.4. Let 9) E M x M with respective empirical approximations á, 3, over n samples. By using the definition of SUOT, the triangle inequality and the assumed sample complexity of UOT for univariate measures, show that
SUOT(a, SUOT( SSUTTO,))-UUOT(Aa....) B.)
(15)
= Soa.1 {UOT(O;a, 033) UOT((;;á, (do(())
(16)
|UOT(E;a, 07 - UOT(f;a,, (,
(17)
gg
E|UOT(OE 033) UOT 07 (d)
(18)
(())do(0) x(n).
(19)
which completes the proof for the first setting.
Next, let E M with corresponding empirical approximation án Then, using the definition of SUOT, the triangle inequality (w.rtt. integral) and the assumed convergence rate in UOT,
(S a)l
(20)
UOT(O;á,, (a) < E {Le U aa)) (0)
(21)
BUUTT an, 0a) do) S { ((n)do E(n)
(22)
24

---

Published in Transactions on Machine Learning Research (12/2024)
Corollary A.6. Assume for μ (R))), BIUOT(H, An)) I E(m) and that for p 2 1, UOT satisfies non-negativity, symmetry and the triangle inequality on M (R) x (R). Then, for a, E M (R*).
E
-
22(n)"
(23)
Proof. Since UOT!/P satisfies non-tegativity, symmetry and the triangle inequality on MM x (R),
SUOT verifies these three metric propertics on (IRS) x (RR)) by Proposition 3.3, and we can derive its sample complexity follows. For any a, B in M+ (RR) with respective empirical approximations åz. Br, applying the triangle inequality yields for p E [1, +00),
(UOT""(a, -Urr/ 3n) I UOT /OT U0
(24)
Taking the expectation of (24) with respect to án, Pn givos,
E B) () SUOT )w)
a) (
(25)
[E [B)SUOT(án,a)) 1/ (E)
(26)
{(n) E(n)) -(m))/p-2((()) //
(27)
where (26) is immediate if p = and results from applying Hölder's inequality on sd-1 if > 1, and (27)
follows from (22).
A.5 Comparison of SUOT, USOT, SOT, and proof of Theorem 3.10 and Theorem 3.11
In this section, we establish several bounds to compare SUOT, USOT and SOT on the space of compactly- supported measures. We provide the detailed derivations and auxiliary lemmas needed for the proofs. The Partial OT setting (f.e., D2 PTV) is treated in Appendix A.7.
Proof of Theorem 3.10. Theorem 3.10 is a direct consequence from Theorems A.7 and A.8.
Theorem A.7. Let (a, 8) E (R*) x (R4). Then, SUOT(a, B) < US)T(a,
Proof. To show that SUOT B) < USOT(a, 5), we use sub-optimality argument. Let be the solution USOT(a, B) and denote by (T) the marginals of For any O Sd-1, denote by To the solution of OT(O)m ()))). By definition of USOT, the marginals of my are given by (0 02))) Since the sequence (TT)e is suboptimal for the problem SUÓT(a, 9), one has
Joh-1 ( 1f CadTo + Da, (0 + D,,
SUOT(a, 8)
(28)
< [ /
CidTodo (0) + (m/(a) + (p2((1)))
(29)
184-1 US),(a;
(30)
where the second inequality results from Lemma A.10, and the last equality follows from the definition of USOT(a,
Theorem A.8. Let 3) E (RdR x (Rd).. Additionally, let E (00+ and assume that for all 2, Edd d 1d-1 (1)) & C)(x,y). Then, USOT(a, B) s UOT(a,
Proof. By (Bonnotte, 2013, Proposition 3.1.3), SOT(p,,) 2) < * as C₂ (8* 0* (v)) I Calo, v) for all y, Rdd e Sd-1 Let be the solution of UOT 8) with marginals (T,, π2). These marginals
25

---

Published in Transactions on Machine Learning Research (12/2024)
sub-optimal for USOT(a, 3), we have
USOT(a, B) z SOT((1. T2) + D,, (T]aa) + p,, (T213),
(31)
( + +D (T| + pa (T2
(32)
UOT B),
(33)
where the last equality is obtained because и is optimal in UOT(a,
Proof of Theorem 3.11.
Theorem A.9. Let X compact subset of Rd with radius and consider at MX) Additionally, p e +x)) and assume Ci (x, y) = I 15--y y|P for (x.y) E R and Ca(a, = || yll for (x,y) E IRd. Let p > and assume Dy, D2p pKL. Then, UOT(a, 8) eSUOT(a, 3) where c c(m((),, R) is non-decreasing function of m(a) and m(3).
Proof. We adapt the proof of (Bonnotte, 2013, Lemma 5.1.4), which establishes bound between OT and SOT. The first step consists in bounding from above the distance between two regularized measures.
Let vb Rd + R+ be smooth and radial function such that supp( C Ba(O, 1) and J&s v(z)dLeb(r) = 1. Let (x(2)) A (z/AA) For any function defined Rº (s 2 1), denote by F[J the Fourier transform of f defined for E R' as F(f((z) = fR- -i(,a)) dw. Let aą a 4p and Bx = 3 µp where is the convolution operator. Let (f.g) such that f ( S Ca. By using the isometry properties of the Fourier transform and the definition of thx, then representing the variables with polar coordinates, we have
| 40 (f())ddaa) = [ Flo ((w))
(34)
- fore Fip [((o))=aa((+))////\/))))>>> drde.
(35)
Since 8º of f is real-valued function, Flyo f] is function, then
/ AA 9 (f(x))ddaxx))
(36)
Flø [|10000FT(((1100111111111111
(37)
2 Jgu JR
= 2 ga-1
Fly? o (1000)
(38)
gga-1 [ Fli o (110 ( n
- (0t-rr00aa())) ((
Flu)) 1m| drdo
(39)
ga-- / Uga (Fal R x ((())) a0 Flo |r| |r dxdrdd
(40)
Equation 38 follows from the property of forhadorward measures, (39) results from the definition of the Fourier transform and и E [-R, Rj, and (40) results from the definition of the Fourier transform and Fubini's theorem. By making a change of variables (æ becomes x - -u0), we obtain
f 00 (f(x))daxxz) Rd
(41)
R
(f(x-- ut))e (r((,,) (0; -1 |-( dædrd0
(42)
gd-1 JR. Rdd -
{
J ('(((x u0) u ir 10 -00 |r| dxddrd0
R
(43)
2 ga
26

---

Published in Transactions on Machine Learning Research (12/2024)
where (43) follows from supp(a) S Ba(O, Indeed, this implies that supp(ax) _ Ba(0, R + X), thus the domain of x + 4 o f(x ud) is contained in (0, 2R + A).
Similarly, one can show that
Jec ((((())))811))
(44)
R (0(( ud))e -0 - d0, |r| ( dydrd0.
1
(45)
2 18--1 (2)
By (43) and (45), obtain
J
Rd le ((()))doo(x)++ / ('((()))3330)))
(46)
[1 R q (00)dd0(((u))
JAJBAO2RHNN 2 gg
-R
St
4' 5g(g( w0)) 3(w) e (1 1r| dodrd0,
(47)
n
and,
1 B1(0.2RHA)
{1=0
R 40 (f(x (d))) + / (0((x w0)) B(v) -i e
(48)
UOT 0f B)]e -i)(0 dd
(49)
{.(00,2+ < (2R X) 03))
(50)
where (49) is obtained by taking the supremum of (48) over the set of potentials (f g) such that for E [-R, R), 3(x, 0) O0 2R + X) x gd-1,
f(z - ud), ğ(u) g ud), which is included in the set of potentials (f", g') s.t. f R + R. g' R - R and f a g' & Ct. Therefore.
[ 4 (f())daxx1)
/ (((()))))))))
Rd
UOT(Ø (0aa,003000 ()) / A 11 ldr s c(22 2)dx 3)
< 1 ( 1)a
A A(S
(51)
2
98-1
(52)
where c 1-((-11))) fg Fivl(r) b- dr. We doduce from the dual formulation of UOT (3) and (49) that,
3x) 3
(53)
The last step of the proof consists in relating UOT(a,, Bx) with UOT(a, For any (f.g) such that f 2 S Ca. we have
[ p (f()))da())+ ( 6e (c(e))))(()) - UOT(ax,82)
(54)
[ ((((=))da(()) ((((())))3()) - [ (((()))dax())) - / ((()))))1))))
(55)
/ (+'(((x)) dx ( / (g0())))) dx * (((66)))))
(56)
27

---

Published in Transactions on Machine Learning Research (12/2024)
For R",
(f((())) vx (f(x))) = = { ( (f((v)))
y
dy
(57)
Rd
A
S _- J (f((())) (2(S(1))]
dy ,
(58)
Since D& pKT,, then for E RR (0() = (1 e - so for (x, TRdd Rd
('((x)))- - (f(()) p(e (itv// - - ((2)/P)
(59)
By Lemma A.13, the potentials (f,g) are bounded by constants depending on mla).m(B)) Therefore, we can bound (59) as follows.
(f(x))
(60)
We thus derive the following upper-bound on (58).
('((())) - s/a & (f(x)) S x x -1/0 { ||x - - 1/
dy
(61)
S 110 yl *b
S x
-x exxi1
y
dy
(62)
By doing the change of variables 2 (y z)/A and using the fact that up is a radial function, we obtain
('([(z)) x x0 (f(z)) de 1010 / (=)l0(z)d2.
(63)
Similarly, using the bounds on g in Lemma A.13, show that
(x'()()) - (u(())) S c(A*+B//lll yll
(64)
therefore,
(g((()) 2b x (g(x)) s Ae(A'+R1/0 / |1]lv(2)dzz
(65)
We conclude that,
J&c 4 (f()))a((z) + / x ('((v)))(()) - UOT(a,, Bx) I (o-2%/0 + +B/+))))) XM)
(66)
where (1)) A Jge (z)d2 Taking the supremum on both sides over (f,g) such that f f g S C. yiclds,
(OT(a, UOT(ax, Bx) S (e-x/le ca' mm/+) AM)
(67)
Finally, by combining (53) with the above inequality, we obtain
UOT(a, B) (e xx clx++ AM, (v) (+) + c(22+ -duoT_((
(68)
$ <di(1 + (2R + 1) (4+))UOO((a..))
(69)
where d' is a constant satisfying d' 2 c and d 2 (e + +R/00 M2()). By choosing À (, (69) becomes
UOT(a, 3) S c' C (d4+)) (1 ( R)²RT4)
(70)
We conclude using that SUOT(a, 3) is bounded from above. Indeed, SUOT(a, B) S p(m(a) + m(5) since on the one hand, π is suboptimal in (3) thus UOT(a, 3) < p(m(a) + m(3)), and on the other hand, m(a) = a() for any e sd-1, This yields X < Rd/(d+1) p( ((T(tl)) ( (/((+)) hence
UOT(a, B) s c(m(a), m(), p. R)SUOT(a, (9) ((d+1)
(71)
where c(m(a), (3), p. R) is non-decreasing function of m(a) and m
28

---

Published in Transactions on Machine Learning Research (12/2024)
Additional Lemmas.
Lemma A.10. For any 0 E gd-1 and a, (R(),, (2(0Fal0;3) s Do(a))).
Proof. For a, M+*(R) with s 2 1, the dual characterization of p-divergences reads (Liero et al., 2018,
Theorem 2.7)
[ (f(x)))33(2) - -fe f(z)da(x),
()(a =
sup fEE(R))
where E(R² denotes the space of lower semi-continuous functions from R to RU [+oo]. Therefore, for any gá-1 and a, B E MM
sup & (110))((33310) -fa000--111 ((0)((0))())) fEE(B) J
()(00a(078)=
(72)
RR.. 3f g=fo0- J ()((=))))) J g(x)da(xx)
(73)
where (73) results from the definition of push-forward measures. We conclude the proof by observing that the supremum in (73) is taken over subset of E(R)).
Lemma A.11. (Sanlambrogio,, 2015, Proposilion 1.11) Let [1, +oc) and assume Ca(o, | y ull.. Let a, 3 with compact support, such that Ca(z, v) S RD for (x,z) supp(a) x supp(3). Then without loss of generality the dual potentials (f.9) of (OT 3) satisfy f(x) E [0, R) and g(y) E R-
Lemma A.12. (Séjourné et al., 2022b, Proposition 2) Define the translation-ineerrinn dual formalation
/ pilf - A)da + / 1vilo- 1o00--aac A)dBB
UOT sup C0 XER
(74)
Let > O and assume De, = Do, = PKL. Take optimal potentials (f.g) in (74). Then optimal potentials in (3) are given by (ʃ + X (f.g)) - (({gg)), where the optimal translation X reads
1 gff
2 (566)~$;00)) Sg(f) & -plog / e-SiPda,
and we call (f) the soft-minimum of f. When m(a) =1 and m S f(x) M, then m Sg)(f) $ M.
Lemma A.13. Assume (a, 3) have compact support such that, for (x, E supp(a) x supp(3), C(r, v) S R. Then, without loss of generality, one can restrict the optimization of the dual formulation (3) of UOT((a B) over the set of potentials satisfying for (x.1) supp(a)) supp(3),
f(x) E 1 + R), g E -- R R)
where X* El-R+ log m(a) R
+ & log m(a) In particular, one has
m(D)
2
f(x) E [-R & log m(a) 3R
log m (a)
g(v) E [- 3R - log
m(a) m(3)
2R m(n) & log (B]
(3
Proof. Consider the translation-invariian dual formulation (74): (Jsg) are optimal, then for any À E R, (f+ g--g-A.0 A) are also optimal. We leverage the structure of the dual constraint f S C2 with Lemma A.11. Since for (x, v) E supp(a) supp(3), Ca(æ, y) S R, then without loss of generality, f(x) [0, R] and g()) E I-
R. R). The potentials (f.g) are optimal for the translation-imvarian dual energy, and we need a bound for the original dual functional (3). To this end, leverage Lemma A.12 to compute the optimal
29

---

Published in Transactions on Machine Learning Research (12/2024)
translation, such that (f.9) = (f Let a/m(() and 3 3/m((B) be the normalized
probability measures. The translation can be written as,
= 1 $/100 - (5)0) 2
+ log m(a)
(f
(75)
2 m(3)
where the functional S defined Lemma A.12. Since ā and 3 are probability measures, then by (Genevay et al., 2019, Proposition 1), f(x)) E [0, R) and g(x) E [-R, R] respectively imply (f) [0, R) and ()) e [-R, R). Combining these bounds on (f), (g) with the expression of (f (75) yields the desired bounds the optimal potentials (f.g) of the dual formulation (3).
A.6 Metrizing weak* convergence: Proof of Theorem 3.12
The Kullback- Leibler setting is treated here. The Partial OT setting (i.e., D2 pTV) is treated in Ap- pendix A.7.
Proof. Let (ax) be a sequence of measures in M+ (X) and a E (x),), where C Rd is compact with radius R > 0. First, we assume that an a. Then, by (Liero al., 2018, Theorem 2.25), under our assumptions, On a equivalent to lim UOT(an, a)
This implies that lim SUOT(an, a). = and 1oo USOT(an, a) = 0, since by Theorem 3.11 and non-negativity of SUOT (Proposition 3.3),
0 ss SUOT(an, a) S USOT(an;a) S UOT(an,
Conversely, assume either that lim SUOT(an, a) = or lim,-++00 USOT(a,, a) 0. First assume there exists > such that for large enough n N", N" m(aa)) I M, then by Theorem 3.11, there exists > such that (OT ax) I c(SUOT(a, a)) Since is doesn't depend the masses (m(a,), m(a)). it does not depend on By Theorem 3.11, it yields metric equivalence between SUOT, USOT and UOT, thus lim UOT(an, = O. By (Liero et al., 2018, Theorem 2.25), we eventually obtain o,, a, which is the desired result.
The remaining step thus consists in proving that the sequence of masses (m(an))nex- is indeed uniformly bounded by M > for large enough n. Note that for any (a, E M_(Rd), one has (a, 3) Z pl p()m(() y m( Indeed one has UOT(a, 2 P(A,-X) where D denotes the dual functional (3) and A = f log mla)
m(ž). Note that the pair (A, -X) are feasible dual potentials for the constraint f fgg S Ca, because the cost Ca is positive in our setting. The property of fush-forwards measures means that for any 0 Sd-1 one has a( = m(a). Therefore, we obtain the following bounds for large enough.
{ USOT(an, a) SUOT(Ua,, a) 2 Iga-1 -Vml0jan)- mm(raa)) do)
pl p(v (m(ma))))))))))))))))()))) vm(a))3
Hence, lim SUOT(aa, a) = or lim USOT a) = 0 implies lim m(a,) m(a). In other terms the mass of sequence converges and is thus uniformly bounded for large enough n. Since we proved that m(a,) < M and m(a) is finite, it ends the proof.
A.7 Properties of sliced partial OT
We provide in this subsection the proofs of Proposition 3.3, Theorems 3.11 and 3.12 for the setting of sliced partial OT. To this end, we rely on a formulation for SUOT and USOT when D D'p = pTV, which we prove below. Equation 76 is proved in (Piccoli Rossi, 2014) and can then be applied to SUOT: we include it for completeness. Equation 77 is our contribution and is specific to USOT.
30

---

Published in Transactions on Machine Learning Research (12/2024)
Lemma A.14, Let p and assume De1 D22 pTV and Ca(a,y) || vll- Then, for ony ( (RR)),
UOT(a, sup / JEE
f(z)d(a- -3)l))))(()))
(76)
where & {f Rd
R, Ilfllzpp
1, llflle I p), llo suPzERd [f(x)] and Il
[ suD(E,))ER' Ca(z.y)
Furthermore, for Cz(2, = x - yl and an empirical approzimation &N = t Ei= d0, of a one has
USOT(a, sup / (Jgn, fo fo(0 (z))do d(aa (()))))z))
(77)
(0)
where
(40 E supp((xx) So TR + RR 1ioollep 1 11 l So o f S s}:
and the Lipschitz norm here is defined w.r.t. C₁ as lIfllci (u
f(a)-f(M) C1(3))
Proof. We start with the formulation of Equation 3 and Theorem 3.9. For USOT one has
/ (i (8i(/g fo(0 (o)d(x))) (o))da()))) da(a))
sup (o()) USOT(a,8)=
+ / 108 188 ga- go(0 (0((())) dB(y).
When D. = PTV, the function 80 reads (x) for x E l- (x) p when x 2 and (x oc otherwise. Noting fang(2) fg- (z)))ooN))) and Goog (x) = fg--1 go (0* No)))) This formula on io imposes favg(z) 2 -p and (x) 2 -. Furthermore, since we perform a supremum w.r.t. (fargs Javg) where 4p attains a plateau, then without loss of generality, we can impose the constraint Ta)g(x) S p and Jaog (x) 2 p. as will have no impact on the optimal dual functional value. Thus we have that [| S p and ||gangloo
p. To obtain the Lipschitz property, we the constraint that fo(-) go(-) S C1 for any 0 E supp(oN)) as well as (Santambrogio, 2015, Proposition 3.1). Thus by using e-transform for the cost C1 v) = |x yl. we can take w.l.o.g fo(-) = -o(() with fo(-) 1-Lipschitz function. Thus w.l.o.g we can perform the supremum over (Jo)s E E, and rephrase the functional as desired, since we have that o (farg) = =avg- favg-
The proof for UOT is exactly the same, except that our inputs are (f.g) instcad of (fe. go).
We can now prove Proposition 3.3, Theorems 3.11 and 3.12 in the setting of sliced Partial OT. All those results are summarized in the following statement.
Theorem A.15. (Properties of Sliced Partial OT) Assume Ci y) = |æ yl and Dj, = D = pTV. Then, USOT satisfies the triangle incquality. Additionally, for any (a, E M+(X) where Id is compact with radius R, UOT(a, B) c(p. R) SUOT () ((d+1), and USOT and SUOT both metrize the weak" convergence.
31

---

Published in Transactions on Machine Learning Research (12/2024)
Proof of Sliced Partial OT properties. First prove that in that setting USOT is a metric. Reusing Lemma A.14, we have that for any measures (a,, (, / (Joc so(0 fo(0"()))dan (x))dax ]d(a - (z)
sup USOT(a,n)=
(fa)aEE
(frr fo(0)())) (x))dox )a(a- - (x)
sup (f))EE
/ (o sol0 Jo(o )d(a- - (x)
sup (fO)EE
(Vo.. 5o (o(0)))ooo )alooo)))33 Jd(3-7)(0) 7x())
+ sup (SO)DE
US) USOT(3,7).
Note that reusing Lemma A.14, we have that SUOT is a sliced integral probability metric over the space of bounded and Lipschitz functions. More precisely, we satisfy the assumptions of (Nadjahi et al., 2020b, Theorem 3), so that one has UOT(a, S c(, RYSSUOT(a ())
To prove that USOT and SUOT metrize the weak* convergence, the proof is very similar to that of The- orem 3.12 detailed above. Assuming that an - implics SUOT(an, a) - 0 and USOT(a,, a) - 0 is already proved in Appendix A.6. To prove the converse, the proof is also the same, Ée., we use the property that SUOT, USOT and UOT are equivalent metrics, which holds as we assumed that supports of (a, 8) are compact in ball radius R. Note that since the bound UOT(a, 3) & dp, R)SSUOT(a, 3)) holds independently of the mcasure's masses, we do not need uniformly bound m(aa), compared to the KI. setting of Theorem 3.12.
B Additional details for Section 4
B.1 Postponed Proofs for Section 4
Proof of Proposition 4.1. Our goal is to compute the first order variation of the SUOT functional. Given that SUOT(a, B) Iga- UOT(@ (f)), one can apply Proposition B.1 slice-wise. Since measures are assumed to have compact support, one can apply the dominated convergence theorem and differentiate under the integral sign. Furthermore, the translation-invariann formulation in the setting of SUOT reads
/ 00 (fo()) + >2 d0;a
sup SUOT(a, 3) Iga- SC,
sup ADER
(78)
f 10 (10() 12o0->oo000 (l0003
(79)
In the setting where 8p is smooth and strictly concave (such as Do = pKL), there always exists a unique optimal Ag- Furthermore, one can apply the envelope theorem such that the Fréchet differential w.r.t. to a perturbation (ro. so) of (fo. go) reads
X Vip [S [Ta()
X5(Fe, 90) d0īa
(80)
+ #(00() x V (mn()) - >ā 90) do33
(81)
Setting
as V (1o()) x1 ((0080
:o= V
=0=V40 v x'(fo. (0)
32

---

Published in Transactions on Machine Learning Research (12/2024)
yields the desired result, i.e., the first order variation is
J [/ [o())d(0(aa)++ + f so(-)d(()BB))
(82)
Proof of Proposition 4.2. Our goal to compute the first order variation of the USOT functional. First, we leverage Theorem 3.9 such that USOT reads
/ 19 ( Jo-
sup (e())ss()))
fol0 (=)) da(x)
(83)
+ I 96 ( g0(000000000)) ((0)))))xx d
(84)
/ si (facg(()) da(x)+ + (d())))))d(((++++))))))))))))))) pم (avgg(())) d
sup (5())s(())))
(85)
where
fz)g(z)= (
Jawg (avg(y)= ( - (v)) (0).
Jga-1 (=))d
From this, we derive the translation-invariant formulation as follows.
/ oi (saeg(z)+ ((oo)+))dad x)da(x) sup sup USOT(a, fe())9o())CC XER
(86)
f 42 ((avoo()) - -x) x)),3)
(87)
For smooth and strictly concave yp, there exists a unique ('faeg. Javg) attaining the supremum. Further- more, one can apply the enveloppe theorem and differentiate under the integral sign (since the support is compact). Consider perturbations (re(-), so())) of (fo))),ge-)). Write
Favg(2) = {
Soog [ Jgh-1 (()
-Sy-11
Given that vilSan + Yang) = (i(snr) + Tang V (Jang) + ([][Vaangl)))) the first order variation reads
/ ravg V fang (I) X3 (Jaugr Fang) da(x)
(88)
+ʃ Sang (1) V Javg (v) - X (farg: Iaog) (d3(y)-
(89)
Then we define
ā == V + X (Jaugs Goog Daog))a
3 Vipggaan X" (Jang (anggggang))) (),g
such that the first. order variation reads
f |reeg (z) fraeg(z)data
(x)dā(z)+ + Soeg (v)
(90)
One can then explicit the definition of (rang: Sang), such that it reads
J ro(0 (x=))a)) + fSan/ / (0(((())))
(91)
{
rod0;a(x)) - ( Jo / sod0)3(y).
(92)
By optimizing the above over the constraint set (re @ se S CiJ, we identify the computation of SOT 3), which concludes the proof.
33

---

Published in Transactions on Machine Learning Research (12/2024)
B.2 Frank-Wolfs methodology for computing UOT
Background: FW for UOT. Our approach to compute SUOT and USOT takes inspiration from the construction of (Séjouréé et al., 2022b). It consists in applying a Frank-Woo (FW) procedure over the dual formulation of UOT. Such approach is equivalent to solve a sequence of balanced OT problems between measures (á, 3) which are iterative renormalizations of (a. While the idea holds in wide generality, is especially efficient. ID where OT has low algorithmic complexity, and we reuse it our sliced setting.
FW algorithm consists in optimizing functional over compact, convex set C by optimizing its lineariza- tion VH. Given current iterate x' of FW algorithm, one computes r*+1 arg max,ee (VH(z'), and performs a convex update x²+1 (1 7++1)= + 7-irr+1 One typically chooses the learning rate = 247' This yields the routine FWStep of Section 4 which is detailed below.
2
Algorithm F.Step([.9.r,8,.7)
Input: a, 8, f, Y
Output: Normalized measures (a, () as (96)
f(z) < (1- (1-7))(x)) -r(z)
s(y) (1-7))g))) 7s(y)
Return (f.g)
In the sctting of UOT, would take C = (f 0g S Ca). However, this set is not compact it contains (A,-X) for any X E R. Thus, Séjourné et al. (2022b) propose to optimise a Iranslation-invaait functional H(f. g; a, 8) A suPxER D(f + g- a; 3), with D defined in (3). Similar to the balanced OT dual, one has H(f + X, a; 8) = H(f.g; a, 8), thus one can apply (Santambrogio, 2015, Proposition 1.11) to assume w.l.o.g. that, e.g., f(0) = 0 and restrict to a compact set functions. We emphasize that FW algorithm is well-posed to optimize H, but not D.
dual
Note that once we have the dual variables (f.g) maximizing H. we retrieve optimal dual variables maximizing D as (f + (f.g).g (f.gg)), where g) & argmaxXeR D(f + X, X; a, B). The KL setting where Dep KT. and D42 KTK is especially convenient, because X (f{gg) admits a closed form, which avoids iterative subroutines to compute it. In that case, it reads
(Se-to)/ddaaaa) (e-
PIP2 log (f
(93)
P1 P1+ + P2
We summarize the FW algorithm for UOT in the proposition below. We refer to (Séjourné et al., 2022b) for more details on the algorithm and pseudo-code. We adapt this approach and result for SUOT and USOT.
Proposition B.1. (Séjourné el al., 2022b) Assume & is smooth. Given current ilerules (f(0) (00gg())))) ()), the linear FW oracle of UOT(a, 3) is (T(a!'), ,,()), where (1)) = (fP(f(()) + x(f(t, (() and B(0) - (f()), ))33 In particular, one has m(a(0) = m(3()), thus the balanced OT problem always has finite value. More precisely, the FW update reads
((1))+ + (1t1 (1(tt))) ((tt))) = (1 - (1(()))(((( (()) (1(++2), s((+1)) g((tt)),(0+1)) E arg max
(94)
((())da"())) (x) + / s(v)d
where
(95)
resSCa
Recall that the in KL setting one has (i(x) = pi(l - -- thus Vpi(I)= = e r/ms normalizes the measures as
Thus in that case one
S (+
99- 8
ā exp
a
B exp
(96)
P1
P2
where X* defined in (93).
This defines the Norm routine in Algorithm 1.
34

---

Published in Transactions on Machine Learning Research (12/2024)
B.3 Implementation of Sliced OT to return dual potentials
Recall from Section 4, Algorithms 2 and and more precisely, Propositions 4.1 and 4.2, that FW linear oracle is sliced OT program, d.e., set of OT problems computed between univariate distributions of (IR. Therefore, key building block of our algorithm is to compute the loss and dual variables of these univariale OT problems. We explain below how one can compute the sliced OT loss and dual polentials. The computation of the loss consists in implementing closed formulas of OT between univariate distributions, as detailed (Santambrogio, 2015, Proposition 2.17). More precisely, when C (z, y) = l - yP and (u, E M+ (R), then
OT(H, [ (1/)"(()) (1)
(97)
where F/-1] denotes the inverse cumulative distribution function (ICDF) of p.
Algorithm SLicedOTLLoss(, B, (0).p)
Input: a, 8, projections {0), exponent
Output: (f of () as (97)
for E {0) do
Project support of 0ça and 0g8
Sort weights (# a, 62 and support (x)),, (v)) s.t. support is non-decreasing
Compute ICDF of 0ea and 8g8
Compute O 8) as (97) with exponent p
end for
To compute dual potentials using backpropagation, one computes the sliced OT losses (using Algorithm 5) then calls the backpropagation w.r.t to inputs (a, (3), because their gradients are optimal dual potentials (Santambrogio, 2015, Proposition 7.17). We describe this procedure in Algorithm 6.
Algorithm 6 S.a.eeddPocerrraaaaaippppolooeae
Input: a, B, projections (0), exponent p
Output: Dual potentials (fo, go) solving 0T(07a,839)
Enable gradients w.r.t. (0) 07
Call Sliced0TLoaa(o, (0),
Sum (but do not average) losses f. L= E, OT(0;a,0;3)
Backpropagate C w.r.t. (a, B)
Return (fe, go) gradients of L w.r.t. (),
The implereentatinn of the dual potentials using 1D closed forms relies on the north-west corner rule prin- ciple, which can be vectorized in PyTTrrc in order be computed in parallel. The contribution of our implementation thus consists in making such algorithm CPU-compatible and allowing for parallel compu- tation for every slice simultancously. We stress that this constitutes non-trivial piece of code, and refer the interested reader to the code in our supplementary material for more details the implementation.
B.4 Output optimal sliced marginals
In all our algorithms, we focus on dual formulations of SUOT and USOT, which optimize the dual potentials. However, one might want the output variables of the primal formulation (See Definition 3.6). In particular, the marginals of optimal transport plans are interesting because they are interpreted as normalized versions of inputs (a, () where geometric outliers have been removed. We detail where this interpretation comes from in the setting of UOT, and then give how it is adapted to SUOT and USOT. In particular, we justify that the Norm routine suffices to compute them.
35

---

Published in Transactions on Machine Learning Research (12/2024)
SUOT USOT
SUOT USOT
SUOT
-25-
USOT
10g opt1)
logu loss opt!
-7%-
11 1: 1.34
M/
-29
-04
Li P4 /M0 MPhh "M
22 number iber
number iter
number iter
Figure 5: (SUOT(a, B) SUOT and JUSOT(a, 33) - USOT, against iteration t, where SUOT,, USOT, are the estimated SUOT, USOT using & FW iterations. Plots are in log-scale. All figures are issued from the same run, but zoomed on a subset of first iterations: (left) 1000 ilerations of FW, (middle) 200 iterations, (right) 20 iterations.
Case of UOT. We focus on the D,, PtKL, As per (Licro et al., 2018, Equation 4.21), we have optimality that the optimal transport n²' plan solving UOT(a, as in (2) has marginals (.i, which read Ti = e /Pl and m² = e- /023, where (f",g") are the optimal dual potentials solving (3). Since on supp(r*) one also has [*(x) + (v) Ca(z,y), if the transportation cost Ca(2, y) is large (i.e. we are matching a geometric outlier), so are (*) and (²)),, and eventually the weights 7ं (2) and (5() are small, hence the interpretation of the geometric normalization of the measures. Note that in that case, one obtain (Ti, mz) by calling Norm(a, f" ,... P2)
Case of SUOT. Since SUOT(a, 3) consists in integrating UOT(@ (53) w.r.t. σ, it shares many sim- ilarities with UOT. For any 0, we consider To and (Jo. ga) solving the primal and dual formulation of UOT 8). The marginals of xa are thus given by (e fe/ a, e 900pp/ In particular, we retrieve the observation made in Figure that the optimal marginals change for each In that case we call for each 0 the routine Norm(a, 3, fo. g0. Pl.P2).
Case of USOT. Recall that the optimal marginals (TI, T2) in USOT 33 do not depend on 6, contrary to SUOT(a, Leveraging the dual formulation of Theorem 3.9, and looking at the Lagrangian which is defined in the proof of Theorem 3.9 (sce Appendix A.2), we have the optimality condition that á = c Sava/// a and
m2 = e ga B. Thus in that case, calling Norm(a, B, Sang Jangs Pl; p2) yields the desired marginals.
B.5 Convergence of Frank- Wolfe iterations: Empirical analysis
We display below an experiment on synthetic dataset to illustrate the convergence of Frank- Wolfe iterations. We also provide insights on the number of iterations that yields a reasonable approximation: few iterations suffices in our practical scttings, typically F 20.
The results are displayed in Figure 5. We consider the empirical distributions (a, computed over respec- tively, N 400 and M 500 samples over the unit hypercube [0, 11 d 10. Moreover, f is slightly shifted by a vector of uniform coordinates 0.5 x 1a. We choose p 1 and report the estimation of SUOT 9) and USOT(a,, 3) through Frank-Wolle iterations. We estimate the true values by rumning F = 5000 iterations, and display the difference between the estimated score and the 'true' values. Appendix B.5 shows that numerical precision is reached in a few tens of iterations. As learning tasks do not usually roquire an esti- mation of losses up to numerical precision, we think that it is hence reasonable to take F 2 20 in numerical applications.
36

---

Published in Transactions on Machine Learning Research (12/2024)
Table 2: Dataset characteristics.
BBCSport
Movies
Goodreads genre
Goodreads like
Doc
737
2000
1003
1003
Train
517
1500
752
752
Test
220
500
251
251
Classes
5
8
2
Mean words by doc 116 = 54
182 + 65
1491 = 538
1491 + 538
Median words by doc
104
175
1518
1518
Max words by doc
469
577
3499
3499
C Additional details on Section 5
C.1 Document classification: Technical details and additional results
C.1.1 Datasets
We sum up the statistics of the different datascts in Table 2.
BBCSport. The BBCSport dataset (Kusner et al., 2015) contains articles between 2004 and 2005, and is composed of 5 classes. We average over the 5 same train/lest split of (Kusner el al., 2015). The dataset can be found in https: /ttes:///tttbt www.///assnn///m////eeeeeeeeeeee
Movie Reviews. The movie reviews dataset (Pang et al., 2002) is composed of 1000 positive and 1000 negative reviews. We take five different random 75/25 train/test /tentttsttre split. The data can be found in http:
//www.cc.cornee..... wtt.:acorrneeeeeeeeeeeeeeeeeeeee http:///epplee/aaba//oreeeeeeeee
Goodrcads. This datasct, proposod in (Maharjan et al., 2017), and which can be found at https: //ritual uh edu/multi, tttttaakbboooo bicck_oook_uueee success _ap___01/////1 is composed of 1003 books from 8 genres. A first possible classification task is to prediet the genre. A second task is to predict the likability, which is a binary task where a book is said to have success if it has an average rating 2 3.5 on the website Goodreads com). The five train/test split are randomly drawn with 75/25 proportions.
C.1.2 Technical Details
All documents are embodded with the Word2Voc model (Mikolov et al., 2013) in dimension d= 300. The embedding can be found in https://dris http:p/////rvvooooooooooo/////// wwt////////////////////////11110 pwwpa//eeeerooooaaaaaaallllttyte
In this experiment, we report the results averaged over 5 random train/test split. For discrepancies which are approximated using random projections, we additionally average the results over 3 different computations, and we report this standard deviation in Table 1. Furthermore, we always use 500 projections to approximate the sliced discrepancies. For Trole based methods, we use 10 iterations, which we found to be enough to have a good accuracy. We added an ablation of these two hyperparameters in Figure 7. We report the results obtained with the best p for USOT and SUOT computed among a grid p E (10-1,5 10-4, 10-1,10-3, 10-3, 3.-3.55- 5. 10-3, 10-3,10 10-2, 101110-1111 13.. For USOT, the best p is consistently around 5. 10-3 for the Movies and Goodreads datasets, and around 5- 14 for the BBCSport dataset. We used second finer grid and reported the results obtained with the genre task. For SUOT, the best p obtained was 0.01 for the BBCSport datasct, 1.0 for the movics dataset and 0.5 for the goodreads dataset. For UOT, we used = 1.0 on the BBCSport dataset. For the movies dataset, the best obtained on a subset was 50, but it took an unreasonable amount time to run on the full dataset as the runtime increases with p (sec (Chapel et al., 2021, Figure 3)). On the goodreads datasot, it took too much memory on the GPU. For Sinkhorn UOT, we used æ 0.1 and p == 1.0 on the BBCSport and & 0.001, p 0.1 the Goodreads dataset, and 0.01 and p 0.1 the Movies dataset. Note
0.00021 on BBCSport,
0.004 for Goodreads the likability task and م 0.003 for
37

---

Published in Transactions on Machine Learning Research (12/2024)
BBCSport
Goodreads
1.5
2.0
Runtime (s)
Runtime (s)
1.5
1.0
o
1.0
0.5
1000
0.5
0.0
0.0
SOT SUOT USOT SUSOT OT
UOT
SOT
SUOT
USOT
SUSOT OT
Figure 6: Runtime on the BBCSport dataset (left) and on the Goodreads dataset (right).
that we also tested other set of parameters for UOT and Sinkhorn UOT, but on a coarser grid than USOT and SUOT given their computational time. For each method, the number of neighbors used for the k-NN method is obtained via cross-validation
C.1.3 Additional experiments
Runtime. We report in Figure the runtime of computing the different discrepancies between each pair of documents, and in Table 3 the full runtimes. On the BBCSport dataset, the documents have average 116 words, thus the main bottleneck is the projection step for sliced OT methods. Hence, we observe that OT runs slightly faster than SOT and the sliced unbalanced counterparts. Goodreads is a dataset with larger documents, with on average 1491 words by document. Therefore, as OT scales cubically with the number of samples, we observe here that all sliced methods run faster than OT, which confirms that sliced methods scale better w.r.t. the number of samples. In this setting, we were not able to compute UOT with the POT implementation in a reasonable time. Computations have been performed with a NVIDIA Tesla V100 GPU.
Table 3: Runtimes on Document Classification
BBCSport
Goodreads
Average (-10-3
3.29
140.30+259
OT
Full (s)
891
221252
Average (-10-3s)
1.80
4.49
SOT
Full (s)
487
2256
Average (-10-93)
14.67+1.29
14.45
USOT
Full (s)
3897
7260
Average (-10-3g)
13.941.21
14.32
SUOT
Full (s)
3770
7193
Ablations. We plot in Figure 7 accuracy function of the number of projections and the number of iterations of the Frank-Woke algorithm. We averaged the accuracy obtained with the same setting described in Appendix C.1.2, with varying number of projections K {4, 10, 21, 46, 100, 215, 464, 1000} and number of FW iterations F' E {1, 2, 3, 4, 5, 10, 15, 20). Regarding the hyperparameter p, we selected the one returning the best accuracy, i.c., = 10 for USOT and = 10-2 for SUOT.
Choice of Table 4, we also add the results obtained when is chosen by cross validation for USOT and SUOT. In this case, the results are slightly below the best one, but are still better than SOT.
we have mentioned in Scction 5, we have performed document classification experiments by normalizing word histograms to be probabilities. It allows to compare SUOT and USOT with SOT since sliced OT is only well-defined between probabilities. However, it seems reasonnable to compare
Unnormalizing measures.
38

---

Published in Transactions on Machine Learning Research (12/2024)
SOT
0.9
Accuracy
0.90
Accuracy
USOT
SUOT
0.8
50T
USOT
SUOT
0.7
0.80
10"
10a
10a
10a
10
15
20
Number of Projections
Iterations FW
Figure Ablation on BBCSport of the number of projections (left) and of the number of Frank- Wolfe iterations (right).
Table 4: Accuracy on document classification. Grid-search over is performed. We report the best accuracy over P, which corresponds to = 5.10-6 for Unnormalized USOT and = 5.10-6 for SOPT.
BBCSport
Movies
Goodreads genre Goodreads like
OT UOT Sinkhorn UOT
94.35
74.44
55.22
71.00
96.73
95.45
72.48
53.55
67.81
SOT
89.39
66.95
50.0910.51
65.60
SUOT
90.12.a.15
67.8 20.33
50. 50.15.0.04
66.72.0.38
USOT SUSOT
93.52
09.21
52.67
67.78+n.39
02.73
69.53
51.93
67.33
SUOT (+CV USOT (+CV 92.61 10.55
90.001a.c9
67 07.40..064
49.67
66.43
68.6440.29
52.0617.20
66.61 10.72
USOT (Unnormalized)
86_..
SOPT (Unuormalized)
87.27
with other unbalanced sliced methods such as SOPT (Bai al., 2023). We chose to compare with this competitor since their code is available in Python. However, numerical restriction of their algorithm is that only outputs measures with constants weights, i.e., distributions a = Σ 0555, and 3 = Bygyy where a;= = 3 = 1, but the number of samples in a and 3 may differ. Under this modeling assumption, the total mass of cach measure corresponds to the number of words in the sentence. We performed the comparison on the BBC dataset, using 500 projections for both SOPT and USOT. Unfortunately, the quadratic footprint of computing the similarity kernel does not scale reasonably for SOPT for larger datasets such as Movies Goodreads, especially because their algorithm is not GP GPU-compatible compared to ours. We cross-validated the parameter f e [00 6], 51}
a;
The result is detailed in the table below. What is noticeable is that the performance degrades for both USOT and SOPT using this parametrization. Furthermore, we observed that the paramater p yielding the best accuracy is much smaller for unnormalized measures than for the best one for normalized histograms (i.e., le 5 here compared to le 3 with normalized measures). Our interpretation of this observation is that considcring unnormalized mcasures adds additional information of the sentence length via the masses of (o., 3). It seems that this additional information dominates the comparison of measures, instead of focusing on the measures support (i.e., the word embedding) which encodes the semantic information of words. When p is large the kernel value of USOT/SON /SOPT is mainly dictated by the mass (i.e., sentence length) comparison. Thus smaller P seems to give less importance on sentence length, hence a better performance. We also note that performance of SOPT and USOT on unnormalized measures are rather similar. Tt means that for the choice of marginal prior D. pTV or D. ,KL does not significantly matter for this specific task, compared to the preprocessing normalization of measures.
C.2 Unbalanced sliced Wasserstein barycenters
We define below the formulation of the USOT barycenter which was used in the experiments of Figure 4 average predictions of geophysical data. We then detail how computed it.
39

---

Published in Transactions on Machine Learning Research (12/2024)
Source
t=0.25
t=0.50
t= t=0.5
Target
24
215
1b
als
(a) SOT barycenters
Source
t= 0.255
t=0.50
t= 0.75
Target
125
10
25
275
25
100
155
175
2
18
56
275
(b) USOT barycenters with P1 P2
100
Source
t=0.25
t=0.50
t- 0.75
Target
26
100
15
275
25
30
100
135
100
175
164
185
19
175
36
300
12
186
175
39
364
190
155
(c) USOT barycenters with = 0.01
Source
t- 0.25
t=0.50
t- 0.75
Target
100
(d) USOT baryoenters with P = 0.01 and P2 100
Figure 8: Interpolation with USOT as a barycenter computation. We compare different. interpola- tions using SOT or USOT with different settings for the p values
Definition C.I. Consider a set of measures (0.....,aB)) E (Rd)), and set of non-negative coefficients
(Wi,..., wB) 2 0 such that Eb Wh = We define the barycender problem (in the KL selling) as
B((at),, (wb)6) A inf (R
wa USOT((a) B),
(98)
B
inf (EP(
inf (5,,)
SOT(Tb,1 To.2 + PIKLL(To,loo) + 23,
(99)
where P(Rd) denotes the set of probability measures.
40

---

Published in Transactions on Machine Learning Research (12/2024)
To compute the barycenter, aggregate several building blocks. First, since consider that the baryeenter B E PP(R)) is a probability, we perform mírror descent as in (Beck & Teboulle, 2003; Cuturi & Doucet, 2014b). More precisely, we use a Nesterov accelerated version of mirror descent. We also tried projected gradient descent, but it did not yield consistent outputs (due to convergence speed (Beck & Teboulle, 2003)). Sccond, we use a Stochastic-USOT version (see Section 4), b.e., we sample new projections each iteration of the barycenter update (but not a each iteration of the FW subroutines in Algorithm 3). This procedure is described in Algorithm
Algorithm Barycenter((aa)) (ub))s, Pl, P2,
Input: measures (as)s. weights (wa)s, Pt, P2, learning rate Ir, FW iter F Output: Optimal barycenter / of (98)
t+1
Init (3,3,3) uniform distribution over grid
while not converged do do
7 [==1
8 + (1- + +
Sample projections (0s =
Compute B((an),, (wn)s) by calling USOT(as, 3, F. (0x)) in Algorithm 3 for each b Compute g as the gradient of B((an)o, (wo)o) w.r.t. variable
3 e exp(- Ir x x g)B
9 3/m
8- (1 7) +8
- --1+1
end while
We illustrate this algorithm with several examples of interpolation in Figure 8. We propose to compute interpolation between two measures located on fixed grid of size 200 x 200 with different values of pi in Dj. =, For illustration purposes, we construct the source distribution as a mixture of two Gaussians with a small and a larger mode, and the taryet distribution as a single Gaussian. Those distributions are normalized over the grid such that both total norms are equal to one (which is not required by our unbalancod sliced variants but grants more interpretability and possible comparisons with SOT). Figure shows the result of the interpolation at three timestamps (t 0.25, 0.5 and 0.75) of SOT interpolation (within this transported over
setting, W1 = 1 t and Wa t). As expected, the two modes of the source distribution the target one. We verify in Figure 8b that for large value of P1 P2 100, the USOT interpolation behaves similarly as SOT, as expected from the theory. When P1 P2 = 0.01, the smaller mode is not moved during the interpolation, whereas the larger one is stretched toward the target (Figure 8c). Finally, in Figure 8d, an asymmetric configuration of #1 = 0.01 and p2 = 100 allows to get an interpolation when only the big mode of the source distribution is displaced toward the target. In all those cases, the mirror-descent algorithm is run for 500 itcrations. Even for large grid of 200 200, those different results are obtained in 2 minutes on commodity GPU, while the OT or UOT barycenters are untractable with limited computational budget.
C.3 Unbalanced version of hyperbolic SOT.
To illustrate the modularity of our FW algorithm, we aim comparing synthetic mixtures of Wrapped Normal Distribution on the 2-hyperbolic manifold III (Nagano al., 2019), so that the FW oracle hyperbolic sliced OT (Bonet et al., 2023c). The parameter 0 characterizes on H any geodesic curve passing through the origin, and each sample is projected by taking the shortest path to such geodesics. Once projected geodesic curve, we sort data and compute SOT w.r.t. hyperbolic metric dg. We consider the 2-hyperbolic manifold on the Poincaré disc. As illustrated in Figure 9, the inpul measure a (in red) is a mixture of 3 isotropic normal distributions, with a mode at the top of the disc playing the role of an outlier. The measure I is a mixture of two anisotropic normal distributions, whose mcans are close to two modes of a, but are
slightly shifted at the disc's center. We show on Figure the impact of the parameter p = Pi P2 on the optimal marginals of USOT.
41

---

Published in Transactions on Machine Learning Research (12/2024)
P 10-3
10
10-1
100 = 10
Inputs (p 00)
Marginal mi
Marginal m
Figure 9: KDE estimation (kernel et// of optimal (T,, ma) of USOT(a, 3) when Dyp =KKL.
This experiment illustrates several take-home messages, mentioned in Section 3. First, the optimal marginals (T1, m2) are renormalisation of (a, B) accounting for their geometry, which are able to remove outliers for properly luned When is large, (2) = (a, B) and we retrieve SOT. When p is too small, outliers are removed, but we see a shift of the modes, so that modes of (T1, T2) are closer to each other, but do not exactly correspond to those of (). Socond, note that such plot cannot be made with SUOT, since the optimal marginals depend on the projection (see Figure 1). Third, we emphasize that we are indeed able to reuse any variant of SOT.
C.4 Choice and interpretation of hyperparameter
An immediate drawback of our framework is the induced additional computational cost w.r.t. SOT. While the above experimental results show that SUOT and USOT improve performance significantly over SOT, and though the complexity is still sub-quadratic in number of samples, our FW approach uses SOT as a subroutine, rendering it necessarily more expensive. Additionally, another practical burden comes from the introduction of extra hyperparameters (pI,P2), which may be tuned using cross-validation. Therefore, a future direction would be to derive efficient strategies to tune (21, maybe w.r.t. the applicative context and further complement the possible interpretations of p as a 'threshold' for the geometric information encode by C1, Ca. While we leave the automation of tuning (P1, for future works, we provide below some details and int ints on the choice of p for the previous experiments. We hope these insights will help the practitioner on how they should chose tune this additional parameter.
General intuition on p. The parameter p when A1 = P2 P can be understood as a characteristcc distance decide whether or not sample should be matched by the coupling π in the primal formulation of (2). Typically, transportation happens for samples (z, such that Ca(z, v) S p, while samples such that Ca(a,y) y) 2 P are interpreted geometric outliers, and are discarded in the matching *(x, v). In the case of SUOT and USOT, there is somehow a similar interpretation, but not for the same quantities, and we rely on their definitions (Equations 7 and 10), as well as the constraint set in Theorem 3.9.
One sees that for SUOT(a,;3) we have a set of 1D-UOT problems between (0ta, (), thus the threshold interpretation holds depending on whether C1 (t)) p or (z), 2 p. In particular the dependence in 0 explains why the outlier threshold depends on the considered projection. Note also we consider C1 instead of Cy-
For USOT(a, (9) it is different because the marginals (T1, which we optimize in Equation (9) are independent of 0, and common to all projections. Informally speaking, we interpret that the thresh- old value to discard a matching between (z,y) depends on whether some quantity proportional to Iga-1 C2 (8' H* (1)))dm((z (8) is larger or smaller than p. This quantity is not properly defined it depends on the optimized variables (mo),, hence the informality of our intuition. However, we wish emphasize that the parameter should be interpreted differently between SUOT and USOT. As highlighted
42

---

Published in Transactions on Machine Learning Research (12/2024)
=01
2011
10-1
U801,
Undt
5137-
5U07
1507.
10
1537-
0537
5.07.
5137, 8- 200
5UDT 4 100
16-1
5J0T.
number
number
Figure 10: Sample complexity: El| Bn) ((a,8)1 against n, with L SUOT or USOT and B = La) (thus [(a, = 0). Results are averaged over 20 runs and the shaded areas represent the 10th and 90th percentiles. All curves exhibit the same convergence rate for any d, that is 1/n (sce solid line black curve).
experimentally for document classification in Figure 2, observe that the value of p yielding the best performance is not the same for each loss.
Choice of p for hyperbolic data. In Figure 9, the hyperbolic distance between overlapping modes is 0.96, while distance from side modes to the top red outlier is 2.83. Thus, proper choice of should lie in between, which seems consistent with the observation of Figure 9 for p 1. Indeed we see that we have satisfying trade-off between removing the top mode and preserving the crescent shape structure of main blue modes.
Choice of p for barycenter experiments. For the barycenter, we used insights from Figure 8 which interpolates circular blobs using asymmetric (2), where P1 is the parameter penalizing the imput measures fidelity, and P2 the parameter of the barycenter. For Figure 4 (especially line (d)), we also took assymetric (Pi,P2) P2) with large P = le4 for the barycenter to force data matching. Then for inputs P = lel is roughly the distance between cyclones (see Figure 4), to keep them in the barycenter. All in all, we force the barycenter to match the cyclone structure which matters most, while any structure who would be beyond this Pr distance between input mcasure would be discarded.
Interpretation of p for document classification. In this task the measures' support are given by word embedding in high dimension, for which we have no intuition of what is for instance the characteristic distance between different semantic clusters, and thus no idea on how p should be tuned. For this reason (and more generally in ML tasks), we need to perform a validatai over this hyperparameter. We would like to comment the dependence of the document classification accuracy w.r.t. p, which can be observed in Figure 2. One can notice that as P increases, the accuracy increases until it reaches a 'peak', until then it decreases to reach a platean as / - cc. When P - SUOT and USOT converge to SOT (see Definitions 2.4 and 3.6), and we get similar performances. As + O, marginals (TI, T2) are allowed to differ significantly from inputs (a, 3), meaning that SUOT/USOT almost ignore input data. Therefore, should be tuned to extract information from inputs while removing noise. In Figure 2, the 'peaks' correspond to such optimal P, and the gain performance justify the use of SUOT/USOT over SOT.
C.5 Illustration of the sample complexity
We investigate the sample complexity of SUOT and USOT in practice and report the results in Figure 10. Our goal is to empirically verify Theorem 3.4 for SUOT, and explore the convergence rate for USOT. To this end, we consider a 8 (N Lx) and compute SUOT(an, (n) and USOT(a, B,) for different number of samples n and dimension d. This allows us to explore the convergence rate of SUOT(a,, 3n) to SUOT(a, B) = 0 (respectively, of USOT(an, Bu) to USOT(a, 33 0) as function of and d.
43

---

Published in Transactions on Machine Learning Research (12/2024)
Figure 10 shows that all curves share the same slope w.r.t n, for any d and for both SUOT and USOT. This experiment is consistent with the dimension-free rate we established in Theorem 3.4 for SUOT. Interestingly, it also reveals that the dimension- free rate holds for USOT as well in that specific setting, More experiments and/or thcoretical justification are needed to verify if this holds for more general distributions.
44


Reviews:
[{"review_id": "gDTO7x0JwS", "reviewer": "Reviewer_xwi2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper is very well written and clear. \n- The definitions are natural and the results are interesting\n- Theory appears to be solid and experiments are OK.\n\n- The paper does not seem to introduce seminal new ideas but mostly combines previous approaches (which is completely fine given the acceptance criteria)\n\n\nOverall I enjoyed reading the paper and think it is a valuable contribution to TMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Optimal transport introduces a distance on probability measures but has limitations for high dimensional settings and measures with non-equal mass. Sliced optimal transport (SOT) (i.e., an average of the OT distance over uniform random 1d projections) and unbalanced optimal transport (UOT) try to address these drawbacks. \nThis paper combines those two techniques and investigates variants of sliced unbalanced optimal transport which has previously only been done in special cases. They propose two formulations that differ in the order in which the operations are performed, either unbalanced optimal transport of the projected measures is considered (SUOT) or they consider unbalanced optimal transport where the OT distance is replaced by its sliced version (USOT).\nLeveraging results for SOT and UOT the authors then show that their variants enjoy favorable statistical properties and they propose an Frank-Wolfe type algorithm to compute these metrics in practice. Experiments show that the introduced methods and algorithms are competetive.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Mostly questions:\n\n- Does such a function $\\kappa$ (and $\\xi$) exist such that the rate holds uniformly for all measures? \n- Weak convergence holds if for any bounded, continuous function ... (p. 7)\n- Are the runtimes really only $10^{-3}s$ (in Table 1)? What do they correspond to, a single distance evaluation?\n- In my understanding the hyperparameters are tuned differently for UOT and the sliced variant which appears a bit unfair, also I think that the cross validation based $\\rho$ should be reported in the main text. \n- Theorem 3.11 seems to be a bit more involved than most of the other results. It would be good if some proof intuition can be provided and if the authors could clarify what parts of the proof are identical to prior work and where the proof is adapted to the new setting.\n- What is shown below Eq. (21) in the proof of Theorem 3.4", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NTHMym8fGa", "reviewer": "Reviewer_u6CG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "After defining SUOT and USOT, this paper extensively studies their theoretical properties including duality, equivalence, and so on. Especially, the equivalence among UOT, SUOT, USOT shown in Theorem 3.10 & 3.11 is important in that we can effectively use SUOT/USOT instead of UOT for fatster computation. They also give Frank-Wolfe algorithms for SUOT and USOT, and confirm that the proposed algorithm can work efficiently in practice. Overall, I think this paper provides a good theoretical/algorithmic contribution to the field and has many potential readers.\n\nA weakness might be in its relatively limited description of related works. Since the resulting SUOT/USOT objectives are straightforward if one wants to merge them, it would be better to explain some strong motivation for merging them and/or the differences from existing studies. For example, we cannot see what a partial OT is and how its limitation is crucial (unit mass points), especially when we compute relatives of OT on empirical measures. The significance of this paper's contribution is thus a bit unclear.\nThis being said, the paper seems to provide sound theoretical analyses and should be a good fit to the scope of TMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper merges the two variants of relaxing optimal transports (OT) -- unbalanced OT (UOT) and sliced OT (SOT).\nDepending on which relaxation (U or S) is applied first, we can consider SUOT or USOT as possible outcomes of their combination.\nThe authors study theoretical properties of both SUOT and USOT and give algorithms for computing them.\nThey test SUOT/USOT and their algorithm on several datasets and confirm the computational efficiency of them, especially compared to the usual OT or UOT.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major:\n- My strong concern is on the presentation of Theorem 3.4. I can see what the authors mean by this statement, but it should be specified how the sequences $\\hat{\\alpha}, \\hat{\\beta}, \\hat{\\mu}$ are generated, how they are related, if they are random, etc. The current statement does not make sense. Also, I believe that such constants $\\kappa(n)$ does not exist unless you consider a proper subset of $\\mathcal{M}_+$. If my intuition is wrong, the authors should prove in which sense we can expect such constant exists; otherwise the conclusion might be meaningless.\n\nMinor:\n- Many of the notations are incrementally added in the theorem statements. A summary at the early stage of the draft would be helpful.\n- \"characteristic radius\" is written in Italic but not much mentioned afterwards. What is the intuition/importance of this?", "broader_impact_concerns": "I do not have any concerns in this regard.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LYcmc0Wmd3", "reviewer": "Reviewer_vipQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The paper is well-written and easy to follow. I enjoy reading this paper. The paper is theoretically interesting and rigorous. The authors have made a good try to explore the slicing unbalanced optimal transport.\n\nWeakness: \n1. The contributions are not clear\n\na: From my understanding, the SUOT has been proposed in the literature, while the USOT is newly proposed by the authors. I wonder if the authors could discuss the additional advantages of USOT over SUOT. For example, the authors mention that outliers could be removed by USOT. Does that mean USOT is more robust towards outliers? Such discussions could increase the contributions of this work. Otherwise, the authors are making non-surprising extensions from SUOT to USOT.\n\nb. The goal of slicing unbalanced optimal transport should not be simply combining these two notions but what new insights could be brought. One of them could be: new frameworks of OT which could achieve robustness and computational efficiency at the same time.\n\n2. The slicing technique is applied to accelerate the computation of UOT problems. This is good, but can the properties of UOT could be preserved? The authors are suggested to discuss from this perspective. For example, in the numerical experiments, in addition to evaluating the ACC and time, other properties like the robustness of SUOT and USOT could be explored and compared with UOT.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates two versions of the sliced unbalanced optimal transport problem, which applies the slicing technique to reformulate unbalanced optimal transport. Some theoretical explorations and comparisons have been explored. The Frank-Wolfe algorithms have also been adapted to solving the sliced unbalanced optimal transport problem. Numerical experiments have been conducted to validate the efficiency of the proposed formulations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the major concerns in the previous section. Also, the following are some other questions or requested changes:\n1. Page 1: Computing UOT ....in the number if n samples O(n^3logn). Please add a reference for this claim.\n2. Page 2: while being statistically more efficient...Why is it statistically efficient?\n3. Page 3: $\\alpha\\otimes\\beta$, what does $\\otimes$ mean?\n4. Could Theorem 3.11 be extended to USOT?\n5. Page 8: adapting the reasoning...? What does this mean?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers praise the paper after the (stimulating!) discussion phase, and the authors have successfully answered all queries and requests for clarification from the initial reviews. The paper effectively introduces interesting results in optimal transport and makes a fine contribution to the field of machine learning. A clear accept. Congratulations!
Decision: Accept (poster)