Mini-batch Submodular Maximization

Gregory SchwartzmanSubmission to ICLR 2026 · Rejected

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. Our experiments demonstrate that a straightforward uniform mini-batch sampling approach significantly outperforms existing state-of-the-art sparsifier methods, requiring only a fraction of their running time. However, explaining this improvement via worst-case analysis is impossible. Instead, we employ smoothed analysis to provide a theoretical justification for our empirical findings. Under mild assumptions, we show uniform sampling is superior to weighted sampling for both the mini-batch and sparsifier approaches. We further verify empirically that these assumptions hold across various datasets. Unlike weighted sampling, uniform sampling is simple to implement and several orders of magnitude faster, making it ideal for handling 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},
}
Figure