騰訊 AI Lab 詳解16篇 ICML 2018 入選論文

本文轉載自騰訊AI實驗室，微信號 tencent_ailab

7月10日至15日，第 35 屆國際機器學習會議（ICML 2018）將在瑞典斯德哥爾摩舉行。ICML是機器學習領域最頂級的學術會議，今年共收到2473篇投遞論文，比去年的1676篇提高47.6%，增幅顯著。最終入圍論文共621篇，接收率25%，與去年26%持平。

這是騰訊AI Lab第二次參與這一頂級會議，共有16篇論文入選，去年則入選4篇，均位居國內企業前列。我們將在下文中分三類介紹這些文章——新模型與新框架、分布式與去中心化、及機器學習優化方法與理論研究。有的研究具有多重貢獻，并不嚴格按照研究內容區分。

第一部分：新模型與新框架

1、用于強化學習的基于反饋的樹搜索

Feedback-based Tree Search for Reinforcement Learning

論文地址：https://arxiv.org/abs/1805.05935

蒙特卡洛樹搜索（MCTS）已經在游戲智能體方面取得了很大的成功（比如 AlphaGo），但對于 Atari 或 MOBA 等需要快速決策的視頻游戲，樹搜索的速度卻太慢了。針對這一問題，該論文提出了一種新型的基于模型的強化學習技術，可在原無限范圍的馬爾可夫決策過程的小型有限范圍版本批量上迭代式地應用 MCTS。在以離策略的方式完成強化學習訓練之后，智能體無需進一步的樹搜索就能實現快速實時的決策。

研究者將這一思想融合到了一個基于反饋的框架中，其中 MCTS 會使用其根節點處生成的觀察結果來更新自己的葉節點評估器。其反饋過程如下圖所示：（1）從一批采樣的狀態（三角形）開始運行一組樹搜索，（2）使用第 k 次迭代時的策略函數近似（PFA）πk 和價值函數近似（VFA）Vk 的葉估計被用于樹搜索過程，（3）使用樹搜索結果更新 πk+1 和 Vk+1。

研究者對該方法進行了理論分析，結果表明當樣本量足夠大且進行了足夠多的樹搜索時，估計得到的策略能夠接近最優表現。這也是對基于批 MCTS 的強化學習方法的首個理論分析。

研究者還使用深度神經網絡實現了這種基于反饋的樹搜索算法并在《王者榮耀》1v1 模式上進行了測試。為了進行對比，研究者訓練了 5 個操控英雄狄仁杰的智能體，結果他們提出的新方法顯著優于其它方法，下圖給出了他們的方法訓練的智能體相對于其它智能體隨時間的金幣比值變化。

其中，NR 是指沒有 rollout 但參數設置與該論文的新方法一樣的智能體，DPI 是使用了直接策略迭代的智能體，AVI 是使用了近似價值迭代的智能體，SL 是一個在大約 10 萬對人類游戲數據的狀態/動作對上通過監督學習訓練得到的智能體。

2、通過學習遷移實現遷移學習

Transfer Learning via Learning to Transfer

論文地址：

https://ai.tencent.com/ailab/media/publications//icml/148_Transfer_Learning_via_Learning_to_Transfer.pdf

遷移學習的三個核心研究問題是：何時遷移、如何遷移和遷移什么。為特定的遷移任務選擇合適的遷移算法往往需要高成本的計算或相關領域的專業知識。為了能更有效地找到適合當前任務的遷移算法，研究者根據人類執行遷移學習的方式，設計了一種可根據之前的遷移學習經歷提升新領域之間的遷移學習有效性的新框架：學習遷移（L2T：Learning to Transfer）。

L2T 分為兩個階段。在第一個階段，每個遷移學習經歷都會被編碼成三個組件：一對源域和目標域、它們之間被遷移的知識（被參數化為隱含特征向量）、遷移學習帶來的性能提升比。然后再從所有經歷中學習一個反射函數（reflection function），該函數能將領域對和它們之間被遷移的知識映射到性能提升比。研究者相信這個反射函數就具備決定遷移什么和如何遷移的遷移學習能力。在第二個階段，新出現的領域對之間所要遷移的內容則可以通過最大化所學習到的反射函數的值而得到優化。

