acceptodds
Under review as a conference paper at ICLR 2027

Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

Abstract

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension . For -strongly convex, -smooth potentials with unknown minimizers in the ball , and unbiased gradient oracles with variance at most , the minimax worst-case expected query complexity is , jointly optimal for the condition number , variance , and TV accuracy . In the noiseless setting , this tight complexity is independent of . Moreover, a gradient-only sampler generates an exact sample with worst-case expected queries. Without previous ball , exact sampling from any initial point 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Tight complexity, stochastic gradient oracle, fixed dimension

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_RU7AOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors provide tight guarantees for well-conditioned logconcave sampling with stochastic oracles.

Critical strengths
  1. This paper addresses an important problem in logconcave sampling: what is the complexity of of sampling with stochastic gradient oracles.
Critical weaknesses
  1. The paper reads to me as if it was one-shot by AI: the authors do not provide good intuition for the proof techniques (especially what components are from prior work and what are novel), and the writing/presentation is very poor.
Questions for authors

I strongly request the authors to consider cleaning up the paper before resubmitting to a new conference. I think the main ideas can likely be conveyed in a paper with half the length.

1 comment

Thank you for raising the presentation concern. We agree that readers should be able to identify the central ideas and distinguish inherited tools from new analysis. We respectfully disagree with the overall assessment and would like to identify the explanations and attribution already present, together with the concrete additions.

The manuscript provides specific explanations in its main text: Section 3.1 explains why reciprocal-energy amortization prevents geometric localization from multiplying the noise cost; Section 3.2 explains the bias from exponentiating an estimate and the role of Poisson compensation, marking margins, and conditional survival; Section 3.3 explains why failed histories and random stopping must be charged. Sections 4.1–4.2 explain the two lower-bound mechanisms. These are the conceptual links underlying the joint result.

The attribution is also explicit. Section 1.1 and Appendix A distinguish the known rare-reply lower bound, classical geometry, and Poisson rejection from the additional joint analysis. We have now added the specific credit to Chen et al., Theorem 3.2, beside the acceptance construction. Appendix B maps the algorithmic routines to their implementations. The revision also makes the full dimension constant explicit, clarifies the two pilot-coupling arguments, and adds Appendix H's numerical checks and a proof for the tested zero-noise specialization.

We have disclosed AI use and remain responsible for the claims and proofs. We appreciate the recommendation for greater concision; the appendix records the conditional-noise, failed-history, and stopping details supporting the guarantees. The revision makes the attribution, limitations, and verification more explicit. We respectfully ask that the revised submission be assessed on these concrete contributions, arguments, and limitations.

Reviewer_iqwROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies sampling from a μ\mu-strongly log-concave, LL-smooth target in a fixed dimension dd, with access only to unbiased stochastic gradients of variance at most σ2\sigma^2. The mode is unknown but lies in the ball B(0,μ−1/2)B(0,\mu^{-1/2}), and accuracy is measured in total variation. The main result is the minimax expected query complexity Θd(log⁡(1+κ)+σ2/(με))\Theta_d(\log(1+\kappa)+\sigma^2/(\mu\varepsilon)), where κ=L/μ\kappa=L/\mu (Theorems 2.2 and 2.3). The upper bound uses ellipsoid-based localization and rounding from noisy gradients, a radial proposal, and a Poisson-marking acceptance step with clipped noisy marks. The lower bound combines a rare-reply noise instance with a finite-reply family that gives Ω(log⁡κ)\Omega(\log\kappa). At σ=0\sigma=0 the method returns an exact sample with O(log⁡(1+κ))O(\log(1+\kappa)) expected queries (Corollary 5.1). The paper has no experiments.

Critical strengths

S1. A correct and carefully built result. The upper bound has an additive dependence on κ\kappa, while the bounded-variance bound of "High-accuracy log-concave sampling with stochastic queries" (Chen, Chewi, Daskalakis, Rakhlin) multiplies the noise term by κd\kappa\sqrt d. That paper leaves the joint dependence open (Section 4.2), so the fixed-dimension answer here is a real step. I checked the load-bearing steps and found no error. These are the clipping bias and the survival recursion (Lemmas C.17 and C.18), the summable cost of the pilots (eq. 3.1), the TV budget 7ε/167\varepsilon/16, and both lower bounds (Propositions D.1 and D.2). The oracle model is general. Replies may depend on the whole history, and failed runs and stopping are fully charged.

