Entrywise convergence of iterative methods for eigenproblems

Vasileios Charisopoulos, Austin R. Benson, Anil Damle

Computing eigenvectors is a foundational step in many machine learning and statistical tasks, from spectral clustering to network analysis. For large-scale problems, these are typically computed using iterative schemes like subspace iteration. While classical analysis provides robust convergence guarantees based on the spectral norm ($l_2$), modern applications often require a different perspective.

This paper introduces the first deterministic convergence analysis for subspace iteration measured in the entrywise ($l_{2 \to \infty}$) norm. By tracking how individual entries of eigenvectors converge, the authors develop a practical stopping criterion that can reduce computation time by 20–80% for downstream tasks without sacrificing accuracy.

The Problem with Standard Metrics

In fields like network science, we often need the "leading" eigenvectors of massive matrices to rank nodes (e.g., eigenvector centrality) or group them (e.g., spectral clustering). Traditionally, numerical analysts measure the quality of these approximations using the spectral norm, which evaluates the "global" error.

However, for many applications, we care primarily about the entrywise error. If you are ranking the top 100 most influential people in a social network, you only need the specific values (entries) in the eigenvector to be accurate enough to maintain the correct order. In these cases, the $l_2$ norm is often a severe overestimate of the error actually needed. Until now, there were no generic stopping criteria or deterministic bounds that specifically tracked this entrywise convergence for iterative eigensolvers.

Methods: Subspace Iteration and Entrywise Bounds

The authors focus on Subspace Iteration, a standard iterative method for finding the principal subspace of a matrix. Their contribution is two-fold:

  1. Theoretical Analysis: They derive new convergence bounds for the $l_{2 \to \infty}$ distance—the maximum $l_2$ norm of the rows of the difference between the true and approximate subspace. These bounds incorporate the coherence of the matrix, which measures how "spread out" the information is across the eigenvector's entries.
  2. Practical Stopping Criterion: They propose a new residual-based stopping criterion ($res_{2 \to \infty}$) derived from perturbation theory. Unlike standard criteria that stop when the global residual is small, this criterion halts the algorithm when the entrywise error is guaranteed to be below a user-defined threshold.
Comparison of convergence metrics showing the entrywise norm converging differently than the standard spectral norm.

Key Insights and Results

The paper evaluates these methods on both synthetic data and real-world networks (including ArXiv collaboration networks and Facebook social graphs).

  • The "Good Enough" Threshold: For tasks like ranking or clustering, eigenvectors do not need to be computed to machine precision. The $l_{2 \to \infty}$ norm captures the point where the ordering of entries stabilizes, which happens long before the $l_2$ norm reaches a tiny value.
  • Efficiency Gains: By using an entrywise stopping criterion, the iterative process can be terminated much earlier. The "naive" $l_2$ stopping criterion forces the algorithm to do unnecessary work that doesn't actually improve the results of the downstream task.
  • Massive Speedups: In node ranking experiments, the proposed stopping criterion led to a 20–40% reduction in required iterations. For spectral clustering tasks, the savings were even more dramatic, reaching 70–80% fewer iterations while maintaining the same "cut" quality as eigenvectors computed to full precision.
Theoretical convergence rates closely tracking the actual entrywise distance during subspace iteration.

Numerical experiments on synthetic data confirmed that their theoretical bounds (specifically "Rate 3" derived in the paper) closely track the actual idealized convergence rate, proving the theory is highly practical.

Limitations and Future Work

The theoretical proofs rely on a technical assumption regarding the decay of the "tail" eigenvalues. While the authors empirically verify that this holds for their test cases, a more general proof removing this assumption would strengthen the theoretical foundation. Additionally, the practical residual estimate ($res_{2 \to \infty}$) can be loose in the very first few iterations before the subspace has made sufficient progress.

While the stopping criterion is generic, the detailed convergence analysis in this paper is specific to subspace iteration. Extending this rigorous entrywise analysis to other popular iterative methods, such as Lanczos or Krylov subspace methods, is a natural and promising next step.

Summary updated

Abstract

Several problems in machine learning, statistics, and other fields rely on computing eigenvectors. For large scale problems, the computation of these eigenvectors is typically performed via iterative schemes such as subspace iteration or Krylov methods. While there is classical and comprehensive analysis for subspace convergence guarantees with respect to the spectral norm, in many modern applications other notions of subspace distance are more appropriate. Recent theoretical work has focused on perturbations of subspaces measured in the ℓ2→∞ norm, but does not consider the actual computation of eigenvectors. Here we address the convergence of subspace iteration when distances are measured in the ℓ2→∞ norm and provide deterministic bounds. We complement our analysis with a practical stopping criterion and demonstrate its applicability via numerical experiments. Our results show that one can get comparable performance on downstream tasks while requiring fewer iterations, thereby saving substantial computational time.
BibTeX
@inproceedings{charisopoulos2020entrywise,
  author = {Vasileios Charisopoulos and Austin R. Benson and Anil Damle},
  title = {{Entrywise convergence of iterative methods for eigenproblems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=oWnIkRuJ6Z},
}
Figure