# Convergence of Stochastic Gradient Descent for PCA

arXiv: https://arxiv.org/abs/1509.09002 · HTML: https://mlsanity.com/paper/1509.09002/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2015.

## Built on by (most cited first, 17 of 17)

- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates](https://mlsanity.com/paper/2102.03646/) (2021)
- [On the Optimality of the Oja's Algorithm for Online PCA](https://mlsanity.com/paper/2104.00512/) (2021)
- [Bootstrapping the error of Oja's algorithm](https://mlsanity.com/paper/2106.14857/) (2021)
- [Black-Box k-to-1-PCA Reductions: Theory and Applications](https://mlsanity.com/paper/2403.03905/) (2024)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems](https://mlsanity.com/paper/2112.14738/) (2021)
- [The Effect of SGD Batch Size on Autoencoder Learning: Sparsity, Sharpness, and Feature Learning](https://mlsanity.com/paper/2308.03215/) (2023)
- [Universal Adversarial Directions](https://mlsanity.com/paper/2210.15997/) (2022)
- [Optimization Can Learn Johnson Lindenstrauss Embeddings](https://mlsanity.com/paper/2412.07242/) (2024)
- [Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy](https://mlsanity.com/paper/2609.26508/) (2026)
- [ADS: Approximate Densest Subgraph for Novel Image Discovery](https://mlsanity.com/paper/2402.08743/) (2024)
- [Global Convergence of Adaptive Sensing for Principal Eigenvector Estimation](https://mlsanity.com/paper/2505.10882/) (2025)
- [Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA](https://mlsanity.com/paper/2602.03682/) (2026)
- [Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition](https://mlsanity.com/paper/2602.13759/) (2026)
- [Gap-free Differentially Private PCA for Gaussian Data](https://mlsanity.com/paper/2609.31614/) (2026)

## Abstract (arXiv)

We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a stream of i.i.d. data points in realsd. A simple and computationally cheap algorithm for this is stochastic gradient descent (SGD), which incrementally updates its estimate based on each new data point. However, due to the non-convex nature of the problem, analyzing its performance has been a challenge. In particular, existing guarantees rely on a non-trivial eigengap assumption on the covariance matrix, which is intuitively unnecessary. In this paper, we provide (to the best of our knowledge) the first eigengap-free convergence guarantees for SGD in the context of PCA. This also partially resolves an open problem posed in citehardt2014noisy. Moreover, under an eigengap assumption, we show that the same techniques lead to new SGD convergence guarantees with better dependence on the eigengap.