A Unified Framework of Constrained Robust Submodular Optimization with Applications

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 su...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-03
Main Author: Iyer, Rishabh
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Lower bounds
Machine learning
Maximization
Optimization
Robustness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422