Nonlocal Hamiltonian Dynamics on Sparse Lévy Graphs: Spectral Analysis and Multimodal Sampling
Authors: Miaolei Zheng, Ting Gao, Jinqiao Duan
Organizations: School of Mathematics, Sun Yat-sen University, Guangzhou 510275, China · School of Sciences, Great Bay University, Dongguan 523000, China · Guangdong Provincial Key Laboratory of Mathematical and Neural Dynamical Systems, Great Bay University, Dongguan 523000, China · School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, China · Center for Mathematical Science, Huazhong University of Science and Technology, Wuhan 430074, China · Steklov-Wuhan Institute for Mathematical Exploration, Huazhong University of Science and Technology, Wuhan 430074, China
We develop a sparse graph method for transporting probability mass toward multimodal target distributions through damped nonlocal Hamiltonian dynamics. The formulation combines logarithmic-mean mobility with symmetric Lévy-type interaction weights, coupling the evolving density to an edge momentum field. A graph constructed from nearest-neighbor connections and sampled long-range edges provides direct mass exchange between spatially separated regions. Once the graph is constructed, the density evolution is deterministic, and each update costs linear in the number of nodes and the long-range sampling budget. Linearization around the target distribution yields a damped oscillator governed by a weighted graph Laplacian. Its spectrum characterizes the interaction between nonlocal connectivity and inertia, with the Lévy exponent alpha tuning the nonlocal connectivity: the spectral gap determines the optimal asymptotic damping, while the largest eigenvalue governs the time-step stability. Experiments on synthetic multimodal distributions demonstrate improved mode balance and more stable mode coverage relative to first-order and MCMC baselines. The resulting framework provides a sparse implementation of nonlocal inertial density transport for sampling problems with low-dimensional spatial structure.
Figures & tables
Figure 3.1 : Convergence analysis of the discrete fractional operator. (a) Numerical illustration of the m−1/2 scaling for the fixed-function sparse estimator. (b)–(c) Pointwise absolute errors of the truncated full-graph approximation for α=0.8 and α=1.0 . The dashed lines indicate the reference slopes 2−α .
Figure 4.1 : Sampling results (kernel density estimation (KDE), top) and transport fields (bottom) for different fractional orders α=0.3,0.7,1.5,1.8 (from left to right).
Figure 4.2 : Evolution of KL divergence and Hamiltonian over time for the banana distribution with different fractional orders α .
α
Mode
Long Jump Ratio
Transport Length
0.10
Nonlocal
0.145
1.118
0.30
Nonlocal
0.129
0.980
0.50
Nonlocal
0.093
0.828
0.70
Nonlocal
0.069
0.729
1.00
Nonlocal
0.031
0.571
1.50
Nonlocal
0.016
0.451
Table 4.1 : Nonlocal transport characteristics on the Banana distribution.
Figure 4.3 : First-order nonlocal gradient flow sampling results (KDE) on three target distributions with α=1.0 . (a) Single ring, (b) banana, (c) four-Gaussian-mixture.
Figure 4.4 : Spectral and damping analysis of the nonlocal flow. (a) KL divergence of the second-order dynamics for different damping coefficients at α=1.0 . (b) Spectral gap λ1 computed from the realized sparse graphs. (c) Corresponding linearized modal mixing-time predictions for the first- and second-order flows with ε=10−3 .
Figure 4.5 : Linearized modal relaxation predictions obtained from the actual sparse-graph spectral gaps for α=0.1,0.5,1.0,1.9 . The tolerance is ε=10−3 , and vertical dotted lines denote the predicted settling times.
Figure 4.6 : Sampling results (KDE) on the single ring distribution π∝e−2(r−3)2 . The proposed method ( α=1.0 ) provides broader coverage than the tested baselines in this experiment.
Figure 4.7 : Sampling results (KDE) on the Banana distribution. The proposed method (α=1.0) provides broader coverage than the tested baselines in this experiment.
Figure 4.8 : Sampling results (KDE) on the four-Gaussian-mixture distribution π=41∑N(μi,0.25I2) . The proposed method (α=1.0) provides broader coverage than the tested baselines in this experiment.
Figure 4.9 : Equal-wall-clock comparison on the four-Gaussian-mixture target. All methods use a 40 -s computational budget; curves show the mean over five independent seeds and shaded regions denote one standard deviation. The proposed-method timing includes its one-time graph setup, while the particle-baseline timing includes warm-up. (a) KL divergence. (b) Mode-weight L1 error.
Figure 4.10 : Mode occupancy comparison. Our method ( α=1.0 ) achieves balanced sampling in both cases.
Four-Gaussian-mixture
Banana
Method
M1
M2
M3
M4
Right
Left
Target
25.0
25.0
25.0
25.0
50.0
50.0
Proposed method ( α=1.0 )
25.1
25.0
25.0
24.9
50.0
50.0
MCMC
34.68
15.54
21.50
28.28
100.0
0.0
MALA
24.74
28.28
30.14
16.84
100.0
0.0
ULD
0.00
0.00
100.00
0.00
100.0
0.0
Table 4.2 : Mode occupancy ratios (%) on Four-Gaussian-Mixture and banana.
Figure 4.11 : MNIST latent space sampling results for different fractional orders α . Top row: KDE-estimated densities. Bottom row: scatter plots of sampled points overlaid with true data (gray points).
Figure 4.12 : Ramachandran plots of alanine dipeptide sampling for different fractional orders α . The target distribution exhibits two major metastable states: C7eq ( ϕ≈−80∘,ψ≈80∘ ) and C7ax ( ϕ≈80∘,ψ≈−80∘ ).
Figure 4.13 : (a) KL divergence evolution on the two-dimensional MNIST latent space for different α ; (b) final KL as a function of α for the alanine dipeptide system.
We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.
Nikolaos Makras, Sotirios Sabanis
School of Mathematics, University of Edinburgh, UK · National Technical University of Athens, Greece · Athena/Archimedes Research Centre, Greece
We address the problem of efficiently sampling multimodal probability distributions, where standard Markov Chain Monte Carlo methods often suffer from poor mixing and mode trapping. To mitigate these issues, we propose Gradient-free Riemannian Langevin Sampler (GRiLS), a novel proposal that improves exploration without requiring gradient evaluations of the target density. Our approach introduces a Riemannian metric which reshapes the local geometry in order to facilitate transitions across modes. The resulting gradient-free MCMC algorithm is particularly suitable for complex, computationally expensive targets where derivatives are unavailable or impractical. The GRiLS proposal requires knowing the mean and covariance of the target density, which we estimate using an ensemble of interacting particles. Empirical results on multimodal benchmarks demonstrate that GRiLS achieves improved mixing compared to existing gradient-based and gradient-free MCMC approaches.
Ricardo Baptista, Olivier Zahm
Department of Statistical Sciences, University of Toronto, Canada · UGA, Inria, CNRS, Grenoble INP*, LJK, 38000 Grenoble, France
There has been a proliferation of sampling algorithms based on Wasserstein gradient flows (WGF) and forward-only diffusion processes (FODP), often accompanied by theoretical guarantees of exponentially fast convergence to the target distribution. These guarantees are frequently interpreted as evidence that such methods can efficiently sample complex multimodal distributions, often supported by empirical results. In this work, we argue that this interpretation is fundamentally misleading. By invoking the Jordan-Kinderlehrer-Otto (JKO) scheme and Otto calculus, we establish that the canonical WGF sampling dynamics and overdamped forward diffusion share the same density evolution and therefore inherit the same metastability and slow-mixing phenomena long understood in nonequilibrium statistical physics. We analyze this family of samplers using two complementary tools -- spectral analysis and mean first-passage time (MFPT) analysis -- and show that well-separated multimodality can induce exponentially long mixing times associated with small spectral gaps and rare inter-mode transitions. For the commonly adopted log-linear annealing schedule studied here, we find that introducing intermediate distributions does not remove the exponential scaling of the total transport time. The limitation is structural rather than implementation-specific: purely local, gradient-driven transport mechanisms can require exponentially long times to transport probability mass across well-separated modes. We argue that this represents a fundamental limitation of WGF- and FODP-based sampling in their standard forms, and motivates future development of fundamentally nonlocal mechanisms for efficient multimodal sampling.
Daniel McBride, Pratik Khandagale, Cristina Garcia-Cardona +1
Los Alamos National Laboratory, Los Alamos, NM 87545, USA