优化算法新观点

2024/03/04

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

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

http://about.2prime.cn/DOPT.pdf

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

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

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

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

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

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

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

然后大家自己推一下也会发现，动量梯度下降会对应着 $\\ddot X +\\dot X +\ abla 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\ abla f(x_k)+\\sqrt{\\Delta t}\\eta_k,\\eta_k\\sim N(0;I)$

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

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

我更想说的是

这个sde $\\dot X=-\ abla 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.

上一篇：内存优化工具Wise Memory Optimizer v4.2.0 单文件版，支持win XP

下一篇：多地持续深化“放管服”改革释放新动能激发新活力

优化算法新观点

友情链接：