Entrywise convergence of iterative methods for eigenproblems
Vasilis Charisopoulos (ORIE, Cornell University)
Several problems in machine learning and statistics admit spectral approaches, via the computation of invariant subspaces via iterative methods. Intepretability considerations as well as recent theoretical work have established that it is often preferable to measure subspace distance using “entrywise” norms, such as the $\ell_{2 \to \infty}$ operator norm; this introduces additional computational considerations, due to the lack of convergence theory and stopping criteria tailored to that choice of norm. In this talk, we introduce a stopping criterion closely tracking the $\ell_{2 \to \infty}$ subspace distance and demonstrate that it introduces nontrivial speedups in the low-to-medium accuracy regime for a few problems of interest. In addition, we show a couple of deterministic bounds for the convergence of subspace iteration and discuss their implications.