# Regularized Submodular Maximization at Scale

arXiv: https://arxiv.org/abs/2002.03503 · HTML: https://mlsanity.com/paper/2002.03503/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2020.

## Built on by (most cited first, 15 of 15)

- [Infinite Recommendation Networks: A Data-Centric Approach](https://mlsanity.com/paper/2206.02626/) (2022)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach](https://mlsanity.com/paper/2206.03718/) (2022)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Farzi Data: Autoregressive Data Distillation](https://mlsanity.com/paper/2310.09983/) (2023)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising](https://mlsanity.com/paper/2109.15180/) (2021)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)
- [Procurement Auctions via Approximately Optimal Submodular Optimization](https://mlsanity.com/paper/2411.13513/) (2024)
- [Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions](https://mlsanity.com/paper/2605.07902/) (2026)

## Abstract (arXiv)

In this paper, we propose scalable methods for maximizing a regularized submodular function f = g - ℓ expressed as the difference between a monotone submodular function g and a modular function ℓ. 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)≥(φ-2-ε) · g(OPT)-ℓ (OPT), where φ is the golden ratio. Furthermore, we develop the first distributed algorithm that returns a solution S with the guarantee that mathbbE[f(S)] ≥ (1-ε) [(1-e-1) · g(OPT)-ℓ(OPT)] in O(1/ ε) 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 ℓ is zero, improves the memory and communication complexity of the existing work by a factor of O(1/ ε) 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.