S2. Honest positioning. Appendix A compares the results with the closest work in detail and states which ingredients are not new. Appendix F derives the value-based exact sampler from prior work only to make the comparison fair. Section 5 separates the cost of the unknown location from the cost of sampling (Proposition 5.5).

Critical weaknesses

W1. Most parts of the result are already known. The paper itself says that neither the 1/ε1/\varepsilon term nor the rare-reply mechanism is new. The noise lower bound Ω(σ2/(με))\Omega(\sigma^2/(\mu\varepsilon)) is Proposition 4.1 and Remark 6 of Chen et al. It is stated there for a fixed horizon and here for the expected query count. For d≥2d\ge2, the Ω(log⁡κ)\Omega(\log\kappa) term is Theorem 4 of "Query lower bounds for log-concave sampling" (Chewi, de Dios Pont, Li, Lu, Narayanan), which holds with a known mode and with value and gradient access. Theorem 49 of the same paper gives O(log⁡κ+polylog(1/ε))O(\log\kappa+\mathrm{polylog}(1/\varepsilon)) in fixed dimension with value access. For d=1d=1, the family of Proposition D.2 encodes the location of the mode at resolution κ−1/2\kappa^{-1/2}. With a known mode the one-dimensional rate is Θ(log⁡log⁡κ)\Theta(\log\log\kappa) ("The query complexity of sampling from strongly log-concave distributions in one dimension", Chewi, Gerber, Lu, Le Gouic, Rigollet). So in d=1d=1 the term log⁡κ\log\kappa is the cost of locating the mode under the ball promise. The noiseless exact sampler follows from Theorem 49 of Chewi et al. once the truncation is removed, as Appendix F shows. The acceptance step follows FORS ("High-accuracy sampling for diffusion models and log-concave distributions", Chen, Chewi, Daskalakis, Rakhlin). Theorem 3.2 of the stochastic-query paper already uses a clipped stochastic-gradient path estimator, and the submission does not credit this. What remains new is the gradient-only localization under history-dependent noise and the analysis of clipped noisy marks. This is careful work, but it uses standard tools: dyadic batching, a volume potential and a survival recursion.

W2. The constant CdC_d is never stated, and the proof makes it very large. Theorem 2.2 gives E[T]≤CdS\mathbb E[T]\le C_dS with no value for CdC_d. The proof sets γ=1/(8d)\gamma=1/(8d) (C.3), ρ=20d/γ=160 d3/2\rho=20\sqrt d/\gamma=160\,d^{3/2} (C.36) and p0=e−11/(ρdDd)p_0=e^{-11}/(\rho^dD_d) (C.58). The algorithm itself uses p0p_0. Equation (C.91) sets τ=p0ε/16\tau=p_0\varepsilon/16 and the batch size n=⌈256A/τ⌉n=\lceil256A/\tau\rceil, so each correction node spends about 4096 σ2/(μp0ε)4096\,\sigma^2/(\mu p_0\varepsilon) queries. Here 1/p01/p_0 is about 5⋅1075\cdot10^7 for d=1d=1, 5⋅10115\cdot10^{11} for d=2d=2 and 102610^{26} for d=5d=5. So in the noise-dominated regime the new bound beats O~(κd(1+σ2/(με)))\tilde O(\kappa\sqrt d(1+\sigma^2/(\mu\varepsilon))) of Chen et al. only when κd\kappa\sqrt d exceeds 4096/p04096/p_0, about 2⋅10112\cdot10^{11} even in d=1d=1. The ratio of the upper and lower bounds is "at most 62Cd62C_d" (Section 2), and CdC_d is at least this large. The introduction motivates the work by ill-conditioned targets, where "an accuracy-optimal bound can still overestimate the cost by a large factor when κ grows". As proved, the bound improves on prior work only for very large κ\kappa. The asymptotic statement for fixed dd remains correct, but the paper should state CdC_d and qualify the comparison.

Questions for authors

Q1. Regarding W2, what is the explicit dependence of CdC_d on dd? Can the acceptance rate p0p_0 be improved, or is a factor dΘ(d)d^{\Theta(d)} unavoidable for this kind of rejection scheme?

Q2. Regarding W1, can you state precisely which parts of Theorems 2.2 and 2.3 do not follow from Chen et al. (Proposition 4.1, Theorem 3.2) and Chewi et al. (Theorems 4 and 49)? Please also discuss Theorem 3.2 of Chen et al. next to the acceptance step.

Q3. For d=1d=1 and a known mode, does the gradient-only setting give Θ(log⁡log⁡κ)\Theta(\log\log\kappa)? If yes, the log⁡κ\log\kappa term is purely the cost of locating the mode, and the paper should say so.

