  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 improve over the sparsifier based approach both in theory and
in practice. We experimentally observe that our algorithm generates solutions
that are far superior to those generated by the sparsifier based approach.
