Pith. sign in

REVIEW 2 major objections 3 minor 79 references

Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read 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

desk verdict 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. read the letter →

arxiv 2607.22353 v1 pith:6L2FO5C2 submitted 2026-07-24 math.OC

Emanuele Naldi , Marco Rando , Lorenzo Rosasco , Silvia Villa This is my paper · ORCID
classification math.OC MSC 90C2665K1090C56
keywords Langevindynamicsnonconvexoptimizationzeroth-orderlog-Sobolevinequalitydissipativityrelativeentropyfinite-differenceestimatorscomplexitybounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Section 3.4, Proposition 3.8] 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
  2. [Section 3.1 / Appendix C.1, Proposition 3.2] 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 δ.
minor comments (3)
  1. [Lemma 2.14, proof, near Eq. (48)] 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.
  2. [Section 5, Figures 1–2] 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.
  3. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivation is self-contained, and all load-bearing results are external theorems or independently verified estimates.

full rationale

The paper's main chain is not circular. The excess-risk decomposition (4) separates the Gibbs-concentration term (b) from the discretization/KL term (a). Term (a) is controlled by Lemma 2.10, an explicit application of the external weighted Csiszár–Kullback–Pinsker inequality of Bolley–Villani [6], together with the exponential-moment bound of Lemma 2.11. The KL contraction in Proposition 2.13 is imported from Vempala–Wibisono [74, Theorem 2], an external discrete-time ULA contraction theorem, and the required LSI is proved in Proposition 2.5 by mollification plus the Holley–Stroock criterion, with the Poincaré-bound estimate taken from Raginsky et al. [61]. No parameter appearing in the final complexity is fitted to algorithm outputs: C_LS(β,d) is a functional-inequality constant of the Gibbs measure, bounded independently in Proposition 2.5/Appendix A.1. The inexact-ULA theory similarly uses Assumption 3.1 as an oracle-error definition, a uniform moment bound (Proposition 3.2), the same external CKP route (Lemma 3.7), and Proposition 3.8, whose proof is delegated to the external [76, Lemma 4.4]. Whether that delegation is fully valid for biased, non-mini-batch surrogates is a correctness/rigor concern, not a circularity, because it is not a reduction of the conclusion to its own inputs. The zeroth-order estimates in Lemmas 4.5 and 4.6 verify Assumption 3.1 for Gaussian and spherical finite differences, and Corollary 4.8 follows by substitution. Self-citations appear only in related-work and application discussions and are not load-bearing for any theorem. There is no fitted input renamed as a prediction, no uniqueness result imported from the authors' own prior work, and no ansatz smuggled in through self-citation.

Assumptions & free parameters 0 free parameters · 9 assumptions · 0 invented entities

No hidden fitted constants: β, γ, k, s, h are explicitly chosen algorithmic parameters, and the constants appearing in the bounds are explicit (or explicitly bounded) in the proofs. The main additional input beyond smoothness and dissipativity is the LSI constant C_LS(β,d), which is a property of the target Gibbs measure and is not fitted to algorithm outputs.

assumptions (9)
  • domain assumption F is M-smooth (Assumption 2.1).
    Used throughout; gives Lipschitz gradients and quadratic growth bounds.
  • domain assumption F is (m,b)-dissipative with m>0 (Assumption 2.2).
    Ensures coercivity, exponential moments of the Gibbs measure, and confinement of iterates.
  • domain assumption Initial distribution μ0 has bounded positive density and finite ∫e^{||x||²}dμ0 < ∞ (Assumption 2.3).
    Provides finite initial moments and KL initialization bounds.
  • domain assumption Gradient surrogate g satisfies E||g(x,ξ)-∇F(x)||² ≤ δ(P||x||²+Q) (Assumption 3.1).
    Central condition for the inexact-gradient and zeroth-order results.
  • standard math Weighted Csiszár–Kullback–Pinsker inequality of Bolley–Villani [6, Thm 2.1].
    Core inequality in Lemma 2.10 for passing from KL to objective-value error.
  • standard math Vempala–Wibisono discrete ULA KL contraction under LSI [74, Thm 2].
    Gives Proposition 2.13, the KL convergence of exact ULA to the Gibbs measure.
  • standard math Raginsky–Rakhlin–Telgarsky Gibbs concentration bound [61, Prop 11].
    Controls E[F(Xπβ)] - minF in Theorem 2.6.
  • standard math Xu–Chen–Zou–Gu comparison lemma for SGLD vs GLD chains [76, Lem 4.4].
    Used in Proposition 3.8 to bound KL between inexact and exact chains; proof is delegated to the cited lemma.
  • standard math Holley–Stroock perturbation criterion [42].
    Used in the mollification proof of Proposition 2.5 to transfer LSI from smoothed potentials to the original C^{1,1} potential.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order." pith.science (2026). https://pith.science/paper/6L2FO5C2

