Computing all Optimal Partial Transports
Authors: Abhijeet Phatak
Sharath Raghvendra
CHITTARANJAN TRIPATHY
Kaiyi Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Optimal Transport
Combinatorial Optimization

Abstract: We consider the classical version of the optimal partial transport problem. Let $\mu$ (with a mass of $U$) and $\nu$ (with a mass of $S$) be two discrete mass distributions with $S \le U$ and let $n$ be the total number of points in the supports of $\mu$ and $\nu$. For a parameter $\alpha \in [0,S]$, consider the minimum-cost transport plan  $\sigma_\alpha$ that transports a mass of $\alpha$ from $\nu$ to $\mu$. An \emph{OT-profile} captures the behavior of the cost of $\sigma_\alpha$ as $\alpha$ varies from $0$ to $S$. There is only limited work on OT-profile and its mathematical properties (see~\cite{figalli2010optimal}). In this paper, we present a novel framework to analyze the properties of the OT-profile and also present an algorithm to compute it.  When $\mu$ and $\nu$ are discrete mass distributions, we show that the OT-profile is a piecewise-linear non-decreasing convex function. Let $K$ be the combinatorial complexity of this function, i.e., the number of line segments required to represent the OT-profile. Our exact algorithm computes the OT-profile in $\tilde{O}(n^2K)$ time. Given $\delta > 0$, we also show that the algorithm by ~\cite{lahn2019graph} can be used to $\delta$-approximate the OT-profile in $O(n^2/\delta + n/\delta^2)$ time. This approximation is a piecewise-linear function of a combinatorial complexity of $O(1/\delta)$.
An OT-profile is arguably more valuable than the OT-cost itself and can be used within applications. Under a reasonable assumption of outliers, we also show that the first derivative of the OT-profile sees a noticeable rise before any of the mass from outliers is transported. By using this property, we get an improved prediction accuracy for an outlier detection experiment. We also use this property to predict labels and estimate the class priors within PU-Learning experiments. Both these experiments are conducted on real datasets.

Published as a conference paper at ICLR 2023
COMPUTING ALL OPTIMAL PARTIAL TRANSPORTS
Abhijeet Phatak', Sharath Raghvendra', Chittaranjan Tripathy', Kaiyi Zhang?* Walmart Global Tech, VVirginia Tech jeet. phatak, ctripathy) @walmart.com [sharathr, paarattr,kaiyiz,,, @et.edu
ABSTRACT
We consider the classical version of the optimal partial transport problem. Let j (with mass of U) and (with a mass of S) be discrete mass distributions with S & U and let n be the total number points in the supports of μ and v. For parameter E [0, S], consider the minimum-cost transport plan da that transports a mass of a from V to μ.. An OT-profile captures the behavior of the cost of da as a varies from 0 S. There only limited work on OT-profile and its mathematical properties (see Figalli (2010).. In this paper, we present a novel framework to analyze the properties of the OT-profile and also present an algorithm to compute it. When and are discrete mass distributions, we show that the OT-profile is a piecewise-lincal non-decreasing convex function. Let K be the combinatorial complexity of this function, i.c., the number of line segments required to represent the OT-profile. Our exact algorithm computes the OT-profile in Ó(n2 K) time. Given >> O, we also show that the algorithm by Lahn et al. (2019) can be used to 6-approximate the OT-profile in O(n²) /8 + n/0²2 time. This approximation is a piecewise-lined function of a combinatorial complexity of ((1/8). An OT- is arguably more valuable than the OT-cost itself and can be used within applications. Under a reasonable assumption of outliers, we also show that the first derivative of the OT-profile sees noticeable rise before any of the mass from outliers is transported. By using this property, we get an improved prediction accuracy for an outlier detection experiment. We also use this property to predict labels and estimate the class priors within PU- PU-Learning experiments. Both these experiments are conducted on real datasets.
INTRODUCTION
Given discrete prohability distributions j (with mass of U = 1) with the set A as the support and v (with a mass of 5 = 1) with B as the support, where |A| + |B] = n, in the optimal transport problem, one wishes to compute the minimum cost plan transport mass from to μ. When the mass U f S, the problem is called the unbalanced optimal transport. In the partial optimal transport problem, given parameter a E [0, S), one wishes determine the a-optimal partial transport cost which is the minimum work required to transport a mass of from y to
Owing to its strong statistical properties, the optimal transport cost (Villami (2003): Peyré & Cuturi (2019) is considered to be an attractive dissimilarity metric between probability distributions, and has found numerous applications in areas involving GANs, image processing, (Arjovsky et al. (2017):
Liu et al.] (2018): |Baajii et al. (2020); Lin et al. (202T); |Schmitz et al.] (2018); Chen et al. (2019))
variational inference (Ambrogioni et al. (2018) ), econometrics (Galichon (2066) and other areas of natural science (Schiebinger et al. (2019)) Sun et al. (2020)) and applied mathematics (Santambrogio (2015)). ). Similarly the unbalanced and partial optimal transport has been used for various problems
that arise in machine learning, including GAN training, image processing, outlier detection and
Positive Unlabelled (PU-) learning (Yang & Uhler (2018); Bonneel & Coeurjolly (019); Chapel
al. 2020); Mukherjee al. (2021)).
The exact optimal transport cost and plan, including in the unbalanced case, can be computed in O log time. For a fixed value of [0, S). one can easily reduce the problem of computing an
FFlllowing convention from Theoretical Computer Science, all authors ordered alphabetical order

---

