A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

arXiv:2609.30215 · cs.DS, cs.LG, math.FA, math.OC · Submitted 2026-09-24 · Read on arXiv

cs.DS, cs.LG, math.FA, math.OC

Submitted: 2026-09-24

Updated: 2026-09-24

Terminology

• Accuracy — 6× in this paper · explained in 1 episode
• Query Complexity — 4× in this paper · explained in 2 episodes
• Ambient Dimension — 1× in this paper · explained in 1 episode
• Trace — 1× in this paper · explained in 2 episodes

Sources

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

Related papers

• Cascaded Learned Bloom Filter for Optimizing Model-Filter Size Balance and Fast Rejection
• Edge-Private Matching Kernels Through Local Decoding
• Local Node Differential Privacy
• Cheaper by the Batch: Shared Traversal for Genotype Graph Editing
• Scalable Algorithms for Approximate DNF Model Counting
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions