最近研究二次判別分析（Quadratic Discriminant Analysis，QDA），發現運用到了交替方向乘數法（ADMM），就很迷，（關鍵是太菜）

很多博主都是直接翻譯或者搬運的，搜羅且了解了很多相關知識，那就來個大總結及其一些自己的想法吧！

（內力有限，僅供學習交流）

確實很難，理論性很強，沒有虛的，閱讀完內容需要有“勇氣”！

ADMM

背景

咱們先來了解了解，ADMM到底是個什么東西？

交替方向乘數法（Alternating Direction Method of Multipliers），從字面意思上理解，交替方向？是不是很迷？交替計算？交替求解？，，，難道是對偶問題？對偶求解？

先不管了，再看后半句，乘數法？咦~是不是感覺有點熟悉，

la.la.la…Lagrange乘數法？？？

（沒錯，就是Lagrange，直接干起來，等等，這里只說對了一半，具體咱們下面慢慢道來~）

ADMM是一個不算是太新的演算法，其實就是一種求解優化問題的計算框架, 適用于求解分布式凸優化問題，特別是統計學習問題， ADMM 通過分解協調（Decomposition-Coordination）程序，將大的全域問題分解為多個較小、較容易求解的區域子問題，并通過協調子問題的解而得到大的全域問題的解，

簡單的理解就是，整個演算法只是整合許多不少經典優化思路，然后結合現代統計學習所遇到的問題，提出了一個比較一般的比較好實施的分布式計算框架，

而他的歷史可以追溯到看下面：

ADMM 最早分別由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976年提出，并被 Boyd 等人于 2011 年重新綜述并證明其適用于大規模分布式優化問題，由于 ADMM的提出早于大規模分布式計算系統和大規模優化問題的出現，所以在 2011 年以前，這種方法并不廣為人知，

作為搞自動化、控制、優化、診斷…的本菜來說，當然是奔著優化求解去學習的，

先來看看一個大佬對目前大資料及其優化的見解，簡直是一針見血，說出來我的心聲：

業界一直在談論大資料，對于統計而言，大資料其實意味著要不是樣本量增加 n → ∞ n\rightarrow \infty n→∞，要不就是維度的增加 p → ∞ p \rightarrow \infty p→∞，亦或者兩者同時增加，并且維度與樣本量的增長速度呈線性或者指數型增長，在稀疏性的假設條件下，再加上一些正則性方法，統計學家可以證明各種加penalty的模型所給出的引數估計具有良好的統計性質，收斂速度也有保證，同時還會給出一些比較好的迭代演算法，但是，他們并沒有考慮真實環境下的所消耗的計算時間，雖然統計學家也希望盡量尋求迭代數目比較少的演算法（比如one-step估計），但是面對真實的Gb級別以上的資料，很多時候我們還是無法直接用這些演算法，原因是一般的硬體都無法支撐直接對所有資料進行運算的要求，如果想減少抽樣誤差，不想抽樣，又想提高估計的精度，那么還是需要尋求其他思路，結合已有的模型思想來解決這些問題，在目前條件下，并行化、分布式計算是一種比較好的解決思路，利用多核和多機器的優勢，這些好演算法便可以大規模應用，處理大資料優勢便體現出來了，對于統計而言，資料量越大當然資訊越可能充分（假設冗余成分不是特別多），因為大樣本性質本身就希望樣本越多越好嘛，—源自此處

還需要知道的一點，我們都知道搞優化會遇到很多問題，無非是資料量上和維度的變化，關鍵詞大都為：降維，收斂，迭代等等，而這里的ADMM演算法不同于那些梯度下降法或其他改進的SGDM、RMSProp、Adam等等更多高級演算法，應用的大多為以GB級別的資料量的資料集，如果與SGDM、Adam這些演算法在同樣的低維資料（這里指的是較GB級別低的）進行比較，收斂速度絕壁沒它們好，很慢，實際的收斂速度往往比那些演算法慢得多，ADMM的主要應用，主要是在解空間規模非常大的情況下（比如X、Y 都是存盤空間上GB的超大規模矩陣），這個時候很多傳統的方法不好用，強制需要分塊求解，而且對解的絕對精度往往要求也沒那么高，所以我覺得這是，需要提前知道的一點，

