Uniform-in-Time Weak Propagation-of-Chaos in Shallow Neural Networks Margalit Glasgow, Joan Bruna Abstract We consider one-hidden layer neural networks trained in the feature-learning regime using gradient descent, and relate the output of the finite-width network f ρ ^ t m f_{\hat{\rho}^{m}_{t}} to its infinite-width counterpart f ρ t MF f_{\rho_{t}^{\textsc{MF}}} , which evolves in the mean-field dynamics. While constant-time horizon bounds for ‖ f ρ t MF − f ρ ^ t m ‖ \|f_{\rho_{t}^{\textsc{MF}}}-f_{\hat{\rho}^{m}_{t}}\| may be obtained via standard Grönwall estimates, the long-time behavior of the fluctuation is a more delicate matter. Uniform-in-time bounds often rely on (local) strong convexity in the landscape or Logarithmic Sobolev inequalities present in noisy gradient dynamics. In this work, we establish non-asymptotic weak propagation-of-chaos that holds uniformly in time, obtained by exploiting instead the convergence rate of the mean-field deterministic Wasserstein-gradient-flow dynamics. Specifically, denoting by ℒ t \mathcal{L}_{t} the mean-field excess MSE loss at time t t and m m the number of neurons, under standard regularity assumptions and the condition ∫ 0 ∞ ℒ t 1 / 2 ​ 𝑑 t = O ⁡ ( log ⁡ d ) \int_{0}^{\infty}\mathcal{L}_{t}^{1/2}dt=O(\log d) , we obtain the uniform in time bound ‖ f ρ t MF − f ρ ^ t m ‖ 2 ≲ poly ​ ( d ) ​ m − min ⁡ ( 1 , c / 6 ) \|f_{\rho_{t}^{\textsc{MF}}}-f_{\hat{\rho}^{m}_{t}}\|^{2}\lesssim\text{poly}(d)m^{-\min(1,c/6)} whenever ℒ t ≲ t − c \mathcal{L}_{t}\lesssim t^{-c} . Our result holds in a noiseless setting and does not make any assumptions on the geometry of the landscape near the optimum, and extends seamlessly to other forms of discretization, including finite number of samples and time discretization. A key takeaway of our result is that whenever the convergence rate of the mean-field, population-loss dynamics is faster than t − 2 t^{-2} , we can attain a loss of ϵ \epsilon with only poly ⁡ ( d / ϵ ) \operatorname{poly}(d/\epsilon) neurons, training samples, and GD steps. 1 Introduction Feature Learning in Shallow NNs: The defining characteristic of neural networks is their ability to automatically learn useful representations out of high-dimensional data, which can then be transferred to downstream tasks. The simplest instance is given by one hidden-layer neural networks, which construct function approximations f:\mathbb{R}^{d}\to\mathbb{R} of the form f(x)=\frac{1}{m}\sum_{i=1}^{m}\sigma(w_{i}^{\top}x)\penalty\ ,\penalty\ w_{1},\ldots,w_{m}\in\mathcal{S}, (1.1) where \sigma is a non-linear activation function, and \mathcal{S}\subseteq\mathbb{R}^{d} . While ( 1.1 ) is an idealized model, far from the bleeding edge of modern architectures, its non-asymptotic learning guarantees under gradient descent remain largely open. As expected, the difficulty comes from the non-convexity of the loss in this model: \mathcal{L}(w_{1},\ldots,w_{m})=\mathbb{E}_{x,y\sim\mathcal{D}}[(f(x)-y)^{2}] . Thanks to the permutation symmetry of neurons in ( 1.1 ), the gradient-flow training dynamics admit an Eulerian description in terms of the empirical measure \hat{\rho}^{m}=\frac{1}{m}\sum_{i=1}^{m}\delta_{w_{i}}\in\mathcal{P}(\mathcal{S}) . In [ 13 , 35 , 43 , 44 ] , the resulting dynamics are shown to be a Wasserstein Gradient Flow (WGF) for the associated functional \mathcal{L}(\rho):=\mathbb{E}_{x}[(f_{\rho}(x)-y)^{2}] , where f_{\rho}(x):=\mathbb{E}_{w\sim\rho}[\sigma(w^{\top}x)] . By leveraging the convexity of this objective in \rho , global asymptotic convergence to minimizers was established under appropriate conditions [ 13 , 40 ] in the mean-field over-parametrized limit m\to\infty . 1 1 1 We remark that these results are qualitatively different from the overparameterized neural tangent kernel (NTK) limit [ 28 , 22 , 4 , 53 ] , where global convergence is also attained, but there is no feature learning. More recently, quantitative \operatorname{poly}(1/\epsilon) local convergence rates were attained for mean-field ReLU networks, under assumptions on the smoothness of the measure minimizing the loss [ 14 ] . The key question is then to understand under which conditions can one bring these mean-field convergence guarantees to a finite-width network , bypassing known negative results (eg [ 25 ] ). This naturally raises the question of stability of the above WGF dynamics to particle discretization (i.e. finite width), which is the main focus of this work. Propagation-of-Chaos, Coupling, and Gronwall’s Inequality: Given a probability measure \rho_{0}\in\mathcal{P}(\mathcal{S}) from which the neurons are initialized, the Monte-Carlo iid discretization \hat{\rho}^{m}_{0}=\frac{1}{m}\sum_{i\leq m}\delta_{w_{i}} , with w_{i}\sim\rho_{0} , satisfies \mathbb{E}_{\hat{\rho}^{m}_{0}\sim\rho_{0}^{\otimes m}}\|f_{\hat{\rho}^{m}_{0}}-f_{\rho_{0}}\|^{2}\lesssim 1/m , where here \|f\|^{2}:=\mathbb{E}_{x\sim\mathcal{D}}(f(x)^{2}) . A key question — known as the Propagation-of-Chaos (PoC) [ 48 ] — is to understand how the initial ‘chaos’ or particle independence evolves under the WGF dynamics. That is, letting \hat{\rho}^{m}_{t} denote the empirical distribution of the m particles at training time t , and \rho_{t}^{\textsc{MF}} the mean-field distribution at time t , we seek to understand how close the joint law of any k -tuple of particles from \hat{\rho}^{m}_{t} is to {\rho_{t}^{\textsc{MF}}}^{\otimes k} . More relevant to the neural network setting is the notion of weak PoC, which only focuses on the convergence of certain observables. In our case, we consider evolution of the function error \mathcal{E}(\rho_{t}^{\textsc{MF}},\hat{\rho}^{m}_{t}):=\|f_{\hat{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}}\|^{2} as a function of t and m . A standard approach to establishing PoC is to consider an appropriate coupling between the mean-field and the empirical evolution [ 35 , 34 , 19 ] . Specifically, we can decompose the error \mathcal{E}(\rho_{t}^{\textsc{MF}},\hat{\rho}^{m}_{t})\leq 2\mathcal{E}(\rho_{t}^{\textsc{MF}},\bar{\rho}^{m}_{t})+2\mathcal{E}(\bar{\rho}^{m}_{t},\hat{\rho}^{m}_{t}) in terms of an auxiliary model \bar{\rho}^{m}_{t} which first evolves along the mean-field dynamics (starting from \rho_{0} ) and then discretizes using an m -particle iid empirical measure. As a result, the first term is at the Monte-Carlo scale O(1/m) , while the second term captures the commutation error between sampling a measure and evolving it along the WGF dynamics. This commutation error can then be controlled by coupling the dynamics of \hat{\rho}^{m}_{t} and \bar{\rho}^{m}_{t} , which we describe in detail in Section 2.2 . Grönwall’s inequality is then used to establish a bound of the form \mathcal{E}(\bar{\rho}^{m}_{t},\hat{\rho}^{m}_{t})\leq\exp(Lt)O(\text{poly}(d)/m) , where L is a uniform Lipschitz bound of the gradient. Towards uniform-in-time estimates Because of the exponential dependence on t , the direct Grönwall estimate is inherently limited to short time-horizons, and leaves open the question of obtaining PoC guarantees for longer timescales. Longer timescales are important for several reasons. First, high dimensional problems often exhibit long “burn-in” times to escape saddles [ 8 , 18 , 2 , 9 ] . Second, convergence to small thresholds \epsilon may require time polynomial in 1/\epsilon , e.g. in problems with flat landscapes near the optimum [ 6 ] or when the minimizing measure lies on a continuous manifold [ 5 , 14 ] . The latter question of small- \epsilon convergence is the main motivation of this work. A common strategy to attain PoC at longer timescales is to add noise in the dynamics, leading to the so-called Mean-Field Langevin dynamics [ 27 , 38 , 15 ] . The diffusion term creates a contraction in the Wasserstein metric, quantified via a uniform logarithmic Sobolev inequality (LSI), leading to uniform-in-time propagation of chaos [ 10 , 46 , 30 , 39 ] . However, the LSI assumption often transfers the exponential dependency to the runtime [ 47 , 52 , 37 , 49 ] . In this work, we take an alternative route towards obtaining uniform weak PoC guarantees. Our approach builds from [ 24 ] , which developed a dedicated PoC analysis beginning with an ODE describing the evolution of the fluctuation \Delta_{t}\in\mathbb{R}^{m\times d} (see ( 2.7 )) which tracks the differences between the m coupled neurons in \hat{\rho}^{m}_{t} and \bar{\rho}^{m}_{t} : \frac{d}{dt}\Delta_{t}=D_{t}\odot\Delta_{t}-H_{t}\Delta_{t}+\varepsilon_{t}+O(\|\Delta_{t}\|^{2}), ( \star ) Here D_{t}(\cdot) is a non-interacting diagonal term that amplifies fluctuations whenever a neuron is visiting non-convex regions of the landscape, and H_{t} is a PSD interaction kernel that dissipates fluctuations across the neurons (see Defn. 1 ). Finally, the source term \varepsilon_{t} ‘pumps’ error at the Monte-Carlo scale O(1/\sqrt{m}) . The focus of [ 24 ] was on obtaining non-asymptotic bounds on \|\Delta_{t}\| for problems with long burn-in times that improved upon the Grönwall estimate, specifically targeting systems where the required timescale to achieve small error is O(\text{poly}(d)) , e.g. single-index models (SIMs) with large information exponent. Our Contributions: In this work, under a suitable decay of the loss in the mean field system, we attain PoC guarantees that hold uniformly in time. This allows us to transfer mean-field convergence guarantees at arbitrary convergence thresholds \epsilon to the finite-width setting. In Lemma 2 , we establish a key refinement of the linearization ( ⋆ ‣ 1 ) that further decomposes the source term \varepsilon_{t} into a term that becomes constant near convergence, and a higher-order term. We then show that under standard regularity assumptions, if S=\int_{0}^{\infty}\sqrt{\mathcal{L}_{t}}dt<\infty , the short-time Grönwall bound \exp(Lt)O(\text{poly}(d)/m) can be extended to a uniform-in- t bound. We state an informal version of this main result below. Theorem 1 (Informal version of Theorem 2 ) . Suppose S:=\int_{t=0}^{\infty}\sqrt{\mathcal{L}_{t}}dt<\infty and Assumption Regularity holds for the regularity constant C_{\text{reg}} . Then \displaystyle\|f_{\hat{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}}\|^{2}\lesssim\begin{cases}\exp(2C_{\text{reg}}S)\frac{\operatorname{poly}(C_{\text{reg}}d)}{m^{1/3}}&\text{always}\penalty\ ,\\ \exp(6C_{\text{reg}}S)\frac{\operatorname{poly}(C_{\text{reg}}dS^{\prime})}{m}&S^{\prime}:=\int_{t=0}^{\infty}t^{2}\sqrt{\mathcal{L}_{t}}dt<\infty\end{cases} (1.2) A key implication of this theorem is that whenever the mean-field dynamics has a convergence rate faster than 1/t^{2} (possibly after a burn-in time of order O(\log(d)) ), we can attain a loss of \epsilon in a network with only \text{poly}(d)/\epsilon neurons. Our proof of PoC can be viewed as a stability analysis of the mean-field dynamics, and thus our uniform-in-time result can also be extended to other sources of discretization error, beyond just finite neurons. Under the same assumptions, the formal version of this theorem gives a uniform-in-time bound that decays polynomially in the smallest of the width m , the number of training samples n , and in \eta^{-1} , the learning rate. Thus whenever the mean-field convergence rate of gradient flow on the population loss is faster than 1/t^{2} , we can attain \epsilon loss with \text{poly}(d)/\epsilon neurons, training samples, and gradient descent steps. Finally, we empirically verify our convergence rate assumption on several synthetic examples in Section 5 . We observe that in many settings, if the target measure is smooth enough, the convergence is fast enough to meet our assumption. Remark 1 . In the case that the ground truth f^{*}(x):=\mathbb{E}_{x,y\sim\mathcal{D}}[y|x] is realizable by some distribution \rho^{*} , ie. f^{*}=\mathbb{E}_{w\sim\rho^{*}}\sigma(\langle{w,\cdot\rangle}) , our setting is an instance of particle gradient descent on the kernel mean discrepancy (KMD) between \rho and \rho^{*} (also called maximum mean discrepancy) [ 5 , 14 ] , with the kernel K(w,w^{\prime}):=\mathbb{E}_{x\sim\mathcal{D}}\sigma(w^{\top}x)\sigma(w^{\prime\top}x) . Indeed, the KMD loss is \mathcal{L}(\rho):=\|\mathbb{E}_{w\sim\rho}K(w,\cdot)-\mathbb{E}_{w\sim\rho^{*}}K(w,\cdot)\|^{2}_{\mathcal{H}} , where \mathcal{H} is the RKHS associated to the kernel K . All of our results hold for the particle and time discretization of Wasserstein gradient flow for KMD, under appropriate assumptions on the kernel K (see Assumption. 1 ). Related Work General Uniform-in-Time Propagation-of-Chaos: There is a rich and developing literature on uniform-in-time propagation of chaos in general interacting particle systems. [ 20 ] establish O(1/m) weak PoC uniformly in time for weakly interacting diffusions under regularity assumptions. [ 31 ] obtain sharp uniform-in-time PoC rates for interacting diffusions with convex potentials and small torus interactions, while [ 36 ] derive time-uniform log-Sobolev inequalities as a tool for uniform propagation of chaos, including sharp marginal estimates in smooth cases; see also [ 21 , 26 ] . These results all rely on contraction mechanisms, where the noise in the dynamics plays an instrumental role. In contrast, our results exploit a different structural property (the decay of the energy functional), enabling uniform-in-time guarantees in the determinisitc setting. Mean-Field Langevin dynamics: [ 15 , 27 , 38 ] studied the effect of adding a diffusive term in the Wasserstein Gradient Flow dynamics arising from Shallow NNs; in particular, by leveraging the aforementioned log-sobolev contraction tools, [ 10 ] prove uniform-in-time propagation of chaos for mean-field Langevin dynamics under functional convexity, with bounds in Wasserstein and relative entropy. [ 45 ] prove a quantitative weak propagation-of-chaos result for mean-field gradient Langevin dynamics, with O(1/m) finite-particle discretization error uniformly over time, explicitly motivated by infinite-width two-layer neural networks; see also [ 52 , 37 , 49 , 39 ] . Most of this work on uniform-in-time PoC exists in settings where there is a unique and stable invariant measure, and the local convergence to this measure is exponentially fast. However, there are several rotatable exceptions: in [ 20 ] , weak PoC is shown for the super-critical Kumamoto model which has continuum of invariant measures, and [ 42 ] attain a uniform-in-time PoC guarantee in a singular-interaction setting where the mean-field object converges at an inversely polynomial rate. We emphasize that in the context of shallow NN feature learning, one typically needs to anneal the diffusive dynamics, leading to exponential runtime [ 49 , 52 ] . PoC under deterministic WGF: Besides the aforementioned [ 24 ] , closest to our results is [ 12 ] , which focuses on deterministic WGF in the asymptotic regime \lim_{t\to\infty}\lim_{m\to\infty}\allowbreak m\mathcal{E}(\rho_{t}^{\textsc{MF}},\hat{\rho}^{m}_{t}) , establishing uniform-in-time PoC under a similar assumption on loss decay as ours. We instead look at the more natural reverse order of the limits, which requires handling the high-order error terms in ( ⋆ ‣ 1 ); see Remark 4 . Finally, [ 16 ] studied weak uniform-in-time PoC under (deterministic) Wasserstein-Fisher-Rao dynamics for atomic targets, although with exponential dependencies in d . For finite times, several works [ 35 , 34 , 1 , 32 ] have used a Grönwall-based approach to attain non-asymptotic PoC guarantees with tight dependencies on the dimension, and have applied these to show feature learning in neural networks. Finally, propagation of chaos has been studied in several other neural network settings, for example ResNets [ 17 ] and deep transformers [ 23 , 11 ] , where in the latter the relevant particle system is the embeddings of the m tokens in the context. Notation. \mathcal{P}(\Omega) denotes the space of probability distributions over \Omega . For a vector w\in\mathbb{R}^{d} , we let \|w\| denote its 2-norm, and for a matrix M\in\mathbb{R}^{d}\times\mathbb{R}^{d} , we let \|M\| denote its operator norm. We will use lower-case letters ( f,g,h ) to denote functions in L^{2}(\mathbb{R}^{d},\mathcal{D}) . We use Greek letters ( \Delta , \xi , etc) to denote vector-valued functions \mathcal{S}\rightarrow\mathbb{R}^{d} , and upper-case letters to denote matrix-valued functions \mathcal{S}\rightarrow\mathbb{R}^{d\times d} or \mathcal{S}\times\mathcal{S}\rightarrow\mathbb{R}^{d\times d} . When \hat{\mu} is an empirical measure of the form \hat{\mu}=\frac{1}{m}\sum_{i}\delta_{w_{i}} , we will use the shorthand \Lambda(i)=\Lambda(w_{i}) , and denote \mathbb{E}_{i}\Lambda(i):=\frac{1}{m}\sum_{i}\Lambda(w_{i}) . In general, we will denote dot products and norms without explicitly specifying inner product we are using, since throughout, the Hilbert space in which objects lie should be clear. Eg. for H\in L^{2}(\mathcal{S}\times\mathcal{S},\mu^{2},\mathbb{R}^{d\times d}) , D\in L^{2}(\mathcal{S},\mu,\mathbb{R}^{d\times d}) and \Lambda\in L^{2}(\mathcal{S},\mu,\mathbb{R}^{d}) , we use H\Lambda(w):=\mathbb{E}_{w^{\prime}\sim\mu}H(w,w^{\prime})\Lambda(w^{\prime}) , and (D\Lambda)(w):=D\odot\Lambda(w)=D(w)\Lambda(w) . Similarly, we let \|\Lambda\|_{p}:=\mathopen{}\mathclose{{\left(\mathbb{E}_{w\sim\mu}\|\Lambda(w)\|^{p}}}\right)^{1/p} , with the default that p=2 if p is omitted. Further, we let \|D\| and \|H\| denote the operator norms \|D\|:=\sup_{w\in\mathcal{S}}\|D(w)\| , and \|H\|:=\sup_{\|\Lambda\|\leq 1}\|H\Lambda\| . Occasionally, we will write \|V\|_{p\rightarrow q} to denote \sup_{\|X\|_{p}\leq 1}\|VX\|_{q} . Typically the relevant measure will be the measure from which the network is initialized, \rho_{0} . When one or more objects in the inner product is defined only on \{w_{i}\}_{i\in[m]} (or equivalently on [m] ), then the relevant measure will be \bar{\rho}^{m}_{t} (or equivalently \operatorname{unif}([m]) ). Acknowledgments: We thank Andrea Agazzi, Shi Chen, Gerard Ben Arous and Philippe Rigollet for stimulating discussions and helpful feedback during the completion of this work. JB acknowledges the generous support of Flatiron Institute, which hosted his sabbatical leave. MG’s work is supported by the NSF under award 2402314. 2 Setting and Preliminaries 2.1 Projected Gradient Dynamics on Neural Networks Consider a neural network to be parameterized by some distribution \rho\in\mathcal{P}(\mathcal{S}) , such that \displaystyle f_{\rho}(x):=\mathbb{E}_{w\sim\rho}\sigma(x;w), for some activation function \sigma . We will be primarily interested in the case where \mathcal{S}=\mathbb{R}^{d} or \mathbb{S}^{d-1} . A supervised regression problem is parameterized by an initial distribution for the network weights, \rho_{0} , and a distribution \mathcal{D} over datapoints (x,y)\in\mathbb{R}^{d}\times\mathbb{R} . Given (\rho_{0},\mathcal{D}) , we define f^{*}(x)=\mathbb{E}_{\mathcal{D}}[y|x] . We will train the neural network to minimize the excess squared loss \displaystyle\mathcal{L}_{\mathcal{D}}(\rho):=\mathbb{E}_{(x,y)\sim\mathcal{D}}(f_{\rho}(x)-y)^{2}-\mathbb{E}_{(x,y)\sim\mathcal{D}}(f^{*}(x)-y)^{2}\penalty\ . (2.1) We study the (projected) gradient flow dynamics of \rho induced by moving each particle w\sim\rho in the (negative) direction of the gradient of the loss \mathcal{L}_{\mathcal{D}}(\rho) , and then optionally projecting the particle back to \mathcal{S} . Let P_{w} denote the orthogonal projection on the tangent space T_{w}\mathcal{S} . Thus when \mathcal{S}=\mathbb{S}^{d-1} , P_{w}=I-ww^{\top} ; when \mathcal{S}=\mathbb{R}^{d} , we have P_{w}=I . In our two settings of interest, we have the dynamics \frac{d}{dt}w=P_{w}\nu_{\mathcal{D}}(w,\rho) , where: \displaystyle\nu_{\mathcal{D}}(w,\rho):=\nabla_{w}F_{\mathcal{D}}(w)-\nabla_{w}\mathbb{E}_{w^{\prime}\sim\rho}K_{\mathcal{D}}(w,w^{\prime}), (2.2) and \displaystyle F_{\mathcal{D}}(w):=\mathbb{E}_{(x,y)\sim\mathcal{D}}y\sigma(x;w)\qquad\text{and}\qquad K_{\mathcal{D}}(w,w^{\prime}):=\mathbb{E}_{(x,y)\sim\mathcal{D}}\sigma(x;w)\sigma(x;w^{\prime}). (2.3) When the data distribution \mathcal{D} is clear from context, we will often abbreviate and drop the \mathcal{D} subscript on \nu_{\mathcal{D}}(w,\rho) , K_{\mathcal{D}} , F_{\mathcal{D}} . Further, whenever an expectation over x appears in this paper without explicit distribution, it should be interpreted being drawn from the x -marginal of \mathcal{D} . 2.2 Coupling between Mean Field and Finite-Neuron Dynamics We will study the evolution of two different learning dynamics in this paper. Infinite-width, infinite-data mean-field gradient flow dynamics. We denote the mean-field distribution at time t by \rho_{t}^{\textsc{MF}}\in\mathcal{P}(\mathcal{S}) , where we initialize \rho_{0}^{\textsc{MF}}=\rho_{0} . Each particle w\in\mathcal{S} in the mean-field dynamics evolves according to the infinite-data velocity \nu(w,\rho_{t}^{\textsc{MF}})\in T_{w}\mathcal{S} . \xi_{t}(w)\in\mathcal{S} denotes the characteristic of a particle initialized at w and evolved under the mean-field dynamics, equivalently expressed in Eulerian form as a continuity equation: \displaystyle\textstyle\frac{d}{dt}\xi_{t}(w) \displaystyle=\nu(\xi_{t}(w),\rho_{t}^{\textsc{MF}})\penalty\ ,\qquad\xi_{0}(w)=w\penalty\ , (2.4) \displaystyle\partial_{t}\rho_{t}^{\textsc{MF}} \displaystyle=-\nabla\cdot(\nu(w,\rho_{t}^{\textsc{MF}})\rho_{t}^{\textsc{MF}}). (2.5) Finite-width, finite-data GD dynamics. Let \hat{\rho}^{m}_{t} denote the empirical measure defined by m neurons under the (projected) gradient descent induced by the empirical loss from n training samples. Let \hat{\mathcal{D}} denote the empirical distribution of the n training samples. We initialize \hat{\rho}^{m}_{0}=\frac{1}{m}\sum_{i=1}^{m}\delta_{w_{i}} , where w_{i}\sim\rho_{0} i.i.d. for each i\in[m] . Each particle in the finite dynamics evolves according to the empirical velocity \nu_{\hat{\mathcal{D}}} evaluated at discrete time steps which are multiples of the step size, \eta . This defines a delay differential equation in \mathcal{S}^{\otimes m} , whose characteristics are now denoted by \hat{\xi}_{t}(w_{i}) , and solve \displaystyle\textstyle\frac{d}{dt}\hat{\xi}_{t}(w_{i})=\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})\qquad\hat{\xi}_{0}(w_{i})=w_{i}\penalty\ ,\penalty\ i\in[m]\penalty\ ,\qquad t_{\eta}:=\eta\lfloor{t/\eta}\rfloor. (2.6) We will study the setting where the training data are drawn i.i.d. from a sub-Gaussian distribution with sub-Gaussian label noise (See Assumption Regularity , 2 ). Coupling the dynamics. Let \bar{\rho}^{m}_{t} be the distribution initialized at \hat{\rho}^{m}_{0} , but that evolves according to the dynamics \nu(\cdot,\rho_{t}^{\textsc{MF}}) . That is, \bar{\rho}^{m}_{t}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\xi_{t}(w_{i})} . Note that \bar{\rho}^{m}_{t} is equivalent in distribution to a random sample of m particles drawn iid from \rho_{t}^{\textsc{MF}} . Now let the coupling error at neuron w_{i} be \displaystyle\Delta_{t}(i):=\hat{\xi}_{t}(w_{i})-\xi_{t}(w_{i})\in\mathbb{R}^{d},\penalty\ i\in[m]\penalty\ , (2.7) such that \Delta_{0}(i)=0 for all i . 2.3 Description of the Dynamics of \Delta_{t} As described in ( ⋆ ‣ 1 ), [ 24 , Lemma 5] gave a first-order approximation to the ODE describing the dynamics of \Delta_{t} , with a source term on the scale 1/\sqrt{m} . In Lemma 2 below, we obtain a refinement of this result, which improves over [ 24 , Lemma 5] in two ways. First, under appropriate regularity assumptions, we extend beyond the spherical setting they studied and to the case where \mathcal{S}=\mathbb{R}^{d} . Second, we refine the source term by separating it into two terms: (1) a term on the scale 1/\sqrt{m} that becomes constant convergence, and (2) a smaller source term on the scale 1/m . This refinement of the source term is key to attaining the 1/m rate in our uniform-in-time guarantee. Before stating Lemma 2 , we review from [ 24 ] the two key quantities governing the dynamics of \Delta_{t} : a self-interaction term, and an interaction term. The self-interaction term is described by what we call the local Hessian, the derivative of a particle’s velocity with respect to that particle’s position. The part of the dynamics driven by the other \Delta_{t}(j) is described by what we term the interaction Hessian, the (rescaled) derivative of a particle’s velocity with respect to the other particles’ position. Definition 1 (Local and Interaction Hessians; cf. [ 24 ] ) . We define the local Hessian D_{t}:\mathcal{S}\to\{\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}\} and the interaction Hessian H_{t}:\mathcal{S}\times\mathcal{S}\rightarrow\{\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}\} by \displaystyle D_{t}(w) \displaystyle:=\nabla_{\xi_{t}(w)}\nu(\xi_{t}(w),\rho_{t}^{\textsc{MF}})P_{\xi_{t}(w)} (2.8) \displaystyle H_{t}(w,w^{\prime}) \displaystyle:=P_{\xi_{t}(w)}\nabla_{\xi_{t}(w^{\prime})}\nabla_{\xi_{t}(w)}K(\xi_{t}(w),\xi_{t}(w^{\prime}))P_{\xi_{t}(w^{\prime})} (2.9) We will also use the abbreviated notation D_{t}(i):=D_{t}(w_{i}) , and H_{t}(i,j):=H_{t}(w_{i},w_{j}) . Note that by construction we have that H_{t} is a PSD operator. We make the following basic regularity assumptions on the activation function and the data. Let \sigma^{(j)} denote the j th derivative of \sigma . Assumption Regularity (Regularity Assumptions) . (i) For a constant C_{\text{reg}} , the activation \sigma satisfies: • If \mathcal{S}=\mathbb{R}^{d} : \sigma^{\prime} and \sigma^{\prime\prime} have total variation at most C_{\text{reg}} and we have the tail variation bound for \sigma^{\prime} : \int_{s=\pm t}^{\pm\infty}|\sigma^{\prime\prime}(s)|ds\leq\frac{C_{\text{reg}}}{1+t^{1/(C_{\text{reg}}d)}} . Also, |\sigma(0)|,|\sigma^{\prime}(0)|,|\sigma^{\prime\prime}(0)|,|\sigma^{\prime\prime\prime}|_{\infty}\leq C_{\text{reg}} . • If \mathcal{S}=\mathbb{S}^{d-1} : for any subgaussian variable X , for j=0,1,2,3 , (\mathbb{E}_{X}|\sigma^{(j)}(X)|^{4})^{\frac{1}{4}}\leq C_{\text{reg}} . (ii) The distribution \mathcal{D} on the data covariates is C_{\text{reg}} -subgaussian, \mathbb{E}_{x\sim\mathcal{D}}\|x\|^{2}=d , and \mathbb{E}_{x,y\sim\mathcal{D}}y^{2}\leq C_{\text{reg}} . (iii) The initialization \rho_{0} is supported on the bounded set \mathcal{S}\cap\{w:\|w\|\leq C_{\text{reg}}\} . Note that in the case where neurons are constrained to the sphere, 1 is quite tame: it suffices to have sufficiently fast decay in the coefficients in the polynomial expansion of \sigma . In the case where neurons can grow arbitrarily, 1 implies that \sigma is smooth and grows no faster than linearly. This includes for example a smoothed ReLU function. Remark 2 . For user-friendliness, we have stated our assumptions as above. We remark however that in all our results, 1 and 2 can be replaced by the more general Assumptions 1 , 2 , 3 in Appendix A , which are implied by 1 and 2 (up to a constant). We believe with some modifications, our proof could be adapted to ReLU activations when \mathcal{S}=\mathbb{S}^{d-1} ; however when the neurons can get arbitrarily close to 0 , even for Gaussian data, the gradients become too unstable for our techniques to work. We introduce the control parameters \displaystyle\epsilon_{m}:=\frac{C_{\text{reg}}^{6}\sqrt{d}\log(dm)}{\sqrt{m}},\qquad\epsilon_{n}:=\frac{C_{\text{reg}}^{5}\sqrt{d}\log(dn)}{\sqrt{n}},\qquad\epsilon_{\eta}=2C_{\text{reg}}^{2}(\eta+\eta^{2}). We will show in Lemma 15 that with high probability, the error \|\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})\| due to sampling only m neurons is uniformly (over i and t ) bounded (roughly) by \epsilon_{m} . Similarly, we will show in Lemma 16 that the error \|\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})\| due to using the empirical data distribution \mathcal{D} is uniformly bounded by \epsilon_{n} . Recall that we have defined K(w,w^{\prime}):=\mathbb{E}_{x}\sigma(x^{\top}w)\sigma(x^{\top}w^{\prime}) , and now define \displaystyle K_{t}(w_{i},w_{j}) \displaystyle=K_{t}(i,j):=K(\xi_{t}(w_{i}),\xi_{t}(w_{j})). (2.10) Let \nabla K_{t}(w,w^{\prime}):=P_{\xi_{t}(w)}\nabla_{\xi_{t}(w)}K(\xi_{t}(w),\xi_{t}(w^{\prime})) and let \kappa_{t} be the subgaussian norm of \|w\| for w\sim\rho_{t}^{\textsc{MF}} . Lemma 2 (Parameter-Space Error Dynamics) . Suppose Assumption Regularity holds. With probability 1-\min(m,n)^{-\Theta(1)} , for all t<\infty and i\in[m] , \frac{d}{dt}\Delta_{t}(i)=D_{t}(i)\Delta_{t}(i)-\mathbb{E}_{j\sim[m]}H_{t}(i,j)\Delta_{t}(j)+\bm{\beta}_{t}(i)+{\bm{\epsilon}_{t}(i)}, where \displaystyle\bm{\beta}_{t}(i):=P_{\xi_{t}(w_{i})}\mathopen{}\mathclose{{\left(\mathbb{E}_{j\sim[m]}\nabla K_{t}(i,j)-\mathbb{E}_{w\sim\rho_{0}}\nabla K_{t}(w_{i},w)}}\right), (2.11) and \|{\bm{\epsilon}_{t}}(i)\|\leq\epsilon_{n}+\kappa_{t}^{2}\epsilon_{\eta}+2\kappa_{t}\log(t+1)\epsilon_{m}+2C_{\text{reg}}\mathopen{}\mathclose{{\left(\|\Delta_{t}(i)\|^{2}+\mathbb{E}_{j}\|\Delta_{j}\|^{2}}}\right) , \|\bm{\beta}_{t}(i)\|\leq\epsilon_{m}\log(t+1) . Note that on constant timescales and with \epsilon_{n}=\epsilon_{\eta}=0 , the {\bm{\epsilon}_{t}}(i) term is on the scale \epsilon_{m}\|\Delta_{t}(i)\|\approx\epsilon_{m}^{2} . We will show in Lemma 9 that the \bm{\beta}_{t}(i) term converges to a constant term \bm{\beta}_{\infty}(i) , with a difference on the scale \epsilon_{m}\|\xi_{t}(w_{i})-\xi_{\infty}(w_{i})\| which dissipates as the network converges. Because this constant term \bm{\beta}_{\infty}(i) is easier to handle, this improves over the naive bound \|\bm{\beta}_{t}(i)+\bm{\epsilon}_{t}(i)\|\lessapprox\epsilon_{m} . We prove Lemma 2 by decomposing \frac{d}{dt}\Delta_{t}(i)\!=\!-\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})\!+\!\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) into five differences (see Figure 3 ), and separating the first order terms (in \Delta_{t} ) from higher order terms in these differences. We defer the proof of Lemma 2 to Appendix A . 3 Technical Approach The first key idea in our proof of Theorem 1 — which has been previously used in [ 12 ] — is the observation that as the loss decreases, D_{t} becomes small, and thus the dynamics of \Delta_{t} in Lemma 2 become nearly dissipative. Precisely, we have the following lemma, which is proved via a simple application of Cauchy-Schwartz in Appendix 4.2 . Lemma 3 (See Lemma 8 for full statement) . For all w\in\mathcal{S} , we have \|D_{t}(w)\|\leq C_{\text{reg}}\mathopen{}\mathclose{{\left(\mathcal{L}(\rho_{t}^{\textsc{MF}})}}\right)^{1/2}. Recall from Lemma 2 that — omitting higher order terms and any error form \epsilon_{n} and \epsilon_{\eta} — we have \displaystyle\frac{d}{dt}\Delta_{t}=D_{t}\odot\Delta_{t}-H_{t}\Delta_{t}+\bm{e}_{t}, (3.1) where \|\bm{e}_{t}\|=\|\bm{\epsilon}_{t}+\bm{\beta}_{t}\|\lessapprox\epsilon_{m} . Since H_{t} is PSD, we have \lambda_{\max}(D_{t}-H_{t})\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho_{t}^{\textsc{MF}})} . Thus if S:=\int_{s=0}^{\infty}\sqrt{\mathcal{L}(\rho_{s}^{\textsc{MF}})}<\infty , by Gronwall’s inequality, we attain that for all t , \displaystyle\|\Delta_{t}\|\leq\exp\mathopen{}\mathclose{{\left(C_{\text{reg}}S}}\right)\int_{s=0}^{t}\|\bm{e}_{s}\|ds\leq\exp\mathopen{}\mathclose{{\left(C_{\text{reg}}S}}\right)t\epsilon_{m}\approx\frac{t}{\sqrt{m}}. (3.2) Unfortunately, because of the linear dependence on t , this approach does not suffice to give a uniform bound on \|\Delta_{t}\| . However, our refined dynamics in Lemma 2 give more control over the error term \bm{e}_{t} . Up to higher order terms, we have that \bm{e}_{t}=\bm{\beta}_{t}\xrightarrow[t\to\infty]{}\bm{\beta}_{\infty} , and \bm{\beta}_{t}^{\top}H^{\dagger}_{t}\bm{\beta}_{t}\lesssim\epsilon_{m}^{2} . To see this, observe that with V_{t}(x,w):=\sigma^{\prime}(\xi_{t}(w)^{\top}x)x , we have that H_{t}=V_{t}^{\top}V_{t} , and \bm{\beta}_{t}=V_{t}^{\top}g_{t} , where matrix/vector multiplications are over L_{2}(\mathcal{D}) , and g_{t}=f_{\bar{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}} . Since \bar{\rho}^{m}_{t} is an i.i.d. sample from \rho_{t}^{\textsc{MF}} , we have that \|g_{t}\|\lesssim 1/\sqrt{m} , and thus \bm{\beta}_{t}^{\top}H^{\dagger}_{t}\bm{\beta}_{t}=g_{t}V_{t}(V_{t}^{\top}V_{t})^{\dagger}V_{t}^{\top}g_{t}\leq\|g_{t}\|^{2}\lesssim 1/m . Nevertheless, one can see from the following example that even if D_{t}=0 , and \bm{e}_{t}\equiv\bm{e} and H_{t}\equiv H are constant (which is the case at convergence), and \bm{e}^{\top}H^{\dagger}\bm{e}\leq\epsilon^{2} it is still possible that \|\Delta_{t}\|\rightarrow\infty . Example 1 (Part 1) . Consider the system \frac{d}{dt}X_{t}=-HX_{t}+\bm{e} with X_{0}=0 . Then for any M , there exists a PSD H with \|H\|\leq 1 and an \bm{e} with \bm{e}^{\top}H^{\dagger}\bm{e}\leq\epsilon^{2} such that for some t , \|X_{t}\|\geq M . Proof. Let H=\sum_{i=1}^{B}\lambda_{i}v_{i}v_{i}^{\top} with \|v_{i}\|=1 and \bm{e}:=\sum_{i}v_{i}e_{i} , such that we have the closed form \displaystyle X_{t}=\int_{s=0}^{t}\exp(-(t-s)H)\bm{e}=\sum_{i=1}^{B}\int_{s=0}^{t}\exp(-\lambda_{i}(t-s))v_{i}e_{i} (3.3) Choosing \lambda_{1}>0 , e_{1}=\sqrt{\lambda_{1}}\epsilon , and the rest of the e_{i}=0 , we have \bm{e}^{\top}H^{\dagger}\bm{e}=\epsilon^{2} and \displaystyle X_{t}=\int_{s=0}^{t}\exp(-(t-s)\lambda_{1})v_{1}e_{1}=\frac{1}{\lambda_{1}}(1-\exp(-t\lambda_{1}))v_{1}\sqrt{\lambda_{1}}\epsilon (3.4) Choosing \lambda_{1}=\frac{\epsilon^{2}}{4M^{2}} , t=\frac{4M^{2}}{\epsilon^{2}} yields \|X_{t}\|=2M(1-\exp(-1))\geq M . ∎ This obstacle suggests that a strong form of propagation of chaos – in which the Wasserstein distance between \rho_{t}^{\textsc{MF}} and \hat{\rho}^{m}_{t} is bounded uniformly in time, may not be attainable when the spectrum of H_{\infty} decays to 0 . In settings where \rho^{*} is non-atomic and thus the landscape is not locally strongly convex, we in fact expect that H_{\infty} will have an infinite spectrum with a positive sequence converging to 0 . 2 2 2 H_{\infty} necessarily has an infinite spectrum whenever \sigma is non-polynomial, and \rho_{\infty}^{\textsc{MF}} and \mathcal{D} have non-atomic support. Further, it is a standard fact that compact PSD operators can only have accumulation points in the spectrum at 0 . Even in the ERM setting, where the data distribution is atomic, the lowest non-zero eigenvalue of H_{\infty} will typically decay in n . Fortunately, this behavior does not present an obstacle when we consider the weak propagation of chaos, namely \|f_{\rho_{t}^{\textsc{MF}}}-f_{\hat{\rho}^{m}_{t}}\|^{2} . We will need the following lemma. Lemma 4 (cf. Lemma 14 in [ 24 ] ) . With probability 1-m^{-\Theta(1)} over \hat{\rho}^{m}_{0} , for any t\in[0,\infty) we have \displaystyle\mathbb{E}_{x}(f_{\rho_{t}^{\textsc{MF}}}(x)-f_{\hat{\rho}^{m}_{t}}(x))^{2} \displaystyle\leq 2\Delta_{t}^{\top}H_{t}\Delta_{t}+\frac{\kappa_{t}^{4}\log(m)}{m}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{2}\|\Delta_{t}\|_{4}^{4}}}\right), (3.5) where \kappa_{t} is the subguassian norm of \|w\| for w\sim\rho_{t}^{\textsc{MF}} . Using this lemma — up to higher order terms — it suffices to bound \Delta_{t}^{\top}H_{t}\Delta_{t} uniformly in t . We return to the example above to give intuition for why this is possible when \bm{e}_{t} is constant. Example 2 (Part 2) . In any system \frac{d}{dt}X_{t}=-HX_{t}+\bm{e} with X_{0}=0 , where \|\bm{e}^{\top}H^{-1}\bm{e}\|\leq\epsilon^{2} and H is PSD, for any t<\infty , we have X_{t}^{\top}HX_{t}\leq\epsilon^{2} . Proof. Plugging in ( 3.3 ), we have \displaystyle X_{t}^{\top}HX_{t}=\sum_{i=1}^{B}\lambda_{i}e_{i}^{2}\mathopen{}\mathclose{{\left(\int_{s=0}^{t}\exp(-\lambda_{i}(t-s))}}\right)^{2}=\sum_{i=1}^{B}\lambda_{i}e_{i}^{2}\mathopen{}\mathclose{{\left(\frac{1}{\lambda_{i}}\mathopen{}\mathclose{{\left(1-\exp(-t\lambda_{i})^{2}}}\right)}}\right)\leq\sum_{i}\frac{1}{\lambda_{i}}e_{i}^{2}\leq\epsilon^{2}. (3.6) ∎ While the idea above is promising, bounding \Delta_{t}^{\top}H_{t}\Delta_{t} uniformly in time is still challenging due to the higher order terms that appear in Lemma 4 , which we expect will be unbounded as t\rightarrow\infty . Fortunately, if the loss decays fast enough (faster than t^{-6} ), we can show these terms are small enough up to some t^{*}_{m}\approx m^{1/6} , when the loss \mathcal{L}(\rho_{t}^{\textsc{MF}}) is on order \frac{1}{m} . If we can show that the error \|f_{\hat{\rho}_{t^{*}_{m}}^{m}}-f_{\rho_{t^{*}_{m}}^{\textsc{MF}}}\|^{2}\approx\frac{1}{m} at that time, then using the fact that that the loss \mathcal{L}(\hat{\rho}^{m}_{t}) is non-increasing, we have that for any t\geq t^{*}_{m} , \displaystyle\|f_{\hat{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}}\| \displaystyle\leq\|f_{\hat{\rho}^{m}_{t}}-f^{*}\|+\|f^{*}-f_{\rho_{t}^{\textsc{MF}}}\|\leq\sqrt{\mathcal{L}(\hat{\rho}_{t^{*}_{m}}^{m})}+\sqrt{\mathcal{L}(\rho_{t^{*}_{m}}^{\textsc{MF}})} (3.7) \displaystyle\leq\|f_{\hat{\rho}_{t^{*}_{m}}^{m}}-f_{\rho_{t^{*}_{m}}^{\textsc{MF}}}\|+2\sqrt{\mathcal{L}(\rho_{t^{*}_{m}}^{\textsc{MF}})}\approx 1/\sqrt{m}. (3.8) If the loss decays faster than t^{-2} but slower than t^{-6} , we can perform a similar argument, but the final uniform bound on \|f_{\hat{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}}\|^{2} will be on the order of \mathcal{L}(\rho_{t^{*}_{m}}^{\textsc{MF}}) , for t^{*}_{m}\approx m^{1/6} . We now have all the ideas in place for proving Theorem 1 . It remains to handle the higher order terms, and the fact that H_{t} and \bm{e}_{t} are not actually constant. Our key idea here is to bound the objects \|\Delta_{t}\| , and \|\Delta_{t}\|_{\infty} , and \|f_{\hat{\rho}^{m}_{t}}-f_{\rho_{t}^{\textsc{MF}}}\| through a careful inductive argument. In the following section, we state the formal version of our main theorem and its proof. 4 Formal Statement and Proof of Main Result on Uniform in Time PoC 4.1 Formal Theorem Statement Before stating the formal version of our main theorem, we remark that whenever f^{*} is realizable by a distribution \rho^{*}\in\mathcal{P}(\mathcal{S}) , i.e., f^{*}(x)=\mathbb{E}_{w\sim\rho^{*}}\sigma(w^{\top}x) , our neural network loss is equivalent to that of a Kernel Mean Discrepancy problem [ 14 , 5 ] with the kernel K(w,w^{\prime})=\mathbb{E}_{x\sim\mathcal{D}}\sigma(w^{\top}x)\sigma({w^{\prime}}^{\top}x) . Let us first verify that under our loss decay assumptions, we are indeed in this realizable setting. Let m_{\rho}:=\mathbb{E}_{w^{\prime}\sim\rho}K(\cdot,w^{\prime}) , and let \mathcal{H} be the RKHS generated by the kernel K , with inner product \langle{,}\rangle_{\mathcal{H}} . Lemma 5 (Reduction to Kernel Mean Discrepancy) . Suppose that \int_{0}^{\infty}\sqrt{\mathcal{L}_{t}}dt<\infty and Assm. Regularity or Assm. 1 hold so that the characteristics in ( 2.4 ) are well-posed. Then the characteristics admit a limit \xi_{t}(w)\to\xi_{\infty}(w) \rho_{0} -a.e as t\to\infty . As a result, defining \rho^{*}:=(\xi_{\infty})_{\#}\rho_{0} , we have \rho_{t}\to\rho^{*} in W_{2} , and f^{*}=f_{\rho^{*}} in L^{2}(\mathcal{D}) . Finally, we have \|f_{\rho}-f_{\rho^{\prime}}\|^{2}=\|m_{\rho}-m_{\rho^{\prime}}\|^{2}_{\mathcal{H}} , and in particular, \mathcal{L}(\rho):=\|m_{\rho}-m_{\rho^{*}}\|^{2}_{\mathcal{H}} . Proof. Recall the continuity equation from ( 2.4 ). Define \mathcal{B}(t):=\|\nu(\cdot,\rho_{t}^{\textsc{MF}})\|_{L^{2}(\rho_{t}^{\textsc{MF}})} . Since \nu(w,\rho_{t}^{\textsc{MF}}) is the gradient of the first-variation of \mathcal{L} , we have the energy dissipation \frac{d}{dt}\mathcal{L}_{t}=-2\mathcal{B}(t)^{2}\penalty\ , and thus \int_{a}^{b}\mathcal{B}(t)^{2}dt=\frac{1}{2}(\mathcal{L}_{a}-\mathcal{L}_{b}) for any a1 3 3 3 using a dyadic argument to control \int_{T}^{\infty}B(t)dt from \sum_{k}T^{1/2}2^{k/2}\mathopen{}\mathclose{{\left(\int_{2^{k}T}^{2^{k+1}T}B(t)^{2}dt}}\right)^{1/2}\lesssim T^{(1-c)/2} , which is weaker than what we require in Theorem 2 . We now state the full version of Theorem 1 . Instead of assuming Assumption Regularity , we assume Assumptions 1 , 2 , and 3 . In Appendix A , we show that up to a polynomial factor in C_{\text{reg}} , Assumption Regularity implies these three assumptions, and that Lemma 2 holds under these three assumptions (See Lemmas 19 and 20 ). Let \bar{\mathcal{S}} denote the convex hull of the space \mathcal{S} . Thus, in the case where \mathcal{S}=\mathbb{S}^{d-1} , we have \bar{\mathcal{S}}=\{w\in\mathbb{R}^{d}:\|w\|\leq 1\} , and when \mathcal{S}=\mathbb{R}^{d} , then \bar{\mathcal{S}}=\mathbb{R}^{d} . Assumption 1 (Kernel Smoothness) . For some C_{\text{reg}}\geq 1 , the kernel K satisfies for all w,w^{\prime}\in\bar{\mathcal{S}} : \displaystyle K(w,w) \displaystyle\leq C_{\text{reg}}(1+\|w\|)^{2}\penalty\ , (4.13) \displaystyle\mathopen{}\mathclose{{\left\|\nabla_{w}K(w,w^{\prime})}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}K(w,w^{\prime})}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{3}_{w}K(w,w^{\prime})}}\right\| \displaystyle\leq C_{\text{reg}}/11(1+\|w^{\prime}\|)\penalty\ , (4.14) \displaystyle\mathopen{}\mathclose{{\left\|\nabla_{w}\nabla_{w^{\prime}}K(w,w^{\prime})}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}\nabla_{w^{\prime}}K(w,w^{\prime})}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}\nabla^{2}_{w^{\prime}}K(w,w^{\prime})}}\right\| \displaystyle\leq C_{\text{reg}}/11. (4.15) Further, \displaystyle\mathopen{}\mathclose{{\left\|\nabla_{w}F(w)}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}F(w)}}\right\|,\mathopen{}\mathclose{{\left\|\nabla^{3}_{w}F(w)}}\right\|\leq C_{\text{reg}}/11, (4.16) or alternatively, for the case of kernel mean discrepancy, \|w\| for w\sim\rho^{*} is subgaussian. It is straightforward to show using Holder’s inequality that Assumption 1 holds under Assumption Regularity , up to a polynomial factor in C_{\text{reg}} . As an example, for \nabla_{w}^{3}K(w,w^{\prime}) , we have \displaystyle\frac{1}{1+\|w^{\prime}\|}\mathopen{}\mathclose{{\left\|\nabla^{3}_{w}K^{\prime}(w,w^{\prime})}}\right\|_{op} \displaystyle\leq\frac{1}{1+\|w^{\prime}\|}\sup_{v_{1},v_{2},v_{3}\in\mathbb{S}^{d-1}}\mathbb{E}_{x}\sigma^{\prime\prime\prime}(w^{\top}x)\sigma(w^{\prime\top}x)(v_{1}^{\top}x)(v_{2}^{\top}x)(v_{3}^{\top}x) (4.17) \displaystyle\leq\sup_{z,z^{\prime}\in\bar{\mathcal{S}}}\mathopen{}\mathclose{{\left(\mathbb{E}_{x}|\sigma^{\prime\prime\prime}(z^{\top}x)|^{4}}}\right)^{1/4}\frac{\mathopen{}\mathclose{{\left(\mathbb{E}_{x}|\sigma(z^{\prime\top}x)|^{4}}}\right)^{1/4}}{1+\|z^{\prime}\|}\sup_{v\in\mathbb{S}^{d-1}}\mathopen{}\mathclose{{\left(\mathbb{E}_{x}|(v^{\top}x)|^{6}}}\right)^{1/2} (4.18) \displaystyle\leq O(C_{\text{reg}}^{5}). (4.19) Assumption 2 (UC over empirical data sample) . Let \displaystyle\mathcal{F} \displaystyle:=\mathopen{}\mathclose{{\left\{f_{w,w^{\prime},v}((x,y)):=\frac{1}{1+\|w^{\prime}\|}(y-\sigma(w^{\prime\top}x))\sigma^{\prime}(w^{\top}x)(x^{\top}v):w,w^{\prime}\in\mathcal{S},v\in\mathbb{S}^{d-1}}}\right\}\penalty\ , (4.20) \displaystyle\mathcal{F}^{\prime} \displaystyle:=\mathopen{}\mathclose{{\left\{f_{w,w^{\prime}}((x,y)):=\frac{1}{(1+\|w\|)(1+\|w^{\prime}\|)}(y-\sigma(w^{\top}x))(y-\sigma(w^{\prime\top}x)):w,w^{\prime}\in\mathcal{S}}}\right\}\penalty\ . (4.21) We have the following uniform convergence bounds with probability 1-n^{-\Theta(1)} over x_{i},y_{i}\sim\mathcal{D} i.i.d., \displaystyle\sup_{f=f_{w,w^{\prime},v}\in\mathcal{F}}\mathopen{}\mathclose{{\left|\mathbb{E}_{x\sim\mathcal{D}}f(x)-\frac{1}{n}\sum_{i=1}^{n}f((x_{i},y_{i}))}}\right| \displaystyle\leq\epsilon_{n}\penalty\ , (4.22) \displaystyle\sup_{f=f_{w,w^{\prime}}\in\mathcal{F}^{\prime}}\mathopen{}\mathclose{{\left|\mathbb{E}_{x\sim\mathcal{D}}f(x)-\frac{1}{n}\sum_{i=1}^{n}f((x_{i},y_{i}))}}\right| \displaystyle\leq\epsilon_{n}\penalty\ , (4.23) \displaystyle\mathopen{}\mathclose{{\left|\mathbb{E}_{x\sim\mathcal{D}}(f^{*}(x)-y)^{2}-\frac{1}{n}\sum_{i=1}^{n}(f^{*}(x_{i})-y_{i})^{2}}}\right| \displaystyle\leq\epsilon_{n}\penalty\ . (4.24) Also with probability 1-n^{-\Theta(1)} , \forall w,w^{\prime}\in\mathcal{S} , \|\nabla^{2}_{w}K_{\hat{\mathcal{D}}}(w,w^{\prime})\|\leq C_{\text{reg}}/11(1+\|w^{\prime}\|) and \|\nabla_{w}\nabla_{w^{\prime}}K_{\hat{\mathcal{D}}}(w,w^{\prime})\|\leq C_{\text{reg}}/11 . Assumption 3 (UC over sample of neurons) . Let \displaystyle\mathcal{F} \displaystyle:=\{f_{w,v}(z):=v^{\top}\nabla_{w}K(w,z):w\in\mathcal{S},v\in\mathbb{S}^{d-1}\}\penalty\ , (4.25) \displaystyle\mathcal{F}^{\prime} \displaystyle:=\{f_{w,v}(z):=\langle{v,\nabla_{w}P_{w}\nabla_{w}K(w,z)\rangle}:w\in\mathcal{S},v\in(\mathbb{S}^{d-1})^{\otimes 2}\}\penalty\ . (4.26) For any distribution \rho\in\mathcal{P}(\mathcal{S}) , with z\sim\rho is \kappa_{z} subgaussian, we have the following uniform convergence bound with probability 1-\epsilon_{m}^{2}m^{-\Theta(1)}/(1+t)^{2} over z_{i}\sim\rho : \displaystyle\sup_{f\in\mathcal{F}\cup\mathcal{F}^{\prime}}\mathopen{}\mathclose{{\left|\mathbb{E}_{z\sim\rho}f(z)-\frac{1}{m}\sum_{i=1}^{m}f(z_{i})}}\right|\leq\epsilon_{m}\kappa_{z}\log(1+t). (4.27) Theorem 2 (Uniform PoC for Polynomial Convergence Rates) . Suppose Assumptions 1 , 2 , and 3 hold, \eta\leq 0.1/C_{\text{reg}} , and write \mathcal{L}_{t}:=\mathcal{L}(\rho_{t}^{\textsc{MF}}) . Assume S:=1+\int_{t=0}^{\infty}\sqrt{\mathcal{L}_{t}}dt<\infty . Define \tilde{S}(t):=1+\min\mathopen{}\mathclose{{\left(t,\int_{s=0}^{\infty}\min(t,s)\sqrt{\mathcal{L}_{s}}ds}}\right) . Let \rho_{t}^{\textsc{MF}} be given by ( 2.4 ), and \hat{\rho}^{m}_{t} by ( 2.6 ). Then with probability at least 1-\min(m,n)^{-\Theta(1)} over \hat{\rho}^{m}_{0} and the data sample, for any t<\infty , \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|^{2}_{\mathcal{H}}\leq 4\mathcal{L}_{R}(m,n,\eta) (4.28) where t^{*}(m,n,\eta):=\operatorname{poly}(SC_{\text{reg}})\exp(3C_{\text{reg}}S)\min\mathopen{}\mathclose{{\left((\epsilon_{m})^{-1/3},(\epsilon_{n}+\epsilon_{\eta})^{-1/4}}}\right) , and \displaystyle\mathcal{L}_{R}(m,n,\eta):=\inf_{t\leq t^{*}(m,n,\eta)}2\mathcal{L}_{t}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+(\epsilon_{n}+\epsilon_{\eta})^{1/2})}}\right), (4.29) with \bar{\epsilon}_{m}:=2C_{\text{reg}}(1+S)\log(m)\epsilon_{m} . Corollary 6 . Suppose Assumptions 1 and 3 hold, \eta=0 , and \mathcal{D}=\hat{\mathcal{D}} such that \epsilon_{\eta}=\eta_{n}=0 . If \mathcal{L}_{t}\leq\max(1,t+1-B)^{-c} for some burn-in time 1\leq Bt , the claim continues to hold up to time t^{\prime} . We will begin with the following observation. Claim 13 . If the inductive hypothesis holds up to time t , then for all s\leq t , we have \displaystyle\|\bm{\beta}_{s}\|_{\infty}+\|\bm{\epsilon}_{s}\|_{\infty} \displaystyle\leq 3\tilde{S}(s)\tilde{\epsilon}_{m} (4.67) \displaystyle\|\bm{\beta}_{s}\|_{2}+\|\bm{\epsilon}_{s}\|_{2} \displaystyle\leq 3\tilde{\epsilon}_{m}. (4.68) Proof. From ( 4.50 ) and the definition of \bar{\epsilon}_{m} , we have \displaystyle\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty}\leq\bar{\epsilon}_{m}\|\Delta_{s}\|_{\infty}+4C_{\text{reg}}\|\Delta_{s}\|^{2}_{\infty}+\bar{\epsilon}_{m}+\bar{\epsilon}\leq\tilde{\epsilon}_{m}+4C_{\text{reg}}\|\Delta_{s}\|^{2}_{\infty}. (4.69) By the induction hypothesis, and the fact that t\leq\min\mathopen{}\mathclose{{\left((8C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}S\tilde{\epsilon}_{m})^{-1/3},(8C_{\text{reg}}^{3}C_{\ell_{2}}^{2}\bar{\epsilon})^{-1/4}}}\right) , we have that for all s\leq t , \displaystyle\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty} \displaystyle\leq\tilde{\epsilon}_{m}+8C_{\text{reg}}C_{\ell_{\infty}}^{2}(\tilde{S}(s))^{2}(s+1)^{2}\tilde{\epsilon}_{m}^{2}+8C_{\text{reg}}^{3}C_{\ell_{2}}^{2}s^{4}\bar{\epsilon}^{2} (4.70) \displaystyle\leq\tilde{\epsilon}_{m}+2\tilde{\epsilon}_{m}\tilde{S}(s)+\bar{\epsilon}\leq 3\tilde{S}(s)\tilde{\epsilon}_{m}. (4.71) Indeed, (s+1)^{2}\tilde{S}(s)\leq(s+1)^{3}S\leq(8C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}\tilde{\epsilon}_{m})^{-1} . Similarly, we have \displaystyle\|\bm{\epsilon}_{s}\|+\|\bm{\beta}_{s}\|\leq\bar{\epsilon}_{m}\|\Delta_{s}\|+4C_{\text{reg}}\|\Delta_{s}\|^{2}_{4}+\bar{\epsilon}_{m}+\bar{\epsilon}\leq 2\tilde{\epsilon}_{m}+4C_{\text{reg}}\|\Delta_{s}\|\|\Delta_{s}\|_{\infty}. (4.72) Again by the induction hypothesis, and the fact that t\leq t^{*} we have that for all s\leq t , \displaystyle\|\bm{\epsilon}_{s}\|+\|\bm{\beta}_{s}\| \displaystyle\leq 2\tilde{\epsilon}_{m}+4C_{\text{reg}}C_{\ell_{\infty}}C_{\ell_{2}}\tilde{S}(s)(s+1)^{2}\tilde{\epsilon}_{m}^{2}+\bar{\epsilon} (4.73) \displaystyle\leq 2\bar{\epsilon}_{m}+\tilde{\epsilon}_{m}+\bar{\epsilon}\leq 3\tilde{\epsilon}_{m}. (4.74) ∎ Now lets prove the inductive step for \|\Delta_{t^{\prime}}\| . Employing ( 4.48 ) with the bound on both \|\bm{\beta}_{s}\|+\|\bm{\epsilon}_{s}\|\leq 3\bar{\epsilon}_{m}+\bar{\epsilon} for t\leq s from Claim 13 , along with Lemma 8 , yields that for all s\leq t , \displaystyle\frac{d}{ds}\|\Delta_{s}\|\leq C_{\text{reg}}\sqrt{\mathcal{L}_{s}}\|\Delta_{s}\|+3\tilde{\epsilon}_{m}. (4.75) Let Q(t,s):=\exp\mathopen{}\mathclose{{\left(\int_{r=s}^{t}\sqrt{\mathcal{L}_{r}}dr}}\right) . Then by Gronwall’s inequality and Duhamel, we have that \displaystyle\|\Delta_{t^{\prime}}\| \displaystyle\leq Q(t^{\prime},0)^{C_{\text{reg}}}\|\Delta_{0}\|+3\tilde{\epsilon}_{m}\int_{s=0}^{t}Q(t^{\prime},s)^{C_{\text{reg}}}ds+\int_{s=t}^{t^{\prime}}Q(t^{\prime},s)^{C_{\text{reg}}}(\|\bm{\epsilon}_{s}\|+\|\bm{\beta}_{s}\|)ds (4.76) \displaystyle\leq 3\exp(C_{\text{reg}}S)t\tilde{\epsilon}_{m}+\exp(C_{\text{reg}}S)(t^{\prime}-t)\sup_{s\in[t,t^{\prime}]}(\|\bm{\epsilon}_{s}\|+\|\bm{\beta}_{s}\|) (4.77) \displaystyle\leq 4\exp(C_{\text{reg}}S)(t^{\prime}+1)\tilde{\epsilon}_{m}, (4.78) for t^{\prime}-t small enough. This proves the inductive step for \|\Delta_{t}\| since C_{\ell_{2}}=4\exp(C_{\text{reg}}S) . Now we prove the inductive step for \|\Delta_{t^{\prime}}\|_{\infty} . We can write \displaystyle\Delta_{t^{\prime}}=-\int_{s=0}^{t^{\prime}}J_{t^{\prime},s}(H_{s}\Delta_{s}-\bm{\epsilon}_{s}-\bm{\beta}_{s})ds, (4.79) so \displaystyle\|\Delta_{t^{\prime}}\|_{\infty} \displaystyle\leq\int_{s=0}^{t^{\prime}}J_{\text{max}}(t^{\prime})(\|V_{s}^{\ast}V_{s}\Delta_{s}\|_{\infty}+\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty})ds (4.80) \displaystyle\leq\exp(C_{\text{reg}}S)\int_{s=0}^{t^{\prime}}(\|V_{s}^{\ast}\|_{\mathcal{H}\to\infty}\|V_{s}\Delta_{s}\|_{\mathcal{H}}+\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty})ds (4.81) \displaystyle\leq\exp(C_{\text{reg}}S)\int_{s=0}^{t^{\prime}}(C_{\text{reg}}\|V_{s}\Delta_{s}\|_{\mathcal{H}}+\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty})ds, (4.82) where here we have used the fact that by Lemma 8 , J_{\text{max}}(t^{\prime})\leq\exp(\int_{s=0}^{t^{\prime}}\|D_{s}\|ds)\leq\exp(C_{\text{reg}}\int_{s=0}^{t^{\prime}}\sqrt{\mathcal{L}_{s}}ds)\leq\exp(C_{\text{reg}}S) , and by Lemma 7 5 , \displaystyle\|V_{s}^{\ast}\|_{\mathcal{H}\to\infty} \displaystyle\leq\sup_{\xi\in\mathcal{S}}\sup_{u\in\mathbb{S}^{d-1}}\sup_{\|g\|_{\mathcal{H}}=1}\mathopen{}\mathclose{{\left\langle g,\,u^{\top}P_{\xi}\nabla K(\xi,\cdot)}}\right\rangle_{\mathcal{H}} (4.83) \displaystyle\leq\sup_{\xi\in\mathcal{S}}\sup_{u\in\mathbb{S}^{d-1}}\mathopen{}\mathclose{{\left\|u^{\top}P_{\xi}\nabla K(\xi,\cdot)}}\right\|_{\mathcal{H}} (4.84) \displaystyle\leq C_{\text{reg}}. (4.85) Let A_{t,t^{\prime}}:=\exp(C_{\text{reg}}S)\int_{s=t}^{t^{\prime}}(C_{\text{reg}}\|V_{s}\Delta_{s}\|_{\mathcal{H}}+\|\bm{\epsilon}_{s}\|_{\infty}+\|\bm{\beta}_{s}\|_{\infty})ds , which goes to zero as t^{\prime}-t\rightarrow 0 . Plugging Claim 13 into ( 4.80 ) along with the inductive hypothesis that \|V_{s}\Delta_{s}\|_{\mathcal{H}}\leq C_{V}\tilde{S}(s)\tilde{\epsilon}_{m}+C_{\text{reg}}s\bar{\epsilon} for s\leq t yields \displaystyle\|\Delta_{t^{\prime}}\|_{\infty} \displaystyle\leq\exp(C_{\text{reg}}S)\int_{s=0}^{t}(C_{\text{reg}}C_{V}\tilde{S}(s)\tilde{\epsilon}_{m}+3\tilde{S}(s)\tilde{\epsilon}_{m}+C_{\text{reg}}^{2}s\bar{\epsilon})ds+A_{t,t^{\prime}} (4.86) \displaystyle\leq 3\exp(C_{\text{reg}}S)\mathopen{}\mathclose{{\left(tC_{\text{reg}}C_{V}\tilde{S}(t)\tilde{\epsilon}_{m}+C_{\text{reg}}^{2}t^{2}\bar{\epsilon}}}\right)+A_{t,t^{\prime}} (4.87) \displaystyle\leq 4\exp(C_{\text{reg}}S)\mathopen{}\mathclose{{\left(C_{\text{reg}}C_{V}\tilde{S}(t)(t^{\prime}+1)\tilde{\epsilon}_{m}+C_{\text{reg}}^{2}{t^{\prime}}^{2}\bar{\epsilon}}}\right) (4.88) for t^{\prime}-t small enough. This proves the inductive step for \|\Delta_{t}\|_{\infty} since C_{\ell_{\infty}}=4\exp(C_{\text{reg}}S)C_{\text{reg}}C_{V} . Finally for \|V_{t^{\prime}}\Delta_{t^{\prime}}\|_{\mathcal{H}} , we have by Claim 11 that \displaystyle\|V_{t^{\prime}}\Delta_{t^{\prime}}\|_{\mathcal{H}} \displaystyle\leq 2C_{\text{reg}}^{3}\bar{\epsilon}_{m}\tilde{S}(t^{\prime})+C_{\text{reg}}^{3}\int_{s=0}^{t^{\prime}}\sqrt{\mathcal{L}_{s}}\|\Delta_{s}\|ds+C_{\text{reg}}\int_{s=0}^{t^{\prime}}\mathopen{}\mathclose{{\left(\bar{\epsilon}_{m}\|\Delta_{s}\|_{2}+4C_{\text{reg}}\|\Delta_{s}\|\|\Delta_{s}\|_{\infty}+\bar{\epsilon}}}\right)ds. (4.89) Now by the inductive hypothesis, \displaystyle\int_{s=0}^{t}\sqrt{\mathcal{L}_{s}}\|\Delta_{s}\|ds \displaystyle\leq\int_{s=0}^{t}\sqrt{\mathcal{L}_{s}}(s+1)C_{\ell_{2}}\tilde{\epsilon}_{m}ds\leq\tilde{S}(t)C_{\ell_{2}}\tilde{\epsilon}_{m}. (4.90) Next, \displaystyle\int_{s=0}^{t}\bar{\epsilon}_{m}\|\Delta_{s}\|_{2}ds \displaystyle\leq\bar{\epsilon}_{m}\int_{s=0}^{t}(s+1)C_{\ell_{2}}\tilde{\epsilon}_{m}\leq\bar{\epsilon}_{m}(t+1)^{2}C_{\ell_{2}}\tilde{\epsilon}_{m}\leq\bar{\epsilon}_{m}, (4.91) by the upper bound on t . Finally, \displaystyle\int_{s=0}^{t} \displaystyle 4C_{\text{reg}}\|\Delta_{s}\|\|\Delta_{s}\|_{\infty}ds (4.92) \displaystyle\leq\int_{s=0}^{t}4C_{\text{reg}}(s+1)^{2}\tilde{S}(s)C_{\ell_{2}}C_{\ell_{\infty}}\tilde{\epsilon}_{m}^{2}ds+\int_{s=0}^{t}4C_{\text{reg}}(s+1)^{3}C_{\ell_{2}}^{2}C_{\text{reg}}\tilde{\epsilon}_{m}\bar{\epsilon}ds (4.93) \displaystyle\leq 4C_{\text{reg}}(t+1)^{3}C_{\ell_{2}}C_{\ell_{\infty}}\tilde{S}(t)\tilde{\epsilon}_{m}^{2}+(t+1)^{4}C_{\text{reg}}^{2}C_{\ell_{2}}^{2}\tilde{\epsilon}_{m}\bar{\epsilon} (4.94) \displaystyle\leq\tilde{S}(t)\tilde{\epsilon}_{m} (4.95) since t\leq\min\mathopen{}\mathclose{{\left((8C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}S\tilde{\epsilon}_{m})^{-1/3},(8C_{\text{reg}}^{3}C_{\ell_{2}}^{2}\bar{\epsilon})^{-1/4}}}\right) . Thus for t-t^{\prime} small enough, since V_{t}\Delta_{t} is continuous in t , we have \displaystyle\|V_{t^{\prime}}\Delta_{t^{\prime}}\|_{\mathcal{H}}\leq\mathopen{}\mathclose{{\left(2C_{\text{reg}}^{3}\tilde{\epsilon}_{m}\tilde{S}(t)+C_{\text{reg}}^{3}\tilde{S}(t^{\prime})C_{\ell_{2}}\tilde{\epsilon}_{m}+\tilde{S}(t^{\prime})\tilde{\epsilon}_{m}+C_{\text{reg}}t^{\prime}\bar{\epsilon}}}\right)\leq 3C_{\text{reg}}^{3}C_{\ell_{2}}\tilde{S}(t^{\prime})\bar{\epsilon}_{m}+C_{\text{reg}}t^{\prime}\bar{\epsilon}. (4.96) This proves the inductive step for \|V_{t}\Delta_{t}\|_{\mathcal{H}} since C_{V}=3C_{\text{reg}}^{3}C_{\ell_{2}} . This completes the proof. ∎ Returning to ( 4.45 ) and again leveraging the bound on \|\Delta_{t}\|_{4}^{4}\leq\|\Delta_{t}\|^{2}\|\Delta_{t}\|^{2}_{\infty} from Claim 12 , we have that for all t\leq\min\mathopen{}\mathclose{{\left((8C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}S\tilde{\epsilon}_{m})^{-1/3},(8C_{\text{reg}}^{3}C_{\ell_{2}}^{2}\bar{\epsilon})^{-1/4}}}\right) , \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2C_{V}^{2}\tilde{S}(t)^{2}\tilde{\epsilon}_{m}^{2}+2C_{\text{reg}}^{2}t^{2}\bar{\epsilon}^{2}+O\mathopen{}\mathclose{{\left(\frac{C_{\text{reg}}^{6}(1+S)^{2}\log(m)}{m}}}\right)+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{2}\|\Delta_{t}\|_{4}^{4}}}\right) (4.97) \displaystyle\leq O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2})}}\right). (4.98) Now because the above bounds hold only for t\lessapprox\min(\bar{\epsilon}_{m}^{-1/3},\bar{\epsilon}^{-1/4}) , we will leverage the fact that this PoC error can also be bounded from the loss of \hat{\rho}^{m}_{t} , which is nearly non-increasing, as per the claim below. Claim 14 . For any t\geq s , we have \displaystyle\mathcal{L}(\hat{\rho}^{m}_{t})\leq\mathcal{L}(\hat{\rho}^{m}_{t})+C_{\text{reg}}^{2}(1+S)^{2}\epsilon_{n}. (4.99) Proof. In the case that \eta=0 and n=\infty (or \mathcal{D}=\hat{\mathcal{D}} ), this is immediate, since we are running gradient flow on the population loss, so it can never increase. If \mathcal{D}=\hat{\mathcal{D}} but we have a non-zero step size \eta , it suffices to show that \eta is smaller than the inverse Lipschitzness of the gradient. Indeed by Lemma 7 , the Lipschitzness of \nu with respect to any parameter is at most \sup_{w,w^{\prime}\in\mathcal{S}}\mathopen{}\mathclose{{\left(\|\nabla^{2}K(w,w^{\prime})\|+\|\nabla_{1}\nabla_{2}K(w,w^{\prime})\|}}\right)\leq 2C_{\text{reg}} , and we have assumed \eta<0.1/C_{\text{reg}} . Finally, for the case that \mathcal{L}_{\mathcal{D}}\neq\mathcal{L}_{\hat{\mathcal{D}}} , we have that for \eta=0 , \mathcal{L}_{\hat{\mathcal{D}}} is non-increasing, and thus \displaystyle\mathcal{L}_{\hat{\mathcal{D}}}(\rho_{t}^{\textsc{MF}})\leq\mathcal{L}_{\hat{\mathcal{D}}}(\rho_{s}^{\textsc{MF}}), (4.100) and by Assumption 2 , we have \sup_{t<\infty}|\mathcal{L}_{\mathcal{D}}(\rho_{t}^{\textsc{MF}})-\mathcal{L}_{\hat{\mathcal{D}}}(\rho_{t}^{\textsc{MF}})|\leq\epsilon_{n}(1+\sup_{t}\kappa_{t})^{2}\leq C_{\text{reg}}^{2}(1+S)^{2}\epsilon_{n} . It remains to show that even if 0<\eta\leq 0.1/C_{\text{reg}} , \mathcal{L}_{\hat{\mathcal{D}}} is non-increasing. This follows from the Lipschitzness bounds on K_{\hat{\mathcal{D}}} and its derivatives in Assumption 2 . ∎ From ( 4.97 ), we have that for t\leq t^{*} , \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho^{*}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2\mathopen{}\mathclose{{\left(\mathcal{L}_{t}+\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2}}}\right) (4.101) \displaystyle\leq 2\mathcal{L}_{t}+O_{C_{\text{reg}}}\mathopen{}\mathclose{{\left(\exp(2C_{\text{reg}}S)\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2}}}\right), (4.102) Employing the claim above, for all t\geq t^{*} , we have \mathcal{L}(\hat{\rho}^{m}_{t})\leq\mathcal{L}_{R}(m,n,\eta) , where \displaystyle\mathcal{L}_{R}(m,n,\eta):=\inf_{t\leq\min\mathopen{}\mathclose{{\left((8C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}S\tilde{\epsilon}_{m})^{-1/3},(8C_{\text{reg}}^{3}C_{\ell_{2}}^{2}\bar{\epsilon})^{-1/4}}}\right)}2\mathcal{L}_{t}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2})}}\right) (4.103) Thus for any t greater than the argmin of ( 4.103 ) we have \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2\mathopen{}\mathclose{{\left(\mathbb{E}_{x}(f_{\rho_{t}^{\textsc{MF}}}(x)-f^{*}(x))^{2}+\mathcal{L}(\hat{\rho}^{m}_{t})}}\right) (4.104) \displaystyle\leq 2\mathcal{L}_{t}+2\mathcal{L}_{R}(m,n,\eta)\leq 4\mathcal{L}_{R}(m,n,\eta), (4.105) while for t less than the argmin, we have \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2}\leq O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2})}}\right)\leq\mathcal{L}_{R}(m,n,\eta). (4.106) The result now follows. Simplifications for Theorem 1 To attain the simplifications of the result stated in Theorem 1 , in the general case where \eta=0,n=\infty , since \mathcal{L}_{t} is non-increasing, we have S\geq\int_{0}^{t}\sqrt{\mathcal{L}_{s}}\,ds\geq\int_{0}^{t}\sqrt{\mathcal{L}_{t}}\,ds=t\sqrt{\mathcal{L}_{t}}. Hence \sqrt{\mathcal{L}_{t}}\leq\frac{S}{t} , and so \mathcal{L}_{t}\leq\frac{S^{2}}{t^{2}} . Thus \displaystyle\mathcal{L}_{t^{*}}\leq\operatorname{poly}(C_{\text{reg}})S^{2}O\mathopen{}\mathclose{{\left(\exp(2C_{\text{reg}}S)\tilde{\epsilon}_{m}^{2/3}+\exp(C_{\text{reg}}S)\bar{\epsilon}^{1/2}}}\right), (4.107) Since the O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2})}}\right) term is smaller, we have \displaystyle\mathcal{L}_{R}(m,n,\eta)\leq\operatorname{poly}(C_{\text{reg}})S^{2}O\mathopen{}\mathclose{{\left(\exp(2C_{\text{reg}}S)\tilde{\epsilon}_{m}^{2/3}+\exp(C_{\text{reg}}S)\bar{\epsilon}^{1/2}}}\right). (4.108) Now in the case that {S^{\prime}}:=\int_{t=0}^{\infty}t^{2}\sqrt{\mathcal{L}_{t}}dt<\infty , we have S^{\prime}\geq\int_{0}^{t}s^{2}\sqrt{\mathcal{L}_{s}}\,ds\geq\int_{0}^{t}s^{2}\sqrt{\mathcal{L}_{t}}\,ds=\sqrt{\mathcal{L}_{t}}\int_{0}^{t}s^{2}\,ds=\frac{t^{3}}{3}\sqrt{\mathcal{L}_{t}}. and thus \mathcal{L}_{t}\leq\frac{9{S^{\prime}}^{2}}{t^{6}} . Thus here we have \displaystyle\mathcal{L}_{t^{*}}\leq\operatorname{poly}(C_{\text{reg}}){S^{\prime}}^{2}O\mathopen{}\mathclose{{\left(\exp(6C_{\text{reg}}S)\tilde{\epsilon}_{m}^{2}+\exp(3C_{\text{reg}}S)\bar{\epsilon}^{3/2}}}\right), (4.109) Combining with the O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t)^{2}+\bar{\epsilon}^{1/2})}}\right) term, this yields \displaystyle\mathcal{L}_{R}(m,n,\eta)\leq\operatorname{poly}(C_{\text{reg}}){S^{\prime}}^{4}O\mathopen{}\mathclose{{\left(\exp(6C_{\text{reg}}S)\tilde{\epsilon}_{m}^{2}+\exp(3C_{\text{reg}}S)\bar{\epsilon}^{1/2}}}\right). (4.110) ∎ Proof. [Proof of Corollary 6 ] Polynomial convergence rate. First we consider the case that \mathcal{L}_{t}\leq\max(1,(t+1-B))^{-c} , for c>2 . Observe that we have \displaystyle S\leq\int_{t=1}^{\infty}\max(1,(t-B))^{-c/2}dt\leq B+\frac{1}{c/2-1} (4.111) Additionally, we have \tilde{S}(t)\leq 1+\min\mathopen{}\mathclose{{\left(t,\int_{s=0}^{\infty}\min(t,s)\sqrt{\mathcal{L}_{s}}ds}}\right) , where for t\geq 2B , \displaystyle\min\mathopen{}\mathclose{{\left(t,\int_{s=0}^{\infty}\min(t,s)\sqrt{\mathcal{L}_{s}}ds}}\right) \displaystyle\leq\min\mathopen{}\mathclose{{\left(t,\int_{s=1}^{\infty}\min(t,s)\max(1,(s-B))^{-c/2}ds}}\right) (4.112) \displaystyle\leq\int_{s=1}^{t}s\max(1,(s-B))^{-c/2}ds+t\min\mathopen{}\mathclose{{\left(1,\int_{s=t}^{\infty}\max(1,(s-B))^{-c/2}ds}}\right) (4.113) \displaystyle\leq\frac{B^{2}}{2}+2\log(t)t^{2-c/2}. (4.114) Thus so long as t^{*}\geq 2B (which occurs whenever n,m\geq\operatorname{poly}(d) ), we have \displaystyle\mathcal{L}_{R}(m,n,\eta) \displaystyle\leq 2\mathcal{L}_{t^{*}}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t^{*})^{2}+\bar{\epsilon}^{1/2})}}\right) (4.115) \displaystyle\leq O\mathopen{}\mathclose{{\left((t^{*})^{-c}}}\right)+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\bar{\epsilon}_{m}^{2}\tilde{S}(t^{*})^{2}+\bar{\epsilon}^{1/2})}}\right) (4.116) \displaystyle\leq O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(6C_{\text{reg}}(B+(c/2-1)^{-1}))\mathopen{}\mathclose{{\left(\bar{\epsilon}_{m}^{\min(c,6)/3}+\bar{\epsilon}^{1/2}}}\right)}}\right) (4.117) This yields the desired results for polynomial decay rates. The c=2 case where S=\infty For the case when c=2 , we can redefine t^{*}=\tilde{O}(\operatorname{poly}(C_{\text{reg}}\log(m))\exp(-C_{\text{reg}}B)\tilde{\epsilon}_{m}^{-1/(6C_{\text{reg}})}), and S:=\int_{t=0}^{t^{*}}\sqrt{\mathcal{L}_{t}}dt\leq B+\log(t^{*}) . This changes nothing in the proof of the main result since t^{*}\leq(4C_{\text{reg}}C_{\ell_{2}}C_{\ell_{\infty}}^{2}I_{S}\bar{\epsilon}_{m})^{-1/3} and \tilde{S}(s)\leq(s+1)S still holds. Note, because we no longer can assume that \xi_{t}(w) and \rho_{t}^{\textsc{MF}} have limits \xi_{\infty}(w) and \rho_{\infty}^{\textsc{MF}} , in all auxiliary lemmas which assumed this limit, we can replace \infty with t^{*} , and nothing changes, since we only need these lemmas to hold for t\leq t^{*} . Now to attain the final loss PoC bound in this case, we use the crude bound \tilde{S}(t)\leq t , yielding \displaystyle\mathcal{L}_{R}(m,n,\eta) \displaystyle\leq 2\mathcal{L}_{t^{*}}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{6}\exp(2C_{\text{reg}}S)(\tilde{\epsilon}_{m}^{2}{t^{*}}^{2}+\bar{\epsilon}^{1/2})}}\right) (4.118) \displaystyle\leq\operatorname{poly}(C_{\text{reg}})O\mathopen{}\mathclose{{\left(\exp(2C_{\text{reg}}B)\tilde{\epsilon}_{m}^{1/(3C_{\text{reg}})}}}\right) (4.119) ∎ 4.4 Proof of Preliminary Lemmas Proof. [Proof of Lemma 7 ] First note that the operator norm of the first and second derivatives of P_{w} is at most 2 . Thus for any vector-valued function \xi(w) , by chain rule, we have \displaystyle\mathopen{}\mathclose{{\left\|\nabla_{w}(I-ww^{\top})\xi(w)}}\right\| \displaystyle\leq\mathopen{}\mathclose{{\left\|\nabla_{w}\xi(w)}}\right\|+2\mathopen{}\mathclose{{\left\|\xi(w)}}\right\|\penalty\ , (4.120) \displaystyle\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}(I-ww^{\top})\xi(w)}}\right\| \displaystyle\leq 3\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}\xi(w)}}\right\|+8\mathopen{}\mathclose{{\left\|\nabla_{w}\xi(w)}}\right\|. (4.121) Thus it is easy to see from Assumption 1 that 1 and 2 hold. For 3 , since \nu(w,\rho)=P_{w}\nabla_{w}F(w)-\mathbb{E}_{w^{\prime}\sim\rho}P_{w}\nabla_{w}K(w,w^{\prime}) , we have (for example) \|\nabla_{w}^{2}P_{w}\nabla_{w}F(w)\|\leq 3\|\nabla_{w}^{3}F(w)\|+8\|\nabla_{w}^{2}F(w)\|\leq C_{\text{reg}} , and similarly \|\nabla^{2}_{w}P_{w}\nabla_{w}K(w,w^{\prime})\|\leq C_{\text{reg}}(1+\|w^{\prime}\|) . Clearly \mathbb{E}_{w^{\prime}\sim\rho}\|w\|\leq\kappa_{\rho} , so this yields the bound on \mathopen{}\mathclose{{\left\|\nabla^{2}_{w}\nu(w,\rho)}}\right\|_{op} in 3 . In the kernel mean discrepancy setting, we have \nu(w,\rho)=P_{w}\nabla_{w}\mathbb{E}_{w^{\prime}\sim\rho^{*}}P_{w}\nabla_{w}K(w,w^{\prime})-\mathbb{E}_{w^{\prime}\sim\rho}P_{w}\nabla_{w}K(w,w^{\prime}), and thus the assumption that \|w\| for w\sim\rho^{*} is subgaussian suffices. For 4 by the reproducing kernel property and Assumption 1 , \displaystyle\mathopen{}\mathclose{{\left\|K(w,\cdot)}}\right\|_{\mathcal{H}}^{2} \displaystyle=K(w,w)\leq C_{\text{reg}}(1+\|w\|)^{2}. (4.122) Now for 5 , by the reproducing kernel property and Assumption 1 , \displaystyle\sup_{w\in\mathcal{S},\;u\in\mathbb{S}^{d-1}}\mathopen{}\mathclose{{\left\|u^{\top}\nabla K(w,\cdot)}}\right\|_{\mathcal{H}}^{2} \displaystyle=\sup_{w\in\mathcal{S},\;u\in\mathbb{S}^{d-1}}u^{\top}\nabla_{w}\nabla_{w^{\prime}}K(w,w^{\prime})\big|_{w^{\prime}=w}u\leq\sup_{w,w^{\prime}\in\mathcal{S}}\mathopen{}\mathclose{{\left\|\nabla_{w}\nabla_{w^{\prime}}K(w,w^{\prime})}}\right\|\leq C_{\text{reg}}, (4.123) Similarly, for 6 , with \partial_{i,u} denoting the directional derivative in the i th argument in direction u , we have \displaystyle\mathopen{}\mathclose{{\left\|D^{2}K(w,\cdot)[u,v]}}\right\|_{\mathcal{H}}^{2} \displaystyle=\mathopen{}\mathclose{{\left\langle\partial_{1,u}\partial_{1,v}K(w,\cdot),\partial_{1,u}\partial_{1,v}K(w,\cdot)}}\right\rangle_{\mathcal{H}} (4.124) \displaystyle=\partial_{1,u}\partial_{1,v}\partial_{2,u}\partial_{2,v}K(w,w) (4.125) \displaystyle\leq C_{\text{reg}}^{2}\|u\|^{2}\|v\|^{2}. (4.126) ∎ Proof. [Proof of Lemma 8 ] Let h_{\rho}:=m_{\rho}-m_{\rho^{\ast}}\in\mathcal{H} , so that under our normalization, \mathcal{L}(\rho)=\|h_{\rho}\|_{\mathcal{H}}^{2}. The first variation of the loss can be written as U(\xi,\rho)=\mathopen{}\mathclose{{\left\langle\Phi(\xi),h_{\rho}}}\right\rangle_{\mathcal{H}}. We first control D_{t} . Differentiating twice with respect to \xi , we have for any v,v^{\prime}\in\mathbb{S}^{d-1} , \displaystyle v^{\top}\nabla_{\xi}^{2}U(\xi,\rho)v^{\prime} \displaystyle=\mathopen{}\mathclose{{\left\langle D^{2}\Phi(\xi)[v,v^{\prime}],h_{\rho}}}\right\rangle_{\mathcal{H}}. (4.127) Therefore, by Cauchy–Schwarz and Lemma 7 6 , \displaystyle\mathopen{}\mathclose{{\left\langle D^{2}\Phi(\xi)[v,v^{\prime}],h_{\rho}}}\right\rangle_{\mathcal{H}} \displaystyle\leq\mathopen{}\mathclose{{\left\|D^{2}\Phi(\xi)[v,v^{\prime}]}}\right\|_{\mathcal{H}}\|h_{\rho}\|_{\mathcal{H}}\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho)}. (4.128) Now recall that D_{t}(w)=\nabla_{\xi_{t}(w)}\mathopen{}\mathclose{{\left(P_{\xi_{t}(w)}\nabla_{\xi_{t}(w)}U(\xi_{t}(w),\rho_{t}^{\textsc{MF}})}}\right). When \mathcal{S}=\mathbb{R}^{d} , we have P_{\xi}=I , so the previous bound directly yields \|D_{t}(w)\|\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho_{t}^{\textsc{MF}})} . When \mathcal{S}=\mathbb{S}^{d-1} , differentiating the projection P_{\xi}=I-\xi\xi^{\top} produces an additional term controlled by 2\|\nabla_{\xi}U(\xi,\rho)\| , but here we have u^{\top}\nabla_{\xi}U(\xi,\rho)=\mathopen{}\mathclose{{\left\langle D\Phi(\xi)[u],h_{\rho}}}\right\rangle_{\mathcal{H}}\leq\|D\Phi(\xi)[u]\|_{\mathcal{H}}\|h_{\rho}\|_{\mathcal{H}}\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho)} , again by Lemma 7 5 . We next control the velocity of the characteristics. The mean-field velocity satisfies \nu(\xi,\rho)=-P_{\xi}\nabla_{\xi}U(\xi,\rho) . Thus for any \xi,\rho , we have \displaystyle\|\nu(\xi,\rho)\| \displaystyle\leq\|\nabla_{\xi}U(\xi,\rho)\|=\|D\Phi(\xi)^{\ast}h_{\rho}\|\leq\|D\Phi(\xi)\|_{\mathrm{op}}\|h_{\rho}\|_{\mathcal{H}}\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho)}. (4.129) Thus \|\dot{\xi}_{t}(w)\|\leq C_{\text{reg}}\sqrt{\mathcal{L}(\rho_{t}^{\textsc{MF}})}. Therefore, since \int\sqrt{\mathcal{L}_{t}}dt<\infty , \xi_{t}(w) converges to some limit \xi_{\infty}(w) , and \boxed{\|\xi_{t}(w)-\xi_{\infty}(w)\|\leq\int_{s=t}^{\infty}\|\dot{\xi}_{s}(w)\|\,ds\leq C_{\text{reg}}\int_{s=t}^{\infty}\sqrt{\mathcal{L}(\rho_{s}^{\textsc{MF}})}ds.} Finally, we control \dot{V}_{t} . Recall that the kernel-native operator V_{t} is given by V_{t}\Lambda=\mathbb{E}_{w\sim\hat{\rho}^{m}_{0}}\mathopen{}\mathclose{{\left[D\Phi(\xi_{t}(w))\big[P_{\xi_{t}(w)}\Lambda(w)\big]}}\right], for vector fields \Lambda\in L_{2}(\hat{\rho}^{m}_{0},\mathbb{R}^{d}) . Differentiating in time gives \displaystyle\dot{V}_{t}\Lambda \displaystyle=\mathbb{E}_{w\sim\hat{\rho}^{m}_{0}}\mathopen{}\mathclose{{\left[D^{2}\Phi(\xi_{t}(w))\big[\dot{\xi}_{t}(w),P_{\xi_{t}(w)}\Lambda(w)\big]}}\right] (4.130) \displaystyle\qquad+\mathbb{E}_{w\sim\hat{\rho}^{m}_{0}}\mathopen{}\mathclose{{\left[D\Phi(\xi_{t}(w))\big[\dot{P}_{\xi_{t}(w)}\Lambda(w)\big]}}\right]. (4.131) The first term is bounded by Lemma 7 as \mathopen{}\mathclose{{\left\|\mathbb{E}_{w\sim\hat{\rho}^{m}_{0}}\mathopen{}\mathclose{{\left[D^{2}\Phi(\xi_{t}(w))\big[\dot{\xi}_{t}(w),P_{\xi_{t}(w)}\Lambda(w)\big]}}\right]}}\right\|_{\mathcal{H}}\leq C_{\text{reg}}\sup_{w}\|\dot{\xi}_{t}(w)\|\|\Lambda\|. In the Euclidean case P_{\xi}=I , the second term vanishes. In the spherical case, \|\dot{P}_{\xi_{t}(w)}\|\lesssim\|\dot{\xi}_{t}(w)\| and therefore the second term is controlled in the same way using the bound on \|D\Phi(\xi)\|_{\mathrm{op}} . Hence \boxed{\|\dot{V}_{t}\|_{\mathcal{H}}\leq C_{\text{reg}}\sup_{w}\|\dot{\xi}_{t}(w)\|\leq C_{\text{reg}}^{2}\sqrt{\mathcal{L}(\rho_{t}^{\textsc{MF}})}.} ∎ Proof. [Proof of Lemma 9 ] Recall that in the kernel mean discrepancy setting, we have g_{t}=m_{\bar{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\in\mathcal{H} . Recall that \bar{\rho}^{m}_{t}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\xi_{t}(w_{i})},\qquad\rho_{t}^{\textsc{MF}}=(\xi_{t})_{\#}\rho_{0}. We have \displaystyle g_{t}-g_{\infty} \displaystyle=\mathopen{}\mathclose{{\left(\mathbb{E}_{w\sim\bar{\rho}^{m}_{0}}\big[\Phi(\xi_{t}(w))-\Phi(\xi_{\infty}(w))\big]}}\right)-\mathopen{}\mathclose{{\left(\mathbb{E}_{w\sim\rho_{0}}\big[\Phi(\xi_{t}(w))-\Phi(\xi_{\infty}(w))\big]}}\right). (4.132) Thus g_{t}-g_{\infty} is the empirical average of m i.i.d. mean-zero \mathcal{H} -valued random variables. Define R_{t}:=\int_{s=t}^{\infty}\sqrt{\mathcal{L}(\rho_{s}^{\mathrm{MF}})}\,ds. By Lemma 8 , \|\xi_{t}(w)-\xi_{\infty}(w)\|\leq C_{\text{reg}}R_{t}. Using Lemma 7 5 , we have \displaystyle\|\Phi(\xi_{t}(w))-\Phi(\xi_{\infty}(w))\|_{\mathcal{H}} \displaystyle\leq\|\xi_{t}(w)-\xi_{\infty}(w)\|\sup_{w^{\prime}\in\mathcal{S},u\in\mathbb{S}^{d-1}}\|u^{\top}\nabla\Phi(w^{\prime})\|_{\mathcal{H}}\leq C_{\text{reg}}^{2}R_{t}. (4.133) Define the truncated random variable \displaystyle\tilde{g}_{t}:=\mathbb{E}_{w\sim\bar{\rho}^{m}_{0}}\big[\Phi(\xi_{t}(w))-\Phi(\xi_{\infty}(w))\mathbf{1}(\sup_{s<\infty}\|\xi_{s}(w)\|\leq\sqrt{\log(m)}\kappa_{\infty}).\big] (4.134) We have by the definition of \kappa_{\infty} that \displaystyle\mathbb{P}[\sup_{t<\infty}\|g_{t}-\tilde{g}_{t}\|_{\mathcal{H}}\geq 0]\leq 1-\mathopen{}\mathclose{{\left(1-\mathbb{P}[\sup_{s<\infty}\|\xi_{s}(w)\|\geq 2\sqrt{\log(m)}\kappa_{\infty}]}}\right)^{m}\leq\frac{1}{m}. (4.135) Now each random variable in \tilde{g}_{t} is bounded by C_{\text{reg}}^{2}\min\mathopen{}\mathclose{{\left(4\sqrt{\log(m)}(1+\kappa_{\infty}),R_{t}}}\right) , since by Lemma 7 4 we can also always bound \|\Phi(\xi_{t}(w))\|_{\mathcal{H}}\leq C_{\text{reg}}(1+\|\xi_{t}(w)\|) . Applying a Hilbert-space concentration inequality [ 41 , 33 ] to the empirical average \tilde{g}_{t}-g_{\infty} in ( 4.132 ) yields \mathbb{P}\mathopen{}\mathclose{{\left[\|\tilde{g}_{t}-g_{\infty}\|_{\mathcal{H}}\geq 2C_{\text{reg}}^{2}\sqrt{\log(1+t)}\epsilon_{m}\min(1+\kappa_{\infty},R_{t})}}\right]\leq\frac{2}{m^{5}(1+t)^{2}}, where we used the definition of \epsilon_{m}=\frac{C_{\text{reg}}^{6}\sqrt{d}\log(dm)}{\sqrt{m}} . It remains to extend this estimate uniformly over t<\infty . Indeed to check the conditions of [ 33 ] , observe that the RKHS is (2,1) -smooth and separable, since \mathcal{S} is separable. For s\geq t , \displaystyle\|(g_{t}-g_{\infty})-(g_{s}-g_{\infty})\|_{\mathcal{H}} \displaystyle\leq 2\sup_{w}\|\Phi(\xi_{t}(w))-\Phi(\xi_{s}(w))\|_{\mathcal{H}} (4.136) \displaystyle\leq 2C_{\text{reg}}\sup_{w}\|\xi_{t}(w)-\xi_{s}(w)\| (4.137) \displaystyle\leq 2C_{\text{reg}}^{2}\int_{r=t}^{s}\sqrt{\mathcal{L}(\rho_{r}^{\mathrm{MF}})}\,dr. (4.138) Thus g_{t}-g_{\infty} is uniformly continuous in t , with continuity modulus controlled by the loss. Taking an \epsilon_{m} -net in time and union bounding the preceding tail estimate over the net points gives, with probability 1-1/m , \|g_{t}-g_{\infty}\|_{\mathcal{H}}\leq 2C_{\text{reg}}^{2}\sqrt{\log(t+1)}\epsilon_{m}\min\mathopen{}\mathclose{{\left(1+\kappa_{\infty},\,\int_{s=t}^{\infty}\sqrt{\mathcal{L}(\rho_{s}^{\mathrm{MF}})}\,ds}}\right) uniformly for all t<\infty . We now bound g_{\infty} . Since g_{\infty}=\mathbb{E}_{w\sim\bar{\rho}^{m}_{0}}\Phi(\xi_{\infty}(w))-\mathbb{E}_{w\sim\rho_{0}}\Phi(\xi_{\infty}(w)), it is again the empirical average of m i.i.d. mean-zero \mathcal{H} -valued random variables. By Lemma 7 , \|\Phi(\xi)\|_{\mathcal{H}}\leq C_{\text{reg}}(1+\|\xi\|). Since \|\xi_{\infty}(w)\| has sub-Gaussian norm \kappa_{\infty} under w\sim\rho_{0} , the random variable \Phi(\xi_{\infty}(w))-\mathbb{E}_{w\sim\rho_{0}}\Phi(\xi_{\infty}(w)) has a O(C_{\text{reg}}\kappa_{\infty}) -subgaussian tail in the \mathcal{H} -norm. Thus with probability 1-\frac{1}{2m} , all of the random varialbles \Phi(\xi_{\infty}(w))-\mathbb{E}_{w_{i}\sim\rho_{0}}\Phi(\xi_{\infty}(w_{i})) are bounded by O(C_{\text{reg}}\kappa_{\infty}\sqrt{\log(m)}) . Again, the Hilbert-space concentration inequality therefore gives \mathbb{P}\mathopen{}\mathclose{{\left[\|g_{\infty}\|_{\mathcal{H}}\geq C_{\text{reg}}\kappa_{\infty}\epsilon_{m}}}\right]=\frac{1}{m}. This proves the lemma. ∎ Proof. [Proof of Lemma 10 ] We first decompose \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2\|m_{\bar{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2}+2\|m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}}\|_{\mathcal{H}}^{2}. (4.139) We begin by bounding the coupling term \|m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}}\|_{\mathcal{H}}^{2}. Recall that \bar{\rho}^{m}_{t}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\xi_{t}(w_{i})},\qquad\hat{\rho}^{m}_{t}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\xi_{t}(w_{i})+\Delta_{t}(i)}. Therefore, \displaystyle m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}} \displaystyle=\mathbb{E}_{i}\mathopen{}\mathclose{{\left[\Phi(\xi_{t}(w_{i}))-\Phi(\xi_{t}(w_{i})+\Delta_{t}(i))}}\right]. (4.140) Using the second-order Taylor expansion of the \mathcal{H} -valued map \Phi , \displaystyle\Phi(\xi_{t}(w_{i}))-\Phi(\xi_{t}(w_{i})+\Delta_{t}(i)) \displaystyle=D\Phi(\xi_{t}(w_{i}))[-\Delta_{t}(i)]+\int_{s=0}^{1}\int_{s^{\prime}=0}^{s}D^{2}\Phi(\xi_{t}(w_{i})+s^{\prime}\Delta_{t}(i))[\Delta_{t}(i),\Delta_{t}(i)]\,ds^{\prime}\,ds. (4.141) Hence \displaystyle m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}} \displaystyle=-V_{t}\Delta_{t}+B_{t}, (4.142) where V_{t}\Delta_{t}:=\mathbb{E}_{i}D\Phi(\xi_{t}(w_{i}))[\Delta_{t}(i)] and B_{t}:=\mathbb{E}_{i}\int_{s=0}^{1}\int_{s^{\prime}=0}^{s}D^{2}\Phi(\xi_{t}(w_{i})+s^{\prime}\Delta_{t}(i))[\Delta_{t}(i),\Delta_{t}(i)]\,ds^{\prime}\,ds. Therefore, \displaystyle\|m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2\|V_{t}\Delta_{t}\|_{\mathcal{H}}^{2}+2\|B_{t}\|_{\mathcal{H}}^{2}. (4.143) Recall from ( 4.31 ) \|V_{t}\Delta_{t}\|_{\mathcal{H}}^{2}=\Delta_{t}^{\top}H_{t}\Delta_{t}. It remains to bound \|B_{t}\|_{\mathcal{H}}^{2} . By Jensen’s inequality, \displaystyle\|B_{t}\|_{\mathcal{H}}^{2} \displaystyle\leq\mathbb{E}_{i}\mathopen{}\mathclose{{\left\|\int_{s=0}^{1}\int_{s^{\prime}=0}^{s}D^{2}\Phi(\xi_{t}(w_{i})+s^{\prime}\Delta_{t}(i))[\Delta_{t}(i),\Delta_{t}(i)]\,ds^{\prime}\,ds}}\right\|_{\mathcal{H}}^{2}. (4.144) Using Lemma 7 6 , we have \mathopen{}\mathclose{{\left\|D^{2}\Phi(\xi)[u,v]}}\right\|_{\mathcal{H}}^{2}\leq C_{\text{reg}}\|u\|\|v\| and thus \displaystyle\|B_{t}\|^{2}_{\mathcal{H}} \displaystyle\leq O(C_{\text{reg}}^{2}\mathbb{E}_{i}\|\Delta_{t}(i)\|^{4}). (4.145) Combining this with ( 4.143 ) yields \displaystyle\|m_{\bar{\rho}^{m}_{t}}-m_{\hat{\rho}^{m}_{t}}\|_{\mathcal{H}}^{2} \displaystyle\leq 2\Delta_{t}^{\top}H_{t}\Delta_{t}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{2}\|\Delta_{t}\|_{4}^{4}\bigr)}}\right). (4.146) We now bound the Monte-Carlo term \|m_{\bar{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2}. Since \bar{\rho}^{m}_{t} is the empirical measure of m i.i.d. samples from \rho_{t}^{\textsc{MF}} , m_{\bar{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}=\frac{1}{m}\sum_{i=1}^{m}\mathopen{}\mathclose{{\left(\Phi(\xi_{t}(w_{i}))-m_{\rho_{t}^{\textsc{MF}}}}}\right) is an average of i.i.d. centered \mathcal{H} -valued random variables. Repeating the exact same argument as the one in the proof of Lemma 9 to bound \|g_{t}-g_{\infty}\|_{\mathcal{H}} , with the exception each term in the truncated random variable is only bounded by 4C_{\text{reg}}^{2}\sqrt{\log(m)}\kappa_{\infty} , we attain that with probability 1-1/m , uniformly over t<\infty , we have \displaystyle\|m_{\bar{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|^{2}_{\mathcal{H}}\leq\frac{C_{\text{reg}}^{4}\kappa_{\infty}^{2}\log(m(1+t))}{m}. (4.147) Combining this Monte-Carlo estimate with ( 4.146 ), we conclude that with probability 1-m^{-\Theta(1)} , \displaystyle\|m_{\hat{\rho}^{m}_{t}}-m_{\rho_{t}^{\textsc{MF}}}\|_{\mathcal{H}}^{2} \displaystyle\leq 4\Delta_{t}^{\top}H_{t}\Delta_{t}+\frac{C_{\text{reg}}^{4}\kappa_{\infty}^{2}\log(m(1+t))}{m}+O\mathopen{}\mathclose{{\left(C_{\text{reg}}^{2}\|\Delta_{t}\|_{4}^{4}}}\right). (4.148) This concludes the proof. ∎ 5 Experiments In this section, we provide several examples of learning problems which empirically demonstrate fast enough convergence rates to satisfy the conditions of our main theorem. We study two settings, and defer further experimental details to Appendix B . Misspecified Sobolev single-index model We draw data (x,f^{*}(x)) , where x is drawn from \sqrt{d-1}\mathbb{S}^{d-1} , and then clamped to have all coordinates of x\in[-1,1] . We have f^{*}(x)=\phi(x_{1})=\mathbb{E}_{w\sim\rho^{*}}\sigma(x^{\top}w) , where \sigma is the ReLU activation, and w\in\mathbb{R}^{d} . Inspired by [ 14 ] , we study a class of problems f^{\gamma} parameterized by \gamma , the largest value such that when d=2 , the \gamma -Sobolev norm of \rho^{*} is finite 6 6 6 The \gamma -Sobolev norm of a function g is \mathopen{}\mathclose{{\left(\sum_{k\in\mathbb{Z}^{d}\setminus 0}(2\pi|k|)^{2\gamma}|\hat{g}_{k}|^{2}}}\right)^{1/2} , where \hat{g}_{k}:=\int_{\mathbb{S}^{d-1}}g(x)\exp(-2\pi ikx)d\omega(x) is the Fourier coefficient of g . . This in turn governs the smoothness of \phi , where larger \gamma means more smooth. These target functions are pictured in Figure 4 , and described mathematically in Appendix B , along with further experimental details. [ 14 ] showed that for a variant of this problem that is equivalent to our setting in the case that d=2 , when both layers are trained, the local convergence rate is of order t^{-(\gamma+1)} . In Figure 1 we plot both the loss, which approximates \mathcal{L}(\rho_{t}^{\textsc{MF}}) , and the integral of the square root of the loss R_{t}:=\int_{s=0}^{t}\sqrt{\mathcal{L}(\rho_{t}^{\textsc{MF}})}ds , which is the quantity Theorem 2 assumes to be bounded to guarantee uniform-in-time PoC. We train up to T=512 time. We observe that when d=2 and \gamma=1 , the least smooth setting, the R_{t} does not converge, while for larger values of \gamma , R_{t} does converge (see Figure 5 ). For d=128 , plotted in Figure 1 , we observe convergence at all values of \gamma , though R_{t} is larger for smaller \gamma . In all cases we observe global convergence. Figure 1 : Approximate loss \mathcal{L}(\rho_{t}^{\textsc{MF}}) (left) and \int_{s=0}^{t}\sqrt{\mathcal{L}(\rho_{s}^{\textsc{MF}})}ds (right) for d=128 . We train both layers. Two-dimensional examples We illustrate low-dimensional examples where \mathcal{S}=\mathbb{S}^{2} , and we choose the arcosine kernel arising from the ReLU activation. We implement the Eulerian dynamics by gridding the domain and performing upwind integration to preserve the probability mass. Figure 2 illustrates several targets with varying smoothness. In qualitative agreement with the local analysis of [ 14 ] , in the smooth settings we observe a sufficiently fast decay of the population loss, leading to an effective PoC rate. In contrast, the singular target measure does not satisfy our decay assumptions, even though we observe global mean-field convergence. Figure 2 : examples of target densities (top), alongside the behavior of \mathcal{L}_{t} (middle) and the associated R_{t}=\int_{0}^{t}\sqrt{\mathcal{L}_{s}}ds (bottom). 6 Conclusions and Future Work The Mean-field Wasserstein gradient flow dynamics offer one of the clearest analytic windows into the training of overparameterized shallow neural networks, but their practical relevance ultimately depends on how accurately finite-width networks track this continuum limit. In this work we studied the long-time behavior of fluctuations introduced by several forms of discretization of these idealized dynamics, such as finite neurons or data samples. Our main contribution is a novel uniform-in-time PoC bound that, focusing on function error, exploits the rate of convergence of the mean-field dynamics, overcoming the short-time barriers of standard Grönwall estimates. As a takeaway, whenever \int_{0}^{\infty}\sqrt{\mathcal{L}_{t}}dt=O(\log d) , one can attain population loss \epsilon using \text{poly}(d)/\epsilon resources, including neurons, training samples and gradient steps. Our result thus reinforces the powerful role of mean-field descriptions in providing novel algorithmic guarantees. While applicable on a variety of idealized learning scenarios, our work leaves several interesting avenues for future research. Two concrete questions are to understand (i) whether other functionals, besides the loss functional, enjoy the same uniform-in-time PoC under our same assumptions, and (ii) the necessity of our assumption on the MF convergence rate — by either weakening it to slower rates \mathcal{L}_{t}\lesssim t^{-c} , c<2 , or else by finding a counter-example. In that respect, as exhibited by empirical scaling laws [ 29 , 7 ] , many tasks do not enjoy such fast convergence rates \mathcal{L}_{t}\lesssim t^{-2} , and further, many problems exhibit dimension-dependent burn-in times to escape saddles. Both of these cases require novel technical tools to avoid exponential dependencies. Thinking bigger, another tantalizing question is whether our tools can be extended to other NN models where mean-field formulations have proven useful, such as Resnets [ 17 ] or Transformers [ 23 ] , or even more broadly to interacting particle systems evolving under deterministic gradient dynamics. Appendix A Proofs of Assumptions 2 , 3 and Lemma 2 A.1 Notations Throughout this section, we will use the following notation, which builds upon the notation in our setup from the main body. \displaystyle F(w) \displaystyle:=\mathbb{E}_{(x,y)\sim\mathcal{D}}y\sigma(w^{\top}x) (A.1) \displaystyle F^{\prime}(w) \displaystyle:=P_{w}\nabla_{w}F(w) (A.2) and \displaystyle K(w,w^{\prime}) \displaystyle:=\mathbb{E}_{x\sim\mathcal{D}}\sigma(w^{\prime\top}x)\sigma(w^{\top}x) (A.3) \displaystyle K^{\prime}(w,w^{\prime}) \displaystyle:=P_{w}\nabla_{w}K(w,w^{\prime}). (A.4) Let \mathcal{H} be the RKHS generated by the kernel K , with inner product \langle{,}\rangle_{\mathcal{H}} . By the gradient flow dynamics in Equation 2.2 , we have \displaystyle\textstyle\frac{d}{dt}w=\nu_{\mathcal{D}}(w,\rho):=P_{w}\nabla_{w}F(w)-P_{w}\nabla_{w}\mathbb{E}_{w^{\prime}\sim\rho}K(w,w^{\prime}). (A.5) We also define the empirical local Hessian \bar{D}_{t} (closely related to D_{t} ), where the expectation is taken over \bar{\rho}^{m}_{t} instead of \rho_{t}^{\textsc{MF}} : \displaystyle\bar{D}_{t}(w) \displaystyle:=\nabla_{\xi_{t}(w)}\nu(\xi_{t}(w),\bar{\rho}^{m}_{t})=\nabla_{\xi_{t}(w)}F^{\prime}(\xi_{t}(w))-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}\nabla_{\xi_{t}(w)}K^{\prime}(\xi_{t}(w),w^{\prime}). (A.6) \displaystyle D_{t}(w) \displaystyle=\nabla_{\xi_{t}(w)}\nu(\xi_{t}(w),\rho_{t}^{\textsc{MF}})=\nabla_{\xi_{t}(w)}F^{\prime}(\xi_{t}(w))-\mathbb{E}_{w^{\prime}\sim\rho_{t}^{\textsc{MF}}}\nabla_{\xi_{t}(w)}K^{\prime}(\xi_{t}(w),w^{\prime}). (A.7) A.2 Concentration Lemmas The main goal of this section is to show that under Assumption Regularity , the following two uniform-convergence guarantees hold with the values \epsilon_{n} and \epsilon_{m} given in the introduction. We state these guarantees as assumptions, because as per Remark 2 , they (along with Assumption 1 ) suffice to yield our main results. See 2 See 3 Before proving that these assumptions hold under Assumption Regularity , we show that they suffice to yield the desired bounds which will be integral in proving Lemma 2 . Lemma 15 (cf. [ 24 ] , Lemma 19) . Suppose that Assumption 3 holds and Lemma 7 2 , 3 hold, and that for all s\leq t<\infty , we have that the random variable \|w\| for w\sim\rho_{s}^{\textsc{MF}} is \kappa_{t} -sub-Gaussian for \kappa_{t}\geq 1 . Then with probability 1-m^{-\Theta(1)} over the initialization \bar{\rho}^{m}_{0} , for all t<\infty and i\in[m] , the following holds: \displaystyle\|\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})\| \displaystyle\leq\epsilon_{m}\kappa_{t}\log(t+1). \displaystyle\|D_{t}(i)-\bar{D}_{t}(i)\| \displaystyle\leq\epsilon_{m}\kappa_{t}\log(t+1). Proof. [Proof of Lemma 15 ] Fix t<\infty and w\in\mathcal{S} . By Equation ( A.5 ), we have that \displaystyle\nu(w,\rho_{t}^{\textsc{MF}})-\nu(w,\bar{\rho}^{m}_{t}) \displaystyle:=P_{w}\mathopen{}\mathclose{{\left(\mathbb{E}_{w^{\prime}\sim\rho_{t}^{\textsc{MF}}}\nabla_{w}K(w,w^{\prime})-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}\nabla_{w}K(w,w^{\prime})}}\right) (A.8) Thus \displaystyle\|\nu(w,\rho_{t}^{\textsc{MF}})-\nu(w,\bar{\rho}^{m}_{t})\|\leq\sup_{u\in\mathbb{S}^{d-1}}\mathbb{E}_{w^{\prime}\sim\rho_{t}^{\textsc{MF}}}u^{\top}\nabla_{w}K(w,w^{\prime})-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}u^{\top}\nabla_{w}K(w,w^{\prime}). (A.9) Plugging in Assumption 3 yields that with probability 1-\delta/(1+t)^{2} , for \delta=\epsilon_{m}^{2}m^{-\Theta(1)} , \displaystyle\sup_{w\in\mathcal{S}}\mathopen{}\mathclose{{\left\|\mathbb{E}_{w^{\prime}\sim\rho_{0}}\nabla_{w}K(w,\xi_{t}(w^{\prime}))-\frac{1}{m}\sum_{i=1}^{m}\nabla_{w}K(w,\xi_{t}(w_{i}))}}\right\| \displaystyle\leq\epsilon_{m}\kappa_{t}\log(1+t)/2. (A.10) Now we need to take a union bound over all t<\infty . Create a net over [0,\infty) of spacing \frac{\epsilon_{m}}{4C_{\text{reg}}} . By a union bound, with probability at least \displaystyle 1- \displaystyle\delta\sum_{k=0}^{\infty}\mathopen{}\mathclose{{\left(\frac{1}{1+k\frac{\epsilon_{m}}{6C_{\text{reg}}}}}}\right)^{2}\geq 1-\frac{\delta 16C_{\text{reg}}^{2}}{\epsilon_{m}^{2}}\geq 1-m^{-\Theta(1)}, (A.11) for any t in the net, we have \|\nu(w,\rho_{t}^{\textsc{MF}})-\nu(w,\bar{\rho}^{m}_{t})\|\leq\frac{\epsilon_{m}\kappa_{t}\log(t+1)}{2}. Now by Lemma 7 3 , for any s,t<\infty , and any w_{0} , we have \displaystyle\|\xi_{t}(w_{0})-\xi_{s}(w_{0})\| \displaystyle\leq C_{\text{reg}}|t-s|\sup_{w\in\mathcal{S}}\sup_{r\in[s,t]}\nu(w,\rho_{r}^{\textsc{MF}}) (A.12) \displaystyle\leq C_{\text{reg}}|t-s|\mathopen{}\mathclose{{\left(1+\sup_{r\in[s,t]}\mathbb{E}_{w^{\prime}\sim\rho_{r}^{\textsc{MF}}}\|w^{\prime}\|}}\right) (A.13) \displaystyle\leq 2\kappa_{t}C_{\text{reg}}|t-s|. (A.14) Thus, for any t<\infty , there exists an s in the net of distance at most \frac{\epsilon_{m}}{4C_{\text{reg}}} . By a standard triangle inequality argument, we attain that with the probability 1-m^{-\Theta(1)} , for all w\in\mathcal{S} and t<\infty , we have \displaystyle\|\nu(w,\rho_{t}^{\textsc{MF}})-\nu(w,\bar{\rho}^{m}_{t})\|\leq\epsilon_{m}\kappa_{t}\log(t+1). (A.15) The argument for proving concentration for \bar{D}_{t}(w) uniformly over w and t is similar. We can write D_{t}(w)-\bar{D}_{t}(w)=\mathbb{E}_{w^{\prime}\sim\rho_{0}}\nabla_{\xi_{t}(w)}P_{\xi_{t}(w)}\nabla_{\xi_{t}(w)}K(\xi_{t}(w),\xi_{t}(w^{\prime}))-\frac{1}{m}\sum_{i=1}^{m}\nabla_{\xi_{t}(w)}P_{\xi_{t}(w)}\nabla_{\xi_{t}(w)}K(\xi_{t}(w),\xi_{t}(w_{i})), and thus we care about \displaystyle X_{t}:=\sup_{u,v\in\mathbb{S}^{d-1},w\in\mathcal{S}}\mathbb{E}_{z\sim\rho_{t}^{\textsc{MF}}}u^{\top}\nabla_{w}P_{w}\nabla_{w}K(w,z)v-\mathbb{E}_{z\sim\bar{\rho}^{m}_{t}}u^{\top}\nabla_{w}P_{w}\nabla_{w}K(w,z)v (A.16) Assumption 3 now gives the result that with probability 1-4\delta/(t+1)^{2} , X_{t}\leq\frac{1}{2}\kappa_{t}\epsilon_{m}\log(t+1) . Again we need to show Lipschitzness in t : we have by Lemma 7 2 and ( A.12 ) above that \displaystyle X_{t}-X_{s} \displaystyle\leq 2\sup_{w^{\prime}\in\mathcal{S}}\|\xi_{t}(w^{\prime})-\xi_{s}(w^{\prime})\|\sup_{z,\xi\in\mathcal{S}}\mathopen{}\mathclose{{\left\|\nabla_{z}\nabla_{\xi}P_{\xi}\nabla_{\xi}K(\xi,z)}}\right\| (A.17) \displaystyle\leq 2(2\kappa_{t}C_{\text{reg}}|t-s|)C_{\text{reg}}. (A.18) The result now follows by the argument before by taking a net in t over [0,\infty) of spacing \frac{\epsilon_{m}}{8C_{\text{reg}}^{2}} . ∎ Lemma 16 (cf. Lemma 23 in [ 24 ] ) . Suppose Assumption 2 holds. Then with probability 1-n^{-\Theta(1)} , uniformly over all w\in\mathcal{S} , and all \rho\in\mathcal{P}(\mathcal{S}) , we have \|\nu_{\hat{\mathcal{D}}}(w,\rho)-\nu(w,\rho)\|\leq\epsilon_{n}\mathopen{}\mathclose{{\left(1+\mathbb{E}_{w\sim\rho}\|w\|}}\right), and |\mathcal{L}_{\hat{\mathcal{D}}}(\rho)-\mathcal{L}_{\mathcal{D}}(\rho)|\leq\epsilon_{n}\mathopen{}\mathclose{{\left(2+\mathbb{E}_{w\sim\rho}\|w\|}}\right)^{2}, Proof. For the first bound, the velocity is linear in \rho , so it suffices to prove that uniformly over w and w^{\prime} , we have \displaystyle\|\nu_{\hat{\mathcal{D}}}(w,\delta_{w^{\prime}})-\nu(w,\delta_{w^{\prime}})\|\leq\epsilon_{n}(1+\|w^{\prime}\|). (A.19) We expand \displaystyle\nu_{\hat{\mathcal{D}}}(w,\delta_{w^{\prime}})=P_{w}\mathbb{E}_{x,y\sim\hat{\mathcal{D}}}(y-\sigma(w^{\prime\top}x))\sigma^{\prime}(w^{\top}x)x. (A.20) The result now follows immediately from Assumption 2 . For the second bound, we have \displaystyle\mathcal{L}_{\hat{\mathcal{D}}}(\rho)-\mathcal{L}_{\mathcal{D}}(\rho) \displaystyle=\mathbb{E}_{(x,y)\sim\hat{\mathcal{D}}}\mathbb{E}_{w,w^{\prime}\sim\rho}(\sigma(w^{\top}x)-y)(\sigma({w^{\prime}}^{\top}x)-y)-\mathbb{E}_{(x,y)\sim\mathcal{D}}\mathbb{E}_{w,w^{\prime}\sim\rho}(\sigma(w^{\top}x)-y)(\sigma({w^{\prime}}^{\top}x)-y) (A.21) \displaystyle\qquad-\mathbb{E}_{(x,y)\sim\hat{\mathcal{D}}}(f^{*}(x)-y)^{2}+\mathbb{E}_{(x,y)\sim\mathcal{D}}(f^{*}(x)-y)^{2}, (A.22) so moving the double expectation over \rho outside, and employing Assumption 2 we have with probability 1-n^{-\Theta(1)} \displaystyle|\mathcal{L}_{\hat{\mathcal{D}}}(\rho)-\mathcal{L}_{\mathcal{D}}(\rho)| \displaystyle\leq\epsilon_{n}\mathbb{E}_{w,w^{\prime}\sim\rho}(1+\|w\|)(1+\|w^{\prime}\|)+|\mathbb{E}_{(x,y)\sim\hat{\mathcal{D}}}(f^{*}(x)-y)^{2}-\mathbb{E}_{(x,y)\sim\mathcal{D}}(f^{*}(x)-y)^{2}| (A.23) \displaystyle\leq\epsilon_{n}\mathopen{}\mathclose{{\left(2+\mathbb{E}_{w\sim\rho}\|w\|}}\right)^{2}. (A.24) ∎ The following two lemmas use standard techniques from empirical process theory. Assume that all constants \kappa and \kappa_{x} throughout are at least 1 in what follows. Lemma 17 (Covering Numbers) . Suppose that \sigma(0),\sigma^{\prime}\leq C , \text{Var}(\sigma^{\prime})_{[t,\infty)},\text{Var}(\sigma^{\prime})_{[-t,-\infty)}\leq\frac{C}{1+t^{1/(Cd)}} and consider the following functions classes from \mathbb{R}^{d} or \mathbb{R}^{d}\times\mathbb{R} to \mathbb{R} . \displaystyle\mathcal{G}^{(j)} \displaystyle=\{g_{u,w,s}((x,y)):=y\langle{u,x^{\otimes j}}\rangle\mathbf{1}(w^{\top}x\geq s):u\in({\mathbb{S}^{d-1}})^{\otimes j},w\in\mathbb{R}^{d},s\in\mathbb{R}\} (A.25) \displaystyle\mathcal{G^{\prime}} \displaystyle=\{g_{u,w,\xi,s}(x):=\frac{1}{1+\|\xi\|}(u^{\top}x)\mathbf{1}(w^{\top}x\geq s)\sigma(\xi^{\top}x):u\in\mathbb{S}^{d-1},w,\xi\in\mathbb{R}^{d},s\in\mathbb{R}\} (A.26) \displaystyle\mathcal{G^{\prime\prime}} \displaystyle=\{g_{w,\xi}((x,y)):=\frac{1}{1+\|\xi\|}\frac{1}{1+\|w\|}(\sigma(\xi^{\top}x)-y)(\sigma(w^{\top}x)-y):w,\xi\in\mathbb{R}^{d}\} (A.27) There exists a universal constant C , such for any distribution P on (x,y) with \mathbb{E}_{x\sim P}\|x\|^{2}\leq\kappa_{x}^{2}d and \mathbb{E}y^{2}\leq\kappa_{x}^{2} , we have for \bar{\mathcal{G}}\in\{\mathcal{G}^{(1)},\mathcal{G}^{(2)},\mathcal{G}^{\prime},\mathcal{G}^{\prime\prime}\} , \displaystyle\log\mathopen{}\mathclose{{\left(N\mathopen{}\mathclose{{\left(\epsilon,\mathcal{\bar{\mathcal{G}}},L_{2}(P)}}\right)}}\right)\leq\Theta\mathopen{}\mathclose{{\left(Cd\log\mathopen{}\mathclose{{\left(\kappa_{x}Cd/\epsilon}}\right)}}\right), (A.28) where N(\epsilon,\bar{\mathcal{G}},L_{2}(P)) denotes the covering number (ie. there exists a net of this size where for any g\in\bar{\mathcal{G}} , there is a g^{\prime} in the net with \mathbb{E}_{x\sim P}(g(x)-g^{\prime}(x))^{2}\leq\epsilon^{2} .) Further, if x\sim P is \kappa_{x} -subguassian, then with probability 1-\delta over n i.i.d. samples x_{i}\sim P for n\geq d , we have for any \bar{\mathcal{G}} , \displaystyle\sup_{g\in\bar{\mathcal{G}}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i}g(x_{i})-\mathbb{E}_{x\sim P}g(x)}}\right|\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\sqrt{\frac{Cd\log^{2}(d/\delta)}{n}}}}\right).. (A.29) Proof. First we prove that \mathcal{G}:=\mathcal{G}^{(1)} is a VC subgraph of VC dimension \Theta(d) . It suffices to bound the VC dimension of the subgraph class \operatorname{subgraph}(\mathcal{G}):=\mathopen{}\mathclose{{\left\{(x,t)\in\mathbb{R}^{d}\times\mathbb{R}:t0\bigr)\quad\text{or}\quad\bigl(w^{\top}x_{i}-s<0\ \text{and}\ t_{i}<0\bigr). Thus, once the sample points are fixed, the induced labeling is determined by the signs of the 2n affine functions P_{i}(u,w,s):=w^{\top}x_{i}-s,\qquad Q_{i}(u,w,s):=u^{\top}y_{i}x_{i}-t_{i},\qquad i=1,\dots,n. These are affine functions of the 2d+1 real parameters (u,w,s) . Since relaxing the constraint u\in\mathbb{S}^{d-1} to u\in\mathbb{R}^{d} can only increase the number of sign patterns, Warren’s theorem implies that the number of possible labelings of the n fixed points is at most \mathopen{}\mathclose{{\left(\frac{8en}{2d+1}}}\right)^{2d+1} provided 2n\geq 2d+1 ; the remaining case is trivial. If the n points were shattered, then all 2^{n} labelings would be realized. Therefore 2^{n}\leq\mathopen{}\mathclose{{\left(\frac{8en}{2d+1}}}\right)^{2d+1}. Writing k=2d+1 and r=n/k , this gives 2^{r}\leq 8er . The latter inequality fails for all r\geq 7.5 . Hence n<7.5(2d+1)\leq 24d for d\geq 1 . Thus no set of more than 24d points can be shattered, and so \operatorname{VCsubgraph}(\mathcal{G})\leq 24d , as desired. The bound \exp\mathopen{}\mathclose{{\left(\Theta\mathopen{}\mathclose{{\left(d\log(\kappa_{x}Cd/\epsilon)}}\right)}}\right) on the covering numbers now follows immediately from [ 50 , Theorem 2.6.7] , with envelope function \|yx\| . The proof for \mathcal{G}^{(2)} is nearly identical. The only difference is that once the sample points are fixed, the induced labeling is determined by the signs of the 2n degree \leq 2 functions P_{i}(u,v,w,s):=w^{\top}x_{i}-s,\qquad Q_{i}(u,v,w,s):=(u^{\top}x_{i})(v^{\top}x_{i})-t_{i}, These are polynomial functions of the 3d+1 real parameters (u,v,w,s) . Warren’s theorem gives the same result but with a slightly worse constant. Now to bound the covering numbers of \mathcal{G}^{\prime} , we use the net N_{\mathcal{G}} for \mathcal{G} with y\equiv 1 , at scale \epsilon/3 , as a starting point. Write \xi=r\bar{\xi} , where r\in\mathbb{R}_{+} , and \bar{\xi}\in\mathbb{S}^{d-1} . Now create nets N_{\mathbb{S}^{d-1}} and N_{\mathbb{R}_{+}} over \mathbb{S}^{d-1} and [0,R(\epsilon)] respectively of spacing \frac{\epsilon}{4C\kappa_{x}^{2}} . We claim that for R(\epsilon) large enough, N_{\mathcal{G}}\times N_{\mathbb{S}^{d-1}}\times N_{\mathbb{R}_{+}} is a covering net for \mathcal{G}^{\prime} at scale \epsilon . Indeed, for r\leq r^{\prime}\in\mathbb{R}_{+} , we have \displaystyle\mathbb{E}_{x}(g_{u,w,r\bar{\xi},s}(x)-g_{u,w,r^{\prime}\bar{\xi},s}(x))^{2} \displaystyle\leq\mathbb{E}_{x}\sup_{\tilde{r}\in[r,r^{\prime}]}\frac{4}{(1+\tilde{r})^{4}}\mathopen{}\mathclose{{\left((x^{\top}u)\mathbf{1}(w^{\top}x)\geq s)\sigma(\tilde{r}\bar{\xi}^{\top}x)(r-r^{\prime})}}\right)^{2} (A.30) \displaystyle\qquad+\mathbb{E}_{x}\sup_{\tilde{r}\in[r,r^{\prime}]}\frac{4}{(1+\tilde{r})^{4}}\mathopen{}\mathclose{{\left((x^{\top}u)\mathbf{1}(w^{\top}x)\geq s)\sigma^{\prime}(\tilde{r}\bar{\xi}^{\top}x)(\bar{\xi}^{\top}x)(r-r^{\prime})}}\right)^{2} (A.31) \displaystyle\leq O\mathopen{}\mathclose{{\left(\kappa_{x}^{4}C^{2}(r-r^{\prime})^{2}}}\right). (A.32) Similarly for \bar{\xi},\bar{\xi}^{\prime}\in\mathbb{S}^{d-1} , \displaystyle\mathbb{E}_{x}(g_{u,w,r\bar{\xi},s}(x)-g_{u,w,r\bar{\xi}^{\prime},s}(x))^{2} \displaystyle\leq\frac{1}{(1+r)^{2}}\mathbb{E}_{x}\sup_{\tilde{\xi},v\in\mathbb{S}^{d-1}}\mathopen{}\mathclose{{\left((x^{\top}u)\mathbf{1}(w^{\top}x)\geq s)\sigma^{\prime}(r\bar{\xi}^{\top}x)(r\|\bar{\xi}-\bar{\xi}^{\prime}\|v^{\top}x)}}\right)^{2} (A.33) \displaystyle\leq O(\kappa_{x}^{4}C^{2}\|\bar{\xi}-\bar{\xi}^{\prime}\|^{2}). (A.34) Finally, with for any u,w,\bar{\xi},s,x , we have that g_{u,w,r\bar{\xi},s}(x) reaches a limit as r\rightarrow\infty in the following quantitative sense: g_{u,w,r\bar{\xi},s}(x)-g_{u,w,r^{\prime}\bar{\xi},s}(x)\leq(u^{\top}x)\mathbf{1}(w^{\top}x\geq s)\frac{3C(1+\|x\|)}{1+\min(r,r^{\prime})^{\frac{1}{Cd}}}. Indeed, for any y\in\mathbb{R}_{+} (a similar argument holds for y\leq 0 ), with \sigma(\infty):=\lim_{t\rightarrow\infty}\sigma^{\prime}(t) , we have \displaystyle\mathopen{}\mathclose{{\left|\frac{\sigma(ry)}{1+r}-\lim_{r\rightarrow\infty}\frac{\sigma(ry)}{1+r}}}\right| \displaystyle\leq\mathopen{}\mathclose{{\left|\frac{\sigma(0)}{1+r}}}\right|+\frac{1}{1+r}\int_{t=0}^{ry}\mathopen{}\mathclose{{\left|\sigma^{\prime}(t)-\sigma^{\prime}(\infty)}}\right|dt-\mathopen{}\mathclose{{\left|\frac{y\sigma^{\prime}(\infty)}{1+r}}}\right| (A.35) \displaystyle\leq\frac{C(1+y)}{1+r}+\frac{\int_{t=0}^{yr}\frac{C}{1+t^{\frac{1}{Cd}}}dt}{1+r} (A.36) \displaystyle\leq\frac{C(1+y)}{1+r}+\frac{2C(yr)^{1-\frac{1}{Cd}}}{(1+r)}\leq\frac{3C(1+y)}{1+r^{\frac{1}{Cd}}}. (A.37) Thus it suffices to choose R(\epsilon)\geq\mathopen{}\mathclose{{\left(O(C\kappa_{x}\sqrt{d}/\epsilon)}}\right)^{Cd} , such that for any r^{\prime} there exists an r in the net such that \|g_{u,w,r\bar{\xi},s}-g_{u,w,r\bar{\xi},s}\|_{L_{2}(P)}\leq\epsilon . We thus have that \displaystyle\log(|N_{\mathcal{G}}\times N_{\mathbb{S}^{d-1}}\times N_{\mathbb{R}_{+}}|)\leq\log(N_{\mathcal{G}})+O(d\log(C\kappa_{x}/\epsilon))+O(\log(C\kappa_{x}/\epsilon)+Cd\log(C\kappa_{x}d/\epsilon))\leq O(Cd\log(dC\kappa_{x}/\epsilon)), (A.38) as desired. The argument for \mathcal{G}^{\prime\prime} is similar, though we do not need to use the original N_{G} . It suffices create nets over (\mathbb{S}^{d-1})^{2}\times[0,R(\epsilon)]^{2} as above, and check the Lipschitzness as above. The rest of the lemma on uniform convergence follows from standard arguments from empirical process theory. For the high probability uniform convergence bound, first we use symmetrization to show that \displaystyle\mathbb{E}\mathopen{}\mathclose{{\left[\sup_{g\in\bar{\mathcal{G}}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i}g(x_{i})-\mathbb{E}_{x\sim P}g(x)}}\right|}}\right]\leq 2\mathcal{R}_{n}(\bar{\mathcal{G}}), (A.39) where \mathcal{R}_{n} denotes the n -sample Rademacher complexity. Now by Dudley’s entropy integral bound (see eg. [ 51 , Theorem 5.22] , since \sup_{g\in\bar{\mathcal{G}}}\|g\|_{L_{2}(P)}\leq O(C\kappa_{x}^{2}) we have that \displaystyle\mathcal{R}_{n}(\bar{\mathcal{G}})\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\sqrt{\frac{Cd\log(d)}{n}}}}\right). (A.40) Now to upgrade to a high probability bound on the uniform convergence, using the concentration in equality in [ 3 , Theorem 4] , yields \displaystyle\mathbb{P}\mathopen{}\mathclose{{\left[\sup_{g\in\bar{\mathcal{G}}}|P_{n}g-\mathbb{E}g|\geq 2\mathbb{E}\sup_{g\in\mathcal{G}}|P_{n}\tilde{g}-\mathbb{E}\tilde{g}|+t}}\right]\leq 2\exp\mathopen{}\mathclose{{\left(-\frac{t^{2}n}{4s^{2}}}}\right)+2\exp\mathopen{}\mathclose{{\left(-\frac{\Theta(tn)}{\kappa_{x}^{2}dC}}}\right), (A.41) where s^{2}:=\sup_{g\in\bar{\mathcal{G}}}\mathbb{E}g(x)^{2}\leq C^{2}\kappa_{x}^{4} . Plugging in \displaystyle t=\frac{\Theta(d\kappa_{x}^{2}C\log(1/\delta))}{n}+\sqrt{\frac{4C^{2}\kappa_{x}^{2}\log(1/\delta)}{n}}, (A.42) yields that with probability at most \delta , for n\geq d , \displaystyle\sup_{g\in\bar{\mathcal{G}}}|P_{n}g-\mathbb{E}g|\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\sqrt{\frac{Cd\log(d)}{n}}+\frac{d\kappa_{x}^{2}C\log(1/\delta)}{n}+\sqrt{\frac{4C^{2}\kappa_{x}^{2}\log(1/\delta)}{n}}}}\right)\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\sqrt{\frac{Cd\log^{2}(d/\delta)}{n}}}}\right). (A.43) ∎ Lemma 18 . Suppose \sigma satisfies the conditions of Lemma 17 for some C , and \phi has total variation and |\phi|_{\infty} bounded by C . Further suppose x\sim P_{x} is \kappa_{x} subgaussian, and y is \kappa_{x} -subgaussian, and \|z\| is \kappa_{z} -subgaussian with z\sim P_{z} . Let \displaystyle\mathcal{F} \displaystyle:=\{f_{u,w}((y,x)):=\sigma^{\prime}(w^{\top}x)(u^{\top}x):u\in\mathbb{S}^{d-1},w\in\mathbb{R}^{d}\} (A.44) \displaystyle\mathcal{F^{\prime}} \displaystyle:=\{f_{u,w,\xi}(x):=\frac{1}{1+\|\xi\|}\sigma^{\prime}(w^{\top}x)(u^{\top}x)\sigma(\xi^{\top}x):u\in\mathbb{S}^{d-1},w,\xi\in\mathbb{R}^{d}\} (A.45) \displaystyle\mathcal{H}^{(j)} \displaystyle:=\{h_{u,w}(z):=\mathbb{E}_{x\sim P_{x}}\phi(w^{\top}x)\langle{u,x^{\otimes j}\rangle}\sigma(z^{\top}x):u\in(\mathbb{S}^{d-1})^{\otimes j},w\in\mathbb{R}^{d}\} (A.46) Then for any \delta>0 , with probability at least 1-\delta , with x_{i} drawn i.i.d. from P_{x} , for \bar{\mathcal{F}}\in\{\mathcal{F},\mathcal{F}^{\prime}\} , we have for n\geq d , \displaystyle\sup_{f\in\bar{\mathcal{F}}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\mathbb{E}_{x\sim P_{x}}f(x)}}\right|\leq\Theta\mathopen{}\mathclose{{\left(C^{2}\kappa_{x}^{2}\sqrt{\frac{Cd\log^{2}(d/\delta)}{n}}}}\right), (A.47) and with z_{i} drawn i.i.d. from P_{z} , for j\in\{1,2\} , \displaystyle\sup_{h\in\mathcal{H}^{(j)}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}h(z_{i})-\mathbb{E}_{z\sim P_{z}}h(z)}}\right|\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{1+j}\kappa_{z}\sqrt{\frac{Cd\log^{2}(Cd/\delta)}{n}}}}\right) (A.48) Proof. First observe that because \sigma has total variation bounded by C , we can write \displaystyle\sigma(y)=A+\int_{s=-\infty}^{\infty}\mathbf{1}(y\geq s)\mu(ds), (A.49) for some constant A\in[-C,C] , and some signed measure \mu with \int_{s=-\infty}^{\infty}|\mu(ds)|\leq C . Thus for \bar{\mathcal{F}}\in\{\mathcal{F},\mathcal{F}^{\prime}\} , we have \displaystyle\sup_{f\in\bar{\mathcal{F}}} \displaystyle\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\mathbb{E}_{x\sim P_{x}}f(x)}}\right|\leq(A+C)\sup_{s\in\mathbb{R},u\in\mathbb{S}^{d-1},w\in\mathbb{R}^{d}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}g_{u,w,s}(x_{i})-\mathbb{E}_{x\sim P_{x}}g_{u,w,s}(x)}}\right|, (A.50) for g_{u,w,s} defined in Lemma 17 . Using the result of Lemma 17 then yields that with probability 1-\delta , \displaystyle\sup_{f\in\mathcal{F}} \displaystyle\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-\mathbb{E}_{x\sim P_{x}}f(x)}}\right|\leq\Theta\mathopen{}\mathclose{{\left(C^{2}\kappa_{x}^{2}\sqrt{\frac{Cd\log^{2}(d/\delta)}{n}}}}\right). (A.51) For \mathcal{H}:=\mathcal{H}^{(1)} , the proof is slightly more complicated. Define \displaystyle h^{\prime}_{u,w,s}(z):=\mathbb{E}_{x\sim P_{x}}(u^{\top}x)\mathbf{1}(w^{\top}x\geq s)\sigma(z^{\top}x), (A.52) and \mathcal{H}^{\prime}=\{h^{\prime}_{u,w,s}:u\in\mathbb{S}^{d-1},w\in\mathbb{R}^{d},s\in\mathbb{R}\} . Then using the decomposition of \phi in ( A.49 ) \displaystyle\sup_{h\in\mathcal{H}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}h(z_{i})-\mathbb{E}_{z\sim P_{z}}h(z)}}\right|\leq 2C\sup_{h^{\prime}\in\mathcal{H}^{\prime}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}h^{\prime}(z_{i})-\mathbb{E}_{z\sim P_{z}}h^{\prime}(z)}}\right|. (A.53) For \mathcal{G}^{(1)} defined in Lemma 17 , define the linear operator T:\mathcal{G}^{(1)}\rightarrow\mathcal{H}^{\prime} by \displaystyle Tg_{u,w,s}(z):=\mathbb{E}_{x\sim P_{x}}g_{u,w,s}(x)\sigma(z^{\top}x). (A.54) Then by Cauchy-Schwartz, \displaystyle\|Tg-Tg^{\prime}\|^{2}_{L_{2}(P_{z})} \displaystyle=\mathbb{E}_{z\sim P_{z}}\mathopen{}\mathclose{{\left(\mathbb{E}_{x\sim P_{x}}(g(x)-g^{\prime}(x))\sigma(z^{\top}x)}}\right)^{2} (A.55) \displaystyle\leq\mathbb{E}_{z\sim P_{z}}\mathbb{E}_{x\sim P_{x}}(g(x)-g^{\prime}(x))^{2}\mathbb{E}_{x\sim P_{x}}\sigma(z^{\top}x)^{2} (A.56) \displaystyle\leq\|g-g^{\prime}\|^{2}_{L_{2}(P_{x})}C^{2}\mathbb{E}_{z}\mathbb{E}_{x}(1+|z^{\top}x|)^{2} (A.57) \displaystyle\leq\|g-g^{\prime}\|^{2}_{L_{2}(P_{x})}C^{2}(1+\kappa_{x}\mathbb{E}_{z}\|z\|)^{2} (A.58) \displaystyle\leq 2\|g-g^{\prime}\|^{2}_{L_{2}(P_{x})}C^{2}\kappa^{2}_{x}\kappa^{2}_{z}. (A.59) It follows from Lemma 17 that \displaystyle\log N(\epsilon,\mathcal{H}^{\prime},L_{2}(P_{z})) \displaystyle\leq\log N(\epsilon/(2C\kappa_{x}\kappa_{z}),\mathcal{G}^{(1)},L_{2}(P_{x})) (A.60) \displaystyle\leq Cd\log(2C\kappa_{x}\kappa_{z}d/\epsilon). (A.61) The remainder of the proof is standard, and uses the same steps as the uniform convergence bound in the proof of Lemma 17 : symmetrization, Dudley, and the concentration bound from [ 3 , Theorem 4] . Since \sup_{h^{\prime}\in\mathcal{H}^{\prime}}\|h^{\prime}\|_{L_{2}(P_{z})}\leq O(C\kappa_{x}^{2}\kappa_{z}) , we have \mathcal{R}_{n}(\mathcal{H}^{\prime})\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\kappa_{z}\sqrt{\frac{Cd\log(d)}{n}}}}\right). The result is that with probability 1-\delta , \displaystyle\sup_{h^{\prime}\in\mathcal{H}^{\prime}}\mathopen{}\mathclose{{\left|\frac{1}{n}\sum_{i=1}^{n}h^{\prime}(z_{i})-\mathbb{E}_{z\sim P_{z}}h^{\prime}(z)}}\right|\leq\Theta\mathopen{}\mathclose{{\left(C\kappa_{x}^{2}\kappa_{z}\sqrt{\frac{Cd\log^{2}(Cd/\delta)}{n}}}}\right). (A.62) Returning to ( A.53 ), this proves the lemma. The proof of \mathcal{H}^{(2)} is identical, we simply need to use the appropriate covering number bound for \mathcal{G}^{(2)} from Lemma 17 , and we lose a factor of \kappa_{x} due to the extra linear-in- x term. ∎ Lemma 19 . Suppose Assumption Regularity holds. Then for n\geq d , Assumption 2 holds for \epsilon_{n}=\frac{C_{\text{reg}}^{5}\sqrt{d}\log^{2}(dn)}{\sqrt{n}} , and with C_{\text{reg}} a polynomial factor in the C_{\text{reg}} from Assumption Regularity . Further, Assumption 3 holds for with \epsilon_{m}=\frac{C_{\text{reg}}^{6}\sqrt{d}\log(dm)}{\sqrt{m}} . Proof. For Assumption 2 , it suffices to prove that with probability 1-n^{-\Theta(1)} , uniformly over w,w^{\prime}\in\mathcal{S} , and v\in\mathbb{S}^{d-1} , we have \displaystyle\mathopen{}\mathclose{{\left|\frac{1}{1+\|w^{\prime}\|}\mathopen{}\mathclose{{\left(\mathbb{E}_{x,y\sim\hat{\mathcal{D}}}\sigma(w^{\prime\top}x)\sigma^{\prime}(w^{\top}x)x^{\top}v-\mathbb{E}_{x,y\sim\mathcal{D}}\sigma(w^{\prime\top}x)\sigma^{\prime}(w^{\top}x)x^{\top}v}}\right)}}\right| \displaystyle\leq\epsilon_{n}/2 (A.63) \displaystyle\mathopen{}\mathclose{{\left|\mathbb{E}_{x,y\sim\hat{\mathcal{D}}}y\sigma^{\prime}(w^{\top}x)x^{\top}v-\mathbb{E}_{x,y\sim\mathcal{D}}y\sigma^{\prime}(w^{\top}x)x^{\top}v}}\right| \displaystyle\leq\epsilon_{n}/2 (A.64) \displaystyle\mathopen{}\mathclose{{\left|\mathbb{E}_{x,y\sim\hat{\mathcal{D}}}(y-\sigma(w^{\top}x))(y-\sigma(w^{\prime\top}x))-\mathbb{E}_{x,y\sim\mathcal{D}}(y-\sigma(w^{\top}x))(y-\sigma(w^{\prime\top}x))}}\right| \displaystyle\leq\epsilon_{n}(1+\|w\|)(1+\|w^{\prime}\|) (A.65) For the case that \mathcal{S}=\mathbb{R}^{d} , the desired bounds follow immediately from the results for \mathcal{F} , \mathcal{F}^{\prime} , \mathcal{G}^{\prime\prime} in Lemma 18 and Lemma 17 with \delta=n^{-\Theta(1)} , C=C_{\text{reg}},\kappa_{x}=C_{\text{reg}} . The result for the case that \mathcal{S}=\mathbb{S}^{d-1} is given by standard epsilon-net arguments eg. similar to [ 24 , Lemma 23] , which can be appropriately tightened to attain this improved \epsilon_{n} using Dudley’s entropy integral. Also with probability 1-n^{-\Theta(1)} , \forall w,w^{\prime}\in\mathcal{S} , \|\nabla^{2}_{w}K_{\hat{\mathcal{D}}}(w,w^{\prime})\|\leq C_{\text{reg}}/11(1+\|w^{\prime}\|) and \|\nabla_{w}\nabla_{w^{\prime}}K_{\hat{\mathcal{D}}}(w,w^{\prime})\|\leq C_{\text{reg}}/11 . Expanding the first term, we have \displaystyle\|\nabla^{2}_{w}K_{\hat{\mathcal{D}}}(w,w^{\prime})\| \displaystyle=\sup_{u,v\in\mathbb{S}^{d-1}}\frac{1}{n}\sum_{i}\sigma^{\prime\prime}(w^{\top}x_{i})\sigma(w^{\prime\top}x_{i})(v^{\top}x_{i})(x_{i}^{\top}u)\leq C_{\text{reg}}^{2}(1+\|w^{\prime}\|)\sup_{\epsilon_{i}\in\pm 1}\frac{\|\sum_{i}x_{i}x_{i}^{\top}\|}{n} (A.66) \displaystyle\leq C_{\text{reg}}^{4}(1+\|w^{\prime}\|)\mathopen{}\mathclose{{\left(1+\sqrt{\frac{d}{n}}+\frac{d}{n}}}\right)\leq O(C_{\text{reg}}^{4}(1+\|w^{\prime}\|), (A.67) The calculation for \|\nabla_{w}\nabla_{w^{\prime}}K_{\hat{\mathcal{D}}}(w,w^{\prime})\| is similar. This yields Assumption 2 up to a polynomial factor in C_{\text{reg}} . Now for Assumption 3 for \mathcal{F} , with z_{i}\sim\rho iid, we seek to bound \displaystyle\sup_{u\in\mathbb{S}^{d-1},w\in\mathcal{S}}\mathbb{E}_{z\sim\rho}u^{\top}\nabla_{w}K(w,z)-\frac{1}{m}\sum_{i=1}^{m}u^{\top}\nabla_{w}K(w,z_{i}). (A.68) Now by definition for any u\in\mathbb{S}^{d-1} , we have \displaystyle u^{\top}\nabla_{w}K(w,z_{i})=\mathbb{E}_{x}\sigma^{\prime}(w^{\top}x)\sigma(z_{i}^{\top}x)(u^{\top}x), (A.69) so in the case that \mathcal{S}=\mathbb{R}^{d} , by Assumption 1 , we can apply the second result in Lemma 18 with \sigma=\sigma , \phi:=\sigma^{\prime} and C=C_{\text{reg}} , \kappa_{z}=\kappa_{z} , and \kappa_{x}:=C_{\text{reg}} to guarantee that with probability 1-\delta/(1+t)^{2} , \displaystyle\sup_{w\in\mathcal{S},u\in\mathbb{S}^{d-1}}\mathopen{}\mathclose{{\left\|\mathbb{E}_{z}u^{\top}\nabla_{w}K(w,z_{i})-\frac{1}{m}\sum_{i=1}^{m}u^{\top}\nabla_{w}K(w,z_{i})}}\right\| \displaystyle\leq\Theta\mathopen{}\mathclose{{\left(C_{\text{reg}}^{3}\kappa_{z}\sqrt{\frac{C_{\text{reg}}d\log^{2}(C_{\text{reg}}d/\delta)}{m}}}}\right). (A.70) Choosing \delta:=\frac{\epsilon_{m}^{2}}{16C_{\text{reg}}^{2}m(1+t)^{2}} , we have that this bound is at most \epsilon_{m}\kappa_{t}\log(1+t)/2 . The argument for proving uniform concentration over \mathcal{F}^{\prime} is similar. In the case that \mathcal{S}=\mathbb{R}^{d} , we have \displaystyle u^{\top}\nabla_{w}P_{w}\nabla_{w}K(w,z)v=\mathbb{E}_{x\sim\mathcal{D}}\sigma^{\prime\prime}(w^{\top}x)\sigma(z^{\top}x)(u^{\top}x)(x^{\top}v), (A.71) and so we can apply Lemma 18 with the activation \sigma , \phi=\sigma^{\prime\prime} , and \kappa_{z}=\kappa_{t} , and \kappa_{x}=C_{\text{reg}} to guarantee the desired result with probability 1-\delta/(1+t)^{2} . In the case that \mathcal{S}=\mathbb{S}^{d-1} , the above uniform convergence bounds follow from standard empirical process theory arguments: from Lemma 7 all the random variables are bounded since all neurons are on \mathbb{S}^{d-1} , and we can take an \epsilon -net over \mathcal{S} of size \exp(d\log(O(1/\epsilon)) . We refer also the reader to [ 24 , Lemma 19] , where a similar result was carried with a slightly worse dependence on d in \epsilon_{m} : this can be improved to our current \epsilon_{m} using Dudley’s entropy integral. ∎ A.3 Proof of Lemma 2 . \nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}}) \nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t}) \nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t}) \nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) \nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}) \nu_{\hat{D}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}) \bm{\beta}_{\infty}+\epsilon_{m}\|\xi_{t}(w_{i})-\xi_{\infty}(w_{i})\| \qquad-\mathbb{E}_{j}H_{t}(i,j)\Delta_{t}(j) D_{t}(i)\Delta_{t}(i) \leq\epsilon_{n}\approx\eta \leq\epsilon_{n}\approx\frac{1}{\sqrt{n}} Figure 3 : Decomposing \frac{d}{dt}\Delta_{t}(i)=-\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})+\nu_{\hat{D}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}) . Upper bound on the approximate differences between the terms in the rectangles are given above the arrows. Now we prove Lemma 2 , which we restate here. Note that we assume Assumptions 1 , 2 , and 3 instead of Assumption Regularity ; these three assumptions are implied by Assumption Regularity as per Lemma 19 and the discussion following Assumption 1 . Lemma 20 (Parameter-Space Error Dynamics) . Suppose Assumptions 1 , 2 , 3 hold. With probability 1-\min(m,n)^{-\Theta(1)} , for all t<\infty and i\in[m] , \frac{d}{dt}\Delta_{t}(i)=D_{t}(i)\Delta_{t}(i)-\mathbb{E}_{j\sim[m]}H_{t}(i,j)\Delta_{t}(j)+\bm{\beta}_{t}(i)+{\bm{\epsilon}_{t}(i)}, where \displaystyle\bm{\beta}_{t}(i):=P_{\xi_{t}(w_{i})}\mathopen{}\mathclose{{\left(\mathbb{E}_{j\sim[m]}\nabla K_{t}(i,j)-\mathbb{E}_{w\sim\rho_{0}}\nabla K_{t}(w_{i},w)}}\right), (A.72) and \|{\bm{\epsilon}_{t}}(i)\|\leq\kappa_{t_{\eta}}\epsilon_{n}+\kappa_{t}^{2}\epsilon_{\eta}+2\kappa_{t}\log(t+1)\epsilon_{m}+2C_{\text{reg}}\mathopen{}\mathclose{{\left(\|\Delta_{t}(i)\|^{2}+\mathbb{E}_{j}\|\Delta_{j}\|^{2}}}\right) , \|\bm{\beta}_{t}(i)\|\leq\epsilon_{m}\log(t+1) . Proof. We first decompose \frac{d}{dt}\Delta_{t}(i) into five terms: \displaystyle\frac{d}{dt}(\Delta_{t}(i)) \displaystyle=-\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})+\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) (A.73) \displaystyle=-\mathopen{}\mathclose{{\left(\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})}}\right)-\mathopen{}\mathclose{{\left(\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})-\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t})}}\right) (A.74) \displaystyle\qquad-\mathopen{}\mathclose{{\left(\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})}}\right)-\mathopen{}\mathclose{{\left(\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})}}\right) (A.75) \displaystyle\qquad-\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})+\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}). (A.76) Note: We prove the lemma ignoring any higher order terms that arise from the projection P_{\xi_{t}(w)} . In the case that \mathcal{S}=\mathbb{S}^{d-1} , following the proof of Lemma 5 in [ 24 ] , since both \xi_{t}(w_{i}) and \hat{\xi}_{t}(w_{i}) are on the sphere, we have that \langle{\xi_{t}(w_{i}),\Delta_{t}(i)\rangle}=\frac{1}{2}\|\Delta_{t}(i)\|^{2} . Thus any corrections to this analysis due to the projections will be on the order of C_{\text{reg}}\|\Delta_{t}(i)\|^{2} . First term: \nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t}) . By Equation ( A.5 ), we have \displaystyle\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t}) \displaystyle=P_{\xi_{t}(w_{i})}\mathopen{}\mathclose{{\left(\mathbb{E}_{w^{\prime}\sim\rho_{t}^{\textsc{MF}}}\nabla_{\xi_{t}(w_{i})}K(\xi_{t}(w_{i}),w^{\prime})-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}\nabla_{\xi_{t}(w_{i})}K(\xi_{t}(w_{i}),w^{\prime})}}\right) (A.77) \displaystyle=P_{\xi_{t}(w_{i})}\mathopen{}\mathclose{{\left(\mathbb{E}_{w\sim\rho_{0}}\nabla K_{t}(w_{i},w)-\mathbb{E}_{j\sim[m]}\nabla K_{t}(i,j)}}\right). (A.78) Alternatively, by Lemma 15 , we have with high probability that \|\nu(\xi_{t}(w_{i}),\rho_{t}^{\textsc{MF}})-\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})\|\leq\epsilon_{m}\kappa_{t}\log(t+1) . Second term: \nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})-\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t}) . Here we have \displaystyle\nu(\xi_{t}(w_{i}),\bar{\rho}^{m}_{t})-\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t}) \displaystyle=\nabla F(\xi_{t}(w_{i}))-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}\nabla K(\xi_{t}(w_{i}),w^{\prime}) (A.79) \displaystyle\qquad-\nabla F(\xi_{t}(w_{i}))+\mathbb{E}_{w^{\prime}\sim\hat{\rho}^{m}_{t}}\nabla K(\xi_{t}(w_{i}),w^{\prime}) (A.80) \displaystyle=-\mathbb{E}_{j}\mathopen{}\mathclose{{\left(\nabla K(\xi_{t}(w_{i}),\xi_{t}(w_{j}))-\nabla K(\xi_{t}(w_{i}),\xi_{t}(w_{j})+\Delta_{t}(j))}}\right) (A.81) \displaystyle=\mathbb{E}_{j\sim[m]}\mathopen{}\mathclose{{\left(H_{t}(i,j)\Delta_{t}(j)+\mathbf{v}_{j}}}\right), (A.82) where \|\mathbf{v}_{j}\|\leq C_{\text{reg}}\|\Delta_{t}(j)\|^{2}. Indeed we can plug Lemma 7 1 into the Lagrange error bound to attain \displaystyle\|K^{\prime}(w,w^{\prime})-K^{\prime}(w,w^{\prime}+\Delta)-\nabla_{w^{\prime}}K^{\prime}(w,w^{\prime})\Delta\| \displaystyle\leq\|\Delta\|^{2}\sup_{\tilde{w}\in\bar{\mathcal{S}}}\mathopen{}\mathclose{{\left\|\nabla^{2}_{\tilde{w}}K^{\prime}(w,\tilde{w})}}\right\|\leq\|\Delta\|^{2}C_{\text{reg}}. (A.83) Third term: \nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) . Here we have \displaystyle\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) \displaystyle=-\nabla_{w}\nu(w,\hat{\rho}^{m}_{t})|_{w=\xi_{t}(w_{i})}\Delta_{t}(i)+\mathbf{v}, (A.84) where here again we use the Lagrange error bound and 3 to bound \displaystyle\|\mathbf{v}\|\leq\|\Delta_{t}(i)\|^{2}\sup_{w\in\bar{\mathcal{S}}}\mathopen{}\mathclose{{\left\|\nabla^{2}_{w}\nu(w,\hat{\rho}^{m}_{t})}}\right\|_{op}\leq C_{\text{reg}}\|\Delta_{t}(i)\|^{2}. (A.85) Recall that we have defined \displaystyle\bar{D}_{t}(w):=\nabla_{\xi_{t}(w)}\nu(\xi_{t}(w),\bar{\rho}^{m}_{t})=\nabla_{\xi_{t}(w)}F^{\prime}(\xi_{t}(w))-\mathbb{E}_{w^{\prime}\sim\bar{\rho}^{m}_{t}}\nabla_{\xi_{t}(w)}K^{\prime}(\xi_{t}(w),w^{\prime}). (A.86) Now \displaystyle\nabla_{\xi_{t}(w_{i})}\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t}) \displaystyle=\nabla_{\xi_{t}(w_{i})}F^{\prime}(\xi_{t}(w_{i}))-\mathbb{E}_{j}\nabla_{\xi_{t}(w_{i})}K^{\prime}(\xi_{t}(w_{i}),\hat{\xi}_{t}(w_{j})) (A.87) \displaystyle=\nabla_{\xi_{t}(w_{i})}F^{\prime}(\xi_{t}(w_{i}))-\mathbb{E}_{j}\nabla_{\xi_{t}(w_{i})}K^{\prime}(\xi_{t}(w_{i}),\xi_{t}(w_{j}))+\mathbf{M}_{j} (A.88) \displaystyle=\bar{D}_{t}(i)-\mathbb{E}_{j}\mathbf{M}_{j}. (A.89) where by the Lagrange error bound and 2 , \displaystyle\|\mathbf{M}_{j}\|_{op}\leq\|\Delta_{t}(j)\|\sup_{w,w^{\prime}}\mathopen{}\mathclose{{\left\|\nabla_{w}\nabla_{w^{\prime}}K^{\prime}(w,w^{\prime})}}\right\|_{op}\leq C_{\text{reg}}\|\Delta_{t}(j)\|. (A.90) Now by Lemma 15 , we also have with high probabililty that \|D_{t}(i)-\bar{D}_{t}(i)\|\leq\epsilon_{m}\kappa_{t}\log(t+1) , and thus \displaystyle\nu(\xi_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t}) \displaystyle=-D_{t}(i)\Delta_{t}(i)+\mathbf{v}, (A.91) where \|\mathbf{v}\|\leq C_{\text{reg}}\|\Delta_{t}(i)\|\mathbb{E}_{j}\|\Delta_{t}(j)\|+\epsilon_{m}\kappa_{t}\log(t+1)\|\Delta_{t}(i)\|. Fourth term: \nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}) First observe that since t_{\eta}=\eta\lfloor{t/\eta}\rfloor , we have |t_{\eta}-t|\leq\eta . We have \displaystyle\|\hat{\xi}_{t_{\eta}}(w_{i})-\hat{\xi}_{t}(w_{i})\|\leq|t-t_{\eta}|\sup_{s\in[t,t^{\prime}]}\|\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{s}(w_{i}),\hat{\rho}^{m}_{s})\|\leq\eta\kappa_{t}C_{\text{reg}} (A.92) by Lemma 7 3 Thus by a second order analysis analogous to that in Third term , we have that \displaystyle\|\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t}^{m})\|\leq C_{\text{reg}}(\eta\kappa_{t}C_{\text{reg}}+(\eta\kappa_{t}C_{\text{reg}})^{2}). (A.93) Finally by a second order analysis analogous to that in Second term , \displaystyle\|\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t}^{m})-\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})\|\leq C_{\text{reg}}(\eta\kappa_{t}C_{\text{reg}}+(\eta\kappa_{t}C_{\text{reg}})^{2}). (A.94) It follows that \displaystyle\|\nu(\hat{\xi}_{t}(w_{i}),\hat{\rho}^{m}_{t})-\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})\|\leq 2C_{\text{reg}}(\eta\kappa_{t}C_{\text{reg}}+(\eta\kappa_{t}C_{\text{reg}})^{2})\leq\kappa_{t}^{2}\epsilon_{\eta}. (A.95) Fifth term: \nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})-\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m}) By Lemma 16 , we have with high probability: \displaystyle\|\nu(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})-\nu_{\hat{\mathcal{D}}}(\hat{\xi}_{t_{\eta}}(w_{i}),\hat{\rho}_{t_{\eta}}^{m})\| \displaystyle\leq\kappa_{t_{\eta}}\epsilon_{n}. (A.96) Final result. Putting together Equations ( A.77 ), ( A.83 ), ( A.91 ), ( A.95 ), and ( A.96 ) or their spherically corrected counterparts, we have \displaystyle\frac{d}{dt}\Delta_{t}(i) \displaystyle=D_{t}(i)\Delta_{t}(i)-\mathbb{E}_{j\sim[m],j\neq i}H_{t}(i,j)\Delta_{t}(j)+P_{\xi_{t}(w_{i})}\mathopen{}\mathclose{{\left(\mathbb{E}_{j\sim[m]}\nabla K_{t}(i,j)-\mathbb{E}_{w\sim\rho_{0}}\nabla K_{t}(w_{i},w)}}\right)+{\bm{\epsilon}}, (A.97) where \displaystyle\|{\bm{\epsilon}}\| \displaystyle\leq\epsilon_{n}+\kappa_{t}^{2}\epsilon_{\eta}+\kappa_{t}\epsilon_{m}\|\Delta_{t}(i)\|+C_{\text{reg}}\mathopen{}\mathclose{{\left(1.5\|\Delta_{t}(i)\|^{2}+\|\Delta_{t}(i)\|\mathbb{E}_{j}\|\Delta_{t}(j)\|+1.5\mathbb{E}_{j}\|\Delta_{t}(j)\|^{2}}}\right) (A.98) \displaystyle\leq\epsilon_{n}+\kappa_{t}^{2}\epsilon_{\eta}+\kappa_{t}\epsilon_{m}\log(t+1)\|\Delta_{t}(i)\|+2C_{\text{reg}}\mathopen{}\mathclose{{\left(\|\Delta_{t}(i)\|^{2}+\mathbb{E}_{j}\|\Delta_{t}(j)\|^{2}}}\right). (A.99) Using the alternative concentration approach to the first term in the decomposition, we also have the simpler result: \displaystyle\frac{d}{dt}\Delta_{t}(i) \displaystyle=D_{t}(i)\Delta_{t}(i)-\mathbb{E}_{j\sim[m],j\neq i}H_{t}(i,j)\Delta_{t}(j)+{\bm{\epsilon}}, (A.100) with \displaystyle\|{\bm{\epsilon}}\| \displaystyle\leq\epsilon_{n}+\kappa_{t}^{2}\epsilon_{\eta}+2\kappa_{t}\log(t+1)\epsilon_{m}+2C_{\text{reg}}\mathopen{}\mathclose{{\left(\|\Delta_{t}(i)\|^{2}+\mathbb{E}_{j}\|\Delta_{j}\|^{2}}}\right). (A.101) ∎ Appendix B Supplemental Experimental Details for Misspecified Sobolev single-index model For \gamma\in\{1,2,4,8\} , train a wide neural network with gradient descent on n=1024 data points (x_{i},f^{\gamma}(x_{i})) . For the best approximation of the population loss, when d=2 , we use x_{i} evenly spaced around \mathbb{S}^{1} ; otherwise we choose the x_{i} randomly on \sqrt{d-1}\mathbb{S}^{d-1} , and then truncate to be contained in [-1,1]^{d} . We use a step size of \eta=0.1 and a width of m=32768 to approximate the mean field gradient flow dynamics on the population loss. We chose these values of n,m,\eta because with twice as much granularity (choosing n,m to be two times larger, or \eta to be two times smaller), the results were very similar. We plot the results for d=2 and d=128 . For x\in[-1,1]^{d} , let \displaystyle f^{*}(x)=\sum_{k\in\mathbb{Z}}^{\infty}\hat{f}_{k}\cos(k\arccos(x_{1})) (B.1) Define f^{\gamma} by \displaystyle\hat{f}^{\gamma}_{k}=\begin{cases}\frac{1}{2}&k=0\\ \frac{1}{4}&k\pm 1\\ \frac{1}{2}(k/\sqrt{2})^{-(\gamma+2.5)}&|k|>1,\operatorname{even}\end{cases} (B.2) We show in Observation 21 that in the case that d=2 , f^{*}(x)=\mathbb{E}_{w\sim\rho^{*}}\operatorname{ReLU}(x^{\top}w) for some \rho^{*} with bounded \gamma -Sobolev norm. We chose this class of functions \{f^{\gamma}\} because it was the simplest class we could think of which could be represented by a ReLU network (this requires zero odd Fourier coefficients for k>1 ), and which had corresponding \rho^{*} with bounded \gamma -Sobolev norm. Figure 4 : Plot of \phi(x_{1})=F(\arccos(x_{1})) for various values of \gamma . The function becomes smoother as \gamma increases. Observation 21 (Representation on \mathbb{S}^{1} ) . Let d=2 , and let \theta(x)=\arccos(x_{1}) . Let F(\theta)=\sum_{k}\widehat{f}_{k}\cos(k\theta) , and assume that \widehat{f}_{k}=0 for all odd k>1 , and that for some \eta>0 , |\widehat{f}_{k}|\leq Ck^{-\gamma-2.5-\eta}\qquad\text{for all even }k\geq 2. Then there exists a finite signed measure \rho^{*} on \mathbb{S}^{1} whose density has bounded \gamma -Sobolev norm such that F(\arccos(x_{1}))=\int_{\mathbb{S}^{1}}\operatorname{ReLU}(\langle x,w\rangle)\,d\rho^{*}(w). Proof. Let \phi(t):=\operatorname{ReLU}(\cos t) . We use the complex Fourier convention h(t)=\sum_{k\in\mathbb{Z}}\widehat{h}_{k}e^{ikt},\qquad\widehat{h}_{k}=\frac{1}{2\pi}\int_{0}^{2\pi}h(t)e^{-ikt}\,dt. The Fourier coefficients of \phi are \widehat{\phi}_{k}=\begin{cases}\dfrac{1}{\pi},&k=0,\\[6.0pt] \dfrac{1}{4},&k=\pm 1,\\[6.0pt] \dfrac{(-1)^{m-1}}{\pi(4m^{2}-1)},&k=\pm 2m,\ m\geq 1,\\[6.0pt] 0,&|k|>1\text{ odd}.\end{cases} Let \mu be a finite signed measure on [0,2\pi) , and define g_{\mu}(\theta):=\int_{0}^{2\pi}\phi(\theta-\omega)\,d\mu(\omega). Writing \widehat{\mu}_{k}:=\int_{0}^{2\pi}e^{-ik\omega}\,d\mu(\omega) , we have \phi(\theta-\omega)=\sum_{k\in\mathbb{Z}}\widehat{\phi}_{k}e^{ik\theta}e^{-ik\omega}. Therefore g_{\mu}(\theta)=\sum_{k\in\mathbb{Z}}\widehat{\phi}_{k}\widehat{\mu}_{k}e^{ik\theta}. Thus the Fourier coefficients of g_{\mu} are \widehat{g}_{\mu,k}=\widehat{\phi}_{k}\widehat{\mu}_{k} . Now we will construct \rho^{*} to be the distribution of (\cos(\omega),\sin(\omega)) for \omega\sim\mu^{*} for some measure \mu^{*} on [0,2\pi) . Define the Fourier coefficients of \mu^{*} by \widehat{\mu}^{*}_{k}:=\begin{cases}\frac{\widehat{f}_{k}}{\widehat{\phi}_{k}}&\widehat{\phi}_{k}\neq 0\\ 0&\widehat{\phi}_{k}=0.\end{cases} By the assumed decay, |\widehat{\mu}^{*}_{\pm k}|\lesssim k^{-\gamma-0.5-\eta}. Therefore \sum_{k\in\mathbb{Z}}(1+k^{2})^{\gamma}|\widehat{\mu}^{*}_{k}|^{2}<\infty. Hence \mu^{*} has bounded \gamma -Sobolev norm. Now g_{\mu^{*}}(\theta)=F(\theta), Thus with x=(\cos(\theta(x)),\sin(\theta(x))) we have \displaystyle\int_{\mathbb{S}^{1}}\operatorname{ReLU}(\langle x,w\rangle)d\rho^{*}(w)=\mathbb{E}_{\omega\sim\mu^{*}}\operatorname{ReLU}(\cos(\theta(x)-w))=g_{\mu^{*}}(\theta(x))=F(\theta(x)). (B.3) But since cosine is an even function F(\theta(x))=F(-\theta(x)) , so \int_{\mathbb{S}^{1}}\operatorname{ReLU}(\langle x,w\rangle)d\rho^{*}(w)=F(\arccos(x_{1})) . ∎ Figure 5 : Approximate loss L(\rho_{t}^{\textsc{MF}}) (left) and \int_{s=0}^{t}\sqrt{L(\rho_{s}^{\textsc{MF}})}ds (right). Training both layers.