A Mean Field View of the Landscape of Two-Layers Neural Networks

Introduction

Multi-layer neural networks are one of the oldest approaches to statistical machine learning, dating back at least to the 1960’s [Ros62]. Over the last ten years, under the impulse of increasing computer power and larger data availability, they have emerged as a powerful tool for a wide variety of learning tasks [KSH12, GBCB16].

In practice, the parameters of neural networks are learned by stochastic gradient descent [RM51] (SGD) or its variants. In the present case, this amounts to the iteration

Here ${\bm{\theta}}^{k}=({\bm{\theta}}^{k}_{i})_{i\leq N}$ denotes the parameters after $k$ iterations, $s_{k}$ is a step size, and $({\bm{x}}_{k},y_{k})$ is the $k$-th example. Throughout the paper, we make the following assumption:

In large scale applications, this is not far from truth: the data is so large that each example is visited at most a few times [Bot10]. Further, theoretical guarantees suggest that there is limited advantage to be gained from multiple passes [SSBD14]. For recent work deriving scaling limits under such assumption (in different problems) see [WML17].

Formal relationships can be established between $R_{N}({\bm{\theta}})$ and $R(\rho)$. For instance, under mild assumptions, $\inf_{{\bm{\theta}}}R_{N}({\bm{\theta}})=\inf_{\rho}R(\rho)+O(1/N)$. We refer to the next sections for mathematical statements of this type.

Roughly speaking, $R(\rho)$ corresponds to the population risk when the number of hidden units goes to infinity, and the empirical distribution of parameters $\hat{\rho}^{(N)}$ converges to $\rho$. Since $U(\,\cdot\,,\,\cdot\,)$ is positive semidefinite, we obtain that the risk becomes convex in this limit. The fact that learning can be viewed as convex optimization in an infinite-dimensional space was indeed pointed out in the past [LBW96, BRV+06]. Does this mean that the landscape of the population risk simplifies for large $N$ and descent algorithms will converge to a unique (or nearly unique) global optimum?

when $N\to\infty$, ${\varepsilon}\to 0$ (here $\Rightarrow$ denotes weak convergence). The asymptotic dynamics of $\rho_{t}$ is defined by the following PDE, which we shall refer to as distributional dynamics (DD)

Using these results, analyzing learning in two-layer neural networks reduces to analyzing the PDE (7). While this is far from being an easy task, the PDE formulation leads to several simplifications and insights. First of all, it factors out the invariance of the risk (4) (and of the SGD dynamics (3)), with respect to permutations of the units $\{1,\dots,N\}$.

where the infimum is taken over all couplings of $\rho_{1}$ and $\rho_{2}$. Informally, the fact that $\rho_{t}$ is a gradient flow means that (7) is equivalent, for small $\tau$, to

Powerful tools from the mathematical literature on gradient flows in measure spaces [AGS08] can be exploited to study the behavior of (7).

Most importantly, the scaling limit elucidates the dependence of the landscape of two-layer neural networks on the number of hidden units $N$.

A remarkable feature of neural networks is the observation that, while they might be dramatically over parametrized, this does not lead to performance degradation. In the case of bounded activation functions, this phenomenon was clarified in the nineties for empirical risk minimization algorithms, see e.g. [Bar98]. The present work provides analogous insight for the SGD dynamics: roughly speaking, our results imply that the landscape remains essentially unchanged as $N$ grows, provided $N\gg D$. In particular, assume that the PDE (7) converges close to an optimum in time $t_{*}(D)$. This might depend on $D$, but does not depend on the number of hidden units $N$ (which does not appear in the DD PDE (7)). If $t_{*}(D)=O_{D}(1)$, we can then take $N$ arbitrarily (as long as $N\gg D$) and will achieve a population risk which is independent of $N$ (and corresponds to the optimum), using $k=t_{*}/{\varepsilon}=O(D)$ samples.

Our analysis can accommodate some important variants of SGD, a particularly interesting one being noisy SGD:

where $\Psi_{\lambda}({\bm{\theta}};\rho)=\Psi({\bm{\theta}};\rho)+(\lambda/2)\|{\bm{\theta}}\|_{2}^{2}$, and $\Delta_{{\bm{\theta}}}f({\bm{\theta}})=\sum_{i=1}^{d}\partial_{\theta_{i}}^{2}f({\bm{\theta}})$ denotes the usual Laplacian. This can be viewed as a gradient flow for the free energy $F_{\beta,\lambda}(\rho)=(1/2)R(\rho)+(\lambda/2)\int\|{\bm{\theta}}\|_{2}^{2}\rho({\rm d}{\bm{\theta}})-\beta^{-1}{\rm Ent}(\rho)$, where ${\rm Ent}(\rho)=-\int\rho({\bm{\theta}})\log\rho({\bm{\theta}})\,{\rm d}{\bm{\theta}}$ is the entropy of $\rho$ (by definition ${\rm Ent}(\rho)=-\infty$ if $\rho$ is singular). $F_{\beta,\lambda}(\rho)$ is an entropy-regularized risk, which penalizes strongly non-uniform $\rho$.

We will prove below that, for $\beta<\infty$, the evolution (12) generically converges to the minimizer of $F_{\beta,\lambda}(\rho)$, hence implying global convergence of noisy SGD in a number of steps independent of $N$.

Examples

With probability $1/2$: $y=+1$, ${\bm{x}}\sim{\sf N}(0,(1+\Delta)^{2}{\bm{I}}_{d})$

With probability $1/2$: $y=-1$, ${\bm{x}}\sim{\sf N}(0,(1-\Delta)^{2}{\bm{I}}_{d})$.

(This example will be generalized later.) Of course, optimal classification in this model becomes entirely trivial if we compute the feature $h({\bm{x}})=\|{\bm{x}}\|_{2}$. However, it is non-trivial that a SGD-trained neural network will succeed.

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 as a running example: $\sigma(t)=s_{1}$ if $t\leq t_{1}$, $\sigma(t)=s_{2}$ if $t\geq t_{2}$, and $\sigma(t)$ interpolated linearly for $t\in(t_{1},t_{2})$. In simulations we use $t_{1}=0.5$, $t_{2}=1.5$, $s_{1}=-2.5$, $s_{2}=7.5$.

where the form of $\psi(r;\rho)$ can be derived from $\Psi({\bm{\theta}};\rho)$. This reduced PDE can be efficiently solved numerically, see Supplementary Information (SI) for technical details. As illustrated by Fig. 1, the empirical results match closely the predictions produced by this PDE.

