FISTA 复合加速法

外推先沿上一段主点位移走得更远，再用一个新的近端子问题校正。第一轮 $t_1-1=0$，所以第二次查询仍在 $x_1$；从第三次查询开始才真正使用动量。

权重不是任选的“惯性强度”。恒等式 $t_{k+1}^2-t_{k+1}=t_k^2$ 使前后两轮的函数值权重对齐；外推式则使距离项对齐。只有这两份对齐共同成立，才能把局部模型不等式累积成式(2)。主点目标上升时，辅助距离项可以下降得更多，因此总势仍下降。

每轮固定 $L$ 需一次光滑梯度和一次精确 prox，加 $O(n)$ 外推；保存常数个向量。prox若内部很贵，外层 $O(1/k^2)$ 不是总运行时间。若只把内层调用记成“一步”，就遗漏了主要开销。

同一 Lasso 中的加速与过冲 ​

用耦合 Lasso理路Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。的数据

取 $L=3,x_0=0$，写 $Q=A^{T}A$、$c=A^{T}b$。式(1)的第一行是 $z_k=y_k+(c-Q{y}_k)/3$、$x_k=S_{1/3}(z_k)$。前两主点为 $(2/3,1/6)$ 和 $(5/6,0)$。$t_2=(1+\sqrt{5})/2$、$t_3=(1+\sqrt{1+4t_2^2})/2$，令 $\beta =(t_2-1)/t_3\approx 0.281753525$，则

第二个查询坐标为负，而新的主点第二坐标仍为零。用完全相同的残差缩放 $\theta =r/max(1,\Vert A^{T}r{\Vert }_{\mathrm{\infty }})$ 认证各主点，得到

第4轮真实目标继续下降，但这一固定构造给出的对偶下界变差，gap反而上升；第8轮连真实目标也比第7轮高。两件事都与式(2)相容。若所需 gap 是 ${10}^{-3}$，第3轮已可停止；继续计算并不承诺此后每个候选都通过同一门槛。保留最佳已认证候选是有用的输出策略，不等于改变式(1)的主序列。

未知曲率时的回溯规则 ​

给 $L_0>0$ 和倍率 $\eta >1$。第 $k$ 轮从 $L_{k-1}$ 开始，只乘以 $\eta$，直至 $p={\mathrm{prox}}_{h/\ell }(y_k-\mathrm{\nabla }g(y_k)/\ell )$ 满足

接受 $L_k=\ell ,x_k=p$，其余权重和外推仍按式(1)。只检验光滑项即可，不必在不可行的 $y_k$ 计算 $h(y_k)$。每轮会有限终止，且 $L_k$ 非递减并满足 $L_k\le max\{L_0,\eta L_g\}$。因此式(2)可把 $L$ 换为这个统一上界。若 $L_0$ 原本过大，不应无条件宣称上界只有 $\eta L_g$。

这个回溯版本允许沿用原来的 $t$ 递推，关键是接受值非递减。每轮先大幅降低 $L$、接受后却不调整加速权重，是另一算法，不能使用下面的证明。每次失败试探还需 prox 和函数值；梯度 $\mathrm{\nabla }g(y_k)$ 可以复用。浮点下模型未通过而达到回溯预算，应报告失败而非强行接受。

非光滑三点模型产生势函数 ​

记 $p={\mathrm{prox}}_{h/\ell }(y-\mathrm{\nabla }g(y)/\ell )$，假设式(3)成立。近端最优性给 $s=\ell (y-p)-\mathrm{\nabla }g(y)\in \partial h(p)$。把 $h(z)\ge h(p)+⟨s,z-p⟩$、$g(z)\ge g(y)+⟨\mathrm{\nabla }g(y),z-y⟩$ 与式(3)相加并展开平方，得到任意 $z\in \mathrm{dom}h$ 的

固定安全 $L$ 时，式(3)来自下降引理理路下降引理Descent lemma · Quadratic upper-bound lemma以 Lipschitz 梯度常数给出函数相对一阶模型的全局二次上界。。这里保留了 $h$ 的完整次梯度不等式，因此式(4)也适用于扩展实值惩罚，而不是对非光滑项做 Taylor 展开。

令 $v_k=F(x_k)-F^{\ast }\ge 0$，$u_k=t_k{x}_k-(t_k-1)x_{k-1}-x^{\ast }$。在第 $k+1$ 轮取 $t=t_{k+1}$ 和 $z=(1-1/t)x_k+x^{\ast }/t$。凸性给 $F(z)-F^{\ast }\le (1-1/t)v_k$；式(1)给

将式(4)乘以 $2t^2/L_{k+1}$，使用 $t(t-1)=t_k^2$，得到

最后一个不等式正使用 $L_{k+1}\ge L_k$ 与 $v_k\ge 0$。第一轮对式(4)取 $z=x^{\ast }$，得到势至多 $\Vert x_0-x^{\ast }{\Vert }^2$。递推式还给 $t_{k+1}\ge t_k+1/2$，由 $t_1=1$ 得 $t_k\ge (k+1)/2$。丢掉非负距离项，便完成固定步长与上述回溯版的函数值界。

证书和保证的分工 ​

式(2)用到通常未知的 $\Vert x_0-x^{\ast }\Vert$，适合解释最坏复杂度；实际停止可用Lasso可行gap或旧近端梯度页的残差转误差条件。小位移、两轮目标接近和若干零坐标均不能替代它们。

有误差的 prox、随机梯度或非凸 $g$ 会分别在近端最优性、确定模型或凸性插值步骤产生额外项。近似 prox 的误差预算理路近似近端梯度的误差预算Inexact proximal gradient · Proximal subproblem residual budget用可核验的近端子问题次梯度残差分配内层精度，并把累计误差传到外层平均目标差。与随机近端梯度理路随机近端梯度Stochastic proximal gradient · Stochastic forward-backward method对光滑项使用历史条件无偏梯度，对结构项精确做prox，以噪声方差和平均输出建立固定预算保证。各有自己的误差账本；本页不把无噪声加速率附给它们。标准FISTA的这个证明也没有证明所有主点序列收敛，重启或单调变体需另行指定协议。

两道短自测 ​

1. $g(x)=x^2/2$、$h(x)=|x|$、$L=2$、$x_0=4$，前两主点是什么？答案：$x_1=S_{1/2}(2)=3/2$；首轮无外推，$x_2=S_{1/2}(3/4)=1/4$。第三轮才用非零动量。
2. 回溯从 $L_0=100$开始，真实 $L_g=3$、倍率2，是否可宣称所有 $L_k\le 6$？答案：不可以；只增不减的规则保留100，通用界是 $max\{100,6\}=100$。

批量随机近端加速理路批量随机近端加速的噪声预算Batched accelerated stochastic proximal gradient · 带权批量 FISTA以放大的安全曲率吸收随机位移，证明加速势中的加权噪声和，再分配批量大小以分别认证近端次数与样本梯度成本。给出一个明确的带噪延伸：采用两倍安全曲率，先支付新点与噪声的相关位移，再对历史可测的加速势取条件期望。增长权重要求相应批量分配，样本数与 prox 次数分别计费；本页的精确无噪声定理仍只在原条件下使用。