Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
Ohad Shamir Weizmann Institute of Science
Abstract
We study the convergence properties of the VR-PCA algorithm introduced by [19] 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.
中文速览
大规模矩阵主成分分析（PCA）面临两难困境：确定性算法精度高但每轮需要完整扫描数据，随机算法每步计算量小但精度难以提升。Shamir 等人此前提出的 VR-PCA 算法借助方差缩减（variance reduction）技术，兼具随机算法的廉价迭代和指数收敛速度，但仍存在三个未解问题：只分析了求单个奇异向量的情况、收敛保证依赖非随机的热启动初始化、以及特征值间隔（eigengap）的依赖阶数是否最优。本文对这三个问题逐一给出了答案：提出并严格分析了同时求 k 个奇异向量的分块版本算法；证明了只需在随机初始化后额外做一次完整的幂迭代（power iteration），就能大幅改善收敛起点，从而实现端到端的收敛保证；还揭示了目标函数在最优解附近的局部强凸性，解释了为何更好的特征值间隔依赖在理论上是可能的，但在多数实际场景中受到距离条件的限制。这些结果填补了 VR-PCA 理论体系的关键空白，也为其他随机 PCA 算法的热启动设计提供了新思路。
原文 arXiv:1507.08788;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1507.08788v1