Mini-batch Submodular Maximization

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. Under mild assumptions, we show that 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.