Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit

Introduction

Multi-layer neural networks, and in particular multi-layer perceptrons, present a number of remarkable features. They are effectively trained using stochastic-gradient descent (SGD) [LBBH98]; their behavior is fairly insensitive to the number of hidden units or to the input dimensions [SHK+14]; their number of parameters is often larger than the number of samples.

In this paper consider simple neural networks with one layer of $N$ hidden units:

Classical theory of universal approximation provides useful insights into the way two-layers networks capture arbitrary input-output relations [Cyb89, Bar93]. In particular, Barron’s theorem [Bar93] guarantees

The universal approximation property is then related to the fact that an arbitrary distribution $\rho$ can be approximated by one supported on $N$ pointsOf course, here we are hiding some important technical issues..

Approximation theory provides some insight into the peculiar properties of neural networks. Small population risk is achieved by many networks, since what matters is the distribution $\rho$, not the parameters ${\bm{\theta}}_{1},\dots,{\bm{\theta}}_{N}$. The behavior is insensitive to the number of neurons $N$, as long as this is large enough for $\hat{\rho}^{(N)}$ to approximate $\rho$. Finally, the bound (4) is dimension-free.

(Here $\xi(t)$ is a function that gauges the evolution of step size and will be defined below. In fact, there is little loss to the following discussion in setting $\xi(t)=1$.) We will refer to this as the mean field description, or distributional dynamics. This description has the advantage of being explicitly independent of the number of hidden units $N$ and hence accounts for one of the empirical findings described above (the insensitivity to the number of neurons). Further, it allows to focus on some key elements of the dynamics (global convergence, typical behavior) neglecting others (local minima, statistical noise).

Several papers used this approach over the last year to analyze learning in two-layers networks: this work will be succinctly reviewed in Section 2.

The results of [MMN18] present several limitations, that we overcome in the present paper. We briefly summarize our contributions.

As mentioned above, both classical approximation theory and the mean-field analysis of SGD approximate a certain target distribution $\rho$ by the empirical distributions of the network parameters $\hat{\rho}^{(N)}$. However, while the approximation bound (4) is dimension-free, the approximation guarantees of [MMN18] are explicitly dimension-dependent. Even for very smooth functions $f({\bm{x}})$, and well behaved data distributions, the results of [MMN18] require $N\gg D$.

Here we prove a new bound that is dimension independent and therefore more natural. The proof follows a coupling argument which is different and more powerful than the one of [MMN18]. A key improvement consists in isolating different error terms, and developing a more delicate concentration-of-measure argument which controls the dependence of the error on $N$.

Let us emphasize that capturing the correct dimension-dependence is an important test of the mean-field theory, and it is crucial in order to compare neural networks to other learning techniques (see Section 4).

The approximation guarantee of [MMN18] only applies to activation functions $\sigma_{\star}({\bm{x}};{\bm{\theta}}_{i})$ that are bounded. This excludes the important case of unbounded second-layer coefficients as in Eq. (1). We extend our analysis to that case. This requires to develop an a priori bound on the growth of the coefficients $a_{i}$. As in the previous point, our approximation guarantee is dimension-free.

Finally, in some cases it is useful to inject noise into SGD. From a practical perspective this can help avoiding local minima. From an analytical perspective, it corresponds to a modified PDE, which contains an additional Laplacian term $\Delta_{{\bm{\theta}}}\rho_{t}$. This PDE has smoother solutions $\rho_{t}$ that are supported everywhere and converge globally to a unique fixed point [MMN18].

In this setting, we prove a dimension-free approximation guarantee for the case of bounded activations. We also obtain a guarantee for noisy SGD unbounded activations, but the latter is not dimension-free.

We analyze the PDE (DD) in a specific short-time limit and show that it is well approximated by a linearized dynamics. This dynamics can be thought as fitting a kernel ridge regression‘Kernel ridge regression’ and ‘kernel regression’ are used with somewhat different meanings in the literature. Kernel ridge regression uses global information and can be defined as ridge regression in reproducing kernel Hilbert space (RKHS), while kernel regression uses local averages. See Remark H.1 for a definition. model with respect to a kernel corresponding to the initial weight distribution $\rho_{0}$. We thus recover –from a different viewpoint– a connection with kernel methods that has been investigated in several recent papers [JGH18, DZPS18, DLL+18, AZLS18]. Beyond the short time scale, the dynamics is analogous to kernel boosting dynamics with a time-varying data-dependent kernel (a point that already appears in [RVE18]).

Mean-field theory allowed to prove global convergence guarantees for SGD in two-layers neural networks [MMN18, CB18b]. Unfortunately, these results do not provide (in general) useful bounds on the network size $N$. We believe that the results in this paper are a required step in that direction.

The rest of this paper is organized as follows. The next section overviews related work, focusing in particular on the distributional dynamics (DD), its variants and applications. In Section 3 we present formal statements of our results. Section 4 develops the connection with kernel methods. Proofs are mostly deferred to the appendices.

Related work

As mentioned above, classical approximation theory already uses (either implicitly or explicitly) the idea of lifting the class of $N$-neurons neural networks, cf. Eq. (1), to the infinite-dimensional space (5) parametrized by probability distributions $\rho$, see e.g. [Cyb89, Bar93, Bar98, AB09]. This idea was exploited algorithmically, e.g. in [BRV+06, NS17].

Only very recently (stochastic) gradient descent was proved to converge (for large enough number of neurons) to the infinite-dimensional evolution (DD) [MMN18, RVE18, SS18, CB18b]. In particular, [MMN18] proves quantitative bounds to approximate SGD by the mean-field dynamics. Our work is mainly motivated by the objective to obtain a better scaling with dimension and to allow for unbounded second-layer coefficients.

The mean-field description was exploited in several papers to establish global convergence results. In [MMN18] global convergence was proved in special examples, and in a general setting for noisy SGD. The papers [RVE18, CB18b] studied global convergence by exploiting the homogeneity properties of Eq. (1). In particular, [CB18b] proves a general global convergence result. For initial conditions $\rho_{0}$ with full support, the PDE (DD) converges to a global minimum provided activations are homogeneous in the parameters. Notice that the presence of unbounded second layer coefficients is crucial in order to achieve homogeneity. Unfortunately, the results of [CB18b] do not provide quantitative approximation bounds relating the PDE (DD) to finite-$N$ SGD. The present paper fills this gap by establishing approximation bounds that apply to the setting of [CB18b].

A different optimization algorithm was studied in [WLLM18] using the mean-field description. The algorithm resamples a positive fraction of the neurons uniformly at random at a constant rate. This allows the authors to establish a global convergence result (under certain assumed smoothness properties on the PDE solution). Again, this paper does not provide quantitative bounds on the difference between PDE and finite-$N$ SGD. While our theorems do not cover the algorithm of [WLLM18], we believe that their algorithm could be analyzed using the approach developed here. Exponentially fast convergence to a global optimum was proven in [JMM19] for certain radial-basis-function networks, using again the mean-field approach. While the setting of [JMM19] is somewhat different (weights are constrained to a convex compact domain), the technique presented here could be applicable to that problem as well.

