動力系統與優化演算法

從ODE的角度看優化演算法

科技發展的重要組成部分就是學科之間的相互借鑒和融合。很多概念和理論是在被提出很久之後才發現了他在另一個似乎完全不想關的領域的應用。比如說我們都很熟悉的傅里葉同志，他的老本行是研究燒鍋爐的。傅里葉當年apply for professor [1] 的時候，用的文章叫做「熱的傳播」，裡面提出的熱傳導方程概括了後世一直到現在的燒鍋爐學問。甚至傅里葉自己就是晚年認為熱能包治百病，燒鍋爐中暑死掉的。傅里葉在解這個方程的時候，發現可以用三角函數的無窮級數來表示一個函數，這就是傅里葉變換。今天說起傅里葉變換，人們首先想到的肯定不是鍋爐，而是信號處理一類的東西。這就是傅里葉變換在另一個完全不相干領域的應用。從鍋爐到示波器，傅里葉的思想完成了從工業時代到信息時代的進步，或者說從蒸汽朋克到賽博朋克的進化 [2]。

又比如說，不是很多人講深度學習其實是某一門古老的化學的分支嗎？（來自傅里葉的微笑）！！

好了不說廢話了，今天我們就來講一下這個動力系統和優化演算法這兩個看起來沒關係的學科的關係。我們知道，優化分為離散優化和連續優化。機器學習里的優化大體都是連續優化，然而這個連續只是說objective function是連續的，優化的演算法依然是離散的。我們要把演算法寫成迭代的形式，每一步的解是一個關於上一步的解和一些其他東西的函數。迭代的演算法實現起來很容易，但是分析起來卻並不簡單，至少不是很直觀。簡單的演算法，比如gradient descent，還能夠很輕鬆的推導出收斂的性質，一些更複雜的演算法就不那麼好理解了。有人就想到，我們能不能從「連續」的角度去研究這些迭代演算法，也就是說，把演算法的每一步當成一個連續的軌跡的某種離散化，這樣我們就可以通過研究連續的軌跡來獲取關於對應迭代演算法的信息。這也是我們今天要探討的東西。

微積分的課上都學過最簡單的數值解常微分方程的方法：Euler Method。簡單來說，我們想解一個常微分方程

我們可以將其用一階泰勒展開離散化，這樣我們就得到了這個函數在初始點的一階近似，然後我們沿著這個切線的方向前進一小步，在那個地方再做一階近似，以此類推。

到目前為止，我們談論的東西和優化還是沒有什麼關係，但是當你把上面的迭代式和gradient descent的迭代式比較一下，你就會發現，gradient descent實際上就是嘗試對下面這個常微分方程用Euler Method做數值解。這裡我們討論簡單的情況，也就是gradient descent的步長為一個定值η，對應的就是Euler Method裡面的h。

當然gradient descent是最簡單的優化演算法，Euler method也是最簡單的常微分方程數值解法，所以這樣的聯立看起來有些trivial, 畢竟直接分析gradient descent也是很容易的。然而這種聯繫給我們對優化演算法的研究提供了一種新的思路。比如我們可以通過研究Euler Method里的h的方式來找到最好的gradient descent的步長，以及在該步長下一些關於收斂速度的結果。這種研究方法其實很早以前就出現了[3]，其核心思路是想像優化演算法的步長趨向於無窮小，使得優化演算法每一步組成的軌跡趨向於一個ODE的軌跡，然後通過已經非常成熟的ODE相關理論來獲得一些關於優化演算法的deep insights。尤其是，當一個新的優化演算法被提出的時候，有時候傳統的分析方法很難理解他。但是利用這種新方法分析，可能會有一些有趣的發現。

一個顯著的例子就是Weijie Su, Stephen Boyd 和 Emmanuel J. Candes在2015年的NIPS上發表的論文（NIPS上發表的是短版的，完整版發布在2016年的JMLR上）A Differential Equation for Modeling Nesterov』s Accelerated Gradient Method: Theory and Insights。 這篇文章討論的是用ODE理解優化里一直很迷的一個演算法 - Nesterov』s Acceleration [4]。本公眾號之前的一篇文章已經對這個演算法有所介紹。它是由戰鬥民族著名的應用數學家尤里 Nesterov在1983年一篇僅有四頁的小文章提出來的，發表在蘇聯的數學期刊上。我在讀過的論文的引用中見過它太多太多次了，足以見得這個演算法影響之深遠。雖然這個演算法有很多種不同（但是等價）的表達式，但是原理非常簡單，大概就是在每做一步gradient descent的時候加上一些之前迭代步驟的信息。這個演算法很了不起的一點是，它的收斂可以被證明達到了任何只包含一階梯度信息的優化演算法的最快收斂速度。然而關於這個演算法背後的intuition卻一直是個迷。Nesterov在最早的那篇小論文里並沒有提供任何直覺上的解釋，只是給出了收斂速度的數學證明。這個證明的過程被很多人評價是 「pure algebraic trick」 ，就跟我們做一些數學難題的時候拼湊項一樣。然後很多人提出這個演算法成功的原因是因為他通過把不同的步驟加權平均提升了穩定性，我之前也是這麼認為的，直到不久前看到Georgia Tech的趙拓教授在知乎上介紹他的研究 [5] ，才發現事情並沒有這麼簡單。簡單來說，Nesterov』s Acceleration並不是加權平均，而是一種外插值（extrapolation）,實際上是破壞穩定性的。當然他主要是想從物理的角度理解，這就扯遠了。除此之外年輕的優化大神朱澤園Allen-Zhu提出「linear coupling」的思路將Nesterov』s Acceleration看成是gradient descent和mirror descent的結合。總之直到現在人們也不敢說完全理解了Nesterov』s Acceleration背後的含義

