mlsanityData to 14 Oct 2026

Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming

arXiv 1309.5549 ↗First posted 22 Sep 2013math.OC cs.CC stat.MLcited by 724

Not on the map. Why?

Cited by 24 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and show that such modification allows to improve significantly the large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available.

Key facts. Cited by 724 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Sep 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 2; 2021: 93; 2022: 101; 2023: 101; 2024: 139; 2025: 131; 2026: 157.

724 papers.

Sort:

By area:

  1. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 193
  2. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 148
  3. 2022Towards Understanding Sharpness-Aware Minimizationcited by 146
  4. 2025Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Modelscited by 138
  5. 2021Decentralized Federated Averagingcited by 114
  6. 2024Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmarkcited by 114
  7. 2022A framework for bilevel optimization that enables stochastic and global variance reduction algorithmscited by 99
  8. 2025Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimizationcited by 92
  9. 2022Do Differentiable Simulators Give Better Policy Gradients?cited by 89
  10. 2022Automatic Clipping: Differentially Private Deep Learning Made Easier and Strongercited by 88
  11. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  12. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
38 more
  1. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  2. 2022Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learningcited by 79
  3. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  4. 2023DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Trainingcited by 76
  5. 2021Learning with User-Level Privacycited by 72
  6. 2022Make Sharpness-Aware Minimization Stronger: A Sparsified Perturbation Approachcited by 70
  7. 2021A Single-Timescale Method for Stochastic Bilevel Optimizationcited by 69
  8. 2022Training Uncertainty-Aware Classifiers with Conformalized Deep Learningcited by 64
  9. 2024MARS: Unleashing the Power of Variance Reduction for Training Large Modelscited by 64
  10. 2022Byzantine Machine Learning Made Easy by Resilient Averaging of Momentumscited by 63
  11. 2022Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delayscited by 63
  12. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  13. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  14. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  15. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  16. 2024Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Modelscited by 54
  17. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 53
  18. 2024Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizercited by 53
  19. 2024Friendly Sharpness-Aware Minimizationcited by 53
  20. 2024Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structurescited by 50
  21. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  22. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  23. 2021A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimizationcited by 46
  24. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  25. 2023Improving the Model Consistency of Decentralized Federated Learningcited by 45
  26. 2023Towards Sustainable Learning: Coresets for Data-efficient Deep Learningcited by 44
  27. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  28. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 43
  29. 2023An Adaptive Policy to Employ Sharpness-Aware Minimizationcited by 43
  30. 2021Anarchic Federated Learningcited by 42
  31. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  32. 2023An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learningcited by 41
  33. 2024Private Fine-tuning of Large Language Models with Zeroth-order Optimizationcited by 41
  34. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  35. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  36. 2021Oracle Complexity in Nonsmooth Nonconvex Optimizationcited by 39
  37. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  38. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39

50 most cited of 724 All 724 (JSON)