論文鏈接：https://arxiv.org/abs/1706.10207

摘要：本篇論文旨在介紹關(guān)于將最優(yōu)化方法應(yīng)用于機(jī)器學(xué)習(xí)的關(guān)鍵模型、算法、以及一些開放性問(wèn)題。這篇論文是寫給有一定知識(shí)儲(chǔ)備的讀者，尤其是那些熟悉基礎(chǔ)優(yōu)化算法但是不了解機(jī)器學(xué)習(xí)的讀者。首先，我們推導(dǎo)出一個(gè)監(jiān)督學(xué)習(xí)問(wèn)題的公式，并說(shuō)明它是如何基于上下文和基本假設(shè)產(chǎn)生各種優(yōu)化問(wèn)題。然后，我們討論這些優(yōu)化問(wèn)題的一些顯著特征，重點(diǎn)討論 logistic 回歸和深層神經(jīng)網(wǎng)絡(luò)訓(xùn)練的案例。本文的后半部分重點(diǎn)介紹幾種優(yōu)化算法，首先是凸 logistic 回歸，然后討論一階方法，包括了隨機(jī)梯度法（SGD）、方差縮減隨機(jī)方法（variance reducing stochastic method）和二階方法的使用。最后，我們將討論如何將這些方法應(yīng)用于深層神經(jīng)網(wǎng)絡(luò)的訓(xùn)練，并著重描述這些模型的復(fù)雜非凸結(jié)構(gòu)所帶來(lái)的困難。

1 引言

在過(guò)去二十年里，機(jī)器學(xué)習(xí)這一迷人的算法領(lǐng)域幾乎以史無(wú)前例的速度崛起。機(jī)器學(xué)習(xí)以統(tǒng)計(jì)學(xué)和計(jì)算機(jī)科學(xué)為基礎(chǔ)，以數(shù)學(xué)優(yōu)化方法為核心。事實(shí)上，近來(lái)優(yōu)化方法研究領(lǐng)域中的許多最新理論和實(shí)際進(jìn)展都受到了機(jī)器學(xué)習(xí)和其它數(shù)據(jù)驅(qū)動(dòng)的學(xué)科的影響。然而即使有這些聯(lián)系，統(tǒng)計(jì)學(xué)、計(jì)算機(jī)科學(xué)和致力于機(jī)器學(xué)習(xí)相關(guān)問(wèn)題的優(yōu)化方法研究之間仍存在許多障礙。因此本文試圖概述機(jī)器學(xué)習(xí)學(xué)習(xí)算法而打破這種障礙。

本篇論文的目的是給出與機(jī)器學(xué)習(xí)領(lǐng)域相關(guān)的一些關(guān)鍵問(wèn)題和研究問(wèn)題的概述?？紤]到涉及運(yùn)籌學(xué)領(lǐng)域的知識(shí)，我們假設(shè)讀者熟悉基本的優(yōu)化方法理論，但是仍將引入在廣義機(jī)器學(xué)習(xí)領(lǐng)域使用的相關(guān)術(shù)語(yǔ)和概念，希望借此促進(jìn)運(yùn)籌學(xué)專家和其它貢獻(xiàn)領(lǐng)域的人員之間的溝通。為了實(shí)現(xiàn)這一目的，我們?cè)谠~匯表 1 中列出了本論文將介紹和使用的最重要的術(shù)語(yǔ)。

1.1 闡明動(dòng)機(jī)
1.2 學(xué)習(xí)問(wèn)題和優(yōu)化問(wèn)題
1.3 學(xué)習(xí)邊界、過(guò)擬合和正則化

2 解決Logistic回歸問(wèn)題的優(yōu)化方法（淺層模型的優(yōu)化方法）

當(dāng) L 和 r 是關(guān)于 w 的任意凸函數(shù)時(shí)，可以運(yùn)用在本節(jié)中討論的方法來(lái)解決問(wèn)題（11）：

