Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
Abstract
We study zeroth-order optimization of convex and strongly convex functions with Hölder smoothness of order β>2 from values corrupted by random noise with bias independent of the method's random directions, a Lipschitz systematic error and a bounded adversarial error. We measure the number of function evaluations (calls), of sequential rounds of parallel calls, and the largest tolerable systematic and adversarial errors. For strongly convex functions with a bounded Hessian, we prove a lower bound of order d2ε−β/(β−1) on the number of calls, where d is the dimension and ε the accuracy, and find the sharp power of d under the stronger Hilbert--Schmidt smoothness for all β>2. An accelerated finite-difference method attains them in O(√κlog(1/ε)) rounds for condition number κ, like Nesterov's method with exact gradients, and tolerates the optimal systematic and, up to logarithms, adversarial errors; rate-optimal methods need Ω(log d) rounds. The same number of calls is attained when the Hessian grows at most linearly with the gradient and, for centered noise, without an upper bound on the Hessian, also in logarithmically many rounds. For convex functions, our lower bound improves the known one polynomially in d and is tight at the curvature of the hard instances; the systematic level is again optimal. These bounds extend to general norms and constraints; on the ℓ1 ball, mirror descent needs calls nearly linear in d. Experiments confirm the theory.
Related
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- The Minimax Complexity of Federated Optimization under Interpolation: The Role of Oracle Models
- Matching Full-Hessian Oracle Complexity for Nonconvex--Strongly-Concave Minimax Optimization
- Near-Optimal Higher-Order Oracle Complexity for Convex--Concave Minimax Optimization
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
BibTeX
@misc{loginov2026minimax,
title = {{Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions}},
author = {Timofei Loginov and Darina Dvinskikh and Nazarii Tupitsa and Osman Osmanov and Yuriy Dorn and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05517},
eprint = {2610.05517},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05517},
}
RIS
TY - UNPB
TI - Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
AU - Timofei Loginov
AU - Darina Dvinskikh
AU - Nazarii Tupitsa
AU - Osman Osmanov
AU - Yuriy Dorn
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.05517
UR - https://arxiv.org/abs/2610.05517
AB - We study zeroth-order optimization of convex and strongly convex functions with Hölder smoothness of order β>2 from values corrupted by random noise with bias independent of the method's random directions, a Lipschitz systematic error and a bounded adversarial error. We measure the number of function evaluations (calls), of sequential rounds of parallel calls, and the largest tolerable systematic and adversarial errors. For strongly convex functions with a bounded Hessian, we prove a lower bound of order d^2ε^−β/(β−1) on the number of calls, where d is the dimension and ε the accuracy, and find the sharp power of d under the stronger Hilbert--Schmidt smoothness for all β>2. An accelerated finite-difference method attains them in O(√κlog(1/ε)) rounds for condition number κ, like Nesterov's method with exact gradients, and tolerates the optimal systematic and, up to logarithms, adversarial errors; rate-optimal methods need Ω(log d) rounds. The same number of calls is attained when the Hessian grows at most linearly with the gradient and, for centered noise, without an upper bound on the Hessian, also in logarithmically many rounds. For convex functions, our lower bound improves the known one polynomially in d and is tight at the curvature of the hard instances; the systematic level is again optimal. These bounds extend to general norms and constraints; on the ℓ_1 ball, mirror descent needs calls nearly linear in d. Experiments confirm the theory.
ER -