# Sum-of-Squares Relaxations for Information Theory and Variational Inference

arXiv: https://arxiv.org/abs/2206.13285 · HTML: https://mlsanity.com/paper/2206.13285/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 80 references that are in the map.
- First posted on arXiv 27 Jun 2022.

## Builds on (most cited first, 11 of 11)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Practical and Consistent Estimation of f-Divergences](https://mlsanity.com/paper/1905.11112/) (2019)
- [Change of measure through the Legendre transform](https://mlsanity.com/paper/2202.05568/) (2022)
- [Semidefinite approximations of the matrix logarithm](https://mlsanity.com/paper/1705.00812/) (2017)
- [The sum-of-squares hierarchy on the sphere, and applications in quantum information theory](https://mlsanity.com/paper/1908.05155/) (2019)
- [Sum-of-squares hierarchies for binary polynomial optimization](https://mlsanity.com/paper/2011.04027/) (2020)
- [Defining quantum divergences via convex optimization](https://mlsanity.com/paper/2007.12576/) (2020)

## Built on by (most cited first, 6 of 6)

- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Asymptotically Optimal Change Detection for Unnormalized Pre- and Post-Change Distributions](https://mlsanity.com/paper/2410.14615/) (2024)
- [Variational Inference on the Boolean Hypercube with the Quantum Entropy](https://mlsanity.com/paper/2411.03759/) (2024)
- [Learning Energy-Based Models by Self-normalising the Likelihood](https://mlsanity.com/paper/2503.07021/) (2025)
- [Convergence of linear programming hierarchies for Gibbs states of spin systems](https://mlsanity.com/paper/2506.06125/) (2025)

## Abstract (arXiv)

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. We also provide 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 convex optimization algorithms, and we present illustrations on multivariate trigonometric polynomials and functions on the Boolean hypercube.