  Robust optimization is becoming increasingly important in machine learning
applications. In this paper, we study a unified framework of robust submodular
optimization. We study this problem both from a minimization and maximization
perspective (previous work has only focused on variants of robust submodular
maximization). We do this under a broad range of combinatorial constraints
including cardinality, knapsack, matroid as well as graph-based constraints
such as cuts, paths, matchings and trees. Furthermore, we also study robust
submodular minimization and maximization under multiple submodular upper and
lower bound constraints. We show that all these problems are motivated by
important machine learning applications including robust data subset selection,
robust co-operative cuts and robust co-operative matchings. In each case, we
provide scalable approximation algorithms and also study hardness bounds.
Finally, we empirically demonstrate the utility of our algorithms on synthetic
data, and real-world applications of robust cooperative matchings for image
correspondence, robust data subset selection for speech recognition, and image
collection summarization with multiple queries.
