Mini-batch Submodular Maximization

Gregory SchwartzmanSubmission to ICLR 2024 · Withdrawn

Its authors withdrew this paper, so there is no full text to read or summarize.

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. The expected number of oracle evaluations of our algorithm only depends on the size of the ground set. Previous results require a number of oracle evaluations that either depend on $N$ or have a worst-case *exponential* dependence on the size of the ground set.
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