如何理解SAG,SVRG,SAGA三种优化算法
最近在看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的区别就是一个是无偏估计，一个不是) 能说一下为什么SVRG是方差缩减的吗 SVRG虽然收敛速度是线性的，但是每轮都要算批梯度，这和BGD没什么两样，还多一个内层循环，等于说时间复杂度度甚至还要高于BGD。太鸡肋了。实在要说优点的话，就是不像BGD那样会陷入鞍点。 因为(\nabla f_{i_j}(w_{k})-\nabla R_{n}(w_{k}))这一步在减小方差。 请问一下，为什么saga是无偏估计，在多轮的迭代之后他还是无偏吗 对啊 我也很疑惑 既然每次循环一开始都要计算批梯度为什么不直接用GD.. 所以用得很少，无脑adam就完事了[捂脸]
页:
[1]