Lasso 的间隙安全筛除

一个近似原始解的零模式会变，不能直接据此删除变量。gap却同时提供原始上界和对偶下界，把未知的最优对偶点限制在一个可计算的球内。若这个球里的每一点都不可能让某列达到KKT阈值，该列就不可能有非零最优系数。

这是先认证区域，再做全区域测试。随着gap变小，半径缩小，可能证明更多坐标为零。它可与坐标下降理路Lasso 坐标下降Lasso coordinate descent · Lasso cyclic coordinate minimization用部分残差和列范数逐坐标精确最小化 Lasso，并保持残差缓存与可行对偶证书一致。或FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。产生的任意候选配合，不要求候选来自某个专用算法。

在第二轮ISTA就得到安全删列证书 ​

仍取

第二轮ISTA候选为 $x=(5/6,0)$。用残差缩放得到 $\theta =(1/2,1/2,0)$，$P=23/18$、$D=5/4$，所以 $G=1/36$、$R=\sqrt{1/18}$。两列范数都是 $\sqrt{2}$，因此

第二列严格小于1，可以安全删除；第一列不能删。注意此时第一系数仍未最优：当前 $5/6$而最优值为1。筛除证明可以先于整个优化任务完成。

第一轮ISTA虽然已有较小目标，其 $G=19/108$、$A_2^T\theta =1/3$，第二列上界为 $1/3+\sqrt{19/27}>1$，尚不能删。这个对比说明，筛除要实际计算安全余量，不能只看某一列的当前相关性小于阈值。

等号、重复列与改变参数 ​

式(1)必须严格。取 $A=(11)$、$b=2$、$\lambda =1$。任意 $x_1,x_2\ge 0$且 $x_1+x_2=1$都是最优解，${\theta }^{\ast }=1$。即使gap为零，两列的测试值都等于 $\lambda$；其中既有 $(1,0)$也有 $(0,1)$，没有哪列可被证明在所有解里为零。把严格小于改成小于等于会删掉必要的最优解。

反过来，等号不证明系数一定非零。单变量 $A=1,b=1,\lambda =1$的唯一最优解为零，但最优对偶相关性也恰等于阈值。筛除是充分条件，不是零坐标的充要识别器。

改变数据或 $\lambda$后，原来的可行集、gap或阈值可能改变，必须重新构造证书。尤其减小 $\lambda$时，旧安全集合不能直接沿用。安全筛除只认证给定正则化优化解；未知生成模型的真实支持需要噪声、设计和信号条件，统计结论留给对应学习理论。

安全球从何而来 ​

$D(\theta )=\Vert b{\Vert }^2/2-\Vert \theta -b{\Vert }^2/2$，所以最大化 $D$等价于把 $b$投影到非空闭凸集 $C$。这保证唯一 ${\theta }^{\ast }$。由受约束凸问题的一阶最优性理路一阶最优性条件First-order optimality condition · Variational inequality optimality condition以梯度和所有可行方向的非负内积充要刻画可微凸问题的全局极小点。，任意 $\theta \in C$满足

直接展开二次式，

Lasso的强对偶给 $D({\theta }^{\ast })=P^{\ast }\le P(x)$，故 $\Vert \theta -{\theta }^{\ast }{\Vert }^2\le 2G$。这一步依靠的是对偶二次目标的曲率，并不要求 $A$满列秩，也不要求原始解唯一。

由Cauchy–Schwarz不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，球内任意 $u$满足

因此式(1)推出 $|A_j^T{\theta }^{\ast }|<\lambda$。Lasso的KKT规定任何非零最优系数必须达到相关性绝对值 $\lambda$，于是 $x_j^{\ast }=0$。全部最优原始解共享同一个最优对偶点，所以结论覆盖所有解而非某个被选中的解。

安全执行与费用 ​

若当前候选在已认证可删列上仍非零，把它们置零可能让当前目标暂时上升，但约束后的问题仍保留全部最优解。应更新残差、重新评价目标与证书，不能在旧缓存上继续计算。筛除余量可作为审计记录，解释为何某列被永久固定。

浮点中不能用一个未经界定的负gap开平方，也不能把近似可行的 $\theta$直接视作可行。若有严格数值上界 $\bar{P}\ge P(x)$和严格下界 $\underset{―}{D}\le D(\theta )$，应使用 $\bar{G}=\bar{P}-\underset{―}{D}$；列相关性和范数也用可靠上界。没有误差界时，在阈值附近保留坐标并报告数值容差，比冒称严格安全更诚实。

一次筛除需所有活跃列的相关性和预计算范数，费用通常为 $O(\mathrm{nnz}(A)+m+n)$；与gap检查共享即可。若只用剩余活跃列计算 $\underset{j}{max}|A_j^{T}r|$，缩放所得 $\theta$未必满足原问题已筛列的对偶约束；要报原问题gap，仍需全列可行性检查，或另有覆盖已筛列的严格界。筛除后每次坐标扫掠可少访问一些列，但完整数据的读入、早期扫描和证书费用仍要计入。若所有测试都失败，算法只是没有缩减维数，原始优化仍可继续。

两道短自测 ​

1. $\lambda =2,G=1/8,\Vert A_j\Vert =1,|A_j^T\theta |=1$且 $\theta$可行，能删吗？答案：$R=1/2$，测试值 $3/2<2$，所以可以。
2. 同样条件但相关性为 $3/2$，能删吗？答案：测试值等于2，不能；等号既可能对应零，也可能对应非零最优系数。