不同的優(yōu)化算法采用不同的方法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，以尋找最優(yōu)預(yù)測(cè)模型。其中最重要的兩個(gè)特性就是收斂速率和復(fù)雜度。優(yōu)化算法最初都是確定性的，不過近年來隨著機(jī)器學(xué)習(xí)中數(shù)據(jù)規(guī)模的不斷增大，優(yōu)化問題復(fù)雜度不斷增高，原來越多的優(yōu)化算法發(fā)展出了隨機(jī)版本和并行化版本。依據(jù)算法在優(yōu)化過程中所利用的是一階導(dǎo)數(shù)信息還是二階導(dǎo)數(shù)信息，還可把優(yōu)化算法分為一階方法和二階方法。

1 優(yōu)化問題定義

我們考慮以下有監(jiān)督機(jī)器學(xué)習(xí)問題。假設(shè)輸入數(shù)據(jù)\(D=\{(x_i, y_i)\}_{i=1}^n\)依據(jù)輸入空間\(\mathcal{X} \times \mathcal{Y}\)的真實(shí)分布\(p(x, y)\)獨(dú)立同分布地隨機(jī)生成。我們想根據(jù)輸入數(shù)據(jù)學(xué)得參數(shù)為\(w\)的模型\(h(\space \cdot\space; w)\)，該模型能夠根據(jù)輸入\(x\)給出接近真實(shí)輸出\(y\)的預(yù)測(cè)結(jié)果\(h(x; w)\)。我們下面將參數(shù)\(w\)對(duì)應(yīng)的模型簡(jiǎn)稱為模型\(w\)，模型預(yù)測(cè)好壞用損失函數(shù)\(\mathcal{l}(w; x, y)\)衡量。則正則化經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化（R-ERM）問題的目標(biāo)函數(shù)可以表述如下：

其中\(R(\space \cdot\space)\)為模型\(w\)的正則項(xiàng)。

由于在優(yōu)化算法的運(yùn)行過程中，訓(xùn)練數(shù)據(jù)已經(jīng)生成并且保持固定，為了方便討論且在不影響嚴(yán)格性的條件下，我們將上述目標(biāo)函數(shù)關(guān)于訓(xùn)練數(shù)據(jù)的符號(hào)進(jìn)行簡(jiǎn)化如下：

其中\(f_i(w)=\mathcal{l}(w, x_i, y_i) + \lambda R(w)\)是模型\(w\)在第\(i\)個(gè)訓(xùn)練樣本\((x_i, y_i)\)上的正則損失函數(shù)。
不同的優(yōu)化算法采用不同的方法對(duì)上述目標(biāo)函數(shù)進(jìn)行優(yōu)化，以尋找最優(yōu)預(yù)測(cè)模型。看似殊途同歸，但實(shí)踐中的性能和效果可能有很大差別，其中最重要的兩個(gè)特性就是收斂速率和復(fù)雜度。

2 收斂速率

假設(shè)優(yōu)化算法所產(chǎn)生的模型參數(shù)迭代序列為\(\{w^t\}\)，其中\(w^t\)為第\(t\)步迭代中輸出的模型參數(shù)，R-ERM問題的最優(yōu)模型為\(w^* = \text{arg min}_w f(w)\)。一個(gè)有效的優(yōu)化算法會(huì)使序列\(\{w^t\}\)收斂于\(w^*\)。我們用\(w^t\)與\(w^*\)在參數(shù)空間中的距離來衡量其接近程度，即

若用正則化經(jīng)驗(yàn)風(fēng)險(xiǎn)的差值來衡量，則為

來衡量。
\(\epsilon(t)\)可視為關(guān)于\(t\)的函數(shù)，收斂的算法都滿足隨著\(t\rightarrow \infty\)，有\(\epsilon(t)\rightarrow 0\)，不過其漸進(jìn)收斂速率各有不同。通常用\(\text{log}\space \epsilon(t)\)的衰減速率來定義優(yōu)化算法的漸進(jìn)收斂速率。

• 如果\(\log \epsilon(t)\)與\(-t\)同階，則稱該算法具有線性(linear)收斂率。

  例： \(\mathcal{O}(\text{e}^{-t})\)

• 如果\(\log \epsilon(t)\)比\(-t\)衰減速度慢，則稱該算法具有次線性(sublinear)收斂率。

  例： \(\mathcal{O}(\frac{1}{\sqrt{t}})、\mathcal{O}(\frac{1}{t})、\mathcal{O}(\frac{1}{t^2})\)

