Document Open Access Logo

Harnessing the Bethe Free Energy

Authors Victor Bapst, Amin Coja-Oghlan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.467.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Victor Bapst
Amin Coja-Oghlan

Cite As Get BibTex

Victor Bapst and Amin Coja-Oghlan. Harnessing the Bethe Free Energy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 467-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.467

Abstract

Gibbs measures induced by random factor graphs play a prominent role in computer science, combinatorics and physics. A key problem is to calculate the typical value of the partition function. According to the "replica symmetric cavity method", a heuristic that rests on non-rigorous considerations from statistical mechanics, in many cases this problem can be tackled by way of maximising a functional called the "Bethe free energy". In this paper we prove that the Bethe free energy upper-bounds the partition function in a broad class of models. Additionally, we provide a sufficient condition for this upper bound to be tight.

Subject Classification

Keywords
  • Belief Propagation
  • free energy
  • Gibbs measure
  • partition function

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dimitris Achlioptas and Cristopher Moore. Random k-sat: Two moments suffice to cross a sharp threshold. SIAM J. Comput., 36(3):740-762, September 2006. Google Scholar
  2. Dimitris Achlioptas, Assaf Naor, and Yuval Peres. Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043):759-764, 06 2005. Google Scholar
  3. Dimitris Achlioptas, Assaf Naor, and Yuval Peres. On the maximum satisfiability of random formulas. J. ACM, 54(2), April 2007. Google Scholar
  4. Dimitris Achlioptas and Yuval Peres. The threshold for random k-sat is 2k (ln 2 - o(k)). In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC'03, pages 223-231, New York, NY, USA, 2003. ACM. Google Scholar
  5. H. A. Bethe. Statistical theory of superlattices. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 150(871):552-575, 1935. Google Scholar
  6. Charles Bordenave and Pietro Caputo. Large deviations of empirical neighborhood distribution in sparse random graphs. Probability Theory and Related Fields, pages 1-73, 2014. Google Scholar
  7. Amin Coja-Oghlan and Konstantinos Panagiotou. The asymptotic k-SAT threshold. arXiv:1310.2728, 2014. Google Scholar
  8. Amin Coja-Oghlan and Lenka Zdeborová. The condensation transition in random hypergraph 2-coloring. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 241-250, 2012. Google Scholar
  9. Amir Dembo, Andrea Montanari, Allan Sly, and Nike Sun. The replica symmetric solution for potts models on d-regular graphs. Communications in Mathematical Physics, 327(2):551-575, 2014. Google Scholar
  10. Amir Dembo, Andrea Montanari, and Nike Sun. Factor models on locally tree-like graphs. Ann. Probab., 41(6):4162-4213, 11 2013. Google Scholar
  11. Jian Ding, Allan Sly, and Nike Sun. Maximum independent sets on random regular graphs. arXiv:1310.4787, 2013. Google Scholar
  12. Jian Ding, Allan Sly, and Nike Sun. Proof of the satisfiability conjecture for large k. arXiv:1411.0650, 2014. Google Scholar
  13. Jian Ding, Allan Sly, and Nike Sun. Satisfiability threshold for random regular NAE-SAT. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 814-822, New York, NY, USA, 2014. ACM. Google Scholar
  14. Silvio Franz and Michele Leone. Replica bounds for optimization problems and diluted spin systems. J. Stat. Phys., 111(3-4):535-564, 2003. Google Scholar
  15. Alan Frieze and Nicholas C. Wormald. Random k-sat: A tight threshold for moderately growing k. In Proceedings of the Fifth International Symposium on Theory and Applications of Satisfiability Testing, pages 1-6, 2002. Google Scholar
  16. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 823-831, New York, NY, USA, 2014. ACM. Google Scholar
  17. R.G. Gallager. Low-density Parity-check Codes. M.I.T. Press research monographs. M.I.T. Press, 1963. Google Scholar
  18. H.O. Georgii. Gibbs Measures and Phase Transitions. De Gruyter studies in mathematics. De Gruyter, 2011. Google Scholar
  19. Francesco Guerra. Broken replica symmetry bounds in the mean field spin glass model. Communications in Mathematical Physics, 233(1):1-12, 2003. Google Scholar
  20. Svante Janson. Random regular graphs: Asymptotic distributions and contiguity. Combinatorics, Probability and Computing, 4:369-405, 12 1995. Google Scholar
  21. Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems. P. Natl. Acad. Sci. USA, 104(25):10318-10323, 2007. Google Scholar
  22. L. Lovász. Large Networks and Graph Limits. American Mathematical Society colloquium publications. American Mathematical Society, 2012. Google Scholar
  23. M. Mézard and A. Montanari. Information, Physics and Computation. Oxford University Press, 2009. Google Scholar
  24. M. Mézard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random satisfiability problems. Science, 297:812-815, 2002. Google Scholar
  25. Andrea Montanari and Devavrat Shah. Counting good truth assignments of random k-sat formulae. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'07, pages 1255-1264, Philadelphia, PA, USA, 2007. Google Scholar
  26. Elchanan Mossel, Dror Weitz, and Nicholas Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields, 143(3-4):401-439, 2009. Google Scholar
  27. Ralph Neininger and Ludger Rüschendorf. A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab., 14(1):378-418, 02 2004. Google Scholar
  28. Dmitry Panchenko and Michel Talagrand. Bounds for diluted mean-fields spin glass models. Probab. Theory Relat. Fields, 130(3):319-336, 2004. Google Scholar
  29. Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. Google Scholar
  30. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 0:361-369, 2012. Google Scholar
  31. Endre Szemerédi. Regular partitions of graphs. In Colloq. Internat. CNRS, volume 260, pages 399-401, 1978. Google Scholar
  32. Jonathan S. Yedidia, W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51(7):2282-2312, July 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact