Streaming PCA achieves optimal rates without eigengap assumptions
Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
Machine LearningData Structures and Algorithms
Summary
Streaming PCA is about finding important patterns in data by looking at it only once. The authors studied a popular method called Oja's algorithm and showed it works well even without assuming a clear separation between important and less important patterns. Their proof uses new mathematical techniques that simplify earlier approaches. They also extended their results to a new way of measuring accuracy and applied their findings to improve privacy when analyzing sensitive data.
What this means in practice
- •For data privacy engineers: Provide strong privacy guarantees when performing PCA on data streams without requiring assumptions about data structure.
- •For machine learning engineers: Use improved streaming PCA methods to extract principal components from high-dimensional data efficiently in a single pass without eigengap restrictions.
Authors
Anming Gu, Syamantak Kumar, Kevin Tian, Chutong Yang
Abstract
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 [Oja82] 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 [JJK+16, HNWW21], or were limited to rank-one updates [AZL17, Lia23]. 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 [JJK+16]. As our main application, we give gap-free differentially private PCA guarantees for sub-Gaussian data, settling Conjecture 1.1 of [Bro26] up to logarithmic factors.