Timezone: »
Poster
A Convex Upper Bound on the LogPartition Function
Laurent El Ghaoui · Assane Gueye
We consider the problem of bounding from above the logpartition function corresponding to secondorder Ising models for binary distributions. We introduce a new bound, the cardinality bound, which can be computed via convex optimization. The corresponding error on the logpartition function is bounded above by twice the distance, in model parameter space, to a class of ``standard'' Ising models, for which variable interdependence is described via a simple mean field term. In the context of maximumlikelihood, using the new bound instead of the exact logpartition function, while constraining the distance to the class of standard Ising models, leads not only to a good approximation to the logpartition function, but also to a model that is parsimonious, and easily interpretable. We compare our bound with the logdeterminant bound introduced by Wainwright and Jordan (2006), and show that when the $l_1$norm of the model parameter vector is small enough, the latter is outperformed by the new bound.
Author Information
Laurent El Ghaoui (University of California at Berkeley)
Assane Gueye (University of California, Berkeley)
More from the Same Authors

2012 Poster: Recovery of Sparse Probability Measures via Convex Programming »
Mert Pilanci · Laurent El Ghaoui · Venkat Chandrasekaran 
2008 Poster: An Homotopy Algorithm for the Lasso with Online Observations »
Pierre Garrigues · Laurent El Ghaoui