THE CONFERENCE
FOR AUTHORS
FOR PARTICIPANTS

Timezone: »

 
Poster
Exact MAP Inference by Avoiding Fractional Vertices
Erik Lindgren · Alexandros Dimakis · Adam Klivans

Tue Aug 08 01:30 AM -- 05:00 AM (PDT) @ Gallery #34
in Posters Tue »

Given a graphical model, one essential problem is MAP inference, that is, finding the most likely configuration of states according to the model. Although this problem is NP-hard, large instances can be solved in practice and it is a major open question is to explain why this is true. We give a natural condition under which we can provably perform MAP inference in polynomial time---we require that the number of fractional vertices in the LP relaxation exceeding the optimal solution is bounded by a polynomial in the problem size. This resolves an open question by Dimakis, Gohari, and Wainwright. In contrast, for general LP relaxations of integer programs, known techniques can only handle a constant number of fractional vertices whose value exceeds the optimal solution. We experimentally verify this condition and demonstrate how efficient various integer programming methods are at removing fractional solutions.

Author Information

Erik Lindgren (University of Texas at Austin)
Alexandros Dimakis (UT Austin)

Alex Dimakis is an Associate Professor at the Electrical and Computer Engineering department, University of Texas at Austin. He received his Ph.D. in electrical engineering and computer sciences from UC Berkeley. He received an ARO young investigator award in 2014, the NSF Career award in 2011, a Google faculty research award in 2012 and the Eli Jury dissertation award in 2008. He is the co-recipient of several best paper awards including the joint Information Theory and Communications Society Best Paper Award in 2012. His research interests include information theory, coding theory and machine learning.

Adam Klivans (University of Texas at Austin)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors