How many exact function-value queries are necessary to minimize a convex Lipschitz function, at a specified dimension and accuracy?
1 record · How we rate progress
Kerger reports Ω(d²/log(d+1)) exact-function-value queries at accuracy Θ(d^−1/2) for deterministic convex Lipschitz minimization over a d-dimensional ball.
Original report: 2026-07-14How many exact function-value queries are necessary to minimize a convex Lipschitz function, at a specified dimension and accuracy?
A precise target for comparing mathematical claims, their baselines, and the documented contribution of AI.
A sourced theorem, construction, algorithm, bound, or substantive formalization with its assumptions and AI role stated.
Background review: 2026-10-11. Selected sources:
Publication dates and editorial changes.
AI-assisted near-quadratic lower bound for exact-value optimization
Allow optional Google Analytics to help improve AIProofWatch? Privacy details.
