一、随机梯度下降法（SGD）背景

许多机器学习与数据科学中的目标函数都具有求和结构：

例如，， 是数据点， 很大。

标准梯度下降法每步需计算：

计算复杂度高达 ，昂贵且不适合大规模问题。因此我们考虑近似计算梯度。

二、随机梯度与SGD算法

1、小批量梯度与期望

定义：对任意索引集 ，可定义小批量目标和梯度：

若 独立均匀采样自 ，则

即小批量梯度是全梯度的无偏估计。

2、SGD算法流程

1. 给定初始点 （可随机）。
2. 对 重复：
   • 随机采样 ，每个 独立采自
3. 步长 可固定或动态调整， 常常取1（单样本），也可取小批量。

由于 不一定 ，每步不保证严格下降，因此分析期望下降。

三、条件期望与马尔可夫性质

• 记 为对 的期望。
• 仅依赖于 和 ，是马尔可夫过程。
• 有 。

四、数值举例

1、二分类问题（MNIST 4 vs 9）

目标函数：

其中 （数字9），（数字4）。

SGD设置：，。数值结果显示目标减少但后期有波动（噪声地板，noise floor）。

2、一般化SGD

更一般形式为：

每步采样 ，取 。同理，

五、L-光滑情形下的SGD收敛性

1、假设

1. 每个 都是 -光滑函数 也是 -光滑。

2. 存在 ，使得

   即条件方差有界。

   证明：

   由于 是对样本集 的梯度均值，且每个 独立均匀采样自 ，我们有

   计算条件方差：

   对于单样本（），

   若每个 在所有 上有界，即存在 使得 ，则

   因此，若每个分量梯度有界，则条件方差有界，满足假设2。

2、关键引理：期望过估计（Overestimation in expectation）

引理：

在上述假设下，

若进一步有条件方差界 ，则

• 当 足够小，右侧为严格下降。

证明：

由 -光滑性，

对 条件期望，利用 ，由 -光滑性，有

对 条件期望（即对 关于 的条件期望）：

由于 ，代入得

3、收敛性定理（L-光滑情况下）

定理：

设 有下界 ，满足上述假设。SGD 用定步长 ，，则

即噪声存在， 只收敛到 ，无法无限趋近于零（称为noise floor）。

证明：

由关键引理，

取 ，其中 ，则

因此，

对 取全期望，记 ，有

移项并累加 到 ，得

由于 （ 为下界），

两边同时除以 ，并取最小值有

证毕。

六、强凸情形下的SGD收敛性

1、假设

1. -光滑， -光滑。
2. 是 -强凸函数，即 极小点 唯一。
3. 步长
4. 有界方差：

2、收敛性定理

定理（SGD 强凸情形）：

SGD 以 Q-线性速率收敛到残差： 设条件数 ，则

• 时，极限误差为 ，依赖噪声和步长。

证明：

由基础引理（L-光滑且 -强凸）：

取 ，代入得

记 ，则 ，上式变为

递归展开（不等式迭代 次）：

等比数列求和，，其中 ，所以

代入得

化简右侧第二项：

最终得

证毕。