Optimization of convex functions under stochastic zeroth-order feedback has
been a major and challenging question in online learning. In this work, we
consider the problem of optimizing second-order smooth and strongly convex
functions where the algorithm is only accessible to noisy evaluations of the
objective function it queries. We provide the first tight characterization for
the rate of the minimax simple regret by developing matching upper and lower
bounds. We propose an algorithm that features a combination of a bootstrapping
stage and a mirror-descent stage. Our main technical innovation consists of a
sharp characterization for the spherical-sampling gradient estimator under
higher-order smoothness conditions, which allows the algorithm to optimally
balance the bias-variance tradeoff, and a new iterative method for the
bootstrapping stage, which maintains the performance for unbounded Hessian.

在在线学习中，优化随机零阶反馈下的凸函数一直是一个主要而具有挑战性的问题。本文考虑了仅能对目标函数进行噪声评估的情况下，对二阶平滑和强凸函数进行优化的问题；通过提出匹配的上下界，第一次对最小化最大简单后悔的速率进行了紧密的刻画。我们提出了一种算法，结合了启动阶段和镜像下降阶段。我们的主要技术创新包括对高阶平滑性条件下球形采样梯度估计器的尖锐刻画，从而使算法能够在偏差 - 方差权衡方面达到最优平衡，以及一种用于启动阶段的新的迭代方法，它能够保持无界 Hessian 的性能。