Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective

Yulong Lu (YL) Department of Mathematics and Statistics, Lederle Graduate Research Tower, University of Massachusetts, 710 N. Pleasant Street, Amherst, MA 01003. [email protected]

Abstract.

Finding the mixed Nash equilibria (MNE) of a two-player zero sum continuous game is an important and challenging problem in machine learning. A canonical algorithm to finding the MNE is the noisy gradient descent ascent method which in the infinite particle limit gives rise to the Mean-Field Gradient Descent Ascent (GDA) dynamics on the space of probability measures. In this paper, we first study the convergence of a two-scale Mean-Field GDA dynamics for finding the MNE of the entropy-regularized objective. More precisely we show that for each finite temperature (or regularization parameter), the two-scale Mean-Field GDA with a suitable finite scale ratio converges exponentially to the unique MNE without assuming the convexity or concavity of the interaction potential. The key ingredient of our proof lies in the construction of new Lyapunov functions that dissipate exponentially along the Mean-Field GDA. We further study the simulated annealing of the Mean-Field GDA dynamics. We show that with a temperature schedule that decays logarithmically in time the annealed Mean-Field GDA converges to the MNE of the original unregularized objective.

Keywords. Nash equilibrium, mixed Nash equilbirium, gradient descent ascent, mean field, simulated annealing.

1. Introduction

Minmax learning underpins numerous machine learning methods including Generative Adversarial Networks (GANs) [20], adversarial training [34] and reinforcement learning [6]. The minmax learning is often be formulated as a zero-sum game between min and max players and hence can be formalized as a minmax optimization problem of the form

\min_{x\in{\mathcal{X}}}\max_{y\in{\mathcal{Y}}}K(x,y),

where the function $K$ is the game objective, $x$ and $y$ represent the player strategies. When $K$ is nonconvex in $x$ or nonconcave in $y$ , finding the pure Nash [38] equilibria of $K$ is difficult and sometimes impossible since the pure Nash equilibrium may not even exist. On the other hand, the mixed Nash equilibria (MNE) [19] where the pure strategies are replaced by mixed strategies modeled by a probability distribution over the set of strategies, do exist for more general objective functions. Formally the mixed Nash equilibria consist of pairs of probability distributions $\mu$ and $\nu$ that solve

(1.1)

\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E_{0}(\mu,\nu),\text{ where }E_{0}(\mu,\nu):=\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\mu(dx)\nu(dy).

Here ${\mathcal{P}}({\mathcal{X}})$ and ${\mathcal{P}}({\mathcal{Y}})$ denote the space of probability measures (or the set of all mixed strategies) on the state spaces ${\mathcal{X}}$ and ${\mathcal{Y}}$ respectively. Thanks to Glicksberg’s theorem [19], a MNE exists if ${\mathcal{X}}$ and ${\mathcal{Y}}$ are finite or if ${\mathcal{X}}$ and ${\mathcal{Y}}$ are compact and $K$ is continuous. While MNE exist in much generality, it is still difficult to find them. Several progress have been made recently for finding MNE of high dimensional game problems with applications in GANs. For instance, the work [22] proposed a mirror-descent algorithm for finding MNE of (1.1) and applied the algorithms for Wasserstein GANs with provable convergence guarantees. The recent work [16, 33] proposed and analyzed an entropy-regularized version of (1.1):

(1.2)

\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}(\mathcal{Y})}E_{\tau}(\mu,\nu),\text{ where }E_{\tau}(\mu,\nu):=\int_{{\mathcal{X}}}\int_{\mathcal{Y}}K(x,y)d\nu(y)d\mu(x)-\tau{\mathcal{H}}(\mu)+\tau{\mathcal{H}}(\nu).

Here ${\mathcal{H}}(\mu)=-\int\log\frac{d\mu}{dx}d\mu$ is the entropy functional of the probability measure $\mu$ , and the parameter $\tau>0$ is the entropy regularization parameter(or temperature). Observe that the objective energy functional $E_{\tau}$ is strongly convex in $\mu$ and strongly concave in $\nu$ . As a result of the famous Von Neumann’s minmax theorem [52, 47, 41, 40], one has that

(1.3)

\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}(\mathcal{Y})}E_{\tau}(\mu,\nu)=\max_{\nu\in{\mathcal{P}}(\mathcal{Y})}\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E_{\tau}(\mu,\nu).

Under very mild assumptions on $K$ , Problem (1.2) has a unique MNE $(\mu^{\ast},\nu^{\ast})$ (see a proof in [16]) in the sense that for any $\mu\in{\mathcal{P}}({\mathcal{X}}),\nu\in{\mathcal{P}}({\mathcal{Y}})$ ,

E_{\tau}(\mu^{\ast},\nu)\leq E_{\tau}(\mu^{\ast},\nu^{\ast})\leq E_{\tau}(\mu,\nu^{\ast}).

Furthermore, the MNE $(\mu^{\ast},\nu^{\ast})$ is given by the unique solution of the fixed point equations

(1.4)

\mu^{\ast}(dx)\propto\exp\Big{(}-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d\nu^{\ast}(y)\Big{)},\quad\nu^{\ast}(dy)\propto\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)d\mu^{\ast}(x))\Big{)}.

In the setting where both players play finite mixtures of $N$ strategies, i.e. $\mu=\sum_{j=1}^{N}\frac{1}{N}\delta_{X^{j}}$ and $\nu=\sum_{j=1}^{N}\frac{1}{N}\delta_{Y^{j}}$ , the following noisy gradient descent-ascent dynamics is perhaps one of the most natural algorithms for finding MNE of (1.2):

(1.5)

dX^{i}_{t}=-\frac{1}{N}\sum_{j=1}^{N}\nabla_{x}K(X^{i}_{t},Y^{j}_{t})dt+\sqrt{2\tau}dW^{i}_{t},\quad dY^{i}_{t}=\frac{\eta}{N}\sum_{j=1}^{N}\nabla_{y}K(X^{j}_{t},Y^{i}_{t})dt+\sqrt{2\tau\eta}dB^{i}_{t},

where $W^{i}_{t},B^{i}_{t},i=1,\cdots N$ are independent Brownian motions. The parameter $\eta>0$ in (1.5) represents the ratio of timescales at which the gradient descent and ascent dynamics is undergoing. When $\eta=1$ , there is no timescale separation. However, GDA with different time scales is commonly used in minmax optimization [24, 28] and sometimes leads to better convergence property [21].

In the limit of large number of strategies ( $N{\rightarrow}\infty$ ), the empirical measures $\mu_{t}^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{X^{i}_{t}}$ and $\nu_{t}^{N}=\frac{1}{N}\sum_{i=1}^{N}\delta_{Y^{i}_{t}}$ of the interacting particle, with $\{X_{0}^{i}\}$ and $\{Y_{0}^{i}\}$ identically independent sampled from the initial distributions $\mu_{0}$ and $\nu_{0}$ , converge weakly within finite time to the solutions $\mu_{t}$ and $\nu_{t}$ of the Mean-Field GDA (also named the Interacting Wasserstein Gradient Flow in [16]) dynamics:

(1.6)		$\displaystyle\partial_{t}\mu_{t}$	$\displaystyle=\nabla\cdot(\mu_{t}\int_{{\mathcal{Y}}}\nabla_{x}K(x,y)d\nu_{t}(y))+\tau\Delta\mu_{t},$
(1.6)		$\displaystyle\partial_{t}\nu_{t}$	$\displaystyle=\eta\Big{(}-\nabla\cdot(\nu_{t}\int_{{\mathcal{X}}}\nabla_{y}K(x,y)d\mu_{t}(x))+\tau\Delta\nu_{t}\Big{)}.$

The dynamics (1.6) can be viewed as the minmax analogue of the Mean-Field Langevin [42, 7, 23] dynamics that arises naturally from the mean field analysis of optimization of two-layer neural networks.

Despite its simplicity and popularity, the long-time convergence of the Mean-Field GDA (1.6) is still not well understood, except in the extreme quasi-static [33] regime where the ascent dynamics is infinitely faster or slower than the descent dynamics ( $\eta=0\text{ or }+\infty$ ). This motivates us to study the first question, which to the best of our knowledge, remains open:

Question 1: Does the Mean-Field GDA (1.6) with a finite scale ratio $\eta>0$ converge to the unique MNE? If so, what is the rate of convergence?

We provide an affirmative answer to Question 1 and establish a quantitative exponential convergence of (1.6) to the MNE for any fixed $\tau>0$ . Furthermore, motivated by the recent simulated annealing results for Langevin dynamics [51, 44] in the context of global optimization or for Mean-Field Langevin dynamics [7] in the setting of training two-layer neural networks, it is natural to ask what would happen to the dynamics (1.6) in the annealed regime that $\tau{\rightarrow}0$ as $t{\rightarrow}\infty$ . In particular, it is natural to ask

Question 2: Does the annealed Mean-Field GDA (1.6) with a decreasing temperature $\tau=\tau_{t}$ converge to a MNE of the unregularized objective $E_{0}$ defined in (1.1)?

Summary of contributions.

In this work we first address Question 1 by providing the first convergence analysis of the two-scale continuous-time Mean-Field GDA dynamics (1.6) with a finite scale ratio. This improves substantially the earlier convergence results by [33, 15] on Mean-Field GDA in the quasistatic setting where the scale ratio either vanishes or explodes. The key ingredient of the proof is the construction of a novel Lyapunov function which decreases exponentially along the dynamics (1.6). We then further address Question 2 by proving that the annealed Mean-Field GDA converges to a global MNE of the original unregularized objective $E_{0}$ . The latter result, to the best our knowledge, is the first rigorous justification of the global convergence of GDA to MNE in the mean field regime.

We highlight the major contributions as follows.

•

For any fixed temperature $\tau>0$ , we show that in the fast ascent/descent regime (or the scale ratio $\eta$ is either larger or smaller than certain threshold), the Mean-Field GDA dynamics (1.6) converges exponentially to the MNE of the entropy-regularized objective $E_{\tau}$ with respect to certain Lyapunov functions; see Theorem 2.1.
•

The convergence in Lyapunov functions further implies the global exponential convergence of the dynamics with respect to the relative entropy (see Theorem 2.2). Our (non-asymptotic) convergence results hold for any positive temperature (regularization parameter) and do not assume convexity or concavity of the interaction potential $K$ . The convergence rate is characterized explicitly in terms of $\tau$ , bounds on $K$ and diameters of the state spaces.
•

We also study the simulated annealing of the Mean-Field GDA dynamics (1.6). We prove that with the cooling schedule $\tau_{t}$ decaying with a logarithimc rate, the Mean-Field GDA dynamics (1.6) converges to the global mixed Nash equilibrium of $E_{0}$ with respect to the Nikaidò-Isoda error (defined in (1.7)). See Theorem 2.3 for the precise statements.

1.1. Related work.

Minmax optimization

Most previous works about minmax optimization focused on the analysis of discrete-time optimization schemes in finite dimensional Euclidean spaces under various assumptions on the objective function. In the convex-concave setting, global convergence guarantees were obtained for various optimization schemes, such as GDA [12], mirror descent [36] and Hamiltonian gradient descent [1]. In the non-convex and/or non-concave setting, local convergence to several notions of stationary points were studied in [11, 28]. In the special case where the objective satisfies a two-sided Polyak-Łojasiewicz (PL) condition, convergence to global Nash equilibria were recently obtained in [55, 56, 13] for two-scale GDA.

Mean-field analysis

Our study of the Mean-Field GDA dynamics for minmax optimization is strongly motivated by a growing amount of work on mean-field analysis of gradient descent algorithms for minimizing neural networks. The study of the latter originates from the work on two-layer networks [35, 48, 46, 8], to residual networks [29, 54] and general deep neural networks [2, 49, 39]. These results show that the mean field dynamics can be realized as Wasserstein gradient flows of certain nonlinear energy functionals on the space of probability measures. Global convergence of the Wasserstein gradient flows were obtained for the mean-field Langevin dynamics in [35, 7, 42, 23] and for the noiseless mean-field dynamics in [8]. We note that mean-field Langevin dynamics can be viewed as a special Mckean-Vlasov dynamics whose long-time convergence are often established by assuming either the small interaction strength or large noise level; see e.g. [17, 23].

Among the existing work on mean field Langevin dynamics, [7] is closest to ours where the author proved the exponential convergence of Mean-Field Langevin dynamics under a certain uniform log-Sobolev inequality assumption, and also proved the convergence of the annealed Mean-Field Langevin to the global minimizers of the objective function. Our results are parallel to the results of [7], but require new proof strategies. A key ingredient of our proof is constructing new Lyapunov functions that decay exponentially along the Mean-Field GDA (1.6).

In the context of minmax optimization, [16] first proposed and analyzed the noisy gradient descent ascent flow (1.5) without scale separation ( $\eta=1$ ) for finding the MNE. Specifically, the authors therein proved the convergence of (1.5) to the mean field GDA (1.6) in the limit of large agent size, and characterized the equilibrium of (1.6) as the unique solution of the fixed point equation (1.4). However, [16] did not provide a proof of the long-time convergence of (1.6). In [33], the authors obtained convergence guarantees for the mean field GDA (1.6) in the quasi-static regime where the ascent dynamics is infinitely faster or slower than the descent dynamics (i.e. $\eta=+\infty\text{ or }0$ ). One of the major contributions of the present work goes beyond the quasi-static regime and provides the first proof for exponential convergence of (1.6) with a finite scale ratio.

Wasserstein-Fisher-Rao gradient flows

As an alternative to Wasserstein gradient flows, gradient flow with respect to the Wasserstein-Fisher-Rao (WFR) metric [9, 25, 27] has recently sparked a large amount of research on PDEs [5, 26], neural network training [45] and statistical sampling [30, 31]. Especially, WFR gradient flows give rise to birth-death interacting particle dynamics that enables “teleportation” of mass and locations of particles and hence lead to better convergence properties than the Langevin dynamics in certain scenarios [45, 30, 31]. More recently, [16] adopts a WFR-gradient flow for two-player zero-mean continuous games and proves that the time-averaging of the WFR-dynamics converges to the MNE in the regime where Fisher-Rao dynamics dominates the Wasserstein counterpart. In [53], a new particle algorithm motivated by the implicit time-discretization of WFR-gradient flow was proposed for finding the MNE in the space of atomic measures. The authors proved a local exponential convergence of the proposed algorithm under certain non-degeneracy assumptions on the game objective and the assumption that the MNE is unique.

