CXQ free your mind

SVRG算法的阅读理解和实践

2018-05-11
caoxiaoqing

最佳拜读了下大名鼎鼎的 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算法

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])

saga算法

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

\[\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. 应用于在线学习

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

online SVRG算法

对上面 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.


Similar Posts

Comments