1 Introduction↩︎

The study of particle systems under mean-field interaction is a classical topic in probability theory [1]. It involves multidimensional diffusions that interact through their empirical distributions of the type \[\label{eq:mckeanvlasov} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_i(t) = b\left(X_i(t), \hat{\mu}^{(N)}(t) \right) \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_i(t) , \quad i \in \bracket*{\lbrack}{\rbrack}{N} , \quad t\in\mathbb{R}_+,\tag{1}\] where \(N\in\mathbb{N}\), \(X_i(t) \in \mathbb{R}^{d}\) for all \(i\in\bracket*{\lbrack}{\rbrack}{N}\) and for some \(d\in\mathbb{N}\), and \(\hat{\mu}^{(N)}(t) \mathrel{\vcenter{:}}= \frac{1}{N} \sum_{i=1}^N \delta_{X_i(t)}\), is the empirical distribution of the vector \(\left(X_i(t)\right)_{i \in [N]}\) at time \(t\in \mathbb{R}_+\), and \(\left(B_i \right)_{i \in [N]}\) is a vector of i.i.d. standard \(d\)-dimensional Brownian motions. Prominent examples of such particle systems include the diffusion given by the SDE \[\label{eq:granmediapart} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_i(t)= - \nabla V\left(X_i(t) \right)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t - \frac{1}{N} \sum_{j=1}^N \nabla W\left( X_i(t) - X_j(t) \right) \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_i(t) ,\quad t\in\mathbb{R}_+,\tag{2}\] for \(i\in\bracket*{\lbrack}{\rbrack}{N}\), where \(V\) and \(W\) are differentiable convex functions on \(\mathbb{R}^{d}\). However, any drift that is symmetric in the coordinates (“mean-field interactions”) can be represented as 1 for some suitable function \(b\). Often, the SDE 1 includes a reflection term to constrain the coordinate process to a subset of the Euclidean space [2]. The study of such systems originated from the probabilistic study of the Boltzmann and Vlasov equations due to Kac [3], McKean [4], Dobrushin [5], Tanaka [6] and many others. For modern surveys, see Sznitman [7], Villani [8], Chaintron and Diez [9] and Jabin [10].

Under suitable assumptions, as the number of particles go to infinity, it is known that the process of empirical distributions of the particle system converges to the solutions of families of well-known PDEs. For example, for the system 2 , the random process \(\hat{\mu}^{(N)}\) converges weakly to the solution of granular media equation [11], as \(N\rightarrow \infty\). The convergence is often obtained via propagation of chaos where, in the large particle limit, a finite collection of randomly chosen particles evolves independently and identically. Furthermore, a randomly chosen particle in the large particle limit is distributed according to the McKean-Vlasov SDE [1]: \(\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X(t) = b\left( X(t), \mu(t) \right)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B(t)\), \(t\in\mathbb{R}_+\), where \(\mu(t)\) is the law of \(X(t)\).

In this work we study an analogous evolution of symmetric matrices where the coordinates interact via a suitably symmetric function. As an example, consider the function \(R_n\) defined on \(\mathcal{M}_n^{0}\), the set of all \(n\times n\) symmetric matrices with entries in \([0, 1]\), given by \[\label{eqn:examplern} R_n(A)\mathrel{\vcenter{:}}=\frac{1}{n}\mathbb{E}\nrm*{2}{Y-n^{-1}AX}^2.\tag{3}\] where \((X, Y)\in \mathbb{R}^n\times \mathbb{R}^n\) is a random vector. Minimizing \(R_n\) is the classical least squares regression problem. However, notice that even in this simple setup, this problem is non-trivial because of the restriction that entries of \(A\) are in \([0, 1]\). If we assume that \((X, Y)\) is exchangeable, that is, \((X, Y)\stackrel{d}{=}(X^{\sigma}, Y^{\sigma})\) for any permutation \(\sigma\) of \([n]\mathrel{\vcenter{:}}= \Set{1,2,\ldots,n}\), then the function \(R_n\) satisfies a permutation invariance property. That is, its value does not change if we permute the rows and columns of the matrix \(A\) by the same permutation over \(\bracket*{\lbrack}{\rbrack}{n}\). Another rich source of such permutation invariant functions comes from the functions on unlabelled weighted graphs, for example, homomorphism density functions. Optimization of homomorphism density functions is a challenging problem that is being actively investigated [12], [13]. Projected stochastic gradient methods are empirically studied for optimizing such problems [14]. We refer the reader to Section 5 for more details on such examples. Consider the following diffusion on symmetric \(n\times n\) matrices \[\label{eq:exampleR} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{n}(t) = -n^2\nabla R_n\bracket*{(}{)}{X_{n}(t)}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \beta\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{n}(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n}(t) ,\qquad t\in\mathbb{R}_+,\tag{4}\] where \(B_{n}\) is a system of \(n\times n\) symmetric matrix-valued process of coordinatewise independent Brownian motions and \(L_{n}\) is the coordinatewise bounded variation local time process that constrains each coordinate process to stay in the interval \(\bracket*{\lbrack}{\rbrack}{0,1}\) (see Section 2.3 for details). One may ask what is an appropriate notion of limit of such a process as \(n\rightarrow \infty\)? Does 4 exhibit propagation of chaos? Note that the function \(R_n\) in 4 is not covered by the classical McKean-Vlasov theory since \(R_n(A)\) is not symmetric in the \(n^2\) (up to symmetry) many entries of a matrix \(A\). Therefore, \(R_n\) cannot be expressed as a function of the empirical distribution of the entries of the argument matrix. The same is true for any arbitrary differentiable function over \(n \times n\) symmetric matrices that is invariant under permuting the rows and the columns using the same permutation. Spectral functions, for example, satisfy such an invariance, as do functions on edge-weighted graphs (represented by their adjacency matrices) that are invariant under vertex relabeling. This particular class of symmetry is captured, not by empirical measures but by graphons. In other words, such functions can be thought of as functions on the space of graphons instead of measures.

Analogous to the classical McKean-Vlasov theory, we show in this paper that, under suitable assumptions, 4 exhibits a propagation of chaos. Furthermore, in \(n\to \infty\) limit, the coordinates of \(X_n(t)\) become conditionally independent, and the evolution of a randomly chosen coordinate can be described by a novel graphon-valued McKean-Vlasov equation. The existence and uniqueness of such a process are established in Proposition 8. Proposition 9 shows that the process \(X_n(t)\) converges to a deterministic curve on the space of graphons, \({\widehat\mathcal{W}}\) (see Section 2). We also refer the reader to see Section 5.4 for details of our example.

Recently, various authors [15]–[18] have investigated McKean-Vlasov limits for interacting particle systems on dense graphs. This is akin to equation 2 where particles interact only if they are neighbors in some underlying graph. In these works, the McKean-Vlasov system describes the evolution of random particles from an infinite ensemble where the underlying interaction is determined by a graph or graphon. Extensions to the sparse regime can be found in  [19]–[23]. We note that our McKean-Vlasov limit describes the evolution of the graphon itself, and not the distribution of any particle system. We borrow the name McKean-Vlasov to stress that each edge-weight evolves by an ensemble effect of all the other edge weights, but that ensemble is a graphon and not the empirical distribution of any particle system as done in the papers cited above.

Notice that 4 arises as the limit of the projected stochastic gradient descent algorithm, which is used in practice to optimize \(R_n\). As mentioned above, we establish that the curves described by 4 converge to a deterministic curve on the space of graphons. In the zero-noise limit, the (deterministic) limiting curve on the space of graphons is a gradient flow and hence converges to the minimizer exponentially fast. Thus, the evolution 4 gives a way to numerically approximate the minimizer. More generally, the limiting curve converges to stationary points and thus 4 provides an algorithm to numerically approximate these stationary points that may be useful in obtaining reasonable guesses regarding the structure of the minimizers in such problems. We describe the projected gradient descent and projected stochastic gradient descent algorithms in more detail in the following paragraphs.

Projected Gradient Descent (GD) based algorithms are the workhorse in optimizing such functions [24]–[26]. However, in most cases, computing gradients can be computationally intensive. In practice, stochastic approximation algorithms based on projected Stochastic Gradient Descent (SGD) are instead used to minimize such functions since they are often faster to simulate [27], [28]. The details of this common Markov chain are described later in the section, and the reader can refer to the monographs [29]–[33] for a detailed overview. Roughly, if the current state is a symmetric matrix \(A\), one jumps to a new state by taking a small step along the negative Euclidean gradient \(-\nabla R_n(A)\), and potentially adding independent, centered, and variance-bounded noise to each matrix entry (up to symmetry). Each matrix entry is then projected onto the interval \(\bracket*{\lbrack}{\rbrack}{0,1}\) to satisfy the entrywise constraint.

Gradient descent (GD), with small step sizes, approximates the Euclidean gradient flow obtained as a solution to Cauchy’s problem \[\dot{A}_{i,j}(t) = -\nabla_{i,j}R_n(A(t)), \qquad (i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2}, \qquad t\in\mathbb{R}_+,\] in the interior of \(\mathcal{M}_n^{0}\). Here \(\mathbb{R}_+\) denotes the set of non-negative real numbers, which is used to index time, \(\nabla_{i,j}\) refers to the partial derivative with respect to the \((i,j)\)-th matrix entry. It is therefore natural to understand a suitable scaling limit of SGD on the space of such matrices.

A previous work [34] showed that under suitable assumptions on \(\bracket*{(}{)}{R_n}_{n \in \mathbb{N}}\), the implicit Euler update scheme approximates a gradient flow curve, in an appropriate sense, over the space of graphons, \({\widehat\mathcal{W}}\), when the step size is taken to zero and \(n\) grows to infinity. The reader is referred to [35]–[37] and Section 2.1 for the required exposition on graphons. In this work, we ask a similar question for SGD-based algorithms. We show that under an appropriate “small noise” assumption and a consistency and other suitable assumptions on the functions \(\bracket*{(}{)}{R_n}_{n \in \mathbb{N}}\), the SGD iterations converge appropriately to a limiting deterministic curve that is a gradient flow on the space of graphons. Moreover, when an extra Gaussian noise is added to each SGD iterate, the noisy SGD iterations also converge to a deterministic curve on graphons which admits a McKean-Vlasov description. Similar McKean-Vlasov system has been studied in [38], however, the focus of [38] is to study a particular Markov chain on large graphs, namely a version of the Metropolis Markov chain. These Markov chains are designed to mimic the gradient flow in the limit.

