Generalization error of minimum weighted norm and kernel interpolation

Introduction

Deep neural networks contain significantly more parameters than data points and run the risk of over-fitting, yet they still perform well on new examples . This behavior appears to contradict classical learning wisdom, which predicts that over-parameterized methods typically result in poor generalization and advocates for models whose complexities are less than the number of training points.

The double descent phenomenon was proposed in as a resolution to this apparent paradox. Experimental evidence shows that for certain interpolators and datasets, for fixed $n$ samples, the generalization error as a function of the number of parameters $p$ appears to behave differently in two regimes. In the under and exactly parameterized regime $p\leq n$, the error curve follows a classical “U” shaped curve with maximum error at $p\approx n$. In the over-parameterized regime $p>n$, the error decreases and its infimum is in the limit $p\to\infty$. The terminology “double descent” is attributed to the generalization error decreasing again in the over-parameterized regime after the first descent in the under-parameterized part of the curve.

While the “U” behavior of the curve is rationalized by the bias-variance trade-off , the over-parameterized regime is less (well) understood, yet highly relevant for modern learning algorithms. For instance, as the number of parameters increases, so do the Rademacher complexities and covering numbers of the corresponding function classes. Thus, ubiquitous statistical learning techniques that rely on controlling these quantities, such as those found in , predict that the generalization error should increase with the number of parameters, not decrease.

There has been significant recent interest in theoretically understanding the generalization error of simple over-parameterized methods and models. Given the prevalent use of kernel and optimization algorithms in data science and machine learning, and the importance of weighted norms, we study the error of interpolants that have minimum weighted norm. Our approach this problem is from a deterministic and approximation theory viewpoint, as opposed a statistical or random matrix one.

2 Contributions

Let us briefly describe our framework. Consider a weight $\omega$ and associated norm $\|\cdot\|_{\Phi,\omega}$ on the coefficient space of a sequence of functions $\Phi$. Given a collection of $n$ data points, for each sufficiently large $p\leq\infty$ (including $p=\infty$), let $f_{p}$ be the interpolant chosen to have minimum $\|\cdot\|_{\Phi,\omega}$ norm among all interpolants spanned by the first $p$ functions of $\Phi$. A classical example is trigonometric interpolation by polynomials of degree $p$ and weights generating a Sobolev norm. To see if $f_{p}$ approximates a given $f$, we study the $L^{2}_{\mu}$ error $E_{2}(f,f_{p}):=\|f-f_{p}\|_{L^{2}_{\mu}(\Omega)}$ of this minimum weighted norm interpolant.

Under natural and general conditions on $\Phi$, weight $\omega$, and sampling set, we show that $f_{p}$ converges to $f_{\infty}$ in norm. The limiting function $f_{\infty}$ is the interpolant belonging to a reproducing kernel Hilbert space uniquely specified by the basis and weight. This rigorously establishes an implicit bias of weighted norm minimization: even though the function space consisting of all possible interpolants grows in $p$, minimum weighted norm interpolation always selects particular interpolants that converge to a limiting one.

As a corollary, we show that $E_{2}(f,f_{p})$ converges to $E_{2}(f,f_{\infty})$ as $p$ increases to infinity. When the interpolated data are samples of $f$, the limiting value $E_{2}(f,f_{\infty})$ is small if the sampling set is sufficiently dense and if $f$ is parsimonious with the weighted norm, which explains why over-parameterization can be helpful for certain target functions $f$. On the other hand, if $E_{2}(f,f_{\infty})$ is large, then using more parameters than necessary could potentially increase the error.

We devote particular attention to two canonical examples. The trigonometric basis with appropriate weights generate isotropic and mixed spaces of smooth functions on the torus. We derive several new upper bounds for $E_{2}(f,f_{\infty})$, which is validated by numerical experiments. The spherical harmonics with appropriate weights generate positive-definite kernel on the unit sphere. We make some new observations about the interpolation and generalization properties of neural tangent kernels.

3 Related work

There are several recent works that study the generalization of over-parameterized learning methods. For linear target functions, $f(x)=x\cdot\theta$ for some $\theta$, estimators based on minimum norm interpolation with $p<\infty$ parameters were analyzed in . These results require statistical assumptions on the samples, co-variance matrices, and/or relationship between $n$ and $p$. Special kinds of non-linear target functions were also considered in . Estimates the for ideal generalization error for several linear and non-linear models were given in , but it did not study the performance of any particular algorithm.

The use of kernel interpolation to approximate large function classes has been extensively studied from an approximation theory viewpoint, see for an overview. Since strictly positive-definite kernels can interpolate an arbitrary number of data points, they correspond to the $p=\infty$ case. It was recently shown that appropriately scaled random kernels in high dimensions and appropriately scaled singular ones can both interpolate and approximate.

A recent preprint also explores the generalization capability of weighted norm interpolation and reaches a similar conclusion that regularity of the target function allows for smallness of the generalization error in the over-parameterized regime. While that reference obtains explicit expressions for the generalization error corresponding to Sobolev weights and one-dimensional trigonometric basis with $n$ equally spaced sampling points on $$, this paper provides upper bounds corresponding to more general weighted norms beyond Sobolev and allows for irregularly spaced sampling sets.

4 Organization

The remainder of this paper is organized as follows. In section 2, we state the main assumptions of this paper and introduces minimum weighted norm interpolation. In section 3, we provide our most general results. There we discuss convergence of the over-parameterized interpolants and develop a connection to reproducing kernel spaces. Finally, in section 4 and section 5, we deal with trigonometric and spherical harmonic interpolation, respectively. All proofs are contained in the appendices.

Notation and assumptions

2 Main assumptions

Given a sequence of real-valued, continuous, and $L^{2}_{\mu}(\Omega)$ orthonormal sequence $\Phi:=\{\varphi_{k}\}_{k=1}^{\infty}$, and a positive sequence $\omega:=\{\omega_{k}\}_{k=1}^{\infty}$ that diverges to infinity, we say $\Phi$ and $\omega$ are compatible if there is a bounded and continuous function $K_{\Phi,\omega}\in L^{2}_{\mu\times\mu}(\Omega\times\Omega)$ such that

where the series is assumed to converge absolutely and uniformly.

Let $\widehat{f}$ denote the coefficients of $f\in L^{2}_{\mu}(\Omega)$ in the $\Phi$ sequence, where $\widehat{f}_{k}:=\int_{\Omega}f\varphi_{k}\ d\mu$. We formally define the weighted inner product $\langle f,g\rangle_{\Phi,\omega}:=\sum_{k=1}^{\infty}\omega_{k}\widehat{f}_{k}\widehat{g}_{k}$ and let $\|f\|_{\Phi,\omega}^{2}:=\langle f,f\rangle_{\Phi,\omega}$. Let $H_{\Phi,\omega}$ be the collection of all $f$ in the $L^{2}_{\mu}(\Omega)$ closed linear span of $\Phi$ for which $\|f\|_{\Phi,\omega}<\infty$.

For each integer $p\geq p_{X}$, including $p=\infty$, given prescribed data $(X,y)$, the minimum weighted norm interpolant is

The solution to this optimization problem is unique and can be computed numerically by inverting a system of linear equations. Each weight $\omega$ generates a different norm, so $\omega$ parameterizes a family of algorithms.

For a given function $f$ defined on $\Omega$, it is possible to ask if the interpolant $f_{p}$ approximates $f$. For each $1\leq q\leq\infty$, we define the $L^{q}_{\mu}(\Omega)$ error,

We primarily view the error as a function of $p$ when $y,X,\Phi,\omega,f$ are fixed. It is important to mention that $f_{p}$ only depends on $p,y,X,\Phi,\omega$, and that in this definition, $f$ is an arbitrary function. There are two important examples. In the standard statistical learning paradigm , $f$ represents the regression function, $y$ are noisy samples of $f$, and $E_{q}(f,f_{p})$ represents the $L^{q}$ generalization error. A more restrictive setting is the noiseless case where $f$ belongs to some function class and $y_{k}=f(x_{k})$ for each $k$. Our results in section 3 apply to both, while those in section 4 and section 5 consider the latter.

