\begin{document}
\maketitle

\begin{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.
\end{abstract}

\input{intro.tex}

\input{tr.tex}
\input{cubic.tex}
\input{lower.tex}
\input{experiment.tex}

\newpage 

\section*{Acknowledgments}
We thank the anonymous reviewers for several helpful questions and 
suggestions. Both authors were supported by NSF-CAREER Award 1553086 
and the Sloan Foundation. YC was partially supported by the Stanford 
Graduate Fellowship.

\setlength{\bibsep}{6pt}
\bibliographystyle{abbrvnat}

\bibliography{bib}

\newpage

\appendix

\part*{Supplementary material}

\input{lanczos.tex}
\input{polys.tex}
\input{ub-proofs.tex}
\input{lb-proofs.tex}
\input{experiment-details.tex}


\end{document}
{"config": "arxiv", "file": "1806.09222/krylov_paper.tex"}