Beyond Matrix Multiplicative Weight Updates

Regret minimization over the PSD cone is a key component in many fast spectral algorithms, and yields nearly-linear time algorithms for many versions of graph partitioning problems. All applications of this idea rely on the matrix version of the classical multiplicative weight update method (MWU).

In this talk, I explain how Matrix MWU naturally arises as an instance of the Follow-the-Regularized-Leader method with the entropy regularizer. I will then generalize this approach to a larger class of regularizers. As an application, I will provide an alternative construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava, and show how to construct these sparsifiers in almost quadratic time.

This is a joint work with Zhenyu Liao and Lorenzo Orecchia.