acceptodds
Under review as a conference paper at ICLR 2027

Fully Dynamic Submodular Maximization over a Matroid with Polylogarithmic Update Time

Abstract

We study fully dynamic maximization of a normalized monotone submodular function subject to a matroid constraint of rank at most . For every oblivious sequence of insertions and deletions and , our randomized algorithm maintains a feasible set satisfying at every fixed time . The total number of value- and independence-oracle queries is for every realization of the random choices, giving polylogarithmic amortized query complexity for fixed . Our approach combines a deletion-tolerant exchange certificate with deterministic hierarchical rebuilding. The certificate charges the optimum to the frozen weights of retained and deleted acceptances. Exact truncated sampling controls expected deletion loss and leaves small residuals for later rebuilding levels, yielding the approximation and query guarantees.

Primary area:
optimization
Keywords:
submodular maximization, dynamic algorithm, matroid, polylogarithmic update

Reviews

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

The submitted paper studies the problem of maximizing a monotone submodular function subject to a matroid constraint in a fully dynamic setting (the stream contains insertions and deletions).

The approximation guarantee achieved is 1/4−ϵ1/4-\epsilon with poly logarithmic in n and the rank k amortized update time.

This is the first work to get a constant guarantee with polylogarithmic amortized update time.

Critical strengths

The strength of the paper is in the result, polylogarthmic update time is the ultimate goal and this is the first paper to achieve that goal (albeit in an amortized setting).

Critical weaknesses

It is not a strict improvement on prior work. First the guarantee is amortized whereas the work of Banihashem et al (2024) is an "each update" guarantee. Furthermore, there update guarantee is independent of the ground set n (and, less importantly, has a logarithmic dependency on the ϵ\epsilon parameter).

The paper would benefit from a clearer explanation what the value/new insights are. The guarantee 1/4 appears frequently in these papers, as they follow the (great) paper of Chakrabarti & Kale, and apart from that, several techniques that appear in other papers are combined, such as sampling from a pool set of candidates and different levels of refinement with (different frequencies in their update schedule).

Questions for authors

The paper contains the full pseudo-code of the algorithms which is good. However, I think it would be helpful if the authors in addition clarify more what the new ideas are (especially compared to prior work). What should we take away from the submitted paper apart from the improved amortized guarantee?

Also, how good are these algorithms compared to other ones in a more practical scenario? There is no implementation and experiments, so it is unclear how the complexity and hidden constants behave compared to other approaches. This strenghtens the importance of the first point. If the main contribution is theoretical, then it is should emphasize what the novelty in terms of ideas and technics are.

1 comment

Thank you for your helpful feedback. We clarify our contributions and present new experiments.

1. Theoretical contributions

Comparison with prior guarantees. We agree that our result does not uniformly improve upon Banihashem et al. (2024). Their query guarantee holds in expectation for each update, is independent of nn, and has only logarithmic dependence on 1/ϵ1/\epsilon. Our guarantee is amortized: the total query bound holds for every realization of the randomness, but individual updates may be expensive. We trade additional dependence on nn and 1/ϵ1/\epsilon for eliminating the polynomial dependence on the matroid rank. We will make these distinctions explicit in the comparison.

We view the technical contribution in two parts.

Polylogarithmic maintenance of the streaming swap process. Dynamic maintenance of swaps was already studied by Dütting et al. (2023). Our observation is that these exchange decisions admit efficient batch maintenance. We use their circuit group-testing method (Lemma 5.4) to find the lightest exchangeable element with O(log⁡(2k))O(\log(2k)) independence queries. During an uninterrupted reconstruction, marginal gains decrease and failed exchange tests remain valid, allowing many acceptances to be processed without a full rescan after each one. This is an observation about the compatibility of established techniques; the exchange rule and circuit-search primitive are inherited.

Simpler and quicker. We believe the cardinality frameworks of Lattanzi et al. (2020, revised 2023) and Banihashem et al. (2023) also offer routes to a polylogarithmic dynamic matroid algorithm with a 1/4−ϵ1/4-\epsilon approximation. We verified the former's main approximation and query-analysis steps in a model allowing queries on deleted elements; the latter remains a possibility. The former uses sampling robustness and cross-level charging for deletion-triggered rebuilds; the latter estimates sample counts and analyzes random depth. Our construction avoids sample-size estimation and random-depth analysis by coupling exact truncation with a fixed rebuilding schedule. Each optimum-value guess maintains O(log⁡n)O(\log n) time levels storing snapshots and small residuals; reconstruction inherits the parent state and processes its residual plus recent insertions. Within a reconstruction, marginal buckets classify candidates; a random-permutation scan and binary searches determine the retained acceptance prefix exactly. Fixed depth and rebuilt suffixes make our algorithm and analysis more intuitive: costs follow rebuild frequencies; a deletion-tolerant exchange certificate bounds approximation loss. For fixed ϵ\epsilon and k≤nk\le n, our query bound also matches or improves the upper bounds of these cardinality algorithms.

2. Experimental evaluation

We added preliminary experiments on Enron, an email network dataset, to our theoretical study as reviewers suggested, comparing with Dütting et al. (2023) and Banihashem et al. (2024).

Setup. We uniformly sampled 4,096 candidates without replacement and randomly split them into eight equal synthetic groups, each with capacity k/8k/8, giving a rank-kk partition matroid. The objective counts nodes covered by selected candidates' closed neighborhoods among all 36,692 graph nodes. Candidates, groups and arrival order are fixed across ranks and methods. All methods use full parallel guesses and native ϵ=0.1\epsilon=0.1 (not identical approximation guarantees); three seeds per configuration give 45 runs.

FIFO stream. Starting empty, insert 1,024 candidates. For each remaining candidate, insert it, then delete the oldest live candidate as a separate update, maintaining an output after each (live size 1,025 then 1,024). Finally delete all remaining candidates in arrival order: 8,192 updates, one insertion/deletion per candidate.

Results. Each cell gives mean value-plus-independence queries/update over the full stream / mean solution value over the 6,145 updates with 1,024 or 1,025 live candidates.

kkOursDütting et al. (2023)Banihashem et al. (2024)
876,318 / 1,431.38,906 / 1,428.31,869 / 1,393.3
16116,898 / 2,104.633,206 / 2,089.06,294 / 2,051.8
32171,259 / 2,765.2138,338 / 2,751.717,976 / 2,726.1
64238,892 / 3,379.1575,457 / 3,432.345,328 / 3,416.5
128322,576 / 4,027.32,216,497 / 4,106.699,113 / 4,099.9

Observations. Solution values are similar. We use 58.5%/85.4% fewer queries than Dütting et al. (2023) at k=64/128k=64/128, but more at smaller ranks. Our query ratio to Banihashem et al. (2024) falls from 40.84 to 3.25, still above one. At fixed accuracy, their bounds have quadratic/linear rank factors up to logs; our polylogarithmic bound replaces the latter's kk by ϵ−1log⁡(2k)log⁡(2n)\epsilon^{-1}\log(2k)\log(2n). As expected, our relative query cost improves as kk grows. Rebuttal time limited completed runs to k≤128k\le128; we will complete larger-rank experiments to further demonstrate our query advantage.

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

The paper studies fully dynamic submodular maximization under a matroid constraint, where ff is a monotone, normalized submodular function. In the standard fully dynamic model, elements may be inserted into or deleted from the active ground set, and the algorithm must efficiently maintain a high-quality feasible solution after every update. Two important aspects are the solution value at each update and the number of value-oracle and matroid-independence-oracle queries required. For 0<ϵ≤1/100<\epsilon\le 1/10, an oblivious sequence of nn updates, and a matroid of rank at most kk, the paper guarantees E[f(Xt)]≥(1/4−ϵ)OPTt\mathbb{E}[f(X_t)]\ge (1/4-\epsilon)\mathrm{OPT}_t at every fixed time tt, using O(ϵ−1log⁡3(k/ϵ)log⁡(2k)log⁡2(2n))O(\epsilon^{-1}\log^3(k/\epsilon)\log(2k)\log^2(2n)) amortized oracle queries per update. The query bound holds for every realization of the algorithm’s randomness.

Critical strengths

This is a theoretical paper with a potentially significant result. Removing polynomial dependence on the matroid rank kk, while keeping the query complexity polylogarithmic in nn and kk for fixed ϵ\epsilon and retaining approximately 1/41/4 of the optimum in expectation, is a meaningful theoretical improvement.

Critical weaknesses

Although experiments are not essential for this theoretical contribution, an empirical evaluation comparing the algorithm’s solution quality after each update and oracle-query complexity with existing baselines, including on real-world data, would help assess its practical performance.

I also find the presentation challenging, particularly in Sections 3 and 4, where several important constructions and arguments are compressed. The interaction between the truncated sampler and the time-level hierarchy is difficult to follow. The proof sketches for Lemmas 1 and 8 would also benefit from bringing more of the intuition from Appendices A and B into the main text

Questions for authors

Please include a small worked example showing how the truncated sampler and the time-level hierarchy interact. The example should distinguish the temporary speculative states from the snapshots retained at each level and show what is reused or rebuilt after an insertion and a deletion.

What are the computational and storage costs beyond the oracle queries? In particular, how are the acceptance histories and speculative snapshots stored, and how much work is needed to maintain the ordering by frozen weight? A brief discussion would help clarify the practical implications of the query-complexity improvement.

2 comments

Thank you for your helpful suggestions. We condensed Sections 3–4 to meet page limits and will clarify:

1. Algorithm and proof sketches

The sampler commits an acceptance prefix and returns eligible residuals; the hierarchy schedules reconstruction and inheritance of snapshots/residuals. We will distinguish temporary speculative states from retained snapshots. The nonterminal cutoff qℓ=⌈2sℓ/ϵ⌉q_\ell=\lceil2s_\ell/\epsilon\rceil bounds residual size and controls expected deletion loss per rebuilding period.

Lemma 1. We will add a proof sketch to the main text: within a reconstruction, marginals decrease as history grows. Swapping a minimum-weight circuit member for a sufficiently heavier element preserves weighted spans: up to the removed weight, the circuit preserves the old span; above it, no generator is removed. Thus exchange thresholds cannot decrease, rejection persists, and binary search locates first failure without rescanning after every acceptance.

Lemma 8. The proof follows the streaming 1/41/4-approximation analysis of Chakrabarti and Kale (2015), extended to deletions. Its exchange and rank-integration arguments are too involved for a brief main-text sketch. We will keep the proof in Appendix B and clearly reference Proposition 20.

2. Computation and storage

Per guess, O(log⁡n)O(\log n) snapshots each store O(klog⁡n)O(k\log n) history records: each reconstruction commits at most kk elements, which later acceptances in the same/lower buckets cannot evict. Persistent balanced trees can share records: h≤kh\le k speculative acceptances add O(h(log⁡(2klog⁡n)+log⁡(2k)))O(h(\log(2k\log n)+\log(2k))) nodes. Frozen-weight order needs one insertion and at most one removal per acceptance, costing O(log⁡(2k))O(\log(2k)). Residuals/insertion records use O(nτlog⁡n)O(n_\tau\log n) space per instance with nτn_\tau assigned updates, excluding oracle data. Cleaning costs O(klog⁡n)O(k\log n); explicit value/independence query sets cost O(klog⁡n)/O(k)O(k\log n)/O(k) to construct.

For example, average reachability over fixed live-edge graphs is an exact monotone submodular objective (Kempe et al., 2003); updates change seed candidates. With 100 graphs of 10510^5 vertices and 10610^6 edges each, a traversal visiting most records processes about 1.1×1081.1\times10^8 records per query. At k=100k=100 and at most 2×1052\times10^5 updates, a snapshot has at most 1900 history records; graphs are shared. This illustrates oracle-dominated costs, not measured runtime; actual time depends on the oracle and set representation.

3. Worked example

We will add an appendix example linked from Section 3, with a unit-weight modular objective and rank-four uniform matroid, tracing speculative states, the committed prefix, and a deletion/insertion to distinguish reused snapshots/residuals from rebuilt levels.

4. Experimental evaluation

We added preliminary experiments on Enron, an email network dataset, to our theoretical study as reviewers suggested, comparing with Dütting et al. (2023) and Banihashem et al. (2024).

Setup. We uniformly sampled 4,096 candidates without replacement and randomly split them into eight equal synthetic groups, each with capacity k/8k/8, giving a rank-kk partition matroid. The objective counts nodes covered by selected candidates' closed neighborhoods among all 36,692 graph nodes. Candidates, groups and arrival order are fixed across ranks and methods. All methods use full parallel guesses and native ϵ=0.1\epsilon=0.1 (not identical approximation guarantees); three seeds per configuration give 45 runs.

