Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the Riemannian optimization with Bures-Wasserstein (BW) geometry for symmetric positive definite (SPD) matrix manifold. The authors compare the proposed approach with its counterpart with the popular Affine-Invariant (AI) geometry.

The authors illustrate that the proposed approach (with BW geometry) is more suitable than its counterpart with AI geometry when SPD matrices are ill-conditioned.

main_review: Riemannian optimization with SPD matrices is important for several approaches in machine learning. The authors consider the new raising Bures-Wasserstein geometry for this Riemannian optimization.

Overall, the paper is easy to follow and well-organized. The authors also evaluate the proposed approaches on several problems in machine learning to illustrate the theoretical findings.

By analyzing the condition number (Lemma 1), the authors show that BW geometry is more suitable for Riemannian optimization with SPD matrices than its counterpart with the popular AI geometry when SPD matrices are ill-conditioned. 

I have some concerns as follow:
+ In Remark 1, from Equ. (1), why BM metric has a linear dependence on X? (but not its inverse?)
+ For Lemma 5, is there any assumption (e.g., the strongly convex and smooth) for the $f$ function?
+ It seems that results about convergence in Theorem 1 and 2 are straightforward results from the literature? It is better in case the authors give more discussions about what new results are here, comparing with the literature?
+ For Figure 2, row 1, (b) and (d), why the AI and LE has the same behaviors for some first iteration, but LE converges better with more iterations?
+ Although the authors perform several experiments, most of them are with synthesized data. It is better in case the authors consider more illustrations with real-world problem/data (such as with the metric learning).

~~~~~~~~
After the rebuttal:

I thank the authors for the response. I agree with the other reviewers that it is better to give general properties for the loss function when AI geometry is better (currently, only 1 example is listed in the submission). Overall, I keep leaning on the positive side.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the Bures-Wasserstein (BW) geometry of symmetric positive-definite (SPD) matrices and compares it to the commonly-used affine-invariant (AI) geometry in the context of Riemannian optimization. It is shown theoretically that the BW geometry has several advantages. Particularly, it is shown that (i) the BW metric is linearly dependent on the SPD matrix, (ii) the condition number of the Riemannian Hessian of the BW metric is smaller than that of the AI metric, and (iii) the curvature constant of the BW metric is smaller than that of the AI metric. Based on these properties, it is shown that the convergence of Riemannian steepest descent and Riemannian trust-region based on the BW metric is faster than based on the AI metric. The theoretical results are demonstrated on simulations of six problems: weighted least squares, Lyapunov equations, trace regression, metric learning, log-det maximization, and Gaussian mixture model.
main_review: The Riemannian geometry of SPD matrices has become popular recently, and the choice of geometry/metric is of paramount importance. This paper provides a systematic way to choose the metric from an optimization standpoint. As I outline below, I believe the paper has few drawbacks. However, despite its weaknesses, I believe this paper presents a solid contribution to the increasing literature and practice of Riemannian geometry of SPD matrices.

Detailed comments:
- The argument that a smaller condition number and/or smaller constant curvature is necessarily better is problematic. In terms of optimization, it is indeed shown for example that a smaller condition number translates to better convergence. However, if this is the only criterion, then one could claim that the Euclidean metric outperforms both the AI and the BW metrics. In other words, the paper claims that “simpler” metrics are better for optimization, but it does not consider the effect of the metric on the induced geometry. 
- To make my comment above more concrete, I would love to see, in addition to the simulations, results on some real data, where the contribution of using Riemannian geometry is established, and where the choice of the metric also determines the “quality” of the analysis.
- In the experiments (line 265), the Frobenius (Euclidean) norm is used as a measure of distance to the desired solution. This departs from the entire message of the paper advocating for Riemannian geometry and could be particularly problematic when measuring the convergence rate.
- In many figures (e.g., Fig 1 (a)+(b)), it appears as if not all the graphs have reached convergence. Why do the graphs have different lengths?  
- line 185: the geodesic gamma(t) is undefined (a missing reference to Prop 3 in the appendix).
- line 200: it would be better to explicitly define “geodesic triangle”, although it is implied from the context.

