🔢 mathematics

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

This paper closes a long-standing gap in the deterministic query complexity of derivative-free convex optimization by establishing a near-quadratic lower bound of $\Omega(d^2/\log d)$ for exact function values, thereby matching the best known upper bound up to polylogarithmic factors and extending the result to mixed-integer settings.

Original authors: Phillip Kerger

Published 2026-07-16

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Phillip Kerger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy valley. You can't see the ground, and you don't have a map. The only tool you have is a magical sensor that, when you place it on the ground, tells you the exact height at that specific spot. You want to find the bottom of the valley as quickly as possible, but you can't see the slope or the direction of the hill; you only get a single number: "Here, it is 100 feet high." This is the world of derivative-free optimization. In science and engineering, we often face problems where we can't calculate how a system changes (the "derivative" or slope) because the system is a black box, a complex simulation, or a physical experiment. We have to rely on trial and error, asking the system, "What happens if I do this?" and getting a precise answer.

For decades, mathematicians have been arguing about how many of these "height checks" are actually needed to guarantee finding the bottom of the valley. If you could also ask for the slope (which way is down?), you could find the bottom very quickly. But if you are only allowed to ask for the height, the rules change. Until now, there was a massive gap in our understanding. Some smart algorithms suggested you might need a huge number of checks (roughly the square of the number of dimensions), while the best theoretical proof said you only needed a number equal to the dimensions themselves. It was like one group saying, "You'll need to check every square inch of a football field," and another saying, "You only need to check a few spots." This paper steps in to settle the score, proving that the "football field" estimate is much closer to the truth than the "few spots" idea.

The paper, titled "Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization," by Phillip Kerger, tackles this exact puzzle. The author, with significant help from advanced AI tools, proves that when you are restricted to using only exact height values (no slopes allowed) to find the minimum of a nonsmooth, bowl-shaped function (specifically, a function made of flat, linear pieces joined together) in a high-dimensional space, you are stuck doing a lot more work than previously thought. Specifically, the paper establishes a new, much stronger lower bound: the number of checks you need grows roughly with the square of the number of dimensions (written mathematically as $\tilde{\Omega}(d^2)$ ), rather than just linearly.

To understand why this matters, think of the "dimensions" as the number of knobs you have to turn on a machine. If you have 10 knobs, the old, weaker proof suggested you might only need to check about 10 or 20 settings. The new proof shows that, in the worst-case scenario, you might actually need to check hundreds or even thousands of settings (roughly $10^2$ or more). The author constructs a clever "adversarial" scenario where a tricky computer program (the oracle) answers your questions in a way that keeps you guessing for as long as possible. By carefully analyzing how much information each answer actually gives you, the paper demonstrates that the "slope-free" method is inherently much slower than the "slope-aware" method.

The paper also extends this discovery to a more complex scenario called mixed-integer optimization. Imagine your valley has not just continuous knobs (like a volume dial) but also switches that can only be flipped on or off (like a light switch). The paper proves that the difficulty of finding the bottom multiplies: if you have $n$ switches and $d$ dials, the number of checks you need explodes to roughly $2^n \times d^2$ . This means that adding just a few switches makes the problem exponentially harder, on top of the already quadratic difficulty of the dials.

Crucially, the paper doesn't just guess this; it provides a rigorous mathematical proof. It rules out the possibility that a clever, deterministic algorithm could magically bypass this quadratic barrier using only exact values. The author even used formal verification software (a tool that checks math proofs line-by-line) to ensure the logic holds up, and they openly acknowledge that modern AI played a major role in discovering the proof. The result closes a gap in mathematical knowledge that had been open since 1996, showing that when you are blind to the slopes of your problem, you really do have to pay the price in extra time and effort.

Technical Summary: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization

Problem Statement
This paper investigates the deterministic query complexity of minimizing a convex, 1-Lipschitz function over a $d$ -dimensional Euclidean ball ( $B_d$ ) using only exact function values (zeroth-order oracle). The study focuses on the worst-case number of evaluations required to find an $\varepsilon$ -approximate solution, specifically at an accuracy of $\varepsilon = \Theta(d^{-1/2})$ .

Prior to this work, a significant polynomial gap existed in the literature for this setting:

Lower Bound: The best known lower bound was $\Omega(d)$ , inherited from the stronger first-order oracle model (where subgradients are available).
Upper Bound: Protasov's (1996) deterministic method required $O(d^2 \log^2 d)$ evaluations to achieve the same accuracy.

The central question addressed is whether the lack of derivative information fundamentally increases the complexity from linear to quadratic in the dimension $d$ , or if the $\Omega(d)$ bound is tight.

