Adaptive Maximization of Pointwise Submodular Functions With Budget Constraint
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.
The paper addresses the problems of adaptive optimization with budget constraint. While previous studies address this problem for the average case, this study focuses on the worst case. In contrast to previous works on adaptive optimization with budget constraint, the authors of this paper consider not only modular cost functions but also general, possibly non-modular, cost functions. The authors investigate the near-optimality of two greedy policies for the worst-caseadaptive optimization problem with budget constraint (a policy is near-optimal if its worst-case utility is within a constant factor of the optimal worst-case utility). The authors prove that in the general case, these two policies cannot achieve near-optimality with non-uniform modular costs, but the best between these two greedy policies always achieves near-optimality. Following that, the main result of the paper is derived: The two greedy policies into one greedy policy that is near-optimal with respect to the optimal worst-case policy that uses half of the budget.  In addition, the authors propose a novel class of utility functions satisfying a property that is a generalization of cost-sensitive submodularity to the adaptive setting. For this new class of utilities, the authors prove similar near-optimality results for the greedy policies as in the case of modular costs.  The proposed algorithm is compared experimentally to other algorithms, and results show that even though it does not yield the best result in almost any case (which is not surprising and supported by the theoretical results in the paper), it is a robust choice for an algorithm that achieves the second best results in all cases.  
Definitions and mathematical proofs are concise and easy to understand. Related work is covered in a sufficient manner. The paper exhibits a novel mathematical analysis relevant to adaptive optimization with budget constraint, a problem with many practical implications. The setting in which the analysis is given is wider compared to previous papers on the subject. Two greedy algorithms are analyzed, and despite negative results regarding their near-optimality, results (proofs) show that a combination of the two has interesting properties and can be sound and useful in some cases. In addition, a subset of utility functions under which strong positive results can be proved is correctly identified. The proposed algorithm is derived naturally from the theoretical results, and experiment results support the theoretical results. On the down side, the proposed algorithm does not perform better than other algorithms (but also never performs catastrophically bad), and was not examined in many different experiment settings.