Sample Efficient Graph-Based Optimization with Noisy Observations

Thanh Tan Nguyen, Ali Shameli, Yasin Abbasi-Yadkori, Anup Rao, Branislav Kveton
; Proceedings of Machine Learning Research, 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 Machine Learning Research}, pages = {3333--3341}, year = {2019}, editor = {Kamalika Chaudhuri and Masashi Sugiyama}, volume = {89}, series = {Proceedings of Machine Learning Research}, address = {}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/nguyen19b/nguyen19b.pdf}, url = {http://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 Machine Learning Research %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-nguyen19b %I PMLR %J Proceedings of Machine Learning Research %P 3333--3341 %U http://proceedings.mlr.press %V 89 %W PMLR %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 Machine Learning Research, in PMLR 89:3333-3341

Related Material