# The Power of Subsampling in Submodular Maximization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 67 references that are in the map.
- First posted on arXiv 6 Apr 2021.

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

- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly](https://mlsanity.com/paper/1706.03583/) (2017)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Submodularity in Action: From Machine Learning to Signal Processing Applications](https://mlsanity.com/paper/2006.09905/) (2020)
- [Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization](https://mlsanity.com/paper/1704.01652/) (2017)
- [Online Submodular Maximization with Preemption](https://mlsanity.com/paper/1501.05801/) (2015)
- [Adaptive Sequence Submodularity](https://mlsanity.com/paper/1902.05981/) (2019)
- [Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization](https://mlsanity.com/paper/1410.0773/) (2014)
- [Streaming Algorithms for Submodular Function Maximization](https://mlsanity.com/paper/1504.08024/) (2015)
- [Constrained Submodular Maximization: Beyond 1/e](https://mlsanity.com/paper/1608.03611/) (2016)
- [Submodular Maximization Through Barrier Functions](https://mlsanity.com/paper/2002.03523/) (2020)
- [Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order](https://mlsanity.com/paper/1712.05450/) (2017)
- [Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint](https://mlsanity.com/paper/1811.07464/) (2018)
- [Streaming Submodular Maximization under a k-Set System Constraint](https://mlsanity.com/paper/2002.03352/) (2020)
- [Online Submodular Maximization: Beating 1/2 Made Simple](https://mlsanity.com/paper/1807.05529/) (2018)

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

- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Improving Video Question Answering through query-based frame selection](https://mlsanity.com/paper/2601.07459/) (2026)

## Abstract (arXiv)

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set, and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual offline setting, we present SampleGreedy, which obtains a (p + 2 + o(1))-approximation for maximizing a submodular function subject to a p-extendible system using O(n + nk/p) evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p+1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present SampleStreaming, which obtains a (4p +2 - o(1))-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and O(km/p) evaluation and feasibility queries per element, where m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.