论文标题
在标准和强大的高斯工艺强盗优化的下限
On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
论文作者
论文摘要
在本文中，我们考虑算法无关的下限，即具有有界规范的功能的黑盒优化的问题是一些繁殖的内核希尔伯特空间（RKHS），可以将其视为非基斯加斯的高斯过程匪徒问题。在标准的噪声设置中，我们提供了一种新颖的证明技术，用于以遗憾得出下界，并提供包括简单性，多功能性和改善对误差概率的依赖性的好处。在一个健壮的环境中，每个采样点可能会受到适当约束的对手的扰动，我们为确定性策略提供了一种新颖的下限，证明了累积性遗憾对腐败水平和时间范围的不可避免的联合依赖性，而与现有的下限相反，与仅表征个人依赖性的现有下限相反。此外，在一个独特的鲁棒环境中，最终点受到对手的扰动，我们加强了一个现有的下限，仅通过允许超过$ \ frac {2} {3} $的任意成功概率来使目标成功概率非常接近一个。
In this paper, we consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm is some Reproducing Kernel Hilbert Space (RKHS), which can be viewed as a non-Bayesian Gaussian process bandit problem. In the standard noisy setting, we provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability. In a robust setting in which every sampled point may be perturbed by a suitably-constrained adversary, we provide a novel lower bound for deterministic strategies, demonstrating an inevitable joint dependence of the cumulative regret on the corruption level and the time horizon, in contrast with existing lower bounds that only characterize the individual dependencies. Furthermore, in a distinct robust setting in which the final point is perturbed by an adversary, we strengthen an existing lower bound that only holds for target success probabilities very close to one, by allowing for arbitrary success probabilities above $\frac{2}{3}$.
