動機
當特徵列標準正交時,對相關性做一次閾值運算便得到 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 與貪婪追蹤。二次函數上的梯度下降說明特徵值如何控制光滑二次問題的步長。