mlsanityData to 14 Oct 2026

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

arXiv 2604.25372 ↗First posted 28 Apr 2026math.OC cs.LG cs.NAcited by 0

Not on the map. Why?

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.

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

21 of 36 references.

References · 21

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  4. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  5. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  6. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  7. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  8. 2014Analysis and Design of Optimization Algorithms via Integral Quadratic Constraintscited by 105
  9. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  10. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  11. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  12. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 37
9 more
  1. 2023Zeroth-order Optimization with Weak Dimension Dependencycited by 11
  2. 2018An Accelerated Directional Derivative Method for Smooth Stochastic Convex Optimizationcited by 5
  3. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  4. 2024Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oraclescited by 4
  5. 2025Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problemscited by 3
  6. 2025Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oraclescited by 3
  7. 2025Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oraclescited by 2
  8. 2026Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approachcited by 2
  9. 2026On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisationcited by 1

Built on by

Not cited yet.