A Comprehensively Tight Analysis of Gradient Descent for PCA
Authors: zhiqiang xu
Ping Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: PCA
Riemannian gradient descent
tight rate
gap-free rate

Abstract: We study the Riemannian gradient method for PCA on which a crucial fact is that despite the simplicity of the considered setting, i.e., deterministic version of Krasulina's method, the convergence rate has not been well-understood yet. In this work, we provide a general tight analysis for the gap-dependent rate at $O(\frac{1}{\Delta}\log\frac{1}{\epsilon})$ that holds for any real symmetric matrix. More importantly, when the gap $\Delta$ is significantly smaller than the target accuracy $\epsilon$ on the objective sub-optimality of the final solution, the rate of this type is actually not tight any more, which calls for a worst-case rate. We further give the first worst-case analysis that achieves a rate of convergence at $O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$. The two analyses naturally roll out a comprehensively tight convergence rate at $O(\frac{1}{\max\{\Delta,\epsilon\}}\hskip-.3em\log\frac{1}{\epsilon})$. Particularly, our gap-dependent analysis suggests a new promising learning rate for stochastic variance reduced PCA algorithms. Experiments are conducted to confirm our findings as well.

A Comprehensively Tight Analysis of Gradient Descent for PCA
Zhiqiang Xu, Ping Li
Cognitive Computing Lab
Baidu Research
No. 10 Xibeiwang East Road, Beijing 100193, China 10900 NE 8th St. Bellevue, Washington 98004, USA (xuzhiqiang04, 1iaggggg com
Abstract
We study the Riemannian gradient method for PCA on which a crucial fact is that despite the simplicity of the considered setting, i.e., deterministic version Krasulina's method, the convergence rate has not been well-understood yet. In this work, O log 2) that holds for any real symmetric matrix. More importantly, when the gap A is significantly smaller than the target accuracy optimality of the final solution, the rate of this type is actually not tight any more, which calls for worst-case rate. We further give the first worst-case analysis that achieves a rate of convergence at O log 2). The two analyses naturally roll out comprehensively tight convergence rate at O max log 2). Particularly, our gap-dependent analysis suggests new promising learning rate for stochastic variance reduced PCA algorithms. Experiments are conducted to confirm our findings well.
provide a general tight analysis for the gap-dependent rate
the objective sub-
Introduction
Gradient descent is basic, well-established, and celebrated optimization method for minimizing convex functions [11, 3]. but remains far less understood theoretically for non-convex functions though it has been proven useful in practice for many non-convex problems [22, 17J. In the past decade, the research on gradient methods for non-convex problems has been gaining increasing attention in optimization and especially machine learning [6, 8, 4]. In this work, we focus on notable example, namely the Riemannian gradient descent for the leading eigenvector computation of real symmetric matrix A E R=**, which lays the foundation of Krasulina's 's method for PCA. This problem can solved by either traditional projection based method from the numerical algebra, such as the well-known power method or Lanczos algorithm [13], or gradient search based method for the associated optimization problem such as the Riemannian gradient descent [18, 21J. The projected gradient descent (with constant step-sizes), as another closely related solver, can be interpreted either as projection method or as a search method in this case (see Section for interpretations). Compared to projection methods which have arguably been well-understood already [13, 9, 10], the search method, i.e., the Riemannian gradient descent, is lacking a clear and deep theoretical understanding their convergence behaviors. This may largely be because the underlying optimization problem is geodesically non-convex:
min f(x)
Ax,
(1)
XES
where the objective function f(x) is constrained on the (n-1)--imensiona) unit sphere manifold g
{x E 1
||x||| = 1} [1].
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Previous analyses of the Riemannian gradient descent for Problem (1) achieve a rate of (global') convergence at O 2 log !) which depends quadratically on the relative gap A between A two (distinct) largest eigenvalues [20, 19I². The poor dependence of the rate on the gap characterizes a loose upper bound on the iteration complexity of the method, due to the artifacts of the used analysis techniques. Ding et al. [5] gave a tight convergence rate at O log 2). However, the analysis is limited to positive definite matrices. This means that the general tight convergence analysis for real symmetric matrices, in fact, has not been settled. Our first goal in this work is to give a general analysis for the tight rate of this type, i.c., dependent gap-dependent analysis hereafter. More importantly, when the gap is significantly smaller than the target accuracy on the objective sub-optimality of the final solution rather than its point distance to the optimal solutions, the rate of this type is actually not tight any more, which calls for a worst-case rate independent of any gap. Our second goal is to further give the first worst-case analysis being able to achieve a rate of convergence at O log 4). The two analyses naturally roll out a comprehensively tight rate of convergence at O( max log 2). Our analyses are based on novel adaptations of the analyses for projection methods working for constant matrices [7, 10] to varying matrices during iterations. We also make a comparison between projection and search methods to help understand their subtle differences. Particularly, the gap-dependent analysis suggests new step-size for search methods which gives rise to a novel learning rate for stochastic variance reduced PCA algorithms. Experiments verify our theoretical findings and demonstrate the effectiveness of the new learning rate. The main contributions are summarized as follows:
the gap, which is termed as the (tight)
gap-independent
We prove the first comprehensively tight convergence rate of the Riemannian gradient descent for Problem (1) at O max log 4).
We propose an adaptive learning rate scheme for stochastic variance reduced PCA algorithms which can dramatically improve their convergence.
We experimentally verify the established theory and demonstrate the effectiveness of the proposed adaptive learning rate.
2
Related Work
We foeus on the gradient methods for the leading eigenvector computation. The classic Oja's algorithm and Krasulina's 's method, as stochastic counterparts of the projected gradient descent and Riemannian gradient descent with diminishing step-sizes, respectively, converge at a rate O x [2]
(Theorem 1.1 where E[ o($) and O ( using their notations except for the iteration number T).. The quadratic dependence on the gap was originally omitted there, probably because the gap was regarded as constant. However, as argued in Musco et al. [10]. this is insufficient. Interestingly, there are much fewer theoretical studies of the two methods in the deterministic setting. Absil et al. [1] introduced the Riemannian gradient descent for Problem (1) (Algorithm 2 there) with the Armijo line search for step-sizes, and implicitly stated a rate at O 1 log 2) (Theorem 4.6.3-iii) which, however, is local (Theorem 4.6.3-ii). Wen et al. [17] proposed d special retraction for the Riemannian gradient descent based on the Cayley transform (Algorithm 1). It was empirically found comparable and more stable than the Lanczos algorithm, however, only with the guarantee of convergence to a critical point (Theorem 2). Since Problem (1) is geodesically non-convex, theories established for geodesically convex functions [23] can't 't be applied unless locally. Note that we only consider global convergence in this work. Xu et al. [19] specifically analyzed the Riemannian gradient descent for Problem (1), and originally stated rate Omin A log 1 2)) (Theorem 1). However, the constituent part O resulted from the same mistake as made Balsubramani et al. [2] and mentioned at the beginning of this section. This means that their analyses are all gap-dependent and the better one of the rates is O A log 2). It is also the case for the work of Xu and Gao 2018 [20] (Theorem 4.1). Particularly, Ding et al. [5] improved the dependence of these rates the gap from quadratic to linear at O( log t). ).. As explained in the previous section, however, it is not general. In
I Only global convergence is considered throughout the paper.
"It needs be noted there that the rate O( was mistakenly stated and actually should be O ( according to their analyses. See the next section for explanations.
Precisely, (xxr) O o($)) ). where 0 0(2,) implied by a's expression, using their notations.
2

