梯度下降

梯度下降(Gradient Descent)通过沿负梯度方向迭代最小化损失函数,更新规则为 $w_{t+1} = w_t - \eta\nabla L(w_t)$。对 $L$-光滑($\Vert\nabla L(w) - \nabla L(w')\Vert \le L\Vert w - w'\Vert$)且 $\mu$-强凸的损失,取 $\eta \le 2/L$ 可保证收敛,固定学习率下误差以 $\Vert w_t - w^*\Vert \le (1 - 1/\kappa)^t\Vert w_0 - w^*\Vert$ 线性收敛,其中 $\kappa = \lambda_{\max}/\lambda_{\min}$ 为 Hessian 条件数。$\kappa$ 越大椭圆等高线越扁,更新轨迹呈锯齿状越慢(近似 $\kappa$ 次迭代才等价于一次沿长轴的进展)。

训练几乎所有 ML/DL 模型的基石算法,面试常对比批量梯度下降(BGD)、随机梯度下降(SGD)与 Mini-batch。SGD 每次随机抽一个样本估计梯度 $g_t = \nabla L_{i_t}(w_t)$,由 $\mathbb{E}[g_t] = \frac{1}{n}\sum_{i=1}^{n}\nabla L_i(w_t) = \nabla L(w_t)$ 可知它是全局梯度的无偏估计;Mini-batch(大小 $B$)把方差降到原来的 $1/B$(独立同分布样本时 $\mathrm{Var}[\hat g] = \mathrm{Var}[g]/B$),但引入了“噪声球”: 强凸条件下 SGD 停在 $\Vert w - w^*\Vert^2 \le \frac{\eta\sigma^2}{2\mu}$ 的邻域内($\sigma^2$ 为梯度估计方差),误差不会精确到 0。

相比解析求解(如正规方程需 $O(d^3)$ 矩阵求逆),GD 只依赖一阶梯度、内存 $O(d)$,可扩展到百万级参数;条件数 $\kappa = 10$ 与 $\kappa = 1000$ 的问题收敛迭代数相差约两个数量级——这是动量、自适应(Adam)与二阶方法(牛顿法)存在的根本动机。

写出梯度下降更新公式 $w_{t+1} = w_t - \eta\nabla L(w_t)$,并推导对 $L$-光滑凸函数学习率上限 $\eta \le 2/L$?

条件数 $\kappa = \lambda_{\max}/\lambda_{\min}$ 如何决定收敛率 $(1 - 1/\kappa)^t$?为什么病态二次型呈锯齿轨迹?

证明 SGD 梯度是全局梯度的无偏估计: $\mathbb{E}[g_t] = \nabla L(w_t)$;mini-batch 把方差降到多少倍?

为什么 SGD 收敛在“噪声球”附近?误差下界 $\frac{\eta\sigma^2}{2\mu}$ 从哪来,与学习率和 batch size 什么关系?

学习率过大或过小分别会发生什么?动量项 $v_t = \beta v_{t-1} + (1-\beta)\nabla L$ 为什么能抑制锯齿震荡?