标题： 嵌入式老虎机用于大规模黑箱优化 显示英文标题

标题： Embedded Bandits for Large-Scale Black-Box Optimization

摘要： 随机嵌入已被成功应用于具有低有效维度的大规模黑盒优化问题。 本文提出了EmbeddedHunter算法，该算法在分层随机赌徒问题设置中结合了该技术，遵循面对不确定性时的乐观原则，并摆脱了随机嵌入传统上被应用的多运行框架，类似于随机黑盒优化求解器。 我们的提议是基于在将低维点随机投影到Lipschitz连续问题的决策空间时目标值的有界均值变化。 本质上，EmbeddedHunter算法基于从低维空间中采样的点的有限数量的随机嵌入，在低维——等于问题的有效维度——搜索空间上乐观地扩展一个划分树。 与多运行随机嵌入算法的概率理论保证不同，所提出的算法的有限时间分析给出了遗憾作为算法迭代次数的函数的理论上限。 此外，进行了数值实验以验证其性能。 结果表明，在内在维度较低的情况下，它在大规模问题上明显优于最近提出的随机嵌入方法。 显示英文摘要

摘要： Random embedding has been applied with empirical success to large-scale black-box optimization problems with low effective dimensions. This paper proposes the EmbeddedHunter algorithm, which incorporates the technique in a hierarchical stochastic bandit setting, following the optimism in the face of uncertainty principle and breaking away from the multiple-run framework in which random embedding has been conventionally applied similar to stochastic black-box optimization solvers. Our proposition is motivated by the bounded mean variation in the objective value for a low-dimensional point projected randomly into the decision space of Lipschitz-continuous problems. In essence, the EmbeddedHunter algorithm expands optimistically a partitioning tree over a low-dimensional---equal to the effective dimension of the problem---search space based on a bounded number of random embeddings of sampled points from the low-dimensional space. In contrast to the probabilistic theoretical guarantees of multiple-run random-embedding algorithms, the finite-time analysis of the proposed algorithm presents a theoretical upper bound on the regret as a function of the algorithm's number of iterations. Furthermore, numerical experiments were conducted to validate its performance. The results show a clear performance gain over recently proposed random embedding methods for large-scale problems, provided the intrinsic dimensionality is low.