Fast entropically regularized semidefinite programming

Michael Lindsey, Berkeley University of California
Fine Hall 214

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 the full pipeline yields fast algorithms for the Max-Cut problem, spectral embedding, and the full/partial permutation synchronization problems.