SVRG算法的阅读理解和实践

最佳拜读了下大名鼎鼎的 SVRG 算法 [5]，读完后把前前后后涉及到的方法都看了一遍，这里做个简单的综述和阅读理解，并描述了如何将方差缩减思想应用于在线学习。

1. 背景介绍

考虑优化问题：

minRn(w)=1nn∑i=1fi(w)

当我们采用 Gradient Descent (GD) 方法时，w 的更新公式是：

wk+1=wk−ηk∇Rn(wk)=wk−ηknn∑i=1∇fi(wk)

梯度下降方法可以追溯到 Cauchy 1847 年的论文 [1]。梯度下降对于样本数目比较多的时候有一个很大的劣势，那就是每次需要求解所有样本的梯度，导致计算量大增，所以实际生产环境中，往往采用随机梯度下降算法（Stochastic Gradient Descent），一般简写做 SGD，它于 1951 和 1952 年在文献 [2,3] 中被提出。SGD 每次迭代的时候均匀随机得选择一个样本或者 mini-batch 做更新。当我们采用 SGD 方法来进行计算的时候，w 的更新公式是

wk+1=wk−ηk∇fik(wk)

相对于梯度下降，SGD 的好处非常明显，就是可以减少每次更新的计算代价，不过也正是因为每次都是随机的使用一个样本或一个 mini batch 来估计梯度，因此对梯度估计的方差就大了。这给 SGD 带来的问题是收敛速度不如梯度下降，从收敛速度分析上看，梯度下降则可以在目标函数强凸的情况下做到 O(ρT)(ρ<1) 的线性收敛（linear convergence），在目标函数为凸函数的情况下可以做到次线性收敛 O(1/T)（收敛速度是衡量优化算法计算复杂度的基本工具，可以参考 wiki 或者 这里）。而 SGD 能够在目标函数强凸并且递减步长的情况下只做到 O(1/T) 的次线性收敛（sublinear convergence）。也就是说，如果想快速得到一个可以勉强接受的解，SGD 比梯度下降更加合适，但是如果想得到一个精确度高的解，应当选择梯度下降，因为为了达到同样的精度，SGD 需要的总迭代次数要大于梯度下降。

至于为什么对梯度估计的方差过大会降低收敛速度，以及 SGD 为什么一定要步长递减，具体原因可参考文章 [4] 的 Theorem 4.6 和 Theorem 4.7 以及 Theorem 4.8，Theorem 4.9 和 Theorem 4.10，简单来说就是如果步长不是递减的，SGD 会收敛到最优解的一个领域中，对梯度估计的噪声让它最终无法进一步收敛。既然影响 SGD 收敛速度的主要原因之一是在所计算的梯度的方差，那就想办法降低这个方差，然后自然就可以提升算法的收敛速度了，这一类方法就被称为方差缩减方法（Noise Reduction Methods）。

2. 方差缩减方法 Noise Reduction Methods

在所谓的方差缩减方法中，又可以分为 3 小类，第一类动态采样方法（dynamic sampling methods）是通过在计算梯度时逐步增加样本量来减少梯度估计的方差；第二类迭代平均方法（iterate averaging methods）则是通过对得到的 w 进行历史平均来减少其方差；第三类梯度聚合方法（gradient aggregation methods）则是通过存储历史梯度，在每次估计梯度时用历史梯度来做修正，前两类方法太过暴力而不优雅，因此我们作为优雅的人主要讨论第三类方法。

我们先来直观的感受下什么叫方差缩减，比如你要通过 monte carlo 采样的方法来估计随机变量 X 的期望 EX，同时假设你已经能够比较容易地估计与随机变量 X 强相关的随机变量 Y 的期望 EY，一个利用方差缩减思想来近似估计 EX 的估计量 (estimator) 是：

θα=α(X−Y)+EY

我们可以看看这个估计量的期望和方差：

Eθα=αEX+(1−α)EYVar(θα)=α2[Var(X)+Var(Y)−2Cov(X,Y)]

可以发现，当 α=1 时，θα 是 EX 的无偏估计，且当 Cov(X,Y) 足够大的时候，θα 的方差也比直接对 X 做估计要来的小，这就是方差缩减的基本思想。后面要提到的各种方差缩减类算法比如大名鼎鼎的 SVRG 等都是这个套路，套路，套路。

3. SAG 算法 [10]

