# Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2018.

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

- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Revisiting Zeroth-Order Optimization for Memory-Efficient LLM Fine-Tuning: A Benchmark](https://mlsanity.com/paper/2402.11592/) (2024)
- [DeepZero: Scaling up Zeroth-Order Optimization for Deep Model Training](https://mlsanity.com/paper/2310.02025/) (2023)
- [Sparse MeZO: Less Parameters for Better Performance in Zeroth-Order LLM Fine-Tuning](https://mlsanity.com/paper/2402.15751/) (2024)
- [Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures](https://mlsanity.com/paper/2410.07698/) (2024)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [DPZero: Private Fine-Tuning of Language Models without Backpropagation](https://mlsanity.com/paper/2310.09639/) (2023)
- [Fast Policy Learning for Linear Quadratic Control with Entropy Regularization](https://mlsanity.com/paper/2311.14168/) (2023)
- [Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning](https://mlsanity.com/paper/2207.10415/) (2022)
- [Simultaneous Computation and Memory Efficient Zeroth-Order Optimizer for Fine-Tuning Large Language Models](https://mlsanity.com/paper/2410.09823/) (2024)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm](https://mlsanity.com/paper/2102.05198/) (2021)
- [Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization](https://mlsanity.com/paper/2107.06534/) (2021)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [Online Estimation and Optimization of Utility-Based Shortfall Risk](https://mlsanity.com/paper/2111.08805/) (2021)
- [STARNet: Sensor Trustworthiness and Anomaly Recognition via Approximated Likelihood Regret for Robust Edge Autonomy](https://mlsanity.com/paper/2309.11006/) (2023)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [ZOQO: Zero-Order Quantized Optimization](https://mlsanity.com/paper/2501.06736/) (2025)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [FOZO: Forward-Only Zeroth-Order Prompt Optimization for Test-Time Adaptation](https://mlsanity.com/paper/2603.04733/) (2026)
- [Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method](https://mlsanity.com/paper/2103.12954/) (2021)
- [A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2104.11283/) (2021)
- [Finding Optimal Policy for Queueing Models: New Parameterization](https://mlsanity.com/paper/2206.10073/) (2022)
- [Gradient-Free Method for Heavily Constrained Nonconvex Optimization](https://mlsanity.com/paper/2409.00459/) (2024)
- [Memory Savings at What Cost? A Study of Alternatives to Backpropagation](https://mlsanity.com/paper/2506.21833/) (2025)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Using Taylor-Approximated Gradients to Improve the Frank-Wolfe Method for Empirical Risk Minimization](https://mlsanity.com/paper/2208.13933/) (2022)
- [An Enhanced Zeroth-Order Stochastic Frank-Wolfe Framework for Constrained Finite-Sum Optimization](https://mlsanity.com/paper/2501.07201/) (2025)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)

## Abstract (arXiv)

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To facilitate zeroth-order optimization in high-dimensions, we explore the advantages of structural sparsity assumptions. Specifically, (i) we highlight an implicit regularization phenomenon where the standard stochastic gradient algorithm with zeroth-order information adapts to the sparsity of the problem at hand by just varying the step-size and (ii) propose a truncated stochastic gradient algorithm with zeroth-order information, whose rate of convergence depends only poly-logarithmically on the dimensionality. We next focus on avoiding saddle-points in non-convex setting. Towards that, we interpret the Gaussian smoothing technique for estimating gradient based on zeroth-order information as an instantiation of first-order Stein's identity. Based on this, we provide a novel linear-(in dimension) time estimator of the Hessian matrix of a function using only zeroth-order information, which is based on second-order Stein's identity. We then provide an algorithm for avoiding saddle-points, which is based on a zeroth-order cubic regularization Newton's method and discuss its convergence rates.