# Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 24 references that are in the map.
- First posted on arXiv 29 May 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Optimizing Molecules using Efficient Queries from Property Evaluations](https://mlsanity.com/paper/2011.01921/) (2020)
- [Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm](https://mlsanity.com/paper/2306.02159/) (2023)
- [Inexact Model: A Framework for Optimization and Variational Inequalities](https://mlsanity.com/paper/1902.00990/) (2019)
- [Randomized gradient-free methods in convex optimization](https://mlsanity.com/paper/2211.13566/) (2022)
- [Lossy compression of matrices by black-box optimisation of mixed integer nonlinear programming](https://mlsanity.com/paper/2204.10579/) (2022)
- [Learning Supervised PageRank with Gradient-Based and Gradient-Free Optimization Methods](https://mlsanity.com/paper/1603.00717/) (2016)
- [Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model](https://mlsanity.com/paper/2001.09013/) (2020)
- [Accelerated Zero-Order SGD Method for Solving the Black Box Optimization Problem under "Overparametrization" Condition](https://mlsanity.com/paper/2307.12725/) (2023)
- [Accelerated gradient methods with absolute and relative noise in the gradient](https://mlsanity.com/paper/2102.02921/) (2021)
- [Optimal inexactness schedules for Tunable Oracle based Methods](https://mlsanity.com/paper/2309.07787/) (2023)
- [The Black-Box Optimization Problem: Zero-Order Accelerated Stochastic Method via Kernel Approximation](https://mlsanity.com/paper/2310.02371/) (2023)
- [Accelerated zero-order SGD under high-order smoothness and overparameterized regime](https://mlsanity.com/paper/2411.13999/) (2024)
- [On Solving Minimization and Min-Max Problems by First-Order Methods with Relative Error in Gradients](https://mlsanity.com/paper/2503.06628/) (2025)

## Abstract (arXiv)

Zeroth-order (black-box) optimization is applied when gradients are unavailable and objective evaluations rely on expensive simulations. In many such applications, the oracle fidelity is tunable: higher-accuracy queries reduce noise but incur higher computational costs. To capture this trade-off, we study an accuracy-aware wall-clock model where each query with fidelity δ has a cost c(δ), and we minimize the total time Ttotal = sumk=1N c(δk), subject to a target accuracy constraint. We show how the choice of oracle type, noise model, and optimization scheme induces explicit wall-clock-optimal choices for the algorithmic parameters. For instance, we demonstrate that accelerated methods can be wall-clock inferior to non-accelerated schemes. Furthermore, we characterize the conditions under which a constant fidelity strategy is optimal in the Big-O sense. Our framework provides a unified methodology to translate convergence guarantees into practical fidelity and batching recommendations.