mlsanityData to 7 Oct 2026

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

arXiv 2609.26508 ↗First posted 22 Sep 2026cs.LG cs.DS stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 26 of its 36 references that are in the map. First posted on arXiv 22 Sep 2026.

Builds on

26 of 36 references.

References · 26

  1. 2017Renyi Differential Privacycited by 643
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  3. 2021Differential privacy and robust statistics in high dimensionscited by 64
  4. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  5. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  6. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
  7. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  8. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  9. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  10. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  11. 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
  12. 2013Memory Limited, Streaming PCAcited by 21
14 more
  1. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  2. 2016Faster Eigenvector Computation via Shift-and-Invert Preconditioningcited by 18
  3. 2015Convergence of Stochastic Gradient Descent for PCAcited by 17
  4. 2015Fast and Simple PCA via Convex Optimizationcited by 16
  5. 2015The Fast Convergence of Incremental PCAcited by 15
  6. 2016Near-Optimal Stochastic Approximation for Online Principal Component Estimationcited by 11
  7. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  8. 2024Optimal Differentially Private PCA and Estimation for Spiked Covariance Matricescited by 10
  9. 2023Streaming PCA for Markovian Datacited by 9
  10. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  11. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  12. 2025Low-Precision Streaming PCAcited by 3
  13. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 2
  14. 2025Robust and Differentially Private Principal Component Analysiscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Gap-free Differentially Private PCA for Gaussian Datacited by 0