Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values

Abstract

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 result to the mixed-integer setting: Mixed-integer convex optimization with $d$ continuous and $n$ discrete variables using function values requires $\tildeΩ(d^2\cdot 2^n)$ queries.

Disclosure

“formal verification in Lean Modern AI tools played a substantial role in developing the mathematical arguments in this work, and it is accurate to say that the AI model used solved the problem, not the author of this paper. In particular, GPT 5.6 Sol Pro was used following a workflow similar to that documented by OpenAI in connection with its recent preprint on the Cycle Double Cover Conjecture and accompanying prompt [16, 17]. Similar success in the optimization literature has rec”

PDF page 5

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-23T18:54:04.137157Z

Structural counts