Information-Theoretic Upper Bounds for Deterministic Noise in Zeroth-Order Convex Optimization

Abstract

We study zeroth-order convex optimization on Euclidean balls with function values corrupted by a fixed, uniformly bounded deterministic perturbation. For a query budget $T$, the maximum admissible level of noise (MALN) is the supremum of noise levels for which an $\eps$-accurate solution can be found with probability $1-\beta$. We construct an explicit hard family: the support function of a spherical belt combined with an affine branch along a hidden random direction. It yields finite-budget upper bounds on the MALN for Lipschitz, strongly convex, uniformly convex, smooth, Hölder, and smooth strongly convex classes. For Lipschitz objectives the bound has order $\eps^2\sqrt\ell/(\sqrt nMR)+\eps\ell/n$, where $\ell =\log (2(T+1)/(1-\beta ))$ and $n-1\ge 32\ell$; this is the scale of Li and Risteski with explicit logarithmic factors. A tangential-gradient estimate for the Moreau envelope yields the smooth scale $\eps^{3/2}/(\sqrt n\sqrt L\,R)$ and, for $L-\mu \ge 5\mu$, the smooth strongly convex scale $\eps\sqrt{μ/((L-μ)n)}$. These bounds are tight: on explicit parameter ranges and subclasses, polynomial-query two-point methods tolerate noise of the order of the terms of order $n^{-1/2}$, so that the MALN is determined up to $O(\sqrt{\ell })$ and absolute constants whenever these terms dominate. At $L=\mu$, simplex interpolation with $n+1$ queries tolerates noise $R\sqrt{2μ\eps/n}$, which is optimal up to $O(\sqrt{\ell })$ for $\eps\leμR^2/3$, while with at most $n$ exact queries no randomized algorithm guarantees success probability greater than $1/2$ uniformly over the class. We also quantify noise tolerance near this endpoint and illustrate the hiding mechanism and the breakdown of a two-point method numerically.

arXiv comment19 pages