---

Table 1: Comparison of convergence rates of the Riemannian gradient descent for Problem (I).
RATE
A
TIGHT
GAP-FREE COVERED
XU ET AL. [19]
O A log
REAL SYMMETRIC
NO
NO
DING ET AL. [5]
O
log )
POSITIVE DEFINITE
YES
NO
THIS WORK
max [.,c) log ()
REAL SYMMETRIC
YES
YES
addition, to the best of our knowledge, before our work, there has been no worst-case or gap-free analysis of the Riemannian gradient descent for Problem (1). Comparisons are summarized in Table 1.
Shamir [14] proposed learning rate scheme for stochastic variance reduced PCA algorithm, namely VR-PCA, based on Oja's 's algorithm. It can be used for VR-PCA's variant as well that is based on Krasulina's method [2, 16]. In this work, we put forward yet another learning rate scheme which we find much more effective than that suggested by [14] for these stochastic variance reduced PCA algorithms.
Notions and Notations
The only assumption on the given matrix A, made in our analyses, is real symmetry, i.e., A A E R.x=, Let A's 's orthonormal eigenvectors be VI, V2, ... Vn. E gn-1, corresponding to eigenvalues A2, An E R, i.e., Av; = A in descending order. If A1 An then let 4p (1 be the first nonzero eigenvalue gap, i.c., Ap = Ap Ap+1 > 0, such that a1 = ... = Ap Ap+1- Particularly, the first nonzero relative eigenvalue gap is defined as A - - if A > An otherwise as A +oc The update equations of the two gradient methods for Problem (1) with constant step-sizes are as follows:
n
X, Vx()
Projected gradient descent (PGD)
X1+1
|x| (x(x)))
(2)
X, (xx))
Riemannian gradient descent (RGD):
X1+1
(3)
X, 7x:](x
where Vf(x)= Ax and (Ixx)=((Ixxx x Ax (throughout the paper I stands for appropriately
sized identity matrix) represent the Euclidean and Riemannian gradients of fxx, respectively, 1y>0 constant step-size, and denominators for normalization, i.c., X S
Consider Algorithm that the Riemannian gradient descent for Problem (1) with constant step-size X E 1 (where &n is entry-wise standard Gaussian), and then repeatedly runs Equation (3) for T iterations. We will focus on the analysis of this algorithm next. The results for the projected gradient descent immediate by much simpler path through the same analysis.
starts from a random initial point Xy |
4 Gap-Dependent Analysis
Let V -vvlvi ... Vpl. The solution space to Problem (1) then is (Vpa: a E SP-1) ) & V, where go = (+1). To study the convergence of iterates to V, it suffices to analyze the principal angle between X, and Vp, i.e., 8(x,, Vp) = cos cos- "[IVV] xxl12). Let V = [Vp+1
vn and Df represent the pseudo-inverse of a matrix. Then tan 0 V,) = ||(V] Ro), (o)o))ll... Suppose that T' iterations are sufficient for sin" 0xx,, V,) 1 VV x, ll reach the target accuracy > i.e., sin" fxx,, Vp) < 6. The goal of our job here is to upper bound 7 with the gap information and show that the bound is tight, namely
Theorem The Riemannian gradient descent for Problem (1) with step-size 7 = +(,,-x))
A1-A., converges in T O 1 log ") iterations, i.e., sin? 0(x,, Vp) < w.hpp (with high proba- bility).
3

