Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate
Authors: Ferdinand Genans
Antoine Godichon-Baggioni
François-Xavier Vialard
Olivier Wintenberger
Venue: NeurIPS 2025 spotlight ()
Keywords: Stochastic Optimization
Gradient Descent
Optimal Transport
Statistical estimation
Primary area: optimization
TL;DR: We investigate the convergence of SGD schemes to approximate the optimal transport map in the semi-discrete setting.

Abstract: We investigate the semi-discrete Optimal Transport (OT) problem, where a continuous source measure $\mu$ is transported to a discrete target measure $\nu$, with particular attention to the OT map approximation. In this setting, Stochastic Gradient Descent (SGD) based solvers have demonstrated strong empirical performance in recent machine learning applications, yet their theoretical guarantee to approximate the OT map is an open question. In this work, we answer it positively by providing both computational and statistical convergence guarantees of SGD. Specifically, we show that SGD methods can estimate the OT map with a minimax convergence rate of $\mathcal{O}(1/\sqrt{n})$, where $n$ is the number of samples drawn from $\mu$.  To establish this result, we study the averaged projected SGD algorithm, and identify a suitable projection set that contains a minimizer of the objective, even when the source measure is not compactly supported. Our analysis holds under mild assumptions on the source measure and applies to MTW cost functions,whic include $\|\cdot\|^p$ for $p \in (1, \infty)$. We finally provide numerical evidence for our theoretical results.

Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Rate
Ferdinand Genans Antoine Codichon-Baggion
François-Xavier Vialard Olivier Wintenberger's
Sorbonne Université, CNRS, LPSM
Université Gustave Fiffel, CNRS, LIGM2
Wolfgang Pauli Institute
(ferdinand, gewans-boitnnn....... antoine godi modichon__bee baahonnaaggion, olivier wwwvier..wnteeneeeee..eee....eee francois -xaiiissxavier... wtw.ooo--aiiii....aaaadde-----e vialard@u-pem.
aatoine.godichaee
Abstract
We investigate the semi-discrete Optimal Transport (OT) problem, where a contin- uous source measure μ is transported to discrete target measure 1/, with particular attention to the OT map approximation. In this setting, Stochastic Gradient Descent (SGD) based solvers have demonstrated strong empirical performance in recent machine learning applications, yet their theoretical guarantee approximate the OT map is an open question. In this work, we answer it positively by providing both computational and statistical convergence guarantees of SGD. Specifically, we show that SGD methods can estimate the OT map with minimax convergence rate of ((1/VT)), where ni the number of samples drawn from μ. To establish this result, we study the averaged projected SGD algorithm, and identify suitable projection set that contains minimizer of the objective, even when the source measure is not compactly supported. Our analysis holds under mild assumptions on the source measure and applies to MTW cost functions, which include for p oo). We finally provide numerical evidence for theoretical results.
Introduction
Optimal Transport (OT) has become a central tool in machine learning for comparing and manip- ulating probability measures. particularly important variant is the semi-discrete setting, where continuous source distribution is transported to a discrete target measure v. This formulation arises naturally in wide range of applications, including image processing [6 22,, statistics
[I] [8) and
generative modeling [4] 19, 24]. Its hybrid structure bridges the gap between fully continuous and
fully discrete formulations, allowing for expressive modeling while remaining more amenable to scalable numerical methods.
Despite its practical appeal, solving semi-discrete OT efficiently and reliably at scale remains challenging. Existing methods with convergence guarantees often require full knowledge of the source density and are typically confined low-dimensional settings. For instance, Newton-type methods (27 23, 21 and combinatorial [2] I methods have been developed and are provided with convergence rates guarantees. However, these techniques become impractical in high-dimensional settings, since they need full knowledge of the source measure, and employ constructions that suffer from the curse of dimensionality such as meshes representation of the source measure.
In high dimensional and/or when the source measure can only be accessed through samples, SGD and its variants have become a popular choice for solving semi-discrete OT, especially in applications such as generative modeling
These methods solve the semi-dual formulation of the OT
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

problem using only i..d. samples from μt and scale well to large data, not requiring to store samples. Yet, a fundamental theoretical gap remains: while SGD methods are widely used in practice, they lack convergence guarantees for approximating the OT map.
Providing convergence rates for SGD approximate the semi-discrete OT map is both computa- tional and a statistical problem, since using more gradient steps in SGD for the semi-discrete setting equivalent using more samples. From statistical point of view, recent work by Pooladian et al. 3I offers promising evidence for the convergence of SGD: they show that semi-discrete OT escapes the curse of dimensionality, unlike the continuous setting [1], and that a convergence rate of O(1/v with samples is achievable when the cost to move mass is the quadratic cost 21l ||2 and the source measure is compactly supported. Moreover, this rate is minimax optimal for estimating the OT map. While their approach requires solving discrete OT problem, i.e., first sampling points from js and then solving the corresponding empirical problem, their key result motivates studying SGD as a way to accurately estimate the OT map in an online setting, where the estimator is refined as more samples become available, without needing to store them, as often required in practice, for instance in generative modeling tasks
Taken together, these observations highlight two major open questions that are answered positively in this work:
(i) Can we establish convergence guarantees for SGD-based algorithms in the semi-discrete OT setting for OT map estimation, especially when only samples from f are available?
(ii) Can we obtain statistical guarantees for the estimation of OT quantities (e.g., cost, potential. map) beyond the compact and quadratic setting of Pooladian et al. [31
Contributions. We establish convergence guarantees for SGDDbased algorithms applied to the non- regularized semi-dual formulation of optimal transport. We focus our analysis on the convergence of the averaged Projected Stochastic Gradient Descent (PSGD) algorithm, relying on key result: the existence of a compact projection set C' (Lemma 3.1) that contains a minimizer of the semi-dual objective, even when the source measure le has unbounded support. To the best of our knowledge, this is the first time such projection set has been identified in the semi-discrete OT setting without assuming boundedness μ.. This projection set allows us derive key properties of the semi- dual functional. including global weak form of strong convexity on C in all our settings (Lemma 4.2). and to extend second-order regularity results that were previously known only the compact setting (Prop 1. such as local strong convexity near the optimum.
The convergence rates for OT quantities, obtained when samples are drawn from μ (equivalently, when PSGD is run for n iterations), answer the two questions posed in the introduction. These results summarized in Table [ Moreover,
show our convergence rate to the OT map is minimax optimal (Theorem 5.3), giving the first statistical guarantees in semi-discrete OT for MTW (defined in Section 2.1 and quadratic costs on unbounded support.
Table I: Summary of the convergence rate achieved by PSGD for the estimation of OT quantities
Costs
OT cost
OT potential
OT map
Non compact
MTW costs
(11/n) [Cor 4.6
((1nn) (Th 4.5
0(1 [Cor 5.2
No
Quadratic
(1/n)) [Cor
4.6
((1/)) 4Th 4.5
011
[Cor 5.2
Yes
All other costs
((1//)) [Th 3.2
No guarantees
No guarantee
Yes
2 Background
2.1 Optimal Transport
Considering a source and target probability measures μ E P(Rd) and v E P(RR), with a cost c: Rd x Idd + R to transfer mass, the OT problem is defined as:
(Tc(M)) = min [
Jgexze c(x, y)d y),
(1)
rell(p.v)
Noo necessarily defined.

---

where (1 2) := { E P(R" x RR); x(-xRR)= - ((-),, ((R x-) = x-)) is the set of joint prob- ability measures on Rd x IR with marginals and v.
In this article, we assume that l continuous, while the target measure takes the form V En wjd(g.), where w w= (W1, ...; WM) are its probability weights and (y1...., yM) its support. We mainly interested in OT problems where (I) has unique deterministic solution, which we refer to as the OT map. This holds under mild assumptions in our semi-discrete setting, as guaranteed by the generalized Brenier's Theorem.
(Generalized) Brenier's Theorem ((44. Th. 10.28). Suppose that I an absolutely continuous probability measure, and y is discrete. Then, if the cost e satisfies the MTW properties, as when c == || with p E (1, oo), and the OT cost in ① is finite then it admits, up to negligible sets, a unique solution of the form ((dr, dy) p(dx) (w)) v(z, v). where:
(x)
(f)
Tu is referred to as the OT map. Moreover, I is a solution of the dual problem of
① given by:
OT (U,( f(x)+(()) Sa(a.e) [ f(w)dp(a)+
[ Rd
g(y)du(y)
The semi-dual problem. The semi-dual formulation of is particularly useful in the semi-discrete setting and can be expressed as concave knite-dimension problem:
M
OT
max RERM
H(g) = (x)dd((())) +
W
(3)
JRd
where g (g1, .... 9M1), and for all Rd, the (vectorial) c-transform is defined gx)x)
min;e]1.M (o(r, M1) - 9i). For any the c-transform also defines the Laguerre cells Lj(g) for
j E [1.M] as
Lj(g) = (a X gx) c(2, v1) - 93}
Using this formulation and under Brenier's generalized theorem, the OT map can be described as (1r) x ((g*)((a)) x Yi for x inside (g"),,. where g", that refer the discrete
OT potential solves
MTW costs. For costs satisfying the Ma- Ma-Trudinger-Ve Wang properties, referred to as MTW costs, such as I|, p E (I, oo) or Bregman divergences d(x) o(y) (Ve(y), x-)) for strictly convex é, we observe improved properties for the function H in Specifically, the differential is defined almost everywhere, except on a j--negigibble set, and [1] proved that is even locally smooth and strongly convex on the orthogonal complement of 1. Moreover, all these costs satisfy Brenier's 's generalized theorem. For a detailed definition of such costs in the semi-discrete setting, see [1 or Appendix] A
2.2 Stochastic approach for the semi-dual problem.
In the semi-discrete setting. the semi-dual formulation is particularly appealing because, even when a continuous measure, it reduces to finite-dimensional problem. Efficient (quasi)-Newton schemes exist to solve this problem in low-dimensional settings when the density of μ is known (27 23 211.
In the more general scenario, where the dimension can be high and/or only sampled points from available, we reformulate the semi-dual OT problem convex expected minimization problem, defined as:
min(H(g) = Ex [h X) g E R-M)
where for all g E RR, E RR., h(g,+) = (c) - mygj- Note that we deliberately multiplied the semi-dual functional by -1 to frame as a convex minimization problem instead of a concave maximization problem; however, this is not a universal convention in the literature.
No matter the cost, H is subdifferentiable everywhere, and we consider the subdifferential (H(g)
Ex- (gg X)), where for x E E2d and j [[, MI.. we define:
0gh(g x) 1l LE))(()) Wy.
3

---

As long as is in the interior of Laguerre cell, this subdifferential 0H is, in fact, a differential that we note VH. Moreover, 0gh(g. X) is an unbiased estimator of (g). Given access samples from naturally leads to the study of stochastic gradient descent schemes of the form
ga ga-1 7r. 7,,0g/( X
where we start from initial point go E RR and at each iteration draw sample X,, and take gradient step with step size "/n > 0 (also referred to as the learning rate).
SGD algorithms are well-suited for this setting 4 9 24 as they adapt to the number of samples drawn, have linear (M) complexity per iteration, efficiently handle bini-batches through GPU parallelization, and do not require storing the drawn samples. Directly solving 4 also helps avoid discretization bias when estimating OT quantities 8 [7]. which can be crucial some applications of a
semi-discrete OT [9] However, the specific structure of the OT semi-dual problem makes analyzing the convergence of SGD algorithms particularly challenging. especially regarding convergence to the optimizer g". Unlike standard cases, it does not fall within the class of well-behaved problems, such as those that are globally strongly convex.
Regularization of the semi-dual. The idea of formulating the semi-dual OT problem as the minimization of an expectation and avoiding discretization by using SGD algorithms was introduced in [17]. However, possibly due to the lack of globally favorable properties of H, they propose using the entropy-rreullrrized version of H, referred to as the entropic semi-dual He, where is the regularization parameter. This results in a globally 1 1/E-smooth problem and as & vanishes, He converges to H. A broader class of regularizer was also introduced and studied in [33]. Unfortunately. the theoretical analysis of SGD algorithms for the regularized problem reveals prohibitive constants e-1 and higher [3 and even for the entropic regularizer 77.. making the use of a small e impractical for theoretical guarantees. Thus, avoiding both regularization and discretization bias to solve the semi- disireiseette problem highlights the relevance of studying SGD for the non regularulrr OT problem.
3 Projected Stochastic Gradient Descent on the Semi-Dual OT Problem
3.1 Localizing a projection set
In convex optimization, particularly in an online stochastic setting, localizing set to restrict the optimization domain and using a projection step in the gradient descent scheme can be very useful, permitting straight- forward convergence proofs (20]. Our first lemma addresses this idea in the context of the OT semi-dual problem, showing that even when the support of is not compact, it still possible to localize || || oo -bal within which a minimizer of the semi-dual function H exists. This projection set is formally defined in Lemma 3.1
Lemma 3.1 (Existence of a projection set), Suppose that the OT problem is well-posed, strong duality holds and 4 admits a minimum. Then, there exists a minimizer g" contained the set
C= {gE
|1, s [lellx,,)))
where [|]||,,00 == suPae Je[I, lo(r, U.)l I. for any compact K satisfying μ( 2 1 miny Wy-
While the existence of a lllo- was previously established under the assumption that the cost function is uniformly bounded on I& x IRd, or when both measures have bounded support, we extend this result to the more general semi-discrete setting. On own, this finding may enable further theoretical developments in semi-discrete OT, where bounded potential is often required 3 13].
-11z yl1 and v as discrete measure with 107 points in [0. 1]a and uniform weights. In this setting, it previously believed that the Brenier potential could not be bounded, since c is not bounded on I x [0, 1
Example 1. Consider y as the standard Gaussian on R3, the cost function
However, using Lemma 3.1 can take the ball (00, 6), which allows us restrict search for the potential within a T ball of radius 18.
Incorporating this projection step into our SGD scheme has several advantages: (i) significantly enhances both the practical performance and theoretical convergence of the algorithm; and (ii)

---

the computational complexity of the projection step is (MM), as it simply involves clipping each coordinate of the vector. The projector is defined
(g)je(g) ig RM M argmin - g gi EC.
Based on this projection step, we derive the PSGD algorithm to minimize H. as presented in Algorithm [ Note that, in practice, this requires knowledge of a compact set K, which we assume to be either given or previously estimated. The estimation for instance trivial when the source the standard Gaussian as in many applications (e.g- generative modeling). When the density is unknown, we can still have high probability guarantees as presented in the next paragraph.
Estimation of the projection set K. When the density of μ is unknown and we only have access to samples, we can, for instance, es- timate the projection set K using a centered ball B(0, R) such that, with high probabil- ity, p(, Rt)) 2 1- W This is for k = 1 to n do
Algorithm 1 Projected Stochastic Gradient De- scent (PSGD)
Parameters: ? > 0, 0 [ ()) Initialize go E C and go go
standard quantile estimation problem for the norm || where X ~ Hr, and the empiri- cal CDF (r) = 1
Draw
/ gi = Proje (gr #ggh(8 1,
+E Di= Iss. can serve as an estimator for R. Indeed, we can take R inf (r (r) > 1 $ [min) By the Dvoretzky-Kinn Kieee--ieee---aee Wolfowitz iequullity (26), for 32 logg(2/)) it holds with wa
3t = k+1 Bc A+1 Bx-1
end for return gn and B.
sample size 2
probability of at least 1- 5 that μ(B(0, R)) 2 1 - 1 Wmin This provides a dimension-fire sample- complexity bound for estimating K.
3.2 A first convergence of PSGD in the general setting
As a first consequence of our projection step, we can directly establish a convergence rate for PSGD on the OT cost in a general setting, without assuming additional regularity of the cost function or the source measure, The proof follows a classical result for PSGD algorithms, and our projection step provides insights into the choice of the learning rate 7/1 Additionally, allows us to recover the rate ((1/ /n) from [17] for the averaged iterates of SGD when applied to the entropy regularize semi-dual.
Theorem 3.2 (PSGD in the general setting). In the general setting, choosing the learning rale Tn n/n" with ? DiammC)/222 and 1/2, obtain
E [ (g.)) H (g") 4v2 (C)
Although most of our results focus on MTW costs, as discussed in the next section, also establish a convergence rate in a more general setting. This broader setting lies outside the scope of the generalized Brenier theorem and an OT map may not exist be unique. However, estimating the OT cost can still be useful in certain applications, such as when c = || |l. corresponding to the 1- 1-Wasserstein distance. Thanks our projection step, the same convergence rate carries over to other SGD-based methods, such as Adagrad [14, which is well-suited when the projection set is a hypereube 28 Section 4.2.4].
4
Convergence analysis of PSGD and minimax estimation for MTW costs
We now focus on costs satisfying the MTW properties, with particular attention to the cost c(x, y) = ||1 - y/12, as it is the most commonly used. For this cost, we extend our results to include non- compactly supported source measures. This setting is used, for instance, in 4 24), where a standard Gaussian mapped to discrete distribution. Our objective to establish the convergence rate of PSGD in approximating the true OT map and cost by estimating the Brenier potential g" We make the following assumptions, distinguishing between the compact case, where we treat MTW costs, and the non-compact case, where we focus solely the quadratic cost 1lll 1|2.
5

---

Assumption A (Compact case). The cost satisfies the MTW condition, Supp(H) is bounded and c-convex (see Appendix [ and μ satisfies weighted (1, 1) Poincaré- -iittigger inequality: there exists Cpw > such that for all f E C³ (IR),
|l B,IffI Cpwll [f
(PW)
Note that (PW) relates to the local strong convexity the semi-dual problem near the optimum and is common assumption in [2] []. Moreover, in the compact setting, the assumption that the density Jn is bounded from above and below by strictly positive values a common assumption, as in [31]. This compact assumption implies (PW).
Regarding the non-compact case, our assumptions are satisfied notably, for non-degenerate Gaussians, finite mixtures of non-degenerate Gaussians, and heavy-tailed distributions such as Student distribu- tions with degree of freedom larger than 2. While a broader class of MTW costs could potentially be covered, perhaps under stronger assumptions regarding the source measure, we deliberately omit these cases to avoid further technical complexity. Moreover, the best of our knowledge, even for the quadratic cost, there are no existing theoretical results in semi-discrete OT when the support of unbounded. We further provide in Appendix A an example where assumption (B3) fails and as consequence, the Hessian is not defined.
Assumption B (Non-compact case).
(B1) The cost is quadratic: c(ar,) 21100 ul12 and the measure y has finite second-order moment.
(B2) There exists compact set K C Rd with ((K) 1 Wiiis such that the probability measure μи with density fux (I) == cτ fx (x) (x) satisfies a (PW) inequality.
(B3) The density Jy satisfies the following integrability and regularity condition: for R > 1 and
r' 2 define
f = fç. 1 ||
fft²== ffp 1
Assume there exist R > C > 0 annd a modulus of continuity such that for all 5 0.
Σ
(8) Cw()),
I(R+r)--CRR < <0,
(5)
where Cfftt == suPrers f
fftt(z)) and w Rtr is the modulus of continuity of fltt..
4.1 Properties of the semi-dual H
In our context, it is known that the discrete Brenier potential g" E RM is unique only up to transformation of the form g* + al with E K. For clarity, we fix g' be the Brenier potential such that g* E Vect(1 Without losing information, we thus restrict our analysis to the orthogonal complement of the subspace spanned by the vector 1M, (ect(1ar) Therefore, for any we define
g. g' IR M
lgg g'll Projveet(] (g g')ll,
(g. g') (Projvect(1 w) (g), Proivect(M)) (g')
We start by stating the second-order regularity of H in our setting.
Proposition 4.1. Under Assumption A or the function H is differentiable everywhere R.M, and we denote its gradient by H.. Moreover, there exists a radius r > O such that on the ball B(g" r). H. is C2 and strongly convex on (gg", ,). If. in addition, Ju a-Hölder continuous with (0, 1]. then the Hessian of H is also a-Hölder continuous.
Naturally, the smallest eigenvalue of the Hessian O, with 1 as its eigenvector. However, we still refer to the strong convexity of H since we focus on the orthogonal complement of Vect(1), (1). Notably, we extended the definition of the Hessian, originally provided (2I for the compact case, to include the quadratic Euclidean cost in the non-compact setting. Furthermore, while the local strong convexity of H was established in 21 for the compact case, was defined over the set of vectors g such that the measures of all Laguerre cells are bounded by a positive constant. To formulate

---

this result with respect to a ball, we also required a result on the quantitative stability of the measures of Laguerre cells. Additional details on this quantitative stability will be provided in section (.1
As corollary of these results, we derive the following lemma, which stems from our projection step weak form of strong convexity of H on C, also referred to Restricted
and can be viewed Strong Convexity (RSC) (37].
Lemma 4.2. Under Assumptions or there exists 1j > such that satisfies a RSC property, uniformly for all g C:
(g) 8%) 7/1g g'l
Direct convergence guarantees under RSC. As a direct consequence of the RSC property C, Projected SGD achieves (1/nn) convergence for our OT problem when using the step size " "t¹ However, our analysis does not provide precise estimate of the parameter 1), which is required to effectively implement this learning rate in practice, and is particularly difficult to obtain in the OT setting. This limitation motivates the following section, where we study PSGD with learning rate of the form ?/8 = =1/tt for b < This variant achieves optimal convergence rates without requiring prior knowledge of 1/-
1
Remark 4.3. Since RSC implies the Quadratic Growth (QG) condition H(g) H(g") > n/lg g" 1 the same convergence guarantees also hold for other SGD variants that rely on either RSC or QG assumptions, such as S-Adagrad []0]
4.2 Convergence rate of PSGD
we derive the convergence rate of the non-averaged iterates of PSGD, which mirrors the convergence behavior observed in the strongly convex setting.
Convergence of the non-averaged iterates Building the RSC of H from Lemma 4.2
Theorem 4.4 (Non-averaged iterates). Under Assumptions Arr and for any decay schedule of the form in 7I/n with 7 > and E (1/2, 1), we have the convergence rate
E gg g. -
-g" -g"l()] O (1/n").
As approaches 1, we observe a nearly (1/nn) rate for the OT potential. In the next section, we further show that this convergence rate is achievable by the averaged iterates sequence 5,, and that it minimax optimal, highlighting the strong performance of PSGD.
Convergence of the averaged iterates In convex stochastic optimization, averaging the iterates of the SGD scheme is widely used technique, as it enables achieving optimal ((1/n) convergence rate for strongly convex functions without requiring knowledge the strong convexity parameter, and regardless of the decay scheme can adapt to the local strong convexity of the objective function, even when global strong convexity does not hold (5)
(1/2, 1) for the gradient steps [30 29]. Moreover, the averaged
Note that, as stated in Proposition 4.1 H locally strongly convex, and as stated after Lemma 4.2 the RSC parameter on C is unknown. These observations motivate the study of the averaged iterates of PSGD, and the next theorem confirms that these motivations hold true our setting. To establish this result, we also impose mild regularity condition on fy. requiring it to be a-Hölder continuous for some a E (0, 1].
Theorem 4.5 (Averaged iterates). Under Assumptions A B and assuming that fy. is a-Höller with
(0, 11, for any decay schedule of the form 7/n. = 71/r /n with 7 > 0 and (ata)) 1). noting the second smallest eigenvalue of H at the optimum, have the convergence rate
E B. g113
x²(n 11) + (1/n).
Without assuming fa be a-Hölder and for b (1/2, 1), we still obtain
Ellg. g" [l:] O (1/n").
7

---

As we can see, the convergence rate depends on the constant À > 0, which can be understood as the local strong convexity of at the optimum. Notably, there is existing literature on X for the entropy-regularized semi-dual problem when has bounded support ([13), Theorem 3.2, [ Proposition 5.1). These results can be extended estimate X, by letting the regularization parameter vanish.
4.2.1 Estimation of the OT cost
Building the convergence rate of PSGD, derive the corresponding for the OT cost. estimation.
Corollary 4.6. Under Assumption A or H is C² -smooth and uniformly bounded, so we have
H. (g) H(g)) - O (lg- -g''(").
Therefore, the Of cost exhibits the same convergence rate as the OT potential.
As we can see, this result establishes a (nearly) ((1/n) convergence rate for the estimation of the OT cost, matching the rate derived in Theorems 4.4 and 4.5 In particular, for MTW costs, faster convergence rate of (1/n)) is achievable, in contrast to the (11/vn) rate from Theorem 3.2 in the general setting.
5
OT cost and map estimation with PSGD
5.1 Minimax estimation of the OT map and Brenier potential
Having the convergence rate of PSGD to the Brenier potential g", we study here the convergence of the map estimate (g) : x x (z)(z). Note that, soon as there exists j [1] such that is in the interior of Lg(g") L, (g), we have
(x)(
(z) Vj-
Therefore, a result on the quantitative stability of the measure of Laguerre cells is sufficient to establish a convergence rate for the map estimator obtained from PSGD. Such result was previously established the compact case in (6. Here, we extend their result to the quadratic Euclidean in the non-compact setting, leading to the following theorem.
Theorem 5.1. Under Assumption A or the function g + (T() - -T.ulliaa is Lipschitz with respect to the infinity norm ||
||oo.
As corollary, we retrieve the convergence rate of our map estimator with PSGD. Corollary 5.2. Under the same assumptions as Theorem 4.4 taking En E {ggn }
(gg)) (x))) O (1/nb/2)
in addition, fp is a-Hölder with (0, taking E (T+ 1), have
E(l[T(g.) - T Tuælllzeu = (M²/>V/)
Note that our dependence on M might be conservative. However, we prove that the rate O(I/Vn) achieved by T Tgg,) ) is minimax optimal.
Theorem 5.3. Fixing c(x, y) +lIl== yl12 and v = + topt and noting (L) the set of probability measures on with Lipschitz densities, we have
inf T
sup (ig())))
En
( Ty,
21/Vm.
where the infimum is taken over all maps (()) constructed with the i.i.d samples of μ.
We recover the same minimax lower bound as in the two-sample setting considered in 31 where the target measure is also subsampled. This shows that, even though we have full information about the target measure, the asymptotic rates remain the same. However, we are able to achieve this rate in the non-batched setting, without the need calibrate regularization parameter as (31, or to know the number of samples in advance. Note also that a direct corollary of Theorem 5.3 and Theorem 5.1 is that the convergence rate (1/nn) for the estimation of the Brenier potential, achieved by the averaged iterates of PSGD, is also minimax optimal.

---

6 Numerical experiments
In this section, we numerically verify our convergence rate guarantees through various examples. All experiments demonstrating convergence rates were repeated 20 times, and the error plots represent the averaged errors. We set the learning rate to "11 = (C), as suggested by the analysis in Theorem 3.2 The step decay parameter b was set to 3/4, unless stated otherwise. We find that this learning rate leads to robust results without requiring further tuning. For each example, we generate g' randomly, and approximate the associated Laguerre cell measures (L,(gg)) )). We then fix w, = pu )). such that is optimal by the first-order condition. The Laguerre cells are estimated with 10 samples. All experiments were repeated 10 times, and the average performance was reported. We consider the following three settings to evaluate our method:
Example 1: Non-quadratic cost. The cost to move mass is set to || || We set μ as the uniform measure (0, 1/20) and take M = 50 points yl,.... yM uniformly in [0, 1|30. The projection set is then C = [-108/4 10$/4)50.
Example 2: Non-compact case. Here, μ has full support on R with cost c(z, y) 1 || y
We choose μ with density fx(x) & (1+ + -x=]))-d-,, satisfying (B1-3). As in Example 1, we sample M = 50 points in [0, 1]. The projection set C [-5, since K B(0, 1) satisfies Lemma 3.1
Example 3: Non-smooth source measure. We define with density (x) 12(2/z)1ze
inequality but is not a-Hölder. We took M = 10 points uniformly in [0, 1]. Since our results do not guarantee acceleration for non-Hölder densities, we set b = 0.9 for PSGD, as our analysis recommends close to for the best rate. The projection set is 1
which satisfies a (1, 1).oo))cccaré-
10
[x
[R
[s KT
18
g
10
12
12 3TR:
1/10
300
1000
50000
325
1000
12000
Isaration
Issration
(a) Example c= || 11
1
(b) Example 2: unhounded support
(c) Example 3: PW measure
Figure 1: Convergence rates of our OT potential and OT map estimators across different settings.
As illustrated in Figure I our theoretical claims are well supported by empirical results. (i) Our convergence guarantees are matched: PSGD exhibits the expected convergence behavior across all three settings. In particular, we observe a rate of (1/v/T)) in Examples I and 2, and rate of O11/n0445 in Example for estimating the OT map. The exponent 0.45 corresponds to b/2 with b = 0.9, which aligns with our theoretical guidance to select b close 1 when the source measure is not a-Hölder regular but still satisfies a (PW) condition. (ii) Averaging yields optimal rates: In Examples 1 and 2, averaging leads to the optimal rate ((1/v/) for the OT map without requiring b = 1. This confirms our theory, which remains robust to the choice of 71 > O and b E (1/2, 1), thanks averaging. for achieving this minimax rate. (iii) We achieve minimax rates across our settings: Our results match the minimax rate O(1 / (1))n) and extend the findings of [31], who established similar behavior in the compact case with quadratic cost. Importantly, we observe that the estimation of the OT map avoids the curse of dimensionality in both compact (MTW cost) and non-compact (quadratic cost) semi-discrete settings.
7 Conclusion and Discussion
We studied SGD-based solvers for the semi-discrete optimal transport (OT) problem, focusing on settings where only one few samples are available per iteration. These solvers are widely used in machine learning applications involving semi-discrete OT, yet their theoretical understanding remains incomplete. Our work bridges this gap by proving that such methods can consistently estimate both

---

the OT cost and the OT map across a broad class of settings, Focusing on PSGD, we established minimax-optimal rates for estimating the OT map under MTW-type costs on compact domains, and under the quadratic Huclidean cost on both compact and non-compact domains. These results rely on novel convergence guarantees and structural properties of the semi-dual OT functional, stemming from the projection set we introduced and the enhanced properties of H we obtained thanks to the restriction of our minimization space.
Future directions: exploiting RSC with adaptive meth- ods. Our analysis suggests promising avenue for future work: leveraging RSC to improve the performance of adaptive SGD methods such as using S-Adam [36] with projection for OT. While Adam is commonly used in semi- discrete OT (especially in generative modeling), often suffers from convergence plateaus due its fixed step size. In contrast, S- S-Adam incorporates a decaying learn- ing rate and is specifically tailored for strongly convex objectives. Despite lacking theoretical guarantees under RSC, our empirical results (Figure show that Projected S-Adam better exploits the local geometry of the semi- dual problem, outperforming Projected Adam practice. Formalizing these observations and extending our theory to include adaptive methods, while challenging, remains a compelling direction for future research.
10"
R.. PL,
10"
10
10
10"
1/n
10
16
10" Iterations
10"
Figure 2: S-Adam outperforms Adam on Ex. 1, avoiding convergence plateau.
8
Acknowledgements
The work of François-Xavins Vialard is partly supported by the Bézout Labex (New Monge Problems), funded by ANR, reference ANR-10-LABX-55
References
[1] P. Agarwal, S. Raghvendra, P. Shirzadian, and K. Yao. A combinatorial algorithm for the semi-discrete optimal transport problem. Advances in Neural Information Processing Systems, 37:25857-2558 -288777 2024.
[2] P. K. Agarwal, S. Raghvendra, P. Shirzadian, and K. Yao. Fast and accurate approximations of the optimal transport in semi-discrete and discrete settings. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4514-4529, SIAM, 2024.
[3] J. M. Altschuler, J. Weed, and A. J. Stromme. Asymptotics for semidiscrete entropic optimal transport. SIAM Journal on Mathematical Analysis. 54(2):1718 17411, 2022.
[4] D. An, Y. Guo, N. Lei. Z. Luo, S.-T. Yau, and X. Gu. Ae-ot: A new generative model based on extended semi-discrete optimal transport. ICLR 2020, 2019.
[5] F. Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. The Journal of Machine Learning Research, 15(1):595-622 2014.
[6] M. Bansil and J. Kitagawa. Quantitative stability in the geometry of semi-discrete optimal transport. International Mathematics Research Notices, 2025(10))35447738 2022.
[7] B. Bercu and J. Bigot. Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures. Annals of Statisties, 49(2): 968-987, 2021.
[8] L. Bottou and O. Bousquet. The tradeoffs of large scale learning. Advances in neural information processing systems, 20, 2007.
[9] Y. Chen, M. Telgarsky, C. Zhang, B. Bailey, D. Hsu, and J. Peng. A gradual, semi remi-discrete approach to generative network training via explicit wasserstein minimization. In International Conference on Machine Learning, pages 1071-1080. PMLR, 2019.
[10] Z. Chen, Xu, F. Chen, and T. Yang. Sadagrad: Strongly adaptive stochastic gradient methods.
In International Conference on Machine Learning, pages 913-921. PMLR, 2018.
10

---

[11] V. Chermozhukov, A. Galichon, M. Hallin, and M. Henry. Monge kantoroiio depth, quantiles, ranks and signs. The Annals of Statistics, 45(1):223 256.-255,111 2017.
[12] L. Chizat, A. Delalande, and T. Vaškevičius. Sharper exponential convergence rates for sinkhorn's &s algorithm in continuous settings. arXiv preprint arXiv:2407.01202 2024.
[13] A. Delalande. Nearly tight convergence bounds for semi-discrete entropic optimal transport. In International Conference On Artificial Intelligence And Statistics, pages 1619-1642, 2022.
[14] Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[15] N. Fournier and A. Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3):707-338, 2015.
[16] B. Galerne, A. Leclaire, and Rabin. A texture synthesis model based on semi-discrete optimal transport in patch space. SIAM Journal on Imaging Sciences, 1 (44):2456-249)) 2018.
[17] A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic optimization for large-scale optimal transport. In Advances In Neural Information Processing Systems, volume 29, 2016.
[18] Ghosal and B. Sen. Multivariate ranks and quantiles using optimal transport: Consistency, rates and nonparametric testing. The Annals of Statistics, 50(2):1012-1037, 2022.
[19] A. Godichon and B. Portier. An averaged projected robbins-monro algorithm for estimating the parameters of truncated spherical distribution. Electronic Journal of Statistics, 11(1):
1890-1927, 2017.
[20] E. Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[21] Kitagawa, Q. Mérigot, and B. Thibert. Convergence of a newton algorithm for semi-discrete optimal transport. Journal of the Europeun Muthematical Society, 2109):200322551, 2019.
[22] A. Leclaire and J. Rabin. A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer. Journal of Mathematical Imaging and Vision, 63(2):282-308, 2021.
[23] B. Lévy. A numerical algorithm for l2 semi-discrete optimal transport in 3d. ESAIM: Mathe- matical Modelling and Numerical Analysis, 49(6):1693-111) 1693-1715, 2015.
[24] 7. Li, S. Li, Z. Wang, N. Lei, 7.. Luo, and D. X. Gu. Dpm-ot: a new diffusion probabilistic model based on optimal transport. In Proceedings of the ieee/cvf international conference on computer vision, pages 22624-22633, 2023.
[25] X.-N. Ma, N. S. Trudinger, and X.-J Wang. Regularity of potential functions of the optimal transportation problem. Archive for rational mechanics and analysis, 177:151-183, 2005.
[26] P. Massart. The tight constant in the dvoretzss--iiffer-woloww inequality. The annals of Probability, pages 1269-1283, 1990.
[27] Q. Mérigot. A multiscale approach to optimal transport. In Computer Graphics Forum, volume 30, pages 1583-1592. Wiley Online Library, 2011.
[28] F. Orabona. A modern introduction to online learning, arXiv preprint 1rXiv:1912.13213. 2019.
[29] M. Pelletier. Asymptotic almost sure efficiency of averaged stochastic algorithms. SIAM Journal
on Control and Optimization, 39(1):9-72, 2000.
[30] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, (0(4))838-855. 1992.
[31] A.-A. Pooladian, V. Divol, and J. Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In International Conference on Machine Learning, pages 28128-28150. PMLR, 2023.
[32] F. Santambrogio. Optimal transport for applied mathematicians. Progress in nonlinear differen- tial equations and their applications. Birkhauser, edition, Oct. 2015.
[33] B. Taşkesen, S. Shafieezadeh- baaieraddhh--aahh.... and Kuhn. Semi-discrete optimal transport: Hardness, regularization and numerical solution. Mathematical Programming, 1933)):003-1106 2023.
[34] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
11

---

[35] M. J. Wainwright. High-dimensional statistics: A non-asympiotie viewpoint, volume 48. Cambridge university press, 2019.
[36] G. Wang, S. Lu, W. Tu, and L. Zhang. Sadam: variant of adam for strongly convex functions. arXiv preprini arXiv: /905009957 2019.
[37] H. Zhang and Cheng. Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimization. Optimization Letters, 9:961-979, 2015.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Proofs and numerical experiments are given for all the claims made in the abstract and the introduction.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper clearly outlines its main limitations, including the underlying assumptions and the reliance on specific parameters, ensuring that the scope and constraints of the proposed approach transparent the reader.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All assumptions are explicitly stated, and detailed proofs for each result are provided in the appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All experimental settings are clearly specified, and the parameters of our algorithm are provided.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All the code reproduce our experiments provided and attached in the supplementary materials.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the parameters in each numerical experiment are explicitly provided.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All the experiments are several times, and the error plots represent the average error across the experiments.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
13

---

Answer: [Yes]
Justification: All our experiments can run on any modern computer, even without needing
GPU.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://pppp.aaa........oooo///aa
Answer: [Yes]
Justification: The authors have read the NeurIPS Code of Ethics and guarantee that the paper conforms
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The code provided is original and included for reproducibility under the correct license.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The algorithms and experiments are clearly explained in the paper, and the code to reproduce the experiments is provided in an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
14

---

Appendix
Table of Contents
Further details Assumptions
15
A.1 The Ma- Trundinger Wang Properties
15
A.2 The Poincaré Wirtinger Inequality
15
B Properties of the semi-discrete OT problem
15
Known results the compact case
New properties
non-compacl case with the quadratic Euclidean cost
B.2.1
Defnnttin and regularity of the Hessian
17
B.2.2
Local strong convexity with respect the of Laguerre cells
21
B.2.3
Quantitative stability of the Laguerre cells
21
B.3
New properties in both our compact and non compact settings
23
Proofs the convergence rates of PSGD
24
convergence rates MTW costs
C.I.I
Convergence the non averaged iterates.
24
C.1.2 Convergence for higher order moments of the non-averaged iterates.
24
Convergence of the averaged iterates.
26
Convergence rate of PSGD in the general setting
29
D Proof of 3.1ma Localisation of a projection set
30
E Minimax estimation OT quantities
31
F.1 Kantorovich potential
31
E.2 OT map
32
F
Technical Lemmas
33
Technical Lemmas for Appendix B
33
F2 Technical Lemmas for Appendix
35
15

---

Notations
: The R \ (0) (i.e., real numbers excluding zero).
||- ||: The Euclidean norm. item Aga: The Lebesgue measure on R
Diameter: For C C Rdd define its diameter
De == sup x- - vll 1, EC,
Hausdorff measure: in Red, for S d, H. refers to the c-dimensional Hausdorff measure.
Indicator function: For set A C Rd (x)x) is defined as A 1 if A, and (x) = otherwise.
Component-wis wise Minimum: For u E Rd: Umin = min miinsssd'l
Special Vectors:
-1 (1, 1) E RM
O0s (o..... 0) M
0j E CRM, for any 1 I S M,is the vector with zeros except for the j-th entry, which is equal 1.
Probability Measures:
-((RR): The set of probability measures on Id.
-
For E P(RR), Supp(p) denotes its support.
Asymptotic Orders:
- --) and o(-): Standard approximation orders.
9 means there exists constant C' > 0 such that f(-) S Cg(-).
= b means both a S b and b S a.
Filtration: We denote by Fr the filtration generated by the sample X1, Xn iid
μ1, i.e.
Fn = (Xi,.... Xn),
Sets:
For any E 0, define:
Kg :g== Vi [ 2 2
Define:
k= (ge Vie [1. (L. 0.
Density of an Absolutely Continuous Measure: For an absolutely continuous measure on Rdd we denote its density w.r.t. the Lebesgue measure by fp.
Orthogonal of Vect(1):
For any g, g' R we define:
lg g'll. = |Proj (g - (g' 1??.
Inner product in this space:
(g.g), (Proj (g), Proj (g)).
Strong Convexity: We discuss the strong convexity of the semi-dual function when the strong convexity holds the orthogonal complement of 1.
16

---

A Further details on our Assumptions
A.1 The Ma-Trundinger-Warnn Properties
In the semi-discrete setting, the class of cost functions verifying the Ma-Trudinger-Waan (MTW)
properties (25 is defined the set of cost functions satisfying the following conditions: (Reg),
(Twist), and Loeper's s condition (QC) detailed below.
(++3))) E (Supp(())) Vi (I, Vac y4) Vae (z, (z,y)). Vz Supp(u), +
(Reg)
(Twist)
Definition A.1 (Loeper's condition). We say e satisfies Loeper's condition if, for each
{I...., M. there exists a convex set X; C I2d and a C² diffeomorphism exp X; + Supp(u) such that
V E RR 1iskis M, f -dexp(( - ve) + (()xp(()) u) S t) is convex.
(QC)
Definition A.2 (c-convexity). We say that X C R is c-convex if (exp?) (X) is convex set for every i N1.
For detailed discussion on this class of cost functions and their implications in the semi-discrete optimal transport framework, we refer the reader Section 1.5 of [2]
A.2 The Poincaré- Poincaré-Wirtinger Inequality
probability measure p w(xr) de on domain ? c
IRd said to satisfy the weighted
inequality (PW) if
/ (IVS) AA cf)
Epllld S Crw 2
Jn
The existence of a finite constant Crw provides quantitative connectedness of the source measure and is necessary for H be locally strongly convex. We provide here two examples of measures satisfying (PW). Notably, Example shows that oendeegnerate Gaussians, mixture of non-degenen -en-degeeee Gaussians and Student distributions satisfy (PW), when we take their restrictions on any ball (0,, R), R 0.
Example 2. (bounded support, density bounded above and below) Let Ω be bounded, connected, a-Holder with E (0, 1], and assume 0 < I w(x) < M < oo almost everywhere.
Note that the assumption of the support being bounded from above and below classical in the semi-discrete OT literature, as in [13 31
Example 3. (Annular support with radial concave profile, (21). Proposition A.1)) Let <r R. and let p E C ( R)) be a nonnegative function such that p(s) 0 for s E [0, and is concave on [r. R). with
[ p(s) ds = 1.
Define the probability measure p on the annulus == B(0, R)) c Rd by
p(z) | W p(1==1))
where wa-1 denotes the surface volume of the unit sphere gd-1, Then p satisfies the weighted Poincaré -irttnggerr inequality for some positive constant.
B Properties of the semi-discrete OT problem
Regularity properties of H
In the main article, we concisely presented the regularity properties of the function this section, we provide more detailed breakdown of these properties, organizing them into sub-properties and referring to the corresponding proofs the quadratic case with unbounded support (assumptions B1-B3).
17

---

Differentiability: The function H is differentiable on the entire space IM, and we denote gradient by VH (see Proposition
Local C2 regularity: There exists radius r such that H is twice continuously differentiable (C²) on the ball (gg". r)) (see Proposition B.5).
Local strong convexity: The function H is strongly convex on the ball Bg",, ,)) (see Proposition B.12).
Hölder continuity of the Hessian: If the density fy is a-Hölder continuous for some a E (0, 1]. then the Hessian H inherits this regularity and is also a-Hölder continuous (see Corollary B.II).
B.1 Known results in the compact case
In this section, we recall known properties of the semi-dual semi-discrete problem when the support of the source measure z is e-convex and contained within compact set and is cost satisfying the MTW properties. We will then extend these results to the non-compact case for the quadratic cost.
Here, we fix 0 and recall that Kg {g RM Vi M,, (g) 2 =).. The two theorems presented below are taken from [21] and have been adapted to our notation. We emphasize that the authors of [2I] considered the semi-dual OT problem concave problem, studying the objective function H instead H under their notation. For a better understanding of the constants in their theorems, refer the reader to their article.
Proposition B.1 (Theorem 1.1 in 121). Let be an absolutely continuous density with bounded support included in IR,, then the functional H C smooth, its gradient is given by
VH(g): (g)) wt
and its Hessian by
fa(x) H(g(g) J llu. uyl
()
dx)
H2H(g) Σ H
Proposition B.2 (Theorem 5.1 in 21 Under the assumption (AI), that satisfies a weighted (..))-Poincréé-irrtin inequality, there exists constant X such that for any g E K the second smallest eigenvalue of 2 (g)), denoted X2 (2 Hg)), satisfies
2
d2 ( ( > X.
H(g))
That is, H strongly convex on Ke, considering the problem on 1 Theorem B.3 (Theorem 1.3 in 21)). 1f has its density fy in (S.((Sup(()), Then, the functional H is 22.a on the set
Kg = (g E RM Vi, ARM,, (Li(g)) > >c)
Lastly, we state a result concerning the quantitative stability Laguerre cells, as presented [6] Lemma B.4 (Lemma 5.5 in 66) Under the same assumptions as in Proposition B.2 for g. g.g' e R we have
(L) (g)))) S M - g'lloe. Vi E [1.M]
Once again, we refer for more detailed understanding of the constant involved in this lemma.
B.2 New properties for the non-compact case with the quadratic Fuclidean cost
In this section, we give second order properties of the semi-dual when the source measure is not supported on compact. In the compact case, this properties are already known as discussed in Appendix B.]
18

---

For the reader's convenience, we recall the Assumptions that we made for the non-compact case.
Assumption (Non-compact case) (B1) The cost is quadratic: c(x, y) has a finite second-order moment.
v|l and the measure
(B2) There exists compact set K C. dd with p( 2 1- Fwmin such that the probability measure
μK with density fux (x) = cK f fx) (x)1x(z) satisfies a Poincaré- Wirtinger inequality.
(B3) The density fu satisfies the following integrability and regularity condition: for R > 1 and
r 2 define
f = fr. |
f+t=: := fF 1 1R ( =)
Assume there exist C > 0 and a modulus of continuity w such that for all > 0.
2 ( rR+ w (8) Cw(().
E(
co.
(6)
fx
where Ch suPpER (x+ and w/
R+r is the modulus of continuity of f# fitt..
Additional notation. Since here the cost is fixed, we define the Laguerre cells by L,(g) instead of Lg(g).
B.2.1 Definition and regularity of the Hessian
Proposition B.5. Under Assumptions (BI) and (B3), the semi-dual H is differentiable everywhere, and its gradient is given by
(g)) (g)) wi
Moreover H is C2 smooth on Kwman/ /2 nc and its Hessian is given by
(gg(g); = 1
(,(R))L l1 fa(x) dup
(i
(x))
my
H'H(g) =- EVHH())
Proof. Definition of the gradient. The proof follows the lines of the proof of Theorem 4.1 of 21 and extend this result the non-compact case. If is in the interior of Laguerre cell L, we have
hg x) = i=j
where we recall that h(g, .) = (x) ΣM Wygs. Since the boundaries of the Laguerre cells are defined by the intersections of M hyperplanes, they form negligible set with respect to the measure μ.. As a result, the gradient definition of H follows immediately.
Definition of the Hessian. Fix i E [1, MJ. We aim to prove the differentiability of the measure (g)( with respect to gj and that its differential is defined by:
(L.().))
f Li)nn, (g) 11 - 1,ll (p)).(g)
fa(x)
d7l d (x), jt1,
0g,
(H(L,(g)
0g;
0gi
This gives us exactly the line
V (g) of the Hessian.
Suppose * j.
1111 gi + Ij. note that we have Suppose > 0. Defining h,((x) b/10 1il12 1|
x0, 0)). L,(g) = n 4
We also have L, (g+ge;) = L,(g)) (u(g)\(Negssae (n 0) (1-5, 0)) Note that h is Lipschitz and for all Vh(z)]I |1 vill. Morcover, under assumption (B3), use Lemma F2
19

---

which states that for all hyperplane H, JH fadHt- 2 1. Therefore, we can apply the coarea formula pass from the second to the third equality below,
(L.(g de;)) - (((L( 1 (Nuys oo, 0J) n nh (l-8,0))
- =m(L;(g))
In (r(x)d
fu(x) (x)"='(x)dt.
= =](L(g))
Meas - (1l ((r)) 18 will
By analogy, for 8 2 we have:
[g deş) (T)(g) ( (Nizs x0, 0)) hTj (1 (1-,,0]))
Using the coarea formula gives:
# (L, + de,)) = ((L((g)) + J ( 00,0000),,, - |1: - y.1l
fx( dHH
Applying Lemma B.6, which stated and proved later in the appendice, the integrand defined above is continuous on K /ggin/ and justify the limit 12 NC. As a consequence, we can apply the Fundamental Theorem of Calculus
lim (g + ōe,)) (().
S (000:))0000000)))) ((0))
(x(
dH (x)
|uyj 3ill
By symmetry
u(L;(g de;)) u(L,(g))
lim
J 00000/700000000000 000,0)) (10))
fu(x)
d
8-0
1 - yil
Since
M sk 0 00, 0)) n () ({0)) T+(g) (ggg))) we thus obtain
F (g)( = Op(L,(g))
fz(x) d (x)), jti.
Og, (1(())))))))) 11:: w
Suppose i = j. No matter g RM the Laguerre cells verifies μ (U:l)y(g) m(R*) 1. Therefore,
a
à = 0. (g)
Ōgj i=1
Og, (L)
This equality gives Bag
a (L)(g)) Eiss
Bag
Lemma B.6. Under assumption (BI) and (B3), for any E K Kumin/2 CC the function Fj, defined for all t TR. as
Fj, (t) = (.at))=S(raaaa -
fu(x) d= (x)
(- ((t)) |/v will
admits as modulus of continuity in some neighborhood of (0).
Proof of Lemma B.6 We keep the same notation as in 211. Restricting ourselves to the quadratic
cost, we get
End Eww
min y/ Mj 1#j
C O(R),
Ceep = O(1),
Coand 0(1),
Cast 0(1)
In order to apply the results in 21), we need to extend Proposition 4.5 to measures with unbounded support in the case of the quadratic cost. We prove the following result:
20

---

Proposition B.7. Consider Ke = E [ =, 1,... M) for some > O sufficiently small and let C be the compact set of the projection. Then, there exists a positive constant 81, such that for all E Ke NC and all E Rdd such that there exist i + for which clp, yc) cup. = 9i 9o and clp. Uj) Uo) = 9j 9o, then
(1 yo, Mú - y0)
2
- 1 87.
U/ Yo |ll
vol
Remark B.8. Note that the transversality equation 7 is independent of p E Rd. However, p still involved in the transversaiity condition by the value of the difference of the costs.
Proof. Fix an index i. The of points p E R such that c(p, vi) c(p yu) 9t 9u defines hyperplane in Rd. The intersection of two such hyperplanes, denoted Hiy(g), is, unless the hyperplanes are parallel, codimension-2 affine subspace of Rd.
For each such (g), let d: (g) TRd be the orthogonal projection of the origin 022 onto (1)())-
Since the vector of potentials (g: (.... is bounded due to the projection set C, the set
(diz (g) + j admissible, and g E Kee nc}
is contained in ball B(0, R - 1) for some sufficiently large R >> 0.
Hence, for every g E Kg NC and every admissible pair (i, there exists point p E Hg)(g) lying in the interior of the ball B(0, Rt.
We now apply the transversality result from 21 to the measure
PR ()) ((B(O,R))
which is the normalized restriction of to B(0, R). This result guarantees transversality of the hyperplanes Hij associated with potentials the set K22 (defined analogously for PR and some > over the whole space Rd
Choose such that u(B(0, Rt) 2 1 8/2. Then it is sufficient to take
e/2 e' = 1- E/2
since one can check that K, C Ky,,. This completes the proof.
We aim to use the transversality result of Kitagawa et al. on decomposition of IRd into balls centered O. To this goal, we now prove a transversality result the boundary of ( R) uniform for R sufficiently large.
Proposition B.9. Consider K. = [g e ( > = M) for some e > O sufficiently small and let C be the compact of the projection. Then, for any positive constant 82 there exists R sufficiently large such that for all g E Kr Nc and all p E Rdd if there exists such that cpp, yi) c(p, vo) = gi go some p ( R), then
P
y: 3/0
(8)
1pll
1 voll
Proof. Rewrite the condition c(p, wi) c(p, yo) |pl| we get
9i 90 as (p, y0) gi -9o. dividing by
9. 90 |pl
|p] 90
The right hand side tends to uniformly with R since gi - go lies in a compact set. The conclusion follows directly.
21

---

The rest of the proof follows the lines of the proofs Appendix B of [2]] with = d1 as in Proposition B.7] From Proposition B.9 applied 82 ò1 there exists R > such as the transversality condition on the boundary 8 holds for every B(0. R + r) and the same 61 for every 2 0. Let us fix such R > 1 so that Assumption is also satisfied.
The next step is to decompose the integral using a partition of unity. We define the sequence of functions (P7))22 by
[ (R ||]]] A1, [[|=]] - (R ++ 2))+ A (R 1 -1=1)
if 0, i 2 1,
(x)
x E Rd
An illustration of the functions (x) defined above is shown below:
(x)
Partition of Unity Functions yor (r)
Pu
P2
P4
||=|||
R+1 R+2
n+
By definition, Ere0 p(x) 1, for all Rd. and every frr is supported on {R - ||>|| 1
R+r) for every r I. Po being supported by (0, R). Moreover yr Lipschitz continuous and we denote wip its modulus of continuity on its support. The moduli of continuity satisfy wip, (6) S 1
5 > 0r 2 0. Then, writing St,jt
Ck co, Oh (ft}) for conciseness, we decompose
the integral
fx(2)
DC
(x())(())
dH (x)
Σ r=U
(
(10)
Siiee
11y - yal
11y - 9il
We apply Proposition B.1 of [21 to each term of the decomposition. We recall below his crucial result, tracking the order of the constants established by [21].
Proposition B.10. Let a be a continuous non non-negative function on B(0, R) bounded by d and with modulus of continuity war Let the functions hig satisfy the transversality conditions 7 and with the same constant Etr > 0. Then
(x)
(t)
d7c
Teessht (14) 11l, will
has modulus of continuity
Wh,, (5) = (C26) C3|8
where C1 = -OB(C R))), Hd (BB(O, R)) = O(RR-1), C2 = 0 = -(1) and
C3 O C(d, 2R), + Hd Hd (BB(O, R))), where 2(),2R) defined in (3.5) of (21) satisfies
C(d, (R) 1
When applying Proposition B.10 to the continuous function o R+r = f (x) we easily
estimate o ft+ <CRtr and Rt I Bet + +0p
+CRtT Wop. Using that Wip (8) |8] obtain:
Wh Rir (0) = ((R + +)) (()
(((T)(()))) + +
uniformly for every g E Ke n C neighborhood of (0}. Noticing that this neighborhood depends solely on the transversality properties that are common to every r 2 and since
WF
Wh B+r
+00
from the decomposition in (10) the desired result follows under the assumption in (5). Corollary B.11. Under Assumptions (BI) and (B3), if moreover Jp is o-Hööler with E (0, 1), then the Hessian of the semi-dual H is also HöHööl K Kwman/ /2 O C.
22

---

Proof. Since f/ is a- cö-Höleer, the function fR with r 2 0 are also a- a-Hölder and we note ff R+r
R+r 8 applying Proposition B.10 ffu
Wh R+r (8)0 +1++) W R+T (0(1))
= O +
0(1)0' ((R+)))==(((())0))0000
By the summability conditions of assumption (B3), for some constants C1, C2 > 0, we have
wF
Wh Rtr r
0(1)8
R+r )(
r20
r20
0 + C28,
Applying Proposition B.3 [2 under our hypothesis shows that for g.g's E K w 2 C, there
exists constant C depending on Eor and fo such that have
( (²H(g') wr,, (llg 8'llo) + Cllg g'll
which gives the a- a-Hölder regularity since wr, I C18º + C25.
B.2.2 Local strong convexity with respect to the mass of Laguerre cells
Proposition B.12. Under Assumptions (BI-B3) H is strongly convex on K wainn
Proof. Recall K C Rd the compact set such that μ(K) > measure with density defined by fux (x) (=)) with eк [1. satisfies weighted Poincaré- Poincaré-Wirtngerr incquality.
1 #mmin and μk. the probability
We thus can use Proposition on Vect, on the set
B.2 which states that the semi-dual between pn and v is strongly-convex
KR Wain
AEER vi e MI.MM,,ILLL" 2 Wmin
This gives us that, for any g KR Whit there exists A 0, lower bounding the second smallest.
value of the semi-dual funetion between Pæ and v. This also gives us that for any g KR the second smallest eigenvalue of the matrix B defined by
Big = - f (1(8))
f (L))1B(..)( d
(i 5)
11 D3
Bü = Σ Bij
lower bounded by AK/OR 2 >x/2 0.
Since for any g. and i + j. (g < Bij and that both Hg) and are Laplacian matrices, we apply Lemma F.1 to obtain that the second smallest eigenvalue of the hessian 4 is lower bounded by XR/CR on KR
T Wmin
For any E K wminn/2 we thus have for all i E [1, n B(0, (Q) 2 Wmin- That is. K
2 Wannn C K R
which completes the proof.
$ Wiinn"
B.2.3 Quantitative stability of the Laguerre cells
Lemma B.13. Under Assumptions (B1-B3), we have
m(Li(g) (g()))) & M lg - g'lloo
Wi [L,M]
23

---

Proof. For all E [1, if r is in the interior of (g), we have
Vg((x) V/j
(11)
Therefore, given g, g'g' E RM, if there exists j [1] such that is the interior of L,(g) n L, (g') we have
V(g)
Moreover, since the support of is finite, we have
sup
Vg (gg')
max 11 Usll (#)
=E
Hence, to bound the enror of (g) bound the difference of measure of Laguerre cells made by and More generally, we now proceed here to bound the difference of measure of Laguerre cells between g, g' R fixed arbitrarily.
(z) and T Jr,.
(x)),, we just need to
Our proof will follow some arguments from [2T] Let us fix E [1. M] and suppose x E L4 (g)
L,, (g'). The definition of the Laguerre cells implies that there is a k: & i such that e (x, yk. Bi.
e (3r, vi) + g while (x, yi) + gi I c (2. yv) + gt. Combining these two inequalities yields
g g < c( ya) - c cx, S ge gi.
Hence, writing fx((x) = c (r, v/) (z, Uke) we have
L, (g) LL, (g') U
fix
(lgk
g% gk -g/))
(12)
kii
We now now bound y (frr) ((g) g: gx|)) using the coarea formula, using that for all x,
| (x)]]] = I1ye yull:
-mod(aa) ((a,6)) du(x)
I
1.a Jistten [V)(() ((x) (x))d
1. S1 ((e) 11l. yv ( (z)dt.
Observe that for the quadratic cost, fan (x) (z, ys Md + 11 1y 12 and so fū ((t)) xx Rdd (1r, yik vi) 1 (llvv 1|2 + 1))) and is therefore hyperplane. Applying Lemma
F2 there exists a constant C such that, for any k and f, we have
f Sasaan 11i. vkll (())) (c) s
Therefore, we have
(fāl ([a, (()) < 1 11 ykl
C
S (b - a)
11::
ykll
Since g:: gi (g) g() 2 g'll bor by combining the above with 12 we conclude
(L L, (g)) Σ p (fit (lgk g gb -gl)) < [g golooo
(13)
24

---

B.3 New properties in both our compact and non compact settings
Theorem 5.1
Under Assumptions (A1) or (B1-3), the function g - - (li is Lipschitz
with respect to the infinity norm || llae. Moreover, the Lipschitz constant grows at most quadratically in M.
Proof. Using that no matter g E RR- for any a E Rd
0
i E (g(") n Li(g) for a certain E M]],
[Tp."(")) - Tu. I
maxx/) I1 Usll
else,
and that for any g, g' E R, we have (g) (g)g)) S Mllg g'll using Proposition B.4 the compact case, or Proposition B.13 we have for any E (0)
/ (g)
(g") Tu, (B)
T (n.
M
Li(g")
max 18 dd((x)
L:(g))(21())
1=1
Σ max 11 (L (g)
(f)
< M gll oo:
where we used ((L,(g) (T(gg)) S |g g"ll for the last line.
Lemma B.14. For any >> 0, there exists g" E Ke and de > O such that B(g", de) Ke.
Proof. This result is a simple application of the results on the quantitative stability of Laguerre cells stated in Proposition B.4 and Proposition B.13
O
Proposition B.15. (Hessian and Local strong convexity). Under Assumptions (Al) or (B1-3), H is
twice differentiable. Moreover, there exists a constant and radius r > 0, such that for any Ig" gllu I r implies that the second smallest value of the Hessian H is lower bounded by
R E
Proof. The fact that H is twice differentiable was already known in the compact case and is proven Proposition for the non compact case under (B1-3).
Under assumptions (A1) and using Proposition B.2 or under assumptions (B1-3) and using Proposition B.12 H is strongly convex K [wmin"" Applying Lemma B. 14 concludes the proof.
Proposition B.16. There exists > 0, such that uniformly in g E C, we have
H g g"), 2 nllg g".
Proof. Observe that, by Proposition B.12 H is locally strongly convex on the orthogonal of 1, on the set
K Wantn
{g vi E M] (LL. 2 W min
2
Therefore, for any g K K Jamnin have (VH(g), g g") > g g 11
Now, suppose g E C Kg Wamnn" Using Lemma B.14 know that there exists do 0 such that B(g" do) C Wmin' Therefore, by the convexity of H. there exists > 0 such that
(V g") H(g) H(g") c.
25

---

Defining
H(()) H(g") gg - g" 1
X inf
> cf (DDiam(()),
gEC|K "miin
have for any g C Kg Miin
(V 1--8--1-- -3",,, 2 l - -
Taking 7 - min {A, } concludes the proof.
C
Proofs of the convergence rates of PSGD
C.1 Fast convergence rates for MTW costs
C.1.1 Convergence of the non-averaged iterates.
Theorem 4.4 (Non averaged iterates). Under Assumptions (A1) or (B1-3) and for any decay step of the form Yn >n/n with 71 0, E (1/2, 1), we have the convergence rate
Ellg g" Ie
7n
Proof. By definition of the gradient step at time n + 1, sampling X,+1 ~ / and since g" E C,
have V hgh(gn. Xn+1)lle I a.s. and
ga+1 - gº
Projec - Tn+1 V ggh(gn (gh( -n+
< BB In+1 Vgh(gn, Xn+1) 8"1l?
(llgn g"ll 2n+1 Xn+1)) gn -g),, + / Xn+1)ll1)))
Xn+1) (Ilgn g" g'll 2 (Vgh(gn, Xn+1), gn -g)), + +
(14)
we have for any g E C, (VH(gn). ).g. g") 2 nllg. g' Therefore, taking the conditional expectation, we obtain
Using Proposition B.16
E [|lg.+1 glll
Fx < Ign g 11: 217m+1) + 4
Taking the expectation and applying Lemma F.3 with ò, Elllgn gn g" and mn 4% gives
E [[1 glll s exp
-2n 2m
4 + E gm. g*1 + 7n/21-1
k=[n/2]
where no = min (n E N. 7/+11 S }.. Remark that the exponential term converges exponentially fast. Indeed, we have En in/2] 7 2 n 1-b with 1 1
b > 0. Moreover, l|g., g g* (C)²
Therefore, since for all 2 2, 7m/22 -1 < 2 we have the desired convergence rate
[g g" [|3] $ Yn
which concludes the proof.
C.1.2 Convergence rate for higher order moments the non-averaged iterates.
prove here the convergence rate higher order moments error ||g.. - g* This conver- gence will be useful for the convergence rate of the averaged iterates of PSGD. While this proposition directly proves Theorem (.reem/444 by the use of Jensen's inequality, the proof is slightly more cumbersome we decided to make separate case.
26

---

Proposition C.1. Under Assumptions (Al) or (B1-3) and for any decay step of the form =///n² with 71 > 0, b (1/2,1) and p E (1, we have the convergence rate
E gn g
Tp
where (gn) is the sequence of non-averaged iterates of PSGD.
Proof. By definition of the gradient step at time n + 1, sampling Xn+1 μ and using inequality
14).
gn+1 gl (llg. gg"ll" 2 (V Vghlgnn Xnt1), gn -g"), + 1
Using that (A + B + C)$ Ea b+c=3 alde A C", we obtain
gg+1 - -g' S gg. - g
- -6|gg, g 1 i+t (V (n+1).x -g",
+ g, g" ll 7
12 g. g" 1
(Vgh(gn: X 8n g')
48|gg g g'lB7 (Vgh(gn Xn+1) g"),
+ 48 g. - g 7|77++1
-8y (V (Vgh(gn Xm+1), gn gg),
48y X - g²),
907 (Vgl X,+1), g*),
In+1-
Taking the conditional expectation and already omitting some negative terms thanks to (VH(gn). gn. g"), 2 0, which follows from the fact that H is convex and g" is minimizer, gives the simplification
E || - g'llo Fx] S g. g'lle
- 61|g. - g I1 7l ga -g").
+ 12 12 gg 1
+ 12
g" 11:
E
[Vh(gn, Xnt1). - -g))
+ 48 [g.
+ 48
E
(Vh(gn, X -F
+ 28
11
(V (Vgh(g. Xn+1). ( -g" -
Using Proposition 1.
we have for any g E C, (gH(g.).88 - -g"), Sauchy-Schwarz inequality gives (Vh(g... (g.. X,t1), gn g"), 2l two inequalities we obtain
n 18a-8a -| The Combining these
[| 1l
Fr. <
g. ----gll 1l - 617m-1 1) + 60 llg. g" 1
+ 240 2
g" 11 + 2
64 04 Ign g g*
Using Young's (generalized) incquality ab ac <
[ac)²
be for + 0, p c²g
+ 1 = 1 and applying
p
60 lgn - g" with e = (2)
2/3
3 gives 60..+1 ||g. gg" S 60"
(g7
P
3, =
27

---

if 1, 2 + gl Analogously, one has 647741 11g.. -g"ll" S
2
7n + 11 -g"l
Thus,
"
taking the expectation, have
32
Elllg++1 g"l - Elllgn g" 11.1(1 41/7+11 + M+41 240 Diam, (C)
103
1/2
2
ntt1 64
"
where the terms involving Dia appears from the crude bound [g. glle I Diamz(C).
similar way as the proof Theorem 4.4 gives gl g* 2 775 so by Jensen's 's inequality, we conclude
Applying Lemma F33
B gn+1
2P
for p E (1,2,3}
Tpp
C.2 Convergence of the averaged iterates.
Theorem 4.5
(Averaged iterates) Under Assumptions (Al) (B1-B3), and assuming that fu is
a-Hölder with E (0, 1]. for any decay schedule of the form 7n n/n" with % > 0 and b E Ita 1).
we have the convergence rate
g*1l3] = 0 (1/n). Ellgg Without assuming fa to a-Hölder, and for b E (1/2,1), 1), we still obtain
Blllg.. g" ||'] = O (1/n").
Proof. For this proof, we introduce the additional following notation: For any c >> we define the function + Ve(() such that
1 (T +
if 1,
K (T)
(15)
(T+
We start by a decomposition of the gradient step, already present in [9). We define the differences
Pk: = Projc (gi: 7 1 Vgh (gx, Xx+1)) - (gi 7 Vgl (ge, Xx+1)),
- = VH (gx) Vig (gx, Xxt1),
6% V// (gx) (²H((")) (gx -g").
Noting IM the identity matrix in MMr(R. we observe that, by incorporating each introduced term sequentially, for any k: E N, we have
gk+1 g' Projc (gk: Not1 Vigh(g: Xx+1)) g
= =gk - 7k+1 V Vig(gt X g" - -pk
gk -7++1 V H X4+1) g" + Pk
(Jss 7K+1 2 H (g") (gr g.) -h+11 8g Th- 1 Pk
Thus, we have that
A H('") (gk g')
g+ gk-1 8y Ex+1 Pk
i
7h+1
Observing that n+I k (gk g*) averaged iterates
g
g' we have the following decomposition of the
v²H(g") (E. -g")= + k=
g
8
E1
Ps
Mk+1
+
k++
k==
k=
k==
28

---

We will now give the convergence rate of each sum.
Convergence rate for
Ek=o
BR Be-1
1
7k-1
gk gk+1
R
gg g
gg++
g'
7k++1
7h+1
0
k=0
n
gk g"
gk+1 g"
Y6+1
7k+1
80 -"
gn+1
8
(gk
7k+1
7k
71
7n+1
k=1
Remark that 7n+1 7n
271 6-1
Using Minkowski's inequality and that, by Theorem 4.4
(non-averaged iterates), E [l g" 111 S (n++)) 1)-
E
g
gk+1
v (1 1) + Diam DC)7 + Vnn "
1
(n + 1)6/2
7k++
k=
We thus have the convergence rate
gk+1
1
E
nnn 1)2-
7K+1
Convergence rate for
1 1
Σ h= 8F.
We recall that 5 V gx) V2 (gx g") and that the Hessian using either Theorem B.3
or Proposition 4.1 depending on our setting, there exists a ball B(g", di) with d, > 0 where f a-Hölder. Therefore, applying Lemma F44 if ga E B(g",d); we have
|6
S
gg g"ll g"
Otherwise, since the Hessian, whose expression is provided in Proposition B.5 is uniformly bounded by an application of Lemma F.2 there exists a constant Cs such that for any g E C, || V (g)
(²H(g") (g gg) < Cs.
Since P(ge & B(g", d))) PP([g: - g-ll d1), using Markov's inequality gives
E 8x [13]
E[] 0 ggg d,), + B111 l
B (d))
C
2 g
12+2a
Ellgg g" g01 (1
d2+2a
1
22+2a]
Therefore, using Minkowski's inequality, we have
E
8
Mk-1
+
k=0 !1
11 (n + +1)
1+a
Atnb
17 (n + +1) bl
11
Convergence rate for Σn Ek+1-
29

---

We recall that Ex+1
VH (gk) - Vgg (gk. Xx+1) and thus E[Ex+1] = 0.
Observe that
n-
Σ Ek+1
=
Σ
Ek+1
+
Ek+1, Eut1
+ 115++111
2= 0
A=
R=0
with
)}=
)
Σ Ek+ts En+11
=B
Ek+
|Sm+1 [Fal
Thus, since for all k; E [[]
s 4, have the convergence rate
1 E
2
Σ
Ek+1
S
Vn
R=0
Convergence rate for x+1 E
P J6+1
k=
Take do such that B(g", do) C. Using the notation Vx = Vgh (gi, XR+1) for conciseness, we obtain
E
P [+]] = E Proje (Bk 7h+1 Vx) (gi: - 7++1 V
E Proie (Bx- 7h+1 Vx) (ge- 7h+1 Vx)ll lg m Vegc
Since for any y E one has |/ Proje(x)]l= S - taking y gk. and since g 1641 VA is satisfied only if lggx Not1 V g lle do, we have
E
P
< EE || V 11e4 V2-
7k+1 V gg
g" 11:0
47
dj
7++1
(2'B
||gx -g'1l(] 29 2
dg
$
172
Th+1
Where used Markov's inequality and the inequality (A BB < 2At + B*), for all A, B e R and that by Proposition C.I
[|g..
g+ll
$ 2 (n
+ 1)-2)
We thus have
27
pk
Yk+1
72
1)
m1
( 1)b
Conclusion.
30

---

Using the convergence rate of all our terms, Gauchy-Schwarr inequality and that (A + B)² 1 2(A1 + B²) for all A, B E R we conclude
E
(g')
Bk+1
P
=B
8
Ek+1
7k+1
+
+
k=0
k=0
k=0
k=
1
11
(1 1)2-b
(n 1)0+ab
n +
1
1f (n 1)26
Since b E ( 1) and E (T+o 1) the limiting term
I+I and we have
B ([ (sn 8')]["] n
Finally, observe that there is an orthogonal matrix U such that
H²"(g") = U diag (Ar...., A...:.,A-I..)UU
Therefore, noting by abuse of notation
(v²1((g)) = U diag (A ,....,,. - 0) UT
the inverse of V in the space Vect (eet(1M)= we finally have
BllB. g01l S
22n+11
where À = Mi A3 > 0 by either Theorem B.3 or Proposition B.12
C.3 Convergence rate PSGD the general setting
Theorem 3.2
(PSGD in the general setting) Assuming that the semi-dual problem 44 admits at least
one solution g" and that there exists compact set K such that μ(K) 2 Wmin choosing the
learning rate 7n n/n with n
Diam(C) and b }. obtain
2v2
4 Diam(C)
E H ( H (g')) 5
vn
Proof. Define 7 for 0, 2 1 and denote by g" E C minimizer of the functional H.
Thanks to Jensen's inequality coupled with the fact that no matter g RR H(g) - H(g") s
(g (g g"), it comes
E | (g..) H (g')) SE
(ga) H (g))
S
E
VH (g:)
(g: gg))
k=U
k=
Then, since no matter k; Xa+1 M4 we have E. Vgli(Br X
Fi) = (H(g),
we have
n Vih (gu, Xx41) (gk g*)
E (H H n
E
(16)
We will proceed to bound the right hand side of this inequality.
By definition of g and since g* E C and Proje is I-Lipschitz, it comes
E
|g
g"
[12] < E |Proje (gA 7h+ Vgh (gt, Xx+1)) - -g 1²]
E gb 7++ V (gr. X - =
B gg 1² + nhhn Vigh (ge, X2+1)12- 2y++1 Vgli (ge, Xa+1) (gx -g))
<
31

---

In addition, since [vghgg S 2 a.s. no matter R and X E R
E 27 Vgh gg. xx+1) 1) (g g*) S gx g" |8+1 - -g"1l -=112++411 + +
Then, with the help of Abel's summation formula.
2E
(g. Xk+1) (gk -")
g" 1|
1¹112)
g
E
+
4
M++1
7k+11
k=0
k=0
E
gg
g¹ll2
1
1g++1
g" 11
80
g
11
4
Mk+1
7h+11
Y
Yh++
7/1
h
Then, since for all k; l|g - g'l S Diama(C) (C), comes
1
D
2E
Vgh (gk Xx+2) T (Bk- g*)
< (C)
+
+
4
7k
7k+1
Yk
0
Am
k
Diama
4
7n+1
k=11
(C)2
+1+ 8n
n
Using the inequality 16 we obtain
1
DC)m
E H (..) (g.)
H (g*))
871
Vn +
"1
The best constant ? is then 71 rate
Diamy 2v/
but matter " have the desired convergence
E E 11
D Proof of Lemma 3.1: Localisation of projection set
Lemma 3.1 (Existence of a projection set) As soon as the semi-dual problem is well-posed, there exists minimizer g* in the set
C: {g {0} x M-1 | S [])]
where ||c||,,> sUP=EK |c(a, 3;)l for any compact set K satisfying (K) 2 1- min wy.
Proof. By the first order condition, the minimizer of H satisfies ((L,((g) wy for all j E [[1, M]. In particular, one can restrict the search set for an optimal potential to the set of potentials defined by
= g AggER MM Vij [1, M..MM. ((L,(g))
Wmin
Let us show that this set is contained in an _ ball with an explicit radius. Consider any compact set K such that u(K) 2 1 Wmin- For g and any j E [L, we get that
(L, k 1((RM L (RM K))
2 M (g)g)) ((RRM K)) (1 ((1-(())
W Wiin
0,
32

---

and so (g) NKK * 0. In particular, for every j E [[1, M, there exists 2, E Ly(g) n K and so for
all [1. MM
dzz, - 9j S c( Us) 9r.
Therefore, using the fact that the cost is non-negative, we have
max min 9j S max max(c(z2 ya) c(z v3)}
S max sup c(z, yi) = ||||,,0..
iE|LM seK
Moreover, since H(g + A1 = (g) one can fix = 0, which concludes the proof.
E
Minimax estimation of OT quantities
Consider P,Q E P(R.) with densities fr and fq. We recall that the Hellinger distance is defined by
d=(P,Q) ( (Vir(o)) Vio(1)) ddda(())
2
(17)
also recall the formulation Le Cam's Lemma. refer 335 Chapter 15, for more details.
Lemma E.1. (Le Cam's 's Lemma.) Let P be set of probability distributions on measurable space, and consider the problem of estimating a parameter E O with a loss function defined, for all 9, 0 E θ as
((0,0) = d(b,6),
where p 2 an integer, and d is distance on O Then, for all 0,, 02 E O
RM = inf sup Ee (00, (X)) 2 (X)))
20 (1 - vndd (Po, Po,)) d(0), 02),
Tim eee
where Ry is the minimax risk, and T()) is estimator based i.i.d samples from Po-
In the sequel, we note PLip the set of probability measures on IR with Lipschitz densities.
E.1 Kantorovich potential
Proof. Consider tooo + 1 and fix the cost to transfer mass to be the usual quadratic cost <xx, y) } || y/12.
For 8 2 0, we define Migs A 1). Since d 1, the optimal transport map is monotone non-decreasing (see, for instance, Chapter 2 in (32). Thus, we must have the identity
0, if S 6,
T T
1, otherwise.
Therefore the vector 8 E IR2 solves the semi-dual problem if and only if it satisfies the following inequalities
c(z, 0) - of < c(z, 05
Vr < 8
Vr 8 c(x, - 0 < clz, 0) 0f
Since c(x,y) 111x 2 fix 0 and compute
g 0, 1 -
Therefore, parameterized the family of probability measures μ4 E Prip that the couple (0 0) is the unique solution in è C. {0 (2),02) R²;0; = 0} of the dual of OT(pe, v) In this class of
33

---

probabilities, the minimax estimation of the optimal transport potential 8, given >> 0 ii.d samples of the source measure, can be written
R
inf sup Euo (cm) BEB
[10(m) 011
where ((x) is based on the n i.dd samples from the source measure μ.. Note that
R
S
inf
sup
E [Ig(") g {=1]]]
(18)
n) PeP
where the infimum is taken over all vectors g(1) based on i..d samples of μ. Using the closed form of the Hellinger distance between Gaussian distributions, we have
du d1( mgs) V exp [
+ (6). Applying Le Cam's Lemma For - 0, the Taylor expansion gives du (1go, Mos) o0/v8+(())
with 1/ / gives
nº 2 vndh (Mrg0 Mo0 1100 1/
1
1/VB+
10n
Using the inequality (18) concludes the proof.
E.2
OT map
Proof. Define for [0, 1] the set of probability measures μo, with density:
Sps(x) (x) = (1 5g(z)),
E [0, 1].
where
g(x) = [ - 2x);
x E [0, 1/2), E [1/2, 1].
- 1),
The squared Hellinger distance between n4 (uniform) and μu is:
v1+5g(x)) dH(1on 21)2 / (VI - / 0g(x)))) 2 dx
1
(1 20)3/2 + 66 (1 (1+ 200)3/2
65
0² + o(
2
when 8 + 0. Therefore, we obtain
du(uo: 146)
_1 + o())
V2
Since y18 E PHr & [0, 1]. we have
|||d(0 - Tpp (())
(r(n)
inf sup E, T6o μEPH
2 inf sup E,s
Trs
(19)
T(m) 5E(0.1]
From the relation 1 - 28 < sro (x) < 11 25, Vo E [0, 1]. we infer that no matter T(n) and 8 small enough
T(() Tps.p 1
1 ((m) Tpe. (
(20)
(P(Us)
2
34

---

Consider v = [0) + (6(1) as above. Recall that the optimal transport map is monotone non- decreasing in dimension 1. Moreover by definition (x) E (0,1), x E [0, 1). and ju8 (
us.u (0))
1/2. Therefore one identifies THgn = ==2MM where M3 is the median of uas, ó > 0, satisfying
J. Ml
(1+ = 2
Noticing that M2 E [0.1/2], we solve
1 (1+ 26(1 2x) dx
1
2
which gives the solution
1 1 26 / + 482
1
Ms
0 +(6))
48
2
Observe that
[T T Tue Tps,0112 1/' |1.2M0 - 122 dr = |M4 Mol
We proved the relation |T Ths (((01)))) = = Applying Le Cam's Lemma with for n sufficiently large and any p E 00), we obtain
5 vn
||r Taaull (L
inf sup Eus 7 6E[U,1]
(1
Vndd Hoo) [|T (ls.weeneennn
2
+0(1)
1 (
1
2
22
Vn
+
Vn
Therefore, combining inequalities (99 and 20 conclude
inf sup E, r(a) PEPn
((m) Tu,
[P(())
Vn
F
Technical Lemmas
F.
Technical Lemmas for Appendix B
Lemma F.1. Perturbation Laplacian Matrices. Let A and B be symmetric Laplacian matrices of the same size such that:
Ag S0, Bij S Agg. for all i $
Suppose Xe(A) > where (A) denotes the second smallest eigenvalue of A. Then:
x²(B)= >²(A)
where (2(B) is the second smallest eigenvalue of B.
Proof. We recall the variational characterization of the second smallest eigenvalue of Laplacian matrix M is
I Mx
Xe(M) = min al
xT x
35

---

Define the matrix C = B A. For i #
Cij= = Bij Aij Aij 10;
and for diagonal elements
C = B An =- Ec520
Thus, is Laplacian matrix and positive, semi-definite. Let y/ be the eigenvector corresponding to (2 the second smallest eigenvalue of B, that is Byz = (B)2 with y2 1
Since A= = C. we have
v Ay2 = T (B- C)y2 3/ Byz y2 T Cy2-
Thus,
y Ay22
1/2 Cyz
= A2(B)
v2 922
V2 1/2
T
By the variational principle:
A'A
vo2 Ay2
3/ Cyz
(A) min 211
$ 12
x²'xx x
vo2 V22
y y2
Since C' is Laplacian matrix, we have vo Oyz 2 0, no matter y/2 and thus A2(A) S A2(B) which
completes the proof.
Lemma F22 Let fn satisfy, for all R2d the decay condition
Σne
sup
fx(2) 00.
B(0,-B(0
Then, there exists constant C > 0 such that, for any hyperplane H C Rd, we have
[ Jn(x) (x) SC C.
1), Proof. Defining for any E R(r) = B(0,r) \ B(0,r - 1), we have
J (a(t))tA (x)
Σ
r21 HnR(() [1(x)d7("-1(x) (x)
Σ J
sup fu(x)d7(-1((x) (x)
r21 HDR(() zE(())
< Σ r1 HDR(() ((R,(
fz)d (x)
sup
Then, using the fact that Hd-1 (H R(r)) < Hd-1 (H B(0, r)), and noting that H/ O B(0,r) is a (d 1)-dimensional ball of radius r, we have
z (d-1)/2
H (H <
T (d+1)
Therefore, incorporating this bound, we obtain:
[ fu(z)aH(' (d-1)//
d+1
fu(z) B(Or))
sup
which is finite by our decay assumption on fp-
36

---

F.2 Technical Lemmas for Appendix C
Lemma F.3. Let (7n) and (ma) be some positive and decreasing sequences and let (6m)220 satisfying the following:
The sequence 8n follows the recursive relation:
8n+1 S (1 wm++1) on + mn+17k+1
(21)
with 60 2 0 and w > O.
converges to O.
Let no = inf {n 2 w1+1 S 1}, Ong is non-negative
Then, for all n 2 no, we have the upper bound:
n
8n S exp
w
7
Σ
nerr + Eng
i=
Proof. For all n 2 no. one has
8n S II
(1 wh:) 6no +
Σ
II
(1 wi)) mom
i= +1
R=
1 i=
=:U1.
=:U2.n
One can consider two cases:
[n//2] - 1 S no and [n/2]
Y10-
Case where [m/2]] - S n1 Since my is decreasing,
U2,n S mmg+1 Σ
II (1 w7;; 7
km i=k+1
n
n
Σ
II (1 w)))
II (1 wy))
Mmo+1
W
Am link1
-mo++1
1
II 1=
(1 - wx))
< Mmo+1
Since m, is decreasing, it comes U2. I w mm/22]
Case where [n/2] - no: As in 5 for m = no + 1,... n, one has
1 7
U2, I exp
mm
k=
k= +1
Then, taking [n/2] 1, comes
1n/21-1 Σ k=
U2 S exp
mm + [1
k= mn/2
Lemma F.4. Linearization of the Hessian If a function H : R.M - is such that its Hessian is a-Hölder the ball B(0, r), with > 0, a (0,1) and constant L, then for any g.g" B(0,r).
we have
[V - V2 g')ll Clgg g'
where C' = L
a+I.
37

---

Proof. Consider the Taylor expansion of VH (g) around g":
V (()(g") + v (1 (g -g") R(g),
where the remainder term R(g) is given by:
R(g) Hg +1g g')) 42 Hg")) (g g")dl.
By the assumption of a-Hölder continuity of the Hessian, we have [[V2 + igg g*)) V2 (g \|| S Ll g*) 111 - 1"
Thus,
[ E S( Le g"1l"||- gd Llgg g'll+ta / dt.
Evaluating the integral:
I dt a + 1
Therefore,
L a+1
[R(g)]
(g (g"
This implies the desired inequality:
[VH(g) v²H(g") (g')l < Cl (g") 1+
where C== a+1
38


Reviews:
[{"review_id": "mgQR1XXkMs", "reviewer": "Reviewer_g7BH", "summary": "The paper studies the convergence of an online SGD-type method for the semi-discrete optimal transport problem, where the source measure $\\mu$ is discrete and the target measure $\\nu$ is continuous. The analysis is applicable to a broad range of settings, including: 1) cases where costs satisfy the Ma-Trudinger-Wang properties (MTW), and $\\operatorname{supp}\\mu$ is compact; 2) cases where costs are quadratic (in which case compactness of $\\operatorname{supp}\\mu$ is not required). The authors consider a semi-dual formulation and introduce a compact set $\\mathcal{C}$, which they prove contains a solution. This set is then used as a projection set in the iterations of an SGD-type method. This leads to an $\\mathcal{O}(1/\\sqrt{n})$ rate for OT map estimation and $\\mathcal{O}(1/n)$ rates in terms of the objective and potential. The authors prove that these rates are minimax optimal. Numerical experiments illustrate the performance of the algorithm.", "questions": "1. In which cases is the compact set $K$ (used in defining $\\mathcal{C}$) difficult or impossible to identify?\n2. The objective $H$ is referenced in lines 95-96 prior to its formal definition, exemplifying clarity issues in the presentation.\n3. Please correct typos (e.g., replace \"whic\" with \"which\" in line 13).\n\nThe paper's final score will depend on satisfactory resolution of these issues.", "limitations": "The limitations related to finding the set $K$ may be discussed in more detail. Apart from that, limitations are mostly addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths are as follows:\n- The theoretical analysis of the method is applicable to a broad range of settings,\n- Lower bounds are established,\n- Numerical experiments illustrate the performance of the method.\n\nAs for the weaknesses, the clarity and quality of the presentation should be improved, and typos should be corrected. In my opinion, more discussion about the compact set $K$ used in the definition of $\\mathcal{C}$ is needed (see questions).", "was_revised": true, "final_justification": "Apart from minor remarks, I only had one question which the authors addressed in detail. The paper's contribution seems valuable and I don't see any major issues. Therefore, I maintain my positive score.", "rebuttal": "We thank the reviewer for the thoughtful and positive feedback. We respond below to the specific concerns raised.\n\n**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.\nIndeed, this collapses to a classical problem of estimating a one-dimensional quantile.  \nWrite $X\\sim\\mu$ and define  \n\n$$\nR\\_{\\star} = \\inf\\big\\\\{r:\\; \\mu(||X|| \\le r) \\ge 1 - \\tfrac{1}{4} w\\_{\\min} \\big\\\\}\n= F^{-1}\\big(1 - \\tfrac{1}{4} w\\_{\\min} \\big)\n$$\n\nwhere $F(r)=\\mu(||X||\\le r)$ is the cumulative distribution function of the scalar random variable $||X||$.\nBecause 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.\n\nDefine the estimator  \n\n$$\n\\widehat R\\_{\\eta} := \\inf\\\\{\\,r:\\; F\\_n(r) \\ge 1 - \\tfrac{1}{4} w\\_{\\min} + \\eta\\\\},\n\\qquad 0 < \\eta < \\tfrac{1}{4} w\\_{\\min}\n$$\n\nwhere $F_n(r)=\\frac1n\\sum_{i=1}^n \\mathbf{1}_{\\{||X_i||\\le r\\}}$ is the empirical CDF of $||X||$.\n\nBy the Dvoretzky–Kiefer–Wolfowitz inequality with Massart’s sharp constant [1,2],  \nchoosing  $ \\eta = \\frac{1}{8}w_{\\min}, \nn\\ge\\frac{\\log(2/\\delta)}{2\\eta^{2}}\n$\nensures that, with probability at least $1-\\delta$, we have $\n\\mu\\bigl(B(0,\\widehat R_{\\eta})\\bigr)\\ \\ge\\ 1-\\tfrac14 w_{\\min}\n$, \nwhich is a dimension‑free sample‑complexity bound.\n\nWe note that tighter bounds in terms of $\\eta$ may be achievable, but we rely here on well-established classical results for clarity and generality.\n\nWe 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.\n\n**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.\n\n**Question 3** Thank you for pointing out the typos. We have corrected them in the revised version.\n\n### **References**\n[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.\n\n[2] Massart, P. (1990). The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. Annals of Probability, 18(3), 1269–1283."}, {"review_id": "FrTaxL640c", "reviewer": "Reviewer_74ib", "summary": "Summary: This paper considers the semi-discrete optimal transport problem where we are given a discrete distribution \\mu and a continuous distribution \\nu and one wishes to compute the optimal transport from \\mu to \\nu. The semi-discrete optimal transport is more expressive than the discrete OT and more tractable than the continuous OT. Moreover, unlike the continuous OT, estimating the semi-discrete OT via samples does not suffer from the curse of dimensionality. In fact, with n samples, we can get an estimate of the semi-discrete OT cost and map with a convergence rate of 1/\\sqrt{n} (I believe this convergence rate hides the support size of the discrete distribution). \n\nFrom an algorithmic stand-point, even with the sampling result, one has to compute the exact discrete OT to estimate the cost. The authors suggest SGD based algorithm that uses these samples and estimates the cost and plan efficiently. The authors also complement their theoretical results with an implementation and analyze the performance. \nAnother major contribution of this paper is in reducing the assumptions (for instance, compactness assumption) from the convergence rate.\n \nThe authors, however, miss an important reference which provides an alternate approach for low-dimensional settings (the result presented at the end of [1]). In this alternate approach, one can pre-process the sample in a data structure in time that is linear in the number of samples, and obtain the exact OT cost (between discrete distributions) using only sub-linearly many calls to this data structure. So, by combining this with the result of Pooladian et al., one should be able to get a linear-time estimator in low dimensions. \n\nOverall, I think this is a solid paper that can be accepted.\n\n[1] \tPankaj K. Agarwal, Sharath Raghvendra, Pouyan Shirzadian, Keegan Yao:\nA Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem. NeurIPS 2024", "questions": "Please answer the questions I raised in weakness.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Positives: This paper establishes near optimal convergence rate for SGD based approaches to estimate both the semi-discrete OT cost and map. The paper generalizes the convergence rate to various cost functions as well as for distributions that are not necessarily compact.\n\nOne the flip side, the paper does not discuss the dependence of the convergence rate on the size of the discrete support. Could the authors provide the dependence of the convergence rate as a function of the size of the support of discrete distribution?\n\nThere are also a few typos across the paper. For instance, L13 (whic -> which) and L146 ([XXXX] must be removed)", "was_revised": true, "final_justification": "This paper studies the behavior of an important approach (SGD) for an important problem (semi-discrete OT) and provides some useful bounds. The authors answered my questions satisfactorily and I maintain my positive score for the paper.", "rebuttal": "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.\n\n\n1. 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.\n\n2. In our convergence analysis (Appendix C.2, see the equation after line 925), we show:\n\n$$\n\\mathbb{E}\\left[\\| \\bar{\\mathbf{g}}_n - \\mathbf{g}^* \\|_v^{2} \\right] = \\frac{1}{\\lambda^2(n+1)} + o\\left( \\frac{1}{n} \\right),\n$$\n\nwhere $\\lambda > 0$ is the smallest eigenvalue of the Hessian of $H$ at the optimum, characterizing the local strong convexity of $H$.\n\nThis 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.\n\nWe 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.\n\nNonetheless, 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)$. \n\nAlthough the dependence on $M$ that comes from our analysis is conservative, we will include and highlight this bound in the revised version."}, {"review_id": "Y8r41uErp8", "reviewer": "Reviewer_9oFK", "summary": "This paper studies the semi-discrete optimal transport problem, whereby one seeks to compute the optimal transport cost and map between a continuous distribution and a discrete one. The authors attack the problem using stochastic gradient descent and study their computational and statistical properties, establishing the convergence of optimal transport costs, Kantorovich potentials, and optimal transport maps with a rate of $1/\\sqrt N$ even when the continuous measure does not have compact support. In a specific setting, the authors also show that the rate for optimal transport maps is minimax optimal. Numerical experiments support the theoretical findings.", "questions": "1. Can the authors please clarify the position of their paper w.r.t. the literature (see comment above)? \n2. Can the authors please clarify my concerns for Lemma 3.1 and Theorem 5.3 (see comment above)?\n3. Can the authors please clarify assumption B (see comment above)? \n4. The authors repeatedly used “linear convergence”. What do they mean by that? The algorithm does not enjoy “linear convergence” as commonly meant in the optimization literature.\n5. In Section 6  and Fig. 3c, the empirical results do not seem to precisely match the theoretical bound, at least not as accurately as in the other experiments. Can the authors explain?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strenghts:**\n- The paper studies an important problem, namely the design of computational algorithms for the semi-discrete optimal transport, which is relevant for a variety of machine learning applications. \n- The algorithm proposed by the authors is intuitive and simple to implement, and enjoys rigorous theoretical guarantees of convergence (rate of $1/N$ for the squared error of the potentials and $1/\\sqrt N$ for OT maps, under mild assumptions).  \n- The paper includes several technical results, in particular boundedness of Kantorovich potentials in the non-compact case (Lemma 3.1) and Lipschitzness of the “error” in the optimal transport map in the non-compact case (Theorem 5.1) which are of independent interest.\n\n**Weaknesses and comments:**\n-  The paper should significantly improve its positioning w.r.t. the existing literature, especially in the following two ways: \n  - What are the novel contributions of the paper compared to [5, 20, 29]? The paper definitely contains novel contributions (e.g., the non-compact case), but the existing work should be better clarified (not only with a citation but with references to the statements). Also, it seems that [29] considers the entropic optimal transport problem.\n  - The authors should review existing results on the regularity of Kantorovich potential and their boundedness.\n  - There is existing work by Taşkesen and co-authors (see reference below and references therein) on the computational aspects of semi-discrete optimal transport. The authors should position their work w.r.t. this literature. \n- Lemma 3.1 and its proof:\n  - I suspect Lemma 3.1 cannot be true without assumptions on transportation cost; indeed, if the transportation cost fails to be lower semi-continuous, then Kantorovich duality might fail (indeed, reference [31] assumes lower semi-continuity of the transportation cost to derive duality). Thus, I suppose some regularity of the transportation cost is necessary.  \n  - The authors say “suppose that (4) admits a minimum”, but already write max in (3). In fact, Kantorovich potentials are well-defined under minor assumptions on the transportation cost, so I do not see the benefit of being more general here. \n  - The equation after line 954 in the proof of Lemma 3.1 needs to be better explained, saying that it follows from the definition of $\\mathbb{L}$.\n- The results in the non-compact case are predicated under Assumption B, which is however never discussed in the paper (in particular, (B3), which does not have an analog in the compact case). Given that the focus that the authors put the non-compact case, the assumption must be explained and justified.  \n- Theorem 5.3: \n  - I fail to understand why Theorem 5.3 is proven in the one-dimensional case when $\\nu$ is only supported on two points. \n  - I fail to understand why the proof implies the presented result. For instance, the set $\\mathcal{P}_\\mathrm{lip}$ appears in the statement of the theorem, but never in the proof.\n  - In the proof, the authors focus on Gaussian distributions (in E1) and specific distributions (in E2). I do not see why this continues to imply the general result in Theorem 5.3. \n- Minor comments: \n  - The structure of the appendix of the paper is confusing, with some of the results hard to find (e.g., the proof of Theorem 5.3 is not clearly identified, same for the one of proposition 4.1 and Lemma 4.2).\n  - Defining measures as on line 73 is not rigorous. A measure “eats” sets of reals and not reals. \n  - The acronym MTW is used in the abstract and section 2 before being defined. \n  - There is a [XXXX] on line 146.\n  - In Section 6, $\\mathbf{g}$ should be $\\mathbf{g}^\\ast$, in lines 317-318. \n  - The norms and inner product defined in the equation after line 219 are in fact seminorms. I suggest making this point clear in the text and in the proofs (e.g., Proposition C1). \n  - In Proposition B1, the term $\\mathcal{H}$ appears undefined. \n  - In Proposition C1, there is a 2 missing in the exponent in the left-hand side of the equation (but the proof appears correct). \n  - In the appendix, Theorem 4.5 is in fact 4.4 and Theorem 4.4 is 4.5.  \n  - In the proof of Theorem 4.5., $p_k, \\xi_{k+1}, \\delta_k$ are vectors. I suggest to use bold to unify the notation. \n  - $\\bar g_n$ should be bold in the equation after line 934. \n  - In the equation after line 955, I suspect that the last sum should run from $k=1$ to $n+1$ (and not $n$), implying that the last term is     $8\\gamma_1\\sqrt{n+2}$.\n  - There should no max over j in the second line of equation 955. \n  - Many equations in the appendix go out of margin, and one equation (after line 939) does not remain visible. \n- Typos: \n  - Period missing on line 47. \n  - There should be no period at end of line 607 and a period at the end of line 613.\n\n\nTaşkesen, Bahar, Soroosh Shafieezadeh-Abadeh, and Daniel Kuhn. \"Semi-discrete optimal transport: Hardness, regularization and numerical solution.\" Mathematical Programming 199.1 (2023): 1033-1106.", "was_revised": true, "final_justification": "The authors have satisfactorily addressed my concerns (in particular, Theorem 5.3 and positioning w.r.t. the literature). Thus, provided that these comments are incorporated in the revision, I am happy to increase my score.", "rebuttal": "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.\n\nWe respond point by point below.\n\n\n### **Questions** \n\n\n**1.** Positioning w.r.t. the existing literature: \nWe understand the reviewer's concerns and will include a more thorough comparison with the literature, notably by highlighting the following points.  \n\n* **Generalizing properties of semi-discrete OT to the non-compact case:** In [5, 20], the authors present several properties of the semi-dual and \nsemi-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.\n * **Giving the first minimax results for non-quadratic cost and non-compact case in \nsemi-discrete OT, and moreover with an online/one-pass algorithm:**\nIn [29], the authors consider the estimation of the OT map from samples, but only \nin the compact case and for the quadratic cost. To achieve this, they show that the \ndiscrete entropic map, with regularization $\\varepsilon \\simeq 1/\\sqrt{n}$, \napproximates the true OT map with an error of $\\mathcal{O}(1/\\sqrt{n})$. \nThis entropic discrete map can be approximated arbitrarily closely using, \nfor instance, the Sinkhorn algorithm.\nIn our paper, we address OT map estimation for a broader class of cost functions, \nincluding non-quadratic costs and the non-compact setting. However, we assume \nfull access to the discrete measure (one-sample setting), whereas their estimator \nachieves the same rate even when sub-sampling from $\\nu$ (two-sample setting). \nA key strength of our estimator is its ability to operate in an online setting, \nwithout the need to store samples drawn from $\\mu$, and to refine the estimate \nas more samples become available.\nWhile some of this information appears in lines 303–309, we will emphasize \nthese differences more clearly in the revised version.\n* **Studying SGD algorithms for non regularized semi-discrete OT:** \nIn Taşkesen et al., the authors study regularized optimal transport in the \nsemi-discrete setting, with a class of regularizers that notably includes \nentropic regularization. They provide convergence guarantees for the regularized \nobjective function.\nIn contrast, we focus on the non-regularized semi-discrete OT problem, and \nanalyze the convergence of both the unregularized OT map and cost. We will \nincorporate a discussion of this work into the paragraph currently titled \n\"Entropic regularization\" (starting at line 124), which we will rename \n\"Regularization of the semi-dual\".\n\n\n \n**2.**  Lemma 3.1:  \nYou 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.  \n\nWe will also add details after line 954, showing that $H$ is invariant under constant shifts of the potential.\n\n**3.** **A)** Assumption B (non-compact case)\nWe 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$.\nWe will explain that it is necessary for the definition and regularity of the Hessian of the semi-dual.\nWe 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\n\n\\begin{equation*}\nf_\\mu(x) = \\frac{1}{Z} \\left[ \\frac{1}{1 + \\|x\\|^4} + \\sum_{k=1}^\\infty k \\cdot \\mathbf{1}_{R_k}(x) \\right]\n\\end{equation*}\nwhere $R\\_{k} := \\{ (x\\_1, x\\_2) :  |x\\_1| \\le \\tfrac{1}{k^5},\\; k \\le x\\_2 \\le k+1 \\}$\nand  $Z$ is the normalizing constant.\nA complete proof of this counter-example will be given in the appendix, and we will refer to it when introducing Assumption B.\n\n**B)** (Theorem 5.3)\n* This theorem states that even in the one-dimensional case, where the source measure \n$\\nu$ is as simple as $\\nu =\\frac{1}{2}\\delta_{\\{0\\}} + \\frac{1}{2}\\delta_{\\{1\\}}$, \nno estimator based on $n$ i.i.d. samples can achieve a convergence rate better than \n$\\mathcal{O}(1/\\sqrt{n})$ uniformly over all Lipschitz measures.\nFixing the measure $\\nu$ while considering a class of source measures is analogous \nto the minimax setting in [29, Proposition 1], where the roles are reversed: the source \nmeasure is fixed and a class of discrete target measures is considered.\n*  There is a typo in Appendix E concerning the proofs of the minimax lower bounds: \nwe consistently refer to $\\mathcal{P}\\_{H}$ instead of $\\mathcal{P}_{\\mathrm{Lip}}$. \nWe will correct this typo in the revised version and apologize for the inconvenience.\nWe focused on Lipschitz measures to emphasize that even within this more regular class, \nthe minimax rate remains the same. Since the class of measures with Lipschitz density \nis a subclass of those with $\\alpha$-Hölder density for $\\alpha \\in (0,1]$, \nwhich we study in the paper, the lower bound extends to this broader class as well. \nWe will clarify this point more explicitly in the revised version.\n* The proof uses Le Cam’s two-point method. The idea is that to lower-bound the minimax risk, \nit suffices to construct a pair of distributions in the model class that are both hard to \ndistinguish (in Hellinger distance) and induce notably different values of the quantity \nto be estimated. The lower bound obtained for this pair then extends to the entire class \nthey belong to.\nIn Appendix E.2, which contains the proof of Theorem 5.3, we consider a subclass of Lipschitz \nprobability measures $\\mu_\\delta$, $\\delta \\geq 0$, and our analysis through (19) and (20) \nyields the lower bound\n\n$$\n\\inf_{T^{(n)}} \\sup_{\\mu \\in \\mathcal{P}_{\\mathrm{Lip}}} \\mathbb{E}\\_{\\mu}[||T^{(n)} - T\\_{\\mu, \\nu}||\\_{L^p(\\mu)}^p] \\geq \\frac{1}{2} \\inf\\_{T^{(n)}} \\sup\\_{\\delta \\in [0,1]}\\mathbb{E}\\_{\\mu\\_{\\delta}}\\big[||T^{(n)} - T\\_{\\mu\\_{\\delta}, \\nu}||\\_{L^p(\\mathcal{U}(0,1))}^p\\big]\n$$\n\nThe goal of this inequality is to eliminate the dependence on $\\mu$ in the norm \n$||\\cdot||\\_{L^{p}(\\mu)}$ by replacing it with the fixed reference measure $\\mathcal{U}(0,1)$ \non the right-hand side. This allows us to treat $||\\cdot||\\_{L^p(\\mathcal{U}(0,1))}$ \nas the loss function $l$ in the statement of Le Cam's Lemma (Lemma E.1).\nWe then apply Le Cam’s two-point method to the pair $(\\mu_0, \\mu_\\delta)$ and propagate \nthe resulting lower bound to the full class. We will ensure that the proof is made \nmore explicit and reader-friendly in the revised version.\n\n**4.** Linear rate:  \nWe 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.\n\n\n**5.**  In Section 6, Fig. 3c, we believe that the small discrepancy comes from the fact that the \nerrors $||\\bar{\\mathbf{g}}\\_t - \\mathbf{g}^{\\*}||^2$ are already below $10^{-4}$. \nThe target weights of $\\nu$ (such that the randomly generated $\\mathbf{g}^*$ is optimal) \nare approximated using a Monte Carlo estimator with $10^9$ samples. At that scale, \nthe residual error in approximating the optimal weights contributes to the slightly less \nsharp convergence behavior observed in this plot. Indeed, the Monte Carlo error for each \nweight is expected to be on the order of $\\mathcal{O}(1/\\sqrt{N})$ with $N$ samples, \nand this propagates into the final error metric. To validate this hypothesis, we reran \nthe experiments using $10^{11}$ samples for the Monte Carlo approximation. With this \nhigher precision, the convergence plot aligned closely with the others, confirming our \ninterpretation. We will update the figure to include the higher-precision results.\n\n\n\n### **Minor comments**\n\nWe 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.  \nWe 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."}, {"review_id": "M8Fg8PCWD0", "reviewer": "Reviewer_M6v8", "summary": "Semi-discrete optimal transport refers to the scenario where we would like to learn the optimal transport map that transports a continuous source measure into a discrete target measure. This problem can be tackled using Stochastic Gradient Descent (SGD), which results in empirical successes but it is unclear how it is able to work so well. The paper considers the projected version of SGD (PSGD), and provide convergence guarantees of PSGD. There are convergence guarantee of PSGD in the general scenario, convergence guarantee of PSGD for MTW cost and compact case and for quadratic cost and non-compact case, among others. It was demonstrated that PSGD can learn the optimal transport map reasonably efficiently. Numerical experiments are provided, verifying the theoretical claims.", "questions": "Please see the weakness in Strengths and Weaknesses section.\n\nSome minor issues: \n\n1. In TL;DR on OpenReview, \"in the semi-discre setting\" -> \"in the semi-discrete setting\"\n2. MTW properties was mentioned on Line 82, while introduced only on Line 93\n3. Line 146: \"[XXXX]\" bibtex error perhaps?\n4. Theorem 5.3, the equation should end with \",\" instead of \".\"", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The research questions are well-motivated.\n2. The theoretical results are rigorous, demonstrating the reasonable convergence of PSGD for semi-discrete OT.\n\nWeaknesses:\n\n1. For the experiments, no error bars were provided: what are the standard deviations across the runs?", "was_revised": true, "final_justification": "I found the theory as outlined in the paper interesting and could not found significant issues apart from the error bars missing. As the authors have promised to add the error bars, I maintain my original positive rating.", "rebuttal": "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.\n\n**Error bars in experiments.**\nThank 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.\n\n**Minor issues.**\nWe 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.\n\n**Formatting.**\nWe will restore the checklist guidelines as required."}]

Author rebuttal:

Meta-review: The paper addresses the semi-discrete OT (continuous source transported to discrete target), showing that the OT cost and map can be estimated efficiently with projected SGD and minimax optimal convergence rate is given. All reviewers agree that the semi-discrete OT problem is interesting and important, and the theory and rate provided are both strong and novel. As such, the paper contribution would be a worthy addition to the literature in OT.
Decision: Accept (spotlight)