**After rebuttal:**
I thank the authors for their response to my comments.
After reading the other reviews and the authors' responses, my two concerns regarding the Euclidean metric and norm still remain. That said, I am increasing my score and recommend accepting the paper, since I believe it presents analysis and results that will be interesting to the community of people working on the Riemannian geometry of SPD matrices.
limitations_and_societal_impact: The limitations of the work could be better presented and discussed, especially since the paper considers only optimization properties. I do not foresee any potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides several results about the Bures-Wasserstein  (BW) geometry on the positive definite matrices. A thorough comparison with the Affine Invariant (AI) metric is made. The main focus of the paper is on optimization: is it faster to optimize a function under the AI or under the BW metric? The authors argue that when the solution of the problem $X^*$ is ill-conditioned, then algorithms derived under BW metric have faster convergence theoretical convergence. This is due to the conditioning of the Riemannian Hessian at the optimum, which is better for the BW metric when $X^*$ has poor conditioning. The authors also demonstrate that a variety of functions that are convex for the AI geometry are also convex for the BW geometry.
Experiments on an array of synthetic problems validate that both Riemannian gradient descent and Riemannian trust region methods are faster in the BW geometry.
main_review: **Originality** :  This paper derives some novel results about the Bures-Wasserstein geometry, and provides some insights comparing it to the affine-invariant metric. Such comparisons are important because both metrics are widely used in practice. To the best of my knowledge, insights regarding the conditioning (lemma 1), distance bounds (lemma 4) or convexity (prop 1) are novel.
- Lemma 2 is already known, see Example 1.7 in [1]
- I think that lemma 4 and Lemma 5 in [2] are similar.

**Quality** : I think that comparing in a thorough manner the convergence properties of optimization algorithms under different metrics is an important and interesting problem. However, I have some concerns regarding the results of the authors. In particular, I think that the authors paint a picture that is too biased in favor the BW metric, and that there are some flaws in the analysis. 

- One of the most important result of the paper is that the conditioning of the Hessian under the BW metric, $\kappa_{BW}$, is smaller than the conditioning under the AI metric, $\kappa_{AI}$, when $\kappa(H) \leq \sqrt{\kappa(X^*)}$, where $H$ is the Euclidean Hessian of the function, and $X^*$ is the solution. This means that algorithms using the BW geometry will be faster when $X^*$ is poorly conditioned, not when $X^*$ is well conditioned. Some parts of the text seem to skip this important condition (e.g. L163). Also, when $\kappa(H) \leq \sqrt{\kappa(X^*)}$, then lemma 1 gives $\kappa_{BW} \geq \kappa(X^*)/ \kappa(H) \geq \kappa(H)$. Therefore, BW has itself a worse conditioning that using simply the Euclidean metric ! This fact should be mentioned, and this also raises the question of using plain Euclidean algorithms (for instance, projected gradient descent) in the experiments.

- The constant $\alpha$ in Lemma 5 plays a key role in the convegence speed of the algorithms. However, I think it is important to insist that $\alpha$ depends on the metric used, since it is defined with the Exp. As a consequence, it is impossible to conclude that the rates in Thm.1 and 2 are better or worse for the BW/AI metric, even when $\kappa_{BW} < \kappa_{AI}$. In order to draw a conclusion, a study of the behavior of $\alpha$ under the two metrics should be carried.

- I also have concerns regarding the experiments. I replicated the least squares experiment with success. However, I tried another  related cost function, where here there is a matrix product instead of Hadamard product $f(X) = \frac12 \|AX - B\|$, where $B = AX^*$ with $X^*$ ill-conditioned, and I found that the two algorithms performed quite comparably, even when $X^*$ is poorly conditioned. I suspect that this is due to the constant $\alpha$ in the bounds. Also, I think that an experiment based on symmetric matrices taken from a real dataset would strengthen the point of the paper.




**Clarity**: the paper is well written and pleasant to read. It is also well organized.

**Significance** : as I already stated, I think that a clear and accurate comparison of the two metrics is a significant result that is of broad interest to any researcher working with PSD matrices.