Finally, a recent stream of works [JGH18, GJS+19, DZPS18, DLL+18, AZLS18] argues that, as $N\to\infty$ two-layers networks are actually performing a type of kernel ridge regression. As shown in [CB18a], this phenomenon is not limited to neural network, but generic for a broad class of models. As expected, the kernel regime can indeed be recovered as a special limit of the mean-field dynamics (DD), cf. Section 4. Let us emphasize that here we focus on the population rather than the empirical risk.

A discussion of the difference between the kernel and mean-field regimes was recently presented in [DL19]. However, [DL19] argues that the difference between kernel and mean-field behaviors is due to different initializations of the coefficients $a_{i}$’s. We show instead that, for a suitable scaling of the initialization, kernel and mean field regimes appear at different time scales. Namely, the kernel behavior arises at the beginning of the dynamics, and mean field characterizes longer time scales. It is also worth mentioning that the connection between mean field dynamics and kernel boosting with a time-varying data-dependent kernel was already present (somewhat implicitly) in [RVE18].

Dimension-free mean field approximation

We will work under a one-pass model, that is, each data point is visited once.

We also consider a noisy version of SGD, with a regularization term:

The infinite-dimensional evolution corresponding to noisy SGD is given by

In order to establish a non-asymptotic guarantee, we will make the following assumptions:

$t\mapsto\xi(t)$ is bounded Lipschitz: $\mathinner{\!\left\lVert\xi\right\rVert}_{\infty}$, $\mathinner{\!\left\lVert\xi\right\rVert}_{\text{Lip}}\leq K_{1}$.

The functions ${\bm{w}}\mapsto v({\bm{w}})$ and $({\bm{w}}_{1},{\bm{w}}_{2})\mapsto u({\bm{w}}_{1},{\bm{w}}_{2})$ are differentiable, with bounded and Lipschitz continuous gradient: $\|\nabla v({\bm{w}})\|_{2}\leq K_{3}$, $\|\nabla u({\bm{w}}_{1},{\bm{w}}_{2})\|_{2}\leq K_{3}$, $\|\nabla v({\bm{w}})-\nabla v({\bm{w}}^{\prime})\|_{2}\leq K_{3}\|{\bm{w}}-{\bm{w}}^{\prime}\|_{2}$, $\|\nabla u({\bm{w}}_{1},{\bm{w}}_{2})-\nabla u({\bm{w}}^{\prime}_{1},{\bm{w}}^{\prime}_{2})\|_{2}\leq K_{3}\|({\bm{w}}_{1},{\bm{w}}_{2})-({\bm{w}}^{\prime}_{1},{\bm{w}}^{\prime}_{2})\|_{2}$.

We will consider two different cases for the SGD dynamics:

We initialize the parameters ${\bm{\theta}}^{0}_{i}=(a^{0}_{i},{\bm{w}}^{0}_{i})$ as $({\bm{\theta}}^{0}_{i})_{i\leq N}\sim_{iid}\rho_{0}$. Both the $a_{i}^{0}$ and ${\bm{w}}^{0}_{i}$ are updated during the dynamics.

We use the same initialization as described above, but the coefficients $a_{i}$ are not updated by SGD. The corresponding PDE is given by Eq. (DD) (or (diffusion-DD)), except that the space derivatives are to be interpreted only with respect to ${\bm{w}}$, i.e. replace $\nabla_{\bm{\theta}}$ by $(0,\nabla_{\bm{w}})$, and $\Delta_{\bm{\theta}}$ by $\Delta_{\bm{w}}$.

While the second setting is less relevant in practice, it is at least as interesting from a theoretical point of view, and some of our guarantees are stronger in that case.

Consider noiseless SGD with fixed coefficients. Then there exists a constant $K$ (depending uniquely on the constants $K_{i}$ of assumptions A1-A4) such that

with probability at least $1-e^{-z^{2}}$.

Consider noiseless SGD with general coefficients. Then there exists constants $K$ and $K_{0}$ (depending uniquely on the constants $K_{i}$ of assumptions A1-A4) such that if $\varepsilon\leq 1/[K_{0}(D+\log N+z^{2})e^{K_{0}T^{3}}]$, we have

with probability at least $1-e^{-z^{2}}$.

As anticipated in the introduction, provided $T,K=O(1)$, the error terms in Eqs. (9), (10), are small as soon as $N\gg 1$. In other words, the minimum number of neurons needed for the mean-field approximation to be accurate is independent of the dimension $D$, and only depends on intrinsic features of the activation and data distribution.

On the other hand, the dimension $D$ appears explicitly in conjunction with the step size $\varepsilon$. We need $\varepsilon\ll 1/D$ in order for mean field to be accurate. This is the same trade-off between step size and dimension that was already achieved in [MMN18].

We next consider noisy SGD, cf. Eq. (noisy-SGD), and the corresponding PDE in Eq. (diffusion-DD). We need to make additional assumptions on the initialization in this case.

The initial condition $\rho_{0}$ is such that, for ${\bm{\theta}}^{0}_{i}=(a^{0}_{i},{\bm{w}}^{0}_{i})\sim\rho_{0}$, we have that ${\bm{w}}^{0}_{i}$ is $K_{5}^{2}/D$-sub-Gaussian.

The last condition ensures the existence of strong solutions for Eq. (diffusion-DD). The existence and uniqueness of solution of the PDE (DD) and the PDE (diffusion-DD) are discussed in Appendix F.

Consider noisy SGD with fixed coefficients. Then there exists a constant $K$ (depending uniquely on the constants $K_{i}$ of assumptions A1-A5 and $K_{6}$) such that

with probability at least $1-e^{-z^{2}}$.

Consider noisy SGD with general coefficients. Then there exists a constant $K$ (depending uniquely on the constants $K_{i}$ of assumptions A1-A5 and $K_{6}$) such that

with probability at least $1-e^{-z^{2}}$.

Unlike the other results in this paper, part $(B)$ of Theorem 2 does not establish a dimension-free bound. Further, while previous bounds allow to control the approximation error for any $T=o(\log N)$, Theorem 2.$(B)$ requires $T=o(\log\log N)$ . The main difficulty in part $(B)$ is to control the growth of the coefficients $a_{i}$. This is more challenging than in the noiseless case, since we cannot give a deterministic bound on $|a_{i}|$.

Despite these drawbacks, Theorem 2 $(B)$ is the first quantitative bound approximating noisy SGD by the distributional dynamics, for the case of unbounded coefficients. It implies that the mean field theory is accurate when $N\gg D$.

2 Example: Centered anisotropic Gaussians

To illustrate an application of the theorems, we consider the problem of classifying two Gaussians with the same mean and different covariance. This example was studied in [MMN18], but we restate it here for the reader’s convenience.

Consider the joint distribution of data $(y,{\bm{x}})$ given by the following:

With probability $1/2$: $y=+1$, ${\bm{x}}\sim{\mathsf{N}}(0,{\bm{\Sigma}}_{+})$,

