Stochastic Approximation, SA, 随机近似
在不知道方程表达式的情况下,通过随机采样来求解或优化方程。
Robbins-Monro, RM
RM 的思想是用函数输出值控制调参幅度。 要想求解包含未知函数的方程
其中
期望值为 0 且 不为无穷。其对应的噪音分布可以不是高斯分布。 - 对于任意
, 。说明 需要单调递增且导数不趋近无穷大。 表示 ,否则 不会收敛。 表示 不应收敛太快,以保证从任意初始值开始都能收敛。
Gradient Descent, GD, 梯度下降
梯度下降的思想是用函数梯度控制调参幅度。 其目的是找到参数
考虑基本梯度下降 GD:
可以发现这里需要求
如果从已有样本中进行二次采样,则得到小批量梯度下降 MBGD:
如果只采样一次,采样得到的梯度称为随机梯度,则得到随机梯度下降 SGD:
与真值 相距较远时,随机梯度更接近 的梯度期望值;相距较近时,随机梯度表现出更大的随机性。
考虑随机梯度与实际梯度的相对误差:
因为
代入相对误差公式,得到:
其中