Regularized Submodular Maximization at Scale
  In this paper, we propose scalable methods for maximizing a regularized
submodular function $f = g - \ell$ expressed as the difference between a
monotone submodular function $g$ and a modular function $\ell$. Indeed,
submodularity is inherently related to the notions of diversity, coverage, and
representativeness. In particular, finding the mode of many popular
probabilistic models of diversity, such as determinantal point processes,
submodular probabilistic models, and strongly log-concave distributions,
involves maximization of (regularized) submodular functions. Since a
regularized function $f$ can potentially take on negative values, the classic
theory of submodular maximization, which heavily relies on the non-negativity
assumption of submodular functions, may not be applicable. To circumvent this
challenge, we develop the first one-pass streaming algorithm for maximizing a
regularized submodular function subject to a $k$-cardinality constraint. It
returns a solution $S$ with the guarantee that $f(S)\geq(\phi^{-2}-\epsilon)
\cdot g(OPT)-\ell (OPT)$, where $\phi$ is the golden ratio. Furthermore, we
develop the first distributed algorithm that returns a solution $S$ with the
guarantee that $\mathbb{E}[f(S)] \geq (1-\epsilon) [(1-e^{-1}) \cdot
g(OPT)-\ell(OPT)]$ in $O(1/ \epsilon)$ rounds of MapReduce computation, without
keeping multiple copies of the entire dataset in each round (as it is usually
done). We should highlight that our result, even for the unregularized case
where the modular term $\ell$ is zero, improves the memory and communication
complexity of the existing work by a factor of $O(1/ \epsilon)$ while arguably
provides a simpler distributed algorithm and a unifying analysis. We also
empirically study the performance of our scalable methods on a set of real-life
applications, including finding the mode of distributions, data summarization,
and product recommendation.
