by , ,
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.
Reference:
Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference Y. Bian, J. M. Buhmann, A. KrauseIn Proc. International Conference on Machine Learning (ICML), 2019
Bibtex Entry:
@inproceedings{bian19optimal,
	Author = {Yatao Bian and Joachim M. Buhmann and Andreas Krause},
	Bibsource = {dblp computer science bibliography, https://dblp.org},
	Bib,
	Booktitle = {Proc. International Conference on Machine Learning (ICML)},
	Crossref = {DBLP:conf/icml/2019},
	Month = {June},
	Pages = {644--653},
	Timestamp = {Tue, 11 Jun 2019 15:37:38 +0200},
	Title = {Optimal Continuous DR-Submodular Maximization and Applications to Provable Mean Field Inference},
	Year = {2019}}