# Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 39 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 15 of 15)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings](https://mlsanity.com/paper/2210.04620/) (2022)
- [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Accelerated Stochastic Power Iteration](https://mlsanity.com/paper/1707.02670/) (2017)
- [DeEPCA: Decentralized Exact PCA with Linear Convergence Rate](https://mlsanity.com/paper/2102.03990/) (2021)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [Cloud K-SVD: A Collaborative Dictionary Learning Algorithm for Big, Distributed Data](https://mlsanity.com/paper/1412.7839/) (2014)
- [Accelerated Gossip in Networks of Given Dimension using Jacobi Polynomial Iterations](https://mlsanity.com/paper/1805.08531/) (2018)
- [Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems](https://mlsanity.com/paper/1612.01216/) (2016)
- [FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis](https://mlsanity.com/paper/2108.12373/) (2021)
- [Noisy Accelerated Power Method for Eigenproblems with Applications](https://mlsanity.com/paper/1903.08742/) (2019)

## Abstract (arXiv)

We analyze the Accelerated Noisy Power Method, an algorithm for Principal Component Analysis in the setting where only inexact matrix-vector products are available, which can arise for instance in decentralized PCA. While previous works have established that acceleration can improve convergence rates compared to the standard Noisy Power Method, these guarantees require overly restrictive upper bounds on the magnitude of the perturbations, limiting their practical applicability. We provide an improved analysis of this algorithm, which preserves the accelerated convergence rate under much milder conditions on the perturbations. We show that our new analysis is worst-case optimal, in the sense that the convergence rate cannot be improved, and that the noise conditions we derive cannot be relaxed without sacrificing convergence guarantees. We demonstrate the practical relevance of our results by deriving an accelerated algorithm for decentralized PCA, which has similar communication costs to non-accelerated methods. To our knowledge, this is the first decentralized algorithm for PCA with provably accelerated convergence.