  This work studies online zero-order optimization of convex and Lipschitz
functions. We present a novel gradient estimator based on two function
evaluations and randomization on the $\ell_1$-sphere. Considering different
geometries of feasible sets and Lipschitz assumptions we analyse online dual
averaging 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 to all parameters of the problem. In
the case of canceling noise that was previously studied in the literature, our
guarantees are either comparable or better than state-of-the-art bounds
obtained by Duchi et al. (2015) and Shamir (2017) for non-adaptive algorithms.
Our analysis is based on deriving a new weighted Poincar\'e type inequality for
the uniform measure on the $\ell_1$-sphere with explicit constants, which may
be of independent interest.