而我們的主角是時候出場了。Nesterov』s Acceleration畢竟也就是個簡單的迭代式，採取之前介紹過的思路，找到那個命中注定與他匹配的ODE並非難事。Su等人用半頁紙推導出了這個ODE：（x的初始值和x的導數的初始值都是0）

停下，這不對啊，這個演算法明明是一階的，怎麼來個二階的ODE？剛讀到這裡我也是懵逼的，但是其實想一想，我們說的一階演算法指的是梯度，是對x求導，這裡ODE是關於t的，其實沒有什麼關係。這個ODE的推導還是十分簡單的，有興趣可以去看一下那篇論文。

當然了，這個ODE並不好分析。傳統的ODE理論對這個方程的解的存在性和唯一性都沒法分析出來。這主要是因為這個3/t的項導致該方程在t=0的時候是singular的。在這裡作者用了一些分析上的辦法，比如用Arzela-Ascoli theorem去找convergent subsequence，這裡就不細說了。我們看看作者發現了Nesterov』s Acceleration的什麼奧秘吧。首先作者嘗試用Euler Method去解這個ODE，然後通過一些計算證明了Nesterov』s Acceleration的迭代過程大致等同於Euler Method裡面的步長取2/√L，這裡L是f的梯度的Lipschitz constant。而相對的，gradient descent對應的ODE如果想用Euler Method的話，在某些情況下步長要小於等於2/L才能收斂，而在L比較大的時候遠小於2/√L。這意味著從ODE數值解的角度來看，Nesterov』s Acceleration允許更大的步長，那麼在都保證收斂的情況下，收斂速度自然比gradient descent快。同時，作者也從ODE的角度推導出了Nesterov』s Acceleration的收斂速度，和Nesterov本人的結果是一致的。

還有更重要的一點，我們回去看看這個ODE，第二項的那個3非常可疑，為什麼是3而不是其他的數呢？這是由Nesterov』s Acceleration演算法里加上之前步驟的信息這一項的係數決定的。作者發現，如果把這個3替換成大於3的其他常數，這個ODE依然可以達到類似的收斂速度。所以通過改變這個常數，作者推導出了一個系列的優化演算法。在某些情況，改變這個常數所對應的優化演算法有更好的結果。比如當函數是強凸的時候，讓這個常數大於9/2可以有更快的收斂速度。這體現了用ODE研究優化的另一個閃光點：有可能從一個特定演算法推導出更多的演算法。

那麼這裡這篇文章就告一段落。這篇文章啟發了很多後來的研究者，尤其是Berkeley的Michael Jordan組。在2016年，Jordan的學生Ashia Wilson發表了兩篇 [6] [7] 分析優化里加速演算法的論文，為聯繫動力系統和優化加速速演算法提供了更紮實的理論基礎。這兩篇論文用到了變分的思想，構造了一個叫Bregman Lagrangian的泛函，並且計算他對應的Euler-Lagrange equation，再對Euler-Lagrange equation做一些比較複雜的離散化。通過這些方法，作者為加速演算法構建了一個很寬泛的框架，Nesterov』s Acceleration只是其中特別的一種情況。

其他的相關研究還包括了用隨機微分方程（SDE）來了解隨機優化演算法。正如從gradient descent到SGD一樣，從ODE到SDE也是一個自然的拓展。 [8]是其中一個例子。這就為相關研究打開了更寬廣的門，因為現在有很多隨機優化演算法都還沒有很到位的理解。

這篇文章到這裡就結束了。其實學習上面提到的這些論文給我最大的感觸就是，對於一個優化方法，並不只是推導它的演算法機收斂速度就夠了，而是要了解它背後的insight。前者Nesterov本人用四頁紙就可以搞定，而後者卻是很多研究者花了30多年還沒有完全解決的問題。Insight重要嗎？是也不是。不管你去不去更深入的了解，演算法都擺在那邊，隨時可以拿來用，但是對於演算法背後的研究卻打開了新世界的大門，提供了一個更高層次的看問題角度。正如早年物理學界一直在嘗試的大一統理論，或許沿著這條路走下去，會通往數值優化的大一統呢。

Reference

[1] 視察國機二院，（大霧）

[2] 段子主體來源於知乎某回答，然而實在找不著了

[3] A. A. Brown and M. C. Bartholomew-Biggs. Some effective methods for unconstrained optimization

based on the solution of systems of ordinary differential equations. Journal of

Optimization Theory and Applications, 62(2):211–224, 1989.

[4] Y. Nesterov. A method of solving a convex programming problem with convergence rate

O(1/k2). In Soviet Mathematics Doklady, volume 27, pages 372–376, 1983.

[5] 常見的關於momentum的誤解（上）, https://zhuanlan.zhihu.com/p/35323828

[6] A. C. Wilson, B. Recht, and M. I. Jordan. A Lyapunov analysis of momentum methods in optimization. arXiv:1611.02635v1 [math.OC] 8 Nov 2016.

[7] A. Wibisono, A. C. Wilson, and M. I. Jordan, A variational perspective on accelerated methods in optimization, Proceedings of the National Academy of Sciences, 133 (2016), pp. E7351–E7358.

[8] Walid Krichene, Alexandre Bayen, and Peter Bartlett. Accelerated mirror descent in continuous and discrete time. In Advances in Neural Information Processing Systems (NIPS) 29, 2015.

作者簡介：

Xavier，本科就讀於加州大學伯克利分校，應用數學和統計學雙專業。目前於芝加哥大學就讀計算數學專業博士。本科階段的學習和研究主要集中於偏微分方程的數值解以及醫學圖像分析。博士階段主要興趣是非凸優化及其在機器學習中的應用，以及計算機視覺的相關問題。

編輯：蜜汁醬，Echo

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！