Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems
Authors: Juno Kim
Kakei Yamamoto
Kazusato Oko
Zhuoran Yang
Taiji Suzuki
Venue: ICLR 2024 spotlight (2024)
Keywords: mean-field Langevin dynamics
minimax optimization
zero-sum games
Markov games
Primary area: optimization

Abstract: In this paper, we extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably convergent updates. We propose \emph{mean-field Langevin averaged gradient} (MFL-AG), a single-loop algorithm that implements gradient descent ascent in the distribution spaces with a novel weighted averaging, and establish average-iterate convergence to the mixed Nash equilibrium. We also study both time and particle discretization regimes and prove a new uniform-in-time propagation of chaos result which accounts for the dependency of the particle interactions on all previous distributions. Furthermore, we propose \emph{mean-field Langevin anchored best response} (MFL-ABR), a symmetric double-loop algorithm based on best response dynamics with linear last-iterate convergence. Finally, we study applications to zero-sum Markov games and conduct simulations demonstrating long-term optimality.

Published as a conference paper at ICLR 2024
SYMMETRIC MEAN-FIELD LANGEVIN DYNAMICS FOR DISTRIBUTIONAL MINIMAX PROBLEMS
Juno Kim
Kakei Yamamoto' Kazusato Oko Zhuoran Yang* Taiji Suzuki!?2
TTee University of Tokyo, Tokyo, Japan Center for Advanced Intelligence Project, RIKEN "assachusetts Institute of Technology, Cambridge, MA junokimeg.co ecc. u-tcc..-okoo.... jc.jp
Yale University, New Haven, CT
ABSTRACT
In this paper, we extend mean-field Langevin dynamics to minimax optimization over probability distributions for the first time with symmetric and provably con- vergent updates. We propose mean-field Langevin averaged gradienl (MFI.-AG), a single-loop algorithm that implements gradient descent ascent in the distribution spaces with novel weighted averaging, and establish average-iterate convergence to the mixed Nash equilibrium. We also study both time and particle discretiza- tion regimes and prove accounts for the dependency of the particle interactions on all previous distri- butions. Furthermore, we propose mean-field Langevin anchored best response (MFL-ABR), a symmetric double-loop algorithm based on best response dynam- ics with linear last-iterate convergence. Finally, we study applications to zero-sum Markov games and conduct simulations demonstrating long-term optimality.
uniform-in-tinee propagation of chaos result which
INTRODUCTION
The mean-field Langevin dynamics (MFLD) provides powerful theoretical tools to analyze opti- mization on the space of probability measures such as the training two-layer neural networks (Mei al., 2018; Chizat & Bach, 2018). The McKean-Vlasse stochastic process corresponds the Wasserstein gradient flow minimizing an entropy-regullrizee convex functional, where the Gaus- sian noise encourages exploration and ensures global convergence (Hu al., 2021: Chizat, 2022; Nitanda et al., 2022a). Langevin- based methods are especially attractive as they capture nonlinear aspects of learning as well admit efficient particle discretizations. However, it remains unclear how to extend beyond single-objective optimization problems in principled manner.
In this work, we develop MFLD for distributional minimax optimization problems. Denote by (X))),, P2()) the spaces of probability measures of finite variance on X, with fixed base measures p², p". We consider the entropy-rreullarized saddle point problem for a convex-concate functional L: P2(2)) x P2(3') I with regularization strength temperature À >> 0,
()(M,V), ()(1,v) L(,, + XKI(HUlP") AKL(VIP"). (X) PEPa(3)
min
(1)
This formulation encompasses all objectives of the form L(,,v) = [[x ()u(dr))(dg) for generic noncomvex-momconcan potentials Q. Such problems naturally arise for example in training generative adversarial networks (Goodfellow et al., 2020; Arjovsky et al., 2017: Hsieh et al., 2019), robust learning (Madry et al., 2018: Sinha et al., 2018) or solving zero-sum games in reinforcement learning (Daskalakis & Panageas, 2019; Domingo-Enrich et al., 2020; Zeng et al., 2022).
One is immediately led consider mean-field Langevin descent ascent (MFL-DA) dynamics, the coupled distributionn-deeedeent stochastic processes which seek to simultaneously minimize L over fu and maximize over (see Appendix A.2 for definitions of functional derivative and convexity):
dX,- ( Vz &L (J,, (X,) A log n² (Xt) dt + v2XdW!. 14 = Law(Xx),
8C dy, (V y Au (u,, (YY) + AV log p² (Y:)) dt + 22d Pt = Law(YY),,
'Throughout the paper, sub/superscripts such /f p" differentiate quantities related to the min and max variables, and do not indicate dependency on the distributions μ,, V. Our results are casily extended to different temperatures for each variable. We will also present many results for μ and omit the analogous statement for

---

Published as a conference paper at ICLR 2024
where W WT" are independent Brownian motions. Descent ascent methods are more challenging to analyze compared to their single optimization counterparts; it is known that simultaneous up- dates may display cyclic or divergent behavior even for the simplest matrix games (Daskalakis & Panageas, 2019). For finite strategy spaces, a vigorous line of research has established convergence guarantees by employing optimistic extragradient update rules; see Cen al. (2023); Zeng et al. (2022) for an overview of recent literature and applications to Markov games.
Unfortunately, the convergence of MFL-DA is to the best of our knowledge still an open problem, and mean-field minimax dynamics remains largely unexplored. Existing results fail to establish convergence guarantees (Domingo-Enrick) Enrich et al.. 2020) or only give proofs for near-static flows where one strategy updates extremely or even infinitely quickly compared to the other (Ma & Ying, 2021; Lu, 2022). These works also impose the unrealistic assumption that X, y are both compact Riemannian manifolds without boundary. In contrast, we allow X, y to be Euclidean spaces.
Another fundamental consideration when implementing mean-field dynamics is to account for the errors arising from time discretization and particle approximation in non-asymptotic manner, the latter referred to as propagation of chaos (Sznitman, 1). Prior works generally give error bounds that blow up exponentially as training progresses (Mei et al., 201 8; De Bortoli et al., 2020); uniform- in-time results were proven in the single optimization case only recently by Chen et al. (2022); Suzuki et al. (2023). Hence are faced with the following research question:
Can we develop symmetric MFLD algorithms for distributional minimax problems with global convergence guarantees, and further provide uniform-ine inettime---teeeeee control over discretization errors?
1.1 SUMMARY OF CONTRIBUTIONS
We address the above problem by proposing mean-field Langevin averaged gradient, a symmetric single-loop algorithm which takes inspiration from dual averaging methods and replaces the MFL- DA drift with the historical weighted average. We prove average-iterate convergence to the mixed Nash equilibrium. We also study both time and particle discretization and establish in-time propagation of chaos result. The analysis is greatly complicated by the dependence of the interactions on all previous distributions and the techniques developed are of independent interest.
uniform-
In addition, we propose symmetric double-loop algorithm, mean-field Langevin anchored best re- sponse, which realizes the best-response flow suggested in Lascu al. (2023) via an inner loop run- ning Langevin dynamics. We show that the outer loop updates enjoy last-iterate linear convergence to the mixed Nash equilibrium. Furthermore, we apply our theory zero-sum Markov games and propose two-step iterative scheme that finds the regularized Markov perfect equilibrium. Finally, we numerically demonstrate the superior optimality of both algorithms compared to MFL.-DA.
PROBLEM SETTING AND ASSUMPTIONS
Denote by P2(R*) the space of probability measures on Idd equipped with the Borel o-algebra with finite second moment. Let X' = Rxx y = dy and L (2') P2())) - IR be weakly convex- concave functional. Our objective is to find the mixed Nash equilibrium (MNE) solving (1). Entropic regularization is frequently adopted in minimax optimization to account for imperfect information and ensure good convergence properties (McKelvey & Palfrey, 1995; Sokota et al., 2023).
We proceed state our assumptions which are standard in the MFLD literature (Suzuki et al., 2023).
Assumption 1 (Regularity of p", ,"")") We assume that pM = exp(-U** and p² = exp(- for Ty- and strsngyygly convex potentials UH X - R and U - + R. respectively. Furthermore, V.Ue and V yUU" are Ru- and R, Rip-sipshiitz repsectively, and V V,U"(0) = (0) 00
Assumption 2 (Regularity of L for MFL-AG). We assume L is convex-concave and admits C' functional derivatives 8L SL
op Su at any (H,v), whose gradients are uniformly bounded, and Lipschitz continuous with respect to the input and p.u. That is, there exist constants K,, Lys M,, 0 such op (x)))
that [| 5C
< My and
V op (1) & 5f (ut, (ud,,,//)))) w)))') S K₁ -'1l (W (1, (2)
for all x. x', pb and The same properties hold for V BC 8y
with Ko, Lwu M, 0.
2

---

Published as a conference paper at ICLR 2024
Assumption 2 implies in particular that by
5c is My--ipschitzz and 4 -(u,v) is M,-Lipschitz in W1. To present our results at full generality, do require boundedness of the functional derivatives 85 and ac which would nevertheless simplify some arguments and improve for instance 5n 8v the log-Sobolev constants via the Holley-Stroode argument (aatiennttPProni (Proposition A.4).
The KI. regularization is enough assure existence and uniqueness of the MNE via application of the Kakutani fixed-point theorem (Conforti et al., 2020); see Appendix A.2 for the proof.
Proposition 2.1 (Existence and uniqueness of MNE). Under Assumptions I and 2, the solution (4","") to (1) uniquely exists and satisfies the first-order equations
μ x p" exp (- -
166 (m²,"")) w²)), X
V x p² exp (u
(3)
The suboptimality of any given pair (1,, is quantified via the Nikaidō-Isodke (NI) error (Nikaidó & Isoda, 1955).
NI(H,)) = max Cx(H,e') min Cx(e', v'EP(())
('EP(())
From the discussion in the proof of Proposition 2.1, it follows that NT(,, 2 0 and NT(,, if and only if μ ,=, = v². A pair (p, 1) satisfying NI(H, S is called an e-MNE. As is usual both discrete (Cen et al., 2021; Wei et al., 2021) and continuous (Lu, 2022: Lascu al., 2023) minimax settings, our main goal is to prove convergence of the NI error along the proposed algorithms, which also implies convergence to the MNE in relative entropy (Lemma 3.5).
Cen et al. (2023) also point out that the MNE serves to approximate the MNE of the unregularized objective L as À - O. However, L may not possess an MNE at all, e.g. for some bilinear objectives. Domingo-EEnrch et al. (2020); Lu (2022) bypass this issue by assuming 2/ ) are compact manifolds without boundary, in which case existence guaranteed by Glicksberg theorem. Alternatively, we may restrict the initialization and solution space to (L()())") R. KL(vllp") < R. for some large radius R. Furthermore, if L does possess an MNE, it is possible to adopt the X = @(1 log t) cooling schedule studied in Lu (2022) for which results be modified to ensure O(1/ log convergence to the unregularized MNE. Nonetheless, our focus is on the regularized problem Lx.
MEAN-FIELD LANGEVIN AVERAGED GRADIENT
3.1 PROPOSED METHOO
The main obstruction to proving convergence of MFL-DA is the complicated dependency of the proximal Gibbs distribution ğ for μ on the opposing policy v. Motivated by dual averaging methods (Nesterov, 2009; Xiao, 2009; Nitanda et al.. 2022b), our idea is simply to take the average of the drift over time so that the slowdown of the rolling average will ensure convergence of the KI. gap.
We propose the mean-field Langevin averaged gradient (MFL-AG) flow with weighting scheme (3e)20 and temperature À > the coupled pair of
McKean- -lasov processes
SC
dX, = B.
3.
(Ma, U. (x)) +x XV2U((X.)
dt + v2XdW,"
on
SC
dY:
3.
dn (Me, u. - dt V2XdW
B,
where μr Law(Laa))))) 14 Law(Y:) and W.". W are independent Brownian motions X and V. respectively. The corresponding particle algorithm is studied Section 3.3.
By weighting scheme we mean any integrable function 3 (3:) R220 R>0 where the normal- izing weight B, = fo 3g ds satisfies B, - oo and /./ BB + as t - co. These conditions are roughly equivalent to (2(1/t) < 3r Ō(e") and ensure that the most recent update continues to influence the rolling average, but at an ever-decreasing rate. We will often substitute 3r for a fixed exponent to obtain explicit convergence rates.
The dependence on previous distributions (Js, V/)ast serves as a major point of departure from most existing works mean-field dynamics. Nevertheless, existence and uniqueness of the flow (4) can be verified by extending the classical contraction argument of Sznitman (1991). The proof can be found in Appendix B.1.
3

---

Published as a conference paper at ICLR 2024
Proposition 3.1 (Well-definedness of MFL-AG flow). Under Assumptions and 2, the MFL-AG flow (X,, Ye) (4) with continuous sample paths uniquely exists for all [0, oo) for any initial distribution Mo Po E P22)").
The Fokker-Planck equations corresponding to the system (4) can be formulated as
Nt dep -v=
Br Jo S B.V.
Sc (Ms, U.) ds + Aps VaU + 14 = ~V=: V4 log
Ht Rr.
Ut
["
dc (1s, ds Aay V -= (v.V log
u1 Di
0.44 - -.y
V.V
Bi Ju
ōv
where Pe: Dr are the MFL-AG proximal distributions given as
(Me: (u,, v,)dds) ( 8μ
dc B.
('
8C (Ms: Uo) Vs)
Py x pf exp
0r x p² exp XB, Jo dv
3.
(5)
XB,
which are well-defined due to the strong convexity of UH, U and Assumption 2.
MFL.AG is similar in spirit fictitious play methods (Brown, 1951) in the two-player zero-sum game setting with 3 = I, where each player assumes their opponent has stationary strategy and optimizes based on the average behavior of the opponent; the ideal fictitious play algorithm would perform the update 1 f... If Be is increasing, the algorithm can be considered to undervalue older information which is more suitable for non-stationary environments. However, such methods require exact computation of the optimal response every step which is generally unfeasible. In contrast, the MFL-AG policies continuously flow towards their response policies at any given time.
As usual, me P. satisfy a Soboloo incquality which is crucial to controlling the mean-field flows. The mild dependency O₂ = (21/dxx is the only manifestation dimensional dependence in our results, and can be avoided in cases where the Polley-Stroock argument applies. See Appendix A. for details.
Proposition 3.2. Let the probability measure μ x p exp(-X-11)) P2(X) with |Millaa S M Then under Assumption I, μ satisfies the log-Sobie rog-ooooevv and Talagrand's inequalities with constant
0g 2
aM2 AA
2d
4
Mp A
+
2 V
( TH
2
2
dx
log
e² e²R,,
4M2
MR e
TH
2
r4 rp
3.2 CONTINUOUS-TH -IME CONVERGENCE
We begin by studying the properties of the flow (4). At each time t the policies evolve towards the proximal distributions, and the deceleration of the rolling average allows the flow to catch up with F4, De; this observation plays key part in further analyses. Note that we state many results for only the min policy μ and omit the analogous statement for v.
Proposition 3.3 (Proximal convergence of MFL-AG flow). Under Assumptions I and 2. for the weighting scheme Br = l" with a fixed exponent >> -1 the proximal KI. gap is bounded as
2(r + 1)
KL(M ll P.) <
at + +(t
See Appendix B.2 for the proof. It is then clear that if MFL-AG converges, it must converge to the MNE (3) by setting Pso = Poo V/c = Do..
For ordinary MFLD, KL gap convergence of the above type is generally enough to show absolute convergence through entropy sandwich incqualities, see c.g. Nitanda et al. (2022a); Lu (2022). In case, however, the relative entropy longer quantifies the optimality gap at (J4, 2/2) since the proximal distributions are no longer 'state functions' and depend on the entire history in (5). Nevertheless, we are able to obtain our first main result, average-iterate convergence of MFL-AG. Our approach, detailed in Appendix B.3, extends conjugate function arguments from dual averaging the minimax setting and also leverages the preceding O(1/t2) KL gap convergence.
Theorem 3.4 (Average-iterate convergence of MFL-AG flow). Denote the weighted average of the MFL-AG distributions up to time ih B, So Bapss ds, i, So B.V, ds. Then under
4

---

The propagation of chaos framework recently developed in Chen al. (2022); Suzuki et al. (2023) relies on a lifted proximal distribution (N) on the configuration space N. By integrating out the conditioning on the previous step in the continuity equation, this is used to elegantly control the Published as a conference paper at ICLR 2024
Algorithm 1 Mean-field Langevin Averaged Gradient
Require: temperature A, max epochs K, learning rate 77, number of particles N, exponent Initialization: L K, V K +- Ø, Li, "
for k == =ark11.-.. 1. K - 1 do
For all particles i = 1....
N sample 5k ~ (00 (xx) ~ (0,, Tay) and update (XX + 2
X X Br Σラ 2j=1 83 V.
op
k+1 Yi +
J Bu
و== B3 (1 Vy (3,) (Y() XnV + 22
BC
end for for k= == 1, 1.... K do
Sample [BgNN/Bk] particles from Lx. 3 and concatenate with H K, V K, resp.
end for return I K. 3 K
Assumptions and 2, for the weighting scheme Bt = t with fixed exponent > 0, the NI error of the averaged pair Pt, Ut converges with rate
M
4(r+1)²
NI(T,, S
rX2t + +
at
#
and the leading term is optimized when Bg = t. For the unweighted averaging scheme Br = 1,
M
M²
4logt
Ni B.)
+0((t))
a
X²t
In light of Lemma 3.5 (proved in Appendix A.2), Theorem 3.4 immediately implies convergence with the same rate of (me F2) in relative entropy to the MNE, Lemma 3.5 (Entropy sandwich lower bound). For any μ E P2(X) and E (P2())) it holds that KL(μ|)и²" + KI((D]>>*) S S
The weighting exponent r can be thought of as a hyperparameter controlling the following trade- off. A larger r tends to give more weight to recent information, which leads faster-moving average and slower convergence of the proximal gap (Proposition 3.3). However, it also allows for faster convergence of the weighted average the MNE. The rate is optimized when is in agreement with works such as Tao et al. (2021) on dual averaging and Guo et al. (2020) on stochastic gradient descent which incorporate averaging with increasing weights B, x to obtain improved rates (~ 1/t) compared to the unweighted averages (~ logt/t).
which
3.3 TIME AND SPACE DISCRETIZATION
We now summarize our discretization analysis of MFL-AG developed throughout Appendix C. Our study incorporates both a discrete time step y for the Langevin flow and particle approximations for the laws P. Denote ordered sets of N particles by 2 = (X and the corresponding empirical distributions by u. N E ox., Va update 2i 3 will depend on the full history (2ij. w.),, where 2, and 3 are sampled independently from initial distributions μº E P2(X') and v" P2()), respectively.
1=1 E XN y (Y E y i=1 5y The
In order to implement gradient averaging, the integral in (4) must be replaced by the discrete-time average with respect to sequence of weights (BK)ReN; the cumulative weights are denoted as B₁ E,=3,, By. Moreover, the final average of 14 ... Mex may be computed by randomly sampling 3.N/BK particles from each set 2x and concatenating. See Algorithm for details.
evolution of the joint distribution μ (N) of the N particles. In our case, however, the dependency on the full history (Ki:k, xxx cannot be integrated out consistently and must be retained:
p (2)) x NNN (2 exp (- exp N XB
8L (uzs, vag )u )p=((z)) ōu
Σ
Bg
5

---

Published as a conference paper at ICLR 2024
This renders the KL gap argument with (N) inaccessible and must work step-by-step with the atomic measures p.g., v which further complicates matters as we cannot directly utilize metrics involving Mag, in order to avoid the curse of dimensionality. Instead, we prove and exploit the following uniform law of large numbers (Appendix C.3).
Proposition 3.6. Let F P2(X)) x P2()) x X + R. (,, + ((), be a functional such that F(,,1) v) is -ipscchtz on X and further satisfies
[F( F((,,(")l
(,, + (i(),
If'n S. 7=== 2[L, +XR A To A F.d +AR,) then for all integers k. N holds that
A
Te and the weight sequence 3q. = k2' for 2 0, axRg
a. R. US F(H.2,, Mu 1I 1 (dm)))) &
r+1 Ci(r C2V k
C3
(6)
VN
The same bound also holds for the max policy v. The constants C2. C2,C3 only depend on problem quantities (including the ISI constants) with at most polynomial order, while the function C1 de- pends on problem quantities and rj.
Here, II denotes the average of the N pushforward operators along the coordinate projection maps 2' + X'. The main idea of the proof is to look backwards in time: close enough so that the dy- namics nearly particl-independdee
due to the slowdown of the averaged gradient, but far enough to assure exponential convergence to the approximate stationary distribution. Furthermore, the W1- Lipschitz leave-one-out argument in Step 3 shows that the O(1/ (LL/VN) rate is optimal.
We finally present our main discretization error bound: the proof presented in Appendix C.5. Theorem 3.7 (Convergence of discretized MFL-AG), Denote the averaged empirical distributions
as 17, v E Σi= B3 V7, 1 Σ B,Vey, If n S 1) and Bx K" with > 0, the MFL.-G discrete update satisfies for all K, N,
B.
(r+1)² rK
(EElEy + W/ Billy, liv2))
VN
with similar constants as in Proposition 3.6. Ifr O, the first term is replaced by O(log K/ K).
Hence the errors arising from time and particle discretization are separately bounded as O( and O(1//N). An unfortunate byproduct of the perturbation analysis is a roughly 17 - order dependency in the constant C1 (1)) nonetheless, the convergence in time is O(1/K) for any fixed n. particular, for any specified error >> we can take 7) = O(e) and N (E=))) as well as K O(c-//a so that W? (Eij x 1, + W? v*) <.
We remark that the squared Wasserstein distance is natural measure of optimality consistent with the continuous-time rate obtained Theorem 3.4 in view of Lemma 3.5. Note that Theorem 3.7 quantifies the bias of the MFL.AG outputs, but does not tell us anything about the variance. In Appendix C.6, we give bound for the expected distance (" ,/²)) + W1 W1 (",,,"") v²)] and also discuss why the curse of dimensionality unavoidable in this setting.
MEAN-FIELD LANGEVIN ANCHORED BEST RESPONSE
4.1 PROPOSED METHON
Our second proposal builds upon the mean-field best response (MF-BR) flow recently proposed in Lascu et al. (2023). There, the authors prove that the strategies (pt, M4 )220 given by the linear flow
du((x) = (x) (x(x)) dt, dvz(x) = (D (x) v1(1)) dt,
with speed 3 > 0 converge exponentially to the unique MNE, where 7, x pM exp (- 1 aL (pt. vt)), (1 exp 32
D. x exp
& v)) are the best response proximal distributions, so called because they are
the optimal responses against the current policies of all players (rather than the historical average

---

Published as a conference paper at ICLR 2024
in MFL-AG). However, major weakness of MF-BR is that the flow is not directly realizable by particle algorithm.
We therefore propose the mean-field Langevin anchored best response (MFL-ABR) process by in- corporating an inner loop running Langevin dynamics, decoupled by anchoring the gradient at the output (jk, vx) of the previous outer loop:
Vx dL 5y
X p", dxp -
(mx, (ma, (x.) + +V dt v2XdW2' OstsT,
and similarly for Y The outputs at time denoted by p/.-- = Law(X "/6-- = Law(Y; serve as approximations of the best response proximal distributions (replacing time t with the discrete index k). The outer loop then performs the discretized MF-BR update,
Pk+1 = (1 - 3) + Spkk. M/+1 = (1 - B)vs + By
where (4g = pM 40 = p². The flow can be immediately realized by a simple particle algorithm; see Algorithm 2 in the appendix. similar method for single convex optimization was also recently implemented in Chen et al. (2023) but without any theoretical guarantees.
4.2 CONTINUOUS-TIME CONVERGENCE
To analyze the convergence of MFL-ABR, we require the following alternative assumptions for which are taken from Lascu et al. (2023).
Assumption (Regularity of for MFL-ABR), We assume that convex-concave and admits C' functional derivatives which are uniformly bounded as 11 (H, v)lle I C.,. 11 (),,))loo S C for constants Cu.Cr Cv > 0. Furthermore, I, admits second order functional derivatives which are 1
uniformly bounded as || 11.00 S Cpps 1 lox S Cuuen
1 Imx S Cvv and symmetric in the 8yōv (H, X. öv8n (H, v, y, x) for all μ. and x E ExyE
sense that 8-C
Existence and uniqueness of the MNE still hold under this assumption as proved Lascu et al. (2023). Also, n., De both satisfy the LSI with constant a = ru exp ( (- 4C,, A Tu exp (- -C" by the Holley-Stroock argument; take the minimum since it dominates the overall convergence rate.
We now present the overall convergence result for MFL-ABR. The proof, given in Appendix D.2, is combination of time-discretized version of the argument in Lascu et al. (2023) for the outer loop and TV distance perturbation analysis for the inner loop developed in Appendix D.1.
Theorem 4.1 (Convergence of MFL-ABR). The NI error of the MFL-ABR outer loop output after k steps is bounded for constant C' as
NI( vk) & 2(C + cxp(
1 cx))xp((oo)
CB.
Hence we achieve linear convergence in the outer loop iteration, with a uniform-in iifform-in-timee inner loop eтror linearly converging in r and time discretization етrоr proportional to 3. It follows that an c-MNE may be obtained in k { log {) outer loop iterations with 8 = O()) and O t
We do not give a discrete-partice analysis of MFL-ABR and instead remark that discretization of the fixed-drift inner loop trivial while Theorem 4.1 already covers the outer-loop error due to finite 7 and nonzero B. The remaining element is particle discretization analysis of the outer loop momentum sampling which we feel strays from the scope of this work.
APPLICATIONS TO ZERO-SUM MARKOV GAMES
5.1 BILINEAR PROBLEMS
We briefly discuss the case when C is bilinear, that is L(p,v) fʃ Q(r, ()d(dr))(dd)) for C reward Q: : X'x x + IR. Assumption 2 easily verified under the conditions | |V Q₂ and V.Q is Li,Lipschitz in each coordinate i = 1,..., ... by taking M₁. Q.. K,, L,p = L. while Assumption holds if Q is uniformly bounded. The averaged gradient in (4) is then equal to
5o' B. V.
8C dy (ps, (X,) ds XV,U((X,) Sy V.Q(X,, XV AVU
7

---

Published as a conference paper at ICLR 2024
the drift only depends the history through the average distributions fi, Pr. Therefore, instead of storing and iterating over all previous states which could be computationally prohibitive, we only require the rolling averages to be stored and updated alongside the primary dynamics. In the discrete case, this means that store the length N arrays 2, T alongside Li. Th and perform
X + X Em= V Y") X + 22Ang
+ y N E V Y
, 2xng
We then discard from 2k+1, 21 respectively. After K steps, the arrays L y are returned.
partieles from L Ty and replace with random samples drawn
Thus, both algorithms only require 4 arrays to be stored and updated (the inner and outer states for MFL-ABR), incurring no significant computational cost compared to MFL.DA (2 arrays).
5.2 ZERO-SUM MARKOV GAMES
In this section outline application policy optimization in Markov games. We consider the two-player zero-sum discounted Markov game defined by the tuple 2 = (S, N, r,r,,) with continuous action spaces X' = _dx y = R finite state space S, reward : S x X' x y + R, transition kernel P S x X' y - PS)) and discount factor y [0. 1). The strategies of the min and max players are represented by f = mss)= = ()((s)): S + (2() and v S - P2()).
The regularized value and Q-functions are defined for all Sas
(s) Σ rt (((S).22, Ue) log
Dc
[ pm
Alog
-(Ur(se) p" (y(e)
80
2tth (s, vls) rs,, x. T.E.
(s'),,
where the expectation taken all trajectories So, To. yo, 81, generated by Th p(-(sk),, The
9k v(([sa) and Sk+1 ~ P(-|sk, Tk. yk). Our goal is to find the MNE which solves the distri- butional minimax problem min PPs:SSPPssA (x)) maxy:s-Ppl
VitP(s) (s) for all states simultancously; detailed introduction to the topic can be found in e.g. Sutton & Barto (2018); Cen et al. (2023). For zero-sum Markov games, the MNE is also called the regularized Markov perfect equilibrium.
To this end, we propose the following two-step iterative scheme. For simplicity, we only consider the continuous-time MFLD and assume full knowledge of game quantities as well as the existence and uniqueness of the MNE (n²", v²) which is known for finite Markov games (Shapley, 1953).
Step (Minimax dynamics). Given ((a,, run MFL-AG or MFL-ABR for each state E S for sufficient time to obtain an <n-NNE (11(0) (s), (s)) for the regularized minimax problem
(x M; ((hh)( (s)) = [fxxxx y (1) (z. (ls))(d)))u(d)) + A (l.())))** AKT((vlle").
Step 2 (Approximate value iteration). For each 8, set (s) Cx(1() 2 (k) (+): and update the Q-function by letting ((++1) = (s) satisfying
[Q(z, vls) r(s, r. y) P( (V(+) | S
where EQ > quantifies a model error. In practice, ((++1) can be obtained by any offline RL algorithm with function approximation, e.g. deep neural network, as long the sup norm of Bellman error to the update is bounded, Moreover, we assume the gradients V.Q. V are bounded and Lipschitz and can be queried freely.
With this scheme, we are guaranteed convergence to the MNE, The proof is identical to the discrete strategy case (Cen et al., 2021, Theorem 3) and is included in Appendix A.3 for completeness. Proposition 5.1. The above scheme linearly converges to the optimal value function as
[](k) - Vo S <1 - -V> +
EC + +
1 1-7
This proposition shows that our two-step algorithm finds the Markov perfect equilibrium at linear rate of convergence up to a sum of the optimization error for learning the MNE of the inner problem, and the Bellman error for estimating the Q-functions.
8

---

Published as a conference paper at ICLR 2024
(a) MFL.AG min
MFL-AG max
(d) W1 convergence
0.2
0.06
MFL-AG
0.2
MFL-BR
MFLDA
0.04
0.0
0.0
MFLABRR
MFL-ABR
0.3
0.02
0.1
0.1
(e) 3-point
0.0
0.0
(c) MFL-DA min
MFL-DA max
0.2
0.2
-10
400
600
800
1000
Figure 1: Density evolution of (a) MFL-AG, (b) MFL-ABR, and (c) MFL-DA every 100 epochs.
(d) Convergence speed measured in Wi distance. (e) Optimality comparison via 3-point NI error.
NUMERICAL EXPERIMENTS
We test our proposed algorithms and compare against ordinary descent ascent dynamics in simu- lated setting. We consider dxx = dy = and optimize the bilinear objective
C(p, v) fI (z, (dddd)))ddy),
Q(a,y) (1 e c=(x-0)²
The sigmoid nonlinearity introduces nontrivial interactions between the min and max policies. We also take regularizers /² p" = (0,0 1) and À = 0.01. Both MFL-AG with r == 1 and MFL.DA run with 1,000 particles for 1,000 epochs with learning rate r 0.3. MFL-ABR is run with 1,000 particles for 50 outer loop iterations with 20 inner iterations per loop and = 0.3, 8 0.15. We implement the rolling average update for MFL-AG in Section 5.1 and 'warm start' scheme for MFL-ABR where the inner loop is not re-initialized for stability. We report the results in Figure 1.
Figure ((a)-(c) show kernel density plots of the evolving min and max policies p.e. V9g for each algorithm per every 100 epochs. MFL.AG and MFL-ABR converge to similar solutions while MFL.- DA converges different distribution much more rapidly. Figure ((d) plots convergence speed by computing the sum of the empirical Wasserstein distances W1 (1 ( W1 W1(v, V3h.1).
To compare the optimality of the outputs (2', (i 0, 1) of the three algorithms, we use the 3-point NI error NI' := max, Cx(Mer p)ar)) miny (x 1) which measures relative optimality analogous to a
payoff matrix. The values are reported in Figure I(c). While the MFL-DA output is initially the desirable strategy due to its rapid convergence, MFL-AG gradually optimizes and soon dominates MFL-DA with zero error, which later followed by MFL-ABR. We therefore conclude MFL-AG and MFL-ABR can substantially outperform ordinary descent ascent despite the slower convergence rates.
7 CONCLUSION
In this paper, we developed the first symmetric mean-field Langevin dynamics for entropy- regularized minimax problems with global convergence guarantees. We proposed the songle-loop MFL-AG algorithm and proved average-iterate convergence the MNE. We also established new uniform-in -inoom--i-ttme analysis of propagation of chaos that accounts for dependence history using novel perturbative techniques. Furthermore, we proposed the double-loop MFL-ABR algorithm and proved discretied linear convergence of the outer loop.
Our work represents early steps towards an understanding of mean-fiell dynamics for multiple learn- ing agents and opens up further avenues of investigation. Some interesting directions developing a single-loop symmetric algorithm with last-iterate convergence, studying conconvex-nonconeen parametrizations applications multi-agent reinforcement learning.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
JK was partially supported by JST CREST (JPMICC2015) and Toshiba Corporation. KO was par- tially supported by JST ACT-X (IPMIAX23C4), TS was partially supported by JSPS KAKENHI (20H00576) and JST CREST (JPMJCR2115).
REFERENCES
M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In Proceed- ings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-223, 2017.
D. Bakry and M. Emery. Diffusions hypercontractives. Séminaire de probabilités de Strasbourg, 19:177-206, 1985.
J.-B. Bardet, N. Gozlan, F. Malrieu, and P.-A. Zitt. Functional inequalities for Gaussian convolutions of compactly supported measures: explicit bounds and dimension dependence. Bernoulli, 24(1): 333-353, 2018.
S. Bobkov and M. Ledoux. One-dimensional empirical measures, order statistics, and Kantorovich transport distances. Memoirs of the American Mathematical Society, 261, 2016.
G. Brown. Iterative solution of games fictitious play. Activity Analysis of Production and Allo- cation, 120:374-376, 1951.
P. Cattiaux and A. Guillin. Functional inequalities for perturbed measures with applications to log- concave measures and to some Bayesian problems. Bernoulli, 28(4):2294-232) 2022.
S. Cen, Y. Wei, and Y. Chi. Fast policy extragradient methods for competitive games with entropy regularization. In 35th Conference on Neural Information Processing Systems, 2021.
S. Cen, Y. Chi, S. Du, and L. Xiao. Faster last-iterate convergence of policy optimization in zero- sum Markov games. In The Eleventh International Conference on Learning Representations, 2023.
F. Chen, Z. Ren, and S. Wang. Uniform-in-time propagation of chaos for mean field Langevin dynamics. arXiv preprint arXiv:22112.33550v2, 2022.
F. Chen, Z. Ren, and S. Wang. Entropic fictitious play for mean field optimization problem. Journal of Machine Learning Research, 24:1-36 2023.
L. Chizat. Mean-Field Langevin dynamics: exponential convergence and annealing. Transactions on Machine Learning Research, 2022.
L. Chizat and Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. In 32nd International Conference on Neural Information Processing Systems, pp. 3040-3050, 2018.
G. Conforti, A. Kazeykina, and Z. Ren. Game random environment, mean-field Langevin system and neural networks. Math. Oper. Res., 48:78-99, 2020.
C. Daskalakis and I. Panageas. Last-iterate convergence: zero-sum games and constrained min-max optimization. In Innovations Theoretical Computer Science, 2019.
V. De Bortoli, A. Durmus, X. Fontaine, and U. Simsekli. Quantitative propagation of chaos for SGD in wide neural networks. In 34th Conference on Neural Information Processing Systems, 2020.
R. L. Dobrushin. Prescribing a system of random variables by conditional distributions. Theory of Probability and Its Applications, 15:458-488 1970.
C. Domingo-Enrichh S. Jelassi, A. Mensch, G. Rotskoff, and J. Bruma. A mean mean--ield analysis two- player zero-sum games. In 34th Conference Neural Information Processing Systems, 2020.
10

---

Published as a conference paper at ICLR 2024
N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162:707-738, 2015.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial networks. Communications of the ACM, 63(11):139-144 oct 2020.
Z. Guo, Z. Wu, Y. Yan, X. Wang, and T. Yang. Revisiting SGD with increasingly weighted averag- ing: optimization and generalization perspectives. arXiv preprint arXiv:2003.04339 2020.
Hiriart-Urrut Urruty and C. Lemaréchal. Fundamentals of convex analysis. Grundlehren Text Editions. Springer, 2004.
R. Holley and D. W. Stroock. Logarithmic Sobolev inequalities and stochastic Ising models. Journal of Statistical Physics, 46: 159-1194, 1987.
Y.-P. Hsieh, C. Liu, and V. Cevher. Finding mixed Nash qquilibria of generative adversarial net- works. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2810-2819, 2019.
K. Hu, Z. Ren, D. Šiška, and L. Szpruch. Mean-field Langevin dynamics and energy landscape of neural networks. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 57(4):2043- 2065, 2021.
N. Lanzetti, S. Bolognani, and F. Dörfler. First-order conditions for optimization in the Wasserstein space. arXiv preprint arXiv:2209. 12197, 2022.
R.-A. Lascu, M. B. Majka, and L. Szpruch. Entropic mean-field min-max problems via best response and Fisher-Rao flows. arXiv preprint vrXiv:2306.03033 2023.
M. Ledoux. Concentration of measure and logarithmic Sobolev inequalities. Séminaire de Proba- bilités XXXIII, 33:120-216, 1999.
Y. Lu. Two-scale gradient descent ascent dynamics finds mixed Nash equilibria of continuous games: A mean-field perspective. In Proceedings of the 40th International Conference on Ma- chine Learning. PMLR, 2022.
C. Ma and L. Ying. Provably convergent quasistatic dynamics for mean-field two-player zero-sum games. In International Conference on Learning Representations, 2021.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resis- tant to adversarial attacks. In The Sixth International Conference on Learning Representations, 2018.
R. D. McKelvey and T. R. Palfrey, Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6-38, 1995.
Mei, A. Montanari, and P.-M. Nguyen. mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(3))E7665-7777) 2018.
Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programming, 120:221-259, 2009.
H. Nikaidō and K. Isoda. Note on non-cooperative game. Pucific Journal of Mathematics, 5:807- 815, 1955.
A. Nitanda, D. Wu, and T. Suzuki. Convex analysis of the mean field Langevin dynamics. In 25th International Conference on Artificial Intelligence and Statistics. PMLR, 2022a.
A. Nitanda, D. Wu, and Suzuki. Particle dual averaging: optimization mean field neural network with global convergence rate analysis. Journal of Statistical Mechanics: Theory and Experiment, 2022(1 11):: 14010, 2022b.
Otto and C. Villani. Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Fanctional Analysis, 173(2)3361400) 2000.
11

---

Published as a conference paper at ICLR 2024
L. S. Shapley. Stochastic games. Proceedings of the National Academy of Sciences, (9(1))1099- 1100, 1953.
A. Sinha, H. Namkoong, and J. C. Duchi. Certifying some distributional robustness with principled adversarial training. In The Sixth International Conference on Learning Representations, 2018.
Sokota, D'Orazio, J. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In The Eleventh International Conference on Learning Representations, 2023.
R. S. Sutton and A. Barto. Reinforcement learning: An introduction. MIT Press, 2018.
T. Suzuki, D. Wu, and A. Nitanda. Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction. arXiv preprint arXiv:2306.0722. 072211 2023.
A.-S Sznitman. Topics in propagation of chaos. École d' d'Éré de Probabilités de Saint-Flour XIX- 1989, 1464:165-251, 1991.
W. Tao, W. Li, Z. Pan, and Q Tao. Gradient descent averaging and primal-dual averaging for strongly convex optimization. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021.
C. Villani. Optimal transport: old and new. Grundlehren der mathematischen Wissenschaften. Springer Berlin, 2009, Chapter 6.
C. Wei, C. Lee, Zhang, and Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite- infinite-horizon competitive Markov games. In 34th Annual Conference on Learning Theory, Proceedings of Machine Learning Research, volume 134, pp. 1-41, 2021.
R. Wong. Asymptotic Approximations of Integrals. Academic Press, 1989.
L. Xiao. Dual averaging method for regularized stochastic learning and online optimization. In Advances in Neural Information Processing Systems, 2009.
Zeng, T. T. Doan, and J. Romberg. Regularized gradient descent ascent for two-player zero-sum Markov games. In 36th Conference on Neural Information Processing Systems, 2022.
12

---

Published as a conference paper at ICLR 2024
TABLE OF CONTENTS
Introduction
1.1 Summary of Contributions
2
Problem Setting and Assumptions
3
Mean-field Langevin Averaged Gradient
3.1
Proposed Method
3.2
Continuous-Time Convergence
3.3
Time and Space Discretization
4
Mcan-field Langevin Anchored Best Response
4.1
Proposed Method
4.2
Continuous- Convergence
5
Applications to Zero-Sum Markov Games
5.1
Bilinear Problems
5.2
Zero-Sum Markov Games
6
Numerical Experiments
7
Conclusion
A Preliminaries
14
A.1 Optimal Transport...
14
A.2 Mixed Nash Equilibrium
15
A.3 Proof of Proposition 5.1
16
Convergence Analysis MFL-AG
16
B.1 Proof of Proposition 3.1
16
B.2 Proof of Proposition 3.3.
18
B.3 Proof of Theorem 3.4
19
C Time and Space Discretization
22
C.I Gradient Stopped Process
22
C.2 Proximal Pushforward Bounds
25
C.3 Proof of Proposition 3.6
28
C,4 Properties of Conjugate Functionals
31
C.5 Proof of Theorem 3.7
35
C66 Expected Wasserstein Distance
37
Convergence Analysis of MFL-ABR
40
D.I Inner Loop Convergence
40
D.2 Proof of Theorem 4.1
13

---

Published as a conference paper at ICLR 2024
Algorithm 2 Mean-field Langevin Anchored Best Response
Require: temperature A, outer loop iteration K, inner loop iteration L, learning rate 7, number of particles N, exponent
Initialization: Ly pt, 3
p
for k 0, 0.... K - do
Sample 20 p²¹ 36 p"
for L = 0,... ... L do
For all particles
1, N sample Sh (N 5/ NO lay) and update
41 - X 1/ x ac (122, Ug (x()) - Xn)VaU((X()) 2 Ki.
&c f-1 Y v y (1 MW, (V( XV 2
end for
Discard [ particles from 2x, B/ and replace with random samples from 2i,, Vy, resp. end for return Kx. K
APPENDIX
A PRELIMINARIES
A.1 OPTIMAL TRANSPORT
We begin by introducing basic concepts and inequalities from optimal transport theory that will be useful in analyzing the behavior of Langevin dynamics.
Definition A.1 (p- Wasserssenn metric). For p [1), (RR)) be the space of probability measures on Rd with finite pth moment. The p- Wassersteiin distance between Jr, E (TR")) is defined as
[ ||+ ||-- yll dr(x, $
Wpln, v)
inf (neinfe
where H(,, v)) denotes the set of joint distributions on IR x Rd with marginal laws μ and the first and second factors, respectively. By Kantorovich Sentorovich-Rubinstein duality, the metric Wi can also be written
[ du J Sd.
Wi(u,
sup I1 S1
Definition A.2 (Log-Sobolev inequality). A probability measure (R is said to satisfy the logarithmic Sobolev inequality (LSI) with constant a >> 0 if for any smooth function f : IRd - R,
Ent, = E. log | E. [o Ex
E [[VS]))
a
For any measure μ (IEd) absolutely continuous with respect to v, the LSI implies that KL divergence is upper bounded by the relative Fisher information,
du
KT(NNPP) < F,, 20:
V log
dv
Proposition A.3 (Bakry & Émery, 1985). I IR I. is a function such that 2 f ' ala the probability density p & exp(-f) satisfies the LSI with constant a.
Proposition A.4 (Holley & Strooek, 1987). Let p be density I satisfying the LSI with constant a. For bounded function B IR R. the perturbed distribution
dz(x)dx- exp(B(x))p(z)) dr Exlexp(B(r))
also satisfies the LSI with constant a/ 1B11s)
14

---

Published as a conference paper at ICLR 2024
Definition A.5 (Poincaré and Talagrand's inequalities). A probability measure E P2((R") (R")) is said satisfy the Poincaré inequality with constant 0 if for any smooth function f R RR
Var. = = - 1 E. ||V /
Moreover, // is said to satisfy Talagrand's s inequality with constant a >> 0 if for any measure l (2(")) absolutely continuous with respect to v, the 2-Wasserstein distance is upper bounded as
a W3 (1, v) & KL(AIle).
2
y satisfies the LSI with constant a, then it satisfies the Poincaré inequality with the same constant. We also have the following implication.
Theorem A.6 (Otto & Villani, 2000). If probability measure v E P22(R)) satisfies the LSI with constant a, then it satisfies Talagrand's 's inequality with the same constant.
Proof of Proposition 3.2. We take the stronger of the two bounds in Lemma 2.1 of Bardet et al. (2018) and Theorem 2.7 of Cattiaux & Guillin (2022); the latter removes the exponential dependency on dæ in exchange for more complicated polynomial terms. See Lemma 6 of Suzuki et al. (2023) for more details.
A.2 MIXED NASI EQUILIBRIUM
Definition A.7 (functional derivative). Let F be functional on P2(IR). The functional derivative 8p f E P2((R)) is defined as functional P2(TR)) x Rdd - R satisfying for all P2(RR),
de F(u + f c(v-~())) w))
d
=== J
5F on
(w)
As the functional derivative is defined up to additive constants, we impose the additional condition fee &F (I)) du = 0. Furthermore, F is defined to be convex if its satisfies the convexity condition for all v E P2(R)):
S
8F (v) p)d)). 8μ
F(v) 2 F(N)
Finally, F defined to be concave if F' convex.
Proof of Proposition 2.1. Recall that the 2- 2-Wasserstein distance is finite and metrizes weak conver- gence on )2(TR))) (Villani, 2009, Theorem 6.9). Also, the divergence r KT((ulpp") is proper and lower semi-continuous with respect to the weak topology (Lanzetti et al., 2022). Furthermore, p satisfies Talagrand's 's inequality with constant тμ by Theorem A.6 so that the map + Cx(M, v/ is strongly convex. Hence the minimizer of μu ト> Lx (p,, v) is unique, and similarly the maximizer of ~ (p,, v) is unique. Existence of the MNE is now guaranteed by Theorem 3.6 in Conforti et al. (2020) by verifying Assumption 2.1 and conditions (i)-(i
For uniqueness, suppose to the contrary that (μ² v²), (f²,"") optimality conditions yield the chain of strict inequalities
,D") are two distinct solutions of (1). The
Cx(x", v²) > Ex(e", (")""""" Cx ,,)) Cx("", v²) > Ex(x", ,v",,
contradiction. Finally, the first-order conditions follow from Corollary 3.3 in Conforti et al. (2020), adjusting the base measures to be different for p.,
Proof of Lemma 3.5. By convex-concavity of C and the first-order condition (3),
NT v) Ex(uxv") Lx(1",P)
SL
(n', ("",v")(H (p=))(-nr' ---11110 (dx))x)))))))))))))))))))))))()) + AKT(U()P"" - AKT(C")le")
I 5y
8L
,,")(u (p²,"")( (v- -
(0)(u=""((pp (dy) - AKT((W"1le>) + AKT((u100))
15

---

Published as a conference paper at ICLR 2024
1 A log 1C Da (m- + AKL(all0*) "AKK(""""""_KK(("l"1""""""""
I Alog P (v- 1² (dy) - AKI (100) + +AKLVVlPP") AKL(u))n") + AKL(ullu")
A.3 PROOF OF PROPOSITION 5.1
We use the bound| (1, fx(e", S NI(,, v) which can be shown by the following string of inequalities,
Cx(M,v) Lx(m", 11") max Cx 1/) L2(x", 12) S max (x(, minn Cx (p',,,)) v): (X(1,D) - Cx(M", 2 min Cx(m', v) - Lx(1, 2 min Lx(x', 1)) max (1,,,
Denoting the ideal minimax update in Step as
(()+ min max Lx(H, v: (8)), (EPs(
this implies
[V(+t (s) (()+)((s) & NI(H (s), (s) S cc.
Now denote the ideal value iteration in Step 2 as
(s) r(s, x, y) + P(h.ay ((())
and note that the optimal value and Q-funciooss V = Vittie" e² , Q²- = 0x .0" satisfy the Bellman equation
(T,,,((s) =
r(s, r + P(ssa)))) (s)))
Hence we bound
[[(++]] - 1o S S<c [((-)) V
S cc + sup
Lx(u, v; (00 (8)) - (x(m,,;((()))
n.ns
$ E2 (²)() 1=
$ 37 + 1Q (k) - 1()) + +1@((0) Q'11
S cc + cq + +)][((()_ Vl
Therefore by Gronwall's lemma we conclude that
||((] - 1o S -011
+ "c +c0
1 1-y
B CONVERGENCE ANALYSIS OF MFL-AG
B. PROOF OF PROPOSITION 3.1
Some definitions are in order. Denote by CX,T C((0, X)) the space of continuous sample paths on X and by M((x,T) the space of probability measures Cx We define two versions of the lifted I-Wasserstein distance on ((xx).r as
inf / 7
sup [[x(t) w d(w,,)) A1,
tST
W1r(Hpp) 100=inn inf
sup l[w(t) - ww(()) A 1dy(w,w") t<T
16

---

Published as a conference paper at ICLR 2024
where the infimum runs over all couplings Y E Mc(xx, Cx.r) with marginal laws μ4, jl. The inner truncated metric W1, is complete, nondecreasing in T and metrizes the weak topology on (( (Dobrushin, 1970); the outer truncation W1,7 serves to upper bound Wi,r. We repeat the construction for y and extend Wi,r, Wi, to the product space M(Cx,T) x xM(Cy,r) as Wi,r((u, (), v/)) Wi,r(u, (') Wi, etc. Now define : M((x,,T x MM(,rr))) + M(Cx..) x xM()).) as the map which associates to the pair (1,1) the laws of the stochastic processes (Xt) (Vi)eST,
8c (1r, v+) dr +V.UU" + V2AW!"
X, Xo-
B. V
B, Jo
Y = Yo + [ B.
dc
8. 9 dv
(pr,
ds + V2XW?
for 0 S S T, where μt; Ut denote the marginal distributions of μ, V at time l and in particular Mo. PD are the prescribed initial distributions. A solution to (4) then corresponds precisely to fixed point of Φ
Lemma B.1. There exists a constant Cr so that for any 0 S
W v), 1(1, v1)) s OT 1/" W..((u,,)) v), v'),
Proof. First note that for any S <oSIST,
WH, p() 2 inf / - (SS]ld((()) A12 Wi(H,,1) A 1.
Let (X))SST. (X)) denote the synchronous processes
1
8L V. (1/, (x.) dr AV,U + V2XW!"
X = No
B, Ju 5p
Y Yo (''
SL (/
B.V
AV, ds V2AW?
B,
dv
corresponding to another pair of distributions (K/,1'). Then by Assumption 2,
sup S5t
|X X
Var 8C (pr, Dr (X.)) - Vx (1,, ())((3) +AIIV=U"(X.) - (xU(())) ds
8C
sup rSs
8pp
54
/ (K₃ + >RRp) ||x, X11l + sup (Wi Wi 1/,)) ^ 2M, ds
rss
$ (Kp + ARR) /' |X, - X:Il ds (L,, v2M,)
/ sup K() A (,(,,,1/) A 1s. rse
|X,-
Thus by Gronwall's lemma we obtain
sup |X, - X < (L,, v 2MM De (R L sup W Wi( 14) A 1+ Wi(,,, A lss. rse Then defining the constant Cr = (Ln v 2M, 2e (K, + (L, V (Ko by taking the joint distribution coupling of (Xt)ssT and (X)sST we have
WI.( 2() //)) < Cr l' sup Wi(H:: A1 M11tW((,,,) 1/) A Adss 55x
which proves the lemma.
17

---

Published as a conference paper at ICLR 2024
We now the contraction property prove Proposition 3.1. Starting at any (p, and recursively applying Lemma B.I, we have
//" 10"
WT, Wi.7((t+1 x² (U, S C2
Wi u) (1, dla d.2 dli
OhT
W (1) (U,2)).
k!
so that W1,7 ( (p, 26 (p, aas Since W1,7 upper bounds W1,7 the sequence (0* 2)) is Cauchy and therefore converges fixed point of & due to the completeness of M((x.) x M(Cy.T with respect to Wi,r. Similarly, recursively applying Lemma B.1 to two fixed points V), (H', v") yields
C+T k!
W ((, (ul w/)) S (ir(((n,))
W Verr((u, (),, +0
hence the fixed point is unique. Finally, truncating the obtained flows (JU))sT, (U))eTT) time T" < T must again yield the fixed point in M(Cx,7)) x M((y,T)) so that we may consistently extend the flows to all time E [0, oo).
B.2 PROOF OF PROPOSITION 3.3
Write the normalization factor for The as
Z =ー= exp (-x+.
I
8C (Ms us) vs) (dx)..
Ba 5y
AB,
We first compute the time derivative of the proximal distribution,
3e 8C (pr, vb)
3
8C
a, log -- log Z!"²
8. (Mar Us) ds
XB, 8p
AB
= 1
3r 8L
3r.
8C
(14, ui)
3. Jn
(Ms, Uz) d8 (d(
XB; 5jz
XB3
Bg S.C.
Be
8C
(Jurs Vv)
+
B. Ōn
(War Ve ds.
XB, ōfz
XB3
Roughly speaking, the proximal evolution speed is O(3,/B:) which converges to zero as new infor- mation is continually downscaled. However, the maximum total displacement Olog B:) + co, ensuring that the algorithm does not prematurely stop before reaching equilibrium.
The time derivative the KL gap can then be controlled by translating back into KL distance as
O (L (.)) /
(log Mt p,
Oepe(dx)) f (Ö, log (.)) pe(dx)
ー /
He
2 (c(x))
Vx log
x
T4e
Be
/
5L
{ Bo Eu
8C (Me: vs) ds (He - (dxr
+ AB x
B,
2M,3e
< 2ad KL (.))
W Wi(pe:
XB,
by Proposition 3.2. The Wasserstein term is further bounded via Talagrand's inequality as
2 KL(U,, Pi))
Wi(pe, W2(u,, R.)
Hence
MrB: 2 AB, V ap
O KL(U4) -0 KL 1.) +
18

---

Published as a conference paper at ICLR 2024
and using integrating factor, we conclude (starting from arbitrary small but positive time tu to avoid potential singularities at = 0)
M
2 au 1o B.
3e
exp(axAt) /LL p.) -
exp(an)s) ds exp(a,,to) KL(H (ro))
In particular, for the weight scheme 3r = t" with >> -1, by employing the asymptotic expansion of the exponential integral (Wong, 1989, Section 1.4)
Ei(z) =
exp(t) dt exp(*) 20 t
Σ z
+
+0(12)((att))
2
we conclude that
2
(r 1++1MM, A
2
KL( (()) S
Ei Ei(azat) + const.
2(r 1)
02A4 +0(t)).
We also show boundedness result which guarantees that the flow is in sense well-behaved. Lemma B.2. The MFL-AG flow (pe, satisfies for all t 2 0,
M and KL(uelle") S KL(volD")) V
M3
KL(pelle") < (L(uolle")) V
2r
2r
Proof. The density pr satisfies the I.SI with constant ru by Proposition A.3 so that we may derive
O, (KT((ulll
1
log Me ph
= / V
14 pu
Vx log Me (e(xx) The
log
x
> J 1 log
14
(cdx) //- V. log
Me pu
V
log
ui (dxx)
pa
pu
À /
PI p
2
Me(dr) A
/ V vog
phe
12
< 2
V log
log
pu pe(dx)
M22
S - KL 1
2X
The assertion is then proved by Gronwall's inequality.
B.3 PROOF OF THEOREM 3.4
We first introduce two conjugate-tyre type auxiliary functionals and state some properties.
Lemma B.3. Given Lipschitz functions Sy X TR So y measures μ E (2)))), v P2((2) define the time dene-dependent functional
- RR, for the pair of probability
(5) st (- pd'))dx)x++ + / -"
(BL(KL())))") +KL(vIlp")),
Then the maximum
J.CS
max max Je MEPA(Z))EP.())
exists for all t > and is uniquely attained by the pair of probability distributions defined as (C(CP) exp(_(AB,)) UH) and v.(5") exp((XB:) -U²).
19

---

Published as a conference paper at ICLR 2024
Proof. Since [p, vls", (*) decomposes into terms depending only μ and v. respectively, the proof similar to that of Proposition 2.1. That is, + (L(pllp") is lower comi-continuuss and strongly convex with respect the 2- 2-Wasserstein metric by Talagrand's inequality for p so that combined with any linear functional,
arg max migmax (P - XB, KI(H)IA") MEP2(X)
has a unique maximizer (5() which moreover is given by the stated first-order condition.
The following properties are direct extensions of standard conjugacy results in convex analysis, see e.g. Hiriart-Urruty & Lemaréchal (2004), Section
Lemma B.4. The functional J&(S",5) satisfies the following properties.
(i) Je is nonnegative and convex in both arguments.
(i) Je admits functional derivatives any (S",5") which are given as
8J+
oJ.
--((==) + p²,
(5 (5) Di((") - p²:
8C"
8ç
(ii) The derivative with respect to time is bounded as
a,J.(S" S - + +KTTD[((")ll"")
Proof. (i) Note that J, 2 0 by taking μ = p", = p², and Je is convex in both C*, S" as is
pointwise maximum of affine functionals.
(ii Due the explicit dependency of (,,(5)) 5" Je(s" P,C admits a functional derivative with respect to 5" and
8J. (()))))= - + pM ( log 8çu
(5*
m((H)) p" 6çn pr (d(s)) (,,( + pM
(ii) The time derivative of Je exists due to the differentiability of (Bi)ezo. For any t' > t.
Je-(S", = Je (C""
= Js" Der A(Br- - (Z) (<L(r(<")I"""))
I Ji(C",5") -BC: (I)L (S")lle") + (("))l)))))
by the maximality of Jr, thus taking the limit t' $ yields the stated inequality.
We proceed the proof of Theorem 3.4. Denote the unnormalized aggregate derivatives
['
B. SC (ps. v.) v.) ds,
8L [ Bg 8v (Ma, ps) ds
8
of
8p
which are Lipschitz due to Assumption 2. Then by Lemma B.4
d
Je(8H,
87)
di
= =ʃo 0,8t 8CH
8Je
85, 8 8dz) + / 0.8% (8+ (dy(d) (8.J)) σG
/ 8L
(He, (,,) (²) 3, /
8L
< Br
oy (mr uz (D, (d))
x op
(BL(KL(( (6, (L.
20

---

Published as a conference paper at ICLR 2024
The NI error of the averaged distributions can now be bounded,
NT(
max (x(Re, (2(,
1
S Be(Cx(Hsi C2(H, vz)) ds
S max
vz)(dy) - -. X(KI(MallP")) - -IT(UIA") KI.(Ul)0))) + (I(Us)lp*))) ds
1
( B. (1, δu (e -
S max n.6 B,
5n (Mss (o) -ua))
(L, 8.(1 (8601
(((1--")((a)) -dn(dy - -J 61 - p²) - (KL((()))) (I(vVlp0))
= max
B. N.N
-0
8L Vo) -v) - 1x (Hai us)(dx)
8c ōu
3g
B. Jo
dv
X(KL(pallP)) + (L(valle")) ds,
where have used the convex-concavity of LA and L in succession. By extracting the terms corresponding to the auxiliary functional Jr. we are able to apply Lemma B.4(iii) and obtain that
J. 87) + [[B (J B.
1
(J (us, (un, Us) - uss) [ 8c (us, us) - (d)
SC 5z
B.
+ A(KL(Hallo") + (L(vallo")) ds
1
<
-A,,(KI(T,(0))111 (KL(
B.
(-))(((((p))))) + (dxx)) + 8, / 8L
+
3,
(1is
dy (Ms, (.),,(1))))))) (dy) ds
8p
x
1-¹ 3g
8L
(Me v.) vo)(dy) J,, / -
5L
(o)(
dv
84
+ ((KKT(Palle") (TT(vsl)0))) ds
3. (X(LL - KI(TxllleM) + KL(usllp") - KT(Dxlle"))
B.
/
SC
(Me, - (.)(d))) - / du U.), - E. (dy ds
8C
+
8u
x
1
/
84
log Be Be(ur (mo (dx)) X pr
/
log Me
ps(xx)
B.
The
Dg (Vz= - (.)(dy) + A / log -/2 1 (dy)
+
A
log
1.
JC
{
SL
+
(Ma, Wo)s (.)(dd))
(1s Uo (vs (d) ds
8p
dy
1
3.
8L
(He)
Br
8C
(pr, vr) dr) (mo - -A,(dr)))
B.
8q
B.
8L
1
f
3 51
5L
(u)) dr) - D.)((d))
(pms
B.
+ A
log Ms
(dxx /
log
Us
vs (dy)
ds.
p
D3
21

---

Published as a conference paper at ICLR 2024
By Proposition 3.3 and Talagrand's inequality, can therefore bound
NI(A,, D()
1
[
<
(.M. (12M,,W(HH.)) WH + W1 (.) + AKL( (1 A ds
B,
2
2
BN
May
(L(())77 + Myy ap
kI((usl ds
B1 Jo
Oy
A
[ B.(KL(uell + KL(Usl 1s
+
Be
M
M2
4()+1)
(
p. (1 O 1) ds.
a a²
X²B,
In partieular, for Br 1' with
obtain the convergence rate
M
M2
4(r + 1)²
Ni pc)
r\21 + O(1-2)
a
whose leading term is optimized when 1. For 3g
1, obtain the slightly slower rate
M
M2
4 Alogt O(
NI b1)
a
X
We remark that for decreasing 3r, the integral tends to converge so that the normalizing B," term dominates, leading to significantly slower convergence. For example, if Br t" for - r < 0 the rate is O(t-1-"); Be ~ t-1,, the rate is O log (11o
1
C TIME AND SPACE DISCRETIZATION
C.I GRADIENT STOPPED PROCESS
Denote 27 (X 3% =Y;)) and J.2. N 5x Σ Syg. That is, the subscript & denotes the number steps while superscript i denotes the ith particle. We also write (X, V ):kk = (Zix, F.x) for notational simplicity.
We analyze the following MFL-AG N V-particle update for all i 1, 1,..,, .N.
SC My (Xx) V /221Et
X -x
B
V
B
8p
j=1
r Y
7
V
SC U, Uay (YF) X + 2
Bs
pv
where eni E are i.i.d. standard Gaussian and the initial values 2i, 3 are sampled from initial distributions po P2(X), (x))), uo E P2())). We write the distory-dependent averaged drift function as
8L (mæ, v3y) (2,, U
6 (- )1.)
B
BB
8p
and similarly for by. The history-dependent N -aratiiel proximal distributions are defined on the configuration spaces N y as the product distributions
(2,) x NnN ( exp
exp
N
Σ
B
8C (Mz,, Ug, )u (dm)) (x)))))))))
XB
(( x 22N exp
N
3
8C (uzg va, u (dy)
XBR
Jy
y=
3=1
8v
22

---

Published as a conference paper at ICLR 2024
We substitute Bi = k- with E Rzo whenever necessary to simplify the calculations, although similar results may be derived for any well- bellvbeheeed sequence of weights.
The following lemma quantifies the sequential evolution of the averaged drift.
Lemma C.1. For any pair of integers ls > l we have [|6 ll 22 (1
Be BN
M
Proof. For any E X.
116% (x)
1
V x ōj
8L (uo
+
1 B₁
Σ
33 x
8L (1 25 May (ar)
Bb
Bk Be
Bi V.
SL
( Uag (z)
1
Σ
5L
Uu Vay, (2)
BrBr
By
j=1
j=t+1
Be
2
Mp.
B&
yielding the assertion.
The rradient-stopped process. For given integers k: >> l, consider the following synchronous modi- fication of the MFL-AG update with the drift stopped at time E,
x 3-1 X3 n 6b () + 2
-ー =1= + 1 b ()))))))(())) + 2
The initializations Hi, 3/ and the random vectors et .S 5x are be shared with the original process so that (. 3 1==--+11 (X. 1+t- We will study this process alongside the original in order to facilitate short-term perturbation analyses.
Lemma C.2. 1f S
"e the second moments of the particles Xj and Xi are uniformly bounded 4ARg
for all k 2 1 as
2 2/M M
1 EI E|| +
s",
5"
+ +nnMa + dx
Tu rnd2
Proof. From the update rule (7),
111
SC
[|
27/
X Bj
B
(1
Ugg ((x) (xx))(
ōp
j=1
1
SC
+1²
3,V
(1 Uay (Xx) AA (x
+ 22
Bk
x 8p
i=1
< [[]|| 11 + 27 M, E X ||| 2 1
+ 2 M + 2x R3 X |1 + 2Ardx
M2
S Awr,, |E[| X2
2x M + 2Xrdxx,
Tnd
where we have used X|| < T from induction. The same logic can be applied to E[|| 1P].
Ma 11|
and rj S Te.
The statement now follows
4xRg
Lemma C.3. If S TT.tAR, the Wasserstein error between the original and gradient-stopper process at time k > is bounded as
r 1
k- + //
23

---

Published as a conference paper at ICLR 2024
where
Mf + )1 + 2n -1)
(107)) = 2n + vu
2
Proof. Decomposing the difference at each step j > k- - as
- -X3+ =
X3
X3 -
(xg(())) - 6y (X3)) + (x)) b% (x))
we expand to obtain
1 x < {|x; -X312 + 2n( 2xx - -b) + 2nl1X3 - X331 - -16"" - -
+ 2172116 - (x))11 21/ |16 el
Bk-1
< |Xx x312 + 20(T x - x3112 + 4n
1
Myll - X311
Bj
(1- Br-
2
+ +217(LH - | - X3112 + 807
M2
B3
5(1 + 2L1+2nn)]11 x1112+ (A
+ 877² Mi;
(1-
BR-1
2
TUL
B3
Starting from X - -Xp-e= = 0 and iterating,
AnD,
k-1
BR 2
| -X12 x1 2
+ +
Σ
(1+2nInn)
1
Bj )
12 222. (8)
rnd
j=k-
Now noting that with 33 =²
Bk-L
Bj < (j (i-k+ E)j" = (r 11)
(1-b-²)
k
(r +
|
<
So 2"
k- 1
setting 0 = =(1+ 2 -1 we can explicitly compute
k-1
1-1
Σ
(j-k + 0)2 + - Σ j00
j=k-
j=1
0--
(- - 1)20e11 -11-81 + (262 - -26 - 11)00 - egt +3
(1 - 0)3
OC-I 2) s [1 - 0]3 (0 1).
0
20
(1 0)3
Plugging back into (8) gives
4M2
(r+ 1)²() + 27 (1 + 27L -
|| - X1IP= <
SnM13
Tud
41121 P
(k-l l 1)2
1 (1+ + 2n) 2 (1 + 11222 2T. -1
S
(1+1)
2m + rnd V
2
n
(k: 1)
uniformly for all i E [N]. Note that the (2L,) term is added to simplify later analyses and is generally vacuous. Finally, taking W.2 (1.24 . ( S || 11 yields the desired bound. O
The calculations for the two above two results are similar but the bounds are fundamentally different. In Lemma C.2 we rely on the long-distance dissipative nature of b% to prove a uniform-in-tine guarantee, while in Lemma C.3 we forego the contraction to isolate the 1 Bz factor and obtain tight short-term error bounds.
Be
The leave-one-out error of the modified process can also be characterized as follows. We remark that the arguments in Lemmas C.2 and C.4 are identical to that in Suzuki et al. (2023).
24

---

Published as a conference paper at ICLR 2024
Lemma C.4. Denote the set of N 1 particles (X..... 8i-1 -xx
x Fx
S 1x2y
Fe the W2 distance between | Hr and 1T at time k >> can be bounded on average
E
W2 W2
4s" 2 N(N - 1) jti
Ei
2 1
rea-
N
Proof. Similarly to Lemma C.2 but starting from time k E, can be shown that
E
(2 (2. (L) [ < | Vo", jE [N].
which will be useful in the sequel. Then taking the coupling Ejii N (x(,3()) +
1 II-11
for 1 T P gives
E (20,
W3 T4 -3.')
E 1 h9)-
1 N(N
Σ
X212
1)
jfi
2
Σ
2/ 11
2
< B 2 )i:k-
N(N - 1)
N
4s
Σ1x2 N
X 112
N
N(N
-
8#1
The same bound holds for the original process.
C.2 PROXIMAL PUSHFORWARD BOUNDS
For measure n (N) on x(N,, denote by the average the pushforward operators II along the projections 2 + X with the defining property
J (x))Il() = -fx- II' (2) /
1 Σ
(1x))
J N
for any integrable function f f:X. R. We immediately see that
B, SC (, 18,)
II M) = pd exp
XB
x
the stationary distribution of the continuous-time Itô diffusion dZ, (2,) dt 22ddW"" which entails the following uniform moment bound.
Lemma C.5. The unnormalized second moment J'x ||0|| I is bounded above for any integer l by qt == 2 2 + 2r, dx--
We also denote p = N Σ N
< oc.
Proof. We may compute for the initialization Zo 0.
d E1|1Z,111
2E 2E (Z,)) 2Adx
df
< 2MM ||
2r [E] + 2Xdx
M
< -B 21
Tu + 2Xdx,
which yields the bound in the infinite-time limit by Gronwall's lemma.
25

---

Published as a conference paper at ICLR 2024
In particular, IT P the approximate stationary distribution of each independent particle of the gradient stopped process after time k - and enjoys an exponential convergence guarantee up to an (()) discretization error term.
(N)
Proposition C.6. Assuming S of the gradient stopped process satisfies
Tu IART
the KL gap from i = Law(Xi D ( to 11 p
(M)
KL | (
(1+
3cxp( 1)andn))
(R* (x Ln),
2772 + AB,y)
where
1/2 RL )
2 r(L + +RR
R =
(nM + X211R2,5" + +ddx)
a+
ax12
are both of order (1)).
Hence, choosing
3
f= 00 =
log 2772 + XR,,
+1
(9)
andn
guarantees that
4 (SR [X
(2 |1
2*)
a'u
for any integer ls > l.
Proof. We emulate the one-step analysis in Nitanda et al. (2022a) whilst keeping the history (œ, 1i fixed; this dependence omitted here for notational clarity. For j 2 k - l, denote by
n the law of the process
dx! (X)) v2Xdw! 0.15
with XJ = Xj so that X d X1+ We overload notation and denote both conditional and joint distributions involving X by nt. The evolution of pt is governed by the conditional Fokker-Planck equation
a. (x -. -
+ AA
Integrating X3,
(x)((x))= =fx -V (ut(xt, X3) (6) (8)3
(dX3) + x
V. (ul(x!) (-Exzix²
6f (X)) AA log log
AV. (,)( log
(NJ (x!)
+ (ul(x)) (x(] - E Exxxx (x33))
Hence the proximal KI. gap from n to IT T satisfies
0, (L = /
log
(ax))
(N)
x
=-> V log
4
n((xxt)
7
- -11 x
log
14
vl(xxt
11 11
(N)
26

---

Published as a conference paper at ICLR 2024
S À 1 V. log
Mi
m((x))) (Ln + +AB,)²
1x] x3]121((xx3) axy)
II M
(N)
22
S a A- KT (T |T ( + (L + +AR,a²
66 (x))
V2NIE11 (3(ax;))
2x
(N) where et (0, Iax) and have used the LSI for II m- The second term is further bounded
as
6% (X}+ 2215" 19
[1022 11@ + 2xrdxx
Ex
I n E BxIIxIa
$ M 2X 2/ 11| + 2xndx
S 22 R2, (1x V 8h) + 22rdx
by the proof of Lemma C.4. Gronwall's 's lemma now leads to
KL (1)))) - (R* el + 2*) Se an (KL(Z)ILIAA)) (M) - (R (8"1|
on))
Thus, iterating the bound for k - 1 < < k gives
(L (
(N) S exp(- ( (e- an) KL e+1
R" X ell D".
where we have stopped at time Instead, the relative entropy after the first step can be directly bounded; since x! is a rescaled Brownian motion with constant drift, the first iteration of 8x;_, is distributed as
+ because the initial distribution مo 5x; is atomic.
- N(X + n bb (X lax).
The LSI then gives that
p E+1
KL
6+1
S
20
Bpi-et1
Vz log
II (N)
3
dx
M²
+
+
R2 (00-e111120000 11 11
20
2
X2
3
dx
M2
R2 (1IX V aat)
+
+
20
2
RR | 2"))
277² + XR )2
Hence arrive at the desired statement,
KL( ( (1+ 3exp(- 1)and1)) 2 + XR,))²
(A* (x*1IXX--el S*).
The subsequent lemmas provide control over the Wasserstein distance between pushforward disti- butions. In particular, Lemma C.8 is the discrete analogue of the O/3,/ B,) time derivative bound obtained the proof of Proposition 3.3.
Lemma C.7. For any two measures (())) E P2(x it holds that
(IP (N) ( (
VN (M ((N))
Proof. Recall the dual formulation of W2,
{ { /odp- [vdi d. b.b x R, 6(x) 2(v) 51 -11
W3 (p, pD) suup
$1=-112
0.
27

---

Published as a conference paper at ICLR 2024
Then for any pair of functions Φ, & such that Φ(x)
v1()) I || yll. the pullback functions
o 1p d on X² satisfy
II" TT (3))
Σ -
1 N
1 N X r-1
11 -
M (
Therefore.
Jx (())lly! - -sx (())ll((M0co))
= =ffr (p (N) (d.)) S II' I ((
1 & W2( (2(N))
N
which yields the assertion by taking the supremum all permissible Φ, Lemma C.8. The projected 2- Wasseesteei distance between (N),
L
p is bounded as
W2 Pk (N)
(N)
2M
a ABx
Proof. The proof is deferred Section C.4.
C.3 PROOF OF PROPOSITION 3.6
We take É = go Onn log 17 !) defined in (9) throughout the proof and only consider the case 2 28 Steps through 4.
Step I. We first look é steps back to the past and control the displacement of the proximal II p from the stationary state 11 p of the modified process via Lemma C.8, conditioning on the earlier history (2, V 1=k--
[ (1))),)966))13 11 p
B(x ) (
< E ( (i U F(H22, 2o, V - -I
+ Mμ Σ
E (0 an ,1 (N) 11 }
U F(H22, (ux -
+ 2M2 2 t-1
Bk_
< <B
1. Σ
and j=l B
It is simple to further verify that
2M 1-1 Bk-j
2M2 (r+ 1) <
and j=1
B₁-j and k-f+1
Step 2. Next, we look back to the future and convert the expectation with respect to μ.R, to the corresponding expectation for the modified process. The incurred error can be bounded by utilizing Lemmas C.2, C.3 and C.4 as
V F(uzz, voL I1 (N) (dr))
E E ( ())
11
E ( n [ Flu,, Mz (1
11 1l (N) (dar)
[ F(u22 Vay (uzi -H (dz))
(2, F, 1
28

---

Published as a conference paper at ICLR 2024
+ 1 (Fluz).Ve)) - F( "xx "xx) (155 - -1 (dxx)
S E (x 19 (
+ 1 N
N Σ
F(u - F(U F(H
"%%, ) Lip
Wxx0 17
(r + 1) M 10/2
k L ++1 1
+ k - ++1
(r + 1اار
(119 + 10²) (x -11--
(
Σ
N
|| x01 11 (N) (
1 (r + 1)
+ (r 1 k --1+1 (oa + ))²)
2
N
7
X 12 + 9r + 25th
k 1+1
N
Step 3. For the modified process, we apply a leave-one-out argument and consider the expectation with respect to each particle X2 which is independent of T. Wy when conditioned the stopped history (2, V >=kk
8. That is,
[ F (1z.
E ( )al((
1 N
R X ,0 D Us FLUE 2z)) mpp
E
N
N
1. 9 , E 3 U/x F(u Uos Mox; - 11 17
<
E T
Min-e
N
N
| F( M 1111 Wi Wi(0x; II p(
E T (2,7) hike
N
) U FIu (0xx
EE 5 ,,
11 )d)r)
N
Σ
E
(5--) (3. )1 x: 11 1
N
1 N
E 11 9 Mak- U/ F(ug,, (ak -
11 1 - (dxz)
N 1=1
Σ
E A 3 1
Wi(H ",..
) Wi(5x; p
N
M₁ N
N
Σ
Wi 11 (2)
Lu N
W3 " "> R B
W2( [33(xx.171+2 ))
N
2M, N
Σ
V /zz
(fa X 11 S*)
2L
29t
1
Σ
11l + N |
1
(1xi + +" + sh)
N
N
N(N 11 4+i
29

---

Published as a conference paper at ICLR 2024
by applying Lemma C.2, Lemma C.4 and Proposition C.6.
Step 4. Putting things together, we obtain the conditional bound
[ F( Vo, Mus. II - (dx)
E ((,,)) (. (i
2M (r -1)
0n1 - 6-e+1
(r + 1)
w + +r+ 1) (wyy + +w²))
(3 N
+
Σ
x x + + + 2g
k l ++1
k- ++1
2M
Og ( 24)
N
$ (1x2- Ei + NN (
2
2gh
+ q" + +S)
+ N(N 1)
jt
Recalling E|||XX || & x + sr from Lemma C.2, taking the expectation with respect to
the history (œ, 2 ",,))..e I finally gives
1/x
((dx)
B( 1m
$
r ++1
2M
(l
1) + Mnn Tup (10, + 1ot) (2p" + qt + 4
4-E+ E+1
and
N
+ 2M, (2,
8 x 2 2*))
O
i=1
N
N
2N - 3
# N
1
| 12
N- | + qthh + 35"
N
i=1
j=1
r +1
2M2
(e- 1) + MM + Lp (10 + wy² (2p" + qth + 4ot))
1+1
and
1
8n'p" + -"
24μ
+ 2M,
(3p" + 9rh + 65
ap
VN
< r+ -
C3
C2v +
k
VN
where the last bound holds if 28" To be explicit,
2M2 (E (E- 1) + M, + Lu (wy + ro?)) (2p" + q" + 4s")3)
C1(n) =
and
C2 2Mμ RRR + 2px)2p"
(I, + AR,)2 (RM, + X2RR,00" + xdxx)
an
ag1²
C3 = 2hp (3p" + 9t + 6s
The constants C2, C3 can be taken to be polynomial and independent of 17 by substituting the upper bound n = 2, 2R,, A TxRō in the expressions for R /T,, 2 /n, while fe = O(1 -1 loog n 1)
A.
However, (17) contains the dependency
-0 -0
L
3
ane
O(w²)) = 0 (x=(ex((LL))))
(12, + XR
30

---

Published as a conference paper at ICLR 2024
which is a consequence of uniformly bounding the perturbation from the gradient stopped process over a time period of L.
Step S. For lo 2f, proceeding similarly without converting to the modified process gives
v us - 1 ((2 vikk 1i Ux
M
W1(5x; 11
11009014
N
i=1
L
1 W3 52 . "z 1 [33 11 1 $
N
M
xi| |1 + 9" + s4)
N
+
24
N
2s
E X
1 + )
(E[I) + +""
N
N
N(N 1) K
1=1
9th 3r")
S MpVP" +
gms
VN
Ci(n)
C3
28
VN
where the final bound follows by noting Thalt
1. hence by expanding + 2x
"I,
M2
M2
(10/)² > 2L 2
(2 l + 207² L 1))
L
and so
(1 10 (2p" + q" 4sn 2M (p" 9tth + $")
Thus the bound holds for all integers k. We conclude the proof by taking the maximum with the corresponding quantities for v.
C.4 PROPERTIES OF CONJUGATE FUNCTIONALS
We proceed to develop the N N-particle lifted analogues J(M) (NN of the conjugate functionals in the proof of Theorem 3.4. In order to deal with time and particle discretization, we will need a more precise characterization of their perturbative properties. Many of the subsequent results do follow from standard methods and requires a careful synthesis of the discussion thus far.
Lemma C.9. Given Lipschitz functions Sa= X - IR, So :y + R and a pair of N-particle probability measures y((N E PP2(N vN) E (222N define the functional
J[M (M (NN
I XN / 5t - (dxr))))))))))))) 1Sx. (KLNN + KL(u(ND1lpBBN
ABR
N
Then the maximum
J M(NI)
(P WIN LINEPP PP(M)
exists for all k E N and is uniquely attained by the pair of distributions
(CP) x NNO exp (- (-XB-- / (d)))
N
( x NN exp
N
I (e
XBs
31

---

Published as a conference paper at ICLR 2024
Proof. The proof is similar to Lemma B.3; only check the first-order condition by setting k. du(N) (u (2)) -- 5th (ux (d)
--x
XBR N
1! DuBN (2)
log
const.
The N- N-particle proximal distributions (N)
j (5t), (N) (C"). despite being defined over the configu- (5"),
ration spaces X y.V also satisfy the log-Sobolev inequality with the same constant before due to the tensorization property of entropy.
Lemma C.10 (product log-Sobolev inequality). Suppose that /² /Bk. /BBx are Mps My- Lipschitz, respectively. Then p (C"), 2 (Ç") satisfy the LSI on XN y with the same con- stants uhp Ov as in Proposition 3.2.
Proof. We can write
p((N) 1i (C") as the symmetric product distribution
N II [I'())) ((xx)) (x(x)) exp (- (-xBB ABR
- ISiSN,
where the marginals 2 (X') each satisfy the LSI with constant an by Proposition 3.2. Also write 1 (X-)) = [I 10 (Xt). ). For an appropriately integrable function f on X denote by I for the
functions f((X*) f(x!,
X X Then by Proposition 2.2 of Ledoux (1999),
N
Ent, (N) (12) S Σ
B Ent ((1))) <
Σ
2 Olp
E E. /I
E Oxp
|| [.
Lemma C.11. The functional J(N) is convex in both arguments, and admits functional derivatives at any (5" (²) which are given as
NT(N) 8Cu
8J.N)
-1T ITT
p",
3 (Ct,5") "C",,")=T==M)(<""" pp.
Proof. Substituting (S", (--)= = (( (7 (N)
(T4 (("), (N)
(S")Ss,
8.((N) 8C"
8
(5 = _c JxN
(" (d) x(N)=
-Sa Jx 51111 - (ds))
ABx (C")
log p(N) (SH)
8 1
(N)
8cu (d2))
1x
5C"
N
pUBON
8
(-/ N
N
(10 + / (t)((a)))
N
(u(N)=
(( (CH)
-1 (I") (C")+
The integral over the configuration space measure 74 therefore lifts the expectation with respect the discrete measure μ.z. to a differentiable functional of Ç", which in turn pushes forward ( onto the space X'
The following proposition is crucial to controlling the evolution of the conjugate functional as well as the proximal distributions over time.
Proposition C.12. Suppose Ç") Bu. /BB are -iiiissiittffunttiiio such that the difference Ç"- Ç" my Lipsciipcht some my > Then the projected proximal distributions satisfy
W₂ (TT (N) (C*), (T
(N) (2*)) S ABA
my
32

---

Published as a conference paper at ICLR 2024
Proof. Taking the first-order conditions
- J (1 pf))
BBR
Pk
(SH))
N
log
pusoN
const.,
- J ("x (dx)
ABR
(2H)
log
const.
N
PuBoN
Subtracting both sides and integrating over the difference
Pk (N) (Ct) - ) we obtain
Jen Jx (C* 2dx)
(Ct) - - (c+))(
ABR
/
log
Pà
(SH) ((H)
(Tk (C))
-pb (2))
(10)
N
JNNN
Pk
Now the left-hand side of (10) be bounded from above by
- -sew J (5t -(") (dx)) (Tk - p/ (3*))(22)
1 =-
-5" Pa (5") 11 (1) (2"))
(N) (C"), (1 m ((x)) S m, W2 Pi (C"), II f m, fi
((
(N) (5")),
while the right-hand side of (10) is bounded from below by
AB
KL
((t)) 1 ((+)) + (E)
N
AB
W3 (pk (N) (S*), (2
N
a AB,
P (N) II
(N)
(N) ((²)),
where we have used Talagrand's inequality from Lemma C.10 and the W2 pushforward bound from Lemma C.7. Combining the two results yields the desired statement.
Denote the unnormalized aggregate derivatives as
dL (1,2, Ugy).
GL Bj 1=1
8/
Bj 8y
8%
8v (1 vg,)
so that p = T. (8%), D( D The functions 8% B& and / B2 are M and M,- Lipschitz, respectively, due to Assumption 2. Lemma C.11 and Proposition C.12 then allow to quantify the change in (8g, 8g) as time progresses.
Lemma C.13. We have the following one-step relation for J. k 2
J(N) (6% k%) J(N)
(6
S Bk / dL (1z2, Uey (-IT (dx) + Be /
8L (1 voy (IT (N)
(dg))
x oμ
oy
ABk
(KL(
[ 100 + <I
12
M2
+
N
ap
Ot
2XBB-1
Proof. By the maximality of J.M.
(8 5 = J( ( (8t)) p
(N) (N) (6%)) 5%)
- (8 p (( (62) (5 52)
(KL(PL
(N) (N) (o! + xK (62))
N
33

---

Published as a conference paper at ICLR 2024
$ - (0 6%)
A3x
(KL(h)))
Further defining the interpolations
k-1
8C 8y
8C
(s) - + 56g 6--1)=
Σ
Bg p, + s3 (1122 vac), 05851
óy
and similarly for 5% (s), we have
8%-1) {-) J(N) (s), (5))
J.N) (8k; 8k) J(.) (8
Jo ds
NJ
/ (8) 1
(8). (s)) + / (6% - -8%
k-1
(8) (s)) ds
DC#
85
(8) 8 I (d)) + / (8% x ds
/ (6) 84_ pp"(dz) - / (0% - - 101))"((de)
+
/
(8% 1 p (dx) + / 18% -8h- ( ds
x
(6% 8 1) / (6% - 8% 1
+
+
(6 ds
+
W
(0% ds
8C
(p Vay (1l (dx) + 3x / dy
8C (U May (
$ Bk
/ 8μ.
8C
/ dv
8C
MM
M2
3
+ 8xx
(1z V3h V3
(dz) 3x
(H22 May )p'
a₂
Oxy
2ABB-1
where for the first inequality we used the fact that 8% - 84_ is M, -iipshhi, and for the second applied Proposition C2 with m, = B.
We now give the promised proof of the pushforward evolution bound.
Proof of Lemma C.8. Note that Pk-1
(NN
fk- (8/ may also be written as
(NV
Mk-1 14k
(N) ((N)
Bx
B3 dh
8C (1 (sy)
14k
(NN)
BR 8th
0
BK-1
B
Since / BB-1 M,-Lipschiiz and
Be
Bk
k-1
8C
8C (prz v.y
8/
84
Σ
By (ux, vo,) + 3k
BR
BR
8q
j=1
Lipsset by Proposition C.12 we obtain the bound
2M
W1 (N)
S
A,
34

---

Published as a conference paper at ICLR 2024
C.5 PROOF OF THEOREM 3.7
Step 1. We first prove a convergent upper bound of the following surrogate M(Z., Vay ) for the NI error of the average distributions. Note that the defining maximum is lifted to the configuration space and the discrete empirical distributions have been replaced with their proximal counterparts for measuring relative entropy. While R is not exactly the desired quantity, it arises naturally from the discrete conjugate argument and helps bound the expected error.
& C,C(TTP (N), ( À N
A
& KL,
:= max ((N)
+
Σ
By
Bk
NB
==1
j=1
k
(1 Hx(N)) A
X
3g (1)
+
+
B&
N
NB
j=1
-S
8h.
33 8y (1 v3, (us u2,, (dzz) (1 (N) (d.2t
max ((N)
x x
BR 1=1
1 BB
5L
Bj 8v
(122 væ, [uv Voy (d
yx
X
(KL(H
| + KL(u(N>||ppan)
N
A
R Σ
By [Ip + KL
N BB
j=1
J (8% 8%) +
Σ
3j (KL(TS5))
N + KL MI
(1
Bu
j=1
SC
(uz, , May Muz, (dx) /
SC Vx, Ve, / ddy
Bg 8v
8p
j=1
due to the convex-concavity of C. Recursively applying Lemma C.13 then yields
M(H x² vT.)
k
1
(8) 53 - (8 + J(N)
JIN
B₁
BB
1=2
OL ( 11 Vay MMs2 - pd)) / Σ
8C
3
(1z,, Ver Ugr) (Vy,, - (dg))
ov
3=1
Σ 3g
(KI
+ KT( 1|
j=1
1
3
8C
(uxx vay uwy Muxs 11 1,, (dz))
BB
x op
8c 1=1 du (ux,, Vay (us, - 11 (dd))
k:
/
1
M2
M2
83
Σ
B
+
+
2x
0gp
B
By-1
j=2
where the initial term is substituted as J.M 64) = f |) 7 that A//1)) Proposition 3.6, we arrive at Es . M V.r )
(N) 18, 54) with the convention
( Now taking the expectation over the full history and applying
35

---

Published as a conference paper at ICLR 2024
B3 J, gc
-
E
2e2 a & Di
Σ
x du (ue;, May, NN, 11 11)
Bu
j=1
Σ
33
J/
8C
(ux Vey, (vey, - -1
+
1
M2
M2
$3
5v
21
0gv
B3-1
)=1
j=2
1
(+ ((()) + +C2V+
C3
1
M
M2
k
33
Bj
BB
j
VN
2X
ap..
0ly
Bj-1
1=2
(r + 1)?
+ 0(k-)) 3)
( (20((0)+ + 2A
M
M2
2C3
+
+ 20
27+
rk
Oy
VN
(r 1)² + +0(K-2)
2C3
C1 + 2C211 +
rk
VN
by simply using& 8 1. For = 0, the last expression is replaced by the exact bound
+ log k
9 (i()) + 202vm 2Cs 4
k
VN
Step 2.
We now control the NI error of the averaged pushforward proximal distributions using
n. In the defining maximum over p(D) E P2(x )) ),(()) E P2()")), ), we may restrict to product distributions y((²² = N ((N) vaN so that
2 r
max
1 k B₁
Bz vy,) AKL(H|l0")
A
Σ
3, (L(
Bk
j=1
j=1
1
3,L(ur,,)) AKL(WIl0")
A
3j KLLIII (
Bk
Bx j=1
max B,
B ( 1okk
1
3, (y,) - AKL(Hllp"")
+
A
By KL
Bk
BR
33 3, 1) - AKL(UIle") +
A
Bg 17
BR
Be
2 maxx 142
C(u, BL 1) - -AKT(NIO")) + (E
+ +EEBuy,,1,) XKL(m + (E
by convex-concavity of L as well as convexity of KL divergence, where we have written
1
1
(N)
11
1 Σ B
B&
BR
5=1
j=1
Again by Proposition 3.6, this is further bounded as
2 max - C2lu, Ex(,,E|TTTA) - EE sack
1
/
Σ
3,
SC. (n.
E
E[TT,))) -1T (dm))
B y j=1
8C
(E v) E Dask
[E (1 1
Be
36

---

Published as a conference paper at ICLR 2024
2 (EETAAEEEE (r 1 + +0(++)) -2 2C2
2C3
rk
VN
with the appropriate modification for 0.
Step 3. Finally, we convert the above pushforward proximal bounds back to a Wasserstein distance bound for the expected empirical measures. By Lemma 3.5 and Talagrand's inequality for the MNE (1²,, ,²",,
(E
(A)
2
(KT. (1)) (I(RITT&)|l>')
02v
2
2
NI(E M [())
and
and
(r + 1)2
+ 0(k-))
17 C16) + 402
4C3 VN
<
0
and
rk
Note also by Proposition 3.6 and Lemma C.8 that
M, (1L," xx))
sup E mi || 1p S.p,
1
M
33
F(Ux, 100s,-11774 1f (da)
BR ==1
1
Bj
r (++
Ci(n) Ci(n) + C2
C'3
+
1
3,W, (11
(N)
Bk j=l
VN
BR 3=2
<
Bj
Ci(n) (i() + C2v
C3
2M
Σ
k 13
B3
VN
Oi A B₁
Bj
j=1
j=2
(r 1)² 1)2
3 _/2 Ci(1) + C2V7+ + +0(+3)
C3
rk
VN
so the square of this term can be ignored. Hence we can conclude that
(7(juz,,)11) W (r (r+ 1)2 Ci(1) + Č2
Ō vN
rk
again with the + log modification when 0.
C.6 EXPECTED WASSERSTEIN DISTANCE
Theorem 3.7 gives error bounds for the expected distributions E[u and E[u J. This quantifies a sort of bias of the MFL-AG outputs, but does not tell us anything about the variance. Can we similarly bound the expected distance E[ tions to the MNE? The following fundamental fact about Wasserstein distance tells us that this is impossible:
+ Wi v²"] of the empirical distribu-
Theorem C.14 (Rate of convergence of the empirical measure, adapted from Fournier & Guillin (2015), Theorem 1). Let X be independent samples drawn from μ² E P2(RR for each i [N]. If d 2 3, the I-Wasserstein distance between the empirical measure 2xx = EN 5xs and the underlying averaged measure μ ; EN jet bounded in expectation
(WW p)] & Cw mmz(p) N-1/d.
where m2(1) is the raw second moment of and Ow is a universal conslant. If = 2, the rate is O(N-1/2(1og N) ifd 1, the rate is 012-1/2) Furthermore, this rate is tight up to constants.
Proof. The original theorem only considers i.idd. samples μ -...= Nº = 1 and omits the W, case for simplicity, so we present the necessary modifications.
37

---

Published as a conference paper at ICLR 2024
For Borel subset A C RR, the quantity Nuæ (A) is not distributed as Binomial NN, ((A)) but as sum of independent Bernoulli(p" (A)) random variables. Nonetheless, we obtain the same bound
2 - p(A))] - (Bip (A)) + p(A)) A /Var parp
I 2p(A) V ((A)/N.
We now repeat the same arguments and substitute p = 1,9 = 2 to arrive at the following inequality,
(wee w)] S mm)
2 (2- (2dm /N)
from which point we give explicit computations. Defining
logg2 N
logz N dm
mN
7mm
2
have for d 2 3 that
8
00
2 m (2 (22mmmma /N)1/2)
my
my 00
26 0
2
m nmm
(2 /N) +
Σ
2
2 m mn
m=0
m=0
112 m= x R=0
(dmy dm + 2)2(4/2-1)m
+
2
+ 2
2
m=U
(2 d)2(d/2 (1)
22+(d/2-1)m)
22-mx
(2d/2- 2)
(24/2- -2
O(N-1/4)
When d 2, the rate is easily checked be N- (log N)2. The tight rate in one dimension is derived using different techniques in Bobkov & Ledoux (2016), Section 3.
That is, even in the ideal case where chaos does not propagate and the particles are somehow i.i.d. sampled directly from the true distribution, the expected Wasserstein distance will always be of order N-1/dxVdy automatically incurring the curse of dimensionality. We emphasize that the uniform law of large numbers and short-term perturbation methods developed throughout Section C as well as the presentation of Theorem 3.7 have been carefully designed to bypass this technicality.
Nevertheless, it is still possible to bound the expected Wasserstein distance a similar manner save for the unavoidable N -idd dependency.2 We first present a more direct bound for the proximal gap.
Proposition C.15. The following inequality holds for all k.
E Wi m
r +
(()) +(())CCT++C+ +
Proof. The derivations are similar and more straightforward compared to the proof of Proposition 3.6. We only look k: 2 2f and directly compare J122, to 2 using Lemma C.3, 25 to the expected modified distribution using Theorem C.14 (recall that the modified particle trajectories Xj are independent when conditioned on (X. W) )1:k t), the expected modified distribution to the stationary distribution IT ((,)) using Proposition C.6, and II (x)) back to IT j
(NN using Lemma C.8.
E (Meg. IT 1
[7)) < E / 5; EWW Elu
of course. we may also simply run the algorithm multiple (M) times and take the average of the outputs, which would also bypass the issue and yield the standard 1//M M convergence.
38

---

Published as a conference paper at ICLR 2024
N
ElW2
11
+
(
11 1
1=
r +1
To
+ Cw
B
N 1/1xx
L
1
N
( 1 + 24) + 2M 1-]
3k-1
Σ
+
N
an
Bk-j
1=0
r r+1
4
2Mp (r + 1)6
1oy Cw + gu. N N-1 +V
(SQ + 9h) + 24)
f+1
V
Vou
Ox
and h E E++
r+1 (n( + +2 CV
= k
We now give the desired bound for the expected Wasserstein distance to the MNE. Note the effect of dimensionality compared Theorem 3.7.
Theorem C.16 (Variance of discretized MFL-AG). If and By K with 0, the MFL-AG discrete update satisfies for all K, N,
Ci(1) ElWi(ug x 16 112 EEWW )| (r+ 21 + -
rK
with similar constants as in Proposition 3.6. When r = 0, the first term is replaced by Olog K/ K/K). If dx V dy- = 2, the third term is replaced by O(N-1/2(log )) if dx dy 1, O(N 1/2).
Proof. Note that by convexity,
v) - c(11 (M) v) 2 J
5C
(N) (ue I (dx)) ( II M) (II
8p
We can modify Step 2 of Section C.5 using Proposition C.15 as follows.
Ex ).
M(" (,,
max 1 h
A &
2 Esx Mick
By B),( - (KI((l)
+
Σ
B3 (IT
B₁
B ==1
1=1
1
3, 3, -
- AKT((UIP')) +
A
By (
Bk
B
j=1
2 (
1
Σ 8, AKI(
A
Σ
By (1T
M.N
BR
B
1 4
C(T (N)
(N) ,D) AKT(VIIO") +
33 KI ( 1lx))
B&
B& ==1
M
&
W 1
Mr
Σ
B, W (13,, 11
BB 1=1
B
1=1
2 E B
max (Zx) - AKL(U|l0") +IL R.U
L(II P). - (KL(ull0") + 7
& M
Σ
2, W1 11
Mr
Σ
3 e M [Wi 11 (1 (x
Bs j=1
Bx
39

---

Published as a conference paper at ICLR 2024
2 B( [NI(II 11)x
My
Σ
&
Bg
Bb j=1
Combining with Step and Lemma 3.5 gives that
KL Pulll"" (L(TT& (r 11+ rk
(i(())
+ CN
Finally, we convert back to a Wasserstein distance bound by invoking Talagrand's inequality and Proposition C.15 again:
2 + ( (,
4 (TT.ll ag
B
This concludes the proof.
Remark. If we assume higher degree of regularity that all relevant distributions have finite fourth moments, say, then Theorem C.14 actually holds for the 2- 2-Wasserstein metric. Theorem C.16 can then be stated in terms of the 2-Wasserstein distance the MNE, guaranteeing us slightly better control over the error compared to Proposition 3.6 which only allows a W1 formulation.
D CONVERGENCE ANALYSIS OF MFL-ABR
D.1 INNER LOOP CONVERGENCE
The convergence of the decoupled inner loop is simple consequence of the convex analysis for single optimization (Nitanda et al., 2022a); we reproduce the proof here for completeness.
Proposition D.I (Convergence of MFL.-BBR inner loop). Under Assumptions and 3,
2C KT 117) S X exp(-2aAr)) (L(v),-110)) S X expl- -2xd).
2C,
Proof. For any StST, T, the KL gap converges as
d KT.((,,ll / log
Ph.t
orrk.
A 1f log
Mks Vx
(1/, Vz log
Mket (dx)
dt
Fix
Thk
Pax
/
Mlee 12 p (dz) S -2ad KL(W (u))
Ve log
P&
by substituting the Fokker-Plant Planck equation for 14,, and applying the LSI for ug via Theorem A.6. Invoking Gronwall's 's lemma and Lemma D.2 below for ea concludes the proof.
The following result gives uniform bounds to control the magnitude of perturbations.
Lemma D.2. For any w > 0, define the class
Fl -Z= { E |los
WC
<
Then under Assumption 3, the distribution Tug E Fl and pks uk Ft
Proof. For Pag, the exponential term and the normalizing integral
1 S.
(uun vh) vn)) 2
dl exp (-X x Ez (uis (He, dx
1
exp
x (-X oz
are both bounded by T TM/A, proving the assertion. For ph.,, define the density ratio hes whel De.. The Fokker-Planck equation for u/,, reads
0,01, Va. (Mhe V. ( (of (uk, ux) + +XVbUr)) + AAathe AVa (nhn va log 8p
Mhi P&
40

---

Published as a conference paper at ICLR 2024
so that the parabolic partial differential equation satisfied by h, is derived as
a,h, = Px 8.pk.
= A V. (P he V, log h4)
AV log Fi -vh + XAhz
(OC 8p
(ux, vs) + AvoU*) Value + AAht
where L is the infinitesimal generator for the stochastic process X1. Hence by the Feynman-Kac formula, we may write for any 1 E [0
h,(2) = E [x)() E
(x,)
Since ||log(Ax 1l0 S 2C,,/A as discussed above, we infer that || S 2C / and therefore
Mler log
HR
4C
log
S
+
log
pr
X
i.e. Prr F& for all k. Finally, since F& is closed under linear combinations in P2(X)
conclude that
μs = 3pk, + 3(1 - -)) + t.. -(1 3)* pb.r E Fo.
D.2 PROOF OF THEOREM 4.
We perform one-step analysis of the outer loop by setting for S S
p(s) = (1 - p + Aspk.. v(s) = (1 3s)ur + 33v
so that p(0)= = jkx x(1)= = p and v(0) = vk, v(1) = Vh+ We track the KL divergence to the interpolated proximal distributions defined
p
18C (m()), ((())) 7(s)
p (s(s) exp (4 (m(o))
((s)
(s)
exp
8p
Note that the second order bounds in Assumption immediately imply the following Lipschitz property in TV distance,
SL (H.
SL
(n', (u',z))
I 2C TV(H, p²) 20 TV(V.').
6f
8μ
Similarly to Lascu et al. (2023), Lemma A.2 we can then prove that
TV
(s))
1
C₁
[2Cμ)
exp
+ exp
(2Cmy, (V(us,((s) 20 TV(,,, v())))
2A
< Bs("
where we have written
ta Cuu + Cyv
2Cμ
exp
+ exp
Also, (ss) E FV and (us) E Fl by Lemma D.2 which implies ||log(<(s)/ (s)) S 6C,/A.
Now the derivative of the KL gap of the max policy for any lis
d (L(m(>)) ((s)) = / log pls). (.f((s((dr) - / d, log (d))
ds
na(s)
41

---

Published as a conference paper at ICLR 2024
The first term can be decomposed as
/ log
mss) ((s)
(s)x))(dx))
x
log (s))
3
((s) (1b, (x)(dr)
x
B log ((8)
(T((s) - mms)) + (u())= 14k + 1/,r Fh + Thx (dx))
(((s)
x
log (us))
S 3 (KL(U(s) (())) + KL(M(s)] (()))) + +
TV
((s)
log
((s) (1(s)
/2KL ,r (10) + log m(s))
+ 3
TV (ss))
[i(s)
S - (L((()) (()) + 128C
23s(tt +1) + V C
V exp(-ax7))
by Proposition D.I. For the second term, we may follow the derivations presented in Section 3 of Lascu et al. (2023) with minimal modifications to obtain
/ 0, log (ss)
X J1 X one
8C L
(()) - -i (4x)(dz)
+ 3 / x Suōn
8 8 vs), p(s))(dz)((e (dw).
When O, the first integral is nonpositive due to convexity while the second integral cancels out when adding with the corresponding term for the KL gap of the max policy, which completes the argument in Lascu al. (2023). Hence the remaining
must control is
B JI
2))(() The +uk u(s)) - pAx (dzz
XJ
x
8p2
-1 Sudy (1(s) ((), w)((s - Thy + - (dx)) ux (dww)
-/
82C
- (pnp + (TV A&) ((s)))()s))
4
< X (CHp + (tt)(t" + 1).
Adding everything up, we obtain
d
ds (KL(U(s)) ((s)) +LLT
-B (KL(((())) ((+)) + (L((())
1230
C 23( +1) + V / explp exp(-aarr)
432 + X - -C + Ctv) + +1)
123C
Co
4 X (Cuo + Cvv) + +1).
2,(e" + +1) + V x exp( exp(-a)r)
+
By applying Gronwall's lemma over s [0, 1] and iterating over conclude that
KT( (hx) + KL(v (x))
2(C, + -C))
12
(c) + ct exp(-axe
exp(- 1ap(-31) 3k)
X
x
42

---

Published as a conference paper at ICLR 2024
43 X ((6C,, Cuu + (tt) + 1) (6C, Oue Ctt) + +1).
Finally, applying Lemma 3.4 of Lascu al. (2023) yields the suboptimality bound
NI(HR, P4) S 2( + exp( 8k) +
12
(
exp(-aAr) + C3. + c
VX
Hence an e-MNE may be obtained in k O log () outer loop iterations by taking 3 O and Oloo )
43


Reviews:
[{"review_id": "OeLFLdg3ZL", "reviewer": "Reviewer_bLee", "summary": "The paper analyzes two approaches for simulating mean-field games, denoted by MFL-AG and MFL-ABR respectively.  The convergence of the algorithms (in idealized form, and finite particle form) is provided.", "questions": "Is it possible to write in this setting an analogue of the BBGKY hierarchy, and conduct the analysis that way? Would this at all sharpen the rates? It seems that under the convex-concavity assumption and bounded gradients assumptions at least, the analysis would be tractable using that approach.\n\nCould Figure 1 be moved to the main text? It is a core part of the contribution and should not be placed in the appendix.\n\nCould the dependency of $K$ on key problem parameters be clarified in the main text? It seems from the Appendices that it should be roughly $\\epsilon^2$. Additionally, it would be good to highlight dimension dependence, which appears to be fairly mild.\n\nWhy in Theorem 4.1 should $k$ be taken as $1/\\epsilon \\log \\epsilon$? Shouldn’t $\\log 1/\\epsilon$ suffice?\n\nIn Lemma C.2, no need to refer to Gronwall’s lemma (induction suffices).\n\nA definition of “convexity” should be given in the Appendix. E.g. geodesic convexity in $W_2$, or convexity wrt TV distance.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This appears to be the first algorithm which achieves a convergence in time + propagation of chaos result for mean-field games under transparent assumptions.\n\nThe proofs are well-written and contain analytical insight into this problem. In particular there is clear intuition on how averaging helps to regularize this problem.\n\nBoth algorithms are realizable and seem to have reasonable performance in practice.", "weaknesses": "I have some issues with the Assumptions in the paper.\n\tFirstly, the requirement of convexity combined with strictly bounded gradients is quite strict, as it essentially forces the problem to be roughly linear. I think this is a major restriction and the authors should do their best to circumvent this, or otherwise explain why this assumption was necessary in their opinion.\n\nSecondly, it is unclear to me why the authors prefer to use $L^1$ Lipschitz-ness and obtain their result in Wasserstein-1. Isn’t it more natural to frame all results in W2, or was W1 chosen for a specific reason?\n\nThe dependencies on $N$ are worse when compared to standard mean-field results. The dependence on $\\eta$ in the first term is also not ideal. For instance uniform-in-time propagation of chaos for the mean-field Langevin dynamics would look like $k^2/N^2$ (in $W_2^2$ under mild assumptions).\n\nThe results in Figure 1 are decent, but it is difficult to have any scale for comparison. It seems as well from the $W_1$ convergence that there is some degree of persistent bias for the choice of parameters. I would recommend further experiments if the authors are interested in highlighting the empirical performance of their approach.\n\nIn summary, I think this is a useful first result in this setting. However, there are numerous ways that it could be improved and I have some important questions regarding the results. I would be willing to raise my score if some of my questions could be addressed in more detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QL1rZp9LQv", "reviewer": "Reviewer_DQbp", "summary": "The paper considers the solution of minmax problems with convex-concave objectives (plus entropic regularization terms) in the space of pairs of probability measures. Numerous problems can be viewed as particular cases of this. \n\nThere exists a natural Mckean-Vlasov type system of diffusions --  mean-field Langevin dynamics (MFLD) -- that should converge to the saddle point that solves the above problem. The paper shows such a result for a version of these diffusions where the drift term is averaged over past states. Moreover, particle approximations of the diffusions are shown to satisfy strong convergence rates: for instance, the approximation bounds are uniform in time. \n\nBounds for the authors' methods are given for \"Markov games\" assuming oracle access to certain functions and gradients related to the problem. A small simulation study suggests improved performance vis a vis MFLD.", "questions": "*(Q1)* Algorithm 1 and elsewhere - rathen than sample subsets of $\\mathcal{X}_k,\\mathcal{Y}_k$, maybe you could just use a weighted empirical measure where set $\\mathcal{X}_k$ has weight proportional to $\\beta_k$?\n\n*(Q2)* Can you clarify what is $\\Pi$ and explain specifically the proof of Lemma C7?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "The class of minmax optimization problems under consideration is quite natural. The result seems to be the first of its kind for this sort of problems. Similar results on convergence of McKean-Vlasov particle systems for convex optimization would be much easier to prove. The technical difficulties faced in the minimax scenario with the time averaging seem considerable.", "weaknesses": "The assumptions over the two measures used in entropic regularization are quite strong. The result of Theorem 3.7 has an expectation inside $W_1$, which is somewhat hard to interpret: it would seem to be saying that the bias of the procedure is small, but not the variance, so many repetitions of the particle dynamics would be needed to estimate the expectation of some function $f$. The outer-loop particle discretization error is not accounted for in the algorithm from Section 4.\n\nI do not understand what is going on in Lemma C.7 (it might be because I do not understand $\\Pi$ fully -- see below). \n\nSome of the notation is unnecessarily hard to parse. Let me offer a few examples.\n\nPage 5: *Denote ordered sets of $N$ particles* -- it would seem that the authors mean a vector in $\\mathcal{X}^N$. Also on the same page: it seems that the authors introduce the subscript $1:k$ to identify particle positions at different times, but then don't use this notation consistently at the bottom of the page (and also elsewhere). \n\n$L_\\mu$ and $L_\\nu$ are used to denote Lipschitz constants in the first/second variable, but also, $L$ is the functional and $(\\mu,\\nu)$ are used to denoted arbitrary elements of the space of probability measures.  \n\nThe definition of $\\Pi$ in page 6 as ``the average of the pushforward operators along the projections $X\\mapsto X^i$ does not seem correct. How can you project to a higher-dimensional space?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "szcG79EmVt", "reviewer": "Reviewer_ByeN", "summary": "This paper presents an approach to minimize optimization over probability distributions by extending the principles of mean-field Langevin dynamics. They propose two methods: (MFL-AG),  a single-loop algorithm designed to achieve convergence towards the mixed Nash equilibrium, and (MFL-ABR), a two-loop algorithm that demonstrates linear convergence in the outer loop. Furthermore, they also investigate various discretization methods and offer a fresh analysis of how chaos spreads, taking into account its dependencies on past distributions. This research paves the way for more in-depth investigations into mean-field dynamics for numerous learning agents.", "questions": "* Could you please explain more about what \"SYMMETRIC\" means in your proposed method and title? Is it mainly from the same temperature or regularization strength $\\lambda$ for both players?\n* Then how compatible your proposed method and proof can be extended to when there exists $\\lambda_1$ and $\\lambda_2$ for two players respectively? Since you mentioned that the problems you are looking for naturally arise for example solving robust learning or zero-sum games in reinforcement learning. Usually, in the robustness via adversarial learning, the regularization strength is relevant to the strength of the adversary. For example, if the adversary is attacked on soft actor-critic (SAC)[1], which originally had its regularization term (temperature), then it is not flexible to have the regularization terms for the target agent and the adversary the same values.\n* Could you analyze why MFL-AG can have a lower NI error compared with MFL-ABR and does it mean that MFL-AG performs better than MFL-ABR in this experiment? Furthermore, please suggest what kind of numerical experiment is more suitable with MFL-ABR against MFL-AG, and vice versa.\n\n[1] Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning (ICML), 2018", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "* The paper's contributions are supported by theoretical proofs\n* It seems that the convergence of mean-field Langevin dynamics was still an open problem and the problem of this paper is well defined.", "weaknesses": "* Proposed methods could be well motivated. The two proposed methods themselves are convincing. However, is there any reasons or motivation why you have both methods at the same time: mean-field Langevin averaged gradient and mean-field Langevin anchored the best response? Any explicit relationship between these two settings? \n* The description of the equation can be more comprehensive. Usually, we should describe all the notations of the equation at least right after it. For example, you do not mention what $\\rho^{\\mu}$ and $\\rho^{\\nu}$ are in equation 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oiYkCEiHx5", "reviewer": "Reviewer_q6kk", "summary": "This paper studied the mean-field minimax theorem with entropic regularization. The contributions can be summarized as follows:\n\n1. The authors proposed the MFL-AG algorithm, which convergence polynomially in continuous time. The author also proposed a discretized algorithm with a uniform-in-time propagation of chaos. \n\n2. The authors proposed the MFL-ABR algorithm and provided a convergence rate for the discrete outer loop.", "questions": "Please also refer to the strengths and weaknesses part. \n\n1.  In Chen et al. (2022), they provide a propagation of chaos in KL-divergence, under extra regularity assumptions (see Theorem 2.4 in Chen et al. (2022) ). In this paper's settings, do you expect a similar propagation of chaos in KL divergence? Also, the propagation of chaos in Chen et al. 2022 provides a $O(1/N)$ error, which is optimal in order of $N$. Is it possible to improve the bounds to  $O(1/N)$ or is there any lower bound on the convergence rate (of propagation of chaos)?\n\n2. In the numerical experiments, you use a 3-point NI error to approximate NI error, what's the justification for this? Since in principle for given $\\mu_{\\mathscr{X}^i}$, one should compute $\\arg\\max_{\\nu} L_{\\lambda}(\\mu_{\\mathscr{X}^i}, \\nu )  $ , it could be that $ \\nu_{\\mathscr{Y}^j}$ are far from $\\arg\\max_{\\nu} L_{\\lambda}(\\mu_{\\mathscr{X}^i}, \\nu ) $. Besides, for fixed $\\mu_{\\mathscr{X}^i} $, to compute $\\arg\\max_{\\nu} L_{\\lambda}(\\mu_{\\mathscr{X}^i}, \\nu )  $, can't one directly run a mean-field Langevin dynamics for example?\n\n3 . Is it possible to apply the annealing techniques in Lu (2022) to achieve the MNE of the unregularized object (assume there is)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The proposed MFL-AG dynamic is new in the literature, and the weighted average of the dynamic provably converges to the MNE polynomially in time.\n\n2. The authors provide a uniform-in-time propagation of chaos for a finite-particle implementation of the MFL-AG flow. Despite I have a few questions on the utility of the results, I believe the techniques based on Chen et.al 2022 are novel in mean-field minimax problem literature, and could potentially benefit future works.\n\n3. The proposed MFL-ABR flow provides a potential way to find a discrete finite-particle algorithm for the best-response dynamics in mean-field min-max problem settings.", "weaknesses": "**Regarding the MFL-AG**:\n\n1. The utility of the finite particle analysis in section 3.3 is not very clear to me. I have the following questions: \n\n- 1.1 In Theorem 3.7, you bound the Wasserstein distance  $ W_1( {E}[ \\mu_{ \\overline{\\mathscr{X}}\\_k } ], \\mu\\_* )$. However, I didn't see why it is useful to consider ${E}[ \\mu_{ \\overline{\\mathscr{X}}\\_k } ]$ since ${E}[ \\mu_{ \\overline{\\mathscr{X}}\\_k } ]$ is basically the average of the pushforward of joint measures to each particle, what does the convergence of this measure to MNE implies? To my understanding, the propagation of chaos refers to that the particles behave almost i.i.d, how does this convergence results imply the particles are almost i.i.d ? Thus, it makes more sense to me to consider  $ W_1 ( \\mu_{ \\overline{\\mathscr{X}}\\_k }, \\mu_*)  $ for example.\n\n- 1.2 Cont'd: you mentioned in the footnote on page 6 that the typical rate Wasserstein distance between a measure and **i.i.d** sampled empirical measure is $N^{-1/d}$. In this case, it seems that the particles in $ \\mu_{ \\overline{\\mathscr{X}}\\_k}$ are highly correlated since the dynamics are coupled. The correlation is not only between the particles in $ \\overline{\\mathscr{X}}\\_k$ for a fixed $k$, but also between particles in different times (i.e.$ \\overline{\\mathscr{X}}\\_k$ and $ \\overline{\\mathscr{X}}\\_j$ for $j \\neq k$ ). Thus, it is unclear to me what is the convergence rate of $W_1(\\mu_{ \\overline{\\mathscr{X}}\\_k},   \\mathbb{E} [ \\mu_{ \\overline{\\mathscr{X}}\\_k} ] )$?\n\n- 1.3 The discussion on top of page 7 is not very clear to me. First of all, you say you expand around $\\mu, \\hat{\\nu} $, but the first order condition in (3) is only for MNE, i.e. it is not clear to me why $ \\frac{\\delta }{\\delta \\mu} \\mathcal{L}\\_\\lambda(\\mu, \\hat{\\nu}) =  \\frac{\\delta }{\\delta \\hat{\\nu}} \\mathcal{L}\\_\\lambda(\\mu, \\hat{\\nu}) = 0$ for an arbitrary $\\mu$. Do you mean you expand around $  \\mu_*, \\nu_*$? Also, it is unclear to me why one can ignore the higher-order terms. Thus, currently, I don't understand how the upper bound on $W_1$ implies an upper bound on $NI$ error. In fact, since the $NI$ error upper bound the KL-divergence, and the KL-divergence upper bound $W_1$, I doubt the correctness of that the $NI$ error can be upper bounded by the sum of $W_1$ in general.\n\n- 1.4 Cont'd: in the case where $\\mathcal{L}$ is bilinear and assumes good regularity (e.g. the kernel is uniformly bounded), is that possible to upper bound  $NI( \\mathbb{E}[ \\mu\\_{ \\overline{\\mathscr{X}}\\_k } ], \\mathbb{E}[\\nu_{ \\overline{\\mathscr{Y}}_k } ])$ by the sum of $W_1$ in the propagation of chaos results?\n\n- 1.5 Cont'd: I suggest making the discussions on top of page 7 more formal and rigorous. The current ambiguous discussion makes it hard to understand the utility of the propagation of chaos results.\n\n\n**Regarding the MFL-ABR**\n\n2. The utility of the results in section 4 is also not very clear to me, I have the following questions:\n\n- 2.1 It's not very clear to me why algorithm 2 works. Since in each round, one should input $\\mu_k, \\nu_k$ which comes from the outer iteration, while in algorithm 2, input $\\mu\\_{\\mathscr{X}\\_k}, \\nu\\_{\\mathscr{Y}\\_k} $ which are empirical measures. Due to the lack of propagation of chaos results, it is not clear to me that $\\mu\\_{\\mathscr{X}\\_k}, \\nu\\_{\\mathscr{Y}\\_k} $ will converge to $\\mu\\_k, \\nu\\_k $.\n\n- 2.2 Theorem 4.1 analyzes the convergence of the discretized version of MFL-ABR. However, compared to the results in Lascu et al. (2023), it seems to me that there are two drawbacks due to the inner Langevin dynamics: (1) There's a non-vanishing error $C \\beta$, so one has to make $\\beta$ small which in turn will make the convergence rate small. (2) The convergence rate of inner Langevin dynamics depends on the LSI, in the case of small $\\lambda$, the convergence rate can be small.  These two drawbacks might limit the utility of the MFL-ABR algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BbBlofez8z", "reviewer": "Reviewer_tSuv", "summary": "The authors considered the problem of developing a symmetric mean-field Langevin dynamics (MFLD) algorithm for distributional minimax problems with global convergence guarantees. Based on the mean-field Langevin descent ascent (MFL-DA) dynamics, the authors proposed mean-field Langevin averaged gradient (MFL-AG) flow that replaces the MFL-DA drift with the historical weighted average; based on the mean-field best response (MF-BR) flow, the authors proposed the mean-field Langevin anchored best response (MFL-ABR) process. Extensive convergence analyses were provided for both methods. The authors also studied the time and particle discretization error and applied their methods to zero-sum Markov games. Numerical experiments were conducted to compare their methods with MFL-DA.", "questions": "See weakness. Also, what are some limitations of the proposed methods?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Compactly written, this paper is the first to establish convergence results in using MFLD for minimax optimization over probability measures. By incorporating a weighting scheme into MFL-AG, the authors offered a creative direction for future works on MFLD. The comprehensive discretization analysis complements the continuous-time convergence result well.  Their second method, MFL-ABR, is also an interesting improvement upon MF-BR that is realizable by a particle algorithm and enjoys convergence guarantees.", "weaknesses": "The paper could be improved by providing more intuitions for the proposed methods. For example, what is the intuition for using a weighting scheme in MFL-AG, and what might cause MFL-AG and MFL-ABR to converge more slowly than MFL-DA in the numerical experiments? Is it correct to think that the slowdown of the convergence ensures better convergence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)