為了證明這種遷移學習方法的優越性，研究者在 Caltech-256 和 Sketches 這兩個圖像數據集上對 L2T 框架進行了實驗評估。下圖給出了 L2T 及另外 9 種基準方法在 6 個源域和目標域對上的分類準確度。

可以看到，不管源域與目標域有較緊密的聯系（比如 (a) 中的“galaxy”、“saturn”和“sun”）還是沒有顯著關聯（比如 (c) 和 (f)），L2T 方法的表現都明顯優于其它所有基準方法。

3、通過強化學習實現端到端的主動目標跟蹤

End-to-end Active Object Tracking via Reinforcement Learning

論文地址：https://arxiv.org/abs/1705.10561

目標跟蹤的目標是根據視頻的初始幀中的目標標注定位該目標在連續視頻中的位置。對于移動機器人和無人機等視角會變動的平臺或目標會離開當前拍攝場景的情況，跟蹤目標時通常還需要對攝像頭的拍攝角度進行持續調整。該論文提出了一種使用強化學習的端到端的主動目標跟蹤方法，可直接根據畫面情況調整攝像頭角度。具體而言，研究者使用了一個 ConvNet-LSTM 網絡，其輸入為原始視頻幀，輸出為相機運動動作（前進、向左等）。

上圖展示了這個 ConvNet-LSTM 網絡的架構，其中的強化學習部分使用了一種當前最佳的強化學習算法 A3C。

因為在現實場景上訓練端到端的主動跟蹤器還無法實現，所以研究者在 ViZDoom 和 Unreal Engine 進行了模擬訓練。在這些虛擬環境中，智能體（跟蹤器）以第一人稱視角觀察狀態（視覺幀）并采取動作，然后環境會返回更新后的狀態（下一幀）。研究者還設計了一個新的獎勵函數以讓智能體更加緊跟目標。

實驗結果表明，這種端到端的主動跟蹤方法能取得優異的表現，并且還具有很好的泛化能力，能夠在目標運動路徑、目標外觀、背景不同以及出現干擾目標時依然穩健地執行主動跟蹤。另外，當目標偶爾脫離跟蹤時（比如目標突然移動），該方法還能恢復對目標的跟蹤。下表給出了不同跟蹤方法在 ViZDoom 環境的幾個不同場景上的表現比較，其中 AR 表示累積獎勵（類似于精確度），EL 表示 episode 長度（類似于成功跟蹤的持續幀數）。

最后，研究者還在 VOT 數據集上執行了一些定性評估，結果表明從虛擬場景學習到的跟蹤能力也有望遷移到真實世界場景中。

4、使用局部坐標編碼的對抗學習

Adversarial Learning with Local Coordinate Coding

論文地址：https://arxiv.org/abs/1806.04895

生成對抗網絡（GAN）是近來一個非常熱門的研究方向，也實現了一些成功應用。但 GAN 仍有一些局限性：很多研究都使用了簡單的先驗分布，GAN 在隱含分布的維度上的泛化能力是未知的。針對這些問題，研究者基于對圖像的流形假設提出了一種全新的生成模型，該模型使用了局部坐標編碼（LCC），可提升 GAN 在生成擬真圖像上的表現。

上圖展示了該論文提出的 LCC-GAN 方案。研究者首先使用了一個自動編碼器（AE）在隱含流形上學習了嵌入來獲取數據中的含義信息。然后，他們又使用 LCC 學習一組基數來在該隱含流形上構建局部坐標系統。之后，他們再通過使用一個與一組編碼相關的線性函數來近似生成器而將 LCC 引入了 GAN。基于這種近似，他們再通過利用在隱含流形上的局部信息而提出了一種基于 LCC 的采樣方法。LCC-GAN 的具體訓練過程如下：

其中 LCC 采樣方法分為兩個步驟：（1）給定一個局部坐標系，我們隨機選擇一個隱含點（可以是一個基（basis）），然后找到其 d-最近鄰點；（2）我們構建一個 M 維向量作為采樣的 LCC 編碼。其中，該向量的每個元素都對應于那個基的權重。

