Partial Optimal Transport for Support Subset Selection
Authors: Bilal Riaz
Yuksel Karahan
Austin J. Brockmeier
Venue: Accepted by TMLR ()

Abstract: In probabilistic terms, optimal transport aims to find a joint distribution that couples two distributions and minimizes the cost of transforming one distribution to another. Any feasible coupling necessarily maintains the support of both distributions. However, maintaining the entire support is not ideal when only a subset of one of the distributions, namely the source, is assumed to align with the other target distribution. For these cases, which are common in machine learning applications, we study the semi-relaxed partial optimal transport problem that relaxes the constraints on the joint distribution allowing it to under-represent a subset of the source by over-representing other subsets of the source by a constant factor. In the discrete distribution case, such as in the case of two samples from continuous random variables, optimal transport with the relaxed constraints is a linear program. When sufficiently relaxed, the solution has a source marginal with only a subset of its original support. We investigate the scaling path of solutions, specifically the relaxed marginal distribution for the source, across different relaxations and show that it is distinct from the solutions from penalty-based semi-relaxed unbalanced optimal transport problems and fully-relaxed partial optimal transport, which have previously been explored. We demonstrate the usefulness of this support subset selection in applications such as color transfer, partial point cloud alignment, and semi-supervised machine learning, where a part of data is curated to have reliable labels and another part is unlabeled or has unreliable labels. Our experiments show that optimal transport under the relaxed constraint can improve the performance of these applications by allowing for more flexible alignment between distributions.

Published in Transactions on Machine Learning Research (12/2023)
Partial Optimal Transport for Support Subset Selection
Bilal Riaz
bilatria Gudel edu
Deportment of Electrical & Computer Engineering
University of Delawore
Yüksel Karahan
Soorahan@udelle edu
Deportment Electrical & Computer Engineering University of Delawore
Austin J. Brockmeier
Modoll&uudel.cm edu
Department of Electrical & Computer Engineering
Department Computer & Information Sciences University of Delawore
Reviewed on OpenReview: https: // openreview. net/ forum? id= 75CcopPaIr
Abstract
In probabilistic terms, optimal transport aims to find joint distribution that couples two distributions and minimizes the cost of transforming one distribution to another. Any feasi- ble coupling necessarily maintains the support of both distributions. However, maintaining the entire support is not ideal when only a subset of one of the distributions, namely the source, is assumed to align with the other target distribution. For these cases, which are com- mon in machine learning applications, we study the semi-rclaxed partial optimal transport problem that relaxes the constraints on the joint distribution allowing to under-represent subset of the source by over-representing other subsets of the source by constant factor. In the discrete distribution case, such as in the case of two samples from continuous random variables, optimal transport with the relaxed constraints is linear program. When suffi- ciently relaxed, the solution has a source marginal with only a subset of its original support. We investigate the scaling path of solutions, specifically the relaxed marginal distribution for the source, across differrnt relaxations and show that is distinct from the solutions from penalty-based semi-relaxed unbalanced optimal transport problems and fully-relaxed partial optimal transport, which have previously been explored. We demonstrate the use- fulness of this support subset selection in applications such as color transfer, partial point cloud alignment, and semisupervised machine learning, where a part of data is curated to have reliable labels and another part is unlabeled or has unreliable labels. Our experiments show that optimal transport under the relaxed constraint can improve the performance of these applications by allowing for more flexible alignment between distributions.
1 Introduction
Measuring, and subsequently minimizing, the dissimilarity between two distributions or data samples are ubiquitous tasks in machine learning. Recently, the theory of optimal transport and the family of Wasserstein distances have
applications across the spectrum of machine learning problems including computer vision [Solomon et al.) 2014;
Kolouri et al.) 2017
Rabin et al. 2011 Garg et al. 2020), generative modeling Salimans et al. 2018 Genevay el. al. 2018 Tolstikhin et al.
Arjovssy et al. 2017 Gulrajani et al.) 2017
2018 Kolouri et al. 2018 Deshpande et al.
2018: Rout et al. 2022 Korotin et al. 2023 Mokrov et al.
2018). and domain adaptation (Kirchmeyer et al.) 2022). Optimal transport is widely applicable since it combines the statistical and geometric aspects of data and provides correspondence to couple two samples distributions.
2021 natural language processing (Xu et al.

---

Published in Transactions on Machine Learning Research (12/2023)
However, limitation of standard optimal transport is the strict constraint on the complete transfer of mass between the two distributions being compared (Frogner et al. 2015). This can be problematic in cases where such a transfer is not necessary or desirable, such as when dealing with distributions with different support, over- or under-repreeenntaion. or the presence of outliers in a portion of the data. In order to deal with
these scenarios partial optimal transport problems (Rubner et al. 1997 Figalli 2010 Caffarelli & McCann 2010: Bonneel & Cocurjolly, 2019; Chapel et al., 2020j have been proposed. Partial optimal transport relaxes the marginal constraints on the transport plan to inequalities, allowing transportation plans that cover only fraction of the total mass. Similarly, unbalanced optimal transport corresponds to the case of unbalanced masses, where only portion of the mass is transported. One or both of the marginal constraints can also be relaxed by divergence-based regularizations, such as Kullback--eibler divergence, total-variation distance (equivalent to the 4-norm of the difference in mass vectors in the discrete case), or squared lz- norm (Benamou 2003 Chizat et al. 2018 Blondel et al., 2018: Peyré & Cuturi 2019 Séjourné et al. 2019; ).21). The solution of partial or unbalanced optimal transport often selects a subsct (also known as an active region) of the support. This property is exploited in machine learning (Chapel et al., 2020 2021; Phatak et al. 2023), including the partial Wasserstein covering problem, which has applications in active learning (Kawano et al. 2022).
Chapel et al.
In practice, a key limiting factor is the scalability of solving the linear programs corresponding to partial, unbalanced, or standard optimal transport for large data sets. While efficient gradient based methods canmot be applied to linear programs directly, a number of regularization based remedies, including entropic (Cuturi
2013 Cuturi & Peyré, 2018), quadratic, and group-LASSO regularization (Flamary et al.] 2016 Blondel et al. 2018) have been shown to give approximate solutions. In particular, the Sinkhorn algorithm provides solution to the entropically regularized standard optimal transport problem. The Sinkhorn algorithm has
been widely applied due to its simple implementation consisting of alternating projections to the feasible sets of marginal constraints. In the work by Chizat et al. (2018), Dykstra's algorithm|] is used to solve the entropically regularized partial optimal transport problem. Similarly, Sinkhorn-like iterations are used for entropically regularized unbalanced optimal transport in the work by Frogner et al.] (2015), and the work by Séjourné et al.] (2019) adapts the Sinkhorn algorithm via asymmetric proximal operators to handle a variety of divergence- baseed relaxations. Scalability is even more important in cases where the solution different levels of relaxation are sought. Recent works have proposed algorithms for computing the entire scaling or regularization path of solution for fully-relaxed partial optimal transport. (Phatak et al. 2023 and unbalanced optimal transport problems with fully or semi-relaxed marginal constraints (Chapel et al. 2021b.
In this paper, we study a discrete case of partial optimal transport (Figalii 2010 Caffarelli & McCann 2010
which is posed as a linear program, where the solution is joint distribution with one fixed marginal and one marginal that is constrained to be pointwise less than or equal to constant factor c 2 1 of the original, typically uniform, marginal. The generalized form of this constraint where each point has its own capacity factor was proposed in the work by Rabin et al.] (2014). Initially, we propose an entropically regularized version to efficiently find an approximate solution, which is equivalent to a specific case within the framework covered in the work of Séjourré el al. (2019), that we solve with an algorithm that combines Sinkhorn-like projections with an accelerated proximal gradient method.
As the regularized solution is not sparse, and sparsity of transport map is essential for support subsct selection, we adopt an inexact Bregman proximal point method (Xie et al. 2020) to yield solutions closer to the original, unregularized, linear program. The work by Xie et al. 2020 is based on the observation that solving the entropically regularized optimal transport problem is equivalent to a Bregman proximal point evaluation with Kullback-Leilber divergence as proximal function. As a proximal point method that uses exact proximal point evaluations is computationally expensive, an inexact proximal point evaluation, where only a few inner Sinkhorn iterations are used, is used to make the algorithm efficient. In our case, the computational complexity on the same order as the accelerated proximal gradient method, but it returns solution much closer to the linear program for the semi-relaxed partial optimal transport problem. While other regularization-baseed methods may induce sparse support, the regularized solution will generally be distinct from the linear program's 's solutions.
I Dykstra's algorithm can find solutions at the intersection of convex, not necessarily affine, sets.
2

---

Published in Transactions on Machine Learning Research (12/2023)
The contributions of this paper are the following:
We motivate and study support susbset selection (SS) specific formulation of semi-relaxed partial optimal transport problem for selecting a subset of a source distribution, parameterized in terms of a single scalar c for a fixed target distribution.
We study the solutions obtained along the scaling path for various values of c, and compare the solution path to fully-relaxed partial and divergence-based semi-relaxed unbalanced optimal transport problems.
We develop an accelerated proximal gradient method-based algorithm to solve the entropically regu- larized version and adapt the inexact Bregman proximal method- based approach for optimal trans- port (POT) (Xie et al., 2020) to mitigate the effects of entropic regularization detailing an algorithm SS-Bregman that yields solutions close to the linear program formulation for subset selection and is as scalable as the Sinkhorn algorithm.
We apply SS-Bregman to applications including color adaptation, partial distribution alignment, partial point cloud registration problems, and positive-unlabeled learning (Bekker & Davis 2020).
We incorporate the subset precctio-bbsedd approach into a semi-supervised loss function for training a neural network-based classifier, which computes the optimal transport based on the learning representa- tion.
2 Methodology
In Section 2.1 relevant preliminaries related to discrete optimal transport along with formulation of subset selection problem are discussed. In Section 2.3 the entropically regularized support subset selection problem and an algorithm to solve it are discussed. In Section [2.]] an inexact Bregman proximal point method to better approximate the solution of the unregularized support selection problem detailed.
Notation: The set of the first n natural numbers {1.2...., n), is denoted by [n]. The set of integers is denoted by Z. The ceiling function defined real numbers floor function defined on real numbers x E R is [x] = max E Z n S x}. The n-dimensional real vector space is denoted by R". Vectors are typeset in lowercase bold (æ:); matrices are in uppercase bold (X); and bold is dropped when an element are referenced by subscripts (x4, When needed for clarity, elements will be referenced by subscripts on square brackets ([x1);, (X2li)) The set of non-nogative vectors in IR", known as the non-negative orthant, is denoted by RT. The n-dimensional vector with all elements equal to unity is denoted by In and the m-by-n matrix with all unity elements denoted by 1mx-- For vectors and matrices, the symbol & denotes element-wise less than or equal to, and x denotes element-wise greater than equal to. The set denoted by An = fx E R" Ei= 24 =}} is the probability simplex. The element-wise product for vectors and matrices is denoted by the @ symbol. The element-wise division for vectors and matrices is denoted by the @ symbol. The diagonal operator is matrix valued map D RR" + Rax", such that [D())]a = x4 V i E [n] and [D(x)lip = 0 i + j E [n]. For x E R", the é1, l2 and too norms are given by ||ж|||| = Σ, lxgl. ||m||a = (E, (mp and ||=|| = max [ respectively. Both, the Euclidean inner-product for æ, y R given by E.0. and the Frobenius inner-product for X, Y E Rmxn given by Em Ez=1 XtyYen are denoted by (:.). The element-wise exponent of vector matrix is denoted by exp(.) and the element-wise logarithm of a vector
IR is [a] min(n Z 2 x)- The
matrix is denoted by log(.). For a matrix X E Ruxx,, its non-negative part is represented by X+ or [X]+, with matrix components given by [X]],] = max(X,;; 0} V E [m]. j E [m]. Similarly, the non-positive part of matrix X E R=x" is denoted by X_ or [X]_ and contains matrix elements [x-] = min (X,, 0) i E [m] and j E [n]. For a vector & E R,, both x+ and x_ denote the non-negative and non-positive parts respectively. We denote
x The set of vectors {e form the
the indicator function of the singleton set {2) as 5=(x)=
0. x *
standard basis for R2_ where [es]: 1 and [ei], for i +
3

---

Published in Transactions on Machine Learning Research (12/2023)
2.1 Problem Formulation
We consider the discrete optimal transport between two weighted samples of size m and corresponding to random variables X ~ defined on fx!*) J C R² and Y ~ V defined on } C R2, with probability
measures Jr Ei=1 (1) and Myan for probability masses μ Am (with {u = p)=(0))=² and V E A. (with {u, = "1 respectively. Let d E x R + R+ denote a distance function. In practice, this is often the Euclidean distance metric between the points d(x, y) = the p- Wasserstein distance (to the p-power) between i and v is expressed in terms of the cost matrix M, where M, = dx (x) y() Vi E [m]. E [n] the cost associated with transporting x(() to y as
Given 1 1 p S co,
Wz(,v)
min P=O
(P,M) s.t. PI, - n. 1_1m= -,,
(1)
where P is the transport map and T PI, - = = 1. The constraints ensure that any solution p is a joint distribution that couples the target marginal μe and the source marginal v. (In the computational optimal transport literature, f is referred to as the target and v as the source.) Therefore, any Wasserstein distance requires the complete mass transfer between a fixed source and larget.
In partial optimal transport (Figalli 2010), the marginal equality constraints are replaced by the inequalities Pl, & n. 1m < V, and the equality 1, P1, = 8: f E RT and v E R may not have equal mass; and the transport map need only transport fraction of the total mass s [0. min [|][]]]]
Motivated by machine learning scenarios with trusted target sample of data and additional source of data which cannot be assumed to be of uniform quality, we focus on the semi-relaxed case, where the constraint on the target is fixed P1, fe with || = 1, ensuring the total mass constraint, but relax the constraint on the source, allowing mass to redistribute among the source points v" = 1_1, I cv, where e 2 is a scaling factor and |||]]] = 1. The resulting partial optimal transport problem which we refer to
as subset selection (SS), is
min
(P.M) s.t. Pl, = 1_1m & cV. P&O
(2)
Let P denote optimal solution, then the source's 's new mass is = P 1m- Since 1, P:I,, ||e = 1. Intuitively, this problem allows the new mass of some source points that have relatively lower cost to increase by a factor of e of the original mass, which enables highor cost source points to have less or even zero mass. In other words, due to total unit mass constraint, the mass increment at one source point results its decrement at other source points. The subset of the source points selected is supp(u?), where supp(.) indicates the support of vector, i.e., the indices of the points with non-zero mass.
To explore the relaxed constraint set, consider the case of uniformly distributed mass = 1,1n and express the constraint as 1 & Lll,, where 0 < L S n and e T. For fixed value of L, the set of feasible source marginal distributions form a polyhedral set E((1) C A, bounded by linear inequalities parameterized by L. The set of feasible source marginals =((-) is defined as =(-)) {x A. < + 1.). The set = for different values of L are given in Figure
| Using combinatoric reasoning we deduce the number of vertices of ! defining the feasible set for the source marginals.
Remark 1. For the support selection portial optimal transport problem with n > and v 1 1n, by defining I. :; the inequality construint can be written PT Imm $ 1 Extreme points of E/!] can be characterized as follows;
For 0 < LLS 1, the entire probability simplez An is feasible due to the fact that in this case the vertices of the probability simpler correspond to extreme points of feasible set.
For 1 < L<2 2 and n > 2, the feasible set (L) has n(n - 1) number of vertices, which can can be written as as conver combination e + (1 t),,, where i,j E [n] and i + j.
For 2 the feasible set E(2) (2) has n(n-1) vertices given as _ + e;) for # j.
2 An equivalent set of constraints Pl P. 1 & ev, 1T
4

---

