A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem

We appreciate your thorough review. We answer your questions below.

Could the authors provide some more background on the construction of Voronoi diagram, ie, the complexity of the construction?

Response: For 2 dimensions, the weighted Voronoi diagram under the squared Euclidean distance (also known as the Laguerre diagram or the power diagram) can be constructed in $O(n\log n)$ time [1, 2]. For higher dimensions $d>2$, the construction time would be $O(n^{\lceil (d+1)/2\rceil})$ [3].

[1] Fortune, Steven. "Voronoi diagrams and Delaunay triangulations." In Handbook of Discrete and Computational Geometry, pp. 705-721, 2017.

[2] Sugihara, Kokichi. "Laguerre Voronoi diagram on the sphere." Journal for Geometry and Graphics 6, no. 1 (2002): 69-81.

[3] Aurenhammer, Franz. "Power diagrams: properties, algorithms and applications." SIAM Journal on Computing 16, no. 1 (1987): 78-96.

Is there any lower bound on the runtime of algorithms for the semi-discrete OT problem?

Response: In 2 dimensions, there are no known sub-quadratic algorithms even for the discrete version of the OT problem. The semi-discrete OT problem is a generalization of the discrete OT problem. So, to obtain a runtime better than $O(n^2)$, one would expect that a subquadratic-time algorithm for the discrete OT would come first.

For higher dimensions, as stated in our paper, computing an $\varepsilon$-close semi-discrete transport plan in a time that is polynomial in $d$ and $\log 1/\varepsilon$ is known to be #$P$-Hard [4].

[4] Taşkesen, Bahar, Soroosh Shafieezadeh-Abadeh, and Daniel Kuhn. "Semi-discrete optimal transport: Hardness, regularization and numerical solution." Mathematical Programming 199, no. 1 (2023): 1033-1106.

How is Theorem 1.2 compared with other algorithms for the discrete OT problem?

Response: Thank you for this question. Given $\mu$ (with support size $N$) and $\nu$ (with support size $k$), the execution times of the best-known discrete OT algorithm is almost-linear in the number of edges of the bipartite graph, i.e., $(Nk)^{1+o(1)}$ [5, 6]. In contrast, by preprocessing $\mu$ in near-linear time, we can compute a discrete OT plan for any query $\nu$ in $O(\sqrt{N}k^{4}\log 1/\delta)$ time. Thus, when $k$ is sufficiently small (say $k < N^{1/6}$), our algorithm is faster than all existing discrete OT algorithms. We will highlight this improvement to discrete OT algorithms in the next version of our paper.

[5] Chen, Li, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. "Maximum flow and minimum-cost flow in almost-linear time." FOCS 2022.

[6] Agarwal, Pankaj K., Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. "Faster Algorithms for the Geometric Transportation Problem." SoCG 2017.

We appreciate your thoughtful review. We address your concern below.

The work is largely a reworking of other recent results in the field, in particular the paper of Agarwal et al. at SODA24. It's not clear that improving the polynomial dependence here is highly relevant.

Response: Improvement in the run time is only one part of our contribution. What we consider the most important contribution is the new algorithmic framework we propose for the semi-discrete OT problem. The algorithm from SODA 2024 discretizes a continuous distribution and then solves an instance of the discrete OT problem defined on these points in $\tilde{O}(n^9)$ time. In contrast, our algorithm extends the classical combinatorial primal-dual approach for discrete OT to the semi-discrete setting. It applies ideas such as augmenting paths on residual graphs directly to continuous regions (rather than samples from the regions). To our knowledge, our paper is the first to introduce this framework. As a result of the new combinatorial framework, we obtain a significant reduction in execution time to $\tilde{O}(n^4)$.

We remark that polynomial improvements to discrete OT have had a significant impact on ML applications [1, 2, 3, 4]. Similar improvements for the semi-discrete OT problem is an important challenge and we make significant progress in addressing this challenge.

[1] Cuturi, Marco. "Sinkhorn distances: Lightspeed computation of optimal transport." NeurIPS 2013.

[2] Altschuler, Jason, Jonathan Niles-Weed, and Philippe Rigollet. "Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration." NeurIPS 2017.

[3] Lahn, Nathaniel, Deepika Mulchandani, and Sharath Raghvendra. "A graph theoretic additive approximation of optimal transport." NeurIPS 2019.

[4] Jambulapati, Arun, Aaron Sidford, and Kevin Tian. "A direct $\tilde{O}(1/\varepsilon)$ iteration parallel algorithm for optimal transport." NeurIPS 2019.

We appreciate your insightful review. We answer your question below.

Is this method an implementable and practically applicable algorithm, or is it challenging to apply in real-world scenarios due to large constant factors, thus possessing only theoretical value?

Response: The main contribution of the paper is a new algorithmic framework for the semi-discrete OT problem, which we believe has much potential. Overall, our algorithm is practical and the constants hiding in the big-O notation are small. However, faithful implementation of our algorithm requires (a) constructing and dynamically maintaining arrangements of Voronoi diagrams, and (b) computing the exact mass inside any given triangle. Developing efficient and robust software that combines our algorithm with black-boxes (a) and (b) is a significant task. An interesting direction of future research is to explore which existing geometric software libraries, including the ones based on GPUs, can be used for our setting.

Recollect that our algorithm does not make any assumptions on the smoothness of the continuous distribution. In future work, we will investigate whether we can significantly simplify our algorithm if we are willing to make certain smoothness assumptions (similar to the ones made in existing work [1, 2]) about the continuous distribution.

[1] Oliker, Vladimir I and Laird D Prussner. ``On the numerical solution of the equation $\frac{\partial^{2}z}{\partial x^2} \frac{\partial^2 z}{\partial y^2} - \left (\frac{\partial^2 z}{\partial x \partial y} \right) = f$ and its discretizations, $i$.'' Numerische Mathematik, 54(3):271–293, 1989.

[2] Merigot, Quentin, and Boris Thibert. "Optimal transport: discretization and algorithms." In Handbook of numerical analysis, vol. 22, pp. 133-212. Elsevier, 2021.