1.2. Notations.

For a measurable space ${\mathcal{X}}$ , we use ${\mathcal{P}}({\mathcal{X}})$ to denote the space of probability measures on ${\mathcal{X}}$ . Given a canonical Borel measure $dx$ on ${\mathcal{X}}$ , such as the uniform measure considered in the paper, if $\mu$ is absolutely continuous with respect to $dx$ , we denote the Radon-Nikodym derivative by $\frac{d\mu}{dx}$ . We define the shannon entropy of $\mu$ by ${\mathcal{H}}(\mu)=-\int_{{\mathcal{X}}}\log(\frac{d\mu}{dx})d\mu(x)$ . The relative entropy (or Kullback-Leibler divergence) and the relative Fisher information between two probability measures $\mu_{1}$ and $\mu_{2}$ are defined by

{\mathcal{H}}(\mu_{1}|\mu_{2})=\int\log\Big{(}\frac{d\mu_{1}}{d\mu_{2}}\Big{)}d\mu_{1},\quad{\mathcal{I}}(\mu_{1}|\mu_{2})=\int\Big{|}\nabla\log\Big{(}\frac{d\mu_{1}}{d\mu_{2}}\Big{)}\Big{|}^{2}d\mu_{1}

if $\mu_{1}$ is absolutely continuous with respect to $\mu_{2}$ and $+\infty$ otherwise. Given an approximate mixed Nash equilibrium $(\mu,\nu)$ , we define the Nikaidò-Isoda [41] error ${\text{NI}}(\mu,\nu)$ by

(1.7)		$\displaystyle{\text{NI}}(\mu,\nu)$	$\displaystyle:=\sup_{\nu^{\prime}\in{\mathcal{P}}({\mathcal{Y}})}E_{0}(\mu,\nu^{\prime})-\inf_{\mu^{\prime}\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu^{\prime},\nu)$
(1.7)			$\displaystyle=E_{0}(\mu,\nu)-\inf_{\mu^{\prime}\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu^{\prime},\nu)+\sup_{\nu^{\prime}\in{\mathcal{P}}({\mathcal{Y}})}E_{0}(\mu,\nu^{\prime})-E_{0}(\mu,\nu).$

Note that by definition ${\text{NI}}(\mu,\nu)\geq 0$ for any $\mu\in{\mathcal{P}}({\mathcal{X}})$ and $\nu\in{\mathcal{P}}({\mathcal{Y}})$ and ${\text{NI}}(\mu,\nu)=0$ if and only if $(\mu,\nu)=(\mu^{\ast},\nu^{\ast})$ .

1.3. Organization

The remaining of the paper is organized as follows. In Section 2 we state the key assumptions and present the main results of the paper. In Section 3 we discuss applications of our results in training GANs and adversarial learning of PDEs. Section 4 devotes to the proofs of main results. We finish with several conclusion remarks and future directions in Section 5. Further proof details are provided in the Appendix.

2. Assumptions and Main Results

Let us first recall the minmax problem of the entropy-regularized continuous game:

(2.1)

\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}(\mathcal{Y})}E_{\tau}(\mu,\nu),\text{ where }E_{\tau}(\mu,\nu):=\int_{{\mathcal{X}}}\int_{\mathcal{Y}}K(x,y)d\nu(y)d\mu(x)-\tau{\mathcal{H}}(\mu)+\tau{\mathcal{H}}(\nu).

When the regularization parameter (or temperature) $\tau=0$ , we write

E_{0}(\mu,\nu)=\int_{{\mathcal{X}}}\int_{\mathcal{Y}}K(x,y)d\nu(y)d\mu(x).

We are interested in the global convergence of the Mean-Field GDA dynamics to the MNE of (2.1):

	$\displaystyle\partial_{t}\mu_{t}$	$\displaystyle=\nabla\cdot(\mu_{t}\int_{{\mathcal{Y}}}\nabla_{x}K(x,y)d\nu_{t}(y))+\tau\Delta\mu_{t},$
	$\displaystyle\partial_{t}\nu_{t}$	$\displaystyle=\eta\Big{(}-\nabla\cdot(\nu_{t}\int_{{\mathcal{X}}}\nabla_{y}K(x,y)d\mu_{t}(x))+\tau\Delta\nu_{t}\Big{)}.$

In what follows, we may suppress the dependence of $E_{\tau}$ on $\tau$ and write $E=E_{\tau}$ to simplify notations when the $\tau>0$ is fixed; we will indicate such dependence in later discussions on the annealed dynamics where $\tau=\tau_{t}$ shrinks to zero in time.

2.1. Assumptions

Following [15] and [53], we make the following assumptions on the state spaces ${\mathcal{X}}$ and ${\mathcal{Y}}$ .

Assumption 2.1.

The state spaces ${\mathcal{X}}$ and ${\mathcal{Y}}$ are (i) either smooth compact manifolds without boundary such that the eigenvalues of the Ricci curvature are strictly positive everywhere or (ii) Euclidean tori (with possibly unequal dimensions).

We also make the following smoothness assumption on the potential $K$ .

Assumption 2.2.

The function $K\in C^{2}({\mathcal{X}}\times{\mathcal{Y}})$ and there exists $K_{xy}>0$ such that

\|\nabla_{xy}^{2}K\|_{\infty}\leq K_{xy}.

It will be very useful to introduce operators ${\mathcal{K}}^{+}:{\mathcal{P}}({\mathcal{X}}){\rightarrow}{\mathcal{P}}({\mathcal{Y}})$ and ${\mathcal{K}}^{-}:{\mathcal{P}}({\mathcal{Y}}){\rightarrow}{\mathcal{P}}({\mathcal{X}})$ where

(2.2)

{\mathcal{K}}^{+}\mu(dy)=\frac{1}{Z^{+}(\mu)}\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)d\mu(x)\Big{)},\quad{\mathcal{K}}^{-}\nu(dx)=\frac{1}{Z^{-}(\nu)}\exp\Big{(}-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d\nu(y)\Big{)}.

Here $Z^{-}(\nu)$ and $Z^{+}(\mu)$ are the corresponding partition functions defined by

(2.3)

Z^{-}(\nu)=\int_{{\mathcal{X}}}\exp\Big{(}-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d\nu(y)\Big{)}dx,\quad Z^{+}(\mu)=\int_{{\mathcal{Y}}}\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)d\mu(x)\Big{)}dy.

It is easy to verify by the definition of $E(\mu,\nu)$ that

(2.4)

\operatorname*{arg\,max}_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)={\mathcal{K}}^{+}(\mu),\quad\operatorname*{arg\,min}_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,\nu)={\mathcal{K}}^{-}(\nu).

With the notations above, the MNE $(\mu^{\ast},\nu^{\ast})$ of (2.1) is characterized as the unique solution of the following fixed point equations (see [16, Theorem 1]):

(2.5)

\mu^{\ast}={\mathcal{K}}^{-}(\nu^{\ast}),\quad\nu^{\ast}={\mathcal{K}}^{+}(\mu^{\ast}).

The lemma below shows that under Assumption 2.2 and Assumption 2.1, the measures ${\mathcal{K}}^{+}(\mu)$ and ${\mathcal{K}}^{-}(\nu)$ satisfy the logarithmic Sobolev inequalities (LSI) uniformly for any $\mu\in{\mathcal{P}}({\mathcal{X}})$ and $\nu\in{\mathcal{P}}({\mathcal{Y}})$ .

Lemma 2.1.

There exists a constant $\lambda_{LS}>0$ such that for any $\mu\in{\mathcal{P}}({\mathcal{X}})$ and $\nu\in{\mathcal{P}}({\mathcal{Y}})$ ,

(2.6)

\lambda_{LS}{\mathcal{H}}(\mu|{\mathcal{K}}^{-}{\nu})\leq{\mathcal{I}}(\mu|{\mathcal{K}}^{-}{\nu}),\quad\lambda_{LS}{\mathcal{H}}(\nu|{\mathcal{K}}^{+}{\mu})\leq{\mathcal{I}}(\nu|{\mathcal{K}}^{+}{\mu}).

Lemma 2.1 follows from the classical Holley-Stroock argument and the fact that the uniform measures on ${\mathcal{X}}$ and ${\mathcal{Y}}$ satisfy the LSI thanks to Assumption 2.1; see e.g. [7, Proposition 5.2] and [15, Proposition 6]). It is worthwhile to note that in the regime where $\tau^{-1}\|K\|_{\infty}\gg 1$ , the log-Sobolev constant $\lambda_{LS}=\lambda_{LS}(\tau)$ satisfies that

(2.7)

\lambda_{LS}(\tau)=\mathcal{O}(\exp(-\tau^{-1}\|K\|_{\infty})).

2.2. Exponential convergence of Mean-Field GDA with a fixed temperature

The goal of this section is to present the global convergence of the GDA dynamics (1.6) to the MNE $(\mu^{\ast},\nu^{\ast})$ . To this end, it will be useful to define the following functionals

(2.8)	$\displaystyle{\mathcal{L}}_{1}(\mu)$	$\displaystyle:=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu),$
	$\displaystyle{\mathcal{L}}_{2}(\mu,\nu)$	$\displaystyle:=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)-E(\mu,\nu),$
	$\displaystyle{\mathcal{L}}_{3}(\nu)$	$\displaystyle:=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,\nu),$
	$\displaystyle{\mathcal{L}}_{4}(\mu,\nu)$	$\displaystyle:=E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,\nu).$

Note that by definition the functionals ${\mathcal{L}}_{i},i=1,\cdots,4$ defined above are non-negative. For a fixed constant $\gamma>0$ , we also define the Lyapunov functions

(2.9)

{\mathcal{L}}(\mu,\nu)={\mathcal{L}}_{1}(\mu)+\gamma{\mathcal{L}}_{2}(\mu,\nu),\quad\widetilde{{\mathcal{L}}}(\mu,\nu)={\mathcal{L}}_{3}(\mu)+\gamma{\mathcal{L}}_{4}(\mu,\nu).

Let $\kappa$ be the effective condition number defined by

\kappa=\frac{K_{xy}}{\tau\lambda_{LS}}.

Our first main theorem characterizes the exponential convergence of (1.6) in terms of the Lyapunov functions ${\mathcal{L}}$ and $\widetilde{{\mathcal{L}}}$ .

Theorem 2.1.

Let Assumption 2.1 and Assumption 2.2 hold. For a fixed $\gamma<1$ , let $(\mu_{t},\nu_{t})$ be the solution to the GDA dynamics (1.6) with an initial condition $(\mu_{0},\nu_{0})$ satisfying ${\mathcal{L}}(\mu_{0},\nu_{0})<\infty$ and $\widetilde{{\mathcal{L}}}(\mu_{0},\nu_{0})<\infty$ , and with a finite time-scale ratio $\eta>0$ .

(i) Fast ascent regime: set $\eta=\frac{2\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\gamma}.$ Then for all $t>0$ ,

{\mathcal{L}}(\mu_{t},\nu_{t})\leq e^{-\alpha_{1}t}{\mathcal{L}}(\mu_{0},\nu_{0})

with

\alpha_{1}=\tau\lambda_{LS}\Big{(}\frac{1-\gamma}{2}\wedge\frac{\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\gamma}\Big{)};

(ii) Fast descent regime: set $\eta=\frac{\gamma}{2\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{X}})^{2}(1+3\gamma)}.$ Then for all $t>0$ ,

\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})\leq e^{-\alpha_{2}t}\widetilde{{\mathcal{L}}}(\mu_{0},\nu_{0})

with

\alpha_{2}=\frac{\tau\lambda_{LS}}{2}\Big{(}1\wedge\eta(1-\gamma)\Big{)}.

Remark 2.1.

Theorem 2.1 states that the two-scale GDA dynamics (1.6) with a suitable finite scale ratio converges exponentially to the equilibrium. This improves substantially the earlier result by [33] on GDA in the quasistatic setting where the scale ratio $\eta=0$ or $\eta=\infty$ . We emphasize that we chose the specific scale ratios merely for the purpose of simplifying the expression of the convergence rate $\alpha$ . In fact, by tracking the proof of Theorem 2.1, one can obtain that the convergence rate

\displaystyle\alpha=\begin{cases}C_{1}\tau\lambda_{LS},&\text{ if }\eta>c_{1}\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2},\\ C_{2}\tau\lambda_{LS}^{2},&\text{ if }\eta<\frac{c_{2}\gamma}{\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)},\end{cases}

for some constants $C_{i},c_{i}>0,i=1,2$ . Moreover, the dependence of the convergence rates on the diameters of the state spaces via $K_{xy}\mathrm{Diam}({\mathcal{Y}})$ and $K_{xy}\mathrm{Diam}({\mathcal{X}})$ can be avoided, and especially the latter two quantities can be replaced by $\|\nabla K\|_{\infty}$ ; see discussions around (A.3).

Observe also that in the low temperature regime ( $\tau\ll 1$ ), the log-Sobolev constant $\lambda_{LS}=\mathcal{O}(\exp(-\tau^{-1}\|K\|_{\infty}))$ . Hence Theorem 2.1 requires $\eta=\Omega((\tau^{-1}K_{xy})^{2}/\lambda_{LS})$ (and $\eta=o(\lambda_{LS}\tau^{2}/K_{xy}^{2})$ ) to guarantee an exponential convergence rate $\alpha=\mathcal{O}(\tau\lambda_{LS})$ (and $\alpha=\mathcal{O}(\lambda_{LS}^{2}\tau^{3})$ ) in the fast ascent (descent) regime. Notice that the quadratic dependence of the convergence rate $\alpha$ on $\lambda_{LS}$ in the fast descent regime, in contrast to the linear dependence on $\lambda_{LS}$ in the fast ascent regime, is due to the fact that the ascent dynamics itself is running in the slow time-scale $\eta=o(\lambda_{LS}\tau^{2}/K_{xy}^{2})$ ; one would recover the same rate of convergence as in the fast ascent regime if one used the time scales $1/\eta$ for the descent dynamics and $1$ the ascent dynamics.

Remark 2.2.

