优化算法新观点

这两天闲下来了，写篇新专栏

这个专栏基于我上学期一门课的大作业见下

我这里的内容都是很简单的介绍，列一些经典文献而已233

我上面report的更详细，而且有更多我的数值佐证一些观点，做出来的实验和一些文章里assert的理解不太符合

基本想法是，把离散一步一步的优化算法连续化观察

基本的motivation是最简单的梯度下降

x_{k+1}=x_{k}-\Delta t\nabla f(x_k)

可以理解成在simulate这个ode \dot X = -\nabla f(X)

然后[1]发现我们熟知的nesterov算法会对应着 \ddot X +\frac{3}{t}\dot X +\nabla f(X)=0

然后大家自己推一下也会发现，动量梯度下降会对应着 \ddot X +\dot X +\nabla f(X)=0

［这里其实我有一个更深刻的理解，因为很少有数值ode社区的人来看这个问题，这个\ddot X在步长变小的时候会消失，其实最后还是收敛到原来的梯度流，变快的原因是\ddot X是修正方程（就是原来的梯度流是O(\Delta t)逼近，二阶方程是更高阶的逼近，这个想法我们想继续做一些工作）］

［1］通过构造能量函数［利亚普诺夫分析的方法证明了优化算法的收敛性

这个构造能量函数的方法还有很多用处比如

［3］、［4］用这个想法证明了优化算法脱离鞍点的速度［随机的部分后面会说

［5］乍看起来很神奇

可以看我最开始贴的note的最后，我讲了这个东西怎么出来的

用一个变换就可以吧 \dot X 项消去，变成典型的牛顿第二定律方程

如果知道一点pde／物理就知道可以用最小作用原理就会出来MJ的那个variational perspective

然后MJ这篇文章还基于了他的同事的工作［6］，我觉得因为［1］有boyd和candes，［5］有MJ，［6］这篇文章虽然有大牛peter但是关注的人却很少

他把上面这一套加速的框架推广到了bregman方法上

［2］还推广到了坐标下降，newton类算法［坐标下降这个其实是自然，就是一个类似蒜子分裂的想法吧

张志华老师最近还有一系列工作用nesterov做到了newton类算法里

然后随机的分析方法就是

基本的motivation是最简单的梯度下降

x_{k+1}=x_{k}-\Delta t\nabla f(x_k)+\sqrt{\Delta t}\eta_k,\eta_k\sim N(0;I)

可以理解成在simulate这个sde \dot X = -\nabla f(X)+dW_t

今年nips有工作把加速的框架放进到这个随机的版本里了，这里不提

我更想说的是

这个sde \dot X = -\nabla f(X)+dW_t 最后收敛到gibbs分布

所以这里就把贝叶斯采样和优化算法联系起来了，这样也能理解一个著名的结果sgd会“train faster generalize better”，因为贝叶斯会采样到flat的minima，所以会更加robust

不过这个是极限情况了

在有限时间的时候王立威老师做了有限时间sgld的generalize的bound

［1］Su W, Boyd S. A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[C]// International Conference on Neural Information Processing Systems. MIT Press, 2014:2510-2518.

http://www.jmlr.org/papers/volume17/15-084/15-084.pdf

［2］Yang L F, Arora R, Braverman V, et al. The Physical Systems Behind Optimization Algorithm.

https://arxiv.org/pdf/1612.02803

［3］Jin C, Ge R, Netrapalli P, et al. How to Escape Saddle Points Efficiently

［4］Jin C, Netrapalli P, Jordan M I. Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent. 2017.

［5］ A. Wibisono, A. Wilson, and M. I. Jordan. A variational perspective on accelerated methods in
optimization. Proceedings of the National Academy of Sciences, 133, E7351-E7358, 2016.

［6］Bartlett P L, Bartlett P L, Bartlett P L. Accelerated mirror descent in continuous and discrete
time[C]// International Conference on Neural Information Processing Systems. MIT Press, 2015:2845-
2853.