Very roughly, \(\mathcal{W}\), the set of bounded symmetric measurable functions on \([0, 1]^2\) or kernels, is our limiting space for symmetric matrices. The set of graphons, \({\widehat\mathcal{W}}\), is obtained as a quotient of \(\mathcal{W}\) where we identify two kernels to be the same if one can be obtained from the other by using the same measure-preserving transformation on its “rows” and “columns” (see Section 2.1). Thus, a function \(R\colon{\widehat\mathcal{W}}\to\mathbb{R}\) over graphons naturally extends to a function over the set of kernels \(\mathcal{W}\). For any \(n\in\mathbb{N}\), the set of symmetric matrices \(\mathcal{M}_n\), over which algorithms like GD and SGD operate on, can be naturally identified with a subset, finite dimensional kernels, \(\mathcal{W}_n\subset \mathcal{W}\) of the kernels (see Section 2.1 for details). This identification/embedding will be denoted by \(K\) (as in kernel) and its inverse will be denoted by \(M_n\) (as in matrix). Using \(K\), the restriction of the function \(R\) to \(\mathcal{W}_n\) can be viewed as a function \(R_n\) on \(\mathcal{M}_n\).

Define the projection operator \(P\colon\mathbb{R}\to\bracket*{\lbrack}{\rbrack}{-1,1}\) as \[P(x) \mathrel{\vcenter{:}}= \begin{cases} -1 & \text{if } x\in(-\infty,-1),\\ x & \text{if } x\in\bracket*{\lbrack}{\rbrack}{-1,1},\\ 1 & \text{if } x\in(1,\infty). \end{cases}\] The operator \(P\) can be used coordinatewise on matrices and kernels. For every \(n\in\mathbb{N}\), let \({\boldsymbol{\tau}}_n \mathrel{\vcenter{:}}= \bracket*{(}{)}{\tau_{n,k}}_{k\in\mathbb{Z}_+}\), be a sequence of positive step sizes (also known as the learning rate). Here \(\mathbb{Z}_+\) denotes the set of all non-negative integers. Given the step size sequence \({\boldsymbol{\tau}}_n\), we can define a monotonically increasing sequence of times \(\bracket*{(}{)}{t_{n,k}}_{k\in\mathbb{Z}_+}\), defined as a cumulative sum of \({\boldsymbol{\tau}}_n\), i.e., \(t_{n,0} = 0\) and \(t_{n,k}\mathrel{\vcenter{:}}= \sum_{j=0}^{k-1}\tau_{n,j}\) for any \(k\in\mathbb{N}\). We assume \({\boldsymbol{\tau}}_n\) to have a divergent sum so to cover the whole non-negative real line \(\mathbb{R}_+\), i.e., to satisfy \(\lim_{k\to\infty}t_{n,k} = \infty\). We define the norm of the step size sequence \({\boldsymbol{\tau}}_n\) as \(\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n} \mathrel{\vcenter{:}}= \sup_{k\in\mathbb{Z}_+}\tau_{n,k}\), which is assumed to be finite. We now describe our first iterative scheme.

There is a natural notion of gradient of functions defined on \({\widehat\mathcal{W}}\) that we call Fréchet-like derivative (see Definition 6), and is related to the Euclidean gradients in finite dimensions by a scaling of \(n^2\). Suppose \(R\) is such a function whose Fréchet-like derivative evaluation map is denoted by \(\phi\). If \(R_n\) is obtained from \(R\) by restricting \(R\) to \(\mathcal{M}_n\) and the function \(R_n\) is differentiable up to the boundary of \(\mathcal{M}_n\) for every \(n\in\mathbb{N}\), then it is shown in [34] that \[\begin{align} n^2\nabla R_n = M_n \circ \phi \circ K.\label{eq:scaling95gradient} \end{align}\tag{5}\] Simply put, \(n^2\) times the Euclidean gradient of \(R_n\) at a matrix argument \(A\) can be identified as the Fréchet-like derivative \(\phi\) of \(R\) at the kernel argument \(K(A)\). The time in the Euclidean gradient in Definition 1 is therefore scaled by \(n^2\) following the relation 5 . The ?? algorithm is essentially the explicit Euler iteration scheme up to the projection.

We now define the stochastic optimization setup for \(R_n\). In order to do so, we first fix some notations and make some assumptions on \(R\) and \(R_n\). Let \(\bracket*{(}{)}{\xi_{k+1}}_{k\in\mathbb{Z}_+}\) be an i.i.d. sequence of random variables with some distribution \(\mathcal{D}\) over some arbitrary measurable space \((\Omega,\mathcal{A})\). Let \(g\colon \mathcal{W}\times \Omega \to L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) where \(L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) is the set of all bounded measurable functions \(\phi:[0, 1]^2\to \mathbb{R}\) such that \(\phi(x, y)=\phi(y, x)\). To emphasize that \(\phi\) is symmetric, we denote the domain by \([0, 1]^{(2)}\) which denotes the set \(\{(x, y)\in [0, 1]^2: x\leq y\}\). Define \(g_n\) on \(\mathcal{M}_n \times \Omega\) as \(g_n(A;\xi) = g(K(A);\xi)\) for every \(n\in\mathbb{N}\) and \(A\in\mathcal{M}_n\), and assume that \[\begin{align} \nabla R_n = \expectationdist*{\xi\sim\mathcal{D}}{g_n(\ifblank{}{\,\cdot\,}{};\xi)}. \end{align}\]

Under suitable assumptions (see Assumption 2) on the function \(g\), the function \(R\) is invariant under measure preserving transformations and hence defines a function on \({\widehat\mathcal{W}}\). We are interested in stochastic analogues of the iteration scheme in Definition 1, for such a function \(R\), possibly with a noise at each iteration. In other words, our interest lies in noisy variations of projected GD iterations (see Definition 1). In this setting, we will consider two ways to introduce noise at each iteration.

1. Small noise: We can replace the Euclidean derivative \(\nabla R_n\) in equation ?? by its unbiased stochastic proxy \(g_n\bracket*{(}{)}{\ifblank{}{\,\cdot\,}{}; \xi_{k+1}}\). As a special case, \(g\) can be obtained from a function \(\ell\colon\mathcal{W}\times \Omega \to \mathbb{R}\), as \(g(\ifblank{}{\,\cdot\,}{};\xi) \mathrel{\vcenter{:}}= (D_{\mathcal{W}})\ell(\ifblank{}{\,\cdot\,}{};\xi)\) for all \(\xi\in\Omega\), where \((D_{\mathcal{W}}\ell)(\ifblank{}{\,\cdot\,}{};\xi)\) is the Fréchet-like derivative (see Definition 6) of \(\ell(\ifblank{}{\,\cdot\,}{};\xi)\). Such a stochastic approximation is known as Stochastic Gradient Descent (SGD).

2. Large noise: We can add an additive noise to iterates in equation ?? before the projection, as we describe in Definition 2 below.

We can now define the noisy analogs of ?? , that is, projected (noisy) SGD. We will use the operator \(\circ\) over symmetric matrices to denote the Hadamard (elementwise) product.

Due to the natural identification of \(\mathcal{M}_n\) with \(\mathcal{W}_n\), the GD iterates \(\bracket*{(}{)}{V_{n,k}}_{k\in\mathbb{Z}_+}\subset \mathcal{M}_n\) and the SGD iterates \(\bracket*{(}{)}{W_{n,k}}_{k\in\mathbb{Z}_+}\subset \mathcal{M}_n\) in Definitions 1 and 2 respectively, can be viewed as kernel valued iterates \(\big(V^{(n)}_{k}\big)_{k\in\mathbb{Z}_+}\subset \mathcal{W}_n\) and \(\big(W^{(n)}_{k}\big)_{k\in\mathbb{Z}_+}\subset \mathcal{W}_n\), under the embeddings \(V^{(n)}_k = K(V_{n,k})\) and \(W^{(n)}_k = K(W_{n,k})\) respectively for \(k\in\mathbb{Z}_+\). This allows us to interpret ?? and ?? as kernel-valued updates.

We consider piecewise constant interpolations of the iterates (see Definition 3) and in this paper, we establish the existence of the scaling limit of these curves. We also characterize the limit under the absence of “large noise". Our limiting procedure takes two steps. First, for every fixed \(n\in\mathbb{N}\), we take the step size, i.e., \(\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}\to 0\) to obtain a limiting SDE on \(\mathcal{M}_n\). We then characterize the limit of the SDEs as \(n\to\infty\) as an absolutely continuous curve on the space of graphons.

Note that the diffusion coefficients in ?? act diagonally on the Brownian increments for each coordinate of the matrix valued process. In practice it makes sense to consider non-diagonal diffusion coefficients as an approximation to SGD. See [39] for a discussion. Practitioners also use variants of SGD under the “small noise” setup where instead of having a single unbiased stochastic proxy of the gradient, an average over independent batches of stochastic gradients is used at every step. Authors in [40] derive weak SDE approximations of various popularly used stochastic optimization algorithms that use batches. However this existing literature does not cover SDEs with boundary terms.

Our main interest is in the limit of the kernel valued stochastic process \(X^{(n)}(\cdot)=K\bracket*{(}{)}{X_n(\cdot)}\) (Theorem 1), as \(n \rightarrow \infty\). This limit is a deterministic curve in \({\widehat\mathcal{W}}\) that we now describe. Consider, for simplicity, the special case when each \(\Sigma_n\) is \(\beta\) times the identity matrix for some \(\beta >0\). On a probability space that supports a standard linear Brownian motion \(B_{1,2}(\cdot)\) and a pair of independent \(\mathrm{Uni}\bracket*{\lbrack}{\rbrack}{0,1}\) random variables \((U_1, U_2)\) and given some \(W_0 \in \mathcal{W}\), one can construct a unique solution of the following family of one-dimensional reflected diffusions. Given \((U_1,U_2)=(x,y)\), for some \((x,y)\in \bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\), let \(X_{1,2}\) be a diffusion with state space \(\bracket*{\lbrack}{\rbrack}{-1,1}\) with the initial condition \(X_{1,2}(0)=W_0(x, y)\), and satisfying \[\begin{align} \label{eq:infinite95SDE0} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{1,2}(t) &= -\phi\left( \Gamma (t)\right)(x, y)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \beta \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{1,2}(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^-_{1,2}(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^+_{1,2}(t), \end{align}\tag{6}\] for some \(\beta\in\mathbb{R}_+\) and \(t\in \mathbb{R}_+\). Here, \(\phi\) is the Fréchet-like derivative of \(R\) in 5 , \(L^-_{1,2}\) and \(L^+_{1,2}\) are the local time processes such that \((X_{1,2},L^+_{1,2},L^-_{1,2})\) solves the Skorokhod problem with respect to \(\bracket*{\lbrack}{\rbrack}{-1,1}\) (see Section 2.3). The kernel-valued process \(\Gamma\colon\mathbb{R}_+ \to \mathcal{W}\) is given by \[\label{eq:whatisgammat0} \Gamma(t)(u,v) \mathrel{\vcenter{:}}= \expectation*{ X_{1,2}(t) (U_1,U_2)=(u,v)},\quad \forall\; (u,v)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)},\tag{7}\] and any \(t\in\mathbb{R}_+\). In Proposition 8, we show that the coupled system \((X_{1,2}, \Gamma)\) exists in a strong sense and is pathwise unique and that the kernel-valued process \(X^{(n)}\) in Theorem 1 converges to the curve \(\Gamma\) in the following sense an \(n\to\infty\).

