CoCoA：大規模機器學習的分布式優化通用框架

去年，Michael I. Jordan 實驗室發表論文《CoCoA: A General Framework for Communication-Efficient Distributed Optimization》提出了一種用于機器學習的分布式優化的通用框架 CoCoA。機器之心技術顧問 Yanchen Wang 對該研究進行了深度解讀。

引言

在做深度學習時，現代數據集的規模必需高效的設計和開發，而且理論上算法也要進行分布式優化。分布式系統可以實現可擴展性——不管是垂直擴展還是水平擴展，提升計算和存儲能力；但同時也讓算法設計者面臨著一些獨特的難題。其中一個尤其關鍵的難題是在機器學習負載的背景下，開發能有效地協調機器之間的通信的方法。對大多數生產集群而言，網絡通信確實比單臺工作機器上的本地內存存取要慢得多；但是，擴展單臺機器顯然不可行。這個問題還可以更加復雜，本地計算和遠程通信之間的最優平衡取決于數據集的特定屬性（比如維度、數據點的數量、稀疏度、偏度等）、分布式系統的特定屬性（比如數據存儲格式、分布式方案和數據存取模式等邏輯方面的設計，以及網絡層次結構、帶寬、計算實例規范等物理方面的條件）和負載的特定屬性（比如簡單的 ETL 過程肯定不同于 logistic 回歸的迭代式擬合）。因此，算法設計者必須要讓他們的優化/機器學習算法具有足夠的靈活性，從而在保證快速收斂的前提下實現特定分布式系統的「計算-通信」的最優平衡。

CoCoA 是加州大學伯克利分校 Michael I. Jordan 的實驗室最近提出的一個框架，通過對多種多樣的優化問題的智能分解而實現了上述目標。通過自由選擇原始或對偶的目標來解決，該框架成功利用了凸對偶性（convex duality），從而可將全局問題分解成一攬子可在工作機器上有效并行求解的子問題，并且可以將局部更新組合起來以一種可證明的方式確保快速全局收斂。CoCoA 有兩個顯著優勢：1）在每臺工作機器上都可以最有效地運行任意本地求解器；2）計算-通信的權衡可以作為形式化問題的一部分進行調節，因此可以對每個不同的問題和數據集進行有效的調節。

根據數據在分布式集群上的分布情況（不管是根據特征還是根據數據點），CoCoA 可以將全局問題分解成近似的局部子問題，推薦應求解原始目標或是對偶目標。每個子問題都使用當前最佳的現成單臺機器求解器解決，然后在單一一步 REDUCE 步驟中將來自每次迭代的局部更新組合起來（REDUCE 這個術語借用自 MAP-REDUCE）。實驗表明 CoCoA 可以在 SVM、線性/logistic 回歸和 lasso 算法上實現最高 50 倍的加速。

在這篇報告中，我們將了解 CoCoA 的核心思想和最重要的結論，感興趣的讀者可以在參考文獻中找到詳細論證和更多實驗。本報告的目標是啟發我們分布式機器學習領域的讀者以及邀請更多人加入到我們的討論中，與我們交流知識以及為我們的技術社區做出貢獻。

問題設置

CoCoA 的目標是解決機器學習算法中普遍存在的下面一類優化問題：

其中 l 和 r 是向量變量 u 的凸函數。在機器學習領域，l 通常是一個單獨的函數，表示所有數據點的經驗損失（empirical loss）的總和 ；而 ，表示 p 范數的正則化項。SVM、線性/logistic 回歸、lasso 和稀疏 logistic 回歸都屬于這個類別。這個問題通常是在原始空間或對偶空間解決的。在我們的討論中，我們將這種原始/對偶問題抽象成了下面的 Fenchel-Rockafeller 對偶形式：

其中 α 和 w 是原始/對偶變量，A 是包含數據點列向量的數據矩陣，而 f* 和 g* 則是 f 和 g 的凸共軛。非負的對偶間隙（duality gap） ，其中 w(α)=?f(Aα)，為原始或對偶的次優性 （suboptimality）提供了一個可計算的上限，并且可以在強凸性下在最優解點減少到零。它可以用于驗證解的質量和用作是否收斂的標志。根據 l 的平滑度和 r 的強凸性，我們可以將目標 l(u)+r(u) 映射到 OA 或 OB：

每種情況的典型案例有：彈性網絡回歸是 Case I，lasso 是 Case II，SVM 是 Case III。這里省略了推倒過程。

CoCoA 框架

要在數據分布在 K 臺機器上時最小化目標 OA，我們需要將計算分配給 K 個局部子樣本并在每次全局迭代過程中將 K 個局部更新組合起來。首先將數據矩陣 A 的列分成 K 個數據分區 。對于每個工作機器 k，定義 ，其中當 i∈Pk 時， ，否則 。注意這種表示方式與數據的分布方式無關——數據矩陣 的維度 n 和 d 各自都可以表示特征的數量或數據點的數量。這種可互換性是 CoCoA 的一個顯著優勢——提供了靈活的數據分區方式，通過特征或數據點都可以，這取決于哪個更大以及使用了哪種算法。

分布 g(α) 很簡單，因為它是可分的  ；但要分布 f(Aα)，我們需要最小化它的二次近似。我們定義了以下僅讀取局部數據子樣本的局部二次子問題：

表示機器 k 上的一組列，類似于 是來自前一次迭代的共享向量， 表示局部變量αi 在所有 i∈Pk 上的變化，而且在 i?Pk 時為零。這個子問題是圍繞固定的 v 的臨近區域 f 的線性化，可以通過大多數有效的二次優化求解器解出。可以直觀地看到， 試圖隨局部 變化而非常近地近似全局目標 OA。如果每個局部子問題都可以得到最優解，那么 REDUCE K 個更新可以被解讀成一個獨立于數據的、與數據塊無關的近似 OA 的 f 部分的步驟。但是，和傳統的近似方法不同，CoCoA 并不需要完美的局部解。相反，它容許局部次優性（定義為與最優的期望絕對偏差），并且會將其整合進自己的收斂邊界中，下面就可以看到。有些實踐者想復用已有的針對特定問題、數據集和機器配置優化的單個求解器，對于他們而言，這是一個巨大的優勢。

完整算法如下：

其中有兩個可調節的超參數：γ 控制了工作機器的更新的組合方式，σ' 則表示數據分區的難度。實際上，對于一個給定的 γ∈(0,1]，我們設 σ':=γK。γ=1 且 σ'=K 能保證最快的收斂速度，盡管理論上任何 都應該是足夠的。詳細證明請參閱原論文。

CoCoA 的原始-對偶靈活性是一大主要優勢。盡管事實上我們一直都在求解 OA，但我們可以自由地把它看作是 的原始或對偶——如果我們將這個原始問題映射成了 OA，那么 OA 就是原始；如果我們將其映射成了 OB，那么 OA 就是對偶。將 OA 看作原始讓我們可以求解 lasso 這樣的非強凸性正則化項，通常這是當數據按特征分布，而不是按數據點分布的時候。這能很好地適用于 lasso、稀疏 logistic 回歸或其它類似 L1 的誘導稀疏性的先驗（sparsity-inducing priors）。求解 CoCoA 的這種原始變體每次全局迭代的通信成本為 O(數據點的數量)。另一方面，將 OA 看作對偶讓我們可以考慮非平滑損失，比如 SVM 的 hinge loss 或絕對偏差損失，而且當數據是按數據點而非特征分布時效果最好。這種變體每次全局迭代的通信成本為 O(特征數量)。下面是對這兩種 CoCoA 變體的總結：

復用上面的表格，我們現在得到：

下表給出了在 CoCoA 框架中構建的常見模型的例子：

