errorsk-4nQwBFp0LP8NpyK9WwwoT3BlbkFJyH23SKdFWR1P9Sr63sF8

阅读本文需要的背景知识点：对数几率回归算法（一）、共轭梯度法、一点点编程知识

一、引言

  接上一篇对数几率回归算法（一），其中介绍了优化对数几率回归代价函数的两种方法——梯度下降法（Gradient descent）与牛顿法（Newton's method）。但当使用一些第三方机器学习库时会发现，一般都不会简单的直接使用上述两种方法，而是用的是一些优化版本或是算法的变体。例如前面介绍的在 scikit-learn 中可选的求解器如下表所示：

求解器/solver	算法
sag	随机平均梯度下降法（Stochastic Average Gradient/SAG）
saga	随机平均梯度下降加速法（SAGA）
lbfgs	L-BFGS算法（Limited-memory Broyden–Fletcher–Goldfarb–Shanno/L-BFGS）
newton-cg	牛顿-共轭梯度法（Newton-Conjugate Gradient）

  下面就来一一介绍上述的这些算法，为什么一般第三方库中不直接梯度下降法与牛顿法，这两个原始算法存在什么缺陷？由于笔者能力有限，下面算法只给出了迭代公式，其迭代公式的来源无法在此详细推导出来，感兴趣的读者可参考对应论文中的证明。

二、梯度下降法

梯度下降法（Gradient Descent/GD）
  梯度下降原始算法，也被称为批量梯度下降法（Batch gradient descent/BGD），将整个数据集作为输入来计算梯度。

  该算法的主要缺点是使用了整个数据集，当数据集很大的时候，计算梯度时可能会异常的耗时。

随机梯度下降法（Stochastic Gradient Descent/SGD）
  每次迭代更新只随机的处理某一个数据，而不是整个数据集。

  该算法由于是随机一个数据点，代价函数并不是一直下降，而是会上下波动，调整步长使得代价函数的结果整体呈下降趋势，所以收敛速率没有批量梯度下降快。

小批量梯度下降法（Mini-batch Gradient Descent/MBGD）
  小批量梯度下降法结合了上面两种算法，在计算梯度是既不是使用整个数据集，也不是每次随机选其中一个数据，而是一次使用一部分数据来更新。

随机平均梯度下降法¹（Stochastic Average Gradient/SAG）
  随机平均梯度下降法是对随机梯度下降法的优化，由于SGD的随机性，导致其收敛速度较缓慢。SAG则是通过记录上一次位置的梯度记录，使得能够看到更多的信息。

方差缩减随机梯度下降法²（Stochastic Variance Reduced Gradient/SVRG）
  方差缩减随机梯度下降法是对随机梯度下降法的另一种优化，由于SGD的收敛问题是由于梯度的方差假设有一个常数的上界，SVRG的做法是通过减小这个方差来使得收敛过程更加稳定。

随机平均梯度下降法变体³（SAGA）
  SAGA是对随机平均梯度下降法的优化，结合了方差缩减随机梯度下降法的方法。

三、牛顿法

牛顿法（Newton Method）
  牛顿法原始版本，将整个数据集作为输入来计算出梯度和黑塞矩阵后求出下降的方向