梯度下降收敛定理

一般光滑凸情形的证明把每轮函数值误差“支付”给到解的平方距离下降；距离预算只有初始的 $\Vert x_0-x^{\ast }{\Vert }^2$，求和后再除以轮数，便得到 $1/k$。这里没有统一曲率下界，目标在解附近可以很平，因而不能从同一假设榨出固定比例的误差缩减。

强凸性补上这一缺口：函数值差大时，梯度范数也必须按比例大；下降引理又把梯度范数变成实际函数值减少，于是每轮至少消去当前误差的 $\mu /L$。条件数 $\kappa =L/\mu$ 表示上下曲率的不匹配，$1-1/\kappa$ 越接近一，几何收缩越慢。所谓“线性收敛”指误差按固定比例缩小，而不是函数图像或算法更新是线性的。

仍取

其 $L=4$、$\mu =1$。从 $x_0=(1,1)$ 以 $1/L$ 更新，精确轨迹为 $x_k=((3/4{)}^k,0)$（$k\ge 1$），故

定理给出的强凸上界是 $(3/4{)}^{k}f(x_0)=(3/4{)}^k(5/2)$；实际因高曲率坐标首步消失而快得多。上界描述最坏目标族，不应拿单个容易二次型的更快轨迹宣称定理常数错误，也不应把上界写成每个问题都取等号。

函数值与迭代点必须区分。对 $f(x_1,x_2)=x_1^2/2$，取步长一后，函数值一步到最优，但 $x_2$ 永远保持初值；最优解本就不是唯一。若只知凸而无强凸，函数值收敛不能指定点收敛到某个预选解。步长取到 $2/L$ 在二次最大曲率方向可持续振荡，超过则发散。若梯度有噪声、$L$ 被低估、解不存在或目标非凸，上述两个确定性全局率均不能直接套用。

一般凸界要求

即可保证函数值误差不超过 $\epsilon$，所以复杂度是 $O(L{R}^2/\epsilon )$。强凸界则给 $k=O(\kappa \log ((f(x_0)-f^{\ast })/\epsilon ))$。前者依赖到某个解的初始距离，后者依赖条件数；若论文或程序只报轮数而隐去这两个尺度，就无法横向比较。

固定步长的函数值率还能转成其他证书，但方向有条件：光滑性给梯度范数上界，强凸性再把函数值差换成点误差。对受约束或复合目标，应改用投影梯度映射或近端梯度映射，普通 $\Vert \mathrm{\nabla }f(x_k)\Vert$ 可能在边界最优点不为零。加速法将一般凸的 $1/k$ 提升到 $1/k^2$，代价是额外状态且函数值未必逐轮下降。