Q4. A suggestion that would raise my score: a small numerical check in d=1d=1 and d=2d=2. For example, a goodness-of-fit test of the exact sampler at σ=0\sigma=0, and the query count as a function of κ\kappa and σ2/ε\sigma^2/\varepsilon. The AI use statement says that the upper-bound algorithm and its proof were proposed by AI tools, so a direct check of the sampler would add confidence.

Q5. Clarification. The claim that the cost at σ=0\sigma=0 does not depend on ε\varepsilon holds for the expected count. Appendix F suggests that a fixed budget needs an extra log⁡(1/ε)\log(1/\varepsilon). Could this be stated in the main text?

3 comments

Thank you for the detailed comparison and concrete verification requests. We have added an explicit full constant, credited the clipped estimator beside the acceptance discussion, and incorporated numerical validation into Section 5 and Appendix H. All newly added or revised text in the manuscript is highlighted in blue.

W1 / Q2: What is new relative to Chen et al. and Chewi et al.?

We agree that the individual ingredients and several lower-bound orders have precedents. The revised manuscript distinguishes them as follows.

  1. Theorem 2.2: the joint upper bound. The contribution is

    \le C_d\left[ 1+\log(1+\kappa) +\frac{\sigma^2}{\mu\varepsilon} \right]$$ using only gradient replies, with an unknown coarsely localized mode, history-dependent conditional noise, and every preprocessing and failed-history cost included. Chen et al.'s bounded-variance upper bound retains multiplicative curvature dependence. Chewi et al.'s Theorem 49 supplies a value-and-gradient benchmark. Neither theorem directly gives this joint gradient-only guarantee.
  2. Acceptance primitives. Poisson rejection and gradient-path integration are credited to FORS and earlier work. Chen et al.'s stochastic-query Theorem 3.2 already uses a clipped stochastic path-gradient estimator; we now cite it explicitly at the start of Section 3.2, beside the acceptance construction. The additional analysis here couples gradient-only envelopes with two-sided marking margins, a conditional survival recursion, and early rejection. Together with reciprocal-energy amortization of the pilots, these estimates control error and total expected work without multiplying the geometric and noise costs. We do not claim the standard primitives themselves as new.

  3. Theorem 2.3: the lower bound. The inverse-accuracy term and rare-reply mechanism are already present in Chen et al., Proposition 4.1 and Remark 6. Our proof adapts the argument to arbitrary adaptive stopping measured by expected physical queries and combines it with the curvature term uniformly in the stated parameters. For d≥2d\ge2, the Ω(log⁡κ)\Omega(\log\kappa) order is already known from Chewi et al., Theorem 4, even with known mode and stronger oracle access. Our scalar unknown-mode construction establishes the corresponding obstruction for the present model also when d=1d=1. We therefore do not claim the logarithmic lower-bound order itself as new in dimensions d≥2d\ge2.

  4. Exactness. Accuracy-independent expected exact rejection with value access is not claimed as novel. Appendix F derives that benchmark using a full-support proposal from Chewi et al.'s geometry. Our additional zero-noise result is gradient-only exact sampling with an unknown localized mode and fully charged expected cost. Removing a trial cap alone does not remove a spatial truncation of the proposal.

Section 1.1 and Appendix A give the corresponding oracle, initialization, and stopping distinctions.

W2 / Q1: The explicit constant and the acceptance probability

We agree with the reviewer's calculation and its practical implication. Appendix C.4 now gives a complete derivation of

