mlsanityData to 7 Oct 2026

On the Optimality of the Oja's Algorithm for Online PCA

arXiv 2104.00512 ↗First posted 31 Mar 2021cs.LG math.OCcited by 11

Not on the map. Why?

Abstract (arXiv)

In this paper we analyze the behavior of the Oja's algorithm for online/streaming principal component subspace estimation. It is proved that with high probability it performs an efficient, gap-free, global convergence rate to approximate an principal component subspace for any sub-Gaussian distribution. Moreover, it is the first time to show that the convergence rate, namely the upper bound of the approximation, exactly matches the lower bound of an approximation obtained by the offline/classical PCA up to a constant factor.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 14 of its 33 references that are in the map. First posted on arXiv 31 Mar 2021.

Builds on

14 of 33 references.

References · 14

  1. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  2. 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
  3. 2016Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithmcited by 29
  4. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  5. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  6. 2021Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updatescited by 21
  7. 2016Faster Eigenvector Computation via Shift-and-Invert Preconditioningcited by 18
  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. 2019AdaOja: Adaptive Learning Rates for Streaming PCAcited by 10
  12. 2015Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexitycited by 9
2 more
  1. 2019An Implicit Form of Krasulina's k-PCA Update without the Orthonormality Constraintcited by 4
  2. 2017Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

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

11 papers.

  1. 2021Bootstrapping the error of Oja's algorithmcited by 11
  2. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  3. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  4. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  5. 2025Low-Precision Streaming PCAcited by 3
  6. 2025Manifold learning and optimization using tangent space proxiescited by 2
  7. 2026Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacycited by 1
  8. 2025Global Convergence of Adaptive Sensing for Principal Eigenvector Estimationcited by 0
  9. 2026Focus on What Matters: Fisher-Guided Adaptive Multimodal Fusion for Vulnerability Detectioncited by 0
  10. 2026Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecompositioncited by 0
  11. 2026PCA-VAE: Differentiable Subspace Quantization without Codebook Collapsecited by 0