动力系统与优化算法

从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