\rho &=160d^{3/2},\\ D_d &=1+4^dd!\sum_{k=0}^{d-1}\frac{4^{-k}}{k!},\\ p_0 &=\frac{e^{-11}}{\rho^dD_d},\\ C_d^{\mathrm{cert}} &= 2^{69}d^{12} \left(1+\log\frac{1}{p_0}\right)^2p_0^{-2}. \end{aligned}$$ This certificate bounds the entire expected query cost, including the two pilots, grids, correction nodes, failed histories, and all markers. It is distinct from $4096/p_0$, which is only the coefficient of $X=\sigma^2/(\mu\varepsilon)$ in the correction batch. For reference, | Quantity | $d=1$ | $d=2$ | | --- | ---: | ---: | | $p_0^{-1}$ | $4.790\times10^7$ | $5.028\times10^{11}$ | | $4096/p_0$ | $1.962\times10^{11}$ | $2.059\times10^{15}$ | | $C_d^{\mathrm{cert}}$ | $4.728\times10^{38}$ | $4.772\times10^{50}$ | The displayed certificate satisfies $$\log p_0^{-1}=\frac52d\log d+O(d),\qquad\log C_d^{\mathrm{cert}}=5d\log d+O(d).$$ These are conservative guarantees, not empirical execution costs. In particular, $p_0$ is a lower bound on acceptance, not its actual value. The main text now explicitly limits the comparison to fixed-dimensional asymptotic dependence and disclaims practical superiority at moderate $\kappa$. For the specific rejection scheme, Appendix C.4 now gives a sharper diagnosis. For a standard Gaussian with exact mode supplied, the best admissible outer ellipsoid yields $$p_{\mathrm G}=e^{-10}\frac{\Gamma(d/2+1)}{D_d},\qquad\log p_{\mathrm G}^{-1}=\frac12d\log d+O(d).$$ Thus $d^{\Theta(d)}$ expected trials remain even with ideal rounding in this fixed radial template. Improving rounding alone is insufficient. This does not prove the full $p_0^{-1}$ or $C_d^{\mathrm{cert}}$ dependence necessary, or constrain other proposals or samplers. In particular, Corollary 5.2 samples the Gaussian by a separate one-query construction at zero noise.

Q4: Numerical validation in dimensions one and two

Thank you for this suggestion. We have added numerical validation to Section 5 and Appendix H, covering the original geometric and acceptance components, complete-output distributional checks, and physical-query costs. The experiments provide the following complementary evidence.

1. The original components are checked against the properties used in their proofs.

We implemented the original zero-noise centering and rounding routines on 224 shifted or rotated instances, including 192 nonquadratic instances and public condition numbers up to κ=106\kappa=10^6. All returned centers and ellipsoids passed the post-run numerical checks: the largest center gap was 0.002810<3/640.002810<3/64, the largest inner-boundary upper bound was 0.074901<10.074901<1, and the smallest outer-boundary lower bound was 7.71558>17.71558>1. The two-dimensional boundary checks include an analytic interpolation remainder between evaluated angles. These checks examine the geometric conditions required by the rejection construction, including both sides of the ellipsoidal sandwich.

We also ran 10,000 conditional continuations in each of 16 cases for the original padded-grid Poisson kernel. Every analytical survival probability e−ℓe^{-\ell} lies within its corresponding confidence interval, with at least 95%95\% simultaneous coverage across the cases. Four additional controls use supplied geometry to exercise the nonflat proposal region U′>0U'>0. This checks the implemented acceptance probabilities against the Poisson identity, including proposal-derivative compensation. These are conditional kernel checks with a fixed completed grid and a passed prefactor coin, not complete target samples.

2. Complete-output tests use separately computed reference distributions and examine joint behavior.

For feasible complete-output experiments, we use the separately specified Gaussian-proposal, gradient-only sampler in Appendix H.2. Its uncapped zero-noise exactness in real arithmetic is proved in Proposition H.1. The sampler receives only gradient replies and public parameters; potential values, the mode, and reference CDFs are used exclusively by the evaluator.

The primary zero-noise experiments contain 12 configurations with 5,000 independent outputs each, covering d=1,2d=1,2, Gaussian and asymmetric nonquadratic targets, and public κ∈{2,16,128}\kappa\in\{2,16,128\}, with shifted modes and rotations in dimension two. Reference CDFs are computed separately by adaptive quadrature, with requested absolute and relative tolerances 2×10−122\times10^{-12}; no reference parameters are fitted to the tested outputs.

The diagnostics include marginal probability-integral-transform Kolmogorov–Smirnov tests, a joint four-bin-per-coordinate statistic, and two fixed diagonal projections of normal scores in dimension two. The joint checks probe distributional discrepancies beyond agreement of individual marginals.

Across the 42 prespecified zero-noise tests, none rejects after Holm correction at level 0.050.05; the minimum adjusted pp-value is 0.272210.27221. The primary Gaussian-noise experiments contain 36,000 outputs, with no rejection among their 42 tests after the same familywise correction and minimum adjusted pp-value 0.867300.86730. Table 2 reports both raw and adjusted statistics, with corrections applied separately to the specified testing families.

3. A negative control demonstrates sensitivity to a concrete acceptance error.

We deliberately remove the Gaussian-proposal compensation, adjusting the envelope to keep the marking probabilities legal. Conditional on the computed pilot center mm, the resulting incorrect zero-noise density is

