RL-赵-(六)：随机逼近/Stochastic Approximation（SA）【无需目标函数】、RM算法、随机梯度下降（SGD）【需目标函数】【采样须独立同分布】【BGD-＞MBGD-＞SGD】_stochastic approximation (sa)

一、Motivating example

首先回顾mean estimation:

• 考虑一个random variablc $X$。
• 目标是估计$\mathbb{E}[X]$
• 假设已经有了一系列随机独立同分布的样本 { x i } i = 1 N \{x_i\}_{i=1}^N {xi​}i=1N​
• $X$的expection可以被估计为
  $$\mathbb{E}[X]\approx \bar{x}:=\frac{1}{N}\sum _{i=1}^N{x}_i$$

已经知道这个估计的基本想法是Monte Carlo estimation，以及$\bar{x}\to \mathbb{E}$,随着$N\to \infty$。

这里为什么又要关注mean estimation, 那是因为在强化学习中许多value被定义为means，例如state/action value。

新的问题： 如何计算mean $barx:$

$$\mathbb{E}[X]\approx \bar{x}:=\frac{1}{N}\sum _{i=1}^N{x}_i$$

我们有两种方式：

• 第一种方法：简单地，收集所有样本，然后计算平均值。但是该方法的缺点是如果样本是一个接一个的被收集，那么就必须等待所有样本收集完成才能计算
• 第二种方法： 可以克服第一种方法的缺点，用一种incremental(增量式)和iterative (送代式) 的方式计算average。

具体地，假设

$$w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i,k=1,2,...$$

然后有

$$w_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i,k=1,2,...$$

我们要建立$w_k$和$w_{k+1}$之间的关系，用$w_k$表达$w_{k+1}:$

w k + 1 = 1 k ∑ i = 1 k x i   = 1 k ( ∑ i = 1 k − 1 x i + x k ) = 1 k ( ( k − 1 ) w k + x k ) = w k   − 1 k ( w k − x k )

$$\begin{aligned}w_{k+1}&=\frac{1}{k}\sum_{i=1}^{k}x_i\:=\frac{1}{k}\left(\sum_{i=1}^{k-1}x_i+x_k\right)=\frac{1}{k}\left((k-1)w_k+x_k\right)=w_k\:-\frac{1}{k}\left(w_k-x_k\right)\end{aligned}$$ wk+1​​=k1​i=1∑k​xi​=k1​(i=1∑k−1​xi​+xk​)=k1​((k−1)wk​+xk​)=wk​−k1​(wk​−xk​)​
因此，获得了如下的迭代算法：
$$\begin{array}{r}{w}_{k+1}=w_k-\frac{1}{k}(w_k-x_k)\end{array}$$

我们使用上面的迭代算法 w k + 1   =   w k   −   1 k   ( w k   −   x k ) \color{blue}{

$$\begin{aligned}w_{k+1}\:=\:w_k\:-\:\frac{1}{k}\:(w_k\:-\:x_k)\end{aligned}$$ } wk+1​=wk​−k1​(wk​−xk​)​增量式地计算 $x$ 的 mean：

w 1 = x 1 , w 2 = w 1 − 1 1 ( w 1 − x 1 ) = x 1 , w 3 = w 2 − 1 2 ( w 2 − x 2 ) = x 1 − 1 2 ( x 1 − x 2 ) = 1 2 ( x 1 + x 2 ) , w 4 = w 3 − 1 3 ( w 3 − x 3 ) = 1 3 ( x 1 + x 2 + x 3 ) , : w k + 1 = 1 k ∑ i = 1 k x i .

$$\begin{aligned} &{w_1} =x_{1}, \\ &w_2 =w_1-\frac11(w_1-x_1)=x_1, \\ &w_3 =w_2-\frac{1}{2}(w_2-x_2)=x_1-\frac{1}{2}(x_1-x_2)=\frac{1}{2}(x_1+x_2), \\ &w_4=w_3-\frac13(w_3-x_3)=\frac13(x_1+x_2+x_3), \\ &\text{:} \\ &w_{k+1} =\frac1k\sum_{i=1}^kx_i. \end{aligned}$$ ​w1​=x1​,w2​=w1​−11​(w1​−x1​)=x1​,w3​=w2​−21​(w2​−x2​)=x1​−21​(x1​−x2​)=21​(x1​+x2​),w4​=w3​−31​(w3​−x3​)=31​(x1​+x2​+x3​),:wk+1​=k1​i=1∑k​xi​.​

