type
Post
status
Published
date
May 11, 2018
slug
2018.05.11 SVRG算法的阅读理解和实践
summary
2018.05.11 SVRG算法的阅读理解和实践
tags
算法
推荐
优化算法
category
算天算地系列
icon
password
最近拜读了下大名鼎鼎的 SVRG 算法 [5],读完后把前前后后涉及到的方法都看了一遍,这里做个简单的综述和阅读理解,并描述了如何将方差缩减思想应用于在线学习。
1. 背景介绍
考虑优化问题:
当我们采用 Gradient Descent (GD) 方法时,w 的更新公式是:
梯度下降方法可以追溯到 Cauchy 1847 年的论文 [1]。梯度下降对于样本数目比较多的时候有一个很大的劣势,那就是每次需要求解所有样本的梯度,导致计算量大增,所以实际生产环境中,往往采用随机梯度下降算法(Stochastic Gradient Descent),一般简写做 SGD,它于 1951 和 1952 年在文献 [2,3] 中被提出。SGD 每次迭代的时候均匀随机得选择一个样本或者 mini-batch 做更新。当我们采用 SGD 方法来进行计算的时候,w 的更新公式是
相对于梯度下降,SGD 的好处非常明显,就是可以减少每次更新的计算代价,不过也正是因为每次都是随机的使用一个样本或一个 mini batch 来估计梯度,因此对梯度估计的方差就大了。这给 SGD 带来的问题是收敛速度不如梯度下降,从收敛速度分析上看,梯度下降则可以在目标函数强凸的情况下做到 的线性收敛(linear convergence),在目标函数为凸函数的情况下可以做到次线性收敛 (收敛速度是衡量优化算法计算复杂度的基本工具,可以参考 wiki 或者 这里)。而 SGD 能够在目标函数强凸并且递减步长的情况下只做到 的次线性收敛(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)则是通过对得到的 进行历史平均来减少其方差;
- 第三类梯度聚合方法(gradient aggregation methods)则是通过存储历史梯度,在每次估计梯度时用历史梯度来做修正,前两类方法太过暴力而不优雅,因此我们作为优雅的人主要讨论第三类方法。
我们先来直观的感受下什么叫方差缩减,比如你要通过 monte carlo 采样的方法来估计随机变量 的期望 ,同时假设你已经能够比较容易地估计与随机变量 强相关的随机变量 的期望 ,一个利用方差缩减思想来近似估计 的估计量 (estimator) 是:
我们可以看看这个估计量的期望和方差:
可以发现,当 时, 是 的无偏估计,且当 足够大的时候, 的方差也比直接对 做估计要来的小,这就是方差缩减的基本思想。后面要提到的各种方差缩减类算法比如大名鼎鼎的 SVRG 等都是这个套路,套路,套路。
3. SAG 算法 [10]
SAG 算法想啊,既然 GD 用上所有数据的梯度就能做到线性收敛,SGD 一次只能用一个样本或者一小批样本来计算梯度,因此对梯度估计的方差影响了最终的收敛速度,那我们能不能在 SGD 上也能用上所有样本的梯度呢?于是就有了 SAG 算法的更新方式:
可以把上面的梯度计算方式写成一个式子
这样就容易看出这个方法就是上面 时的一个应用,虽然这种估计不是无偏估计,但是方差会以 的比例缩小。这个方法理论上可以获得于 GD 方法同样的收敛速度。另外,在实践中,需要在内存里保存所有样本的上一次梯度值。
4. SVRG 算法 [5]
因为 SAG 算法需要保存所有样本的梯度值,在实际的大规模工业应用中并不实用,因此就有了 SVRG 算法。SVRG 算法的迭代过程 (图片来自文章 [4])
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2F47d0e971-7e51-451d-abcf-89ba612744ee%2FUntitled.png%3Ftable%3Dblock%26id%3D1360ca7b-35ef-4acd-88fc-52f44bb9bcd2%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725717600000%26signature%3DW_OMXWk1j77CxALa2FBYrq20Dcr4u1ZkAVGYjDi5vb4?table=block&id=1360ca7b-35ef-4acd-88fc-52f44bb9bcd2&cache=v2)
SVRG 算法在每一轮迭代的内部有一个内部的迭代,在进行内部迭代前用当前的 值计算一次所有样本的平均梯度 ,内部迭代的初始值被赋予为当前的 ,内部迭代中每次的梯度采用如下方式计算:
按照上文对方差缩减方法的描述,对此公式为什么能降低梯度估计的方差就可以有个直观的解释:因为 的期望就是 ,因此可以将 视为梯度估计 的 bias,那么在每一次的迭代中,算法都对基于当前参数 做的梯度估计 进行了一次修正。在 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])
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Fab8376c4-fd09-4b49-bf01-05988df4b184%2FUntitled.png%3Ftable%3Dblock%26id%3D1809b5e2-5031-4ae9-bc0c-963a8b0ec411%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725717600000%26signature%3Dt0xIeQ8kbk1OLa7t1h1GdP4BVSWYRF7t5gN7wcQ5hlI?table=block&id=1809b5e2-5031-4ae9-bc0c-963a8b0ec411&cache=v2)
同样,如果我们仔细审视它的梯度计算过程:
会发现,相比于 SAG 算法,SAGA 算法只是把前面的一个 去掉了,使得对梯度的估计变成无偏的了,当然同时它的方差相比于 SAG 也大了 。
6. SCSG 算法 [8]
SVRG 的主要特征就是利用全部数据的梯度来对 SGD 的方差进行控制。因此 SVRG 的计算成本(Computation Cost)是 。这里 n 是数据的总数,m 是 Step-size,而 T 是论数。SVRG 的通讯成本也是这么多,这里面的主要成本在于每一轮都需要对全局数据进行访问。
Stochastically Controlled Stochastic Gradient(SCSG)算法就是对 SVRG 进行了两个改进:
- 每一轮并不用全局的数据进行梯度的计算,而是从一个全局的子集 Batch 中估计梯度,子集的大小是 B。
- 每一轮 SGD 的更新数目 N 也不是一个定值,而是一个和之前那个子集大小有关系,基于 Geometric Distribution 的随机数。
剩下的更新步骤和 SVRG 一模一样。然而,这样的改变之后,新算法的计算成本成为了 。也就是说,这是一个不依赖全局数据量大小的数值。而通过分析,作者们也比较了 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. 应用于在线学习
以上算法都只是适用于有限数据集的,我所关注的在线学习面临的是无限数据集,因此上述方法都不适用。但是有了上面的套路,我们也可以轻松地设计出适用在线学习的方差缩减方法,比如下面这个算法:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fafdd680a-876e-4511-91a1-e1f4fcf8337b%2Fb4fd4b52-bf07-4e56-bd9c-a1b3dac8e27b%2FUntitled.png%3Ftable%3Dblock%26id%3Dcd3665ef-d7ef-4cc7-93c3-1f54d3073d75%26spaceId%3Dafdd680a-876e-4511-91a1-e1f4fcf8337b%26expirationTimestamp%3D1725717600000%26signature%3DAjqVXbj_F4KXelj-V1pqLxlAZ7iH7RJDw2hNAm7HO98?table=block&id=cd3665ef-d7ef-4cc7-93c3-1f54d3073d75&cache=v2)
对上面 SSVRG-v1 算法做几点说明:
- 来自上一次的梯度,这里可以不要求是同一个 mini batch 的数据,其中的 也可以是被其他 worker 更新后的值,因此,这个算法可以适用于多 worker 异步更新的场合,因为我们可以假设在很短的一个时间内,所有 worker 拿到的数据都是独立同分布的。
- 为了获得上文第二部分所说的 ,也就是上文其他算法中的 ,我们使用了一个滑动加权平均的方式,其中参数 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.