New arXiv paper unlocks uncertainty quantification for streaming PCA with Oja's algorithm

Streaming principal component analysis (PCA) is a workhorse for modern machine learning, letting you estimate dominant subspaces from data that arrives one point at a time without storing everything in memory. But until now, two fundamental questions remained open: how fast does Oja's algorithm converge in operator norm for general rank, and can you actually quantify the uncertainty of the resulting subspace estimate? In a new arXiv paper, Haoshu Xu and Hongzhe Li tackle both head-on.

The authors close the convergence gap by eliminating the non-vanishing remainder terms that plagued earlier analyses. This yields a sharp rate that, in the dense-tail spiked covariance regime, matches the minimax lower bound up to logarithmic factors. They also prove a matching lower bound across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. Building on this, they linearize Oja's iterates to establish a high-dimensional Gaussian approximation for the general-rank subspace estimation error, with an explicit limiting covariance. For practitioners, they introduce an online multiplier bootstrap algorithm and prove its consistency, meaning you can now build confidence intervals for subspaces in genuinely streaming settings. The techniques extend beyond PCA, offering tools for Gaussian approximation and bootstrap inference in nonconvex stochastic approximation, making this a significant theoretical step with direct practical payoff.