Practical Regularized Quasi-Newton Methods with Inexact Function Values

Each language version is independently generated for its own context, not a direct translation.

这篇论文讲述了一个关于**“如何在充满噪音和误差的环境中，依然能高效找到最优解”**的数学故事。

为了让你轻松理解，我们可以把优化问题想象成**“在迷雾中下山”**。

1. 核心问题：迷雾中的下山者

想象你站在山顶，想要走到山谷最低点（这就是最小化目标函数）。

理想情况：你有一双火眼金睛，能看清脚下的每一步高度，也能精准感知坡度（梯度）。这时候，你走起路来飞快，像著名的L-BFGS 算法（一种经典的下山方法），几步就能到谷底。
现实情况：但是，现实世界充满了“迷雾”和“杂音”。
- 你的高度计（函数值）可能因为电池老化或信号干扰，显示的数字是错的（数值误差）。
- 你脚下的路可能因为浮点数计算精度不够（比如手机芯片只有 16 位精度），导致你感觉到的坡度也是歪的。
- 在这种“脏数据”环境下，传统的下山方法会晕头转向：它们会误以为前面是下坡，结果掉进坑里；或者因为数据抖动，在原地疯狂打转，永远到不了终点。

2. 作者的解决方案：带“防抖”功能的智能登山杖

作者提出了一种新的方法，叫**“抗噪正则化拟牛顿法”。我们可以把它想象成给登山者配备了一根“智能登山杖”**，这根杖有三个绝招：

绝招一：给路加“缓冲垫”（正则化 Regularization）

比喻：当你感觉脚下不稳（数据噪音大）时，传统的登山者会盲目加速，结果摔跟头。新方法则是：一旦检测到数据不可靠，就立刻给脚下的路加一层**“缓冲垫”**（数学上的正则化参数 $\mu_k$ ）。
作用：这层垫子让你不敢走得太快、太激进。它强迫你每一步都走得稳一点，哪怕牺牲一点速度，也要保证不会掉进坑里。这就叫**“正则化”，它让算法在乱糟糟的数据中也能保持“情绪稳定”**。

绝招二：模糊的“成功标准”（松弛的 Armijo 条件）

比喻：传统的下山规则是：“只要高度下降了 0.001 米，就算成功”。但在噪音环境下，高度计可能今天显示降了，明天显示升了，全是假象。
新方法：作者改规则说：“只要高度下降的幅度超过噪音的干扰范围，才算成功。”
作用：这就像给登山者戴上了**“降噪耳机”**。如果高度计显示的波动只是杂音，登山者就忽略它，继续走；只有当真正的下坡出现时，才确认前进。这避免了因为一点点数据抖动就停止前进或乱跑。

绝招三：聪明的“记忆模式”（自适应更新）

比喻：登山者有两种模式：
1. 冲刺模式：当天气好、路清晰时，他完全信任自己的经验（拟牛顿法），大步流星。
2. 稳健模式：当雾太大时，他切换到“盲走模式”（类似 AdaGrad-Norm 算法），只依赖累积的步数经验，不再盲目相信当下的错误读数。
作用：这个新方法能自动切换。如果数据靠谱，它就跑得飞快；如果数据全是噪音，它就自动变得保守稳健。它不需要人工去调参数，自己就能“见风使舵”。

3. 实验结果：在“烂泥地”里也能跑赢

作者把这套方法放在各种极端环境下测试：

人工噪音：故意给数据加了很多随机干扰。
低精度计算：模拟只有 16 位或 32 位精度的老旧芯片（就像在泥地里跑步）。

结果令人惊讶：

传统的“火眼金睛”登山者（标准 L-BFGS）在噪音里经常迷路、卡死或者跑偏。
而作者的新方法（Ours），就像那个戴着降噪耳机、脚踩缓冲垫的登山者，不仅没迷路，反而比其他人更早到达终点，而且跑得依然很快。

4. 总结：为什么这很重要？

在现实世界中，无论是训练 AI 模型、模拟物理实验，还是在手机芯片上运行算法，数据永远不可能是完美的。

以前的算法太“娇气”，稍微有点误差就崩溃。
这篇论文提出的方法，就像给算法穿上了一身**“防弹衣”**。它证明了：即使数据是“脏”的，我们依然可以设计出让算法既跑得快、又跑得稳的数学工具。

一句话总结：
这就好比在狂风暴雨中开车，以前的车（传统算法）容易打滑翻车，而作者造了一辆自带防滑链和智能避震的越野车，不管路面多烂，都能稳稳当当地把你送到目的地。

Each language version is independently generated for its own context, not a direct translation.

论文技术总结：具有不精确函数值的实用正则化拟牛顿法

1. 研究背景与问题定义

核心问题：许多实际优化问题中的目标函数值会受到不可避免的数值误差污染（例如有限精度浮点运算、基于仿真的评估、随机近似等）。在光滑非凸优化中，传统的拟牛顿法（如 BFGS/L-BFGS）结合线搜索（Line Search）虽然高效，但其理论保证依赖于精确的函数评估。
现有挑战：当函数值存在噪声时，标准的线搜索条件（如 Wolfe 条件或 Armijo 条件）可能变得不可靠，导致步长不稳定、Hessian 近似病态或算法过早终止。
问题设定：
- 目标：求解无约束优化问题 $\min f(x)$ ，其中 $f$ 是连续可微的非凸函数。
- 噪声模型：假设只能获得受误差污染的目标函数值 $\tilde{f}(x)$ ，满足混合绝对 - 相对误差模型： $|\tilde{f}(x) - f(x)| \le \varepsilon_f \max(1, |f(x)|)$ 。
- 梯度假设：为了理论分析的简化，假设梯度 $\nabla f(x)$ 是精确计算的（或误差远小于停止准则容差），但在实验部分验证了算法在梯度也有噪声时依然有效。

