Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja’s algorithm (Oja, 1982) for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underlying mean matrix, complemented by a nearly matching lower bound. Prior works achieving near-optimal rates for streaming PCA either required gap assumptions (Jain et al., 2016; Huang et al., 2021) or were limited to rank-one updates (Allen-Zhu and Li, 2017; Liang, 2023). Our proof only uses a second-moment bound on the individual stochastic updates, bypassing the almost-sure bounds needed by prior near-optimal analyses and the analogous offline matrix Bernstein bound. We also extend our result to a Rayleigh quotient notion of approximate PCA, addressing an open question of Jain et al. (2016). As our main application, we give gap-free differentially private PCA guarantees for sub-Gaussian data, settling Conjecture 1.1 of Brown (2026) up to logarithmic factors.