这样就得到了一个求平均数的迭代式的算法。

• 算法的优势是在第k步的时候不需要把前面所有的 $x_i$ 全部加起来再求平均，可以在得到一个样本的时候立即求平均。
• 另外这个算法也代表了一种增量式的计算思想，在最开始的时候因为$k$比较小，$w_k\ne \mathbb{E}[X]$，但是有比没有强。随着获得样本数的增加，估计的准确度会逐渐提高，也就是$w_k\to \mathbb{E}[X]$ as $k\to N$ 。

更进一步地，将上述算法 w k + 1   =   w k   −   1 k   ( w k   −   x k ) \color{blue}{

$$\begin{aligned}w_{k+1}\:=\:w_k\:-\:\frac{1}{k}\:(w_k\:-\:x_k)\end{aligned}$$ } wk+1​=wk​−k1​(wk​−xk​)​ 用一个更泛化的形式表示为：

$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

其中 $\frac{1}{k}$ 被替换为 ${\alpha }_k>0$。

• 该算法是否会收敛到mean $\mathbb{E}[X]$? 答案是Yes，如果 { α k } \{\alpha_k\} {αk​}满足某些条件的时候。
• 该算法也是一种特殊的Stochastic Approximation（SA）算法，也是一种特殊的 stochastic gradient descent 算法。

二、Robbins-Monro algorithm

随机逼近/Stochastic approximation (SA)：

• SA指的是一类广泛的随机迭代算法，用来求解方程的根或者优化问题。
• 与其他求根算法（如基于梯度的方法）相比，SA的强大之处在于它不需要知道目标函数的表达式，也不知道它的导数或者梯度表达式。

Robbins-Monro（RM）算法：

• 这是随机逼近（stochastic approximation）领域的开创性工作。
• 著名的随机梯度下降算法（stochastic gradient descent algorithm）是RM算法的一种特殊形式。
• 它可以用于分析在开头介绍的均值估计算法（mean estimation algorithms）。

1、Problem statement

问题声明： 假设我们要求解下面方程的根

$$g(w)=0$$

其中$w\in \mathbb{R}$是要求解的变量，$g:\mathbb{R}\to \mathbb{R}$是一个函数.

• 许多问题最终可以转换为这样的求根问题。例如，假设$J(w)$是最小化的一个目标函数，然后，优化问题被转换为
  $$g(w)={\nabla }_{w}J(w)=0$$
• 另外可能面临$g(w)=c$,其中$c$是一个常数，这样也可以将其转换为上述等式，通过将$g(w)-c$写为一个新的函数。
  
  如何计算方程 $g(w)=0$ 的根？
• 如果已知函数 $g$ 或其导数的表达式，那么有许多数值算法可以解决这个问题。
• 如果函数 $g$ 的表达式是未知的呢？例如，该函数是由人工神经网络（artificial neural network）表示的。

这样的问题可以使用Robbins-Monro(RM)算法求解：

w k + 1   =   w k   −   a k   g ~ ( w k , η k   ) , k   =   1 , 2 , 3 , . . .

$$\begin{aligned}w_{k+1}\:=\:w_k\:-\:a_k\:\tilde{g}(w_k,\eta_k\:),k\:=\:1,2,3,...\end{aligned}$$ wk+1​=wk​−ak​g~​(wk​,ηk​),k=1,2,3,...​

2、Robbins-Monro（RM）算法

Robbins-Monro(RM)算法：
w k + 1   =   w k   −   a k   g ~ ( w k , η k   ) , k   =   1 , 2 , 3 , . . .

$$\begin{aligned}w_{k+1}\:=\:w_k\:-\:a_k\:\tilde{g}(w_k,\eta_k\:),k\:=\:1,2,3,...\end{aligned}$$ wk+1​=wk​−ak​g~​(wk​,ηk​),k=1,2,3,...​

其中

• $w_k$是root的第 $k$ 次估计；
• $\tilde{g}\left(w_k,{\eta }_k\right)=g(w_k)+{\eta }_k$ 是第 $k$ 次带有噪声的观测；
• $a_k$ 是一个positive coefficient；

函数$g(w)$是一个black box! 也就是说该算法依赖于数据：

• 输入序列： { w k } \{w_k\} {wk​}
• 噪声输出序列 : { g ~ ( w k , η k ) } :\{\tilde{g}\left(w_k,\eta_k\right)\} :{g~​(wk​,ηk​)}

这里边的哲学思想：没有model，就要有data！ 这里的model就是指函数的表达式。

3、收敛性分析（Convergence properties）

为什么RM算法可以找到$g(w)=0$的解？

3.1 直观的例子

首先给出一个直观的例子：

• $g(w)=tanh(w-1)$；
• $g(w)=0$的 true root 是 $w^{\ast }=1$；
• 初始值： $w_1=2,a_k=1/k,{\eta }_k=0$ (为简单起见，不考虑噪音)

在本例中RM算法如下【当 ${\eta }_k=0$的时候 $\tilde{g}\left(w_k,{\eta }_k\right)=g(w_k)$】：
$$w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right)=w_k-a_{k}g(w_k)$$

模拟仿真结果是： $w_k$ 收敛到 true root $w^{\ast }=1$。

直观上： $w_{k+1}$比$w_k$ 更接近于$w\ast$

• 当$w_k>w^{\ast }$,有$g(w_k)>0$,那么$w_{k+1}=w_k-a_{k}g(w_k)<w_k$,因此$w_{k+1}$比$w_{k+1}$比$w_k$ 更接近于$w^{\ast }$；
• 当$w_k<w^{\ast }$,有$g(w_k)<0$,那么$w_{k+1}=w_k-a_{k}g(w_k)>w_k$,因此$w_{k+1}$比$w_k$ 更接近于$w^{\ast }$；

3.2 RM算法的3个前提条件

上面的分析是基于直观的，但是不够严格。一个严格收敛的结果如下：

在RM算法中，如果上面的条件满足，那么$w_k$就会收敛到$w^{\ast }$,$w^{\ast }$就是$g(w)=0$的一个解。

• 第一个条件是关于 $g(w)$ 的梯度要求；
• 第二个条件是关于$a_k$系数的要求；
• 第三个条件是关于这个${\eta }_k$,就是测量误差的要求。

3.2.1 这三个条件的解释

• 条件1【关于 $g(w)$ 的梯度要求】: 对于所有的 $w$，满足：$0<c_1\le {\nabla }_{k}g(w)\le c_2$ ，这个条件表示：
  • $g$ 必须单调递增，确保 $g(w)=0$ 的根存在且唯一。
  • 梯度从上方有界。
• 条件2【关于$a_k$系数的要求】: ${\sum }_{k=1}^{\infty }{a}_k=\infty$ 且 ${\sum }_{k=1}^{\infty }{a}_k^2<\infty$
  • ${\sum }_{k=1}^{\infty }{a}_k^2<\infty$ 确保 随着$k\to \infty$, $a_k\to 0$；
  • ${\sum }_{k=1}^{\infty }{a}_k=\infty$表明$a_k$不应当太快收敛到0；
• 条件3【关于${\eta }_k$测量误差的要求】：$\mathbb{E}[{\eta }_k\mid {\mathcal{H}}_k]=0$ 并且 $\mathbb{E}[{\eta }_k^2\mid {\mathcal{H}}_k]<\infty$
  • 一个特殊但常见的情况是 ${\eta }_k$ 是一个满足 $\mathbb{E}[{\eta }_k\mid {\mathcal{H}}_k]=0$ 并且 $\mathbb{E}[{\eta }_k^2\mid {\mathcal{H}}_k]<\infty$ 的独立同分布随机序列。观测误差 ${\eta }_k$ 不要求是高斯分布的。

3.2.2 对第二个条件进行详细讨论

$$\sum _{k=1}^{\infty }{a}_k^2<\infty ,\sum _{k=1}^{\infty }{a}_k=\infty$$
首先： ${\sum }_{k=1}^{\infty }{a}_k^2<\infty$表明随着$k\to \infty$, $a_k\to 0$ 为什么这个条件重要呢？ 因为：
$$w_{k+1}-w_k=-a_k\tilde{g}(w_k,{\eta }_k)$$

• 如果$a_k\to 0$,那么$a_k\tilde{g}(w_k,{\eta }_k)\to 0$,因此$w_{k+1}-w_k\to 0$；
• we need the fact that $w_{k+1}-w_k\to 0$ 如果$w_k$ 最终收敛
• 如果$w_k\to w\ast$,那么$g(w_k)\to 0$和$\tilde{g}(w_k,{\eta }_k)$由${\eta }_k$确定。
  

第二，${\sum }_{k=1}^{\infty }{a}_k=\infty$表明$a_k$不应当太快收敛到0. 为什么这个条件重要呢？

• 根据$w_2=w_1-a_1\tilde{g}\left(w_1,{\eta }_1\right),w_3=w_2-a_2\tilde{g}\left(w_2,{\eta }_2\right),\dots ,w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right)$得出：
  $$w_{\infty }-w_1=\sum _{k=1}^{\infty }{a}_k\tilde{g}\left(w_k,{\eta }_k\right)$$
• 假定$w_{\infty }=w^{\ast }$。如果${\sum }_{k=1}^{\infty }{a}_k<\infty$,那么${\sum }_{k=1}^{\infty }{a}_k\tilde{g}\left(w_k,{\eta }_k\right)$可能是有界的。然后，如果初始猜测$w_1$任意选择远离$w\ast$,那么上述等式可能是不成立的 (invalid) 。

那么问题来了，什么样的$a_k$能够满足这样两个条件呢？ ${\sum }_{k=1}^{\infty }{a}_k=\infty$且${\sum }_{k=1}^{\infty }{a}_k^2<\infty$ 一个典型的序列是
$$a_k=\frac{1}{k}$$

• 在数学上 $k$ 满足
  lim ⁡ n → ∞ ( ∑ k = 1 n 1 k − ln ⁡ n ) = κ

  $$\begin{aligned}\lim_{n\to\infty}\left(\sum_{k=1}^n\frac{1}{k}-\ln n\right)=\kappa\end{aligned}$$ n→∞lim​(k=1∑n​k1​−lnn)=κ​
  其中$\kappa \approx 0.577$,称为Euler-Mascheroni 常数 (也称为Euler常数)

• 另一个数学上的结论是：
  $$\sum _{k=1}^{\infty }\frac{1}{k^2}=\frac{{\pi }^2}{6}<\infty$$
  极限${\sum }_{k=1}^{\infty }$在数论中也有一个特定的名字： Basel problem 。

如果不满足这三个条件，RM算法可能无法正常工作。

• 例如，$g(w)=w^3-5$ 不满足梯度有界性的第一个条件。如果初始猜测很好，算法可以收敛（在局部）。否则，它将发散。

我们将看到，在许多强化学习算法中，$a_k$ 通常被选为一个足够小的常数。尽管在这种情况下第二个条件未被满足，但算法仍然可以有效地工作。

$a_k$ 通常被选为一个足够小的常数还有一个作用：防止 $a_k=\frac{1}{k}$ 时，当 $k$ 特别大的时候，后面的数据起到的作用就会特别小，而我们希望未来进来的数据依然能够有用，所以不会让 $a_k$ 到后面趋向于0，而是让它趋向于一个特别小的数。

4、将RM算法用于mean estimation

回顾本文最初的mean estimation算法

$$w_{k+1}=w_k-{\alpha }_k(w_k-x_k)$$

我们知道：

• 如果${\alpha }_k=1/k$,那么$w_{k+1}=1/k{\sum }_{i=1}^k{x}_i$；
• 如果${\alpha }_k$不是$1/k$, 收敛性没办法分析。

现在我们证明这个算法是一个特殊的RM算法，它的收敛性就能够得到了。

1. 考虑–个函数
   $$g(w)\doteq w-\mathbb{E}[X]$$
   我们的目标是求解$g(w)=0$,这样，我们就可以得到$\mathbb{E}[X]$
