PaperlayerView exact revision on arXiv

Source-linked AI summary

High-accuracy simulation of Picard HMC, part I: Gaussian cloud correction

Fan Chen, Sinho Chewi, Jianfeng Lu, Matthew S. Zhang

arXiv:2609.38710v1math.STcs.DScs.NAmath.NAstat.TH

TL;DR

Correcting Picard HMC trajectories is difficult because the nonlinear Picard map makes likelihood ratios complicated. The paper tracks Gaussian clouds without knowing their means and corrects the proposal law, achieving high-accuracy sampling with d^1/5 dimension dependence.

  • Problem

    Direct correction of Picard HMC is difficult because its nonlinear map makes the required likelihood ratios complicated.

    Source: §1 · p. 4

  • Method

    The sampler tracks Gaussians centered at ideal Picard iterates using cloud samples, then uses correction mechanisms to tilt the proposal law toward the next cloud.

    Source: §1 · p. 5

  • Results

    The Gaussian cloud sampler achieves high-accuracy sampling with d^1/5 dimension dependence and query cost polylogarithmic in inverse accuracy.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The authors expect the Gaussian cloud sampler’s algorithmic components to be of broad interest beyond its dimension-dependent rate.

    Source: §1 · p. 3

    The authors anticipate a natural d^3/16 bottleneck for improving the d^1/5 dependence, but do not develop that improvement.

    Source: §3.4 · p. 18

Abstract

from arXiv · show

We study the problem of sampling from a continuous density $\pi\propto \exp(-V)$ on $\mathbb R^d$, where $V\in C^2(\mathbb R^d)$ has a $\beta$-Lipschitz gradient and $\pi$ satisfies a logarithmic Sobolev inequality with constant $\alpha^{-1}$, and write $\kappa = \beta/\alpha$. We introduce the Gaussian cloud sampler, which achieves total variation accuracy $\varepsilon$ using $\widetilde O(\kappa d^{1/5}\,\text{polylog}(1/\varepsilon))$ gradient queries in expectation. The algorithm uses first-order rejection sampling (FORS) to correct the law of smoothed Picard HMC trajectories. To do so, we represent the iterates of the ideal Picard iteration via Gaussian clouds, whose centers are never evaluated, and we develop a suite of likelihood correction gadgets which only use samples from this indirect cloud representation.

1 Introduction

For high-accuracy sampling, the Gaussian cloud sampler achieves d^1/5 dimension dependence without higher-order smoothness, improving on d^1/4 while remaining incomparable to proximal BPS in its κ dependence. It corrects smoothed Picard HMC by tracking Gaussian clouds around ideal iterates without evaluating their centers.

1 Introduction

  • The sampler achieves d^1/5 dimension dependence without higher-order smoothness, improving on d^1/4 while remaining incomparable to proximal BPS's square-root κ dependence from a warm start.The main result assumes a 1-Lipschitz gradient, an LSI, and a supplied reference point; it gives TV error at most ε using gradient queries in expectation.Source: §1 · p. 3
  • The prerequisite smoothed Picard HMC framework targets a smoothed distribution and uses Picard iteration with Chebyshev–Lobatto quadrature, shifting the challenge from discretization to score estimation.That framework returns to the original target through a restricted Gaussian oracle.Source: §1 · p. 4
  • FORS corrects smoothed Picard HMC trajectories, replacing the earlier approach of controlling final error through score-estimator bias and variance.FORS samples from a tilted proposal using an unbiased estimator of the tilt rather than direct evaluations.Source: §1 · p. 4
  • Direct likelihood correction is difficult for Picard HMC because its nonlinear map makes the likelihood ratio complicated; leapfrog's volume preservation supports tractable MH correction.The paper instead tracks Gaussian clouds centered at ideal Picard iterates and corrects the proposal law to that of the next cloud.Source: §1 · pp. 4–5
  • The cloud updates use samples without knowing cloud means, avoiding costly mean estimation that could make cloud samples grow exponentially with Picard depth.The paper combines stochastic approximations of the means with FORS in a suite of correction gadgets.Source: §1 · p. 5

2 Preliminaries

The preliminaries recall earlier algorithmic ingredients, define the Gaussian-smoothed target and score, and set up Picard iteration with Chebyshev–Lobatto quadrature for high-accuracy guarantees.

2 Preliminaries

