# A Unified Approach to Submodular Maximization Under Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 24 Oct 2025.

## Builds on (most cited first, 11 of 11)

- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization](https://mlsanity.com/paper/1511.07211/) (2015)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Maximization of Approximately Submodular Functions](https://mlsanity.com/paper/2411.10949/) (2024)
- [No-regret algorithms for online k-submodular maximization](https://mlsanity.com/paper/1807.04965/) (2018)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [An Optimal Algorithm for Online Unconstrained Submodular Maximization](https://mlsanity.com/paper/1806.03349/) (2018)
- [On Additive Approximate Submodularity](https://mlsanity.com/paper/2010.02912/) (2020)
- [Efficient Submodular Optimization under Noise: Local Search is Robust](https://mlsanity.com/paper/2210.11992/) (2022)
- [A Threshold Greedy Algorithm for Noisy Submodular Maximization](https://mlsanity.com/paper/2312.00155/) (2023)

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

- [Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning](https://mlsanity.com/paper/2608.12134/) (2026)

## Abstract (arXiv)

We consider the problem of maximizing a submodular function with access to a noisy value oracle for the function instead of an exact value oracle. Similar to prior work, we assume that the noisy oracle is persistent in that multiple calls to the oracle for a specific set always return the same value. In this model, Hassidim and Singer (2017) design a (1-1/e)-approximation algorithm for monotone submodular maximization subject to a cardinality constraint, and Huang et al (2022) design a (1-1/e)/2-approximation algorithm for monotone submodular maximization subject to any arbitrary matroid constraint. In this paper, we design a meta-algorithm that allows us to take any "robust" algorithm for exact submodular maximization as a black box and transform it into an algorithm for the noisy setting while retaining the approximation guarantee. By using the meta-algorithm with the measured continuous greedy algorithm, we obtain a (1-1/e)-approximation (resp. 1/e-approximation) for monotone (resp. non-monotone) submodular maximization subject to a matroid constraint under noise. Furthermore, by using the meta-algorithm with the double greedy algorithm, we obtain a 1/2-approximation for unconstrained (non-monotone) submodular maximization under noise.