In Fig. 2, we compare the asymptotic risk achieved by SGD with the prediction obtained by minimizing $R(\rho)$, cf. (5) over spherically symmetric distributions. It turns out that, for certain values of $\Delta$, the minimum is achieved by the uniform distribution over a sphere of radius $\|{\bm{w}}\|_{2}=r_{*}$, to be denoted by $\rho^{\mbox{\tiny\rm unif}}_{r_{*}}$. The value of $r_{*}$ is computed by minimizing

where expressions for $v(r)$, $u_{d}(r_{1},r_{2})$ can be readily derived from $V({\bm{w}})$, $U({\bm{w}}_{1},{\bm{w}}_{2})$ and are given in the SI.

Let $r_{*}$ be a global minimizer of $r\mapsto R_{d}^{(1)}(r)$. Then $\rho^{\mbox{\tiny\rm unif}}_{r_{*}}$ is a global minimizer of $\rho\mapsto R(\rho)$ if and only if $v(r)+u_{d}(r,r_{*})\geq v(r_{*})+u_{d}(r_{*},r_{*})$ for all $r\geq 0$.

Checking numerically this condition yields that $\rho^{\mbox{\tiny\rm unif}}_{r_{*}}$ is a global minimizer for $\Delta$ in an interval $[\Delta^{\rm l}_{d},\Delta^{\rm h}_{d}]$, where $\lim_{d\to\infty}\Delta^{\rm l}_{d}=0$ and $\lim_{d\to\infty}\Delta^{\rm h}_{d}=\Delta_{\infty}\approx 0.47$.

for any $k\in[T/{\varepsilon},10T/{\varepsilon}]$ with probability at least $1-\delta$.

In particular, if we set ${\varepsilon}=1/(C_{0}d)$, then the number of SGD steps is $k\in[(C_{0}T)\,d,(10C_{0}T)\,d]$: the number of samples used by SGD does not depend on the number of hidden units $N$, and is only linear in the dimension. Unfortunately the proof does not provide the dependence of $T$ on $\eta$, but Theorem 6 below suggests exponential local convergence.

2 Centered anisotropic Gaussians

We can generalize the previous result to a problem in which the network needs to select a subset of relevant nonlinear features out of many a priori equivalent ones. We assume the joint law of $(y,{\bm{x}})$ to be as follows:

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

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

Even with a reduced degree of symmetry, SGD converges to a network with nearly-optimal risk, after using a number of samples $k=O(d)$, which is independent of the number of hidden units $N$.

3 A better activation function

We consider the same data distribution introduced in the last section (anisotropic Gaussians). Figure 3 reports the evolution of the risk $R_{N}({\bm{\theta}}^{k})$ for three experiments with $d=320$, $s_{0}=60$ and different values of $\Delta$. SGD is initialized by setting $a_{i}=1$, $b_{i}=1$ and ${\bm{w}}_{i}^{0}\sim_{iid}{\sf N}({\mathbf{0}},0.8^{2}/d\cdot{\bm{I}}_{d})$ for $i\leq N$. We observe that SGD converges to a network with very small risk, but this convergence has a nontrivial structure and presents long flat regions.

The empirical results are well captured by our predictions based on the continuum limit. In this case we obtain a reduced PDE for the joint distribution of the four quantities ${\bm{r}}=(a,b,r_{1}=\|{\bm{P}}_{{\cal V}}{\bm{w}}\|_{2},r_{2}=\|{\bm{P}}^{\perp}_{{\cal V}}{\bm{w}}\|_{2})$, denoted by $\overline{\rho}_{t}$. The reduced PDE is analogous to (13) albeit in $4$ rather than $1$ dimensions. In Figure 3 we consider the evolution of the risk, alongside three properties of the distribution $\overline{\rho}_{t}$ –the means of the output weight $a$, of the offset $b$, and of $r_{1}$.

4 Predicting failure

SGD does not always converge to a near global optimum. Our analysis allows to construct examples in which SGD fails. For instance, Figure 4 reports results for isotropic Gaussians problem. We violate the assumptions of Theorem 1 by using non monotone activation function. Namely, we use $\sigma_{*}({\bm{x}};{\bm{\theta}})=\sigma(\langle{\bm{w}},{\bm{x}}\rangle)$, where $\sigma(t)=-2.5$ for $t\leq 0$, $\sigma(t)=7.5$ for $t\geq 1.5$, and $\sigma(t)$ linearly interpolates from $(0,-2.5)$ to $(0.5,-4)$, and from $(0.5,-4)$ to $(1.5,7.5)$.

Depending on the initialization, SGD converges to two different limits, one with a small risk, and the second with high risk. Again this behavior is well tracked by solving a one-dimensional PDE for the distribution $\overline{\rho}_{t}$ of $r=\|{\bm{w}}\|_{2}$.

General results

In this section we return to the general supervised learning problem described in the introduction and describe our general results. Proofs are deferred to the SI.

First, we note that the minimum of the asymptotic risk $R(\rho)$ of (5) provides a good approximation of the minimum of the finite-$N$ risk $R_{N}({\bm{\theta}})$.

We next consider the distributional dynamics (7) and (12). These should be interpreted to hold in weak sense, cf. SI. In order to establish that these PDEs indeed describe the limit of the SGD dynamics, we make the following assumptions.

$t\mapsto\xi(t)$ is bounded Lipschitz: $\|\xi\|_{\infty},\|\xi\|_{\mbox{\tiny\rm Lip}}\leq K_{1}$, with $\int_{0}^{\infty}\xi(t){\rm d}t=\infty$.

The activation function $({\bm{x}},{\bm{\theta}})\mapsto\sigma_{*}({\bm{x}};{\bm{\theta}})$ is bounded, with sub-Gaussian gradient: $\|\sigma_{*}\|_{\infty}\leq K_{2}$, $\|\nabla_{{\bm{\theta}}}\sigma_{*}(\bm{X};{\bm{\theta}})\|_{\psi_{2}}\leq K_{2}$. Labels are bounded $|y_{k}|\leq K_{2}$.