2.1 Gaussian smoothing

  • The smoothed score g_η is an RGO expectation and is not directly computable from gradient queries, motivating a stochastic estimator.Source: §2.1 · p. 6

2.2 Picard iteration and Chebyshev–Lobatto quadrature

  • High-accuracy guarantees require arbitrary-depth Picard iteration; Chebyshev–Lobatto quadrature approximates time integration in the Hamiltonian flow.Source: §2.2 · p. 7
  • For 0 < η ≤ 1, J ≥ 2, K ≥ 1, the Picard reference estimates assume h² ≤ 1/4 and h ≤ c/κ, for p ≥ 2.Source: §2.2 · p. 7

3 The Gaussian cloud sampler

The Gaussian cloud sampler corrects stochastic Picard updates without computing the ideal iterates, using Gaussian clouds and likelihood corrections to target their laws. The section describes hidden fluctuation, mean, and RGO corrections, first-order rejection sampling, and how correction costs determine the sampler’s dimension dependence.

3.1 Main ideas

  • Gaussian clouds centered at hidden ideal Picard iterates let corrected transitions target the next cloud law despite noisy proposals with incorrect means and excess fluctuations.Fluctuation correction removes extra randomness while mean correction moves the Gaussian mean to the next ideal iterate.Source: §3.1 · pp. 8–10
  • Lazy auxiliary cloud sampling yields polylogarithmic expected cloud-count overhead rather than an exponential dependence on Picard depth.Auxiliary samples are generated only when a tilt estimator or rejection requests them; the relevant events have probability O(B).Source: §3.1 · p. 10

3.2 Algorithm description

  • The sampler corrects the joint endpoint position–momentum law, retains added position noise between phases, and removes the accumulated smoothing with a terminal RGO draw.The reference smoothing level advances as η_n+1 = η_n + τ, and the final RGO disintegration returns the original target.Source: §3.1 · pp. 10–11
  • The proximal sampler wrapper handles arbitrary κ by calling the Gaussian cloud sampler only on targets with condition number at most three..Source: §3.2 · p. 13

3.3 Algorithmic components

  • When B ≤1, FORS uses O(1) expected proposal calls and O(B) expected estimator calls to realize its corrected law.FORS requires a proposal sampler and a sampler for a bounded estimator, but does not evaluate the tilt or its normalizing constant.Source: §3.3 · p. 13
  • The hidden fluctuation gadget corrects excess fluctuations without requiring the unavailable expectation EΦ(G), whose direct estimation to accuracy δ would take poly(1/δ) evaluations.Its raw proposal Φ(G) + Z has the desired mean but is not Gaussian and has excess fluctuations.Source: §3.3 · pp. 13–14
  • The ideal fluctuation tilt produces N(EΦ(G), I_n), and its FORS implementation handles clipping and truncation without evaluating EΦ(G).For K = ⌈C log(1/δ)⌉, the implementation uses at most C evaluations of Φ and C B_fluc log(1/δ) Jacobian-vector products in expectation.Source: §3.3 · p. 15
  • The hidden mean correction uses approximate draws near N(µ, I_m) and an independent random vector Δ, without being supplied µ or EΔ.Its construction invokes first-order rejection sampling with a clipped inner-product tilt estimator.Source: §3.3 · pp. 15–16
  • The hidden RGO sampler returns a draw within total variation δ of R_{η,y} without access to unknown center y.Its expected calls are at most C cloud draws, 2 + C B_RGO RGO calls, and 1 + C B_RGO gradient evaluations; approximate RGO calls with uniform TV error ε change the output bound to δ + Cε.Source: §3.3 · pp. 16–17

3.4 Proof roadmap and complexity

  • Balancing h^-1 + d h^4 gives h ≍ d^-1/5 and N ≍ d^1/5, with query complexity h^-1 + d h^4.The bound is for the contributions combined over N ≍ h^-1 phases.Source: §3.4 · p. 18
  • The analysis identifies d^3/16 as a natural bottleneck, while anticipating that the Gaussian cloud sampler could improve slightly beyond d^1/5.The paper does not develop that improvement further.Source: §3.4 · p. 18

4 Gaussian cloud corrections

This section develops strengthened Gaussian-cloud correction gadgets, including clipping for biased likelihood estimators, fluctuation and mean correction, and their composition, and establishes composition and block-evaluation guarantees. It also analyzes the hidden RGO gadget’s likelihood moments, accuracy, and oracle-call costs.

