Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback
Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback
复制标题
DOI：
10.1609/aaai.v36i9.21280
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Junxiong Wang;D. Basu;Immanuel Trummer
中科院分区：
文献类型：
--
作者：
Junxiong Wang;D. Basu;Immanuel Trummer
在黑盒优化问题中，我们的目标是最大化一个未知的目标函数，其中该函数只能通过评估或模拟预言的反馈来访问。在现实生活中，这种预言机的反馈通常是嘈杂的，并且在一些未知的延迟之后可用，这可能取决于预言机的计算时间。此外，如果精确的评估是昂贵的，但粗略的近似是可用的，在一个较低的成本，反馈可以有多保真度。为了解决这个问题，我们提出了分层乐观树搜索（HOO）的通用扩展，称为ProCrastinated Tree Search（PCTS），它灵活地适应延迟和抗噪的Bandit算法。我们提供了一个通用的证明技术，以量化延迟，噪声和多保真度反馈下的PCTS的遗憾。具体来说，我们得到的PCTS启用延迟UCB 1（DUCB 1）和延迟UCB-V（DUCBV）算法的遗憾界限。对于给定的时域T，PCTS在期望时滞为O（log T）时保持了无时滞HOO的遗憾界，在期望时滞为O（T^（1-α））（α ∈（0，1]）时保持了T^（（1-α）/（d+2））.我们在多个合成函数和超参数整定问题上进行了实验验证，PCTS在具有不同噪声水平、延迟和保真度的反馈方面优于最先进的黑盒优化方法。
In black-box optimization problems, we aim to maximize an unknown objective function, where the function is only accessible through feedbacks of an evaluation or simulation oracle. In real-life, the feedbacks of such oracles are often noisy and available after some unknown delay that may depend on the computation time of the oracle. Additionally, if the exact evaluations are expensive but coarse approximations are available at a lower cost, the feedbacks can have multi-fidelity. In order to address this problem, we propose a generic extension of hierarchical optimistic tree search (HOO), called ProCrastinated Tree Search (PCTS), that flexibly accommodates a delay and noise-tolerant bandit algorithm. We provide a generic proof technique to quantify regret of PCTS under delayed, noisy, and multi-fidelity feedbacks. Specifically, we derive regret bounds of PCTS enabled with delayed-UCB1 (DUCB1) and delayed-UCB-V (DUCBV) algorithms. Given a horizon T, PCTS retains the regret bound of non-delayed HOO for expected delay of O(log T), and worsens by T^((1-α)/(d+2)) for expected delays of O(T^(1-α)) for α ∈ (0,1]. We experimentally validate on multiple synthetic functions and hyperparameter tuning problems that PCTS outperforms the state-of-the-art black-box optimization methods for feedbacks with different noise levels, delays, and fidelity.