{"id":"arxiv/2609.18230","url":"https://arxiv.org/abs/2609.18230","tags":["math.OC"],"score":0,"title":"Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"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\\sqrt{β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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}