{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-18","reactions":{}}