前言: 本文从优化的角度整理了随机梯度法中的常用的一类算法: 噪声缩减方法, 这里的噪声指的是对随机样本计算梯度带来的噪声. 主要参考了Léon Bottou的综述Optimization Methods for Large-Scale Machine Learning、Jorge Nocedal的Numerical Optimization(2nd edition)以及这篇博客.
机器学习中的优化
一些记号
首先给出两个基本记号, 这是机器学习中要考虑的两种优化基本函数, 前者是定义在\(n\)个样本上的函数, 而后者是定义在样本的概率空间上的函数.
- \(R_n(w)=\frac{1}{n}\sum_{i=1}^nf_i(w)\)表示经验风险.
- \(R(w)=\mathbb{E}[f(w;\xi)]\)表示期望风险.
而关于最优解\(w\)有三种:
- 第一种是\(w_{*}\in \arg\min R(w)\).
- 第二种是\(w_{n}\in \arg\min R_n(w)\).
- 第三种是实际运行算法返回的最优解\(\tilde{w}_n\), 其受制于具体优化算法的计算.
注意: 下面用\(F(w)\)表示\(R_n(w)\)或者\(R(w)\), 意在区分只适用\(R_n(w)\)和\(R_n(w), R(w)\)均适用的算法
梯度下降法
梯度下降法(gradient descent, GD), 只适用于\(R_n(w)\), 在强凸前提下其收敛速度为线性[Numerical Optimization TH3.4]:\[R_n(w_k)-R_*\le O(\rho^k)\]其中\(\rho\in(0,1)\). 因此GD的计算复杂度为:\[O(n\kappa\log(1/\epsilon))\]因为\(O(\rho^k)=\epsilon \Rightarrow k=O(\log(1/\epsilon))\)且每次迭代要计算\(n\)个样本的梯度.
注意: \(\kappa=L/\mu\)为优化中常用的常数, 类比于二次情形的条件数. 可参见[leon bottou]中的Assumption4.1 4.3
随机梯度
随机梯度(stochastic gradient, SG), 为梯度下降法的随机版本, 但因为每次迭代不能保证下降, 因此没有descent的字眼, 它是适用于\(F(w)\)的算法. 在强凸(步长满足\(\alpha_k=\frac{\beta}{\gamma+k}\))及期望的意义下其收敛速率为次线性[leon bottou TH4.7] :\[\mathbb{E}[F(w_k)-F_*]\le \frac{\nu}{\gamma+k}\]其中\(\beta, \nu\)为常数. 因此SG的计算复杂度为:\[O(\kappa/\epsilon)\]因为\(\frac{\nu}{\gamma+k}=\epsilon \Rightarrow k=\frac{\nu}{\epsilon}-\gamma\)
噪声减小方法
迭代平均方法
先来看最容易想到的一类方法, 迭代平均方法, 它直接基于SG因此适用\(F(w)\). 考虑SG迭代序列\[w_{k+1}\leftarrow w_k-\alpha_k g(w_k,\xi_k)\]这里的\(\xi_k\)为随机变量, 指代第\(k\)步随机抽取的样本, \(g(w_k,\xi_k)\)表示样本\(\xi_k\)对应的梯度. 迭代平均法新建了一个序列:\[\tilde{w}_{k+1}\leftarrow \frac{1}{k+1}\sum_{j=1}^{k+1}w_{j}\]若步长衰减速度为\(O(1/k^a)\), \(a\in(\frac{1}{2},1)\). 在强凸的前提下有:\[\mathbb{E}[\Vert w_k-w_+\Vert_2^2] = O(1/k^a)\]且(注:这里的\(w_+\)指\(w\)的最优值点)\[\mathbb{E}[\Vert \tilde{w}_k-w_+\Vert_2^2] = O(1/k)\]
动态样本大小方法
动态样本大小方法同样直接基于SG因此适用\(F(w)\). 下面介绍一个核心的结果, 简言之就是, 若能把每步迭代的方向的方差控制住:\[\mathbb{V}_{\xi_k}[g(w_k, \xi_k)]\le M \zeta^{k-1}\]在强凸(步长固定)的前提下, 可得到线性收敛[leon bottou TH5.1]:\[\mathbb{E}[F(w_k)-F_*]\le \omega\rho^{k-1}\]其中\(\rho<1, \omega\)为常数. 再结合统计中的一个结果: \(n_k\)个独立同分布样本的方差为单个样本的方差的\(1/n_k\). 因此只需要动态改变每次迭代所用样本个数, 使其控制在定理条件下\[\mathbb{V}_{\xi_k}[g(w_k, \xi_k)]\le\frac{C}{n_k}\le M\zeta^{k-1}\Rightarrow n_k\ge\frac{C}{M}(\frac{1}{\zeta})^{k-1}\](这里假定所有样本的梯度的方差有一致的上界, 记为\(C\)) 就能得到线性收敛的结果. 然而虽有线性收敛的速度, 但每次迭代所需样本也是指数级增长, 因此动态样本大小方法的计算复杂度为[leon bottou TH5.3]:\[O(1/\epsilon)\]由于样本集是有限的, 在某一步中必然会出现样本不够用的情况, 一种可行的做法是转而要求每步迭代的方向产生了足够多的下降, 而不管上述样本量指数级增长的要求.
梯度聚合
这类方法着重于利用先前迭代中计算得到的样本的梯度信息, 其包括SVGR、SAG/SAGA等.
SVRG
SVGA只适用于\(R_n(w)\). 如上图算法所示, 相比SG, SVGA多了抽取\(m\)个样本的内层循环, 再用内层循环产生的子序列\(\{\tilde{w}_j\}\),\({j=1,...,m}\)去生成高质量的\(w_{k+1}\), 方式比如说(a),(b),(c). 核心式子为:\[\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))\)可视为从单个样本\(i_j\)到\(n\)个样本的修正, 因此\(\tilde{g}_j\)可近似视为\(\nabla R_n(\tilde{w}_j)\).
- 若\(m\)取的不是特别大, \(\nabla f_{i_{j}}(\tilde{w}_j)\)显然与\(\nabla f_{i_{j}}(w_k)\)强相关, 而\(\nabla f_{i_{j}}(w_k)\)的期望恰为\(\nabla R_n(w_k)\), 此时上述形如\[\tilde{g}_j\leftarrow X-(Y-\mathbb{E}[Y])\]此时\(\mathbb{E}[\tilde{g}_j]=\mathbb{E}[X]\), \(\mathbb{V}[\tilde{g}_j]=\mathbb{V}[X]+\mathbb{V}[Y]-2Cov(X, Y)\). 再加上强相关的假设, 确实能取到Variance Reduced(VR)的效果, SVRG原论文在Experiments中说明了这一点.
在强凸前提下其收敛速度为线性[SVRG TH1]\[\mathbb{E}[R_n(w_{k})-R_*]\le\omega\rho^{k-1}\]其中\(\rho\in(0,1)\). SVRG的计算复杂度为:\[O((n+\kappa)\log(1/\epsilon))\]
SAGA/SAG
SAGA只适用于\(R_n(w)\), 显然算法部分第一块为初始化所有样本梯度值并存储, 第二个循环才是算法循环. 其中\(\nabla f_j(w_{[j]})\)表示第\(j\)个样本最近一次存储着的梯度值. 比如说对于第\(1\)个样本, 初始化时\(\nabla f_1(w_{[1]})\leftarrow \nabla f_1(w_{1})\), 剩下涉第\(1\)个样本的梯度的更新就只有靠算法循环中的Choose j uniformly in {1,...,n}抽到再用\(\nabla f_1(w_k)\)更新. 因此可以看出, SAGA本着能不计算梯度就不计算的原则(每步迭代只计算一个样本的梯度, 从这个角度看更接近SG), 而其核心式子为:\[g_k\leftarrow \nabla f_{j}(w_k)-\nabla f_{j}(w_{[j]})+\frac{1}{n}\sum_{i=1}^n\nabla f_i(w_{[i]})\]它同样可以从两个角度去理解:
- \(\nabla f_{j}(w_{[j]})-\frac{1}{n}\sum_{i=1}^n\nabla f_i(w_{[i]})\)视为单样本到\(n\)个样本的修正, \(g_k\)可近似视为\(\nabla R_n(w_k)\).
- \(\nabla f_{j}(w_{[j]})\)的期望为\(\frac{1}{n}\sum_{i=1}^n\nabla f_i(w_{[i]})\), 但\(\nabla f_{j}(w_k)\)与\(\nabla f_{j}(w_{[j]})\)未必强相关.
SAGA起源自SAG, 它们唯一的不同在于核心式子, SAG的核心式子如下:\[g_k\leftarrow \frac{1}{n}(\nabla f_{j}(w_k)-\nabla f_{j}(w_{[j]})+\sum_{i=1}^n\nabla f_i(w_{[i]}))\]与SAGA不同的是, 此时\(g_k\)不是\(\nabla R_n(w_k)\)的无偏估计.在强凸前提下, SAGA与SAG均能线性收敛, 且计算复杂度与SVRG一样均为:\[O((n+\kappa)\log(1/\epsilon))\]
其它
SARAH
SARAH只适用于\(R_n(w)\), 它与SVGR一样有内圈循环, 不同的是核心迭代式子中把\(\nabla R_n(w_k)\)替换成了上一步的迭代方向. 且此时无偏性不再保持. 在强凸前提下, SARAH线性收敛 且计算复杂度与SVRG一样均为:\[O((n+\kappa)\log(1/\epsilon))\]注意到SARAH与SVRG中的\(m\)均为超参, SARAH原论文中还提出了以\(\Vert v_{t-1}\Vert_2^2\le\gamma \Vert v_0\Vert_2^2\)为内圈循环停止条件的实用版算法SARAH+. 