Sample Efficient Graph-Based Optimization with Noisy Observations
Abstract
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 advertising application.
Cite
Text
Nguyen et al. "Sample Efficient Graph-Based Optimization with Noisy Observations." Artificial Intelligence and Statistics, 2019.Markdown
[Nguyen et al. "Sample Efficient Graph-Based Optimization with Noisy Observations." Artificial Intelligence and Statistics, 2019.](https://mlanthology.org/aistats/2019/nguyen2019aistats-sample/)BibTeX
@inproceedings{nguyen2019aistats-sample,
title = {{Sample Efficient Graph-Based Optimization with Noisy Observations}},
author = {Nguyen, Thanh Tan and Shameli, Ali and Abbasi-Yadkori, Yasin and Rao, Anup and Kveton, Branislav},
booktitle = {Artificial Intelligence and Statistics},
year = {2019},
pages = {3333-3341},
volume = {89},
url = {https://mlanthology.org/aistats/2019/nguyen2019aistats-sample/}
}