Cubic regularized subspace Newton for non-convex optimization

本文探讨了在高维机器学习应用中普遍存在的过度参数化问题下，最小化非凸连续函数的优化问题。我们分析了一种随机坐标二阶方法，名为SSCN，它可以被解释为在随机子空间中应用三次正则化。这种方法有效地降低了利用二阶信息所需的计算复杂度，使其适用于更高维的场景。在理论上，我们为非凸函数建立了收敛保证，对于任意子空间大小，允许不精确的曲率估计，具有插值速率。当子空间大小增加时，我们的复杂度与三次正则化（CR）速率的$\mathcal{O}(\epsilon^{-3/2})$相匹配。此外，我们提出了一种自适应采样方案，确保精确收敛速率为$\mathcal{O}(\epsilon^{-3/2}, \epsilon^{-3})$，即使没有采样所有坐标也能达到二阶稳定点。实验结果表明，与传统的一阶方法相比，SSCN取得了显著的加速效果。

本论文旨在解决高维机器学习应用中的非凸连续函数最小化优化问题，该问题特点是过度参数化。论文提出了一种名为SSCN的随机坐标二阶方法，可以在随机子空间中应用三次正则化，有效地降低了利用二阶信息所需的计算复杂度，使其适用于更高维的情况。

论文的关键思路是将三次正则化应用于随机子空间中，以降低计算复杂度，提高算法效率。此外，论文还提出了一种自适应采样方案，可以在不采样所有坐标的情况下确保精确收敛速率。

论文建立了非凸函数的收敛保证，可以对任意子空间大小进行插值，并允许不精确的曲率估计。当增加子空间大小时，复杂度与三次正则化（CR）速率的复杂度匹配。实验结果表明，与传统的一阶方法相比，SSCN取得了显著的加速效果。

在这个领域中，最近的相关研究包括：Cubic regularization for non-convex optimization problems，Randomized coordinate descent methods with arbitrary sampling，Stochastic cubic regularization methods for nonconvex optimization。