Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate

We sincerely thank the reviewer for their thoughtful and positive assessment of our work. We appreciate the recognition of the motivation and theoretical contributions in our paper.

Error bars in experiments. Thank you for pointing this out. We did look at the standard deviations (based on multiple runs of the SGD-based algorithms), and they are consistently small, especially for the averaged iterates and the OT map estimation, indicating low variance in the performance. We agree that showing this is important and will include error bars in the revised version to make this clearer to the reader.

Minor issues. We will correct the typo in the TL;DR , fix the BibTeX citation issue at line 146, and update the punctuation in Theorem 5.3. We will also make sure that the introduction of the MTW properties comes before they are first mentioned (currently line 82), to improve clarity. Thank you for catching these details.

Formatting. We will restore the checklist guidelines as required.

We sincerely thank the reviewer for their thoughtful, detailed, and constructive feedback. Your comments have been extremely helpful and have led us to significantly improve the clarity, rigor, and positioning of our paper. Your suggestions helped us identify several key areas requiring clarification, and we are confident that the revised version of the paper will be much stronger as a result.

We respond point by point below.

Questions

1. Positioning w.r.t. the existing literature: We understand the reviewer's concerns and will include a more thorough comparison with the literature, notably by highlighting the following points.

• Generalizing properties of semi-discrete OT to the non-compact case: In [5, 20], the authors present several properties of the semi-dual and semi-discrete OT, which we recall in Appendix B.1. In our work, we notably generalize these properties to the non-compact case for the quadratic cost.
• Giving the first minimax results for non-quadratic cost and non-compact case in semi-discrete OT, and moreover with an online/one-pass algorithm: In [29], the authors consider the estimation of the OT map from samples, but only in the compact case and for the quadratic cost. To achieve this, they show that the discrete entropic map, with regularization $\varepsilon \simeq 1/\sqrt{n}$, approximates the true OT map with an error of $\mathcal{O}(1/\sqrt{n})$. This entropic discrete map can be approximated arbitrarily closely using, for instance, the Sinkhorn algorithm. In our paper, we address OT map estimation for a broader class of cost functions, including non-quadratic costs and the non-compact setting. However, we assume full access to the discrete measure (one-sample setting), whereas their estimator achieves the same rate even when sub-sampling from $\nu$ (two-sample setting). A key strength of our estimator is its ability to operate in an online setting, without the need to store samples drawn from $\mu$, and to refine the estimate as more samples become available. While some of this information appears in lines 303–309, we will emphasize these differences more clearly in the revised version.
• Studying SGD algorithms for non regularized semi-discrete OT: In Taşkesen et al., the authors study regularized optimal transport in the semi-discrete setting, with a class of regularizers that notably includes entropic regularization. They provide convergence guarantees for the regularized objective function. In contrast, we focus on the non-regularized semi-discrete OT problem, and analyze the convergence of both the unregularized OT map and cost. We will incorporate a discussion of this work into the paragraph currently titled "Entropic regularization" (starting at line 124), which we will rename "Regularization of the semi-dual".

2. Lemma 3.1:
You are right, duality may fail without assumptions on the regularity of the cost. However, the existence of a minimizer in the stated set is still guaranteed, provided that (4) admits a minimizer. That said, we agree that minimizing (4) is not meaningful if there is a duality gap. We will therefore restate the theorem under the assumption that (3) is well-posed and that strong duality holds, as is the case when the cost is lower semi-continuous and bounded from below.

We will also add details after line 954, showing that $H$ is invariant under constant shifts of the potential.

3. A) Assumption B (non-compact case) We agree that Assumption B3 is new and somewhat technical. However, it is satisfied by common distributions such as the Normal distribution and the Student distribution with degrees of freedom $\nu > 2$. We will explain that it is necessary for the definition and regularity of the Hessian of the semi-dual. We will add an example in the appendix showing that if B3 fails, the Hessian may not be defined. This example uses a measure with a spiky density of the form

$

f_\mu(x) = \frac{1}{Z} \left[ \frac{1}{1 + |x|^4} + \sum_{k=1}^\infty k \cdot \mathbf{1}_{R_k}(x) \right]

$

where $R\_{k} := \{ (x\_1, x\_2) : |x\_1| \le \tfrac{1}{k^5},\; k \le x\_2 \le k+1 \}$ and $Z$ is the normalizing constant. A complete proof of this counter-example will be given in the appendix, and we will refer to it when introducing Assumption B.

