【學界】Mirror descent: 統一框架下的一階演算法

04-26

本文首發於知乎專欄【Optimizers Garden】：Mirror descent: 統一框架下的first order methods 作者: @覃含章美國麻省理工學院（MIT）計算科學與工程方向博士在讀，清華大學工業工程及數學與應用數學（第二學位）本科。研究興趣主要為優化理論，機器學習演算法在運營管理中的應用。
『運籌OR帷幄』責任編輯： @文雨之（東北大學系統工程博士生）
歡迎原鏈接轉發，付費轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。
敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：
『運籌OR帷幄』大數據人工智慧時代的運籌學

一、序言：Mirror descent方法概述

Mirror descent方法第一次引起人們的廣泛注意是在20年前，Aharon Ben-Tal，Tamar Margalit和Arkadi Nemirovski三人在[1]中引用了該方法，解決了在一個幾百萬維的單純形（unit simplex $Delta_n:=left{ xin mathbb{R}_+^n: sum_{i=1}^n x_i=1 ight}$ ）上的凸優化問題，並應用在了 positron emission tomography （PET）相關的三維醫學圖像重構問題：一個最大似然問題（Maximum Likelihood Estimate）。

他們的成功之處便是拓展了其實是在歐式距離上定義的投影梯度下降演算法（projected gradient descent method），利用了一種更general的迫近點梯度下降演算法（proximal gradient descent method）的觀點，也就是重新定義了這種gradient descent演算法中的「距離」。具體來說，在上述問題中，即所謂的simplex setup，如果選取的「距離」為entropy function（熵函數），這類proximal algorithm在做prox step的時候（也就是投影，projection）在simplex上基本上是免費的。因此，他們成功給出了如上所述的一個大規模凸優化的演算法解決方案。

因此，從這個意義上我們知道proximal algorithm是一種比傳統的gradient descent方法更廣泛（適用於任何合理的"非歐式（non Euclidean）"距離）的觀點，本文我們主要就探究這一點。當然，對於mirror descent演算法還可以有很多其它的理解方式，如Zeyuan Allen-Zhu和學Lorenzo Orecchia[2]的研究觀點：gradient descent演算法可以看作從primal space出發的某種upper bounding，mirror descent演算法可以看作從primal-dual space出發的某種lower bounding。我之後會在個人專欄進行討論。

本文主要的參考資料是Ben-Tal和Nemirovski的講義[3]的第五章，和本校Prof. Robert Freund的「地下講義」。

二、問題描述

我們本文考慮的general問題為：

$minlimits_{xin X} F(x)= f(x)+P(x).$

其中， $F(x)$ 是我們的目標函數，它可以被分解為兩個函數之和： $f(x)$ 是凸（convex）且光滑（比如Lipschitz連續）的， $P(x)$ 是convex但可以不光滑，不過至少有一些方便計算的性質。另外， $X$ 是有限維的向量空間。

具體的例子比如說Lasso Regression， $X=mathbb{R}^n$ ， $f(x)=| Ax-b|_2^2$ ， $P(x)= C cdot |x|_1$ ，我們知道 $f(x)$ 是處處可導的，而 $P(x)$ 雖然不可導但是也是很容易處理的。或者 $P(x)$ 也可以表達任意的凸集約束，即取 $P(x)=0, ext{if }xin S$ 且 $P(x)=+infty, ext{if }x otin S$ 。當然這個時候我們希望凸集 $S$ 的結構不太複雜（比如ball，box或unit simplex）。

三、預備知識

一些必要的預備知識。

首先是範數（norm）。我們用 $|cdot|$ 表示向量空間 $X$ 上的範數，那麼我們在對偶空間 $X^*$ 所取的一點 $v$ 的範數定義是： $|v|^*:=max{ v^T:|x|leq 1 }$ ，這也是 $|cdot|$ 的對偶範數。

容易驗證我們有「範數的對偶的對偶是它自己」。且我們指出以下兩條性質：

$v^T xleq |v|_*|x|$ (H?lders inequality)
$forall~xin X,exists~ar{v}in X^* ext{s.t. } |ar{v}|_*=1 ext{ and }ar{v}^Tx=|x|.$

給定一個strongly convex的函數 $h(cdot):mathbb{R}^n ightarrow mathbb{R}, h(x)geq h(y)+ abla h(y)^T (x-y)+frac{1}{2}|x-y|^2,forall~x,y,$ 我們定義Bregman divergence function為 $D(x,y):mathbb{R}^n imesmathbb{R}^n ightarrow mathbb{R}:=h(x)-h(y)- abla h(y)^T(x-y)$ 。

