基于惯性动力系统的加速梯度算法

李 春 凯

(北京邮电大学 理学院， 北京 100876)

近年来，优化算法广泛应用于机器学习领域，对于求解大规模的问题，Hessian矩阵的计算和存储成本大，因此一阶梯度算法再一次回归主流.对连续时间下的常微分方程(Ordinary differential equation，ODE)与离散迭代算法建立联系，获取加速梯度算法引起越来越多的关注.

本文针对二阶的ODE 采用不同的离散格式，得到了加速梯度算法.

1 研究方法

本文考虑无约束最优化问题：

(1)

其中：f是光滑的凸函数.最基础的一阶梯度算法是梯度下降法(Gradient decent method，GD):

xk+1=xk-sf(xk),

(2)

其中:x0是初始点，s是步长.在一阶优化算法的框架下，是否存在改进GD收敛速率的算法是一个微妙而重要的问题.

1.1 动量方法

动量方法是指迭代过程中在仅使用一阶梯度信息的基础上加入前一步的迭代信息的一种方法.现代对于这种扩展的一阶算法的研究可以追溯到Polyak[1-2]，他在GD 的基础上加入动量项(xk-xk-1)，得到重球方法(Heavy-Ball):

yk+1=xk-sf(xk)，xk+1=yk+1-α(xk-xk-1)(3)

其中:α>0是动量系数.重球方法在最小值附近比GD能获得更快的局部收敛速率，但它通常并不能保证全局加速.而且Lessard[3]证明了即使对于强凸函数，由于步长的选择，重球方法并不能保证收敛性.

另外一种重要的动量方法是Nesterov[4-5]提出的Nesterov加速梯度算法(Nesterov’s accelerated gradient algorithm，NAG),当目标函数f为强凸函数时，迭代形式为：

(4)

(5)

1.2 连续时间ODE

近年来，通过连续时间的ODE来分析加速梯度算法越来越受到人们的关注.特别是Su等人[6]表明，假设目标函数f为凸函数，当s→0时，NAG可收敛到一个关于时间t的连续时间ODE:

(6)

Su等人通过构造合适的连续时间下的Lyapunov函数，证明了在连……