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

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.

Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Keqin Chen, Jie Bian, Yulian Wu +1
arXiv3 Oct 2026PreprintCC BY 4.0Full textGeneral mathematicsarXiv
Optimal Conversion from Zero-Concentrated to Gaussian Differential Privacy
Yu-Wei Chen, Aaradhya Pandey, Jordan Awan
arXiv1 Nov 2026PreprintCC BY 4.0Full textStatisticsarXiv
Prophet Inequalities under Local Differential Privacy
Achraf Azize, Mathieu Molina, Hugo Richard +1
HAL19 Jun 2026PreprintLicence not statedGeneral mathematicsHAL
Quality Certification and Coopetition in Live-Streaming E-Commerce: A Differential Game with Consumer Reference Effects
Yongpeng Liu, Fangfang Wei, Andi Xu +1
Mathematics11 Oct 2026Peer-reviewedCC BY 4.0General mathematicsCrossref
Performative Privacy: When Differential Privacy Maximizes Utility
Uddalak Mukherjee, Edwige Cyffers, Yann Chevaleyre
arXiv28 Sep 2026PreprintCC BY-NC-SA 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{gu2026gapfree,
  title = {{Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy}},
  author = {Anming Gu and Syamantak Kumar and Kevin Tian and Chutong Yang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26508},
  eprint = {2609.26508},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26508},
}

RIS

TY  - UNPB
TI  - Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
AU  - Anming Gu
AU  - Syamantak Kumar
AU  - Kevin Tian
AU  - Chutong Yang
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26508
UR  - https://arxiv.org/abs/2609.26508
AB  - 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.
ER  -

Abstract

Related

Cite