Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference
Yatao (An) Bian · Joachim Buhmann · Andreas Krause

Tue Jun 11th 12:05 -- 12:10 PM @ Room 104

Mean field inference for discrete graphical models is generally a highly nonconvex problem, which also holds for the class of probabilistic log-submodular models. 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 baselines on both synthetic and real-world datasets.

Author Information

Yatao (An) Bian (ETH Zürich)
Joachim Buhmann (ETH Zurich)
Andreas Krause (ETH Zurich)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors