论文标题
利用无衍生化优化和连续匪徒中的高阶平滑度
Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
论文作者
论文摘要
我们研究了强凸功能的零级优化问题。目的是通过在测量噪声下对其值进行连续探索来找到该函数的最小化器。我们研究了该功能的高阶平滑度特性对优化误差和累积遗憾的影响。为了解决这个问题，我们考虑了投影梯度下降算法的随机近似。通过涉及两个函数评估和平滑内核的随机过程来估计梯度。我们在约束和不受约束的设置中得出了该算法的上限，并证明了任何顺序搜索方法的最小下限。我们的结果表明，零级算法在样本复杂性和问题参数方面几乎是最佳的。基于该算法，我们还提出了实现几乎尖锐甲骨文行为的功能最小值的估计值。我们将结果与最新的结果进行比较，突出了许多关键改进。
We study the problem of zero-order optimization of a strongly convex function. The goal is to find the minimizer of the function by a sequential exploration of its values, under measurement noise. We study the impact of higher order smoothness properties of the function on the optimization error and on the cumulative regret. To solve this problem we consider a randomized approximation of the projected gradient descent algorithm. The gradient is estimated by a randomized procedure involving two function evaluations and a smoothing kernel. We derive upper bounds for this algorithm both in the constrained and unconstrained settings and prove minimax lower bounds for any sequential search method. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters. Based on this algorithm, we also propose an estimator of the minimum value of the function achieving almost sharp oracle behavior. We compare our results with the state-of-the-art, highlighting a number of key improvements.