The gradients ${\bm{\theta}}\mapsto\nabla V({\bm{\theta}})$, $({\bm{\theta}}_{1},{\bm{\theta}}_{2})\mapsto\nabla_{{\bm{\theta}}_{1}}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})$ are bounded, Lipschitz continuous (namely $\|\nabla_{{\bm{\theta}}}V({\bm{\theta}})\|_{2}$, $\|\nabla_{{\bm{\theta}}_{1}}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})\|_{2}\leq K_{3}$, $\|\nabla_{{\bm{\theta}}}V({\bm{\theta}})-\nabla_{{\bm{\theta}}}V({\bm{\theta}}^{\prime})\|_{2}\leq K_{3}\|{\bm{\theta}}-{\bm{\theta}}^{\prime}\|_{2}$, $\|\nabla_{{\bm{\theta}}_{1}}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})-\nabla_{{\bm{\theta}}_{1}}U({\bm{\theta}}^{\prime}_{1},{\bm{\theta}}_{2}^{\prime})\|_{2}\leq K_{3}\|({\bm{\theta}}_{1},{\bm{\theta}}_{2})-({\bm{\theta}}_{1}^{\prime},{\bm{\theta}}_{2}^{\prime})\|_{2}$).

We also introduce the following error term which quantifies in a non-asymptotic sense the accuracy of our PDE model

The convergence of the SGD process to the PDE model is an example of a phenomenon which is known in probability theory as propagation of chaos [Szn91].

with probability $1-e^{-z^{2}}$. The same statements hold for noisy SGD (11), provided (7) is replaced by (12), and if $\beta\geq 1$, $\lambda\leq 1$, and $\rho_{0}$ is $K_{0}$ sub-Gaussian for some $K_{0}>0$.

Notice that dependence of the error terms in $N$ and $D$ is rather benign. On the other hand, the error grows exponentially with the time horizon $T$, which limits its applicability to cases in which the DD converges rapidly to a good solution. We do not expect this behavior to be improvable within the general setting of 3, which a priori includes cases in which the dynamics is unstable.

We can regard $\bm{J}({\bm{\theta}};\rho_{t})=\rho_{t}({\bm{\theta}})\nabla_{{\bm{\theta}}}\Psi({\bm{\theta}};\rho_{t})$ as a current. The fixed points of the continuum dynamics are densities that correspond to zero current, as stated below.

Assume $V(\,\cdot\,),U(\,\cdot\,,\,\cdot\,)$ to be differentiable with bounded gradient. If $\rho_{t}$ is a solution of the PDE (7), then $R(\rho_{t})$ is non-increasing. Further, probability distribution $\rho$ is a fixed point of the PDE (7) if and only if

Note that global optimizers of $R(\rho)$, defined by condition (17), are fixed points, but the set of fixed points is, in general, larger than the set of optimizers. Our next proposition provides an analogous characterization of the fixed points of diffusion DD (12) (see [CMV+03] for related results).

Assume that conditions A1-A3 hold and that $\rho_{0}$ is absolutely continuous with respect to Lebesgue measure, with $F_{\beta,\lambda}(\rho_{0})<\infty$. If $(\rho_{t})_{t\geq 0}$ is a solution of the diffusion PDE (12), then $\rho_{t}$ is absolutely continuous. Further, there is at most one fixed point $\rho_{*}=\rho_{*}^{\beta,\lambda}$ of (12) satisfying $F_{\beta,\lambda}(\rho_{*})<\infty$. This fixed point is absolutely continuous and its density satisfies

In the next sections we state our results about convergence of the distributional dynamics to its fixed point. In the case of noisy SGD (and for the diffusion PDE (12)), a general convergence result can be established (although at the cost of an additional regularization). For noiseless SGD (and the continuity equation (12)), we do not have such general result. However, we obtain a stability condition for fixed point containing one point mass, which is useful to characterize possible limiting points (and is used in treating the examples in the previous section).

Remarkably, the diffusion PDE (12) generically admits a unique fixed point, which is the global minimum of $F_{\beta,\lambda}(\rho)$ and the evolution (12) converges to it, if initialized so that $F_{\beta,\lambda}(\rho_{0})<\infty$. This statement requires some qualifications. First of all, we introduce sufficient regularity assumptions to guarantee the existence of sufficiently smooth solutions of (12).

Next notice that the right-hand side of the fixed point equation (21) is not necessarily normalizable (for instance, it is not when $V(\,\cdot\,)$, $U(\,\cdot\,,\,\cdot\,)$ are bounded). In order to ensure the existence of a fixed point, we need $\lambda>0$.

Assume that conditions A1-A4 hold, and $1/K_{0}\leq\lambda\leq K_{0}$ for some $K_{0}>0$ Then $F_{\beta,\lambda}(\rho)$ has a unique minimizer, denoted by $\rho_{*}^{\beta,\lambda}$, which satisfies

where $C$ is a constant depending on $K_{0}$,$K_{1}$,$K_{2}$,$K_{3}$. Further, letting $\rho_{t}$ be a solution of the diffusion PDE (12) with initialization satisfying $F_{\beta,\lambda}(\rho_{0})<\infty$, we have, as $t\to\infty$,

The proof of this theorem is based on the following formula that describes the free energy decrease along the trajectories of the distributional dynamics (12):

(A key technical hurdle is of course proving that this expression makes sense, which we do by showing the existence of strong solutions.) It follows that the right-hand side must vanish as $t\to\infty$, from which we prove that (eventually taking subsequences) $\rho_{t}\Rightarrow\rho_{*}$ where $\rho_{*}$ must satisfy $\beta\Psi_{\lambda}({\bm{\theta}};\rho_{*})+\log\rho_{*}({\bm{\theta}})={\rm const}$. This in turns mean $\rho_{*}$ is a solution of the fixed point condition 21 and is in fact a global minimum of $F_{\beta,\lambda}$ by convexity.

This result can be used in conjunction with Theorem 3, in order to analyze the regularized noisy SGD algorithm (11).

2 Convergence: noiseless SGD

The next theorems provide necessary and sufficient conditions for distributions containing a single point mass to be a stable fixed point of the evolution. This result is useful in order to characterize the large time asymptotics of the dynamics (7). Here, we write $\nabla_{1}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})$ for the gradient of $U$ with respect to its first argument, and $\nabla^{2}_{1,1}U$ for the corresponding Hessian. Further, for a probability distribution $\rho_{*}$, we define

Note that $\bm{H}_{0}(\rho_{*})$ is nothing but the Hessian of ${\bm{\theta}}\mapsto\Psi({\bm{\theta}};\rho_{*})$ at ${\bm{\theta}}_{*}$.

If $\rho_{0}$ has a bounded density with respect to Lebesgue measure, then it cannot be that $\rho_{t}$ converges weakly to $\rho_{*}$ as $t\to\infty$.

Discussion and future directions

In this paper we developed a new approach to the analysis of two-layers neural networks. Using a propagation-of-chaos argument, we proved that –if the number of hidden units satisfies $N\gg D$– SGD dynamics is well approximated by the PDE in (7), while noisy SGD is well approximated by (12). Both of these asymptotic descriptions correspond to Wasserstein gradient flows for certain energy (or free energy) functionals. While empirical risk minimization is known to be insensitive to overparametrization [Bar98], the present work clarifies that the SGD behavior is also independent of the number of hidden units, as soon as this is large enough.

