- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes a consistent algorithm for dynamic submodular maximization. Previous algorithms with theoretical analysis only apply to the monotone objective case. The main contribution of this work is proposing an algorithm with theoretical guarantees for the non-monotone objective case and achieving update complexity that is independent of active set size.
The proposed algorithm claims to achieve O(\log k / \epsilon^2) consistency, (0.1716 - \epsilon)) approximation, and a update complexity O(k^2 \log^4 (k/\epsilon) + (k/ \epsilon^2) \log^2 (k/ \epsilon)) amortized.
Critical strengths
The paper makes substantial theoretical advancements. The results on non-monotone objective is especially striking. The results on update complexity is also substantial (removing dependency on n), but its high powers of k make it not necessarily always computationally preferable. Overall, the theoretical results are significant because they provide a combination of desirable guarantees that previous work was unable to achieve jointly.
The proposed methodology is technically sophisticated. It extends existing techniques for consistent dynamic submodular maximization to non-monotone objectives while achieving efficient update complexity.
Critical weaknesses
The proposed algorithm represents a trade-off between multiple qualities; in particular, solution quality versus number of queries for example, as seen in the experimental results against DynamicNM. This is not an inherently bad trait given the theoretical nature of the work, but it suggests that the said trade-off needs careful justification and motivation. Specifically, the practicality of the method can be better supported with a more compelling application-specific demonstration. The experiments focus solely on MaxCut, which is appropriate for non-monotonicity. However, it does not provide a natural setting where consistency is preferred. A task like video summarization from Banihashem et al., (2023) can be helpful in demonstrating this.
While the theoretical results are valuable, the algorithmic contribution requires more deliberation. See Questions.
Questions for authors
Could the authors more explicitly characterize the algorithmic novelty relative to Dutting et al. (2026)? While the paper already argues that direct application of the Dutting et al. framework to the non-monotonic setting would be problematic and detailed the changes made, it is unclear which components of those changes are fundamentally new algorithmic ideas and which are adaptations of existing techniques.
Follow-up on Our Responses
Dear Reviewer,
Thank you again for your careful and thoughtful review. We understand that this is a busy time, and as the discussion period is coming to a close, we wanted to briefly follow up. We hope our responses have adequately addressed your questions and concerns. If our clarifications have resolved the issues you raised, we would sincerely appreciate it if you would consider revisiting your overall assessment of the paper.
We would be very happy to provide any further clarification.
Best regards