4.1 A clipping lemma

  • The clipping lemma bounds FORS output error even when the likelihood estimator is biased, under its stated clipping and normalization assumptions.The clipping threshold satisfies 0 < B ⩽ 1, and the normalization constant is assumed finite and at least 1/2.Source: §4.1 · p. 19

4.2 Gadget 2: Fluctuation correction

  • The robust fluctuation corrector gives a total-variation guarantee when the implemented map approximates a comparison map, including with randomized nonlinear approximations.Its expected evaluation counts are at most 1+CBfluc proposal evaluations and CBflucK bΣ evaluations.Source: §4.2 · pp. 20–21

4.3 Gadget 3: Mean correction

  • The mean correction tilts N(µ, Im) to the desired N(µ + E∆, Im), and the clipping lemma controls the resulting output error.For approximate proposals, maximal coupling bounds output total-variation error by Cε.Source: §4.3 · pp. 24–25

4.4 Composition and block evaluation

  • Under the stated hypotheses, composing fluctuation and mean correction yields an output-law guarantee when independent samples estimate the missing mean.The corollary assumes the fluctuation-correction error is at most cδ and bounds the Lp norm of the independent mean samples.Source: §4.4 · p. 25
  • The fluctuation corrector’s TV error is at most cδ, and applying Lemma 3.7 with a sufficiently small constant multiple of δ gives total TV error at most δ.Source: §4.4 · p. 25
  • Blockwise derivative actions call only the selected block, and the expected number of Jacobian-vector product calls is at most C B_fluc K.Source: §4.4 · p. 26
  • Each fluctuation tilt estimator uses at most CK Jacobian-vector product calls, giving at most C B_fluc K such calls in expectation.The total is at most CK(u + 1) with probability at least 1 − exp(−u); for K = O(L) and u = O(L), this is at most CL^2.Source: §4.4 · pp. 26–27

4.5 Gadget 4: Hidden RGO sampler

  • Under 0 < η−2θ ≤ 1 and 0 < θ ≤ (η−2θ)/4, Proposition 4.8 bounds hidden-RGO likelihood moments for every p ≥ 2 under the proposal law.Source: §4.5 · p. 27
  • The hidden-RGO gadget samples the clipped center tilt and applies the final RGO kernel without increasing the resulting total-variation error.Its expected center proposals and tilt-estimator calls are at most C and C B_RGO, respectively; each tilt estimator uses one cloud draw, two RGO calls, and two gradient evaluations.Source: §4.5 · p. 29

5 Applying the cloud corrections to Picard HMC

The section applies cloud corrections to stochastic-gradient evaluations in Picard HMC, deriving fluctuation and mean estimators that work around hidden Gaussian centers.

5 Applying the cloud corrections to Picard HMC

  • The implementation is first developed with proximal and Hessian oracles; the gradient-only implementation is deferred to Section B.Source: §5 · p. 29

5.1 Fluctuation estimator

  • The gradient estimator’s forward and transpose derivative actions have operator norm at most √θ + η and use O(1) exact Hessian and proximal queries.Source: §5.1 · p. 29
  • Cloud draws replace the unavailable hidden endpoint in fluctuation correction, and a joint batch preserves correlations across requested Brownian-path evaluations.Source: §5.1 · pp. 30–31

5.2 Mean estimator

  • A Gaussian Stein identity and integration by parts remove dependence on hidden y to construct the mean estimator; its implementation addresses an unavailable exact Rη,y draw via Gadget 4.Source: §5.2 · pp. 32–33
  • The exact-draw implementation also uses proximal queries and inverts I + η∇²V at the proximal point, while Section B gives an alternative without these stronger oracles.Source: §5.2 · p. 33

6 Recursive assembly, accuracy, and complexity

Section 6 analyzes the recursively corrected cloud sampler, controlling its adaptive call tree and cloud/RGO work. It bounds finite-recursion TV error and query complexity, then composes the sampler with proximal steps to obtain linear dependence on κ.

