Windowed thinning and query complexity for the bouncy particle and Zigzag samplers

• URL: http://arxiv.org/abs/2607.28413v1
• Date: Thu, 30 Jul 2026 15:59:25 GMT
• Title: Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
• Abstract summary: We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process.<n>For total-variation error $varepsilon$, the expected query counts are $O(1/2d,(dlog+logfrac1varepsilon))$ gradient queries for the bouncy particle sampler and $O(d1/4(dlog+logfrac1varepsilon))$ full-gradient equivalents for Zigzag.
• Score: 5.726854405157353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Let $μ(d x)\propto e^{-U(x)} d x$ on $\R^d$, where $U$ is $m$-strongly convex and $L$-smooth, and denote by $κ=L/m$ the condition number. We consider windowed thinning, an exact simulation method for the bouncy particle sampler and the coordinate Zigzag process. The method divides a trajectory into deterministic windows and uses a gradient evaluation at the beginning of each window to construct a tractable local envelope for the event rate. Combining this construction with quantitative mixing estimates and finite-time bounds on the expected numbers of bounces and flips yields query complexity guarantees from a Gaussian cold start. For total-variation error $\varepsilon$, the expected query counts are $O(κ^{1/2}d\,(d\logκ+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(κd^{1/4}(d\logκ+\log\frac1\varepsilon))$ full-gradient equivalents for Zigzag, where $d$ coordinate-partial queries count as one equivalent.

Related papers

• Smoothed Picard Hamiltonian Monte Carlo [15.748402989364804]
  We develop a new low-accuracy sampler, called emphsmoothed Picard Hamiltonian Monte Carlo, which combines Gaussian smoothing, Picard iteration, and higher-order discretization.<n>This produces a warm start for the proximal bouncy particle sampler, introduced in a companion work, leading to a high-accuracy log-concave sampler complexity.
  arXiv  Detail & Related papers  (2026-09-07T01:13:28Z)
• Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler [15.748402989364804]
  We study the problem of sampling from $(mathrmdx)propto e-V(x),mathrmdx$ on $mathbbRd$, where $V$ is $$-strongly convex and $$-smooth, and write $:=/$.<n>We design and analyze the Proximal Bouncy Particle Sampler (Proximal BPS), a new sampler that combines ideas from the proximal sampler and the bouncy particle sampler.
  arXiv  Detail & Related papers  (2026-09-07T01:13:27Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• A proximal gradient algorithm for composite log-concave sampling [9.11122093402205]
  We propose an algorithm to sample from composite log-concave distributions over $mathbbRd$, i.e., densities of the form $propto e-f-g$.<n>We further extend our results to cases where (1) $$ is non-log-concave but satisfies a Poincaré or log-Sobolev inequality, and (2) $f$ is non-smooth but Lipschitz.
  arXiv  Detail & Related papers  (2026-05-12T17:48:09Z)
• Zeroth-order log-concave sampling [2.61072980439312]
  We study the zeroth-order query complexity of log-concave sampling using membership oracles.<n>We propose a simple variant of the proximal sampler that achieves complexity with matched R'enyi orders between the initial warmness and output guarantee.
  arXiv  Detail & Related papers  (2025-07-24T01:31:49Z)
• On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
  We study the problem of sampling from a $d$-dimensional distribution with density $p(x)propto e-f(x)$, which does not necessarily satisfy good isoperimetric conditions.<n>We show that for a wide range of parameters, sampling is strictly easier than optimization by a super-exponential factor in the dimension $d$.
  arXiv  Detail & Related papers  (2025-02-10T06:54:16Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. We prove that the zigzag sampling algorithm achieves $varepsilon$ error in chi-square divergence with a computational cost equivalent to $Obigl.
  arXiv  Detail & Related papers  (2020-12-21T03:10:21Z)
• Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
  We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization.
  arXiv  Detail & Related papers  (2020-10-07T01:43:07Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.