確實，這個演算法很難理解，公式也很難，不敢保證，我能將其解釋清楚，抱著互相學習的態度寫這篇Blog！（望各位大佬批評指正）

具體結構，從ADMM需要用到的背景知識、ADMM原理、具體應用這幾塊進行解釋，

下面咱們從基本框架結構入手吧~

背景知識

《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》文章中提到了一些預備知識，學過最優化或最優估計等優化課程的童鞋應該能夠很快能夠理解，對偶問題若很陌生的小伙伴，可以補充補充相關的知識，

先來了解一些基本演算法思想吧~

對偶上升

對于凸函式的優化問題，對偶上升法核心思想就是引入一個對偶變數，然后利用交替優化的思路，使得兩者同時達到optimal，

讀到這里，讓我們想起咱們的主題，“交替方向”，是不是有點感覺了，
對于凸函式，我們只需要知道，凸優化問題有一個良好的性質即：區域最優解便是全域最優解
對凸函式有不解的地方，可看這位大佬的博客，

一個凸函式的對偶函式其實就是原凸函式的一個下界，因此可以證明一個較好的性質：在強對偶性假設下，即最小化原凸函式（primal）等價于最大化對偶函式（dual），兩者會同時達到optimal，這種轉化可以將原來很多的引數約束條件變得少了很多，以利于做優化，具體表述如下：
min ? f ( x ) s . t . A x = b \begin{array}{l} \min \quad f(x) \\s.t.\quad A x=b \end{array} minf(x)s.t.Ax=b?

其中的s.t.約束項，有些地方可能寫成“ A x + B z = C Ax+Bz=C Ax+Bz=C”的形式，原理都是一樣的，只是多了一個變數而已，不用過于擔心，理解到整個演算法的思路就好，(先不透露為什么會出現這個公式，哈哈哈哈)

對于對偶問題有所不解的，可以簡單理解成為原函式是Y關于X的函式，那么對偶的函式則為X關于Y的函式，這樣理解是不是更容易一點呢，

其中 f ( x ) f(x) f(x)為目標函式也即是凸函式，然后拉格朗日干起來，則為：
L ( x , y ) = f ( x ) + y T ( A x ? b ) L(x, y)=f(x)+y^{T}(A x-b) L(x,y)=f(x)+yT(Ax?b)
其中 y T y^{T} yT為拉格朗日乘子，對偶的 L ( x , y ) L(x,y) L(x,y)函式為：
g ( y ) = inf ? x L ( x , y ) = ? f ? ( ? A T y ) ? b T y g(y)=\inf _{x} L(x, y)=-f^{*}(-A^{T}y)-b^{T}y g(y)=xinf?L(x,y)=?f?(?ATy)?bTy
對于上式， inf ? \inf inf 代表的是一個下界，之所以用下確界而不是用min，可能是因為有些函式沒有極值（定義域取不到），但有一個下確界，

而 y y y 相對于原 L ( x , y ) L(x,y) L(x,y)函式來說，是拉格朗日乘子的對偶變數（這里表現為矩陣的轉置）

