On Robust Optimal Transport: Computational Complexity and Barycenter Computation
Authors: Khang Le
Huy Nguyen
Quang Minh Nguyen
Tung Pham
Hung Bui
Nhat Ho
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimal transport
optimization
complexity
robustness

Abstract: We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibler divergence. We show that Sinkhorn-based algorithms can approximate the optimal cost of robust optimal transport in $\widetilde{\mathcal{O}}(\frac{n^2}{\varepsilon})$ time, in which $n$ is the number of supports of the probability distributions and $\varepsilon$ is the desired error. Furthermore, we investigate a fixed-support robust barycenter problem between $m$ discrete probability distributions with at most $n$ number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case $m = 2$, we show that this algorithm can approximate the optimal barycenter value in $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon})$ time, thus being better than the previous complexity $\widetilde{\mathcal{O}}(\frac{mn^2}{\varepsilon^2})$ of the IBP algorithm for approximating the Wasserstein barycenter.

On Robust Optimal Transport: Computational Complexity and Barycenter Computation
Khang Le*
Huy Nguyen*
Quang Minh Nguyen
University of Texas, Austin
VinAI Research
Massachusetts Institute of Technology
khanglnt@utexas.cem edu
Muyym12@vinee iio
nmquang@mit.cc
Tung Pham
Hung Bui
Nhat Ho
VinAI Research
VinAI Research
University of Texas, Austin
tunggh44@vinai.. io
minhnhat@utexas.c edu
Abstract
We consider robust variants of the standard optimal transport, named robust optimal transport, where marginal constraints are relaxed via Kullback-Leibh divergence. We show that Sinkhorn- based algorithms can approximate the optimal cost of robust optimal transport in Ö a² time, in which n is the number of supports the probability distributions and is the desired error. Furthermore, a fixed-support robust barycenter problem between m discrete probability distribu- tions with at most n number of supports and develop an approximating algorithm based on iterative Bregman projections (IBP). For the specific case m = 2, we show that this algorithm can approximate the optimal barycenter value in O O(mn²)
investigate
time, thus being better than the previous complexity Ō mn² of the IBP algorithm for approximating the Wasserstein barycenter.
1 Introduction
The recent advance in computation with optimal transport (OT) problem [12, 13, 22, 26, 20] has led to surge of interest in using that tool in various domains of machine learning and statistics. The range its applications is broad, including deep generative models [4, 16, 36), scalable Bayes [33,34], 34], mixture and hierarchical models [24], and other applications [32, 29, 10, 17, 37, 35, 8).
The goal of optimal transport is find minimal cost of moving masses between (supports of) probability distributions. It is known that the estimation of transport cost is not robust when there are outliers. To deal with this issue, [38] proposed trimmed version of optimal transport. In particular, they search for truncated probability distributions such that the transport cost between them is minimized. However, their trimmed optimal transport is non-trivial hinders its usage in practical applications. Another line of works proposed using unbalanced optimal transport (UOT) to solve the sensitivity optimal transport outliers [5, 31]. More specifically, their idea is to assign as small possible masses to outliers by relaxing the marginal constraints of OT through penalty function such as the Kullback-Leeble (KI.) divergence. This direction of robust optimal transport has been shown to have good performance in generative models and domain adaptation [5]. Although this approach achieved considerable success, the full picture of its computational complexity has remained missing.
compute, which
Khang Le and Huy Nguyen contributed equally to this work.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Our Contribution: In the paper, we provide a comprehensive study of the computational complexity of robust optimal transport and its corresponding barycenter problem when the probability distribu- tions are discrete and have at most n components. Our contribution is twofold and can be summarized as follows:
(1) On robust optimal transport, we consider two versions corresponding to two ways of relaxing marginal constraints in the standard optimal transport problem via the KL divergence. We show that two scaling algorithms computing these robust formulations have the complexities Ö(n²/e)) where denotes the desired error for the computed cost. These complexities are lower than the complexity of the Sinkhorn algorithm for solving the optimal transport problem, which is O(n2/=²) [13], and match the complexity of the Sinkhorn algorithm that solves the UOT problem [27]. Furthermore, we show how the above complexity can be improved by utilizing the low-rank approximation method to speed up the matrix-vector computations in the loop similar to [2], and obtain the improved computing time of Önr + ) where r is the approximated rank.
(2) On robust barycenter problem, where the goal is to determine a probability measure that minimizes its robust optimal cost to a given set of m 2 2 probability measures, we propose ROBUSTIBP algorithm for solving the robust barycenter problem, which is inspired by the iterative Bregman projection (IBP) algorithm for solving the traditional barycenter problem [6]. We show that when m = 2, the complexity of ROBUSTIBP algorithm is at the order of O(mn" /E), better than that of the IBP algorithm for solving the traditional barycenter problem [19], which
O(mm² / To the best of our knowledge, the ROBUSTIBP also the first practical algorithm obtaining the near-optimal complexity O(mn²/e) /E) for solving the barycenter problem even under only the setting m 2.
The paper is organized as follows. In Section 2, we provide the background on the optimal transport problem and some of its variants that have robust effects. In Section 3, discuss in-depth the variant where only one marginal constraint is relaxed, study the computational complexity of a Sinkhorn-base algorithm that solves it, and then briefly introduce the fully-relaxed formulation. We also establish the complexities of these algorithms after applying Nyström method. Subsequently, we present study of the robust barycenter problem in Section 4. In Section 5, we carry out empirical studies to illustrate the theories before concluding with a few discussions in Section 6. The proofs of our theoretical results in the supplementary material.
Organization:
We let [n] stand for the set [1, .,,,,...u ........, n1 while IR indicates the set of all vectors with non- negative entries. For a vector x E Iº and p E [1, oo), denote ||>||p its E, -n-m and diag(z) (x) as the diagonal matrix with x on the diagonal. The natural logarithm of a vector a = (a1, ... an) E RT is denoted by log equal to 1, and 0, f refers to the partial differentiation of function f with respect to x. For any given space X' C Rd we denote by P(X)) the space of all probability measures on X. Given an integer n > 0 and a real number > 0, the notation a = O ()) means that a S C b(n,e) where C' is independent of and e. Meanwhile, the notation = (b(n,e)) indicates the previous inequality may depend on a logarithmic function of n and E. For any two probability measures (I1,..., ,In) and y = (91,... Bnn) with the same supports, the generalized Kullback-Leibler divergence is defined as KL(X|)) = Σm= I log [1) 2, + v:l. Finally, the entropy of matrix X is given by (X) Σij=r -X;; X 1).
Notation:
(log 01, ..,, log a,). 1, stands for vector of length that all of its entries
2 Background on Optimal Transport
In this section, we review optimal transport and its unbalanced formulation, then from that deriving formulations for robust optimal transport. For any P and Q in P(X)) for space X, the OT distance between P and Q takes the following form
f f c(xx,))dx =EI((P.Q)
OT(P, = min
where IT(P, Q) is the set of joint probability distributions in x X' such that their marginal distribu- tions are P and Q, and e: X X [0, oo) is cost function.

---

Unbalanced Optimal Transport: When P or Q is not a probability distribution, the OT formulation between P and Q in equation (1) is no longer valid. One solution this issue is using the unbalanced optimal transport (UOT) [9], which is given by:
(OT(P,Q) == min (EM,(XXxx). / c(d,,)dd y)dr(a v) + (I( + (L((12)1))
(2)
where MM x X²) denotes the set of joint non- non-negatvve measures on the space X' x X:; 11, T2 are the marginal distributions of ιτ and respectively correspond P and Q: 71, 72 are regularized positive parameters. Note that, we can replace the KL divergence in equation (2) by any Ciiszár-divergence [1I]. However, we only consider the case of KL divergence in this work.
Robust Optimal Transport: Optimal transport is well-known for not being robust in the present of outliers. A way to deal with this issue is using the approach of unbalanced optimal transport (UOT), which has demonstrated favorable practical performance in generative models and domain adaptation [5]. More specifically, when P and Q are probability distributions in X, the Robust Unconstrained Optimal Transport (ROT) admits the following form
inf ROT(P,Q) = PL.QIEP(X) =EI((P...)) /
ʃ c(x, y)d + KL(P)))) + (Q)(II), (3)
min
where Tı, 72 > 0 are some given regularized parameters. The reason to name it robust unconstrained optimal transport is that instead of looking for optimal transport plan moving masses from P to Q, we seek another plan that optimally transports masses between their approximations, which probability measures P1 and Q,, under the KL divergence. This formulation is closely related to the ones studied in [5] and [23]: the former used x x²-divergence for the relaxation and the latter used total variation distance (note that those three divergences all together belong the family of f-divergence).
By relaxing only one marginal constraint regarding (presumably) on P. we have another version of ROT, named Robust Semi-constrained Optimal Transport (RSOT), which is given by
RSOT Q)
inf min PLEP(X) RETT(P:.Q) /
/ c(xx y) (z, v) (KL(P)))),
where T > 0 is a regularized parameter. We could also define RSOT(Q, P) similarly with a remark that although RSOT(P. Q) can be different from RSOT(Q, P), the techniques for obtaining the computational complexity of both are similar.
Though the formulations ROT/RSOT and UOT seem to be similar, they serve different purposes. The goal of UOT is deal with unbalanced measures, thus there is no condition on the "transport plan". Hence, the meaning of the optimal plan ı of UOT problem is dependent on the interpreter. For example, in applications such as [30], the UOT used to figure out the developmental trajectory of cells. Meanwhile, ROT/RSOT aim to seek an accurate transport plan between two possibly corrupted probability distributions. The toy example in Figure 1 illustrates this difference. In particular, the marginals of the "transport plan" obtained by the latter (see plots (b), (d)) are very different from the two original probability measures a, b. On the other hand, the solution of the former leads to good approximations of and b (see plots (a), (c)) while removing some bumps in both tails which are presumably outlicrs.
UOT vs ROT/RSOT:
3 Discrete Robust Optimal Transport and its Computational Complexity
When P and Q are discrete measures, the KL penalties in equations (3) and (4) suggest that the prob- ability distributions P1 and Q1 need to share the same set of supports as that of P and Q. respectively. Therefore, throughout this section, we implicitly require this condition in our formulations of RSOT and ROT and we denote the masses of P and Q by and b, respectively.
3.1 Robust Semi-constrained Optimal Transport
Assume that the marginal constraint associating with Q is kept and that of P is relaxed and P1 and P share the same set of supports, the formulation of RSOT in equation (4) can be rewritten as follows
min
Snoi( (X) = (C, X) + +KKLLXX |la),
(5)
XeR X XT1, =b
3

