论文标题
通过L1随机化的梯度估计器，用于在线零级优化，并具有两个点反馈
A gradient estimator via L1-randomization for online zero-order optimization with two point feedback
论文作者
论文摘要
这项工作研究了凸和Lipschitz功能的在线零级优化。我们根据两项函数评估和$ \ ell_1 $ -sphere的随机化提出了一个新颖的梯度估计器。考虑到可行的集合和Lipschitz假设的不同几何形状，我们分析了在线双重平均算法的算法，代替了通常的梯度。我们考虑了零级甲骨文噪声的两种假设：取消噪声和对抗性噪声。我们提供任何时间和完全数据驱动的算法，它适应问题的所有参数。在文献中先前研究过的噪声的情况下，我们的保证可以比Duchi等人获得的最新界限可比性或更好。 （2015）和Shamir（2017）非自适应算法。我们的分析是基于在$ \ ell_1 $ -sphere上带有明确常数的均匀度量的新加权庞加莱型不平等，这可能具有独立的兴趣。
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é type inequality for the uniform measure on the $\ell_1$-sphere with explicit constants, which may be of independent interest.
