有界延迟梯度下降 | Codeboy's Blog

形式陈述

沿用梯度下降收敛定理的欧氏目标： $f:\mathbb R^d\to\mathbb R$ 全局可微、 $\mu$ -强凸、梯度全局 $L$ -Lipschitz， $0<\mu\le L$ 。强凸下界使 $f$ 强制增长，连续性保证极小点存在，强凸性保证其唯一；记为 $x^*$ ， $f^*=f(x^*)$ 。本页所有梯度和算术精确。

输入初值 $x_0$ 、整数延迟上界 $\tau\ge0$ 、常步长 $\alpha>0$ 、提交预算 $T\ge0$ ，以及实际读取的版本号 $r_k$ 。第 $k$ 次提交执行

\max(0,k-\tau)\le r_k\le k,\qquad d_k=k-r_k,\qquad x_{k+1}=x_k-\alpha\nabla f(x_{r_k}),\quad 0\le k<T.\tag{1}

$k$ 数的是已经原子提交的更新，不是秒数、设备数或通信轮数。一次查询必须读取同一个版本的完整向量；延迟可随轮变化，甚至由对手选择。不同结果可以乱序完成，但每个被接受的结果都加到当前 $x_k$ 上，不能把旧的 $x_{r_k}-\alpha\nabla f(x_{r_k})$ 覆盖回来。启动阶段不读取负版本，故必须有 $d_k\le\min(k,\tau)$ 。

一个带初值系数一的充分保证

若

0<\alpha\le\frac1{2L(\tau+1)},\qquad q=1-\alpha\mu,\tag{2}

则对每条满足式(1)的版本历史、每个 $k\ge0$ ，

\Delta_k:=f(x_k)-f^*\le q^k\Delta_0, \qquad \|x_k-x^*\|^2\le\frac{2q^k\Delta_0}{\mu}.\tag{3}

这是确定性的末点界。它不要求目标值逐轮下降，也不是期望界或最锐安全步长。以下完整证明给出本页自行推导的保守常数，不能将它署为参考论文中的某个定理。

返回 $x_T$ 、提交/读取版本日志、声明的 $\mu,L,\tau,\alpha$ 、实际整梯度查询数及状态。应区分“版本无效”“数值非有限”“参数未通过本定理条件”“预算完成且具有先验界”“当前点残差已认证”。参数越界不等于已经发散，参数通过也不免除对全局曲率与完整读取的核实。

直觉

旧梯度在它的查询点完全正确，却可能已经不是当前点的下降方向。误差

e_k=\nabla f(x_{r_k})-\nabla f(x_k)

由两点之间尚未计入的更新产生。因此应记录最近 $\tau$ 个实际位移；每个新位移入队后，其权重逐轮下降，直到离开窗口。支付延迟误差的不是“它平均为零”，而是这份可以移位求差的历史能量。

提交5读取旧版本4，其完整梯度加到当前版本5后产生版本6；另一条支路保留真实位移并将历史权重从旧到新移位，红色覆盖写入被排除 — 读旧版本、更新当前版本、收缩带权历史

图中取后文算例的 $\tau=2$ 。当前提交5读取版本4；此前提交3读取版本3，紧接着提交4反而读取版本2，显示读取版本不必单调。灰色线连的是已提交状态，蓝色线传递旧版本梯度，绿色线显示实际位移入历史窗口。红色说明标出另一种会丢失更新的写入语义，不属于式(1)。

SGD的方向要求相对于当前历史条件无偏；本页旧整梯度通常相对于当前点有偏。SAGA则用当前查询和旧表作校正，恢复条件无偏。三者可以都“保存过去的信息”，但证明接口不同。

例子与边界

带权历史的完整收缩证明

先设 $\tau\ge1$ 。写 $g_k=\nabla f(x_k)$ 、 $h_k=\nabla f(x_{r_k})$ ，真实位移 $s_j=x_{j+1}-x_j$ （ $j\ge0$ ）；仅为历史求和规定 $s_j=0$ （ $j<0$ ），这不是增加负时间查询。由下降引理及极化恒等式， $s_k=-\alpha h_k$ 给出

\begin{aligned} \Delta_{k+1}-\Delta_k &\le-\alpha\langle g_k,h_k\rangle+\frac{L\alpha^2}{2}\|h_k\|^2\\ &=-\frac\alpha2\|g_k\|^2-\left(\frac1{2\alpha}-\frac L2\right)\|s_k\|^2 +\frac\alpha2\|g_k-h_k\|^2. \end{aligned}\tag{4}