SAG 算法想啊，既然 GD 用上所有数据的梯度就能做到线性收敛，SGD 一次只能用一个样本或者一小批样本来计算梯度，因此对梯度估计的方差影响了最终的收敛速度，那我们能不能在 SGD 上也能用上所有样本的梯度呢？于是就有了 SAG 算法的更新方式：

wk+1=wk−ηknn∑i=1ykiyki={∇fi(wk),ifik=i∇fi(wk−1)otherwise

可以把上面的梯度计算方式写成一个式子

˜gk←∇fik(wk)−∇fik(wk−1)n+∇Rn(wk−1)

这样就容易看出这个方法就是上面 α=1/n 时的一个应用，虽然这种估计不是无偏估计，但是方差会以 1/n2 的比例缩小。这个方法理论上可以获得于 GD 方法同样的收敛速度。另外，在实践中，需要在内存里保存所有样本的上一次梯度值。

4. SVRG 算法 [5]

因为 SAG 算法需要保存所有样本的梯度值，在实际的大规模工业应用中并不实用，因此就有了 SVRG 算法。

SVRG 算法的迭代过程 (图片来自文章 [4])

SVRG 算法在每一轮迭代的内部有一个内部的迭代，在进行内部迭代前用当前的 wk 值计算一次所有样本的平均梯度 ∇Rn(wk)，内部迭代的初始值被赋予为当前的 wk，内部迭代中每次的梯度采用如下方式计算：

˜gj←∇fij(˜wj)−(∇fij(wk)−∇Rn(wk))

按照上文对方差缩减方法的描述，对此公式为什么能降低梯度估计的方差就可以有个直观的解释：因为 ∇fij(wk) 的期望就是 ∇Rn(wk)，因此可以将 (∇fij(wk)−∇Rn(wk)) 视为梯度估计 ∇fij(wk) 的 bias，那么在每一次的迭代中，算法都对基于当前参数 ˜wj 做的梯度估计 ∇fij(˜wj) 进行了一次修正。在 SGD 的收敛性分析中，假定了样本梯度的方差是有个常数上界的 (见文章 [4] 的 Assumption 4.3(c))，正是这个常数上界的存在导致 SGD 算法无法线性收敛，SVRG 利用它新的更新方式可以让估计的梯度方差有个不断减小的上界 (见文章 [4] 的 Theorem 5.1)，这就是 SVRG 算法的核心思想，这也是为什么这个算法被称为 SVRG（stochastic variance reduced gradient）的原因，SVRG 算法在目标函数光滑和强凸的情况下做到线性收敛速度。更多更为正式更为数学的分析可参考 bottou 大神写的综述文章 [4]。

SVRG 算法的问题是虽然不用存储所有样本的梯度了，但是计算量上去了，因为它在每次的大迭代里面还有一轮小迭代，每次都要算两遍梯度，整体的计算量已经和 GD 一样了，而且还多一个超参数 m 要调。另外，这里 有一个 PPT ，讲的还比较通俗，可以随意看看。

5. SAGA 算法 [6]

SAGA 算法其实是介于 SAG 和 SVRG 之间的一种算法，但作者声称在强凸的条件下其收敛速度要快于 SAG 和 SVRG，且两倍于 SDCA，并同时适用于非强凸的情形。

SAGA 算法的迭代过程 (图片来自文章 [4])

同样，如果我们仔细审视它的梯度计算过程：

˜gk←∇fik(wk)−∇fik(wk−1)+∇Rn(wk−1)

会发现，相比于 SAG 算法，SAGA 算法只是把前面的一个 1/n 去掉了，使得对梯度的估计变成无偏的了，当然同时它的方差相比于 SAG 也大了 n2。

6. SCSG 算法 [8]

SVRG 的主要特征就是利用全部数据的梯度来对 SGD 的方差进行控制。因此 SVRG 的计算成本（Computation Cost）是 O((n+m)T)。这里 n 是数据的总数，m 是 Step-size，而 T 是论数。SVRG 的通讯成本也是这么多，这里面的主要成本在于每一轮都需要对全局数据进行访问。

Stochastically Controlled Stochastic Gradient（SCSG）算法就是对 SVRG 进行了两个改进：

• 每一轮并不用全局的数据进行梯度的计算，而是从一个全局的子集 Batch 中估计梯度，子集的大小是 B。
• 每一轮 SGD 的更新数目 N 也不是一个定值，而是一个和之前那个子集大小有关系，基于 Geometric Distribution 的随机数。

剩下的更新步骤和 SVRG 一模一样。

然而，这样的改变之后，新算法的计算成本成为了 O((B+N)T)。也就是说，这是一个不依赖全局数据量大小的数值。而通过分析，作者们也比较了 SCSG 的通讯成本和一些原本就为了通讯成本而设计的算法，在很多情况下，SCSG 的通讯成本更优。通过 MNIST 数据集的实验发现，SCSG 达到相同的准确度，需要比 SVRG 更少的轮数，和每一轮更少的数据。可以说，这个算法可能会成为 SVRG 的简单替代。

7. 其它方法

有了套路，设计算法就 easy 多了，到目前为止已经有各种各样的 SVRG 类算法，除了下面列出的这些，还有朱泽园的 SVRG++，Alex 的 MSVRG 以及 Roy Frostig 的 streaming SVRG 等等。

S2GD(Semi-Stochastic Gradient Descent Methods)

Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting. 将S2GD扩展到mini-batch上，因此允许并行运行，但是需要更多的同步，只能允许小的batch

SDCA(Stochastic dual coordinate ascent methods for regularized loss) [7]

Finito(Finito: A faster, permutable incremental gradientmethod for big data problems)

8. 应用于在线学习

以上算法都只是适用于有限数据集的，我所关注的在线学习面临的是无限数据集，因此上述方法都不适用。但是有了上面的套路，我们也可以轻松地设计出适用在线学习的方差缩减方法，比如下面这个算法：

对上面 SSVRG-v1 算法做几点说明：

• gold 来自上一次的梯度，这里可以不要求是同一个 mini batch 的数据，其中的 wk 也可以是被其他 worker 更新后的值，因此，这个算法可以适用于多 worker 异步更新的场合，因为我们可以假设在很短的一个时间内，所有 worker 拿到的数据都是独立同分布的。
• 为了获得上文第二部分所说的 EY，也就是上文其他算法中的 ∇Rn(wk)，我们使用了一个滑动加权平均的方式，其中参数 d 是为了控制历史值与当前值的权重分配。

为什么我们还要指定学习率 η 和衰减系数 d 呢？已经有很多算法可以免去这两个超参数了，我们可以把他们的思想拿过来，和上面的算法进行综合，得到一个真正免超参，同时又能降低梯度估计方差，提升学习率的算法，这就是我们后续提出的 SSVRG-v2 算法，关于这个算法以及数学上的一些证明我们下一篇再写。

Reference

[1] Cauchy, Augustin. “Méthode générale pour la résolution des systemes d’équations simultanées.” Comp. Rend. Sci. Paris 25.1847 (1847): 536-538.

[2] Robbins, Herbert, and Sutton Monro. “A stochastic approximation method.” The annals of mathematical statistics (1951): 400-407.

[3] Kiefer, Jack, and Jacob Wolfowitz. “Stochastic estimation of the maximum of a regression function.” The Annals of Mathematical Statistics 23.3 (1952): 462-466.

[4] Bottou, Léon, Frank E. Curtis, and Jorge Nocedal. “Optimization methods for large-scale machine learning.” SIAM Review 60.2 (2018): 223-311.

[5] Johnson, Rie, and Tong Zhang. “Accelerating stochastic gradient descent using predictive variance reduction.” Advances in Neural Information Processing Systems. 2013.

[6] Defazio, Aaron, Francis Bach, and Simon Lacoste-Julien. “Saga: A fast incremental gradient method with support for non-strongly convex composite objectives.” Advances in Neural Information Processing Systems. 2014.

[7] Shalev-Shwartz, Shai, and Tong Zhang. “Accelerated mini-batch stochastic dual coordinate ascent.” Advances in Neural Information Processing Systems. 2013.

[8] Lei, Lihua, and Michael Jordan. “Less than a Single Pass: Stochastically Controlled Stochastic Gradient.” Artificial Intelligence and Statistics. 2017.

[9] Nitanda, Atsushi. “Stochastic proximal gradient descent with acceleration techniques.” Advances in Neural Information Processing Systems. 2014.

[10] Roux, Nicolas L., Mark Schmidt, and Francis R. Bach. “A stochastic gradient method with an exponential convergence _rate for finite training sets.” Advances in Neural Information Processing Systems. 2012.