Our construction of Lyapunov functions (2.9) is strongly motivated by the recent study [55, 13] of two-scale GDA for minmax optimization on Euclidean spaces. In the finite dimensional setting, a two-sided PL condition is sufficient to guarantee the exponential convergence of two-scale GDA in both continuous-time [13] and discrete-time [55, 56] cases. In our infinite dimensional setting of the Mean-Field GDA, the uniform log-Sobolev inequality plays the same role as the two-sided PL condition, which however, needs to be combined with the entropy sandwich inequalities in Lemma 4.1 to obtain the exponential dissipation of Lyapunov functions.

Our next theorem provides an exponential convergence of (1.6) with respect to the relative entropy.

Theorem 2.2.

Let the assumptions of Theorem 2.1 hold. Let the rates $\alpha_{i},i=1,2$ be defined as in Theorem 2.1.

(i) Fast ascent regime: set $\eta=\frac{2\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\gamma}.$ Then for all $t>0$ ,

(2.10)

\tau{\mathcal{H}}(\mu_{t}|\mu^{\ast})\leq\frac{e^{-\alpha_{1}t}}{\gamma}{\mathcal{L}}(\mu_{0},\nu_{0})\text{ and }\tau{\mathcal{H}}(\nu_{t}|\nu^{\ast})\leq\Big{(}\frac{2}{\gamma}+\frac{4\|K\|_{\infty}^{2}}{\tau^{2}}\Big{)}e^{-\alpha_{1}t}{\mathcal{L}}(\mu_{0},\nu_{0}).

(ii) Fast descent regime: set $\eta=\frac{2\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\gamma}.$ Then for all $t>0$ ,

(2.11)

\tau{\mathcal{H}}(\mu_{t}|\mu^{\ast})\leq\frac{e^{-\alpha_{2}t}}{\gamma}{\mathcal{L}}(\mu_{0},\nu_{0})\text{ and }\tau{\mathcal{H}}(\nu_{t}|\nu^{\ast})\leq\Big{(}\frac{2}{\gamma}+\frac{4\|K\|_{\infty}^{2}}{\tau^{2}}\Big{)}e^{-\alpha_{2}t}{\mathcal{L}}(\mu_{0},\nu_{0}).

2.3. Convergence of annealed Mean-Field GDA

In this section, we proceed to presenting the convergence of the “annealed” Mean-Field GDA dynamics

(2.12)		$\displaystyle\partial_{t}\mu_{t}$	$\displaystyle=\nabla\cdot\left(\mu_{t}\int_{{\mathcal{Y}}}\nabla_{x}K(x,y)d\nu_{t}(y)\right)+\tau_{t}\Delta\mu_{t},$
(2.12)		$\displaystyle\partial_{t}\nu_{t}$	$\displaystyle=\eta_{t}\left(-\nabla\cdot\left(\nu_{t}\int_{{\mathcal{X}}}\nabla_{y}K(x,y)d\mu_{t}(x)\right)+\tau_{t}\Delta\nu_{t}\right),$

where $\tau_{t}>0$ is now a time-dependent temperature which shrinks in time. Given any initial condition $(\mu_{0},\nu_{0})\in{\mathcal{P}}({\mathcal{X}})\times{\mathcal{P}}({\mathcal{Y}})$ , the existence of uniqueness of the global solution to (2.12) follow directly from the classical well-posedness of the theory of nonlinear Mckean-Vlasov-type PDEs [18, 50]. Our goal is to show that by carefully choosing the cooling schedule $\tau_{t}$ and the time-scale ratio $\eta_{t}$ the solution $(\mu_{t},\nu_{t})$ to the annealed dynamics (2.12) converges to the MNE of $E_{0}$ .

Let $(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ be the solution of (2.5) corresponding to temperature $\tau$ . Recall the Nikaidò-Isoda defined by (1.7).

Theorem 2.3.

Let Assumption 2.2 and Assumption 2.1 hold. Let $(\mu_{t},\nu_{t})$ be the solution to (2.12) with an initial condition $(\mu_{0},\nu_{0})\in{\mathcal{P}}({\mathcal{X}})\times{\mathcal{P}}({\mathcal{Y}})$ . Assume that the log-Sobolev constant $\lambda_{LS}=\lambda_{LS}(\tau)\geq C_{0}e^{-\xi^{\ast}/\tau}$ for some $\xi^{\ast},C_{0}>0$ .

(i) Fast ascent regime: Assume further that $\tau_{t}$ is smooth, decreasing in $t$ and for some $\xi>\xi^{\ast}$ , $\tau_{t}=\xi/\log t$ for large values of $t$ . Set $\eta_{t}=\frac{M}{(\log t)^{2}}t^{\xi^{\ast}/\xi}$ for some large $M>0$ . Then for every $0<\epsilon<1-\xi^{\ast}/\xi$ , there exists $C,C^{\prime}>0$ such that for $t$ sufficiently large,

(2.13)

{\mathcal{H}}(\mu_{t}|\mu_{\tau_{t}}^{\ast})\leq Ct^{-(1-\xi^{\ast}/\xi-\epsilon)},\qquad{\mathcal{H}}(\nu_{t}|\nu_{\tau_{t}}^{\ast})\leq Ct^{-(1-\xi^{\ast}/\xi-\epsilon)},

and that

(2.14)

0\leq{\text{NI}}(\mu_{t},\nu_{t})\leq\frac{C^{\prime}\log\log t}{\log t}.

(ii) Fast descent regime: Assume further that $\tau_{t}$ is smooth, decreasing in $t$ and for some $\xi>2\xi^{\ast}$ , $\tau_{t}=\xi/\log t$ for large values of $t$ . Set $\eta_{t}=\frac{\log t}{Mt}$ for some large M. Then for every $0<\epsilon<1-2\xi^{\ast}/\xi$ , there exists $C,C^{\prime}>0$ such that for $t$ sufficiently large,

(2.15)

{\mathcal{H}}(\mu_{t}|\mu_{\tau_{t}}^{\ast})\leq Ct^{-(1-2\xi^{\ast}/\xi-\epsilon)},\qquad{\mathcal{H}}(\nu_{t}|\nu_{\tau_{t}}^{\ast})\leq Ct^{-(1-2\xi^{\ast}/\xi-\epsilon)},

and that

(2.16)

0\leq{\text{NI}}(\mu_{t},\nu_{t})\leq\frac{C^{\prime}\log\log t}{\log t}.

3. Applications

In this section, we discuss briefly applications of our theoretical results in training of GANs and adversarial learning of PDEs.

3.1. Training of GANs

Let $\mu_{m}$ be the empirical measure associated to the i.i.d. samples $\{x_{i}\}_{i=1}^{m}\in{\mathcal{X}}$ from a target measure $\mu\in{\mathcal{P}}({\mathcal{X}})$ . Let $D_{{\mathcal{F}}}$ be an IPM on the space of probability measures ${\mathcal{P}}({\mathcal{X}})$ parameterized by a set ${\mathcal{F}}$ of discriminators, i.e.

D_{{\mathcal{F}}}(\mu,\nu):=\sup_{f\in{\mathcal{F}}}\int fd\mu-\int fd\nu.

IPM-based GAN learns an optimal $\mu$ that minimizes $D_{{\mathcal{F}}}(\mu,\mu_{m})$ over ${\mathcal{P}}({\mathcal{X}})$ :

(3.1)

\inf_{\mu\in{\mathcal{P}}({\mathcal{X}})}D_{{\mathcal{F}}}(\mu,\mu_{m})=\inf_{\mu\in{\mathcal{P}}({\mathcal{X}})}\sup_{f\in{\mathcal{F}}}\int fd\mu-\int fd\mu_{m}.

Consider the witness function class ${\mathcal{F}}$ given by the unit ball of Barron space $\mathcal{B}$ which consists of functions admitting the representation

f(x)=\int_{{\mathcal{Y}}}a\sigma(b\cdot x+c)d\nu(y),

where $y=(a,b,c)\in{\mathcal{Y}}$ and $\nu$ is a probability measure on the parameter space ${\mathcal{Y}}$ . Observe that Barron functions arise as natural infinite-width limit of two-layer neural networks with a dimension-free rate [3, 32, 4]. When the activation function satisfies that $\sup_{x}|a\sigma(b\cdot x+c)|\leq\phi(y)$ for some nonnegative function $\phi$ and for all $y\in{\mathcal{Y}}$ , the Barron norm $\|f\|_{{\mathcal{B}}}$ is defined by

(3.2)

\|f\|_{{\mathcal{B}}}:=\inf_{\nu}\Big{\{}\int_{{\mathcal{Y}}}\phi(y)\mu(dy)\ \Big{|}\ f(x)=\int_{{\mathcal{Y}}}a\sigma(b\cdot x+c)d\nu(y)\Big{\}}.

Setting ${\mathcal{F}}=\{f\in{\mathcal{B}}\ |\ \|f\|_{{\mathcal{B}}}\leq 1\}$ in (3.1) leads to

(3.3)

\inf_{\mu\in{\mathcal{P}}({\mathcal{X}})}\sup_{\nu\in{\mathcal{P}}({\mathcal{Y}})}\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\mu(dx)\nu(dy),\text{ where }K(x,y)=\Sigma(x,y)-\int_{{\mathcal{X}}}\Sigma(x,y)\mu_{m}(dx)+\phi(y).

Here we adopted the short-notation $\Sigma(x,y)=a\sigma(b\cdot x+c)$ with $y=(a,b,c)\in{\mathcal{Y}}$ in the above. Assume that the activation function $\sigma\in C^{2}({\mathbb{R}})$ , and the input space ${\mathcal{X}}$ and the parameter space satisfy the Assumption 2.1. Then it is straightforward to see that $K\in C^{2}({\mathcal{X}}\times{\mathcal{Y}})$ and there exists $C_{\sigma}<\infty$ such that for any multi-indices $\mathbf{i}$ and $\mathbf{j}$ with $0\leq|\mathbf{i}|+|\mathbf{j}|\leq 2$ ,

\|\nabla_{x}^{\mathbf{i}}\nabla^{\mathbf{j}}_{y}K(x,y)\|_{\infty}\leq 2\|\nabla_{x}^{\mathbf{i}}\nabla^{\mathbf{j}}_{y}\Sigma\|_{\infty}+\|\nabla^{\mathbf{j}}_{y}\phi\|\leq C_{\sigma}.

Therefore the convergence results in Theorem 2.1-2.2 for the Mean-Field GDA hold for the entropy-regularization of the GAN objective defined in (3.3). Moreover, Theorem 2.3 implies that the annealed GDA dynamics finds the MNE of the unregularized GAN objective.

3.2. Adversarial learning of PDEs

We provide another usage of our results in adversarial learning of PDEs. To demonstrate the idea, we focus on a simple linear elliptic PDE on a bounded Lipschitz domain ${\mathcal{Z}}\subset{\mathbb{R}}^{d}$ equipped with the Neumann boundary condition

	$\displaystyle-\Delta u(z)+Vu(z)$	$\displaystyle=f(z),z\in{\mathcal{Z}},$
	$\displaystyle\partial_{\nu}u(z)$	$\displaystyle=0,z\in\partial{\mathcal{Z}}.$

Assume that $0<V_{\min}\leq V\leq V_{\max}<\infty$ and $f\in(H^{1}({\mathcal{Z}}))^{*}$ . The weak solution $u\in H^{1}({\mathcal{Z}})$ satisfies that

(3.4)

\int_{{\mathcal{Z}}}\nabla u\cdot\nabla v+Vuvdz=\int_{{\mathcal{Z}}}fvdz,\forall v\in H^{1}({\mathcal{Z}}).

We seek an approximate solution to (3.4) in the framework of Petrov-Galerkin [43, 37] where we choose the spaces of trial functions and test functions as two different Barron functions. More precisely, consider a trial function $u(z)\in{\mathcal{U}}:=\{u\in{\mathcal{B}}_{1}\ |\ \|u\|_{{\mathcal{B}}_{1}}\leq 1\}$ and a test function $v\in{\mathcal{V}}:=\{v\in{\mathcal{B}}_{2}\ |\ \|v\|_{{\mathcal{B}}_{2}}\leq 1\}$ , where ${\mathcal{B}}_{i},i=1,2$ are Barron spaces defined in Section 3.1 with activation function $\sigma_{i}$ and Barron norm $\|\cdot\|_{{\mathcal{B}}_{i}}$ defined in (3.2) with $\phi$ replaced by nonnegative weight functions $\phi_{i}$ . We look for a solution $u\in{\mathcal{U}}$ parameterized by some probability measure $\mu\in{\mathcal{P}}({\mathcal{X}})$ ,

u(z)=\int_{{\mathcal{X}}}a_{1}\sigma_{1}(b_{1}\cdot z+c_{1})\mu(dx)

with $x=(a_{1},b_{1},c_{1})\in{\mathcal{X}}$ satisfying equation (3.4) for any $v\in{\mathcal{V}}$ with $\|v\|_{{\mathcal{B}}_{2}}\leq 1$ parameterized by $\nu\in{\mathcal{P}}({\mathcal{Y}})$ such that

v(z)=\int_{{\mathcal{Y}}}a_{2}\sigma_{2}(b_{2}\cdot z+c_{2})\nu(dy).

Putting these into the weak formulation (3.4) leads to

\inf_{\mu\in{\mathcal{P}}({\mathcal{X}})}\sup_{\nu\in{\mathcal{P}}({\mathcal{Y}})}\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\mu(dx)\nu(dy),

where the potential $K(x,y)$ is given for $x=(a_{1},b_{1},c_{1}),y=(a_{2},b_{2},c_{2})$ by

	$\displaystyle K(x,y)$	$\displaystyle=\int_{{\mathcal{Z}}}\Big{(}a_{1}a_{2}b_{1}\cdot b_{2}\sigma^{\prime}_{1}(b_{1}\cdot z+c_{1})\sigma^{\prime}_{2}(b_{2}\cdot z+c_{2})+V(z)a_{1}a_{2}\sigma_{1}(b_{1}\cdot z+c_{1})\sigma_{2}(b_{2}\cdot z+c_{2})$
		$\displaystyle\qquad-f(z)a_{2}\sigma_{2}(b_{2}\cdot z+c_{2})\Big{)}dz-\phi_{1}(x)+\phi_{2}(y).$

Assume that the activation functions $\sigma_{i}\in C^{2}({\mathbb{R}})$ and the parameter spaces ${\mathcal{X}}$ and ${\mathcal{Y}}$ satisfy Assumption 2.1. Assume also that $\phi_{1}\in C^{2}({\mathcal{X}})$ and $\phi_{2}\in C^{2}({\mathcal{Y}})$ . Then it is easy to verify that $K\in C^{2}({\mathcal{X}}\times{\mathcal{Y}})$ and that $\|K\|_{C^{2}}\leq C$ for some constant $C>0$ depending on $\sigma_{i},\phi_{i},{\mathcal{X}},{\mathcal{Y}},V$ and $f$ . Hence the convergence results on Mean-Field GDA and its annealed version established in Section 2 apply to this problem.

4. Proofs of Main Results

4.1. Proof of convergence for Mean-Field GDA with a fixed temperature

We only present the proof of our main convergence results in the fast ascent regime. The proofs for the fast descent regime can be carried out in a similar manner and are provided in the Appendix B for completeness.

We first state a lemma below summarizing some important properties on the functionals ${\mathcal{L}}_{i},i=1,\cdots,4$ . defined in (2.8).

Lemma 4.1.

For any $\mu\in{\mathcal{P}}({\mathcal{X}})$ and $\nu\in{\mathcal{P}}({\mathcal{Y}})$ , the following hold

(4.1)	$\displaystyle{\mathcal{L}}_{2}(\mu,\nu)$	$\displaystyle=\tau{\mathcal{H}}(\nu\|{\mathcal{K}}^{+}(\mu)),$
(4.2)	$\displaystyle{\mathcal{L}}_{4}(\mu,\nu)$	$\displaystyle=\tau{\mathcal{H}}(\mu\|{\mathcal{K}}^{-}(\nu)),$
(4.3)	$\displaystyle\tau{\mathcal{H}}(\mu\|\mu^{\ast})\leq{\mathcal{L}}_{1}(\mu)$	$\displaystyle\leq\tau{\mathcal{H}}(\mu\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu))),$
(4.4)	$\displaystyle\tau{\mathcal{H}}(\nu\|\nu^{\ast})\leq{\mathcal{L}}_{3}(\nu)$	$\displaystyle\leq\tau{\mathcal{H}}(\nu\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu))).$

