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

arXiv: https://arxiv.org/abs/2607.13335 · HTML: https://mlsanity.com/paper/2607.13335/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model](https://mlsanity.com/paper/2609.30215/) (2026)

## Abstract (arXiv)

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.