One for all and all for one: Efficient computation of partial Wasserstein distances on the line
Authors: Laetitia Chapel
Romain Tavenard
Venue: ICLR 2025 Poster (2025)
Keywords: Optimal Transport
Partial Optimal Transport
Sliced Partial Optimal Transport
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We introduce a novel algorithm designed to efficiently compute all exact PArtial Wasserstein distances on the Line with a complexity O(n log(n))

Abstract: Partial Wasserstein helps overcoming some of the limitations of Optimal Transport when the distributions at stake differ in mass, contain noise or outliers or exhibit mass mismatches across distribution modes.
We introduce PAWL, a novel algorithm designed to efficiently compute exact PArtial Wasserstein distances on the Line. PAWL not only solves the partial transportation problem for a specified amount of mass to be transported, but _for all_ admissible mass amounts. This flexibility is valuable for machine learning tasks where the level of noise is uncertain and needs to be determined through cross-validation, for example. 
By achieving $O(n \log n)$ time complexity for the partial 1-Wasserstein problem on the line, it enables practical applications with large scale datasets. 
Additionally, we introduce a novel slicing strategy tailored to Partial Wasserstein, which does not permit transporting mass between outliers or noisy data points. We demonstrate the advantages of PAWL in terms of computational efficiency and performance in downstream tasks, outperforming existing (sliced) Partial Optimal Transport techniques.

Published as a conference paper at ICLR 2025
One for all and all for one: EFFICIENT COMPUTATION OF PARTIAL WASSERSTEIN DISTANCES ON THE LINE
Laetitia Chapel
Romain Tavenard
L'Institut Agro Rennes-Anger - IRISA Rennes, France
Université de Rennes 2 IRISA Rennes, France
laetitia chapel (iriellrrrrsa.re trisa. fr
roma in. aeweeaarddunv--reeeeee
ABSTRACT
Partial Wasserstein helps overcoming some of the limitations of Optimal Trans- port when the distributions at stake differ in mass, contain noise or outliers or exhibit mass mismatches across distribution modes. We introduce PAWL, novel algorithm designed to efficiently compute exact PArtial Wasserstein distances on the Line. PAWL not only solves the partial transportation problem for specified amount of mass to be transported, but for all admissible ones. This flexibility is valuable for machine learning tasks where the level of noise is uncertain and needs to be determined through, e.g., cross-validation. By achieving O (n log n) time complexity for the partial 1-Wasserstein problem the line, it enables practical applications with large scale datasets. Additionally, we introduce novel slic- ing strategy tailored to Partial Wasserstein, which does not permit transporting mass between outliers or noisy data points. We demonstrate the advantages of PAWL terms of computational efficiency and performance in downstream tasks, outperforming existing (sliced) Partial Optimal Transport techniques.
INTRODUCTION
Optimal Transport (OT) plays crucial role in machine learning (ML) by offering geometry-awand ways to compare probability distributions. To name a few flagship applications. optimal transport and the Wasserstein distance have being used generative modeling (Arjovsky et al., 2017), can be used for quantization unsupervised learning (Cuturi & Doucet 2014). and allows to align distributions in domain adaptation (Courty et al. 201 6).
loss in classification (Frogner et al., 2015) and
However, OT suffers from two major limitations that may prevent its practical use in ML. First, its sensitivity to noise in the input distributions or mass mismatches between their modes hinder reliable computation the distance and can degrade the performance of downstream tasks. Second, existing OT solvers struggle with respect to computational efficiency. Most algorithms exhibit polynomial time complexity, making OT unsuitable for large-scale applications.
Unbalanced Optimal Transport (UOT (Benamou 2003), see Séjourné et al. (003b) for review) is
often deemed to be more robust to noise or outliers than its balanced counterpart (Balaji et al.) (2020)
UOT relaxes the mass conservation constraint of OT, allowing to match subparts of distributions or distributions with unequal total masses. Partial Optimal Transport (Caffarelli & McCann 2010) special case of UOT, on which the amount of mass be transferred can be fixed, which is convenient feature when the amount of out- out-of- de-ddiriibbtionn samples is known beforehand. Note also that Unbalanced or Partial OT can come with profile (Phatak et al.) 2023) or a regularization path (Chapel et al. 2021) that provides solutions for all values of the method's parameter at once. This can be leveraged for parameter selection or faster cross-validation on the mass to be transferred.
Exact solvers for OT (and UOT) exhibit cubic complexity in the number of samples, making them impractical for large-scale applications. Various relaxations and approximations have been introduced to reduce this computational burden. In this paper, we rely on the sliced approximation, which builds upon the property that the Wasserstein distance between I-dimensional distributions can be computed in O (n log (Peyré et al.) 2019). For UOT the line, several algorithms have been devised to efficiently find solutions in general cases (Bai et al., 2223 Séjourné et al.) 2023a), when the transport is an injective map (Bonneel & Coeurjolly 2019) involves free metric (Sato al. 2020).

---

