A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees¶
会议: NeurIPS 2025
arXiv: 2502.04799
代码: 无公开代码（MATLAB实现，实验基于CUTEst benchmark）
领域: 优化理论 / 非凸优化 / 二阶方法
关键词: 正则化Newton方法, 非凸优化, 最优全局复杂度, 二次局部收敛, 自适应算法
一句话总结¶
提出一类基于当前与历史梯度构造的新型正则化器，结合带负曲率监测的共轭梯度法求解正则化Newton方程，在不需要Hessian Lipschitz常数先验知识的自适应框架下，首次同时实现了\(O(\epsilon^{-3/2})\)最优全局迭代复杂度和二次局部收敛速率。
背景与动机¶
非凸优化中寻找\(\epsilon\)-稳定点（\(\|\nabla\varphi(x^*)\|\leq\epsilon\)）是核心问题。Newton类方法因其在正定Hessian解附近的二次局部收敛性而强大，但经典Newton法无法保证全局收敛。为此发展了多种全局化技术：
- 三次正则化（Nesterov & Polyak 2006）：达到最优\(O(\epsilon^{-3/2})\)迭代复杂度且保留二次局部收敛率，但子问题比二次正则化更难求解
- 二次正则化（Levenberg-Marquardt）：子问题等价于求解线性方程组，可用共轭梯度法高效实现，适合大规模问题
- 信赖域方法：如CAT（Hamad & Hinder 2024）同时达到了最优全局阶和二次局部收敛率，但内存开销大
二次正则化方法存在一个长期的全局-局部权衡问题：使用\(\rho_k\propto\|g_k\|^{1/2}\)可获得最优全局复杂度但局部收敛阶仅为\(3/2\)；使用\(\rho_k\propto\|g_k\|\)可获得二次局部收敛但全局率不明确。之前的工作（如Gratton et al. 2024）达到了近最优的\(O(\epsilon^{-3/2}\log(1/\epsilon))\)全局率和超线性局部率，但二者无法同时最优。这篇论文的核心动机就是弥合这一鸿沟。
核心问题¶
能否设计一种无参数的二次正则化Newton方法，同时达到： 1. 最优全局迭代复杂度\(O(\epsilon^{-3/2})\)（不含对数因子） 2. 二次局部收敛率 3. 不需要Hessian Lipschitz常数\(L_H\)的先验知识 4. 不需要计算最小特征值
方法详解¶
整体框架¶
算法名为ARNCG（Adaptive Regularized Newton-CG），其pipeline如下：
输入：初始点\(x_0\)，参数\(\mu,\beta,\tau_-,\tau_+,\gamma,m_{\max},M_0\)以及正则化器序列\(\{\omega_k^t, \omega_k^f\}\)
每次迭代包含三个层次： 1. 主循环：用试探步正则化器\(\omega_k^t\)调用NewtonStep，如果梯度突然上升则切换到回退步正则化器\(\omega_k^f\) 2. NewtonStep子程序：调用CappedCG求解正则化Newton方程\((H+2\rho I)d=-g\)，根据返回类型（SOL/NC/TERM）执行不同的线搜索策略 3. CappedCG子程序：标准共轭梯度法+负曲率监测，总共只需一次额外Hessian向量积
输出：\(\epsilon\)-稳定点\(x^*\)满足\(\|\nabla\varphi(x^*)\|\leq\epsilon\)
关键设计¶
- 新型正则化器构造：论文提出两类正则化器，通过引入一个额外参数\(\theta>0\)和比率\(\delta_k\)来调节全局-局部权衡：
- 第一类：\(\omega_k^f=\|g_k\|^{1/2}\)，\(\omega_k^t=\omega_k^f\cdot\min(1, (g_k/g_{k-1})^\theta)\)
- 第二类：\(\omega_k^f=\epsilon_k^{1/2}\)（其中\(\epsilon_k=\min_{i\leq k}\|g_i\|\)），\(\omega_k^t=\omega_k^f\cdot(\epsilon_k/\epsilon_{k-1})^\theta\)
关键洞察：当\(\theta=0\)时退化为经典的梯度平方根正则化（局部阶\(3/2\)）；当\(\theta>0\)时，额外项\(\delta_k^\theta\)在迭代开始超线性收敛时快速趋零，逐步将局部收敛率从\(3/2\)提升到接近\(2\)；当\(\theta>1\)时达到完整的二次收敛。
- 带负曲率监测的Capped CG：基于Royer et al. (2020)的算法，输出三种状态：
- SOL：找到了正则化Newton方程的近似解
- NC：发现了负曲率方向\(d^T H d \leq -\rho\|d\|^2\)
- TERM：正则化参数太小导致迭代次数过多，提前终止
每次CG迭代只需一次Hessian向量积，且整个CG过程负曲率监测只引入一次额外的Hessian向量积。
- 自适应Lipschitz常数估计：参数\(M_k\)自适应估计\(L_H\)，通过线搜索的成功/失败来调节：
- 成功且下降充分→减小\(M_k\)（\(\mathcal{J}_{-1}\)集合）
- 成功且下降适中→保持\(M_k\)（\(\mathcal{J}_0\)集合）
- 失败→增大\(M_k\)（\(\mathcal{J}_1\)集合）
经过\(O(\log(M_0/L_H))\)次迭代后，\(M_k\)稳定在\(O(L_H)\)水平。
-
双线搜索策略：对SOL情况，先尝试标准的Armijo线搜索（判据2.4），若失败则切换到步长缩放的第二线搜索（判据2.5），确保函数评估次数均匀有界。
-
回退步机制：当试探步导致梯度突然上升（\(g_{k+1/2}>g_k\)且\(g_k\leq g_{k-1}\)）时，切换到使用\(\omega_k^f\)的回退步。这保证了子序列间转换引理（Lemma 3.2）的成立。实验表明回退步在实际中很少触发，可以放松或移除。
损失函数 / 训练策略¶
- 正则化系数\(\rho_k=(M_k\cdot\omega_k)^{1/2}\)，其中\(\omega_k\)根据试探/回退步选取
- CG求解精度\(\xi=\rho_k=M_k^{1/2}\omega_k\)（随迭代自适应变化）
- 实验推荐参数：\(\mu=0.3\), \(\beta=0.5\), \(\tau_-=0.3\), \(\tau_+=1.0\), \(\gamma=5\), \(M_0=1\), \(\eta=0.01\), \(\theta\in[0.5,1]\), \(m_{\max}=1\)
实验关键数据¶
在CUTEst benchmark的124个超过100变量的无约束优化问题上测试（变量维度100-123200），与CAT（信赖域方法）和AN2CER（正则化Newton方法）对比：
| 指标 | ARNCG g | ARNCG ε | CAT | AN2CER |
|---|---|---|---|---|
| 成功率(%) | 87.10 | 86.29 | 85.48 | 81.45 |
| 时间(shifted geo-mean) | 16.71 | 18.28 | 23.34 | 36.70 |
| Hessian评估 | 80.86 | 85.03 | 88.47 | 170.10 |
| 梯度评估 | 86.41 | 90.78 | 96.61 | 172.02 |
| 函数评估 | 119.51 | 125.29 | 125.56 | 176.80 |
| 内存(最大问题) | ~6GB | ~6GB | ~74GB | - |
消融实验要点¶
- 回退步参数\(\lambda\)：对成功率影响微弱，但\(\lambda\)越大回退步触发越频繁、计算成本越高。推荐\(\lambda=0\)（移除回退步）
- 正则化参数\(\theta\)：\(\theta\in[0.5,1]\)是最佳区间，平衡计算效率和局部收敛速度。\(\theta\)过大会要求CG更严格的容差关系，增加Hessian向量积
- 线搜索参数\(m_{\max}\)：\(m_{\max}=1\)即可（每次迭代至多4次函数评估），增大\(m_{\max}\)不会带来显著收益
- 第二线搜索和TERM状态：在实践中很少被触发
- 两类正则化器对比：虽然ARNCG g理论上多一个双对数因子，但实践中表现相当甚至略好
亮点¶
- 理论突破：首次证明二次正则化Newton方法可以同时达到最优\(O(\epsilon^{-3/2})\)全局迭代复杂度和二次局部收敛率，填补了该领域长期存在的理论空白
- 局部收敛率提升技巧（Lemma 3.9）：通过递归论证展示\(\delta_k^\theta\)如何逐步将局部阶从\(3/2\)提升到\(2\)，这是一个非常优雅的分析方法。\(\theta\in(0,1]\)时可达到\(1+\nu_\infty\)阶（\(\nu_\infty\)为特定方程的正根），\(\theta>1\)时经过有限步后达到严格二次
- 实用性：无需Hessian Lipschitz常数的先验知识，无需最小特征值计算，每次CG迭代仅需一次Hessian向量积，大规模问题下内存效率远优于基于矩阵分解的方法（6GB vs 74GB）
- \(\omega_k^f=\epsilon_k\)的选择消除了\(\log\log(1/\epsilon)\)对数因子，其关键在于\(\epsilon_k\)的单调性使得\(V_k\)的控制更精细
局限性 / 可改进方向¶
- 实验规模有限：仅在CUTEst benchmark上测试，虽有PINN实验但深度学习中的大规模应用仍待验证
- Hölder连续Hessian推广：论文指出技术可推广到Hölder连续Hessian的情形，但由于Hölder指数未知需要额外估计，尚未完成
- 凸情形：是否适用于Doikov & Nesterov (2021)等研究的凸设置仍是开放问题
- 随机优化：能否推广到不精确方法（如Yao et al. 2023）和随机优化设置
- 回退步的必要性：实验表明回退步在实践中几乎不触发，理论上是否可以完全移除值得进一步研究
- CG精度的自适应策略：当前CG精度\(\xi=\rho_k\)是为局部收敛设计的，全局阶段可以使用更宽松的固定容差\(\eta\)以减少计算量
与相关工作的对比¶
| 方法 | 全局复杂度 | 局部收敛率 | 需要\(\epsilon\) | 需要最小特征值 |
|---|---|---|---|---|
| Royer et al. 2020 | \(O(\epsilon^{-3/2})\) | N/A | ✓ | ✗ |
| Gratton et al. 2024 (AN2CER) | \(O(\epsilon^{-3/2}\log(1/\epsilon))\) | N/A | ✗ | ✓ |
| Zhu & Xiao 2024 | \(O(\epsilon^{-3/2})\) | 超线性（需全局强凸） | ✓ | ✗ |
| CAT (Hamad & Hinder 2024) | \(O(\epsilon^{-3/2})\) | 二次 | ✗ | ✗ |
| 本文 ARNCG | \(O(\epsilon^{-3/2})+\tilde{O}(1)\) | 二次（\(\theta>1\)时） | ✗ | ✗ |
与CAT相比，ARNCG使用更少内存（避免构造完整Hessian），且在CUTEst上速度略快。与AN2CER相比，ARNCG无需最小特征值计算，全局复杂度无对数因子。
启发与关联¶
- 正则化器中利用历史信息（\(g_{k-1}\)）来"提升"局部收敛率的思想，是否可以类比到深度学习优化器（如Adam的动量项）中，设计同时具有好的全局和局部收敛性质的自适应方法？
- 论文中将迭代序列按梯度范数单调性分段分析的技巧（subsequence partition），在分析其他自适应优化算法时可能有用
- Hessian向量积的高效利用对于大规模问题（如PINN训练）很实用，可作为二阶优化方法在科学计算中的baseline
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次解决了二次正则化Newton法全局-局部复杂度权衡的开放问题
- 实验充分度: ⭐⭐⭐⭐ CUTEst benchmark全面对比，但实际ML应用的验证偏少
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导严谨，结构清晰，关键insight解释到位
- 价值: ⭐⭐⭐⭐⭐ 填补了重要的理论空白，算法设计优雅且实用