Fair Submodular Cover

The motivation for considering FSC is unclear. The authors only say that FSM has been well studied while FSC has not. This can not be a good motivation

What are the motivations for FSC, e.g., real-world applications?

We believe that FSC has broad applications within machine learning, and in the response to all reviewers and ACs we have included a detailed discussion on four different important applications of FSC. The applications include data summarization, data subset selection for training, neural network pruning, and influence in social networks. For more details, see https://openreview.net/forum?id=ULorFBST6X&noteId=vZ496FjX3r; a discussion of these applications has further been added to the paper in Appendix B.1 and is highlighted in blue.

The experiments demonstrate the advantages of the discrete algorithms on the FSC problem compared to the standard greedy algorithm; however, the solutions obtained by the discrete algorithms include many more elements. Moreover, the experiments lack the presentation of the effectiveness of the continuous algorithm.

The continuous algorithm proposed in the paper theoretically outperforms the discrete algorithms, while the experiments only showcase the performance of the discrete algorithms. Are there any experimental results available for the continuous algorithm?

Continuous algorithms in submodular optimization can have relatively high query complexity because we do not necessarily have direct access to the multilinear extension, and instead have to make many noisy queries to $f$ and apply concentration bounds in order to approximate it (See Definition 3 in Section 1.2). For instance, with $\epsilon = 0.05$, $n = 5000$, and $\kappa = 10$, a single estimation of the multilinear extension value in Line 8 of the Decreasing-Threshold-Procedure (DTP) in Algorithm 3 requires approximately $5.33 \times 10^5$ queries. The total number of queries can reach up to $10^{12}$. In fact, many prior works on the multilinear extension have not included experiments due to the high computational cost. However, we agree with the reviewer that it would be interesting to know if the continuous algorithm can produce solutions of lower cardinality compared to our other algorithms, and so we have performed additional experiments evaluating our continuous algorithms heuristically on smaller problem instances.

Given the high query complexity and the limited time available during the rebuttal period, we take 5 samples per estimation in Line 8 of the DTP and test the algorithms on a subgraph of the Twitch dataset with $n = 2000$ on the instance of maximum coverage. The results comparing different algorithms are included in the updated submission PDF (appendix, highlighted in blue). Notice that by taking fewer samples than is theoretically needed, this could potentially hurt the performance of the continuous algorithm. Despite this handicap, the cost of the continuous algorithm is smaller than the discrete algorithms under fairness constraint which includes the GREEDY-Fair and THRES-Fair algorithms. While the fair algorithms do still generally produce solutions of higher cost compared to the greedy without fairness constraint, this is to be expected since in order to be fair our algorithms have to select elements that are not optimal from the perspective of $f$ value.

We have added these experiments into Appendix G of the updated version of our manuscript.

The studied problem is theoretically interesting, but it is a little incremental. One needs to provide convincing motivation for the problem. It looks that the studied problem only adds an extra constraint to the classical submodular cover problem. The introduction section does not give a specific motivation for the studied problem.

We are confident that FSC has broad applications within machine learning, and in the response to all reviewers and ACs we have included a detailed discussion on four different important applications of FSC. The applications include data summarization, data subset selection for training, neural network pruning, and influence in social networks. For more details, see https://openreview.net/forum?id=ULorFBST6X&noteId=vZ496FjX3r; a discussion of these applications has further been added to the paper in Appendix B.1 and is highlighted in blue.

It is true that FSC is the classical submodular cover problem with an additional constraint for fairness. However, we believe the problem is important both in terms of its broad range of applications and from a technical perspective. The maximization of a submodular function with a matroid constraint has received significant attention, but to the best of our knowledge, this work is the first to investigate a submodular cover problem with a matroid-type constraint. To tackle this problem, we introduced the novel concept of the $\beta$ matroid extension and proved an insightful result in Lemma 2, which establishes the relationship between a fairness matroid and its $\beta$-extension.

There is no lower bound known in the paper. Namely, there is no lower bound for the bicriteria approximation. This may not be a big problem since these fair constraints are usually hard. But, one still needs to show how good is the trade-off obtained by the paper.

Because set cover is a special case of fair submodular cover (FSC), by the result of Feige (1998) it is not possible to achieve a $(1-o(n)\ln(n))$ approximation to FSC unless NP has "slightly superpolynomial time algorithms". If we set $\epsilon=1/n$, our continuous algorithm (Algorithm 2) for FSM with the converting algorithm (Algorithm 1) achieves a $((1+\alpha)\ln(n)+1,1-7/n)$ bicriteria approximation guarantee for an instance of FSC, and so if $\alpha$ is close to 0, then the guarantee is very close to being feasible while having an approximation guarantee close to the lower bound. For other values of $\epsilon$, a lower bound has not yet been developed.

The problem certainly holds theoretical interest. However, I am a bit concerned about whether it will engage the ICLR community. Could the authors provide some real-world applications?

