Convergence of Stochastic Gradient Descent for PCA
Ohad Shamir Weizmann Institute of Science
Abstract
We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a stream of i.i.d. data points in $\mathbb{R}^{d}$ . A simple and computationally cheap algorithm for this is stochastic gradient descent (SGD), which incrementally updates its estimate based on each new data point. However, due to the non-convex nature of the problem, analyzing its performance has been a challenge. In particular, existing guarantees rely on a non-trivial eigengap assumption on the covariance matrix, which is intuitively unnecessary. In this paper, we provide (to the best of our knowledge) the first eigengap-free convergence guarantees for SGD in the context of PCA. This also partially resolves an open problem posed in [10]. Moreover, under an eigengap assumption, we show that the same techniques lead to new SGD convergence guarantees with better dependence on the eigengap.
中文速览
流式数据场景下的主成分分析（PCA）需要在不存储全量数据的情况下，用随机梯度下降（SGD，即 Oja 算法）找到数据方差最大的方向，但由于目标函数非凸，理论分析一直依赖一个"特征间隔（eigengap）"假设——要求协方差矩阵最大特征值与第二大特征值之间存在明显差距，而这在实际中未必成立。本文首次给出了不需要特征间隔假设的 SGD 收敛保证：在适当步长下，经过 T 步迭代后 SGD 能以正概率返回误差约为 $\sqrt{d/T}$ 量级的近似最优解；进一步通过一次近似幂迭代做初始化，可将对维度 d 的依赖替换为更小的数值秩（numerical rank），大幅改善结果。当特征间隔存在时，同样的技术还给出了对特征间隔依赖为 $1/\lambda$ 的新保证，优于此前所有已知结果的 $1/\lambda^2$，从而填补了流式 PCA 理论分析中的一个重要空白。
原文 arXiv:1509.09002;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1509.09002v2