# Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2018.

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

- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)

## Abstract (arXiv)

Mean field inference in probabilistic models is generally a highly nonconvex problem. Existing optimization methods, e.g., coordinate ascent algorithms, can only generate local optima. In this work we propose provable mean filed methods for probabilistic log-submodular models and its posterior agreement (PA) with strong approximation guarantees. The main algorithmic technique is a new Double Greedy scheme, termed DR-DoubleGreedy, for continuous DR-submodular maximization with box-constraints. It is a one-pass algorithm with linear time complexity, reaching the optimal 1/2 approximation ratio, which may be of independent interest. We validate the superior performance of our algorithms against baseline algorithms on both synthetic and real-world datasets.