近似近端梯度的误差预算

精确prox会让模型的梯度与惩罚次梯度完全平衡。式(1)允许有一小段“未平衡力”，但把它的大小记录下来。外层每轮为这段力支付至多 $R{\delta }_k$，因此误差不是消失了，而是进入最终账本。

令

式(1)正是给出了 $e_{k+1}\in \partial Q_k(z)$。强凸子问题还有两个可用推论：若精确解为 $p_k$，则 $\Vert z-p_k\Vert \le \alpha \Vert e_{k+1}\Vert$；且 $Q_k(z)-Q_k(p_k)\le \alpha \Vert e_{k+1}{\Vert }^2/2$。第一条由强单调性与Cauchy–Schwarz得到；第二条由强凸下界对比较点最小化得到。因此一个小残差确实控制内层点和内层值，但反方向不能随意使用。

固定容差造成真实偏移 ​

取 $F(x)=(x-2{)}^2/2+|x|$，最优点 $x^{\ast }=1$，最优值 $3/2$。令 $\alpha =1/2$、$x_0=1$，内层总返回正点并取 $s=1$，使残差恒为 $e=1/10$。式(1)变成

于是 $x_1=21/20$、$x_2=43/40$，一般地 $x_k=11/10-(1/10)2^{-k}$，趋于 $11/10$。由于正半轴上 $F(x)-F^{\ast }=(x-1{)}^2/2$，极限目标误差为 $1/200$。每次内层都满足同一个小容差，仍会留下不消失的外层误差。

若已知初始距离不超过1、$R=2$、$\alpha =1/2$，要求式(2)的右侧不超过 $0.02$，可取 $T=100$，并选 ${\delta }_k=1/(4k^2)$。用 $\sum _{k=1}^{\mathrm{\infty }}{k}^{-2}\le 1+{\int }_1^{\mathrm{\infty }}{t}^{-2}dt=2$，得上界 $1/100+1/100=0.02$。这是一份可检查的外层预算；是否能经济地实现后期很小的残差，仍要看内层求解器。

很小的目标误差不保证很小的次梯度残差 ​

取 $Q(u)=|u|+u^2/2$，精确最小点为零。令 $z=\epsilon >0$，则 $Q(z)-Q(0)=\epsilon +{\epsilon }^2/2\to 0$；但 $\partial Q(z)=\{1+\epsilon \}$，最小次梯度范数反而趋于1。靠近尖点的目标值可以非常准确，而普通次梯度残差依然大。

若只有 $Q_k(z)-min{Q}_k\le {ϵ}_k$，强凸性只能直接给 $\Vert z-p_k\Vert \le \sqrt{2\alpha {ϵ}_k}$。要把这个误差传入外层，应使用相应的点扰动或 $ϵ$-次微分分析，不能把 ${ϵ}_k$直接当作式(1)的 ${\delta }_k$。具体说，$s\in {\partial }_{ϵ}h(z)$表示对全部 $u$有 $h(u)\ge h(z)+⟨s,u-z⟩-ϵ$。若内层给出这一证据，并在式(1)中使用该 $s$，则下面一步式右侧额外加 $ϵ$，平均界额外加各轮 $ϵ$的平均。仅有 $Q_k$的目标误差不等于已经给出了这份关于 $h$的证据。残差、目标误差和 $ϵ$-次梯度是三种不同接口。

一步不等式与完整累计 ​

由式(1)，有 $s=e-\mathrm{\nabla }g(x)+(x-z)/\alpha \in \partial h(z)$。任取 $u\in \mathrm{dom}h$，用其次梯度不等式、$g$的凸下界与光滑上界理路下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。相加，得到

这里误差内积的正号来自 $s=e-\mathrm{\nabla }g(x)+(x-z)/\alpha$；若把残差定义改成相反方向，必须同步改符号。取 $u=x^{\ast }$，因 $\alpha \le 1/L$ 可丢掉非正位移项，再以距离上界估计最后一项不超过 $R{\delta }_{k+1}$。

从 $k=0$ 到 $T-1$ 求和，平方距离望远镜消去；去掉最后的非负距离，并由Jensen不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。将平均函数值换成平均点函数值，便得到式(2)。证明没有使用目标单调，因此不能把平均点保证自动替换为最后一点保证。

若 $\sum _k{\delta }_k<\mathrm{\infty }$，式(2)保持 $O(1/T)$；若 ${\delta }_k=d/k$，得到 $O((1+\log T)/T)$；若固定 ${\delta }_k=d$，该账本只给额外的 $Rd$。这里只讨论不加速版本，FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。的增长权重会改变误差累计要求，不能把同一容差表直接搬过去。

内外层费用与误差位置 ​

若第 $k$ 轮内层为达到 ${\delta }_k$用了 $N_k$ 次工作，总费用要报告 $T$次光滑梯度、$\sum _k{N}_k$ 次内层工作以及次梯度证据的计算成本。若模型本身的梯度也近似，那个误差需一同计入式(1)，并说明是否可确定地上界。

ADMM理路交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。的两份近端子问题也可能采用内层求解，但其外层势与本页不同。本文的 $R\sum {\delta }_k$结论只属于这里的近端梯度协议，不是给所有拆分算法通用的许可。旧近端点方法理路近端点方法Proximal point method · Proximal point algorithm反复精确求解带二次稳定项的子问题以逼近闭凸函数最小点的方法。已经给出prox点误差可求和时的点收敛条件，并展示近似点离解很近却处于有效域之外的反例；本页新增的是复合子问题残差、有效域内候选和有限预算目标平均界。

两道短自测 ​

1. 在式(2)中取初始距离上界1、$\alpha =1/2,R=2,T=100$、各轮 ${\delta }_k=0.01$，可报告多大界？答案：$0.01+2\cdot 0.01=0.03$，增加 $T$只消除第一项。
2. 内层给 $Q(z)-Q^{\ast }\le {10}^{-8}$，是否能直接填 $\delta ={10}^{-8}$？答案：不能；这是目标误差，尖点例说明普通次梯度残差仍可接近1。必须取得式(1)证据，或换用与目标容差匹配的分析。