Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

By Rishabh K. Iyer, J. Bilmes. 2013

278 citations recorded by the source corpus.

We investigate two new optimization problems — minimizing a submodular function subject to a submodular lower bound constraint (submodular cover) and maximizing a submodular function subject to a submodular upper bound constraint (submodular knapsack). We are motivated by a number of real-world applications in machine learning including sensor placement and data subset selection, which require maximizing a certain submodular function (like coverage or diversity) while simultaneously minimizing another (like cooperative cost). These problems are often posed as minimizing the difference between submodular functions [9, 25] which is in the worst case inapproximable. We show, however, that by phrasing these problems as constrained optimization, which is more natural for many applications, we achieve a number of bounded approximation guarantees. We also show that both these problems are closely related and an approximation algorithm solving one can be used to obtain an approximation guarantee for the other. We provide hardness results for both problems thus showing that our approximation factors are tight up to log-factors. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
Submodular Optimization-based Diverse Paraphrasing and its Effectiveness in Data Augmentation (2019, background): “Submodular functions have been applied to a wide variety of problems in machine learning (Iyer and Bilmes, 2013; Jegelka and Bilmes, 2011; Krause and Guestrin, 2011; Kolmogorov and Zabih, 2002) and have recently attracted much attention in several NLP tasks including document summarization (Lin and ”
Approximation Guarantees for Adaptive Sampling (2018, background): “Curvature is a well-studied concept in the context of submodular optimization (Conforti & Cornuéjols, 1984; Vondrák, 2010; Iyer & Bilmes, 2013; Iyer et al., 2013; Sviridenko et al., 2015; Balkanski et al., 2016).”
Beyond Distributive Fairness in Algorithmic Decision Making: Feature Selection for Procedurally Fair Learning (2018, methodology): “…cost submodular cover (SCSC) problem (Iyer and Bilmes 2013) and can be solved by using the iterated submodular set cover (ISSC) algorithm proposed in Iyer and Bilmes (2013), which offers nHacc1+(n−1)(1−κunf ) bound on unf , where κunf is the curvature of unf , n is the number of features and…”
Adaptive Information Gathering via Imitation Learning (2017, methodology): “Iyer and Bilmes [17] solve a related problem (submodular knapsack constraints) using an iterative greedy approach which is generalized by Zhang and Vorobeychik [41].”
A Review on Fairness in Machine Learning (2022, background): “Their mechanisms are mathematical optimization formulations that are solved by applying a constrained submodular optimization [104].”
Submodularity in Data Subset Selection and Active Learning (2015, background): “…2014; Zheng et al., 2014; Hoi et al., 2006; Shamaiah et al., 2010; Prasad et al., 2014; Krause et al., 2008; Das & Kempe, 2011; Wei et al., 2014b; Kempe et al., 2003; Gabillon et al., 2013; Chen & Krause, 2013; Reed & Ghahramani, 2013; Singla et al., 2014; Liu et al., 2013; Iyer et al., 2013).”