Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain

Xiangru Huang, Ian En-Hsu Yen, Ruohan Zhang, Qixing Huang, Pradeep Ravikumar, Inderjit S. DhillonAISTATS 2017 · OpenReview

Abstract

Maximum-a-Posteriori (MAP) inference is a fundamental task in graphical models and structured prediction. While Linear Programming (LP) relaxations provide a powerful framework for approximate inference, they often become computationally intractable when the output domain is large. This paper introduces GDMM (Greedy Direction Method of Multiplier), an algorithm that combines Augmented Lagrangian methods with an active-set strategy and greedy variable selection. GDMM achieves orders-of-magnitude speedups and significant memory savings compared to traditional LP solvers by focusing on a small, relevant fraction of labels.

Introduction

In fields such as computer vision and computational biology, MAP inference is used to find the most likely configuration of a system. For instance, in protein folding, the goal is to determine the most probable 3D orientation for each amino acid. However, as the number of possible labels per variable grows, the complexity of pairwise factors increases quadratically, often leading to intractable memory requirements and slow convergence for standard optimization algorithms.

Methodology: The GDMM Approach

GDMM addresses the scalability bottleneck by treating MAP inference through the lens of the Augmented Lagrangian Method (ALM). The core innovations include:

  1. Active Set Strategy: Instead of optimizing over the entire label space, GDMM maintains a small "active set" of currently relevant labels for each variable.
  2. Greedy Direction Updates: The algorithm employs greedy optimization techniques, such as variants of Frank-Wolfe and Block-Greedy Coordinate Descent, to efficiently select new labels for the active set.
  3. Sublinear Search: By utilizing pre-built data structures like sorted lists of local scores, GDMM identifies the most promising greedy directions in sublinear time, avoiding exhaustive scans of the label space.
  4. On-Demand Variable Instantiation: Variables and factors are introduced only when required by the optimization process, maintaining a sparse internal representation.

The authors provide two algorithmic variants: one optimized for large label sets per variable and another for problems with a massive number of binary factors, such as multi-label prediction.

Experimental Evaluation

GDMM was evaluated across five diverse benchmarks:

  • Protein Folding: Dense interactions with 404 states per variable.
  • Graph Matching: Social network data with 1,034 states per variable.
  • Segmentation & Image Alignment: Standard computer vision tasks from the PASCAL challenge.
  • MultiLabel Prediction: The EurLex dataset, featuring over 7.5 million factors.

Key Results

GDMM demonstrated superior performance, particularly on large-domain problems where traditional solvers often fail.

Performance comparison of GDMM against state-of-the-art solvers across five benchmarks (a-e). GDMM (red line) consistently reaches lower primal gaps faster than competitors.

Speed and Scalability

On the Protein Folding task, GDMM reached the best objective in 661 seconds, significantly outperforming competitors like TRWS and MPLP, which either took over 10,000 seconds or failed to reach comparable solution quality. In the MultiLabel dataset with millions of factors, GDMM was the fastest to reach the optimal primal objective.

Memory Efficiency

Memory usage is a critical bottleneck for large-scale matching. While traditional solvers like AD3 or MPLP required over 100GB of RAM for the Graph Matching task, GDMM solved the same problem using only 260MB. This efficiency allows GDMM to run on standard hardware where other methods are unusable.

Relative Primal Gap vs. Time for the Graph Matching benchmark, highlighting GDMM's rapid convergence and efficiency in large state spaces.

Conclusion

GDMM provides a highly efficient and scalable framework for MAP inference in graphical models with massive label spaces. By mathematically exploiting the natural sparsity of real-world problems, it achieves significant gains in both speed and memory usage. Future research may explore hybridizing GDMM with tree-based message-passing algorithms to further improve performance on grid-structured problems.

Summary updated

Abstract

Maximum-a-Posteriori (MAP) inference lies at the heart of Graphical Models and Structured Prediction. Despite the intractability of exact MAP inference, approximated methods based on LP relaxations...
BibTeX
@inproceedings{huang2017greedy,
  author = {Xiangru Huang and Ian En-Hsu Yen and Ruohan Zhang and Qixing Huang and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=yQ7jk-TOSvy},
}
Figure