Tight Convergence Rate of Gradient Descent for Eigenvalue Computation

1 Introduction

Leading eigenvector computation has been studied extensively during the past few decades. Power method and Lanczos method have been applied to solve this problem, and their convergence rates have been well justified. In comparison, Riemannian gradient descent (RGD) is another efficient algorithm for this problem, but its convergence rate has not been tightly characterized yet [Absil et al., 2009; Xu et al., 2018]. Given a symmetric and semi-positive definite (PSD) matrix A, Riemannian gradient descent uses the following update rule repeatedly to compute the leading eigenvector:

Here R is some retraction over the unit hypersphere, and gradf(x) is the Riemannian gradient of the Riemannian function f(x). (See formal definitions in Section 3.) An important property of RGD is that it embraces a large family of algorithms via different choices of retraction, stepsize scheme and metric. As suggested by the empirical results in [Xu et al., 2018], Riemannian gradient descent with Cayley transformation as the retraction rule is comparable to the Lanczos algorithms in convergence rate but is even more stable.

However, the convergence analysis for Riemannian methods on leading eigenvector computation is not tight. In [Absil et al., 2009], only asymptotic convergence results are proven. And recently, [Xu et al., 2018] proved the convergence rate of O( 1 ∆2 ln nϵ ) by Lyapunov analysis using a logarithmic potential function. However, we show that the tight convergence rate is O( 1∆ ln nϵ ) and the analysis in [Xu et al., 2018] in fact suffers from a quadratic loss. Our method involves an innovative reduction and chaining based argument that enable us to track the progress much better.

Another popular method for leading eigenvector computation is Oja's rule [Oja, 1982]. We remark that the original algorithm in [Oja, 1982] has an online and a deterministic version which are quite different. The online variant has been well studied [Shamir, 2015], while the convergence rate for the deterministic version remains unknown. We focus on the deterministic version throughout the paper.

In terms of convergence analysis of Oja's rule, only asymptotic convergence results are established using the method of invariant set [Oja, 1989; Yi et al., 2005] . However, we prove that the convergence rate of Oja's rule is in fact O( 1∆ ln nϵ ). Our method for proving convergence is based on a two-phase argument: in the first phase we obtain an exponential decay of the tail error; and in the second phase we attain an exponential growth of the principal component, by analyzing a noisy fixed point iteration.

An interesting observation is the connection between RGD, Oja's flow and Oja's rule. We show that RGD and Oja's rule are in fact two different discretizations of Oja's flow.

We summarize our main contributions as follows:

• We use innovative reduction and chaining techniques to show that RGD has tight convergence rate of O ( 1∆ ln nϵ ) for leading eigenvector computation. This improves the prior analysis [Xu et al., 2018] by a quadratic factor.
• We use a two-phase analysis and a detailed study of a noisy fixed point iteration to establish convergence rate of O ( 1∆ ln nϵ ) for Oja's rule. The prior analysis [Oja, 1982; Oja, 1989; Yi et al., 2005] only gave asymptotic convergence results.
• We validate our convergence results on both synthetic

and real datasets. The empirical iteration complexity matches with our iteration complexity bound, and is much better than that proved in [Xu et al., 2018].

We remark that these techniques could be applied to analyzing other algorithms for eigenproblems as well.

2 RelatedWorks

Riemannian optimization is a meta-algorithm for solving optimization problems using the inherent structure of the feasible space. [Absil et al., 2009] is an excellent survey on this topic. In the past few decades, Riemannian method has been shown to be a powerful tool for solving optimization problems with orthogonality constraints [Wen and Yin, 2013]. It also has a useful Matlab toolbox [Boumal et al., 2014].

The leading eigenvector computation is one of the most widely studied problems using Riemannian optimization method [Absil et al., 2009]. The asymptotic convergence results for RGD on eigenproblems have been established in a number of papers and books, see [Absil et al., 2009] for example. However, the non-asymptotic convergence rate of this method is still undetermined prior to this work, and the tightest analysis before this work is O ( 1 ∆2 ln nϵ ) due to [Xu et al., 2018].

There are also convergence results for RGD on geodesically convex(g-convex) functions [Zhang and Sra, 2016; Zhang and Sra, 2018]. However, the Rayleigh quotient function is neither g-convex nor g-concave on the hypersphere [Absil et al., 2009]. Thus, the convergence results on gconvex functions is not applicable to it.

