# Adaptive Regularized Submodular Maximization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 28 Feb 2021.

## Builds on (most cited first, 8 of 8)

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)
- [No Time to Observe: Adaptive Influence Maximization with Partial Feedback](https://mlsanity.com/paper/1609.00427/) (2016)

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

- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)
- [Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization](https://mlsanity.com/paper/2309.05183/) (2023)
- [Procurement Auctions via Approximately Optimal Submodular Optimization](https://mlsanity.com/paper/2411.13513/) (2024)
- [Worst-Case Adaptive Submodular Cover](https://mlsanity.com/paper/2210.13694/) (2022)

## Abstract (arXiv)

In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and an non-negative modular (cost) function under the adaptive setting. The input of our problem is a set of n items, where each item has a particular state drawn from some known prior distribution p. The revenue function g is defined over items and states, and the cost function c is defined over items, i.e., each item has a fixed cost. The state of each item is unknown initially, one must select an item in order to observe its realized state. A policy π specifies which item to pick next based on the observations made so far. Denote by gavg(π) the expected revenue of π and let cavg(π) denote the expected cost of π. Our objective is to identify the best policy πo∈ argmaxπgavg(π)-cavg(π) under a k-cardinality constraint. Since our objective function can take on both negative and positive values, the existing results of submodular maximization may not be applicable. To overcome this challenge, we develop a series of effective solutions with performance grantees. Let πo denote the optimal policy. For the case when g is adaptive monotone and adaptive submodular, we develop an effective policy πl such that gavg(πl) - cavg(πl) ≥ (1-frac1e-ε)gavg(πo) - cavg(πo), using only O(nε-2log ε-1) value oracle queries. For the case when g is adaptive submodular, we present a randomized policy πr such that gavg(πr) - cavg(πr) ≥ frac1egavg(πo) - cavg(πo).