# Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems

arXiv: https://arxiv.org/abs/1806.09222 · HTML: https://mlsanity.com/paper/1806.09222/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2018.

## Built on by (most cited first, 9 of 9)

- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace](https://mlsanity.com/paper/2404.03331/) (2024)
- [Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate](https://mlsanity.com/paper/2401.03058/) (2024)
- [A Momentum Accelerated Adaptive Cubic Regularization Method for Nonconvex Optimization](https://mlsanity.com/paper/2210.05987/) (2022)
- [Approximate Secular Equations for the Cubic Regularization Subproblem](https://mlsanity.com/paper/2209.13268/) (2022)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence](https://mlsanity.com/paper/2608.22129/) (2026)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)
- [Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization](https://mlsanity.com/paper/2302.11076/) (2023)

## Abstract (arXiv)

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.