\propto \exp\left\\{ -f(x)-\frac{\mu}{4}\\|x-m\\|^2 \right\\}\\,dx.$$ With 3,000 outputs in each dimension, **all seven negative-control tests reject after Holm correction**; even the largest adjusted $p$-value is only $0.001121$. Thus the diagnostics detect this specific structural error in the acceptance mechanism. This makes the agreement observed for the intended implementation more informative than nonrejection without a corresponding failing control.

(Continuing part of Q4) 4. The cost measurements include complete independent executions.

Every output starts with a fresh pilot. We count pilot and validation batches, rejected trials, correction queries, and all transcript-marker replies. No preprocessing cost is amortized across outputs. Across all 44 configurations, including cost checks and negative controls, 120,000 complete runs used 795,836,091 physical gradient replies; saved run records were reconciled with their component query totals.

Table 3 reports costs against both κ\kappa and X=σ2/(με)X=\sigma^2/(\mu\varepsilon). For the nonquadratic zero-noise family, increasing κ\kappa from 22 to 128128 increases the mean complete-output cost from 18.4118.41 to 143.81143.81 queries in dimension one, and from 32.7032.70 to 967.75967.75 in dimension two.

For positive noise at ε=0.05\varepsilon=0.05, representative measured costs are:

XX(d,κ)=(1,8)(d,\kappa)=(1,8)(d,κ)=(2,32)(d,\kappa)=(2,32)
11251.74±5.88251.74\pm5.882,031.12±71.642,031.12\pm71.64
16163,647.89±85.193,647.89\pm85.1929,322.18±962.1929,322.18\pm962.19
646414,153.00±315.5514,153.00\pm315.55116,779.42±3,956.51116,779.42\pm3,956.51

Entries are means plus or minus approximate 95%95\% Student interval half-widths over 3,000 independent full runs. At fixed (d,κ)(d,\kappa), the observed costs grow approximately in proportion to XX over these settings, consistently with the fixed experimental batch rule n=max⁡{1,⌈16X⌉}n=\max\{1,\lceil16X\rceil\}. Together with the distributional diagnostics, these measurements document the output agreement and actual workload of the implemented noisy calibration.

These experiments support the implementation of the geometric conditions, conditional acceptance mechanism, complete-output distributions, and query accounting.

Q3: The one-dimensional known-mode case

Our paper does not prove a Θ(log⁡log⁡κ)\Theta(\log\log\kappa) gradient-only rate when the mode is known. The scalar upper bound of Chewi et al., Theorem 3, uses potential values, so it cannot be transferred to gradient-only access without an additional argument.

The reviewer is correct that Proposition D.2 encodes the unknown mode at resolution κ−1/2\kappa^{-1/2}. The discussion preceding Proposition D.2 explicitly identifies this localization mechanism and does not assert that the family remains hard after revealing the mode. Thus the log⁡κ\log\kappa obstruction exhibited by this family is a localization obstruction. This does not determine the optimal gradient-only complexity once the mode is supplied; we make no double-logarithmic claim for that setting.

Q5: Expected cost versus a fixed budget

Yes. The text immediately after Corollary 5.1 now states explicitly that accuracy independence concerns expected query count. The exact sampler is uncapped and terminates almost surely; finite truncation introduces an accuracy-dependent fallback probability.

The deterministic Od(log⁡(1+κ)+log⁡(1/ε))O_d(\log(1+\kappa)+\log(1/\varepsilon)) budget in Appendix F is proved for the value-based benchmark. We do not assert that same deterministic budget for the gradient-only exact sampler without a separate tail analysis.

We hope these revisions and clarifications address your concerns. We would welcome any further questions or discussion.

Reviewer_Y475OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the minimax expected query complexity of sampling from smooth, strongly log-concave distributions using gradient oracles in fixed dimension, assuming a coarsely localized minimizer. Based on a gradient-only sampling algorithm combining geometric preprocessing and Poisson rejection sampling, it establishes matching upper and lower bounds of order Θd(log⁡(1+κ)+σ2/(με))\Theta_d(\log(1+\kappa)+\sigma^2/(\mu\varepsilon)). It also provides exact gradient-only sampling guarantees in the noiseless setting.

Critical strengths
  1. Jointly optimal complexity: The additive separation of curvature and stochastic noise costs improves upon the multiplicative dependence established by Chen et al. (2026). This provides a meaningful theoretical refinement of the existing sampling complexity bounds.

  2. Exact gradient-only sampling: The logarithmic expected query complexity for exact sampling in the noiseless setting, without potential-value evaluations or knowledge of the minimizer, constitutes a distinct contribution.

