Paper deep dive
Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence
Luis Wiederhold, Nil Ayday, Debarghya Ghoshdastidar
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Randomly initialised neural networks of width $m$ converge to Gaussian processes as $m \to \infty$, with two types of quantitative bounds characterising this convergence. Finite-sample bounds compare the network with its Gaussian limit at a fixed finite sample set, on an arbitrary domain, in the quadratic Wasserstein distance $\mathcal W_2$, achieving a convergence rate of $m^{-1/2}$ with explicit constants. However, these constants grow with the number of samples, so the bound becomes uninformative as the sample set is refined. Functional bounds remove that dependence by comparing the two as random functions, at the price of spherical input, metrics weaker than $\mathcal W_2$, or slower rates. In this paper, we therefore lift a finite-sample bound to a functional one. The lifting refines the sample set until it is dense in the domain, so the bound must first be made independent of the number of samples. We achieve this by measuring the error per sample, which makes the constant uniform. For a polynomial activation and any compact input set, this gives a rate of $m^{-1/2}$ in the supremum norm, with an explicit constant.
Tags
Links
- Source: https://arxiv.org/abs/2610.18166v1
- Canonical: https://arxiv.org/abs/2610.18166v1
Trouble viewing inline? Open PDF directly →
Full Text
93,312 characters extracted from source content.
Expand or collapse full text
Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence Luis Wiederhold †thanks: Equal contribution Affiliation: School of Computation, Information and Technology Affiliation: Technical University of Munich Email: wiederhold.luis@gmx.de Nil Ayday* Affiliation: School of Computation, Information and Technology Affiliation: Technical University of Munich Email: nil.ayday@tum.de Debarghya Ghoshdastidar Affiliation: School of Computation, Information and Technology Affiliation: Technical University of Munich Abstract Randomly initialised neural networks of width m converge to Gaussian processes as m→∞m→∞, with two types of quantitative bounds characterising this convergence. Finite-sample bounds compare the network with its Gaussian limit at a fixed finite sample set, on an arbitrary domain, in the quadratic Wasserstein distance 2W_2, achieving a convergence rate of m−1/2m^-1/2 with explicit constants. However, these constants grow with the number of samples, so the bound becomes uninformative as the sample set is refined. Functional bounds remove that dependence by comparing the two as random functions, at the price of spherical input, metrics weaker than 2W_2, or slower rates. In this paper, we therefore lift a finite-sample bound to a functional one. The lifting refines the sample set until it is dense in the domain, so the bound must first be made independent of the number of samples. We achieve this by measuring the error per sample, which makes the constant uniform. For a polynomial activation and any compact input set, this gives a rate of m−1/2m^-1/2 in the supremum norm, with an explicit constant. October 13, 2026 Keywords neural network Gaussian process, functional convergence rates, Wasserstein distance 1 Introduction The connection between wide neural networks and Gaussian processes (GPs) was first established in Neal (1996), which showed that a randomly initialised single-hidden-layer network converges in distribution to a GP as its width grows. The limiting neural network Gaussian Process (NNGP) is fully specified by its covariance kernel, which depends explicitly on the network’s activation function and initialisation. For many standard activations, this kernel can be computed in closed form (Williams, 1996). This convergence reduces the network to its kernel, enabling exact Bayesian inference for infinite-width networks (Lee et al., 2018), to distill large datasets into a handful of synthetic examples by optimizing them directly through the kernel (Nguyen et al., 2021), and to rank neural architectures without training them (Chen et al., 2021). Beyond single-layer neural networks, this equivalence extends to architectures such as deep fully connected networks (Lee et al., 2018; Matthews et al., 2018). Convergence to GPs has also been established for wide feedforward and recurrent architectures (Yang, 2019), with analogous kernels derived for transformers (Hron et al., 2020), graph convolutional networks (Niu et al., 2023), and graph transformers (Ayday et al., 2026). The same framework has since led to more refined and practical approximations, such as tensor programs and the maximal update parametrisation (μ ) (Yang and Hu, 2021; Yang et al., 2022). Although the qualitative picture is now well understood, the convergence rate to NNGP in terms of width m remains less developed. Quantitative convergence has been studied from two distinct perspectives: comparing the finite-dimensional distributions of the network at a fixed finite sample set, or treating the network and its limit as random functions to establish convergence on a function space. Table 1 collects the results of both perspective. Result Depth Inputs Metric Activation Rate with n finite sample (Basteri and Trevisan, 2024, Thm. 3.1) any finite 2W_2 Lipschitz m−1/2m^-1/2 n n §2.3 (Bordino et al., 2024, Thm. 6) 11 finite 1W_1 2C^2, poly. gr. m−1/2m^-1/2 n n (Balasubramanian and Ross, 2025, Thm.1.1) any finite 1W_1 Lipschitz m−1/6m^-1/6 implicit (Favaro et al., 2025, Thm. 3.6(1)) any finite∗ dcvxd_cvx poly. gr. m−1/2m^-1/2 (Trevisan, 2023, Thm. 1.1(a)) any finite∗ pW_p Lipschitz m−1m^-1 (Celli and Peccati, 2025, Thm. 5) any finite∗ 2W_2 1C^1 or PL m−1m^-1 functional (Eldan et al., 2021, Thm. 2) 11 sphere 1(0)W_1(C^0) polynomial m−1/6m^-1/6 none (Eldan et al., 2021, Thm. 5) 11 sphere 1(0)W_1(C^0) monomial m−1/2m^-1/2 (Klukowski, 2022, Thm. 1) 11 sphere 2(L2)W_2(L^2) polynomial m−1/2m^-1/2 (Balasubramanian et al., 2023, Thm. 1.2) any sphere 1(0)W_1(C^0) Lipschitz m−qdm^-q_d (Favaro et al., 2025, Thm. 3.16) any ball 2(k)W_2(C^k) smooth m−1/8m^-1/8 This paper (Thm. 2) 11 compact 2(0)W_2(C^0) polynomial m−1/2m^-1/2 Table 1: Quantitative Gaussian approximation for wide networks; rates are in the width m, and n is the number of inputs. Finite-sample bounds hold at a fixed sample set with a constant growing in n; “implicit” means the bound depends on the input set, but this dependence is not quantified. Functional bounds avoid this at the cost of the input set, metric or rate. finite∗: finite input, non-degenerate kernel; dcvxd_cvx: convex distance; poly. gr.: polynomial growth; PL: piecewise linear. Rates for Balasubramanian and Ross (2025) and Balasubramanian et al. (2023) are one-hidden-layer specialisations. For the latter, inputs lie on the unit sphere of ℝdR^d and qd=18d−2−εq_d= 18d-2- for arbitrary ε>0 >0. By Corollary 1 the last row holds on every compact subset of ℝdR^d, with the constant of an enclosing hyperrectangle. Finite-Sample Convergence. The first approach fixes a finite sample set =x1,…,xnX=\x_1,…,x_n\ and compares the random vector f[]f[X] of n network evaluations with the corresponding Gaussian vector G[]G[X]. The strength of the finite-input route is its broad applicability. Once the comparison is reduced to a pair of random vectors in ℝnR^n, the tools of finite-dimensional Gaussian approximation apply: the distance between two centred Gaussian laws is controlled by their covariances, and couplings can be constructed explicitly (Basteri and Trevisan, 2024). This yields bounds in the quadratic Wasserstein distance 2W_2, a stronger metric than the first-order 1W_1, with explicit constants, and it asks nothing of the input points themselves: they may form an arbitrary finite collection in any dimension, rather than requiring restrictive structural assumptions such as lying on a unit sphere. It also covers the standard Gaussian initialisation with bias terms and arbitrary depth (Basteri and Trevisan, 2024). Working with a finite sample set, however, introduces a dependence on its size. A bound at X is a statement about a random vector in ℝnR^n, and with n fixed, quantities that vary with n are absorbed into the constants. For example in Basteri and Trevisan (2024) these include the Frobenius norm of a n×n× n covariance fluctuation and the smallest strictly positive eigenvalue of the limiting covariance matrix K[]K[X]. Whether the bound survives refinement of the sample set depends on how these scale. In a learning-theoretic application the sample set is the training sample, so n needs to be large. Arora et al. (2019) bound the population error of kernel regression with the limiting kernel by a term of order n−1/2n^-1/2, and carrying that guarantee over to a network of width m means comparing the two on that same sample. An n-dependent constant that grows with the sample size can offset the statistical decay. Moreover, a finite-input bound describes the network only at the chosen inputs. Convergence of the finite-dimensional distributions is a statement about each fixed finite sample set, so it does not imply convergence of the laws on a function space. The second perspective treats the network directly as a random function. Functional Convergence. Bracale et al. (2021) and Hanin (2021) establish functional convergence without rates. The lower half of Table 1 collects the quantative results. These avoid the dependence on a prescribed finite sample set, but each restricts the setting elsewhere, in the domain or in the metric. The inputs lie on a sphere in Eldan et al. (2021); Klukowski (2022); Balasubramanian et al. (2023), and Klukowski (2022) draws the weights from a sphere as well. A sphere has no interior, so such a bound says nothing about a ball, a hyperrectangle, or any set with positive volume. The metric is the weaker 1W_1 distance in Eldan et al. (2021); Balasubramanian et al. (2023). Since 1≤2W_1 _2, a bound in 2W_2 implies one in 1W_1 but not conversely. Closest to our setting is Favaro et al. (2025) with an open ball in any dimension, arbitrary depth, the same Gaussian initialisation with biases, and a kC^k norm stronger than ours, since it controls derivatives as well. Unlike a sphere, their ball is full-dimensional but they pay for the larger domain and the stronger metric with the rate m−1/8m^-1/8, against the m−1/2m^-1/2 available on the sphere. Apart from the last row, no functional row of Table 1 combines a general compact set of inputs with the rate m−1/2m^-1/2. The two perspectives are therefore complementary: finite-input bounds are general in the domain, the initialisation and the metric but carry a constant that depends on the input set. In contrast, functional bounds remove that dependence at the price of restricted domains and metrics. To our knowledge, no functional bound in the quadratic Wasserstein distance with respect to the supremum norm attains the rate m−1/2m^-1/2 on a general compact domain under the standard Gaussian initialisation. A functional bound with the generality of the finite-input analysis would give guarantees that do not weaken as the sample grows. Contribution. Our result combines the two perspectives. We start from the finite-sample bound of Basteri and Trevisan (2024) and prove that under an effective-rank condition, which we verify for polynomial activations, the constant of Basteri and Trevisan (2024) is at most of order n n. The bound therefore reads n/m n/m, so the width must grow at least as fast as the number of inputs for it to be informative. Measuring the error per input removes this growth entirely. Then we provide a chain of results that converts this finite-sample bound into a functional bound in the supremum norm. For one hidden layer, any polynomial activation, and inputs in a hyperrectangle, we obtain 2C0(I)(f,G)=O(m−1/2)W_2^C^0(I)(f,G)=O(m^-1/2) with explicit constants, and by restriction (Corollary 1) the bound holds on every compact subset of ℝdR^d. Among the functional bounds of Table 1, the rate m−1/2m^-1/2 appears only on the sphere. Theorem 2 reaches it on an arbitrary compact set, so the spherical setting of Eldan et al. (2021); Klukowski (2022); Balasubramanian et al. (2023) is a special case. This is a first step towards merging the two formalisations of quantitative convergence, carrying the generality of the finite-sample bounds into a statement about the random function. Section 2 fixes notation, introduces the network and its Gaussian process limit, and states the finite-sample bound we start from, whose constant grows at most like n n and becomes independent of the input set once the error is measured per input. Section 3 turns that uniformity into a functional bound by refining the input set until it is dense in the domain, a limit that is available only because the constant no longer grows with the number of inputs. Section 4 discusses the open questions. 2 Preliminaries and notes on finite-sample bound We fix here the objects and notation used throughout: the network and its Gaussian process limit (Section 2.1), the distance in which the two are compared (Section 2.3), and the finite-sample bound we start from, whose constant we track as the sample set grows (Section 2.3). Notation. For v∈ℝnv ^n we write ∥v∥=(∑i=1nvi2)1/2 v = ( _i=1^nv_i^2 )^1/2 for the Euclidean norm, and for a matrix A=(Aij)A=(A_ij) we write ∥A∥=(∑i,jAij2)1/2 A = ( _i,jA_ij^2 )^1/2 for the Frobenius norm, which coincides with the Euclidean norm when A is a vector. For a symmetric positive semi-definite A∈ℝn×nA ^n× n with eigenvalues λ1,…,λn≥0 _1,…, _n≥ 0 we write λmin(A)=miniλi _ (A)= _i _i, λ+(A)=minλi:λi>0,λ^+(A)= \ _i: _i>0\, and A A for the symmetric positive semi-definite square root, obtained by replacing each λi _i by λi _i in the spectral decomposition. λmin _ and λ+λ^+ differ exactly when A is singular, which is the regime of Section 2.3. For a function h and a finite set =t1,…,tnT=\t_1,…,t_n\ in its domain, fixed together with an enumeration, we write h[]=(h(t1),…,h(tn))h[T]=(h(t_1),…,h(t_n)) for the vector of evaluations; if h is ℝmR^m-valued, h[]h[T] is the m×nm× n matrix whose i-th column is h(ti)h(t_i). For a multi-index α=(α1,…,αd)∈ℕ0dα=( _1,…, _d) _0^d we write |α|=∑j=1dαj α = _j=1^d _j and xα=x1α1⋯xdαdx^α=x_1 _1·s x_d _d for x∈ℝdx ^d. The polynomials of total degree at most r in d variables form a vector space of dimension (r+d) r+dd, spanned by xα:|α|≤r\x^α: α ≤ r\. Gaussian vectors. For a random vector X∈ℝnX ^n with finite second moment, its covariance matrix is defined as Σ(X)=[(X−[X])(X−[X])⊤]. (X)=E [(X-E[X])(X-E[X]) ]. If X is centred then Σ(X)=[XX⊤] (X)=E[X ]. We write (0,Σ)N(0, ) for the centred Gaussian law on ℝnR^n with covariance Σ . 2.1 Random neural networks and their Gaussian process (GP) limit We now define the two objects the paper compares. The first is a network at finite width m; the second is the GP it approaches as the width grows (m→∞m→∞), whose kernel is determined by the activation and the initialisation variances. Definition 1 (randomly initialised shallow network). Let ϕ:ℝ→ℝφ:R be an activation function. A shallow neural network of width m is a function f:ℝd→ℝf:R^d of the form g(x)=Wx+b∈ℝm,f(x)=a⊤ϕ(g(x))+c∈ℝ,g(x)=Wx+b ^m, f(x)=a φ (g(x) )+c , with parameters W∈ℝm×dW ^m× d, b,a∈ℝmb,a ^m, c∈ℝc , where ϕφ acts componentwise and g is the pre-activation. At random initialisation the parameters are independent, with Wrj∼(0,σw2d),br∼(0,σb2),ar∼(0,τa2m),c∼(0,τc2),W_rj (0, _w^2d ), b_r (0, _b^2 ), a_r (0, _a^2m ), c (0, _c^2 ), with σw2,τa2>0 _w^2, _a^2>0 and σb2,τc2≥0 _b^2, _c^2≥ 0. The network in Definition 1 maps d-dimensional inputs to scalar outputs. Multivariate outputs can be handled analogously and are omitted for notational simplicity. Throughout, I⊂ℝdI ^d denotes a fixed compact set, and input sets =x1,…,xnX=\x_1,…,x_n\ are finite subsets of I, with corresponding evaluations f[]∈ℝnf[X] ^n and g[]∈ℝm×ng[X] ^m× n. Since W and b are Gaussian, the pre-activation is a GP for every width. Applying ϕφ destroys Gaussianity, but the output is a sum of m independent terms, so by the central limit theorem it is asymptotically Gaussian as m→∞m→∞. The covariance of that limit is computable, and the two kernels are the following. Definition 2 (Gaussian process and NNGP kernels). A Gaussian process on I is a family (G(x))x∈I(G(x))_x∈ I of real random variables on a common probability space, every finite subfamily of which is a Gaussian vector; it is centred if [G(x)]=0E[G(x)]=0 for every x∈Ix∈ I, and its covariance kernel is (x,y)↦[G(x)G(y)](x,y) [G(x)G(y)]. A centred Gaussian process is determined in law by its covariance kernel, and every symmetric positive semi-definite function on I×I× I is the covariance kernel of one (Kallenberg, 2002, Theorem 6.16). For x,y∈Ix,y∈ I define κ(x,y) κ(x,y) =σw2d⟨x,y⟩+σb2, = _w^2d\, x,y + _b^2, (1) K(x,y) K(x,y) =τa2[ϕ(Zx)ϕ(Zy)],(Zx,Zy)∼(0,(κ(x,x)κ(x,y)κ(x,y)κ(y,y))), = _a^2\,E [φ(Z_x)\,φ(Z_y) ], (Z_x,Z_y) (0, pmatrixκ(x,x)&κ(x,y)\\ κ(x,y)&κ(y,y) pmatrix ), (2) Kc(x,y) K_c(x,y) =K(x,y)+τc2. =K(x,y)+ _c^2. (3) Here κ is the covariance of the pre-activation coordinates of Definition 1, the same for every coordinate, and for a finite =x1,…,xn⊆IX=\x_1,…,x_n\ I we write κ[]κ[X], K[]K[X], Kc[]∈ℝn×nK_c[X] ^n× n for the matrices with entries κ(xi,xj)κ(x_i,x_j), K(xi,xj)K(x_i,x_j), Kc(xi,xj)K_c(x_i,x_j). All three kernels are symmetric and positive semi-definite, so the neural network Gaussian process (NNGP) associated with Definition 1 is well defined as the centred Gaussian process G on I with covariance kernel KcK_c. The pre-activation g[]g[X] consists of m independent rows with law (0,κ[])N(0,κ[X]) and is exactly Gaussian at every width. The output f[]f[X] is not. A finite-input Gaussian approximation bound such as Theorem 1 measures, at finite width, how far the law of f[]f[X] is from (0,Kc[])N(0,K_c[X]). It is stated in the quadratic Wasserstein distance, defined next. 2.2 The quadratic Wasserstein distance Definition 3 (quadratic Wasserstein distance). Let (E,∥⋅∥E)(E, · _E) be a separable Banach space and let p,qp,q be probability measures on E with finite second moment. Then 2E(p,q)=inf[∥X−Y∥E2]:X∼p,Y∼q,W_2^E(p,q)= \ E [ X-Y _E^2 ]\;:\;X p,\ Y q \, the infimum running over all couplings of p and q, i.e. all pairs (X,Y)(X,Y) of E-valued random variables on a common probability space with the given marginals. We write 2E(X,Y)W_2^E(X,Y) for 2E(ℙX,ℙY)W_2^E(P_X,P_Y). Four instances occur below, differing only in the state space E or its norm: E ∥⋅∥E · _E notation compares used in ℝnR^n ∥v∥=(∑i=1nvi2)1/2 v = ( _i=1^nv_i^2 )^1/2 2=2ℝnW_2=W_2^R^n finite sample set, total error Thm. 1 ℝnR^n ∥v∥n=(n−1∑i=1nvi2)1/2 v _n= (n^-1 _i=1^nv_i^2 )^1/2 2,nW_2,n finite sample set, error per sample §2.3 L2(I)L^2(I) (∫Ih(x)2x)1/2 ( _Ih(x)^2\,dx )^1/2 2L2(I)W_2^L^2(I) random functions, mean-square error §3 0(I)C^0(I) supx∈I|h(x)| _x∈ I h(x) 20(I)W_2^C^0(I) random functions, supremum error §3 All four are separable Banach spaces. In ℝnR^n the norm ∥⋅∥n · _n is the root mean square of the coordinates, so 2,n=n−1/22W_2,n=n^-1/2W_2 measures the transport cost per input, where 2=2ℝnW_2=W_2^R^n is the Euclidean case; it is again a metric, being a positive multiple of one. Since ∥h∥L2(I)≤Vol(I)∥h∥0(I) h _L^2(I)≤ (I)\, h _C^0(I), we have 2L2(I)≤Vol(I)20(I)W_2^L^2(I)≤ (I)\,W_2^C^0(I), so the supremum-norm statement is the strongest of the two functional bounds. Remark 1 (coupling convention). Since 2EW_2^E is an infimum over couplings, a single explicit coupling bounds 2EW_2^E from above (Proposition 2 (1)). Throughout, (f,G)(f,G) therefore denotes a pair defined on a common probability space with the laws of Definitions 1 and 2: all bounds on ∥f−G∥E f-G _E are proved for almost every realisation, and the expectation and the infimum are taken only at the end. Further properties of 2W_2 are collected in Appendix A. 2.3 The finite-sample bound and its data dependence Quadratic Wasserstein distance is well suited for Gaussian approximation since the distance between two centred Gaussian laws is bounded by the Frobenius distance of the square roots of their covariances, so covariance perturbations can be tracked explicitly. This is the mechanism behind the bound of Basteri and Trevisan (2024), revisited in Theorem 1. We state their result under the following standard assumptions about the activation function. Assumption 1 (activation function). The activation ϕ:ℝ→ℝφ:R of Definition 1 satisfies: (1) Polynomial growth. There are A,p<∞A,p<∞ with |ϕ(z)|≤A(1+|z|)p φ(z) ≤ A(1+ z )^p for all z∈ℝz . (2) Locally Lipschitz with derivative of polynomial growth. ϕφ is absolutely continuous and there are A′,p′<∞A ,p <∞ with |ϕ′(z)|≤A′(1+|z|)p′ φ (z) ≤ A (1+ z )^p for almost every z∈ℝz . (3) Non-degeneracy. For every x∈Ix∈ I the variance κ(x,x)κ(x,x) is strictly positive and ϕφ does not vanish (0,κ(x,x))N (0,κ(x,x) )-almost everywhere. Assumption 1 is satisfied by tanh , the logistic sigmoid, erf , ReLU and its leaky and smooth variants (GELU , SiLU , softplus), by every polynomial, and by products such as ztanh(z)z (z). It excludes exponential growth, which violates Assumption 1(1); unbounded derivatives at the origin such as |z|α z ^α with α∈(0,1)α∈(0,1), which violate Assumption 1(2); and jump discontinuities, which are not absolutely continuous. Assumption 1(3) also involves the bias and the domain: since κ(x,x)=σw2d‖x‖2+σb2κ(x,x)= _w^2d\|x\|^2+ _b^2, it holds for all the above activations if and only if σb>0 _b>0 or 0∉I0∉ I. Theorem 1 (adapted from (Basteri and Trevisan, 2024, Theorem 3.1)). Let =x1,…,xn⊂IX=\x_1,…,x_n\⊂ I be a finite sample set, let f be the network of Definition 1 and let G be the Gaussian process of Definition 2. Under Assumption 1, for every width m∈ℕm , 2(f[],G[])≤C(ϕ,)m,W_2 (f[X],\,G[X] )\;≤\; C(φ,X) m, (4) with the explicit constant C(ϕ,)=[∥τa2ϕ(Z)ϕ(Z)⊤−K[]∥2]λ+(K[]),Z∼(0,κ[])∈ℝn.C(φ,X)\;=\; E [ _a^2\,φ(Z)φ(Z) -K[X] ^2 ] λ^+ (K[X] ), Z (0,κ[X] ) ^n. (5) The output bias contributes the same independent translation to f[]f[X] and to G[]G[X], so by Proposition 2 (3) it cancels and the constant involves K[]K[X] rather than Kc[]K_c[X]. C(ϕ,)C(φ,X) depends only on the activation ϕφ, the input set X and the variances σw2,σb2,τa2 _w^2, _b^2, _a^2, but not on the width m. Theorem 3.1 of Basteri and Trevisan (2024) makes the stronger assumption that ϕφ is globally Lipschitz. The proof under Assumption 1 is given in Appendix B. The bound of Theorem 1 holds at any fixed finite sample set, but its constant C(ϕ,)C(φ,X) depends on that set. Section 3 evaluates f and G on grids that become dense in I, and hence arbitrarily large, so the growth of C(ϕ,)C(φ,X) decides whether a functional comparison is possible. This remainder of this section determines how C(ϕ,)C(φ,X) behaves: the numerator of (5) grows at most linearly in the number of inputs, while the denominator admits no lower bound in general, so that enlarging the input set can render (4) vacuous. A lower bound on the denominator must therefore be assumed. Linear growth in n n is the most that can be demanded, since λ+(K[])λ^+(K[X]) never exceeds trK[] K[X], which grows linearly under Assumption 1. Assumption 2 (effective-rank condition). A collection ℱF of finite sample sets ⊂IX⊂ I satisfies the effective-rank condition with constant ν>0ν>0 if, writing n=||n= , λ+(K[])≥νnfor every ∈ℱ.λ^+ (K[X] )\;≥\;ν\,n every X . (6) Assumption 2 excludes every activation for which the rank(K[])rank(K[X]) is unbounded (see proof of Proposition 1 for details). In particular every activation whose kernel K is strictly positive definite on I is excluded, since then rank(K[])=||rank(K[X])=|X|. 11 1 The rows of Table 1 that reach m−1m^-1 do so under exactly this non-degeneracy, so the m−1/2m^-1/2 rate of Theorem 1 is the best available rate in our setting. The condition is therefore a finite-rank condition, and Lemma 1 verifies it for polynomial activations on the grids of Section 3. Under Assumption 1 the numerator of the constant in Equation (5) grows at most linearly in n, while under Assumption 2 the denominator grows like n n, leaving the bound of Theorem 1 with a factor n n and a constant that depends neither on the sample set nor on the width. The following proposition makes these statements precise, and is proved in Appendix B. Proposition 1 (the constant of Theorem 1). Let ⊂IX⊂ I be a finite sample set with n=||n= . 1. Under Assumption 1 with growth constants A,pA,p, the numerator of (5), N:=[∥τa2ϕ(Z)ϕ(Z)⊤−K[]∥2],Z∼(0,κ[])∈ℝn,N:= E [ _a^2\,φ(Z)φ(Z) -K[X] ^2 ], Z (0,κ[X] ) ^n, satisfies N≤τa2A2M4pnN≤ _a^2A^2 M_4p\,n, where Ms:=[(1+|ξ|)s]<∞for s>0 and ξ∼(0,κI2) with κI2:=maxx∈Iκ(x,x)<∞.M_s:=E [(1+ ξ )^s ]<∞ s>0 and ξ (0, _I^2) with _I^2:= _x∈ Iκ(x,x)<∞. 2. If in addition K[]K[X] satisfies Equation (6) with constant ν>0ν>0, then for every width m∈ℕm , 2(f[],G[])≤Dnm,W_2 (f[X],G[X] )\;≤\;D nm, with D:=τa2A2M4p/νD:= _a^2A^2 M_4p/ν. The constants depend only on ϕφ through A,pA,p, on I, on the variances σw2,σb2,τa2 _w^2, _b^2, _a^2 and, in part (2), on ν, and neither on X nor on m. Proposition 1 shows that the bound of Theorem 1 grows with the number of inputs: the width m must grow faster than n for it to be informative. This is the main limitation of finite-sample bounds. Section 3 removes that growth and compares f and G as random functions. 3 From a Finite-Input Bound to Functional Convergence ∥f−G∥0(I) f-G _C^0(I)∥f−G∥L2(I) f-G _L^2(I)∥(f−G)[k]∥n (f-G)[X_k] _nC∗/mC / m≲ 2≲ 3≲ ++ Uniform Wasserstein DistanceLemma 4, Equation 7 Figure 1: Roadmap of Section 3. Each inequality bounds the quantity on its left by the one on its right, and the reference names the result that does it. A norm equivalence bounds the supremum norm by the L2(I)L^2(I) norm, a discretization bounds that by the grid values, and a coupling bounds those by the width. Composing the three steps proves Theorem 2. Measured per input rather than in total, the bound of Proposition 1 gives, 2,n(f[],G[])≤Dm,D:=τa2A2M4p/ν.W_2,n (f[X],G[X] )\;≤\; D m, D:= _a^2A^2 M_4p/ν. (7) The right-hand side of 7 does not depend on the sample set. In the unrescaled form, the bound Dn/mD n/m is informative only when n≪mn m, so the width must grow with the number of inputs for this bound to be useful, as discussed in the introduction. In the rescaled distance, the width alone governs the per-sample approximation error. But rescaling presupposes n, and (7) is still a statement about a random vector in ℝnR^n. This section uses (7) to get a bound on f and G as random functions. Converting this bound into a statement about the function is a chain of three steps, shown in Figure 1, where each arrow replaces the quantity on its left by a larger one. (i) A norm equivalence bounds the supremum norm by the L2(I)L^2(I) norm on the finite-dimensional space when ϕφ is a polynomial. (i) A discretization estimate bounds the L2(I)L^2(I) norm by the values on a finite grid, up to a mesh error that shrinks as the grid is refined. Refining the grid adds inputs, so with the unrescaled constant the mesh error and the constant cannot be made small at once. This is the obstruction identified in Basteri and Trevisan (2024, Section 5), which is why the functional bound is only sketched there. Since the right-hand side of (7) does not grow with the number of inputs, the grid may be refined freely and the mesh error sent to zero. (i) An explicit coupling then identifies the remaining grid term with the left-hand side of (7). The three bounds are deterministic and are applied pathwise to h=f−Gh=f-G, for the coupled pair of Remark 1, with the expectation taken only afterwards. We take I to be a hyperrectangle, so that the grids are products of d one-dimensional grids. The product structure gives the covering property that the discretization step needs (Remark 2 in Apendix A). For a polynomial activation these grids also satisfy Assumption 2 with one constant ν for all k≥k1k≥ k_1 (Lemma 1). The hyperrectangle restriction is removed afterwards by Corollary 1. Definition 4 (midpoint grid). Assume I=I1×⋯×IdI=I_1×·s× I_d be a d-dimensional hyperrectangle, with Ij=[aj,bj]I_j=[a_j,b_j], |Ij|:=bj−aj>0 I_j :=b_j-a_j>0 and Vol(I):=∏j=1d|Ij| (I):= _j=1^d I_j . For k∈ℕk let k(j)=aj+(l−12)|Ij|k:l=1,…,k⊂IjX_k^(j)= \\,a_j+ (l- 12 ) I_j k\;:\;l=1,…,k\, \⊂ I_j be the one-dimensional midpoint grid of order k on IjI_j, the superscript indexing the coordinate. The midpoint grid of order k on I is k=k(1)×⋯×k(d)⊂I.X_k=X_k^(1)×·s×X_k^(d)⊂ I. (8) In particular n=|k|=kdn= _k =k^d: the subscript k counts points per axis, not the total number of points. Further properties of kX_k are collected in Appendix A. The grids of Definition 4 form the collection to which Assumption 2 is applied. For a polynomial activation the following lemma establishes it with a single constant ν, so (7) holds with the same D for every k, which is what the limit taken in Theorem 2 requires. Lemma 1 (polynomial activations). Let ϕφ be a nonzero polynomial of degree r satisfying Assumption 1, and let kX_k be the midpoint grids of Definition 4. Then rank(K[k])≤(r+d) (K[X_k])≤ r+dd for every k, and there are ν>0ν>0 and k1∈ℕk_1 such that kX_k satisfies the effective-rank condition (Assumption 2) with constant ν for every k≥k1k≥ k_1. The proof of Lemma 1 factorises the kernel matrix as K[k]=VkMVk⊤K[X_k]=V_kMV_k , where the rows of Vk∈ℝkd×RV_k ^k^d× R are the monomials of total degree at most r evaluated at the grid points, R=(r+d)R= r+dd, and M∈ℝR×RM ^R× R is positive semi-definite and independent of k. Hence rank(K[k])≤rank(M)≤R (K[X_k])≤ (M)≤ R, however fine the grid is. The nonzero eigenvalues of K[k]K[X_k] coincide with those of the R×R× R matrix kdM1/2(1kdVk⊤Vk)M1/2k^dM^1/2( 1k^dV_k V_k)M^1/2, whose middle factor 1kdVk⊤Vk 1k^dV_k V_k is a midpoint Riemann sum. Its limit is positive definite, which yields λ+(K[k])≥νkdλ^+(K[X_k])≥ν\,k^d for all k≥k1k≥ k_1. Our main result, Theorem 2, provides a functional Wasserstein bound in the supremum norm (20(I)(f,G)W_2^C^0(I)(f,G)). This bound compares the neural network and its NNGP as random continuous functions on a compact interval for polynomial activation functions. Theorem 2 (main result: functional bound with m−1/2m^-1/2 rate). Let ϕφ be a nonzero polynomial of degree r satisfying Assumption 1, let I=I1×⋯×IdI=I_1×·s× I_d be a hyperrectangle. Then for every m∈ℕm , 20(I)(f,G)≤C∗m,C∗:=(r+1)dτa2A22M4pν,W_2^C^0(I)(f,G)\;≤\; C m, C :=(r+1)^d\, _a^2A^2 2\,M_4pν, (9) where A,pA,p are the growth constants of Assumption 1, M4pM_4p is the moment of Theorem 2, and ν>0ν>0 is the effective-rank constant supplied by Lemma 1. The supremum norm only decreases when the domain is made smaller, so Theorem 2 carries over from the hyperrectangle to every compact set it contains, with the same constant (Corollary 1). Corollary 1. Let S⊂ℝdS ^d be compact and let I be a hyperrectangle containing S. Under the hypotheses of Theorem 2 on I, 20(S)(f,G)≤20(I)(f,G)=O(m−1/2).W_2^C^0(S)(f,G)\;≤\;W_2^C^0(I)(f,G)\;=\;O (m^-1/2 ). Since every compact set is contained in a hyperrectangle, the rate m−1/2m^-1/2 holds on any compact set of inputs; only the constant depends on the enclosing hyperrectangle. 3.1 Proof Sketch Each step of Figure 1 is one lemma, and the final paragraph combines them. All proofs of this section are given in Appendix C. Supremum norm to L2L^2 norm. For a polynomial activation the sample paths of f and of G lie in a space of polynomials, on which the supremum norm and the L2L^2 norm are comparable. Lemma 2 (norm equivalence for polynomial activations). Let I=I1×⋯×IdI=I_1×·s× I_d be a hyperrectangle, let r∈ℕ0r _0, and let rP_r denote the space of real polynomials on I of total degree at most r. For every p∈rp _r, ∥p∥0(I)≤(r+1)dVol(I)∥p∥L2(I). p _C^0(I)\;≤\; (r+1)^d (I)\, p _L^2(I). (10) If ϕφ is a polynomial of degree r, then f has sample paths in rP_r almost surely, and G admits a version with the same property. Reduction to the grid (Discretization). The L2(I)L^2(I) norm is controlled on the midpoint grid of Definition 4. The grid constrains h at finitely many points only, so it says nothing about h in between unless h is prevented from moving sharply. The Hölder seminorm measures that movement. Definition 5 (Hölder spaces). Let S⊂ℝdS ^d be compact and let γ∈(0,1]γ∈(0,1]. For h:S→ℝh:S set ∥h∥0(S)=supx∈S|h(x)|,[h]γ(S)=supx,y∈Sx≠y|h(x)−h(y)|∥x−y∥γ,∥h∥γ(S)=∥h∥0(S)+[h]γ(S). h _C^0(S)= _x∈ S h(x) , [h]_C^γ(S)= _ subarraycx,y∈ S\\ x≠ y subarray h(x)-h(y) x-y ^γ, h _C^γ(S)= h _C^0(S)+[h]_C^γ(S). The space γ(S)C^γ(S) consists of all h:S→ℝh:S with ∥h∥γ(S)<∞ h _C^γ(S)<∞. A finite [h]γ(S)[h]_C^γ(S) means that h changes by at most [h]γ(S)∥x−y∥γ[h]_C^γ(S) x-y ^γ between any two points of S. The seminorms of f and of G have finite second moment at every fixed width, by the regularity of ϕφ (Assumption 1) for f and by the Kolmogorov–Chentsov theorem (Revuz and Yor, 1999) for G. Both are verified in Appendix C, as part of the proof of Theorem 2. The midpoint grid has the covering property: every point of I lies within a distance ρk=O(k−1) _k=O(k^-1) of a grid point (Remark 2). A Hölder function therefore differs little from its value at the nearest grid point, and comparing h with that value bounds the L2(I)L^2(I) norm by the grid values, up to an error governed by ρk _k and by the Hölder seminorm of h. Lemma 3 (Discretization). Let γ∈(0,1]γ∈(0,1], let h∈γ(I1×⋯×Id)h ^γ(I_1×·s× I_d) and let kX_k be the midpoint grid of order k on I1×⋯×IdI_1×·s× I_d. Using h[k]=(h(x1),…,h(xkd))h[X_k]=(h(x_1),…,h(x_k^d)) we get ∥h∥L2(I)2≤ 2Vol(I)kd∥h[k]∥2+ 2Vol(I)ρk2γ[h]γ(I)2. h ^2_L^2(I)\;≤\;2\, (I)k^d\, h[X_k] ^2\;+\;2\, (I)\, _k^2γ\,[h]^2_C^γ(I). (11) The proof partitions I into the kdk^d cells of the grid, each of volume Vol(I)/kd (I)/k^d and each containing its grid point as midpoint, and compares h with that value on each cell. Two properties of (11) matter. The mesh error (2Vol(I)ρk2γ[h]γ(I)22\, (I)\, _k^2γ\,[h]^2_C^γ(I)) vanishes as the grid is refined, since ρk=O(k−1) _k=O(k^-1). The first term 2Vol(I)∥h[k]∥n22 (I) h[X_k] _n^2 carries the grid values in the rescaled norm of Definition 3, which averages over the grid instead of summing. This is the norm in which Equation (7) is uniform in the number of inputs, so refining the grid shrinks the mesh error without inflating the first term. The two limits of m and n therefore decouple, and this is the step for which Section 2.3 is needed. Coupling The grid term of (11) is a second moment, not a Wasserstein distance. The two agree when the grid evaluations are optimally coupled, and such a coupling of the full processes exists. Lemma 4 (Coupling the Processes). Let ⊂IX⊂ I be a finite sample set with n=||n= . There is a pair (f~,G~)( f, G) of random elements of 0(I)C^0(I) with f~=f f d=f and G~=G G d=G, whose evaluations (f~[],G~[]) ( f[X], G[X] ) form an optimal coupling of the laws of f[]f[X] and G[]G[X]. Consequently 2,n(f[],G[])2=[∥f~[]−G~[]∥n2].W_2,n (f[X],G[X] )^2\;=\;E [ f[X]- G[X] _n^2 ]. An optimal coupling of f[]f[X] and G[]G[X] exists by Villani (2008, Theorem 4.1), and the proof extends it from these n values to the whole functions by drawing f and G independently from their conditional laws given their values on X, which leaves the law of each unchanged. Completing proof of Theorem 2. We can now put the pieces together. Fix a midpoint grid kX_k and let (f~,G~)( f, G) be the coupled pair of Lemma 4, so that h=f−Gh=f-G is a single random function. Lemma 2 bounds ∥h∥0(I) h _C^0(I) by ∥h∥L2(I) h _L^2(I), and Lemma 3 bounds ∥h∥L2(I) h _L^2(I) by the values on the grid plus a mesh error. Taking expectations, Lemma 4 turns the grid term into 2,n(f[k],G[k])2W_2,n (f[X_k],G[X_k] )^2, which Equation 7 bounds by D2/mD^2/m, the same bound for every k, its effective-rank hypothesis supplied by Lemma 1. The mesh error, by contrast, vanishes as the grid is refined, since ρk=O(k−1) _k=O(k^-1) while the Hölder seminorms of f and of G have finite second moment at the fixed width m and do not depend on k. Letting k→∞k→∞ at fixed m therefore leaves only the width. 4 Discussion Finite-sample bounds have two limitations: their constant depends on the sample set, so a guarantee transferred from the infinite-width limit weakens as the sample grows; and they compare two random vectors, not the two random functions. Section 2.3 shows a simple way to remove the first by measuring the error per input, and Section 3 shows how to remove the second by refining the sample set until it is dense in the domain. For polynomial activations, the result is a functional bound in the quadratic Wasserstein distance with respect to the supremum norm, at the finite-sample rate m−1/2m^-1/2, with an explicit constant, on every compact set of inputs. Beyond Polynomial Activations. The effective-rank condition of Assumption 2 holds for polynomial activations but fails whenever K[]K[X] has unbounded rank, in particular for strictly positive definite kernels. For such activations it must be replaced by a weaker spectral lower bound λ+(K[])≥νn1−αλ^+(K[X])≥ν\,n^1-α for some α≥0α≥ 0, with α=0α=0 recovering Assumption 2. Every step of the roadmap in Figure 1 other than the norm equivalence of Lemma 2 requires only Assumption 1, and Lemma 2 can be replaced by an interpolation inequality. Lemma 5 (interpolation). Let γ∈(0,1]γ∈(0,1] and let I=I1×⋯×IdI=I_1×·s× I_d be a hyperrectangle. There are constants C1,C2<∞C_1,C_2<∞ depending only on d and on minj|Ij| _j I_j such that for every h∈γ(I)h ^γ(I), ∥h∥0(I)≤C1∥h∥L2(I)2γ2γ+d[h]γ(I)d2γ+d+C2Vol(I)∥h∥L2(I). h _C^0(I)\;≤\;C_1\, h _L^2(I) 2γ2γ+d\,[h]_C^γ(I) d2γ+d\;+\; C_2 (I)\, h _L^2(I). The proof of Lemma 5 is in Appendix D. The L2(I)L^2(I) norm carries the exponent 2γ2γ+d 2γ2γ+d, which is smaller than one and decreases with the dimension, and the Hölder seminorm carries the remainder. The seminorm now enters the rate, so it must be bounded uniformly in m. With α>0α>0, the right-hand side of (7) is no longer uniform in the number of inputs, and the grid can no longer be refined freely after the discretization step. The grid term now grows with k while the mesh error decays, so instead of letting k→∞k→∞ one has to choose k as a function of m to balance the two. The resulting rate is slower than m−1/2m^-1/2, and it deteriorates with the dimension d through the exponent 2γ/(2γ+d)2γ/(2γ+d) of the interpolation inequality. Sharpness of the rate. Whether the rate in Theorem 2 is sharp remains open. A lower bound does not require a further lifting argument: for every x∈Ix∈ I, 2(f(x),G(x))≤20(I)(f,G).W_2 (f(x),G(x) ) _2^C^0(I)(f,G). Combining this inequality with single-input bound of Favaro et al. (2025, Theorem 3.3(2)) yields a lower bound of order m−1m^-1. Since this bound uses only one input, it does not establish whether the rate m−1/2m^-1/2 is sharp for general n. The upper bound in Theorem 2, in contrast, inherits the rate of the corresponding finite-input bound. For finite input sets, a rate of m−1m^-1 is available when K[]K[X] is invertible (Trevisan, 2023). When it is singular, the best known rate is m−1/2m^-1/2. Our setting falls into the latter case: the effective-rank condition imposes a rank bound on K[]K[X], precluding invertibility for sufficiently large input sets. Thus, the available finite-input bounds yield the rate m−1/2m^-1/2. Deeper networks. Our analysis covers only one hidden layer. The steps in Section 3 that convert a finite-sample bound into a functional one carry over to deeper networks with polynomial activations. The finite-sample bound of Basteri and Trevisan (2024, Theorem 3.1) also holds at any depth, but its proof propagates the comparison through the layers and therefore requires a Lipschitz activation, while our functional argument requires a polynomial one. Extending Theorem 2 to deeper networks therefore requires a propagation step that does not rely on Lipschitz continuity. The metric. Our bound controls the function values but not their derivatives. The only stronger metric in Table 1 is the kC^k norm of Favaro et al. (2025), obtained at the slower rate m−1/8m^-1/8, and whether m−1/2m^-1/2 is attainable in such a norm is open in general. Implications for tensor programs. Tensor programs (Yang, 2019) extend the Gaussian process limit to essentially all standard architectures, and Agazzi et al. (2026) recently made this limit quantitative, recovering the m−1/2m^-1/2 rate of Basteri and Trevisan (2024) for general programs. The bounds of Agazzi et al. (2026) are finite-sample statements: they hold on a fixed set of inputs, with a constant that depends implicitly on that set. Our approach suggests how to lift such bounds to functional statements for tensor programs, yielding convergence rates that do not deteriorate as the evaluation set grows, provided their dependence on the number of inputs can be made explicit. AI Disclosure ChatGPT (OpenAI) and Claude (Anthropic) were used as auxiliary tools for language editing, literature discovery, and typesetting support. Each reference and bibliographic item identified through these tools was independently verified against primary sources, and we take full responsibility for the final content and accuracy of the document. References Agazzi et al. (2026) A. Agazzi, E. M. García, and D. Trevisan Quantitative Gaussian-process limits of Tensor Programs. CoRR. Cited by: §4. Arora et al. (2019) S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 322–332. Cited by: §1. Ayday et al. (2026) N. Ayday, L. Yang, and D. Ghoshdastidar Gaussian process limit reveals structural benefits of graph transformers. In Conference on Uncertainty in Artificial Intelligence, Cited by: §1. Balasubramanian et al. (2023) K. Balasubramanian, L. Goldstein, N. Ross, and A. Salim Gaussian random field approximation via Stein’s method with applications to wide random neural networks. CoRR. Cited by: §1, §1, Table 1, Table 1. Balasubramanian and Ross (2025) K. Balasubramanian and N. Ross Finite-dimensional Gaussian approximation for deep neural networks: universality in random weights. CoRR. Cited by: Table 1, Table 1. Basteri and Trevisan (2024) A. Basteri and D. Trevisan Quantitative Gaussian approximation of randomly initialized deep neural networks. Machine Learning 113 (9), p. 6373–6393. Cited by: §1, §1, §1, Table 1, §2.3, §2.3, §3, §4, §4, Theorem 1. Bordino et al. (2024) A. Bordino, S. Favaro, and S. Fortini Non-asymptotic approximations of Gaussian neural networks via second-order poincaré inequalities. In Symposium on Advances in Approximate Bayesian Inference, Proceedings of Machine Learning Research, Vol. 253, p. 45–78. Cited by: Table 1. Bracale et al. (2021) D. Bracale, S. Favaro, S. Fortini, and S. Peluchetti Large-width functional asymptotics for deep Gaussian neural networks. In International Conference on Learning Representations, Cited by: §1. Celli and Peccati (2025) L. Celli and G. Peccati Entropic bounds for conditionally Gaussian vectors and applications to neural networks. CoRR. Cited by: Table 1. Chen et al. (2021) W. Chen, X. Gong, and Z. Wang Neural architecture search on imagenet in four GPU hours: A theoretically inspired perspective. In International Conference on Learning Representations, Cited by: §1. Eldan et al. (2021) R. Eldan, D. Mikulincer, and T. Schramm Non-asymptotic approximations of neural networks by Gaussian processes. In Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 134, p. 1754–1775. Cited by: §1, §1, Table 1, Table 1. Favaro et al. (2025) S. Favaro, B. Hanin, D. Marinucci, I. Nourdin, and G. Peccati Quantitative CLTs in deep neural networks. Probability Theory and Related Fields 191 (3), p. 933–977. Cited by: §1, Table 1, Table 1, §4, §4. Hanin (2021) B. Hanin Random neural networks in the infinite width limit as Gaussian processes. CoRR. Cited by: §1. Hron et al. (2020) J. Hron, Y. Bahri, J. Sohl-Dickstein, and R. Novak Infinite attention: NNGP and NTK for deep attention networks. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 4376–4386. Cited by: §1. Kallenberg (2002) O. Kallenberg Foundations of modern probability. Second edition, Probability and its Applications, Springer-Verlag, New York. Cited by: Definition 2. Klukowski (2022) A. Klukowski Rate of convergence of polynomial networks to Gaussian processes. In Conference on Learning Theory, Proceedings of Machine Learning Research, p. 701–722. Cited by: §1, §1, Table 1. Lee et al. (2018) J. Lee, Y. Bahri, R. Novak, S. S. Schoenholz, J. Pennington, and J. Sohl-Dickstein Deep neural networks as Gaussian processes. In nternational Conference on Learning Representations, Cited by: §1. Matthews et al. (2018) A. G. d. G. Matthews, J. Hron, M. Rowland, R. E. Turner, and Z. Ghahramani Gaussian process behaviour in wide deep neural networks. In International Conference on Learning Representations, Cited by: §1. Neal (1996) R. M. Neal Priors for infinite networks. In Bayesian Learning for Neural Networks, p. 29–53. Cited by: §1. Nguyen et al. (2021) T. Nguyen, R. Novak, L. Xiao, and J. Lee Dataset distillation with infinitely wide convolutional networks. In Neural Information Processing Systems, p. 5186–5198. Cited by: §1. Nirenberg (2011) L. Nirenberg On elliptic partial differential equations. In Il principio di minimo e sue applicazioni alle equazioni funzionali, S. Faedo (Ed.), Cited by: Appendix D. Niu et al. (2023) Z. Niu, M. Anitescu, and J. Chen Graph neural network-inspired kernels for Gaussian processes in semi-supervised learning. In International Conference on Learning Representations, Cited by: §1. Revuz and Yor (1999) D. Revuz and M. Yor Continuous martingales and Brownian motion. 3 edition, Grundlehren der mathematischen Wissenschaften, Vol. 293, Springer. Cited by: Appendix C, §3.1. Trevisan (2023) D. Trevisan Wide deep neural networks with Gaussian weights are very close to Gaussian processes. Cited by: Table 1, §4. Villani (2008) C. Villani Optimal transport: old and new. Cited by: Appendix C, §3.1. Williams (1996) C. K. I. Williams Computing with infinite networks. In Advances in Neural Information Processing Systems, p. 295–301. Cited by: §1. Yang et al. (2022) G. Yang, E. J. Hu, I. Babuschkin, S. Sidor, X. Liu, D. Farhi, N. Ryder, J. Pachocki, W. Chen, and J. Gao Tensor programs V: tuning large neural networks via zero-shot hyperparameter transfer. CoRR. Cited by: §1. Yang and Hu (2021) G. Yang and E. J. Hu Tensor programs IV: feature learning in infinite-width neural networks. In International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 11727–11737. Cited by: §1. Yang (2019) G. Yang Tensor programs I: wide feedforward or recurrent neural networks of any architecture are Gaussian processes. CoRR. Cited by: §1, §4. Appendix A Auxiliary results Proposition 2 (properties of 2W_2). Let X,Y,ZX,Y,Z be E-valued random variables with finite second moments. 1. (coupling bound) For any pair (X,Y)(X,Y) on a common probability space, 2E(X,Y)≤[∥X−Y∥E2]W_2^E(X,Y)≤ E[ X-Y _E^2] . 2. (triangle inequality) 2E(X,Z)≤2E(X,Y)+2E(Y,Z)W_2^E(X,Z) _2^E(X,Y)+W_2^E(Y,Z). 3. (independent translations) If Z is independent of X and of Y, then 2E(X+Z,Y+Z)≤2E(X,Y).W_2^E(X+Z,Y+Z) _2^E(X,Y). 4. (convexity) If Z takes values in some Euclidean space, then (2E(X,Y))2≤∫(2E(ℙX|Z=z,ℙY))2dℙZ(z). (W_2^E(X,Y) )^2≤ (W_2^E(P_X Z=z,P_Y) )^2\,dP_Z(z). 5. (Gaussian comparison) If E=ℝnE=R^n and X,YX,Y are centred Gaussian, then 2(X,Y)≤∥Σ(X)−Σ(Y)∥.W_2(X,Y)≤ (X)- (Y) . Remark 2 (properties of the midpoint grids). 1. |k|=kd _k =k^d: the subscript k counts points per axis, not the total number of points. 2. For every x∈Ix∈ I there is xi∈kx_i _k with ∥x−xi∥≤ρk:=12k(∑j=1d|Ij|2)1/2. x-x_i \;≤\; _k:= 12k ( _j=1^d I_j ^2 )^1/2. (12) Choosing xix_i coordinatewise gives |xj−(xi)j|≤|Ij|/(2k) x_j-(x_i)_j ≤ I_j /(2k) for each j leading to (12). Lemma 6 (square-root perturbation). Let A,B∈ℝn×nA,B ^n× n be positive semi-definite with range(A)⊆range(B)range(A) (B). Then ∥A−B∥≤∥A−B∥λ+(B). A- B \;≤\; A-B λ^+(B). Proof. Put W:=range(B)W:=range(B). Since A and B are symmetric with range(A)⊆Wrange(A) W, both vanish on W⟂W and map W into itself, and so do A A and B B. On W the matrix B is positive definite with smallest eigenvalue λ+(B)λ^+(B), and the standard bound ∥A−B∥≤(λmin(A)+λmin(B))−1∥A−B∥ A- B ≤ ( _ (A)+ _ (B) )^-1 A-B for positive definite matrices applies there. All four matrices vanish on W⟂W , so the restriction changes no norm. ∎ Lemma 7 (range of a second-moment matrix). Let V be a random vector in ℝnR^n with ∥V∥2<∞E V ^2<∞ and Σ:=[VV⊤] :=E [V ]. Then V∈range(Σ)V ( ) almost surely. Proof. If Σu=0 u=0 then [(u⊤V)2]=u⊤Σu=0E [(u V)^2 ]=u u=0, so u⊤V=0u V=0 almost surely. Applying this to a basis of kerΣ gives V⟂kerΣ=range(Σ)⟂V =range( ) almost surely. ∎ Appendix B Proofs of Section 2 Theorem 1. Write ∈ℝn1 ^n for the all-ones vector and let Z(r)∈ℝnZ^(r) ^n denote the r-th row of g[]∈ℝm×ng[X] ^m× n, that is Z(r)=(gr(x1),…,gr(xn))⊤Z^(r)= (g_r(x_1),…,g_r(x_n) ) . Step 1 (structure of the evaluation vector). Each gr(x)=⟨Wr,x⟩+brg_r(x)= W_r,x +b_r is an affine function of x with independent centred Gaussian coefficients, so Z(r)Z^(r) is a centred Gaussian vector with Cov(gr(xi),gr(xj))=σw2d⟨xi,xj⟩+σb2=κ(xi,xj) (g_r(x_i),g_r(x_j) )= _w^2d x_i,x_j + _b^2=κ(x_i,x_j) by (1); the pairs (Wr,br)(W_r,b_r) are independent across r, so Z(1),…,Z(m)Z^(1),…,Z^(m) are i.i.d. (0,κ[])N (0,κ[X] ). The input dimension enters only here, through κ. With ϕφ acting componentwise, f[]=∑r=1marϕ(Z(r))+c 1.f[X]\;=\; _r=1^ma_r\,φ (Z^(r) )\;+\;c\,1. By Assumption 1 (1) the vector ϕ(Z(r))φ(Z^(r)) has finite moments of every order, so all quantities below are finite. Step 2 (removing the output bias). Since Kc=K+τc2K_c=K+ _c^2, we may realise G[]=Γ+c 1G[X]= +c\,1 with Γ∼(0,K[]) (0,K[X] ) independent of c, and c is independent of (W,b,a)(W,b,a). Writing f~[]:=∑rarϕ(Z(r)) f[X]:= _ra_rφ(Z^(r)), the independent translation c 1c\,1 cancels by Proposition 2 (3): 2(f[],G[])≤2(f~[],Γ).W_2 (f[X],G[X] )\;≤\;W_2 ( f[X], ). Step 3 (conditional Gaussianity). Condition on (W,b)(W,b), equivalently on Z(1),…,Z(m)Z^(1),…,Z^(m). The coefficients ara_r are i.i.d. (0,τa2/m)N(0, _a^2/m) and independent of (W,b)(W,b), so conditionally f~[] f[X] is a centred Gaussian vector with covariance K^m:=τa2m∑r=1mϕ(Z(r))ϕ(Z(r))⊤,[K^m]=τa2[ϕ(Z)ϕ(Z)⊤]=K[], K_m\;:=\; _a^2m _r=1^mφ (Z^(r) )φ (Z^(r) ) , [ K_m ]= _a^2\,E [φ(Z)φ(Z) ]=K[X], the last identity being (2). By Proposition 2 (4), applied with the Euclidean conditioning variable (W,b)(W,b), 2(f~[],Γ)2≤[2((0,K^m),(0,K[]))2].W_2 ( f[X], )^2\;≤\;E [W_2 (N(0, K_m),\,N(0,K[X]) )^2 ]. Step 4 (covariance perturbation). Apply Lemma 7 to V=τaϕ(Z)V= _aφ(Z), whose second-moment matrix is K[]K[X]: almost surely ϕ(Z)∈range(K[])φ(Z) (K[X] ). Each Z(r)Z^(r) has the law of Z, so almost surely range(K^m)⊆range(K[])range( K_m) (K[X] ). Assumption 1 (3) gives K(x,x)>0K(x,x)>0, so K[]≠0K[X]≠ 0 and λ+(K[])λ^+(K[X]) is defined. Proposition 2 (5) followed by Lemma 6 therefore yields 2((0,K^m),(0,K[]))≤|K^m−K[]|≤∥K^m−K[]∥λ+(K[]).W_2 (N(0, K_m),N(0,K[X]) )\;≤\; K_m- K[X] \;≤\; K_m-K[X] λ^+ (K[X] ). Step 5 (the fluctuation of K^m K_m). The matrices Yr:=τa2ϕ(Z(r))ϕ(Z(r))⊤Y_r:= _a^2φ(Z^(r))φ(Z^(r)) are i.i.d. with mean K[]K[X], and K^m−K[]=1m∑r(Yr−K[]) K_m-K[X]= 1m _r (Y_r-K[X] ). Expanding the Frobenius norm and using that the summands are independent and centred, the cross terms vanish, so ∥K^m−K[]∥2=1m[∥τa2ϕ(Z)ϕ(Z)⊤−K[]∥2].E K_m-K[X] ^2\;=\; 1m\,E [ _a^2φ(Z)φ(Z) -K[X] ^2 ]. Combining Steps 2–5 gives 2(f[],G[])2≤C(ϕ,)2/mW_2(f[X],G[X])^2≤ C(φ,X)^2/m with C(ϕ,)C(φ,X) as in (5). No step above uses global Lipschitz continuity of ϕφ. The only property of the activation that enters is the finiteness of the fourth moment in Step 5, which follows from Assumption 1 (1). ∎ Corollary 2 (at most linear growth). Let ⊂IX⊂ I be a finite sample set with ||=n =n and let ϕφ satisfy Assumption 1 with growth constants A,pA,p. Then the numerator of (5), N:=[∥τa2ϕ(Z)ϕ(Z)⊤−K[]∥2],Z∼(0,κ[])∈ℝn,N:= E [ _a^2\,φ(Z)φ(Z) -K[X] ^2 ], Z (0,κ[X] ) ^n, satisfies N≤τa2A2M4pnN≤ _a^2A^2 M_4p\;n, where Ms:=[(1+|ξ|)s]<∞for s>0 and ξ∼(0,κI2) with κI2:=maxx∈Iκ(x,x)<∞.M_s:=E [(1+ ξ )^s ]<∞ s>0 and ξ (0, _I^2) with _I^2:= _x∈ Iκ(x,x)<∞. The constant depends only on ϕφ through A,pA,p, on I, and on the variances, and not on n. Corollary 2. Abbreviate Z=(Z1,…,Zn)∼(0,κ[])Z=(Z_1,…,Z_n) (0,κ[X] ) and consider the random matrix Y:=τa2ϕ(Z)ϕ(Z)⊤∈ℝn×n,Yij=τa2ϕ(Zi)ϕ(Zj).Y:= _a^2\,φ(Z)φ(Z) ^n× n, Y_ij= _a^2\,φ(Z_i)φ(Z_j). For every pair (i,j)(i,j) the vector (Zi,Zj)(Z_i,Z_j) is centred Gaussian with covariance (κ(xi,xi)κ(xi,xj)κ(xi,xj)κ(xj,xj)) pmatrixκ(x_i,x_i)&κ(x_i,x_j)\\ κ(x_i,x_j)&κ(x_j,x_j) pmatrix, so by (2) we have [Yij]=K(xi,xj)E[Y_ij]=K(x_i,x_j), that is [Y]=K[]E[Y]=K[X]. Step 1 (centring). Entrywise, [(Yij−[Yij])2]=[Yij2]−([Yij])2≤[Yij2]E [(Y_ij-E[Y_ij])^2 ]=E[Y_ij^2]- (E[Y_ij] )^2 [Y_ij^2]. Summing over i,ji,j gives N2=[∥Y−K[]∥2]≤[∥Y∥2].N^2=E [ Y-K[X] ^2 ]\;≤\;E [ Y ^2 ]. Step 2 (reduction to fourth moments). By the definition of the Frobenius norm, ∥Y∥2=(τa2)2∑i,j=1nϕ(Zi)2ϕ(Zj)2,hence[∥Y∥2]=(τa2)2∑i,j=1n[ϕ(Zi)2ϕ(Zj)2]. Y ^2= ( _a^2 )^2 _i,j=1^nφ(Z_i)^2φ(Z_j)^2, [ Y ^2 ]= ( _a^2 )^2 _i,j=1^nE [φ(Z_i)^2φ(Z_j)^2 ]. Step 3 (a uniform fourth-moment bound). By the Cauchy–Schwarz inequality, [ϕ(Zi)2ϕ(Zj)2]≤[ϕ(Zi)4]1/2[ϕ(Zj)4]1/2E[φ(Z_i)^2φ(Z_j)^2] [φ(Z_i)^4]^1/2E[φ(Z_j)^4]^1/2, so it suffices to bound [ϕ(Zi)4]E[φ(Z_i)^4] uniformly in i. Polynomial growth (Assumption 1 (1)) gives ϕ(z)4≤A4(1+|z|)4pφ(z)^4≤ A^4(1+ z )^4p. Each ZiZ_i is centred Gaussian with variance κi2=κ(xi,xi)≤κI2 _i^2=κ(x_i,x_i)≤ _I^2, and for ξ∼(0,1)ξ (0,1) the map σ↦[(1+σ|ξ|)4p]σ [(1+σ ξ )^4p ] is non-decreasing on [0,∞)[0,∞), whence [ϕ(Zi)4]≤A4[(1+|Zi|)4p]≤A4Z∼(0,κI2)[(1+|Z|)4p]=A4M4p.E [φ(Z_i)^4 ]≤ A^4\,E [(1+ Z_i )^4p ]≤ A^4\,E_Z (0, _I^2) [(1+ Z )^4p ]=A^4M_4p. Combining the three steps, N2≤(τa2)2∑i,j=1nA4M4p=(τa2)2A4M4pn2,N^2\;≤\; ( _a^2 )^2 _i,j=1^nA^4M_4p\;=\; ( _a^2 )^2A^4M_4p\,n^2, and taking square roots yields N≤τa2A2M4pnN≤ _a^2A^2 M_4p\,n. The moment M4pM_4p is finite because Gaussian random variables have moments of all orders, and κI2<∞ _I^2<∞ because I is compact and κ is continuous; the constant depends only on A, p, on I through κI2 _I^2, and on the variances σw2,σb2,τa2 _w^2, _b^2, _a^2, as stated. ∎ Proposition 1. Part (1) is Corollary 2. The matrix inside the norm in (5) has n2n^2 entries, each bounded in expectation uniformly over the compact set I, so its Frobenius norm grows like n2=n n^2=n. We bound the centred fluctuation by the second moment of τa2ϕ(Z)ϕ(Z)⊤ _a^2φ(Z)φ(Z) , reduce the Frobenius norm to its entries, and control those by Assumption 1 (1). For part (2), let ⊂IX⊂ I satisfy (6) with constant ν and let n=||n= . Then Corollary 2 and (6) give C(ϕ,)2≤(τa2A2M4pn)2νn=D2n,D:=τa2A2M4pν,C(φ,X)^2\;≤\; ( _a^2A^2 M_4p\,n )^2ν\,n\;=\;D^2n, D:= _a^2A^2 M_4pν, (13) so that C(ϕ,)≤DnC(φ,X)≤ D n, and Theorem 1 gives 2(f[],G[])≤C(ϕ,)m≤Dnm.W_2 (f[X],G[X] )\;≤\; C(φ,X) m\;≤\;D nm. The order n n cannot be improved within (5). For any finite sample set ⊂IX⊂ I with n=||n= , write Z∼(0,κ[])∈ℝnZ (0,κ[X] ) ^n as in Corollary 2. The trace of a positive semi-definite matrix dominates each of its eigenvalues, so by Assumption 1 (1) and κ(xi,xi)≤κI2κ(x_i,x_i)≤ _I^2, arguing as in the proof of Corollary 2, λ+(K[])≤trK[]=τa2∑i=1n[ϕ(Zi)2]≤ν¯n,ν¯:=τa2A2M2p,λ^+ (K[X] )\;≤\; K[X]\;=\; _a^2 _i=1^nE [φ(Z_i)^2 ]\;≤\; ν\,n, ν:= _a^2A^2M_2p, (14) so linear growth is the largest order the denominator can have. Combining (14) with (6) and tr(K[])≥rank(K[])λ+(K[])tr(K[X]) (K[X])\,λ^+(K[X]) gives rank(K[])≤ν¯/νrank(K[X])≤ ν/ν so the condition forces the K[]K[X] to have bounded rank. This excludes every activation for which this rank is unbounded, in particular every activation whose kernel K is strictly positive definite on I, since then rank(K[])=||rank(K[X])=|X|. The condition is therefore a finite-rank condition, and Lemma 1 verifies it for the midpoint grids with polynomial activations. ∎ Appendix C Proofs of Section 3 Lemma 1. Write ϕ(z)=∑h=0rβhzhφ(z)= _h=0^r _hz^h with βr≠0 _r≠ 0, and abbreviate R:=(r+d)R:= r+dd. Step 1 (finite-rank representation of the kernel). Let ξ0∼(0,1) _0 (0,1) and ξ1∼(0,Id×d) _1 (0,I_d× d) be independent, and set Zx:=σwdξ1⊤x+σbξ0,x∈ℝd.Z_x\;:=\; _w d\, _1 x+ _b\, _0, x ^d. (15) This realisation has the covariance required by (2): by independence of ξ0 _0 and ξ1 _1, Cov(Zx,Zy)=σw2dCov(ξ1⊤x,ξ1⊤y)+σb2Var(ξ0)=σw2d⟨x,y⟩+σb2=κ(x,y). (Z_x,Z_y)\;=\; _w^2d\, ( _1 x, _1 y )+ _b^2\, ( _0)\;=\; _w^2d\, x,y + _b^2\;=\;κ(x,y). By the binomial theorem, ϕ(Zx)=∑h=0rβhZxh=∑i=0r(ξ1⊤x)iPi,Pi:=(σw2d)i/2∑h=ir(hi)βh(σbξ0)h−i∈ℝ.φ(Z_x)\;=\; _h=0^r _hZ_x^h\;=\; _i=0^r ( _1 x )^iP_i, P_i\;:=\; ( _w^2d )^\!i/2 _h=i^r hi _h\,( _b _0)^h-i\;∈\;R. (16) For 0≤i≤r0≤ i≤ r define φi:ℝd→ℝ(i+d−1d−1) _i:R^d i+d-1d-1 by φi(x)=⨁|α|=i(iα1,…,αd)xα, _i(x)\;=\; _ α =i i _1,…, _d\;x^α, (17) the dimension (i+d−1d−1) i+d-1d-1 being the number of multi-indices of total degree i. Fixing the order of these multi-indices gives a bijection ei:1,…,(i+d−1d−1)→α∈ℕ0d:|α|=ie_i: \1,…, i+d-1d-1 \→\α _0^d: α =i\ between the coordinates of φi _i and the multi-indices of degree i. In this notation the multinomial theorem reads (ξ1⊤x)i=⟨φi(ξ1),φi(x)⟩ ( _1 x )^i= _i( _1), _i(x) , so (16) becomes ϕ(Zx)=∑i=0r⟨Piφi(ξ1),φi(x)⟩=⟨⨁i=0rPiφi(ξ1),⨁i=0rφi(x)⟩.φ(Z_x)\;=\; _i=0^r P_i\, _i( _1),\, _i(x) \;=\; _i=0^rP_i\, _i( _1),\; _i=0^r _i(x) . (18) The vectors in the last inner product have dimension ∑i=0r(i+d−1d−1)=R _i=0^r i+d-1d-1=R. Setting Ψ(x):=⨁i=0rφi(x)∈ℝR,Φ:=⨁i=0rPiφi(ξ1),M:=τa2[ΦΦ⊤], (x):= _i=0^r _i(x) ^R, := _i=0^rP_i\, _i( _1), M:= _a^2\,E [ ], we obtain from (2) and (18) K(x,y)=τa2[ϕ(Zx)ϕ(Zy)]=Ψ(x)⊤MΨ(y).K(x,y)\;=\; _a^2\,E [φ(Z_x)φ(Z_y) ]\;=\; (x) M\, (y). (19) The matrix M is positive semi-definite, and M≠0M≠ 0: since degϕ=r φ=r, the sum defining PrP_r in (16) has only the term h=rh=r, so Pr=βr(σw2/d)r/2≠0P_r= _r( _w^2/d)^r/2≠ 0 is deterministic, and the degree-r diagonal block of M equals τa2βr2(σw2/d)r[φr(ξ1)φr(ξ1)⊤]≠0 _a^2 _r^2( _w^2/d)^r\,E [ _r( _1) _r( _1) ]≠ 0. In particular λ+(M)>0λ^+(M)>0. Let Vk∈ℝkd×RV_k ^k^d× R be the matrix with rows Ψ(x1)⊤,…,Ψ(xkd)⊤ (x_1) ,…, (x_k^d) , where k=x1,…,xkdX_k=\x_1,…,x_k^d\. Then (19) gives K[k]=VkMVk⊤,K[X_k]\;=\;V_kMV_k , (20) whence rankK[k]≤rank(M)≤R K[X_k]≤ (M)≤ R, which is the first assertion. Step 2 (passing to a matrix of fixed dimension). Put B:=VkM1/2B:=V_kM^1/2, so that K[k]=BB⊤K[X_k]=B , and set Tk:=B⊤B=M1/2Vk⊤VkM1/2∈ℝR×R.T_k\;:=\;B B\;=\;M^1/2V_k V_kM^1/2\;∈\;R^R× R. (21) The matrices BB⊤B and B⊤B B have the same nonzero eigenvalues, so λ+(K[k])=λ+(Tk)λ^+ (K[X_k] )=λ^+(T_k) whenever Tk≠0T_k≠ 0. Unlike K[k]K[X_k], the matrix TkT_k has dimension R, independent of k. We therefore analyse the normalised moment matrix Θk:=1kdVk⊤Vk∈ℝR×R,so thatTk=kdM1/2ΘkM1/2. _k\;:=\; 1k^dV_k V_k\;∈\;R^R× R, that T_k\;=\;k^d\,M^1/2 _kM^1/2. (22) Step 3 (the Riemann-sum limit). Index the rows and columns of Θk _k by pairs (i,s)(i,s) with 0≤i≤r0≤ i≤ r and 1≤s≤(i+d−1d−1)1≤ s≤ i+d-1d-1, where (i,s)(i,s) refers to the s-th coordinate of the degree-i block of Ψ . By (17), (Θk)(i,s),(j,t)=1kd∑l=1kd(φi(xl))s(φj(xl))t=c(i,s),(j,t)⋅1kd∑l=1kdxlei(s)+ej(t), ( _k )_(i,s),(j,t)\;=\; 1k^d _l=1^k^d ( _i(x_l) )_s ( _j(x_l) )_t\;=\;c_(i,s),(j,t)· 1k^d _l=1^k^dx_l^\,e_i(s)+e_j(t), (23) where c(i,s),(j,t):=[(iei(s))(jej(t))]1/2c_(i,s),(j,t):= [ ie_i(s) je_j(t) ]^1/2 does not depend on k. Since kX_k is the product grid (8), the points xlx_l are the midpoints of the kdk^d cells of a uniform partition of I, each of volume Vol(I)/kd (I)/k^d. The sum in (23) is therefore the d-dimensional midpoint rule for the continuous function x↦xαx x^α with α:=ei(s)+ej(t)α:=e_i(s)+e_j(t), and 1kd∑l=1kdxlα=1Vol(I)∑l=1kdVol(I)kdxlα→k→∞1Vol(I)∫Ixαx. 1k^d _l=1^k^dx_l^α\;=\; 1 (I) _l=1^k^d (I)k^d\,x_l^α\; [k→∞]\; 1 (I) _Ix^α\,dx. (24) Writing H for the matrix with entries H(i,s),(j,t):=c(i,s),(j,t)Vol(I)−1∫Ixei(s)+ej(t)xH_(i,s),(j,t):=c_(i,s),(j,t) (I)^-1 _Ix^e_i(s)+e_j(t)\,dx, the convergence (24) holds entrywise, and since the dimension R does not depend on k this gives ∥Θk−H∥→0 _k-H → 0. The limit H is positive definite. Indeed, for u∈ℝRu ^R, u⊤Hu=1Vol(I)∫Iqu(x)2x,qu(x):=∑i=0r∑s=1(i+d−1d−1)u(i,s)(iei(s))xei(s).u Hu\;=\; 1 (I) _Iq_u(x)^2\,dx, q_u(x)\;:=\; _i=0^r\; _s=1 i+d-1d-1u_(i,s) ie_i(s)\;x^e_i(s). (25) The map (i,s)↦ei(s)(i,s) e_i(s) is a bijection onto α:|α|≤r\α: α ≤ r\, and the monomials xαx^α are linearly independent, so u≠0u≠ 0 implies qu≢0q_u ≡ 0. A nonzero polynomial vanishes on a Lebesgue null set, so the integral in (25) is strictly positive, and λmin(H)>0 _ (H)>0. For every unit vector v, v⊤Θkv≥v⊤Hv−|v⊤(Θk−H)v|≥λmin(H)−∥Θk−H∥,v _kv\;≥\;v Hv- v ( _k-H)v \;≥\; _ (H)- _k-H , so there is k1∈ℕk_1 with λmin(Θk)≥12λmin(H)> 0for all k≥k1. _ ( _k)\;≥\; 12 _ (H)\;>\;0 all k≥ k_1. (26) Step 4 (conclusion). Fix k≥k1k≥ k_1. By (26) the matrix Θk _k is positive definite, so Tk≠0T_k≠ 0: if M1/2ΘkM1/2=0M^1/2 _kM^1/2=0 then ∥Θk1/2M1/2u∥2=u⊤M1/2ΘkM1/2u=0 _k^1/2M^1/2u ^2=u M^1/2 _kM^1/2u=0 for every u, forcing M1/2=0M^1/2=0 and hence M=0M=0, which Step 1 excludes. From (21) we have range(Tk)⊆range(M1/2)=range(M)range(T_k) (M^1/2)=range(M), and every unit vector v∈range(M)v (M) satisfies v⊤Mv≥λ+(M)v Mv≥λ^+(M). Hence for every unit vector v∈range(Tk)v (T_k), 1kdv⊤Tkv=(M1/2v)⊤Θk(M1/2v)≥λmin(Θk)∥M1/2v∥2=λmin(Θk)v⊤Mv≥λmin(Θk)λ+(M). split 1k^d\,v T_kv&= (M^1/2v ) _k (M^1/2v )\\ &≥ _ ( _k)\, M^1/2v ^2\\ &= _ ( _k)\,v Mv\\ &≥ _ ( _k)\,λ^+(M). split (27) Minimising over such v gives λ+(K[k])=λ+(Tk)≥kdλmin(Θk)λ+(M)λ^+ (K[X_k] )=λ^+(T_k)≥ k^d _ ( _k)λ^+(M), and with (26), λ+(K[k])≥νkdfor every k≥k1,ν:=12λmin(H)λ+(M)> 0.λ^+ (K[X_k] )\;≥\;ν\,k^d every k≥ k_1, ν:= 12 _ (H)\,λ^+(M)\;>\;0. For the finitely many k<k1k<k_1, Assumption 1(3) gives, for every x∈kx _k, that κ(x,x)>0κ(x,x)>0 and that ϕφ does not vanish (0,κ(x,x))N(0,κ(x,x))-almost everywhere, so K(x,x)=τa2[ϕ(Zx)2]>0K(x,x)= _a^2\,E[φ(Z_x)^2]>0. Hence K[k]≠0K[X_k]≠ 0 and λ+(K[k])>0λ^+(K[X_k])>0; replacing ν by minν,mink<k1k−dλ+(K[k])>0 \ν,\ _k<k_1k^-dλ^+(K[X_k])\>0 gives the bound for every k∈ℕk . ∎ Lemma 2. Step 1 (the supremum bound). The affine change of variables xj=aj+bj2+|Ij|2tjx_j= a_j+b_j2+ I_j 2t_j maps [−1,1]d[-1,1]^d onto I and preserves total degree. Writing p~(t):=p(x(t)) p(t):=p(x(t)), we have ∥p∥0(I)=∥p~∥0([−1,1]d) p _C^0(I)= p _C^0([-1,1]^d) and ∥p∥L2(I)2=2−dVol(I)∥p~∥L2([−1,1]d)2 p _L^2(I)^2=2^-d (I)\, p _L^2([-1,1]^d)^2, so it suffices to prove ∥p~∥0≤2−d/2(r+1)d∥p~∥L2 p _C^0≤ 2^-d/2(r+1)^d p _L^2 on the cube. Let P0,P1,…P_0,P_1,… be the Legendre polynomials on [−1,1][-1,1], so that ∥Pn∥∞=1 P_n _∞=1 and ∫−11Pn2=22n+1 _-1^1P_n^2= 22n+1. Since p~ p has degree at most r in each coordinate, it expands as p~(t)=∑αcα∏j=1dPαj(tj) p(t)= _αc_α _j=1^dP_ _j(t_j) over multi-indices α with αj≤r _j≤ r, and these products are orthogonal on [−1,1]d[-1,1]^d. Hence ∥p~∥0≤∑α|cα|≤(∑αcα2∏j22αj+1)1/2(∑α∏j2αj+12)1/2=∥p~∥L2(∏j=1d∑n=0r2n+12)1/2, p _C^0≤ _α c_α ≤ ( _αc_α^2 _j 22 _j+1 )^1/2 ( _α _j 2 _j+12 )^1/2= p _L^2 ( _j=1^d _n=0^r 2n+12 )^1/2, by Cauchy–Schwarz and Parseval. As ∑n=0r2n+12=(r+1)22 _n=0^r 2n+12= (r+1)^22, the last factor equals 2−d/2(r+1)d2^-d/2(r+1)^d, which proves the first inequality in (10). Step 2 (sample paths). Each coordinate of Wx+bWx+b is affine in x, so ϕφ applied to it is a polynomial of total degree at most r; hence f(x)=a⊤ϕ(Wx+b)+cf(x)=a φ(Wx+b)+c lies in rP_r for every realisation. For G, Step 1 of the proof of Lemma 1 gives K(x,y)=Ψ(x)⊤MΨ(y)K(x,y)= (x) M (y) with Ψ a vector of polynomials of degree at most r and M⪰0M 0. Let ζ∼(0,M)ζ (0,M) and c′∼(0,τc2)c (0, _c^2) be independent, and set G~(x):=Ψ(x)⊤ζ+c′ G(x):= (x) ζ+c . Then G~ G is a centred Gaussian process with Cov(G~(x),G~(y))=Ψ(x)⊤MΨ(y)+τc2=Kc(x,y) ( G(x), G(y))= (x) M (y)+ _c^2=K_c(x,y), so G~ G has the law of G, and its sample paths lie in rP_r. ∎ Lemma 3. Partition I into the kdk^d cells Q1,…,QkdQ_1,…,Q_k^d of the grid, each of volume Vol(I)/kd (I)/k^d and each containing its grid point xix_i as midpoint. For x∈Qix∈ Q_i we have ∥x−xi∥2≤ρk x-x_i _2≤ _k by (12), so |h(x)|≤|h(xi)|+|h(x)−h(xi)|≤|h(xi)|+[h]γ(I)∥x−xi∥2γ≤|h(xi)|+[h]γ(I)ρkγ, h(x) ≤ h(x_i) + h(x)-h(x_i) ≤ h(x_i) +[h]_C^γ(I) x-x_i _2^γ≤ h(x_i) +[h]_C^γ(I) _k^γ, hence h(x)2≤2h(xi)2+2ρk2γ[h]γ(I)2h(x)^2≤ 2h(x_i)^2+2 _k^2γ[h]^2_C^γ(I). Integrating over QiQ_i and summing over i, ∥h∥L2(I)2 h ^2_L^2(I) =∑i=1kd∫Qih(x)2x = _i=1^k^d _Q_ih(x)^2\,dx ≤Vol(I)kd∑i=1kd(2h(xi)2+2ρk2γ[h]γ(I)2) ≤ (I)k^d _i=1^k^d (2h(x_i)^2+2 _k^2γ[h]^2_C^γ(I) ) =2Vol(I)kd∥h[k]∥2+2Vol(I)ρk2γ[h]γ(I)2. =2 (I)k^d h[X_k] ^2+2 (I) _k^2γ[h]^2_C^γ(I). ∎ Lemma 4. We regard f and G as random elements of the Polish space 0(I)C^0(I). The grid evaluations f[]f[X] and G[]G[X] are random vectors in ℝnR^n. Let π∗π^* be an optimal coupling of their laws for the quadratic Wasserstein distance, which exists by [Villani, 2008, Theorem 4.1]. Since 2,nW_2,n is a positive multiple of 2W_2, the coupling π∗π^* is optimal for the rescaled distance as well. Because 0(I)C^0(I) is Polish, the regular conditional distributions μfu:=ℙf|f[]=u,μGv:=ℙG|G[]=v,u,v∈ℝn,μ^f_u:=P_f f[X]=u, μ^G_v:=P_G G[X]=v, u,v ^n, exist, and by disintegration 1=ℙ(f[]=f[])=∫ℝnμuf(φ:φ[]=u)dℙf[](u)1=P (f[X]=f[X] )= _R^nμ^f_u (\ : [X]=u\ )\,dP_f[X](u), so μufμ^f_u is concentrated on the fibre φ:φ[]=u\ : [X]=u\ for ℙf[]P_f[X]-almost every u; likewise for μvGμ^G_v. Define the measure π(A):=∫ℝn×ℝn(μuf⊗μvG)(A)dπ∗(u,v),A⊆0(I)×0(I) Borel,π(A):= _R^n×R^n (μ^f_u μ^G_v )(A)\,dπ^*(u,v), A ^0(I)×C^0(I) Borel, which is a probability measure since (u,v)↦μuf⊗μvG(u,v) μ^f_u μ^G_v is a probability kernel; on rectangles, π(A1×A2)=∫μuf(A1)μvG(A2)dπ∗(u,v)π(A_1× A_2)= μ^f_u(A_1)\,μ^G_v(A_2)\,dπ^*(u,v). The two coordinate projections on (0(I)×0(I),π) (C^0(I)×C^0(I),π ) define random functions f~ f and G~ G. We check the marginals: ℙ(f~∈A1) ( f∈ A_1 ) =∫ℝn×ℝnμuf(A1)μvG(0(I))⏟=1dπ∗(u,v) = _R^n×R^nμ^f_u(A_1)\, μ^G_v (C^0(I) )_=1\,dπ^*(u,v) =∫ℝnμuf(A1)dℙf[](u) = _R^nμ^f_u(A_1)\,dP_f[X](u) =∫ℝnℙ(f∈A1∣f[]=u)dℙf[](u) = _R^nP (f∈ A_1 f[X]=u )\,dP_f[X](u) =ℙ(f∈A1), =P(f∈ A_1), where the second equality uses that the first marginal of π∗π^* is ℙf[]P_f[X], and for G the argument works the same. Moreover, for every Borel set A⊆ℝn×ℝnA ^n×R^n, ℙ((f~[],G~[])∈A) ( ( f[X], G[X] )∈ A ) =∫ℝn×ℝn(μuf⊗μvG)((φ,ψ):(φ[],ψ[])∈A)dπ∗(u,v) = _R^n×R^n (μ^f_u μ^G_v ) (\( ,ψ):( [X],ψ[X])∈ A\ )\,dπ^*(u,v) =∫ℝn×ℝn(δu⊗δv)(A)dπ∗(u,v) = _R^n×R^n ( _u _v )(A)\,dπ^*(u,v) =∫ℝn×ℝnA(u,v)dπ∗(u,v) = _R^n×R^n1_A(u,v)\,dπ^*(u,v) =π∗(A), =π^*(A), where the second equality uses the concentration on the fibres, whose exceptional sets are π∗π^*-null because they are null under the marginals of π∗π^*. Therefore (f~,G~)( f, G) is a coupling of f and G whose evaluations (f~[],G~[]) ( f[X], G[X] ) have the optimal law π∗π^*, and consequently [∥f~[]−G~[]∥n2]=∫ℝn×ℝn∥u−v∥n2dπ∗(u,v)=2,n(f[],G[])2.E [ f[X]- G[X] _n^2 ]= _R^n×R^n u-v _n^2\,dπ^*(u,v)=W_2,n (f[X],G[X] )^2. ∎ Theorem 2. Fix γ=12γ= 12 and k≥k1k≥ k_1, with k1k_1 as in Lemma 1, and let (f~,G~)( f, G) be the coupling of Lemma 4 for kX_k; write h:=f~−G~h:= f- G, so that n=|k|=kdn= _k =k^d. Since ϕφ is a polynomial of degree r, Lemma 2 gives that f and G have sample paths in rP_r almost surely, hence so does h, and (10) may be applied pathwise. Combining it with (11) of Lemma 3 and taking expectations, [∥h∥0(I)2]≤(r+1)2dVol(I)[∥h∥L2(I)2]≤ 2(r+1)2d([∥h[k]∥kd2]+ρk[[h]1/2(I)2]),E [ h ^2_C^0(I) ]\;≤\; (r+1)^2d (I)\,E [ h ^2_L^2(I) ]\;≤\;2\,(r+1)^2d (E [ h[X_k] _k^d^2 ]+ _k\,E [[h]^2_C^1/2(I) ] ), (28) the volume cancelling between the two steps. By Lemma 4 the first expectation equals 2,kd(f[k],G[k])2W_2,k^d (f[X_k],G[X_k] )^2. The grids kX_k satisfy the effective-rank condition of Assumption 2 with a constant ν that does not depend on k, by Lemma 1, so Equation 7 applies with n=kdn=k^d and gives 2,kd(f[k],G[k])2≤D2m,W_2,k^d (f[X_k],G[X_k] )^2\;≤\; D^2m, (29) uniformly in k, with D as in (13). For the second expectation, [⋅]1/2(I)[\,·\,]_C^1/2(I) is a seminorm, so [h]1/2(I)2≤2[f~]1/2(I)2+2[G~]1/2(I)2[h]^2_C^1/2(I)≤ 2[ f]^2_C^1/2(I)+2[ G]^2_C^1/2(I) pathwise. Since f~=f f d=f and G~=G G d=G, this gives [[h]1/2(I)2]≤ 2[[f]1/2(I)2]+2[[G]1/2(I)2]=:Λ,E [[h]^2_C^1/2(I) ]\;≤\;2\,E [[f]^2_C^1/2(I) ]+2\,E [[G]^2_C^1/2(I) ]\;=:\; , (30) and Λ does not depend on k, since it involves only the laws of f and G. Therefore we need to prove that Λ stays finite. To bound the first term, let WrW_r be the r-th row of W, so that gr(x)=⟨Wr,x⟩+brg_r(x)= W_r,x +b_r. Since I is convex and ϕφ is absolutely continuous with |ϕ′(z)|≤A′(1+|z|)p′ φ (z) ≤ A (1+ z )^p (Assumption 1 (2)), each map x↦ϕ(gr(x))x φ(g_r(x)) is Lipschitz on I with constant Lr:=A′∥Wr∥(1+maxx∈I|gr(x)|)p′.L_r\;:=\;A W_r (1+ _x∈ I g_r(x) )^p . As f(x)−f(y)=∑r=1mar(ϕ(gr(x))−ϕ(gr(y)))f(x)-f(y)= _r=1^ma_r (φ(g_r(x))-φ(g_r(y)) ), for x,y∈Ix,y∈ I |f(x)−f(y)|≤∑r=1m|ar|Lr∥x−y∥≤diam(I)1/2∑r=1m|ar|Lr∥x−y∥1/2, f(x)-f(y) \;≤\; _r=1^m a_r L_r\, x-y \;≤\;diam(I)^1/2 _r=1^m a_r L_r\, x-y ^1/2, hence [[f]1/2(I)2]≤diam(I)[(∑r=1m|ar|Lr)2]<∞,E [[f]^2_C^1/2(I) ]\;≤\;diam(I)\,E [ ( _r=1^m a_r L_r )^2 ]\;<\;∞, the parameters being Gaussian and hence having moments of every order. The same Lipschitz bound controls the second term. By Step 1 of the proof of Theorem 1, the pair (g1(x),g1(y)) (g_1(x),g_1(y) ) has the law of (Zx,Zy)(Z_x,Z_y) in (2), and the constant τc2 _c^2 in (3) cancels, so applying the bound to the first neuron gives, for x,y∈Ix,y∈ I, [(G(x)−G(y))2] [ (G(x)-G(y) )^2 ] =Kc(x,x)−2Kc(x,y)+Kc(y,y)=τa2[(ϕ(g1(x))−ϕ(g1(y)))2] =K_c(x,x)-2K_c(x,y)+K_c(y,y)= _a^2\,E [ (φ(g_1(x))-φ(g_1(y)) )^2 ] ≤τa2[L12]∥x−y∥2=:L2∥x−y∥2. ≤ _a^2\,E [L_1^2 ] x-y ^2\;=:\;L^2 x-y ^2. Since G(x)−G(y)G(x)-G(y) is centred Gaussian, it follows that |G(x)−G(y)|4d≤μ4dL4d∥x−y∥d+3d,μ4d:=|ξ|4d,ξ∼(0,1).E G(x)-G(y) ^4d\;≤\; _4dL^4d x-y ^d+3d, _4d:=E ξ ^4d,\ ξ (0,1). The Kolmogorov–Chentsov theorem in the form of Revuz and Yor [1999, Theorem I.2.1] covers Hölder exponents below 3d/4d=343d/4d= 34, in particular 12 12, and yields [[G]1/2(I)4d]<∞E [[G]^4d_C^1/2(I) ]<∞ for the continuous version of G from Lemma 2, with which the modification provided by the theorem is indistinguishable. By Jensen’s inequality, [[G]1/2(I)2]≤[[G]1/2(I)4d]1/(2d)<∞E [[G]^2_C^1/2(I) ] [[G]^4d_C^1/2(I) ]^1/(2d)<∞, and hence Λ<∞ <∞. The pair (f~,G~)( f, G) is a coupling of f and G as random elements of 0(I)C^0(I), so by Definition 3, (28) and (30), 20(I)(f,G)2≤[∥h∥0(I)2]≤2(r+1)2dD2m+ 2(r+1)2dΛρk.W_2^C^0(I)(f,G)^2\;≤\;E [ h ^2_C^0(I) ]\;≤\; 2\,(r+1)^2dD^2m\;+\;2\,(r+1)^2d\, \, _k. (31) Neither the left hand side nor the finite constant Λ depends on k, and ρk=O(k−1) _k=O(k^-1) by (12), so letting k→∞k→∞ in (31) removes the second term and leaves 20(I)(f,G)2≤2(r+1)2dD2m=(C∗)2m,W_2^C^0(I)(f,G)^2\;≤\; 2\,(r+1)^2dD^2m\;=\; (C )^2m, since D=τa2A2M4p/νD= _a^2A^2 M_4p/ν by (13). Taking square roots gives (9). ∎ Corollary 1. For S⊆IS I and any h∈0(I)h ^0(I) we have ∥h∥0(S)≤∥h∥0(I) h _C^0(S)≤ h _C^0(I). Applying this pathwise to h=f−Gh=f-G under any coupling and taking the infimum gives the first inequality; Theorem 2 gives the second. ∎ Appendix D Beyond Polynomial Activations For a general activation, an interpolation inequality of Gagliardo–Nirenberg type [Nirenberg, 2011] bounds the supremum norm by the L2(I)L^2(I) norm and the Hölder seminorm together. Lemma 5. Write ℓj:=|Ij|>0 _j:= I_j >0, ℓmin:=minjℓj _ := _j _j, L:=[h]γ(I)L:=[h]_C^γ(I) and M:=∥h∥0(I)M:= h _C^0(I). Since h is continuous and I is compact, M is attained at some x0∈Ix_0∈ I; replacing h by −h-h if necessary we may assume h(x0)=M≥0h(x_0)=M≥ 0. If M=0M=0 the inequality is trivial. If L=0L=0, then h≡Mh≡ M , so ∥h∥L2(I)=MVol(I)≥Mℓmind/2 h _L^2(I)=M (I)≥ M _ ^d/2 and already the second term on the right-hand side is at least 2M2M. Assume from now on M,L>0M,L>0. For x∈Ix∈ I, Hölder continuity gives h(x)≥M−L∥x−x0∥γh(x)≥ M-L x-x_0 ^γ. Choose δ:=(M2L)1/γδ:= ( M2L )^1/γ, so that Lδγ=M2Lδ^γ= M2, and η:=δ/dη:=δ/ d. Let J:=∏j=1dJj,Jj:=[x0,j−η,x0,j+η]∩Ij.J:= _j=1^dJ_j, J_j:=[x_0,j-η,\,x_0,j+η]∩ I_j. Every x∈Jx∈ J satisfies ∥x−x0∥≤dη=δ x-x_0 ≤ d\,η=δ, hence h(x)≥M2h(x)≥ M2 on J. Since x0,j∈Ijx_0,j∈ I_j, we get |Jj|≥min(η,ℓj)≥min(η,ℓmin) J_j ≥ (η, _j)≥ (η, _ ), so Vol(J)≥min(η,ℓmin)d (J)≥ (η, _ )^d and ∥h∥L2(I)2≥∫Jh(x)2x≥M24min(η,ℓmin)d. h _L^2(I)^2≥ _Jh(x)^2\,dx≥ M^24\, (η, _ )^d. Case 1: η≤ℓminη≤ _ . Substituting η, ∥h∥L2(I)2≥M24d−d/2(M2L)d/γ=M2γ+dγ22γ+dγd/2Ld/γ, h _L^2(I)^2≥ M^24\,d^-d/2 ( M2L )^d/γ= M 2γ+dγ2 2γ+dγ\,d^d/2\,L^d/γ, and raising both sides to the power γ2γ+d γ2γ+d gives M≤2dγd2(2γ+d)Ld2γ+d∥h∥L2(I)2γ2γ+d.M≤ 2\,d γ d2(2γ+d)\,L d2γ+d\, h _L^2(I) 2γ2γ+d. Case 2: η>ℓminη> _ . Then ∥h∥L2(I)2≥M24ℓmind h _L^2(I)^2≥ M^24\, _ ^d, i.e. M≤2ℓmin−d/2∥h∥L2(I)M≤ 2\, _ ^-d/2\, h _L^2(I). In either case M is bounded by one of the two non-negative terms on the right-hand side of the claim, hence by their sum. ∎