Lower Bounds For Gradient-Free Convex Optimization And Convex-Concave Saddle-Point Problems
We study the query complexity of optimization with exact scalar-value information. For globally $L$-smooth convex functions on $\mathbb R^d$ with a minimizer in a Euclidean ball of radius $R$, we prove the lower bound $Ω(d\min\{d,\sqrt{LR^2/\varepsilon}\})$ for adaptive randomized algorithms in the stated accuracy range. Queries are unrestricted, and the bound contains no logarithmic factor. It holds for quadratics and matches the minimum of two elementary upper bounds on that class. Prescribed strong convexity introduces the additional cap $\sqrt{L/μ}$. The proof compares the mean of a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.00345
curl -X POST /api/v1/records/arxiv/2610.00345/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.00345/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'