高效的隨機(jī)優(yōu)化mini-batch訓(xùn)練

Mu Li, Tong Zhang, Yuqiang Chen, Alexander J. Smola, 2014.

本文提出了一種mini-batchSGD算法，該算法的收斂速度隨批量的增大而增大柒傻。

它解決了每個(gè)迭代中的保守子問題红符，以最大限度地利用小批處理预侯，同時(shí)通過保守約束控制方差萎馅。

結(jié)果表明糜芳，該算法具有最優(yōu)的收斂速度耍目，并提出了實(shí)用的分布式實(shí)現(xiàn)邪驮。

在大規(guī)模數(shù)據(jù)集的串行和分布式實(shí)驗(yàn)中毅访，驗(yàn)證了該方法的有效性喻粹。

1 ? 介紹

傳統(tǒng)的SGD每次迭代處理一個(gè)示例守呜，這種連續(xù)的特性使得SGD很難處理分布式推理弥喉。

一個(gè)常見的實(shí)際解決方案是使用mini-batch訓(xùn)練由境，它在每個(gè)迭代中聚合多個(gè)示例虏杰。然而纺阔，對于大規(guī)模的應(yīng)用程序來說州弟，mini-batch training同步成本可能仍然太大。在實(shí)際應(yīng)用中掏婶，雖然可以采用mini-batch的方法來降低通信成本雄妥，但可能會(huì)降低收斂速度老厌。

對于一般的凸目標(biāo)函數(shù)枝秤，SGD的收斂性為

對于小批量規(guī)模b的SGD淀弹，收斂性為

為了解決這個(gè)問題，提出了一個(gè)替代的mini-batch更新策略缭乘，該策略不會(huì)隨著mini-batch大小的增加而降低收斂速度。

具體地說邑时，在每次迭代中刁愿，我們都求解一個(gè)保守的風(fēng)險(xiǎn)最小化子問題铣口。它由兩部分組成：mini-batch的原始目標(biāo)函數(shù)和保守懲罰(conservative penalty)脑题。為了達(dá)到目標(biāo)叔遂，我們需要兩個(gè)要素：一個(gè)更復(fù)雜的更新策略已艰；第二蚕苇，一個(gè)解決保守子問題的有效方法嚼吞。

作者的方法不同于以往的工作舱禽，除了簡單的梯度計(jì)算外恩沽，還增加了一個(gè)保守的懲罰罗心，并以非平凡(nontrivial)的方式使用每個(gè)數(shù)據(jù)分區(qū):

提出了一種新的和通用的方式來執(zhí)行mini-batch更新超越簡單的參數(shù)平均协屡。

結(jié)果表明肤晓，該算法具有最優(yōu)的收斂速度,

提高了批量（batch size）b較大時(shí)的收斂速度。此外卷员，進(jìn)一步證明了對于一個(gè)λ-強(qiáng)凸目標(biāo)函數(shù)毕骡，它可以改進(jìn)為

提出了兩種策略來解決保守子問題未巫，并演示了如何在一個(gè)通信高效的分布式實(shí)現(xiàn)（distributed implementation）中擴(kuò)展它們叙凡。

在大型數(shù)據(jù)集上驗(yàn)證了該算法的有效性握爷。

2??算法

推理問題的通用形式：

其中

為凸損失函數(shù)，w為共享參數(shù)燥撞。

這種通用形式解決了大量的機(jī)器學(xué)習(xí)問題教硫。

2.1 有效的mini-batch training

在實(shí)踐中瞬矩，當(dāng)我們使用大型的迷你批處理大小時(shí)景用，在處理的示例數(shù)量方面伞插，收斂速度會(huì)顯著降低媚污。

給定一個(gè)隨機(jī)的mini-batch耗美，大小為b，我們可以將I上的目標(biāo)函數(shù)定義為

在的簡單情況下堰怨，迷你批處理SGD采用以下隨機(jī)更新規(guī)則:在每個(gè)迭代t，我們選擇迷你批處理揽涮，大小b隨機(jī)取弃鸦，令

