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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-14 Page: https://delphi.science/r/arxiv/2607.13335 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…