---

Proof First, it is trivial and T = 0 for the case that \1 = An since f(x) is a constant. Thus, it is always assumed that X1 > An in what follows. Let (x) = + 7 x Axi) and write
(A) = Ei=1 he (Ai).... = Vvhh(Zn) where hr (2n) = (Ai): .M.. (Nn)). We
can write that
XT hr 1 (A)xT-1
M (A)xx
IT he (A)xo
(4)
Il - (A)xull2 I (A)Axx2
where the second last equality is equivalently renormalized. Noting that the initial point xo can be expressed as xi= (v; xo)vs, the last numerator above can be written as
1 (A)x0x Ei xo) Io he (A),,
Ex= (v. X0) IT, (o().)
Accordingly, it holds that
IV IL hc(A)xo Σ (v. x0) Io=oo h2(A)),
( (A)xx = E (v. X )² IT:=0 (A,).
By the fact that x T Ax E [',, An] for x E s (Corollary 4.7 in [15]). we have that (A,) 2
1 + 77An. X)) for all and t. If + 7>nn A1) 2 0, i... 1) S A._ it then holds that he (X:) 2 0
for all and t. When 1j S A, we can get that
sin 0XT, vp) 1- VV p XT 12
Σ _
( Xo)
T (2,)
2i (v. )² II T-1 122
=
(V. X
T
(2,)
Σ (v. xx)
-o 12 (N,)
(5)
T-1 h2 (Ap+1) bip+1 (v. xo)²
T-1 ho() tan? 0(xo, Vp)
1=0
ITT h2( Ei=1 (v, x²)
hx(A1)
t=
r(pp+11 - Xnn) 2 Lan? 0(xo, Vp)
1 1111= - Am))
2T X,,))
expl 1 11+1(1 1 ((11
tan 6(xu, Vp) c
where the second last inequality have used the fact that 1+00g11-2) is nonnegative and mono- T+1(11=2)
tonically decreasing for E [Am A1]- Solving the last equality about for T yields that T L+m(Ar- -Am)
2n log tan? 0(xg, Note that V and (V &u)) are entry-wise standard Gaussian since V -pp and Vp are orthonormal. By standard Gaussian matrix concentration theory [12], w.h.p. T x S cin and [I x0) l/ S cap for some fixed constants Ci, c We then have w.h.p. that tan (xx, Vp) S cap for some fixed constant e and log tan? 0(xo: Vp) = O(lg(n)). Hence, T= log 4) for 1) = 0 -x,=)
To justify the tightness of this upper bound, now show that the Riemannian gradient descent for Problem (1) requires 22 ( log ") iterations to converge. To this end, we resume the analysis from Eq. (5) as follows:
xT 12 Σi (v. Xo)
(2((
sin 2 0(XT, Vp)
1- V
Σ (v. xx)x ITLo h2(A,)
(v Vo xo) 2 IITT1 h/2 (Ap+1)
T
> 1 (v. x0)² 1211 h?((b)
14 EL (v. (v] xo)
-IT-
1- he(As) )2
(V (v)1200)2
1
(1 - ,) tan 0
1 + DL (v. xo)²
T T-1 1 )2
1 1+ (1 1lnn-App tan 9
(V (V,t xo)=
I1t=0
(I
2 m)p))} tan 8
1 1+ exppp pT/TT/1 - 1) m))))) tan 0'
4

---

