Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM
Many problems in machine learning can be formulated as optimizing a convex
functional over a space of measures. This paper studies the convergence of the
mirror descent algorithm in this infinite-dimensional setting. Defining Bregman
divergences through directional derivatives, we derive the convergence of the
scheme for relatively smooth and strongly convex pairs of functionals. Applying
our result to joint distributions and the Kullback--Leibler (KL) divergence, we
show that Sinkhorn's primal iterations for entropic optimal transport in the
continuous setting correspond to a mirror descent, and we obtain a new proof of
its (sub)linear convergence. We also show that Expectation Maximization (EM)
can always formally be written as a mirror descent, and, when optimizing on the
latent distribution while fixing the mixtures, we derive sublinear rates of
convergence.