6.1 Recursive cloud implementation and adaptive calls

  • A level-(ℓ+1) cloud sample is generated from a fresh level-ℓ cloud via a noisy Picard proposal, then corrected for fluctuation and mean, with fresh recursive requests when needed.At level zero, the known center is perturbed with independent Gaussian noise.Source: §6.1 · p. 34
  • Contracting each mandatory predecessor chain into one vertex yields an adaptive forest whose additional cloud requests form side branches.For a mean correction, the expected additional cloud requests are at most C(Bmean + Bfluc Kser).Source: §6.1 · pp. 35, 40
  • Under the lemma’s offspring conditions, P{T > C(q + μ)} ≤ exp(−u), and a per-vertex query cap Qloc bounds total reference queries by C Qloc(q + μ) except with probability exp(−u).The proof bounds the expected number of new child requests per explored vertex by at most 1/4.Source: §6.1 · pp. 36–37
  • When J + Kser ≤ C L and K ≤ C L, choosing u = Ccap L for sufficiently large fixed universal Ccap justifies the local cap Qloc = C L^2.The parameter choices are J = ⌈CJL⌉, Kser = ⌈CserL⌉, and K = 1 + ⌈CKL/log L⌉.Source: §6.1 · pp. 35, 40
  • Local caps and parameter choices keep the conditional expected number of children at most 1/4, while global caps bound vertices and RGO requests by C(N+L^3) except with exponentially small probability.The expected numbers of vertices and RGO requests remain O(N); the deterministic global slot cap is C(N+L^3)L^2, exceeded with probability at most 3 exp(−CcapL).Source: §6.1 · pp. 40–41
  • With at most Tmax slots and ideal cap-overrun probability εcap, uniform per-slot TV replacement error ε yields total output error at most Tmaxε+εcap.The adaptive comparison permits later requests to depend on earlier outputs and includes the probability of stopping at the cap.Source: §6.1 · p. 41

6.2 Analysis of the Gaussian cloud sampler

  • Theorem 6.4 analyzes Algorithm 3.1 with RGO calls implemented by Proposition B.8 and local corrections realized as in Section B, under its stated κ and reference-point assumptions.It returns an output law bπ, though the supplied theorem passage omits the displayed accuracy bound.Source: §6.2 · p. 42

Its expected total number of gradient queries is at most

  • The expected total gradient-query count is at most C L^(11/2)(d+L)^(1/5) for Algorithm 3.1 under Theorem 6.4’s assumptions and specified implementations.The theorem assumes 1 ≤ κ ≤ κ0 and a supplied reference point satisfying (1.2); RGO calls use Proposition B.8 and local corrections follow Section B.Source: Its expected total number of gradient… · p. 42, §6.2 · p. 42

6.2.1 Contraction and preliminary estimates

  • The ideal phase analysis uses contraction factor ρ=1−ch/κ and establishes concentration along the run and moment estimates uniformly across phases and Picard depths.The supplied passages state that the moment estimates hold for 2 ≤ p ≤ CL and uniformly over nodes of the ideal sampler.Source: §6.2.1 · p. 44

6.2.2 Proof of Theorem 6.4

  • For interior cloud updates, the chosen fluctuation and mean correction budgets are small, and the RGO correction achieves prescribed local TV accuracy on its good event.The passages bound Bfluc by cL^−3, bound Bmean by Cc^2L^−11/4, and give the good event a failure probability at most exp(−cp0).Source: §6.2.2 · pp. 45–46
  • The uncapped reference algorithm is within ε/32 in total variation of the exact ideal algorithm; with exact Hessian and proximal local corrections, terminal RGO steps bound distance to π by 3ε/16.The remaining 13ε/16 is reserved for the gradient-only realization of the local corrections.Source: §6.2.2 · p. 48
  • C L^(9/2)(d+L)^(1/5) expected reference queries suffice for the complete reference realization; gradient-only realization adds an O(L) factor per local query.The phase cost is at most C L^2 expected reference queries, and the terminal RGO cost is absorbed into the total bound.Source: §6.2.2 · p. 48

6.3 Composition with the proximal sampler

  • C L^(13/2)κ(d+L)^(1/5) expected gradient queries suffice after proximal-sampler composition, giving linear dependence on the LSI constant κ.The composition uses O(κL) RGO calls; its accuracy proof charges ε/8 for the exact proximal chain, ε/8 for caps, and ε/8 for RGO replacement errors.Source: §6.3 · pp. 48–49

A Improved RGO sampler

The improved RGO sampler uses the RGO target’s known quadratic structure to make each Picard update cheaper to correct. This improves the Gaussian cloud sampler’s dimension dependence from d^1/4 to d^1/5.