where tan 0 (x))
2i (v. xo)² and we have used for the last inequality that (1 -) 2T
(27 log(1 p) 2 expl 2nd,T 1- } by log(1 x) 2 Ite for > -1 Setting
exp expl-I-n3,
2n I- } tan 0 = 2e yields that T = I-nAr log tan and sin 0(xT, Vp) 2 1-22 z
2
2nd,
2c
assuming E < 1. Hence, for r) = ( (x,,-x,,, we need T = 2( log 2) iterations to get sin² ((x,) Vp) which completes the proof.
Remark 1 In the gap-dependent analysis above, from the optimization point of view, we care more about the distance of the iterate x, to the optimal solution set V. i.c., sin ((x, V,) = minvev ||x - vI12. with emphasis on the eigenvector computation. In fact, it is also common to consider the objective sub-optimality gap, i.e., (x(x;) minlxes--) [x)) = (Ai - x! Ax₂), with emphasis on the eigenvalue computation. From the proof of Lemma 4.6 Xu and Gao 2018 [20]. we know that λ x Axt I (A1 An) sin 2 ((xT, Vp). By Theorem 1, with e-rescaling, we then have that \1= - x AxT < E for T = O 7)
5 Gap-Independent Analysis
The issue of the gap-dependent rate in Theorem is that when the gap A significantly smaller than the target accuracy the convergence in terms of sin" 0(xr, Vp) is too slow, e.g. T== O log ") for A )e²). In this case, it is often acceptable to swap the true leading eigenvector for any e-accurate solution Xy E g in terms of the objective sub-optimality gap, i.e. ò - x AxT < e. In this section, by extending the analysis of Musco et al. 2015 [10] for constant matrices (i.e.. (z( = z), we show without the need of the eigenvalue gap information that even if the gap A is significantly smaller than the target accuracy, we only need O log )) (far less than O log ") for, e.g., A = (c3/2), see Remark 1) iterations to achieve that \1 - A < c, as stated in the following theorem the worst-case performance.
Theorem The Riemannian gradient descent for Problem (1) with step-size nj = 0(1) S A1-An converges in T = [ log ") iterations, ie., X1- X AxT
<
Proof Sketch Due to space limit, we only give proof sketch here. The complete proof and all the missing proofs can be found the supplementary material. We assume again that À > Aa and 1 - such that he():) = 1 + n(); x, Ax,) 2 0 for all i and 4. It suffices to show
that \ x < 2e always holds no matter whether A is significantly larger than X2 in the
sense that ho (A1) ) 2 (1 + (/2)ho(\2) for 0 < 8 < 2. We take T T==1 [ log m(1+tan 0o) + 1, where Oo- 0(xo: V.).
Case that ho (11) (1 + 8/2) Consider the polynomial
pr(x) = /(1 8/2) (2)) IT=-1
(x (1+672)b.
2 O, x E A1n
and matrix form (A) = Σ (A.)vav. = VPr (n)) VT, where (E.) = diag(pr (Az),
(A.)) We have
Fact For x E [An, A2], (o2) 2 (1 (1/2))oo()) implies h₂ 2 (1+ (z)) for all t, by
Lemma 1f11 S
A1-X- then x Ax++1 2 x, Axi.
2
Hence, (r() 2 Vho(dz). Also, (r())) S (ho(da) 8/2) 2, .n. Eq. (4) can (A))) where the rank-1 approximation inequality for pr (A) holds: be rewritten as Xx (A)xoll)
[A) - xxxTpr(AA]]E
< (1 tan? 0o) |pr (A)
= (1 tan 0n) (2))
< (1 tan? 00) 1) 8//22) 2T++1 - ho(2))e
5

---