With probability $1/2$: $y=-1$, ${\bm{x}}\sim{\mathsf{N}}(0,{\bm{\Sigma}}_{-})$,

where ${\bm{\Sigma}}_{\pm}={\bm{U}}^{\mathsf{T}}\text{diag}((1\pm\Delta)^{2}{\bm{I}}_{s_{0}},{\bm{I}}_{d-s_{0}}){\bm{U}}$ for ${\bm{U}}$ to be an unknown orthogonal matrix. In other words, there exists a subspace ${\mathcal{V}}$ of dimension $s_{0}$, such that the projection of ${\bm{x}}$ on the subspace ${\mathcal{V}}$ is distributed according to an isotropic Gaussian with variance $\tau_{+}^{2}=(1+\Delta)^{2}$ (if $y=+1$) or $\tau_{-}^{2}=(1-\Delta^{2})$ (if $y=-1$). The projection orthogonal to ${\mathcal{V}}$ has instead the same variance in the two classes.

We choose an activation function without offset or output weights, namely $\sigma_{*}({\bm{x}};{\bm{\theta}}_{i})=\sigma(\langle{\bm{w}}_{i},{\bm{x}}\rangle)$. While qualitatively similar results are obtained for other choices of $\sigma$, we will use a simple piecewise linear function (truncated ReLU) as a running example: take $t_{1}<t_{2}$,

We say that ${\bar{\rho}}\in\mathscrsfs{P}_{{\rm good}}$ if: $(i)$ ${\bar{\rho}}$ is absolutely continuous with respect to Lebesgue measure, with bounded density; $(ii)$ ${\overline{R}}_{\infty}({\bar{\rho}})<1$.

The following theorem is an improvement of [MMN18, Theorem 2] using Theorem 1, whose proof is just by replacing the last step of proof of [MMN18, Theorem 2] using the new bounds developed in 1 (A).

Comparing to [MMN18, Theorem 2], here we require $N=O(1)$ neuron rather than previously $N=O(d)$ neurons. The number of data used $k=O(d)$ is still on the optimal order.

Connection with kernel methods

As discussed above, mean-field theory captures the SGD dynamics of two layers neural networks when the number of hidden units $N$ is large. Several recent papers studied a different description, that approximates the neural network as performing a form of kernel ridge regression [JGH18, DZPS18]. This behavior also arises for large $N$: we will refer to this as to the ‘kernel regime’, or ‘kernel limit’. As shown in [CB18a] the existence of a kernel regime is not specific to neural networks but it is a generic feature of overparameterized models, under certain differentiability assumptions.

In the case of general coefficients $a_{i}$, this amounts to rescaling the coefficients $a_{i}\to a_{i}/\alpha$. Equivalently, this corresponds to a different initialization for the $a_{i}$’s (larger by a factor $\alpha$).

We first note that the theorems of the previous section obviously hold for the modified dynamics, with the PDE (DD) generalized to

where $\hat{f}_{\alpha}({\bm{x}};\rho)=\alpha\int\sigma_{\star}({\bm{x}};{\bm{\theta}})\,\rho({\rm d}{\bm{\theta}})$. It is convenient to redefine time units by letting $\rho^{\alpha}_{t}\equiv\rho_{\alpha^{-2}t}$. This satisfies the rescaled distributional dynamics

Coupling the dynamics (Rescaled-DD) and (RD) suggests the following point of description. Gradient flow dynamics of two-layers neural network is a kernel boosting dynamics with a time-varying kernel. The scaling parameter $\alpha$ controls the speed that the kernel evolves.

The mean field residual dynamics (RD) implies that

so that the risk will be non-increasing along the gradient flow dynamics. However, since the kernel ${\mathcal{H}}_{\rho_{t}^{\alpha}}$ is not fixed, it is hard to analyze when the risk converges to (see [MMN18, Theorem 4], [CB18b, Theorem 3.3 and 3.5] for general convergence results).

2 Kernel limit of residual dynamics

The kernel regime corresponds to large $\alpha$ and allows for a simpler treatment of the dynamics. Heuristically, the reason for such a simplification is that the time derivative of $\rho_{t}^{\alpha}$ is of order $1/\alpha$, cf. (Rescaled-DD). We are therefore tempted to replace ${\mathcal{H}}_{\rho^{\alpha}_{t}}$ in Eq. (RD) by ${\mathcal{H}}_{\rho_{0}}$. Formally, we define the following linearized residual dynamics

We can also define the corresponding predictors by $f^{*}_{t}=f-u_{t}^{*}$. The operator ${\mathcal{H}}_{\rho_{0}}$ is bounded and standard semigroup theory [Eva09] implies the following.

We have $\lim_{t\to\infty}u^{*}_{t}=u^{*}_{\infty}={\bm{P}}_{\rho_{0}}u^{*}_{0}$, where ${\bm{P}}_{\rho_{0}}$ is the orthogonal projector onto the null space of ${\mathcal{H}}_{\rho_{0}}$. In particular, if the null space of ${\mathcal{H}}_{\rho_{0}}$ is empty, then $\lim_{t\to\infty}\|u^{*}_{t}\|_{{L^{2}}}\to 0$. Correspondingly $f^{*}_{\infty}={\bm{P}}^{\perp}_{\rho_{0}}f+{\bm{P}}_{\rho_{0}}f_{0}^{*}$ (where ${\bm{P}}^{\perp}_{\rho_{0}}={\bm{I}}-{\bm{P}}_{\rho_{0}}$).

Let $u^{\alpha}_{t}$ and $u^{*}_{t}$ be the residues in the mean-field dynamics (RD) and linearized dynamics (17), respectively. Let assumptions A1, A3, A4 hold, and additionally assume the following

$|y_{i}|$, $\|\sigma\|_{\infty}\leq K_{2}$, and ${\bm{\theta}}\mapsto\sigma_{\star}({\bm{x}};{\bm{\theta}})$ is differentiable.

$\|\nabla^{3}u({\bm{w}},{\bm{w}}^{\prime})\|_{{\rm op}},\|\nabla^{4}u({\bm{w}},{\bm{w}}^{\prime})\|_{{\rm op}}\leq\kappa$.

Then there exists a constant $K$ depending on $\{K_{i}\}_{i=1}^{4}$, such that

For SGD with general coefficients, we have

Unlike in similar results in the literature, we focus here on the population risk rather than the empirical risk. The recent paper [CB18a] addresses both the overparametrized and the underparametrized regime. The latter result (namely [CB18a, Theorem 3.4]) is of course relevant for the population risk. However, while [CB18a] proves convergence to a local minimum, here we show that the population risk becomes close to .

For the sake of completeness, we review the connection in Appendix H.7.

References

Appendix A Notations

For future reference, we copy the key definitions from the main text:

In the case of fixed coefficients, without loss of generality, we will fix in the proof $a_{i}=1$ for notational simplicity and freely denote $({\bm{\theta}}_{i})_{i=1}^{N}=({\bm{w}}_{i})_{i=1}^{N}$,