Published as a conference paper at ICLR 2023
a-optimal partial transport cost to solving unbalanced instance of the optimal transport problem in (n log n) time: Create a catchment node r in the support of l with additional mass of (S - a). Let A' = A U {r} be the new support of μ. Note that the total mass of A' is U + - For every b E B, add an edge (r, b) with a cost of 0. To find the a-optimal partial transport, one can simply solve the unbalanced optimal transport between A' and B using an exact solver in ( log n) time.
Several algorithms approximate the optimal transport cost in Onnypoly po (1/6, logn)) time. Cutturi (2013) introduced the Sinkhorn algorithm to solve the entropic regularized optimal transport problem and showed that it can be used to approximate the optimal transport cost within an additive factor of 5 in O(n² /82) time; see also Abid & Gower (2018); Altschuler et al. 2017): 7): Dvurechensky et al. (2018): Lin et al. (2019): Guo et al. (2020); Xie et al. (2022). Since then, there has been significant research on the design of additive approximation algorithms and several algorithms achieve an execution time of Ón /8) (Lahn et al. (2019); Jambulapati et al. (2019); Quanrud (2019)). The state- of-the-art execution time for approximating the Optimal Transport is achieved by the combinatorial algorithm by [ahhn et al. (2019) (LLMR-llgorrthm) Their algorithm is based on adapting a cl classical graph theory algorithm Gabow & Tarjan 1989) and runs in O(n²/8 + n/8²) time. In this paper, we study the classical version of the optimal partial transport problem which we introduce next.
We are given μ and whose supports are the point sets A and B, respectively. Let A,A B) be complete bipartite graph with A U B as the vertex set and A x B as its set of edges. For any a E A (resp. b E B), we associate a mass of Pa (resp. 1b) such that the U = Enes Pa and S= EbEB 4 S U We refer to each point a E A (resp. b E B) to be a demand (resp. supply) point and assume Ph (resp. 1%)) to be a positive rational number. For any pair of points
A and 6 E B, we are given a non-negative cost c(a, b) E R20 bounded by 1. The cost of transporting a supply of mass 33 from b to is 3c(a, b). A transport plan is a function o A x B + Rz that assigns non-negative value to each edge of G indicating the quantity of supply transported along the edge. The transport plan o is such that the total supplies transported into (resp. from) any demand (resp. supply) node a E A (resp. b E B) is bounded by the demand Hta (resp. supply v%) at a (resp. b), i.e., ElEB or (a, b)= = ja (resp. Eae (a, b) = v¹). For any a E [0, S). we say that any transport plan is an a-partial transport plan if transports a mass of a from v to μr, i.e., E(a.)) (a, 6) = a. The cost of the partial transport plan denoted by w(() is given by Σ(a, () (a, b)c(a, b). In the o-optimal partial transport problem, we are interested in finding a minimum-cost a-partial transport [0, S] + Rzo that maps
plan which we denote by d² We define the OT-pproille to be function value a E [0, S] to the cost of w(o") as a goes from 0 to S. For discrete distributions, we show that this function is convex and piecewise-linear. Let K denote the combinatorial complexity of w. Since, OT profile is a piecewise- -ineer convex function, its first derivative is non-decre atep-function We denote this step function as Da where Dw(a) denotes the first derivative of the OT--pooile at a.
Next, we define the notion of a 6-approximate OT-profile. We say that function w S] + Rg0 6-approximates the OT-profile, if, for every a [0, S). w(a) S waa) S w(a) + S8. Recollect that, when and v are probability distributions, U = S = and we get w(a) S w(a) < w(a) + 5. Therefore, ((a) is an additive approximation of w(a) and the function W represents an additive approximations of all optimal partial transports.
From a theoretical standpoint, there is limited understanding of the properties of an OT-profile and its first derivative. In the seminal work by Figalli (2000), he considered the OT-profile of the optimal partial transports for the case where the distributions are continuous and the ground distance c( (u, v) is |/u v/l2. To the best of our knowledge, we are not aware of any other work on OT-profile.
Our Contributions: In this paper, we present a new exact and approximation algorithm to compute the OT- We also provide novel framework to derive properties of the OT OT-profile and its first derivative. Using this framework, we show how an OT-profile can be used to identify points from the outlier class and the inlier class within the support of distribution. All our results apply for any arbitrary cost function -....).
First, we present a simple primal-dua based combinatorial algorithm to compute the exact optimal transport cost. Our algorithm is generalization of the well-known Hungarian method for the
We consider the generalized case for arbitrary and potentially unbalanced case. For the case where y and are probability distributions U and S =
2

---

Published as a conference paper at ICLR 2023
assignment problem. Interestingly, we show that this algorithm not only computes the OT-cost but also traces the entire OT-profile (Lemma [2. and 3.1]. Moreover, as the OT-profile is traced, certain dual weights maintained by the algorithm capture the first derivative values (Lemma (34). By tracking the evolution of these dual weights, we show that the first derivative Dw is a non-decreasing step function (Lemmaa [3.4] and 3.2 (.2 b)) and therefore, w is piecewise- convex function. Our
algorithm constructs w and Dis in O K) time; here K is the combinatorial complexity of w. i.e.
the number of line segments in w.
We further exploit these properties (Lemma 3.4 and 3.2) to show that the OT-profile can be used to detect outliers. Recollect A and B are supports of the distributions μ and v, respectively. ]Let A consists of points from the 'inlier' class (with a total mass of U') and B be a dataset that contains both points B from the inlier class (with a total mass of a²)) and points B= from the outlier class (with a total mass of S - a²)) Let w denote the minimum-coss required to transport mass from B+ to A. We assume that outlier points in B are separated from the inlier points of A as follows: Assumption: For some small ε > 0 and a constant C' > 1, every outlier point 6 E B is at a distance least Cw/s from any inlier point in A. Under this assumption of the outlier points, we show the following lemma
Lemma 1.1 (Outlier Lemma). (A) The (a* - e)-optimal partial transport generated by our algorithm will not transport any mass from the outlier points, and, (B) The first derivative values Dw(a" - =) S w/s and Dw(a" + +e)= 2 Ow/e.
In other words, the first derivative function Dw will show noticeable rise in an interval of width around a². By detecting this rise, we can approximate the values ax* and also mark the inliers and outliers. The proof of Lemma is presented in the Appendix (See Section 7.5p.
We prove that the current state-of-the- the- algorithm (LMR-alge) alggorttt) approximate the OT cost can also generate a 6-approximation W of the OT-profile. The combinatorial complexity of w is only [4/8]. Thus, one can not only approximate the OT-cost but construct an approximate OT-profile in O(n² / / time. However, w is not convex function, its first derivative may be very unstable and therefore does not satisfy any approximate version of the Outlier Lemma (Lemma [.1]. Instead, by drawing insights from our exact algorithm, we describe a non-decreasing step function D that tracks the evolution of certain dual weights maintained by the LlR--algorihmm (see Section 8.2.1
We then show that DWi satisfies an approximate version of the Outlier Lemma (Lemma 8.3
We consider two applications where partial optimal transport has been successful and show how an OT-profile can help in improving accuracy while reducing the need for data dependent parameters. First, we conduct an outlier detection experiment that was proposed by Mukherjee et al. (021)) In this, we are given two sets of MNIST images, one set is the inlier (digits 0-4) the other the mixture containing a -fractononnn of inliers (0-4) and (1 - a²) )-facctio outlier (5-9) data. We can obtain a" by identifying a sharp rise in the first derivative function Dw. Then, we mark the free vertices with respect to a -optimal partial transport as outliers. In contrast, the method proposed in Mukherjee et (202T) depends on an additional data driven parameter that approximates the average distance between inliers. We conduct a second set of experiments for PU-learning that was proposed in Chapel et al. (2020). In this experiment, we are given a small set of positive samples and an unlabelled dataset. We are required to use them and identify (a) the fraction a' of positive samples in the unlabelled set (called the class prior), and, (b) classify all the samples in the unlabelled dataset as positive or negative. Chapel et al. (2020) presented optimal partial transport based method that assumed the knowledge of class prior. In contrast, we use OT-profile to both identify the class prior a* as well as generate set of labels for the unlabelled data. In Figure [] we show the first derivative of the OT-profile for four real-world PU-Learning experiments (See Section 5.2). In each case, one can observe a noticeable jump around the class prior. In both outlier detection as well as PU-Learning experiments, the use of OT-profile leads to a better prediction accuracy as well reduced dependence on additional data dependent parameters.
2 PRELIMINARIES
In this section, we present notations and definitions that are required to describe the exact algorithm. Recollect μ and // are the distribution of demand and supply, respectively. Consider any transport plan a transporting mass from V to μ.. We say that a vertex a E A (resp. b E B) is free with respect if its demand (resp. supply) is not exhausted by a, i.e., paa EseB a(a, b) > 0 (resp.
3

---

Published as a conference paper at ICLR 2023
11000-10
Figure I:
First derivative of the OT-profile for PU-learning Datasets (mushroom, shuttle, pageblocks, and, usps). Notice jump in the first derivative values near the true class prior a².
Vs - a (a, > 0). For free vertices, we refer to Moo - (a, b) (resp. 1/- - -L-EA o(a, b)) as the deficit (resp. surplus) at (resp. b). At any stage in our algorithm, we use AF (resp. Bp) to denote the set of free demand nodes (resp. free supply nodes). Recollect that w(or is the cost of any transport plan a with respect c).
We say that a transport plan a is dual feasible if, for every a E A and b E B, there are dual weights y(a) and y(b) associated with a and respectively such that
v(a) (b)) S c(a.b) v(a) + (b) 2 c(a,b)
if o b)
min min mo} if o b) > O.
(1)
(2)
These are the classical constraints corresponding to the dual formulation of the optimal transport problem. Let Ymax = max [b())) In Lemma 2.1 (see Section f proof), we show that any feasible transport plan a transporting a mass of a that satisfies the following property is an a-optimal partial transport plan:
(C) For every demand (resp. supply) node (resp. b). the dual weight y(a) S (resp. y(b) 2 0) and, if a free demand (resp. free supply) node, then yaa) (resp. y(b) = ymaxx).
To compute the OT-profile, therefore, we incrementally construct transport plan while maintaining (C) as an invariant. By doing so, we guarantee that every intermediate transport plan is also an optimal partial transport plan. We can then use these intermediate transport plans to build the OT-profile.
Lemma 2.1. Let along with dual weights v(-) be a feasible partial transport plan that transports mass of a and satisfies (C). Then, a an a-optimal partial transport plan.
Next, we introduce residual graphs that extensively used in the design of combinatorial minimum- cost flow algorithms. We use ut to denote an edge directed from a vertex u to a vertex v. Given a transport plan a,, can build residual graph Go as follows. The residual graph T, (AU B, E) a directed graph with A U B as the vertex set. For every a E A and E B,
If min(Ha, ) > (a, b) 0, there is a forward edge ba to F. and assign its residual capacity to be min(Ha, } - (a, b).
If0 < (a, I min(Ha, we add a backward edge ab to E with a residual capacity of (a..b)
We would like to note that if (a, 0 (resp. ()a min(Pa, })),, then there is only a forward (resp. backward) edge between a and b in E. all other cases, both the forward edge ba and the backward edge Z are in E. We set the cost of any edge between and b regardless of their direction to be c(a, b). Given partial transport plan a, any directed path in the residual network G, that starts from free supply vertex b E Br and ends at a free demand vertex a E Ar is called an augmenting path. Note that, since the graph is bipartite, edges on any path alternate between a forward edge (directed from B to A) and a backward edge (directed from A to B). Any augmenting path P in G, can be used to increase the total mass that is transported along σ. We describe this process of augmenting o along the path P next. For any augmenting path P from a free supply vertex b to a free demand vertex a, let Sp be the surplus at b and d, be the deficit at a. We denote the bottleneck edge capacity x of an augmenting path P to be the smallest residual capacity among all edges of P. Let
4

---

Published as a conference paper at ICLR 2023
rp min(k, Sb. du) be the bottleneck capacity of the path P. We can augment 0 < k S rp units of + mass along an augmenting path P as follows. For every forward edge ba on the path P. we increase the mass transported from b to to (a, b) aa, b) + k. For every backward edge ab the path P. we reduce the mass transported from to a to ar (a, b) + aa., b) - k. We show that the updated o additional mass of & (See Lemma 2.2)
continues to be a valid and feasible plan that transports Hence, we also refer to this operation as pushing a mass along P. Finally, we define the net-cost of augmenting path Pa Pas
(PP)
Σ
v),
Σ
c(u, v).
TOE forward
THE hackward
By its definition, ((P) is simply the change in the cost of the transport plan when we push one unit of mass along P. Using this observation, we can show the following (see Section for proof):
Lemma 2.2. For any transport plan da that transports a mass of a, let P be an augmenting path in the residual graph and let rp be its residual capacity. For any k E [0, rpl. let oa+k be the transport plan obtained after pushing k supplies along Then da+k is a valid transport plan with a cost w(ox+*) w(a.) + kb(P).
For any ba E AAx x B, the slack of any forward edge ba in the residual network is
s(a, b) c(a, b) y(a) y(b).
(3)
Any backward edge ab in the residual network has a slack of s(a, b) v(a) + v(b) c(a, b).
(4)
For feasible transport plan, all slacks are non-negative. Furthermore, note that if both ab and ba present in the residual network, then the slack is O. The next lemma, whose proof is in Section relates the net-cost of any augmenting path to the slack of its edges.
Lemma 2.3. Consider any augmenting path P with respect a feasible transport plan a. Suppose P starts at a free supply vertex b E By and ends at a free demand vertex a E Ap. Then,
+ ((P) = y(b) y(a) + Σ s(u,
(5)
K
Next, we define any edge (a, b) in the residual graph Go as admissible if s(a, 6) 0. The admissible graph A, is the subgraph of Go consisting of the admissible edges of the residual graph.
Lemma 2.4. Consider a feasible transport plan a that satisfies (C) and let P be an augmenting path consisting of admissible edges that starts surplus node b E B and ends at deficit node a A. Then,
(PP)
Ymaxx
(6)
Finally, given residual network Go, define augmented residual network, (V E) follows. In addition to A U B. the vertex set also contains two additional special vertices s and t. The edge set & consists of two types of edges: (a) Every edge wt E E is also in E. The weight of this edge is set to its slack s su,, v). and (b) For every free supply (resp. demand) node E B₁ (resp. a E Ar), & contains edge sh (resp. at) of weight O. From the definition of slack, it follows that the weight of all edges in the augmented residual network in non-negative. The weight of any directed path the augmented residual network is simply the sum of the weights of its edges.
EXACT ALGORITHM
We begin by describing an algorithm to compute an optimal transport plan and establish a few of its properties. Our algorithm is based the primal-dual framework where it constructs transport plan while maintaining a feasible solution for the dual program for the optimal transport. Then, we show how the intermediate computations in the execution of this algorithm describes the exact OT-profile.
5

---

Published as a conference paper at ICLR 2023
Initialization Step: The algorithm picks initial transport plan where, for every edge (a, A x B, o(a, b) = 0. Let a (initialized to 0) denote the mass transported by a. The algorithm also initializes the dual weights of every vertex v E Ao 0, i.., y(v) 0. Note that a and y(-) together form a feasible transport plan.
Our algorithm executes in phases. Within each phase there are two steps.
First step (Hungarian Search): Execute Dijkstra's 's shortest-pase path algorithm on the augmented residual network Go with the source and t as the sin? This algorithm computes the minimum weight path (or shortest path) from a to every vertex in the graph. For any vertex E A U B, let & denote the weight of the shortest path from to / in Go. and thus, is the weight of the shortest path from s to t. The algorithm then uses these shortest path weights to update the dual weights of vertices. For any vertex E AU B, if L. 2 4, the dual weight of remains unchanged. Otherwise, if l. < f, we update the dual weight as follows: (U1): If v E A, we set y(u) + u(v) - l + ty. (U2): Otherwise, if v E B, we set y(u) < y(v) + 4 E.-
Second step: Let A be graph obtained by adding an additional vertex s to the admissible graph, and, for every free supply vertex b E Bp adding an edge (s, b) directed from to Starting from s, we execute a Depth First Search (DFS) in A to find a path to free demand vertex. Let P' be path returned by DFS that starts at s and ends at a free demand vertex a E Ap. Let P be the path that remains after starting at a free supply node and ending at a free demand node, i.c., P is an augmenting path. Let rp > 0 be the bottleneck capacity of P. We update by augmenting mass of rp along the path P. After augmentation, we update a f a + Tp.
remove the vertex from P.. Note that P is a directed path in the residual graph
The algorithm iteratively executes phases until becomes maximum transport plan (i.e., S). This completes the description of the algorithm.
The dual updates the end of the first step of each phase guarantee that the transport plan along with the updated dual weights remains feasible and there is at least one augmenting path in the admissible graph (See Lemma 7.1 and 7.2 in Appendix for proof). The second step computes an augmenting path P in the admissible graph and increments the mass transported by augmenting the transport plan along P. Using this and the fact that the demands and supplies are rational numbers, we show, in Section /7.1 that the algorithm terminates in finite number of phases with maximum transport plan. Furthermore, we show that our algorithm maintains (C) as an invariant.
Lemma 3.1. The algorithm terminates after executing a finite number of phases. Furthermore, (C) holds for the duration of the algorithm'ss 's execution.
Before we describe the construction of the OT-profile, introduce a few notations. Suppose the algorithm described above executes for q phases. Let (au, oI...., og) be the partial transport plan maintained by the algorithm where dg is the initial empty transport plan and a, is the transport plan at the end of phase i. Let {ag = 0, a1 Qg = 5} be such that a; is the mass transported by d, For any V E AUAAU B, let y: (v) denote the dual weight of v after phase and let y = max 19 (v)). For < i < q, let P. denote the augmenting path computed in phase and rV denote its bottleneck capacity. The following lemma, whose proof is in Section 7.2, will be useful in describing the construction of OT-profile and its first derivative.
Lemma 3.2. For every 1 < i S g. we have: (a) w(o:) = Ei= V and, (b) yinax = Vink + Ea-
Generating the OT-profile w and the first derivative Dw: To generate the OT-profile w. we set p; to be a point (a;, Ej- Ty8Phax) and set w to be the piecewise- linear function given by the sequence of points (Po.Pi..... Pi.....P.p Py)) where each consecutive pair in the sequence is connected by a line segment. We set the first derivative function Da as follows: For a 0. Dw(a) yhax- For
any E aa), we set Dw(a)= = Vinax.
Correctness of the OT Profile: Next, we discuss why w returned by the algorithm is indeed the OT- Observe that, from Lemma and Lemma 3.1 or is an ox-optimal partial transport and from Lemma a), w(as) w(o,) m TyUnnxx Therefore, Po. Pi,..., Py points on the OT-profile w.
a),
Recolleect that and f are special vertices added in the augmented residual network.