At the same time,
(PT( - XTXIPT (A)1
= IIPT - (1)
2 (1-
Thus, \1 - -x < e holds by noting that
ho1) (F) = ho1 Ei= (X.
- (1 )2)oo)) < cho()22)
Case
that ho(A1) < (1 8/2) Consider the polynomial qí (x) = v hho(21) II Ax(w)
and write XT rewrite
fr(A Xx. lor Axx0
Define the index set a = {i: T ho (A1) S no(A,) < ho and
Eisa QT (A))vvvvv Xo
Eigo 9 (N.)vov,7 x & x(a) + x x(aa
XT
11 A A)x0l22
1 (A)xxl
We then have 116 (A)xf) (0) 112 2 (o))2 (1 c)ho for d = 2e, where the first
inequality is by the definition of the index set. For XT (-a)
A
x(=
or (A and [yr(A-a)xoll) -xolll
[x I12
A A Eiea A.v.yy similar argument to Case can be applied to get that ho(A1) ho (A ax)ff-a) ho(de)e Then [|n (A)xf-0))
(x7 )
(x) ho(A (xa)) >
e)ho(d1). Thus, d1- AXT < Ze holds by noting that "
(A)xxT (A)x ll |I (A)
|| m 12
- 1/2 (A)x
> (1 + ||
ko - = (1 - (A1o
Remark 2 When the gap is significantly larger than the target accuracy c, e.g., A = 0(1), and sin? ((xT, Vp) 2 1A,- for T O log
=(A)=A=)A (see the proof of Theorem 1 on the tightness), we have that d x AxT 2 (A An) 0(XT, V,) 2 by Lemma 2 in Xu al. [19]. Thus, it needs log log ") iterations to make it. Thus, a comprehensively tight rate can be stated as O( mass (A.e) log l)
need T Q x log ") iterations to get d Ax 6. Otherwise,
Remark 3
The analysis of Case in the proof of Theorem 2 can give us a gap-dependent rate:
7
ho(A1) 1 17\1- X Axx) (1 1 11122 X1 Axo)
)(1 nn x Axo))
1 (ho()2) 2 (1 7 ()o
(1+ + 1 11(22 Apa
Taking 8 = n in T [ log n(1+tan" Go)
+ gives T 0 nA log "). It is straightforward to extend to the setting \ = = Ap Ap+1 of the previous section to get T = O log ") with 4, and O ---x), But it is worth mentioning this is about the convergence in terms of \1 xI AxT < e, rather than sin? 2 (XxT, Vp) E.
Remark 4 Compared to (A) = A which leads to simple monomials in [7, 10], AA( =
I+ ( x Ax, I) varies with iterations and requires complicated polynomials in our analysis.
In addition, from Remark 1-2, it holds for ||x||2 = that A sin" 0xx, V,) < f(x) - f(vi) < {A, - >m)) sin² 0(x, Vp). Note that either these inequalities or Wedin's theorem can't 't be used to translate results between Theorem and Theorem 2, because the translated results by these incqualitics may possibly be worse and Wedin's 's theorem (which upper bounds perturbation of eigenspace in

---

subspace distance by those of both the given matrix and corresponding gap) is inapplicable here. For example, by the second inequality and Theorem we can get λ X Axy e for T O 1 log ")- But when A is much less than e, '' will clearly be worse than the results in Theorem 2. On the other hand, by the first inequality and Theorem 2, we can get sin (xr, Vp) < 6 for T = 0 = log ) which is worse than the results in Theorem 1.
6 Projection Versus Search
To be specific, in this section, we refer to the power iteration (PI) and Riemannian gradient descent (RGD) as the projection and search methods for Problem (1), respeciveely and the projected gradient descent (PGD) belongs to both classes.
The above analyses for the search method apply the PGD by simply setting he(x)) In this case, represents the step-size and needs satisfy 0 < S to make sure h₂,),) 2 0 for all i, where p max; |xj is A's spectral radius. Assuming that A > O, it will converge to Vi. On the other hand, the analyses [7, 10] of the PI apply to the PGD as well. Then v/ can be any nonzero real value and the PGD converges to Vo(1) assuming that the largest two values of (Ax)() j=, ... _ are distinct, where maps to such that (2,)l is the i-th largest value of (Ay) : 1,
mpc.
1,... n). In addition, the PI can be seen as the PGD with constant step-size 7 too, and can also be interpreted as the RGD with varying step-sizes T) positive definite.
when A is
x Ax:
Table 2: Comparison of the PI, PGD, and RGD.
Xc+1
A
T
Xy
A
PI
(+x)
1
Ar(1)
Ao(2)
max [ log +)
Vo(L)
Ae(1)
PGD
(0, )
A1
[3.] log +)
RGD
[|x (xl
(0, -
A1 Am
max [.r] log :)
VI
Table 3: Contraction factors of the PI, PGD, and RGD on positive definite matrices.
Pl
PGD
RGD
(x(x)
1 f
+ 7(
x Ax:)
hra))
1
1 A
1
(.(A))
A
" +Ai
1 Ax:
Table 2 summarizes the comparisons between these methods for Problem (1), where represents the target accuracy for A AxA, and (xf,Ar, Xy)) describes which eigenpair approximates. Table 3 shows that the PGD even with varying step-sizes 1)t S always gets larger contraction factor ke(Aa] ((() (see the equation right below Eq. (5)) than the PI, but the RGD can achieve a smaller one when step-sizes satisfy that 7)
Ax," In practice, it may be worth try to set 7) x, Ax, with r > 1. However, the Riemannian gradient descent update requires more computations than the power iteration in each step. possibly leading to an even worse wall-clock running time. This can be easily seen from the equivalence between the two methods with
In the next section, we will investigate the effect of this step-size scheme Y) x Ax. (T 1) on both projected and Riemannian gradient descent for cigenvector computation as well as the stochastic variance reduced algorithms for PCA (VR-PCA) based on Oja's algorithm Krasulina's 's method.
7