現在我們來看我們的原問題（Primal）的對偶(Dual）函式：
max ? y g ( y ) \max_y \quad g(y) ymax?g(y)
在強對偶的假設下，原問題和對偶問題的解都是一樣的，同時達到最優，

什么是強對偶性？就是指原問題的解與對偶問題的解是相同的，也即是： x ? = y ? x^{*}=y^{*} x?=y?

知道了原問題和對偶的解都是最優解，那么我們是不是可以從對偶問題入手，找到對偶問題的最優解 y ? y^{*} y?，這樣就能對應的求得原問題的解 x ? x^{*} x?,
x ? = arg ? min ? x L ( x , y ? ) x^{*}=\arg \min_{x} L(x, y^{*}) x?=argxmin?L(x,y?)

arg 是變元（即自變數argument）的英文縮寫，
arg min 就是使后面這個式子達到最小值時的變數的取值>
arg max 就是使后面這個式子達到最大值時的變數的取值

假如 g ( y ) g(y) g(y)可求其導數，那么利用梯度上升法，交替更新引數，使得同時收斂到最優，迭代如下：
x k + 1 : = arg ? min ? x L ( x , y k ) ( x ? 最 小 化 步 ) y k + 1 : = y k + α k ? g ( y ) = y k + α k ( A x k + 1 ? b ) ( 對 偶 變 量 更 新 , α k 是 步 長 ) x^{k+1}:=\arg \min _{x} L\left(x, y^{k}\right) \quad(x -最小化步 ) \\ y^{k+1}:=y^{k}+\alpha^{k} \nabla g(y)=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right) \quad (對偶變數更新, \alpha^{k} 是步長 ) xk+1:=argxmin?L(x,yk)(x?最小化步)yk+1:=yk+αk?g(y)=yk+αk(Axk+1?b)(對偶變量更新,αk是步長)

由于以上需要的 f ( x ) 、 α f(x)、\alpha f(x)、α條件都非常的苛刻，難以滿足其要求，一般應用中都不會用到對偶上升法，

對偶分解

雖然對偶上升的方法有所缺陷，導致我們在實際操作中會遇到重重困難，

但是世界萬物都是存在著兩面，有其弊也有其利，就如下面的太極雙魚圖

那么，我們可以利用其優秀的一面，當目標函式 f f f 是可分的（separable）時候（引數亦或feature可分），整個問題可以拆解成多個子引數問題，分塊優化后匯集起來整體更新，

這也就是快接近咱們的主題了，分布式凸優化問題，

我們可以分塊，然后并行化處理，

由此，我們可分離的目標函式為：
min ? f ( x ) = ∑ i = 1 N f i ( x i ) s . t . A x = ∑ i = 1 N A i x i = b \min \quad f(x)=\sum_{i=1}^{N} f_{i}\left(x_{i}\right) \\ s.t. \quad Ax=\sum_{i=1}^{N}A_ix_i=b minf(x)=i=1∑N?fi?(xi?)s.t.Ax=i=1∑N?Ai?xi?=b
其中，對 A A A矩陣按照列分開， x = ( x 1 , x 2 , . . . , x N ) ， A x=(x_1,x_2,...,x_N)，A x=(x1?,x2?,...,xN?)，A 可分解為 A = ( A 1 , A 2 , . . . , A N ) A=(A_1,A_2,...,A_N) A=(A1?,A2?,...,AN?)，

現在，拉格朗日干起來，得到了：
L ( x , y ) = ∑ i = 1 N L i ( x i , y ) = ∑ i = 1 N ( f i ( x i ) + y T A i x i ? ( 1 / N ) y T b ) L(x, y)=\sum_{i=1}^{N} L_{i}\left(x_{i}, y\right)=\sum_{i=1}^{N}\left(f_{i}\left(x_{i}\right)+y^{T} A_{i} x_{i}-(1 / N) y^{T} b\right) L(x,y)=i=1∑N?Li?(xi?,y)=i=1∑N?(fi?(xi?)+yTAi?xi??(1/N)yTb)
由此，可以得知，當程式迭代優化很多次的時候，其中 x x x最小化步長，可拆分為多個子問題來進行并行運算（注意這里的拆分并行和神經網路中批量化Batch_size不同，不會前后影響，如改變 W ^ \hat W W^后批量Normalization會改變 Z Z Z的值，在這里不會），同時也由于是強對偶關系，對偶變數更新不變這對于多特征任務時是很有用的，
x i k + 1 : = arg ? min ? x L i ( x i , y k ) ( 多 個 x i 并 行 最 小 化 步 ) y k + 1 : = y k + α k ? g ( y ) = y k + α k ( A x k + 1 ? b ) ( 匯 集 整 體 的 x , 然 后 對 偶 變 量 更 新 ) x_{i}^{k+1}:=\arg \min _{x} L_{i}\left(x_{i}, y^{k}\right) \quad\left(\right. 多個 x_{i} 并行最小化步) \\ y^{k+1}:=y^{k}+\alpha^{k} \nabla g(y)=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right) \quad( 匯集整體的 x , 然后對偶變數更新 ) xik+1?:=argxmin?Li?(xi?,yk)(多個xi?并行最小化步)yk+1:=yk+αk?g(y)=yk+αk(Axk+1?b)(匯集整體的x,然后對偶變量更新)

