A gradient estimator via L1-randomization for online zero-order optimization with two point feedback. (arXiv:2205.13910v1 [math.ST])

This work studies online zero-order optimization of convex and Lipschitz
functions. We present a novel gradient estimator based on two function
evaluation and randomization on the $\ell_1$-sphere. Considering different
geometries of feasible sets and Lipschitz assumptions we analyse online mirror
descent algorithm with our estimator in place of the usual gradient. We
consider two types of assumptions on the noise of the zero-order oracle:
canceling noise and adversarial noise. We provide an anytime and completely
data-driven algorithm, which is adaptive …

arxiv feedback gradient math optimization randomization