Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Energy Gap
Graphical Model
Lp Relaxation
Map Estimation
Message Passing
Potential Function
Randomized Rounding
Linear Program
Markov Random Field
Subscribe
Academic
Publications
Messagepassing for Graphstructured Linear Programs: Proximal Methods and Rounding Schemes
Messagepassing for Graphstructured Linear Programs: Proximal Methods and Rounding Schemes,10.1145/1756006.1756040,Journal of Machine Learning Resear
Edit
Messagepassing for Graphstructured Linear Programs: Proximal Methods and Rounding Schemes
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Pradeep Ravikumar
,
Alekh Agarwal
,
Martin J. Wainwright
The problem of computing a maximum a posteriori (MAP) configuration is a central computational challenge associated with Markov random fields. A line of work has focused on "treebased" linear programming (LP) relaxations for the MAP problem. This paper develops a family of superlinearly convergent algorithms for solving these LPs, based on proximal minimization schemes using Bregman divergences. As with standard message passing on graphs, the algorithms are distributed and exploit the underlying graphical structure, and so scale well to large problems. Our algorithms have a doubleloop char acter, with the outer loop corresponding to the proximal sequence, and an inner loop of cyclic Bregman divergences used to compute each proximal update. Di!erent choices of the Bregman divergence lead to conceptually related but distinct LPsolving algorithms. We establish convergence guarantees for our algorithms, and illustrate their performance via some simulations. We also develop two classes of graphstructured rounding schemes, randomized and deterministic, for obtaining integral configurations from the LP solu tions. Our deterministic rounding schemes use a "reparameterization" property of our algorithms so that when the LP solution is integral, the MAP solution can be obtained even before the LPsolver converges to the optimum. We also propose a graphstructured
randomized rounding
scheme that applies to iterative LP solving algorithms in general. We analyze the performance of our rounding schemes, giving bounds on the number of iterations required, when the LP is integral, for the rounding schemes to obtain the MAP solution. These bounds are expressed in terms of the strength of the potential functions, and the energy gap, which measures how well the integral MAP solution is separated from other integral configurations. We also report simulations comparing these rounding schemes.
Journal:
Journal of Machine Learning Research  JMLR
, vol. 11, pp. 10431080, 2010
DOI:
10.1145/1756006.1756040
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
jmlr.csail.mit.edu
)
(
doi.acm.org
)
(
www.informatik.unitrier.de
)
(
www.eecs.berkeley.edu
)
(
www.stat.berkeley.edu
)
(
statwww.berkeley.edu
)
More »
Citation Context
(1)
...lem, smoothing of the objective was proposed in a series of papers [5, 6,
15
, 23]...
Bogdan Savchynskyy
,
et al.
A study of Nesterov's scheme for Lagrangian decomposition and MAP labe...
References
(44)
BeliefPropagation for Weighted bMatchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
(
Citations: 17
)
Mohsen BayatiChristian
,
Christian Borgs
,
Jennifer T. Chayes
,
Riccardo Zecchina
Journal:
Computing Research Repository  CORR
, vol. abs/0709.1, 2007
Parallel and Distributed Computation: Numerical Methods
(
Citations: 1747
)
D. P. Bertsekas
,
J. N. Tsitsiklis
Published in 1989.
Introduction to Linear Optimization
(
Citations: 619
)
Dimitris Bertsimas
,
John Tsitsiklis
Published in 1997.
On the statistical analysis of dirty pictures
(
Citations: 1645
)
JULIAN BESAG
Published in 1986.
Fast Approximate Energy Minimization via Graph Cuts
(
Citations: 1587
)
Yuri Boykov
,
Olga Veksler
,
Ramin Zabih
Conference:
International Conference on Computer Vision  ICCV
, pp. 377384, 1999
Sort by:
Citations
(1)
A study of Nesterov's scheme for Lagrangian decomposition and MAP labeling
(
Citations: 1
)
Bogdan Savchynskyy
,
Jorg Kappes
,
Stefan Schmidt
,
Christoph Schnorr
Conference:
Computer Vision and Pattern Recognition  CVPR
, pp. 18171823, 2011