计算均值的新方法

有两种方法。第一种方法很直接，即收集所有样本后计算平均值；但这种方法的缺点是，若样本是在一段时间内逐个收集的，我们必须等到所有样本都收集完毕。第二种方法可避免此缺点，因为它以增量迭代的方式计算平均值，来几个就计算几个，不需要等了。

步骤

假设

由此可得

则有

最终推导出 增量更新公式：

一般性替换

此算法是一种特殊的 SA 算法（随机近似算法），也是一种特殊的 随机梯度下降算法

Robbins-Monro 算法

随机梯度下降算法是 RM 算法的特殊形式

RM算法的目的是在不知道方程表达式、只进行采样的前提下求方程的解

为了求解 $g(\omega)=0$ 的解，我们采用 $\omega_{k+1}=\omega_k-a_k\widetilde{g}(\omega_k,\eta_k)$ （*），其中 $\widetilde{g}(\omega_k,\eta_k)$ 是第k次带噪声的观测

具体的实现步骤是，输入一个 $\omega_1$ ，我们可以得到一个带噪声的观测值 $\widetilde{g_1}$ ，通过（*）式可以得到 $\omega_2$ ，又可以据此我们可以得到一个带噪声的观测值 $\widetilde{g_2}$ ，由 $\widetilde{g_2}$ 通过（*）式可以得到 $\omega_3$ ......

如果我们能证明这样的序列 $\omega_k,k=1,2,3\dots$ 会收敛于 $g(\omega)=0$ 的解 $\omega^*$ ，那这样的一个算法就是可行的

下面我们引入Robbins-Monro定理来证明这个序列 $\omega_k,k=1,2,3\dots$ 收敛于 $g(\omega)=0$ 的解 $\omega^*$

Robbins-Monro定理

若有

满足 $\sum_{k = 1}^{\infty} a_k = \infty, \sum_{k = 1}^{\infty} a_k^2 < \infty$ 的一个典型序列是 $\frac{1}{k}$ ，其无穷级数发散，其无穷平方和= $\frac{\pi^2}{6}$ ，实际常把 $a_k$ 选为足够小的常数，这虽然违反条件，但是可以避免 $\frac{1}{k}$ 带来的后端序列权重过低的问题

是一种特殊的RM算法

随机梯度下降

Stochastic Gradient Descent (SGD)

随机梯度下降算法是为了解决一个优化问题 $\begin{aligned} \min_{w} J(w) = \mathbb{E}[f(w, X)] \end{aligned}$

我们要优化 $\omega$ 来使 $J(\omega)$ 的值最小

$X$ 是随机变量， $f$ 是 $\omega$ 和 $X$ 的函数； $X$ 这个随机变量的概率分布已经给定但是暂时是未知的， $\begin{aligned} \mathbb{E}[f(w, X)] \end{aligned}$ 的 $\begin{aligned} \mathbb{E} \end{aligned}$ 就是对 $X$ 求期望； $\omega$ 和 $X$ 既可以是向量也可以是标量， $f$ 的值是标量

方法一：梯度下降GD

$\begin{aligned} 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)] \end{aligned}$

随机梯度下降通过在每次迭代中，沿着目标函数期望梯度的负方向来更新参数 $\omega$ ，逐步逼近目标函数的最小值点。实际应用中，由于计算整个数据集上目标函数的期望梯度（全量梯度）计算量过大，通常会采用小批量数据或者单个数据来近似计算期望梯度，从而实现高效的参数更新。

方法二：批量梯度下降BGD

$\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \approx \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i) \quad w_{k + 1} = w_k - \alpha_k \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i). \end{aligned}$

当 n = 1时，就是每次只用一个样本进行梯度更新，即SGD；当 n 为整个数据集样本数时，就退化为批量梯度下降。这种基于样本近似计算梯度的方式，在大规模数据场景下极大地降低了计算复杂度，使得优化算法能够高效运行

方法三：随机梯度下降SGD

$\begin{aligned} w_{k + 1} = w_k - \alpha_k \nabla_{w} f(w_k, x_k) \end{aligned}$

式子等号右边，原来的 $X$ 变成了对 $X$ 的随机采样 $x_k$ ；true gradient $\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \end{aligned}$ 变成了stochastic gradient $\begin{aligned} \nabla_{w} f(w_k, x_k) \end{aligned}$ 。这就是BGD里令n=1的情况

例子

考虑一个优化问题 $\begin{aligned} \min_{w} J(w) = \mathbb{E}[f(w, X)] = \mathbb{E}\left[ \frac{1}{2} \| w - X \|^2 \right] \end{aligned}$

其中 $\begin{aligned} f(w, X) = \frac{\| w - X \|^2}{2} \quad \nabla_{w} f(w, X) = w - X \end{aligned}$

其最优解为 $\begin{aligned} w^* = \mathbb{E}[X] \end{aligned}$

GD

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \nabla_{w} J(w_k) &= w_k - \alpha_k \mathbb{E}[\nabla_{w} f(w_k, X)] &= w_k - \alpha_k \mathbb{E}[w_k - X]. \end{aligned}$

SGD
$\begin{aligned} w_{k+1} = w_k - \alpha_k \nabla_{w} f(w_k, x_k) = w_k - \alpha_k (w_k - x_k) \end{aligned}$

收敛性

从GD到SGD：

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \mathbb{E}[\nabla_{w} f(w_k, X)] \\ &\Downarrow \\ w_{k + 1} &= w_k - \alpha_k \nabla_{w} f(w_k, x_k) \end{aligned}$

$\begin{aligned} \nabla_{w} f(w_k, x_k) \end{aligned}$ 可以看作是 $\begin{aligned} \mathbb{E}[\nabla_{w} f(w_k, X)] \end{aligned}$ 的带噪声的观测值：

$\begin{aligned} \nabla_{w} f(w_k, x_k) = \mathbb{E}[\nabla_{w} f(w, X)] + \underbrace{\nabla_{w} f(w_k, x_k) - \mathbb{E}[\nabla_{w} f(w, X)]}_{\eta} \end{aligned}$

下面我们证明SGD是一个特殊的RM算法，由此来证明SGD在满足某些条件的情况下是收敛的

proof:

SGD是要解决一个优化问题： $\begin{aligned} J(w) = \mathbb{E}[f(w, X)] \end{aligned}$ ，令 $J(w)$ 最小。这样的优化问题可以转化为寻找 $\begin{aligned} \nabla_{w} J(w) = \mathbb{E}[\nabla_{w} f(w, X)] = 0 \end{aligned}$ 的根，因为其梯度为0是取得极小值的必要条件。

下面即求 $\begin{aligned} g(w) = \nabla_{w} J(w) = \mathbb{E}[\nabla_{w} f(w, X)]=0 \end{aligned}$ 的根

我们用RM算法来求 $g(w)=0$ 的根

$\begin{aligned} \tilde{g}(w, \eta) &= \nabla_{w} f(w, x) \\ &= \underbrace{\mathbb{E}[\nabla_{w} f(w, X)]}_{g(w)} + \underbrace{\nabla_{w} f(w, x) - \mathbb{E}[\nabla_{w} f(w, X)]}_{\eta} \end{aligned}$

$\begin{aligned} w_{k + 1} = w_k - a_k \tilde{g}(w_k, \eta_k) = w_k - a_k \nabla_{w} f(w_k, x_k) \end{aligned}$ 这实际上就是SGD算法

SGD算法的有趣性质

由于随机梯度是随机的，因此其近似并不精确，那么随机梯度下降法（SGD）的收敛过程是缓慢的还是随机的呢？

$\begin{aligned} \delta_{k} \leq \frac{\left| \nabla_{w} f(w_k, x_k) - \mathbb{E}[\nabla_{w} f(w_k, X)] \right|}{c \left| w_k - w^* \right|} \end{aligned}$

上述等式揭示了随机梯度下降法（SGD）一种有趣的收敛模式：

BGD & MBGD & SGD

$\begin{aligned} w_{k + 1} &= w_k - \alpha_k \frac{1}{n} \sum_{i = 1}^{n} \nabla_{w} f(w_k, x_i), & \text{(BGD)} \\ w_{k + 1} &= w_k - \alpha_k \frac{1}{m} \sum_{j \in \mathcal{I}_k} \nabla_{w} f(w_k, x_j), & \text{(MBGD)} \\ w_{k + 1} &= w_k - \alpha_k \nabla_{w} f(w_k, x_k). & \text{(SGD)} \end{aligned}$