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 $\beta$-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\sqrt{\beta R^2/\epsilon})$ 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 $\Omega\!\left(d\min\{\sqrt{\beta R^2/\epsilon},(d/\log(ed))^{1/3}\}\right)$ queries. Consequently, the minimax oracle complexity is $\Theta(d\sqrt{\beta R^2/\epsilon})$ throughout the moderate-accuracy regime $\beta R^2(\log(ed)/d)^{2/3}\leq\epsilon\leq c\beta 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.