2. 方法论：提出的算法

作者提出了一种噪声容忍的正则化拟牛顿法（Noise-Tolerant Regularized Quasi-Newton Method），其核心思想是结合正则化技术与无目标函数优化（OFFO）策略，在函数值可靠时利用线搜索，在噪声主导时切换到基于梯度的控制。

算法主要组件（Algorithm 1）：

正则化拟牛顿方向：
- 搜索方向 $d_k = -(B_k + \mu_k I)^{-1} g_k$ 。
- 其中 $B_k$ 是近似 Hessian 矩阵（基于 L-BFGS 更新）， $\mu_k \ge 0$ 是正则化参数。
- 正则化项 $\mu_k I$ 确保矩阵正定，从而保证 $d_k$ 是下降方向，即使在 Hessian 近似不准确时也能维持数值稳定性。
带误差吸收项的松弛 Armijo 线搜索（Algorithm 2）：
- 传统的 Armijo 条件要求 $f(x_k + \alpha d_k) \le f(x_k) + c \alpha g_k^T d_k$ 。
- 本文提出松弛条件： $f(x_k) + c \alpha g_k^T d_k + \Delta_k \ge f(x_k + \alpha d_k)$ 。
- 其中 $\Delta_k$ 是一个误差吸收项，根据当前的误差界 $\varepsilon_f$ 动态计算： $\Delta_k = \frac{2\varepsilon_f}{1-\varepsilon_f} \max(1, f(x_k), -f(x_k + \alpha d_k))$ 。
- 作用：允许函数值在噪声影响下出现暂时的“虚假”上升，只要上升幅度在误差范围内即可接受，从而避免算法因噪声而错误地拒绝有效步长。
自适应正则化参数更新策略：
- 算法根据迭代历史动态切换 $\mu_k$ $μ_{k}$ 的取值模式：
  - 模式 A ( $\mu_k = 0$ )：当观察到函数值有充分下降（即 $\min_{j \in K_0} (f(x_j) - \Delta_j) \ge f(x_k)$ ）时，保持 $\mu_k=0$ ，此时算法表现为标准的拟牛顿法，追求快速收敛。
  - 模式 B ( $\mu_k > 0$ )：当函数值未充分下降（可能受噪声主导）时，激活正则化。 $\mu_k$ 的更新借鉴了 AdaGrad-Norm 的思想：
    $\mu_k = \theta_k \sqrt{\varsigma + \sum_{j \in K_+, j \le k} \|g_j\|^2}$
    这种策略不依赖函数值，仅依赖梯度范数，因此在噪声环境下具有鲁棒性，能保证收敛到一阶驻点。

3. 理论贡献

全局收敛率：在假设目标函数下有界、L-光滑且 Hessian 近似一致有界的条件下，证明了该算法在噪声环境下达到一阶驻点的全局收敛率为 $O(1/\varepsilon^2)$ （即迭代复杂度为 $O(1/\varepsilon_{gtol}^2)$ ）。
理论分析难点突破：
- 证明了在 $\mu_k=0$ 的集合（ $K_0$ ）上，函数值的总下降量受初始差距和误差界控制。
- 证明了在 $\mu_k>0$ 的集合（ $K_+$ ）上，利用 AdaGrad-Norm 类型的分析工具，建立了梯度范数平方和的下界。
- 结合两者，推导出了统一的收敛界，表明即使存在非消失的数值噪声，算法依然能收敛。

4. 实验结果

作者在 CUTEst 基准测试集上进行了广泛的数值实验，对比了多种现有方法（包括标准 L-BFGS、正则化 L-BFGS、SciPy 实现、NTQN 等）。

实验设置：
- 人工噪声：在 64 位精度下人为添加均匀随机噪声。
- 低精度浮点运算：模拟 64-bit、32-bit 和 16-bit（半精度）环境。
- 评估指标：达到指定梯度容差所需的 Oracle 调用次数（函数 + 梯度评估）及计算时间。
主要发现：
1. 鲁棒性显著：在人工噪声（ $\varepsilon_f = 10^{-2}$ ）和低精度（32-bit, 16-bit）设置下，传统线搜索方法（如 SciPy L-BFGS-B）经常失败或表现极差，而提出的方法（Ours/Ours-MS）表现出极强的稳定性，解决了绝大多数问题。
2. 收敛速度：在标准 64 位无噪声或低噪声环境下，该方法保持了与标准 L-BFGS 相当的收敛速度，没有因为正则化机制而牺牲效率。
3. 计算成本：单次迭代的计算开销与标准方法相当，证明了算法的实用性。
4. 性能图谱（Performance Profiles）：在所有测试场景下，该方法在“解决问题比例”指标上均优于或持平于其他对比方法，特别是在噪声较大时优势明显。

5. 意义与结论

理论意义：填补了拟牛顿法在“不精确函数值”场景下的理论空白，证明了结合正则化和 OFFO 策略可以在噪声下保持 $O(1/\varepsilon^2)$ 的收敛率。
实际意义：
- 为低精度计算（如 AI 硬件中的 FP16/FP8 训练）提供了可靠的优化器选择。
- 适用于仿真优化、黑盒优化等函数评估本身带有噪声的领域。
- 提供了一种“自适应”机制：在数据可靠时利用二阶信息加速，在数据不可靠时自动退化为稳健的一阶正则化方法。
未来方向：包括局部收敛性分析、扩展到约束优化问题、以及在机器学习大规模训练中的具体应用。

总结：该论文提出了一种兼具理论保证和实用性的拟牛顿算法，成功解决了数值噪声导致传统优化方法失效的问题，是连接高精度优化理论与低精度/噪声实际应用场景的重要工作。