- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
In this paper, the authors propose a solver for semi-discrete optimal transport, where the source distribution is continuous and the target distribution is discrete under the squared Euclidean cost. Starting from the semi-dual formulation of the Kantorovich OT problem, the authors derive a convex energy function whose minimization yields the optimal transport solution. To minimize this objective, they propose a stochastic projected gradient descent algorithm that estimates the gradient using mini-batches sampled from the source distribution. At each iteration, the algorithm performs a gradient update with a decreasing step size, clips the resulting potentials to a bounded interval, and projects them onto the subspace of centered potentials. Finally, the method returns a weighted average of the iterates. The authors provide an alternative version of this algorithm that uses Monte Carlo guidance during the iterations. The experimental section consists of a synthetic experiment with a uniform source distribution on and a discrete target distribution supported on points, with a target mass ratio of four.
Critical strengths
Despite some minor inconsistencies in notation, the paper is clear and easy to follow, with good presentation and organization. The theoretical results are well motivated, and the paper provides several theoretical guarantees to support its claims.
Critical weaknesses
Below I list my main concerns:
[W1]General relevance of the contribution. The paper introduces RSC-PSGD in Algorithm 1 and an improved variant in Algorithm 2, with particular emphasis on addressing the empty-cell problem in semi-discrete optimal transport. However, the experiments do not explicitly evaluate how the proposed method behaves when empty cells occur, making it difficult to assess the practical relevance of this contribution. This is particularly important because the proposed algorithms closely resembles conventional PSGD, with the main differences being the clipping operation and step-size schedule. Moreover, Figure 2 shows that RSC-PSGD (Algorithm 1) performs worse than conventional PSGD. Therefore, without empirical evidence demonstrating the benefits of the proposed method in the presence of empty cells, its practical advantages over existing approaches remain unclear.
[W2] Effectiveness of the MC-guided strategy. Appendix B.2 reports that all spectral-gap estimates were rejected in the experiments of Figure 2, meaning that Algorithm 2 retained the theoretical RSC constant while using an empirical smoothness estimate. Therefore, it is unclear whether estimating both spectral quantities is necessary. An ablation evaluating the contribution of each estimated constant would help clarify which components are responsible for the observed performance improvements.
I have other minor comments:
-
The brief derivation of the dual formulation in Appendix A.1 could be moved to the main text to improve the flow and readability of the paper.
-
The notation in the convergence rate in the introduction should be explicitly defined. I also suggest using a different symbol to avoid confusion with the transport map introduced in Equation (1).
-
The notation initially represents the potential associated with target , while in Algorithm 1 denotes the potential vector at iteration . This change in indexing should be clarified or modified to avoid confusion.
In summary, although the proposed methods are closely related to conventional PSGD, the paper provides valuable theoretical results that constitute its main contribution. Nevertheless, there is insufficient empirical evidence demonstrating the practical benefits of the proposed approach in the presence of empty Laguerre cells. I also have concerns regarding the significantly worse performance of the original RSC-PSGD method compared to existing approaches. Based on these observations, I recommend weak reject.
Questions for authors
Q1. Could the authors clarify why RSC-PSGD (Algorithm 1) performs worse than conventional PSGD in Figure 2? Given that the proposed method uses theoretically derived constants and a prescribed step-size schedule, one would expect these modifications to provide some advantage over conventional PSGD.
6 comments
I thank the authors for their response. After carefully reviewing their answers, I have decided to maintain my original score, as my first concern remains largely unaddressed, while the second has only been partially addressed.
Follow-up: exact empty-cell experiments and clarification of scope
Thank you for carefully reconsidering our response. We agree that our previous reply did not provide the direct empty-cell evidence requested in W1. We have now completed controlled experiments with exact cell-mass diagnostics.
Contribution and the role of empty cells. Genans et al. already establish convergence of stochastic semi-discrete OT. Our contribution makes the curvature and regional RSC constants explicit: the Hessian lower bound applies at positive-mass configurations, and the regional inequality extends the convergence analysis to bounded potentials with zero-mass cells. It does not require a positive Hessian eigenvalue at every iterate.
For distinct target sites in the interior of the source domain, our adoption of Voronoi initialization gives every cell positive mass under the stated density assumptions. This places the initial point in the convex positive-mass region, but does not guarantee that later cells remain positive. Empty cells do not make the dual problem infeasible: the energy remains convex and its stochastic gradient remains unbiased.
If , the sampled gradient coordinate is almost surely, so the update raises that potential before projection. PSGD shares this mechanism. Our regional RSC analysis and prescribed schedule give convergence guarantees without an explicit cell-repair step. By comparison, KMT's damped Newton algorithm checks a positive mass threshold when accepting steps. Avoiding exact geometric mass checks and per-step Hessian construction is useful when scaling sampling-based methods to higher dimensions, because the construction of geometric cells is difficult in higher dimension.
New controlled experiments. We use a uniform source on : 1D with , and 2D with on a grid or at random sites. Shared initial potentials have 0%, 25%, 50% or 75% true empty cells; an additional 50% case places the suppressed potentials farther below the active envelope. The target mass ratio is four. All methods receive the same initialization and paired training samples. Interval/polygon integration measures every actual iterate's cell masses and energy, without MC validation noise; the irregular 2D optimum is computed numerically with a population mass residual below .
With and three training seeds, every method uses 272k source samples per run. The revised fixed-shift RSC method includes 10,240 draws for one independent MC calibration; baselines spend that allowance on extra updates. We retain all three PSGD coefficients, , and the author's default .
For the shared 50% empty-cell initialization, mean final dual-energy gaps are:
| Geometry | Revised RSC + MC | PSGD default | PSGD c=0.5 | PSGD c=5 |
|---|---|---|---|---|
| 1D | 3.95e-6 | 7.53e-4 | 1.20e-6 | 2.72e-5 |
| 2D grid | 3.46e-6 | 6.86e-5 | 2.79e-6 | 7.06e-6 |
| 2D random | 2.39e-6 | 1.34e-4 | 8.47e-7 | 1.00e-5 |
These are native outputs: shifted pre-update averaging for RSC and uniform post-update averaging for PSGD. Across all 12 initially-empty settings (3 geometries times 4 initial configurations), the revised method has lower mean energy error than default PSGD; this ordering also holds with common pre-update uniform averaging. Smaller PSGD coefficients can perform better, and half-suffix averaging favors default PSGD in the 2D settings. We therefore claim finite-budget improvements for the specified comparisons, not universal superiority.
Recovery is measured on actual iterates, using for every cell. Median source draws to first reach this threshold, including calibration, are:
| Geometry, 50% initially empty | Revised RSC + MC | PSGD default |
|---|---|---|
| 1D | 11,328 | 153,408 |
| 2D grid | 14,528 | 16,512 |
| 2D random | 11,648 | 30,592 |
Both revised RSC and default PSGD reached this threshold in all 36 runs with initially empty cells. All revised runs ended with no empty cells. After first recovery, empty cells reappeared in 9/36 revised runs, compared with 36/36 default-PSGD runs. Thus, first recovery does not imply permanent positivity.
W2: simplified MC calibration. The revised MC wrapper algorithm calibrates only the upper spectral scale once, retains the theoretical RSC constant, and fixes the shift before training. We therefore no longer claim that estimating both spectral quantities is necessary. The new experiments evaluate this simplified design, rather than separately isolating the effects of calibration and the schedule revision.
These exact low-dimensional tests complement our revised experiments at , . They directly quantify recovery from true empty cells and finite-budget accuracy under matched sampling budgets.
Thank you for highlighting the empty-cell behavior and MC calibration.
W1: theoretical and practical contributions. Genans et al. already establish convergence and regional RSC. Our theoretical contribution supplies explicit curvature bound and regional constants under our assumptions, making parameter selection and finite-time guarantees quantitative. In particular,
a_D=\frac{\nu_{\min}}{A(d+1)f_{\max}/f_{\min}+R_0+D},$$ holds throughout the bounded potential region, including initial or intermediate zero-mass cells. It controls the gradient toward the optimizer without requiring a positive Hessian eigenvalue at every iterate. For an empty cell, the stochastic gradient component is $-\nu_i$, so its potential is raised before projection. PSGD has the same mechanism. Our lifting construction is an analytical device, not an extra cell-repair operation. For the distinct sites inside the source cube used in our experiments, Voronoi initialization gives positive mass to every cell. This property concerns the initial potential; subsequent stochastic steps can still create empty cells. Both methods share this initialization. Practically, curvature scales guide step sizes in larger problems. Submitted tests reach $d=128,k=5000$; revised comparisons use $k=1000,d=10,50,128$. We agree that these comparisons do not isolate recovery from true empty cells. We will add a controlled experiment using exact one-dimensional cell masses, varying initial zero-mass cells and measuring recovery and subsequent error. Existing performance gains alone do not establish faster empty-cell recovery. **Q1: original Algorithm 1 and the revision.** The reason is our upper bound of $\beta$ is too conservative because we focused more on the improvement of the lower bound of $\lambda_2$. The original schedule $\eta_t=2/(at+4\beta)$ uses $\beta$ around 2200-3500. Its warmup phase $4\beta/a$ is $5.1\times10^9$-$3.3\times10^{11}$, far above 8192 training steps. Thus the method remains near its very small initial step, explaining the poor finite-budget progress. Our implementation audit found agreement with the stated updates and the PSGD baseline. We therefore revised the algorithm 1 with better initialization and scheduling. The revised core retains certified $a$, clipping and centering, but permits any fixed $s\ge2$ in $\eta_t=2/[a(t+s)]$, with weights $t+s-1$. A bounded-gradient proof retains $O(1/T)$ expected dual-energy error without requiring $s\ge4\beta/a$, while losing the original bound's explicit $1/B$ benefit. One independent calibration selects and freezes $s$. At $k=1000,B=64$, equal total source-sample budget 592,384 including calibration, and three training seeds, mean validation $L^1$ residuals are: | $d$ | Revised RSC-SGD | PSGD default | | --- | ---: | ---: | | 10 | 0.07604 | 0.16441 | | 50 | 0.07449 | 0.09530 | | 128 | 0.07460 | 0.08730 | This compares weighted-query averaging with PSGD's native post-update averaging, coefficient $\sqrt{Bk}$ and decay $3/4$, from a shared initial potential. **W2: rejection of the estimated gap.** Each setting has four refreshes per seed and three seeds, hence 12 refreshes. The empirical gap is used only if graphs at both bandwidths $\delta/2,\delta$ are connected and their spectral computations return positive gaps. Archived records show that every rejection in Figure 2 was caused by a disconnected empirical graph, with no reported eigensolver failure. This rejects a finite-sample local estimate; it does not invalidate our analytic lower bound or imply that the true gap is zero. Sampling can miss interfaces even with positive-mass cells. For example, at initialization for $d=10,k=1000$, seed 0, both sampled graphs are disconnected although all cells receive samples and their population masses are positive. Consequently, these runs retain theoretical $a$ and use empirical $\widetilde\beta$ in $2/(at+4\widetilde\beta)$. The benefit comes from the less conservative upper spectral scale, not from changing the lower constant. We agree that the experiments do not establish a need to estimate both quantities. The revised MC wrapper therefore calibrates the upper scale only once and keeps $a$ fixed. At equal training budget, original four-refresh Algorithm 2 residuals are 0.07628, 0.07527, 0.07470, close to the revised results above, while requiring four times the calibration samples. We will update Appendix B.2 with the rejection criterion, its observed causes, and this comparison.