Robust Submodular Minimization with Applications to Cooperative Modeling
This work addresses robustness in cooperative modeling for applications like image segmentation and correspondence, offering incremental algorithmic advancements.
The paper tackles robust submodular minimization under combinatorial constraints, providing scalable approximation algorithms and hardness bounds for various constraints like cardinality and graph-based ones, with empirical validation on synthetic and real-world datasets.
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.