研究者用 PyTorch 實現了 LCC-GAN 并通過大量基于真實世界數據集的實驗對該方法進行了評估。結果表明 LCC-GAN 的表現優于其它多種 GAN 方法（Vanilla GAN、WGAN、Progressive GAN）。下圖展示了 LCC-GAN 和 Progressive GAN 基于 CelebA 數據集的人臉生成結果比較。

研究者還推導了 LCC-GAN 的泛化界限，并證明維度較小的輸入就足以實現優良的泛化表現。

5、一種可變度量超松弛混合臨近外梯度方法的算法框架

An Algorithmic Framework of Variable Metric Over-Relaxed Hybrid Proximal Extra-Gradient Method

論文地址：https://arxiv.org/abs/1805.06137

極大單調算子包含（maximal monotone operator inclusion）問題是非平滑凸優化和凸凹鞍點優化的 Karush-Kuhn-Tucker（KKT）廣義方程的一種擴展，其包含大量重要的優化問題并且在統計學、機器學習、信號與圖像處理等領域有廣泛的應用。在該論文中，研究者關注的算子包含問題是：

其中， X是一個有限維度的線性向量空間，T:X?X是一個極大單調算子。

針對這一問題，研究者提出了一種可變度量超松弛混合臨近外梯度方法（VMOR-HPE）的新型算法框架，能保證在解決該問題時的全局收斂。不同于已有的混合臨近外梯度（HPE）方法，該框架能根據一種全新的相對誤差準則來生成迭代序列，并且還在外梯度步驟中引入了一種超松弛的步長來提升其收斂速度。尤其值得一提的是，這個外梯度步長和超松弛步長都可以事先設定為固定常量，而不是從某個投影問題中獲取的值，這能減少很多計算量。

研究者還提供了該框架的迭代復雜度和局部線性收斂速率，從理論上證明一個較大的超松弛步長有助于加速 VMOR-HPE。并且，研究者在文中嚴格證明了VMOR-HPE算法框架包含大量一階原始算法和一階原始-對偶算法為特例。此外，研究者還將 VMOR-HPE 應用到了一類 具有線性等式約束的多塊可分復合凸優化問題的KKT 廣義方程上，得到了一種尺度化的外梯度校正步驟的臨近交替方向乘子法（PADMM-EBB），在該步驟中的尺度化矩陣是通過一種分塊式的 Barzilai-Borwein 線搜索技術生成的。該算法的迭代格式如下：

PADMM-EBB 算法

最后，研究者在合成和真實數據集上進行了實驗，將 PADMM-EBB 應用在了非負雙圖正則化低秩表征問題上，結果表明該方法是有效的。

研究表明，這種 VMOR-HPE 算法框架能為原始與原始-對偶算法提供新見解并可用作證明它們的收斂性、迭代復雜度和局部線性收斂速率的強大分析技術。

第二部分：分布式與去中心化

6、針對次模函數最小化的元素安全篩選算法

Safe Element Screening for Submodular Function Minimization

下載地址：https://arxiv.org/abs/1805.08527

次模函數可以看成是離散函數中的凸函數，其在眾多領域中有著重要應用，比如：機器學習、計算機視覺和信號處理。然而，在大規模實際應用中，次模函數最小化問題的求解依然是一個具有挑戰性的問題。在本文中，我們第一次嘗試將大規模稀疏學習中新興的篩選方法擴展到次模函數最小化中，以加快它的求解過程。通過仔細研究次模函數最小化問題和其對應凸問題之間的關系以及該凸問題最優解的估計，我們提出了一種新穎安全的元素篩選算法，能夠在優化過程中迅速檢測出一定包含在最優解中的元素（我們稱為活躍元素）以及一定不包含在最優解中的元素（不活躍元素）。通過刪除不活躍元素和固定活躍元素，問題規模得以顯著減小，從而我們能夠在不損失任何精度的情況下大大減少計算量。據我們所知，我們的方法是次模函數最優化領域乃至組合優化領域中的第一個篩選算法。因此，我們的方法為加速次模函數最小化算法提供了一種新思路。在合成數據集和實際數據集上的實驗結果均證實我們的算法能夠顯著加速次模函數最小化問題的求解。

研究者首先研究了 SFM 和對應的凸近端問題之間的關系，還研究了這些近端問題的準確原始最優估計。基于該研究，他們提出了一種全新的安全篩選方法：不活動和活動元素篩選（IAES）。該框架由兩個篩選規則構成：不活動元素篩選（IES）和活動元素篩選（AES）；這兩個規則在 IAES 框架中是交替執行的，如下算法 2 所示。

最終該框架可快速識別確保可在優化過程中被包含（活動元素）在 SFM 的最終最優解之內或被排除在外（不活動元素）的元素。然后，研究者可移除不活動元素并固定活動元素，從而大幅降低問題規模，進而在不降低準確度的前提下顯著降低計算成本。

該研究為加速 SFM 算法指出了一個新方向。研究者在合成和真實數據集上進行了實驗，結果表明他們所提出的方法確實能實現顯著加速。下表給出了在圖像分割任務上求解 SFM 的運行時間結果（單位：秒）。

可以看到，IAES 帶來的加速效果非常明顯，最高甚至可達 30.7 倍！

7、生成對抗網絡的復合函數梯度學習

Composite Functional Gradient Learning of Generative Adversarial Models

論文地址：https://arxiv.org/abs/1801.06309

生成對抗網絡（GAN）已經得到了非常廣泛的研究和使用，但由于不穩定問題，GAN 往往難以訓練。從數學上看，GAN 求解的是一種最小最大優化問題。而這篇論文則首先提出了一個不依賴于傳統的最小最大形式的生成對抗方法理論。該理論表明，使用一個強大的鑒別器可以學習到優良的生成器，并使得每一個函數梯度（functional gradient）步驟之后真實數據分布和生成數據分布之間的 KL 散度都能得到改善，直至收斂到零。

基于這一理論，研究者提出了一種穩定的新型生成對抗方法，即復合函數梯度學習（CFG）；如算法 1 所示。

在此基礎上，研究者又提出了漸進式 CFG（ICFG，見算法 2）以及更進一步的近似式 ICFG（xICFG，見算法 3）。其中 ICFG 是以漸進方式使用生成器的更新一點一點地逐步更新鑒別器，使得生成器可以不斷提供新的更有難度的樣本，從而防止鑒別器過擬合。而 xICFG 則能通過訓練一個固定大小的近似器（近似 ICFG 所獲得的生成器的行為）來對 ICFG 得到的生成器進行壓縮，從而提升效率。

研究者還發現，通常的使用 logistic 模型的 GAN 與使用一種極端設置的 xICFG 的特例高度相關，即：GAN 的生成器更新等效于粗略近似 T=1 的 ICFG 得到的生成器。這個視角是理解 GAN 的不穩定性的新角度，即：GAN 的不穩定性源自 T 過小以及粗略近似。

研究者進行了圖像生成的實驗，結果表明他們提出的新方法是有效的。下圖給出了各種方法生成的圖像的質量（inception 分數）隨訓練時間的變化情況。

可以看到，盡管 GAN1（使用了 logd 技巧的 GAN）在 LSUN 數據集上偶爾有更優的表現，但 xICFG 的表現總體更優且更穩定。

8、用于高斯圖模型中最優估計的圖非凸優化

Graphical Nonconvex Optimization for Optimal Estimation in Gaussian Graphical Model

論文地址：https://arxiv.org/abs/1706.01158

高斯圖模型已被廣泛用于表示一組變量之間的成對的條件依賴關系。graphical lasso 是估計高斯圖模型的最常用方法之一。但是，它還未達到理想的收斂速度。具體而言，一般認為 graphical lasso 的譜范數中的最優收斂率大約為

其中 n 是樣本規模，d 是節點數量，s 是實際的圖中的邊數。