旧梯度与当前梯度之差沿真实读取间隔展开。由Cauchy–Schwarz，

\begin{aligned} \|g_k-h_k\|^2 &\le L^2\left\|\sum_{j=r_k}^{k-1}s_j\right\|^2 \le L^2d_k\sum_{j=r_k}^{k-1}\|s_j\|^2\\ &\le L^2\tau\sum_{i=1}^{\tau}\|s_{k-i}\|^2. \end{aligned}\tag{5}

空和取零。强凸一阶下界对比较点取最小值，给 $f^*\ge f(x_k)-\|g_k\|^2/(2\mu)$ ，即 $\|g_k\|^2\ge2\mu\Delta_k$ 。定义

c=\alpha L^2\tau,\qquad H_k=c\sum_{i=1}^{\tau}(\tau+1-i)\|s_{k-i}\|^2,\qquad E_k=\Delta_k+H_k.\tag{6}

移动窗口的恒等式是

H_{k+1}-H_k=c\tau\|s_k\|^2-c\sum_{i=1}^{\tau}\|s_{k-i}\|^2.\tag{7}

式(4)–(7)相加，得

E_{k+1}-E_k\le-\alpha\mu\Delta_k -\frac c2\sum_{i=1}^{\tau}\|s_{k-i}\|^2 -B\|s_k\|^2,\qquad B=\frac1{2\alpha}-\frac L2-c\tau.\tag{8}

核对两个系数，不能只丢掉 $H_k$ 就宣称它也收缩。令 $a=\alpha L$ ，由式(2)，

a+2a^2\tau^2 \le\frac1{2(\tau+1)}+\frac{\tau^2}{2(\tau+1)^2}\le1,

故 $B\ge0$ 。另一方面， $H_k\le c\tau\sum_i\|s_{k-i}\|^2$ ，且 $\alpha\mu\le1/[2(\tau+1)]\le1/(2\tau)$ ，所以

\frac c2\sum_i\|s_{k-i}\|^2\ge\frac{H_k}{2\tau}\ge\alpha\mu H_k.

代回式(8)便得 $E_{k+1}\le qE_k$ 。启动时 $H_0=0$ ，故 $E_0=\Delta_0$ ；再用 $\Delta_k\le E_k$ ，即证式(3)及其初值系数一。点误差界来自强凸二次增长。

$\tau=0$ 时另证，避免除以零。此时 $r_k=k$ 、 $\alpha\le1/(2L)$ ，普通下降估计给

\Delta_{k+1}\le\Delta_k-\alpha(1-\alpha L/2)\|g_k\|^2 \le(1-\alpha\mu)\Delta_k.

零延迟的更锐 $1/L$ 结论仍见原收敛页。本页选同一保守公式是为了覆盖任意允许的延迟历史。

六次提交：完整版本真的改变了轨迹

取 $f(x)=(x_1^2+4x_2^2)/2$ 、 $x_0=(1,1)$ ，则 $\mu=1,L=4$ 。设 $\tau=2,\alpha=1/24$ ，依次使用延迟 $(0,1,2,0,2,1)$ ，即读取版本 $(0,0,0,3,2,4)$ 。精确轨迹为

\begin{aligned} x_1&=(23/24,5/6),&x_2&=(11/12,2/3),&x_3&=(7/8,1/2),\\ x_4&=(161/192,5/12),&x_5&=(461/576,11/36),&x_6&=(3527/4608,17/72). \end{aligned}

例如提交4读取 $x_2$ ，故 $s_4=-(1/24)(11/12,8/3)=(-11/288,-1/9)$ ；更新从 $x_4$ 开始，而非从 $x_2$ 开始。终点有

\Delta_6=\frac{17174705}{42467328},\quad H_6=\frac{91627}{2654208},\quad E_6=\frac{2071193}{4718592},\quad q^6\Delta_0=\frac{740179445}{382205952},\qquad q=\frac{23}{24}.

能量与目标差是不同的数；此例的实际误差远小于最坏历史上界，并不改变定理。

固定标量延迟：精确稳定区间与真正反例

令 $f(x)=\lambda x^2/2$ ， $\lambda>0$ ， $a=\alpha\lambda$ 。固定延迟的线性递推

x_{k+1}=x_k-a x_{k-\tau},\qquad p(z)=z^{\tau+1}-z^\tau+a\tag{9}

对所有初始历史都渐近稳定，当且仅当

0<a<2\sin\frac\pi{4\tau+2}.\tag{10}

这条精确边界只属于固定延迟标量模型，不是任意非线性目标、变延迟的式(2)。其证明如下。充分小的 $a>0$ 时，近1的根为 $1-a+O(a^2)$ ，其余 $\tau$ 个根近0，全部在单位圆内。令圆上的根为 $z=e^{i\theta}$ ， $0<\theta<2\pi$ 。由 $a=z^\tau(1-z)$ ，正实数条件为

(\tau+1/2)\theta-\pi/2\in2\pi\mathbb Z,\qquad a=2\sin(\theta/2).

第一次交圆发生在 $\theta=\pi/(2\tau+1)$ 或其共轭，得到式(10)的上端点。圆上根均为单根，因为 $p'(z)=z^{\tau-1}[(\tau+1)z-\tau]$ 不会在那里为零。隐式求导还给

\operatorname{Re}\frac{a z'(a)}z =\frac{(2\tau+1)(1-\cos\theta)}{|\tau-(\tau+1)e^{i\theta}|^2}>0.

因此所有交圆都向外，不能越过端点后重新全部稳定。端点有不衰减模式； $a=0$ 有根1， $a<0$ 在1以上有实根。 $\tau=0$ 直接由 $z=1-a$ 得到相同公式。

特别地， $\tau=1$ 时根为 $(1\pm\sqrt{1-4a})/2$ 。当 $0<a<1/4$ ，两实根在 $(0,1)$ ； $a=1/4$ 为重根 $1/2$ ，其 $k(1/2)^k$ 模式也衰减； $a>1/4$ 时共轭根模为 $\sqrt a$ 。所以稳定区间恰为 $0<a<1$ 。

取合法启动 $d_0=0$ ，之后 $d_k=1$ ， $x_0=1$ 。 $a=3/2$ 在零延迟时每步乘 $-1/2$ ，却在一阶延迟时具有模 $\sqrt{3/2}>1$ 的两个根，真实序列开始为

1,-1/2,-2,-5/4,7/4,29/8,1,-71/16,\ldots.

非零初始状态激发至少一个不稳定模式，故不可能趋于0。这是真正的不稳定反例，不只是没有通过某个充分条件。边界 $a=1$ 则产生周期 $1,0,-1,-1,0,1,\ldots$ ：在当前 $x_2=-1$ 时，版本1的旧梯度恰为零，当前目标差仍为 $1/2$ 。旧梯度为零不能认证当前点。

将 $a=3/4$ 从 $\tau=1$ 移到 $\tau=2$ 也会改变结论：前者稳定，后者超过 $2\sin(\pi/10)=(\sqrt5-1)/2$ 。此时 $p(z)=z^3-z^2+3/4$ 在 $(-1,0)$ 有唯一实根；对 $z\ge0$ ，最小值 $p(2/3)=3/4-4/27>0$ ，故另外两根必为共轭对。负实根的模小于一，而已越过式(10)的首次外向交圆边界，故共轭对不稳定。合法夹紧启动的 $x_1=1/4$ 不等于这个负实根乘 $x_0$ ，所以它也激发不稳定共轭模式。为 $\lambda=1,\tau=2$ 改取 $\alpha=1/6$ ，则重新满足任意变延迟的充分保证。

即使满足式(2)，目标仍可短暂回升： $f(x)=x^2/2$ 、 $x_0=1$ 、 $\tau=2$ 、 $\alpha=1/6$ 、 $d_k=\min(k,2)$ 时， $x_{13}=-7/7776$ 、 $x_{14}=-1/432$ ，所以 $f(x_{14})>f(x_{13})$ 。此时带权能量继续收缩，不能删去历史项改说目标单调。

哪些工程变化需要另一个定理

坐标来自不同版本时不存在式(5)的单个 $r_k$ ；覆盖当前值会改变式(1)；梯度压缩、舍入误差、噪声、客户端局部目标或局部多步也会产生本页没有控制的项。延迟无界时有限窗口恒等式失效。全局 $\mu,L$ 也不能由若干采样点的曲率估计替代。这里没有把“异步”当成免检标签，更没有声称任意调度都带来加速。

推论与应用

预算与当前点停止证书

已知合法上界 $B_0\ge\Delta_0$ ，若 $B_0\le\varepsilon$ ，无需更新；若 $B_0>\varepsilon>0$ ，足够的提交数为

T=\left\lceil\frac{\log(B_0/\varepsilon)}{-\log(1-\alpha\mu)}\right\rceil.\tag{11}

不知道 $f^*$ 时不能偷偷计算 $\Delta_0$ 。一个合法替代是另查初始当前梯度，取 $B_0=\|\nabla f(x_0)\|^2/(2\mu)$ ；这次查询必须计费，若首个梯度完整缓存且可复用则只计一次。运行后新查一次当前 $x_T$ 的精确梯度，能认证

f(x_T)-f^*\le\frac{\|\nabla f(x_T)\|^2}{2\mu}.

这是新的当前点证书；旧梯度日志不自动提供它。由于式(3)对所有整数 $k$ 路径式成立，在同一有效模型内选择某个已提交时刻不会引入统计多次检验问题；但不能据此把有噪声验证也升级为任意停止保证。

保留 $\mu=1,L=4,B_0=5/2,\varepsilon=1/100$ ，每次取式(2)的最大充分步长： $\tau=1,2,5$ 分别得到 $\alpha=1/16,1/24,1/48$ ， $q=15/16,23/24,47/48$ ，式(11)预算为86、130、263次提交。延迟上界从2变5后，旧步长和130次预算都不再由本计算认证；减小步长修复条件，还须重算预算。

版本不变量与完整费用

简单回放器保存最近 $\tau+1$ 个带版本号的完整向量，空间 $O((\tau+1)d)$ 。每次提交先核对结果的版本号、完整快照与年龄，再把 $-\alpha h_k$ 加到当前值，产生新版本，最后淘汰过旧快照。历史证书另存最近 $\tau$ 个位移即可；移位的权重属于证明，不改变更新。

$T$ 次提交在本页回放模型中需要 $T$ 次整梯度求值及 $O(Td)$ 向量运算；本页六步示例重复读取同一点时仍逐次查询，不暗算免费缓存。这里 $O(Td)$ 仅指更新本身；教学读数器逐轮重算窗口能量，另需 $O(T\tau d)$ 历史诊断运算。真实异步系统若还计算了过旧而被拒绝或最终未用的梯度，这些查询也须计入实际总费用，不能只报被接受的 $T$ 次。初始证书与最终当前梯度验证按实际复用另加。有限和整梯度需要遍历全部分量，不能计成一条SGD样本。保留全部教学日志另需 $O(Td)$ 空间；它不是上述滚动回放器的必需状态。真实并行执行还须另报在途梯度、快照复制、通信量与墙钟时间。仅给 $\tau$ 不能推出并行加速比。

完整练习与答案要求从版本日志重算精确轨迹、历史能量和查询账，构造错误覆盖写入及过时停止，再改变延迟上界重配预算。有理数读数器只依赖Python标准库，有限检查支持复算，不替代上面的全局证明。

参考资料

Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，arXiv:1405.4980v2，2015-11-16，§3.2、Lemma 3.4（印刷267页）及§3.4：光滑上模型、强凸梯度下降背景。式(4)–(8)的延迟历史证明与式(2)常数由本页独立给出
Hyung Jun Choi、Woocheol Choi、Jinmyoung Seok，Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak–Łojasiewicz condition，arXiv:2308.11984v2，2024-02-22，§5、式(5.1)与Theorem 5.1，PDF15–18页：变延迟整梯度与历史差的分析背景。原文使用 $x_0=\cdots=x_\tau$ 的填充启动，并另有PL/随机噪声假设；本页不借用其噪声结论或直接替换其常数
Yossi Arjevani、Ohad Shamir、Nathan Srebro，A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates，ALT 2020，§3、Theorem 2，PDF8页（论文集页118）：原定理限定固定延迟二次目标，并要求 $k\ge(\tau+1)\ln(2(\tau+1))$ 。它提供二次递推背景，不证明本页任意变延迟结论；式(10)的精确根边界由本页交圆论证给出

形式陈述 ​

一个带初值系数一的充分保证 ​

带权历史的完整收缩证明 ​

六次提交：完整版本真的改变了轨迹 ​

固定标量延迟：精确稳定区间与真正反例 ​

哪些工程变化需要另一个定理 ​

预算与当前点停止证书 ​

版本不变量与完整费用 ​

反向链接