Convergence of Mean-Field Langevin Stochastic Descent-Ascent for Distributional Minimax Optimization
Authors: Zhangyi Liu
Feng Liu
Rui Gao
Shuang Li
Venue: ICML 2025 spotlightposter (2025)
Keywords: mean-field Langevin dynamics
minimax optimization
Wasserstein gradient flow
Primary area: optimization
TL;DR: We derive a $\tilde{O}(1/\epsilon)$ convergence rate for dicrete-time mean-field Langevin stochastic gradient descent-ascent algorithm for solving distributional minimax optimization.

Abstract: We study convergence properties of the discrete-time Mean-Field Langevin Stochastic Gradient Descent-Ascent (MFL-SGDA) algorithm for solving distributional minimax optimization. These problems arise in various applications, such as zero-sum games, generative adversarial networks and distributionally robust learning. 
Despite the significance of MFL-SGDA in these contexts, the discrete-time convergence rate remains underexplored.
To address this gap, we establish a last-iterate convergence rate of $O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$ for MFL-SGDA. This rate is nearly optimal when compared to the complexity lower bound of its Euclidean counterpart. This rate also matches the complexity of mean-field Langevin stochastic gradient descent for distributional minimization and the outer-loop iteration complexity of an existing double-loop algorithm for distributional minimax problems.
By leveraging an elementary analysis framework that avoids PDE-based techniques, we overcome previous limitations and achieve a faster convergence rate.