Remark 4.1.

The sandwich inequalities (4.3) and (4.4) play an essential role in controlling terms in the entropy production of the Mean-Field GDA dynamics via the Lyapunov functions in order to close the Grönwall argument to obtain the dissipation of the latter along the dynamics. A similar sandwich inequality appeared in [7, Lemma 3.4] in the proof of convergence for the Mean-Field Langevin dynamics.

Next, we keep track of the time-derivatives of ${\mathcal{L}}_{1}(\mu_{t})$ and ${\mathcal{L}}_{2}(\mu_{t},\nu_{t})$ in the next proposition whose proof can be found in Appendix A.

Proposition 4.1.

Let $(\mu_{t},\nu_{t})$ be the solution to the DGA dynamics (1.6). Then

(4.5)

\displaystyle\frac{d}{dt}{\mathcal{L}}_{1}(\mu_{t})\leq-\frac{\tau^{2}}{2}{\mathcal{I}}(\mu_{t}|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\cdot{\mathcal{H}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t}))

and

(4.6)

\displaystyle\frac{d}{dt}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})\leq-\tau^{2}\eta{\mathcal{I}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t}))+\frac{\tau^{2}}{2}{\mathcal{I}}(\mu_{t}|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+3K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\cdot{\mathcal{H}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t})).

With Proposition 4.1, we are ready to present the proof of Theorem 2.1 and Theorem 2.2.

Proof of Theorem 2.1.

Thanks to Proposition 4.1 and identity (4.1), we have

	$\displaystyle\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})$	$\displaystyle\leq-\eta\tau^{2}\gamma{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\frac{\tau^{2}}{2}(1-\gamma){\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))$
		$\displaystyle\qquad+\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\tau}{\mathcal{L}}_{2}(\mu_{t},\nu_{t}).$

Observe also from Lemma 2.1 and sandwich inequality (4.3) that

	$\displaystyle\tau{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))$	$\displaystyle\geq\tau\lambda_{LS}{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))$
		$\displaystyle\geq\lambda_{LS}{\mathcal{L}}_{1}(\mu_{t}).$

Combining the last two displays leads to

	$\displaystyle\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})$	$\displaystyle\leq-\eta\tau^{2}\gamma{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\frac{\tau}{2}(1-\gamma)\lambda_{LS}{\mathcal{L}}_{1}(\mu_{t})+\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\tau}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})$
		$\displaystyle\leq-\eta\tau^{2}\gamma\lambda_{LS}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\frac{\tau}{2}(1-\gamma)\lambda_{LS}{\mathcal{L}}_{1}(\mu_{t})+\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\tau}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})$
		$\displaystyle=-\frac{\tau}{2}(1-\gamma)\lambda_{LS}{\mathcal{L}}_{1}(\mu_{t})-\tau\Big{(}\eta\gamma\lambda_{LS}-\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\tau^{2}}\Big{)}{\mathcal{L}}_{2}(\mu_{t},\nu_{t}).$

Now for any fixed $\gamma<1$ , we set

\eta=\frac{2K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\tau^{2}\gamma\lambda_{LS}}=\frac{2\lambda_{LS}\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\gamma}.

Then it follows from the last inequality that

\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})\leq-\alpha{\mathcal{L}}(\mu_{t},\nu_{t})

with

\displaystyle\alpha=\tau\lambda_{LS}\Big{(}\frac{1-\gamma}{2}\wedge\frac{\kappa^{2}\mathrm{Diam}({\mathcal{Y}})^{2}(1+3\gamma)}{\gamma}\Big{)}.

∎

Proof of Theorem 2.2.

First, thanks to Theorem 2.1, ${\mathcal{L}}(\mu_{t},\nu_{t})\leq e^{-\alpha t}{\mathcal{L}}(\mu_{0},\nu_{0})$ . In particular, for any $t>0$ ,

(4.7)

{\mathcal{L}}_{1}(\mu_{t})\leq e^{-\alpha t}{\mathcal{L}}(\mu_{0},\nu_{0})

and

(4.8)

\tau{\mathcal{H}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t}))={\mathcal{L}}_{2}(\mu_{t},\nu_{t})\leq\frac{e^{-\alpha t}}{\gamma}{\mathcal{L}}(\mu_{0},\nu_{0}).

As a result of (4.7) and (4.3), one obtains that

(4.9)

\tau{\mathcal{H}}(\mu_{t}|\mu^{\ast})\leq e^{-\alpha t}{\mathcal{L}}(\mu_{0},\nu_{0}).

Next, to obtain the exponential decay of ${\mathcal{H}}(\nu_{t}|\nu^{\ast})$ , notice first that

	$\displaystyle\tau{\mathcal{H}}(\nu_{t}\|\nu^{\ast})$	$\displaystyle=\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d\nu_{t}$
		$\displaystyle=\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d(\nu_{t}-\nu^{\ast})-\tau{\mathcal{H}}(\nu^{\ast}\|{\mathcal{K}}^{+}(\nu_{t}))$
		$\displaystyle\leq\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d(\nu_{t}-\nu^{\ast}).$

Since $\nu^{\ast}={\mathcal{K}}^{+}(\mu^{\ast})$ , we have

\displaystyle(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))(y)

\displaystyle=\tau^{-1}\int_{{\mathcal{X}}}K(x,y)(\mu_{t}(dx)-\mu^{\ast}(dx))-(\log Z^{+}(\mu_{t})-\log Z^{+}(\mu^{\ast})).

It follows from the last two displays that

(4.10)

\displaystyle\tau{\mathcal{H}}(\nu_{t}|\nu^{\ast})

\displaystyle\leq\tau{\mathcal{H}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t}))+\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)(\mu_{t}(dx)-\mu^{\ast}(dx))(\nu_{t}(dy)-\nu^{\ast}(dy)).

The last term on the right side above can be upper bounded by

(4.11)	$\displaystyle\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)(\mu_{t}(dx)-\mu^{\ast}(dx))(\nu_{t}(dy)-\nu^{\ast}(dy))$	$\displaystyle\leq\\|K\\|_{\infty}\cdot\text{TV}(\mu_{t},\mu^{\ast})\cdot\text{TV}(\nu_{t},\nu^{\ast})$
		$\displaystyle\leq 2\\|K\\|_{\infty}\sqrt{{\mathcal{H}}(\mu_{t}\|\mu^{\ast})}\cdot\sqrt{{\mathcal{H}}(\nu_{t}\|\nu^{\ast})}$
		$\displaystyle\leq\frac{\tau}{2}{\mathcal{H}}(\nu_{t}\|\nu^{\ast})+\frac{2\\|K\\|_{\infty}^{2}}{\tau}{\mathcal{H}}(\mu_{t}\|\mu^{\ast}).$

where we have used the Pinsker’s inequality and Young’s inequality in the last two lines above. Finally combining the last two estimates leads to

	$\displaystyle\tau{\mathcal{H}}(\nu_{t}\|\nu^{\ast})$	$\displaystyle\leq 2\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\frac{4\\|K\\|_{\infty}^{2}}{\tau}{\mathcal{H}}(\mu_{t}\|\mu^{\ast})$
		$\displaystyle\leq\Big{(}\frac{2}{\gamma}+\frac{4\\|K\\|_{\infty}^{2}}{\tau^{2}}\Big{)}e^{-\alpha t}{\mathcal{L}}(\mu_{0},\nu_{0}),$

where we have used inequalities (4.8) and (4.9) in the last inequality above.

∎

4.2. Proof of convergence for the annealed dynamics

Recall that the MNE of entropy-regularized objective $E_{\tau}$ is given by $(\mu^{\ast}_{\tau},\nu^{\ast}_{\tau})$ characterized by (1.1). Note that we emphasized the dependence of the objective and the optimizer on the temperature $\tau$ since the later will be time-dependent throughout this section.

It will be useful to define energies ${\mathcal{E}}_{i},i=1,2$ as follows.

(4.12)		$\displaystyle{\mathcal{E}}_{1}(\mu)$	$\displaystyle:=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E_{\tau}(\mu,\nu)=-\tau{\mathcal{H}}(\mu)+\tau\log Z^{+}(\mu),$
(4.12)		$\displaystyle{\mathcal{E}}_{2}(\nu)$	$\displaystyle:=\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E_{\tau}(\mu,\nu)=\tau{\mathcal{H}}(\nu)-\tau\log Z^{-}(\nu).$

It is clear that ${\mathcal{L}}_{1}(\mu)={\mathcal{E}}_{1}(\mu)-{\mathcal{E}}_{1}(\mu^{\ast})$ .

Proof of Theorem 2.3.

Similar to the last section, we only present here the proof for the fast ascent regime. The proof for the other regime can be carried out analogously which for completeness is provided in Appendix C. The proof of the entropy decays in (2.13) follows largely the proof of Theorem 2.1 and is also inspired by the proof of [7, Theorem 4.1].

Step 1. Bounding ${\mathcal{L}}_{1}(\mu_{t})={\mathcal{E}}_{1}(\mu_{t})-{\mathcal{E}}_{1}(\mu_{\tau_{t}}^{\ast})$ . First, let us compute the time-derivative $\frac{d}{dt}{\mathcal{E}}_{1}(\mu_{\tau_{t}}^{\ast})$ . Note that since

{\mathcal{E}}_{1}(\mu)=-\tau{\mathcal{H}}(\mu)+\tau\log Z^{+}(\mu),

we have for $\tau>0$ ,

	$\displaystyle\frac{d}{d\tau}{\mathcal{E}}_{1}(\mu_{\tau}^{\ast})$	$\displaystyle=-{\mathcal{H}}(\mu_{\tau}^{\ast})+\log Z^{+}(\mu_{\tau}^{\ast})$
		$\displaystyle\qquad+\tau\Big{(}\langle\log\mu_{\tau}^{\ast},\partial_{\tau}\mu_{\tau}^{\ast}\rangle+\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)K(x,y)\frac{d}{d\tau}(\tau^{-1}\mu^{\ast}_{\tau}(x))dydx\Big{)}.$

Moreover,

		$\displaystyle\tau\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)K(x,y)\frac{d}{d\tau}(\tau^{-1}\mu^{\ast}_{\tau}(x))dydx=-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)\tau^{-1}K(x,y)dy\mu^{\ast}_{\tau}(x)dx$
		$\displaystyle\qquad+\tau\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)\tau^{-1}K(x,y)dy\partial_{\tau}\mu^{\ast}_{\tau}(dx)$
		$\displaystyle=-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)\tau^{-1}K(x,y)dy\mu^{\ast}_{\tau}(x)dx-\tau\langle\log{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{\tau}^{\ast})),\partial_{\tau}\mu^{\ast}_{\tau}\rangle$

Combining the last two identities leads to

	$\displaystyle\frac{d}{d\tau}{\mathcal{E}}_{1}(\mu_{\tau}^{\ast})$	$\displaystyle=-{\mathcal{H}}(\mu_{\tau}^{\ast})+\log Z^{+}(\mu_{\tau}^{\ast})-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)\tau^{-1}K(x,y)dy\mu^{\ast}_{\tau}(x)dx$
		$\displaystyle+\underbrace{\tau\langle\log\mu_{\tau}^{\ast}-\log{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{\tau}^{\ast})),\partial_{\tau}\mu^{\ast}_{\tau}\rangle}_{=\langle\partial_{u}{\mathcal{E}}_{1}^{\tau}(u)\|_{u=\mu_{\tau}^{\ast}},\ \partial_{\tau}\mu^{\ast}_{\tau}\rangle=0}$
		$\displaystyle=\tau^{-1}{\mathcal{E}}_{1}(\mu^{\ast}_{\tau})-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau})(y)\tau^{-1}K(x,y)dy\mu^{\ast}_{\tau}(x)dx.$

Consequently, we have

(4.13)		$\displaystyle\frac{d}{dt}{\mathcal{E}}_{1}(\mu_{\tau_{t}}^{\ast})$	$\displaystyle=\tau^{\prime}_{t}\frac{d}{d\tau}{\mathcal{E}}_{1}(\mu_{\tau}^{\ast})\Big{\|}_{\tau=\tau_{t}}$
(4.13)			$\displaystyle=\tau^{\prime}_{t}\Big{(}\tau_{t}^{-1}{\mathcal{E}}_{1}(\mu^{\ast}_{\tau_{t}})-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau_{t}})(y)\tau_{t}^{-1}K(x,y)dy\mu^{\ast}_{\tau_{t}}(x)dx\Big{)}.$

