Non-asymptotic convergence bounds for Wasserstein approximation using point clouds
Authors: Quentin Mérigot
Filippo Santambrogio
Clément SARRAZIN
Venue: NeurIPS 2021 Poster (2021)
Keywords: Optimal transport
Wasserstein distance
Non-convex optimization
Polyak-Lojasiewicz inequality
Lloyd's algorithm
Point clouds

Abstract: Several issues in machine learning and inverse problems require to generate discrete data, as if sampled from a model probability
distribution. A common way to do so relies on the construction of a uniform probability distribution over a set of $N$ points which
minimizes the Wasserstein distance to the model distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. Yet, in most cases, a suitably adjusted version of Lloyd's algorithm in which Voronoi cells are replaced by Power cells, leads to configurations with small Wasserstein error. This is surprising because, again, of the non-convex nature of the problem, which moreover admits spurious critical points. We provide explicit upper bounds for the convergence speed of this Lloyd-type algorithm, starting from a cloud of points sufficiently far from each other. This already works after one step of the iteration procedure, and similar bounds can be deduced, for the corresponding gradient descent. These bounds naturally lead to a sort of Poliak-Łojasiewicz inequality for the Wasserstein distance cost, with an error term depending on the distances between Dirac masses in the discrete distribution.

-as-asympio convergence bounds for Wasserstein approximation using point clouds
Quentin Mérigot
Filippo Santambrogio
Université Paris-Saclay, CNRS, Laboratoire de mathématiques d' d'Orsay, 91405, Orsay, France Institut Universitaire de France
Univ Lyon,
Université Claude Bernard Lyon 1, CNRS
UMR 5208, Institut Camille Jordan
F-69622 Villeurbanne
Institut Universitaire de France
Clément Sarrazin
Université Paris- Sacia-aclly, CNRS, Laboratoire de mathématiques d' O'Orsay 91 91405, Orsay, France
Abstract
Several issues in machine learning and inverse problems require to generate discrete data, if sampled from model probability distribution. common way do so relies on the construction of uniform probability distribution over set of N points which minimizes the Wasserstein distance to the model distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. Yet, most cases, suitably adjusted version of Lloyd's algorithm in which Voronoi cells are replaced by Power cells - leads to configurations with small Wasserstein error. This surprising because, again, of the non-convex nature of the problem, as well as the existence of spurious critical points. We provide explicit estimates for the convergence of this Lloyd-type algorithm, starting from cloud of points that are sufficiently far from each other. Our estimates are tight when the algorithm is initialized from an point cloud that is evenly distributed the ambient space. Similar bounds can be deduced for the corresponding gradient descent. These bounds naturally lead to modified Poliak Foliak-Lojasien Lojssiewicz inequality for the Wasserstein distance cost, with error term depending the distances between Dirac masses in the discrete distribution.
Introduction
In recent years, the theory optimal transport has been the source of stimulating ideas in machine learning and in inverse problems. Optimal transport can be used to define distances, called Wasserstein or earth-mover distances, between probability distributions over a metric space. These distances allows one to measure the closeness between a generated distribution and a model distribution, and they have been used with success as data attachment terms in inverse problems. Practically, it has been observed for several different inverse problems that replacing usual loss functions with Wasserstein distances tend to increase the basin of convergence of the methods towards good solution of problem, even to convexify the landscape of the minimized energy [8] 77. This good behaviour is not fully understood, but one may attribute it partly to the fact that the Wasserstein distances encodes the geometry of the underlying space. A notable use of Wasserstein distances in machine learning is the field of generative adversarial networks, where one seeks to design neural network able to produce random examples whose distribution is close prescribed model distribution (2).
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Wasserstein distance and Wasserstein regression Given two probability distributions p. l on R the Wasserstein distance of exponent p between p and μ a way to measure the total cost of moving mass distribution described by / to j,, knowing that moving unit mass from x to y costs || yll".
Formally, is defined as the value of an optimal transport problem between p and j.:
W Wp(p = (TEl(pp))) / ||= v1l'dT(z,)))
1/r
(1)
where we minimize over the set [p, 14) of transport plans between p and μ,, i.e. probability distributions over IR Rd with marginals p and μ. Standard references on the theory of optimal
transport include books by Villani and by Santambrogio [21 [2 (0], while the computational and
statistical aspects are discussed in survey of Cuturi and Peyré [17].
In this article, we consider regression problems with respect to the Wasserstein metric, which can be put in the following form
min WP WP (T) EEB
where j is the reference distribution, a probability measure on [0, 1J", is the model distribution, a probability measure on R and where T. : [0, 11 - IR a family of maps indexed by a parameter 0 E θ. In the previous formula, we also denoted # the image of the measure l under the map To. also called pushforward of μ under Tg. This image measure is defined by (B) := (TT (B)) for any measurable set B in the codomain of Tg. In this work, we will concentrate on the quadratic Wasserstein distance W2. Several problems related to the design of generative models can be put under the form (2) see for instance 9 2 Alternatively, in some occasions (4) and initially [88), extracting uniform quantization can be used an intermediate step in k- k-means clustering. Let note briefly here that our estimates do not make assumptions on the absolute continuity of the sampled measure and are therefore valid in this fully discrete case. In any case, solving 2 numerically is challenging for several reasons, but in this article we will concentrate on one of them: the non-convexity of the Wasserstein distance under displacement of the measures.
Non-convexity of the Wasserstein distance under displacements. It is well known that the Wasserstein distance is convex for the standard (linear) structure of the space of probability measures, meaning that if vo and 11 are two probability measures and V4 = (1 1)1o + (v,, then the map t e [0,1] + WZ p) is convex. Using a terminology from physics, we may say that the Wasserstein distance is convex for the Eulerian structure of the space of probability measures, e.g. when one interpolates linearly between the densities. However, in the regression problem (2), the perturbations are Lagrangian rather than Fulerian, in the sense that modifications of the parameter 0 leads to displacement of the support of the measure Ta This appears very clearly in particular when μ is the uniform measure over a set X (Z1,.... ENN of N point in [0, 1]d, ie. μ = 6x with
N
8x def
8Z1-
N
In this case To p is the uniform measure over the set Tx(X) (To( To(xn)), i.e. To (x). In this article, we will therefore be interested by the function
1 FN : Y E (R + W (0,6y).
(3)
2
This function Fx is not convex, and actually exhibits beemi-)ooncavity properties. This has been observed first in [1] (Theorem 7.3.2), and is related to the positive curvature of the Wasserstein space. A precise statement in the context considered here may also be found Proposition 21 in [5]. A practical consequence of the lack of convexity of F'y is that critical points of FN are not necessarily global minimizers. It is actually easy construct examples of families of critical points YN of FN such that Fv (N)) is bounded from below by a positive constant, while lim +00 min FN = 0, so that the ratio between Fv (Yx) and min EN arbitrarily large as N + +o0. This can be done by concentrating the points YN on lower-dimensional subspaces of RRd as in RemarksBandd
When applying gradient descent to the nonconvex optimization problem (2). is in principle possible to end up on local minima corresponding to high energy critical points of the Wasserstein distance,

---

Figure I: From left to right, point cloud Y in the square 52 = [0, 1] x [0, 1/. the associated power cells P,(Y) in the optimal transport to the Lebesgue measure on Ωt the vectors -NVEX(XY)) = BY - y followed during the Lloyd step and the positions of the barycenters Y = (Y).
regardless of the non- con-lincay of the map 0 + tu Our main theorem, or rather its Corollary 6 shows that if the points of Y are at distance least from one another, then
1 Nga-I SNIVE
(x C
In the previous inequality, /V (Y) denotes the Euclidean norm of the vector in RN obtained by putting one after the other the gradients of F'y w.r.t. the positions of the atoms y:- We note that due to the weights 1 1/N in the atomic measure ōy, the components of this vector are in general of the order of 1/N, see Proposition I. This inequality resembles the Malyaa---jjaieiiir inequality, and shows in particular that if the quantization error FN (Y) (2 8y) is large, i.e. larger than (2-d/N. then the point cloud Y is not critical for Fx. From this, we deduce in Theorem 7 that if the points in the initial cloud are not too close to each other at the initialization, then the iterates of fixed step gradient descent converge to points with low energy FN, despite the non-convexity of FN.
Relation to optimal quantization Our main result also has implications in terms of the uniform optimal guantization problem, where one seeks point cloud Y (y1, ................................ yN) in (IRd) such that the uniform measure supported over Y, denoted ōy, is as close as possible to the model distribution with respect to the 2- Wasserstein distance:
min (Y). YERR
4
The uniform optimal quantization problem 44) is a very natural variant of the (standard) optimal quantization problem, where one does not impose that the measure supported on Y is uniform:
min GN(Y), where GN E (IR))N + min Y Y
W? HEAN
P.
(5)
and where AN C R is the probability simplex. This standard optimal quantization problem is cornerstone of sampling theory, and refer the reader to the book of Graf and Luschgy [1] and to the survey by Pagès [16]. The uniform quantization problem (4) less common, but also very natural. It has been used in imaging to produce stipplings of an image 15 3 or for meshing purposes [10] A common difficulty for solving (5) and (4) numerically is that the minimized functionals FN and GN are non-convex and have many critical points with high energy. However, in practice, simple fixed-point or gradient descent stategies behave well when the initial point cloud is not chosen adversely. Our second contribution a quantitative explanation for this good behaviour in the case of the uniform optimal quantization problem.
Lloyd's algorithm [13 is fixed point algorithm for solving approximately the standard optimal quantization problem (5). Starting from a point cloud y = (vf,-. v E (RRd)N with distinct points, one defines the next iterate y* in two steps. First, one computes the Voronoi diagram of Y, tessellation of the space into convex polyhedra (V.(Y* )))ssN)),,, where
Vi(Y) (x E Ω Vj E (1, | vill s ||x -
In the second step, moves every point yy towards the barycenter, with respect p, of the corresponding cell V,(K)). This algorithm can also be interpreted as a fixed point algorithm for
3

---

solving the first-order optimality condition for (5), i.c. (Y) = 0. One can show that the energy (Gx(Y")) decreases k. The convergence of y towards a critical point of Fy as - +o0 has been studied in [6]. but the energy of this limit critical point not guaranteed be small.
In the case the uniform quantization problem one can try to minimize the energy PN by gradient descent, defining the iterates
yk+1 y TNVFF(YY".
where is the time step. The factor N in front FN is set as a compensation for the fact that we have, in general, VFN O1/NN). When = 1, one recovers version of Lloyd's ss algorithm for the uniform quantization problem, involving barycenters By (Y) of Power cells, rather than Voronoi cells, associated to Y. More precisely, Proposition proves that FF) = (Y (Y))))/ so that y = Bx(Y when = 1. Quite surprisingly. we prove in Corollary 4 that if the points in the initial cloud Y are not too close each other, then the uniform measure over the point cloud Y = yu NV Fx (Y obtained after only one step of Lloyd's algorithm is close to This is illustrated in Figure M We prove in particular the following statement.
Theorem (Particular case of Corollary 4). Let p be a probability density over a compact convex set Ω S RR, let Y (yf.... v S2d and assume that the points lie at some positive distance from one another: for some constant
Vi j. v11 cN-1/4
corresponding for instance to point cloud sampled a regular grid. Then, the point cloud -NV obtained after one step of Lloyd's 's algorithm satisfies
W p) S Ce
where Ce.d,1 is a constant depending on c, d and diam([).
Outline Section 2 we start by a short review of background material on optimal transport and optimal uniform quantization. We then establish our main result (Theorem B the approximation of a measure p by barycenters of Power cells. This theorem yields error estimates for one step of
Lloyd's algorithm in deterministic and probabilistic settings (Corollaries and 5). In Section 3
establish a Polyak-Lon Lojyak--jssiewiic-typee inequality (Corollary 6) for the function FN Y + 1 W3 (p. dy
introduced in (3), and study the convergence of gradient descent algorithm for Fv (Theorem 7 Finally, in Section 4 we report numerical results on optimal uniform quantization dimension d= d=2 2.
2 Lloyd's algorithm for optimal uniform quantization
Optimal transport and Kantorovich duality this section we briefly review Kantorovich duality and its relation to semidiscrete optimal transport. The cost is fixed to c(x, y) =| | assume that p is a probability density over a compact convex domain Ω. In this setting, Brenier's theorem implies that given any probability measure μ supported on Ω the optimal transport plan between p and j., i.e. the minimizer æ in the definition of the Wasserstein distance (T) with p = 2, is induced by transport map Tμ Ω Ω, meaning æ (Tμ, Id) p. One can derive alternative expression for the Wasserstein distance using Kantorovich duality, which leads to a more precise
y11² and
description of the optimal transport map (00 Theorem 1.39]:
/ odu
/ d'dp,
(2. H)
max o:Y +R gd
(
where (x) min, c(z, B1) o. When 8y is the uniform probability measure over point cloud = (y1,..., yN) containing N distinct points, we set o. = o(y.) and we define the ith Power cell associated to the couple (Y, v))
Pow,(Y,6) = (x E Rd
| - 11 di < || wzll² -z)-
Then, the Kantorovich dual 8 of the optimal transport problem between and 8y turns into a finite dimensoimensional concave maximization problem
w2(
max DER
from:(Yss)) (1 wil12 - 0i) d)(())

---

By Corollary 1.2 in [2], vector & IN is optimal for this maximization problem if and only if the potential is such that each Power cell contains the same amount of mass, i.c. if
1
vi E Ny, p(Pow, N
(10)
From now on, we denote P.(Y) = PY, Φ) n where á E R satisfies (10) The optimal transport map Ty between P and dy sends every Power cell P.(Y) the point yt. i.c. is defined
p-almost everywhere by Ty P.(Y)
We refer again to the introduction of [2 for more details.
Optimal uniform quantization In this article, study the behaviour of the squared Wasserstein distance between the (fixed) probability density p and a uniform finitely supported measure 5y where
Y (11..... ......... .UN) is cloud of N points, in terms of variations of Y. As in equation (3). we denote Fx = (p..). Proposition 21 in [13] gives an expression for the gradient of F, and proves its semiconcavity. We recall that F is called a-seemiconcave, with o 2 0, if the function F - 2 concave. We denote y the generalized diagonal
DN = (Y E (R4) 3i #j yr = =y}}.
Proposition 1 (Gradient of Fx). The function FN is -eemicooncvee on (R4) and is of class C² on (IR N N In addition, one has
1 AY E (RA) A DN, VFN(Y) = N -
where Bx = =(b((Y)....b>(>))) (11)
and where bY) is the barycenter of the ith power cell, i.e. by(Y)) = N Sp,(r zdp(x).
It is not difficult to prove that FN admits at least one minimizer, and that this minimizer Y satisfies the first-order optimality condition Y Bx point cloud that satisfies this condition is called critical.
Remark 1 (Upper bound the minimum of FN). We note from 15 Proposition 12] that when p is supported on a compact subset of IR, then
-
if 2
min Fny
min YE(RA
v W3(p,or)
log
if [ 2 if d 1.
(12)
Remark (High energy critical points). On the other hand, since FN is not convex, this first-order condition is sufficient have minimizer Fy. For instance, if = on the unit square f? = [o, 1]² can check that the point cloud
((2))) YN (( 2N 2
3
2N - )
2N
2.N
a critical point of Fy but not minimizer of Fx. In fact, this critical point becomes arbitrarily bad as N + +oo in the sense that
Fx(YN) +00.
lim +00 min FN
On the other hand, note that the point cloud YN is highly concentrated, in the sense that the distance between consecutive points in YN is 2N. whereas in an evenly distributed point cloud, one would expect the minimum distance between points to be of order N-
Gradient descent and Lloyd's algorithm One can find critical point of Fy by following the discrete gradient flow of FN, defined in 77. starting from initial position y e (IRd) Dy. Thanks to the expression of FN given in Proposition [ the discrete gradient flow may be written as
k+1 yk + (T((BN(( y*),
(13)
5

---

where TN is fixed time step. For TN = 1, one recovers a variant of Lloyd's algorithm, where one moves every point to the barycenter of its Power cell P; (Y* at each iteration:
y = BN (Y**))
(14)
We can state the following result about Lloyd's algorithm for the uniform quantization problem, whose proof is postponed the appendix.
Proposition 2. Lel N be fixed integer and (Y*))20 be the iterates of (1). with yo & D Then, the energy k + (Y*) is decreasing, and limg->+oe [ = O. Moreover, the sequence (z2 belongs to a compact subset of (R4) \ Dy and every limit point of a converging subsequence of it is critical point for Fn.
Experiments suggest that following the discrete gradient flow of Fy does not bring us high energy critical points of FN. such as those described in Remark 2 unless we started from an adversely chosen point cloud. The following theorem and its corollaries, the main results of this article, backs up this experimental evidence. It shows that if the point cloud Y is not too concentrated, then the uniform measure over the barycenters of the power cells, (Y), ,, is a good quantization of probability density i.e. it bounds the quantization error after one step of Lloyd's algorithm (14
We will use the following notation for 0:
(VY (i (1...., N) Vj # 1, yy 2 e)
DN,= = {Y E (d 3i + j. 11:/ M2 E Note that D, is an E-neighborhood around the generalized diagonal DN-
Theorem 3 (Quantization by barycenters). Let Ω C Rd be compact convex set, p probability density on and consider a point cloud Y (U1,..., .NN 22 \ TTx. Then, for all <es1,
W3 (p. ()) & Ca. (
E (s1-d
+1 Card(4((X)))
(15)
N
N
where Ca.
224-1 (!)) + 1)d+1 and where wa-1 is the volume of the unit ball in IR-1
Wa
The proof relies arguments from convex geometry. In particular, we denote A a B the Minkowski sum of sets: A + = {a + b (a, b) A x B}.
Proof. Let o' R be the solution to the dual Kantorovich problem (00) between p and ōy. We let o' = =o and we denote p = Pow,(X (Y, o') n L the ith Power cell intersected with the slightly enlarged convex set ! l2 + (00 1). This way, P. 2 P.YY) whereas P is in fact the intersection of the i-th Voronoi cell defined in (6) with Ω
We will now prove an upper bound on the sum of the diameters of the cells P.(Y) whose index lies in (Y)). First, we notice the following inclusion, which holds for any e [0, 1):
(1 (1- P) e LPP Ct,
(16)
Indeed, let x0 E pd and x E P!,, so that for all j E (1..... N) and e (0.1}.
||** 22 d; < ||* y
Expanding the squares and substracting || 1 on both sides these inequalities become linear in Φs. 2 and x² implying directly that x' (1 t)z² 0 + tx S P. as desired.
For any index E Ig. the point y: is at distance at least e from other points, implying that ( f) is contained in the Voronoi cell Vi(Y) with Ω Using that po = Vi(Y) n that Ω = Ω @ B 1) and that y/ E S2 we deduce that 1.00 contains the same ball. On the other hand, P! contains segment St of length diam(P!) and inclusion (6) with t gives
(B(ys, e/2) @ S.) C / 2
The Minkowski sum the left-hand side contains in particular the product of (d - -iddimensional ball of radius e/2 with an orthogonal segment with length diam(P!) 2 dY))( Thus.
1
d-1
diam diam((.()))) (((X))) < |
Wa Wa-1 2
2d

---

where I-| denotes the Lehesgue measure. Using that the Power cells P form a tesselation of the domain S2' we therefore obtain
22d-1
22d-1
diam (P(()) -
(di + 1)del-d
(17)
wa-1
Wd-1
We now estimate the transport cost between on and the density p. where B By (Y). The transport cost due to the points whose indices do not belong (Y) can be bounded in a crude way by
Σ Σ
|| b, (x S Card (Y) diam
ig1,0 P.0))
N
Note that we used p(P:(Y)) (Y) can be bounded using
On the other hand, the transport cost associated with indices in 17 and (iaam(:(()) I diam((?);
Σ
x 18-6,(3 b,)r)
Σ
diam(P.(Y))²
iEL(Y) PP)
iETL(Y)
(1)
diam (P((Y)
N
xET
2n 1
(diam(!)) + 1) E l-d
Wa-1
N
In conclusion, obtain the desired estimate:
22d-1
(diam(St) + 1) s--d W
N + diam(S))² (1- Card Ie
W2 (p.
N
This theorem could be extended mutatis mutandis to the case where & is a general probability measure (i.e. not density). However, this would imply some technical complications in the definition of the barycenters b; by introducing a disintegration of p with respect to the transport plan æ.
Consequence for the uniform Lloyd's algorithm (1) In the next corollary, we assume that any pair of distinet points in Yv E (R4y bounded from below by nN CN-B, implying that Iex (Yn) N. This corresponds to the value could expect for point set uniformly sampled from set with Minkowski dimension 3. When 3 > d - 1, the corollary asserts that one step of Lloyd's algorithm is enough to approximate p. in the sense that the uniform measure d (Yw) over the barycenters converges towards p as N +oc.
Corollary 4 (Quantization by barycenters, asymptotic case). Assume EN 2 C. 1-8 C-N-1/8 with C, O. Then, with 1 d-1
Ca.
VY E (R DN W2lp.dna(n) S -
(18)
and in particular, B >
1,
max +++ Y ((
lim
Wa(p, =.
(19)
Remark 3 (Optimality of the exponent when 3= d). There is no reason to believe that the exponent in the upper bound (18) is optimal in general. However, it seems be optimal in "worst-case sense" when 3 d. More precisely, we show the following result in Appendix E for any 8 e (0, 1). and for every N nd (n E N) there exists a sequence of separable probability densities aN over X [-1, 1] (pn is truncated Gaussian distributions, whose variance converges to zero slowly as N + +oo) such that if YN is a uniform grid of size n X X N' in X, then
W2 PN) 2 CN 12-4)
where independent of N. On the other hand, in this setting every point in YN is distance at least 11/ from any other point in Yx. Applying Corollary 4 with d, i.c. a J. we get
W (6 S C'N-à.
Comparing this upper bound on W (5 with the above lower bound, one sees that is not possible to improve the exponent.
7

---

Remark 4 (Optimality of (19). The assumption 8 > d - 1 for 19 is tight: if p is the Lebesgue measure on [0. 11 is possible to construct point cloud YN with N points on the (d 1) cuue (2) x [0, 1]0-1 such that distinct point in Yv are at distance at least EN 2 C..N CCN-I/(d-1) Then, the barycenters By (Yx) are also contained in the cube, so that (2 (Bw 12
The next corollary is probabilistic analogue of Corollary | assuming that the initial point cloud Y is drawn from probability density on f2. Note that a can be distinct from The proof of this corollary relies on McDiarmid's inequality to quantity the proportion of s-isolated points in a point cloud that is drawn randomly and independently from a. The proof of this result is in Appendix B
Corollary 5 (Quantization by barycenters, probabilistic case). Let L (SI) and let X1, ..., X be i..dd random variables with distribution E L (R*). Then, there exists constant C > 0 depending only on |o and d, such that for N large enough,
P
W2
1 N
Σ 0ogi0)
N
)
2 21 21-e-CNa CCN
24-3
3 Gradient flow and a
inequality
Theorem 3 can be interpreted as modified
(PL for short) inequality for the function FN. The usual PL inequality for a differentiable function F IR - E is of the form
VY E RR, F(Y) min F I C))VE(Y))??
where C a positive constant. This inequality has been originally used by Polyak to prove conver- gence of gradient descent towards the global minimum of F. Note in particular that such an inequality implies that any critical point of F is a global minimum of F. By Remark Fx has critical points that are not minimizers, so that we cannot expect the standard PE. inequality to hold. What we get a similar inequality relating FN (Y) and [/ (2)12 but with a term involving the minimimum distance between the points in place of min FN.
Corollary (Polyak-L.jjaa Poolyak--ojasiewizz-yyy inequality). Let Y E (IRA)N \ NN.. Then,
1 FY Ca.a N
(
d-1
S (NIVFN((Y))
(20)
A proof of Corollary 6 can be found in Appendix C
We note that when & = N-1/d, the second term of the left-hand side of (20) has order N-1/2, On the other hand, as recalled in Remark | min FN S 2/d when d > 2. Thus, (20 is strictly weaker than the PL inequality, which would
involve the minimum of FN.
Convergence of discrete gradient flow The modified Lojyyak--ojsiiiiizzzz inequality (0) sug- gests that the discrete gradient flow [3 will bring us close point cloud with low Wasserstein distance to p. provided that we can guarantee that the the points clouds Y remain far from the generalized diagonal Dx during the iterations. We prove Lemma 3 in Appendix D that
ykk+1 = yk TN V Px (Y*) and TN E (0, 1), then
Vi j.
| 1
21 (1-TN))l 1/
(21)
We note that this inequality ensures that y never touches the generalized diagonal Dx, that the gradient FN (Y*) is well-defined at each step. Combining this inequality with Theorem 3 one can actually prove that if the points in the initial cloud Y are not too close to each other, then a few steps of gradient discrete gradient descent leads to discrete measure Y that is close to the target p. We stress here that the goal of this paragraph is to showcase these kinds of several-steps estimates, in the simple case of our gradient flow for Fx. However, in this case, it provides a worse convergence rate to (w.r.t. N) than that given by Corollary and the decrease of the energy along the iterations from Proposition
2 Precisely, we arrive at the following theorem, proved in Appendix D
Theorem 7. Let 0 < a < र J. eN 2 N - and Y N \ [BE Let &Y ) be the iterates
of 133) starting from Y with timestep 0 < TN 1. We assume that Iim IN and we set
1
KN =
In IF (X))
drN
8

---

Figure 2: Optimal quantization of density P corresponding gray-scale image (Wikimedia Commons, CC BY-SA 3.0). (Left) We display the point clouds obtained after one step of Lloyd's algorithm, starting from regular grid of size N E (3750, 7350, 15000, 43350). (Right) Quantization error W (p. dBw) as function of N the number of points, showing that W2 (p. dBw) = N-0.00
Then,
W (p. 8ybe
=N ( +
(22)
Remark 5. Note that the exponential behavior implied by 21 and Lemma 3 is coherent with the estimates that are known in the absolutely continuous setting for the continuous gradient flow. When transitioning from discrete measures probability densities, lower bounds on the distance between points become upper bounds on the density. The gradient flow jrę = 1/2 V W pe) has an explicit a constant-speed geodesic in the Wasserstein space with do = po and 01 = p. In this case, a simple adaptation of the estimates in Theorem 2 in [9] shows the bound |4 - I edd [/olll== Still in this absolutely continous setting, is possible to remove the exponential growth if the target density is also bounded, as a consequence of displacement convexity [4 Theorem 2.2]. There seems be no discrete counterpart this argument, explaining in part the discrepancy between the exponent of N in 22 with the one obtained in Corollary 4
solution [4 = 01 01-e-- 1, where
4 Numerical results
In this section, we report some experimental results in dimension d 2.
Gray-scale image As we mentioned in the introduction, uniform optimal quantization allows to sparsely represent (gray scale) image via points, clustered more closely in areas where the image is darker 3). On figure we ploted the point clouds obtained after single Lloyd step toward the density representing the image on the left (Puffin), starting from regular grids. The rate of convergence observed on the sanht side chart, namely N 1100, is coherent with the theoretical estimate log (NN of Remark
Gaussian density with small variance We now consider toy model where we approximate gaussian density truncated the unit square [0, 1)2, p(a, v) = e -8((=-(()))))) +v= 4)*) where Z a normalization constant. On the left column of Fig. the initial point clouds Y are randomly distributed in [0, 1ja. The three point clouds represented above are obtained after one step of Lloyd's algorithm (1).. The blue curve displays in a log-log scale the mean values of (B (Yn)) over a hundred random point clouds, for N E {400, 961, 1600, 2500). In this case, we observe a decrease rate N 0.95 with respect to the number of points, similar to the case of the gray scale picture.
However, an interesting phenomena occurs when the initial point cloud Y is aligned on a axis- aligned grid. The pictures the right column of Fig. 3 where computed starting from such grid with N E {400, 961, 1600, 2500} points. As in the randomly initialized case, we represented the values of Fx xBN (Yx)) )) in log- scale. The corresponding discrete probability measure (xx) seems to converge to p as N + oc, but with much worse rate for these "low" values of N: Fx (Yw))
- In this specific setting, with a separable density and an axis-aligned grid Yo the power cells are rectangles and a single Lloyd step brings to critical point of Fx. Thanks to this remark, it is possible to estimate the approximation error from the one-dimensional case. In fact, Appendix E shows that for any 5 E (0, 1), there exists variances ON x8) such that

---

Figure Optimal quantization of Gaussian truncated to the unit square. On the left, the initial point cloud YN is drawn randomly and uniformly from [0, 1 while on the right YN is on a regular grid. The top row displays the point clouds obtained after one step of Lloyd's algorithm. The bottom row displays the quantization error after one step of Lloyd's algorithm Fy (Bx (Yx)) as fuction of the number of points. We get Fn (By (Yn)) N-0.95 when Yy is a random uniform point cloud in [0, 1] and EN (N((N(YN) ~ N 0.8 when YN is regular grid.
the approximation error W (PaN. 5B is of order ~ On the other hand, for fixed a, the approximation enror is of order N to be compared with the bound log(N)) for general measures.
5
Discussion
We have studied the problem of minimizing the Wasserstein distance between a fixed probability measure p and uniform measure over N points öy, parametrized by the position of the points
== (31..... ...,, (N). The main difficulty is the nonconvexity of the Wasserstein distance FN Y E (p, 5y), which we tackled by means of a modified Polyak-toojccewiic inequality 20) One limitation of work is that the exponents in estimates depends the ambient dimension: would be more interesting (but quite nontrivial) to establish similar estimates depending on the dimension of the support of p. Another direction of research would be derive consequences for the algorithmic resolution of Wasserstein regression problems ming ( To starting with the case where 0 + To is linear.
[Rd
Acknowledgments and Disclosure of Funding
This work was supported by grant from the French ANR (MAGA, ANR-16-CE40000144)
10

---

References
[1] Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008.
[2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[3] Michael Balzer, Thomas Schlömer, and Oliver Deussen. Capacity-constriine point distribu- tions: a variant of lloyd's 's method. ACM Transactions on Graphics (TOG), 28(3):1 2009.
[4] Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31 International Conference Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 085-693, Bejing, China, 22-24 Jun 2014. PMLR.
[5] Fernando De Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. Blue noise through optimal transport. ACM Transactions on Graphics (TOG), (11: 2012. 2012.
[6] Qiang Du. Maria Emelianenko, and Lili Ju. Convergence of the lloyd algorithm for computing centroidal voronoi tessellations. SIAM journal on numerical analysis, 44(1):102-119; 2006.
[7] Bjorn Engquist, Brittany D Froese, and Yunan Yang. Optimal transport for seismic full waveform inversion. Communicationn in Mathematical Sciences, 14(8):2309-2300 23300,,,,,,, 2016.
[8] Jean Feydy, Benjamin Charlier, François-Xavis Vialard, and Gabriel Peyré. Optimal transport for diffeomorphic registration. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages
Springer, 2017.
[9] Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with Sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, pages 1608- 1617. PMLR, 2018.
[10] Fernando de Goes, Pooran Memari, Patrick Mullen, and Mathieu Desbrun. Weighted tri- angulations for geometry processing. ACM Transactions on Graphics (TOG), 33(3);1-13, 2014.
[11] Siegfried Graf and Harald Luschgy. Foundations of quantizaation for probability distributions. Springer, 2007.
[12] Jun Kitagawa, Quentin Mérigot, and Boris Thibert. Convergence of newton algorithm for semi- discrete optimal transport. Journal of the European Mathematical Society, 21(9):2603-28) 2651, 2019.
[13] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 1892)11 1982.
[14] Robert J McCann. A convexity principle for interacting gases. Advances in mathematics, 128(1):153-179, 1997.
[15] Quentin Mérigot and Jean-Marie Mirebeau. Minimal geodesics along volume-preserving maps, through semidiscrete optimal transport. SIAM Journal on Numerical Analysis, 54(6):3465-33) 3492, 2016.
[16] Gilles Pagès. Introduction to vector quantization and its applications for numerics. ESAIM: proceedings and surveys, 48:29-79, 2015.
[17] Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning. 115-6))355-660 607, 2019.
[18) Sebastian Reich. A nonparametric ensemble transform method for bayesian inference. SIAM Journal on Scientific Computing. 35(4):22013-2222,, 2013.
[19] Filippo Santambrogio. Absolute continuity and summability of transport densities: simpler proofs and new estimates. Calculus of variations and partial differential equations, ( 354, 2009.
[20] Filippo Santambrogio. Optimal transport for applied mathematicians, volume 55. Springer, 2015.
[21] Cédric Villani. Topics in optimal transportation. Number 58. American Mathematical Soc., 2003.

---

[22] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
12


Reviews:
[{"review_id": "vIgAlnv-8Ob", "reviewer": "Reviewer_T7tc", "summary": "In the paper, the author studies the problem of generating $N$ samples $Y_{1}, ..., Y_{N}$ such that they are the optimal solution of the following uniform quantization problem:\n                                                    $$\\inf_{Y \\in \\mathbb{\\Omega}^{N}} W_{2}^{2}(P, \\frac{1}{N} \\sum_{i = 1}^{N} \\delta_{Y_{i}}), \\quad (1)$$\nwhere $P$ is a given distribution on $\\Omega$, $\\Omega$ is a subset of $\\mathbb{R}^{d}$. That problem can be thought as a constrained version of population K-means problem, which entails that\n                                                    $$\\inf_{G: |G| \\leq N} W_{2}^2(P, G), \\quad (2)$$\nwhere $|G|$ indicates the number of supports of probability distribution $G$.\n\nSince we only need to optimize the supports $Y_{1},..., Y_{N}$ from objective function (1), that optimization problem can therefore have a better optimization landscape than that of the population K-means problem in equation (2) where we need to optimize both the supports and weights of the probability measure $G$.\n\nBased on that insight, the authors propose an adjusted version of Loyd's algorithm to solve objective function (1) and establish the convergence rate of that algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the viewpoint of considering a uniform quantization problem of generating the samples $Y_{1}, Y_{2}, ..., Y_{n}$ is of interest though some of the main results are based on previous results in the literature. The key point here is that we are able to obtain a favorable theoretical guarantee for Loyd's algorithm under that specific setting.\n\nHere, I have the following comments with the paper:\n\n(1) There are typos in Theorem in page 4. The condition $\\|y_{i} - y_{j}\\| \\geq c N^{-1/d}$ should be changed to $\\|y_{i}^{0} - y_{j}^{0}\\| \\geq c N^{-1/d}$.\n\n(2) I wonder whether the assumption that the parameter space $\\Omega$ is compact and convex can be further relaxed? One key insight from the K-means problem (2) is that even though the supports of probability measure $G$ lie on $\\mathbb{R}^{d}$, eventually we can find a ball of some radius such that these supports will lie on. I think that a similar viewpoint may also hold for the uniform quantization problem that the authors consider.\n\n(3) In practice, what is good guidance for the choice of $N$? For example, if the distribution $P$ in equation (1) is a mixture of Gaussian distributions, poor choice of $N$ may lead to the lack of samples in some clusters or a very large value of $N$ may lead to the redundancy of samples in some clusters. Furthermore, the fact that the error rate is proportional to $N^{-1/d}$ is quite painful for practical application as we need to choose $N$ to be proportional to $d$ and $d$ is usually very large in practice. \n\n(4) In Proposition 2, do we have convergence speed for some sub-sequences of $\\{F_{N}(Y^{k})\\}$ to critical points? Furthermore, will $F_{N}$ be locally strongly convex around the minimizes?\n\n(5) In the proof of Theorem 3, several places used $I_{\\epsilon}$. The authors should change it to $I_{\\epsilon}(Y)$. Furthermore, I may misunderstand the statement of Theorem 3. If we allow $\\epsilon$ goes to 0 in the RHS of equation (15) in Theorem 3, the RHS will go to 0. On the other hand, the LHS does not depend on $\\epsilon$, which means its value will be 0 as $\\epsilon$ goes to 0. I feel that there is a typo with the assumption of $Y$ in that Theorem 3, namely, $Y \\in \\Omega^{N} \\backslash D_{N, \\epsilon}$. The authors please check that potential typo.\n\n(6) The experimental results are quite poor as they are mainly in 2D. The authors may need to carry out more experiments in high-dimensional settings to showcase the benefits of their methods.\n\n(7) The authors may consider adding a few relevant machine learning references using optimal transport for quantization purposes, such as clustering, which have quite a similar flavor as that being studied in the paper. A few representative examples include: multilevel clustering via optimal transport [1],  approximate optimal transport using quantization [2].\n\n(8) Some other typos:\n\n- Line 190: \"It is possible for to\" -> \"It is possible for us to\".\n\n- In Corollary 4, I think we should change $D_{\\epsilon_{N}}$ to $D_{N, \\epsilon_{N}}$.\n\n--- References:\n\n[1] N. Ho, L. Nguyen, M. Yurochkin, H. Bui, V. Huynh, and D. Phung. Multilevel clustering via Wasserstein means. ICML, 2017.\n\n[2] G. Beugnot, A. Genevay, K. Greenewald, J. Solomon. Improving Approximate Optimal Transport Distances using Quantization. UAI, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any foreseeable limitations and negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not detect any ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "mnPY_1dssS3", "reviewer": "Reviewer_u2eX", "summary": "Authors study a variant of the quantization problem: given a probability measure $\\rho$ on $\\mathbb{R}^d$, we are looking for the uniform measure on $N$ points that approximates the best $\\rho$ for the Wasserstein distance. Even though this problem is non-convex, it is shown that one step of a gradient descent allows one to reach a configuration with low energy (of order $N^{-1/d}$, whereas the minimum is of order $N^{-2/d}$). Furthermore, computing the gradient boils down to performing one step of a variant of Lloyd's algorithm.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "COMMENTS:\n\nThe paper addresses a variant of the classical quantization problem, that is well-motivated as an instance of a Wasserstein regression problem. Understanding why the OT approach is efficient in ML is an important topic, and proving that a (non-convex) Wasserstein regression problem can be solved by a gradient descent participates to this general goal. \nThe main result (one step of a gradient descent is enough to attain a region with low energy) is nice and quite surprising. \n The overall presentation of the paper is clear, and the different implications of the main result (Theorem 3) are explored in detail. I also appreciate that the limitations of the paper are clearly laid out: in its current form, the main theorem asserts that one can attain a region with low energy, but this energy can still be far from being minimal. The theoretical results are also showcased on simple examples (Figure 1 being particularly striking).\n\nQUESTIONS:\n\nI would like the authors to explain in a few sentences whether the behavior shown in Theorem 3 also occurs for the classical quantization problem. Can similar proof techniques be applied to this different setting? \n\nAlso, I have trouble understanding Theorem 7. Indeed, the rate of convergence in this theorem is slower than $N^{-1/d}$, whereas this is the energy we attain with one step in Theorem 3. The hypothesis $\\epsilon_N \\gtrsim N^{-1/d-\\alpha}$ is a little bit weaker than the assumption $\\epsilon_N\\gtrsim N^{-1/d}$ of Theorem 3, but still, it is weird that as $\\alpha$ goes to 0 we do not recover a rate that is at least as good as in Theorem 3. Could the authors elaborate on that?\n\n\nMINOR MISTAKES/TYPOS:\n\nl.33: minimize OVER the set\n\nl.54: examples OF families\n\nl.60: $\\theta \\mapsto T_{\\theta} \\mu$\n\nl.109: $F_N:Y\\mapsto ...$\n\nl.127: Power cell containS\n\nl.132: ''for any Y\\in D_n\" should be removed.\n\nl.168: $\\phi_i^k$ in the equation above\n\nl.170: second and third equation: I believe that the power cell should be transported towards $b_i(Y)$ and not $y_i$.\n\nl.205: Mention that the proof is in the Appendix\n\nl.209: provided that WE.. / far FROM THE\n\nl.373: I_\\eps(Y) already defined. \\kappa should be defined\n\nl.381: remove ( in the equation\n\nl.405: A_N instead of A (also below)\n\nl.416/417: We do not have \\sigma m_\\sigma \\to \\sqrt{2\\pi}. \n\nl.416/417: remove ..., \\leq y_N)\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "k76NtyAediQ", "reviewer": "Reviewer_gM3z", "summary": "This paper studies Lloyd's algorithm and gradient descent for Wasserstein regression and provides approximation and convergence guarantees.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. This paper tackles the problem of approximating a model distribution using a pushforward of a discrete reference distribution, which is hard due to non-convexity. The authors establish some theoretical guarantees for one-step Lloyd's algorithm and gradient descent, showing that these methods are valid and useful for the problem.\n2. The theoretical results are presented clearly, and numerical experiments are conducted to verify the theory.\n\nWeakness / comments:\n1. The non-asymptotic convergence rate in Corollary 4, 5 and 7 does not match the upper bound on the minimum of $F_N$ in Remark 1. It might be beneficial to explain why the present theory is not sharp, and which part of the analysis is not tight.\n1. Corollary 4 present the results for running Lloyd's algorithm for only one step. Will it get improved if we run more steps? Is it possible to get an error rate that matches the rate in Remark 1? (either from theoretical perspective or numerical perspective)\n2. It would be more convincing to include the case when $d\\geq3$ in the numerical experiment.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper, and I think there is no potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6fLWQ7As8HF", "reviewer": "Reviewer_nnEq", "summary": "This paper studies the non-convexity that arises in Optimal Transport problems when trying to optimize particle locations (a.k.a. Lagrangian approach), typically when optimizing maps $F_N : Y = (y_1,\\dots, y_N) \\mapsto W_2^2(\\rho, \\frac{1}{N} \\sum_i \\delta_{y_i})$ (_uniform_ quantization problem with reference measure $\\rho$). The map $F_N$ admits spurious local minima $Y^\\mathrm{bad}_N$ which in particular satisfy $F_N(Y^\\mathrm{bad}_N) \\not\\to 0$ when $N \\to \\infty$. However, the paper proves that, given a proper (non-adversarial) initialization, a single step of (a variant of) the Lloyd algorithm is sufficient to obtain a quantization $Y_N$ that satisfy $F_N(Y_N) \\to 0$ (with rate $\\leq N^{-1/d}$). Authors then prove a ''``PL-type'' inequality and use it to prove convergence (with rates) of a gradient descent scheme to minimize $F_N$. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity:\nThe paper is well-written and very pleasant to read. \n\nSignificance: \nThe results presented are novel to the best of my knowledge, and give some interesting insight on the behavior of Lloyd-like algorithms in semi-discrete OT problems. \n\nQuality:\nI think this paper is definitely a competent paper that should find its place at NeurIPS. It is somewhat frustrating that the paper does not deal with the case $\\theta \\mapsto W_2(T_\\theta \\circ \\mu, \\rho)$ as advertised in the introduction, though the current contributions of the paper are sufficient in my opinion. (note: the pushforward notation does not render properly so I use $\\circ$ instead)\n\nQuestions for the authors:\n- (a) The update considered in the paper ($Y_N \\mapsto B_N(Y_N)$) requires to explicitly know the target **density** $\\rho$. Why this is reasonable in some situation (typically in semi-discrete OT), one is more likely to face a sample $x_1,\\dots, x_M \\sim \\rho$ (with $M$ large), or a discretization $\\rho_M$ of $\\rho$ as an histogram (as in Figure 3 for instance). Is it possible/easy to extend the results presented in the paper (in particular Corollary 4 and Theorem 7) to this (somewhat more general/realistic) setting? i.e. do we lose much by performing the update with respect to $x_1,\\dots,x_M$ instead of $\\rho$ directly when it comes to quantize $\\rho$?\n- (b) If my understanding is correct, Theorem 7 proves that $\\mu_N = \\delta_{Y_N^{k_N}}$ converges to $\\rho$ for the metric $W_2$ (i.e. it is not \"too bad\"); but there is no guarantee that $\\mu_N$ is (asymptotically) an optimal quantization of $\\rho$. Do you have any clue on additional assumptions that may ensure that $F_N(\\mu_N) /\\min F_N \\to 1$ (or even stronger, that $\\mu_N$ is asymptotically optimal?)?\n\nMinor remarks and suggestions:\n- The notation $\\delta_X$ for $\\frac{1}{N} \\sum_i \\delta_{x_i}$ when $X = \\{x_1,\\dots,x_N\\}$ may be a bit confusing, as $\\delta_X$ refers to the measure supported on $\\{x_1,\\dots,x_N\\}$ in $\\mathbb{R}^{N \\times D}$. \n- (Figure 1 caption, typo?) The notation $[0;1]$ for intervals is not consistent with the notation $[0,1]$ used elsewhere in the paper. \n- (Ref) It may be worth to mention [C, section 6.2] as another situation where people are interested in uniform quantization problems.\n- (typo/notations) The notation $|P_i^{\\frac{1}{2}}|$ has not been defined (I guess $| \\cdot |$ is the diameter and the exponent $1/2$ should be out of the $| \\cdot |$).\n- (line 175) The naming ` ''Lloyd algorithm'' may be a bit misleading here as the paper considers a variant of this algorithm (the ``uniform'' Lloyd algorithm?).\n- (Caption of Figure 2, typo) A $)$ is missing in $F_N ( \\cdot )$\n- Mention that proof of Corollary 6 can be found in the appendix.\n- (Eq 22) Using $F_N(Y_N^0)$ would help to alleviate/harmonize notations (wrt the equation above). \n- (line 237) ``\"this figure'', a href is missing. \n- (line 239) ``\"red curve'', they seem blue (on my pdf reader at least).\n- (related to question b) In [A,B], roughly speaking, authors give conditions on initialization so that the Lloyd algorithm converges toward an optimal (standard, not uniform) quantization of the target measure.\n\nReferences:\n- [A] Levrard 2015, _Nonasymptotic bounds for vector quantization in Hilbert spaces._\n- [B] Chazal et al., 2020. _Clustering of measures via meanmeasure quantization._\n- [C] Cuturi and Doucet, 2015, _Fast Computation of Wasserstein Barycenters._\n\nNote:\n I checked the proofs of Theorem 3 and those of section 3; which seem correct as far as I can tell. The argument of using an orthogonal segment in the Minkowski sum to obtain the $d-1$ exponent may be detailed a bit. The proof of Corollary 5 was not checked. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper explicitly discusses some of its limitations, which is appreciated. I did not identified specific negative social impact the paper could have. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers stressed that this paper presents strong theoretical and numerical contributions, and it should be accepted.  As a side note, I think the authors should cite the paper “A note on constrained k-means algorithms, Michael K. Ng, 2000” which proposed the idea of quantizing toward uniform weights. The paper “Fast Computation of Wasserstein Barycenters Marco Cuturi, Arnaud Doucet, 2013” also contains an extensive discussions and numerical tests about this approach.
Decision: Accept (Poster)