2. 我们不知道 $X$，但是可以对 $X$ 进行采样，因此我们得到的观察是
   $$\tilde{g}\left(w,x\right)\doteq w-x$$
   注意：
   $$\begin{array}{rl}\tilde{g}(w,\eta )& =w-x\\ & =w-x+\mathbb{E}[X]-\mathbb{E}[X]\\ & =(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\doteq g(w)+\eta ,\end{array}$$
3. 求解$g(x)=0$的RM算法是

w k + 1   =   w k   −   α k   g ~ ( w k , η k   )   =   w k   −   α k ( w k   −   x k   )

$$\begin{aligned}w_{k+1}\:=\:w_k\:-\:\alpha_k\:\tilde{g}\left(w_k,\eta_k\:\right)\:=\:w_k\:-\:\alpha_k\left(w_k\:-\:x_k\:\right)\end{aligned}$$ wk+1​=wk​−αk​g~​(wk​,ηk​)=wk​−αk​(wk​−xk​)​
这就是之前给出的mean estimation算法。可见，mean estimation algorithm 是 RM算法的一个特殊情况。

三、Stochastic gradient descent【随机梯度下降】

stochastic gradient descent(SGD)算法在机器学习和强化学习的许多领域中广泛应用；

• SGD算法是RM算法的一个特殊情况。
• mean estimation algorithm 是 RM算法的一个特殊情况，也是SGD算法的一个特殊情况。

假设我们的目标是求解下面优化问题
$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]$$

• $w$是被优化的参数
• $X$ 是一个随机变量，The expection 实际上就是针对这个$X$进行计算的
• $w$和$X$可以是标量或者向量，函数$f(\cdot )$是一个标量。

有三种方法求解：

• 方法1: gradient descent (GD)
  $$w_{k+1}=w_k-{\alpha }_k{\nabla }_w\mathbb{E}[f(w_k,X)]=w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]$$
  问题是整体样本 $X$ 的梯度值的期望值 $\mathbb{E}[{\nabla }_{w}f(w_k,X)$ 很难获取（the expected value is difficult to obtain）。
• 方法2: batch gradient descent (BGD)
  $$\begin{array}{rl}& \mathbb{E}[{\nabla }_{w}f(w_k,X)]\approx \frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)\\ & w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i).\end{array}$$
  问题是对于每个 $w_k$，在每次迭代中需要许多次采样。【批量梯度下降法（Batch Gradient Descent，简称BGD）是梯度下降法最原始的形式，它的具体思路是在更新每一参数时都使用所有的样本来进行更新，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果样本数目m很大，这种方法的迭代速度很慢！】
• 方法3: stochastic gradient descent (SGD):
  $$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$
  SGD与前面两种算法相比：
  • 与GD算法相比，将 true gradient $E[{\nabla }_{w}f(w_k,X)]$替换为 stochastic gradient ${\nabla }_{w}f(w_k,x_k)$；
  • 与BGD算法相比，令 $n=1$；

1、SGD算法的示例、应用

考虑下面的一个优化问题：
$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]=\mathbb{E}\left[\frac{1}{2}\Vert w-X{\Vert }^2\right],$$
其中：
$$f(w,X)=\Vert w-X{\Vert }^2/2{\nabla }_{w}f(w,X)=w-X$$

有三个练习：

• 证明最优解是 $w^{\ast }=\mathbb{E}[X]$
• 用GD算法求解这个问题
• 用SGD算法求解这个问题

答案：

• 练习01：证明最优解是 $w^{\ast }=\mathbb{E}[X]$：
  对$J(w)$求梯度，使其等于0，即可得到最优解，因此有${\nabla }_{w}J(w)=0$,然后根据公式，得到$\mathbb{E}[{\nabla }_{w}f(w,X)]=0$,然后得到$\mathbb{E}[w-X]=0$，由于w是一个常数，因此$w=\mathbb{E}[X]$。

• 练习02：用GD算法求解这个问题：
  w k + 1 = w k − α k ∇ w J ( w k ) = w k − α k E [ ∇ w f ( w k , X ) ] = w k − α k E [ w k − X ] .

  $$\begin{aligned} w_{k+1}& \begin{aligned}=w_k-\alpha_k\nabla_wJ(w_k)\end{aligned}$$ \\ &=w_k-\alpha_k\mathbb{E}[\nabla_wf(w_k,X)] \\ & $$\begin{aligned}=w_k-\alpha_k\mathbb{E}[w_k-X].\end{aligned}$$ \end{aligned} wk+1​​=wk​−αk​∇w​J(wk​)​=wk​−αk​E[∇w​f(wk​,X)]=wk​−αk​E[wk​−X].​​

