A Comprehensively Tight Analysis of Gradient Descent for PCA

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(1/∆ log 1/ϵ) that holds for any real symmetric matrix. More importantly, when the gap ∆ is significantly smaller than the target accuracy ϵ 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(1/ϵ log 1/ϵ). The two analyses naturally roll out a comprehensively tight convergence rate at O(1/max{∆,ϵ}log 1/ϵ). 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.