提出窗口化精简方法，降低两种采样器的梯度查询次数。
Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
- 用窗口分割轨迹，每窗首处评估梯度构建事件率局部上界。
- 证明采样误差ε下，反弹采样器需约κ¹ᐟ²d(d log κ + log 1/ε)次查询。
- 适用于高维强凸优化问题，适合追求高效采样的研究人员。
设概率测度μ(dx) ∝ e⁻ᵘˣdx定义在ℝᵈ上，其中能量函数U为m-强凸且L-光滑，条件数κ = L/m。研究窗口化精简方法，用于精确模拟反弹粒子采样器和坐标方向的Zigzag过程。该方法将轨迹划分为确定性窗口，在每个窗口起点通过梯度评估构造事件率的可处理局部上界。结合量化混合速率估计与有限时间内的期望反弹和翻转次数，从高斯冷启动出发，给出查询复杂度保证：总变差误差为ε时，反弹采样器的期望梯度查询次数为O(κ¹ᐟ²d(d log κ + log 1/ε))；而Zigzag的全梯度等价查询次数为O(κd¹ᐟ⁴(d log κ + log 1/ε))，其中每个坐标偏导查询计为一个等价单位。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。