梯度下降收敛定理

一般光滑凸情形的证明把每轮函数值误差“支付”给到解的平方距离下降；距离预算只有初始的 $\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 )$。若初始误差已经不超过 $\epsilon >0$，无需迭代。否则，当 $0<\mu <L$ 时，强凸界给 $k=O(\kappa \log ((f(x_0)-f^{\ast })/\epsilon ))$；当 $\mu =L$ 时，一步就使函数值达到最优。前者依赖到某个解的初始距离，后者依赖条件数；若论文或程序只报轮数而隐去这两个尺度，就无法横向比较。

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

对线性平方损失，还能进一步说明收敛到哪一个最小者。线性回归的隐式偏置理路线性平方损失的隐式偏置Implicit bias in linear regression · Gradient descent minimum-norm bias · 线性回归隐式正则化证明固定步长梯度下降在任意线性平方损失上保留初始零空间分量，并选择离初值最近的最小二乘解。逐个分析正奇异方向，并证明零空间分量保持初值；即使目标不强凸，也能在可达仿射空间中得到具体极限和收缩率。

梯度精确，却来自旧版本时 ​

本页两种速率都在当前点查询 $\mathrm{\nabla }f(x_k)$。若改用旧完整版本 $\mathrm{\nabla }f(x_{r_k})$，仅有“仍是精确整梯度”不够：原来消掉的内积会留下当前与旧梯度的差。即使一维 $f(x)=x^2/2$，步长 $3/2$ 在零延迟时每步乘 $-1/2$，而固定一阶延迟的特征根模为 $\sqrt{3/2}>1$，会失去稳定性。

有界延迟梯度下降理路有界延迟梯度下降Bounded-delay gradient descent · Coherent stale-gradient descent对完整旧版本的精确梯度，用带权更新历史证明任意有界延迟下的末点几何界，并核验固定延迟稳定边界、版本不变量与实际费用。单独维护最近位移的加权能量。在全局光滑强凸、完整快照、年龄至多 $\tau$、更新加到当前点且没有覆盖丢失的条件下，步长 $\alpha \le 1/[2L(\tau +1)]$ 给末点目标差 $(1-\alpha \mu {)}^k{\mathrm{\Delta }}_0$。这份充分保证允许目标局部回升，不能沿用本页凸情形中依赖目标单调的求和步骤。

例如 $L=4,\mu =1,{\mathrm{\Delta }}_0\le 5/2$，延迟上界2时取 $\alpha =1/24$，要由该界认证目标差 $1/100$，130次提交足够；上界改成5后，步长和预算分别改为 $1/48$ 与263次。计数是整梯度更新数，不是设备数或墙钟加速比。旧结果的零梯度也不能认证当前点，应另查当前梯度并按强凸误差界验证。版本日志练习给出完整复算与成本账。