梯度下降（Gradient Descent）的收敛性分析
?作者 | 黃秋實
單位 | 香港中文大學（深圳）
研究方向 | 智能電網
梯度下降是一種簡單且常用的優化方法，它可以被用來求解很多可導的凸優化問題（如邏輯回歸，線性回歸等）。同時，梯度下降在非凸優化問題的求解中也占有一席之地。我們常聽到神經網絡（neural network），也常常使用梯度下降及其變種（如隨機梯度下降，Adam 等）來最小化經驗誤差（empirical loss）。
不妨設可導的目標函數（objective function）為f(w)，其中 w 為優化變量。對于優化問題（1）：
我們可以使用如下算法進行求解：
隨機初始化優化變量 ?
重復如下步驟直至收斂：，其中 為優化步長
算法收斂后得到的 即為原優化問題的一個解。顯然，對于凸優化問題，梯度下降可以讓帶領我們找到全局的最優解（global minima）；但是對于非凸優化問題，梯度下降有很大的可能只能讓我們得到一個局部最優（local minima）或者鞍點（saddle point）。
1. 在什么條件下，梯度下降可以保證 更新后的目標函數值 更小？
2. 優化步長 應該如何設定？可以隨意選擇嗎？
3. 梯度下降的優化算法為什么可以收斂？收斂的速度又是多快呢？
為了回答以上問題，我們需要先回顧一些數學知識。
多元泰勒展開（multivariate Taylor expansion）
對于一個二階可導的函數 ，它的泰勒展開可以表示為：
其中， 和 為函數定義域中任意兩點， 是 和 眾多凸組合（convex combination）中的一個（）。
Lipschitz 連續性
給定兩個度量空間 和 ， 是集合 X 上的測度， 是集合 Y 上的測度。一個從集合 X 到集合 Y 函數 滿足 Lipschitz 連續，則存在一個常數 對于集合 X 中任意兩點 和 有：
因此對于函數 ，若其滿足 Lipschitz 連續，則對于任意兩點 w 和 v，都滿足：
一個函數 f(x) 滿足 Lipschitz 連續，可以理解為該函數的變化速率受到了限制。這個變化速率的上界就被稱為 Lipschitz 常數。函數梯度的 Lipschitz 連續性在實際情況中相對容易得到滿足，因為真實世界中的數據的變化幅度并不大。這也是很多其他數據處理方法物理釋義，例如應用數據低秩性與稀疏性的 Robust PCA 等用壓縮感知方法。對于常用的機器學習模型，例如邏輯回歸，SVM等方法，大多可以證明其損失函數的梯度在一定條件下滿足 Lipschitz 連續性。但是對于深度學習模型，我們無法證明。
有了如上兩個至關重要的數學知識，我們就可以開始回答最開始的問題了。我們首先去回答：在什么條件下，梯度下降可以保證 更新后的目標函數值 更小？
下降引理 （Descent Lemma）
對于一個二階可導的函數 ，它的導數 滿足 Lipschitz 連續，則它的 Hessian 矩陣滿足：
我們可以從這個角度來理解式（5）：首先，我們知道導數 變化最快的方向就是它的 Hessian 矩陣 絕對值最大特征值所對應的特征向量。由于 Hessian 矩陣 是對稱矩陣（symmetric matrix），于是根據 Rayleigh quotient，我們就可以得到，對于任意 v 都滿足：
因此，對于導數 滿足 Lipschitz 連續的函數 ，它任意點 w 的 Hessian 矩陣 都滿足 ，即式（5）。
當我們對這樣滿足二階可導，且導數 滿足 Lipschitz 連續的函數 進行泰勒展開時，我們可以得到
式（7）就是很多梯度相關的優化算法收斂性證明中常用的下降引理。
應用下降引理，我們就可以直接回答當前的問題了。我們將梯度下降的更新公式 代入式（7）中，我們就可以得到：
從式（8）中，我們可以看到，由于 ，所以當 時（即 ），我們就可以保證梯度下降算法的更新過程中，目標函數值的大小始終保持單調遞減（非嚴格）的狀態。并且當優化步長選取 時， 目標函數值縮減的速度最快（讀者可以自行驗證）。因此，我們可以看到選擇最優的優化步長其實就是在估計目標函數的 Lipschitz 常數。
梯度下降的收斂性與收斂速度
在上面的論述中，我們已經回答了梯度下降算法為什么可以優化目標函數，讓每一步優化得到的結果的目標函數的函數值更小。同時我們也給出了如何選擇優化步長的指標?，F在我們就來回答，為什么梯度下降的優化算法可以收斂？它的收斂速度又是多少？
梯度下降算法收斂性的證明依賴于如下三個條件：
目標函數的梯度 滿足 Lipschitz 連續?
目標函數 ，即目標函數有一個下界?
優化步長 ?
我們來簡單分析一下這三個條件：條件（1）和條件（3）使得下降引理成立，保證了梯度下降算法在優化目標函數過程中的正確性。同時，條件（3）也使得梯度下降算法處于收斂速度最快的狀態，這有助于我們對算法收斂速度進行計算。條件（2）是一個不可或缺的條件，它保證了原始的優化問題存在可行解。例如，當 時，我們可以看到這個優化問題并不存在可行解；而當 時，這個優化問題就存在唯一可行解 。
我們注意到我們平時常用的損失函數，例如交叉熵，均方誤差等，在一定的范圍內（部分損失函數會依賴于一個好的初始值的選擇）都可以滿足以上三個條件。
首先我們證明梯度下降的收斂性。對于梯度下降算法的收斂條件，我們可以遵循如下定義：
其中 為任意常數， 是對應的收斂指標。根據優化定理，我們將優化步長 代入式（8），進而可以得到：
因此，當我們將前 K 步的 進行加和時，我們可以（神奇的）得到：
但是式（11）左側的部分仍和 t 相關，我們可以通過放縮來去除它們與 t 之間的相關性。我們將每一個 放縮成為 進而得到：
于是，我們就得到了，從 到 的一共 步， 個梯度中，至少存在一個最小的梯度滿足
由式（13），我們知道：雖然我們無法保證梯度下降的更新過程中每一步的 都隨著算法迭代次數的增加而減小；但是對于收斂指標為 的情況下，算法可以保證在 步之內收斂。同時，對于任意給定的收斂指標 ，我們可以保證算法在 步之內收斂。
文章部分內容參考 [1]，Lipschitz 連續性部分參考 [2]。
參考文獻
[1] CPSC 540 - Machine Learning (January-April, 2018)?https://www.cs.ubc.ca/~schmidtm/Courses/540-W18/
[2] Lipschitz_continuity?https://en.wikipedia.org/wiki/Lipschitz_continuity
更多閱讀
#投 稿?通 道#
?讓你的文字被更多人看到?
如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。
總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?
PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。
📝?稿件基本要求：
? 文章確系個人原創作品，未曾在公開渠道發表，如為其他平臺已發表或待發表的文章，請明確標注?
? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發送，要求圖片清晰，無版權問題
? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創首發稿件，提供業內具有競爭力稿酬，具體依據文章閱讀量和文章質量階梯制結算
📬?投稿通道：
? 投稿郵箱：hr@paperweekly.site?
? 來稿請備注即時聯系方式（微信），以便我們在稿件選用的第一時間聯系作者
? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿
△長按添加PaperWeekly小編
🔍
現在，在「知乎」也能找到我們了
進入知乎首頁搜索「PaperWeekly」
點擊「關注」訂閱我們的專欄吧
·
總結
以上是生活随笔為你收集整理的梯度下降（Gradient Descent）的收敛性分析的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： win10怎么更改屏保时间设置 Win1
- 下一篇： 微软surface pro3怎么u启动