By definition, $f_{p}$ belongs to a subspace of dimension $p$ and $p_{X}$ is the minimum number of basis functions required to interpolate arbitrary data on $X$. We interpret $p/p_{X}$ as the over-parameterization factor. If $n$ is the cardinality of $X$, then $p_{X}\geq n$, but in general $p_{X}\not=n$. The quantity $E_{q}(f,f_{p_{X}})$ is the error of the exactly parameterized minimum weighted norm solution.

Minimum norm and kernel interpolation

The main results in this section are proved in appendix A and we provide necessarily preparatory lemmas in section A.1.

At the core of our main findings is convergence of $f_{p}$ to $f_{\infty}$ and hence automatically $E_{q}(f,f_{p})$ to $E_{q}(f,f_{\infty})$ for any $f$. This will be crucial in explaining and understanding when over-parameterization may be beneficial for minimum norm interpolation. The following theorem is proved in section A.3.

Assume $\Phi$ and $\omega$ are compatible, and $X$ is a sampling set for $\Phi$. Given any data $y$ defined on $X$, for each $p_{X}\leq p\leq\infty$, let $f_{p}$ denote the minimum weighted norm interpolant of $(X,y)$. Then $f_{p}$ converges to $f_{\infty}$ in $L^{q}_{\mu}(\Omega)$ for each $2\leq q\leq\infty$. If additionally $\mu(\Omega)<\infty$, then convergence also holds for $1\leq q<2$.

theorem 3.1 proves an important property of minimum weighted norm interpolation. As the number of parameters $p$ increases, so does the space of functions that interpolate the given data $(X,y)$. Yet, minimum weighted norm interpolation always selects particular interpolants that converge to a limiting one $f_{\infty}$. This rigorously establishes an implicit bias of weighted norm minimization. Notice that this result holds for any data $y$, and importantly, does not require $y$ to be generated by function(s) satisfying certain properties. An important consequence of the theorem is convergence of the error between $f_{p}$ and arbitrary $f$.

Assume $\Phi$ and $\omega$ are compatible, and $X$ is sampling for $\Phi$. Given any data $y$ defined on $X$, for each $p_{X}\leq p\leq\infty$, let $f_{p}$ denote minimum weighted norm interpolant of $(X,y)$. For any $2\leq q\leq\infty$ and function $f\in L^{q}_{\mu}(\Omega)$, we have $\lim_{p\to\infty}E_{q}(f,f_{p})=E_{q}(f,f_{\infty})$. If additionally $\mu(\Omega)<\infty$, then convergence also holds for $1\leq q<2$.

then increasing the number of parameters eventually leads to a decrease in the error. One the other hand, it also shows that over-parameterization might make matters worse if $E_{q}(f,f_{\infty})$ is large.

Notice that corollary 3.2 holds for arbitrary $f$, and in particular, does not require any relationship between $f$ and $y$. This might seem counter-intuitive, but it is important to remember that we have not made any claims yet about the limiting error $E_{q}(f,f_{\infty})$ which we call the plateau. In section 4 and section 5, we will consider the case where $y$ consists of noiseless samples of $f$ belonging to an appropriate function class.

2 Relationship with kernel spaces

We say $K$ is strictly positive-definite if the above statement holds with a strict inequality instead. For any positive-definite $K$, the closure of $\text{span}\{K(x,\cdot)\colon x\in U\}$ under the inner product

defines a Hilbert space of functions such that for any $f\in H_{K}(U)$ and $x\in U$,

It is standard to call $H_{K}(U)$ a reproducing kernel Hilbert space (RKHS) and it can be shown that it is a space of continuous functions. We refer the reader to for further details.

From an interpolation perspective, strictly positive-definite kernels are advantageous and can be used to interpolate arbitrary data. In our setting where $\Omega=U$, the matrix ${\bf K}$ containing samples of $K$ on any $X\times X$ is invertible and the kernel interpolant

belongs to $H_{K}(\Omega)$ and $I_{K}(x_{j})=y_{j}$ for each $j$. Note that if $K$ is not strictly positive-definite, then ${\bf K}$ is not necessarily invertible and interpolation is not always feasible. The following proposition connects our main assumptions with an appropriate RKHS, and is proved in section A.2.

