Dynamic Non-monotone Submodular Maximization

Summary

This work studies non-monotone submodular maximization subject to a cardinality constraint in a fully dynamic setting, i.e., maintaining a good solution as elements are inserted and deleted from the "current" ground set. Studying non-monotone submodular maximization in this model is the natural follow-up to the works of: - Monemizadeh (NeurIPS 2020): $(0.5 - \varepsilon)$-approximation for *monotone* dynamic submodular maximization with amortized update time $O(k^2 \varepsilon^{-3} \log^{5} n)$. - Lattanzi et al. (NeurIPS 2020): $(0.5 - \varepsilon)$-approximation for *monotone* dynamic submodular maximization with amortized update time $O(\log^4(k) \log^2 (n) / \varepsilon^{7})$. - Chen and Peng (STOC 2020): proves query complexity lower bounds for approximation ratios strictly greater than $0.5$ for monotone dynamic submodular maximization. Gives $(1-1/e-\varepsilon)$-approximation for "insertion-only" streams for matroid constraints. This work gives a $(1/8-\varepsilon)$-approximation for the *non-monotone* fully dynamic cardinality-constrained problem with amortized query complexity $O(\varepsilon^{-3} k^3 \log^3 n \log k)$ queries per update. The proposed algorithm builds on connections to thresholding algorithms for *monotone* submodular maximization and then altering these solutions to get guarantees for non-monotone functions. The authors include experiments and compare their algorithm to the Simple-Streaming in Feldman-Karbasi-Kazemi (NeurIPS 2018).

Strengths

- Gives $(1/8 - \varepsilon)$-approximation for fully-dynamic non-monotone submodular maximization subject to a cardinality constraint, answering an open question in Chen-Peng (STOC 2020). - Builds on thresholding techniques commonly used for monotone submodular maximization. This helps connect the toolkits for each problem type. Some missing references on line 54 when discussing thresholding: 1. "Submodular Optimization in the MapReduce Model" (Liu-Vondrak, SOSA 2019) 2. "Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity" (Fahrbach-Mirrokni-Zadimoghaddam, SODA 2019) 3. "Fully Dynamic Algorithm for Constrained Submodular Optimization" (Lattanzi et al., NeurIPS 2020) 4. "Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint" (Chen-Kuhnle, arXiv:2009.01947, 2022)

Weaknesses

- The biggest weakness of this paper are the experiments. They almost check all of the boxes, but they aren't very motivating. This paper investigates: 1. video frame summary on the entire set, which doesn't use any aspect of streaming but is a reasonable starting place to show what the algorithms output. 2. sliding window model of length $W$, which is fully dynamic but not in the most interesting way (though possibly the most practical way). 3. only compares against the Sample-Streaming algorithm of Feldman-Karbasi-Kazemi (NeurIPS 2018). It would be nice to include comparisons to the three papers discussed in the abstract, too, even though they are for monotone submodular functions. - Given that there is randomness in this paper's Update algorithm (line 4 of SubsetSelection), it is important for these experiments to be averaged over several trials with standard deviation error bars. Both the oracle calls and objective value plots appear somewhat noisy and non-monotone.

Questions

**Questions** - [line 74] This is less of a question and more of a comment: The authors are correct in questioning whether thresholding works in a non-monotone setting when a randomly sampled set is added to the current solution, i.e., $f(S_t) \ge k \tau$. See Chen-Kuhnle (2022) for an example where this property does not hold. However, also see Chen-Kuhnle (2022) and Fahrbach-Mirrokni-Zadimoghaddam (ICML 2019, arXiv:1808.06932v3) for a method to circumvent this problem. **Typos and suggestions** - [line 27] Two relevant missing works for non-monotone submodular maximization: 1. "Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity" (Fahrbach-Mirrokni-Zadimoghaddam, ICML 2019) 2. "Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint" (Chen-Kuhnle, arXiv:2009.01947, 2022) - [line 38] suggestion: The description of the dynamic setting "... set of elements that are inserted but not deleted after their last insertion time till time $t$" is not clear and should be improved. The description in Section 1.1 is better, but could still be improved (i.e., saying that $V_t$ is the set of ``active'' elements at time $t$). - [line 71] typo: "The only such a result" --> "The only such result" - [line 184] suggestion: Consider using $\text{Insert}_{i}(v, \tau)$ to avoid a double subscript. - [line 313] typo in Figure 3 description: "submdoular"

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

NA

Summary

In this paper, the authors consider the non-monotone submodular maximization problem under the cardinality constraint and dynamic model. Here, the dynamic model means that the ground set of the submodular function changes every time step where one element is inserted into or deleted from the ground set, and the update is controlled by an oblivious adversarial. They show a reduction from non-monotone case to monotone case, and then obtain a dynamic algorithm with (8+eps)-approximation ratio. They further test their algorithm on some real-world data sets.

