Research map / Optimization / Nonconvex and smooth optimization

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

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows via input-to-state stability that averaged Gaussian zeroth-order GD, heavy ball, NAG and L2-regularised GD inherit first-order convergence rates with no extra dimension dependence in iteration complexity, converging to a neighbourhood whose radius carries the dimension factor.

Problem

Zeroth-order optimisation is commonly believed to incur an extra dimension-dependent factor in iteration complexity compared with first-order methods.

Approach

Reformulate the averaged Gaussian ZO iterates as perturbed FO dynamics with bounded perturbations, then apply discrete-time input-to-state stability (ISS) Lyapunov results to transfer FO decay rates to ZO methods, with the dimension appearing only in the radius of the convergence neighbourhood.

Key results

• On a 1000-dimensional strongly convex quadratic, ZO-GD tracks GD with its deviation shrinking as step size h decreases.
• On a two-layer MNIST network (n=100,609), GD, HB, NAG and their ZO counterparts all reach 99.55% train and 99.40% test accuracy.
• Across network sizes from n≈12,700 to ≈201,000, the ZO/FO iteration ratio stays between 0.99 and 1.05, while ZO runs take about 4 to 5.7 times longer per run.

Surprising findings

• The ZO/FO iteration ratio stays close to 1 across dimensions, contrary to the commonly assumed O(n) overhead.

Limitations

• Results are in expectation and local, holding on a ball around the fixed point.
• Achieving small neighbourhood may require parameter choices (mu, t) depending on problem parameters, so total function-evaluation cost may retain dimension dependence.
• Analysis covers strongly convex or L2-regularised objectives; the non-convex case is addressed only via regularisation.

Experimental setup

Datasets: MNIST

Benchmarks: MNIST (digits 0 vs 1)

Metrics: training loss train accuracy test accuracy iteration ratio ZO/FO time ratio ZO/FO

Baselines: gradient descent ZO-GD heavy ball Nesterov accelerated gradient

Builds on: ISS for discrete-time systems Nesterov (Gaussian smoothing ZO) heavy ball Nesterov accelerated gradient

Closest papers by meaning

• Refining Adaptive Zeroth-Order Optimization at Ease (ICML 2025 · similarity 0.86)
• Adaptively Incorporating Directional Hints into Zeroth-Order Optimization (NeurIPS 2026 · similarity 0.85)
• ZNO: Stable Rational Neural Operators in the Z-Domain for Discrete-Time Dynamics (NeurIPS 2026 · similarity 0.85)
• Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.85)
• A Memory Efficient Unified Algorithm for Online Learning of Linear Dynamical Systems (NeurIPS 2026 · similarity 0.85)
• Zeroth-Order Sharpness-Aware Learning with Exponential Tilting (NeurIPS 2026 · similarity 0.84)