On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
Authors: Minhui Huang
Shiqian Ma
Lifeng Lai
Venue: ICLR 2022 Submitted (2022)
Keywords: Equitable and Optimal Transport
Fairness
Saddle Point Problem
Projected Alternating Maximization
Block Coordinate Descent
Acceleration
Rounding

Abstract: This paper studies the equitable and optimal transport (EOT) problem, which has many applications such as fair division problems and optimal transport with multiple agents etc. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon \etal suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating maximization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that can numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems. 

Under review as a conference paper at ICLR 2022
ON THE CONVERGENCE OF PROJECTED ALTERNATING MAXIMIZATION FOR EQUITABLE AND OPTIMAL TRANSPORT
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies the equitable and optimal transport (EOT) problem, which has many applications such fair division problems and optimal transport with mul- tiple agents etc. In the discrete distributions case, the EOT problem can be for- mulated linear program (LP). Since this LP is prohibitively large for general LP solvers, Scetbon et al. [Scetbon et al.) (202T) suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating max- imization algorithm (PAM) to solve the dual of the entropy regularized EOT. In this paper, we provide the first convergence analysis of PAM. A novel rounding procedure is proposed to help construct the primal solution for the original EOT problem. We also propose a variant of PAM by incorporating the extrapolation technique that numerically improve the performance of PAM. Results in this paper may shed lights on block coordinate (gradient) descent methods for general optimization problems.
INTRODUCTION
Optimal transport (OT) is classical problem that recently finds many emerging applications in machine learning and artificial intelligence, including generative models/Arjovsky al. (2017). rep- resentation learning Ozair et al. (2019), reinforcement learning Bellemare et al. (2017) and word embeddings Alvarez-Melis et al. 2019) etc. More recently, Scetbon et al. SSeetbon et al. 2021 pro- posed equitable and optimal transport (EOT) problem that targets to fairly distribute the workload of OT when there are multiple agents. In this problem formulation, there are multiple agents work- ing together to move mass from measures μ and each agent has its unique cost function. A very important issue that needs to be considered here is the fairness, which aims at finding transportation plans such that the workloads among all the agents by minimizing the largest transportation cost among all agents, which leads to a convex-concave saddle point problem. The EOT problem has wide applications economics and machine learning, such as fair division or the cake-cutting problem Moulin (2003); Brandt et al. (2016), multi-type re- source allocation Mackin & Xia (2155, internet minimal transportation time and sequential optimal transport Scetbon et al. (2021).
equal to each other. This
be achieved
We now describe the EOT problem formally. Given two discrete probability measures f4n Ex a,or, and Vn n bedg, the EOT studies the problem of transporting mass from μ to by N agents. Here, {21, 22,, of each measure and a = [a), a2,,.., an] E A", weights for each measure, where A denotes the probability simplex in R". Moreover, through- out this paper, we assume vector c (z. y), k E [N] (I....,N} N) and its cost matrix as C. where C+,, c* c,,,,, Uj). Moreover, define the following coupling decomposition set
C Rd and {21, U2. yn C _Rd are the support points b2..b,.... bn]" E A are corresponding
O. For each agent k. we denote its unique cost function as
(I= x/ = a,
N n.b
= π = (I [ r
Σ nk = b. = 20,4, [m]

---

Under review as a conference paper at ICLR 2022
where r(T) c(T) = 1 are the row sum and column sum of matrix x respectively. Mathe- matically, the EOT problem can be formulated as
min max (T*, C")). FET
(1)
ISRSN
When N = 1, (1) reduces to the standard OT problem. Note that ① minimizes the point-wise maximum of finite collection of functions. It is easy to see that equivalent to the following constrained problem:
N
min max A(T = A x AEA
(2)
The following proposition shows an important property of EOT: at the optimum of the minimax EOT formulation (2). the transportation costs of the agents are equal each other.
Proposition 1 (Scetbon et al. 2021 Proposition 1) Assume that all cost matrices C+, KE [N] have the same sign. Let T E 11,, be the optimal solution of (2). holds that
(( (m")','') C*) = (0=","''
V
(3)
Note that Proposition| I requires all cost matrices to have the same sign. When the cost matrices all non-negative, (2) solves the transportation problem with multiple agents. When the cost matrices
all non-positive, the cost matrices are interpreted as the utility functions and ( solves the fair division problem Moulin (2003).
The discrete OT is linear programming (LP) problem (in fact, assignment problem) with complexity of On log n1) Tarjan (197).. Due to this cubic dependence on the dimension n, it is challenging solve large-scale OT in practice. A widely adopted compromise is to add an entropy regularizer to the OT problem Cuturi (2013). The resulting problem is strongly convex and smooth, and its dual problem can be efficiently solved by the celebrated Sinkhorn's 's algorithm [Sinkhorn & Knopp (1977); Cuturi (201)). This strategy is now widely used in the OT community due to its computational advantages as well as improved sample complexity (eenvay al. (2019). Similar ideas were also used for computing the Wasserstein barycenter Benamou et al. (2015), projection robust Wasserstein distance Paty & Cuturi (2019); Lin et al. (020);(Huan) et al. (021a), projection
robust Wasserstein barycenter Huang et al. (2021b). Motivated by these previous works, Scetbon er al. [Scetbon et al. (202I) proposed to add an entropy regularizer to (2), and designed a projected alternating maximization algorithm (PAM) to solve its dual problem. However, the convergence of PAM has not been studied. Scetbon et al. [Seethon et al. (202T) also proposed an accelerated projected gradient ascent algorithm (APGA) for solving different form of the dual problem of the entropy regularized EOT. Since the objective function of this new dual form has Lipschitz continuous gradient, APGA essentially the Nesterov's accelerated gradient method and thus its convergence rate is known. However, numerical experiments conducted in Scetbon et al. (202T) indicate that APGA performs worse than PAM. We will discuss the reasons in details later.
Our Contributions. There are mainly three issues with the PAM and APGA algorithms in Scetbon ct al. (202T), and we will address all of them in this paper. Our results may shed lights on designing new block coordinate descent algorithms. Our main contributions are given below.
(i) The PAM algorithm in Scetbon et al. (202T) only returns the dual variables. How to find the primal solution of (2) i.e., the optimal transport plans was not discussed in /Scetbon et al. (2021). In this paper, we propose a novel rounding procedure to find the primal solution. Our rounding procedure is different from the one widely used in the literature Altschuler et al. (2017).
(ii) We provide the first convergence analysis of the PAM algorithm, and analyze its iteration com- plexity for finding an e-optimal solution to the EOT problem (2). In particular, show that it takes at most ONN'² -² arithmetic operations to find an e-optimal solution to (2). This matches the rate of the Sinkhorn's 's algorithm for computing the Wasserstein distance Dvurechensky al. (018)..
(iii) We propose a variant of PAM that incorporates the extrapolation technique as used in Nesterov's accelerated gradient method. We name this variant PAM with Extrapolation (PAME). The iter- ation complexity of PAME is also analyzed. Though we are not able to prove a better complexity over PAM at this moment, we find that PAME performs much better than PAM numerically.
2

---

Under review as a conference paper at ICLR 2022
Notation. For vectors and b with the same dimension, a./b denotes their entry-wise division. We denote Coo = max; ||C* lec. Throughout this paper, we assume vector > 0, and we denote all equal to one. We use (x) to denote the indicator function of set X, i.e., xx(x)) = 0 if x E X, and
2 == min, log(b,). We use 1, to denote the n-dimensional vector whose entries
[x(x) otherwise. We denote e - c(2 n² =f+++1, ,g", XQ). For integer N >> 0, we denote [N] = (1....,N), N). We also denote π (S. A) = [=* 2)]RE(N]-
2 PROJECTED ALTERNATING MAXIMIZATION ALGORITHM
The PAM algorithm proposed in Scethon et al. 2021) aims to solve the entropy regularized FOT problem, which is given by
N min max e (T, A) = Σ ( T NEAR
(4)
k=
where 17 0 is regularization parameter, plj (Tt A) = X (T - (T*",, and the entropy function H is defined as (=) Ei, T (log क..j - 1). The entropy regularization was first introduced into the OT problem by Cuturi (013) and is now widely used the OT community. By adding an entropy regularizer, the primal problem becomes strongly convex and the dual problem unconstrained and is suitable for alternating maximization. This leads to the Sinkhorn's 's algo- rithm which has low per-iteration complexity and thus is scalable. The PAM algorithm proposed by Scetbon et al. (202T) used the same idea for the EOT problem. Note that 4 is a strongly-convex- concave minimax problem whose constraint sets convex and bounded, and thus the Sion's 's mini- max theorem Sion 1958) guarantees that
min max (T, max min (T, A)- AEA xEll
(5)
EEIN YEAN
Now we consider the dual problem of min TEny 0.
(T) First, we add a redundant constraint
Endd "ig and consider the dual of
min
ey (). A).
(6)
* Eeay st.
The reason for adding this redundant constraint is guarantee that the dual objective function is Lipschitz smooth. is easy to verify that the dual problem of (6) is given by
max
min 1.9 Evny =t.= k=1 xE(RUX))
Σ Aa ch) (
a a--
Σ
x
+g"
bbcc
b
where ff and are the dual variables and H(T)) Ex H (x*)) the following solution:
It is noted that problem 7 admits
(f
* (f.g,1))
Ak [N],
(8)
Ex (f.
where
(f1 +1.9" Ax
(f. g. = exp
exp
Vk v [N].
(9)
"
By plugging
8 into
we obtain the following dual problem of
6
max
(f.a) + (g. b) 17 log
Elk A)1h 7.
(10)
FER", DER
Plugging 10 into 5). we know that the entropy regularized EOT problem 4 is equavalent to a
pure maximization problem:
max fER%, gER", AEAN
F(f.gA)) = (f.a) a) + (). - 1l Σ 1c (f,g, -7.
(II)
3

---

Under review as a conference paper at ICLR 2022
Function (ff.g g. A) is smooth concave function with three block variables (f.g. A). We use 9"" ) to denote an optimal solution of (TT), and we denote F = " The PAM algorithm proposed in Scetbon et al. (202T) essentially a block coordinate descent (BCD) algo- rithm for solving scheme:
More specifically the PAM updates the three block variables by the following
fl+ argmax (ffmaxF(f.g. F(f. g.',..))
(12a)
ge+1 argmax F(f .9. X')
(12b)
X ProjaN v (X' + + "9" gg ,²))
(12c)
Each iteration of PAM consists of two exact maximization steps followed by one projected gradi-
ent step. Importantly, the two exact maximization problems [2a 12bb have numerous optimal solutions, and we choose to use the following ones:
f++ S +1
a -k=1 ( (h(S, ,2,,,)((,)))))
(13)
b
ge 9" + 1logg
(14)
EN
k=1 (fftt) ((ffttigg,.n ,g))))))
c
Furthermore, the optimiality conditions ([2a) 12b) imply that
r (EN (+ (((tt),))))))))) ( gg,g2)11l 0, b
e En (1(tt1 , ,2,,
Vt.
(15)
(fttt
However, we need to point out that the PAM (22 only returns the dual variables (f', g", x²). One can compute the primal variable using (8) but not necessarily a feasible solution. That is, computed from (8) does not satisfy æ W How to obtain an optimal primal solution from the dual variables was not discussed in Scetbon et al. (2021). For the OT problem. i.c., .N-. = 1, rounding procedure for returning feasible primal solution has been proposed in Altschuler et al. (017). However, this rounding procedure cannot be applied to the EOT problem directly. In the next section, we propose new rounding procedure for returning primal solution based on the dual solution "',))",'") This new rounding procedure involves a dedicated way to compute the margins.
2.1 THE ROUNDING PROCEDURE AND THE MARGINS
Given a E A b E A", and æ = {sr* JE[N] satisfying r(Ex T*) a. we construct vectors at, b E RRRKKE [N] from the procedure
(a 6 ) = Margins(T. (T, a, b).
(16)
The details of this procedure given below. First, we set a r(mr*), which immediately implies Σx= a = a. We then construct 6t such that the following properties hold (these properties are required in convergence analysis later):
6 0: (ii)
N
k= b = b;
(ii) En D of
b Yk E [N]:
(iv) For any fixed j E [n]], the quantities by [c(T*))] have the same sign for all k: E [N]. That is,
for any and k. we have
11/ [c(s))))s)) (1/) Ic(
(e(m<)))))) })bb) 0,
(17)
4

