Quantile Search with Time-Varying Search Parameter

摘要

We consider the problem of active learning in the context of spatial sampling, where the sampling cost is a function of both the number of samples taken and the distance traveled during the sampling procedure. We present Uniform-to-Binary (UTB) search, a novel algorithm in this setting. UTB search extends the Quantile Search (QS) algorithm such that the tuning parameter m is allowed to vary throughout the search procedure. We analyze the algorithm in terms of both sample complexity and distance traveled. Empirical results show that our proposed method outperforms QS with fixed m in all cases considered.