對偶分解是非常經典的優化方法，可追溯到1960年代，這種思想對后面的分布式優化方法影響較大，比如近期的graph-structure優化問題，（具體可自行查詢一下下）

增廣的拉格朗日乘數法

增廣的拉格朗日乘數法，說到這里，可就太熟悉了，無非就是加上各種懲罰項，L0、L1、L2正則化，lasso套索、嶺回歸等等，故，在我們上面的 L ( x , y ) L(x,y) L(x,y)拉格朗日項后面加上懲罰項，搞機器學習的都知道，增加懲罰項或正則化，目的是為了擴大我們的約束條件，讓一些噪聲或者不夠到約束的值能夠融入進去，SVM的軟間隔就是一個很好的例子，具體可自行了解，這里就不擴展開來了，

反正，記住一點即可：增加懲罰項，擴大約束條件的容納范圍，放松假設條件，

可使其收斂的更快，

那么，增加懲罰項的拉格朗日項為：
L ρ ( x , y ) = f ( x ) + y T ( A x ? b ) + ρ 2 ∥ A x ? b ∥ 2 2 L_{\rho}(x, y)=f(x)+y^{T}(A x-b)+\frac{\rho}{2}\|A x-b\|_{2}^{2} Lρ?(x,y)=f(x)+yT(Ax?b)+2ρ?∥Ax?b∥22?
其中，最后加了的L2正則化，二范數，也就是嶺回歸優化項就是懲罰項， ρ \rho ρ 則為我們的松弛因子（懲罰系數），用于更加精細的調節擴大的范圍邊界，

我們可以將其等價為優化的目標函式形式：
min ? f ( x ) + ρ 2 ∥ A x ? b ∥ 2 2 s.t. A x = b \begin{array}{lc} \min & f(x)+\frac{\rho}{2}\|A x-b\|_{2}^{2} \\ \text { s.t. } & A x=b \end{array} min s.t. ?f(x)+2ρ?∥Ax?b∥22?Ax=b?
我們增加的懲罰函式的好處是為了讓對偶函式
g ρ ( y ) = inf ? x L ρ ( x , y ) g_{\rho}(y)=\inf _{x} L_{\rho}(x, y) gρ?(y)=xinf?Lρ?(x,y)
更具有可導性，更新引數的計算程序和對偶上升的一致，除最小化 x x x的時候加上懲罰項：
x k + 1 = arg ? min ? x L ρ ( x , y k ) y k + 1 = y k + ρ ( A x k + 1 ? b ) \begin{aligned} x^{k+1} &=\arg \min _{x} L_{\rho}\left(x, y^{k}\right) \\ y^{k+1} &=y^{k}+\rho\left(A x^{k+1}-b\right) \end{aligned} xk+1yk+1?=argxmin?Lρ?(x,yk)=yk+ρ(Axk+1?b)?
由于我們更新的 x 、 y x、y x、y引數中都包含有懲罰項，其中 y y y的更新引數中， α \alpha α步長則變為了懲罰項中的松弛因子 ρ \rho ρ，由此原函式 f ( x ) f(x) f(x)則不需要滿足嚴格凸函式的限制了，在此條件下其對偶函式和原函式也能同時達到最優求解，