我們指出， $D(x,y)$ 便是mirror descent algorithm更general的關鍵，即是用來刻畫各種非歐距離的要素。在proximal algorithm的框架里，它也被稱作prox(imal) function/prox(imal) term等等，因為它便是用來衡量兩個點 $x,y$ 的接近（proximity）程度的。 $D(x,y)$ 有很多性質，如它也是strongly convex的（given $y$ ），它不對稱， $D(x,y)geq frac{1}{2}|x-y|^2$ 等等，更深層次的探討可以見我之前的一個知乎回答[4]。

本節最後，我們指出mirror descent演算法分析里需要用的一個核心引理（「三點」性質），它最早由Paul Tseng[5]發現：

引理1（Three-Point Property）：對任意凸函數 $phi(cdot)$ 和Bregman function $D(x,y)$ ，對給定一點 $z$ 定義 $z^+:=argmin{phi(x)+D(x,z)}$ ，則我們有

$phi(x)+D(x,z)geq phi(z^+)+D(z^+,z)+D(x,z^+),forall~xin X.$

熟悉projected gradient演算法分析的同學可能已經注意到了， $z^+$ 其實相當於做了一步projection（實際上，在mirror descent的分析里這一步叫做prox(imal) step）。而這個性質即表明了任給兩點 $x,z$ ，將 $z^+$ 看成 $z$ 演算法迭代1次之後的結果，他們所導致的目標函數上的差可以用 $z,z^+,x$ 三個點之間的距離lower bound住，這也是保證mirror descent演算法能收斂的關鍵，我們可以由此導出mirror descent每一步都在降低 $F(x)$ 的值。這個引理的證明只需要利用convexity和 $D(x,y)$ 的性質，留作練習。

四、光滑情形下的演算法複雜度分析

本節我們假設 $f$ 可微，且導數Lipschitz連續： $| abla f(y) - abla f(x)|_*leq L|y-x|$ ，並證明mirror descent的收斂速度定理。那麼我們General 的prox gradient algorithm可以表示如下：即給定初始值 $x_0$ ，

$x_{t+1}leftarrow argmin_x{f(x_t)+ abla f(x_t)^T(x-x_t)+P(x)+LD(x,x_t) }.$

注意到上式其實有很多對min來說的常數項（只是為了分析方便），等價於

$x_{t+1}leftarrow argmin_x{ abla f(x_t)^Tx+P(x)+LD(x,x_t) }.$

本節我們證明收斂性定理：

定理1（光滑mirror descent收斂速度）： $F(x_t)leq F(x)+frac{LD(x,x_0)}{t}, forall~xin X$ .

顯然，在以上定理的基礎上，如果我們考慮 $X={ x:D(x,x_0)leq ar D }$ ，即「半徑」為 $ar D$ 的範圍內，令最優解 $x^*=argminlimits_{xin X}F(x),$ 就有 $F(x_t)leq F(x^*)+frac{ar D L}{t}.$ 也就是說，為了達到 $epsilon$ 的絕對誤差，我們需要 $frac{LD(x_*,x_0)}{epsilon}$ 步。

我們的證明還需要一個額外的引理，對導數L-Lipshitz連續的函數 $f$ 我們有如下的二次函數上界：

引理2： $f(y)leq f(x)+ abla f(x)^T(y-x)+frac{L}{2}|y-x|^2.$

證明基於微積分基本定理，留作練習。

現在我們就有了足夠的預備知識，可以證明本節主要定理了（非常短）！具體來說，我們進行如下推導：

$egin{align} F(x_{t+1})= & f(x_{t+1})+P(x_{t+1})\ leq & f(x_t)+ abla f(x_t)^T(x_{t+1}-x_t)+P(x_{t+1})+frac{L}{2}| x_{t+1}-x_t |^2 ag{引理2}\ leq & f(x_t)+ abla f(x_t)^T(x_{t+1}-x_t)+P(x_{t+1})+LD(x_{t+1},x_t) ag{Bregman性質}\ leq & f(x_t)+ abla f(x_t)^T(x-x_t)+P(x)+LD(x,x_t)-LD(x,x_{t+1}) ag{引理1}\ leq & f(x)+P(x)+LD(x,x_t)-LD(x,x_{t+1}) ag{凸函數性質}. end{align}$

也就是說我們得到了 $F(x_{t+1})leq F(x)+LD(x,x_t)-LD(x,x_{t+1})$ ，即演算法每步的效果大概是 $Lcdot(D(x,x_t)-D(x,x_{t+1}) )$ 。如果我們在這個式子中取 $x=x_t$ 則得到 $F(x_{t+1})leq F(x_t)$ ，即mirror descent每步確實遞減了 $F(x)$ ，再對這個式子兩邊對t求和，經過裂項相消就能得到定理1。

思考題1：對比gradient descent的收斂性分析，你發現有什麼相似的地方么，對應的區別在哪裡？（提示：考慮gradient descent中的 $f(x_{t-1})-f(x_t)leq ?.$ ）以及，如果我們取 $h(x,y):=|x-y|^2$ 我們的演算法會是怎麼樣的？（提示：gradient descent?!）

