Robust Adaptive Submodular Maximization
share
Most of existing studies on adaptive submodular optimization focus on the average-case, i.e., their objective is to find a policy that maximizes the expected utility over a known distribution of realizations. However, a policy that has a good average-case performance may have very poor performance under the worst-case realization. In this study, we propose to study two variants of adaptive submodular optimization problems, namely, worst-case adaptive submodular maximization and robust submodular maximization. The first problem aims to find a policy that maximizes the worst-case utility and the latter one aims to find a policy, if any, that achieves both near optimal average-case utility and worst-case utility simultaneously. We introduce a new class of stochastic functions, called worst-case submodular function. For the worst-case adaptive submodular maximization problem subject to a p-system constraint, we develop an adaptive worst-case greedy policy that achieves a 1/p+1 approximation ratio against the optimal worst-case utility if the utility function is worst-case submodular. For the robust adaptive submodular maximization problem subject to a cardinality constraint, if the utility function is both worst-case submodular and adaptive submodular, we develop a hybrid adaptive policy that achieves an approximation close to 1-e^-1/2 under both worst case setting and average case setting simultaneously. We also describe several applications of our theoretical results, including pool-base active learning, stochastic submodular set cover and adaptive viral marketing.
READ FULL TEXT