在整理舊電腦時，才發(fā)現(xiàn)13年下半年電腦里有不少殘文。老師說，東西擱下了再拿起來花費(fèi)的時間和之前可能差不多。我一眼看過去這篇關(guān)于分布式計(jì)算的文章，貌似還真的沒有了當(dāng)時理解的深度和感覺。當(dāng)時還想利用ADMM算法，把統(tǒng)計(jì)中常見的帶懲罰的高維問題在此框架下用R重寫一下，但是中途多種事情一耽擱，就早已拋之腦后。看來任何事情，真的還是需要堅(jiān)持，哪怕?lián)茳c(diǎn)時間都是好的。先把一篇?dú)埼娜映鰜砑赖煜逻^去的13年吧。公式多文字長，慎入！

業(yè)界一直在談?wù)摯髷?shù)據(jù)，對于統(tǒng)計(jì)而言，大數(shù)據(jù)其實(shí)意味著要不是樣本量增加n→∞，要不就是維度的增加p→∞，亦或者兩者同時增加，并且維度與樣本量的增長速度呈線性或者指數(shù)型增長。在稀疏性的假設(shè)條件下，再加上一些正則性方法，統(tǒng)計(jì)學(xué)家可以證明各種加penalty的模型所給出的參數(shù)估計(jì)具有良好的統(tǒng)計(jì)性質(zhì)，收斂速度也有保證，同時還會給出一些比較好的迭代算法，但是，他們并沒有考慮真實(shí)環(huán)境下的所消耗的計(jì)算時間。雖然統(tǒng)計(jì)學(xué)家也希望盡量尋求迭代數(shù)目比較少的算法（比如one-step估計(jì)），但是面對真實(shí)的Gb級別以上的數(shù)據(jù)，很多時候我們還是無法直接用這些算法，原因是一般的硬件都無法支撐直接對所有數(shù)據(jù)進(jìn)行運(yùn)算的要求。如果想減少抽樣誤差，不想抽樣，又想提高估計(jì)的精度，那么還是需要尋求其他思路，結(jié)合已有的模型思想來解決這些問題。在目前條件下，并行化、分布式計(jì)算是一種比較好的解決思路，利用多核和多機(jī)器的優(yōu)勢，這些好算法便可以大規(guī)模應(yīng)用，處理大數(shù)據(jù)優(yōu)勢便體現(xiàn)出來了。對于統(tǒng)計(jì)而言，數(shù)據(jù)量越大當(dāng)然信息越可能充分（假設(shè)冗余成分不是特別多），因?yàn)榇髽颖拘再|(zhì)本身就希望樣本越多越好嘛。

本文是基于Stephen Boyd 2011年的文章《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》進(jìn)行的翻譯和總結(jié)。Boyd也給出了利用matlab的CVX包實(shí)現(xiàn)的多種優(yōu)化問題的matlab示例。

1. 優(yōu)化的一些基本算法思想

ADMM算法并不是一個很新的算法，他只是整合許多不少經(jīng)典優(yōu)化思路，然后結(jié)合現(xiàn)代統(tǒng)計(jì)學(xué)習(xí)所遇到的問題，提出了一個比較一般的比較好實(shí)施的分布式計(jì)算框架。因此必須先要了解一些基本算法思想。

1.1 Dual Ascent

對于凸函數(shù)的優(yōu)化問題，對偶上升法核心思想就是引入一個對偶變量，然后利用交替優(yōu)化的思路，使得兩者同時達(dá)到optimal。一個凸函數(shù)的對偶函數(shù)其實(shí)就是原凸函數(shù)的一個下界，因此可以證明一個較好的性質(zhì)：在強(qiáng)對偶性假設(shè)下，即最小化原凸函數(shù)（primal）等價于最大化對偶函數(shù)（dual），兩者會同時達(dá)到optimal。這種轉(zhuǎn)化可以將原來很多的參數(shù)約束條件變得少了很多，以利于做優(yōu)化。具體表述如下：

minf(x) s.t.Ax=b ? ? ? ? ???L(x,y)=f(x)+yT(Ax?b)?對偶函數(shù)（下界）g(y)=infL(x,y)

在強(qiáng)對偶性的假設(shè)下，primal和dual問題同時達(dá)到最優(yōu)。

x?=argminL(x,y?)

因此，若對偶函數(shù)g(y)g(y)可導(dǎo)，便可以利用梯度上升法，交替更新參數(shù)，使得同時收斂到最優(yōu)。迭代如下：

xk+1:yk+1:=argminxL(x,yk)(x-最小化步)=yk+αk?g(y)=yk+αk(Axk+1?b)(對偶變量更新，αk是步長)xk+1:=arg?minxL(x,yk)(x-最小化步)yk+1:=yk+αk?g(y)=yk+αk(Axk+1?b)(對偶變量更新，αk是步長)

當(dāng)gg不可微的時候也可以將其轉(zhuǎn)化下，成為一個所謂的subgradient的方法，雖然看起來不錯，簡單證明下即可知道xkxk和ykyk同時可達(dá)到optimal，但是上述條件要求很苛刻：f(x)f(x)要求嚴(yán)格凸，并且要求αα選擇有比較合適。一般應(yīng)用中都不會滿足（比如f(x)f(x)是一個非零的仿射函數(shù)），因此dual ascent不會直接應(yīng)用。

轉(zhuǎn)載于:https://www.cnblogs.com/FYSong/p/5962224.html

總結(jié)

以上是生活随笔為你收集整理的分布式计算、统计学习与ADMM算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。