Convergence of Mean-Field Langevin Stochastic Gradient Descent-Ascent for Distributional Minimax Optimization
Zhangyi Liu
Feng Liu
Rui Gao Shuang Li*
Abstract
generalizes minimax optimization problems in Euclidean spaces and arises widely in many important applications, including generative adversarial networks (GANs) (Good- fellow et al., 2020; Arjovsky et al., 2017), distribution- ally robust learning (Madry al., 2017), as well as zero- sum games with mixed Nash equillibrium (Daskalakis Panageas, 2018).
We study convergence properties of the discrete- time Mcan-Field Langevin Stochastic Descent- Ascent (MFL-SDA) algorithm for solving distri- butional minimax optimization. These problems arise in various applications, such as zero-sum games, generative adversarial networks and dis- tributionally robust learning. Despite the signifi- cance of MFL-SDA in these contexts, the discrete- time convergence rate remains underexplored. To address this gap, we establish last-iterate conver- gence rate of ( log 2) for MFL-SDA. This rate is nearly optimal when compared the complex- ity lower bound of its Euclidean counterpart. This rate also matches the complexity of mean-field Langevin stochastic gradient descent for distribu- tional minimization and the outer-loop iteration complexity an existing double-loop algorithm for distributional minimax problems. By leverag- ing elementary analysis framework that avoids PDE-based techniques, we overcome previous limitations and achieve a faster convergence rate.
Solving such optimization problems over distributional spaces is inherently challenging. Unlike in Euclidean spaces, the convexity/concavity of the objective function does not di- rectly guarantee the convergence of gradient- -based methods. address this, mean-field Langevin dynamics (MFLD) has emerged as powerful theoretical framework (Mei al., 2018; Sirignano & Spiliopoulos, 2020; Hu al., 2021; Chizat, 2022; Nitanda et al., 2022a; Suzuki et al., 2024). In this framework, an entropy reghoupy-rruulaiieed distributional convex minimization is considered:
min E(μ) - TH((),
#EP(
where H(n) = - R, log [4] is the entropy functional. The mean-field Langevin gradient descent method in discrete time proceeds as follows:
1. Introduction
SE 8y
0x+1 0g r/
JuN (Ok) 2
In this paper, we study distributional minimax optimiza- tion of the form
$E [Mx] is the first varia- where μe is the distribution of 0s: 8y. tion of with respect to μ1 at pæ; and & is an independent injected standard Gaussian noise. Notably, the gradient in this context often replaced with unbiased stochas- tic gradient estimator to accommodate practical settings such as stochastic gradient descent. By leveraging the uni- form log-Sobolev inequality, corresponding to the Polyak- Lojasiewicz (PL) condition (Karimi et al., 2016) in the dis- tributional space, recent works have established exponential (linear) convergence for MFLD in continuous time (Chizat, 2022; Nitanda et al., 2022a) sublinear convergence of the order O log ! in discrete time (Nitanda et al., 2022a) and with a stochastic gradient oracle (Suzuki et al., 2024).
min max E(p, v),
DEPLEEP,
where P2 are sets of probability measures and E is convex-concave probability functional. This formulation
'Department of Mathematical Sciences, Tsinghua Univer- sity, Beijing, China School of Economics and Manage- ment, University of the Chinese Academy of Sciences, Bei- jing. China 'epaatment of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA "School of Data Science, The Chinese University of Hong Kong (Shenzhen), Shenzhen, China. Correspondence to: Rui Gao <rui.gao gao mccombs.utexas. udex.
The MFLD framework can be extended to distributional min- imax problems (1), giving rise to the Mean- Field Langevin Descent-Ascese (MFL.-AA) algorithm. For instance, under
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
two-sided Polyak-t.ojasiewiez conditions, Lu (2023) estab- lished linear convergence rate for MFL.-DA in continuous time. Furthermore, Kim et al. (2024) proposed two variants: the Mean-Field Langevin Averaged Gradient method, which guarantees average-iterate convergence, and the Mean-Field Langevin Anchored Best Response, a symmetric double- loop algorithm whose outer loop achieves linear last-iterate convergence. Despite recent advances, the convergence properties of single-loop discrete-time algorithms remain largely unexplored. A notable exception is the discrete- time stochastic Mean-Field Langevin Averaged Gradient algorithm introduced by Kim et al. (2024), which achieves an average-iterate convergence rate of ( O(c-O(1/o)), where a the log-Sobolev constant. However, this rate appears suboptimal. Furthermore, last-iterate convergence often more desirable in minimax optimization due to its practical significance. To our knowledge, the nearly optimal complex- ity of last-iterate convergence for discrete-time Mean-Field Langevin Stochastic Descent-Ascent (MFL-SDA) has not yet been investigated.
tings involving stochastic gradient oracles and Unite-particht approximations, established by Suzuki al. (2024). Our discrete-time analysis draws inspiration from a recent work by Wang et al. (2024), which established the convergence of MFLD in discrete time for one-hidden layer neural network with softmax activations and a square loss.
Distributional Minimax Optimization Compared to dis- tributional minimization problems, the study of MFLD in distributional minimax problems remains limited, particu- larly in the discrete-time setting. The most relevant work in this area is by Kim et al. (2024), who investigated the conver- gence of general convex-concave functionals in both contin- uous and discrete time. Rather than analyzing the standard MFL-DA algorithm, they proposed two alternative meth- ods: the Mean-Field Langevin Averaged Gradient (MFL- AG) (Tao et al., 2021) and the Mean-Field Langevin An- chored Best Response (MFL-ABR) algorithm (Lascu et al., 2023). MFL-AG updates are computed using a weighted average of past gradients instead of the current gradient. For the discrete-time setting with a stochastic oracle, they demonstrated that the average-iterail -iterate convergence rate to an e-optimal saddle point is O(c-1-0(//a)) ) where a is the log- log-Sobolev constant. They derived an ((1/d) bound for a and noted that this dependence on the dimension of the sample space can sometimes be avoided. MFL-ABR is a double-loop algorithm, with the outer loop having an iteration complexity of O log 2). Additionally, Cai et al. (2024) analyzed MFL-SDA with bilinear functional and strongly convex-concave interaction function, an assump- tion not applicable in our context. Wang & Chizat (2022) introduced and analyzed a particle-based method inspired by the mirror prox algorithm in Euclidean space.
In contrast, minimax problems in Euclidean spaces have been extensively studied. For stochastic strongly convex- strongly concave functions, an optimal complexity of O(L/e) is achieved by a variant of stochastic gradient descent-ascent (Yan et al., 2020; Zhang& & Hu, 2025). Sim- ilarly, for problems with two-sided PL conditions using a stochastic oracle, an (1/e) convergence rate is attained by alternating stochastic gradient descent-ascent (Yang et al., 2020). In view of this, it is natural ask whether MFL- SDA can achieve similar last-iterate convergence rate in the distributional space under the two-sided distributional PL condition. These gaps in understanding motivate our central question:
In addition, there has been some convergence analysis for MFL-DA in continuous time. Domingo-Enricn et al. (2020), Ma & Ying (2021) and Lu (2023) studied its convergence for finding the saddle point of an entropy- entropy-regularized ob- jective. Qualitative convergence results were established in Domingo EnrrichErcchhhh et al. (2020), while Ma & Ying (2021) proved the asymptotic convergence under quasi-static con- ditions, where the ascent dynamies is infinitely faster or slower than the descent dynamics. Lu (2023) provided non- asymptotic exponential convergence rates with based two-sided PL condition. Zhu et al. (2024) demonstrated sublinear convergence rate for the stochastic gradient descent-ascent algorithm for solving functional minimax optimization using mean-field neural networks, and showed that the discrete-time algorithm converges to its continuous- time counterpart.
Can the discrete time MFL-SDA for (1) achieve a last-iterate complexity similar to that of minimax problems in the Euclidean space?
1.1. Related Work
Mean Field Langevin Dynamies Our primary motiva- tion stems from recent advancements in applying MFLD to neural networks. The pioneering works of Mei et al. (2018);
Chizat & Bach (2018); Sirignano & Spiliopoulos (2020) leveraged MFLD to establish global convergence guaran- tees for (noisy) gradient descent in optimizing two-layer neural networks. Building on these foundations, Chizat (2022); Nitanda et al. (2022a) demonstrated that, under the log-Sobolev inequality-th the distributional counterpart of the PI. condition, continuous-time MFL.D for distribu- tional minimization can achieve an exponential convergence rate. Furthermore, Nitanda et al. (2022a) showed that the discrete-timg time MFLD enjoys a convergence guarantee with a complexity of O log(!)) This rate also extends to set-
Eucliean Minimax Optimization There is a substantial body of research on minimax optimization problems in Fuclidean space (e.g., see recent works of Daskalakis &
2

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Panageas (2018); Doan (2022); Jin al. (2020); Lin al. (2020); Li al. (2022)), encompassing both the convex- concave setting and more general scenarios. Among these studies, some provide valuable insights for our work. For instance, Doan (2022) analyzed the convergence properties in Euclidean space under the PL condition using continuous- time analysis. Similarly, Yang et al. (2020) proposed a (stochastic) alternating gradient descent-ascent algorithm under the PL condition. We aim to achieve a similar conver- gence result in the distributional space.
differs slightly from Lu (2023), who considered entropy reg- ularization. When the reference distributions are standard Gaussians, the KL divergence is equivalent to the entropy plus the recond-order moment of the distribution. With KL (or entropy) regularization, the energy functional E(u,, v) is strongly convex in f and strongly concave in V, which ensures the existence and uniqueness of the mixed Nash equilibrium (p*, ,²) (Kim al.. 2024, Proposition 2.1). where
B(C v) S B(x² 1²) S E(H, VU,
(3)
1.2. Main contributions
dy ju, (-()) the first variations of J with respect to μ and 1/ respectively, which are assumed to be well-defined throughout. Convexity/concavity can be also defined via first variations, as detailed in Appendix A.1. Denote by 0 and w the random variables with distri- butions μ and v, respectively. Denote by V &dd V dJ
Denote by 5d ju, (-() and 5J ou
We establish the last-iterate convergence rate of the MFL.- SDA algorithm in discrete time. Our O log 4) bound is nearly optimal, comparable to the O bound for minimax problems in Euclidean space, and aligns with the O log !) complexity of mean-field Langevin stochastic gradient de- scent in distributional minimization problems (Suzuki et al., 2024) and the outer-loop iteration complexity of the double- loop MFL-ABR algorithm (Kim et al., 2023).
öр [u, and dv [t, (-)-) the Wasserstein gradients of J with respect to μ and v, respectively. For more details on Wasserstein gradient flow, see Ambrosio et al. (2008); Santambrogio (2015).
Unlike previous studies that rely on PDE-based techniques, our proof is elementary and bears more resemblance to analyses conducted in Euclidean space. Our perturbation analysis is flexible enough to overcome the limitations of existing discrete-time algorithm analyses and thereby im- proves the convergence rate.
The continuous time mean-field gradient flow of (2) is given by
d0, - 5J
Iu, mnl( - T0,dt + v2rdBt,
dw, = (Voj (e Tw,dt + v2ddB))
We apply findings to several applications, including zero-sum games and mean field neural networks, and verify the essential assumptions required to ensure the theoretical convergence of MFL-SDA in these contexts.
(4) Here, 14 and us are the distributions of 0, and wi at time t, respectively. The drift terms V V [Mc. vi](wr) (1 are the Wasserstein gradients with respect to μl and Vi at time t, while (B. (B,), he are two inde- pendent Brownian motions initialized at zero The decay terms T0, and TW, correspond to the second-order moment regularization associated with the KL regularization. To simplify the presentation, we set the scaling factor and the weight decay to be the same the hyperparameter for KI. regularization, corresponding to the standard Gaussian, but our analysis can be easily extended to other choices. The scaling factor 77 > 0 follows from the formulation in Lu (2023), who derived an exponential convergence of (4) to the saddle point.
Sy (ue, ve)(O.) and [ee,
2. Preliminaries
2.1. Problem Setup
Let P(Rda) (resp.. ((Rda)) denote the space of probability distributions on de (resp., Rda) where the entropy and second-order moment are well-defined. Let J P (RRde) ) x P(IR0)) + IR be a convex-concave functional, in the sense that for any distributions μn, R22 E P((Rde) and vn, 1/2 E P(Ida) and any E [o, 1]. the following conditions hold
J(tp) + (1 (1- ()p2) v1) S tJ (m,, v1) + (1- ()2 J(1,, tv + (1 -1- t) 2 (M),)) .1) + (1 - (2).
Algorithm Mean field Langevin Stochastic Descent- Ascent (MFL-SDA)
We consider the following energy functional
((,,)) J= E(H,v)== :
v) + TKL(plp") (LL(<())"<<<((vp")))))
(2)
1: Initialize Mlu Po, K
2: for l = 1 to K - 1 do
where (L(u|p²)) E., log ( (( denotes the Kullback- Leibler (KL) divergence; the reference distributions p² p² are assumed to be standard Gaussian for simplicity, though they can be generalized to distributions with a strongly con- vex potential. The hyperparameter T >> controls the reg- ularization. This setup aligns with Kim et al. (2023) but
3: Ox+1 < O2 7i (V 22 [uk, un (0x) + +0c) + /2m
4: Wk+1 +- wk 12 (a [(wx))[[---- Twk) + 22
ed
5: end for
In this paper, we focus on the discrete-time counterpart of
(4), as outlined in Algorithm 1. In this algorithm, v denotes
3

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
an unbiased stochastic gradient estimator, and & and & are independent standard normal random variables sampled at each iteration k. The algorithm employs dynamics with two timescales, 71, 722 >> O, aligning with the continuous- time updates in Lu (2023) and the discrete-time Fuclidean updates in Yang et al. (2020). Additionally, the updates for y and y are performed alternately, following strategy (2020) for Euclidean spaces. Our primary goal of this work is to analyze the convergence of Algorithm to the saddle point (u* ,)),
To address this, we consider the fixed point of (5), defined
6J 1 [n](w)] 2*(4) exp (r-1
11
ov IM, |,, [n]]
2
where
2*(N) (m)== exp (T [1, K. [n]] (w) 8v
5J
|| 12 ddw
similar to Yang
pdd
2
is normalization constant. It can be verified that 1C, [p] satisfies the following equation of v/:
2.2. Log-Sobolev Inequality
8.1 oy In, ml((w) - |Wl2 T log v(w) = const, Vw,
Unlike minimax problems in Euclidean space, the convex- concave property of the energy functional does not provide immediate algorithmic benefits for gradient-based methods in the Wasserstein space'. Conversely, a more generalized notion, the Polyak-Lojasiewice. (PL. condition, has proven useful for analyzing the gradient flow the distribution space. In Euclidean space, the PL condition facilitates linear convergence rate (Karimi et al., 2016). Extending this notion to distribution spaces leads to the log-Sobolev inequality, which has been employed in the analysis of opti- mization over distribution spaces with MFLD (Chizat, 2022; Nitanda et al., 2022a; Lu, 2023; Kim et al., 2023).
2
where the constant is independent of but may depend on μ. Observe that the above equation is the first-order condition for the problem maKde E(p, 1/. Thus we have
E Ble, K [u
max E(H,v) =: E*). (EP(R
(7)
This will be frequently used in our convergence analysis.
3. Main Results
The goal of this section is to establish the convergence of MFL-SDA (Algorithm 1). Following Yang et al. (2020); Lu (2023), we introduce the Lyapunov function
Definition 1. A distribution satisfies the log-Sobolev in- equality with parameter > 0 if, for all < v, the follow- ing holds:
L(u,D) := (1) + AC2(H,
1
KL(ul)) S Iulp)
(LSI)
where A > 0 is fixed constant, and
2a
(1) max E(H,v) min max M'EP(R (EP() L2(11, == max E(U,v') E), VEP((RA)
E(y', 1/),
where the relative Fisher information T( T(plv) ) is defined as
('EP(3'))
dp 2 de
[mlv) ;- E,,
V log
(8)
Note that L1 and Lg are both non- non-negative and vanish if and only if (u,v) = (n", v²) ") in the weak sense.
2.3. Gibbs Distributions
We begin by stating our main assumptions.
To define the optimizer of the inner maximization in (2), we introduce several Gibbs distributions. We define the Gibbs
3.1. Assumptions
operators K [ and K2 [-] as
We impose the following assumptions. Assumption 1 (Initial condition). The initial iterate (Ho, v0) satisfies F(Jo, 2)) < oc, and the initial third-order mo- ments satisfy E,,, [[]0o] [1), EE, [|] [1 < co.
(7-15) 5J
[M, vi((w) |
[+W() x exp
(5)
5v
5J
1011 (6)
(0) & exp(
--
dy [n, (()
2
Assumption (Regularity of functional J). The functional J(H, 2) is convex in μ and concave in v. The first varia- tions of J have bounded derivatives up to the fourth or- der: | Sy Il ||
When the energy functional v), is bilinear in
and v, Lu (2023) demonstrated that [t] arg (R E(u, v). However, this equality no longer holds when J (14, v) is a general nonlinear functional.
V &d l|r < M. i = 1,...,4, where || is Frobenius norm. Additionally, J has bounded cross second-order variation: 11 lloo < Co. More- over, the Hessian of its second variations are bounded: J
In fact, another notion of convexity, known displacement convexity or geodesic convexity, is more applicable for studying gradient flow in the Wasserstein space (Villani, 1998; Ambrosio al., 2008), which not satisfied in our setting.
& V op ll,, V w opov ll V| V 82
dot ll S C1.
d V. kndv Io. |V 8
Sudu 8o $ Cz.

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Assumption 3 (Log-Sobolev inequality). For any le E P P(Rde), (() the measures Kitt [v]; Ky [n] satisfy LSI with parameter
where fs. depending on the Gibbs distribution K [mg] is only used for theoretical analysis but not in the implemen- tation of algorithm. Moreover, we omit the constants ap- pearing in the higher-order error bounds, whose explicit expressions are provided in Appendix A.3.
We will validate these assumptions in various applications, as discussed in Section 4 and Appendix B.1.
Remark 1. Using Suzuki et al. (2024); Kim et al. (2023), Asssumption 2 implies Assumption 3 with a conservative LSI constant; see Lemma 5 in the Appendix.
3.2.1. BOUNDING (1(++1)) - (1(e)
By definition of C1 in (8) and E* in (7), holds that (1(1x+2) - (1(e) = E* (#x+1) (Ex)) We have the following result.
Remark 2. For simplicity, we assume dg = d3 = in proofs related to convergence rates.
3.2. Convergence Analysis
Proposition Assume Assumptions 1-3 hold. Let in < cT. Then it holds that
At high level, our analysis framework parallels that of stochastic gradient descent-ascent in Euclidean spaces (e.g..
(1 - (1(m)) S ?1 (Ef + V Vloggall
Yang et al. (2020)). However, analyzing the evolution of distributions in our problem presents greater challenges. Specifically, the noise terms El and 4 introduce time- discretization error terms that do not appear in Euclidean problems, even when the gradient oracle is exact. To show that these errors are negligible higher-order terms, most existing analyses leverage the connection between discrete- time updates and continuous-time gradient flow (4) (e-g-, Vempala & Wibisono (2022); Nitanda et al. (2022a); Suzuki et al. (2024); Kim et al. (2024)). In contrast, we directly analyze the tiscrete-time updates and carefully bound the higher-order terms Taylor expansions through integra- tion by parts and the divergence theorem. As will be seen from Theorem 2, our approach is flexible enough handle the stochastic gradient oracle straightforward manner, similar to the Euclidean case.
Epp 1119k fxllB)) +onn
where remainder To is defined in Appendix A.3.
Proposition 1 establishes that the difference Li (M++1) Ci (Hk), or equivalently, E* (2i+1) (1)) is bounded by the squared Wasserstein gradient norm of F. (μ) at jkk- The bound consists of two dominant terms, corresponding to the squared norm of the partial Wasserstein gradients of E (p,, KC, [44)-an an equivalent form of E (u)-with respect to the first and second arguments of the energy functional E. The first term arises from the outer minimization problem in (2) with respect to p. while the second term serves as correction due to the inner maximization in (2) over v. This result parallels the convergence analysis in Euclidean space (Yang et al., 2020). However, obtaining the O remainder requires significant effort, as it involves analyzing the smoothness of the functional E (J),, which, in turn, de- pends on the smoothness of the operator XC, [u]; see Lemma the Appendix for details.
Below, to illustrate the main idea, we first present the conver- gence analysis of MFL-DA, where the algorithm has access to exact gradients, then extend our results to MFL-SDA in Section 3.3. Observe that
3.2.2. BOUNDING 12(M8+1,M++1) - (2(
((H6+1,P4+1) L(HE, vk)
By definition, we have
-LI(U++1) - (14x) X(22(HE41, U1+1) C2( vk)).
C2( - L2( uk)
In the following, we bound the two terms L1 (1x++)) L1 (px) and C2(Pk+1, 1 C2(KR, 2k) in Sections 3.2.1 and 3.2.2, respectively. Once these bounds established, sum them over all iterations and apply telescoping argument to derive the overall convergence rate in Section 3.2.3.
= =(E*(M++1) - E (Hx)) + (E(Kk, (k) - E(Hu+1,, vw)).
We have already established an upper bound on the first difference above in Proposition 1. It remains bound the second difference.
Lemma 1. Assume Assumptions 1-3 hold. Then we have
E(px+1, #x-1) E(ux+1,
To simplify the presentation, we define
2 no [1|/ - TV log ux |2 - 12n2
8J
gk = V
5jz
Luk, (0x( + +0ks
Similarly, we have
8J
E(ux+1, vK) - E(H vk) S 7/2 E Illg + log pa 1ll +Im7 Here, the remainders D1 and T2 are defined Appendix A.3.
ha V
du | un vw)((w) TWh:
8JJ
f& V
[m,, K [(x] T8K
84
5

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
This lemma provides a lower bound on the per-step objective improvement for the inner gradient ascent and outer gradient descent in solving (2). The leading terms in both bounds correspond to the squared Wasserstein gradient norm with respect to Uj and (A,, respectively. The Onni)) and ((g) bias terms arise from time discretization and are consistent with the results of Nitanda et al. (2022a) for distributional convex minimization problems.
small, then the remainder rg4. T' in Appendix A.3 caused by the fourth moment has max (O()) 7?2) scale. Sub- stitute into To, I1, we can get an estimation of these bias term: To = max(O rd, r2d², 1/ } T1(2) = max (O(1),d,, xd²} Replace them into R1 we can get a worst bound R = O (ann)))))))))))) ). Let R = e, then choose 1/1 = 0 0(=220") get a sample complexity K = O log ! This complexity matches that of MFLD for distributional convex minimization (Nitanda et al., 2022a) and the outer- loop complexity of discrete-time MFL-ABB (Kim et al., 2024), and the sample complexity K = O Cي log ! in (Nitanda et al., 2022b) who discussed about discrete- time MFLD in the single minimization problem, the higher order of T, a because the two-timescale optimization scheme in minimax problem, hence the efficiency of this algorithm mainly depends on the slower part, which is the descent part in our paper.
Using Lemma and Assumption 3, the following result is immediate.
Lemma 2. Assume Assumptions 1-3 hold. Then we have
(2(1 s (1 2ngTai vk) + T2122
Using the bound in Proposition and combining Lemma and Lemma 2, obtain the following bound the differ- ence between C2 (p (641) and C2 vk)-
Comparatively, in the Euclidean case, the (exact) gradient descent-ascent method (Yang et al., 2020, Theorem 3.1 with = 0) achieves linear convergence rate of O where the bias term is absent. This is because, in the Euclidean setting, higher-order terms in the Taylor expansion can be absorbed into the first-order squared gradient norm, result- ing in a contraction of the Lyapunov function. However, in our distributional case, the randomness introduced by Gaus- sian noise prevents the absorption of higher-order terms into the first-order term, leading to a sublinear convergence rate. Remark 3. Similar to Lu (2023), we can also consider the Lyapunov function L3(v) + XL4(H, v), where
Proposition 2. Assume Assumptions 1-3 hold. Then we have
C2 Mk+1) S
(1 (1-222Ta) (C2(HR: vx) + m Em I11gx + V log M
1!1 Ep fllfk + V log 1 [12] +
"
Bp [119k - fxll2]
2
2
+ +1'2122 + (1 Ta) + Tommi
Combining Propositions 1 and 2 yields recursive bound on the Lyapunov function L.
C3(v) max min VEP((R)) (PP())))) L1( E(u,v)- min ('EP(RdA)
E(p',v), E(H',v') #'EP(E)))
min
3.2.3. CONVERGENCE OF MFL-DA
E(p',
By applying Propositions and 2, and using an argument similar to that in the Fuclidean case (Yang al., 2020), we can establish the following convergence result for MFL- DA. Note that different learning rates 1/1 722 are employed to ensure convergence, as is commonly done (Yang et al., 2020; Lu, 2023).
which useful for max- problem. The result is similar to Theorem but with reverse scaling of mn and 1/2-
3.3. Convergence of MFL-SDA
Theorem 1. Assume Assumptions 1-3 hold. Set 7 < 20T 1 M I c 122 S 1 and m) = min(2.0.2. Ta Tamp then Zra
In the previous subsection, we assumed the availability of exact gradients. In practice, however, we often work with stochastic gradients, where the exact gradient is replaced by an unbiased estimate. Thanks to the similar high-level structure of our analysis to the Fuclidean case (Yang et al., 2020), our results can be extended to the stochastic gradient setting in a straightforward manner. We can show that the convergence rate of MFL-SDA is analogous that of MFL- DA, with the same geometric decay rate and bias term. The main difference is that the bias term now depends on the higher-order moments of the stochastic gradients.
holds that
L(pK,UR S Ta) K C(po, vo) + RI, (9)
where Ri X(Tan3+ 20 +
Theorem demonstrates that the Lyapunov function C(u, v) converges to bias Rj at geometric rate. This geo- metric decay aligns with the exponential decay observed in the continuous-time time case, as established by Lu (2023). The bias term R,, which results from time discretization, is of order (m,) ). To assess the algorithm's 's complexity, since in practical algorithm we often assume T, 7h, 7/2 is
Assumption 4 (Bounded moments). There exists Ç 2 0 such that
E E11@ - lell" | uk], Ellha - 1ull1 M6]56 SC
6

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
We have the following result for MFL-SDA analogous to Theorem 1.
established that the stochastic MLF-AG achieves con- vergence rate of 0(c-1-0(a")) in terms of the squared I-Wasserstein distance, where a is the LSI constant in As- sumption 3. Since W2 upper bounds W1, Corollary 1 im- proves the existing complexity bound for stochastic MI.F- AG, particularly when the log-Sobolev constant a is small. Notably, it surpasses the conservative a = O(1/d) bound established in Proposition 3.2 of their paper.
Theorem 2. Under the same setup in Theorem 1, and assume further that Assumption 4 holds. Then we have
E E[C(UK ux)] s (1 20) K L(po, vo) + R2: where R2 Alfrn +11 (115+++11221000 2f ( +foof)+ff with fo, fí, 7i
I22 defined in (17), and the expectation is taken over the randomness in the stochastic gradients.
4. Applications
This result demonstrates that the convergence rate of MFL.- SDA (Algorithm 1) is O log 4). This rate is nearly op- timal when compared to the O convergence rate of stochastic gradient descent-ascent for minimax optimiza- tion with two-sided PL condition in Euclidean space, discussed in Yang et al. (2020).
4.1. Zero-Sum Games
Zero-sum games are widely applicable in economics, oper- ations research, and reinforcement learning. These games involve payoff function G)),w), which defines the interac- tion between two players' strategies 0 and w. While finding pure Nash equilibrium can be challenging or even impos- sible when G' is nonconvex-nonconcaay librium (MNE) often exists. In an MNE, players optimize their mixed strategies, represented as probability distribu- tions over available actions.
mixed Nash equi-
Proof Sketch. Let Hi be o-field generated by the ran- dom gradients up to iteration k - 1. Similar to the Eu- clidean case, at iteration k, we analyze the impact of using stochastic gradient oracles on the bound [[ Pk++1) XR] L(M,, By controlling the second- and third- order moments of the stochastic gradients, we ensure that the convergence properties established in Section 3.2.3 re- main valid, albeit with additional error terms. Specifically, thanks to the unbiasedness of the stochastic gradients and the moment bounds in Assumption 4, the error term intro- duced by stochastic gradients is (17²) or higher order. This holds for both the squared gradient norm and the entropy regularization. By carefully bounding these error terms, show that the overall convergence result holds with modified remainder term that accounts for the inexactness of the gradient.
Following Lu (2023), consider a bilinear distributional min- imax optimization problem, where the strategies of two players are represented by probability distributions μ E Pi and v/ E P2. The energy functional (H,, which captures the expected payoff, is expressed as
J(H v) EG
(10)
The goal is to find an MNE (f²,,²) that satisfies p* E arg mingep, E(H,,") and V² E arg max E(a".v) .v). This formulation extends the classical minimax problem to a distributional setting, where players optimize over prob- ability measures rather than deterministic strategies.
Furthermore, leveraging the connection between the Lya- punov function and KL-divergence, we can also obtain con- vergence rate in terms of KL-divergence to (14", ,,²) and further in terms of Wasserstein distance.
Example (GAN). Consider the following generative ad- versarial network with an integral probability metric:
min max (EP() FEF
[E,I Epaaca [f]].
Corollary (Convergence in KL-divergence Wasserstein distance). Under the same setup as in Theorem suppose that Ktt [p] and K2 (v] satisfy LSI with constant 0n, then it holds that
where Pdata is the real data distribution, μ the distribution of the generated data, and I is a discriminator function. Sup- pose that the discriminator function f is parameterized by Suffnite-widthh two-layer neural network with an activation function a(, w) parameterized by w under the mean-field scaling, so that every function f E F can be expressed as
2T (W3(p), W2(KR, x²))
a1 < <<(KL(uk|m*) + KL(Ux(U") (n)) I (1-m)aa) K QC(Ha, vo) + +QI1
f()) = Eu-olo
Then the generative adversarial network can be formulated as a distributional minimax optimization problem with
where Q (1 (1+(6 ( ) and W2 denotes the 2- Wasserstein distance.
J(H v) = R, [R (0(( [0] Epraca [R (0 w]]]]
Similar to Remark 1, Assumption 2 implies a conservative upper bound on the LSI constant 01. Kim et al. (2023)
which a bilinear functional.
7

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
The bilinear nature of the functional J simplifies the analy- sis, as the Wasserstein gradients are given by
Example 3 (Feature-based Policy Learning). Feature-based decision-making (Yang et al., 2022) aims to find policy f from set of features X to action f(X). Given data set 2 = (X,Y) ~ D, where Y is some exoge- nous random variable, the goal is to minimize the ex- pected loss Ex(e(f(X), Y),, subject to feasibility con- straints Af(X) S for every X. By introducing La- grangian dual function g(2) = gXX), this problem can be formulated distributional minimax optimization prob- lem with the objective
8J V
[e, v/ = - VoG(O,w))
6u 8J
dv [4,21 = EennullV.vno EeGG(V]
and the Gibbs distribution K [o] satisfies the first-order optimality condition of the inner maximization problem in (I). Under mild regularity conditions on G, we can verify that Assumptions 2-3 are satisfied.
g(f.g. (.f.g. + 2) b).
Proposition 3. Assume the payoff function G satisfies that F G, i 0, ...... 4. Then the functional J in (10) satisfies Assumption 2, and Assumption 3 holds with
We introduce regularity assumptions on F and ø1 02 which implies Assumption 2.
exp(2G6r-T)
Assumption 5. The function F(x,, y) is convex-concave, L-smooth in both x and y, and has bounded deriva- tives (i.e., || ll F I Fi). Moreover, we assume that 01, og has bounded gradients up to fourth-order, i.e., | VV S m, 0, 0.
4.2. Mean-Field Neural Networks
Consider functional minimax problem
min max (F-D)
(11)
Under this regularity condition, we can also show that the Gibbs distributions K [v] and K., [n] satisfy the log- Sobolev inequality, which verifies Assumption 3.
where I and are functions of a variable 2. The objective function convex in I and concave in g, and the expec- tation is taken with respect to ~ D. We parameterize and g as mnfnite-widthh two-layer neural networks with activations σ1 and 02 respectively:
Proposition 4. Under Assumption 5, (12) satisfies As- sumption 2. Meanwhile, for J(, defined in (12), we huve K [M] E I.-((Rda) and Kz E (= and they both satisfy the Log-Sobolev inequality with parameter
f()) =
g(=) = Fuwrloo2(us =)]-
01 exp(2Fimort
This transforms the original problem into minimax prob- lem in distributional space:
5. Conclusion
In this paper, we establish an Ö(1/e) last-iterate conver- gence guarantce for the Mcan-Field Langevin Stochastic Descent Ascent (MFL-SDA) algorithm. We also explore several common applications. including sero-sum games and mean-field neural networks.
min max E.-D (ai 0)], B w)], =)]-
(12)
Example 2 (Functional Conditional Moment Equations). The conditional moment equation is a fundamental prob- lem in econometrics and statistics. Given dataset = = (X, Y) ~ D. the goal is to find a function f that solves the following functional equation involving the conditional distribution of X given Z:
There are several directions for future research. First, in practical applications, the MFL-SDA algorithm often re- quires finite-particle approximation, which calls for further analysis to establish iniform-in-time propagation of chaos. To address this issue, our analysis can be combined with the techniques from Chen et al. (2022); Suzuki et al. (2023; 2024); Nitanda (2024); Kim et al. (2023). Second, while our results apply to a broad class of nonlinear functionals, more specialized analyses for specific functionals-such as bilinear forms or convex-concave functions of expectations- may lead to sharper convergence guarantees. Lastly, current algorithm follows a two-time-scale framework with relatively large time-scale ratio, in line with Yang et al. (2020); Lu (2023). remains an open question whether a single-timesent approach could be advantageous in certain settings, as highlighted in Wang & Chizat (2024).
Eyix (X(( X x]=====0 = 0. Vx,
where & is a known function that is convex in f. Examples of & include conditional moment equations in nonparamet- ric instrumental variable regression, policy evaluation in reinforcement learning, and asset pricing models in finance (Zhu et al., 2024). Using a Lagrangian dual function g. this problem can be formulated distributional minimax optimization problem by setting g(z) g(X) and
F(f.g,2= = (1..g,2=ggb/6 ().
8

---

Convergence of MFL--GDA for Distributional Minimax Optimization
Impact Statement
Hu, K., Ren, Z., Siška, D., and Szpruch, t. Mean-field langevin dynamics and energy landscape of neural net- works. In Annales de I' l'Institut Henri Poincare (B) Proba- bilites et statistiques, volume 57, pp. Henri Poincaré, 2021.
This paper presents work whose goal is to advance the theo- retical understanding of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Institut
Jin, C., Netrapalli, P., and Jordan, M. What is local optimal- ity in nonconvex-noneoneav minimax optimization? In International conference on machine learning, pp. 4880- 4889. PMLR, 2020.
References
Ambrosio, L., Gigli, N., and Savaré, G. Gradient flows: in metric spaces and in the space of probubility measures. Springer Science & Business Media, 2008.
Karimi, H., Nutini, J., and Schmidt, M. Linear conver- gence of gradient and moximal-gradien methods under the nolyak-tojasiewicz. condition. In Machine Learn- ing and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part I 16, pp. 795- 811. Springer, 2016.
Arjovsky, M., Chintala, S., and Bottou, L. Wasserstein gen- erative adversarial networks. In International conference on machine learning, pp. 223. PMLR, 2017.
Bakry, D. and Émery, M. Diffusions hypercontractives. In Séminaire de Probabilités XIX 1983/84: Proceedings, pp. 177-206. Springer, 2006.
Kim, J., Yamamoto, K., Oko, K., Yang, Z., and Suzuki. T. Symmetric mean-field langevin dynamics for distributional minimax problems. arXiv preprint 2rX1v:2312.01127,20000 2023.
Cai, Y., Mitra, S., Wang. X., and Wibisono, A. Convergence of the min-max langevin dynamics and algorithm for zero- sum games. arXiv preprint arXiv:2412.20471 2024.
Chen, F., Ren, Z., and Wang. S. Uniform-in-tine -imttm propaga- tion of chaos for mean field langevin dynamics. arXiv preprint arXiv:2212.030500 2022.
Kim, J., Yamamoto, K., Oko, K., Yang, Z., and Suzuki, T. Symmetric mean-field langevin dynamics for distribu- tional minimax problems. In The Twelfth International Conference on Learning Representations, 2024.
Chizat, L. Mean-field langevin dynamies Exponential convergence and annealing. Transactions on Machine Learning Research, 2022.
Lascu, R.-A., Majka, M. B., and Szpruch, L. Entropic mean- field min-max problems via best response flow. arXiv preprint arXiv:2330.003033, 2023.
Chizat, L. and Bach, F. On the global convergence of gradi- ent descent for over-parameterizze models using optimal transport. Advances in neural information processing systems, 31, 2018.
Li, J., Zhu, L., and So, A. M.-C. Nonsmooth nonconvex- nonconcave minimax optimization: Primal-dual balanc- ing and iteration complexity analysis. arXiv preprint urXiv:2209 10825, 2022.
Daskalakis, C. and Panageas, I. Last-iterate convergence: Zero-sum sum games and constrained min-max optimization. arXiv preprint |rXiv:1807.0e4. 1807.04252, 2018.
Lin, T., Jin, C., and Jordan, M. On gradient descent ascent for conconvex-concatt minimax problems. In Interna- tional Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Doan, T. Convergence rates of two-time-scale gradient descent-ascent dynamics for solving nonconvex min-max problems. In Learning for Dynamics and Control Confer- ence, pp. 192-206. PMLR, 2022.
Lu, Y. Two-scale gradient descent ascent dynamics finds mixed nash equilibria of continuous games: A mean-field perspective. In International Conference Machine Learning, pp. 22790-22811 22811. PMLR, 2023.
Domingo-Enrich, C., Jelassi, S., Mensch, A., Rotskoff, G., and Bruna, J. A mean-field analysis of two-player zero- sum games. Advances in neural information processing systems, 15:20215-20224 2020.
Ma, C. and Ying, L. Provably convergent quasistatic dy- namics for meen-field two-player zero-sum games. In International Conference on Learning Representations, 2021.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial networks. Communications of the ACM, 63(11): 2020.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. Towards deep learning models resistant to adversarial attacks. stat, 1050(9), 2017.
Holley, R. and Stroock, D. W. Logarithmic sobolev inequal- ities and stochastic ising models. 1986.

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Mei, S., Montanari, A., and Nguyen, P.-M. A mean field view of the landscape of two-layer neural networks. Pro- ceedings of the National Academy of Sciences, 1 115(33); E7665-E7671, 2018.
Archive for Rational Mechanics and Analysis, 143(3): 273-307, September 1998.
Wang. G. and Chizat, L. An exponentially converging parti- cle method for the mixed nash equilibrium of continuous games. arXiv preprint 2a..vv:22110022800 2022.
Nitanda, A. Improved particle approximation enror for mean field neural networks. arXiv preprint 15577 2024.
Wang, G. and Chizat, L. Open problem: Convergence of singletimeseetn mean-field Langevin descent- ascent for two-player 7ero-sum games. In Proceedings of Thirty Seventh Conference on Learning Theory, pp. 5345-5350.
Nitanda, A., Wu, D., and Suzuki, T. Convex analysis of the mean field langevin dynamics. In International Confer- ence on Artificial Intelligence and Statistics, pp. 9741 9757. PMLR, 2022a.
PMLR, June 2024, ISSN: 2640-3498.
Wang. Z., Gao, R., and Li, Neural-network mixed logit choice model: Statistical and optimality guarantees. Avail- able SSRN 51 5118033, 2024.
Nitanda, A., Wu, D., and Suzuki, T. Convex Analysis of the Mean Field Langevin Dynamics, February 2022b. Ttt1:2201.10466 [cs, math, stat].
Yan, Y., Xu, Y., Lin, Q. Liu, W., and Yang, T. Optimal epoch stochastic gradient descent ascent methods for min- max optimization. Advances in Neural Information Pro- cessing Systems, 33:5789-5800 2020.
Otto, F. and Villani, C. Generalization of an inequality by ta- lagrand and links with the logarithmic sobolev inequality. Journal of Functional Analysis, 173(2):361-400, 2000.
Santambrogio, F. Optimal Transport for Applied Mathe- maticians: Calculus of Variations, PDEs, and Model- ing, volume 87 of Progress in Nonlinear Differential Equations and Their Applications. Springer International Publishing, Cham, 2015. ISBN 978-3-319-20827-5 978- 3-319-20828-2.
Yang. J., Kiyavash, N., and He, N. Global convergence and variance reduction for a class of snnconvex-nonconcann minimax problems. Advances in Neural Information Processing Systems, 33:1153- 1165, 2020.
Yang. J., Zhang, L., Chen, N., Gao, R., and Hu, M. Decision- making with side information: A causal transport robust approach. Optimization Online, 2022.
Sirignano, J. and Spiliopoulos, K. Mean field analysis of neural networks: A law of large numbers. SIAM Journal Applied Mathematics, 80(2):725-752, 2020.
Zhang, S. and Hu, Y. Avoid overclaims: Summary of com- plexity bounds for algorithms in minimization and mini- max optimization. In The Fourth Blogpost Track at ICLR 2025, 2025.
Stam, A. J. Some incqualities satisfied by the quantities of information of fisher and shannon. Information and Control, 2(2):101-112, 1959.
Zhu, Y., Zhang, Y., Wang. Z., Yang, Z., and Chen, X. A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascee for Functional Minimax Optimization, October 2024, arXiv:2404. 123122204.12312 [cs].
Suzuki, T., Nitanda, A., and Wu, D. Uniform in prop- agation of chaos for the mean-field gradient langevin dynamics. The Eleventh International Conference on Learning Representations, 2023.
Suzuki, T., Wu, D., and Nitanda, A. Mean-field langevin dynamics: Time-space discretization, stochastic gradient, and variance reduction. Advances in Neural Information Processing Systems, 36, 2024.
Tao, W., Li, W., Pan, Z.,, and Tao, Q. Gradient descent averaging and primal-dual averaging for strongly convex optimization. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 9843-9850, 2021.
Vempala, S. S. and Wibisono, A. Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices, March 2022. arXiv: 1903:099000000 [cs, math, stat].
Villani, C. On a New Class of Weak Solutions to the Spa- tially Homogeneous Boltzmann and Landau Equations.
10

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
A. Notation and Definition
A.1. First-variation of functional
Let be a functional on P(Rd)) + R. its firstvariation for all P(IRde)
by [ at fa is defined as a functional P(Rde) - RR satisfying
d [[ + c(v -1) S 6J (n)(0 pddd. 8y
lim c-0 de
(13)
The first-vaiaaion 3 [n] is unique up an additive constant, and for simplicity, we let Se 8n ju]dp J(... For example, the first variation of F(4)= Je fdp with respect to μ is exactly f.
83
The convexity of J can also expressed via its first variation, i.e. for all v E P(RRo)):
J(v) 2 J(m) + / 8J W (d))
(14)
5p
And if concave if J is convex.
A.2. Tensor representation
For a function fxx) R2d R. consider its Tayler expansion, we may denote the twice and third order derivative 2 f(x) E Rddd and V fxx() Rxddd as s tensor. i.e.
0 f(z) 0x,0x,"
(V')(=)) f2(())
(v)f(z))
(15)
02,0r,00x
And the inner product with vector can be defined as
(V'[(s) - - [V ()) [V(())))))))))))))))))))))
(16)
igik
A.3. Constants
In this section, we explicitly define the constants that have been used in the main content:
M2+ T 1/2
M3
C₁C2 1/2
To =
2
g4
+
6
(m
3/4
94
+ Grdr g4 + M2T/2+ 2d
1/2, 94
+M4 (ni
+ 4n 1// mi
3/1
12dm 1/2 +8/2mg73 5/2 1/2
4m ddd
gt
r1
M2
2
r g4
1/2
+
Ms
(12
3/4
+
6rdr
1/4 (M2 (
g4
C 1/2
l94
+ Mn 91
+
+4v
3.5
mir
3/4 + 12 1/ + 12
5/2 1/4
Tgt
+
T2
M2 + T
2 h4
1/2
M3
(112T4
h4
3/4
+ Grdr
1/4 h4
+ (M2 + 247
C1 1/2
2 Thhh
+ (T + 4v 2
m
3/4 + 12dn TT 1/2
+ 8 3/2 5/2 1/1
+ + 2)),
The
where constants Tg4, Tha defined as
2nd <1
16r 2d)),
'94
= 8M +
2nd (+ (8 16 +2))).

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
The above constants used in the proof of Theorem 1, and the following constants are used in the proof of Theorem 2:
To M2 +
R
M3
m
R
+ + M2
C₁C₂ R1/2
91
91
+ M4 Ry4 + 44/21/
3.5 7
m
3/4
R2 482mm 3/2 5/2 R3g 4n/ 2)),
P1
M2 + 121/
M3
3/4
+rdRR
(M₂ (M2+r)
M
C1 p1/2
6
2
(17)
+ Ma 94 + 4v
2m
3.3
1/2
mi g4
+ 12 /// /4 + 8 5/2 2//4 + 4127 4
Ry
d + 2)),
2
M2 T T R4
M3
112
R
R3/4
+ GrdR + (M + +) M47 +
Ci
n1/2
6
2
MM Rus 2
3.5 1/2 mi R4 T /
3/2 3/2 R + 4 2 2)),
5/2
2/4
where constants Ryt, R&4 are defined as
= + +
(,, 16r² 2d))),
+ (( 2rd (
RM
+ 15M +B+ (112) 16 + +2d)))
B. Preliminary Results
B.1. Log-Sobolev Inequality
In this section, we present some sufficient conditions for ensuring log-Sobolev inequality from the existing literature.
Lemma (Bakry & Emery (2006)). If Rd IR is a function and 2 f 'c aT, then the probability density p xx exp( - satisfies LSI with constant
Lemma 4 (Holley & Stroock (1986)). Let p be a density satisfying LSI with constant then for bounded function
B B:Rd Rdd + R. the perturbed distribution
dpn(x) = exp( exp(B(x)))ot da,
(18)
Epp (exp( (x(x]
satisfies LSI with parameter exp(-(sup B - inf B))a.
11012 with /hil S M1
Lemma 5 (Suzuki et al. (2024); Kim et al. (2023)), Let the probability measure i exp(-r-1 then satisfies LSI with constant
e V a
a
4M2
2d V
4+
( + va)²
Mi
4M (2 (2+ d+
2
72
B.2. Technical Lemmas
Lemma 6. Let be probability density and let be its convolution with normal distribution N (0, cl), then
Epllog p.] S Epllog (p) -
where (() is Fisher information of p. and C is a uniform bound on the Hessian log
Proof of Lemma 6. Define h 14 + RR as
h(c)) Ep, (log pe).
Then by de Brujin's s identity (Stam, 1959), we have h'(e) [(pe)) I 0. Based on the data processing inequality, ((p))
nonincreasing in and hence 1' is nondecreasing. This establishes the convexity of h, and arrive at
h((e) < ((()) + c0) + Ce?
which yields the desired result.
12

---

Convergence of MFL--GDA for Distributional Minimax Optimization
Lemma 7. For measures Vk-1, Mi defined in Algorithm we have
H((++11) -H((v)) 2 1/2 Ev [| 1o 1/2 B2 1040 VV VV uz)l Ō(TT))
(19)
Similarty, for Pk-11 1 Pk. have
TH(u4) TH((x+1)) - -122 [|| log uel - Bu M9rk : TV log ux)) Ö(TT)).
(20)
where Ö(Tn))) (M2 + T)? /2 2d2 2 + Crnū.
Proof of Lemma 7. We first prove (19). Let Px+1 be the distribution of @k+1 = T(w)) with T(we) = w/ + 1244 and We ~ Vk- With this definition, we can decompose H(px) H(ux-1) into the sum of the following two terms
Beu+1 [log Pk++]] + Reg [log mx]
and Bp Dog Uk+1] Bea+ [log vn-1]-
(21)
Note that T is invertible for 1/2 I 1/M2. By the formula for change of variables, we arrive at
E Dog uk+1]
Uk+1 (Wx+1) log Uk+1 (# )d
M (T(w)) log PA+ (T(w))) (et(VT
(22)
Vk (wx) log un (wx) / vx(ww) log det (T((w)))
Ev, [log vn] Evg [log det (VT]]]
Hence, the first term in (21) becomes
Eo, 11 [log PR+1] + Exg, (log un]
= Eug (log] | dee((VT))
Ev [log det 7/2 Vhy,
Bug (Tr(112 Vhn(ww)) (V /2)]
(23)
2 1/2 Bur, V h1] (M2 + n//
72 Eyy (1E, V log (M2 + 122
Here, the last equality follows since
/ us V hudw ha Vendw -Eve [(hx, V log vn))-
Eug
V hp]
(24)
Note that 1k+1 equals the convolution of 1 and a Gaussian distribution ((0,, 21) By Lemma the second term in (21) can be bounded by
T (E log 11+1]
E
[log vx+ 2 E2, [|] log ux [|2] (TE, ||| V log 1x Er,,, [|| log D (1)), (25)
where the last term the right-hand side can be further bounded by
/ Ph++ | log Pk+1 |d
Ep V log P4+1 12
/ vx log uA (wse)
log det (T((w)
(26)
Ey, | log 11]
2
v log u T V log det (w)))
Ey,
V log PA [2]
2112 sup A gb (wx). we
13

---

E(H',)), Convergence of MFL.-GDA for Distributional Minimax Optimization
Here, the last inequality follows since
/ (u((W>) Vlog (W)((V((
/ Vk (W()))()log) det( (T()s) )) )dws
/ ve(wx))(tr(na hy (hx(
(27)
n22 / (a(wx))² 5J dv
| U (wy dwo..
Since h2 M4, holds that
Ta (E [I| log - Ep.., [|| log 11))) S 2d M4T
(28)
Combining these terms together we then obtain the desired result (19). Finally, note that (19) and (20) are symmetric, Hence, (20) can be proved using similar technique and we omit here for brevity.
Lemma 8. For any ((TRd)) and E P(TRda), ) the following inqualities hold:
=KL(ulm") S Li()) K (Kt [+])) TKL(v/CT [n]) - (2(1,)) S +KL(w/K5(u))
Proof of Lemma 8. We start by establishing the lower bound and upper bound of L2 via KL-divergence. Specifically,
(2(U, = rKL(ul0") *KL(Kt(All'') + J(u - (14
2 TKL(vlp") - TKL(KE wille") f
8J ju, K.t [w]]d(w xt((w)
du
2 =KL(U/KT Iw]),
(29)
(2(M,)) *KL(ul0") AKLLCTIAAA + (()) J(H,2)
S TKL(')0") =KL(Kt I 0J (u v)
S <KL(UIKCt (n)).
The inequalities is consequence convex-concave property of functioinal J, see Appendix A.1. To prove inequalities of C (p), we first need a symmetric functional of L1, C2, named L3, C1 defined by
Cs(v): = max min (EP(R"A) ()((Re)
E(H', MEP(R(O)
min
(30)
CA(U,v)= = F((
min #EEP(R
By the same technique as in (29), we can verify that
C4(H,)) *KL(H(K,]P))
(31)
Then we arrive at
(((p)
max ()P((R max (EP(RAD)
E(u,
min max (R(())))
Elg' v')
E(H,V') - min ('P((R)))
E [n])
K( (u])
min (
Elp' E(p',Ct((l) (n])
(32)
=
S STKL(HING
14

---

Convergence of MFL--GDA for Distributional Minimax Optimization
The inequality is since fixed the value of second term in E. It remains to establish lower bound for (1). To this end, note that
log 2" 2aaaa1 + (1-a))ul
(f /exp/ (af=120)
J [mn]] + | exp (1- aa) f -- Juz 1ot [12l] + | (2d dw
loog
Jun KC
5v
ōv
S log (f exp ( +-1
dv Jun 10 [mn]] | dw (fexp (fr1 Juu, K.: [ezl] + | dw 1-0
6
a log 2 [111]] + (1 - x)) log 2" [u2),
which verifies the convexity of log z". Then obtain
(i(M) = (H) E (N²)
- (H((K) - -H(x")) + Tlog 2'(4]
-log 2 3114"1)
2r ( log log pddy - - / log logu"cy''
-
6 ólog 2 2²
d(p 11")
(33)
(f log udd
/ log do"""du"
/
log(n log(a))d(u 1²)
TKL(m)A"),
where the first inequality follows from the convexity of log Z Hence, we complete the proof. Lemma 9, Given P. n² P(IRde),, can obtain
1
||
82J ôpór [t,
KL(CCTNTIKCTN)
2a72 BKllun lud
V
K. [i]]d(e' 11)
(34)
Proof of Lemma 9. First, consider
C2(u, KC, (k(T) = E(u, KC, [m]) K(u,Kt(H')
By Lemma we obtain
Se(u,Ct(m1 2
The last incquality follows from the fact that if v satisfies (LSI) with constant a, then it satisfies the Talagrand inequality. Also, we use another side of Lemma 8 we can get
C2(u, KC. (w'I) I KKLCK [n']KK,
KC (a')
27
Ex
kcl [n']
V log
20
Kr₁, KT [ur']]
V 8J
5J
(35)
E
Ext [un]
Wn' xC [n']]
V
ju,
K [n')
2nr
bv
5e
1 EE 2cr
|| Vw 82.
27
li,, xc [ud]d('' 20)
Exctbu) [un]
Combing the above two equation we can get desired result.
Lemma 10. Given Assumptions (2)-(3), we can prove under the algorithm
Exg, (1 ( S Eng [11+)]])]] + Th4s
Epg
[llaa S Eyoo [1 [1 + rg4-
(36)
where Tha, T9 are specified in the proof.
15

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Proof of Lemma 10. Let p (0, Iu) be standard multivariate Gaussian distribution. We first consider the second-order moment, note that
Byg B2 (|wk + 1
Evy |||0|] [/ + 2 @p l(uk 1/2 (h + Twk Twk))] + E,, @plll Twx Tlx)
< |||0|| [|]
+ M,,, ||| 2/12 2122 Ev,, ||| 1121 2n² (MF + [1
(37)
<(1 21/2 + 1/2T
+ 20 E,, ||| [ + 21/ /T + M12
2
<(1 - 7/ Bun w 1| + 7/2 (2M /T + 21)
where the first inequality follows the fact that ||Ae + Twk = 1 2x) (w)(w) S M1, the second inequality is since
2M, EE,, [|| S こ [luxllll)))) + 2M S _B + 2M/ /T and last inequality since 122 < 1/4.
Then we consider the fourth moment,
Eyz+i [|[a++1ll2
=En + n2hk 22
(38)
EE |lwe + n2hxel** (8 + 4d)m2//lws + n2hull2 2 +dd)
Since have prove
Ey llwa 12/1 s (1 122 11 + (222222///222/222
Then
Ev, [|ww + 12hxelll S Ee, - 3322/27 + )) 1awlal//w/ + /
= - 3/22g2 + 1 2 ||/ [12] 22222 3/21/2 + ), || + 12222/ 2))
Then combining them together,
E2, ||
<(1 3/2 + 3 12 4rd 27 ||
(39)
M1 + +8 4d) + (d
<(1 - E || || + (2 27d TH M2) n (8 4d) 1d2 ed +d))
Hence, by iteratively applying this inequality we can get
Ee, [1llwal13 < E2p [| + 72T
72 (2(47 + 2rd M/) "/) + (8 4d) + 2 + 2d)).
Then by (a b) < 8(a + b²) we can obtain the upper bound of fourth moment of gradient hy:
Eeg (1 (En, [1 Twxl1 ||>=ا| |1
<8M/ + 87 (Ez,, ||ا0|||||| + (2(47 + 2nd +
4d) + 16 + +d))).
Denote Th4 = 8MP - 8T ((2(7 + 2rd +
167 2d)))
For Eng [llgg111]]] we can similarly obtain
Epg
11g [1 < E 1 + rg4
where The = 8M+ + 872( + 2rd + / + 1 M + (8 4d) 26 + 2d))).
16

---

Convergence of MFL--GDA for Distributional Minimax Optimization
C. Proofs for Section 3
Proof of Proposition 1. To prove the boundedness of E( KC [(x++ - Elux, K [MN]), we split it into
(E(ue42, [ux+al) E( (mxl)) + (E(uut1,
[ux]) (a(pe))))((((EEEE3333 EC (mx)))
(40)
The second term includes
(((e)) E(uR, K. [mel) = JuK+1, KrT [mxx) - J [Ju, KC. [uel) (Euatz Dogg M6+1l Ex Dlg mel)
(41)
+ (Buutill00s [2] Ey [1|0010x000 (1xx11))
Where the entropy term has bound
T (Epees [lo pk+1] Epg llg px]) $ Ep V log uu 1121 -12 [9rn TV -V log [x)]
(M2+ (
via Lemma Now we consider the weight decay term (Epe+i [110++++11 Enn O1 12]) Let p = NN Ia) be standard multivariate Gaussian distribution, then:
2 PL+1 -E [110121 = E spl0x + 119h + 12 E 11 - 110x1121
T E
T
2
(42)
B 22m (0k.9h) + 1 || + 7
2
And by second-order expansion of J[, v),
J(K+I, KC; [u&]) J(uk, K. [mc])
8J lun, IC. (0x) 6p
+ 2 l
8- dn² lūs Kot (anllo, 0')((R+1 (o))0)d(u++111a) - -m)
(43)
By the fourth-order Taylor expansion with Lagrangian remainder, the first part the right-hand side of (43) becomes
8J
E
pct1
#k
8fc
[kk,
x [px]]
(44)
8J
8J
= E
=Ep
ju KC
(0x T19h + v (
lux, x (Ox)
8y
8JJ
[Mx. K [Mx]lllll.Cc (-mgg + 22m Tgh) >
=EpLOp
[u,,
K
[ux]], m19k + /21
+
(45)
2
ôu
8J
83 ).
[uk KC,
[RR]l. (-MIgh + 2 TE
(46)
6
1
5J TT (-T9gh + T 1844 )
24
E
pu @p
8p
(47)
where we use 0g to indicate the point achieving the equality from the mean value theorem. Since 1Ep(E O, we have
Jy (
8J lux, Kc [ue]], m9.9 + / 221 )} Enu
E.l
[un]], -11.9k )}
Epscoo 000
lues
KJ
(48)
5je
Since
2 od ow ju, w|ll
My for all μ, further have
E Ep (To
jus, xt [uell (mi9 + 22 >}
Tr V² SJ
[p Uk] )
< M2njE,, 111 + 2m T
8q
M2n Ey [11 2m 7 Tl (gg,,
V log (m:)) + 21/1 2d,
(49)
17

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
where the equality follows from (24).
Similarly, can derive an upper bound for the third term and the fourth term:
( (Dosd Öje Lux, K2, [mull. (-mig + / 22)
)
En 20
< Ma Eu Il [ž + 6ní F Il 12)).
and
1u ( Jus Nrt [un]((a))) (-))))(mm9)) -19h (2 I
<Ma Bua 1l + 4v 2n)² 3.5 , 1/2 m2 Br g [12] + 12d1) 7 F, (119n 12) + 2/2mm37
3/2 //21//
5/21, uu Illan + 4 add + 2))
Where my = 22 my = 23/23(())))2 [(d/2)
r(d/2)
The second term of (43) indeed
J
J²J
Lú, KJ -a) (n)
8p2
E Epi-1
lū, KC; (0, me)(o)
Mk
Rd 8u2
82
Bp
E B
k [0,]] (000000000000 (711N 2
8p22
0r 52 J
Ept-1- Mb
Ep 0
E
(i+ Kt | 8' (m + 22 8p2
(50)
Vo 8 J
Epa-1 Mk
Eps
já, K...
[mx 00 mL
8rz²
82_J
Epp
Epp
VoVN
[i, KC, (1x m mgk
< C 11l.91112222))
CiviB |11
Then we analyse the first term F( KC KG by concavity of (p,,) + +H(());
E(ux+1, ((R++1)))) - E( KC, [px)]
6J
<
dz [ux42, Kt [ux]] 1w012 T log Kt [uk]
Kt [ux])
6J
K. [uwll + [
ōvōz 1ū, K.t [u]]dduee mw) ブ =1lu13 log KC. [ue]] a(K, [ua+1] - XC. [mx])
8².
Jun,
Āv
[
{
J2J
[ū, (t. [me]ld(uats (a)dd(Ct(eetti x (mo))
8pōv
(51)
The last equality since 81 [uk, K. [uue]] 3||=11 7 log KT [us]] log (*(u)), which is constant relative w.
18

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Now
82J
[it, KCt [ee]dd[u - - (ma)d(C(((++ - K2T (ux))
2a Ja ōpzv
82
Me Bppti
ōuōr li,, K |uell (1ktt1u K lux)))
Jad
82 J
Ja Bus
Vo
1it [Al]( + V TE( [px+1] - K (uxl)
$ 1n C2 ye
fo++ Kct (mx))
< C2 (11ga111))
KL ((++1))C(((a
(52)
s 22 C2E
1
Bxc Pxctineel [mverl
Vw
uuóv lux, Kc [illd(uut+ - mm)
J2
\
2002
S I V 20r2 17 (lagkl 121)2
n 1/27 C2
Combining these inequalities with the result in Lemma 7, we finally get
Li (1(x+1)) (1u)
niC
m: KKf gh3و 711 TI Kff + ghe log [k)] + 717 2 f V log
mm
11
+ Toni
(53)
2
1/1 Ee fll.fx Vlog ua
7n Enn Illgk fxll21 + Loon,
2
where
M2 +
M3
C1C₂
To
Ey [1lgk
(m Br 11 [12] (T, 1199 [12)) +
E |11gx11
2
6
at/27
2m +M E, [1lgx [1 4v
3.5 7 m2 E,,, 1l 12 12dh) E p.. [llo 1/ 2mm
3/2 2 |119*112| [2] + 2 d(d 2)).
The last inequality is since 7)1 T.. Therefore, complete the proof.
Proof of Lemma 1. By the definition of E, we note that
((18+1,4641) F( uk)
(astei))JJ(Jaae J(H++1, - TKLL(V (L(vkl)") J(H4+1, + =(J(U++1, - (a(e))))))(((H(((())) ((H(UE++) H((vx) + 2/ 11 ||ww+
T
Ev, [|| 112))
Note that the second term H(VR+1) H(vk) can be bounded via Lemma 7. In the following, focus term &E 1 |||a>]]]] 12), Let NN( Ia) be standard multivariate Gaussian distribution, then:
5 E E [1| = E Eu,sppllux + 1224 + 22112222112 - |ww
T
2
2
(54)
T
Bvg (2x, hw) + 1 1/ 11 + ? dd.
2
By second order expansion with functional J (M -), it holds that
6J 5v
1 / +
82,1 frce duz [ub+1, 1 -w
((41)) mb)) E 1
|u++1 (i4++1,,|(uun vul(w))
(55)
Define
5-1
8.J
Ie, viww + 21eeTT)
dv Im, vw(w) = Benp
(56)
dv
19

---

Convergence of MFL--GDA for Distributional Minimax Optimization
By Taylor expansion with Lagrangian remainder, the first part on the right-hand side of (55) becomes
8. 8v [M vxl
Buzti- M vk
(57)
8.1 [ (+x+1))
88J [
=Bou+1
- Ey
( (w)(w))
8v
6v
8J
[8] 8v
-Bvr
| PE)(Wa)
- Eve
1
(58)
óv
8.
lus+1, val, (Teh + v 2 82 }
-EN
8v |MR+1. uol. nehu + 2
(59)
2
8v
3 5J
+ Brs Op
[K++1, uk). (1224 + v 2 +2) (03)
(60)
8v
8J
(()( (122a + 2 04 )
+
Ex 8p
(61)
24
dy
where we use Wy to indicate the point achieving the equality from the mean value theorem. Since Ep = -0, we have
(v
8J 5v
|4++1, uk], nah + v 22 }] Erasso
{
SJ
Mx], n2h1 }
Exp 60p
[1N+11,
(62)
8r
Since
| 6J 8y (r, w|ll < M2, we further have
( (22
8J dr
vel. vel, (12hx + v 22) 02) >1
8J
Ev
[Kx+1,
M22 |1/ [|2] + 2 11
|ux+1 mml)
dv
(63)
M2n1 Erg |1 1 2 (ine, V log uxyi 217272
where the equality follows from (24).
Similarly, we can derive an upper bound for the third term:
(
8J [MR+1; ux], (112h + (2 >}
)
Evg 8
2Ma El 1/ G (11/xll2))-
dv
Plugging in the above incqualities to (57), we arrive at
5J
B MM UK
[16411, uR]
2 7/2 Erg [11/xe1111
1/2 Ber (ik, V log
5v
M2 Eu,, 11 + Ma Ev [1|e [ GrdRen hall)))))) l12))-
21
The second term is indeed
1
82. duz Mux+i, D (d))))))(((++ -w))d(u2+++1 mx) 2 C
Eug |11
(64)
2
Rd
2
which is similar to (50). Combining with the bound of T(H(U)+11) - H(())) as established in Lemma 7, we then obtain
E(pu, 1k+1) - E(uR, us) 2 M2 111 2//27 E.,, [(h,, V log ux)) + 7/27 [I] V log us (12] T2n2
= FF [1 V log u [2] T2722
where
T3 M2 + r Ey, [1
M3
+ 1))) (M₂ + 2) M2T² + C1 E,, l1 18]
Eng [1| + (T Pi 12
2
6
2
+ (T
+ 4v 2 3.5 ,, 1/2 m E., || 1221 +
12d
A 3 + 8 B/22m372///1/ 3/2
5/2 'E, || ||l| + 4n d + 2)).
(65)
where Fy,, 11). 2,3, terms can be further bounded by proposition 10. This gives rise to the desired result.
20

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Proof of Lemma's 2. By definition of K [r], we have
Be, [llb vV log u |1 Eez, [|| V log Ket [Mx] vV log vxll2 = (Tx(( [xx]))
Applying the log-Sobolev inequality for Kp [ex] as well as Lemma 8, we then obtain
72 1 K (ww]]) 2 (L (Pw]) 2 200 C2 (p)+,,
which implies that E,,, 11 Based on Lemma 1,
V log un [1]]] 20T 200 (2
(1++1) E(UR+1,
E" E( 14) + E( - E(px+1: Mk+1)
(66)
S E (ME+1) Pt) M(Hx+1, +2212
= (1 - 202 vx) + +-2722
Hence get the desired result.
Proof of Proposition 2. Lemma 2 shows that
C2( V--1) s 22 T2nE
(67)
([2 uk) + E(Ma, vx) F(Ux+1, + E (ME+1) FF (uxx) T2n2.
By Lemma 1,
Elus, vx) - E( v/) S &. E llla + V log pu [x1 + +Imm.
(68)
By Proposition 1, we further have
(²(4411) Ex (px) S 11 E,, Illff + V log uu 121
71 Ep 11.g1191 fulløl + Poni.
Combining the above inequalities, inequality (67) then becomes
L2 1k+1) < (1 - 21)/T( C2(Uk, vR) + (1 - 2 Byn, By 1119 + V Vlgg 1x - (1 - 22) 171 Ep fll + V log u4 112) + (1 21y
2 Ey,, Ill9 fx l1ă1
(69)
2
+ T2n (1 21/2 Ta) (Ti To)n?
which completes the proof.
Proof of Theorem 1. Combining (53) and (69), we have
11(px=1)+ + (C2(/4+1, < Li (14)) - 7)
(1 + A(1 - (270) [I] + V log (x:1 + X(1
uk)
2
+ X(1 - 70 F,, [l|g V log /4 + (A(1 - 7270) + +1 72
E [llga - fx
2
X( (1 20) (T: ro)n T
(70)
According to the Pinsker's inequality, it holds that (KL() 2 TV v) where TV v) = ||||||1 distance between I and v. Since J has bounded second-order Wasserstein gradients, we have
w/1 1|ll-//11
the total-variation
JJ Juk, KC [un]]]
8J
Epc Illgk fu
V
Lun, mz] dq
dpp s (CTVV((Ct 2CFKL(M [px]),
(71)
which, by invoking Lemma 8, further leads to
20 [ux)) Uz(
E Illgs=
fxll2]
2CPKL(ux
(72)
21

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
By Assumption N [v] satisfies the log-Sobolev inequality with parameter a, and hence,
pp Ill + V log ua
[2] I M [K]] (mx]]) 2 2or (eer"KL( [K] (uxl]) 2 20t (14e),
where the last inequality follows from Lemma 8. Additionally, applying the Young's inequality, we obtain
Ep Il V log pu (2] s 2( [l.fk + V Vlogu118 + Ep, [llax - fx
(73)
Combining the above inequalities then yields
Li(M441) X22 1015(1111 (1- ( (1+ A(1 21p2Ta) + 2,111(1 A(1 2222aa) 204) L (HK))
21(1 212 2C7
+ [A(L - -m2 + (A(1 - 21p + +11 11
L2 C2(N vK)
(74)
+ A(T2m2 + (1 - (T² - -To)mt) + +imi
By noting that
1 - th (1 + A(1 2(pTaa) + 2m - 2m2Taa 2at < maa
since 1 Ta > O, as well as
A(1 21) + (A1( T1) + -1 2A(1 - 212Ta)m) 203
71 (1 2a) + 2m (1 272Taa)
<A(1 21p +
2
2X
<X(1 mT))),
we can rewrite inequality (74) into
(1(++11)+ XC2(14+11, $ -1-maoll ( AC2(Kx, + + (12 + M2M1)m²)++ +T2nf
By recursively applying the above inequality, we then obtain
((ux) S (1 mITa)* + 0(m),
where O(m) x(Tan)+(1 (2T Ms MZ Taan This completes the proof.
ra
Proof of Corollary 1. We proceed by bounding (L(ux)(*) and (L(Px(v") separately, Lemma 8 and Theorem I allow us to bound (L(uxlu)) by
rKL(u=)1() & CI(UR) S C(MR, S (1 mT- L(u,, vo) + Rı (n)).
(75)
In the following, focus on (L(x)(e"). By definition, it holds that
<KL(ux(U") -KL(ux (Kt (ux)) + [ (log(IC) (mx)) log o² "ddex
=KK ACT [Mn)) + S llogKtti [ux] - log "d(gu" - v²) -xC((=((Cct(e))
(76)
<KKL KG (ux)) + / (log Kt [me] - log v* )d(( v²).
By noting that v² = KC [1c*), we then have
log (C log(v") -1 (oJ 8v
8JJ
1ur xct (=txxt((())) ((()))
[r, Ktt [n]]
- (log [mx) - log 2 21(1))
(77)
ov
22

---

Convergence of MFL.-GGA for Distributional Minimax Optimization
And the constant part log 3d [ux] log (n("") equals to zero when integrate over uk V². This leads to
82. ōςóv (H, d(ux - 1 )d(cn - v²)
=KL(vx(2)) & TKL(Px (C, ((x]) +
S rKL(PA (m+]) + Co TV H²) (VKKK
(78)
S =KL(ux/K) (ux) + 2Cp VKL(HRlU*) (KL(us)(*)
+ 20
(KL(PA)p") S FKL 2
KL(Uull")
T
where the second inequality used Pinsker's inequality and the last inequality used Young's inequality. Combining the ahove inequalities we then arrive at
=KL(px/v") S 2TKL(PK/K + 40h
KL(Axle") - (2
40 72
((1 (1-mTra)<C(m)) L(po, vo) + (i(m))
(79)
which yields the desired result. Finally, by Otto & Villani (2000), every v satisfies LSI with parameter a also satisfies Talagrand's inequality with parameter a, where
2 W u) S KL(plu)
a
For any μ..
Proof of Theorem 2. The proof mainly relies distributional update, and take the update of μ as example:
P ((Ia n1 (x)))4))) Ak+1 Mu+11 * pk+
(80)
where (x(',28 is the inexact gradient oracle generated by label 2k, and Pk represents an independent N(0, 2m)
Let Hi the o-algebra generated by {= then conditional on Hr. we have
E[E(14+1, 2.)] - E( Vk) = -(x (((++1, +
(81)
T B || 2
Ab
J (pk, 1%)
2 Bl (11))))) ((((((()++))) H((p))
We can analyze the difference term conditioned on My similar with exact gradient Proposition 1,2 and Lemma 1, Among them, every expectation term of HA zk) would be E[Een [dxc =u Hi = hig by the law of iterated expectations. For the fourth order moments, we first bound
Ey, [ 24) + Twnl 12] < 8E,, [l 24) - hy 1 + SEe, hl + rwwll
(82)
8C SMM.
Then similar to Lemma 10, denoted the distribution of random variable zy be Çx:
Then
Epg [|w + n2 (1. 2 < E., [[(1 3/2 + (MM + (2/2))
(1-3/2172
,) ||| + / 3/21/2 + n3 E (| 1l m/ 22/2222
Then combining them together,
Ex, [||ww]]]
<(1 - 3/20/2 + 2 [|| [1 + 72 - + 2/ 4rd
(,, +
+
[1]
(MG 2212322 + (8 4 T + 222
2d 2d)
(83)
<(1 )27))nn [||~>|11]
- (2(4r + 2nd +1
/1/32 + (8 (M + 26 2d))
23

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Hence, by iteratively applying this inequality we can get
1 T2T
By, [| - Ev, || +
Then by +) 2 8(a + b$) we can obtain the upper bound of fourth moment of gradient h4:
E2, (. 2x) < 8, (+, =wxl12 1/22+ + Tw 112)
<8(M} + 5)+ 8 (,, || [12]]
+ (2(47 2rd n MM + /T nML + (204+++12200 ( (8) (2 +,
2d))).
Denote R44 8(M <) 87 ((2(47 2rd + (M (1 (1 (8 T (MP + (1/)) +
2df + 2d))).
For By 11 12)), we can similarly obtain
E I1lxx 2/ M121 < EuD |1|0/ 12 + Rg1:
where Ry4 = 8(M + () + ((2(4 + 2rd + n (M² + (1 (M + (1 + -8+ 4d) + (122)) + (df + 2d))).
Hence, by repeating the proof process MFL-DA with exact gradients, we can get a result similar to exact gradient one, we give track whole proof process for 1, for first order term as (48), (62),
}
/ 8JJ
(
[UK, K [ux]], -77 -799%) )
(unlllll - 90, (0)22)
Ax = E
5jc
Since Gr, hy are unbiased estimator, hence introduce no error term.
For weight decay terms (52), we have
E
T E 2
[10111]
Hi
= E Bpn (2m (0z: In. (0x; 2x)) + vf1l0x (Ox; zx)1 + + 22d Add A
patt
Ma
- r p 10., gx)] + ?1 72 2d +
T ク T 11lxx
(84)
< T (00 )2 7 2d + T 5 12122
And for second order part,
K
(Fx
(
E
Bussp
[pk, KC. [Hw]]. (ni T(t) 82
H
2mp F.p Ju Tr 22 ŌJ
M ps |1|i
jmk: uk)
(85)
/ |1|ا
[
27 BB K V log [w) | + 27/1 22d
< M2n R
21/1 B (gh. V log [R)] + 2111 22d
Hence, we can get new constants as in (17). Substitute into Theorem we can get a result with remainder R2-
D. Proofs for Section
-=]"² By the Bakry-fmery condition (Bakry & féeer, 2006), v' satisfies LSI with parameter 1. Then according to the Holley-Stroock perturbation principle (Holley & Stroock, 1986), if v and are Gibbs measures with Hamiltonian H and + H, respectively, and v/ satisfies LSI with parameter a', then also satisfies LSI with parameter a 2 e (sup iiint d) a' Note that the first variation of J as defined in (10) equals
Proof of Proposition: 3. Let v' x exp(-
5J [M, (1)) = E2 (G0,ww)
8n
24

---

Convergence of MFL.-GDA for Distributional Minimax Optimization
Then the Gibbs functional becomes
[ = exp (T=,,, - 1|w11 2
Let
||| ((w) - E, H 2
We can verify that sup o inf Φ = 2T 2r-22110 Go. This implies that x [v] satisfies LSI with parameter a exp(2G can show the same conclusion for K2, [u] using similar technique, and we omit here for brevity,
We
15.
Then verify the conditions in Assumption 2. Observe that the Wasserstein gradient of (10)
8J V
8J
dv / G(D,
V VoG((O,)dy,,
V
(86)
8p
both smooth up fourth order since
| S Gú 0, ,..,,..,.. 4. Morcover, since bilinear,
J(H v) - v) = Egg
8J [[, v/) - J(u v) = Esv [1:00
8J
5v 1 ws
(87)
Hence, the second-order term equals zero. Meanwhile, the cross second-vairation which certificating Assumption 2.
G(O, w) satisfies boundedness,
Proof of Proposition 4. Similar to proof Proposition 3, note that the first variation as defined (12) equals
8J
lu, v| = (0t1:///.A...0000......o/oooolld
5v
Then the Gibbs functional becomes
[+t exp (T-1
||w11
Let
w||
2 <(w) = E
We can verify that sup inf 27 Fimo. This implies that K [p] satisfies LSI with parameter a exp(2Fimor 15. We can show the same conclusion for K2 [H]] using similar technique, and we omit here for brevity. Then, we will verify defined in (12) satisfies Assumption
is evident that J is convex in a and concave in v. Furthermore, we note that
V 8p
[u, v)
s Fim.
(88)
And the same for |/V b (M, v)lFF. For second variation term, note that
82
J(GDD)
Lmg.
(89)
Similarly,
82 V.V
dn
J
(14, v)
=
=ED(F" (E,lo1 Ey (1 & Lmm
(90)
F
And similar for 2.
52 VoV.
(1, w)
V dez J (/, w
Hence we has verified all the condition Assumption
0r o
25


Reviews:
[{"review_id": "If6i12LEBG", "reviewer": "Reviewer_eWwv", "summary": "The paper analyzes a Langevin-type scheme for finding equilibria in mean-field games under convexity and smoothness assumptions. The rates obtained scale as $\\widetilde{O}(1/\\varepsilon)$, which agrees with the rate in Euclidean space. An extension to stochastic gradients is also considered.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thorough and constructive feedback. Below, we address your main points raised. \n$\\newcommand{\\bs}{\\boldsymbol}$\n## Addressing Weakness:\n\n**Particle Discretization**:  For this problem, we have verified that our method is feasible in the particle setting. As an illustration, we briefly summarize the adjustments needed in our proof technique under the particle approximation setting:\n\nWe set the joint distribution $\\bs\\mu,\\bs\\nu$ as $N$ finite particles $\\bs\\theta=[\\theta^i]^N_{i=1}$ and $\\bs \\omega = [\\omega^i]^N_{i=1}$. In this case, the LSI has the form adapted from [1, Lemma 7]\n\n$$\n  \\frac{\\tau^2}{N} \\sum^N_{i=1} \\mathbb E_{\\bs\\nu_k}[\\\\|h_i(\\bs\\omega_k)-\\nabla \\log \\bs\\rho_k(\\bs\\omega_k)\\\\|^2_2]\\geq 2\\alpha \\tau {\\mathcal L_2^N}(\\bs\\mu_{k+1},\\bs\\nu_k)+O(\\frac{1}{N})\n$$\nwhere $\\bs\\mu_k$ and $\\bs\\nu_k$ denote the distribution of $\\bs\\theta$ and $\\bs\\omega$ in the $k$-th iteration, respectively; $h_i$ denotes the partial derivative w.r.t the $i$-th particle; $\\mathcal{L}_2^N$ denotes the Lynapunov function for the counterpart on the product space; $\\bs\\rho$ denotes the Gibbs distribution; $O(\\frac{1}{N})$ is from the propagation of chaos. Other log-Sobolev inequalities used in our setting have similar forms. Thereby, most derivations in the manuscript involving Taylor expansions can be extended to analyze the joint distribution of particles, but with additional approximation error $O(1/N)$ due to weak particle interactions. The per-step improvement would be of the form\n\n$$\n\\mathcal L(\\bs\\mu_{k+1},\\bs\\nu_{k+1})\\leq (1-2\\eta_1\\tau\\alpha)\\mathcal L(\\bs\\mu_{k},\\bs\\nu_{k}) + O(\\eta_1^2) + O(\\frac{\\eta_1}{N})\n$$\n\nwhere the $O(\\frac{\\eta_1}{N})$ term comes from the propagation of chaos. Building on our current line of thought, we believe this approach can be extended to the stochastic gradient setting while maintaining the same sample complexity order as well. However, due to the extensive computations involved, we will present a complete proof of our results in an upcoming extended journal version.\n\n**Parameters**: Due to the space limit, please refer to our response to Reviewer 5VGF for a detailed analysis of how the sample complexity in Theorems 1 and 2 depends on various parameters, including the dimension $d$. Notably, the sample complexity of MFL-AG in [2] is $O(\\epsilon^{-O(1/\\alpha)})$, which is exponential in the LSI constant $\\alpha$, hence in $d$ under their conservative bound $O(1/(2+d/2))$ of $\\alpha$, whereas our bound does not suffer from this exponential dependence. The Hessian bound $C_1$ occurs in bias $\\Gamma_i=O(C_1)$. As for the condition number, adopting the notion of effective condition number in [3, Theorem 2.1], our bound has a similar dependence in the case of zero-sum game.\n\n## Addressing Questions:\n\n**Line 143 and Equation (9)**: Thank you for pointing this out. We will correct the issues in the updated version of the manuscript.\n\n**Boundedness of third-moment**: The existence of this issue arises from the presence of $\\mathbb{E}_{\\mu_k}[\\\\|g_k\\\\|_2^3]$ in our remainder term. Therefore, in the stochastic gradient part, to ensure that this remainder term remains uniformly bounded, we need to impose a bound on the third-order moment. In fact, [1] assumed that the stochastic gradient is uniformly bounded with respect to any $\\omega$ and $\\theta$, which is stronger than ours. \n\nThank you again for your valuable feedback! We will correct the typos and formatting issues as you suggested.\n\n### References \n\n[1] Suzuki, T., Wu, D., & Nitanda, A. (2023). Convergence of mean-field Langevin dynamics: time-space discretization, stochastic gradient, and variance reduction. Advances in Neural Information Processing Systems, 36, 15545-15577.\n\n[2] Kim, J., Yamamoto, K., Oko, K., Yang, Z., & Suzuki, T. (2023). Symmetric mean-field langevin dynamics for distributional minimax problems. arXiv preprint arXiv:2312.01127.\n\n[3] Lu, Yulong. Two-scale gradient descent ascent dynamics finds mixed Nash equilibria of continuous games: A mean-field perspective. International Conference on Machine Learning. PMLR, 2023.", "claims_and_evidence": "The main selling point of this work is the $\\widetilde{O}(1/\\varepsilon)$ rate, under standard assumptions on the boundedness of (derivatives of) differentials of the objective. This result is state-of-the-art compared to prior work (which generally has higher complexity). There is also an extension to stochastic gradient oracles when the oracle has bounded error in the second and third moments. The authors provide solid proofs for their claims.", "methods_and_evaluation_criteria": "This is not applicable to this paper.", "theoretical_claims": "The results make sense and the proofs appear rigorous; I checked all the results (without verifying all technical details).", "experimental_designs_or_analyses": "The paper is theoretical in nature and therefore does not contain an experimental component. However, some ramifications for typical applications are discussed.", "relation_to_broader_scientific_literature": "The paper is related to prior work on mean-field games, in particular to Langevin-type algorithms for computing equilibrium points. The main claim of this paper is that it improves the rates compared to those prior works (at least with respect to the inverse accuracy dependence). Earlier work had a super-linear dependence on $\\varepsilon$ or required an inner-outer loop complexity.", "essential_references_not_discussed": "As far as I am aware, the most relevant references have been covered.", "other_strengths_and_weaknesses": "**Strengths:**\n\nI believe this work is impactful as it makes a significant improvement to the rate estimate for an important statistical problem.\n\nThe rates are examined in the context of various applications, with interpretable and clear results.\n\n**Weaknesses:**\n\nThe result is mainly theoretical, as in general a particle-algorithm is needed for implementability (which complicates the rate). This is agreed upon by the authors; it is unclear to me whether the analysis scheme in this paper can be preserved after particle discretization. \n\nIt would be helpful if the authors included other important parameters in their rate estimates, such as the dimensions.", "other_comments_or_suggestions": "Line 143: “We set the scaling factor the weight decay the regularization” does not make sense, please revise.\n\nEquation 9 exceeds the column spacing. This occurs in multiple other places; please fix this.", "questions_for_authors": "What is the dependence of the result on the dimension, and the condition numbers (Hessian bounds, etc.)? How does it compare to prior work?\n\nIt is a bit strange that third-moment boundedness is needed for the stochastic gradient oracle, when normally it is only the second moment that is required. Can the authors comment if they believe this requirement is fundamental?\n\nAlthough the paper attains a sharp rate, this is for the mean-field version of the algorithm. It is not clear whether this type analysis can be carried out using this framework for a finite particle algorithm (accounting for additional error of the particles). Can the authors comment?", "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": "QmjcrMx8Sq", "reviewer": "Reviewer_YCRA", "summary": "This paper analyzes a natural algorithm for distribution min-max optimization, which consists in taking alternating Langevin steps. The main contribution of the paper is theoretical analysis of this algorithm for the case where the gradients are exact as well as the case where the gradients are in-exact. Their analysis avoids the more standard approach which first analyzes the continuous time flow and then bounds the discretization error. The main application is to mean-field networks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your critical feedback, especially your sharp observations about the order of the bias term. Below, we address your concerns.\n$\\newcommand{\\bE}{\\mathbb{E}} \\newcommand{\\o}{\\omega}$\n## Addressing Weaknesses\n\n**Bias term of second moment**: Indeed, the norm control in the submitted version (adopted from [3, Lemma 1]) is sub-optimal. Below, please find a stronger control, adopted from [2, Lemma 1]. The corrected expression for $r_{g2}$ should be $r_{g2}= 2M^2_1+2\\tau^2\\bE_{\\mu_0}[\\\\|\\\\theta_0\\\\|^2_2]+4M^2_1+ \\tau(4\\eta_2M^2_1+4\\tau d)$ and similarly for $r_{h2}$. They are of order $O(1)$, thereby the bias term $R_1$ in Theorem 1 is $O(\\eta_1)$. \n\n$$\n\\begin{aligned}\n  &\\bE_{\\nu_{k+1}}[\\\\|\\o_{k+1}\\\\|^2]\\\\\\\\\n  =&\\bE_{\\nu_k\\otimes \\rho}[\\\\|\\o_k+\\eta_2 h_k+\\sqrt{2\\eta_2\\tau}\\xi^2_k\\\\|^2]\\\\\\\\\n  =&\\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2]+2\\bE_{\\nu_k\\otimes \\rho}[\\langle \\o_k,\\eta_2 (h_k+\\tau\\o_k-\\tau\\o_k)+\\sqrt{2\\eta_2 \\tau}\\xi^2_k\\rangle]+\\bE_{\\nu_k\\otimes \\rho}[\\\\|\\eta_2h_k+\\sqrt{2\\eta_2 \\tau} \\xi^2_k\\\\|^2]\\\\\\\\\n   \\leq&\\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2] + 2\\eta_2 M_1 \\bE_{\\nu_k}[\\\\|\\o_k\\\\|]-2\\eta_2\\tau \\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2]+2\\eta^2_2( M^2_1 + \\tau^2 \\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2]) +2\\eta_2\\tau d\\\\\\\\\n  \\leq& (1-2\\eta_2\\tau +\\frac{\\eta_2\\tau}{2}+2\\eta^2_2\\tau^2) \\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2] + 2\\eta_2 M^2_1/\\tau +2\\eta^2_2 M^2_1 + 2\\eta_2\\tau d\\\\\\\\\n  \\leq& (1-\\eta_2\\tau)\\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2] +\\eta_2(2M^2_1/\\tau+2\\eta_2M^2_1+2\\tau d),\n\\end{aligned}\n$$\nwhere the first equality uses the fact that $\\xi_k^2$ is an independent zero-mean normal; the first inequality follows the fact that \n$\\\\|h_k+\\tau\\o_k\\\\| = \\\\|\\nabla \\frac{\\delta J}{\\delta \\nu} \\[\\mu_{k+1}, \\nu_k\\](\\o_k)\\\\| \\leq M_1$; the second inequality is because $2M_1\\bE_{\\nu_k}[\\\\|\\\\o_k\\\\|]\\leq \\frac{\\tau}{2} (\\bE_{\\nu_k}[\\\\|\\o_k\\\\|])^2 + 2M^2_1/\\tau \\leq  \\frac{\\tau}{2}\\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2]+2M^2_1/\\tau$ and last inequality holds for $\\tau<1/(4\\eta_2)$. Hence, we obtain\n$$\n\\begin{aligned}\n\\bE_{\\nu_k}[\\\\|\\o_k\\\\|^2] & \\leq  (1-\\eta_2\\tau)^k \\bE_{\\nu_0}[\\\\|\\o_0\\\\|^2]+ 2\\eta_2 (M_1^2/\\tau + \\eta_2 M_1^2 + \\tau d )\\sum_{j=0}^{k-1}(1 - \\eta_2\\tau)^j\\\\\\\\\n&\\leq \\bE_{\\nu_0}[\\\\|\\o_0\\\\|^2]+  \\frac{2(M^2_1/\\tau + \\eta_2 M^2_1 + \\tau d)}{\\tau},\n\\end{aligned}\n$$\nThe remaining part of the proof stays the same.  Hence, we can directly check that the remaining constants $r_{gi}$, $r_{hi}$ as well as $\\Gamma_0$, $\\Gamma_1$, $\\Gamma_2$ are all of order $O(1)$. Since $\\eta_1$ and $\\eta_2$ are of the same order, we conclude that the bias term $R_1= \\frac{\\lambda(\\Gamma_2\\eta_2^2+(1-2\\eta_2\\tau\\alpha)(\\Gamma_1+\\Gamma_0)\\eta_1^2)+\\Gamma_1\\eta_1^2}{\\eta_1\\tau\\alpha}$ is of order $O(\\eta_1)$.\n\nRegarding your question on the definition of constants in (18), they are defined in the proof of Theorem 2 (Line 1214, etc.). We apologize for not explicitly displaying them. \n\n**Assumptions of LSI in examples**: Indeed, we have provided two applications in Section 4, with the LSI being verified in Proposition 3 and Proposition 4, respectively. This follows a line of work like [1, proposition 5.1] and [2, Appendix A]. The setups therein are satisfied in our context.\n\n**Existence and uniqueness of optimal $\\mu^\\*,\\nu^\\*$ :**  The primal objective $J(\\mu, \\nu)$ is convex in $\\mu$ and concave in $\\nu$. With an additional KL (or entropy) regularization, the regularized objective $E(\\mu, \\nu)$ becomes strongly convex in $\\mu$ and strongly concave in $\\nu$. This ensures the existence and uniqueness of the mixed Nash equilibrium $(\\mu^*, \\nu^*)$; please refer to the detailed discussion before equation (3) in the manuscript as well as [2, Proposition 2.1].\n\n## Addressing Questions\n**A1**. To get (24), the first line follows directly from equation (23); the second line follows from the definition of $T$; the third line follows from the Taylor's expansion of $\\log {\\rm det}$, where $\\bar{\\o}_k$ is the point that achieves the mean-value; and the fourth line follows from the property of trace operator and that ${\\rm Tr}(h_k^2) =\\\\|\\nabla h_k\\\\|_F^2 = (\\\\|\\nabla^2 \\frac{\\delta J}{\\delta \\nu}\\\\|_F - \\tau)^2 \\leq (M_2 + \\tau)^2$.\n\n**A2**. Yes, you're absolutely right.\n\nThank you so much again for your insightful and constructive feedback. We hope our responses alleviate your concerns.\n\n### References: \n[1]Chizat, L. Mean-field Langevin dynamics: Exponential convergence and annealing. *Transactions on Machine Learning Research*, 2022.\n\n[2]Suzuki, T., Wu, D., and Nitanda, A. Mean-field Langevin dynamics: Time-space discretization, stochastic gradient, and variance reduction.  *Advances in Neural Information Processing Systems*, 36, 2024.\n\n[3] Nitanda, Atsushi, Denny Wu, and Taiji Suzuki. Convex analysis of the mean field langevin dynamics. *International Conference on Artificial Intelligence and Statistics*, 2022.", "claims_and_evidence": "I am seriously concerned about their claim, after Theorem 1, that the bias term $R_1$ is $O(\\eta_1)$. In fact, when I examine the definitions of $\\Gamma_1, \\Gamma_2, \\Gamma_3$, it looks to me that they are in fact $O(1/\\eta_1)$ (this is coming from the final terms in the definitions of $r_{g2}, r_{h2}$). Unless there is a typo, this would seem to indicate that the bias term $R_1$ is in fact $O(1)$, meaning that their main result only shows that the objective doesn't increase more than $O(1)$ throughout the trajectory. I assume that this problem extends to Theorem 2, but the relevant constants don't seem to be defined in Section A.3 (where are they?).\n\nAnother -- although less critical -- issue is Assumption 3 on the log-Sobolev constants. Although they consider several applications of their results, they don't demonstrate any settings where their assumptions hold. Of course, verifying their assumptions for neural networks is likely far too difficult, but as a sanity check, I would like to seen an example of a setting where Assumption 3 actually holds. I think this would make the paper stronger.\n\nFinally, I am probably confused, but in Corollary 1, I don't understand why there must be unique $\\mu^*, \\nu^*$ that the algorithm even converges to? What am I missing here?", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked some of the proofs in the appendix, but not all of them and not in full detail. I didn't find any serious issues, and at a high level the results seem plausible. The main concern is the dependence of the bias term on the step-sizes $\\eta_1, \\eta_2$, see above.", "experimental_designs_or_analyses": "There were no experiments but I don't think that's necessary.", "relation_to_broader_scientific_literature": "The paper is trying to push forward on discrete time analysis of distributional min-max problems. This is certainly a worthy problem, and it seems their contribution would be novel. However, I am seriously concerned about the bias terms.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "If the bias term were truly $O(\\eta_1)$ the paper would be a strong theoretical contribution. In fact, it would probably even imply a new analysis of discrete-time Langevin dynamics since that seems to be a special case of their setup. But this is exactly why I am a bit skeptical of their results -- it's hard to imagine that they found a completely new analysis of Langevin dynamics that simulatenously holds in their more general setup. If the bias term is indeed only $O(1)$ then I don't think the paper is strong enough, as it merely asserts the objective doesn't blow up.", "other_comments_or_suggestions": "- I don't follow equation 24.\n- Equation 46 uses $\\tilde \\mu$ without defining it (reading onwards I suppose that it is meant to be a distribution coming from the mean-value theorem).", "questions_for_authors": "Please address the issue about the size of the bias term $R_1$.", "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": "uBIEgTM7c5", "reviewer": "Reviewer_GF3y", "summary": "This paper studies the convergence rate of discrete-time mean-field Langevin stochastic descent-ascent for min-max problems in distributional optimization under log-Sobolev inequality condition. The authors claim that the derived convergence rate is near-optimal compared to its Euclidean counterpart. The paper includes two examples: zero-sum games and mean-field neural networks. However, no experimental results are provided.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments! Below, we respond to the concerns and clarify the novelty and contributions of our work.\n\n\n**On our analysis**:   We would clarify that both our proof technique and the resulting conclusions differ from the aforementioned papers in several fundamental ways. First, these prior works (*Kim et al. (2024)*, *Chen et al. (2022)*, *Suzuki et al. (2023)*, *Nitanda et al. (2022)*) tackle the discrete-time MFLD problem by first establishing convergence in continuous time (typically via Wasserstein gradient flow) and then controlling the discretization error as a separate step. In contrast, our proof directly analyzes the per-step improvement using Taylor expansion and remainder estimates. This not only provides a more elegant and adaptable proof framework, but also yields stronger results as detailed in the next point. \n\nMoreover, our results also differ in several key aspects. *Kim et al. (2024)* do not study MFL-SDA. To our best knowledge, their analysis of other algorithms does not extend to our established convergence rate of MFL-SDA. While *Yang et al. (2020)* study a minimax optimization in Euclidean space, and our analysis shares some structural similarities with theirs, the time-discretization error anlaysis of the probability functional on distributional space requires substantially more sophistication -- we devote pages of proofs to controlling this error, whereas in the Eucliean case, it follows directly from smoothness assumptions. The other cited references--*Chen et al. (2022)*, *Suzuki et al. (2023)*, and *Nitanda et al. (2022)*--focus on minimization problems, whereas minimax problems present more complexity due to the interaction between two players. \n\n**On the Lyapunov function**: As you said, $\\lambda$ can be fixed to 1. Yet, our chosen form of the Lyapunov function follows what is commonly used in previous works on minimax problems in Euclidean space (*Yang et al. (2020)*) and in continuous-time MFLD (*Lu (2023)*).\n\n**Comparison with MFL-AG and MFL-ABR:** First, our analysis of stochastic gradient descent-ascent with last-iterate convergence and the inexact gradient analysis closely aligns with practical implementations.  \nSecond, MFL-AG achieves a sample complexity $O(\\epsilon^{-O(1/\\alpha)})$ to reach an $O(\\epsilon)$-approximation of the saddle point, where the bound on LSI constant $\\alpha$ can be small--potentially even of order $1/(2+d/2)$. In contrast, our convergence analysis for MFL-DA establishes a sample complexity $O(\\frac{1}{\\epsilon}\\log\\frac{1}{\\epsilon})$. MFL-ABR is a double-loop algorithm, it is shown that the outer loop has an $O(\\frac{1}{\\epsilon}\\log\\frac{1}{\\epsilon})$ sample complexity; however, it needs an inner loop and the total complexity is not specified.\n\n**On Experimental Results and Applications:**\nThe primary aim of our work is to establish convergence guarantees for commonly used stochastic gradient descent-ascent algorithms. We acknowledge the value of empirical validation, we have included a numerical experiment based on Example 2 in our paper. We apply our algorithm to the nonlinear instrumental variable (NPIV) regression problem $$\n\\min_f \\max_g E[g(Z)(Y-f(X))-\\frac{1}{2}g(Z)^2+\\lambda R(f)]\n$$\nwhere $R$ is a regularizer.\nUsing the problem setup and datasets in [1,2], we compare our algorithm with a classic series-approximation (SA) method [3] based on out-of-sample MSE (lower values indicate better performance) and average R² (higher values indicate better performance)\n\n*Engel Curve*\n| Method                    | Average MSE | Average R² |\n| ------------------------- | ----------- | ---------- |\n| MFL-SDA                 | **0.00698**  | **0.256**   |\n|SA | 0.00730  | 0.218   |\n\n*Returns to schooling*\n| Method                    | Average MSE | Average R² |\n| ------------------------- | ----------- | ---------- |\n| MFL-SDA                 | **0.1494**  | **0.0799**   |\n| SA | 0.1626  | 0.1543   |\n\n**4. Clarification of Equation (9):**\nGood catch! We will revise Equation (9) in the updated version.\n\nThank you again for your feedback, and we hope our response clarifies the contribution of our paper.\n\n### References:\n[1]Hausman, J. A., Newey, W. K., & Powell, J. L. (1995). Nonlinear errors in variables estimation of some Engel curves. *Journal of Econometrics*, *65*(1), 205-233.\n\n[2] Card, David. Estimating the return to schooling: Progress on some persistent econometric problems. *Econometrica* 69.5 (2001): 1127-1160.\n\n[3] Newey, Whitney K., and James L. Powell. Instrumental variable estimation of nonparametric models. *Econometrica* 71.5 (2003): 1565-1578.", "claims_and_evidence": "The theoretical results are consistent with the authors' claims.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "I did not verify the details of the proofs.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The topic is important to optimization theory and has significant relevance to the machine learning community", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. The topic is interesting.\n2. The paper is easy to read.\n\nWeaknesses:\n1. The analysis and results appear elementary and straightforward, closely following previous works such as Kim et al. (2024), Yang et al. (2020), Chen et al. (2022), Suzuki et al. (2023), and Nitanda et al. (2022). Specifically, the variable lambda in the Lyapunov function seems unnecessary, as it can be set to 1 in this case. Given this, the results appear quite direct based on current results in MFLD, limiting the paper’s technical contribution.\n\n2. What are the advantages of the MFL-SDA algorithm compared to MFL-AG and MFL-ABR? The lack of comparison makes the motivation unconvincing. A discussion of their relative strengths and weaknesses would improve clarity.\n\n3. The two provided examples are restricted to two-layer neural networks, and no experimental evidence is given. I would expect more interesting applications and empirical results to strengthen the paper’s impact.", "other_comments_or_suggestions": "In Eq (9):\n\nL1(u) = max E(u,v') - minmax E(u',v')\nL2(u,v)=max E(u,v') - E(u,v)", "questions_for_authors": "See my comments in weaknesses.", "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": "1B5n6hJa43", "reviewer": "Reviewer_5VGF", "summary": "This paper studies the mean-field Langevin (stochastic) descent-ascent (MFL-DA) algorithm for solving distributional minimax optimization problems. The authors demonstrate that the infinite-particle limit of discrete-time MFL-DA is able to converge to the unique stationary point of the problem with a convergence rate of $\\frac{1}{\\epsilon}\\log\\frac{1}{\\epsilon}$ measured in squared 2-Wasserstein distance. The authors show applications of their result to finding mixed Nash equilibria of zero-sum games, generative adversarial networks, and mean-field neural networks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed feedback! Below, we address the comments and questions point-by-point.\n\n**Pessimistic LSI bound**:  We will explicitly comment on the weakness of this type of analysis, and we are trying to overcome this in our ongoing research.  \n\n**Explicit dependence on other parameters**:\nIn the revised version, we will include a dedicated paragraph discussing the roles of parameters and here we provide a sketch.\n\n**On dimension $d$ and regularization parameters**: We agree that a more explicit discussion of the role of parameters in the convergence rate would be beneficial. Viewing $\\tau,\\eta_1,\\eta_2$ as small numbers, in Appendix A.3 on page 11, the remainder $r_{g2}, r_{h2}$ due to the second moment are $\\max\\\\{O(1),\\tau d\\\\}$, similarly $r_{g3}, r_{h3}$ are $\\max \\\\{ O(1),\\tau^{3/2}d^{3/2} \\\\} $. Substituting them into $\\Gamma_0, \\Gamma_1, \\Gamma_2$, we can get $\\Gamma_0=\\max\\\\{O(1), \\tau d,\\tau^{2}d^{2},\\frac{d}{\\alpha^{1/2}\\tau} \\\\}$, and $\\Gamma_{1(2)}=\\max\\\\{O(1),\\tau d,\\tau^2d^2\\\\}$.  Substutiuting them into $R_1$ in (10), we can get $R_1=O(\\frac{d^2\\eta_1}{\\tau^3\\alpha^3})$. Let $R_1=\\epsilon$ and choose $\\eta_1= O(\\frac{\\epsilon \\tau^3 \\alpha^3}{d^2})$, we obtain a sample complexity $K=O(\\frac{d^2}{\\epsilon \\tau^4 \\alpha^4}\\log \\frac{1}{\\epsilon})$. Comparing with sample complexity $K=O(\\frac{d^2}{\\epsilon \\tau^2 \\alpha^2}\\log \\frac{1}{\\epsilon}$) in [1] for the MFLD of minimization problems, the higher orders of $\\tau, \\alpha$ is because the two-timescale algorithm MFL-SDA: the overall complexity of the algorithm depends on the slower descent step. \n\n**On other parameters:** The variance $\\zeta,\\sigma^2$ only affect the $O(1)$ term in $\\Gamma_i$. The parameters $\\eta_1,\\eta_2$ correspond to the fast descent and fast ascent regime similar to [3], and thus their choice depends on the instance and the user's emphasis on the descent/ascent part.\n\n**Another standard of suboptimality**: Our problem is to find a saddle point rather than a maxima(mimima), hence  $E(\\mu_K,\\nu_K)-E(\\mu^*,\\nu^*)$ may not apply to our analysis. \n\n## Addressing References Not Discussed:\n\nThank you for pointing this out! We will cite this paper in the revision and investigate if their Theorem 5.2 can inspire a better LSI bound for our problem.\n\n## Addressing Questions:\n\n**A1.** Thank you for catching this: the Talagrand's inequality should be $W_2^2(\\mu_k,\\nu^*)\\leq \\frac{2}{\\alpha}\\mathrm{KL}(\\mu_k|\\mu^*)$.\n\n**A2.** $\\lambda$ corresponds to the Lyapunov function similar to [2] [3], and it is not an explicit hyperparameter in our algorithm.\n\n**A3.**  Yes, it holds point-wise for all $\\theta$ and $\\omega$.\n\n**A4.** See our response on the dimension above.\n \n**A5, A6.** Thank you for noticing this. We will correct the notation.\n\nWe thank you very much again for the constructive feedback and helpful suggestions!\n\n### Reference:\n\n[1] Nitanda, A., Wu, D., & Suzuki, T. (2022). Convex analysis of the mean field Langevin dynamics. In International Conference on Artificial Intelligence and Statistics (pp. 9741-9757). PMLR.\n\n[2] Lu, Y. (2023). Two-scale gradient descent ascent dynamics finds mixed Nash equilibria of continuous games: A mean-field perspective. In International Conference on Machine Learning (pp. 22790-22811). PMLR.\n\n[3] Yang, J., Kiyavash, N., & He, N. (2020). Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. arXiv preprint arXiv:2002.09621.", "claims_and_evidence": "The claims seem clear and well-supported.", "methods_and_evaluation_criteria": "Not applicable since this is a theory paper.", "theoretical_claims": "I did not go over the details of the proof but the overall claims seem to be consistent with the literature and the proof technique seems sound from a high level.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "This paper contributes to a long line of work of applications of the mean-field Langevin dynamics for optimization in the space of probability distributions. As discussed in the paper, this is (to my knowledge) the first discrete-time convergence guarantee for mean-field Langevin descent-ascent for solving distributional min-max problems. Both the algorithm and the problem are of significant interest to the community.", "essential_references_not_discussed": "Most essential references are discussed in the paper. I think the authors can also discuss [1] where the mean-field Langevin algorithm is used for optimization over signed measures. Specifically, that paper contains ideas for going beyond pessimistic LSI constant estimates which can be useful for the results here as well, and similar to this paper, they also need a two-timescales approach for their analysis.\n\n[1] G. Wang, A. Mousavi-Hosseini, L. Chizat. \"Mean-Field Langevin Dynamics for Signed Measures via a Bilevel Approach.\" NeurIPS 2024.", "other_strengths_and_weaknesses": "**Strengths**:\n\nSolving minmax optimization on the space of distributions is a fundamental problem, and it is nice to have discrete-time convergence guarantees for the mean-field Langevin descent-ascent algorithm. Also, the paper is mostly well-written and easy to ready.\n\n**Weakness**:\n\n* A main concern for me is that there is almost no discussion on the role of other parameters besides $\\epsilon$ in the convergence rate. A major weakness of this type of mean-field Langevin analysis is that convergence requires $\\tau$ to be at least linearly small with ambient dimension $d$. When plugged into the pessimistic LSI bound, this implies $\\alpha$ that is exponentially small in $d$, and thus a convergence rate that is exponentially large in $d$. This is a drawback of this type of analysis and not a weakness of this paper in particular, but I think it is better to be explicitly discussed.\n\n* Similarly, the role of other parameters is not clear/made explicit. For example, is it better to have $\\eta_1 \\gg \\eta_2$ or $\\eta_1 \\ll \\eta_2$? How do quantities like $\\alpha$, $\\sigma^2$, and $\\zeta$ enter the final convergence rate? While these questions might be answered by following certain quantities in the appendix, I think it would be nice to have summaries of the convergence rate in the main text.\n\n* The convergence analysis yields a bound on $\\mathcal{L}$ and the Wasserstein distance to $\\mu^*$ and $\\nu^*$. Can such bounds be turned into a bound on the suboptimality $E(\\mu_K,\\nu_K) - E(\\mu^*,\\nu^*)$? I am asking this in particular since bounding this suboptimality is possible for distributional minimization problmes with mean-field Langevin.\n\n* Additional suggestions are discussed below.", "other_comments_or_suggestions": "Please see below.", "questions_for_authors": "1. It seems that $\\frac{1}{\\alpha_1}$ should be replaced with $\\alpha_1$ in Corollary 1, otherwise we can drive the Wasserstein distances to zero by simply letting $\\alpha_1 \\to 0$.\n\n2. What is the optimal value of $\\lambda$ for Theorems 1, 2, and Corollary 1?\n\n3. Does Assumption 4 hold point-wise for all $\\theta$ and $\\omega$? I believe the expectation is over the random noise for estimating $g_k$ and $h_k$, which still leaves out $\\theta$ and $\\omega$.\n\n4. Do we expect the constants that appear in the paper, such as those in Assumptions 1-4 and in Proposition 3 to be dimension-dependent in typical settings?\n\n5. Equation (8) seems to have a typo, why are you using the expectation notation?\n\n6. Typo in the first line of Equation (9), I believe $\\nu$ should be $\\nu’$.", "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:

Meta-review: This paper presents a convergence analysis of the discrete-time mean-field Langevin stochastic descent-ascent (MFL-SDA) algorithm for solving distributional minimax optimization problems. The authors establish an $O(\frac{1}{\epsilon} \log(\frac{1}{\epsilon}))$ convergence rate under log-Sobolev conditions, which is nearly optimal. A key technical contribution is the direct discrete-time analysis without resorting to continuous-time PDE arguments.

The work is theoretically well-motivated and relevant to key applications, including GANs, zero-sum games, and robust learning. All reviewers leaned toward acceptance, with several increasing their scores after a detailed and thoughtful rebuttal.

That said, reviewer 5VGF pointed out a crucial issue: the dependence of convergence rate on parameters such as the dimension, regularization parameter, and LSI constant was suppressed in the initial submission. The authors responded with clear expressions, but this content should be more prominently discussed in the final version.

Overall, this paper advances the theoretical understanding of Langevin-type algorithms in minimax distributional settings and deserves to be accepted.
Decision: Accept (spotlight poster)