Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
This provides a solution for researchers and practitioners in machine learning dealing with inference in probabilistic models, though it is incremental as it builds on existing submodular optimization techniques.
The paper tackles the nonconvex problem of mean field inference in probabilistic models by proposing provable methods for log-submodular models and posterior agreement, achieving a 1/2 approximation ratio with linear time complexity.
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.