B) (Theorem 5.3)

• This theorem states that even in the one-dimensional case, where the source measure $\nu$ is as simple as $\nu =\frac{1}{2}\delta_{\{0\}} + \frac{1}{2}\delta_{\{1\}}$, no estimator based on $n$ i.i.d. samples can achieve a convergence rate better than $\mathcal{O}(1/\sqrt{n})$ uniformly over all Lipschitz measures. Fixing the measure $\nu$ while considering a class of source measures is analogous to the minimax setting in [29, Proposition 1], where the roles are reversed: the source measure is fixed and a class of discrete target measures is considered.
• There is a typo in Appendix E concerning the proofs of the minimax lower bounds: we consistently refer to $\mathcal{P}\_{H}$ instead of $\mathcal{P}_{\mathrm{Lip}}$. We will correct this typo in the revised version and apologize for the inconvenience. We focused on Lipschitz measures to emphasize that even within this more regular class, the minimax rate remains the same. Since the class of measures with Lipschitz density is a subclass of those with $\alpha$-Hölder density for $\alpha \in (0,1]$, which we study in the paper, the lower bound extends to this broader class as well. We will clarify this point more explicitly in the revised version.
• The proof uses Le Cam’s two-point method. The idea is that to lower-bound the minimax risk, it suffices to construct a pair of distributions in the model class that are both hard to distinguish (in Hellinger distance) and induce notably different values of the quantity to be estimated. The lower bound obtained for this pair then extends to the entire class they belong to. In Appendix E.2, which contains the proof of Theorem 5.3, we consider a subclass of Lipschitz probability measures $\mu_\delta$, $\delta \geq 0$, and our analysis through (19) and (20) yields the lower bound

The goal of this inequality is to eliminate the dependence on $\mu$ in the norm $||\cdot||\_{L^{p}(\mu)}$ by replacing it with the fixed reference measure $\mathcal{U}(0,1)$ on the right-hand side. This allows us to treat $||\cdot||\_{L^p(\mathcal{U}(0,1))}$ as the loss function $l$ in the statement of Le Cam's Lemma (Lemma E.1). We then apply Le Cam’s two-point method to the pair $(\mu_0, \mu_\delta)$ and propagate the resulting lower bound to the full class. We will ensure that the proof is made more explicit and reader-friendly in the revised version.

4. Linear rate:
We apologize for any confusion. We referred to $\mathcal{O}(1/t)$ as a linear rate, which differs from the standard use of the term "linear" in the deterministic optimization literature, where it typically denotes exponential convergence. In the revised version, we will avoid using the term "linear rate" to describe $\mathcal{O}(1/t)$ convergence.

5. In Section 6, Fig. 3c, we believe that the small discrepancy comes from the fact that the errors $||\bar{\mathbf{g}}\_t - \mathbf{g}^{\*}||^2$ are already below $10^{-4}$. The target weights of $\nu$ (such that the randomly generated $\mathbf{g}^*$ is optimal) are approximated using a Monte Carlo estimator with $10^9$ samples. At that scale, the residual error in approximating the optimal weights contributes to the slightly less sharp convergence behavior observed in this plot. Indeed, the Monte Carlo error for each weight is expected to be on the order of $\mathcal{O}(1/\sqrt{N})$ with $N$ samples, and this propagates into the final error metric. To validate this hypothesis, we reran the experiments using $10^{11}$ samples for the Monte Carlo approximation. With this higher precision, the convergence plot aligned closely with the others, confirming our interpretation. We will update the figure to include the higher-precision results.

Minor comments

We agree with the minor comments and thank the reviewer for the detailed suggestions. We will correct the typos, notably by defining $\mathcal{H}^{d-1}$ as the $(d{-}1)$-dimensional Hausdorff measure in Proposition B.1, clarifying the use of seminorms, unifying the vector notation, and ensuring that all symbols and acronyms are properly defined.
We will also reorganize the appendix for clarity, fix formatting issues, ensure that each theorem has a dedicated proof with an explicit section title, and adjust incorrect indices or equations as pointed out.

We sincerely thank the reviewer for their constructive and positive feedback. Thank you for pointing out typos, we will correct them for the final version. We will address the specific questions and comments raised below.