• 练习03：使用SGD算法求解这个问题：
  $$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)=w_k-{\alpha }_k(w_k-x_k)$$
  

2、收敛性分析（Convergence）

使用SGD时，采样必须满足 iid（独立同分布/independent and identically distributed）。

3、收敛模式（Convergence pattern）

注：BGD是梯度下降法最原始的形式，它的具体思路是在更新每一参数时都使用所有的样本来进行更新，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据。

问题：由于stochastic gradient是随机的，那么approximation是不精确的，SGD的收敛性是slow或者random？

为了回答这个问题，我们考虑在stochastic gradient 和真实梯度 batch gradients之间的一个相对误差 relative error:

$${\delta }_k\doteq \frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}{|\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}$$

由于 $\mathbb{E}[{\nabla }_{w}f(w^{\ast },X)]=0$，因此：

$${\delta }_k=\frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}{|\mathbb{E}[{\nabla }_{w}f(w_k,X)]-\mathbb{E}[{\nabla }_{w}f(w^{\ast },X)]|}=\frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}{|\mathbb{E}[{\nabla }_w^{2}f({\tilde{w}}_k,X)(w_k-w^{\ast })]|}$$

其中后面等式的分母使用了一个mean value theorem（中值定理），并且${\tilde{w}}_k\in [w_k,w\ast ]$

假设$f$是严格凸的，满足
$${\nabla }_w^{2}f\ge c>0$$
对于所有的$w,X$,其中 $c$ 是一个positive bound。

然后，${\delta }_k$ 的证明就变为了
∣ E [ ∇ w 2 f ( w ~ k , X ) ( w k − w ∗ ) ] = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ( w k − w ∗ ) ∣ = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ∣ ∣ ( w k − w ∗ ) ∣ ≥ c ∣ w k − w ∗ ∣

$$\begin{aligned} \begin{aligned}\left|\mathbb{E}[\nabla_w^2f(\tilde{w}_k,X)(w_k-w^*)]\right.\end{aligned}$$ & $$\begin{aligned}=\left|\mathbb{E}[\nabla_w^2f(\tilde{w}_k,X)](w_k-w^*)\right|\end{aligned}$$ \\ &=\left|\mathbb{E}[\nabla_w^2f(\tilde{w}_k,X)]\right|\big|(w_k-w^*)\big|\geq c|w_k-w^*| \end{aligned} ​E[∇w2​f(w~k​,X)(wk​−w∗)]​​= ​E[∇w2​f(w~k​,X)](wk​−w∗) ​​= ​E[∇w2​f(w~k​,X)] ​ ​(wk​−w∗) ​≥c∣wk​−w∗∣​
然后把这个分母的性质带入刚才的relative error公式，就得到
$${\delta }_k\le \frac{\left|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]\right|}{c|w_k-w^{\ast }|}$$

再看上面的式子：
$${\delta }_k\le \frac{\left|\stackrel{\text{stochastic gradient}}{\overbrace{{\nabla }_{w}f(w_k,x_k)}}-\stackrel{\text{true gradient}}{\overbrace{\mathbb{E}[{\nabla }_{w}f(w_k,X)]}}\right|}{\underset{\text{distance to the optimal solution}}{\underbrace{c|w_k-w^{\ast }|}}}.$$
这个公式也表明了SGD的一个有趣的收敛模式：

• relative error ${\delta }_k$ 与$|w_k-w^{\ast }|$成反比
• $w_k$离 $w^{\ast }$比较远，$|w_k-w^{\ast }|$比较大，分母会比较大，所以SGD方法与GD方法的相对误差 ${\delta }_k$ 会比较小，也就是说stochastic gradient的行为与true gradient是比较接近的；这时SGD与GD的行为比较类似（behaves like），都会朝着最终目标迭代；
• 当$w_k$接近$w^{\ast }$，分母会比较小，这时SGD方法与GD方法的相对误差 ${\delta }_k$ 会比较大，这时$w_k$会跑到$w^{\ast }$的附近，有一定的随机性（收敛性在$w\ast$的周边存在较多的随机性）；