只要有一個(gè)非平凡的形狀家破，我們就需要添加一個(gè)投影步驟汰聋，它會(huì)找到Wt在可行集中的最近鄰居烹困。

對于一般域髓梅，可以將更新（5）重寫為小批量的優(yōu)化問題：

在本文中枯饿，我們提出通過在迭代t處求解以下子問題來更新參數(shù):

它由兩個(gè)部分組成:第一部分最小化了對mini-batch It的目標(biāo)函數(shù)，旨在實(shí)現(xiàn)對mini-batch的充分利用蟋字。第二個(gè)組件是一個(gè)保守約束鹊奖，它限制參數(shù)的劇烈變化嫉入，以避免過度使用。

下圖給出該算法：

2.2? 理論分析

解決保守子問題(6)的優(yōu)點(diǎn)是當(dāng)mini-batch大小增加時(shí)，收斂速度不會(huì)顯著降低垫竞。

這反映在主要結(jié)果中欢瞪。

在說明定理之前遣鼓，需要引入凸函數(shù)f的Bregman散度的概念如下:?

定理需要以下假設(shè):

假設(shè)1 ? 假設(shè)對于所有t:

只要我們選擇t大于或等于的平滑度參數(shù)回懦，假設(shè)成立：

換句話說怯晕，強(qiáng)凸性的對應(yīng)項(xiàng)舟茶，即變化量存在一個(gè)二次上界堵第，就足以保證這個(gè)條件阀捅。事實(shí)上也搓，可以證明是充分的。

基本上幔摸，假設(shè)1限定了當(dāng)用子集上的一個(gè)和一個(gè)保守懲罰替換全部Bregman散度時(shí)我們可以預(yù)期的‘surprise’的數(shù)量摸柄。

定理1 ?考慮隨機(jī)更新規(guī)則(6)，假設(shè)對于所有i都λ-強(qiáng)凸既忆。

在假設(shè)1下驱负，當(dāng)選擇更新參數(shù)時(shí)嗦玖，對于所有的：

由于增加小批量尺寸時(shí)，方差隨著 O(1/b)的減小而減小跃脊，因此γ=O(1/)的縮放是合適的。這將產(chǎn)生以下總計(jì)regret bound：

這意味著如果小批量大小為b，在T步之后欣除，我們的收斂邊界為 。因此，增加小批量大小并不影響算法處理的訓(xùn)練實(shí)例數(shù)量的收斂性卓研。

3 實(shí)際考慮

兩種求解保守問題（6）的優(yōu)化近似方法及其分布式實(shí)現(xiàn)。

3.1 早期停止近似

3.1.1 EMSO-GD

EMSO-GD是SGD的直接擴(kuò)展。它通過梯度下降法求解(6)。標(biāo)準(zhǔn)停止標(biāo)準(zhǔn)可用于實(shí)現(xiàn)早期停止搪锣。在實(shí)踐中，使用最簡單的策略是最方便的:限制最大的迭代次數(shù)L弹澎。這種策略的一個(gè)主要好處是簡化了將在下一節(jié)中介紹的分布式實(shí)現(xiàn)的同步。

算法如下：

3.1.2 EMSO-CD

利用坐標(biāo)下降法求解mini-batch線性SVM的對偶形式，在每一個(gè)時(shí)間EMSO-CD隨機(jī)選取一個(gè)坐標(biāo)j∈[1,p]，其中p為坐標(biāo)的總數(shù)躺涝，然后求解一維問題：

與EMSO-GD類似苍蔬，使用最大迭代次數(shù)作為早期停止條件。

算法如下：

3.2 分布式模型平均

在分布式計(jì)算中，我們假設(shè)有d臺機(jī)器。通過網(wǎng)絡(luò)連接侮东。其中每臺機(jī)器獨(dú)立地解決保守的子問題，然后所有機(jī)器平均其結(jié)果煤伟。

算法如算法4所示。前面部分介紹的算法適用放案。

4 實(shí)驗(yàn)

4.1 數(shù)據(jù)集

使用三個(gè)不同尺度的二分類數(shù)據(jù)集友雳，如表1所示。