We illustrated our approach on several concrete examples, by proving convergence of SGD to a near-global optimum. This type of analysis provides a new mechanism for avoiding the perils of non-convexity. We do not prove that the finite-$N$ risk $R_{N}({\bm{\theta}})$ has a unique local minimum, or that all local minima are close to each other. Such claims have often been the target of earlier work, but might be too strong for the case of neural networks. We prove instead that the PDE (7) converges to a near global optimum, when initialized with a bounded density. This effectively gets rid of some exceptional stationary points of $R_{N}({\bm{\theta}})$, and merges multiple finite $N$ stationary points that result into similar distributions $\rho$.

In the case of noisy SGD (11), we prove that it converges generically to a near-global minimum of the regularized risk, in time independent of the number of hidden units.

We emphasize that while we focused here on the case of square loss, our approach should be generalizable to other loss functions as well, cf. SI.

The present work opens the way to several interesting research directions. We will mention two of them. $(i)$ The PDE (7) corresponds to gradient flow in the Wasserstein metric for the risk $R(\rho)$, see [AGS08]. Building on this remark, tools from optimal transportation theory can be used to prove convergence. $(ii)$ Multiple finite-$N$ local minima can correspond to the same minimizer $\rho_{*}$ of $R(\rho)$ in the limit $N\to\infty$. Ideas from glass theory [MP99] might be useful to investigate this structure.

Let us finally mention that, after a first version of this paper appeared as a preprint, several other groups obtained results that are closely related to Theorem 3 [RVE18, SS18, CB18].

Acknowledgements

This work was partially supported by grants NSF DMS-1613091, NSF CCF-1714305 and NSF IIS-1741162. S. M. was partially supported by Office of Technology Licensing Stanford Graduate Fellowship. P.-M. N. was partially supported by William R. Hewlett Stanford Graduate Fellowship. The authors would like to thank Jiajun Tong for helpful discussions concerning strong solutions for parabolic PDEs.

References

Supplementary information

We present here proofs and additional technical details for our mathematical results, as well as additional information concerning the numerical experiments.

Notations

We use lowercase bold for vectors (e.g. ${\bm{u}},{\bm{v}},\dots$), uppercase bold for matrices (e.g. $\bm{A},\bm{B},\dots$), and lowercase plain for scalar ($x,y,\dots$).

Given a measurable space $\Omega$, we denote by $\mathscrsfs{P}(\Omega)$ the set of probability measures on $\Omega$.

Given a measurable function $f$, and a measure $\mu$, we denote by $\langle f,\mu\rangle=\langle\mu,f\rangle=\int f\,{\rm d}\mu$ the corresponding integral.

$\|f\|_{\mbox{\tiny\rm Lip}}\equiv\sup_{x\neq y}|f({\bm{x}})-f({\bm{y}})|/\|{\bm{x}}-{\bm{y}}\|_{2}$ denotes the Lipshitz constant of a function $f$.

$d_{\mbox{\tiny\rm BL}}(\,\cdot\,,\,\cdot\,)$ is the bounded Lipschitz distance between probability measures

Here ${\mathcal{C}}(\mu,\nu)$ is the set of couplings of $\mu$ and $\nu$.

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

For $p=1$, the Kantorovich-Rubinstein duality gives

$K$ is a generic constant depending on $K_{0},K_{1},K_{2},K_{3}$, where $K_{i}$’s are constants which will be specified from the context.

General results: Statics

In this section, we discuss some properties of the population risk, $R_{N}({\bm{\theta}})$, and its continuum counterpart $R(\rho)$. For future reference, we copy the key definitions from the main text:

We show that minimizing the population risk $R_{N}({\bm{\theta}})$ yields similar results to minimizing its continuum counterpart $R(\rho)$:

We establish the condition for $\rho_{*}$ to be a minimizer:

First notice that, for any ${\bm{\theta}}=({\bm{\theta}}_{i})_{i\leq N}$, we have

Indeed, $R_{N}({\bm{\theta}})=R(\rho)$ for $\rho=(1/N)\sum_{i=1}^{N}\delta_{{\bm{\theta}}_{i}}$.

whence the claim (6.6) follows since ${\varepsilon}$ is arbitrary.

We next establish the minimum condition (6.7). Notice that since $V(\,\cdot\,)$ is continuous, and $U(\,\cdot\,,\,\cdot\,)$ is bounded below, it follows from Fatou’s lemma that, for any $\rho$, the function ${\bm{\theta}}\mapsto\Psi({\bm{\theta}};\rho)$ is lower semicontinous and takes values in $(-\infty,\infty]$. In particular the set $S_{0}(\rho)\equiv\arg\min_{{\bm{\theta}}}\Psi({\bm{\theta}};\rho)$ must be closed.

We first prove that any minimizer must satisfy (6.7). Let $\rho_{*}$ be a minimizer and define $\Psi_{*}=\inf_{{\bm{\theta}}}\Psi({\bm{\theta}};\rho_{*})$. By rearranging terms, for any probability measure $\rho$, we have

First we will assume $\Psi_{*}>-\infty$ (whence, by lower semicontinuity, $S_{0}(\rho_{*})$ must be a non-empty closed set). Let ${\bm{\theta}}_{1}\in S_{0}(\rho_{*})$, and assume by contradiction that there exist ${\bm{\theta}}_{0}\in{\rm supp}(\rho_{*})$, ${\bm{\theta}}_{0}\not\in S_{0}(\rho_{*})$. Let ${\sf B}({\bm{\theta}}_{0};{\varepsilon})$ be a ball of radius ${\varepsilon}$ around ${\bm{\theta}}_{0}$. By lower semicontinuity, we can find ${\varepsilon}_{0},\Delta>0$ such that $\inf_{{\bm{\theta}}\in{\sf B}({\bm{\theta}}_{0};{\varepsilon}_{0})}\Psi({\bm{\theta}};\rho_{*})=\Psi_{*}+\Delta>\Psi_{*}$. Further $t_{0}\equiv\rho_{*}({\sf B}({\bm{\theta}}_{0};{\varepsilon}_{0}))>0$ because ${\bm{\theta}}_{0}\in{\rm supp}(\rho_{*})$.

Let $\nu\equiv{\bm{1}}_{{\sf B}({\bm{\theta}}_{0};{\varepsilon}_{0})}\rho_{*}/t_{0}$ (i.e. $\nu$ is the conditional distribution given ${\bm{\theta}}\in{\sf B}({\bm{\theta}}_{0};{\varepsilon}_{0})$). Define, for $t\in[0,t_{0}]$, the probability measure

