Reproduce “Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Phillip Kerger
The research establishes a near-quadratic lower bound of "~","Θ","(","d","^2",")" for the deterministic query complexity of minimizing convex, 1-Lipschitz functions using only exact function values, closing a decades-old theoretical gap in derivative-free optimization. This explicitly quantifies a polynomial increase in required function evaluations compared to methods utilizing subgradient information.
Key insights
- Exact function values provide substantially less information than subgradients, leading to a polynomial separation in query complexity.
- A sophisticated adversarial argument can precisely quantify the informational limitations of value-only oracles in high dimensions.
- The complexity of mixed-integer convex optimization with value-only queries scales multiplicatively with the number of discrete variables (2^n) and the continuous component (~Θ(d^2)).
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.