KDD04來自于2004年KDD杯的粒子物理任務(wù)，其目標(biāo)是對高能對撞機(jī)實(shí)驗(yàn)中產(chǎn)生的兩種粒子進(jìn)行分類神帅。

URL數(shù)據(jù)集的目的是檢測惡意的URLs萎坷。

CTR是一個(gè)包含顯示廣告的私人數(shù)據(jù)集，隨機(jī)采樣時(shí)間為三個(gè)月。目標(biāo)是預(yù)測一個(gè)廣告是否會(huì)被點(diǎn)擊插佛。

KDD04是一個(gè)密集的數(shù)據(jù)集，而其他兩個(gè)數(shù)據(jù)非常稀疏嫩海。最大的數(shù)據(jù)集CTR有超過1億個(gè)示例深滚，原始文本文件大小約為300 GB血柳。

4.2 設(shè)置

用邏輯回歸的方法來研究分類問題栖榨。通過令

目標(biāo)函數(shù)可以寫成(1)的形式。這里令(yi, xi)為第i個(gè)樣本對。

評估五種算法鞍陨，如表2所示寿烟。

L-BFGS 這是經(jīng)典內(nèi)存受限BFGS方法的一個(gè)并行版本，如[18]中所述。也就是說炉擅，根機(jī)器從每個(gè)客戶機(jī)獲得次梯度來聚合成一個(gè)全局次梯度莹汤。隨后更新參數(shù)并傳播其新值。按構(gòu)造方法是一個(gè)批量優(yōu)化解決方案。

LibLinear 這是由林志仁的網(wǎng)站獲得的單機(jī)實(shí)現(xiàn)。我們將它包括進(jìn)來，為現(xiàn)有的和著名的“解決方案”提供一個(gè)參考點(diǎn)逗旁。這是一個(gè)對于凸問題復(fù)雜的批量求解堤舒。

Mini-Batch SGD 這可以有效地為每臺機(jī)器上的小批量SGD計(jì)算次梯度国撵。這些次梯度然后聚合环础，以獲得一個(gè)完整的小批量超梯度。之后，我們使用(5)更新服務(wù)器并重新廣播參數(shù)勺三。我們使用O(1/)衰減學(xué)習(xí)率的小批量算法刻蚯。具體來說,我們設(shè)定

對于迭代t充甚，其中常數(shù)和a分別指定初始規(guī)模和衰減速度技矮。通過對收斂過程的分析樊零，進(jìn)行網(wǎng)格搜索塑悼，選擇最優(yōu)解斑鸦。我們搜索范圍

EMSO-GD 使用算法4中引入的參數(shù)平均方法，同時(shí)通過(10)對每個(gè)客戶機(jī)執(zhí)行參數(shù)更新。它不同于以前的方法，在處理一個(gè)小批處理時(shí)考慮到損失函數(shù)的高階信息下愈。

EMSO-CD 與EMSO-GD的關(guān)鍵區(qū)別在于，它使用坐標(biāo)下降來更新一個(gè)minibatch中的參數(shù)。除此之外，結(jié)構(gòu)基本上是相同的。對于兩個(gè)EMSO變量寸爆，我們設(shè)置λ=0魔种。內(nèi)部迭代的數(shù)量分別為5和2，并從{}搜索λ氓辣。

4.3 小批量和收斂性

第一個(gè)完整性檢查是確定關(guān)于單個(gè)節(jié)點(diǎn)hold上的微型批處理方法的收斂結(jié)果。為此蹬敲，將批量大小從103增加到105.處理107個(gè)實(shí)例后的目標(biāo)值如圖1所示闹究。

圖1:在單個(gè)節(jié)點(diǎn)中處理107個(gè)示例后的目標(biāo)值與小批量大小自娩。從上到下姊扔，數(shù)據(jù)集分別是KDD04、URL和CTR绵载，由于單個(gè)節(jié)點(diǎn)的容量有限著摔，CTR被向下采樣到400萬個(gè)示例。

