2025-11-10T02:38:56.409187

Re$^3$MCN: Cubic Newton + Variance Reduction + Momentum + Quadratic Regularization for Finite-sum Non-convex Problems

Pasechnyuk-Vilensky, Kamzolov, TakÃ¡Ä

We analyze a stochastic cubic regularized Newton method for finite sum optimization $\textstyle\min_{x\in\mathbb{R}^d} F(x) \;=\; \frac{1}{n}\sum_{i=1}^n f_i(x)$, that uses SARAH-type recursive variance reduction with mini-batches of size $b\sim n^{1/2}$ and exponential moving averages (EMA) for gradient and Hessian estimators. We show that the method achieves a $(\varepsilon,\sqrt{L_2\varepsilon})$-second-order stationary point (SOSP) with total stochastic oracle calls $n + \widetilde{\mathcal{O}}(n^{1/2}\varepsilon^{-3/2})$ in the nonconvex case (Theorem 8.3) and convergence rate $\widetilde{\mathcal{O}}(\frac{L R^3}{T^2} + \frac{Ï_2 R^2}{T^2} + \frac{Ï_1 R}{\sqrt{T}})$ in the convex case (Theorem 6.1). We also treat the matrix-free variant based on Hutchinson's estimator for Hessian and present a fast inner solver for the cubic subproblem with provable attainment of the required inexactness level.

academic

Re³MCN: Cubic Newton + Variance Reduction + Momentum + Quadratic Regularization for Finite-sum Non-convex Problems

基本信息

论文ID: 2510.08714
标题: Re³MCN: Cubic Newton + Variance Reduction + Momentum + Quadratic Regularization for Finite-sum Non-convex Problems
作者: Dmitry Pasechnyuk-Vilensky (MBZUAI), Dmitry Kamzolov (TSE, France), Martin Takáč (MBZUAI)
分类: math.OC (数学优化)
发表时间: 2025年10月9日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.08714

摘要

本文提出了一种随机立方正则化牛顿方法用于有限和优化问题 $\min_{x\in\mathbb{R}^d} F(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$ ，该方法使用SARAH型递归方差缩减技术，配合大小为 $b \sim n^{1/2}$ 的小批量和指数移动平均(EMA)来估计梯度和Hessian矩阵。研究表明，该方法在非凸情况下能以 $n + \tilde{O}(n^{1/2}\varepsilon^{-3/2})$ 的随机预言机调用次数达到 $(\varepsilon,\sqrt{L_2\varepsilon})$ -二阶平稳点(SOSP)，在凸情况下达到 $\tilde{O}(\frac{LR^3}{T^2} + \frac{\sigma_2 R^2}{T^2} + \frac{\sigma_1 R}{\sqrt{T}})$ 的收敛率。

研究背景与动机

核心问题

在非凸机器学习优化中寻找二阶平稳点是一个核心挑战。深度神经网络训练、张量分解和贝叶斯推断等问题通常涉及一阶方法可能在鞍点停滞的目标函数。

问题重要性

鞍点逃逸：二阶方法利用曲率信息提供了逃离鞍点的潜在途径
计算瓶颈：处理精确Hessian矩阵的计算成本过高，特别是对于大规模经验风险最小化问题，复杂度为 $O(nd^2)$
理论保证：立方正则化牛顿(CRN)方法为逃避优化轨迹上的鞍点提供了强收敛保证

现有方法局限性

现有的方差缩减立方牛顿方法存在以下问题：

复杂度依赖性差：某些方法在维数和目标精度上的依赖性较差
预言机复杂度不优：梯度或Hessian预言机复杂度未达到最优
实用性限制：缺乏高效的实用版本分析

研究动机

整合方差缩减技术与二阶更新，开发既有理论保证又具实用效率的算法，特别是在高维场景下避免 $O(d^2)$ 瓶颈。

核心贡献

算法设计：提出Re³MCN算法，结合EMA-SARAH估计器用于梯度和Hessian，以及基于Hutchinson估计器的无矩阵子问题求解器
理论保证：证明Re³MCN在非凸情况下以 $\tilde{O}(n+n^{1/2}\varepsilon^{-3/2})$ 的预言机复杂度找到 $(\varepsilon,\sqrt{L\varepsilon})$ -SOSP，在凸情况下达到 $\tilde{O}(\frac{LR^3}{T^2} + \frac{\sigma_2R^2}{T^2} + \frac{\sigma_1R}{\sqrt{T}})$ 收敛率
实用效率：算法设计适用于高维问题，通过无矩阵内求解器避免 $O(d^2)$ 瓶颈
可实现性：进行数值实验比较现有方差缩减立方牛顿方法，作为OPTAMI包的一部分实现

方法详解

问题设定与假设

优化问题： $F(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$

核心假设：

(A1) 二阶光滑性：Hessian矩阵Lipschitz连续，常数为 $L_2 > 0$
(A2) 有界性：Hessian矩阵在算法轨迹上一致有界
(A3-A5) 方差有界性：随机预言机具有有界方差

算法架构

Re³MCN算法核心组件：

EMA权重调度： $\alpha_t = c(t+1)^{-1/2}$ ，其中 $c \in (0,1/2]$
SARAH更新：
- 梯度： $\Delta g_t := \frac{1}{b}\sum_{i \in I_t}[\nabla f_i(x_t) - \nabla f_i(x_{t-1})]$
- Hessian： $\Delta H_t := \frac{1}{b}\sum_{i \in I_t}[\nabla^2 f_i(x_t) - \nabla^2 f_i(x_{t-1})]$
EMA聚合：
- $g_t \leftarrow (1-\alpha_t)g_{t-1} + \alpha_t \hat{g}_t$
- $H_t \leftarrow (1-\alpha_t)H_{t-1} + \alpha_t \hat{H}_t$
立方子问题： $m_t(s) = g_t^T s + \frac{1}{2}s^T H_t s + \frac{\beta_t}{2}\|s\|^2 + \frac{M}{6}\|s\|^3$

技术创新点

EMA-SARAH结合：首次将指数移动平均与SARAH方差缩减技术结合，实现更稳定的估计
自适应二次正则化：
- 凸情况： $\beta_t = 2\max\{\frac{C_4\sigma_2}{\sqrt{b}}, C_5L_2R\}(t+1)$
- 非凸情况：引入固定的近端二次项改善噪声聚合
矩阵无关实现：基于Hutchinson估计器实现Hessian-向量乘积，避免显式存储Hessian矩阵

理论分析框架

一步下降界： $E[F(x_{t+1}) - F(x_t) | \mathcal{G}_t] \leq -\frac{L_2}{8}E[\|s_t\|^3] + \frac{2}{3}M^{-1/2}E[\|\epsilon_t\|^{3/2}] + M^{-1/2}E[\|\Sigma_t\|_{op}^{3/2}]$