Strengths

1. In the dynamic setting, they provide a constant approximation algorithm for non-monotone submodular maximization problem under cardinality constraint. 2. The reduction between non-monotone dynamic algorithm and monotone dynamic algorithm shows some connection between these two cases.

Weaknesses

1. I’m confused with the relation between parameter $\tau$ and the results in theorem 1.2. The current description looks like there is no relationship between these two. But, if $\tau$ is large enough, it seems we can satisfy definition 1.1 by keeping $S_t$ an empty set. For example, we can assume without loss of generality $f(u)\leq 1$ for any u and set $\tau =1$. In this case, we have a trivial $\tau$-thresholding dynamic algorithm. Then, what does theorem 1.2 look like? 2. Although the paper tries to show the connection between monotone case and non-monotone case by the reduction theorem, it seems that this connection is weak. Firstly, to show a monotone dynamic algorithm is \tau-thresholding algorithm is not an easy task, so that it is not easy to use this reduction. More importantly, the reduction does not mean that a better monotone dynamic algorithm can imply a better non-monotone dynamic algorithm (comparing to the reduction result in [35]). The better approximation ratio of the monotone dynamic algorithm does not help. It is also not clear whether the lower amortized update time can help or not. The author's response has clarified my main concern here, so I would like to raise my score.

Questions

See weakness 1

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes

Summary

The paper studies the dynamic submodular maximization problem and gives the first efficient dynamic algorithm that maintains a constant approximation solution. In the problem of dynamic submodular maximization, there is a sequence of updates (insertions/deletions) of ground set element, and one wants to maintain a subset (of size at most $k$) that obtains the maximum possible function value. Previous work provide tight approximation guarantee when the function is monotone, while this paper extends to non-monotone submodular function (albeit with worse approximation guarantee). The main result of this paper is an $(8+\epsilon)$ approximation algorithm with $\mathsf{poly}(k, \log n, \epsilon^{-1})$ amortized update time per update. The algorithm is obtained through a clever reduction from dynamic algorithms for monotone function (and satisfies certain threshold property). The overall idea is to simulate the monotone threshold algorithm twice and combines double greedy or random sampling. The first run guarantees the marginal is small for the second algorithm, if it works bad. Besides theoretical results, the author also conduct empirical study and verify its practicality. -------------- I have read the author's response and I keep my positive evaluation of the paper.

Strengths

The paper provides the first sublinear dynamic algorithm for non-montonne submodular maximization. The theoretical contribution is novel and interesting from my perspective. The experiment result is also promising.

Weaknesses

There is no major weakness. Some minor issues are listed below. (1) Line 201, it seems one can directly use the double greedy algorithm to extract $S_1'$, I don't see why you mention the 3-approximation deterministic algorithm. (2) Line 242, delete "what" (3) The related work is quite extensive, there are a few missing reference that are relevant to the paper. The first two reference below seems appear on Arxiv later than NeurIPS submission, but I encourage the author to add the reference in the later version. The third reference gives lower bound for white box dynamic submodular maximization. [1] Dynamic Algorithms for Matroid Submodular Maximization. Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh [2] Fully Dynamic Submodular Maximization over Matroids. ICML 2023 Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Morteza Zadimoghaddam [3] Dynamic influence maximization. NeurIPS 2021 Binghui Peng

Questions

.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

.

Summary

The authors consider an submodular non-monotone optimization problem in fully dynamic setting. The authors propose a 8+epsilon approximation algorithm by combining several existing methods.

Strengths

- The technique behind the proposed algorithm is interesting. - Proven approximation guarantee. - A nice continuation of the existing literature in submodular optimization.

Weaknesses

- 8 + epsilon is a rather weak approximation guarantee. - The other algorithm with 10 + epsilon approximation uses a weak algorithm, so the algorithm is largely pedagogical. - Presentation needs improvement.

Questions

The authors should improve the presentation of the paper - The abstract is probably better without references to Neurips or STOC - Line 20-22. Provide citations. - Page 2: remove grey outline boxes. - Line 51, remove bolding - Property 2. queries is not defined. - Reword/remove metatheorem. - Line 98: . That is -> , that is, - Line 178: algorithms -> algorithm - Named paragraphs starting on Page 5 need connecting text. - There is a follow-up paper of [7] that derandomizes the algorithm of [7] (and keeping 2-approximation). Can this algorithm used?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

Probably the biggest limitation of the method is a rather weak approximation guarantee. It is not clear whether a stronger approximation is possible. This is not discussed by the authors.