Breakthrough Tracker record
A near-quadratic lower bound in derivative-free convex optimization
The paper proves an Ω(d²/log(d+1)) lower bound for a specified deterministic exact-value-oracle problem at accuracy on the order of d⁻¹ᐟ². This nearly matches the known upper bound up to polylogarithmic factors.
← Back to the filtered Breakthrough Tracker
- Stable ID
math-derivative-free-convex-lower-bound-2026- Revision
math-derivative-free-convex-lower-bound-2026.v1- Field
- Mathematics · Convex optimization
- Evidence
- Tier 1 · Peer reviewed: No
- Record state
- Current · Lean-verified claimed theorem; specialist reception developing
- Last checked
AI role
Kerger reports that GPT-5.6 Sol Pro generated the main argument, which he checked and formalized in Lean.
Record details
- Problem or result
- Oracle-complexity gap for deterministic derivative-free convex optimization
- Authors
- Phillip Kerger
- Institutions
- Affiliation not stated on the inspected arXiv record
- Result date
- Preprint submitted July 14, 2026
Why it matters
It sharply narrows a complexity gap dating to the 1990s and limits what derivative-free methods can achieve in the stated oracle model.
Limits
The theorem concerns a specific deterministic oracle model and accuracy regime. Lean verification supports deductive correctness, but independent specialists still need to assess statement correspondence, novelty and the surrounding literature.
Sources
- Primary: Phillip Kerger, Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization
- Primary: Author disclosure and discussion
- Independent: Cautious secondary explainer
Correction and revision history
- Added on 2026-07-22 as a formally checked but very recent preprint whose novelty and scope still need specialist review.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.