Reproduce “Robust Streaming PCA” on OpenResearch

About this paper

Daniel Bienstock, Minchan Jeong, Apurv Shukla, Se-Young Yun

Robust Streaming PCA characterizes how quickly principal-subspace estimation can track a covariance matrix that drifts over time. It establishes a minimax error floor scaling with the cube root of the drift rate, shows that a blockwise noisy power method attains this rate up to logarithmic factors in a broad regime, and finds that Oja’s algorithm follows the same drift-dependent tuning law but has a weaker proven dimension dependence.

Key insights

• More observations cannot reduce error indefinitely under drift: after an initial T^{-1/2} improvement, the risk plateaus at a drift-limited level proportional to Γ^{1/3}, with an effective useful horizon scaling as Γ^{-2/3}.
• The optimal noisy-power block size and Oja virtual-block length both scale as Γ^{-2/3}; longer blocks reduce sampling noise but increasingly average over obsolete covariance information.
• The noisy power method is minimax-rate optimal up to logarithmic factors when the noise dimension dominates and the signal condition number is controlled, while Oja’s analysis incurs an additional approximately p^{1/3} factor.

Summary by alphaXiv.