Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization
Abstract
We study the deterministic oracle complexity of smooth convex optimization when the algorithm receives only exact function values. The objective is a globally β-smooth convex function, all queries and the final output are restricted to the Euclidean ball of radius R, and the unique minimizer lies in the ball of radius R/2. We establish an upper bound of O(d√(βR2/ε)) using coordinate finite differences together with an error-robust accelerated projected method. Our main contribution is a matching lower bound, up to the high-accuracy saturation of the construction: any deterministic adaptive value-oracle algorithm requires Ω (dmin{√(βR2/ε),(d/log(ed))1/3}) queries. Consequently, the minimax oracle complexity is Θ(d√(βR2/ε)) throughout the moderate-accuracy regime βR2(log(ed)/d)2/3≤ε≤ cβR2 for a universal constant c>0. The lower bound must account for the fact that a single exact real value can encode arbitrarily much information. To overcome this difficulty, we construct a single fixed smooth convex hard instance using a Moreau-smoothed biased max chain, an exact prefix-shielding mechanism, and batched delayed rotations. These techniques preserve consistency with the full adaptive transcript and establish the optimality of the square-root complexity branch for deterministic bounded-query algorithms.
Related
- Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
- On the Optimal Linear Minimization Oracle Complexity of Active-Hull Methods for Minimizing Convex Hölder Smooth Functions
- Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization
- Optimal Gradient-Norm Minimization in Non-Euclidean Hölder-Smooth Convex Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
BibTeX
@misc{wu2026nearoptimal,
title = {{Near-Optimal Deterministic Exact-Value Complexity for Smooth 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.18230},
eprint = {2609.18230},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18230},
}
RIS
TY - UNPB
TI - Near-Optimal Deterministic Exact-Value Complexity for Smooth 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.18230
UR - https://arxiv.org/abs/2609.18230
AB - We study the deterministic oracle complexity of smooth convex optimization when the algorithm receives only exact function values. The objective is a globally β-smooth convex function, all queries and the final output are restricted to the Euclidean ball of radius R, and the unique minimizer lies in the ball of radius R/2. We establish an upper bound of O(d√(βR^2/ε)) using coordinate finite differences together with an error-robust accelerated projected method. Our main contribution is a matching lower bound, up to the high-accuracy saturation of the construction: any deterministic adaptive value-oracle algorithm requires Ω (dmin{√(βR^2/ε),(d/log(ed))^1/3}) queries. Consequently, the minimax oracle complexity is Θ(d√(βR^2/ε)) throughout the moderate-accuracy regime βR^2(log(ed)/d)^2/3≤ε≤ cβR^2 for a universal constant c>0. The lower bound must account for the fact that a single exact real value can encode arbitrarily much information. To overcome this difficulty, we construct a single fixed smooth convex hard instance using a Moreau-smoothed biased max chain, an exact prefix-shielding mechanism, and batched delayed rotations. These techniques preserve consistency with the full adaptive transcript and establish the optimality of the square-root complexity branch for deterministic bounded-query algorithms.
ER -