mlsanityData to 7 Oct 2026

Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates

arXiv 2102.03646 ↗First posted 6 Feb 2021cs.DS cs.LG math.PRcited by 21

Not on the map. Why?

Abstract (arXiv)

We analyze Oja's algorithm for streaming k-PCA and prove that it achieves performance nearly matching that of an optimal offline algorithm. Given access to a sequence of i.i.d. d × d symmetric matrices, we show that Oja's algorithm can obtain an accurate approximation to the subspace of the top k eigenvectors of their expectation using a number of samples that scales polylogarithmically with d. Previously, such a result was only known in the case where the updates have rank one. Our analysis is based on recently developed matrix concentration tools, which allow us to prove strong bounds on the tails of the random matrices which arise in the course of the algorithm's execution.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 16 of its 38 references that are in the map. First posted on arXiv 6 Feb 2021.

Builds on

16 of 38 references.

References · 16

  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  3. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
  4. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  5. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  6. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  7. 2013Memory Limited, Streaming PCAcited by 21
  8. 2015Convergence of Stochastic Gradient Descent for PCAcited by 17
  9. 2015The Fast Convergence of Incremental PCAcited by 15
  10. 2016Near-Optimal Stochastic Approximation for Online Principal Component Estimationcited by 11
  11. 2018Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Lawcited by 11
  12. 2019AdaOja: Adaptive Learning Rates for Streaming PCAcited by 10
4 more
  1. 2015Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexitycited by 9
  2. 2013Online Algorithms for Factorization-Based Structure from Motioncited by 3
  3. 2014Finding the largest low-rank clusters with Ky Fan 2-k-norm and ℓ1-normcited by 2
  4. 2015Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCAcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 3; 2024: 3; 2025: 4; 2026: 6.

21 papers.

Sort:

  1. 2022Preference Dynamics Under Personalized Recommendationscited by 25
  2. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  3. 2021On the Optimality of the Oja's Algorithm for Online PCAcited by 11
  4. 2021Bootstrapping the error of Oja's algorithmcited by 11
  5. 2023Streaming PCA for Markovian Datacited by 9
  6. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  7. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  8. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  9. 2021On the Correspondence between Gaussian Processes and Geometric Harmonicscited by 3
  10. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  11. 2024Spectral Guarantees for Adversarial Streaming PCAcited by 2
  12. 2025Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCAcited by 2
9 more
  1. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 1
  2. 2026Graph Regularized PCAcited by 1
  3. 2026Pro-KLShampoo: Projected KL-Shampoo with Whitening Recovered by Orthogonalizationcited by 1
  4. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  5. 2025Spike-timing-dependent Hebbian learning as noisy gradient descentcited by 0
  6. 2025Global Convergence of Adaptive Sensing for Principal Eigenvector Estimationcited by 0
  7. 2026Factor Augmented High-Dimensional SGDcited by 0
  8. 2026Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computationcited by 0
  9. 2026AIM-ZO: Activation-Informed Subspace Maintenance for Zeroth-Order LLM Fine-Tuningcited by 0