A Unified Framework of Constrained Robust Submodular Optimization with Applications
This work addresses robust optimization challenges in machine learning applications such as data subset selection and image processing, offering a unified framework that extends beyond previous maximization-focused approaches, though it is incremental in nature.
The paper tackles robust submodular optimization under various combinatorial constraints, providing scalable approximation algorithms and hardness bounds for both minimization and maximization problems, with empirical validation on synthetic and real-world datasets like image correspondence and speech recognition.
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.