Sample Efficient GraphBased Optimization with Noisy Observations
[edit]
Proceedings of Machine Learning Research, PMLR 89:33333341, 2019.
Abstract
We study sample complexity of optimizing “hillclimbing friendly” functions defined on a graph under noisy observations. We define a notion of convexity, and we show that a variant of bestarm identification can find a nearoptimal 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 graphbased nearest neighbor classification as well as a web advertising application.
Related Material


