Scalable Semidefinite Relaxation for Maximum A Posterior Estimation

Maximum a posteriori (MAP) inference over discrete Markov random fields is a fundamental task spanning a wide spectrum of real-world applications, which is known to be NP-hard for general graphs. In this paper, we propose a novel semidefinite relaxation formulation (referred to as SDR) to estimate the MAP assignment. Algorithmically, we develop an accelerated variant of the alternating direction method of multipliers (referred to as SDPAD-LR) that can effectively exploit the special structure of the new relaxation. Encouragingly, the proposed procedure allows solving SDR for large-scale problems, e.g., problems on a grid graph comprising hundreds of thousands of variables with multiple states per node. Compared with prior SDP solvers, SDPAD-LR is capable of attaining comparable accuracy while exhibiting remarkably improved scalability, in contrast to the commonly held belief that semidefinite relaxation can only been applied on small-scale MRF problems. We have evaluated the performance of SDR on various benchmark datasets including OPENGM2 and PIC in terms of both the quality of the solutions and computation time. Experimental results demonstrate that for a broad class of problems, SDPAD-LR outperforms state-of-the-art algorithms in producing better MAP assignment in an efficient manner.

• Publication year

  2014

• Venue

  International Conference on Machine Learning

• Publication date

  2014-05-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1405.4807
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SfM with MRFs: Discrete-Continuous Optimization for Large-Scale Structure from Motion

  2013cited by this paper
• Towards Efficient and Exact MAP-Inference for Large Scale Discrete Computer Vision Problems via Combinatorial Optimization

  2013influential reference
• A Fast Semidefinite Approach to Solving Binary Quadratic Problems

  2013cited by this paper
• Anytime AND/OR depth-first search for combinatorial optimization

  2012cited by this paper
• Approximate Inference by Intersecting Semidefinite Bound and Local Polytope

  2012influential reference
• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

  2012cited by this paper
• Discrete-continuous optimization for large-scale structure from motion

  2011cited by this paper
• Tighter Relaxations for MAP-MRF Inference: A Local Primal-Dual Gap based Separation Algorithm

  2011cited by this paper
• Dyson: An Architecture for Extensible Wireless LANs

  2010influential reference
• Message-passing for Graph-structured Linear Programs: Proximal Methods and Rounding Schemes

  2010cited by this paper
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  2010cited by this paper
• Alternating direction augmented Lagrangian methods for semidefinite programming

  2010influential reference
• Soft arc consistency revisited

  2010cited by this paper
• A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors

  2008influential reference
• Beyond Loose LP-Relaxations: Optimizing MRFs by Repairing Cycles

  2008cited by this paper
• Tightening LP Relaxations for MAP using Message Passing

  2008cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• An Analysis of Convex Relaxations for MAP Estimation

  2007influential reference
• Solving Large Scale Binary Quadratic Problems: Spectral Methods vs. Semidefinite Programming

  2007cited by this paper
• Convergent Tree-Reweighted Message Passing for Energy Minimization

  2006influential reference
• MAP estimation via agreement on trees: message-passing and linear programming

  2005cited by this paper
• DSDP5: Software for Semidefinite Programming

  2005cited by this paper
• An LP Formulation and Approximation Algorithms for the Metric Labeling Problem

  2004cited by this paper
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

  2003cited by this paper
• Solving Markov Random Fields using Semi Definite Programming

  2003cited by this paper
• A Spectral Bundle Method for Semidefinite Programming

  1999cited by this paper
• SDPT3 -- A Matlab Software Package for Semidefinite Programming

  1996cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• Finding MAPs for Belief Networks is NP-Hard

  1994cited by this paper
• Lanczos algorithms for large symmetric eigenvalue computations

  1985cited by this paper

• Sharp-Peak Functions for Exactly Penalizing Binary Integer Programming

  2025cites this paper
• Computing Binary Integer Programming via A New Exact Penalty Function

  2025cites this paper
• Pose Synchronization under Multiple Pair-wise Relative Poses

  2023cites this paper
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching

  2023cites this paper
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization

  2021cites this paper
• Conditional gradient methods for stochastically constrained convex minimization

  2020cites this paper
• LMI-based robust mixed-integer model predictive control for hybrid systems

  2020cites this paper
• Online state of charge estimation of Li-ion battery based on an improved unscented Kalman filter approach

  2019cites this paper
• Scalable Semidefinite Programming

  2019cites this paper
• Path-Invariance of Directed Map Networks

  2019cites this paper
• Tighter continuous relaxations for MAP inference in discrete MRFs: A survey

  2019influential citation
• Non-Unique Games Over Compact Groups and Applications

  2018cites this paper
• Joint Map and Symmetry Synchronization

  2018cites this paper
• Accelerated Inference in Markov Random Fields via Smooth Riemannian Optimization

  2018cites this paper
• Path-Invariant Map Networks

  2018cites this paper
• An Exact Penalty Method for Binary Optimization Based on MPEC Formulation

  2017cites this paper
• Data collection & preprocessing Feature extraction Learning Classification Regression Retrieval Segmentation Reconstruction Synthesis Processed or generated data with semantic information Clustering Inference ... ... Feature learning Belief propagation Bayesian inference Gibbs sampling

  2016influential citation
• Binary Optimization via Mathematical Programming with Equilibrium Constraints

  2016cites this paper
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

  2016cites this paper
• Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems

  2016cites this paper
• Graph matching with low-rank regularization

  2016cites this paper
• Efficient SDP inference for fully-connected CRFs based on low-rank decomposition

  2015cites this paper
• Data‐Driven Shape Analysis and Processing

  2015cites this paper
• Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference

  2014cites this paper
• Large-Scale Binary Quadratic Optimization Using Semidefinite Relaxation and Applications

  2014cites this paper