Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM
This work provides theoretical convergence guarantees for mirror descent in infinite-dimensional settings, which is incremental for applications like optimal transport and EM algorithms in machine learning.
The paper tackles the problem of optimizing convex functionals over measure spaces by analyzing mirror descent convergence under relative smoothness assumptions, and applies this to show that Sinkhorn's iterations for entropic optimal transport correspond to mirror descent with a new proof of its (sub)linear convergence, and that EM can be formally written as mirror descent with derived sublinear convergence rates for specific cases.
Many problems in machine learning can be formulated as optimizing a convex functional over a vector 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 convex pairs of functionals. Such assumptions allow to handle non-smooth functionals such as the Kullback--Leibler (KL) divergence. Applying our result to joint distributions and KL, 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. When optimizing only on the latent distribution while fixing the mixtures parameters -- which corresponds to the Richardson--Lucy deconvolution scheme in signal processing -- we derive sublinear rates of convergence.