# Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2020.

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

- [A low-rank ensemble Kalman filter for elliptic observations](https://mlsanity.com/paper/2203.05120/) (2022)
- [Expected information gain estimation via density approximations: Sample allocation and dimension reduction](https://mlsanity.com/paper/2411.08390/) (2024)
- [Nonlinear Bayesian optimal experimental design using logarithmic Sobolev inequalities](https://mlsanity.com/paper/2402.15053/) (2024)
- [Sequential Bayesian Optimal Experimental Design in Infinite Dimensions via Policy Gradient Reinforcement Learning](https://mlsanity.com/paper/2601.05868/) (2026)

## Abstract (arXiv)

We propose and analyze batch greedy heuristics for cardinality constrained maximization of non-submodular non-decreasing set functions. We consider the standard greedy paradigm, along with its distributed greedy and stochastic greedy variants. Our theoretical guarantees are characterized by the combination of submodularity and supermodularity ratios. We argue how these parameters define tight modular bounds based on incremental gains, and provide a novel reinterpretation of the classical greedy algorithm using the minorize-maximize (MM) principle. Based on that analogy, we propose a new class of methods exploiting any plausible modular bound. In the context of optimal experimental design for linear Bayesian inverse problems, we bound the submodularity and supermodularity ratios when the underlying objective is based on mutual information. We also develop novel modular bounds for the mutual information in this setting, and describe certain connections to polyhedral combinatorics. We discuss how algorithms using these modular bounds relate to established statistical notions such as leverage scores and to more recent efforts such as volume sampling. We demonstrate our theoretical findings on synthetic problems and on a real-world climate monitoring example.