在這篇論文中，研究者提出了用于高斯圖模型中的最優估計的圖非凸優化。然后又通過一系列自適應的凸程序來近似求解。研究者指出，盡管新提出的方法求解的是一系列凸程序，但研究表明在某些規律性條件下，這種新提出的用于估計稀疏集中度矩陣的估計器能實現 的理想收斂率，就好像非零位置事先已知一樣。算法 1 展示了這個近似求解過程。然后，通過使用估計的邊際方差來重新調整逆相關矩陣，可以得到該集中度矩陣的一個估計器，其譜范數收斂率大約最大值。

算法 1 可使用 glasso 等現有的 R 語言軟件包實現。

這種新提出的方法在計算上是可行的，并且能得到能實現理想收斂速度的估計器。使用凸程序通過序列近似引入的統計誤差可以使用稀疏模式的概念來進一步提升。

研究者分析了新提出的估計器的理論性質，還將這種新方法擴展到了半參數圖模型中，并通過數值研究表明新提出的估計器在估計高斯圖模型方面的表現優于其它常用方法。

9、用于大型多類分類問題的候選項與噪聲估計

Candidates v.s. Noises Estimation for Large Multi-Class Classification Problem

論文地址：https://arxiv.org/abs/1711.00658

圖像分類和語言建模等很多任務的類別數量往往很大，采樣是應對這類任務的常用方法，能夠幫助降低計算成本和提升訓練速度。這篇論文對這一思想進行了擴展，提出了一種使用一個類別子集（候選項類別，其余類別被稱為噪聲類別——會被采樣用于表示所有噪聲）的用于多類分類問題的方法：候選項與噪聲估計（CANE）。

研究者表明 CANE 總是能保持一致的表現并且很有計算效率。此外，當被觀察到的標簽有很高的概率屬于被選擇的候選項時，所得到的估計器會有很低的統計方差，接近最大似然估計器的統計方差。

研究者通過兩個具體算法展現了 CANE 方法的優越性。其一是用于 CANE 的一般隨機優化過程（算法 1）：

另外，研究者還使用了一種樹結構（葉表示類別）來促進對候選項選擇的快速波束搜索（算法 2）。這種波束搜索具有更低的復雜度，能快速得到預測結果，還能自然地輸出最靠前的多項預測。

研究者實驗了 CANE 方法在有大量類別的多類分類問題和神經語言建模任務中的應用。下圖展示了各種方法在不同分類數據集上的測試準確度隨 epoch 的變化情況。可以看到，有更大候選項集的 CANE 在準確度方面基本優于其它方法，有時甚至能超過 softmax 方法。而且 CANE 方法的收斂速度明顯勝過噪音對比估計（NCE）和 Blackout。

下圖則給出了神經語言建模實驗的結果。可以看到，CANE 方法的收斂速度比 NCE 和 Blackout 更快，同時還達到了與 softmax 方法同等的困惑度。

總體而言，實驗結果表明 CANE 的預測準確度優于 NCE 及其變體方法和多種之前最佳的樹分類器，同時其速度也顯著優于標準的 O(K) 方法。

10、使用演示的策略優化

Policy Optimization with Demonstrations

論文地址：

https://ai.tencent.com/ailab/media/publications//icml/152_Policy_Optimization_with_Demonstrations.pdf

對強化學習方法而言，探索仍然是一個突出的難題，尤其是在獎勵信號稀疏的環境中。目前針對這一問題的研究方向主要有兩個：1）通過鼓勵智能體訪問之前從未見過的狀態來重塑原來的獎勵函數；2）使用從某個專家策略采樣的演示軌跡來引導學習過程。從演示中學習的方法看起來有克服探索難題的希望，但這通常需要難以收集的質量很高的演示。

結合這兩種思路，研究者提出了一種有效地利用可用演示來引導探索的方法，即強制所學到的策略與當前演示之間的占有率匹配。這種方法背后的直觀思想是，當獎勵信號不可用時，智能體應該在早期學習階段模擬所演示的行為，從而實現探索。在獲得了足夠多的能力之后，智能體就可以自己探索新狀態了。這實際上是一種動態的固有獎勵機制，可被引入強化學習用于重塑原生的獎勵。

