  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 document re-ranking application.
