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

We provide convergence rates for Krylov subspace solutions to the trust-region and cubic-regularized (nonconvex) quadratic problems. Such solutions may be efficiently computed by the Lanczos method and have long been used in practice.

This paper gives a complete analysis of how many iterations are required for a Krylov subspace method to approximately solve the "trust region" and "cubic-regularized" quadratic minimization problems. These problems take the form: min x T A x b Tx subject to x R or with an additional regularization term of param* x 3. A is a symmetric, but not necessarily PSD matrix (i.e. it can have negative eigenvalues). The objective function is not necessarily convex. Problems of this form are important in a number of applications, especially as subroutines for regularized Newton methods. In addition to their practical importance, such methods have recently been used to give the fastest theoretical runtimes for finding stationary points and local minima of general non-convex objective functions.

We provide convergence rates for Krylov subspace solutions to the trust-region and cubic-regularized (nonconvex) quadratic problems. Such solutions may be efficiently computed by the Lanczos method and have long been used in practice. We prove error bounds of the form $1/t^2$ and $e^{-4t/\sqrt{\kappa}}$, where $\kappa$ is a condition number for the problem, and $t$ is the Krylov subspace order (number of Lanczos iterations). We also provide lower bounds showing that our analysis is sharp.