近端梯度法

拆分的依据是计算结构：$g$ 的梯度便宜，$h$ 的 prox 便宜。把更新配方，可见新点精确最小化

当 $\alpha \le 1/L$ 时，光滑凸性理路光滑凸函数Smooth convex function · L-smooth convex function同时具有凸性与全局 Lipschitz 梯度的函数类，其曲率被零与有限上界夹住。与下降引理理路下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。保证这是一份接触当前目标值的二次上界。它线性化光滑项，却完整保留惩罚的尖角，所以能产生精确零坐标。

图中选取 $\alpha h(x)=\Vert x{\Vert }_1$，故近端步是阈值为 $1$ 的逐坐标软阈值：$(2.1,-0.3,0.2,1.4)\mapsto (1.1,0,0,0.4)$。

当 $h=0$，prox 是恒等映射；当 $h$ 是集合指标函数，prox 是投影。步长约束来自 $g$ 的曲率，不需要为非光滑的整个 $F$ 编造 Hessian。若每轮改为对整个 $F$ 求 prox，就变成近端点方法理路近端点方法Proximal point method · Proximal point algorithm反复精确求解带二次稳定项的子问题以逼近闭凸函数最小点的方法。，通常会得到另一个、更难的子问题。

一维收缩与耦合回归 ​

保留最简单的计算作为起点：$F(x)=(x-3{)}^2/2+|x|$，$L=1$。从 $x_0=0$ 取 $\alpha =1/2$，软阈值 $S_{\tau }(z)=\mathrm{sign}(z)(|z|-\tau {)}_{+}$ 给出

目标值依次为 $4.5,3,2.625,2.53125$，趋向 $x^{\ast }=2$ 的 $F^{\ast }=2.5$。若取 $\alpha =1$，梯度候选恒为 $3$，于是一步到解。这里二次项恰好消除了初值影响；一般设计矩阵的列相互耦合时，不会如此。

具体地，令

此时 $A^{T}A=\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ 的最大特征值为 $3$，可以取 $\alpha =1/3$。从零开始，前三个迭代点为 $(2/3,1/6)$、$(5/6,0)$、$(17/18,0)$。第二步恰把处于阈值边界的第二坐标送到零。完整候选计算、零坐标最优性与逐轮误差证书见Lasso 的最优性与对偶间隙理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。；那里同时说明为何不能先求最小二乘解再一次软阈值。

同一组数据也可用交替方向乘子法（ADMM）理路交替方向乘子法（ADMM）Alternating direction method of multipliers · ADMM将凸目标拆成两个近端子问题，用乘子累积一致性误差，并以原始与对偶残差检查最优性的算法。求解：它对平方损失精确解一个耦合线性系统，对复制变量做软阈值，再累积两份变量的不一致量。近端梯度在这里使用显式梯度候选，ADMM 则保留完整二次损失；该页给出四轮分数计算，并说明为什么停止时需要同时检查原始残差与对偶残差。

步长与结论的边界 ​

“小于安全上界”不意味着累积推进足够。令 $h=0$、$g(x)=x^2/2$、${\alpha }_k=2^{-k-2}$，则

这些步长均不超过 $1/L=1$，但和有限。因为 $0\le {\alpha }_j\le 1/4$，有 $\log (1-{\alpha }_j)\ge -2{\alpha }_j$，所以无穷乘积严格为正；非零初值不会趋于最优点零。这就是本页明确固定正步长的原因。

过大步长也可能破坏下降。对上面的耦合例取 $\alpha =1$，第一步是 $(2,1/2)$，目标值从 $9/4$ 升到 $13/4$。这展示一个实际失败，不表示每个 $\alpha >1/L$ 都必然失败。若用回溯，应检验光滑二次上界并另行说明步长规则；若 prox 仅近似求解，应控制内层误差；若 $g$ 非凸，固定点一般只认证驻点。

三点不等式如何产生下降与速率 ​

记 $y={\mathrm{prox}}_{\alpha h}(x-\alpha \mathrm{\nabla }g(x))$。最优性条件给出

任取 $z\in \mathrm{dom}h$，次梯度不等式给 $h(y)-h(z)\le ⟨s,y-z⟩$；凸性给 $g(x)-g(z)\le ⟨\mathrm{\nabla }g(x),x-z⟩$；光滑性给 $g(y)-g(x)\le ⟨\mathrm{\nabla }g(x),y-x⟩+L\Vert y-x{\Vert }^2/2$。相加后，梯度内积消去，剩下 $⟨x-y,y-z⟩/\alpha +L\Vert y-x{\Vert }^2/2$。再用三点平方恒等式，得到

先取 $z=x$。前一个分式本身又贡献一份负平方项，所以

即使 $\alpha =1/L$，只要新旧点不同仍有严格下降。再取任一最小点 $z=x^{\ast }$，舍去三点不等式末尾的非正项，从 $j=0$ 到 $k-1$ 求和便有

这一步首先控制的是一串函数值差的和。由于刚刚证明了函数值单调，每个求和项都不小于最后一项 $F(x_k)-F^{\ast }$，故

点收敛需要再走一步。三点不等式与 $F(x_{k+1})\ge F^{\ast }$ 表明，到每个最小点的距离不增，这称为 Fejér 单调性，因而序列有界。下降估计还给 $\sum _k\Vert x_{k+1}-x_k{\Vert }^2<\mathrm{\infty }$，故相邻差趋零。有限维有收敛子列 $x_{k_j}\to \overline{x}$；prox 是连续映射，梯度也连续，固定步长更新与相邻差趋零便推出 $\overline{x}={\mathrm{prox}}_{\alpha h}(\overline{x}-\alpha \mathrm{\nabla }g(\overline{x}))$。所以 $\overline{x}$ 是最小点。最后，到这个 $\overline{x}$ 的距离不增且有子列趋零，整个序列都趋于 $\overline{x}$。这一论证没有假设 $h$ 在定义域边界连续。

