Variational Inference on the Boolean Hypercube with the Quantum Entropy
This work addresses inference challenges in probabilistic models for researchers in machine learning and statistics, though it appears incremental as it builds on existing variational and quantum relaxation techniques.
The paper tackles the problem of variational inference for pairwise Markov random fields on the Boolean hypercube by deriving upper bounds using quantum relaxations of the Kullback-Leibler divergence and proposing efficient primal-dual optimization algorithms, with extensive numerical experiments showing competitive results compared to state-of-the-art methods.
In this paper, we derive variational inference upper-bounds on the log-partition function of pairwise Markov random fields on the Boolean hypercube, based on quantum relaxations of the Kullback-Leibler divergence. We then propose an efficient algorithm to compute these bounds based on primal-dual optimization. An improvement of these bounds through the use of ''hierarchies,'' similar to sum-of-squares (SoS) hierarchies is proposed, and we present a greedy algorithm to select among these relaxations. We carry extensive numerical experiments and compare with state-of-the-art methods for this inference problem.