---

15
Dust
Dust
0.02
0.00
200
50
150
(a)
(c)
(d)
Figure Comparison on marginals induced by ROT/RSOT solutions and UOT solutions. Here a, are two (possibly corrupted) 1-D Gaussian distributions on which we compute the optimal transport, and Aproblem]] [[problem] represent two marginals (with respect to a and b respectively) of the optimal solution for the corresponding [problem]. In plots (a), (b), we compare ROT and UOT where both and b contain (10%) outliers from other Gaussians, while in plots (c). (d) investigate RSOT and UOT where only is corrupted.
Algorithm 1: ROBUST-SRMISINKKEN
Input: C, b, Fiter Initialization: un 00
while h < Diter do a Buu², II, bt + (B(u+, xt)) T 1n
if is even then
y7
=n log(a) log(a*))
g+
wh- t x
else
wh+1 +- ut
k c- 1 + log(b) log(b*))
end
k <- k + end while
return Bt v*)
where a, b are the masses of P and Q respectively, and C the cost matrix whose entries are distances between the supports of these distributions. Solving directly problem (5) by traditional linear programming solvers can be expensive and not scalable terms of n. Therefore, we utilize the entropic regularization approach proposed by [12] to the objective function of RSOT, leading to
min XER X
Fisot (X) Sisot (XH
Here, 7) > is given regularization parameter, and we refer the problem (6) to as entropic RSOT. The dual problem of entropic RSOT is
Prsa (u, v) = BllB(u, w)Il + + =(e- a) -1) (), M.VER"
min
(7)
where Buu, v) is defined as matrix of size x n with entries [Buu, r)lis t O,y)// Since equation (7) is an unconstrained convex optimization problem, we can perform alternating and Ōh(u, v)/Ou = O, resulting in closed-form updates of a Sinkhorn-like procedure (see [12]) in Algorithm 1. This procedure is known to converge to the optimal solution (u* (") := arg min (1, v). As strong duality holds for the convex optimization problem (6), the optimal transport plan of the entropic RSOT is exactly B(u","").
minimization for u and v by setting Øh(u, v)/Ou
Since no assumptions are made on the cost matrix, except its entries non-negative, closed-form solutions of OT and UOT generally do not exist. Therefore, we introduce the definition of an E-approximation solution of an optimization problem, which will be used for all the subsequent complexity analyses.
Definition (--approximation). For any O, a transportation plan X is called an approximation of the minimizer X of some objective function if f(X) - f(X) +

