Practical and Fast Momentum-Based Power Methods

Tahseen Rabbani, Apollo Jain, Arjun Rajkumar, Furong Huang

Abstract

The power method is a classical algorithm with broad applications in machine learning tasks, including streaming PCA, spectral clustering, and low-rank matrix approximation. The distilled purpose 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 divergence. 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 achieving near-optimal convergence with far less restrictive hyperparameter requirements. We provide convergence analyses for both algorithms through the lens of perturbation theory. Further, we experimentally 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.

Introduction: The Challenge of Momentum

The Power Method is a fundamental tool for finding the dominant eigenvalue ($\lambda_1$) and eigenvector of a matrix, essential for Principal Component Analysis (PCA) and spectral clustering. However, its convergence speed is limited by the "eigengap"—the ratio between the first and second largest eigenvalues. While momentum (the "heavy ball" method) can significantly accelerate convergence, its success depends on precisely tuning the momentum coefficient $\beta$.

Sensitivity of iteration count to the momentum coefficient beta. Sub-optimal choices can lead to slower convergence than the vanilla power method.

As shown in the figure above, choosing an optimal $\beta$ (based on $\lambda_2$) leads to the fewest iterations. However, $\lambda_2$ is typically unknown in practice. Sub-optimal guesses for $\beta$ can actually make the algorithm slower than the vanilla power method or even cause it to diverge.

Methodology: Delayed Momentum and Inexact Deflation

To solve this, the authors propose DMPower and its streaming counterpart DMStream. These algorithms use a two-phase approach:

  1. The Warm-up (Pre-momentum Phase): The algorithm begins with standard power iterations. Simultaneously, it performs inexact Hotelling deflation. By using the current (imperfect) estimate of the first eigenvector to "strip away" the dominant component, the algorithm can estimate the second-largest eigenvalue $\lambda_2$.
  2. The Sprint (Momentum Phase): Once the estimate for $\lambda_2$ stabilizes, the algorithm switches to accelerated momentum-based updates, setting $\beta \approx \lambda_2^2/4$.
Accuracy of the second eigenvalue estimation during the warm-up phase across different error thresholds.

A key theoretical contribution is proving that this "inexact" deflation is sufficient. As illustrated above, the Rayleigh quotient provides a quadratically accurate estimate of eigenvalues relative to eigenvector error, allowing the algorithm to find a suitable $\beta$ even before the first eigenvector has fully converged.

Experimental Results

The researchers evaluated DMPower and DMStream on synthetic PSD matrices, the MNIST dataset for streaming PCA, and toy clustering benchmarks.

  • Oracle-Level Speed: DMPower consistently matched the performance of an "Oracle" version that was given the exact eigenvalues beforehand.
  • Streaming Efficiency: DMStream outperformed Oja’s algorithm, the standard for streaming PCA, across various batch sizes.
  • Wall-Clock Superiority: In many practical scenarios, DMPower was faster in total execution time than the Lanczos algorithm, which, while theoretically fast, can suffer from numerical instability and high re-orthogonalization costs.
  • Spectral Clustering: On non-linear datasets like "concentric circles," DMPower achieved perfect classification with significantly fewer iterations than the vanilla method.

Conclusion and Future Directions

DMPower and DMStream offer a practical, "tuning-free" way to achieve momentum-based acceleration for eigenvalue problems. By delaying acceleration until a spectral sketch is available, they avoid the pitfalls of manual tuning. Future work may address scenarios where the second and third eigenvalues are tightly clustered, making deflation more challenging, or further automate the transition threshold between the warm-up and sprint phases.

Summary updated

Abstract

The power method is a classical algorithm with broad applications in machine learning tasks, including streaming PCA, spectral clustering, and low-rank matrix approximation. The distilled purpose 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 divergence. 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 achieving near-optimal convergence with far less restrictive hyperparameter requirements. We provide convergence analyses for both algorithms through the lens of perturbation theory. Further, we experimentally 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.
BibTeX
@inproceedings{rabbani2021practical,
  author = {Tahseen Rabbani and Apollo Jain and Arjun Rajkumar and Furong Huang},
  title = {{Practical and Fast Momentum-Based Power Methods}},
  booktitle = {MSML},
  year = {2021},
  url = {https://openreview.net/forum?id=_IYBKOrW3H},
}
Figure