Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints

Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. Below, we will respond to the concerns you have raised in Weaknesses.

---

Weaknesses:

---

W1: The paper could benefit from a more thorough analysis of the scalability of the proposed algorithms. As the scalability of the algorithms are improved compared to prior continuous algorithms theoretically, evaluating the algorithms on larger datasets would provide deeper insights into their performance in practice.

Thank you very much for your constructive suggestion.

Scaling up the proposed algorithms to larger datasets and a wider range of subset selection tasks is indeed one of our long-term goals. For example, similar to [1,2], exploring how to use distributed architectures to accelerate our algorithms or handle extremely large-scale datasets is something we are actively considering.

Furthermore, we would like to emphasize that the experiments conducted in this paper are highly representative:

First, to demonstrate the scalability of our proposed algorithms, we have tested them on multiple datasets and various tasks, where they consistently show strong performance in terms of both efficiency and effectiveness compared to previous methods.

Second, it is worth noting that in the video summarization task, the scale of data we are dealing with is already significantly larger than that of most known subset selection tasks. For instance, in the V2 video, which has a duration of 7 minutes and 45 seconds (465 seconds), with 30 frames per second, we have effectively selected 20 representative frames from nearly 13,900 frames.

References

[1] Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):8330–8373, 2016.

[2] Mokhtari, A., Hassani, H., and Karbasi, A. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp. 3616–3625. PMLR, 2018b.

Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. In the following, we will address the concerns you have raised in Questions.

---

Questions:

---

Q3:Why can we assume that $x(T + 1)$ is on the boundary of the domain (see details in "Theoretical claims")?

Thank you very much for your question.

Firstly, this paper primarily focuses on monotone set functions $f$. Secondly, as noted in Theorem 1 (2), we have shown that when $f$ is monotone, its multinoulli extension is also monotone. Specifically, for any two feasible vectors $(x_{1},\dots,x_{K})$ and $(y_{1},\dots,y_{K})$, if $x_{i}\ge y_{i},\forall i\in[K]$, then $F(x_{1},\dots,x_{K})\ge F(y_{1},\dots,y_{K})$. Thus, for any feasible vector

$(x_{1},\dots, x_{K})$, we have $F(\frac{x_{1}}{u_{1}},\dots,\frac{x_{K}}{u_{K}})\ge F(x_{1},\dots, x_{K})$ where $u_{i}=||x_{i}||_1$ for any $i\in[K]$.

Note that ($\frac{x_{1}}{u_{1}},\dots,\frac{x_{K}}{u_{K}}$) lies on the boundary of the constrained domain $\prod_{k=1}^{K}\Delta_{n_{k}}$.

Therefore, even if the output of Algorithm 1 is not on the boundary, we can first normalize this output vector to the boundary and then use Algorithm 2 to round the normalized output vector. This process will not decrease the function value for the monotone set objective function $f$. This is why we assume $x(T+1)$ is on the boundary-because we can always increase the function value by normalizing the output vector.

Q2: Why is it an issue to select the same element when rounding as discussed in Remark 9? Isn't the resulting set simply a union of the elements obtained. What is the motivation for using a rounding-without-replacement method?

Thank you very much for your question. we will explain Q2 with a simple example.

Considering $V=[3]$ and we will select at most 2 elements from $V$. Given $p=(1/3,1/3,1/3)$, if we use the definition of multinoulli extension to round $p$, we might end up selecting element 3 twice. This would result in a final subset containing only element 3. Since this paper focuses on monotone set functions $f$，we naturally know that randomly adding element 1 or element 2 to the resulting subset (which contains only element 3) will increase the function value without violating the constraints. This illustrates the issue of selecting the same element over multiple selections.

To address this, we propose a rounding-without-replacement method. This ensures that the final resulting subset contains the maximum number of distinct elements, thereby avoiding the pitfalls of multiple selections of the same element and maximizing the function value more effectively.

Q1: Would using a similar implementation of the Hessian-vector product as the one described in Section 4.1 of (Karbasi et al., 2019) also lead to better computational and memory complexity for your proposed algorithm? If yes, what is the resulting complexity?

Thank you very much for your suggestion. This is a very good question.

We have also considered the same question. However, we noticed that in Section 5 of (Karbasi et al., 2019), when dealing with discrete submodular maximization, they did not use the Hessian-vector product described in Section 4.1. Instead, they employed a Hessian estimation method similar to the one used in our paper. Therefore, we suspect that the Hessian estimation method in Section 4.1 of (Karbasi et al., 2019) may not be directly applicable to our multinoulli extension.

