Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic\n Problems

2018/06/24 by Yair Carmon, John C. Duchi, Carmon, Yair +1 · 4 citations
Computer Science · Mathematics · #Advanced Mathematical Modeling in Engineering #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1806.09222

openalex publication_date 2018/06/24 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28

Abstract

We provide convergence rates for Krylov subspace solutions to the\ntrust-region and cubic-regularized (nonconvex) quadratic problems. Such\nsolutions may be efficiently computed by the Lanczos method and have long been\nused in practice. We prove error bounds of the form 1/t² and\ne^{-4t/\√(\κ)}, where \κ is a condition number for the problem,\nand t is the Krylov subspace order (number of Lanczos iterations). We also\nprovide lower bounds showing that our analysis is sharp.\n

Cited by

• A Distributed Cubic-Regularized Newton Method for Smooth Convex Optimization over Networks
• Fast Approximation of the Gauss-Newton Hessian Matrix for the Multilayer Perceptron
• Uncorrelated Semi-paired Subspace Learning
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales

Related

• Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate
• Some Results on Regularization of LSQR and CGLS for Large-Scale Discrete Ill-Posed Problems
• Regularized methods via cubic model subspace minimization for nonconvex optimization
• Extended-Krylov-subspace methods for trust-region and norm-regularization subproblems
• Error Bounds for the Krylov Subspace Methods for Computations of Matrix Exponentials