动机
当特征列标准正交时,对相关性做一次阈值运算便得到 LASSO 解。列之间相关时,改变一个系数会改变其他列看到的残差。我们需要考虑整个设计矩阵的迭代,也需要判断现有答案距离最优值有多远。目标函数下降得很少,并不保证它已接近最小值。
固定 A=[a1,…,ap]∈Rn×p、y∈Rn 及 λ>0,考虑有限维目标函数
F(x)=f(x)+λ∥x∥1,f(x)=21∥Ax−y∥22.
所有系数均受惩罚,这里没有另设截距。损失函数的梯度是 ∇f(x)=AT(Ax−y)。令 L=∥A∥22,即 ATA 的最大特征值。先假设 A=0,故 L>0。惩罚项使 F 在系数范数趋无穷时趋无穷,因此即使列线性相关,最小解仍存在;但列线性相关时解未必唯一。
由二次模型得到更新
对 a≥0,定义 Sa(v)j=sign(vj)max(∣vj∣−a,0),并约定 sign(0)=0。给定 x 和 η>0,下一个向量最小化
Qη(u;x)=f(x)+∇f(x)T(u−x)+2η1∥u−x∥22+λ∥u∥1.它的唯一解是 x+=Sηλ(x−η∇f(x))。
配方后,除与 u 无关的项外,Qη 是各坐标 (uj−vj)2/(2η)+λ∣uj∣ 的和,其中 v=x−η∇f(x)。正、负半轴的驻点候选分别是 vj−ηλ 和 vj+ηλ;若 ∣vj∣≤ηλ,零满足次梯度条件。二次项保证最小解唯一。因此,每一步先沿损失梯度反方向移动,再以与步长相乘的 ηλ 作阈值,而不是单纯使用 λ。
概念视角几何
软阈值等于恒等映射减去盒投影
逐个坐标地看,Sa(v)=v−Πa(v),其中 Πa 是到盒子 [−a,a]p 的欧氏(Euclidean)投影,即把每个坐标截断到 [−a,a]:若 ∣vj∣≤a,截断给出 vj,阈值给出 0;否则两者分别给出 asign(vj) 和 vj−asign(vj)。因此近端步保留的,是梯度步向量中半宽为 ηλ 的盒子吸收不了的部分。半宽为 λ 的盒子会在下面的证书中以对偶约束 ∥ATθ∥∞≤λ 再次出现。
收敛保证
设 A=0、λ>0、0<η≤1/L。从任意 x0 出发,令
xk+1=Sηλ(xk−ηAT(Axk−y)).对每个最小解 x∗ 和每个 k≥1,
0≤F(xk)−F(x∗)≤2ηk∥x0−x∗∥22.目标值不递增,迭代向量收敛至一个最小解。若最小解不唯一,极限可以依赖起点。
二次损失同时满足凸性下界和上方模型
f(z)≥f(x)+∇f(x)T(z−x),f(u)≤f(x)+∇f(x)T(u−x)+2η1∥u−x∥22.第二式直接来自 ∥A(u−x)∥22≤L∥u−x∥22 和 1/η≥L。近端子问题中 u=x+ 的最优性给出某个 g∈∂∥u∥1,使 ∇f(x)+(u−x)/η+λg=0。先结合 u 处的上方模型、z 处的凸性下界与次梯度不等式 ∥u∥1−∥z∥1≤gT(u−z)。然后把 ∇f(x)+λg 替换为 (x−u)/η。使用恒等式 2(u−x)T(z−u)=∥x−z∥22−∥u−z∥22−∥u−x∥22,对每个 z 得到
F(u)−F(z)≤2η∥x−z∥22−∥u−z∥22.取 z=x 可知目标值下降或不变。取 z=x∗,对第 0 至第 k−1 步求和,右边裂项抵消。目标差非负且不递增,因此最后一项不超过平均值,便得到所列速率。
同一不等式说明到每个最小解的距离不递增,因此迭代有界。目标差趋零,加上连续性,任何聚点都是最小解。取其中一个聚点 xˉ;因 ∥xk−xˉ∥ 不递增,而且某子列的距离趋零,整列必收敛至 xˉ。这不需要列满秩。若 A=0,可取任意 η>0:唯一最小解为零,而重复阈值运算在有限步内到达零。
证明透视
裂项求和需要什么
证明建立在一条对每个比较点 z 都成立的不等式上,而每个假设只在其中用一次。步长条件 η≤1/L 给出新点 u 处的上方模型;凸性给出 z 处的下界;近端最优性条件 ∇f(x)+λg=(x−u)/η 把两者连接起来,使一次项互相抵消,只剩下距离的平方。
真正起作用的是 z 的自由选择。取 z=x 得到下降性;取 z=x∗ 则右边裂项相消,而目标差的单调性把总和转为最后一项的界。同一不等式还表明,对任何最小解,∥xk−x∗∥ 都不会增加。这比速率更强:它给出有界性,配合一个聚点便确定整个序列的极限。论证既不用唯一性,也不用列满秩。条件 η≤1/L 只用于上方模型,而下文步长过大的反例恰好破坏了这一点。
不动点与稀疏决定
命题 1.5.3
(不动点恰是 LASSO 最小解)
对任意 η>0,向量 x 是映射 x↦Sηλ(x−η∇f(x)) 的不动点,当且仅当它最小化 F。
近端子问题有唯一最小解,所以 x 是不动点,当且仅当 u=x 是 Qη(⋅;x) 的最小解。在 u=x 处 (u−x)/η 一项为零,故其最优性条件是 0∈∇f(x)+λ∂∥x∥1。这正是凸函数 F 最小化的充要条件。
对所有正步长,包括太大而不满足收敛定理的步长,不动点等价性仍成立。区分两者十分重要:找到正确的不动点,并不证明迭代必定到达它。
对非零系数,条件要求 ajT(y−Ax)=λsign(xj);在零处,容许的相关性构成区间 [−λ,λ]。一次阈值运算可把系数设为零,但其后残差会改变,相关性可能离开此区间,令系数重新变成非零。因此暂时为零并不能保证永久选择或剔除特征。
令
A=(103/54/5),y=(3,1)T,λ=1.这里 ATA 的特征值为 8/5 和 2/5,故容许 η=5/8=1/L。从零出发,初始相关性是 (3,13/5)T。梯度步得到 (15/8,13/8)T,以 5/8 作阈值后得到 x1=(5/4,1)T。其残差是 (23/20,1/5)T,相关性是 (23/20,17/20)T。下一步两个坐标仍为正,结果为 x2=(43/32,29/32)T:第一个增加,第二个减少。两项更新都依赖同一残差。精确最小解是 (13/8,5/8)T;其残差 (1,1/2)T 与两列的相关性均为 1,验证了最优性。由于 A 的列线性无关,此例最优解唯一。
沿用同一矩阵、步长 η=5/8 和 λ=1,但取 y=(1,−3)T、x0=0。起初 ATy=(1,−9/5)T,故以 5/8 作阈值得 x1=(0,−1/2)T:梯度步的第一坐标刚好等于阈值。此后 r1=y−Ax1=(13/10,−13/5)T,相关性为 ATr1=(13/10,−13/10)T。下一次梯度步向量是 (13/16,−21/16)T,阈值运算给出 x2=(3/16,−11/16)T。第一个系数重新出现,因为残差相关性由 1 变为 13/10。单凭它初次为零或后来重新出现,都不能确定最终支撑集。
定理使用最大奇异值给出一个充分的固定步长。实际上不一定要精确计算它:任何已知上界 L≥L 都容许保守选择 η≤1/L。较小步长可能需要更多迭代。反过来说,实用的自适应规则需要真正检查适当的上方模型不等式;只看到某一步下降,不能证明其后每一步都满足定理。
曲率未知时的回溯
全局上界可能难以计算,也可能过分保守。可先固定试探步长 η0>0 和缩减因子 0<β<1。在每个迭代点 x,重新由 η=η0 开始,计算 u=Sηλ(x−η∇f(x)),只在下列条件成立时接受:
f(u)≤f(x)+∇f(x)T(u−x)+2η1∥u−x∥22.
若检查失败,将 η 换成 βη,并重新计算梯度步和阈值。检查的是 f 而非整个目标函数:惩罚项已在近端子问题中原封不动地保留。对这里的二次损失,条件等价于 ∥A(u−x)∥22≤∥u−x∥22/η。只检查 F(u)≤F(x) 是另一种规则,不能直接得到以下论证。
设 A=0,L=∥A∥22。上述规则每次都在有限次试探后接受,且接受的步长 ηk 至少为 m=min(η0,β/L)>0。目标值不递增;对任意最小解 x∗ 和 k≥1,
F(xk)−F(x∗)≤2∑i=0k−1ηi∥x0−x∗∥22≤2mk∥x0−x∗∥22.即使最小解不唯一,迭代向量仍收敛到某个最小解。
展开二次损失可知,只要 η≤1/L,不论候选方向是什么,试探都会通过。因此反复乘以 β 必会终止。若第一次试探通过,步长便是 η0;否则首次通过之前的失败步长大于 1/L,所以接受的步长大于 β/L,得出一致正下界。因为检查只依赖实际方向,更大的步长有时也可通过;此规则不必估算最大奇异值。
接受的上方模型正是前面三点不等式所需的条件。将该论证中的步长换成第 i 步的 ηi,得
2ηi(F(xi+1)−F(z))≤∥xi−z∥22−∥xi+1−z∥22.取 z=xi 得到下降性;取 z=x∗ 并求和,便控制了非负目标差的加权和。因目标差不递增,最后一项乘以 i∑ηi 不大于该加权和,得到所列估计。同一不等式使到每个最小解的距离不递增;有界性、目标差趋零、连续性及固定步长证明中的聚点论证,继而给出整列收敛。一致正步长下界不可省略:若容许步长总和有限,此证明便不能保证速率或收敛。
证明透视
为什么局部模型已足够
检查只在实际产生的候选点进行,而三点不等式用到的也只有这些:u 处的上方模型、任意 z 处的凸性下界,以及采用已接受步长 ηi 的近端最优性条件。由于 1/L 并不出现在不等式本身中,一个比 1/L 长而通过检查的步长,与短步长同样有效。
常数 1/L 只在一处回来,就是下界 m。裂项求和控制的是 i∑ηi 乘以最后的目标差,所以速率需要 i<k∑ηi≥mk。没有这个下界,接受的步长之和可能有限,加权和便不再迫使目标差趋于零。
取 A=[2]、y=3、λ=1、x0=0、η0=1 和 β=1/2。此时 f(x)=(2x−3)2/2、f(0)=9/2、f′(0)=−6。第一个候选点 u=S1(6)=5 的损失 49/2 大于模型值 9/2−30+25/2=−13,因此拒绝。取 η=1/2 时,候选点为 S1/2(3)=5/2;损失 2 大于 9/2−15+25/4=−17/4,再次拒绝。取 η=1/4 时,候选点为 S1/4(3/2)=5/4;损失与模型值均为 1/8,所以接受。此时残差为 1/2,且 AT(y−Au)=1=λ,验证它已是最优解。一步到达是此标量例子的特殊情况,并非一般保证。
在接受的候选点,上方模型与近端子问题的最优性共同保证 F(u)≤F(x);反过来不一定成立:目标值下降仍可能不通过模型检查。另外,零更新对任何正步长都通过检查;根据不动点结果,即使试探步长超过 1/L,此时也已找到最小解。
算例与可计算的证书
取 A=diag(1,2)、y=(3,2)T、λ=1、x0=0 和 η=1/4=1/L。梯度步得到 (3/4,1)T,以 1/4 作阈值得 x1=(1/2,3/4)T。残差是 r=y−Ax1=(5/2,1/2)T,而 F(x1)=9/2。
此例的坐标可分开求解:最小解是 x∗=(2,3/4)T,残差 (1,1/2)T,目标值 F(x∗)=27/8。第二坐标已到达最终值,第一坐标却未到达。对列互相耦合的情况,不能使用此分离捷径,但速率定理仍然有效。
实际上 x∗ 及其与 x0 的距离通常未知。若 θ∈Rn 满足 ∥ATθ∥∞≤λ,称它对偶可行,其对偶值为 D(θ)=yTθ−∥θ∥22/2。对任意 x 和可行 θ,
F(x)−D(θ)=21∥y−Ax−θ∥22+λ∥x∥1−θTAx≥0.
展开平方即可验证恒等式。由可行性和范数不等式,λ∥x∥1−θTAx≥(λ−∥ATθ∥∞)∥x∥1≥0。在最小解代入此恒等式得 D(θ)≤F(x∗),所以 F(x)−D(θ) 是可观察的 F(x)−minF 上界。它衡量的是目标值误差,不一定衡量系数误差或特征选择是否正确。
上例中 ∥ATr∥∞=5/2,将 r 乘以 2/5 得可行的 θ=(1,1/5)T。此时 D(θ)=72/25,间隙是 9/2−72/25=81/50。一般可取 θ=cr,当分母非零时令 c=min(1,λ/∥ATr∥∞);分母为零时取 c=1。在最小解处,残差本身对偶可行,并由 LASSO 的次梯度条件给出零间隙。
步长过大会怎样
反例模式
周期序列可能令目标值上升
标量问题 A=[1]、y=2、λ=1 的 L=1。选 η=3、x0=0,阈值为 3:x1=S3(6)=3,继而 x2=S3(0)=0,序列永远交替。而且 F(0)=2、F(3)=7/2,连下降也不成立。这并非说每个大于 1/L 的步长都失败,而是说任意步长需要另外论证。
即使远离最小解,固定的小步长也可能使更新很小。应比较目标值与对偶可行下界。即使目标间隙很小,若没有强凸性等额外假设,也不保证系数误差很小。例如,若 A 的列满秩,则 F(x)−F(x∗)≥σmin(A)2∥x−x∗∥22/2,故目标间隙至多为 ε 时,系数误差平方至多为 2ε/σmin(A)2。
常见错误
(以 λ 而非 ηλ 作阈值)
梯度步已乘以 η,所以阈值必须是 ηλ。取 A=[1]、y=3、λ=1、η=1/2,错误的迭代 x↦S1((x+3)/2) 的不动点是 x=1,但最小解是 S1(3)=2。一般地,x↦Sλ(x−η∇f(x)) 的不动点最小化 f+(λ/η)∥⋅∥1:错误的阈值求解的是惩罚为 λ/η 而非 λ 的 LASSO 问题。
练习
快速检查
(设 A=[1]、y=3、λ=1、η=1/2、x0=0。计算前两步及精确最小解。)
解答 · 答案
x1=S1/2(3/2)=1,x2=S1/2(2)=3/2。标量最优解是 S1(3)=2。两次迭代均在其下方;收敛一般不会在一步内完成。
快速检查
(设 A=[1,1]、y=3、λ=1。给出两个不同的最小解,解释目标值收敛为何不一定指定唯一的系数向量。)
使用残差相关性条件或三角不等式。
解答 · 答案
(2,0)T 和 (0,2)T 的残差都是 1,各自满足 λ=1 时的残差相关性条件,故都是全局最小解。事实上,所有和为 2 的非负系数对都是最小解。因此,目标值收敛本身不能选出唯一表示。迭代向量仍然收敛,但极限可依赖 x0。
快速检查
(在第一题的标量问题中,于 x=1 求一个对偶可行向量及对偶间隙。)
有需要时缩放残差。
解答 · 答案
x=1 时残差为 2;取 θ=1,满足 ∣ATθ∣=1。原问题值 F(1)=3,对偶值 D(1)=3−1/2=5/2,间隙为 1/2。此例恰好等于真实目标误差,因为 θ=1 等于最优残差 y−x∗;任意可行对偶向量未必给出紧的界。
快速检查
(取 A=[1]、y=2、λ=1、x=0。在回溯检查中先试 η=3/2,若被拒则减半。单靠目标值下降能否决定第一次试探?)
求阈值后的候选点,并比较损失与上方模型。
解答 · 答案
当 η=3/2,u=S3/2(3)=3/2。虽然 F(u)=13/8<2=F(0),但其损失为 1/8,上方模型却是 2−3+(3/2)2/3=−1/4。因此即使目标值下降,试探仍被拒绝。减半后 η=3/4、u=S3/4(3/2)=3/4,损失 25/32 不超过上方模型 2−3/2+(3/4)2/(3/2)=7/8,所以接受。
相关笔记
LASSO 与匹配追踪介绍残差最优性条件,并区分整体 LASSO 与贪婪追踪。二次函数上的梯度下降说明特征值如何控制光滑二次问题的步长。