Sample Efficient Graph-Based Optimization with Noisy Observations

Thanh Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori, Anup Rao, Branislav Kveton
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3333-3341, 2019.

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 this Paper

BibTeX
@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.} }
Endnote
%0 Conference Paper %T Sample Efficient Graph-Based Optimization with Noisy Observations %A Thanh Tan Nguyen %A Ali Shameli %A Yasin Abbasi-Yadkori %A Anup Rao %A Branislav Kveton %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-nguyen19b %I PMLR %P 3333--3341 %U https://proceedings.mlr.press/v89/nguyen19b.html %V 89 %X 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.
APA
Nguyen, T.T., Shameli, A., Abbasi-Yadkori, Y., Rao, A. & Kveton, B.. (2019). Sample Efficient Graph-Based Optimization with Noisy Observations. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3333-3341 Available from https://proceedings.mlr.press/v89/nguyen19b.html.

Related Material