Suppose $\Phi$ and $\omega$ are compatible, and that any finite $X\subseteq\Omega$ is a sampling set for $\Phi$. Then $K:=K_{\Phi,\omega}$ is strictly positive-definite on $\Omega$, and is the unique reproducing kernel for a RKHS such that $\|\cdot\|_{H_{K}(\Omega)}=\|\cdot\|_{\Phi,\omega}$. For any data $y$ defined on $X$, the $p=\infty$ minimum norm interpolant $f_{\infty}$ of $(X,y)$ is precisely the $H_{K}(\Omega)$ reproducing kernel interpolant of $(X,y)$.

We emphasize that not every weighted norm is related to reproducing kernel norms. For instance, this occurs if the uniform convergence condition in the admissibility criteria is violated. An extreme case is when $\omega_{k}=1$ for each $k$ and $\Phi$ is the trigonometric basis for the one-dimensional torus, in which case, the series attempting to define $K_{\Phi,\omega}$ does not even converge pointwise.

3 The plateau and double descent

To investigate conditions for which inequality (3.1) holds, we use proposition 3.3, which shows that $f_{\infty}$ can be interpreted as the $K_{\Phi,\omega}$ kernel interpolant of the prescribed data. Upper bounds for such interpolants have been extensively studied, from both approximation theory and statistical viewpoints, which we briefly describe below.

This is just a representative result, since more refined estimates can be given by exploiting additional properties of the kernel, see . We will consider typical examples later on.

Statistical methods require that $\mu$ is a probability measure and all $n$ sampling points of $X$ are drawn i.i.d. from $\mu$. By controlling the Rademacher complexity of reproducing kernel Hilbert spaces, a representative result from and also Theorem 3 in , shows that for probability exceeding $1-\delta$ over the random draw of $X$, for each $f\in H_{K}(\Omega)$, if $f_{\infty}$ denotes the kernel interpolant of $(X,f|_{X})$,

Both inequalities (3.3) and (3.4) show that, for sufficiently dense sampling sets, both $h_{X}^{k}$ and $1/n$ are small, and so is the plateau. We have chosen to present the material in this subsection rather informally for several reasons. First, $E_{q}(f,f_{\infty})$ greatly depends on $f,\Phi,\omega,X$, so it is impossible to cover every case that may be of interest. Second, the convergence results in theorem 3.1 and corollary 3.2 are deterministic, so they hold for general situations and we have presented the main ingredients on how to combine it with existing bounds for $E_{q}(f,f_{\infty})$. Third, we will consider in detail two types of examples that are particularly relevant to machine learning.

4 Kernel spaces have near optimal interpolants

In the previous subsections, we analyzed the generalization properties of minimum weighted norm interpolation. One may be interested in other algorithms, so for this reasons, we focus on an existence question: given samples of a target function, does there exist an interpolant that is also a near optimal approximant?

There are negative and positive answers to this question. For instance, Runge’s phenomenon is a classical example such that if the sampling set consists of uniformly spaced points on an interval, then the extra interpolation constraints may impede optimal approximation by algebraic polynomials.

The following theorem provides a positive answer to the previous question under the assumption that $f$ belongs to the RKHS associated with $K_{\Phi,\omega}$, and the interpolants are chosen from the span of $\Phi_{p}:=\{\varphi_{k}\}_{k=1}^{p}$. To obtain an idea of the fundamental limits, we observe the simple lower bound,

The below theorem establishes the reverse inequality up to a small additive constant and it is proved in section A.4.

Assume $\Phi$ and $\omega$ are compatible, and $X$ is a sampling set for $\Phi$. Given any $\varepsilon>0$ and $f\in H_{K_{\Phi,\omega}}(\Omega)$, there exist $p<\infty$ and $g\in\text{span}(\Phi_{p})$ such that $g$ interpolates $f$ on $X$ and

This theorem shows that both interpolation and near optimal approximation of functions in reproducing kernel Hilbert spaces can be simultaneously achieved. However, it is purely existential as the extremal function(s) cannot be computed directly from the proof.

Example: Fourier series

The main results of this section are proved in appendix B and section B.1 provides overview of the organization of the proofs.

Our use of complex-valued functions in this section is purely for convenience of notation. Since we will only consider interpolation and approximation of real-valued functions, the trigonometric basis $\Phi$ can be equivalently rewritten in terms of sines and cosines, while the kernel $K_{\Phi,\omega}$ can be expressed as a summation of cosines.

