Akhavan, A; Chzhen, E; Pontil, M; Tsybakov, AB; (2022) A gradient estimator via L1-randomization for online zero-order optimization with two point feedback. In: Advances in Neural Information Processing Systems. (pp. pp. 2-12). Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022): 36th Conference on Neural Information Processing Systems (NeurIPS 2022).

Preview

PDF 9231_a_gradient_estimator_via_l1_ra.pdf - Published Version Download (1MB) | Preview

Abstract

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 ℓ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. [14] and Shamir [33] for non-adaptive algorithms. Our analysis is based on deriving a new weighted Poincaré type inequality for the uniform measure on the ℓ1-sphere with explicit constants, which may be of independent interest.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item