**Misc** :
- Another field where PSD matrices with the AI/BW matrices are extensively used is EEG/MEG processing, with works such as [3]
- It should be mentioned that the paper assumes that the Euclidean gradient of $f$ is always symmetric.
- The actual BW and AI distances between two PSD matrices is never explicitly written in the paper, while these are the most used quantities. Including them in Table 1 would be worthwhile.
- Following the definition of conditioning of the authors, the conditioning of a linear problem is ill-defined.
- In lemma 1, are the inequalities tight?
- In Lemma 5, what is $t$?
- In fig.1 with gradient descent, how was chosen the step size? It is of crucial importance.
- In fig1. c, d, e, using a log scale for the y axis would make things more readable. 

[1]: McCann, Robert J. "A convexity principle for interacting gases." Advances in mathematics 128.1 (1997): 153-179.

[2]: Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In
Conference on Learning Theory, pages 1617–1638. PMLR, 2016.

[3]: Barachant, Alexandre, et al. "Multiclass brain–computer interface classification by Riemannian geometry." IEEE Transactions on Biomedical Engineering 59.4 (2011): 920-928.
limitations_and_societal_impact: The authors seem over optimistic about the performance of BW metric compared to AI metric.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper investigates the advantages of the Bures-Wasserstein (BW) metric over the widely used Affine Invariant (AI) one, for the manifold of symmetric positive definite (SPD) matrices. Rewriting the two metrics in a compatible manner reveals that for a wide variety of objectives, the BW metric is a linear function of the input matrix whereas the AI has a quadratic dependence. One exception is the log-det function which is included in the analysis. The paper experimentally validates that for ill-conditioned problems BW is a better choice compared to AI.
main_review: PROS

- SPD matrices are used ubiquitously in computer vision. Hence, the fundamental contribution of this paper is expected to have a significant impact in the field -- at least for the portion which consider optimization on SPDs. 
- I like the principled approach of the paper. It starts with an analysis of the problem and later fills in some theoretical gaps in the literature. 
- The experiments include various relevant problems and reflect what the theory stands for: BW does indeed converge better.
- The content, albeit involved, is clearly presented with adequate references. I would be happy to see this paper at NeurIPS.

CONS

While I have not gone through all the derivations, I have not spotted major weaknesses of the paper. Here are some minor points of concern:
- The fact that BW provides a valid RKHS is very important. In fact the non-positive definiteness of the kernel has already caused nuisances for computer vision people. See for example:
* Birdal, T., Arbel, M., Simsekli, U., & Guibas, L. J. (2020). Synchronizing probability measures on rotations via optimal transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 1569-1579). *
Therefore, I would be happy to see further discussions on the connections with kernel methods here.
- Can we extend this study and compare with other metrics? Are there other metrics which also show linear dependence but somewhat inferior to BW? 
- Log-det seems to be just one counter-example. I feel like there are many other functions of this type. Could we have a general characterization of when affinte-invariant metric is a good choice and when not? Maybe a general recipe towards choosing a metric?
- While the analysis is conducted for an analytical Hessian, in practice the Hessian is approximated using a finite differencing scheme. Does that create a significant gap with the theory? Can we actually study/quantify this gap? Why would the paper not use auto-differentiation to be exact?
- The paper assumes the availability of an exponential map. For SPDs this is okay. But for conducting a similar analysis on other manifolds, a (maybe first-order) retraction should be considered. Is it possible to extend the analysis to the case of retractions? 
- I suggest that the findings here are incorporated into Manopt. 
limitations_and_societal_impact: This paper has a theoretical nature and does not have direct negative impacts on society. The limitations are explained in the discussions section.
review_title: null

Meta-review: The authors consider the Riemannian optimization with Bures-Wasserstein geometry for symmetric positive definite matrix manifold. Since the reviewers agree that the content of the paper will interest many researchers working on this subject, we conclude that the paper is worthy of acceptance. I think that the comment on the Frobenius norm by a reviewer is important. I expect that the authors add some comments on that issue in the revision. 

Decision: Accept (Poster)