Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
Abstract
We study deterministic adaptive optimization of globally β-smooth, μ-strongly convex functions using exact scalar function values. Queries and outputs lie in B2d(R), and the minimizer lies in B2d(R/2). Set κ=β/μ, Q=βR2/ε, and Dd=(d/log(ed))1/3. For sufficiently large d and 0<ε≤ cεβR2, the minimax value complexity Nε satisfies Nε&≥ c dmin{√Q,√κ,Dd}, Nε&≤ C dmin{ √Q,√κ[1+log+(Q/κ)] }, where c,C,cε>0 are universal constants and log+(t)=max{0,log t}. The lower bound uses an exactly shielded smooth chain and batched delayed rotations; the upper bound combines finite differences, acceleration, and restart. When min{Q,κ}≤ Dd2, these bounds match up to constants in the accuracy-dominated regime Q≤κ and at constant relative accuracy ε=Θ(μR2). For arbitrarily higher accuracy in the range κ≤ Dd2, the bounds differ by at most 1+log(μR2/ε); the optimal accuracy dependence remains unresolved in general.
Related
- Sharp Minimax Rates for Highly Smooth Strongly Convex Zeroth-Order Optimization
- Minimax Oracle Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
BibTeX
@misc{wu2026nearoptimal,
title = {{Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization}},
author = {Wendao Wu and Haihan Zhang 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.2609.18728},
eprint = {2609.18728},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18728},
}
RIS
TY - UNPB
TI - Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
AU - Wendao Wu
AU - Haihan Zhang
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.2609.18728
UR - https://arxiv.org/abs/2609.18728
AB - We study deterministic adaptive optimization of globally β-smooth, μ-strongly convex functions using exact scalar function values. Queries and outputs lie in B_2^d(R), and the minimizer lies in B_2^d(R/2). Set κ=β/μ, Q=βR^2/ε, and D_d=(d/log(ed))^1/3. For sufficiently large d and 0<ε≤ c_εβR^2, the minimax value complexity N_ε satisfies N_ε&≥ c dmin{√Q,√κ,D_d}, N_ε&≤ C dmin{ √Q,√κ[1+log_+(Q/κ)] }, where c,C,c_ε>0 are universal constants and log_+(t)=max{0,log t}. The lower bound uses an exactly shielded smooth chain and batched delayed rotations; the upper bound combines finite differences, acceleration, and restart. When min{Q,κ}≤ D_d^2, these bounds match up to constants in the accuracy-dominated regime Q≤κ and at constant relative accuracy ε=Θ(μR^2). For arbitrarily higher accuracy in the range κ≤ D_d^2, the bounds differ by at most 1+log(μR^2/ε); the optimal accuracy dependence remains unresolved in general.
ER -