Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
arXiv:1805.07482
Abstract
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.
arXiv comment28 pages
References in corpus (10)
- Determinantal point processes for machine learning
- Near-optimal Nonmyopic Value of Information in Graphical Models
- Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
- Online Continuous Submodular Maximization
- Submodular Functions: from Discrete to Continous Domains
- Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
- A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns
- Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
- Continuous DR-submodular Maximization: Structure and Algorithms
- Information theoretic model validation for clustering
Cited by in corpus (9)
- One Sample Stochastic Frank-Wolfe
- Parallel Algorithm for Non-Monotone DR-Submodular Maximization
- A Parallel Double Greedy Algorithm for Submodular Maximization
- Non-monotone DR-submodular Maximization: Approximation and Regret Guarantees
- Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
- Black Box Submodular Maximization: Discrete and Continuous Settings
- Submodular + Concave
- Scalable Projection-Free Optimization
- Competitive Algorithms for Online Budget-Constrained Continuous DR-Submodular Problems