Non-monotone Submodular Optimization: $p$-Matchoid Constraints and Fully Dynamic Setting

Thank you for the constructive and encouraging review. We greatly appreciate your positive assessment of the strength and elegance of our algorithm. Below, we address questions and concerns you raised.

The theoretical query complexity includes high-degree polynomial terms ...

We note that the query complexity, although polynomial in $k$, is independent of $n$, the size of the ground set. This makes it practical in many real-world scenarios.

The dynamic model is based on the oblivious adversarial assumption, and its robustness against adaptive attack scenarios has not been fully discussed.

The approximation guarantee of the algorithm does not rely on the oblivious adversarial assumption. However, our current analysis of the query complexity bounds is tailored to the oblivious setting and may not directly extend to scenarios against an adversary with full knowledge of the random bits used in the algorithm. However, we should note that this is a valid assumption in many real-world scenarios, and it is also consistent with prior work in fully dynamic submodular optimization, where, to the best of our knowledge, all existing results assume the same kind of adversarial setting. Nonetheless, robustness against adaptive adversaries is an interesting and important direction for future research in the field. 

The algorithm relies on random sampling to simulate monotone behavior. How sensitive is the performance to the sampling probability q?

The analysis of the algorithm is based on a fixed value for the parameter $q = (p+\sqrt{p^2+p}+1)^{-1}$. We use equalities $\frac{1}{q} - 1 = (1 + c)p$ and $1 - q = \frac{1}{c}$ to get an approximation gurantee of $\frac{c}{(1+c)^2p}\left(\frac{1}{c} - \epsilon \right)$. These equalities hold for the said choice of $q$ and $c=\sqrt{1+\frac{1}{p}}$.

We will clarify this earlier in the paper to avoid ambiguity.

If you feel that our response has adequately addressed your concerns, we would appreciate it if you would possibly raise your score accordingly.

We thank the reviewer for the positive evaluation and for highlighting the importance and quality of our contributions. We are very pleased that you found our paper well-written and technically solid.

We appreciate your helpful feedback and will incorporate your suggestions into our paper.

Specifically, regarding empirical evaluations, while the primary focus of this work has been on the theoretical development, we fully agree that empirical evaluations would further enhance the impact of our work. For the special case of cardinality constraints, we have conducted experiments on real-world datasets (videos from YouTube and Open Video Project for the task of video summarization). We compared our algorithm’s query complexity and submodular value against the state-of-the-art $(8+\epsilon)$-approximation algorithm, and the results showcased the competitive performance of our algorithm. We will include these in the revised version of our paper.

Thank you so much for your positive feedback. We are glad you were satisfied with the clarity, significance, and quality of our paper. We address specific questions and comments below:

Since $f$ can be non-monotone, the assertion ... . Do the results in this work require that the latter hold, or would a more careful application of notations suffice?

Thank you for the question. The stronger assumption is not required, and non-negativity of the function $f$ is sufficient for the analysis to hold, which, as you noted, preserves the generality of the problem. We have made proper adjustments to the notations accordingly.

Algorithm 1: is $A_0$ assigned 0 or $\emptyset$?

The variable $A_0$ is initialized to $\emptyset$. Thanks for catching this.

It'd be nice to see the online approximation quality of the algorithm under various insertion/deletion patterns, or at least a direct comparison to the performances given by Banihashem et. al, 2023.

We acknowledge that empirical results would provide further valuable insight. We have conducted experiments evaluating the performance of our algorithm for video summarization using datasets obtained from YouTube and the Open Video Project. For the special case of cardinality constraint, we benchmarked the total number of query calls and the submodular value of our solution, demonstrating competitive performance compared to [Banihashem et al., 2023]. As per the guidelines, we are unable to provide these during the rebuttal period; however, we will incorporate them in the final version of the paper.

We thank the reviewer for recognizing the importance of our problem and contributions. We are pleased that you found the paper well-written and of high quality, and we greatly appreciate the positive and affirming review.