VR方法区别

VR方法性质

要求随着迭代次数的增加，梯度估计 $g_k$ 的方差逐渐收敛到0。即估计的梯度最终能够接近真实梯度。 $\lim_{k \rightarrow \infty}\mathbb{E}[\|g_k - \nabla f(x_k)\|^2] = 0$

常见VR方法

SAG

SAG方法希望得到全梯度的近似，是全梯度的有偏估计。近似方法如下： $g_k = \frac{1}{n} \sum_{i=1}^n v_k^i \approx \frac{1}{n} \sum_{i=1}^n \nabla f_i( x_k )$ 其中 $g_k$ 表示梯度，并且希望 $g_k$ 尽可能的接近 $\nabla f(x_k)$ 。这是 $v_k^i$ 的更新规则： $v_{k+1}^j = \begin{cases} \nabla f_{i_k}(x_k) & j = i_k \\ v_k^j & j \neq i_k \end{cases}$ 然而我们可以不用这么麻烦的每一次都将 $v_k^i$ 从1加到n，可以用如下式子简化计算： $\begin{align}g_k & = \frac{1}{n} \sum_{j=1, j \neq i_k}^n v_k^j + \frac{1}{n} v_k^{i_k} \\ &= \frac{1}{n} \sum_{j=1, j \neq i_k}^n v_{k-1}^j + \frac{1}{n} v_k^{i_k} \\ &= g_{k-1} - \frac{1}{n} v_{k-1}^{i_k} + \frac{1}{n} v_k^{i_k} \end{align}$
具体算法过程：

SAG算法

SAG方法相当于对n个数据维护一个表，每个表中存储这次迭代求的随机梯度。对于样本i来说，如果这次选到了样本i，则存的数据就是随机梯度，否则就保持不变。然后每次计算梯度时是对这张表中的梯度取平均，用以模拟全梯度，是全梯度的有偏估计。这种方法与GD相比可以减少计算量，但是却需要至少 $O(nd)$ ( $n$ 是数据量， $d$ 表示数据维度)的存储空间。而且这种方法分析非常困难，因此有人提出了更易于分析的SAGA。

SAGA

SAGA方法基于以下变换得到： $\begin{align} \frac{1}{n} \sum_{i=1}^n f_i(x) &= \frac{1}{n} \sum_{i=1}^n (f_i(x) - z_i(x) + z_i(x)) \\ &= \frac{1}{n}\sum_{i=1}^n (f_i(x) - z_i(x) + \frac{1}{n} \sum_{j=1}^n z_j(x)) \end{align}$ 因此 $g_k$ 可以取： $g_k = \nabla f_{i_k}(x_k) - \nabla z_{i_k}(x_k) + \frac{1}{n} \sum_{j=1}^n \nabla z_j(x_k)$ 而且只要 $\nabla z_{i_k}(x_k)$ 足够接近 $\nabla f_{i_k}(x_k)$ ， $g_k$ 最终就会收敛到 $\nabla f(x_k)$ ，即会满足VR性质。

SAGA使用如下形式的 $z_i(x)$ : $z_i(x) = f_i (\bar{x}_i) + \langle \nabla f_i(\bar{x}_i), x - \bar{x}_i\rangle$ 其中 $\bar{x}_i$ 是每一个样本 $i$ 的参考点。因此可得到梯度为： $g_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k}(\bar{x}_{i_k}^k) + \frac{1}{n} \sum_{j=1}^n \nabla f_j (\bar{x}_j^k)$ 每次在计算完梯度之后，需要用如下式子更新参考点 $\bar{x}_i$ : $\bar{x}_j^{k+1}= \begin{cases} \bar{x}_j^k & j = i_k \\ x_k & j \neq i_k \end{cases}$
具体算法过程：

SAGA算法

SAG和SAGA都需要的存储空间，对于大规模机器学习应用来说很不现实。因此有人提出了能达到相同收敛速度，但是只需要存储空间的SVRG方法。

SVRG

（以计算换存储）
SVRG中存在两个循环，其中外循环计算并存储全梯度 $\nabla f(\bar{x}_{s-1})$ ，在内循环中固定参考点 $\bar{x}_{s-1}$ ，更新 $x_k$ ，然后将内循环中更新得到的 $x_k$ 赋给 $\bar{x}_s$ 。由于不需要为每个样本存储一个参考点的随机梯度，因此存储空间只要 $O(d)$ 。

SVRG算法

其中SVRG还有很多变种
- 使用内循环迭代次数 $t$ 的替代分布，使 $t$ 无上限。
- 使用mini-batch的梯度近似全梯度 $\nabla f(\bar{x}_{s-1})$ ，然后每次迭代增加batch大小以满足VR性质
- 使用如下公式更新梯度： $g_k = \nabla f_{i_k}(x_k) - \nabla f_{i_k} (x_{k-1}) + g_{k-1}$
SAG，SAGA和SVRG均有 $O((\kappa_{max}+n)log(\frac{1}{\epsilon}))$ 的复杂度，其中 $\kappa:= L/\mu$ 为条件数。

SDCA（Stochastic dual coordinator）

最后编辑于：2020.05.16 09:40:19