Critical weaknesses
  1. Severe dimension dependence and limited computational significance: The main result applies only to fixed dimension, with potentially enormous dimension-dependent constants. In particular, combining the constants in (C.107)–(C.108), the coefficient of σ2/(με)\sigma^2/(\mu\varepsilon) in the prescribed correction batch size is approximately 2×10112\times10^{11} already for d=1d=1, and grows as exp⁡(Θ(dlog⁡d))\exp(\Theta(d\log d)). Although these constants concern the proposed construction rather than an intrinsic lower bound, they considerably limit its computational relevance. The result is therefore primarily an abstract oracle-complexity characterization rather than a practically efficient sampling method.

  2. Restrictive initialization assumptions: The sharp joint complexity result assumes that the unknown minimizer lies in a prescribed ball of radius μ−1/2\mu^{-1/2}. For a more general localization radius RR, Corollary 5.3 introduces an additional factor max⁡(1,μR2)\max (1,\mu R^2) in the noise term, without a corresponding optimality guarantee. The radius-free extension applies only to noiseless gradients. These restrictions limit the generality and significance of the main characterization.

Questions for authors
  1. Dimension dependence: Can the exp⁡(Θ(dlog⁡d))\exp(\Theta(d\log d)) dependence of the proposed construction be substantially improved, or is it intrinsic to the approach?

  2. Initialization: Is the additional factor ΓR\Gamma_R in Corollary 5.3 necessary, or could the sharp joint complexity bound extend to arbitrary localization radii?

2 comments

Thank you for identifying these two limitations. We have made the dimension dependence explicit, and we clarify below the scope of the initialization guarantees.

W1 / Q1: Dimension dependence and computational significance

We agree that the prescribed constants are very large. The correction-batch coefficient is 4096/p0≈1.962×10114096/p_0\approx1.962\times10^{11} already for d=1d=1. Appendix C.4 now collects all costs, including both pilots, failed histories, and transcript markers, into the conservative admissible choice

p_0=\frac{e^{-11}}{\rho^dD_d}, \qquad\rho=160d^{3/2},$$ where $D_d$ is defined in (C.107). This particular certificate satisfies $\log C_d^{\mathrm{cert}}=5d\log d+O(d)$. It is a sufficient upper bound, not the smallest possible constant or an observed runtime. The discussion following Theorems 2.2–2.3 now explicitly qualifies the practical comparison. Our result characterizes the joint dependence on $\kappa,\sigma^2,\varepsilon$ for each fixed dimension; it does not establish practical superiority at moderate condition numbers. Appendix C.4 also identifies a limitation of the fixed radial proposal: even for a standard Gaussian with its exact mode supplied, the best admissible ellipsoid gives an acceptance probability $p_{\mathrm G}$ satisfying $\log p_{\mathrm G}^{-1}=\tfrac12d\log d+O(d)$. Thus better rounding alone cannot remove the exponential loss of this template. This does not establish that the full $p_0^{-1}$ or $C_d^{\mathrm{cert}}$ dependence is necessary. Improving the proposal profile and calibration remains unresolved by our analysis; the example is not a lower bound for Gaussian sampling, which has the separate one-query construction of Corollary 5.2. ## **W2 / Q2: Initialization and the factor $\Gamma_R$** The factor $\Gamma_R=\max\{1,\mu R^2\}$ in Corollary 5.3 comes from applying the main theorem with the weaker strong-convexity bound $\mu_R=\mu/\Gamma_R$. This changes the effective parameters to $\kappa\Gamma_R$ and $\Gamma_R\sigma^2/\mu$. Appendix E presents this as a sufficient reduction, without a matching radius–noise lower bound. The factor is not universally necessary: when $L=\mu$, the quadratic-endpoint construction works for an arbitrary mean using $$\max\left\\{1, \left\lceil\frac{\sigma^2}{2\mu\varepsilon}\right\rceil \right\\}$$ queries, independently of its location. This special case does not resolve the general noisy problem. Corollary 5.4 removes the supplied radius only at zero noise; Proposition 5.5 proves a logarithmic worst-case location cost at fixed curvature, without implying a multiplicative radius penalty in the noise term. The sharp joint characterization therefore remains restricted to the main localized class. We hope these clarifications address your concerns. We would welcome any further questions or discussion.

Thank you for the detailed clarifications. They help clarify the scope of the results, although the main limitations regarding dimension dependence and initialization remain. I maintain my weak-accept recommendation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.