The primary issue with using the Hessian-vector product described in Section 4.1 of (Karbasi et al., 2019) is that it involves computing $\nabla\log(p(z;y))$, which may require differentiating some $log(p)$, where $p\in(0,1)$ is a parameter of interest. Note that $(log(p))^{'}=\frac{1}{p}$ and $\frac{1}{p}$ is unbounded on the interval $(0,1)$. Therefore, we thimnk directly applying the Hessian-vector product from Section 4.1 of (Karbasi et al., 2019) to our multinoulli extension might violate the bounded gradient and smoothness assumptions in (Karbasi et al., 2019).

---

Other Comments Or Suggestions:

---

Thank you very much for your comments and suggestions. We will carefully address all the proposals and correct any typos in the final version.

---

Claims And Evidence:

---

• We will add a detailed remark after Remark on Table 2, specifically after line 153, to discuss the comparison of query complexities between multinoulli-SCG and distorted local search under different values of $n$. Moreover, in this additional remark, we will also explicitly point out that the query complexity of Distorted-LS-G uses a different error term $\epsilon^{'}$, which is related to $\epsilon$ of Multinoulli-SCG by the transformation $\epsilon' = \epsilon / OPT$.
• We will remove the inappropriate claim from "Our Contributions" in RHS in line 94, i.e.," match the information-theoretic lower"

Thank you very much for your careful reading and constructive feedback. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in Questions and Weaknesses.

---

Weaknesses:

---

W1: The multinoulli extension is advantageous specifically for weakly submodular functions, and so doesn't seem useful to those who are primarily concerned with submodular objectives.

Thank you very much for your question.

First, it is important to note that when $\alpha=\gamma=\beta=1$, the $(\gamma,\beta)$-weakly submodular or $\alpha$-weakly DR-submodular functions considered in this paper will degenerate into standard submodular functions. Thus, the class of set functions we study is a broader category that includes standard submodular functions as a special case.

Moreover, when $\alpha=\gamma=\beta=1$, the approximation ratio $(1-e^{-\alpha})$ or $(\frac{\gamma^{2}(1-e^{-(\beta(1-\gamma)+\gamma^2)})}{\beta(1-\gamma)+\gamma^2})$ yielded by Multinoulli-SCG will equal $(1-1/e)$. This means that our algorithm can guarantee an optimal $(1-1/e)$-approxiation for submodular maximization over partition constraints, which is consistent with the state-of-the-art algorithms for submodular maximization problems.

As a result, our proposed Multinoulli-SCG algorithm not only offers advantages for weakly submodular functions but also guarantees the same approximation performance as the best existing algorithms for submodular maximization.

---

Questions:

---

Q1:Could you give more detail about the issues with the multi-linear extension being used for weakly submodular functions?

Thank you very much for your question.

At first, it is important to note that we have provided a detailed introduction to the multi-linear extension in Appendix A.1 (lines 680-714), where we also discussed the main challenges in applying the multi-linear extension to weakly submodular functions

Here, we will briefly restate the key issue.

Before that, we call the defintion of multi-linear extension, that is,

For a set function $f:2^{V}\rightarrow R_{+}$ where $|V|=n$ and $V:=[n]$, we define its multi-linear extension as

$

	G(x)=\sum_{\mathcal{A}\subseteq V}\Big(f(\mathcal{A})\prod_{a\in\mathcal{A}}x_{a}\prod_{a\notin\mathcal{A}}(1-x_{a})\Big)=E_{\mathcal{R}\sim x}\Big(f(\mathcal{R})\Big),

$where$x=(x_{1},\dots,x_{n})\in [0,1]^{n}$and$\mathcal{R}\subseteq V$is a random set that contains each element$a\in V$independently with probability$x_{a}$and excludes it with probability$1-x_{a}$. We write$\mathcal{R}\sim x$to denote that$\mathcal{R}\subseteq V$is a random set sampled according to$ x$.

From the previous definition, we can view multi-linear extension $G$ at any point $x\in[0,1]^{n}$ as the expected utility of independently selecting each action $a\in V$ with probability $x_{a}$. With this tool, we can cast the previous discrete subset selection problem (1) into a continuous maximization which learns the independent probability for each element $a\in V$, that is, we consider the following continuous optimization:

$

\max_{x\in[0,1]^{n}} G(x),\ \ \text{ s.t.}\ \  \sum_{a\in V_{k}}x_{a}\le B_{k},\forall k\in[K]

$where$G(x)$is the multi-linear extension of$f$.

It is important to note that, if we round any point $x$ included into the constraint of the previous multi-linear maximization problem by the definition of multi-linear extension, there is a certain probability that the resulting subset will violate the partition constraint of the original discrete subset selection problem.

---

Q2: It was mentioned, and a citation was provided, that the multi-linear extension has issues when being used for weakly submodular objectives. Because this is an important problem that motivated the paper, I think that they should go in to further depth in the main paper about why this is the case.

Thank you very much for your insightful question.

Indeed, the limitation of the multi-linear extension when applied to weakly submodular functions is a significant motivation for our work. Due to space constraints, we have detailed these limitations in Appendix A.1, where we discuss the specific challenges in using the multi-linear extension for weakly submodular functions, as shown in the answers in Q1.

Given the importance of this issue, we will add a small subsection at the end of Section 3 to further discuss the limitations of the multi-linear extension and how our proposed multinoulli extension overcomes these challenges. This will provide a more detailed explanation directly within the main paper, addressing your concern more comprehensively.