Bicriteria Approximation Algorithms for the Submodular Cover Problem
Authors: Wenjing Chen
Victoria G. Crawford
Venue: NeurIPS 2023 poster (2023)
Keywords: submodular
combinatorial optimization
approximation algorithms
TL;DR: Approximation algorithms for the submodular cover problem

Abstract: In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe $U$ such that the value of a submodular function $f$ is above an input threshold $\tau$. In particular, we consider several variants of SCP including the general case, the case where $f$ is additionally assumed to be monotone, and finally the case where $f$ is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time; (ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible; and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an extensive experimental section on data summarization and graph cut, two applications of SCP.

Bicriteria Approximation Algorithms for the Submodular Cover Problem
Wenjing Chen, Victoria G. Crawford
Department of Computer Science & Engineering
Texas A&M University
jj9754@tamu.co edu, vcrawford@tamu edu
Abstract
In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find minimum cardinality subset finite universe U such that the value of a submodular function is above an input threshold т. In particular, we consider several variants of SCP including the general case, the case where f is additionally assumed to be monotone, and finally the case where f is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time: (ii) We are the first develop algorithm for general SCP that achieves a solution arbitrarily close to being feasible; and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated be effective in an experimental section on data summarization and graph cut, two applications of SCP.
Introduction
Submodularity captures diminishing returns property of set functions: Let f 2 R be defined over subsets of universe U of size Then f is submodular if for all A C C and $ B. f(A U {=)) - (A) 2 f(B {x}) - f(B). Examples of submodular set functions include cut functions in graphs [Balkanski et al., 2018), information-tteorrtic quantities like entropy and mutual information [[yer al., 2021], determinantal point processes [Gillenwater et al., 2012], and coverage functions [Bateni et al., 2017]. Submodular set functions arise in many important real-world applications including active learning [Kothawade et al., 2021. 2022], partial label learning [Bao et al., 2022], structured pruning of neural networks [EI Halabi et al., 2022], data summarization [Tsschiatshhek al., 2014], and client selection in federated learning [Balakrishnan et al., 2022].
While the majority of existing work has focused on developing approximation algorithms to maximize submodular function subject some constraint [Nemhauser al., 1978a, Mirzasoleiman al., 201 5a, Harshaw et al., 2019, Buchbinder et al., 2014) in this paper we focus on developing algorithms for the related optimization problem of Submodular Cover (SCP), defined follows.
Problem (Submodular Cover (SCP)). Let f: 2 + Rzo be nonnegative submodular set function defined over subsets of the ground sel U of size n. Given threshold T S max( X C SCP T).
find argmin [ [(X)
SCP captures applications where we seek to achieve certain value of in few elements as possible. For example, consider data summarization, where a submodular function formulated to measure how effectively subset X summarizes the entire dataset U [Tschiatschek et al., 2014]. Then we set 7 = max [ (X) : X C U.. SCP asks to find the set of minimum size in that achieves the maximum effectiveness summary. Another example is when expected advertising revenue
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

functions are formulated over subsets of social network [Hartline et al., 2008], then SCP asks how we can reach a certain amount of revenue while picking as small a subset of users as possible.
In this paper, we propose and analyze algorithms for several variants of SCP including the general case, the case where f is assumed to be monotone', and finally when f is regularized monotone submodular function (and potentially takes on negative values). We now list an overview of the contributions of our paper. In addition, a table summarizing all of our algorithmic contributions can be found in Table in the appendix.
(i) We first address the need for scalable algorithms for SCP where / is assumed to be monotone (MSCP). While the greedy algorithm finds the best possible approximation guarantee for MSCP [Feige, 1998], it makes O(n²) queries of which may be impractical in many applications. We propose and introduce two algorithms for MSCP which achieve nearly the same theoretical guarantee the greedy algorithm but only make O In(n)) queries of f. In addition, we extend the work of Iyer and Bilmes [2013a] to a method of converting fast randomized approximation algorithms for the dual cardinality constrained monotone submodular maximization problem [Nemhauser et al., 1978b] into approximation algorithms for MSCP.
(ii) Next, we address the need for algorithms that can produce nearly feasible solutions to the general SCP problem, where can be nonmonotone. In particular, provide the first algorithm for SCP that returns solution S that is guaranteed to satisfy: (i) J(S) 2 (1-e) -<)r; and (ii) |S| S 2(1 + OT/OPT]/e where OPT is optimal solution to the instance and a > O are input parameters. A caveat for our algorithm is that it is not necessarily polynomial time and requires an exact solution the cardinality constrained submodular maximization problem [Buchbinder et al., 2014] on an instance of size O(OOPT/E")) (iii) Third, we are the first to consider regularized monotone SCP (RMSCP). RMSCP where the objective f = g c where g is a nonnegative, monotone, and submodular function and i a modular cost penalty function. f is not necessarily monotone but potentially takes on negative values, and therefore this new problem doesn't 't fall under the general SCP problem. We develop a method of converting algorithms for the regularized monotone submodular maximization problem [Harshaw et al., 2019] into ones for RMSCP. We then propose the first algorithm for RMSCP, which a greedy algorithm using queries to a distorted version of f 9
(iv) Finally, we conduct an experimental analysis for our algorithms for MSCP and general SCP instances of data summarization and graph cut. We find that our algorithms for MSCP make large speedup compared to the standard greedy approach, and we explore the pros and cons of each relative to the other. We also find that our algorithm for general SCP is practical for our instances despite not being guaranteed to run in polynomially many queries of f.
1.1 Preliminary Definitions and Notation
We first provide number of preliminary definitions that will be used throughout the paper: (i) The Submodular Maximization Problem (SMP) is the dual optimization problem to SCP defined by. given budget x and nonnegative submodular function f. find argmax[/(X) (ii) Monotone SCP (MSCP) is the special case of SCP where f is additionally assumed to be monotone; (iii) Regularized MSCP (RMSCP) is where f = g -- and g is monotone. submodular, and nonnegative, while e is modular" nonnegative cost function; (iv) OPT is used to refer to the optimal solution to the instance of SCP that should be clear from the context; (v) OPT s. used to refer to the optimal solution to the instance of SMP that should be clear from the context; (vi) An (a, B)-bicriteria approximation algorithm for SCP returns a solution X such that |X| S a|OPT] and f(X) 2 BT. An (o, 3) biccritteaa approximation algorithm for SMP returns a solution X such that f(X) 2 af(PPT) and |X| < 3k. Notice that in the (a, 3) notation, the approximation on the objective is first, and the approximation on the constraint is second; (vii) The marginal gain of adding an element u E U to a set ç U is denoted as AS u) = J(S U - f(S); (viii) The function f. (fr
X U, I k];
AA set function f is monotone if for all A R U. f(A) S f(B). Every Z. E U is assigned cost cr such that c(X) Exex Ca.
2

---

1.2
Related Work
MSCP is the most studied variant of SCP [Wolsey, 1982, Wan et al., 2010, Mirzasoleiman et al., 2015b.
2016, Crawford et al., 2019]. The standard greedy algorithm produces logarithmic approximation guarantee for MSCP in O(n²) queries of f [Wolsey, 1982], and this is the best approximation guarantee that we can expect unless NP has n [[ooo(oonnn))) -time deterministic algorithms [Feige, 1998]. One version of the greedy algorithm for MSCP works as follows: A set S is initialized to be 0. Iteratively, the element argmax (/S(S x) (rgmaxA/(Ss)) x E U3 is added to S until ((S) reaches (1 ---) -)TT. It has previously been shown that this is (In(1/e), 1 - e)-bicriteria approximation algorithm [Krause et al., 2008). Beyond greedy algorithmss, algorithms for the distributed setting [Mirzasoleiman et al., 2015c, 2016], the streaming setting [Norouzi-Fate et al., 2016]. as well as the low-adaptivity setting Fahrbach et al. [2019] for MSCP have been proposed.
On the other hand, developing algorithms for SCP in full generality is more difficult since the monotonicity of f is not assumed. It is not even obvious how to find a feasible solution. The standard greedy algorithm does not have any non-trivial approximation guarantee for SCP. In fact, the best of our knowledge, no greedy-like algorithms have been found to be very useful for SCP. Recently, Crawford [2023] considered SCP and proved that it is not possible to develop an algorithm that guarantees f(x) 2 7/2 for SCP in polynomially many queries of f assuming the value oracle model. On the other hand, algorithmic techniques that are used for SMP in the streaming setting [Alaluf et al., 2022] proved to be useful for SCP. In particular, Crawford [2023] proposed an algorithm using related techniques to that of Alaluf al. that achieves a (O(1/e2), 1/2 e)-bicriteria approximation guarantee for SCP in polynomially many queries of f. We also take an approach inspired by the streaming algorithm of Alaluf al., but sacrifice efficiency in order find a solution for SCP that is arbitrarily close to being feasible.
SMP has received relatively more attention than SCP [Nemhauser al., 1978b, Badanidiyuru and Vondrák, 2014, 4, Mirzasoleiman et al., 2015a, Feige et al., 2, Buchbinder et al., 2014, Alaluf et al., 2022]. Iyer and Bilmes [2013b) 3b] proposed a method of converting algorithms for SMP ones for SCP. In particular, given a deterministic (7, )bbbriiitei approximation algorithm for SMP, the algorithm convert (see pseudocode Section 4.1 in the supplementary material) proposed by Iyer and Bilmes produces a deterministic ((1 + 3, -bbcrritia approximation algorithm for SCP. The algorithm works by making log1+a (n2) guesses for [OPT] (which is unknown in SCP), running the SMP algorithm with the budget set to each guess, and returning the smallest solution with f value above YT. However, this approach is limited by the approximation guarantees of existing algorithms for SMP. The best for monotone SMP is 1-11 1/c, and the best for general SMP where f is not assumed to be monotone is significantly lower [Gharan and Vondrák, 2011]. Several of the algorithms that we propose in this paper do generally follow the model of convert in that they rely on guesses of IOPT), but are different because they: (i) Implicitly use bicriteria approximation algorithms for SMP which have better guarantees on the objective (7) because they do not necessarily return feasible solution; (ii) Are more efficient with respect to the number of queries of f. since convert potentially wastes many queries of f by doing essentially the same behavior for different guesses of [OPT].
2 Algorithms and theoretical guarantees
In this section, we present and theoretically analyze our algorithms, with each subsection correspond- ing to the variant of SCP we consider. In particular, in Section 2.1 we first consider algorithms for MSCP, followed by the general problem of SCP in Section 2.2, and finally in Section 2.3, we consider algorithms for RMSCP.
2.1 Monotone submodular cover
In this section, we develop and analyze approximation algorithms for MSCP. The greedy algorithm is a tight (In(1/c), - e)- bicriittaia approximation algorithm for MSCP [Krause et al., 2008]. However, the greedy algorithm makes O(n²) queries of ʃ, which is impractical in many application settings with large U and/or when queries of are costly [Mirzasoleiman et al., 2015a]. Motivated by this, we propose and analyze the algorithms t thresh-greedy-o and stoch- stoch-greedy-c for MSCP which give about the same bicriteria approximation guarantees but in many fewer queries of f.
3

---

We first describe thresh-greedy--. thresh-greedy--o is closely related to the existing threshold greedy algorithm for monotone SMP (MSMP) [Badanidiyuru and Vondrák, 2014], and therefore we relegate the pseudocode of thresh-greedy- tary material and only include a brief discussion here. At each iteration of thresh-greedy--. instead of picking the element with the highest marginal gain into S, it sequentially adds any el- ements in with marginal gain above a threshold, w, at the time of addition. w is initialized to max.eu f({u)), and is decreased by a factor of (1 e/22) when the algorithm proceeds to the next iteration. thresh greedy с adds elements to a solution S until f(S) reaches (1 - E)T, which is shown to happen in at most (n(2 + elements in the proof of Theorem 1. We now state the theoretical guarantees of -greeh--reedd---- in Theorem
to Section 4.1 in the supplemen-
Theorem 1. thresh-greedy produces a solution with (In(2/c) 1, -)-biiiiteriaa approxi- mation guarantee to MSCP, in ( )) number of queries of f.
Another method of speeding up the standard greedy algorithm is by introducing randomization, as has been done for MSMP in the stochastic greedy algorithm [Mirzasoleiman et al., 2015a]. A natural question is whether a randomized algorithm for MSMP can be converted into algorithm for MSCP using the algorithm convert of Iyer and Bilmes [2013b]. However, convert relies on a deterministic approximation guarantee. We now introduce a new algorithm called convert rand that is analogous to convert but runs the MSMP algorithm repeatedly in order to have the approxi- mation guarantee hold with high probability. Pseudocode for convert-rande as well as proof of Theorem 2 can be found in Section 4.1 in the supplementary material.
Theorem Any randomized (y, (...3)rriiteriii approximation algorithm for MSMP that runs in time T(n) where holds only in expectation can be converted into an approximation algorithm for MSCP that with probability least 8 is a ((1 + 3) - c)bbicriteria approximation algorithm that runs in time ([lo)+.0000P])) ( (n) In( 1-)++)).
Therefore by applying Theorem the stochastic greedy algorithm of Mirzasoleiman al., we have a (1 + a. 1 e e)-bicriteria approximation algorithm for MSCP with high probability in (n 10g1+ (1) ln(1/e)/ In( (n(++zt()) queries of f. However, a factor of 1 - 1/ee - of is not very close to feasible, and further the convert -rnn method wastes many queries of s essentially doing the same computations for different guesses of [OPT]. Therefore we focus the rest of this section on developing an algorithm, stoch-trreeee Meochh-greey--- cc that uses the techniques of the stochastic greedy algorithm more directly for MSCP.
The idea behind the stochastic greedy algorithm for MSMP is that instead of computing the marginal gains of all elements each iteration, we take uniformly random sampled subset from U and pick the element with the highest marginal gain among the sampled subset. If the sampled subset is sufficiently large, particular of size at least (n/ (k) In (1/c) where k the budget for the instance of MSMP and c > 0 is an input, then with high probability a uniformly random element of OPTsM will appear in the sampled subset and the marginal gain of adding the element is nearly the same as the standard greedy algorithm in expectation. However, in MSMP we know that IOPT k. but in MSCP PT| is unknown. Therefore is not obvious how to apply this technique in more direct way than convert-rand.
We now introduce our algorithm stoch stoch- -aeeee-reeyccccce for MSCP, pseudocode for which is provided in Algorithm 1. stoch greedy----eey-eeeeo c takes as input > 0, 5 >> 0, a >> 0, and an instance of MSCP. keeps track of (In(1/)) possibly overlapping solutions S1, S2. ... throughout sequence of iterations. stochh-gredyy-eee also keeps track of an estimate of [OPT], g. During each iteration, for each solution S,, stoch-greedy- uniformly randomly and independently samples set R of size min(n, (n/g) ln(3/e)) and adds u argmax (frnaaxAAA(SS. (S,(S,,
E Ry to S,.
e Every time I+a ln(3/e)g elements have been added to each S;, g is increased by a factor of + a. stoch- toch-greedy--o stops once there exists an St such that f(S.) 2 (1 - e)r, and returns this solution.
We now state the theoretical results for stoch in Theorem 3. Theorem 3. Suppose that stoch-greedde at least 1 Setoch-greedy--eee bicriteria approximation guarantee in at most O (4aa" (1 (3/c) (og1+a((PPT)) queries of f.
is run for an instance of MSCP. Then with probability stoch greedy outputs a solution S that satisfies a ((1 + [)] 1- e)-

---

Algorithm 1 stochhgreedy-
Input: a, Output: 5 U
1: S. - -0Vi (1,..,,n(11)))) (n())
2: r r 11,1g 1+a
3: while f({) < (1- vi do
4:
for torie- [L..., (04_..,,n(1//0/1111 [m()) do
5:
R - sample min (nn(3c)//)) elements from U
6:
- argmax Af
7:
+ A.-SUUR fu}
8:
9:
if ln(3/e)g then +
10: return argmin f(S.) (1 - c)r}
Compared to ttresh-greedye the number of queries made to f. In addition, it possible to extend the stochastic greedy algorithm of Mirzasoleiman al. a (1 (1-6 e, In [ -bicriiciae approximation algorithm for MSMP and then use convert rand (see Section 4.1 in the supplementary material). However, stoch -orehhggreeyeeee still would have strictly fewer queries of by a factor of _
stoch-greedy-- has better dependence in terms of
T+o compared this approach because convert-rant does essentially the same computations for different guesses of [OPT].
In order to prove Theorem 3, we first need Lemma below, which states that as long as S (1+ + (OP] the marginal gain of adding u in Line 6 is about the same as the standard greedy algorithm in expectation. Next, Lemma 2 below uses Lemma to show that by the time g reaches (1 + a)) OPT), (S.)] Z (1 F I for all Finally, because there are (In(1/6)) solutions, by the time reaches (1 + =a)ooPTi there exists such that f(S,) 2 (1 e)T with probability at least 8 by using concentration bounds, which stated in Lemma Because of Lemma 3 we keep increasing g by factor of (1 a) periodically, because intuitively the longer we keep adding elements, the bigger we know that JOPT] must be since the algorithm is still running and none of the solution sets has reached (1 - t)T yet. The proof of Lemmas and 2, and of Theorem 3 can be found Section 4.1 in the supplementary material.
Lemma Consider any of the sets S the beginning of an iteration on Line where g S (1 + OPP] Then if u4 is the random element that will be added on Line 6, we have that 1-e/3 (Taa)OPTT(* (T((()))
(S u)) 2
Lemma 2. Once r reaches (1 + a) [iI[nn(/C))OPTT]] we have that Blf+ 2 (1 (1-5) 5) T for all i.
Lemma 3. With probability at least 5, once reaches (1 a)+))\l(33 we have that
max; ((S) (1 E)T.
2.2 Non-monotone submodular cover
In this section, we introduce and theoretically analyze the algorithm stream-c for SCP in the general setting, where f assumed be monotone. the general setting, the standard greedy algorithm doesn't t have non-trivial approximation guarantee for SCP. In addition, it has previously been shown that not possible for an algorithm to guarantee that f(X) 2 7/2 for SCP, where X is its returned solution, in polynomially many queries of assuming the value oracle model [Crawford, 2023]. Our algorithm reamm-- does produce a solution that guaranteed to satisfy f(X) > (1 E)T, but relies solving an instance of SMP exactly a set of size O(OPT)/e Despite not being polynomial time, streant c is still useful for some instances of SCP because: (i) JOPT may be relatively small; and (ii) the instance of SMP may be relatively easy to solve, e.g. If may be very close to monotone on the instance SMP even was very mon-monotonee on the original instance of SCP. These aspects of stramm-c are further explored in Section 3.
now describe st ream-c, pseudocode for which can be found Algorithm ream-- c takes as input > 0, > 0, and an instance of SCP. ream-c takes sequential passes through the universe U (Line 4) with each pass corresponding
new guess of (TPT), g. g initialized as 1 + a, and at the end of each pass is increased by factor of 1 + a. Throughout st ream-c, a subset
5

---

Algorithm 2 stream-c
Input:
Output: SC U
1: S x 0,51 <- 0.,,, S2e t- 0
2: g+ 1+a
3: while f(S) < (1-11)10) <)T do
4: for
do
5:
if jj s.t. Af(S;: 2 (2/(2g) and |Sy] < 2g/c then
6:
Sj 8j {u)
7:
S + argmax (X( X 1 x 2g/e}
8:
g 9= ag
9:
return S
of elements of U are stored into 2/c disjoint sets, S1.-.., An element is stored in at most set S₁ if both of the following true: (i) |Syl 2g/c; (ii) adding is sufficiently beneficial to increasing the f value of Sj i.e. Af(S, u) 2 cT (2g). If no such S, exists, u is discarded. At the end of each pass, stream-c finds 5 argmax{f(XX X US s 2g/c) on Line 7. If S(S) 2 (1 e)T, then is returned and stramm- terminates. We now present the theoretical guarantees of ream--- in Theorem 4.
Theorem 4. Suppose that stream c run for an instance of SCP. Then stream returns S such that (SS) (1 - E)T and |8| (1 (2/e))]PPT in most
2m ( +T (T((+)))))))) (
log l
queries of f. where ((m) is the number of queries to f of the algorithm for SMP used on Line 7 of Algorithm 2 on an input set of size m.
The key idea for proving Theorem is that by the time is in the region [I OPP]) there
exists subset X C US; such that [X| 2g/c and f(X) 2 (1-c)r. In fact, is shown in the proof of Lemma in Section 4.2 of the supplementary material that the set X is (U, for certain one of the sets S, Then when we solve the instance of SMP on Line same properties as X, and stream- C returns this set and terminates. Because S (1 + OPT) the properties described in Theorem 4 hold. Further notice that U S,| < 2(1 + a)(OPT) at all times before st re am-o C exits, which implies the bounded query complexity in Theorem 4. The key idea for proving Theorem is stated below in Lemma and proven in Section 4.2 in the supplementary material.
find set that has these
Lemma 4. By the time that g reaches the region [[OPT), (1+ + a)[OPT]] and the loop on Line of ream-c has completed, there exists set X US of size at most 2(1 + +a)OOPT/e such that f(X) 2 (1 c)r
2.3
Regularized monotone submodular cover
The final class of submodular functions we consider take the form f f= - where is monotone, submodular, and nonnegative, while is modular, nonnegative penalty Regularized Monotone Submodular Cover Problem (RMSCP). In this case, f may take on negative values and therefore this class of submodular functions does not fit into general SCP. f may also be nonmonotone. Existing theoretical guarantees for the dual problem of Regularized Monotone Submodular Maximization (RMSMP) are in a different form than typical approximation algorithms [Harshaw et al., 2019, Kazemi et al., 2021]. In particular, they are of the following form: Given budget k, the RMSMP algorithm is guaranteed return S such that | < к. and g(S))c(S) > rg(OPTs>s)
function, called the
(T where is some value less than 1, e.g. - 1/e for the distorted greedy algorithm of Harshaw et al.. A guarantee of this form means conver cannot used (the check on Line 2 of the pseudocode for convert in the appendix is the problem). Motivated by this, we first develop an algorithm, convert -eeg, that takes algorithms for RMSMP and converts them into an algorithm for RMSCP. Next, we propose generalization of the distorted greedy algorithm of Harshaw et al. for RMSMP, called di distorted-be that can used along with convert-red to produce an algorithm for RMSCP.

---

Algorithm 3 convert -rag reg
Input: a >0
Output: S
1: k --- a 4- 0
2: while g()) - (c() < yT do
3: S trrg run with objective 3e and budget A
4: k a))
5: return S
We now describe convert-reg, pseudocode for which can be found Algorithm 3. convert-reg takes input algorithm reg for RMSMP with the guarantees described previ- ously, and a > O. convert-zeg repeatedly makes guesses for [OPT], K. For each guess K, the algorithm reg is on instance of RMSMP with objective g (7/B)c and budget k. Once (7/ ( reaches yy, convert exits.
The theoretical guarantees of convert-reg are stated below in Theorem 5 and proven in Section 4.3 in the supplementary material. Theorem makes a slightly stronger assumption on reg than its approximation guarantees relative to OPTsM- In particular, it is assumed that it returns solution satisfying |S| S pk and g(S) - dS) 2 (X(X) 3x(X) for all X C U such that [X] S K, not just for OPT SM- However, this is true of many algorithms for RMSMP including the distorted greedy algorithm of Harshaw et al..
Theorem 5. Suppose that we have an algorithm reg for RMSMP, and given budget k req is guaranteed return set S of cardinality at most pK such that g(S) - c()) 2 (X( Bc(X) for all such that [X] S K. in time T(n). Then the algorithm convert-res using reg as subroutine returns set S in time (1) such that |S| S (1 + p)P and g(S) (c(S)= 2 y7.
If we use convert reg on the distorted greedy algorithm of Harshaw et al., end up with an algorithm for RMSCP that is guaranteed to return a set such that |S] s a1+ and g(S) 1/e)c(S) 2 (1 - 1/e)r. If we set O, then the problem setting reduces to MSCP and the distorted greedy algorithm of Harshaw et al. [2019] is equivalent to the standard greedy algorithm. However, our approximation guarantee does not reduce to the (In(1/e), 1-c) e)bbcrriteria approximation guarantee that would be preferable. more intuitive result would be one that converges to that of the standard greedy algorithm goes to O. Motivated by this, now propose extension of the distorted greedy algorithm of Harshaw et al. [2019] for RMSMP, distorted-bi, that accomplishes this.
We now describe distorted-bi, pseudocode for which can be found in Section 4.3 in the supplementary material. distorted-bl takes as input an instance of RMSMP and > 0. distorted-bi bi is related to the standard greedy algorithm, but instead of making queries to g c, distortdd-b queries distorted version of y c that de-emphasizes y compared to c, and evolves over time. In particular, when element is being added to the solution set, we choose the element of maximum marginal gain, provided it is positive, to the objective
ln(1/e)x=$
2x(X) (1 (1-##) K
((X)
The theoretical guarantees of di diottedd-bi now presented in Theorem 6, and the proof of Theorem can be found in Section 4.3 in the supplementary material.
Theorem 6. Suppose that distorted-bi is run for an instance of RMSMP. Then distorted-bi produces solution S in O (1(c))) queries of f such that |S| In(1/e)K and all X C U such that |X| < K, g(S) - c(S) 2 (1 =)g(()- In(1ee)((())
Therefore by running convert-res with di distorted-bi as a subroutine for RMSMP, we end up with algorithm for RMSCP that is guaranteed to return a set S such that |S| (1 + a) In(1/e)) and g(S) - (1 - ()((S)/n((1)) 2 (1 - t)T in O((1- +
O)][OPT| log ((OPT)) (o)(1 queries of f.
7

---

SG2
SC2
SG2
56
1.2
quirees
10
0.08
TO
3.0
1.5
0.0
0.2
0.6
1.0
0.2
0.4
0.66
0.8
1.0
0.05
0.10
0.15
(a)
(b) size
(c) queries
(d) queries
x10*
x101
queries
1.2
150
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.8
0.8
0.2
0.4
0.8
0.8
1.0
0.1
0.2
0.3
0.4
0.5
threshold
threshold
threshold
(c) euall f
(f) cuall size
(g) cuall queries
(h) cuall queries
Figure I: The experimental results of running the monotone algorithms on instances data summa- rization on the delicious URL dataset ("cover") and running stamam-c on the instances of graph cut on the email-EuAll graph ("euall").
Experiments
In this section, we experimentally evaluate the algorithms proposed in Sections 2.1 and 2.2. In particular, the emphasis of Section 3.1 on evaluation of our algorithm stoch groecy-reed--- on instances of data summarization, an application of MSCP. Next, we evaluate stream-c on instances of graph cut, an application of SCP that is monotone, in Section 3.2. Additional details about the applications, setup, and results can be found in Section 5 in the supplementary material.
3.1 Monotone submodular objective
We first compare the solutions returned by stoch- ("SG"), greedy-c ("G"), thresh-greedy-oe ("TG"), and convert-rand using the bicriteria extension of the stochastic greedy algorithm of Mirzasoleiman al. (see Section 4.1 in the supplementary material) ("SG2") on instances of data summarization. The data summarization instance featured here in the main paper the delicious dataset of URLS tagged with topics, and takes subset of URLs to the number of distinct topics represented by those URLs (n = 5000 with 8356 tags) [Soleimani and Miller, 2016]. Additional datasets explored in Section 5.2 in the supplementary material. We run the algorithms with input in the range (0, 0.15) and threshold values between 0 and f(U) (f(U) is the total number of tags). When is varied, is fixed OU. When is varied, is fixed 0.2. The parameter set to be 0.1 and the initial guess of |OPTI for Stocch-greede be T/ max, f(s).
and convert- - -rand is set
The results in terms the values and size of the solutions are presented Figure ((a) and 1(b). From the plots, one greedy-c, thresh-gae thresh-greedy-c are nearly the same, and are smaller than the ones returned by convert-rand This is unsurprising, because the theoretical guarantees the same for the different algorithms, but convert-rand tends to perform closer to its worst case guarantee on size. The number of queries f for different and are depicted in Figures I(d) and 1(c). Recall that the theoretical worst case number of queries to ʃ for stoch-greedy greedy-c, thresshgreedy-- and convert are O((a/(1 + a:) (1/)))011++((PPP))) (n In (n/c)))OPPT) (n (Pg[(OPT)/c//// and (nn (1/c) log ((OPT)) respectively. As ex- pected based on these theoretical guarantees, greedy-c does worst and increases rapidly as (and therefore (OPT)) increases. thresh-greedys tends to do worse compared to sttcch-greedye and convert as gets smaller. stoch-greedy-c consistently performs the fastest out of all of the algorithms.
that the ff values and size of solutions returned by
f and size about

---

3.2 Non-Monotone Submodular Objective
We now analyze the performance of stream-c on several instances of graph cut over real social network data. The universe U is all nodes in the network, and f is the number of edges between a set and its complement. The network featured in the main paper is the email- -uAlll dataset (n 265214, 420045 edges) from the SNAP large network collection [Leskovec and Sosič, 2016] and additional datasets can be found in Section 5.1 in the supplementary material. We run stream-c with input c in the range (0, 0.5) and threshold values between O and f(X) where X is a solution returned by the unconstrained submodular maximization algorithm of Buchbinder et al. [2015] on the instance. When is varied, is fixed at (x9 When 7 is varied, is fixed at 0.15.
We compare the performance of stream-c C using several possible algorithms for the subroutine of SMP over US; (see line 7 in Algorithm 2). including polynomial time approximation algorithm and an unconstrained submodular maximization algorithm. In particular, we use the random greedy approximation algorithm for SMP that is proposed in Buchbinder et al. [2014] (" ("RG"), and the double greedy approximation algorithm for unconstrained submodular maximization proposed in Buchhinder et al. [2015] ("DG"). Random greedy and double greedy are both approximation algorithms (1 /e in expectation and 1/2 in expectation respectively), and therefore the stopping conditions are set to be (l-s)r and (l=r)r respectively. We also consider an exact algorithm ( ("EX"), which essentially is greedy heuristic followed by an exact search of all (exponentially many) possible solutions if the greedy fails. On instances where the exact algorithm was unable to complete in a time period of 5 minutes, we did not include a data point. We further discuss the use of these algorithms Section 5.1 in the supplementary material.
Before introducing the fourth subroutine, discuss an interesting pattern that we saw in our instances of graph cut. We noticed that it was often the case that: (i) US; tended to be small compared to its upper bound and in fact typically UU S was smaller than the SMP constraint, making the subroutine an instance of unconstrained submodular maximization; (ii) The majority of elements (if not all) were "monotone" in the sense that for many x E US Af(US, x) 2 0. Let M S US, be the set of monotone elements. It follows that if (i) holds, then the instance of submodular maximization equivalent to arg maxxeus, fXX M). If M is large US,, this new problem instance is relatively easy to solve exactly. This motivates our fourth algorithm, fast-exact ("F-EX"), used on instances where (i) holds, and is to separate US; into monotone and non-monotone and search for the best subset amongst the non-mone non-monotone elements in similar manner as the plain exact algorithm. We explore to what extent properties (i) and (ii) hold on different instances, as well as give additional details about the fast exact algorithm, in Section 5.2 in the supplementary material.
The results in terms of the ʃ values and size of the output solutions returned by the four algorithms are plotted in Figure 1(e) and Figure 1(f). From the plots, one can see that the f values satisfy that ((Sea)) = fS
fSDO)) > f(RG). This due the stopping conditions for each algorithm, which follow from each algorithms approximation guarantee on f of 1 - e, 1 e, 1/2. and 1/c respectively. On the other hand, the size mirrors the f value, since it tends to the case that reaching a higher f value requires more elements from U. The number of queries made by the algorithms can be seen in Figure 1(h) and I(g). As expected, the exact algorithms make more queries compared to the approximation algorithms, and in some cases "EX" doesn't 't even finish. However, by taking advantage of the properties (i) and (ii) discussed above, "F-EX" is able to run even for smaller Therefore, depending on the application, an exact algorithm on the relatively small set US; may be a practical choice in order to achieve a solution that very close to feasible.

---

References
Eric Balkanski, Adam Breuer, and Yaron Singer. Non- con-monotone submodular maximization in exponentially fewer iterations. Advances in Neural Information Processing Systems, 31, 2018.
Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, and Himanshu Asnani. Generalized submodular
information measures: Theoretical properties, examples, optimization algorithms, and applications. IEFE Transactions on Information Theory, 68(2):752-781 2021.
Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. Advances in Neural Information Processing Systems, 25, 2012.
MossmmadHosseein Bateni, Hossein Esfandiari, and Vahab Mirrokni. Almost optimal streaming algorithms for coverage problems. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pages 13-23, 2017.
Suraj Kothawade, Nathan Beck, Krishnateja Killamsetty, and Rishabh Iyer. Similar: Submodular information measures based active learning in realistic scenarios. Advances in Neural Information Processing Systems, 34: 1 8685-18697, 2021.
Suraj Kothawade, Saikat Ghosh, Sumit Shekhar, Yu Xiang, and Rishabh Iyer. Talisman: targeted active learning for object detection with rare classes and slices using submodular mutual infor- mation. In Computer AssionEECYY 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings. Part XXXVIII, pages 1-16. Springer, 2022.
Wei-Xuan Bao, Jun-Yi Yi Hang, and Min-Ling Zhang. Submodular feature selection for partial label learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 26-34,22 2022.
Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien, Data-efficient structured pruning via submodular optimization. Advances in Neural Information Processing Systems, 35:36613-36628 2022.
Sebastian Tschiatschek, Rishabh lyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. Advances in neural information processing systems, 27, 2014.
Ravikumar Balakrishnan, Tian Li, Tianyi Zhou, Nageen Himayat, Virginia Smith, and Jeff Bilmes. Diverse client selection for federated learning via submodular maximization. In International Conference on Learning Representations, 2022.
George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14(1):265-294, 1978a.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015a.
Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In International Conference on Machine Learning, pages 2634 2643. PMLR, 2019.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM- symposium on Discrete algorithmss, pages 1433-1452. SIAM, 2014.
Jason Hartline, Vahab Mirrokni, and Mukund Sundararajan. Optimal marketing strategies over social networks. In Proceedings of the 17th international conference on World Wide Web, pages 189-198, 2008.
Uriel Feige. A threshold of In(n) for approximating set cover. Journal of the ACM (JACM), 45(4): 634-652, 1998.
Rishabh K Iyer and Jeff Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. Advances in neural information processing systems, 26, 2013a.
10

---

George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming. 14(1):265-294 1978b.
Laurence A Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, (44:338-333,, 1982.
Peng-Jun Wan, Ding-Zhu Du, Panos Pardalos, and Weili Wu. Greedy approximations for minimum submodular cover with submodular cost. Compulational Optimization and Applications, 45(2): 463-474, 2010.
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Dis- tributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Informa- tion Processing Systems, pages 2881 2881-2889, 2015b.
Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi. Fast distributed submodular cover: Public-private data summarization. In Advances in Neural Information Processing Systems, pages 3594-3602, 2016.
Victoria Crawford, Alan Kuhnle, and My Thai. Submodular cost submodular cover with an ap- proximate oracle. In International Conference Machine Learning, pages 1426-1435, PMLR, 2019.
Andreas Krause, H Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9(12), 2008.
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Dis- tributed submodular cover: Succinctly summarizing massive data. Advances in Neural Information Processing Systems, 28, 2015c.
Ashkan Norouzi-Fard Abbas Bazzi, Ilija Bogunovic, Marwa El Halabi, Ya-Ping Hsieh, and Volkan Cevher. An efficient streaming algorithm for the submodular cover problem. In Advances in Neural Information Processing Systems, pages 4503, 2016.
Matthew Fahrbach, Vahab Mirrokni, and Morteza Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algorithms, pages 255-273. SIAM, 2019.
Victoria Crawford. Scalable bicriteria algorithms for non-monotone submodular cover. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 9517-9537. PMLR, 2023.
Naor Alaluf, Alina Ene, Moran Feldman, Huy L Nguyen, and Andrew Suh. An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 47(4): 2022.
Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the twenty-fifth annual ACM-SIA symposium on Discrete algorithms, pages 1497-1514. SIAM, 2014.
Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing con-monotone submodular functions. SIAM Journal on Computing, 40(4):1133-113 1153, 2011.
Rishabh K Iyer and Jeff A Bilmes. Submodular optimization with submodular cover and submodular knapsack constraints. In Advances Neural Information Processing Systems, pages 1436-2444, 2013b.
Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the (wenty-second annual ACM-SIAM symposium on Discrete Algorithmss, pages 1098-1118 1116. SIAM, 2011.
Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. In International Conference on Machine Learning, pages 5356-5366. PMLR, R, 2021.
11

---

Hossein Soleimani and David J Miller. Semi Semi-supperiiee multi-label topic models for document classification and sentence labeling. In Proceedings of the 25th ACM international on conference on information and knowledge management, pages 105-114, 2016.
Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-mining library, ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1-20, 2016.
Niv Buchbinder, Moran Feldman, Joseph Seffi, and Roy Schwartz. A tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM Journal Computing, 44(5): 1384-1402, 2015.
Pinar Duygulu, Kobus Barnard, Joao FG de Freitas, and David A Forsyth. Object recognition as machine translation: Learning lexicon for a fixed image vocabulary. In Computer Ecoon-ECV 2002: 7th European Conference on Computer Vision Copenhagen, Denmark, May 38-31, 2002 Proceedings, Part IV pages 97-112. Springer, 2002.
12


Reviews:
[{"review_id": "27EcKCXQRY", "reviewer": "Reviewer_fbw1", "summary": "The paper considers the Submodular Cover Problem (SCP), where one\nis given a submodular function f through an oracle that returns the\nvalue f(A) for each subset A of the underlying set U (over which\nthe function f is defined). The goal is to find a minimum cardinality\nsubset X of a set such that the value f(X) is >=  a given threshold\n\\tau and |X| is a minimum. Since this problem is NP-hard in general,\nresearchers have considered bicriteria approximation algorithms,\nwhere the size of the size of the returned subset X is within a\nsmall factor of the size of a minimum subset and the value f(X) is\nat least a suitable fraction of the given threshold.  While some\nsuch approximation algorithms are available (using a dual problem),\nthey may use quadratically many queries to the oracle.  The focus\nof the paper is to develop methods whose approximation guarantees\nare close to known results but which use significantly fewer queries\nto the evaluation oracle. Results are provided for general SCP as\nwell as some restricted versions.", "questions": "(1) In the results for the general SCP (lines 50--54, page 2), it is\n  mentioned that the algorithm does not run in polynomial time in general.\n  Is there a known hardness result which precludes a polynomial\n  time algorithm for this case (under some well accepted hypothesis in\n  complexity theory)?\n\n  (2) Lines 98--100 in Section 1.2 discusses a result from {Crawford, 2023].\n  This result (as described) says that one \"cannot have an algorithm for SCP\n  which can guarantee that f(X) >= \\tau/2 using only polynomially many queries\".\n  Does this result rely  on an underlying complexity hypothesis (such as P != NP)?\n\n  Some minor suggestions to the author(s):\n\n  (a) In stating the results for RCSP (lines 56--62 on page 2), please\n  consider indicating the number of queries to the oracle.\n\n  (b) Line 65: \"make a large\" ---> \"provides a large\"\n\n  (c) Line 120 (page 3): \"about queries\" ---> \"with respect to the\n      number of queries\"", "limitations": "None", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "(1) The paper presents new methods for SCP with significantly smaller\n  numbers of queries to the function evaluation oracle without significantly\n  affecting the performance guarantees. To this reviewer's knowledge, this\n  is the first work that achieves this goal for SCP. Given the importance\n  of submodular optimization in ML these results represent a useful advance.\n\n  (2) The paper nicely summarizes prior work on the topic.", "weaknesses": "   A (very) minor weakness is that it takes a fair amount of time\nto understand the details regarding the algorithms. (This is due to the\nnature of the problem.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments about the paper. We will update the manuscript to add your suggested modifications. We address your questions below.\n\n(1) The result we are aware of for SCP is that under the value oracle model of access for $f$, meaning that $f$ is only accessed as a black box that returns $f(X)$ given $X$, it is not possible for an algorithm to produce a solution $X$ with the guarantee that $f(X)>\\tau/2$ in polynomially many queries to $f$ [Crawford, 2023]. Our algorithm stream-c guarantees $f(X)\\geq (1-\\epsilon)\\tau$ for any $\\epsilon > 0$, but on the other hand is not guaranteed to make polynomially many queries to $f$.\n\n(2) The result of [Crawford, 2023] does not rely on any complexity hypothesis, but rather applies to any algorithm under the value oracle model. For more intuition about hardness results for submodular optimization problems assuming the value oracle model access to $f$, we refer the reviewer to Section 4 of [Feige et al., 2011]. In fact, the result that we cite from [Crawford, 2023] for general SCP is closely related to Theorem 4.5 in this paper."}, {"review_id": "XOfRlb0Gs7", "reviewer": "Reviewer_DEGK", "summary": "This paper proposes several bicriteria approximation methods for solving the standard monotone submodular cover problem (SCP). Additionally, the authors also propose new variants of the problem: removing the monotone assumption, producing nearly feasible solutions, and adding regularization via a modular cost function. The general methodology involves novel conversions from common bicriteria algorithms for the (dual) submodular maximization problem (stochastic greedy, threshold greedy, distorted greedy) into ones for SCP.", "questions": "- What are some applications of regularized SCP?\n- Are any bicriteria approximations or query complexity results optimal, or can they be improved further?\n\n\n-----\nEDIT: I have read the author rebuttal, and it addressed my questions sufficiently.", "limitations": "No discussions of limitations or broader impact", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- Significance: This paper uses a powerful framework which leads to not only novel algorithms but also new problem formulations. Expanding the scope of SMP/SCP conversion is of independent interest and has high potential impact\n- Originality/Clarity: Novel combination of previous work and new ideas (discussed and cited clearly)", "weaknesses": "- Experiments: The impact of the regularized SCP problem would be more significant if the paper included experimental results comparing convert-reg and distorted-greedy-bi. The paper would be improved if it provided additional motivations/applications for each SCP formulation. When is SCP preferable to SCM?\n- Typo: distorted algorithm is distorted-greedy-bi in the main paper and distorted-bi in the appendix", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and comments. We address each of your questions below.\n\n- \"What are some applications of regularized SCP?\"\n\nMany applications of the well-studied regularized submodular maximization problem (SMP) [Harshaw et al., 2019] are also suitable applications for RSCP, just with a shifted emphasis from keeping within a budget (the constraint in regularize SMP) to achieving a certain value of $f$ (the constraint in RSCP). As an example, consider the profit maximization setting where $f=g-c$ and $g$ models the revenue from a group of products while $c$ models the price of producing them. Then RSCP would formalize the problem of achieving a certain amount of revenue ($\\tau$) using the minimum amount of products. In addition, many existing applications of SCP such as data summarization [Mirzasoleiman et al., 2016]  or influence in a social network  [Crawford et al., 2019] could be extended to RSCP by adding a modular penalty/cost for including each item into the solution set.\n\n- \"Are any bicriteria approximations or query complexity results optimal, or can they be improved further?\"\n\nIt was proven by [Feige, 1998] that set cover cannot be approximated efficiently below a threshold of $(1-o(1))\\ln(n)$ subject to the condition that NP has slightly superpolynomial time algorithms. Set cover is a special case of the general monotone submodular cover problem, and therefore this result applies to MSCP as well as SCP. If we fix the parameter $\\epsilon=1/n$, then the algorithms threshold-bi and stoch-greedy-c presented in our paper achieve nearly feasible solutions for MSCP with approximations of $\\ln(2n)+1$ (Theorem 1) and $(1+\\alpha)\\lceil \\ln(3n)\\rceil$ (Theorem 3) respectively. Therefore these algorithms have bicriteria guarantees that are somewhat close to the best possible. However, we have not yet been able to determine the optimality of our results beyond this."}, {"review_id": "UQ5aOI4TUz", "reviewer": "Reviewer_AFAK", "summary": "The paper studies bicriteria approximation algorithms for sub-modular cover problem (SCP). In the problem, we are given an oracle to some sub-modular function f, and a threshold tau. Our goal is to find the smallest set X such that f(x) >= tau. \n\nThe paper is not well-written at all. There are critical typos in the theorem statements, making it hard to understand what the main results are.  Only after reading the rebuttal and the supplementary materials carefully, I was able to put all the pieces together. Two main results of the paper are \n\nFor the monotone SCP problem (MSCP), the result is an algorithm that achieves O(ln(1/eps))-approximation with 1-epsilon violation on the value, using O_eps(n log n) queries. This improves the previous query complexity of O(n^2). However, the algorithm is called threshold-greedy-c, described in Algorithm 5 in the supplementary material. But the theorem statement says the algorithm is threshold-bi, which is never defined.\n\nThe second result is for SCP. It says there is an algorithm that achieves 1/epsilon approximation with 1-epsilon violation on the value. The result uses theorem 2, which converts a randomized algorithm for the dual problem SMP into a randomized algorithm for SCP. The algorithm needs to guess a budget g, and repeat the algorithm for SMP multiple times in order to convert the expectation guarantee into high probability guarantee. However, in the theorem statement, gamma should be epsilon as pointed by the authors in the rebuttal, and alpha is never defined. From the supplementary material, I learnt that alpha is the parameter controlling the multiplicative step size of the guessed size budget g, and the term log |OPT| in the running time should really be log_{1 + alpha} |OPT|.\n\nI am raising my score to borderline reject.  There are so many typos in the theorem statements. Yes, they are just a few typos in the whole paper, but I think mistakes in the main theorems, which give the formal descriptions of main results, are intolerable. They are the first things that people will read, and they only take a few lines in the paper. \n\nIf I needed to judge the contribution of the results, without taking the typos into consideration, I would say the first result makes a fair improvement, but I do not see too much technical contribution from the second result. It is based on the dual relationship between SCP and SMP, and conversion from expectation to high probability comes from repeating the algorithm multiple times. \n\n", "questions": "No questions.", "limitations": "None.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper improved the query complexity for the MSCP algorithm from O(n^2) to O(n log n). ", "weaknesses": "The paper is not written well.  There are critical typos in the statements of the main theorems. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their time and comments on the paper. We address each concern and question below.\n\n(1) \"The authors stated that they have an algorithm that achieves the best approximation guarantee with O(n ln(n)) queries. I do not see any proof of the result.\"\n\nWe will explain this point more clearly in the next version of the manuscript. It is stated in the paper (see contribution (i) in the introduction) that we provide two algorithms for MSCP that achieve nearly the same theoretical guarantees as the greedy algorithm but in $O(nln(n))$ queries of $f$. The two algorithms that make $O(nln(n))$ queries to $f$ are threshhold-bi and stoch-greedy-c. The theoretical guarantee for threshold-bi is presented in Theorem 1, which states that the number of required queries is $O(\\frac{n}{\\epsilon}\\log(\\frac{n}{\\epsilon}))$. If we fix $\\epsilon$, then the number of queries is $O(n \\ln(n))$. The theoretical guarantee for stoch-greedy-c is presented in Theorem 3, which states that the number of required queries is $O\\left(\\frac{\\alpha}{1+\\alpha}n\\ln(1/\\delta)\\ln^2(3/\\epsilon)\\log_{1+\\alpha}(|OPT|)\\right)$. If we fix $\\alpha$, $\\delta$, and $\\epsilon$ then the number of queries is $O(n \\ln(n))$. \n\n(2) \"For the problem with (1-epsilon)-approximation allowed on the f(S) value, do you get an O(1/epsilon), or an O(ln(1/epsilon))-approximation guarantee? In result (ii), the size of S is OPT/epsilon. But in Theorem 1, the approximation ratio is ln(2/epsilon) = O(ln(1/epsilon)).\"\n\nThe two approximation ratios that you describe are for different problem settings. If we assume that $f$ is monotone, we get the stronger $O(\\ln(n))$ approximation guarantees proven for threshold-bi and stoch-greedy-c (Theorems 1 and 3). If we do not assume that $f$ is monotone and therefore consider the more general setting, then the approximation guarantee we have is the weaker $O(1/\\epsilon)$ guarantee proven for stream-c in Theorem 4.  All of the algorithms described above achieves a $(1-\\epsilon)$-approximation on the f(S) value (see Theorem 1, Theorem 3 and Theorem 4). There is a typo that may have contributed to the confusion, Theorems 1 and 2 are in the monotone submodular section but say \"SC\"/\"SCP\" instead of the correct \"MSCP\".\n\n(3) \"Finally, what is the purpose of Theorem 2? How does it improve the result in Theorem 1? What does gamma mean in the theorem statement?\"\n\nThe purpose of Theorem 2 is to provide a method for converting randomized algorithms for the dual problem SMP into ones for SCP. In particular, we are interested in using Theorem 2 to convert the stochastic greedy algorithm for monotone SMP [Mirzasoleiman et al.] into an algorithm for MSCP.\n\nWe actually made a typo with the $\\gamma$ and it should be replaced with $\\epsilon$. Thank you for bringing this to our attention. The corrected version of Theorem 2 appears in the supplementary material on page 14 of our submission.\n\nThe method described by Theorem 2 gives results beyond those of Theorems 1 and 3 for monotone SCP. In particular, consider the stochastic greedy algorithm of Mirzasoleiman et al., which is a randomized algorithm for SMP that returns a solution set $S$ satisfying $f(S)\\geq(1-1/e-t)f(OPT)$ and $|S|=\\kappa$. Then in Theorem 2, $\\epsilon=2/e+2t$ and $\\beta=1$. Then by using the algorithm convert-rand (Algorithm 6 in the appendix) Theorem 2 states that we have a $(1+\\alpha, 1-2/e-2t)$-bicriteria that holds with probability $1-\\delta$, where $\\alpha,\\delta$ are input. This is incomparable to the guarantees given in Theorems 1 and 3 since the first part can get arbitrarily close to 1 but the second part, i.e. the guarantee on the feasibility, is relatively weak. In contrast, the approximation ratio on $f$ for both Theorem 1 and Theorem 3 is $1-\\epsilon$ and can get arbitrarily close to 1. We will more explicitly describe this example in the next version of the manuscript."}, {"review_id": "XoiuZze2cn", "reviewer": "Reviewer_Swbd", "summary": "This work focuses on designing approximation algorithms for the submodular cover problem. In this problem, we are given a submodular function $f$ over subsets of a ground set $U$, and the goal is to find the smallest subset $S$ such that $f(S)$ is greater than or equal to a given threshold. The authors present a fast algorithm for monotone functions with similar approximation guarantees as greedy, while being almost a factor of $n$ faster. They improve the approximation guarantee with an algorithm that runs in exponential time with respect to the size of the optimal solution. They extend their results to non-monotone functions and achieve a high-quality solution with exponential running time.\n\nFurthermore, they consider the regularized submodular cover problem, which is similar to the submodular cover problem minus an additional modular function. They are the first to study this problem and present bicriteria algorithms for this problem. Moreover they compare their algorithms with baselines in multiple experiments.\n", "questions": "Please provide details if the weaknesses mentioned above are not accurate.", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors' work makes significant contributions to the field of submodular cover optimization. Their algorithms are simple and easy to understand, and the results are explained clearly. The authors also provide a fair comparison with previous works. The experimental section is well-organized and the datasets used are commonly used in submodular maximization publications in ML conferences. The results show the strengths and weaknesses of this work, and support the theoretical guarantees.\n", "weaknesses": "First, the novelty of the work is not clear to me. The algorithms and proof techniques are similar to previous works and are well-known in the literature. Second, exponential time algorithms are not practical in most cases, and I do not agree with the reasons provided in this work. Third, the results for Regularized SCP are good, but less interesting compared to the rest of the results in this work.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments on the paper.\n\nIn this paper, we do use a variety of techniques inspired by those found in literature on the cardinality constrained submodular maximization problem (SMP). However, a few examples of components of our algorithms and analyses that are particularly distinct from existing approaches for SMP are: (i) In many algorithms for SMP, the size of the optimal solution is known to be beneath an input budget. This value is used in many algorithms including ones that inspired our algorithms such as the stochastic greedy algorithm of Mirzasoleiman et al. (inspired stoch-greedy-c), and the streaming algorithm of Alaluf et al. (inspired stream-c). In stoch-greedy-c we use a method of adaptively guessing the size of the optimal solution $|OPT|$ throughout the algorithm in order to determine how many samples are needed at each iteration. (ii) Theoretical guarantees for the regularized submodular maximization problem [Harshaw et al.] take an unusual form that is not a typical approximation guarantee. In order to convert these algorithms to ones for the RSCP (convert-reg), we had to use a technique of distorting the function $f$ and then giving it to a regularized submodular maximization subroutine. \n\nWe agree that exponential time algorithms are usually impractical. As described in the paper in Section 2.2, it has previously been shown that for general SCP when $f$ is not assumed to be monotone it is not possible for an algorithm to guarantee that its returned solution satisfies $f(X)>\\tau/2$ in polynomially many queries of $f$ assuming the value oracle model [Crawford, 2023]. Therefore, in order to have $f(X)$ be nearly feasible, i.e. reach $(1-\\epsilon)\\tau$, we propose stream-c which requires an exact solution to submodular maximization on an instance of size $O(|OPT|/\\epsilon^2)$. When $|OPT|$ is small or in other restricted settings, stream-c may be a reasonable choice."}]

Author rebuttal:

Meta-review: All reviewers appreciate the theoretical improvement of the results for several variants of the important submodular cover problem. The authors are strongly advised to improve the presentation, as suggested by the reviewers.
Decision: Accept (poster)