{"id":"arxiv/2606.19909","url":"https://arxiv.org/abs/2606.19909","tags":["stat.CO","math.PR","stat.ME"],"score":0,"title":"Establishing an $Ω(\\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub-$\\sqrt{d}$ algorithm for Gaussian-tailed targets","domain":"stat.CO","source":"arxiv","authors":["Augustin Chevallier"],"reviews":0,"subject":"stat.CO","summary":"Despite the theoretical appeal of their non-reversibility, to date, no Piecewise Deterministic Markov Process (PDMP) samplers have been developed that scale better than $\\mathcal{O}(\\sqrt{d})$ in computational complexity with respect to the target dimension $d$. We prove that this is a fundamental limitation by establishing an $Ω(\\sqrt{d})$ lower bound on the algorithmic complexity of PDMP samplers in a standard setup. By relaxing the assumption that the target density must remain invariant at all continuous times, we then demonstrate how to bypass this barrier. Specifically, we introduce a…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-06-18","reactions":{}}