8.6.3 BFGS

（\textbf{BFGS}）算法具有牛顿法的一些优点，但没有牛顿法的计算负担。 在这方面，BFGS\,和共轭梯度法很像。 然而，BFGS\,使用了一个更直接的方法近似牛顿更新。回顾牛顿更新由下式给出

$$\begin{aligned} \theta^* = \theta_0 - H^{-1} \nabla_{\theta} J(\theta_0), \end{aligned}$$

其中，$H$是$J$相对于$\theta$的\,Hessian\,矩阵在$\theta_0$处的估计。 运用牛顿法的主要计算难点在于计算\,Hessian\,逆$H^{-1}$。 拟牛顿法所采用的方法（BFGS\,是其中最突出的）是使用矩阵$M_t$近似逆，迭代地低秩更新精度以更好地近似$H^{-1}$。

BFGS\,近似的说明和推导出现在很多关于优化的教科书中，包括{Lue84}。

当\,Hessian\,逆的近似$M_t$更新时，下降方向$\rho_t$为$\rho_t = M_t g_t$。

[success] 第一项相当于$h^{-1}$ 第二项相当于$\nabla_{\theta} J(\theta_0)$

该方向上的线搜索用于决定该方向上的步长$\epsilon^*$。

[success] 牛顿法不需要自定义步长。

参数的最后更新为：

$$\begin{aligned} \theta_{t+1} = \theta_t + \epsilon^* \rho_t. \end{aligned}$$

和共轭梯度法相似，BFGS\,算法迭代一系列线搜索，其方向含二阶信息。 然而和共轭梯度法不同的是，该方法的成功并不严重依赖于线搜索找到该方向上和真正极小值很近的一点。 因此，相比于共轭梯度法，BFGS\,的优点是其可以花费较少的时间改进每个线搜索。 在另一方面，BFGS\,算法必须存储\,Hessian\,逆矩阵$M$，需要$O(n^2)$的存储空间，使\,BFGS\,不适用于大多数具有百万级参数的现代深度学习模型。

[success] 缺点：需要$O(n^2)$的存储空间 改进：L-BFGS

\paragraph{存储受限的\,BFGS（或\,L-BFGS）} 通过避免存储完整的\,Hessian\,逆近似$M$，BFGS\,算法的存储代价可以显著降低。 L-BFGS\,算法使用和\,BFGS\,算法相同的方法计算$M$的近似，但开始时假设上一步的$M$即$M^{(t-1)}$是单位矩阵，而不是每一步都为下一步存储近似。 如果使用精确的线搜索，L-BFGS\,定义的方向会是相互共轭的。 然而，不同于共轭梯度法，即使线搜索只是找到近似的极小值点，该过程的效果仍然不错。 这里描述的无存储的\,L-BFGS\,方法可以拓展为包含\,Hessian\,矩阵更多的信息，每步存储一些用于更新$M$的向量，且每步的存储代价是$O(n)$。

[warning] 最后几段没看懂