Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
This work addresses the problem of improving computational efficiency for SVD and PCA in machine learning, but it is incremental as it builds on existing algorithms.
The paper analyzes the convergence properties of the VR-PCA algorithm for fast computation of leading singular vectors, proving new results including formal analysis of a block version and convergence from random initialization.
We study the convergence properties of the VR-PCA algorithm introduced by \cite{shamir2015stochastic} for fast computation of leading singular vectors. We prove several new results, including a formal analysis of a block version of the algorithm, and convergence from random initialization. We also make a few observations of independent interest, such as how pre-initializing with just a single exact power iteration can significantly improve the runtime of stochastic methods, and what are the convexity and non-convexity properties of the underlying optimization problem.