随机梯度下降 | 我爱机器学习

    随机梯度下降(Stochastic Gradient Descent, SGD)是 随机 和 优化 相结合的产物，是一种很神奇的优化方法，属于梯度下降的一种，适用于 大规模的问题 。
    要想扯清楚它，还得先谈谈梯度下降。众所周知，每个优化问题会有一个目标函数f(w)，梯度下降就是采用迭代的策略，从初始点w1开始，每次沿着目标函数在当前点的负梯度方向前进一定的步长，即

wt+1=wtηtf(wt)

只要步长ηt设置合理，这样可以得到一个单调递减的序列{f(w1),…,f(wt),…}，直至最终不再下降，即可得到最优解w。对于一般优化问题，梯度下降可以找到局部最优解，对于凸优化问题，梯度下降可以得到全局最优解，下面我们只考虑凸优化问题。
    考虑如下的目标函数

f(w)=∑i=1nf(w,xi)

其中xi是与w无关的常向量。当n为很大的正整数时，例如几十万甚至几百万时，计算梯度

f(w)=∑i=1nfi(w,xi)

代价很大，那么这个方法就行不通了。但是这样的问题在机器学习领域又很常见，比如感知机(Perceptron)，支持向量机(Support Vector Machine, SVM)，套索(Least Absolute Shrinkage and Selection Operator, LASSO)等算法都可以写成如下的形式

λΩ(w)+1n∑i=1nL(w,xi)

其中Ω(w)是关于w的凸正则化项，L(w,xi)是关于w的凸损失函数。因此我们需要克服梯度下降计算开销太大的问题，那么，随机梯度下降就呼之欲出了。
    随机梯度下降的基本想法很简单，就是不直接计算梯度的精确值，而是用梯度的 无偏估计 g(w)来代替梯度，即

wt+1=wtηtg(wt)

其中E[g(wt) | wt]=f(wt)。
    那么肯定有人要问，这么简单，靠不靠谱啊？可以证明的是在某些条件下，这样得到的序列{f(w1),…,f(wt),…}中的 最小值依期望收敛 到f(w)。具体来说，设

ηt≥0, ∑t=1∞η2t=||η||22<∞, ∑t=1∞ηt=∞

其中η=[η1,η2,…]是无穷维向量，并假设存在常数G和R满足，对于任意t有E[||g(wt)||22]≤G2，E[||w1w||22]≤R2，并记fbest(t)=min{f(w1),…,f(wt)}，那么当t→∞时，E[fbest(t)]→f(w)。
    结合条件期望的性质和f的凸性知

E[||wt+1w||22 | wt]=E[||wtηtg(wt)w||22 | wt]=E[||wtw||22 | wt]2ηtE[g(wt)(wtw) | wt]+η2tE[g(wt)2 | wt]=||wtw||222ηtE[g(wt) | wt](wtw)+η2tE[g(wt)2 | wt]=||wtw||222ηtf(wt)(wtw)+η2tE[g(wt)2 | wt]≤||wtw||222ηt(f(wt)f(w))+η2tE[g(wt)2 | wt]

两边同时对wt取期望，由重期望公式知

E[||wt+1w||22]≤E[||wtw||22]2ηt(E[f(wt)]f(w))+η2tG2

重复利用该式可得

E[||wt+1w||22]≤E[||w1w||22]2∑j=1tηj(E[f(wj)]f(w))+G2∑j=1tη2j

注意E[||wt+1w||22]≥0，E[||w1w||22]≤R2以及∑tj=1η2j≤||η||22，于是

2∑j=1tηj(E[f(wj)]f(w))≤R2+G2||η||22

结合E[fbest(t)]≤E[f(wj)]可知

E[fbest(t)]f(w)≤R2+G2||η||222∑tj=1ηj

由于∑∞t=1ηt=∞，故当t→∞时有E[fbest(t)]→f(w)。
    此外，由Markov不等式知对于>0有

P(fbest(t)f(w)≥)≤E[fbest(t)f(w)]≤R2+G2||η||222∑tj=1ηj

即当t→∞时有P(fbest(t)f(w)≥)→0。
    下面举几个机器学习里的具体例子，设训练集S有n个样本，即S={(x1,y1),(x2,y2),…,(xn,yn)}，由于有

Exi[L(w,xi)]=∑i=1n1nL(w,xi)=(1n∑i=1nL(w,xi))

成立，于是一个很直观的想法就是每次更新只随机选取一个样本xi来计算梯度。