Minimum-norm interpolation and double descent

By [F1], $X^{+}$ exists uniquely and has size $p\times n$, so $X^{+}y$ is a well-defined vector in ${\mathbb{R}}^p$.

By [F2], this vector is exactly the unique minimum-norm least-squares solution, which verifies the equivalent characterization.

For $n$ large enough that $t_n:=(n\mathrm{/}(2\log n){)}^{1\mathrm{/}d}\ge 2$, put $m_n=\lfloor t_n\rfloor$ and partition each coordinate interval of $\mathrm{\Omega }$ into $m_n$ equal half-open intervals, closing the last interval at its right endpoint. This gives $m_n^d$ disjoint cells covering $\mathrm{\Omega }$. Each cell differs from a half-open box with the same coordinate bounds only on its boundary faces, which lie in finitely many coordinate hyperplanes. By [F4] those hyperplanes and every subset of their union are measurable and null, so each cell is measurable and has the same measure as that half-open box, namely $(L\mathrm{/}{m}_n{)}^d$ by [F1]. The same argument for the boundary of $\mathrm{\Omega }$ gives ${\lambda }_d(\mathrm{\Omega })=L^d$. Hence normalized Lebesgue measure assigns each cell probability $(L\mathrm{/}{m}_n{)}^d\mathrm{/}{L}^d=m_n^{-d}$.

For a fixed cell, independence [F3] gives probability $(1-m_n^{-d}{)}^n\le e^{-n\mathrm{/}{m}_n^d}$ that it is empty. By [F2], the probability that some cell is empty is at most $m_n^d{e}^{-n\mathrm{/}{m}_n^d}\le n{e}^{-2\log n}=1\mathrm{/}n$, because $m_n^d\le n\mathrm{/}(2\log n)$ and hence $n\mathrm{/}{m}_n^d\ge 2\log n$.

On the complementary event every cell contains a sample point. Every $x\in \mathrm{\Omega }$ belongs to one cell, whose Euclidean diameter is $L\sqrt{d}\mathrm{/}{m}_n$; therefore $h_n\le L\sqrt{d}\mathrm{/}{m}_n$. Since $t_n\ge 2$ implies $m_n=\lfloor t_n\rfloor \ge t_n\mathrm{/}2$, we obtain $h_n\le 2L\sqrt{d}{\left(\frac{2\log n}{n}\right)}^{1\mathrm{/}d}=C_{d}L{\left(\frac{\log n}{n}\right)}^{1\mathrm{/}d}\mathrm{.}$ The event has probability at least $1-1\mathrm{/}n$ by step 2.1.

Write a rank-$q$ singular value decomposition $X=U_q{D}_q{V}_q^{\mathsf{T}}$ with positive diagonal $D_q$. The four Penrose equations and uniqueness [F2] give $X^{+}=V_q{D}_q^{-1}{U}_q^{\mathsf{T}}$, $I_p-X^{+}X=I_p-V_q{V}_q^{\mathsf{T}}$, and $X^{+}(X^{+}{)}^{\mathsf{T}}=V_q{D}_q^{-2}{V}_q^{\mathsf{T}}=(X^{\mathsf{T}}X{)}^{+}$; the last equality follows by checking the four equations for $X^{\mathsf{T}}X=V_q{D}_q^2{V}_q^{\mathsf{T}}$. The same decomposition gives $S^{+}=n(X^{\mathsf{T}}X{)}^{+}$.

For any fixed $v\in {\mathbb{R}}^p$, [A2] gives $\mathbb{E}[(z_0^{\mathsf{T}}v{)}^2\mid X,\epsilon ]=v^{\mathsf{T}}{I}_{p}v=\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$. Taking $v=\widehat{\beta }-\beta$ and then expectation over $\epsilon$ reduces $\mathcal{R}(X)$ to ${\mathbb{E}}_{\epsilon }[\mathrm{\parallel }\widehat{\beta }-\beta {\mathrm{\parallel }}_2^2\mid X]$.

