Fenchel-Lengendre Duality觀點下的優化演算法們(I):前言

03-12

前兩天 @Zeyuan AllenZhu 大神到本組visit，與之交流一番後感慨澤園確實是在思想的深度上已經站在（非）凸優化演算法理論領域的極前沿的。在他的眼裡，繁雜多樣的deterministic/stochastic (accelerated) first/second order methods早就已經化繁為簡，其中雖有各種細微的差別然而大體不出乎primal，primal-dual和dual的三種觀點出發而來。且其對各種方法間細微差別的來源理解已是極為深刻，短短的交流讓我實在也是收益良多，感覺把很多之前覺得不相關的知識結構終於慢慢聯繫在了一起。

因此，基於我本人先前的知識積累和最近的一些歸納總結，我希望將澤園腦海里漸漸統一的框架也在一系列的文章里分享給大家。另外，我可能也會想自己寫一些最近在優化理論、在線學習等相關領域的閱讀思考所得，所以不見得發文順序會是線性的（比如下一篇會集中討論mirror descent以及variants），請大家多包涵。

本文主要是提綱挈領，將澤園的primal，primal-dual，dual的三種觀點和與具體演算法之間的聯繫大概指出。本系列主要參考的是澤園在ICML 2017的tutorial talk（下為youtube連接，國內觀看需翻牆）。

https://www.youtube.com/watch?v=jPjhiaeYruQ&feature=youtu.be?

www.youtube.com

本節定義預備知識：Fenchel-Legendre Duality.

給定一個 $mathbb{R}^d$ 上良好的凸函數(proper convex function，可以簡單認為該凸函數在有效定義域上不會達到負無窮) $g(x)$ ，它的Fenchel dual定義為：

$g^*(y):=maxlimits_{xin mathbb{R}^d}{y^Tx-g(x) },forall~yin mathbb{R}^d.$

在這種條件下，我們擁有強對偶定理成立：即一個函數的對偶的對偶還是它自己。

$g^{**}(x):=maxlimits_{yin mathbb{R}^d} { x^Ty-g^*(y) }=g(x).$

還有其它值得注意的性質：

$g^*(y)$ 也是（proper）convex的。
$g(x)$ L-smooth等價於 $g^*(y)$ 1/L strongly convex。
$g(x)$ m-strongly-convex等價於 $g^*(y)$ 1/m-smooth。

其中假設函數足夠光滑，f(x)是L-smooth的定義為： $abla^2 f(x) preceq Lcdot I$ ，而f(x)是m-strongly-convex的定義為： $abla^2 f(x) succeq m cdot I$ 。可以統一用Hessian矩陣來刻畫。

三種觀點：primal，dual，primal-dual。原問題，對偶問題，原+對偶問題，分別對應針對原變數 $x$ ，針對原變數 $x$ 和對偶變數 $y$ 和針對對偶變數 $y$ 的優化問題。

Primal: $minlimits_{xin mathbb{R}^d} left{psi(x)+frac{1}{n}sum_{i=1}^n f_i(a_i^Tx) ight}$
Primal-dual: $minlimits_{xin mathbb{R}^d} maxlimits_{yin mathbb{R^n}} left{psi(x)+frac{1}{n}sum_{i=1}^n f_i^*(y_i)+frac{1}{n} y^TAx ight}$

(從Primal的表達式中代入 $f_i(a_i^Tx) = maxlimits_{yin mathbb{R}^n}{ y_icdot a_i^Tx-f_i^*(y) }$ )

Dual: $min limits_{yin mathbb{R^n}} left{-psi^*left(-frac{1}{n} A^Ty ight)+frac{1}{n}sum_{i=1}^n f_i^*(y_i) ight}$

(從Primal-dual的表達式中代入 $psi^*left(-frac{1}{n}A^Ty ight)=maxlimits_{xin mathbb{R^d}} left{ -frac{1}{n}y^TAx-psi(x) ight}$ )

原問題自然是一般我們最熟悉的形式，目標函數由一個convex的loss function（常可以分解為data point數量個的損失函數 $f_i$ 之和）加上一個同樣是convex的regularizer $psi$ 。比如SVM，Lasso，Ridge, Logistic Regression都是以這種形式最為常見在我們的視野當中。

至於問題的複雜度，我們可以用 $psi$ 是否是m-strongly-convex（ $psi^*$ 是否1/m-smooth）和 $f_i$ 是否是L-smooth（ $f_i^*$ 是否是1/L-strongly-convex）來刻畫。也就是說，每種形式都可以分為四類：

strongly-convex且smooth。
strongly-convex但不smooth。
不strongly-convex但smooth。
不strongly-convex也不smooth。

用以上標準我們很容易知道，Ridge Regression屬於第1類，L2-SVM屬於第2類（L1-SVM就是第4類了），Lasso和Logistic Regression屬於第3類。所以到這裡我們其實就有一個很自然的想法，像第2類問題，因為在原問題space上不光滑然而到對偶空間卻是光滑的，因此對偶演算法會天然有優勢（這也解釋了L2-SVM的主流演算法是對偶演算法，因為在原空間上的話需要額外再人工添加regularizer）。第3類問題則反之。

同樣的，我們在三種形式下可以得到某種程度意義上等價的同一類演算法的三種形式，並且自然預計這三種形式應該擁有相同的演算法複雜度。事實也是如此，比如我們Primal問題上最經典的gradient descent演算法： $x = x - abla(ldots)$ 顯然有Dual的版本 $y = y - abla(ldots)$ 。而這種用gradient的反方向來update變數的最速下降法在primal-dual的觀點上自然則會導出同時update變數 $x,y$ 的mirror descent。澤園在他的talk里用Ridge Regression做例子表明了這三種形式確實具有同樣的複雜度。

同樣，我們也有三種對應的加速（accelerated）演算法，primal和dual對應的accelerated gradient descent和primal-dual對應的mirror-prox/momentum演算法，它們同樣具有一致的複雜度（雖然形式上區別非常巨大）。

以此類推，我們當然對隨機演算法也可以推導出具有一致複雜度的三種形式的演算法。這也是澤園tutorial最主要的內容。但是，作為我這個系列的內容來說，我還是希望先繼續深入討論確定性first-order methods的具體性質。因此，我打算稍稍放慢腳步，暫緩介紹隨機性演算法的故事：下篇文章，我將著重討論擁有同一個名字，但在不同人筆下其實指的不是同一個東西的mirror descent演算法。它的主流版本演算法的性質，和gradient descent演算法的關係，以及它的加速版本mirror prox/momentum演算法的思路，以及mirror descent在在線學習（online learning）中的自然應用，也會指出一些關鍵性的推導步驟。

如果你對這個系列的內容比較期待，歡迎關注我，並催促我進行更新。那樣的話，我應該會更有動力更新之後的內容O(∩_∩)O

感謝閱讀！