---

Based on this concept. we then state our main theorem on the runtime complexity of Algorithm 1 in solving the RSOT problem (5).
Theorem For Unat max (3 log(n), and v E/Ursa. Algorithm
returns an
approximation of the optimal solution Xna of the problem (5) in time
Tn o
log(n)
log
[T|[C]]m=) E
logg(og(n))
6
Proof Sketch. The full proof of Theorem is in Appendix B. Note that, this result is not achieved by directly applying Theorem in [27] with 72 - oo as nature the dual function changes that limit, invalidating many previous results. Let rsot be the output of Algorithm at the k-th step while Xisot and Aot denotes the minimizers of equations (5) and (6), respectively. The goal is find that guarantees Fisoe( (xsoe(X(baa) -froot (X1soo) S E ryU/soo. We start by decomposing
froot(
I [ (X - Irsor (Xsor(X + H (( - H (X
(X (X mum) Shoee (maa tigH (Ryor)
and try to bound each term by a linear function of Dealing with the entropy term is simple as the
factor is already presented, and the entropy difference can be bounded by constant due to the fact
that 1 < H(X)= < 2 log(n) + 1 for all X E _ || I| = 1. The non-trivial part is bounding the difference between Grsoe values, which hinges upon two results. The first one is the value of Gisot at optimality:
Grace (Xise) -1
-1 -1 T(1 (x) + (Misot Misor)
The second result is the geometric convergence rate of the updates and (Lemma in Ap- pendix B):
k/2
max || u² uooo |10 ++ 1oo (const)
A
T
The final step is using equation (8) to tailor the Gisor difference to be bounded by linear function of A which is an exponential function of k, then solving for the minimum & at which this exponential function is small enough compared to n. The main technical difficulty here is to deal with the unknown term (D (ao))) in equation (8), which causes the deviation from the previous techniques.
Remark 1. The result of Theorem indicates that the complexity of ROBUST- ROBUST-SEMI SEMIŠINKHORN algorithu for computing RSOT is at the order of Ō(n²), This complexity is near-optimal and faster than the complexity of the standard Sinkhorn algorithm for computing the optimal transport problem [13, 22], which the order of ( n²
3.2 Robust Unconstrained Optimal Transport
In this section, we briefly present another version of robust optimal transport, abbreviated by ROT, when two distributions are contaminated. We first show that the approach of using the duality of the objective function of ROT problem with entropic regularizer does not produce a Sinkhorn algorithm in the cases of RSOT and UOT. However, a second thought of the problem finds an interesting link between the optimal solutions of ROT and UOT, which results in a nice algorithm for the ROT. We also discuss some technical difficulties when analysing the complexity for the ROT problem. At the end of this section, we show that the result could be extended to the case of low-rank cost matrix, which will significantly reduce the computation.
Recall that the masses of P and Q are a and b, respectively, the ROT problem (3) becomes
min
(m)( = (C, + (
+ + 1,,lbb.
XER Kn 1||11=11
Here we set 7i = 72 = r for the sake of simplicity, since there are no more technical difficulties to work with finite π. * 72. As noted in Section 2, the formulation (9) bears some resemblance to the unbalanced optimal transport problem studied in [27], except the additional norm condition forcing X to be a transportation plan (i.e., joint probability distribution), which shows the different nature
5

---

of two problems. Following the approach of using the Sinkhorn algorithm of UOT, the duality of formulation (9) has the form
log [(u, r)lla + (e a) + (c"
By taking derivatives of the above function with respect to a and and set the derivatives to be zero, we obtain
Buu, u) [ e)llı
Blu, v) I -// ④ b, B(u,
e e-u/T a,
where @ denotes element- multiplication. Unfortunately, the above equations do not have closed- form solutions to produce update as the Sinkhorn algorithms do because of the term [B(u, v)ll in the denominator. However, the objective function of UOT is not homogeneous with respect to X, but could be written as linear function of ROT and another function of [|X || due to some special properties of the KL divergence. This observation leads to the interesting result summarized in the below lemma.
Lemma 1 (Connections with UOT). The optimal solution of problem (9), denoted Xis is the normalized version of Xuo which is the minimizer of UOT entropic formulation. More specifically, we have X
The proof of Lemma is in Appendix D. Based on this result, we can utilize the Sinkhorn algorithm that solves UOT (see [27]) with a normalizing step at the end to produce a solution for the ROT. Although the normalizing step convenient in finding ROT's solution, introduces new challenge in the proof compared to that of UOT since the normalizing constant does not have a lower bound. Even so, are still able to obtain e-approximation solution for the ROT in O /s) time without any additional constraints on the setting. For more technical details, please refer to Appendix D.
Further Improving Complexities by Low-Rank Approximation: As a consequence of our com- plexity analysis, we can show that by using low-rank approximation method studied in [2] to the kernel matrix K == exp(-C/n), we could further reduce the complexities of both robust semi/un- constrained optimal transport problem Ö(r + nr/e) time, given the same e-approximation and the approximated-raan -rankk r. This result is essentially different from the complexity studied in [2], where the e-approximation is considered regarding the optimal value of the entropic-reguularize problem, not the original one in our analysis. For a more detailed discussion, please refer to Appendix E.
4 The Robust Barycenter Problem
In this section, we consider the problem of computing the barycenter of a set of possibly corrupted probability measures. The cemi-constrained formulation arises natural candidate for this goal, when potential outliers only appear in the given probability measures and the desired barycenter is the barycenter of the uncontaminated probability measures. particular, assume that we have m 2 discrete probability measures Pı..... Pm: each has at most n fixed support points and the associated positive weights are given by wT. .........ee Wm 2 W/ 1). The barycenter problem then aims to find the probability measure that minimizes Σ -= w WRRSOT(P, (P, P). which is a linear combination of RSOT divergence from the barycenter to all given probability measures. We refer it as Robust Semi-constrained Barycenter Problem (RSBP). this work, we consider the fixed-support settings where all the probability measures P: share the same set of support points. This setting had been widely used in the previous works to study the computational complexity of Wasserstein barycenter problem [19, 21]. Let p; be the mass of probability measure P; for i E [m], the discrete RSBP reads
min PERT JIp
Σ
wi
min X,ER 1.
(C,, + 7KL(X,1, Ip:)
which is equivalent to
min (X)
frsp(() (X) = Σ wi [CC,, X2) +XKL(x,,,lpp)))
(10)

---

Algorithm 2: ROBUSTIBP
Input: [= Pi p T, T,7) Rier
Initialization: u. o = O, for i [m], k 0
while Oiter do
at < Blu : Ci)lm; of - (B( v/; Ci)) In vi e [m]]
if k is even then
ab+1 t gt
[" log(p.) - log(a))) vi E [m]]
o - t o Vi [m]
else
Vi E [m] u ++ 11 t u
u/ o/-1 t n
vt log(b!) 21=1 -E log(b)))
vi [m]
end if
< k+1 end while
X Bl : Ci) Vi E [m]
return (Xf..... ....... X for equation (14)
x x
X
for equation (11).
where D1 (X) : ((. X, R4x" and |X 1 1 [m]:
vi [m - 1]}. Note that the objective function of RSBP is different from that of Wasserstein barycenter [19]: here we relax the marginal constraints X,1, = by using the KL divergence to deal with the contaminated P:. Finally, the constraints X, 1n, I p are to guarantee that the transportation plans X; have one common marginal which turns out to be feasible barycenter Similar to RSOT, consider an entropic-regularizee formulation of (10), named entropic RSBP:
172
min XED, (X)
Jisbp (X)
=
Σ
wi Irsor (a C.).
(1I)
Since some functions like Irsa (X), depends on some parameters like C2 and P;, sometimes abuse the notation by including these parameters next to variables, e.g., Insot (X;; C. Ps). A general approach deal with (11) is consider its dual function, which admits the following form:
hepp (u, v) = Σ wi [n log [Bu,, uy C.)ll + T w17 p.)]. (12)
min
u= (01 Mmm v= (m)
ΣE w
We could use the alternating minimization method to find the minimizer of (12). In particular, starting an initialization u and vo, we update them alternatively follows:
A+ arg min heshp (u, v*), v++ arg min v m00=
hrstp (u k+1 v).
(13)
In some problems (c.g., RSOT), closed-form updates can be acquired if the system equations 0 could be solved exactly by some simple formulas.
Oh (u, v²0 and (u v)/0v However, this is not the case with the formulation of Arsp in equation (12) because the logarithmic term leads to solve the optimization problem (11) via another objective function, whose dual form can be solved effectively by alternating minimization.
intractable system of equations of the partial derivative of hest.. Instead, propose
4.1 ROBUSTIBP Algorithm
We consider similar problem to the entropic RSBP in (11), with its feasible set D(X)
((X,...., Xm) X, Rax", Vi [m]:X]] 1,, 1 1, e [m 1]} which does not have the
7

---

norm constraint. The primal objective function and its dual are as follows:
m
Primal:
min XED(X)
grsbp (X) =
Σ
Wist X5 Pr. Ci),
(14)
Dual:
min
hispp (u, v) =
Σ wi [nl B(u es C.)lli + (/ p.)]
(15)
U.V u.v: DV th w
The dual formulation (15) has closed form updates for u and v. Based on these, we develop Algorithm namely ROBUSTIBP, since this procedure resembles the iterative Bregman projections studied in [6] and [19]. The updates of u and v are known to converge to the optimal solution (u", v*) of the problem (15), and strong duality suggests that X (B(u,, 2 C))) the optimal solution of the problem (14). Furthermore, there is an intriguing relation between the optimal solution of the problem (14) that of the problem (11), presented in the following lemma.
Lemma 2. Let X* = (Xi
Xm) and X
(Xi...., be the optimizers of 9lsbp with the X;
feasible set DXX) and with the feasible set Di (X), respectively. Then, X;
for all i [m]]
11
The proof of Lemma 2 is in Appendix C. This result indicates that we can approximate the solution of equation (11) by the solution of equation (14), using the same Algorithm with an additional normalizing step at the end.
4.2 Complexity Analysis
In this section, we provide the analysis of ROBUSTIBP algorithm for obtaining an e-approximation of the robust semi-constrained barycenter problem (11) when m = 2. We also discuss the challenges of extending the current proof technique to m 2 3 the end of this section. First, we present the complexity of the ROBUSTIBP algorithm in the following theorem.
Theorem 2. For 2 and rj
sop where Unipp max (2 + log(n), 22, 3a log(n)/T), the ROBUSTIBP algorithun returns an e-approximation of the optimal solution , of the Tn² RSBP (10) in time O log(m) log
Σ ICill.. + log (log()) (b0)(N))))
Remark 2. The complexity Ō(n²/8 /E) of ROBUSTIBP algorithm is near-optimal and better than that
of IBP algorithm for solving the Wasserstein barycenter problem, which is O when m 2 in [19]. It is also better than the complexity of FASTIBP algorithu in [21], which is / To the best of our knowledge, the ROBUSTIBP is also the first practical algorithm obtaining the near-optimal complexity O( /E) for solving the barycenter problem under the setting 2.
The main ingredient in the proof of Theorem 2 is the convergence rate of vectors u and v of the problem (15), which is captured follows:
max Σ
Σ A 1 <
(constant)
T
k/2
(16)
where Aut ur f++1 of and Auf k+1 vf- The result can be achieved by alternatively
applying two following inequalities.
For the first inequality, with even k. from the update of ++1 in the Algorithm 2, we obtain ||An++1|l I| < -
The second inequality obtained from the update of v in Algorithm 2 as follows:
Σ E
Σ (m 2)wx + 1)
1 -1
Thus, when m = 2, we can achieve inequality (16), though this approach inapplicable for the case
>> 2. For a formal statement regarding the above convergence rate, please refer to Lemma 12 in

---

iberation
18
F+
T+1
1.5
22
(0]
772
(6) 772 3
(c) m 10
Figure 2: On the convergence rate of RSBP dual variables when m E {2, 3, 10). Lines with different colors
present different runs (with the same values of = 0.1 and = 0.01). Other parameters are set as follows: 10, O 4(0.01111 1jnxn.
Appendix C. Note that for m 2 3, the result Theorem 2 still holds u and v converge at the rate of the order (,+7) )k/2 So next we will take closer look at this case to see whether the rate remains geometrie.
Em A Em |
On m 2 3: In Figure 2, plot the values of two ratios: Rie
and Rus
E IAA
De Ie, 1 When even, we have that Rus S __ for all m, while the inequality Ruv S т+カ was only proved for the m 2. From this figure, both these bounds are true in all considered cases. However, while the bound on Ruv (which is theoretically true for all m) only tight when m = 2 and seems to be loose in several trials with larger values of m. the bound R (which only showed for the case m = 2) appears be tight in all reported scenarios. Thus, conjecture that the geometric convergence rate at equation (16) may still hold for m greater than 2. We leave the case m 2 for the future work.
log(1/e)
15.0
16
14
32.5
14
12
log (t)
12
10
7.5
RSOT theo.
RSBP-2 theo.
5.0
RSBP-3 theo.
RSOT empi.
RSBP-2 empl.
RSBP-3- empl.
10
RSOT
RSBP-2
RSBP.3
25
Kilas
Kunegt.
20
10
10
(a) RSOT
(b) RSBP m
(c) RSBP
(b), (c) ROBUST- IBP algorithms. Top The log value of the number of itcrations computed in our theorems (dashed lines with circle marker) and the true number of iterations at which the algorithms achieve e-approximations (solid lines with square marker). Bottom: The ratio between values of the upper figures. Both the number of iterations (on the left) and plotted the log domain, while the ratios (on the right) are computed with the original values.
Figure 3: Runtime demonstration for (a)

---

Experiments
In this section, we provide numerical evidences regarding our presented complexities for ROBUST- SEMIŠINKHORN and ROBUST-IBU algorithms. We put additional experiments (including the runtime comparison of ROT/RSOT on synthetic and real datasets, as well some applications for the studied robust formulations) in Appendix F. All the optimal solutions for convex problems in the following part are computed using the evxpy library [1]. All the experiments are conducted on a server with 32 GB RAM, 8 cores Intel(R) Core(TM) 17-9700K and 1 GeForce RTX 2080 GPU.
Runtime Demonstration: For each algorithm, investigate the number of iterations required to obtain an e-approximation. We compare the theoretical values in Theorems and 2 with the empirical values computed by running the corresponding algorithms obtain the first iterations from where the algorithm always returns an e-approximation.
For RSOT, let 100, r 1, generate entries of C uniformly from the interval [1, 50] and draw entries a, 6 uniformly from [0.1, 1] then normalizing them to form probability vectors. 1j is set according to Theorem For each varying from 5 10 to 5 x 10-5, we calculate the number of theoretical and empirical iterations described above, as well as their ratio. This experiment is run 10 times and we report their mean and standard deviation values in Figure 3 (a). We also carry out similar experiment on MNIST data, which is reported in the Appendix F.
For RSBP, run the ROBUSTIBP algorithm with the following sctup: 1m
10; 1:07=1:p11 Pi....... Pm probability vectors; {C+ is a set of n X n matrices whose entries drawn uniformly in [0.01, 0.1]; five chosen values of vary from 10-3 to 10 (which are relatively small compared to the optimal cost (X*) is about 0.019 = 0.001 when m 2 and is about 0.021 + 0.001 when m 3); and the corresponding values of are set according to Theorem 2. The results are shown in Figure 3 (b) and (c). Note that the complexity for the case m 2 3 is still an open problem, and we use the formula in Theorem 2 to compute the (hypothetical) theoretical number of iterations in that case.
1:
WW...... Wm]] are randomly-initializ
In all three experiments, it is noticeable that the ratios between theoretical and empirical values decrease as + 0, indicating the our complexity bounds get tighter.
Conclusion
In the paper, we study the complexity of Sinkhorn-base algorithms for approximately solving robust versions of optimal transport between two discrete probability measures with at most n components, and show that they return e-approximated solutions in Ö(n² //) time. Low-rank approximation technique is also analysed to further reduce the dependency of these complexities on n, resulting in Ö(rr² + nrr/e) complexities. Finally, we investigate a robust barycenter problem between probability measures and develop the IBP-based algorithm for solving it. When m 2, the complexity of the ROBUSTIBP algorithm proved to be at the order of ( while in the case m 2 3 we believe that a novel proof technique needs to be developed to establish the geometric convergence of the updates from the algorithm. We leave this direction for the future work.
10

---

References
[1] A. Agrawal, R. Verschueren, S. Diamond, and S. Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60 60, 2018.
[2] Altschuler, Bach, A. Rudi, and J. Niles-Weed. Weed. Massively scalable Sinkhorn distances via the Nyström method. In NeurIPS, 2019.
[3] Altschuler, J. Weed, and Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In NeurlPS, 2017.
[4] M. Arjovsky, S. Chintala, and L.. Bottou. Wasserstein generative adversarial networks. In ICMI., 2017.
[5] Y. Balaji, R. Chellappa, and S. Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. In NeurlPS, 2020.
[6] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, A7111:1111- A1138, 2015.
[7] Blanchet, A. Jambulapati, C. Kent, and A. Sidford. Towards optimal running times for optimal transport. ArXiv Preprint: 1810.07717, 2018.
[8] L. Chen, Z. Gan, Y. Cheng, L. Li, L. Carin, and J. Liu. Graph optimal transport for cross-domain alignment. JCML, 2020.
[9] L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(114)22563 2018
[10] N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3959)11853-1855 2017.
[11] I. Csiszár. Information-tyee measures of difference of probability distributions and indirect observation. Studia Sci. Math. Hungar, 2:299-318, 1967.
[12] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In NeurlPS, 2013.
[13] Dvurechensky, Gasnikov, and A. Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's 's algorithm. In ICML, 2018.
[14] A. Figalli. The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-560, 2010.
[15] A. Genevay, G. Peyre, and M. Cuturi. Learning generative models with Sinkhorn divergences. AISTATS, 2018.
[16] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville. Improved training of Wasserstein GANs. In NeurIPS, 2017.
[17] N. Ho, X. Nguyen, M. Yurochkin, H. Bui, V. Huynh, and D. Phung. Multilevel clustering via Wasserstein means. In ICML, 2017.
[18] D. Kingma and J. Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
[19] A. Kroshnin, N. Tupitsa, D. Dvinskikh, P. Dvurechensky, A. Gasnikov, and C. Uribe. On the complexity of approximating Wasserstein barycenters. In JCML, 2019.
[20] N. Lahn, D. Mulchandani, and S. Raghvendra. graph theoretic additive approximation of optimal transport. In NewriPS, 2019.
[21] T. Lin, Ho, X. Chen, M. Cuturi, and M. Jordan. rixpo-support Wasserstein barycenters: Computational hardness and fast algorithm. In NeurIPS, 2020.

---

[22] T. Lin, N. Ho, and M. Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In ICML, 2019.
[23] D. Mukherjee, A. Guha, M. Solomon, Sun, and M. Yurochkin. Outlier-robust optimal transport. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pages 7850-7860. PMLR. 18 24 Jul 2021.
[24] X. Nguyen. Convergence of latent mixing measures in finite and infinite mixture models. Annals of Statistics, 4(1):370-400, 2013.
[25] M. Perrot, N. Courty, R. Flamary, and A. Habrard. Mapping estimation for discrete optimal transport. In NeurIPS, 2016.
[26] G. Peyré and M. Cuturi. Computational optimal transport. Foundations and Trends@ Machine Learning, 1 (5--6)355-661 2019.
[27] K. Pham, K. Le, N. Ho, T. Pham, and H. Bui. On unbalanced optimal transport: An analysis of sinkhorn algorithm. In ICML, 2020.
[28] J. Rabin, S. Ferradans, and N. Papadakis. Adaptive color transfer with relaxed optimal transport. In 2014 IEEE International Conference on Image Processing (ICIP), pages 4852-4856. IEEE, 2014.
[29] A. Rolet, M. Cuturi, and G. Peyré. Fast dictionary learning with a smoothed Wasserstein loss. 2016.
In AISTATS, pages
[30] G. Schiebinger, J. Shu, M. Tabaka, B. Cleary, Subramanian, Solomon, S. Liu, S. Lin, P. Berube, I.. Lee, et al. Reconstruction of developmental landscapes by optimal-transport analysis of single-cell gene expression sheds light on cellular reprogramming. BioRxiv, page 191056, 2017.
[31] T. Séjouméé, F. Vialard, and G. Peyré. The unbalanced Gromov Wasserstein distance: Conic formulation and relaxation. arXiv preprint arXiv:2009.0425 04266, 2020.
[32] J. Solomon, F. Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas. Convolutional Wasserstein distances: Efficient optimal transportation geometric domains. In SIGGRAPH, 2015.
[33] S. Srivastava, V. Cevher, Q. Dinh, and D. Dunson. WASP: Scalable Bayes via barycenters of subset posteriors. In AISTATS, pages 912-920, 2015.
[34] Srivastava, C. Li, and D. Dunson. Scalable Bayes via barycenter Wasserstein space. Journal of Machine Learning Research, 19(8):1335, 2018.
[35] V. Titouan, I. Redko, R. Flamary, and N. Courty. Co-optimal transport. NeurlPS, 2020.
[36] I. Tolstikhin, O. Bousquet, S. Gelly, and B. Schölkopf. Wasserstein auto-encoders. In ICLR,
2018.
[37] H. Xu, D. Luo, and L. Carin. Scalable Gromov- iassestennsnnttein learning for graph partitioning and matching. In NeurlPS, 2019.
[38] P. C. Álvarez Esteban, E. D. Barrio, J. A. Cuesta-Albertos, and C. Matran. Trimmed comparison of distributions. Journal of the American Statistical Association, 103:697-700 2008
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work has no negative societal impacts.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report the mean, the standard deviation and the number of trials in our main experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [No] We only use public datasets.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're
using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information offensive content? [No] We do not such information.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No]
13


Reviews:
[{"review_id": "yJySXhXg1xe", "reviewer": "Reviewer_yb1x", "summary": "This paper presents the complexity analysis of two problems: robust optimal transport and robust barycenter problem. For both these problems, the paper analyzes a sinkhorn-based algorithm and obtains a complexity of O(n^2 / \\epsilon). Finally, the authors show some numerical analysis to support the theoretical claims.\n\n", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern is that the paper is very similar to the analysis in  [26] where the convergence proof of unbalanced Sinkhorn is provided. This paper analyses a modification of unbalanced optimal transport in which the variable X is forced to be a transportation plan. This modification also translates to a normalization step in the sinkhorn algorithm. In Figure 1, the authors show why this modification is important. The convergence proof of Theorem 1, however, looks very similar to [26]. There is a slight difference due to the normalization step. \n\nThe authors also analyze the robust barycenter problem, which is an extension of the robust OT problem. This convergence analysis, which looks like an extension of the robust OT analysis, provides a O(n^2/\\epsilon) solution for the barycenter problem.\n\nI am not a theory person, so I did not go over the proofs in detail. However, from a quick look, I am concerned about the similarity of the problem/analysis compared to [26] and not sure of the novelty. I would like if the authors help clarify this.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The similarity with [26] seem to be the biggest concern for me.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "IkI8fHumTi", "reviewer": "Reviewer_uvAE", "summary": "This paper proposes two robust formulation of the optimal transport problem (namely RSOT and ROT) based on the relaxation of the marginal constraints of the optimal transport plan using Kullback-Leibler divergence. The authors introduces algorithms based on Sinkhorn iterations in order to solve RSOT and ROT problems, and analyse their computational complexities. The fixed-support Wasserstein barycenter problem is also tackled using the proposed RSOT as a divergence, and the algorithm shows a better complexity than the one based on entropy regularised OT. Numerical experiments are also provided to support the theoretical results and applied task are performed (color transfer and generative modeling).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality : The proposed robust optimal transport is very similar the unbalanced optimal transport. Moreover the algorithms proposed are largely inspired from existing method (UOT [9]). For example, the ROT algorithm follows the generalised Sinkhorn algorithm with a extra step that is the normalisation of the transport plan.\n\nQuality : The complexity analysis of the proposed algorithms (solving ROT, RSOT and RobustIBP) are theoretically strong, as they in particular provide an $\\varepsilon$-approximation of the solutions. Additionally, a low-rank approximation improves the complexity of the algorithm solving ROT. On the other hand, ROT is presented as a robust method but there are no theoretical or experimental results that truly support this claim (except for Figure 1, see Limitations).\n\nClarity : This paper is well written and the different problems are clearly stated.\n\nSignificance : In my opinion, the improvements of the methods proposed in the article compared to the UOT is not clear. Indeed, both problem have the same complexity. Moreover, the methods are compared with UOT in terms of complexity analysis but not in terms of behaviour: how does an optimal transport plan move the mass under ROT or RSOT? Does the normalising step significantly impact the results? What are the key differences?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations :\n- When dealing with color transfer applications, it is known that OT behaves poorly. To be fair, the authors should compare their results with more adapted OT-liked method, such as [Adaptive Color Transfer With Relaxed Optimal Transport, Julien Rabin, Sira Ferradans, Nicolas Papadakis] for example.\n- The complexity of the RobustIBP algorithm, that aims at computing the Wasserstein barycenter, is only available when computing the barycenter of two measures.\n\nQuestions : \n- I find the toy example in Figure 1 interesting in order to differentiate the proposed method and UOT. However, is the poor solutions coming from UOT are simply due to the choice of the regularisation parameter? Since UOT does not impose any constraints on the optimal plan being a probability measure, I imagine that larger parameters for the KL penalties on the marginals should give better results.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GUVQhkLu8fO", "reviewer": "Reviewer_aBfM", "summary": "The paper proposes the Robust Optimal Transport(ROT), Robust Semi-constrained Optimal Transport (RSOT), Robust Unconstrained Optimal Transport (RUOT) and Robust Semi-constrained Barycenter Problem (RSBP). In these problems, the equality constraints in the original OT problem is replaced by the soft KL divergence. Then the Sinkhorn-like algorithms are proposed to solve the corresponding dual problems. Finally, the detailed convergence analysis is given. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- It seems unfair to compare the proposed methods with the Sinkhorn algorithm, since the solution of the proposed method is even not in $\\Pi(P,Q)$. Also, there is no comparison between the proposed methods and Sinkhorn, in terms of both accuracy and efficiency.\n- By further relaxing the equality constraints, the problem should be simpler and easier to compute. But what's the purpose of such a relaxing? \n- In Fig. 2, what's the meaning of different colors? Is there any way to enlarge the difference of different lines like plotting them in the log-domain? Currently they just mix together.\n- Similar relaxation about OT has been proposed in [Fast Unbalanced Optimal Transport on a Tree] and its cited works. Please see the first formula of this paper.\n- No comparison between the proposed methods and other similar ones, like the standard OT and UOT. Without such comparisons, it is hard to see the merits of the proposed ones.\n- Many missing references about partial optimal transport: \n  - Alessio Figalli.  The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533–560, 2010\n  - Luis A Caffarelli and Robert J McCann. Free boundaries in optimal transport and monge-ampere obstacle problems. Annals of mathematics, pages 673–730, 2010.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "BiNbSfR_TAD", "reviewer": "Reviewer_7VwK", "summary": "The present paper is on optimal transport problems. The authors derived computational complexity results for robust optimal transport and robust barycenter in the special case with two marginals.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\nThe theoretical results derived in this work is new. The methods and proof techniques are essentially the same as [1].\n\nQuality: \nThe theoretical results and the associated proof seem to be solid. The result on barycenter is restricted to the setting with only two marginals.\nThough this is a pure theoretical work, the authors provided numerical examples to support their claims, which is a plus.\n\nClarity:\nThe paper is well-written. The presentation is well-structured and clear. \n\nSignificance:\nThe theoretical results in this paper are elegant, but I feel the contribution is incremental in view of [1]. Also, the barycenter result is a bit restricted.\n\n[1] K. Pham et al, On unbalanced optimal transport: an analysis of Sinkhorn algorithm", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations have been discussed. It is stated that there is not societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "03ZHTX4tN0N", "reviewer": "Reviewer_8LKP", "summary": "This paper focuses on the computational complexity of robust optimal transport between discrete probability measures. The authors propose two Sinkhorn-based algorithms with near-optimal complexity to approximate the optimal cost. Furthermore, for solving a robust barycenter problem, they propose an algorithm based on iterative Bregman projections (IBP) and show that it also has near-optimal complexity between two discrete probability distributions.\nExperiments verify the presented complexities for the above algorithms. The main limitations and future work directions are also discussed.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- For robust optimal transport and its corresponding barycenter problem, the authors develop Sinkhorn-based and IBP-based algorithms for solving them, and provide a comprehensive study of the computational complexity. The proposed algorithms can achieve near-optimal complexity, which outperform state-of-the-art competitors.\n\n- The organization of this paper is satisfactory, and the motivation is very clear.\n\n- The experiments are implemented on various synthetic and real datasets; the experimental settings and results are well explained.\n\n- Some existing work considers the problem of robust optimal transport with similar  idea, e.g., [1] and [2]. More discussion is needed to compare them with the proposed method.\n\n[1] Mukherjee, Debarghya, et al. \"Outlier-Robust Optimal Transport.\" arXiv preprint arXiv:2012.07363 (2020).\n\n[2] Jawanpuria, Pratik, N. T. V. Dev, and Bamdev Mishra. \"Efficient robust optimal transport: formulations and algorithms.\" arXiv preprint arXiv:2010.11852 (2020).\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- The complexity of ROBUSTIBP algorithm is near-optimal only when the number of discrete probability distributions, $m$, equals 2. This case is quite special and restrictive.\n\n- In the experimental part, the approximation error of proposed algorithms is not discussed. Also, there is a lack of comparison with other methods.\n\n- Optimal transport methods usually suffer from the curse-of-dimensionality.\nFor example, the convergence rate of the Wasserstein distance may be arbitrarily slow as the number of dimension increases.\nI am wondering how does the size of the dimension affect the performance of the proposed method? Some discussion and empirical results are needed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the reviewers and the AC agree that the submission makes a worthwhile theoretical contribution in designing and analyzing new algorithms for RSOT and RIBP. 

The reviewers highlight the following main concerns:
- The algorithm appears to be a simple normalized version of the Sinkhorn algorithm for UOT. 
- the technical novelty appears to be somewhat incremental, as the necessary techniques already appear in the OT and UOT literature.
In the rebuttal, the authors explain that the obstacle to overcome in the analysis of the new algorithms. They also stress the fact that no simple, very efficient algorithms were known for RSOT and RIBP before this work. The AC believes that the simplicity of the algorithm and the lack of other algorithms besides standard convex solvers makes this paper close to the acceptance threshold for NeurIPS.

A number of issues spotted by the reviewers and the AC could be addressed by the authors in a final version:
- the discussion of the significance and novelty of the convergence analysis of RSOT should appear in the paper,
- the experimental section would ideally include more varied experiments. In particular, larger examples would be nice to test the scalability of the method, even if it may not be possible to run cvxpy on them to obtain the ground-truth optimum.
Decision: Accept (Poster)