Put $Q=I_p-X^{+}X$. From the definition of $\widehat{\beta }$, $\widehat{\beta }-\beta =-Q\beta +X^{+}\epsilon$. Expanding the squared norm, the cross term has conditional expectation zero by [A1], and the noise term is ${\mathbb{E}}_{\epsilon }[\mathrm{\parallel }{X}^{+}\epsilon {\mathrm{\parallel }}_2^2\mid X]={\sigma }^2\mathrm{tr}(X^{+}(X^{+}{)}^{\mathsf{T}})={\sigma }^2\mathrm{tr}((X^{\mathsf{T}}X{)}^{+}),$ using step 1.1. Combining with step 1.2 and the scaling identity in step 1.1 proves the two displayed risk formulas.

We first prove that for every real univariate polynomial $r$ of degree at most $N\ge 1$, $\mathrm{\mid }{r}^{\mathrm{\prime }}(u)\mathrm{\mid }\le \frac{100N}{\sqrt{1-u^2}}{\sup }_{-1\le v\le 1}\mathrm{\mid }r(v)\mathrm{\mid }(-1<u<1)\mathrm{.}$ For $m\ge 1$ define the finite trigonometric polynomial $F_m(t)={\sum }_{\mathrm{\mid }k\mathrm{\mid }<m}(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}m)e^{ikt}=\frac{1}{m}{\mid {\sum }_{j=0}^{m-1}{e}^{ijt}\mid }^2=\frac{{\sin }^2(mt\mathrm{/}2)}{m{\sin }^2(t\mathrm{/}2)}\mathrm{.}$ Here $i^2=-1$; the square identity follows by expanding the finite sum and counting pairs of indices with a prescribed difference, and the last identity follows from the finite geometric series, with continuous values at multiples of $2\pi$. For $\mathrm{\mid }t\mathrm{\mid }\le 1\mathrm{/}m$, differentiate the finite Fourier sum to obtain $\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }\le {\sum }_{\mathrm{\mid }k\mathrm{\mid }<m}\mathrm{\mid }k\mathrm{\mid }(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}m)\le m^2$. For $1\mathrm{/}m\le \mathrm{\mid }t\mathrm{\mid }\le \pi$, differentiating the sine quotient gives $\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }\le \frac{{\pi }^2}{t^2}+\frac{{\pi }^3}{m\mathrm{\mid }t{\mathrm{\mid }}^3},$ because $\mathrm{\mid }\sin (t\mathrm{/}2)\mathrm{\mid }\ge \mathrm{\mid }t\mathrm{\mid }\mathrm{/}\pi$. This sine bound follows on $[0,\pi \mathrm{/}2]$ by concavity of sine, whose second derivative is $-\sin \le 0$, applied to the chord joining $(0,0)$ and $(\pi \mathrm{/}2,1)$; symmetry gives the negative arguments.

Put $Q=[-1,1{]}^d$ and $Q_c=[-1\mathrm{/}2,1\mathrm{/}2{]}^d$. For a univariate polynomial of degree at most $n$, interpolate at $t_j=-1\mathrm{/}2+j\mathrm{/}n$ for $0\le j\le n$. The interpolation identity holds because its difference from the polynomial has degree at most $n$ and $n+1$ distinct roots; the root bound follows by successively factoring each distinct root. For $\mathrm{\mid }t\mathrm{\mid }\le 1$ the absolute value of the $j$th Lagrange polynomial is at most $(3\mathrm{/}2{)}^n{n}^n\mathrm{/}(j!(n-j)!)$: numerator factors are at most $3\mathrm{/}2$ and its denominator has absolute value $n^{-n}j!(n-j)!$. Summing these bounds gives $(3n{)}^n\mathrm{/}n!\le (3e{)}^n$, where $\log (n!)={\sum }_{j=1}^n\log j\ge {\int }_1^n\log tdt=n\log n-n+1$ proves $n!\ge (n\mathrm{/}e{)}^n$. Applying this univariate estimate in each coordinate in turn, and taking suprema after each application, shows for every polynomial $p$ of total degree at most $n$ that $\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le R^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c},R=(3e{)}^d,$ since its degree in each separate coordinate is at most $n$. Here and below $\mathrm{\parallel }p{\mathrm{\parallel }}_E={\sup }_{z\in E}\mathrm{\mid }p(z)\mathrm{\mid }$.

