{"id":"7d9fa5c2-c426-4f27-add5-f565d4d8df80","arxiv_id":"2502.06200","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper characterizes the worst-case query complexity of sampling from smooth non-log-concave distributions as exponential in dimension, with matching lower and upper bounds.","lead":"This paper determines how many queries are needed to sample from a high-dimensional distribution when an algorithm can only evaluate the potential function and its gradient, proving that the answer grows exponentially with dimension. The matching upper and lower bounds settle the worst-case query complexity of a basic and widely studied sampling model.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's upper bound is proven only for potentials with ∇f(0)=0; the claimed (LM/dε)^{Θ(d)} characterization for all distributions satisfying Assumptions 1 and 2 depends on an unquantified gradient-descent reduction.","rationale":"The reader's weakest-assumption analysis identifies exactly this gap: the upper-bound proof is written under ∇f(0)=0, and the promised reduction to a stationary point is not formalized. I agree that this is the most load-bearing issue for the central claim. The lower bound itself appears structurally sound: the packing argument, the smooth interpolation with the mollifier, and the TV separation estimate are all internally consistent, and the O(M) second-moment normalization gap noted by the reader is an asymptotic-constant issue rather than a threat to the exponent. The upper bound is where the formal statement and proof diverge: the grid approximation in Proposition 18, the truncation construction, the Poincaré bound, and the warm-start analysis all invoke ∇f(0)=0 at least once. If the reduction to an exact stationary point is not available or requires more than (LM/dε)^{O(d)} queries, then Theorem 4 does not match Theorem 3 on the full stated family. This does not make me reject the paper: the construction and proofs are detailed and largely coherent, and the issue is precisely the kind of missing formalization a conditional verdict should request. My concrete test would settle the concern by forcing the authors to either supply the reduction with explicit constants or restrict the theorem statement, in which case the abstract's Θ(d) phrasing must be softened. Since the reader already marked the paper CONDITIONAL and my concern is the same one, the verdict should remain unchanged.","tokens_in":80543,"tokens_out":4764,"duration_ms":50433,"concrete_test":"Add a preprocessing lemma to Section 4: given only Assumptions 1 and 2, find a point s with ∥∇fμ(s)∥≤δ using value/gradient queries, then re-derive Lemma 32, Lemma 26, Corollary 28, and Lemma 34 with the origin shifted to s and with all grid and smoothness estimates carrying explicit δ-dependence. Compute the largest δ for which f̂* stays within d of f*, Ẑμ stays within the stated factor of Zμ, and the KL warm-start bound remains polynomial; then verify that the gradient-descent query count plus the subsequent (LM/dε)^{O(d)} poly(ε^{-1},d,L,M) stays within the theorem's bound for all LM≥d and ε<1. If no such δ exists, Theorem 4 applies only to centered potentials and the paper's claimed tight characterization for all non-log-concave distributions is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and Theorem 3 state a lower bound for every L-log-smooth distribution with second moment at most M, while Theorem 4, the matching upper bound, is stated only under the extra condition ∇f(0)=0. The paper says this is 'for simplicity' and that one can first run gradient descent to find a stationary point and shift the origin, but no part of Section 4 quantifies that reduction. The missing quantification is load-bearing because the proof uses ∇f(0)=0 in several places that would fail if the origin is only an approximate stationary point. In Lemma 32, the grid estimates of f* and Zµ rely on ∥∇fμ(x)∥≤L∥x∥, which gives f(vx)≤f(x)+d/2; with only ∥∇f(s)∥≤δ after shifting to s, each grid-error bound acquires an extra δ·√d·ℓ term, where ℓ is the grid side length, and the allowable δ must be computed before the claimed accuracy of f̂* and Ẑµ is preserved. Lemma 26 uses ∇f≤2Rπ(0)=0 both to get ∇f≤2Rπ(0)=0 and to bound gradients in B2R; Corollary 28 and Lemma 34 then use fπ(0)−min fπ to bound the KL warm start. If the shifted origin is only δ-stationary, these bounds change by terms involving δ and the location of s, and the second moment about s need not still be at most M. The text asserts that the reduction can be done but gives no theorem, no query count for the preprocessing, and no error-propagation analysis. Without these, Theorems 3 and 4 do not formally establish the stated tight complexity for the full family DL,M; they establish it only for the centered subclass and leave the asserted Θ(d) matching claim conditional on an unverified reduction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the worst-case query complexity of sampling from a d-dimensional distribution whose log-density is L-smooth and whose second moment is at most M. The lower-bound construction (Section 3) starts from a Gaussian-like base density with a flat annular plateau, then perturbs disjoint balls on that plateau; the authors prove that any algorithm must discover the perturbed ball, yielding an (LM/(dε))^{Ω(d)} query lower bound. The upper-bound algorithm (Section 4) constructs an auxiliary distribution π by truncating low-density regions of the target, approximating the minimum and normalizing constant on a grid, and then samples from π with a Langevin algorithm, giving (LM/(dε))^{O(d)} queries. The paper also compares the target-smoothness assumption with smoothness along the Ornstein-Uhlenbeck trajectory (stitched Gaussians and mixtures of Gaussians) and compares sampling with non-convex optimization, arguing that sampling can be super-exponentially easier than optimization.","tokens_in":80875,"tokens_out":9145,"duration_ms":92617,"significance":"If the matching upper and lower bounds hold for the full class, this is a significant contribution: it identifies the correct exponential dependence of query complexity on L, M, d, and ε for non-log-concave sampling, improves the earlier e^{Ω(d)} lower bound, and gives the first ε-dependence in this regime. The explicit stitched-Gaussian family clarifies that smoothness of the initial log-density does not imply smoothness along the OU trajectory, and the Ising-model connection is a nice addition. The proof structure is coherent, with detailed estimates for the lower-bound construction and for the Poincaré constant, smoothness, and warm start of the auxiliary distribution. However, the upper bound is formally proved only under the extra condition ∇f(0)=0, and the paper's claim that this is removable by a gradient-descent preprocessing step is not backed by a theorem; this gap affects the central matching-characterization claim for the full family.","major_comments":[{"comment":"Theorem 4 is stated only for potentials with ∇f(0)=0, and the text says the assumption is made 'for simplicity' and that one can first run gradient descent to find a stationary point and shift the origin. No theorem, query count, or error-propagation analysis for this reduction is provided. The gap is load-bearing: Lemma 26 uses ∇f(0)=0 to conclude ∇f_{≤2Rπ}(0)=0 and to bound gradients by L‖x‖ in B_{2R}; Lemma 32 uses ∥∇fμ(x)∥≤L‖x‖ when estimating f* and Zμ on the grid; and Corollary 28 together with Lemma 34 uses fπ(0)=min fπ and the warm-start bound KL(μ0∥π). If the new origin is only a δ-stationary point, each of these estimates changes: the grid errors in Lemma 32 acquire extra δ·√d·ℓ terms, the second moment about the shifted origin need not remain at most M, and the KL warm-start bound must be recomputed. A formal reduction with explicit δ and query cost is therefore necessary before Theorems 3 and 4 establish the claimed tight complexity for the full family D_{L,M}; alternatively, the abstract and Section 1 should state the upper bound only for the centered subclass.","section":""},{"comment":"Theorem 8 claims that for every algorithm that succeeds on all of D_{L,M}, there is a hard distribution in D_{L,M}. However, the hard instances constructed in Section 3 are shown only to be O(L)-log-smooth with second moment O(M): Lemma 10 gives second moment O(M), Lemma 13 gives E_{μv}[‖X‖²]=O(M), and Lemma 14 gives O(L)-smoothness with unspecified universal constants. The proof then asserts, without a further argument, that the instances can be assumed to satisfy second moment at most M and smoothness L. This is a formal gap in the theorem statement. It is likely fixable by rescaling M (or by absorbing the universal constants into the Ω-exponent), but as written the lower bound is not literally against D_{L,M}.","section":""}],"minor_comments":[{"comment":"The definition r₂ = √(2r₁) is dimensionally inconsistent and incompatible with the mollifier construction, which requires r₂ ≥ r₁; the intended definition is presumably r₂ = √2·r₁. Please correct this throughout Section 3, since all subsequent radius ratios depend on it.","section":""},{"comment":"The displayed Hessian computations in Lemma 10 (and similar long displayed equations in Lemma 22 and Section 5.2.1) contain unreadable inserted symbols in the provided version. These are likely transcription artifacts, but the arXiv version should be checked so that every displayed calculation is legible and complete.","section":""},{"comment":"The statement of Theorem 5 says 'for arbitrary s=Ω(d)' but uses s both for the squared center distance and later for time scales; please define the parameter explicitly and avoid reusing s with the stationary-point notation from Section 1.1.","section":""}],"recommendation":"major_revision","confidential_remarks":"This is a strong theory paper with a substantial central result. The main issue is formal rather than conceptual: the upper bound is proved only for the centered case ∇f(0)=0, and the claimed reduction to the general case needs a real proof with quantified query cost and error propagation. The second lower-bound gap (instances having O(M) rather than ≤M second moment) is also fixable. I recommend major revision rather than rejection; if the stationarity reduction can be written out, the paper will be a solid journal contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The main result is real: the (LM/dε)^{Θ(d)} query complexity for non-log-concave sampling, with the first ε-dependence in the lower bound. The lower-bound construction (plateau-and-bump on a ring) is the real contribution; it improves the old e^{Ω(d)} bound and gets the right dependence on L, M, and ε. The upper bound is an honest algorithmic construction — truncate, estimate f* and Zμ on a grid, sample the smoothed version by LMC — and it matches the lower bound up to the exponent constant. The OU-process analysis and the sampling-vs-optimization comparison are secondary but worth reading.\n\nThe soft spots are in proportion. Most importantly, Theorem 4 is stated for the full family DL,M, but proven under the extra condition ∇f(0)=0. The paper says you can first run gradient descent to find a stationary point and shift the origin, but no theorem, no query count, no error propagation is given. This is load-bearing, because the proof uses ∇f(0)=0 to bound gradients on the ball and to ensure ∇fπ(0)=0 for the KL warm-start bound (Corollary 28 and Lemma 34). Without it, the bound on fπ(0) − min fπ picks up extra terms; they may be harmless or may not, but the reader can't tell. The stress-test note is right about this. The fix may be straightforward — ∇f(0) is at most L√M by integration by parts, so the grid estimates survive with slightly larger constants — but the KL warm-start part needs real work. The authors should either prove the reduction or restate the upper bound for the centered subclass and adjust the abstract accordingly.\n\nTwo smaller issues: r2 = √(2r1) in Section 3.2 is dimensionally inconsistent and is almost certainly a typo for something like √2·r1 or 2r1; should be fixed. And the hard instances have second moment O(M), not ≤ M; this is fixable by rescaling and doesn't threaten the exponent, but the formal statement needs a sentence.\n\nIf the reduction is patched, this is a clean, significant paper. As it stands, the lower bound is solid and the upper bound is a strong partial result. It deserves peer review, and the referees should push on the reduction.","headline":"Strong lower bound with a matching upper bound that is formally proven only for centered potentials; the gap to the stated general theorem is real but probably fixable.","tokens_in":81441,"tokens_out":8011,"would_cite":true,"duration_ms":72609,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves matching upper and lower bounds showing the worst-case query complexity of sampling from $L$-log-smooth distributions with second moment at most $M$ is $(LM/(d\\varepsilon))^{\\Theta(d)}$.","keywords":["non-log-concave sampling","query complexity","log-smooth","second moment","total variation distance","value and gradient oracle","Ornstein-Uhlenbeck process","sampling versus optimization"],"falsifier":"For a fixed parameter choice such as $d=10$, $L=M=10$, $\\varepsilon=1/200$, evaluate the Hessian of the perturbed potential $f_v$ from Section 3.2 at points in the interpolation shell $r_1<\\|x-v\\|