在原始的設置（算法 2）中，局部子問題 變成了在局部數據塊上的二次問題，其中僅有局部的 是正則化的。在對偶的設置（算法 3）中，經驗損失僅應用于局部 ，這使用了由一個二次項近似的正則化項。

收斂分析

關于收斂的詳細論證過于技術，會把我們的討論弄得比較混亂，為了避免這種情況，我們這里僅給出了關鍵結果。感興趣的讀者可以查看原始論文詳細了解。

為了簡化我們的演示，這里給出了我們的三個主要假設：

1. 數據在 K 臺機器上均等分配；
2. 數據矩陣 A 的列滿足 ||xi||≤1;
3. 我們僅考慮 γ=1 且 σ'=K 的情況，這能保證收斂，而且在分布式環境中的收斂速度也最快。

我們的第一個收斂結果涉及到使用一般凸性的 gi 或 L-Lipschitz 的 （這兩個條件是等價的） ：

其中 L-bounded support 和  -smooth 的定義可以在原論文找到。這個定理涵蓋了帶有非強凸性正則化項（比如 lasso 和稀疏 logistic 回歸）的模型或帶有非平滑損失（比如 SVM 的 hinge loss）的模型。

我們還可以證明在強凸性的 gi 或平滑的 （這兩個條件也是等價的）上有更快的線性收斂速度，這涵蓋了彈性網絡回歸和 logistic 回歸：

類似地，μ-strong convexity 的定義也可以在原論文找到。

這兩個定理都參考了下列假設作為局部解 Θ 的質量的定義。

這個假設基本上將 Θ 定義成了局部二次問題的經驗絕對偏差之前的相乘的常數。實際情況下，并行地分配到局部計算的時間應該差不多等于池化所有 K 個工作機器的更新的全部通信時間成本。

將這些收斂定理與我們前面的類別關聯起來：

實驗

我們將 CoCoA 與幾種適用于 lasso、彈性網絡回歸和 SVM 的當前最佳的通用大規模分布式優化算法進行了比較：

1. MB-SGD：minibatch 隨機梯度下降。對于 lasso，我們在 L1-prox 上與 MB-SGD 進行了比較。我們在 Apache Spark MLlib v1.5.0 中進行了實現和優化。
2. GD：完全梯度下降。對于 lasso，我們使用了近似版本 PROX-GD。我們在 Apache Spark MLlib v1.5.0 中進行了實現和優化。
3. L-BFGS：有限內存擬牛頓法。對于 lasso，我們使用了 OWL-QN（orthant-wise limited quasi-Newton method）。我們在 Apache Spark MLlib v1.5.0 中進行了實現和優化。
4. ADMM：交替方向乘子法。對于 lasso，我們使用了共軛梯度；對于 SVM，我們使用了 SDCA（隨機對偶坐標上升）。
5. MB-CD：minibatch 并行化的坐標下降。對于 SVM，我們使用了 MB-SDCA。

為了避免麻煩，這些不談每種參與比較的方法的調參細節。感興趣的讀者可以參考原論文，以便重現論文的結果。對于 CoCoA，所有的實驗在單機上都使用了隨機坐標下降作為局部求解器。如果使用更加復雜的求解器，當然有可能進一步提升表現水平。這個開放性的實踐就留給感興趣的讀者探索吧。

我們比較的指標是離原始最優（primal optimality）的距離。為此我們為所有方法都運行了大量迭代次數，直到觀察不到明顯的進展為止，然后選擇其中最小的原始值。使用的數據集是：

所有代碼都是用 Apache Spark 編寫的，并且都運行在 Amazon EC2 m3.xlarge 實例上（每臺機器一個核）。代碼已發布到 GitHub： www.github.com/gingsmith/proxcocoa

在原始的設置中，我們應用 CoCoA 在上述每個數據集上擬合 lasso 模型，其中使用了隨機坐標下降作為局部求解器，而總迭代次數 H 調節了局部解的質量 Θ。我們也包括了多核 SHOTGUN 作為極端案例。對于 MB-CD、SHOTGUN 和原始 CoCoA，數據集是按特征分布的；而對于 MB-SGD、PROX-GD、OWL-QN 和 ADMM，數據集則是按數據點分布的。以秒為單位繪制原始次優性，我們得到：

