Nesterovs accelerated method：gradient descent & mirror descent的線性耦合

04-29

本文是「Fenchel-Lengendre Duality觀點下的優化演算法們」系列的第二篇文章。第一篇前言文章的鏈接：Fenchel-Lengendre Duality觀點下的優化演算法們(I):前言。

我們知道，著名的Nesterov加速演算法由Nesterov在83年即提出，並證明了廣泛情形下這種一階演算法（即只用到gradient信息）在凸優化問題中的收斂速度達到最優（match information lower bound）。然而，這麼多年以來，為何形式上一個簡單變化（比如，基於gradient descent）之後的演算法就能將gradient descent的收斂速度整整提升一個量級，達到最優，這背後隱含的原理一直是很多人難以理解和解釋的。我記得之前在Prof Robert Freund課上他講Nemirovski回憶第一次見到Nesterov這個work的時候，「I was very surprised that a seemingly mere algebraic trick can make a real difference in the algorithm in terms of its convergence behavior」... "It was a beautifully written proof that I felt like I didnt understand whats behind."

本文旨在給出Nesterov加速演算法之所以能對常規一階演算法加速的一種algebraic解釋，這種觀點來自於將此種方法intepret成gradient descent（primal view）和mirror descent（dual view）的線性耦合（linear coupling）。這種觀點是由 @Zeyuan AllenZhu 和Lorenzo Orecchia在14年嚴格提出（見下面文章鏈接）。

Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent." LIPIcs-Leibniz International Proceedings in Informatics. Vol. 67. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.?

drops.dagstuhl.de

自然，這並不是唯一一種intepret為何這種方法可以加速一般一階演算法的觀點。比如，Nesterov最早基於potential function的proof: Nesterov, Yurii. "A method of solving a convex programming problem with convergence rate O (1/k2)." Soviet Mathematics Doklady. Vol. 27. No. 2. 1983.

基於微分方程的interpretation（看成離散化的二階ODE）： Su W, Boyd S, Candes EJ. A differential equation for modeling Nesterov』s accelerated gradient method: theory and insights. Journal of Machine Learning Research. 2016 Jan 1;17(153):1-43.

基於橢圓法（ellipsoid method）的幾何加速演算法（形式上已經和Nestrov的原始方法區別很大了）：Bubeck S, Lee YT, Singh M. A geometric alternative to Nesterovs accelerated gradient descent. arXiv preprint arXiv:1506.08187. 2015 Jun 26.

其實這些其它的觀點也很有意思，不過和本文的觀點出發點完全不同，所以本篇文章不會涉及。如感興趣的人多（請評論/給我留言）可能我之後也可以介紹Boyd，Candes，Bubeck等人的觀點。

本節我們給出一些high level的對於gradient descent(GD)和mirror descent(MD)的相關討論。

我們考慮一般情形的凸優化問題：函數 $f(x)$ 是一個在閉凸集 $Qsubset mathbb{R}^n$ 上的可微凸函數，並且我們假設 $f$ 足夠光滑：L-smooth， $| abla f(x)- abla f(y)|_*leq L|x-y|$ . （我們假設讀者已經閱讀過系列文章（I）和專欄文章Mirror descent: 統一框架下的first order methods，具有相關預備知識。這裡其實用的是一致的定義，也不會再詳細定義dual norm這些具體概念了）

首先我們指出，GD在primal view下的本質是利用convexity minimize一個quadratic upper bound（同樣，這點在專欄文章里已經有詳細討論）。具體來說，固定步長 $1/L$ 的gradient descent的更新步驟可以寫成：

$ext{GD}(x)=argminlimits_{yin Q} left{ frac{L}{2}|y-x|^2+left< abla f(x),y-x ight> ight}$

定義 $Delta(x)=minlimits_{yin Q} left{ frac{L}{2} |y-x|^2+left< abla f(x),y-x ight> ight}$ .

證明GD收斂的核心引理便是每一步演算法迭代都能降低當前目標函數的值，即

$f( ext{GD}(x))leq f(x)-Delta(x)$ ，如果考慮特殊情形 $Q=mathbb{R}^n$ 那麼 $f( ext{GD}(x))leq f(x)-frac{1}{2L}| abla f(x)|^2_*$ .

定義 $x^*$ 是 $Q$ 上的minimizer，考慮歐式模（L2 norm，最簡單的情形），由此我們有GD的收斂性定理：

$f(x_T)-f(x^*)leq Oleft(frac{L|x_0-x^*|_2^2}{T} ight)$ 或者說 $Tgeq Omegaleft( frac{L| x_0-x^*|_2^2}{epsilon} ight)Rightarrow f(x_T)-f(x^*)leq epsilon.$

我們注意到很顯然的一點，GD在gradient值（ $| abla f(x)|^2_*$ ）很大的時候會很有效，因為核心引理保證了這樣每一步使目標函數值降低的值也會很大，反之即在比較flat的區域則就對目標函數值的下降會比較緩慢。

接下來我們簡單回顧MD。之前的專欄文章里我們已經指出MD同樣適用於非光滑的凸優化，所以這裡我們假設 $f$ 僅僅是Lipschitz continuous: $forall~x,yin Q, |f(x)-f(y)|leq L|x-y|$ 。步長 $alpha$ 的GD演算法的更新步驟可以寫成：（ $gin partial f(x), D$ 是Bregman divergence function，不清楚定義的請見之前的文章）

$ext{MD}(x)=argminlimits_{yin Q}left{ f(x)+alphaleft<g, y-x ight>+ D(x,y) ight}.$