Next, a similar calculation as above applied to ${\mathcal{E}}_{1}(\mu_{t})$ gives

(4.14)	$\displaystyle\frac{d}{dt}{\mathcal{E}}_{1}(\mu_{t})$	$\displaystyle=\tau^{\prime}_{t}\Big{(}\tau_{t}^{-1}{\mathcal{E}}_{1}(\mu_{t})-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu_{t})(y)\tau_{t}^{-1}K(x,y)dy\mu_{t}(x)dx\Big{)}$
		$\displaystyle\qquad+\tau_{t}\int_{{\mathcal{X}}}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}\cdot\partial_{t}\mu_{t}(dx)$
		$\displaystyle=\tau^{\prime}_{t}\Big{(}\tau_{t}^{-1}{\mathcal{E}}_{1}(\mu_{t})-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu_{t})(y)\tau_{t}^{-1}K(x,y)dy\mu_{t}(x)dx\Big{)}$
		$\displaystyle\qquad-\tau_{t}^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\mu_{t}(dx).$

As a result of (4.14) and (4.13),

(4.15)			$\displaystyle\frac{d}{dt}{\mathcal{L}}_{1}(\mu_{t})=\frac{d}{dt}({\mathcal{E}}_{1}(\mu_{t})-{\mathcal{E}}_{1}(\mu^{\ast}_{\tau_{t}}))$
			$\displaystyle=\frac{\tau_{t}^{\prime}}{\tau_{t}}\Big{[}{\mathcal{L}}_{1}(\mu_{t})-\Big{(}\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu_{t})(y)K(x,y)dy\mu_{t}(x)dx-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}{\mathcal{K}}^{+}(\mu^{\ast}_{\tau_{t}})(y)K(x,y)dy\mu^{\ast}_{\tau_{t}}(x)dx\Big{)}\Big{]}$
			$\displaystyle\qquad-\tau_{t}^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\mu_{t}(dx)$
			$\displaystyle\leq\frac{\tau_{t}^{\prime}}{\tau_{t}}\Big{(}{\mathcal{L}}_{1}(\mu_{t})+2\\|K\\|_{\infty}\Big{)}-\frac{\tau_{t}^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\cdot{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t})).$

Next, we have from the ascent dynamics for $\nu_{t}$ ,

(4.16)		$\displaystyle\frac{d}{dt}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})$	$\displaystyle=\tau^{\prime}_{t}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau_{t}\int_{{\mathcal{Y}}}\log\Big{(}\frac{d\nu_{t}}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}\partial_{t}\nu_{t}(dy)-\tau_{t}\int_{{\mathcal{Y}}}\frac{d}{dt}(\log{\mathcal{K}}^{+}(\mu_{t}))\nu_{t}(dy)$
(4.16)			$\displaystyle\leq\tau^{\prime}_{t}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\eta_{t}\tau_{t}^{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\tau_{t}\int_{{\mathcal{Y}}}\frac{d}{dt}(\log{\mathcal{K}}^{+}(\mu_{t}))\nu_{t}(dy).$

The third term on the RHS above is

		$\displaystyle-\tau_{t}\Big{(}\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\frac{d}{dt}(\tau_{t}^{-1}\mu_{t}(x))K(x,y)dx\nu_{t}(y)dy-\frac{d}{dt}\log(Z^{+}(\mu_{t}))\Big{)}$
		$\displaystyle=-\tau_{t}\Big{(}\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\frac{d}{dt}(\tau_{t}^{-1}\mu_{t}(x))K(x,y)dx(\nu_{t}(y)-{\mathcal{K}}^{+}(\mu_{t})(y))dy\Big{)}$
		$\displaystyle=-\frac{\tau^{\prime}_{t}}{\tau_{t}}\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\mu_{t}(x)K(x,y)dx(\nu_{t}(y)-{\mathcal{K}}^{+}(\mu_{t})(y))dy$
		$\displaystyle\qquad\qquad-\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\partial_{t}\mu_{t}(x)K(x,y)dx(\nu_{t}(y)-{\mathcal{K}}^{+}(\mu_{t})(y))dy$
		$\displaystyle=-\frac{\tau^{\prime}_{t}}{\tau_{t}}\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\mu_{t}(x)K(x,y)dx(\nu_{t}(y)-{\mathcal{K}}^{+}(\mu_{t})(y))dy$
		$\displaystyle\qquad+\tau_{t}^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}d\mu_{t}(x)$
		$\displaystyle\leq\frac{2\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}+\frac{\tau_{t}^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+3K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\cdot{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t})).$

Combining the last two displays yields

(4.17)			$\displaystyle\frac{d}{dt}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})\leq\Big{(}\tau^{\prime}_{t}+3K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\Big{)}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))-\eta_{t}\tau_{t}^{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))$
(4.17)			$\displaystyle\qquad+\frac{2\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}+\frac{\tau_{t}^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))).$

It then follows from (4.15) (4.17) that

		$\displaystyle\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})\leq-\frac{\tau_{t}^{2}(1-\gamma)\lambda_{LS}(\tau_{t})}{2}{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+\Big{(}\gamma\tau^{\prime}_{t}+(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\Big{)}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))$
		$\displaystyle+\frac{2(1+\gamma)\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}+\frac{\tau^{\prime}_{t}}{\tau_{t}}{\mathcal{L}}_{1}(\mu_{t})-\gamma\eta_{t}\tau_{t}^{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))$
		$\displaystyle\leq-\Big{(}\frac{(1-\gamma)\tau_{t}\lambda_{LS}(\tau_{t})}{2}-\frac{\tau^{\prime}_{t}}{\tau_{t}}\Big{)}{\mathcal{L}}_{1}(\mu_{t})-\Big{(}\gamma\eta_{t}\tau_{t}\lambda_{LS}(\tau_{t})-\frac{\gamma\tau^{\prime}_{t}}{\tau_{t}}-\frac{(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\tau_{t}}\Big{)}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})$
		$\displaystyle+\frac{2(1+\gamma)\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}$
		$\displaystyle\leq-\alpha_{t}{\mathcal{L}}(\mu_{t},\nu_{t})+\frac{2(1+\gamma)\\|K\\|_{\infty}}{t\log t},$

where the time-dependent rate satisfies for large $t$ that

	$\displaystyle\alpha_{t}$	$\displaystyle=\Big{(}\Big{(}\frac{(1-\gamma)\tau_{t}\lambda_{LS}(\tau_{t})}{2}-\frac{\tau^{\prime}_{t}}{\tau_{t}}\Big{)}\wedge\Big{(}\eta_{t}\tau_{t}\lambda_{LS}(\tau_{t})-\frac{\tau^{\prime}_{t}}{\tau_{t}}-\frac{(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\gamma\tau_{t}}\Big{)}\Big{)}$
		$\displaystyle\geq\frac{\xi}{\log t}\Big{(}C_{1}t^{-\xi_{\ast}/\xi}\wedge\Big{(}\eta_{t}t^{-\xi^{\ast}/\xi}+\frac{C_{2}}{t\log t}-\frac{C_{3}}{(\log t)^{2}}\Big{)}\Big{)}.$

Note that in the above we have used the decreasing of $\tau_{t}$ for large $t$ . By choosing $\eta_{t}\geq M\frac{t^{\xi^{\ast}/\xi}}{(\log t)^{2}}$ for some large $M>0$ , we have

\alpha_{t}\geq\frac{Ct^{-\xi^{\ast}/\xi-\epsilon}}{\log t}.

As a result, we have obtained that for any $\epsilon^{\prime}<1-\xi^{\ast}/\xi$ and for $t$ large enough,

\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})\leq-Ct^{-\xi^{\ast}/\xi-\epsilon^{\prime}}{\mathcal{L}}(\mu_{t},\nu_{t})+\frac{C^{\prime}}{t\log t}.

Define $Q(t)={\mathcal{L}}(\mu_{t},\nu_{t})-\frac{C^{\prime}}{C}t^{-1+\xi^{\ast}/\xi+\epsilon^{\prime}}$ . Then it is straightforward to show that for $t>t_{\ast}$ large enough,

\frac{d}{dt}Q(t)\leq-Ct^{-\xi^{\ast}/\xi-\epsilon^{\prime}}Q(t),

which implies that

(4.18)

{\mathcal{L}}(\mu_{t},\nu_{t})\leq Q(t_{\ast})e^{-\frac{C}{1-\xi^{\ast}/\xi-\epsilon}(t^{1-\xi^{\ast}/\xi-\epsilon^{\prime}}-t_{\ast}^{1-\xi^{\ast}/\xi-\epsilon^{\prime}})}+\frac{C^{\prime}}{C}t^{-1+\xi^{\ast}/\xi+\epsilon^{\prime}}\leq C^{\prime\prime}t^{-1+\xi^{\ast}/\xi+\epsilon^{\prime}}

since $\xi^{\ast}<\xi$ and $Q(t_{\ast})$ is finite. By the definition of ${\mathcal{L}}$ and the fact that $\log t\ll t^{\epsilon}$ for any $\epsilon>0$ , the last estimate further implies that for any $0<\epsilon<1-\xi^{\ast}/\xi$ ,

(4.19)

{\mathcal{H}}(\mu_{t}|\mu_{\tau_{t}}^{\ast})\leq C^{\prime\prime}t^{-1+\xi^{\ast}/\xi+\epsilon},\text{ for }t>t_{\ast}.

In addition, using the same arguments used in the proof of the second bound in (2.10) from Theorem 2.2, one can obtain that

{\mathcal{H}}(\nu_{t}|\nu_{\tau_{t}}^{\ast})\leq C^{\prime\prime}t^{-1+\xi^{\ast}/\xi+\epsilon},\text{ for }t>t_{\ast}.

Step 2: Bounding ${\text{NI}}(\mu_{t},\nu_{t})$ . Let us first claim that the difference ${\text{NI}}(\mu_{t},\nu_{t})-{\text{NI}}(\mu_{\tau_{t}}^{\ast},\nu_{\tau_{t}}^{\ast})$ satisfies

(4.20)

{\text{NI}}(\mu_{t},\nu_{t})-{\text{NI}}(\mu_{\tau_{t}}^{\ast},\nu_{\tau_{t}}^{\ast})\leq Ct^{-\frac{1-\xi^{\ast}/\xi-\epsilon}{2}}.