這一類中包含很多機(jī)器學(xué)習(xí)模型，包括支持向量機(jī)、Lasso（Least Absolute Shrinkage and Selection Operator）、稀疏逆協(xié)方差選擇等。有關(guān)這些模型的詳細(xì)信息請(qǐng)參見 [86] 和其中的參考文獻(xiàn)。為了每一步都能具體（展現(xiàn)出來(lái)），此處我們指定以二分類的正則化logistic回歸為例（進(jìn)行講解）。為了簡(jiǎn)化例子中的符號(hào)，我們作不失一般性的假設(shè)，令。（此處省去了偏置項(xiàng) b0），這一省略操作可以通過(guò)在輸入向量上增加一維恒為 1 的特征值來(lái)彌補(bǔ)）。當(dāng) w 和 x 都是 d 維時(shí)就可以令其為特定的凸優(yōu)化問(wèn)題。

值得一提的是，對(duì)于此類問(wèn)題，正則化項(xiàng)必不可少。想一想為什么說(shuō)它必不可少，假設(shè)對(duì)于所有的 i ∈{1,...,n}，有參數(shù)向量 w，滿足 yi(wT*xi) > 0 以及（存在）無(wú)界射線 {θw : θ > 0}。那問(wèn)題就很明朗了，在這個(gè)例子中，當(dāng) θ →∞時(shí)，

也就是說(shuō)函數(shù)（式 12）無(wú)法取最小值。另一方面，通過(guò)增加（強(qiáng)制）正則化函數(shù) r，可以保證問(wèn)題（12）將具有最優(yōu)解。

對(duì)于正則化函數(shù) r，我們將會(huì)參考常用選擇和 r(w) = ||w||1。不過(guò)為了簡(jiǎn)單起見，我們通常會(huì)選擇前者，因?yàn)樗沟霉?12 對(duì)于每一個(gè)因子是連續(xù)可微的。相反，r(w) = ||w||1 會(huì)導(dǎo)致非平滑問(wèn)題，為此，（實(shí)現(xiàn)）函數(shù)最小化就需要更復(fù)雜的算法。

2.1 一階方法

我們首先討論用一階方法求解問(wèn)題（12），這里的」一階」僅僅指對(duì)函數(shù) F 中的參數(shù)進(jìn)行一階偏導(dǎo)的數(shù)學(xué)技巧。

2.1.1 梯度下降法

從概念上講，最小化光滑凸目標(biāo)的最簡(jiǎn)單的方法是梯度下降法，具體分析參見 [ 62 ]。在這種方法中，從初始化估計(jì)值 w0 開始，通過(guò)下述公式迭代地更新權(quán)重估計(jì)值。

其中 αk > 0 是一個(gè)步長(zhǎng)參數(shù)。步長(zhǎng)序列 {αk} 的選擇直接決定此算法的性能。在優(yōu)化研究領(lǐng)域，人們普遍認(rèn)為，在每次迭代中采用線性搜索來(lái)確定 {αk }，可以為解決各種類型的問(wèn)題找到一個(gè)性能優(yōu)越的算法。然而，對(duì)于機(jī)器學(xué)習(xí)應(yīng)用程序來(lái)說(shuō)，這種運(yùn)算成本高昂，因?yàn)槊看魏瘮?shù) F 的計(jì)算都需要傳遞整個(gè)數(shù)據(jù)集，如果 n 過(guò)大，很可能帶來(lái)高昂的（訓(xùn)練）成本。

好在當(dāng)每個(gè)αk 都設(shè)置為一個(gè)正的常數(shù)α且它是一個(gè)足夠小的固定值時(shí)，從理論上分析，該算法的收斂性仍可以得到保證。（固定的步長(zhǎng)常數(shù)在機(jī)器學(xué)習(xí)領(lǐng)域叫做學(xué)習(xí)率。但即使不是常數(shù)，也有人把αK 或整個(gè)序列 {αK } 叫做學(xué)習(xí)率）。該算法的收斂速度取決于函數(shù) f 是強(qiáng)凸函數(shù)還是弱凸函數(shù)。

