New Outer Bounds on the Marginal Polytope

By David A. Sontag, Tommi S. Jaakkola. 2007

159 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “For optimization overMδ , updating ρ realizes better marginals and bound on logZ (over and above those obtained in Sontag and Jaakkola (2007)).”
Determinantal Point Processes for Machine Learning (2012, methodology): “Indeed, such negative potentials can create “frustrated cycles”, which have been used both as illustrations of common MRF inference algorithm failures [82] and as targets for improving those algorithms [136].”
The Recurrent Temporal Restricted Boltzmann Machine (2008, background): “, [16, 12, 19], including [15], which works well for the RBM).”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, unknown): “The importance of relaxation LP MRF to MRF optimization and/ or its connection to message-passing methods has also been explored in some other interesting works (e.g., we point the interested reader to [52], [28], [43], [56] for more details).”
Tightening LP Relaxations for MAP using Message Passing (2008, methodology): “Algorithms such as our earlier cutting-plane algorithm [12] or CPLEX’s branch-and-cut algorithm require solving the primal LP relaxation at least once, but solving the primal LP on all but the smallest of the design problems is intractable [18].”
Learning and Evaluating Boltzmann Machines (2008, background): “Recently, [23, 22] proposed a cutting plane algorithm that solves for an upper bound of the logpartition function of Eq.”
Structure preserving embedding (2009, methodology): “Since we have a semidefinite program, these guarantees do not carry over immediately, although in practice the cutting plane algorithm works well and has also been successfully deployed in settings beyond structured prediction and quadratic programming ( Sontag & Jaakkola, 2008 ).”
Optimization for machine learning (2010, methodology): “First, primal methods were proposed (Koster et al., 1998; Sontag and Jaakkola, 2007; Sontag, 2007), then dual methods (Werner, 2008a, 2010; Kumar and Torr, 2008; Sontag et al.”
Automorphism Groups of Graphical Models and Lifted Variational Inference (2012, methodology): “To address this issue, we follow [14] and employ a cutting plane approach in which we find and add only the most violated lifted cycle constraint in each iteration (separation operation).”
Exact and Approximate Sampling by Systematic Stochastic Search (2009, background): “Many popular approaches to inference, such as mean-ﬁeld variational methods (Jordan et al., 1999), convex relaxations (Wainwright et al., 2002; Sontag and Jaakkola, 2008), and generalized belief propagation (Yedidia et al., 2001), focus on approximating MAP assignments or (low-dimensional, e.g. 1…”
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts (2009, unknown): “design move making algorithms for more complex relaxations such as [19, 28].”