The Riemannian method is also called natural gradient descent (NGD) in deep learning society [Amari, 1998], which is further equivalent to mirror descent with certain metric [Raskutti and Mukherjee, 2015]. Recently, Riemannian method is shown to be efficient for training deep neural networks, whose loss surface can be highly non-convex and non-smooth [Li et al., 2018]. Despite the superiority of the Riemannian method, few theoretical justifications have been given so far [Pascanu and Bengio, 2013].

Oja's rule was introduced by Oja for principal component analysis (PCA) in [Oja, 1982]. The deterministic version of Oja's rule, together with its continuous-time analogy called Oja's flow, have been widely studied in the literature since its invention [Chen et al., 1998; Yan et al., 1994; Yi et al., 2005]. [Yan et al., 1994; Chen et al., 1998] proved linear convergence of Oja's flow, and [Yi et al., 2005] proved asymptotic convergence of Oja's rule. However, the nonasymptotic convergence rate of Oja's rule is only known to be at least sublinear prior to this work (see Table 1 for a summary). A great exposition of this topic can be found in [Helmke and Moore, 2012].

3 Preliminaries andMain Results

We first give the definitions for the terminologies in the Riemannian method. A manifold M is a nonlinear space that is locally isomorphic to the Euclidean space in the neighborhood of each point. For example, the unit hypersphere in the n-dimensional Euclidean space is a submanifold of dimension n - 1 with the induced metric, and is denoted as Sn-1 . At each point x ∈M, there is an associated structure, called the tangent space Tx(M), which is also a linear space. For the unit hypersphere, the tangent space is just the tangent plane at some point x ∈ Sn-1 , which can be explicitly expressed as Tx(M) = {y|〈x, y〉 = 1, y ∈ Rn }. Riemannian function assigns each point on the manifold a real value f (x) ∈ R, ∀x ∈ M.

The leading eigenvector computation considers the problem of finding the leading eigenvector e1 (or -e1), given a symmetric and positive definite matrix A ∈ Rn×n . We denote the eigenpairs of A as (λi, ei), ∀i ∈ [n], with {λi, i ∈ [n]} arranged in non-increasing order. We make the standard eigengap assumption [Musco and Musco, 2015] that λ1 > λ2, though it is trivial to generalize it to the case where λ1 = λ2 = ... = λp > λp+1, which is called the general p-th eigengap assumption. The eigengap ∆ is defined as ∆ = 1 - λ2 λ1 ∈ (0, 1]. The leading eigenvector problem is equivalent to the following Riemannian optimization problem [Absil et al., 2009]:

Here f(x) = xT Ax, ∀x ∈ Sn-1 is a Riemannian function over the unit hypersphere. The Riemannian gradient of this function is g(x) = (I - xxT )Ax, which gives the locally steepest descent direction at x restricted to the tangent space of x. After updating x using the gradient by y = x + ηg(x), we will need a retraction that maps the tangent plane to the hypersphere. The most widely used retraction is just the normalization, R(x, ηg(x)) = x+ηg(x) ‖x+ηg(x)‖2 . To this end, we have the following RGD update rule for leading eigenvalue computation.

Riemannian gradient descent:

For leading eigenpair computation, Oja's rule [Yi et al., 2005] is equivalent to Riemannian gradient descent method without retraction. And when η → 0+, it evolves to its continuous counterpart, Oja's flow, which can be characterized by an ordinary differential equation (ODE) as follows.

Oja's rule : xt+1 = xt + ηg(xt).

Oja's flow :

˙x(t) = g(x(t)).

Here ˙x denotes the derivative of x with respect to t, or equivalently, dx dt . Through the lens of numerical integration [Hairer et al., 2006], it turns out that Oja's rule and RGD are essentially two different discrete integration algorithm for Oja's flow. Using forward Euler method to discretize Oja's flow gives us Oja's rule, while using the structure-preserving method to discretize it gives us the RGD algorithm (See Figure 1).

Before we delve into the technical proofs, we present our main results and briefly discuss the techniques we use. Our first convergence result is the convergence rate of RGD, which is quadratically better than the previous result [Xu et al., 2018].

Theorem 1 (Convergence of RGD). Under random initialization over the unit hypersphere, RGD with stepsize η = 1 λ1 converges to e1 (or -e1), and it achieves precision ϵ ∈ (0, 1) such that ‖xt - e1‖2 ≤ ϵ (or ‖xt + e1‖2 ≤ ϵ) in O( 1∆ ln nϵ ) iterations with high probability.

