如何理解SAG,SVRG,SAGA三种优化算法

ainatipen · 发表于 2022-11-16 21:46

最近在看Leon Bottou的大规模机器学习中的优化算法，发现里面有一些算法不太好理解，所以自己找了一些文章看了看，决定把SAG,SVRG,SAGA三种算法介绍一下。
对于这三种方法，我们主要目的是希望达到线性收敛的结果。
   我们都知道，在机器学习中，最常用的优化算法就是SGD(随机梯度下降算法)，我们发现它在但是SGD由于每次迭代方向都是随机选择的，所以产生了下降方向的噪音的方差。正是由于这个方差的存在，所以导致了SGD在每次迭代（使用固定步长 \alpha ）时，最终是收敛不到最优值的，最优间隔最终趋于一个和方差有关的定值。为了克服这一点，我们采取一种办法，是想要让方差呈递减趋势下降，那么最终算法的将会以线性速度收敛于最优值。下面这个定理时论文中的结果：

在这个定理中国，我们发现当下降方向的方差呈几何级数形式下降时，那么使用SGD最终结果是线性于最优值。

根据这个想法，我们主要有SAG,SVRG,SAGA三种最常用的算法。
一 . SVRG算法

我们首先来介绍SVRG(stochastic variance reduced gradient),该方法是在一个循环中进行的，在每次循环之前， w_{k} 可用于计算

然后我们初始化 \tilde{w_{1}} \leftarrow w_{k} ,然后进行一系列由j引导的m次内循环，它的更新格式是：

i_{j}\in\left\{ 1,2,3,... \right\} 是随机选取的，而且我们可以发现 \tilde{g_{j}} 是 \bigtriangledown{R}{\left(\tilde{w{j}}\right)} 的一个无偏估计，这样我们就可以和全梯度下降（GD）联系起来。方差会减小(在后面会说为什么)，所以最终该算法会以线性收敛到最优值。他的具体算法如下：

从算法过程来看，我们也很明显可以看到SVRG的计算量相比较SGD大得多，所以文中作者使用了相同的计算量的办法来比较SAG和SVRG算法的区别(就是说，在SGD和SVRG同时都计算了相同次，来看它们各自算法的优越），我们有如下图：

主要观看图a和图c，很明显SVRG相对于SGD来说在最优值附近几乎没有震荡，既没有噪音，但是SGD在最优值附近震荡明显。而且在图c中，可以看到SVRG下降方向的方差最终趋于零，明显比SGD小。
二 . SAG算法

提出SAG（Stochastic Average Gradient）主要是它既有SGD算法计算量小的特点，又具有像FGD一样的线性收敛速度。它的一般形式如下：

这里的 y_{k}^{i} 是方向，其中中每次迭代中任意选取 i_{k}\in\left\{ 1,2,... \right\} ，我们有：

这样，我们可以看到，每次迭代时，通过访问 i_{k}  并为每个索引i保留最近计算出的梯度值的储存，具体算法如下：(我们令 d=\Sigma y_{i} )

（加一下自己的理解，SAG就是一开始我们先在 x^{0} 处计算每个梯度( \triangledown f_{i} \left( x^{0} \right) ),  一共有n个，然后把这n个梯度全部存储到计算机中。在每次迭代时，我们随机选i，然后对于内存里面第i个样本的损失函数 f_{i}(x) ,我们计算出 \triangledown f_{i} \left( x\right) ，使用它替换掉原来位置 i 的梯度  ，然后我们就很好的解释了公式 d = d-y_{i} + \triangledown f_{i}(x) .它有点像SGD，但是每次计算中我们需要涉及到两个梯度，而且都将新计算出来的梯度取代原来相同位置的梯度，并且保存该梯度。）
   对于SAG，我们并没有实际理论说明它降低了方差，但是我们有理论证明它在步长 \alpha = \frac{1}{16L} 时线性收敛于最优值。
三 . SAGA算法

   SAGA算法是SAG算法的一个加速版本，和SAG一样，它既不在一个循环里面操作，也不计算批量梯度(除了在初始点)，在每次迭代中，它都计算随机向量 g_{k} 作为前期迭代中随机梯度的平均值。
特别的，在迭代k次中，算法将会存储 \triangledown f_{i}\left( w_{\left[ i \right]} \right) ,对于前期所有的 i \in \{{1,2,3...}\} ,其中 w_{\left[ i \right]} 表示 \triangledown f_{i} 计算出的最近的一次迭代。整数 j \in \{{1,2,3...}\} 是任意选取的。并且随机方向为：

看 g_{k} 的结构,也可以发现他也是 \triangledown R_{n}\left( w_k \right) 的一个无偏估计。而且每次都需要存储n个梯度。他的具体算法如下：

SAGA也减少了噪音的影响。(SAGA和SAG的区别就是一个是无偏估计，一个不是)

zt3ff3n · 发表于 2022-11-16 21:54

能说一下为什么SVRG是方差缩减的吗

maltadirk · 发表于 2022-11-16 21:57

SVRG虽然收敛速度是线性的，但是每轮都要算批梯度，这和BGD没什么两样，还多一个内层循环，等于说时间复杂度度甚至还要高于BGD。太鸡肋了。实在要说优点的话，就是不像BGD那样会陷入鞍点。

fwalker · 发表于 2022-11-16 22:04

因为(\nabla f_{i_j}(w_{k})-\nabla R_{n}(w_{k}))这一步在减小方差。

DomDomm · 发表于 2022-11-16 22:13

请问一下，为什么saga是无偏估计，在多轮的迭代之后他还是无偏吗

Zephus · 发表于 2022-11-16 22:20

对啊我也很疑惑既然每次循环一开始都要计算批梯度为什么不直接用GD..

RhinoFreak · 发表于 2022-11-16 22:24

所以用得很少，无脑adam就完事了[捂脸]

		自动登录	找回密码
密码			立即注册

如何理解SAG,SVRG,SAGA三种优化算法

本帖子中包含更多资源