A Improved RGO sampler

  • The hidden RGO sampler requires explicit RGO calls, motivating an improved sampler to keep their cost acceptable.The improved RGO sampler is built from the main sampler’s Gaussian corrections and exploits the target’s known quadratic part.Source: A Improved RGO sampler · p. 50
  • The construction solves the known linear term in each Picard update exactly and applies Gaussian cloud correction only to the residual gradient.Its localized RGO calls use a direct rejection routine, without invoking Theorem 6.4 or the oracle being proved.Source: A Improved RGO sampler · p. 50
  • If d + L ≥ L^9, the query-count exponent in (A.1) improves from 17/4 to 15/4.The counts include gradient, proximal, and full Hessian queries.Source: A Improved RGO sampler · p. 50
  • eO(κd^1/4) becomes eO(κd^1/5) when the improved per-call RGO bound permits h ≍ d^-1/5.The direct RGO sampler would require h ≲ d^-1/4; the improved bound supports the larger step size.Source: A Improved RGO sampler · p. 50

A.1 Direct RGO sampler

The direct RGO sampler uses a proximal query followed by a constant expected number of gradient queries when η is sufficiently small. Its proof applies the FORS sampler with a proximal point that makes the proximal residual zero.

A.1 Direct RGO sampler

  • When η satisfies the stated condition, Rη,y reaches TV accuracy ε using one exact proximal query and O(1) expected gradient queries, uniformly in y.The displayed condition on η is incomplete in the supplied passage.Source: §A.1 · p. 50
  • The proof applies FORS with x+ = proxηV(y), making the proximal residual zero and yielding the required TV bound.A universal clipping level gives O(1) expected gradient queries after the proximal query.Source: §A.1 · p. 50

A.2 Removing the quadratic part of the Picard update

This construction separates the known quadratic part of the RGO potential from its residual, solves the linear dynamics exactly, and discretizes the residual Picard updates. The resulting correction acts on residual evaluations rather than the known anchor and transformed weights.

A.2 Removing the quadratic part of the Picard update

  • The RGO potential’s known quadratic term is separated so the linear part of each Picard update can be solved exactly, leaving only the residual gradient for Gaussian correction.The normalized target is well-conditioned, and its residual gradient has Lipschitz constant at most η/2.Source: §A.2 · pp. 50–51
  • The quadratic-only dynamics form a harmonic oscillator; Picard iteration replaces the residual on each trajectory with its value on the preceding trajectory.The continuous iteration contracts in the uniform norm by at most Cηh^2.Source: §A.2 · p. 51
  • Chebyshev–Lobatto quadrature discretizes the residual updates, while the linear equations are solved through a known anchor and transformed weights.The endpoint position uses the final Picard layer; the momentum update integrates the linear term on that layer and the residual on the preceding one.Source: §A.2 · p. 52
  • The exact conditional residual is replaced by a computable stochastic estimator, and fluctuation and mean corrections are applied only to residual evaluations.The known anchor and transformed weights require no correction; the final cloud is shared by both endpoint components before joint endpoint correction.Source: §A.2 · pp. 52–53

A.3 Proof of Theorem A.1

The proof uses the residual’s η-scaled curvature to tighten Gaussian cloud correction bounds and establish the improved RGO sampler’s accuracy and query guarantees. For D ≥ L^9, it also gives a sharper query-count exponent.

A.3 Proof of Theorem A.1

  • The residual Hessian bound ∥∇²F∥op ≤ η/2 supplies an η factor in derivative bounds, giving η^2 factors in fluctuation and mean-error bounds and allowing cloud variance to shrink by η^2.These are the residual versions of the local correction bounds used in the proof.Source: §A.3 · p. 53
  • The residual updates have a common limiting phase kernel with contraction 1 − c1h and a stationary W2 defect.The residual fixed-point contraction and endpoint weight bounds support the finite-depth comparison.Source: §A.3 · pp. 54–55
  • The implementation bounds expected local queries by O(NL^2) and explicit RGO calls by O(N), then allocates local errors to obtain total TV error at most ε.The explicit RGO calls have O(1) expected query cost, and the final output is rescaled to the original coordinates.Source: §A.3 · p. 55
  • For D ≥ L^9, the expected total query count is bounded by C(1 + NL^2) ≤ C{1 + L^15/4(η^2D)^1/4}.The same accuracy argument applies with the sharper parameter choices.Source: §A.3 · p. 56

