# Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization

arXiv: https://arxiv.org/abs/2301.06428 · HTML: https://mlsanity.com/paper/2301.06428/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 65 references that are in the map.
- First posted on arXiv 16 Jan 2023.

## Builds on (most cited first, 30 of 35)

- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Do Differentiable Simulators Give Better Policy Gradients?](https://mlsanity.com/paper/2202.00817/) (2022)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Simple random search provides a competitive approach to reinforcement learning](https://mlsanity.com/paper/1803.07055/) (2018)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization](https://mlsanity.com/paper/2008.08170/) (2020)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions](https://mlsanity.com/paper/2112.06969/) (2021)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functions](https://mlsanity.com/paper/2112.09002/) (2021)
- [SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points](https://mlsanity.com/paper/1904.09265/) (2019)
- [Highly-Smooth Zero-th Order Online Optimization Vianney Perchet](https://mlsanity.com/paper/1605.08165/) (2016)
- [Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergence](https://mlsanity.com/paper/1811.11829/) (2018)
- [No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzians](https://mlsanity.com/paper/2210.06907/) (2022)
- [Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack](https://mlsanity.com/paper/1812.11377/) (2018)
- [Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions](https://mlsanity.com/paper/2002.04130/) (2020)
- [On the Complexity of Finding Small Subgradients in Nonsmooth Optimization](https://mlsanity.com/paper/2209.10346/) (2022)

## Built on by (most cited first, 17 of 17)

- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2307.04504/) (2023)
- [General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimization](https://mlsanity.com/paper/2411.07061/) (2024)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Private Zeroth-Order Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2406.19579/) (2024)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2406.01484/) (2024)
- [Mollification Effects of Policy Gradient Methods](https://mlsanity.com/paper/2405.17832/) (2024)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient](https://mlsanity.com/paper/2405.17761/) (2024)
- [How to Boost Any Loss Function](https://mlsanity.com/paper/2407.02279/) (2024)
- [Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationarity](https://mlsanity.com/paper/2601.19730/) (2026)
- [Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2605.24513/) (2026)
- [The Exponential Price of Determinism in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2609.23837/) (2026)
- [Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling](https://mlsanity.com/paper/2609.38561/) (2026)
- [Dimension-Free Decentralized Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2610.05789/) (2026)

## Abstract (arXiv)

We consider the optimization problem of the form minx ∈ ℝd f(x) triangleq mathbbExi [F(x; xi)], where the component F(x;xi) is L-mean-squared Lipschitz but possibly nonconvex and nonsmooth. The recently proposed gradient-free method requires at most O( L4 d3/2 ε-4 + Delta L3 d3/2 δ-1 ε-4) stochastic zeroth-order oracle complexity to find a (δ,ε)-Goldstein stationary point of objective function, where Delta = f(x0) - infx ∈ ℝd f(x) and x0 is the initial point of the algorithm. This paper proposes a more efficient algorithm using stochastic recursive gradient estimators, which improves the complexity to O(L3 d3/2 ε-3+ Delta L2 d3/2 δ-1 ε-3).