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

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

## Key facts

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

## Built on by (most cited first, 30 of 724)

- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Dash: Semi-Supervised Learning with Dynamic Thresholding](https://mlsanity.com/paper/2109.00650/) (2021)
- [Towards Understanding Sharpness-Aware Minimization](https://mlsanity.com/paper/2206.06232/) (2022)
- [Pass@k Training for Adaptively Balancing Exploration and Exploitation of Large Reasoning Models](https://mlsanity.com/paper/2508.10751/) (2025)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Do Differentiable Simulators Give Better Policy Gradients?](https://mlsanity.com/paper/2202.00817/) (2022)
- [Automatic Clipping: Differentially Private Deep Learning Made Easier and Stronger](https://mlsanity.com/paper/2206.07136/) (2022)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Make Sharpness-Aware Minimization Stronger: A Sparsified Perturbation Approach](https://mlsanity.com/paper/2210.05177/) (2022)
- [A Single-Timescale Method for Stochastic Bilevel Optimization](https://mlsanity.com/paper/2102.04671/) (2021)
- [Training Uncertainty-Aware Classifiers with Conformalized Deep Learning](https://mlsanity.com/paper/2205.05878/) (2022)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums](https://mlsanity.com/paper/2205.12173/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [FedNest: Federated Bilevel, Minimax, and Compositional Optimization](https://mlsanity.com/paper/2205.02215/) (2022)
- [Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning](https://mlsanity.com/paper/2201.09531/) (2022)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Variance-reduced Zeroth-Order Methods for Fine-Tuning Language Models](https://mlsanity.com/paper/2404.08080/) (2024)
- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [Second-Order Fine-Tuning without Pain for LLMs:A Hessian Informed Zeroth-Order Optimizer](https://mlsanity.com/paper/2402.15173/) (2024)

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