尽管均值的初始猜测离真实值很远，随机梯度下降（SGD）的估计可以迅速接近真实值的邻近区域。
当估计接近真实值时，它表现出一定的随机性，但仍然逐渐接近真实值。

4、一个确定性公式（A deterministic formulation）

在之前介绍的SGD的formulation中，涉及random variable和expectation。但是在学习其他材料的时候可能会遇到一个SGD的deterministic formulation，不涉及任何random variables。

同样地，考虑这样一个优化问题：
$$\underset{w}{\min }J(w)=\frac{1}{n}\sum _{i=1}^{n}f(w,x_i)$$

• $f(w,x_i)$是一个参数化的函数；
• $w$是需要被优化的参数
• 一组实数 { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​，其中$x_i$不必是任意random variable的一个采样，反正就是一组实数。

求解这个问题的gradient descent算法如下：
$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}J(w_k)=w_k-{\alpha }_k\frac{1}{n}\sum _{i=1}^n{\nabla }_{w}f(w_k,x_i)$$
假设这样的一个实数集合比较大，每次只能得到一个 $x_i$，在这种情况下，可以使用下面的迭代算法：
$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$

那么问题来了：

• 这个算法是随机梯度下降（SGD）吗？它不涉及任何随机变量（random variable）或期望值（expected values）。
• 我们应该如何使用有限的数集 { x i } i = 1 n {\{x_i\}}^{n}_{i=1} {xi​}i=1n​？是应该将它们按照某种顺序一个接一个地取出？还是随机地从这个集合中取出？

对上述问题的一个快速回答是，我们可以手动引入一个随机变量（random variable），并将确定性的表述（deterministic formulation）转化为随机梯度下降（SGD）的随机形式（stochastic formulation）。

具体地，假设一个$X$是定义在集合 { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​的random variable。假设它的概率分布是均匀的，即
$$p(X=x_i)=1/n$$
然后，这个deterministic optimization problem变成了一个stochastic one:
$$\underset{w}{\min }J(w)=\frac{1}{n}\sum _{i=1}^{n}f(w,x_i)=\mathbb{E}[f(w,X)]$$

• 上面等式的后面是strict，而不是approximate。因此，这个算法是SGD。
• The estimate converges if $x_k$ is uniformly and independently sampled from { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​（采样必须满足独立同分布） ；
• $x_k$ may repreatedly take the same number in { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​ since it is sampled randomly。

四、BGD, MBGD, and SGD

• BGD：批量梯度下降法（Batch Gradient Descent，简称BGD）是梯度下降法最原始的形式，它的具体思路是在更新每一参数时都使用所有的样本来进行更新，它的目的是得到一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果样本数目很大，这种方法的迭代速度很慢！
• SGD：随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
  • 优点：训练速度快；
  • 缺点：准确度下降，并不是全局最优；不易于并行实现。
• MBGD：小批量梯度下降，是对批量梯度下降以及随机梯度下降的一个折中办法。其思想是：每次迭代 使用 batch_size 个样本来对参数进行更新。

MBGD与BGD和SGD进行比较：

• 与SGD相比，MBGD具有更少的随机性，因为它使用更多的采样数据，而不是像SGD中那样仅仅使用一个。·与BGD相比，MBGD在每次迭代中不要求使用全部的samples，这使其更加灵活和高效
• if m=1, MBGD变为SGD
• if m=n, MBGD does NOT become BGD strictly speaking, 因为MBGD使用 $n$ 个样本的随机采样，而BGD使用所有n个样本。特别
  地，MBGD可能使用 { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​中的一个值很多次，而BGD使用每个数值一次。

1、Illustrative examples

五、Summary

这些结果是有用的：

我们将在下一章中看到，时差分学习算法可以被看作是随机逼近算法，因此具有类似的表达式。
它们是可以应用于许多其他领域的重要优化技术。

---

---

---

参考资料：
【强化学习】强化学习数学基础：随机近似理论与随机梯度下降