前面的筆記分析了正定二次函數上的梯度下降:迭代是線性的,Hessian 的特徵值精確描述誤差。即使訓練一個很小的神經網絡,目標函數也可能既非二次函數,又非凸函數。此時譜分解的論證不再適用,我們需要改變問題。
一般情況下,不能指望證明算法收斂到全局最小點。但在梯度光滑且目標函數有下界時,可以證明梯度趨於零。本節從頭推導這一保證,並用例子檢驗它的邊界。
基本假設
以下設 滿足:
- 光滑性: 連續可微,且對某個 ,梯度在整個空間上滿足 Lipschitz 條件:
- 有下界: 存在實數 ,使得對所有 都有 。
只需是一個下界,不一定是下確界,也不一定能被取到。對非負損失, 總是可用。本文使用歐幾里得(Euclid)範數。
固定步長梯度下降選擇 和 ,然後令
下降引理
Lipschitz 條件控制梯度變化的快慢。先將它轉化為關於函數值的結論:函數與其切平面相差多少?
定理 3.2.1
(下降引理)
在上述光滑性假設下,對所有 ,
證明
(沿線段對梯度積分)
固定 ,記 ,定義 為 。
由鏈式法則,。因為 連續,這個導數關於 連續,故微積分基本定理給出
將 寫為它在 上的積分並相減,得到
Cauchy–Schwarz 不等式給出 ;Lipschitz 條件則給出 。因此
證明用到了梯度連續性和 Lipschitz 界:前者保證可應用微積分基本定理,後者控制被積函數;這裏沒有用到凸性。引理給出了切平面兩側的二次界,下面只需要上界:
每一步使目標下降
定理 3.2.2
(充分下降)
在基本假設和 下,每一步滿足
證明
(代入梯度步)
記 ,則 。在上面的下降不等式中取 、:
記 。步長限制 恰好保證 。作為 的函數, 是開口向下的拋物線,在 取得最大值 。因此 使保證的下降量最大,實際下降量可以更大。
概念視角算法
梯度下降作為二次上界模型的極小化
下降不等式的上半部說明 位於 之上,並在 處與它相切。配方可見 恰好在 處取得極小值 。因此步長 就是「先取上界、再極小化」的一步,其保證下降量 正是模型本身的下降。步長 極小化的是曲率為 的模型,而它只在 時才是上界模型。
梯度平方可和與有限步界
定理 3.2.3
(固定步長梯度下降的駐點保證)
在基本假設和 下,
對於每個整數 ,
特別地,。
證明
(將下降不等式累加)
充分下降可改寫為 。從 加到 ,右側首尾相消:
最後一步正是使用下界的地方。
非負級數 的部分和因此有統一上界,所以級數收斂,其和也滿足同一界。收斂級數的項趨於零,故 ,從而 。
對於有限步界,每一項都不小於前 項中的最小值,所以
兩邊除以 並取平方根即可;平方根遞增,故最小平方範數等於最小範數的平方。
證明透視
各個假設在駐點證明中的位置
整個論證只有一個想法:每一步都以函數值「支付」它的梯度平方,而可用的函數值總量是有限預算 。累加把局部的單步不等式變成全局的計數,過程中完全不需要知道迭代點在哪裏。
光滑性只出現一次:透過下降引理產生單步不等式。步長限制透過 進入:當 時,累加後的不等式變成 ,不含任何資訊。下界只在最後一步 用到;沒有它,預算便是無限的。例如 的梯度是常數,因而對每個 都是 -Lipschitz;迭代為 ,而每個 都有 。
證明控制的是一個和,而和只能控制最小項與平均值,不能控制每一項。所以有限步結論是關於 ,而不是關於最後一個迭代點。凸性從未用到。
這個界按 衰減。要保證 ,取
便足夠。
例題 3.2.4
(迭代次數的界可以多悲觀)
取 ,於是 、、。選 、,則 ,且
定理保證甚麼。 容差 對應的充分次數為
所以 次迭代保證足夠。
實際發生甚麼。 迭代為 ,故 、。條件 即 ,首次在 成立,此時 。所以前 個迭代點中已有滿足容差的點。
檢查。 第一步的充分下降預測 ,而 :單步不等式在此取等號。 與 的差距來自累加:它假設每一步只得到保證的下降量,並耗用保證的預算。這個函數是強凸的,而定理沒有用到這種結構,所以最壞情況的次數在此遠離實際。
迭代點能否收斂?
定義 3.2.5
(駐點與聚點)
若 ,稱 為 的駐點。
如果某個子序列 收斂到 ,稱 為序列 的聚點。
推論 3.2.6
(梯度下降的聚點都是駐點)
在基本假設和 下,梯度下降序列 的每個聚點都是 的駐點。若 有界,則至少存在一個聚點。
證明
(沿子序列取極限)
設 。梯度連續性給出 。由駐點保證,整個梯度範數序列趨於零,子序列也如此。極限唯一,故 。
若 有界,Bolzano–Weierstrass 定理給出一個收斂子序列,因而至少有一個聚點;由第一部分,它是駐點。
有界性是額外假設,基本假設並不能保證它;下面的 logistic 損失反例就沒有聚點。
定理並不保證迭代點收斂、駐點是最小點(它可能是鞍點甚至最大點)、恢復數據生成模型的真實參數,也不保證 趨零的任何速率。這些結論需要額外結構,例如凸性、梯度支配不等式,或有界次水平集以及關於駐點集合的資訊。
例題 3.2.7
(收斂到鞍點)
令 。則 ,可取 ,且
Hessian 的算子範數為 ,故 是 -Lipschitz,。取 ,兩個座標互不影響:
邊界情形 。 從 出發,每一步都有 ,故 、。迭代點收斂到 ;這是 Hessian 為 的駐點,即鞍點,且 ,而最小值是 。定理的每個結論都成立,但極限不是最小點。
擾動後的起點。 從 出發,其中 。映射 滿足 和 ,所以把 映入自身;又因 ,在該區間上 。序列 遞增且以 為上界,其極限 滿足 ,故 。迭代點收斂到全局最小點 ,。到達哪個駐點取決於起點,而定理看不到這一點。
對二次連續可微的目標函數及足夠小的固定步長,只有測度為零的起點集合會收斂到嚴格鞍點。
自然延伸的下一個問題
梯度下降停在鞍點的情況有多常見?
對二次連續可微的目標函數及足夠小的固定步長,只有測度為零的起點集合會收斂到嚴格鞍點。
在上例中,壞的起點恰好是水平直線族 ,即 之處;從其他每個起點出發,迭代都到達最小點。這是典型情況。若 二次連續可微且 ,梯度映射是微分同胚,而迭代收斂到某個 Hessian 有負特徵值的駐點的起點,構成 Lebesgue 測度為零的集合。證明要用到穩定流形定理,超出本節範圍;它也沒有給出迭代點在鞍點附近停留多久的上界。
單參數 tanh 預測器
例題 3.2.8
(用 擬合目標值 )
考慮預測器 :它是一個權重為 、輸入固定為 的 tanh 單元。用平方損失擬合目標 :
顯然 ,所以可取 。
導數。 由 和 ,得
再用乘積法則:
一個有效的 Lipschitz 常數。 對所有實數 ,、,因而 。由三角不等式,
中值定理給出 ,故 可用。
這個界並非最緊。令 ,可得 ,例如 。定理只需要一個有效的 ,不要求最佳常數。
從 以 走一步。 因為 ,定理適用。由 、,
此時 ,充分下降給出
在 代入級數 ,可得 ,故
實際值嚴格小於初值 ,也小於保證的上界 。
最優點及本例的特殊之處。 由於 ,方程 必須有 。因此唯一駐點為
且 ,所以它是全局最小點。
在本例中還可證明迭代點收斂。對 ,單調下降給出 ,即 。因此 落在閉區間 內,而這個區間包含於 ,所以 保持有界。
每個聚點都是駐點,因此只能是 。有界序列若只有一個聚點 ,便收斂到 。這裏用到了本例特有的有界次水平集和唯一駐點,不能把結論推廣成一般定理。
反例:結論的邊界
反例模式
下降但沒有有限駐點:logistic 損失
令 。它嚴格為正,故可取 。其導數為
由於 ,有 ,因此 有效。這個函數根本沒有駐點。
從任意有限的 出發,以任意固定 作梯度下降:
增量嚴格為正,故 嚴格遞增。若它收斂到有限數 ,在更新式中取極限便得 ,矛盾。遞增實數序列若無有限極限,必無上界,故 。
於是 且 :梯度趨零的結論成立,但既沒有聚點,也沒有最小點。梯度小並不意味著迭代點接近某個駐點。
以上是精確算術中的推導。浮點計算時, 很負會使 溢出。應使用穩定的改寫
並使用專門的 log1p 函數計算 。
第二個反例針對步長假設,而不是 的形狀。
反例模式
端點步長:L 分之二
令 ,其梯度 的 Lipschitz 常數恰為 。當 時,
若 ,迭代值在 之間交替, 始終不變。梯度範數始終為 ,並不趨零。
這與充分下降不矛盾,因為 ;它說明嚴格條件 不能省去。
常見錯誤
(把定理用於帶 ReLU 折點的損失)
令 。當 時 ;當 時 。兩式在 處相等,故 連續,於是很容易直接引用駐點保證。
但 處左導數為 ,右導數為 ,故 在此不可微。下降引理中沿直線應用微積分基本定理的證明不再適用,上述形式的駐點保證也不適用;下面最後一題說明,無論把哪個數當作「 處的導數」,都挽救不了下降不等式。這類損失需要另行作非光滑分析。
如何理解訓練中的保證
報告哪個迭代點。 有限步界針對前 個迭代點中的最優者,而非最後一個。算法每步本來就計算 ,因此可以記錄
並報告 ,它滿足該界。這只說明 的駐點程度。
常見錯誤
(把界當作關於最後一個迭代點的結論)
有限步界並不控制 。梯度範數不一定逐步下降:在下面關於正弦迭代的練習中,第一步之後梯度範數反而上升。證明控制的是前 個梯度範數平方之和,所以只有最優的迭代點,或平方範數的平均值,才滿足這個界。例如在 中均勻抽取的指標 滿足 。
確定性梯度與隨機梯度。 上面的分析要求每一步使用 的精確梯度。隨機訓練將其替換成隨機小批次估計,此時下降不等式逐路徑不一定成立,需要另作論證,通常要取期望值並對雜訊和步長作假設。上述結論不能自動沿用。
經驗損失與總體損失。 若 是固定數據集上的平均損失,定理只保證經驗損失近似駐點,並不說明來自基礎分布的新數據上的損失。訓練梯度小是優化結論;測試表現好是另一個統計問題。
練習
練習 3.2.9
(設 。求使 為 -Lipschitz 的最小常數,以及有效下界 。直接證明下降引理,並寫出 時 的界。)
核心
解答(4)
- 1
說明 有效
對某個介於 之間的 ,有 ,故 可用。
依據: 對 應用中值定理。
- 2
說明更小的常數不行
若對所有 有 ,除以 並令 得 ;取 得 。下界 有效且可取到。
- 3
直接驗證下降引理
令 ,則
被積函數絕對值至多為 ,所以整個式子的絕對值至多為 。
- 4
應用駐點保證
滿足 ,且 ,因此
練習 3.2.10
(設 、、。定理要求多少次迭代才能保證 ?與 比較。)
基礎
解答(3)
- 1
檢查步長並計算
因為 ,定理適用;。
- 2
解出 的充分條件
故 次足夠。
- 3
與 比較
若 ,則 ,只需 。因為 在 最大,這是該界能給出的最小充分次數。這些都是最壞情況界的充分次數,並非實際表現的預測。
練習 3.2.11
(取 、。(a) 從 出發,證明 。(b) 證明迭代值留在 中,並確定其極限。(c) 從 出發會發生甚麼?)
核心
解答(4)
- 1
(a) 梯度範數可以上升
,故 。於是
由於 ,角度滿足 。正弦在 嚴格遞增,所以 。梯度範數不一定單調下降;定理並未聲稱如此。另一方面,充分下降給出 。
- 2
(b) 區間在迭代下不變
令 ,則 ,故 不遞減。當 時,,因此 ;又 。
- 3
(b) 確定極限
關鍵一步
在區間內 ,故序列不遞增且有下界,收斂到某個 ;它是駐點,因而 ,。又 ,故 ,是全局最小點。
依據: 確定極限的是單調性,而不是一般定理。
- 4
(c) 從最大點出發
,故所有 都有 。迭代點停在全局最大點:梯度為零,卻離最優函數值最遠。
練習 3.2.12
((a) 對 ,描述 和 時的梯度下降。(b) 對 ,證明不管把哪個數 指定為 處的導數,都不存在 使下降引理的雙側不等式在 附近成立。)
綜合證明
解答(4)
- 1
(a) 線性遞推
兩種情形均有 。 時乘數為 ,迭代值在 和 之間交替,損失不變。 時 ;只要 ,便有 且 。
- 2
(b) 折點兩側的餘項
令 。若 ,則 ;若 ,則 。
- 3
(b) 兩個單側極限都必須為零
關鍵一步
所以 從兩側都必須趨於零。右側極限為 ,迫使 ;左側極限為 ,迫使 。
依據: 把 除以 ,得 。
- 4
(b) 矛盾
∎與 兩個要求不相容。折點並非記號造成的假象,它確實違反了定理要求的光滑性。
總結
若連續可微函數有下界且梯度為 -Lipschitz,則對固定步長 :
- 每步至少使 下降 ;
- 梯度範數的平方可和;
- 前 個梯度範數的最小值不超過 ;
- 每個聚點都是駐點;若迭代序列有界,至少存在一個聚點。
迭代點收斂、全局最優、參數恢復和函數值差距的收斂速率都需要額外結構。