Integrating the bounds of step 1.1 over $[-\pi ,\pi ]$, with the near-zero interval contributing at most $2m$ and the other terms bounded by extending their elementary integrals to infinity, gives $\frac{1}{2\pi }{\int }_{-\pi }^{\pi }\mathrm{\mid }{F}_m^{\mathrm{\prime }}(t)\mathrm{\mid }dt\le \frac{2+2{\pi }^2+{\pi }^3}{2\pi }m\le 20m\mathrm{.}$ For $m=1$ this also holds because $F_1=1$. Define $V_N=2F_{2N}-F_N$. Its Fourier coefficients for every $\mathrm{\mid }k\mathrm{\mid }\le N$ equal $1$: for $\mathrm{\mid }k\mathrm{\mid }<N$ they are $2(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}(2N))-(1-\mathrm{\mid }k\mathrm{\mid }\mathrm{/}N)$, and for $\mathrm{\mid }k\mathrm{\mid }=N$ they are $2(1\mathrm{/}2)$. For any trigonometric polynomial $T$ of degree at most $N$, integration of finite sums, using ${\int }_{-\pi }^{\pi }{e}^{ikt}dt=0$ for nonzero integer $k$ and $2\pi$ for $k=0$, therefore gives $T(t)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }T(s)V_N(t-s)ds\mathrm{.}$ Differentiating this finite-sum identity and using periodicity and the integral bound yields $\mathrm{\parallel }{T}^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}\le 100N\mathrm{\parallel }T{\mathrm{\parallel }}_{\mathrm{\infty }}$. Taking $T(t)=r(\cos t)$, a trigonometric polynomial of degree at most $N$ by expansion of powers of cosine, and using $T^{\mathrm{\prime }}(t)=-\sin (t)r^{\mathrm{\prime }}(\cos t)$ proves the inequality announced in step 1.1. All integrals here integrate continuous finite trigonometric sums or the displayed elementary bounds.

Define constants depending only on $d$ by $a=(3\mathrm{/}4{)}^d,\delta =\min \{1\mathrm{/}4,a\mathrm{/}(8R)\},G=600\sqrt{d}\mathrm{/}\sqrt{\delta },\kappa =\min \{\delta \mathrm{/}2,1\mathrm{/}(2G)\},A=2R\mathrm{/}a\mathrm{.}$ Let $Y\subset Q$ be finite and nonempty with Euclidean fill distance $\eta$ and $n\eta \le \kappa$. The zero polynomial satisfies the desired inequality, so fix nonzero $p$ of degree at most $n$ and set $q(u)=p(u){\prod }_{i=1}^d(1-u_i^2{)}^n,S=\mathrm{\parallel }q{\mathrm{\parallel }}_Q,M={\max }_{y\in Y}\mathrm{\mid }p(y)\mathrm{\mid }\mathrm{.}$ The coordinate degrees of $q$ are at most $3n$. On $Q_c$ its product weight is at least $a^n$, so $S\ge a^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}>0$. The last inequality holds because a polynomial vanishing on a box with nonempty interior vanishes identically: fix all but one coordinate in the interior and apply the univariate root bound, then repeat in each coordinate. If some $\mathrm{\mid }{u}_i\mathrm{\mid }\ge 1-\delta$, then $1-u_i^2\le 2\delta$ while all other weight factors are at most $1$, and step 1.2 implies $\mathrm{\mid }q(u)\mathrm{\mid }\le (2\delta {)}^n\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le (2\delta R{)}^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}\le (1\mathrm{/}4{)}^{n}S<S\mathrm{.}$ The maximum of $\mathrm{\mid }q\mathrm{\mid }$ is attained on $Q$ by compactness and the extreme value theorem, so a maximizer $u_{\ast }$ lies in $[-1+\delta ,1-\delta {]}^d$.

