Sharp Minimax Rates for Highly Smooth Strongly Convex Zeroth-Order Optimization
Abstract
We determine the minimax dimension dependence of noisy zeroth-order optimization for globally strongly convex functions with higher-order smoothness in multilinear operator norm. Each query returns one function value with fresh independent Gaussian noise. For dimension d, query budget T, and any fixed finite smoothness order β>2, the minimax expected objective error satisfies ℰβ(T,d)=Θβ(min{1,(d2/T)(β−1)/β}), with dimension-independent strong-convexity, gradient-smoothness, higher-order-smoothness, noise, and minimizer-radius bounds. Thus, for sufficiently small target error ε, the necessary and sufficient number of noisy values is Θβ(d2ε−β/(β−1)), with no logarithmic loss. The new lower bound matches the dimension and budget dependence of the upper bound of Akhavan et al. (2024), and holds for arbitrary randomized adaptive algorithms with unrestricted query points. Its key step localizes a normalized hypercube with one radial cutoff: a query can emphasize one hidden coordinate, but the aggregate information about all coordinates remains small. A self-contained multiscale spherical estimator attains the matching upper bound by cancelling lower-order bias terms. Constants in the rates depend only on the fixed smoothness order under the stated normalization.
Related
- Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
- On Minimax Optimality and Uniqueness of Fixed-Step First-Order Methods for Smooth Convex Optimization
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
- Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
BibTeX
@misc{zhang2026sharp,
title = {{Sharp Minimax Rates for Highly Smooth Strongly Convex Zeroth-Order Optimization}},
author = {Haihan Zhang and Wendao Wu and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00276},
eprint = {2610.00276},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00276},
}
RIS
TY - UNPB
TI - Sharp Minimax Rates for Highly Smooth Strongly Convex Zeroth-Order Optimization
AU - Haihan Zhang
AU - Wendao Wu
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.00276
UR - https://arxiv.org/abs/2610.00276
AB - We determine the minimax dimension dependence of noisy zeroth-order optimization for globally strongly convex functions with higher-order smoothness in multilinear operator norm. Each query returns one function value with fresh independent Gaussian noise. For dimension d, query budget T, and any fixed finite smoothness order β>2, the minimax expected objective error satisfies ℰ_β(T,d)=Θ_β(min{1,(d^2/T)^(β−1)/β}), with dimension-independent strong-convexity, gradient-smoothness, higher-order-smoothness, noise, and minimizer-radius bounds. Thus, for sufficiently small target error ε, the necessary and sufficient number of noisy values is Θ_β(d^2ε^−β/(β−1)), with no logarithmic loss. The new lower bound matches the dimension and budget dependence of the upper bound of Akhavan et al. (2024), and holds for arbitrary randomized adaptive algorithms with unrestricted query points. Its key step localizes a normalized hypercube with one radial cutoff: a query can emphasize one hidden coordinate, but the aggregate information about all coordinates remains small. A self-contained multiscale spherical estimator attains the matching upper bound by cancelling lower-order bias terms. Constants in the rates depend only on the fixed smoothness order under the stated normalization.
ER -