- 1. 背景介绍
- 2. 方差缩减方法 Noise Reduction Methods
- 3. SAG 算法 [10]
- 4. SVRG 算法 [5]
- 5. SAGA 算法 [6]
- 6. SCSG 算法 [8]
- 7. 其它方法
- 8. 应用于在线学习
- Reference
最佳拜读了下大名鼎鼎的 SVRG 算法 [5]，读完后把前前后后涉及到的方法都看了一遍，这里做个简单的综述和阅读理解，并描述了如何将方差缩减思想应用于在线学习。
1. 背景介绍
考虑优化问题：
\[min \, R_n(w)=\frac{1}{n}\sum_{i=1}^{n}f_i(w)\]当我们采用 Gradient Descent (GD) 方法时，\(w\) 的更新公式是：
\[w_{k+1}=w_{k}-\eta_k\nabla R_n(w_{k})=w_{k}-\frac{\eta_k}{n}\sum_{i=1}^{n}\nabla f_{i}(w_{k})\]梯度下降方法可以追溯到 Cauchy 1847 年的论文 [1]。梯度下降对于样本数目比较多的时候有一个很大的劣势，那就是每次需要求解所有样本的梯度，导致计算量大增，所以实际生产环境中，往往采用随机梯度下降算法（Stochastic Gradient Descent），一般简写做 SGD，它于 1951 和 1952 年在文献 [2,3] 中被提出。SGD 每次迭代的时候均匀随机得选择一个样本或者 mini-batch 做更新。当我们采用 SGD 方法来进行计算的时候，\(w\) 的更新公式是
\[w_{k+1}=w_{k}-\eta_k\nabla f_{i_k}(w_{k})\]相对于梯度下降，SGD 的好处非常明显，就是可以减少每次更新的计算代价，不过也正是因为每次都是随机的使用一个样本或一个 mini batch 来估计梯度，因此对梯度估计的方差就大了。这给 SGD 带来的问题是收敛速度不如梯度下降，从收敛速度分析上看，梯度下降则可以在目标函数强凸的情况下做到 \(O(\rho^T) (\rho<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\) 的期望 \(\mathbb{E}X\)，同时假设你已经能够比较容易地估计与随机变量 \(X\) 强相关的随机变量 \(Y\) 的期望 \(\mathbb{E}Y\)，一个利用方差缩减思想来近似估计 \(\mathbb{E}X\) 的估计量 (estimator) 是：
\[\theta_{\alpha}=\alpha(X-Y)+\mathbb{E}Y\]我们可以看看这个估计量的期望和方差：
\[\mathbb{E}\theta_{\alpha}=\alpha\mathbb{E}X+(1-\alpha)\mathbb{E}Y \\ Var(\theta_{\alpha})=\alpha^2[Var(X)+Var(Y)-2Cov(X,Y)]\]可以发现，当 \(\alpha=1\) 时，\(\theta_{\alpha}\) 是 \(\mathbb{E}X\) 的无偏估计，且当 \(Cov(X,Y)\) 足够大的时候，\(\theta_{\alpha}\) 的方差也比直接对 \(X\) 做估计要来的小，这就是方差缩减的基本思想。后面要提到的各种方差缩减类算法比如大名鼎鼎的 SVRG 等都是这个套路，套路，套路。
3. SAG 算法 [10]
SAG 算法想啊，既然 GD 用上所有数据的梯度就能做到线性收敛，SGD 一次只能用一个样本或者一小批样本来计算梯度，因此对梯度估计的方差影响了最终的收敛速度，那我们能不能在 SGD 上也能用上所有样本的梯度呢？于是就有了 SAG 算法的更新方式：
\[w_{k+1}=w_k-\frac{\eta_k}{n}\sum_{i=1}^{n}y_i^{k} \\ y_i^{k}=\left\{ \begin{aligned} &\nabla f_i(w_k), \, &\text{if}\,i_k=i\\ &\nabla f_i(w_{k-1}) \, &\text{otherwise} \end{aligned} \right.\]可以把上面的梯度计算方式写成一个式子
\[\tilde g_k \, \leftarrow \, \frac{\nabla f_{i_k}(w_k) - \nabla f_{i_k}(w_{k-1})}{n} + \nabla R_n(w_{k-1})\]这样就容易看出这个方法就是上面 \(\alpha=1/n\) 时的一个应用，虽然这种估计不是无偏估计，但是方差会以 \(1/n^2\) 的比例缩小。这个方法理论上可以获得于 GD 方法同样的收敛速度。另外，在实践中，需要在内存里保存所有样本的上一次梯度值。
4. SVRG 算法 [5]
因为 SAG 算法需要保存所有样本的梯度值，在实际的大规模工业应用中并不实用，因此就有了 SVRG 算法。
SVRG 算法的迭代过程 (图片来自文章 [4])
SVRG 算法在每一轮迭代的内部有一个内部的迭代，在进行内部迭代前用当前的 \(w_k\) 值计算一次所有样本的平均梯度 \(\nabla R_n(w_k)\)，内部迭代的初始值被赋予为当前的 \(w_k\)，内部迭代中每次的梯度采用如下方式计算：
\[\tilde g_j \, \leftarrow \, \nabla f_{i_j}(\tilde w_j)-(\nabla f_{i_j}(w_k)-\nabla R_n(w_k))\]按照上文对方差缩减方法的描述，对此公式为什么能降低梯度估计的方差就可以有个直观的解释：因为 \(\nabla f_{i_j}(w_k)\) 的期望就是 \(\nabla R_n(w_k)\)，因此可以将 \((\nabla f_{i_j}(w_k)-\nabla R_n(w_k))\) 视为梯度估计 \(\nabla f_{i_j}(w_k)\) 的 bias，那么在每一次的迭代中，算法都对基于当前参数 \(\tilde w_j\) 做的梯度估计 \(\nabla f_{i_j}(\tilde w_j)\) 进行了一次修正。在 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])
同样，如果我们仔细审视它的梯度计算过程：
\[\tilde g_k \, \leftarrow \, \nabla f_{i_k}(w_k) - \nabla f_{i_k}(w_{k-1}) + \nabla R_n(w_{k-1})\]会发现，相比于 SAG 算法，SAGA 算法只是把前面的一个 \(1/n\) 去掉了，使得对梯度的估计变成无偏的了，当然同时它的方差相比于 SAG 也大了 \(n^2\)。
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 算法做几点说明：
- \(g_{old}\) 来自上一次的梯度，这里可以不要求是同一个 mini batch 的数据，其中的 \(w_k\) 也可以是被其他 worker 更新后的值，因此，这个算法可以适用于多 worker 异步更新的场合，因为我们可以假设在很短的一个时间内，所有 worker 拿到的数据都是独立同分布的。
- 为了获得上文第二部分所说的 \(\mathbb{E}Y\)，也就是上文其他算法中的 \(\nabla R_n(w_k)\)，我们使用了一个滑动加权平均的方式，其中参数 \(d\) 是为了控制历史值与当前值的权重分配。
为什么我们还要指定学习率 \(\eta\) 和衰减系数 \(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.