Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler

• URL: http://arxiv.org/abs/2609.06905v1
• Date: Mon, 07 Sep 2026 01:13:27 GMT
• Title: Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler
• Abstract summary: 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.
• Score: 15.748402989364804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of sampling from $μ(\mathrm{d}x)\propto e^{-V(x)}\,\mathrm{d}x$ on $\mathbb{R}^d$, where $V$ is $α$-strongly convex and $β$-smooth, and write $κ:=β/α$. 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. From a warm start initialization with $ O(1) $ Rényi divergence w.r.t. $μ$, Proximal BPS returns a sample whose law is $\varepsilon$-close to $μ$ in total variation distance using $\widetilde O(\sqrtκ\,d^{1/4} \,\mathrm{polylog}(1/\varepsilon))$ gradient queries in expectation.

Related papers

• Windowed thinning and query complexity for the bouncy particle and Zigzag samplers [5.726854405157353]
  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.
  arXiv  Detail & Related papers  (2026-07-30T15:59:25Z)
• 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)
• A Black-Box Debiasing Framework for Conditional Sampling [18.132736654624058]
  Conditional sampling is a fundamental task in Bayesian statistics and generative modeling.<n>In this paper we propose a black-box debiasing scheme that improves the accuracy of such a naive plug-in approach.
  arXiv  Detail & Related papers  (2025-10-13T07:11:27Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Spike-and-Slab Posterior Sampling in High Dimensions [11.458504242206862]
  Posterior sampling with the spike-and-slab prior [MB88] is considered the theoretical gold standard method for Bayesian sparse linear regression.<n>We give the first provable algorithms for spike-and-slab posterior sampling that apply for any SNR, and use a measurement count sub in the problem dimension.<n>We extend our result to spike-and-slab posterior sampling with Laplace diffuse densities, achieving similar guarantees when $sigma = O(frac1k)$ is bounded.
  arXiv  Detail & Related papers  (2025-03-04T17:16:07Z)
• Outsourced diffusion sampling: Efficient posterior inference in latent spaces of generative models [65.71506381302815]
  We propose amortize the cost of sampling from a posterior distribution of the form $p(mathbfxmidmathbfy) propto p_theta(mathbfx)$.<n>For many models and constraints, the posterior in noise space is smoother than in data space, making it more suitable for amortized inference.
  arXiv  Detail & Related papers  (2025-02-10T19:49:54Z)
• Sharper Bounds for $\ell_p$ Sensitivity Sampling [56.45770306797584]
  We show the first bounds for sensitivity sampling for $ell_p$ subspace embeddings for $p. We also show that the root leverage score sampling algorithm achieves a bound of roughly $d$ for $1leq p2$, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly $d2/pmathfrak S2-4/p$ for $2pinfty.
  arXiv  Detail & Related papers  (2023-06-01T14:27:28Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• 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.