acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Gradient Descent for Semi-Discrete Optimal Transport

Abstract

Semi-discrete optimal transport maps a continuous probability distribution onto finitely many target points with prescribed masses. We study stochastic gradient descent (SGD) for its Kantorovich dual energy, using source samples to estimate the masses of the associated Laguerre cells. For quadratic cost, a compact convex source domain, and a positive bounded H\"older continuous density, we derive an explicit lower bound on the smallest positive eigenvalue of the dual Hessian from a transport variance inequality. The bound is linear in the smallest cell mass. The main difficulty is that cells can become empty during SGD, making this eigenvalue bound vanish. We prove an explicit restricted strong-convexity bound on an entire bounded region of potentials, including empty-cell configurations. Clipping and centering keep every iterate in this region. Together with an explicit smoothness bound, decreasing steps and weighted averaging give an expected dual-energy error, with separate initialization and sampling terms. We also introduce MC-guided SGD, which uses sampled spectra to choose practical steps and can restart the guaranteed algorithm when needed. Experiments up to dimension 128 and 5000 targets show lower errors than the global schedule in many settings, with competitive accuracy against projected SGD and a measurable spectral-estimation overhead.

Primary area:
optimization
Keywords:
optimal transport, optimization

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_uSrXOpenReview ↗
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 H0H_0 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 [0,1]d[0,1]^d and a discrete target distribution supported on kk 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 TT in the O(1/T)O(1/T) convergence rate in the introduction should be explicitly defined. I also suggest using a different symbol to avoid confusion with the transport map TT introduced in Equation (1).

  • The notation hih_i initially represents the potential associated with target yiy_i, while hth_t in Algorithm 1 denotes the potential vector at iteration tt. 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

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.

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.

AuthorsOpenReview ↗

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 pi(h)=0p_i(h)=0, the sampled gradient coordinate is −νi-\nu_i 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 [0,1]d[0,1]^d: 1D with k=12k=12, and 2D with k=16k=16 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 10−1210^{-12}.

With B=64B=64 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, 0.50.5, 55 and the author's default Bk\sqrt{Bk}.

For the shared 50% empty-cell initialization, mean final dual-energy gaps are:

GeometryRevised RSC + MCPSGD defaultPSGD c=0.5PSGD c=5
1D3.95e-67.53e-41.20e-62.72e-5
2D grid3.46e-66.86e-52.79e-67.06e-6
2D random2.39e-61.34e-48.47e-71.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 pi≥0.1νip_i\ge0.1\nu_i for every cell. Median source draws to first reach this threshold, including calibration, are:

Geometry, 50% initially emptyRevised RSC + MCPSGD default
1D11,328153,408
2D grid14,52816,512
2D random11,64830,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 k=1000k=1000, d=10,50,128d=10,50,128. They directly quantify recovery from true empty cells and finite-budget accuracy under matched sampling budgets.

Reviewer_rg28OpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies semi-discrete optimal transport, i.e. a problem where absolutely continuous probability law is transported into point masses of given size. The manuscript studies algorithm based on stochastic gradient descent for the problem. In particular, several interesting theoretical results are proved.

Critical strengths

The problem is analyzed clearly and the theoretical approach is solid: proofs are correct and rigor, and results are strong. While the theoretical approach is the focus, the paper is accompanied with experiments.

Critical weaknesses

Numerical experiments could be better connected to the theory. Also, theory is limited to compactly supported distributions. Hence, e.g., Gaussian distributions cannot be covered.

Questions for authors

Could the results be extended to cover more general class of distributions with non-compact support, under suitable conditions that would cover at least Gaussian type-distributions? At least some discussion could be added.

1 comment

Thank you for the positive assessment. We will strengthen the theory-experiment connection and clarify the scope of distributional extensions.

Revised algorithm and empirical evidence. The original global smoothness bound made Algorithm 1's steps overly conservative. The revised core retains the certified regional RSC constant aa, uses ηt=2/[a(t+s)]\eta_t=2/[a(t+s)] with any fixed s≥2s\ge2, and averages with weights t+s−1t+s-1. A bounded-gradient argument gives O(1/T)O(1/T) expected dual-energy error without requiring s≥4β/as\ge4\beta/a. The tradeoff is loss of the original bound's explicit 1/B1/B improvement. One independent calibration selects the initial step and freezes ss, so the training guarantee does not require empirical spectra to be valid global curvature bounds. Details has been posted above in previous response to reviewer QhPG.