---

7 Experiments
The purpose of the experimental study for corroborating findings in above sections is twofold. One is to verify the rate (((1/ max A +)) log(n//)) of the Riemannian gradient descent on real symmetric matrices in the form of A E TRmxx. The other is experiment on the step-size scheme for both projected and Riemannian gradient descent methods on PCA data in the form of C E Redx such that A CC Experiments were done on a laptop (dual-core 2.30GHZ CPU and 8GB RAM).
The constituent part (((L/A) log(n/e)) of the rate has been experimentally verified in Ding et al. [5]. Hence, only the worst-case rate (((1/e) log(n/e)) needs verification, for which we generate synthetic data A-VEVT as follows. Given 1=1000, 1010 A=0.01 and entry-wise i.i.d. standard normal U E R a E (R=
we consider orthogonal V = U( and diagonal Σ diag(2I Adiag(0, 1, .s), _diag([a [an=s-1) ()). In this case, the convergence for each method considered in this work should behave differently in terms of different measures, i.e.,
log(nc)) for (A1 x Axx) versus O((1/ A) log(n/c)) for sin? ((xr, V1).
10
10
101
PCDD PGID-
sir v.
0.9
- A 1/
10
PGD
0.8
airRix
104
PGDD
10
0.7
10
20
40
50
90
100
20
40
60
80
100
0.03
0.06
0.01
0.08
Iterationa
A Ileration
Time (Sec.)
Timo (Seo.)
10
RCD BCIDoN
80 V.1
0.8
10
Atr
0.6
0.
10
10
10
0.4
10
0.02 (Sec.)
0.04
0.4
0.02
0.04
Itarationns
Ittrationns
Timo
Figure I: Test on synthetic data.
We implemented the PGD with 11 p. 1)t x, Ax, Ax. x, Ax,' and RGD with step-size schemes
1.6
y = A 1/+ Ax,' x, Ax, Ax," MATLAB. Each is compared the PI. All the methods start from the same random initial point X, and run for T = 100 iterations. Figure 1 reports their performance across iterations (or the average performance over time on 10 runs) in two measures, where the y-axis of the figures in the first and third columns is in log scale of (A1 x, Ax.) /1 It is clear for each method that (>1 x, Ax;) converges sub-linearly while sin? 0(x,, v1) ) is decreasing even more slowly, matching their respective theoretical rates. Consider the case that = 0.01 and accuracy 0.1 here. First, from the figures on the left in Figure 1, it is clear that the (relative) target in objective converges sub-linearly (note that y-axis is log scale here), roughly matching (((1/e) (og))))) iterations. From the figures on the right, the target sin? 0(x,, v1) converges about one order of magnitude slower than the target in objective, roughly matching (((1/e²² (((1/e))log(n/e))) log(n/e)) iterations which is basically consistent with (((IA) log(n/e)) for 0.1.
We also experiment on two real d Schenk that was used in [19. 5] and GHS indef. Schenk is a 10728 x 10728 real symmetric matrix with 85000 nonzero entries. The performance is depicted in Figure 2, where all the methods converge linearly due to a large gap and their differences are sharper. Particularly, we add the plot of the average performance over time on 10 runs. Although the RGD with 7) = x, Axi is theoretically the same as the PI (thus performing exactly the same over iterations in Figures 1 1-2), it needs more computational costs reflected by the wall-clock time in Figure Nonetheless, Figures 1-2 showcase the great potential of the RGD with aggressive step-size 1.6 here, in practice. In the meanwhile, the performance schemes to outperform the PI, e.g., 7)t x, Ax,
of the PGD even with adaptive step-sizes worse than that of the PT. We tested significantly larger
'nttps://sppan tamu.
8

---

10
Schenk
Schenk
Schenk
Schenk
X -u 3.4
10-9
RGD
NGD
10
sirWe
NG77
10112
10"1
10'12
10
10'19
10"
10
0.005
0.015
0,028
10
0.005
0.015
0.025
10
10
100
X 1/4
10-
sirR00 94)
10"
10
atrin 71
10
10
10
10
10
19
10
10
0
20
40
50
80
100
10'1
40
00
100
16
0.08
0:18
0.05
0.15
Ieeraions
lterations
Time (Sac.)
Time (Sec.)
Figure 2: Deterministic Krasulina's method on Schenk and GHS indef with adaptive step-sizes.
constant in x; Ax, PGD's performance is still worse than that of the PI. Similar results appear on GHS jindf which 76638 76638 real symmetric matrix with 859520 nonzero entries.
Algorithm 1 VR-PCA (Oja)
Alooithmm 2 VR-PCA (Krasulina)
1: Input: C (c1, Cn) E Rdxn, No. 1: Input: C = (C1.
.x,) E Rdx" No. T,
T, = l0t], m [g]. S, where [n]
b [as]. m n 1
(1,2,..,,1) .n.
Output: X5
2: Output: Xs
3: for = 0, 1, ... S do
3: for 0, , do
4: g. 1 (CC x, x x ). xo No.
4: g, a
1CC X,, Xy x,. 17s | x.13
a7
? = &
5: for 0,,, m do
5:
for = 0, 1.. m do
6: Pick a: C [n] uniformly at random
6:
Pick at C [n] uniformly at random
7:
Eiea: C,O, (x+ x,) + +
7:
g:
Eiea. (c.ce (x:
x,)
8: Xc+1
x, 8:
((c) x,)
(c. xx,)x,))))))))))))))))))))))x) g
9: end for
8:
Xx41 8+
x.=noE
9: end for
10: X, Xm
11:
end for
10: X, Xm
II: end for
Table 4: Statistics of PCA data
DATA
DESCRIPTION
n
MMILL JW11 MNIST
MULTI-LABEL IMAGES
221
30000
ACOUSTIC AND ARTICULATION
385
30000
IMAGES OF HANDWRITTEN DIGITS
784
70000
We check the performance of two versions of the VR-PCA based on Oja's algorithm and Krasulina's method, corresponding to Algorithm in the work of Shamir 2015 [14] (Algorithm above) and variance reduced version (see the supplementary material) of Algorithm 1 in the work of Tang 2019 [16] (Algorithm 2 above), respectively, where the constant learning rate is replaced with the proposed adaptive learning rate scheme. The common PCA datasets used and summarized in Table We use = 100. Note that we only update the learning rate at the epoch level and keep unchanged within each epoch, similar to the case of the computation of the full gradient. Figure reports the average performance of the VR-PCA with our adaptive learning rate on three real datasets, following the previous experimental setting on Schenk except for 5 used for average. It is easy in the PCA setting consistently to see that the proposed learning rate scheme (i.e., [

---

MMILL
MMIILL
MMILL
MMILL
X 1.A,,
10"
10'
10
10
10
an
10
Squclali
10'2
10
10
10"10
10"10
500
100
300
2
Passes
# Passes
(Sec.)
Time (Sec.)
10
JW/1
JW/1
10
JW11
10
JW11
AA 1/4
10
10"
x AAxx117 1,A,A
10%
10"
sirWWy
10
10
1011
10112
10
1011.
10
10
10
100
300
500
100
320
500
Passes
Passes
Time (Sec.)
Time (Sec.)
MNIST
MNIST
10
10
Axx 1/A,
sin V.
10
sin WW v.
10%
X.Ax
10
12
10
10112
10
10
10
300
10
20
30
10
20
30
Time (Sec.)
Time (Sec)
Figure 3: VR-PCA on MMILL, JW11, and MNIST with adaptive learning rates.
works better than that proposed Shamir 2015 [14] (i.e., 1)
/n across the datasets, for both C.I.
versions of the VR-PCA. Interestingly, an opposite case (see Figure 2 for the deterministic setting) happens that the performance of the Oja-based VR-PCA performs significantly better than that based on Krasulina's 's method. This shows that the proposed learning rate scheme is very promising for the practitioners of the VR-PCA.
Conclusions
We presented two analyses of the Riemannian gradient descent for eigenvector computation. Specifi- cally, the gap-dependent one is the first general analysis that achieves tight rate 0 ( log _) terms of the point distance to the optimal solutions. However, if we are only concerned with the objective distance to the optimal solutions, the rate of this type is not worst-case optimal. We succeeded in establishing worst-case rate O log 2 independent of any gap, by adapting an existing analysis for projection methods to our context which a prominent characteristic lies in varying matrices hy (A) during iterations, and ended up with comprehensively tight rate O max((A.] log ") In addition, we discussed the equivalence and subtle differences between projection and search methods that give rise to new insights on the step-size schemes, and conducted experimental studies to verify the established theories. Particularly, the proposed adaptive learning rate scheme for the VR-PCA works far better than those proposed previously. One limitation of our analyses lies in the great difficulties of their extensions to the block setting where E R for because X AX, is no longer scalar but matrix and the key matrix function hy (A) then is not well-defined for the analysis. We consider overcoming the underlying difficulties in this setting as an important future work.
(this work corresponds to 1),
References
[1] Pierre-Antoine Absil, Robert E. Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008
[2] Akshay Balsubramani, Sanjoy Dasgupta, and Yoav Freund. The fast convergence of incremental PCA. In Advances Neural Information Processing Systems (NIPS), pages 3174-3182, Lake Tahoe, NV, 2013.
10

---

[3] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014.
[4] Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM J. Optim., 30(4))3098 -118888-11,,, 3121, 2020.
[5] Qinghua Ding, Kaiwen Zhou, and James Cheng. Tight convergence rate of gradient descent for eigenvalue computation. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), pages 3276-3282, 2020.
[6] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: unified geometric analysis. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1233-1242, Sydney, Australia, 2017.
[7] Gene H Golub and Charles F Van Loan. Matrix Computations, forth edition. Johns Hopkins University Press, 2013.
[8] Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Found. Trends Mach. Learn., 106--))142-33) 2017.
[9] J. Kuczynski and Henryk Wozniakowski. Estimating the largest eigenvalue by the power and lanczos algorithms with random start. SIAM J. Matrix Anal. Appl., 13(4): 1094-)0099-1122 1992.
[10] Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems (NIPS), pages 3396-4044 Montreal, Canada, 2015.
[11] Yurii E. Nesterov. Introductory Lectures on Convex Optimization Basic Course, volume 87 of Applied Oplimization. Springer, 2004.
[12] Mark Rudelson and Roman Vershynin. Non-asymptotic theory of random matrices: extreme singular values. arXiv preprint arXiv: 2990, 2010.
[13] Yousef Saad. Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
[14] Ohad Shamir. A stochastic PCA and SVD algorithm with exponential convergence rate. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 144-152, Lille, France, 2015.
[15] G. W. Stewart and Ji- Ji-Guang Sun. Matrix Perturbation Theory. Academic Press, 1990.
[16] Cheng Tang. Exponentially convergent stochastic k-pea without variance reduction. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems (NeurIPS), pages 12393-12404, Vancouver, Canada, 2019.
[17] Zaiwen Wen and Wotao Yin. A feasible method for optimization with orthogonality constraints. Math. Program., 142(1-2):397-434 2013.
[18) Zhiqiang Xu. Gradient descent meets shift-and-invert preconditioning for eigenvector compu- tation. In Advances in Neural Information Processing Systems (NeurIPS), pages 2839, Montréal, Canada, 2018
[19] Zhiqiang Xu, Xin Cao, and Xin Gao. Convergence analysis of gradient descent for eigenvector computation. Proceedings of the Twenty-Sevent International Joint Conference on Artificial Intelligence (IJCAI), pages
Stockholm, Sweden, 2018.
[20] Zhiqiang Xu and Xin Gao. On truly block eigensolvers via riemannian optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 168-177. Playa Blanca, Lanzarote, Canary Islands, Spain, 2018
[21] Zhiqiang Xu and Ping Li. On the riemannian search for eigenvector computation. Journal of Machine Learning Research, 2021.

