# Accelerated Stochastic Power Iteration

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2017.

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

- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Improving Generalization in Federated Learning by Seeking Flat Minima](https://mlsanity.com/paper/2203.11834/) (2022)
- [Learning by Reconstruction Produces Uninformative Features For Perception](https://mlsanity.com/paper/2402.11337/) (2024)
- [Beyond Local Sharpness: Communication-Efficient Global Sharpness-aware Minimization for Federated Learning](https://mlsanity.com/paper/2412.03752/) (2024)
- [CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra](https://mlsanity.com/paper/2309.03060/) (2023)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [One Rank at a Time: Cascading Error Dynamics in Sequential Learning](https://mlsanity.com/paper/2505.22602/) (2025)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Practical and Fast Momentum-Based Power Methods](https://mlsanity.com/paper/2108.09264/) (2021)
- [Multiplication-Avoiding Variant of Power Iteration with Applications](https://mlsanity.com/paper/2110.12065/) (2021)
- [On the Error-Propagation of Inexact Hotelling's Deflation for Principal Component Analysis](https://mlsanity.com/paper/2310.04283/) (2023)
- [Provable Model-Parallel Distributed Principal Component Analysis with Parallel Deflation](https://mlsanity.com/paper/2502.17615/) (2025)
- [Improved analysis of randomized SVD for top-eigenvector approximation](https://mlsanity.com/paper/2202.07992/) (2022)
- [Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points](https://mlsanity.com/paper/2211.00866/) (2022)
- [Towards guarantees for parameter isolation in continual learning](https://mlsanity.com/paper/2310.01165/) (2023)
- [Local vs Global continual learning](https://mlsanity.com/paper/2407.16611/) (2024)
- [Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem](https://mlsanity.com/paper/2501.15131/) (2025)
- [k-SVD with Gradient Descent](https://mlsanity.com/paper/2502.00320/) (2025)
- [Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA](https://mlsanity.com/paper/2602.03682/) (2026)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

Principal component analysis (PCA) is one of the most powerful tools in machine learning. The simplest method for PCA, the power iteration, requires mathcal O(1/Delta) full-data passes to recover the principal component of a matrix with eigen-gap Delta. Lanczos, a significantly more complex method, achieves an accelerated rate of mathcal O(1/√Delta) passes. Modern applications, however, motivate methods that only ingest a subset of available data, known as the stochastic setting. In the online stochastic setting, simple algorithms like Oja's iteration achieve the optimal sample complexity mathcal O(σ2/Delta2). Unfortunately, they are fully sequential, and also require mathcal O(σ2/Delta2) iterations, far from the mathcal O(1/√Delta) rate of Lanczos. We propose a simple variant of the power iteration with an added momentum term, that achieves both the optimal sample and iteration complexity. In the full-pass setting, standard analysis shows that momentum achieves the accelerated rate, mathcal O(1/√Delta). We demonstrate empirically that naively applying momentum to a stochastic method, does not result in acceleration. We perform a novel, tight variance analysis that reveals the "breaking-point variance" beyond which this acceleration does not occur. By combining this insight with modern variance reduction techniques, we construct stochastic PCA algorithms, for the online and offline setting, that achieve an accelerated iteration complexity mathcal O(1/√Delta). Due to the embarassingly parallel nature of our methods, this acceleration translates directly to wall-clock time if deployed in a parallel environment. Our approach is very general, and applies to many non-convex optimization problems that can now be accelerated using the same technique.