Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain
By Xiangru Huang, Ian En-Hsu Yen, Ruohan Zhang, Qi-Xing Huang, Pradeep Ravikumar, Inderjit S. Dhillon. 2017
5 citations recorded by the source corpus.
Maximum-a-Posteriori (MAP) inference lies at the heart of Graphical Models and Structured Prediction. Despite the intractability of exact MAP inference, approximate methods based on LP relaxations have exhibited superior performance across a wide range of applications. Yet for problems involving large output domains (i.e., the state space for each variable is large), standard LP relaxations can easily give rise to a large number of variables and constraints which are beyond the limit of existing optimization algorithms. In this paper, we introduce an effective MAP inference method for problems with large output domains. The method builds upon alternating minimization of an Augmented Lagrangian that exploits the sparsity of messages through greedy optimization techniques. A key feature of our greedy approach is to introduce variables in an on-demand manner with a pre-built data structure over local factors. This results in a single-loop algorithm of sublinear cost per iteration and O(log(1/ε))-type iteration complexity to achieve ε sub-optimality. In addition, we introduce a variant of GDMM for binary MAP inference problems with a large number of factors. Empirically, the proposed algorithms demonstrate orders of magnitude speedup over state-of-the-art MAP inference techniques on MAP inference problems including Segmentation, Protein Folding, Graph Matching, and Multilabel prediction with pairwise interaction.
Subfields: Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Optimization & Training
- Fabian Pedregosa
- Gauthier Gidel
- Simon Lacoste-Julien
- Peter Richtárik
- Martin Jaggi
- Sebastian U. Stich
- Nicolas Loizou
- Sebastian Pokutta
Citations in the corpus
- Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “In their work, Yen et al. (2016a,b); Huang et al. (2017) only provide a rate on both gaps (9) and (10) which is not sufficient to derive guarantees on either how close an iterate is to the optimal set or how small is the suboptimality of the closest feasible point.”