EMSO-GD緩解了小批量SGD的目標(biāo)值會(huì)增加（也就是說處理的例子的收斂速度變慢）的問題。EMSO-CD求解保守子問題時(shí)优床，收斂性更穩(wěn)定仍翰。

總之喧笔，與單純的梯度計(jì)算相比，在mini-batch上求解保守優(yōu)化問題是有益的割按。

4.4 與其他算法的比較

根據(jù)目標(biāo)值對比表2中列出的算法和運(yùn)行時(shí)够吩，但只報(bào)告最佳批處理大小的結(jié)果鱼鼓。圖2顯示了結(jié)果于樟，可以看出关霸，這兩批處理算法的收斂性。

圖2：單個(gè)節(jié)點(diǎn)的目標(biāo)值與運(yùn)行時(shí)間相恃。數(shù)據(jù)集與圖1相同苍苞，從上到下依次是KDD04歉铝、URL和CTR邻吭。

對于mini-batch處理算法。EMSO-GD與SGD相當(dāng)翅楼。同時(shí)，即使使用更小的批處理大小胎挎，EMSO-CD也比其他兩種方法快10倍。

4.5 小批量生產(chǎn)和同步成本

圖3顯示了使用12臺機(jī)器時(shí)同步成本對算法整體運(yùn)行時(shí)間的貢獻(xiàn)。

圖3：當(dāng)在12個(gè)和12個(gè)節(jié)點(diǎn)之間通信時(shí)，同步成本的一部分作為小批量大小的函數(shù)页响。

由于EMSO-GD和EMSO-CD在每個(gè)mini-batch中都比SGD解決了更復(fù)雜的優(yōu)化問題盼玄，因此它們的同步成本也相應(yīng)地比SGD小暴心。它比梯度下降占用更多的CPU時(shí)間，即使后者處理最少的批處理5次买决，因此同步性進(jìn)一步降低成本。

各種小批量條件下的收斂結(jié)果如圖4所示。

圖4:使用12個(gè)節(jié)點(diǎn)改變迷你批處理大小時(shí)的目標(biāo)值。頂部:對于固定總數(shù)的例子設(shè)置為5x106。底部:對于固定運(yùn)行時(shí)間設(shè)置為1000秒筑凫。

EMSO-GD稍微改進(jìn)了SGD瓦盛，而EMSO-CD有彈性地增加了mini-batch處理的大小谒麦。盡管在單節(jié)點(diǎn)實(shí)驗(yàn)中SGD與EMSO-GD具有可比性臣咖，但由于分布式環(huán)境中的通信成本，后者的性能優(yōu)于前者波闹。

此外，EMSO-CD使用大批大小有明顯的優(yōu)勢庄撮，因?yàn)樗趍ini-batch大小增加時(shí)收斂得更快。

4.6 可伸縮性

圖5比較了以下兩種算法:EMSO-CD和LBFGS吞琐，評估不同節(jié)點(diǎn)數(shù)量的運(yùn)行時(shí)結(jié)果。

這兩種算法都受益于節(jié)點(diǎn)數(shù)量的增加趾牧。但L-BFGS比EMSO-CD獲益更多。然而, 由于更快的對流速率，EMSO-CD仍然比L-BFGS快10倍。

表3顯示了EMSO-CD達(dá)到特定目標(biāo)值的定量加速发笔。

當(dāng)節(jié)點(diǎn)數(shù)量從5個(gè)增加到10個(gè)時(shí)盟萨，兩個(gè)目標(biāo)值的平均加速倍數(shù)都是1.75倍，如果節(jié)點(diǎn)數(shù)量增加4倍了讨，則加速倍數(shù)增加到2.5倍捻激。

5 結(jié)論

作者提出了一種新的mini-batch算法，在每一步中以原始形式解決一個(gè)正則化優(yōu)化問題前计。結(jié)果表明胞谭，該方法在理論上也能達(dá)到最優(yōu)收斂速度，并給出了該方法的實(shí)際實(shí)現(xiàn)男杈。在各種情況下丈屹，所得到的方法的實(shí)際性能都優(yōu)于mini-batch SGD。