Sample Efficient Graph-Based Optimization with Noisy Observations

@InProceedings{pmlr-v89-nguyen19b,
  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 = 	 {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics},
  pages = 	 {3333--3341},
  year = 	 {2019},
  editor = 	 {Chaudhuri, Kamalika and Sugiyama, Masashi},
  volume = 	 {89},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {16--18 Apr},
  publisher =    {PMLR},
  pdf = 	 {http://proceedings.mlr.press/v89/nguyen19b/nguyen19b.pdf},
  url = 	 {https://proceedings.mlr.press/v89/nguyen19b.html},
  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.}
}