---

Published as a conference paper at ICLR 2023
Lemma 3.3. For any 0 < S q and any intermediate value a E a.)) an a-optimall partial transport plan can be obtained by augmenting 0s-1 by a mass of (a - (4-1) along the augmenting path P.. The resulting transport plan has a cost of Ej=1 Ty + (a - 04 04
From Lemma 3.3 (proof in Section 7.3 the point Pa = (a, شزー Ty + (a- -
ala-aa-in a4-1) Vimss) will be
on the OT-profile. The set of points Pa as a goes from 0; to a; will be the line segment connecting Pi-1 = (a:-1: 2j=1 Σi-1 Tyni) and P: = (as, Ej= TyD Note that the slope of this line segment
precisely Viaax. Therefore, we can conclude the following:
Lemma 3.4. For any a E (0), Dw(a) Vinax
From Lemma b), (Vimax .............. Vlanx) is a non-decreasing sequence, w is non-decreasing piecewise- linear convex function.
Efficiency analysis: Each phase of our algorithm requires executing a single Dijkstra's 's shortest- shortest-path algorithm which takes (n²)) time. Therefore, the total time taken by the algorithm is (ggm²) Note that the OT-profile generated by our algorithm also has points, i.e., w = (po: Pl, P1.22 However, if subsequence (pi, Pet.pet......199 .P) are all collinear, one can remove the points that lie between p. and Py to obtain a sparser representation of w. Thus, the number of phases may be higher than the complexity K of w.
Pa)-
Suppose, for every value of a E [0, S]. we assume that the optimal partial transport is unique. In this case, we show (in the proof of Lemma 3.5 presented in Section 7.4 that (ymaxe... ... ylaax a strictly increasing sequence and therefore no three points on the OT- OT -ropooe generated by our algorithm are collinear, implying q = K.
Lemma 3.5. Given two distributions μ and with support set of A and B, suppose the demand (resp. supply) at any point of A (resp. B) is a rational number. Also, suppose, for every value of |J0,S), S). the optimal partial transport unique, then the algorithm described above executes in O( K) time where K is the complexity of the OT-profile.
In order to avoid collinear points, one can modify the second step of the algorithm as follows. In the second step of any phase i, instead of computing single augmenting path in the admissible graph, we can compute maximum flow by using a Ó(n²) time algorithm Chen et al. 2022). By doing so, we can guarantee that at the end of the phase i, there are no more augmenting paths the admissible graph. Thus, Step I of phase i + 1 will adjust the dual weights and create an augmenting path in the admissible graph. Therefore, l, as computed in Step I of phase + is positive and from Lemma (b), we have yith > Vmax Vinxx and yith (pi, Pi+1) respectively. Therefore, we conclude that no three points Pi-1; P;, and P;+1 are collinear points in the OT OT-profile and so the number of phase q is exactly equal to the complexity K of the OT--prfile.
slopes of line segments (pi-1.P.) P.) and
Theorem 3.6. Given two distributions μ and with a support set of and B, suppose the demand (resp. supply) at any point of A (resp. B) is rational number. Then, the OT-profile of μ. and v can be computed in Ö(n² time.
The proof of the outlier lemma (Lemma is presented in the Appendix (See Section 7.5
4 APPROXIMATION ALGORITHM
Next, we show how a single execution of the alg-algorithm (that has an execution time of O(n²/8 n/8²) can be used to compute d-approximate OT-profile with combinatorial complexity of 0(1 The allgaaggo is split into three parts. the first part, the algorithm will scale-and-round the demands and supplies to integers. In the second part, the algorithm finds approximate transport plan using a primal-dual method that is similar in style to the exact algorithm described in Section 3 Like in the exact case, the intermediate computations of this part can be used to compute an approximate OT- Oropllfile. Finally, in the third part, the transport plan is mapped back to the original demands and supplies.
The second part of the LMR algorrtt maintains a partial transport plan a (initialized to 0) and dual weights v(-) (initialized to 0) that satisfy relaxed set of feasibility conditions. This part of the
7

---

Published as a conference paper at ICLR 2023
algorithm executes in phases and terminates when becomes maximum transport plan. Within each phase there are two steps. Similar to the exact algorithm, in the first step, the algorithm conducts Hungarian Search and adjusts the dual weights that there is at least one augmenting path of admissible edges. In the second step, the algorithm computes many augmenting paths and updates o by augmenting it along all paths computed. At the end of the second step, we guarantee that there is no augmenting path of admissible edges. Lahn et al. (2019) bounded the number of phases to q = O(1/0) and the total execution time of the algorithm by O(n" / n//22.. Let do be the initial transport plan and be the partial transport plan maintained after phase i. Let ag = O and a; be the mass transported by 02 and let Fmax be the largest dual weight at the end of phase To approximate the OT-profile, we simply add, for each 0 < i S y the points p; (ax,,((a) w(a,)). ) The approximate OT-profile w is given by the piece-wise linear function (Po. Pl,... ;P,. where every consecutive pair of points in this sequence is connected by line segment. Unlike in the exact case, w is not necessarily convex and its first derivative can be unstable. Nonetheless, we are able to define a step function Dw that satisfies approximate version of the outlier lemma: (0) 0 and for every a E (a,, a++1], (a) = Vmax- Details of the LMR-algon LMR-algorithm, the approximate version of the OT-profile as well as the approximate outlier lemma are presented in the Appendix (see 8 8.2.1
EXPERIMENTS
Experimental Setup:
We conduct experiments for outlier detection as well as PU-Learning experi- ments on synthetic and real world dataset. Our algorithm is implemented in Java and experiments conducted using Python, and executed machine with 2.1 GHz Intel Xeon E5-226834 processor with 64 GB of RAM.
5.1 OUTLIER DETECTION
In this section, we test the effectiveness of our outlier detection lemma on a real-world dataset. Additional experiments synthetic datasets presented in the Appendix 9.4] Our lemma helps identify the inlier mass a based on an observable increase in the first derivative function around a².
Experiment with Real Data-set: In this experiment, we follow the setup of Mukherjee et al. (2021). Denote j as the set of clean data containing n MNIST digits LeCun (1998) from 0 to 4, and v/ as mixed set contaminated by digits from 5 to We set as the mixing ratio of outlier data in the whole dataset, i.e., (1 é)n digits in v are between 0 and 4 and remaining en fraction are outliers that are between and 9. We utilize the L1 distance (Manhattan distance) as the metric of MNIST digits. We execute two sets of experiments, one with = 1k and another with n = 10k images. For each set, we consider = = 0.2, 0.25 and 0.3. Our algorithm computes the OT-profile w and its first derivative Dw. Then, it uses the kneedle method (with a default sensitivity of 1) to catch sudden rise in the first derivative Dw. Thus, from the outlier lemma, we are able to estimate the value of with è (we refer to this as the check point). We then label the images as inliers (resp. outliers) if they are matched (resp. free) with respect to the (1 - opptiiall partial transport. See Appendix 9.2 for details regarding the application of the kneedle method. We repeat the experiments 30 times and report the average and standard deviation of the accuracy. We also conduct the same set of experiments for the robust optimal transport algorithm of Mukherjee et al. (202I). The results are presented in Table
Table 1: Outlier Detection (ccuracy(left) and Check Point Detected(right) for MNIST
Method(n)
é = 0.3 6 = 0.25 e = 0.2
Method(n)
6 = 0.3 E = 0.25 8 = 0.2
ROBOT(14)
0.73
0.77
0.81
OT-Profile(1k)
0.728
0.744
0.792 0.796
OT-Profile(1k)
0.81
0.82
0.85
OT-Profile(10k)
0.754
0.770
ROBOT(10K)
0.77
0.80
0.84
OT-Profile10ok)
0.88
0.89
0.90
Our outlier detection method consistently achieves slightly better accuracy (between 4% 10%). Table (right) shows the the check point detected by our algorithm is very close to value of e (the actual outlier ratio). Note
check point that is automatically detected by our algorithm. Observe that
8

---

Published as a conference paper at ICLR 2023
that the method of Mukherjee et al. 20221) relies on thyeer-paramete that is obtained by sampling μa Our method on the other hand, does not rely on any data driven hyperparameters. In the supplemental MNIST images for ROBOT and OT-profile
material, show visual sample of the miss-classifes approaches. We also provide number of errors made on a sample of n = 2000 by ROBOT and OT-Profile for each digit.
5.2 PU LEARNING
In this section, we apply OT-profile in the context of PU Learning Bekker & Davis 2020). The goal of PU learning similar binary classification problem where labelled positive examples (Iet ni denote the number of positive examples) make up the training set where as the test set consists of positive and negative examples that are unlabelled (let ng denote the number of unlabelled examples). In case of multiple classes, similar approach is followed where the target classes are considered as positive (y = 1) and all the others are considered as negative (y = -1). Following the previous work set up. we applied our approach under the SCAR assumption (selected completely at random) on six datasets from UCI repository, which are: Mushrooms, Shuttle, Pageblocks, USPS, Connect-4 and Spambase and test SAR (selected at random) assumption with colored MNIST. From each dataset, we randomly choose equal number of samples, np = ny = 800 for the positive set as well as the unlabelled set. Experiments are run 10 times, and the mean accuracy and running times is reported.
Recently, Chapel et al. (2200) demonstrated that specific optimal partial transport formulations (namely Partial Wasserstein (D-W) and Partial -aasoo-assserttiinn (p-GW)) can be used for learning positive unlabelled data. In Chapel et al. 2020), is assumed that the true proportion of positives ply = 1)), called class prior is known in advance for
in the unlabelled dataset (denoted by different datasets. π is used to sample the test (unlabelled) set as per the marginal p(æ) = Tp(#ly 1) + (1 - p 1). Both these methods need the knowledge of
On the other hand, we describe an approach that uses the OT-profile w and the first derivative Dw solve the PU-learning task without the knowledge of class prior. We refer this approach as OTP-wo-prior. Since the unlabelled data can have samples from multiple classes, there can be several noticable rise in the first derivative Dw. In such a case, we pick the earliest jump to estimate the class prior. Let Ω be the class prior estimate returned by our algorithm. We then mark all free points with respect to #-optimal partial transport as negative and all other points are positive. We describe our method to detect jump in Dw in the Appendix 99.] We also describe a method assuming the class prior æ is known. æ is known, we simply mark the free points with respect to the --ppttial transport plan as negative and the remaining points as positive. We refer to this approach OTP-w --P-oor
We observed that OTP- nroproo-rroo is both computationally efficient as well as achieves comparable or better accuracy (see Table 2] standard deviation reported in Appendix S than the methods p-W and P-GW proposed by Chapel et al. (2020). Moreover, unlike previous methods, our method does not need the knowledge of class prior which arguably is significant limitation of the work by Chapel et al. (2020). Under SCAR assumption, except for usps and spambase, both OTP-w-prior(italie and OTP (bo-ooo)pror outperform p-W and p-GW. And detected priors close to the real value within 0.2% for mushrooms, shuttle, and pageblocks. Under SAR, OTP-w-prior yields the best accuracy, and OTP-wo-prior has similar result with p-W and P-GW.
Table 2: PU learning accuracy rates(left) and execution time(right) in seconds
p-W p-GW OTP-
OTP-
dataset
π
p-W p-GW OTP-w- prior
ОТP-
W- prior
wo-prior
prior
mushrooms
0.518 96.1
95.2
99.8
99.7
0.517
1.2
83.9
0.6
0.5
shuttle
0.786 96.3
95.5
97.9
97.7
0.785
1.0
82.3
0.5
0.4
pageblocks
0.898 92.4
90.6
93.1
93.1
0.925
1.4
92.1
0.3
0.3
usps
0.167 98.6
95.7
97.3
92.5
0.092
2.1
80.2
8.1
7.5
connect-4
0.658 61.0
55.4
74.7
67.3
0.860
2.2
82.0
1.9
1.8
spambase
0.394 79.8
71.1
73.4
65.9
0.301
1.2
80.3
0.8
0.7
mnist
0.1 99.1
98.4
99.3
98.1
0.081
1.8
82.3
3.1
2.6
colored mnist
0.1 91.6
97.5
99.3
97.6
0.076
1.9
81.8
3.2
2.9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
We would like to acknowledge, Advanced Research Computing (ARC) at Virginia Tech, which provided with the computational resources used to run the experiments. Research presented in this paper was funded by NSF CCF-190917) and NSF CCF-2223871. We would like to thank the anonymous reviewers for their useful feedback.
REPRODUCIBILITY STATEMENT
The code used for the experiments reported in this paper is available at httpp:://gtthbb com/ ka Salyiz/CComutt int.rppuutnn--llllll -opt -ap-rtaaaaaatiiiieeaeeee -partia -transport.
REFERENCES
Brahim Khalil Abid and Robert Gower. Stochastic algorithms for entropy-regularized optimal transport problems. In International Conference Artificial Intelligence and Statistics, pp. 1512-1512. PMLR, 2018.
Jason Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhorn iteration. arXiv preprint 1eXXiv:705.090000 2017.
Luca Ambrogioni, Umut Güęlü, Yagmur Güçlätürk, Max Hinne, Marcel A van Gerven, and Eric Maris. Wasserstein variational inference. Advances in Neural Information Processing Systems, 31, 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pp. 214 223. PMLR, 2017.
Yogesh Balaji, Rama Chellappa, and Soheil Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems Foundation (NeurIPS), 2020.
Jessa Bekker and Jesse Davis. Learning from positive and unlabeled data: A survey. Machine Learning, 109(4)7719-66) 2020.
Nicolas Bonneel and David Cocurjolly. Spot: sliced partial optimal transport. ACM Transactions Graphics (TOG), 183, 2019.
Lactitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial optimal tranport with applications positive-und uantivee learning. Advances in Neural Information Processing Systems, 33:2903-2911 2020.
Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-coom flow in almost-linear time. CoRR, abs/2203.00671, 2022. doi: 10448550//xxxw22233.0067 URL https:: /ttp://////oo.o//10/... 48550/axxiii
2203 00671
Liqun Chen, Yizhe Zhang, Ruiyi Zhang, Chenyang Tao, Zhe Gan, Haichao Zhang, Bai Li, Dinghan Shen, Changyou Chen, and Lawrence Carin. Improving sequence-to-sequene learning via optimal transport. arXiv preprint arXiv:/901 1ete::91100.... 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent better than by sinkhorn's algorithm. In International conference on machine learning, pp. 1367-1376. PMLR, 2018
Alessio Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-560 2010.
10

---

Published as a conference paper at ICLR 2023
H. N. Gabow and R.E. Tarjan. Faster scaling algorithms for network problems. SIAM J. Comput. 18: 1013-1036, October 1989.
A. Galichon. Optimal Transport Methods in Economics. Princeton University Press, 2016.
Wenshuo Guo, Nhat Ho, and Michael Jordan. Fast algorithms for computational optimal transport and wasserstein barycenter. In Interaational Conference on Artificial Intelligence and Statistics, pp. 2088-2097. PMLR, 2020.
Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct tilde (O)((/ssilon)) iteration parallel algorithm for optimal transport. Advances in Neural Information Processing Systems, 32, 2019.
Nathaniel Lahn, Deepika Mulchandani, and Sharath Raghvendra. A graph theoretic additive approxi- mation of optimaa transport. Advances Neural Information Processing Systems, 13:36666-38866 2019.
Yann LeCun. The MNIST database of handwritten digits. http://yanm. lecun. com/exdb/mnist// 1998.
License: Creative Commons Attribution-Shar Alike 3.0.
Hsin-Yi Lin, Huan-Hsin Tseng, Xugang Lu, and Yu Tsao. Unsupervised noise adaptive speech enhancement by peeriminattr-coostraiinn optimal transport. Advances Neural Information Processing Systems, 34, 2021.
Tianyi Lin, Nhat Ho, and Michael Jordan. the efficiency of sinkhorn and greenkhorn and their acceleration for optimal transport. arXiv preprint arXiv:1906.011 2019.
Huidong Liu, Xianfeng Gu, and Dimitris Samaras. A two-step computation of the exact GAN Wasser- stein distance. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 3169-3168. PMLR, 10-15 Jul 2018. URL htttts:::pppceeeeeeee 1iu1 8d. ht.ll
mlr pre.s v
Debarghya Mukherjee, Aritra Guha, Justin Solomon, Yuekai Sun, and Mikhail Yurochkin. Outlie- robust optimal transport. In International Conference Machine Learning, pp. 7850-7860. PMLR, 2021.
G. Peyré and Marco Cuturi. Computational Optimal Transport: With Applications to Data Science. Now Publishers Inc, 2019.
Kent Quanrud. Approximating optimal transport with linear programs. In 2nd Symposium on Simplicity in Algorithms, pp. 1, 2019.
F. Santambrogio. Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling. Springer, 1st edition, 2015.
Ville Satopaa, Jeannie Albrecht, David Irwin, and Barath Raghavan. Finding a" kneedle" in haystack: Detecting knee points system behavior. 2011 / 31st international conference on distributed computing systems workshops, pp. 166-171. IEFF, 2011.
Geoffrey Schiebinger, Jian Shu, Marcin Tabaka, Brian Cleary, Vidya Subramanian, Aryeh Solomon, Joshua Gould, Siyan Liu, Stacie Lin, Peter Berube, Lia Lee, Jenny Chen, Justin Brumbaugh, Philippe Rigollet. Konrad Hochedlinger, Rudolf Jaenisch, Aviy Regev, and Eric S. Lander. Optimal- transport analysis of single-cell gene expression identifies developmental trajectories in reprogram- ming. Cell, (76()):92-943.cm 2019, ISSN 0092-8674. doi: https://do..rrg//..100f....... 2019.01 0119.01.000 1006. 000092677220 07667771933399
URL https: www. www.ncedireeceeeoooceeoeeoooeeee com/ httm://ccec///aacee//lllll/
Morgan A. Schmitz, Matthieu Heitz, Nicolas Bonneel, Fred Maurice Ngolè Mboula, David Coeurjolly, Marco Cuturi, Gabriel Peyré, and Jean-Luc Starck. Wasserstein dictionary learning: Optimal transport-based based unsupervised nonlinear dictionary learning. SIAM Imaging Sci., 11(1):643-67 2018. doi: 10. 1..1137/7MM 1007/1114445 140431. URL wtl.httpss.. fittps://éoi: .erif.org// 1137 7M1 40431
11

---

Published as a conference paper at ICLR 2023
Gang Sun, Alexander Hawken, and Peter Harrowell. The displacement field associated with the freezing of a melt and its role in determining crystal growth kinetics. Proceedings of the National Academy of Sciences, (1707))3221-3426 2020. ISSN 0027-8424. doi: (0.1073//nas..111886. 17.
URL ptRlhttps:/ /tt:://wwwwe pnas. pras orgg//ooneentt11////4445
C. Villani. Topics in Optimal Transportation. American Mathematical Society, 2003.
Yiling Xie, Yiling Luo, and Xiaoming Huo. An accelerated stochastic algorithm for solving the optimal transport problem. arXiv preprint arXiv:2203.008/33 2022.
Karren D Yang and Caroline Uhler. Scalable unbalanced optimal transport using generative adversarial networks. arXiv preprint arXiv: /810. 144. 2018.
12


Reviews:
[{"review_id": "xmL57B5cHr", "reviewer": "Reviewer_Xdgc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the optimal transport (OT) profile. That is, the dependence of the OT cost on the amount of mass being transported from the source measure. The main result gives a characterization of the OT profile as a piecewise-linear function. This characterization gives rise to an approximation algorithm that allows to numerically approximate the entire OT profile. The paper also explores a potential application for outlier detection.", "summary_of_the_review": "I feel that the results are new and interesting. Lately, the Machine Learning community has shown an increasing interest in optimal transport methods, and it is likely that some parts of the community will find the paper interesting and relevant. This is especially true given the more practical nature of some of the results. I am therefore inclined to recommend acceptance.", "strength_and_weaknesses": "The proof of the main result goes by a standard dual characterization of OT solutions. The authors then demonstrate a procedure that takes an OT solution that transports total mass $\\alpha_1$ from the source measure and produces an OT solution of total mass $\\alpha_2$ with $\\alpha_1 < \\alpha_2$. Moreover, it is shown that for any $\\alpha \\in (\\alpha_1, \\alpha_2)$ the OT profile linearly interpolates between the values at $\\alpha_1$  and $\\alpha_2$. Under a slightly restrictive (but probably necessary) assumption of having all costs rational, the above two properties give a complete description of the OT profile. Relaxing the duality condition affords an approximation algorithm for the OT profile.\n\nStrength:\n- The paper studies a relevant problem.\n- The introduced algorithms are practical.\n\nWeakness:\n- The method is not very novel, even if the results are.\n\nSome comments:\n- I would be happy to see a formal definition of combinatorial complexity instead of a footnote. After all, it is a central concept for the algorithms.\n- The fact that the involved probabilities need to be rational should be emphasized, maybe in the Theorem's statement.\n- In the preliminaries section: \"Consider any transport plan $\\sigma$ transporting mass from $\\nu$ to $\\mu$.\" I think the paper adopts the convention that mass is transported from $\\mu$ to $\\nu$.\n- Section 3, first step: I don't think $\\ell_t$ was properly defined.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XMpusBnWU4", "reviewer": "Reviewer_JBGe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors consider the problem of optimal partial transport. In this problem some fraction of a mass distribution over a set of supply nodes, needs to be transported and distributed to a subset of the demand nodes. The amount of mass supplied or demanded by each node as well as the per unit transportation cost between a pair of nodes are given. The goal is to find the optimal way to transport a fraction $\\alpha$ of the supply mass to demand nodes. \nThe authors are interested to find the so called \"optimal transport profile\" $\\omega(\\alpha)$ which is the optimal transport as a function of this parameter $\\alpha$. The proposed algorithm is a modification of an algorithm by Lahn at' al (LMR algorithm) also using ideas from the Hungarian algorithm like augmenting paths. The modification is needed so that the optimal transport cost if found as a function of $\\alpha$ rather than for a fixed value of it. The running time of the algorithm is output sensitive and proportional to the number of linear parts of the output $\\omega$, which is shown to be a piecewise-linear function. In particular, the running time is $O(n^2\\cdot K)$, where $n$ is the total number of nodes and $K$ the number of linear parts of $\\omega$. They also provide a $\\delta$-approximation algorithm that outputs an approximate profile $\\bar{\\omega}$ that has O(1/\\delta) linear parts and can be computed in $O(n^2/\\delta + n\\delta^2)$ time. \nThe applications mentioned in the paper for these algorithms are Outlier detection and PU learning. The reason why the optimal transport algorithm could be used for the former, is that the existence of outliers would result in a \"sudden jump\" in the OT-profile $\\omega$ since for some sufficiently large value of $\\alpha$, some mass has to also be transported through the \"outliers\". ", "summary_of_the_review": "Although it's an interesting adaptation of prior work, I believe the algorithms and techniques are not novel enough to recommend acceptance. \n", "strength_and_weaknesses": "Strengths:\n\n-This paper slightly generalizes and appropriately adapts an algorithm for partial optimal transport. This is further used to improve performance in a couple of real-world applications. \n\nWeaknesses:\n- The algorithms and techniques seem to be similar and heavily dependent on prior work.\n- Regarding prior work, even though the most relevant work is mentioned, the paper is missing a wider overview of prior work on this topic.\n\nMinor comments:\n- In lines 1 and 2 of the Introduction I think $A$ and $B$ should be swapped. $A$ should be the support of $\\mu$ and $B$ the support of $\\nu$\n- Page 2, 4th paragraph,1st line: \"$\\alpha$-approximate\"-> \"$\\delta$-approximate\"   \n- Last paragraph of section 3, line 1: the proof of Lemma 1.1 is not presented there. A reference to the Appendix is missing. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ArNg2RIybEc", "reviewer": "Reviewer_HDeV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In the optimal transport problem, we are given two mass distributions $\\mu$ and $\\nu$ and the goal is to transport a mass of $\\alpha$ from $\\nu$ to $\\mu$ using a minimal cost with respect to a certain distance such as $\\ell_1$. In this paper, the authors look at the problem of computing an optimal OT profile for any particular fixing of $\\alpha$ when the underlying distributions are discrete.\n\nThe authors first show that the OT profile is a piecewise linear function with a non-decreasing convex function. They first give an exact algorithm of time complexity $n^2K$ where $n$ is the support size of the distributions and $K$ is the number of pieces of the OT profile. Then for any $\\delta>0$ they give a $1/\\delta$-factor approximate algorithm for the OT profile using $n^2/\\delta+n/\\delta^2$ time. For designing this approximation algorithm, they use an existing algorithm by Lahn et al.\n\nThen they apply the OT-profile computation to the detection of outliers under a certain reasonable assumption of the outliers. They conduct experiments on the MNIST dataset with outliers and show evidence that their algorithms better the existing algorithm in achieving a better accuracy of detecting outliers.", "summary_of_the_review": "Due to novelty of the algorithm design and the experimental evidence, I tend to accept the paper.", "strength_and_weaknesses": "Strength: the OT problem is non-trivial and has a rich history. The authors give theoretical guarantees of their algorithm before giving experimental evidence of the superiority of their algorithm in detecting outliers.\n\nWeakness: A high-level idea of their theoretical algorithm would have improved the presentation. I think the n^2K bound may be expensive in practice due to a large value of K. The approximation algorithm looks like a straightforward application of Lahn et al.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster