Processing math: 100%
Skip to yearly menu bar Skip to main content


Poster

Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate

Ruichen Jiang · Parameswaran Raman · Shoham Sabach · Aryan Mokhtari · Mingyi Hong · Volkan Cevher

MR1 & MR2 - Number 138

Abstract: Second-order optimization methods, such as cubic regularized Newton methods, are known for their rapid convergence rates; nevertheless, they become impractical in high-dimensional problems due to their substantial memory requirements and computational costs. One promising approach is to execute second-order updates within a lower-dimensional subspace, giving rise to subspace second-order methods. However, the majority of existing subspace second-order methods randomly select subspaces, consequently resulting in slower convergence rates depending on the problem's dimension d. In this paper, we introduce a novel subspace cubic regularized Newton method that achieves a dimension-independent global convergence rate of O(1mk+1k2) for solving convex optimization problems. Here, m represents the subspace dimension, which can be significantly smaller than d. Instead of adopting a random subspace, our primary innovation involves performing the cubic regularized Newton update within the \emph{Krylov subspace} associated with the Hessian and the gradient of the objective function. This result marks the first instance of a dimension-independent convergence rate for a subspace second-order method. Furthermore, when specific spectral conditions of the Hessian are met, our method recovers the convergence rate of a full-dimensional cubic regularized Newton method. Numerical experiments show our method converges faster than existing random subspace methods, especially for high-dimensional problems.

Chat is not available.