Mini-batch Submodular Maximization
Lists
Only you see this
Abstract
We present the first *mini-batch* algorithm for maximizing a non-negative monotone *decomposable* submodular function, $F=\sum_{i=1}^N f^i$, under a set of constraints. We consider two sampling approaches: uniform and weighted. We show that mini-batch with weighted sampling improves over the state of the art sparsifier based approach both in theory and in practice. Surprisingly, we experimentally observe that uniform sampling achieves superior results 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.
BibTeX
@misc{schwartzman2024mini,
author = {Gregory Schwartzman},
title = {{Mini-batch Submodular Maximization}},
year = {2024},
eprint = {2401.12478},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2401.12478},
}Loading related content...