mlsanityData to 7 Oct 2026

Stochastic Zeroth order Descent with Structured Directions

arXiv 2206.05124 ↗First posted 10 Jun 2022math.OC cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

We introduce and analyze Structured Stochastic Zeroth order Descent (S-SZD), a finite difference approach that approximates a stochastic gradient on a set of l≤ d orthogonal directions, where d is the dimension of the ambient space. These directions are randomly chosen and may change at each step. For smooth convex functions we prove almost sure convergence of the iterates and a convergence rate on the function values of the form O( (d/l) k-c) for every c<1/2, which is arbitrarily close to the one of Stochastic Gradient Descent (SGD) in terms of number of iterations. Our bound shows the benefits of using l multiple directions instead of one. For non-convex functions satisfying the Polyak-Lojasiewicz condition, we establish the first convergence rates for stochastic structured zeroth order algorithms under such an assumption. We corroborate our theoretical findings with numerical simulations where the assumptions are satisfied and on the real-world problem of hyper-parameter optimization in machine learning, achieving competitive practical performance.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 33 of its 81 references that are in the map. First posted on arXiv 10 Jun 2022.

Builds on

33 of 81 references.

References · 33

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2018A Tutorial on Bayesian Optimizationcited by 734
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 555
  5. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  6. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  7. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 109
  8. 2020Kernel methods through the roof: handling billions of points efficientlycited by 88
  9. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 82
  10. 2019A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimizationcited by 66
  11. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  12. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
21 more
  1. 2021A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimizationcited by 46
  2. 2020Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Samplingcited by 45
  3. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 38
  4. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 36
  5. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  6. 2021Zeroth order optimization with orthogonal random directionscited by 21
  7. 2017Gaussian Process bandits with adaptive discretizationcited by 20
  8. 2014Convergence of Stochastic Proximal Gradient Algorithmcited by 17
  9. 2020A stochastic subspace approach to gradient-free optimization in high dimensionscited by 15
  10. 2020A One-bit, Comparison-Based Gradient Estimatorcited by 15
  11. 2021Consensus-Based Optimization Methods Converge Globallycited by 15
  12. 2022Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regressioncited by 11
  13. 2021Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimizationcited by 10
  14. 2022The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problemscited by 9
  15. 2021Trends in Consensus-based optimizationcited by 8
  16. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  17. 2022Direct search based on probabilistic descent in reduced spacescited by 7
  18. 2014Simple Complexity Analysis of Simplified Direct Searchcited by 4
  19. 2015Randomized Derivative-Free Optimization of Noisy Convex Functionscited by 3
  20. 2020Expected complexity analysis of stochastic direct-searchcited by 3
  21. 2021Accelerating Derivative-Free Optimization with Dimension Reduction and Hyperparameter Learningcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 5.

8 papers.

  1. 2023Gradient-free optimization of highly smooth functions: improved analysis and a new algorithmcited by 12
  2. 2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
  3. 2025Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbationscited by 9
  4. 2025Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbationscited by 2
  5. 2025On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimizationcited by 2
  6. 2024A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detectioncited by 1
  7. 2024Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimizationcited by 1
  8. 2025A Structured Tour of Optimization with Finite Differencescited by 0