1，概述

1.1，梯度下降法

假定給定函數(shù)：?，求解該函數(shù)的極小值時，k的取值是多少？

通常做法：對??求導(dǎo)，然后令導(dǎo)數(shù)=0，求解 k 值即為所求：

1.2，迭代與梯度下降求解

求導(dǎo)解法在復(fù)雜實際問題中很難計算。迭代法通過從一個初始估計出發(fā)尋找一系列近似解來解決優(yōu)化問題。其基本形式如下：

其中??被稱為學(xué)習(xí)效率。

假設(shè)初始化??，為了通過迭代讓??趨近最優(yōu)解2，?要滿足兩個條件：

• ?要能使??向最優(yōu)解逼近。
• 當(dāng)??達(dá)到最優(yōu)解時，?要等于0。當(dāng)??達(dá)到最優(yōu)解的時候，?要等于?，即：

因此，我們的核心問題：尋找??滿足上述兩個要求。

1.3，求解思路

隨著迭代的不斷進(jìn)行，?可以使??向最優(yōu)值逼近。而且，當(dāng)??離最優(yōu)值越近時，?的絕對值就越來越小。當(dāng)達(dá)到最優(yōu)解時，。

學(xué)習(xí)速率的取值問題：

• 當(dāng)??取值較大時，即梯度下降迭代的步長較大，梯度下降迭代過程較快?？梢钥焖俚阶顑?yōu)解附近，但是可能一直在最優(yōu)解附近徘徊，無法找出最優(yōu)解。
• 當(dāng)??取值較小時，即梯度下降迭代的步長較小，梯度下降迭代過程較慢。

梯度優(yōu)化：方向+步長

2，梯度下降

2.1，可微函數(shù)的梯度

可微函數(shù)的梯度??：?在? 處，?表示為是? 的偏導(dǎo)數(shù)的向量，即：

梯度下降是一種迭代算法：

• 從初始值? 開始。
• 在每次迭代中，我們沿著當(dāng)前點梯度的負(fù)方向邁出下一步：

其中，?為學(xué)習(xí)率。直觀地說，該算法在梯度點的相反方向上邁出了一小步，從而降低了函數(shù)的值。在? 次迭代之后，算法輸出最后一個向量?。

輸出也可以是平均向量?。取平均值是非常有用的，特別是當(dāng)我們將梯度下降推廣到不可微函數(shù)和隨機(jī)情況時。

【證明】，即：梯度不斷下降。

由于，。

由于?，學(xué)習(xí)率?，所以 ，故：

2.2，梯度下降算法的收斂速率

Lipschitz連續(xù)：對于在實數(shù)集的子集的函數(shù)?，若存在常數(shù)?，使得??，則稱函數(shù)?符合利普希茨條件。

為了分析GD算法的收斂速度，我們僅限于凸 Lipschitz 函數(shù)的情況。?是??在?條件下的最小值的點坐標(biāo)。

• 假設(shè)：
• 求證：?有界

2.3，凸函數(shù)性質(zhì)?

凸函數(shù)性質(zhì)（1）：

證明方法（1）：

即，判斷上述關(guān)系即可：

從圖上可以看出，，且趨近于0時取等號。

故，

凸函數(shù)性質(zhì)（2）：

證明：將??進(jìn)行泰勒展開可得：

?，且??處為偏導(dǎo)最小處，即??。

?，且??處為偏導(dǎo)最小處，即??。

即：

故：

因此：

?

合體證明性質(zhì)（1）（2）：

2.4，求解收斂速率

設(shè)? 是向量的任意序列。任何具有初始化? 和以下形式的更新規(guī)則的算法：

滿足：

前提（1）：

前提（2）：

證明：

即：

特別的，對每個??，如果對所有的??都存在??使得??，且對每個??且?，都存在：

證明：由前面可得

令?

令??，可得??得極小值，因此也是T的最小值。

且：

，當(dāng)且僅當(dāng)??

在允許一定誤差的情況下：對任意的??，使得：

則必須滿足：

即：，T 存在最小值。

3，子梯度

3.1，為何需要子梯度

次梯度方法是傳統(tǒng)的梯度下降方法的拓展，用來處理不可導(dǎo)的凸函數(shù)。它的優(yōu)勢是比傳統(tǒng)方法處理問題范圍大，劣勢是算法收斂速度慢。