$W_{2}(\cdot,\cdot)$ is the Wasserstein distance between probability measures

K will denote a generic constant depending on $K_{i}$ for $i=1,2,3,4,5,6$, where the $K_{i}$’s are constants that will be specified from the context.

In the proof and the statements of the theorems, we will only consider the leading order in $T$. In particular, we freely use that $KT^{k}\log^{l}Te^{KT}\leq K^{\prime}e^{K^{\prime}T}$ for a constant $K^{\prime}\geq K$.

For readers convenience, we copy here the two simplified versions of Gronwall’s lemma that will be used extensively in the proof.

Consider an interval $I=[0,t]$ and $\phi$ a real-valued function defined on $I$, assume there exists positive constants $\alpha,\beta$ such that $\phi$ satisfies the integral inequality

then $\phi(t)\leq\alpha e^{\beta t}$ for all $t\in I$.

Consider a non-negative sequence $\{\phi_{k}\}_{k=0}^{n}$ and assume there exists positive constants $\alpha,\beta$ such that $\{\phi_{k}\}_{k=0}^{n}$ satisfies the summation inequality

then $\phi_{k}\leq\alpha+\alpha\beta ke^{\beta k}$ for all $k\in\{0,1,\ldots,n\}$.

Appendix B Proof of Theorem 1 part (A)

Throughout this section, the assumptions of Theorem 1 (A) are understood to hold. These are assumptions A1-A4 in Section 3. In writing the proofs, for notational simplicity, we consider the following special setting:

The step size function $\xi(t)\equiv 1/2$.

The proof can be easily generalized to the case of general bounded coefficient $|a_{i}|\leq K$, and non-constant function $\xi(t)$.

In the proof of this theorem, we have $({\bm{\theta}}_{i})_{i=1}^{N}=({\bm{w}}_{i})_{i=1}^{N}$, and

We will consider four dynamics (note we choose $\xi(t)=1/2$ in these equations):

The nonlinear dynamics (ND): we introduce $(\bar{\bm{\theta}}^{t}_{i})_{i\in[N],t\geq 0}$ with initialization $\bar{\bm{\theta}}^{0}_{i}\sim\rho_{0}$ i.i.d.:

Equivalently, we have the integral equation

where we denoted ${\bm{G}}({\bm{\theta}};\rho)=-\nabla\Psi({\bm{\theta}};\rho)=-\nabla V({\bm{\theta}})-\int\nabla_{1}U({\bm{\theta}},{\bm{\theta}}^{\prime})\rho({\rm d}{\bm{\theta}}^{\prime})$. Note that $\bar{\bm{\theta}}^{t}_{i}$ is random because of its random initialization, and its law is $\rho_{t}$.

The particle dynamics (PD): we introduce $(\underline{\bm{\theta}}^{t}_{i})_{i\in[N],t\geq 0}$ with initialization $\underline{\bm{\theta}}_{i}^{0}=\bar{\bm{\theta}}_{i}^{0}$:

We introduce the particle distribution ${\underline{\rho}}^{(N)}_{t}=(1/N)\sum_{i=1}^{N}\delta_{\underline{\bm{\theta}}_{i}^{t}}$. In integration form, we get:

The GD dynamic corresponds to the discretized particle dynamic (25).

where ${\bm{F}}_{i}({\bm{\theta}}^{k};{\bm{z}}_{k+1})=(y_{k+1}-\hat{y}_{k+1})\nabla_{{\bm{\theta}}}\sigma_{\star}({\bm{x}}_{k+1};{\bm{\theta}}^{k}_{i})$, with ${\bm{z}}_{k}\equiv({\bm{x}}_{k},y_{k})$ and $\hat{y}_{k+1}=(1/N)\sum_{j=1}^{N}\sigma_{\star}({\bm{x}}_{k+1};{\bm{\theta}}^{k}_{j})$. In summation form, we have

By Proposition 1, 2, 3, 4 proved below, we have with probability at least $1-e^{-z^{2}}$,

Combining these inequalities gives the conclusion of Theorem 1 (A). In the following subsections, we prove all the above interpolation bounds, under the setting of Theorem 1 (A).

Assumptions A1 - A3 immediately implies that

There exists a constant $K$ depending on $K_{1},K_{2},K_{3}$, such that

For any ${\bm{\theta}}=({\bm{\theta}}_{i})_{i=1}^{N}$ and ${\bm{\theta}}^{\prime}=({\bm{\theta}}_{i}^{\prime})_{i=1}^{N}$, we have

The boundedness of $V$ and $U$ are implied by the boundedness of $\|\sigma\|_{\infty}$ and $|y|$ in Assumption A1. The boundedness of $\|\nabla V\|_{2},\|\nabla U\|_{2},\|\nabla^{2}V\|_{{\rm op}},\|\nabla^{2}U\|_{{\rm op}}$ are implied by Assumption A3.

and by the Lipschitz property of $V$ and $U$. ∎

Using Eq. (24) and (25), we immediately have

There exists a constant $K$ such that for any time $s,t$

The first two inequalities are simply implied by the boundedness of $\nabla V$ and $\nabla_{1}U$, and Eq. (24) and (25). The third inequality is simply implied by

B.2 Bound between PDE and nonlinear dynamics

There exists a constant $K$ depending only on the $K_{i}$, $i=1,2,3$, such that with probability at least $1-e^{-z^{2}}$, we have

We decompose the difference into the following two terms

where the expectation is taken with respect to $\bar{\bm{\theta}}_{i}^{0}\sim\rho_{0}$. The result holds simply by combining Lemma 4 and Lemma 5. ∎

Let ${\bm{\theta}}=({\bm{\theta}}_{1},\ldots,{\bm{\theta}}_{i},\ldots,{\bm{\theta}}_{N})$ and ${\bm{\theta}}^{\prime}=({\bm{\theta}}_{1},\ldots,{\bm{\theta}}_{i}^{\prime},\ldots{\bm{\theta}}_{N})$ be two configurations that differ only in the $i$’th variable. Then

Hence taking the union bound over $s\in\eta\{0,1,\ldots,\lfloor T/\eta\rfloor\}$ and bounding the difference between time in the interval and grid, we have

Now taking $\eta=1/\sqrt{N}$ and $\delta=K[\sqrt{\log(NT)}+z]/\sqrt{N}$, we get the desired result. ∎

B.3 Bound between nonlinear dynamics and particle dynamics

There exists a constant $K$, such that with probability at least $1-e^{-z^{2}}$, we have

We would like to prove a uniform bound for $I_{i}^{t}$ for $i\in[N]$ and $t\in[0,T]$.

By Lemma 3, there exists $K$ such that, for any $0\leq t,s\leq T$ and $i\in[N]$, we have

Taking the union bound over $i\in[N]$ and $s\in\eta\{0,1,\ldots,\lfloor T/\eta\rfloor\}$ and bounding time in the interval and the grid, we have