B Realization with gradient queries

The appendix constructs gradient-query inputs for the robust fluctuation theorem and implements proximal maps by a finite gradient iteration. That iteration is non-expansive and converges toward the proximal-map fixed point.

B Realization with gradient queries

  • The robust fluctuation theorem’s approximate Jacobian-vector products and evaluations are constructed using only gradients.The appendix also implements the mean estimators and RGO sampler with gradients.Source: B Realization with gradient queries · p. 56

B.1 Approximation of a proximal map

  • For convex 1-smooth V and 0 < η ⩽ 1, the finite iteration xM is 1-Lipschitz and costs M gradient queries per evaluation.Its iterates contract by η/(1 + η) toward the fixed point proxηV(y).Source: §B.1 · p. 56
  • The proximal-map error is bounded by η∥∇V(y)∥, while the iteration’s contraction establishes convergence to proxηV(y).The proof also gives a second error bound using the (1 + η)-Lipschitz map id + η∇V.Source: §B.1 · p. 56

B.2 Smoothed secants and compositions

Smoothed centered secants provide gradient-only approximations to derivatives while retaining pathwise oddness and Lipschitz control. The composition construction propagates value and derivative approximations through finite sequences of identity, gradient, and proximal maps.

B.2 Smoothed secants and compositions

  • Centered Gaussian-smoothed secants approximate derivatives in conditional expectation, while every realization remains odd and inherits the underlying map’s Lipschitz bound.For gradients of convex functions, the smoothed derivative is symmetric positive semidefinite.Source: §B.2 · p. 57
  • The composition lemma allows identity, gradient, and proximal maps with known coefficients, and its coefficient condition ensures the composed map is L-Lipschitz.Each component map is 1-Lipschitz under the stated convexity and smoothness assumptions.Source: §B.2 · pp. 57–58
  • The construction gives L-Lipschitz smooth comparison and deterministic gradient-only approximations, with derivative routines whose expected outputs approximate the corresponding Jacobian actions.The realized derivative routines remain odd and L-Lipschitz for every fixed auxiliary Gaussian draw.Source: §B.2 · p. 58
  • Increasing smoothing radii control propagated value errors, while suitable fixed iteration counts and secant parameters yield value error at most ϵ and mean derivative error at most (ϵL/B)∥u∥.The increasing radii ensure earlier value errors are small relative to the smoothing radius used at later differentiation steps.Source: §B.2 · p. 59
  • Each evaluation of the composition approximation or either Jacobian-vector routine costs at most C S^3 L* gradient queries.The routines provide values, Jacobian-vector products, and transposed Jacobian-vector products using gradients.Source: §B.2 · pp. 58–59
  • For cloud applications, the hidden center need not be evaluated because the required input combines it with an observed Gaussian perturbation.The construction preserves the joint Gaussian Lipschitz bound used by the fluctuation correction.Source: §B.2 · p. 60

B.3 Gradient implementation of the fluctuation correction

The fluctuation correction admits a gradient implementation that preserves its accuracy and moment scale under the stated assumptions. Blockwise evaluations and integrated bias control yield the prescribed total-variation accuracy.

B.3 Gradient implementation of the fluctuation correction

  • The fluctuation correction has a gradient implementation at the prescribed local total-variation accuracy and with the same fluctuation moment scale.Each value or derivative evaluation of a single block costs at most C S^3 L* gradient queries.Source: §B.3 · p. 60
  • Blockwise construction keeps covariance actions to the selected block, while a full proposal evaluates all J blocks.Independent seeds are used for the inner and outer routines, with shared seeds for paired directions.Source: §B.3 · p. 60
  • Capping calls and input and direction radii controls stopping probabilities and tail errors, allowing the integrated bias theorem to deliver the prescribed TV accuracy.The full proposal cost sums the value costs over all J blocks.Source: §B.3 · pp. 60–61

B.4 Gradient implementation of the mean estimator

The mean estimator is implemented with gradients without evaluating the unknown point y, while retaining its moment bound up to the prescribed error. Its construction combines a gradient-secant term with a divergence term whose bias is controlled after averaging over the Gaussian cloud.

