Near-Optimal Deterministic Exact-Value Complexity for Smooth Convex Optimization

Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2609.18230Sep 16, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.18230
curl -X POST /api/v1/records/arxiv/2609.18230/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.18230/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'