Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a tight analysis of riemannian gradient descent of its iteration complexity. 
main_review: I think the paper is solid and a good work. It provides a gap free bound which is interesting. I am just wondering whether there would be any block version of the gradient descent method. If so, is it possible 
to extend the analysis here to that setting. I notice the specific update form, e.g., (4), is crucial for the analysis. Can the author comment on this part. 
limitations_and_societal_impact: I don't think this paper discuss limitations. Probably the author can comment on the case of computing a block of eigenvectors.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies Riemannian gradient descent for largest eigen-vector computation real symmetric matrices. For matrices with eigen-gap $\Delta$ and (global) convergence error $\epsilon$, the paper gives a gap-dependent convergence rate of $\frac{1}{\Delta} \log(1/\epsilon)$ and gap-independent analysis which gives a convergence rate of $\frac{1}{\epsilon} \log(1/\epsilon)$. This improves upon previous work that achieves a $\frac{1}{\Delta^2} \log(1/\epsilon)$ rate and generalizes related work that that achieves the same rate for projected gradient descent, power iteration and Riemannian gradient descent restricted to PSD matrices.

The paper highlights an omission in previous work that mistakenly stated a rate of $\frac{1}{\epsilon} \log(1/\epsilon)$ which is in fact $\frac{1}{\Delta^2\epsilon} \log(1/\epsilon)$. 

Experiments comparing the power iteration, projected gradient descent and RGD are done for proposed adaptively chosen step-sizes. 
main_review: Eigen-vector computation is a ubiquitous problem in machine learning and the improved convergence rate for RGD is an important contribution in understanding the convergence behaviour of PCA algorithms. The exploration of adaptive step-sizes in the experiments can also be a valuable line of investigation for future work.

That said, some concerns:
1. It seems like in Thm 1 and Thm 2 both have a dependence on $\log(\tan^2 \theta(x_0, V_p)))$. How do you bound this without any assumptions about the starting vector $x_0$? What am I missing here?
2. Line 49, Line 149, you mention that the analysis is adapted from [2] that uses "constant matrices". It isn't quite clear what this means. It seems like you mean the definition of $h_t(x)$ is different. A little more explanation may make the distinctino more clear. 


[1] Xu, Z., Cao, X., & Gao, X. (2018, July). Convergence analysis of gradient descent for eigenvector computation. International Joint Conferences on Artificial Intelligence.

[2] Musco, C., & Musco, C. (2015). Randomized block krylov methods for stronger and faster approximate singular value decomposition. _arXiv preprint arXiv:1504.05477_.
limitations_and_societal_impact: Not applicable since the work is mainly theoretical.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper considers Riemannian gradient method for PCA. Contributions of the paper are following: 1) proved convergence rate of $O(\frac{1}{\max{\Delta, \epsilon}}\log\frac{1}{\varepsilon})$ for any real symmetric matrix; 2) showed without the need of the eigenvalue gap information that even if the gap $\Delta$ is significantly smaller than the target accuracy, it is possible to achieve a speed of convergence $O(\frac{1}{\epsilon}\log\frac{1}{\varepsilon})$. Numerical results verify obtained rate of convergence.
main_review: Paper achieves new state-of-the-art theoretical results for Riemannian gradient method for PCA. Clear accept
limitations_and_societal_impact: Yes, the authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this work authors presented two analyses of the Riemannian gradient descent for eigenvector computation.  First authors provided a general tight analysis that holds for any real symmetric matrix. In addition, authors further give the first worst-case analysis that achieves a rate of convergence.

For real-world application, this gap-dependent analysis suggests a new promising learning rate for stochastic variance reduced PCA algorithms. Authors provided experiments to confirm the findings.

Overall this is a solid paper with both theoretical analysis and empirical studies.
main_review: Originality: One suggestion is adding a table to compare the work with other related works on the assumptions and convergence rate (especially with Ding et al. 2020.). This would make it easier to compare and understand the contribution of this work.

Quality:  This paper has good quality with comprehensive theoretical analysis and rich empirical experiments.

Clarity: The writing is clear. The footnote in page 7 is a bit too long, authors may consider put it in the main text. 
Also it is great to see the comparison w.r.t. both passes and wall-clock time (sec) in figure 2 and 3. I am curious if authors has any results for time (sec) comparison for figure 1?

Significance: This paper provides theoretical analysis for the Riemannian gradient descent for eigenvector computation. From the real world application, authors confirms it significantly improves the speed for VR-PCA.  
limitations_and_societal_impact: I did not observe any potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors considered Riemanninan gradient descent for solving the top eigenvector/value problem for real-symmetric matrices. Rates in two regimes are given, depending on the gap of the top eigenvalues compared to the desired accuracy. The analysis is based on polynomial recursion derived from the algorithm updates. Additionally, for positive-definite matrices, a stepsize choice is proposed based on the upper bound on the contraction factor as suggested by the recursion. Numerical experiments are conducted for the power iteration, projected GD and Riemanninan GD.
main_review: The relevant literature is adequately surveyed. The claims do look right but I think the writing can be somewhat improved. The analysis itself, I believe, is somewhat standard from the numerical analysis literature.

Regarding the result, I'm a bit puzzled by the mismatch of guarantee for Theorem 1 and 2 - one is in terms of eigenvector (iterate) and the other is in terms of eigenvalue (objective function). And related to this, wouldn't something like Wedin's theorem (or slight variation thereof) help translate the result on eigenvalue back to a guarantee for subspace recovery perhaps? It would be nice if the authors could help clarify. Both the statements for Theorem 1 and 2 are also tied to the stepsize that depends on the gap, it would make a much more convincing case if a rigorous argument can be made on how robust the convergence rate is w.r.t these unknown quantities.

I also have some doubts about the practicality of the suggested stepsize for large instances. The plots for the experiments are shown w.r.t \# iterations, but it would make much more sense to show the walltime instead.

Minor typos: At various points in the proof of Thm 1, the index for $\prod$ is reversed.

======== post author-response ==============

Thank you for addressing my comments -- I do think some of these points need better clarification in the paper.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This paper studies an important problem and improves upon existing quantitative results. The reviewers agree that this is a solid contribution and in particular appreciate that both gap-dependent and gap-free bounds are obtained.

The reviewers also recognize as a major limitation of this work that the results only apply to finding the top eigenvectors. It is unclear how the current techniques can be generalized to top-k eigenvectors.

The paper can be made stronger if the authors can add (1) a table for quantitative comparison with existing work, (2) discussion of generalization to top-k, (3) discussion on the choice of initial vectors and the use of random initialization, and (4) discussion on practical implementation. These discussions will be useful to those who want to apply the results in this paper.
Decision: Accept (Poster)