In fact, by definition,

		$\displaystyle{\text{NI}}(\mu_{t},\nu_{t})-{\text{NI}}(\mu_{\tau_{t}}^{\ast},\nu_{\tau_{t}}^{\ast})=\max_{\nu\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu_{t},\nu)-\max_{\nu\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu_{\tau_{t}}^{\ast},\nu)+\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu,\nu_{\tau_{t}}^{\ast})-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E_{0}(\mu,\nu_{t})$
		$\displaystyle=\max_{y\in{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)\mu_{t}(dx)-\max_{y\in{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)\mu_{\tau_{t}}^{\ast}(dx)$
		$\displaystyle\qquad+\min_{x\in{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\nu_{\tau_{t}}^{\ast}(dy)-\min_{x\in{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\nu_{t}(dy)$
		$\displaystyle=:J_{1}+J_{2}.$

To bound $J_{1}$ , let us define $y_{t}\in\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)\mu_{t}(dx)$ and $y^{\ast}_{t}\in\operatorname*{arg\,max}_{y\in{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)\mu_{\tau_{t}}^{\ast}(dx)$ . Then by the optimality of $y^{\ast}_{t}$ and the boundedness of $K$ ,

	$\displaystyle J_{1}$	$\displaystyle=\int_{{\mathcal{X}}}K(x,y_{t})\mu_{t}(dx)-\int_{{\mathcal{X}}}K(x,y^{\ast}_{t})\mu_{\tau_{t}}^{\ast}(dx)$
		$\displaystyle\leq\int_{{\mathcal{X}}}K(x,y_{t})\mu_{t}(dx)-\int_{{\mathcal{X}}}K(x,y_{t})\mu_{\tau_{t}}^{\ast}(dx)$
		$\displaystyle\leq\\|K\\|_{\infty}\text{TV}(\mu_{t},\mu_{\tau_{t}}^{\ast})$
		$\displaystyle\leq\sqrt{2}\\|K\\|_{\infty}\sqrt{{\mathcal{H}}(\mu_{t}\|\mu_{\tau_{t}}^{\ast})}$
		$\displaystyle\leq Ct^{-\frac{1-\xi^{\ast}/\xi-\epsilon}{2}}.$

The same bound holds for $J_{2}$ after applying a similar argument as above, which completes the proof of (4.20). Finally, applying Lemma 4.2 with $\tau=\tau_{t}=\xi/\log t$ , we have for $t$ large enough,

(4.21)

{\text{NI}}(\mu_{\tau_{t}}^{\ast},\nu_{\tau_{t}}^{\ast})\leq\frac{C\log(\log t)}{\log t}.

Hence the estimate (2.14) follows from (4.20) and (4.21).

∎

We restate [16, Theorem 5] in the following lemma which is used to control ${\text{NI}}(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ .

Lemma 4.2.

[16, Theorem 5] Let $\epsilon>0,\delta:=\epsilon/(2\text{Lip}(K))$ and let $V_{\delta}$ be a lower bound on the volume of a ball of radius of $\delta$ in ${\mathcal{X}}$ and ${\mathcal{Y}}$ . Let $(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ be the solution of the solution of (2.5). Then $(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ is an $\epsilon$ -Nash equilibrium of $E_{0}$ if

\tau\leq\frac{\epsilon}{4\log\Big{(}\frac{2(1-V_{\delta})}{V_{\delta}}(4\|K\|_{\infty}/\epsilon-1)\Big{)}}.

In particular, when ${\mathcal{X}}$ and ${\mathcal{Y}}$ are Riemannian manifolds or Euclidean tori of dimensions $d_{{\mathcal{X}}}$ and $d_{{\mathcal{Y}}}$ respectively so that $\text{Vol}(B_{x}^{\delta})\geq C\delta^{d_{{\mathcal{X}}}}$ and $\text{Vol}(B_{y}^{\delta})\geq C\delta^{d_{{\mathcal{Y}}}}$ , the bounds above become

\tau\leq\frac{C\epsilon}{\log\epsilon^{-1}}

for some constant $C>0$ depending only on $K,d_{{\mathcal{X}}},d_{{\mathcal{Y}}}$ . Alternatively, if $\tau$ is sufficiently small, then $(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ is an $\epsilon$ -Nash equilibrium with

(4.22)

\epsilon=\beta\tau(\log(1/\tau))\text{ for }\beta>d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1.

5. Conclusion and future work

In this paper, we proved the global exponential convergence of two-scale Mean-Field GDA dynamics for finding the unique MNE of the entropy-regularized game objective on the space of probability measures. We also proved that the convergence of the annealed GDA dynamics to the MNE of the unregularized game objective with respect to the Nikaidò-Isoda error. The key ingredient of our proofs are new Lyapunov functions which are used to capture the dissipation of the two-scale GDA dynamics in different scaling regimes.

We would like to mention several open problems and future research directions. First, although we have proved the global convergence of the Mean-Field GDA in the fast ascent/descent regime (with a finite but large/small time-scale ratio), it remains an open question to show the convergence or nonconvergence of the Mean-Field GDA in the intermediate time-scale regime, including particularly the case where no time-scale separation occurs (i.e. $\eta=1$ in (1.6)). Also, currently our results only hold on bounded state spaces and the convergence rate depends on the uniform bounds of the potential function $K$ on the state spaces. It remains an important question to extend the results to minmax optimization on unbounded state spaces. In practice, the Mean-Field GDA needs to be implemented by a certain interacting particle algorithm such as (1.5) with a large number of particles. Existing result on the mean field limit of (1.5) (e.g. [16, Theorem 3]) only holds in finite time interval and the error bound can potentially grow exponentially in time. To obtain a quantitative error analysis of the GDA for minmax optimization, it is an interesting open question to derive a uniform-in-time quantitative error bound between the particle system and the mean field dynamics. Finally, we anticipate our results can be exploited to prove theoretical convergence guarantees for a variety of minmax learning problems, including especially the training of GANs [20], adversarial learning problems [34], dual training of energy based models [10, 14] and weak adversarial networks for PDEs [57].

Acknowledgments

The author thanks Lexing Ying for suggesting the question and thanks Jianfeng Lu, Yiping Lu and Chao Ma for helpful discussions at the early stage of the problem setup. The author also thank Fei Cao and Lénaïc Chizat for the valuable feedback on an early version of the paper. This work is supported by the National Science Foundation through the award DMS-2107934.

Appendix

Appendix A Proofs of preliminary lemmas

Proof of Lemma 4.1.

First we have from the definition of $E$ and (2.4) that

	$\displaystyle{\mathcal{L}}_{2}(\mu,\nu)$	$\displaystyle=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)-E(\mu,\nu)$
		$\displaystyle=\tau\log Z^{+}(\mu)-\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\mu(dx)\nu(dy)-\tau{\mathcal{H}}(\nu)$
		$\displaystyle=\tau{\mathcal{H}}(\nu\|{\mathcal{K}}^{+}(\mu))$

which proves (4.1). To see (4.2), notice again from (2.4) that

	$\displaystyle{\mathcal{L}}_{4}(\mu,\nu)$	$\displaystyle=E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,\nu)$
		$\displaystyle=\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)\mu(dx)\nu(dy)-\tau{\mathcal{H}}(\mu)+\tau\log Z^{-}(\nu)$
		$\displaystyle=\tau{\mathcal{H}}(\mu\|{\mathcal{K}}^{-}(\nu)).$

Next, we prove (4.3). In fact, replacing $\nu$ by ${\mathcal{K}}^{-}(\mu)$ in the last display leads to

	$\displaystyle\tau{\mathcal{H}}(\mu\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu)))$	$\displaystyle={\mathcal{L}}_{4}(\mu,{\mathcal{K}}^{+}(\mu))$
		$\displaystyle=E(\mu,{\mathcal{K}}^{+}(\mu))-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,{\mathcal{K}}^{+}(\mu))$
		$\displaystyle=\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}E(\mu,{\mathcal{K}}^{+}(\mu))$
		$\displaystyle\geq\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)-\min_{\mu\in{\mathcal{P}}({\mathcal{X}})}\max_{\nu\in{\mathcal{P}}({\mathcal{Y}})}E(\mu,\nu)$
		$\displaystyle={\mathcal{L}}_{1}(\mu),$

which proves the lower bound part of (4.3). To prove the upper bound part, we first compute the first-variation of the log partition function $\log Z^{+}(\mu)$ as

(A.1)

\frac{\partial}{\partial\mu}\log Z^{+}(\mu)=\tau^{-1}\int_{{\mathcal{Y}}}K(x,y)d{\mathcal{K}}^{+}(\mu)(y)=-\log({\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu)))-\log Z^{-}({\mathcal{K}}^{+}(\mu)).

Then an application of the convexity of $\mu{\rightarrow}\log Z^{+}(\mu)$ shown in Lemma A.1 yields

	$\displaystyle\log Z^{+}(\mu)-\log Z^{+}(\mu^{\ast})$	$\displaystyle\geq\int_{{\mathcal{X}}}\frac{\partial\log Z^{+}(\mu)}{\partial\mu}\Big{\|}_{\mu=\mu^{\ast}}(d\mu-d\mu^{\ast})$
		$\displaystyle=-\int_{{\mathcal{X}}}\log({\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu^{\ast})))(d\mu-d\mu^{\ast})$
		$\displaystyle=-\int_{{\mathcal{X}}}\log(\mu^{\ast})(d\mu-d\mu^{\ast}).$

Consequently, one obtains that

	$\displaystyle{\mathcal{L}}_{1}(\mu)$	$\displaystyle={\mathcal{E}}_{1}(\mu)-{\mathcal{E}}_{1}(\mu^{\ast})$
		$\displaystyle=-\tau({\mathcal{H}}(\mu)-{\mathcal{H}}(\mu^{\ast}))+\tau(\log Z^{+}(\mu)-\log Z^{+}(\mu^{\ast}))$
		$\displaystyle\geq\tau\int\log\mu d\mu-\int\log\mu^{\ast}d\mu^{\ast}-\int_{{\mathcal{X}}}\log(\mu^{\ast})(d\mu-d\mu^{\ast})$
		$\displaystyle=\tau{\mathcal{H}}(\mu\|\mu^{\ast}).$

Finally, the inequality (4.4) follows from the same reasoning above by exploiting the convexity of $\nu{\rightarrow}\log Z^{-}(\nu)$ .

∎

The following lemma establishes the convexity of the log partition functions $\log Z^{+}(\mu)$ and $\log Z^{-}(\nu)$ . It was proved in [33, Proposition 3], but for completeness we include its proof here.

Lemma A.1.

Both the functional $\mu{\rightarrow}\log Z^{+}(\mu)$ and the functional $\nu{\rightarrow}\log Z^{-}(\nu)$ are convex.

Proof.

We only present the proof for the convexity of the map $\mu{\rightarrow}\log Z^{+}(\mu)$ since the other case can be proved in the same manner. For any $\mu_{1},\mu_{2}\in{\mathcal{P}}({\mathcal{X}})$ and $\alpha\in(0,1)$ ,

		$\displaystyle Z^{+}(\alpha\mu_{1}+(1-\alpha)\mu_{2})$
		$\displaystyle=\log\Big{(}\int_{{\mathcal{Y}}}\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)(\alpha\mu_{1}(dx)+(1-\alpha)\mu_{2}(dx))\Big{)}dy\Big{)}$
		$\displaystyle=\log\Big{(}\int_{{\mathcal{Y}}}\exp\Big{(}\alpha\int_{{\mathcal{X}}}\tau^{-1}K(x,y)\mu_{1}(dx)\Big{)}\cdot\exp\Big{(}(1-\alpha)\int_{{\mathcal{X}}}\tau^{-1}K(x,y)\mu_{2}(dx)\Big{)}dy\Big{)}$
		$\displaystyle\leq\log\Big{(}\Big{(}\int_{{\mathcal{Y}}}\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)\mu_{1}(dx)\Big{)}dy\Big{)}^{\alpha}\cdot\Big{(}\int_{{\mathcal{Y}}}\exp\Big{(}\int_{{\mathcal{X}}}\tau^{-1}K(x,y)\mu_{2}(dx)\Big{)}dy\Big{)}^{1-\alpha}\Big{)}$
		$\displaystyle=\alpha Z^{+}(\mu_{1})+(1-\alpha)Z^{+}(\mu_{2}).$

∎

Proof of Proposition 4.1.

First let us compute the functional gradient $\frac{\partial{\mathcal{L}}_{1}}{\partial u}(\mu_{t}).$ In fact, thanks to the fact that ${\mathcal{L}}_{1}(\mu)={\mathcal{E}}_{1}(\mu)-{\mathcal{E}}_{1}(\mu^{\ast})$ and (4.12), one has that

	$\displaystyle\frac{\partial{\mathcal{L}}_{1}}{\partial u}\Big{\|}_{\mu=\mu_{t}}$	$\displaystyle=-\tau\frac{\partial}{\partial u}\Big{(}{\mathcal{H}}(\mu)-\log Z^{+}(\mu)\Big{)}\Big{\|}_{\mu=\mu_{t}}$
		$\displaystyle=\tau\Big{(}\log\mu+\tau^{-1}\int_{{\mathcal{Y}}}K(x,y)d{\mathcal{K}}^{+}(\mu)(y)\Big{)}\Big{\|}_{\mu=\mu_{t}}$
		$\displaystyle=\tau\Big{(}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}-\log Z^{-}({\mathcal{K}}^{+}(\mu_{t}))\Big{)},$

where in the second identity we have used (A.1). Therefore it follows from (1.6) and the Cauchy-Schwarz inequality that

	$\displaystyle\frac{d}{dt}{\mathcal{L}}_{1}(\mu_{t})$	$\displaystyle=\int_{{\mathcal{X}}}\frac{\partial{\mathcal{L}}_{1}}{\partial u}(\mu_{t})d(\partial_{t}\mu_{t})$
		$\displaystyle=\tau^{2}\int_{{\mathcal{X}}}\Big{(}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}-\log Z^{-}({\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))\Big{)}\nabla_{x}\cdot\Big{(}\mu_{t}\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{)}dx$
		$\displaystyle=-\tau^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}d\mu_{t}(x)$
		$\displaystyle=-\tau^{2}\int_{{\mathcal{X}}}\Big{\|}\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}\Big{\|}^{2}d\mu_{t}(x)$
		$\displaystyle\qquad-\tau^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}d\mu_{t}(x)$
		$\displaystyle\leq-\frac{\tau^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+\frac{\tau^{2}}{2}\int_{{\mathcal{X}}}\Big{\|}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{\|}^{2}d\mu_{t}(x).$

Furthermore, using the fact that

{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))\propto\exp\Big{(}-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d{\mathcal{K}}^{+}(\mu_{t})(y)\Big{)},\quad{\mathcal{K}}^{-}(\nu_{t})\propto\exp\Big{(}-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d\nu_{t}(y)\Big{)},

one derives that

(A.2)

\displaystyle\frac{1}{2}\int_{{\mathcal{X}}}\Big{|}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{|}^{2}d\mu_{t}(x)

\displaystyle=\frac{1}{2\tau^{2}}\int_{{\mathcal{X}}}\Big{|}\int_{{\mathcal{Y}}}\nabla_{x}K(x,y)(d{\mathcal{K}}^{+}(\mu_{t})(y)-d\nu_{t}(y))\Big{|}^{2}d\mu_{t}(x).

Moreover, using the mean value theorem, one has for any $y_{0}\in{\mathcal{Y}}$ that

\nabla_{x}K(x,y)-\nabla_{x}K(x,y_{0})=\Big{[}\int_{0}^{1}\nabla_{xy}^{2}K(x,y_{0}+s(y-y_{0}))s\,ds\Big{]}(y-y_{0}).

Inserting the last identity into (A.2) leads to

(A.3)		$\displaystyle\frac{1}{2}\int_{{\mathcal{X}}}\Big{\|}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{\|}^{2}d\mu_{t}(x)$	$\displaystyle\leq\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{2\tau^{2}}\text{TV}^{2}({\mathcal{K}}^{+}(\mu_{t}),\nu_{t})$
(A.3)			$\displaystyle\leq\frac{K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\tau^{2}}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t})),$

where we have used the Pinsker’s inequality in the last inequality above. Combining the last two estimates proves (4.5).

Next we proceed with the proof of (4.6). Recall from (4.1) that

{\mathcal{L}}_{2}(\mu,\nu)=\tau{\mathcal{H}}(\nu|{\mathcal{K}}^{+}(\mu))=\tau\int_{{\mathcal{Y}}}\log\Big{(}\frac{\nu}{{\mathcal{K}}^{+}(\mu)}\Big{)}d\nu.

Hence

(A.4)

\displaystyle\frac{d}{dt}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})=\tau\Big{(}\int_{{\mathcal{Y}}}\log\Big{(}\frac{\nu_{t}}{{\mathcal{K}}^{+}(\mu_{t})}\Big{)}d(\partial_{t}\nu_{t})-\int_{{\mathcal{Y}}}\frac{d}{dt}\log({\mathcal{K}}^{+}(\mu_{t}))d\nu_{t}\Big{)}

Using the second equation of (1.6) that $\nu_{t}$ solves, one sees that the first term on the right side above becomes

(A.5)

