Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: Paper studies dimensionality reduction and coresets for the Wasserstein barycenter problem. The objects are distributions supported on n points in R^d, and the barycenter is a single distribution which minimizes sum of Wasserstein distances (or related quantities). The show that using random projections, they can reduce the dimension of the ambient space from R^d to R^{O(log(n))} while preserving the cost of optimal barycenter. They also give coresets from which one can compute the Wasserstein barycenter.
main_review: The paper considers the Wasserstein barycenter problem: we receive k distributions supported on n points in R^d, and the task is to find a single distribution which is a good 'center' for these k distributions. In particular, the center minimizes the sum-of-p-th powers of Wasserstein-p distances from the single distribution to the k other distributions. 

A few remarks: 
1. This problem can be interpreted as 1-mean (or 1-median) clustering, where distances are measured according to the Wasserstein distance.
2. The paper actually considers a constrained version of the problem, where the center distribution is also supported on at most n points in R^d. With this constrain, the problem can be interpreted as a n-cluster problem in R^d with a few additional constraints on the allowed clustering. At a high level, consider a barycenter which is specified by n points c_1, ..., c_n in R^d and n weights a_1, ..., a_n which specify the probability that we sample c_i. Then, for each of the k distributions, think of them as uniform over a *multi-set* in R^d. The Wasserstein distance from a distribution x to the barycenter is given by an assignment of the points to the n centers with the additional constrain that for each center c_i, the total weight is a_i. In other words, this is a n-clustering problem where we consider partitions of the total support with k constraints (one for each distribution).

The paper shows that one can reduce the dimensionality to O(log(n)/eps^2) dimensions with JL and preserve the cost up to 1+eps, and how to construct coresets with poly(n) distributions. Furthermore, they show that O(log(n)/eps^2) dimensions are necessary for preserving the Wasserstein distance between two points (and hence this is a limit). Finally, they show it is NP-hard to find an approximate Wasserstein barycenter supported on n points up to some constant factor.

I am confused about the following. The paper builds heavily on [Makarychev-Makarychev-Razenshteyn], who showed that in k-clustering problems, the dimension may be reduced to O(log(k)) and preserve the cost to *all* partitions of the points into k parts. Furthermore, coreset results for k-clustering objectives usually have the property of being "strong coresets" in that they preserve cost to *all* partitions into k parts. If I understand the problem correctly, [MMR] directly implies Theorem 4.1? If I am misunderstanding some point, this should definitely be addressed in the introduction, since I don't see the challenges in utilizing [MMR] directly. 

One additional comment: I don't see why the assumption that the distributions are supported on poly(n) points is necessary. It seems that the important aspect is that the actual barycenter is restricted to support-size n, a point which should be stressed in Theorem 1.1. It seems like an open problem to determine whether this assumption is actually needed (?).
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper suggests a coreset construction scheme and a dimensionality reduction for the Wasserstein Barycenter, which can be thought of the $\ell_p$-mean of $k$ discrete distributions where the mean here is a probability distribution.
main_review: In this paper, a dimensionality reduction via JL has been proposed followed by a coreset construction, yielding a small weighted coreset. 
The ideas behind applying these methods rely on the Lipschitz property of the cost function, whereas the coreset relied on the sensitivity sampling framework which in this paper, exploited the weak triangle inequality concerning the cost function. 
Usually in the literature of coresets, when the weak triangle inequality concerning the loss functions holds, then one can attain a coreset easily. 

Regardless, I find the paper interesting. 

Furthermore, The authors suggested the first upper bound on the vc dimension concerning the problem.


limitations_and_societal_impact: - The coreset size depends heavily on the size of the support of the given $k$ discrete probability distribution, i.e., $O\left(n^8\right)$. This bound actually comes from the bound on the VC dimension of the problem at hand. 
The coreset becomes impractical when $n$ is large.  Is your bound on the VC dimension tight? Would it be better to use the doubling dimension instead of the VC dimension, while increasing the depencedy on the total sensitivity from near-linear to quadratic at the sample size (concerning the coreset)?

- Experimental results:
  a. add graphs where the x-axis is the time took to compute a coreset + to solve the problem on the coreset (compared to uniform sampling) --> at the end this is what is important.

  b.  why there are no graphs in the coreset comparison to uniform sampling (the reader wants to see phenomena, not just numbers) +  add variance to these graphs --> it is an important measure.

Note-> it is almost clear that the importance sampling is better, however, I think there is a lot of experiments that should be done more to emphasize that.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper justifies compute Wasserstein barycenter with dimension reduction techniques, which can lead to significant cost saving. Specifically, with the help of JL lemma, the original Wasserstein problem can be solved in a space of dimension $\mathcal{O}(\log n)$, where n is the specified barycenter support size. The reduced dimension is **tight**, and is not dependent on the original problem dimension and the number of input distributions. The authors also discuss the hardness of the barycenter approximation, the existence of a coreset with size poly($n$), and the connection between the Wasserstein barycenter problem and constrained low-rank problems. The authors empirically validate their claims using real datasets on dimension reduction and a synthetic dataset on coreset construction.

main_review: This paper flows well. The related concepts are well introduced, and the proofs are properly outlined. 

The idea of using dimension reduction to speed up the computation of Wasserstein barycenter is promising. This paper provides a comprehensive discussion of the applicability of dimension reduction – when the cost can be preserved and when cannot. The speedup from algorithm 1 should be significant. 

The proof techniques might shed lights on other related future works on dimension reduction.


My questions mainly focus on the computation time. In the MNIST experiment, the dimension is reduced from 784 to 30, which is remarkable. However, the average time taken is **73%** of without dimension reduction. I wonder why the time reduction is not very significant. What is the decomposition of the time usage in this particular experiment, i.e., what is the time cost of each step of algorithm 1? As claimed in line 207, the cost of running algorithm A is usually much more expensive than performing the projection – does this still hold for this experiment? 

In contrast, the time usage for FACES is only 9% of the original one. What causes the difference? Larger original dimensions? Smaller support sizes of the input distributions and the barycenter? More generally, in what cases the speedup from dimension reduction is more significant? Also, have you tested on different barycenter support sizes? **Is the current time reduction optimal with respect to the barycenter support size?**


Some minor comments:
1.	I guess “ratio of the quality of solution” in Figure 2 is the ratio between the costs (as implied by line 353)? It would be better if this is more clear in the caption.
2.	Figure 2 would be more straightforward if there is a horizontal line at ratio=1.
3.	Figure 3 should be a table, and the caption should locate on the top of the table.

limitations_and_societal_impact: This paper mainly focuses on the mathematical and algorithmic properties of the Wasserstein barycenter problem, not do not focus on any particular downstream applications that may have negative social impact.
review_title: null

Meta-review: As pointed out by the reviewer W1WL, and discussed with the authors, the main result follows relatively directly from [MMR]. While the paper has other merits, the paper needs a major rewrite to address that.

Some reviewers were also not fully satisfied by the authors answer to the question on the time usage decomposition of the MNIST experiment.
Decision: Accept (Poster)