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}\left(\frac{1}{mk}+\frac{1}{k^2}\right)$ 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 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.

该研究介绍了一种新的子空间三阶正则牛顿方法，其在解决凸优化问题时具有与维度无关的全局收敛速度，并且在特定谱条件下能恢复到完全维度的三阶正则牛顿方法的收敛速度，数值实验表明该方法比现有的随机子空间方法收敛更快，尤其在高维问题上。