為何需要複合方法
不少最優化問題具有「光滑的數據擬合項加簡單的非光滑懲罰項」的形式,例如最小二乘項加上 範數的倍數。懲罰項不可微,故不能直接用梯度下降;對懲罰項取次梯度步只能得到較慢的速率。近端梯度法利用此結構:對光滑部分走一個梯度步,再精確處理懲罰項,只要近端映射有閉式便可直接計算。本單元以絕對值的近端映射(軟閾值)、凸函數的次梯度運算,以及投影梯度單元所用的 Lipschitz 梯度下降不等式為基礎。
定義與基本假設
考慮
假設:
- 為凸且可微,且 對某個 為 -Lipschitz。於是對所有 ,
- 為凸(處處有限,故連續),但不必可微。
- 在某點 取得最小值 。
定義 9.2.1
(近端映射)
對 及 , 的近端映射定義為
此目標函數連續、強凸,且當 時趨向 ,故最小點存在且唯一。當 時,該映射逐分量作用為閾值 的軟閾值;當 時為恆等映射。
引理 9.2.2
(近端映射的刻劃)
當且僅當 。
證明
(強凸子問題的最優條件)
函數 為凸且有限,故 為其最小點當且僅當 屬於它在 的次微分。二次項可微,所以和的次微分為 。因此條件即 。
定義 9.2.3
(近端梯度法)
步長為 、起點為 的近端梯度法產生
當 時就是梯度下降。當 為閉凸集的示性函數(並非處處有限,但同樣的公式仍適用)時,近端映射即歐氏投影,該方法即投影梯度法。當 時,即迭代軟閾值算法(ISTA)。
概念視角分析
每一步都在極小化一個二次上界模型
配方可得
這個方法只把 線性化,加上一個鄰近項,而保留 不變。當 時,下降不等式使這個模型 成為 的上界,並在 處等於 ,所以 :在證明任何收斂速率之前,就已得到單調下降。
不動點即極小點
命題 9.2.4
(不動點恰好是極小點)
設 。點 極小化 當且僅當 。
證明
(兩個次梯度不等式相加)
由刻劃引理,不動點方程等價於 。若此式成立,則對每個 有 ,而由 為凸,。相加得 。反之,若 極小化 ,則由和規則 ,即上述包含關係。
因此該方法恰好停在極小點,且不動點集合與步長無關。
單步不等式
定理 9.2.5
(單步不等式)
設 ,,。則對每個 ,
證明
(三個不等式與一個極化恆等式)
記 (梯度映射)。對點 應用刻劃引理,得 。次梯度不等式給出
由光滑性不等式及 ,
又由凸性 。將三式相加,項 與 合併為 ,恰與第一式帶來的項 抵消。餘下
而 ,且 。故 ,最後一項與 抵消。
證明透視
單步不等式中每個假設用在哪裏
三個不等式各自用掉一個假設: 處的次梯度不等式經刻劃引理使用 的凸性,下降不等式使用 Lipschitz 梯度, 處的下界使用 的凸性。步長限制只出現一次,就是把 換成 的那一步。 的線性項能抵消,是因為三個不等式分別錨定在 、 與 ,合起來形成一個閉環。關鍵一步是極化恆等式:它把剩下的內積 改寫成到 的距離平方之差,再減去 ,而這個負項恰好吸收下降不等式的二次項。若 ,右邊會留下正的餘項 ,速率證明中的裂項相消便不能閉合。
收斂速率
定理 9.2.6
(目標值差距的 O(1/k) 上界)
設 ,。則迭代滿足 ,且對每個 ,
證明
(把單步不等式裂項相消)
在單步不等式取 ,得 。取 並對 求和,距離平方項裂項相消:
由於函數值不增, 個被加項每項都至少為 。除以 即得結論。
此上界是次線性的:要把差距減半,所需迭代次數要加倍。它只是關於目標值的陳述。證明亦顯示 (因每項 非負),但沒有給出距離的收斂速率。
例題
例題 9.2.7
(一步即解的純量問題)
令 ,,故 。 的極小點為 ,其中 ,且 。
取 及任意 ,則 ,故 :一步即精確。
例題 9.2.8
(同一問題,步長減半)
保留 與 ,但取 、。梯度步為 ,閾值為 。於是 ,;,;,。一般地 :只要梯度步的結果大於閾值,就有 ,即 。此處迭代幾何收斂,因為 強凸,比速率定理的假設更強。在 檢驗:,而上界為 。
例題 9.2.9
(稀疏分量只在極限處為零的二維 lasso)
令 ,,,。則 ,其 Lipschitz 常數為 。取 (閾值亦為 ),。
梯度步給出 及 。因此第一分量每步之後都等於 ;第二分量只要 ,便有 。由 起,迭代為
即 ,極限為 。以不動點檢驗最優性:,故 ,以 軟閾值後得 。此例中稀疏分量只在極限處才等於零,並非有限步內。
在 檢驗速率定理。;。,故差距為 。上界為 ,成立。
常見錯誤與細節
常見錯誤
(先取近端映射再走梯度步)
近端映射作用於梯度步之後的點 ,而非 。先對 取近端再走梯度步是另一種方法,一般而言是錯的。
常見錯誤
(按懲罰項選擇步長)
只需 為 Lipschitz。懲罰項 可以不可微,其 Lipschitz 性質與步長無關。
常見錯誤
(把 O(1/k) 上界讀成迭代點的結論)
是末次迭代目標值的上界。它並不表示迭代點收斂更快,也不表示 的支撐集在有限步後等於 的支撐集。
另外兩點關乎假設本身。
- 的凸性用了兩次:近端映射的唯一性,以及單步不等式中的次梯度不等式。若 非凸,近端映射可能多值,速率定理不再成立。
- 方法是否實用取決於近端映射是否廉價。軟閾值以及到方盒或球上的投影有閉式;一般的 可能需要內層求解器,此時定理不適用於不精確迭代。
反例模式
步長過長可使方法發散
條件 是充分而非必要的,但必須有某種上界。取 (故 )、、、。迭代為 ,所以迭代點為 ,且 ,而 。任何 形式的上界都不可能成立。對這個 ,每個 都收斂(見下面關於步長的練習),所以定理的條件 雖然保守,卻不能直接刪去。
練習
快速檢查
(令 ,,,。計算 並驗證它極小化 。)
閾值是 乘以懲罰權重。
解答
梯度步為 ,閾值為 ,故 。驗證最優性:對 ,,在 處為零( 與所用符號一致)。由於 為凸, 即極小點。
快速檢查
(令 ,,,。計算 ,並判斷方法是否已收斂。)
對新點作不動點檢驗。
解答
梯度步給出 ,故 。因 ,點 為極小點,亦為不動點:。方法一步即已收斂。
快速檢查
(某問題 ,以 由滿足 的點出發運行。給出 的保證上界。)
代入速率定理。
解答 · 答案
由速率定理,取 ,差距至多為 。
快速檢查
(證明當 為零函數時,速率定理化為梯度下降的界 ,並寫出此時的 。)
對 極小化 。
解答
若 ,則 在 處最小,故 為恆等映射,迭代為 。此時 ,速率定理正是所述的梯度下降界。
快速檢查
(對 與 ,求所有使迭代從任意起點收斂到 的步長 。)
把迭代寫成乘以一個常數。
解答
此時迭代為 ,故 。它對每個 都趨向 當且僅當 ,即 。由於 ,這包含定理所保證的整個範圍 ,並顯示該充分條件相當保守。