CUED Publications database

Adaptive maximization of pointwise submodular functions with budget constraint

Cuong, NV and Xu, H (2016) Adaptive maximization of pointwise submodular functions with budget constraint. In: UNSPECIFIED pp. 1252-1260..

Full text not available from this repository.

Abstract

© 2016 NIPS Foundation - All Rights Reserved. We study the worst-case adaptive optimization problem with budget constraint that is useful for modeling various practical applications in artificial intelligence and machine learning. We investigate the near-optimality of greedy algorithms for this problem with both modular and non-modular cost functions. In both cases, we prove that two simple greedy algorithms are not near-optimal but the best between them is near-optimal if the utility function satisfies pointwise submodularity and pointwise cost-sensitive submodularity respectively. This implies a combined algorithm that is near-optimal with respect to the optimal algorithm that uses half of the budget. We discuss applications of our theoretical results and also report experiments comparing the greedy algorithms on the active learning problem.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Subjects: UNSPECIFIED
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 17 Jul 2017 19:26
Last Modified: 05 Oct 2017 02:06
DOI: