Smoothed Picard Hamiltonian Monte Carlo

• URL: http://arxiv.org/abs/2609.06906v1
• Date: Mon, 07 Sep 2026 01:13:28 GMT
• Title: Smoothed Picard Hamiltonian Monte Carlo
• Abstract summary: 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.
• Score: 15.748402989364804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a new low-accuracy sampler, called \emph{smoothed Picard Hamiltonian Monte Carlo}, which combines Gaussian smoothing, Picard iteration, and higher-order discretization. For a log-concave target $π\propto \exp(-V)$ in dimension $d$ satisfying $0 \prec αI \preceq \nabla^2 V \preceq βI$, with condition number $κ:= β/α$, smoothed Picard HMC returns a sample with $\sqrt α\,W_2(\cdot,π) \le \varepsilon$ using $\widetilde O(κ^2 + κ^{7/6} d^{1/6}/\varepsilon^{1/3})$ gradient queries. We also prove stronger $W_q$ bounds, and then develop an algorithmic framework, the recursive warm start generator, to upgrade these $W_q$ bounds to stronger divergence guarantees. This produces a warm start for the proximal bouncy particle sampler, introduced in a companion work, leading to a high-accuracy log-concave sampler with complexity $\widetilde O((κ^{7/6} d^{1/6} + κ^{1/2} d^{1/4})\mathrm{polylog}(1/\varepsilon))$.

Related papers

• Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling [9.454986540713655]
  We study the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA) for $(,mathrmd x)propto e-f(x)-g(x),mathrmd x$, where $fin C2(mathbbRd)$ is $m$-strongly convex with $L_f$-Lipschitz gradient and $g:mathbbRdtomathbbR$ is convex and globally $G$-Lipschitz
  arXiv  Detail & Related papers  (2026-09-11T08:47:33Z)
• 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)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  This paper deals with the problem of efficient sampling from a differential equation, given the drift function and the diffusion matrix. It is possible to obtain independent and identically distributed (i.i.d.) samples at precision $varepsilon$ with a cost that is $m2 d log (1/varepsilon)$ Our results suggest that as the true solution gets smoother, we can circumvent the curse of dimensionality without requiring any sort of convexity.
  arXiv  Detail & Related papers  (2023-03-30T02:50:49Z)
• 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)
• Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Sampling [17.832449046193933]
  We consider the constrained sampling problem where the goal is to sample from a target distribution of $pi(x)prop ef(x)$ when $x$ is constrained. Motivated by penalty methods, we convert the constrained problem into an unconstrained sampling problem by introducing a penalty function for constraint violations. For PSGLD and PSGULMC, when $tildemathcalO(d/varepsilon18)$ is strongly convex and smooth, we obtain $tildemathcalO(d/varepsilon
  arXiv  Detail & Related papers  (2022-11-29T18:43:22Z)
• Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps [0.0]
  Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density $e-f(x)$. We show that HMC can sample from a distribution that is $varepsilon$-close in total variation distance using $widetildeO(sqrtkappa d1/4 log(1/varepsilon)$ gradient queries.
  arXiv  Detail & Related papers  (2022-09-26T15:29:29Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.