mlsanityData to 7 Oct 2026

Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization

arXiv 2301.06428 ↗First posted 16 Jan 2023math.OC cs.LGcited by 16

Not on the map. Why?

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).

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

Builds on

35 of 65 references.

References · 35

  1. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  4. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  7. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  8. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 116
  9. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 109
  10. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
  11. 2022Do Differentiable Simulators Give Better Policy Gradients?cited by 83
  12. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
23 more
  1. 2018Simple random search provides a competitive approach to reinforcement learningcited by 75
  2. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  3. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  4. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  5. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  6. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  7. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 39
  8. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 38
  9. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  10. 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 37
  11. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 30
  12. 2019SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Pointscited by 25
  13. 2016Highly-Smooth Zero-th Order Online Optimization Vianney Perchetcited by 22
  14. 2018Stochastic Optimization for DC Functions and Non-smooth Non-convex Regularizers with Non-asymptotic Convergencecited by 16
  15. 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 15
  16. 2018Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attackcited by 14
  17. 2020Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functionscited by 13
  18. 2022On the Complexity of Finding Small Subgradients in Nonsmooth Optimizationcited by 7
  19. 2022On the Complexity of Deterministic Nonsmooth and Nonconvex Optimizationcited by 6
  20. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  21. 2021A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fastcited by 4
  22. 2021Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descentcited by 4
  23. 2019Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimizationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 2; 2026: 5.

16 papers.

Sort:

  1. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  2. 2023An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimizationcited by 20
  3. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 14
  4. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  5. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  6. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  7. 2026StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Modelscited by 4
  8. 2024Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimizationcited by 3
  9. 2024Mollification Effects of Policy Gradient Methodscited by 2
  10. 2025On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimizationcited by 2
  11. 2024Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradientcited by 1
  12. 2024How to Boost Any Loss Functioncited by 0
4 more
  1. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  2. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0
  3. 2026The Exponential Price of Determinism in Nonsmooth Nonconvex Optimizationcited by 0
  4. 2026Parameter-Free Zeroth-Order Optimization with Ellipsoidal Samplingcited by 0