Timezone: »

 
Poster
Analysis of Krylov Subspace Solutions of Regularized Non-Convex Quadratic Problems
Yair Carmon · John Duchi

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #48
in Wed Poster Session B »
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.
Keywords: Optimization · Non-Convex Optimization · Algorithms
[ Paper] 

Author Information

Yair Carmon (Stanford)
John Duchi (Stanford)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors