acceptodds
Under review as a conference paper at ICLR 2027

Fully Dynamic Regularized Submodular Maximization with Polylogarithmic Update

Abstract

Regularized submodular maximization provides a principled framework for cost-aware subset selection in machine learning and has attracted substantial research attention. Meanwhile, fully dynamic submodular maximization has received increasing attention for settings in which elements may be inserted or deleted over time. However, existing fully dynamic algorithms are designed for nonnegative submodular objectives and therefore do not apply to potentially negative regularized objectives, while existing algorithms for regularized submodular maximization do not support arbitrary deletions. To fill this gap, we study regularized submodular maximization under a cardinality constraint in the fully dynamic setting. We propose a novel randomized algorithm, BatchReg, that achieves an approximation ratio of under the commonly adopted regularized approximation notion, while using expected amortized oracle queries per update, where is the maximum number of active elements and is the cardinality constraint. To the best of our knowledge, this is the first algorithm to achieve a nontrivial approximation guarantee for fully dynamic regularized submodular maximization with polylogarithmic update complexity. We further conduct extensive experiments on the maximum coverage problem using real-world datasets, and the results demonstrate that our algorithm maintains high-quality solutions while supporting efficient dynamic updates.

Primary area:
optimization
Keywords:
submodular maximization, fully dynamic algorithm, subset selection, data summarization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_N4BDOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies cost-aware submodular maximization under a cardinality constraint when elements can be inserted and deleted. BatchReg maintains a feasible solution with a regularized approximation guarantee and polylogarithmic expected amortized value-oracle query complexity. The guarantee assumes that the update sequence is independent of the algorithm's random choices. The algorithm groups candidates by distorted marginal gain and cost, selects filtered random batches, and reconstructs affected parts of a layered data structure. Experiments on maximum coverage using Slashdot compare solution values and oracle queries with two streaming algorithms that restart after deletions.

Critical strengths
  1. The paper addresses a gap between regularized streaming algorithms and fully dynamic submodular maximization. Supporting both insertions and deletions while maintaining a regularized approximation guarantee with polylogarithmic expected amortized query complexity is a useful theoretical result.

  2. The algorithm's components address concrete difficulties in dynamic maintenance. Joint bucketing accounts for differences in cost among elements with similar distorted gains. Filtered batch selection checks that accepted elements still meet the gain threshold, while suffix reconstruction confines rebuilding to the affected part of the layered structure.

Critical weaknesses
  1. The paper does not report batch-size statistics or the estimator's share of total queries. These measurements would clarify the practical cost of batch selection.

  2. Figure 1 omits solution sizes and best-singleton output frequency. It is therefore unclear whether the tested cardinality limits substantially affect the solutions.

  3. Both baselines restart after every deletion. This provides a useful reference, but a maintenance heuristic and wall-clock measurements would give a fuller picture of practical efficiency.

  4. The experiments use one graph, a fixed active window, and random deletions, without reporting variation across independent runs. The empirical evidence for performance across different settings remains limited.

Questions for authors
  1. In Figure 1, how many elements does BatchReg typically select? Does it often return the best singleton? I could not tell whether the cardinality limit affects the solutions in these experiments.

  2. Both baselines restart after every deletion. How much of the reported advantage remains against a baseline that rebuilds less often? A wall-clock comparison would help put the query reductions in context.

  3. How much of the total query count comes from batch-size estimation? Does the estimator usually process just one candidate, or are larger batches common?

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

The paper studies fully dynamic regularized submodular maximization under a cardinality constraint. That is maximizing f(S)−ℓ(S)f(S)-\ell(S) when ff is a monotone, normalized submodular function and ℓ\ell is a normalized modular function. In the standard fully dynamic model, elements may be inserted into or deleted from the current ground set, and the algorithm is required to efficiently maintain a high-quality solution after every update. There are two aspects to this optimization problem, one is the utility of the solution at each update time and the other is the number of function evaluation queries being used. BatchReg achieves E[f(St)−ℓ(St)]≥((3−5)/2−ϵ)f(Ot)−ℓ(Ot)\mathbb{E}[f(S_t)-\ell(S_t)]\ge ((3-\sqrt{5})/2-\epsilon)f(O_t)-\ell(O_t) with poly(log⁡n,log⁡k,1/ϵ)\mathrm{poly}(\log n,\log k,1/\epsilon) expected amortized oracle queries per update, assuming an oblivious update sequence.

Critical strengths

The problem is well motivated and relevant to the submodular optimization community. The introduction does a good job positioning the paper and explaining the gap between existing streaming and fully dynamic results.

