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

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 Theta(d-1/2), the previously applicable lower bound was Omega(d), inherited from the stronger full first-order oracle, while an upper bound from Protasov's value-only method requires O(d2log2 d) evaluations. By providing a lower bound of Omega(,fracd2log(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 tildeOmega(d2· 2n) queries.