where the second inequality follows from the fact that $U$ is continuous and $\delta_{{\bm{\theta}}_{1}}$, $\nu$ have bounded support. By taking $t$ small enough, we get $R(\rho)<R(\rho_{*})$ hence reaching a contradiction.

By selecting $t=t_{M}=\min(t_{0},(M+\Psi_{0})/C_{0}(M))$ (which is positive for all $M$ large enough), we obtain $R(\rho_{M,t})-R(\rho_{*})<0$ for all $M$ large and hence reach a contradiction.

Setting $\mu=2[\Psi(\,\cdot\,;\rho_{*})-\Psi_{*}]$, and noticing that condition (6.7) implies $\langle\Psi(\,\cdot\,;\rho_{*})-\Psi_{*},\rho_{*}\rangle=0$, we get $R(\rho)\geq R(\rho_{*})+\langle U,(\rho-\rho_{*})^{\otimes 2}\rangle\geq R(\rho_{*})$.

2 Some additional results

We often find empirically that the optimal density $\rho_{*}$ is supported on a set of Lebesgue measure (sometimes on a finite set of points). The following consequence of the previous results partially explains these findings.

Assume ${\bm{\theta}}\mapsto V({\bm{\theta}})$ to be an analytic function and $({\bm{\theta}}_{1},{\bm{\theta}}_{2})\mapsto U({\bm{\theta}}_{1},{\bm{\theta}}_{2})$ to be analytic with respect to ${\bm{\theta}}_{1}$, uniformly in ${\bm{\theta}}_{2}$. Namely there exists a locally bounded function ${\bm{\theta}}\mapsto B({\bm{\theta}})$ such that $\|\nabla^{k}_{{\bm{\theta}}_{1}}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})\|_{2}\leq k!B({\bm{\theta}}_{1})^{k}$ for all $k$, ${\bm{\theta}}_{1}$, ${\bm{\theta}}_{2}$. If $\rho_{*}$ is a minimizer of $R(\rho)$, then one of the following holds

The support of $\rho_{*}$ has zero Lebesgue measure.

If $D=1$, then $(b)$ can be replaced by: $(b^{\prime})$ $\rho_{*}$ is a convex combination of countably many point masses with no accumulation point (finitely many if $\Psi(\theta;\rho_{*})\to\infty$ as $|\theta|\to\infty$).

Note that, under the stated conditions $f({\bm{\theta}})\equiv\int U({\bm{\theta}},{\bm{\theta}}^{\prime})\,\rho_{*}({\rm d}{\bm{\theta}}^{\prime})$ is analytic. Indeed, by a standard dominated convergence argument, we have that $\nabla^{k}f$ is given by the integral of $\int\nabla^{k}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})\,\rho_{*}({\rm d}{\bm{\theta}}_{2})$ for any $k\geq 0$. Further, by an application of the intermediate value theorem there exists $t_{{\bm{\theta}}_{1},{\bm{\theta}}_{2},{\bm{\delta}}}\in$ such that

which vanishes as $k\to\infty$ for uniformly over $\|{\bm{\delta}}\|_{2}\leq\delta_{0}$ for $\delta_{0}$ small enough.

General results: Dynamics

In this section we consider the SGD dynamics with step size $s_{k}={\varepsilon}\xi(k{\varepsilon})$, under the assumptions ${\sf A1},{\sf A2},{\sf A3}$ stated in the main text. For the readers convenience, we reproduce here the form of the limiting PDE

For background on this and similar PDEs (and the analogous ones at finite temperature, cf. Section 10), we refer to [MV00, CMV+03, CMV06, AGS08, CDF+11]. Our treatment will be mostly self-contained because of some differences between our setting and the one in these papers.

Recall assumptions A1, A2, A3 in the main text. By [Szn91, Theorem 1.1], assumptions A1 and A3 are sufficient for the existence and uniqueness of solution of PDE (7.1).

Assume conditions A1 and A3 hold. Let $(\rho_{t})_{t\geq 0}$ be the solution of the PDE (7.1). Let $(\overline{\bm{\theta}}_{i}^{t})_{t\geq 0}$ be the solution of nonlinear dynamics (7.4). Then $t\mapsto\overline{\bm{\theta}}^{t}_{i}$ is $K_{1}K_{3}$-Lipschitz continuous, and $t\mapsto\rho_{t}$ is $K_{1}K_{3}$-Lipschitz continuous in $W_{2}$ Wasserstein distance, with $K_{1}$ and $K_{3}$ as per conditions A1 and A3. In particular, $t\mapsto\rho_{t}$ is continuous in the topology of weak convergence.

Since $\xi$ and $\nabla\Psi$ are $K_{1}$ and $K_{3}$ bounded respectively, $t\mapsto\overline{\bm{\theta}}^{t}_{i}$ is $K_{1}K_{3}$-Lipschitz continuous. Further, Eq. (5.2) implies that $t\mapsto\rho_{t}$ is Lipschitz continuous in $W_{2}$ Wasserstein distance, namely

The proof follows a ‘propagation of chaos’ argument [Szn91]. Throughout this proof, we will use $K$ to denote generic constant depending on the constants $K_{1},K_{2},K_{3}$ in conditions A1, A2, A3.

It is convenient to introduce the notations ${\bm{z}}_{k}=({\bm{x}}_{k},y_{k})$ to denote the $k$-th example and define

Note that the assumption of bounded Lipschitz $\nabla V$, $\nabla_{1}U$ (here and below $\nabla_{1}U({\bm{\theta}}_{1},{\bm{\theta}}_{2})$ denotes the gradient of $U$ with respect to its first argument) implies $\|{\bm{G}}({\bm{\theta}};\rho)\|_{2}\leq K$ and $\|{\bm{G}}({\bm{\theta}}_{1};\rho)-{\bm{G}}({\bm{\theta}}_{2};\rho)\|_{2}\leq K\|{\bm{\theta}}_{1}-{\bm{\theta}}_{2}\|_{2}$. Further

With these notations, we can rewrite the SGD dynamics in the main text as

Recall $({\bm{\theta}}^{0}_{i})_{i\leq N}\sim\rho_{0}$ independently.

We next state and prove the key estimate controlling the difference between the original dynamics and the nonlinear dynamics.

Under the assumptions of Theorem 3, there exists a constant $K$ depending uniquely on $K_{1},K_{2},K_{3}$ in conditions A1, A2, and A3, such that for any $T\geq 0$, we have

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

