次梯度法

次梯度法把梯度下降推广到没有普通导数的凸函数。例如 $f (x) = | x |$ 在零点有尖角，不能说它在零点的导数为零；但零仍是显然的最小点。次梯度用一条在函数图像下方的仿射直线描述这个尖角，使“朝哪边走”和“何时到达最优”仍能写成可检验的条件。

次梯度的定义与绝对值例子

对凸函数 $f : ℝ^{d} \to ℝ$ ，向量 $g$ 是 $x$ 处的次梯度，若对每个 $y$ 都有 $f (y) \geq f (x) + g \cdot (y - x) .$ 在可微凸函数的内部点，梯度就是唯一的次梯度。对 $f (x) = | x |$ ，若 $x > 0$ ，可取 $g = 1$ ；若 $x < 0$ ，可取 $g = - 1$ 。在 $x = 0$ ，条件变成 $| y | \geq g y$ 对每个实数 $y$ 成立。让 $y > 0$ 得 $g \leq 1$ ，让 $y < 0$ 得 $g \geq - 1$ ；反过来这两个不等式足以保证原条件，所以 $\partial f (0) = [- 1, 1]$ 。集合符号 $\partial f (x)$ 表示 $x$ 处所有次梯度。

因此在无约束凸最小化中， $0 \in \partial f (x^{*})$ 是全局最优的充要条件：把 $g = 0$ 放入定义，就得到 $f (y) \geq f (x^{*})$ ；反向若 $x^{*}$ 最优，同一个不等式说明零向量符合次梯度定义。

三步走到尖角

算法在每一步选 $g_{k} \in \partial f (x_{k})$ ，然后令 $x_{k + 1} = x_{k} - α_{k} g_{k}$ ，其中 $α_{k} > 0$ 。从 $x_{0} = 2$ 开始最小化绝对值，依次用步长 $1, 1 / 2, 1 / 2$ ；前三次选择的次梯度都是 1，所以位置依次变成 $1, 1 / 2, 0$ 。到零时可选择次梯度 0，保持在那里。若从 $x = 0.2$ 使用固定步长 1，轨迹会在 $- 0.8$ 与 $0.2$ 间跳动，故“每一步都取一个次梯度”本身不保证函数值单调下降。

绝对值还解释了统计中的一种稳健拟合。要用一个数 $x$ 代表两次观测 1 和 3，若目标是总绝对偏差 $| x - 1 | + | x - 3 |$ ，那么在 $1 < x < 3$ 内，两项的次梯度分别是 1 和 -1，相加为零；两端也可各选一组合使和为零。因此整个区间 $[1, 3]$ 都是最小点，目标值为 2。区间外，两项变化方向相同，目标值严格增大。这与最小二乘法使用平方偏差、在本例得到唯一解 2 的情况不同。

加入一个明显偏远的观测 100，更能看出两种损失的区别：对 $1, 3, 100$ 的绝对偏差总和，在 $1 < x < 3$ 时斜率为 $- 1$ ，在 $3 < x < 100$ 时斜率为 $1$ ，所以最小点是中间数 3。平方偏差总和的导数是 $2 [(x - 1) + (x - 3) + (x - 100)]$ ，令它为零得 $x = 104 / 3$ 。这说明绝对偏差对一个极端观测的影响较小；它并不意味着任何数据分析都应改用绝对值，误差模型仍须与问题匹配。

误差界从距离平方得到

设 $x^{*}$ 是最优点，且沿迭代始终有 $‖ g_{k} ‖ \leq G$ 。展开一步的平方距离： $‖ x_{k + 1} - x^{*} ‖^{2} = ‖ x_{k} - x^{*} ‖^{2} - 2 α_{k} g_{k} \cdot (x_{k} - x^{*}) + α_{k}^{2} ‖ g_{k} ‖^{2} .$ 次梯度定义在 $y = x^{*}$ 时给 $g_{k} \cdot (x_{k} - x^{*}) \geq f (x_{k}) - f (x^{*})$ 。把它代回、从 $k = 0$ 加到 $T - 1$ ，左边的平方距离逐项抵消，再舍去末项这个非负数，得到 $min_{0 \leq k < T} {f (x_{k}) - f (x^{*})} \leq \frac{‖ x_{0} - x^{*} ‖^{2} + G^{2} \sum_{k < T} α_{k}^{2}}{2 \sum_{k < T} α_{k}} .$ 因此在有界次梯度等条件下，若步长满足 $\sum_{k} α_{k} = \infty$ 、 $\sum_{k} α_{k}^{2} < \infty$ ，右边趋向零，至少能保证历史中最好的函数值逼近最优值。这一结论不等于任意固定步长都使最后一个迭代点收敛。

Python 3 实现

以下代码专门求 $| x |$ 的例子，接受步长序列，返回每一步的位置；不改写步长输入。一般凸函数需要调用者提供一个合法次梯度选择器。

Python 3

def subgradient_absolute(start, rates):
    x = float(start)
    history = [x]
    for rate in rates:
        if rate <= 0:
            raise ValueError("every step size must be positive")
        g = 1.0 if x > 0 else (-1.0 if x < 0 else 0.0)
        x -= rate * g
        history.append(x)
    return x, history


if __name__ == "__main__":
    point, path = subgradient_absolute(2, [1, 0.5, 0.5])
    assert path == [2.0, 1.0, 0.5, 0.0]
    assert point == 0.0

运行 $T$ 步需 $O (T)$ 时间，保存历史需 $O (T)$ 空间；只返回末点则可用常数额外空间。有可行域时通常把一步的结果再投影，见投影梯度法；证明误差界时还要利用投影不会增大到最优点的距离。

参考资料

Stanford EE364b《Subgradient Methods》，含次梯度法的步长与误差界。
MIT 6.253 凸分析讲义，第15讲讨论次梯度及其收敛。