Fast entropically regularized semidefinite programming

I will present fast practical algorithms for approximate semidefinite programming (SDP) based on regularization by the von Neumann entropy. These approaches are based on a dual formulation of the regularized problem, and dual updates are computed using randomized trace estimators. Since the primal variable is only represented implicitly and we deliberately want to avoid assumptions of low-rankness, some care is required to recover problem-specific desiderata from the dual solution. I will show how this framework can be used to derive improved practical scaling for the Max-Cut problem, spectral embedding, and the full/partial permutation synchronization problems.