Hamiltonian Descent Algorithms for Optimization: Accelerated Rates via Randomized Integration Time
Qiang Fu, Andre Wibisono
我们研究用于优化的Hamiltonian流(HF-opt),它模拟了Hamiltonian动态一段时间的集成时间,并将速度重置为0以降低目标函数;这是用于采样的Hamiltonian Monte Carlo算法的优化模拟。 在较短的集成时间中,HF-opt具有与梯度下降相同的收敛率,用于最小化强弱凸函数。 我们表明,通过随机化HF-opt中的集成时间,由此产生的随机哈密尔顿流(RHF)在连续时间内实现加速收敛率,类似于加速梯度流的速率。 我们研究RHF作为随机汉密尔顿梯度下降(RHGD)算法的离散时间实现。 我们证明RHGD实现了与Nesterov的加速梯度下降(AGD)相同的加速收敛率,以最小化平滑强弱凸函数。 我们提供数值实验来证明RHGD在所有设置中与经典的加速方法(如AGD)具有竞争力,并在某些机制中优于它们。
We study the Hamiltonian flow for optimization (HF-opt), which simulates the Hamiltonian dynamics for some integration time and resets the velocity to 0 to decrease the objective function; this is the optimization analogue of the Hamiltonian Monte Carlo algorithm for sampling. For short integration time, HF-opt has the same convergence rates as gradient descent for minimizing strongly and weakly convex functions. We show that by randomizing the integration time in HF-opt, the resulting randomize...