Published as a conference paper at ICLR 2025
In this paper, we aim improve the usability of optimal transport by introducing novel algorithm for efficiently computing PArtial Wasserstein distances on the Line (PAWL) along with a well- grounded, original slicing scheme tailored for partial OT. Unlike previous approaches with polynomial complexities, PAWI. exactly solves the partial 1-Wasserstein problem in 1 in O (n. log n) time complexity when the ground cost is the Manhattan distance, making it suitable for practical use cases involving sliced partial OT on large-scale datasets. It provides solutions for all transported masses once, empowering users to accommodate diverse tasks when syper-paramete tuning required. Before diving into the details of our PAWL solver, we review the necessary background on Optimal Transport. We then introduce the proposed algorithm and the tailored slicing scheme. Empirical evaluations are provided in Section
2 BACKGROUND ON OPTIMAL TRANSPORT
Let us consider two point clouds {ax 1i=1 and {y51リ= where each sample belongs to IR, and the associated empirical measures = E, azda; and v Σ, byōy, with o, (resp. b,) the mass associated to z; (resp. y, We assume we can define a ground cost d( 9y) between æ; and y, In Kantorovitch's formulation of the discrete optimal transport problem, one aims at transporting the total mass of the source j to the target with a minimal cost:
OT(H, v) min
Ed(ars y mm 2.
(Kantorovitch)
=EII(A.))
where the constraint set M(u,, v) (Nr E Rixm such that Vi, E, Tzy = a, and Vj. Σ Fsj b,). This problem admits a solution as long as and v have the same total mass Σ, a; = Σ, by. Matrix π is called the transportation matrix and Tey indicates how much mass is transported from I; to y d(x y) = || - ullp. OT is a distance, called the p- --ssssrsttein distance.
Kantorovitch's formulation is a relaxation of the original Monge problem:
min Σ d( T(æ:))
(Monge)
where T : E; (;ŌT(2,)) = E, b,0y, is called Monge map. The question of the existence of such map has been thoroughly studied: it requires, among other conditions, that 2 and still that Σ, a. Ej by. When n = m and a; = bj. Vi.j. it corresponds to the optimal assignment problem where one aims finding a permutation operator solving
min Σ d(x,, (0))
(Assignment)
2.1 PARTIAL OPTIMAL TRANSPORT
If the measures j and not normalized an unbalanced optimal transport (UOT) problem, in which only a fraction S min(E, 0i Σ, by) of the mass transported. Here, we focus on the partial Wasserstein (PW) problem, a particular instance of UOT, where the constraint set in Equation (Kantorovitch) is modified to [[ps, {T B Rexm S. Vi, E, Tij 0g Vj, E, Tiy S by and E.j Ty s). This problem was initially studied by Caffarelli & McCann (0100) who proved uniqueness of the solution for any cost function d(x; y) h(x c y) (where is a convex function) in the case of measures with disjoint supports. Later, Figalli (210)) refined this result, relaxing the disjoint support assumption in the case of quadratic cost function. He analyzed the function that associates to each mass s the cost: + Ps)
contaminated with outliers, may instead solve
Although the problem of deriving an UOT version of the Kantorovitch formulation has been well studied, deriving an analogous formulation for the Monge problem (Monge) is less obvious. Eyring et al. 2023) defined unbalanced Monge maps by rescaling the target measure. Gallouët et al. (2021) proved the existence of UOT maps in the context of specific cost function.
In this paper, we consider variant of the linear assignment problem where all samples have equal mass, a; by = w, no constraints on n and m, and only a fraction s of the total mass is transported:
(W(, v, min Σ d( y ) such that Vi,j, j, Mej S. and Σ Tij = s. (PW(s))
HER
2

---

Published as a conference paper at ICLR 2025
2.2 COMPUTATIONAL (PARTIAL) OPTIMAL TRANSPORT
Solving OT problems is computationally demanding, with exact solvers typically having a cubic complexity. One key for permitting broader use of OT is to focus on favorable cases approximate solutions that reduce this prohibitive complexity. For instance, the entropy-reeularized formulation proposed by Cuturi 2013) reduces the complexity to O (n²). When samples 2; and yj are 1- dimensional, the complexity is O log n) as a closed-form solution exists. It suffices sort the distributions μ and / and match their cumulative distribution functions. This special case is at the core of sliced OT (Rabin al., 2012) which is defined as the average of dimensional OT costs computed along L projection directions over the unit-sphere. This approximation of OT has a complexity of O (dLn + Ln logn), where d is the dimension of the samples, and exhibits favorable statistical properties (e.g. improved sample complexity) that makes it a standard tool for the OT practitioner.
When it comes to partial OT, several algorithms have been devised. Phatak et al. (2023) propose an exact solver that computes partial OT solutions for all possible values of the mass with complexity O (n²). Bai et al. (2023) define an efficient computation scheme for the partial OT problem on the line, with a quadratic worst-case complexity. [Bonneel & Coeurjolly (2019) solve specific one-dimensional injective partial assignment problem with a quasi linear time algorithm. [éejurné et al. (2022) introduce an iterative algorithm that converges to the exact solution of the Id UOT problem with a quasi-lineal complexity, but it does not extend to Partial OT, preventing its use when one aims at transporting fixed amount of mass (rather than setting sparse transport plan is sought. In addition, plugging these 1d solvers into a slicing scheme is not obvious: it corresponds to averages over different directions, different samples can be selected for each direction, which may lead to sub-optimal results (Séjourné et al. 2023a).
ssper-parameter) or when
In this paper, we propose new numerical scheme to compute partial solutions for all possible values of the transported mass & with O (n lo complexity for the Manhattan cost (i.e. we focus on the partial I-Wasserstein problem). We also define an appropriate slicing scheme based on |Mahey et al. (2024) that allows an efficient and grounded sliced partial OT solution.
3 PARTIAL WASSERSTEN DISTANCES ON THE LINE (PAWL)
Let æ = (21, ... In) and y - (yI (u..... Ura be I empirical arbitrary measures, with fixed weights a; b, w. As in Caffarelli & McCann (2010), we assume that the two distributions are disjoint sets, which allows ensuring the existence and uniqueness of the solution. In the following, we denote by {z1.... 2n+m} } the union distribution and we assume that æ. y and z have been sorted in a preprocessing step, which can be done in O (n log
The overall idea of PAWL is to be able to efficiently compute solutions æ E M(us, for all possible amounts of transported mass whenever the set of constraint is not empty. To do so, let us introduce the related problem for given number of samples to be transported:
min Σ d(z,, Us Ta such that Vi,j, May {0, w and Σ Taj k
(PAWL:)
We denote nO the arg min of PAWL.E.
Proposition 1. To solve problem PW(s) on the line, denoted sW it is sufficient to solve problems PAWL: and PAWLE with k'' # and i- [ and π (s) = πt + (x x²*) (s mod w).
Proofs for all propositions are provided in Appendix. In the following, our goal will hence be to design iterative algorithm that will construct {T for growing values of k. We denote A = {z; Ej Ti > 07 {8g E. m > 0} the active set associated to a solution π for PAWLI-
3.1 A FIRST, O (n²), ALGORITHM
Our PArtial Wasserstein distances on the Line (PAWL) solver will rely on induction to compute, incre- mentally, solutions for PAWL; with growing values of k. The main ingredient for this construction is the following important result from Caffarelli & McCann (0100)
Theorem 1. For all & < k,, there exist solutions for PAWL& and PAWLy such that Ak C Av-
3

---

Published as a conference paper at ICLR 2025
Initialization. We aim to compute solution for PAWLo. The constraint set on π (0) is such that the only admissible solution is Tij" = for any i, Hence PAWLo = 0 and Ao =
Induction. Let us now assume that solution for PAWL& has been constructed. Our goal is now to solve P1 Using straightforward cardinality reasoning on active sets considered in Theorem [ there exists 1 of the form As U {a,, 12 with zi, yj E Ay the complement of Ag. A naive solution would then be to iterate over all candidate pairs and pick the one that least increases the cost.
In the following, we will aim at improving the induction step of this naive algorithm in two decisive ways. The first one is to drastically restrict the candidate pairs set and the second one to efficiently compute the increase in cost each candidate pair would induce. Section titles reflect the successive gains in time complexity offered by each improvement.
3.2 RESTRICTING THE CANDIDATE SET TO GET O (n²*) TIME COMPLEXITY
Let us first restrict the set of candidate pairs {Ii, Mj at given step k of our algorithm. To do so, we rely on the following property, illustrated in Figure
(a)
Proposition 2. A given sample 2ς E As, can only be added in the active set together with one of its neighbors in As coming from the other distribution.
24
yj
A
This property restrains the search space from O ((n - k)2) enumerations to O (Card(AAe)
(b)
Figure 1: Candidate pairs for PAWL given Ag. At each iteration k, a candi- date pair is either a pair of neighbors in the union distribution (a) it is such that all points in between are already in- cluded in AN (b). The dotted links are the matchings in PAWL; and those in magenta are the matchings in PAWL
O k). For each pair, computing the cost of the candidate active set A& U {I,, yj is 1d OT problem on already sorted distributions, for which complexity is O (k.) Induction step & hence runs in O (kin k)) time.
At this point, the algorithm iteratively constructs solutions for all PAWL& problems for k ranging from 0 to n, with an overall time complexity will be further lowered in Section 3.4 by providing ways
O
(n²) ) This complexity
of accessing the best candidates { {2, y at each step. For now, let us have a closer look at what
takes to efficiently compute the cost of including given candidate pair.
3.3 EFFICIENTLY COMPUTING THE OT COST FOR EACHI CANDIDATE SET (O (n²))
For each step, we now need to compute the increase in cost induced by each pair in the (restricted) set of candidates. We provide an O (1) method to compute this increase in cost for any candidate when d(..:) is the Manhattan distance. In nutshell, we will show that i) all candidates form specific patterns the real line coined chains and that such chains chains can be decomposed into minimal sets for which the OT cost can be computed in O (1) and iii) it is possible examine only one candidate each iteration of our algorithm.
be extracted efficiently, ii) those
As stated earlier, candidate pairs are of the form {a,, 35 where x; and yj are neighbors in Ak. This can only happen in two settings: (S1) x; and yj are also neighbors in (i.e. there exists such that {zt, Vy = 1 ze or (S2) and yy are not neighbors in z and all points from z included in the open interval (2.. are Ag (i.e. {2,, } (zt-p- 22} and 1e-pt1.... 2 E As).
In order to efficiently compute the increment in cost induced by such candidate sets, we will rely on the notion of chain defined hereafter:
Definition 1 (Chain '6). A chain '6 is an ordered set of contiguous samples that is balanced, i.e. such that the total number of samples from x in '6 is equal to the total number of samples from y in E. This notion is illustrated in magenta in Figure
Definition 2 (Cost of a chain c(C)). Let E be chain. Its cost is c(C) -OT(uu, ve) where ex) b, δy,
pe = Σ, 1 (m:e Sz, and Ve = E3 (0,
Let us first focus on the (S1) setting. As shown in the proof for Proposition 2 Ay. is the union of disjoint chains. As consequence, knowing that samples mapped in order, 3; will be mapped to
4

---

Published as a conference paper at ICLR 2025
0
C
C
c
V/
(63
32
y1
c
1/2
333
i=4
271
1/1
322
1/2
74
375 9/3
J66
3/1
35
9/6
21 22
23
25
26
27 28
20 210
212
c(6) dl (6)) + ((6)) + c(
Figure 2: Chains and their associated costs. In order compute the cost for chain & (in magenta), we partition it into sequence of 3 minimal chains E3 '55 and 61i, for which cost computation can be made efficient when the Manhattan distance is considered.
Vj in Ax+1 and the increment in the transportation cost between As and As {2,,8)) will be the distance between v; and y, (cf Figure Tap. All such distances can be computed in preprocessing step with complexity (n) such that no additional cost is incurred at step
When it comes to the (S2) setting, the increase in cost cannot be computed the same way, since some of the mappings involved in PAWL, will be revocated in PAWL More precisely, all the mappings involving samples in the interval [ara, yj] will be revocated (cf Figure Tb). We now show how to efficiently compute the increment cost induced by changing the active set from A& to A& {zi, Mj}. The set {zt-p..... ze} introduced (S2) is a balanced set of contiguous samples. is hence a chain, denoted p---- Note that Ep-p-1-é-- is also a chain. In what follows, the increment in cost between A& and A& {-r, will be referred as the marginal cost associated to 61-p-e It can be computed as
marginal_comm costll_oss((_e (e-p-r) c(6c-p-41) - c(6e-p4i-e-1).
(I)
Efficiently computing the cost of chain. As can be seen in Equation (I) being able to efficiently compute the cost of any chain is sufficient to ensure efficient computation of the marginal cost of any chain. In order allow O (1) computation of the cost of chains during the run of our algorithm, will precompute sufficient quantities such that the cost of a chain can be accessed through simple lookups, relying the following proposition:
Proposition 3. Let Cr-p-r be a chain. Then have
c(66tt) c(6 d(6.-t---1).
Notation "6... denotes the maximal chain with a largest element at position E, i.e. E.st = arg minle,., card (b,=)) and we use the convention c(66-t-p-1) a largest element at position
if there is chain with
The burden of precomputing the cost of any chain has now shifted to that of computing, for any position E, the cost of the maximal chain with largest position f. We now derive algorithm for the computation of maximal chain cost, based on the observation that a chain is a set of contiguous non overlapping minimal chains, where minimal chains are defined as:
Definition 3 (Minimal chain ET). A chain & with its largest element position is said to be minimal iff i is the smallest set of contiguous points with a largest element at position & in z that is balanced. For each position there exists most one minimal chain, that we denote Ct.
This notion of minimal chain is illustrated in gray in Figure We have:
(66_1))= {f e (BT) + c c66. a minimal chain of the form '5 = .zr...., otherwise.
.e,....,,)! 22} exists
Given this, and assuming that we can access the existence of a minimal chain with a maximal element any position, can compute all c(6..e) terms in increasing order of & using dynamic programming in O (n). Once these quantities stored, the cost for any chain can be computed in O (1) using Proposition 3 We now need to extract all minimal chains and their associated cost from
5

---

Published as a conference paper at ICLR 2025
Algorithm 1: Efficient computation of chain costs for the Manhattan distance
Data: Sorted æ. Sorted y. Sorted 2
Compute all cumulative sums of the form Ch and C +1 Preconputatiions ons Extract all minimal chains from Uses Proposition 4
for j E [1..n] do
if 6 exists then
Compute (6;) using Proposition 5 and the necessary cumulative sums end
Compute c(6..)) using Equation
end
b Computation of a chain marginal cost using eq. and prop. marginal_com (6t-p-1t) c c(6--14111 (ccp))--(66----p ((6--1---) c (6 (t.ppp))
Efficiently computing all minimal chains and their associated costs. Proposition 4. Assuming that is sorted, extracting all minimal chains can be done in O (n) by iterating over items in z in increasing order.
We also need to efficiently compute minimal chain costs. If an arbitrary distance function is used, then computation of the cost for a chain of length L can be performed in O (L) by summing distances of items mapped increasing order. Let now focus on the specific case of the Manhattan distance. First, one should notice that, inside minimal chain, all mappings have the same ordering (cf. Proposition 5|s proof). In other words, if " is a minimal chain and { y5 one of the mappings inside 8* with < Mý, then all the mappings in E* will be of the form { y with The following proposition holds as a direct consequence of this observation:
Proposition 5. Let us denote the cumulative sums Ch Eist 2112, and similarly Ch
Eist 2 ,,y, with C% = C% = 0 by convention. The Manhattan cost for the minimal chain 8i = (z-pp..., 2 is:
c (66)) C CL--CC----- C³ C-e-p-
which can be computed in (1) time once the cumulative sums stored.
At that point, we can store, as a preprocessing step, all minimal chains and their associated costs in a lookup table such that one access the cost and smallest element of minimal chain of largest position in O (1) (lines 1-6 in Alg. []. We have reduced the complexity of induction step from O (k - k)) to (n k), which leads to an improved complexity O (n²) to compute solutions
to all partial problems. Our next step will be to avoid iterating through all candidates at each step,
3.4 CHOOSING THE BEST CANDIDATE AT EACH STEP (O (n))
At each step k; we have to decide which pair is the best candidate. In order not to iterate over all candidates at each step, we maintain ordered list of candidates, sorted increasing order their marginal cost. Choosing the best pair at each step then reduces to popping the first element of the list.
Recall that the candidates neighbors in z or (S2) such that all intermediate points are already in A& (Figure D.. We will hence make sure that all such pairs are included in our sorted list of candidates before they can involved in an active set. First, we initialize the list with all neigh- bor pairs, for which distances can computed in O (n). For these candidates, the marginal cost is their pairwise distance. Second, after each step l of the algorithm, assuming that the pair {2,, yソ has been selected as the best candidate, we can extract
either (S1) pairs of
Figure New candidate chain to be consid- ered after step k. At step k; the chain & (solid line) has been formed in Ag. U {x,, yy (dashed line) hence arises for future steps.
candidate
the largest chain '6 such that 24 Uj E 6 and & C Ag- We call this chain the covering chain for 34, Uj in Ak. If the immediate predecessor and

---

Published as a conference paper at ICLR 2025
Algorithm 2: Efficient computation of all PArtial Wasserstein distances on the Line (PAWL)
Data: Sorted 2, (maximum mass be transported)
Result: {Aks h and their associated costs
list__cantiino candidates <- cnitial_candddate
D Sorted ascending ng order of cost
Ag f-O 0
for k E {1,2, 1 do
Fe Vj. <- list candidates.popO Candidate with minimal marginal cost
A + A U {.,, 1.m covering_chain_jinggg
b cost((A) = cost(AA to
yj, A&))
candidatees.lean((6.
b Remove candidated overlapping with 61-m
21-1 and 2m+1 do not come from the same distribution then
marginal_ Lcciinlll_ssttt & c(6)-1-m+1) - c(61-mm
10
list www.ccaandncseeeeee cannddates.insertssotteee sowtiissiiieetssssdee------ 2m+1, marginal_com
11
end
end
successor elements of '6 do not come from the same distribution, then the union of E and those two elements a valid candidate for future steps k' > k. as shown in Figure 3 we can compute its induced increment in cost (ef. Algorithm D and insert it in the ordered list.
By doing so, at each step our algorithm, we pop exactly one candidate from our list candidates, and append at most one new candidate to that list. Since the list is initialized with at most n elements, the whole process can be done in O (n log n) complexity and this will dominate the complexity for Algorithm 2 when the Manhattan distance used as a cost. For other costs, and assuming single cost computation takes O (C) time, the overall cost is O (Cn²) (see Appendix A.2 for more details). Finally, note that this algorithm provides active sets and transportation costs. Recovering the transportation plan for given & requires an additional O (k log k) step to sort As.
SLICED PARTIAL WASSERSTEIN
Sliced OT Rabin et al. (2012) leverages 1d solvers to approximate the Wasserstein distance between probability distributions. While various methods have been introduced for sliced partial Wasserstein distances in Rd. there is currently
widely accepted consensus on the best approach within the community. Bai et al. (2023) define the Sliced Optimal Partial Transport that averages over 1d partial Wasserstein computed on the line, taking into account outliers into the approximation (note that, in their experiments, Bai et al. 2023) only rely on single projection in order to avoid this side effect). Séjourné al. (2023a) propose to reweight globally the input measures into the slicing process rather than projection by projection, allowing one to consistently discard some samples. However, their algorithm relies on specific properties of the UOT problem that prevent its extension to partial Wasserstein. Other variants of Sliced Wasserstein have been defined that either focus on refining the averaging process (Nguyen & Ho. 2024 Nguyen et al. 2024) or build upon the maximum distance over sampled projection directions (Desppande et al. 2019). Here, we advocate to rely on Mahey jet al. 2024) to define sliced-PW that has the advantage to provide sparse approximated transport map, hence allowing to identify samples as OOD. Our sliced-PW is bi-level optimization problem, where the inner problem is PWL(ss) one:
Sliced-PWCC (a, v, min Σ d(æ, 1z) with T²(0)= = arg min
Σ d((a,, 0), (y 0)) Tell(ggPg) i.
0584
1.j
such that Tij S w and Σ kiy s. (z. and (y 8) are the projections of the samples on to the direction over the unit sphere gd. In practice, we sample several directions and keep the one that gives the lowest PsL(s) solution. Sliced-PW inherits the main properties of SWGG, that is to say:
Proposition 6. Sliced-PW(fr, v, 5) is upper bound of PW and is a semi-metric almost surely.
7

---

Published as a conference paper at ICLR 2025
5 EXPERIMENTAL VALIDATION
To evaluate the efficiency and practicality of PAWL we conducted comprehensive experiments comparing it with the main state-of-the-ar related solvers. We compare them in terms of computation times and usefulness in three different settings. PAWL computes solutions for all partial optimal transport problems at the same cost of computing only one. This advantage allows it to operate without any prior assumption about the amount of mass to be transported, enabling a post-hoc selection of this quantity through the elbow method based on the variation of the transportation cost with respect to the number of transported samples. In the following experiments, we compare PAWL. with fixed amount of mass to be transported with PAWI. (elbow) that computes all partial optimal transports and decides on the amount of mass to be transported using an off-the-shelf implementation of the elbow method (Satopaa et al. 201T). As a result, this version does not require prior knowledge about the actual amount of corrupted or noisy samples, compared to other solvers.
10
PARL Mi
5.1 COMPUTATIONAL EFFICIENCY
Aserge time (in smaadss)
CPI, - 0.001 dlai
10/
In order to validate the theoretical complex- ity of PAWL, we compare its running times with those obtained for OPT (Bai et al., (023) that solves the exact same problem, and Fast- UOT (Séjoumé et al. 2022). that solves differ- ent yet related problem. In more details, OPT is an exact solver for POT given a
107
10-2
10
10'
10"
Namber of points x (resg.
that drives the amount of transported mass. Fast-UOTT is exact solver for the Kullback- optimal transport problems.
Figure 4: Running time comparisons for 1d partial
Leibler UOT problem and has one important hyper-parameter / which controls the strength of the KL relaxation in the unbalanced formulation. In this set of experiments, we set PAWL's target transported mass from Algorithm@ are computed, whereas only one solution (corresponding to hyper- spper-parameters À and p) is computed for the baselines. We study the computation time as a function of the number of points in the Id distributions involved. To do so, we generate random discrete distributions 1 and vary the size of their support between 100h and 10 As advised in Bai et al. (2023). the OPT's À is set as a fraction of the median distance between samples. A fixed value is used for Fast-UOT's p typer--aramettr. Figure 4 shows a quasi-linear trend for both PAWL with Manhattan cost and Fast-UOT, whereas OPT exhibits a quadratic trend for larger problem sizes, which is coherent with theoretical complexities. Note that PAWL with squared Euclidean cost is also competitive, even if it exhibits super-lineat trend. Fast-UOT is slightly more computationally expensive than PAWL in practice.
such that, for PAWL, all partial optimal transport problem solutions
5.2 PARTIAL GRADIENT FLOWS
Starting from an initial distribution μ. Wasserstein Gradient flows aim at driving it toward target distribution v by minimizing a displacement (or flow) over time. At each iteration, we minimize the loss pu()) + OT(p(t). v). We consider two variants of OT losses: Sliced Wasserstein (SW) Rabin et al. (2012) and SW Generalized Geodesic (SWGG) Mahey et al. (2024), considering 100 projection directions. We display the results in Figure by considering a transport with all samples (Vanilla OT) and only a partial transport using PAWL, in which either we set the amount of mass to be moved or select using the elbow method. We run the experiment for 500 iterations, with a fixed learning rate of 52- We consider scenario of bimodal distributions with unbalanced modes, which is typical failure case of vanilla OT. As expected, in this case, all the samples are transported, regardless of the cluster unbalance. SW with PAWL fails at providing a consistent flow as all the samples can be transported depending on the direction, leading to non-sparse transport. On the opposite. Sliced-PW defined in Sec. A produces a consistent flow, where some samples are not transported at all (black symbols), even in the case where the amount of mass to be transported is determined thanks to the elbow. Note here that the gradient flow scheme converges to the target v even if Sliced-PW is not a metric. Indeed, thanks to the partial scheme (in opposite to unbalanced OT for instance), the set of samples that belong to the solution is sparse, hence the set of samples pu(t) transported at each iteration remains stable, and SWiced-PW then benefits from the metric properties of vanilla SWGG.
Cooe is available at attp:pp://ggihhh...cc/rrreeeee/r
l
8

---

Published as a conference paper at ICLR 2025
Source and Tagget
(Viuilla
SWGG (Vanilla (11)
PAWL
Sheed-PW with PAWL
S-PW PAWL (clbow)
Figure 5: Results of the Gradient Flows scheme for different sliced methods after 500 iterations. Orange symbols represents the source distribution and blue ones the target distribution. Light and dark symbol have different number of samples. In black, the samples that have not been transported at the last iteration. Sliced-PW is defined in Section
Table 1: Performance for the point cloud registration experiment (error norms, the lower the better).
10k.5%
100.7%
56.5%%
91,7%
Uses s?
30s.
60s
End
30s.
60s.
End
30s.
60s.
End
30s.
60s.
End
SPOT
1.919
1,663
1.505
1.994
1.781
1.626
2,019
1.736
1.519
2,101
1.852
1.627
PAWI. (slloo)
2.155
1.754
0.014
2.097
1.621
0.030
2.359
2.104
0.121
2.340
2.097
0.174
SOFT PAWL
1.242
0.451
0.001
1.066
0.426
8:002
1,000
0.566
0.167
1.120
0.621
0.212
0.301
0.207
0.000
0,511
0,356
0.000
0.689
0,510
0,116
0.992
0,702
0,318
5.3 POINT CLOUD REGISTRATION
Point cloud registration involves estimating the transformation between two sets of 3D points, crucial task in various computer vision scenarios (Huang et al. 2021 | Bai et al. (023). Specifically, given two point clouds, we hypothesize an unknown mapping T that relates them. In many cases, this transformation is constrained to follow the form T(x) = o Rx + 3, where R is rotation matrix, represents scaling, and (3 is a translation vector. The objective then to estimate T.
The standard method for this task is Iterative Closest Point (ICP Chen & Medioni (1992)) that alternates between matching points their closest transformed neighbours and estimating the transform based on these matchings, until convergence. [Bonneel & Coeurjolly (2019) introduces a variant of ICP which the l-nearest neighbour assignment replaced by the sliced version of their 1d injective matching method, named SPOT. In the context of noisy point clouds, (Bai et al.) 2023] Algorithm 3) introduce a variant relying on partial optimal transport to match distributions projected in 1d. Notably, parameters of the transform T are estimated along the projection direction on transported samples alone. At each step of their algorithm, their as close possible to the actual mass of uncorrupted
À is tuned such
that the amount of transported samples samples 8, which is supposed to be known. For a fair comparison, we keep the same slicing scheme as it relies on one direction only and does not mixes several directions.
We will build on this strategy to develop two variants that rely on PAWL. A first variant, denoted "PAWL" is a direct adaptation of SOPT in which PAWL solver is plugged in place of the OPT one. Note that, in our case, we do not need to tune À at each step since we can use the prior about directly as an input. second implementation, named "PAWL (elbow)" decides on the best amount of mass to be transported at each iteration.
We use the same noisy point cloud datasets as in Bai al. (2023): Stanford Bunny, Dragon, Witch- Castle, Mumble Sitting. For each dataset, transforms are generated with uniformly sampled angles, translations, and scalings. Noisy points are appended to the distributions. Target data has a fixed size of 10k points; source data sizes vary (9-10k). The amount of added noisy samples ranges from 5% to 7%. We compare our PAWL variants to both SOPT (Bai et al. 2023) and SPOT (Bonneel & Coeurjolly 2019). We do not include ICP in our comparison since it has been shown perform poorly on noisy point clouds (Bai et al. 2023 Bonneel & Coeurjolly] 2019).
As shown in Table I. both PAWL variants demonstrate low error in estimating the transform's parameters. When employing the prior on s, PAWL outperforms SOPT in rapid convergence and, at convergence, surpasses SOPT in 3 out of 4 cases. Notably, even without using prior information,

---

Published as a conference paper at ICLR 2025
SPOT
SOPT
(c) PAWL
(d) PAWL (elbow)
Figure 6: Point cloud registration using SPOT, SOPT and our PAWL solver after 30 seconds. The target point cloud blue and the source point cloud in green. The dataset used this illustration is Stanford Bunny, with 10k samples in the source distribution and 7% of noisy points.
PAWL (elbow) is solid competitor, exceeding SOPT (which relies on such prior information) in half the cases. However, PAWI. (elbow) tends to require more time converge due to the elbow method's s initial challenge in accurately estimating the amount samples to transported when the transform is weakly estimated and clean/noisy samples are difficult to distinguish. These observations are corroborated by visual inspection of Figure
5.4 SLICED PARTIAL WASSERSTEIN FOR DOMAIN ADAPTATION
We demonstrate the relevance of our Sliced-PW method, as defined in Section 4 in a higher- dimensional scenario. We consider the setup de- scribed in Chapel et al. 2021), where obtaining solu- tions for different egglaaizztiinn values proves useful for detecting data that may be contaminated with outliers. The source data consists of MNIST digits sampled from classes O, 1, 2, 3 (200 points per class). The target data includes MNIST digits from classes and 1, as well as Fashion MNIST digits from classes and 9. Label propagation used to classify the target data, for each possible mass amount s. Figure [ ccompares the overall accuracy (defined as the ratio of correctly classified samples to the total number of samples) and the current accuracy (defined as the proportion of correctly classified samples among the transported points) of the Sliced-PW method and the regularization path approach proposed in Chapel et al. (2021) and the OT profiles (Phatak et al. 2023) (we considerered L1 ground cost), which are the state-of-the art methods that provide the entire set of solutions. Sliced -PW relies on d + 100 randomly drawn directions and for each s, it selects the direction of minimal cost. Experiments are repeated 10 times, and the results show that the average runtime of PAWL. (1 sec. on a personal computer) more than 200 times faster than that of UOT, and 14 times than OT profiles. Moreover, it provides comparable or even superior detection performance than UOT, as it avoids the need to set a threshold parameter to determine whether a sample has been transported.
Oveallaas (DOT
Cameut (UOT Za)
Ovcrell us. (Slxd PR)
Aesmay
Cament am [Slied PW)
Oonall (0T pof)
pmot)
Figure 7:
Evolution of the accuracies w.r.t.
the number of transported samples.
CONCLUSION AND PERSPECTIVES
In this work, have introduced PAWL, a novel algorithm for efficiently computing partial optimal transports between one- -ieedmmesiional distributions. It enhances robustness against distributional variations (as Partial Wasserstein) while enabling practical use cases with large-scale datasets (as Wasserstein on the line). By computing solutions to all partial problems with a linear complexity, it allows an inspection of the evolution of the Wasserstein distance with the mass, hence providing a way to determine the best amount of mass to transfer.
Future work will explore differentiable variants of Sliced-PW: as we rely on the Manahattan distance to provide an efficient scheme, the smoothing scheme described in Mahey et al. (0024) can not be used, preventing the efficient search of an optimal slicing direction in large dimensions. Another line of work concerns the extension of PAWL non constant masses 0; # a, and a, * by. or, ultimately, to continuous distributions. Finally, studying statistical guarantees on the subset that is selected through PW would allow establishing some conditions of convergence for sliced-PW scheme.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
Both authors are deeply grateful Paul Viallard for his invaluable feedback on early versions of this work. Romain Tavenard would like to acknowledge funding from ANR through project MATS ANR-18-CE23-0000
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference muchine learning, pp. 214-223. PMLR, 2017.
Yikun Bai, Bernhard Schmitzer, Matthew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 13681-13690, 2023.
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33:12934-12944, 2020.
Jean-David Benamou. Numerical resolution of an "unbalanced" mass transport problem. ESAIM: Mathematical Modelling and Numerical Analysis, 37(5):851-868, 2003.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances in neural information processing systems, 33:9508-9513 2020.
Mathieu Blondel and Vincent Roulet. The elements of differentiable programming. arXiv preprint arXiv:2403. 14606, 2024.
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In International Conference on Machine Learning, pp. 950-959. PMLR, 2020.
Nicolas Bonneel and David Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions Graphics (TOG), 38(4):1-13, 2019.
Luis A Caffarelli and Robert McCann. Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics, pp. 673-730, 2010.
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- -22222, 2021.
Yang Chen and Gérard Medioni. Object modelling by registration of multiple range images. Image and vision computing, 10(3):145-155) 1992.
Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamoniy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):18533114 1865, 2016.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In International conference on machine learning, pp.
PMLR, 2014.
Ishan Deshpande, Yuan- -ang-Ting& Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander G Schwing. Max-sliced wasserstein distance and its use for gans. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10648-10656, 2019.
Luca Eyring, Dominik Klein, Théo Uscidda, Giovanni Palla, Niki Kilbertus, Zeynep Akata, and Fabian Theis. Unbalancedness in neural monge maps improves unpaired domain translation. arXiv preprint arXiv:2311.15100 2023.
11

---

Published as a conference paper at ICLR 2025
Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-560) 2010.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with wasserstein loss. Advances in neural information processing systems, 28, 2015.
Thomas Gallouët, Roberta Ghezzi, and François-Xavier Vialard. Regularity theory and geometry of unbalanced optimal transport. arXiv preprint arXiv: /2. 1056, 2021.
Xiaoshui Huang, Guofeng Mci, Jian Zhang, and Rana Abbas. A comprehensive survey on point cloud registration. arXiv preprint arXiv:2103.02690, 2021.
Guillaume Mahey, Laetitia Chapel, Gilles Gasso, Clément Bonet, and Nicolas Courty. Fast optimal transport through sliced generalized wasserstein geodesics. Advances in Neural Information Processing Systems, 36, 2024.
Khai Nguyen and Nhat Ho. Energy-based sliced wasserstein distance. Advances in Neural Information Processing Systems, 36, 2024.
Khai Nguyen, Nicola Bariletto, and Nhat Ho. Quasi-monte carlo for 3d sliced wasserstein. 2024.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 1165-6)355-607, 2019.
Abhijeet Phatak, Sharath Raghvendra, Chittaranjan Tripathy, and Kaiyi Zhang. Computing all optimal partial transports. In International Conference on Learming Representations, 2023.
Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision: Third International Conference, SSVM 2011, Ein-Ged; Israel, May 29 June 2, 2011, Revised Selected Papers 3, pp. Springer, 2012.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on tree. Advances in neural information processing systems, 33:19039-19051, 2020.
Ville Satopaa, Jeannie Albrecht, David Irwin, and Barath Raghavan. Finding a" kneedle" in haystack: Detecting knee points in system behavior. In 2011 31st international conference on distributed computing systems workshops, pp. 166-171. IEEE, 2011.
Thibault Séjourné, François- Xavier Vialard, and Gabriel Peyré. Faster unbalanced optimal transport: Translation invariant sinkhorn and 1-d trank-wolfe In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2022.
Thibault Séjourné, Clément Bonet, Kilian Fatras, Kimia Nadjahi, and Nicolas Courty. Unbalanced optimal transport meets sliced-wasserstedd arXiv preprint arXiv:2306.077 077306000666...... 2023a.
Thibault Séjourné, Gabriel Peyré, and François-Xave Xavier Vialard. Unbalanced optimal transport, from theory to numerics. Handbook of Numerical Analysis, 24:407-471, 2023b.
12

---

Published as a conference paper at ICLR 2025
A APPENDIX
A.1 PROOFS
Proposition 1. To solve problem PW(s) the line, denoted PWL(s), it is sufficient to solve problems
PAWL2; and PAWLES, with k' and L and (8) T + (Ix =T*) ).*)..C (s mod w).
Proof of + k'
If = k', the proof is straightforward as = k. w. We then only focus on the case when
Let be the mass to be transported, such that there exists with k < < k
From Caffarelli
McCann 2010 Prop 3.1), we know that there exist solutions PAWL; and PAWL L++1 such that their active sets are related by Ak+1 Aş U {Ta, Mj (Caffarelli & McCann
2010 Theorem
3.4) (monotone expansion of active regions) tells us that there exists a solution ( (()) to the problem
PWL(s) such that the marginals of π are stable between π", Tss) and π +1 except for > The and
D mey (i.e. H; and Y/ are the only samples for which transported mass changes and for all other indices, the marginal is either 0 or w).
At this point, we hence know the marginals of a solution л (s). At fixed marginals, our Partial Wasserstein problem becomes a Wasserstein problem in 1d. It is known that these problems can be solved by matching cumulative distribution functions (Peyré et al. 2019 Equation 2.37), which can be obtained from the marginals of
Let us assume, without loss of generality, that 2; < My. Since the marginals of nh, (s) and π *+1 only differ in z; and yj. they typically coincide outside the interval [a), My]- As direct consequence, we have
π (8) nT" + (n**+1 n x²) (s mod w)
outside this interval.
2; will be mapped with sample inside the open interval (Ii, Vj). More precisely, a direct application of matching the cumulative distribution functions gives that the mass mod coming from x; will be transported the lowest sample that is greater than Fg. This sample used to be mapped to the lowest z in (Iz, My) in πτ. Since it has only (s mod w) available mass remaining, it will send this mass x. Since xy is mapped to y PAWL the equality
As discussed in greater details in Section 3.2
π (s) Th + (T x²) (s mod w)
holds for samples x; and y.
The exact same line of reasoning can be used recursively on the interval (z, yj) from which we exclude (since all of its mass has already been transported), etc. until we reach yj- At this point, we have shown that the equality holds globally.
Theorem 1. For all ls < k', there exist solutions for PAWL; and PAWL such that An C. Ap-
Proof of Theorem 1 See (Caffarelli & McCann 2010 Prop. 3.1) For two disjoint with finite cardinality and a continuous cost d, the active sets A grow monotonically with the amount of mass transferred s k
Proposition 2. A given sample zt E As only be added in the active set together with one of its neighbors As coming from the other distribution.
Proof of For start, should note that, if A& is the active set for the PAWL; problem, then the mappings involved in the solution are those induced by the OT problem on distributions supported by (. Ag and y A.Ag respectively, with uniform weights. Since know that these couplings correspond to mapping the samples from both distributions in order.
in 1-dimensional setting,
We will now prove the following lemma:
13

---

Published as a conference paper at ICLR 2025
Lemma 1. If Ag is the active set for some POT problem, then it can be written as the union of disjoint chains:
Ale A -U
Cr such that Vi + 3. 66 n 0
where the notion of chain E defined in Definition 7 aad C; denotes the tth chain of Ak-
Proof. We will prove this lemma by induction on k. Initialization is straight- since, as discussed in Section 3.1 the solution to PAWLo is such that Ao 0.
For the induction step, we now assume that Aş can be written as the union of disjoint chains. Let A U {z, } be the active set for PAWLK+1. and let assume < z' without lack of generality. Let
us write A = "T") (U, ((t)) such that {8 are chains that lie outside the interval [z, ='] and {8 are chains that lie inside this interval. Since the mappings for Ar+1 are those of ld OT problem, all the mappings involving points from {'6;")) will be preserved.
Let us now prove that (U, 6Tth) U(2, is chain (which would allow us to prove the induction step). Let assume, by contradiction, that there exists y such that = < y z' and y & Ak. More precisely, if there exists several such samples, we will take y as the smallest sample satisfying this double inequality. Let us assume that y comes from the same distribution as 2' (the case where y comes from the same distribution show that As U (z, ='} has a higher cost than As {2, y) and hence cannot in the active set at step k + 1.
can be derived
simple symmetry of this one). We will now
U.S.
U, 8,
U
6 6.-y uf+
(U, UrE'M
U, 1,
3/
Figure 8: Illustaaioon of the setup considered in the proof for Lemma [ Here, all points in shaded areas are in As and points in non-shaded areas are in Ag. We show in this proof that we cannot have this setup if 22,2') E Ak+1 (top), since A& U {2, y (middle) would have lower cost than Au (z, z²} (bottom).
By the definition of chains, cannot belong to a chain (as a chain is a set of consecutive points), hence (U, Gim)) can be further partitioned into (U, e the union of chains whose samples g are such that g < y and (U, gtt) the union of chains such that their samples >> y. By definition of we know that (U, 6,7) U(z,y) y} forms a chain that we denote Ez-zy. hence the cost associated to A& (2. y} writes:
( + ((55t) + c(62-1))
On the other hand, let us examine the mappings (and induced cost) that Al. U (2,22'} would induce. First, as for the previous case, the mappings related to (U, Goout are left unchanged. Let us denote by
14

---

Published as a conference paper at ICLR 2025
y* the immediate successor of be in (U, (,t).. Then the cost associated to Ar U (2,22) writes:
c (Uerm) +c ((Uxt ) + u
(4)
order to have the same number of samples from æ and y each part the cost.
If we first focus on E2-ty U {y- Mu). we see that the mappings in this set will be the same as the mappings in Ez-z except for the last one that will involve yt in place of y. As yt > ys we get
(6.-z U ty MW(t) > >c c(62+4)
If now turn foeus ((U. U(=')((( the mappings here are all be different from those (U; (,t).. However, given that z' & Ax. both these sets could have been candidates to be included in A& without changing all other mappings in As. Since (U, (6,t) was finally included in Ag, we know by optimality of Ag that:
((UET) JLNNNr)) 20 ((ET))
(6)
Using Equations ( and 66) Equations and
we get to the conclusion that c(Ar (2,
> L
c(As U (zz, (2, which is contradiction.
One should note that during the induction step of the proof of this lemma, we have proven the current proposition.
Proposition Let Ce-p-se be a chain. Then we have
c(61-p-r)=
c(6__e) =(( clc c(6--t--1)-
Notation E.., denotes the maximal chain with a largest element position E, i.e. E..st arg min card ((6(se) and we use the convention c(66. = O if there is no chain with a largest element position
Proof of For this proof, we will rely on the following lemma and the notion of minimal chain defined in definition
Lemma 2. Let ' be a chain. Then there is a unique (up to the order) sequence of adjacent non overlapping minimal chains such that E = -, C7 Moreover we have c(66) c(6()))
Proof. The proof for this lemma will be made of three parts:
existence of the sequence can be proven by recursive construction;
unicity of the sequence stems from the unicity of minimal chains with largest element at given position;
formula for the cost comes from the fact that the cost for a chain is an OT cost in 1d, hence it is the cost of mapping elements from both distributions in the chain in increasing order, which implies that no mapping will occur across minimal chains forming the series.
Let us start by proving, for any chain Eioj. the existence of a sequence of adjacent non overlapping minimal chains such that the chain is the union of those minimal chains. We will build this set of minimal chains incrementally. We hence start with an empty set and add the minimal chain E3 whose largest element is at position in the set. We know that such minimal chain exists since there is at least one chain whose largest element is at position j, which is G,-zj Let us assume that the first element of E is position f1. By definition of minimal chain, l 2: i, we have E6 C G--j- Now, if & = 1, we are done, and if not, we are left to finding a minimal chain partition for the chain C Gi- -1 11 We repeat this process recursively until the minimal chain find covers the remaining
15

---

Published as a conference paper at ICLR 2025
chain (which will occur since are building sequence of chains of decreasing length), and the sequence of minimal chains we have extracted hence covers the chain 6;-+j-
Let us now prove the unicity of this partition of a chain into minimal chains. Let assume that have two sets of minimal chains that would give partitions for 6;-5
6 G
C le'
We further assume, without loss of generality, that the sets are ordered in increasing order of their largest position. Since the union of those minimal chains has its largest element at position I (in order to strictly cover Ei=)), the last minimal chain in each set is the one with the largest element at position j (which is unique by definition). We hence have:
6
The same argument can be used to prove, by recurrence, that the p-th minimal chains in both sets are equal, hence both sets are equal, which proves unicity of the partition.
Finally, let partition the computation of the cost for chain B. From the partition we just proved, we have:
c(8) = = LOU C
Also, we know that the cost of the chain is the Optimal Transport cost between points involved in the chain, which corresponds to mapping the points order. Given that minimal chains are balanced by definition, know that mapping the points in order implies mapping the points within the chains, which gives our claimed result:
c(8) --c
Let us come back to proving that computation for the cost of any chain be deduced from the cost of maximal chains, i.e. the ones that have the highest cardinality.
Let Ce-p-z be chain. We will distinguish between cases:
Case 1: There is at least one chain whose largest element is at position & e p 1. Let us denote by l' the smallest index of the maximal chain whose largest element is position & p 1. We will show that l' is also the smallest index of the maximal chain whose largest element is at position &.
First, let observe that Cr is indeed chain. This is because -pr- and f are chains, hence in -p = 1p--e-p-1 U 61-p-z there are as many samples coming from x and y.
We now need to prove that De is maximal. Let assume, by contradiction, that there exists index t" < l' such that Egn- is chain. Since '6---= is chain, simply counting x and y samples -e-pe---1 tells us that it is chain. We have hence found chain ending in f- p whose first index is strictly smaller than E', which contradicts our initial hypothesis about the maximality of Co +e-----1
Overall, we have
8 = E7
and
6 b. 60-
From Lemma and using the fact that 1r Co -8 and Ce-p-se are chains, we have:
c(C..)) c(pp-e)
d'6p + c(66tpp-d
c(6..1-p-1) + c c(66-p--
Case 2: There is no chain ending at position - p-1 1. this case, we have c(66..1-p-1 = by definition, hence need prove c(6%-p--/) c(6..e)) Let assume, by contradiction, that there
16

---

Published as a conference paper at ICLR 2025
exists chain -r such that L' <t- p. We can hence use Lemma to partition this chain in set of contiguous non-ovent overlaapppnngg minimal chains. Since 66---+ is a chain too, we know that the partition of "r be written:
U
U
6x-p-t
and this contradicts initial hypothesis that there is chain ending position 8- p 1. There hence no chain ending at position that starts before - and we have 1t-p-t = 66.+6, from which the cost equality follows.
Proposition 4. Assuming that x is sorted, extracting all minimal chains can be done in O (n) by iterating over items
increasing order.
Proof of Let us start by extracting all minimal chains from the sorted union distribution To do so, we will rely on the notion of differential rank, defined below and illustrated in Figure
Definition 4. The differential rank position L, denoted тt, is defined Tt Card({ ( E x|2 & ze}) Card E ylu S ze))
By convention, we set ro
0.
Differential ranks can be computed in (n) given sorted z, and they can later be used extract all chains from given the following property:
Lemma 3. The following two statements are equivalent:
1. E i-p-s is a minimal chain in x
2. is the smallest strictly positive integer such that Tt-p-1
Proof. Let start by proving 1. + Let 6 be minimal chain in z. Then have:
re
Card((z E æ/2 S =x) Card (y E ylv S ze)) (Card((x E a/æ S =t-p-1) + Card( (xr axe E ((-p-e))) - (Card( E yly S zz-p-1)) + Card E yiu E1 bi-p-1)))
re-p-1 Card (x E a|æ E E1 ((-p))) - Card(fy E vly br ((-p-e))
since Et- d
Now we still have to prove that p is the smallest strictly positive integer such that T = -t-p-11 which we will do by contradiction. Let assume that there exists strictly positive integer p' such that Then we have:
l - < l -pp < e and re-p'-1
re-p'-1= = + Card (ar E a|æ S 2 2
Card(ly E vlv S =e-p/-1))
= Card((x E æ|æ S 2t) ) - Card(Ly E yly S 2x})
+ Card(fz E 2/2 S 23) Card(fa 2|2 zt-p-11))
Card((y E ylu S 2)) CCrdd(y E ylv S =t-p'-))
+ Card((# E m/ S x S =x)) = Card (v E gاıाー/ S S 21)
Er-p'-e is hence chain, which contradicts the minimality of 87p--p
Let us now prove 2. = We hence assume that p is the smallest strictly positive integer such that re- 1- Using the series of equivalences above, we have that Card( (u =l/r-p
S ) = Card (y yl=eep S Syysa {z)))
hence Ci-p-st is a chain. We now need to prove that this is the smallest chain whose smallest element at position f, which we will do, once again, by contradiction. Let us assume that there exists such that l p < E and Ce is chain. Then using the series of equivalences above again, get that ry- = Tt-p-1 = Tzs which contradicts the fact that p is the smallest strictly positive integer such that rz Tt-p-1-
17

---

Published as a conference paper at ICLR 2025
We will now rely this lemma efficiently extract all minimal chains by iterating items in in increasing order. Since a chain contains as many x' s as y's by definition, it should preserve the differential ranks (i.e. the differential rank before the chain should be equal to that after the chain).
Given this property, extracting all chains from & can be done in O (n) by iterating over positions in increasing order: at each position is sufficient compute rg based on 72-1 and 2g. Then, lookup table storing the last occurrence of each differential rank value can be used to decide a chain has largest element the current position and, if so, get the smallest position of the chain.
Let us denote the cumulative sums C= Eiggzilzz and similarly CLe Eise z4 2,EY, with 0 = C=0 = 0 by convention. The Manhatlan cost for the minimal chain '67 = (zt-p.... 2 is:
Proposition 5.
e cbit) = -C - C
which can be computed in O (1) time once the cumulative sums stored.
Proof of We have:
e c66)) 1
=t- ze-p+1l + /z--+2- - 2t-p+al + 126-1 - zel
Since inside minimal chain all mappings have the same ordering (shown in Lemma below), then all the quantities inside
have the same sign, hence
(6))
10E-D 2t-0-1 + Z8-p+2 2t-p+3 3+ + + 28-1 2t.
= (zte-p + 28 zt-p+2 + .... 21-1) (2t-pt1 + 2t-D+3 + ... . 24)1
26 1 IxEx k=1-p
Σ
Σ 2x xllnEy
k=t-p
Σ 2k 1
Σ
Σ ESP
Σ
26 sEE
syEy
zx mhy
kSt-p-1
kst-p-1
C CYam --1+1++
Lemma Inside minimal chain, all mappings have the same ordering, i.e. either xa < ye Va,, Vi E 6** Di >> yi. Vas, E E+.
Proof. Let 6; (EE 22} be a minimal chain. Let us assume, without loss of generality, that zt-p xc We will now show that all samples from n not mapped to samples from y n E, that are greater than them. By contradiction, let us assume that there is at least one mapping inside 67 that goes the other way around. Let denote by and the samples involved in the leftmost of such mapping on the line. We hence have ÿ < f.
By definition of (., ú) all y samples in E9 that lower than ý mapped samples that lower than themselves. This means that
card(æ E a 67 < ú) 2 card(y
67 < Ú)
Similarly, since samples matched in order on the real line, all æ samples in E, that are lower than have to be mapped to a sample that is lower than Ú. and we get
card(æ E æ n 87 l < ú) < card(y y El < ú)
By combining these two inequalities, the set of points
(= E 67 = < ú}
balanced set of contiguous points, hence it is chain, which contradicts the minimality of 6f 1
18

---

Published as a conference paper at ICLR 2025
Proposition 6. Sliced-PW(j, s) is upper bound of PW and it is semi-metrit almost surely.
Proof 6 Let first recall that
Sliced-PW PW (j,, v, = min Σ 6E84
d(a;; (y) with x²(0) = arg min rell(ggeg) i.
Σ dl (a.,,
(aa;;,), 0), (y. ma)
In brief, Sliced-PW(p,, almost surely for distributions living in R. This requirement is also needed for using PAWL as the latter requires the distributions to disjointly supported.
v. V,
memiic as long as (æ,, 0) + (xy, Vi # i', which is true
Upper bound. It is easy to see that (WL s) s Sliced-PW v, s) as the optimal transport matrices of the two problems live in the same set of constraints and that the cost matrices are the same.
Non negativity. As the cost is distance d, Sliced- (W U, 2
Symmetry. It can be easily shown as by noticing that d( f), (u, 0)) = d( (y) 0). (mi, 0)).
Identity. Let us first consider that v - μ.. It implies that x; yo Vi, hence d(æ;, y,) = 0 <> d((xe, 8), (y., ))) 0, vo. We thus have Sliced-P((Hr, p. = 0, Vs, A.
Let us now suppose that (liced-P((,,r,.5 v, = O. Note 6" the optimal direction. It means that d(x,, 3
0, j. We first consider problem PAWL&, with k L
Let us denote 1r² the active support of 4 and D the active support of v. We straighforwardly have Sliced-PW vG k w) Sliced-PW(1*" 5 k w) 0. As a, by w, miy (0*) is
permutation matrix. We define the injective map f 11,2, kk {1,2, .k) such that
PAWL; = >; (dd((1,)) (1, f())) As we suppose that Sliced-PW (W, v, k-w) = 0, it means that PAWL:
E d(x;, ((a) = - 2; F(()) Vi, but also that E, d(<x,, 8*), (()) (a)) = (d(æ; ) = 0. In addition, as 0* belongs to the unit sphere, and with the assumption of disjointly supported distributions the line, it holds true iif x; f())
We then have μ4 1% when Sliced-PW (W, v, w) 0. The extension of this result for PWL(s) comes directly from Prop. and is omitted here.
Discussion about the triangular inequality. We claim here that, despite having a metric of prime importance for assessing weak convergence for instance, it may be an undesirable property in case of Partial Wasserstein. To illustrate our point, just consider the following scenario: l is a bimodal distribution with one mode of mean m. -2 and m 2 (where most of the samples are sampled according to the first mode), P is another bimodal distribution with one mode of mean m. - and m 2 (where most of the samples are sampled according to the second mode) and third distribution with same amount of mass on the two modes. It is easy to see that, at least for some amount of mass s, the Partial Wasserstein distance between μ and will be greater than the sum of the Wasserstein distance between and a and a and v, which makes sense in machine learning context for instance.
When triangular inequality is sought (e.g. when metrizing the weak convergence), soon as the partial distributions 2²* and u that are at stake are stable over the iterations, one can rely on the metric properties of SWGG. We left investigation of this behavior future work.
A.2 COMPUTATIONAL COMPLEXITY
Proposition 7. As claimed in the paper, computational complexity is O (n log when the cost is the Manhaltan distance and O (Cn?) for any other cost, where C is the complexity of single distance computation.
Proof. One should first note that Algorithms Tand 2 require sorted distributions. Sorting distributions of size is O (n log ni) complexity operation. Let focus the study of the time complexity
19

---

Published as a conference paper at ICLR 2025
Algorithm 3: Computation of chain costs for costs other than the Manhattan distance
Data: Sorted æ. Sorted y. Sorted &
D Precomputat ons (to be performed once and for al1)
Extract all minimal chains from d Uses Proposition
for j E [1..m]] do
6 exists then
Compute c (6))
end
Compute c ((6.-)) using Equation 22
end
Computation of chain marginal cost using eq. and prop. marginal_ cost (6t-p-+) t (66.14+1) -06 - c(6_.e) + (6
of the precomputations presented in Algorithm T (for the Manhattan cost) and Algorithm 3 (for other costs).
Cumulative sums that are computed at line 1 of Algorithm 1 can be obtained in O (n). Then, as stated in Proposition all minimal chains can be extracted from in (n) time.
The loop over j has iterations, and at each iteration:
The existence of 8 can be tested O (1) thanks to the extraction of all minimal chains performed beforehand;
For the Manhattan cost, the computation of c (6)) can be done in O (1) time (cf. Proposi- 5
For other costs, assuming a single cost computation takes O (C) time, the computation of c (167) can be done in O (C card(())) time;
Using Equation
(2) computing (8)) can be done in O (1).
Overall, the computational complexity for this loop is O (n n) in the Manhattan and O (C S), where 5 - car)( for other costs. In practice, O (m) < O I O (n²).
hence our worst-case complexity for this step (C .n?) if the cost not Manhattan. The last step that consists in the marginal cost computation is in all cases (1).
If we now study the complexity of Algorithm) that operates after the precomputations of Algorithm I first notice that this algorithm will have the same complexity whatever the cost, since all required costs computations have been performed beforehand. The first step in this algorithm is initialize the list of candidates with all candidate pairs that consist of neighbors in z. As discussed in Section 3.3 (S1 case), this can be done in O (n) time. Since we rely here on heap queue implementation of the list of candidates in order keep it sorted in increasing order of the marginal costs, the cost is extended to O (n log n)). Then, each of the [ steps of the algorithm, the minimal element is popped from list_ tist_candidates (this is an O (1) operation thanks to our weap-queue-- based sorted list of candidates). Extracting the covering chain of the current samples can be done in O (1) time, as long as one maintains dictionary of maximal chains in the active set throughout the execution of the algorithm.
Algorithm 3
In practice, cleaning could be a costly operation, and we decide to postpone it. In other words, at each step k. need check whether sample x; or yy is already included in A if so, the iteration is skipped.
Finally, insertion in sorted list implemented by heap queue is O (log n) given that the list is of size at most n. Overall, execution of this algorithm runs in O (n log n) time.
Finally, the full execution of our PAWL. solver algorithm takes:
20

---

Published as a conference paper at ICLR 2025
0.4
PAWL(O) PAWL,
0.2-
0.0
PAPAWI
Figure 9: Perturbed PAWL (top) and its gradient (bottom).
O (n n) time if the Manhattan cost is used;
(Cn?) time, or O (CnS + n log n) (where 28 is the size of the largest minimal chain) for tighter estimation, otherwise.
A.3 PERTURBED PAWL.
As noted in the literature (e.g., (Blondel et al.) 2020)), back-propagating through sorting- based algorithms like PAWL poses challenges due to the non-smooth nature of the operations involved. Specifically, if PAWL is treated function of some parameter 0, its gradient be expressed
OC
VAPAWL =
0e
where nt is the optimal transport plan and C' is the cost matrix. However, this gradient is often unstable, making unsuitable for direct use in standard gradient- based optimization methods. To address this, we can leverage perturbed optimizers (e.g., Berthet et al. (2020)), which introduce noise to smooth the optimization landscape.
For illustration, consider a 2D setup where we compute the PAWL. distance between two distributions I and v, projected onto 1D as function of the orientation 0 of the projection direction. Using perturbed optimizer, the smoothed objective PAWL, (0) is defined as:
PAWL,(0) = E2-No. [PAWL + +x)]
where epsilon controls the magnitude of the perturbation. One then Stein's lemma to get the following expression for its gradient (cf. Blondel & Roulet (2024), Section 14.4.5):
V dAPAW.. Ega.No. [PAWIL + c2) PA) :]
Figure 9 illustrates this approach, showing the smoothed PAWL (top) and its gradient (bottom) with Monte Carlo estimation using 1k samples and 0.1. As shown, this perturbation is sufficient to smooth the gradients, making them more stable and suitable for gradient- based optimization neural network contexts.
21

---

Published as a conference paper at ICLR 2025
10
Wi
Average time (in seconds)
PAWL W
TreeGKR
10
10
10
10a
10
10
Number of points x (resp. y)
Figure 10:
Running time comparisons between our PAWL solvers and TreeGKR. Dashed line corresponds to extrapolation based on theoretical complexity.
A.4 ADDITIONAL EXPERIMENTS
A.4.1 INCLUDING SATO ET AL.. 2020 IN THE TIMINGS COMPARISON
TreeGKR (Sato et 2020) is not included in our benchmark of the computational complexities of the partial and unbal lanced optimal transport methods, though it constitutes serious competitor, since ID unbalanced OT problem can be cast to a tree OT problem. Indeed, for samples on the real line, one can build path graph (which is specific kind of tree) such that the distances in ID are reflected on the tree.
Unfortunately, we were unable to reuse code from Sato et al., 2020) on large datasets. As consequence, we present in Figure [0 benchmark that involves TreeGKR for sample size up to 7k. For larger sample sizes, the complexity is extrapolated using the theoretical O log" n) complexity for TreeGKR, for the sake of visualization.
A.4.2 IMPACT OF THE TRANSPORTED MASS ON THE MEASURED TIMINGS
In Figure 4 we provide running times for PAWL compared with two baselines, namely OPT (Bai al. 2023) and Fast-UOT (Séjourné et 2022). Partial transportation problems for all intermediate masses are solved at once for PAWL, but for the baselines, the amount of transported mass is controlled via hyper-parameter of the method. Figure [1 shows that varying the hyper-parameter for OPT does not seriously impact its temporal complexity 2 Note also that the selected values for À cover a wide range of transported mass s.
Similar observations could be drawn for Fast-UOT when varying the o pareeepar
22

---

Published as a conference paper at ICLR 2025
PAWL Wi
Average time (in seconds)
102
PAWL W3
OPT, A 0.0001 meddian(isss))) (5 0.617)
OPT, 2 0.001 (00l-mcdian(ditss) ($ = 0.785)
10a
OPT. 2 0.01 mddiianddssts) ($ 0.897)
10-2
10a
10a
10
10
Number of points in x (resp. y)
Figure 11: Running time comparisons between our PAWL solvers and OPT with varying A. 5 the average transported mass.
23


Reviews:
[{"review_id": "2umrp06KOC", "reviewer": "Reviewer_U54C", "summary": "The paper discusses a novel algorithm and a slicing scheme to efficiently compute PArtial Wasserstein distances on a Line (PAWL) under L1 (Manhattan) cost  which is a variant of the linear assignment problem in $O(nlogn)$. The concept of \"chains\" that are specific patterns formed by the samples on the real line is introduced which enable fast computation of partial Wasserstein distances requiring a sorting operation as precomputation enabling fast computation of marginal and cumulative costs (sums). Authors develop a sliced partial Wasserstein (sliced-PW) scheme to enable sparse approx transport maps thus allowing identification of outliers (OOD samples) without requiring prior knowledge of the amount of noise/outliers. The proposed algorithm is then used in two applications - Wasserstein gradient flow and point cloud registration", "questions": "- Can you suggest some other applications and extensions for PAWL?\n- Is the algorithm usable in training neural net architectures? What is the notion of gradient in this case?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Extends several prior theoretical results to meaningfully solve partial 1-Wasserstein problem on line\n- Introduces concept of chains and efficient way to calcualte marginal/cumualitve sums of cost for chains using precomputing step in O(nlogn)\n- Designed scheme sliced-PW for using PAWL in real world applications like gradient flow and point cloud registration", "weaknesses": "- More thorough experimental evaluation would be great\n- Applications to PU learning or outlier detection might be a good fit\n- Might not be friendly to backpropagation algorithm limiting use in context of deep learning / neural nets", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tAARlOYAHo", "reviewer": "Reviewer_yYXF", "summary": "This paper introduces PAWL (PArtial Wasserstein on the Line), an efficient algorithm for computing partial Wasserstein distances in one-dimensional distributions. The primary motivation is to improve the performance of optimal transport (OT) in scenarios where input distributions contain noise, outliers, or mass mismatches. PAWL enables exact partial transportation, computing solutions for all possible transported mass amounts simultaneously with an optimal time complexity of O(nlogn), making it suitable for large-scale applications. \nExperiments confirm PAWL's computational efficiency and demonstrate its advantages in gradient flows and point cloud registration tasks.", "questions": "* I would like to investigate the effectiveness of the proposed method in higher-dimensional experiments and settings.\n* How does PAWL ensure efficiency when managing the candidate list of pairs in each step, especially as the list grows with larger datasets?\n* What mechanisms are in place to handle cases where multiple candidate pairs have nearly identical marginal costs?\nWhen several pairs have similar transport costs, selecting the best pair could become computationally challenging or introduce instability", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* Paper is very-well written and clear\n* Paper proposes a novel algorithm for efficiently calculating the partial 1-D Wasserstein on the lines in $O(nlogn)$", "weaknesses": "* Experimental designs lacks high-dimensional benchmarks and and PAWL is only tested on toy distributions.\n* Calculating the chain costs is limited to $L_1$ norm and is unable to generalize to $L_2$ norms.\n* PAWL’s incremental pair selection could face challenges when multiple candidates have nearly identical costs, which may lead to ambiguities in choosing the most optimal pairs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GFc0wuQJMK", "reviewer": "Reviewer_aHWQ", "summary": "The paper proposes a new algorithm to solve partial Wasserstein distance on the line which achieves the optimal complexity i.e., $\\mathcal{O}(n\\log n $ for $n$ is the number of supports. The key idea is to choose the best candidate set at each step of the algorithm. With the new algorithm to solve 1D partial Wasserstein, the paper proposes a new semi-metric named sliced partial Wasserstein which selects the projecting direction yielding the minimal transport cost under the lifted partial transportation plan. The paper shows that PAWL (the new algorithm) leads to faster computation than the previous unbalanced approach including optimal transport transport (OPT) and fast unbalanced optimal transport (Fast-UOT).  The paper conducts experiments in gradient flow and point cloud registration to show the efficiency of the proposed method.", "questions": "* Could elbow variant provide the true contamination percentage when the data contains additive noise?\n\n* How could we extend the proposed approach to continuous cases and cases where measures do not having the same weight for their supports?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper addresses an important question in the community which is having a partial Wasserstein variant with the complexity of $\\mathcal{O}(n\\log n)$. Therefore, the proposed variant  can scale to more than 10000 supports.\n\n* The proposed solution is novel including constructing and maintaining a candidacy set.\n\n*  PAWL shows a favorable performance in computation, gradient flows, and point cloud registration compared to existing unbalanced optimal transport solver.", "weaknesses": "* The proposed algorithm requires the supports of two measures having the same weight. This setup might limit the application of the proposed algorithm i.e., the proposed algorithm seems to work well only for point clouds.\n\n* The sliced partial Wasserstein is defined based on SWGG, however, it is still possible to define many other variants of sliced partial Wasserstein by using more projections\n\n* There is no experiment for testing the robustness of the proposed methods and other baselines.\n\n* The application seems to be limited to low-dimension i.e., <= 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SxqgNbw9Ji", "reviewer": "Reviewer_ErWA", "summary": "1. The paper presents a new algorithm for solving the partial Wasserstein problem in a straightforward manner.\n2. It introduces the concept of sliced-partial Wasserstein and discusses its semi-metric properties.\n3. The new algorithm is applied to shape registration experiments, and an evaluation of its performance is provided.", "questions": "1. In the 1D case, what is the difference between \"Manhattan distance\" and basic absolute distance?  \n2. In the repository `repo/baselines/cvpr_2023_bai.icp_xp.py`, it appears that all the baseline methods are not accelerated by Numba; however, Numba acceleration is implemented in the original repository at [yikun-baio/sliced_opt](https://github.com/yikun-baio/sliced_opt). Could you test the convergence time using the original code from [yikun-baio/sliced_opt](https://github.com/yikun-baio/sliced_opt)?  \n3. Can you provide a formal proposition/theorem (with a formal proof) to present the proposed solver's computational cost for solving a partial Wasserstein problem, both with and without the Manhattan metric assumption?\n4. Could you print the transportation plan for the new algorithm in the following partial OT problem?\n\nLet \\(\\mu = \\delta_{x_1} + \\delta_{x_2} + \\delta_{x_3}\\), where \\(x_1 = 0\\), \\(x_2 = 1\\), \\(x_3 = 2\\) (with support on points 0, 1, 2, and each point having a mass of 1), and \\(\\nu = \\delta_{y_1} + \\delta_{y_2} + \\delta_{y_3}\\), where \\(y_1 = 2\\), \\(y_2 = 3\\), \\(y_3 = 4\\) (with support on points 2, 3, 4, and each point having a mass of 1). \n\nThe transported mass is set to \\(k = s = 3\\), with \\(w = 1\\). The cost function can be either the Manhattan distance or the square of the Manhattan distance. When using the squared distance, the optimal transportation plan is \\(x_1 \\rightarrow y_1\\), \\(x_2 \\rightarrow y_2\\), and \\(x_3 \\rightarrow y_3\\). I am curious to see the outcome of this new algorithm.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The classical solver for the proposed partial optimal transport (OT) problem requires $O(n^3)$ complexity for linear programming or $O(n^2 / \\epsilon)$ for the Sinkhorn algorithm. This paper proposes an efficient algorithm specifically for the Manhattan distance in a one-dimensional, empirical distribution setting.  \n2. The sliced-partial Wasserstein (sliced-PW) concept is introduced, and its semi-metric properties are analyzed.  \n3. The authors demonstrate the application of this new algorithm in a shape registration experiment.", "weaknesses": "1. **Regarding Complexity**:\n   - 1.1 If the cost is not based on the Manhattan distance, the computational complexity of the new algorithm is \\( k \\cdot n^2 \\). In the worst-case scenario (when \\( k = n \\)), this becomes \\( n^3 \\). Is this correct?\n   - 1.2 In Section 5.1 and Figure 4, it seems the authors discuss only cases where the cost is a metric. I recommend the following:\n     - (a) Include **(Sato et al., 2020)** as a baseline. The two baselines from **(Bai et al., 2023)** and **(Sejourne et al., 2023)** apply when the cost is not a metric, while Sato's method and the algorithm proposed in this paper are specifically designed for metric costs. In the one-dimensional metric cost scenario, Sato's algorithm appears to have a comparable computational cost of \\( n \\log^2 n \\).\n     - (b) Upon reviewing the anonymized repository (specifically `timing_partial.py`), it seems that only the extreme case of full mass transportation has been tested. I recommend measuring the wall-clock time for various mass transport settings, such as transporting 20%, 50%, and 100% of the total mass.\n   - 1.3 In Section 5.1, the parameters for fast UOT are set as \\( \\rho_1 = \\rho_2 = 1.0 \\), and for OPT, \\( \\lambda = 0.001 \\times \\text{median} \\). However, it appears that the parameter for PAWL (denoted as \\( s \\)) is missing, as I could not find it in the code repository. Could you clarify the missing parameter and explain why the resulting problems are equivalent or comparable under these settings?\n\n2. **Regarding the Semi-Metric Properties of Sliced-PW**: When \\( \\text{sliced-PW}(\\mu, \\nu; k \\cdot \\omega) = 0 \\), it implies \\( \\mu^k = \\nu^k \\), but we cannot conclude that \\( \\mu = \\nu \\) (see lines 998–1002 in the appendix). Therefore, sliced-PW does not satisfy the triangle inequality or identity properties, though it does exhibit symmetry and non-negativity. It appears that sliced-PW was not applied in the experiments, and its potential applications were neither discussed nor demonstrated.\n\n\nMinor comments: \nIt appears that the proposed algorithm primarily addresses cases where $\\mu$ and $\\nu$ are empirical measures with equal mass on each point. If this is the case, setting $\\omega = 1$ makes the equations for (PAWL) and classical partial OT, i.e., Eq (PW), equivalent. Therefore, introducing the new problem (PAWL)  seems unnecessary, as it merely changes the notation of the original partial OT problem. (This comment is only about notation redundancy and does not affect my overall rating.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)