Submodular functions are the mathematical workhorses of data summarization, sensor placement, and viral marketing. They capture the intuitive law of diminishing returns: adding an item to a small collection yields a larger marginal benefit than adding it to a larger collection.
For decades, the standard recipe for maximizing a submodular function has been the greedy algorithm. It is simple and elegant: start with an empty set, and iteratively choose the single item that provides the highest immediate marginal gain. In static environments, this short-sighted strategy is remarkably effective, guaranteed to capture at least 63% ($1 - 1/e$) of the optimal solution's total utility.
However, real-world deployment exposes a critical vulnerability in this approach. What happens if some of your chosen items are suddenly deleted?
The Fragility of Greedy Selection
Standard greedy algorithms are fragile because they are inherently optimistic; they assume every selected item will remain functional and available forever. Consequently, they tend to concentrate massive utility into a tiny handful of "super-items."
As noted by Ehsan Kazemi et al. and Morteza Zadimoghaddam et al., if an adversary removes even a single one of these high-value items, or if a user exercises their legal "right to be forgotten" under modern privacy regulations, the utility of the remaining summary can collapse precipitously.
Standard Greedy: [ Super-Item ] ---> (Adversary Deletes) ---> [ Empty / Low Utility ]
Robust Selection: [ Item A ] [ Item B ] [ Item C ] ---------> [ Item B ] [ Item C ] (High Utility)
This vulnerability is particularly acute in sequential tasks. Greedy sequence optimization tends to front-load value into the earliest positions. If an attacker targets and removes these initial elements, the entire downstream sequence can be rendered ineffective, as shown by Gamal Sallam et al..
Why Simple Redundancy Fails
An intuitive first attempt to fix this vulnerability might be to introduce simple redundancy. If you need a summary of size $k$, and you expect an adversary to delete up to $d$ items, why not just use the greedy algorithm to select a larger pool of $k + d$ items?
Baharan Mirzasoleiman et al. demonstrated why this naive volume-based strategy fails. Because submodular optimization is driven by marginal gains, a single high-utility element can completely dominate the selection process. The subsequent $k+d-1$ items might be chosen purely because they complement that single dominant item. If an adversary deletes that core item, the remaining elements may possess near-zero collective utility on their own.
True robustness requires structural diversity, not just increased volume. The algorithm must be forced to select high-quality backup options that can stand on their own feet if the primary choices disappear.
Forcing Diversity via Partitioning and Thresholding
To prevent a single item from dominating the selection, robust algorithms actively distribute their choices across independent buckets. This is known as a partitioning strategy.
The PRO (Partitioned Robust) algorithm, introduced by Ilija Bogunovic et al., achieves this by dividing the selection budget into non-uniform partitions. Instead of picking items sequentially from the entire dataset, the algorithm fills these distinct partitions independently. If an adversary targets the most valuable items, they can only wipe out a single partition, leaving the remaining partitions intact to provide a guaranteed constant-factor approximation of the optimal utility.
Dataset ---> [ Partition 1: Top Tier ] ---> Wiped out by adversary
---> [ Partition 2: Backup A ] ---> Survives (Guarantees utility)
---> [ Partition 3: Backup B ] ---> Survives (Guarantees utility)
In streaming environments—where data arrives one element at a time and cannot be reprocessed—robustness requires combining partitioning with smart thresholding. Algorithms like STAR-T (Slobodan Mitrović et al.) and RSK-Streaming (Kai Han et al.) maintain a cascading chain of thresholds. As items stream past, they are accepted only if their marginal contribution exceeds a specific, dynamically adjusted bar. This prevents the algorithm from burning its budget on redundant elements early on, ensuring a balanced, diverse summary is constructed in a single pass.
The Memory Cost of Robustness: Linear Coreset Scaling
If data points are constantly being deleted post-hoc, running a heavy optimization algorithm from scratch every time the dataset changes is computationally intractable. Instead, we want to maintain a coreset—a highly compressed, representative subset of the data from which a high-quality solution can be instantly extracted after deletions occur.
What is the fundamental memory cost of defending against $d$ deletions? Guangyi Zhang et al. proved a strict theoretical boundary: to maintain a constant-factor approximation, the size of a deletion-robust coreset must scale linearly with both the target solution size $k$ and the number of potential deletions $d$. They achieved an asymptotically optimal coreset size of $k + d/\epsilon$.
Remarkably, this additive space complexity ($O(k+d)$) means that the "price of robustness" is incredibly low. As demonstrated by Paul Duetting et al. under general matroid constraints and Dmitrii Avdiukhin et al. under knapsack constraints, these space-efficient summaries can capture 90–95% of the objective value achieved by an "all-knowing" benchmark that has perfect foresight of which items will be removed.
Beyond Submodularity
The intuition behind deletion-robust selection extends even beyond pure submodular functions. In many real-world machine learning applications, the objective functions exhibit weak submodularity or are entirely non-submodular.
To bridge this gap, Ilija Bogunovic et al. introduced the OBLIVIOUS-GREEDY algorithm. They proved that constant-factor approximation guarantees can be maintained for non-submodular objectives even in the "linear regime"—where the number of adversarial deletions scales as a fixed percentage of the total selection budget, rather than just a small, sub-linear fraction.
Furthermore, by shifting from deterministic selections to randomized strategies, researchers have shown that the theoretical penalty of defending against an adversary can be completely eliminated. As shown by Yasushi Kawase et al., employing randomized strategies via linear programming or multiplicative weights updates allows robust algorithms to match the optimal $(1 - 1/e)$ approximation bounds of their non-robust counterparts, proving that we can build systems that are both highly efficient and profoundly resilient to change.
Key Foundational Work
Robust monotone submodular function maximization (2018) — contributed 6 concept elements to this direction.
Robust Submodular Maximization: A Non-Uniform Partitioning Approach (2017) — contributed 5 concept elements to this direction.
Robust Maximization of Non-Submodular Objectives (2018) — contributed 3 concept elements to this direction.