用贝叶斯优化解决低差异子集选择难题，提升采样效率
A Bayesian Approach to Low-Discrepancy Subset Selection
- 基于深度嵌入核的贝叶斯优化框架
- 首次证明核差异下的子集选择问题为NP-hard
- 适用于多种设计准则，适合高维采样场景
低差异设计在拟蒙特卡洛方法中起核心作用，并在机器学习、机器人学和计算机图形学等领域日益重要。近年来，一种称为子集选择的方法受到广泛关注：从大规模样本中选取小规模低差异子集，以最小化基于差异度量的目标。此类问题已被证明是NP-hard。本文首次证明，针对核差异的子集选择问题同样属于NP-hard。鉴于其计算复杂性，我们提出一种基于深度嵌入核的贝叶斯优化算法来求解该问题。实验表明，该方法能有效降低各类差异度量，且框架可广泛应用于多种设计准则。
原文摘要 · Abstract (English)
Low-discrepancy designs play a central role in quasi-Monte Carlo methods and are increasingly influential in other domains such as machine learning, robotics and computer graphics, to name a few. In recent years, one such low-discrepancy construction method called subset selection has received a lot of attention. Given a large population, one optimally selects a small low-discrepancy subset with respect to a discrepancy-based objective. Versions of this problem are known to be NP-hard. In this text, we establish, for the first time, that the subset selection problem with respect to kernel discrepancies is also NP-hard. Motivated by this intractability, we propose a Bayesian Optimization procedure for the subset selection problem utilizing the recent notion of deep embedding kernels. We demonstrate the performance of the BO algorithm to minimize discrepancy measures and note that the framework is broadly applicable any design criteria.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。