基于此，研究者開發了一種全新的使用演示的策略優化（POfD）方法，可從演示數據獲取知識來提升探索效果。研究表明 POfD 能隱式地塑造動態獎勵并助益策略提升。此外，它還可以與策略梯度方法結合起來得到當前最佳的結果。

研究者在一系列常見的基準稀疏獎勵任務上進行了實驗。結果發現，他們提出的方法的表現甚至可媲美用在理想密集獎勵環境中的策略梯度方法；而且即使演示很少且不完美，這種新方法依然表現優異。下面兩張圖給出了新提出的 POfD 方法與幾種強基準方法分別在具有離散動作空間和連續工作空間的稀疏環境中的學習曲線。

各種方法在具有連續動作空間的稀疏環境中的學習曲線

11、邊密度屏障：組合推理中的計算-統計權衡

The Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference

統計推理的一大最主要目標是確定變量之間的依賴結構，即推理底層圖模型的結構。這篇論文關注的是一個更加具體的推理問題：檢驗底層圖中是否有特定的組合結構。

盡管對這一問題的信息論極限的研究已有很多了，但能否通過有效的算法得到這樣的極限很大程度仍未被研究過。此外，檢驗問題（尤其是圖模型的組合結構）的構建方式對信息論極限的可達成性的影響方式也并不明朗。

為了理解這兩個問題，研究者在這篇論文中描述了圖模型中組合推理的這種基本極限；并基于一種 oracle 計算模型量化研究了達到這個信息論極限所需的最小計算復雜度。

研究證明，要在空圖上檢驗團（clique）、最近鄰圖、完美匹配等常見組合結構，或在小團上檢驗大團，信息論極限是無法通過一般的可實現算法達到的。

更重要的是，研究者定義了名為弱邊密度 μ 和強邊密度 μ' 的結構量。根據定義，邊集的弱邊密度表征了可從一個無效（null）變到另一個圖的關鍵邊的密集程度。這能反應這兩個圖的差異水平。強邊密度是另一個表征這兩個圖的差異水平的量，且總是不小于弱邊密度。下面給出了 μ 和 μ' 的定義：

這兩個結構量的一大突出性質是它們僅依賴于被測試的組合結構的拓撲性質。它們能幫助研究者理解組合推理問題的結構性質決定其計算復雜度的方式。研究表明，如果 μ 遠小于 μ'，則信息論下界和計算有效的下界之間會存在明顯差距。下面給出了 4 個案例的具體最優比率；可以看到，這些案例都存在統計與計算的權衡。

本研究也是首個確定和解釋無向圖模型中組合推理問題的統計和計算之間的基本權衡的研究。

第三部分：機器學習優化方法與理論研究

12、異步去中心化并行隨機梯度下降

Asynchronous Decentralized Parallel Stochastic Gradient Descent

論文地址：https://arxiv.org/abs/1710.06952

最常用的分布式機器學習系統要么是同步的，要么就是中心化異步的。AllReduce-SGD 這樣的同步算法在異構環境中表現很差，而使用參數服務器的異步算法則存在很多問題，其中包括工作器（worker）很多時參數服務器的通信問題以及當參數服務器的流量擁堵時收斂性下降的問題。

研究者在這篇論文中提出了一種異步去中心化并行隨機梯度下降（AD-PSGD），能在異構環境中表現穩健且通信效率高并能維持最佳的收斂速率。理論分析表明 AD-PSGD 能以和 SGD 一樣的最優速度收斂，并且能隨工作器的數量線性提速。下面是該算法的工作過程：

研究者使用 Torch 和 MPI 在多達 128 個 P100 GPU 的 IBM S822LC 集群上實現和評估了 AD-PSGD。實驗結果表明，AD-PSGD 的表現優于最佳的去中心化并行 SGD（D-PSGD）、異構并行 SGD（A-PSGD）和標準的數據并行 SGD（AllReduce-SGD）。AD-PSGD 在異構環境中的表現往往能超出其它方法多個數量級。