用于解決 L1 范數(shù)正則化的logistic回歸問(wèn)題的梯度下降和加速梯度下降拓展算法分別被稱作 ISTA 和 FISTA。我們觀察到，在這種情況下，即使λ> 0，目標(biāo)函數(shù)也不會(huì)是強(qiáng)凸函數(shù)。只有目標(biāo)函數(shù)為凸時(shí) [5]，ISTA 和 FISTA 具有與其對(duì)應(yīng)的平滑函數(shù)相同的次線性收斂速度。

梯度下降在 ML 訓(xùn)練過(guò)程中的一個(gè)重要特性就是計(jì)算出每次迭代中求解函數(shù) F 的梯度的運(yùn)算成本。在 ML 的訓(xùn)練過(guò)程中，單個(gè)梯度計(jì)算的成本通常是 O（ND），這個(gè)確實(shí)可以看到，例如，在正則化項(xiàng)為的情況中，函數(shù) F 關(guān)于每一個(gè)特定的 w 的梯度是

2.1.2 隨機(jī)梯度法

隨機(jī)梯度法由于其用于最小化隨機(jī)目標(biāo)函數(shù)而在運(yùn)籌學(xué)領(lǐng)域廣為人知，同時(shí)也是 ML 社區(qū)中的一種特征優(yōu)化算法。該算法最初由 Robbins 和 Monro [ 67 ] 在解決隨機(jī)方程組問(wèn)題時(shí)提出，值得注意的是，它可以用于最小化具有良好收斂性的隨機(jī)目標(biāo)，而且每次迭代的計(jì)算復(fù)雜度僅為 O（d）而不是 O（nd）（梯度下降中的計(jì)算復(fù)雜度）。

在每一次迭代中，隨機(jī)梯度法都會(huì)計(jì)算梯度 F（Wk）的無(wú)偏估計(jì) GK。該估計(jì)可以以及低的代價(jià)計(jì)算得到；例如，對(duì)于公式（12），某次迭代的隨機(jī)梯度可被求解為

其中 Sk 被稱作小批量，它的所有元素都是從總數(shù)據(jù)集 {1,...,n} 中按均勻分布選出來(lái)的。接下來(lái)的運(yùn)算類似于梯度下降：

毫無(wú)疑問(wèn)，該算法的關(guān)鍵在于選擇步長(zhǎng)序列 {αk}。不同于梯度下降，固定的步長(zhǎng)（即學(xué)習(xí)率）不能保證算法會(huì)收斂到強(qiáng)凸函數(shù) F 的最小值，而只保證收斂到最小值的鄰域。

SGD 的收斂速度比梯度下降慢。尤其當(dāng)函數(shù) F 是強(qiáng)凸函數(shù)時(shí)，該算法只保證當(dāng) k ≥ O(1/ε) 時(shí)可以得到預(yù)期精度的解（即滿足 E[F(wk)]-F(w) ≤ ε的解），而當(dāng)函數(shù) F 僅僅是凸函數(shù)時(shí)，只有在 k ≥ O(1/ε^2) [11] 時(shí)才能保證得出上述解。

另一方面，正如前文提及的，如果 Sk 的大小由一個(gè)常數(shù)限定（獨(dú)立于 n 或 k 的常數(shù)），那么 SGD 的每次的迭代成本都比梯度下降法小 0（n）倍。

然而，在實(shí)際運(yùn)用中，標(biāo)準(zhǔn)的 SGD 并不一定是解決機(jī)器學(xué)習(xí)中優(yōu)化問(wèn)題的最有效方法。事實(shí)上，機(jī)器學(xué)習(xí)和優(yōu)化算法領(lǐng)域在開發(fā)改進(jìn)或替代 SGD 方面進(jìn)行了大量的積極研究。在隨后的兩部分中，我們將討論兩類方法：方差縮減法和二階方法。但是在這兩類方法以外，還有多種方法。例如，加有動(dòng)量的 SGD 就是一個(gè)實(shí)踐中被發(fā)現(xiàn)的性能好于好于標(biāo)準(zhǔn) SGD 的拓展版 SGD。見下圖算法 1