B.4 Gradient implementation of the mean estimator

  • The estimator targets gη(y) − Egη(C) without evaluating y, using gradients and retaining the Proposition 5.4 moment bound up to the prescribed error.Under the stated radius hypothesis and log(1/δ) = O(L), it uses C L gradient queries apart from RGO draws.Source: §B.4 · pp. 61–63
  • The estimator follows two terms: a gradient secant in the first and a divergence term in the second, with integration by parts removing the unknown y.When θ = 0, the divergence term is omitted.Source: §B.4 · pp. 61–63
  • Averaging over C controls the divergence estimator’s bias without requiring a known modulus of continuity for D proxηV.The averaged-secant bound accounts for secant and proximal-iteration errors.Source: §B.4 · p. 62
  • The divergence contribution needs no inverse power of θ in its error control, and it disappears when θ = 0.The prescribed accuracy is obtained by choosing smoothing, secant, and proximal tolerances under the stated radius bounds.Source: §B.4 · p. 63

B.5 Cost of the local gradient operations

Local gradient operations have cost CL gradients when inputs and directions are capped at exp(CL), with cap failures and tail contributions kept within the allocated error budget.

B.5 Cost of the local gradient operations

  • On caps of radius exp(CL), each block value or derivative action and each mean replica apart from its RGO draws uses CL gradients.The caps are measured relative to xref for the main sampler and in normalized coordinates for an RGO call.Source: §B.5 · p. 63
  • The caps hold with sufficiently small stopping probability because local reference-operation counts are capped and the ideal phase inputs have controlled radii and moments.The proof uses a union bound over operation slots; Hölder’s inequality controls linear and quadratic tail terms.Source: §B.5 · p. 64
  • Each evaluation uses S = O(1) maps with L∗ = O(L), and fixed-count secants give the mean estimator the same logarithmic-precision cost.The J terms of a proposal are counted separately; the evaluation cost is CL gradients, excluding RGO draws.Source: §B.5 · p. 64

B.6 Gradient implementation of the RGO

The RGO construction replaces exact proximal points with gradient-query approximations and allocates error across normalization, corrections, replacements, and stopping events. Its query bound follows by applying the gradient implementation to the sampler of Theorem A.1 and adding normalization cost.

B.6 Gradient implementation of the RGO

  • The gradient RGO construction approximates Rη,y in TV using gradient queries for convex V with 0 ⪯ ∇2V ⪯ I.The supplied passage does not include the query-bound expression.Source: §B.6 · p. 64
  • For b,v, it computes xM(v), sets r = ∇V(xM(v)) + (xM(v) − v)/b, and uses V(x) − ⟨r,x⟩ so xM(v) is an exact proximal point.The modified potential has gradient ∇V − r.Source: §B.6 · p. 64
  • Initial normalization costs CLy gradients, and choosing M sufficiently large makes its additional TV error fit the local budget.The tilted target is normalized about xM(y), with residual gradient zero at the origin.Source: §B.6 · p. 64
  • The implementation runs Theorem A.1 at accuracy ε/4, allocates ε/2 to replacements and stopping events, and adds normalization cost to the gradient-scaled query bound.The gradient implementation multiplies Theorem A.1’s query bound by CL; when d + L ≥ L^9, the exponent 21/4 improves to 19/4.Source: §B.6 · pp. 64–65

B.7 Gradient implementation of the Gaussian cloud sampler

The Gaussian cloud sampler has a gradient-only implementation that preserves its total-variation accuracy guarantee. The construction implements local corrections and RGO draws with gradient queries, while caps and allocated error budgets yield the stated query cost.

B.7 Gradient implementation of the Gaussian cloud sampler

  • C L^(11/2) (d + L)^(1/5) expected gradient queries suffice to return a law within ε in TV of π.This is the gradient realization of Algorithm 3.1 under the hypotheses of Theorem 6.4.Source: §B.7 · p. 65
  • Fluctuation corrections, mean estimators, and explicit RGO draws implement the sampler using gradient queries while retaining its fluctuation parameter and moment bounds up to constants.The joint Lipschitz bound √θ + η is preserved.Source: §B.7 · p. 65
  • Caps and local error budgets preserve the TV guarantee while multiplying the reference query count by CL, including RGO normalizations.The proof budgets at most 3ε/16 for reference estimates, ε/2 for additional value, derivative, and mean errors, and ε/4 for caps and tails, totaling 15ε/16.Source: §B.7 · p. 65

Related papers

Loading 2609.38710v1…