Sample Efficient Graph-Based Optimization with Noisy Observations
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.
Code (1)
Tasks
Re-RankingSimilar Papers 제목 키워드 기반
On the Impact of Sample Size in Reconstructing Graph Signals
Reconstructing a signal on a graph from observations on a subset of the vertices is a fundamental problem in the field of graph signal processing. It is often assumed that adding additional observations to an observation…
Learning Graphical Games from Behavioral Data: Sufficient and Necessary Conditions
In this paper we obtain sufficient and necessary conditions on the number of samples required for exact recovery of the pure-strategy Nash equilibria (PSNE) set of a graphical game from noisy observations of joint action…
Elicitation-Augmented Bayesian Optimization
Human-in-the-loop Bayesian optimization (HITL BO) methods utilize human expertise to improve the sample-efficiency of BO. Most HITL BO methods assume that a domain expert can quantify their knowledge, for instance by pin…
A Corrected Expected Improvement Acquisition Function Under Noisy Observations
Sequential maximization of expected improvement (EI) is one of the most widely used policies in Bayesian optimization because of its simplicity and ability to handle noisy observations. In particular, the improvement fun…
Bayesian OptimizationModel CompressionOn the Impact of Sample Size in Reconstructing Noisy Graph Signals: A Theoretical Characterisation
Reconstructing a signal on a graph from noisy observations of a subset of the vertices is a fundamental problem in the field of graph signal processing. This paper investigates how sample size affects reconstruction erro…