Journal
2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS)
Volume -, Issue -, Pages 487-492Publisher
IEEE
DOI: 10.1109/FOCS.2017.51
Keywords
principal component analysis; streaming algorithm; online algorithm; global convergence; stochastic optimization; convergence; optimal algorithm; nonconvex optimization
Funding
- Microsoft [0518584]
- NSF [CCF-1412958]
Ask authors/readers for more resources
We study streaming principal component analysis (PCA), that is to find, in Omicron(dk) space, the top k eigenvectors of a d x d hidden matrix Sigma with online vectors drawn from covariance matrix Sigma. We provide 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 Oja(++) that runs 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 Omicron(dk) space.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available