解除嚴格凸函式的限制的任務已經完成了，但是同時又存在另外一個問題，當增加懲罰項后，其平方項寫成矩陣形式無法是用之前那種分塊形式的，因此，在更新 x x x最小化時，無法做到并行優化多個 x i x_i xi?引數，關于新的問題的解決辦法，ADMM則殺出重圍了！！！

ADMM演算法原理

在上述的層層遞進的方法中，你是否也發現了其中的奧秘，對偶上升法解決了可分解性問題，增廣乘子法解決了嚴格的凸函式限制條件，增強了收斂性，那么是否，我們可以將二者集合在一起，取其各自的優點呢？

答案當然是肯定的，那就是ADMM演算法，同時解決了將原函式進行分解和擴展函式的約束范圍問題，使得 f ( x ) f(x) f(x)能夠適應于更多的更廣泛的約束條件求解問題，

結合兩者的優點，就有了下式目標函式：
min ? f ( x ) + g ( z ) s . t . A x + B z = c \begin{array}{lc} \min & f(x)+g(z) \\ s . t . & A x+B z=c \end{array} mins.t.?f(x)+g(z)Ax+Bz=c?
從中，我們可以看出，優化后的目標函式增加了新的變數 g ( z ) g(z) g(z)，約束條件則增加了 B z Bz Bz，可以看出，我們將原 X X X分解了，原始變數和目標函式都拆分開了，對于原論文中的解釋，感覺有一些蹊蹺，但簡單的理解就是將最初的原始變數就拆分為 x x x和 z z z兩個變數，這樣在后面的優化求解中，就不需要在融合到一起，最后求解出來也是兩個值，也即是從一開始就將其分解開來，保證了前面優化程序的可分解性，

緊接著，我們的增廣拉格朗日項：
L ρ ( x , z , y ) = f ( x ) + g ( z ) + y T ( A x + B z ? c ) + ( ρ / 2 ) ∥ A x + B z ? c ∥ 2 2 L_{\rho}(x, z, y)=f(x)+g(z)+y^{T}(A x+B z-c)+(\rho / 2)\|A x+B z-c\|_{2}^{2} Lρ?(x,z,y)=f(x)+g(z)+yT(Ax+Bz?c)+(ρ/2)∥Ax+Bz?c∥22?
和上面的增廣拉格朗日一樣，只不過增加了新的變數 z z z而已，

于是ADMM的優化就變成了如下序貫型迭代（這正是被稱作alternating direction交替方向的緣由）：
x k + 1 = arg ? min ? x L ρ ( x , z k , y k ) z k + 1 = arg ? min ? z L ρ ( x k + 1 , z , y k ) y k + 1 = y k + ρ ( A x k + 1 + B z k + 1 ? c ) \begin{aligned} x^{k+1} &=\arg \min _{x} L_{\rho}\left(x, z^{k}, y^{k}\right) \\ z^{k+1} &=\arg \min _{z} L_{\rho}\left(x^{k+1}, z, y^{k}\right) \\ y^{k+1} &=y^{k}+\rho\left(A x^{k+1}+B z^{k+1}-c\right) \end{aligned} xk+1zk+1yk+1?=argxmin?Lρ?(x,zk,yk)=argzmin?Lρ?(xk+1,z,yk)=yk+ρ(Axk+1+Bzk+1?c)?

可以看出，每次迭代分為三步：

1. 求解與 x x x 相關的最小化問題，更新變數 x x x
2. 求解與 z z z 相關的最小化問題，更新變數 z z z
3. 更新對偶變數 u u u

