Timezone: »
Variational methods are frequently used to approximate or bound the partition or likelihood function of a Markov random field. Methods based on mean field theory are guaranteed to provide lower bounds, whereas certain types of convex relaxations provide upper bounds. In general, loopy belief propagation (BP) provides (often accurate) approximations, but not bounds. We prove that for a class of attractive binary models, the value specified by any fixed point of loopy BP always provides a lower bound on the true likelihood. Empirically, this bound is much better than the naive mean field bound, and requires no further work than running BP. We establish these lower bounds using a loop series expansion due to Chertkov and Chernyak, which we show can be derived as a consequence of the tree reparameterization characterization of BP fixed points.
Author Information
Erik Sudderth (University of California, Irvine)
Martin J Wainwright (UC Berkeley)
Alan S Willsky (Massachusetts Institute of Technology)
More from the Same Authors
-
2021 Poster: Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints »
Henry C Bendekgey · Erik Sudderth -
2021 Poster: Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning »
Andrea Zanette · Martin J Wainwright · Emma Brunskill -
2017 Poster: Kernel Feature Selection via Conditional Covariance Minimization »
Jianbo Chen · Mitchell Stern · Martin J Wainwright · Michael Jordan -
2016 Poster: Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences »
Chi Jin · Yuchen Zhang · Sivaraman Balakrishnan · Martin J Wainwright · Michael Jordan -
2015 Poster: Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models »
Michael Hughes · William Stephenson · Erik Sudderth -
2013 Poster: Learning Gaussian Graphical Models with Observed or Latent FVSs »
Ying Liu · Alan S Willsky -
2013 Poster: Efficient Online Inference for Bayesian Nonparametric Relational Models »
Dae Il Kim · Prem Gopalan · David Blei · Erik Sudderth -
2013 Poster: Analyzing Hogwild Parallel Gaussian Gibbs Sampling »
Matthew Johnson · James Saunderson · Alan S Willsky -
2013 Poster: Memoized Online Variational Inference for Dirichlet Process Mixture Models »
Michael Hughes · Erik Sudderth -
2012 Poster: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright -
2012 Poster: Effective Split-Merge Monte Carlo Methods for Nonparametric Models of Sequential Data »
Michael Hughes · Emily Fox · Erik Sudderth -
2012 Poster: Communication-Efficient Algorithms for Statistical Optimization »
Yuchen Zhang · John Duchi · Martin J Wainwright -
2012 Poster: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2012 Poster: Truly Nonparametric Online Variational Inference for Hierarchical Dirichlet Processes »
Michael Bryant · Erik Sudderth -
2012 Oral: No voodoo here! Learning discrete graphical models via inverse covariance estimation »
Po-Ling Loh · Martin J Wainwright -
2012 Oral: Privacy Aware Learning »
John Duchi · Michael Jordan · Martin J Wainwright -
2012 Poster: Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright -
2012 Poster: Minimization of Continuous Bethe Approximations: A Positive Variation »
Jason Pacheco · Erik Sudderth -
2012 Poster: Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods »
John Duchi · Michael Jordan · Martin J Wainwright · Andre Wibisono -
2012 Poster: From Deformations to Parts: Motion-based Segmentation of 3D Objects »
Soumya Ghosh · Erik Sudderth · Matthew Loper · Michael J Black -
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 -
2011 Poster: A More Powerful Two-Sample Test in High Dimensions using Random Projection »
Miles Lopes · Laurent Jacob · Martin J Wainwright -
2011 Poster: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright -
2011 Poster: The Doubly Correlated Nonparametric Topic Model »
Dae Il Kim · Erik Sudderth -
2011 Oral: High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity »
Po-Ling Loh · Martin J Wainwright -
2011 Poster: Spatial distance dependent Chinese Restaurant Process for image segmentation »
Soumya Ghosh · Andrei B Ungureanu · Erik Sudderth · David Blei -
2010 Spotlight: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright -
2010 Poster: Distributed Dual Averaging In Networks »
John Duchi · Alekh Agarwal · Martin J Wainwright -
2010 Oral: Fast global convergence rates of gradient methods for high-dimensional statistical recovery »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright -
2010 Poster: Global seismic monitoring as probabilistic inference »
Nimar Arora · Stuart J Russell · Paul Kidwell · Erik Sudderth -
2010 Poster: Fast global convergence rates of gradient methods for high-dimensional statistical recovery »
Alekh Agarwal · Sahand N Negahban · Martin J Wainwright -
2010 Spotlight: Layered image motion with explicit occlusions, temporal consistency, and depth ordering »
Deqing Sun · Erik Sudderth · Michael J Black -
2010 Poster: Layered image motion with explicit occlusions, temporal consistency, and depth ordering »
Deqing Sun · Erik Sudderth · Michael J Black -
2009 Session: Oral session 9: Bayesian Analysis »
Erik Sudderth -
2009 Poster: Sharing Features among Dynamical Systems with Beta Processes »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2009 Poster: Information-theoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright -
2009 Poster: Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness »
Garvesh Raskutti · Martin J Wainwright · Bin Yu -
2009 Spotlight: Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness »
Garvesh Raskutti · Martin J Wainwright · Bin Yu -
2009 Spotlight: Information-theoretic lower bounds on the oracle complexity of convex optimization »
Alekh Agarwal · Peter Bartlett · Pradeep Ravikumar · Martin J Wainwright -
2009 Oral: Sharing Features among Dynamical Systems with Beta Processes »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2009 Poster: A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers »
Sahand N Negahban · Pradeep Ravikumar · Martin J Wainwright · Bin Yu -
2009 Oral: A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers »
Sahand N Negahban · Pradeep Ravikumar · Martin J Wainwright · Bin Yu -
2008 Oral: Shared Segmentation of Natural Scenes Using Dependent Pitman-Yor Processes »
Erik Sudderth · Michael Jordan -
2008 Poster: Nonparametric Bayesian Learning of Switching Linear Dynamical Systems »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2008 Poster: High-dimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan -
2008 Poster: Phase transitions for high-dimensional joint support recovery »
Sahand N Negahban · Martin J Wainwright -
2008 Poster: Shared Segmentation of Natural Scenes Using Dependent Pitman-Yor Processes »
Erik Sudderth · Michael Jordan -
2008 Spotlight: High-dimensional union support recovery in multivariate regression »
Guillaume R Obozinski · Martin J Wainwright · Michael Jordan -
2008 Spotlight: Phase transitions for high-dimensional joint support recovery »
Sahand N Negahban · Martin J Wainwright -
2008 Spotlight: Nonparametric Bayesian Learning of Switching Linear Dynamical Systems »
Emily Fox · Erik Sudderth · Michael Jordan · Alan S Willsky -
2008 Session: Oral session 4: Combinatorial Approximation »
Erik Sudderth -
2008 Poster: Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \ell_1-regularizedMLE »
Pradeep Ravikumar · Garvesh Raskutti · Martin J Wainwright · Bin Yu -
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 Spotlight: Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization »
XuanLong Nguyen · Martin J Wainwright · Michael Jordan -
2007 Poster: Estimating divergence functionals and the likelihood ratio by penalized convex risk minimization »
XuanLong Nguyen · Martin J Wainwright · Michael Jordan -
2007 Poster: Adaptive Embedded Subgraph Algorithms using Walk-Sum Analysis »
Venkat Chandrasekaran · Jason K Johnson · Alan S Willsky -
2007 Poster: Linear programming analysis of loopy belief propagation for weighted matching »
Sujay Sanghavi · Dmitry Malioutov · Alan S Willsky -
2006 Poster: Inferring Graphical Model Structure using $\ell_1$-Regularized Pseudo-Likelihood »
Martin J Wainwright · Pradeep Ravikumar · John Lafferty -
2006 Spotlight: Inferring Graphical Model Structure using $\ell_1$-Regularized Pseudo-Likelihood »
Martin J Wainwright · Pradeep Ravikumar · John Lafferty