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

Yatao Bian, Joachim Buhmann, Andreas Krause
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:644-653, 2019.

Abstract

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, typically only find 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-bian19a, title = {Optimal Continuous {DR}-Submodular Maximization and Applications to Provable Mean Field Inference}, author = {Bian, Yatao and Buhmann, Joachim and Krause, Andreas}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {644--653}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/bian19a/bian19a.pdf}, url = {https://proceedings.mlr.press/v97/bian19a.html}, abstract = {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, typically only find 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.} }
Endnote
%0 Conference Paper %T Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference %A Yatao Bian %A Joachim Buhmann %A Andreas Krause %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-bian19a %I PMLR %P 644--653 %U https://proceedings.mlr.press/v97/bian19a.html %V 97 %X 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, typically only find 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.
APA
Bian, Y., Buhmann, J. & Krause, A.. (2019). Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:644-653 Available from https://proceedings.mlr.press/v97/bian19a.html.

Related Material