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

摘要

Mean field inference in probabilistic models is generally a highly nonconvex problem. Existing optimization methods, e.g., coordinate ascent algorithms, typically only find local optima. In this work we propose provable mean field 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. This one-pass algorithm achieves the optimal 1/2 approximation ratio, which may be of independent interest. We validate the superior performance of our algorithms with baseline results on both synthetic and real-world datasets.