Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study Riemannian gradient descent on the Bures-Wasserstein manifold and provide non-asymptotic convergence guarantees for three optimization tasks: The computation of Wasserstein barycenters, entropy-regularized Wasserstein barycenters, and geometric medians.
main_review: After rebuttal: Thanks to the authors for their comments. I'm keeping my score of acceptance.

-----------------------------------------

*Assessment*

Non-asymptotic convergence guarantees for regularized barycenters and geometric medians are to my knowledge novel and should be of great interest to the community. The theoretical results are clearly formulated and seem correct. The paper is very well written.

*Additional Comments*

- Related work: Wasserstein barycenters on the Bures manifold lie in a compact, geodesically convex set and can therefore be treated as a constrained problem. One can then get non-asymptotic convergence guarantees with constrained Riemannian methods, such as Frank-Wolfe. The PL inequality should ensure linear convergence for such methods too. See, e.g., [*].
- I did not see any experimental results for a practical application. The current numerical evaluation on synthetic data is (to me) sufficient for acceptance, but an experiment illustrating the results in an application could strengthen the paper.

[*] Weber, Sra: Projection-free nonconvex stochastic optimization on Riemannian manifolds 

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: The paper address the problem of computing the barycenter of a gaussian distributions using optimal transport metric. The paper propose two algorithm (section 3.1, section 4.1) to compute thw Entropically regularized barycenters and the Bures-Wasserstain barycenters and it studies its convergence guarantees.
main_review: Even if the paper deals with an interesting and important topic, it is not well organized neither clear. For example, the general discussion is completely missing. In this current form, the paper can not be published. As a general comment,  I think it is more suitable for a journal, where there is more room for discussion of the literature and additional details. 

Some comments for the possible reorganization of the paper:
1) Section 1 and Section 2 should be reorganized, separating the state of the art from the rest
2) Results in section 3,4,5 should be well listed at the beginning, otherwise it is not clear the whole paper structure
3) Discussion is a fundamental part of the paper, beacuse it allows the reader to understand the work and value your discovers
4) The simulated data should be better explained, not left on the side of the figures as captions.


limitations_and_societal_impact: No, unfortunately the discussion is missing.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work is with the recent active wave of work in numerical optimal transport to take ML and statistical estimation problems. More precisely, the authors study first-order optimization algorithms on Bures-Wasserstein manifold for computing the barycenter of Gaussian measures with respect to the 2-Wassertstein distance, the  regularized barycenter and geometric median.

main_review: The main contribution of the paper is to show new geodesic convexity results hence allowing to obtain a dimension-free convergence rate of Riemannian gradient descent. The techniques also enable to go beyond barycenters by tackling the problem the entropically-regularized barycenter and geometric median, hence providing first convergence guarantees for these problems. Although linear convergence of gradient descent on the Bures-Waasserstein manifold was established recently, the rate had exponential dependence on the dimension. Therefore, as far as I can say, the results of this paper are new and of interest to the literature. The paper is also fairly well-written. Having said this, I still have some comments:

1) I found that the paper lacks discussion to prior work for each stated result (though a brief discussion is gathered in the introduction).
2) P3, L106-107: the reference given there is not fair. Rather cite the original paper of Łojasiewicz, and those of J. Bolte and his co-authors who have the actual pioneers of this in optimization. 
3) P4, L151-153: please void self-citation for such a classical subject on which there are many standard monographs (including diCarmo).
4) P4, L155: sentence in parentheses. You say a bit later that it is in [Che+20, §4]. Note also that for the regularized W_2, it is also in [Jan+20, Lemma 1].
5) P5, Theorem 2: the notation of the iteration counter is t in the algorithms and n here. Unify notations.
6) P5, Theorem 2: can you comment on optimality of this rate ? We know the optimal rate in the Euclidean (convex) case.
7) P5, Theorem 2: the statement "appropriate step-sizes" (ans also the K_t's) has to be made precise here (not just in the appendix). It is well-known that such a choie crucial to get the 1/n rate. 
BTW, can the dependence in \kappa^3 be improved again ?
Is there any hope to have a variance reduced version for the case of finitely many distributions (i.e. finite sum) ?
8) Figure 2: the difference between ESGD and SGD is quite sensitive to the constant in the stepsize. Can you comment on this ?
9) P6, L208: n is now used for the number of Gaussians (see comment 5) above).
10) Figure 3 and dimension-independence: an alternative way would be rather to run several examples of the experiment on Figure 1 for increasing dimension, estimate the rate from a semilog fit, and plot the estimated rate as a function of d.
11) Proposition 1: a similar result is in Theorem 2 of [Jan+20] but with a different metric (debiased version of the entropically regularized 2-W). Discuss please.
12) Theorem 5: why this form of smoothing ? There are other ways, probably with better guarantees, or even no smoothing with subgradient descent. the iteration complexity in \varepsilon^{-4} is rather slow (and play be pessimistic). Any clue on optimality of this bound or if it is unavoidable ?

