PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

Weiming Ou, Xiao Wang

arXiv:2609.12590v2math.STcs.LGmath.PRstat.TH

TL;DR

Sampling from smooth strongly log-concave targets with stochastic gradients raises the question of tight query complexity across accuracy, curvature, and noise. The paper gives a gradient-only sampler and matching fixed-dimensional minimax bounds, including the noiseless regime.

  • Problem

    For strongly convex, smooth targets, the query complexity dependence on TV accuracy and condition number was not jointly settled, and a useful characterization should also adapt to the gradient-noise level.

    Source: §1 · p. 3

  • Method

    A gradient-only sampler combines geometric preprocessing with variance-controlled Poisson acceptance, charging failed histories and transcript markers.

    Source: §1 · p. 3

  • Results

    For every fixed d ≥1, minimax expected query complexity is Θ(log(1 + κ) + σ2/(µε)), jointly over κ, σ2 ≥0, and 0 < ε ≤1/10.

    Source: §1 · p. 3, §2.1 · p. 8

  • Takeaways & Limitations

    At σ2 = 0, the tight complexity is Θ(log(1 + κ)), independent of ε, and the paper also gives a gradient-only exact sampler.

    Source: §1 · p. 3

    The results are fixed-dimensional information bounds, not dimension-uniform optimal rates or polynomial-time implementations.

    Source: §2.1 · p. 9

Abstract

