Sum-of-Squares Relaxations for Information Theory and Variational Inference
We consider extensions of the Shannon relative entropy, referred to as
f-divergences. Three classical related computational problems are typically
associated with these divergences: (a) estimation from moments, (b) computing
normalizing integrals, and (c) variational inference in probabilistic models.
These problems are related to one another through convex duality, and for all
them, there are many applications throughout data science, and we aim for
computationally tractable approximation algorithms that preserve properties of
the original problem such as potential convexity or monotonicity. In order to
achieve this, we derive a sequence of convex relaxations for computing these
divergences from non-centered covariance matrices associated with a given
feature vector: starting from the typically non-tractable optimal lower-bound,
we consider an additional relaxation based on ''sums-of-squares'', which is is
now computable in polynomial time as a semidefinite program, as well as further
computationally more efficient relaxations based on spectral information
divergences from quantum information theory. For all of the tasks above, beyond
proposing new relaxations, we derive tractable algorithms based on augmented
Lagrangians and first-order methods, and we present illustrations on
multivariate trigonometric polynomials and functions on the Boolean hypercube.