Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise
Taha El Bakkali 1 Elmahdi Chayti 2 Qiuyi Zhang 3 Imane Rahali 1 Omar Saadi 1 1 College of Computing Mohammed VI Polytechnic University (UM6P) 2 EPFL 3 Elorian AI · 2026
Read Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise by Taha El Bakkali 1 Elmahdi Chayti 2 Qiuyi Zhang 3 Imane Rahali 1 Omar Saadi 1 1 College of Computing Mohammed VI Polytechnic University (UM6P) 2 EPFL 3 Elorian AI (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17394.txt.
Introduction
Taha El Bakkali and colleagues study stochastic zeroth-order optimization of smooth nonconvex goals under heavy-tailed gradient noise. These methods see only noisy function values, so they build finite-difference guesses from scalars. Their robust scalar-clipped method clips each scalar directional slope before combining. Given sample-wise smoothness and a weak moment tail condition it finds an approximate stationary point with high probability, matching optimal first-order accuracy dependence. A momentum variant is also analyzed.
Catalog record
| CREATOR | Taha El Bakkali 1 Elmahdi Chayti 2 Qiuyi Zhang 3 Imane Rahali 1 Omar Saadi 1 1 College of Computing Mohammed VI Polytechnic University (UM6P) 2 EPFL 3 Elorian AI |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110627 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17394
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise Taha El Bakkali 1 Elmahdi Chayti 2 Qiuyi Zhang 3 Imane Rahali 1 Omar Saadi 1 1 College of Computing Mohammed VI Polytechnic University (UM6P) 2 EPFL 3 Elorian AI Abstract We study stochastic zeroth-order (ZO) optimization of smooth nonconvex objectives under heavy-tailed sample-gradient noise. This regime is motivated by empirical evidence that gradient noise in modern machine learning can violate the bounded-variance assumptions used in classical ZO theory. While first-order methods have optimal rates under bounded p p -th moment noise for p ∈ ( 1 , 2 ] p\in(1,2] , analogous high-probability guarantees for nonconvex ZO methods are much less understood. The ZO setting is not a direct corollary of first-order theory. First-order methods observe stochastic gradients, whereas derivative-free methods only query noisy function values and build finite-difference estimates. Thus, weak- L p L_{p} control of ∇ F ( x , ξ ) − ∇ f ( x ) \nabla F(x;\xi)-\nabla f(x) must first be transferred to scalar directional estimates. We propose the Robust Scalar-Clipped Zeroth-Order method (RSC-ZO), a two-point method that clips each scalar directional derivative before aggregation. Under sample-wise smoothness and a weak- L p L_{p} tail condition on the sample-gradient noise, RSC-ZO finds an ε \varepsilon -stationary point with high probability using O ~ ( d p 2 ( p − 1 ) ε − 3 p − 2 p − 1 ) \widetilde{O}\!\left(d^{\frac{p}{2(p-1)}}\varepsilon^{-\frac{3p-2}{p-1}}\right) noisy function evaluations. This matches the optimal first-order ε \varepsilon -dependence. At p = 2 p=2 , the bound becomes O ~ ( d ε − 4 ) \widetilde{O}(d\varepsilon^{-4}) , matching the classical stochastic ZO dimension–accuracy dependence, but with a high-probability guarantee and under a weaker weak- L 2 L_{2} condition that can allow infinite variance. We also analyze a momentum variant and quantify its batch-size/stepsize tradeoff. 1 Introduction We consider the stochastic optimization problem \min_{x\in\mathbb{R}^{d}}f(x):=\mathbb{E}_{\xi\sim\mathbb{P}}\bigl[F(x;\xi)\bigr], where (\Xi,\mathcal{F},\mathbb{P}) is a probability space. For each \xi , x\mapsto F(x,\xi) is differentiable, and for each x , it is measurable with respect to \xi . We assume that f is finite-valued and bounded below. The finite-sum case is recovered by taking \Xi=\{1,\dots,n\} and \mathbb{P} to be the uniform distribution. In this paper, we consider the zeroth-order (ZO) setting where the algorithm can query only noisy function values F(x;\xi) , with no access to gradients. This oracle model arises naturally in black-box adversarial attacks ( 5 ; 14 ) , simulation-based optimization ( 8 ) , and, more recently, memory-efficient fine-tuning of large language models, where backpropagation is prohibitive and ZO methods such as MeZO achieve competitive performance using only forward passes ( 21 ) . For smooth nonconvex objectives, stochastic ZO methods ( 11 ; 3 ) establish the benchmark O(d\,\varepsilon^{-4}) query complexity for finding an \varepsilon -stationary point in expectation, when each sample function x\mapsto F(x;\xi) is smooth and the gradient noise has bounded variance. The bounded-variance assumption is, however, increasingly at odds with the regimes in which ZO methods are deployed. Empirical evidence in modern machine learning indicates that stochastic gradient noise is often heavy-tailed . For example, 28 provide evidence of heavy-tailed stochastic-gradient noise in BERT pretraining, with empirical variance estimates that fail to stabilize as the sample size increases. Similar behavior has been reported in image classification: 25 estimate stochastic-gradient tail indices below 2 , consistent with infinite-variance noise. Heavy-tailed gradients have also been documented in reinforcement learning ( 10 ) . In such regimes, the second moment may be infinite or poorly controlled. This poses a challenge not only for first-order gradient-based stochastic methods, but also for ZO methods, whose updates rely on gradient estimates reconstructed from noisy function evaluations. The first-order literature has responded with a substantial line of work showing that gradient clipping , possibly combined with momentum or normalization, can restore convergence guarantees under bounded p -th moment noise on the sample gradients for p\in(1,2] ( 12 ; 28 ; 6 ; 24 ; 23 ; 19 ; 4 ) . For smooth nonconvex first-order stochastic optimization under bounded p -th moment noise on the sample gradients, the standard benchmark is the optimal in-expectation \varepsilon -dependence \Theta(\varepsilon^{-(3p-2)/(p-1)}) 28 . Matching high-probability guarantees were later obtained by 6 . The zeroth-order picture is much less developed. For zeroth-order optimization, results under heavy-tailed noise are scarce and almost entirely confined to the convex setting. 15 obtain complexity bounds for nonsmooth convex ZO under symmetric heavy-tailed noise using mini-batched median estimates of two-point gradient differences followed by vector clipping; 16 treat convex compact domains; and 17 give an accelerated method when the variance is infinite. To the best of our knowledge, no prior result appears to give a high-probability complexity bound for smooth nonconvex stochastic ZO that matches the classical finite-variance expectation benchmark. This work closes this gap under a weak- L_{p} tail condition on the sample gradient noise \nabla F(x;\xi)-\nabla f(x) (Assumption 1.3 ), which is strictly weaker than the classical bounded p -th moment assumption and allows for infinite variance even when p=2 . Why the nonconvex ZO case is not a corollary. A natural temptation is to view ZO under heavy tails as an immediate consequence of first-order results. In first-order SGD, the noise assumption is imposed directly on the stochastic gradient noise \nabla F(x;\xi)-\nabla f(x) , and the update uses \nabla F(x;\xi) itself. Thus the stochastic error appearing in the update is exactly the quantity controlled by the assumption. In zeroth-order optimization, however, the algorithm does not observe \nabla F(x;\xi) . It only observes noisy function values and forms directional finite-difference estimates. Consequently, the error in the update is not the original sample-gradient noise vector, but a scalar directional derivative multiplied by a random direction, together with finite-difference and smoothing effects. Therefore, weak- L_{p} control of \nabla F(x;\xi)-\nabla f(x) must first be transferred to the scalar two-point estimator. This directional transfer is the main ZO-specific step in our proof and is absent from standard first-order analyses. The difficulty is amplified by the fact that our assumption is a weak- L_{p} tail condition, which is strictly weaker than the classical bounded p -th moment assumption. Contributions. We study a robust two-point ZO method, RSC-ZO , that combines spherical smoothing, shared-randomness directional estimates, and scalar clipping applied to each directional derivative before aggregation (Algorithm 1 ). Our contributions are as follows. • High-probability ZO stationarity under weak- L_{p} noise. Under sample-wise smoothness (Assumption 1.2 ) and a weak- L_{p} tail assumption on the sample-gradient noise (Assumption 1.3 ), we prove that RSC-ZO finds an \varepsilon -stationary point with high probability using \widetilde{O}\!\left(\frac{d^{\frac{p}{2(p-1)}}}{\varepsilon^{\frac{3p-2}{p-1}}}\right) noisy function evaluations, up to logarithmic and problem-dependent factors (Theorem B.11 and Remark B.12 ). At p=2 , this gives \widetilde{O}(d\,\varepsilon^{-4}) , matching the benchmark dimension–accuracy dependence of stochastic ZO methods under bounded-variance noise ( 11 ; 3 ) . Unlike these classical results, which are typically established in expectation, our guarantee holds with high probability and under a weaker weak- L_{2} tail condition. Moreover, the \varepsilon -dependence matches the optimal first-order rate of 28 . • A scalar-clipping analysis tailored to derivative-free estimation. A key step in the proof is to transfer weak- L_{p} control of the sample-gradient noise