Mean-Field Langevin Dynamics : Exponential Convergence and Annealing
Authors: Lénaïc Chizat
Venue: Accepted by TMLR ()

Abstract: Noisy particle gradient descent (NPGD) is an algorithm to minimize convex functions over the space of measures that include an entropy term. In the many-particle limit, this algorithm is described by a  Mean-Field Langevin dynamics---a generalization of the Langevin dynamic with a non-linear drift---which is our main object of study. Previous work have shown its convergence to the unique minimizer via non-quantitative arguments. We prove that this dynamics converges at an exponential rate, under the assumption that a certain family of Log-Sobolev inequalities holds. This assumption holds for instance for the minimization of the risk of certain two-layer neural networks, where NPGD is equivalent to standard noisy gradient descent. We also study the annealed dynamics, and show that for a noise decaying at a logarithmic rate, the dynamics converges in value to the global minimizer of the unregularized objective function.

Published in Transactions on Machine Learning Research (08/2022)
Mean-Field Langevin Dynamics: Exponential Convergence and Annealing
Lénaïe Chizat EPFL
lenaic.chizaat@epff.cc
Reviewed on OpenReview: https: // openreview. net/ formm? id- BDquLHi gEm
Abstract
Noisy particle gradient descent (NPGD) is an algorithm to minimize convex functions over the space of measures that include an entropy term. the many-partee particle limit, this algorithm described by Mean-Field Langerin dynamics generalization of the Langevin dynamic with non-linear drift which is main object of study. Previous work have shown its convergence to the unique minimizer via non-quantitative arguments. We prove that this dynamics converges at an exponential rate, under the assumption that a certain family of Log-Soboler inequalities holds. This assumption holds for instance for the minimization of the risk of cerlain two-layer neural networks, where NPGD equivalent to standard noisy gradient descent. We also study the annealed dynamics, and show that for noise decaying at logarithmic rate, the dynamics converges in value to the global minimizer of the unregularized objective function.
1 Introduction
Let (2R4) (resp. (RR)) be the set of probability measures (resp. absolutely continuous probability measures) with finite second moment on Id and let G P2(R)) + R be convex function which is "smooth" in the sense of Assumption below. Our goal to solve problems of the form
min (+) where F+()): = G(A) +TH(m) (E
(1)
with (()) = f'log(
du dd the entropy of and 7 > 0 the ietllarizatiio/mmmpeaaattt parameter. Seo Section for examples problems of this form (typically with T = 0) that arise in machine learning such as the regularized risk functional of wide two-layer neural networks, or Maximum Mean Discrepancy (MMD) minimization.
Noisy Particle Gradient Descent (NPGD)
The starting idea of NPGD is to parameterize the measure -i 8x,- Let X = (X,..., Xm) E (Red)" encode the position of all
μ mixture of m particles μ = / >m particles and consider the function
G (X) G
6x.)
(2)
Then, NPGD is just noisy gradient descent Gm with initialization sampled from fn P2RD)... It is defined, for k 2 0, as
X + = X(k] myVG (X())) + 2 X(0)
Pn 8om
(3)
where > 0 is the step-size and Z[1. [2.... are i.i.d. standard Gaussian vectors (see Eq. equivalent definition of NPGD directly in terms G and its first-vriationn.
for an
When G is linear, i.c G(μ² f Vdp for some smooth V Rd
R, the particles X, are independent and
each follows the (unadjusted) Langevin algorithm (Ermak 1975
Roberts and Tweedie 1996 Durmus and

---

Published in Transactions on Machine Learning Research (08/2022)
Moulines 2017] given by the stochastic recursion
x = [[]] - VVV(X + /2rr
X po
and it is thus sufficient. to choose m = 1 in that case. In the general case of a convex and non-linear G, the particles will interact in non-trivial ways and m should be taken large, so that a mean-field behavior emerges.
Mean-Field Langevin The dynamics obtained in the many-particle mn - oo and vanishing step-size 1j -> limit was called the Meon-Field Langevin dynamics in Hu al. (2021) and is our object of interest. In this limit, the distribution ir of particles at time t kn solves the following drift-diffusion partial differcntial equation (PDE) of McKean- Vlasov lype:
Oap = V V (V(al)) + +TAat
(5)
where V. stands for the divergence operator and V[n] el (R*) is the first-variation of G at μ (sce Definition 2.1). This dynamics, which can be interpreted as the gradient flow of F, under the W2 Wasserstein metric (Ambrosio and Savare 2007), is generalization of the Langevin dynamics to specific form of non-linear drift term.
There is long line of work around mean-field dynamics Dobrushin 1979 Sznitman 1991 (see Lacker 2018
for an introduction and references) which guarantec that NPGD (3) indeed converges to the Mcan-Fiin Field
Langevin dynamics, sometimes with fine quantitalive bounds (Lacker 2021 Mei et al. 2019). As for the behavior of the Mean-Field Langevin dynamics (5) itself, it is shown in (Mei et al.) 2018 Hu al., 2021) that, under suitable coercivity assumptions, (ut) weakly converges to the unique minimizer of Fr as f-> oc.
Moreover, Hu et al. (2021) remarks that the results from Eberle et al. (2019) to obtain quantitative rates apply here, but this argument is restricted to the large noise regime and does not exploit the convexity of G. These works leave open the question of quantitative guarantees without a strong noise assumption.
1.1 Contributions and related work
Our contributions are the following:
We prove that, under a certain uniform log- Sobolev inequality assumption (which is in particular satisfied in the settings of Mei et al. (2018); Hu et al. (2021)), solutions to converge at global The known convergence rate of the Langevin dynamics under a log-Soboley inequality recovered as a particular case when G is linear.
exponential rate to the minimizer of F- (Theorem 3.2
We study the annealed dynamics where the noise = T. is time-dependent and decays as a/ log(t)) and prove that for a > 0) large enough, G(J))) converges towards the minimum of the unregularized functional Fu = G (Theorem 4.1
- In Section 5 we show that our results apply to noisy gradient descent on infinitely wide two- layer neural networks and we provide numerical experiments for G being a kernel Maximum Mean Discrepancy (MMD).
Let us mention that other algorithms to solve problems of the form 1 are possible. Nitanda et al. 2021 proposed a dual averaging scheme which involves sequence of Langevin diffusions and enjoys a O1/l)) convergence rate in the mcan-field limit. For low-dimensional problems, one can resort to discrctizing the measure on fixed grid, which leads to convex problem amenable to standard (Bregman) gradient descent.
algorithms Tseng 2010
The long-time behavior of drift-diifusion PDEs of the form Eq. has been studied in the mathematical physics literature. General convergence rates (under assumptions that imply a large noise in our context) are proved in Eberle et al. (2019). For interacting particule systems with an interaction kernel k (discussed in Scction 5.2), the case where k(x, y) h(r y) with h convex can be dealt with using the notion of displacement converity, see (Villani 2021 Chap. 9.6). In contrast, we rely on standard convexity, which corresponds to positive semi-definite interaction kernel k.
2

---