Take $y\in Y$ with $\mathrm{\parallel }y-u_{\ast }{\mathrm{\parallel }}_2\le \eta$; such a point exists because the minimum over the finite set is attained and is at most its supremum $\eta$. Since $\eta \le \kappa \le \delta \mathrm{/}2$, the segment from $u_{\ast }$ to $y$ lies where every coordinate has absolute value at most $1-\delta \mathrm{/}2$. Apply step 2.1 to each univariate coordinate slice of $q$, of degree at most $3n$ and norm at most $S$ on $[-1,1]$. At each point of this segment it gives $\mathrm{\mid }{\mathrm{\partial }}_{i}q\mathrm{\mid }\le \frac{300nS}{\sqrt{\delta -{\delta }^2\mathrm{/}4}}\le \frac{600nS}{\sqrt{\delta }},\mathrm{\parallel }\mathrm{\nabla }q{\mathrm{\parallel }}_2\le GnS\mathrm{.}$ Apply the fundamental theorem of calculus to the univariate polynomial $t\mapsto q(u_{\ast }+t(y-u_{\ast }))$: it follows directly here by integrating each power in this finite polynomial. With the Euclidean Cauchy–Schwarz inequality, obtained by expanding ${\sum }_i(v_i-s{w}_i{)}^2\ge 0$ and minimizing the quadratic in $s$, this gives $S\le \mathrm{\mid }q(y)\mathrm{\mid }+Gn\eta S\le M+S\mathrm{/}2.$ Thus $S\le 2M$, and steps 1.2 and 2.2 yield $\mathrm{\parallel }p{\mathrm{\parallel }}_Q\le R^n\mathrm{\parallel }p{\mathrm{\parallel }}_{Q_c}\le (R\mathrm{/}a{)}^{n}S\le 2(R\mathrm{/}a{)}^{n}M\le A^{n}M\mathrm{.}$ This also includes the zero polynomial.

Fix $x\in Q$, enumerate $Y=\{y_1,\dots ,y_m\}$, and let $v(u)\in {\mathbb{R}}^D$ be the vector of all monomials in $u$ of total degree at most $n$, in any fixed order, where $D$ is their finite number. Let $K$ be the convex hull of $\{v(y_j),-v(y_j):1\le j\le m\}$. More explicitly it is the image of the closed bounded simplex of $2m$ nonnegative real coordinates summing to $1$, under the continuous map taking these coordinates to the corresponding weighted sum of these $2m$ vectors. Thus $K$ is nonempty and compact, and is convex because convex combinations of two sets of simplex weights remain simplex weights. Suppose $v(x)\mathrm{\notin }{A}^{n}K$. The continuous squared distance from $v(x)$ attains a minimum at some $z\in A^{n}K$; put $b=v(x)-z\mathrm{\ne }0$. For each $w\in A^{n}K$ the segment $z+t(w-z)$, $0\le t\le 1$, lies in $A^{n}K$. Its squared distance to $v(x)$ equals $\mathrm{\parallel }b{\mathrm{\parallel }}_2^2-2tb\cdot (w-z)+t^2\mathrm{\parallel }w-z{\mathrm{\parallel }}_2^2\mathrm{.}$ Minimality at $t=0$ forces $b\cdot (w-z)\le 0$, since a strictly positive value would make this displayed expression smaller for sufficiently small positive $t$.

Therefore $b\cdot z$ is the maximum of the linear functional $b\cdot w$ on $A^{n}K$. A linear functional on this convex hull has maximum equal to the largest of its values on its finite generators: every convex weighted average is at most that largest value and that value is attained at a generator. Consequently $b\cdot v(x)=b\cdot z+\mathrm{\parallel }b{\mathrm{\parallel }}_2^2>A^n{\max }_{1\le j\le m}\mathrm{\mid }b\cdot v(y_j)\mathrm{\mid }\mathrm{.}$ This contradicts step 3.1 applied to the polynomial $u\mapsto b\cdot v(u)$, because $x\in Q$. Thus $v(x)\in A^{n}K$. Write it as $A^n$ times a convex combination of the vectors $\pm v(y_j)$, with nonnegative weights $t_j^{+},t_j^{-}$ summing to $1$. For ${\lambda }_j=A^n(t_j^{+}-t_j^{-})$ one has $v(x)={\sum }_j{\lambda }_{j}v(y_j),{\sum }_j\mathrm{\mid }{\lambda }_j\mathrm{\mid }\le A^n{\sum }_j(t_j^{+}+t_j^{-})=A^n\mathrm{.}$ Taking the scalar product with the coefficient vector of any polynomial of degree at most $n$ proves simultaneous reproduction. This argument uses finite-dimensional compactness and a single minimum, without an infinite choice principle.

Finally choose orthonormal coordinates along the edges of $\mathrm{\Omega }$, with its center as origin, and multiply these coordinates by $2\mathrm{/}L$. This affine map carries $\mathrm{\Omega }$ to $Q$ and scales Euclidean distances by $2\mathrm{/}L$, so it carries $X$ to a set $Y$ of fill distance $\eta =2h_X\mathrm{/}L$. Composition in either direction preserves total polynomial degree because each coordinate is affine linear. The condition in the Statement is exactly $n\eta \le \kappa$. Transporting the norming inequality from step 3.1 and the coefficients from step 5.1 proves both assertions on $\mathrm{\Omega }$, including rotated cubes. All selections made in the proof are finite or individual existential choices, so no choice axiom is used.

Let $z_c$ be the center of $\mathrm{\Omega }$, let $L>0$ be its side length, and use orthonormal coordinates along its edges, writing $u(z)$ for the coordinates of $z-z_c$. These coordinates preserve distances and give $\mathrm{\parallel }u(z){\mathrm{\parallel }}_2\le B=L\sqrt{d}\mathrm{/}2$ for every $z\in \mathrm{\Omega }$. Put $t=B^2\mathrm{/}{\sigma }^2>0$. For a multi-index $\alpha =({\alpha }_1,\dots ,{\alpha }_d)\in {\mathbb{N}}_0^d$, write $\mathrm{\mid }\alpha \mathrm{\mid }={\sum }_i{\alpha }_i$, $\alpha !={\prod }_i{\alpha }_i!$, and $u^{\alpha }={\prod }_i{u}_i^{{\alpha }_i}$, and define ${\mathrm{\Phi }}_{\alpha }(z)=\exp (-\mathrm{\parallel }u(z){\mathrm{\parallel }}_2^2\mathrm{/}(2{\sigma }^2))\frac{u(z{)}^{\alpha }}{{\sigma }^{\mathrm{\mid }\alpha \mathrm{\mid }}\sqrt{\alpha !}}\mathrm{.}$ Multiplying the convergent exponential power series in the $d$ coordinates yields ${\sum }_{\alpha }{\mathrm{\Phi }}_{\alpha }(z){\mathrm{\Phi }}_{\alpha }(w)=e^{-(\mathrm{\parallel }u(z){\mathrm{\parallel }}_2^2+\mathrm{\parallel }u(w){\mathrm{\parallel }}_2^2)\mathrm{/}(2{\sigma }^2)}{e}^{u(z)\cdot u(w)\mathrm{/}{\sigma }^2}=k_{\sigma }(z,w)\mathrm{.}$ The series is absolutely convergent, since replacing each coordinate product by its absolute value gives the finite value $e^{-(\mathrm{\parallel }u(z){\mathrm{\parallel }}_2^2+\mathrm{\parallel }u(w){\mathrm{\parallel }}_2^2)\mathrm{/}(2{\sigma }^2)}\exp ({\sum }_i\mathrm{\mid }{u}_i(z)u_i(w)\mathrm{\mid }\mathrm{/}{\sigma }^2)$. In particular the vector $\mathrm{\Phi }(z)=({\mathrm{\Phi }}_{\alpha }(z){)}_{\alpha }$ is square summable with squared norm $k_{\sigma }(z,z)=1$.

