# Noisy Submodular Maximization via Adaptive Sampling with Applications to Crowdsourced Image Collection Summarization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Nov 2015.

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

- [Training Data Subset Selection for Regression with Controlled Generalization Error](https://mlsanity.com/paper/2106.12491/) (2021)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Video Summarization Overview](https://mlsanity.com/paper/2210.11707/) (2022)
- [Multi-objective optimisation via the R2 utilities](https://mlsanity.com/paper/2305.11774/) (2023)
- [Show Me What I Like: Detecting User-Specific Video Highlights Using Content-Based Multi-Head Attention](https://mlsanity.com/paper/2207.08352/) (2022)
- [Linear Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2407.02601/) (2024)
- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit](https://mlsanity.com/paper/2410.08578/) (2024)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)

## Abstract (arXiv)

We address the problem of maximizing an unknown submodular function that can only be accessed via noisy evaluations. Our work is motivated by the task of summarizing content, e.g., image collections, by leveraging users' feedback in form of clicks or ratings. For summarization tasks with the goal of maximizing coverage and diversity, submodular set functions are a natural choice. When the underlying submodular function is unknown, users' feedback can provide noisy evaluations of the function that we seek to maximize. We provide a generic algorithm -- submM -- for maximizing an unknown submodular function under cardinality constraints. This algorithm makes use of a novel exploration module -- blbox -- that proposes good elements based on adaptively sampling noisy function evaluations. blbox is able to accommodate different kinds of observation models such as value queries and pairwise comparisons. We provide PAC-style guarantees on the quality and sampling cost of the solution obtained by submM. We demonstrate the effectiveness of our approach in an interactive, crowdsourced image collection summarization application.