A General Framework for Dynamic Consistent Submodular Maximization¶

Conference: ICML2026
arXiv: 2606.04946
Code: Code not provided
Area: Optimization / Submodular Maximization / Dynamic Algorithms
Keywords: Submodular Maximization, Dynamic Algorithms, Consistency, Deletion-Robust, Matroid Constraints

TL;DR¶

This paper introduces a general consistency framework for fully dynamic submodular maximization. In streaming environments allowing both insertions and deletions, it is the first to achieve constant approximation guarantees and sublinear worst-case per-step solution changes (recourse) for both cardinality and matroid constraints.

Background & Motivation¶

Background: Submodular maximization is widely used in tasks such as data summarization, recommendation, active learning, and sparse selection. Traditional dynamic algorithms focus on maintaining approximate optimality quickly after updates, whereas recent consistent optimization also requires that the solutions presented to users do not change drastically after each update.

Limitations of Prior Work: Existing consistent submodular maximization primarily investigates insertion-only scenarios. In insertion-only settings, old solutions typically do not become invalid immediately upon the arrival of new elements. However, fully dynamic scenarios include deletions; if a critical element is removed, the optimal solution might require a complete reconstruction. Directly re-running dynamic algorithms may yield good approximations but might replace a large number of elements simultaneously.

Key Challenge: There is a tension between approximation and stability; approximation requires the solution to track the current optimum quickly, while stability requires changing only a few elements per step. Insertions and deletions cause the optimal value to fluctuate, making it impossible to rely on the monotonicity analysis common in insertion-only settings. Furthermore, matroid constraints restrict the set of exchangeable elements, making the repair of old solutions more difficult.

Goal: Construct a modular framework that, given appropriate robust and non-robust submodular routines, maintains high-value feasible solutions in a fully dynamic environment while limiting the per-step symmetric-difference change to a small scale.

Key Insight: The authors borrow the coreset concept from deletion-robust submodular maximization. Instead of assuming a known number of deletions, the framework maintains multiple robustness levels. It employs random scheduling to spread the recomputation of different levels across transition windows, avoiding large-scale one-time replacements.

Core Idea: Periodically recompute candidate solutions for different deletion-robustness levels and transition block-by-block within short windows, ensuring that "global reconstructions" are amortized into multiple small changes.

Method¶

The paper considers an operation sequence provided by an oblivious adversary, where each step involves the insertion or deletion of an element. The algorithm maintains a feasible solution \(ALG_t \subseteq X_t\) at each time \(t\). The goals are twofold: approximation requires \(\mathbb{E}[f(ALG_t)] \geq \alpha f(OPT_t)\), and consistency requires that the symmetric difference \(|ALG_t \triangle ALG_{t-1}|\) is bounded by a small constant or value \(C\).

Overall Architecture¶

The framework consists of three parts: Random-Scheduling, a robust routine \(\mathcal{A}_R\), and a non-robust routine \(\mathcal{A}_N\). Random-Scheduling generates multi-level transition times based on maximum and minimum robustness parameters \(d_0, d_\ell\), corresponding to different deletion robustness levels. When a transition time arrives, the algorithm calls the robust routine to recompute intermediate solutions and the remaining candidate set for that level. In regular time steps, the algorithm starts from the intermediate solution of the most recent lower-level transition and uses the non-robust routine to process new candidate elements.

Crucially, the focus is not just on recomputation but on how the solution is presented. Within a transition window, the algorithm does not immediately replace the old solution with the new one. Instead, it partitions the difference between the new and old solutions into several blocks, swapping one block at each step while maintaining matroid feasibility. Thus, even if the internal intermediate solution changes significantly, the \(ALG_t\) seen by the user undergoes only controlled changes.

Key Designs¶

