# Stochastic Submodular Maximization via Polynomial Estimators

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 17 Mar 2023.

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

- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification](https://mlsanity.com/paper/1812.00151/) (2018)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Stochastic Submodular Maximization: The Case of Coverage Functions](https://mlsanity.com/paper/1711.01566/) (2017)
- [Categorical Feature Compression via Submodular Optimization](https://mlsanity.com/paper/1904.13389/) (2019)
- [Kelly Cache Networks](https://mlsanity.com/paper/1901.04092/) (2019)
- [Submodular Maximization via Taylor Series Approximation](https://mlsanity.com/paper/2101.07423/) (2021)

## Abstract (arXiv)

In this paper, we study stochastic submodular maximization problems with general matroid constraints, that naturally arise in online learning, team formation, facility location, influence maximization, active learning and sensing objective functions. In other words, we focus on maximizing submodular functions that are defined as expectations over a class of submodular functions with an unknown distribution. We show that for monotone functions of this form, the stochastic continuous greedy algorithm attains an approximation ratio (in expectation) arbitrarily close to (1-1/e) ≈ 63% using a polynomial estimation of the gradient. We argue that using this polynomial estimator instead of the prior art that uses sampling eliminates a source of randomness and experimentally reduces execution time.