{"id":"5c48db8b-9398-4cdb-b24e-9cda063628d7","arxiv_id":"2608.07837","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"LMC-SPSA, using two noisy function evaluations per iteration, is claimed to converge in W2 distance with an O(p^2) dimension bound and O(p/epsilon^2 + delta^2 p^3/epsilon^3) oracle complexity.","lead":"This paper analyzes a Langevin Monte Carlo sampler that estimates gradients from only two noisy function evaluations per step using SPSA perturbations. It claims Wasserstein convergence with improved dimension scaling and oracle complexity for black-box noisy sampling.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(p^2) sharpening in Theorem 3 rests on an invalid pointwise bound for the third-derivative tensor under Assumption A3, and Theorem 4's oracle complexity is not consistent with the stated M1=O(p) scaling.","rationale":"The reader's weakest_assumption identifies the same core defect: the proof of the O(p^2) bound uses an operator-norm-style inequality that Assumption A3 does not supply. My stress-test confirms this is a genuine flaw in the written proof of Theorem 3. The M1 scaling issue in Theorem 4 is also real: the paper explicitly allows M1=O(p), and plugging that into the chosen stepsize yields an iteration count that contradicts the advertised O(p/ε^2) complexity. I do not see a way to recover the stated complexity without either strengthening A4 to M1=O(1) or changing the dimension scaling of the final bound. The numerical experiments use a quadratic potential with zero third derivative, so they cannot validate the sharpened p^2 dependence; the oracle-budget comparisons are consistent with the method's practical efficiency but do not test the proof. The constant-step W2 analysis and the diminishing-step convergence argument may be salvageable, but the headline dimension-accuracy claims are not supported as written. Therefore I keep the reader's REJECT verdict.","tokens_in":23021,"tokens_out":18872,"duration_ms":196558,"concrete_test":"Re-derive the third-derivative remainder bound with the test potential f(x)=M3/6 (Σ_i x_i)^3, for which Assumption A3 holds with max-norm M3 and the Taylor remainder is exact. Compute E∥(c^2/12)(∇^3f(X+)+∇^3f(X−))(Δ⊗Δ⊗Δ)Δ^{-1}∥^2 with X=0 and Δ Rademacher. If the leading term is c^4 M3^2 p^4, then the p^2 L2 bound is valid and only Eq. (42)'s pointwise justification needs repair; if it is c^4 M3^2 p^5 or higher, the claimed O(p^2) sharpening in Theorem 3 is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advance rests on Theorem 3's replacement of the p^4 third-derivative bound by Eq. (42): the paper bounds |∇^3 f(X±)(Δ⊗Δ⊗Δ)| pointwise by M3∥Δ∥^3 = M3 p^{3/2}, then multiplies by ∥Δ^{-1}∥=√p to obtain 2M3p^2. Assumption A3 only bounds the max-norm of the tensor, not its spectral norm. For the Rademacher vector Δ∈{±1}^p, the tensor with all entries equal to M3 gives T(Δ,Δ,Δ)=M3(Σ_i Δ_i)^3, which at Δ=1 has magnitude M3 p^3, not M3 p^{3/2}; the pointwise inequality is false. No correct L2 estimate over the Rademacher randomness is supplied, so the sharpened p^2 term is not derived. Independently, Theorem 4's complexity O(p/ε^2+δ^2p^3/ε^3) is incompatible with Assumption A4 as stated: A4 allows M1=O(p), and even the natural M1=O(√p) for a standard Gaussian makes the projection term √((p-1)/m)M1√h force h ≲ ε^2/(p M1^2), giving N=Ω(p^2/ε^2) (or Ω(p^3/ε^2) under M1=O(p)), not O(p/ε^2). Both advertised contributions therefore lack support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes LMC-SPSA, an unadjusted Langevin Monte Carlo method that uses a two-point SPSA gradient surrogate built from two noisy function evaluations per iteration, for sampling from strongly log-concave targets when gradients are unavailable. The authors prove Wasserstein-2 convergence bounds under constant and diminishing step sizes, claim to sharpen the dominant dimension dependence in the error bound from O(p^4) to O(p^2), and derive an oracle complexity of O(p/epsilon^2 + delta^2 p^3/epsilon^3) under paired noise. They also provide numerical comparisons with finite-difference LMC and the one-point ZO-LMC of Roy et al. under matched oracle budgets.","tokens_in":23326,"tokens_out":9093,"duration_ms":89494,"significance":"If the theoretical claims were correct, the paper would contribute a query-efficient zeroth-order sampler with improved noise scaling relative to existing ZO-LMC methods, and the two-call-per-iteration SPSA estimator would be practically attractive. The paper also makes a good-faith effort at fair oracle-budget-matched numerical comparisons, and its diminishing-step-size analysis (Theorems 2, 5, 6) contains useful ideas. However, the two central advertised advances—the O(p^2) bound and the stated oracle complexity—are not supported by the proofs as written, and one complexity claim is inconsistent with the paper's own assumptions. The numerical experiment used to validate the O(p^2) sharpening does not actually exercise the third-derivative term that the sharpening concerns.","major_comments":[{"comment":"The key inequality |∇^3 f(X)(Δ⊗Δ⊗Δ)| ≤ M3 ||Δ||^3 is false under Assumption A3. A3 only bounds the max-norm of the third-derivative tensor, not its operator norm. For the tensor with every entry equal to M3, the i-th component of ∇^3 f(Δ⊗Δ⊗Δ) is M3(Σ_j Δ_j)^3; at Δ = (1,...,1) this equals M3 p^3, not M3 p^{3/2}. Thus the displayed bound in Eq. (42) is invalid, and the claimed O(p^2) third-derivative term is not established by the proof. A correct argument would need to control the L2 norm over the Rademacher randomness, for example via second moments of the Rademacher chaos of order three; no such estimate is supplied.","section":"Theorem 3, Eq. (42)"},{"comment":"The stated oracle complexity O(p/epsilon^2 + delta^2 p^3/epsilon^3) is inconsistent with Assumption A4. The step-size choice in Eq. (48) contains the term m epsilon^2 / (16((p-1)M1^2 + ...)), so the iteration count N = Theta(1/(mh)) includes a contribution of order (p-1)M1^2/epsilon^2 from the projection-error term. Under the allowed scaling M1 = O(p), this term is Omega(p^3/epsilon^2); even under the natural M1 = O(sqrt(p)) it is Omega(p^2/epsilon^2). The proof of Theorem 4 explicitly writes 1/(mh) = O(1 + M^2p/(m^3 epsilon^2) + M1^2(p-1)/(m^2 epsilon^2) + delta^2 M3 p^3/(m^3 epsilon^3)) and then silently drops the M1 term when claiming Eq. (50). The paper's assertion that M1 = O(p) 'does not affect the leading-order dimension dependence' is therefore incorrect.","section":"Theorem 4, Eqs. (48)-(50)"},{"comment":"The numerical validation of the O(p^2) dimension scaling uses the quadratic potential f(x) = (1/2)||x-2||^2, whose third derivative is identically zero. Consequently, the third-derivative remainder term being sharpened in Theorem 3 is absent in this experiment, so the observed flattening of W2/p^2 cannot provide evidence for the claimed sharpened bound. The experiment may only reflect the behavior of the projection-error and noise terms, which scale differently in p.","section":"Section 6.1"}],"minor_comments":[{"comment":"The theorem statement says the bound holds for 'constant or shrinking h_k', but the displayed bound contains h_k and c_k only in the additive terms while the contraction factor is a product up to index k; for genuinely time-varying schedules the cumulative contribution of the remainders requires a summation argument as in Theorem 5. The statement should clarify that the displayed bound refers to a single-step or constant-step setting, or include the appropriate summed form.","section":"Section 4.4, Theorem 3 statement"},{"comment":"There is a duplicated sentence fragment: 'where∆k = (∆k1,...,∆kp)⊤ is a random perturbation vector.' appears twice in close succession. Please clean up the typesetting.","section":"Section 3"},{"comment":"The complexity comparison with Roy et al. suppresses the M1-dependent term in the LMC-SPSA row; since M1 may depend on p, the table's 'Total calls' column is misleading unless the dependence on M1 is shown or M1 is explicitly assumed constant.","section":"Section 5, Table 1 and surrounding text"},{"comment":"The numerical diagnostic is the squared error of the post-burn-in empirical mean (and moment errors), not a direct estimate of the Wasserstein-2 distance. The authors acknowledge this, but the abstract and introduction could be clearer that the empirical claims about W2 rely on the theoretical bounds, not on the plots.","section":"Section 2, Fair-budget protocol"}],"recommendation":"reject","confidential_remarks":"The paper's two headline contributions—the O(p^2) sharpening and the O(p/epsilon^2 + delta^2 p^3/epsilon^3) oracle complexity—are both unsupported: the first rests on a false tensor-norm inequality, and the second is inconsistent with the paper's own Assumption A4 allowing M1 = O(p). These are not local presentation issues; they invalidate the central theoretical advances. Even if the tensor bound could be repaired with a more careful Rademacher-chaos argument, the complexity claim would still require a substantial revision of either the assumptions or the advertised complexity, and the comparison with Roy et al. would need to be re-evaluated. I do not see a path within a normal minor revision to preserve the paper's main claims as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hongbo Li and Spall propose LMC-SPSA, a Langevin sampler that replaces the gradient with a two-point SPSA estimate built from two noisy function evaluations per iteration. The algorithm is sensible and practical, and the paper contains a genuine extension over the prior constant-step analysis: Theorem 5 gives a diminishing-step schedule that drives the Wasserstein bound to zero, and Theorem 6 derives a balanced rate. Those parts follow standard coupling arguments and look correct to me. The oracle-matched numerical comparison with Roy et al.'s ZO-LMC is also honest and useful.\n\nThe trouble is the paper's two headline claims. Theorem 3 claims to sharpen the dominant dimension dependence from p^4 to p^2. The proof hinges on the pointwise bound |∇^3 f(Δ⊗Δ⊗Δ)| ≤ M3 ||Δ||_2^3 = M3 p^{3/2}, using only Assumption A3's max-norm bound on the third-derivative tensor. That inequality is false. A tensor with all entries equal to M3 gives M3 (Σ_i Δ_i)^3, which at Δ = (1,...,1) is M3 p^3, not M3 p^{3/2}. The stress-test note is exactly right, and I do not see a quick repair; you would need a genuine L2 estimate over the Rademacher randomness, which is not supplied. So the p^2 claim is unsupported.\n\nTheorem 4's oracle complexity has a separate, independent problem. The step-size constraint includes the (p−1)M1^2 term. Under Assumption A4, M1 may grow linearly in p, and even the typical M1 = O(√p) for a Gaussian target makes h ≲ ε^2/(p M1^2), forcing at least Ω(p^2/ε^2) iterations, not O(p/ε^2). The paper's statement that M1 = O(p) does not affect the leading-order dimension dependence is simply wrong in light of its own constraint.\n\nWhat is good here: the constant-step bound in Theorem 1 is a standard coupling analysis and is likely correct if you keep the p^4 term. The diminishing-step and rate theorems are valuable and should survive a change in the third-derivative bound. The experiments use a quadratic target, whose third derivative is zero, so they cannot discriminate between p^2 and p^4; that evidence is inconclusive for the advertised claim.\n\nOverall, this is a useful algorithm with some correct analysis, but the two main advertised contributions are not established. I would not cite the p^2 bound or the complexity result. I would still send a revised version to a referee who knows Langevin analysis and SPSA, because the diminishing-step analysis and the practical algorithm deserve a careful look. As it stands, the paper should be rejected.","headline":"The paper's advertised O(p^2) sharpening and oracle complexity rest on a false tensor bound and an inconsistent M1 scaling, but the SPSA-LMC algorithm and the diminishing-step analysis are worth a referee's time.","tokens_in":23926,"tokens_out":4445,"would_cite":false,"duration_ms":45475,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65C05","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two noisy function evaluations per step are enough for Langevin Monte Carlo to converge in Wasserstein distance, with leading $W_2$ error $O(p^2)$ and oracle complexity $O(p/\\epsilon^2+\\delta^2p^3/\\epsilon^3)$.","keywords":["LMC-SPSA","zeroth-order sampling","simultaneous perturbation stochastic approximation","noisy function evaluations","Wasserstein distance","Langevin Monte Carlo","oracle complexity","dimension dependence"],"falsifier":"Take a strongly log-concave potential $f(x)=\\frac{m}{2}\\|x\\|^2+\\frac{c}{6}(\\mathbf{1}^T x)^3$ on a bounded region where the Hessian stays positive definite, and consider the Rademacher perturbation with all coordinates equal to $1$. At that configuration the third-derivative contraction equals $c p^3$, whereas $M_3\\|\\Delta\\|^3=M_3p^{3/2}$, so the inequality used to derive the $p^2$ term fails; a numerical version is to run LMC-SPSA on such a cubic-tilted target and plot $W_2/p^2$ versus $p$.","tokens_in":22753,"feed_emoji":"🎯","tokens_out":11771,"duration_ms":114812,"temperature":0.7,"pith_summary":"This paper proposes LMC-SPSA, a sampler that replaces the gradient in Langevin Monte Carlo with a two-point simultaneous-perturbation estimate built from two noisy function evaluations per iteration. It tries to establish that, under strong convexity, smoothness, a third-derivative bound, and paired measurement noise, the sampler converges in 2-Wasserstein distance with an explicit non-asymptotic bound, including under a diminishing step-size and perturbation schedule. The central quantitative claim is a sharpened error bound whose dominant dimension dependence is $O(p^2)$ rather than the $O(p^4)$ of the earlier SPSA-LMC analysis, and a total noisy-oracle complexity of $O(p/\\epsilon^2+\\delta^2p^3/\\epsilon^3)$ to reach $W_2$-accuracy $\\epsilon$. If the claim is right, noisy black-box targets can be sampled almost as cheaply as targets with exact gradients, and the accuracy scaling improves over the one-point zeroth-order baseline while using only two oracle calls per step.","feed_headline":"Two noisy oracle calls per step shrink LMC error as p^2","feed_subtitle":"A two-point SPSA gradient keeps Wasserstein convergence and improves noise scaling from epsilon^-4 to epsilon^-3.","key_machinery":"The load-bearing object is the two-point SPSA gradient surrogate $\\tilde G_k=\\frac{\\tilde f(X_k+c_k\\Delta_k)-\\tilde f(X_k-c_k\\Delta_k)}{2c_k}\\Delta_k^{-1}$, with $\\Delta_k$ a Rademacher vector and $\\tilde f$ the noisy oracle. It is conditionally nearly unbiased with bias $O(c_k^2)$, its projection-error second moment is exactly $(p-1)\\mathbb{E}\\|\\nabla f(X_k)\\|^2$ via the identity $\\mathbb{E}[(\\Delta\\Delta^T-I)^2]=(p-1)I$, and its paired-noise variance is controlled by $\\delta^2 p/(2c^2)$. The Wasserstein argument is carried by a one-step coupling between the chain and the Langevin diffusion: comparing $L_h-X_{k+1}$ with $L_0-X_k$ decomposes the error into drift contraction, Euler discretization remainder, SPSA projection error, third-derivative bias, and oracle noise. The explicit parameter choices then balance these five contributions equally so that each is $\\epsilon/4$.","core_discovery":"The paper's central result is Theorem 3: under Assumptions A1-A5 the law of the LMC-SPSA chain satisfies $W_2(\\nu_{K+1},\\pi)\\leq \\prod_{j=0}^K(1-m h_j)W_2(\\nu_0,\\pi)+\\frac{7\\sqrt{2}M}{6m}\\sqrt{h_K p}+\\frac{M_3}{6m}c_K^2p^2+\\sqrt{\\frac{p-1}{m}}M_1\\sqrt{h_K}+\\sqrt{\\frac{h_K p}{2m}}\\frac{\\delta}{c_K}$. The proof keeps the SPSA gradient estimator's projection error at size $(p-1)E\\|\\nabla f(X_k)\\|^2$ through the exact identity $E[(\\Delta\\Delta^T-I)^2]=(p-1)I$ and compresses the third-derivative remainder to a $p^2$ term, replacing the $p^4$ term in the noise-free predecessor. Theorem 4 turns this bound into explicit choices of step size $h$, perturbation $c$, and iteration count $N$, giving the noisy-oracle complexity $O(p/\\epsilon^2+\\delta^2p^3/\\epsilon^3)$; under perfectly paired noise $\\delta=0$ this becomes $O(p/\\epsilon^2)$. Theorems 5 and 6 extend the guarantee to diminishing schedules, with a balanced schedule yielding $W_2(\\nu_k,\\pi)=O(\\delta^{2/3}pk^{-1/3})$ for fixed $\\delta>0$.","pith_inferences":["A stress test beyond the paper's quadratic example would run LMC-SPSA on a strongly log-concave target with a cubic component and plot $W_2/p^2$ against $p$; growth of the normalized error would indicate that the $O(p^2)$ dimension term is specific to the example rather than the general theorem.","The paired-noise assumption is the practical crux: when the two SPSA measurements cannot be paired, the $\\delta^2p^3/\\epsilon^3$ term dominates, so a concrete engineering follow-up is to impose common random numbers or antithetic noise across the two evaluations.","The same two-call SPSA surrogate should plug into kinetic Langevin or Hamiltonian Monte Carlo; the dimension-balancing logic here suggests the $O(p^2)$ term and the paired-noise benefit would carry over, but the paper does not analyze those samplers."],"forward_implications":["Under perfectly paired noise ($\\delta=0$), the total oracle complexity for $W_2$-accuracy $\\epsilon$ is $O(p/\\epsilon^2)$, matching the iteration count of gradient LMC up to constants.","Under independent additive noise with variance $\\sigma^2$ (so $\\delta^2=\\sigma^2$), the complexity is $O(p/\\epsilon^2+\\sigma^2p^3/\\epsilon^3)$, improving the $\\epsilon^{-4}$ scaling of the one-point ZO-LMC baseline at the cost of a larger dimension factor.","A diminishing schedule such as $h_k=a/(k+k_0)$ with balanced perturbations gives $W_2(\\nu_k,\\pi)=O(k^{-1/3})$ even when paired noise persists, so the sampler converges asymptotically without a constant-step bias.","Under a fixed oracle-call budget, the numerical section reports that LMC-SPSA achieves smaller mean-estimation errors and better dimension scaling than LMC-FDSA and one-point ZO-LMC, with an empirical mean-squared error scaling of roughly $p^{1.34}$.","The comparison with the one-point baseline is not uniform: LMC-SPSA wins on accuracy scaling but has higher dimension dependence, so which method is cheaper depends on the regime of $p$, $\\epsilon$, and $\\sigma$."],"supporting_citations":[{"why":"Supplies the noise-free SPSA-LMC analysis whose O(p^4) bound Theorem 3 sharpens, along with the Wasserstein recursion template.","marker":"[14]"},{"why":"Defines the SPSA gradient estimator and supplies the bias lemma used to establish the O(c_k^2) conditional bias.","marker":"[16]"},{"why":"Supplies the one-step Wasserstein coupling lemmas, drift contraction and Euler discretization remainder, used throughout Theorems 1 and 3.","marker":"[28]"},{"why":"The one-point ZO-LMC method used as the oracle-complexity and numerical baseline for the comparisons in Section 5.","marker":"[30]"},{"why":"Establishes W2 contraction of the exact Langevin kernel, which underlies the recursive Wasserstein bounds.","marker":"[33]"}],"fun_headline_variants":["Two noisy calls per step give LMC p^2 error bound","SPSA-gradient LMC: p^2 error from two noisy evaluations","LMC without gradients: noise-robust p^2 convergence","Diminishing schedules maintain LMC-SPSA convergence","Noisy LMC: better dimension and noise scaling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O(p^2)$ dimension improvement rests on the step in the proof of Theorem 3 that bounds the third-derivative remainder by $M_3\\|\\Delta\\|^3$, as though Assumption A3's entrywise max-norm bound on third derivatives controlled the contraction norm of the tensor; if that step fails, the leading dimension dependence is larger than $p^2$.","fun_headline_variants_meta":{"raw":{"variants":["Two noisy calls per step give LMC p^2 error bound","SPSA-gradient LMC: p^2 error from two noisy evaluations","LMC without gradients: noise-robust p^2 convergence","Diminishing schedules maintain LMC-SPSA convergence","Noisy LMC: better dimension and noise scaling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001267,"raw_usage":{"total_tokens":5320,"prompt_tokens":1212,"completion_tokens":4108,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":828,"completion_tokens_details":{"reasoning_tokens":4020}},"tokens_in":828,"tokens_out":4108,"duration_ms":30031,"temperature":1.0,"reasoning_tokens":4020,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:49:27.037108+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a strongly log-concave potential $f(x)=\\frac{m}{2}\\|x\\|^2+\\frac{c}{6}(\\mathbf{1}^T x)^3$ on a bounded region where the Hessian stays positive definite, and consider the Rademacher perturbation with all coordinates equal to $1$. At that configuration the third-derivative contraction equals $c p^3$, whereas $M_3\\|\\Delta\\|^3=M_3p^{3/2}$, so the inequality used to derive the $p^2$ term fails; a numerical version is to run LMC-SPSA on such a cubic-tilted target and plot $W_2/p^2$ versus $p$.","supporting_citations":[{"cited_title":"Langevin Monte Carlo with SPSA-approximated gradients,","cited_arxiv_id":null,"evidence_quote":"Supplies the noise-free SPSA-LMC analysis whose O(p^4) bound Theorem 3 sharpens, along with the Wasserstein recursion template."},{"cited_title":"Multivariate stochastic approximation using a simultaneous perturba- tion gradient approximation,","cited_arxiv_id":null,"evidence_quote":"Defines the SPSA gradient estimator and supplies the bias lemma used to establish the O(c_k^2) conditional bias."},{"cited_title":"User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient,","cited_arxiv_id":null,"evidence_quote":"Supplies the one-step Wasserstein coupling lemmas, drift contraction and Euler discretization remainder, used throughout Theorems 1 and 3."},{"cited_title":"Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference,","cited_arxiv_id":null,"evidence_quote":"The one-point ZO-LMC method used as the oracle-complexity and numerical baseline for the comparisons in Section 5."},{"cited_title":"Nonasymptotic convergence analysis for the un- adjusted Langevin algorithm,","cited_arxiv_id":null,"evidence_quote":"Establishes W2 contraction of the exact Langevin kernel, which underlies the recursive Wasserstein bounds."}],"review_version":1}