Stochastic Approximation Algorithms for Systems of Interacting Particles
Authors: Mohammad Reza Karimi Jaghargh
Ya-Ping Hsieh
Andreas Krause
Venue: NeurIPS 2023 poster (2023)
Keywords: Stochastic Approximation
Mean-Field Dynamics
Dynamical Systems
Neural Networks
Sampling

Abstract: Interacting particle systems have proven highly successful in various machine
learning tasks, including approximate Bayesian inference and neural network optimization. However, the analysis of these
systems often relies on the simplifying assumption of the \emph{mean-field} limit, where particle
numbers approach infinity and infinitesimal step sizes are used. In practice, discrete time steps,
finite particle numbers, and complex integration schemes are employed, creating a theoretical gap
between continuous-time and discrete-time processes. In this paper, we present a novel framework
that establishes a precise connection between these discrete-time schemes and their corresponding
mean-field limits in terms of convergence properties and asymptotic behavior. By adopting a dynamical system perspective, our framework seamlessly integrates various numerical schemes that are typically analyzed independently. 
For example, our framework provides a unified treatment of optimizing an infinite-width two-layer neural network and sampling via Stein Variational Gradient descent, which were previously studied in isolation.

Stochastic Approximation Algorithms for Systems of Interacting Particles
Mohammad Reza Karimi ETH Zürich mkarimi @inf ethz. ch
Ya-Ping Hsieh ETH Zürich yaping hsieheinf ethz. ch
Andreas Krause ETH Zürich krauseaGethz.co ch
Abstract
Interacting particle systems have proven highly successful in various machine learning tasks, including approximate Bayesian inference and neural network optimization. However, the analysis of these systems often relies the simplifying assumption of the mean-field limit, where particle numbers approach infinity and infinitesimal step sizes are used. In practice, discrete time steps, finite particle numbers, and complex integration schemes are employed, creating theoretical gap between continuous-time and discrete-time processes. In this paper, we present a novel framework that establishes precise connection between these discrete- time schemes and their corresponding mean-fiell limits in terms convergence properties and asymptotic behavior. By adopting dynamical system perspective, our framework seamlessly integrates various numerical schemes that are typically analyzed independently. For example, our framework provides unified treatment of optimizing an infinite-widhe width two-layer neural network and sampling via Stein Variational Gradient descent, which were previously studied in isolation.
Introduction
Dynamics of interacting particle systems are central to many challenges in modern machine learning. These range from algorithm design for approximate Bayesian inference, to the study of equilibria games [26, 31, 34]. Moreover, researchers have gained valuable insights by interpreting the training process of over-paranee ver-parametrized two-layer neural networks as a system of interacting particles, thereby advancing our intuition in this domain [11, 12, 36-38, 46, 51].
Analyzing the behavior of such systems poses a significant challenge. To simplify the analysis, researchers often turn to the concept of the mean-field limit. In this approach, the number of particles increased infinity, the step-size of the algorithm shrinks to zero, and results are deduced from this continuous limit. Specifically, an initial probability distribution is assigned to the infinitely many parti- cles, and a continuous time evolution derived for this distribution. The resulting evolutionary equa- tion serves as a powerful tool for gaining insights into the system's 's asymptotic behavior, significantly aiding in the comprehension of systems with large number of interacting particles 5, 22, 26, 47].
Although the mean-fiee field limit has offered valuable insights into the aforementioned problems, its rigorous justification necessitates examining systems with both a finite number of particles and the discrete-time algorithms commonly used in practice. Unfortunately, to the best of our knowledge, while a substantial body of work exists finiteparticle systems (see, e.g., the review papers [8, 9] and references therein), these studies are confined to analyzing continuous-time dynamics. As a result, gap between theory and practice has emerged, and precise link between continuous and discrete-time schemes is still largely lacking.
$ Contributions. Our paper aims to bridge this gap by rigorously establishing the convergence of discrete-time algorithms to their continuous-time counterparts in terms of long-term behavior.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To accomplish this, we draw inspiration from the field of dynamical system theory, which traces its origins back to early developments in statistics [42] and has recently found success in various domains of machine learning, including optimization theory, games, and sampling [21, 23, 24].
This dynamical system framework offers two significant advantages. Firstly, it provides a flexible framework capable of accommodating wide range of practical schemes commonly employed in real-world scenarios. Secondly, this framework enables a unified treatment of various machine learning tasks that were previously studied in isolation. Notably, it allows us to address tasks such as training neural networks and approximate Bayesian inference using techniques like Stein variational gradient descent in coherent and unified manner.
In summary, paper makes the following contributions:
We introduce comprehensive framework for analyzing a broad class of algorithms called stochastic approximation schemes. These schemes are widely utilized in simulating systems of interacting particles, and our framework provides unified approach analyze their behavior.
2. Under mild assumptions on the discrete-time schemes and the mean-field dynamies, we prove the convergence of these schemes towards their respective mean-field limits. The convergence is established in terms of the 2-Wasserstein distance, a metric commonly used to measure the dissimilarity between probability distributions.
3. Since our framework is specifically tailored to address a wide range of fields, we instantiate our main theorem and provide novel guarantees diverse array of interacting particle systems across domains such as the Stein variational gradient descent, the training of wide two-layer neural networks, and the examination of game equilibria.
2 Illustration: Training Two-Layer Neural Networks via Noisy SGD
To illustrate the particle system under study and its corresponding mean-field limit, let us consider the example of training two-layer neural network with N neurons and squared loss using the noisy SGD algorithm. The network takes an input E R ddd and computes function:
h=(z) N NN 2)) with g' = (a' Rd- x R and <(0'', = b' k((a',
Here, 0 = (6'...., y denotes the collection of neurons' parameters, and к is an activation function (such as sigmoid or tanh). To train this network, one ideally minimizes the regularized risk (()) == - 1 { (2)) U()), where D is the data distribution, and U(0) N Σ, U(0') is a regularizer, such as U(A)= = _10r.. Applying the noisy gradient descent algorithm to the regularized risk then results in the update rule:
8 0 Yk+1 V of L(0x)) + 2 ELE..
I.....,, N,
(SGD,)
where yk+1 is the step-size, or 0 is the noise level, and ( } is a collection of i.i.d. standard Gaussians. To cast this algorithm as a system of interacting particles, we define the interaction kernel W and the potential V as
W(0. 0') = Ez- ()) (0) and V(O) =
+U(()).
(1)
It is then easily seen (cf. [36, Eqn. 4]) that the update rule (SGD,) can be rewritten as N
6 oz Yx+1
1
Σ J=1
VoW(O, op) +V((')) t V Sk-p i=
(2)
By considering neurons particles, the equation (2) reveals that the training dynamics of each particle is influenced by the potential V and the interaction energy W with other particles. This interpretation highlights that (SGD,)) represents the evolution of system of interacting particles. In a broader context, one may consider more sophisticated a algorithms, several of which (see Section for examples) can be formulated
E' = 0 Yk+1 (V L(Ox) + Pii.i) 2 K
i= i=
(3)
where pi_ is the (random or deterministic) perturbation in evaluating the gradient. These algorithms are usually called stochastic approximation algorithms. For example, Noisy SGD corresponds to setting P = Vo L(0x) V L(Ox), where L is the loss of a random batch of data.

---

$ Continuous-time limit and the mean-field approximation. We now go from the discrete- time algorithm (3) to a continuous-time process and then derive the mean-field approximation. First, observe that the risk I(0) depends on (o'....,0%) only through their empirical measure
N Ei 6gt. For example,
I N EE VoW(O, + = V voW(O,0) jidd') + VV(O) =: p)
(4)
where we have introduced the drift function b. To simplify the analysis, previous studies then consider the idealized setting where an infinitesimal step-size is employed, thereby further reducing (3) the following system of stochastic differential equations (SDEs):
d0;- = b(88 (T) di o V2dw
1 I......N
(5)
where ū., = N Σi oe is the empirical measure of the particles at time r, and (W.) is collection of i..d. standard Brownian motions. In the over wer-parametrizer regime where the number of particles N becomes very large. one can approximate the initial setting of the particles ño with a probability density po. and consider the following mean- field approximation defined over Rd as
do, = Pi) dt + o dW, Pt = density(O,).
(6)
This dynamics captures the behavior of individual particle 9 within a density of particles distributed according to p. The analysis of (6) turns out to be considerably simpler compared to the system of SDEs in (5), e-g., via studying the evolutionary PDE a,p, V (pr (()) o Apt. As result, it has attracted significant interest in the field of deep learning theory [11, 12, 36-38].
In conclusion, the mean-field dynamics (6) offers powerful and elegant framework, but its validity rests on two simplifying assumptions: an infinite number of particles and a step-size approaching zero A rigorous justification of these two steps is by no means trivial. While the existing literature has made progress in addressing the infinite particle issue, the second assumption has received comparatively less attention. Bridging this gap is one of the primary objectives of our paper. Specifically, we aim to establish the Wasserstein convergence of the discrete-time dynamics (3) to the same limit sets' as the uatiinuuu-time particle dynamics (5), under mild conditions on the drift b and perturbations (Pk.)) h as well as the step-size rule yk+1.
3 Dynamics of Systems of Interacting Particles
This section presents the fundamental master theorem that forms the basis for all the applications discussed in Section 4. Our objectives are two-fold. Firstly, we aim to provide set of assumptions for the discrete-time scheme that can be easily verified by practical algorithms. Secondly, we establish a set of assumptions on the mean-field dynamies, which, as demonstrated in Section 4, are readily implied by the standard assumptions in the finite particle regime. The key result of our paper asserts that, under these assumptions, any discrete-time scheme converges to its continuous counterpart, thus closing the existing theoretical gap.
3.1 The algorithmic template
In this paper, we study the stochastic approximattin algorithms for simulating systems of interacting particles of the form:
x = =x Y2+1 (1)) Pk.n) VYk-io (tx) 5k i= i= N, (SAA)
where b: Rd x (RR) - Rd is the (non-local) drift, or Rd x P2R) - R is the (state- dependent and non-local) diffusion coefficient, Pk,1 is the noise and bias in evaluating the drift, and jA is the empirical measure of the particles at iteration k. The system (SAA) can be written in more succinct way by stacking all the variables in larger vector. That is, define x == (x'), (e') E (Rd)ss sN and let μy be the empirical distribution corresponding to the N vectors in x. and define the aggregated drift and diffusion terms as
(xx = (xx':N (Rd)0N ON
(xx) == diag( (orx', (x)li(N))
Defin (Pk-1) and (5x+)) analogously. We can then rewrite (SAA) as:
xk+1 x + 7 (b(x)) P Vyk=1 or (xx) Ex+1-
(PSAA)
TTee limit set of curve (c(1))r20 in a metric space is Droo (eec((())))))) oo))), that the set of all limits of convergent sequences (c(tz), 1s - oo).
2 (922(R ) is the space of probability measures on Rd with bounded second moments.
3

---

3.2 Dynamical system theory
By considering infinitesimal step-sizes and neglecting the perturbations P k we can derive a system of corresponding SDEs as follows:
dx; b(x; p.) di oxx, dw;, i= i= N, jr, Φ E
(Sys-SDE)
with the corresponding aggregated version
dx, bX,) (
(PSDE)
important emphasize that even though we have rearranged the particles into unified vec- lor and introduced the concepts of aggregated drift and diffusion, the original process retains its exchangeability. This property implies that the distribution of X in (Sys-SDE) remains invariant under permutations of the particles (for further details, refer to [8, Def. 2.1])-
The primary objective of paper is to rigorously establish the convergence of the stochastic approximation scheme (PSAA) to its continuous-time counterpart (PSDE). To accomplish this, we employ the dynamical system theory introduced by Benaïm and Hirsch [4]. First, construct continuous-tiie time interpolated process associated with the discrete-time algorithm (PSAA):
X, = xx + (1- (b((())))) + E[| F.)) + (xx)) Wt.), Tk S Tk+1-
(Int)
Here, = د Yj represents the cumulative time until step k. It is worth noting that we construct (Int) in such way that it is adapted to the same filtration (FF) as the Brownian motion.
To compare (PSAA) with (PSDE), we integrate (PSDE) using the following approach: For fixed I 2 O, we define w = W W, and denote the solution of (PSDE) as the flow:
( dw!") D = X, f(" b(o du + S." (
(Flow)
It is important observe that the flow starts X, and continues according to the true SDE.
We now introduce the central concept in our paper, which is the asymptotic psendotrajectory theory of Benaïm and Hirsch [4].
Definition (Wasserstein asymptotic pseudotrajectoryy. We say the stochastic process (X,) is
Wasserstein asymptotic pseudotrajectory (WAPT) of the flow & if for any fixed 7' > 0,
lim sup W2 ) O. OgssT
where W2(+.-) denotes the 2- Wassersttii distance between two distributions.
The notion of WAPT provides a measure of "asymptotic closeness" between two stochastic processes. In particular, (8) requires that (Xe)r20 closely tracks the flow "..") over arbitrarily long time intervals T with arbitrary precision. The key aspect of the WAPT that it serves as a tool specifically designed establish the convergence of stochastic approximation scheme its continuous-time counterparts. In particular, it is known that proving the convergence of stochastic approximation algorithm (PSAA) to its continuous-time counterparts (PSDE) can be accomplished by demonstrating the following two conditions [3, 4]:
The interpolation (Int) satisfies the WAPT condition with respect to the corresponding flow.
The iterates (xxhx 's in (PSAA) have bounded second moments.
Below, we present a set of general conditions that are straightforward to verify and ensure the satisfaction of the above two conditions.
Remark. There are two major reasons for choosing W2 as the distance (8): Firstly, the 2- Wasserstein space is metric space on which McKean -lasov equations can be seen as a floww both aspects indispensable for invoking the dynamical system theory of Benaïm and Hirsch [3, 4]. Secondly, is popular metric in the propagation of chaos literature. This allows seamless transition from convergence guarantees for stochastic approximation schemes to their mean-field limit counterparts via combining our results with the propagation of chaos results in the literature, see (13).

---

3.3 Technical Assumptions
We proceed present our technical assumptions and discuss their generality.
$ On the mean-field dynamics. We begin by introducing three assumptions that pertain to the drift and diffusion coefficients of the continuous-time dynamics (Sys-SDE):
Assumption 1 (Lipschitzness of drift and diffusion). There is some L > 0 such that for all x, Rd and all μ. E (R
[b(x, μ1) by. v) [lo (1) oy, v)lFF S 1((x - yl W2(H, v)). Assumption 2 (Drift growth condition). For all μ P2(R)), there is some C. O such that
f (xx, (x,b(x, p(dx) s SCo f(xx+ 1)x+++))((d))) p(dx).
Assumption 3 (Boundedness of the diffusion). There is some K > O such that for all x E Rd and all P2(R)) (x p)llF K.
We note that the first assumption is standard and is commonly used to prove existence of strong solutions for the mean-field equation (see [26, Thm. 3.3]). The other two assumptions exceedingly weak and are satisfied by all the applications we consider.
$ On the stochastic approximation schemes. The following assumptions concern the time- discretization scheme and the induced noise and bias.
Assumption (Noise and bias). The perturbation Pk+1 decomposes into noise and bias as PR+1
Uk+1 + Ex+1, where the noises {Ux+1} form a martingale difference sequence, i.e., E(Ux+1 [x] = and have second moments uniformly bounded by My. In addition, the bias terms satisfy 8k F and
E[| | =10=0kykk (xxx) +k+1)).
Assumption 5 (Step-sizes), The step-sizes are decreasing and satisfy the Robbins-Monro summability conditions
Σ yk+1 = =0 and Ekn <0.
(10)
Moreover, we require, for some constant P 0,
Yk+1 PYRYŁ+1 S Yx+1-
(11)
The condition specified in equation (9) is algorithm-dependent, and will prove in Section it is satisfied by numerous practical schemes. In Assumption 5, equation (10) is a commonly used condition in the literature [42], while (11) imposes mild growth condition the step size, which remains satisfied even for slowly-decreasing step-sizes such as Yk+1 (og k) Therefore, this condition is not overly restrictive and accommodates a wide range of scenarios. logk))
On dissipativity. In the context of dynamical system theory, it is important to ensure that the iterates of stochastic approximation schemes have bounded second moments. In the literature, this requirement is often met by imposing dissipativiry-tyen conditions. Building upon this concept, we introduce the following definition:
Definition (Average Dissipativity). We call the drift be (a,, -)iiisiipteeeee on average for some > () and B E R, if for all probability measures fr P2RR)), it holds
f (v.,(x, pldx) -a |x| ((xx) (((xx))x2 B.
The concept of average dissipativity, as introduced in Definition 2, provides a novel formulation specifically designed to capture the dissipativity property of a drift function that depends on measures, as in equation (Sys-SDE). In contrast to the traditional notion of dissipativity [19], which focuses on the dissipative behavior of individual particles in isolation, this formulation allows for a more fine-grained control over the collective behavior exhibited by N particles, each running in parallel with the same stochastic approximation scheme. Section 4, we will provide concrete examples from the applications of machine learning to demonstrate the satisfaction of average dissipativity.
5

---

3,4 Main Results
We are now ready state our main theorem, whose proof can be found in Appendix B.
Theorem 1. Consider the algorithm (SAA), where the drift and diffusion satisfy Assumptions 1-3, and the step-sizes {Yk-1) and the perturbations (Pkr) satisfy Assumptions 4 and 5. Then the following holds:
The interpolation (Int) of iterates of the algorithm a WAPT of the flow in (Flow).
Moreover, if the drift is dissipative on average (see Definition 2), the iterates of (PSAA) are bounded in second moments, and their limit set is included in that of the original SDE (PSDE).
Proof sketch. The main step of the proof is the construction of the Picard process, which is inspired by [23] and defined as follows:
n = =X, / b(Xytu) du [[d o ((Xetu) (X
(Picard)
The proof is completed in four steps: first, we prove that the Picard process closely tracks the flow (Flow), and then bound the distance between the Picard process and the interpolation (Int). By using martingale convergence arguments, employing our assumption on bias Assumption 4, and Grönwall inequality, we conclude the proof of the WAPT property. Lastly, we show that dissipativity on average ensures a uniform bound on the second moments of the iterates, The convergence is then implied by invoking [23, Theorem 3].
In summary, according to Theorem 1, the convergence of the stochastic approximation scheme in (SAA) can reduced to continuous time counterpart in (Sys-SDE) when the assumptions stated in Section 3.3 are satisfied.
Our Theorem I can be combined with existing results in the finite particle regime to establish the overall convergence towards the desired mean-field limit. To this, let M be N independent processes, synchronously coupled with (Sys-SDE), each starting from X and following
dM..N = bbM,.N .i) dt + (MM .p) dw,
where H,, is the mean-field solution. A common phenomenon in the study of interacting particle systems, known as uniform propagation of chaos [8, 22, 27, 47], implies the existence of constant such that for every N:
sup,20 N ΣM W .M..) s C
(12)
where x, represents the particles following the continuous-timg time dynamics in (Sys-SDE). Letting Mo represent the limit of the mean mean-field equation, straightforward application of the triangle incquality argument, which we defer to Appendix B.2, yields:
lima- t/2 N W2 pco)
m s &
as N - co.
(13)
In other words, as the number particles approaches infinity, the law of the empirical distribution of the particles following the discrete-time algorithm (SAA) also converges to the mean-field solution.
$ A note on the literature. The rich body of literature on McKean- Vlasov SDEs and interacting particle systems offers considerable insights on the convergence of Suler-Maruyana and Milstein type numerical schemes to their limiting mean-fiele equations, e.g., [2, 28, 41J. However, is noteworthy that our study diverges in several key respects: Firstly, work emphasizes and biased drift oracles. This contrasts with the deterministic and unbiased drift oracles considered in the aforementioned studies, making our algorithmic approach broader in scope. Secondly, while those studies present strong finite-timm time error bounds, our convergence results focus on providing asymptotic guarantees. Lastly, we incorporate different underlying assumptions. For instance, need global Lipschitz drifts to ensure globally integrable flows, while one-sided Lipsehitz drifts are allowed in the works by [2, 28, 41]. However, growth condition in Assumption 2 requires control on average, whereas the works mentioned assume stronger pointwise controls.
generie stochastic
In the light of these distinctions, we believe that our work complements this body of literature.

---

4 Applications
The goal of this section is demonstrate the wide-ranging applicability of our framework across diverse domains such as machine learning, game theory, and physics, which were previously analyzed in isolation. In each of these applications, we demonstrate that standard assumptions in their respective domains meet the necessary conditions to invoke Theorem 1. All proof' are deferred to Appendix C.
4.1 Two-Layer Neural Networks and Mean-Field Langevin
Our first application is providing a rigorous guarantee for the training dynamics of wide two-layer neural networks as alluded to in Section 2. To begin, let us quickly recall the notations therein: The noisy SGD iterates in (SGD,r) for wide two-layer neural networks can be viewed as approximations of the mean-fiell dynamics (6) through the discrete-time system (SAA), whose drift term b(:-) is defined in (1). The corresponding continuous-tine and finite-particle dynamics is (5), which has been extensively studied in recent years; see [11, 12, 36-38, 46, 51] and references therein. Under the standard assumptions in [11, 12, 37], a simple application of Theorem then yields the convergence of (SGD,):
Corollary 1. Let K()) denote the activation function. Assume that (1) and k' are Lipschitz and bounded, (2) the data has bounded support, and (3) la (a)) is bounded. Then the discrete-time scheme (SGD,) v) converges in W2 to the same limit sets the continuous-time (5).
The mean-field dynamics for two-layer neural networks converges stationary point Wasserstein space due to its gradient flow structure [12]. In addition, it is known that under fairly mild assumptions, the resulting limit becomes a unique global risk minimizer [12]. By employing uniform propagation of chaos for neural networks [46], it is observed that the limit sets of the continuous-ting N N-particle dynamics exhibit similar generalization error to the global minimizer. Remarkably, Corollary validates that noisy SGD and other discretizations following template (SAA) eventually converge to this limit set, providing justification for the observed generalization behavior neural networks.
& Comparison to prior work. Our result above cannot be directly compared to the existing analysis conducted on the discrete-time scheme (SGD,), namely [37], due to the assumption Al therein, which excludes step-size rules of the form Yk+1 k where B E (1/2. 1]. Conversely, the bounds resulting in
provided in [37] for a constant step-size are -onastyptooicc (albeit doubly-exponentian stronger conclusions compared to our asymptotic results. Therefore, these two analyses complement each other and contribute more comprehensive understanding of the training dynamics exhibited by neural networks.
4.2 Stein Variational Gradient Descent
Sampling from distribution & V is crucial task in various machine learning applications. An effective method that has demonstrated practical success in this regard is the Stein variational gradiens descent (SVGD) [29, 30). Intuitively, this method emulates the steepest descent for the KL divergence in continuous- with a continuous probability measure. In practice, the algorithm is implemented interacting particle system follows (see [33] for a derivation). Let K : RR x Rd R be positive definite kernel. The SVGD algorithm updates the set of N particles as
xku1 x Yلاا Em
[(x (<xx xV)((())) - V2K(x(.2)))
i= N.
(SVGDz)
where V,K is the gradient of K with respect to its second input. The corresponding continuous-time dynamics is then:
i= which is special case of (Sys-SDE) with bxx, (V2K * (x) - (K (xVV))(x and o = (no diffusion), where denotes the convolution operator. We now prove:
E, = x/) E, X
(SVGD,)
Corollary 2. Suppose that (1) VV(x) is Lipschitz. (2) V is dissipative," (3) for some C
[VV()) C(1 + Ixl2), (4) || [lse, K|V2 || co, (5) 1V2K(x, y)1 S n/Ix yl. and
(6) Kx. y) S 1/11x- y12 for some n > O. Then the iterates in (SVGD)) converge in W2 to the same process (SVGD,).
limit sets as the continuous-tin
That is, 3m 0. m' E R such that (x. vV(x)) mxx 3-m2mm
7

---

Similar to neural networks training discussed in Section 4.1, the mean-field SVGD also exhibits a gradient flow structure, and in this case, the target distribution π serves as the only limit set for the mean-field SVGD [29]. Combining Corollary 2 with uniform propagation of chaos argument for SVGD then confirms that the iterates of (SVGD;), or any discretization of (SVGD,) that satisfies Assumption 4, effectively converge to distribution that closely approximates π in terms of W2. This outcome underscores the effectiveness of these algorithms in sampling.
$ Comparison to prior work. While there has been extensive theoretical work the convergence of SVGD, most of it focuses on either the population limit (i.e., when N - oo in (SVGD;)) )) or the vanishing step-size (which directly examines the properties of (SVGD,)) [10, 14, 25, 29, 43, 45]. However, the convergence behavior of the discrete iterates (SVGD)) remains a challenging task with limited success. To the best of our knowledge, the only existing work in this direction is [44], but its result is not directly comparable to ours. Although our assumptions on the bounded derivatives of V and W are similar to those in [44], the difference lies in the requirement imposed on the target distribution e e-V. Specifically, Shi and Mackey [44] assume a T T1-inequality on e V [50], whereas our work requires V to be dissipative. Notably, our approach holds a significant advantage over [44] in terms of simplicity: The result of [44] is only applicable to highly specific and fairly complicated step-size rule (see [44, Cor 2]). whereas our sole requirement on Yk+1 is the standard Assumption 5. However, it should be noted that the bounds in [44] are non-asymptotic (albeit doubly- doubly-exponential in N and exponential in k), while we can only handle asymptotic convergence.
Remark. It is worth mentioning that Corollary 2 can be straightforwardly extended to the Stochastic Purticle- Optimization Sampling algorithm of Zhang et al. [53], which is identical to SVGD but includes a constant diffusion term o > O. Since the analysis remains the same, we omit the details.
4.3 Two-Player Zero-sum Continuous Games
Min-max learning appears in several important machine learning tasks such as Generative Adversarial Networks [18] and adversarial training [35]. These learning problems can be formulated as a continuous zero-sum game between min-player and max-player. The min-player selects strategies from the set X' c Rd, while the max-playe pla-el selects strategies from the set y C Rd, with the goal of finding a saddle point of function ((x,)) y):
min max K(x.g).
(14)
x yey
However, solving (14) becomes challenging and sometimes impossible when K is non-convex in x and non-concave in y. as a solution to (14) may not even exist. To address this issue, mixed Nash equilibriums (MNEs) are introduced, where the pure strategies are replaced by probability distributions over the sets of strategies, which exist under mild assumptions on K [13, 17].
Specifically, an MNE is represented by a pair of measures (n*,, y*) E (2( x P2()), forming saddle point of the functional E(H, v) == Jf ((x, ()x,)))((xxx)() The quest for efficient solutions to the MNE problem in machine learning has led to the development of particle-based methods that offer approximate solutions [13, 20, 34J. However, the existing studies have primarily focused on analyzing the continuous dynamics of these methods. Below, we shift our focus to the more practical setting of the discrete-time system of interacting particles in these work:
Xxpm = x Yk+1 N Σj K uf) + 22TYKA Ee4) 1he = 1/. +ay++1 N Σj (y 1/) + - ZaTyksl E241
(GDAa)
where f and kk+1 are independent standard Gaussians, T > O is a hyperparameter chosen by the user, and a is the scale difference between the two players [34]. We will additionally consider the optimistic version of (GDA2) in [20], which has shown empirical benefits over (GDAA):
Xxhni = x - 7 Φ Ej
(6) v KK(
( kk-1))= + +TTYET Eke
(OGDAz)
Uaei = U/2 + +ayx+1 + Σ (2 v, x-1 1)= (arrya- sko
At first glance, may seem that (GDAa) and (OGDA,) are distinct algorithms that cannot be analyzed together. However, subsequent corollary reveals that these systems actually converge to the same
8

---

continuous-timg time dynamics:
dx; - Σ, VxK(X, ,.) dt v2rdW; dY; = & E, V,K(X), ()) (2
(GDA,)
where w and BY collections of i.i.d. Brownian motions. The key enabling factor for this unified treatment to allow for a non-zero bias in the algorithmic template (SAA).
To facilitate the analysis, we introduce pairing of players' particles by setting Q = (X) R2d
and define the drift b IR2d x (2 2d) 2d
b(q. /
4.K(q).42) u(dq), q (q1 q2), Vv
and the diffusion (q. ()) V2 diag( Va laxa). By doing so, we can then cast (GDA,) in template of (Sys-SDE).
Corollary 3. Assume that (1) X and y are Lipschitz, and (2) V x and -VyK are dissipative, or (2') the domains X and y are bounded. Then the al algorithms (GDAa) and (OGDA)) converge in W2 to the same limits of (GDA,).
We note that the assumptions in (3) are mild and are even required for analying the continuous-tin time dynamics; e.g.. [34]. Consequently, consideration of continuous-time dynamics in existing studies such as [13, 20, 34).
Corollary 3 provides rigorous foundation for the
Remark. The schemes (GDA2) and (OGDAz) above rely on simultaneous updates, i.e., from (xx. yk). one obtains (XK+1. (k+1) However, empirical evidence suggests that alternating updates i.e., fol- lowing (xx, 9x)) - (xk+1, 9x)) - (XK+1, 9k+1), often preforms better. Our framework allows for this flexibility, as is easy cast the alternating (GDA2) and (OGDA²) as stochastic approximation schemes satisfying Assumption 4, see [24, Proposition 4] for an example of this argument.
4.4 Kinetic Equations
In this section, we study the kinetic equations defined the space of probability measures. Initially emerging from the physics community, these equations have recently gained attention in the machine learning community due their connection to Wasserstein gradient flows [15, 32, 39, 40, 48, 49, 52]. Here, we denote p as probability density, and we examine three distinct "energy" functionals: an internal energy U, potential energy V, and an interaction energy W. These functionals are defined as follows:
u(p) = f- U(p(x)) dx, V(p) = ( V(X) WG)) = f W(x - g) ((dx)
(15)
The most interesting scenario is when U(s) = s slogs represents the entropy, in which case the Wasserstein gradient flow with finite particles becomes [5, 7]:
dx VV)()) dr + Σ VW(X: - x/) dr + v2dw;
i= I..,..., (Kin-SDE)
By setting b(x, n1 VV - (VW * (x) and (xx p) = v2, we again see that (Kin-SDE) is special case of (Sys-SDE).
In the physics community, the equation commonly simulated using a system of interacting particles through the proximal point method [6, 48]:
x = x - yk+1 (VV((()))))))))))( -VV-L(VV(X( + A ΣN (W(x(.1-xX) -x²)) 22 E
(Kin-Prox)
Note that the right-hand side of (Kin-Prox) involves the next iterates x so that, as opposed to the simple Euler discretization, it an implicit rule. The key factor that enables the application of our framework to these implicit schemes is the observation that IKin-Prox, can be formulated as stochastic approximation scheme (SAA) by incorporating a non-zero bias term; see Appendix C. Our next result provides a rigorous guarantee for these methods:
Corollary 4. Assume that (1) V is dissipative and VV is L-Lipschitz (2) W is symmet- ric and VW is L-Lipschitz (3) There exists some Mw 2 O such that for all x, Rd (x VW(y). y) 2 Mw. Then, the iterates (Kin-Prox) converge Wa to the same limit sets (Kin-SDE).

---

We remark that the convergence of (Kin-Pront under these standard assumptions is known 48]. However, we emphasize that the aforementioned results only apply to deterministic updates. while our proof is robust enough to accommodate updates with finite-variance noise. This flexibility sets our approach apart, allowing for broader range of practical applications.
5 Conclusion and Future Directions
In conclusion, our work has successfully bridged the gap between continuous- and discrete-time schemes by establishing the convergence discrete-time algorithms to their continuous-ting coun- terparts, drawing inspiration from dynamical system theory. This achievement offers a flexible framework that can accommodate practical schemes and unify tasks from various domains, including machine learning, game theory, and physics. By introducing a comprehensive framework for analyz- ing stochastic approximation schemes, providing convergence proofs, and presenting easily verifiable conditions at the finite particle level, our contributions enhance the understanding and application of stochastic approximation schemes for simulating interacting particle systems.
In our future works, we will explore the exciting possibilities offered by the dynamical system theory of [4] to derive convergence rates through d-pseudotrajectoriee, This avenue of research will allow us to establish exponential convergence for dynamics using smaller step-sizes after a "burn-in" time, thereby sharpening our understanding for the long-term behavior of these practical schemes.
Additionally, we aim to relax the Lipschitzness assumption on the drift and expand the scope of guaranteed algorithms, such as the Ensemble Kalman Sampler [16]. We also aim to explore further applications in natural sciences, including stochastic mean-field FitzHugh-Nagumo models and networks of Bondgkin-Huxleyy neurons [1]. These models important because they provide mathematical description of neuronal dynamics, contribute to our understanding of neurological disorders, and inform the development of brain-computer interfaces. By leveraging our novel framework, we hope to offer rigorous guarantees for the algorithms employed these domains while also designing new, efficient approaches that can support computational neuroscience research.
Acknowledgments and Disclosure of Funding
This work was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program grant agreement No 815943. YPH acknowledges funding through an ETH Foundations of Data Science (ETH-FDS) postdoctoral fellowship.
References
[1] Javier Baladron, Diego Fasoli, Olivier Faugeras, and Jonathan Touboul. Mean Field description of and propagation of chaos in recurrent multipopulation networks of Hodgkin Haugkin-Huuleyy and Fitzhugh-Nagumo neurons, October 2011.
[2] Jianhai Bao, Christoph Reisinger, Panpan Ren, and Wolfgang Stockinger. First-order con- vergence of milstein schemes for LecKenn-vlaoo equations and interacting particle systems. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 477 (2245), January 2021. doi: 10. (0.10998/spa.222000256 URL pettp::/ddii.oggg/ 1098/
rspa. r020.2020.. 0258.
[3] Michel Benaïm. Dynamics stochastic approximation algorithms. In Seminaire de probabilites XXXIII, pages 1-68. Springer, 2006.
[4] Michel Benaim and Morris W Hirsch. Asymptotic pseudotrajectories and chain recurrent flows, with applications. Journal of Dynamics and Differential Equations, 8(1):141-176, 1996.
[5] Dario Benedetto, Emanuelle Caglioti, José A Carrillo, and Mario Pulvirenti. A non-maxwellian steady distribution for one-dimensional granular media. Journal of statistical physics, 91: 979-990, 1998.
[6] Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-21,, 1967.
10

---

[7] Patrick Cattiaux, Guillin Amaud, and Malrieu Florent. Probabilistic approach for granular media equations in the non uniformly convex case. March 2006.
[8] Louis-Pierre Chaintron and Antoine Diez. Propagation of chaos: review of models, methods and applications. i. models and methods. Kinetic and Related Models, 2022. doi: 10.3934/krm. 2022017.
[9] Louis-Pierre Chaintron and Antoine Diez. Propagation of chaos: A review of models, methods and applications. II. Applications. Kinetic and Related Models, 15(6):1017, 2022. ISSN 1937-5093, 1937-5077. doi: 1..934//kmm20220115
[10] Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, and Philippe Rigollet. Svgd as a kernelized wasserstein gradient flow of the chi-squared divergence. Advances in Neural Information Processing Systems, 33:2098-2109, 2020.
[11] Lénaïc Chizat. Mien-field langevin dynamics: Exponential convergence and annealing. Trans- actions on Machine Learning Research, 2022.
[12] Lênaïc Chizat and Francis Bach. On the Global Convergence of Gradient Descent for Over- parameterized Models using Optimal Transport. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[13] Carles Domingo-Enrich, Samy Jelassi, Arthur Mensch, Grant Rotskoff, and Joan Bruna. A mean-field analysis of two-player zero-sum games, May 2021.
[14] Andrew Duncan, Nikolas Nüsken, and Lukasz Szpruch. On the geometry of stein variational gradient descent. arXiv preprini 1rXivv19/2.000
2019.
[15] Alain Durmus, Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. An elementary approach to uniform in time propagation of chaos. Proceedings of the American Mathematical Society, 148(12)553775538, 2020.
[16] Alfredo Garbuno-Inigo, Franca Hoffmann, Wuchen Li, and Andrew M Stuart. Interacting langevin diffusions: Gradient structure and ensemble kalman sampler. SIAM Journal on Applied Dynamical Systems, 19(1):412 441, 2020.
[17] Irving L Glicksberg. further generalization of the kakutani fixed theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 311:1170-174 1952.
[18] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Communications of the ACM, 1444 2020.
[19] Jack K. Hale, Asymptotic Behavior of Dissipative Systems. American Mathematical Society, 1988.
[20] Ya-Ping Hsieh, Chen Liu, and Volkan Cevher. Finding mixed nash equilibria of generative adversarial networks. In International Conference Machine Learning, pages 2810-2819, 2019.
[21] Ya-Ping Hsich, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-man max optimiza- tion algorithms: Convergence to spurious non-critical sets. In International Conference Machine Learning, pages 4337-4348. PMLR, 2021.
[22] M. Kac. Foundations of Kinetic Theory. Proceedings the
the Third Berkeley Symposium on Mathematical Statistics and Probability, Volume 3: Contributions Astronomy and Physics, volume 3.3, pages 171-198. University of California Press, January 1956.
[23] Mohammad Reza Karimi, Ya-Ping Hsich, and Andreas Krause. A dynamical system view of langevin-based non-convex sampling. arXiv preprint arXiv:2210.1386; 2022.
[24] Mohammad Reza Karimi, Ya-Ping Hsieh, Panayotis Mertikopoulos, and Andreas Krause. The dynamics of Riemannian Robbins- algorithms. In COLT 2022-35th Annual Conference on Learning Theory, pages 1-31, 2022.

---

[25] Anna Korba, Adil Salim, Michael Arbel, Giulia Luise, and Arthur Gretton. A -onmsyymio analysis for stein variational gradient descent. Advances in Neural Information Processing Systems, 33:4672-46822 2020.
[26] Daniel Lacker. Mean field games and interacting particle systems. preprint, 2018.
[27] Daniel Lacker and Luc Le Flem. Sharp uniform-ing in- propagation of chaos. Probability The- ory and Related Fields, February 2023. ISSN 1432-2064. doi: 10. 1007//0004400023-001 192-x.
[28] Gunther Leobacher, Christoph Reisinger, and Wolfgang Stockinger. Well-posedness and numerical schemes for one-dimeniional McKean-vlasov equations and interacting particle systems with discontinuous drift. BIT Numerical Mathematics, 62(4): May 2022. doi: 10. (0.10077/1100443-02--099220
URL htttps://dot http///toooorg///////
[29] Qiang Liu. Stein Variational Gradient Descent as Gradient Flow, November 2017.
[30] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. Advances in neural information processing systems, 29, 2016.
[31] Qiang Liu and Dilin Wang. Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm, September 2019.
[32] Wei Liu, Liming Wu, and Chaoen Zhang. Long- Time Behaviors of Mean-Field Interacting Particle Systems Related McKean Vlasov Equations. Communications in Mathematical Physics, 387(1):179 214, October 2021. ISSN 1432-0916. doi: 10.1007/s00220-021 -04198-..
[33] Jianfeng Lu, Yulong Lu, and James Nolen. Scaling limit of the stein variational gradient descent: The mean field regime. SIAM Journal on Mathematical Analysis, 51(2):648 67116,6166 2019.
[34] Yulong Lu. Two-Scale Gradient Descent Ascent Dynamics Finds Mixed Nash Equilibria of Continuous Games: A Mean-Field Perspective, January 2023.
[35] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 2017.
[36] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115(33): E7665-E7671, 2018.
[37] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: Dimension- bounds and kernel limit, February 2019.
[38] Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Convex Analysis of the Mean Field Langevin Dynamics. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 9741-9757, PMLR, May 2022.
[39] Felix Otto. The geometry of dissipative evolution equations: the porous medium equation. Communications in Partial Differential Equations, 26(1-2):101-174, 2001. doi: 1081/
PDE- 100002243.
[40] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends& in Machine Learning, 11(5-6):355-077, 2019.
[41] Christoph Reisinger and Wolfgang Stockinger. An adaptive guler-maruyany scheme for McK- ean-vlasov SDEs with super-linear growth and application to the mean-field FitzHugh nagumo model. Journal of Computational and Applied Mathematics, 400:113725: January 2022. doi: 10.1016/j.cam.2222 1137225. URL https:/ //tpi//diii..o http//ii..go//////// www.ooog///o http:/10.11180 1016/j cam. 2021. 113725.
[42] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[43] Adil Salim, Lukang Sun, and Peter Richtarik. A convergence theory for svgd in the population limit under talagrand's inequality t1. International Conference on Machine Learning, pages 19139-19152. PMLR, 2022.
12

---

[44] Jiaxin Shi and Lester Mackey. A liite-ppatiie convergence rate for stein variational gradient descent. CoRR, abs/2211.0972. 2022. doi: 10.4855Warxxw.22111.9922 URL https:
[45] Lukang Sun, Avetik Karagulyan, and Peter Richtarik. Convergence of stein variational gradient descent under a weaker smoothness condition. In International Conference on Artificial Intelligence and Statistics, pages 3693-3717. PMLR, 2023.
[46] Taiji Suzuki, Atsushi Nitanda, and Denny Wu. Uniform-in -n-timmm propagation of chaos for the mean-field gradient Langevin dynamics. In ICLR, 2023.
[47] Alain-Sol Sznitman. Topics in propagation of chaos. In Donald L. Burkholder, Etienne Pardoux, Alain-Sol Sznitman, and Paul-Louis Hennequin, editors, Ecole d' Eté de Probabilités de Saint- Flour XIX - 1989, Lecture Notes in Mathematics, pages
Berlin, Heidelberg, 1991.
Springer. ISBN 978-3-540-4631944 doi: 10. 10.1007/BF00085669
[48] Juan Luis Vázquez. The porous medium equation: mathematical theory. Oxford University Press Demand, 2007.
[49] Cédric Villani. Topics in optimal transportation. Number 58. American Mathematical Soc., 2003.
[50] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
[51] Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference on Learning Theory, pages 3635- 3673. PMLR, 2020.
[52] Rentian Yao, Xiaohui Chen, and Yun Yang. Mcan-field nonparametric estimation of interacting particle systems. In Conference Learning Theory, pages 2242-2275. PMLR, 2022.
[53] Jianyi Zhang, Ruiyi Zhang, Lawrence Carin, and Changyou Chen. Stochastic Particle- Optimization Sampling and the Non-Asymptotic Convergence Theory. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pages 1877- 1887. PMLR, June 2020.
[54] Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, and Marcelo Pereyra. Wasserstein Control of Mirror Langevin Monte Carlo, arXiv:2002.0453 [cs, math stat], February 2020.
13

---

A Properties of Mean-field Transfer to Particle System
Lemma A.1. The Assumptions 1-3 transfer seamlessly to the aggregated notions of drift and diffusion given in (7);
1. If .f.,) and o(++)) satisfy Assumption 1, then b()) and o-)) are L(VN + L)piiscchiz.
If b(,,) satisfies Assumption 2, then b() satisfies the same condition with the constant VNC,-
If (fo(..) satisfies Assumption 3, then the same holds for (-)) with constant VNK.
Proof. We prove these statements separately:
1. Let x, (N and define |xr y'l. First, notice that W (4xx My) N E as the average on the right-hand-side corresponds to the specific coupling of x; + yi- Now, observe that
[b(x) b()) - Ibb('' :x) -b(y Hn)l
$ L2 E(ar + (2(m)xHHy)
$ L2 ai
/
| N
Σ a))
Let and notice that the last quantity above is equal to
22 = 2| la
2 1
22 aa
Iall- 1
V
I N
s
L
1+ vV
This means that
(xx) - b()) L(VN 1) yl.
For the diffusion, suffices to notice that
[|o -
- (v)
Ellord'' = - oiy My)ll
The rest of the proof is similar to the one for the drift.
We have
N N (x. = N Eee. s Col EN++ Co( Elxi 1),
1
where in the last inequality, we used Cauchy-Schwar Schwarz. This implies b(x)) s C,VN((x)+1), 3. It is easy that
= =
Σ tr(o ux) Tx( .x)) s NK2.
Lemma A.2. b(., is () diissipaiee on average, then b(.) is (B), in the usual sense, that is, for all x (R (x,)(x)) -a|x NB.
Proof. Observe that for E (Rd)8M 8N we have
N (x. bxx)) = N
Σ
(x, b(x ux)) = Ep, [l, b(y s -a E 2 +B
i=1
N
Axf 12 + -a 1x| B.
a N
This means that (x. bx)) < =x|xx|2 NB.
14

---

B
The Main Theorem
B.1 Proof of Theorem 1
Recall the Picard process (Picard):
1, = X, / b(Xevu) du+ S-d o (Keea) dw!..
We break down the proof into four steps: first, we prove that the Picard process is close to the flow (Flow), and then we bound the distance between the Picard process and the interpolation (Int). We then conclude the proof of the WAPT property. Lastly, we prove that stability is implied by dissipativity.
$ Distance of Picard from Flow.
L - du + +2E
I ((Xitu)- aw!!l
E (1)
60
s 2E $ T % EIb(D! - b(X du + 2E / -0(0) )1p du
["END!
$ 2(
Xytul
where we used Lipschitzness of and a (implied by Assumption and Lemma A.1), Itô's isometry (see, e.g., [54, Lemma 3.4]), and Lemma A.1.
$ Distance of Picard to Interpolation. constant interpolation.
We place a bar above a symbol to denotes its piecewise
X = E b(X,)- b(x,) du+ [ (Xx)) - o (Xx) dw AAp(I.s)
s 3(T+ 1)1.
J, IIIx,- du +E)/Ap(1ss)
where Ap(t, s) is the accumulated noise and bias from time / to time / + which is equal to
Sr(t, Σ Pis (t+ T,) E[P Frt) (1 Tk) E[Px+1 [y).
(B.1)
with m(t s) and & m(). It shown in [23] that lim ElAp(r, s) 0, a.s. Continuing to bound the inside the integral, we have
+(t E|X,- xx < 3(r T -t E (x(x))
where we used the fact that conditional expectation is contraction in 2.2, and
(x(r(xx) Ex.1 2 E(r(f(+) (xx)))())))))))))))) (xx))
=Etr((o(xxx) (xx) ExHIET))
=Etr(or(xx)" (xx)) ElEx+1 FT.1)
(x
Moreover, by Assumption we have ( = 0(1). We thus get by Lemma B.
E|x, -1X,-x112 3C72 (1/yk.) + 3C O(rx.)).
This implies
sup E - X $ 2 se[o.]]
Tu + 3 (/3 Ar. *SuSt+
sup
with A, 0 as 00, a.s.
15

---

$ Concluding the proof of APT. By Grönwall inequality,
E|X,+s 0 s C S." E|x 0 A, A, exp(sC) A, exp(TC) 0
0o, Since
W2 (law(Xrts) law law
E|Xr4s - 1
we get the desired result.
$ Stability. Lemma A.2 implies that under dissipativity average, the iterates stable, and as in [23, Theorem 3], we get the desired convergence result.
B.2 On Propagation of Chaos
Theorem shows that the law μæ of Xg E (Rd)&N eN converges in the Wasserstein space to the limit-set (or the internally chain-transitive (ICT) set) (2))))) (NN) of the corresponding flow:
lim inf W2(HK, p)= =0. k-w0 pES
By looking only at the first particle of xg. namely, x and given that the dynamics is exchangeable, follows that
/ 1x yp xdx, dy)
( (1) =inf inf
= inf (ʃ 1x' 2 (dx' dy' +.... f Lo yy x (dxx day
2 inf f Ix' - y2 (dx' dy'))
x²
= W (law(x)))) marginal, (14),
where x' (dx', dy') = f (xx y) dx² dy2 dx dy and we used the exchangability in deducing that the law of of are the same as the first marginal of for all i = I. Hence, as the limit-set S' of the first component of the SDE X is subset of the marginal of S.
lim inf (2lwa(x))) S - YES!
lim inf Lo vemarginal,
(2(law(x)), =0
This means that the first particle converges law to the ICT sets of the corresponding SDE. Assuming uniform propagation of chaos, we also know that the law of X has distance of (1/NN) from the mean-field equation, and hence, we get that the law the particles following the discrete algorithm have controllable distance from the mean-fite ffeld dynamics.
B.3 Supporting Lemmas
Lemma B.1. Suppose Assumptions 1-5 hold. One has = E| O(yr.)) and E| P O(I).
Proof. We repeatedly use the fact that (x) < 2L 2 2 E|b(x))) = 2 E|x, 2 Co. By Assumption 4, 12 z Olrk.,) + +(yk+1), and we have
E|Px+11 < 2| +2E = O(1).
(B.2)
Moreover, as vp+q vp+ + vg. we have
VEIPEnP O(y--1) O(1).
(B.3)
Assumption 3 also implies that (xo s Co.
16

---

Define == E(xx|". Then,
ak+1 ak F Elb(x)) + + P 1 2 2yk+1 E(xx, b(xx) PR+1)
++ 1/2 E(xx (x4) 2 2/2 E(b (XL) + PR+1. (x+)
2L y kk+ 7k+1 Co + 2 E| 2 yk+ICo + C
+y ax E| P + 2y k+1 VC VEIPRIPP
(B.4)
Plugging the bounds from (B.2) and (B.3) into (B.4) gives
ak+1 ak 01 aa O(y++)) O(K++) -rr + Qyk+I RyK+1.
for some P. 2. R 0 that do not depend on k.
We now prove ag & M /y1+1 for some fixed > 0 via induction. Suppose this is the case for k. For k we have
a++1 S (PY241 + 1)ax + (Yx+IVa + Ryk+1
$ ( + 1/yx+1) VMQ RyR+1
$ M/Y222-
The last inequality is equivalent to the fact that the following quadratic equation (in VM) has bounded largest root (and the bound shall not depend on k):
M(Pyk+1 + 1/7k+1 1/yx+2) + VMQ + Ryk+1
Notice that by Assumption 5, the leading coefficient is negative, and the larger root is computed as
@vłk+1 + +VTK+++ + 4R(yx-1/7kx2 Pr
2(1/yk+2 PYR+1 1/7k+1)
2Q 22 R RVRyytsI/Yes 2Q + VR < 2Q VR =: M.
2yx+1 1
The claim for b follows by Lipschitzness, from which the claim for the bias and perturbation follows directly.
C Proofs of Results for Applications
C.1 Two-Layer Neural Networks and Mean-field Langevin
Proof of Corollary Smoothness of drift: We start by showing Lipschitzness with respect the
measure parameter of the drift. First, observe that V -e,,)) -) is Lipschitz:
VV VoW(0,0') (') = EEEz- ((((2, 0') - o(2,0")) Vor(2,0)) 0)]
(IE.-D((x((( 0')) x((z, ("))) x x'( 8)) z]1
s ClØ' 6"1
due to the boundedness of x' and z, and Lipschitzness of k.
Now, consider μ,, (RR)) and let æ be the optimal coupling (in W2 sense) between them. Then, for fixed 0 Rd
- b(0,v)) (olp))bbbb.)))) / Vow(e, Vow(e.)) voW(O)) x(dp.dd)) 2
$ / (
/ Clp - ql2 Slpp.drrddp.do
17

---

Next, we show for fixed measure P2(R4), b), is Lipschitz in the first input.
lb(0. μ) b If (oW((.))
p) v..(:.)) -VV0- -v(())-((()))
Let us treat each term separately, We have
VoW p) VoW(e', p) [Ez-Dlo((, (VVo(((2) Vop(z, f'))]l
(Tt=D((((p,2))(x(((( K <'z,, x)))
s ClE =1
C|0 0'|.
Similarly,
- -V
x'(((', D(dy, dz)] C|e 6%).
Thus,
b) - b(0'v(())) .)) < b(e.)) b(0', v) s L(10 - 0'1 W2(u, v)),
showing b satisfies Assumption 1.
Growth control: First, let us calculate
f (0, (0) u(d0) = If p(z, (0, Peo(2,0)) ((d=))
II y (0, vop(z, D(dy, (2)
f I0p u(de)
l plz, O)
lI yk ((z, (0, (dy (
- -a 101 u(do).
As pp, K', and sDpp(D) are bounded, we can see that
V (6, b(.b 10). C If [ella| ((da))(())) c' / (ell)I sc (10 u(de),
thus, satisfying Assumption 2.
Dissipativity on average: Here we use the extra assumption that |a xa() bounded. We directly bound the terms x' x'(0,, (0, 2) above and obtain
f (0, m(do) s - f 10p2 p(do)) +
C.2 Stein Variational Gradient Descent
Proof of Corollary 2. While the first term in the drift is standard to work with (see Section 4.4), is the second term in the drift that makes it difficult to analyze. Specifically, prove the dissipativity average only for empirical measures. While this would enough for our purposes (and Theorem goes through), it is interesting future direction to when does dissipativity hold in more general setup. Moreover, for simplicity, we only consider the case where the kernel K is of the form K K(x,g) h(x y), for some function h.
Below, we first prove that is dissipative on average, which implies that the law of the iterates will be in compact subset of 5o (RR). Then, we show that is smooth on this compact subset.
18

---

Dissipativity on average; Due to K being symmetric, (2k(x. = (y))),x)). We thus have
] (x y. (2)
[s (x, (2K(xx))) ((dx) |] (u. V2K((x u(dx)u(dy)
= II (x. (x)
If (v. V2K(y)))) (( ((d)))
= 2 If (x. V.VoK(o.))
Thus,
(x. V2K(x, y)) p(dx) - /f (x y, V2, v)) ((d)) s
by Cauchy-Schwarz Schwarz and the assumption that [V2K(x, s n/|x yl. With similar arguments, and using dissipativity of V, we have
lI x VV(V)) u(dx)u(dy)
= Il (x. (c)
1 2 If WV()) vV())) ((dx)u(dy)
2 a If
-|]
1 1fxx/-//0 v13 1/xx v) ( ((dx)
2a a 1f |xPK((x,) y) u(ds))(dg)) B|| K1
Ln 2
As ((x,x) = h(O) and K(x,y) > 0 for all x. y. and that μ is an empirical measure == 1 the last quantity is equal to
N M 6xy
1 N2
1
h(O)
f (wPPu(ar)
Σ
1 Σ K(x),)))
2
N²
N
In total, we derive that b is dissipative on average.
Smoothness of the drift: We have, for μ in compact set of P2(Rd) |b(x, 2) b(x.
f (2K(x,))-Vaa V2K(x', mccu)+ ()()))))(()))+
1 (K(x.)))K(x' K(x',)) u(dy)
s L|x 11x-x1(11 1+ / (VVV pldy))
$ 1|x -x--xx C f (1+ u(dg)) 1.1x--1 x'I-
Moreover, take μ, in the same compact set, and let æ be the optimal coupling (in W2 sense). Then, [b(x. - b(x, r)}
2 / V2K(x.y) (2K(x, x(dy, dz)
2
+ f -(..vvv) ((y. dz)
222
+2/ f ((x. - -Kx.,)VVV+++ K(x,))V(()) K(x, x dz)
19

---

C.3 Two-player sero-sum Continuous Games
Proof of Corollary 3. Recall that
b(q. p1) = ( u(dq'), q= (q(1192)).
Smoothness of drift: For a fixed μ E (IR R and q, 2d we have
/
-V VV,K(q.. 4/))
-V,K(n, 93)
2
1b(q. b(r, b(r,)))
u(dg')
a V 92)
a v 12)
L6\q) 1 + a L 1-
S L-4q - -r
where we used L-Lipschitzness of v.K and VyK. Now, for a fixed q R2dd and μr, v E P2 P2 2 2d with optimal coupling x, we have
(v, 2
lb(9. 1) - b(q, v)
- (
s(dr, dr')
a (r(((1192))
$ 1.2 1f |r2
1r2- - -12l + +ln -1--- r x(frxddr,0 dr')
ril
= (
Average dissipativity of drift: Suppose V and - v are (a. disssiipiee Then
f (q, (q, p(dg)= If (q) (..gvv.(()).9)) (q2 Ky' 42)) a(dq))(ldg)
$ f -aae(qi1 192 ((q)) + +B.
implying that b(.,)) is (aa, 2 on average.
If, on the other hand, the domains X' and y are bounded, observe that by Cauchy-Schwarz
If (q. blg blq. m(da) & If Ieeill
9f)1 [lleillV,x (g1, +l (24 s M,
where M = sup sup supyexxxy 1g12, we see that for any a 0. b(.,)) is (a, M + dii--issippaiee on average, as
K((, 911 +
42)1 Also denoting by R
f fla.ble, ((q 1i) pldq)
/ 1af u(dq) s M + aN
Optimistic algorithm fits Assumption 4: Recall the iterates
denl 4 + yk+1 (2b( (ia) - b(gf/-1-xx-1)) 2 E
where E/,1 = (2 Notice that the bias of this iteration is
6L11 =b(g FTe) - b(g(-11-fa-1).
For brevity, let write Ft F We have
E[1ega1121 Ellgke1 - 4/. - ykoi 7k.i ( (T)) - V2 o E/
s 33Ell l/2l [11)) +322,1 E[|b(g] 12) |
Fx] 61
Moreover, have
Ellgk-1 of(221 1/12
Fx
s 2y..1 El12b(9'- b(g))b 2 + a)d
= =2y2.11 Ellb(g)- f2)) +
11 (1
$ 4y 1 Elle
F + 2y +a)d
20

---

Combining the last two inequalities, we have
Elle P FRl 3 (4 E[| [ 4y E[le || [(x))
+ 3 El (1x 3 67
12 E[| /2 [R + 15y E[ (ix) 5x] 12yk:17(1+a))
Since Yk+1 - 0, assume that 12 1/2, which implies
E[le |[|ek=111 & 30y Ellb(q Am) | 24 add,
which is exactly what we are after.
C.4 Kinetic Equations
Proof of Corollary 4. Smoothness of the drift: Let x, Rd and μ. e E P2((H.) and set be an optimal coupling between μ and y (in W1 sense). Then
lb(x, u) - b(y v) S -VV(x)-VV(C)) VV())+++ /f VW(x- 2W(x-2)
vW(y-2) r(da). -WW--aadt--//WW------a
By L-Lipschitzness of VV, the first term is bounded by L|x yl. For the second term, using the coupling, we can write as
Vw(x- - 21) - vw(y - 22) x xd2),, d22) S I/ -
v z2)1 xT(2), d22)
/f [x 1 - 211-21 π(džı, dzz)
L // [x - yl + 122 - =1 지 dz dz2)
L|x y/ LW1 ( v)
L|x - yl LW2 v).
Putting these together we get
[b(x, - bly. v) s 2L( - yl + W2(H, v)).
Average dissipativity of the drift: First we show that for x Rd and probability measure μ. we have
lf (x. VW 9)) u(dx))(((d)) -Mw /2.
(C.1)
This holds, since
J (x. VW 9) m(dx)p(dy)
= lf (x y--yyy,wWCc y)) ((dx)
= II (x - (L- p(ds) If (y. vw m(ds))(dy)
2 Mw If (v. VW y)) p()()))))ddd))lll((()) ((dx)p(dy))
2 -M - ff (.. (.
9)) p(d)))(())))))))))
where the penultimate inequality we used the assumption (which implies x -M and in the last one, we used the that W is symmetric (which implies VW(-z) -VW(2)), and used Fubini's theorem to exchange integrals. Bringing the last term to the left and dividing by shows (C.I).
21

---

To show average dissipativity, it suffices to observe
-f (x, ((x w)) p(dx)= u()x))))=
f (x, VV(x)) If (x. VW y) ((dy)
2 a / ((dx) - M-
Proximal algorithm fits Assumption 4: Note that this implicit algorithm corresponds to the following proximal step
</41 arg
min min
V(x)
Σ
N W(x - xxx)
x (x) 12yariEuul
2yx+1
By defining the perturbation as
1 N (VW(S - -x()),
P++ = = = -V(c).)
N
we see that the algorithm (Kin-Prox) fits the template (SAA). For brevity, let us write Fy. == F We only have to show that
E| E|
1|x)=
Σ
Elle El = - ((.)).
i=l
We have
|= 2 = VV(Kk)) vv(x))+
Σ
(VW -xx) -ow(rk - -xf1))
j=l
s <2/ Fv(E))2
2 Σ
VW(kke1 -x-) vw(ck x
N
j=l
21. N N
s 221.7/k411 - -xhl= +
Σ k+1 - xx ?
= 4/ - -2l..
For brevity, let
1 f(x)= = VV(x) + N Σ vw(x xx))
noticing that E/T1 = f((kk)) - fxxx). By the update rule (Kin-Prox)
Ellx/-11 xx{1 [ 2y Ellf(((())) 4yk-id.
Moreover, we have that (x( 12 s ((5)) Since Yk+1 - 0, we can
assume that y k+1 < 1.- All in all, this gives
E(lekail 1 Fx | < 4L E[ x [x]
< 8L y (l | 16L
[x)
< 16L 2 - 161 +16 ykild
16L vv Elle/_, (| [1x]+ 1221++16222,,10(/00 162
2 Elle [| + +
This implics that
Ell /2 F5 $ 32L (/1 32L 32L rk.d.
Summing over i and observing that (x = [bxx)) concludes the proof.
22


Reviews:
[{"review_id": "u1ObAskJNr", "reviewer": "Reviewer_MJDT", "summary": "This paper fills a theoretical gap between the application of ideas interacting particle systems to algorithms in machine learning--algorithms, like SGVD, that are almost always realized as discrete-time routines with a finite number of particles--and the substantial existing body of theoretical work on finite particle systems with continuous dynamics. These latter works have yielded valuable insights about, e.g., the training process of two-layer neural networks, algorithm design for approximate Bayesian inference, or the nature of equilibria in games. However, they have not rigorously established the convergence of discrete-time to continuous. This paper establishes that convergence via Benaïm and Hirsch's notion of a Wasserstein asymptotic pseudo-trajectory (WAPT), which gives a measure of asymptotic closeness (in the Wasserstein-2 sense) between two stochastic processes. Specifically, via Theorem 1, the convergence of the family of (discrete-time) stochastic approximation algorithms (SAA) is reduced to its continuous time counterpart. Combining Theorem 1 with existing results in the literature yields the conclusion that the empirical distribution of particles following the discrete-time SAA converges to the mean-field solution, as desired.", "questions": "- For readers unfamiliar with pseudo-trajectories from the dynamical systems literature, a brief footnote or aside giving a terse formal definition may be helpful. The intuitive explanation is mostly clear--the requirement than the orbit X(t) closely tracks the flow over arbitrarily long time intervals T with arbitrary precision--but a formal statement that uses a constant like \\lambda (as I see in line 352!) would likely not strain the reader too much.\n- It may be valuable, in the future directions section or in an appendix, to discuss what kinds of algorithms do not fall under the algorithmic template of the SAA family, as a way to highlight other gaps in the existing mean-field theory.", "limitations": "The authors have adequately address the limitations of their work. I see no potential negative societal impacts.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The central originality of this paper lies in its adaptation of WAPT to solve an open problem in the mean-field theory of discrete-time IPS in machine learning.\nBroadly, I found the clarity and elegance of the mathematical exposition to be exceptionally good. The paper persuasively argues for the importance of a rigorous theory of convergence, and smoothly introduces concepts and definitions needed for understanding Theorem 1, while re-orienting the reader by summarizing previous results at effective moments. After stating the Theorem, the applications of the theory to two-layer NNs, SGVD, games, and kinetic equations were clear and enlightening.\nThe significance of the presented comprehensive framework is high, as the future directions section makes clear.", "weaknesses": "I found the paper without major weaknesses. In terms of the overall presentation of results, I was surprised to see interacting particle systems (IPS) as the frame for this theory rather than simply continuous-time Markov jump processes. I can see the value in specializing to interacting particle systems, but some readers may be deeply acquainted with continuous Markov jump processes and be largely unaware of the IPS literature. Bringing that connection onto the screen by mentioning it in the technical background may help orient readers with a more general stochastic process background.\n\nIn the same vein, a brief mention of the relationship to multi-agent systems could be of value in ensuring that this work reaches the wide readership for which its theory is relevant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your input and remarks. We reply to your questions below, and we will revise our manuscript accordingly in the upcoming revision.\n\n> In terms of the overall presentation of results, I was surprised to see interacting particle systems (IPS) as the frame for this theory rather than simply continuous-time Markov jump processes. I can see the value in specializing to interacting particle systems, but some readers may be deeply acquainted with continuous Markov jump processes and be largely unaware of the IPS literature. Bringing that connection onto the screen by mentioning it in the technical background may help orient readers with a more general stochastic process background. In the same vein, a brief mention of the relationship to multi-agent systems could be of value in ensuring that this work reaches the wide readership for which its theory is relevant.\n\nWe thank the reviewer for bringing this up. Indeed, we have altogether omitted the discussion related to Markov jump processes via passing to the mean-field limit $N\\rightarrow\\infty$. A similar remark holds for the multi-agent perspective: The mean-field game perspective allows us to bypass it analytically, but we agree that expanding upon these perspectives could enhance the clarity and understanding of our work.\n\n> For readers unfamiliar with pseudo-trajectories from the dynamical systems literature, a brief footnote or aside giving a terse formal definition may be helpful. The intuitive explanation is mostly clear--the requirement than the orbit X(t) closely tracks the flow over arbitrarily long time intervals T with arbitrary precision--but a formal statement that uses a constant like $\\lambda$ (as I see in line 352!) would likely not strain the reader too much.\n\nWe thank the Reviewer for this reminder: We have indeed defined the concept of a WAPT early-on (line 139). The other concept ($\\lambda$-pseudotrajectory) is stronger than the usual APT, and gives stronger results such as asymptotic rates, which is left for future work (see lines 351-354).\n\n> It may be valuable, in the future directions section or in an appendix, to discuss what kinds of algorithms do not fall under the algorithmic template of the SAA family, as a way to highlight other gaps in the existing mean-field theory.\n\nA prime illustration of this is the *adaptive* schemes, like Adam, for training wide two-layer neural networks. Yet another very important example that our theory does not have guarantees for is the Ensemble Kalman Sampler, which we mentioned in the conclusion. Even though this algorithm follows the SAA template, one does not know *a priori* if the diffusion coefficient is bounded in Hilbert-Schmidt norm. Proving convergence of these algorithms is challenging (even in continuous-time) and we do not yet know how to deal with such problems. \n\n---\nWe hope that the above addresses your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "mqUONccPLo", "reviewer": "Reviewer_UKxL", "summary": "This work considers the convergence of discrete time interacting particle systems to their respective continuous time limits (i.e, McKean-Vlasov type equations) under general assumptions which are applicable to varied contexts like neural networks, kinetic theory, game theory and sampling algorithms.  The finite particle + finite step size algorithms are considered to be stochastic approximations of the mean field limit and convergence is analyzed in terms of dynamical systems theory.  This work considers the notion of weak asymptotic pseudo-trajectory to show that the stochastic approximations are close to mean field limit under general conditions. These are then applied to various specific contexts like neural networks and SVGD to derive convergence bounds. ", "questions": "Please answer the questions posed in the weaknesses section.", "limitations": "The authors have a good discussion on the applicability of their work. I think they should discuss the drawbacks of WAPT better. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The generality of the assumptions and the framework is the main contribution of this work. This enables the authors to derive several useful results in varied domains under a common framework. This can be a useful tool in establishing convergence to mean field limits in new problems without requiring elementary analysis. ", "weaknesses": "1. The notation in the algorithmic template is extremely confusing. Shortening $b(x,\\mu)$ to just $b(x)$ makes it very confusing. Population level SA is also a bad terminology since it confuses the reader about whether this is the mean-field limit (i.e, $n \\to \\infty$) or not (because the mean field limit is often referred to as the population limit).\n\n2. WAPT as the notion of convergence requires more justification. This is so since the continuous process begins at $X_t$, the $t$-th time instant of the discrete time process and the uniform convergence is established as $t \\to \\infty$. What if the initial deviation in the stochastic approximation ensures that $X_t$ itself is not likely to be reached by PSDE ? \n\n3. Assumption 5 is a bit non-standard. Also, I think there is a typo here. Assumption (11) is not satisfied for any decreasing step size sequence since $\\gamma_{k+1}/\\gamma_{k+2} > 1$. Please clarify and state what exact step sizes are allowed.\n\n4. Under specific settings, much stronger results can be derived for convergence when the algorithm is designed specially or under specific assumptions like logarithmic sobolev inequalities (even with finite particles and constant step sizes). This framework precludes such analyses.  (See [A1,A2]). I am not very well versed in the game theory or kinetic theory literature, so I will abstain from commenting on these results. \n\n[A1]  Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction.\n\n[A2]  Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable input and remarks. We are dedicated to addressing your concerns through revisions in our upcoming review. Having taken all your feedback into account, we kindly ask for your consideration in potentially revising the score.\n\n> The notation in the algorithmic template is extremely confusing. Shortening b(x,mu) to just b(x) makes it very confusing. Population level SA is also a bad terminology since it confuses the reader about whether this is the mean-field limit (i.e, ) or not (because the mean field limit is often referred to as the population limit).\n\nWe thank the reviewer for this comment. We can use \"aggregate drift/diffusion\" instead of \"population level drift/diffusion\" and also make the notation for the aggregated drift and diffusion boldface to avoid further confusion.\n\n> WAPT as the notion of convergence requires more justification. This is so since the continuous process begins at , the -th time instant of the discrete time process and the uniform convergence is established as . What if the initial deviation in the stochastic approximation ensures that itself is not likely to be reached by PSDE ? I think they should discuss the drawbacks of WAPT better.\n\nWe thank the Reviewer for bringing forth this question, leading us to recognize that our presentation can be substantially improved by clarifying this misunderstanding: WAPT is **not** intended to serve as a notion of convergence itself. Rather, we **prove** that popular schemes in practice **are** WAPTs, which **implies** convergence to the desirable measures in the standard 2-Wasserstein metric.\n\nTo conclude, the notion of WAPT is an important intermediate step in our analysis framework, not the final convergence result. This nuanced perspective will be highlighted in our forthcoming revision.\n\n> Assumption 5 is a bit non-standard. Also, I think there is a typo here. Assumption (11) is not satisfied for any decreasing step size sequence since... Please clarify and state what exact step sizes are allowed.\n\nThanks a lot for pointing out this typo: Equation (11) should read $\\gamma_{k+1}/\\gamma_k + P \\gamma_k\\gamma_{k+1} < 1 - \\gamma_k$. We will fix this in the final version.\n\nWe also remark that this assumption is not restrictive. For example, one can show that it is met by step-sizes as slow as $1 / (\\sqrt{k} \\log k)$.\n\n> Under specific settings, much stronger results can be derived for convergence when the algorithm is designed specially or under specific assumptions like logarithmic sobolev inequalities (even with finite particles and constant step sizes). This framework precludes such analyses. (See [A1,A2]). I am not very well versed in the game theory or kinetic theory literature, so I will abstain from commenting on these results. \n[A1] Convergence of mean-field Langevin dynamics: Time and space discretization, stochastic gradient, and variance reduction.\n[A2] Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation\n\nThank you for your insightful comments and references. While the Reviewer has rightfully pointed out that much stronger results can be derived under additional assumptions, we argue that our analysis *complements* instead of \"precluding\" stronger assumptions such as LSI: In scenarios where establishing LSIs proves challenging, such as in multi-agent systems or SVGD, our theory demonstrates that existing schemes still converge under remarkably mild conditions.\n\nAdditionally, we highlight that when strong assumptions like LSIs are present, it is possible to enhance the notion of asymptotic pseudo-trajectories to its non-asymptotic counterpart, known as the $\\lambda$-pseudo-trajectories. However, as our primary focus lies in the generic setting where such assumptions are unavailable, we have chosen to defer these studies to future work.\n\n---\nWe hope that the above addresses your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors"}, {"review_id": "W7GqaZANzu", "reviewer": "Reviewer_S8Cs", "summary": "This paper develops a theoretical mathematical framework to characterize the convergence properties of discrete particle systems to their mean-field limit.", "questions": "I think it would be helpful to provide some examples of how these these theoretical results can help inform and guide ML development, etc. For example, how can I use these convergence guarantees as a design a NN?", "limitations": "Limitations do not seem to be explicitly addressed by the authors.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The mathematical theory in this paper is beyond my scope, but it appears to be mathematically sound. The paper is well-written.", "weaknesses": "I believe that this paper would benefit from some applied tests/results to show practical relevance. For example, how would it help training a GAN? Do the theoretical convergence results help actual training? How do the results compare to actual training? Are the bounds tight relative to actual convergence?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for raising issue of practical relevance. We have taken this concern seriously and made the necessary adjustments to address it in the rebuttal below, which will be incorporated into the revision. \n\nHaving addressed the concerns and made the appropriate changes, we sincerely hope for a re-evaluation of our work based on the constructive discussions we have engaged in. We are open and eager for any further discussions or feedback that can contribute to the improvement and practical applicability of our submission. \n\n> I believe that this paper would benefit from some applied tests/results to show practical relevance. For example, how would it help training a GAN? Do the theoretical convergence results help actual training? How do the results compare to actual training? Are the bounds tight relative to actual convergence?\n\n>Questions:\nI think it would be helpful to provide some examples of how these these theoretical results can help inform and guide ML development, etc. For example, how can I use these convergence guarantees as a design a NN?\n\n\nWe address these concerns together. The strength of our frameworks lies not in the design of neural networks but rather in their **algorithmic flexibility**. We provide two justifications to support this claim:\n\n1. **Providing rigorous guarantees for existing interacting particle systems:** In the machine learning community, exploiting stochastic gradients is a common practice for training large-scale neural networks, even when the algorithm's motivation and analysis are based on *deterministic* gradients. This is evident in methods like SVGD, where literature on stochastic gradients is scarce (cf. Section 4.2). In this context, our framework establishes rigorous convergence guarantees for the important stochastic SVGD methods under the mild assumption that the noise has a finite variance, ensuring the applicability of these popular schemes.\n\n2. **Enabling algorithmic design:** We present a pertinent example in multi-agent learning that is not included in the current version of our submission. The (GDA$\\_k$) and (OGDA$\\_k$) schemes in our paper rely on *simultaneous* updates, i.e., $(x_k, y_k) \\rightarrow (x_{k+1}, y_{k+1})$, as dictated by existing theory. However, empirical evidence suggests that *alternating* updates $(x_k, y_k) \\rightarrow (x_{k}, y_{k+1}) \\rightarrow (x_{k+1}, y_{k+1})$ often performs better. Our framework allows for this flexibility, as it is easy to cast alternating (GDA$\\_k$) and (OGDA$\\_k$) stochastic approximation schemes satisfying **Assumption 4**, and thus, convergence is guaranteed according to our theory.\n\n\n    In a broader context, our algorithmic template facilitates flexible design by merely verifying a few straightforward assumptions. This empowers researchers and practitioners to explore and develop novel algorithms that suit specific requirements and scenarios, such as in the game-theoretic settings mentioned earlier\n\n\n> Limitations do not seem to be explicitly addressed by the authors.\n\nWe will incorporate the above discussions into our forthcoming revision and make sure to highlight the limitations of our framework.\n\n---\nWe hope that the above addresses your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and constructive criticism,\n\nThe authors"}, {"review_id": "ZFMPLuQcRM", "reviewer": "Reviewer_77LN", "summary": "This paper analyses discretisations of mean-field type SDEs arising in several areas of machine learning. The main contribution is a convergence result (Theorem 1) stating that under appropriate conditions on the drift and diffusion coefficients, the discretised dynamics convergence in 2-Wasserstein distance, in an infinite time horizon limit, to the continuous-time system of interacting particles. Using the classical uniform propagation of chaos for interacting particle systems to show convergence to the mean field dynamics. Applications to Two-Layer NNs training by SGD, Stein Variational Gradient Descent, Two-Player Zero-sum Continuous Games and Kinetic Equations are presented.", "questions": "- Can the authors comment on the choice of 2-Wasserstein distance in the WAPT convergence criterion?\n- The authors make repetitive use of the notion of a *limit set*; albeit this is classical in the theory of dynamical systems, it is worth defining it in the main body of the paper.\n- The paper would benefit from the addition of an *idea-of-proof* paragraph following Theorem 1 (still defering the details to the appendix).\n- (This is not necessarily a question targeted to this paper, but more generally to the community working at the intersection between NNs and mean-field dynamics) What are the issues in analysing more-than-two layers feedforward NNs using the language of mean-field SDEs? What about more general architectures such ResNets, RNNs etc. ?", "limitations": "The authors adequately addressed limitations of their contribution and discussed future work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "As outlined by the authors, SDEs of mean-field type arise in several areas of machine learning and statistics as continuous-time and infinite-number-of-particle limits of discrete stochastic difference equations. Therefore, a convergence analysis of the discrete schemes to the their continuous-time counterparts is of high relevance and importance within the modern machine learning landscape. The paper is well-written and clear, its structure is easy to follow. The four examples on Two-Layer NNs, Stein Variational Gradient Descent, Two-Player Zero-sum Continuous Games and on Kinetic Equations nicely demonstrate the applicability of the main result (Theorem 1) to several topics/areas of modern machine learning.", "weaknesses": "There is a rich body of literature on SDE discretisation scheme for McKean-Vlasov SDEs and interacting particle systems [1, 2, 3], that is completely ignored by the authors. The results of these papers concern convergence of Euler-Marayama and/or Milstein type numerical schemes to the limiting mean-field equations when the step size of the solver goes to zero and the number of particles goes to infinity. As far as I see, the main difference in the anlyses is in the notion of convergence in time: the authors consider as convergence criterion the *Wasserstein asymptotic pseudotrajectory* (WAPT), which is a large time behaviour from dynamical systems theory, while in the aforementioned series of paper the convergence is in terms of discretisation step, which is more classical in (numerical) stochastic analysis. Albeit the two notions of convergences are different, I think an in-depth discussion and comparison between the two is required.\n\nI invite the authors to initiate a conversation on the above during the rebuttal period. If a rigorous and fair comparison/discussion is eventually presented, I will happily increase my rating.\n\n**References**\n\n[1] Bao, Jianhai, et al. \"First-order convergence of Milstein schemes for McKean–Vlasov equations and interacting particle systems.\" Proceedings of the Royal Society A 477.2245 (2021): 20200258.\n\n[2] Reisinger, Christoph, and Wolfgang Stockinger. \"An adaptive Euler–Maruyama scheme for McKean–Vlasov SDEs with super-linear growth and application to the mean-field FitzHugh–Nagumo model.\" Journal of Computational and Applied Mathematics 400 (2022): 113725.\n\n[3] Leobacher, Gunther, Christoph Reisinger, and Wolfgang Stockinger. \"Well-posedness and numerical schemes for one-dimensional McKean–Vlasov equations and interacting particle systems with discontinuous drift.\" BIT Numerical Mathematics 62.4 (2022): 1505-1549.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable and insightful review, especially for pointing out the missing references. We will incorporate Reviewer's recommendation in the revision accordingly.\n\n> There is a rich body of literature on SDE discretisation scheme for McKean-Vlasov SDEs and interacting particle systems [1, 2, 3], that is completely ignored by the authors. The results of these papers concern convergence of Euler-Marayama and/or Milstein type numerical schemes to the limiting mean-field equations when the step size of the solver goes to zero and the number of particles goes to infinity. As far as I see, the main difference in the anlyses is in the notion of convergence in time: the authors consider as convergence criterion the Wasserstein asymptotic pseudotrajectory (WAPT), which is a large time behaviour from dynamical systems theory, while in the aforementioned series of paper the convergence is in terms of discretisation step, which is more classical in (numerical) stochastic analysis. Albeit the two notions of convergences are different, I think an in-depth discussion and comparison between the two is required.\n\nWe sincerely appreciate the Reviewer for bringing these references to our attention, which we had indeed overlooked. It is important to clarify several significant differences between our work and the references [1, 2, 3]:\n\n\n- **Generic Stochastic and Biased Drift Oracles**: Our primary focus lies in generic stochastic and biased drift oracles denoted by $b(\\cdot,\\cdot)$, while [1, 2, 3] concentrate on deterministic and unbiased drift oracles. Consequently, our algorithmic framework is substantially more general than theirs.\n\n- **Asymptotic vs Finite-Time Bounds**: On the other hand, our convergence results provide asymptotic guarantees, whereas the results in [1, 2, 3] offer much stronger bounds, explicitly controlling the $\\mathcal{W}_2$ error in finite time.\n\n- **Incomparable Assumptions**: Apart from the aforementioned differences, our work and [1, 2, 3] rely on incomparable assumptions. For instance, we impose global Lipschitz drifts, whereas [1, 2, 3] can handle more general drifts with only one-sided Lipschitzness. On the other hand, our milder growth condition in Assumption 2 requires control on average, while the stronger pointwise controls are assumed in [1, 2, 3].\n\nIn light of these distinctions, we believe that our paper complements the references pointed out by the Reviewer. Moreover, these works raise an intriguing research question: Can the Milstein schemes be adapted as stochastic approximation schemes within our framework, potentially leading to stochastic versions of Milstein schemes that enhance computational efficiency? We look forward to exploring this avenue for future research.\n\n> Can the authors comment on the choice of 2-Wasserstein distance in the WAPT convergence criterion?\n\nThere are two major reasons for adopting the Wasserstein distances in our framework:\n\n- It is a popular metric in the propagation of chaos literature, which our framework relies on. Adopting the Wasserstein metrics therefore allows for a seamless transition from stochastic approximation schemes (finite step-size + finite particles) to its mean-field continuous-time limits (infinitesimal step-size + infinite particles) by combining our theory and the propagation of chaos results.\n\n- It is important that 2-Wasserstein space is a **metric space** on which McKean–Vlasov equations can be seen as a **flow**, both aspects indispensable for invoking the dynamical system theory of Benaïm and Hirsch.\n\n> The authors make repetitive use of the notion of a limit set; albeit this is classical in the theory of dynamical systems, it is worth defining it in the main body of the paper.\n\nWe agree on this point and we intend to include relevant definitions in the revision.\n\n> The paper would benefit from the addition of an idea-of-proof paragraph following Theorem 1 (still defering the details to the appendix).\n\nWe agree with the Reviewer. The main issue preventing us from this was the page limit, which can be easily addressed given an extra page on the camera-ready version.\n\n> (This is not necessarily a question targeted to this paper, but more generally to the community working at the intersection between NNs and mean-field dynamics) What are the issues in analysing more-than-two layers feedforward NNs using the language of mean-field SDEs? What about more general architectures such ResNets, RNNs etc.?\n\nIt is possible to extend our framework beyond two layers: The mean-field limit for multilayer or structured neural networks is a research area with several notable contributions. In particular, [NP], [SS], and [AOY] have explored the mean-field limit for deep networks, while [F] has addressed this topic in the context of ResNets.\n\nThe rationale behind our selection of a 2-layer neural network lies in the pursuit of clarity in representation. By focusing on this simpler architecture, we aim to provide a more straightforward and accessible presentation of our work.\n\n---\nWe hope that the above addresses your questions - but please let us know if any of the above is not sufficiently clear.\n\nThank you again for your input and positive evaluation,\n\nThe authors\n\n\n**References:**\n\n[NP] A Rigorous Framework for the Mean Field Limit of Multilayer Neural Networks by Phan-Minh Nguyen, Huy Tuan Pham.\n\n[SS] Mean Field Analysis of Deep Neural Networks by Justin Sirignano and Konstantinos Spiliopoulos.\n\n[AOY] A mean-field limit for certain deep neural networks by Dyego Araújo, Roberto I. Oliveira, and Daniel Yukimura.\n\n[F] Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks by Fang et al.\n"}]

Author rebuttal:
Dear AC, dear reviewers,

We deeply appreciate your time, input, and thoughtful critiques, as well as your positive evaluation. Your contributions have our sincere gratitude, and all your questions are addressed in a separate point-by-point thread below. 

A focal concern that has emerged pertains to the practical relevance of our paper. In this context, we wish to emphasize that our work brings forth two pivotal contributions with direct relevance for practitioners:

1. **Ensuring guarantees for popular heuristics:** Numerous widely-employed interacting particle systems, such as several stochastic variants of SVGD, currently lack convergence guarantees. Our paper fills this gap by establishing their rigorous convergence, thereby solidifying the reliability of these approaches.

2. **Devising novel schemes:** Through a simple validation of **Assumption 4**, our framework furnishes a template for inspiring novel schemes. An illustration of this potential is elucidated in the discussion with Reviewer S8Cs, where we delve into a concrete application within game theory.

For a comprehensive exploration of the remaining points, we refer you to the specific threads tailored to each reviewer's concerns. As we proceed to the discussion phase, we eagerly anticipate any further inquiries that may arise.

With the utmost appreciation,

The authors

Meta-review: This paper derives an asymptotic convergence analysis of mean field Langevin dynamics. More precisely, it is shown that the discrete time dynamics with finite particles converges that with an infinitely many particles (mean field limit) as the number of particles goes to infinity, and the convergence is analyzed in the infinite time horizon limit (Wasserstein asymptotic pseudotrajectory).  
The authors showed the result under a rather milder assumptions than the usual log-Sobolev inequality, which makes difference from the recent development on the uniform-in-time propagation of chaos. It gives another piece of convergence guarantee on the interacting particle systems. I would like to recommend acceptance.
Decision: Accept (poster)