Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
Not on the map. Why?
Abstract (arXiv)
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 mathcal O(d^fracp2(p-1)δ-1ε^-frac2p-1p-1), where d is the problem dimension and p∈(1,2] is the order of bounded moments. Note that our dependence on dimension 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 δ 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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 27 of its 47 references that are in the map. First posted on arXiv 23 May 2026.
Builds on
27 of 47 references.
References · 27
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
- 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
- 2018Stochastic model-based minimization of weakly convex functionscited by 157
- 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 97
- 2022Do Differentiable Simulators Give Better Policy Gradients?cited by 83
- 2018Simple random search provides a competitive approach to reinforcement learningcited by 75
- 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 60
- 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
- 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
- 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
15 more
- 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
- 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
- 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 37
- 2017Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problemscited by 30
- 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 30
- 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 30
- 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
- 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
- 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 19
- 2023Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimizationcited by 16
- 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 15
- 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 13
- 2023Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variancecited by 10
- 2023Gradient-Free Methods for Non-Smooth Convex Stochastic Optimization with Heavy-Tailed Noise on Convex Compactcited by 2
- 2024Median Clipping for Zeroth-order Non-Smooth Convex Optimization and Multi-Armed Bandit Problem with Heavy-tailed Symmetric Noisecited by 1
Built on by
Not cited yet.