Published in Transactions on Machine Learning Research (08/2022)
Upon completion of this work, we became aware of the paper (Nitanda et al 2022 which also proves the exponential convergence of the Mean-Field Langevin dynamics with the same proof technique. The main differences between these two works is that they perform a discrete time analysis while we study the annealed dynamics. These works were conducted independently and simultancously.
1.2 Notations
We use || for the Euclidean norm on R For μ, E P2(R*), I[ v) is the set of transport plans, that is, probability measures on Idd x Id with marginals y and v respectively. The Wasserstein distance W2 (IR))) + R4 is defined the square-root of
min / 11 x (2,))))))
W2(u,
(6)
yETT(E.)) (Ra)²
Relevant background on the Wasserstein distance can be found Ambrosio and Savaré (2007) We often identify absolutely continuous probability measures with their density with respect the Lebesgue measure. A funetion / Rd R is said L-smooth if its gradient is L-Lipschitz continuous function.
2
Assumptions and preliminaries
2.1
First-variation and smoothness of
The Mean-Field Langevin dynamics in Eq. (5) involves the first-variation V G, defined as follows. Definition 2.1 (First-variation). We say that G :::(( R admits first-variation at μ P2(R)) if
there ezists continuous function [[n] Rd R such that
Yv E P2(2)) lim (G((1- e)μ Ev) G(u)) / vlul(t)d(--pp (2))..
(7)
c00
If it erists, the fist-variation Vip] is unique up to an additive constant.
The notion of firs--vrriaton appears naturally when studying variational problems over P2 P2(R and its precise definition varies across references, e.g. (Santanbrogio 2015 Def. 7.12). Throughout our work, we make the following regularity assumptions on G.
Assumption 1 (Smoothness of G). For all P2(RR), G admits first-variation Vinl e' (RR) and x), + [v]j](*) is Lipschilz conlinuous in the following sense: there exists L > such that
E P2(D), Vz,yER [VV[n](z) - VV(M())l s L(1 ull + W2(uvv)).
Let us now state a lemma that is useful in our proofs, that gives the evolution of G and H along dynamics (He)eeta))) PP()) that solve the continuity equation (in the sense of distributions):
dep - (142))
for some time-dependent velocity field v E ()) Observe that Eq. (5) is an equation of this form with i = -VViuu] - vV log(H)).
Lemma 2.2 (Chain rulc). Let (He)tE(a,d) be weakly continuous solution to Eq. such that V Vlog(pe) E L²((a, b), (u.)). Then G(px) and H (We) are absolulely continuous funclions of I and il holds for a.e. t E b),
d - / VV[pe] vidaa
d
((e)) / (V log( Juddu.
G(l))
and dt
dt
gd
Proof. Using the vocabulary of analysis in Wasserstein space, the function is displacement convex with subdifferential Vlgg (Ambrosio and Savaré, 2007 Thm. 4.16). Also we prove in Lemma A.2 that G is (-2L) displacceeen convex with subdifferential VV pc]. Then the claim consequence of (Ambrosio and Savare 2007 Sec. 4.4.E).
3

---

Published in Transactions on Machine Learning Research (08/2022)
2.2 Characterization of the minimizer
We recall the optimality conditions for P, which have been proved in several works (see e.g. (Mei et al. 2018
Lem. 10.4) or (Hu et al. 2021 Prop. 2.5)) and require the following assumptions.
Assumption The function G is conver and F, G + TH admits minimizer pt--
We stress that by convexity we mean standard convexity for the linear structure in P2(RR), i.c.
Vp,v E P2(R"), Va e [0, G(ap (1-)) S aG(μ) + (1-a)G(v).
Proposition 2.3. Under Assumplion and the minimizer F. of F unique and salisfies
,4 x Vlut//T
(9)
The uniqueness comes from the strict convexity of H. For Eq. 9 one first derives the first order optimality condition, which require that that 1c, has positive density everywhere due to the entropy term, and concludes. We refer to (Mei et al. 2018 Lem. 10.4) for details.
must be constant 1G--amostt everywhere. Then one shows
2.3
Noisy Particle Gradient Descent (NPGD)
The NPGD algorithm has been defined in Section [ via the function Gm- We now give an alternative definition of this algorithm involving the firs-vvariation V of G.
let V be its first-variation and fix m E N For i E [m]] initialize Assume that G satisfies Assumption !
std randomly Xi. no E P2((R)) and define recursively for 2
Xi Xi, (VV + 22
A = 1 Σ 6x.,
(10)
1=1
where 1) > 0 is the step-size and Zr,k ~ N(O, T) are iid standard Gaussian random variables.
Proposition 2.4. Under Assumption D the two definitions of NPGD in Eq. (3) and in Eq. equivalent.
10 are
Proof. For X E (Rdym and Y E (Red)m define L Em -x, It satisfies the continuity equation S with velocity field (X, + tY,) = Y. By Lemma 2.2 it holds
d Gm X + +X) t di G(me))= /
VV[ua](>> vo(x)ddo(1)) VV] m
Σ
m
Ty.
di
This proves that E [m], m. x, Gm (X) (V(oo((X,) and thus the update equations in Eq. 33 and Eq. are the same.
10
2.4 Mean-Field Langevin dynamics
Given Eq. 10 standard results about mean-field systems tell us that as m + oo, the random measure fis bocomes deterministic, so that in the limit (and taking also the small-step size limit n + 0) the particles trajectories are given by i.i.d. samples from the following stochastic differential equation (SDE)
ax. (X.)d + 2rdBB Xo ~ P40
(11)
= Law(Xx)
4

---

Published in Transactions on Machine Learning Research (08/2022)
where (Bz) is Brownian motion. As mentioned in the introduction, the law (F)) of solution to this SDE solves the following PDE which is our main object of study:
Oap = V (HoVVT + T
(12)
where V. stands for the divergence operator. Standard results about this class of PDFs guarantee its well-poscdness, i.c. the existence of unique solution, under Assumption [ (sce c.g. (Huang et al. 2021 Thm. 3.3) or Ambrosio and Savaré (2007) for an approach based on the gradient flow structure which applies here thanks to Lemma A.2 which states that G is -isplaeemee convex).
Let us now study the convergence of (14420 to the global minimum of F7-
3 Exponential convergence of Mean-Field Langevin dynamics
For 14, E (R())) with absolutely continuous w.r.t. v we define the relative entropy (a.k.. Kullback-Leibler divergence) by
H(ulv) = /
log (d(1)) dr.
(dj
JR.
and the relative Fisher information by
dp
| du. de
[ulvv) =
V
log
Definition 3.1 (Log-Sobolev incquality). We say that P2 (R.) satisfies logarithmic Sobolev inequality with constant > 0 (in short LSI(p)) if for all u E PP(RR) absolulely continuous w.r.l. il holds
1 - (Hlp))
H(lv))
(13)
2p
This inequality can be interpreted as 2-Lojasiewicz gradient inequality for the functional f ++ H (ulv) f Vdu + (2) (where we have posed V logg) v) in the Wasserstein geometry (Otto and Villani 2000) and thus directly implics the exponential convergence of its Wasserstein gradient flow. This corresponds to our objective function in the linear case G(μ) Vdu, and in this case exponential convergence towards minimizers is thus guaranteed when = e satisfies a Log-Sobolev inequality.
In the general case, we make an analogons assumption that such an incquality holds uniformly for e VWd/T throughout the dynamics.
Assumption (Uniform lob-Sobolev). There erists pr such that Vp P2(Rd) holds Viul/T e L' ('R)) and the probability measure e V/ul/T satisfies LSI(pr).
Remember that [[n] is defined up to constant term, and in this section, we fix this constant so that e V/wl/T (Rd). Let recall two criteria for probability measure to satisfy Log-Sobolev inequality:
If VVV pla then e ((Rd) satisfies LSI(p) Bakry and Emery 1985
- v satisfics LSI(p) and = vv E P(Rd) a perturbation of v with a E L (RR) then i satisfies LSI(Ø) with ý = iu vi v (Holley and Stroock 1987).
These two criteria are standard, but many finer criteria are known, such as integral conditions (Wang 2001): Lyapunov conditions (Cattiaux al.] (2010) or criteria for mixture distributions CChn et al.) 2021) (sce also Section 5.1 Our main result regarding the Mean-Field Langevin dynamics 11 is the following.
5

---

Published in Transactions on Machine Learning Research (08/2022)
Theorem 3.2. Under Assumptions 1 and 3 it holds
let E (2((R) be such that Fr (po) < co. For t 2 0,
(r(()) - F.( S ( (F+()(()(()))) -
(14)
Proof. Let v4 e- VVuul/7 By Lemma 2.2 applied to 2 -V[ul vV log(4)), we have
d Fr(e)) - VVV [u]] -V log(u))) du - = di
(15)
Note that although Lemma general results about Wasserstein gradient flows (Ambrosio and Savaré 2007 Thm. 5.3 (v)). Combining this energy identity with the log-Sobolev inequality and Lemma 3.4 it follows
2.2 requires some regularity estimates, they can be bypassed here thanks to
d
F+(4)) -T2((())))) S 2p, (0)TH((UP S -
dt
which is a 2-Lojasiewicz gradient inequality for Fy. By integrating in time we get Eq- 14
In the proof, we see that we could relax Assumption 3 and require the Log-Sobolev incquality to hold only for μ E (2(4)) such that (x( S F-(p)). Also, Assumption only a general assumption that guarantees well- coll-posedness of the dynamics and the energy decay formula Eq. (15); this regularity assumption can be relaxed on a case by case basis. Convergence guarantees in parameter space directly follow from the previous theorem.
Corollary 3.3. Under the assumptions of Theorem 3.2 for t 2 0 we have
1 -2rp (F, (r())) H(eelA) < -e -e-
2e 2xp,t
and
W3 M&)
(F-(Ho) F+())).
TPr
Proof. The first inequality follows from Theorem 3.2 and Lemma 3.4 For the second one, follows from the fact that if v satisfies LSI(p), then satisfies the Talagrand inequality, which states that Vy P2 (2(,,v) v) 2 (Hlv),, proved in Otto and Villani (2000).
The following lemma establishes inequalities which are key to handle the non-lincar aspect of the dynamics (when G is linear, they become trivial equalities). Lemma 3.4 (Entropy Sandwich). Under Assumption 1
2 and let pt be the unique minimizer of Fr. For
all μ E P2d),, letting v = e -V(A/T e P2(R"), holds
(H(M)))) & -
- F+(G)) <
(H())).
Proof. The convexity of G implies that, VH, E P2R)), [G +)u e) +ev) -G()) < G(v) - G(u). So, passing to the limit in the definition the firstvvaiation (Definition 2.1 we recover the usual convexity inequality (interpreting [[n] as the gradient. of G at p)::
G(v) 2 G(p) + f Viulddi p)-
(16)
Invoking this incquality twice with the role of and n² exchanged, it holds - G(p)-
I Vln*dd(H - n²) <
s / Viujd(H- - -4)).
Recalling F,()) G(H) + T - (p), it holds, on the one hand,
(x) F+(#") / / /Vluldu ([uld=+</((w)) -11(4)- -HQ(")
= =Tl((Ul)) TH((4*))) S (Hl())

