Analysis of Krylov Subspace Solutions of Regularized Nonconvex 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.

Cited by in corpus (6)

• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Stochastic Gradient Descent with Nonlinear Conjugate Gradient-Style Adaptive Momentum
• Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales
• An accelerated first-order method with complexity analysis for solving cubic regularization subproblems