Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
Abstract
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions, focusing on non-asymptotic expected excess-risk bounds rather than sampling guarantees for the full target distribution. A main methodological message is that relative-entropy sampling guarantees can be converted directly into expected objective-value guarantees, without passing through Wasserstein distance. This direct KL-to-objective route yields sharper dependence on the Log-Sobolev constant, which may scale exponentially with inverse temperature and dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds in terms of inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to inexact ULA, allowing 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 on function evaluations. We show that Gaussian and spherical finite-difference estimators fit the theory and obtain explicit function-evaluation complexity bounds. 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 spherical zeroth-order scheme.
Related
- Multilevel Monte Carlo for Zeroth-Order Stochastic Bilevel Optimization with Inexact Lower Level Solves
- Primal-Dual Inexact Newton-MR for Nonconvex Optimization with Equality Constraints
- Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
- On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
- Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
BibTeX
@misc{naldi2026langevin,
title = {{Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order}},
author = {Emanuele Naldi and Marco Rando and Lorenzo Rosasco and Silvia Villa},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.22353},
eprint = {2607.22353},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.22353},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
AU - Emanuele Naldi
AU - Marco Rando
AU - Lorenzo Rosasco
AU - Silvia Villa
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2607.22353
UR - https://arxiv.org/abs/2607.22353
AB - We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions, focusing on non-asymptotic expected excess-risk bounds rather than sampling guarantees for the full target distribution. A main methodological message is that relative-entropy sampling guarantees can be converted directly into expected objective-value guarantees, without passing through Wasserstein distance. This direct KL-to-objective route yields sharper dependence on the Log-Sobolev constant, which may scale exponentially with inverse temperature and dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds in terms of inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to inexact ULA, allowing 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 on function evaluations. We show that Gaussian and spherical finite-difference estimators fit the theory and obtain explicit function-evaluation complexity bounds. 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 spherical zeroth-order scheme.
ER -