---

Published in Transactions on Machine Learning Research (08/2022)
On the other hand, using the fact that pr = e-Vi'1/
(Proposition 2.3 it holds
Fr(m) F. / V[u]du - V -+l(x")
=TH((lm") - -
4 Convergence of the annealed dynamics
We now turn our attention to the "anncaled" Mcan-Ficld Langevin dynamics
Opp V (H T:App
(17)
with time-dependent temperature parameter т that converges to O. The existence of unique solution from any Mo E (TE") follows again from the theory of McKean-Vlason equations, now with time inhomogencous
coefficients (see e.g. (Huang et al. 2021 Thm. 3.3)). As a side note, notice that 11 cannot strictly be interpreted as a Wasserstein gradient flow anymore, but some aspects of the theory of Wasserstein gradient flows have been extended to cover the case of time-dependent diffusion coefficients [Ferreira and Falencia-Guevary
2018 Soc. 6.2).
The linear case when G(μ)) f Vd has been considered in numerous works (e.g. Holley et al. (1899)
Geman and Hwang (1986); Miclo (1992); Raginsky et al. (2017); Tang and Zhou (2021) (). It is known in
particular (Miclo 1992) that under suitable cocrcivity assumptions for V and if T C/ colog(t) for some C > 0
large enough, then G(j4) converges to (EP G(n) = min V(r).
Here we show that a similar guarantee holds in our more general context.
Theorem 4.1 (Convergence of annealed dynamics). Suppose Assumplions 1 and hold for all 0, and moreover assume that:
the Log-Sobolev constants satisfy p. 2 Cue
a'/7 Ca
for some a", Co > 0,
G is lower-bounded,
(Tt) is smooth, decreases, and for t large it holds T. az/ log(t) for some a a*. Let pa E P2(Rd) be such that (Po) < co. Then for each > O, there crists C,C² > 0 such that
(r.) Fr.(G))) s Ct (0--(1110 -0-
(18)
and
G(p)) inf < C lo logt
(19)
logt
We can make the following comments:
The lower-bound assumed on is natural when one has in mind the Holley and Stroock criterion given in Section In Section 5 we show a lower bound of this form on a concrete example related to two-layer neural networks.
The bounds of Theorem 4.1 exhibit a two lime-scales phenomenon: the dynamics (wx) converges at a polynomial rate to the regularization path (HC,) (in relative entropy or W3 distance, thanks to the "entropy sandwich" " Lemma 3.4 or the Talagrand inequality) but the regularization path only converges at logarithmic rate the optimal value inf G, because of the slow decay of Tt-
The slow docay of Tr an inconvenience but it cannot be improved. It known that in the lincar case G(p) = Vdu, convergence lost if F decays faster (Holley et al. 1989 Sec. 3) (in fact, taking a/ log(() with 0 too small already breaks convergence).
7

---

Published in Transactions on Machine Learning Research (08/2022)
Proof. Our proof is partly inspired by Miclo (1992). revisited by Tang and Zhou (2021)
Step 1. Consider the function that returns the values of the regularization path
h(T) = Fx(G)
min NEP2(RA)
G(u) + (N).
As an infimuum of affine functions, h is concave and since the minimizer n7 is unique, h is differentiable for I >> O and its derivative is 11(T)= = ((T))=((())) (uद). We focus on t 2 to so that T, aa/ log(t). By Lemma 2.2 applied to U = [V][u + T V log(p4) (here again, the regularity assumptions of Lemma 2.2 can be bypassed using the gradient flow-like structure, see (Ferreira and Valencia-Guevara
2018 Thm. 6.9)), we have
a (Fr((e)) dt
- / [VVimd] + T. Vlgg(() + + -((((())((
--77 (H(()) ((,,))
where we introduced the probability measure i x e -iiil/ On the one hand, we have by the Log-Sole Sog-Sobolev inequality and the "entropy sandwich" Lemma
[11 2 2 Pr. (Pdd)) 2 2p,, To (F., - Fr, (HG)))
On the other hand, by Lemma 4.2 below, it holds for some C2, Cs > 0 independent from and t,
(M)()) H(,)))
< (2n) + T.Ca+ + (r G(uf,)
< CCT((P - (r. + (1 C2T (KT)) G(G)) + +TC
s (Fr - (F, + CC
where in the last step, we used that G is lower bounded and l((T) = F+(U)) is bounded for T E [0, Combining the previous estimates, we get that for any e> > O, there exists C1 C2 C3 > 0 such that
d (Fr((e)) (ME)) S -2p dt
C2 7 (Fr) (r.()) 7 "Cs
(Fr Te
Fr.(EE))
Te
Tt
-0 + C21 (Fr) - Fr. (Mf + C3 logt
1-1
logt
where we used t. = a//lo((), = ()²) and pr, 2 Col-a'/a /a In passing, the first inequality in the above display guarantees that (me) - Fr. (1t) remains finite all time because log T, et, which justifies the fact that we can consider only large enough in the rest of the proof.
It follows that for any >> O such that e < 1 - a² /a, for L large enough and some C, C" > O,
d dt
d
(Fr,(H)) Fr, (xt))) S -Ct # (Fr - Fr,()))) + /Voo//oog(t))
Now define
C² C" 114
Q(1) = (Fr) (( (vt,))
which satisfies
d dt Q(t) -Ct -0 + C² a¹ ah -
E) e), 24
(20)
Observe that the term -C't-1 dominates the two last terms for t large enough. Thus for 2 to large enough, @1(11= < -Ct- -0------((1) which implies Q(1)= < exp()xxp(->o) f x- - As consequence
Fr, Fr((1) - FFr, (4 < C" - +-
exp (-
C (t" - +*,)
8

---

Published in Transactions on Machine Learning Research (08/2022)
and thus Fr. (1)) - Fr. (17,))
t* because k:= 1 8- < 0 and Q(t") is finite. This proves Eq.
18
Step 2. Let us now prove Eq. 19 under the assumption that G admits a minimizer He E P2()). The proof can be easily adapted to the general case by choosing Pb as a quasi-mininizer such that G(u)) S inf G + and taking e arbitrarily small. Remember that h(0) = G(1)) = Fo(uG), so
G(p)) G((5) = (M) Fr. (M7,) + F., (pt,) Fo(45) THH(M) S + +h((T) h()) + C'
where we have used the bound (w,) S C.FT, (1a) + +22 from Lemin 4.2 which is uniformly bounded for 2 0 by some C' thanks to Step 1.
The rest of the proof consists in bounding h(T) - h(0) via an approximation argument. Let (o(x) (2mo²) exp(-Il=1"/(o0)) be the standard Gaussian kernel and let go (x) go y)dμū We consider the transport plan E [ī (a)) given by the joint law of (X, X + 2) for Law(X) = no = 14 and Law(Z)= = 9o. On the one hand, it holds by convexity of
2 G( - G( / Viūo]d[ãoo - -Arl
/ (Vl V(daI(=))dr((,.)>
It follows, using the smoothness bound (x) V(ūa(()) VV) (x v) =ll x=12 and the fact that the Gaussian kernel is centered, that
- (G(io) < (((
L |1 xl/dd(1,)))
[
~0
= 0 + 2
On the other hand, we have by Jensen's inequality for the convex function &p 8 slog(s) and Fubini's theorem:
H())) = f (0 go (o))dp(()) dr
$ { plealo - v))dr)
()ld ddolo) = -1 (1 + log(2
which is the entropy of the Gaussian distribution 9o- Thus have
M(T) - h(O) < inf 0² - 7 (1+ ([+log(2mo²)) s - log(TT)
L
0>0 2
by choosing 0² === =TL. Plugging the value of Tr a/ log(!) we gel, for some C,C² > 0,
G(m) - G(p)) < a (log log 1. log(T)) + CC + C' a
log(t) < C" log log! log
2
logt
In the proof of Theorem 4.1
we used lower bound on the value of H(R) in terms of the functional value that is provided in the following lemma.
Lemma 4.2. Under the assumptions of Theorem there exists C1, C2, C3 > 0 such that for all 0 < T S and E Po (Rd), it holds F+(r) 2 -C3. and
-H() S C.F(()) + C2.
9

---

Published in Transactions on Machine Learning Research (08/2022)
Proof. In the following proof, C, C CT > are constants independent from μ which value may change from line to line. Since by assumption the probability measure v proportional to e-Vlual satisfies a logarithmic Sobolev inequality, there exists C1, C2 > 0 such that Vo E R2, [=))(=>) 2 Ci||æ||2 C2. Indeed, by Herbst argument (Bakry et al. 2014 Prop. 5.4.1), there exists C1 > 0 such that f feCillal [ - < and we conclude using the fact that if f E e (R4) has a Lipschitz gradient and f e/dr < co then f must be upper-bounded.
Letting M2(H) = f [x])), it follows, using convexity of G, that G(u) 2 G(uo)+ + Viuold(u - no) 2 M2 - -C--
Invoking Lemma 4.3 with o² = T/C we have
TH()) 2 - M2 - - rdlog(2rx/(i)
Summing the two previous equations (with the same value of C1), we get that for T S To.
(+(1) 2 (12(()) - C2-
Combined with the fact that - (H) S (2) + C22 get -H()) S (T) CЧ.
See e.g. Mei et al. 2018 Lem. 10.1) for proof of the following lemma.
Lemma 4.3. For E (RR), let M2(u) = J [1=[)dp((x). For any o² > 0, it holds
1
- (H()) Ma(u) + d
5 Applications and experiments
5.1 Noisy GD on a wide two-layer neural network
We now show that our results apply to the training dynamics of certain wide 2-layer neural networks trained with noisy gradient descent.
Let us introduce the formulation of two-neural networks of arbitrary width parameterized by probability measure, which is at the heart of the field-field analysis of the training dynamics (Nitanda and Suzuki 2017
Mei et al. 2018 Sirignano and Spiliopoulos 2020 Rotskoff and Vanden-Fijnden 2018 Chizat and Bach
2018). Consider a input/output data distribution (z,8) ~ D P(R" x R), a loss function E: R - R,, a
"feature function" ((2,x) E C(R" x I2d) and let.
G(p) = E ((v.) ((2, ((zx))))(()) - / ||a|(du((())
(21)
where A is regularization parameter. Typical choices for the loss are the logistic loss Ely, v/) log(1 exp(-yt')) and the square loss Ely.v') = y 1112 and in what follows, l' denotes the derivative of with respect to y'
When f = 1 En. 8z, is an empirical distribution with m atoms/particles, the function Gm derived from G as in Eq. ( is exactly the risk with weight decay regularization for a two-layer neural network width m.
Thus noisy gradient descent for two-layer neural networks equivalent to NPGD with G defined Eq 22
Let us give simple conditions under which our convergence theorems apply in this case.
Proposition 5.1. Assume that & is the square the logistic loss, that | is bounded by K > 0 and that + smooth in uniformly in z. Then Assumptions 1 and are satisfied and the first variation of G is given, for p E P2(Rd) and x E Idd, by
Vin((x) = E e' (v. D()((a')) (an((a))(((( (2,, x)) + 2 1|==11..
Morcover Assumption satisfied when:
10

---

Published in Transactions on Machine Learning Research (08/2022)
is the logistic loss. Then have Pt 2 2e-2k/r
E is the square loss and [βy|2]| S K' a.s. Then we have P 2 e -2((K++K//
Proof. For the computation of the first variation and Assumptions we refer e.g. to Hu et al. (2021). For Assumption 2 G is convex as a composition of a linear operator and a convex function. To see that F admits a minimizer, notice that thanks to the regularization term, the sublevel sets of G are tight and thus peakly-precompact by Prokorov's 's theorem. Moreover, the loss term in G is weakly continuous, the regularization term weakly sover-semiooutinuous (Isc) and H weakly lsc (Ambrosio and Savaré 2007 Sec. 3.2) so, overall, F, Isc. Thus a minimizer je, cxists for all by the Direct Method in the calculus of variations.
Let us derive the power-bound on the log-Soboles constant Pr using the criteria given below Assumption 3 First, by the Bakry-Emery criterion, the probability mcasure & e tेt |a| satisfics LSI(A/T). Also, our assumptions guarantee that the first term in V is uniformly bounded by K - in case of the logistic loss because [e (')\ & or by K(K + K*) - in case of the square loss. We conclude by applying the Holley-Stroock criterion with a perturbation e that satisfies sup vi - inf & - 22// (for the logistic loss) or sup 3 inf v < 2K(K + K')TT (for the square loss).
Limitations of this approach While the previous proposition, combined with our theorems, gives new convergence guarantees for noisy gradient descent on neural networks (in a certain limit), let us stress on the limitations of these results. First, the convergence proof fundamentally relies on the existence of noise and analysis misses the fact that, in certain contexts, G has specific structure (of different nature than the uniform LSI) that in practice seemss to ease convergence and even make the noiseless dynamics converge, see e.g. Bach and Chizat (2021). Second, this approach introduces, in addition to weight decay, an entropic regularization which might be detrimental to the statistical performance. Finally, the risk for a vanilla two-layer neural network with non-lincarity & R + R is obtained from Eq. 211 by taking
((2, x) = aQ(bT2) 2) where (a. R R
(22)
which is not covered by our assumptions (in particular because is not bounded). In the case of the ReLU non-lincarity ((s) = max(0, (0, s}, there is in addition a lack of smoothness issuc. An interesting direction for future research would be adapt this algorithm and analysis in order to cover the case of ReLU non-linearities.
Relaxing the boundedness assumption In Proposition 5.1 we assumed that is bounded in order to obtain casy quantitative bounds on the LST constant, but this assumption is not necessary. For instance, the Lyapunov condition in (Cattiaux et al. 2010, Cor. 2.1) implies that if there exists C₁, C22 C3 >> 0 such that for all μ E P2 ) Vin] (2RRa) and
||ll|2 2 C1, x [V]](()) 2 C2 and Va e Rd v2V[a](=) 2/- -Clld
(23)
then a uniform LSI holds (i.e. Assumption 3 holds).
As an illustration, consider a positively 2- 2-homogeneous and @² (uniformly in 2) function x ++ (xx (this does not cover functions of the form Eq. (22) except in the simple case ó = id; a valid example the square non-linearity (2z 2) = (x 2))). Given the expression of in Proposition 5.1 and invoking Euler's identity x (0 2) (x, =), we have
vv]y[(>) = ( El (v. y, ((2 ((zxa()du(a')) ((2,)) + A||a/11.
So, assuming E' is absolutely bounded by some M > O, the first part of Eq. 23 holds for À large enough, namely X > 2ME (22,, w)] for all S2-1- Moreover, the Hessian lower-bound also satisfied since V is 0-homogencous, Thus, in this simple example, Assumption 3 holds although & is unbounded with a quadratic growth (but this is at the price of requiring a strong weight decay regularization).
11

---

Published in Transactions on Machine Learning Research (08/2022)
5.2 Numerical illustration: kernel Maximum Mean Discrepancy
We conclude this paper with numerical experiments exploring the behavior of NPGD defined in 3 Let us stress that our theoretical guarantees only apply to the mean-field Langevin dynamics recovered in the many-particle and continuous time limit so there remains gap between the theory and the NPGD algorithm.
We consider the torus X (2)((2 and the convex function defined on P(X) by
1 G( / h(,, ((zd))dd()))d / k( v)dp(z)dv()) + 2 k( y)du(z)dv(())
(24)
where & (X x X)) is smooth positive semi-defnite kernel and P(X) a fixed probability measure. This function G can be interpreted as the square kernel Maximum Mean Discrepancy (kMMD) (Gretton al. 2008) between and v. This choice of function is convenient for numerical experiments because its minimum value is known and is 0, attained in particular for v. Although our theory was developed for X = R it is straightforward to adapt it to the torus, and our main convergence results apply, as shown below.
Proposition 5.2. The first variation of G is given, for E P(X) and x E X by
(in((x) = 1 k(r, v)d(u- vv).
Moreover, Assumptions and satisfied with p. 2 ((1 + 2x -1 (inf susup/
Proof. The properties of G and V are obtained by standard arguments. For the oob-oooley inequality, we note that the normalized volume mcasure on X satifies LSI with a constant larger than (1+2m)diamXX) (Ledoux 1999 Thm. 7.3) and here d2) = π vdd. The lower bound on Pr follows by the Holley-Stroock criterion.
In our experiments, we consider d = 2 and the translation invariant kernel k(z, v) = I (1+2 4)-1cco(k((e - 11))) with n frequency components. Because of the frequency cut-off, this kernel is not strictly positive definite, so G admits minimizers other than v (Sriperumbudur et al.] 2010: Simon- Gabriel et al. 2020) although in practice we observed that NPGD was in general attracted towards v. We take as random empirical distribution of m = 10 samples from the uniform distribution on X. We run NPGD with 0.08 and μo being the uniform distribution on X.
m = 50 particles, step-size
Figure Ta shows an example of a large-time particle configuration, with the atoms of v is red and the atoms of La in black (with t large), with a noise temperature = 0.1. Here the mcasure fhe is a noisy version of v*.
Figure Lb shows the evolution of the objective F, = G+TH (up to constant, adjusted for ease of comparison) along the iterations, where the entropy И is estimated using the neighbo estimator (Kozachenko and Leonenko 1987 Singh et al. 2003). We observe the exponential decay of F, towards platcau which we expect to be the global minimum of Fr, up to discretization errors. For small values of т, it is not excluded that the plateau corresponds instead to a suboptimal metastable state.
Finally, Figure Ic shows the advantage of NPGD with simulated anncaling vs. PGD to minimize the unregularized function G. We used a noise temperature that decays polynomially as Tę = 20(1 + 1) where is the iteration count, which is a faster decay than what the theory suggests. At iteration 800, we stopped the noise in order to observe the "quality" of the configuration of particles. We see that the NPGD with simulated annealing consistently outperforms PGD, which gets stuck in poorer local minima.
6 Conclusion
We have proved the convergence of the Mean-Field Langevin dynamics the global minimizer an exponential rate, under natural assumptions that include all settings where (non-quantitative) convergence
Link Julia code reproduce the experiments: httppr//ssituaaacc///hhhaaaapppp
field-iiiid- -ee---------------ge--------
12

---

Published in Transactions on Machine Learning Research (08/2022)
104
0.1
10P
= 0.03
F.b00
G0e Inf6
100
10-2
PGD
NPGD (annealed)
Noise stopped
200
400
600
800
200
400
600
800
1000
Iteration count
Iteration count
(a) Example of a large-time config- uration of NPGD for = 0.1. (red)
(b) Evolution of (+(ee) (aver-
(c) Evolution of G( for NPGD with simulated annealing PGD (averaged over 10 experiments).
aged over 10 random experiments). Curves' height adjusted to end at 1.
atoms of (black) atoms of ji.
was previously shown. We have also proved the convergence of the annealed dynamics for a suitable noise decay.
From higher perspective, analysis-in particular the simple "entropy sandwich" Lemma suggests that often, the guarantees about Langevin dynamics obtained via log-Sobolev inequalities can be generalized to mean-field Langevin dynamics. In this paper, we focused on exponential convergence and on simulated annealing, but other aspects could be considered, such as a direct analysis of the discrete dynamics, which could lead to computational bounds, as done in e.g. (Vempala and Wibisono Langevin algorithm.
2019
Ma et al. 2019 for the
Another interesting direction for future work to develop and study more applications of Mean-Field Langevin dynamics, since many problems can be cast optimization problems of the form Eq. ( This includes
sparse deconvolution problems, mixture models fitting [Boyd et al. 2017 or problems involving optimal
transport Peyyré and Cuturi 2019 Chap. 9).
Acknowledgments
would like to thank Loucas Pillaud- Vivien for orienting me through the literature simulated annealing and Mo Zhou for noticing gap previous version of the proof of Theorem 4.1 would also like to thank the anonymous reviewers for their insightful comments and for suggesting the discussion LSI in Section 5.1
References
Luigi Ambrosio and Giuseppe Savaré. Gradient flows of probability measures. Handbook of differential equations: evolutionary equations, 3:1-136, 2007.
Francis Bach and Lénaïc Chizat. Gradient descent on infinitely wide neural networks: Global convergence and generalization. arXiv preprint wrXiv:2110.0808, 2021.
Dominique Bakry and Michel Emery. Diffusions hypercontractives. In Seminaire de probabilités XIX 1983/84, pages 177-206. Springer, 1985.
Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Nicholas Boyd, Geoffrey Schiebinger, and Benjamin Recht. The alternating descent conditional gradient method for sparse inverse problems. STAM Journal on Optimization, 27(2):616-66 639, 2017.
Patrick Cattiaux, Arnaud Guillin, and Li-Ming Wu. A note on Talagrand's is transportation inequality and logarithmic Sobolev incquality. Probability theory and related fields, 148(1):285-304 2010.
Hong-Bat Bin Chen, Sinho Chewi, and Jonathan Niles- Weed. Dimension-free log- Sobolo inoqualities for mixture distributions. Journal of Functional Analysis, (11(1:111,2 2021.
13

---

Published in Transactions on Machine Learning Research (08/2022)
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. Advances in Newral Information Processing Systems, 31:3036-300 3046, 2018.
R. Dobrushin. Vlasov equations. Functional Analysis and its Applications, 13(2):115-122 123, 1979.
Alain Durmus and Eric Moulines. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm.
The Annals of Applied Probability, 27(3):1551-1581 2017.
Andreas Eberle, Arnaud Guillin, and Raphael Zimmer. Quantitative Harris-type theorems for diffusions and McKean-Vlason processes. Transactions of the American Mathematical Society, 371 (10):7777377777 2019.
Donald L. Frmak. A computer simulation of charged particles in solution. T. Technique and equilibrium properties. The Journal of Chemical Physics, 62((0):4189 4196, 1975.
Lucas C.F. Ferreira and Julio C. Valencia-Guuvara. Gradient flows of time-dependent functionals in metric spaces and applications to PDEs. Monatshefte für Mathematik; (85(2))231-268) 2018.
Stuart Geman and Chii-Ruey Hwang. Diffusions for global optimization. SIAM Journal on Control ond Optimization, 24()):1031 1986.
Arthur Gretton, Karsten M Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. kernel method for the two-sample problem. Journal of Machine Learning Reseurch, 1:1-10, 2008
Richard Holley and Daniel Stroock. Logarithmic Sobolev incqualities and stochastic Ising models. Journal of Statistical Physics, (6(5-6):1155 1191119919999 1987.
Richard A. Holley, Shigeo Kusuoka, and Daniel W. Stroock. Asymptotics of the spectral gap with applications to the theory of simulated annealing. Journal of functional analysis, 83(2):333 347, 1989.
Kaitong Hu, Zhenjie Ren, David Šiška, and Lukasz Szpruch. Mean-field Langevin dynamics and energy landscape of neural networks. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 37(4):2043 2065, 2021. doi: 10.1214/20-AIHPI1 A1HHP1140. URL
Xing Huang, Panpan Ren, and Feng- Yu Wang- Distribution dependent stochastic differential equations. Frontiers of Mathematics in China, 16(2):257-30) 2021.
Lyudmyla F. Kozachenko and Nikolai N. Leonenko. Sample estimate of the entropy of a random vector.
Problemy Peredachi Informatsii, 23(2):9-16 1987.
Daniel Lacker. Mean field games and interacting particle systems. Preprint, 2018.
Daniel Lacker. Hierarchies, entropy, and quantitative propagation of chaos for mean field diffusions. arXiv preprint XrXi::2105. 02988,, 2021.
Michel Ledoux. Concentration of measure and logarithmic Sobolev inequalities. In Seminaire de probabilites XXXIII, pages 226.116.22 Springer, 1999.
Yi-An Ma, Yuansi Chen, Chi Jin, Nicolas Flammarion, and Michael Jordan. Sampling be faster than optimization. Proceedings of the National Academy of Sciences, (16(42))20881-2088) 2019.
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):E7765 E7671, 2018.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages
PMLR, 2019.
Laurent Miclo. Recuit simulé sur R étude de l'évolution de l'énergie libre. In Annales de l'HHP Probabiliéss et statistiques, volume 28, pages 235-266, 1992.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. orXiv preprint arxiv: 1712.1122000 171200088,, 2017.
14

---

Published in Transactions on Machine Learning Research (08/2022)
Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Particle dual averaging: Optimization of mean field neural networks with global convergence rate analysis. In Neural Informalion Processing Systems, 2021.
Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Couvex analysis of the mean field langevin dynamics. International Conference on Artificial Intelligence and Statistics, pages 9741-9757. PMLR, 2022.
Felix Otto and Cédric Villani. Generalization of inequality by Talagrand and links with the logarithmic Sobolev inequality. Journal of Functional Analysis, 173(2):361-40)) 2000.
Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications data science. Foundations and Trendso in Machine Learning, 11(5-6):355 607, 2019.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient Langevin dynamics: nonasymptotic analysis. In Conference on Learning Theory, pages 1674 1703. PMLR, 2017.
Gareth O. Roberts and Richard L. Tweedie. Exponential convergence of Langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996.
Grant M. Rotskoff and Eric Vanden-Eijnden. Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 7146-7155, 2018.
Filippo Santambrogio. Optimal transport for applied mathematicians. Birküuser, NY, 55(58-63):94, 2015.
Carl-Johann Simon-Gabriel, Alessandro Barp, Bernhard Schölkopf, and Lester Mackey. Metrizing weak convergence with Maximum Mean Discrepancies. arXiv preprint arXim:2006. vrXi::2006.0268,, 2020.
Harshinder Singh, Neeraj Misra, Vladimir Hnizdo, Adam Fedorowicz, and Eugene Demchuk. Nearest neighbor estimates of entropy. American journal of mathematical and management sciences, 23(3-4):301-32 2003.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: law of large numbers. SIAM Journal on Applied Mathematics, 80(2):725-755 2020.
Bharath K. Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert R.G. Lanckrict. Hilbert space embeddings and metrics on probability measures. The Journal of Machine Learning Research, 11:1517-1561, 2010.
Alain-Sol Sznitman. Topics in propagation of chaos. In Ecole d'été de probabilités de Saint-Flour XIX 1989, pages 165-251. Springer, 1991.
Wempin Tang and Xun Yu Zhou. Simulated annealing from continuum to discretization: a convergence analysis via the Eyring- Kramers law. arXiv preprint wxXiv:2102.0233) 2021.
Paul Tseng. Approximation accuracy, gradient methods, and error bound for structured convex optimization. Mathematical Programmingg 125(2):263 295, 2010.
Santosh Vempala and Andre Wibisono. Rapid convergence of the Unadjusted Langevin Algorithm: Isoperime- try suffices. Advances in Neural Information Processing Systems, 32:8094 8106, 2019.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Feng- Yu Wang. Logarithmic Sobolev inequalities: conditions and counterexamples. Journal of Operator Theory, pages 183-197, 2001.
15

---

Published in Transactions on Machine Learning Research (08/2022)
A
Additional proofs
Let us start with relation between G and its first-variation V that is more convenient for proofs.
Lemma A.1 (Integral formula). Under Assumption ① for po: Pr E P2(R)), one has
(0nn)G((o)) S.' l Viueld(p1 po)dt
where 14 = (1 t)po + tjn for t E [0,
Proof. Let h(t) G(H)). By definition of the firstvariiatio,, h is right (resp. left) contimuuu at t= 0 (resp. =). We just need to prove that h is differentiable on J0, 1[ with (t) = V[u,)d(11 no). Then, because this expression is continuous in under Assumption D the fundamental theorem of calculus would imply A(1) - (0) = So H' (()dd, which is our claim. For 1,6 E 10 one has (1 e)me 6/4 pe-te and thus
hit 1e) - -i())
G((1 e)fl + (po) G(u))
- th (t) = lim ++
lim -0
- -
Viuldd(oo 14) --)=-1
/ Vluedd(mi- - mo)
where W/_ (t) stands for the left-derivative of h at t. This shows that NL_ (6)= [Vjj=d(( 14) for t e J0, 1[. A similar computation using (1 c)şt + cpi = [r+(1-t)ee shows that the right derivative (t) has the same value, and thus h1(1)= = V - nо) for / [0, 1] which concludes the proof of the formula.
In the following lemma, we verify that G is well-behaved (in fact smooth) as function in the Wasserstein space (2(R),, using the vocabulary and results from Ambrosio and Savaré (2007).
Lemma A.2. Let p E (2))), let v E (2) and let μr = (id + tu) Then
d ((m)= =
VVim](< + to(x)) ((()dd((()
dt
JRd
Moreover, G is s-mionseme along any interpolating curve in PR(R)) and the W2 Wer-derivative of G at p is V[n].
Since the same holds true for -G, we could say that G is 2L-smooth in the Wasserstein geometry, in the sense that it is both 2L-semiconvex and 2L-semiconvex.
Proof. For > 0 and s E [0, let us (1 s)p spete- It holds by Lemma A.1
1 CC((uete--G(up)
1 6
('' [ (lus)d(uese-ua)
1
/ / (Viual<I (t+e) Viua((e + ddz))))
Ra
VViHo[< + tu(x)) ( v())d ((Le|l)))))))
Rd
[V[n(x=+ o( + ((e(]]])))()))
where we used successively the Lipschitz continuity of + [z(p] and of μ + [V[p](x) the last two lines. The first claim follows by taking the limit This also shows that Vlμ is the unique (strong) Wz-differential ial of W2 at μ, in the sense of (Ambrosio and Savaré 2007 Def. 4.1).
16

---

Published in Transactions on Machine Learning Research (08/2022)
For the semi-convexitg claim, let h(t) = G(ue). For s, e [0,1]. 1], it holds by Sauchy-Schwarz
[W(t) h'ss) < (10ll22(m) f ( vV[ual( + so(x)) (1 1.2 [ (W2(1ss)4) + |t =]]](())]|) dy((x)
| I.2 (22 + 2/t s 11
Since W2(Hs, S - =|||o|l> it follows
(1)(1) [s)) s 2 =|||=||2>
which proves that G is (-2L) in the sense of (Ambrosoo and Savaré 2007
Remark 3.2).
17


Reviews:
[{"review_id": "cwaW4oSgjz", "reviewer": "Reviewer_piEG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThe paper is clearly writing and well-organised.  The idea of \"entropy sandwich\" is intuitively interesting and theoretic promising, although it is a direct application of convexity of functionals. The application of obtaining the convergence rate of two-layer neural networks training in the mean-field regime is also an important result. \n\nWeakness:\nI have some minor concerns on the discussion of the related works. The exponential convergence of non-linear Langevin dynamics seems already obtained in previous works. For example, in [Yang, Zhuoran, et al. 2020], the authors proved a similar exponential convergence result of mean-field particle optimization in Theorem 4.8 under a similar \"uniform\" Polyak-Lojasiewicz condition in Assumption 4.6 and Equation 4.14.  I think the authors should provide some discussions on the similarity and difference from previous works. In particular, how Theorem 3 and Assumption 3 differs from [Yang, Zhuoran, et al. 2020]. \n\n[not critical] In proposition 5.1, when \\ell is the square loss, there should be an additional assumption that |E[y|z]| \\leq K'. I'm a little bit confused with this assumption: does it mean we should put some restrictions on the data distribution D? If it is, this assumption seems to be somewhat restrictive. \n\n\n[not critical] There seems no experimental validations. It is good even the author could run some toy examples to validate the theory. \n\nReference:\n\n[1]. Yang, Zhuoran, et al. \"Variational Transport: A Convergent Particle-Based Algorithm for Distributional Optimization.\" arXiv preprint arXiv:2012.11554 (2020).\n\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the convergence rate of mean-field Langevin dynamics (MFLD). The main contributions lie in three folds: (i). the authors prove that under a certain family of LSI holds, the MFLD converges at an exponential rate; (ii). the authors study the convergence of annealed dynamics and prove when the noise decay at an logarithmic rate, the dynamics also converges for the unregularized objective; (iii). for the application of (i), the author study the mean-field dynamics of two-layer neural networks and obtain the exponential convergence rate to the global optima. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. discuss more related works including what mentioned in [Strengths And Weaknesses]. \n\n2. [not critical] may run some toy experiments to make the theory more convincing. \n\n3. [not critical] discuss some limitation of assumptions, for example, in proposition 5.1 of  |E[y|z]| \\leq K'. ", "broader_impact_concerns": "N.A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nUNj4LNr3K", "reviewer": "Reviewer_A4WX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Contributions: \n\n- Recently, convergence analysis of the mean-field Langevin dynamics has become a very important research topic because of the preferable property of neural networks in the mean-field regime. In fact, many studies analyzed the convergence of the dynamics. \nHowever, previous related works only show the convergence to the unique minimizer without an explicit convergence rate or require strong regularization to guarantee the quantitative convergence. \nIn contrast, the paper succeeds in providing an explicit convergence rate under any strength of regularization with a much more simple analysis.\n\n- Moreover, the proof is quite neat and will be useful for the community because it is a natural extension of the analysis of normal Langevin dynamics which is recovered as a special case when the objective is linear functional plus entropy. This proof technique will be further investigated in the future.\n\n- I would acknowledge the analysis of annealing dynamics is a unique and important contribution, although the result on non-annealing dynamics was also obtained by the concurrent work [Nitanda et al. 2022].\n\n\nWhile these contributions, I think the proof of Theorem 4.1 probably needs to be fixed a bit as commented below.\nIf my understanding is wrong, I would appreciate it if you could correct me.\n\n\n- Doesn't the constant $C_2$ (in the first inequality on page 8) depend on $t$?\n    From Lemma 4.2, $-\\tau_t H(\\mu_t)$ is upper bounded by $\\tau_t C_1 F_{\\tau_t}(\\mu_t) + \\tau_tC_2$. Indeed, the second term can be free from $t$ because of monotonicity of $\\tau_t$ and positivity of $C_2$, but that is not the case for the first term because $F_{\\tau}(\\mu)$ can be negative. Please elaborate on how $\\tau_t C_1$ of $\\tau_t C_1 F_{\\tau_t}(\\mu_t)$ can be independent of $t$ in the inequality.\n\n- Minor comment: I am not sure how the term $C' t^{-1-\\epsilon}$ (which is the last term in the (displayed) fourth inequality on page 8) is derived. I guess this constant relates to $t^{-1}/\\log t$ in the previous inequality, but the inequality is reversed. I think it can be corrected: the term $t^{-1}/\\log t$ could remain itself, which does not affect the argument of Step 1 because $t^{-1}/\\log t$ is dominated by $-t^{-1}$ in Eq.(20).\n\n- Suggestion: It would be helpful for the readers to elaborate a bit more on the derivation of the first inequality on $| G(\\tilde{\\mu_0}) - G(\\tilde{\\mu_\\sigma})|$ (appearing on the first displayed inequality on page 9), though I understand ``Gaussian kernel is centered\" is used to show $\\int \\nabla V(\\tilde{\\mu}_\\sigma)(x)^\\top (y-x)d\\gamma(x,y)=0$ through $\\int \\nabla V(\\tilde{\\mu}_\\sigma)(x)^\\top z g_\\sigma(z)dz=0$.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a convergence of mean-field Langevin dynamics which is a time-and-many particle limit of noisy gradient descent for mean-field models.  In particular, it is shown that this dynamics minimizes the convex functional plus negative entropy on the space of measures and converges to the optimal solution with an exponential rate.\nThis result includes an important application: the global convergence of the optimization of two-layer neural networks in the mean-field regime.\nMoreover, the paper also studies annealing dynamics in which the noise decays at a logarithmic rate, which implies the global convergence to the solution for unregularized problems.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "A few concerns (especially the first one) about the proof commented above should be addressed and corrected if needed.\n\nBelow are some minor comments:\n\n- About the comment just before Sec 1.1.: ``As for the behavior of the Mean-Field Langevin dynamics (5) itself, it is shown ... but these works leave open the question of quantitative\". \nIt is better to note that the exponential convergence in $W_1$-distance was shown in related studies. For instance, see Remark 2.12 in [Hu et al. (2019)].  However, the contribution of the paper is not negated by the previous work, because they required the strong regularization.\n\n- Typo: $h(\\tau)=F_{\\tau_t}(\\mu_\\tau^*)$ on line 3 (page 8) is correctly $h(\\tau)=F_{\\tau}(\\mu_\\tau^*)$.\n\n- Typo: $C_2$ (which is the last term in the (displayed) second inequality on page 8) is correctly $C_3$.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9hGQFo6wur", "reviewer": "Reviewer_QWcw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strength:**\n\n- global convergence of two-layer neural network in the mean-field regime is an important research problem, and most existing works do not prove a quantitative convergence rate, even in the presence of regularization. This submission fills this gap by proving linear convergence for the regularized objective. \n\n- The analysis is based on a clever observation that the optimality gap can be \"sandwiched\" between two relative entropy terms, one of which relates to the Gibbs measure defined by the objective \"linearized\" at the current point. This observation, together with the uniform LSI condition, gives a simple proof of the convergence rate. \n\n- I expect that the studied mean-field Langevin dynamics can find applications beyond two-layer neural networks, since it covers settings where sampling via the vanilla Langevin dynamics is not possible. \n\n### **Weakness:**\n\n- The convergence rate is only shown for the continuous-time and infinite-particle setting, but the algorithm employed in practice requires space- and time-discretization. While the concurrent [Nitanda et al. 2022] provided a discrete-time analysis, the finite-particle guarantee is still not available. \nThis is especially challenging for the annealed dynamics, where the very slow convergence rate likely results in the discretization error blowing up through time. \n\n- In the context of two-layer neural network, the LSI constant has exponential dependence on the regularization hyperparameter. This limits the applicability of the theory in providing meaningful convergence rate under weak regularization (which is important if we want to cover the near-interpolation setting or exact recovery in student-teacher settings). \n\n- Related to the previous point, the uniform LSI condition is shown by invoking the Holley-Stroock criterion. While this derivation may be optimal in some settings, it also feels a bit underwhelming: the neural network function itself is treated as a \"perturbation\", and in some sense training converges only because of the regularization. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission studies the convergence rate of a generalization of the the Langevin dynamics termed the *mean-field Langevin dynamics*, which can be viewed as an optimization algorithm in the space of measures that minimizes an entropy-regularized convex functional. This dynamics naturally arises from the optimization of two-layer neural network (in the mean-field regime) using the noisy gradient descent algorithm. The main contribution of this submission is a simple proof that the continuous-time dynamics converges exponentially to the optimum, under a uniform log-Sobolev inequality (LSI) on the trajectory. In addition, an annealed dynamics with decreasing entropy regularization is also studied and a slower convergence rate is obtained. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Overall, I feel that this is an interesting submission that is relevant to the TMLR community. I hope the authors can comment on the weaknesses mentioned above, and be a bit more explicit about the limitations of the current approach.", "broader_impact_concerns": "This submission does not require a Broader Impact Statement. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers and the AE think that this a good paper with solid contributions. The author also have addressed a few minor concerns which improved the quality of the paper even further. 

The author should address any remaining minor issues (e.g. the promised discussion on weakened assmp w/ stronger regularization) before camera ready.

AE
Decision: Accept (poster)