Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper considers the problem of constructing a uniform probability distribution over a set of N points which minimizes the Wasserstein distance to a known reference distribution. This minimization problem, where the unknowns are the positions of the atoms, is non-convex. However, it can be shown that a suitably adjusted version of Lloyd's algorithm in which Voronoi cells are replaced by Power cells, leads to configurations with small Wasserstein error. Explicit upper bounds for the convergence speed of this Lloyd-type algorithm are presented in Theorem 7, starting from a cloud of points sufficiently far from each other. These bounds also 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.
main_review: This paper considers an interesting problem, i.e., minimizing the Wasserstein distance between a known continuous distribution and a discrete distribution defined over a set of N points. Such a problem cannot be solved in KL divergence, as the KL divergence between any continuous distribution and discrete distribution is always infinite. 

However, I am a bit confused by the contribution of the paper; it seems that Lloyd’s algorithm based on power cell has been studied in [11] and [14] under similar setting, see, equation (10) and Proposition 1 in the current paper. The authors should make it clear whether the adjusted Lloyd’s algorithm is a main contribution of the paper or not. In addition, more details about how to efficiently compute the barycenter for the power cell should be provided.

In general, there are some merits in the paper, but it is not well-written in the current form, and a lot of details need to be clarified. 

Minor comments:
1.	In Line 118, the notation $(T_\mu, Id)$# is used without definition
2.	In line 62, should be “In the previous inequality”.
3.	In line 133, the definition of barycenter is not correct, the current definition gives $b_i(Y)=1$, should be $b_i(Y)=N\int_{P_i(Y)}x d\rho(x)$.
4.	The order of Figure 2 and 3 should be swapped. 

limitations_and_societal_impact: This work is mainly theoretical, its practical impact will depend on the specific applications.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the optimal quantization problem, where one is tasked with fitting a discrete uniform measure supported on a fixed number of points to a continuous measure, measured by 2-Wasserstein loss. Their primary theoretical finding is that one step of gradient descent on this objective, makes progress proportional to the minimum distance between the starting uniform measure's support.
main_review: The main finding in this work is that a well-separated discrete measure leads to progress in gradient descent for the optimal quantization problem. This result is achieved by a short argument which proceeds by showing that a well-separted discrete measure must induce well-conditioned power cells, and so their barycenters must have relatively little transport cost. The result is further developed by combination with a previous observation that their objective is semi-concave, which allows some understanding of multiple steps of gradient descent.

While the primary result is interesting and novel, I feel that there is insufficient context and empirical or theoretical development to merit acceptance. In particular, I wonder whether this result is of questionable significance since in practice, to perform the gradient descent step one must estimate integrals of the density over the relevant power cells. If this is done via Monte-Carlo (which would be standard in a high-dimensional context), then the natural competitor would be the empirical measure on a sample of size $N$, which would achieve rates of the order $N^{-1/d}$ [1]. How does this compare to the estimator proposed here in terms of relative computational/statistical efficiency? If theoretical results are difficult, can an empirical comparison be made?

Another issue is that I feel the context for the obtained rates is not clearly explained. This is somewhat addressed in Remark 3, but I feel it should be more clearly explained that generically we expect for $N$ points and a "nice" density supported a bounded subset of $\mathbb{R}^d$, we cannot do better than $N^{-1/d}$ (this being a strength of the obtained result that is not properly expounded). Finally, I feel the experimental results section could be improved by a much more thorough substantiation of the claim that Lloyd's algorithm typically finds good local minima. Or, if there is already such a work in the literature, it should be cited (apologies if this has been cited and I missed it).

[1] Fournier and Guillin, "On the rate of convergence in Wasserstein distance of the empirical measure"
limitations_and_societal_impact: The authors addressed limitations adequately other than this issue regarding the situation of applying Lloyd's algorithm in practice.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study the semi-discrete optimal transport problem between the source measure, which is the distribution of a set of points after one iteration of the Lloyd's algorithm and the target continuous measure. In particular, they prove that the 2-Wasserstein distance between these two probability distribution can be approximation with a given accuracy, depending on $N$ the number of support points of the discrete measure and $d$ the dimension of the underlying Euclidean space, providing that the initial points in the initial point cloud are sufficiently spaced. A more general result on the convergence of Lloyd's algorithm towards a critical point of the Wasserstein distance with respect to the point cloud is also provided. These issues are related to uniform optimal quantization problems.
main_review: Originality : To my knowledge, this paper is the first to provide accuracy bounds for the Wasserstein distance between a continuous measure and a point cloud after the first step of Lloyd's algorithm, reducing the gap between experimental and theoretical results, the latter being mostly asymptotic (in particular in the optimal quantization community). In particular, this paper proves the advantage of Lloyd's algorithm, even if the functional $F_N$ to optimise wrt to the point cloud $Y$ is non-convex.

