Sample Efficient Graph-Based Optimization with Noisy Observations
This addresses sample efficiency in graph-based optimization for applications like classification and ranking, but it appears incremental as it builds on existing methods like best-arm identification and simulated annealing.
The paper tackles the problem of optimizing functions on graphs with noisy observations, showing that a variant of best-arm identification achieves near-optimal solutions with a sample complexity independent of graph size, and simulated annealing works for nearly convex functions with local minima, demonstrating effectiveness in graph-based nearest neighbor classification and web document re-ranking.
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.