Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic\n Problems

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