Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems

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/t2 and e^-4t/√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.