# Replica Exchange for Non-Convex Optimization

arXiv: https://arxiv.org/abs/2001.08356 · HTML: https://mlsanity.com/paper/2001.08356/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2020.

## Built on by (most cited first, 11 of 11)

- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization](https://mlsanity.com/paper/2204.05923/) (2022)
- [Active Learning with Bayesian Multi-Fidelity Laplace Neural Operators for Oscillatory Parametric PDEs](https://mlsanity.com/paper/2502.00550/) (2025)
- [Can We Do Better Than Random Start? The Power of Data Outsourcing](https://mlsanity.com/paper/2205.08098/) (2022)
- [Flatness-Aware Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2510.02174/) (2025)
- [Solving Integer Linear Programming with Parallel Tempering](https://mlsanity.com/paper/2605.29366/) (2026)
- [Shield-Loco: Shielding Locomotion Policies with Predictive Safety Filtering](https://mlsanity.com/paper/2606.07193/) (2026)
- [Fast PAC Global Optimization via Restarted Langevin: Exploration, Exploitation, and Degenerate Cooling](https://mlsanity.com/paper/2609.06196/) (2026)
- [Mode Coverage in Normalizing Flow Boltzmann Generators via Log-Ratio Variation](https://mlsanity.com/paper/2609.09473/) (2026)

## Abstract (arXiv)

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 and their non-swapping variants. 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 also study non-swapping variants of the algorithm, which achieve similar performance. We further verify our theoretical results through some numerical experiments and observe superior performance of the proposed algorithm over running GD or LD alone.