随机梯度下降(Stochastic Gradient Descent)是在处理大规模优化问题的折衷手段。本来对于优化问题的普适解法是梯度下降(Gradient Descent)，通过每次对目标函数在负梯度上进行迭代下降从而渐进的得到最优解。简单而又直观的来说：假设目标函数为\(\boldsymbol{f(w)}\)，且该函数是凸函数(convex function)，则梯度下降有如下形式
\begin{equation}{w}_{t+1} = {w}_t - \eta_t \nabla f({w}_t)\end{equation}
即每次在\({w}\)处，在负梯度\(-\nabla f({w}_t)\)方向上行进\(\eta _t\)个单位。在合理设置步长\(\eta _t\)时，可以得到一个收敛的序列\(\{f({w}_1), \ldots, f({w}_t), \ldots \}\)，以任意精度逼近最优解\(\boldsymbol{f({w}^*)}\)。
梯度下降最重要的部分就是计算梯度\(\nabla f({w}_t)\)，但是该梯度的计算在大数据量的情况下是不可行的：计算梯度所依赖的内存太大，计算梯度的复杂度太高。例如下面的目标函数：
\begin{equation}f({w}) = \sum_{i=1}^n L({w}, \boldsymbol{x}_i)\end{equation}
为了计算该函数的梯度，我们需要计算下面的式子：
\begin{equation}\nabla f({w}) = \sum_{i=1}^n\nabla L({w}, \boldsymbol{x}_i)\end{equation}
当\(n\)的数量级非常大时，就会造成内存无法存储所有数据的情况，同时一次完整的计算代价太大。因此，只能选取随机梯度下降的方法。
所谓随机梯度，就是以随机采样到的单个数据来当作全体数据，进行梯度计算。即以下面的方式来迭代：
\begin{equation}{w}_{t+1} = {w}_t - \eta_t g({w}_t)\end{equation}
其中\(g({w})\)是单个数据点计算而来的随机梯度，该随机梯度是全局梯度的无偏估计：
\begin{equation}\mathbb{E} [ g({w}_t) \ | \ {w}_t] = \nabla f({w}_t)\end{equation}
但是，在随机下降方法上所得到的搜索序列\(\{f({w}_1), \ldots, f({w}_t), \ldots \}\)会跟梯度下降一样收敛到最优值\(f^*({w})\)么？
既然你诚心诚意的问了，那我就发发慈悲告诉你们吧。会，但是有一些前提条件：
\begin{equation}\eta_t \geq 0, \ \sum_{t=1}^\infty \eta_t^2 = ||\boldsymbol{\eta}||_2^2 < \infty, \ \sum_{t=1}^\infty \eta_t = \infty\end{equation}
同时，对于任意的\(t\)，我们还要求存在常数\(G,R\)，使得：
\begin{equation}\mathbb{E}[||{w}_1 - {w}^*||_2^2] \leq R^2 \quad \mathbb{E}[||g({w}_t)||_2^2] \leq G^2\end{equation}
此时，我们可以证明序列\(f_{best}(t) = \min \{f({w}_1), \ldots, f({w}_t)\}\)会依概率收敛到\(f({w}^*)\)：
\begin{equation}P(f_{best}(t) - f({w}^*) \geq \epsilon) \rightarrow 0\end{equation}
依照期望的性质，我们可以得到下面的等式：
\begin{equation}\begin{split}&\mathbb{E}[{\Vert w_{t+1}-w^*\Vert}_2^2|w_t]\\=&\mathbb{E}[{\Vert w_t-\eta_tg(w_t)-w^*\Vert}_2^2|w_t]\\=&\mathbb{E}[{\Vert w_t-w^*\Vert}_2^2|w_t]-2\eta_t\mathbb{E}[g(w_t)^T(w_t-w^*)|w_t]+\eta_t^2\mathbb{E}[g(w_t)^2|w_t]\\=&\Vert w_t -w^*\Vert_2^2-2\eta_t\mathbb{E}[g(w_t)^T|w_t](w_t-w^*)+\eta_t^2\mathbb{E}[g(w_t)^2|w_t]\\=&\Vert w_t -w^*\Vert_2^2-2\eta_t\nabla f(w_t)(w_t-w^*)+\eta_t^2\mathbb{E}[g(w_t)^2|w_t]\\\end{split}\end{equation}
此时，根据凸函数的性质，我们有：
\begin{equation}f(a)-f(b)\geq\nabla f(b)(a-b)\Rightarrow f(w^*)-f(w_t)\geq\nabla f(w_t)(w^*-w_t)\end{equation}
所以
\begin{equation}\mathbb{E}[{\Vert w_{t+1}-w^*\Vert}_2^2|w_t]\leq \Vert w_t -w^*\Vert_2^2-2\eta_t (f(w_t)-f(w^*))+\eta_t^2\mathbb{E}[g(w_t)^2|w_t]\end{equation}
上式的两边同时对\(w_t\)取期望，可以得到：
\begin{equation}\mathbb{E}[{\Vert w_{t+1}-w^*\Vert}_2^2]\leq \mathbb{E}[{\Vert w_t-w^*\Vert}_2^2]-2\eta_t (f(w_t)-f(w^*))+\eta_t^2G^2\end{equation}
可以看出，上面的公式有一个递归部分。我们对这个递归部分重复利用，可以得到：
\begin{equation}\mathbb{E}[{\Vert w_{t+1}-w^*\Vert}_2^2]\leq \mathbb{E}[{\Vert w_1-w^*\Vert}_2^2]-2\sum_{j=1}^t{\eta_j (f(w_j)-f(w^*))}+G^2\sum_{j=1}^t{\eta_j^2}\end{equation}
此时，利用之前给的限定条件，可以得到：
\begin{equation}2\sum_{j=1}^t{\eta_j (f(w_j)-f(w^*))}\leq R^2+G^2\Vert \boldsymbol{\eta}\Vert_2^2\end{equation}
又因为我们之前的定义\(\mathbb{E}[f_{best}(t)] \leq \mathbb{E}[f({w}_j)]\)，所以：
\begin{equation}E[f_{best}(t)] - f(w^*) \leq \frac{R^2 + G^2 ||\boldsymbol{\eta}||_2^2}{2 \sum_{j=1}^t \eta_j}\end{equation}
根据我们之前的前提假设\(\sum_{t=1}^\infty \eta_t = \infty\)，可以得到：
\begin{equation}E[f_{best}(t)] \rightarrow f({w}^*)\end{equation}
此时，我们可以利用Markov不等式：
\begin{equation}P(f_{best}(t) - f({w}^*) \geq \epsilon) \leq \frac{E[f_{best}(t) - f({w}^*)]}{\epsilon} \leq \frac{R^2 + G^2 ||{\eta}||_2^2}{2 \epsilon \sum_{j=1}^t \eta_j}\end{equation}
所以，当\(t\rightarrow\infty\)时：
\begin{equation}P(f_{best}(t) - f({w}^*) \geq \epsilon) \rightarrow 0\end{equation}