我們指出，MD的核心引理是minimize dual averaging lower bound。具體來說，

$forall~uin Q,alpha (f(x_t)-f(u))leq alpha left< partial f(x_t),x_t-u ight>leq frac{alpha^2}{2}|partial f(x_t)|_*^2+D(x_t,u)-D(x_{t+1},u)$ ,

注意到第一個不等號我們利用了 $f(u)$ convexity的一個lower bound，第二個式子我們利用了3-point property（見MD的專欄文章）。這一項 $left< partial f(x_t),x_t-u ight>$ 相當於是online optimization里第 $t$ 步選擇 $u$ 所導致的regret。我們將 $t$ 從0到T-1求和，裂項相消就有

$alpha T(f(ar x)-f(x^*) )leq sum_{t=0}^{T-1} alphaleft< partial f(x_t),x_t-u ight>leq frac{alpha^2}{2}sum_{t=0}^{T-1}|partial f(x_t)|_*^2+D(x_0,x^*)-D(x_T,x^*).$

注意 $ar x = sum_{t=0}^{T-1} x_t$ ，令 $Theta$ 是 $D(x_0,x^*)$ 的一個上界，另 $alpha = frac{sqrt{2Theta}}{Lsqrt{T}}$ ，則有MD的收斂性定理：

$f(ar x) -f(x^*)leq Oleft(frac{sqrt{2Theta}cdot L }{sqrt{T}} ight)$ 或者說 $Tgeq Omegaleft(frac{2Theta L^2}{epsilon^2} ight) Rightarrow f(ar x) -f(x^*)leq epsilon$ .

注意這裡我們MD的收斂速度比GD要慢一個量級，因為我們考慮了非光滑情形（回憶系列（I），即使primal光滑的情況下dual問題也可能不光滑），即每一步MD甚至不一定會降低目標函數值。至於光滑情形下的分析和GD類似，具有同樣速度的收斂速度，詳情請見專欄的MD文章。

同樣我們指出一個很顯然的觀察， MD與GD相反，在(sub)gradient比較小的時候更加有效，這是因為核心引理里的regret實際上在這種情況才比較小，反之可能會很大。

基於上一節的討論，那麼一個自然的思路是能否把某種意義上具有互補特性的GD與MD結合，比如我們的問題是考慮在給定 $x_0$ 滿足 $f(x_0)-f(x^*)leq 2epsilon$ 的情況下，找到 $x$ 使得 $f(x)-f(x^*)leq epsilon$ (從 $2epsilon$ 到 $epsilon$ 的步驟往往是一階演算法們耗時最多的過程)，然後我們的演算法就是設定一個閾值 $K$ ，然後如果 $| abla f(x)|_2geq K$ 我們就迭代GD，反之就迭代MD。簡單起見，先假設我們的演算法觀察到的gradient值永遠是大於K，或是小於K的，這樣T步GD需要 $Tgeq Omegaleft( frac{epsilon L}{K^2} ight)$ 達到目標，而T步MD需要 $Tgeq Omegaleft( frac{K^2}{epsilon^2} ight)$ ，我們的目標就變成了找到一個最好的 $K$ 使得 $Tgeq Omegaleft(maxleft{ frac{epsilon L}{K^2} , frac{K^2}{epsilon^2} ight} ight)=Omegaleft( frac{L}{epsilon} ight)^{1/2}$ .

當然這個方法並不實用，只能是一個思想實驗。因為實際情況下顯然不可能觀察到的gradient值永遠在閾值的一邊，這種情況下這種演算法顯然會很差，因為可能GD跑了幾步剛降低了一些目標函數值結果gradient值很小了，這時候MD接入，可能反而又開始增加目標函數值，也就是說這個naive演算法其實是完全可能不收斂的。那麼自然經過思考一個更好的解決方案便是線性耦合（linear coupling）！具體來說，我們第t步迭代的時候應該是同時對 $x_t$ 做GD和MD，然後求一個加權平均值作為 $x_{t+1}$ ！而這，就是Nesterov基於momentum的加速思想的一種algebraic詮釋。考慮題圖，Nesterov在primal space上的演算法可以想像成有 $x_t$ 是拖著一塊磁鐵的GD演算法，即除了要往負梯度方向走以外，它的運動同時具有比較大的慣性。

從algebraic的角度，那麼我們的加速演算法便可以寫成如下迭代過程：

$x_{t+1}leftarrow au ext{GD}(x_t) + (1- au) ext{MD}(x_t).$

類似於前面的 $K$ ，這裡我們需要仔細定出 $au$ 來達到一個真正數量級上的加速。在Zeyuan和Lorenzo的工作里，便是具體確定了 $alpha$ 和 $au$ 的值，用全新的proof recover了Nesterov當年的結果。具體來說，在改變步長的情況下，在第t步選擇 $alpha_{t+1} = frac{t+2}{2L}, au_t=frac{1}{alpha_{t+1}L}=frac{2}{t+2}$ ，我們有

$f(x_T)-f(x^*)leq Oleft( frac{4Theta L}{T^2} ight)$ 或者說 $Tgeq Omegaleft( sqrt{frac{4Theta L}{epsilon}} ight)Rightarrow f(x_T)-f(x^*)leq epsilon.$

具體的proof有興趣的同學可以自行參閱他們的paper。

接下來的計劃可能是介紹隨機一階演算法們和如何對他們進行加速。我個人最近在集中研究multi-arm bandit相關的問題，也可能會寫一些自己的總結。敬請期待！