For any finite set of points $z_1,\dots ,z_q\in \mathrm{\Omega }$ and real coefficients $a_1,\dots ,a_q$, the reproducing property gives ${\parallel {\sum }_{j=1}^q{a}_j{k}_{\sigma }(\cdot ,z_j)\parallel }_{{\mathcal{H}}_{\sigma }}^2={\sum }_{j,l=1}^q{a}_j{a}_l{k}_{\sigma }(z_j,z_l)={\parallel {\sum }_{j=1}^q{a}_j\mathrm{\Phi }(z_j)\parallel }_{{\mathrm{\ell }}^2}^2\mathrm{.}$ The second equality follows from step 1.1 by interchanging a finite sum with an absolutely convergent series. Thus this norm identity concerns finite kernel combinations and requires no description of the whole Gaussian RKHS or extension of its functions to ${\mathbb{R}}^d$. The RKHS used here is available under the stated Countable Choice hypothesis.

Fix $X$ as in the Statement, set $h=h_X$, and for now choose an integer $n\ge 1$ such that $2nh\mathrm{/}L\le \kappa$. Fix any $x\in \mathrm{\Omega }$ and take coefficients ${\lambda }_j$ from [F4]. Define real coefficients $b_j={\lambda }_j\exp \left(\frac{\mathrm{\parallel }u(x_j){\mathrm{\parallel }}_2^2-\mathrm{\parallel }u(x){\mathrm{\parallel }}_2^2}{2{\sigma }^2}\right)\mathrm{.}$ Then ${\sum }_j\mathrm{\mid }{b}_j\mathrm{\mid }\le e^{t\mathrm{/}2}{A}^n$. For every $\mathrm{\mid }\alpha \mathrm{\mid }\le n$, the polynomial $z\mapsto u(z{)}^{\alpha }$ has total degree at most $n$, so reproduction implies ${\sum }_j{b}_j{\mathrm{\Phi }}_{\alpha }(x_j)=\frac{e^{-\mathrm{\parallel }u(x){\mathrm{\parallel }}_2^2\mathrm{/}(2{\sigma }^2)}}{{\sigma }^{\mathrm{\mid }\alpha \mathrm{\mid }}\sqrt{\alpha !}}{\sum }_j{\lambda }_{j}u(x_j{)}^{\alpha }={\mathrm{\Phi }}_{\alpha }(x)\mathrm{.}$ Consequently all coordinates of $\mathrm{\Phi }(x)-{\sum }_j{b}_j\mathrm{\Phi }(x_j)$ with $\mathrm{\mid }\alpha \mathrm{\mid }\le n$ vanish.

Write ${\mathrm{\Phi }}_{>n}(z)$ for the coordinates with $\mathrm{\mid }\alpha \mathrm{\mid }>n$. Expanding $({\sum }_i{u}_i(z{)}^2\mathrm{/}{\sigma }^2{)}^r$ by multiplication shows that its monomial coefficient at multi-index $\alpha$ of size $r$ is $r!\mathrm{/}\alpha !$: it counts the ordered $r$ choices of coordinates with the prescribed multiplicities. Hence $\mathrm{\parallel }{\mathrm{\Phi }}_{>n}(z){\mathrm{\parallel }}_{{\mathrm{\ell }}^2}^2=e^{-\mathrm{\parallel }u(z){\mathrm{\parallel }}_2^2\mathrm{/}{\sigma }^2}{\sum }_{r=n+1}^{\mathrm{\infty }}\frac{(\mathrm{\parallel }u(z){\mathrm{\parallel }}_2^2\mathrm{/}{\sigma }^2{)}^r}{r!}\le {\sum }_{r=n+1}^{\mathrm{\infty }}\frac{t^r}{r!}\mathrm{.}$ If $n+2\ge 2t$, the ratio of any successive terms in the last tail is at most $1\mathrm{/}2$, so summing the geometric majorant gives ${\sum }_{r=n+1}^{\mathrm{\infty }}\frac{t^r}{r!}\le \frac{2t^{n+1}}{(n+1)!}\le 2{\left(\frac{et}{n+1}\right)}^{n+1}\mathrm{.}$ For the final inequality, $\log (q!)={\sum }_{j=1}^q\log j\ge {\int }_1^q\log sds=q\log q-q+1$ for every integer $q\ge 1$, and exponentiation yields $q!\ge (q\mathrm{/}e{)}^q$. Thus the bound holds uniformly for every $z\in \mathrm{\Omega }$.

