PaperlayerView exact revision on arXiv

Source-linked AI summary

Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling

Bo Yuan, Wei Guo, Yongxin Chen

arXiv:2610.16248v1cs.LGcs.AImath.STstat.TH

TL;DR

The paper studies sampling from strongly convex, smooth log-concave targets, where proximal resampling loses directional information despite preserving the target. It introduces reflected proximal dynamics with conditional kinetic motion and refreshment, and reports warm-start and end-to-end oracle bounds with polylogarithmic accuracy dependence.

  • Problem

    The proximal sampler preserves the target and recovers overdamped Langevin dynamics at small steps, but its Gaussian redraw discards directional information that underdamped dynamics retains through momentum.

    Source: §1 · p. 1

  • Method

    Reflected proximal dynamics reflects the auxiliary variable, combines conditional motion with controlled refreshment, and has flux-resampled half-turn and persistent quarter-turn realizations.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Both realizations use ~O(√κ d^1/4) expected oracle queries from a constant-χ² warm start, while warm-start removal yields an end-to-end ~O(κ^6/7 d^1/4) bound; both have polylogarithmic dependence on 1/ε.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    The reported guarantees give reflected proximal dynamics high-accuracy sampling bounds in the strongly convex, smooth setting, with only polylogarithmic dependence on 1/ε.

    Source: §2 · p. 2, §7 · p. 10

    The guarantees assume an α-strongly convex, β-smooth target; extending the analysis to settings such as log-Sobolev or Poincaré inequalities is left for future work.

    Source: §2 · p. 2, §7 · p. 10

Abstract

from arXiv · show

