优化 | Nesterov's accelerated method

『运筹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.基于线性耦合的加速