The proof is rather technical and requires several preparatory lemmas, which can be found in section B.4.

This theorem tells us that the error is largely controlled by $h_{X}$ to the $\min(r,s)-d/2$ power. This agrees with our intuition as more sampling points and highly regular $f$ should lead to small error. The ratio $h_{X}/q_{X}\geq 1$ is large if $X$ is irregular and equals one for uniformly spaced sampling points. Usually in practice, we interpret $h_{X}/q_{X}$ as a universal constant.

While the above theorem is similar in flavor to the scattered data approximation error bounds in , its interpretation is different. The scattered data approximation point of view examines the limit $h_{X}\to 0$, whereby the theorem suggests that it is optimal to pick $s=r$ in order to maximize the decay of $h_{X}$. In our case, $h_{X}$ is finite and fixed, so the answer is more complicated. The error bound in theorem 4.2 contains $\|f\|_{W^{s}}$ which grows in $s$, an implicit constant $C>0$ which presumably also grows in $s$, and $h_{X}^{s-d/2}$ which decreases in $s$. Thus, it is not clear whether $s=r$ is best.

As seen in theorem 4.2, interpolation of smooth functions in standard smoothness spaces suffer from the curse of dimensionality. Indeed, if $X$ consists of $n$ approximately uniformly spaced points, then $h_{X}$ is on the order of $n^{-1/d}$. In high dimensions, this leads to a poor approximation rate. As shown in the supplementary material in section D.1, the curse of dimensionality in the approximation rate can be avoided by assuming $f$ belongs to a mixed Sobolev space.

2 Numerical illustration

The primary goal of this section is to validate and illustrate our theory for a concrete example. We consider the classical Runge function,

To avoid sampling sets with special structures, suppose $X=\{x_{k}\}_{k=1}^{n}$ is a set of $n$ points chosen i.i.d. from the uniform measure on $[-1/2,1/2]$. For each realization of $X$ and real parameter $s\geq 0$, we let $f_{p}$ be the trigonometric polynomial of degree at most $p$ chosen according to the following procedure:

Both algorithms are naturally related to each other because the least squares solution uses the pseudo-inverse instead of an inverse to perform the interpolation, see supplementary material in section D.2.

The left plot in fig. 1 shows the error for several choices of smoothness parameters $s$, as a function of $p$. Here, $n=35$ random samples are drawn and the results are averaged over 100 realizations of the sampling set. In the under and exactly parameterized case $p\leq n$, the error follows a classical “U” shaped curve with minimum attained for some $p<n$. The peak occurs at $p\approx n$ and it has been suggested that this is due to the poor condition number of the interpolation matrix . In the over parameterized regime $p>n$, the error behaves differently depending on the choice of weight which is specified by the parameter $s$. We see in this example that the over parameterized minimum norm interpolants for $s=3,4$ perform better than the optimally chosen under parameterized interpolant.

Example: spherical harmonics

We have the following approximation rate for kernel interpolation on the sphere.

2 Neural tangent kernels

An explicit formula for the NTK corresponding to two layer neural networks with ReLU activation was derived in . For our purposes, we forego its formula and instead work with its Mercer decomposition, which was derived in . There, it was shown that for some $C_{d}>0$ depending only on $d$, the NTK denoted $K_{\tan}(x,y)$ has the absolutely and uniformly convergent series expansion

We end this subsection with a theorem regarding the approximation quality of the NTK interpolant of a function. The theorem is proved in section C.3.

Appendix A Proofs for section 3

When $\Phi$ and $\omega$ are fixed, to simplify the presentation, let $K:=K_{\Phi,\omega}$ and $K_{p}(x,y):=\sum_{k=1}^{p}\omega_{k}^{-1}\varphi_{k}(x)\varphi_{k}(y)$ be its truncation. Fix any finite $X=\{x_{j}\}_{j=1}^{n}\subseteq\Omega$ and $p\geq 1$, let ${\bf K}_{p}$ and ${\bf K}$ be square symmetric matrices containing the values of $K_{p}$ and $K$ evaluated on $X\times X$, respectively. Let ${\bf A}_{p}$ denote the $p\times n$ matrix where $({\bf A}_{p})_{j,k}=\varphi_{j}(x_{k})$ and ${\bf W}$ denote the $n\times n$ diagonal matrix ${\bf W}_{j,j}=\omega_{j}^{-1}$. A direct calculation shows that ${\bf K}_{p}={\bf A}_{p}^{t}{\bf W}{\bf A}_{p}$. We also define the quantities