ADMM名稱中的“乘子法”是指這是一種使用增廣拉格朗日函式（帶有二次懲罰項）的對偶上升（Dual Ascent）方法，而“交替方向”是指變數 x 和 z 是交替更新的，兩變數的交替更新是在 f ( x ) f(x) f(x)或 g ( z ) g(z) g(z)可分時可以將優化問題分解的關鍵原因，

到此，通過以上的內容來理解“交替方向乘數法（ADMM）”是不是就豁然開朗了許多，開篇說很難，其實是不是并沒有那么的難，

其實，還有一個更為簡潔的縮放形式（Scaled form），令 u = ( 1 / ρ ) y u = (1/\rho)y u=(1/ρ)y，也就是對對偶變數做了縮放處理，對 A x + B z = c Ax+Bz=c Ax+Bz=c進行配方，得
x k + 1 = arg ? min ? x L ρ ( x , z k , y k ) = arg ? min ? ( f ( x ) + ( ρ / 2 ) ∥ A x + B z k ? c + u k ∥ 2 2 ) z k + 1 = arg ? min ? z L ρ ( x k + 1 , z , y k ) = arg ? min ? ( g ( z ) + ( ρ / 2 ) ∥ A x k + 1 + B z ? c + u k ∥ ) u k + 1 = u k + A x k + 1 + B z k + 1 ? c \begin{array}{l} x^{k+1}=\arg \min _{x} L_{\rho}\left(x, z^{k}, y^{k}\right)=\arg \min \left(f(x)+(\rho / 2)\left\|A x+B z^{k}-c+u^{k}\right\|_{2}^{2}\right) \\ z^{k+1}=\arg \min _{z} L_{\rho}\left(x^{k+1}, z, y^{k}\right)=\arg \min \left(g(z)+(\rho / 2)\left\|A x^{k+1}+B z-c+u^{k}\right\|\right) \\ u^{k+1}=u^{k}+A x^{k+1}+B z^{k+1}-c \end{array} xk+1=argminx?Lρ?(x,zk,yk)=argmin(f(x)+(ρ/2)∥∥?Ax+Bzk?c+uk∥∥?22?)zk+1=argminz?Lρ?(xk+1,z,yk)=argmin(g(z)+(ρ/2)∥∥?Axk+1+Bz?c+uk∥∥?)uk+1=uk+Axk+1+Bzk+1?c?

當然，寫成這種形式有利于后面簡化優化問題，也可不作任何的處理，

具體應用

大佬回答及點評

ADMM( Alternating Direction Method of Multipliers)演算法是機器學習中比較廣泛使用的約束問題最優化方法，它是ALM演算法的一種延伸，只不過將無約束優化的部分用塊坐標下降法（block coordinate descent，或叫做 alternating minimization）來分別優化，產生這種方法主要是為了彌補二次懲罰的缺點，
在一些問題當中，用二次懲罰來近似約束問題在最優點附近需要懲罰項的系數趨近于無窮，而這種要求會使得海森矩陣很大，因此近似的目標函式很不穩定，為了解決這個問題，引入了線性逼近的部分，通過線性項系數不斷的接近最優解（對偶上升），使得在二次懲罰項的系數很小的情況下，也能得到滿足要求精度的解，ADMM目前是比較成熟，比較受歡迎的約束問題最優化通用框架，（參考源自知乎大佬）

在這里，關于知乎大佬的回答，我說兩句，從上面的對偶上升，我們發現了可以解決分解性問題，通過交替更新 x 、 y x、y x、y引數，但實際的 f ( x ) f(x) f(x)是很難滿足，故將加入新變數 g ( z ) g(z) g(z)來提前分解原始變數，這樣就解決了第一個問題；同時又引入了增廣的拉格朗日乘數法，也即增加懲罰項，來改進擴大其求解范圍，使得 f ( x ) f(x) f(x)的約束更小，適應性更好，

受約束的凸優化問題

