Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
Authors: Ferdinand Genans
Antoine Godichon-Baggioni
François-Xavier Vialard
Olivier Wintenberger
Venue: NeurIPS 2025 poster ()
Keywords: Entropic Optimal Transport
Decreasing Regularization
Stochastic Gradient Descent
Primary area: optimization
TL;DR: We introduce and analyze a stochastic gradient descent method for solving semi-discrete optimal transport, based on a decreasing regularization scheme.

Abstract: Adding entropic regularization to Optimal Transport (OT) problems has become a standard approach for designing efficient and scalable solvers. However, regularization introduces a bias from the true solution. To mitigate this bias while still benefiting from the acceleration provided by regularization, a natural solver would adaptively decrease the regularization as it approaches the solution. Although some algorithms heuristically implement this idea, their theoretical guarantees and the extent of their acceleration compared to using a fixed regularization remain largely open. In the setting of semi-discrete OT, where the source measure is continuous and the target is discrete, we prove that decreasing the regularization can indeed accelerate convergence. To this end, we introduce DRAG: Decreasing (entropic) Regularization Averaged Gradient, a stochastic gradient descent algorithm where the regularization decreases with the number of optimization steps. We provide a theoretical analysis showing that DRAG benefits from decreasing regularization compared to a fixed scheme, achieving an unbiased $\mathcal{O}(1/t)$ sample and iteration complexity for both the OT cost and the potential estimation, and a $\mathcal{O}(1/\sqrt{t})$ rate for the OT map. Our theoretical findings are supported by numerical experiments that validate the effectiveness of DRAG and highlight its practical advantages.

Decreasing Entropic Regularization Averaged Gradient for Semi-Discrete Optimal Transport
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, geaandd-aaanabbbete...... antoine godi gooic baahoonaaggion, olivier wwwvier. www.:///errrrerooooooooobmeeeeee
aatoine.godichaee
francois- xxvioirr wtw.rir-aaaaa....aaaad-d------- vialard@u-pem.
Abstract
Adding entropic regularization Optimal Transport (OT) problems has become a standard approach for designing efficient and scalable solvers. However, regu- larization introduces a bias from the true solution. To mitigate this bias while still benefiting from the accelcration provided by regularization, a natural solver would adaptively decrease the regularization algorithms heuristically implement this idea, their theoretical guarantees and the extent of their acceleration compared to using fixed regularization remain largely OT, where the source measure is continuous
approaches the solution. Although some
open. In the setting of and the target is discrete, we prove that decreasing the regularization can indeed accelerate convergence. To this end, we introduce DRAG: Decreasing (entropic) Regularization Averaged Gradient, stochastic gradient descent algorithm where the regularization decreases with the number of optimization steps. We provide a theoretical analysis showing that DRAG benefits from decreasing regularization compared to fixed scheme, achieving unbiased OLL/t) sample and iteration complexity for both the OT cost and the potential estimation, and O rate for the OT map. Our theoretical findings are supported by numerical experiments that validate the effectiveness of DRAG and highlight its practical advantages.
Introduction
Optimal transport is now a widely used framework to compare probability distributions in different
areas of data science such machine learning [14 25 6), computational biology [47), imaging
7 even economics
[22] or material sciences ( The computational and statistical efficiency of
OT solvers is the key to facilitating their use practical applications. Therefore, both computational methods and the statistical bottleneck in OT, often referred to as the curse of dimensionality. have received significant attention over the past decade 42 [57] Regularization methods such as Entropic OT (EOT) [6] are popular techniques to mitigate these two issues. It consists of adding an entropic regularization term the objective function. OT and entropic regularization apply to different contexts of interest. The most general context is when the two distributions are accessed via samples and one wants to estimate the OT distance and the corresponding plan or map. Another context of interest in some applications, that has recently gained popularity in generative modeling [0] (3),, the case of semi-discrete OT. In this setting, one of the two distributions discrete and the other continuous. The OT problem, while being natural proxy to the continuous case, is then slightly simpler since (i) it reduces to the estimation of Laguerre cells and (ii) the curse of dimensionality is alleviated 45).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Related works. The incorporation of entropic regularization for OT was pioneered in the discrete setting by Cuturi [T6], showing that the Sinkhorn algorithm [53] can efficiently solve the EOT problem. Sinkhorn leads to e-accurate OT plan in (n /s²) time when both measures have n points [19] However, the poor dependence on e, observed both theoretically and empirically, motivated annealing strategies (also called e-scaling), which gradually decrease the regularization during optimization to
better approximate the true OT solution. Such schemes appear to significantly improve performance in practice 34 48 20), but their theoretical analysis remains largely open [52] 48 [2]. From statistical perspective, it has recently been shown that decreasing the regularization is not only computationally beneficial but also statistically necessary when using EOT: [45 demonstrate in the semi-discrete setting that with / samples from the source and target measures, taking = 1/vl allows one to achieve a minimax-optimal (11/vt) rate for OT map estimation, thereby escaping the curse of dimensionality without assuming smoothness of the transport map. Their analysis leverages and builds upon the entropic map estimator convergence results for entropic potentials 1 g
developed [5
In parallel, there has been increasing interest in solving semi-discrete OT problems, where the source distribution is continuous while the target measure is known and discrete 22
[54. In low dimensions. 31 have been proposed, offering highly efficient methods for solving the semi-dual problem. higher dimensions, or when the source measure is only accessible via samples (24] propose solving the semi-dual formulation of semi cemi-discrete (E)OT using an SGD scheme. SGD solvers are a natural choice here since they are well-suited for large-scale applications: they can operate in an online setting using one sample at time without storage requirements, and they avoid discretization bias. The study of SGD and Averaged SGD (ASGD) for solving the semi-dual of EOT was further investigated in [5] revealing, however, prohibitive constants in terms of 1/E and higher. This study shows that, as in the discrete case, the use of entropic regularization introduces computational trade-off.
when the source density is fully known, Newton-type solvers [3
35
Contributions. We introduce DRAG (Decreasing Regularization Averaged Gradient), an SGD- based algorithm for solving the non-regularized semi-discrete OT. DRAG employs decreasing entropic regularization scheme decaying with the sample count, aiming to have the best regular- ization/accuracy trade-off at any time. While matching the computational and memory efficiency of vanilla SGD, DRAG attains superior convergence compared to fixedrreullarization methods by exploiting the enhanced properties of the entropic semi-dual without incurring adverse dependencies on the vanishing regularization. Concretely, given iid samples from the source measure, DRAG achieves rates up to (1/tt) for both the OT cost and the potential. A key technical result (Lemma 2) underlying DRAG is that, within an s-ball around the optimum, the entropic semi-dual with regularization satisfies a restricted strong-convexit property independent of e. DRAG is designed to remain, with high probability, within this e-ball, even as e decreases. Furthermore, by analyzing the difference between the Laguerre cells induced by the true OT potential and our estimate, establish ((1/Vt) convergence rate for the OT map. Both our theoretical analysis and numerical experiments confirm the benefits of decreasing regularization incorporated in DRAG.
Notations. We note || || the Euclidean norm, and for C C Rd. De == supf || - yll : I. C) denote its diameter. For a, h E R, a V b == max(a, b) and a A b == min (a,n(a,b)) b}. For v E Rd. Umin == minigjgd Vy. 1a and 0₂ denote the vectors (I,..., 1) and (o....,.)) 0) in IRd ARu is the Lebesgue measure in Rd. P(RR) is the set of probabilities in Rd, and for p E P(Rd). Supp(p) is its support. O(-) and o()) are the usual approximation orders. We use f S g if there exists constant C 0 such that f(-) < Cg(-). We write a x b if both a X and S a.
2 Behind Stochastic Approximation for Optimal Transport
2.1 Background on (Entropic) Optimal Transport
Given a source and target probability measures μ4, v P(RR), a cost function e: Rd Rd + R+ and a regularization parameter ε 2 0, the Entropic Optimal Transport (EOT) problem is
(TH(H,)) == min [
xell(u..) J c(x, ((=.))d((..)) +
In
dp 3 v (R. do(x,)); y). (1)
dm
Rd
where TTp, v) is the set of joints probability measures on Idd x Rd with marginals μ and v. Mild conditions on μ., and the cost can be made so that this problem is well-posed, see (56). When 0.

---