• 如果\(\log \epsilon(t)\)比\(-t\)衰減速度快，則稱該算法具有超線性(superlinear)收斂率(進(jìn)一步地，如果\(\log \log \epsilon(t)\)與\(-t\)同階，則該算法有二階收斂速率)。

  例：\(\mathcal{O}(\text{e}^{-\text{2}^t})\)

收斂速率各階數(shù)對(duì)比可參照下圖：

3 復(fù)雜度

優(yōu)化算法的復(fù)雜度需要考慮單位計(jì)算復(fù)雜度與迭代次數(shù)復(fù)雜度。單位計(jì)算復(fù)雜度是優(yōu)化算法進(jìn)行單次迭代計(jì)算需要的浮點(diǎn)運(yùn)算次數(shù)，如給定\(n\)個(gè)\(d\)維樣本，采用梯度下降法來求解模型的單位計(jì)算復(fù)雜度為\(\mathcal{O}(nd)\)，隨機(jī)梯度下降法則是\(\mathcal{O}(d)\)。迭代次數(shù)復(fù)雜度則是指計(jì)算出給定精度\(\epsilon\)的解所需要的迭代次數(shù)。比如若我們的迭代算法第\(t\)步輸出的模型\(w_t\)與最優(yōu)模型\(w^*\)滿足關(guān)系

，若要計(jì)算算法達(dá)到精度\(f(w^t) - f(w^*) \leqslant \epsilon\)所需的迭代次數(shù)，只需令\(\frac{c}{\sqrt{t}}\leqslant \epsilon\)得到\(t \geqslant \frac{c^2}{\epsilon^2}\)，因此該優(yōu)化算法對(duì)應(yīng)的迭代次數(shù)復(fù)雜度為\(\mathcal{O}(\frac{1}{\varepsilon^2})\)。注意，漸進(jìn)收斂速率更多的是考慮了迭代次數(shù)充分大的情形，而迭代次數(shù)復(fù)雜度則給出了算法迭代有限步之后產(chǎn)生的解與最優(yōu)解之間的定量關(guān)系，因此近年來受到人們廣泛關(guān)注。

我們可以根據(jù)單位計(jì)算復(fù)雜度和迭代次數(shù)復(fù)雜度來得到總計(jì)算復(fù)雜度，如梯度下降法單位計(jì)算復(fù)雜度為\(\mathcal{O}(nd)\)，在光滑強(qiáng)凸條件下的迭代次數(shù)復(fù)雜度為\(\mathcal{O}\left(\log(\frac{1}{\varepsilon})\right)\)，則總計(jì)算復(fù)雜度為\(\mathcal{O}\left(nd\log{(\frac{1}{\varepsilon})}\right)\)。隨機(jī)梯度下降法單位計(jì)算復(fù)雜度為\(\mathcal{O}(d)\)，在光滑強(qiáng)凸條件下的迭代次數(shù)復(fù)雜度為\(\mathcal{O}(\frac{1}{\varepsilon})\)，則總計(jì)算復(fù)雜度為\(\mathcal{O}(\fracw0obha2h00{\varepsilon})\)。

4 假設(shè)條件

目前大多數(shù)優(yōu)化算法的收斂性質(zhì)都需要依賴目標(biāo)函數(shù)具有某些良好的數(shù)學(xué)屬性，如凸性和光滑性。近年來由于深度學(xué)習(xí)的成功人們也開始關(guān)注非凸優(yōu)化問題。我們這里先討論凸優(yōu)化的假設(shè)。

凸函數(shù) 考慮實(shí)值函數(shù)\(f:\mathbb{R}^d\rightarrow \mathbb{R}\)，如果對(duì)任意自變量\(w, v \in \mathbb{R}^d\)都有下列不等式成立：

則稱函數(shù)\(f\)是凸的(可以直觀理解為自變量任何取值處的切線都在函數(shù)曲面下方)。

凸性會(huì)給優(yōu)化帶來很大方便。原因是凸函數(shù)任何一個(gè)局部極小點(diǎn)都是全局最優(yōu)解。對(duì)于凸函數(shù)還可以進(jìn)一步區(qū)分凸性的強(qiáng)度，強(qiáng)凸性質(zhì)的定義如下：

強(qiáng)凸函數(shù) 考慮實(shí)值函數(shù)\(f:\mathbb{R}^d\rightarrow \mathbb{R}\)和\(\mathbb{R}^d\)上范數(shù)\(\lVert \space \cdot \space \rVert\)，如果對(duì)任意自變量\(w, v \in \mathbb{R}^d\)都有下列不等式成立：