Taking $\eta=\sqrt{1/N}$, and $\delta=K[\sqrt{\log(NT)}+z]/\sqrt{N}$, we get the desired result. ∎

Let $\delta(N,T,z)=K[\sqrt{\log(NT)}+z]/\sqrt{N}$, and define

We condition on the good event in Lemma 6 to happen. By Eq. (32), we have

By Eq. (28), this proves Eq. (30) and (31) hold with probability at least $1-e^{-z^{2}}$. ∎

B.4 Bound between particle dynamics and GD

B.5 Bound between GD and SGD

There exists a constant $K$, such that with probability at least $1-e^{-z^{2}}$, we have

where $\rho^{(N)}_{k}\equiv(1/N)\sum_{i\in[N]}\delta_{{\bm{\theta}}^{k}_{i}}$ is the empirical distribution of the SGD iterates. Hence we get:

Note ${\bm{F}}_{i}({\bm{\theta}}^{l};{\bm{z}}_{l+1})=(y_{l+1}-\hat{y}_{l+1})\nabla_{{\bm{w}}}\sigma({\bm{x}}_{l+1};{\bm{w}}_{i}^{l})$ for ${\bm{z}}_{l+1}=(y_{l+1},{\bm{x}}_{l+1})$. Since we assumed in A2 that $\nabla_{\bm{w}}\sigma({\bm{x}};{\bm{w}})$ is $K$-sub-Gaussian, and since $y_{l+1}$ and $\hat{y}_{l+1}$ are $K$ bounded, we have that ${\bm{Z}}_{i}^{l}$ is $K$-sub-Gaussian (the product of a bounded random variable and a sub-Gaussian random variable is sub-Gaussian). We can therefore apply Azuma-Hoeffding inequality (Lemma 31) and get:

Taking the union bound over $i\in[N]$, we get:

Assuming the bad events in Eq. (35) does not happen, we have

Applying Gronwall’s inequality and applying Eq. (28) concludes the proof. ∎

Appendix C Proof of Theorem 1 part (B)

The difference in the proof of part (B) with the proof of part (A) comes from the fact that the functions $V$ and $U$ are not bounded and Lipschitz anymore, and that $\hat{f}({\bm{x}};{\bm{\theta}})$ is not bounded by a constant. However, we show that when starting from an initial distribution $\rho_{0}$ with compact support in the variable $a$, the support of $\rho_{t}$ in the variable $a$ remains bounded uniformly on the interval $[0,T]$ by a constant that only depends on the $K_{i}$, $i=1,2,3,4$, and $T$.

For ${\bm{\theta}}=(a,{\bm{w}})$ and ${\bm{\theta}}^{\prime}=(a^{\prime},{\bm{w}}^{\prime})$, remember we have

Throughout this section, the assumptions A1 - A4 are understood to hold. For the sake of simplicity we will write the proof under the following restriction:

The step size function $\xi(t)\equiv 1/2$.

The proof for a general function $\xi(t)$ is obtained by a straightforward adaptation.

We define the four dynamics with the same definitions as at the beginning of Section B. We copy them here for reader’s convenience.

The nonlinear dynamics (ND): $(\bar{\bm{\theta}}^{t}_{i})_{i\in[N],t\geq 0}$ with initialization $\bar{\bm{\theta}}^{0}_{i}\sim\rho_{0}$ i.i.d.:

where we denoted ${\bm{G}}({\bm{\theta}};\rho)=-\nabla\Psi({\bm{\theta}};\rho)=-\nabla V({\bm{\theta}})-\int\nabla_{1}U({\bm{\theta}},{\bm{\theta}}^{\prime})\rho({\rm d}{\bm{\theta}}^{\prime})$.

The particle dynamics (PD): $(\underline{\bm{\theta}}^{t}_{i})_{i\in[N],t\geq 0}$ with initialization $\underline{\bm{\theta}}_{i}^{0}=\bar{\bm{\theta}}_{i}^{0}$:

where ${\underline{\rho}}^{(N)}_{t}=(1/N)\sum_{i=1}^{N}\delta_{\underline{\bm{\theta}}_{i}^{t}}$.

where ${\bm{F}}_{i}({\bm{\theta}}^{k};{\bm{z}}_{k+1})=(y_{k+1}-\hat{y}_{k+1})\nabla_{{\bm{\theta}}}\sigma_{\star}({\bm{x}}_{k+1};{\bm{\theta}}^{k}_{i})$, with ${\bm{z}}_{k}\equiv({\bm{x}}_{k},y_{k})$ and $\hat{y}_{k+1}=(1/N)\sum_{j=1}^{N}a_{j}^{k}\sigma({\bm{x}}_{k+1};{\bm{w}}^{k}_{j})$.

By Proposition 5, 6, 7, 8, there exists constants $K$ and $K_{0}$, such that if we take $\varepsilon\leq 1/[K_{0}(D+\log N+z^{2})e^{K_{0}(1+T)^{3}}]$, with probability at least $1-e^{-z^{2}}$, we have

Combining these inequalities, and noting that $Ke^{K(1+T)^{3}}\leq K^{\prime}e^{K^{\prime}T^{3}}$ for some $K^{\prime}\geq K$, give the conclusion of Theorem 1 (B). In the following subsections, we prove all the above interpolation bounds, under the setting of Theorem 1 (B).

There exists a constant K depending only on the $K_{i}$, $i=1,2,3,4$, such that

Step 1. Let $\bar{\bm{\theta}}_{i}^{t}=({\bar{a}}_{i}^{t},{\bar{\bm{w}}}_{i}^{t})$, and $\hat{y}({\bm{x}};\rho_{t})=\int a\sigma({\bm{x}};{\bm{w}})\rho_{t}({\rm d}{\bm{\theta}})$. Note that along the PDE, we have

The nonlinear dynamics for ${\bar{a}}_{i}^{t}$ gives

Step 2. Denote $\underline{\bm{\theta}}_{i}^{t}=({\underline{a}}_{i}^{t},{\underline{{\bm{w}}}}_{i}^{t})$, ${\underline{\rho}}_{t}^{(N)}=(1/N)\sum_{i=1}^{N}\delta_{\underline{\bm{\theta}}_{i}^{t}}$, and denote $\underline{y}({\bm{x}};\underline{\bm{\theta}}^{t})=(1/N)\sum_{i\in[N]}{\underline{a}}_{i}^{t}\sigma({\bm{x}};{\underline{{\bm{w}}}}_{i}^{t})$. Note along the PDE, we have

Hence we have (note $|y|\leq K$, $|\sigma|\leq K$, and $|{\underline{a}}_{i}^{0}|\leq K$)

The nonlinear dynamics for ${\underline{a}}_{i}^{t}$ gives

Denoting ${\bm{\theta}}=(a,{\bm{w}})$, ${\bm{\theta}}_{1}=(a_{1},{\bm{w}}_{1})$ and ${\bm{\theta}}_{2}=(a_{2},{\bm{w}}_{2})$. We have

There exists a constant $K$ such that for any time $0\leq s<t$

