Faculty Recruiting Support CICS

High-Dimensional Discrete Integration by Hashing and Optimization

06 Feb
Wednesday, 02/06/2019 12:15pm to 1:15pm
Computer Science Building Room 140
Theory Seminar
Speaker: Raj Kumar Maity

Large scale counting problem such as computing the permanent of a matrix or computing the partition function of a probabilistic graphical model, come up often in different inference task. Recently Ermon et. al . (2013 ) pioneered a practical way of approximately computing such large scale counting and discrete integration problem. Hashes are used to reduce the problem into separate discrete optimization problem that are solved by an NP-oracle such as SAT solver or Integer linear programming Solver.  If the domain of the problem is \{0,1\}^n then a factor of 16 approximation can be achieved by the technique of Ermon et. al. .

But in many crucial counting task such as Potts Model the domain of the integration is a hypergrid , (\{0,1,...,q-1\}^n where q>2).  The straightforward extension of the Ermon's method will find a solution in a factor of q^2. We show an improved method to obtain a factor of 4+O(1/q^2) to this problem by optimizing over multiple bin of the hash functions. This method is easily implementable  using inequality constraint in the solver or even in a unconstrained way.

Faculty Host