下圖給出了在 ImageNet 數據集上基于 ResNet-50 模型得到的訓練損失和每 epoch 訓練時間情況。可以看到，AD-PSGD 和 AllReduce-SGD 的收斂情況接近，都優于 D-PSGD。在使用 64 個工作器時，AD-PSGD 每 epoch 耗時 264 秒，而另外兩種方法每 epoch 耗時會超過 1000 秒。

下圖則展示了各種方法在 CIFAR10 上為 VGG（通信密集型）和 ResNet-20（計算密集型）模型帶來的加速情況。可以明顯看到 AD-PSGD 一直都有最優的表現。

AD-PSGD 是首個在超過 100 個 GPU 的規模上達到接近 AllReduce-SGD 的 epoch 收斂速度的異步算法。

13、D2：在去中心化數據上的去中心化訓練

D2: Decentralized Training over Decentralized Data

論文地址：https://arxiv.org/abs/1803.07068

以去中心化的方式訓練機器學習模型近來得到了很大的研究關注。在使用多個工作器訓練機器學習模型時（其中每一個都會從自己的數據源收集數據），從各個不同的工作器收集的數據也各不相同時這些數據是最有用的。但是，近期的很多去中心化并行隨機梯度下降（D-PSGD）研究都假設托管在不同工作器上的數據并沒有很大的差異——否則這些方法的收斂速度會非常慢。

研究者在這篇論文中提出了一種全新的去中心化并行隨機梯度下降算法 D2，該算法是為各工作器之間數據差異很大的情況（可以說是“去中心化”數據）設計的。

D2 基于標準的 D-PSGD 算法，但添加了一個降低方差的組件。在這種 D2 算法中，每個工作器都會存儲上一輪迭代的隨機梯度和局部模型，并將它們與當前的隨機梯度和局部模型線性地結合到一起。這能將收斂速度改善，其中 ζ2 是不同工作器上的數據差異，σ2 是每個工作器內的數據方差，n 是工作器的數量，T 是迭代次數。

研究者在圖像分類任務上對 D2 進行了評估，其中每個工作器都僅能讀取一個有限標簽集的數據。實驗結果表明 D2 的表現顯著優于 D-PSGD。下面給出了在無數據混洗（unshuffled）情況下（不同工作器之間的數據差異最大）的不同分布式訓練算法的收斂性比較。

可以看到，D-PSGD 算法的收斂速度比中心化方法慢，而 D2 也比 D-PSGD 快很多，并且損失非常接近中心化算法。

14、實現更高效的隨機去中心化學習：更快收斂和稀疏通信

Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication

論文地址：https://arxiv.org/abs/1805.09969

去中心化優化問題近來得到了越來越大的關注。大多數現有方法都是確定性的，具有很高的每次迭代成本，并且收斂速度與問題條件數呈二次關系。此外，為了確保收斂還必需密集的通信，即使數據集是稀疏的也是如此。

在這篇論文中，研究者將去中心化優化問題泛化成了一個單調算子根查找問題，并提出了一種名為去中心化隨機反向聚合（DSBA）的算法。

在 DSBA 的計算步驟，每個節點都會計算一個隨機近似的單調算子的預解式（resolvent），以降低對問題條件數的依賴程度。這樣的預解式接受脊回歸等問題中的閉式解。在 DSBA 的通信步驟，每個節點都接收連續迭代之間差異的非零分量，以重建其臨近節點的迭代。因為 ?2-relaxed AUC 最大化問題等效于凸凹函數的極小極大問題，其微分是一個單調算子，因此能無縫地適配 DSBA 的形式。

該算法具有以下優勢：（1）能以與問題條件數呈線性的速度以幾何方式收斂，（2）可以僅使用稀疏通信實現。此外，DSBA 還能處理 AUC 最大化等無法在去中心化設置中高效解決的學習問題。研究者在論文中也給出了對該算法的收斂性分析。

研究者在凸最小化和 AUC 最大化上進行了實驗，結果表明新提出的方法是有效的。下圖給出了 DSBA 與幾種之前最佳方法在 logistic 回歸上的結果比較

