acceptodds
Under review as a conference paper at ICLR 2027

Consistent Algorithms for Dynamic Non-Monotone Submodular Maximization with Efficient Updates

Abstract

Submodular maximization is a fundamental framework for subset selection with broad applications in machine learning and data mining. In many modern applications, however, the underlying data evolves over time, making it desirable to maintain not only a high-quality solution but also a stable one that changes only slightly after each update. Recent work has initiated the study of consistent algorithms for fully dynamic submodular maximization, but existing algorithms are restricted to monotone objectives, and their expected amortized query complexity suffers from an undesirable linear dependence on the maximum number of active elements. In this paper, we address both limitations by developing ConsistentSample, a consistent algorithm for dynamic non-monotone submodular maximization under a cardinality constraint . For accuracy parameter , our algorithm achieves a -approximation with consistency and expected amortized query complexity. To the best of our knowledge, among consistent algorithms for fully dynamic submodular maximization, ours is the first to achieve active-set-independent query complexity and the first to obtain a constant-factor approximation guarantee for non-monotone objectives. As a by-product, for monotone objectives, our framework achieves a approximation with consistency while retaining the same query complexity. We further evaluate our algorithm on the Max-Cut problem using real-world datasets, and the empirical results demonstrate its practical efficiency and stability.

Primary area:
optimization
Keywords:
consistent submodular maximization, non-monotone submodular maximization, dynamic algorithms

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_oYzZOpenReview ↗
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.

Reviewer_TSViOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies consistent algorithms for fully dynamic non-monotone submodular maximization. The authors are the first to achieve query complexity independent of the active-set size and the first to establish a constant-factor approximation guarantee for non-monotone objectives in this setting.

Critical strengths
  1. This paper investigates an important variant of the classical dynamic submodular maximization problem by additionally incorporating algorithmic consistency, which is an interesting and potentially useful consideration in dynamic optimization.
  2. The paper makes significant theoretical contributions. In particular, the proposed algorithms are the first to achieve active-set-independent query complexity and the first to provide a constant-factor approximation guarantee for non-monotone objectives in this setting.
Critical weaknesses
  1. The motivation for introducing consistency is not entirely clear to me. Consider the recommendation system example discussed in the paper. Even in a static setting where the pool of available products remains unchanged, it is often beneficial, and indeed common practice, for platforms to periodically update their recommendations to the same customer. One reason is to promote diversity in recommended items and encourage users to explore a broader range of products on the platform. In this sense, enforcing consistency may, to some extent, conflict with this practical objective. I would appreciate it if the authors could provide additional applications or concrete examples that better motivate the need for consistency, particularly in settings where maintaining a stable solution is more desirable than frequently updating it.

  2. Some assumptions are made without sufficient justification or discussion of their practical implications. For example, the paper assumes that the update sequence is fixed independently of the algorithm's randomness and that each element is inserted at most once. I understand that these may be standard assumptions in the literature, but I believe they still warrant further justification, especially in the context of the motivating applications, such as recommendation systems and data summarization. Consider product recommendation as an example. Recommending a product to customers can directly influence its future inventory or availability, thereby affecting subsequent updates to the set of available products. This introduces a potential dependence between the algorithm's decisions and the future update sequence. Furthermore, a product that becomes temporarily unavailable may later become available again, meaning that the same element could be inserted multiple times. These scenarios appear quite natural in practical applications but are not captured by the current assumptions. I would appreciate a discussion of the extent to which these assumptions are necessary for the theoretical results and how relaxing them might affect the proposed algorithms' approximation guarantees, query complexity, and consistency guarantees.

Questions for authors
  1. I would appreciate it if the authors could provide additional applications or concrete examples that better motivate the need for consistency, particularly in settings where maintaining a stable solution is more desirable than frequently updating it.
  2. I would also appreciate a discussion of the extent to which the aforementioned assumptions are necessary for the theoretical results and how relaxing them might affect the proposed algorithms' approximation guarantees, query complexity, and consistency guarantees.
3 comments
AuthorsOpenReview ↗

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

I want to thank the authors for their clarification, which has addressed most of my concerns. I will raise my rating.

We appreciate your recognition of our work and your valuable feedback.

Reviewer_fKjuOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies (non-monotone) submodular maximization under a cardinality constraint in the fully-dynamic setting

The algorithm maintains a small pool of candidates, it patches its decisions locally instead of restarting, and it rolls out changes gradually. The building blocks are the following. Sampled exchange is the work from Feldman et al. 2018 (Do Less, Get More). Bands are used for guessing the scale. Band sample essentially runs the sampled exchange within one band, and already touches few items. Since they log every trial, they can cheaply re-execute upon deletions, only re-executing after the earliest invalidated record. The clever idea is that they use the sampling not only in the Feldman way to make non-monotone work out, but also to make deletions cheap.

In terms of contributions, they give the first constant-factor approx guarantee and bounded consistency in the fully-dynamic setting, either with active-set-independent (amortized) query complexity or for a non-monotone objective. The algorithmic contribution is especially the deletion horizon, which controls "deletion robustness, update cost, and distance of the next target". For the monotone case, the contribution is improved query complexity.

Experiments show that they are only slightly worse than less consistent algorithms, which do not provide any consistency guarantees.

Critical strengths
  1. As stated in the summary, they are first in these settings: get constant-factor approx, and bounded consistency, and non-monotone.
  2. Novel and clever algorithm: they use the sampling not only in the Feldman way to make non-monotone work out, but also to make deletions cheap.
  3. Experiments show that they're only slightly worse than less consistent algorithms (which do not provide any consistency guarantees).
Critical weaknesses
  1. Experimental validation could much more extensive.
  2. Presentation is a bit dense, but that might just be in the nature of the algorithm
Questions for authors

Could you expand your experimental evaluation?

Comments on the paper

1 comment

Dear Reviewers and Area Chair,

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

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.