{"id":"8922fba1-d3b6-466b-b70f-6e15c528ae8c","arxiv_id":"2607.22353","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For smooth dissipative nonconvex objectives, exact, inexact and zeroth-order ULA achieve expected excess risk ε with iteration complexity ~O~(β²dC_LS²/ε²) and zeroth-order evaluation complexity ~O~(β⁴d³C_LS³/ε⁴).","lead":"This paper proves non-asymptotic convergence bounds for Langevin-based optimization, including a zeroth-order version that uses only function evaluations. The key trick converts relative entropy directly into objective-value error, improving the dependence on the log-Sobolev constant.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Inexact/zeroth-order ULA bounds rest on Proposition 3.8, whose proof is delegated to [76, Lemma 4.4] for unbiased mini-batch gradients; for biased surrogates the KL bound may be invalid.","rationale":"The reader's verdict correctly identifies the exponential LSI constant as a limitation, but that is a known and honestly stated caveat, not a gap in the argument. The more load-bearing issue is the unproven Proposition 3.8, which is essential to the inexact and zeroth-order results. The paper itself flags this as a delegated proof, and the referenced lemma was developed for unbiased stochastic gradients. Since the paper deliberately allows biased surrogates and the zeroth-order estimators are biased, the transfer is not automatic. If the KL bound fails, the zeroth-order complexity bounds, a central claimed contribution, do not follow from the provided analysis. I recommend a conditional acceptance: the authors should either provide a complete proof of Proposition 3.8 for biased estimators or restrict the inexact/zeroth-order results to settings where the bias is controlled in a way that prevents error accumulation. The exact-gradient analysis (Theorem 2.6, Corollary 2.8) and the general framework appear sound, so a rejection is not warranted.","tokens_in":46969,"tokens_out":30868,"duration_ms":264442,"concrete_test":"Take a one-dimensional or two-dimensional dissipative non-convex F (e.g., F(x) = (x^2 − 1)^2 + (m/2)x^2 with m > 0, which is M-smooth and (m,b)-dissipative). Run Algorithm 2 with the deterministic biased gradient g(x) = ∇F(x) + b, where b is a small constant, and the exact ULA chain (18) using the same Gaussian noise and the same initialization. For a sequence of step sizes γ and horizons k, estimate KL(μ_k || ν_k) by Monte Carlo: approximate both laws by many coupled sample paths, fit the empirical distributions (or use a Gaussian/Laplace approximation), and compute the KL divergence. Compare the empirical KL against the Proposition 3.8 bound γ k β δ (P Γ + Q)/4 with δ = ||b||², P=0, Q=1. If the empirical KL exceeds the claimed bound and the ratio grows with k (e.g., scales roughly as k² or k³), Proposition 3.8 is false for biased surrogates, and the zeroth-order complexity theorems in","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central inexact and zeroth-order complexity claims (Corollaries 3.5, 4.3, 4.8) hinge on Proposition 3.8, which asserts KL(μ_k || ν_k) ≤ γ k β δ (P Γ + Q)/4. The proof is not given; it is stated to be identical to the proof of [76, Lemma 4.4]. That lemma was derived for unbiased stochastic gradients (mini-batch SGLD), where the cross term between the state error and the gradient noise vanishes. Assumption 3.1 in this paper explicitly permits biased surrogates g(x,ξ) with only a second-moment bound, and the zeroth-order estimators in Section 4.2 are indeed biased. For a deterministic bias b(x) = g(x) − ∇F(x), the mean error e_k = E[x_k − y_k] can accumulate over time if the linearized dynamics are not contractive along the trajectory. In such a case the per-step KL contribution grows with the accumulated mean error, and the total KL can scale super-linearly in k — e.g., like γ³ β k³ b² for a constant bias under a non-contractive linearization. The bound in Proposition 3.8 is only linear in k and would then be violated. Since Proposition 3.8 is the only link between the inexact chain and the exact ULA analysis, its failure would invalidate Corollaries 3.5, 4.3, and 4.8, including the claimed first zeroth-order ULA global optimization complexity bounds.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies fixed-temperature Unadjusted Langevin Algorithm (ULA) variants for nonconvex optimization under M-smoothness and (m,b)-dissipativity, with the goal of bounding the expected excess risk E[F(x_k)] - min F. The central methodological novelty is a direct passage from KL divergence to objective-value error via a weighted Csiszár–Kullback–Pinsker inequality and exponential-moment estimates (Lemma 2.10), avoiding intermediate Wasserstein bounds. This is used to derive explicit iteration complexity for exact ULA (Corollary 2.8), then extended to inexact ULA under a second-moment growth condition on possibly biased gradient surrogates (Theorem 3.3, Corollary 3.5), and finally applied to mini-batch and zeroth-order (Gaussian and spherical finite-difference) estimators (Corollaries 4.3 and 4.8). The claimed iteration complexity is ~O(β² d C_LS(β,d)²/ε²) for exact and inexact ULA, and ~O(β⁴ d³ C_LS(β,d)³/ε⁴) function evaluations for zeroth-order ULA. The paper also supplies a mollification-based proof that the Gibbs measure satisfies a logarithmic Sobolev inequality under merely C^{1,1} smoothness and dissipativity (Proposition 2.5), and presents numerical experiments on Ackley, Rastrigin, and Levy functions.","tokens_in":47365,"tokens_out":20501,"duration_ms":174907,"significance":"If the results are correct, the paper makes a solid contribution: the weighted-CKP KL-to-objective comparison is elegant and yields a genuinely better exponent on the log-Sobolev constant than the Wasserstein-based route, and the zeroth-order complexity bounds appear to be the first of their kind for global nonconvex optimization under standard smooth dissipative assumptions. The proof of the LSI via mollification closes a regularity gap in earlier work, and the parameter choices in the corollaries are explicit. The main weakness is that the inexact and zeroth-order results all hinge on Proposition 3.8, whose proof is delegated to a cited lemma for unbiased stochastic gradients; as written, this delegation is not sufficient for a result that explicitly covers biased surrogates. The paper is clearly written and the comparisons with prior work are careful, but the inexact core needs a self-contained proof before the headline claims can be fully vouched for.","major_comments":[{"comment":"The inequality KL(μ_k||ν_k) ≤ γkβδ(PΓ+Q)/4 is the only control of the perturbation term (a) in decomposition (19), and it is asserted to follow 'identically' from [76, Lemma 4.4]. That lemma was proved for unbiased mini-batch SGLD, where the cross term between the state error and the gradient noise vanishes; Assumption 3.1, however, explicitly allows biased surrogates, and the zeroth-order estimators in Section 4.2 are biased. The manuscript does not show how the proof extends to this setting. I do not claim the bound is false: for a deterministic bias the linear-in-k KL bound is consistent with a discrete-time Girsanov calculation, and the variance-only form of Assumption 3.1 suggests such an extension exists. But the proposition is load-bearing for Corollaries 3.5, 4.3, and 4.8, so the proof must be written out. Please provide the full argument, indicating exactly where the conditional","section":"Section 3.4, Proposition 3.8"},{"comment":"The uniform second-moment bound Γ is claimed to be independent of γ, β, δ, d. In the proof, the constant C is defined as (1+m)(2b+2B²)+m²Q/(4P)+mQ/(4P)+2, and Γ in (51) likewise contains Q/(4P). These expressions are undefined when P=0, a case explicitly allowed by the convention in Remark 3.1. If P=0, the recursion constant is O(Qδ/m), which is not bounded independently of δ unless an additional constraint on δ is imposed. As written, Theorem 3.3 is not proved in the P=0 case. Please handle P=0 separately, e.g., by adding δ≤δ₀ or by allowing Γ to depend on δ.","section":"Section 3.1 / Appendix C.1, Proposition 3.2"}],"minor_comments":[{"comment":"The expression 'log(3πβ/m)' appears to be a typo: the β cancels in the preceding term log(3πβ/(mβ)) = log(3π/m). As printed, the constant \\tilde C appears to depend on β, contradicting the lemma statement that it is independent of β and d.","section":"Lemma 2.14, proof, near Eq. (48)"},{"comment":"The empirical study is limited to parameter sweeps without comparison to any existing zeroth-order or random-search baseline. A baseline would strengthen the practical message, though it is not essential to the theoretical claims.","section":"Section 5, Figures 1–2"},{"comment":"The notation \\tilde O suppresses polylog factors that may include log(1/ε) and log β; this is standard, but a brief reminder in the captions of Tables 1–3 would help avoid confusion when comparing β scalings.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central exact-ULA analysis is sound and the CKP-based KL-to-objective route is a genuine improvement. The main risk is the inexact part: Proposition 3.8 is the hinge for the paper's headline zeroth-order and stochastic-gradient claims, and the current one-line delegation to a lemma for unbiased mini-batch gradients is not adequate when the framework explicitly allows biased surrogates. I believe the claim is likely true and fixable, so the appropriate action is major revision rather than rejection. The P=0 case in Proposition 3.2 is a smaller but real technical gap. I would also advise the authors to double-check the novelty claim against Liu–Wang (2020) and Roy et al. (2022); the paper's comparisons are reasonable, but an explicit statement of what 'first bounds' means relative to those works would preempt criticism."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The exact-gradient half of this paper is a real step forward. The weighted Csiszár–Kullback–Pinsker passage from relative entropy directly to objective-value error is a genuinely useful trick, and it gives a clean quadratic dependence on the log-Sobolev constant instead of the usual cubic-or-worse Wasserstein route. The mollification proof of the LSI under smoothness and dissipativity closes a real C²-to-C^{1,1} gap, and the variance computations for the Gaussian and spherical zeroth-order estimators are careful and explicit. The experiments are modest but honest.\\n\\nThe soft spot is load-bearing. Proposition 3.8 is the hinge for the inexact and zeroth-order claims, and its proof is not in the paper: the authors say it is identical to [76, Lemma 4.4], which was derived for unbiased mini-batch SGLD. Assumption 3.1 explicitly allows biased surrogates, and the zeroth-order estimators in Section 4.2 are biased. That matters. In the [76] argument, unbiasedness kills the cross term between gradient error and the exact chain; with a bias, that cross term contributes and can accumulate. Here is a concrete counterexample to the lemma as stated: take F quadratic, set g(x) = ∇F(x) + b for a constant vector b. Assumption 3.1 holds with P = 0. Couple the inexact and exact chains with the same Gaussian increments. For small γk, the mean gap grows like kγb, so the KL between the two Gaussians is roughly βγ k² ||b||² / 4, quadratic in k, while Proposition 3.8 promises at most linear growth. So the proposition is false for biased surrogates.\\n\\nThat failure propagates directly to Corollaries 3.5, 4.3, and 4.8, including the claimed first zeroth-order ULA global optimization complexity bounds. The zeroth-order estimators are biased, so the paper's main new claim is not established by the proof as written. The exponential dependence of C_LS(β,d) is acknowledged and is a property of the problem, not a flaw; the reliance on the Vempala–Wibisono theorem is standard and fine.\\n\\nWho this is for: people working on Langevin-based nonconvex optimization and derivative-free methods. The exact-gradient analysis deserves a serious referee and probably publication after some tightening. The inexact/zeroth-order part needs a major revision: either prove a correct KL bound for biased surrogates, or restrict the claims to unbiased stochastic gradients and rework the zeroth-order analysis accordingly. I would send this to peer review rather than desk reject, but I would not accept it in the current form.","headline":"The exact-gradient half is a genuine advance, but the inexact and zeroth-order results rest on Proposition 3.8, which is unproven and false as stated for biased surrogates.","tokens_in":800,"tokens_out":829,"would_cite":false,"duration_ms":92652,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","65K10","90C56"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that smooth, dissipative nonconvex optimization by exact, inexact, and zeroth-order Langevin algorithms has expected-excess-risk complexity quadratic in the log-Sobolev constant, and it supplies the first explicit global n","keywords":["Langevin dynamics","nonconvex optimization","zeroth-order optimization","log-Sobolev inequality","dissipativity","relative entropy","finite-difference estimators","complexity bounds"],"falsifier":"For a one-dimensional double-well potential F(x)=(x²−1)², numerically estimate the log-Sobolev constant of the Gibbs measure, run exact ULA with β = 5, 10, 20 using the paper's parameter choices, and measure E[F(x_k)]−minF. If the ratio |E[F(x_k)−F(x_π)]|/(√KL + KL/2) grows with β beyond the explicit constant C₀ from the proof, or the iteration count scales as C_LS³ rather than C_LS² at fixed β, the central comparison fails.","tokens_in":46885,"feed_emoji":"🎯","tokens_out":8061,"duration_ms":67631,"temperature":0.7,"pith_summary":"This paper tries to establish that, for smooth and dissipative nonconvex objectives, the right way to analyze Langevin optimization is to convert relative entropy directly into objective-value error, skipping Wasserstein distance. It proves that exact, inexact, and zeroth-order Unadjusted Langevin Algorithms reach E[F(x_k)]−minF ≤ ε with iteration complexity whose dependence on the log-Sobolev constant C_LS(β,d) is quadratic, not cubic or worse. Because C_LS can scale exponentially with inverse temperature and dimension, reducing its exponent removes an entire exponential factor. The zeroth-order result, covering Gaussian and spherical finite-difference estimators, is the first non-asymptotic global nonconvex optimization complexity bound for gradient-free Langevin. A reader should care because the guarantee is directly about the optimization objective, not merely about sampling the Gibbs distribution.","feed_headline":"Log-Sobolev constant now enters squared in Langevin rates","feed_subtitle":"Direct entropy-to-objective control yields explicit nonconvex bounds for gradient-free Langevin.","key_machinery":"The load-bearing mechanism is a direct entropy-to-objective comparison: a weighted Csiszár–Kullback–Pinsker inequality converts small relative entropy KL(μ_k‖π_β) into an objective-value gap, after the Gibbs measure is shown to have finite exponential moments under smoothness and dissipativity. This replaces the usual two-step route through Wasserstein distance and Talagrand-type transportation inequalities, which would inject an extra factor of the log-Sobolev constant C_LS(β,d). The KL contraction of ULA comes from a discrete-time contraction bound requiring γ ≤ 1/(4βM²C_LS), so C_LS remains the central object carrying all geometric difficulty. The paper also supplies a mollification argum","core_discovery":"The central claim is that expected excess risk of ULA-type dynamics can be controlled without a Wasserstein intermediate step. The proof decomposes E[F(x_k)]−minF into a sampling error and a Gibbs bias, then bounds the sampling error by applying a weighted Csiszár–Kullback–Pinsker inequality to the objective F itself, using the fact that smoothness and dissipativity imply quadratic growth of F and finite exponential moments of the Gibbs measure. This yields E[F(x_k)]−minF ≤ C(M+1)(√KL + KL/2) + Gibbs bias, with KL controlled by a discrete-time contraction bound under step-size γ ≤ 1/(4βM²C_LS). Optimizing parameters gives k = O~(β²d C_LS²/ε²) for exact and inexact ULA, and total function-eva","pith_inferences":["The avoid-Wasserstein principle is transferable: any algorithm that supplies a KL contraction toward a Gibbs-like measure could inherit the same quadratic C_LS dependence, so the technique may extend beyond ULA to proximal or consensus-based samplers.","The tight temperature choice β ≈ d/ε means algorithm comparisons should be made after substituting this β; otherwise superficially better ε-dependence can hide exponential penalties through C_LS.","The spherical estimator's larger admissible smoothing radius suggests a practical rule for noisy function-evaluation settings, though the paper's experiments illustrate the trade-off rather than certify it.","A specialist unbiased-gradient analysis is the obvious missing piece: the worst-case bias framework is not designed to exploit gradient-estimator cancellation, and closing that gap would plausibly reduce the C_LS power in mini-batch rates."],"forward_implications":["Exact-gradient ULA reaches ε in O~(β²d C_LS(β,d)²/ε²) iterations, improving earlier tracked fourth- or fifth-power dependence on C_LS.","The inexact-gradient theory tolerates biased and stochastic gradient surrogates with state-dependent quadratic mean-square error; the same iteration count holds provided precision δ is chosen as Θ~(ε²/(β² C_LS)).","Mini-batch stochastic-gradient Langevin has total single-component gradient complexity O~(β⁴d C_LS³/ε⁴).","Zeroth-order ULA with Gaussian or spherical finite-difference estimators reaches ε in O~(β⁴d³C_LS³/ε⁴) function evaluations, giving the first explicit global nonconvex bound for derivative-free Langevin.","Because the excess risk is nonnegative, the expectation bound immediately yields a Markov high-probability guarantee for near-optimal objective values."],"fun_headline_variants":["Entropy-to-objective shortcut tightens nonconvex Langevin rates","Gradient-free Langevin gets explicit nonconvex complexity bounds","Squared Log-Sobolev constant in Langevin nonconvex rates","First non-asymptotic bounds for zeroth-order Langevin optimization","Langevin optimization skips Wasserstein for sharper nonconvex bounds"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"All the rates are multiplied by a log-Sobolev constant (a measure of how slowly the Gibbs distribution mixes) that can grow exponentially with inverse temperature and dimension in nonconvex problems, so the polynomial-in-ε guarantees are only practically meaningful when that constant is explicitly bounded.","fun_headline_variants_meta":{"raw":{"variants":["Entropy-to-objective shortcut tightens nonconvex Langevin rates","Gradient-free Langevin gets explicit nonconvex complexity bounds","Squared Log-Sobolev constant in Langevin nonconvex rates","First non-asymptotic bounds for zeroth-order Langevin optimization","Langevin optimization skips Wasserstein for sharper nonconvex bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00081,"raw_usage":{"total_tokens":3451,"prompt_tokens":862,"completion_tokens":2589,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":606,"completion_tokens_details":{"reasoning_tokens":2509}},"tokens_in":606,"tokens_out":2589,"duration_ms":15233,"temperature":1.0,"reasoning_tokens":2509,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T05:02:37.087985+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a one-dimensional double-well potential F(x)=(x²−1)², numerically estimate the log-Sobolev constant of the Gibbs measure, run exact ULA with β = 5, 10, 20 using the paper's parameter choices, and measure E[F(x_k)]−minF. If the ratio |E[F(x_k)−F(x_π)]|/(√KL + KL/2) grows with β beyond the explicit constant C₀ from the proof, or the iteration count scales as C_LS³ rather than C_LS² at fixed β, the central comparison fails.","supporting_citations":[],"review_version":1}