Can algorithms collaborate? The replica exchange method

Add to your list(s) Download to your calendar using vCal

• Xin Tong (National University of Singapore)
• Tuesday 04 August 2020, 14:00-15:00
• https://zoom.us/j/3264147316?pwd=S1ZZMS81UzRjRnp3NlFTcWFPOVpnZz09.

If you have a question about this talk, please contact Hong Duong.

Meeting ID: 326 414 7316 Password: 772020

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 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.

This talk is part of the Data Science and Computational Statistics Seminar series.

This talk is included in these lists:

• Data Science and Computational Statistics Seminar
• School of Mathematics events
• https://zoom.us/j/3264147316?pwd=S1ZZMS81UzRjRnp3NlFTcWFPOVpnZz09

Note that ex-directory lists are not shown.