In Section 4 a more general statement with state-dependent diffusion has been proved (see Proposition 9). It is worth noting that presence of noise and the boundary \(\Set*{-1,1}\) in our problem makes it non-trivial. To see this, consider ?? for a constant function \(R_n\) (i.e., \(\nabla R_n\equiv 0\)) and without the local times, say starting at \(W_{n, 0}\in\mathcal{M}_n\). The solution is a symmetric matrix of independent Brownian motions. It can be easily checked that, if \(\lim_{n\rightarrow \infty}\nrm*{\square}{W_{n,0} - W_0}=0\), then \(\lim_{n\to \infty}\sup_{t\in\bracket*{\lbrack}{\rbrack}{0,T}}\nrm*{\square}{X^{(n)}(t)-W_0} = 0\) for any finite \(T>0\). However, if we consider ?? again with \(\nabla R_n\equiv 0\) but with reflection at the boundary, the coordinate processes are independent reflected Brownian motions. In this case the cut limit of \(X^{(n)}(t)\) is also the cut limit of the kernel \(\expectation*{X^{(n)}(t)}\). But reflecting Brownian motions do not have constant expectations in time due to boundary effect. Hence, the limit of \(X^{(n)}(t)\) is not constant in \(t\). But, if this limit were a gradient flow, it would be a constant.

1.1 Scaling limit without added noise↩︎

When \(\Sigma_n \equiv 0\), equation ?? reduces to \[\begin{align} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) = -n^2\nabla R_n(X_n(t))\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{-}_n(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{+}_n(t),\quad t\in\mathbb{R}_+,\quad X_n(0) = W_{n,0},\label{eq:RSDE95beta0} \end{align}\tag{8}\] such that \((X_n,L^+_n,L^-_n)\) solves the Skorokhod problem on \(\mathcal{M}_n\) (see Section 2.3 for details). Moreover, it is shown in Section 3 that the solution of 8 is the same as the solution of 9 given below. Furthermore, it is shown in [34] that if the solution \(X_n\colon\mathbb{R}_+\to\mathcal{M}_n\) of \[\label{eqn:GF95n} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) = -n^2\nabla R_n(X_n(t))\circ\mathbb{1}_{G_n(X_n(t))}\ifblank{}{}{\Set*{}}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t,\qquad t\in\mathbb{R}_+,\tag{9}\] exists, where \(G_n(A)\) is the subset of \(\bracket*{\lbrack}{\rbrack}{n}^{2}\) (defined in equation 28 later in Section 3.1), then \(X_n\) is a gradient flow on \(\mathcal{M}_n\) in a suitable sense. Further, it is shown in [34] that under reasonable assumptions on \(R\), the sequence of solutions \(\bracket*{(}{)}{X_n}_{n\in\mathbb{N}}\) of equation 9 obtained for all natural numbers \(n\in\mathbb{N}\), converge to an absolutely continuous curve \(W\colon\mathbb{R}_+\to\mathcal{W}\) (appropriately in the cut metric (see Definition 4)), which is a curve of maximal slope [42] (a.k.a. gradient flow) of \(R\), as \(n\to\infty\). This yields the following.

We should mention that our method allows us to also obtain a non-asymptotic rate of convergence. We refer the reader to Remark 14 for details.

As an example, consider the function \(R_n\) considered at the beginning of Section 1. \(R_n\) is the restriction to \(\mathcal{M}_n^{0}\) of the function \(R\) on \(\mathcal{W}_0\mathrel{\vcenter{:}}= \Set*{W\in \mathcal{W}W(x, y)\in [0,1] \text{ for a.e. } (x,y)\in[0,1]^{(2)} }\) given by \[R(W) = \frac{1}{2}(H_{\mathrel{-}}(W)-e)^2+\frac{1}{2}(H_{\triangle}(W)-\tau)^2+\mathcal{E}(W),\] where \(\mathcal{E}\mathrel{\vcenter{:}}=\int_0^{1}\int_0^{1} h(W(x, y))\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}x\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}y\). The function \(H_{F}\) is the homomorphism density of \(F\) [34]. The function \(R\) satisfies all the assumptions of Theorem 5. See Section 5.3 for details.

1.2 SGD and permutation symmetries in Deep Neural Networks (DNNs)↩︎

We end this section with a significant example where the permutation invariant functions arise, namely, DNNs. DNNs typically consist of a sequence of matrices that share row/column labels with their adjacent ones. Most modern DNNs possess permutation symmetries in their parametric representations. That is, their output is invariant under permutations applied to the rows/columns of the matrices appearing in DNN representation. The goal is to obtain the sequence of matrices that minimizes the risk function \(R_n\) for \(n\in\mathbb{N}\). This can be thought of as a generalization of the linear regression example discussed in the introduction and in Section 5.4. Authors in [43] empirically study the effectiveness of SGD in optimizing the non-convex DNN risk functions \(R_n\) for large \(n\in\mathbb{N}\). For simplicity, consider the special case when the DNN is parameterized through a single finite symmetric matrix and therefore does not involve shared labels. Let \(\bracket*{(}{)}{U_{n,k}}_{k\in\mathbb{Z}_+}\) and \(\bracket*{(}{)}{V_{n,k}}_{k\in\mathbb{Z}_+}\) be the SGD iterations, starting at two independent initializations, say, \(U_{n,0} \neq V_{n,0}\). Authors in [43] observe that \(\bracket*{(}{)}{U_{n,k}}_{k\in\mathbb{Z}_+}\) and \(\bracket*{(}{)}{V_{n,k}}_{k\in\mathbb{Z}_+}\) can be “aligned” by optimizing over the set of all permutations. That is, for every \(k\in\mathbb{Z}_+\), they solve for \[\pi^*_k \in \argmin_{\pi_k\in S_n}\nrm*{\mathrm{F}}{U_{n,k} - V_{n,k}^{\pi_k}}^2,\] where \(\nrm*{\mathrm{F}}{}\) denotes the Frobenius norm, \(S_n\) is the set of all permutations of \([n]\), and \(V_{n,k}^{\pi_k}\) is the matrix \(V_{n,k}\) with rows and columns relabeled by the permutation \(\pi_k\in S_n\). The authors observe an emergent property of SGD called “linear mode connectivity” (LMC) [44]. This property essentially says that \(R_n\) does not fluctuate a lot on \(W_{n,k}(\lambda)\) for large \(k\in\mathbb{Z}_+\), where \[W_{n,k}(\lambda) = (1-\lambda)U_{n,k} + \lambda V_{n,k}^{\pi_k^*}, \qquad \lambda\in [0, 1].\] Further, they observe that \(R_n(W_{n,k}(\lambda))\) approaches a constant uniformly on \(\lambda\in[0,1]\) as \(n\) goes to infinity. Authors in [45] observe through experiments that for a fixed and large enough \(k\in\mathbb{Z}_+\setminus\Set*{0}\), the permutation \(\pi^*_k\), has negative convexity gap \[R_n\bracket*{(}{)}{(1-\lambda)U_{n,0} + \lambda V_{n,0}^{\pi_k^*}} - \bracket*{\lbrack}{\rbrack}{(1-\lambda) R_n(U_{n,0}) + \lambda R_n\bracket*{(}{)}{V_{n,0}^{\pi_k^*}}}.\] Following these empirical observations and the hypothesis made by the authors in [46], it makes sense to consider DNNs up to their permutation symmetries, and as a consequence, study limiting behaviors of stochastic optimization algorithms over the space of graphons. This requires some generalization of our theory and is an important direction for future work.

2 Background, Assumptions and Setup↩︎

Since we want to obtain continuous time scaling limits of the iterative schemes defined in Definition 1 and Definition 2, we will use piecewise constant interpolations.

We now provide a background on graphons (see [47], [48] for broader expositions).

2.1 Background on Graphons↩︎

Consider the set \(\mathcal{S}\) of all bounded, Borel measurable function \(W\colon [0,1]^{(2)}\to \mathbb{R}\) such that \(W(x, y)=W(y, x)\) for a.e. \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\). For any function \(W\in \mathcal{S}\) one can define the cut norm, \(\nrm*{\square}{}\colon\mathcal{S}\to \mathbb{R}_+\) as \[\begin{align} \nrm*{\square}{W} \mathrel{\vcenter{:}}= \sup_{S, T\subseteq [0, 1]}\bracket*{\lvert}{\rvert}{\int_{S\times T}W(x, y)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}x\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}y}, \qquad W\in\mathcal{S},\label{eq:cut95norm} \end{align}\tag{10}\] where the supremum is taken over Borel measurable sets \(S,T\subseteq\bracket*{\lbrack}{\rbrack}{0,1}\). The cut norm was first introduced in [49] in the context of matrices and was later extended to \(\mathcal{S}\) in [36]. In the following definitions, let \(\mathcal{T}\) denote the set of all measure preserving transformations on \(\bracket*{\lbrack}{\rbrack}{0,1}\) equipped with the Lebesgue measure. We say \(W_1\cong W_2\) (i.e., \(W_1\) and \(W_2\) are weakly isomorphic) if there exists \(W\in \mathcal{S}\) and measure preserving transformations \(\varphi_1, \varphi_2 \in \mathcal{T}\) such that for \(W^{\varphi_i}\in \mathcal{S}\) defined as \(W^{\varphi_i}(x,y) \mathrel{\vcenter{:}}= W\bracket*{(}{)}{\varphi_i(x),\varphi_i(y)}\) for a.e. \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\) and \(i\in[2]\), \(W_1=W^{\varphi_1}\), and \(W_2=W^{\varphi_2}\).