Quality : This paper contains strong theoretically results, for which the assumptions and consequences are clearly stated and explained. Moreover, some unfamiliar behaviours, such as in Figure 2 (right) are still presented and commented.

Clarity : This paper well written and the problems are clearly stated. Moreover, natural results following the first part of the paper, such as Corollary 5 (probabilistic case of quantization) are also proven. However, in my opinion, the introduction of regression problems is not completely justified as it can be more confusing than anything else (it is neither used or leveraged in the applications for example).

Significance : Lloyd's algorithm is largely used in several communities, from optimal transport to optimal quantization problems, even if it only solves provide critical points of a non-convex problem. Therefore, such a study on the behaviour of Lloyd's algorithm, both in finite time and asymptotically, is of great interest.

limitations_and_societal_impact: Limitations : As the authors discuss in the conclusion, the bound obtained for Lloyd's algorithm does not reach the theoretical rate of convergence, even if the initialisation points are sufficiently far apart.

Questions : - Considering the bounds on $W_2^2(\rho, \delta_{B_n(Y)})$, would the gain after $k$ iterations of Lloyd's algorithm be significantly better than after a single step?
-  In practice, Lloyd's algorithm can produce solutions with some boundary issues on the compact domain $\Omega$. From your results, I would say that this behaviour is avoided when the points in $Y$ are sufficiently far away. Could you comment on this?

Minor comments : 
- line 60 : the pushforward operator should be above, i.e. $T_{\theta}$ # $\sigma$.
- In Proposition 1, $Y$ is defined in both $DN$ and ${D}{N,\varepsilon}$. Moreover, in the definition of the barycenter of the power cell, the variable $x$ is missing (it is written $b_i(Y) = N\int_{P_i(Y)}d\rho(x)$).
- In Theorem 3, the point cloud $Y$ should belong to $\mathbb{D}_{N,\varepsilon}$.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies approximation of continuous measures in Wasserstein distance using point clouds, which define empirical distributions over their support. Optimizing over the locations of the points in these clouds results in a nonconvex optimization problem. Despite this, the authors develop a Polyak-Lojasiewicz-like inequality that states that, from a well-separated initialization, one can get to a point that is close to the underlying measure (on the order of $N^{-1/d}$). An iterative version of this method is shown to converge with a slower order.
main_review: Upsides:

+ This paper tackles an important problem of approximation of measures in Wasserstein distance by discrete distributions and gives the first theoretical results for this problem.
+ The PL-like inequality is new and interesting from a nonconvex optimization perspective. In particular, it gives an approximation error for a nonconvex setting that decreases with the sample size. This type of analysis may have broader applications.
+ The main results and their proofs are clear.

Downsides:

- The experiments are not extensive, and rather serve as a proof of concept. Furthermore, they do not illustrate the curse of dimensionality encountered in the theorems.
- How does one compute the barycenter of the Voronoi cells in practice? What is the general computational complexity and practicality of implementing this method?
- Theorem 7 and Remark 5 are not sufficiently clear. In particular, the discrepancy in the rates of Theorem 7 and Corollary 4 is not clearly expounded on. In general, it would be helpful to collect the results for the various methods/theorems together to make them easier to interpret and compare.
- In some sense, for the one-step algorithm, the method seems to be learning the barycentric projection optimal transport map, provided that the initial $Y^0$ is drawn from some density. This would then explain the types of rates that are seen in this setting, due to the rates of estimation for the optimal transport distance. It would be nice if the authors could comment on the connection here.
- The guarantees do not give hints as to what types of measures are easier to approximate than others. Furthermore, the dimension dependence of the constants is not discussed.

---

I still find the result interesting and think that it is close to being ready for publication. However, due to some issues raised by other reviewers, as well as the limited practical experiments, I will leave my score at a 6.
limitations_and_societal_impact: Limitations appear to be discussed in the conclusion. Societal impact/applications of the methodology are not adequately discussed. When does one which to quantize a distribution with an empirical distribution, and why does it make sense to do this with Wasserstein distance?
review_title: null

Meta-review: The reviewers recognize the theoretical interest of the authors' contribution, bounding in particular the error done after one step of gradient descent to minimize Wasserstein distance between a given density and a uniform discrete N-point distribution. They however raise valid concerns, particularly on the complexity needed to compute such gradients, on how it would rely on obtention of samples from the density being approximated. These are important aspects that are not treated in the paper. The reviewers also point to the lack of a discussion contrasting the guarantee they obtain to the one that results from taking as an approximating point cloud an N-sample from the target density. 

It therefore appears that the paper contains a very promising set of results, but is at this stage too preliminary and not ready yet for publication at NeurIPS.
Decision: Accept (Poster)