高效的隨機(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è)示例。然而，對(duì)于大規(guī)模的應(yīng)用程序來說，mini-batch training同步成本可能仍然太大。在實(shí)際應(yīng)用中，雖然可以采用mini-batch的方法來降低通信成本，但可能會(huì)降低收斂速度。

$\bullet$ 對(duì)于一般的凸目標(biāo)函數(shù)，SGD的收斂性為

$\bullet$ 對(duì)于小批量規(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ū):

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

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

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

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

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

2??算法

推理問題的通用形式：

其中 $\phi _{i} :\Omega →R$

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

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

2.1 有效的mini-batch training

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

給定一個(gè)隨機(jī)的mini-batch $I\subset \left\{ 1,....,n \right\}$ ，大小為b，我們可以將I上的目標(biāo)函數(shù)定義為

在 $\Omega =R^d$ 的簡單情況下，迷你批處理SGD采用以下隨機(jī)更新規(guī)則:在每個(gè)迭代t，我們選擇迷你批處理 $It\subset \left\{ 1,....,n \right\}$ ，大小b隨機(jī)取，令

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

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

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

它由兩個(gè)部分組成:第一部分最小化了對(duì)mini-batch It的目標(biāo)函數(shù)，旨在實(shí)現(xiàn)對(duì)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è)對(duì)于所有t:

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

換句話說，強(qiáng)凸性的對(duì)應(yīng)項(xiàng)，即變化量存在一個(gè)二次上界，就足以保證這個(gè)條件。事實(shí)上，可以證明 $\gamma t=O(1/b)$ 是充分的。

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

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

在假設(shè)1下，當(dāng)選擇更新參數(shù) $\gamma t=\gamma +λ(t-1)$ 時(shí)，對(duì)于所有的 $w*\in Ω$ ：

由于增加小批量尺寸時(shí)，方差隨著 O(1/b)的減小而減小，因此γ=O(1/ $\sqrt$ )的縮放是合適的。這將產(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的對(duì)偶形式，在每一個(gè)時(shí)間EMSO-CD隨機(jī)選取一個(gè)坐標(biāo)j∈[1,p]，其中p為坐標(biāo)的總數(shù)，然后求解一維問題：

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

算法如下：

3.2 分布式模型平均

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

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

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

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

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

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

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

CTR是一個(gè)包含顯示廣告的私人數(shù)據(jù)集，隨機(jī)采樣時(shí)間為三個(gè)月。目標(biāo)是預(yù)測(cè)一個(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è)樣本對(duì)。

評(píng)估五種算法，如表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è)對(duì)于凸問題復(fù)雜的批量求解。

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

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

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

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

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)值對(duì)比表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。

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

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

圖3顯示了使用12臺(tái)機(jī)器時(shí)同步成本對(duì)算法整體運(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)值。頂部:對(duì)于固定總數(shù)的例子設(shè)置為5x106。底部:對(duì)于固定運(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)勢(shì)，因?yàn)樗趍ini-batch大小增加時(shí)收斂得更快。

4.6 可伸縮性

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

這兩種算法都受益于節(jié)點(diǎn)數(shù)量的增加。但L-BFGS比EMSO-CD獲益更多。然而, 由于更快的對(duì)流速率，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。