Our analysis for RGD uses innovative reduction and chaining techniques. These new techniques enable us to track the convergence procedure step-by-step without much loss and allows us to obtain a tighter bound than [Xu et al., 2018]. We also provide concrete instances to show that our characterization is essentially tight.

Our second convergence result is the convergence rate of Oja's rule as the following. We remark that the previous analysis [Oja, 1982; Oja, 1989; Yi et al., 2005] only gave asymptotic convergence results for this algorithm.

Theorem 2 (Convergence of Oja's rule). Under random initialization over the unit hypersphere, Oja's rule with stepsize η = 1 4λ1 converges to e1 (or -e1), and it achieves precision ϵ ∈ (0, 1) such that ‖xt - e1‖2 ≤ ϵ (or ‖xt + e1‖2 ≤ ϵ) in O( 1∆ ln nϵ ) iterations with high probability.

Since no explicit retraction is used in Oja's rule, the convergence in L2 norm is non-trivial. We prove this result using the invariant set technique [Yi et al., 2005] and a detailed analysis of a noisy fixed-point iteration.

It is important to point out that Oja's flow was shown to converge at rate O( 1 λ1∆ ln nϵ )[Chen et al., 1998]. However, the analysis heavily depends on the ODE characterization that allows a smooth calculation since it is continuous in time. However, the recurrence in the discrete algorithms can be extremely complex to analyze even just for a few iterations. Thus, we need to develop fundamentally new techniques for proving convergence rates of the discrete algorithms.

The rest of the paper is organized as follows. In Section 4 we present our proof for the convergence rate of RGD (Theorem 1). In Section 5, we continue to prove the convergence rate of Oja's rule (Theorem 2). We conclude the paper in Section 6.

4 Riemannian Gradient Descent

Our analysis for RGD mainly consists of two phases. First, we reduce the dimension of the convergence procedure from n to 2 for a single step and further for multiple steps, without compromising on the convergence rate (Lemma 1). Then, we investigate the basic 2-dimensional case and give the convergence guarantee shown in Theorem 1. Here we denote ∠(a, b) as the angle between vectors a and b.

Lemma 1 (Multiple-step reduction). If we take η ≤ 1 λ1 , then for two sequences {xt} and {yt } generated by RGD with different initial points, x0 = ∑ni=1 qiei ∈ Sn-1 , and y0 = q1e1 + √1- q2 1 e2, we have sin2 ∠(xt, e1) ≤ sin2 ∠(yt , e1), ∀t ≥ 0.

Proof of Lemma 1. We first prove the result for a single step. To simplify the notation, we denote x′ = R(x, ηg(x)) as the one-step update of x ∈ Sn-1 , here x = ∑ni=1 qiei is the spectrum decomposition of x. We let y = q1e1 + √1 - q2 1 e2, which is a counterpart of x with all the non-principal components concentrated on the second dimension. And we denote y′ = R(y, ηg(y)) to be the one-step update of y accordingly. Consider one-step update as x′ = R(x, ηg(x)) = ∑ni=1 q′i ei. Then component-wise, we have

It is conceptually easier to proceed the proof by thinking of (q2 1 , q2 2 , ...q2n ) as a discrete probability distribution. Thus, we denote pi = q2 i , ∀i ∈ [n] and we have p = (p1, ..., pn) ∈ Γn-1 , where Γn-1 ≜ {p ≥ 0 | ∑ni=1 pi = 1} is the (n - 1)- dimensional probability simplex. Our analysis and notations will benefit from this point of view of probability distribution. We further denote η(λ1 - λi) ≜ χi, thus χ1 = 0, χ2 = η(λ1 - λ2), and χ2 ≤ χi ≤ ηλ1, ∀i ≥ 2.

Now we consider the following function g(p), which characterizes the increment of the principal component p1 by p′1 = g(p) · p1,

We create a random variable χ that follows the distribution P (χ = χi) = pi. Then we know E(χ) = ∑ni=1 χipi and

Here we used the equation E(1-χ+E(χ))2 = 1+E(χ2 )- E(χ)2 = 1 +Var(χ). Then it suffices to study the extremal property of this function, which gives a lower bound on the increment of the principal component and thus a lower bound for the convergence rate.

Note that ∑ni=1 pi = 1, then we can substitute it into g(p) to eliminate pn. We then consider the following restricted functions over ¯Γn-1 = {¯p ≥ 0, | ∑n-1 i=1 ¯ pi ≤ 1}. Note that

¯Γn-1 is not a probability simplex, but the projection of Γn-1 onto the first n - 1 dimensions.

Also note that Var(χ) = E(χ2 ) - E(χ)2 . Then we claim that for stepsize η ≤ 1 λ1 , we always have ∂ ∂p2 ¯ g(¯p) ≤ 0. To see this, we take the derivative of ¯ g(¯p) w.r.t. p2 and obtain

Taking the derivative of E(χ) and Var(χ) w.r.t. p2 gives us ∂ ∂p2 E(χ) = χ2 - χn and ∂ ∂p2 Var(χ) = (χ22 - χ2n ) - 2(χ2 - χn)E(χ). Substituting these derivatives into that of ¯ g(¯p) gives

Since - (1+E(χ))(χn-χ2) (1+Var(χ))2 ≤ 0, we have ∂ ∂p2 ¯ g(¯p) ≤ 0 when 2E(χ2 ) + (1 + E(χ))(2 - χ2 - χn) ≥ 0. But since η ≤ 1 λ1 , we have χi ≤ 1, ∀i ∈ [n] and thus 2 - χ2 - χn ≥ 0. Thus our claim is correct, and hence the minima should satisfy the boundary condition of ¯Γn-1 as p2 = 1 - p1 - ∑n-1 i=3 pi, or equivalently, pn = 0.

In other words, we have proved that when η ≤ 1 λ1 , the increment of principal component satisfies g(p) ≥ g(p1, (p2 + pn), p3, ..., pn-1, 0). Using similar arguments over pn-1, ..., p3, we can show that g(p) ≥ g(p1, ∑ni=2 pi, 0, ..., 0) = g(p1, 1 - p1, 0, ..., 0). This means that the increment of the principal component attains minima when all the weights p2, p3, ..., pn are concentrated on the second leading component. Thus when η ≤ 1 λ1 , we have

This together with the fact that sin2 ∠(x′ , e1) = 1-g(p)p1 gives

Note that the right hand side is in fact equivalent to sin2 ∠(y′ , e1), then we get sin2 ∠(x′ , e1) ≤ sin2 ∠(y′ , e1). This proves the lemma for a single step. Now we critically use a chaining argument to show that this is also true for multiple steps.

With some abuse on notations, suppose we have an array {p(t) = (p1(t), ..., pn(t))} produced by the RGD algorithm above. Then we have

We further construct another virtual sequence {r(t) = (r1(t), ..., rn(t))}, which is also generated by the gradient process but with a different starting point r1(0) = p1(0), r2(0) = 1-p1(0), ri(0) = 0, ∀3 ≤ i ≤ n. Then r(t), ∀t ≥ 0 will only have nonzero values for its first two components. And we have the recurrence for r(t) as

To establish our reduction for multiple steps, it suffices to prove that p1(t) ≥ r1(t), ∀t ≥ 0. Note that we have validated this inequality for t = 0 by Lemma 1, since p1(1) = g(p(0)) · p1(0) ≥ g(p1(0), 1 - p1(0), 0, ..., 0) · p1(0) = r1(1).

In the following, we will prove that p1(t) ≥ r1(t), ∀t ≥ 0 by induction. The induction base is that ∀t ≤ k, we have p1(t) ≥ r1(t). In fact, if the function h(p) = p · g(p, 1 - p, 0, ..., 0), ∀p ∈ [0, 1] is monotonically increasing, then by induction base we have

and this concludes our proof. The fact that h(p) is a monotonic function can be validated via its derivative:

Note that for χ2, p ∈ [0, 1], we have d dp h(p) ≥ 0. Thus, h(p) is indeed monotone, which establishes our previous statements. In other words, if x0 = ∑ni=1 qiei, and y0 = q1e1 + √1 - q2 1 e2, then after t iterations, we will have sin2 ∠(xt, e1) = 1-p1(t) ≤ 1-r1(t) = sin2 ∠(yt , e1). This proves the lemma.

Since the worst-case convergence rate occurs when the initial vector lies in the span of the first and second principal dimensions due to Lemma 1, it suffices to lower bound the rate for the two-dimensional case. By putting all these arguments together, it is straight-forward to establish Theorem 1 as follows.

Proof of Theorem 1. By Lemma 1, we have sin2 ∠(xt, e1) ≤ sin2 ∠(yt , e1), ∀t ≥ 0. Since the series of yt only remains in the two-dimensional space of span{e1, e2}, in essence its convergence follows the case where d = 2.

Here we consider the convergence property of the basic 2-dimensional case. Denote θt ≜ ∠(xt, e1), then we have q1(t) = | cos θt|, q2(t) = | sin θt|. And we have

Since we have tan2 θt 1+tan2 θt ∈ [0, 1), then 1 + χ2 tan2 θt 1+tan2 θt < 1+χ2. Thus

By simple chaining, we have tan2 θt ≤ tan2 θ0 (1+χ2)2t → 0. Note that sgn(tan(θt)) = sgn(tan(θ0)). Thus, we conclude that either θt → 0 or θt → π, which corresponds to the cases where xt converges to e1 and -e1. Without loss of generality, we consider the case where θt → 0, then we can bound sin2 θt as

Thus when η ≤ 1 λ1 , with high probability over random initialization over the hypersphere, we have tan2 θ0 = Θ(n), and hence

Taking η = 1 λ1 , we have χ2 = ∆ and for t = O( 1∆ ln nϵ ), the required precision is attained.

Remark 1 (Tightness of the analysis). We show that our analysis is essentially tight by considering the concrete instance where {xt} is defined by the RGD process with starting point x0 = 1 √2 (e1 + e2), then we have tanθt ≥ (1 - ∆)t tanθ0 = Ω(ne-2∆t ) with high probability. Thus it requires Ω( 1∆ ln ( nϵ )) iterations to converge in the least.

5 Oja's Rule

The difference between Oja's rule and RGD lies in the retraction step. Since no explicit retraction is enforced during the execution of Oja's rule, the convergence behavior is very different from that of RGD, and the analysis also needs different techniques.

To give our non-asymptotic analysis for L2 convergence, we first review the following lemma previously established in [Yi et al., 2005], using the invariant set technique.

Lemma 2 (Invariant set property [Yi et al., 2005]). If we let η ≤ 1 2λ1 in Oja's rule, then we always have xtAxt ≤ 1 η throughout the process, and tan2 θt decreases as follows.

We will also use the following version of fixed point iteration theorem.

Proposition 1 (Fixed point convergence theorem). Let g and g′ be continuous on [a, b] and suppose that if a ≤ x ≤ b then a ≤ g(x) ≤ b. Also suppose that λ = maxa≤x≤b |g′ (x)| < 1. Then:

1. There exists a unique solution α ∈ [a, b] to the equation x = g(x).
2. For any initial estimation x0 ∈ [a, b], we have |xn-α| ≤ λ|xn-1 - α|, and limn→∞ xn = α.

Our proof for Theorem 2 mainly studies the convergence property of a noisy fixed point iteration.

Proof of Theorem 2. Due to Lemma 2 and tan2 θt = ∑ni=2 q2 i (t) q2 1 (t) , we have

And note that λ1q2 1 (t) ≤ xTt Axt ≤ 1 η , thus q2 1 (t) ≤ 1 ηλ1 . Taking ηλ1 = 14 , then we have

Thus, to achieve tail error ∑ni=2 q2 i (t) ≤ δ, it suffices to assure

And after t1 = O( 1∆ ln tanθ0 δ ) iterations, we always have tail error bounded by δ. Suppose that we have already ran t1 iterations to reduce the tail error to some δ ≤ 14 , then we have ∑ni=2 λiq2 i (t) ≤ λ1 ∑ni=2 q2 i (t) ≤ λ1δ. It is not hard to show that Oja's rule updates q1(t) as follows,

Note that q1(t) preserves the sign throughout the process. Thus, w.l.o.g. we assume q1(t) ≥ 0, ∀t ≥ 0. And thus

Then we study the convergence of the fixed point iterations gζ(x) = 1 4 (5-ζ -x2 )x, where ζ ∈ [0, δ]. Since q2 1 ≤ 1 ηλ1 = 4, it suffices to study this fixed point iteration over (0, 2]. We heve the first-order and second-order derivatives of gζ(x) as g′ζ (x) = 1 4 (5 - ζ - 3x2 ) and g′′ ζ (x) = - 3 2 x.

Thus gζ(x) is concave in (0,+∞). And since the zero of g′ζ (x) on (0,+∞) is sζ = √ 5-ζ 3 , we have gζ(x) increasing with ζ in (0, sζ], and decreasing in (sζ,+∞). To guarantee that gζ(x) is positive in interval (0, 2], it suffices to let gζ(2) = 1 2 (1 - ζ) > 0, and this is equivalent to ζ < 1.

Denote tζ = gζ(sζ) = 5-ζ 6 · sζ, thus for any x ∈ (0, 2], a single update is guaranteed to bring it to (0, tζ] and get trapped within it. But tζ ≤ t0 = 5 6 √ 53 ≃ 1.076 < sζ. Thus, w.l.o.g., we may only consider the interval (0, t0]. And note the fixed point of gζ(x) in (0, t0] is rζ = √1 - ζ.

By Proposition 1, since g′ζ (0) = 14 (5 - ζ) > 1, thus x = 0 cannot be a stable fixed point; and since g′ζ (rζ) = 1 2 (1 + ζ) < 1, rζ is a stable fixed point. Summarizing our analysis above, over the interval (0, t0], the function family

{gζ(x), ∀ζ ∈ [0, δ]} is concave, increasing and positive, and each function have fixed point rζ. For x ∈ (0, rζ], we have gζ(x) ≥ x; and for x ∈ (rζ , t0], we have gζ(x) ≤ x.

After studying the property of gζ (x), we now turn to bound the convergence of a noisy fixed point iteration, where in each iteration t, we are given a different ζ(t) ∈ [0, δ], and update according to xt = gζ(t)(xt-1). Specially, setting ζ(t) = ∑ni=2 λiq2 i (t)/λ1 recovers the original Oja's rule.

By Proposition 1 and detailed case analysis 1 , we claim that if we set δ = ϵ ≤ 14 , then the worst case iteration complexity is O( max{ln 1 x0 , ln 1ϵ }). Putting together the tail error reduction and the noisy fixed point iteration gives us the final convergence rate as

Then with high probability, we have tanθ0 = Θ(√n) and q1 = Θ(1/n) under random initialization over the hypersphere. This proves the theorem.

We summarize the convergence properties for RGD and Oja's rule in Table 1 for reference. We remark that the sublinear rate O( 1ϵ ) when 1 < d < n is not supposed to be tight in general.

6 Experiments

We re-implement experiments from [Xu et al., 2018] for validation of our results. Our setting is exactly the same as [Xu et al., 2018], with n = 1000 and A = UΣU T . Here U is a random orthonormal matrix and Σ = [Σ1 Σ2]. Further, we have Σ2 = [ |g1| n , ..., |gn-6| n ] for gi ∼ N(0, 1); and Σ1 = [1, 1-∆, 1-1.1∆, ..., 1-1.4∆] for certain ∆. We refer readers to [Xu et al., 2018] for detailed parameter settings. Here we let ϵ = e-5 ≃ 0.0067 be the desired precision, and compare the empirical iteration complexity to attain this precision compared with the iteration complexity bound of ours, m1 = 1 2∆ ln nϵ ≃ 5.954 · 1∆ , and that of [Xu et al., 2018], m2 = 1 ∆2 ln nϵ ≃ 11.908 · ( 1∆ )2 .

1 Not presented here due to limited space. Please refer to the full version of this paper.

As shown by the experiment results, the empirical iteration complexity linearly depends on 1∆ , which is well characterized by our iteration complexity bound. However, the quadratic bound of [Xu et al., 2018] is already much higher than the empirical complexity when ∆ ≥ 0.2 (Figure 2); and this gap becomes huge when ∆ ≤ 0.2 (Figure 3).

Moreover, we also validate our convergence results on the Schenk 2 dataset used by [Xu et al., 2018] for fair comparision. Schenk dataset provides a 10,728 × 10,728 PSD sparse matrix with 85,000 non-zeros in it. The eigengap of this matrix is roughly ∆ = 0.39. And our convergence bound in Theorem 1 gives ϵ ≤ O(ne-2∆t ), thus ln(ϵ) ∝ -∆t; while [Xu et al., 2018] gives ln(ϵ) ∝ -∆2 t. As shown in Figure 4, our convergence bound is much closer to empirical rate than theirs. This also justify the tightness of our analysis.

7 Conclusions

In this paper, we proved tight convergence rate of O( 1∆ ln nϵ ) for RGD and Oja's rule, for leading eigenvector computation. Our methods for proving convergence mainly involves a special reduction and chaining technique, together with a noisy fixed point iteration argument. We believe these methods will also be useful when analyzing other algorithms for eigenproblems.

Acknowledgments

We thank the reviewers for their valuable comments. Qinghua Ding would like to thank Prof. Lifeng Sun for giving nice suggestions on this work. This work was partially supported GRF 14208318 from the RGC and ITF 6904945 from the ITC of HKSAR, and the National Natural Science Foundation of China (NSFC) (Grant No. 61672552).

2 https://sparse.tamu.edu/