\tau\Big{(}\int_{{\mathcal{Y}}}\log\Big{(}\frac{\nu_{t}}{{\mathcal{K}}^{+}(\mu_{t})}\Big{)}d(\partial_{t}\nu_{t})=-\eta\tau^{2}{\mathcal{I}}(\nu_{t}|{\mathcal{K}}^{+}(\mu_{t})).

To compute the second term on the right side of (A.4), observe that

\log{\mathcal{K}}^{+}(\mu_{t})=\tau^{-1}\int_{{\mathcal{X}}}K(x,y)d\mu_{t}(x)-\log(Z^{+}(\mu_{t})).

An a result of above and (A.1), one obtains that

		$\displaystyle-\tau\int_{{\mathcal{Y}}}\frac{d}{dt}\log({\mathcal{K}}^{+}(\mu_{t}))d\nu_{t}$
		$\displaystyle=-\tau\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}\Big{(}\tau^{-1}K(x,y)-\frac{\partial\log(Z^{+}(\mu))}{\partial\mu}(\mu_{t})\Big{)}d(\partial_{t}\mu_{t}(x))d\nu_{t}(y)$
		$\displaystyle=-\tau\int_{{\mathcal{X}}}\Big{(}\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d\nu_{t}(y)-\int_{{\mathcal{Y}}}\tau^{-1}K(x,y)d{\mathcal{K}}^{+}(\mu_{t})(y)\Big{)}d(\partial_{t}\mu_{t}(x))$
		$\displaystyle=-\tau\int_{{\mathcal{X}}}\Big{(}\log({\mathcal{Z}}^{-}({\mathcal{K}}^{+}(\mu_{t})){\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))-\log({\mathcal{Z}}^{-}(\nu_{t}){\mathcal{K}}^{-}(\nu_{t}))\Big{)}d(\partial_{t}\mu_{t}(x))$
		$\displaystyle=\tau^{2}\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}d\mu_{t}(x)$
		$\displaystyle=\tau^{2}\Big{(}\int_{{\mathcal{X}}}\Big{\|}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{\|}^{2}d\mu_{t}(x)$
		$\displaystyle\qquad+\int_{{\mathcal{X}}}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\cdot\nabla_{x}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}d\mu_{t}(x)\Big{)}$
		$\displaystyle\leq\frac{\tau^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+\frac{3\tau^{2}}{2}\int_{{\mathcal{X}}}\Big{\|}\nabla_{x}\log\Big{(}\frac{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}{d{\mathcal{K}}^{-}(\nu_{t})}\Big{)}\Big{\|}^{2}d\mu_{t}(x)$
		$\displaystyle\leq\frac{\tau^{2}}{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+3K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t})),$

where we have used (A.3) in the last inequality above. The estimate (4.6) then follows from above, (A.5) and (A.4). This completes the proof of the proposition. ∎

Proof of Lemma 4.2.

The proof of the lemma can be found in [16, Appendix C.4]. We would like to elaborate on the proof of (4.22). In fact, by tracking the proof of [16, Theorem 5], one sees that $(\mu_{\tau}^{\ast},\nu_{\tau}^{\ast})$ is an $\epsilon$ -Nash equilibrium provided that

e^{\frac{{\varepsilon}}{2\tau}}\Big{(}\frac{\text{Vol}(B_{x}^{\delta})}{1-\text{Vol}(B_{x}^{\delta})}\vee\frac{\text{Vol}(B_{y}^{\delta})}{1-\text{Vol}(B_{y}^{\delta})}\Big{)}\geq 2(4\|K\|_{\infty}/\epsilon-1),

where we recall that $\delta=\epsilon/(2\text{Lip}(K))$ . Thanks to the lower bound on the volume of small balls in ${\mathcal{X}}$ and ${\mathcal{Y}}$ , the inequality above holds if

e^{\frac{\epsilon}{2\tau}}\geq C_{1}\epsilon^{-(d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1)}

for some $C_{1}>0$ depending only on $K,d_{{\mathcal{X}}},d_{{\mathcal{Y}}}$ . Now with the choice (4.22) for $\epsilon$ with $\beta>d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1$ , one has for $\tau$ sufficiently small that

\displaystyle e^{\frac{{\varepsilon}}{2\tau}}\geq\frac{1}{\tau^{\beta}}>\frac{C_{1}}{\beta^{d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1}}\Big{(}\frac{1}{\tau\log(1/\tau)}\Big{)}^{d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1}=C_{1}\epsilon^{-(d_{{\mathcal{X}}}\vee d_{{\mathcal{Y}}}+1)}.

∎

Appendix B Proofs of convergence for Mean-Field GDA in the fast descent regime

Let us first state a proposition which bounds the time-derivative of ${\mathcal{L}}_{2}(\nu_{t})$ and ${\mathcal{L}}_{4}(\mu_{t},\nu_{t})$ .

Proposition B.1.

Let $(\mu_{t},\nu_{t})$ be the solution to the DGA dynamics (1.6). Then

(B.1)

\frac{d}{dt}{\mathcal{L}}_{3}(\nu_{t})\leq-\frac{\eta\tau^{2}}{2}{\mathcal{I}}(\nu_{t}|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}\cdot{\mathcal{H}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t}))

and

(B.2)

\frac{d}{dt}{\mathcal{L}}_{4}(\mu_{t},\nu_{t})\leq-\tau^{2}{\mathcal{I}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t}))+\frac{\eta\tau^{2}}{2}{\mathcal{I}}(\nu_{t}|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+3\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}\cdot{\mathcal{H}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t})).

Proof.

The proof follows essentially the same reasoning as the proof of Proposition 4.1. In fact, it can be shown by a straightforward calculation that

	$\displaystyle\frac{d}{dt}{\mathcal{L}}_{2}(\nu_{t})$	$\displaystyle=-\eta\tau^{2}\int_{{\mathcal{Y}}}\nabla_{y}\log\Big{(}\frac{d\nu_{t}}{d{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t}))}\Big{)}\cdot\nabla_{y}\log\Big{(}\frac{d\nu_{t}}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}d\nu_{t}(y)$
		$\displaystyle\leq-\frac{\eta\tau^{2}}{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+\frac{\eta\tau^{2}}{2}\int_{{\mathcal{Y}}}\Big{\|}\nabla_{y}\log\Big{(}\frac{d{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t}))}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}\Big{\|}^{2}d\nu_{t}(y)$

Similar to (A.3), one can obtain that

\displaystyle\frac{\eta\tau^{2}}{2}\int_{{\mathcal{Y}}}\Big{|}\nabla_{y}\log\Big{(}\frac{d{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t}))}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}\Big{|}^{2}d\nu_{t}(y)\leq\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}\cdot{\mathcal{H}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t})).

Combining the last two inequalities yield (B.1).

As for time-derivative of ${\mathcal{L}}_{4}(\mu_{t},\nu_{t})$ , one has that

\displaystyle\frac{d}{dt}{\mathcal{L}}_{4}(\mu_{t},\nu_{t})=-\tau^{2}{\mathcal{I}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t}))-\eta\tau^{2}\int_{{\mathcal{Y}}}\nabla_{y}\log\Big{(}\frac{d{\mathcal{K}}^{+}(\mu_{t})}{d{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t}))}\Big{)}\cdot\nabla_{y}\log\Big{(}\frac{d\nu_{t}}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}d\nu_{t}(y).

The second term on the right side above is bounded by

		$\displaystyle\eta\tau^{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+\frac{3\eta\tau^{2}}{2}\int_{{\mathcal{Y}}}\Big{\|}\nabla_{y}\log\Big{(}\frac{d{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t}))}{d{\mathcal{K}}^{+}(\mu_{t})}\Big{)}\Big{\|}^{2}d\nu_{t}(y)$
		$\displaystyle\leq\frac{\eta\tau^{2}}{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+3\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}\cdot{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t})).$

The estimate (B.2) follows directly from the last two inequalities. ∎

Proof of Part (ii) of Theorem 2.1 .

It follows from Proposition B.1 that

	$\displaystyle\frac{d}{dt}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})$	$\displaystyle\leq-\frac{\eta\tau^{2}}{2}(1-\gamma){\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))-\gamma\tau^{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))$
		$\displaystyle+\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}(1+3\gamma)\cdot{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t})).$

Thanks to Lemma 2.1 and (4.4),

	$\displaystyle\tau{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))$	$\displaystyle\geq\tau\lambda_{LS}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))$
		$\displaystyle\geq\lambda_{LS}{\mathcal{L}}_{3}(\nu_{t}).$

As a result of above and (4.2),

\displaystyle\frac{d}{dt}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})

\displaystyle\leq-\frac{\eta\tau}{2}(1-\gamma)\lambda_{LS}{\mathcal{L}}_{3}(\nu_{t})-\tau\Big{(}\gamma\lambda_{LS}-\eta K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}(1+3\gamma)\Big{)}{\mathcal{L}}_{4}(\mu_{t},\nu_{t}).

Therefore setting

\eta=\frac{\gamma\tau^{2}\lambda_{LS}}{2K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}(1+3\gamma)}

and applying the Grönwall’s inequality to above leads to

\displaystyle\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})\leq e^{-\alpha t}\widetilde{{\mathcal{L}}}(\mu_{0},\nu_{0})

with

\alpha=\frac{\tau\lambda_{LS}}{2}\Big{(}1\wedge\eta(1-\gamma)\Big{)}.

∎

Proof of Part (ii) of Theorem 2.2.

Thanks to Part (ii) of Theorem 2.1 and the bound (4.4), we have that

(B.3)

\tau{\mathcal{H}}(\nu_{t}|\nu^{\ast})\leq\widetilde{L}(\mu_{t},\nu_{t})\leq e^{-\alpha_{1}t}\widetilde{L}(\mu_{0},\nu_{0})

and that

(B.4)

\tau{\mathcal{H}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t}))={\mathcal{L}}_{4}(\mu_{t},\nu_{t})\leq\frac{e^{-\alpha_{1}t}}{\gamma}\widetilde{L}(\mu_{0},\nu_{0}).

Next to obtain the exponential decay of $\tau{\mathcal{H}}(\mu_{t}|\mu^{\ast})$ , observe that

(B.5)	$\displaystyle\tau{\mathcal{H}}(\mu_{t}\|\mu^{\ast})$	$\displaystyle=\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d\mu_{t}$
		$\displaystyle=\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d(\mu_{t}-\mu^{\ast})-\tau{\mathcal{H}}(\mu^{\ast}\|{\mathcal{K}}^{-}(\nu_{t}))$
		$\displaystyle\leq\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d(\mu_{t}-\mu^{\ast}).$

Since $\mu^{\ast}={\mathcal{K}}^{-}(\nu^{\ast})$ , we can write

\displaystyle\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast}=-\tau^{-1}\int_{{\mathcal{Y}}}K(x,y)(\nu_{t}-\nu^{\ast})(dy)-(\log Z^{-}(\nu_{t})-\log Z^{-}(\nu^{\ast})).

Hence the second term on the RHS of the last line of (B.5) can be bounded by in a similar manner as (4.11). Namely,

	$\displaystyle\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d(\mu_{t}-\mu^{\ast})$	$\displaystyle=\int_{{\mathcal{X}}}\int_{{\mathcal{Y}}}K(x,y)(\nu_{t}-\nu^{\ast})(dy)(\mu_{t}-\mu^{\ast})(dx)$
		$\displaystyle\leq\frac{\tau}{2}{\mathcal{H}}(\mu_{t}\|\mu^{\ast})+\frac{2\\|K\\|_{\infty}^{2}}{\tau}{\mathcal{H}}(\nu_{t}\|\nu^{\ast}).$

Combining the last inequality with (B.5) leads to

	$\displaystyle\tau{\mathcal{H}}(\mu_{t}\|\mu^{\ast})$	$\displaystyle\leq 2\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\frac{4\\|K\\|_{\infty}^{2}}{\tau}{\mathcal{H}}(\nu_{t}\|\nu^{\ast})$
		$\displaystyle\leq\Big{(}\frac{2}{\gamma}+\frac{4\\|K\\|_{\infty}^{2}}{\tau^{2}}\Big{)}e^{-\alpha_{2}t}\widetilde{L}(\mu_{0},\nu_{0}),$

where we have used (B.3) and (B.4) in the last inequality. ∎

Appendix C Proof of convergence for the annealed dynamics in the fast descent regime

Proof of Part (ii) of Theorem 2.3.

By a direct calculation, one has

(C.1)

\displaystyle\frac{d}{dt}{\mathcal{L}}_{3}(\nu_{t})\leq\frac{\tau_{t}^{\prime}}{\tau_{t}}({\mathcal{L}}_{3}(\nu_{t})+2\|K\|_{\infty})-\frac{\eta_{t}\tau_{t}^{2}}{2}{\mathcal{I}}(\nu_{t}|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+\eta_{t}K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}{\mathcal{H}}(\mu_{t}|{\mathcal{K}}^{-}(\nu_{t}))

and

(C.2)		$\displaystyle\frac{d}{dt}{\mathcal{L}}_{4}(\mu_{t},\nu_{t})$	$\displaystyle\leq\frac{\tau_{t}^{\prime}}{\tau_{t}}({\mathcal{L}}_{4}(\nu_{t})+2\\|K\\|_{\infty})-\tau_{t}^{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\frac{\tau_{t}^{2}\eta_{t}}{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))$
(C.2)			$\displaystyle+3\eta_{t}K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t})).$

Combining the last two displays, one can obtain the time-derivative of $\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})$ as follows

	$\displaystyle\frac{d}{dt}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})$	$\displaystyle\leq\frac{\tau_{t}^{\prime}}{\tau_{t}}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})+\frac{\tau_{t}^{\prime}}{\tau_{t}}2(1+\gamma)\\|K\\|_{\infty}-\gamma\tau_{t}^{2}{\mathcal{I}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))$
		$\displaystyle-\frac{(1-\gamma)\eta_{t}\tau_{t}^{2}}{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}({\mathcal{K}}^{-}(\nu_{t})))+\eta_{t}(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))$
		$\displaystyle\leq\frac{\tau_{t}^{\prime}}{\tau_{t}}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})-\frac{(1-\gamma)\eta_{t}\tau_{t}\lambda_{LS}(\tau_{t})}{2}{\mathcal{L}}_{3}(\nu_{t})-\tau_{t}\Big{(}\gamma\lambda_{LS}(\tau_{t})$
		$\displaystyle\qquad-\frac{\eta_{t}(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}}{\tau_{t}^{2}}\Big{)}{\mathcal{L}}_{4}(\mu_{t},\nu_{t})+\frac{2\tau_{t}^{\prime}}{\tau_{t}}(1+\gamma)\\|K\\|_{\infty}$
		$\displaystyle\leq-\alpha_{2}(t)\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})+\frac{2\tau_{t}^{\prime}}{\tau_{t}}(1+\gamma)\\|K\\|_{\infty},$

