Mirror descent: 統一框架下的first order methods

03-27

在之前的文章（Fenchel-Lengendre Duality觀點下的優化演算法們(I):前言）中，我提及了我想先相對深入地探討一下mirror descent這一類演算法。Mirror descent這個名字這幾年也是越來越響亮了，然而日常交流中我發現可能很多同學還是沒有很好的理解它。

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

The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography Read More: http://epubs.siam.org/doi/abs/10.1137/S1052623499354564?

epubs.siam.org

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

因此，從這個意義上我們知道proximal algorithm是一種比傳統的gradient descent方法更general（適用於任何合理的"非歐式（non Euclidean）"距離）的觀點，本文我們主要就探究這一點。當然，對於mirror descent演算法還可以有很多其它的理解方式，如在Fenchel-Duality觀點系列的下一篇我會討論澤園的觀點：gradient descent演算法可以看作從primal space出發的某種upper bounding，mirror descent演算法可以看作從primal-dual space出發的某種lower bounding，也請期待。本文主要的參考資料是Ben-Tal和Nemirovski的如下講義第五章，和本校Prof. Robert Freund的「地下講義」。

Lectures on Modern Convex Optimization?

www2.isye.gatech.edu

我們本文考慮的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 |x|_*|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$ 等等，更深層次的探討可以見我之前的一個回答：

如何理解Bregman divergence？?

www.zhihu.com

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

引理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，然後考慮line search方法）

本節我們討論前一節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) }.$ 我們指出，這一步實際上是free的，即有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演算法。

本文的最後，我們指出一些extensions。首先是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，with high probability（熟悉bandit的同學應該知道UCB，Thompson sampling這些演算法都有這樣的regret bound）。這其實是利用了mirror descent也可以用來處理stochastic optimization問題的性質，不過我之前也說了先只針對deterministic的優化問題/演算法所以這方面也不深入討論了。

對mirror descent有興趣的同學可以參閱題頭和其它一些相關的參考文獻。之後我應該會介紹澤園的觀點，在duality觀點下比較gradient descent和mirror descent，以及他們的coupling->Nestrovs accelerated gradient descent，敬請期待！

Mirror descent and nonlinear projected subgradient methods for convex optimization?

www.sciencedirect.com

Approximation accuracy, gradient methods, and error bound for structured convex optimization?

link.springer.comIntroduction to Online Optimization - Sébastien Bubeck?

sbubeck.com