Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization

Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2609.18728Sep 16, 2026math.OCscore 0

We study deterministic adaptive optimization of globally $β$-smooth, $μ$-strongly convex functions using exact scalar function values. Queries and outputs lie in $B_2^d(R)$, and the minimizer lies in $B_2^d(R/2)$. Set $κ=β/μ$, $Q=βR^2/ε$, and $D_d=(d/\log(ed))^{1/3}$. For sufficiently large $d$ and $0 0$ are universal constants and $\log_+(t)=\max\{0,\log t\}$. The lower bound uses an exactly shielded smooth chain and batched delayed rotations; the upper bound combines finite differences, acceleration, and restart. When $\min\{Q,κ\}\le D_d^2$, these bounds match up to constants in the…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.18728
curl -X POST /api/v1/records/arxiv/2609.18728/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.18728/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'