← Back to all news
arXiv Machine Learning

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

The paper presents a new analysis of Oja's algorithm for streaming principal component analysis (PCA) that works without any eigengap assumptions, achieving near‑optimal rates and matching lower bounds. It extends the results to a Rayleigh quotient notion of approximate PCA, resolving an open question, and applies the findings to provide gap‑free differentially private PCA guarantees for sub‑Gaussian data. The analysis relies solely on a second‑moment bound of stochastic updates, avoiding the almost‑sure bounds used in previous work.

Related stories

arXiv Machine Learning
Aug 20

Inference and Uncertainty Quantification for Streaming $r$-PCA

The paper tackles two key gaps in streaming PCA using Oja's algorithm: it establishes sharp operator‑norm convergence for general‑rank subspaces under sub‑Gaussian data, and it provides distributional inference for the resulting subspace estimator. The authors remove non‑vanishing remainder terms from existing analyses, achieving rates that match minimax bounds in both dense‑tail and sparse‑tail regimes. They further develop a linearization of Oja’s iterates, enabling high‑dimensional Gaussian approximations and an online multiplier bootstrap for practical inference.

By Haoshu Xu, Hongzhe Li
More like this →
arXiv Machine Learning
2d ago

Gap-free Differentially Private PCA for Gaussian Data

The paper presents a gap‑free differentially private algorithm for performing principal component analysis on Gaussian data. It addresses the PCA problem while ensuring privacy guarantees without relying on a spectral gap assumption. The work is announced on arXiv with the identifier 2609.31614v1.

By Alina Ene, Huy L. Nguyen
More like this →
arXiv Machine Learning
Sep 3

Robust Streaming PCA

The paper studies streaming principal component analysis under a robust setting where the covariance matrix can vary within a temporal uncertainty set, rather than being fixed. It establishes fundamental convergence limits for any algorithm that recovers principal components and analyzes the noisy power method and Oja's algorithm, showing that the noisy power method achieves rate‑optimal convergence in this setting. Numerical experiments on synthetic and real‑world data confirm the theoretical findings.

By Daniel Bienstock, Minchan Jeong, Apurv Shukla, Se-Young Yun
More like this →
arXiv Machine Learning
Sep 23

SuperPCA: subspace analysis and an efficient algorithm for high-dimensional PCA

SuperPCA is a new algorithm for high‑dimensional principal component analysis that exploits an approximate eigenspace of the sample covariance matrix. The authors show that the subspace spanned by several leading eigenvectors contains useful signal information long before individual eigenvectors converge, and they derive posteriori bounds on the angle between this subspace and the true signal subspace. By using only a small number of subsampled coordinates, SuperPCA can achieve up to a ten‑fold improvement in accuracy over classical PCA while reducing data acquisition costs, especially when the signals are approximately sparse.

By Irina-Beatrice Haas, Maike Meier, Yuji Nakatsukasa, Taejun Park
More like this →