Methodology
The authors construct a "hard family" of functions and a "resisting oracle" to establish a near-quadratic lower bound. The proof proceeds through four main components:

Hard Function Family: The authors define a class of functions $f_W(x, z) = \max_{i \in [m]} \{ ax_i + \langle w_i, z \rangle \}$ , where $m = d/2$ , $x, z \in \mathbb{R}^m$ , and the rows $w_i$ are vectors in a small ball of radius $\tau = \Theta(m^{-1/2})$ . These functions are convex and 1-Lipschitz. The minimizers of these functions are determined by the Euclidean projection of the origin onto the convex hull of the vectors defining the linear pieces.
Exact Resisting Oracle: Instead of providing a single function, the adversary maintains a "rectangular" uncertainty set $P_1 \times \dots \times P_m$ , where each $P_i$ is a compact convex set of possible row vectors $w_i$ . The invariant is that any selection of rows from these sets produces a function consistent with the entire history of query responses.
- When the algorithm queries a point, the adversary analyzes the affine functionals defined by the query on each row set.
- If a row is non-constant, the adversary cuts the set by a hyperplane (reducing dimension by 1) but ensures the remaining set retains a significant fraction of its intrinsic volume.
- If all relevant rows are constant, the adversary returns the constant value without reducing dimension.
Aggregate Width and Indistinguishability: The proof tracks the total codimension and the logarithmic loss of intrinsic volume across all row sets. After $T = O(m^2 / \log m)$ queries, the analysis shows that a linear number of row sets remain high-dimensional with large normalized volume. Using Urysohn's inequality and averaging arguments, the authors identify a single direction $\theta$ in which the aggregate width of these remaining sets is large.
Separation of Minimizers: By selecting the extreme points of the row sets in the direction $\theta$ , the adversary constructs two distinct functions, $f_{W^+}$ and $f_{W^-}$ , that are indistinguishable to the algorithm (they produce identical transcripts). However, due to the "almost-uniform" barycentric structure of the projection (Lemma 8), the aggregate displacement of the rows forces the unique minimizers of these two functions to be separated by a constant distance. Consequently, any single output from the algorithm must be far from the true minimizer of at least one of the functions, resulting in an error of $\Omega(d^{-1/2})$ .

Key Contributions and Results

Near-Quadratic Lower Bound: The primary result (Theorem 1) establishes that for accuracy $\varepsilon = \Theta(d^{-1/2})$ , the deterministic exact-value complexity is $\tilde{\Omega}(d^2)$ . Specifically, there exist constants such that:
$c \frac{d^2}{\log(d+1)} \leq Q_{\text{val}}^{\text{det}}\left(d, \frac{\varepsilon_0}{\sqrt{d}}\right) \leq C d^2 \log^2(d+1)$
This closes the gap between the lower and upper bounds up to polylogarithmic factors, proving that exact values alone are significantly less informative than full first-order information (which is $\Theta(d)$ ).
Mixed-Integer Extension: Using a transfer theorem from Basu et al., the authors lift this result to mixed-integer convex optimization with $n$ binary and $d$ continuous variables. They prove that the complexity scales multiplicatively with the integer dimension:
$Q_{\text{MI,val}}^{\text{det}}(n, d, \varepsilon) = \tilde{\Theta}(2^n d^2)$
This holds even when queries are allowed at arbitrary fractional points in the product domain.
Formal Verification: The authors acknowledge extensive use of AI tools (GPT-5.6 Sol Pro) in developing the mathematical arguments. To ensure rigor, they provide a formal verification of the $\tilde{\Omega}(d^2)$ lower bound proof using the Lean programming language.

Significance and Claims
The paper claims to resolve a complexity gap dating back to 1996. Its significance lies in isolating the cost of lacking subgradient information in the noiseless, exact-real setting. The authors emphasize that this separation is not an artifact of finite precision or memory constraints but is intrinsic to the information provided by exact function values versus first-order oracles.

The work demonstrates that for nonsmooth convex optimization, the "value-only" model is fundamentally harder than the first-order model, requiring a polynomial (quadratic) number of queries in the dimension rather than a linear number. The proof technique, relying on a Cartesian-product uncertainty invariant and aggregate width arguments, is presented as a novel mechanism for establishing lower bounds in partial-information settings without assigning finite information content to exact real responses.

The authors remain modest regarding the remaining logarithmic factors between the lower and upper bounds and note that the current hard family relies on a specific depth ( $\Theta(d^{-1/2})$ ), leaving open the question of dimension-free accuracy bounds and the behavior under additional regularity assumptions like smoothness.

Technical Summary: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization

More like this