Timezone: »
Poster
Linear programming analysis of loopy belief propagation for weighted matching
Sujay Sanghavi · Dmitry Malioutov · Alan S Willsky
Loopy belief propagation has been employed in a wide variety of applications with great empirical success, but it comes with few theoretical guarantees. In this paper we investigate the use of the max-product form of belief propagation for weighted matching problems on general graphs. We show that max-product converges to the correct answer if the linear programming (LP) relaxation of the weighted matching problem is tight and does not converge if the LP relaxation is loose. This provides an exact characterization of max-product performance and reveals connections to the widely used optimization technique of LP relaxation. In addition, we demonstrate that max-product is effective in solving practical weighted matching problems in a distributed fashion by applying it to the problem of self-organization in sensor networks.
Author Information
Sujay Sanghavi (UT-Austin)
Dmitry Malioutov (DE Shaw Group)
Alan S Willsky (Massachusetts Institute of Technology)
More from the Same Authors
-
2022 : Differentially Private Federated Learning with Normalized Updates »
Rudrajit Das · Abolfazl Hashemi · Sujay Sanghavi · Inderjit Dhillon -
2022 Poster: Minimax Regret for Cascading Bandits »
Daniel Vial · Sujay Sanghavi · Sanjay Shakkottai · R. Srikant -
2022 Poster: Toward Understanding Privileged Features Distillation in Learning-to-Rank »
Shuo Yang · Sujay Sanghavi · Holakou Rahmanian · Jan Bakus · Vishwanathan S. V. N. -
2021 Poster: Nearly Horizon-Free Offline Reinforcement Learning »
Tongzheng Ren · Jialian Li · Bo Dai · Simon Du · Sujay Sanghavi -
2019 Poster: Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space »
Shuo Yang · Yanyao Shen · Sujay Sanghavi -
2019 Poster: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Spotlight: Sparse Logistic Regression Learns All Discrete Pairwise Graphical Models »
Shanshan Wu · Sujay Sanghavi · Alex Dimakis -
2019 Poster: Iterative Least Trimmed Squares for Mixed Linear Regression »
Yanyao Shen · Sujay Sanghavi -
2019 Poster: Blocking Bandits »
Soumya Basu · Rajat Sen · Sujay Sanghavi · Sanjay Shakkottai -
2019 Poster: Learning Distributions Generated by One-Layer ReLU Networks »
Shanshan Wu · Alex Dimakis · Sujay Sanghavi -
2018 : Poster Session »
Sujay Sanghavi · Vatsal Shah · Yanyao Shen · Tianchen Zhao · Yuandong Tian · Tomer Galanti · Mufan Li · Gilad Cohen · Daniel Rothchild · Aristide Baratin · Devansh Arpit · Vagelis Papalexakis · Michael Perlmutter · Ashok Vardhan Makkuva · Pim de Haan · Yingyan Lin · Wanmo Kang · Cheolhyoung Lee · Hao Shen · Sho Yaida · Dan Roberts · Nadav Cohen · Philippe Casgrain · Dejiao Zhang · Tengyu Ma · Avinash Ravichandran · Julian Emilio Salazar · Bo Li · Davis Liang · Christopher Wong · Glen Bigan Mbeng · Animesh Garg -
2016 Poster: Single Pass PCA of Matrix Products »
Shanshan Wu · Srinadh Bhojanapalli · Sujay Sanghavi · Alex Dimakis -
2016 Poster: Normalized Spectral Map Synchronization »
Yanyao Shen · Qixing Huang · Nati Srebro · Sujay Sanghavi -
2015 Poster: Convergence Rates of Active Learning for Maximum Likelihood Estimation »
Kamalika Chaudhuri · Sham Kakade · Praneeth Netrapalli · Sujay Sanghavi -
2014 Poster: Non-convex Robust PCA »
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain -
2014 Spotlight: Non-convex Robust PCA »
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain -
2014 Poster: Greedy Subspace Clustering »
Dohyung Park · Constantine Caramanis · Sujay Sanghavi -
2013 Poster: Learning Gaussian Graphical Models with Observed or Latent FVSs »
Ying Liu · Alan S Willsky -
2013 Poster: Analyzing Hogwild Parallel Gaussian Gibbs Sampling »
Matthew Johnson · James Saunderson · Alan S Willsky -
2013 Poster: Phase Retrieval using Alternating Minimization »
Praneeth Netrapalli · Prateek Jain · Sujay Sanghavi -
2012 Poster: Clustering Sparse Graphs »
Yudong Chen · Sujay Sanghavi · Huan Xu -
2011 Poster: High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions »
Animashree Anandkumar · Vincent Tan · Alan S Willsky -
2011 Oral: High-Dimensional Graphical Model Selection: Tractable Graph Families and Necessary Conditions »
Animashree Anandkumar · Vincent Tan · Alan S Willsky -
2010 Workshop: Robust Statistical Learning »
Pradeep Ravikumar · Constantine Caramanis · Sujay Sanghavi -
2010 Oral: A Dirty Model for Multi-task Learning »
Ali Jalali · Pradeep Ravikumar · Sujay Sanghavi · Chao Ruan -
2010 Poster: Robust PCA via Outlier Pursuit »
Huan Xu · Constantine Caramanis · Sujay Sanghavi -
2010 Poster: A Dirty Model for Multi-task Learning »
Ali Jalali · Pradeep Ravikumar · Sujay Sanghavi · Chao Ruan -
2009 Poster: Sharing Features among Dynamical Systems with Beta Processes »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2009 Oral: Sharing Features among Dynamical Systems with Beta Processes »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2008 Poster: Nonparametric Bayesian Learning of Switching Linear Dynamical Systems »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2008 Spotlight: Nonparametric Bayesian Learning of Switching Linear Dynamical Systems »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2007 Spotlight: Message Passing for Max-weight Independent Set »
Sujay Sanghavi · Devavrat Shah · Alan S Willsky -
2007 Poster: Message Passing for Max-weight Independent Set »
Sujay Sanghavi · Devavrat Shah · Alan S Willsky -
2007 Poster: Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis »
Venkat Chandrasekaran · Jason K Johnson · Alan S Willsky -
2007 Poster: Loop Series and Bethe Variational Bounds in Attractive Graphical Models »
Erik Sudderth · Martin J Wainwright · Alan S Willsky