# From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 36 references that are in the map.
- First posted on arXiv 28 Apr 2026.

## Builds on (most cited first, 21 of 21)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints](https://mlsanity.com/paper/1408.3595/) (2014)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Stochastic Zeroth-order Optimization in High Dimensions](https://mlsanity.com/paper/1710.10551/) (2017)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [Zeroth-order Optimization with Weak Dimension Dependency](https://mlsanity.com/paper/2307.05753/) (2023)
- [An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/1804.02394/) (2018)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2405.09106/) (2024)
- [Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems](https://mlsanity.com/paper/2504.03069/) (2025)
- [Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2505.02281/) (2025)
- [Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles](https://mlsanity.com/paper/2510.15257/) (2025)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation](https://mlsanity.com/paper/2603.01430/) (2026)

## Abstract (arXiv)

While it is generally understood that zeroth-order (ZO) algorithms have an extra dependency on their number of iterations for any choice of parameters, compared to their first-order (FO) counterparts, in this work, we show that under several conditions, in expectation, ZO methods do not suffer from extra dimension dependencies in their convergence rates with respect to their FO counterparts. We look at optimisation algorithms from the dynamical systems perspective and analyse the conditions under which one can formulate the average of a ZO algorithm as the average of its FO counterpart with bounded perturbations with values dependent on design parameters. Then, using input-to-state stability properties, we show ZO methods follow the same decay rate as their FO counterparts and converge to a neighbourhood of the fixed point of FO methods, where its radius depends on the bound of the norm of the perturbations, which can be made arbitrarily small. The theoretical findings are illustrated via numerical examples.