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: 立方ニュートン法 + 分散削減 + モーメンタム + 二次正則化による有限和非凸問題の解法

基本情報

論文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)を組み合わせて勾配とヘッシアン行列を推定する。研究結果は、非凸の場合に $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}})$ の収束率を達成することを示している。

研究背景と動機

核心問題

非凸機械学習最適化において二階平稳点を見つけることは中心的な課題である。深層ニューラルネットワーク訓練、テンソル分解、ベイズ推論などの問題は、通常、一階法が鞍点で停滞する可能性のある目的関数を含む。

問題の重要性

鞍点からの脱出：二階法は曲率情報を利用して鞍点から脱出する潜在的な手段を提供する
計算ボトルネック：正確なヘッシアン行列の処理は計算コストが高く、特に大規模経験リスク最小化問題では複雑度が $O(nd^2)$ となる
理論的保証：立方正則化ニュートン(CRN)法は最適化軌跡上の鞍点回避に対して強い収束保証を提供する

既存手法の限界

既存の分散削減立方ニュートン法には以下の問題がある：

複雑度依存性の悪さ：ある手法は次元と目標精度に対する依存性が良くない
オラクル複雑度の非最適性：勾配またはヘッシアンオラクル複雑度が最適に達していない
実用性の制限：効率的な実用版の分析が不足している

研究動機

分散削減技術と二階更新を統合し、理論的保証と実用的効率を両立するアルゴリズムを開発すること、特に高次元シナリオで $O(d^2)$ ボトルネックを回避する。

核心貢献

アルゴリズム設計：勾配とヘッシアンのEMA-SARAH推定器、およびHutchinson推定器に基づく行列フリー部分問題ソルバーを組み合わせたRe³MCNアルゴリズムを提案
理論的保証：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) 二階平滑性：ヘッシアン行列がLipschitz連続で、定数が $L_2 > 0$
(A2) 有界性：ヘッシアン行列がアルゴリズム軌跡上で一様に有界
(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})]$
- ヘッシアン： $\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推定器に基づいてヘッシアン-ベクトル積を実装し、ヘッシアン行列の明示的な保存を回避

理論的分析フレームワーク

一ステップ下降界： $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}]$

主不等式：BDG不等式を用いて分散項を集約し、以下を得る： $\frac{L_2}{8}E[S_T] \leq \Delta F + \frac{C_*}{b^{3/4}}T^{9/8}E[S_T^{1/6}]$

実験設定

理論的検証

論文は主に理論分析を提供し、以下の方法で検証する：

複雑度分析：オラクル複雑度界の詳細な導出
収束性証明：アルゴリズムの収束性質の厳密な証明
パラメータ選択：最適なパラメータ設定に対する理論的指導

実装の詳細

バッチサイズ： $b = \lceil n^{1/2} \rceil$

エポック長：

正則化なし： $T_{max} = \Theta(n^{1/3})$
正則化あり： $T_{max} = \Theta(n^{3/5})$

内部ソルバー：割線二分法 + 打ち切り共役勾配法を用いて立方部分問題を解く

実験結果

主要な理論的結果

定理8.3（非凸複雑度）：仮定(A1)-(A5)の下で、Re³MCNアルゴリズムは $(\varepsilon,\sqrt{L_2\varepsilon})$ -SOSPを返し、総オラクル複雑度は以下の通り： $G = H \leq n + \tilde{O}(n^{1/2}\varepsilon^{-3/2})$

定理6.1（凸収束率）： $F$ が凸関数と仮定すると、アルゴリズムは以下の収束率を達成する： $E[F(x_T) - F^*] \leq \frac{C_1L_2R^3 + C_\beta\beta_0R^2}{(T+1)^2} + \frac{C_3\sigma_1R}{\sqrt{T+1}}$

複雑度比較

既存手法との比較：

改善された $n$ 依存性： $n^{5/6}$ または $n^{4/5}$ から $n^{1/2}$ に改善
最適な $\varepsilon$ 依存性： $\varepsilon^{-3/2}$ の最適率を達成
統一フレームワーク：凸と非凸の場合を同時に処理

結論と議論

主要な結論

理論的突破：非凸有限和最適化において初めて $n + \tilde{O}(n^{1/2}\varepsilon^{-3/2})$ のオラクル複雑度を実現
技術的革新：EMA-SARAH結合がより安定した分散削減を提供
実用性：Hutchinson推定器により高次元問題への適用が可能