技术摘要：L-BFGS 逆海森矩阵近似的保护机制

1. 问题陈述

由于其 $O(mn)$ 的内存和计算复杂度，有限记忆 BFGS（L-BFGS）算法已成为大规模优化领域的标准方法。然而，在病态或非凸优化景观中，隐式逆海森近似矩阵（$H_k$）可能会遭受条件数爆炸（$\kappa(H_k) \to \infty$）的问题。这种数值不稳定性会导致收敛性能退化、搜索方向渐近正交于梯度，并可能导致算法失效（例如出现 NaN 错误）。

虽然标准的 L-BFGS 通常采用 Oren-Spedicato (OS) 缩放来调整初始海森近似，但仅靠这种缩放并不能防止条件数发散，特别是在梯度差向量 $y_k$ 相对于步长向量 $s_k$ 发生突然剧烈变化时。现有的保护措施（如 Li-Fukushima 谨慎更新规则）解决了曲率下界问题（防止 $y_k^T s_k \to 0$），但并未约束曲率尖峰的上界。

2. 方法论：双侧 L-BFGS

本文提出了双侧 L-BFGS，这是一种通过双侧几何包络线动态约束逆海森算子条件数的受保护变体。

核心机制

该算法通过过滤向量对 $(s_k, y_k)$ 的历史缓冲区来修改标准的 L-BFGS 更新过程。只有当一个向量对同时满足以下两个条件时，才会被接受进入深度为 $m$ 的记忆缓冲区：

1. 下界（Li-Fukushima 谨慎更新）：
   $$\frac{y_k^T s_k}{\|s_k\|^2} \geq \epsilon$$
   其中 $\epsilon > 0$。这确保了曲率不会消失，从而保持海森近似的正定性。

2. 上界（提出的保护措施）：
   $$\frac{\|y_k\|^2}{y_k^T s_k} \leq M$$
   其中 $M \gg 0$。这防止了爆炸性的曲率尖峰。从数学上看，由于 OS 缩放因子为 $\gamma_k = \frac{s_k^T y_k}{\|y_k\|^2}$，该条件等价于强制执行缩放参数的下限：$\gamma_k \geq \frac{1}{M}$。

算法实现

• 过滤： 在迭代过程中，如果新的 $(s_k, y_k)$ 对违反了 $\epsilon$ 或 $M$ 条件，则跳过更新。历史缓冲区保持不变，并沿用之前的有效 OS 缩放因子（$\gamma_k$）。
• 复杂度： 执行包络线检查仅需基础的向量点积和范数运算，每轮迭代增加 $O(n)$ 的计算开销。这严格受限于标准两循环递归的 $O(mn)$ 成本，从而保持了标准 L-BFGS 的整体时间与空间复杂度。

3. 主要贡献

理论保证

1. 条件数的一致上界：
   本文证明了对于任何迭代 $k$，逆海森近似的条件数 $\kappa(H_{k+1})$ 被一致地限制在一个有限常数 $\kappa_{max}$ 之内。

   • 利用迹-行列式引理（Byrd 和 Nocedal, 1989），作者推导出了一个依赖于问题维度 $n$、记忆深度 $m$ 以及包络参数 $\epsilon$ 和 $M$ 的显式界限。
   • 证明表明，$H_{k+1}$ 的特征值被限制在一个紧致区间 $[m_1, M_1]$ 内，确保矩阵既不会变得严格奇异，也不会产生无限大的病态程度。

2. 保持渐近全局收敛性：
   本文确立了双侧 L-BFGS 在非凸机制下保持了标准 L-BFGS 的渐近全局收敛特性。

   • 在标准假设（有界水平集和 $\beta$-Lipschitz 连续梯度）下，该算法满足 Zoutendijk 条件。
   • 至关重要的是，有界的条件数确保了搜索方向 $p_k$ 与梯度的正交性保持一致的界限（$\cos^2 \theta_k \geq 1/\kappa_{max}^2 > 0$）。
   • 因此，$\lim_{k \to \infty} \|\nabla f(x_k)\| = 0$，保证了收敛至一阶驻点。

数值实验

作者从三个方面验证了该方法：

1. 高维 Rosenbrock 函数： 展示了双侧 L-BFGS 如何保持有界的 $\kappa(H_k)$，并避免了在极端病态条件下标准 L-BFGS 中观察到的最优性间隙（$\|\nabla f(x_k)\|$）停滞现象。
2. CUTEst 基准测试 (DIXMAANA)： 表明受保护的方法相比标准 L-BFGS 显著减少了每次线搜索步骤的函数评估次数（通常减少 2–4 次），因为标准 L-BFGS 由于搜索方向对齐不良，往往需要大量的回溯。
3. MNIST 上的深度自动编码器： 证实了 $O(n)$ 的保护开销不会降低墙钟效率。事实上，通过消除由病态算子引起的线搜索瓶颈，该方法实现了更快的总收敛速度。

4. 重要性与主张

本文声称，双侧 L-BFGS 为非凸设置下 L-BFGS 的数值不稳定性提供了一个统一的解决方案，且不会牺牲理论收敛保证或计算效率。

• 鲁棒性： 通过主动约束几何包络线 $[\epsilon, M]$，该方法防止了导致标准 L-BFGS 在病态问题上失败的“最优性间隙扁平化”和数值溢出（NaN 错误）。
• 效率： 保护机制非常轻量。论文指出，检查包络线条件的微小成本，通过消除线搜索中昂贵的回溯循环，反而提升了墙钟性能。
• 理论严谨性： 不同于启发式的修改，该方法提供了严谨的证明，证明其条件数是统一有界的，并且全局收敛性得以保持，这与利用 Li-Fukushima 谨慎更新规则的 L-BFGS 变体具有相同的理论保证。

作者指出，性能取决于超参数 $\epsilon$ 和 $M$ 的选择。他们建议，过于激进的界限可能会导致算法跳过有效的更新，使其行为退化为标准梯度下降，并将自适应包络线缩放作为未来的研究方向。