Published in Transactions on Machine Learning Research (12/2023)
More generally, the number of eatreme points of the feasible set Ex is
n!!
- - - Mn [4]
L DM''
I.
with the vertices given as the set of possible multi-set permutations of the vector:
[L]
terms
Berms
1
terms
terms
I I TI. ... I
0
(3)
Thus, when L L27 2 is an integer, which corresponds to c c uniform distribution of mass across support of cardinality L == on the other marginal the optimal solution may be convex combination of these vertices.
R and 1 mod O the vertices correspond to C e However, due the equality constraints
Since the amount of mass to be transported is constant, when the scaling parameter с is increased (or oquivalently, when the value of L is docreased) starting from c = 1, the behavior of the coupling P and the marginal ve = (Pt)) TT,, 1n in the transportation problem affected. This behavior depends on the structure of the cost matrix M and leads a redistribution of mass, assigning more mass to certain points and less others. At c = 1, corresponding to standard optimal transport, all source constraints are active, meaning that all constraints in the problem are considered. As the value of c is increased, constraints become inactive, which roists depends on the structure of the cost matrix M and the distributions. Once a point's mass goes to zero it never re-enters the support for larger values of c. These observations follow from the linear nature of the problem. Analogons solution paths have been studicd for fully-relaxod optimal transport (Phatak et al., 2023) and fully or semi-relaxed regularized unbalanced optimal transport (Chapel et al. 2021p. Once e reaches c², all inequality constraints are inactive and can be discarded. After this breakpoint c*, any further increments in do not affect the resulting transport plans. In other words, for 2 c², the transport plan P remains the same as P which is solution that can found by greedy algorithm. The exact value of e* can be determined analytically, based on the possible greedy solutions. The analytical expression for c* depends on the propertics of the cost matrix M and the constraints involved,
Σ.
max jEIn]
(4)
Vjj
where the matrix Q is found by nearest neighbor scarch,
Mi: j arg Mik i [m].. E [n].
Qu
(5)
0,
otherwise
P.: is a greedy solution with non-zero entries taken from Q by taking one non-zero element in each row, breaking ties arbitrarily. Thus, as a varies from 1 to c², SS varies from standard optimal transport to a nearest-neighbor transport.
For more flexibility, a designer can provide an upper-bound on the mass assigmments to source points by Ç RR. with ||[|/ 2 (equality corresponds to standard optimal transport), which adds the flexibility in designing partial optimal transport problems that allow variable ranges of masses for the source points. The upper-bound can be expressed in terms of a capacity vector RT such that Ç k @ as introduced in the work by Rabin et al. (2014). For larget distribution and source upper-bounding measure < = En= which is not necessarly a probability measure, the support subset selection problem can be stated as
Sp(u, () min Px0
(P,M) s.t. Pl, 14, 1 C.
(6)
and related to the p- Wasserstein distance (to the p-power) by Sp(u, ((M,)))sa S) Sp(u, WP(,,)) for c c
2.2 Relation to Prior Work
While we consider a purely lincar program consisting of a semi-relaxed partial optimal transport, prior work includes fully-relaxed partial optimal transport and a variety of non-linear approaches for fully or semi-relaxed partial and unbalanced optimal transport.
5

---

Published in Transactions on Machine Learning Research (12/2023)
1.0
1.0
0.0
0.0
0.0
0.0
08.0 0.5
8.0
0.5
0.0
0.5
0..0
1.6-0
0.5
1.d.0
0.5
1.6.0
0.5
1.0.0
(a)
(b)
(c)
(d)
Figure 1: The feasible set =(L) of the source's new marginal distribution given uniform distribution v for
different values of For 0 < < 1 the whole probability simplex is feasible. (a) -= 1.3, six vertices will
exist for 1 < L 2. (b) L = 2 yields vertices. (c) L = 2.2, 2 < < also give 3 vertices. (d) L = yields
singleton set corresponding the original uniform distribution.
2.2.1 Divergence-basee semi-relaxed partial and unbalanced optimal transport
Many relaxed approaches for unbalanced and partial optimal transport penalize the divergence of the marginal from the source and/or target distribution (Rabin et al., 2014 Frogner et al. 2015 Chizat et al. 2018
Séjourné et al. 2019). Many of these also use entropic regularization for scalable algorith since en- tropic regularization of the joint distribution defining the transport plan can be cast as the Kullback-Leibi divergence between the joint and the product of the marginals. The works by Chizat et al.) (2018) and Séjourné et al. (019 provides
extensive framework for entropic regularization and düvergence-basee re- laxations. The latter work (Séjourné et al. 2019 mentions the adjustments necessary to perform asymmetric marginal penalty case for the semi-relaxed case.
The Bullback-Leibles divergence is a member of the wider family of f-divergences that have been adopted relaxed and semi-relaxed optimal transport (Chizat et al. 2018: Séjourné al. 2019). In the discrete distribution case p. q E An, these divergences can be expressed as (p E ( where & the
generating function of the divergence. Notably, :p() = KL(r) := r log r
the generating function for
the KL divergence, and (p(r = TV(r) := lr - 1/ is the gencrating function for total variation, which in the
discrete case equivalent an fı-nrrm based distance: Drv(pllg) = E 9: l 1| = p
The family of semi-relaxed optimal transport problems with divergence penalty 1 > 0 on the marginal is
SRW (,, = min 20 (P.M) + 1 D. 1m v) s.t. Pl = p
(7)
The choice p(r) = (r) = 0,
r E [0,
oe, otherwise, yields range constraint to the interval of [0, c] for the ratio
of the source marginal (Chizat et al. 2018 Séjourné et al. 2019 which equivalent to Sp(4, cv) for any value of p and 2 1: SRW too.e (14, v)
(p, cv).
More generally, one can consider penalties which are not f-divergences such as those based fx-norr Dia (PT 1m p) :=
1mm oo and the squared norm De, (P 1m [p] ())= := : 1 1m 1 Benammu, 2003 Blondel et al. 2018: Chapel et al. 2021). The work by [Chapel et al. (2021) details regularization path algorithm for finding the breakpoints in terms of p of the piecewise linear related solutions along the path and efficiently calculating the solutions via rank-1 updates of matrix inverse required to solve the sequence non-negative, penalized linear regression problems.
Solutions all of the penalty forms can also be found via equivalent constraint castrrait--bsod optimizations with the constraint. Di (PT,ml) mmll v) & a, where 2 0. In partieular, for 2 Sp(u, the SS problem 2 is

---

Published in Transactions on Machine Learning Research (12/2023)
equivalent to the constraint-baser optimization with the -nom based penalty by letting 1, since
1IPT1mm 1m) @ 1, Vj [m], ()-a)u; - P m S (a + 1)1; = (2 - c)v き P 1m - cv
Vj [n], -av; 1 [P] mmlj -V avj
where the lower bound is non-positive for c 2 2. However, for < c < or for other choices of De the feasible set of the marginal differs from the lincar program.
The work by Rabin et al. (2014) presents semi-relaxed optimal transport that combines additional f-normm penalty the capacity's deviation with an inequality constraint on the marginal, which ensures the problem in terms of the transport plan P stays lincar,
min =0
(P, M) + - In/
min P =0
Ic (P,M) + 1- 1n
C=KOM
RER-
CER
s.1.
-4 P SKOU, (K, 21
s.L.
=4, P < 1 1.
For given p. there is value of a 0 such that the constraint-based optimization problem
min P 20 CER
(P.M) s.t. PI ,4, 1 5 S. 5 11 15 1,/1 sa,
(8)
has an equivalent solution. The f--norm based divergence constraint will induce sparsity in the deviations between ② v and 1,, such that many of the points maintain the corresponding value of v. In the uniform distribut case v 1 I,, the solution for Ç has a maximum value of a such that Ç @ v =a the vertices x
of the feasible set for the constraint based formulations include permutations of the vector
teris
a -a-aa
This can be compared to the vertices of the feasible set for the marginals of the SS problem 2 explored in Remark [ which have more uniform distribution of mass. More uniform mass distribution is motivated by the maximum entropy principle and desirable such as machine learning tasks such as semi-supervised learning where the goal is augment the learning based on additional diversity.
By replacing the 4--orm with the -orm in the capacity-basse optimization problem can be related to Sp(u, cv) for all values of e 2 1 by setting = c- since Çj is only involved considering the lower bound of (2 c)u/, for [P 1m1] = >m problem
upper bound, no longer 2i=1 Poj I Sj S cvj Vj E [n], yielding the SS
2.2.2 Strictly uniform, semi-relaxed partial optimal transport
The work by Chapel el al. 22000 introduced in the context of posilive-unlabeled (PU) learning, further constrains the semi-relaxed partial optimal transport problem such that the non-zero source masses must be 1 the PU Wasscrstein optimal transport problem is
n.
- (T.M) s.t. I = Tl, $ m - T 1m E (0, n
min T =0
(9)
Due to the constraint that the marginal source masses are in the set {0, }} this problem not a linear program and only has a non-empty feasible set when s mod 1/n = 0, since must be an integer multiple of L. which an analogous condition to having a uniform distribution among the support discussed in x Li1n, then the problem is equivalent to semi-relaxed SS problem 2 which by the linearity of the problem may result in a solution satisfying the original constraint T E 00 1m To solve this combinatoric problem, the work by Chapel et al. (2020) obtains the solution to convex minimization problem involving group LASSO regularization and additional dummy points, as in problems for unbalanced optimal transport (Guittet) 2002) to account for dropped mass. The solution to this problem will create strictly uniform distribution (after renormalization) amongst the selected subsct of the source marginal. That is, the group LASSO regularization induces a solution whose marginal is a vertex of the feasible set. discussed in Remark 1
Remark 1 If this constraint is relaxed to T 1mm

---

Published in Transactions on Machine Learning Research (12/2023)
2.2.3 Fully-relaxed partial optimal transport
While the formulation we adopt for subset selection is only for the source marginal (a semi-relaxed formulation of optimal transport), partial optimal transport formulations can achieve support subset selection on both
marginals using a fully-relaxed optimization (Figalli 2010 Phatak et al. 2023 Adapting the notation in
the work by Chapel et al. (2020), the partial optimal transport problem
(MP( == min M) s.t. Th. H. T 1m V, 1 T1, =s
(10)
where & E (0, is the fraction of the mass transported. When the source distribution is uniform 1 after renormalization P = LT, the feasible set for the source marginal P 1m consists of permutations of the vector
ns terms
n(1-s)
0
72.8
12
which are also the vertices of the feasible set of the marginals for the semi-relaxed SS problem 2 explored in Remark [ with L = ns. We note that solutions for the fully-relaxed problem are more likely to have marginals with this form due to the lack of the equality constraints for the target marginal, as compared to the semi-relaxed SS problem. However, the main difference of the fully-relaxed approaches compared to our semi-relaxed SS approach (or other semi-relaxed approaches) is that points in the target may lose be completely dropped, which is not ideal when the goal is to filter the source distribution for any points similar to the target distribution.
The fully-relaxed optimal transport can be directly related to the divergence-basel unbalanced optimal transport problem,
FR (1, min (P,M) 1 (Po ()) + +D (P mmll D))) P =0
(11)
There exists a value of p 2 such that the fully-relaxed optimal transport with modified cost matrix M' M- 1 1 and total variation divergence penalties on both marginals will yield the same solution as PWp(H, s) Caffarelli & McCann (010 ; Chizat et al. (2018); Séeourné et al. (019). However, as discussed
above, a total variation or Ea-bad penalty on only the one marginal with an equality constraint on the other induces a different solution.
For c= 2 1, the fully-relaxed partial optimal transport problem is
min P²O
(P.M)
min T
c(T
(12)
s.l. Pl & eu, P swv, Pl, 11,
s.t. T1, & H. T x <V, 1,,,, c
where T !P. Based on equation 12 c. PWg(, w; 2) is the cost for an optimal transport plan with fully-relaxed constraints P1, ep and PT Im & cv.
The recent work by Phatak et al. (2023) studies the value of (ss) = PW v) across all values of s E (0. 1]. which is known as the Or-profile as introduced the work Figalli (210)). In the work by Phatak et al. (2023), w(s) shown to be piece-wise linear convex function of 8, and the entire profile can be computed exactly and approximated efficiently. Furthermore, derivative of with respect to can be used find mass fraction where the partial transport separates inlicrs and outliers Phatak et al. (2023)
To relate the fully-relaxed to the semi-relaxed partial optimal transport, we consider the unbalanced partial OT-pprfile function to denote the case where the target marginal is also scaled down by such that it is wholly transported
(sp, min (T.)) s.t. T1, & sp,, T XV, 1 TT,, 20
8

---

Published in Transactions on Machine Learning Research (12/2023)
Let 1, then our proposed subset support cost is
Sp(p1 v) min (P.M)
1
1
min
- (T,M)
P =0
T >0
8
s.t. 1 Pl, =1,
s.t.
1, =
1
P n4, P x -v
T1, $ spc, T 1 $ v. 1m
Thus, Sp(H, (1) (sp v;)) and (H,, = PW v; () with optimal solutions related by P ! Based this relation explore the adoption of the knee finding algorithms applied to selection of (Phatak et al. 2023) to optimize the selection of in cases where the source differs from the larget by the presence of outliers.
2.3 Support Subset Selection with Entropic Regularization
The support subset selection problem 6 is linear program, which can be exactly solved by the simplex method or interior point methods, both of which do not scale well with the dimension of transport map (Cuturi 2013). In order to apply efficient gradient-based optimization to linear programs, entropic regu- larization has been added to linear objective functions (Li & Fang 1997). In the work by Cuturi (2013). entropic regularization added the optimal transport, problem to efficiently approximate the Wasserstein distance using Sinhkorn's matrix scaling algorithm (Cuturi) 2013 Sinkhorn, 1964). For fixed target distri- bution j and upper-bounding source measure Ç with mass Ç RR, the proposed entropically regularized support subset selection problem is
S/ () == min P (P.M) + (o, 1mxn) s.t. Pl, = nb 1 <C
(13)
where y is the regularization parameter. In the case of uniform distribution v 1 1nn the entropically regu- larization problem will be equivalent to using Kullback-Leibbee divergence between the joint and product of the given marginals and additional identity and range constraints on the solution's marginals Séjourné et al. (2019), as shown in Appendix D It is important to mention that the regularization ion term (P, log P) 1mxn) is negative entropy, which is I-strongly convex with respect to the & and & norms the feasible set: (P:P> P1, = M4 1 1m * <} (Bock 2017). The Lagrangian of problem 13 is
C(P.o. = (P, M >log P -11 1,) + al,, I (a. 11) (B,C).
(14)
where a, B are the Lagrange multipliers. Note that we have adopted the approach of Cuturi 2013 and do not explicitly enforee the simplex constraint on P, which would lead the log-sum-exp formulation in the works by Cuturi & Peyré (2018); Lin al. (2022); Guminov et al. (2021). Taking the element-wise derivative of L with respect to P and setting it to yields
P(a, B) exp((a/1))
exp exp (xp(-M/n)D) exp(-8/7)) (<x/)))(exxpp((/1))
(15)
Substituting P back into Lagrangian results in the dual problem
min a.3
( B)1, + (a. + (8,C)
(16)
s.t. B x 0.
The constraint set / bz= 0 is closed. The indicator function of the constraint set B b 0 is defined as
0, for @ >> 0
4 (
oc, otherwise.
Therefore, we can convert problem into an unconstrained composite optimization problem,
min a
f(a. (9) + (1)).
(17)
9

---

Published in Transactions on Machine Learning Research (12/2023)
Since f(a, 3) is convex and (B) is proper, closed, and convex, we can apply the accelerated proximal gradient algorithm to solve the composite optimization problem. Defining the Gibbs kernel K = exp ( M the partial gradient Vaf(a, 9) is
Val(a, B) = - exp(-8/7) @ (K" exp xxp(-//7)))
(18)
The proximal projection for the non-negative orthant's indicator function is computed by setting any negative entrics to zero.
Algorithm (SS-Entropic) outlines our accelerated proximal gradient algorithm to solve the dual form of subset selection problem with entropic regularization. Similar the standard entropically regularized optimal transport problem, the dual variable is updated with Sinkhorn-like update at iteration & as
( (Kexp(-3(0))) /2)) 2 en))
(k+1)) log
(19)
Whercas, 3 is updated itcration using accelerated proximal gradient based update rule (Beck Bock & Teboulle, 2009) using the extrapolated point & with step size 1/1b (k)
2017
g(e+1) = [5(h]
1
V (((())))))
(((0)
1 n/aa) (5 -xe( e (k) /7) @ KT exp (xp(-altt)//))
/1)
(K) n/s
(20)
g(k+1) = (((++) + ts - 1 (1(h+1)-1(0)
1
412
with fx41
(21)
t++1
which uses equation 18 to compute the gradient with respect to the variable g(k) before applying the proximal operator [+]+. In SS- SS-Entropic, we use constant step size 1 = (since the primal problem 16 y-strongly
convex and its semi-dual is 1 L-Lisschitz smooth Cuturi & Peyró (2016), see Appendix A for details), but
another option is a backtracking line search [Beck] 2017).
By incorporating the update of (*+1) in equation 19 directly into the gradient (a g(k),, the algorithm be written entirely in terms of ((k)_ This shows that S5-Entropic consists of standard accelerated proximal gradient updates and has (11/k²) convergence rate. As shown in the work by Beck (2017), the required number of iterations ke to achieve an s sub-optimal solution of the optimization problem using -SSEntropic is upper-bounder as
2 yE ke + + 1
||(0) - 11
(22)
where g00 the initialization and 3 is the optimal solution.
If SS-Entropic is allowed to run until its convergence, returns the optimal coupling P", but in practice, if SS-Entropic does not reach convergence, P. E & Rm may violate the primal constraints on its marginals as these are not ensured by an approximate dual solution. For some applications a projection of p. to satisly one or both of the marginal constraints may be required. While not explored in this paper due to the additional computational cost, projection to the feasible set can be done by the fast dual proximal gradient (FDPG) algorithm from the works by Beck & Teboulle (2014) and Beck (0117) in conjunction with 2 in the work of Altschuler et al. 2017).
2.4 Support Subset Selection with the Inexact- Inexact-Bregman Proximal-point Method
Although the entropic regularization of the coupling distribution enables an efficient approximation of the support subset selection problem [ the entropic regularization yields denser coupling distributions as com- pared to the unregularized problem. The denser coupling distributions result in new marginal mass D² that is also not sparse, yielding complete support rather than subset of the source points. Different approaches
10

---

Published in Transactions on Machine Learning Research (12/2023)
Algorithm 1: (SS-Entropic) Fast proximal gradient algorithm to solve the dual problem 17 of the entropically regularized support subset selection problem 13
Inputs
Target distribution μ. mass assignment bounding vector Ç, cost matrix M, entropic regularization parameter 7; initial dual variable, B 14,, and iteration limit mar-iter.
Outputs P which approaches the optimal coupling P
1 Function EntropicSS (ps, Ç, ((),, ?, M, maz-iter):
Initialization: to t 1, g(0) + g(), g(() + -0, K +- exp(--,
2
for + to mar-iler- do
((++)) t 7og
(Kexp(- 2 p
3
g(++l) - (Vgf(att))) {(())
1++1 1+ 1+
5
{((+1) t g(i+1) + (#e=)) (3(k+2) - -(())
6
7
end
a' t (k+l)
8
8r g(k+1)
9
p. t P(a", B²)) D exp (- KD( eex((- (D(xp(((())(
10
return p., o², gr
11
have been proposed to maintain the computational benefits of entropic regularization while yielding solutions closer to the unregularized problem [Schmitzer
2019 Xie et al., 2020
In this paper, we follow the work by Xie ct al. 2020) and adapt an inexact Bregman proximal gradient for the negative entropy function (Teboulle] 1992) to the partial optimal transport case. The Bregman proximal
gradient approach uses a proximal operator where the usual Euclidean distance(Parikh & Boyd 2014] is replaced with the Bregman divergence associated with a continuously differentiable and strictly convex function [Beck 2017). In the case of negative entropy, the Bregman divergence is the Kullback-Leibler divergence. Let (PP) lo,g - mmxn) denote the negative entropy of non-negative matrix P, then given non-negative matrix P E R Rmxx the Bregman divergence is
B P = [P, P Ø P')) (P, 1mxn) + (P', 1mxx).
(23)
For the subset selection problem the Bregman proximal point evaluated at p(), is
Brog-prox, (P(9) = arg min P²0
(P. (PI
(24)
s.t. Pl = μt P 1m < C.
where is positive scaling factor. By substituting Bø (PI(((t from equation 23 into equation
24 and
ignoring the constant term (P(t) Imxa) we oblain
Breg-prox, (P(!) arg min
(P,M log (()() loP,log(P) 1 1mxa)
P=0
(25)
s.t. P1, 1
which corresponds to the entropically regularized subset. selection problem 13 with parameters 7 and M
in 13 replaced by À and M - -log ((*)), respectively. Thus, solving the retropy-regularized support subset selection problem required to solve an iteration of the proximal-stop evaluation problem in equation 25 It
has been shown in the work by Xie et al. (2020) that as co, the iterations ((++)) Breg-prox,, (P())
converge to imal solution of the original unregularized problem. Therefore, to solve 6 we iteratively
11

---

Published in Transactions on Machine Learning Research (12/2023)
invoke SS S8-Entropic to obtain p(++1) Breg- Breg-prox, (Pit)), while replacing y and M in problem 13 by A and M AP(()) in problem 25 respectively.
Algorithm (SS B outlines the steps to solve the subset support selection using the Bregman proximal-point method, where the inner loop is solved by SS-Entropic. The nested loops of the exact proximal point algorithm can result in high computational costs, but this can be circunvented by choos- ing a lower number of iterations for the inner pop-stopping before its convergence. This is justified by the observation that the majority of the progress towards optimal solutions by gradient based methods is achieved during the first few iterations. Recently, an inertial variant of inexact- BBegannn proximal point method for the optimal transport has been proposed (Yang Toh 2022), which may further accelerate the Bregman proximal point method, but to the best of our knowledge there are no guarantees for accelerated convergence.
Algorithm 2: (SS-Bregman) Inexact-Bregman Proximal Point Algorithm to approximately solve 6
via 25
Target distribution μ, mass assignment upper bounding vector C, cost matrix M, Bregman scaling parameter X, and initial dual variable, z IR4, inner-iteration limit mar-inner-iter and outer-iteration limit maz-outer-iter Outputs P Initialization: ((0) + 3 p(O) < 1
Inputs
mn mxx
1 for 4 to mar-outer-iter
do // repeatedly invoke Entropic-SS
p(++1),
(((+)),((++)), ((+1)), g(++1) + EntropicSS (,,,, A, M - log(P(!), mar-inner-iter)
2
3 end
4 p p(t+1)
Due to carly stopping, SS SS-Bregman can yield infeasible solutions that do not satisfy the marginal constraints. In practice, the number of iterations depends problem in the hand. For applications related to point cloud registration, color transfer and PU learning, where number of data points in a data-batch is small, the algorithm allowed to run with a large number of iterations yielding a highly accurate and feasible solution. Whereas, for the applications related to neural network training where training efficiency is more important than the solution accuracy, the algorithm allowed to run for smaller number of iterations.
2.5 Point Cloud Registration with Subset Selection
Point cloud registration is a well studied problem that tries to find a correspondence of points in one sample (cloud) to another sample (Zhang et al., 2021 Zang al.) 2019). Practical settings include points sampled from the boundaries of 3D images such as captured by LIDAR the points on the edges of objects in 2D images Xu et al., 2023 More generally, points correspond to data points in two more samples. In both of these cases it is useful to consider the case that the two samples exist in different coordinate frames such that there is an affine transformation needed to align the samples before finding the correspondence.
Partial optimal transport for point cloud registration motivated by cases of occlusion in 2D or 3D imagery. In the case of data, it could be that one sample has dropped modes either by the nature of the data gathering or generating process. Our proposed subset selection algorithms are applicable cases where the source is assumed to have a complete or overcomplete representation of the target, ie., only subset of the target is available and all target points should be maintained.
We propose to use support subset selection as loss function for optimizing affine transformations in partial point cloud registration. This can be posed as a bi-level optimization problem
min min @ P
(P. (P))(O)) s.t. P1, u. P 1m x cV,
(26)
where θ [A, b] are the parameters of the affine transform, the entries of the cost matrix M()) are
[O)] | 9 i e [m].j E [n] for fixed target {a.}m and transformed source (0) Ay, b-1-1-
12

---

Published in Transactions on Machine Learning Research (12/2023)
The standard approach to solve bi-level optimization problems in point cloud registration discussed in the works by Arun et al. (1987) and Myronenko & Song (2010), is iterative alternating algorithm with two steps, where the sub-problem for the affine transform is solved exactly via ordinary least squares. If the coupling matrix during an iteration is given by P", the next subproblem is to find the affine transformation parameters = [A, bj that minimize the weighted squared errors Σij [P Plllllaa - (Ay, + b- The solution can be found analytically in terms of the source mass vector v² ppp Imy weighted means of the target point cloud X [........ Im! and the source point cloud Y 1......, yn
as X i and y 'V,
and centered point clouds X = = l and Y =Y 1y-11,7 1,
as
A = [X T P ( (VT)()))))
(27)
b= a Ay.
where (.) indicates the Moore-Penrose pseudo-inverse.
To find a solution to equation 26 we also use an iterative alternating algorithm with two steps. In contrast to Myronenko & Song (2010). instead of using complete source and target point clouds to obtain affine transformations, during every itcration we draw batches from both source and target point clouds to obtain the coupling matrix P and update the affine transformation parameters via a gradient update. The advantage of this mini-batch based approach is an implicit regularization and faster updates for affine transformation parameters. In the first step, step__iven the affine transformation we obtain approximate solution P. to the subset selection problem 6 via SS-Bregman. In the second step, we used automatic differentiation of the cost. (P*, (9)) and perform gradient based update for the parameters θ = [A, b). Tt is important to mention that we follow the approach adopted by Xie et al. (2020) for gradient evaluation. Therefore, during an iteration, once the subset set selection map P is obtained, it is deemed constant for the iteration in consideration, therefore the gradient is: Ve (O)) = Ex,(P'), [P*), Ve specifically, we used PyTorch basod automatic differentiation for gradient evaluation (Paszke et al. 2017) and the Adam optimizer (Kingma & Ba 2014) with learning rate of 0.5 for gradient based updates of parameters
( (M) More
O. To initialize the affine mapping parameters we simply set A and b to the identity matrix and zero vector, respectively. However, since the bi-level optimization problem is not convex, even though the subset selection problem at each iteration is convex, in practice the algorithm could be allowed to run with multiple initialization to obtain the best, fit.
3 Experimental Results and Discussion
In this section we discuss the application of subset selection. Subsections 3.1 and 3.2 discuss the application of subset selection in toy data sets: point-clouds in 2D and 3D with and without afline transformations and color transfer, respectively. Subsection 3.3 discusses subset selection for positive-umlabeldd learning tasks. Subsection 3.4 discusses the application of subset selection for semi-supervised training of neural networks. All the experiments done in this paper use p = and the Euclidean distance define the cost matrix. Unless stated otherwise, experiments use μ - 1m and Ç = n In, where c is the scaling factor.
3.1 Subset Selection on Point Clouds
In order to demonstrate the proposed algorithms and highlight the difference between regular optimal transport and subset selection, we consider a target sample of points from a circle centered at the origin and a source sample of points from a 2D uniform distribution also centered at the origin. We allow the scaling parameter to vary between 1 and 100, obtain the optimal transport plans P using both SS-Entropic and SS-Bregman, and evaluate the cost values M)) Results for this toy case are shown in Figure 2 It can be observed that as is increased the transport cost decrcases until it saturates to the cost of the greedy solution Σie( (m) I minjetm] [M] which corresponds to e c* where the transport map could be found by greedily choosing nearest source point for each target point as in equation [ Figure 2 also illustrates the transport couplings for e E (1, 1.25, 1.5, 1.75, 2, 4, 8, 16). A key observation that transport maps obtained with -reBaagman are sparser as compared to the denser maps obtained using SS-Entropic. Additionally, they achieve smaller values of transport cost. Therefore in the subsequent sections, we focus
Circle and Square:
13

---

Published in Transactions on Machine Learning Research (12/2023)
results from SS-Bregman in the main body; results for Algorithm SS-Entropic are in the Appendix B
and Appendix C
the latter includes comparisons with penalty-based semi-relaxed formulations.
Entropic subset-selection (SS-Entropic)
1.0
c=1
c=1.25
c=1.5
c=1.75
0.5
0.0
C=2
C=4
c=8
C=16
-0.5
-1.0
-1.0
0.5
0.0
0.5
1.0
target
source
target
source
(a)
(c)
Entropic subsct-sclection (SS-Bregman)
C=1
c=1.25
c=1.5
c=1.75
0.650
SS-Entropic
0.625
Brogran
0.600
(P' M
0.575
0.550
C=2
C=4
8=8
11
0.525
0,500
IIII
0.475
100
target
source
(b)
(d)
Figure 2: (a) The toy data generated by uniformly sampling m = 100 points from a circle centered at the origin with unit diameter as the larget. The source contains n = 80 points generated by sampling uniformly from :- ( x 2.. (b) The optimal costs MP) obtained using -S--Enropic and sS SS-Bregman versus e for C [00]. SS oS-Entropic is ran for 10,000 iterations with 7 0.1. SS-Bregman is ran for maz-outer-iter 100, mar-inner-iter (1, 1.5, 1.75, 2, 2,4,8, 16) using the Algorithms SS-Entropic and SS-Bregman, respectively.
100 and x = 0.1. (c) and (d) Support subset selection results obtained for e
Fragmented Hypercube with Mode Dropping: We demonstrate the utility of the support subset selection algorithm for partial point cloud registration on a toy case with one dropped mode and an affine transformation between the source and the target. Specifically, we consider data sampled from a uniform distribution over a hypercube (specifically, a square in 2D or a cube in 3D), which is then fragmented, where the target has one less fragment than the source. To generate the source we sample n points {0, from the uniform distribution over unit hypercube centered at the origin |- _ 1jd d E (2,3). These points are then fragmented into 2d fragments according to their quadrant D, = 8; + (d - 1) sign(r:) and then offset to obtain the source points as y; ÿ; + 5(d -1) 1) for i E [m]. The target data is generated similarly: a sample of m > m points {2 is obtained from |- 1td then points with all negative coordinates are discarded, leaving m points, which are fragmented into 2d 1 fragments to obtain the target set {x.}m via
x; z; + (d - 1) sign(z;) for i E [m]. Examples of the data for 2D and 3D are shown in Figure 3 (a) and Figure 4 (a), respectively.
14

---

Published in Transactions on Machine Learning Research (12/2023)
10
e-125
e-15
10"
10-2
100
200
300
400
500
+ updates
X
(a)
(b)
C
1.25
e 1.50
e 1.75
c
c
8
16
Figure 3: Results for affine transformation optimization with subset selection for partial optimal transport. Target points X are sampled from 2D fragmented hypercube centered at the origin with negative co- ordinates removed, whereas source points Y are sampled from a translated fragmented hypercube. (a) Source and target sample points. (b) Loss function plotted against.
[A, b] updates for scaling parameter c e 1.25, 1.5, 1.75, 2, 4, 8, 16). (c) Target and transformed source points after application of optimized affine transformation. Subset selection problems are solved using the SS- oS-Bregman with À = 0.1, maz-outer-iter 100 and maz-inner-iter 500.
Due to the translation by 5(d - 1) of the source point coordinates, direct application of the transport map will not yield a meaningful registration. Instead we use the bi-level optimization algorithm described in Scction 2.5 The target and the transformed source after applying the affine transformation obtained using SS- -r-Bregman for {1, 1.25, 1.5, 1.75, 2, 4, 8, 16] are displayed in Figure 3()) and Figure [c), respectively. Clearly, the e= case corresponding to the complete optimal transport fails to identify a meaningful affine transformation, instead skewing and rotating the source fragments to minimize the Wasserstein distance to the target. The figures also display the cost (P*, across iterations. It can be observed that, like the previous toy examples as the value of scaling factor e is increased, initially the value of the optimal loss (P*,M) decreases but after certain values of e, it saturates and stops decrcasing and stays constant afterwards.
Partial Point Cloud for 3D Shapes: We further apply this form of subset selection based point cloud registration to point clouds for 3D objects when the target points are only taken from portion of the entire 3D point cloud. Results for the Stanford bunny and armadillo Turk & Levoy 1994 Krishnamurthy & Levoy 1996) are shown in Figure 5 It can be observed that for the case c 1, which corresponds to complete optimal transport, the entire set of source points are coupled the target point cloud which results in distorted affine transform. For {2, 5, 10, 20), subset selection allows an appropriate subset of the source points to be well-fit by affine transform to the target point cloud.
15

---

Published in Transactions on Machine Learning Research (12/2023)
10
el
e12
10a
10
5
10
10a
10
0
5
10-1
0
10
10
Y
100
200
300
400
500
4 updates
(a)
(b)
c=1 1
c=1.25
c= 1.50
c= 1.75
-4
-
-
-
-4
c=
2
c=4
4
C= 8
16
-4
44
4
4
4
X
(c)
Figure 4: Results for affine transformation optimization with subset selection for partial optimal trans- port. Target points X are sampled from a 3D fragmented hypercube centered at the origin with negative co-ordinates removed, whereas source points Y are sampled from a translated fragmented hypercube. (a) Source and target sample points. (b) Loss function plotted against = [A, bj updates for scaling pa- rameter {1, 1.25, 1.5, 1.75, 2, 4,8, 16). (c) Target and transformed source points after application of the optimized affine transformation. Subset selection problems are solved using the SS-Bregman with À 0.1, maz-outer-iter 200 and maz-inner-iter = 500.
3.2 Color Transfer
Color transfer is the problem of finding correspondence in the colors of pixels (represented points in 3D color space) between two images and then using this map to assign the colors of the source image to the target image (Reinhard et al., (001). Color transfer is essentially an optimal transport problem in the color space, but with the added context that the pixels have their image coordinates, which are not used by the algorithm. For practical application to high resolution images, the pixel colors are first quantized using k-means clustering, as using partial optimal transport on the full set of pixel colors is computationally demanding. While in standard optimal transport the relative mass of each color cluster has to be preserved, here we exploit our formulation of partial optimal transport support subset. selection to allow a subset of colors to be used at higher proportion than in the original source and allow a subset of colors to be completely discarded. For example, if a color cluster represents 1% of the original source's pixels, then it could represent up to e% of the target's pixels.
We apply m-manns clustering to the set vectors in RGB color space representing the source's M pixels and the target's N pixels soparately to obtain m & M color centroids {æx ) C R3 for the target image and n & N color centroids ( C R2 for the source image, with μ An and μ E A, being the vectors of proportion of colors in the target and source image color clusters, respectively. After that, define the
16

---

Published in Transactions on Machine Learning Research (12/2023)
X
c=1
c=2
c=5
c= 10
c=20
(a)
Xx1 Y
c=l
2
c=5
c=10
c=20
(b)
Figure Affine transformation optimization for partial alignment. of point clouds where a subset of the source point-cloud Y can be perfectly aligned (after rotation and scaling) with the target point cloud X. We use the optimization algorithm described in Section 2.5 where SS-Bregman is employed to obtain the coupling P given the affine transformation parameters A and b, which are updated using equation 27 (a) Stanford bunny point cloud. (b) Stanford armadillo point cloud.
cost matrix between the color centroids as Myj - -1=; yı vi E [m],.j [n] and obtain the support subset selection map P x=*x using SB-Bregman, such that P*1, μ and p 1m * cv. The support subset selection is then used to obtain the barycenter projections by solving (Boonee et al. 2018)
arg min ZER3
- Vi [m]]
(28)
The analytic solution of the barycenter projections can be compactly written as
X = (P" @ (1I E mR3x3
(29)
where X = [21, F2...., _m]" m and Y [31. U2...., vml R2x3 are matrices of the color centroids.
Each pixel in the target image is assigned the corresponding barycenter projection en()), where x(i) E [m]] is the cluster assignment for the ith pixel of target image, i E [M]
We apply this color transfer scheme to images freely available though a Creative Commons liconce, the "Louisiana Nature Scene Barataria. Preserve" by Neil O as target and "Autumm in Toronto" by Bahman A- Mahmoodi source. The color transfer results with m n 128 and SS-Bregman with A 0.1 are shown in Figure [6] It can be observed that the results for larger values of are smoother within objects areas of similar color (e.g., the dark backdrop behind the peppers) and sharper in the color transitions between different objects (the colors in the orange versus red pepper on the right side of the photograph) as compared to the optimal transport case c == 1. This is due to the fact that larger values of c allow certain colors to be reused more than their prevalence enables smoother transitions in colors for areas of the target images with smooth color gradients. Similar obscrvations can be scen in Figure which uses the same scttings and MATLAB test images: "poppers" target and "corn" as source.
the source image and allow some colors to be discarded, which
3.3 Subset Selection for
Learning
In this section, we discuss the application of subset selection the one-class semi-supervised classification scheme known as positive-unlabeled (PU) learning (Bekker & Davis 2020). In PU learning, the training
17

---

Published in Transactions on Machine Learning Research (12/2023)
target
c=1.25
c=1.5
source
a
(b)
Figure 6: Color transfer results for 1.,1. 1.5,, 1.75, 2,8,8, 16) for "Louisiana Nature Scene Barataria
Preserve" by Neil O target and "Autumn in Toronto" source by Bahman A-Mahmoodi as target. The value of for each image is indicated at the top of image.
target
-225
1=5
L.75
source
16
(a)
(b)
Figure 7: Color transfer results for c E {1, 1.25, 1.5, 1.75, 8, 16) for MATLAB image "peppers" as target and "corn" as source. The value of e for each image is indicated at the top of image.
sample consists of purely positively labeled instances, and the unlabeled test sample consists of both positive and negative instances. Previous work often assumes that a prior on the probability of positive instances unlabeled data known (Kato et al. 2019 Hsieh al. 2019 Chapel et al. 2020). Partial optimal transport is then used to find subset with cardinality proportional to the prior of the test sample (source/ (source/unlabedt /unlabeled) that corresponds to all subset of the training sample (target/posittive) We argue that all of the target mass should be preserved in cases of relatively small and curated positive training sample. This motivates the application of our proposed subset selection approach to find the subset of the source that covers the positive target, compared to fully-relaxed approaches.
To illustrate the difference between fully and semi-relaxed partial optimal transport for PU learning, we consider two-dimensional random variables for the positive and unlabeled points where the support of pos- itive random variable is a subset. of the support of unlabeled random variable and both have long-tailed distributions, as shown in Figure g The lower accuracy for the relly-relaxed solution (79.5% versus subset selection's is 84.1%) can be accounted for by the increased distances between source and target points away from the origin, which causes the target points to be dropped, preventing true positives in the source from being selected. This result holds for more general settings discussed in Appendix
We applied subset selection PU learning using the experimental scttings adapted from the work of Chapel et al. (2020), who explored using the PU- PU-Wasserstein (PUW) and the partial Gromov- Wasserstein distance (PGW) on various UCT, MNIST, colored-MNISTT, and Caltech-office data sets. For the UCI, MNIST, and
18

---

Published in Transactions on Machine Learning Research (12/2023)
Subsct Selection
Sebsett Sebrect-Sccriin Selection
Full- Relaxed Partill Wisserstiie
Fulls Rice--d Purtial Waseesttio
H
-2
-2
-5.0
-2.5
0.0
2.5
5.0
-5.0
-2.5
0.0
2.5
5.0
-5.0
-2.5
0.0
2.5
5.0
-5.0
-2.5
0.0
2.5
5.0
<Tex Unibbvieed
100
Reveggined Unisnedd
-tax Untabeled
Reweigtred Unidbsted
APa Postive
Jnex Postivve
400 Reevighted Unkabvied
pnea Poeltiv
shea
Poetive eg0 Reweggine Uniibood
(a)
(b)
(d)
Figure 8: Results of PU learning on toy data using subset selection (accuracy 84.1%) and fully-relaxed partial optimal transport (accuracy 79.5%). Data is generated as [r cos( rsin(e)] where the radius r is drawn from a truncated exponential distribution with density 2 exp((-))(oo 2.0) and vo is uniform over subset of angles [0, n.. The points belong to four classes corresponding to the angle falling in one of the intervals [0, F), ( 31. (g. 11 or (2r, T]. The m = 100 target/ prost//ositive points are all from the third class. The solutions are obtained using the known number of positives n4 out of the n = 400 source points, setting for our semi-relaxed approach and s "4 for the fully-rclaxod partial optimal transport.
n
colored-MNIST data sets, we randomly draw m 400 positive points and n 800 unlabeled points. For Caltech-office data sets, we randomly sampled m 100 positive points from the first domain and 100 unlabeled data points from the second domain. Following the experiments from the works by CCapel et al. (2020) and Kato et al. (2019), for multi-class data sets, we chose the data points from the class labeled 1 as positive and a random mixture of all classes as unlabeled, and the prior probability of positive class in the unlabeled set π4 is set to be exactly the proportion of posítives in unlabeled sample - = n+ where n4 is the number of true positives. This informs the PU-Wasserseein, partial Gromov- Wasserstein, and fully- relaxed partial Wasserstein optimal transport problems on the amount of mass to be transported as s = T++ whereas for subset selection we set the scaling parameter be c n. _. Classification accuracy evaluated by assigning positive predictions to the n4 largest source mass assignments and negative predictions to the remaining source points. We also compute the ROC curve by using the source mass assignment n² to rank the unlabeled source points. We ran the experiment 10 times and report the average of classification accuracy and the area under the ROC curve (ROC-AUC) in Table [ It can be observed that the proposed subset-selection performs better than PU Wasserstein in terms of accuracy in 8 out of the 10 data sets with same domain (UCI, MNIST, and Caltech-office with same domains). Subset selection does best overall on 6 out of these 10, with fully-relaxed partial optimal transport performing better on 4 datasets. For the Caltech-office data sets with domain transfer, the partial In terms of ROC-AUC, subset selection does better than PU Wasserstein in 9 out of the intra-domain data sets, which is not surprising since the relative ranking is more meaningful than when the mass assignments are restricted to be binary valued {0, 11 as in the solutions from PU Wasserstein.
Wasnoo--esserttein optimal transport does best.
n2
We attribute, higher AUC-ROC of subset selection as compared to fully-relaxed Wasserstein, to the fact that, subset selection problem has equality constraints target mass which ensures coverage (lower false negatives). The differences between our solutions (SS) and those for the PU Wasserstein (PUW) are subtle, as both are semi-relaxed and maintain equality constraints on the target distribution. The small, but consistent, differences in the accuracy between our method and PUW may be due to the additional uniform mass assignment constraints in PUW, which achieved through group-LASSO. The uniform mass assignment constraints PUW may result into larger transport costs as compared to solutions obtained using SS with same cardinality. The largest mass assignments in the solution to SS might be more reliable than constrained solutions to PU Wasserstein.
19

---

Published in Transactions on Machine Learning Research (12/2023)
Accuracy
ROC-AUC
Dataset
7T
PUW
PGW
FR-PW
SS
PUW
PGW
FR-PW
SS
mushrooms
0.518
95.15
94.85
99.45
96.63
0.9657
0.3336
0.9948
0.9883
shuttle
0.786
95.13
93.63
96.35
96.20
0.9321
0.6215
0.9467
0.9718
pageblocks
0.898
91.90
90.35
91.88
92.40
0.8036
0.7197
0.7817
0.8513
usps
0.167
98.28
95.55
97.08
98.48
0.9815
0.5096
0.9476
0.9927
connect-4
0.658
60.95
58.05
60.95
60.73
0.5692
0.5126
0.5666
0.5871
spambase
0.394
78.80
68.40
69.08
79.28
0.7952
0.5834
0.6770
0.8369
mnist
0.1
99.08
98.23
99.15
99.18
0.9874
0.7638
0.9768
0.9971
mmist-colored
0.1
91.58
96.78
97.66
91.88
0.8189
0.6619
0.9360
0.9521
surf C - surf C
0.1
90.00
87.20
82.00
90.40
0.8576
0.4622
0.7469
0.7333
surf C + surf A
0.1
81.60
86.80
81.40
81.60
0.4546
0.4764
0.5337
0,4889
surf C + surf W
0.1
82.20
86.40
81.20
82.20
0.4707
0.4807
0.4451
0.5056
surf C surf D
0.1 80.00 87.00
80.00
80.00
0.3756
0.4328
0.4056
0.4444
decaf C decaf C
0.1
94.00 86.20
82.00
94.40
0.9498
0.5713
0.7667
0.9682
decaf C decaf A
0.1 80.20 88.20
81.80
80.40
0.3986
0.5031
0.5349
0.4564
decaf C + decaf W
0.1
80.20
88.60
82.00
80.00
0.4299
0.5827
0.5611
0.5965
decaf C + decaf D
0.1 80.80 92.20
80.40
80.40
0.4546
0.5042
0.4617
0.4530
Table 1: PU learning on data sets as in the work by (Chapel et al. 2020). For subset selection (SS) and fully-relaxed partial- Wasserstiin (FR-PW), accuracy is evaluated by assigning label 1 to n4+ largest mass assignments and label 0 to the remaining mass assignments. For PU Wasserstein (PUW), the mass assignment are constrained to be binary valued in the set {0,p}. the data points with mass assignments 0 are labeled 0 and the data points with mass p
ne are labeled 1.
3.3.1 PU Learning on MNIST/EMNIST
To further illustrate how SS-Bregman operates on PU learning, we apply it to the case where the positive training sample (target) consists of MNIST digit images and the unlabeled test sample contains 50% points (MNIST digits) and 50% negative points (alphabetic letters from EMNIST). When e 1, which is equivalent to standard optimal transport, initially all the images in the unlabeled source sample are assigned uniform masses. As is increased, we hypothesize that the true positive MNIST digits will been assigned larger mass and remain in the selected support, whereas the EMNIST letters will receive relatively lower or zero mass. Our hypothesis is confirmed by the results displayed in Figure M aa), which displays the ROC curve across different choices of e, and in Figure (c), which displays the area under the ROC curve (AUC). As c is increased, source points with largest mass assignments are mostly MNIST digits. Likewise, Figure 9 e) shows the images with highest mass for different values of e which are mainly MNIST nunbers or EMNIST letters with close resemblance to a number. Figure (b) visualizes the distribution of source point masses by graphing the sorted masses for different values of c. From these curves the cardinality of the subset is easily seen for different values of c. Notably, for values of I 4 there are exists subset of the selected source points with uniform mass, but for larger values of the mass is non-uniform across all instances. These changes correspond to the change in slope of the entropy of the distribution for different values of is displayed in Figure
We further compared our approach for PU learning with semi-relaxed optimal transport approaches using the the squared fg-nrm penalty Chapel et al. (2021) and total-variation (TV) divergence Séjourné al. (2019). The formulation of semi-relaxed problems is discussed in Appendix C We used POT-toolbox Flamary et al.) (2021) to solve the semi-relaxed optimal transport problems. For both squared f--nrr and total-variation penaltics, we varied regularization paramcter with 32 uniform steps on logarithmic scale between 1 and 10a. For subsel-selection, e parameter is varied uniformly on logarithmic scale with 32 sleps between 1 and 32. In order to evaluate the performance of each method, we assigned label to all the selected points and zero to all the remaining points. We also computed the cardinalities and entropies of ansinnssignmsnns v². In Figure I0 we compare the effect of the cardinality of the support of the mass assignment vector v² on the accuracy and entropy H H(v"). We observe that for the mass assignments with same cardinality,
20

---

Published in Transactions on Machine Learning Research (12/2023)
mass assignments obtained through subset selection have higher entropy compared to both TV and & penalized semi-relaxed optimal transport. For each regularization discussed above, mass-assignment paths across scaling parameter с for SS-Bregman are discussed in the Appendix C
We also adapt the approach proposed in the work by Phatak et al. (0023) in the context of fully-relaxed partial optimal transport to automatically select the proportion of mass to separate inliers and outliers
automatically find a choice of for subset selection for PU learning. The approach finds the knee of the smoothed version of the first derivative of (,, ev) as function of ! E (0, using the kneedle method (Satopaa al. 2011 The results in Figure 10 (c) show that the automatically selected value of is at the highest accuracy.
1.0
1.2
1.0
Thes Foxinve
0.6
0.8
c=1
c=1.25
2
9
Q
0
7
0
0
7
7
1
4
7
1
7
11
40
9
1
0.5
0.4
c=
7
770
0
0
0
7
7
7
0 8 O
0.4
c=1.75
0
8
05
7
3
8
0
0.2
c=2
8
0
9
0
0
0
0
9
0
0.0
1.0
Positive
c=4
5
5
/
/
/
O
9
9
6
7
(a)
(b)
c-
9
9
8
6
4
4
7
0
c-
9
8
9
6
4
7
4
6
0
0.9
6.0
2=
9
8
9
6
4
1447
6
0
24
9
8
9
6
4
6
0
5.8
H(v*)
0.7
c=
9
8
9
6
4
6
0
5.6
0.6
c=32
9
8
9
6
1
4
4
6
0
0.5
0.4
(e)
(d)
c=1
c=1,7
c=8
24
e=
c=2
c=
28
e=,
cm4
e=
3=32
Figure 9: Subset selection results obtained using SS SS-Bregman with parameters X = 1, maz-outer-iter = 250 and maz-inner-iter- = 20. Source sample n = 512 consists of 50% digit images from MNIST and 50% lotter images from EMNIST. The larget sample contains m = 512 digit images drawn from MNIST. (a) ROC curves for different values for e E (1, 1.50, 1.75, 4, 2, 16, 20, 24, 28, 32). (b) Mass assignments to source images in descending order Dt (c) AUC of ROC versus c. (d) Entropy H(v") of the mass assignments 4² versus
3.3.2 PU Learning for CIFAR-10 Neural-Network Representations
We now consider the proposed subset selection algorithm for PU learning on the CIFAR-10 data set, where a single class from the training set is treated as the positive target and a mixture of all classes from the test set is the unlabeled source. Fundamentally, the performance of optimal transport methods on PU learning depends on the distance metric defining the cost matrix. Thus, the method performs poorly if Euclidean distance metric is applied to complex data such natural images. Instead, learning representation extracted from
21

---

Published in Transactions on Machine Learning Research (12/2023)
6.05
42-
22-2regran
TV
6.-
S5 DS-Rregmann Accancy
0.80
Accuraccy
4.-
H(y
2.0-
144
S2-Rregran
0.85
4
9.2
200
250
300
350
400
450
500
202
250
350
403
400
60o
0.80
card(
card ()*)
(a)
(b)
(c)
Figure 10: PU learning with semi-relaxed optimal transport approaches MINIS/EMMISS EMNIIT. Solutions for different cardinalities are obtained by varying the regularization, on a logarithmic scale. (a) Accuracy versus cardinality of selected subset using SS- Bregman, semi-rclaxed op- timal transport with total variation (TV) and squared-f2 penalties for PU learning on MNIST PIIST/EMNTS /EMNIST. (b) Entropy of mass assignments versus cardinality selected subset using SS-Bregman, semi- relaxed optimal transport with total variation (TV) and squared l penaltics.
/tt.tttiiooooonannntttttm constrriit parameters across a grid, uniform
(c) Accuracy of PU lcarning on MNIST MUSST/EN /EM- NIST using SS-Bregman versus scaling parameter c. Vertical lines indicate the location of the knee obtained using Phatak et al. (2023), the true peak accuracy value of e, and the break point c*.
pretrained neural network can be used. Here each image is represented as the vector of activations of the penultimate layer of the pre-trained ResNet-20 classifier (trained on CIFAR-10), and the Euclidean distance belween the activation vectors defines the cost matrix for the transport problem. results are given in Figure [1 The results are similar to the previous MNIST/EMNISS data set. Mass is uniformly distributed across a subset of images for values of < When the subset is greater than the proportion of positive instances in the unlabeled source, then the relative ranking of mass is not reliable: the top instances for 21,5,2, 4)
images from the target class, but (1.25, 1.75) have images resembling it from other classes. As c is increased above 8 the mass assignment is non-uniform, but constant for further increment in c. Values of e greater than 2 have an AUC >90%
Similar to PU learning on MNIST /NISS/EMNIST, we also compared our approach for PU learning on neural network representations of CIFAR-10 with TV and lo penalized semi-relaxed optimal transport. For semi- relaxed formulations (f2 and TV penaltics) we varied p on logarithmic scale between 10-4 and 10a with 32 steps. For subset selection we varied the scaling parameter e logarithnically between and 60 in 32 steps. We adopted the same strategy previous case (PU learning MNIST (NNST/EMNISTT) to evaluate accuracy, cardinality, and entropy of mass assiguments v² at different values regularization and scaling parameters. Figure 12 shows accuracy versus cardinality, and entropy versus cardinality, along with variation of PU learning accuracy across e and knee-based scaling parameter selection. Our observations in this case are similar to the case for EMNIST/BEE MANISTTEMNISST: subset selection has the highest entropy at a given cardinality, accuracy is at or above the other solutions, and the knee method selects close optimal value of c.
3.4 Subset Selection for Semi-supervised Learning
We consider the semi-supervised training of classifter where the training set is divided into reliably labeled (curated) target set and an unlabeled or noisily labeled source set. We apply our proposed subset selection algorithm to perform partial optimal transport of the unlabeled source to the labeled target. The transport plan is computed without knowledge of any labels but defines how the source points will be labeled, and subset selection removes points that cannot easily be aligned to labeled training points. Additionally, the new mass assignment source points may be relatively higher for unlabeled points relatively close labeled training points and lower for unlabeled points from existing points. Used in this way, the optimal transport with subset selection automatically tunes how far propagate labels in manner that takes
22

---

Published in Transactions on Machine Learning Research (12/2023)
35
0.-
c=1
1.25
2.0
1.5
c 1.5
1.2
1=15
0.5
0.0
100
400
100
Fabe Puiliie
indiees
(a)
(b)
8
6.0
16
0.-
5.5
H(v*
24
5.0
0.4
28
4.5
c=32
0.0
15
30
10
15
25
10
(e)
(c)
(d)
c=1
1=.75
-
8=8
24
1,25
c=2
c-16
2
1.5
4
c-20
6=
Figure 11: Subset selection results obtained using algorithm SS-Bregman with parameters X 1, maz-outer-iten -ter 250 and maz-inner-êter = 20. Target and source consist of ResNet-20 embeddings of m = 512 CIFAR-10 dog images and 512 randomly sampled CIFAR-10 images, respectively. (a) ROC curves for e E {1, 1.25, 1.50, 1.75, 2, 4, 8, 16, 20, 24, 28, 32). (b) Mass assignments to souree images in descend- ing order v²___ (c) AUC of the ROC versus c. (d) Entropy H (v²)) of mass assignments v² with versus e. (e)
Source images with 10 largest mass assignments.
into consideration the geometry and distribution of the curated target. data set rather than only the local distances.
However, using the distances defined directly in the imput space may not be suitable, and pre-trained representation may not exist for various tasks. Instead, we propose to use the internal learning representation from the neural network classifier while it is being optimized with the semi semi-supervised loss function.
Let = {(x,, M denote the labeled portion of the training set with the input x; E X and label encoded as a one-hot vector L, E 13 C A L,Il = for i [M], and T = {y denote the unlabeled portion, yj E X' for j E [N]. We consider neural-network classifier with soft-max activation f(- :)) X - A with parameters trained on data with & classes. The neural network's internal representation is function g(: :)) X + Rd. The Euclidean distance between the internal representation of data points provides the distance function, da y₁) = (1 0) g(y;; l)1,, which is paramcterized by the network's parameters.
We train the neural network using mini-balches and a semi-supervised cross-entropy loss. Equal-sized batches are drawn uniformly from the pooled training data set of size M + N. Let T and or denote the length-m and length-n vectors of indices of the labeled and unlabeled points in a given batch, respectively, where m + n is the constant batch size. The m-by-n ground cost matrix (0) is defined using the squared distances among the batch's 's latent representations, M.) dz (xr, Vo,)),))))))))))>)
[[g( ( 0) g(yo;: 11
23

---

Published in Transactions on Machine Learning Research (12/2023)
1.0
88-Brognan
0.8
-Bregan Accuraccy
0.0
30000000-0000
G 0---- 0-
Accuraccy
H(v*
5.0-
0.7
4.0
0.6
Phana of True peak
100
200
300
400
500
160
200
300
400
500
card P*)
(vrd(v*)
a
(b)
(c)
Figure 12: PU learning with semi-relaxed optimal transport approaches on CTFAR-10. Solutions for different cardinalities are obtained by varying the regularization/ tatllarization/constrantt logarithmic scale. (a) Accuracy versus cardinality of selected subset using Bregman,, semi-relaxed optimal transport with total variation (TV), and squared l for PU learning CIFAR-10. (b) Entropy of mass assignments versus cardinality. (c) Accuracy of PU learning on CIFAR-10 using SS SS-Bregman versus scaling parameter e. Vertical lines indicate knee obtained using Phatak et al. 2023), true peak accuracy value of c, and break point c*.
cconsrraint parameters across grid, uniform on a
Given the cost matrix and pyper-parameters (including S n),, the subset selection transport plan P E
[o, 1Jmxx is obtained using SS SS-Bregman. Given the matrix of one-hot encoded labels = [Lr....., I,,.]" JT e {0, 1)mmk, the matrix pseudo-labels assigned by the algorithm of the unlabeled mini-batch points is computed Ż np*
T L E m where [P* Lljt " Ly [0, 1] the estimate of the joint probability
that batch unlabeled instance j [n] belongs to class [k]] Given the pseudo-labels, the semi- supervised cross-entropy loss function for batch
k
loss(O 0) =
Σ
La log(f((z;; 0))+
+
i y1 log log(f(((,;
(30)
m
n
j=
Our approach similar other recent work (Damodaran et al. 2020) that also employs optimal transport using a learning representation. While we address the semi-supervised case, Damodaran al. (2020) address supervised learning in the presence of label noise and perform self optimal transport within batches to correct for label noise.
As bascline comparisons, we compare our semi-supervised approach to supervised training with cither only the labeled portion or with noisy labels on the unlabeled portion. Due to the curated labeled set, the latter is not the typical label noise scenario; however, the division of a training set into a curated portion and a portion with label noise relevant to practical scenarios. While our semi-supervised approach does not use noisy labels, future extensions could consider how leverage the noisy labels too.
In order to evaluate our approach used MNIST, Fashion-MNIST (FMNIST), and CIFAR-10. We split training data sets into 80/20 proportions for training and validation. We further split the training part into reliably labeled and unreliably labeled parts. Labels for the unreliably labeled part are generated by uniformly corrupting the true labels to other classes depending on the noise level. For each of our experiments, the subset selection transport underlying the loss done is found via SS-Bregman with X = 0.1, maz-outer-iter maz-inner-ite experiments. A ResNet-18 model architecture is used the CIFAR-10 data set. We trained the ResNet-18 for 180 epochs using Adam optimizer with initial learning rate of 0.001, which is schoduled to be halved
20 with a batch-size of 512. We used PyTorch framework for our
3It can be seen that the total sum of this joint is 1, 1 p
L1g
24

---

Published in Transactions on Machine Learning Research (12/2023)
after every 60 epochs. The model architectures containing two convolutional layers for MNIST and FMNIST are given in Appendix F The neural network classification models for MNIST are trained using stochastic gradient descent with a learning rate of 0.001, whereas models for FMNIST are trained using Adam with a learning rate of 0.001 and weight decay 1c-4. Model training for MNIST and Fashion-MNIST are done on a desklop system containing Intel Core-i7 9700 CPU, with 32 GB memory and NVIDIA GeForce RTX 2070 GPU. ResNet-18 based models for CTFAR-10 are trained using Lambda-labs cloud resources with 30 vCPUs, 200 GB memory, and NVIDIA A10 GPUs.
Subset Selection
Dataset
Architecture
stand.
c= 1
c=
3=
c=
c=
c= 6 c
c=
c=
8
c= 20
MNIST
2- 2-layer conv-net
96.57
97.15
97.39
97.33
97.40
97.43
97.32
97.38
97.44
97.35
FMNIST
2-layer conv-net
88.68
90.14
90.30
90.27
90.51
90.23
90.38
90.21
90.37
90.16
CIFAR-10
ResNet-18
79.10
87.18
89.45
89.27
89.21
89.53
89.54
89.72
89.47
89.57
Table 2: Validation accuracies for different values for neural network classification models trained with 50%
reliably labeled points and 50% points with noisy labels (noise level 0.8). Standard training (stand.) treats them equally, but subset selection treats them as unlabeled and assign pseudo-labels. Subset selection is done using the -S-Bregman with À = 0.1 and maz-ouler-iter- = maz-inner-iter- = 20.
In the first step of experiments, we split the training set for each data set into 50/50 proportions for unreliably and unroliably labeled parts. Unreliably labeled data is generated by uniformly corrupting the labels with a 80% chance (noise level 0.8). Validation accuracies for each data set are displayed in the Table 2 Notably, the performance for = 1 is higher than training with noisy labels, which shows that the semi-supervised training performs better than training with data with high noise level. (Because the algorithm is not run to convergence, the mass assignments for unlabeled points may not be be exactly uniform in the 1 case.) The performance of subset selection is consistently higher for values of c > compared to the c = 1, and the validation accuracies do not exhibit much change between c = 2 and 20. Therefore, we further evaluated our approach by varying both noise levels and clean and noisy proportions only for c= 2 and c= 20.
Progress of validation accuracies on CIFAR-10 are displayed in Figure 13 for clean/noisy proportions in (20/80, 40/60, 60/40, 80/20} with noise levels f0.2, 0.4, 0.6, 0.8}. It can be obscrved that standard neural network training process with label noise can divided into three phases, first in which the validation accuracy increases until peak. In the second phase, validation accuracy decreases, where the magnitude of the decrement depends on the noise level: it decreases less for low noise levels and more for higher noise levels. In the third phase, validation accuracy increases again and then oscillates around a constant value. This kind of phenomenon is more pronounced for larger noise levels (Zheng et al. 2020). In contrast, for the proposed subset selection based semi-supervised learning the validation accuracy does not go down after hitting its peak during the training process. This indicates that the transport map tend to assign correct pscudo-labels to the data points nearest the labeled data points and does not. introduce label noise.
The test set accuracies are displayed in Table 3 for supervised training on only the labeled data versus the semi-supervised training. The semi-supervised training with subset selection outperforms training performs better on 2 of 3 data sets under a 20/80 split of labeled and unlabeled, but does not outperform supervised learning for the 40/60 split. Thus, the semi-supervised loss function equation 30 is most beneficial when there is a higher ratio of unlabeled to labeled points.
4 Discussion and Further Work
In this paper, we have focused on selecting a subset of one distribution's 's support as a special case of partial optimal transport Figalli (2010); Chapel et al.] (2020). This is useful to find meaningful alignment when the support of the target distribution is assumed be a subset of the source distribution. Results on the partial point cloud alignment, color transfer, PU learning, and semi-supervised learning all demonstrate the utility of this approach.
25

---

Published in Transactions on Machine Learning Research (12/2023)
standard training
subset-select training c=2
subset-select training c=20
20/88
40/60
20/30
40/60
20/80
40/60
valsarion sccurecy
100
90
valisaniio sccuracy
90
validarim aicimee
100
90-
Velisation Rccurncy
90
100
90
validatio sccuracy
90
80
80
80
80
80
80
70-
70
70-
70
70
60-
60
60-
60
60
60
50
50
50
40
40
40
40
40
40
60
120
180
0
50
120
180
50
120
180
50
120
180
60
120
180
0
50
120
180
training spoctts
training specits
training spectss
training epecits
training spoctss
training epectts
validtion accuraa
100
.0-
64:-40
validation accuraey
100
90-
80-20
validriion accorney
100
90-
60/40
validrionn accurscy
100
90
80/20
validnion PCC0ERAX
100
64:40
validation ScCU3163
100
90
80/20
su
au
80-
80
80
800
70
70
70
60
60
60
8
60
60
50
40-
40
40
40
60
120
180
50
120
180
60
120
180
60
120
180
60
120
180
50
120
150
training spocits
trsining spochs
training spocts
Iraining spocts
training spocits
trsining opochs
0.4
0.8
0.4
0.8
0.2
0.4
0.6
0.5
(a)
(b)
Figure 13: Progress of validation accuracies while training ResNet-18 for CIFAR-10 classification. (a) Uni- form noise levels are varied between 0.2, 0.4, 0.6, 0.8 for standard training. (b) and (c) Training with the
subset selection based semi-supervised loss at different values of c, does not use the unreliable labels, and
outperforms standard training with noisy labels when either the proportion of reliably labeled data is 40%
or the noise level is 0.4 or greater. Subset selection is done using theSS -Bregmnn with = 20, X = 0.1, maz-outer-iter- maz-inner-ite = 20.
Dataset
Architecture Labeled Unlabbled %
Labeled only
Semi-supervised
with subsot selection
2-layer conv-net
20/80
98.19
96.09
MNIST
40/60
98.30
97.14
2-layer
20/80
88.35
88.42
F-MNIST
conv-net
40/60
89.93
89.48
20/80
81.62
82.37
CIFAR-10
ResNet-18
40/60
87.77
86.74
Table 3: Semi-supervised learning test accuracies on MNIST, Fashion-MNIST, and CIFAR-10. Subset selection is done using SS-Bregman with 20, x 0.1, maz-outer-iter mar- mar-inner-itte- 20.
In particular, the results from the PU learning show that the proposed subset selection is useful when there is known target distribution (an existing training or validation set) and an additional source distribution, which has additional diversity, but also outliers, compared to the target. One application of PU learning is to filter a source of new data for relevant examples for further modeling. Future work could explore subset selection approach for source distributions created from synthetic generation mechanisms. While not explored in a machine learning context, it is possible that the partial optimal transport with affine (or nonlinear) transformation can be applied to account for global covariate shift between the synthetic and real data. In this case, a user would want to balance the diversity (entropy) of the filtered source with its purity.
Interestingly, the solution for the subset selection similar but consistently outperform those from PU Wasserstein Chapel et al. (2020), which by design of the constraints, have maximum entropy, uniform distribution over the selected subset achieved through the group LASSO penalty. The results from subset selection show that il maintains close to maximum entropy amongst the selected support and is as accu- rate as other semi-relaxed penalty based approaches. Additionally, the manual choice of e controlling the constraint is more intuitive than selecting a penalty parameter. Finally, the automatic selection of e using the straightforward bnso- selection adapted from fully-relaxed partial optimal transport (Phatak al. 2023) shows promising results to separate inliers and outliers.
26

---

Published in Transactions on Machine Learning Research (12/2023)
In our experiments related to semi-supervised learning, we employed optimal transport between a labeled larget and unlabeled source, to assign pseudo-labels to source points that cover the labeled data distribution, while ignoring ambiguous cases, during training. In future extension, we can consider how to use class information in the optimal transport planning, perhaps by using class conditional optimal transport, as currently the transport plan is not informed of the known larget labels nor the classifier's boundaries. Another line of exploration is how to use the support subset selection to correct noisily labeled source.
Another key contribution of this work is the proposed support subset selection algorithm using the inexact Bregman proximal point algorithm (SS-Bregman), which as shown in Appendix B yields solution with a sparse source marginal similar to solutions to the original linear program i unlike the entropically regu- larized solution from SS-Entropic. We also demonstrate that the mass assignments of the linear program solution are piece-wise linear as a function of c. While not fully investigated here, this behavior could be exploited find the sequence of breakpoints where points leave the support and where points leave the active set of constraints (indicated by being on the upper diagonal).
Recently, Gromov- Wasserstein optimal transport has seen applications in graph-matching and generative
modeling (Brogat- Motta et al.) 2022 Li et al.) 2023 Nekrashevich et al. 2023 Bunne et al. 2019 Mé-
moli 2009). Due to inherent ability to match structural corrospondences across spaces, partial Gromov- Wasserstein optimal transport can be used to solved robust graph-alignment problems. Recently, efficient locally convergent solutions for a relaxed Gromov-Wasserstee Wasserstein distance have been proposed (Peyré et al,
2016 Li et al. 2023). Future work can explore the subset selection case of the partial Waauoov-asssssteein optimal transport, where one domain is expected have a complete or overcomplete source distribution com- pared to the target. This may be useful in robust domain adaptation, semi-supervised domain adaptation, and metric alignment.
Author Contributions
Bilal Riaz and Austin Brockmeier worked on the formulation and design of experiments for subset-selection. Bilal Riaz implemented the algorithms and results. Manuscript was written and edited by all authors.
Acknowledgments
Bilal Riaz is supported by Higher Education Commission of Pakistan and University of Delaware. We would like to express gratitude to Matthew S. Emigh for insightful discussions and the Office of Naval Research for funding this rescarch. Research at the University of Delaware was sponsored by the Department of the Navy, Office of Naval Research under ONR award number N00014-21-1-2300.
Code Availability
Code for the paper is available
References
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A Rewriting System for Convex Optimization Problems. Journal of Control and Decision, 5(1):42-60, 2018.
Jason Altschuler, Jonathan Niles Weed, and Philippe Rigollet. Near-Linear Time Approximation Algorithms for Optimal Transport via Sinkhorn Iteration. Advances in Neural Information Processing Systems, 30, 2017.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein Generative Adversarial Networks. In International Conference on Machine Learning, pp.
PMLR, 2017.
K Somani Arun, Thomas S Huang, and Steven D Blostein. Least-squares Fitting of Two 3-D Point Sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(5):698-770 1987.
Amir Beck. First- Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadel- phia, PA, 2017.
27

---

Published in Transactions on Machine Learning Research (12/2023)
Amir Beck and Mare Teboulle. A Fast Iterative Seetinkag-Thresholiie Algorithm for Linear Inverse Prob- lems. STAM Journal on Imaging Sciences, 2(1):183-220) 202, 2009.
Amir Beck and Mare Teboulle. Fast Dual Proximal Gradient Algorithm for Convex Minimization and Applications. Operations Reseorch Letters, 42(1):1-6 6, 2014.
Jessa Bekker and Jesse Davis. Learning from Positive and Unlabeled Data: A Survey. Machine Learning, 109:719-760, 2020.
Jean-David Benamou.
Numerical resolution of an "unbalanced" mass transport problem. ESAIM: Mothe- matical Modelling and Numerical Analysis, 37(5):851 868, 2003.
Mathicu Blondel, Vivicn Seguy, and Antoine Rolet. Smooth and Sparse Optimal Transport. In International Conference on Artificial Intelligence and Slalislics, pp. 880 889. PMLR, 2018.
Nicolas Bonneel and David Coeurjolly. SPOT: Sliced Partial Optimal Transport. ACM Transactions Graphics (TOG), 38(4):1-13, 2019.
Luc Brogat-Motte, Rémi Flamary, Céline Brouard, Juho Rousu, and Florence d' A'Aché Buc. Learning Predict Graphs with Fused Wasserteansnn Barycenters. In International Conference on Machine Learning, pp. 2321 2335. PMLR, 2022.
Charlotte Bunne, David Alvarez-Melis, Andreas Krause, and Stefanie Jegelka. Learning Generative Models across Incomparable Spaces. In International Conference on Machine Learning, pp. 851-861, PMLR, 2019.
Luis A Caffarelli and Robert J McCann. Free Boundaries in Optimal Transport and Monge- Ampere Obstacle Problems. Annals of Mathematics, pp. 673-730, 2010.
Laetitia Chapel, Mokhtar Z Alaya, and Gilles Gasso. Partial Optimal Tranport with Applications on Positive- Unlabeled Learning. Advances in Neural Information Processing Systems, 33:2903 2913, 2020.
Lactitia Chapel, Rémi Flamary, Haoran Wu, Cédric Févotte, and Gilles Gasso. Unbalanced optimal transport through non-negative penalized linear regression. Advances in Neural Information Processing Systems, 34: 23270 23282, 2021.
Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavii Xavier Vialard. Scaling Algorithms for Unbalanced Optimal Transport Problems. Mathematics of Computation, 87(31)):2563- 2609, 2018.
Marco Cuturi. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. Advances in Neural Information Processing Systems, 26, 2013.
Marco Cuturi and Gabriel Peyré. A Smoothed Dual Approach for Variational Wasserstein Problems. SIAM Journal on Imaging Sciences, 9():3220 343, 2016.
Marco Cuturi and Gabriel Peyré. Semidual Regularized Optimal Transport. SIAM Review, 60(4):941 965, 2018.
Bharath Bhushan Damodaran, Rémi Flamary, Vivien Seguy, and Nicolas Courty. An Entropic Optimal Transport Loss for Learning Deep Neural Networks under Label Noise in Remote Sensing Images. Com- puler Vision and Image Understanding, 191:102863, 2020.
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing, Generative Modeling Using the Sliced Wasserstein Distance. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 3483- 3491, 2018.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embeddeed Modeling Language for Convex Opti- mization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Alessio Figalli. The Optimal Partial Transport Problem. Archive for Rational Mechanics and Analysis, 195 (2):533 560, 2010.
28

---

Published in Transactions on Machine Learning Research (12/2023)
Rémi Flamary, Nicholas Courty, Davis Tuia, and Alain Rakotomamoniy. Optimal Transport for domain Adaptation. IEEE Transactions on Pattern Analysis Machine Intelligence, 1, 2016.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Cham- bon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayrand, Hicham Janati, Alain Rakotomamonjy, levgen Rodko, Antoine Rolct, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Tilouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78))1-8,, 2021.
Charlie Frogner, Chiyuan Zhang, Hossein Mobahi, Mauricio Araya, and Tomaso A Poggio. Learning with Wasserstein loss. Advances in Newral Information Processing Systems, 28, 2015.
Divyansh Garg, Yan Wang, Bharath Hariharan, Mark Campbell, Kilian Q Weinberger, and Wei-Lun Chao. Wasserstein Distances for Stereo Disparity Estimation. Advances in Neural Information Processing Sys- lems, 33:22517 22529, 2020.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning Generative Models with Sinkhorn Divergences. In International Conference on Artificial Intelligence and Statistics, pp. 1608-1617. PMLR, 2018.
Kevin Guittet. Eztended Kantorovich norms: tool for optimization. PhD thesis, INRIA, 2002.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved Training of Wasserstein GANs. Advances in Neural Information Processing Systems, 30, 2017.
Sergey Guminov, Pavel Dvurechensky, Nazarii Tupitsa, and Alexander Gasnikov. On Combination of Alternating Minimization and Nesterov's Momentum. In International Conference on Machine Learning, pp. 3886 3898. PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Roger A Horn and Charles R Johnson. Matrix Analysis. Cambridge University Press, 2012.
Yu-Guan Hsich, Gang Niu, and Masashi Sugiyama. Classification from Positive, Unlabeled and Biased Negative Data. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR, 2019.
Masahiro Kato, Takeshi Teshima, and Junya Honda. Learning from Positive and Unlabeled Data with a Selection Bias. In International Conference on Learning Representations, 2019.
Keisuke Kawano, Satoshi Koide, and Keisuke Otaki. Partial Wasserstein Covering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7115 1123,, 2022.
Diederik P Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv preprint 14 6980, 2014.
Matthieu Kirchmeyer, Alain Rakotomamonjy, Emmanuel de Bezenac, and Patrick Gallinari. Mapping Con- ditional Distributions for Domain Adaptation under Generalized Target Shift. In International Conference on Learning Representations, 2022.
Soheil Kolouri, Se Rim Park, Matthew Thorpe, Dejan Slepcev, and Gustavo K Rohde. Optimal Mass Transport: Signal Processing and Machine-Learming Applications. IEEE Signal Processing Magazine, 34 (4):43-59, 2017.
Soheil Kolouri, Gustavo K Rohde, and Heiko Hoffmann. Sliced Wasserstein Distance for Learning Gaussian Mixture Models. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3427-3436, 2018.
Alexander Korotin, Daniil Selikhanovych, and Evgeny Burnaev. Neural Optimal Transport. In The Eleventh International Conference on Learning Representations, 2023.
29

---

Published in Transactions on Machine Learning Research (12/2023)
Venkat Krishnamurthy and Mare Levoy. Fitting Smooth Surfaces Dense Polygon Meshes. In Proceedings of the 23rd Ansoual Conference on Compuler Graphics and Interaclive Techniques, pp.
1996.
Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Authony Man-Cho So, and Jose Blanchet. A Convergent single-Loop Algorithm for Relaxation of Gromov- Wasserstein in Graph Data. In The Eleventh International Conference on Learning Representations, 2023.
Xing-Si Li and Shu-Cherng Fang. On The Entropic Regularization Method for Solving Min-Max Problems with Applications. Mathematical methods of operations research, 46(1):119 130, 1997.
Tianyi Lin, Nhat Ho, and Michael Jordan. On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms. In Proceedings of the 36th International Conference Machine Learning, Proceedings of Machine Learning Research. PMT.R, 2019.
Tianyi Lin, Nhat Ho, and Michael I Jordan. On the Efficiency of Entropic Regularized Algorithms for Optimal Transport. Journal of Machine Learning Research, (3(17))1 2022.
Petr Mokrov, Alexander Korotin, Lingxiao Li, Aude Genevay, Justin Solomon, and Evgeny Burnacv. Large- Scale Wasserstein Gradient Flows. In Advances in Neurul Information Processing Systems, volume 34, pp. 15243 15243-15256, 2021.
Andriy Myronenko and Xubo Song. Point Set Registration: Coherent Point Drift. IEEE transactions Pattern Analysis and Machine Intelligence, 32(11):2262-22275 2010.
Facundo Mémoli. Spectral Gromov- Wasserstein distances for shape matching. In 2009 IEEE 12th Interna- tional Conference on Computer Vision Workshops, 1CCV Workshops, pp. 256 256-263, 2009.
Maksim Nekrashevich, Alexander Korotin, and Evgeny Burnaev. Neural Gromov- Wasserstiin optimal trans- port. arXio preprint arXiv:2303.0599 2023.
Neal Parikh and Stephen Boyd. Proximal Algorithms. Foundations and Trends in Optimization, 1(3): 127 127-239, 2014.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic Differentiation in Pytorch. In NIPS 2017 Autodiff Workshop, 2017.
Gabriel Peyré and Marco Cuturi. Computational Optimal Transport: With Applications to Data Science. Foundations and Trends0 in Machine Learning, (556)))3555-60 607, 2019.
Gabriel Peyré, Marco Cuturi, and Justin Solomon. Chomov-Wassersiee Averaging of Kernel and Distance Matrices. In International Conference on Machine Learning, pp. 2664 2672. PMLR, 2016.
Abhiject Phatak, Sharath Raghvendra, Chittaranjan Tripathy, and Kaiyi Zhang. Computing all optimal partial transports. In The Eleventh International Conference on Learning Representations, 2023.
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein Barycenter and its Application Texture Mixing, In International Conference on Scale Space and Variational Methods in Computer Vision, pp. 435-446. Springer, 2011.
Julien Rabin, Sira Ferradans, and Nicolas Papadakis. Adaptive color transfer with relaxed optimal transport. In 2014 IEFE International Conference. on Image Processing (TCIP), pp. 4852-4856, 2014.
Erik Reinhard, Michael Adhikhmin, Bruce Gooch, and Peter Shirley. Color Transfer Between Images. 1EEE Computer Graphics and Applications, 21(5):34-41, 2001.
Litu Rout, Alexander Korotin, and Evgeny Burnaev. Generative Modeling with Optimal Transport Maps.
In International Conference on Learning Representations, 2022.
30

---

Published in Transactions on Machine Learning Research (12/2023)
Yossi Rubner, Leonidas J Guibas, and Carlo Tomasi. The earth mover's distance, multi-dimennional scaling, and color-based image retrieval. In Proceedings of the ARPA Image Underslanding Workshop, volume 661, pp. 668, 1997.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs Using Optimal Transport In International Conference on Learning Representations, 2018.
Ville Satopaa, Jeannie Albrecht, David Irwin, and Barath Raghavan. Finding a' kneedle' in a haystack: Detecting knee points in system behavior. In 2011 31st International Conference on Distributed Computing Systems Workshops, pp. 166 171. TEEE, 2011.
Bernhard Schmitzer. Stabilized Sparse scaling algorithms for entropy regularized transport problems. SIAM Journal on Scientific Computing, A1(3):A1443 A1481, 2019.
Thibault Séjourné, Jean Feydy, François Xavier Vialard, Alain Trouvé, and Gabriel Peyré. Sinkhorn diver- gences for unbalanced optimal transport. ar preprint 1rXiv:1910.12900 2019.
Richard Sinkhorn. A Relationship between Arbitrary Positive Matrices and Doubly Stochastic Matrices.
The Annals of Mathematical Statistics, 35(2):876-879, 1964.
Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. Wasserstein Propagation for Semi-
Supervised Learning. In International Conference on Machine Learning, pp. 306 314. PMLR, 2014.
Marc Teboulle. Entropic Proximal Mappings with Applications to Nonlincar Programming. Mathematics of Operalions Research, 17(3):670 690, 1992.
Πya Tolstikhin, Olivier Bousquet, Sylvian Gelly, and Bernhard Schölkopf. Wasserstein Auto-Encoders In 6th International Conference Leorning Representations (ICLR 2018), 2018.
Greg Turk and Marc Levoy. Zippered Polygon Meshes from Range Images. In Proceedings of the 21sl Anvuaal Conference on Computer Graphics and Interactive Techniques, pp. 311 118, 1994.
Yujia Xie, Xiangfeng Wang, Ruijia Wang, and Hongyuan Zha. A Fast Proximal Point Method for Computing Exact Wasserstein Distance. In Uncertaindy in Artificial Itelligence, pp. 433-453. PMLR, 2020.
Hongteng Xu, Wenlin Wang, Wei Liu, and Lawrence Carin. Distilled Wasserstein Learning for Word Em- bedding and Topic Modeling. Aduances in Neural Information Processing Systems, 31, 2018.
Ningli Xu, Rongjun Qin, and Shnang Song. Point Cloud Registration for Lidar and Photogrammetric Data: A Critical Synthesis and Performance Analysis on Classic and Deep Learning Algorithms. ISPRS Open Journal of Photogrammetry and Remote Sensing, pp. 100032, 2023.
Lei Yang and Kim-Chuan Toh. Bregman Proximal Point Algorithm Revisited: A New Inexact Version and Tts Inertial Variant. STAM Journal on Oplimization, 32(3):1523-1555 1554, 2022.
Yufu Zang, Roderik Lindenbergh, Bisheng Yang, and Haiyan Guan. Density-Adaptive and Geometry- Aware Registration of TLS Point Clouds Based on Coherent Point Drift. IEEE Geoscience and Remote Sensing Letters, 17(9):1628 1632, 2019.
Juyong Zhang, Yuxin Yao, and Bailin Deng. Fast and Robust Iterative Closest Point. IEEE Transactions on Pattern Analysis and Machine Intelligence, 4457):3450-3466, 2021.
Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-Bounded Correction of Noisy Labels. In International Conference Machine Learning, 2020.
31

---

Published in Transactions on Machine Learning Research (12/2023)
A
Appendix: Lipschitz Smoothness of Dual
The dual form 16 considered in this paper does not explicitly enforce the primal problem's marginal simplex constraints on the transport plan. Consequently, the dual form not necessarily Lipschitz smooth {Lin) et al. 2019 Cuturi & Peyré 2018 Lin al., 2022p. But the proposed algorithm, we first. update the dual variable a using the Sinkhorn-like update, which implicitly enforces the simplex constraint, making the semi-duul problem L-iisschizz smooth with respect to & & and lo norms. This justifies the use of
(k) in the accelerated proximal-gradient based approach to solve 16
l/s
Recall that the Lagrangian of 16 given in equation 14
a( = (P, M + (log( P) Im 1 + + 1m - (a,, (4) (3,5)-
(31)
By Slater's conditions, the problem
16 is strongly dual therefore
min max C(P, a, 8) = max min C(P, a) P&0 a.
(32)
a, P
In order to find the minimum of the Lagrangian with respect to P, one takes its element wise derivative with respect to P and obtains P(a, B) = D exp exp (- (- (eepp
exp (-),))))) which can then be
substituted back into the Lagrangian 31 to obtain the problem
max a
{g(a, = P(a
8)1, (a, μ) - ( s.t. B > 0.
(33)
which can be converted to the convex minimization problem 16 by defining f(a, B) = -g(a, (o(a,B)) B), as in
min
(f(a, -,,, + (a. (B, (),C) s.t. B > 0.
(34)
a
The partial gradients of S(x,,) with respect to and B are
Vaf(a, B) μ exe ( (- a
B -B) ② K exp
(35a)
7
Val(o, = - - exp (- (- o K exp exp(--) (--)
?
(35b)
For twice continuously differentiable functions, the Lipschitz smoothness parameter is determined by the Hessian. The Hessian for f(, is
Valla 8) Va B) (a Va
(36)
V V B)
where
ViVa(a,
1 D
exp
(
(-
@ K exp
(-2)
B
-
1
D(P((a,))1.)
(37a)
7
7
7
Vofla, 9)
1 D
exp (
B KT exp
(- a
7 )
1 D (((((a,)) 1,))
(37b)
7
?
7
-5) })
V Vafla, 3)
K
exp
(-
exp
P((a.))
(37c)
ViVaf(a,3) 1 7
B _ exp T = 'Paa, T.
K o exp (-
(37d)
The Sinkhorn update for a in equation 19 ensures that after each update a, the transport plan lies on the probability simplex and matches the target marginal 4 ( Defining
ú ((a(++1), ((K)) my the Hessian equation 36 at (a+(+1), (())) is compactly written
1 D(u)
P(a(tt),g00) D(0)
H (y (k+1) g(x)) = (t+()) (((0 ((0)T
32

---

Published in Transactions on Machine Learning Research (12/2023)
We use the induced- norms of the Hessian H y (1 ((()) to characterize the smoothness at (a(k+)) ))))) ((())
For matrix A E [Rmxx, the induced norm llp. is defined as
A
p-g ==
max [Ax1lg-
(38)
2:1
The twice contimuously differentiable function ((at is L-Lipschitz with respect to l, norm, if || H ((( ((()) S L, where lg is the dual norm of the bp norm. Since the Hessian H H((a((++), ((k) ((())) is a non-negative matrix, one can observe that all its matrix entries are less than 1 mmx {Amax: Pmax) where Pmax and Vmax are maximum entrics of f and respectively. Therefore for p = 1, if one can find the column index k corresponding to a matrix entry with value & max (mmax, Umax): then ex is the vertex of the & norm-ball where (a)(()()))) )alloo = mmxx/umxx Fmax). Thus,
[H)(alht)),
((6) ,(0))))))))))))))))))) 1 7
max {Niaax, Pmax) S 7
(39)
which proves the function f((((t1), ,(()) is LiLpschiizz with respect to the l norm. Since all the matrix entries of the Hessian H (a((()))) , ((0) are less than 1, its spectral radius less than & (Horn & Johnson (012)TTheoren 8.1.18) and
(a , Amax (H₁) 7
(40)
Therefore, the function ((((t)),,) g(t) is Lipishhitz with respect to the la norm. For = 0o, one can maximize the norm ([H(((((+)), ,(())) at the vertex of the foo ball where all entries are unit magnitude, in particular Imtn; which results into
1 [ 1 + ((a ,((h0) )( 2 F
H
- ? ((a((t))) ((()) I, + -ij
(41)
? 1
Therefore,
H H ,(t
2 F1
4 ?
(42)
7
and the function ((a ((0) is --iiscciitz with respect to the loo norm. In summary, the partial gradients are all L-Lisschiuz smooth with respect to Li, f2 and for norms. Additionally, considering the dual variables a and B, seperately, one can see that
(1+1),
Amax 1
IV 3 S 7
VVIaaf(a!tt) B(0+))
((k) "
and
IV (t( ,(())) Mmax
1
V 1
( ,(0) = 1
S q'
S 7"
Therefore, ((((k+1) ((()) is separately - Lipischiiz for both a and with respect to e,, la and loo norms.
7
B Appendix: Entropic Regularization Results
In this Appendix, results for point cloud registration and color transfer for SS-Entropic are displayed, which can be compared to the results for SS- Bregman in the main body.
Fragmented Hypercubes: Figure 14 shows the results for affine transformation optimization in 2D, which can be compared with the results in Figure aa). Visually it is clear that the aligmment is much worse for values of с E (1.25, 1.5), but quantitatively it is worse for all values of > as SS-Bregman achieves cost below 10-2 at 500 iterations of @ updates. Figure 15 shows the results 3D using Ss -Sttntrop,,, which can be compared with the results in Figure [a). In this case, results are quantitatively worse for all values of >> 1 as SS- Bregman achieves cost below 10-1 at 500 iterations O updates.
33

---

Published in Transactions on Machine Learning Research (12/2023)
C=1
c=1.25
C=1.5
C= 1=75
c#
G# 1.25
10
1.5
c=
109
C-8
C= 16
(P'
10-1
10-2
100
200
300
400
500
Updates
(b)
Figure 14: Results for affine transformation optimization with subset selection for partial optimal transport. Target points X are sampled from 2D fragmented hypercube centered al the origin with negative co- ordinates removed, whereas source points Y are sampled from a translated fragmented hypercube. (a) Target and transformed source points after application of optimized affine transformation. Subset selection problems are solved using the SS SS-Entropic with y = 0.01 with mar-iter 4000.(b) Loss function curves for scaling parameter E {1, 1.25, 1.5, 1.75, 2, 8, 16].
C=1
C=1.25
c=
c=1.75
10a
C+
c*2
1,25
102
1.5
c=
1.75
C- 16
2
C=4
C=8
C-16
100
10
-
10
100
200
300
400
500
Updates
(a)
(b)
Figure 15: Results for affine transformation optimization with subset selection for partial optimal transport. Target points X are sampled from 3D fragmented hypercube centered at the origin with negative co- ordinates removed, whereas source points Y are sampled from translated fragmented hypercube. (a) Target and transformed source points after application of optimized alfine transformation. Subset selection problems are solved using the SS SS-Encropic with 0.01 with mar-iter 4000.(b) Loss function curves for scaling parameter E {1, 1.25 1.5, 1.75, 2, 4, 166.
Partial point cloud registration: The results for partial point cloud registration with entropically regu- larized subset selection (SS-Entropic) for the Stanford bunny and armadillo point clouds. It is clear that the entropically regularized form alone fails to find a meaningful correspondence, transforming the source such that is completely covered by the partial point cloud.
The results for color transfer with the entropically regularized subset selection SS- ES-Ertoopic are shown in Figure [7 which can be compared to results from SS-Bregman shown in Figure 0 and Figure| 7 Namely, for the first image "oouisiana Nature Scene Barataria Preserve" the entropically
Color Transfer:
34

---

Published in Transactions on Machine Learning Research (12/2023)
c=1
C=2
c=5
c=10
c=
c=1
c=2
c=5
c= 10
c=
Figure 16: Bunny and Armadillo partial point cloud registration using entropically regularized subset se- lection SS-Entropic y = 0.05, fails to find a accurate alignment of the source with the partially occluded target.
regularized results appear more monochromatic with less distinct colors. In the second set of images, there is no visual difference between the outputs of SS-Entropic and SS-Bregman.
c=1
C- 1 1.25
1-1.5
C= 1.75
2
c=4
C=
16
a
c=1.25
1=1.5
c=1.75
c=2
c=4
C=8
c=16
(b)
Figure 17: Color transfer results for cE (1, 1.25 1.5, 1.75. 2,4,8,
244,,666 16) using SS -S-Entropic.
35

---

Published in Transactions on Machine Learning Research (12/2023)
C Appendix: Comparison with Semi-Relaxed Formulations
We analyze the variation of subset-sclection mass assignments vi Li=1 Pij. for [n]] as function of for source and larget points (m 100, n = 80) given in Figure We use SS-Entropic and SS SS-Bregman and compare to solutions for the subset selection linear program using CVXPY (Diamond & Boyd 2016; Agrawal ct al. 2018). We also use CVXPY to solve following semi-relaxed unbalanced optimal transport problems of the form
1 Dr (P' 1mlly) (P.M) + 0
min P&0
s.t. Pl He,
where Do E (TV, E2, foc) can be either TV distance (TV), squared Euclidean (6), or fx-norm based distance, and p > 0. It can be observed from Figure 18 that the sparsity patterns of mass assignments obtained using SS-Bregman closely match the linear program solutions across a range of c, whereas mass assignments obtained using SS-Entropic are more dense with less mass assignments equal to 0. The sparsity patterns for penalty-based relaxations differ from the linear program solutions. By comparing the mass assignments of different solutions in terms of number of non-zeros, ie., the cardinality of the support of solution's marginal v", denoted as (card), we note that the assignments obtained using subset selection have the largest entropy, which implies that subset selection tends to assign uniform masses to the selected subset of points. In comparison, the TV-based penalty, corresponding to the f-norm tends to have sparse deviations from uniform 1 with many points at exactly this value. Entropies of n* are plotted in Figure 19
To further elaborate our observations, we plot the mass assignments to unlabeled data points v, across different values of scaling parameter e for MNNIS/EMMIIS PU lcarning in Figure 20 and Figure 21 for CIFAR-10 PU learning, as discussed in 3.3 and compared that with the mass assignments using semi- relaxed formulations (f2 and TV) with different values of regularization parameter p. We observe that paths taken by our formulation differs from both &2 and TV. But the solutions correspond at the extreme limits: as p + 0 and + 1 all solutions approach optimal transport solution, similarly as + oc and V c 2 c* mass assignments correspond to nearest neighbor solutions discussed in the Section 2.1 For PU learning experiments on MNIST/ /EMISST and CIFAR1O, we used the POT toolbox Flamary et al. (2021) function optim, semirelaxed_oe _ag to obtain the solutions for semi-relaxed optimal transport problem with TV and squared-Ey penalties via the Frank- Wolfe conditional gradient algorithm.
D Appendix: Relation between Entropically Regularized Subset Selection and Unbalanced Optimal Transport
Using the notation from our paper, we have adapted the formulations for the unbalanced optimal transport with asymmetric penalties from the work by (Séjourné et al. (2019). For 41, P2, the generating functions for the divergence penalty functions the marginals, and entropic regularization parameter 7 >> 0, the unbalanced optimal transport for discrete probability measures μl, v, and cost M is
HOT (H,
min
(P.M) DDy (P1 DDpz (P + (Kl(P)
P
PiS
E, Poj
min PER
(P.M) +
Σ
+
VPPP2
14
111
i=1
1=1
Pi (Pgg(Pg)) - log(uiu;)
- Σ
Pij + Σ Mil1i)
()
P.M + Σ piPpl Ej Pss.
Σ, Pij
min PER
+
Σ
11lp2
Mt
V4.
+7
(P, P)
11)-mmm 1mxa) Σ Ms log(ns)
ΣΣ
Pej log(us) +1)
36

---

Published in Transactions on Machine Learning Research (12/2023)
S--Bregman
0.10
0.10
0.00
0.08
0.08
0.06
3.06
0.08
0.04
0.04
11
15
TV-penalty
Ep-persltty
f--penalty
0.00
0.08
0.06
0.04
0.04
0.04
0.02
0.02
(a)
S24F
402-
375
16
56
cardiv))
(b)
Figure 18: (a) The variation of mass assignment vector D² with for toy problem in Figure using SS-En Entropiriicc SS-Bregman, and the subset selection linear program 2 is solved using CVXPY Agrawal el al. (2018); Diamond Boyd (016).. All divergence regularized semairelaxxed problems are also solved using CVXPY. (b) Entropy versus cardinality selected set of points. It can be observed that SS-Bregman and t solutions match each other until support cardinality of around 40. This is due to fact that subset selection
solution matches unique foo pemalized solution for all values of 2.
55-Entrapic
trepmur 15/
S5 Brogman SS-UP
4.00
4.0-
3.75
375
3.50
3.5
325
3.00
3.00
2.75
275
10
16
15
c(p)
Figure 19: (a) Entropy of mass assignment vector D² with e for toy problem in Figure 2 (b) Entropy as function scaling parameter for penalized relaxed-OT problems c(p), obtained using formula c(p) = max (e) which implies that for sufficiently large values of p, c(p) c"
37

---

Published in Transactions on Machine Learning Research (12/2023)
SS-Bregman
TV-penalty
t ty-penalty
0.020
0.020
0.020
0.015
0.015
0.015
0.010
0.010
0.010
0.005
0.005
0.005
0.000
0.000
0.000
10-3
10-1
10a
10a
10-2
10-1
10a
10a
Figure 20: Mass assignments v² to unlabeled data points in PU learning on MNIST/EMNISS discussed in across с for Bregman and across p for TV and le penalties.
Section 3.3.1
SS-Bregman
TV-penalty
Iy-ennaty
0.10
0.08
0.08
0.08
0.06
0.06
0.06
0.04
0.04
0.04
0.02
0.02
0.02
20
40
60
10
10-2
10"
10²
10-1
10
10"
102
P.
Figure 21:
Mass assignments v¹ to unlabeled data points in PU learning on CIFAR-10 neural network
representations, discussed in Section 3.3.2 across e for SS-Bregman and across p for TV and la penalties.
0,
==1
When (21))))
is the indicator function for the ratio of the target marginal and 00, otherwise
0,
[0
(2(x) (x)
is a range constraint the interval of [0, c] for the ratio of the source otherwise
marginal, then
(u, min (P,M) + ((P, 1mxn) (M,, log(u)) (11mm. 1m. log(v)) + 1)
PERmXn
s.t. Pl, =, p. P 1m $ av.
With these choices of f1, and uniformly weighted source vs E, E, Psy log(u;) = - log(n), then HoT (2)) (u, s (u, cv) + (H) - log(n) + 1), where H(n) = (1, log(u)) = E. us log(u4). The uniformly weighted source is necessary to eliminate the bias towards v for the marginal that the Sullback-Leiller divergence penalty induces compared to our entropy penalty, which only considers v through the constraint.
n Vi [n], we can relate sfa) (H, cv)
to (OT()1w2)) (1, v), since (PT 1m,
11, log(p)
E PU Learning Toy Comparison Test
In order show evidence that subset selection, as a semi-relaxed partial optimal transport, can consistently outperform fully-relaxed partial optimal transport on PU learning, we plot the mean accuracy for range of examples using of the same design those in Figure 22
38

---

a. for our Published in Transactions on Machine Learning Research (12/2023)
0.96
0.94
PU learning accuracy
0.92
0.90
0.88
0.86
0.84
100
200
300
400
500
600
700
800
Unlabeled batch size
88, (-(-39
SS, y (0-
SS, -ー 9.
SS, 1-
FR-PW, w-(-E.9)
FR-PW, w
FR-PW, 4
FR-PW, w-
Figure 22: PU learning accuracy toy data using subset selection and fully-relaxed partial optimal transport. Subset set consistently outperforms fully-relaxed on this toy data. Data is generated [r cos(v), rsin(v)] where the radius r is drawn from a truncated exponential distribution with density exxp(r)))ng2.c011 and zi is uniform over the set of angles |- _ 2 31 for the source and different subsets for the target as indicated the legend. For each run m 100 positive points are drawn and the size of the unlabeled sample is varied from n 100 n s00 while are all from the third class. The solutions are obtained using the known number of positives n. out of the source points, setting π. semii-relxed approach and s at for the fully-relaxed partial optimal transport. Confidence intervals show +1 standard deviations of the accuracy across 100 runs.
39

---

Published in Transactions on Machine Learning Research (12/2023)
F Appendix: Neural Network Model Architectures
For semi-supervised learning, we used neural networks to both perform the classification and provide learning representation space in which to perform the optimal transport to assign pseudo-labels to both unlabeled points. For the CIFAR-10 data set, we used the ResNet-18 (He et al. 2016) architecture. For MNIST and Fashion-MNIST, we used custom, but simple, model architectures. Both architectures contain two convolutional layers, followed by three fully-connected layers. The model used to train Fashion-MNIST (FMNIST) classifier contains additional batch-nnormlliztioon layer between the convolutional layers. Opti- mization algorithms along with related hyper-parametert exact architectures along with types and shapes of all transformations.
in Section 3.4
The code below details the
ämport torch
import torch
import torch functional
class MNIST KNIST_classing classifiieee Module):
__init__ (self): super .0._.init__
self. conv1 nn Conv2d (in_ in__haanele--, out out_channels-S, kernele sizeel_siee(( (5,5))
self. conv2 nn. Conv2d (in_channels-5, out out_channels=1, kerkel sernel_sizer size- (5,5))
10
self.fe fet fc2 fc2
an an. Linerr (400, 128)
11
an an. Linear (128, 64)
12
self fc3 an. Linear (64, 10)
13
14
def forward x):
= F.relu(self, conv1 (x))
F.relu conv2
torch.flatted (x, 1)
F.relu(self. (x))
x_rep (sel fc2 (x))
20
self fol_ree x, x_rep
21
23
class FMNIST FMNIST_classiNN classifier (nn. :odule):
34
def
_.init__ (self):
25
super Q....iittt..
26
self convi nn Conv2d (in_ (oancn(in_chenneeeee 3ut_chhanel==-2, fernel_size- 5))
27
belf.batchN1 nn. (t..atchhoonn2((nnn_aauuuu (eatureeee_ calf.conve nn. (hn out out_chammels=4,, kernel_ sizeel_ 5))
28
29
felf an www.ieerrin_
out fet_feature--1288
30
self.fet fc2 an. Linerr (in_tariin_etuueeeeeeeeee
out out_features-6d)
31
self fc3
an. an. Linea (in_ out fut_feeatues-100)
def forward (self, (self,, x):
= self. convi (x)
F.relu max_paaal_ppppaaee.
kernel_size-2 stride-2))
self batch
col)
(Frelu(F. ..roluff.ax..poo2(appte kernel_size=2, stride=2))
39
(x,
40
F.relu(self.fc1(4))
41
x_rep (x)
42
self.fc3(x_rep)
43
return x, x_rep
Listing 1: Models used for training classifiers for MNIST and Fashion-MNIST
40


Reviews:
[{"review_id": "s5aFp6Acce", "reviewer": "Reviewer_sJdW", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written; it is extensive, but that is because the authors give a great amount of detail, which I consider to be positive in this type of article, blending concepts with applications. \n\nThe conceptual part is very clearly presented, the authors re-derive the Sinkhron approach for the particular case of partial OT, and the procedure is presented in a detailed manner to the reader.\n\nThe experimental validation is superb. The treatment and explanation of the experimental aspects are very deep and informative. \n\nSome points can be improved in the paper, but they are mainly related to the presentation and not methodology (so listed in the next section of the review) **except the following ones**: \n\n- how can the scaling factor be chosen? The article provides multiple instances to compare how the methodology performs for different choices of $c$. However, in real applications, $c$ is not known and needs to be chosen. By arbitrarily choosing this factor, the method will leave parts of the support unmatched to the target (as shown in the first experiment), so a naive choice can lead to misleading conclusions. Can $c$ be chosen in a way that is more principled than just the ratio between the points one wants to match and all the points? (because one could not know how many points should be matched)\n\n- Also, why is only the uniform case considered? In the toy example, the application of the method to this kind of distribution appears to result in removing the parts of the support that are far away from the target, to then rescale the source and apply complete OT", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The article deals with partial optimal transport, that is, when the target and source measures do not maintain the entirety of their mass over the transport. In particular, the authors focus on a specific case where the measures are discrete and uniform, to propose a methodology for a particular case where it is only for the source that only part of the mass is transported. \n\nThe paper is well presented with sufficient experimental validation", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "i) Please refer to my comments above\n\nii) Sec 2.2: *Cuturi applied entropic regularization* please refer to works, not persons\n\niii) Secs 2.2, 2.3, 2.4 seem to propose a methodology and then the next section refutes them to propose something \"better\". In my opinion (if I am correct) this weakens the proposal of the paper. If possible, please reformulate. \n\niv) Possibly rename \"algorithm 1 / algorithm 2\" so that in the experiments they are not referred to as such. Idea: SS-entropic and SS-Bregman (or other appropriate names)\n\nv) Sec 3.2 reads *It can be observed that the results for larger values of c are smoother and sharper as compared to the optimal transport case c = 1.* Can something be **smoother and sharper** at the same time?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "57ApiuAq7Y", "reviewer": "Reviewer_BRfh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\n- Fairly well motivated problem / solution. \n- Theory and experiments seem sounded overall. \n- Large set of experiments, and performances seem convincing as far as I can tell. \n\n\n# Weaknesses\n\n- As far as I can tell, from a theoretical perspective, the paper only plugs together known tools (Partial OT from Figalli, entropic OT a la Cuturi, Bregman projection from Xie et al). In particular the first two points of the contributions (page 2) are disputable as, unless I am missing something, there is no real novel problem/method introduced in this paper from a theoretical perspective. \n- Related to the previous point, I would have appreciated more insights on the problem considered. Namely, the paper consider a subcase of Figalli's partial OT problem (transporting the whole $\\mu$ and considering discrete measures with mostly uniform mass), but as far as I can tell the specificity of this formulation is never used (aside from the experimental intuition); everything developed in this paper could be adapted to POT faithfully, isn't it? \n- A more detailed comparison with state-of-the-art theoretical and/or computational approach would be important. For instance, [this work](https://arxiv.org/pdf/1910.12958.pdf) by Séjourné et al., already propose a Sinkhorn scheme for Partial OT (which correspond to taking the total variation as marginal divergence) and I think that the dual problem / Sinkhorn algorithm derived is substantially equivalent to their algorithm. The work of Chapel et al. is not described either while being used as a major competitor in experiments. Right now, it is hard to assess how \"fair\" the comparison is. \n- The choice of the parameter $c$ is not discussed while it is showcased to play an important role in terms of experimental results. Intuitively, it interpolates between standard OT (possibly with entropic regularization) and \"nearest-neighbor Transport\", the latter being simpler to compute than the former. As such, I think that a natural question (that would be an interesting contribution as it would depend on the specific context of the paper) would be to know whether the computational complexity decreases as $c$ increases (similarly to the entropic regularization parameter, see (Feydy et al., 2019)). \n- Clarity can be improved in some places, see the \"Minor remarks\" below.\n\n\n# Minor remarks and suggestions\n\n- While the Remark in page 4 feels interesting, it is never leveraged later on as far as I can tell. If not, I think it could be deferred to the Appendix. If it plays an important role (e.g. as a way to somewhat bound the support of $\\nu^*_c$ or so), this should be highlighted. \n- [clarity] I'm a bit failing to see the point of introducing the two settings $P1 \\leq c  \\nu$ and $P 1 \\leq \\zeta$, given that we could always write the later $P 1 \\leq \\|\\zeta\\| \\underbrace{\\frac{\\zeta}{\\|\\zeta\\|}}_{=: \\nu}$. I think that it would make things clearer to stick with one or another formulation, and only briefly mention the equivalence between these two settings. \n- [clarity] The variable $\\xi^{(k)}$ is only defined in the Algorithm 1; which makes equation (13) hard to parse at first glance. \n- A more extensive presentation of the work of (Xie et al., 2020) would be useful given the role it plays in the current work. \n- [clarity-ish] In Section 2.4, I think the presentation would be enhanced by immediately saying that we have access to a close form for $\\theta$, but that relying on mini-batch gradient descent has merits (I was first really confused about the need of running a gradient descent for a simple weighted linear regression). \n- [clarity] In the experiments (Figure 3 and 4), what are the 500 iterations on the $x$-axis? The caption only mentions 200 inter and outer iterations. From page 26, it seems to be a comparison point between Alg. 1 and 2. Please clarify this. \n- The overhead (if any) of using Algorithm 2 instead of Algorithm 1 is not discussed as far as I can tell (even in the supplementary material).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers (a special case of) the _partial optimal transport_ (POT) problem, as introduced by Figalli (2010). Namely, in this work, authors consider two probability measures $\\mu,\\nu$ (typically discrete), \n\n$$ \\min_{P} \\braket{P,M}, $$\n\nfor some cost matrix $M$, provided that the first marginal $1^T P$ of $P$ should be $\\mu$ (so the total mass of $P$ must be $1$), but its second marginal is only required to satisfy $P 1 \\leq c \\nu$ for some prescribed $c \\geq 1$ (hyper-parameter). \nThe main idea is that the second marginal of the optimal solution to this linear program, denoted by $\\nu^*_c \\leq c \\nu$ is a probability measure that can be seen as a \"subset selection\" problem. \n\nEven though this linear program can be solved by standard (simplex, interior points) methods, better computational properties can be achieved by considering its entropic regularization, adding a term $+ \\gamma \\braket{P, \\log(P) - 1}$. Standard duality considerations yields a Sinkhorn-like algorithm with respect to two dual variables $(\\alpha,\\beta)$, where the standard log-sum-exp iteration holds for $\\alpha$ while for $\\beta$ a projection step on the non-negative ortant is required (as a consequence of the submarginal constraint). \n\nAs typical in entropic OT, the resulting (partial) transport plan has a density with respect to $\\mu \\otimes \\nu$, which is somewhat in contradiction with the \"subset selection\" motivation of the problem. \nTo mitigate this effect, authors follow the work of (Xie et al., 2020) and rely on an additional Bregman projection scheme , which can also be solved using a Sinkhorn like algorithm, yielding a sequence of transportation plans $P^{(t)}$ which are guaranteed to converge toward a solution of the _unregularized_ problem (with sparse support in general).\n\nAuthors support the feasibility and usefulness of their approach on an extensive set of experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- [Critical] Having a better understanding of the benefits of the proposed setting (having one exact marginal, and one submarginal ; working with discrete measures). And if there is no such benefits, re-write the theoretical part of the paper in a more general setting. \n- [Critical] A better presentation of related works to make the contribution of the present paper more salient. \n- [Enhancement] Improving the clarity of the paper (see \"Minor remarks and suggestion\" above).", "broader_impact_concerns": "No broader impact concerns as far as I can tell.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v66HP9Ej9z", "reviewer": "Reviewer_4Dfp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths of the paper**\n\nThe paper is mostly comprehensive in the formulation of the problem and on the description of the algorithms. The experiments provided showcase the behavior of the proposed method in a wide variety of contexts, from toy examples that illustrate the behavior of the solution (in particular, the impact of the parameter that tunes the \"partialness\" of the solution) to experiments in image and machine learning contexts, showing that the problem that is addressed is useful in a number of applications.\n\n\n**Weaknessess of the paper**\n\nWhile relaxing one of the two marginals' constraints has previously been proposed in existing literature, there is a lack of discussion regarding how the proposed approach positions itself in relation to the current state of the art. For instance, [1], p. 2, paragraph \"Relaxed Weighted OT,\" relaxes the matching constraint towards one distribution by introducing a set of relaxation parameters to increase (or decrease) the capacity value of each sample; [2], eq. (14), defines the \"semi-relaxed OT,\" in which one of the marginals is free.\n\nIn the context of support subset selection, one advantage of using partial OT is that it defines a set of active regions, that is to say a subset of the samples. As stated in section 2.3, the entropic formulation of the problem yields denser couplings, which may be detrimental to the identification of active regions. A Bregman Proximal-point method is provided in Algorithm 2; as mentioned in the paper, it can result in infeasible solutions and/or high computational time. One might then wonder why not utilize a different yet related problem for active region identification that would inherently leads to sparse solutions, such as unbalanced OT with an $\\ell_2$ penalization rather than an $\\ell_1$ one, as in [2]. \n\nFurthermore, the experimental section lacks comparison with competitors.\n\n\n[1]  RABIN, Julien, FERRADANS, Sira, et PAPADAKIS, Nicolas. Adaptive color transfer with relaxed optimal transport. IEEE international conference on image processing (ICIP), 2014.\n\n[2] BLONDEL, Mathieu, SEGUY, Vivien, et ROLET, Antoine. Smooth and sparse optimal transport. International conference on artificial intelligence and statistics, 2018.\n\n\n*Other comments*\n- In the introduction, the second paragraph discussing partial OT might be misleading. When $\\mu$ is discrete, the TV norm is equivalent to the $\\ell_1$ norm of vectors, hence it comes down to a partial OT problem.\n- On page 4, the claims regarding extreme points and breakpoints lack supporting arguments.\n- Regarding the PU learning experiments, it remains unclear why the relative ranking provided by the entropic formulation outperforms the unconstrained one. Could you please elaborate on this point?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper deals with the problem of solving an instance of a semi-relaxed optimal transport problem, which differs from the original OT problem by relaxing the constraint on the marginal of one of the distributions. Algorithms to solve the problem are described, and a set of experiments, ranging from toy examples that illustrate the behavior of the solution, to color transfer, PU learning, and semi-supervised learning, is provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses about the position of the paper with respect to the literature and justification of the formulation (entropic formulation of a partial OT problem).", "broader_impact_concerns": "There seems to be no ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agreed that while this work might not be totally original, it provides a new formulation for partial OT and interesting experiments, they all lean toward accept.

Some minor comments from the final discussion with reviewers that should be taken into account in the camera ready:

- p2 "Recent works have proposed algorithms for computing the entire scaling or regularization path of solution [...] semi-relaxed unbalanced optimal transport (Chapel et al., 2021)": the work of (Chapel et al., 2021) also computes the regularization path of the UOT problem, not only the semi-relaxed version.
- in Fig. 2, I would recommend scaling the point size wrt the amount of mass points to better illustrate the creation of mass.
- Fig 3 and 4 : the points are not visible (for all c>1 and theta opdate) in the pdf reader from google chrome (they are visible in local PDF reader) please solve this problem for final version.
- It is claimed "However, the main difference with this relaxation [(Chapel et al 2020)] as compared to our approach (or other semi-relaxed approaches) is that points in the target may lose mass or be completely dropped". It is still unclear why the proposed method and the one of Chapel et al, 2020 should give different accuracy results in a PU learning context as "accuracy is evaluated by assigning label 1 to the largest mass assignments to and label 0 to the remaining mass assignment". Please discuss and give more details about  this.
- Fig. 9 (a): It is not clear why the-sampling is not the same.
Decision: Accept (poster)