2.1.3 方差縮減法（Variance reducing method）

考慮到問(wèn)題（11），人們發(fā)現(xiàn)通過(guò)利用目標(biāo) F 的結(jié)構(gòu)作為 n 個(gè)函數(shù)的有限和再加上簡(jiǎn)單的凸函數(shù)項(xiàng)，可以改善 SGD 方法。目前已經(jīng)研究出幾種方法，如 SAG [74]，SAGA [22]，SDCA [76] 和 SVRG [44]。

為了方便引用，我們把 SVRG 叫做算法 2。該算法在每個(gè)外部迭代中執(zhí)行一次完整的梯度計(jì)算，然后沿著隨機(jī)方向再迭代 L 步，這是整個(gè)梯度的隨機(jī)修正過(guò)程。內(nèi)環(huán)步長(zhǎng) L（inner loop size）必須滿足一定的條件以保證收斂 [ 44 ]。

SVRG，全稱為隨機(jī)方差減小梯度，其名稱源自于該算法可以被視為 SGD 的方差減小變體（尤其是有限和最小化/finite-sum minimization）。

研究員通過(guò)結(jié)合 SVRG 和 SAGA 的一些思想，提出一個(gè)新的方法，叫做 SARAH。僅是內(nèi)層迭代步長(zhǎng)不同于 SVRG，SARAH 的公式如下

該變化導(dǎo)致 ，使得 SARAH 中的步長(zhǎng)不基于無(wú)偏梯度估計(jì)。不過(guò)，相對(duì)于 SVRG，它獲得了改進(jìn)的收斂特性。

表 2 ： 最小化強(qiáng)凸函數(shù)的一階方法計(jì)算復(fù)雜度

表 3 ： 最小化一般凸函數(shù)的一階方法計(jì)算復(fù)雜度

2.2 二階方法和擬牛頓法

受確定性優(yōu)化研究領(lǐng)域幾十年研究成果的激勵(lì)，ML 優(yōu)化中最活躍的研究領(lǐng)域之一就是關(guān)于如何使用二階導(dǎo)數(shù)（即曲率）信息來(lái)加速訓(xùn)練。

不幸的是，當(dāng) n 或 d 很大時(shí)，在機(jī)器學(xué)習(xí)應(yīng)用程序中，海塞矩陣（Hessian matrix）的計(jì)算和存儲(chǔ)變得非常昂貴。

另一類基于形如（21）模型的算法是擬牛頓方法：

有趣的是，這些方法沒有計(jì)算出顯式二階導(dǎo)數(shù)，而是通過(guò)在每次迭代中應(yīng)用低秩更新構(gòu)造完全由一階導(dǎo)數(shù)的海塞近似矩陣。例如，讓我們簡(jiǎn)要介紹最流行的擬牛頓算法，全稱為 Broyden-Fletcher-Goldfarb-Shanno（BFGS）方法。在這種方法中，我們首先可以看到（21）的最小值為、進(jìn)一步發(fā)現(xiàn)它實(shí)際上可以方便地計(jì)算出逆 Hessian 近似。由于隨著步長(zhǎng) sk = w_k+1 − wk 和位移 yk = ∇F(wk+1) − ∇F(wk) 的移動(dòng)，有人選擇 以最小化以滿足割線方程 sk = (B^-1)yk。使用精心挑選的規(guī)范表達(dá)，這個(gè)問(wèn)題的解析式可以顯示的寫成

其中之間的差異可以僅表示為二階矩陣。

為方便引用，完整的經(jīng)典 BFGS 算法被稱為算法 3。

