论文标题
带有嘈杂观测的样品有效的基于图的优化
Sample Efficient Graph-Based Optimization with Noisy Observations
论文作者
论文摘要
我们研究了在嘈杂观测值下定义的“爬山友好”功能的样本复杂性。我们定义了一个凸度的概念，我们表明，在少量的查询之后，最佳武器识别的变体可以找到一个近乎最佳的解决方案，而这些解决方案与图形的大小无关。对于具有局部最小值并且几乎是凸的函数，我们在嘈杂的观测值下显示了经典模拟退火的样品复杂性。我们通过重新启动显示了贪婪算法的有效性，并在基于图的最近的邻居分类以及Web文档重新排列应用程序的问题上进行了模拟退火。
We study sample complexity of optimizing "hill-climbing friendly" functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of best-arm identification can find a near-optimal solution after a small number of queries that is independent of the size of the graph. For functions that have local minima and are nearly convex, we show a sample complexity for the classical simulated annealing under noisy observations. We show effectiveness of the greedy algorithm with restarts and the simulated annealing on problems of graph-based nearest neighbor classification as well as a web document re-ranking application.