1. Thank you for pointing out the algorithm described at the end of [1]. It is true that their method achieves linear computational complexity in the number of samples and could serve as an alternative to the Sinkhorn algorithm to obtain an efficient estimator in dimension 2, in the setting of Pooladian et al., i.e., for the quadratic cost with a compactly supported source measure. While the statistical/sample complexity remains the same as in Pooladian et al., their algorithm could offer faster runtime than Sinkhorn. We will make sure to cite this work in the revised version.

2. In our convergence analysis (Appendix C.2, see the equation after line 925), we show:

where $\lambda > 0$ is the smallest eigenvalue of the Hessian of $H$ at the optimum, characterizing the local strong convexity of $H$.

This was briefly noted between lines 271 and 274. While prior work has analyzed $\lambda$ in specific cases, it is known to depend on the structure of both $\mu$ and $\nu$. However, we do not currently have general estimates for its value, and obtaining such bounds remains a challenging and interesting direction for future research.

We agree that this aspect deserves more attention. After Theorem 4.5, we will clarify that although the convergence rate depends on $\lambda$, sharp bounds on its dependence (e.g., in terms of the number of points) are not yet available in full generality.

Nonetheless, combining this dependence with our stability results on Laguerre cells, we can derive,for instance, when $f\_\mu$ is $\alpha$-Hölder as in Corollary 2.2, a convergence of the OT map of $\mathcal{O}\left( \frac{M^2 }{\lambda\sqrt{n}} \right)$.

Although the dependence on $M$ that comes from our analysis is conservative, we will include and highlight this bound in the revised version.

My earlier comment lacked sufficient context. Here is what I intended:

In fully discrete settings, the combinatorial graph techniques of Gabow and Tarjan, (SICOMP 1989), yield an $n^{2.5} \log (1/\varepsilon)$-time algorithm. Lahn et al., (NeurIPS 2019) demonstrated that a mild modification of these techniques leads to a different trade-off between $n$ and $\varepsilon$, achieving a running time of $n^2 / \varepsilon$.

Analogously, although it would be non-trivial, the combinatorial framework introduced by Agarwal et al., NeurIPS 2024 might be adaptable to obtain a different trade-off between $d$ and $\varepsilon$, particularly under reasonable assumptions on the continuous distribution.

SGD-based algorithms are also of significant value, and understanding their behavior is an important contribution that this paper advances.

We thank the reviewer for the thoughtful and positive feedback. We respond below to the specific concerns raised.

Question 1: While the compact set $K$ is easy to find analytically when the density is known, we can always identify, with high probability, a ball $B(0,R)$ such that $\mu(B(0,R)) \geq 1 - \frac{1}{4}w_{\min}$, and therefore use the compact set $K = B(0,R)$, even when only samples from $\mu$ are available without any other information. Indeed, this collapses to a classical problem of estimating a one-dimensional quantile.
Write $X\sim\mu$ and define

where $F(r)=\mu(||X||\le r)$ is the cumulative distribution function of the scalar random variable $||X||$. Because we do not need the exact infimum, and any $R \geq R_\star$ provides a satisfactory $K = B(0,R)$, we estimate a slightly higher quantile.

Define the estimator

where $F_n(r)=\frac1n\sum_{i=1}^n \mathbf{1}_{\{||X_i||\le r\}}$ is the empirical CDF of $||X||$.

By the Dvoretzky–Kiefer–Wolfowitz inequality with Massart’s sharp constant [1,2],
choosing $\eta = \frac{1}{8}w_{\min}, n\ge\frac{\log(2/\delta)}{2\eta^{2}}$ ensures that, with probability at least $1-\delta$, we have $\mu\bigl(B(0,\widehat R_{\eta})\bigr)\ \ge\ 1-\tfrac14 w_{\min}$, which is a dimension‑free sample‑complexity bound.

We note that tighter bounds in terms of $\eta$ may be achievable, but we rely here on well-established classical results for clarity and generality.

We thank the reviewer for this important question. Due to space constraints, we will include the full argument and dimension-free sample complexity bound in the supplementary material, and add a concise summary in the main paper to clarify that such a compact set $K$ can always be estimated from samples with high probability.

Question 2: You are correct, the reference to $H$ appears to early and may cause confusion. We will revise the text to ensure $H$ is properly introduced before being used, in order to improve clarity.

Question 3 Thank you for pointing out the typos. We have corrected them in the revised version.

References

[1] Dvoretzky, A., Kiefer, J., & Wolfowitz, J. (1956). Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Annals of Mathematical Statistics, 27(3), 642–669.

[2] Massart, P. (1990). The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. Annals of Probability, 18(3), 1269–1283.