Oracle-Complexity Gap in Derivative-Free Convex Optimization

For deterministically minimizing a convex 1-Lipschitz function on the $d$ -dimensional ball using only exact function values, the query complexity sat between $\Omega(d)$ and $O(d^2 \log^2 d)$ since 1996. The paper proves a near-quadratic lower bound $\Omega(d^2 / \log(d+1))$ , closing the gap: $Q(d, \sim d^{-1/2}) = \Theta(d^2)$ , a polynomial separation from full first-order information.

Result: Proved
Field: Optimization (Oracle Complexity)
Posed by: Vladimir Protasov (gap since 1996)
Year posed: 1996
Years open: 30y
Solved: 2026-07-14
Model: GPT-5.6 Sol Pro
Vendor: OpenAI
Collaborators: Phillip Kerger
Verification: Preprint (unrefereed)
Notability: No dedicated article

What the AI did

Kerger reports that GPT-5.6 Sol Pro solved the problem rather than the author, following a workflow like OpenAI's Cycle Double Cover effort. It first proved a $\tilde{\Omega}(d^2)$ lower bound at accuracy of order $d^{-3}$ (after ~148 minutes), which was then refined to the order- $d^{-1/2}$ result via a further ~230-minute run. The author verified the arguments by hand and takes full responsibility.

Verification

arXiv preprint 2607.13335 (14 Jul 2026) by Phillip Kerger (UC Berkeley), not yet peer-reviewed. The weaker-accuracy $\tilde{\Omega}(d^2)$ -at- $d^{-3}$ lower bound was formally verified in Lean (github.com/PhillipKerger/zero-order-bounds-lean-verification); the headline improvement to accuracy $d^{-1/2}$ is not yet Lean-formalized (it needs convex-geometry results like Urysohn's inequality absent from current Lean libraries) and rests on the author's hand verification.

Source

arXiv:2607.13335