---

[22] Florian Yger, Maxime Berar, Gilles Gasso, and Alain Rakotomamonjy. Adaptive canonical correlation analysis based on matrix manifolds. In Proceedings of the 29th International Conference on Machine Learning (ICML), Edinburgh, Scotland, UK, 2012.
[23] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Proceedings of the 29th Conference on Learning Theory (COLT), pages 1617-1638, New York, 2016.
12


Reviews:
[{"review_id": "fNym8atOiVy", "reviewer": "Reviewer_g4Fd", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nRegarding 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.\n\nI 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.\n\nMinor typos: At various points in the proof of Thm 1, the index for $\\prod$ is reversed.\n\n======== post author-response ==============\n\nThank you for addressing my comments -- I do think some of these points need better clarification in the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SQqyo97d31", "reviewer": "Reviewer_UVrc", "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.\n\nThe 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)$. \n\nExperiments comparing the power iteration, projected gradient descent and RGD are done for proposed adaptively chosen step-sizes. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThat said, some concerns:\n1. 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?\n2. 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. \n\n\n[1] Xu, Z., Cao, X., & Gao, X. (2018, July). Convergence analysis of gradient descent for eigenvector computation. International Joint Conferences on Artificial Intelligence.\n\n[2] Musco, C., & Musco, C. (2015). Randomized block krylov methods for stronger and faster approximate singular value decomposition. _arXiv preprint arXiv:1504.05477_.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable since the work is mainly theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "Cab9rUfTN7f", "reviewer": "Reviewer_ZjFy", "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Paper achieves new state-of-the-art theoretical results for Riemannian gradient method for PCA. Clear accept", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "9tj5x6hs7nx", "reviewer": "Reviewer_KXps", "summary": "This paper provides a tight analysis of riemannian gradient descent of its iteration complexity. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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 \nto 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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "5q8E7IhCFx", "reviewer": "Reviewer_AfhS", "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.\n\nFor 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.\n\nOverall this is a solid paper with both theoretical analysis and empirical studies.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nQuality:  This paper has good quality with comprehensive theoretical analysis and rich empirical experiments.\n\nClarity: The writing is clear. The footnote in page 7 is a bit too long, authors may consider put it in the main text. \nAlso 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?\n\nSignificance: 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.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not observe any potential negative societal impact of their work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "Not observed", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)