# Distributionally Robust Submodular Maximization

arXiv: https://arxiv.org/abs/1802.05249 · HTML: https://mlsanity.com/paper/1802.05249/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2018.

## Built on by (most cited first, 12 of 12)

- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Decision-Focused Evaluation of Worst-Case Distribution Shift](https://mlsanity.com/paper/2407.03557/) (2024)
- [Distributionally Robust Active Learning for Gaussian Process Regression](https://mlsanity.com/paper/2502.16870/) (2025)
- [Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees](https://mlsanity.com/paper/2205.15624/) (2022)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Localized Distributional Robustness in Submodular Multi-Task Subset Selection](https://mlsanity.com/paper/2404.03759/) (2024)
- [Temporal Robustness in Discrete Time Linear Dynamical Systems](https://mlsanity.com/paper/2505.02347/) (2025)
- [Bandit Guided Submodular Curriculum for Adaptive Subset Selection](https://mlsanity.com/paper/2511.22944/) (2025)
- [Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization](https://mlsanity.com/paper/2606.11804/) (2026)

## Abstract (arXiv)

Submodular functions have applications throughout machine learning, but in many settings, we do not have direct access to the underlying function f. We focus on stochastic functions that are given as an expectation of functions over a distribution P. In practice, we often have only a limited set of samples fi from P. The standard approach indirectly optimizes f by maximizing the sum of fi. However, this ignores generalization to the true (unknown) distribution. In this paper, we achieve better performance on the actual underlying function f by directly optimizing a combination of bias and variance. Algorithmically, we accomplish this by showing how to carry out distributionally robust optimization (DRO) for submodular functions, providing efficient algorithms backed by theoretical guarantees which leverage several novel contributions to the general theory of DRO. We also show compelling empirical evidence that DRO improves generalization to the unknown stochastic submodular function.