The main theoretical guarantee is meaningful. The algorithm supports both insertions and deletions while maintaining a constant regularized approximation guarantee with expected amortized query complexity that is polylogarithmic in both nn and kk.

The technical overview identifies a concrete difficulty: elements with similar distorted gains can contribute very different amounts to the original objective. This gives a clear motivation for jointly grouping elements by gain and cost.

Critical weaknesses

The conceptual novelty is modest, and much of the method is inherited from previous work, such as Banihashem et al. (2023). I am not an expert in the dynamic setting, but joint cost/gain bucketing and filtered selection seem like natural modifications.

I understand that this is primarily a theory paper. However, the authors claim extensive experimental results, while the experimental section is very limited and provides little additional evidence of practical significance. Specifically, the evaluation covers only one network, one cost range, and one update scheme. The comparison also relies on baselines that are rebuilt after every deletion. See my comments in the questions section.

A minor presentation comment: Section 4 introduces a large amount of notation that is difficult to keep track of. A compact notation table and a clearer breakdown of the algorithm’s components would improve accessibility.

Questions for authors
  1. Could you comment on the number of oracle queries reported in the experiments? I do not find the current comparison very informative about practical efficiency, since the baselines are naive adaptations that require many oracle queries by design.

  2. Could you please add a baseline that reruns static cost-scaled or distorted greedy after every update? This would help us compare solution quality with a strong static baseline.

  3. It is interesting that the objective-value gap in favor of your algorithm grows with kk. Could you please comment on this? I would have expected smaller values of kk to be more challenging.

  4. Could you please describe settings that could push your algorithm toward its worst performance, in terms of solution quality or oracle-query complexity?

  5. What is the main conceptual contribution beyond extending the Banihashem et al. (2023) framework with cost bucketing, filtered sampling, and standard regularized threshold analysis? Which step of the algorithm or proof best demonstrates this contribution?

2 comments
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

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 so, we would sincerely appreciate it if you could consider increasing your rating.

We would be very happy to provide any further clarification.

Best regards

Thank you for the rebuttal and for taking the time to address my comments and revising the manuscript. Most of my comments have been addressed. My remaining uncertainty concerns the significance of the result and the novelty of the approach. As I noted, I am not very familiar with the techniques used in this area and therefore cannot confidently assess these aspects.

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

The submitted paper studies the problem of maximinizing a regularized monotone submodular function subject to a cardinality constraint in the fully dynamic settting (during each time step an element is either inserted or deleted and one wants to maintain a "good" solution using an algorithm with a "fast" update time). Regular means that we are optimizing a submodular function achieved by f(S)- l(S) where f is a monontone submodular function and l is a modular function. This in particular means that f(S) - l(S) may not be nonnegative (and rules out standard approximation guarantees)

The paper gives the first constant (3-sqrt(5))/2 approximation algorithm (where approximation is defined appropriately) with amortized expected polylogarithmic update time.

The update time is kind of the best (up to the polyonomial) except that it is randomized and amortized. It is unclear whether the constant is tight (it more appears due to the use of some similar techniques as prior papers achieve the same guarantee).

The paper also presents some preliminary experiments where the algorithm shows promising guarantees and update times.

Critical strengths

It is a solid theory result to achieve the great update time (albeit amortized) and at the same time maintain a constant-factor guarantee.

Critical weaknesses

The paper fails to excite me. The problem is a little too exotic (fully dynamic and regular submodular function), and there is little evidence that the obtained theoretical result is tight.

Coupled with this is heavy writing (see e.g. beginning of Section 4.1) and the reader gets few takeaways or general insights apart from the improved statements.

I would rank the experiments as very preliminary. The data set doesn't seem to allow for much more solutions when k grows significantly, which seems a little odd.

Questions for authors
  • What about other datasets in experiments? Also the setup seems not ideal to me. If I understand it correctly you start with a graph with average degree ~20 and then you put a penalty l(u) value to be between 50 and 500 for every vertex. That seems to make a good fraction of the vertices "useless" even as singletons.

  • Is there any metric that shows that regularized submodular objective is much better than submodular? It seems that the cardinality constraint and the penalty is achieving similar effects

2 comments
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

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 so, we would sincerely appreciate it if you could consider increasing your rating.

We would be very happy to provide any further clarification.

Best regards

Thanks for your careful responses. My assessment is that this is a borderline paper.

Comments on the paper

1 comment

Dear Reviewers and Area Chair,

Thank you again for your careful and insightful reviews. We appreciate your time amid this busy discussion period. We hope our responses have sufficiently addressed your questions and concerns. Should our clarifications resolve the issues you raised, we would be grateful if you could kindly reconsider your evaluation of our paper.

Please feel free to let us know if you require any further information or 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.