NeurIPS 2018oral59 citations
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.
BibTeX
@inproceedings{NEURIPS2018_349f36aa,
author = {Carmon, Yair and Duchi, John C},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/349f36aa789af083b8e26839bd498af9-Paper.pdf},
volume = {31},
year = {2018}
}