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

Pierre Aguié, Mathieu Even, Laurent Massoulié
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:1123-1168, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-aguie26a, title = {Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized {PCA}}, author = {Agui\'{e}, Pierre and Even, Mathieu and Massouli\'{e}, Laurent}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {1123--1168}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/aguie26a/aguie26a.pdf}, url = {https://proceedings.mlr.press/v306/aguie26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA %A Pierre Aguié %A Mathieu Even %A Laurent Massoulié %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-aguie26a %I PMLR %P 1123--1168 %U https://proceedings.mlr.press/v306/aguie26a.html %V 306 %X 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.
APA
Aguié, P., Even, M. & Massoulié, L.. (2026). Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:1123-1168 Available from https://proceedings.mlr.press/v306/aguie26a.html.

Related Material