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.
Introduction
In large-scale optimization, particularly within the context of training deep neural networks or solving complex physical simulations, second-order methods like Newton’s method are highly desirable for their rapid convergence. However, these methods require solving a quadratic subproblem at every iteration. When the objective function is nonconvex, the Hessian matrix $A$ may not be positive definite, necessitating the use of globalization strategies such as trust-region or cubic regularization to ensure stability.
The primary challenge in high-dimensional settings is the computational cost. With millions or billions of parameters, storing or inverting the Hessian is infeasible. Practitioners instead rely on Krylov subspace methods—specifically the Lanczos method—which only require Hessian-vector products. Despite their decades-long use, a complete theoretical understanding of their convergence rates for nonconvex problems remained elusive until now. This paper addresses this gap by providing the first comprehensive convergence analysis, covering both linear and sublinear regimes and addressing the notorious "hard case."
Problem Formulation and Methodology
The core of the analysis focuses on minimizing a quadratic function $f(x) = \frac{1}{2}x^T Ax + b^T x$ over a Krylov subspace $\mathcal{K}_t(A, b) = \text{span}\{b, Ab, \dots, A^{t-1}b\}$. To solve this efficiently, the Lanczos method is employed to construct an orthonormal basis for the subspace, transforming the high-dimensional problem into a much smaller, manageable tridiagonal system.
Technical Framework
The authors utilize several key technical components to derive their bounds:
- Polynomial Approximation: Leveraging classical results from approximation theory, specifically Chebyshev polynomials, to bound the approximation error within the subspace.
- Error Decomposition: The authors demonstrate that the total error in nonconvex problems can be decomposed into a "convex error" (governed by standard optimization theory) and a "norm error" (related to how effectively the subspace captures the direction of the minimum eigenvector).
- Randomization Strategies: To resolve the "hard case"—where the linear term $b$ is orthogonal to the matrix's smallest eigenvector—the paper analyzes two strategies: augmenting the Krylov subspace with a random vector and perturbing the linear term $b$ with Gaussian noise.
Convergence Results and Sharpness
The paper establishes two primary convergence rates that characterize the performance of the Lanczos method in this setting:
- Linear Convergence: For well-conditioned problems, the error decreases at a rate of $e^{-4t/\sqrt{\kappa}}$. This result is significant as it matches the well-known convergence rate of the Conjugate Gradient method for convex problems, extending that intuition to the nonconvex regime.
- Sublinear Convergence: In scenarios where the problem is poorly conditioned or approaches the "hard case," the authors guarantee a convergence rate of $1/t^2$.
Crucially, the authors prove that these rates are sharp. By constructing adversarial matrices using a resisting oracle argument, they demonstrate that no deterministic algorithm relying solely on matrix-vector products can surpass these bounds. This establishes the reported rates as the fundamental limits for this class of algorithms.
Numerical Validation
To validate the theoretical findings, the authors conducted experiments on synthetic high-dimensional problem instances ($d = 1,000,000$). By constructing matrices with controlled spectral properties, they tested various condition numbers and "hard case" scenarios. The results, averaged over 5,000 random instances, perfectly aligned with the $4/\sqrt{\kappa}$ slope predicted by the theory. Furthermore, the experiments confirmed that even a minimal amount of noise is sufficient to bypass the "hard case," restoring fast convergence with high probability.
Discussion and Limitations
While this work provides a rigorous foundation for Krylov subspace methods in nonconvex optimization, some questions remain. The current analysis assumes exact arithmetic, whereas the Lanczos method in practice is sensitive to floating-point errors which can lead to a loss of orthogonality. Additionally, while randomization is effective, choosing the optimal perturbation magnitude $\sigma$ remains a heuristic challenge: too much noise creates an accuracy floor, while too little fails to escape the hard case efficiently. Future research into automated parameter tuning and finite-precision analysis will be essential for further refining these methods in practical applications.
Summary updated