@misc{pith2026260722353,
  author       = {Pith},
  title        = {Pith review of: Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6L2FO5C2}},
  note         = {Machine review of arXiv:2607.22353}
}
abstract

We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.

Figures

Figures reproduced from arXiv: 2607.22353 by the authors.

Figure 1
Figure 1. Averaged normalized optimality gap at the best iterate over the last 100 iterations, as a function [PITH_FULL_IMAGE:figures/full_fig_p025_1.png] view at source ↗
Figure 2
Figure 2. Averaged normalized optimality gap at the best iterate over the last 100 iterations, as a function [PITH_FULL_IMAGE:figures/full_fig_p026_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

79 extracted references · 1 linked inside Pith

  1. [76]

    Global convergence of Langevin dynamics based algorithms for nonconvex optimization

    Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of Langevin dynamics based algorithms for nonconvex optimization. InAdvances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018

    2018

  2. [1]

    Charles Audet and J. E. Dennis. Mesh adaptive direct search algorithms for constrained optimization. SIAM Journal on Optimization, 17(1):188–217, 2006

    2006

  3. [2]

    Springer, 2014

    Dominique Bakry, Ivan Gentil, and Michel Ledoux.Analysis and Geometry of Markov Diffusion Oper- ators, volume 348 ofGrundlehren der mathematischen Wissenschaften. Springer, 2014

    2014

  4. [3]

    Erdogdu, Adil Salim, and Shunshi Zhang

    Krishna Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of non-log-concave sampling: First-order stationarity guarantees for Langevin Monte Carlo. InProceedings of the 35th Conference on Learning Theory (COLT 2022), volume 178, page 2896–2923, 2022. 27

    2022

  5. [4]

    Constrained consensus-based optimization and numerical heuristics for the few particle regime.Journal of Global Optimization, 2026

    Jonas Beddrich, Enis Chenchene, Massimo Fornasier, Hui Huang, and Barbara Wohlmuth. Constrained consensus-based optimization and numerical heuristics for the few particle regime.Journal of Global Optimization, 2026

    2026

  6. [5]

    Julius R. Blum. Approximation Methods which Converge with Probability one.The Annals of Mathe- matical Statistics, 25(2):382 – 386, 1954

    1954

  7. [6]

    Weighted Csisz´ ar-Kullback-Pinsker inequalities and applications to transportation inequalities.Annales de la Facult´ e des sciences de Toulouse : Math´ ematiques, Ser

    Francois Bolley and C´ edric Villani. Weighted Csisz´ ar-Kullback-Pinsker inequalities and applications to transportation inequalities.Annales de la Facult´ e des sciences de Toulouse : Math´ ematiques, Ser. 6, 14(3):331–352, 2005

    2005

  8. [7]

    A distributed Plug- and-Play MCMC algorithm for high-dimensional inverse problems.IEEE Transactions on Computa- tional Imaging, 12:839–849, 2026

    Maxime Bouton, Pierre-Antoine Thouvenin, Audrey Repetti, and Pierre Chainais. A distributed Plug- and-Play MCMC algorithm for high-dimensional inverse problems.IEEE Transactions on Computa- tional Imaging, 12:839–849, 2026

    2026

Show all 79 references
  1. [8]

    Springer, 2015

    Anton Bovier and Frank den Hollander.Metastability: A Potential-Theoretic Approach, volume 351 of Grundlehren der mathematischen Wissenschaften. Springer, 2015

    2015

  2. [9]

    Metastability in reversible diffu- sion processes I: Sharp asymptotics for capacities and exit times.Journal of the European Mathematical Society, 6(4):399–424, 2004

    Anton Bovier, Michael Eckhoff, V´ eronique Gayrard, and Markus Klein. Metastability in reversible diffu- sion processes I: Sharp asymptotics for capacities and exit times.Journal of the European Mathematical Society, 6(4):399–424, 2004

    2004

  3. [10]

    Adam D. Bull. Convergence rates of efficient global optimization algorithms.Journal of Machine Learning Research, 12:2879–2904, 2011

    2011

  4. [11]

    Carrillo, Shi Jin, Lei Li, and Yuhua Zhu

    Jos´ e A. Carrillo, Shi Jin, Lei Li, and Yuhua Zhu. A consensus-based global optimization method for high dimensional machine learning problems.ESAIM: Control, Optimisation and Calculus of Variations, 27:S5, 2021

    2021

  5. [12]

    Functional inequalities for perturbed measures with applications to log-concave measures and to some Bayesian problems.Bernoulli, 28(4):2294–2321, 2022

    Patrick Cattiaux and Arnaud Guillin. Functional inequalities for perturbed measures with applications to log-concave measures and to some Bayesian problems.Bernoulli, 28(4):2294–2321, 2022

    2022

  6. [13]

    A note on Talagrand’s transportation inequality and logarithmic Sobolev inequality.Probability Theory and Related Fields, 148(1–2):285–304, 2010

    Patrick Cattiaux, Arnaud Guillin, and Li-Ming Wu. A note on Talagrand’s transportation inequality and logarithmic Sobolev inequality.Probability Theory and Related Fields, 148(1–2):285–304, 2010

    2010

  7. [14]

    Chen, Ayush Sekhari, and Karthik Sridharan

    August Y. Chen, Ayush Sekhari, and Karthik Sridharan. Langevin dynamics: A unified perspective on optimization via Lyapunov potentials. InOPT 2024: 16th Annual Workshop on Optimization for Machine Learning (NeurIPS Workshop), 2024

    2024

  8. [15]

    Zoo: Zeroth order optimiza- tion based black-box attacks to deep neural networks without training substitute models

    Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimiza- tion based black-box attacks to deep neural networks without training substitute models. InProceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AISec ’17, ...

    2017

  9. [16]

    Chatterji, Yasin Abbasi-Yadkori, Peter L

    Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, and Michael I. Jordan. Convergence rates for Langevin Monte Carlo in the nonconvex setting.Journal of Machine Learning Research, 20(164):1–49, 2019

    2019

  10. [17]

    Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang

    Sinho Chewi, Murat A. Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang. Analysis of Langevin Monte Carlo from Poincar´ e to log-Sobolev. InProceedings of the 35th Conference on Learning Theory, volume 178 ofProceedings of Machine Learning Research, pages 1–2. PMLR, 2022

    2022

  11. [18]

    Diffusion for global optimization inR n

    Tzuu-Shuh Chiang, Chii-Ruey Hwang, and Shuenn Jyi Sheu. Diffusion for global optimization inR n. SIAM Journal on Control and Optimization, 25(3):737–753, 1987

    1987

  12. [19]

    Conn, Katya Scheinberg, and Luis N

    Andrew R. Conn, Katya Scheinberg, and Luis N. Vicente.Introduction to Derivative-Free Optimization, volume 8 ofMPS-SIAM Series on Optimization. SIAM, 2009. 28

    2009

  13. [20]

    Dalalyan

    Arnak S. Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities.Journal of the Royal Statistical Society: Series B (Statistical Methodology), 79(3):651–676, 2017

    2017

  14. [21]

    Dalalyan and Avetik Karagulyan

    Arnak S. Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient.Stochastic Processes and their Applications, 129(12):5278–5311, 2019

    2019

  15. [22]

    Nagaraj, and Anant Raj

    Aniket Das, Dheeraj M. Nagaraj, and Anant Raj. Utilising the CLT structure in stochastic gradient based sampling: Improved analysis and faster algorithms. InProceedings of Thirty Sixth Conference on Learning Theory, volume 195 ofProceedings of Machine Learning Research, pages ...

    2023

  16. [23]

    Duchi, Michael I

    John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero- order convex optimization: The power of two function evaluations.IEEE Transactions on Information Theory, 61(5):2788–2806, 2015

    2015

  17. [24]

    Analysis of Langevin Monte Carlo via convex optimization.Journal of Machine Learning Research, 20(73):1–46, 2019

    Alain Durmus, Szymon Majewski, and B la˙ zej Miasojedow. Analysis of Langevin Monte Carlo via convex optimization.Journal of Machine Learning Research, 20(73):1–46, 2019

    2019

  18. [25]

    Nonasymptotic convergence analysis for the unadjusted Langevin algorithm.The Annals of Applied Probability, 27(3):1551–1587, 2017

    Alain Durmus and ´Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm.The Annals of Applied Probability, 27(3):1551–1587, 2017

    2017

  19. [26]

    Reflection couplings and contraction rates for diffusions.Probability Theory and Related Fields, 166(3):851–886, Dec 2016

    Andreas Eberle. Reflection couplings and contraction rates for diffusions.Probability Theory and Related Fields, 166(3):851–886, Dec 2016

    2016

  20. [27]

    Ehrhardt, Lorenz Kuger, and Carola-Bibiane Sch¨ onlieb

    Matthias J. Ehrhardt, Lorenz Kuger, and Carola-Bibiane Sch¨ onlieb. Proximal Langevin sampling with inexact proximal mapping.SIAM Journal on Imaging Sciences, 17(3):1729–1760, 2024

    2024

  21. [28]

    Erdogdu and Rasa Hosseinzadeh

    Murat A. Erdogdu and Rasa Hosseinzadeh. On the convergence of Langevin Monte Carlo: The interplay between tail growth and smoothness. InProceedings of Thirty Fourth Conference on Learning Theory, volume 134 ofProceedings of Machine Learning Research, pages 1776–1822. PMLR, 15–...

    2021

  22. [29]

    Flaxman, Adam T

    Abraham D. Flaxman, Adam T. Tauman Kalai, and Brendan H. McMahan. Online convex optimization in the bandit setting: Gradient descent without a gradient. InSODA ’05 Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385–394, January 2005

    2005

  23. [30]

    From consensus-based optimiza- tion to evolution strategies: Proof of global convergence, 2026

    Massimo Fornasier, Hui Huang, Jona Klemenc, and Greta Malaspina. From consensus-based optimiza- tion to evolution strategies: Proof of global convergence, 2026

    2026

  24. [31]

    Consensus-based optimization methods converge globally.SIAM Journal on Optimization, 34(3):2973–3004, 2024

    Massimo Fornasier, Timo Klock, and Konstantin Riedl. Consensus-based optimization methods converge globally.SIAM Journal on Optimization, 34(3):2973–3004, 2024

    2024

  25. [32]

    On the information-adaptive variants of the admm: An iteration complexity perspective.Journal of Scientific Computing, 76(1):327–363, Jul 2018

    Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the information-adaptive variants of the admm: An iteration complexity perspective.Journal of Scientific Computing, 76(1):327–363, Jul 2018

    2018

  26. [33]

    Diffusions for global optimization.SIAM Journal on Control and Optimization, 24(5):1031–1043, 1986

    Stuart Geman and Chii-Ruey Hwang. Diffusions for global optimization.SIAM Journal on Control and Optimization, 24(5):1031–1043, 1986

    1986

  27. [34]

    Stochastic first- and zeroth-order methods for nonconvex stochastic programming.SIAM Journal on Optimization, 23(4):2341–2368, 2013

    Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming.SIAM Journal on Optimization, 23(4):2341–2368, 2013

    2013

  28. [35]

    E. G. Gladyshev. On stochastic approximation.Theory of Probability & Its Applications, 10(2):275–278, 1965

    1965

  29. [36]

    SGD for structured nonconvex functions: Learn- ing rates, minibatching and interpolation

    Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learn- ing rates, minibatching and interpolation. InProceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 ofProceedings of Machine Learni...

    2021

  30. [37]

    Diffusion at absolute zero: Langevin sampling using successive Moreau envelopes.SIAM Journal on Imaging Sciences, 19(1):35–77, 2026

    Andreas Habring, Alexander Falk, Martin Zach, and Thomas Pock. Diffusion at absolute zero: Langevin sampling using successive Moreau envelopes.SIAM Journal on Imaging Sciences, 19(1):35–77, 2026

    2026

  31. [38]

    Subgradient Langevin methods for sampling from nonsmooth potentials.SIAM Journal on Mathematics of Data Science, 6(4):897–925, 2024

    Andreas Habring, Martin Holler, and Thomas Pock. Subgradient Langevin methods for sampling from nonsmooth potentials.SIAM Journal on Mathematics of Data Science, 6(4):897–925, 2024

    2024

  32. [39]

    Forward-KL convergence of time-inhomogeneous Langevin diffu- sions, 2026

    Andreas Habring and Martin Zach. Forward-KL convergence of time-inhomogeneous Langevin diffu- sions, 2026

    2026

  33. [40]

    Cooling schedules for optimal annealing.Mathematics of Operations Research, 13(2):311– 329, 1988

    Bruce Hajek. Cooling schedules for optimal annealing.Mathematics of Operations Research, 13(2):311– 329, 1988

    1988

  34. [41]

    Harris, K

    Charles R. Harris, K. Jarrod Millman, St´ efan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime ...

    2020

  35. [42]

    Logarithmic Sobolev inequalities and stochastic Ising models

    Richard Holley and Daniel Stroock. Logarithmic Sobolev inequalities and stochastic Ising models. Journal of statistical physics, 46(5-6):1159–1194, 1987

    1987

  36. [43]

    John D. Hunter. Matplotlib: A 2d graphics environment.Computing in Science & Engineering, 9(3):90– 95, 2007

    2007

  37. [44]

    The performance of the unadjusted Langevin algorithm without smoothness assumptions, 2025

    Tim Johnston, Iosif Lytras, Nikolaos Makras, and Sotirios Sabanis. The performance of the unadjusted Langevin algorithm without smoothness assumptions, 2025

    2025

  38. [45]

    Improved convergence rate of stochastic gradient Langevin dynam- ics with variance reduction and its application to optimization

    Yuri Kinoshita and Taiji Suzuki. Improved convergence rate of stochastic gradient Langevin dynam- ics with variance reduction and its application to optimization. InAdvances in Neural Information Processing Systems, volume 35, pages 19022–19034. Curran Associates, Inc., 2022

    2022

  39. [46]

    Zygalakis

    Teresa Klatzer, Savvas Melidonis, Marcelo Pereyra, and Konstantinos C. Zygalakis. Efficient Bayesian computation using Plug-and-Play priors for Poisson inverse problems.SIAM Journal on Imaging Sci- ences, 19(2):1325–1363, 2026

    2026

  40. [47]

    Proximal basin hopping: global optimization with guarantees, 2026

    Guillaume Lauga, Cesare Molinari, and Samuel Vaiter. Proximal basin hopping: global optimization with guarantees, 2026

    2026

  41. [48]

    Bayesian imaging using Plug & Play priors: When Langevin meets Tweedie.SIAM Journal on Imaging Sciences, 15(2):701–737, 2022

    R´ emi Laumont, Valentin De Bortoli, Andr´ es Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. Bayesian imaging using Plug & Play priors: When Langevin meets Tweedie.SIAM Journal on Imaging Sciences, 15(2):701–737, 2022

    2022

  42. [49]

    On maximum a posteriori estimation with Plug & Play priors and stochastic gradient descent.Journal of Mathematical Imaging and Vision, 65(1):140–163, Jan 2023

    R´ emi Laumont, Valentin De Bortoli, Andr´ es Almansa, Julie Delon, Alain Durmus, and Marcelo Pereyra. On maximum a posteriori estimation with Plug & Play priors and stochastic gradient descent.Journal of Mathematical Imaging and Vision, 65(1):140–163, Jan 2023

    2023

  43. [50]

    Almost sure convergence rates analysis and saddle avoidance of stochastic gradient methods.Journal of Machine Learning Research, 25(271):1–40, 2024

    Jun Liu and Ye Yuan. Almost sure convergence rates analysis and saddle avoidance of stochastic gradient methods.Journal of Machine Learning Research, 25(271):1–40, 2024

    2024

  44. [51]

    One-point gradient estimators for zeroth-order stochastic gradient Langevin dynamics

    Lewis Liu and Zhaoran Wang. One-point gradient estimators for zeroth-order stochastic gradient Langevin dynamics. InOPT2020: 12th Annual Workshop on Optimization for Machine Learning, 2020

    2020

  45. [52]

    Majka, Aleksandar Mijatovi´ c, and Lukasz Szpruch

    Mateusz B. Majka, Aleksandar Mijatovi´ c, and Lukasz Szpruch. Non-asymptotic bounds for sampling algorithms without log-concavity.The Annals of Applied Probability, 30(4):1534–1581, 2020. 30

    2020

  46. [53]

    Global optimization of Lipschitz functions

    C´ edric Malherbe and Nicolas Vayatis. Global optimization of Lipschitz functions. InProceedings of the 34th International Conference on Machine Learning, volume 70 ofProceedings of Machine Learning Research, pages 2314–2323. PMLR, 06–11 Aug 2017

    2017

  47. [54]

    Lee, Danqi Chen, and Sanjeev Arora

    Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. InAdvances in Neural Information Processing Systems, volume 36, pages 53038–53075. Curran Associates, Inc., 2023

    2023

  48. [55]

    Mattingly, Andrew M

    Jonathan C. Mattingly, Andrew M. Stuart, and Desmond J. Higham. Ergodicity for SDEs and approxi- mations: locally lipschitz vector fields and degenerate noise.Stochastic Processes and their Applications, 101(2):185–232, 2002

    2002

  49. [56]

    Convergence of zeroth-order proximal point algorithms in the high-temperature regime, 2026

    Emanuele Naldi, Hippolyte Labarri` ere, Cesare Molinari, and Silvia Villa. Convergence of zeroth-order proximal point algorithms in the high-temperature regime, 2026

    2026

  50. [57]

    Random gradient-free minimization of convex functions.Foun- dations of Computational Mathematics, 17(2):527–566, Apr 2017

    Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions.Foun- dations of Computational Mathematics, 17(2):527–566, Apr 2017

    2017

  51. [58]

    Unadjusted Langevin algorithm for non-convex weakly smooth potentials.Communications in Mathematics and Statistics, 13(4):979–1036, Aug 2025

    Dao Nguyen, Xin Dang, and Yixin Chen. Unadjusted Langevin algorithm for non-convex weakly smooth potentials.Communications in Mathematics and Statistics, 13(4):979–1036, Aug 2025

    2025

  52. [59]

    Pytorch: An imperative style, high-performance deep learning library

    Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu ...

    2019

  53. [60]

    A consensus-based model for global optimization and its mean-field limit.Mathematical Models and Methods in Applied Sciences, 27(1):183– 204, 2017

    Ren´ e Pinnau, Claudia Totzeck, Oliver Tse, and Stephan Martin. A consensus-based model for global optimization and its mean-field limit.Mathematical Models and Methods in Applied Sciences, 27(1):183– 204, 2017

    2017

  54. [61]

    Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis

    Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: a nonasymptotic analysis. InProceedings of the 2017 Conference on Learning Theory, volume 65 ofProceedings of Machine Learning Research, pages 1674–1703. PMLR...

    2017

  55. [62]

    A new formulation for zeroth-order op- timization of adversarial EXEmples in malware detection.IEEE Transactions on Information Forensics and Security, 21:506–515, 2026

    Marco Rando, Luca Demetrio, Lorenzo Rosasco, and Fabio Roli. A new formulation for zeroth-order op- timization of adversarial EXEmples in malware detection.IEEE Transactions on Information Forensics and Security, 21:506–515, 2026

    2026

  56. [63]

    An optimal structured zeroth- order algorithm for non-smooth optimization

    Marco Rando, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. An optimal structured zeroth- order algorithm for non-smooth optimization. InAdvances in Neural Information Processing Systems, volume 36, pages 36738–36767. Curran Associates, Inc., 2023

    2023

  57. [64]

    Stochastic zeroth order descent with structured directions.Computational Optimization and Applications, 89(3):691–727, Dec 2024

    Marco Rando, Cesare Molinari, Silvia Villa, and Lorenzo Rosasco. Stochastic zeroth order descent with structured directions.Computational Optimization and Applications, 89(3):691–727, Dec 2024

    2024

  58. [65]

    A structured proximal stochastic variance reduced zeroth-order algorithm.arXiv preprint arXiv:2506.23758, 2025

    Marco Rando, Cheik Traor´ e, Cesare Molinari, Lorenzo Rosasco, and Silvia Villa. A structured proximal stochastic variance reduced zeroth-order algorithm.arXiv preprint arXiv:2506.23758, 2025

    2025 arXiv

  59. [66]

    Zoba: An efficient single-loop zeroth-order bilevel optimization algo- rithm, 2026

    Marco Rando and Samuel Vaiter. Zoba: An efficient single-loop zeroth-order bilevel optimization algo- rithm, 2026

    2026

  60. [67]

    From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling

    Marien Renaud, Valentin De Bortoli, Arthur Leclaire, and Nicolas Papadakis. From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling. InAdvances in Neural Information Processing Systems, volume 38, pages 115709–115773. Curran Associates...

    2025

  61. [68]

    Roberts and Richard L

    Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations.Bernoulli, 2(4):341–363, 1996

    1996

  62. [69]

    Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference.Bernoulli, 28(3):1810–1834, 2022

    Abhishek Roy, Lingqing Shen, Krishna Balasubramanian, and Saeed Ghadimi. Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference.Bernoulli, 28(3):1810–1834, 2022

    2022

  63. [70]

    Automatic gain tuning for humanoid robots walking architectures using gradient-free optimization tech- niques

    Carlotta Sartore, Marco Rando, Giulio Romualdi, Cesare Molinari, Lorenzo Rosasco, and Daniele Pucci. Automatic gain tuning for humanoid robots walking architectures using gradient-free optimization tech- niques. In2024 IEEE-RAS 23rd International Conference on Humanoid Robots ...

    2024

  64. [71]

    Solis and Roger J-B

    Francisco J. Solis and Roger J-B. Wets. Minimization by random search techniques.Mathematics of Operations Research, 6(1):19–30, 1981

    1981

  65. [72]

    Discrete-time simulated annealing: A convergence analysis via the eyring–kramers law.Numerical Algebra, Control and Optimization, 14(4):778–794, 2024

    Wenpin Tang, Yuhang Wu, and Xun Yu Zhou. Discrete-time simulated annealing: A convergence analysis via the eyring–kramers law.Numerical Algebra, Control and Optimization, 14(4):778–794, 2024

    2024

  66. [73]

    Tail probability estimates of continuous-time simulated annealing processes.Numerical Algebra, Control and Optimization, 13(3&4):473–485, 2023

    Wenpin Tang and Xun Yu Zhou. Tail probability estimates of continuous-time simulated annealing processes.Numerical Algebra, Control and Optimization, 13(3&4):473–485, 2023

    2023

  67. [74]

    Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices

    Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. InAdvances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019

    2019

  68. [75]

    Springer Berlin, Heidelberg, Berlin, Heidelberg, 2009

    C´ edric Villani.Optimal Transport: Old and New, volume 338 ofGrundlehren der mathematischen Wissenschaften. Springer Berlin, Heidelberg, Berlin, Heidelberg, 2009

    2009

  69. [77]

    Inexact proximal point algorithms for zeroth-order global optimization, 2024

    Minxin Zhang, Fuqun Han, Yat Tin Chow, Stanley Osher, and Hayden Schaeffer. Inexact proximal point algorithms for zeroth-order global optimization, 2024

    2024

  70. [78]

    Faster convergence of stochastic gradient Langevin dynamics for non-log-concave sampling

    Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient Langevin dynamics for non-log-concave sampling. InProceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 ofProceedings of Machine Learning Research, pages ...

    2021

  71. [79]

    Moreover, their main result is a Wasserstein tracking bound to the Gibbs measure, rather than an explicit expected-excess-risk oracle complexity

    does not provide a directly applicable benchmark in the standard smooth dissipative regime considered 49 here. Moreover, their main result is a Wasserstein tracking bound to the Gibbs measure, rather than an explicit expected-excess-risk oracle complexity. Our zeroth-order res...

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.