limitations_and_societal_impact: None.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 
The subject of this paper is Riemannian (stochastic) gradient descent for Bures-Wasserstein barycenters of Gaussian measures. The authors first improve recent results by S. Chewi et al (2020) by removing the exponential dependence of the convergence rates w.r.t. the dimension d. This improvement is obtained by showing the geodesic convexity of $-\sqrt{\lambda_{\min}}$ and $\sqrt{\lambda_\max}$, which yields tighter bounds on the eigenvalues of the iterates of Bures-(S)GD than that of S. Chewi et al (2020). Next, the authors extend Bures-(S)GD to a KL-regularized barycenter problem that encodes an isotropy prior on the barycenter, and to a median version of the barycenter problem (where the sum of un-squared distances is minimized). Finally, in numerical experiments they compare Bures-Riemannian (S)GD to Euclidean (S)GD on the original barycenter problem, and investigate the effect of smoothness parameters in the regularized and median problems.

main_review: I have greatly enjoyed reading this paper, which is well-written and makes important contributions, even though it relies on techniques developed by S. Chewi et al (2020). Here is a list of points I particularly appreciated:

- Removing the exponential dependence in $d$ is a *tour de force* that closes the gap with the sample complexity bounds for Bures-Wasserstein distance estimation, which are also dimension-free (see e.g. R. Flamary et al. (2019))

- The paper is very clearly-written, and mostly self-contained. I particularly appreciated the fact that all required geometric notions are recalled in appendix A, which does a great job at introducing them in an intuitive way.

- The extensions to the regularized barycenter and geometric median are interesting, in that they show how the tools developed for the Riemannian descent on the BW barycenter problem can be applied to problems that seem less amenable to them at first sight.

- Thm. 1 is of interest by itself, and could probably be used to optimize spectral functions of PSD matrices in the Bures geometry.


A few comments:

- While I appreciated the fact that they provide additional examples of how to apply proof techniques based on (generalized) geodesic convexity, I am not sure how significant the regularized barycenter and geometric problems are.

- l.238: « Prior work focuses on a slightly different entropic penalty, the differential entropy  $\int b \ln b$. ». There are some works that study this problem with a broader class of penalties, see e.g. the work of J. Bigot et al. (2019) which seems quite relevant.


References:

Flamary, R., Lounici, K., & Ferrari, A. (2019). Concentration bounds for linear Monge mapping estimation and optimal transport domain adaptation. arXiv preprint arXiv:1905.10155.

Bigot, J., Cazelles, E., & Papadakis, N. (2019). Penalization of barycenters in the Wasserstein space. SIAM Journal on Mathematical Analysis, 51(3), 2261-2285.
limitations_and_societal_impact: My only comment on that subject is that the fact that the algorithm for geometric medians computes an approximate solution that depends on the smoothness parameter $\varepsilon$ could be mentioned earlier than in section 5. However, based on Figure 5 it seems that numerical precision is reached quite fast when taking $\varepsilon$ to $0$.
review_title: null

Meta-review: The paper proves dimension-free convergence rates for the gradient descent algorithm for the Bures-Wasserstein Barycenter computation. It is a significantly novel result that provides a theoretical basis to something that is practically observed and as such should be of interest to many.

Decision: Accept (Spotlight)