Practical and Fast Momentum-Based Power Methods

Tahseen Rabbani, Apollo Jain, Arjun Rajkumar, Furong Huang
Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:721-756, 2022.

Abstract

The power method is a classical algorithm with broad applications in machine learning tasks, in- cluding streaming PCA, spectral clustering, and low-rank matrix approximation. The distilled pur- pose of the vanilla power method is to determine the largest eigenvalue (in absolute modulus) and its eigenvector of a matrix. A momentum-based scheme can be used to accelerate the power method, but achieving an optimal convergence rate with existing algorithms critically relies on additional spectral information that is unavailable at run-time, and sub-optimal initializations can result in di- vergence. In this paper, we provide a pair of novel momentum-based power methods, which we call the delayed momentum power method (DMPower) and a streaming variant, the delayed momentum streaming method (DMStream). Our methods leverage inexact deflation and are capable of achiev- ing near-optimal convergence with far less restrictive hyperparameter requirements. We provide convergence analyses for both algorithms through the lens of perturbation theory. Further, we ex- perimentally demonstrate that DMPower routinely outperforms the vanilla power method and that both algorithms match the convergence speed of an oracle running existing accelerated methods with perfect spectral knowledge.

Cite this Paper

BibTeX
@InProceedings{pmlr-v145-rabbani22a, title = {Practical and Fast Momentum-Based Power Methods}, author = {Rabbani, Tahseen and Jain, Apollo and Rajkumar, Arjun and Huang, Furong}, booktitle = {Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference}, pages = {721--756}, year = {2022}, editor = {Bruna, Joan and Hesthaven, Jan and Zdeborova, Lenka}, volume = {145}, series = {Proceedings of Machine Learning Research}, month = {16--19 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v145/rabbani22a/rabbani22a.pdf}, url = {https://proceedings.mlr.press/v145/rabbani22a.html}, abstract = {The power method is a classical algorithm with broad applications in machine learning tasks, in- cluding streaming PCA, spectral clustering, and low-rank matrix approximation. The distilled pur- pose of the vanilla power method is to determine the largest eigenvalue (in absolute modulus) and its eigenvector of a matrix. A momentum-based scheme can be used to accelerate the power method, but achieving an optimal convergence rate with existing algorithms critically relies on additional spectral information that is unavailable at run-time, and sub-optimal initializations can result in di- vergence. In this paper, we provide a pair of novel momentum-based power methods, which we call the delayed momentum power method (DMPower) and a streaming variant, the delayed momentum streaming method (DMStream). Our methods leverage inexact deflation and are capable of achiev- ing near-optimal convergence with far less restrictive hyperparameter requirements. We provide convergence analyses for both algorithms through the lens of perturbation theory. Further, we ex- perimentally demonstrate that DMPower routinely outperforms the vanilla power method and that both algorithms match the convergence speed of an oracle running existing accelerated methods with perfect spectral knowledge. } }
Endnote
%0 Conference Paper %T Practical and Fast Momentum-Based Power Methods %A Tahseen Rabbani %A Apollo Jain %A Arjun Rajkumar %A Furong Huang %B Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2022 %E Joan Bruna %E Jan Hesthaven %E Lenka Zdeborova %F pmlr-v145-rabbani22a %I PMLR %P 721--756 %U https://proceedings.mlr.press/v145/rabbani22a.html %V 145 %X The power method is a classical algorithm with broad applications in machine learning tasks, in- cluding streaming PCA, spectral clustering, and low-rank matrix approximation. The distilled pur- pose of the vanilla power method is to determine the largest eigenvalue (in absolute modulus) and its eigenvector of a matrix. A momentum-based scheme can be used to accelerate the power method, but achieving an optimal convergence rate with existing algorithms critically relies on additional spectral information that is unavailable at run-time, and sub-optimal initializations can result in di- vergence. In this paper, we provide a pair of novel momentum-based power methods, which we call the delayed momentum power method (DMPower) and a streaming variant, the delayed momentum streaming method (DMStream). Our methods leverage inexact deflation and are capable of achiev- ing near-optimal convergence with far less restrictive hyperparameter requirements. We provide convergence analyses for both algorithms through the lens of perturbation theory. Further, we ex- perimentally demonstrate that DMPower routinely outperforms the vanilla power method and that both algorithms match the convergence speed of an oracle running existing accelerated methods with perfect spectral knowledge.
APA
Rabbani, T., Jain, A., Rajkumar, A. & Huang, F.. (2022). Practical and Fast Momentum-Based Power Methods. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 145:721-756 Available from https://proceedings.mlr.press/v145/rabbani22a.html.

Related Material