一般的受約束的凸優化問題可以寫成如下形式：
min ? f ( x ) s.t x ∈ C \begin{array}{ll} \min & f(x) \\ \text { s.t } & x \in \mathcal{C} \end{array} min s.t ?f(x)x∈C?
可將此型別寫成ADMM形式，增加新變數，以分解原始變數：
min ? f ( x ) + g ( z ) s.t x ? z = 0 \begin{array}{l} \min \quad f(x)+g(z) \\ \text { s.t } \quad x-z=0 \end{array} minf(x)+g(z) s.t x?z=0?
相應的增廣拉格朗日項為：
L ρ ( x , z , u ) = f ( x ) + g ( z ) + ( ρ / 2 ) ∥ x ? z + u ∥ 2 2 L_{\rho}(x, z, u)=f(x)+g(z)+(\rho / 2)\|x-z+u\|_{2}^{2} Lρ?(x,z,u)=f(x)+g(z)+(ρ/2)∥x?z+u∥22?
其中的 g g g 函式即 C C C 的示性函式，上述是scaled形式，那么具體演算法就是:
x k + 1 = arg ? min ? ( f ( x ) + ( ρ / 2 ) ∥ x ? z k + u k ∥ 2 2 ) z k + 1 = Π C ( x k + 1 + u k ) u k + 1 = u k + x k + 1 ? z k + 1 \begin{aligned} x^{k+1} &=\arg \min \left(f(x)+(\rho / 2)\left\|x-z^{k}+u^{k}\right\|_{2}^{2}\right) \\ z^{k+1} &=\Pi_{\mathcal{C}}\left(x^{k+1}+u^{k}\right) \\ u^{k+1} &=u^{k}+x^{k+1}-z^{k+1} \end{aligned} xk+1zk+1uk+1?=argmin(f(x)+(ρ/2)∥∥?x?zk+uk∥∥?22?)=ΠC?(xk+1+uk)=uk+xk+1?zk+1?

示性函式，顧名思義，是表示自變數性態的一個函式，

統計學習中的應用

統計學習問題也是模型擬合問題（我們知道有擬合和過擬合），可表示為：
min ? l ( D , d , z ) + r ( z ) \min l(D,d,z)+r(z) minl(D,d,z)+r(z)

• 其中， z ∈ R n z\in R^{n} z∈Rn代表待學習的引數
• D ∈ R m × m D\in R^{m\times m} D∈Rm×m是模型的輸入資料集
• d ∈ R m d\in R^{m} d∈Rm是模型的輸出資料集
• l : R m × n × R m × R n l:R^{m\times n}\times R^{m} \times R^{n} l:Rm×n×Rm×Rn是損失函式
• r : R n → R r:R^{n}\rightarrow R r:Rn→R是正則化項
• m m m代表的是資料的個數， n n n表示的是特征的個數

1. 對于帶L1正則化項的線性回歸（Lasso），其平方損失函式為
   l ( D , d , z ) = ( 1 / 2 ) ∥ D z ? d ∥ 2 2 l(D, d, z)=(1 / 2)\|D z-d\|_{2}^{2} l(D,d,z)=(1/2)∥Dz?d∥22?
2. 對于邏輯回歸（Logistic Regression），其極大似然損失函式為
   l ( D , d , z ) = 1 T ( log ? ( exp ? ( D z ) + 1 ) ? D z d T ) l(D, d, z)=\mathbf{1}^{T}\left(\log (\exp (D z)+\mathbf{1})-D z d^{T}\right) l(D,d,z)=1T(log(exp(Dz)+1)?DzdT)
3. 對于線性支持向量機（Linear Support Vector Machine），其合頁（Hinge）損失函式為
   l ( D , d , z ) = 1 T ( 1 ? D z d T ) + l(D, d, z)=\mathbf{1}^{T}\left(\mathbf{1}-D z d^{T}\right)_{+} l(D,d,z)=1T(1?DzdT)+?

