Regime-Switching Langevin Monte Carlo Algorithms

Xiaoyu Wang, Yingli Wang, Lingjiong ZhuarXiv 2025 · DOI · arXiv

Abstract

This paper introduces a novel family of Langevin Monte Carlo (LMC) algorithms where key parameters—specifically stepsize and friction—switch dynamically according to a hidden Markov chain. By leveraging the theory of regime-switching stochastic differential equations (RS-SDEs), we provide rigorous convergence guarantees for these algorithms. We demonstrate that these "jumping" parameters are more than a heuristic; they provide a formal framework for accelerated sampling, particularly in the case of kinetic Langevin dynamics.

Introduction

Sampling from complex probability distributions is a foundational task in Bayesian machine learning. While Langevin Monte Carlo (LMC) and its kinetic (underdamped) variant (KLMC) are standard tools, they typically rely on fixed parameters. In the optimization literature, varying the learning rate through cyclic or random schedules is known to help models escape local minima and improve generalization. However, in the context of sampling, haphazardly varying parameters can prevent the algorithm from converging to the correct target distribution. This research bridges the gap between the empirical success of varying parameters and the mathematical rigor required to ensure convergence to the desired Gibbs distribution.

The Regime-Switching Framework

We propose three primary algorithms inspired by Regime-Switching Stochastic Differential Equations (RS-SDEs). In these models, the system's parameters are governed by a Continuous-Time Markov Chain (CTMC), allowing the algorithm to transition between different discrete states or "regimes."

  1. RS-LMC (Regime-Switching Langevin Monte Carlo): The standard LMC algorithm where the stepsize ($\eta$) switches between discrete values.
  2. RS-KLMC (Regime-Switching Kinetic LMC): The kinetic version, incorporating a velocity term for momentum, where the stepsize switches between regimes.
  3. FRS-KLMC (Frictional-Regime-Switching Kinetic LMC): A specialized variant where the friction coefficient ($\gamma$) switches between regimes.

This framework provides the first formal mathematical analysis of random stepsizes in sampling, using the 2-Wasserstein distance ($W_2$) to quantify the rate at which the distribution of samples converges to the true target.

Theoretical Convergence and Complexity

A central contribution of this work is the derivation of iteration complexity for each algorithm under the assumption of $m$-strongly convex potential functions. Our analysis reveals that the speed of convergence is intrinsically tied to the "spectral gap" of the underlying Markov chain; a larger gap facilitates more efficient switching and faster convergence.

Key theoretical results include:

  • RS-LMC: Achieves a complexity of $O(\epsilon^{-2} \log(1/\epsilon))$ with a linear dependence on dimension $d$.
  • RS-KLMC: Improves complexity to $O(\epsilon^{-1} \log(1/\epsilon))$ with a square root dependence on dimension $\sqrt{d}$.
  • FRS-KLMC: Provides the most significant acceleration, reaching a complexity of $O(\epsilon^{-1/2} \log(1/\epsilon))$.

Notably, the friction-switching variant (FRS-KLMC) offers a superior theoretical rate compared to both standard LMC ($O(\epsilon^{-2})$) and standard KLMC ($O(\epsilon^{-1})$).

Empirical Evaluation

We validated the proposed algorithms across several Bayesian tasks, comparing them against standard non-switching counterparts.

Synthetic and Real-World Datasets

  • Synthetic Bayesian Linear Regression: Used to confirm theoretical convergence rates and the influence of the spectral gap.
  • Bayesian Logistic Regression: Tested on the Iris dataset (150 samples, 4 features) and the MAGIC Gamma Telescope dataset (19,020 samples, 10 features).

Key Findings

Experiments demonstrated that regime-switching enhances both speed and stability. On the small-scale Iris dataset, standard Stochastic Gradient Langevin Dynamics (SGLD) often exhibited erratic behavior, whereas the regime-switching version (RS-SGLD) maintained consistent performance. In larger-scale tests on the MAGIC dataset, momentum-based regime-switching algorithms (RS-SGHMC and FRS-SGHMC) consistently outperformed their static counterparts in both accuracy and convergence velocity.

Discussion and Limitations

While regime-switching provides a powerful tool for sampling, several considerations remain for future research. Our current theoretical guarantees rely on the assumption of strong convexity, which may not hold in the non-convex landscapes typical of deep learning. Additionally, the effectiveness of these algorithms depends on the selection of hyperparameters, such as the specific values of the regimes and the transition rates between them. Future work will explore extending these guarantees to non-convex potentials and investigating generalized regime-switching where the target distribution itself may evolve.

Summary updated

Abstract

Langevin Monte Carlo (LMC) algorithms are popular Markov Chain Monte Carlo (MCMC) methods to sample a target probability distribution, which arises in many applications in machine learning. Inspired by regime-switching stochastic differential equations in the probability literature, we propose and study regime-switching Langevin dynamics (RS-LD) and regime-switching kinetic Langevin dynamics (RS-KLD). Based on their discretizations, we introduce regime-switching Langevin Monte Carlo (RS-LMC) and regime-switching kinetic Langevin Monte Carlo (RS-KLMC) algorithms, which can also be viewed as LMC and KLMC algorithms with random stepsizes. We also propose frictional-regime-switching kinetic Langevin dynamics (FRS-KLD) and its associated algorithm frictional-regime-switching kinetic Langevin Monte Carlo (FRS-KLMC), which can also be viewed as the KLMC algorithm with random frictional coefficients. We provide their 2-Wasserstein non-asymptotic convergence guarantees to the target distribution, and analyze the iteration complexities. Numerical experiments using both synthetic and real data are provided to illustrate the efficiency of our proposed algorithms.
BibTeX
@misc{wang2025regime,
  author = {Xiaoyu Wang and Yingli Wang and Lingjiong Zhu},
  title = {{Regime-Switching Langevin Monte Carlo Algorithms}},
  year = {2025},
  eprint = {2509.00941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.00941},
}
Figure