{"ID":22952684,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18728","arxiv_id":"2609.18728","title":"Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization","abstract":"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\u003cε\\le c_εβR^2$, the minimax value complexity $N_ε$ satisfies \\[ \\begin{aligned} N_ε\u0026\\ge c d\\min\\{\\sqrt Q,\\sqrtκ,D_d\\},\\\\ N_ε\u0026\\le C d\\min\\left\\{ \\sqrt Q,\\sqrtκ[1+\\log_+(Q/κ)] \\right\\}, \\end{aligned} \\] where $c,C,c_ε\u003e0$ 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 accuracy-dominated regime $Q\\leκ$ and at constant relative accuracy $ε=Θ(μR^2)$. For arbitrarily higher accuracy in the range $κ\\le D_d^2$, the bounds differ by at most $1+\\log(μR^2/ε)$; the optimal accuracy dependence remains unresolved in general.","short_abstract":"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\u003cε\\le c_εβR^2$, th...","url_abs":"https://arxiv.org/abs/2609.18728","url_pdf":"https://arxiv.org/pdf/2609.18728v1","authors":"[\"Wendao Wu\",\"Haihan Zhang\",\"Chenheng Zhang\",\"Yanyi Li\",\"Chunyuan Zheng\",\"Cong Fang\",\"Haoxuan Li\",\"Zhouchen Lin\"]","published":"2026-09-16T14:27:53Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}