计算成本与可以认证的对象 ​

对 $m\times n$ 矩阵的平方损失，梯度通过 $Ax$ 和 $A^T(Ax-b)$ 计算，连同残差与输出向量操作，稠密实数算术成本为 $O(1+mn+m+n)$，在 $m,n\ge 1$ 时可简写为 $O(mn)$；若稀疏表示实际保存 $s$ 个条目（包括显式零和重复坐标），稀疏实现为 $O(1+s+m+n)$，逐坐标软阈值另需 $O(n)$。不必形成可能稠密的 $A^{T}A$。要报告新点处的残差与对偶证书，还需新点的矩阵向量乘法、转置乘法及 $O(1+m+n)$ 的范数和内积检查；可以与下一轮梯度共享这些结果。

FISTA 在相应凸条件下将函数值界改善为 $O(1/k^2)$，但需新的加速权重与势函数，且通常不逐轮下降。函数值收敛、迭代点收敛与有限步识别支持集是不同结论；上述一般 $O(1/k)$ 证明没有提供统计意义的变量恢复保证。Moreau 包络理路Moreau 包络Moreau envelope · Moreau-Yosida regularization以二次 infimal convolution 将闭凸函数平滑化并保留其极小点的函数。则对整个函数做平滑，虽然也出现 $x-\mathrm{prox}(x)$，仍应与这里的拆分子问题区分。

把复合残差转换成可核验的停止条件 ​

梯度映射 $G_{\alpha }(x)$检查的是旧点 $x$的固定点偏差；要在新点 $z={\mathrm{prox}}_{\alpha h}(x-\alpha \mathrm{\nabla }g(x))$构造真正的目标次梯度，可用

第一式来自prox最优性给出的 $G_{\alpha }(x)-\mathrm{\nabla }g(x)\in \partial h(z)$，再加上 $\mathrm{\nabla }g(z)$。若已知 $\Vert z-x^{\ast }\Vert \le R$，次梯度下界和Cauchy–Schwarz给 $F(z)-F^{\ast }\le R\Vert v\Vert$。若整个 $F$具有$\mu$-强凸性理路强凸性Strong convexity · Strongly convex function函数在一阶凸下界之外还保留统一二次增长量的曲率性质。，对其二次下界最小化，则得到 $F(z)-F^{\ast }\le \Vert v{\Vert }^2/(2\mu )$。二者都需要明确的距离或曲率信息；仅有一个很小的残差数不够。

例如 $F(x)=\mu x^2/2$，在 $x=\delta /\mu$处梯度为 $\delta$，目标差却为 ${\delta }^2/(2\mu )$，可在 $\mu$很小时很大。若只看位移，则 $F(x)=x^2/2,x=1,\alpha ={10}^{-12}$给约 ${10}^{-12}$的位移，目标差仍约 $1/2$。步长缩小能够制造小位移，不能制造同等精度的最优性。

对Lasso，优先使用可行原对偶gap理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。直接上界目标差，不需要猜最优点距离。坐标下降理路Lasso 坐标下降Lasso coordinate descent · Lasso cyclic coordinate minimization用部分残差和列范数逐坐标精确最小化 Lasso，并保持残差缓存与可行对偶证书一致。和FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。都可以产生候选，再使用同一证书；安全筛除理路Lasso 的间隙安全筛除Gap Safe screening for Lasso · Lasso safe sphere screening把可行原对偶间隙转成最优对偶点的安全球，再以严格列判据证明某坐标在所有 Lasso 最优解中为零。进一步将gap转成可永久删列的严格判据。这里的停止接口仍完整保留，方法选择不会改变证书含义。

若prox只有近似解，需改用内层残差预算理路近似近端梯度的误差预算Inexact proximal gradient · Proximal subproblem residual budget用可核验的近端子问题次梯度残差分配内层精度，并把累计误差传到外层平均目标差。；若梯度带条件无偏噪声，需采用随机近端的平均输出保证理路随机近端梯度Stochastic proximal gradient · Stochastic forward-backward method对光滑项使用历史条件无偏梯度，对结构项精确做prox，以噪声方差和平均输出建立固定预算保证。。这两种误差不能仅凭“每轮看起来下降”省略。

结构项还可以作用于整组变量或矩阵奇异方向。组 Lasso理路组 Lasso 的块收缩与对偶证书Group Lasso proximal certificate · Block soft thresholding · 组软阈值对不相交变量组推导径向近端收缩，以整组残差相关性建立KKT和可行对偶间隙，并在耦合设计上认证停止。把本页的欧氏近端子问题变成块收缩，并以整组对偶球认证；带核惩罚的矩阵补全理路矩阵补全的优化间隙与唯一性证书Matrix completion certificate · Nuclear norm completion dual certificate · 核范数补全证书以掩码近端梯度求解带核惩罚的观测损失，用支持受限的谱范数对偶点认证误差，再以切空间严格证书证明精确补全唯一性。把光滑梯度换成观测掩码残差，保留未观测位置的当前猜测，再做奇异值软阈值。两者都逐项检查本页的凸性和固定步长条件，误差证书分别需要全组相关性或观测支撑内的谱范数约束。