對于光滑的凸函數(shù)而言，我們可以直接采用梯度下降算法求解函數(shù)的極值，但是當(dāng)函數(shù)不處處光滑、處處可微的時候，梯度下降就不適合應(yīng)用了。因此，我們需要計算函數(shù)的次梯度。對于次梯度而言，其沒有要求函數(shù)是否光滑，是否是凸函數(shù)，限定條件很少，所以適用范圍更廣。

允許? 是一個開凸集。?函數(shù)? 是一個凸函數(shù)。滿足下列條件的向量?：

稱為? 在? 處的次梯度。?在?處的次梯度集稱為微分集并表示為 。?

3.2，計算次梯度

【定義法】如果??在? 處可微，那么? 包含一個元素? 在? 處的梯度為?。例如：?。

?由于??在??處不可導(dǎo)，因此根據(jù)定義：

?

即：

【對比法】令??關(guān)于??的凸可微函數(shù)??。存在某些??使得??，則 ?。

此時，取值C，D處作為次梯度點。

證明：

前提：

選擇 C 作為次梯度點：

即，可得：

可得：

選擇 B? 作為次梯度點：

即，可得：

?此時，?無解，故不可作為次梯度點。

4，隨機(jī)梯度下降

4.1，核心思想

在隨機(jī)梯度下降中，我們不要求更新方向完全基于梯度。相反，我們允許方向為隨機(jī)向量，并要求其期望值為當(dāng)前向量處函數(shù)的次梯度。

在隨機(jī)梯度下降中，我們不要求更新方向完全基于梯度。相反，我們允許方向為隨機(jī)向量，并要求其期望值為當(dāng)前向量處函數(shù)的次梯度。

SGD偽碼：在學(xué)習(xí)問題的背景下，很容易找到期望值為風(fēng)險函數(shù)次梯度的隨機(jī)向量。例如，每個樣本的風(fēng)險函數(shù)梯度。

4.2，使用SGD實現(xiàn)SVM

機(jī)器學(xué)習(xí)：支持向量機(jī)（SVM）_燕雙嚶-CSDN博客1，算法描述支持向量機(jī)（SVM）是用來解決分類問題的。作為數(shù)據(jù)挖掘領(lǐng)域中一項非常重要的任務(wù)，分類目前在商業(yè)上應(yīng)用最多（比如分析型CRM里面的客戶分類模型、客戶流失模型、客戶盈利等，其本質(zhì)上都屬于分類問題）。而分類的目的則是構(gòu)造一個分類函數(shù)或分類模型，該模型能吧數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個，從而可以用來預(yù)測未知類別。先考慮最簡單的情況，比如豌豆和米粒，用篩子很快可以分離它們，小顆粒漏下去，大顆粒保留。用函數(shù)來表示就是當(dāng)直徑d大于某個值D，就判定其為豌豆，小于D就是米粒。在數(shù)軸上就是D左邊https://shao12138.blog.csdn.net/article/details/121164645當(dāng)最優(yōu)化時的函數(shù)不是全區(qū)間可微時，無法通過對偶問題解決，此時可以使用SGD實現(xiàn)SVM。

為了應(yīng)用SGD，我們必須將上式中的優(yōu)化問題轉(zhuǎn)化為無約束問題：

更新規(guī)則：

求梯度可得：

：在迭代? 選擇的隨機(jī)例子上，?處損失函數(shù)的次梯度。

4.3，SGD的收斂速度

?特別的，對每個??，如果對所有的??都存在??使得??，且對每個??且?，都存在：

證明：

由2.3節(jié)證明的性質(zhì)可得：

下面過程同2.4節(jié)，得：

，

故：

即證明：

同理，如果使得??都成立，則要求：

即：，T 存在最小值。

4.4，投影步驟

在之前對GD和SGD算法的分析中，我們要求??，這相當(dāng)于對??劃定了一個半徑為??的區(qū)間，然后進(jìn)行選擇。

但大部分時候我們無法保證全部的???的時候，可以采用增加投影的方法求解問題：?

，不考慮范圍求得一個值。

，然后投影到??上。

我們可以求得，D為最近的點，即投影點，B，E也是，但是不是最小的投影點。