math.OCNov 7, 2026

Zeroth-Order Langevin Dynamics for Stochastic Nonconvex Optimization: Curvature Regularization and Non-Asymptotic Guarantees

Authors: Stefano Bruno, Dong-Young Lim

Organizations: School of Mathematics, University of Edinburgh, Edinburgh, EH9 3FD, United Kingdom · UNIST InnoCORE AI-Space Solar Initiative, Ulsan National Institute of Science and Technology (UNIST), Ulsan, 44919, Republic of Korea · Department of Industrial Engineering and Artificial Intelligence Graduate School, Ulsan National Institute of Science and Technology (UNIST), Ulsan, 44919, Republic of Korea

Abstract

Zeroth-order methods provide a way to optimize stochastic nonconvex objectives using only noisy function evaluations. However, the smoothing inherent in their gradient estimators effectively modifies the objective being optimized. In particular, Gaussian smoothing with smoothing parameter η>0η>0 induces, to leading order, an implicit Hessian-trace regularization, which motivates the study of the curvature-regularized objective of the form f(x)+(η2/2)tr(∇2f(x))f(x)+(η^2/2) tr(\nabla^2 f(x)). We develop a non-asymptotic theory in the nonconvex setting for a class of algorithms called stochastic zeroth-order Langevin dynamics (ZOLD), which use only noisy function evaluations and do not have access to first- or higher-order derivative information, and derive excess-risk guarantees for the curvature-regularized objective. We first control the finite-time distribution of the ZOLD iterates in Wasserstein distance with respect to the Gibbs measure associated with the Gaussian-smoothed objective. An explicit coupling between the smoothing and inverse temperature parameters then quantifies the proximity of this measure to the Gibbs measure associated with the corresponding Hessian-trace-regularized objective. These distributional estimates in Wasserstein distance lead to excess-risk bounds for the curvature-regularized objective. Our analysis accommodates assumptions under which the stochastic function evaluations are allowed to have non-uniform dependence on the data stream. In addition, the constants in the non-asymptotic bounds do not rely on log-Sobolev or Poincaré inequalities as in prior zeroth-order Langevin analyses. To the best of our knowledge, this is the first non-asymptotic analysis of a zeroth-order Langevin method that simultaneously establishes excess-risk guarantees for a curvature-regularized objective and Wasserstein guarantees for the associated Gibbs measure in the nonconvex setting.

Figures & tables

Explore similar work

May 23, 2026

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a (δ,ε)(δ, ε)-Goldstein stationary point with zeroth-order oracle complexity of O(dp2(p−1)δ−1ε−2p−1p−1){\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}}), where dd is the problem dimension and p∈(1,2]p\in(1,2] is the order of bounded moments. Note that our dependence on dimension dd matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters δδ and εε is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.
Oct 20, 2026

Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding ε\varepsilon-stationary points of LL-smooth nonconvex functions on Rd\mathbb{R}^d from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most LELE; this is a fixed-matrix form of the effective rank condition used to explain zeroth-order fine-tuning. When ET≤dET\le d, the Gaussian two-point method that such fine-tuning uses needs only O(ET)O(ET) calls if it rejects steps that raise ff, where T=LΔ/ε2T=LΔ/\varepsilon^2 is the iteration count of gradient descent from initial gap ΔΔ, and we prove that every randomized method needs Ω(ET)Ω(ET) calls, so this cost is optimal up to constants. In contrast, every deterministic method needs Ω~(dmin⁡{T,ET})\widetildeΩ(d\min\{T,\sqrt{ET}\}) calls, and adaptive subspace search attains O(dmin⁡{T,ET})O(d\min\{T,\sqrt{ET}\}): a deterministic method pays about dd calls per discovered direction, and the trace budget allows about ET\sqrt{ET} directions. Determinism thus multiplies the cost by a factor of order d/(E+ET)d/(E+\sqrt{ET}) up to logarithmic factors, which grows linearly with dd for fixed EE and TT; once EE exceeds TT by a logarithmic factor, deterministic methods need Ω(dT)Ω(dT) calls, as without any trace budget. Our lower bounds hold for C∞C^\infty functions with the matrix bound on all of Rd\mathbb{R}^d, even when each call also returns gradient projections priced by rank.
Oct 14, 2026

On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as O(dε−4)O(dε^{-4}), with both factors separately necessary. We show that their product is unavoidable. We establish an Ω(dε−4)Ω(dε^{-4}) lower bound for smooth stochastic nonconvex optimization, yielding an Ω(dδ−1ε−3)Ω(dδ^{-1}ε^{-3}) bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.