將訓練資料在其原始樣本M維度下將其劃分為N塊：
D = ( D 1 ? D N ) , d = ( d 1 ? d N ) D=\left(\begin{array}{c} D_{1} \\ \vdots \\ D_{N} \end{array}\right), d=\left(\begin{array}{c} d_{1} \\ \vdots \\ d_{N} \end{array}\right) D=????D1??DN??????,d=????d1??dN??????

由此我們可得到分塊的目標函式來實作分布式計算：
min ? ∑ i = 1 N l i ( D i , d i , x i ) + r ( z ) s . t . x i ? z = 0 ( i = 1 , 2 , . . . , N ) \min \quad \sum_{i=1}^{N} l_i(D_i,d_i,x_i)+r(z) \\ s.t. \quad x_i-z=0 \quad (i=1,2,...,N) mini=1∑N?li?(Di?,di?,xi?)+r(z)s.t.xi??z=0(i=1,2,...,N)

相應的簡潔迭代更新 D 、 d 、 x D、d、x D、d、x的計算方式為：
x i k + 1 : = arg ? min ? x i ( l i ( D i , d i , x i ) + ( ρ / 2 ) ∥ x i ? z k + u i k ∥ 2 2 ) z k + 1 : = arg ? min ? z ( r ( z ) + ( N ρ / 2 ) ∥ z ? x ˉ k + 1 ? u ˉ k ∥ 2 2 ) u i k + 1 : = u i k + x i k + 1 ? z k + 1 \begin{array}{l} x_{i}^{k+1}:=\arg \min _{x_{i}}\left(l_{i}\left(D_{i}, d_{i}, x_{i}\right)+(\rho / 2)\left\|x_{i}-z^{k}+u_{i}^{k}\right\|_{2}^{2}\right) \\ z^{k+1}:=\arg \min _{z}\left(r(z)+(N \rho / 2)\left\|z-\bar{x}^{k+1}-\bar{u}^{k}\right\|_{2}^{2}\right) \\ u_{i}^{k+1}:=u_{i}^{k}+x_{i}^{k+1}-z^{k+1} \end{array} xik+1?:=argminxi??(li?(Di?,di?,xi?)+(ρ/2)∥∥?xi??zk+uik?∥∥?22?)zk+1:=argminz?(r(z)+(Nρ/2)∥∥?z?xˉk+1?uˉk∥∥?22?)uik+1?:=uik?+xik+1??zk+1?

（完結撒花?）

個人見解

最后說兩句，雖然優化演算法千千萬，在不同時期，隨著科技的發展與進步，老的演算法暫時過時，新的演算法逐步崛起，但終歸要落實到實際應用當中才是真正的好演算法，并不是說一味的提高求解速度，提高精度，有些時候成本會很高，有些時候老的演算法會被拾起成為yyds，新的演算法未必就好，終究說來，希望能夠有更多更實際應用范圍更加廣泛的優化演算法逐步崛起吧~

Reference

• http://maths.nju.edu.cn/~hebma/slides/20C.pdf
• https://www.zhihu.com/question/36566112/answer/79535746
• http://shijun.wang/2016/01/19/admm-for-distributed-statistical-learning/
• http://www-scf.usc.edu/~yuhao/journal/SimpleParallel-SIOPT-2017.pdf
• Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends? in Machine Learning, 2011, 3(1): 1-122.
• Eckstein J, Yao W. Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives[J]. Pac. J. Optim., 2014.
• Lusk E, Huss S, Saphir B, et al. MPI: A Message-Passing Interface Standard Version 3.1[J], 2015.
• Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.

?堅持讀Paper，堅持做筆記，堅持學習?！！！
?To Be No.1

??哈哈哈哈

學習DeepLearning堅持！30天計劃！！！

打卡 第 5 /30 Day!!!

---

?創作不易?，過路能?關注、收藏、點個贊?三連就最好不過了

?( ′･?･` )

?

『
When you think your life sucks, just think to yourself about how many people have it worse.
』