This lemma holds by the bounds of $\nabla V$ and $\nabla_{1}U$ in Lemma 8 and the bounds for $|{\bar{a}}_{i}^{t}|,|{\underline{a}}_{i}^{t}|$ in Lemma 7, and by the inequality

C.2 Bound between PDE and nonlinear dynamics

There exists a constant $K$, such that with probability at least $1-e^{-z^{2}}$, we have

We decompose the difference into the following two terms

where the expectation is taken with respect to $\bar{\bm{\theta}}_{i}^{0}\sim\rho_{0}$. The result holds simply by combining Lemma 10 and Lemma 11. ∎

Let ${\bm{\theta}}=({\bm{\theta}}_{1},\ldots,{\bm{\theta}}_{i},\ldots,{\bm{\theta}}_{N})$ and ${\bm{\theta}}^{\prime}=({\bm{\theta}}_{1},\ldots,{\bm{\theta}}_{i}^{\prime},\ldots{\bm{\theta}}_{N})$ be two configurations that differ only in the $i$’th variable. Assuming $a,a^{\prime}\in[-K(1+t),K(1+t)]$, then

Note we have ${\bar{a}}_{i}^{t}\in[-K(1+t),K(1+t)]$, applying McDiarmid’s inequality, we have

By Lemma 9, 8 and 7, for $0\leq s<t$, we have

Hence taking union bound over $s\in\eta\{0,1,\ldots,\lfloor T/\eta\rfloor\}$ and bounding difference between time in the interval and grid, we have

Now taking $\eta=1/\sqrt{N}$ and $\delta=K(1+T)^{4}[\sqrt{\log(NT)}+z]/\sqrt{N}$, we get the desired inequality. ∎

C.3 Bound between nonlinear dynamics and particle dynamics

There exists a constant $K$, such that with probability at least $1-e^{-z^{2}}$, we have

The last inequality follows by Lemma 8 and 7. Now we would like to prove a uniform bound for $I_{i}^{t}$ for $i\in[N]$ and $t\in[0,T]$.

By Lemma 9, there exists $K$ such that, for any $0\leq s<t\leq T$ and $i\in[N]$, we have

Taking the union bound over $i\in[N]$ and $s\in\eta[T/\eta]$ and bounding time in the interval and the grid, we have

Taking $\eta=\sqrt{1/N}$, and $\delta=K[\sqrt{\log(NT)}+z]/\sqrt{N}$, we get the desired result. ∎

Denote $\delta(N,T,z)=K(1+T)^{2}[\sqrt{\log(NT)}+z]/\sqrt{N}$ and

We condition on the good event in Lemma 12 to happen. By Eq. (43), we have

This happens with probability $1-e^{-z^{2}}$. This proves Eq. (41). Finally, Eq. (42) holds by Lemma 8. ∎

C.4 Bound between particle dynamics and GD

There exists constants $K$ and $K_{0}$ such that, letting $\varepsilon\leq 1/(K_{0}e^{K_{0}(1+T)^{3}})$, we have for any $t\leq T$,

By Lemma 9 and 8, for $0\leq s\leq t$, we have

Let $T_{\Delta}=\inf\{t\mathrel{\mathop{\mathchar 58\relax}}\Delta(t)\geq 1\}$. For $t\leq T_{\Delta}$, we have $\Delta(s)^{2}\leq\Delta(s)$. Applying Gronwall’s lemma, we get for any $t\leq T_{\Delta}$,

Note we assumed $\varepsilon\leq 1/(K_{0}e^{K_{0}(1+T)^{3}})$, which gives $Ke^{K(1+T)^{2}T}\varepsilon\leq 1/2$. This shows that $T_{\Delta}\geq T$. Hence we get

Finally, applying the last inequality in Lemma 8 concludes the proof. ∎

C.5 Bound between GD and SGD

There exists constants $K$ and $K_{0}$, such that if we take $\varepsilon\leq 1/[K_{0}(D+\log N+z^{2})e^{K_{0}(1+T)^{3}}]$, the following holds with probability at least $1-e^{-z^{2}}$: for any $t\leq T$, we have

where $\rho^{(N)}_{k}\equiv(1/N)\sum_{i\in[N]}\delta_{{\bm{\theta}}^{k}_{i}}$ denotes the empirical distribution of the iterates of SGD. Hence we get:

where $\hat{y}({\bm{x}}_{k+1},{\bm{\theta}}^{k})=(1/N)\sum_{j=1}^{n}a_{j}^{k}\sigma({\bm{x}}_{k+1};{\bm{w}}_{j}^{k})$.

The following discussion is under the conditional law ${\mathcal{L}}(\,\cdot\,|{\mathcal{F}}_{k})$. Note that $|\sigma({\bm{x}}_{k+1};{\bm{w}}_{i}^{k})|\leq K$, and $|y_{k+1}-\hat{y}_{k+1}({\bm{\theta}}^{k})|\leq K(1+\max_{j}|a_{j}^{k}|)$, hence $(y_{k+1}-\hat{y}({\bm{x}}_{k+1},{\bm{\theta}}^{k}))\sigma({\bm{x}}_{k+1};{\bm{w}}_{i}^{k})$ is $K(1+\max_{i}|a_{i}^{k}|)$-sub-Gaussian. Furthermore, $\nabla_{\bm{w}}\sigma({\bm{x}}_{k+1};{\bm{w}}_{i}^{k})$ is a $K$-sub-Gaussian random vector, and $|(y_{k+1}-\hat{y}({\bm{x}}_{k+1},{\bm{\theta}}^{k}))a_{i}^{k}|\leq K(1+\max_{i}|a_{i}^{k}|)^{2}$, hence $(y_{k+1}-\hat{y}({\bm{x}}_{k+1},{\bm{\theta}}^{k}))a_{i}^{k}\nabla_{\bm{w}}\sigma({\bm{x}}_{k+1};{\bm{w}}_{i}^{k})$ is a $K(1+\max_{j}|a_{j}^{k}|)^{2}$-sub-Gaussian random vector. As a result, we have ${\bm{F}}_{i}({\bm{\theta}}^{k};{\bm{z}}_{k+1})$ under the conditional law ${\mathcal{L}}(\,\cdot\,|{\mathcal{F}}_{k})$ is a $K(1+\max_{j}|a_{j}^{k}|)^{2}$-sub-Gaussian random vector (concatenation of two possibly dependent sub-Gaussian random vectors is sub-Gaussian).

Let $T_{a}=\min\{l\mathrel{\mathop{\mathchar 58\relax}}\max_{i\in[N]}|a_{i}^{l}|\geq M_{T}\}$ where $M_{T}\equiv 2K(1+T)$. Then we have

Now let ${\bar{\bm{A}}}_{i}^{k}={\bm{A}}_{i}^{k\wedge T_{a}}$. Then ${\bar{\bm{A}}}_{i}^{k}$ is also a martingale. Furthermore, we have

Hence we can apply Azuma-Hoeffding’s concentration bound (Lemma 31) to $\|{\bar{\bm{A}}}_{i}^{l}\|_{2}$,

