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. This work introduces DMPower and DMStream, two novel momentum-based algorithms that accelerate the classical power method for finding a matrix's dominant eigenvector. Unlike previous accelerated methods that require "oracle" knowledge of the matrix's spectrum to work, these algorithms use a clever two-phase approach to estimate optimal parameters on the fly, achieving near-optimal convergence speeds without the guesswork.
Introduction
The power method is a fundamental tool in machine learning, used for everything from Principal Component Analysis (PCA) to spectral clustering. While simple and robust, it is notoriously slow when the gap between the largest eigenvalue ($\lambda_1$) and the second-largest ($\lambda_2$) is small. Researchers have previously tried to fix this using "momentum"—adding a "heavy ball" term to the update to speed up convergence. However, setting the optimal momentum coefficient ($\beta$) requires knowing $\lambda_2$, which is typically unknown at runtime. Incorrect guesses lead to divergence or suboptimal speed, and existing auto-tuning solutions often negate the speed gains of using momentum.
Methods: Delayed Momentum
The authors propose a two-phase strategy called Delayed Momentum:
- Pre-momentum Phase (The Warm-up): The algorithm starts with standard "vanilla" power iteration. Simultaneously, it performs inexact Hotelling deflation, using the current estimate of the top eigenvector to "subtract" its influence from the matrix. This allows the algorithm to estimate the second eigenvalue, $\lambda_2$.
- Momentum Phase (The Sprint): Once the estimate for $\lambda_2$ stabilizes (controlled by a hyperparameter $\rho$), the algorithm switches to an accelerated momentum-based update using a $\beta$ derived from that estimate.
The paper introduces DMPower for deterministic, offline settings and DMStream for online streaming settings. The core technical contribution is a convergence analysis using perturbation theory, proving that even though the deflation in Phase 1 is "inexact," it provides a sufficiently accurate estimate of $\lambda_2$ to guarantee acceleration in Phase 2.
Key Insights
- The Rayleigh Quotient Advantage: A key realization is that the Rayleigh quotient (used to estimate eigenvalues) is quadratically accurate. Even if the eigenvector estimate is only moderately accurate, the eigenvalue estimate ($\lambda_2$) becomes very accurate quickly, justifying an early switch to the momentum phase.
- Near-Oracle Performance: The "delayed" approach allows the algorithm to eventually match the speed of an "oracle" that was told the exact value of $\lambda_2$ at the start.
- Stability vs. Lanczos: While the Lanczos algorithm is a common alternative, it can be numerically unstable. The authors demonstrate that for many precision requirements, DMPower is faster in terms of "wall-clock" time and more stable.
Key Results
DMPower consistently outperformed the vanilla power method. In cases with tight eigengaps ($\Delta = 0.001$), it matched the convergence speed of the optimal (but practically impossible) Power+M algorithm.
In $500 \times 500$ matrix tests, DMPower was significantly faster than the Lanczos algorithm when factoring in the total time required for numerical stability. On the MNIST dataset, DMStream achieved significantly lower error than Oja’s algorithm (a standard streaming PCA baseline) across various batch sizes. In spectral clustering tasks, DMPower achieved perfect classification accuracy much faster than the vanilla power iteration.
Limitations and Future Work
The method requires a positive "second eigengap" ($\lambda_2 > \lambda_3$) to estimate $\lambda_2$ effectively via deflation. If the second and third eigenvalues are nearly identical, the warm-up phase might take longer. Additionally, while the need for $\lambda_2$ is removed, a new hyperparameter $\rho$ is introduced to decide when to switch phases. Future work includes exploring more sophisticated variance reduction techniques for the streaming version to improve stability in noisy environments.
Summary updated