The cut norm \(\nrm*{\square}{}\) induces a metric called the cut metric, denoted by \(\delta_{\square}\), when restricted to the quotient space \(\widehat{\mathcal{S}}\mathrel{\vcenter{:}}=\mathcal{S}/{\cong}\). We denote the equivalence class of \(W\in\mathcal{S}\) under weak isomorphism (\(\cong\)) as \(\bracket*{\lbrack}{\rbrack}{W}\mathrel{\vcenter{:}}= \Set*{U\in\mathcal{S}U\cong W}\in \widehat{\mathcal{S}}\). We now define the cut metric.

More generally, given any norm \(\nrm*{}{}\) on \(\mathcal{S}\), one can define an induced metric \(\delta_{\nrm*{}{}}\) on \(\widehat{\mathcal{S}}\) as \[\begin{align} \delta_{\nrm*{}{}}([W_1], [W_2])\mathrel{\vcenter{:}}= \inf_{\varphi, \psi\in\mathcal{T}} \nrm*{}{W_1^{\varphi}-W_2^{\psi}} , \end{align}\]

In particular, the induced metric due to the \(L^2\) norm, \(\nrm*{2}{}\colon L^2(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)})\to\mathbb{R}_+\), is called the invariant \(L^2\) metric, \(\delta_2\), and it would be used in our discussion.

As defined in Section 1, the set of kernels \(\mathcal{W}\subset \mathcal{S}\) is the set of measurable, symmetric functions \(W\colon [0,1]^{(2)}\to [-1, 1]\) and correspondingly \({\widehat\mathcal{W}}\mathrel{\vcenter{:}}=\mathcal{W}/{\cong}\) is the set of graphons. For most of our discussion, we will be concerned only with the space of graphons equipped with either the cut metric \(\delta_{\square}\) or the invariant \(L^2\) metric \(\delta_{2}\). The metrics on \(\mathcal{S}\) induced by the norms \(\nrm*{\square}{}\) and \(\nrm*{2}{}\) with be denoted by \(d_\square\) and \(d_2\) respectively.

For every \(n\in\mathbb{N}\), the set \(\mathcal{M}_n\) can be naturally identified with a subset of \(\mathcal{W}\). Let \(\mathcal{V}_n\mathrel{\vcenter{:}}= \Set*{V_i}_{i\in\bracket*{\lbrack}{\rbrack}{n}}\) be a partition of the interval \(\bracket*{\lbrack}{\rbrack}{0,1}\) into contiguous intervals of equal length (Lebesgue measure). We define the set of kernels \(\mathcal{W}_n\subset\mathcal{W}\) which contain kernels which are constant a.e. over sets in \(\mathcal{V}_n\times \mathcal{V}_n\).

We note some crucial properties of these metric spaces that will be frequently used throughout this paper even without explicitly mentioning.

1. Properties of \(\delta_\square\):

   1. The topology induced by the cut metric \(\delta_\square\) on \({\widehat\mathcal{W}}\) is compact [50], [47].

   2. Convergence in the cut metric is related to the convergence of homomorphism functions via the counting and the inverse counting lemmas [47].

2. Properties of \(\delta_{2}\):

   1. The metric space \(({\widehat\mathcal{W}},\delta_2)\) is a geodesic metric space [34].

   2. The metric space \(({\widehat\mathcal{W}},\delta_2)\) is complete and separable but not compact.

   3. Convergence in \(\delta_2\) implies convergence in \(\delta_\square\), implying that the topology generated by \(\delta_2\) is stronger that the one generated by \(\delta_\square\) on \({\widehat\mathcal{W}}\).

As \(({\widehat\mathcal{W}}, \delta_{2})\) is a geodesic metric space, it therefore makes sense to talk about geodesically convex or geodesically semiconvex functions.

In Section 1, we noted in equation 5 that Euclidean gradient \(\nabla R_n\) of \(R_n\) is closely related to what we call the Fréchet-like derivative of \(R\colon\mathcal{W}\to \mathbb{R}\). We state its definition below.

The scaling limit as we obtain in Theorem 2, under certain assumptions can be shown to be absolutely continuous with respect to \(d_2\) (see Proposition 10). We state its definition for the sake of completeness.

2.2 Assumptions↩︎

In this section we state all the required assumptions we need to prove our results (see Theorem 1 and Theorem 2).

2.3 System of reflected diffusions↩︎

For \(n\in\mathbb{N}\), consider the domain \(\mathcal{M}_n\). Notice that \(\mathcal{M}_n\) is a cube, and is closed with respect to the usual topology. Consider the SDE: \[\begin{align} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{n}(t) &= -n^2\nabla R_n(X_{n}(t))\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \Sigma_n(X_n(t))\circ \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{n}(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n}^-(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n}^+(t),\label{eq:SDE95with95L} \end{align}\tag{11}\] for \(t\in\bracket*{\lbrack}{\rbrack}{0,T}\) for some fixed \(T\in\mathbb{R}_+\) and starting at \(X_n(0)=X_{n,0}\in \mathcal{M}_n\). Here \(\Sigma_n\) is a map from \(\mathcal{M}_n\) to the set of \(n\times n\) symmetric matrices with non-negative entries, \(B_{n}\) is a \(n\times n\) symmetric matrix valued process containing a set of standard Brownian motions \(\bracket*{(}{)}{B_{n,(i,j)}}_{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{(2)}}\) which are independent up to matrix symmetry, and the processes \(L_{n}^-\) and \(L_{n}^+\) are local times at the boundary. More precisely, they satisfying the following conditions:

1. The processes \(X_{n}\), \(L_{n}^+\) and \(L_n^-\) are adapted processes.

2. The process \(L_{n}^-\) and \(L_n^+\) are coordinatewise non decreasing processes a.e.

3. For every \((i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2}\), \[\begin{align} \begin{aligned} \int_0^\infty \mathbb{1}_{}\ifblank{X_{n,(i,j)}(t) > -1}{}{\Set*{X_{n,(i,j)}(t) > -1}} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n,(i,j)}^-(t) &= 0, \qquad\text{and}\quad\\ \int_0^\infty \mathbb{1}_{}\ifblank{X_{n,(i,j)}(t) < +1}{}{\Set*{X_{n,(i,j)}(t) < +1}} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n,(i,j)}^+(t) &= 0. \end{aligned} \end{align}\]

We say that \(\bracket*{(}{)}{X_{n},L_{n}^+,L_{n}^-}\) solves the Skorokhod problem with respect to the set \(\mathcal{M}_n\). Following [51], the strong solution \(\bracket*{(}{)}{X_{n},L_{n}^+,L_{n}^-}\) of the Skorokhod problem exists and is unique if \(n^2\nabla R_n\) and \(\Sigma_n\) are Lipschitz with respect to \(\nrm*{\mathrm{F}}{}\) (following Assumption 1, Assumption 3 and equation 5 ).

2.3.1 The Lipschitz property of the Skorokhod map↩︎

Let \(Y_1\) and \(Y_2\) be two real valued stochastic processes. Let \(\Lambda_{\bracket*{\lbrack}{\rbrack}{-1,1}}\) denote the Skorokhod map that maps the set of càdlàg functions on \(\bracket*{\lbrack}{\rbrack}{0,T}\) to itself. If \((X_1 \mathrel{\vcenter{:}}= \Lambda_{\bracket*{\lbrack}{\rbrack}{-1,1}}(Y_1),L_1^+,L_1^-)\) and \((X_2 \mathrel{\vcenter{:}}= \Lambda_{\bracket*{\lbrack}{\rbrack}{-1,1}}(Y_2),L_2^+,L_2^-)\) solve the Skorokhod problem with respect to the set \(\bracket*{\lbrack}{\rbrack}{-1,1}\), then the Skorokhod map \(\Lambda_{\bracket*{\lbrack}{\rbrack}{-1,1}}\) is \(4\)-Lipschitz under the uniform metric [51], i.e., \[\begin{align} \sup_{t\in\bracket*{\lbrack}{\rbrack}{0,T}}\bracket*{\lvert}{\rvert}{X_1(t) - X_2(t)} \leq 4\sup_{t\in\bracket*{\lbrack}{\rbrack}{0,T}}\bracket*{\lvert}{\rvert}{Y_1(t) - Y_2(t)}, \qquad\forall\;T\in\mathbb{R}_+.\label{eq:skorokhod95lipschitz} \end{align}\tag{12}\]

3 Convergence of Projected Noisy Stochastic Gradient Descent↩︎

The goal of this section is to show that for each \(n\in\mathbb{N}\), the projected noisy SGD iterates, defined in ?? , converges weakly to the strong solution of the SDE ?? as \(\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}\to 0\). This is done in two steps that we describe below.

