Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a novel method for solving the discrete optimal transport problem based on the celebrated Douglas-Rachford splitting (DR) method. The core idea is to split the original transportation map into two variables X and Z, where X is simply non-negative and Z is real-valued and obeys the given row and column sums constraints. The Z-update step in DR is then non-trivial, consisting in projecting a given matrix onto the set of all real-valued matrices with such row/column constraints, which has a closed-form solution due to Bauschke et al. (2021). The authors present a detailed discussion on how to implement the resulting algorithms efficiently on GPUs, and provide a theoretical convergence analysis that recovers the known O(1/k) rate of convergence for DR method. Experiments on a synthetic problem show that the proposed method (using the authors' CUDA implementation) is more numerically stable than the standard Sinkhorn method, while being comparably fast.
main_review: The authors address an important problem and come up with an interesting algorithm. They also provide a rigorous theoretical convergence analysis as well as many insights on their CUDA implementation. The performance of the proposed method is competitive with Sinkhorn.

Unfortunately this paper also has some major limitations. The biggest one lies in its rather modest set of experiments. Some fundamentally important experiments are missing to support the claims of the paper.

1. Implementation is presented as a core contribution of this paper: it is mentioned in the title, and in addition, it is devoted a substantial amount of space for presentation (almost 3 pages, a part of Section 3.1 and especially the whole Section 3.3). Therefore, it would be absolutely necessary to show that the presented materials are important by actually comparing the provided implementation (with highly-optimized CUDA kernels) with a naive implementation, e.g., using GPU linear algebra libraries such as PyTorch or TensorFlow. The proposed method (Algorithm 1) can be easily implemented using these libraries in just a few lines.

2. The color transfer experiment is weird. Why aren't the results of Sinkhorn presented? Moreover, if sparsity is considered as an important objective, then the authors should also compare with Blondel et al. (2018). I would suggest to consider a more diverse set of examples to showcase the performance of DR in comparison with Sinkhorn (see also the next point).

3. Sinkhorn has been highly successful not only because of its efficiency, but also because its updates are differentiable, which makes it suitable for learning with stochastic gradient descent. While the updates of Algorithm 1 are also differentiable almost everywhere, it is unclear how this algorithm performs in learning, compared to Sinkhorn. I would encourage the authors to add some learning experiments to make the paper even more solid.


Finally, this paper also has some presentation issues.

1. Major issues:

- I wonder why the authors decided to denote 1_n as "e" and 1_m as "f". The notation "f" is used at multiple locations with different meanings (while the "e" can be confused with the Euler's number, though this is less critical than the "f"). It would be laborious to change because this is used everywhere, so I would suggest (as an acceptable fix) to replace the other instances of "f" with "h", e.g., "h(x) + g(x)" instead of "f(x) + g(x)".

- In Figure 1 and 2, the descriptions of the axes should be clear from the captions (instead of being hidden in the text). Furthermore, the text in the plots (such as axis labels, markers, legends) are unreadable (too small).

- Figure 3b shows that Sinkhorn is actually faster to reach a given accuracy (even though it is less numerically stable). This would deserve some comments (in a fair comparison of two methods, we should present both strengths and weaknesses of both methods).

2. Minor issues:

- Page 2, last paragraph of Section 1.1: "Liang et al. (2017), derived" --> "Liang et al. (2017) derived"

- Page 2, line -5: "methods(Rockafellar, 1976)" --> "methods (Rockafellar, 1976)"

- Section 2 2nd paragraph: 
	- "computed as Bauschke et al. (2021):"  --> "computed as (Bauschke et al., 2021):"
	- "linear program on the form" --> "linear program of the form"

- Page 3 last paragraph: "problems on the form" --> "problems of the form"

- Section 3, 2nd paragraph: "and fact that" --> "and the fact that"

- The notation for indicator function in Eq. (7) should be defined.

- Page 5 first paragraph: "matrix-vector multiples" --> "matrix-vector multiplications"

- Page 8 last paragraph: "A algorithm" --> "An algorithm"

---
**Update on November 10th:**

I would like to have some additional comments/questions. Hopefully the authors could address them as well in their rebuttal:

1. There seems to be a minor (likely fixable) **flaw** in Theorem 1 and the discussion thereafter. The inequality 
\begin{equation}
\langle C,\bar{X}\_k \rangle - \langle C,X^* \rangle \le \mathcal{O}(\|Y\_0-Y^*\|^2/k)\qquad (\star)
\end{equation}

is **not sufficient** to yield the convergence of the objective (let alone its rate). Note that **$\bar{X}_k$ might not be feasible** and thus $\langle C,\bar{X}\_k \rangle - \langle C,X^* \rangle$ might be negative. In order to obtain the convergence of the objective, one would need a lower bound as well:
\begin{equation}
\alpha_k \le \langle C,\bar{X}\_k \rangle - \langle C,X^* \rangle \le \mathcal{O}(\|Y\_0-Y^*\|^2/k),\qquad (\star\star)
\end{equation}
where $\alpha_k\to 0$. Furthermore, in order to obtain the claimed $\mathcal{O}(1/k)$ rate of convergence, one would also need to show that $(\alpha_k)$ converges to $0$ at the same rate.

2. The authors mentioned that they use the Sinkhorn implementation from POT. It is important to provide enough details so that the interested reader could reproduce the results. For example, which function of POT did the authors use and with which arguments? (ot.sinkhorn has quite several options for its arguments.)
summary_of_the_review: The proposed algorithm and analysis/implementation are interesting but the experiments are not convincing. The paper also has some issues with the presentation (but these can be easily fixed).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In order to solve large-scale optimal transport problems, the authors propose a Douglas-Rachford (DR) splitting method that solves the original OT without entropy regularization. 
The proposed DROT algorithm has the same cost per iteration as the well-known Sinkhorn method but avoids its numerical issues.
Furthermore, the proposed method possesses the strong convergence guarantees for its linear convergence rate; and it can be implemented efficiently using parallel processing on GPUs.
Experiments verify its efficiency and accuracy compared to Sinkhorn.

main_review: - It's a novel idea to rewrite the original OT problem into the standard form for DR-splitting and exploit the DR-splitting algorithm to solve it. The DROT method performs well in aspects of both speed and accuracy, thus being a strong competitor of the popular Sinkhorn method. 

- The proposed algorithm can save memory efficiently for it can be executed with only a single matrix variable.

- The organization of this paper is satisfactory, and the flow of algorithm derivation is very clear.

- Experiments on much larger-scale datasets are needed to verify the effectiveness of the proposed OT solver.

- Log-domain stabilization of Sinkhorn proposed by [1] is also a popular strategy to deal with numerical issues introduced by entropy regularization, while there is a lack of comparison with it.

[1] Schmitzer, Bernhard. "Stabilized sparse scaling algorithms for entropy regularized transport problems." SIAM Journal on Scientific Computing 41.3 (2019): A1443-A1481.

There are some typos and nitpicks:

- In line 1 of page 2, $\|v_{k} \odot\left(K^{\top} u_{k}\right)-q\|$ should be $\|v_{k-1} \odot\left(K^{\top} u_{k}\right)-q\|$. Note that $\|v_{k} \odot\left(K^{\top} u_{k}\right)-q\|$ always equals to 0 due to the Sinkhorn iteration equation.

- In figure 3, it’s better not to use colors to distinguish various methods, as this is not friendly for color-blind people; the text font of labels and axes is too small to read.




summary_of_the_review: The proposed method is interesting, while some points listed above need to be clarified.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a new splitting scheme for the original discrete OT problem. Unlike the existing splitting techniques, their solution requires an efficient implementation of rectangular matrix range space projection. The authors provide (somehow standard) 1/T convergence complexity and global linear convergence complexity. They report numerical results compared with the Sinkhorn method.
main_review: This paper report a new efficient numerical scheme for the fundamental discrete OT problem. The main technical contribution is a new splitting scheme by a recent result on efficient range space projection, which is very interesting. The authors also parallelize the algorithm for GPU computing and made the procedure numerical stable and efficient. The theoretical results are somehow standard as DR splitting is a special case of ADMM, of which the standard convergence behavior is well understood now. The linear convergence is mainly due to the KKT mapping being polyhedral and thus metric subregular. Existing results could directly give the linear convergence.

My main questions are as follows:

* The experiments are mostly conducted compared with the Sinkhorn method. It would be interesting to see the results of other splitting schemes for discrete OT, e.g., the iterative Bregman projection.

* It would be good to also provide empirical objective function value convergence curves. As the global linear convergence (due to global Hoffman bound) is proved, it would be interesting to see the empirical performance for that.

* Could the 1/k convergence be made non-ergodic?

summary_of_the_review: This paper introduces a new efficient DR scheme for discrete OT. The problem is important as it's widely used in ML models. The new splitting Eq.(7) is interesting, and the authors have spent an extensive effort to make the implementation efficient and robust.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies a splitting based gradient descent method for computing optimal transport objectives. It's based on splitting the row/column sum constraints into two objectives, and using a variant of the DR splitting algorithm. The paper rigorously proves a convergence guarantee of 1/k times the initial distance after k steps. Then it explores ways of setting up its algorithm in ways friendly to parallelism / memory hierarchy empirically: they obtain a very good wall-clock performance of about 1 second on a 20,000-by-20,000 optimal transport instance, and also examine the convergence of these algorithms.
main_review: While alternate minimization type approaches for OT have been extensively studied, I find the performance of about 1 second for 20000-by-20000 instances highly impressive. This requires a fairly high degree of parallelism, and is quite difficulty to obtain without significantly adapting to hardware. Some of the subtleties, such as numerical instability of sinkhorn2, is also something that I have observed before, so I consider the experiments quite thorough.

The algorithms are theoretically well founded, and have convergence guarantees typical of this type of methods. They also have the advantage of working directly with regularized OT instances, which to my understanding are critical for the downstream applications using OT. My main worry about these theoretical guarantees is that they are quite difficult to compare vs. unconditional bounds such as those obtained via combinatorial optimization packages, or the recent (purely theoretical) n^2 type methods (https://arxiv.org/pdf/2101.05719.pdf).
summary_of_the_review: Overall, I believe this paper has useful ideas for improving the performance of OT methods, especially those currently in use, but it falls a bit short of proposing something that significantly advances the state-of-art for OT.
review_title: null

Meta-review: This paper proposes a new algorithm to solve the discrete optimal transport problem, consisting of showing how the well-known Douglas Rachford algorithm can be efficiently applied, and also providing a convergence rate. Secondly, the paper gives an efficient implementation suitable for GPUs.

The paper would be a bit weak on just the DR contribution alone, so the efficient implementation, and experiments, are significant. However, the reviewers were not consistently happy with the experiments.

Two big issues raised by reviewers were wanting more experiments (having comparison experiments with real-world data), and wanting to compare with variants of the baseline algorithm (Sinkhorn), such as the log-transformed version which is more stable.  Looking at the revision, I think the reviewers have done a good job adding experiments.  Overall, for a paper with strong theoretical components, I think the computational aspects are strong.

As for (not) comparing with the log-transformed Sinkhorn and other more robust methods, the authors argue that this implementation would be slower.  I agree with reviewers that it would be nice to have these comparisons, but the authors' argument is plausible and I don't find it grounds to reject the paper.

Overall, it seems there is some evidence that this is a worthwhile method, and there are no theoretical concerns other than presentation issues. Thus I think it would be a benefit to the community to accept this paper.
Decision: Accept (Poster)