思考題2：L不知道的情況如何繼續用這個演算法，這裡我們假設理論分析也找不到一個合適的L的上界。（提示：利用引理2，然後考慮線搜索方法）

五、非光滑情形下的演算法複雜性分析

本節我們討論前一節mirror descent演算法的variant： $f$ 不再可微（即問題nonsmooth）的情況（當然，仍然是convex的），我們引入次梯度（subgradient）的記號 $partial f$ ，即 $gin partial f(x)$ 當且僅當 $f(y)geq f(x)+g^T(y-x),forall~yin X.$ 然後我們假設 $f$ Lipschitz連續： $|f(y)-f(x)|leq L|y-x|.$

這個時候，我們的prox subgradient演算法如下：給定初始值 $x_0,$ 我們需要定義一列步長（stepsizes） $alpha_t$ ，並每步進行如下迭代：

$x_{t+1}leftarrow argmin_x{ f(x_t)+g_t^T(x-x_t)+P(x)+frac{1}{alpha_t}D(x,x_t) }.$

其中 $g_tin partial f(x_t)$ ，也就是說我們利用次梯度代替梯度來進行迭代。另外，我們的步長選取也和光滑情況不太一樣。

我們指出，subgradient method不能保證演算法每步一定能減小 $F(x)$ 的值！收斂速度定理如下。

定理2（非光滑mirror descent收斂速度）： $minlimits_{0leq kleq t}F(x_k)leq F(x)+frac{frac{L^2}{2}sum_{l=0}^talpha_t^2+D(x,x_0)+alpha_0P(x_0)-alpha_t P(x_{t+1}) +sum_{l=1}^tP(x_t)(alpha_t-alpha_{t-1})}{sum_{l=0}^t alpha_l}.$

也就是說，如果我們同樣考慮 $X={x:D(x,x_0)leq ar D }$ ，且 $x_0in argmin_x P(x)$ ，那麼為了達到絕對誤差 $epsilon,$ 我們如果選取 $alpha_t:=frac{epsilon}{L^2}$ ,我們需要至少 $frac{2L^2ar{D}}{epsilon^2}$ 步，和定理1一比較我們就知道subgradient method確實是比graident method（即光滑情況下）要慢了1個次方的。當然，這是為了估計步數，我們指出一般來說一個更合理的步長選擇應該是 $alpha_t:=frac{2ar D}{Lsqrt{t+1}}.$

思考題3：在 $alpha_t:=frac{2ar D}{Lsqrt{t+1}}$ 的情況下化簡定理2。

思考題4：證明定理2。（提示：利用下面兩個引理，考慮 $F(x)-(f(x_t)+g^T(x-x_{t})+P(x))$ 的一個下界，其中 $gin partial f(x_t)$ ，即 $F(x)$ 和 $F(x_t)$ 的一階線性近似的差的下界）

引理3： $|g|_*leq L,forall~gin partial f(x).$

引理4： $forall~ain X,bin X^*,gamma>0: b^Ta+frac{1}{2}frac{|a|^2}{gamma}geq -frac{1}{2}gamma|b|_*^2.$

六、光滑情形下加速演算法的複雜性分析

本節我們考慮如何對光滑情況下的mirror descent進行加速。注意，不光滑情況的subgradient method一般來說沒有加速的辦法。我們的給出accelerated prox subgradient演算法如下：給定初始值 $x_0,z_0:=x_0$ 我們需要定義一列步長（stepsizes） $alpha_tin (0,1],$ 並每步進行如下迭代：

定義 $y_tleftarrow (1-alpha_t)x_t+alpha_t z^t.$
$z_{t+1}leftarrow argmin_x{ f(y_t)+g_t^T(x-y_t)+P(x)+alpha_tLD(x,z_t) }.$
$x_{t+1}leftarrow (1-alpha_t)x_t+alpha_t z_{t+1}.$

這種Nesterov式的加速方法，其幾何意義是不容易理解的，我這裡不多做贅述。我們指出，一種常用的步長為： $alpha_t=frac{2}{t+2}.$

可以想像的是，加速方法的證明比前兩節會更複雜一些（雖然說如果你理解的足夠好，完整的proof篇幅也是不長的），我們這裡就步介紹了，只介紹主要結果（假設步長已經如上選取好了）。

定理3（光滑情況下加速演算法的收斂速度）： $minlimits_{0leq kleq t}F(x_k)leq F(x)+frac{4LD(x,x_0)}{(t+1)^2}.$

