First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate

Abstract

We study streaming principal component analysis (PCA), that is to find, in $O(dk)$ space, the top $k$ eigenvectors of a $d\times d$ hidden matrix $\mathbf{\Sigma }$ with online vectors drawn from covariance matrix $\mathbf{\Sigma }$. We provide $\text{global}$ convergence for Oja's algorithm which is popularly used in practice but lacks theoretical understanding for $k>1$. We also provide a modified variant ${\mathsf{Oja}}^{++}$ that runs $\text{even faster}$ than Oja's. Our results match the information theoretic lower bound in terms of dependency on error, on eigengap, on rank $k$, and on dimension $d$, up to poly-log factors. In addition, our convergence rate can be made gap-free, that is proportional to the approximation error and independent of the eigengap. In contrast, for general rank $k$, before our work (1) it was open to design any algorithm with efficient global convergence rate; and (2) it was open to design any algorithm with (even local) gap-free convergence rate in $O(dk)$ space.

REMARK: v4 adds discussions and polishes writing; v3 contains a stronger Theorem 2, a new lower bound Theorem 6, as well as new Oja++ results Theorem 4 and Theorem 5

References in corpus (4)

• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Fast and Simple PCA via Convex Optimization
• LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain
• Doubly Accelerated Methods for Faster CCA and Generalized Eigendecomposition

Cited by in corpus (7)

• Accelerated Stochastic Power Iteration
• AdaOja: Adaptive Learning Rates for Streaming PCA
• History PCA: A New Algorithm for Streaming PCA
• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
• Semi-groups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations
• Online Factorization and Partition of Complex Networks From Random Walks