Random-Scheduling:
- Function: Determines when to recompute robust intermediate solutions for different robustness levels and ensures that transition windows do not overlap.
- Mechanism: Blocks the timeline starting from the highest robustness level \(d_0\), reserving a transition window of \(\varepsilon' d_i\) at the beginning of each block. Remaining intervals are partitioned recursively for the next level. Finally, a uniform random shift is applied so that the probability of any fixed time falling into a transition window is controlled.
- Design Motivation: Different scales of deletion require different recomputation frequencies. High robustness levels do not need frequent recomputations, while lower levels require more recent updates. The random shift allows the analysis to average the losses incurred during transitions.
Robust Routines and Residual Candidate Sets:
- Function: Constructs intermediate solutions that remain valuable against a certain number of deletions without knowing the future deletion positions.
- Mechanism: The robust routine takes an initial solution, a candidate set, and a parameter \(d\), outputting an updated solution \(I\) and a set \(C\) of remaining useful candidates. For matroids, Robust-Swap is used, sampling candidates based on the inverse of their marginal contributions and retaining only high-marginal elements. For cardinality constraints, Robust-Greedy samples from high-marginal candidates.
- Design Motivation: After deletions, some selected elements become invalid. Maintaining a small yet representative residual candidate set allows for repairing the solution with minimal changes in future steps.
Consistency Transition Windows:
- Function: Transforms a potentially large solution replacement into multiple small replacements.
- Mechanism: After calculating a new solution \(I_t\) at a transition time, elements common to the old and new solutions remain fixed. The sets \(I_t \setminus ALG_{old}\) and \(ALG_{old} \setminus I_t\) are partitioned into an equal number of blocks and swapped step-by-step within the window, using matroid exchange properties to maintain feasibility.
- Design Motivation: Internal dynamic algorithms can recompute for approximation performance, but the externally exposed solution must be stable. The window mechanism decouples internal reconstruction from external consistency.

Loss & Training¶

As this is a theoretical algorithm paper, there are no neural network training losses. The "objective function" is a monotone submodular function \(f\), with constraints including cardinality or matroid independent sets. The algorithm uses a value oracle and a matroid feasibility oracle. The analysis provides approximation ratios, consistency bounds, and amortized oracle complexity.

Key Experimental Results¶

Main Results¶

The paper provides theoretical guarantees rather than empirical experiments. The following table summarizes the key theoretical results under the fully dynamic setting.

Setting	Algorithm (Ours)	Approx. Guarantee	Consistency Guarantee	Significance
Cardinality constraint	ConsistentCardinality	\(1/2 - 3\varepsilon\)	\(O(1/\varepsilon^2)\)	Approaches the known \(1/2\) level of dynamic submodular maximization while maintaining constant per-step change.
Rank-\(k\) matroid constraint	ConsistentMatroid	\(1/4 - 7\varepsilon\)	\(O(\log k / \varepsilon^2)\)	Matches the classic \(1/4\) approximation in streaming matroids but allows deletions with logarithmic consistency.
Fully dynamic generic framework	Random scheduling + routines	Determined by routines	Determined by windows & \(d_i\)	Deconstructs consistent dynamic algorithms into a reusable template.
Prior insertion-only cardinality	Constant recourse algorithms	~0.51 or theoretical upper bound	Constant consistency	Does not handle deletions; optimal values are more monotone.

Ablation Study¶

As a theoretical paper, it lacks empirical ablation; the roles of the framework components are viewed as analytical ablations.

Configuration / Component	Key Metric	Description
Without robust routine	Fails under deletions	Cannot guarantee enough value in the candidate set for replacements; fails in fully dynamic scenarios.
Without multi-level robustness	Hard to cover matroid deletion scales	A single level is either too frequent or not robust enough for large deletions, failing the \(O(\log k / \varepsilon^2)\) bound.
Without transition window	Recourse becomes uncontrolled	Symmetric difference can reach \(\Theta(k)\) when replacing solutions directly.
Without random shift	Transition loss at fixed times	Approximation analysis cannot use the "off-transition probability \(\geq 1 - \varepsilon\)" to control loss.
Cardinality-specific Robust-Greedy	\(1/2 - 3\varepsilon\), \(O(1/\varepsilon^2)\)	Leverages the simple structure of uniform matroids, requiring only a single robustness level.

Key Findings¶

The difficulty of fully dynamic settings stems primarily from deletions rather than insertions. Deleting a dominant element may force a global change in the optimal solution, necessitating pre-emptive robust candidate structures.
Matroid constraints are significantly harder than cardinality constraints because exchangeable elements are limited by independence constraints; this explains the \(1/4\) ratio for matroids versus \(1/2\) for cardinality.
Consistency is guaranteed in the worst-case per step, which is more aligned with user needs for stable recommendations/summaries than the amortized updates used in many dynamic algorithms.

Highlights & Insights¶

The framework is highly modular. Scheduling, consistency transitions, and submodular routines are decoupled, allowing for the direct replacement of robust routines to inherit consistency mechanisms.
Spreading transition loss via random shifts is a simple yet effective technique. It does not force the best approximation at every moment but ensures a high probability of not being in a transition period at any fixed time.
The paper adapts the deletion-robust coreset idea to online fully dynamic settings and handles unknown, varying deletion scales through multiple robustness levels, which is more practical than static deletion-robustness.

Limitations & Future Work¶

The results are primarily theoretical, lacking experiments on runtime and stability in real-world data summarization or recommendation tasks. The actual oracle costs—especially for matroid independence oracles—could be significant.
The approximation ratios remain constant-level, particularly \(1/4 - O(\varepsilon)\) for matroids. Applications highly sensitive to quality might require more powerful offline or dynamic submodular routines.
The framework assumes an oblivious adversary and uses randomization in its analysis. The guarantees do not directly apply to adaptive adversaries or non-monotone submodular functions.
Block-by-block swapping within transition windows requires implementation details, especially in finding feasible exchange blocks efficiently for complex matroids.

vs Insertion-only Consistent Submodular Maximization: Previous works achieved constant recourse and better approximations but relied on the monotone structure of insertions. Ours extends to dual operations at the cost of complex robust scheduling.
vs Deletion-Robust Submodular Maximization: Deletion-robust methods typically assume a fixed deletion budget \(d\). This work maintains multiple \(d_i\) online as the scale of deletions is unknown and time-varying.
vs Fully Dynamic Submodular Algorithms: Classic fully dynamic algorithms prioritize amortized update time and may change solutions drastically. This paper treats "solution change perceived by the user" as a first-class metric.
vs Online Submodular Maximization with Preemption: Preemption allows replacing elements but does not allow recovery after discarding. This work maintains a stable solution within a dynamically active set of available elements.

Rating¶

Novelty: ⭐⭐⭐⭐☆ Handling the combination of fully dynamic + consistency + matroid constraints is challenging and the modular framework is valuable.
Experimental Thoroughness: ⭐⭐☆☆☆ Purely theoretical; lacks empirical data experiments, though theorems and complexity analyses are complete.
Writing Quality: ⭐⭐⭐⭐☆ Technical overview is clear, and algorithm components are well-structured, though proofs are extensive with long notation chains.
Value: ⭐⭐⭐⭐☆ Theoretically significant for stable data summarization and dynamic selection; serves as a reminder that dynamic optimization should consider more than just approximation and update time.