拟牛顿法是什么？不算海森矩阵也能享受二阶优化的好处

拟牛顿法（Quasi-Newton Method）是一类求解无约束优化问题的迭代算法。它的目标是在不直接计算二阶导数，也就是海森矩阵的情况下，获得接近牛顿法的快速收敛效果。它是数值优化中最重要、最常用的一类方法之一。

从梯度下降和牛顿法说起

梯度下降法只利用一阶导数，也就是梯度：每一步都沿着当前最陡的下坡方向走一小步。它简单，但收敛可能很慢，尤其是在函数的形状像一个狭长山谷的时候，会在山谷两侧来回震荡。牛顿法同时利用一阶导数和二阶导数：二阶导数组成的海森矩阵描述了函数在各个方向上的弯曲程度。牛顿法用一个二次函数在当前点附近近似原函数，然后直接跳到这个二次函数的最低点，相当于在弯曲剧烈的方向上走小步、在平缓的方向上走大步。在接近最优解时，牛顿法的收敛非常快。但它有明显的缺点：需要计算海森矩阵，当变量有 n 个时，海森矩阵有 n 乘 n 个元素，计算和存储的代价都很高；还需要对海森矩阵求逆，计算量大约与 n 的三次方成正比；而且如果海森矩阵不是正定的，牛顿法给出的方向可能不是下降的方向。

拟牛顿法的思路

拟牛顿法的核心想法是：不直接计算海森矩阵，而是利用每一步迭代中梯度的变化，逐步地“猜”出海森矩阵或者它的逆矩阵的近似值。依据是：在两个相邻的迭代点之间，梯度的变化量大约等于海森矩阵乘以位置的变化量，这叫拟牛顿条件或割线条件。每走一步，就用这一步的位置变化和梯度变化来更新对海森矩阵的近似，让它满足这个条件。随着迭代的进行，这个近似会越来越好，算法的表现也越来越接近牛顿法。拟牛顿法能够达到超线性的收敛速度，比梯度下降快得多，而每一步只需要计算梯度。同时，它的更新方式可以保证近似矩阵始终是正定的，从而保证每一步都朝着下降的方向前进。

代表性的算法

DFP 算法：由 William Davidon 在 1959 年提出，Roger Fletcher 和 Michael Powell 在 1963 年加以改进，是最早的拟牛顿法之一，直接近似海森矩阵的逆。BFGS 算法：1970 年，Charles Broyden、Roger Fletcher、Donald Goldfarb 和 David Shanno 四人几乎同时独立地提出了这一方法，名字取自四人姓氏的首字母。它在实践中比 DFP 更加稳定、效果更好，是最常用的拟牛顿法。L-BFGS 算法：由 Jorge Nocedal 在 1980 年提出的有限内存版本。BFGS 仍然需要存储一个 n 乘 n 的矩阵，当变量很多时也难以承受。L-BFGS 不存储完整的矩阵，只保存最近若干步，比如 5 到 20 步的位置变化和梯度变化，利用它们隐式地计算搜索方向，内存占用只与变量的数量成正比，因此可以处理有成千上万甚至上百万个变量的问题。

在机器学习中的应用

拟牛顿法，尤其是 L-BFGS，被广泛用于训练逻辑回归、最大熵模型、条件随机场等模型，scikit-learn 中逻辑回归的默认求解器就是 L-BFGS。它在需要精确求解的中等规模优化问题中非常高效，也常被用于科学计算、工程设计和统计模型的参数估计。在深度学习中，由于数据量巨大，训练通常使用小批量的随机梯度，而拟牛顿法依赖准确的梯度来估计曲率，在随机的、带噪声的梯度下效果会大打折扣，因此大规模的神经网络训练主要使用随机梯度下降和 Adam 等一阶方法。不过，研究者也在探索把二阶信息引入深度学习，比如 K-FAC、Shampoo 等方法，以及在神经风格迁移等全批量的小规模问题中使用 L-BFGS。