Note that $\alpha_{p}$ converges to zero when $\Phi$ and $\omega$ are compatible.

Assume $\Phi$ and $\omega$ are compatible and $X$ is a sampling set for $\Phi$. For each $p\geq p_{X}$, ${\bf A}_{p}$ is injective and ${\bf K}_{p}$ is invertible.

The following lemma provides us with an explicit formula for $f_{p}$ in terms of ${\bf K}_{p}$. We omit its proof because it is a direct calculation using the explicit formula for the minimum norm solution subject to linear constraints.

Assume $\Phi$ and $\omega$ are compatible, and $X$ is a sampling set for $\Phi$. Given any data $(X,y)$, for each $p_{X}\leq p\leq\infty$, the minimum norm interpolant $f_{p}$ of $(X,y)$ has an explicit formula, f_{p}(x)=\sum_{k=1}^{n}K_{p}(x,x_{k})\big{(}{\bf K}_{p}^{-1}\,y\big{)}_{k}.

A.2 Proof of proposition 3.3

The last inequality follows injectivity of ${\bf A}_{p}$, which is shown in Lemma A.1. This verifies that $K$ is strictly positive-definite on $\Omega$. Since $\Phi$ and $\omega$ are compatible, notice that for each $x\in\Omega$, by orthogonality of $\Phi$, we have

By Proposition 1 in , since we have shown that $K(x,\cdot)\in L^{2}_{\mu}(\Omega)$ for each $x\in\Omega$ and $K\in L^{2}_{\mu\times\mu}(\Omega\times\Omega)$ by assumption, the integral kernel operator, $T_{K}f(x):=\int_{\Omega}K(x,y)f(y)\ dy,$ is positive and compact on $L^{2}_{\mu}(\Omega)$. By the spectral theorem, $T_{K}$ admits a countable orthonormal basis of eigenfunctions for $L^{2}_{\mu}(\Omega)$. A direct calculation shows that all nonzero eigenvalues are precisely $\omega^{-1}$ with corresponding eigenfunctions $\Phi$. It follows from standard RKHS theory that $\|f\|_{H_{K}(\Omega)}=\|f\|_{\Phi,\omega}$ for all $f\in H_{K}(\Omega)$.

The kernel interpolant defined in (3.2) has the smallest RKHS norm among all interpolants of $(X,y)$. See Theorem 13.2 in , and it can be directly proved by modifying the argument in Lemma A.2. Since $\|\cdot\|_{H_{K}(\Omega)}=\|\cdot\|_{\Phi,\omega}$, this implies $f_{\infty}$ is also the kernel interpolant. ∎

A.3 Proof of theorem 3.1

We denote the sampling set by $X=\{x_{k}\}_{k=1}^{n}$ and let $K:=K_{\Phi,\omega}$. From Lemma A.2 and proposition 3.3, we have explicit formulas for $f_{p}$ and $f_{\infty}$,

From here, we use triangle and Cauchy-Schwarz inequalities to obtain,

We first focus on the terms with $L^{q}_{\mu}(\Omega)$ norms. We start with the $L^{2}_{\mu}(\Omega)$ estimates involving $K$. By orthogonality of $\Phi$ and definition of $\alpha_{p}$, for each $x\in\Omega$,

The $L^{\infty}(\Omega)$ estimates are more straightforward. For each $x\in\Omega$, we use Cauchy-Schwarz and the definition of $\alpha_{p}$ to see that

By log-convexity of the $L^{q}_{\mu}(\Omega)$ norm and the above estimates, for each $2\leq q\leq\infty$ and $x\in\Omega$,

It remains to upper bound all terms involving the matrices ${\bf K}$ and ${\bf K}_{p}$. Observe that

where $\|\cdot\|_{F}$ is the Frobenius norm. Combining inequalities (A.1), (A.2), and (A.3) shows that for each $p\geq p_{X}$ and $2\leq q\leq\infty$, we have