可以看到，DSBA 的表現是最優的，而且能以更低的計算成本更快地收斂。

15、誤差補償式量化 SGD 及其在大規模分布式優化中的應用

Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization

論文地址：https://arxiv.org/abs/1806.08054

這一輪機器學習熱潮的出現很大程度上得益于計算機處理能力的指數級發展以及出現了可用于訓練模型的海量數據。為了有效地完成海量數據的訓練，往往需要用到分布式優化方法，其中包括數據并行化的處理方法。但在這樣的分布式框架中，各個節點之間的通信速度往往會成為整體性能的關鍵制約因素。目前的常見解決方法是對節點之間的通信信息進行壓縮，但這會引入量化誤差。

為了解決這一問題，這篇論文提出通過使用累積的所有之前的量化誤差的誤差反饋方案來補償當前的局部梯度。研究者將該方法稱為“誤差補償式量化隨機梯度下降（ECQ-SGD）”。實驗結果表明這種方法能實現比很多基準方法更快更穩定的收斂。下面是該算法的工作過程：

在量化完成之后，總體通信成本會降至 32+dr 比特（r ? 32），遠少于原來的 32 位全精度梯度所需的 32d 比特；其中 d 是原向量的維度；其中 s 是非零量化級別的數量：s 越大，則量化越細粒度，通信成本也就越高。下圖給出了在 ILSVRC-12 數據集上訓練 ResNet-50 模型時，使用不同數量的 GPU 的吞吐量情況比較：

在使用 512 個 GPU 進行訓練時，ECQ-SGD 相對于普通 SGD 實現了 143.5% 的加速（每秒各 66.42k 與 27.28k 張圖像）。如果節點之間的帶寬更小，這樣的優勢還會更加顯著。

研究者還在該論文中提供了該方法的理論保證：分析了其收斂行為并證明了其相對于其它之前最佳方法的優勢。

16、使用聯網智能體的完全去中心化多智能體強化學習

Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

論文地址：https://arxiv.org/abs/1802.08757

在多智能體強化學習（MARL）問題中，多個智能體的聯合行動會影響它們所處的共同環境。在每個狀態，每個智能體都會執行一個動作，這些動作共同決定了環境的下一個狀態和每個智能體的獎勵。此外，這些智能體可能針對的是不同的任務，會有不同的獎勵函數；但每個智能體都只能觀察自己的獎勵。每個智能體都會基于局部觀察到的信息以及從網絡中的臨近智能體接受到的信息各自做出決策。在這種設置內，所有智能體的整體目標是通過與其臨近智能體交換信息而最大化在整個網絡上的全局平均回報。

針對這一問題的中心化方法存在可擴展性和穩健性等方面的問題，因此，研究者在這篇論文中基于一種用于 MARL 的全新策略梯度定理提出了兩種去中心化 actor-critic 算法；結合函數近似，可應用于狀態和智能體數量都非常大的大規模 MARL 問題。

基于動作-價值函數的聯網式 actor-critic 算法

基于狀態-價值 TD 誤差的聯網式 actor-critic 算法

具體來說，actor 步驟是由每個智能體單獨執行的，無需推斷其它智能體的策略。對于 critic 步驟，研究者提出了一種在整個網絡通過通信實現的共識更新（consensus update），即每個智能體都會與其網絡中的臨近智能體共享其價值函數的估計，從而得到一個共識估計。這個估計又會被用在后續的 actor 步驟中。通過這種方式，每個智能體的局部信息都能散布到整個網絡，從而最大化整個網絡層面的獎勵。

這種算法是完全漸進式的，可以以一種在線形式實現。研究者還提供了當價值函數位于線性函數類別內近似求取時的算法收斂性分析。

研究者使用線性和非線性函數近似執行了大量模擬實驗，對所提出的算法進行了驗證。下圖給出了當使用神經網絡進行函數近似時，在協同導航任務上的全局平均獎勵。其中 Central-1 和 Central-2 分別是算法 1 和算法 2 對應的中心化方法。

研究者表示該研究是首個使用函數近似的聯網智能體的完全去中心化 MARL 算法研究。