  Robust Optimization is becoming increasingly important in machine learning
applications. This paper studies the problem of robust submodular minimization
subject to combinatorial constraints. Constrained Submodular Minimization
arises in several applications such as co-operative cuts in image segmentation,
co-operative matchings in image correspondence, etc. Many of these models are
defined over clusterings of data points (for example pixels in images), and it
is important for these models to be robust to perturbations and uncertainty in
the data. While several existing papers have studied robust submodular
maximization, ours is the first work to study the minimization version under a
broad range of combinatorial constraints including cardinality, knapsack,
matroid as well as graph-based constraints such as cuts, paths, matchings, and
trees. In each case, we provide scalable approximation algorithms and also
study hardness bounds. Finally, we empirically demonstrate the utility of our
algorithms on synthetic and real-world datasets.
