Unverified 2026

Windowed Bouncy Particle Weight Sampler

Implementation & benchmark of arXiv:2607.28413 — Windowed thinning and query complexity for the bouncy particle and Zigzag samplers

Usefulness6/10

Difficulty6/10

Novelty7/10

Sampling Speedup Sample efficiency Stability Optimizer Sampling Training Probability Stochastic processes Convex analysis Dynamical systems Numerical analysis

Source paper: Windowed thinning and query complexity for the bouncy particle and Zigzag samplers arXiv:2607.28413 ⓘ · analyzed Aug 31, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace stepwise gradient evaluation in a Bouncy Particle sampler over neural-network parameters with deterministic windows. At the start of each window, compute one gradient and use smoothness to upper-bound the event intensity along the ballistic trajectory; candidate events are generated analytically from the integrated envelope and accepted using a gradient evaluation only at candidate locations. This gives an exact sampler under a certified global smoothness bound and a controllable approximate sampler when the bound is estimated adaptively.

Formulas

$$\mu(\mathrm{d}x)=Z^{-1}e^{-U(x)}\,\mathrm{d}x,\qquad mI_d\preceq\nabla^2U(x)\preceq LI_d.$$

$$x(t)=x+tv,\qquad \lambda(t)=\langle\nabla U(x+tv),v\rangle_+\le \bar\lambda(t):=\langle\nabla U(x),v\rangle_+ + Lt\|v\|^2.$$

$$\bar\Lambda(t)=\int_0^t\bar\lambda(s)\,\mathrm{d}s=at+\frac{1}{2}bt^2,\qquad a=\langle\nabla U(x),v\rangle_+,\quad b=L\|v\|^2.$$

$$t=\frac{-a+\sqrt{a^2+2b(-\log r)}}{b},\qquad \Pr(\text{accept candidate at }t)=\frac{\langle\nabla U(x+tv),v\rangle_+}{a+bt}.$$

Mathematical statement

The target is $\mu(\mathrm{d}x)=Z^{-1}e^{-U(x)}\,\mathrm{d}x$, where $x\in\mathbb{R}^{d}$, $U$ is the negative log posterior or loss energy, and $Z$ is a normalizing constant. The paper assumes $mI_d\preceq \nabla^2U(x)\preceq LI_d$, with strong-convexity constant $m>0$, smoothness constant $L>0$, and condition number $\kappa=L/m$. For position $x$, velocity $v$, and ballistic path $x(t)=x+tv$, the Bouncy Particle event intensity is $\lambda(t)=\langle\nabla U(x+tv),v\rangle_+$, where $a_+=\max(a,0)$. By $L$-smoothness, $\|\nabla U(x+tv)-\nabla U(x)\|\le Lt\|v\|$, hence $\lambda(t)\le\bar\lambda(t):=\langle\nabla U(x),v\rangle_+ + Lt\|v\|^2$ on a window. Its integrated envelope is $\bar\Lambda(t)=at+\tfrac12bt^2$, with $a=\langle\nabla U(x),v\rangle_+$ and $b=L\|v\|^2$. A candidate time is sampled by solving $\bar\Lambda(t)=-\log r$ for $r\sim\operatorname{Uniform}(0,1)$, yielding $t=(-a+\sqrt{a^2+2b(-\log r)})/b$. At the candidate, compute the true gradient and accept with probability $\lambda(t)/\bar\lambda(t)$. On acceptance, reflect the velocity using $v\leftarrow v-2\langle v,n\rangle n$, where $n=\nabla U(x)/\|\nabla U(x)\|$. Exactness requires a valid upper bound $L$; for neural networks, first use a certified bound for a convex head or an inflated empirical curvature estimate for an approximate variant.

Implementation notes

1. Integration point: apply this as a parameter-space sampler or optimizer for a neural-network parameter vector $\theta$, with $U(\theta)$ equal to a regularized training loss or negative log posterior. For the first implementation, restrict $\theta$ to the final linear classification head while keeping the feature extractor frozen; this makes logistic-loss smoothness easier to bound. Maintain position $\theta$, velocity $v$, window length $h$, and scalar smoothness bound $L$. 2. Pseudocode: compute $g=\nabla U(\theta)$, set $a=\max(\langle g,v\rangle,0)$, $b=L\|v\|^2$, and repeatedly draw $r$, solve $t=(-a+\sqrt{a^2+2b(-\log r)})/b$, and stop if $t>h$. Otherwise set $\theta_c=\theta+tv$, compute $g_c=\nabla U(\theta_c)$, set $\lambda=\max(\langle g_c,v\rangle,0)$, and accept with probability $\lambda/(a+bt)$. On acceptance reflect $v\leftarrow v-2(g_c^Tv/\|g_c\|^2)g_c$. If rejected, continue from $\theta_c$ with the residual window, or conservatively restart with a fresh gradient. At a window boundary set $\theta\leftarrow\theta+hv$ and recompute $g$. Refresh $v\sim\mathcal N(0,I)$ every fixed number of windows. 3. Compute from the mathematics: the quadratic envelope, inverse integrated hazard, and thinning acceptance ratio. Estimate empirically: $L$, event acceptance rate, effective sample size, and envelope violations. Log $\lambda/\bar\lambda$; any value above one indicates an invalid bound and should trigger envelope inflation, for example $L\leftarrow2L$. 4. First experiment: train only the last layer of a small MLP or ResNet-18 on MNIST or CIFAR-10. Compare windowed BPS against SGD, AdamW, and conventional small-step BPS at equal gradient-query budgets. Sweep $h$ and $L$. Success signals are fewer gradient evaluations per effective parameter sample, higher event acceptance than stepwise thinning, and comparable validation loss or posterior predictive accuracy at equal gradient-query count. A secondary full-network test should report whether local envelope violations remain rare and whether the method improves loss descent per gradient evaluation.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.