GAP

动态筛选的提出

以往的安全筛选法则，都是脱离训练过程所存在的筛选。我们称之为静态筛选规则(We will refer to such safe rules as static safe rules)他大致分为全局的(利用λ₀)和递归的(加速筛选一系列λ),动态筛选规则为我们提供了新的思路。作者用简单的伪代码为我们展示了何为动态筛选：(字典D就是上篇里的X，x是上篇的w)

它通过在优化过程中迭代减少字典的大小，丢弃已知不属于 Lasso 解的元素，从而加速了一大类优化算法。

动态筛选的符号选择跟前面处处有不同，看得我挺难受，同时一些处理做了细微改动。主要区别在于以下：

字典D就是上篇里的X，x是上篇的w,原问题写为

$$ \mathcal{P}(\lambda,\mathbf{D},\mathbf{y}):\tilde { \mathbf {x} }\triangleq\arg\min_\mathbf{x}\frac12\|\mathbf{D}\mathbf{x}-\mathbf{y}\|_2^2+\lambda\|\mathbf{x}\|_1 $$

对偶问题除以了λ，变成了这样：

$$ \tilde{\boldsymbol{\theta}} \triangleq \arg\max_{ {\boldsymbol{\theta}} } \frac{1}{2}\left\|\mathbf{y}\right\|_{2}^{2}-\frac{\lambda^{2}}{2}\left\|\boldsymbol{\theta}-\frac{\mathbf{y}}{\lambda}\right\|_{2}^{2} \quad \mathrm{s.t.~}\forall i\in\Omega,|\boldsymbol{\theta}^{T}\mathbf{d}_{i}|\leq1. $$

抛弃了之前求出的闭式解，在有球形约束的情况下采用了计算量较小的筛选规则：

Lemma 1 (Sphere Test Principle [7])
If the solution $\tilde{\boldsymbol{\theta}}$of (2) satisfies $\exists \{ r, \mathbf{c} \} \in \mathbb{R} \times \mathbb{R}^{N}, \| \widetilde{\boldsymbol{\theta}} - \mathbf{c} \| _{2}\leq r$, then:

$$ |\mathbf{c}^T\mathbf{d}_i|<1-r\Rightarrow\tilde{\mathbf{x}}(i)=0. $$

这种思路是很好的，他使得safe screen技术由一种预处理技术变为了对solver的加速技术，作者给出算法如主要利用了对偶缩放技巧，意在使得r_k尽可能的收敛，从而使得加速效率越来越快。但是作者并没有很好的处理好“如何让r_k必然收敛”这件事，于是新的方法诞生了。

GAP SAFE Rule

针对于上一篇文章提出的方法，本文的作者进行了一种关键的改进。insight在于，由于强对偶性的存在，对偶间隙必然是不断缩小直到趋于0的，那么我们如果构建一个与对偶间隙成比例的安全区域，那么这个安全区域也是严格收敛的，这样的加速方法大概率更优。定义本文的gapsafe区：

$$ \widehat{R}_{\lambda}(\beta):=\frac{1}{\lambda}\big(\left\|y\right\|^{2}-\left\|X\beta-y\right\|^{2}-2\lambda\left\|\beta\right\|_{1}\big)_{+}^{1/2}, $$

$$ \check{R}_{\lambda}(\theta):= \left\|\theta-\frac{y}{\lambda}\right\|, $$

θ̂^(λ)为 dual optimal Lasso solution，并且定义：

$$ \tilde{r}_\lambda(\beta,\theta):=\sqrt{\breve{R}_\lambda(\theta)^2-\widehat{R}_\lambda(\beta)^2}, $$

那么：

(15)

证明是很简洁的，根据对偶关系可以得到

$$ \frac{1}{2}\left\|y\right\|^{2}-\frac{\lambda^{2}}{2}\left\|\theta-\frac{y}{\lambda}\right\|^{2} \leqslant \frac{1}{2}\left\|X\beta-y\right\|^{2}+\lambda\left\|\beta\right\|_{1} $$

因此：

$$ \left\|\theta-\frac{y}{\lambda}\right\| \geqslant \frac{\sqrt{\left(\left\|y\right\|^2-\left\|X\beta-y\right\|^2-2\lambda\left\|\beta\right\|_1\right)}}{\lambda}. $$

同时利用原先的SAFE技巧，任取一个对偶可行点，可以约束得到Ř_λ(θ)，因此安全区域夹在了两个圆之间的环上，根据几何关系可以直观地推导出最终的安全区域：

GAP SAFE sphere:

𝒞_k = B(θ_k, r_λ(β, θ))

GAP SAFE dome:

$$ \mathcal{C}_k=D\Bigg(\frac{\frac{y}{\lambda}+\theta_k}{2},\frac{\breve{R}_\lambda(\theta_k)}{2},2\left(\frac{\widehat{R}_\lambda(\beta_k)}{\check{R}_\lambda(\theta_k)}\right)^2-1,\frac{\theta_k-\frac{y}{\lambda}}{\|\theta_k-\frac{y}{\lambda}\|}\Bigg) $$

回到本来的思路，我们探究gap safe sphere和对偶间隔G_λ(β, θ) = P_λ(β) − D_λ(θ)的关系，容易证明得到：

$$ \tilde{r}_\lambda(\beta,\theta)^2\leqslant r_\lambda(\beta,\theta)^2:=\frac{2}{\lambda^2}G_\lambda(\beta,\theta). $$

为此作者一开始的insight得到了利用，区域的收敛性有了保障。

K表示优化步骤最多进行的次数，f表示每隔几次单独的优化步骤便进行一次筛选。
作者进行了时间比较，在加速以及特征筛选方面效果显著。