This paper addresses the optimization problem of minimizing non-convex
continuous functions, which is relevant in the context of high-dimensional
machine learning applications characterized by over-parametrization. We analyze
a randomized coordinate second-order method named SSCN which can be interpreted
as applying cubic regularization in random subspaces. This approach effectively
reduces the computational complexity associated with utilizing second-order
information, rendering it applicable in higher-dimensional scenarios.
Theoretically, we establish convergence guarantees for non-convex functions,
with interpolating rates for arbitrary subspace sizes and allowing inexact
curvature estimation. When increasing subspace size, our complexity matches
$\mathcal{O}(\epsilon^{-3/2})$ of the cubic regularization (CR) rate.
Additionally, we propose an adaptive sampling scheme ensuring exact convergence
rate of $\mathcal{O}(\epsilon^{-3/2}, \epsilon^{-3})$ to a second-order
stationary point, even without sampling all coordinates. Experimental results
demonstrate substantial speed-ups achieved by SSCN compared to conventional
first-order methods.

该论文研究了优化非凸连续函数的问题，提出了一种名为 SSCN 的随机坐标二阶方法，通过在随机子空间应用立方正则化来降低使用二阶信息的计算复杂性，在高维场景中表现出了良好的适用性，并且通过提出自适应采样方案，实现了比传统一阶方法更快的速度。