---

Under review as a conference paper at ICLR 2022
which provides the following identity that is useful in convergence analysis later:
Σ b
c(
Σ
|0(
Σ bb - [c()>)),))
j=1
(18)
N
]
N
=
Σ j=1
bj
The procedure on constructing (b*) (E")EE satisfying these four properties provided in Appendix
After (at, bt) [ are constructed from 16 with
XT-1, adopt the rounding
procedure proposed in Altschuler et al. (0177) output a primal feasible solution (#* )EENN. The
rounding procedure is described In Algorithm
With this new procedure for rounding and computing the margins a², 6t, we now formally describe [
our PAM algorithm in Algorithm!] are met:
Note that the algorithm is terminated when the following criteria
|| b/] </((6(6co0 m2)),
(19a)
|| x x- $ (1(((1)22))
(19b)
P( """,""""~"-1
,x-11 S e/6,
(19c)
where F(f.g, is the suboptimality defined as: F(f, A) F(f F(f.g,)).
Algorithm Projected Alternating Maximization Algorithm
1: Input: Cost matrices (C* IisgEN, vectors a A with b > 0, accuracy fo 90 [].... 1]", Xo [I/N, ..., 1/N] E EAN. E 1=
2: Choose parameters as
3(log(n2N) (n + 1) Coo ) = n/22.
min
(20)
3: while (19) is not met do
4:
Compute ft by 13
5:
Compute g a++ by
6:
Compute +++ by
12c
7: 1+t+1
8: end while
9: Assume stopping condition (99 is satisfied at the 7'-th iteration. Compute (at b b*)kE(N) Margins(x gT xT--1), -""-1,"--1),, (a.a,b) b) in Section 2.1
10: Output: (ft 2) where ** = R=* .g"
a bt), Ak E [N], â = XT-11
Algorithm Round n. a,
1: Input: E RRax a E R2, E RD_
2: X Diag (x) with x; r()). 1
3: n' = XTT
4: Y Diag (v) with yj
b, A
J
5: n" = =
6: err, a - r(T"), erry = b -- c(TT)
7: Output: n" + errgerr? /llertall1.
5

---

The output pair of Under review as a conference paper at ICLR 2022
2.2 CONNECTIONS WITH BCD AND BCGD METHODS
We now discsuss the connections between PAM and the block coordinate descent (BCD) method and the block coordinate gradient descent (BCGD) method. For the ease of presentation, we now assume that we are dealing with the following general convex optimization problem with m block variables:
(x T2 Em))
(21)
where X; C Rdd, and J is convex and differentiable. The BCD method for solving follows:
21 iterates as
++1
argmin [x]++
222
1+1
++1 -11 a441
(22)
=;Ex,
and it assumes that these subproblems are easy to solve. The BCGD method for solving 21 iterates as follows:
+++ argmin vV [z]+t 22 iE
x1)
||=,
2 12 (23)
2T
23 in the sense that some block variables are updated by exactly solving a maximization problem (the f and steps), and some other block variables updated by taking gradient step (the step). Though this hybrid idea has been studied in the literature Hong et al. (207) Xu & (203). their convergence analysis requires the blocks corresponding exact minimization to be strongly convex. However, in our problem (1I). the negative of the objective function is merely convex. Hence we need to develop new convergence proof' analyze the convergence of PAM (Algorithm[I) How to extend to more general settings is a very interesting topic
where > 0 is the step size. The PAM 12) is hybrid of BCD
22 and BCGD
our convergence results of PAM (Algorithm I for future study.
CONVERGENCE ANALYSIS OF PAM
In this section, analyze the iteration complexity of Algorithm T for obtaining an e-optimal solu- tion to the original EOT problem ( The e-optimal solution to is defined as follows.
Definition 2 (see, e.g., Nemirovski (2005)) We call (Øt Å) the EOT problem (2) if the following inequality holds:
H. x A e-optimal solution to
max E( A) min E(T, 2) S
XEAN
TENLY
Note that the left hand side of the inequality is the duality gap of (2).
3.1
MAIN RESULT
We now present our main theorem, which gives the iteration complexity of PAM such that (55) is satisfied, and as a result of Lemma 15| an e-optimal solution to the original EOT problem is obtained.
Theorem 3 Define e' e/(6co mT), and set T as
36
648c2
28
T = 5
+
0
(c 22)
(24)
1) Toc'
me
7700
where "/u min
(2e mu) 962 constant and we know "o O(c=²))
Algorithm is an c-optimal solution of the EOT problem 2
Proof. See Appendix
B
Remark 4 Though our complexity result matches the rate of the Sinkhorn's algorithm in terms of the dependence on e, we argue that EOT is a more difficult problem than the entropic regularized OT, and thus results are promising. First, EOT is saddle-point problem while entropic regularized

---

Under review as a conference paper at ICLR 2022
OT is minimization problem. Second, the extra variable in EOT requires gradient projection step in the PAM algoritlu, which introduces significant difficulty to the analysis of the convergence behavior. While for Sinkhorn's 's algorithu it is much easier analyze, because the dual is uncon- strained. Third, since there are multiple agents in EOT, it is more difficult to design the rounding procedure obtain the primal solution. We also note that the dependence Coo in result and in the result of Sinkhorn's 's algorithm Dvurechensky et al. (2018) are both co
4 PROJECTED ALTERNATING MAXIMIZATION WITH EXTRAPOLATION
In this section, we discuss how to accelerate the PAM algorithm (Algorithm) It can be shown that the gradient of F in (II) is Lipschitz continuous Therefore, Scetbon al. Scetbon al. (2021)
proposed to adopt Nesterov's accelerated gradient method Nesterov] (2004) to solve [11b. Their
algorithm, named APGA (Accelerated Projected Gradient Ascent algorithm), iterates as follows:
(v, w. 2) t (f--1 .9" .g 1+1 .9 1
-(
(25a)
(f' + (1, + I (F.)))((u
(25b)
(A9) 4 Proja V.F(
(25c)
where L is the Lipschitz constant of V.. Note that APGA treats the problem (II) as a generic con- vex and smooth problem, and does not take advantage of the special structures of (TT). In particular, and 9 are updated using gradient ascent steps. This is in contrast to PAM in which f and g are obtained by exact maximizations, which is expected to improve the function value of F more sig- nificantly. the following, we will design an accelerated algorithm that utilizes this property. Our method is called PAME (PAM with Extrapolation) and it incorporates the extrapolation technique to the gradient step for updating X, and f and g are still updated using exact maximizations. We not able to prove a better complexity for PAME. Our iteration complexity
note that currently result in Theorem 22 is in the same order as that of PAM, but numerically we have observed great improvement of PAME over PAM. It is an interesting future topic to study other accelerations to PAM that can provably achieve improved complexity.
A typical iteration of our PAME algorithm is given below:
f = fr + log
(26a)
EE (h
1+ = g¹ + +n
(26b)
c (1E&&t(ft ,g¹, x2)
n+ ProjaN
(2 + (1 0)(2' -)(x--x-1) -x-1),
(26c)
*+ ProjAN (1 F gg , 1))
(26d)
Here 0 E (0. 1) is given parameter for the extrapolation step. We that steps 26a 26b) are the
same as - 14) and they are solutions to the exact maximizations (1a)) Steps (26c) (26c) give extrapolation
the gradient step for X, similar to Nesterov's accelerated gradient method. Note that PAME (26) solves the dual catropy-regularizer EOT problem (T.. We use the same rounding procedure in Section 2. to generate primal solution the original EOT problem (I.
The complete PAME algorithm is described in Algorithm 3 Note that the algorithm is terminated
when the following criteria are met:
[e - b11 S <e/(6(6c> 111),
(27a)
||--11 - X'2212 nc/(60(1 0)c22)
(27b)
q/ (12(2
(27c)
F(f'gg--1, ( $ e/6.
(27d)
II Lemma 8 we proved that F is Lipschitz continuous. The Lipschitz continuity of V, and F,F be proved similarly.
7

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Projected Alternating Maximization with Extrapolation Algorithm
Cost matrices (C* IggEN, accuracy c, E (0.1). 2: Initialization: f = 9
Input:
22 [1/N, ..... 1/N]T E EAN
3: Choose parameters as
3(log(n2 1) 1),000 T= "
min
(28)
20
4:
while (27) is not met do
5:
Compute f++1 by (26a)
6:
Compute g" ++1 by 26b
7:
Compute y +1 by 26ch
8: Compute x+1 by (6d
9:
t- 1+
10:
end while
11: Assume the stop condition 27 is satisfied the 7--th iteration. Compute (a bt) )
Margins(T -T--- x"-1),a, b) in Section 2.1
Output: (f, X) where ** Round( (nt (fT. .9" )) at b*), Ak E [V], Å == XT-1.
10
100
AAM
10"1
10
EOT Erro
10
EOT
10
1
10
1.5
2.5
40
60
80
Execution Time
Execution Time
10"
HMM
NMM
10
10
EOT Error
EOT Error
1
10
10:10
10
0.5
1.5
2
2.5
0
0.5
1.5
Execution Time
Execution Time
Figure 1: Computational time comparison between PAM, PAME and APGA algorithms on Gaussian
distributions. Upper Left: N = 10, n 100, = 0.1, Upper Right: N = 10, 500, r7 = 0.1, Bottom Left: 10, n = 100, r7 = 0.5, Bottom Right: N = 5, n 100, 7 = 0.1.
4.1 CONVERGENCE ANALYSIS OF PAME ALGORITHM
In this section, we analyze the iteration complexity of PAME (Algorithm for obtaining an e- optimal solution to the original EOT problem (I] The proof for PAME is different from that of PAM, and here need to analyze the behavior of the following Hamiltonian, inspired by Jin et al. Jin et al. (2018).
F(f.g.At)
27 1 1
(29)
8

---

Under review as a conference paper at ICLR 2022
Theorem Define è' e/(60x mi), and set T be
48
(3600(1 8)² + 882) 2
48
T
+
=
(30)
Tic'
mE?
TYY
where "1 min (2
n0)at (7- 2 49c2 j and we know "n O(c33). At least of the
2(28 82)
iterations in Algorithm after rounding, is an e-saddle point of the EOT problem 2
Proof. See Appendix
Remark 6 We are not able analytically prove that PAME has improved complexity bound at this moment yet. The APGA proposed in Sceebonn et al. (2027) in fact has better complexity than PAM and PAME. However, as demonstrated in Sceebon al. (2021) and in our numerical experiments (Sections 5 and D). APGA performs worse than PAM. We believe the reason is that APGA takes gradient step for the variables f and g, while PAM exactly minimizes the subproblems corresponding to these two variables. It is the exact minimization step that led to the improvement. Developing a provably better algorithm definitely important and interesting, and we will work on it in the future.
5 NUMERICAL EXPERIMENTS
We compare the performance of PAME with PAM and APGA (25 Scetbon et al. (2021) on a syn- thetic dataset: the Gaussian distributions. We also conduct numerical comparison on another syn- thetic dataset: the fragmented hypercube dataset, and the results will be given in the Appendix.
Gaussian Distribution:
Consider case when two sets of discrete support {ai)iem) (ustse independently sampled from Gaussian distributions
N 1
( 10 10 )) and N
((2).(-12
2 (2))((
1 -0.2
))
(31)
-
0.2
1
respectively. The base cost matrix Chhose computed by Ci ||æ; y Assume we have N agents. The cost matrix of each agent can be obtained by adding Gaussian noise sampled from N (0, 10) to each element of the base cost. For instance, for the k-th agent with cost matrix C* we have Ct2, Cha + N/ (0, 10)].
We then set
[1/n, 1/n] for all experiments. For algorithms, we set 5y
and
set = 0.1 for the PAME algorithm. We consider the EOT error as a measure of optimality. The EOT error iteration is defined by
Error [[(= .offfggg.. x),x)-ET
(32)
where ( is the approximated optimal value of EOT 2 obtained by running the PAM algorithm for 20000 iterations. Figures plptts the EOT error against the execution time for Gaussian distributions. We run each algorithm for 2000 iterations for different parameter settings. In all cases, the PAME and PAM perform significantly better than APGA, and PAME also shows significant improvement over PAM.
CONCLUSION
In this paper, we provided the first convergence analysis of the PAM algorithm for solving the EOT problem. Specifically, we have shown that takes at most O iterations for the PAM algorithm to find an e-saddle point. We proposed PAME algorithm which incorporates the extrapolation technique to PAM. The PAME shows significant numerical improvement over PAM. Results in this paper might shed lights on designing BCD type algorithms.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Jason Altschuler, Jonathan Wiles-Weed and Philippe Rigollet. Near-linear time approximation algo- rithms for optimal transport via Sinkhorn iteration. In Advances neural information processing systems, pp. 1964-1974, 2017.
David Alvarez-Melis, Stefanie Jegelka, and Tommi Jaakkola. Towards optimal transport with global invariances. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1870-18799 PMLR, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Marc G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. In International Conference Machine Learning, pp. 449 458, 2017.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iterative Bregman projections for regularized transportation problems. SIAM Journal on Scientific Com- puting, 37())A1111-A1133) 2015.
Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pp. 2292-2300, 2013.
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's 's algorithm. Interna- tional Conference on Machine Learning, pp. 1367-1376. PMLR, 2018.
Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1574-1583, 2019.
M. Hong, X. Wang, M. Razaviyayn, and Z.-Q. Luo. Iteration complexity analysis of block coordi- nate descent method. Mathematical Programming Series A, 163(1):85-114 2017.
Minhui Huang, Shiqian Ma, and Lifeng Lai. A Riemannian block coordinate descent method for computing the projection robust Wasserstein distance. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 4446-4455, PMLR, 2021a.
Minhui Huang, Shiqian Ma, and Lifeng Lai. Projection robust Wasserstein barycenters. In Proceed- ings of the 38th International Conference on Machine Learning, volume 139, pp. 4465- PMLR, 2021b.
Chi Jin, Pranceth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.
Tianyi Lin, Chenyou Fan, Nhat Ho, Marco Cuturi, and Michael Jordan. Projection robust Wasser- stein distance and Riemannian optimization. In NewrIPS, volume 33, 2020.
Erika Mackin and Lirong Xia. Allocating indivisible items in categorized domains. arXiv preprint 1504vv1504.000 05932, 2015.
Hervé Moulin. Fair division and collective welfare. MIT press, 2003.
A. Nemirovski. Prox-method with rate of convergence O(1/L) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15()):29--251, 2005.
Y. E. Nesterov. Introductory lectures on convex optimization: A basic course. Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004. ISBN 1-4020-7553-7.
10

---

Under review as a conference paper at ICLR 2022
Sherjil Ozair, Corey Lynch, Yoshua Bengio, Aaron Van den Oord, Sergey Levine, and Pierre Ser- manet. Wasserstein dependency measure for representation learning. Advances in Neural Information Processing Systems, pp. 15604-15614, 2019.
François-Pierre Paty and Marco Cuturi. Subspace robust Wasserstein distances. In International Conference on Machine Learning, pp. 5072-5081, 2019.
Meyer Scetbon, Laurent Meunier, Jamal Atif, and Marco Cuturi. Equitable and optimal transport with multiple agents. In International Conference on Artificial Intelligence and Statistics, pp- 2035-2043, PMLR, 2021.
R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math., 21:343-344 -344, 1967.
Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4):402-405: 1967.
Maurice Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):111-776, 1958.
Robert Tarjan. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathematical Programmingg 1877),169-177, 1997.
Y. Xu and W. Yin. A block coordinate descent method for regularized multi-convex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on Imaging Sciences, 6358)11758-178, 2013.

---

Under review as a conference paper at ICLR 2022
A CONSTRUCTING be IN THE MARGINS PROCEDURE (16
In the section, we show how to construct (b*)kE()) in the Margins procedure (16) such that the four properties in Section 2.1 are satisfied.
First, we set
c T ( -0--1,==-1)
= c "- x--1)) (f
N
It is easy to verify that properties (ii)-(iv) are satisfied. But is possible that (i) is violated. We now describe procedure to iteratively update 6² to achieve (i) while keeping (ii)-(iv) satisfied. (i) does not hold, then there exist &t and j. such that 1/ 0, which further implies by [c(=>)]] 0. Since
ΣΦ |1 and El((T>>> = Σ T
||a 12.
3
there must exist an j' such that by; - [ > O, which further implies by. > 0. Moreover, since Eg b, there must also exists an k'' such that b5 O. We then update the following quantities:
bg. - b/. 0
by by 0
by byt O,
where
== min (10 1 18y. - [c(x>))>>11
Note that this update maintains that (iv)- are satisfied. From our discussion above, it is guaranteed that Therefore, b/: is improved, i.c., getting closer to O, if not equal. Repeating this procedure leads to bº, & E [N] such that (i) is also satisfied.
B PROOF OF THEOREM 16
B. TECHNICAL PREPARATIONS
We first give the partial gradients of F.
[yF(f,g,A) a; Ens exp (fs + - 1101
r |(=_ x I $5
Σe (J,,,
(33a)
[gF( =by- exp(([ 99 >x2%t)/nn)
= Σ * (
11 A]]Ili
(33b)
[AF(J.9 Eig C2 + - - C*)
(33c)
Σx (I( x))l1
Since 13 and 14
renormalize the row sum and column sum of Σ₁ <h [f g, A) to be a and b, we
immediately have
N Eis g1 ,,,,, = 1,
Σ ( X.10 1,
(34)
which, combined with 8 yields
*((++) X²= N*),
(((tt g ,1) (h( ghhh X²), Vl.
(35)
The following lemma gives bound for Algorithm
2 (see Altschuler et al. (017
12

---

Under review as a conference paper at ICLR 2022
Lemma (Rounding Error) Let a. E R7 with Ei= ai EE= by q. E R4*", and
Round( TT, a, b). The following inequality holds:
f T|| - 2(11((x) - alli + [|((T)) - b).
Proof. The proof is slight modification from (Altschuler et al. 2017 Lemma 7). Note that Lines
2 in Algorithm eagorithm@renon renormalize the row sum and column sum that are larger than the corresponding a, and by. It is easy verify that #, x". erra and erty nonnegative with ||erralli ||erralli
|| and
r(+) = r(="((=))))))))r + r rerrrerryy / /lerral))) = r(>") + erra a,
and likewise c(+) b. Denote A ||||| ||="|| Since remove from of when (T(T)) 2 a,, and from a column when cy( 2 bj. we have
n Σ (r)(
1 (c((t')-b))
A
ai)+
j=1
Firstly, a simple calculation shows
az)+ [|]r(=) - a/l1 + ||>||1 - g)
Secondly, the fact that the vector c(TT is entrywise larger than c(x') leads to
(()(+') b,)+ S [e((T) b,)+ $ ||((T)) - b111.
Therefore we conclude
|| - T|| - A |errgerr, 11//|lerrall A A + 24 + q |||||
a/l1 + 2|(((x)) b/] s 2 2[(((T)) all1 |<(x)) b1l1 $ ||](m))
The following lemma shows that F is Lipschitz continuous.
Lemma 8 For any f.g E IR" and A X2 E AN the following inequality holds
|| A²) v VxF(f.9, S 2 >2112//
(36)
which immediately implies
2 221
F(J,g,A)) F(Jg, (V
X3)
||>
(37)
2n
Proof. The proof essentially follows Scetbon et al. of the Hessian of F(S.g, with respect to À
2021 It easy verify that the (q. k) entry
82 F a,
mp (A)o 2(O
where 11 k=q 1 iff k 9 and 0 otherwise, for all {1,..., N) and p
ft + - C
(A)
Σ
Pexp
"
N
J ( 9و
Ox
exp
A=1
13

---

Under review as a conference paper at ICLR 2022
Let E R satisfying ||la| f. 9. we obtain
1, and by denoting F the Hessian of F with respect to À for fixed
N
v
F mpp
Σ
kk2
k=1
h=1
2
N
N
Ji+ 93 AR.
Ji + 95 - da Aa
(2ORR1(a))
Σ
Σ
exp
(2,))
nju2
i.
is
2
27
Ji + 9j - -A
Σ
2
Σ
exp
$0.
tp22
"
A=1
where the last three incqualities come from Cauchy Schwartz inequality. Moreover we have
N
2
Ek
c20 97
V Fu
Σ
Σ
0
2
nu2
Tp
k=
which completes the proof.
The next lemma gives bound for g.
Lemma 9 Let (f+, g." 2²) be the sequence generated by Algorithm 7
For any t 2 0, it holds that
max Jj min gî S Coo 776,
(38a)
max 0j min 93 S Coo TJc.
(38b)
Proof. We prove 38a first. When t= 0, 38a holds because of the initialization gb. When / 2 1, from we have
Σ
10 1o0
1ct1 2 Ne No-
(39)
A=
1=1
where the second inequality is due to0 A < 1. Combining 39 and 34 we
Li/n . Ne-eo1/n e0 1'/m/ < Eest/n
e03/n
Σ
2 ctt//
efi/n by 1
which leads to Moreover, note that
max of co - log(N(1
(40)
X /0///n therefore # E
-xt 1ct//0 /n < 1. This fact leads to:
e0//n (1, f/ > Σ 2g//n
2 -t//0/ etln
1 bbg
A=1
which gives
min 9 n 17 log (ololo((NN11
(41)
Combining 40 with (41) yields (3aa.. The bound for g" 38b) can be obtained similarly, by noting
that π² II o.h.
We omit the details for brevity.
Lemma 10 Let { g", 2f be generated by PAM (Algorithm Dg. The following equality holds.
N
Σ
( 1 2 x g. A. 29 = ||c* :bl1, .t. Vt.
14

---

Under review as a conference paper at ICLR 2022
Proof. By
35
we have
Σ (fttt) * (ft+)) . g", X1111
N
to -1gtt c + Xi )/
(ftt)
N')k by/c// - 11 = E Edlbs//c - 11 -Ilec ||c--bl1
B.2 KEY LEMMAS
In this subsection, we provide few useful lemmas that will lead to our main theorem on the iteration
complexity of PAM (Algorithm DT. These lemmas yield the following results: the function F is
monotonically increasing (Lemmas ITp. the suboptimality the dual problem can be upper bounded
(Lemma 12 14 and the PAM returns an e-optimal solution under conditions (55) (Lemmal 15). In
Theorem 16 we will show that these conditions can indeed be satisfied.
Lemma 11 [Increase of F] Let (''.'',' be generated by PAM (Algorithm 7 inequalities hold:
The following
F( ,f ; F(J", ,', ,',,1))) X9) 20
(42a)
F( ggt11177 -F(ftt) ,g','7 (²) 2 " l|e² - -b12
(42b)
2
F(J 1 g , F(g(t) g gh+1, x²) 2 || -xx+-x111/(22))) 2/112/(2n)
(42c)
Proof.
First, 42aa is a direct consequence of (2ap.
Next, we prove (42b). We have
F(ft+1 gg
4+ 2²) - F(ftt1,0) ,6 x²)
(g b) - 17 log
15* (fet1 | , >1)1aa + 7og
Σ Eistuutt, of, x311a)
= -g 41 -
- b) = by log(bs/c)) x/((lllc = 2 " bl?
1=1
where K(x:: denotes the KL divergence of x and y. the second equality is due to 34 the third equality is due to (14). and the last inequality follows the Pinsker's inequality.
Finally, we prove 42c From the optimality condition of (2c know that there exists
h(A+1)= E A (1++))
(43)
such that
VXF(E++ , M 1 (1 -x9- O.
(44)
From 37 we have
2
F( ge +1 x+1)- F(rtt1 ggtttigtt1,. (21 2 [VA(((t , 44, 1-511-9) -29)
|사 2f112
2n
( x²) + 1,
2
_
|| - 111
2n
(1 - x9) -
2 2n
| X112
= x912/(21))
15

---

Under review as a conference paper at ICLR 2022
where the first equality is due 44 the second inequality is due 43 and the last equality is due to the definition in (20).
Before we bound the suboptimality gap, we need the following lemma.
Lemma 12 Let {fr g", }²} be generated by PAM (Algorithm 7 For any x E AN, the following inequality holds:
X VXF( , x²) 3 || 1112/11 + c20 ||c b/11
(45)
Proof. The optimality condition of [2c) is given by:
(A x - (2 x²) VxF( , t2 2,,, MEEA"
(46)
which implies that
( - X, - F( s+1 -g
(1 X+1 - xt) S - -
- X |221| 12l2 20201114 - ->11l2/n,
(47)
where the last inequality is due to the fact that the diameter of AN is bounded by v2 S 2. Moreover, have
(A* A, VXP(F g gh . VxF(ftt) ,',a1))
N
Σ (A1 Aa) (7T ptt gtth * (f--1 gg 2²),
(48)
N
<
| ggthg ,1) (f .g' |l
k
S cool c| bll1:
where the equality is due to (3cc) and the last inequality is due to Lemma 10 Finally, we have
(X A, - g (²))
(X - --++111____111 -VXF(t +t (++))() + (x+11-1 - ~,, -VF((ft)) ,9 41, (,)) +
(49)
(X A, VxF((tt ggt ,,-) - F ,g,,')
< - - [( //++''')l + 2r2211 || 1122/11 + coolle' bbli,
where the first inequality is due to 47 and (48). From 33c we have |V ,gtt / >a)12
<
Coo. which, combined with 449 and the fact that 77 S Coo. yields the desired result.
The suboptimality of 11 is defined as: F(f.g,)) = "If",g",X' - F(f.g. A). Note that F( A) 2 0, G. A
Lemma 13 Let (f', gg,, Xt) be generated by PAM (Algorithm) 7.. The following inequality holds:
P( . < (26x0 - - - b11 + 3 | - -2112/nn
Proof. Denote wt = (max, of min, 93)/2, (max, 93 miny 92)/2. From 35 we get
(1, [ b) = Σ
Σ j=1
bj = 0,
i=1
which further implies
(g) g",c² b) ((g) u'1) (g" - 1i) c² -b)
(50)
< (1lg* u''ll/ + 01 u 1 1lo0) |c - b1/ s (cso m7) |lee - 6112,
16

---

Under review as a conference paper at ICLR 2022
where the last inequality is due Lemma 9 Now set X in (45 and obtain
- 30 X 12/// ||c* -b11-
(51)
Since F( is concave function, we have
F(f", 9- x) = g'. ,.) (VF(f* (V))
(f(t) ,''"'))))))
which, combining with 33 yields
F(s++1 , X² F( :9" X²) - F( ,²)
S (1+)) - r"rr The (let1, (0)) a) + +(g' gg, -)
+ - -f g (()))
- (2cx mu)lcc b|l1 + 3 ||| 12/1
where the last inequality follows from
15
35
and 5TT.
The next lemma shows that the suboptimality gap F(f,
(ff.g. 9, A) can be bounded by O(1/t).
Lemma 14 Let (f', ""'''', (²) be generated by PAM (Algorithm A The following inequality holds:
4/(rn0)
F(f+t1 g'+11 x
1+1+
where = -min (20x0-10) Sc
is a constant.
Proof. Combining 42bb and 42c
we have
F(f++1, , g1 x - E(ftt1 g',0' 2
17 ||c bll + +2 29112/(2n)
(52)
2
Therefore, we have
:9 ++ (1411-- - ,²,22)
S " c' bl1 2 || X2 ((n)
S 70 (((26o0 mullie - b1l1)² + -3e2 ||| -x112/n)²
"
(53)
2
S 7
70 ((2600 - mm]lect - b|l, + 3c 11 114t1~1'12/1> 21112/1)2
? yo p( ,g", ,
S
where the last inequality is from Lemma 13 Dividing both sides of (53 by F(fttl get1111-1 .1 F(gtt) g²) we have
F(f+t (1ft+lgg,, ,g,,'))
70 F(ft+), ggthl xx+1)
F(f++1, , X++1)
F(r++1.g'. 9(,
(54)
F(ftt1.g) X9)
70 2 F(f', g',
4 Yo.
where the second inequality is due to (53) and the last inequality is from (42a). Summing 55) from to leads to
n(t + 1)
F( A+11) 2 P( 20)
70.
which implies the desired result.
The next lemma gives sufficient conditions for the PAM algorithm to return an e-optimal solution to the original EOT problem 2
17

---

Under review as a conference paper at ICLR 2022
Lemma 15 Assume PAM terminates at the T -itteration, i.e.
| bll1 S <6/(6(0600 - -1))
(55a)
|X" - -- 1--111 1 nc((1)))))
(55b)
F - s e/6.
(55c)
x² Then the output (#, X) of PAM (Algorithm) i.e., * Round ( (s", T- ,-= -)) a², br), Ak
[N]. \ XT-1, is an c-optimal solution of the original FOT problem
Proof. According to Definition it is sufficient to show that the output ( 2) E II the following two inequalities:
a,b x N satisfies
max l E(E, A) - E( 2) S c
(56a)
NEAN [( ((T,A))
2
min E(TT, 2) - 2
(56b)
TElL
We prove (5aa) first. For ease of presentation, we denote ग T(f". .9 10--1A--11 π rf""g" A Note that ** = RRonddI* a², ",,"), [N]. We also denote
N
A(T) = arginax ((TT,)) = Σ A
Ce Otly
(57)
YEAN
k=1
Note that the term on the left hand side of (6aa can be rewritten as
é (#t, A(+)) - ( 2
= (E(#, A(+)) - E((T, {(T))) + (Ie( (I((F, - (H) -[((T" .x) (TT')))
(58)
(T)
(IT)
+ (((TT" x²) H1 [e(#t, À) -
- H)))) + (e(#t, 2) ((tt))),t 21)
(1I1)
(IV)
We now provide upper bounds for these four terms. Denote
k
argmaxx(** Ck)), k-= argmax("**, C*).
(59)
KE(N)
ke[N]
Since 1 and (2) are equivalent, have the following for the term (I):
(1) Σ (#* ct) [i( O+ = (##* ) Okk))
5(# chty - (7th ,,, S || - + S Coo Σ | - *
(60)
$2000 E(Ir(E*)- - a + ||(((*) b+111) = 20 || - bl11,
where the first inequality follows from the definition of K in (5)) the fourth inequality is from Lemma 7 and the last equality follows from (15) and (17)
For the term (II), recall that H (T) =
Eniis m. (log tt, 1) and #k
exp ("1' - 1c due to 35 and define T-11 = max, of T-1 + min, of 7-1
We
2
18

---

Under review as a conference paper at ICLR 2022
have
P + T-1 XT ----00 Ck
(1I) Σ ((F) Ct)) +1 Σ
*
-1 F
11
k,tsJ
-
- (w)(tt , + Σ
Fi (17 + +
T-1 - 11) =
(X(#) i, V.F(F 99 ---1 xx-11) + (12 () + (0) 1- , Eijjt Ti. F
(T X V.F(F" --11, (11 + (f", a) + (0) (0--1, 111 - -log
|| 112) -17 F
(X A, V.F(Ft 9 x + (0" 2- b) + F(ft ---,, F
S (x 2, VAF(ST 9 T-1 xT + (g -- -0-11-1--1-- -1 b)
Scx 1c --1 1 - b/]1 + 3 A - x- 12/1 + (5 f-1 =²= 1111 1, x- - b)
Sco 1 - b/11 + 32 |^ - x- 12/ n + 11g T - -=-'-11 1110111"" -- bl1
(3 /2 m1/2)) 2-16 + 3c 1^ - X 1111/
(61)
where the third equality uses (35) (33c) and
15 the second inequality follows from Lemma 12 by setting À = X and & = 7 - I, and the last incquality uses Lemma
For the term (III), we have
+9
T-1 T-
\/
Ck
-1 -1)
(III) S
*k Σ ( +1 Σ
F
n
(62)
(gT-1, (0T-1,cT-11
--- -b) + F(f " T-1 . - F*1
/2 m/ m1/2)llcT-1 b111 + F(fT .g T- 1111 1-1) F*1.
where the last inequality follows from Lemma 9 Finally, for the term (IV), we have
(IV) Σ (5 #t. #h, SA. S Σ ||# ||
(63)
<20 Σ (1) - 1 + [|((at) b*111) = 20 06c -bb1,
where the first inequality uses
A < 1, the second inequality uses Lemma and 17 Plugging
60
63)
into 588. and using 55
obtain (56ap.
Now we prove (56b). For ease of presentation, we denote
π (A) == argmin E(T, A). rell
(64)
We also denote 6= of- E. e (T*) and th = Round (A)*, (ao)),,,, aa, (t),, where
(at, 8 ) = Margins (i (A)
as defined in (6). From 18 we know that
Σ||c (((A))))) - 1+ = ((((()))))) - k
Σ b6 - R
= 11 - b1/ = 116 cT (65)
where the second equality is due to (①}) E 11W, and thus ctEx (T)))) = b. and the fact that
Σx 8 = i due to Property (ii) of the Margins procedure in Section
2.1 By the Sinkhorn's theorem
19

---

Under review as a conference paper at ICLR 2022
Sinkhorn 1967), ft is the unique optimal solution of min b A). Therefore
(it(" - (+) S Σ ATT C n
(66)
&
Now, note that the left hand side of (56b) be arranged into three parts:
e(tt, 2) (2),
Σ Aat cch) -
-
E da (7th (t,,, Imuttt,.C))
I C - E (a .chy
Σ
(V)
(VT)
(67)
Σ (TT , - Σ ((((((())))C0
(VII)
We now upper bound these three terms. First note that the term (V) the same as the term (IV) and
thus has the same upper bound in 663 Since 0 < ((x) s log(n N) + 1, from (66) we have that
(VI) Σ Sn ( Oty - Σ (n < H H
(68)
where the last step uses the definition of 1f in 20 For the term (VII), we have
(VII)= Sulat Budt"",CC*) E) c*) S Σ 1|
(69)
220, ((Ir((+()))) - 1+1l |[(((((())) - B²111) = 2c 2coolle 1loc bll..
where the second inequality follows from Lemma the second equality uses (65 and the fact that ({)))))))) = a due to the property of the Margins procedure in (16).
Finally, plugging (63) (note (V)=(IV)). (68) and 66 into (67). and using (5aa and noting < 0, we obtain (56b). This completes the proof.
B.3 MAIN RESULT
Theorem 16 Define e' = </(60oo - T)), and set T as
5 Toc
36
648c2
28
=0
(c2
(70)
n7
1700
where to is defined in Lemma 14 and we know 7o 20 c-optimal solution of the EOT problem (2)
The output pair of Algorithm is an
Proof. According to Lemmal 15 we only need to show that (55) holds after iterations as defined in 70 To guarantee (55a) and (55b), follow the ideas of Dvurechensky al. Dvurechensky al.
2018 and construct switching process. We first reduce F from F(5o, ", (,))) constant by
running t steps. In this process, Lemma 14 i4liniiates
4
4 S 1+
(71)
17088
F (ff.fff.f.. (o)
Secondly, starting from 8, we continue running the algorithm, and assume that there are la iterations in which (55a) fails. By (42b) we have
72s
t2 < 1 +
20

---

Under review as a conference paper at ICLR 2022
Therefore, know that the total iteration number that (55a) fails is upper bounded by
72s
4
Ti = 1 + 1o 2
1708
FF :9.00
iterations. By choosing s = <6/(6/70)) we know that
2 + ny Tae"
24
2 + Tue'
F9 2
T S
Toe'
6
2 + By TaT
S 2 +
otherwise.
TaE'
(f
Tue
Therefore, we have Ti S 2 + fails can be bounded by
Similarly, starting from s, the number of iterations that (55b)
13 S 1 + 648sc
m/22
where we apply (42b). is upper bounded by
By choosing s c, we know that the total iteration number that 55b fails
648c ne
4
4
T- = 4 ts s 2
+
mow
770
iterations. Finally, by letting
e in
we know that
F(F
g To- x
S e/6
after
24
T3 = 1+
iterations. From 42a
we know that after T3 iterations, we have
P( - "( " < P( , ,--,, S e/6,
i.e., (55c) holds. Combining the above discussions, we know that after T = + + T3 + iterations, there must exist least one iteration such that (55) holds, and thus the output of PAM an e-optimal solution to the original EOT problem
C PROOF OF THEOREM 22
The following simple fact is useful for our analysis later.
| X1|12 P (X* + - 0) - x(-11) Projaw (29) l/2 S (1 - 00110 - -011 1|
(72)
where the equality follows from the definition of + in 266 and the inequality is due to the non-expansiveness of the projection operator.
The following lemma shows that the Hamiltonian E'f', X3, X is monotonically increasing when updating À in Algorithm
Lemma [Sufficient increase in A] Let (f". .'''''""' X' be generated by PAME (Algorithm
3 The
following inequality holds:
20 02
E(f+1 42 X+1 (2) E((t+1 g x
| -
X-
|
- +2 lg.
2T
(73)
Note that since e (0, 1), the right hand side of (73 is always nonnegative.
Proof. From the optimality condition of (26c) we know that, there exists h(1++1) E MAAN (1+11) such that
VxF(f++1 r y
(2++1 ,(t) h(x++1)= =
(74)
21

---

Under review as a conference paper at ICLR 2022
By the convexity of the indicator function MA (A*+1), we have
(g/ - x h((xt)(()))))))))))))))))))))) S 0, (A'- - (d'=x(t)h(x*+1)) - O.
(75)
Moreover, we have the following inequality:
| - x11 || y/ + y - x112
- 11y - 1112 -
,// - X²) + +|| -gt
- 113
(76)
S <1 01- 1| - 11 - 1/+ )²) + || 11
where the inequality from 72p
We then have the following inequality:
F(ftt), . _g X²) - F(f++1 1
s (F(stt) 1 .y + + (VxF( g t1 , - (1))
(F( gg ,
,y + + (VxF()tt) ((tt] g ) 1,, t11 - 12 11111
(ViF( p+1 .9 g y ),,'' - ) + c 11 y1111/((2)
S (ViP(( 1+1 " H+ .y ) h(x**),, ),,²' - x 11 ) + 2 |1 - yy 1 122(22)2n
= (141 - 1+ /=,1,'' ,'' -
- x + 47
11 112
1 -N41 y , 1x---" -2 + + - 2 + 47
| -2
T
1 (1 n/th ,g - x -
3
- - y²+1112
45
(77)
where the first inequality is from the concavity of F with respect to and (37). the second inequality is due to 75). the second equality is due to 74). Combining (6) and (77) leads to
E(ftt1 1+ X .x*) = F(f*t
1+ )
27 || - 1211
1
F(ft+) ,g 1+, ,²' + - (2 x++1__0
- y +1, y +1 X²3 + 47
| - 112
(1 012 | - X 1| (22+1
y1 . - -²-- - 1
| - 11-1112
2T
2r
F(ftt] _gth1 (²) 1
20- 0
1| - x11 +
|X x-1 $12 || 2212
27
2T
E(ftt1 .9 +1, X 11 20- 02
2T 1|
x
1
+
|| - 112
47
which completes the proof.
Now we define the following function É, and later we will prove that EC "g", Xe, 1111 can be upper bounded by O(1/t).
XP) = = ,-) - E(f, (2)).
The next lemma is useful for obtaining the upper bound for E(S g' N X-1). Moreover, it is noted that E(f,g, (²) 2 0.Vf.g, X², and E(f.g,,, = F(f. A), V..g
Lemma 18 Let { "g'. .yy, At3 be generated by PAME (Algorithm 3). For any X E AN, the follow- ing inequality holds
. x)) S coollc' - -bll2 + 11 11/1ll//++ 0) 12 - x- 112/n VxF(f .g',
(78)
Proof. From the optimality condition of (26d), we have the following inequality:
(A-X0 x+1 : (x - ,(+
VXF( gtth l )t1)) 2 0. A.EAN
(79)
22

---

Under review as a conference paper at ICLR 2022
The left hand side of 78 can be rearranged to three terms.
(A X², V VxF(f .' X²)
(X - X, VXF( g () (X X, VAF(J , ".thyt ( VxF(S++) , (())
(II)
+ (X' - A. V2F(f gtt ,2) VxF(f ,(,'))..
(80)
We now bound these three terms one by one. To bound the term (I), we first note that from (33c)
and
15 we have
|VxF(ftt) ggttt l2 I Coo S /
(81)
where the second inequality is due to the definition of 28 Now we can bound the term (I) as follows:
(1) (1'- - - gf )o) + (2' X+1
ge+ g6+ VXF( ,gt 1/t1))
+ +1 - -x,- -,-- -V g 1 ,9 ))
< | X 2 | F ++1 g xt)1|2 + 2ee
- - 1|| - 111
"
+ 1 | - 2112 || - 1 112
<3e² | x*+111/// 4e || y ll/n
(82)
where the first inequality uses Lemma and 79). the second inequality uses (8T and the facts that |X - y²+1 S 2 and | - X112 2
For the term (II), Lemma yields:
(IT) $2 VxF(
t(t VxF(ftt) , (x)l2 S 20 11 - 1112 //
(83)
For the term (III), it can be bounded as:
(III) Σ (Ah An) (1tt 1+ -²) - ** (s(tt, , "6,,)),.7
(84)
| , -
- - (stt, of X X -0 S coolle' - blI
where the last inequality is due Lemma 10 triangle inequality, we obtain
Plugging
82
84
into 80 and applying the
(A X VXF( 'g', Xa) S coolle- b/1 + 7 |1
g lla/ + 5c Il 1112//1
which immediately implies (78) by noting (72)
Lemma 19 Let ''''8'') be generated by PAME (Algorithm 3
The following inequality
holds:
B , Xt, x-1) < -w) 76 -oo-t--y'+10 -/ c |> x- 1
Proof.
Since F(J.g, A) is a concave function, we have
F(J, ""","",7"" X²) < F(r+t) (V "0,
which implies that
R( /g X²) S <(g' - 9" g-, -
-V ,g','))
5(c>0 - nu)lle' 6/1 + / - b1|1 + 702 || - y 1 (85)
+ +5(1 0) || x 12/n
23

---

Under review as a conference paper at ICLR 2022
where in the first inequality we have used (35). and the second inequality follows from (50) and setting À = X in 78). From (85) we immediately get
E(ftt1 ,g' X x = F(fet1, ,g, - || - X
2T
S 2 - X 11// + (2c.0 - m7)]le' - -bl1 7 ||
11- - 1
2 ||* x 112/ + (2 mmillle - bll1 + 7c || - y 112/ -) 1| X 12/n
where the second inequality is due to || 1 I This completes the proof.
The following lemma bounds E(ft+1, g X+11 X by O(1/t).
Lemma 20 Let (f",""
o X be generated by PAME (Algorithm
3). The following inequality holds:
6/(m))
B(f++l, , 11=1,
Vt 2 0,
L 1+1+ ++1+6/(mm) F0
where we assume X- = 20, and
1 (2cz0 - m1)2² (7- 20) 49
2(20 02)
n1 min
(86)
is a constant.
Proof. Combining 42bb and Lemma 17 we have
E(f+t g x++1, )² - E
f+ '', 1-11)
= (EE(t+1 _g 11_,,,11,00 , E(stt1 .9 X x x² + (F(st11 , ,11- - P .f)
2 |c' - bll + 20 02
|| 11 +
1
|| - -
2
2r
47
which implies that
B( g++l ,x+1, x²) - E(s++1 ",",,,,,',,'""""" )
7 Illd' bl? - -(20- - 02) ) ف || X-1 11
2 ||| - y 112
2
2n
< 1
2 71 ((2000 - m1 ||e² b1l)² + ((7 -5)) || x-11122/13 + (7 1| - [²]
< 1
n [20c0 171) ||e - b|1 + +77 - 20) ||* - x22'1le/v + 7 | --- (121111/1)
6
< 7 n E E(f ,
6
(87)
where the last inequality applies Lemma 19
We then divide both sides of (87 by
Elptt1 gh+1, Xtt1,19 E(t+l, g Xt, x-1), and we obtain
1 E(ftt), ([ft+),gtt,, Xt11 E(ft+l ,g X X
n
E(f+h g ,.X,,'
6 E(f++1 gft 1011,10
(88)
n
+ 7
E(f+t1 g X
Z Df g² N
6
71
where the second inequality holds because 87 implics that B( X
>
E(pt+1, ( gh+ A411, ,²),, and the last inequality follows from 42a). Summing 88 leads to
from to t
1 E(ftt1 gg+t1 X+11 2 E(fu 9" ,0,
1
()( + 1)
+ ( 1)
n F(F", g0 20)
%
24

---

Under review as a conference paper at ICLR 2022
which immediately leads to the desired result.
Similar to Lemma 15 the following lemma provides some sufficient conditions for the PAME algo-
rithm to return an e-optimal solution to the original EOT problem (2)
Lemma 21 Assume PAME terminates at the T-iteration, i.e.,
|c_-11 bll2 S c/(666o - 77))
(89a)
|AT-11 1T S n/c////00( - 0)
(89b)
|^_ -y'll2 S ne/ (420
(89c)
F(f g ---1,17-1 S c/6.
(89d)
Then the output Round(T" (f" _-- "---,XT-11 at bt), wk E [N] = XT-1, is an E-optimal solution of the original EOT problem 2
(t, of PAME (Algorithm
ie.. #
More specifically, we again need to show that the output of PAME (#t X) satisfies (56). The proof of (56b) is exactly the same as the
Proof. The proof essentially the same as that of Lemma 15
proof of Lemma 15
The proof of 56a only requires to develop new bound for
{( - VXP(V "-" ))T))))
(90)
that is used in 61. Other parts are again exactly the same as the ones in Lemma 15 The new bound of 90 can be obtained by applying Lemma 18 with X(+t) and
1, which yields
(Ā(T) - A VxF(T" g T-1 ' )²
(91)
I ccollle T b/[1 + 5(1 -
72 -
1l12//n
By combining (91 with (60) 63
can bound the left hand side of 56a by
{ (#t A(+)) - {(ft
< (Booo -1L) ||o b/| +5 0)2 ||---1 XT / 72 |
1121
+ |F ,g T-1 1) F*
(92)
< 12
12
2
where in the last inequality we have used all the sufficient conditions
89a
89d
Theorem 22 Define é' </(66x m)), and set T to be
T 8=8-
48
(3600(1 - 0)² + 882)
2
48
=
( (22
(93)
nea
1/E
where " is defined in (66 and know "/1 Occ²²). At least one of the iterations in Algorithm after rounding, is an e-saddle point of the EOT problem 2
Proof. According to Lemma 21 we only need to show that in 993
89 holds after T' iterations as defined
We follow the same idea as the proof of Theorem First we reduce E( g ge+1 X+1 X²) from
E(f ... 1o x-)1))= F 9. 29) to a constant by running & steps. By Lemma 20 we have
4 1
(94)
mYis
FfF "x 2o)
Secondly, starting from 8, we continue running the algorithm, and assume that there are la iteration in which (8aa) fails. By (42b) we have
72s
t2 < 1 +
25

---

Under review as a conference paper at ICLR 2022
Therefore, we know that the total iteration number that (89a) fails can be upper bounded by iterations. By choosing 8
72s
6
6
Ti f + 2o
S 2 +
11
1718
myn mn
we know that
2
12
36
2
48
if PPPS..... 2 B
S
"y
2
2
otherwise.
TI
Therefore, we have Ti S 2- THe Similarly, from Lemma 17 we know that, starting from s, the number of iterations that (89b) and 889c fail can be respectively bounded by
1 S 1 3600 c2 and 44 1514
3528 ne
s/e2 (20 - 02)
By choosing s = e, we have the total iteration numbers that 89bb and bounded by
89c)
fail can be respectively
3600 - 2)
6
S 2+ 3600(1 - 0)
6
T3 = 11 t3 2
nc(20 82)
(fF 90,0) 10)
nc(20 82)
1
and
3528c
6
6
3528c
+t, 2
$
77
mhE
7 T "0, 20)
1/c
71/1
Finally, by letting s c/6 in
94
we know that
E
9
xT
xTa 2) S c/6
(95)
after
36
T4 1
1/711E
iterations. From 95 we know that
TT .9 .T To
TT-1 S c/6,
which implies that 89d holds with T T4 by noting 42a)).
Combining the above discussions, we know that after T T, + T. T3 + T4 + iterations, there must exist at least one iteration such that the sufficient condition (89) holds, and thus the output of PAME is e-optimal solution to the original EOT problem 2
D ADDITIONAL NUMERICAL RESULTS
D.1 GAUSSIAN DISTRIBUTION
Figure 2 shows the optimal couplings obtained from the standard OT and EOT of two Gaussian distributions under three different metrics: the Euclidean cost (|) l12), the square Euclidean cost
(Il 113) and the 1.1.5 norm (II (l|-5) respectively. We set
4, 1 0.05 and generate samples independently according to (31). For the EOT problem, we consider three agents with cost matrices computed by the three metries mentioned above. Note that the entropy regularized models lead to dense transportation plan and Figure only plots the couplings with a probability larger than 10-3, We see that all the agents have the same total cost the EOT model, and expected, the cost is smaller than the other three OT costs obtained by using the same metric. The sub figures in the first row imply that if we split the workload to three parts evenly, then the three agents will each have costs 5.935/3, 2. 2.158/2 /3 and /3, which is not fair because they have different costs. But the EOT model can indeed guarantee the fairness.
We further compare the computational time for Gaussian distributions. We generate the data as in Section 5 and set the parameters as 7 = 0.5, T = 5n/c2_ We stop all the algorithms when the EOT eтror 32) is less than 10-4 Tables and 2 show the CPU time (in seconds) for different (n,, N) pairs. The reported computational time is averaged over 5 runs. In Table D the APGA algorithm fails to reach eтror of 1 in 500000 iterations when = 100 and = 500. We conclude that the APGA algorithm converges much slower than PAM and PAME algorithms. The PAME algorithm performs the best among all three algorithms.
26

---

Under review as a conference paper at ICLR 2022
Square
EOT: Agent Duclidean
EOT: Agent Square Euclidean
EOT: Agent 1.5
Figure 2: Optimal couplings of standard OT (first row) and EOT (second row). OT Square Euclidean
Cost: 5.935; OT Euclidean Cost: 2.158; OT 1.1.5 Cost: 5.030; EOT Cost: 0.906.
Table 1: CPU time (in seconds) comparison for Gaussian Distributions. Fixed = 3.
Algorithms
π2 10
20
50
100
500
PAM
0.038283
0.096039
0.177209
1.038785
1.768560
PAME APGA
0.025210
0.065552
0.091593
0.564618
1.340104
1.125673
12.364775
106.768840
D.2 NUMERICAL RESULTS ON FRAGMENTED HYPERCUBE DATASET
In this section, compare the performance of PAME with PAM and APGA 25 202T on the fragmented hypercuhe dataset.
Scethon et al.
Fragmented Hypercube: We now consider transferring mass between a uniform distribution over hypercube
1[1-1.119) and a distribution obtained by pushforward by T(x) = x 2sign(z) o (Em= em Here sign(-) is taken elementwisely. m E [d] and e, E [d] is the canonical basis of Idd In our experiments, we set d 10, m = 2 and sample two base support sets (atuse) {y)==") independently from μr, v. To obtain the cost matrix for one agent, we first add Gaussian noise sampled from N (0, 1) to the base support sets to get (upoisy )ie|n]- (xpoisy)))))) {uj noiay, Jjejo] and compute the cost using the noisy support sets. For instance, for y base + (0,1) and Ch,,
Ty defined
the k-th agent, we have (I: (oinsssh base + N (0, 1) noissy
[1 b (v) " A11..
Figures plots the EOT error versus the CPU time for Fragmented Hypercube dataset. We run PAM for 20000 iterations to get approximate optimal & and run all algorithms for 2000 iterations for different parameter settings. In all cases, the PAME and PAM perform significantly better than APGA, and PAME also shows significant improvement
PAM.
We then compare the computational time for Fragmented Hypercube dataset. We set the parameters as 7) 0.2, T 5n/c22. We stop all the algorithms when the EOT error (32) is less than 10 Tables and 4 show the CPU time (averaged over 5 runs) for different (n, N) pairs. We see that the PAME algorithm still performs the best among all three algorithms. Note that Table the APGA algorithm fails to reach an error of 10 in 500000 iterations when n = 50, n 100 and = 500.
27

---

Under review as a conference paper at ICLR 2022
Table 2: CPU time (in seconds) comparison for Gaussian Distributions. Fixed n = 50.
Algorithms
N 2
N = 3
N = 5
N 10
N 20
PAM
0.180343
0.177209
1.021598
0.719909
0.903429
PAME
0.105775
0.091593
0.560785
0.385495
0,618381
APGA
70.959300
106.
169.213121
178.637889
212.697866
100
PAN
10
FAN
EOT Errr
1
10.2
EOT
10
10
10.6
0.5
1.5
0
10
20
30
40
50
60
Execution Time
Execution Time
10
10
RAME
PAME
APOL
10
10
Eroo
Error
10
10
3
10
10
0.5
1.5
3
5
Execution Time
Execution Time
Figure 3: CPU time comparison between PAM. PAME and APGA algorithms the Fragmented
Hypercube dataset. Upper Left: 5, n 100, = 0.2, Upper Right: N = 5, n 500, 1j =
0.2, Bottom Left: N = 5, n 100, 17 0.1, Bottom Right: N 10, 100, 1 0.2.
Table 3: CPU time (in seconds) comparison for Fragmented Hypercube. Fixed N 3.
Algorithms
7 = 10
n = 20
n = 50
n = 100
n = 500
PAM
0.165165
0.101363
0.177209
1.154193
3.840804
PAME
0.112527
0.068529
0.091593
0.588553
2.007653
APGA
13.771911
22.017804
Table CPU time (in seconds) comparison for Fragmented Hypercube. Fixed n 20.
Algorithms
N = 2
N = 3
N =
N = 10
N = 20
PAM
0.003 180
0.101363
0.172696
0.253926
0.231646
PAME
0.040302
0.068529
0.110080
0.150513
0.129156
APGA
1.007166
22.017804
13,801 154
6.304324
3.749495
28


Reviews:
[{"review_id": "x8PJUPhEcdP", "reviewer": "Reviewer_M8bm", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths\n1. The authors provide a novel, useful and thorough convergence analysis for the PAM algorithm for the EOT problem. The convergence analysis is facilitated by the introduction of a novel procedure for extracting the primal solution. \n2. The paper proposes an acceleration procedure, and provides a convergence proof. The authors cannot theoretically establish a faster rate, but the numerical experiments indicate a substantial improvement. \nWeaknesses\n1. There is limited discussion of the main result. The authors do draw connections with (hybrid) BCD and BCGD methods, although this is more to explain why existing convergence analysis results cannot be applied. \n2. The experimental section is limited. It focuses on a single synthetic example. While it is certainly sufficient considering that the primary contribution of the paper is the theoretical development, more extensive experiments (and associated analysis) would strengthen the paper.\nComments:\nThe paper provides a useful and novel theoretical result for the EOT problem. The paper is very well-written and provides clear explanations. The proofs are laid out clearly with a good development of lemmas so that the overall structure can be easily followed. \nI think the paper could be improved by some further discussion of the main result. For example, there is an observation in the contributions section that the rate is the same as that of Sinkhorn’s algorithm for computing the Wasserstein distance. I would appreciate some further discussion along these lines, and also some comments regarding the c_\\infty term. \nGiven that the paper is primarily theoretical, the experimental results are sufficient, but they do not represent a systematic, thorough examination of the algorithm, focusing on a single toy example (or two, if we include the supplementary), and restricting attention to the case of uniform distributions. \nThere is not a strong tie between the theoretical results and the experiments. There is a single figure showing the EOT error with respect to execution time for different configurations of N, n, and \\eta, but it is challenging to draw too many conclusions from these figures. No attempt is made to connect the depicted results to the theoretical result. \nFigure 2 provides a comparison of the optimal couplings of OT versus EOT for different metrics. The figure could be explained more clearly. The figure provides a nice illustration of the difference between EOT and OT, although I am not convinced that such an illustration is particularly relevant to the main contribution of this paper. The conclusion  drawn from this figure is not particularly insightful – “the [EOT] cost is smaller than the other three OT costs obtained by using the same metric”. \n", "summary_of_the_paper": "The paper addresses the equitable and optimal transport (EOT) problem. One approach to this problem involves perturbation via the addition of an entropy regularization. For this formulation, researchers have proposed a projected alternating maximization algorithm (PAM). The authors of this paper provide a convergence analysis of the PAM algorithm. They also introduce a novel rounding procedure to construct the primal solution of the EOT problem. The paper also contributes a variant of PAM that leads to numerical performance improvements. Numerical experiments are provided for a synthetic dataset.", "summary_of_the_review": "I have recommended “Accept”. \nI think the theoretical contribution is novel and valuable. I followed the proofs and did not identify any concerns with the arguments. \n\nThe experimental component of the paper could be improved, and some additional discussion of the main results would be appreciated.  \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "re1gKSimmTK", "reviewer": "Reviewer_9vP7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nThis work solves a somewhat narrowly scoped problem of EOT: equitable optimal transport, together with entropy regularization, as an intriguing novel formulation. However, what is unclear is why the entropy regularization is necessary, or in what sense it helps. I agree that strong concavity helps with rate analysis, especially as it is necessary to obtain improved rates from Nesterov acceleration.\n\n However, for strongly concave problems, the best achievable rate is linear/exponential, and often invokes mirror-prox style updates. These aspects are not treated anywhere in the manuscript, so I wonder whether additional improvements are possible. Some more rigorous/granular discussion of how the main convergence results address these points is missing.\n\nOn the practical side, a few different use cases of EOT are discussed in the introduction  such as cake-cutting, multi-type resource allocation, internet minimal transportation time, etc. However, none of these are credibly addressed in the experiments, which implicitly asks the reviewer to take it on faith that EOT is applicable to these domains. This seems like a major drawback of the manuscript. The authors would do well to properly develop a single application that corroborates the theory. Put another way, why are the Gaussian distributions and the fragmented hypercube dataset representative of practical problems?\n\nIn summary, this paper develops some interesting theoretical insights about optimal transport with entropy regularization, but the innovations mostly borrow from existing results that are standard in numerical optimization, machine learning with regularization, and while the rate analysis is presented for a novel context, it does not itself employ any novel techniques or technical innovations. On top of that, the experiments are extremely simple and do not convincingly demonstrate that EOT is useful in a problem that arises in practice.\n", "summary_of_the_paper": "This paper considers the problem of approximate optimal transport, where population probability measures are replaced by discrete PMFs at collections of samples, and there is an additional \"equitable\" constraint that seeks to ``fairly\" distribute the probability mass. This admits a formulation as a linear program and may be solved efficiently through its dual. However, recovering the primal solution is nontrivial, and there exists no rate analysis to-date. This work develops a stochastic dual ascent method to solve an entropy-regularized version of this LP, where entropy regularization is introduced to ensure strong concavity, as well as avoid a notion of over-fitting. The crux of this method is an alternating block coordinate ascent algorithm, which is then combined with an extrapolation/Nesterov acceleration scheme to accelerate convergence. Numerical experiments demonstrate the practical utility of the proposed approach.\n", "summary_of_the_review": "This work is well-written but not particularly technically innovative, and is missing a thoroughly convincing use-case.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "WDXFRWt2I0M", "reviewer": "Reviewer_rMWc", "summary": "", "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": "Strengths.\n- This manuscript recognizes and provides clear references for the OT and EOT problem, and clearly positions itself with respect to previous work.\n- The paper is well written, apart from minor typos, and easy to follow.\n- The theoretical analysis seem to be correct to the best of my knowledge. However, I did not checked every line in all proofs.\n\nWeakness.\n- This was a missed chance to really motivate why EOT is an interesting problem. There are some references, but I cannot see why would one want to use EOT.  \n-The numerical experiments are toy examples, of low dimension.\n- Is a pity that there is no provable accelerated for the proposed accelerated method.\n- Contributions are rather incremental, yet still very useful.", "summary_of_the_paper": "This paper develops new algorithms, convergence rate analysis and additional tools for the equitable and optimal transport problem. Following the same history of OT, where we moved from the OT formulation, to the entropic regularization, to primal-dual analysis to explicit convergence analysis, this manuscript extends the idea of EOT and provides useful tools with provable performance for the practitioner. The contributions of this paper are on the complexity analysis, as well as new algorithms for the EOT problem.", "summary_of_the_review": "Correctness: The techniques use for proving the results are rather classical in primal-dual methods.\n\nNovelty: I gave a 2 precisely because this is a rather clear extension of the original EOT what make use of classical analysis tools to further describe the performance of the EOT algorithms. There is no new tools, but rather the use of old tools on a problem that looks very similar mathematically.\n\nEmpirical: The numeric section is very small, with toy examples of low dimensions, etc. It show it works but really does not provide any additional insights or interesting applications. \n\nI think this paper provides sufficient results for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "P-fsvg8MkIJ", "reviewer": "Reviewer_1p7i", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n(a) The paper is well-written as easy to follow.\n(b) The paper provides missing convergence guarantees for the interesting problem of EOT.\n(c) The authors further provide a novel rounding scheme plus a variant of EOT. \n\nWeaknesses:\n(a) My main concern is about the novelty and the level of contribution of the paper, which is mostly providing analysis of an existing algorithm for an existing probem. \n(b) The experimental section is quite limited and its presentation is rushed: it only considers synthetic data. I also have difficulty interpreting the results reported in Fig. 2.", "summary_of_the_paper": "The authors focus on the equitable and optimal transport (EOT) problem. In particular, EOT is a linear programming (LP) problem, which is expensive to solve in practice. The existing work suggests adding an entropy term to the objective and solving the resulting problem in the dual domain via an algorithm named Projected Alternating Maximization algorithm (PAM). However, there are two main issues with PAM: that is its convergence is unknown and it only provides a solution in the dual domain. The authors precisely address these issues by providing a convergence rate for PAM and proposing a novel method to compute a feasible primal solution from the dual solution. Furthermore, they propose a variant of PAM, i.e., PAM with Extrapolation (PAME), which appears to perform better in practice. ", "summary_of_the_review": "Overall, the paper provides some novel theoretical results for the PAM algorithm that is used for solving EOT. The paper is well-written and its theoretical results are strong. However, my main concern is the scope of the contributions. I am personally not familiar with EOT applications, but if other reviewers believe that EOT is a sufficiently interesting problem, I will be willing to vote for acceptance.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the Equitable and Optimal Transport (EOT) problem which is arises in fair division of goods and multi-resource allocation. The resulting problem is a linear program, which is polynomial-time solvable; however, the existing polynomial-time solvers either do not scale well with the dimension or are dual methods with entropic regularization for which it is unclear how to extract a primal solution. The paper shows how to extract a primal solution and also provides complexity analysis of a recently proposed projected alternating minimization method (PAM). The paper further provides a Nesterov accelerated variant of PAM. 

Overall, the paper is a meaningful contribution and was considered borderline. On one side, EOT seems like an interesting problem, the paper is well-presented, and the provided complexity results are technically sound. On the other hand, the reviewers felt that the EOT problem was not motivated enough, that the techniques for proving the results were mostly standard, and that the numerical experiments were insufficient. Even though the authors provided additional numerical experiments, I did not find the responses regarding motivation (particularly in the context of ML applications) and technical novelty convincing enough. The paper could have gone in either direction, but as there was ultimately no particularly strong support from any of the reviewers, I recommend rejection. The authors are advised to carefully revise the paper and resubmit.
Decision: Reject