Gaussian and other noncompact sources. A full Gaussian is itself noncompact. Our sampling updates can use Gaussian samples without truncation. For quadratic cost and finitely many distinct target sites, Gaussian integrability and almost-surely unique assignments give an unbiased gradient GtG_t with

\mathbb E[\|G_t-\nabla E(h_t)\|^2\mid\mathcal F_t]\le1/B.$$ Moreover, $\|G_t\|^2\le1-2\nu_{\min}+\|\nu\|^2\le2$. Thus unbounded source samples do not make the gradient with respect to the potentials unbounded. The limitation is our current explicit geometric constants: a full Gaussian has infinite support diameter and no positive global density lower bound. Our formulas for the potential region and regional $a$ therefore cannot be applied directly. The optimization argument remains usable if a valid invariant region containing the optimizer and a quantitative RSC constant are supplied. [Genans et al., Section 4](https://arxiv.org/html/2510.25287v1#S4) already establishes potential localization and regional RSC existence for noncompact quadratic OT under conditions that include nondegenerate Gaussians. Our open direction is to obtain explicit estimates suitable for parameter selection, not to establish Gaussian SGD from scratch. A Gaussian conditioned on a compact convex domain is already covered by our assumptions, but transferring its guarantee to the full Gaussian requires a separate tail-error analysis. Gaussian comparisons for the revised schedule have not yet been completed. We will discuss explicit constants for Gaussian and more general noncompact sources as future work. Nonconvex source domains are a separate direction: the energy remains convex in the potentials, but geometric connectivity and curvature estimates can become more delicate.
Reviewer_QhPGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors prove bounds on the smoothness and restricted strong convexity of the dual energy potential for the semi-discrete optimal transport problem. They then use these bounds to argue that stochastic gradient descent converges at the rate of O(1/T)O(1/T) to the global optimum. The authors additionally introduce MC-guided stochastic gradient descent, which uses sampled eigenvalues to approximate the true global smoothness parameters. The authors show experimentally that in some cases, MC-guided stochastic gradient descent outperforms the default stochastic gradient descent algorithm they describe.

Critical strengths

I believe that high-quality research papers focus on simplicity and ease of presentation, and the authors do a great job of meeting this expectation. The authors generously provided clean proof sketches for many of the main technical lemmas and theorems of their paper in the main text, which I greatly appreciated. The authors did a good job of defining the semi-discrete optimal transport problem and stochastic gradient descent on the dual energy potential. And they included Figure 1 to help explain key ideas of gradient descent on the dual energy potential, which I thought was incredibly well made.

Critical weaknesses

My one biggest concern is that I do not yet appreciate the theoretical contributions of the authors. The key bound that they prove is an O(1/T)O(1/T) convergence under assumptions on the smoothness and restricted strong convexity of the input. Yet their cited reference (Genans et al., 2025b) proves the same convergence rate. It is true that on page 7 of (Genans et al., 2025b), it is stated that they do not prove a bound on the precise constant appearing in the convergence rate. However, I do not see the value in proving bounds for the constant if the constants are weak and do not lead to an improved analysis of the stochastic gradient descent algorithm. A more detailed description of how their bounds on the precise constant yield a significant improvement would be much appreciated.

In particular, the parameters β\beta and aa for smoothness and restricted strong convexity, respectively, appear in the error bounds for both Theorems 3.2 and 3.3. It is true that since these are parameters of the input and remain constant throughout the performance of the algorithm. However, it also seems misleading to say that to get a desired error of ε\varepsilon one needs O(ε−1)O(\varepsilon^{-1}) iterations when the constant depends on the parameters of the input. In practice, it should be assumed that these parameters are quite large. Even in just the 4 examples that you give in Table 1, most of them have β/α≥7000\beta/\alpha \geq 7000. The constants β\beta and aa seem to be related to the condition number of the dual optimization problem, and linear dependence on the condition number seems to be a highly expected outcome for convex optimization, such as in "Convex optimization" by Vandenberghe and Boyd. There are alternative algorithms which solve the semi-discrete optimal transport problem without stochastic gradient descent, and therefore also remove the dependence on these smoothness parameters. A justification that the parameters β\beta and aa should be small in practice therefore seems necessary to motivate the benefits of stochastic gradient descent.

In short, I found the discussion of related work to be quite weak, and it meant that I could not appreciate the contributions that the authors made. A more thorough review of all related work on semi-discrete optimal transport would better place the authors' contributions into context.

Questions for authors
  • How would you differentiate your theoretical contributions from the work of (Genans et al., 2025b)? Is it only the bound on the constants?
  • If the bound on the constants for the convergence rate are the primary theoretical contributions of the paper, then intuitively why should a constant that depends on 1/νmin1/\nu_{min} (or proportional to the condition number of the dual problem) be an interesting bound on the constant for the convergence rate?
1 comment

Thank you for asking us to clarify the contribution.

Q1: distinction from Genans et al. Genans et al. already establish regional RSC and O(1/T)O(1/T) results, while leaving the RSC constant unquantified. Our contribution is explicit OT geometry under our compact convex source and positive-density assumptions:

A=e(f_{\max}/f_{\min})D_XR_Y,$$ and, on $\operatorname{osc}(h)\le D$, $$\langle\nabla E(h),h-h^{\ast}\rangle\ge a_D\|h-h^*\|^2,\qquad a_D=\frac{\nu_{\min}}{A(d+1)f_{\max}/f_{\min}+R_0+D}.$$ Here $D_X$ is source diameter, $R_Y$ target radius, and $R_0$ bounds optimal potentials. The second estimate remains valid with empty cells, where a pointwise Hessian lower bound is insufficient. Building on the transport variance inequality of Letrouit-Merigot, our spectral estimate improves the minimum-mass exponent from KMT's cubic dependence to linear dependence under our assumptions. The estimates enable explicit parameter choices. Submitted experiments reach $d=128,k=5000$, beyond Genans et al.'s 10/50-target examples; the revised comparisons below use $k=1000$. **Q2: why is $1/\nu_{\min}$ informative?** Inverse-curvature dependence is standard; the additional information is which OT inputs determine it and at what order. We obtain $$a_D^{-1}=\frac{A(d+1)f_{\max}/f_{\min}+R_0+D}{\nu_{\min}}.$$ For example, $\nu_{\min}\ge c/k$ and bounded $A$ give $\lambda_2(L(h^*))\ge c/(Ak)$. Other geometric quantities can still depend on $k,d$. Regional mass dependence can be necessary at a well-conditioned optimum. For $\mu=\mathrm{Unif}[0,1]$, sites $(0,1)$ and masses $(q,1-q)$, $0<q\le1/2$, the optimal Hessian has positive eigenvalue $2$ and condition number $1$. Yet on the fixed region $\operatorname{osc}(h)\le1$, the best RSC constant is $2q/(1+q)=\Theta(\nu_{\min})$: an empty cell with target mass $q$ has a restoring gradient of magnitude $q$. This distinguishes regional optimization geometry from the optimal-point condition number. We will also state the original finite-budget guarantee explicitly: $$\mathbb E[E(\bar h_T)-E(h^*)] =O\left(\frac{\beta^2U_0}{aT^2}+\frac1{aBT}\right).$$ A sufficient budget is $T=O(\beta\sqrt{U_0/(a\epsilon)}+1/(aB\epsilon))$. Thus $O(\epsilon^{-1})$ is a fixed-problem statement, not uniform over geometry or masses; $\beta/a$ should not be assumed small or equated with the actual optimal condition number. **Conservative constants and the revised algorithm.** We agree that Figure 2 exposes a practical limitation. With $\eta_t=2/(at+4\beta)$, the old warmup phase is $5.1\times10^9$-$3.3\times10^{11}$ versus 8192 steps budget. The method makes little progress with nearly constant steps around $10^{-4}$. Original Algorithm 2 retains theoretical $a$ in these runs; its improvement comes from an empirical upper spectral scale $\hat{\beta}$. We now retain certified $a$ but allow any fixed $s\ge2$ in $\eta_t=2/[a(t+s)]$, with matching weights $t+s-1$. Bounded stochastic gradients yield an $O(1/T)$ guarantee without requiring $s\ge4\beta/a$, at the cost of losing the explicit $1/B$ benefit. One independent calibration selects and freezes $s$; the proof does not require empirical eigenvalues to be global certificates. Separately, a KMT boundary-area argument tightens analytic $\beta$ by factors 16-21; those bounds have not yet been used in the new runs. At $k=1000,B=64$, three training seeds and equal total source-sample budget 592,384 including calibration, mean $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 | We use shared initialization and each method's primary output: weighted-query averaging versus PSGD's native post-update averaging, with default coefficient $\sqrt{Bk}$ and decay $3/4$. The revision reaches accuracy comparable to old Algorithm 2 with 75% fewer calibration samples. **Other convex methods and context.** Such methods remain applicable. Gu et al. provide the geometric variational formulation; KMT analyzes damped Newton; Genans et al. supplies stochastic convergence theory. Newton needs cell/interface integration and linear solves, whereas SGD uses sampled assignments. Line search can avoid specifying constants without removing geometry from guarantees. Entropic methods introduce a regularization tradeoff; their results do not automatically give unregularized guarantees. We will sharpen these distinctions in related work. Currently the applications of OT theory in generative modeling (e.g. GAN, Diffusion models and Flow Matching) are quite popular, those works either use standard SGD, or rely on entropic algorithm and work on small batch of data, or require an extra sub-solver. The applications of OT in generative modeling motivates the study of efficient and scalable algorithm; end-to-end benefits in generative modeling remain future work.
Reviewer_RsGqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies SGD on the Kantorovich dual of semi-discrete optimal transport (mapping a continuous distribution onto kk points with prescribed masses), with a quadratic cost, where the gradient is the mismatch between sampled cell masses (the fraction of source mass assigned to each target) and target masses. It derives explicit smoothness and restricted strong-convexity constants, the latter from a transport variance inequality that gives a Hessian eigenvalue bound linear in the smallest cell mass and is extended by a separate argument to configurations with empty cells, where the Hessian bound itself vanishes. By clipping and centering the iterates, decreasing step sizes and weighted averaging, this yields an O(1/T)O(1/T) bound on the expected dual-energy error. Because the constants are conservative, a Monte Carlo-guided variant estimates the extreme Hessian eigenvalues from samples to take larger steps, with a fallback to the guaranteed schedule; experiments up to d=128d = 128 and k=5000k = 5000 show it outperforms the guaranteed schedule and is competitive with projected SGD, without a guarantee for the MC-guided phases.

Critical strengths

The claims appear correct, and the proofs are managed carefully. The Hessian eigenvalue bound is linear in the smallest cell mass pminp_{\mathrm{min}}, improving on the cubic dependence in the literature. The extension of RSC to configurations with empty cells---which lifts each empty cell’s affine piece until it touches the envelope---is mathematically elegant. Finally the constants are explicit and presented in closed form.

Critical weaknesses

The primary weakness is that the theory and the experiments are largely disconnected. The guaranteed algorithm (Algorithm 1) barely converges in the multidimensional experiments, while Algorithm 2, the one that performs well and is more practical, has no guarantee during the MC-guided phases and in all large-scale runs reduces to Algorithm 1 with an empirically estimated β\beta. Moreover, the experiments never test the assumptions that drive the constants: all sources are uniform on a cube, so fmax/fmin=1f_{\mathrm{max}}/f_{\mathrm{min}} = 1 and the Hölder condition is trivially satisfied.

Questions for authors

In dimension one with a uniform source, the Hessian at the optimum doesn't depend on ν:\nu: how do you justify in this simple case the dependence on νmin\nu_{\mathrm{min}} in the bound?

It could be nice to have some experiments in settings where the Laguerre cells are computable explicitly: if we take dimension two or three, can you compare your method with damped Newton method? Or is it that the advantage of SGD is only in high dimensions?

1 comment
AuthorsOpenReview ↗

Responses to Reviewer RsGq

Thank you for the careful reading and advice. We address the theory-experiment connection and both questions below.

Practical schedule and its guarantee. Our analysis improves the minimum-cell-mass dependence of the Hessian bound from cubic to linear and gives explicit regional RSC, including empty cells. The original schedule, ηt=2/(at+4β)\eta_t=2/(at+4\beta), was nevertheless too conservative: in Figure 2, β\beta is about 2200-3500 and 4β/a4\beta/a is 5.1×1095.1\times10^9-3.3×10113.3\times10^{11}, versus only 8192 steps. Thus the steps remain close to the small value 1/(2β)1/(2\beta) throughout the experiment.

The revised core retains the certified aa, clipping and centering, but permits any fixed s≥2s\ge2 in ηt=2/[a(t+s)]\eta_t=2/[a(t+s)], with averaging weights t+s−1t+s-1. Since the complete stochastic gradient has squared norm at most Mν2=1−2νmin⁡+∥ν∥2≤2M_\nu^2=1-2\nu_{\min}+\|\nu\|^2\le2, a bounded-gradient argument gives

\frac{a(s-1)(s-2)U_0}{T(T+2s-3)} +\frac{4M_\nu^2}{a(T+2s-3)}.$$ Here $U_0\ge\|h_0-h^*\|^2$. This preserves $O(1/T)$ while losing the original bound's explicit $1/B$ benefit. One independent calibration selects $s$, which is then frozen; conditional on calibration, the guarantee covers training without treating empirical eigenvalues as certified global bounds. 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 | Both share geometric initialization. Revised RSC uses weighted-query averaging; PSGD uses $c=\sqrt{Bk}$, decay exponent $3/4$, and native post-update averaging. Common half-suffix averages can favor PSGD. These are finite-budget residual comparisons. The original four-refresh Algorithm 2 reaches similar accuracy; the revision uses 75% fewer calibration samples. Separately, a KMT boundary-area argument reduces our analytic $\beta$ bounds by factors 16-21; those new bounds have not yet been used in these training runs. **Source assumptions.** We agree that uniform sources do not test density contrast; nonuniform target weights do not resolve this. With $r=f_{\max}/f_{\min}$, $$a_D=\frac{\nu_{\min}}{e(d+1)D_XR_Yr^2+R_0+D}.$$ The uniform tests fix $r=1$. The Hölder condition justifies positive-cell Hessian regularity; its exponent and seminorm do not explicitly enter this formula. We will add a controlled positive, nonuniform-density study. **Q1: the one-dimensional uniform Hessian.** Your observation is correct. For fixed ordered sites and $\mu=\mathrm{Unif}[l,u]$, let $\ell=u-l$. Positive target masses give boundaries $b_i^{\ast}=l+\ell\sum_{j\le i}\nu_j$ and $$L(h^*)=\sum_{i=1}^{k-1} \frac{(e_i-e_{i+1})(e_i-e_{i+1})^\top}{\ell(y_{i+1}-y_i)}.$$ Thus the optimal Hessian is independent of $\nu$, and our general optimal-point bound is conservative here. For $[0,1]$ and sites $(0,1/2,1)$, its eigenvalues are always $0,2,6$. Regional RSC is different. For sites $(0,1)$ and masses $(q,1-q)$, $0<q\le1/2$, write $h=(t/2,-t/2)$ on the fixed region $t\in[-1,1]$. The ratio $\langle\nabla E(h),h-h^{\ast}\rangle/\|h-h^{\ast}\|^2$ equals $2$ for $t\ge0$ (away from the optimizer), and $2q/(q-t)$ for $t<0$. Its infimum is $2q/(1+q)=\Theta(\nu_{\min})$, although the optimal positive eigenvalue is always $2$. Mass dependence is therefore necessary for this regional guarantee, not for the optimal Hessian in this special case. **Q2: damped Newton.** We agree that it is an important low-dimensional baseline. Geometric Newton requires cell masses, density integrals over $(d-1)$-dimensional interfaces, and a linear solve. The Hessian is $k\times k$; the high-dimensional difficulty is constructing and integrating the cells. Our SGD updates use sampled assignments at cost $O(Bkd)$, avoiding explicit cells. Sample-only or streaming access can also motivate SGD in low dimension. Calibration still estimates a Laplacian and its cost is counted. For 2D/3D Newton method comparison, we do not claim superiority there. SGD based algorithm has its advantage in its simplicity and scalability in high dimensions when maintaining the diagram and computing Hessian is difficult.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.