优化 | Nesterov's accelerated method

运筹OR帷幄 2021-05-04 21:17
↑↑↑↑↑点击上方蓝色字关注我们!






『运筹OR帷幄』温故


作者:覃含章



编者按


本文旨在给出Nesterov加速算法之所以能对常规一阶算法加速的一种代数解释,这种观点来自于将此种方法看成gradient descent(primal view)和mirror descent(dual view)的线性耦合(linear coupling)。我们知道,一阶算法常用于深度学习中对神经网络损失函数的训练当中,而本文则是给出了Nesterov加速算法背后的一些更深层次的原理性探讨。


我们知道,著名的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 didn't understand what's behind."


本文旨在给出Nesterov加速算法之所以能对常规一阶算法加速的一种代数解释,这种观点来自于将此种方法intepret成gradient descent(primal view)和mirror descent(dual view)的线性耦合(linear coupling)。这种观点是由朱泽园和Lorenzo Orecchia在14年提出([1])。


自然,这并不是唯一一种intepret为何这种方法可以加速一般一阶算法的观点。比如,Nesterov最早基于potential function的proof: [2] 基于微分方程的interpretation(看成离散化的ODE):[3] 基于椭圆法(ellipsoid method)的几何加速算法(形式上已经和Nestrov的原始方法区别很大了):[4]


其实这些其它的观点也很有意思,不过和本文的观点出发点完全不同,所以本篇文章不会涉及。



1.一些关于Gradient Descent和Mirror Descent的基本观点

本节我们给出一些high level的对于gradient descent(GD)和mirror descent(MD)的相关讨论。

我们指出,GD在primal view下的本质是利用convexity minimize一个quadratic upper bound(同样,这点在专栏文章里已经有详细讨论)。具体来说,固定步长  的gradient descent的更新步骤可以写成:

注意这里我们MD的收敛速度比GD要慢一个量级,因为我们考虑了非光滑情形,即每一步MD甚至不一定会降低目标函数值。至于光滑情形下的分析和GD类似,具有同样速度的收敛速度,详情请见公众号之前的文章。


同样我们指出一个很显然的观察, MD与GD相反,在(sub)gradient比较小的时候更加有效,这是因为核心引理里的regret实际上在这种情况才比较小,反之可能会很大。



2.基于线性耦合的加速


参考文献:

[1] Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent." arXiv preprint arXiv:1407.1537 (2014).

[2] Nesterov, Yurii. "A method of solving a convex programming problem with convergence rate O (1/k2)." Soviet Mathematics Doklady. Vol. 27. No. 2. 1983.

[3] Shi, Bin, et al. "Understanding the acceleration phenomenon via high-resolution differential equations." arXiv preprint arXiv:1810.08907 (2018).

[4] Bubeck S, Lee YT, Singh M. A geometric alternative to Nesterov's accelerated gradient descent. arXiv preprint arXiv:1506.08187. 2015 Jun 26.


火柴OR青年

全网独家运筹er交友平台,每周一次AI匹配最适合你的运筹专业优质小伙伴!

火柴OR青年 | 对运筹优化感兴趣?快来PICK与你深度匹配的TA!【DeepMatch】



相关文章推荐

下文为介绍mirror descent方法的综述教程,强烈推荐对这方面基础知识不熟悉的同学在阅读本文前先行阅读。

点击蓝字标题,即可阅读【学界】Mirror descent: 统一框架下的一阶算法


其他

【优化】为什么凸优化这么重要?

优化 | 优化理论能给深度学习带来怎样的革命?

优化|要理解深度学习,必须突破常规视角去理解优化





—— 完 ——



文章须知

文章作者:覃含章

责任编辑:覃含章

审核编辑:阿春

微信编辑:玖蓁

本文由『运筹OR帷幄』原创发布

如需转载请在公众号后台获取转载须知