也就是說，同樣考慮 $X={x:D(x,x_0)leq ar D }$ ，我們知道絕對誤差達到 $epsilon$ 的步數是 $sqrt{frac{4LD(x_*,x_0)}{epsilon}}$ ，比smooth情況下naive的mirror descent又快了1個次方！也就是說，實際上在光滑情況下你永遠應該考慮使用加速版本（除非你要用coordinate descent，沒有對應的加速方法，不過本文我們不討論這點了）

思考題5：思考加速演算法的幾何意義。這點其實歷史上已經有很多著名的討論了。

思考題6：證明定理3。（其實你仍然只需要利用Bregman function和convex function的性質，引理1，引理2，但需要你有更好的理解：)）

七、在單純形上的應用

本節我們討論mirror descent演算法的一個實際應用：在unit simplex上的凸優化問題，也就是讓題頭那篇paper名聲大噪的原因。此時，我們的 $f$ 可以是任意可微凸函數，不過本節為了討論方便起見我們認為它是光滑可微的。也就是說，我們本節考慮 $P(x)$ 是 $Delta_n$ 的indicator function，即在 $xin Delta_n$ 的時候取值0，不然取值 $+infty.$ 且我們考慮所謂的simplex/entropy setup，讓我們的Bregman function由entropy function組成： $h(x):=sum_{j=1}^n x_jlog(x^{(j)})+log(n).$

也就是說，prox step實際上就是要計算 $x_{t+1}leftarrow argminlimits_{xin Delta_n} { abla f(x_t)^Tx+LD(x,x_t) }.$ 我們指出，這一步實際上是很快的，即有closed form如下：

$x_{t+1}^{(j)} = frac{x_t^{(j)} e^{-[ abla f(x_t)]^{(j)/L}} }{sum_{i=1}^n x_t^{(i)} e^{-[ abla f(x_t)]^{(i)/L}} },forall~i=1,ldots,n.$

思考題7：證明上述迭代公式成立。（提示：entropy的引入很關鍵，strongly convex的unit simplex約束優化問題）

也就是說，這一步實際上相當於只是作normalization！而且實際上，由於都是exponents，實際update的時候可能只需要update很少的一部分component（這裡涉及到numerical details，略過），另外，這一步也可以再被並行化！

於是，我們看到了mirror descent的一個具體應用，當然，為了更好的理解其優勢我們需要作如下的思考。

思考題8：考慮對同樣問題的projected gradient descent的演算法複雜度。（提示：主要比較projection的複雜度）

思考題9：給出對同樣問題的accelerated mirror descent演算法。

八、拓展：在線學習中的應用

本文的最後，我們指出first order methods在online learning中的自然應用，比如我們的問題改變定義，即我們在每個時間 $t,$ 都有一個adversary選擇一個 $f_t(cdot)$ 並report它在 $x_t$ 的(sub)gradient給我們。那麼顯然我們的演算法可以直接用來進行"learning"，我們的regret是 $sum_{t=1}^T f_t(x_t)- sum_{t=1}^T f_t(x^*)$ （注意這裡我們假設了目標 $x^*$ 是固定的），即我們的演算法可以某種程度上minimize這個regret。

當然，更有意思的地方在於比如 $f_t(cdot)$ 是IID（獨立同分布）地從一個分布中被選取，mirror descent仍然能保證 $O(sqrt{T})$ 的regret。對mirror descent和相關online learning的應用有興趣的同學可以進一步參閱參考文獻[3][6][7]。

參考文獻

[1] Ben-Tal, Aharon, Tamar Margalit, and Arkadi Nemirovski. "The ordered subsets mirror descent optimization method with applications to tomography." SIAM Journal on Optimization 12.1 (2001): 79-108.

[2] Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent." arXiv preprint arXiv:1407.1537 (2014).

[3] Aharon Ben-Tal, and Arkadi Nemirovski. "Lectures on Modern Convex Optimization". https://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf

[4] 覃含章. "如何理解Bregman Divergence?" https://www.zhihu.com/question/22426561/answer/209945856

[5] Tseng, Paul. "Approximation accuracy, gradient methods, and error bound for structured convex optimization." Mathematical Programming 125.2 (2010): 263-295.

[6] Beck, Amir, and Marc Teboulle. "Mirror descent and nonlinear projected subgradient methods for convex optimization." Operations Research Letters 31.3 (2003): 167-175.

[7] Bubeck, Sébastien. "Introduction to online optimization." Lecture Notes (2011): 1-86.

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號後台留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

運籌學|控制論|優化理論愛好者，歡迎加qq群：686387574

人工智慧愛好者，歡迎加qq群： 685839321

數據科學|分析愛好者，歡迎加qq群：130414574

最後敬請關注和擴散本專欄及同名公眾號，會陸續發布運籌學、人工智慧中優化理論相關乾貨及行業動態：『運籌OR帷幄』大數據和人工智慧時代下的運籌學 - 知乎專欄