# Mini-batch Submodular Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 23 Jan 2024.

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

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints](https://mlsanity.com/paper/2006.15744/) (2020)
- [Submodular Cost Submodular Cover with an Approximate Oracle](https://mlsanity.com/paper/1908.00653/) (2019)
- [Differentially Private Decomposable Submodular Maximization](https://mlsanity.com/paper/2005.14717/) (2020)
- [Budget-Smoothed Analysis for Submodular Maximization](https://mlsanity.com/paper/2102.05782/) (2021)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Cut Sparsification and Succinct Representation of Submodular Hypergraphs](https://mlsanity.com/paper/2307.09110/) (2023)
- [Local max-cut in smoothed polynomial time](https://mlsanity.com/paper/1610.04807/) (2016)
- [Sparsification of Monotone k-Submodular Functions of Low Curvature](https://mlsanity.com/paper/2302.03143/) (2023)

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

- [The Power of Second Chance: Personalized Submodular Maximization with Two Candidates](https://mlsanity.com/paper/2409.03545/) (2024)

## Abstract (arXiv)

We present the first mini-batch algorithm for maximizing a non-negative monotone decomposable submodular function, F=sumi=1N fi, under a set of constraints. We consider two sampling approaches: uniform and weighted. We first show that mini-batch with weighted sampling improves over the state of the art sparsifier based approach both in theory and in practice. Surprisingly, our experimental results show that uniform sampling is superior to weighted sampling. However, it is impossible to explain this using worst-case analysis. Our main contribution is using smoothed analysis to provide a theoretical foundation for our experimental results. We show that, under very mild assumptions, uniform sampling is superior for both the mini-batch and the sparsifier approaches. We empirically verify that these assumptions hold for our datasets. Uniform sampling is simple to implement and has complexity independent of N, making it the perfect candidate to tackle massive real-world datasets.