We are confident that FSC has broad applications within machine learning, and in the response to all reviewers and ACs we have included a detailed discussion on four different important applications of FSC. The applications include data summarization, data subset selection for training, neural network pruning, and influence in social networks. For more details, see https://openreview.net/forum?id=ULorFBST6X&noteId=vZ496FjX3r; a discussion of these applications has further been added to the paper in Appendix B.1 and is highlighted in blue.

The authors did not compare the empirical running time of the proposed algorithms with the baselines. The theoretical running time looks horrible, so I wonder how long these algorithms will take in practice.

Generally, the runtime bottleneck for submodular optimization algorithms such as ours is the number of queries to the function $f$. Therefore, both our theoretical and empirical analyses focus on the number of queries to $f$, as is standard in submodular optimization. For GREEDY-Fair and THRES-Fair, the query complexities are $O\left(\frac{n|OPT|\log(|OPT|)}{\epsilon\log(\alpha+1)}\right)$ and $O\left(\frac{n\log(|OPT|)\log(|OPT|/\epsilon)}{\epsilon\log(\alpha+1)}\right)$, respectively. Compare these to the standard greedy algorithm that does not find a fair solution, which makes $O(n\ln(1/\epsilon)|OPT|)$ queries to $f$, so the theoretical runtime of our fair algorithms are similar to those of the greedy algorithm. In contrast, the continuous algorithm has a higher complexity of $O\left(\frac{n(1+\alpha)|OPT|\log^2\left(\frac{n}{\epsilon}\right)\log|OPT|}{\epsilon^4\alpha}\right)$. Our experiments aimed to demonstrate the relative performance of the algorithms rather than emphasize their absolute runtime efficiency, and comparing query complexity is most effective for this purpose. However, all experiments with each parameter configuration were able to run quickly and were completed within a 2-minute runtime.

The difference between the authors' reduction and the existing reduction from general submodular maximization to submodular cover could be elaborated on further.

The standard reduction from an instance of submodular cover (SC) with objective $f$ and threshold constraint $\tau$ to an instance of submodular maximization (SM) with objective $f$ and budget $k$ involves iteratively doing the following procedure: A guess is made for the size of the optimal solution ($|OPT|$) to the instance of SC, and this guess as the budget along with $f$ are input into an algorithm for SM. The procedure is repeated with increasingly large guesses until a solution is found with $f$ value sufficiently close to $\tau$. This process is relatively straightforward since the two problems are dual to each other, and the conversion requires only a flip between the objective and the constraint. A clear description of the process is provided in (Iyer & Bilmes, 2013b).

In contrast, in our fairness setting, the conversion from fair submodular cover (FSC) to fair submodular maximization (FSM) is less clear because of the more complex matroid structure of the fairness constraints. It is important to note that there is currently no existing formulation of SC that incorporates a matroid constraint, nor has any conversion process been developed to address such constraints. To address this, we devised a method where each guess of the size of the optimal solution for the instance of SC is used to construct an extended fairness matroid (we propose the concept of an extension to a matroid in Section 1.2). This matroid is then input as a constraint into a bicriteria FSM algorithm, such as those developed in Sections 3.1 and 3.2. Furthermore, post-processing (Lines 6–12 in Algorithm 1 and Lines 7-13 in Algorithm 4) is required for each guess to ensure the fairness constraint is met, unlike the non-fairness setting where no such post-processing is necessary. A final difference between our fair setting and the general setting is that we are the first to introduce a converting process for multilinear extension algorithms (Algorithm 4).

We have included this discussion in Appendix B.2 of our updated version of the manuscript.

The paper could benefit from a more detailed comparison between their fair submodular maximization algorithms and existing algorithms ... submodular maximization.

First, we note that the fair submodular maximization (FSM) problem can be converted into an instance of submodular maximization with a general matroid constraint, as shown by Lemma 3 in (El Halabi et al.,2020). Therefore, existing algorithms for SM with a general matroid constraint can also be applied to FSM. Such algorithms return a feasible solution to the instance of SM with a matroid constraint, and achieve an approximation guarantee of at best $1-1/e$. However, our goal with our algorithms for FSM is to use them as subroutines in the conversion process, and so we develop algorithms that find sets that are better approximations to the optimal solution than $1-1/e$ but are not necessarily feasible. i.e., we propose algorithms for FSM with bicriteria approximation ratio. To this end, we have developed the notion of an extension of the fairness matroid (see Definition 2 in Section 1.2) and shown that by transferring to this "bigger" constraint we can achieve better objective values. In the case of our continuous algorithm, this means traveling within an extended polytope of the $\beta$-extension of the fairness matroid. This approach enables the $f$ value of the solution set to approach arbitrarily close to the optimal objective.

We have incorporated this discussion into Appendix B.3 of our updated version of the manuscript.