Seminar by Nisheeth Vishnoi
Entropy, Optimization and Counting
Nisheeth Vishnoi
Microsoft Research, India
Date: Monday, May 19th, 2014
Time: 11:00 AM
Venue: CS102.Abstract:
In this talk I will discuss the problem of computing max-entropy distributions over a discrete set of objects subject to observed marginals. For instance, given a bipartite graph and a positive number for every edge, can we compute a probability distribution that maximizes entropy over the set of perfect matchings in the graph whose marginals are the given numbers for the edges?
There has been a tremendous amount of interest in such distributions due to their applicability in areas such as statistical physics, economics, biology, information theory, machine learning, combinatorics and algorithms. However, a rigorous and systematic study of how to compute such distributions has been lacking. Since the underlying set of discrete objects can be exponential in the input size, the first question is whether max-entropy distributions have polynomially-sized descriptions. We start by giving a structural result which shows that such succinct descriptions exist under very general conditions. Subsequently, we use techniques from convex programming to give a meta-algorithm that can efficiently (approximately) compute max-entropy distributions provided one can efficiently (approximately) count the underlying discrete set. Thus, we can translate a host of existing counting algorithms, developed in an unrelated context, into algorithms that compute max-entropy distributions.
Conversely, we prove that counting oracles are necessary for computing max-entropy distributions: namely, we show how algorithms that compute max-entropy distributions can be converted into counting algorithms.
Joint work with Mohit Singh.