Despite recent provably guaranteed variants, the empirical performance often remains unsatisfactory.

Shift-and-invert preconditioning, as a classic acceleration technique for the leading eigenvector computation, has received much attention again recently, owing to fast least-squares solvers for efficiently approximating matrix inversions in power iterations.

For regression, we obtain a running time of O(nd+(nL/µ) p snL/µ) where µ > 0 is the smallest eigenvalue ofA>A. This running time improves upon the previous best unaccelerated running time of O(nd + nLd/µ). This result expands the regimes where regression can be solved in nearly linear time from whenL/µ= O(1)towhenL/µ= O(d2/3/(sn)1/3).

CG method: only a single eigenvector computation is required.

Shift-and-invert preconditioning, as a classic acceleration technique for the leading eigenvector computation, has received much attention again recently, owing to fast least-squares solvers for efficiently approximating matrix inversions in power iterations. In this work, we adopt an inexact Riemannian gradient descent perspective to investigate this technique on the effect of the step-size scheme. The shift-and-inverted power method is included as a special case with adaptive step-sizes. Particularly, two other step-size settings, i.e., constant step-sizes and Barzilai-Borwein (BB) step-sizes, are examined theoretically and/or empirically.

Neural Information Processing Systems http://nips.cc/

The main idea is incorporating Nesterov's accelerated gradient descent (AGD) in eigenvalue problem. The approach relies on shift-and-invert preconditioning method that reduces the non-convex objective of Rayleigh quotient to a sequence of convex programs. Shift-and-invert preconditioning improves the convergence dependency of the gradient method to the eigengap of the given matrix. The focus of this paper is using AGD method to approximately solve the convex programs and reaching an accelerated convergence rate for the convex part. Exploiting the accelerated convergence of AGD, they reach an accelerated convergence for the first-order optimization of the eigenvalue problem.

Minimizing a convex function over the spectrahedron, i.e., the set of all d d positive semidefinite matrices with unit trace, is an important optimization task with many applications in optimization, machine learning, and signal processing. It is also notoriously difficult to solve in large-scale since standard techniques require to compute expensive matrix decompositions. An alternative is the conditional gradient method (aka Frank-Wolfe algorithm) that regained much interest in recent years, mostly due to its application to this specific setting. The key benefit of the CG method is that it avoids expensive matrix decompositions all together, and simply requires a single eigenvector computation per iteration, which is much more efficient.

Shift-and-invert preconditioning, as a classic acceleration technique for the leading eigenvector computation, has received much attention again recently, owing to fast least-squares solvers for efficiently approximating matrix inversions in power iterations. In this work, we adopt an inexact Riemannian gradient descent perspective to investigate this technique on the effect of the step-size scheme. The shift-and-inverted power method is included as a special case with adaptive step-sizes. Particularly, two other step-size settings, i.e., constant step-sizes and Barzilai-Borwein (BB) step-sizes, are examined theoretically and/or empirically. Our experimental studies show that the proposed algorithm can be significantly faster than the shift-and-inverted power method in practice.