and taking the union bound over $i\in[N]$, we get:

Denote the above event to be a good event $E_{{\rm good}}$,

Since we choose $\varepsilon\leq 1/[K_{0}(D+\log N+z^{2})e^{K_{0}(1+T)^{3}}]$, we have

Moreover, for $t\leq T_{a}\wedge T_{\Delta}\wedge T$, we have

This means that the stopping times $T_{a},T_{\Delta}\geq T$. Hence, for any $t\leq T$, we have

Note all these happens when event $E_{{\rm good}}$ happens. Hence, the probability such that the events above happens is at least $1-e^{-z^{2}}$. Finally, by Lemma 8, we have the desired bound on $R_{N}$. This concludes the proof. ∎

Appendix D Proof of Theorem 2 part (A)

The proof follows the same scheme as for Theorem 1 (A) and we will limit ourselves to describing the differences.

Throughout this section, the assumptions A1-A6 of Theorem 2 are understood to hold. For the sake of simplicity we will write the proof under the following restriction:

The step size function $\xi(t)\equiv 1/2$.

The proof for a general function $\xi(t)$ is obtained by a straightforward adaptation.

For the reader’s convenience, we copy here the limiting PDE:

We will consider four different coupled dynamics with same initialization $(\bar{\bm{\theta}}^{0}_{i})_{i\leq N}\sim_{iid}\rho_{0}$ and stochastic term. We will denote $\{{\bm{W}}_{i}(s)\}_{s\geq 0}$ for $i\in[N]$ independent $D$-dimensional Brownian motions. The integral equations and summation forms of the four dynamics are as follows:

where we denoted ${\bm{G}}({\bm{\theta}};\rho)=-\nabla\Psi_{\lambda}({\bm{\theta}};\rho)=-\lambda{\bm{\theta}}-\nabla V({\bm{\theta}})-\int\nabla_{{\bm{\theta}}}U({\bm{\theta}},{\bm{\theta}}^{\prime})\rho({\rm d}{\bm{\theta}}^{\prime})$, and $\bar{\bm{\theta}}\sim\rho_{0}$ i.i.d.

where $\underline{\bm{\theta}}^{0}_{i}=\bar{\bm{\theta}}^{0}_{i}$.

where we denoted ${\bm{F}}_{i}({\bm{\theta}}^{k};{\bm{z}}_{k+1})=-\lambda{\bm{\theta}}_{i}^{k}+(y_{k+1}-\hat{y}_{k+1})\nabla_{{\bm{\theta}}_{i}}\sigma_{\star}({\bm{x}}_{k+1};{\bm{\theta}}^{k}_{i})$, and ${\bm{\theta}}^{0}_{i}=\bar{\bm{\theta}}^{0}_{i}$.

By Proposition 9, 10, 11, 12, there exists constants $K$ and $K_{0}$, such that with probability at least $1-e^{-z^{2}}$, we have

Combining these inequalities gives the conclusion of Theorem 2 (A). In the following subsections, we prove all the above interpolation bounds, under the setting of Theorem 2 (A).

Define the maximum and the average of the norm of the initialization:

Similarly define the following bounds on the Brownian noise:

Let us first consider a generic $D$-dimensional $K^{2}$-sub-Gaussian random vector ${\bm{X}}$, we have:

Taking the union bound over $i\in[N]$, and noting that $|a_{i}^{0}|\leq K$, we get:

Taking $\mu=D/(2K^{2})$ and $u=2K[\sqrt{D+\log N}+z]/\sqrt{D}$, we get:

Let us now consider the average over $i\in[N]$ of the $\|{\bm{w}}^{0}_{i}\|_{2}$, which are independent, we get:

Taking $\mu=D/(2K^{2})$ and $u=2K\left[1+z\right]$, noting $(1/N)\sum_{i=1}^{N}|a_{i}^{0}|\leq K$, we get:

Similarly, we consider $\overline{\bm{W}}_{i}(t)\equiv\sqrt{\tau/D}{\bm{W}}_{i}(t)$ which is a $D$-dimensional Gaussian random variable with variance $\text{Var}(\overline{W}^{j}_{i}(t))=\int_{0}^{t}(\tau/D){\rm d}s=\tau t/D$. We note that $\exp\{\mu\|{\bm{W}}_{i}(t)\|_{2}^{2}\}$ is a sub-martingale and by Doob’s martingale inequality, we have:

Taking the union bound over $i\in[N]$ gives:

Taking $\mu=D/(4\tau T)$ and $u=4\sqrt{T\tau}[\sqrt{D+\log N}+z]/\sqrt{D}$, we get:

We can consider the average over $i\in[N]$ of the preceding bound, by noticing that:

where ${\bm{W}}(t)$ is a $ND$-dimensional Brownian motion. We can therefore apply Doob’s martingale inequality to the sub-martingale $\exp\{\mu\|{\bm{W}}(t)\|^{2}_{2}\}$. We have

Taking $\mu=D/(4\tau T)$ and $u=4\sqrt{T\tau}[1+z]$, we get:

The two following lemmas are modified from [MMN18, Section 7.2, Lemma 7.5].

Define $\Delta_{i}(t)\equiv\sup_{s\leq t}\|\bar{\bm{\theta}}^{t}_{i}\|_{2}$. From Eq. (45),

which gives, after applying Gronwall’s inequality with the bounds of Lemma 13:

Consider $\Delta_{i}(h;k,\varepsilon)=\sup_{0\leq u\leq\varepsilon}\|\bar{\bm{\theta}}_{i}^{k\varepsilon+u}-\bar{\bm{\theta}}_{i}^{k\varepsilon}\|_{2}$. We have

where we defined $\overline{\bm{W}}_{i,k}(u)\equiv\int_{k\varepsilon}^{k\varepsilon+u}\sqrt{\tau/D}{\rm d}{\bm{W}}_{i}(s)$. By a similar computation as in Lemma 13, we have

Combining this bound and Eq. (47) yields:

We now bound $W_{2}(\rho_{t},\rho_{t+h})$:

Integrating this upper bound on the probability yields the desired inequality. ∎

The exact same proof shows a similar lemma for the particle dynamics.

D.2 Bound between PDE and nonlinear dynamics

There exists a constant $K$ such that with probability at least $1-e^{-z^{2}}$, we have

We will follow the same decomposition as in the proof of Proposition 1. The proof of term II only depend on the upper bound on the potential $U$ and still apply. The term I bound follow from a similar proof as lemma 5.

Furthermore we have the following increment bound for $t,h\geq 0$:

with probability at least $1-e^{-z^{2}}$. Hence taking an union bound over $s\in\eta\{0,1,\ldots,\lfloor T/\eta\rfloor\}$ and bounding the variation inside the grid intervals, we have

Taking $\eta=1/N$ and $\delta=K[\sqrt{\log(NT)}+z]/\sqrt{N}$ concludes the proof. ∎

D.3 Bound between nonlinear dynamics and particle dynamics

There exists a constant $K$, such that with probability at least $1-e^{-z^{2}}$, we have

The nonlinear dynamics and the particle dynamics are coupled by using the same Brownian motion, and the noise term cancel out. By the same calculation as in Proposition 2, we get

Now we would like to prove a uniform bound for $I^{t}_{i}$ for $i\in[N]$ and $t\in[0,T]$.

We then bound the variation of $I_{i}^{s}$ over an interval $[t,t+h]$, with $t,h\geq 0$:

By Lemma 14, there exists $K$ such that, we have

Taking an union bound for $i\in[N]$ and $s\in\eta\{0,1,\ldots,\lfloor T/\eta\rfloor\}$ and bounding the variation inside the grid intervals, we have

Taking $\eta=1/N$, and $\delta=K[\sqrt{\log(NT)}+z]/\sqrt{N}$, we get the desired result. ∎

Denote $\delta_{N}(T,z)=Ke^{KT}[\sqrt{\log(NT)}+z]/\sqrt{N}$ and

With probability at least $1-e^{-z^{2}}$, we have

which, after applying Gronwall’s inequality, concludes the proof. ∎

D.4 Bound between particle dynamic and GD

There exists a constant $K$ such that with probability at least $1-e^{-z^{2}}$, we have

with probability at least $1-e^{-z^{2}}$. Denote $\delta(N,T,z)=TKe^{KT}\left[\sqrt{\log{(N(T/\varepsilon\vee 1))}}+z\right]\sqrt{\varepsilon}$ and

With probability at least $1-e^{-z^{2}}$, we get

Applying Gronwall’s inequality concludes the proof. ∎

D.5 Bound between GD and SGD

There exists a constant $K$ such that, with probability at least $1-e^{-z^{2}}$, we have

Appendix E Proof of Theorem 2 part (B)

We remind the notations used in the proof of Theorem 1 (B): for ${\bm{\theta}}=(a,{\bm{w}})$ and ${\bm{\theta}}^{\prime}=(a^{\prime},{\bm{w}}^{\prime})$,

For convenience, we copy here the properties of the potentials $V({\bm{\theta}})$ and $U({\bm{\theta}},{\bm{\theta}}^{\prime})$ listed in Lemma 8. Denoting ${\bm{\theta}}=(a,{\bm{w}})$, ${\bm{\theta}}_{1}=(a_{1},{\bm{w}}_{1})$ and ${\bm{\theta}}_{2}=(a_{2},{\bm{w}}_{2})$. We have

Throughout this section, the assumptions A1 - A6 are understood to hold. For the sake of simplicity we will write the proof under the following restriction:

The step size function $\xi(t)\equiv 1/2$.

The proof for a general function $\xi(t)$ is obtained by a straightforward adaptation.

We will consider four different coupled dynamics with same initialization $(\bar{\bm{\theta}}^{0}_{i})_{i\leq N}\sim_{iid}\rho_{0}$. The integral equations and summation form are as follows:

where we denoted ${\bm{G}}({\bm{\theta}};\rho)=-\nabla\Psi_{\lambda}({\bm{\theta}};\rho)=-\lambda{\bm{\theta}}-\nabla V({\bm{\theta}})-\int\nabla_{{\bm{\theta}}}U({\bm{\theta}},{\bm{\theta}}^{\prime})\rho({\rm d}{\bm{\theta}}^{\prime})$, and $\bar{\bm{\theta}}\sim\rho_{0}$ iid.

where $\underline{\bm{\theta}}^{0}_{i}=\bar{\bm{\theta}}^{0}_{i}$.

where we defined ${\bm{F}}_{i}({\bm{\theta}}^{k};{\bm{z}}_{k+1})=-\lambda{\bm{\theta}}_{i}^{k}+(y_{k+1}-\hat{y}_{k+1})\nabla_{{\bm{\theta}}_{i}}\sigma_{\star}({\bm{x}}_{k+1};{\bm{\theta}}^{k}_{i})$, and ${\bm{\theta}}^{0}_{i}=\bar{\bm{\theta}}^{0}_{i}$.

By Proposition 13, 14, 15, 16, there exists constants $K$, such that with probability at least $1-e^{-z^{2}}$, we have

Combining these inequalities gives the conclusion of Theorem 2 (B). In the following subsections, we prove all the above interpolation bounds, under the setting of Theorem 2 (B).

The bounds on the potentials $U,V$, and their derivatives scales with the coefficients $a$, which can be arbitrarily large with non-zero probability due to the Brownian noise. In our analysis we will need to keep track of the maximum and the first moment of $|a|$ for each of the different dynamics. In this section we will show that there exists high probability bounds along the trajectories.

We recall the following notations introduced in Appendix Section D.1,

For convenience, we recall here the bounds derived in Lemma 13:

There exists a constant $K$, such that denoting $M_{2}(t)=Ke^{Kt}$, we have

Furthermore, letting $({\bar{a}}^{t},{\bar{\bm{w}}}^{t})\sim\rho_{t}$, then ${\bar{a}}^{t}$ is $M_{2}(t)$-sub-Gaussian.

Denote $A(t)=\int a^{2}\rho_{t}({\rm d}a)/2$. For simplicity, we will directly take the derivative of this function. This computation can be made rigorous by considering smooth approximation of a truncated squared function, with bounded second derivative, and using the definition of weak solution. We get:

which implies by applying Gronwall’s lemma we have

Let us consider the nonlinear dynamics for the variable ${\bar{a}}^{t}\sim\rho_{t}$:

Denote $u_{\lambda}(t)={\bar{a}}^{t}e^{\lambda t}$ and

We deduce that we can rewrite ${\bar{a}}^{t}\sim\rho_{t}$ as the sum of three random variables:

By assumption $a_{0}$ is $K$-bounded, and thus $\Gamma_{1}$ is $K^{2}$-sub-Gaussian. By the boundedness of $u$ and $v$, Cauchy Schwartz inequality, and by $A(t)\leq M_{2}(t)$, then for $s\leq t$, we have $|K({\bar{\bm{w}}}^{s},\rho_{s})|\leq Ke^{Kt}$, hence the random variable $\Gamma_{2}$ is $Ke^{Kt}$-bounded and thus $Ke^{Kt}$-sub-Gaussian. The random variable $\Gamma_{3}$ is a Gaussian random variable with variance

We deduce that ${\bar{a}}^{t}$ is the sum of three (dependent) sub-Gaussian random variables with parameters $K^{2},Ke^{Kt},Kt$ respectively, and therefore the sum ${\bar{a}}^{t}$ is $Ke^{Kt}$-sub-Gaussian. ∎

There exists a constant $K$ such that with probability at least $1-e^{-z^{2}}$, we have

Let us start with the non-linear dynamics trajectories. We have in integral form:

where we recall that $\overline{W}^{a}_{i}(t)=\sqrt{\tau/D}W^{a}_{i}(t)$. Applying Gronwall’s lemma to $\Delta(t)=\sup_{s\in[0,t]}|\bar{a}^{s}_{i}|$ with Lemma 13 gives: