Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
Zhuanghua Liu, Luo Luo · 2026
Read Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise by Zhuanghua Liu, Luo Luo (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-24513.txt.
Introduction
Zhuanghua Liu and Luo Luo study optimization where only noisy function values are available, not gradients, and the noise has heavy tails. Their stochastic zeroth-order method clips a two-point gradient estimate inside an online-to-nonconvex conversion scheme. Theory shows it reaches a Goldstein stationary point with dimension dependence matching the best known convex results. Its accuracy dependence matches the best known first-order methods for nonconvex nonsmooth problems, and experiments confirm the method works.
Catalog record
| CREATOR | Zhuanghua Liu, Luo Luo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43177 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24513
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise Zhuanghua Liu, Luo Luo Abstract 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 ( δ , ϵ ) (\delta,\epsilon) -Goldstein stationary point with zeroth-order oracle complexity of 𝒪 ( d p 2 ( p − 1 ) δ − 1 ϵ − 2 p − 1 p − 1 ) {\mathcal{O}}(d^{\frac{p}{2(p-1)}}\delta^{-1}\epsilon^{-\frac{2p-1}{p-1}}) , where d d is the problem dimension and p ∈ ( 1 , 2 ] p\in(1,2] is the order of bounded moments. Note that our dependence on dimension d d 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 δ \delta and ϵ \epsilon 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. 1 Introduction This paper considers the following unconstrained stochastic optimization problem \min_{x\in{\mathbb{R}}^{d}}f(x)={\mathbb{E}}_{\xi\sim{\mathcal{P}}}[F(x;\xi)], (1) where the stochastic component function F(x;\xi)\colon{\mathbb{R}}^{d}\to{\mathbb{R}} is L(\xi) -Lipschitz continuous with respect to x but possibly nonconvex and nonsmooth. Such formulation is very popular in machine learning applications, including statistical learning [ 14 , 48 , 32 ] , reinforcement learning [ 31 , 40 , 7 ] , deep neural networks [ 33 , 17 , 6 ] , and simulation optimization [ 19 , 34 ] . We focus on stochastic zeroth-order optimization where the algorithm can only access the noisy function evaluations. The primary motivation for such gradient-free oracles arises in the context of simulation optimization [ 19 , 34 ] , where gradients (first-order information) are expensive or even impossible to evaluate. There has been increasing interest in developing stochastic zeroth-order algorithms for nonconvex nonsmooth optimization under the bounded variance assumption [ 26 , 5 , 25 , 28 ] . In particular, the best known stochastic zeroth-order oracle complexity is achieved by applying the technique of online-to-nonconvex conversion, which attains the optimal dependence on the dimension. It is worth noting that the popular bounded variance assumption adopted in many existing analyses of stochastic nonconvex nonsmooth optimization is rather restrictive and often fails to hold in practice. In contrast, heavy-tailed noise has been widely observed in empirical studies across various real-world applications, including training the machine learning models [ 39 , 46 , 2 , 15 ] . This phenomenon motivates us to adopt the weaker assumption of p -th bounded moment on the noise of function value evaluations. Specifically, we assume formulation ( 1 ) holds that \displaystyle{\mathbb{E}}[L(\xi)^{p}]\leq L^{p}, for some constant L>0 , where p\in(1,2] denotes the order of the moment of the noise. The special case of p=2 leads to the bounded variance, which has been well studied [ 16 , 3 ] . For a general p\in(1,2) , the variance may be unbounded, giving rise to heavy-tailed noise distributions such as the Lévy \alpha -stable distribution. In such a case, all existing works on stochastic zeroth-order optimization focus on the convex setting [ 23 , 24 , 22 ] , while there is quite a limited understanding of the nonconvex case, which plays a crucial role in modern machine learning theory. In this paper, we propose an efficient stochastic zeroth-order stochastic algorithm called z eroth- o rder c lipped o nline-t o - n onconvex (ZOCOON) algorithm for solving stochastic nonconvex nonsmooth optimization under the heavy-tailed noise. Building upon the framework of online-to-nonconvex conversion [ 9 , 25 ] , our algorithm leverages the gradient clipping on the stochastic zeroth-order gradient estimator to mitigate the heavy-tailed noise. We establish the theoretical guarantee to show that our ZOCOON attains a (\delta,\epsilon) -Goldstein stationary point of the objective within the stochastic zeroth-order oracle complexity of {\mathcal{O}}(d^{\frac{p}{2(p-1)}}\delta^{-1}\epsilon^{-\frac{2p-1}{p-1}}) both in expectation and with high probability. Notably, the resulting dependence on the dimension d matches the best-known complexity bounds of stochastic zeroth-order methods for convex nonsmooth optimization. Moreover, the dependence on the accuracy parameters \delta and \epsilon is consistent with that of the best-known stochastic first-order methods under the heavy-tailed noise [ 27 ] . We compare the proposed methods with prior work for stochastic nonconvex nonsmooth optimization in Table 1 . We also show that our results extend naturally to the smooth setting, where the resulting \epsilon -dependence matches that of the best-known stochastic first-order methods [ 20 , 29 ] . Finally, we perform numerical experiments to validate the effectiveness of the proposed methods. Table 1: We compare the proposed ZOCOON algorithm with baseline methods by showing their stochastic zeroth-order oracle complexity bounds for achieving a (\delta,\epsilon) -Goldstein stationary point. In the case of p=2 , the complexity of our ZOCOON matches the best-known results of ZOO2N [ 25 ] . Methods Complexity p References GFM {\mathcal{O}}\left(d^{\frac{3}{2}}\delta^{-1}\epsilon^{-4}\right) 2 [ 26 ] GFM + {\mathcal{O}}\left(d^{\frac{3}{2}}\delta^{-1}\epsilon^{-3}\right) 2 [ 5 ] ZOO2N {\mathcal{O}}\left(d\delta^{-1}\epsilon^{-3}\right) 2 [ 25 ] ZOCOON {\mathcal{O}}\left(d^{\frac{p}{2(p-1)}}\delta^{-1}\epsilon^{-\frac{2p-1}{p-1}}\right) (1,2] Theorem 2 Paper Organization In Section 2 , we present a literature review on the convergence analysis of the nonconvex nonsmooth optimization problem and stochastic optimization with heavy-tailed noise. In Section 3 , we formalize the notations and assumptions of our problem and introduce the stationarity of the nonconvex nonsmooth optimization problem. In Section 4 , we propose our ZOCOON algorithm and provide its convergence analysis. In Section 5 , we conduct numerical experiments to demonstrate the improved effectiveness of the proposed methods. Finally, we conclude this work in Section 6 . 2 Related Work For general nonconvex nonsmooth optimization, 47 introduce the notion of (\delta,\epsilon) -Goldstein stationary points to describe the approximate stationarity of the Lipschitz continuous objective. They also provide an algorithm based on the non-standard oracle of Hadamard directional derivative to find (\delta,\epsilon) -Goldstein stationary points with a dimension-independent convergence rate. The subsequent works apply the perturbation techniques to design non-asymptotic convergent algorithms with the standard first-order oracle [ 10 , 43 ] . Moreover, 42 , 21 proved that randomization is necessary to achieve dimension-free complexity bounds for the general nonconvex nonsmooth optimization. Building on these insights, 9 proposed an online-to-nonconvex framework that achieves the optimal first-order oracle complexity bound for finding (\delta,\epsilon) -Goldstein stationary points. Besides, another line of work consider finding the near approximate stationary of the weakly convex objectives [ 12 , 11 ] . However, a broad class of nonconvex nonsmooth functions, including the objective function in training deep neural networks with ReLU activations, does not satisfy the weak convexity. In the scenario that the first-order information is unavailable, 26 designed the gradient-free method by considering the smoothed surrogate of the objective, achieving the (\delta,\epsilon) -Goldstein stationary points with the stochastic zeroth-order oracle complexity of {\mathcal{O}}(d^{\frac{3}{2}}\delta^{-1}\epsilon^{-4}) . Later, 5 introduced the variance reduction to attain an improved upper bound of {\mathcal{O}}(d^{\frac{3}{2}}\delta^{-1}\epsilon^{-3}) . Furthermore, 25 extended the framework of online-to-nonconvex conversion [