{"id":"arxiv/2607.13335","url":"https://arxiv.org/abs/2607.13335","tags":["math.OC","cs.CC"],"score":0,"title":"Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values","domain":"math.OC","source":"arxiv","authors":["Phillip Kerger"],"reviews":0,"subject":"math.OC","summary":"We study the deterministic query complexity of minimizing a convex Lipschitz function over a $d$-dimensional Euclidean ball using only exact function values. At accuracy $Θ(d^{-1/2})$, the previously applicable lower bound was $Ω(d)$, inherited from the stronger full first-order oracle, while an upper bound from Protasov's value-only method requires $O(d^2\\log^2 d)$ evaluations. By providing a lower bound of $Ω(\\,\\frac{d^2}{\\log(d+1)})$ on the oracle complexity in this setting, we thereby close this gap dating back to 1996, up to polylogarithmic factors. Furthermore, we are able to lift this…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-14","reactions":{}}