By [F3], the infimum defining $P_X(x)$ is attained by orthogonal projection onto the finite section span. The vector ${\sum }_j{b}_j{k}_{\sigma }(\cdot ,x_j)$ is in that span, so its error norm is an upper bound for $P_X(x)$. Steps 2.1 and 2.2 show that its error norm is $\mathrm{\parallel }{\mathrm{\Phi }}_{>n}(x)-{\sum }_j{b}_j{\mathrm{\Phi }}_{>n}(x_j){\mathrm{\parallel }}_{{\mathrm{\ell }}^2}$. Apply the triangle inequality to these finitely many square-summable vectors and use steps 2.2 and 2.3 to obtain $P_X(x)\le \sqrt{2}(1+e^{t\mathrm{/}2}{A}^n){\left(\frac{et}{n+1}\right)}^{(n+1)\mathrm{/}2}\mathrm{.}$ The ${\mathrm{\ell }}^2$ triangle inequality here can be obtained from the finite Euclidean triangle inequality on every initial finite collection of multi-indices and then passing to the supremum of their squared partial sums; thus no additional choice principle is involved. The bound is independent of $x$, and holds whenever $n\ge 1$, $2nh\mathrm{/}L\le \kappa$, and $n+2\ge 2t$.

Put $D=\kappa L\mathrm{/}2>0$ and $n=\lfloor D\mathrm{/}h\rfloor$. For all sufficiently small $h>0$ this integer satisfies $n\ge 1$, $n+2\ge 2t$, and $D\mathrm{/}(2h)\le n\le D\mathrm{/}h$; the lower bound follows from $\lfloor s\rfloor \ge s\mathrm{/}2$ for $s\ge 2$. Also $2nh\mathrm{/}L\le \kappa$. Since $1+e^{t\mathrm{/}2}{A}^n\le 2e^{t\mathrm{/}2}{A}^n$, the logarithm of the positive bound in step 3.1 is at most $-\frac{1}{2}(n+1)\log (n+1)+K(n+1),$ where one may take $K=1+\frac{3}{2}\log 2+t\mathrm{/}2+\log A+\frac{1}{2}\mathrm{\mid }\log (et)\mathrm{\mid }>0$. Decrease $h_0>0$ until for all $0<h\le h_0$ the preceding integer conditions hold, $h<1$, $\log (n+1)\ge 4K$, and $\log (n+1)\ge \frac{1}{2}\mathrm{\mid }\log h\mathrm{\mid }$. Such an $h_0$ exists because $n\ge D\mathrm{/}(2h)$ implies $\log (n+1)\ge \mathrm{\mid }\log h\mathrm{\mid }+\log (D\mathrm{/}2)$, which tends to infinity and eventually exceeds $\mathrm{\mid }\log h\mathrm{\mid }\mathrm{/}2$.

For $0<h\le h_0$ the exponent in step 4.1 is at most $-(n+1)\log (n+1)\mathrm{/}4$, and hence at most $-D\mathrm{\mid }\log h\mathrm{\mid }\mathrm{/}(16h)$, by the two lower bounds for $n$ and $\log (n+1)$. Therefore step 3.1 gives, uniformly in $x\in \mathrm{\Omega }$, $P_X(x)\le \exp (-\frac{D}{16}\frac{\mathrm{\mid }\log h\mathrm{\mid }}{h})\mathrm{.}$ Taking the supremum over $x$ proves the Statement with $c=D\mathrm{/}16$ and $C=1$, and also with any larger positive $C$. All constants depend only on $d$, $\mathrm{\Omega }$, and $\sigma$. Countable Choice was used only through the canonical RKHS supplier in step 2.1; the reproduction and feature estimates add no further choice assumption.