即使采用二階信息，隨機(jī)優(yōu)化方法（無(wú)差異減少）也無(wú)法達(dá)到比次線性更快的收斂速度。不過(guò)，使用二階信息是一個(gè)不錯(cuò)的想法，因?yàn)槿绻Ｈ凭仃囀諗坑诤Ｈ仃嚨恼鎸?shí)解，則可以減少收斂速度中的常數(shù)，同時(shí)還可以減少病態(tài)（ill-conditioning）的影響。

不幸的是，盡管已經(jīng)觀察到了實(shí)際的效率提升，但在理論上還沒有一個(gè)真正的二階方法，可以實(shí)現(xiàn)這樣的提升。到目前為止，只要海塞（近似）矩陣保持良好特性，大多數(shù)實(shí)際的方法只能保證實(shí)現(xiàn) SGD 的收斂（速率）特性。例如，如果序列 {Bk}（不一定由 BFGS 更新生成）對(duì)所有 k 滿足：

此時(shí)具有與 SGD 相同的收斂速度屬性。我們就 可以合理地假設(shè)這些限定適用于上述討論的方法，這些假設(shè)有適當(dāng)?shù)谋Ｕ?。然而，在擬牛頓方法的背景下應(yīng)該小心，其中隨機(jī)梯度估計(jì)可能與海塞近似相關(guān)。

3 深度學(xué)習(xí)

沿著這些方向進(jìn)行的主要進(jìn)展包括深層神經(jīng)網(wǎng)絡(luò)（DNN）的運(yùn)用。機(jī)器學(xué)習(xí)的一個(gè)相應(yīng)的分支稱為深度學(xué)習(xí)（或分層學(xué)習(xí)），它代表了一類試圖通過(guò)使用包含連續(xù)線性和非線性變換的多層次深層圖來(lái)構(gòu)造數(shù)據(jù)中高層次抽象的算法 [6, 51, 73, 37, 38, 23]。近年來(lái)科學(xué)家們已經(jīng)研究了各種神經(jīng)網(wǎng)絡(luò)類型，包括全連接神經(jīng)網(wǎng)絡(luò)（FNN）[84,28]，卷積神經(jīng)網(wǎng)絡(luò)（CNN）[50] 和循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）[41,57,52]。對(duì)于我們來(lái)說(shuō)，將主要關(guān)注前兩類神經(jīng)網(wǎng)絡(luò)，同時(shí)留意其它網(wǎng)絡(luò)。

3.1 問(wèn)題公式化
3.2 隨機(jī)梯度下降法

我們引用以下內(nèi)容來(lái)強(qiáng)調(diào)將優(yōu)化算法應(yīng)用于訓(xùn)練 DNN 的令人困惑的反應(yīng)。首先，例如在 [11] 中，有一個(gè)結(jié)論表明，通過(guò)應(yīng)用 SGD 來(lái)最小化非凸目標(biāo)函數(shù)（一直從輸入×輸出空間繪制），可以保證預(yù)期梯度風(fēng)險(xiǎn)將消失，至少在一個(gè)子序列上是這樣，即：。這一結(jié)論令人欣慰，這表明 SGD 可以實(shí)現(xiàn)與其他最先進(jìn)的基于梯度的優(yōu)化算法類似的收斂保證。然而，盡管文獻(xiàn)中的種種保證是有局限性的; 畢竟，盡管許多基于梯度的優(yōu)化算法確保目標(biāo)函數(shù)單調(diào)減少，但 SG 并不以這種方式計(jì)算。因此，如果一個(gè)子序列收斂到一個(gè)固定點(diǎn)，那么我們?cè)趺茨艽_定該點(diǎn)不是鞍點(diǎn)，或者是有誤差局部最小值，亦或是一些目標(biāo)值比初始點(diǎn)差的最大值？事實(shí)上，我們并不能肯定。也就是說(shuō)，SGD 方法通常擅長(zhǎng)找到局部極小值，而不是全局最小值。另一方面，SGD 往往會(huì)在固定值附近減緩收斂速度，這可能會(huì)阻礙它在深度神經(jīng)網(wǎng)絡(luò)中發(fā)展。