Recall the projected noisy SGD iterates defined in Definition 2, starting from \(W_{n,0}\in\mathcal{M}_n\), rewritten for convenience:\[\begin{align} W_{n, k+1} &= P\bracket*{(}{)}{W_{n, k} - n^2\tau_{n,k}\nabla R_n\bracket*{(}{)}{W_{n, k}} - \tau_{n,k}\Delta M_{n,k} + \tau_{n,k}^{1/2}G_{n, k}}, \label{eq:PSGD43Noise}\end{align}\tag{13}\] for \(k\in\mathbb{R}_+\), where \(\bracket*{(}{)}{G_{n, k}}_{k\in\mathbb{Z}_+}\) is any \(n\times n\) real symmetric matrix valued martingale difference sequence with each element containing centered and independent entries up to matrix symmetry, as defined in Section 1, and\[\Delta M_{n, k} \mathrel{\vcenter{:}}= n^2g_n\bracket*{(}{)}{W_{n,k};\xi_{k+1} } -n^2\nabla R_n\bracket*{(}{)}{W_{n, k}} , \qquad k\in\mathbb{Z}_+ .\] Observe that \(\bracket*{(}{)}{\Delta M_{n, k}}_{k\in\mathbb{Z}_+}\) is an \(n\times n\) symmetric matrix valued martingale difference sequence with respect to the filtration \(\bracket*{(}{)}{\mathcal{F}_k}_{k\in\mathbb{Z}_+}\) where \(\mathcal{F}_k\mathrel{\vcenter{:}}= \sigma\big(\Set*{ W_{n, 0}, \xi_{i+1}, G_{n, i}}_{i\in\Set*{0}\cup[k-1]}\cup\Set*{\xi_{k+1}} \big)\) for \(k\in\mathbb{Z}_+\). Without the martingale difference term \(\tau_{n,k}\Delta M_{n, k}\), equation 13 reduces to the projected GD iterates with additive noise, \(\bracket*{(}{)}{V_{n,k}}_{k\in\mathbb{Z}_+}\) starting at \(V_{n,0}=W_{n,0}\), described in 14 , re-written below \[\begin{align} V_{n,k+1} &= P\bracket*{(}{)}{V_{n,k} - n^2\tau_{n,k}\nabla R_n\bracket*{(}{)}{V_{n,k}} + \tau_{n,k}^{1/2}G_{n,k}}, \qquad k\in\mathbb{Z}_+. \label{eq:PGD43Noise}\end{align}\tag{14}\] Let \(W^{(n)}_{k} \mathrel{\vcenter{:}}= K\bracket*{(}{)}{W_{n,k}}\) and \(V^{(n)}_{k} \mathrel{\vcenter{:}}= K\bracket*{(}{)}{V_{n,k}}\) for all \(k\in\mathbb{Z}_+\), and let \(W^{(n)}\) and \(V^{(n)}\) be piecewise constant interpolations of \(\big(W^{(n)}_k\big)_{k\in\mathbb{Z}_+}\) and \(\big(V^{(n)}_k\big)_{k\in\mathbb{Z}_+}\) respectively with the step size sequence \({\boldsymbol{\tau}}_n\). Using Grönwall’s inequality and an obvious coupling between the processes 13 and 14 , we show in Lemma 1 that the two processes are close as \(\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}\to 0\).

Our next step is to show that sequence of iterates defined in 14 is close to the solution of the SDE ?? which we reproduce below \[\begin{align} \begin{aligned} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{n}(t) &= -n^2\nabla R_n(X_{n}(t)) + \Sigma_n(X_n(t)) \circ \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{n}(t)\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n}^+(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n}^-(t) ,\quad t\in\mathbb{R}_+, \end{aligned} \label{eq:SDE}\end{align}\tag{19}\] where \(B_n\) is an \(n\times n\) symmetric matrix valued process whose entries are independent Brownian motions up to matrix symmetry, and \(X_{n}(0) = V_{n,0} = W_{n,0} \in \mathcal{M}_n\). The tuple \(\bracket*{(}{)}{X_{n},L_{n}^+,L_{n}^-}\) solves the Skorokhod problem with respect to the set \(\mathcal{M}_n\) (see Section 2.3).

In Lemma 2 we compare 14 with a discretization of the SDE ?? . This is obtained by coupling the discrete noise in 14 with the Brownian motion driving the SDE 19 . Combining these we conclude the convergence of  13 to the SDE 19 as \(\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}\to 0\).

We combine Lemma 1 and 2 to conclude the proof of Theorem 1. Moreover, we also obtain the following non-asymptotic error rate \[\expectation*{\sup_{s\in\bracket*{\lbrack}{\rbrack}{0,T}} \nrm*{2}{W^{(n)}(s)-K(X_{n})(s)}^2} \leq Cn^2(M+\sigma^2T)\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}\log\frac{1}{\bracket*{\lvert}{\rvert}{{\boldsymbol{\tau}}_n}}\exp\bracket*{\lbrack}{\rbrack}{C \kappa_2^2 T}\] for some constants \(C, M<\infty\).

3.1 Convergence of Projected Stochastic Gradient Descent↩︎

In the absence of “large noise” (i.e., when \(\Sigma_n\equiv 0\)), the SDE 19 reduces to the SDE \[\begin{align} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) = -n^2\nabla R_n(X_n(t))\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{-}_n(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{+}_n(t),\qquad X_n(0) = W_{n,0},\label{eq:RSDE95sigma0} \end{align}\tag{26}\] As we describe in Section 1.1, it is show in [34] that if the solution of \[\label{eqn:GF95indicator} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) = -n^2\nabla R_n(X_n(t))\circ\mathbb{1}_{G_n(X_n(t))}\ifblank{}{}{\Set*{}}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t,\tag{27}\] exists, where \(G_n(A)\) is the subset of \(\bracket*{\lbrack}{\rbrack}{n}^{2}\) defined as \[\begin{align} \label{eq:G95n} \begin{aligned} G_n(A) &\mathrel{\vcenter{:}}= \Set*{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2} \bracket*{\lvert}{\rvert}{A(i,j)}<1}\\ &\qquad\cup \Set*{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2} A(i,j)=1, \@ifnextchar^{\pDIfF}{ \mathop{\mathrm{\mathstrut \partial}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}_{i,j} R_n(A)>0}\\ &\qquad\qquad \cup \Set*{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2} A(i,j)=-1, \@ifnextchar^{\pDIfF}{ \mathop{\mathrm{\mathstrut \partial}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}_{i,j} R_n(A)<0}, \end{aligned} \end{align}\tag{28}\] for all \(A\in\mathcal{M}_n\), then the solution \(X_n\) is a gradient flow on \(\mathcal{M}_n\) in a suitable sense. In this section, we will argue that the solutions \(X_n\) of equation 26 and 27 are equal. To this end, we define processes \(L_n^{\pm}\) as \[\begin{align} \label{eq:L94pm95def} \begin{aligned} L^+_n(t) &\mathrel{\vcenter{:}}= -\int_0^t n^2\nabla R_n(X_n(s))\circ\mathbb{1}_{\Set*{X_n(s)=+1,\nabla R_n(X_n(s))<0}}\ifblank{}{}{\Set*{}}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}s,\\ L^-_n(t) &\mathrel{\vcenter{:}}= +\int_0^t n^2\nabla R_n(X_n(s))\circ\mathbb{1}_{\Set*{X_n(s)=-1,\nabla R_n(X_n(s))>0}}\ifblank{}{}{\Set*{}}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}s, \end{aligned} \end{align}\tag{29}\] for \(t\in\mathbb{R}_+\), and equation 27 can be rewritten as \[\begin{align} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) &= -n^2\nabla R_n(X_n(t))\circ\mathbb{1}_{G_n(X_n(t))}\ifblank{}{}{\Set*{}} + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^-_n(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^+_n(t), \end{align}\] and the processes \(L_n^+\) and \(L_n^-\) satisfy the following conditions:

1. The processes \(X_{n}\), \(L_{n}^+\) and \(L_n^-\) are adapted processes.

2. The processes \(L_{n}^-\) and \(L_n^+\) are non-decreasing processes.

3. For every \((i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{2}\), \[\begin{align} \int_0^\infty \mathbb{1}_{}\ifblank{X_{n,(i,j)}(t) > -1}{}{\Set*{X_{n,(i,j)}(t) > -1}} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n,(i,j)}^-(t) &= 0, \quad\text{and}\\ \int_0^\infty \mathbb{1}_{}\ifblank{X_{n,(i,j)}(t) < +1}{}{\Set*{X_{n,(i,j)}(t) < +1}} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L_{n,(i,j)}^+(t) &= 0. \end{align}\]

Following Section 2.3, these conditions ensure that the processes \(L_n^+\) and \(L_n^-\) are unique and \((X_n,L_n^+,L_n^-)\) solves the Skorokhod problem with respect to the set \(\mathcal{M}_n\). This proves Theorem 5.

4 Convergence of the finite dimensional SDEs↩︎

4.1 The limit at infinity: infinite exchangeable array of diffusions↩︎

Let \(\mathcal{E}\) be a standard Borel space. The sets \(\bracket*{\lbrack}{\rbrack}{n}^{(2)}\) and \(\mathbb{N}^{(2)}\) will refer to the set of natural number pairs \((i,j)\) in \(\mathbb{N}^2\) and \(\bracket*{\lbrack}{\rbrack}{n}^2\) respectively, such that \(i<j\). Recall that an \(\mathcal{E}\)-valued exchangeable (symmetric) array refers to a doubly indexed collection of random elements \(\left(\zeta_{i,j}\mathrel{\vcenter{:}}= \zeta_{\{i,j\}} \in \mathcal{E} \right)_{(i,j)\in\mathbb{N}^{(2)}} \eqqcolon\zeta\) that remain invariant in law under finite permutations of natural numbers \(\mathbb{N}\). Two special cases of \(\mathcal{E}\) that are important to us are \(\mathcal{E}=[-1,1]\) and \(\mathcal{E}=C[0, \infty)\) with the usual Borel topology. The Aldous-Hoover representation theorem [56]–[58] says that given any exchangeable array as above, there exists a measurable function \(f\colon [0,1]\times \bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\times \bracket*{\lbrack}{\rbrack}{0,1} \rightarrow \mathcal{E}\) such that \(\zeta_{i,j}=f\left( U, U_i, U_j, U_{i,j} \right) = f\left( U, U_j, U_i, U_{i,j} \right)\) for \((i,j)\in\mathbb{N}^{(2)}\), where \(U\), \(\bracket*{(}{)}{U_i}_{i \in \mathbb{N}}\), \(\bracket*{(}{)}{U_{i,j}=U_{\{i,j\}}}_{(i,j)\in \mathbb{N}^{(2)}}\) are i.i.d. \(\mathrm{Uni}[0,1]\) random variables. The function \(f\) is typically not unique. Following [59], we say that \(\zeta\) is directed by \(f\).

The relationship between exchangeable arrays and graphons follows from the Aldous-Hoover representation [60]. Assume that \(\zeta_{i,j}\)s are real valued and take values in the closed interval \([-1,1]\). An infinite exchangeable array gives rise to a random graphon reminiscent of the de Finetti representation theorem for exchangeable sequences of random variables. Although we believe that the following result is well-known, we could not find a statement to this effect in the literature. However, it inspires our later constructions.

