Id: arxiv/2607.16558 Url: https://arxiv.org/abs/2607.16558 Tags: math.OC Score: 0 Title: Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization Domain: math.OC Source: arxiv Authors: Haihan Zhang, Chenheng Zhang, Zhiquan Qi, Zhouchen Lin Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-18 Page: https://delphi.science/r/arxiv/2607.16558 Whether exact scalar feedback intrinsically incurs the additional dimension $d$ paid by known zeroth-order methods remains open even for Lipschitz convex optimization. For a universal Lipschitz scale, the value only bound $O(d^2\log(d+1)\log(1/ε))$ and two-point bound $O(dε^{-2})$ yield the upper bound $\widetilde O\left(d\min\{d,ε^{-2}\}\right)$. By contrast, prior lower bounds for arbitrary randomized algorithms give only $Ω(\min\{d,ε^{-2}\})$, leaving a factor $d$ unexplained. We close this gap, up to logarithmic factors, for arbitrary adaptive randomized algorithms minimizing a convex…