一般來(lái)說(shuō)，對(duì)于非凸問(wèn)題，SGD 的收斂速度記錄在 [29,30]，但是它們非常有限，特別是它們不適用于§1.3 中的討論。因此，我們不能以同樣的方式爭(zhēng)論 SGD 是機(jī)器學(xué)習(xí)中非凸優(yōu)化問(wèn)題的最佳方法。此外，下式

中的學(xué)習(xí)界限是沒有用的，因?yàn)閷?duì)于許多 DNN 和 CNN，由神經(jīng)網(wǎng)絡(luò)產(chǎn)生的分類的復(fù)雜度 C 比訓(xùn)練樣本數(shù) n 大得多。事實(shí)上，在 [90] 中，經(jīng)驗(yàn)表明，只有這些集合中的數(shù)據(jù)隨機(jī)擾動(dòng)，神經(jīng)網(wǎng)絡(luò)才能輕易地超過(guò)典型的數(shù)據(jù)集類型。

3.3 海塞-自由優(yōu)化方法（Hessian-free method）

有研究者發(fā)現(xiàn)我們可以修改 DNN 的反向傳播算法來(lái)計(jì)算這樣的海塞-矢量乘積，因?yàn)樗鼈兛梢员豢醋魇欠较驅(qū)?shù) [65]。計(jì)算這種乘積的復(fù)雜度只是比計(jì)算梯度多一個(gè)常數(shù)因子。所得到的類的方法通常被稱為海塞-自由優(yōu)化方法，因?yàn)楫?dāng)訪問(wèn)和使用 Hessian 信息時(shí)，沒有顯式地存儲(chǔ) Hessian 矩陣。

由于目標(biāo)函數(shù)的非凸性，在 DNN 的情況中出現(xiàn)了其它的問(wèn)題，真正的海塞矩陣可能不是正定矩陣。一般來(lái)說(shuō)，在確定性優(yōu)化中，處理這個(gè)問(wèn)題的兩種可能的方法是修改海森矩陣和運(yùn)用置信域（trust region）方法。這兩種方法都在訓(xùn)練 DNN 的情況中探討過(guò)，例如，在 [54,55] 中，提出了一種高斯牛頓法，其在（11）中函數(shù) F 的 Hessian 的公式中的第一項(xiàng)近似于 Hessian 矩陣（省略了正則化項(xiàng)）

其中是關(guān)于第一個(gè)參數(shù)的損失函數(shù) l(·, ·) 的海塞矩陣，∇p(w, xi) 是 dy-維函數(shù) p(w, x) 對(duì)于權(quán)重 w 的雅可比式，∇^2 [pj (w, xi)] for all j ∈ {1, . . . , dy} 是關(guān)于 w 的按元素運(yùn)算的海塞矩陣。

3.4 子采樣海森方法（Subsampled Hessian method）

最近，在一系列論文（3, 15, 34）中，研究員們利用一個(gè)很一般的隨機(jī)模型框架，對(duì)凸區(qū)域和非凸情形下的置信域、線搜索和自適應(yīng)三次正則化方法進(jìn)行了分析。在這項(xiàng)工作中，它表明，只要梯度和 Hessian 估計(jì)是足夠準(zhǔn)確的一些正概率，使用隨機(jī)不精確梯度和 Hessian 信息的標(biāo)準(zhǔn)優(yōu)化方法就可以保留其收斂速度。

在機(jī)器學(xué)習(xí)和采樣 Hessian 和梯度的情況下，結(jié)果只要求| SK |必須選擇足夠大的相對(duì)于該算法采取的步驟的長(zhǎng)度。例如，在 [ 3, 34 ]，| SK |大小與置信域半徑的關(guān)系。需要注意的是，對(duì)于采樣的海塞矩陣，其對(duì)樣本集的大小要求比采樣的梯度要高得多，因此支持使用精確梯度的海塞估計(jì)的思想催生了強(qiáng)大的算法，它擁有強(qiáng)大理論支撐和良好的實(shí)踐高效性。