Analysis of Kernel Mirror Prox for Measure Optimization
Pavel Dvurechensky Jia-Jie Zhu
By choosing a suitable function space as the dual to the non-negative measure
cone, we study in a unified framework a class of functional saddle-point
optimization problems, which we term the Mixed Functional Nash Equilibrium
(MFNE), that underlies several existing machine learning algorithms, such as
implicit generative models, distributionally robust optimization (DRO), and
Wasserstein barycenters. We model the saddle-point optimization dynamics as an
interacting Fisher-Rao-RKHS gradient flow when the function space is chosen as
a reproducing kernel Hilbert space (RKHS). As a discrete time counterpart, we
propose a primal-dual kernel mirror prox (KMP) algorithm, which uses a dual
step in the RKHS, and a primal entropic mirror prox step. We then provide a
unified convergence analysis of KMP in an infinite-dimensional setting for this
class of MFNE problems, which establishes a convergence rate of $O(1/N)$ in the
deterministic case and $O(1/\sqrt{N})$ in the stochastic case, where $N$ is the
iteration counter. As a case study, we apply our analysis to DRO, providing
algorithmic guarantees for DRO robustness and convergence.