Replica Exchange for Non-Convex Optimization
Replica Exchange for Non-Convex Optimization
复制标题
DOI：
--
复制
发表时间：
2020-01
期刊：
影响因子：
--
通讯作者：
Jing Dong;Xin T. Tong
中科院分区：
文献类型：
--
作者：
Jing Dong;Xin T. Tong
梯度下降（GD）是已知的凸目标函数的快速收敛，但它可以被困在局部极小值。另一方面，Langevin动力学（LD）可以探索状态空间并找到全局最小值，但为了给出准确的估计，LD需要以小的离散步长和弱的随机力运行，这通常会减慢其收敛速度。本文表明，这两个算法可以通过一个简单的交换机制，他们交换他们目前的位置，如果LD产生一个较低的目标函数“合作”。这个想法可以被看作是从抽样文献的副本交换技术的奇异极限。我们证明，假设目标函数在唯一全局最小值的邻域中是强凸的，该新算法以高概率线性收敛到全局最小值。通过用随机梯度代替梯度，并在交换机制中加入适当的阈值，我们的算法也可以用于在线设置。我们进一步验证了我们的理论结果，通过一些数值实验，并观察所提出的算法优于单独运行GD或LD的上级性能。
Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minimums. On the other hand, Langevin dynamics (LD) can explore the state space and find global minimums, but in order to give accurate estimates, LD needs to run with small discretization stepsize and weak stochastic force, which in general slow down its convergence. This paper shows that these two algorithms can "collaborate" through a simple exchange mechanism, in which they swap their current positions if LD yields a lower objective function. This idea can be seen as the singular limit of the replica exchange technique from the sampling literature. We show that this new algorithm converges to the global minimum linearly with high probability, assuming the objective function is strongly convex in a neighborhood of the unique global minimum. By replacing gradients with stochastic gradients, and adding a proper threshold to the exchange mechanism, our algorithm can also be used in online settings. We further verify our theoretical results through some numerical experiments, and observe superior performance of the proposed algorithm over running GD or LD alone.