Particle samplers move a cloud of points until the cloud looks like draws from a target distribution. The standard local versions get stuck: when the target has several high-probability regions ("modes") separated by low-probability gaps, particles that follow local gradients stay in whichever mode they reach first. There is a known fix in principle. If each particle's motion is driven by the inverse of the target's Laplacian, an operator whose slowest eigenfunctions encode which mode a point belongs to, then mass moves between modes at a rate that does not depend on how deep the gaps are. In practice this fix has been confined to toy dimensions, because it needs an eigendecomposition that is either computed on a grid or recomputed densely over all particles at every step.
We propose to make this sampler cheap enough to run with many particles. The approach rests on two moves taken from numerical linear algebra and control. First, replace the dense eigendecomposition with a Chebyshev polynomial filter: a fixed-degree sequence of sparse matrix–vector products on a nearest-neighbour particle graph. Second, because particles move only slightly between steps, start each step's filter from the previous step's eigenvectors rather than from scratch. The new risk this creates is that a warm start can lock the sampler onto an outdated picture of the modes. Handling that risk, and showing that temporal reuse also lowers the noise of the particle velocity field, is the core of the work.
Core Claim
Laplacian-adjusted Wasserstein gradient descent (LAWGD) is a particle method from SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence. It uses the kernel $K_\pi=\mathcal{L}_\pi^{-1}$, where $\mathcal{L}_\pi$ is the generator of Langevin dynamics for target $\pi$, and its convergence is scale-invariant across multimodal mixtures. Diffusion map particle systems for generative modeling (DMPS) builds an empirical version of this generator from pairwise distances between particles and truncates it to its leading eigenpairs. DMPS has been demonstrated only up to $d\le 15$, and it re-solves the eigenproblem at each step. Our claim is that the leading eigenpairs of the particle-graph generator can be tracked across sampler steps by warm-started Chebyshev subspace filtering with a few matrix–vector products per step. Tracking in this way gives three things. Per-step cost becomes near-linear in the number of particles. The velocity field has lower variance than a from-scratch recomputation, because the warm-started subspace acts as a time-average over the noisy finite-sample operator. With a simple guard, the tracked subspace still detects newly discovered modes rather than staying locked to the old ones.
Written out, at sampler step $t$ the particles $x^t_1,\dots,x^t_n$ define a sparse reweighted kernel matrix $L_t$ approximating $\mathcal{L}_\pi$. We maintain a block $V_t\in\mathbb{R}^{n\times m}$ that approximates its $m$ smallest nontrivial eigenvectors. The update is
$$V_{t+1}=\mathrm{RR}\big(p_D(L_{t+1})\,[\,V_t,\ G_t\,]\big),$$
where $p_D$ is a degree-$D$ Chebyshev polynomial that amplifies the low end of the spectrum, $G_t$ is a small block of fresh random vectors (the guard), and $\mathrm{RR}$ is a Rayleigh–Ritz projection. Particle velocities then come from the Nyström extension of the tracked eigenpairs, which can be differentiated analytically. The degree $D$ is kept small, in the range of 2 to 10, so each sampler step costs $O(nk(m+q)D)$ for a $k$-nearest-neighbour graph and $q$ guard vectors.
Where this sits
The mechanism is borrowed directly from Accelerating Eigenvalue Dataset Generation via Chebyshev Subspace Filter. SCSF warm-starts a Chebyshev filtered eigensolver across a sorted sequence of related PDE operators and reports up to 3.5× speedup and 5–50% fewer iterations. Its operators, however, are static, Hermitian and fixed in advance. In our setting the operator is produced by the sampler's own state, changes every step, and is a random matrix. Two other papers supply the matrix-function machinery. DASH uses Clenshaw–Chebyshev recurrences and power-iteration spectral scaling on GPUs, but restarts its solvers each optimizer step. Stochastic Chebyshev Gradient Descent for Spectral Optimization shows that fixed-degree truncation biases stochastic optimization and that randomized degrees with an optimal distribution remove the bias. We reuse that idea as an option for the filter degree.
The motivation comes from the mode-entrapment literature. Annealed Stein Variational Gradient Descent recovers modes by scheduling the driving force, which requires empirical tuning. Understanding the Variance Collapse of SVGD in High Dimensions shows that SVGD's particle variance shrinks as $O(n/d)$ in high dimensions. Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics shows that spectral preconditioning rescues annealed Langevin dynamics up to $d=75$, but only when all the relevant matrices share one eigenbasis. Score Operator Newton transport obtains global transport from elliptic PDE solves that stop scaling beyond $d\approx 3$.
One constraint has to be stated plainly. Matrix–vector tricks fix the computational cost of DMPS in $n$. They do not fix the statistical cost of estimating a generator from samples in high $d$. Whether the low eigenfunctions, which are what separate modes, remain estimable at $d=50$–$100$ is something we test, not something we assume.
Research Program
We first build the operator. It is a sparse $k$-nearest-neighbour kernel on the particles, density-normalized and reweighted with the known unnormalized $\log\pi$ so that it approximates the target's Langevin generator rather than the generator of the current particle distribution. Neighbour lists are themselves warm-started by re-querying around the previous neighbours. Spectral bounds for the Chebyshev map are also warm-started, using a few power-iteration steps seeded from the previous step's top vector. This targets the "inaccurate bounds cause divergence" weakness noted for polynomial methods.
The filter and the guard are the second component. We study three things here: how many filter applications per sampler step are needed (the sampler can tolerate stale eigenvectors, so possibly one); how many guard vectors are needed; and a lock-in test. The lock-in test is principled. A newly populated mode creates a new near-zero eigenvalue of $L_t$. Because $p_D$ amplifies the low end of the spectrum, the guard vectors pick up that direction at a rate set by the filter's amplification ratio, so detection lag can be predicted from the spectral gap. We compare detection lag with and without guards.
The third component is variance analysis. We measure the step-to-step variance of the velocity field under warm-started tracking and under a fresh solve at the same particle positions. We also characterize the bias–variance trade between lag and smoothing as a function of step size, analogous to an exponential moving average. As an ablation, we test whether randomized Chebyshev degrees in the style of Han et al. change the stationary particle distribution relative to a fixed small degree.
The fourth component is high-dimensional behaviour. We track particle variance against $d$ to see whether the inverse-Laplacian kernel avoids SVGD's $O(n/d)$ collapse, and how many particles are needed for the low eigenfunctions to separate modes.
Baselines
The naive reference point is the same sampler with a cold start: the same graph, Chebyshev filter and particle update, but the subspace re-initialized randomly at every step and filtered to the same residual tolerance. This isolates the warm start. Beating it means equal sample quality (MMD, mode counts) at substantially lower wall-clock time, plus a measurably lower step-to-step velocity variance. Both arms get identical particle counts, step sizes and hardware.
The strongest exact reference on the same idea is DMPS with dense eigendecomposition each step (Diffusion map particle systems for generative modeling), which reports 6.21 s versus 1633 s for score-based generative models on its Arc problem. Our method should match DMPS sample quality within seed noise at small $n$. It should also continue to run at particle counts where dense eigendecomposition becomes too expensive. We report the crossover $n$ honestly.
The strongest mode-discovery competitor is Annealed SVGD (Annealed Stein Variational Gradient Descent), which captures all 16 modes of the 4×4 grid where standard SVGD finds 4. For its 100-dimensional, 5-component mixture the file contains no numeric MMD, so no reported result was found on Lacuna for A-SVGD MMD at $d=100$, and we will rerun it. Damped SVGD (Understanding the Variance Collapse of SVGD in High Dimensions) covers variance collapse. For that paper we take as reference its finding that MMD-descent holds particle variance near 1.0 regardless of dimension. Each baseline gets the same particle budget, the same number of target-score evaluations, and an equal hyperparameter search budget: schedules and $\gamma$ for A-SVGD, damping $\lambda$ for Damped SVGD, and $k$, $m$, $q$, $D$ for ours. Beating them means full mode recovery with correct relative weights, at lower MMD or energy distance and no annealing schedule.
Two ablations isolate the key ingredients. The first removes the guard vectors, to show the lock-in failure. The second replaces subspace tracking with a single-vector warm-started conjugate-gradient solve of $L_t u=r_t$, to test whether eigen-truncation matters.
Why not just…?
Why not just recompute the dense eigendecomposition every few steps instead of every step? Lazy recomputation is a real threat when $n$ is a few thousand, because stale eigenvectors may be good enough between refreshes. We include it as a baseline swept over refresh intervals. Our method wins only if it achieves equal quality at lower cost once $n$ is large, or if stale refreshes miss newly found modes in the sequential-target experiment. If neither happens, the warm-started filter offers nothing over lazy recomputation, and we will say so.
Why not just warm-start conjugate gradient on one linear system per step? The χ²-flow velocity can be written as the gradient of $L^{-1}$ applied to a single residual vector, so a warm-started Krylov solve is simpler than tracking a subspace. Two arguments favour the subspace. The truncation to $m$ eigenpairs is the regularizer DMPS relies on for finite-sample stability. The Nyström gradient needs eigenfunctions rather than node values. Neither argument has been tested in the file's sources, so this is run as a head-to-head ablation. If CG matches on quality and cost, the contribution narrows to the warm-start and graph construction, with CG as the solver.
Why not just use annealed SVGD or annealed Langevin and skip the operator entirely? A-SVGD already recovers 16 of 16 grid modes, and preconditioned annealed Langevin scales to $d=75$. However, the first needs a tuned schedule, and the second needs a known co-diagonalizable preconditioner and fails beyond $d=10$ without it, where flat annealed Langevin dynamics did not reach target accuracy within 20,000 steps (Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics). Our sampler learns the slow mode structure from the particles. The experiments below test whether that advantage holds up in practice, in particular on unequal mode weights, where schedule-driven methods tend to miscalibrate.
Why not just add Langevin noise? Barrier-crossing times for noisy local dynamics grow exponentially with barrier height. We include stochastic gradient Langevin dynamics on the mixtures as a sanity floor, not as a serious competitor.
Proposed Experiments
We use the benchmarks reported in the A-SVGD paper: the 1D five-peak mixture, the 4×4 grid, the irregular-weight 2D mixture, and the 100-dimensional five-component mixture. We add the bimodal Gaussian mixtures from $d=1$ to $75$ used for preconditioned annealed Langevin dynamics, evaluated with its $k$-nearest-neighbour KL estimator, and the two-moons and hyper-semisphere ($d\le 15$) problems from DMPS. As a real posterior, we use Bayesian logistic regression and the two-layer, 100-unit Bayesian neural network from Ba et al., with minibatch scores so that gradient noise is present. Metrics are mode count, mode-weight error, MMD, energy distance, particle variance against $d$, wall-clock time and matrix–vector products per step, and velocity-field variance across steps.
Three checks are decisive. The first is the warm-start check: at matched sample quality, warm-start versus cold-start matrix–vector products per step. If the saving falls below SCSF's lower end of roughly 5% fewer iterations, the temporal-reuse claim fails. The second is the lock-in check, on a sequence of targets in which a new mode appears partway through, as in streaming Bayesian updating. We measure how many steps pass before particle mass reaches the new mode, comparing guarded tracking, unguarded tracking, lazy dense refresh and A-SVGD with a cyclical schedule. Unguarded tracking should lag or fail, while guarded tracking should match dense refresh within a lag predicted by the filter's amplification ratio. The third is the dimension check: mode recovery and particle variance at $d=25, 50, 100$ with $n$ scaled up. This shows where the empirical generator stops separating modes. If that happens near DMPS's $d\approx 15$ regardless of $n$, the bottleneck is statistical, and the proposal's contribution is limited to speed at moderate dimension. That would be a useful negative result for the whole inverse-Laplacian line of work.
References
- SVGD as a kernelized Wasserstein gradient flow of the chi-squared divergence
- Diffusion map particle systems for generative modeling
- Accelerating Eigenvalue Dataset Generation via Chebyshev Subspace Filter
- DASH: Faster Shampoo via Batched Block Preconditioning and Efficient Inverse-Root Solvers
- Stochastic Chebyshev Gradient Descent for Spectral Optimization
- Annealed Stein Variational Gradient Descent
- Understanding the Variance Collapse of SVGD in High Dimensions
- Dimension-Free Multimodal Sampling via Preconditioned Annealed Langevin Dynamics
- Score Operator Newton transport