Gap-free Differentially Private PCA for Gaussian Data

Alina Ene; Huy L. Nguyen

cs.DSSep 25, 2026

Gap-free Differentially Private PCA for Gaussian Data

Authors: Alina Ene, Huy L. Nguyen

Organizations: Department of Computer Science, Boston University · Khoury College of Computer and Information Science, Northeastern University

Abstract

We give a gap-free $(ε,δ)$ -differentially private algorithm for the principal component analysis (PCA) problem with Gaussian data. The algorithm is based on a private variant of the power iteration method, and it is computationally efficient.

Explore similar work

Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
Sep 22, 2026Anming Gu, Syamantak Kumar, Kevin Tian +1Principal Component Analysis Differential Privacy
University of Texas at Austin
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
Jun 20, 2026Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar +1Principal Component Analysis Minimax Estimation
University of Texas at Austin
Private Adaptive Covariance Estimation via Gaussian Graphical Models
May 22, 2026Cecilia Ferrando, Miguel Fuentes, Brett Mullins +2Differential Privacy Covariance Estimation
Manning College of Information and Computer Sciences University of Massachusetts Amherst

Sep 22, 2026, cs.LGJ/K move · Enter open · S save

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

Anming Gu, Syamantak Kumar, Kevin Tian, Chutong Yang

University of Texas at Austin

Principal Component Analysis Differential Privacy Streaming Algorithms

Open paper AskPDF 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.

Abstract

Explore similar work

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

On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA

Private Adaptive Covariance Estimation via Gaussian Graphical Models