為甚麼曲率影響收斂速度?
對光滑凸目標,前面的下降估計給出隨 遞減的界。在更強的條件下,我們可以證明每次更新都消去剩餘誤差的一個固定比例。想像二次損失的等高線是又長又窄的橢圓:能在陡峭方向安全使用的步長,沿平坦方向可能走得很慢。這兩種曲率的比值,可以預告單一固定步長會遇到的困難。
我們研究確定性、無約束的目標;含雜訊梯度和邊界最小值需要另外分析。
假設與記號
定義 21.1.1
(光滑強凸目標)
設 二次連續可微,且存在 ,使每個 都滿足
矩陣不等式按二次型理解。條件數定義為 。固定步長 的梯度下降為 。
下界推出 。特別地,以 代入,右邊在 時趨於無窮,因此 有最小點 。強凸性保證它唯一,而整個 上的可微性給出 。上界則給出係數為 的相應二次上界。這些都是全域假設,不能由某一步觀察到的 Hessian 自動推得。
收縮定理
定理 21.1.2
(平衡曲率的步長)
在上述假設下,取 及 。對每個整數 ,
若 ,一次更新便到達最小點。 的界可獨立理解,或約定 。
證明
(沿線段把誤差線性化)
寫 。沿 到 的線段使用微積分基本定理,
對任意固定向量積分原來的二次型不等式,可得對稱矩陣 亦滿足 。故其每個特徵值 都在 內,而且
代入指定步長,兩端的因子分別為 和 。仿射函數的絕對值在區間上的最大值出現在端點,所以範數因子不大於 。反覆使用便得到距離界。再在 使用二次上界,並利用該處梯度為零,便得目標值界。
證明透視
為甚麼 Hessian 改變仍可證明
兩個曲率界各用了兩次。下界給出 的存在與唯一,以及 ;有了後者,誤差遞推才可從 出發。兩個界合起來,再把每個平均 Hessian 的特徵值限制在 內。關鍵一步是積分形式的中值定理:它把非線性的更新化為精確的線性遞推 ,其中對稱矩陣隨 而變。 可以每一步都不同,也不必與先前的矩陣可交換。我們先統一控制每一步的算子範數,然後才相乘,無須同時對角化。這正是假設必須是全域的原因:只知道起點的 Hessian,並不能控制其後各線段上的平均 Hessian。
對在兩個端點均有特徵值的對稱正定二次函數,固定步長的最壞倍數是 。令兩端大小平衡,得 ,其最小最壞倍數是 。這是針對這些曲率的最壞情況結論,並非每個初始向量都以此步長最快。 很大時, 接近一。重新縮放特徵或採用有理據的預條件法可能改善條件數,但變換變量後須同時改寫目標和更新公式。
另一條路:目標值下降
步長 可直接給出目標值界,完全不用距離 。
定理 21.1.3
(步長 的目標值下降)
在同一假設下,步長 的梯度下降對每個整數 滿足
證明
(合併下降一步與梯度下界)
Hessian 上界給出 。取 ,得
強凸性亦推出 。證法是把強凸性下界視為 的函數,在整個 上取最小:最小值在 取得,等於 ,且不大於 。在第一式取 ,兩邊減去 ,再代入第二式:
反覆使用這個每步因子 ,便得結論。
這是直接控制目標值之差;它與前面的距離界使用不同步長,也使用不同的初始量。單看指數不能證明哪個數值界一定較小。
例題 21.1.4
(細長的二次函數)
設 ,。這裏 、、,平衡步長為 。更新分別把兩個座標乘以 和 ,因此 ,,比 小。第二個座標雖然正負交替,其絕對值仍在收縮。本例的目標值每一步恰好乘以 。
例題 21.1.5
(曲率會變化的非二次目標)
設 上的 。以邏輯斯諦(logistic)函數 表示,有 及 。由於 ,假設在 、 時成立。因此 ,。
最小點滿足 ,沒有閉式解;數值上 。由 出發,梯度是 ,所以 。於是
線段上的平均曲率是 ,正如證明所需,落在 內。由於 ,迭代越過了 ,但誤差仍按保證的因子收縮。
例題 21.1.6
(條件數如何決定迭代次數)
要以平衡步長保證 ,需要 ,即 ,其中 。
當 ,,,所以 足夠。當 ,,,所以 足夠。 增大十倍,保證所需的迭代次數也約增大十倍,因為 很大時 ,得 。在邊界情況 ,,一步便足以達到任何容許誤差。
反例模式
只有光滑性並不保證存在最小值
函數 的梯度是 -Lipschitz,但函數無下界,也沒有最小點。取 ,梯度下降得到 ,任何非零起點都會發散。曲率上界不能代替曲率下界;即使非凸目標的迭代收斂,也未必收斂至全域最小點。
定理是在假設成立時的保證,不是訓練效果的直接測量。神經網絡的經驗目標可能有負曲率或零曲率;有隨機梯度雜訊時,一般亦不能不加修改便把此確定性定理用於每條迭代軌跡。加二次懲罰後要得到強凸性,仍須假設其餘部分凸,或另行證明 Hessian 下界。
常見錯誤
(只看一個 Hessian 就定出 與 )
這兩個常數必須控制迭代點及通往 的線段可能經過的每一點的 Hessian。在非二次例子中,,但 時 ;在其他目標上,起點的曲率可以遠小於別處。只按 選的步長沒有任何保證。
常見錯誤
(以為任何二次懲罰都帶來強凸性)
加上 會把每個 Hessian 特徵值提高 。若其餘部分的曲率低於 ,和仍然不凸: 的二階導數是 。只有其餘部分凸時,懲罰才給出 。
練習與解答
快速檢查
(對 和 ,找出 ,並計算平衡步長的 。)
二階導數是常數。
解答 · 答案
Hessian 為 ,故取 ,,得到 。這是 的特殊情況。
快速檢查
(在細長二次函數例子中,用 計算第一次更新及其目標值。)
每個座標乘以 ,其中 是該座標自己的曲率。
解答 · 答案
兩個倍數是 和 ,所以 ,。一般目標值界只保證不大於 ;對這個起點它雖然有效,卻不緊。
快速檢查
(同一二次函數取 和 ,會發生甚麼?)
計算第二個座標的倍數。
解答 · 答案
第二個倍數為 ,所以 。目標值維持 ,迭代不收斂。嚴格收縮的步長條件不能包括端點 。
快速檢查
(若 、,平衡步長至少迭代多少次,才能保證距離不超過初始距離的百分之一?)
先計算 。
解答 · 答案
這時 ,需要 ,即 。因此 次足夠。這只是最壞情況保證,不表示每個起點都需要十二次。