20. 随机梯度下降法

# 随机梯度下降（SGD）

1. 问题形式

   考虑最小化函数的平均值：

   $$\min_x \frac{1}{m} \sum_{i=1}^{m} f_i(x)$$

   由于 $\nabla \sum_{i=1}^{m} f_i(x) = \sum_{i=1}^{m} \nabla f_i(x)$，梯度下降法会重复：

   $$x^{(k)} = x^{(k-1)} - t_k \cdot \frac{1}{m} \sum_{i=1}^{m} \nabla f_i(x^{(k-1)}), \quad k = 1, 2, 3, \ldots$$

2. SGD 算法

   相比之下，随机梯度下降法（Stochastic Gradient Descent，SGD）或增量梯度下降法重复：

   $$x^{(k)} = x^{(k-1)} - t_k \cdot \nabla f_{i_k}(x^{(k-1)}), \quad k = 1, 2, 3, \ldots$$

   其中 $i_k \in \{1, \ldots, m\}$ 是在第 $k$ 次迭代时选择的某个索引。

3. 索引选择规则

   在第 $k$ 次迭代选择索引 $i_k$ 的两种规则：

   • 随机规则：从 $\{1, \ldots, m\}$ 中均匀随机选择 $i_k$
   • 循环规则：选择 $i_k = 1, 2, \ldots, m, 1, 2, \ldots, m, \ldots$

   随机规则在实践中更常用。对于随机规则，注意：

   $$\mathbb{E}[\nabla f_{i_k}(x)] = \nabla f(x)$$

   因此我们可以将 SGD 视为在每一步使用梯度的无偏估计。

4. SGD 的主要优势

   • 迭代成本与 $m$ 无关（函数数量）
   • 在内存使用方面也能大幅节省

5. 例子：随机逻辑回归

   给定 $(x_i, y_i) \in \mathbb{R}^p \times \{0, 1\}$，$i = 1, \ldots, n$，逻辑回归问题为：

   $$\min_{\beta} \frac{1}{n} \sum_{i=1}^{n} \underbrace{\left(-y_i x_i^T \beta + \log(1 + \exp(x_i^T \beta))\right)}_{f_i(\beta)}$$

   梯度计算 $\nabla f(\beta) = \frac{1}{n} \sum_{i=1}^{n} (y_i - p_i(\beta)) x_i$ 在 $n$ 适中时可行，但当 $n$ 很大时不可行。

   全梯度（批量）与随机梯度：

   • 一次批量更新成本为 $O(np)$
   • 一次随机更新成本为 $O(p)$

   显然，例如 10K 次随机步骤要便宜得多。

6. 批量方法与随机方法的比较

   经验法则：

   • 随机方法通常在远离最优点时表现良好
   • 随机方法通常在接近最优点时表现较差

7. 步长选择

   SGD 的标准做法是使用递减步长，例如 $t_k = 1/k$。

   为什么不使用固定步长？ 假设我们使用循环规则。设置 $t_k = t$ 连续进行 $m$ 次更新，我们得到：

   $$x^{(k+m)} = x^{(k)} - t \sum_{i=1}^{m} \nabla f_i(x^{(k+i-1)})$$

   同时，步长为 $mt$ 的全梯度会给出：

   $$x^{(k+1)} = x^{(k)} - t \sum_{i=1}^{m} \nabla f_i(x^{(k)})$$

   这里的差异：$t \sum_{i=1}^{m} \left[\nabla f_i(x^{(k+i-1)}) - \nabla f_i(x^{(k)})\right]$，如果我们保持 $t$ 恒定，这个差异通常不会趋于零。

8. 收敛性分析

   对于凸函数 $f$，使用递减步长的梯度下降满足：

   $$f(x^{(k)}) - f^* = O\left(\frac{1}{\sqrt{k}}\right)$$

   当 $f$ 可微且具有 Lipschitz 梯度时，对于合适的固定步长，我们得到：

   $$f(x^{(k)}) - f^* = O\left(\frac{1}{k}\right)$$

   对于 SGD，对于凸函数 $f$，使用递减步长的 SGD 满足：

   $$\mathbb{E}[f(x^{(k)})] - f^* = O\left(\frac{1}{\sqrt{k}}\right)$$

   不幸的是，即使进一步假设 $f$ 具有 Lipschitz 梯度，这也不会改善。

   更糟糕的是：

   • 当 $f$ 是强凸且具有 Lipschitz 梯度时，梯度下降满足 $f(x^{(k)}) - f^* = O(\gamma^k)$，其中 $0 < \gamma < 1$
   • 但在相同条件下，SGD 给出 $\mathbb{E}[f(x^{(k)})] - f^* = O(1/k)$

   因此，随机方法在强凸性下不能享受梯度下降的线性收敛速度。