By [A1], [F1], and [F2], the Gaussian kernel has the real RKHS used in the Statement, with evaluation property [F3]. Let $X_n=\{x_1,\dots ,x_n\}$ and $V_n=\mathrm{span}\{k_{\sigma }(\cdot ,x_i):1\le i\le n\}$. For any interpolant $h$, put $g=h-h^{\ast }$. Then $g(x_i)=0$, so [F3] gives $⟨g,k_{\sigma }(\cdot ,x_i)⟩=0$ for each $i$ and hence $g\perp V_n$. By [F6] the projection ${\mathrm{\Pi }}_{V_n}$ exists; therefore $g(x)=⟨g,k_{\sigma }(\cdot ,x)⟩=⟨g,k_{\sigma }(\cdot ,x)-{\mathrm{\Pi }}_{V_n}{k}_{\sigma }(\cdot ,x)⟩\mathrm{.}$ The inner-product Cauchy--Schwarz inequality follows by expanding $\mathrm{\parallel }u-tv{\mathrm{\parallel }}^2\ge 0$ and minimizing over real $t$ (with the zero-vector case immediate). Thus $\mathrm{\mid }g(x)\mathrm{\mid }\le \mathrm{\parallel }g{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}{P}_{X_n}(x)$.

The triangle inequality gives $\mathrm{\parallel }g{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}\le \mathrm{\parallel }h{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}+\mathrm{\parallel }{h}^{\ast }{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}$. Taking the supremum in step 1.1 yields ${\sup }_{x\in \mathrm{\Omega }}\mathrm{\mid }h(x)-h^{\ast }(x)\mathrm{\mid }\le (\mathrm{\parallel }h{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}+\mathrm{\parallel }{h}^{\ast }{\mathrm{\parallel }}_{{\mathcal{H}}_{\sigma }}){\sup }_{x\in \mathrm{\Omega }}{P}_{X_n}(x)\mathrm{.}$

Write $\mathrm{\Omega }=v+Q[0,L{]}^d$ using its side length $L>0$ and an orthogonal matrix $Q$, and put $u_i=Q^{\mathsf{T}}(x_i-v)$. The affine map $F(u)=v+Qu$ bijects the product cube $C_0=[0,L{]}^d$ onto $\mathrm{\Omega }$. For every Borel $E\subseteq C_0$, [F7] gives $\mathbb{P}(u_i\in E)={\lambda }_d(F(E))\mathrm{/}{\lambda }_d(\mathrm{\Omega })=\mathrm{\mid }\det Q\mathrm{\mid }{\lambda }_d(E)\mathrm{/}(\mathrm{\mid }\det Q\mathrm{\mid }{\lambda }_d(C_0))={\lambda }_d(E)\mathrm{/}{\lambda }_d(C_0)$. The transformed samples remain independent: for finitely many Borel sets $E_i\subseteq C_0$, their joint event is ${\bigcap }_i\{x_i\in F(E_i)\}$, and independence of the $x_i$ makes its probability the product of the individual probabilities. These events are measurable since $F$ is a homeomorphism. Also $\mathrm{\parallel }F(u)-F(w){\mathrm{\parallel }}_2=\mathrm{\parallel }u-w{\mathrm{\parallel }}_2$, so the fill distance of $\{u_1,\dots ,u_n\}$ in $C_0$ equals $h_{X_n}$ in $\mathrm{\Omega }$. By [F5], on an event of probability at least $1-1\mathrm{/}n$, the fill distance $h_{X_n}$ is at most ${\bar{h}}_n=C_{d}L(\log n\mathrm{/}n{)}^{1\mathrm{/}d}$. For all sufficiently large $n$, ${\bar{h}}_n<\min (h_0,e^{-1})$; the function $u\mapsto \mathrm{\mid }\log u\mathrm{\mid }\mathrm{/}u$ is decreasing on $(0,e^{-1}]$, so [F4] applies and gives ${\sup }_x{P}_{X_n}(x)\le C\exp \text{\hspace{0.17em}⁣}(-c\frac{\mathrm{\mid }\log h_{X_n}\mathrm{\mid }}{h_{X_n}})\le C\exp \text{\hspace{0.17em}⁣}(-\frac{c}{{\bar{h}}_n})=C\exp \text{\hspace{0.17em}⁣}(-\frac{c}{C_{d}L}{\left(\frac{n}{\log n}\right)}^{1\mathrm{/}d})\mathrm{.}$ Using this bound in step 2.1 proves the displayed estimate with $A=C$ and $B=c\mathrm{/}(C_{d}L)$, uniformly for every interpolant on that event.