Problem T recovers the Kantorovich formulation of OT. In this article, we focus on the quadratic cost c(z, y) | v/|², although some of our results can be extended to other costs. Our analysis relies on the semi-dual formulation of the convex problem ① given by
- -I f(x)dp(x) -
/ fo (v)dr()),
O))
min SEC(R4)
(2)
where for all E R",
minlzeRd c(a, - f(x) if 8= = -E log (Jzuen exp ((a)) du(xx) if 8
(x)
Under mild conditions on the cost densities, positive makes the semi-dual formulation 1/s- smooth [7]. The key property of this semi-dual formulation of (E)OT to retain more convexity than the standard dual of I (see 28 (5)).
Optimal map and Brenier's theorem. We consider the quadratic cost, E and v having second-order moments. Under the additional assumption that the measure is absolutely continuous, the optimal potential f*. called Kantorovich potential, is (locally) Lipschitz and the map
(x) x (xr)
pushes forward onto // (see 8). In addition, Tu is the gradient of a convex function. This optimal map has more importance than the OT cost in subfields of machine learning such generative modeling 29 36 or domain adaptation [1]..
2.2 Semi-discrete OT
Semi-discrete (E)OT is when the source measure is absolutely continuous and the target measure شーー
wydy, is finite sum of M 2 1 Dirac masses with weights wj > 0. In this case, the semi-dual formulation reduces to finite-dimensional convex optimization problem on R.M
min (g(g) def. - -/e gd (x)d((())
Σ 9y
(4)
8 SERM M
1=1
where for all E Rdd (x)(x) is a (vectorial) (c, -)rtansfoorm with respect to vector g .9M) E R defined by
(x) minje[i,M] 1 - 10ar-y,12- 9j
if E = 0,
le
Σ/ exp -
1112--81 B1
49.
wy
if E > 0.
The vector g corresponds to the value of the potential function at the points y/- For notational convenience, we write Hg(g) f ha (z, g)du(=) with he g) ge (x) ー wy For all E M and given X ~ μr, an unbiased estimator of the gradient is given by
V g Vg,,(X,g)) = w, + g),,),
1 i M
where for (x.g) E Rdd x R M we have
+ 8 ツı 11 +2;
exp
Wi
(x
+ |1
-gg
Am
exp
Wk
For = = 0, (z, = (x) (x) is an indicator function and we have a partition Rd -U Lg(g). where for all j E [1, M].
Lg(g) { f RR: g"())
1 - 1 9j 93
The convex sets (g) are called power or Laguerre cells and [[ (g) n (g) when / j. By the first-order optimality condition, solving semi-discrete OT amounts to finding such that for all j E [1, MI, (g)) = Wj- Semi-discrete OT a case of application of Brenier's s theorem. Given the optimal potential g" the OT map is (x)
v(g (xr) yj for inside (g").
3

---

2.3 Solving semi-discrete (E)OT with the semi-dual formulation
Exploiting its laite-dimensionll nature, solving semi-discrete OT by optimizing its semi-dual formu- lation has become a popular approach. Notably, Newton methods are highly effective solve Ho in scenarios with low dimensions and known source densities, utilizing meshes to approximate the source density [8 35 31 In scenarios involving arbitrary dimensions or when only sample-based access to the source measure is available, EOT emerges as favored strategy. Notably, to avoid working with a discretized version the source measure, such as with the Sinkhorn Algorithm, [24] recommend employing stochastic optimization to solve (4). Indeed, the semi-dual EOT problem has a convex objective of the form
Hg(g) Ex- (X,,(x(()))))
with X as random variable under μ.. As noted in [24], the main advantage of stochastic optimization algorithms is that they are suited for really large-scale problems, keeping in memory only the discrete measure v. Moreover, avoiding discretization enables unbiased estimation of (EJOT quantities. SGD-based solvers also naturally operate in an online fashion, progressively refining their solutions as more samples become available.
For given fixed regularization parameter e > O, stochastic first-order methods are predominantly employed solve (4) Starting with an initial value go IR M, these algorithms consider at each iteration one or many samples X, ~ I and rely on an update of the form
g = - V g 8x-1)
At time f, the Averaged Stochastic Gradient Descent (ASGD) returns the averaged estimate g, = 1 Ei=o gk, while Stochastic Gradient Descent (SGD) returns ASGD, as an acceleration of 1+1
SGD, has been widely studied in the literature (see 43
and for the specific case of EOT).
Choosing the regularization parameter & for FOT. Approximating the EOT problem rather than the OT one benefits from an enhanced convergence rate, especially in the discrete setting. The introduction of the Sinkhorn Algorithm for solving the EOT problem, as highlighted by [16], has led to resurgence of interest in OT within the Machine Learning community.
The choice of the regularization parameter then becomes practical and/or statistical problem:
1. Selecting the regularization parameter is practical issue that aims to strike an optimal balance between convergence speed and accuracy [9). To address this trade-off, some heuristics, such E-scaling [49], which involves decreasing regularization scheme, employed in the discrete setting, although they lack sharp thcoretical guarantees.
2.
In the dimi-discrete and continuous settings, the initial statistical problem is to determine the number of samples needed accurately approximate the OT quantities. In this line of work, the use of EOT to construct estimators has also been proven to be satisfactory. In this case, studies show that regularization must decrease as the number of samples increases 44 [5). However, discrete solvers do not adjust to the number of drawn points, as the solver is initiated once the points approximate the measures have been sampled.
3 DRAG: Decreasing Regularization Averaged Gradient
3.1 The setting.
We focus here on the one-sample setting of semi-discrete OT. Specifically, we sample from the source measure y and leverage the full information of the discrete measure v. Furthermore, fixing and a E (0, 1]. we make the following mild assumption, already present in [18 45
Assumption 1. We assume that μ E (((R")) has support contained in the convex ball B(0, R) and admits densiry du that is H-Höle continuous and satisfies 0 du < so on its support. We denote by Pa (B(O, R)) the set of such measures.
The target is assumed to be discrete, of the form M ΣM 8gy- with (y1...., VM) B(0, R)

---

3.2 DRAG: A gradient-basse algorithm adaptive to both the sample size and the regularization parameter
To accurately estimate the non-regularized OT cost and map, it is crucial to use regularization parameter that decreases as the number of drawn samples increases. However, no existing algorithm in the OT literature simultaneously adapts to both entropic regularization and sample size. Inspired by e-annealing [9], decreasing regularization scheme from the discrete OT setting, which is known for accelerating the convergence of the Sinkhorn algorithm in practice, and considering that SGI) algorithms are inherently adaptive to the number of samples, we introduce the Decreasing entropic Regularization projected Averaged stochastic Gradient descent (DRAG) to solve the semi-dual (2). Our algorithm employs a decreasing regularization sequence (Ex), and replaces the usual gradient step in SGD with projected step using adaptive regularization
Projc (g--1 - v Vhe (X(,
where for U' C AR convex, we define the projector Projy (g) == arg min -g'll E U}. This method can be interpreted as decreasing bias SGD scheme. For such a method, employing projection step be highly effective in ensuring convergence [13] [3). In the context of EOT with bounded cost, is well established that the (c, -ttransform enables the localization of 11o1 ball, where a minimum of the semi-dual problem lies [40]. Specifically, since sup(c(z, y e J E [1. M]] < 2R by Assumption a preliminary projection set can be expressed as Co. : 0, 2 M and we know that we can search for a minimum in this set. Nonetheless, leveraging the regularity of the cost function, we can have projection set with unique optimizer, as described in the following Lemma.
Lemma 1. (Proof in Appendix
B.6 Under Assumption 7 for all 2 there exists a unique solution g. to in C. == [g E RRM :9 0 and lgyl < R1yy1 My Vl E [1,
Note that the choice Φ1 is arbitrary. In what follows, we refer to C = Co or C = Cu as our projection set. Note that for both sets, the projec- tion's 's computational complexity is only (M), as it involves merely clipping each coordinate of our vector.
Algorithm DRAG
Parameters: (Y1 a, b.
Initialize go E C. go go. Eo 1.
for to f do
* カ
X μ
Finally, we consider the Decreasing Regular- ization projected Averaged stochastic Gradient descent (DRAG) defined by
= Projc (gi 7 Vgher (X gx-1))
g 1+ gk k- 8 8k-1
5k k-
g: =
g:
++1 B
end for return g
++1
with Eo = go. The pscudo-code of our algo- rithm is given in Algorithm [ main advantage of DRAG is its OdtM)) computational complexity and ((dM) spatial complexity, which make it well suited for large-scale problems.
3.3 Key properties of the semi-dual He for the design of DRAG
The design and convergence analysis of DRAG rely on two fundamental properties of the semi-dual objective H.. First, the fast convergence of entropic potentials ensures that the optimal solution does not change abruptly as the regularization parameter varies. Second, the enhanced Restricted Strong Convexity (RSC) of Ht around its optimum. These two properties are crucial to the construction of DRAG and are detailed below.
Convergence of the entropic potentials. The following result from 18 establishes that the convergence of entropic optimal potentials is faster than linear g E. Note that this result is only given for the quadratic cost and is, therefore, the limiting factor in our analysis for broadening the class of cost functions for DRAG.
Proposition 1. /Corollary 2.2 [18I] For 0 < E' S under Assumption 7. there exists constant Ko, notably depending on the characteristics of v, such that for any a' E a),
gg. - S Koea' (E (E'E
5

---

The constant Ko can depend on the souree measure μ., through the radius R and the constants 12, m, such that m, du < m2 on its support, see Remark 2.1 in [18]. However, terms depending on Ko will be asymptotically negligible in the analysis of DRAG.
Note that, the semi-dual H has the invariance (g) H(g al.) for any g E RM and IR. Therefore, the minimizer g" of the semi-dual is unique only up to a transformation of the form g:, +al Mr where a E R. Consequently, our analysis the orthogonal complement the subspace spanned by 1 M. denoted as (ect(1M))* For simplicity, for g, E ERM, we denote for p E [1, oo]
|gg g'l Ipp = g g'llg Vect(1u)**
(g g') (g. g') Vect(Im)**
Global and local Restricted Strong Convexity. The convergence behavior of gradient-based methods is central topic in convex optimization. The Restricted Strong Convexity (RSC) condition [58] offers a strictly weaker alternative to strong convexity while still providing comparable guarantees in many settings [58] 50]. The following lemma characterizes the RSC of Hg. Notably, while the global RSC constant on C scales linearly with E the local RSC in a neighborhood of radius e/2 around the optimum becomes independent of e. This motivates the decreasing regularization scheme in DRAG: by gradually reducing e, we ensure that iterates remain within regions where the improved convexity properties can be fully exploited.
Lemma 2 (Global and local RSC of He proof in Appendix
For any E (0, 1]. under there exists P. > O independant of e, such that for all EC.
B.7
Assumption ?
P+ 2cx
8
(1
(1-6-
11-c
llg
B:ll
if fgg - g.1 > 8
g -.) 2
P. (1-6-1)
l1g -.
g:l
8 if fg g. s 2
Here, P. provides a lower bound on the strong convexity constant of H. restricted to the subspace Vect(1-), and it holds uniformly over (0, 1] (see Theorem 3.2 in [18 for further details).
3.4 Convergence rate of DRAG
Convergence rate before averaging. The following proposition provides a key high-probability control, ensuring that the iterates g: remain uniformly close to the optimal potential ge, all times t.
Proposition 2. (Proof in Appendix B.5 Under Assumption 7 with μ E (B R)), taking the
parameters (71, b) of DRAG such that 71 0, b E (2. 1). with constraints 2a b, +
1,1 a + aa > 26, we have for any > 0 and every q > 0,
P (lgg: g. 2 E.) S t (b-22))4
This result is key leveraging the locally enhanced RSC of H., and guides how quickly the regularization can decay. When b > 2a, it yields a convergence rate of o(t") for all p. This proposition leads the convergence rate of the ave-averd DRAG iterates stated in Theorem [
Dependence on b, and a. As we can see, the convergence rate depends on a, b from DRAG and the Hölder regularity. While the constraints may seem difficult to interpret, setting arbitrarily close to 1 (denoted a = 3 and b = a. ensures that the constraints are satisfied for any a E (1/2, 1] and 3 the best converge rate for DRAG in our convergence analysis.
Theorem 1. (Proof in Appendix B. any a' E (0,
Under the same assumptions as in Proposition 2 we have for
1 p. {2a+2aa
E [lgg 1oa--g112
g017]
S
+
121.
Remarkably, we achieve a convergence rate without any undesirable dependence on regularization. In contrast, [5] derived a convergence rate of the form (0 for a fixed regularization, with at least equal 1. Note that having no adverse dependence on the regularization parameter a key necessary characteristic of DRAG, which aims to solve the non-regularized OT problem at fast rates. This is indeed the case here, and there is no trade-off with the choice the admissible and since the result holds for all 0.

---

Enhanced convergence rate with averaging. In convex stochastic optimization, it is known that averaging SGD iterations can lead acceleration. More precisely, ASGD can adapt to the possibly unknown local strong convexity of the objective function at the optimizer
E 3 and achieve optimal (1/tt) converge rates, Despite the fact that our objective function changes at each time i, Theorem 2 shows that DRAG fully exploits the acceleration thanks to averaging.
Theorem 2. (Proof in Appendix (.2) Under the same assumptions as Theorem min 2a 200") ). we have for all o' (0,
7 noting s =
E | g -g'1 4
The rates again depend on 6, and a. The key message here is that by taking a = and 6 = we recover the optimal (1/tt) rate for any a E ( ( 1].
4 Optimal Transport cost and map estimation with DRAG
In the previous section, we established the convergence rate DRAG to the OT potential. While this result was central to our theoretical analysis, our final objective is to estimate the OT cost and transport map. Leveraging the convergence rate the potential, we derive estimation guarantees for these key OT quantities.
4.1 OT cost estimation
Corollary (Proof in Appendix min(1, 2a + 2aa'), we have
B.4 Taking the same assumptions as Theorem with
1
E (o((g) Ho( S
(5)
Once again, when a > 1/2 and setting rate, which is optimal for strongly convex objectives. This rate is obtained by leveraging the locally enhanced RSC property and our adaptive decreasing regularization scheme. The fact that Ho is locally smooth, as noted in Theorem 4.1 of 32). also plays a crucial role in the proof of Corollary
and b 3 we achieve an (11/t) convergence
4.2 Brenier map estimation
When employing entropic regularization, a popular choice to approximate the OT map involves using the estimator of the entropic Brenier map [44] TE (z) = x Vgg Indeed, for g E IR Te u.v (x) could serve as an estimator. The objective is then to find an accurate estimator, g, close g and analyze its performance based on the bias-variance decomposition
TT (g) (g) S I1 (g) T (g)) +
using the fact that IIT,,,, TH. (x.))
(445 Theorem 3.4). However, the mapping
-+ Th Th (g) is = complicating the bias- trade-off given that e, = t-a Instead, we rely on the gradient computed thanks the c-transform of the estimator g, DRAG. In fact, for any z E Rd, if there exists j E [1, M] such that æ is in the interior of (gyg") L,, (.), we have (r) = x (z). Indeed, no matter whenever x E Rd is in the interior of L, (g), the gradient of g is given by
[1 f1
(g) arg max k 2
ykl12 93 = yn.
(6)
By analyzing the differences of Laguerre cells partitions between Lgg,) and L(g"), we derive the following theorem.
Theorem 3. (Proof in Appendix
B.3 Under the same assumptions as Theorem 7 defining for all
E Rd and time 2 0 T(g.) (x)
Vg.. min(1, 2a 20x'), }. we have for all 1 S p
1
E TTp. Tu (B:))())))())) t2/2
7

---

When > 1/2, setting matches the rate obtained algorithm that refines its estimate online, whereas their approach relies on the Sinkhorn algorithm in a batched setting. Note that, unlike our method, theirs achieves the optimal rate for any a E (0, 1). However, the use of online algorithms is crucial in high- nigh-dimensional applications where data is sampled sequentially, such as in generative modeling. In such settings, although the source measure is not compact, it is often chosen to be the standard Gaussian, which has Lipschitz density and therefore corresponds to the case a = 1.
and b 3. we recover an O(IvV)) convergence rate. This but in our case it is achieved in the one-sample setting with an
45
5 Numerical experiments
Convergence rates of DRAG synthetic data. We numerically verify here our convergence rate guarantees through various examples. For each example, we know the theoretical OT map, cost, and discrete potential. The first two examples are similar to those in (45) In all figures and experiments, we set the parameters of DRAG to e = 0.1/1" a = 0.33, b = 2/3, 71 = Diam(Suppla numerical investigation found that our parameter selection is robust without further hypertuning.
Our
Examples settings: (1) μ U( 1]'0",, Supp(v) fu, = ( MMM 2 ..... 2).
E [1, M]].
1 1 : .M- = 1000. (2) μ ((00, 1]100) ). M 30 and 01,-.., Var randomly generated in [0, 1 M
We then also randomly generate g" E R:30 and approximate w with Monte Carlo (MC), such that y the discrete optimum potential. This setting led to non-uniform weights, with wmin = 0.001. (3) a U([6, 1 o)). 8 0.5, Supp(r) = k [1, M]]. w
M M. M 1000.
Ecomple
Docmpie 2
Example 3
16
10
1011
DC 1/v
10-2
10"
10-2
1/1
110
10
10-4
(Hugg)) Hiiiil
38-5
100
10
1000
300003
Iterations
Inerations
Iterations
Figure 1: Convergence rate to the OT potential, cost and map for Examples 1,2 and 3.
In Figure 1 we show the convergence rates of the OT cost, map, and discrete potential. As we can see, our theoretical rates are matched for all OT quantities. The higher variance in the OT cost estimations in Example 3 is likely due to the use of 10 Monte Carlo samples approximate H, which introduces an additional approximation error beyond the one caused by DRAG alone.
Dependence on the dimension. For DRAG, the ambient dimension of the measures does not change the convergence rate but the number of points M does. This is due the fact that, with the semi-dual formulation, we solve an expected minimization problem, and the dimension is then the number of points of our discrete measure. For instance, changing the dimension from 10 to d = 1000 does not change the convergence rate. However, one wants to approximate continuous OT with semi-discrete OT and DRAG, the accuracy the approximation of the continuous measure with M points will depend on the dimension and thus will have an impact on DRAG.
DRAG compared to fixed regularization ASGD. In Figures and we compare the effectiveness and robustness of decreasing vs. fixed regularization schemes. Figure 2 shows that DRAG consistently outperforms projected ASGD with various fixed regularization values, achieving a better trade-off between convergence speed and solution quality. Fixed schemes either converge to biased solutions when regularization is large or fail to converge in time when is too small (e.g., E 5 10-3). This highlights DRAG's advantage during the entire optimization process and supports the idea that starting with high regularization and gradually reducing it yields more stable and accurate solutions in semi-discrete optimal transport. Figure shows DRAG's robustness to the decay parameter both a = 0.3 and a 0.5 yield similar convergence, indicating low sensitivity. All decreasing regularization variants also clearly outperform the non-regularized projected ASGD, While all
8

---

regularization schemes eventually converge with more iterations, DRAG remains one to two orders of magnitude more accurate, due its improved start visible both figures (see Appendix A
107
10
Emn
0. 0.0
10"0
ASGD, Boed
10-1
DILAG, f (uappt
10000
100030
100
1000
100000
Irecations
Figure 2: DRAG compared to ASGD with fixed regularization on Example 1.
Figure 3: DRAG, with different decreasing regularization rate 6 0.1/t 1 on Example 1.
Generative modeling task. We illustrate the practical benefits of our solver in the context of generative modeling. In [2], semi-discrete OT used to map a simple prior onto encoded data points in latent space, with the goal of reducing mode collapse. To generate new samples, they approximate semi- discrete OT map from standard gaussian to the pirical distribution of encoded data points in the latent space and then apply specific interpolation scheme to obtain a continuous mapping from prior to latent space. We replicate their pipeline on toy datasets from their repository [27]. replacing their ADAM- based solver with DRAG, using the same number of samples. As we can see, while both solvers yield good results the "swissroll" target data, DRAG outperforms the ADAM solver on the "spiralarms" data, being able almost completely generate whereas ADAM shows poorer coverage. Since the Gaussian is not compactly supported, this setup falls under Assumption 1 and DRAG was run without projections. This further underscores its robustness in more general settings.
DRAG grr-rtderateed
Adamgenersted
Figure 4: Comparison of DRAG and ADAM for a generative model task
Quantiles. We visualize our OT map estimator on a concrete example of Monge-Kantorove (MK) quantiles [IT]. In this context, having target measure v to investigate, the source measure is set to be the uniform measure on the unit Euclidean ball ~ U(B(O, 1)). Given the OT map T (or its approximation), Tp. (B, k/10)) for E [1, 10] define MK quantile regions. We used M = 10 points to approximate v. discrete version of a boomerang-shaper measure and benchmarked DRAG against two OT solvers that solve semi-discrete OT: Online Sinkhorn [37]. using the EOT map estimator and Neural OT [33] DRAG and Online Sinkhorn used 10" source samples; for the latter, the entropic regularisation under one minute. Neural OT, following Appendix B of 333 processed over 10s samples using a three hidden layers MLP, was times slower, even on a A100 GPU. Figure displays the estimated MK quantile regions of the target measure v. color-coding each centered annulus region. As visible in the figure, DRAG is the only method producing an unbiased estimate of the MK quantiles, fully covering the support of v while keeping every MK region convex, expected in theory.
tuned
10- Both ran in
(a) Source
(b) Target
(c) DRAG
(d) Online Sinkhorn
(e) Neural OT
Figure 5: Comparison of Longe-Kantorovice, quantiles approximation with different solvers

---

Additional experiments. The appendix presents further experiments that, while not affecting our theoretical results, may benefit practitioners. We show that mini- batching with GPU acceleration and weighted averaging of iterates g: can significantly speed up the algorithm. We also compare DRAG to Adam on synthetic data, highlighting its superior performance.
6 Conclusion
In EOT, decreasing regularization parameter naturally appeals practitioners who employ annealing schemes to accelerate Sinkhorn-like algorithms. Similarly, in the statistical community, regularization that decreases with the number of samples is preferred for more accurately approximating true OT quantities. With our algorithm, DRAG, we show that these two motivations for decreasing regularization can successfully coexist by proving that decreasing entropic regularization scheme can indeed improve the convergence rate, whereas it was only a heuristic beforehand. Moreover, we prove that DRAG achieves optimal convergence rates: (1/tt) for both the OT potential and cost, and (( for the OT map. These rates are obtained by leveraging decreasing regularization as a form of acceleration. To the best of our knowledge, this is the first algorithm in the OT literature that adapts to both regularization strength and sample size. Our results also motivate further investigation of decreasing regularization in (i) discrete OT, by adapting our approach to demonstrate the acceleration benefits annealing schemes, and (ii) semi-discrete OT, by developing new optimized versions of DRAG, such as those incorporating adaptive step sizes in similar way to Adam Adagrad.
7 Acknowledgements
The work of François-Xave Xavier Vialard partly supported by the Bézout Labex (New Monge Problems), funded by ANR, reference ANR-10-LABX-58.
References
[1] J. M. Altschuler, J. Wiles-Weed, and A. J. Stromme. Asymptotics for semidiscrete entropic optimal transport. SIAM Journal on Mathematical Analysis, 54(2):1118-1741, 2022.
[2] 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.
[3] Bach. Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. The Journal of Machine Learning Research, 15(1):595-627, 2014.
[4] F. Bach and E. Moulines. Non Non-stronglyycom gence rate o (1/n). Advances in neural information processing systems, 26, 2013.
smooth stochastic approximation with conver-
[5] B. Bereu and J. Bigot. Asymptotic distribution and convergence rates of stochastic algorithms for entropic optimal transportation between probability measures. Annals of Statistics, 49(2): 968 188-987,22 2021.
[6] Bigot, R. Gouet, T. Klein, and A. Lopez. Geodesic pea in the wasserstein space by convex pca. In Annales de I'Institut Henri Poincaré (B) Probabilités et Statistiques, volume 53, pages 1-26, 2017.
[7] N. Bonneel and J. Digne. A survey of optimal transport for computer graphics and computer vision. Computer Graphics Forum, 42(2))439 2023. doi: https://oiiorr//00 1lgl.. httpt::tt///mmiiioe
eettarryyylllee http////.ooom//b///a////1/111111 . 14778
[8] Y. Brenier. Polar factorization and monotone rearrangement of veltor-valued functions. Com- munications on Pure and Applied Mathematics, 44(4):375-417, 1991.
[9] M. Buze, J. Feydy, S. M. Roper, K. Sedighiani, and D. P. Bourne. Anisotropic power diagrams for polycrystal modelling: efficient generation of curved grains via optimal transport, 2024.
[10] Y. Chen, M. Telgarsky, C. Zhang, B. Bailey. D. Hsu, and J. Peng. A gradual, semi-discrete approach to generative network training via explicit wasserstein minimization. International Conference Machine Learning, pages 1080- PMLR, 2019.
10

---

[11] V. Chermozhukov, A. Galichon, M. Hallin, and M. Henry. Longee-kantrovvie depth, quantiles, ranks and signs. The Annals of Statistics, 45(1):223 220-226, 2017.
[12] L. Chizat. Annealed sinkhorn for optimal transport: convergence, regularization path and debiasing. arXiv preprint arXiv:2408. I1620, 2024.
[13] K. Cohen, A. Nedić, and R. Srikant. On projected stochastic gradient descent algorithm with weighted averaging for least squares regression. IEEE Transactions on Automatic Control, 62 (11):5974-5981, 2017.
[14] N. Courty, Flamary, and D. Tuia. Domain adaptation with regularized optimal transport. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2014, Nancy, France, September 15-19, 2014. Proceedings, Part 14, pages 274-289. Springer, 2014.
[15] N. Courty, R. Flamary, D. Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 185) 2017. doi: 10. N0.1109/PAAM..216.2260 5921..
[16] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances In Neural Information Processing Systems, 26, 2013.
[17] M. Cuturi and G. Peyré. Semidual regularized optimal transport. SIAM Review, 60(4)9941-965, Utt.pstps://do. owg/oo..//.. 10. 1137/1881111885544
2018. doi: 10. 1 137718M12086633
[18] A. Delalande. Nearly tight convergence bounds for semi-discrete entropic optimal transport. In International Conference On Artificial Intelligence And Statistics, pages 1619-1642, 2022.
[19] Dvurechensky, A. Gasnikov, and A. Kroshnin. Computational optimal transport: Complex- ity by accelerated gradient descent is better than by sinkhorn's 's algorithm. In International Conference On Machine Learning, pages 1367-1376, 2018
[20] J. Feydy. Geometric data analysis, beyond convolutions. Applied Mathematics, 2020.
[21] J. Feydy, B. Charlier, F.-. Vialard, and G. Peyré. Optimal transport for diffcomorphic registra- tion. In M. Descoteaux, L. Maier-Hein, A. Franz, P. Jannin, Collins, and S. Duchesne, editors, Medical Image Computing and Computer Assisted Intervention MICCAI 2017, pages 291-299, Cham, 2017. Springer International Publishing. ISBN 978-3-319-66188
[22] A. Galichon. Optimal transport methods in economics. Princeton University Press, 2018.
[23] C. Geiersbach and G. C. Pflug. Projected stochastic gradients for convex constrained problems hilbert spaces. SIAM Journal on Optimization. 29(3):2079-2099 2019.
[24] 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.
[25] A. Genevay, G. Peyré, and M. Cuturi. Learning generative models with sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, pages 1608-1617. PMLR, 2018.
[26] A. Godichon and B. Portier. averaged projected robbins-monro algorithm for estimating the parameters of truncated spherical distribution. Electronic Journal of Statistics, 11(1): 1890-1922 1927, 2017.
[27] Y. Guo. pyomt: A pytorch implementation of adaptive monte carlo optimal transport. https //ithub. wwwm///cuu//pppeee ppypT//yyyTTT/////m 2024. Accessed: 2025-05-07.
[28] J.-C. Hütter and Rigollet. Minimax estimation of smooth optimal transport maps. The Annals of Statistics, 49(2), 2021.
[29] V. Khrulkov and I. Oseledets. Understanding ddpm latent codes through optimal trans- port. ArXiv, abs/2202.07477, 2022. URL htRl/hhtts://appp 246863713
sel.aapiicmmatncchooclarr. hwtpaattiiiicilaaaooooroorrllllo Iorg/CrrusII:

---

[30] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arX.v:1412.6980, 2014.
arXiv preprint
[31] J. Kitagawa, Q. Mérigot, and B. Thibert. A newton algorithm for semi-discrete optimal transport. Journal of the European Mathematical Society, 21, 03 2016. doi: 10.4171/JEMS/89.
[32] J. Kitagawa, Q. Mérigot, and B. Thibert. Convergence of a newton algorithm for optimal transport. Journal of the European Mathematical Sociery, 21(9):2603-266 2019.
[33] A. Korotin, D. Selikhanovych, and E. Burnaev. Neural optimal transport. arXiv preprint arXiv:2201. 122200, 2022.
[34] J. Kosowsky and L. Yuille. The invisible hand algorithm: Solving the assignment problem with statistical physics. Neural Networks, 7:477 1994. URL lntpt:tt////// api semanticscholar
:96673444 6967348
[35] B. Lévy, A numerical algorithm for l2 semi-discrete optimal transport in 3d. ESAIM: Mathe- matical Modelling and Numerical Analysis, 49(6): 1eet11196----11 2015.
[36] Z. Li, S. Li, Z. Wang, N. Lei, Z. Luo, and D. X. Gu. Dpm-ot: a new diffusion probabilistic model based on optimal transport. In Proceedings of the ieeelcvf international conference on computer vision, pages 22624-22633, 2023.
[37] A. Mensch and G. Peyré. Online sinkhorm: optimal transport distances from sample streams. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829566.
[38] Q. Mérigot. A multiscale approach to optimal transport. In Computer Graphics Forum, volume 30, pages 1583-1592. Wiley Online Library, 2011.
[39] A. Mokkadem and M. Pelletier. generalization of the averaging procedure: The use of two-time-see scale algorithms. SIAM Journal on Control and Optimization, 49(4):1523-1543, 2011.
[40] M. Nutz and J. Wiesel. Entropic optimal transport: Convergence of potentials. Probability Theory and Related Fields, 184(1-2):401 1244, 2022.
[41] M. Pelletier. Asymptotic almost sure efficiency of averaged stochastic algorithms. SIAM Journal on Control and Optimization, 39(1):49-72, 2000.
[42] G. Peyré, M. Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-677, 2019.
[43] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 50(4)):33-855) 1992.
[44] A.-A. Pooladian and J. Niles-Weed Entropic estimation of optimal transport maps. arXiv preprint arXiv:2/09, /2004, 2021.
[45] A.-A. Pooladian, V. Divol, and Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In International Conference on Machine Learning. pages 28128-28150 PMLR, 2023.
[46] F. Santambrogio. Optimal transport for applied mathematicians. Progress in nonlinear differen- tial equations and their applications. Birkhauser, edition, Oct. 2015.
[47] G. Schiebinger, Shu, M. Tabaka, B. Cleary, V. Subramanian, A. Solomon, J. Gould, S. Liu, analysis of single-cell gene expression identifies
S. Lin, P. Berube, et al. developmental trajectories in reprogramming. Cell, 176(4):928-99)) -922889943,77 2019.
[48] B. Schmitzer. Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM Journal on Scientific Computing, 41 1443))444444111111 2019. doi: 10.1137/16MI 106018.
URL hhttps://dot org/10../.. 1137 11111/
12

---

[49] B. Schmitzer. Stabilized sparse scaling algorithmss for entropy regularized transport problems.
SIAM Journal On Scientific Computing, 41:A1443-A1481, 2019.
[50] Schopfer. Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions. SIAM Journal on Optimization,
2016.
[51] V. Seguy, B. B. Damodaran, R. Flamary, N. Courty, A. Rolet, and M. Blondel. Large-scale optimal transport and mapping estimation. arXiv preprint arXiv:/711.02283 2017.
[52] M. Sharify, S. Gaubert, and I.. Grigori. Solution of the optimal assignment problem by diagonal scaling algorithms. arXiv preprint arXiv:1104.3888 2011.
[53] R. Sinkhorn. Diagonal equivalence matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4):402-405, 1967.
[54] B. Taskesen, S. Shafieezadeh-Abade and D. Kuhn. Semi-discrete optimal transport: Hardness, regularization and numerical solution. Mathematical Programming, 199(1): 2023.
[55] A. Vacher and F.-X. Vialard. Semi-dual unbalanced quadratic optimal transport: fast statistical rates and convergent algorithm. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JoLR.org, 2023.
[56] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[57] J. Weed and F. Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25, 06 2017. doi: B-E0016......5.
[58] H. Zhang and W. Yin. Gradient methods for convex minimization: better rates under weaker conditions. arXiv preprint arXiv: #rXiv:1303.46455 2013.
13

---

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 main limitations, such the assumptions or dependence specific parameters, are clearly stated in the paper.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are always clearly stated and all the proofs are given in appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: All the settings for the experiments are clearly stated and the parameters of our algorithm are given.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All the code to reproduce our experiments provided in Python Notebooks and attached in a zip file 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 understand the results?
Answer: [Yes]
Justification: The parameters of our algorithm given at the beginning of the Numerical Experiments section, and the example settings 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 run 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:
14

---

Answer: [Yes]
Justification: No specific computing resources are required for our experiments; they can be run any modern machine, without GPU. The only exception is the Neural OT algorithm, which does require a GPU.
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
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]
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Licenses for existing assets
Question: 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?
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 clearly explained in the paper, and the code to reproduce the experiments is provided an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include 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]
Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
15

---

Appendix
Table of Contents
A Additonnal Experiments
17
A.I Mini-batch DRAG.
17
A.2
Weighted Averaging: Maintaining a better trade-of off between averaged and non-
averaged iterations.
A.3
DRAG compared to Adam.
18
A.4
DRAG compared to non regularized ASGD
18
B
Proofs
19
B.1
Proof of Thorem
Convergence rate of the non averaged iterates.
19
B.2
Proof of Theorem
Convergence rate of DRAG
22
Proof Theorem
Convergence of the OT map estimator
25
8.4
Proof of Corollary
OT estimation
26
B.5
Proof of Proposition
High probability being in Big.,
27
B.6
Proof of Lemma
Projection step
31
B.7
Proof of Lemma
Global and local RSC condition of Hg
32
B.8
Other Technical results
34
16

---

A Additonnal Experiments
A.1 Mini-batch DRAG.
As for Vanilla SGD, take advantage of GPU parallelization and replace the gradient estimator using one sample X p
V ggh
by a mini-batch estimator, using n 2 iidd samples X1, XI..., Xns samples of the source measure at once
Sh Se (Xx,
11b
Of course, no matter the choice np.
defines an unbiased estimator of (H
Using mini-batch of size The we suggest multiplying by TTy. as is usual with mini-batch SGD. The following figure shows the acceleration due to mini-batching on Example 1, 2 and 3, while maintaining the same computational time when using GPU. Indeed, each mini-batch estimator has an error an order of magnitude lower than the non-batched ones, even with small mini-batch size of yıp 16.
Esomple
2/1
Exompde
Example 3
10
Eroor
1
g. (minkkhatek)
30.
ur5
30
35031
Figure 6: Comparison of the non mini-batched and mini-batched estimators on Example 1, 2 and 3, ng 16.
A.2 Weighted Averaging: Maintaining a better trade-off between averaged and non-averaged iterations.
I well known that the averaged algorithm can suffer from bad initialization. One strategy to over- _
come this weighted averaging 39 Namely, we replace the averaged estimator g, E+T 2 Sr.
by
log(k 1) gk.
Ek log(k: 1)20
with a parameter w 0. The parameter balances the weights assigned to the estimators ge. As increases, greater importance is given to the more recent estimates, while we retrieve g, when w goes to As for the usual averaged estimators, we can perform the weighted average online, without having to store all the iterates, with the recursion
B
(1)
(1
1
Elso In(k + 1)
In(t + 1)
g
(w)
El In(k: + 1)
In(t + 1)
Bi+1
It is important to note that g!") will have the same asymptotic convergence guarantees g:-
17

---

Example
Esoumple
Example $
20a
10
Bro
lls 8. =''
10
10m"
10
1111
0...
10:
1000
30000
350
1000
1000
300
1000
10000
Iserations
Iterations
Iterations
Figure 7: Comparison between ge. g. and g:
on Examples 1,2 and 3, with w
As illustrated in Figure 7 the weighted average estimator consistently outperforms g.. achieving orders of magnitude better performance in Examples 2 and 3. Note that mini-batch size of 16 was used for all experiments, each repeated 10 times.
A.3 DRAG compared to Adam.
We compare here the performance our algorithm DRAG to that of the Adam algorithm 30 on Example 1, with M E 200, 2000. The experiment
repeated 10 times. For this comparison, fixed the parameters of DRAG to (VM, 1/3, 2/3) and ran the algorithm for 10 iterations. The parameters for Adam were set to 31 = 0.9, 82 = 0.999, and = 10-3 (learning rate/weight decay). As shown in Figure 8 DRAG clearly outperforms Adam on this example, particularly in the early iterations and as the number of points increases.
M 200
M 2000
17
Iresatioss
Iteratinns
DRAG St
Artam
Figure 8: Comparison of DRAG with Adam on Example 1, for different values of M.
A.4 DRAG compared non regularized ASGD
As discussed in the numerical section, we observed empirically that all methods, including the non- regularized projected ASGD, eventually converge to the true solution given sufficient number of iterations. In Figure behavior. Notably, even the non-regularized ASGD converges, albeit much more slowly. In contrast, DRAG converges significantly faster and achieves higher accuracy carlier in the optimization process. Among the DRAG variants, we observe that choices of a 0.2, 0.4 yield the best performance, which aligns with our theoretical analysis suggesting that 3 achieves the optimal convergence rate in this setting, since 6 3. These results reinforce claim from the main text that, while all schemes converge given enough iterations, DRAG remains consistently one to two orders of magnitude more accurate due to its improved
report additional experiments with larger iteration budget to confirm this
performance (see Appendix (A).
Note also that convergence of the non-regularized ASGD encouraging, as highlights that, with a sufficiently large number of steps, the effect of vanishing regularization is not deterrent. Indeed, as + oo, the regularized gradient becomes numerically indistinguishable from non-regularized one, essentially corresponding to the difference between tempered softmax with temperature and
18

---

an argmax. This further supports the view that DRAG serves as an effective acceleration mechanism in the early stages optimization and that by decreasing the regularization, we will not hit plateau.
10
10
10P
10-1
-X
0.4
0.6
0.8
(nom-rog)
10"
10
10
10
Iterationss
Figure Comparison of DRAG with different a and non-regularized ASGD
B Proofs
Additionnal notations.
For any c > we define the function + Ve(t) such that
1 + (T +1)
if 1, if 1,
(T)
(8)
1+ (T
if 1.
For sequence (u))Ee, if 1/2 & N, ug must be understood as " "[:] In all the sequel, we note
A, g: g
Remark that the dependence in / is both in the estimator g: and the optimizer g We also recall that we note De = sup
||g g'll < oc.
EC
B.1 Proof of Theorem
Convergence rate of the non averaged iterates.
Proof. Using Lemma for any t 2 ta we have
A A4t1 A, 27++1 (V (gr, X X g.,) + 5
Let J; denote the filtration generated by the samples XI,..., X₂ iid n. that is F, = (X Xx) and taking the conditional expectation, we have
E [Atti]FF] < A, 2 VVH, (g:), g: Bi.) + 5
(9)
Using Lemma 2 on the restricted strong convexity of He we have
(VH,, - gt.) 2 p1 e -)-g) g", 1 |R.. Re, 150./2
Therefore, have
E E[A Fil < [1- 20=(1 - m A, + [2p (00(11---1)) --1)1 l1s. -t, 12e./2 M, + 572-11
(10)
19

---

Using Proposition 2 for all p and B E (0, 1). there exists Cs,p such that for all t 2 0, B|A! - CR.pp N. o
S CB.pl Op bpta(1-9)) B)p, Therefore,
E [g -2, 1122//2
= [ l| RE, [202e]" /20)
1 Cpppt bpppppppp-ppp
by Markov's inequality
4b with a(3 - 3) < <b (11)
$ c. 5-a(5-3)
taking p b a(3 3)
Note that, since 2a < b.
always choose such that the inequality a(3 3) < holds. Using
the fact that A s D and taking the expectation in (I0), we obtain
E 1 $ [1 2p. (1 e m --
E[4,] + 5%
Ca. Ca.a-al 8
D
Let E, == min (t, 2 S 1 and to == maxfta, b we apply Proposition 5 obtain
E| < exp
2A
Σ
%
D
+
5
+
74 + o(%)).
(12)
imfo++
k=
Applying Corollary the exponential product converges exponentially fast to 0 and an asymptotic comparison gives
5 E[A,] 2p - --1 o(7)) 2 2
p
We conclude by using Proposition 1 using the bound |gg g*ll S 1ta
Proposition Under the same assumptions as in Theorem 7 we have for any a' (0,a)
1
[lg. -011
121.
2 126
flu+
Note that this proposition directly proves Theorem but we decided to split them, to have a cleaner proof of Theorem 1.
Remark:
Proof. We begin by squaring equation
of Lemma
For / la,ar where la,a is defined (5
we have
A 2+1 < (A. 27++1 (Vatie (g., X ).g: g: (g.-)))) +5//411
< < 2 + 4 (Vghe (ge, Xe+1). -g,) + 25
4Arret (Vghe, (g:, X X.t1). g..) +10A, 20 (Vghe, (gi, X 1++1),00 g: g..
Taking the conditional and using Lemma 2
we have
E[A Fil 2 41 - e ) 8., 15
We also use the simple bound
E|B Fi] 2 0.
These two inequalities lead to
E Fi] < [1 4p-(1 - m+41 A + 4p. (1-11-4 - ---1)-+111 11141111 8., 115//22
4- E
(Vhee (gr, X(+1), g: -g;,)² | + 25 + 54
20

---

Using that the gradient norm is bounded by two, we apply the Cauchy-Schwarz inequality to obtain
4 he. (g., X(+1). B²,)² - 16 16 llg. BE,
21 164,7441
Applying Hölder's s inequality yields
21 < Ar1/2,(1-e-))
22p -e-1) 21 7411
21
S (1m1App(11E1) 4px - e-1) 9::1
Summing up these inequalities, we obtain
2 Fel - [1 - 3p- e m Ai 4p- - - 1: 1120//2
212
+ 4p. e Y441
3
+ +2251411
Similarly to the case p = 1, using that TP|| ||ll: B., 2 ex/2) - C3
1- by and that
db
al3 D)
A S D2 for all 1, taking the expectation yields
21
E[A 2 (1 31 + 41 Yet1 25 + 4XC,
D
Again, as in the case p = 1, applying Proposition and Corollary and using that gg, -g'll S e t!+a' concludes the proof.
Lemma 3. Under the assumptions of Theorem there exists a finite time ta depending and o, such that for all f, 2 la,a we have
D41 S., 2 (Vghe, Xe+1). gi g:.) 5
(13)
Proof. By definition of the gradient step at time + 1 and since g E C, we have
A++1 || Be.tz 1|
= ||Proj((:: - 7++1 Vgllo 2glt,,88 (gt, X(+1)) - Be.. 112
< ||g: r++1 Vghe, (gr, Xe+1) g g 112
Then, incorporating the change of optimum between time L and + 1, we get
A < [:: T++ V Vghie (gr, Xx+1) - Be, + ge. Bi.1ill 1|2 g+ 7+ V he (g. X(+1) - -g", 112 + l|g;, ,i,,11 g: 7 V Ville (Be, Xe+1) ge, g., se.t))
Using Corollary 2.2 in 18 (see Proposition
Dp. there exists Ky > 0 such that for any a' EJ0, al lg.., - ge., < Koe?" (E: Ec+11 S Kot Kat- (t- + 1)-a) S aKot (I+a+aad) (14)
For clarity, we define ri == aot=aKot- (L+otaaa) and Rd = (2Dc + 2 + re)r..
Using that for all t, g: E C, and that for x E Rd. g E M | te. (g. x1 s 2, we obtain
A4t g: N++1 V he, (gr X(+1) 1²,1 2 + (2De 2*+1)llg' Be.. || + +l... g...l 11?
|g: Tit1 V Ne. [g X - g: 2 + R.
g: g., 2 2
X gt gr,) + 2 /ighe (gi, Xe+1)112 + R.
A, - (Vghes (g:, X X(41), g:.) + 4n 1 Ri-
21

---

Note that, since we have 1 + + 0a > 2b, we can also take a' E]0, of such that 1 + + aa' > 2b. / is decreasing and tends to For conciseness, we note Consequently, the sequence R
la. = min { 2 R2 S )
(15)
For any 2 la we then obtain the following upper bound of 4++1 in terms of A, and the gradient direction:
1141 A. 27411 (Vglte, (Bi, X ge 82,) + 5-1+1
B.2
Proof of Theorem 2 Convergence rate of DRAG
Proof.
We start with decomposition of the gradient step, similar to (26). By abuse of notation,
note
V 2
and define the following differences:
:= Projc (gt 7k++1 Vglles (Br. Xx+1)) - (gx 7k41 Valee (gk, Xx+1)),
Ex+1 V Hig (gx) Valter Xk+1),
= V Ho(g)) - V Hor (gi))
6. = Ho (g&) - V2 (g: - -6)-
The term Pş represents the difference between the projected and non non-projected steps. Note that C. The term & is martingale difference & representing
Pk 0 if g:: -k+1 hth (gk; the difference between the regularized gradient and its non-biased estimator. оg represents the difference between the ex-reullarized gradient and the non-regularized gradient. 6& represents the difference between the gradient at gi and its linear approximation given by the Hessian at the optimum.
Let [M denote identity matrix of MM observe that for any E
gk++
gō Proje (gk
.++1 V he (gi, Xx+1)) gō
gi: 1 V Vghen (gt Xk+1) gō Pk
incorporating incorporating + incorporating de
ge 7 VHe, (g&) 5o + +7K+1EE+1 pk
gi + V Ho(gg)) +*++10k - gō + 7++1E++1 - Pk
(IM 7 V2) (gi -80) -74+104 + 7441 + 7h4 Ex+1 +
incorporating 6%
Thus, have that
gk
g6)
gk
gh+1
8y + ox + Ek+1 +
Pk
T
Yo++
Observe that there is orthogonal matrix U such that V? = U diag (A1, AM-1; OT There- fore, in the following, we denote
(V2) U diag (AT1 .................... ".....,,.11111 A 1 U U
the inverse of ? restricted to the subspace Vect(1ux) Note that we have
18 Theorem 3.2]
min LLL.M-11
X; 2 P.: for all & 2 0.
Taking all the equalities in (ect(1 that is, considering all our vectors in the subspace V we have
-
gi)
-1 gk Bk+1
-1
6k
t+1
7h+1
++1
k= 0
k=
+
(V2)
Ebt1 +
(v2) -1
Pk
[+1
[+) km0
7h+
k=0
k=
22

---

We will now give the convergence rate for each sum. Note that thanks to the introduction of σ₁. we will directly be able to use the local smoothness and strong convexity of Ho, proved our setting in
22
Convergence rate for
ge+1
[+1
7h+1
8h
Bk
18k
g¹)
(gt+1 g')
7k+1
7h+1
R=0
k=0
8k
g
gk++ g"
7k+1
7k+1
k=0
k=0
1
8o
g"
gt+1
g"
(gk
g
Yx+1
7kk
7/1
7++1
Remark that 7
7 1)-b, Therefore (t
S 271 nn" By Theorem (non-averaged iterates), E [1lg g' x
21
+
P.
1/2
E
gk+1
S v
(1- - Doni- + Vap (t+ 11
1)4/2.
7k+1
P.
K=
We thus have the convergence rate
27
Bk+1
E
S
+
7++1
(t
k=0
Convergence rate for
Ekzo Oz.
2+1
By 33 Theorem 1.3], there exists ball B(g", di) with d1 >> 0 where H is a-Hölder. Therefore, by applying a Taylor expansion of Ho(g) around g". if ga E BBg",, dd)) we have
| S gg g" 11
Otherwise, since the Hessian Ho is uniformly bounded 32 Theorem 1.1], there exists a constant C.
such that for any g C, || H (g) (g") (g gl) Cs.
Since P(ge & Bgg", di = IP gg - g- || d1), we obtain by Markov's inequality
111 |1 = 6 g. B(g .di) + |11 g4 ('((g' .d.))
C2
E I|ge g" 1122aa]
Bilgg. g" 1l12tt2a
12+2a
2A
E
g
g g21l2t2a]
Therefore, using Minkowski's inequality, we have
E
5z
7
+
t+1
k=
k=0
14a
btab
0 (1+1)
S 14a
Px (1 + 1) uiاb
23

---

Convergence rate for 1 1+1 Ek= Sk+1-
We recall that ER+1 = VH (gx) Vgh h (gi Xx+1) and thus [ = O.
Observe that <<2x Sk+1; Se+1 >,] (2x= I (c+ (Fl)) ),}
Ex+1:
Thus, since EB [||&/1|] 2 4 for all k, we have the convergence rate
2
E
Ek+1
V++I
k==
Convergence rate of 1 H+1
Ex= Tk.
Using Proposition
we have uniformly in gi that, for all a' E (0,
|ox|
||V
Hee,, (gx)ll || & et gataa'
Therefore
o
v Vataa
++1
tt1
ta+aa
Convergence rate for F+1
Ph
k=
Take do such that Bgg", do)
C C. Defining VR = Vgh (gk, Xb+1) for conciseness, we obtain
E [[lp& [ E
Projec (gx 7k+1 V&) (gi: -+++ v
E
Proic (gk- 7k+1 VK) (gx Th+1 V - gg 71+ vzec]
Since for any y E C, one has (o--Poje((x))
(2)) 1I S | yllus taking y = gk and since gi 7641 VA &
is satisfied only if [|ga Ye+1
Vx g 1l > do. we have
E 11xlll
[10]
E |1 v 1 lime 7441 Va- 1.
Yh+t Vi - E Iigx
47
d3
2
Me+1
220
29 2 1k+11 |gg 8''1[]]
dj
$
1k+1
p
We thus have
Pk
7++
E
YYk
8
p+
k=0
71
(t + 116
Conclusion.
Finally, summing up all the convergence rates, using Cauchy-Schwarz inequalitt and that (A+ < 2(A² + B²) for any A, B IR we obtain
H'' E.. - -0]) & pālt - 1)2-b +30+2an"
1
1
+
7
P.
Lia
(t+ 1)btah
t+1
p² + 1)26
24

---

Since b > 2a and b+ aa > 2a + 2aa' and so noting min 2a + 20a"), and since the Hessian norm is uniformly bounded, we finally obtain
E
Il
8'llo]]
S 1
B.3 Proof of Theorem 3 Convergence of the OT map estimator
Proof. We show that the convergence rate of g, to gō implies a convergence rate convergence rate for the map estimation. The Brenier map is given by (x)) 46). Theorem 1.17. We thus focus on the convergence of Vgi to V(gā)".
(z); see for instance
For all E [1, [1, if lies in the interior of (g), have
(x) x Vjj
(16)
Therefore, given g.g' E MRM, if there exists j E [1, M] such that is the interior of (L)gg) we have
Vg (z) V(g'
We will now follow arguments from 46). Section 6.4.2. Fix j.j E [L. M] such that j * j' and is
in the interior of (g) L (g'). By definition of the c-transform, observe that L (g) is defined by M linear inequalities the form
(z, My リ₁} S (g.ji'") Рj gy +
2 My
11
2 ||5 12
Similarly, interchanging the role of g. g' and j. j' we have
(a. Us yr) S ag ()' := g'y- 9/و ブ 1111
1oy 112
We obtain that
(g(g) C fo E Rdd a (J' S (z, Uz Us) S ag(j.r))}
Moreover, noting (h1 hM) =g- g': see that
la (f' (..'' - 12g hi1
(17)
We have
(A = ( (g)))) v(g)
" UL,(8)Ly(()
jey
(Lggg)))L(())
Σ u ((IER' ( - vz) S dg(i,j'))) j4l
Under Assumption bounded by dpmax.
μ measure such that Supp(u) B(0, R) and it admits a density djc Thus,
((A)= du
Σ
ARa B(0, R): G'.)) (x. 4n) S ag (i.5'))
jej
< dpmmxx
Σ
(f Z R)O,R):
ag (F'
<
1 2 1 <
Uj -
11 21 })
(z(i"
18 8/l12
j<j
(frE ( R)O,R)
ag ()'
1 yj 1| }).
dg(irj"))
S ddmmx jej
Σ Apd
< Φ S
1uy Usl12
25

---

by the rotational invariance of the Lebesgue measure. Combining this remark with 17 yields
hyl
((A) I dumax Rdd
Σ
luy Ms 2
Similarly, for the L" norm of the map difference, we obtain
El
III (Vg"(+) (gg))()))l (1 S
((Vg())(()))()), (vV vgg) du(()
jej (g))L,(
- Σ
1uy - Vyllag (L, (Ly()))
jzj
dpmmax Rd-1 11u5 リı Villgاnyg hg]
1, リز
< djimax M 1)+00)))2220 2 |M|
So, in particular, there exists constant
Cs > 0, independent of the location of the points yj. which
grows at least linearly in M such that
IIII (+) (g (II (1) S Calgg - g'1l SCAVM g- g'll.
Plugging in the convergence rate of g; to g" concludes the proof.
B.4 Proof of Corollary OT cost estimation
Proof. For any vector g MRM, we recall the definition of [g)) U (g) Rd gx)
for all E [1, MI. L,(g) = g = 2 || V/ 1/ 93
Note that L(g) defines partition of Rd up to æ--ull sets ie. μ (L) (Ly when i i and the convex sets (g) are called power or Laguerre cells. We define the set
K = RR. R MI (Tv(g)) 5}.
Ho is uniformly Ca.a on K That is, there exists constant such that Ho is L-smooth on K Note that the constant depends on pmins R. We refer to [32, Remark 4.1 for more details.
Using Theorem 4.1 in [32 under Assumption I
By the first order condition, have for all E [1. (L)(g")) wy We fix here ö = 10 Wmin-
as ö < Wmin: we have g' E KC. Indeed, at the optimum,
Thanks to the L-smoothness, for any E K we have
L g'1
Ho(g) Ho(g") )1 5
Note that, for any g M and i [.]. the difference of measure the Laguerre cells (g) and [g(g") is at most linear with respect to lgg g"lloo- We refer to Theorem or Section 6.4.2 in 46 for more details.
Therefore, there exists a constant C₁, such that, as soon as lg g || Cr. we have that g E K
This constant depends on 5, Mmax. R and d as in Theorem Using Theorem 2 El g" (11*)) with 8 > 0. Then
E (o,g)) - Ho(g") I|] E [ Ho(g")
1 [g, + E [[H6(g,)
- [,
Ellg - -"
max gEC
Ho (g)
Holg (B[gg)([[[z,ee'""
2
L
Ellg gg ||
max gEc
H (g)
Ho | | -
O (Bile, g 1131)
where the Markov incquality of order was used on |[
26

---

B.5 Proof of Proposition 2 High probability being in Blg.,
Proof. The proof of this proposition relies heavily on the technical Lemma which we state and prove immediately after this proof.
We start with base case at å un 0, which provides initial convergence rate for [[ Then, by an inductive argument, we gradually increase Mrn to improve this rate till the limit when n tends to infinity, namely min(b- a. a.
1-p-aCoo 10,0
Base case (uo = 0). Using Lemma with Aa,t Pa
Ee if c = O, and dat pa
"e,t l if E (0, a]. we have
E & B]AN] 11 7111d0, + CI rét1) + Cz.p Anr -- T2+1-
we obtain the following baseline convergence rate, for all By applying Proposition 5 and Corollary
p > 0:
E|
Tt
Inductive step (improving the rate). Suppose that for some un E min - a, a)), we already
have
E|A S (bp(t-atun)
2c > O, which is positive by construction. By Markov's inequality, we then get for q >
Choose
2 6-a+tun and set d = + un
P(A 2 1 2 PP [ 2 { 2 X 1- (b- -20) t 1d
We take q chosen large enough so that dq p + Consequently, applying Lemma
E B[A S ET 74t de,t + C1 né-11
C2.p Note mitl + o(1
Therefore, if we pick any un+1 (0, baatun) ) applying Proposition 5 and Corollary
we that 2
P E
BJA X
t
As soon as a > Uns we have (b - a + 122/22 > un as a valid range upper range for un+1, so we can take un++1 Un and strictly improve convergence rate.
Achievability for all 8 E [0, min(b a, a})) Finally, note that the sequence defined by uh and #n+11 b-a+wr converges to (b a). showing that every value 5 up to a) can be reached 2
through successive improvements. Since e is the upper bound in Lemma 4 we can continue the limit min (b a, a), so for all 8 [0, min a, a,))), we have
7/66
E A
Using Markov's inequality concludes the proof.
Lemma For any a, O, such that + a + ar > 2b, there exists constants C1,p- C2 only depending on " and such that defining
Px 1 c 40x
40xo Et, ifc= 0, ifc E (0.a).
Aeg
-
we have for any c E [0,a]
E[A < E[A]] (1 7411 + C1.7211) + 7o41 D'' (A, 2 20) 1 + C2 -pt1
7411 (18)
27

---

Proof. Let us fix c E [0, a]. Starting from equation 13 raising to the power gives
1 S (De 2- (Vghe, (g. Xx41). -f) 51
(19)
We note (...t)
p! Tylk!
and apply the trinomial expansion to obtain
( (, (1,5.k) ) A- 2 (Vghe, (gr, X4t1). gī)) 5* 76+1
A 4+1
Σ
(ti*k=p
$ AP - 2 1 7t+1
- (Vghee X X -g)))
2p(p !) nt1 (Vgha, (gt, X(+1). gi) 57
( (j,k)
Σ i..k
Di (-2 (Vghe, (B. -gi))² 5 5
14j+k=p (G200) (p. 221,1)))
We divide the set
S
(p,0,0) (,,,0, 2,1,1))
into the following partition
Pa = (,0,AAAA-00000222000033000000100
Pg == (S) P.)
Pe = (S /2anf(++0//622244000
Pa (S 12an(+++0000<))<4))**)0
Pe (8 pa)n
In what follows, the constants Cg may depend on the constant from the learning rate Y / since will often use the crude bound 7t p+1+k sinptt for k E N. Note, however, that Ae, S 1 for all t. and therefore g X for all q. lo E N, so the constants Cg will not depend on A,, We also introduce, for all p, the constant
3p 1 r
2p 1
Case where ki,j.k) Pa. (i, = (p - 2)2,0):
9 2, 2,2, 0/ 2 (-27041 (Valte, (ge, Xe+1), -g;))²
s 8p(pp 1)2F-1 7221
by Cauchy-Schware
Ap00 2/60-1 + 1et1 pcy
1
s 8p(p 1)
9+11
by Young: q = - P.ci 00
pAP Mot1dae + Ttt1 p
p+1l 1
888 18Tplp 1) P-1
taking C1
An.t 88 (F-(P-1)
11/1
I'p
Datt
< pAP rр
+ Cixepti
-pt p+1
defining C₁1 readily.
1t41
28

---

If (i,j,k) = -p--3p3 -3,
AP
(-2 ge, X(41), -g;))s
p 3,,,
$ A
p-
3
7+11
by Mauchy-Schware
p
2p/3
< 64
Ap
2
p-
p
+ p((- 4)
7et1 2p12
Ap/3
2p/3
1+41
by Young: & == p-3/2 a'
20-2
32I p( 1)(p - 2) (p2r))
1pt1
- p
Tp
+
7241
2p
3daa
taking C2
3A.
32T ,2
S p
I
+ C2
CsA-pti,pt 7441
since $ 1 and
2p-3
S -
3
p
(1,j,kk) = (p - 1,0,1):
p
1,0,1
A,- 1--17241
7+41
Sp
p-1
Cg
5" +
pez
1241
Y6+1
by Young: g p o
(TTpp)
p-1
S p&p
Mti
p+1
taking C3
Anat Tp
Ipp
Ao,t
Itt dost Osdaptl p+1 rp
$ ppp
p+1
defining C3 readily.
If (1,1,A) (0.p;
P ) 0.p.0)
(-27441 (Vghe, (gi,
X141), (g,, g(gi))))))) -gi))"
2
AP
+
203
1++
2p-2
70t1
Cauchy-Schwarz Schwarz and Young q = o/ =
< A M+idda
1
(2PTTp
7-11
2p-1
taking C4
2Ac 2P p
2
M411
I A
+ C1A
since 2p-12 2ppt + 1, and defining C₁ readily.
Case where ki,j.k) E Pb.
We have j + k = such that j + 2k 2 pppt since à + 0. Using the bound Ig. g |l S De, we obtain:
Σ
(-2
(e..)) -g:))² 5 2k
(gr X.+1).
(,j,k)
(...A))P,
S Σ
i.j,k (4D)''' s+2
P
(K..A)EPS
< C5r p+1
defining C₁ readily.
Case where ki.j,k) P..
29

---

Σ
(.1))
p
A
-m+1 (Vgle, (gc, X1+)): -g))
by Cauchy-Schwee Schwarz
i.j
(KA.EEP
Σ
4
71+1 76+1
3-2-2
by Young: q = 14572. 22
{,3)
(1..))EP
(
i 5/2
20(i-2)113 R241
AP 2p l++1
(i.))
P
G...EEP.
Σ (H..A))PP
43
AP
+
1pt1
1 pt1
j 2 so: 2 2) + 2 p +1
i,j)
2
2
s 8 AP + 881
Case where (i.j.k) Pa.
Σ
A (-2++1 (gghe, (gt, X(+1), gt - -g)))² 10/55m2 7
i,j
(HAR)EP
Σ
P
5
by
(,j,k)
(U,.))P
Σ
(1,ik)
P
4
CO
i
p
j/2
D + CB
of
cC
2p
22
7+41
(UJ.))P
by Young: = 1+372: 9 = 3+2k
2/9 it comes o/ = %/- Taking G = Vt
- 11 Since we are only considering cases with excluding the particular case (i. k) (p 2, 1, 1). one
26'19
7/
i,jk k 2 1 (which forces p 2 3) and
can show that the parameter q 2p 2i
2p
2p satisfies
2
2p
2p
S q S
2p - 4 4
3
2p 3
Sq q
1
2
2p
Thus, since q-1 S p- - 2, it follows that
2
2p
2 2p - (p 2) = =
9-
Therefore, using the crude bound E(i.AEE (g,,,) < 3 and defining a constant Co readily, we obtain
Σ
(P) (2))at(( --7++ (Vehe, (g. ,g+ Bii) 5th 1 S S3 + Co
{,j
((..R)EPs
Case where (i.j.k) E P..
Since j = 0. + k = p. and (p 1,0,1) E Pa. we have h 2 2. We use Young's 's inequality with
q= = F. c to obtain
Σ (L..AJEP,
A i 2k
5h
Σ
( AP
- k (14115t) (126-2)
2
i,k
12415
i,k)
p
p
7
(..,k))P,
Σ
P (APr2t + +5- -ritt
2p- 28+2)
i,k)
(K.jk))EP
< 2" 2
1241
+ Crapt1 p+1
since 2p
2p
k
+ 2 2
30

---

Summing up the inequalities, we obtain
4 - A
2phr 1- 7+1 (g. gi)
2p(p 1 1 M+1 (V (8,, X:+1).:--88 - g7)5444
+ AP, 3p +
r
70+11
4P7241 (8P 3 2
ptl 1++1
(Ca C2 + C3) C.Aol C5 + Co + C2)
By convexity of He, taking the conditional expectation gives
E
2p(p 1) 1+11 (Vght, (Bt; Xx+1); gr gi) 5 Fi s 50,
Applying Lemma e E (0, a), we have
recalling that det = Po 1-e 2//cw Et if O. and d = D. 1-e-1
vI Et 10 if
A 2 Moce ifc=
(VH.(g) gi) P+ V2 g gi
(20)
(e ifce (0.a).
Therefore,
2p 70+1 V th, (gr, X(+1), g: -gi) Fr
=- n-1 net ( M1. (gt, X(+1), -gi) [i)
= --2pA m+1 (V H3 (g) ) g: - gi)
by 20
S --2pAcr A + D A.2r Le
using that A < D
We now just have up the inequalities. Fixing r 3p+1 such that 2p + 3p++1 1, 2--1
T,
CL.P 8 + 2P, C2.p 8" +E Ck. and taking the expectation, we have the desired form
S (1 70. + (1p124) + D4 [1a,2r 2c] 1oz0 + A2t 7--
p+1
B.6 Proof of Lemma 1: Projection step
Proof. According to 40 any optimal pair of functions (Fe, solving the dual formulation of
entropic OT with regularization 2 0 satisfies the Schrödinger equations. That is, all E Rd, (y) (f) Moreover, 1| - y/|² R-Lipschitz on B(0, R). Therefore, since by Assumption I we have Sμрр(μ) C BO,, R) and Supp(z) C B(0, R). we can exploit the Lipschitz property of our cost function on B(0, R). Using that the (c, -)-rranfformm has the same modulus of continuity as (see Lemma 3.1 (40)., we get, for all y, 1/' E Rd:
take for
| f (g) (F'()/)) < Rlyy 1/1l-
That is, coming back to the function g. we have for all j.j E [1, Ige ge (1 < R |ly yyr
By writing back our dual potential as a vector, that is g" = (9r))..))))) where for all j e [1. 9; ge (vy), we have
10 93 S Rlly, yy
Moreover, if g" optimizes the semi-dual He. then for any R, the vector g" + +131 optimizes He In particular, g* ge ( which we rename g", optimizes the semi-dual, with gi = 0. Hence, for all j 1,...,M M
1 - 9 - Rl - 8
That is, there exists optimizer in the desired closed convex set.
31

---

Remark: Note that for other costs such as c(z.y) y) || yll which defines the 1- W-sssserstein distance, this projection set can be more relevant. Indeed, this case, the cost is 1-Lipschitz and the projection set depends only on the target measure and no assumption of bounded cost is needed. In this case, the practitioner could choose the index such that gi O, minimizing for instance the Euclidean diameter of the corresponding set.
B.7 Proof of Lemma 2 Global and local RSC condition of H
Proof. For any g E C and 8 [0, 1]. note g, - g s(g g²), where g the minimizer of H satisfying ΣM 9: = Σ M
i=1 I2, and define yp by
9 s E [0, 1] H (g.))
Applying Lemma 5 whose proof is postponed until after this one, we have that
(x) - (s())
max ISJM
Øj 9j -m (x., 8s)
(21)
where for all x E RR (1, g.) - xf(x, 8.) (8. B²)
Using Hölder's inequality with the Hölder conjugates p = 1, = too for ón and Cauchy-Schwarz inequality in [5] for 61, we obtain
g 0c =: =0
max 19) Pes - m go) ISISM
(22)
gill =: 81
Use 8 = 6g or 61 = Since Σ 91 = Eis Fo, to is strictly convex, and therefore, we can divide
by (s(s) to obtain for E [0, 1]
(*)
2 5.
(s())
Integrating between 0 and S and using that So
("
ds In (()((() - In |4"(0) gives (x)
("(s) exp( ( 65) (0) (0))
(23)
Since (s(s) (g g:) T (g.) (g g recalling that pa is the second smallest eigenvalue of H (g:) gives the upper bound
(0) 0 g - g- 1
Then, since (s() (VH.(g.).B g g.) an integration of 23 between 0 and I gives
(VH: 3 p exp( 0))
g 1
(24)
Note that the function d E xo) ! (1 exp(-8)) is strictly decreasing and upper bounded by 1.
If e take d, 22|g ge clee and use the fact that ||g ge x0 S 20cc obtain
1 (1-e-4Ca 40x) l|g g:ll2.
(g). gi> 2 p" ACx0 (1 -
In the same way, for e < 1 and ||g g < / taking 8 d =V2lg g. S 1 we obtain
(VH: g 2 p" (1 e - 1
which concludes the proof.
Lemma 5 (Helping Lemma for the RSC condition of H2). For any C and t E [0, define
g. = s(g -g",, where g is the minimizer of He satisfying EM 9: EM Ge. The function s., defined by
9: [0,1] (g.))
32

---

satisfies
(x)) S -s)
max ISJSM
99s 93 m (x, gs)
Where g(x >i x (I, go) (g: g2.).
Proof. The proof is an adaptation of the proof of Lemma A.2 in [5] For completeness, we recall all the steps of their proof that needed for results. Note that their recent erratum regarding Lemma A.I has no impact on Lemma A.2.
For any RM and E [0, 11, define g: g. + s(g gt), where g is the minimizer of H3g M satisfying Ei=19e 9: = E i= G2 We also define the function yp by
M
s:sE [0, + (g.).
Its first to third-order derivatives are given by
('(s) = (g 8 - g.
<'(x) = (g B H2 (g (())---))-
M
83 He g.)
(s) Σ
(g 8.)) (g 83) (g g B²)x.
dg.0g,00g
kj
Since for all g E R VH. (g) - Ex~a bx (X, +w,
('(s) = (-Ex~M (X, g.)] + w.g - -
-Exup (m gx]] + (w.g g²) defining for all E Rd, "0,,m(xg)) gx) X/ ( E.))
Using that V (z, g) = (diag(x -
we have
ds -
+ (Xx g²).
1 (diag(x
Therefore, using the expression of m yields to
(s)()) Exap (g- (5-=g)) diag(xxxxXx g.) m(X.g.)²
= Exau [x)(
defining for all a E Rd
M
o² 0x g.) Σ
Xi (2, (at-- gE,x) (m(a, (m(x,g)))²
M
Σ X g.) (gt Le, m(x ga))²
A derivation of o² leads (see 15 eq. (A.19).) for more details)
d (z,
0²
Σ Xi(a.g.)(9
gE,)²* 3m(x, (oo.g)))2(1g)))) (x) (m(x,g.))*
ds
M
Σ
x (x, g.) (g: - ge, -m(x, m(x.g.))
i=1
Since (s) = ExxE [ 02 2 g+) conclude
(s)( - _ (s)
|93 93 m (x. gx)
15J5M
33

---

B.8 Other Technical results
Proposition 4. For all g and all a' E (0, we have
(g) (Hu(g) S elto'
Proof. We adopt the decomposition of X from Appendix A.3 of [8. See Figure 1 in [8]] for an illustration of this decomposition. Fix i E (1....,M) M). let c B(0, R) be the support of j4, and choose parameters
7 2/h
B E (0, 1).
Define, for all i E Ml], the function
1
f((z) = -c vi) + =
2/ vill + 9s:
2
and use these to define the following sets:
Hu (g)
Xin+ (g) fi(z) - f1) 2 2nj.
11 Vil
Xi,,- x RR. arg max (z( k, fx(x)= f((x)
11yk Vill 1
Hîj ( E Hy VK & (i.j). f((x) fs(x) 2 fx( + 7 max [1 yull I1ys y/ 11)3
Ain. Ut f ix E Hyy, E {l-mlly リ |1, n112> My |1]|
dej
1/ Vj
BLn = Rd (X U X,n, U A....))
We also recall the point-wise definitions of the regularized and nog-ragularized functions constituting the gradients
exp(fi(z)/e)
(x) Σn exp(fx(z)/s)
xi(x) i = arg max fu (x)).
k
and define the constant
Cy
min 11y U5اl 0.
Error decompasition.
[[VH((g) Ho(lg)l = max / (i - xi) du S1 + 1 + I3 + 14,
with
11 f Ix - Xild 12 = / Xi.
3xx-xlde de,, 13 = / xxi -8-xit xil dp, 11 = f 1xf xil du.
Ix -
Xinn
Bien
Interior regions X and Xin.
For & E Nin one has fi - fg 2 n1(yi - yıll 2 n,,, for every j o i, hence
[xx(x) xi(x) = xi(x)
elite
E etule
Σ Ener elale
Aml elkle
< 0 e nncyle
34

---

In same way, we obtain the same bound if x E X therefore
1 12 0 (e-neyl=)
2. Simple slabs Ai.
Inside one slab Tiş = {o + tdy x E H.J. t [-mlly - 8yll, nllv - 3/ll].. and we have fi(x)
fy(x) = tlyy: Bill for a certain t E [-nllys - Vsll. nlus - Us ll- All other indices satisfy
fa(z) - f((x) - -,7,
Σ kE(G))
elfe- elfe-Sils S (M- - 2)/
Hence
1 -- 1o--:lll-iilll wyllcc + (kg(),)) e(la(0)) = = + O ( (e-oa/l))
(x)
with pε(() = (1 t =////ly - Wzll.
Introduce coordinates x = 2 + tny with naj of coordinate 1. Since fy is Hölder. there exists fz( + To (z, t) with (z, t) < t Note that the function pe - Leso is odd. Writing the Hausdorff measure of dimension 1, we obtain
Ui 9; and 2 E Hsy: the Jacobian of this change such that we can write f tnyy)
by -y
Viz (xi xx)
J
M y w1-ll
pε(() 1120 + O 0(e71/)) (Ju(z) + vr(a,))) di (z)
H2,
1 HH,DBOORR)
'pa(t) - 1,20]
-ollve Myll
(Pe(l) lesol (ll do
H2,0B(O.RR
Ole (/e> (fx(z) + ra(2,))) dt dz)
-nll 2 1 0 B(O, R2)
H2,nB(U.R).
1110 dt O (ne- 1 1y:-
= (n) + ne (n- re/e)
Summing over j + yields
I3 0(1 Onne--alg
3. Corner set BL
As shown in [88) denoting by 0 the maximum angle that can be formed by three non-alignn aligned points of the target measure, each corner that constitutes Biny is included in cylinder of volume at most diam: Bi0, R)) 772. Moreover, there are at most M such corners. Therefore, μ (Bnn)) = (0/2)
O = 017 ) and so
1 = 0
4. Choice of the exponent 8.
35

---

Let a' E a) and pick
8 E
I-a'
1).
Ita
Then 1) = gg(l+a) < st and 1/2 = 23 S Elta' Exponential terms are even smaller, hence
[VH - Hollg) = =0 =0(s)taa)
Proposition 5. Lel (7e)120 and (ve)120 be some positive and decreasing sequences and let (6)) satisfying the following;
The sequence & follows the recursive relation:
51+1 S (1 Yw + m2t1) de + 1141
(25)
with 8 2 and w,
Let " converge to O.
Letto inf (t 2 1 wh+ 1; me S w/.
Then, for all 1. lo, have the upper bound:
1
1
8t S exp Σ
Σ
2a + ôeo)
V[=l-
- +o()).
w
imto+1
Proof. For all t 2 to, since - 2w7++1 + -17/111 S Wh++, one has
6: < (1 wh+11 + - ) 85 + V++17++1
(1-w)) 8co + Σ II
(1 -1-wi wY)) YoMk
i=o++
k1
k=
=:U..t
=:U2,
One can consider two cases:
[t/2] 1 S to and [t/2] to.
Case where [t/2] 1 < to < t: Since uk is decreasing,
U2 S 1oo+l Σ
II (1- (1-w)) 7
k= i=++1
V/g+1 Σ
II wT:)
II (1 w7))
k=to+1iskt1
1=k
M/at1
1-
II i=to+1
(1 (1-w1) wni)
Mttt1
Since va is decreasing, it comes U2 S [1/22-
Case where [t/2] - - to: As in 3) for all m = to + 1..... t, one has
U2 S exp
Σ
Ykek + Vm
kmm+1 I
+
Then, taking m [t/2] 1, comes
[-/2]-1 Σ
1 -M/1/22-1
U2 S exp
-w Σ Ph
Witk
w
A= [c/2]
36

---

Corollary 2. Let (ru)22 and (Vi) be some positive and decreasing sequences and let (ōt)120 be a sequence satisfying the following:
The sequence & follows the recursive relation:
8e+1 S (1 Yw1 + m2+t2 de + 14417041
(26)
with 6, 2 and w, 1) O.
Let 7tt = c,, a with a E 10.
Let bo = inf (1 2 1 w 1; 7/7t S w).
Then, for all 1 N. we huve the upper bound:
6, S - Ui + o(v)).
Proof. Applying Proposition for all & to. we have the upper bound:
62 S exp
7v
Σ
Yakk + ôeo
1=0++
Approximating the sum Eg=to 7 via Riemann sum lower bound for the function I _. and
applying the logarithmic inequality log(1 - x) I x, one can now bound [[ (1 w%) 8 as
II (1 (1-wa (y-w))) 8to S exp i=fo+1
Cy ((t ((+ 1))+1) - (to + 1) 11) Tto Uto
w a
WCy
(1+1)) (1o 10+11 1))-aaa nho Mto
S exp
2
In same way, since
exp
Σ
S exp
(-u2) + 1))
(-
WCq
2
k= [1/2]
we obtain
& S exp (-bwc,t-rg exp
( (We,, 2 Twc, (to + 1) 1))
Σ nalk + 8e + -
Since the product involving exponential terms converges exponentially fast, we finally obtain the desired convergence rate
8, < U4 1 + o(vi).
37


Reviews:
[{"review_id": "God991fZrv", "reviewer": "Reviewer_nRvS", "summary": "Entropy regularisation is one of the most popular methods for computing optimal transport distances. Adding entropy decreases computational time however worsens the approximation. Scaling the amount of entropy to zero should therefore reduce computational time whilst providing a better estimate for the OT distance. This paper analysis the affect of entropy and proposes a scaling of the entropic regularisation which produces a consistent estimate of the OT distance with a rate of convergence.\n\nDisclaimer: due to the length of the paper and the time available to review all NeurIPS submissions I did not check the proofs.", "questions": "See 1-3 in the strengths/weaknesses. And\n4. In Proposition 1, does the constant $K_0$ depend *only* on $\\nu$?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The theory (assuming it is correct) is very nice. I haven't seen this type of result before (although I only work adjacent to the field) and it is definitely useful. The only scaling results I am aware of are heuristic results. The numerical results are good, but the main contribution (in my opinion) is theoretical.\n\nThere were a few parts where I felt the paper was harder to understand than it should have been. For example:\n1. In eq (1) $\\frac{d\\pi}{d\\mu d\\nu}$ is difficult for me to understand. I assume it means $\\frac{d\\pi}{d \\mu\\otimes \\nu}$.\n2. Was the scaling of $\\gamma_k$ in Algorithm 1 ever explained?\n3. How important is the projection in Algorithm 1? I'm understanding it as a thresholding step if $g_{k-1} - \\gamma_k \\nabla_g h_{\\eps_{k-1}}(X_k,g_{k-1}))$.", "was_revised": true, "final_justification": "My comments and scores seem to be inline with the other reviewers so I'm comfortable with my assessment. In short, I thought the results were good and interesting. This is a problem where I'm only aware of heuristics and a more principled approach is valuable. I recommend acceptance.", "rebuttal": "Dear Reviewer,  \nThank you for your positive evaluation of our work and for your questions. We are also glad that you appreciate that our work is, to the best of our knowledge, the first to provide theoretical guarantees for acceleration through a decreasing regularization scheme in OT, whereas this approach had previously been used in the discrete setting only as a heuristic.\n\nPlease find below our replies to the weaknesses you pointed out and the questions you raised.\n\n### **Weaknesses**\n\n1. You are right, it should be $\\frac{d\\pi}{d\\mu \\otimes d\\nu}$. We will incorporate this correction in the final version.\n\n2. While $\\gamma_k = \\frac{\\gamma_1}{k^b}$ with $\\gamma_1, b > 0$ is the standard decreasing step size (learning rate) sequence in the SGD algorithm, as in [1, Equation (1)], it is true that in our case, the decay parameter $b$ depends on $a$ and $\\alpha$ to achieve the best convergence rate. This follows from the convergence analysis of DRAG in Theorem 2, where the optimal rate is always attained for $b = \\frac{2}{3}$ as soon as $\\alpha > 1/2$, as discussed in the paragraph \"Dependence on $a$, $b$, and $\\alpha$\" (l. 224).  \nIn the final version, we will emphasize that the specific scaling of $\\gamma_k$ is motivated by the convergence proof of DRAG.\n\n3. The projection step in Algorithm 1 is indeed a thresholding operation. This step is crucial in the convergence analysis of the non-averaged iterates of DRAG, as established in Theorem 1. In practice, we also find this projection step helpful, particularly during the early iterations, where it can improve both the convergence speed and the stability of the algorithm.  \nIn the later iterations, when the estimator $\\mathbf{g}_t$ is close to $\\mathbf{g}^*$, the thresholding becomes unnecessary and typically does not occur. In the final version, we will further emphasize the usefulness of this projection step, both from a theoretical perspective and in practice, especially in the early stages of the algorithm.\n\n### **Question on Proposition 1**  \n$K_0$ depends not only on the target measure $\\nu$, but also on the source measure $\\mu$, through the radius $R$ and the constants $m_1, m_2 > 0$ such that $m_1 < d\\mu < m_2$. We will update Proposition 1 to reflect this dependence and include a reference to Remark 2.1 in [2].  \n\nAdditionally, we will add a clarification that our choice of $a$ in the decreasing scheme $\\varepsilon_k = 1/k^a$ (used in the convergence rate of DRAG in Theorem 2) ensures that the terms involving $K_0$ become negligible as the number of iterations increases. More precisely, they are of the order $o(||\\bar{\\mathbf{g}}_t - \\mathbf{g}^*||^2)$ and therefore do not affect the leading convergence rate.\n\n### **References** \n\n[1]  Moulines, E., \\& Bach, F. (2011). Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24.\n\n[2] Delalande, A. (2022). Nearly tight convergence bounds for semi-discrete entropic optimal transport.  International Conference on Artificial Intelligence and Statistics (pp. 1619-1642). PMLR."}, {"review_id": "oMntUP0VDM", "reviewer": "Reviewer_fbxE", "summary": "In this paper, the authors propose a new algorithm for solving semi-discrete optimal transport problem, which reduces the regularization parameter while increasing the number of samples from the source measure. The authors provide and prove the estimates for convergence rate of potentials and optimal mappings. The authors provide results of working their algorithms and compare with Online Sinkhorn [1] and Neural OT [2].", "questions": "- Typos?\n    - (l.153) It is not necessary to assume that a continuous function is bounded on a compact set, isn't it?\n    - To what extent does the notational framework presented between lines 202-203 enhance the clarity of the mathematical exposition?\n- Does your analysis of the decreasing regularization scheme generalize to the setting of continuous target measures? Does your scheme of decreasing epsilon while increasing the number of training samples is viable in continuous target measure case? \n- Can the α-Hölder continuity assumption on the density be relaxed while maintaining the convergence properties? Furthermore, does there exist a counterexample demonstrating that this regularity condition cannot be entirely removed?\n- For which costs do the results of the paper remain valid?", "limitations": "The authors have addressed some limitations of their approach in the conclusion. But the authors don’t specify for which costs the results of the paper remain valid. This aspect should be stated as a limitation of their approach.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths.** \n\nThe paper is almost clearly written and provides a complete theoretical analysis of the convergence rate of optimal mappings and potentials.\n\n**Weaknesses.** \n\nMy first concern is devoted to the quality and clarity of the theoretical results. The proofs of many lemmas given in the paper are quite technical, they reduce to consideration of many particular cases, which complicates their verification, and does not allow me to say with full confidence that all the proofs given are completely correct and original. Besides, I am confused by the fact that all of the results only cover the case of the quadratic cost. The line 84 states that some of the results can be extended to other costs, but authors do not specify which exactly and do not state it as a limitation of their approach. I kindly suggest the authors fix this point.\n\nBesides, I am concerned by the limited experimental validation of the proposed algorithm. All of the experiments are conducted in small-dimensional (with dimensionality not exceeding ten) spaces and cover only toy artificial setups, see their Section 5. Thus, It is not obvious for me whether the presented algorithm is scalable or not. I kindly suggest the authors to include some experiments testing their approach  in bigger dimensions to mitigate these concerns. Besides, I am wondering what real-world problems such an algorithm could be used for? I would appreciate it if the authors could conduct or list the real-world experiments where their approach is really effective in comparison with other well-known algorithms. \n\nAdditionally, although this paper is devoted to semi-discrete optimal transport, I am wondering whether the proposed scheme of decreasing epsilon while increasing the number of training samples is viable in the continuous target measure case. The authors have not mentioned this, but I would like to know whether semi-discreteness is a fundamental limitation of this method or not.\n\n**To conclude,** the overall contribution of the paper is questionable for me. Theoretical estimation of the convergence rate (Theorem 3) for optimal mappings is asymptotically equivalent to the estimation from [3] (where it holds for all $\\alpha\\in(0,1)$ while the results of this paper hold for $\\alpha\\geq 1/2$). Thus, I have doubts regarding the originality of the theoretical results presented in the paper as long as practicality and real-world applications of the developed approach.\n\n\n*Typos:*\n\n- The formulation of the dual problem (2) contains typos affecting the correctness of the formulation. Supremum must be used in formula (2) instead of minimum by continuous functions, because it is claimed that expression (1) is equal to expression.\n\n**References.**\n\n[1] A. Mensch and G. Peyré. Online sinkhorn: optimal transport distances from sample streams. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.\n\n[2] A. Korotin, D. Selikhanovych, and E. Burnaev. Neural optimal transport. The 11th International Conference on Learning Representations, 2023.\n\n[3] A.-A. Pooladian, V. Divol, and J. Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In the International Conference on Machine Learning, 2023.", "was_revised": true, "final_justification": "*Why not higher score?* DRAG has certain restrictions limiting its practical usability. 1) DRAG is designed only for the quadratic cost, 2) it seems to be hard to generalize it for the case of continuous distributions, 3) its scalability remain questionable for me.\n\n*Why not lowet score?* The paper proposes a new approach and presents a good combination of its empirical verification and supporting theoretical results.", "rebuttal": "Dear Reviewer,  \nThank you for your detailed feedback and constructive comments. We also thank you for pointing out some typos such as the one regarding equation (2), they will be corrected in the revised version. \nWe adress each point below.\n\n### **Weaknesses**\n\n1.   We acknowledge that several of the proofs are technically involved, and we sincerely appreciate the time and attention you dedicated to reading through them. We would like to emphasize that, to the best of our knowledge, the proofs are both correct and original, and we have carefully verified their correctness. We appreciate the reviewer's concern and would welcome any specific suggestions that could help improve the accessibility of our proofs.\n\n2. Our results indeed cover only the quadratic cost case, as we rely on Corollary 2 in [1] concerning the convergence of entropic potentials, which we stated in Proposition 1. This result applies only to the quadratic cost. Note that [2] also focuses exclusively on the quadratic cost, as their analysis is similarly based on [1].  \nThat said, the two key technical lemmas: Lemma 1 (projection step) and Lemma 2 (Restricted Strong Convexity) can be generalized to other cost functions. In particular, the lower bound on $\\rho_*$ stated on line 213 is proven for a broader class of costs in Proposition 5.1 of [3].  \nProposition 1, which is restricted to the quadratic cost, is therefore the limiting factor. Generalizing it to other costs would directly enable us to extend our results without modifying the convergence algorithm or the structure of our proof. However, we believe this generalization is technically challenging and constitutes an interesting direction for future work.  \nIn the final version, we will further emphasize that Proposition 1 is the limiting factor and will explicitly state the generalization to other costs as a valuable research direction.\n\n3.  (This reply is mostly the same for both Reviewer fbxE and Reviewer zxMk) We reran our synthetic data experiments (Examples 1, 2, and 3) in dimensions 100 and 1000, instead of 10. We observed the same convergence rate behavior across all experiments with respect to the number of samples, with similar final errors. The experiments were approximately 4 and 15 times slower to run, respectively, which is solely due to the increased time required to compute $c(x, y) = \\frac{1}{2}||x - y||^2$ on our GPU.  \nThis similar behavior in higher dimensions is not surprising in the semi-discrete OT setting, which is known not to suffer from the curse of dimensionality, as shown in [2]. While changing the parameter $d$ does not affect the error in our setting, increasing the number of points $M$ does impact the convergence rate, as we are solving a stochastic optimization problem in $\\mathbb{R}^M$ via the semi-dual formulation.  \nSince our algorithm is SGD-based and has linear memory complexity $\\mathcal{O}(M)$ and computational complexity $\\mathcal{O}(dM)$ per iteration, we believe it is highly scalable.  \nWe will include these comments in the final version and thank the reviewer for highlighting this point. Furthermore, we will replace our synthetic examples in Figures 1, 2, and 3 with their dimension-1000 versions to better illustrate this scalability.\n\n4. For real-world applications, DRAG can be used in generative modeling tasks that rely on semi-discrete OT to improve performance, as in [4] with GANs, [5] with diffusion models, and in statistics for Monge–Kantorovich quantile estimation [7].\nBesides the fact that DRAG has optimal convergence guarantees for semi-discrete OT, we also observed in practice its better performance compared to Adam, which is not tailored for the OT task. As mentioned in our reply to Reviewer Ueg5’s request, we have extended both the generative modeling and Monge–Kantorovich quantile experiments to include more complex and large-scale examples.    \nFurthermore, unlike DRAG, Adam does not come with theoretical guarantees for convergence to the true OT potential and map, to the best of our knowledge.\n\n### **Questions**\n\n1. a) (l. 153) You are correct, the assumption is unnecessary.    \nb) The notational framework on lines 202–203 was intended to emphasize that the optimal potential $\\mathbf{g}^*$ is only unique up to transformations of the form $\\mathbf{g}^{\\*} + a \\mathbf{1}_{M}$, with $a \\in \\mathbb{R}$. Therefore, we conduct all our convergence analysis in the orthogonal complement of $\\mathrm{vect}(\\mathbf{1}_M)$.\n\n2. While extending our results to the continuous setting is an interesting direction for future work, our method fundamentally relies on the fact that the semi-discrete setting leads to a finite-dimensional problem. This property does not hold in the fully continuous setting. Therefore, the semi-discrete nature of the problem is indeed a limitation of our approach.\nThat said, we would like to emphasize that the semi-discrete setting is, in itself, a very interesting and challenging problem with numerous applications. For example, it arises in generative modeling [4,5] and statistics, such as with Monge–Kantorovich quantiles.\n\n3. While our algorithm achieves the best convergence rate when $\\mu$ is $\\alpha$-Hölder with $\\alpha > 1/2$, we still guarantee convergence for any $\\alpha$, as stated in Theorem 2. The condition $\\alpha > 1/2$ is somewhat conservative and arises from our convergence analysis.  \nThat said, we believe that at least continuity of the source measure is necessary, since without that the optimal potential $\\mathbf{g}^{\\*}$ may not be unique, even in the orthogonal complement of $\\mathrm{vect}(\\mathbf{1}\\_{M})$. For example, consider the case where $\\mu = \\frac{1}{2}\\mathcal{U}([-2, -1]) + \\frac{1}{2}\\mathcal{U}([1, 2])$ and $\\nu = \\frac{1}{2}\\delta_{-1} + \\frac{1}{2}\\delta_{1}$. Then, for the quadratic cost, all vectors of the form $\\mathbf{g}_{x} = (-x, x)$ with $x \\in (-1, 1)$ are optimal for the semi-dual problem, even though they all lie in the orthogonal of $\\mathrm{vect}(\\mathbf{1}_M)$.\n\n4. (Cost question) see weakness 2. \n\n### **Comparison with [2]**\n\n While [2] provides statistical guarantees for the approximation of the semi-discrete OT map and establishes that an optimal rate of $\\mathcal{O}(1/\\sqrt{t})$ is achievable, this is done by discretizing the source measure using $t$ points and employing the discrete entropic OT map as an estimator, with entropic regularization $\\varepsilon \\simeq 1/\\sqrt{t}$.\n  \nTheir work offers strong statistical guarantees for OT map estimation, provided that the discrete OT map is accurately computed. However, it focuses on an offline setting where all $t$ samples from the source measure are stored, and a discrete entropic OT problem is solved. The analysis is limited to sample complexity, specifically the statistical bias between the semi-discrete and discrete entropic OT maps. The computational complexity of Sinkhorn required to accurately approximate the OT map is not discussed, even though it typically scales poorly with $\\varepsilon^{-1}$. Moreover, in this offline or multi-pass setting, increasing the number of Sinkhorn iterations does not correspond to using more samples. \n \nIn contrast, our paper directly tackles the semi-discrete OT problem without introducing discretization bias. We propose an algorithm that operates in an online (single-pass) setting, does not require storing past samples from the source measure, and demonstrates that decreasing regularization can indeed accelerate convergence for OT algorithms. Their paper provides stronger statistical guarantees, achieving optimal rates for $\\alpha \\in (0,1)$, whereas our results apply to $\\alpha > 1/2$. However, we directly solve the semi-discrete problem, avoid discretization bias, and offer a scalable algorithm with linear computational and memory complexity per iteration.\n\n### **Overall contribution of the paper**\nWe would like to emphasize that, while decreasing regularization is a popular heuristic in optimal transport, DRAG is, to the best of our knowledge, the first algorithm in OT where acceleration due to decreasing regularization is formally proven. Prior to our work, theoretical guarantees that a decreasing regularization scheme can indeed accelerate the convergence of an OT algorithm remained an open question.  \nWhereas a fixed regularization typically leads to a complexity that depends adversely on $\\varepsilon^{-1}$ in OT algorithms, our approach achieves convergence rates without such adverse dependence, thanks to the careful design of our regularization schedule. This theoretical benefit is reflected in practice, as shown in Figure 2, where DRAG outperforms all fixed regularization baselines.\n\nWe hope that our response has clarified the originality and significance of our work. We appreciate the reviewer’s time and hope they find the revised explanations helpful.\n\n### **References**\n\n[1] Delalande, A. (2022). Nearly tight convergence bounds for semi-discrete entropic optimal transport.  International Conference on Artificial Intelligence and Statistics (pp. 1619-1642). PMLR\n\n[2] A.-A. Pooladian, V. Divol, and J. Niles-Weed. Minimax estimation of discontinuous optimal transport maps: The semi-discrete case. In the International Conference on Machine Learning, 2023.\n\n[3] Chizat, L., Delalande, A., \\& Vaškevičius, T. (2024). Sharper Exponential Convergence Rates for Sinkhorn's Algorithm in Continuous Settings. arXiv preprint arXiv:2407.01202.\n\n[4] An, D., Guo, Y., Lei, N., Luo, Z., Yau, S. T., \\& Gu, X. (2019). AE-OT: A new generative model based on extended semi-discrete optimal transport. ICLR 2020.\n\n[5] Li, Zezeng, et al. \"DPM-OT: a new diffusion probabilistic model based on optimal transport.\" Proceedings of the ieee/cvf international conference on computer vision. 2023."}, {"review_id": "yZ1UmV0S66", "reviewer": "Reviewer_XDRF", "summary": "The authors study the unregularized optimal transport (OT) problem with quadratic cost in the semi-discrete setting, where the source measure is continuous and the target measure is discrete. They focus on the semi-dual formulation, which yields a convex optimization problem, and analyze the convergence properties of single-pass (online) stochastic gradient descent algorithms applied to the entropy-regularized formulation when the regularization parameter is reduced during the iterations according to an annealing schedule. When averaging over iterations, the authors establish convergence rates of O(1/t) for both the OT cost and potential, and O(1/\\sqrt{t}) for the OT map, where t denotes the iteration count. These results hinge on proving that a regularization-free restricted strong convexity property holds locally within a ball around the optimum, and on showing that the algorithm's iterates remain within this region with high probability. Numerical experiments on synthetic data are provided to support the theoretical findings.", "questions": "A) In the related works section of the introduction, the authors write that “decreasing the regularization is not only computationally beneficial but also statistically necessary,” referring to the results in [45]. However, as far as I can tell, [45] does not show that decreasing regularization is truly necessary. They only show that a method using this approach can reach the best possible rates, which is just one way to succeed, not the only one. Could the authors please clarify what kind of necessity they had in mind?\n\nB) Proposition 2 (before averaging) seems to require some restrictions on the Hölder continuity parameter \\alpha, e.g. 1/2 < \\alpha \\leq 1, while Theorem 2 (which uses averaging) seems to allow for weaker conditions, e.g. 0 < \\alpha \\leq 1. Could the authors explain why averaging leads to this improvement?\n\nC) Overall, I feel the paper does not give enough intuition about why the restricted strong convexity property can hold locally with a parameter that does not depend on the regularization size. Since this seems to be one of the main ideas of the work, I think it deserves a clearer explanation. Could the authors say more about this?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Quality and Clarity: The paper is clear and easy to follow, with the main results introduced and explained well. The key ideas are presented in a direct way, and the numerical experiments are easy to interpret. It would be helpful to include more explanation of what causes the main effect being studied (on restricted strong convexity).\n\nSignificance: This work seems to provide the first (?) theoretical guarantees for annealing stochastic iterative schemes in optimal transport.\n\nOriginality: While the paper seems to bring together the idea of decreasing regularization (as in [45]) with a stronger analysis of SGD building from [5], many of the core ideas, specifically showing that a local restricted strong convexity property holds with regularization-independent parameters—seems both original and non-trivial.", "was_revised": true, "final_justification": "I appreciate the authors’ rebuttal, which addressed my questions. I believe this is a good paper and have maintained my positive score.", "rebuttal": "Dear Reviewer,  \nThank you for your positive and constructive feedback on our work. We are particularly pleased that you highlighted the convergence guarantees for decreasing regularization in OT. We also believe this is the first such result. We appreciate your insightful questions and helpful suggestions.\n\n### **Questions**\nA) We apologize for the lack of clarity. What we intended to convey is that, when using entropic OT as in [45], decreasing the regularization with respect to the number of points is necessary to achieve the optimal convergence rate. Using a larger, fixed regularization would lead to a non-optimal bias.\nOf course, an estimator that does not rely on entropic OT could, in principle, also achieve the optimal rate. Although, to the best of our knowledge, no such estimator currently exists for the semi-discrete OT setting. Therefore, while decreasing regularization is necessary when using entropic OT, using entropic OT itself may not be strictly necessary. We will better explain our meaning in the revised version of the paper. \n\nB) We believe this question may have arisen due to a typo in the comment following the statement of Theorem 2, on line 241, where it incorrectly states $\\alpha \\in (0,1]$ instead of the correct $\\alpha \\in (1/2, 1]$. This typo was corrected in the full version of the paper included in the supplementary material. We apologize for the inconvenience.\n Both theorems allow for $\\alpha \\in (0,1]$ and yield a convergence rate. There is indeed an improvement in the convergence rate for the averaged case: when $\\alpha > 1/2$, choosing $a = 1/3^-$ and $b = 2/3$ leads to a convergence rate of $\\mathcal{O}(1/t^{2/3})$ for the non-averaged iterates, compared to the optimal rate of $\\mathcal{O}(1/t)$ for the averaged iterates. \nThis acceleration due to averaging is well known in the context of SGD algorithms [1], where, without averaging, the iterates tend to oscillate around the minimizer due to stochastic noise, while averaging “smooths out” this noise by aggregating information from multiple iterates.\n\nC) We acknowledge that restricted strong convexity is a key property for the success of the convergence analysis of DRAG. In our setting, it holds locally with a parameter that does not depend on $\\varepsilon$, because, denoting by $\\rho^\\varepsilon_*$ the smallest eigenvalue of the Hessian of $H_\\varepsilon$ on $\\mathrm{vect}(\\mathbf{1})^\\bot$, we have a uniform lower bound $\\rho_* = \\inf_{\\varepsilon \\in (0,1]} \\rho^\\varepsilon_*$. In particular, we do not have $\\rho^\\varepsilon_* \\to 0$ as $\\varepsilon \\to 0$.\nThis is due to the fact that, under our assumptions, even the non-regularized semi-dual has $\\rho^0_* > 0$. This provides a form of local strong convexity, stemming from the regularity of the quadratic cost and the uniqueness of the minimizer. Using Theorem 3.2 in [2], we have $\\rho^\\varepsilon_* \\geq \\frac{1}{2}\\rho^{\\*}$ for all $\\varepsilon \\in [0,1]$.\nHowever, while the local restricted convexity is common for all $\\varepsilon$, we see that the area in which it is true depends on $\\varepsilon$, which thus show that when we decrease the regularization, the radius around $\\mathbf{g}_{\\varepsilon}^*$ in which we have a favorible restrcited strong convexity is smaller.  \nWe hope this explanation clarifies the local behavior, and we will incorporate it into the final version of the paper.\n\n### **References**\n[1] Polyak, B. T., \\& Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4), 838–855."}, {"review_id": "AErz7NqAaP", "reviewer": "Reviewer_zxMk", "summary": "This paper introduces DRAG, a stochastic gradient algorithm for solving semi-discrete optimal transport problems.  DRAG employs a decreasing entropic regularization schedule that shrinks with the number of optimization steps and achieves:\n\n1. $O(1/t$) convergence for OT cost and potentials,\n\n2. $O(1/\\sqrt{t})$ convergence for the transport map,\n\nThe convergence is  independent on the vanishing regularization parameter.", "questions": "1. Is the averaging step for the gradient  $\n\\bar g_t = \\frac{1}{1+t} g_t + \\frac{t}{t+1} \\bar{g}_{t-1} $\nessential for convergence, stability, or theoretical guarantees?  How it impacts empirical performance?\n\n 2.We noticed the following potential typos and would like to confirm:\n\nline 111: $T_{\\mu,\\nu}(x)=...=x-y_j$ should be  $T_{\\mu,\\nu}(x)=...=y_j$,\n\nline 241: $\\alpha \\in (0,1]$ should be $\\alpha \\in (\\frac{1}{2},1]$.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengthens:\n\n1. The DRAG algorithm is conceptually simple and easy to implement.\n\n2.The restricted strong convexity argument is technically interesting.\n\n3.Relevant experiments to support claims are included.\n\nWeakness:\n\n1.Some related ideas (e.g., multiscale Sinkhorn, continuation methods) have been considered in fully discrete OT; a clearer positioning relative to those methods would help sharpen the originality claim.\n\n2.Scalability of the method is not rigorously evaluated beyond low dimension ( dimension 10 is shown, but real-world applications could go higher).", "was_revised": true, "final_justification": "**Update**\nThe authors' response addressed my primary concern, I have updated my score accordingly.", "rebuttal": "Dear Reviewer,  \nWe would like to thank you for your time and thoughtful comments. Please find below our responses to the weaknesses and questions you raised.\n\n\n### **Weaknesses**\n\n1.  **Originality of DRAG**  \n\nWith our algorithm DRAG, and in the semi-discrete setting, we provide, to the best of our knowledge, the first theoretical proof of accelerated convergence rates due to decreasing regularization for solving an OT problem in any setting. While the heuristic of $\\varepsilon$-scaling / $\\varepsilon$-annealing [1] in discrete OT has been observed in practice to enhance the convergence rate of the Sinkhorn algorithm, theoretical guarantees that a decreasing regularization scheme can indeed accelerate the convergence of an OT algorithm remained an open question prior to our work.\n\nWhereas algorithms with fixed regularization typically suffer from adverse dependence on the regularization parameter, our use of a decreasing regularization sequence entirely avoids this issue.  \nMoreover, unlike discrete solvers that reuse all samples multiple times (multi-pass), DRAG is adaptive to the number of samples and operates in an online (one-pass) setting, without the need to store past samples. This enables us to solve the semi-discrete OT problem without incurring either discretization or regularization bias.\n\nIn the final version, we will further emphasize these distinctions, highlighting DRAG’s main contribution: it is the first OT algorithm to confirm, through theory, the heuristic (previously only observed in practice) that decreasing regularization leads to acceleration.\n\n\n2. **Scalability of the method** (This reply is mostly the same for both Reviewer fbxE and Reviewer zxMk.) \n\nWe reran our synthetic data experiments (Examples 1, 2, and 3) in dimensions 100 and 1000, instead of 10. We observed the same convergence rate behavior across all experiments with respect to the number of samples, with similar final errors. The experiments were approximately 4 and 15 times slower to run, respectively, which is solely due to the increased time required to compute $c(x, y) = \\frac{1}{2}||x - y||^2$ on our GPU.\nThis similar behavior in higher dimensions is not surprising in the semi-discrete OT setting, which is known not to suffer from the curse of dimensionality, as shown in [2]. While changing the parameter $d$ does not affect the error in our setting, increasing the number of points $M$ does impact the convergence rate, as we are solving a stochastic optimization problem in $\\mathbb{R}^M$ via the semi-dual formulation.\nSince our algorithm is SGD-based and has linear memory complexity $\\mathcal{O}(M)$ and computational complexity $\\mathcal{O}(dM)$, we believe it is highly scalable.\nWe will include these comments in the final version and thank the reviewer for highlighting this point. Furthermore, we will replace our synthetic examples in Figures 1, 2, and 3 with their dimension-1000 versions to better illustrate this scalability. \n\n### **Questions**\n\n1. The averaging of the gradient steps is indeed essential, both theoretically and numerically.\n**Theoretically:** Averaging the iterates leads to improved convergence guarantees, as shown in Theorem 2. For instance, for any $\\alpha > 1/2$, choosing parameters $a = \\frac{1}{3}^-$ and $b = 2/3$ results in a convergence rate of only $\\mathcal{O}(1/t^b)$ for the non-averaged iterates, compared to the optimal rate of $\\mathcal{O}(1/t)$ for the averaged iterates. Moreover, our convergence analysis requires $b < 1$, which prevents us from achieving the optimal $\\mathcal{O}(1/t)$ rate for non-averaged iterates in theory.  Note that acceleration by averagin is classic in the stochastic gradient descent litterature [2]. \n**Numerically:** This difference is also observed in practice. The non-averaged iterates converge at a rate of approximately $\\mathcal{O}(1/t^b)$, while the averaged iterates converge faster and exhibit improved stability. To illustrate this, we will include the errors of the non-averaged iterates in Figure 1, showing that averaging indeed enhances convergence in practice.\n\n2. We confirm that these are indeed typos, and we thank you for pointing them out.\n\n\nWe hope that we have addressed all of your concerns and that the clarifications and improvements above provide a clearer picture of the quality, originality, and significance of our work.\n\n### **References**\n\n[1] B. Schmitzer. Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM Journal on Scientific Computing\n\n[2] Polyak, B. T., & Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4), 838–855."}, {"review_id": "Bprplt1oVB", "reviewer": "Reviewer_Ueg5", "summary": "This paper investigates an entropic-regularized optimal transport (OT) problem between a continuous source distribution and a discrete target distribution--referred to as the **semi-OT** problem. Specifically, the authors focus on the dual formulation of this problem, which reduces to a stochastic optimization task in a finite-dimensional space due to the discreteness of the target distribution.\n\nTo solve this, the authors propose an algorithm named **DRAG**, designed with the following components:\n\n1. The core of the algorithm is stochastic gradient descent (SGD).\n2. The entropic regularization parameter $\\gamma$ is gradually decreased as more samples are observed in an online fashion.\n3. The learning rate is annealed over time -- together with the regularization parameter.\n4. A projection step is applied right after each gradient update.\n\nThe authors prove that, with appropriate annealing for the regularization parameter and step size, **DRAG** achieves optimal convergence rates:\n- $\\mathcal{O}(1/t)$ for both the OT potential and OT cost,\n- $\\mathcal{O}(1/\\sqrt{t})$ for the OT map.\n\nThese convergence rates are also empirically verified in synthetic numerical experiments. Furthermore, the experiments show that DRAG is able to find accurate OT maps in practice.", "questions": "Some questions/suggestions:\n\n- In section 2, the dependence of OT quantities on the cost function $c$ should be dropped if the cost is already quadratic (for example, right after line 102, right after right 107). Otherwise, these equations should be in general forms with $c$ in their formulations.\n\n- The projection step looks unconventional to me. Although it does not hurt to project back to the set that is known to contain the optimal solution, is necessary to do so in terms of theory?\n\n- The paragraph from line 200 to line 202 will benefit from further details and discussion.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n- The theoretical findings are solid: while previous methods with a fixed regularization parameter $\\epsilon$ has a complexity dependent adversely on $\\epsilon^{-1}$, i.e., $O(\\epsilon^{c} t^{-b})$, DRAG -- with a careful design of the sequence of decreasing regularization parameters -- bypasses this dependence. \n\n- The algorithmic design of DRAG is desirable in the context of large-scale learning. Not only it unbiasedly converges to the optimal solution (OT map / OT potential), it is also doing so in an online manner -- using one sample or a minibatch of samples at each iteration.\n\n# Weaknesses\n\n- Assumption 1 requires the target distribution to be discrete with equal weights, which limits the applicability of DRAG. In the experiment on synthetic data, the target distribution in Example 2 has unequal weights. It is unclear to me how DRAG is still valid for this case. \n\n- In the theoretical results, to obtain the optimal convergence rate, they require $a$ to be (very) close to $1/3$ and $b=2/3$ to ensure the flexibility of $\\alpha$. However, this choice has a negative impact. For example, in the inequality right after line 220, the power of $t$ is at the limit of $0$, making that claim vacuous. My impression is that this choice has an overall (negative) trade-off in the optimization bounds and the complexity (that is probably ignored by the asymptotic notations) that deserves a careful discussion.\n\n- I would expect more data sets to be considered in the Generative modeling task and the Monge-Kantorovich Quantiles experiment. Currently, each experiment has only two datasets, which makes the conclusion on the performance of DRAG premature.", "was_revised": true, "final_justification": "The authors have sufficiently addressed my comments. I therefore keep my score.", "rebuttal": "Dear Reviewer,  \nThank you for your positive and constructive feedback on our work. We are particularly pleased that you highlighted the convergence guarantees for decreasing regularization in OT and the use of online algorithm that is suitable for large-scale problems. \nWe address the specific concerns below: \n\n### **Weaknesses**\n\n1. We thank the reviewer for this insightful question.\nIt is correct that our theoretical analysis assumes uniform weights for the target distribution, as stated in Assumption 1. This restriction was made primarily to simplify the convergence proof. However, we believe that the results should still hold when the target distribution has strictly positive but unequal weights, although extending the theory to this more general setting would require additional technical work.  \nIn the revised version, we will make this point clearer and explicitly state that Example 2 was included to illustrate that DRAG continues to perform well in practice even when the uniformity assumption is relaxed.\n\n2.  Since the result of Proposition 2 holds for any $q$, there is no negative trade-off: we can always make the decay arbitrarily fast by increasing $q$, even when $2a$ is close to $b$. Indeed, given any $\\delta > 0$ and any constants $a, b$ such that $2a < b$, and for any $s > 0$, we can always choose $q$ large enough so that \n$$\n-q(b - 2a) + \\delta < -s.\n$$\nWe will clarify this point in the revised version and emphasize that there is no trade-off in the choice of $a$ and $b$ here, thanks to the fact that the result holds for all $q > 0$.\n\n3. We agree that the number of datasets considered in both the generative modeling and Monge-Kantorovich quantiles experiments is currently limited, and that more examples would help strengthen our conclusions.    \nTo address this, we have already extended both experimental sections and will include the results in the appendix of the revised version. In particular, we now provide more comprehensive examples involving 16 different measures for both the generative modeling and MK quantile tasks. Moreover, we use discrete measures with up to $10^8$ points for MK quantiles, emphasizing that DRAG, as an SGD-based algorithm, is well suited for large-scale problems.  \nWhile the rebuttal process does not allow us to include additional figures, we summarize the findings here:    \n- For the generative modeling task, DRAG consistently outperformed Adam-based optimization, especially on more complex synthetic measures, where standard SGD showed instability.    \n- For the MK quantile task, the general observations remained the same: Neural OT performed significantly worse than DRAG , both in terms of coverage and bias, despite being significantly slower. DRAG continued to outperform Online Sinkhorn in terms of accurately covering the support of the target distribution without entropic bias, which aligns with the theoretical expectation of convex MK regions.  \nWe will make sure to discuss these additional results in the final version to provide a more complete empirical validation.\n\n\n\n\n### **Questions**\n\n1. We thank the reviewer for the suggestion. In the revised version, we will present results in general form with explicit cost dependence when possible, especially when introducing the background on (entropic) Optimal Transport in Section 2. We will then specialize to the quadratic cost case only when needed, to enhance clarity and avoid unnecessary notational overload.\n\n2. The projection step in Algorithm 1 is indeed a thresholding operation. This step is crucial in the convergence analysis of the non-averaged iterates of DRAG, as established in Theorem 1. In practice, we also find this projection step helpful, particularly during the early iterations, where it can improve both the convergence speed and the stability of the algorithm.\n\n3.  The notational framework on lines 200–203 was intended to emphasize that the optimal potential $\\mathbf{g}^{\\*}$ is only unique up to transformations of the form $\\mathbf{g}^{\\*} + a \\mathbf{1}_M$, with $a \\in \\mathbb{R}$. Therefore, we conduct all our convergence analysis in the orthogonal complement of $\\mathrm{vect}(\\mathbf{1}_M)$. We apologize for the lack of clarity and will provide a clearer explanation in the final version of the paper."}]

Author rebuttal:

Meta-review: **Strengths:**

This paper provides the first analysis of a method for optimal transport that anneals the entropic regularization. This is a natural heuristic that is already used in practice [20,34,48,49] but the theoretical analysis of this scheme is open [12,48,52].

The paper is well-written.

Many of the core ideas, specifically showing that a local restricted strong convexity property holds with regularization-independent parameters—seems both original and non-trivial (reviewer XDRF)

The algorithmic design of DRAG is desirable in the context of large-scale learning. Not only it unbiasedly converges to the optimal solution (OT map / OT potential), it is also doing so in an online manner -- using one sample or a minibatch of samples at each iteration. (reviewer Ueg5)


**Weaknesses:**

It was not clear to me from reading the reviews and the paper if the O(1/t) rate was novel.

Experiments were relatively small scale.
Decision: Accept (poster)