How to calculate partition functions using convex programming hierarchies: provable bounds for variational methods
We consider the problem of approximating partition functions for Ising models. We make use of recent tools in combinatorial optimization: the Sherali-Adams and Lasserre convex programming hierarchies, in combination with variational methods to get algorithms for calculating partition functions in these families. These techniques give new, non-trivial approximation guarantees for the partition function beyond the regime of correlation decay. They also generalize some classical results from statistical physics about the Curie-Weiss ferromagnetic Ising model, as well as provide a partition function counterpart of classical results about max-cut on dense graphs \cite{arora1995polynomial}. With this, we connect techniques from two apparently disparate research areas -- optimization and counting/partition function approximations. (i.e. \#-P type of problems). Furthermore, we design to the best of our knowledge the first provable, convex variational methods. Though in the literature there are a host of convex versions of variational methods \cite{wainwright2003tree, wainwright2005new, heskes2006convexity, meshi2009convexifying}, they come with no guarantees (apart from some extremely special cases, like e.g. the graph has a single cycle \cite{weiss2000correctness}). We consider dense and low threshold rank graphs, and interestingly, the reason our approach works on these types of graphs is because local correlations propagate to global correlations -- completely the opposite of algorithms based on correlation decay. In the process we design novel entropy approximations based on the low-order moments of a distribution. Our proof techniques are very simple and generic, and likely to be applicable to many other settings other than Ising models.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
Scalable Models for Computing Hierarchies in Information Networks
Information hierarchies are organizational structures that often used to organize and present large and complex information as well as provide a mechanism for effective human navigation. Fortunately, many statistical and…
Multiresolution hierarchy co-clustering for semantic segmentation in sequences with small variations
This paper presents a co-clustering technique that, given a collection of images and their hierarchies, clusters nodes from these hierarchies to obtain a coherent multiresolution representation of the image collection. W…
Boundary DetectionClusteringSemantic SegmentationVideo Segmentation+1Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. The approach balances model size and tightness by partitioning node inputs into a number of groups and forming the convex hull…
Nuclear Partition Functions at Temperatures Exceeding 10^10 K
Nuclear partition functions were calculated for a grid of temperatures from 1.2x10^10 K to 2.75x10^11 K (1<=kT<=24 MeV) within a Fermi-gas approach, including all nuclides from the proton-dripline to the neutron-dripline…
Robust DNN Partitioning and Resource Allocation Under Uncertain Inference Time
In edge intelligence systems, deep neural network (DNN) partitioning and data offloading can provide real-time task inference for resource-constrained mobile devices. However, the inference time of DNNs is typically unce…
CPUGPU