FIFO stream. Starting empty, insert 1,024 candidates. For each remaining candidate, insert it, then delete the oldest live candidate as a separate update, maintaining an output after each (live size 1,025 then 1,024). Finally delete all remaining candidates in arrival order: 8,192 updates, one insertion/deletion per candidate.

Results. Each cell gives mean value-plus-independence queries/update over the full stream / mean solution value over the 6,145 updates with 1,024 or 1,025 live candidates.

kkOursDütting et al. (2023)Banihashem et al. (2024)
876,318 / 1,431.38,906 / 1,428.31,869 / 1,393.3
16116,898 / 2,104.633,206 / 2,089.06,294 / 2,051.8
32171,259 / 2,765.2138,338 / 2,751.717,976 / 2,726.1
64238,892 / 3,379.1575,457 / 3,432.345,328 / 3,416.5
128322,576 / 4,027.32,216,497 / 4,106.699,113 / 4,099.9

Observations. Solution values are similar. We use 58.5%/85.4% fewer queries than Dütting et al. (2023) at k=64/128k=64/128, but more at smaller ranks. Our query ratio to Banihashem et al. (2024) falls from 40.84 to 3.25, still above one. At fixed accuracy, their bounds have quadratic/linear rank factors up to logs; our polylogarithmic bound replaces the latter's kk by ϵ−1log⁡(2k)log⁡(2n)\epsilon^{-1}\log(2k)\log(2n). As expected, our relative query cost improves as kk grows. Rebuttal time limited completed runs to k≤128k\le128; we will complete larger-rank experiments to further demonstrate our query advantage.

Thank you for the clarifications and the proof. I could not find the promised worked example in the supplementary PDF. Thank you also for adding the experiments. Although they are limited in scope, it would be useful to connect the observed trend in query costs to Reviewer rSxq’s comment that the proposed bound is not uniformly better than that of Banihashem et al. (2024).

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

This paper studies fully dynamic monotone submodular maximization under general matroid constraints. The authors develop a randomized algorithm combining deletion-resistant exchange certificates, exact truncated sampling, and hierarchical rebuilding. The algorithm achieves a (1/4−ϵ)(1/4-\epsilon) expected approximation with polylogarithmic amortized oracle-query complexity in both the number of updates nn and the matroid rank kk, eliminating the polynomial dependence on kk in previous results.

Critical strengths

The paper addresses an important theoretical problem and introduces a nontrivial hierarchical rebuilding framework. The main result significantly improves the rank dependence of existing algorithms while maintaining a constant-factor approximation guarantee. The theoretical analysis is detailed and provides substantial support for the claimed improvement.

Critical weaknesses

Although the proposed algorithm eliminates polynomial dependence on the matroid rank kk, its complexity bound introduces an additional (ϵ−1log⁡2n)(\epsilon^{-1}\log^2 n) factor compared with Banihashem et al. (2024). Consequently, the new bound is not uniformly better across all parameter regimes. A more explicit discussion of this trade-off would strengthen the paper.

Questions for authors
  1. Compared with Banihashem et al. (2024), the proposed oracle-query complexity bound replaces the polynomial dependence on kk with an additional ϵ−1log⁡2n\epsilon^{-1}\log^2 n factor. Could the authors clarify the parameter regimes in which the new bound is tighter and whether this additional dependence on ϵ\epsilon and nn can be reduced?

  2. What are the main obstacles to improving the (1/4−ϵ)(1/4-\epsilon) approximation ratio while maintaining polylogarithmic amortized oracle-query complexity? Is this limitation inherent to the proposed framework or mainly due to the current analysis?

2 comments

Thank you for these questions. We will clarify the parameter trade-off and obstacles to improving the approximation, and include a tighter analysis of the submitted algorithm.

1. Parameter regimes and a tighter query bound

We agree that our bound is not uniformly better than that of Banihashem et al. (2024). After constant-factor normalization of the approximation parameters, their bound is O(klog⁡3(k/ϵ)log⁡(2k)),O\left(k\log^3(k/\epsilon)\log(2k)\right), whereas our submitted bound is O(ϵ−1log⁡3(k/ϵ)log⁡(2k)log⁡2(2n)).O\left(\epsilon^{-1}\log^3(k/\epsilon)\log(2k)\log^2(2n)\right). Thus, the submitted upper bound is asymptotically smaller when k=ω(ϵ−1log⁡2(2n))k=\omega(\epsilon^{-1}\log^2(2n)). We will make this parameter-dependent comparison explicit in the revised paper.

A tighter analysis. We have further refined the algorithm's analysis and obtained a tighter query bound. Consider one call to BUCKET-CONSTRUCT with mm candidates whose initial marginals lie in [a,2a)[a,2a). Every newly accepted element receives frozen weight at least aa. Since the history only grows during this call, a later acceptance has gain g<2ag<2a and cannot evict an earlier acceptance from the same call: the exchange test would require g≥2w(e)≥2ag\ge2w(e)\ge2a. All newly accepted elements therefore remain together in the final independent set of the full speculative scan. Consequently, the number hh of acceptances satisfies h≤min⁡{m,k}.h\le\min\{m,k\}. The binary searches over these states take O(log⁡(2min⁡{m,k}))O(\log(2\min\{m,k\})) decisions per candidate. Substituting this bound into the existing reconstruction analysis gives O(ϵ−1log⁡3(k/ϵ)log⁡(2k)log⁡(2min⁡{k,n})log⁡(2n))\boxed{ O\left( \epsilon^{-1}\log^3(k/\epsilon)\log(2k) \log(2\min\{k,n\})\log(2n) \right) } amortized oracle queries per update, without changing the algorithm or its approximation guarantee.

For k≤nk\le n, this replaces log⁡2(2n)\log^2(2n) by log⁡(2k)log⁡(2n)\log(2k)\log(2n). The refined upper bound is therefore asymptotically smaller than that of Banihashem et al. (2024) when k=ω(ϵ−1log⁡(2k)log⁡(2n)).k=\omega\left(\epsilon^{-1}\log(2k)\log(2n)\right). For fixed approximation accuracy ϵ\epsilon, this includes k=(log⁡n)1+δk=(\log n)^{1+\delta} for any fixed δ>0\delta>0, and k=nγk=n^\gamma for any fixed 0<γ≤10<\gamma\le1. In the latter regime, the rank dependence in the previous bound gives a polynomial dependence on nn, whereas ours is polylogarithmic. The previous bound can be preferable for small ranks or high accuracy. These comparisons concern proven upper bounds. Their guarantee is expected per update; ours is amortized and bounds the total queries for every realization of the randomness.

The ϵ−1\epsilon^{-1} factor comes from the pool cutoff qℓ=⌈2sℓ/ϵ⌉q_\ell=\lceil2s_\ell/\epsilon\rceil, which controls the expected deletion loss before reconstruction. For fixed accuracy, it contributes only a constant factor to the query bound.

2. Improving the approximation ratio

We have studied in depth whether a higher approximation ratio can be achieved with polylogarithmic queries. A main obstacle to directly importing the 0.31780.3178 streaming guarantee of Feldman et al. (2022) is the query cost of its fractional construction. It uses the multilinear extension and its derivatives, whose existing sampling-based implementations at the required accuracy introduce polynomial dependence on the rank. For example, the analysis of PICK in Gao et al. (2026), Lemma 10, gives O(ϵ−2k2log⁡2(k/ϵ)log⁡k)O\left(\epsilon^{-2}k^2\log^2(k/\epsilon)\log k\right) oracle queries per call, with the value-oracle cost dominating. This is the cost of an existing implementation, not a lower bound for all possible estimators.

We also investigated a fully combinatorial variant inspired by the 0.31780.3178 streaming algorithm to avoid these estimates. It maintains integral anchor sets at different value levels and extracts an independent solution through layered packing. However, our current analysis of this variant establishes only a 1/5−O(ϵ)1/5-O(\epsilon) approximation. The loss already appears in the static setting, when converting the weighted anchor certificate into the value of a feasible independent set; the stronger fractional guarantee does not transfer directly. If helpful, we can include this static construction and its analysis in an appendix to explain the obstacle more concretely.

Thank you for the detailed response. The refined oracle-query bound and the discussion of parameter regimes address my main concern. I encourage the authors to incorporate these results and the corresponding comparison with Banihashem et al. (2024) into the main text. The explanation of the obstacles to improving the approximation ratio is also helpful. I will maintain my rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.