where

	$\displaystyle\alpha_{2}(t)$	$\displaystyle=\frac{(1-\gamma)\eta_{t}\tau_{t}\lambda_{LS}(\tau_{t})}{2}\wedge\tau_{t}\Big{(}\lambda_{LS}(\tau_{t})-\frac{\eta_{t}(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{X}})^{2}}{\gamma\tau_{t}^{2}}-\frac{\tau_{t}^{\prime}}{\tau_{t}}\Big{)}$
		$\displaystyle\geq\frac{\xi}{\log t}t^{-(\xi^{\ast}/\xi)}\Big{(}C_{1}\eta_{t}\wedge\Big{(}t^{-(\xi^{\ast}/\xi)}+\frac{C_{2}}{t\log t}-\frac{C_{3}\eta_{t}}{\log(t)^{2}}\Big{)}\Big{)}.$

Setting $\eta_{t}=c\log t/t$ for some $c<C_{2}/C_{3}$ in the above yields that for every $0<\epsilon<1-\xi^{\ast}/\xi$ and $t$ large enough

\alpha_{2}(t)\geq Ct^{-2\xi^{\ast}/\xi-\epsilon}.

Therefore we have obtained that

\displaystyle\frac{d}{dt}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})\leq-Ct^{-2\xi^{\ast}/\xi-\epsilon}\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})+\frac{C^{\prime}}{t\log t}.

Similar to the proof of (4.18), one can obtain from above that for $t$ large enough

\widetilde{{\mathcal{L}}}(\mu_{t},\nu_{t})\leq C^{\prime\prime}t^{-1+2\xi^{\ast}/\xi+\epsilon}.

This directly implies the entropy decay bounds in (2.15). Finally the estimate (2.16) follows from (2.15) and the arguments used in Step 2 of the proof of Theorem 2.3- Part(i). ∎

References

[1] Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv:1906.02027, 2019.
[2] Dyego Araújo, Roberto I Oliveira, and Daniel Yukimura. A mean-field limit for certain deep neural networks. arXiv preprint arXiv:1906.00193, 2019.
[3] Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629–681, 2017.
[4] Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930–945, 1993.
[5] Yann Brenier and Dmitry Vorotnikov. On optimal transport of matrix-valued measures. SIAM Journal on Mathematical Analysis, 52(3):2849–2873, 2020.
[6] Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156–172, 2008.
[7] Lénaïc Chizat. Mean-field langevin dynamics: Exponential convergence and annealing. arXiv preprint arXiv:2202.01009, 2022.
[8] Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in neural information processing systems, 31, 2018.
[9] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard. An interpolating distance between optimal transport and fisher–rao metrics. Foundations of Computational Mathematics, 18(1):1–44, 2018.
[10] Bo Dai, Zhen Liu, Hanjun Dai, Niao He, Arthur Gretton, Le Song, and Dale Schuurmans. Exponential family estimation via adversarial dynamics embedding. Advances in Neural Information Processing Systems, 32, 2019.
[11] Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. Advances in neural information processing systems, 31, 2018.
[12] Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. 10th Innovations in Theoretical Computer Science, 2019.
[13] Thinh Doan. Convergence rates of two-time-scale gradient descent-ascent dynamics for solving nonconvex min-max problems. In Learning for Dynamics and Control Conference, pages 192–206. PMLR, 2022.
[14] Carles Domingo-Enrich, Alberto Bietti, Marylou Gabrié, Joan Bruna, and Eric Vanden-Eijnden. Dual training of energy-based models with overparametrized shallow neural networks. arXiv preprint arXiv:2107.05134, 2021.
[15] Carles Domingo-Enrich and Joan Bruna. Simultaneous transport evolution for minimax equilibria on measures. arXiv preprint arXiv:2202.06460, 2022.
[16] Carles Domingo-Enrich, Samy Jelassi, Arthur Mensch, Grant Rotskoff, and Joan Bruna. A mean-field analysis of two-player zero-sum games. Advances in neural information processing systems, 33:20215–20226, 2020.
[17] Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Quantitative harris-type theorems for diffusions and mckean–vlasov processes. Transactions of the American Mathematical Society, 371(10):7135–7173, 2019.
[18] Tadahisa Funaki. A certain class of diffusion processes associated with nonlinear parabolic equations. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 67(3):331–348, 1984.
[19] Irving L Glicksberg. A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 3(1):170–174, 1952.
[20] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139–144, 2020.
[21] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
[22] Ya-Ping Hsieh, Chen Liu, and Volkan Cevher. Finding mixed nash equilibria of generative adversarial networks. In International Conference on Machine Learning, pages 2810–2819. PMLR, 2019.
[23] Kaitong Hu, Zhenjie Ren, David Šiška, and Łukasz Szpruch. Mean-field langevin dynamics and energy landscape of neural networks. In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, volume 57, pages 2043–2065. Institut Henri Poincaré, 2021.
[24] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconcave minimax optimization? In International conference on machine learning, pages 4880–4889. PMLR, 2020.
[25] Stanislav Kondratyev, Léonard Monsaingeon, and Dmitry Vorotnikov. A new optimal transport distance on the space of finite radon measures. Advances in Differential Equations, 21(11/12):1117–1164, 2016.
[26] Stanislav Kondratyev and Dmitry Vorotnikov. Spherical hellinger–kantorovich gradient flows. SIAM Journal on Mathematical Analysis, 51(3):2053–2084, 2019.
[27] Vaios Laschos and Alexander Mielke. Geometric properties of cones with applications on the hellinger–kantorovich space, and a new distance on the space of probability measures. Journal of Functional Analysis, 276(11):3529–3576, 2019.
[28] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, pages 6083–6093. PMLR, 2020.
[29] Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterization from depth. In International Conference on Machine Learning, pages 6426–6436. PMLR, 2020.
[30] Yulong Lu, Jianfeng Lu, and James Nolen. Accelerating langevin sampling with birth-death. arXiv preprint arXiv:1905.09863, 2019.
[31] Yulong Lu, Dejan Slepčev, and Lihan Wang. Birth-death dynamics for sampling: Global convergence, approximations and their asymptotics. arXiv preprint arXiv:2211.00450, 2022.
[32] Chao Ma, Lei Wu, et al. The barron space and the flow-induced function spaces for neural network models. Constructive Approximation, 55(1):369–406, 2022.
[33] Chao Ma and Lexing Ying. Provably convergent quasistatic dynamics for mean-field two-player zero-sum games. In International Conference on Learning Representations, 2021.
[34] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
[35] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665–E7671, 2018.
[36] Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. arXiv preprint arXiv:1807.02629, 2018.
[37] Andrew Ronald Mitchell and David Francis Griffiths. The finite difference method in partial differential equations. A Wiley-Interscience Publication, 1980.
[38] John Nash. Non-cooperative games. Annals of Mathematics, 54:286–295, 1951.
[39] Phan-Minh Nguyen. Mean field limit of the learning dynamics of multilayer neural networks. arXiv preprint arXiv:1902.02880, 2019.
[40] Hukukane Nikaido. On von neumann’s minimax theorem. Pacific J. Math, 4(1):65–72, 1954.
[41] Hukukane Nikaido and Kazuo Isoda. Note on non-cooperative convex games. Pacific Journal of Mathematics, 5(S1):807–815, 1955.
[42] Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Convex analysis of the mean field langevin dynamics. In International Conference on Artificial Intelligence and Statistics, pages 9741–9757. PMLR, 2022.
[43] Georgii Ivanovich Petrov. Application of the method of galerkin to a problem involving the stationary flow of a viscous fluid. Prikl. Matem. Mekh., 4(3):3–12, 1940.
[44] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674–1703. PMLR, 2017.
[45] Grant Rotskoff, S Jelassi, Joan Bruna, and Eric Vanden-Eijnden. Global convergence of neuron birth-death dynamics. 2019.
[46] Grant Rotskoff and Eric Vanden-Eijnden. Trainability and accuracy of artificial neural networks: An interacting particle system approach. Communications on Pure and Applied Mathematics, 75(9):1889–1935, 2022.
[47] Maurice Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):171–176, 1958.
[48] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725–752, 2020.
[49] Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of deep neural networks. Mathematics of Operations Research, 47(1):120–152, 2022.
[50] Alain-Sol Sznitman. Topics in propagation of chaos. In Ecole d’Eté $de$ $probabilit\'{e}s$ $de$ Saint-Flour XIX-1989, pages 165–251. Springer, 1991.
[51] Wenpin Tang and Xun Yu Zhou. Simulated annealing from continuum to discretization: a convergence analysis via the eyring–kramers law. arXiv preprint arXiv:2102.02339, 2021.
[52] J Von. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295–320, 1928.
[53] Guillaume Wang and Lénaïc Chizat. An exponentially converging particle method for the mixed nash equilibrium of continuous games. arXiv preprint arXiv:2211.01280, 2022.
[54] Stephan Wojtowytsch et al. On the banach spaces associated with multi-layer relu networks: Function representation, approximation theory and gradient descent dynamics. arXiv preprint arXiv:2007.15623, 2020.
[55] Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for a class of nonconvex-nonconcave minimax problems. Advances in Neural Information Processing Systems, 33:1153–1165, 2020.
[56] Junchi Yang, Antonio Orvieto, Aurelien Lucchi, and Niao He. Faster single-loop algorithms for minimax optimization without strong concavity. In International Conference on Artificial Intelligence and Statistics, pages 5485–5517. PMLR, 2022.
[57] Yaohua Zang, Gang Bao, Xiaojing Ye, and Haomin Zhou. Weak adversarial networks for high-dimensional partial differential equations. Journal of Computational Physics, 411:109409, 2020.

	$\displaystyle\tau{\mathcal{H}}(\nu_{t}\|\nu^{\ast})$	$\displaystyle=\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d\nu_{t}$
		$\displaystyle=\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d(\nu_{t}-\nu^{\ast})-\tau{\mathcal{H}}(\nu^{\ast}\|{\mathcal{K}}^{+}(\nu_{t}))$
		$\displaystyle\leq\tau{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))+\tau\int_{{\mathcal{Y}}}(\log({\mathcal{K}}^{+}(\mu_{t}))-\log(\nu^{\ast}))d(\nu_{t}-\nu^{\ast}).$

(4.11)	$\displaystyle\int_{{\mathcal{Y}}}\int_{{\mathcal{X}}}K(x,y)(\mu_{t}(dx)-\mu^{\ast}(dx))(\nu_{t}(dy)-\nu^{\ast}(dy))$	$\displaystyle\leq\\|K\\|_{\infty}\cdot\text{TV}(\mu_{t},\mu^{\ast})\cdot\text{TV}(\nu_{t},\nu^{\ast})$
		$\displaystyle\leq 2\\|K\\|_{\infty}\sqrt{{\mathcal{H}}(\mu_{t}\|\mu^{\ast})}\cdot\sqrt{{\mathcal{H}}(\nu_{t}\|\nu^{\ast})}$
		$\displaystyle\leq\frac{\tau}{2}{\mathcal{H}}(\nu_{t}\|\nu^{\ast})+\frac{2\\|K\\|_{\infty}^{2}}{\tau}{\mathcal{H}}(\mu_{t}\|\mu^{\ast}).$

		$\displaystyle\frac{d}{dt}{\mathcal{L}}(\mu_{t},\nu_{t})\leq-\frac{\tau_{t}^{2}(1-\gamma)\lambda_{LS}(\tau_{t})}{2}{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t})))+\Big{(}\gamma\tau^{\prime}_{t}+(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}\Big{)}{\mathcal{H}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))$
		$\displaystyle+\frac{2(1+\gamma)\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}+\frac{\tau^{\prime}_{t}}{\tau_{t}}{\mathcal{L}}_{1}(\mu_{t})-\gamma\eta_{t}\tau_{t}^{2}{\mathcal{I}}(\nu_{t}\|{\mathcal{K}}^{+}(\mu_{t}))$
		$\displaystyle\leq-\Big{(}\frac{(1-\gamma)\tau_{t}\lambda_{LS}(\tau_{t})}{2}-\frac{\tau^{\prime}_{t}}{\tau_{t}}\Big{)}{\mathcal{L}}_{1}(\mu_{t})-\Big{(}\gamma\eta_{t}\tau_{t}\lambda_{LS}(\tau_{t})-\frac{\gamma\tau^{\prime}_{t}}{\tau_{t}}-\frac{(1+3\gamma)K_{xy}^{2}\mathrm{Diam}({\mathcal{Y}})^{2}}{\tau_{t}}\Big{)}{\mathcal{L}}_{2}(\mu_{t},\nu_{t})$
		$\displaystyle+\frac{2(1+\gamma)\\|K\\|_{\infty}\|\tau^{\prime}_{t}\|}{\tau_{t}}$
		$\displaystyle\leq-\alpha_{t}{\mathcal{L}}(\mu_{t},\nu_{t})+\frac{2(1+\gamma)\\|K\\|_{\infty}}{t\log t},$

	$\displaystyle\frac{\partial{\mathcal{L}}_{1}}{\partial u}\Big{\|}_{\mu=\mu_{t}}$	$\displaystyle=-\tau\frac{\partial}{\partial u}\Big{(}{\mathcal{H}}(\mu)-\log Z^{+}(\mu)\Big{)}\Big{\|}_{\mu=\mu_{t}}$
		$\displaystyle=\tau\Big{(}\log\mu+\tau^{-1}\int_{{\mathcal{Y}}}K(x,y)d{\mathcal{K}}^{+}(\mu)(y)\Big{)}\Big{\|}_{\mu=\mu_{t}}$
		$\displaystyle=\tau\Big{(}\log\Big{(}\frac{d\mu_{t}}{d{\mathcal{K}}^{-}({\mathcal{K}}^{+}(\mu_{t}))}\Big{)}-\log Z^{-}({\mathcal{K}}^{+}(\mu_{t}))\Big{)},$

(B.5)	$\displaystyle\tau{\mathcal{H}}(\mu_{t}\|\mu^{\ast})$	$\displaystyle=\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d\mu_{t}$
		$\displaystyle=\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d(\mu_{t}-\mu^{\ast})-\tau{\mathcal{H}}(\mu^{\ast}\|{\mathcal{K}}^{-}(\nu_{t}))$
		$\displaystyle\leq\tau{\mathcal{H}}(\mu_{t}\|{\mathcal{K}}^{-}(\nu_{t}))+\tau\int_{{\mathcal{X}}}(\log{\mathcal{K}}^{-}(\nu_{t})-\log\mu^{\ast})d(\mu_{t}-\mu^{\ast}).$