Mini-batch Submodular Maximization

TL;DR — We introduce a mini-batch algorithm for maximizing decomposable submodular functions that significantly improves over sparsifier based approaches.

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.