Can Algorithms Collaborate? The Replica Exchange Method and Its Spectral Gap
发布时间：2021年03月18日
浏览次数：5464
发布者: Xiaoni Tan
主讲人： Xin Tong (National University of Singapore)
活动时间： 从 2021-03-23 16:00 到 17:00
场地： Online
Abstract: Gradient descent (GD) is known to converge quickly for convex objective functions, but it can be trapped at local minima. On the other hand, Langevin dynamics (LD) can explore the state space and find global minima, but in order to give accurate estimates, LD needs to run with a small discretization step size and weak stochastic force, which in general slows 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. We will further explain how does replica exchange method improve LD’s spectral gap using Poincare type of inequality.
Zoom Meeting number: 640 9204 6894
Passcode: 128410
