2026/07/18 by Haihan Zhang, Chenheng Zhang, Zhiquan Qi +1
Mathematics · #math.OC
arxiv created 2026/07/30 · arxiv updated 2026/07/31
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(d2log(d+1)log(1/ε)) and two-point bound O(dε-2) yield the upper bound \widetilde O(dmin\d,ε-2\). 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 objective with a universal Lipschitz scale over the d-dimensional Euclidean unit ball, where each query returns only the exact scalar value. Let Tε denote the minimum number of queries required to return an ε-suboptimal point with probability at least 1/2, uniformly over the function class. We prove that Tε≥ c \fracdmin\d,ε-2\log (min\d,ε-2\), for d≥ d0 and 0<ε≤ε0, where c,ε0>0 and d0∈\mathbb N are universal constants. This gives Ω((d)/(ε2log(1/ε))) in the low-accuracy regime ε≥ d-1/2 and Ω((d2)/(log d)) in the high-accuracy regime ε≤ d-1/2 with the latter independent of ε. These bounds match the corresponding upper bound up to logarithmic factors. To our knowledge, this is the first near-optimal lower bound for arbitrary adaptive randomized algorithms throughout both accuracy regimes of exact value Lipschitz convex optimization. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.