9. 小批量随机梯度下降（Mini-batch SGD）

   也常用的是小批量随机梯度下降，我们选择一个随机子集 $I_k \subseteq \{1, \ldots, m\}$，$|I_k| = b \ll m$，重复：

   $$x^{(k)} = x^{(k-1)} - t_k \cdot \frac{1}{b} \sum_{i \in I_k} \nabla f_i(x^{(k-1)}), \quad k = 1, 2, 3, \ldots$$

   同样，我们通过无偏估计来近似全梯度：

   $$\mathbb{E}\left[\frac{1}{b} \sum_{i \in I_k} \nabla f_i(x)\right] = \nabla f(x)$$

   使用小批量将方差减少 $1/b$ 倍，但成本也增加 $b$ 倍。理论并不令人信服：在 Lipschitz 梯度下，收敛速度从 $O(1/\sqrt{k})$ 变为 $O(1/\sqrt{bk} + 1/k)$。

# Modified SGD

1. 改进 SGD 的动机

   标准 SGD 的收敛速度较慢，特别是在强凸情况下只能达到 $O(1/k)$ 的收敛速度，而梯度下降可以达到线性收敛。因此，需要改进 SGD 以提高收敛速度和稳定性。

2. 典型性采样（Typicality Sampling）

   基本思想：不是随机选择样本，而是根据样本的典型性来选择，优先选择更典型的样本。

   方法：

   • 为每个类别构建典型样本池
   • 根据典型样本的定义，在线找到对应于每个类别的典型样本
   • 使用找到的典型性样本梯度，根据训练样本梯度与基准之间的角度对训练样本进行加权

3. 非典型性采样（Non-typicality Sampling）

   基本思想：为了更好地泛化深度神经网络，选择非典型样本进行训练。

   方法：

   • 识别非典型样本（与典型样本差异较大的样本）
   • 在训练过程中增加非典型样本的权重
   • 通过这种方式提高模型的泛化能力

4. 其他改进方法

   • SAG（Stochastic Average Gradient）：使用所有历史梯度的平均值
   • SAGA：SAG 的改进版本
   • SVRG（Stochastic Variance Reduced Gradient）：通过定期计算全梯度来减少方差
   • SDCA（Stochastic Dual Coordinate Ascent）：对偶坐标上升方法

# SGD 与 深度学习

1. 不均衡数据流

   问题：在深度学习中，数据往往是不均衡的，某些类别的样本数量远多于其他类别。

   MixGradient 方法：

   • 典型样本发现：为每个类别构建典型样本池，在线找到对应于每个类别的典型样本
   • 样本权重生成：使用找到的典型性样本梯度，根据训练样本梯度与基准之间的角度对训练样本进行加权
   • 数据混合：每次随机打乱训练样本并进行线性插值（mixup）

   实验结果：

   • 在 ResNet-32 和 DenseNet-169 模型上的实验表明，MixGradient 方法可以显著提高准确率
   • 在不均衡度为 20 时，MixGradient 在 ResNet-32 上达到 84.40% 的准确率，优于其他方法（Equal Weight: 81.30%，ROS: 82.19%，Focal Loss: 82.20%）
   • 在不均衡度为 50 时，MixGradient 在 ResNet-32 上达到 79.38% 的准确率，优于其他方法
   • 在多个数据集上的结果表明，MixGradient 方法可以将准确率提高高达 12%

2. 多任务学习

   问题：

   • 不同训练任务之间存在竞争关系
   • 不同任务在不同训练阶段具有不同的优先级
   • 不同任务的数据量不同

   基于样本梯度相似性的多任务学习：

   训练样本加权：基于每个任务 $t$ 下训练样本 $i$ 的梯度计算训练样本的鲁棒性，从而给出每个训练样本的权重。

   训练任务加权：基于每个任务 $t$ 下每个训练样本 $i$ 的梯度计算训练任务的一致性，从而给出每个训练任务的权重。

   实验结果：

   • 在多个数据集上的实验表明，该方法优于 Equal Weight、MGDA、DWA、PCGrad 等方法
   • 在场景分割、实例分割、深度估计等多个任务上都有提升
   • 平均相对测试提升达到 +0.094

3. SGD 在深度学习中的特点

   • 大规模数据：SGD 能够处理大规模数据集，因为每次迭代只需要一个或少量样本
   • 非凸优化：虽然理论分析主要针对凸函数，但 SGD 在深度学习的非凸优化中表现良好
   • 泛化能力：SGD 的随机性有助于模型泛化，避免过拟合
   • 计算效率：相比批量梯度下降，SGD 的计算成本大大降低

4. 深度学习中的 SGD 变体

   • Adam：自适应矩估计，结合了动量和自适应学习率
   • RMSprop：自适应学习率方法
   • AdaGrad：自适应梯度方法
   • Momentum SGD：带动量的 SGD，加速收敛
   • Nesterov Accelerated Gradient：Nesterov 加速梯度方法