When designing algorithms for data summarization, streaming, or dynamic optimization, we often optimize for the average case or assume that data changes are benign. However, in real-world scenarios—such as complying with privacy regulations like GDPR's "right to be forgotten," handling adversarial network manipulation, or mitigating targeted data corruption—systems must remain robust when critical elements are deliberately deleted or altered.
If an algorithm selects elements deterministically, a sophisticated adversary who understands the algorithm can easily predict which items are most vital to the solution's utility. By deleting just a few of these high-value items, the adversary can catastrophically degrade the system's performance.
To counter this vulnerability, a powerful paradigm has emerged: using internal randomness to hide critical elements from the adversary. By shifting from deterministic selection to stochastic subset selection, algorithms can maintain high-quality solutions even under massive, targeted data removal.
The Core Intuition: Hiding Behind Internal Randomness
The fundamental reason randomized selection provides robustness against adversarial deletions is an information asymmetry: the adversary cannot observe the algorithm's internal random bits.
Imagine trying to build a representative summary of a massive dataset. A standard greedy algorithm would pick the single element providing the highest marginal utility, then the second highest, and so on. An adversary can replicate this exact logic and delete those specific items.
As Ehsan Kazemi et al. demonstrate in Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints, we can neutralize this threat by maintaining a larger pool of interchangeable, high-utility candidates and selecting from them stochastically. Because the specific identity of the chosen elements remains unpredictable, the adversary cannot target the critical components of the summary.
Deterministic Selection (Vulnerable):
[Candidate Pool] ---> Always Pick Best ---> Adversary Deletes It ---> Utility Drops
Randomized Selection (Robust):
[Candidate Pool] ---> Randomly Sample ---> Adversary Guesses ---> Summary Remains Intact
This mechanism ensures that no single element is uniquely critical to the overall utility. As shown by Morteza Zadimoghaddam et al. in Deletion-Robust Submodular Maximization at Scale, incorporating controlled randomness stabilizes the utility of a selected subset, guaranteeing constant-factor approximations even when a significant portion of the dataset is wiped out.
Downgrading the Adversary: From Adaptive to Oblivious
In robust statistics, researchers distinguish between two types of threats:
- Oblivious Adversaries: Attackers who must choose which data points to corrupt or delete before seeing how the algorithm responds.
- Adaptive Adversaries: Attackers who can observe the dataset or the algorithm's intermediate state and dynamically tailor their sabotage.
Randomized selection acts as a mathematical filter that strips away an adaptive adversary's advantage. In On the power of adaptivity in statistical adversaries, Guy Blanc et al. prove that large-scale random subsampling can effectively convert an adaptive adversary into an oblivious one.
When an adversary targets specific data points, they introduce complex dependencies and correlations into the dataset. However, by drawing a large pool of data and randomly selecting a subset, the algorithm breaks these engineered dependencies. The authors expand on this principle in Adaptive and oblivious statistical adversaries are equivalent, demonstrating that correlation rounding and random subsampling make the resulting data subset statistically indistinguishable from data corrupted by a blind, oblivious distribution. The targeted attack is effectively downgraded to harmless background noise.
Maintaining Efficiency in Dynamic Environments
Introducing randomness does not just preserve utility; it also prevents computational bottlenecks in dynamic environments where items are constantly inserted and deleted.
In a fully dynamic system, deleting a high-value element might normally force the algorithm to recompute the entire solution from scratch—a prohibitively expensive operation for massive streams. To solve this, Silvio Lattanzi et al. in Fully Dynamic Algorithm for Constrained Submodular Optimization propose uniform random sampling from pre-qualified candidate pools. Because the selection is stochastic, an adversary must remove a disproportionately large number of elements to force a major configuration change.
This concept of maintaining a "uniform invariant" is pushed further by Kiarash Banihashem et al. in Improved Dynamic Algorithm for Non-monotone Submodular Maximization under Cardinality Constraint. By ensuring elements are selected uniformly at random from a leveled structure of high-gain candidates, the authors guarantee that the probability of any single deletion triggering a large-scale recomputation remains low. This keeps the expected update time highly efficient while preserving robust approximation guarantees.
Application Across Algorithmic Domains
The power of randomized subset selection spans across several distinct areas of computer science, proving that the underlying mechanism is universally applicable:
Streaming Sketches and Importance Sampling
In data streams, adversaries often exploit fixed null spaces or blind spots in an algorithm's sketch. Avinatan Hassidim et al. show in Adversarial Robustness of Streaming Algorithms through Importance Sampling that using importance sampling provides inherent adversarial robustness. By introducing fresh randomness for each selection step, the algorithm prevents adaptive adversaries from learning and exploiting the internal state of the stream. Similarly, Guangyi Zhang et al. in Optimal deletion-robust coreset for submodular maximization utilize a randomized buffer during the streaming exchange process to prevent attackers from identifying and destroying high-value items.
Complex Combinatorial Constraints
When moving beyond simple cardinality constraints to complex structures like matroids or knapsacks, the strategy remains consistent: over-provision the candidate pool. Paul Duetting et al. demonstrate in Deletion Robust Submodular Maximization over Matroids that maintaining candidate sets significantly larger than the expected number of deletions—and sampling uniformly from them—ensures the expected loss from deletions is strictly proportional to the fraction of items removed. For knapsack constraints, Kai Han et al. in Deletion-Robust Submodular Maximization with Knapsack Constraints introduce a "warehouse" sampling technique that weights selections inversely to their marginal gains, balancing the expected loss of targeted items against the utility of the remaining pool.
Information Aggregation and Linear Algebra
The principle even holds when aggregating forecasts or decomposing matrices. In Universally Robust Information Aggregation for Binary Decisions, Inbal Talgam-Cohen et al. study scenarios where the correlations between information sources are unknown or malicious. They prove that the uniquely optimal strategy is the "random dictator rule"—randomly selecting a single source's recommendation—which completely prevents an adversary from exploiting complex coordination patterns among agents. In numerical linear algebra, Yijun Dong et al. show in Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition that incorporating randomness into row selection prevents deterministic greedy algorithms from failing when encountering adversarial matrix structures.
Conclusion
Whether defending deep learning models against adversarial data selection—where Yuejun Guo et al. note in DRE: density-based data selection with entropy for adversarial-robust deep learning models that simple random sampling remains a remarkably competitive baseline—or protecting facility location networks against cost fluctuations (Stephen Pasteris et al. in Online Learning of Facility Locations), the core lesson is clear.
When faced with an adversary capable of deleting or manipulating data, determinism is a liability. By embedding internal, unobservable randomness directly into the selection process, algorithms can successfully decouple their success from individual data points, rendering targeted adversarial deletions no more effective than random noise.
Key Foundational Work
Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints (2018) — contributed 3 concept elements to this direction.
Deletion-Robust Submodular Maximization at Scale (2017) — contributed 2 concept elements to this direction.