則稱函數(shù)\(f\)關(guān)于范數(shù)\(\lVert \space \cdot \space \rVert\)是\(\alpha\)-強(qiáng)凸的。
可以驗(yàn)證當(dāng)函數(shù)\(f\)是\(\alpha\)強(qiáng)凸的當(dāng)前僅當(dāng)\(f - \frac{\alpha}{2} \lVert \space\cdot \space \rVert^2\)是凸的。

下圖中給出了凸函數(shù)、強(qiáng)凸函數(shù)和非凸函數(shù)的直觀形象：

光滑性刻畫了函數(shù)變化的緩急程度。直觀上，如果自變量的微小變化只會(huì)引起函數(shù)值的微小變化，我們說這個(gè)函數(shù)是光滑的。對(duì)于可導(dǎo)和不可導(dǎo)函數(shù)，這個(gè)直觀性質(zhì)有不同的數(shù)學(xué)定義。

對(duì)于不可導(dǎo)函數(shù)，通常用Lipschitz性質(zhì)來描述光滑性。

Lipschitz連續(xù) 考慮實(shí)值函數(shù)\(f:\mathbb{R}^d\rightarrow \mathbb{R}\)和\(\mathbb{R}^d\)上范數(shù)\(\lVert \space \cdot \space \rVert\)，如果存在常數(shù)\(L>0\)，對(duì)任意自變量\(w, v \in \mathbb{R}^d\)都有下列不等式成立：

則稱函數(shù)\(f\)關(guān)于范數(shù)\(\lVert \space \cdot \space \rVert\)是\(L\)-Lipschitz連續(xù)的。

對(duì)于可導(dǎo)函數(shù)，光滑性質(zhì)依賴函數(shù)的導(dǎo)數(shù)，定義如下：

光滑函數(shù) 考慮實(shí)值函數(shù)\(f:\mathbb{R}^d\rightarrow \mathbb{R}\)和\(\mathbb{R}^d\)上范數(shù)\(\lVert \space \cdot \space \rVert\)，如果存在常數(shù)\(\beta>0\)，對(duì)任意自變量\(w, v \in \mathbb{R}^d\)都有下列不等式成立：

則稱函數(shù)\(f\)關(guān)于范數(shù)\(\lVert \space \cdot \space \rVert\)是\(\beta\)-光滑的。
下圖是Lipshitz連續(xù)函數(shù)和光滑函數(shù)的直觀形象：

可以驗(yàn)證，凸函數(shù)\(f\)是\(\beta\)-光滑的充分必要條件是其導(dǎo)數(shù)\(\nabla f\)是\(\beta\)-Lipschitz連續(xù)的。所以，\(\beta\)-光滑函數(shù)的光滑性質(zhì)比Lipschitz連續(xù)的函數(shù)的光滑性質(zhì)更好。

5 算法分類和發(fā)展歷史

數(shù)值優(yōu)化算法的發(fā)展歷史如下圖所示：

可以看到，優(yōu)化算法最初都是確定性的，也就是說只要初始值給定，這些算法的優(yōu)化結(jié)果就是確定性的。不過近年來隨著機(jī)器學(xué)習(xí)中數(shù)據(jù)規(guī)模的不斷增大，優(yōu)化問題復(fù)雜度不斷增高，原來越多的優(yōu)化算法發(fā)展出了隨機(jī)版本和并行化版本。

為了更好地對(duì)眾多算法進(jìn)行分析，我們對(duì)其進(jìn)行了如下分類：

• 依據(jù)是否對(duì)數(shù)據(jù)或變量進(jìn)行隨機(jī)采樣，把優(yōu)化算法分為確定性算法和隨機(jī)算法。
• 依據(jù)算法在優(yōu)化過程中所利用的是一階導(dǎo)數(shù)信息還是二階導(dǎo)數(shù)信息，把優(yōu)化算法分為一階方法和二階方法。
• 依據(jù)優(yōu)化算法是在原問題空間還是在對(duì)偶空間進(jìn)行優(yōu)化，把優(yōu)化算法分為原始方法和對(duì)偶方法。

以上分類可以用下圖加以總結(jié)：

我們下面的博客將依次討論一階和二階確定性算法、單機(jī)隨機(jī)優(yōu)化算法和并行優(yōu)化算法，大家可以繼續(xù)關(guān)注。

參考

• [1] 劉浩洋，戶將等. 最優(yōu)化：建模、算法與理論[M]. 高教出版社, 2020.
• [2] 劉鐵巖，陳薇等. 分布式機(jī)器學(xué)習(xí)：算法、理論與實(shí)踐[M]. 機(jī)械工業(yè)出版社, 2018.
• [3] Stanford CME 323: Distributed Algorithms and Optimization (Lecture 7)