Averaged Mirror Descent: a Convergent Algorithm for Entropic Gromov–Wasserstein Problems

The Gromov--Wasserstein (GW) distance measures the discrepancy between metric measure (mm) spaces and identifies optimal alignments between them based solely on their intrinsic structure. Since it identifies isomorphic mm spaces, it provides a natural notion of distance for heterogeneous datasets which may admit isomorphic representations. In order to accelerate computation of GW distances, many practitioners employ entropic regularization to obtain an Entropic GW (EGW) problem. The most popular EGW solver is the Mirror Descent (MD) algorithm, which reduces EGW computations to an iterative process where an entropic optimal transport problem is solved at each iteration. Despite its widespread use, the theoretical convergence of MD for this problem remains unaccounted for in the literature. To address this, we introduce Averaged Mirror Descent (AMD) which averages consecutive MD steps. We establish that AMD is provably convergent and, in addition, account for inexactness in the iterations which is inescapable in practice. We also compare the empirical performance of MD and AMD across a variety of settings.