We study sampling from $\pi(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ is $\alpha$-strongly convex and $\beta$-smooth with condition number $\kappa=\beta/\alpha$. For this problem, the proximal sampler preserves the target exactly and recovers overdamped Langevin dynamics in the small-step limit, but its Gaussian resampling step discards directional information. Underdamped Langevin dynamics retains such information through momentum to accelerate exploration, motivating a proximal construction that combines target preservation with directional persistence. We introduce \textit{reflected proximal dynamics}, which combines proximal sampling with an exact reflection of the auxiliary variable, conditional kinetic motion, and controlled refreshment. We develop two realizations: a flux-resampled underdamped half-turn and a persistent-momentum quarter-turn. From a warm start with constant $\chi^2$ divergence, both methods achieve total variation error $\varepsilon$ using $\widetilde O(\sqrt{\kappa}d^{1/4})$ expected oracle queries. We further remove the supplied warm-start assumption by combining either sampler with existing posterior samplers in a proximal initialization stage with an optimized coarse step size. Accounting for both initialization and sampling yields $\widetilde O(\kappa^{6/7}d^{1/4})$ expected oracle queries. In both regimes, the dependence on the target accuracy $\varepsilon$ is $\mathrm{polylog}(1/\varepsilon)$, making reflected proximal dynamics a promising framework for accelerated high-accuracy log-concave sampling.

1 INTRODUCTION

The paper combines proximal target preservation with the directional persistence of underdamped dynamics by reflecting the auxiliary variable and adding conditional motion and refreshment. It presents two realizations, with warm-start and end-to-end guarantees whose accuracy dependence is polylogarithmic.

1 INTRODUCTION

  • The proximal sampler preserves the target and recovers overdamped Langevin dynamics at small steps, but its Gaussian redraw discards directional memory retained by underdamped dynamics.Underdamped dynamics uses momentum to retain direction and can accelerate exploration.Source: §1 · p. 1
  • The two realizations store directional information differently, while concurrent PBPS uses an undamped harmonic half-turn with deterministic momentum reflections.The flux method uses a damped flux-resampled half-turn; the persistent method uses a position–momentum quarter-turn.Source: §1 · p. 2
  • From a constant-χ² warm start, both realizations achieve ~O(sqrt(κ)d^1/4) expected oracle complexity.The two realizations are the flux-resampled half-turn and persistent quarter-turn.Source: §1 · p. 2
  • Without a supplied warm start, an optimized proximal warm-up yields end-to-end expected oracle complexity ~O(κ^6/7 d^1/4).The bound accounts for initialization and final sampling.Source: §1 · p. 2

2 PRELIMINARIES

The preliminaries define the target and query conventions, then review Langevin dynamics, proximal sampling, and Poisson thinning. Together these establish the sampling setting and the basic tools used by the paper.

2 PRELIMINARIES

  • The target is π(x) ∝ e^-V(x), with V α-strongly convex and β-smooth; κ = β/α, and oracle-query counts include internal work and rejected proposals.A constant-D2 warm start has D2(ν∥π)=O(1), and tilde-O notation suppresses polylogarithmic factors.Source: §2 · p. 2

2.1 OVERDAMPED AND UNDERDAMPED LANGEVIN DYNAMICS

  • Overdamped Langevin dynamics moves position diffusively, whereas underdamped dynamics stores direction in momentum and has a faster stated χ² contraction rate under the low-friction choice.The bounds given are e^-2αt for overdamped dynamics and Ce^-c√αt for underdamped dynamics under Assumption 1.Source: §2.1 · pp. 2–3

2.2 THE PROXIMAL SAMPLER

  • The proximal sampler augments X∼π with Gaussian Y, then alternates Y|X and the localized conditional X|Y=q_y; its ideal chain preserves π and approaches Langevin dynamics as η→0.An exact independent draw from q_y is an ideal restricted Gaussian oracle draw.Source: §2.2 · p. 3

2.3 POISSON PROCESS AND POISSON THINNING

  • Poisson thinning simulates a state-dependent event rate by proposing times from a homogeneous rate upper bound and accepting each candidate with probability λ_s/λ̄.This avoids directly inverting the integrated intensity when it has no closed-form inverse.Source: §2.3 · p. 3

3 REFLECTED PROXIMAL DYNAMICS

Reflected proximal dynamics replaces independent Gaussian redraws with auxiliary-variable reflection, then uses a conditional kernel and occasional refreshes. The framework preserves the augmented target when its accelerated kernel preserves the relevant conditional distribution.

3 REFLECTED PROXIMAL DYNAMICS

  • The framework reflects the auxiliary variable rather than redrawing it, modifying the proximal sampler’s outer update to retain the previous displacement direction.The momentum-augmented version is introduced later in the paper.Source: §3 · p. 3

3.1 THE FRAMEWORK

Algorithm 1: Ideal reflected proximal dynamics

  • Each ideal iteration sets Y_{k+1}=2X_k−Y_k, then chooses an independent q_y draw with probability ρ or an M_y transition from X_k otherwise.The accelerated branch is the one that introduces directional persistence; invariance alone does not guarantee acceleration.Source: §3.1 · p. 3, Algorithm 1: Ideal reflected proximal… · p. 4

3.2 WHY REFLECTION AND REFRESHMENT?

  • Reflection reverses the displacement without changing its magnitude; a correlated q_y-preserving conditional update can turn that retained direction into motion, while occasional independent refreshes remove correlations.The identity kernel is invariant but provides no contraction, motivating refreshment.Source: §3.2 · p. 4

3.3 A ONE-DIMENSIONAL PICTURE OF ACCELERATION

  • In the quadratic example, correlated reflected moves add approximately linearly as n√η, compared with the standard sampler’s random-walk displacement √(nη).The figure contrasts an independent redraw with reflection and shows sign retention in the accelerated branch, unlike the independent RGO draw.Source: §3.3 · p. 4, Figure 1 · p. 5

4 FLUX-RESAMPLED UNDERDAMPED HALF-TURN

The flux-resampled half-turn combines a reflected auxiliary variable with an event-driven conditional update, then discards momentum. Its ideal kernel preserves the conditional target, while capped implementations are coupled to the ideal chain to obtain a warm-start sampling guarantee.

4.1 THE FLUX-RESAMPLED UPDATE

  • At each outer step, a reflected auxiliary value is followed by a conditional update using a Gaussian momentum and an event-driven underdamped half-turn.The update freezes the nonlinear force at an independent conditional reference and uses events to correct the residual force.Source: §4 · p. 5, §4.1 · p. 5

4.2 WHY A HALF-TURN AND WHY EVENTS?

  • The half-turn’s event rate and Rayleigh momentum update pair fixed-reference paths with momentum-reversed paths of equal stationary probability.Averaging over the independent reference and discarding momentum yields a reversible position kernel that preserves the conditional law when βη ≤ 1/2.Source: §4.2 · p. 6

4.3 FROM THE IDEAL KERNEL TO AN IMPLEMENTABLE UPDATE

  • The implementable update replaces the exact conditional reference with a certified approximate RGO and the state-dependent event clock with capped Poisson thinning.A coupling to the ideal chain tracks disagreements from solver caps, approximate conditional draws, or an ideal event rate exceeding the cap.Source: §4.3 · pp. 6–7

4.4 CONVERGENCE AND ORACLE COMPLEXITY

  • The ideal chain contracts over blocks of eO(1/√(αη)) iterations by transferring auxiliary variation into conditional position, reversing it with the half-turn, and damping the remainder through the RGO branch.The theorem’s contraction condition includes βη ≤ c0.Source: §4.4 · p. 7
  • The implementable flux sampler returns total variation error at most ε from an initial law with D2 divergence at most ∆.The theorem initializes the auxiliary variable with a Gaussian draw conditional on the initial position.Source: §4.4 · p. 7

5 PERSISTENT-MOMENTUM QUARTER-TURN

The persistent-momentum method carries momentum between outer iterations, using a quarter-turn to transfer centered position information into momentum. Its implementable reference avoids an RGO draw on every accelerated iteration, and the method achieves the stated warm-start query bound.

5 PERSISTENT-MOMENTUM QUARTER-TURN

  • The method augments the outer state with momentum, carries terminal momentum forward, and requires the accelerated branch to preserve q_y ⊗ γ_d.The refresh branch redraws position and momentum; the accelerated branch applies the persistent phase-space kernel.Source: §5 · p. 7, §5.1 · p. 8

5.2 WHY A QUARTER-TURN?

  • A quarter-period rotation maps centered position and momentum as (W0, P0) → (P0, −W0), storing centered position information in terminal momentum for later iterations.Specular momentum reflections correct the residual force while preserving momentum magnitude; the RGO branch supplies occasional refreshment.Source: §5.2 · p. 8

5.3 FROM THE IDEAL KERNEL TO AN IMPLEMENTABLE UPDATE

  • The implementable accelerated branch uses a shifted Gaussian reference based on a conditional mode solve, preserving exact conditional invariance while approximating q_y for contraction.Approximate RGO calls are reserved for refresh iterations, which occur with probability ρ.Source: §5.3 · p. 8

5.4 CONVERGENCE AND ORACLE COMPLEXITY

  • The ideal contraction tracks dependence moving among the auxiliary variable, conditional position, and momentum, with the quarter-turn transferring it and the RGO branch removing remaining conditional dependence.The stated theorem sets the refresh probability using g = √(αη).Source: §5.4 · p. 9
  • A constant-D2 warm start gives eO(√κd^1/4) expected oracle queries and only polylog(d, κ, 1/ε) expected RGO calls.The implementable sampler reaches TV error at most ε under the stated initialization and step-size conditions.Source: §5.4 · p. 9

6 REMOVING THE SUPPLIED WARM START

The cold-start pipeline combines proximal warm-up with either reflected sampler as a finalizer, counting the costs of all stages. Optimizing the coarse step size yields a polynomial query bound while retaining polylogarithmic dependence on target accuracy.

6 REMOVING THE SUPPLIED WARM START

  • The cold-start pipeline localizes when needed, uses a coarse proximal chain to reduce divergence to a constant, then runs a reflected sampler for final high-accuracy sampling.The end-to-end query count includes all stages, and the overall dependence on 1/ε remains polylogarithmic.Source: §6 · p. 9
  • The coarse route balances fewer iterations at larger r against harder conditional draws, using implementable posterior samplers in place of exact conditional draws.The optimized route’s bound includes implementable warm-up and final reflected sampling but excludes one-time localization cost.Source: §6 · p. 10
  • Optimizing the coarse route gives polynomial cost factor κ^2/3d^1/3 when d ≲ κ^16/7, κd^3/16 when κ^16/7 ≲ d ≲ κ^8, and √κd^1/4 when d ≳ κ^8.The corresponding coarse-step choices are r ≍ κ, d^1/8, and κ, respectively.Source: §6 · p. 10
  • For polynomially bounded divergence B, warm-start removal yields at most eO(κ^6/7d^1/4) expected oracle queries.The wrapper uses either reflected sampler as its final stage and achieves TV error at most ε.Source: §6 · p. 10

7 CONCLUSION

Reflected proximal dynamics combines exact Gaussian reflection, conditional kinetic transport, and controlled refreshment to accelerate sampling. The two realizations have polylogarithmic accuracy dependence, while the persistent method uses only a polylogarithmic expected number of approximate-RGO calls; broader target settings remain future work.

7 CONCLUSION

  • From a constant-χ2 warm start, both realizations use eO(√κd1/4) expected oracle queries; end-to-end complexity is eO(κ6/7d1/4), with polylogarithmic dependence on 1/ε.The persistent construction makes only a polylogarithmic expected number of approximate-RGO calls.Source: §7 · p. 10

A RELATED WORK AND DETAILED COMPARISON

  • Extending the analysis beyond smooth, strongly log-concave targets to settings such as log-Sobolev or Poincaré inequalities is left for future work.Related proximal approaches broaden target, geometry, oracle, or convergence settings, while these methods retain the smooth strongly log-concave setting and modify outer dynamics to carry directional memory.Source: §7 · p. 10, A RELATED WORK AND DETAILED COMPARISON · p. 17
  • Unlike PBPS and the flux method, the persistent method uses an independent RGO reference only on rare refresh iterations.It carries momentum between ordinary iterations through a quarter-turn; PBPS uses a harmonic BPS half-turn with specular bounces and a fresh reference each iteration.Source: A RELATED WORK AND DETAILED COMPARISON · p. 17

B PROOFS FOR THE FLUX-RESAMPLED HALF-TURN

The proof follows the algorithm from conditional-law geometry through outer-chain contraction to finite implementations and complexity accounting. Its new ingredients are a covariance-weighted half-turn estimate and a modified-energy argument.

B PROOFS FOR THE FLUX-RESAMPLED HALF-TURN

  • The proof sequence establishes conditional-law geometry and half-turn preservation, derives approximate reversal of relevant affine position coordinates, then uses reflection and refreshment for accelerated L2 contraction.Finite implementations replace exact conditional draws and unbounded event clocks, with total-variation error and oracle queries accounted for afterward.Source: B PROOFS FOR THE FLUX-RESAMPLED… · pp. 17–18
  • The appendix states that it proves Props. 2 and 5 and Thms. 1 and 2, following the algorithm’s steps.It introduces a normalized conditional coordinate w = (x−y)/√η and names operators for conditional expectation, outer reflection, and the conditional flux half-turn.Source: B PROOFS FOR THE FLUX-RESAMPLED… · pp. 17, 19
  • The new proof ingredients are a covariance-weighted half-turn estimate and a modified-energy argument that yields contraction of the complete reflected proximal chain.Standard ingredients, including Brascamp–Lieb and Poincaré inequalities, skew balance, and approximate-RGO implementation, are cited rather than reproved.Source: B PROOFS FOR THE FLUX-RESAMPLED… · pp. 18–19

B.1 CONDITIONAL GEOMETRY AND VALIDITY OF THE HALF-TURN

This section establishes the conditional geometry and exact validity of the event-driven half-turn, then develops local and global error estimates. It uses a decreasing corrected energy to prove convergence, block contraction, and a chi-square bound.

B.1 CONDITIONAL GEOMETRY AND VALIDITY OF THE HALF-TURN

  • The conditional law has covariance controlled by I − Σ_y, and its score identities quantify the same conditional geometry used to bound the Y-marginal curvature.The passage also gives bounds on Σ_y, I − Σ_y, and Cov(g_y(W)) when s < 1.Source: §B.1 · p. 19
  • For each fixed y and reference, the event-driven process is non-explosive, preserves q_y ⊗ γ_d, and yields a reversible position kernel, including after averaging over an independent reference.The outer reflection preserves Π_η, so the complete row and its position marginal π are invariant.Source: §B.1 · pp. 20–21

B.2 THE COVARIANCE-WEIGHTED HALF-TURN ESTIMATE

  • When s = βη ≤ 1/2, the conditional position kernel’s affine half-turn estimate controls deviation from negation with covariance-weighted error.The proof uses exact affine evolution at the damped harmonic half-period and bounds the event correction using s(I − Σ_y).Source: §B.2 · p. 21

B.3 FROM THE CONDITIONAL HALF-TURN TO ACCELERATED CONTRACTION

  • The ideal chain has an L2 contraction under s ≤ c and ρ ≍ a log(e/a), combining outer-reflection transfer, the conditional half-turn, and occasional independent conditional refreshment.The section describes reflection as transferring part of the fixed-Y observable component into conditional variation, which refreshment damps.Source: §B.3 · p. 22

B.3.1 WHAT OUTER REFLECTION TRANSFERS

  • Outer reflection transfers conditional variation through Γ, with Γ ⪰ γ_a I for γ_a = 2√a and 4η∥∇Tf∥² ≤ ∥Γf∥².The transferred component is represented as an isometric image of Γf.Source: §B.3.1 · p. 23
  • The transferred signal decomposes into a centered affine conditional-position term and an error, separating the leading reflection signal from its nonlinear remainder.The error is centered conditionally on Y+; the accompanying lemma bounds its size for sufficiently small universal s.Source: §B.3.1 · p. 23

B.3.2 LIFTING THE LOCAL HALF-TURN ESTIMATE

  • A dyadic operator comparison converts an interpolation-type bound into A*A ⪯ C{1 + log(M/m)}B, and the subsection establishes a resulting global half-turn estimate.The comparison applies when mI ⪯ B ⪯ MI and ∥Av∥₂ ≤ ∥v∥∥Bv∥.Source: §B.3.2 · p. 24
  • A spectral decomposition and Lemma 5 lift the local estimate to bound the half-turn error Aht without treating this generally non-self-adjoint operator as positive.On the complementary spectral subspace, Γ2 ⪰ 3I/4 and ∥Aht∥ ≤ 2.Source: §B.3.2 · p. 24

B.3.3 A DECREASING ENERGY

  • A cross-term correction tracks the exchange between variation across Y and the conditional signal; under exact sign reversal it decreases by ∥fY∥2 − ∥fV∥2, while the RGO branch controls the full conditional component.The conditional component also contains the remaining variation f⊥.Source: §B.3.3 · p. 25
  • For nblk chosen as in Theorem 1 with a sufficiently large universal constant, Proposition 6 gives block L2 norm at most e^-1; applying this estimate J times yields the chi-square result for the evolving density.Source: §B.3.3 · p. 25

B.4 IMPLEMENTABLE ALGORITHM AND QUERY-COMPLEXITY ANALYSIS

The section identifies a finite counterpart to the ideal chain and indicates that its operations are organized by source and finite-operation columns.

B.4 IMPLEMENTABLE ALGORITHM AND QUERY-COMPLEXITY ANALYSIS

  • The finite counterpart replaces three operations of the ideal chain.The supplied table heading identifies source ideal operations and finite operations as the comparison columns.Source: §B.4 · p. 26
  • The ideal chain assumes an exact conditional reference and an uncapped event clock.These are the ideal operations that motivate finite replacements.Source: §B.4 · p. 26
  • The implementation comparison is organized by pairing each source ideal operation with its finite operation.Source: §B.4 · p. 26

B.4.1 CAPPED POISSON THINNING

The appendix establishes the capped half-turn’s total-variation guarantee by coupling its finite implementation to the ideal chain. It also gives per-row work accounting and extends the regularity arguments to the stated weak-gradient domains.

B.4.1 CAPPED POISSON THINNING

  • After caching the reference gradient, the conditional linear Gaussian motion needs no oracle queries between candidate event times.A candidate time uses one oracle query for the event test; each row also incurs center-solver, RGO, and event-test work.Source: §B.4.1 · pp. 26, 28
  • Capping the event rate gives exact thinning of the truncated rate, while the stationary rate-tail bound supports coupling the exact and capped half-turns.Under a D2-warm initial law, the capped-clock separation probability is at most ξ, and the final expected clock work is that of a homogeneous Poisson clock over an O(1) interval.Source: §B.4.1 · pp. 26–27
  • Each row uses a capped center solver, an approximate RGO reference, and either an independent refresh or the capped flux half-turn.A failed center-solver cap stops the algorithm; the stated construction is almost surely finite from every initial state.Source: §B.4.1 · p. 27
  • The three finite-row disagreements—center-cap failure, approximate-reference mismatch, and capped-clock mismatch—are each controlled at the row level before a union bound over rows.The center-cap failure is at most δrow under the ideal law; the reference and clock couplings also have failure probability at most δrow.Source: §B.4.1 · p. 28
  • The ideal mixing error plus a union-bounded ε/2 finite-row error yields the total-variation conclusion for the capped implementation.The ideal output is within ε/2 of π, and the finite-row disagreements contribute at most ε/2.Source: §B.4.1 · pp. 27–28

B.4.2 REGULARITY AND DOMAIN EXTENSIONS

  • Mollification and Gaussian-envelope bounds extend the regularity identities to nonsmooth potentials, while graph-norm approximation extends the weak-gradient estimates.The event-driven process itself requires no smoothing because its residual force is globally Lipschitz and its integrated hazard is continuous.Source: §B.4.2 · p. 29

C PROOFS FOR THE PERSISTENT QUARTER-TURN

The appendix proves exactness of the persistent conditional move and invariance of the complete iteration. It distinguishes standard ingredients from the new position–momentum transfer, contraction, and shifted-reference arguments.

C PROOFS FOR THE PERSISTENT QUARTER-TURN

  • The new arguments are the position–momentum transfer estimate, its unit-circle contraction analysis, and the shifted-reference implementation; established skew-balance, functional-inequality, and RGO results are used as standard ingredients.Absorbing the known strong-convexity quadratic into the conditional motion yields a near-Gaussian refinement.Source: C PROOFS FOR THE PERSISTENT QUARTER-TURN · p. 29

C.1 EXACTNESS OF THE PERSISTENT CONDITIONAL MOVE

  • For fixed reference, the conditional move follows a harmonic flight and uses a state-dependent Poisson clock to reflect momentum across the residual-gradient direction.A reference drawn independently of the incoming state may be averaged while retaining the stated invariance and adjoint properties.Source: §C.1 · p. 30
  • The fixed-reference conditional kernel is well-defined and non-explosive because the event rate is bounded on invariant energy sets.Every initial state lies in some such set, where thinning a homogeneous Poisson process constructs the process.Source: §C.1 · p. 30
  • Pairing each trajectory with its momentum-reversed time reversal proves skew balance; taking the constant observable then gives invariance of the conditional move.The path pairing matches collision factors and cancels the target-density change against the survival-probability change.Source: §C.1 · pp. 30–31
  • The ideal iteration composes outer reflection with a mixture of conditional refresh and persistent quarter-turn, preserving the augmented target.The refresh is conditional expectation given Y; orthogonality of the refreshed and remaining components yields the stated refresh dissipation.Source: §C.1 · p. 31

C.2 HOW REFLECTION FEEDS THE QUARTER-TURN

This section develops the contraction argument for the reflected quarter-turn chain, tracing how reflection transfers conditional-position information into momentum and assembling the resulting steps. It also presents a resolvent strategy and tools for implementing the persistent sampler with warm-start guarantees, including comparison, approximation, and bounded-cost numerical procedures.

C.2 HOW REFLECTION FEEDS THE QUARTER-TURN

  • For observables in the slow spectral subspace, Proposition 10 controls the position–momentum transfer errors when βη is sufficiently small.The transfer argument uses an intermediate affine observable; refreshment damps variation not represented by the transferred signals.Source: §C.2 · p. 32

C.2.1 STEP 1: WHAT THE OUTER REFLECTION CREATES

  • Reflection creates a conditional-position signal that is approximated by an affine observable, with derivative bounds established on the slow spectral subspace.The proof extends the estimates to the full weak-gradient domain without requiring the spectral projection to preserve smoothness.Source: §C.2.1 · pp. 33–34

C.2.2 STEP 2: WHAT THE QUARTER-TURN DOES TO AFFINE INFORMATION

  • When βη ≤ 1/2, the quarter-turn approximately maps affine position information into momentum and maps momentum back into negative position information.The deviation is controlled using the conditional variation of the potential's gradient.Source: §C.2.2 · p. 35

C.2.3 STEP 3: ASSEMBLE THE GLOBAL TRANSFER ESTIMATE

  • The global transfer estimate combines reflection and quarter-turn errors, then extends the result from smooth observables to the slow spectral subspace by one graph-closure argument.The normalized position and momentum channels form an approximate quarter rotation, with each transfer error bounded by the amount of signal being transferred.Source: §C.2.3 · pp. 35–36

C.3 FROM POSITION–MOMENTUM TRANSFER TO CONTRACTION

  • The contraction strategy rules out large solutions to the unit-circle resolvent equation using three slowly varying coordinates, then uses refreshment to control the remaining conditional variation.The three coordinates expose position and momentum companions of slow modes; they do not decompose the full state space, so refreshment is essential.Source: §C.3 · pp. 36–37
  • A unit-circle resolvent bound yields geometric operator decay, which the proof uses to obtain χ2 contraction and a total-variation guarantee for the chain.The TV conclusion follows by augmenting the initial state, applying the χ2 bound, and marginalizing to X.Source: §C.3 · pp. 38–39

C.4 IMPLEMENTABLE ALGORITHM AND WARM-START ACCOUNTING

  • The implementation theorem gives an implementable persistent iteration with TV error at most ε from an initialization satisfying D2(ν0∥π) ≤ ∆.The algorithm uses Alg. 3 as its accelerated branch.Source: §C.4 · p. 39

C.4.1 A COMPARISON PRINCIPLE FOR THE COMPLETE PATH

  • A warm-start path comparison bounds N-step disagreement between exact and approximate chains using their stationary one-step disagreement probability.The comparison applies when the exact kernel preserves π and the warm start has bounded χ2 divergence.Source: §C.4.1 · p. 39

C.4.2 REPLACING THE IDEAL EXACT-CONDITIONAL REFERENCE ON THE ACCELERATED BRANCH

  • A shifted Gaussian centered near the conditional mode can replace the ideal conditional reference while preserving the local quarter-turn estimate under smallness conditions on τL and τL²d.The mode approximation has normalized shift at most L√d/(1 + αη).Source: §C.4.2 · pp. 40–41

C.4.3 MODE, CLOCK, AND REFRESH SUBROUTINES

  • The mode solver admits a deterministic iteration cap whose failure probability is at most 2e^-B under the stationary augmented law.The conditional potential has condition number at most two, enabling a pointwise logarithmic iteration bound.Source: §C.4.3 · p. 41
  • Capping the event rate permits homogeneous Poisson thinning, with the stated expected-query bound for the capped flight including the query at the reference.The cap changes a stationary transition with exponentially small probability in B.Source: §C.4.3 · p. 41
  • The first-order rejection sampler returns an approximate RGO with χ2 error at most δ² in both directions, using at most Krgo expected queries after mode certification.The result applies for 0 < δ < 1/2 and a point satisfying the proposition’s mode-certificate condition.Source: §C.4.3 · pp. 41–42

C.4.4 PROOF OF THE IMPLEMENTATION THEOREM

The implementation proof controls approximation and work-cap errors before establishing the quadratic-baseline refinement. That refinement changes the curvature integrated by the conditional motion while preserving the outer reflection gap, and the warm-start wrapper proof sets up the subsequent end-to-end analysis.

C.4.4 PROOF OF THE IMPLEMENTATION THEOREM

  • The implementation error budget combines ideal mixing, mode-solver and event-clock caps, and approximate refresh, with their stated contributions summing to less than ε.The approximate-refresh contribution is at most Nρδrgo/2 ≤ ε/16, and projection to position cannot increase total variation.Source: §C.4.4 · p. 42

C.4.5 AFFINE FORM USED BY THE QUADRATIC BASELINE

  • The affine local compiler transfers the shifted-Gaussian comparison, quarter-turn forcing, clock estimate, and RGO gate to conditionals with local smoothness L.Its assumptions include τL ≲ 1 and τL2d ≲ 1.Source: §C.4.5 · pp. 42–43

C.5 QUADRATIC-BASELINE REFINEMENT

  • eO(1 + √κ −1 d1/4) expected oracle queries suffice for the quadratic-baseline algorithm under the stated augmented initialization and D2(ν0∥π) = O(1) condition.The refinement changes the quadratic part integrated exactly by conditional motion; the outer reflection and its gap remain unchanged.Source: §C.5 · p. 43
  • The quadratic baseline leaves residual strong convexity, sets normalized residual smoothness to θ, and preserves the small-step condition governing the outer reflection gap.In the rescaled coordinates, the outer gap remains g = √αη while the local collision scale changes from βη to θ.Source: §C.5 · pp. 43–44

D PROOF OF THE WARM-START WRAPPER

  • The warm-start wrapper compares a constant-D2-warm ideal coarse endpoint with a nearby algorithmic endpoint, then applies the same capped reflected kernel to both.Only the algorithmic endpoint is generated by the algorithm; the ideal endpoint supports the convergence argument.Source: D PROOF OF THE WARM-START WRAPPER · p. 45

D.1 POSTERIOR SAMPLERS USED BY THE WRAPPER

The wrapper uses implementable posterior interfaces and capped reflected finalizers, then combines exact proximal warmification with approximate conditional draws along adaptive centers. Work caps preserve deterministic query limits while controlling the total-variation error.

D.1 POSTERIOR SAMPLERS USED BY THE WRAPPER

  • The regular interface first constructs a constant-warm law and applies a reflected sampler, while the harmonic-base interface starts from a localized Gaussian and invokes exact-ULD/FORS.The regular interface serves intermediate- and large-dimensional regimes; the harmonic-base interface supplies the small-dimensional endpoint.Source: §D.1 · p. 45
  • Geometric, Poisson, and linearly convergent random-length operations can be capped with only logarithmic work factors and at most ξ total-variation change.A fixed fallback output is returned when a cap stops the routine.Source: §D.1 · p. 46
  • For constant B, either capped reflected finalizer uses eO(√κd1/4) oracle queries and remains a common kernel whose application cannot increase total-variation distance between inputs.For a D2-warm input, its output is within ε + ξ of π.Source: §D.1 · p. 47

D.2 IDEAL COARSE PROXIMAL CONTRACTION

  • The ideal coarse proximal chain becomes constant-D2 warm after the number of equal-step updates set by r = βu and αu = r/κ.The exponent gains across each exact proximal Gibbs update multiply, yielding the stated warmification bound.Source: §D.2 · p. 48

D.3 RANDOM CENTERS AND THE ALGORITHMIC PATH

  • Approximate conditional draws at adaptive observation centers can be coupled row by row with total mismatch at most δ, while capped work remains valid after paths diverge.The ideal coarse endpoint, rather than the algorithmic endpoint, is the law to which the contraction bound applies.Source: §D.3 · p. 49

D.4 COST OPTIMIZATION AND FINAL ERROR TRANSFER

The coarse-stage cost is optimized by choosing between harmonic-base and regular posterior interfaces across dimension regimes, then transferring the final guarantee through a capped reflected sampler. For a supplied point, localization is added to the wrapper cost to obtain the end-to-end bound.

D.4 COST OPTIMIZATION AND FINAL ERROR TRANSFER

  • eO(κ2/3d1/3 log(eB)) is the harmonic-base coarse-stage cost for d ≤ κ16/7; the regular-interface costs are eO(κd3/16 log(eB)) and eO(√κd1/4 log(eB)) in the other regimes.The regular-interface regimes split at d = κ8.Source: §D.4 · p. 49
  • The final capped reflected kernel contributes eO(√κd1/4) queries and transfers the coarse-stage approximation to the target within the allocated error budget.Applying one common Markov kernel preserves the total-variation bound between the ideal and algorithmic inputs.Source: §D.4 · p. 50
  • Every optimized coarse-cost branch is at most κ6/7d1/4, giving an envelope for the finite-divergence warm-start wrapper.The proof selects among the coarse routes by dimension regime.Source: §D.4 · p. 50

D.5 INITIALIZATION FROM ONE POINT

  • For initialization from a point, adding the one-time localization cost to the coarse-wrapper branch proves the stated supplied-point query bound.The localization step uses accelerated optimization followed by an explicit Gaussian draw.Source: §D.5 · p. 50

Related papers

Loading 2610.16248v1…