Faster Eigenvector Computation via Shift-and-Invert Preconditioning

Abstract

We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix $\Sigma$ -- i.e. computing a unit vector $x$ such that $x^T\Sigma x\ge (1-\epsilon ){\lambda }_1(\Sigma )$: Offline Eigenvector Estimation: Given an explicit $A\in {\mathbb{R}}^{n\times d}$ with $\Sigma =A^{T}A$, we show how to compute an $\epsilon$ approximate top eigenvector in time $\tilde{O}([nnz(A)+\frac{d\ast sr(A)}{ga{p}^2}]\ast \log 1/\epsilon )$ and $\tilde{O}([\frac{nnz(A{)}^{3/4}(d\ast sr(A){)}^{1/4}}{\sqrt{gap}}]\ast \log 1/\epsilon )$. Here $nnz(A)$ is the number of nonzeros in $A$, $sr(A)$ is the stable rank, $gap$ is the relative eigengap. By separating the $gap$ dependence from the $nnz(A)$ term, our first runtime improves upon the classical power and Lanczos methods. It also improves prior work using fast subspace embeddings [AC09, CW13] and stochastic optimization [Sha15c], giving significantly better dependencies on $sr(A)$ and $\epsilon$. Our second running time improves these further when $nnz(A)\le \frac{d\ast sr(A)}{ga{p}^2}$. Online Eigenvector Estimation: Given a distribution $D$ with covariance matrix $\Sigma$ and a vector $x_0$ which is an $O(gap)$ approximate top eigenvector for $\Sigma$, we show how to refine to an $\epsilon$ approximation using $O(\frac{var(D)}{gap\ast \epsilon })$ samples from $D$. Here $var(D)$ is a natural notion of variance. Combining our algorithm with previous work to initialize $x_0$, we obtain improved sample complexity and runtime results under a variety of assumptions on $D$. We achieve our results using a general framework that we believe is of independent interest. We give a robust analysis of the classic method of shift-and-invert preconditioning to reduce eigenvector computation to approximately solving a sequence of linear systems. We then apply fast stochastic variance reduced gradient (SVRG) based system solvers to achieve our claims.

Appearing in ICML 2016. Combination of work in arXiv:1509.05647 and arXiv:1510.08896

References in corpus (8)

• Powers of Tensors and Fast Matrix Multiplication
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Fast and Simple PCA via Convex Optimization
• SDCA without Duality
• Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• Convergence of Stochastic Gradient Descent for PCA

Cited by in corpus (16)

• Accelerated Methods for Non-Convex Optimization
• Accelerated Stochastic Power Iteration
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation
• A Universal Variance Reduction-Based Catalyst for Nonconvex Low-Rank Matrix Recovery
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• Saving Gradient and Negative Curvature Computations: Finding Local Minima More Efficiently
• Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
• Noisy Accelerated Power Method for Eigenproblems with Applications
• Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgeness
• On the Optimality of the Oja's Algorithm for Online PCA
• Stochastic Variance-reduced Gradient Descent for Low-rank Matrix Recovery from Linear Measurements
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Stochastic Non-convex Optimization with Strong High Probability Second-order Convergence
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Gen-Oja: A Two-time-scale approach for Streaming CCA