To see why this inequality implies that $f_{p}$ converges to $f_{\infty}$ in $L^{q}_{\mu}(\Omega)$, notice that $\alpha_{p}$ converges to zero, $\|{\bf K}_{p}^{-1}\|_{2}$ converges to $\|{\bf K}^{-1}\|_{2}$ due to Weyl’s inequality and our above upper bound on $\|{\bf K}-{\bf K}_{p}\|_{2}$,

and all the other terms are independent of $p$. This proves the theorem for $2\leq q\leq\infty$.

Under the additional assumption that $\mu(\Omega)<\infty$, the same conclusion holds for the range $1\leq q<2$. To see why, the key observation is that for any $x,y\in\Omega$, by Cauchy-Schwarz,

Using these inequalities and that $\mu(\Omega)<\infty$, for each $x\in\Omega$,

The rest follows by repeating the same argument. ∎

A.4 Proof of theorem 3.4

Our desired function is $g:=h+g_{p}$. Indeed, by construction, $g$ interpolates $f$ on $X$, is a linear combination of $K_{p}(\cdot,x_{k})$ which implies $g\in\text{span}(\Phi_{p})$, and

It remains to show that $\|g_{p}\|_{L^{2}_{\mu}(\Omega)}$ tends to zero as $p$ goes to infinity. By Cauchy-Schwarz,

To bound the $\|u\|_{\infty}$ term on the right hand side, we use the definition of $L^{2}_{\mu}$ projection and Cauchy-Schwarz to obtain,

We claim the right hand side tends to zero as $p\to\infty$. Indeed, we have convergence of $\lambda_{\min}({\bf K}_{p})$ to $\lambda_{\min}({\bf K})$ (as shown in the proof of theorem 3.1) and $\|K_{p}(\cdot,x_{k})\|_{L^{2}_{\mu}}$ to $\|K(\cdot,x_{k})\|_{L^{2}_{\mu}}$ in view of the Lebesgue dominated convergence theorem. Recall that $\alpha_{p}$ converges to zero and so does $\sum_{k>p}|\widehat{f}_{k}|^{2}\omega_{k},$ since $f\in H_{K}(\Omega)$ by assumption. Hence, for all $\varepsilon>0$, there exists $p$ sufficiently large such that $\|g_{p}\|_{L^{2}_{\mu}(\Omega)}\leq\varepsilon$. ∎

Appendix B Proofs for section 4

The proof of Theorem 4.2 is rather technical and builds upon core ideas from the kernel interpolation literature. There are two distinctive steps carried out separately in section B.2 and B.3.

B.2 Lemmas for the first step

From Theorems 11.4 and 11.9 in , there exist $C>0$, $c>0$, and $h>0$ such that if $h_{X}\leq h$, then for any algebraic polynomial $Q$ restricted to the unit cube,

where $B(0,ch_{X})$ is the ball of radius $ch_{X}$ centered at the origin. Let $Q$ be the $s$-th degree Taylor polynomial of $K$ expanded around zero. Using the integral form for the remainder and performing some algebraic manipulations, we obtain

Since $\int_{0}^{1}s(1-t)^{s-1}\ dt=1$, by the Hölder continuity of $K$, we obtain

We specialize to $x\in B(0,ch_{X})$ to complete the proof. ∎

By using this lemma, we obtain an immediate consequence for isotropic Sobolev kernels.

By Theorem 6.3.6 in , this implies $\partial^{\beta}K$ is Hölder continuous of order $\alpha$. ∎

B.3 Lemmas for the second step

Approximation by single variable trigonometric polynomials is classical and the multidimensional case is similar. Define the one-variable trigonometric function

Theorem 4.3 in is a multi-variable extension of the classical Jackson’s inequality, and the following lemma is a special case of the referenced result.

Employing the previous lemmas enables us to prove that there exists a trigonometric interpolant that is also a near optimal approximation.

B.4 Proof of theorem 4.2

This proves the first inequality of the theorem.

To upper bound the fist term on the right hand side of inequality (B.2), we use Lemmas B.5 and B.4 to obtain

Thus, combining inequalities (B.2) – (B.6), using that $m\geq C_{d}/q_{X}\geq 1$, and performing some algebraic manipulations, we arrive at

Appendix C Proofs in section 5