很顯然，就算與比較中最好的方法 OWL-QN 相比，CoCoA 的收斂速度也快了 50 多倍，而且在有大量特征的數據集上表現最好，而這也正是 lasso 常常應用的領域。

在對偶的設置中，我們考慮的是擬合 SVM。CoCoA 使用隨機對偶坐標上升作為局部求解器。所有方法都按數據點分布數據。顯然，CoCoA 的表現又超出了其它方法一大截。

為了理解 CoCoA 的原始-對偶互換性，我們讓其兩種變體都擬合了彈性網絡回歸模型，并使用了坐標下降作為局部求解器。

當數據集有大量特征而非數據點時，原始 CoCoA 的表現更好，而且對強凸性的退化（deterioration）是穩健的。另一方面，當數據集有大量數據點而非特征時，對偶 CoCoA 的表現更好，在針對強凸性的損失的穩健性方面不夠好。這提醒實踐者在面臨不同的問題設置時，應該使用不同的 CoCoA 變體——算法 2 或算法 3.

原論文還報告了更多有趣的發現，比如原始 CoCoA 可以保留局部稀疏性，并會將其最終傳遞為全局稀疏性；調節控制 Θ 的 H 允許機器學習系統設計者一路探索「計算-通信」權衡曲線，以確定他們當前系統的最佳平衡所在。

總結

CoCoA 是一個通用分布式優化框架，可以在分布式集群中實現通信高效的原始-對偶優化。它的方式是利用對偶性將全局目標分解成局部二次近似子問題，而這些子問題可以使用架構師選擇的任意當前最佳的單機求解器并行地求解到任意準確度。CoCoA 的靈活性允許機器學習系統設計者和算法開發者輕松探索分布式系統的「計算-通信」權衡曲線，并為他們的特定硬件配置和計算負載選擇最優的平衡。在實驗中，CoCoA 將這種選擇總結歸納成了單個可調的超參數 H（迭代的總次數），它間接等效的 Θ（局部解的質量）進入了關于原始和對偶 CoCoA 的收斂速度的兩個重要理論證明。實證結果表明 CoCoA 的表現可以以最高 50 倍的差距超越當前最佳的分布式優化方法。

參考文獻

[1] CoCoA: A General Framework for Communication-Efficient Distributed Optimization, V. Smith, S. Forte, C. Ma, M. Takac, M. I. Jordan, M. Jaggi, https://arxiv.org/abs/1611.02189

[2] Distributed Optimization with Arbitrary Local Solvers, C. Ma, J. Konecny, M. Jaggi, V. Smith, M. I. Jordan, P. Richtarik, M. Takac, Optimization Methods and Software, 2017, http://www.tandfonline.com/doi/full/10.1080/10556788.2016.1278445

[3] Adding vs. Averaging in Distributed Primal-Dual Optimization, C. Ma*, V. Smith*, M. Jaggi, M. I. Jordan, P. Richtarik, M. Takac, International Conference on Machine Learning (ICML '15), http://proceedings.mlr.press/v37/mab15.pdf

[4] Communication-Efficient Distributed Dual Coordinate Ascent, M. Jaggi*, V. Smith*, M. Takac, J. Terhorst, S. Krishnan, T. Hofmann, M. I. Jordan, Neural Information Processing Systems (NIPS '14), https://people.eecs.berkeley.edu/~vsmith/docs/cocoa.pdf

[5] L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework, V. Smith, S. Forte, M. I. Jordan, M. Jaggi, ML Systems Workshop at International Conference on Machine Learning (ICML '16), http://arxiv.org/abs/1512.04011

 

來自：https://www.jiqizhixin.com/articles/2017-08-27-4