Jun, 2020
带有噪声观测的高效图优化
Sample Efficient Graph-Based Optimization with Noisy Observations
TL;DR本研究主要研究在嘈杂观测下，在图上定义“爬山友好型”函数的样本复杂度。作者提出了一个凸性的概念，利用最佳臂识别的变种，可以在少量查询后找到近似最优解。对于具有局部极值并且接近凸性的函数，作者证明了在噪声观测下经典模拟退火的样本复杂度。作者在图基邻近分类和文档重新排序应用问题上，展示了贪心算法和带重启的模拟退火的有效性。