C.2 Proof of proposition 5.3

Finally, the desired interpolant is $f+g$. This shows that for arbitrary $X$ with at most $k\leq d$ symmetric points and any $u$ defined on $X$, there exists an interpolant the span of $\Phi_{\tan}$ that interpolates $(X,u)$. ∎

C.3 Proof of theorem 5.4

The more interesting case is $(d-1)/2<2r<d/2$. Its proof is a variation of the results in , so we only give a sketch of the main steps and the interested reader should refer to the aforementioned paper for full details. All subsequent constants potentially depend on $d$ and $r$, and their values may change from line to line. There exist $L\geq C/q_{X}$, a $C>0$ independent of $X$, and

For the second term on the right hand side of inequality (C.1), this can be upper bounded verbatim from , giving us

Combining inequalities (C.1), (C.2), and (C.3), and using that $L\geq C/q_{X}\geq 1$, we have

Appendix D Supplementary material

For large $m\geq 1$, we compare with the integral

where we used that $\{2^{m}\leq\|x\|_{2}\leq 2^{m+1}\}\subseteq\{2^{m}/\sqrt{d}\leq\|x\|_{\infty}\leq 2^{m+1}\}$. Then we have

This proves that $\partial^{\beta}K$ is Hölder continuous of order $\alpha$. ∎

We see that if $h_{X}$ is on the order of $n^{-1/d}$, then the generalization error decays on the order of $n^{-s}$. It is also interesting to note that the interpolant allows for irregular sampling sets $X$ and can be numerically computed.

D.2 Least squares vs minimum norm

This section describes a relationship between the following two algorithms. Assume $\Phi$ and $\omega$ are compatible, and that $X=\{x_{k}\}_{k=1}^{n}$ is sampling for $\Phi$. Given prescribed data $(X,y)$, define the functions

We follow the notation introduced in section A.1. The following proposition provides an explicit formula for the solution to this problem.

Assume $\Phi$ and $\omega$ are compatible, and $X=\{x_{k}\}_{k=1}^{n}$ is sampling for $\Phi$. For any $p\geq 1$ such that ${\bf A}_{p}$ has full rank, we have

The $p\geq p_{X}$ case is implied by Lemma A.2 since ${\bf K}_{p}^{\dagger}={\bf K}_{p}^{-1}$. For the case where $p\leq n$, the matrix ${\bf K}_{p}={\bf A}_{p}^{t}{\bf W}{\bf A}_{p}$ is possibly rank deficient. Since $\sum_{j=1}^{n}(y_{j}-f(x_{j}))^{2}=\|y-{\bf A}_{p}^{t}\widehat{f}_{p}\|_{2}^{2}$ and ${\bf A}_{p}^{t}$ is assumed to have full column rank, we see that

On the other hand, ${\bf B}:={\bf A}_{p}^{t}{\bf W}^{1/2}$ satisfies

This proposition is known for the unweighted case ($\omega_{j}=1$ for each $j\geq 1$), in which case, it connects the least squares solution of an over-determined linear system to the minimum norm one to an under-determined. Perhaps, it is not as widely known that this statement also holds for weighted norms.

D.3 Additional experiments for trigonometric interpolation

In our next set of experiments, we study the same experimental setup that was discussed in section 4.2 and explore the effects of increasing the number of samples $n$. Comparing fig. 1 (a) with fig. 2 (a) and (b), we see that increasing $n$ decreases the plateau, which is consistent with our theory that the plateau decreases in $h_{X}$. An interesting feature of these experiments is that the over-parameterized interpolant that achieves the smallest error in the $p\to\infty$ limit for $n=35,105,205$ are $s=4,3,2$ respectively. One explanation is that the Runge function is not differentiable at the singularity $x=\pm 1/2$, but is smooth elsewhere. For smaller values of $n$, hence larger $h_{X}$, the singularity does not have a significant impact, so smoother over-parameterized interpolants perform better. For larger $n$ and hence smaller $h_{X}$, the singularity becomes more influential and smoother interpolants suffer.

Appendix E NTK is not strictly positive-definite

Acknowledgments

The author thanks Sinan Güntürk for valuable discussions and gratefully acknowledges support from the AMS–Simons Travel Grant.

References