Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems
Abstract
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.
Cite
Text
Carmon and Duchi. "Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems." Neural Information Processing Systems, 2018.Markdown
[Carmon and Duchi. "Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems." Neural Information Processing Systems, 2018.](https://mlanthology.org/neurips/2018/carmon2018neurips-analysis/)BibTeX
@inproceedings{carmon2018neurips-analysis,
title = {{Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems}},
author = {Carmon, Yair and Duchi, John C.},
booktitle = {Neural Information Processing Systems},
year = {2018},
pages = {10705-10715},
url = {https://mlanthology.org/neurips/2018/carmon2018neurips-analysis/}
}