from arXiv · show

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $\mu$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,\mu^{-1/2})$, and unbiased gradient oracles with variance at most $\sigma^2$, the minimax worst-case expected query complexity is $\Theta\left(\log(1+\kappa)+\frac{\sigma^2}{\mu\varepsilon}\right)$, jointly optimal for the condition number $\kappa:=L/\mu$, variance $\sigma^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $\sigma=0$, this tight complexity $\Theta\left(\log(1+\kappa)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+\kappa))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,\mu^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+\kappa)+\log(1+\sqrt{\mu}\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

1 Introduction

The section asks how sampling query complexity depends jointly on accuracy, curvature, and gradient noise, beyond bounds that establish only accuracy dependence. It presents fixed-dimensional matching bounds and distinguishes the paper’s gradient-only exact-sampling contribution from prior value-based results.

1 Introduction

  • Joint optimality in accuracy and condition number requires matching bounds as both parameters vary, while noise adaptivity must also recover the zero-noise regime.An accuracy-optimal bound alone may retain a large curvature factor, and fixing positive noise can hide the transition to noiseless sampling.Source: §1 · p. 3
  • For every fixed d ≥1, the paper establishes minimax complexity Θ(log(1 + κ) + σ2/(µε)), jointly over ε, κ, and σ2 ≥0.The construction uses geometric preprocessing and variance-controlled Poisson acceptance, while charging failed histories and transcript markers.Source: §1 · p. 3

1.1 Closest related work

  • The paper’s noiseless exact-sampling contribution is gradient-only sampling with a coarsely localized unknown mode, not accuracy-independent expected rejection cost alone.Chewi et al. give a scalar benchmark with a known mode and potential values, while Chewi et al. [13] give value-and-gradient bounds.Source: §1 · p. 3, §1.1 · p. 4
  • The paper analyzes Poisson rejection and randomized gradient integration under noisy, history-dependent replies, explicitly charging geometric preprocessing and random stopping.These principles have precedents in Chen et al. [6] and Beskos et al..Source: §1.1 · p. 4

2 Model and main minimax results

The section specifies a fixed-dimensional strongly convex, smooth potential class, a localized unknown mode, and conditional stochastic-gradient access with physical-query stopping. It presents a gradient-only sampling construction and matching minimax guarantees under these conventions.

2 Model and main minimax results

  • The potential class Cd(L, µ) comprises C1 functions on Rd satisfying the stated µ-strong-convexity and L-smoothness inequalities, for public parameters 0 < µ ≤ L.The curvature endpoints need not be attained, and no second derivative is assumed.Source: §2 · p. 4
  • Each physical query returns a full gradient vector with a conditional total-variance bound; replies may be history-dependent, and stopping must be visible in the physical-query filtration.Potential values, Hessians, proximal oracles, and convex-body sampling oracles are unavailable.Source: §2 · pp. 4–5

2.1 Sampling procedure and guarantees

  • The center pilot uses score estimates to certify a constant potential gap or select a cutting direction, rather than optimizing to accuracy ε.The rounding pilot then returns an ellipsoid intended to enclose a whole level set; when the pilots succeed, z locates the ellipsoid and T determines its shape.Source: §2.1 · pp. 5–6
  • The proposal combines a flat ellipsoidal region with full-support tails, adapting to the level-set geometry without discarding target mass.The sampler uses a radial proposal and directional derivative envelopes for its acceptance procedure.Source: §2.1 · p. 6
  • The constructive upper bound and minimax lower bound match up to dimension-dependent constants, jointly across κ, σ2, and ε.The displayed benchmarks have ratio at most 62Cd; these are fixed-dimensional information bounds, not dimension-uniform optimal rates or polynomial-time implementations.Source: §2.1 · pp. 8–9

3 Upper bound: geometric amortization and variance-controlled acceptance

The upper-bound analysis combines score-adaptive geometric cuts with a variance-controlled acceptance experiment. A compensated Poisson construction controls acceptance bias, while calibrated tolerances and explicit charging of failed histories yield the stated accuracy and expected-work guarantees.

3.1 Constant-energy geometry at additive cost

  • O(log(1 + κ)) geometric cuts and score-adaptive batching yield total cost O(log(1 + κ) + A/δ), without multiplying geometric search by statistical precision.The batching analysis sums dyadic error probabilities without a logarithmic union penalty and extends the cost bound to failed histories.Source: §3.1 · p. 9, §3 · p. 9

3.2 A compensated Poisson experiment instead of exponentiating an estimate

  • The Poisson no-mark experiment represents the exponential exactly, avoiding the bias from exponentiating an unbiased estimate.Compensating the negative derivative keeps the marking intensity nonnegative.Source: §3.2 · p. 10
  • With n = O(1 + A/ε), noise-induced acceptance bias is controlled and vanishes at A = 0; stopping after the first mark bounds processed work even when Q is large.The survival comparison uses conditional bounds at reached histories, not independent oracle replies, and does not require a moment bound on Q.Source: §3.2 · p. 10

3.3 Accuracy, failed histories, and physical stopping

  • Calibrated trial tolerances and caps bound the total TV error by 7ε/16 across acceptance, outer-cap fallback, and pilot failure.The components are at most ε/8 from normalization, ε/16 from the outer cap, and ε/4 from pilot failure.Source: §3.3 · p. 10
  • Including failed pilots, examined nodes, correction calls, and transcript markers gives E[T] ≤ CdS under physical-transcript stopping.The analysis charges failed-pilot work by its small probability and uses all-history proposal moments to control grid costs.Source: §3.3 · p. 10

4 Lower bound: noise and curvature encode different information

The lower bound separates noise and curvature costs using distinct scalar hard instances, then embeds those witnesses into full-vector algorithms. Rare informative replies force a noise-dependent cost, while finite-reply transcripts force logarithmic curvature dependence.

4 Lower bound: noise and curvature encode different information

  • Scalar witnesses are embedded as h(x1) plus a quadratic in the added coordinates, so the lower-bound arguments apply directly to full-vector algorithms.The added coordinates have exact gradients, preserve the scalar target law under projection, and leave total noise variance unchanged.Source: §4 · p. 11

4.1 Rare informative replies force the noise term

  • E[T] ≥ A/(24ε) follows by hiding an O(ε) gradient gap in rare oracle innovations, forcing enough physical queries to separate the target laws.The coupling argument applies at random stopping times and does not require a fixed query horizon or a positive lower bound on A.Source: §4.1 · p. 11

4.2 A finite-reply family forces logarithmic curvature cost

  • A finite-reply family has Θ(√κ) separated mass concentrations, while each query yields at most three replies, limiting information per query.With a uniform family index, TV accuracy gives decoding probability above 89/100; truncation and ternary transcript counting yield the logarithmic curvature lower bound in the large-curvature regime.Source: §4.2 · pp. 11–12
  • Combining the noise, curvature, and one-query lower bounds gives the stated worst-case lower-bound conclusion; these are bounds from different hard instances, not costs on one instance.The curvature construction uses exact gradients, which are admissible under every advertised variance ceiling.Source: §4.2 · p. 12

5 Exact sampling and the role of initialization

At zero noise, an uncapped gradient-only procedure gives exact samples with logarithmic condition-number cost. The section also treats supplied initialization information and shows that uniform guarantees over locations can require additional cost.

5 Exact sampling and the role of initialization

  • At σ² = 0, an accuracy-free gradient-only sampler returns an exact sample, terminates almost surely, and has worst-case expected cost at most C_d log(1 + κ).The guarantee uses physical-transcript stopping.Source: §5 · p. 12
  • The exact sampler is uncapped and is not obtained by setting ε = 0 in the finite-accuracy theorem.The quadratic case admits a sharper bound.Source: §5 · p. 12
  • With an arbitrary supplied ball centered at x0, the section gives an ε-TV sampler for potentials in the corresponding localized class.The stated result assumes x0 and R are supplied; no joint radius–noise optimality is claimed.Source: §5 · p. 12, At zero noise an almost surely… · p. 12

At zero noise an almost surely terminating exact sampler satisfies

  • Without a supplied radius, exact gradients still permit exact sampling from fixed x0 with an instance-wise guarantee, but finite instance-wise cost need not give a uniform bound over locations.At μ = 1 and L = 2, the worst-case noiseless expected minimax cost over a supplied radius R ≥ 64 is Θ(log(1 + R)); the obstruction is not per-instance and does not apply when L = μ.Source: At zero noise an almost surely… · p. 13

6 Conclusion

The conclusion states a fixed-dimensional joint query-complexity characterization and an exact-sampling result at zero noise.

6 Conclusion

  • The joint expected query bound is Θ(log(1 + κ) + σ²/(με)); at zero noise, an uncapped variant gives exact sampling with almost-sure termination.The bounds allow dimension-dependent constants and assert no accuracy-independent deterministic cap; sharper radius–noise dependence and finite-precision implementations remain open directions.Source: §6 · p. 13

A Extended related work

The related-work discussion distinguishes the paper’s fixed-dimensional stochastic-gradient model from value-based, structured-oracle, and algorithm-specific sampling results. It positions the contribution as joint optimality under its oracle and stopping conventions, alongside a gradient-only exact variant at zero noise.

Stochastic-gradient comparisons

  • Chen et al. [7] establish the inverse-accuracy exponent under bounded variance, while the paper identifies joint ε–κ optimality and the variance-only transition to zero noise as distinctions.A small variance ceiling does not imply a tail bound; admissible replies can still be rare and large at every positive variance.Source: A Extended related work · p. 16

Positioning and oracle model

  • The paper’s comparison is a joint fixed-dimensional minimax rate under an unknown mode, localization promise, conditional variance-bounded replies, and expected physical-call stopping.It states matching bounds for 1 + log(1 + κ) + A/ε, with constants depending only on fixed dimension, and no multiplicative curvature or logarithmic losses.Source: A Extended related work · pp. 16, 20

Exact-information benchmarks

  • Chewi et al. obtain a scalar Θ(log log κ) benchmark with known mode and potential values, so it does not replace the unknown-mode localization cost studied here.Their logarithmic accuracy cost concerns a capped rejection procedure, unlike their constant expected additional cost for exact sampling.Source: A Extended related work · p. 16
  • Chewi et al. [13] give fixed-dimensional value-and-gradient bounds; the paper derives exact expected O(log(1 + κ)) value-and-gradient rejection from their geometry, distinct from its gradient-only result.The paper’s additional noiseless guarantee is gradient-only exact sampling with a coarsely localized unknown mode.Source: A Extended related work · pp. 16–17

Stochastic-gradient comparisons

  • Chatterji et al. [5] provide a stochastic-gradient lower-bound framework, but their inverse-square accuracy comparison is restricted by curvature conditions and does not contradict the present inverse-linear rate.Their bound does not extend to arbitrarily small accuracy at a fixed positive strong-convexity parameter.Source: A Extended related work · p. 17

Rejection-sampling precedents

  • Classical rejection methods use exact evaluations, whereas this paper’s noisy-gradient construction separately controls preprocessing failure, clipping bias, and stopping costs.Gilks and Wild use tangent envelopes; Beskos et al. use a Poisson no-point identity for path integrals, which this proof applies on a deterministic segment with gradient-derived envelopes.Source: A Extended related work · pp. 17–18

Algorithm-specific and structured-oracle comparisons

  • Langevin analyses address particular recursions rather than minimax query complexity; Wasserstein guarantees do not by themselves establish the TV guarantees required here.Finite-sum variance-reduction methods such as those of Chatterji et al. [4] use correlated component-gradient access unavailable from an arbitrary conditional variance oracle.Source: A Extended related work · pp. 18–19

Proximal and diffusion-path comparisons

  • Proximal and diffusion-path methods provide multivariate benchmarks under different access and initialization assumptions, rather than implementations of the arbitrary conditional variance oracle here.The cited results use value access, proximal access, supplied warm starts, or exact gradients; the present construction instead analyzes a proposal for the original target.Source: A Extended related work · pp. 19–20

B Subroutine and implementation guide

The guide connects the sampler’s named finite routines to their proof-level notation, parameter choices, and execution accounting.

B Subroutine and implementation guide

  • The named routines abbreviate finite constructions rather than additional oracles, and the guide maps their symbols to proof notation.The working-ellipsoid symbols cE and QE become c and Q in the pilot proofs; the pilot batch size b is denoted n there.Source: B Subroutine and implementation guide · p. 20
  • The center and rounding routines have call and update caps with fallbacks; the rounding output determines U and q for finite radial sampling.The rounding routine’s terminal score threshold is 4, and its ellipsoid contraction yields z and T in (C.53).Source: B Subroutine and implementation guide · p. 20
  • Directional grids, derivative conventions, and a finite rectangle mixture specify correction positions, while repeated locations still incur new physical calls.Marker calls, the overflow branch, and category weights are explicit in the implementation.Source: B Subroutine and implementation guide · p. 20
  • The proof accounts for failed pilots and envelopes, ignored marker replies, and the zero-radius branch; the zero-noise exact variant removes rejection caps.The capped procedure has pathwise finite execution, whereas the exact modification terminates almost surely.Source: B Subroutine and implementation guide · p. 20

C Proof of the Upper Bound

  • In the global sampler, B = 3/64 and bacc = 10; algorithms operate in normalized coordinates and divide outputs by √µ before returning them.Local pilot statements with variable B retain their stated ranges.Source: C Proof of the Upper Bound · p. 21

C.1 Conditional averages and a constant-gap center

This section develops procedures for finding a center with bounded potential gap using adaptive gradient estimates, deterministic shallow cuts, vertex-based certification, and a capped pilot. From that center, it constructs a fixed-dimensional, full-support proposal with bounded physical calls, a high-probability enclosure guarantee, and positive dimension-dependent ideal acceptance mass on successful pilot histories.

C.1 Conditional averages and a constant-gap center

  • Adaptive conditional averages satisfy a mean-square error bound and a conditional tail bound even when batches are entered at history-dependent times.The centered replies are martingale differences; projection onto a unit vector fixed before the calls inherits the scalar variance bound.Source: §C.1 · p. 21
  • The deterministic shallow-cut update contains the prescribed halfspace and contracts ellipsoid volume by at least e^(-a_d).The inclusion follows from the unit-coordinate interval argument for α < 1/d.Source: §C.1 · p. 22
  • Doubling batches at the 2d test vertices yield, on an event measurable at termination, accurate returned scores and a bounded total number of calls.On that event, the stopping batch size is at most max{1, 4Λ/fM}, and the sum of fresh stage sizes is at most twice that size.Source: §C.1 · pp. 23–24
  • On accurate estimated iterations, the vertex-score test returns a center with gap at most 3B/4; otherwise, the update preserves the protected level set K_b.The certificate uses symmetric test vertices, while free geometric cuts also preserve K_b.Source: §C.1 · pp. 25–26
  • Volume comparisons bound reciprocal energies over valid prefixes even when energy scales are nonmonotone, allowing costs to be summed without a log κ factor multiplying A/δ.The bounds apply through a final estimated iteration before its accuracy is decided.Source: §C.1 · pp. 22, 26
  • When all estimation events hold, the pilot returns a center with gap at most 3B/4, and the global call cap does not interrupt that successful run.The proof establishes the claimed success guarantee with a stronger upper bound of δ/2.Source: §C.1 · p. 28
  • The capped pilot has a deterministic physical-call bound, which also bounds its expected cost under every admissible oracle.The proof notes that costs incurred after an erroneous estimate are not discarded.Source: §C.1 · p. 28

C.2 Constructing a proposal in fixed dimension

  • With conditional probability at least 1 − δ, proposal construction returns z and invertible T enclosing the level set between z + TBd and z + 20TBd.The procedure uses at most Bgeom physical calls on every execution.Source: §C.2 · p. 29
  • A reciprocal-energy bound controls the number of testing rounds, while adaptive batches provide observable estimates with bounded calls and failure probability.The batching guarantee is conditional on the incoming history of a testing round.Source: §C.2 · pp. 31–32
  • If every test is good, proposal construction terminates before the Hκ outer-round cap, so the finite caps do not disrupt an all-good execution.The all-good execution also stays within the stated geometric call budget.Source: §C.2 · pp. 31, 32, 34
  • The proposal is a normalized full-support density with an explicit sampling rule requiring no oracle queries, including when the rounding procedure falls back.The rule uses a radial mixture and has no internal rejection loop or convex-body sampling oracle.Source: §C.2 · pp. 34–35
  • The proposal’s first- and second-moment bounds hold on every history, independent of the oracle’s past errors or whether the pilot succeeds.The bounds follow from the explicit radial mixture and the uniformly bounded center and proposal parameters.Source: §C.2 · p. 36
  • The center and rounding pilots use δm = ε/8 and δq = ε/8, and their successful-pilot event is defined from the implemented transcript.The pilot states and return branches can be reconstructed from the physical transcript.Source: §C.2 · pp. 36–37
  • On successful pilot histories, the potential gap at the returned center is at most B, and ideal acceptance mass is at least p0 > 0, depending only on d.The proposal domination implies h > 1 and 1 + I(x) ≤ 2(1 + h(x)).Source: §C.2 · p. 37

C.3 Directional envelopes and acceptance at every noise level

This section develops directional envelopes and margins to control target-gradient mass and enable finite noisy acceptance across noise levels. It establishes accuracy and closeness to the target under specified pilot and envelope histories, with the final law controlled by conditional acceptance bounds, all-reject probability, and pilot failure.

C.3 Directional envelopes and acceptance at every noise level

  • On a good pilot history, the absolute derivative mass is at most I(x) + 2B, while the ray length satisfies r^2 ≤ 4(I(x) + 2B).These bounds allow positive and negative derivative mass to be treated separately even when the gradient at the center is large.Source: §C.3 · pp. 37–38
  • The geometric grid yields an upper envelope for any nondecreasing κ-Lipschitz function, with a terminal remainder of at most 1/2 in the integral bound.Its construction uses ordinary intervals with halving lengths and a terminal rectangle.Source: §C.3 · p. 38
  • With probability at least 1−δ, the noisy envelopes dominate both derivative parts and have combined integral at most 2∫|w(t)|dt + 16.The guarantee is conditional on the history before envelope construction; each envelope’s integral is at most twice its corresponding true mass plus 8.Source: §C.3 · p. 39
  • Along a proposed ray, the proposal-potential derivative is zero in its flat region and is dominated by the target derivative after leaving that region.The comparison holds on a good pilot; it enables compensation for negative target-derivative mass while keeping the marking intensity nonnegative.Source: §C.3 · pp. 40–41
  • On a good pilot and completed good envelope history, the marking intensity has two-sided margins, and the computable normalizer satisfies Q/ℓ < 68.The margins support a uniform mark probability and make clipping affordable through variance-controlled bias.Source: §C.3 · pp. 41–42
  • The analysis uses an ideal Poisson-mark identity for acceptance, while the implementable procedure uses finitely many categories and caps the number of correction nodes.For Poisson mean Q and mean mark probability ℓ/Q, the probability of no marks is e^−ℓ; the finite procedure assigns a remaining probability mass to category H + 1.Source: §C.3 · pp. 42–43
  • On completed good envelope histories, acceptance error is at most 3τ/8; accounting for grid failure gives error below τ.At x = m, the explicit zero-radius branch has zero error.Source: §C.3 · p. 45
  • For each reached node, the implementation freshly samples its position, makes exactly n oracle calls there, and records its rejection mark with a marker call.A mark ends the node stage and rejects the trial; Nc unmarked nodes accept it.Source: §C.3 · p. 45
  • After any reached-trial history, the proposal law conditional on acceptance is within ε/8 of the target, even when oracle kernels change adaptively.Mixing over the first accepting trial preserves this bound.Source: §C.3 · p. 46
  • The probability all K trials reject is at most ε/16; conditional on a good pilot history, the output law is within 3ε/16 of the target.Failed pilot histories contribute at most ε/4 to total variation.Source: §C.3 · p. 46
  • Envelope failure is included in each trial’s conditional acceptance error rather than union-bounded over K trials; random integration positions add no approximation error when A = 0.Only clipping bias from oracle noise is bounded in Lemma C.18.Source: §C.3 · p. 47

C.4 Operational completion and endpoint cases

The completed sampler charges preprocessing, failed histories, ignored replies, and markers while establishing operational stopping and expected cost. At zero variance it yields exact sampling, with separate endpoint handling for κ = 1.

C.4 Operational completion and endpoint cases

  • The capped sampler’s complete construction has unconditional expected query cost at most C_dS, charging grid, node, marker, pilot, and failure-history costs.The physical transcript makes stopping decisions measurable, and ignored replies remain part of the conditioning history for later oracle calls.Source: §C.4 · pp. 48–50
  • At zero variance, removing the outer-trial and Poisson-overflow caps gives an exact sampler with O(log(1 + κ)) expected queries.Acceptance is at least p0, and early rejection bounds expected processed nodes independently of Poisson intensity.Source: §C.4 · pp. 50–51
  • For every positive ε, the capped construction terminates on every specified finite-real-reply path, whereas the uncapped exact algorithm allows exceptional infinite rejection paths.The capped construction retains the same expected asymptotic cost when A = 0.Source: §C.4 · pp. 47, 51
  • When κ = 1, the target is Gaussian with an unknown shift, and averaging replies at zero gives an accuracy guarantee from the mean error’s second moment.The construction also works without a localization assumption when L = µ; if A = 0, one reply gives an exact sample.Source: §C.4 · pp. 51–52

D Proof of the Lower Bound

  • The lower-bound appendix separates noise, curvature, and constant obstructions before combining them at the same public parameter tuple.The minimax cost dominates each witness family separately; the proof does not require their costs to add on one instance.Source: D Proof of the Lower Bound · p. 52

D.1 Hard-family embedding for vector algorithms

  • The lower-bound proof embeds scalar targets into vectors by adjoining a fixed standard Gaussian, preserving the scalar first marginal and contracting total variation under projection.The embedding supports lower bounds against fully vector-valued algorithms, including queries outside the first-coordinate axis.Source: §D.1 · p. 53

D.2 The stochastic-noise lower bound

The stochastic-noise lower bound constructs two localized potentials with separated target laws and valid noisy gradient oracles. Coupling their executions until an informative reply forces expected query cost proportional to the variance budget divided by accuracy.

D.2 The stochastic-noise lower bound

  • The stochastic-noise lower-bound construction gives a cost proportional to A/ε for the stated public parameter regime.Its witnesses use fresh, conditionally unbiased replies with conditional variance exactly A and allow adaptive vector queries and random stopping.Source: §D.2 · pp. 53, 56
  • The two potentials have modes inside the localization promise and a gradient gap independent of the query, so remote queries cannot amplify that gap.Their normalized target laws are separated, while their oracle replies agree until the first informative Bernoulli event.Source: §D.2 · pp. 54–55
  • Fresh Bernoulli-kernel replies satisfy the stipulated conditional oracle contract with variance exactly A, including at adaptive and unbounded query points.The Bernoulli flag is not a separate observation.Source: §D.2 · p. 55
  • Coupling the runs through their common execution converts target-law separation and uniform TV accuracy into a lower bound for arbitrary expected stopping.The argument includes zero-call branches, random output kernels, and rare arbitrarily long executions.Source: §D.2 · pp. 55–56

D.3 The scalar curvature lower bound

The scalar curvature lower bound uses a localized family of threshold-ramp potentials whose target mass concentrates on disjoint intervals. A finite-branch decoding argument then forces a logarithmic curvature cost, even with exact gradients.

D.3 The scalar curvature lower bound

  • This curvature obstruction applies to the stated localized gradient-only model, and the finite-branch argument is not claimed to survive exact mode-revealing values.The paper identifies a separate family for why unrestricted initialization cannot have a uniformly finite bound in general.Source: §D.3 · p. 56
  • The localized threshold-ramp family yields the curvature lower bound N⋆ ≥ Bκ using exact gradients and arbitrary adaptive vector queries with expected stopping.The witness modes lie inside the prescribed localization region and attain curvature endpoints 1 and κ.Source: §D.3 · pp. 56, 59
  • The family’s target distributions concentrate on pairwise disjoint intervals, allowing an output-based decoder to identify the hidden instance with high probability.The intervals have strict gaps, and the normalized tail probability outside each interval is below 1/100.Source: §D.3 · pp. 57–58
  • Each exact-gradient query has at most three possible replies across the family, so a truncated transcript tree has at most 3H_tree leaves.The resulting decoding bound converts the finite branching factor into a lower bound on expected queries.Source: §D.3 · pp. 58–59

D.4 The constant lower bound and completion

A pair of separated Gaussian targets establishes a constant lower bound under physical stopping. Combining this with the noise and curvature obstructions proves the joint lower benchmark and the paper’s constant-factor characterization.

D.4 The constant lower bound and completion

  • Every admissible uniformly accurate algorithm must make at least one query in the worst case, including when A = 0.A common zero-query output law cannot be within ε in total variation of both separated Gaussian targets.Source: §D.4 · pp. 59–60
  • The curvature obstruction gives N⋆ ≥ S/62 across both curvature ranges, including κ = 1.For large κ the proof derives a logarithmic curvature lower bound; the remaining range uses the constant lower bound.Source: §D.4 · p. 60
  • Combining the three obstructions proves the joint minimax characterization, with the upper-to-lower benchmark ratio bounded by 62C_d for each fixed dimension.The bound is uniform in L, µ, σ, and ε throughout the stated regime.Source: §D.4 · p. 60

E Proofs of the initialization extensions

The initialization extensions remove the localization-ball requirement by translating the target and supplying a more conservative curvature bound. They give noisy and exact sampling bounds for supplied or unknown initial distances, with a separate one-query endpoint when κ = 1.

Corollary 5.3

  • For a supplied radius R, translation yields a noisy upper bound with condition number κΓ_R and normalized variance Γ_Rσ^2/µ; its radius-noise factor is not claimed optimal.Here Γ_R = max{1, µR^2}; no matching lower bound for its factor Γ_Rσ^2/(µε) is asserted.Source: E Proofs of the initialization… · p. 61
  • With zero variance and a supplied radius R, the translated exact sampler costs O(log(1 + κ) + log(1 + √µR)) expected queries.The sampler receives only a more conservative lower-curvature bound; the target potential and temperature are unchanged.Source: E Proofs of the initialization… · p. 61

Corollary 5.4

  • From any initial point x_0, one exact gradient reply certifies a radius around the minimizer and enables exact sampling without knowing the initial distance.The resulting cost is 1 + C_d log(1 + κb_Γ), where b_Γ = max{1, ||g_0||^2/µ}; this certificate is not valid for a noisy reply.Source: E Proofs of the initialization… · pp. 61–62

Quadratic endpoint

  • At κ = 1, averaging n replies and adding Gaussian noise gives TV error at most σ^2/(2µn), while one query suffices for exact sampling at zero noise.The quadratic argument does not use a bound on the mode location.Source: E Proofs of the initialization… · p. 62

F A value-and-gradient benchmark for the noiseless comparison

This appendix gives a value-and-gradient benchmark for a known-mode setting, distinct from the paper’s gradient-only sampler. A level-set geometry supports exact rejection sampling with accuracy-independent expected cost, while truncation gives a deterministic accuracy-dependent budget.

Value-based rejection benchmark

  • With a known mode and value access, the level-set sandwich yields an exact sampler using O(log(1 + κ)) expected queries overall.The expected additional value-query count is at most e^2 d!(2ρ)^d; physical-transcript stopping changes the bounds by only a constant factor.Source: F A value-and-gradient benchmark for… · pp. 63–64
  • For 0 < ε < 1, truncating the exact sampler gives an ε-TV sampler with deterministic budget O(log(1 + κ) + log(1/ε)).The truncation couples the capped procedure to the uncapped sampler; their outputs differ only if the first m_ε trials reject.Source: F A value-and-gradient benchmark for… · pp. 63–64

Scope

G A fixed-curvature lower bound for unrestricted localization

This appendix establishes location hardness at fixed curvature for unrestricted minimizer locations. Its nested scalar family forces logarithmic expected query cost as the supplied localization radius grows, even with adaptive queries and random stopping.

Hard instance

  • The construction uses a depth-m binary family with radius R_m = 8m + 1, uniformly bounded curvature, and minimizers separated enough for accurate samples to decode the hidden signs.Each target places more than 99/100 of its mass within distance four of its mode.Source: G A fixed-curvature lower bound for… · pp. 64, 66

Scope

  • The fixed-curvature lower bound applies in every fixed dimension by adding independent standard Gaussian coordinates to the scalar construction.The supplied-radius conclusion is obtained by choosing m = ⌊log_8 R⌋ − 1 for R ≥ 64.Source: G A fixed-curvature lower bound for… · pp. 65, 67

Information argument

  • An augmented oracle exposes only the hidden prefix needed to answer each query; each query reveals at most two new signs in expectation.Further revelations require successive independent signs, each with conditional probability at most one half.Source: G A fixed-curvature lower bound for… · pp. 65–66
  • Decoding with constant success requires a linear number of exposed signs, forcing a linear expected query cost in m even under adaptive random stopping.The unrevealed suffix remains uniform at the stopping time, so the stopping event itself cannot reveal its signs.Source: G A fixed-curvature lower bound for… · pp. 65, 67

Location lower bound

  • For R ≥ 64, the noiseless expected minimax cost at µ = 1 and L = 2 is Θ(log(1 + R)), uniformly for 0 < ε ≤ 1/10.This is a worst-case-over-locations result, not a per-instance lower bound, and it does not apply to the quadratic endpoint L = µ.Source: G A fixed-curvature lower bound for… · pp. 65, 67

Related papers

Loading 2609.12590v2…