We next consider the three terms above. Using the Lipschitz continuity of ${\bm{G}}({\bm{\theta}};\rho)$ with respect to ${\bm{\theta}}$ and $\rho$ (see Eq. (7.10)), and due to condition A1 and Lemma 7.1 (implying that $\xi$, $\overline{\bm{\theta}}^{t}_{i}$, and $\rho_{s}$ are Lipschitz continuous), we get

Bounding the second term yields (by using the Lipschitz continuity of ${\bm{G}}$ with respect to its first argument):

where $\hat{\rho}^{(N)}_{k}\equiv(1/N)\sum_{i\leq N}\delta_{{\bm{\theta}}^{k}_{i}}$. Hence

and taking union bound over $i\leq N$, we get

For the term $E_{3,0}^{i}(t)$, we use the Lipschitz continuity property (7.10), whence

Since for any fixed $k$, $(\overline{\bm{\theta}}_{j}^{k{\varepsilon}})_{j\leq N,j\neq i}$ are i.i.d. and independent of ${\bm{\theta}}_{i}^{k}$, and $\nabla_{1}U$ is bounded, we get by another application of Azuma-Hoeffding inequality, cf. Lemma A.1,

Conditional on the good events in Eq. (7.22) and (7.25), Eq. (7.20) thus yields

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

Using the bounds (7.16), (7.17), (7.26) in Eq. (7.15), we get

Using the bound (7.27), the claim follows. ∎

Under the assumptions of Theorem 3, we have

Let ${\bm{\theta}}=({\bm{\theta}}_{1},\dots,{\bm{\theta}}_{i},\dots,{\bm{\theta}}_{n})$ and ${\bm{\theta}}^{\prime}=({\bm{\theta}}_{1},\dots,{\bm{\theta}}_{i}^{\prime},\dots,{\bm{\theta}}_{n})$ be two configurations that differ only in position $i$. Then

Under the assumptions of Theorem 3, we have,

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

By Eq. (7.32) and by Azuma-Höeffding inequality and union bound, we get

with probability at least $1-e^{-z^{2}}$. The claim follows since

The proof of the theorem follows from a straightforward application of Lemma 7.2, 7.3, 7.4. The proof for any bounded Lipschitz function $f$ follows the same argument as Lemma 7.3, 7.4. As a result, for any sequence $(N,{\varepsilon}={\varepsilon}_{N})$ such that $N\to\infty$ and ${\varepsilon}_{N}\to 0$ with $N/\log(N/{\varepsilon}_{N})\to\infty$ and ${\varepsilon}_{N}\log(N/{\varepsilon}_{N})\to 0$, we have $\hat{\rho}_{\lfloor k/{\varepsilon}\rfloor}^{(N)}$ converges weakly to $\rho_{t}$ almost surely immediately.

2 Proof of Theorem 3: Generalization to β<∞𝛽\beta<\infty

Here we generalize the proof given in the previous section to noisy SGD at finite temperature $\beta<\infty$. Since the proof follows the same scheme as in the noiseless case, we will limit ourselves to describing the differences.

Throughout this section we assume that conditions ${\sf A1}$, ${\sf A2}$, ${\sf A3}$ hold. We also let

for some $\lambda\leq 1$. Further we assume $\rho_{0}$ is $K_{0}^{2}$-sub-Gaussian. Finally, we assume $1\leq\beta<\infty$.

For the reader’s convenience, we reproduce here the form of the limiting PDE

which again should be interpreted in weak sense.

Recall conditionss A1, A2, A3 in the main text. By a modified argument of [Szn91, Theorem 1.1], conditions A1 and A3 are sufficient for the existence and uniqueness of solution of PDE (7.37) in weak sense. Section 10 provides further information of this PDE, including a proof of existence and uniqueness.

As in the noiseless case, there is an equivalent formulation of this PDE as a fixed point distribution for the following nonlinear dynamics, which is an integration form of a stochastic differential equation,

where $\{\bm{W}_{i}(s)\}_{s\geq 0}$ for $i\leq N$ are independent $D$-dimensional Brownian motions, and ${\bm{G}}({\bm{\theta}};\rho)\equiv-\nabla\Psi_{\lambda}({\bm{\theta}};\rho)$. The assumptions on $U$, $V$, $\lambda$, and $\xi$ ensures that this nonlinear dynamics has a unique continuous solution.

It is convenient to collect some standard estimates about the solution of the stochastic differential equation (7.38).

Assume $\rho_{0}$ is $K_{0}^{2}$-sub-Gaussian, $\xi(s)$ and ${\bm{G}}({\mathbf{0}};\rho_{s})$ are $K_{0}$-bounded, ${\bm{G}}({\bm{\theta}};\rho_{s})$ is $K_{0}$-Lipschitz in ${\bm{\theta}}$, and $\beta\geq 1$. Let $(\overline{\bm{\theta}}_{i}^{t})_{t\geq 0}$ for $i\leq N$ be the solution of (7.38) with independent initialization $({\bm{\theta}}_{i}^{0})_{i\leq N}\sim\rho_{0}$. Let $(\rho_{t})_{t\geq 0}$ be the solution of PDE (7.37). Then there exists a constant $K$ depending uniquely on $K_{0}$, such that

Part (a). First, note that for any $D$-dimensional $K_{0}^{2}$-sub-Gaussian random vector $\bm{X}$, we have

Note that $({\bm{\theta}}_{i}^{0})_{i\leq N}\sim\rho_{0}$ independently, and $\rho_{0}$ is $K_{0}^{2}$-sub-Gaussian. Therefore

Taking $\tau=1/(2K_{0}^{2})$ and $u=2K_{0}(\sqrt{D+\log N}+z)$, we get

Then we define $\bm{W}_{\xi,i}(t)\equiv\int_{0}^{t}\sqrt{2\xi(s)}\,{\rm d}\bm{W}_{i}(s)$. We have ${\rm Var}(W_{\xi,i}^{j}(t))=\int_{0}^{t}2\xi(s){\rm d}s\leq 2K_{0}t$ for $j\leq D$. Note $\exp\{\tau\|\bm{W}_{\xi,i}(t)\|_{2}^{2}\}$ is a submartingale, due to Doob’s martingale inequality, we have

Taking $\tau=1/(4K_{0}T)$ and $u=4\sqrt{K_{0}T}(\sqrt{D+\log N}+z)$, we get

By noting that $\xi(s)$, ${\bm{G}}({\mathbf{0}};\rho_{s})$ are $K_{0}$-bounded, and ${\bm{G}}({\bm{\theta}};\rho_{s})$ is $K_{0}$-Lipschitz in ${\bm{\theta}}$, according to Eq. (7.38), there exists some constant $K$ depending on $K_{0}$, such that

where $\Delta_{i}(t)\equiv\sup_{s\leq t}\|\overline{\bm{\theta}}_{i}^{s}\|_{2}$, $W\equiv\max_{i\leq N}\sup_{t\leq T}\|\bm{W}_{\xi,i}(t)\|_{2}$, and $\Theta\equiv\max_{i\leq N}\|{\bm{\theta}}_{i}^{0}\|_{2}$. Due to Gronwall’s inequality, we have

The high probability bound (7.42) holds by noting the high probability bound for $\Theta$ and $W$ in Eq. (7.46) and (7.47).

Part (b). Define $\Delta_{i}(h;k,{\varepsilon})=\sup_{0\leq u\leq h}\|\overline{\bm{\theta}}_{i}^{k{\varepsilon}+u}-\overline{\bm{\theta}}_{i}^{k{\varepsilon}}\|_{2}$. By noting that $\xi(s)$, ${\bm{G}}({\mathbf{0}};\rho_{s})$ are $K_{0}$-bounded, and ${\bm{G}}({\bm{\theta}};\rho_{s})$ is $K_{0}$-Lipschitz in ${\bm{\theta}}$, according to Eq. (7.38), we have

where $\bm{W}_{\xi,i,k}(u)\equiv\int_{k{\varepsilon}}^{k{\varepsilon}+u}\sqrt{2\xi(s)}\,{\rm d}\bm{W}_{i}(s)$. Similar to the bound Eq. (7.47), we have

Plugging the bound Eq. (7.42) and Eq. (7.49) into Eq. (7.48), we have

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

Part (c). Equation (7.44) holds directly by noting that

As in the noiseless case, the key step consists in bounding the difference between the nonlinear dynamics and the SGD dynamics.

Under the assumptions of Theorem 3, there exists a constant $K$ depending uniquely on $K_{0},K_{1},K_{2},K_{3}$, such that for any $T\geq 0$, we have

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

Terms $E_{2}^{i}(t)$, $E_{3}^{i}(t)$ can be bounded the same as in Lemma 7.2, i.e., Eq. (7.17) and (7.26), by noting that the replacement of $\Psi$ by $\Psi_{\lambda}$ does not affect these estimates.

To bound $E_{4}^{i}(t)$, notice that \bm{W}_{\xi,i}\equiv\int_{0}^{T}\big{(}\sqrt{2\xi(s)}-\sqrt{2\xi([s])}\big{)}\,{\rm d}\bm{W}_{i}(s) is a Gaussian random vector, $\bm{W}_{\xi,i}\sim{\sf N}({\mathbf{0}},\tau^{2}{\bm{I}}_{D})$, where, using the Lipschitz continuity of $\xi$,

and therefore by applying Doob’s inequality to the submartingale $t\mapsto E_{4}^{i}(t)$, we get

We need to modify the proof of Lemma 7.2 to bound terms $E_{1}^{i}(t)$.

To bound the first term $E_{1,A}^{i}(t)$, due to the Lipschitz property of ${\bm{G}}({\bm{\theta}};\rho)$ and the boundedness of ${\bm{G}}({\mathbf{0}};\rho)$, with probability at least $1-e^{-z^{2}}$, we have for all $i\leq N$ and $t\leq T$,

Here the last inequality is due to Eq. (7.42) in Lemma 7.5.

To bound the second term $E_{1,B}^{i}(t)$, using the fact that $\nabla_{1}U$ is bounded Lipschitz, we have for all $i\leq N$ and $t\leq T$,

Here the last inequality is due to Eq. (7.44) in Lemma 7.5.

To bound the third term $E_{1,C}^{i}(t)$, with probability at least $1-e^{-z^{2}}$, we have for all $i\leq N$ and $t\leq T$,

Here the last inequality is due to Eq. (7.43) in Lemma 7.5.

As a result, combining Eq. (7.17), (7.26), (7.27), (7.51), (7.52), (7.54), (7.55), and (7.56), defining

Applying Gronwall’s inequality gives the desired result.

The generalization of Theorem 3 to $\beta<\infty$ follows from this lemma exactly as in the previous section.

3 Proof of Proposition 2: Monotonicity of the risk

By Lemma 7.1, $t\mapsto\rho_{t}$ is Lipschitz continuous in Wasserstein distance $W_{2}(\rho_{t_{1}},\rho_{t_{2}})\leq K|t_{1}-t_{2}|$. Hence, we get

where in the second step we used Eq. (7.3). This immediately implies that $R(\rho_{t})$ is non-increasing in $t$.

Let $\rho$ be a fixed point of Eq. (7.1). Since $\partial_{t}R(\rho_{t})|_{\rho_{0}=\rho}=0$, the above formula implies

and therefore $\rho$ is supported in the set of ${\bm{\theta}}$’s such that $\nabla\Psi({\bm{\theta}};\rho)={\mathbf{0}}$.

Vice versa, if this is the case, setting $\rho_{0}=\rho$, Eq. (7.3) implies $\partial_{t}\langle\varphi,\rho_{t}\rangle=0$, then $\rho_{t}\equiv\rho_{0}$ is a fixed point.

4 A general continuity result

It is useful to notice that the solution $(\rho_{t})_{t\geq 0}$ of the PDE (7.1) is continuous with respect to changes in $V(\,\cdot\,)$, $U(\,\cdot\,,\,\cdot\,)$. Namely, we consider the following two PDEs:

The proof adapts the argument used to establish uniqueness in [Szn91]. Without loss of generality, we fix $\xi(t)\equiv 1/2$. We further denote by $K$ generic constants depending on $K_{1}$, $K_{3}$.

The assumption of bounded Lipschitz $\nabla V$ and $\nabla U$ implies that $\nabla\Psi({\bm{\theta}};\rho)$ is $K$-bounded Lipschitz with respect to argument $({\bm{\theta}},\rho)$, that is,

Using bound (7.70), the first term $E_{1}(t)$ is simply bounded by

To bound the second term $E_{2}(t)$, we have

with the definition of ${\varepsilon}_{0}$ given by Equation (7.69).

Combining Equation (7.74), (7.75), and (7.76), we have

Applying Equation (7.73), the result follows. ∎

5 Some properties of the solution of the PDE (7.1)

In this section we prove four lemmas on the properties of the solution of the PDE (7.1), under conditions A1 and A3. All of these facts are quite standard, but we provide complete proofs for them for reader’s convenience.

We will use several times the following notations. Let $\rho_{t}$ be a solution of the PDE (7.1) with initialization $\rho_{0}$. Let $({\bm{\theta}}^{t})_{t\geq 0}$ be the solution of the ordinary differential equation (ODE)

With these notations, $\rho_{t}$ is the push forward of $\rho_{0}$ under ${\bm{\varphi}}^{t}$: $\rho_{t}={\bm{\varphi}}_{*}^{t}\rho_{0}$. In other words, for any Borel set $B$, $\rho_{t}({\bm{\varphi}}^{t}(B))=\rho_{0}(B)$.

The lemma holds immediately by noting that $\rho_{t}(\Omega)\geq\rho_{t}({\bm{\varphi}}^{t}(\Omega))=\rho_{0}(\Omega)$. ∎

Assume conditions A1, A3 hold. Further assume there exists a constant $K<\infty$ such that

for any ${\bm{\theta}}\in(0,\infty)^{D}$ and $\rho\in{\mathcal{P}}([0,\infty]^{D})$. Let $(\rho_{t})_{t\geq 0}$ be the solution of the PDE (7.1) with initial condition $\rho_{0}$ with $\rho_{0}((0,\infty)^{D})=1$. Then for any $t<\infty$, $\rho_{t}((0,\infty)^{D})=1$.

According to Eqs. (7.80) and (7.79), we have for $i\in[d]$,

Then according to (7.81), we have ${\bm{\varphi}}^{t}(\Omega_{k}(0))\subseteq\Omega_{k}(t)$. Note $\Omega_{k}(t)$ is increasing in $k$ for fixed $t$, and $\cup_{k}\Omega_{k}(t)=\cup_{k}\Omega_{k}(0)=(0,\infty)^{D}$. Hence,

Let $(\rho_{t})_{t\geq 0}$ be a continuous curve in a compact metric space $(\Omega,d)$. Denoting

to be the set of all limiting points of $(\rho_{t})_{t\geq 0}$. Then ${\mathcal{S}}_{*}$ is a connected compact set.

First, it is easy to see that ${\mathcal{S}}_{*}$ should be closed. Note that $\Omega$ is a compact space, then ${\mathcal{S}}_{*}$ should be a compact set. If ${\mathcal{S}}_{*}=\{\rho_{*}\}$ is a singleton, this lemma holds automatically. Therefore, we would like to consider the case when ${\mathcal{S}}_{*}$ is not a singleton.

For any $\rho_{1},\rho_{2}\in{\mathcal{S}}_{*}$, and $d(\rho_{1},\rho_{2})>0$. We would like to show $\rho_{1}$ and $\rho_{2}$ are connected in ${\mathcal{S}}_{*}$.

We use proof by contradiction. Now suppose $\rho_{1}$ and $\rho_{2}$ are not connected. Define ${\mathcal{A}}\subseteq{\mathcal{S}}_{*}$ to be the maximal connected subset of ${\mathcal{S}}_{*}$ containing $\rho_{1}$. It is easy to see that ${\mathcal{A}}$ is compact. It is also easy to see that its complement ${\mathcal{B}}\equiv{\mathcal{S}}_{*}\setminus{\mathcal{A}}$ is also a compact set, and $\rho_{2}\in{\mathcal{B}}$. As a result, we have ${\mathcal{A}}\cup{\mathcal{B}}={\mathcal{S}}_{*}$, ${\mathcal{A}}\cap{\mathcal{B}}=\emptyset$, and $\rho_{1}\in{\mathcal{A}}$, $\rho_{2}\in{\mathcal{B}}$.

Note that $\Omega$ is a metric space, so it satisfies T4 separation axiom. Since ${\mathcal{A}}$ and ${\mathcal{B}}$ are closed sets and ${\mathcal{A}}\cap{\mathcal{B}}=\emptyset$, there exists an open set ${\mathcal{O}}$, such that ${\mathcal{A}}\subseteq{\mathcal{O}}$, ${\mathcal{O}}\cap{\mathcal{B}}=\emptyset$. Hence, $\partial{\mathcal{O}}\subseteq{\mathcal{S}}_{*}^{c}$.

Note that $\rho_{1}$ and $\rho_{2}$ are limiting points of $(\rho_{t})_{t\geq 0}$ which is a continuous curve in $\Omega$. Therefore, it must cross the boundary $\partial{\mathcal{O}}$ infinite times. That is, there is a sequence $(t_{k})_{k\geq 1}$ of time with $\lim_{k\to\infty}t_{k}=\infty$, such that $\rho_{t_{k}}\in\partial{\mathcal{O}}$. But since $\partial{\mathcal{O}}$ is compact, there exists a limiting point $\rho_{*}\in\partial{\mathcal{O}}$, so that a subsequence of sequence $\rho_{t_{k}}$ converges to $\rho_{*}$. Therefore, $\rho_{*}$ should be a limiting point of $(\rho_{t})_{t\geq 0}$. But this contradict with $\partial{\mathcal{O}}\subseteq{\mathcal{S}}_{*}^{c}$. ∎

Under the assumptions of A1 and A3, further assume that $U,V$ are twice continuous differentiable, and that $\rho_{0}$ has density with respect to the Lebesgue measure, bounded by $M_{0}$. Then $\rho_{t}$ also has a density, bounded by $M_{t}=K\,M_{0}\exp\{KDt\}$ (where $K$ depends on the constants in the assumptions).

Let $\bm{J}({\bm{\theta}};t)$ for the Jacobian of ${\bm{\varphi}}^{t}(\,\cdot\,)$ at ${\bm{\theta}}^{0}={\bm{\theta}}$. Then Eq. (7.79) implies that $\bm{J}({\bm{\theta}};t)$ satisfies

with initial condition $\bm{J}({\bm{\theta}};0)={\bm{I}}_{D}$. This implies

Therefore, using the fact that $\|\nabla^{2}\Psi({\bm{\theta}};\rho_{t})\|_{\mbox{\tiny\rm op}}$ is $K$-bounded, we obtain \lambda_{\min}\big{(}\bm{J}({\bm{\theta}};t)\big{)}\geq\exp(-Kt). Finally, since ${\bm{\varphi}}^{t}$ is a diffeomorphism, we have

6 Proof of Theorems 6: Stability conditions

where $\bm{H}_{0}\equiv\bm{H}_{0}(\delta_{{\bm{\theta}}_{*}})=\nabla^{2}V({\bm{\theta}}_{*})+\nabla^{2}_{1,1}U({\bm{\theta}}_{*},{\bm{\theta}}_{*})$. Notice that