Consider \(\left(C[0, \infty)\right)^{\mathbb{N}^{(2)}}\) with the natural filtration generated by the coordinate process. Enlarge the filtration by expanding the probability space to accommodate the countably many i.i.d. \(\mathrm{Uni}[0,1]\) random variables \(\bracket*{(}{)}{U_i}_{i \in \mathbb{N}}\) and including the sigma algebra generated by them in the sigma algebra at time zero. Endow this filtered probability space with a probability measure \(P^\infty\) that denote the joint law of \((U_i)_{i \in \mathbb{N}}\) and that of an independent array of countably many independent Brownian motions (BMs) \(\Set*{B_{i,j}=B_{\{i,j\}}}_{(i,j)\in\mathbb{N}^{(2)}}\). Finally we turn the natural filtration to one that is right-continuous and complete, thereby satisfying the so-called usual conditions and denote it by \(\mathcal{F}= \left(\mathcal{F}_t\right)_{t \in \mathbb{R}_+}\). All our processes will be adapted to this filtration associated with this set-up. Note that all uniform random variables \(\bracket*{(}{)}{U_i}_{i\in\mathbb{N}}\) are measurable with respect to \(\mathcal{F}_0\).

Let \(\phi\) and \(\Sigma\) be two functions from \(\mathcal{W}\) to \(L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) that are both \(\kappa_2\)-Lipschitz functions on kernels with respect to the the \(L^2\) norm \(\nrm*{2}{}\) (Assumption 1 and 3). Our goal is to construct, on the above probability space with filtration \(\bracket*{(}{)}{\mathcal{F}_t}_{t\in\mathbb{R}_+}\), an exchangeable array of reflected diffusions satisfying \[\begin{align} \label{eq:infinite95SDE951} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{i,j}(t) &= -\phi\bracket*{(}{)}{\Gamma(t)}(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \Sigma\left( \Gamma(t)\right)(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{i,j}(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^-_{i,j}(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^+_{i,j}(t) , \end{align}\tag{31}\] with the initial condition \(X_{i, j}(0)=W_0(U_i, U_j)\) for all \((i,j)\in\mathbb{N}^{(2)}\), for some \(W_0\in \mathcal{W}\) and \[\Gamma(t)(x, y)=\expectation*{X_{1, 2}(t)U_1=x, U_2=y}.\]

We construct a diffusion with more general drift as follows. Let \(b\colon \bracket*{\lbrack}{\rbrack}{-1,1}\times \mathcal{W}\to L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) be satisfy Assumption 5. Given \(W_0 \in \mathcal{W}\), let \(X \mathrel{\vcenter{:}}= \bracket*{(}{)}{X_{i,j}\mathrel{\vcenter{:}}= X_{\{i,j\}}}_{(i,j) \in \mathbb{N}^{(2)}}\), be the solution of the following system of SDE taking values in \([-1,1]^{\mathbb{N}^{(2)}}\) with the initial condition \(\bracket*{(}{)}{X_{i,j}(0)=W_0(U_i, U_j)}_{(i,j)\in\mathbb{N}^{(2)}}\), and satisfying \[\begin{align} \label{eq:infinite95SDE} \begin{aligned} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_{i,j}(t) &= b\bracket*{(}{)}{X_{i,j}(t),\Gamma(t)}(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \Sigma\left( \Gamma(t)\right)(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{i,j}(t)\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^-_{i,j}(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^+_{i,j}(t) , \end{aligned} \end{align}\tag{32}\]

for \((i,j)\in\mathbb{N}^{(2)}\) and \(t\in \mathbb{R}_+\). The processes \(L^-_{i,j}\) and \(L^+_{i,j}\) are such that \((X_{i,j},L^+_{i,j},L^-_{i,j})\) solves the Skorokhod problem with respect to \(\bracket*{\lbrack}{\rbrack}{-1,1}\) (see Section 2.3), i.e., \(L^-_{i,j}\) and \(L^+_{i,j}\) are non-decreasing processes that keep the processes \(X_{i,j}\)s in the closed interval \(\bracket*{\lbrack}{\rbrack}{-1,1}\). The kernel valued process \(\Gamma \colon \mathbb{R}_+ \to \mathcal{W}\) is adapted to the sigma algebra generated by the uniform random variables \((U_i)_{i \in \mathbb{N}}\), and the independent BMs \(\bracket*{(}{)}{B_{i,j}}_{(i,j)\in\mathbb{N}^{(2)}}\), and given by \[\label{eq:whatisgammat} \Gamma(t)(x,y) \mathrel{\vcenter{:}}= \expectation*{ X_{1,2}(t) U_1=x, U_2=y},\tag{33}\] for \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\) and \(t\in\mathbb{R}_+\). Note that if the solution \(X\) of the system of SDEs 32 exists, then conditioned over the sigma algebra \(\mathcal{F}_0\), the coordinate processes of \(X\) are all independent but not necessarily identically distributed. In particular, taking \(b(z, W)(x, y)=-\phi(W)(x, y)\), we recover the system of diffusions in 31 .

It is not obvious if an infinite-dimensional stochastic process satisfying 32 and 33 exists, although it is obvious that such a process, if it exists, will be an infinite exchangeable array taking values in \(\mathcal{E}=C[0, \infty)\). In the rest of this section, under Assumption 5 we show that the process \(\left( X, \Gamma \right)\) is indeed well-defined. As will be made clear in Proposition 9, the limiting object \(\Gamma\) is the counterpart to the measure-valued solution of the McKean-Vlasov equation, while every \(X_{i,j}\) for \((i,j)\in\mathbb{N}^{(2)}\) is the counterpart to the non-linear evolution of a randomly chosen particle evolving in the McKean-Vlasov interacting system. It should be noted that the particles in this McKean-Vlasov interaction correspond to the edges of the graphs not the vertices. The McKean-Vlasov equation here describes how the graphon itself evolves in time and it is different from the McKean-Vlasov system described in the introduction where the McKean-Vlasov equation describes the evolution of particles which may possibly depend on some underlying graphon.

Observe that Assumption 5 implies Assumption 1([item:phi95lip]) for \(\kappa_2^2 = 2(L^2+\kappa^2)\) and that \(\nrm*{\infty}{b(z, W)}\leq C\) uniformly over all \(z\in [-1, 1]\) and \(W\in \mathcal{W}\).

To argue about the existence of a unique solution of the system of SDEs 32 , we construct a sequence of stochastic processes \(\left( X^{(k)}, \Gamma^{(k)}\right)_{k \in \mathbb{Z}_+}\) on \(C\big([0, \infty),\bracket*{\lbrack}{\rbrack}{-1,1}^{\mathbb{N}^{(2)}} \times \mathcal{W}\big)\) iteratively. Start by defining \(\bracket*{(}{)}{X^{(0)},\Gamma^{(0)}}\) as \(X^{(0)}_{i,j}(t) \equiv W_0(U_i, U_j)\), \(\Gamma^{(0)}(t)\equiv W_0\), for all \((i,j)\in\mathbb{N}^{(2)}\), and \(t\in\mathbb{R}_+\). The induction proceeds by showing that whenever \(\bracket*{(}{)}{X^{(k)}, \Gamma^{(k)}}\) for \(k\in\mathbb{Z}_+\) is well defined, \(X^{(k)}\) is an infinite exchangeable array (Lemma 4 below) and, \(\Gamma^{(k)}\) is a deterministic process of kernels (Lemma 5). Note that these claims are clearly true for \(k=0\). Then, inductively, define the process \(X^{(k+1)}\) as the strong solution to the coordinatewise reflected SDE: \[\begin{align} \label{eq:picardsde} \begin{aligned} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X^{(k+1)}_{i,j}(t) &= b\bracket*{(}{)}{X^{(k)}_{i,j}(t),\Gamma^{(k)}(t)}(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \Sigma\left(\Gamma^{(k)}(t)\right)(U_i, U_j)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_{i,j}(t)\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{(k+1)-}_{i,j}(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{(k+1)+}_{i,j}(t), \end{aligned} \end{align}\tag{34}\] for \(t\in\mathbb{R}_+\), with the same initial condition \(X^{(k+1)}_{i,j}(0)=W_0(U_i, U_j)\) for all \((i,j)\in\mathbb{N}^{(2)}\). As usual, \(L^{(k+1)-}_{i,j}\) and \(L^{(k+1)+}_{i,j}\) are processes such that \(\big(X^{(k+1)}_{i,j},L^{(k+1)+}_{i,j},L^{(k+1)-}_{i,j}\big)\) solves the Skorokhod problem with respect to \(\bracket*{\lbrack}{\rbrack}{-1,1}\) (see Section 2.3) for every \((i,j)\in\mathbb{N}^{(2)}\). Since the drift and diffusion functions \(\phi\) and \(\Sigma\) are deterministic and Lipschitz (Assumption 1), given \(\mathcal{F}_0\), every process \(X^{(k)}\) for \(k\in\mathbb{N}\) exists uniquely in the strong sense.

In fact, given \(\mathcal{F}_0\), the entries of the array \(X^{(k+1)}\) are independent and distributed as reflected Brownian motions (RBMs) with Lipschitz (but time-varying) drifts and diffusion coefficients. In particular, the kernel \(\Gamma^{(k+1)}\) is constructed from the array \(X^{(k+1)}\) (which over the entire probability space is exchangeable, as we show next in Lemma 4) as described in equation ?? in Lemma 3, and is therefore defined as \[\label{eq:picardgamma} \Gamma^{(k+1)}(t)(x,y)\mathrel{\vcenter{:}}= \expectation*{ X^{(k+1)}_{1,2}(t) U_1=x, U_2=y}, \qquad t\in\mathbb{R}_+.\tag{35}\] The kernel \(\Gamma^{(k+1)}(t)\) is well-defined for a.e. \((x,y)\in \bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\) and all \(t\in\mathbb{R}_+\). The induction hence continues.

4.2 Convergence of the finite dimensional processes↩︎

Consider now the finite dimensional SDE ?? : \[\label{eq:sden2} \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}X_n(t) = -n^2\nabla R_n(X_n(t))\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}t + \Sigma_n(X_n(t)) \circ \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}B_n(t) + \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{-}_n(t) - \@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}L^{+}_n(t).\tag{45}\]

The Fréchet-like derivative of \(R\) is a symmetric kernel-valued map from \(\mathcal{W} \rightarrow L^\infty\big( \bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\). Thus, for \((x,y) \in \bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\), there is a real-valued map \(\phi_{x,y}\colon \mathcal{W} \rightarrow \mathbb{R}\) given by \(\phi_{x,y}\left( V\right)= \phi(V)\bracket*{(}{)}{x,y}\) for all \(V\in\mathcal{W}\). This is the same map that we get when we replace \((x,y)\) by \((y,x)\). To show that the finite dimensional processes converge as \(n\to\infty\), we will need to put further assumptions on the drift and diffusion functions.

5 Examples↩︎

In this section, we will verify our assumptions for a class of functions introduced as linear functions in [34]. Let \(\Set*{Z_i}_{i\in\bracket*{\lbrack}{\rbrack}{n}}\) be i.i.d. \(\mathrm{Uni}\bracket*{\lbrack}{\rbrack}{0,1}\). For any kernel \(W\in\mathcal{W}\) and any \(n\in\mathbb{N}\), sample a random matrix \(G_n[W]\) as \(G_n[W] \mathrel{\vcenter{:}}= \bracket*{(}{)}{W(Z_i,Z_j)}_{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{(2)}} \in\mathcal{M}_n\). Let \(\rho_n([W])\) denote its law, i.e., \(\mathrm{Law}(G_n[W]) = \rho_n([W])\). Now let \(R\colon\mathcal{W}\to \mathbb{R}\) be defined as a linear function, i.e., \[R(W) \mathrel{\vcenter{:}}= \int_{\mathcal{M}_n} R_n(z)\rho_n([W])(\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}z), \qquad \forall\;W\in\mathcal{W},\] Let \((\Omega,\mathcal{A})\) be the standard measurable space on \(\bracket*{\lbrack}{\rbrack}{0,1}^n\). Let \(\ell\colon \mathcal{W}\times \Omega\) be the function defined as \[\ell(W,Z) \mathrel{\vcenter{:}}= R_n\bracket*{(}{)}{\bracket*{(}{)}{W(Z_i,Z_j)}_{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^{(2)}}}.\]

Let \(R_n\) satisfy Assumption 1([item:Rn95C1]) and let \(R\) admit a Fréchet-like derivative evaluation map \(\phi\colon\mathcal{W}\to L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) (see [34] for conditions). The map \(\phi\) then satisfies \[\begin{align} \phi(W)(x,y) = \sum\nolimits_{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^2} \expectation*{ \nabla R_n \bracket*{(}{)}{\bracket*{(}{)}{W(Z_p,Z_q)}_{(p,q)\in\bracket*{\lbrack}{\rbrack}{n}^{(2)}}} (Z_i,Z_j) = (x,y)}, \end{align}\] and \(D_\mathcal{W}\ell(\ifblank{}{\,\cdot\,}{};Z)\) for \(Z\in\bracket*{\lbrack}{\rbrack}{0,1}^n\) satisfies \[\begin{align} (D_\mathcal{W}\ell(\ifblank{}{\,\cdot\,}{};Z))(W)(x,y) = \sum\nolimits_{(i,j)\in\bracket*{\lbrack}{\rbrack}{n}^2} \nabla R_n \bracket*{(}{)}{\bracket*{(}{)}{W(Z_p,Z_q)}_{(p,q)\in\bracket*{\lbrack}{\rbrack}{n}^{(2)}} \big\vert_{(Z_i,Z_j) = (x,y)}}, \end{align}\] for \(W\in\mathcal{W}\) and \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\).

5.1 Scalar Entropy and Homomorphism density↩︎

Examples like the scalar entropy and the homomorphism density functions considered in [34], all satisfy Assumption 1 for some \(\kappa_2\in\mathbb{R}_+\) since \(\nrm*{\mathrm{op}}{\mathrm{Hess}(R_n)}\) exists and is bounded uniformly in the domain. Specifically, for homomorphism density function \(R = H_F\) for a simple graph \(F\) with \(n\) vertices and \(m\) edges \(\Set*{e_l}_{l=1}^m\), the constants \(\kappa_2 = mn(n-1)\), and for scalar entropy \(R = \mathcal{E}\), the constant \(\kappa_2 = 2\epsilon^{-1}(1-\epsilon)^{-1}\) on its domain \(\mathcal{W}_\epsilon\mathrel{\vcenter{:}}= \Set{W\in\mathcal{W}\epsilon\leq W \leq 1-\epsilon}\) where \(\epsilon\in(0,1/2)\). Since this implies that there exists \(M_\infty\in\mathbb{R}_+\) such that \(\nrm*{\infty}{\phi(W)}\leq M_\infty\) for all \(W\) in the domain, these example also satisfy Assumption 2 for \(\sigma = M_\infty\).

In the following, we define \(b\colon\bracket*{\lbrack}{\rbrack}{-1,1}\times \mathcal{W}\to L^\infty\big(\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\big)\) as \(b(W(x,y),W)(x,y) = -\phi(W)(x,y)\) for all \(W\in\mathcal{W}\) and a.e. \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\). We will now verify Assumption 6 when \(R\) is the sum of scalar entropy and some homomorphism density \(H_F\) for a simple graph \(F\) with \(n\) vertices and \(m\) edges. Note that for this example, we have \[\begin{align} b(z,W)(x,y) = \log\frac{z}{1-z} + \phi_{H_F}(W)(x,y),\qquad z = W(x,y)\in \bracket*{\lbrack}{\rbrack}{\epsilon,1-\epsilon},\label{eq:phi95scalar95entropy43hom} \end{align}\tag{56}\] for a.e. \((x,y)\in[0,1]^{(2)}\) where from [34], \[\begin{align} \phi_{H_F}(W)(x,y) &= \sum_{l=1}^m \expectation*{\prod_{r=1,r\neq l}^m W(Z_{e_r}) Z_{e_l}=(x,y)}\\ &\eqqcolon \sum_{l=1}^m \mathbf{t}_{x,y}(F_{e_l},W), \quad (x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}, \end{align}\] \(Z_{e} = (Z_{e(1)},Z_{e(2)})\) and \(F_{e_l}\) is the simple graph obtained from \(F\) by removing the edge \(e_l\). It is shown in [34] that the map \(W \mapsto \mathbf{t}_{(\cdot,\cdot)}(F_{e},W)\) continuous as a map from \((\mathcal{W},d_\square)\) to \(\big(L^\infty\big([0,1]^{(2)}\big),d_\square\big)\). To show that \(\phi_{H_F}(\ifblank{}{\,\cdot\,}{})(x,y)\) is Lipschitz in the cut norm for every \((x,y)\in\bracket*{\lbrack}{\rbrack}{0,1}^{(2)}\), it is sufficient to show that \(\mathbf{t}_{x,y}(F_e,\ifblank{}{\,\cdot\,}{})\) is Lipschitz in the cut norm for \(e\in\Set*{e_l}_{l=1}^m\). For \(W_1,W_2\in\mathcal{W}\), note that \[\begin{align} \mathbf{t}_{x,y}(F_e,W_1) - \mathbf{t}_{x,y}(F_e,W_2) = \sum_{\Set*{p,q}\in E(F_e)} I_{p,q}, \end{align}\] where for any \(\Set*{p,q}\in E(F_e)\), \[\begin{align} I_{p,q} \mathrel{\vcenter{:}}= \int_{\bracket*{\lbrack}{\rbrack}{0,1}^{n-2}}\bracket*{(}{)}{W_1(x_p,x_q)-W_2(x_p,x_q)}\prod_{(i,j)\in E(F_e)\setminus \Set*{p,q}}W_1(x_i,x_j) \prod_{v\in V(F_e)\setminus e}\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}x_v. \end{align}\] Following the proof in [47], we get \(\bracket*{\lvert}{\rvert}{I_{p,q}} \leq \nrm*{\square}{W_1-W_2}\), which yields \[\begin{align} \label{eqn:t95calc} \bracket*{\lvert}{\rvert}{\mathbf{t}_{x,y}(F_e,W_1) - \mathbf{t}_{x,y}(F_e,W_2)} \leq (m-1)\nrm*{\square}{W_1-W_2}, \end{align}\tag{57}\] i.e., the Lipschitz constant of \(\mathbf{t}_{x,y}(F_e,\ifblank{}{\,\cdot\,}{})\) for every \(e\in E(F)\) is \(m-1\). This implies that the Lipschitz constant of \(\phi(\ifblank{}{\,\cdot\,}{})(x,y)\) with respect to \(\nrm*{\square}{}\) is \(m(m-1)\). Therefore, for \(b\) as in equation 56 , we have \[\begin{align} \bracket*{\lvert}{\rvert}{b(z,W_1)(x,y) - b(z,W_2)(x,y)} &= \bracket*{\lvert}{\rvert}{\phi_{H_F}(W_1)(x,y) - \phi_{H_F}(W_1)(x,y)}\nonumber\\ &\leq m(m-1)\nrm*{\square}{W_1-W_2}. \end{align}\] Therefore \(b\) (as in equation 56 ) satisfies Assumption 6 with \(\kappa_\square= m(m-1)\).

5.2 Quadratic functions of homomorphism density↩︎

More generally, let \(k\in \mathbb{N}\) and let \(\Set*{F^{1}, \ldots, F^{k}}\) be a family of finite simple graphs. Let \(c_1, \ldots, c_k\in [0, 1]\) be fixed constants. Define a function \(R\colon\mathcal{W}\to \mathbb{R}\) as \[R(W) \mathrel{\vcenter{:}}= \frac{1}{2}\sum_{\alpha=1}^{k} \bracket*{(}{)}{H_{F^{\alpha}}(W)-c_{\alpha}}^2.\] Note that a lower bound on \(R\) is achieved if \(H_{F^{\alpha}}\equiv c_{\alpha}\) for all \(\alpha\in [k]\). We note that \(R\) being a sum of squares of \(k\) many functions satisfies Assumption 1([item:phi95lip]).

Moreover, let \(\phi\colon\mathcal{W}\to L^\infty\big([0,1]^{(2)}\big)\) denote the Fréchet-like derivative evaluation map of \(R\). It follows from chain-rule that \[\begin{align} \phi(W)(x, y) &= \sum_{\alpha=1}^{k}(H_{F^{\alpha}}(W)-c_{\alpha})\phi_{H_{F^{\alpha}}(W)}(W)(x, y)\;. \end{align}\]

Note that \(W\mapsto \phi_{H_{F^{\alpha}}}(W)\) satisfies Assumption 1([item:phi95lip]) with \(\kappa_{2, \alpha}=m_{\alpha}(m_{\alpha}-1)\) where \(m_{\alpha}\) is the number of edges in \(F^{\alpha}\). Further note that for any finite graph \(F\) and \(U, V\in \mathcal{W}\) we have \(\bracket*{\lvert}{\rvert}{H_{F}(U)-H_{F}(V)}\leq |E(F)|\nrm*{\square}{U-V}\leq \bracket*{\lvert}{\rvert}{E(F)}\nrm*{2}{U-V}\). A simple calculation using the fact that \(\bracket*{\lvert}{\rvert}{(H_{F^{\alpha}}(W)-c_{\alpha})}\leq 1\) for all \(W\) and that \(\nrm*{2}{\phi_{H_{F}}(W)}\leq \bracket*{\lvert}{\rvert}{E(F)}\), we obtain that \(\phi\) satisfies Assumption 1([item:phi95lip]) with \[\kappa_2\leq \sum_{\alpha=1}^{k}(m_{\alpha}^2+\kappa_{2, \alpha})\leq km^2,\] where \(m=\max_{\alpha\in [n]}m_{\alpha}\).

Similarly, for any edge \(e\) in a finite simple graph \(F\), note \(W\mapsto \mathbf{t}_{x, y}(F_{e}, W)\) is \((m-1)\)-Lipschitz in cut norm for every \((x, y)\in[0,1]^{(2)}\) and \(W\mapsto H_{F}(W)\) is \(m\)-Lipschitz in cut norm where \(m\) is the number of edges in \(F\). Using the fact that \(\nrm*{\infty}{\phi_{H_{F}}(W)}\leq m\) and \(H_{F}(W)\in [0,1]\) for every \(W\in\mathcal{W}_0\), we conclude that \(\phi(\ifblank{}{\,\cdot\,}{})(x, y)\) is \(km^2\)-Lipschitz with respect to \(\nrm*{\square}{}\) for a.e. \((x,y)\in[0,1]^{(2)}\) and hence \(\phi\) satisfies Assumption 6.

5.3 Entropy minimization with edge-triangle constraints↩︎

We conclude with the discussion of the example mentioned in the Introduction. Recall the problem of minimizing the scalar entropy \(\mathcal{E}\) over \({\widehat\mathcal{W}}_0\) with prescribed edge density \(H_{\mathrel{-}}(\ifblank{}{\,\cdot\,}{})=e \in[0,1]\) and triangle density \(H_{\triangle}(\ifblank{}{\,\cdot\,}{})=\tau\in [0,1]\) (see [63]). As mentioned in [13], in general this problem does not admit unique minimizer.

Let us consider a relaxation of this problem. Let \(\psi\colon\mathbb{R}\to \mathbb{R}\) be a non-decreasing convex function such that \(\psi'(-\log(2))\eqqcolon A>1\). Consider minimizing the function \[W\mapsto R(W)\mathrel{\vcenter{:}}= \frac{1}{2}\left((H_{\mathrel{-}}(W)-e)^2+(H_{\triangle}(W)-\tau)^2\right) + \psi(\mathcal{E}(W)).\] Since \(\psi\) is non-decreasing, minimizing \(\mathcal{E}\) is equivalent to minimizing \(\psi\circ \mathcal{E}\). On the other hand, the term \(\frac{1}{2}\left((H_{\mathrel{-}}(W)-e)^2+(H_{\triangle}(W)-\tau)^2\right)\) penalizes any deviation from the marginal constraint on the edge and triangle densities.

It follows from the previous discussion that \(W\mapsto \frac{1}{2}(H_{\mathrel{-}}(W)-e)^2+\frac{1}{2}(H_{\triangle}(W)-\tau)^2\) is \(\lambda\)-semiconvex with \(\lambda=-8\). On the other hand, \(\mathcal{E}\) is \(4\)-semiconvex and therefore \(\psi \circ \mathcal{E}\) is \(4A\)-semiconvex. In particular, if \(A>2\) then \(R\) is strongly convex and hence admits a unique minimizer and the gradient flow converges exponentially fast to the minimizer of \(R\). In this case, the gradient flow of \(R\) converges exponentially fast to the minimizer.

For instance, take \(\psi = 4\mathrm{id}\) and consider the optimization algorithm described in Definition 2. For every \(n\in\mathbb{N}\), \(X_n\in\mathcal{M}_n\), and \((i,j)\in[n]^{(2)}\), we can evaluate \(g_{n,(i,j)}(X_n;\xi)\) as \[\begin{align} g_{n,(i,j)}(X_n;\xi) &\mathrel{\vcenter{:}}= 4\log\bracket*{(}{)}{\frac{X_n(i,j)}{1-X_n(i,j)}} + \bracket*{(}{)}{X_n(i_1,i_2) - e}\\ &\qquad + \bracket*{(}{)}{X_n(i_3,i_4)X_n(i_4,i_5)X_n(i_5,i_3) - \tau}X_n(i,i_6)X_n(i_6,j), \end{align}\] where \(\xi = (i_z)_{z\in[6]} \overset{\rm i.i.d.}{\sim} \mathrm{Uni}\bracket*{(}{)}{[n]}^6\). Notice that \(\expectationdist*{\xi}{g_n(X_n;\xi)} = \nabla R_n(X_n)\), and Assumption 2 is satisfied. Theorem 1 and Theorem 5 tell us that the ?? algorithm in the absence of large noise, converges to the minimizer of \(R\) as the step size of the algorithm goes to zero, and \(n\to\infty\).

If one takes \(\psi=\mathrm{id}\) then the function \(R\) is not guaranteed to be convex. Therefore, there may be multiple minimizers of \(R\) as mentioned in [13]. Since \(R\) is not strictly convex, the gradient flow may not converge to the minimizer, however, it does converge to a stationary point with a polynomial rate.

5.4 A linear regression problem↩︎

Let \((X, Y)\in \mathbb{R}^n\times \mathbb{R}^n\) be a random vector. Consider the function \(R_n\) on \(\mathcal{M}_n^0\), the set of symmetric \(n\times n\) matrices with entries in \([0, 1]\) defined as \[\label{eq:gls} R_n(A)\mathrel{\vcenter{:}}=\frac{1}{n}\mathbb{E}\nrm*{2}{Y-n^{-1}AX}^2.\tag{58}\] The function \(R_n\) in 58 is permutation invariant if the joint distribution of \((X, Y)\) is exchangeable (i.e. for any permutation \(\tau\), the distribution of \((X^\tau, Y^{\tau})\) is the same as that of \((X, Y)\), where \((X^\tau_i, Y^\tau_i)=(X_{\tau(i)}, Y_{\tau(i)})\). The function \(R_n\) is also differentiable in the Euclidean sense. Let \(X_n\) be \(\mathcal{M}_n^0\) valued process satisfying the SDE 4 with drift function \(R_n\). We now describe the McKean-Vlasov limit of \(K(X_n)\) as \(n\to \infty\).

To this end, we first expand \(R_n\) in 58 and compute the \(\nabla R_n\). Let \(C_n, C_n'\) be \(n\times n\) matrices such that \(\Sigma(i, j) = \expectation*{X_iX_j}, \quad \Sigma'(i, j) = \expectation*{Y_iX_j}\). It follows from the exchangeability of \((X, Y)\) that \[\begin{align} C_n(i, j) &= a\delta_{i\neq j}+b\delta_{i=j}, \qquad C_n'(i, j) = c\delta_{i\neq j}+ d\delta_{i=j}\;, \end{align}\] where \(a= \mathbb{E}(X_1X_2), b= \expectation*{X_1^2}, c= \mathbb{E}(Y_1X_2), d=\expectation*{X_1Y_1}\). With this notation, we can rewrite \(R_n\) as \[\begin{align} R_n(A) &= \expectation*{Y_1^2}+ H_n(A)+ E_n(A)\;, \end{align}\] where \[\begin{align} H_n (A)&= \frac{a}{n^3}\sum_{i, j, k=1}^{n}A(i, j)A(i, k)-\frac{2c}{n^2}\sum_{i, j=1}^{n}A(i, j) =a\hom(P_3, A)-2c\hom(P_2, A),\\ E_n(A) &= \frac{(b-a)}{n^3}\nrm*{\mathrm{F}}{A}^2 - \frac{2(d-c)}{n}\hom(P_2, A)\;. \end{align}\] In particular, \(\nabla R_n(A) = \nabla H_n(A) + \nabla E_n(A)\). Since the entries of \(A\) are bounded, we also have \[\begin{align} |\nabla E_n(A)(i, j)| &\leq \frac{C}{n^3}\delta_{i\neq j}+ \frac{C}{n^2}\delta_{i=j}\, \end{align}\] for some constant \(C>0\). Therefore, \[\nrm*{2}{K\bracket*{(}{)}{n^2\nabla H_n(A)-n^2\nabla R_n(A)}} = \nrm*{2}{K\bracket*{(}{)}{n^2\nabla E_n(A)}}\leq \frac{C}{n}\to 0,\] as \(n\to \infty\). By Remark 13, the McKean-Vlasov limit of \(\bracket*{(}{)}{X_n}_{n\in\mathbb{N}}\) is the same as the McKean-Vlasov limit of the process \(\bracket*{(}{)}{Y_n}_{n\in\mathbb{N}}\) satisfying 4 with drift function \(\nabla H_n\) for all \(n\in\mathbb{N}\). Since \(H_n\) is a linear combination of homomorphism density functions and can be seen as the restriction of the function \(\mathcal{H}\colon \mathcal{W}\to \mathbb{R}\) given by \[\mathcal{H}(W) = \sigma_{Y}^2 + a \int W(x, y)W(x, z)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}x\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}y\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}z-2c \int W(x, y)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}x\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}y,\] it follows from our discussion in Section 5.1 that \(\bracket*{(}{)}{Y_n}_{n\in\mathbb{N}}\) converges to a McKean-Vlasov limit 6 and 7 with the drift \(\phi\) defined as \[\phi(W)(x, y) \mathrel{\vcenter{:}}= -D\mathcal{H}(W)(x, y) = a\int W(x, z)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}z -2c, \qquad (x,y) \in [0,1]^2\] In particular, any local minimizer must satisfy the condition \(a\int W(x, z)\@ifnextchar^{\DIfF}{ \mathop{\mathrm{\mathstrut d}} \nolimits^{} \futurelet\diffarg \let\DiffSpace\! \ifx\diffarg( \let\DiffSpace\relax \else \ifx\diffarg[ \let\DiffSpace\relax \else \ifx\diffarg\{ \let\DiffSpace\relax \fi\fi\fi\DiffSpace}z=2c\). The same method can be extended in an obvious manner to the squared norm in 58 is replaced by any even positive power.

References↩︎