Timezone: »
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 NPhard, 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 timewe 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 corecipient 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)

2017 Talk: Exact MAP Inference by Avoiding Fractional Vertices »
Tue. Aug 8th 12:30  12:48 AM Room C4.9& C4.10
More from the Same Authors

2023 Poster: RestorationDegradation Beyond Linear Diffusions: A NonAsymptotic Analysis For DDIMtype Samplers »
Sitan Chen · Giannis Daras · Alexandros Dimakis 
2022 Poster: ScoreGuided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis 
2022 Spotlight: ScoreGuided Intermediate Level Optimization: Fast Langevin Mixing for Inverse Problems »
Giannis Daras · Yuval Dagan · Alexandros Dimakis · Constantinos Daskalakis 
2021 : Invited Talk: Alex Dimakis »
Alexandros Dimakis 
2021 Poster: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis 
2021 Spotlight: Provable Lipschitz Certification for Generative Models »
Matt Jordan · Alexandros Dimakis 
2021 Poster: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price 
2021 Spotlight: Fairness for Image Generation with Uncertain Sensitive Attributes »
Ajil Jalal · Sushrut Karmalkar · Jessica Hoffmann · Alexandros Dimakis · Eric Price 
2021 Poster: Solving Inverse Problems with a Flowbased Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis 
2021 Spotlight: Solving Inverse Problems with a Flowbased Noise Model »
Jay Whang · Qi Lei · Alexandros Dimakis 
2021 Poster: InstanceOptimal Compressed Sensing via Posterior Sampling »
Ajil Jalal · Sushrut Karmalkar · Alexandros Dimakis · Eric Price 
2021 Poster: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis 
2021 Poster: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis 
2021 Spotlight: Intermediate Layer Optimization for Inverse Problems using Deep Generative Models »
Giannis Daras · Joseph Dean · Ajil Jalal · Alexandros Dimakis 
2021 Spotlight: InstanceOptimal Compressed Sensing via Posterior Sampling »
Ajil Jalal · Sushrut Karmalkar · Alexandros Dimakis · Eric Price 
2021 Spotlight: Composing Normalizing Flows for Inverse Problems »
Jay Whang · Erik Lindgren · Alexandros Dimakis 
2020 Poster: Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection »
Mao Ye · Chengyue Gong · Lizhen Nie · Denny Zhou · Adam Klivans · Qiang Liu 
2020 Poster: SGD Learns OneLayer Networks in WGANs »
Qi Lei · Jason Lee · Alexandros Dimakis · Constantinos Daskalakis 
2020 Poster: Superpolynomial Lower Bounds for Learning OneLayer Neural Networks using Gradient Descent »
Surbhi Goel · Aravind Gollakota · Zhihan Jin · Sushrut Karmalkar · Adam Klivans 
2019 : Alex Dimakis: Coding Theory for Distributed Learning »
Alexandros Dimakis 
2019 Poster: Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling »
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi · Felix Xinnan Yu · Daniel HoltmannRice · Dmitry Storcheus · Afshin Rostamizadeh · Sanjiv Kumar 
2019 Oral: Learning a Compressed Sensing Measurement Matrix via Gradient Unrolling »
Shanshan Wu · Alexandros Dimakis · Sujay Sanghavi · Felix Xinnan Yu · Daniel HoltmannRice · Dmitry Storcheus · Afshin Rostamizadeh · Sanjiv Kumar 
2018 Poster: Learning One Convolutional Layer with Overlapping Patches »
Surbhi Goel · Adam Klivans · Raghu Meka 
2018 Poster: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo 
2018 Oral: Gradient Coding from Cyclic MDS Codes and Expander Graphs »
Netanel Raviv · Rashish Tandon · Alexandros Dimakis · Itzhak Tamo 
2018 Oral: Learning One Convolutional Layer with Overlapping Patches »
Surbhi Goel · Adam Klivans · Raghu Meka 
2017 Poster: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai 
2017 Poster: CostOptimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath 
2017 Poster: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban 
2017 Talk: Identifying Best Interventions through Online Importance Sampling »
Rajat Sen · Karthikeyan Shanmugam · Alexandros Dimakis · Sanjay Shakkottai 
2017 Talk: On Approximation Guarantees for Greedy Low Rank Optimization »
RAJIV KHANNA · Ethan R. Elenberg · Alexandros Dimakis · Joydeep Ghosh · Sahand Negahban 
2017 Talk: CostOptimal Learning of Causal Graphs »
Murat Kocaoglu · Alexandros Dimakis · Sriram Vishwanath 
2017 Poster: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis 
2017 Poster: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis 
2017 Talk: Gradient Coding: Avoiding Stragglers in Distributed Learning »
Rashish Tandon · Qi Lei · Alexandros Dimakis · Nikos Karampatziakis 
2017 Talk: Compressed Sensing using Generative Models »
Ashish Bora · Ajil Jalal · Eric Price · Alexandros Dimakis