Vishesh Jain
ABSTRACT
The free energy is a key quantity of interest in Ising models, but unfortunately, computing it in general is computationally intractable. Two popular (variational) approximation schemes for estimating the free energy of general Ising models (in particular, even in regimes where correlation decay does not hold) are: (i) the mean-field approximation with roots in statistical physics, which estimates the free energy from below, and (ii) hierarchies of convex relaxations with roots in theoretical computer science, which estimate the free energy from above. We show, surprisingly, that the tight regime for both methods to compute the free energy to leading order is identical.
More precisely, we show that the mean-field approximation to the free energy is within O((n||J||F)2/3) of the true free energy, where ||J||F denotes the Frobenius norm of the interaction matrix of the Ising model. This simultaneously subsumes both the breakthrough work of Basak and Mukherjee, who showed the tight result that the mean-field approximation is within o(n) whenever ||J||F = o(√n), as well as the work of Jain, Koehler, and Mossel, who gave the previously best known non-asymptotic bound of O((n||J||F)2/3log1/3(n||J||F)). We give a simple, algorithmic proof of this result using a convex relaxation proposed by Risteski based on the Sherali-Adams hierarchy, automatically giving sub-exponential time approximation schemes for the free energy in this entire regime. Our algorithmic result is tight under Gap-ETH.
We furthermore combine our techniques with spin glass theory to prove (in a strong sense) the optimality of correlation rounding, refuting a recent conjecture of Allen, O’Donnell, and Zhou. Finally, we give the tight generalization of all of these results to k-MRFs, capturing as a special case previous work on approximating MAX-k-CSP.
- Nir Ailon and Noga Alon. 2007. Hardness of fully dense problems. Information and Computation 205, 8 (2007), 1117–1129. Google Scholar
Digital Library
- Michael Aizenman, Joel L Lebowitz, and David Ruelle. 1987.Google Scholar
- Some rigorous results on the Sherrington-Kirkpatrick spin glass model. Communications in mathematical physics 112, 1 (1987), 3–20.Google Scholar
- Sarah R Allen and Ryan O’Donnell. 2015.Google Scholar
- Conditioning and covariance on caterpillars. In Information Theory Workshop (ITW), 2015 IEEE. IEEE, 1–5.Google Scholar
- James Anderson and Carsten Peterson. 1987.Google Scholar
- A Mean Field Theory Learning Algorithm for Neural Networks. Complex Systems 1 (1987), 995–1019. Issue 5.Google Scholar
- Boaz Barak, Prasad Raghavendra, and David Steurer. 2011. Rounding semidefinite programming hierarchies via global correlation. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on. IEEE, 472–481. Google ScholarDigital Library
- Anirban Basak and Sumit Mukherjee. 2017. Universality of the mean-field for the Potts model. Probability Theory and Related Fields 168, 3-4 (2017), 557–600.Google ScholarCross Ref
- Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós, and Katalin Vesztergombi. 2012.Google Scholar
- Convergent sequences of dense graphs II. Multiway cuts and statistical physics. Annals of Mathematics 176, 1 (2012), 151–219.Google Scholar
- Amin Coja-Oghlan and Will Perkins. 2017. Bethe states of random factor graphs. arXiv preprint arXiv:1709.03827 (2017).Google Scholar
- Fernandez de la Vega and Marek Karpinski. 2006. Approximation Complexity of Nondense Instances of MAX-CUT. Electronic Colloquium on Computational Complexity (2006).Google Scholar
- TR06-101.Google Scholar
- Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu. 2007.Google Scholar
- Linear programming relaxations of maxcut. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 53–61. Google ScholarDigital Library
- Amir Dembo and Andrea Montanari. 2010.Google Scholar
- Ising models on locally tree-like graphs. Ann. Appl. Probab. 20, 2 (2010), 565–592. 09-AAP627Google Scholar
- Ronen Eldan. 2016.Google Scholar
- Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. arXiv preprint arXiv:1612.04346 (2016).Google Scholar
- Ronen Eldan and Renan Gross. 2018. Decomposition of mean-field Gibbs distributions into product measures. Electronic Journal of Probability 23 (2018).Google Scholar
- Richard S Ellis and Charles M Newman. 1978.Google Scholar
- The statistics of Curie-Weiss models. Journal of Statistical Physics 19, 2 (1978), 149–161.Google Scholar
- Dimitris Fotakis, Michael Lampis, and Vangelis Th Paschos. 2016. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse. In 33rd Symposium on Theoretical Aspects of Computer Science.Google Scholar
- Alan Frieze and Ravi Kannan. 1999. Quick approximation to matrices and applications. Combinatorica 19, 2 (1999), 175–220.Google ScholarCross Ref
- Martin Grötschel, László Lovász, and Alexander Schrijver. 2012.Google Scholar
- Geometric algorithms and combinatorial optimization. Springer Science & Business Media.Google Scholar
- Venkatesan Guruswami and Ali Kemal Sinop. 2011. Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on. IEEE, 482–491. Google ScholarDigital Library
- Dmitry Ioffe and Yvan Velenik. 2000. A note on the decay of correlations under δ -pinning. Probability theory and related fields 116, 3 (2000), 379–389.Google Scholar
- Vishesh Jain, Frederic Koehler, and Elchanan Mossel. 2018. The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity. In Conference on Learning Theory (COLT).Google Scholar
- Vishesh Jain, Frederic Koehler, and Elchanan Mossel. 2018. The Vertex Sample Complexity of Free Energy is Polynomial. In Conference on Learning Theory (COLT).Google Scholar
- Vishesh Jain, Frederic Koehler, and Andrej Risteski. 2018. Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective. arXiv preprint arXiv:1808.07226 (2018).Google Scholar
- Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul. 1999.Google Scholar
- An introduction to variational methods for graphical models. Machine learning 37, 2 (1999), 183–233. Google ScholarDigital Library
- S Kirkpatrick and D Sherrington. 1975. Solvable model of a spin-glass. Phys. Rev. Lett 35, 26 (1975), 1792–1796.Google ScholarCross Ref
- Pasin Manurangsi and Prasad Raghavendra. 2017. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In Proceedings of ICALP, Vol. 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mean-Field Approximation, Convex Hierarchies, and. .. STOC ’19, June 23–26, 2019, Phoenix, AZ, USAGoogle Scholar
- Claire Mathieu and Warren Schudy. 2008. Yet Another Algorithm for Dense Max Cut: Go Greedy. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’08). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 176–182. http://dl.acm.org/citation.cfm?id=1347082. Google ScholarDigital Library
- 1347102Google Scholar
- Marc Mézard, Giorgio Parisi, and Miguel Virasoro. 1987.Google Scholar
- Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications. Vol. 9. World Scientific Publishing Company.Google Scholar
- Dmitry Panchenko. 2013.Google Scholar
- The Sherrington-Kirkpatrick model. Springer Science & Business Media.Google Scholar
- Giorgio Parisi. 1988.Google Scholar
- Statistical field theory. New York: Addison-Wesley.Google Scholar
- Prasad Raghavendra and Ning Tan. 2012.Google Scholar
- Andrej Risteski. 2016. How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods. In COLT.Google Scholar
- Allan Sly and Nike Sun. 2012. The computational hardness of counting in twospin models on d-regular graphs. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on. IEEE, 361–369. Google ScholarDigital Library
- Michel Talagrand. 2011.Google Scholar
- Michel Talagrand. 2011.Google Scholar
- Mean Field Models for Spin Glasses. Volume II: Advanced Replica-Symmetry and Low Temperature. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics {Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics}, Vol. 55. Springer, Heidelberg (2011b). ISBN.Google Scholar
- Martin J. Wainwright and Michael I. Jordan. 2008. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning 1(1-2) (2008), 1–305. Google ScholarDigital Library
- Eugene P Wigner. 1958. On the distribution of the roots of certain symmetric matrices. Annals of Mathematics (1958), 325–327.Google Scholar
Index Terms
- Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
Recommendations
Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate: Extended Abstract
SIGMETRICS '17 Abstracts: Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer SystemsIn this paper, we study the accuracy of mean-field approximation. We show that, under general conditions, the expectation of any performance functional converges at rate O(1/N) to its mean-field approximation. Our result applies for finite and infinite-...
Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate
Mean-field approximation is a powerful tool to study large-scale stochastic systems such as data-centers -- one example being the famous power of two-choice paradigm. It is shown in the literature that under quite general conditions, the empirical ...
Expected Values Estimated via Mean-Field Approximation are 1/N-Accurate: Extended Abstract
Performance evaluation reviewIn this paper, we study the accuracy of mean-field approximation. We show that, under general conditions, the expectation of any performance functional converges at rate O(1/N) to its mean-field approximation. Our result applies for finite and infinite-...
Comments