Controlling Statistical, Discretization, and Truncation Errors in Learning Fourier Linear Operators

## Abstract

Abstract We investigate the problem of learning operators between function spaces, focusing on the linear layer of the Fourier Neural Operator. First, we identify three main errors that occur during the learning process: statistical error due to finite sample size, truncation error from finite rank approximation of the operator, and discretization error from handling functional data on a finite grid of domain points. Finally, we analyze a Discrete Fourier Transform (DFT) based least squares estimator, establishing both upper and lower bounds on the aforementioned errors.

## 1 Introduction

Operator learning is the field, where the goal is to use statistical methods to estimate an unknown operator between function spaces. A primary application of operator learning is the development of fast data-driven methods to approximate the solution operator of partial differential equations (PDEs) (Li et al., ; Kovachki et al., ). For example, consider Possion equations on $\Omega\subset\mathbb{R}^{3}$ with Dirichlet’s boundary conditions:

$$ $-\nabla^{2}w=v,\quad\quad\quad x\in\Omega\text{ such that }w(x)=0\text{ for all }x\in\text{boundary}(\Omega).$ $$

The function $v$ is usually given and the goal is to map $v$ to the solution $w$. It is well known (Boullé and Townsend, , Section 1) that the solution operator of this PDE is a *linear* operator $\mathcal{L}$ such that $w=\mathcal{L}v$, where

$$ $(\mathcal{L}v)(y)=\int_{\Omega}G(y,x)\,v(x)\,dx\quad\quad\forall y\in\Omega.$ $$

Here, $G$ is the Green’s function of the Poisson equation. Given the training data $(v_{1},w_{1}),\ldots,(v_{n},w_{n})$, operator learning entails using statistical methods to estimate the solution operator $\widehat{\mathcal{L}}_{n}$. Then, given a new input $v$, one can get the approximate solution $\widehat{w}=\widehat{\mathcal{L}}_{n}v$. The goal is to develop the estimation rule such that $\widehat{w}$ is close to the actual solution $w=\mathcal{L}v$ under some appropriate metric.

Traditionally, given an input function $v$, one would use numerical methods such as finite differences to get a numerical solution. The solver starts from scratch for every new function $v$ of interest and can be computationally both slow and expensive depending on the numerical solver. This can be limiting in some applications such as engineering design where the solution needs to be evaluated for many different instances of the input functions. To solve this problem, operator learning aims to learn surrogate models that significantly increase speed for solution evaluation compared to traditional solvers while sacrificing a small degree of accuracy.

In this work, rather than focusing on specific PDEs, we carry out statistical analysis of a data-driven approach to operator learning in general. Focusing on the linear layer of the Fourier Neural Operator (Li et al., ) as our operator of interest, we begin by identifying the various types of errors incurred while learning these operators. For example, in addition to the statistical error resulting from finite sample size, there is also a discretization error in operator learning, as we deal with functional data that is available only on a finite grid of domain points. Finally, we analyze a Discrete Fourier Transform (DFT) based estimator, commonly used in practice, and provide both upper and lower bounds on the various errors associated with this estimator.

### 1.1 Neural Operators (Kovachki et al., 2023 )

To formally define our problem setting, we need to introduce neural operators. Unlike that of Poisson equations, the solution operators for most PDEs of interest
are nonlinear. Neural operators are the neural network-based architectures developed to model these nonlinear operators.

Let $\mathcal{V}$ be a vector space of functions from a bounded subset $\mathcal{X}\subset\mathbb{R}^{d_{\text{in}}}$ to $\mathbb{R}^{p}$. Consider $\mathcal{W}$ to be a vector space of functions from $\mathcal{Y}$ to $\mathbb{R}^{q}$ where $\mathcal{Y}\subset\mathbb{R}^{d_{\text{out}}}$ is also a bounded subset. Given a function $v\in\mathcal{V}$ , a single layer of neural operator $\texttt{N}_{t}:\mathcal{V}\to\mathcal{W}$ is a mapping such that

$$ $(\texttt{N}_{t}v)(y)=\sigma\Big{(}\left(\mathcal{K}_{\theta_{t}}v\right)(y)+b_ {t}(y)\Big{)}\quad\quad\forall y\in\mathcal{Y}\quad\text{ where }\quad\left( \mathcal{K}_{\theta_{t}}v\right)(y)=\int_{\mathcal{X}}k_{\theta_{t}}(y,x)\,v(x )\,dx.$ $$

The function $b_{t}:\mathcal{Y}\to\mathbb{R}^{q}$ is a bias function in $\mathcal{W}$, the function $\sigma:\mathbb{R}^{q}\to\mathbb{R}^{q}$ is a point-wise non-linear activation, and
the transformation $v\mapsto\mathcal{K}_{\theta_{t}}v$ is a integral kernel transform of $v$ using some kernel $k_{\theta_{t}}:\mathcal{Y}\times\mathcal{X}\to\mathbb{R}^{q\times p}$. Finally, the neural operator is a map $v\mapsto\operatorname{N}v$ where $\operatorname{N}v=\mathcal{Q}\circ\operatorname{N}_{T}\ldots\circ\operatorname
{N}_{1}\circ\mathcal{P}(v)$
where $\mathcal{P}$ and $\mathcal{Q}$ are lifting and projection operators that can be used to change the dimension of the functions.

Parametrizing $\mathcal{K}_{\theta_{t}}$ in terms of $k_{\theta_{t}}$ can be impractical due to the computational cost of calculating the integral in for each layer. Thus, a significant area of research in neural operators focuses on developing innovative parametrizations of $\mathcal{K}_{\theta_{t}}$ that facilitate more efficient computation. One such parametrization gives rise to a well-known architecture called the Fourier Neural Operator.

### 1.2 Fourier Neural Operator (FNO) (Li et al., 2021 )

Let $\mathcal{X}=\mathcal{Y}=\mathbb{T}^{d}$ be a $d$-dimensional periodic torus. In this work, we will identify $\mathbb{T}^{d}$ by $[0,1]^{d}$ with periodic boundary conditions. Assume the kernel $k_{\theta}$ is translation invariant–that is, $k_{\theta}(y,x)=k_{\theta}(y-x)$. This implies that $\mathcal{K}_{\theta}$ is a convolution operator. In particular, we have $\mathcal{K}_{\theta}v=k_{\theta}\star v$ (see Section 3 for more detail).
Then, the Convolution Theorem implies that

$$ $\mathcal{K}_{\theta}v=\mathcal{F}^{-1}\Big{(}\mathcal{F}(k_{\theta})\,\mathcal {F}(v)\Big{)},$ $$

where $\mathcal{F}$ and $\mathcal{F}^{-1}$ are Fourier and Inverse Fourier transform respectively. The key insight in FNO is that instead of parametrizing the kernel $k_{\theta}$, we parametrize its Fourier transform $\mathcal{F}(k_{\theta})$ directly. That is, we parametrize the kernel transform operator as

$$ $\mathcal{K}_{\beta}v=\mathcal{F}^{-1}\Big{(}\Lambda_{\beta}\,\,\mathcal{F}(v) \Big{)}.$ $$

This is a linear operator and will be referred to as *Fourier linear operator*. When $|\Lambda_{\beta}(m)|_{\ell^{1}}<\infty$, we can write this as

$$ $(\mathcal{K}_{\beta}v)(y)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i} \left\langle m,y\right\rangle}\,\Lambda_{\beta}(m)\,\,(\mathcal{F}v)(m)\quad \quad\forall y\in\mathcal{Y}.$ $$

There are two practical challenges in implementing the operator $\mathcal{K}_{\beta}$. First, the implementation involves an infinite sum over $\mathbb{Z}^{d}$. Second, the Fourier transform $\mathcal{F}v$ cannot be computed exactly since the function $v$ is only available on a finite grid of domain points. To address the first challenge, Li et al. () proposes fixing a large $K\in\mathbb{N}$ and summing only over $m\in\mathbb{Z}^{d}$ such that $|m|_{\ell^{\infty}}\leq K$. The second challenge is addressed by approximating $\mathcal{F}v$ using the discrete Fourier transform (DFT) of $v$ over the finite grid of domain points, which can be efficiently computed using fast Fourier transform (FFT) algorithms. The solution to the second challenge motivates our DFT-based least-squares estimator.

### 1.3 Our Contribution

In this work, we study the error bounds of learning the operator class $\{v\mapsto\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)\big{)}\,:
\,\beta\in\mathcal{B}\}$, where $\mathcal{B}$ is some parameter space that will be specified later. We study this simple setup to distinguish the paradigm of operator learning from the commonly used neural network architectures. By eliminating the complexities associated with neural networks, studying this linear class can provide insights that are broadly applicable to both algorithm design and theoretical analysis.

We assume that $\mathcal{V}=\mathcal{W}=\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$, a $(s,2)$-Sobolev space of real-valued functions defined on the $d$-dimensional periodic torus. See Section 4.3 for an explanation of why $\mathcal{V}$ and $\mathcal{W}$ need to be spaces of functions with higher-order smoothness to achieve a vanishing error in this setting. We work in the agnostic (misspecified) setting and analyze the DFT-based least-squares estimator (see Section 4.2 for more details). Specifically, for some universal constant $c_{1}>0$, we show that the excess risk of the DFT-based least-squares estimator is

$$ $\leq c_{1}\left(\frac{1}{\sqrt{n}}+\frac{1}{N^{s}}+\frac{1}{K^{2s}}\right).$ $$

The term $1/\sqrt{n}$ is the usual *statistical/estimation* error due to a finite sample size. The term $1/N^{s}$ is the *discretization* error incurred because the input and output functions are accessible to the learner only on the uniform grid of size $N^{d}$ of $[0,1]^{d}$. Finally, the term $1/K^{2s}$ is the *truncation* error incurred because the learner only works with the low Fourier modes $m$ such that $|m|_{\ell^{\infty}}\leq K$. Additionally, we establish the lower bound on excess risk, showing that

$$ $\geq c_{2}\left(\frac{1}{n}+\frac{1}{N^{2s}}+\frac{1}{K^{2s}}\right)$ $$

for some $c_{2}>0$. Our analysis is non-asymptotic and the precise form of the constants $c_{1}$ and $c_{2}$ are provided in Theorems 1 and 2 respectively.

### 1.4 Related Works

After Li et al. () proposed Fourier Neural Operators (FNOs), there has been a surge of interest in this architecture. The number of applied works is too vast and not entirely relevant to list here, so we will focus on theoretical works. One of the earliest theoretical analyses of FNOs was the universal approximation result by Kovachki et al. ().

More closely related to our work is a recent study on the sample complexity of various operator classes, including FNOs, by Kovachki et al. (). Their scope is broader than ours as they address a general class of nonlinear operators. However, their results do not imply ours. They treat the truncation parameter $K$ as a part of the model rather than a variable that the learning algorithm can choose. Their error bounds are based on metric entropy analysis, which leads to a suboptimal dependence on $K$ and the input dimension $d$. Specifically, their bounds break down as $K\to\infty$ and suffer from the curse of dimensionality in $d$. In contrast, our work establishes statistical error bounds using sharp Rademacher analysis, avoiding both dependence on $K$ and the curse of dimensionality in $d$. An interesting future direction is to extend our Rademacher-based analysis to capture function classes at the level of generality considered in Kovachki et al. (). Finally, we note that Rademacher-based analysis has also been used by (Raman et al., ; Tabaghi et al., ) to study Schatten operators between Hilbert spaces. Kim and Kang () also bound the Rademacher complexity of FNOs, but their results have issues as the implied generalization bounds do not always vanish.

A recent work by Lanthaler et al. () aligns with our goal of quantifying the discretization error of FNOs, and some of our proof techniques are inspired by their work. However, the nature of their results differs from ours. To discuss the difference precisely, let $\Psi$ be a trained Fourier Neural Operator and $v$ be an input function available to the learner only over a discrete grid of domain points of size $N$. Denote $v^{N}$ as the set of discrete values of $v$ available to the learner. Lanthaler et al. () bound the term $\|\Psi v-\Psi v^{N}\|$, quantifying the error incurred in the forward pass due to the function being available only over a discrete grid. Essentially, this only captures errors incurred during the test time but does not quantify the discretization error incurred during training. In contrast, our work focuses on quantifying how the error propagates to the trained operator and its evaluation during the test time because the training data is only available over a discrete grid.

Finally, we also note that our setup is closely related to the function-to-function regression often studied in the functional data analysis (FDA) literature. For example, the linear layer of a neural operator $v\mapsto\mathcal{K}v+b$ is a well-studied model in FDA (Wang et al., , Equation 15). Even a single layer of a neural operator $v\mapsto\sigma\left(\mathcal{K}v+b\right)$ has been examined in FDA literature as multi-index functional models (Wang et al., , Equation 13), (Chen et al., ). That said, the overall goal of the FDA differs slightly from that of operator learning. In FDA, the focus is on statistical inference, typically using RKHS-based frameworks under some assumptions about the data-generating process. As a result, FDA methods often do not always scale to large datasets. In contrast, operator learning primarily aims at prediction, seeking to develop surrogate models that approximate numerical PDE solvers (Li et al., ; Kovachki et al., ). The emphasis is on creating computationally efficient methods that can be used to train large models and handle large datasets. However, we believe that the intersection of these two fields can benefit both. The theoretical tools developed in FDA literature over more than 40 years can be applied to the analysis of operator learning methods, while the computational advances in operator learning can help scale FDA methods.

## 2 Preliminaries

### 2.1 Notation

Let $\mathbb{N}$ be natural numbers and $\mathbb{Z}$ be integers. Define $\mathbb{N}_{0}:=\mathbb{N}\cup\{0\}$. $\mathbb{R}$ and $\mathbb{C}$ denote real and complex numbers respectively. For any $\eta\in\mathbb{R}^{d}$, we let $|\eta|_{\infty}:=\max_{1\leq i\leq d}|\eta_{i}|$ denote the $\ell^{\infty}$ norm. For any complex number $z\in\mathbb{C}$ such that $z=a+b\operatorname{i}$, we use $|z|=\sqrt{a^{2}+b^{2}}$. For any $x,y\in\mathbb{R}^{d}$, the term $\left\langle x,y\right\rangle$ denotes the Euclidean inner product. Occasionally, the inner products on other Hilbert spaces such as $L^{2}$ will be distinguished from the Euclidean one with the subscript such as $\left\langle\cdot,\cdot\right\rangle_{L^{2}}$. However, when the context is clear, we will use $\left\langle\cdot,\cdot\right\rangle$ to denote canonical inner products on the respective Hilbert spaces.

Given $K\in\mathbb{N}$, we define

$$ $\mathbb{Z}^{d}_{\leq K}=\{m\in\mathbb{Z}^{d}\,:\,|m|_{\infty}\leq K\}\quad \quad\text{ and }\quad\quad\mathbb{Z}^{d}_{>K}:=\mathbb{Z}^{d}\backslash \mathbb{Z}^{d}_{\leq K}.$ $$

For a sequence $s:=\{s_{k}\}_{k\in\mathbb{Z}^{d}}$, we will also use $|s|_{\ell^{p}}$ to denote the $\ell^{p}$ norm of $s$.

We let $\mathbb{T}^{d}$ denote a $d$-dimensional periodic torus. In this paper, we identify $\mathbb{T}^{d}$ by $[0,1]^{d}$ with periodic boundary conditions. For a more detailed discussion on the torus, see (Grafakos et al., , Chapter 3).

Throughout the paper, for any $m\in\mathbb{Z}^{d}$, we let $\varphi_{m}$ denote a function from $\mathbb{T}^{d}$ to $\mathbb{R}$ defined as $\varphi_{m}(x)=e^{2\pi\operatorname{i}\left\langle m,x\right\rangle}$. The sequence $\{\varphi_{m}\}_{m\in\mathbb{Z}^{d}}$ will be referred as Fourier basis.

### 2.2 L 2 superscript 𝐿 2 L^{2} italic_L start_POSTSUPERSCRIPT 2 end_POSTSUPERSCRIPT -Spaces and Fourier Analysis

We define

$$ $L^{2}(\mathbb{T}^{d},\mathbb{R}):=\left\{u:\mathbb{T}^{d}\to\mathbb{R}\,:\, \int_{\mathbb{T}^{d}}\,|u(x)|^{2}\,dx<\infty\right\}.$ $$

Recall that $L^{2}(\mathbb{T}^{d},\mathbb{R})$ is a Hilbert space with inner-product

$$ $\left\langle u,v\right\rangle_{L^{2}}=\int_{\mathbb{T}^{d}}\,u(x)\,\overline{v (x)}\,dx,$ $$

where $\overline{z}=a-b\operatorname{i}$ is the complex conjugate of $z=a+b\operatorname{i}$. The norm induced by this inner-product will be denoted as $\left\lVert\cdot\right\rVert_{L^{2}}$.

The sequence $\{\varphi_{m}\}_{m\in\mathbb{Z}^{d}}$ forms a basis for $L^{2}(\mathbb{T}^{d},\mathbb{R})$. That is, for any $u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$, we can write

$$ $u=\sum_{m\in\mathbb{Z}^{d}}\left\langle u,\varphi_{m}\right\rangle_{L^{2}}\, \varphi_{m},$ $$

where the convergence is in $L^{2}$-norm. The celebrated Parseval’s identity implies that

$$ $\left\lVert u\right\rVert_{L^{2}}^{2}=\sum_{m\in\mathbb{Z}^{d}}|\left\langle u ,\varphi_{m}\right\rangle_{L^{2}}|^{2}.$ $$

We note that $u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$ only guarantees that the sum $\sum_{m\in\mathbb{Z}^{d}}\left\langle u,\varphi_{m}\right\rangle_{L^{2}}\,
\varphi_{m}$ converges to $u$ in $L^{2}$ norm. Occasionally, we require a stronger notion of convergence, namely pointwise convergence for every fixed $x\in\mathbb{T}^{d}$ or uniform convergence across $x\in\mathbb{T}^{d}$. For these cases, we will make appropriate assumptions to ensure that $\sum_{m\in\mathbb{Z}^{d}}|\left\langle u,\varphi_{m}\right\rangle|<\infty$. This absolute convergence with the Weierstrass M-test guarantees uniform convergence over $x\in\mathbb{T}^{d}$.

Since $\mathbb{T}^{d}$ is identified with a bounded set $[0,1]^{d}$, the condition $u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$ implies that $u$ is integrable. That is, $\int_{\mathbb{T}^{d}}|u(x)|\,dx<\infty$. For integrable functions, we use $\mathcal{F}$ to denote the Fourier transform operator such that $\mathcal{F}u:\mathbb{Z}^{d}\to\mathbb{C}$ is a complex-valued function on $\mathbb{Z}^{d}$ defined as

$$ $(\mathcal{F}u)(m)=\int_{\mathbb{T}^{d}}u(x)\,e^{-2\pi\operatorname{i}\left \langle m,x\right\rangle}\,dx.$ $$

Note that we have $(\mathcal{F}u)(m)=\left\langle u,\varphi_{m}\right\rangle$. We let $\mathcal{F}^{-1}$ denote the operator that satisfies
$\left(\mathcal{F}^{-1}\mathcal{F}\right)(u)=u$ for any integrable functions. The operator $\mathcal{F}^{-1}$ will be referred to as inverse Fourier transform.

### 2.3 Sobolev Spaces

Fix $s\in\mathbb{N}$ and define

$$ $\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})=\{u\in L^{2}(\mathbb{T}^{d},\mathbb {R})\,\,:\,\,\partial^{k}u\in L^{2}(\mathbb{T}^{d},\mathbb{R})\quad\forall k \in\mathbb{N}_{0}^{d}\text{ such that }|k|_{\infty}\leq s\}.$ $$

Here, $\partial^{k}u$ is the $k^{th}$-weak partial derivatives. The space $\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$, also referred to as $(s,d)$-Sobolev space, is
is a Hilbert space with an inner product

$$ $\left\langle u,v\right\rangle_{\mathcal{H}^{s}}:=\sum_{k\in\mathbb{N}_{0}^{d} \,:\,|k|_{\infty}\leq s}\left\langle\partial^{k}u,\partial^{k}v\right\rangle_{ L^{2}},$ $$

which naturally induces the norm

$$ $\left\lVert u\right\rVert_{\mathcal{H}^{s}}:=\sqrt{\sum_{k\in\mathbb{N}_{0}^{d }\,:\,|k|_{\infty}\leq s}\left\lVert\partial^{k}u\right\rVert_{L^{2}}^{2}}\quad.$ $$

In this paper, we often assume that $s>d/2$. This ensures that (see Lemma 4)

$$ $\sum_{m\in\mathbb{Z}^{d}}|\left\langle u,\varphi_{m}\right\rangle|<\infty.$ $$

As mentioned before, this absolute convergence of the sum of Fourier coefficients implies uniform convergence of the Fourier series. The absolute convergence also allows us to use Fubini’s Theorem to exchange sum and integrals.

Note that it is more common to define Sobolev spaces with multi-indices $k$ such that $|k|_{1}\leq s$ or $|k|_{2}\leq s$. We chose the restriction $|k|_{\infty}\leq s$ simply for the convenience of computation. However, as $d$ is finite and all $\ell_{p}$ norms on a $d$-dimensional space are equivalent up to a factor of $d$, our
results extend to the case $|k|_{p}\leq s$ for any $p\geq 1$ with minimal work.

## 3 Fourier Linear Operators

In this section, we provide a formal treatment of Fourier linear operators and the corresponding parametrization in FNOs. Recall that, in the Fourier Neural operator, one assumes that $\mathcal{X}=\mathcal{Y}=\mathbb{T}^{d}$ and the kernel is translation invariant. This implies that $\mathcal{K}_{\theta}$ defined in Section 1.1 is a convolution operator. That is,

$$ $\mathcal{K}_{\theta}\,v=k_{\theta}\star v,\quad\text{ where }\quad(k_{\theta} \star v)(y)=\int_{\mathbb{T}^{d}}k_{\theta}(y-x)\,v(x)\,dx.$ $$

The convolution is done elementwise,

$$ $(\mathcal{K}_{\theta}v)_{i}(y)=\sum_{j=1}^{p}\big{(}[k_{\theta}]_{ij}\star v_{ j}\big{)}(y),$ $$

where $[k_{\theta}]_{ij}:\mathbb{T}^{d}\to\mathbb{R}$ is the scalar-valued kernel defined by the $(i,j)^{th}$ component of $k_{\theta}$ and $(\mathcal{K}_{\theta}v)_{i}$ is the $i^{th}$ component of a $\mathbb{R}^{q}$-valued function. Similarly, $v_{j}:\mathbb{T}^{d}$ is the $j^{th}$ component function of $\mathbb{R}^{p}$-valued function $v$.
Next, using the linearity of the Fourier transform and the Convolution Theorem, we can write

$$ $\left(\mathcal{K}_{\theta}v\right)_{i}=\mathcal{F}^{-1}\left(\mathcal{F}\left( \sum_{j=1}^{p}\,[k_{\theta}]_{ij}\star v_{j}\right)\,\right)=\mathcal{F}^{-1} \left(\sum_{j=1}^{p}\mathcal{F}\big{(}[k_{\theta}]_{ij}\big{)}\,\mathcal{F}(v_ {j})\,\right).$ $$

where $\mathcal{F}$ is Fourier transform operator, and $\mathcal{F}^{-1}$ is the inverse Fourier transform. Here, $\mathcal{F}([k_{\theta}]_{ij}):\mathbb{Z}^{d}\to\mathbb{C}$ and $\mathcal{F}(v_{j}):\mathbb{Z}^{d}\to\mathbb{C}$ are Fourier transforms of $[k_{\theta}]_{ij}$ and $v_{j}$ respectively. Note that only discrete Fourier modes are defined because all the functions are defined on a periodic domain $\mathbb{T}^{d}$.

The key insight in FNO is that instead of parametrizing the kernel $k_{\theta}$, we parametrize its Fourier transform $\mathcal{F}(k_{\theta})$ directly. That is, we parametrize the kernel transform operator as

$$ $\left(\mathcal{K}_{\beta}v\right)_{i}=\mathcal{F}^{-1}\left(\sum_{j=1}^{p}\,[ \Lambda_{\beta}]_{ij}\,\,\mathcal{F}(v_{j})\,\right).$ $$

for some $\Lambda_{\beta}:\mathbb{Z}^{d}\to\mathbb{C}^{q\times p}$ that maps Fourier modes to a complex-valued matrix. Using the linearity of the inverse Fourier transform, we can write this parametrization more succinctly in a matrix form as

$$ $\mathcal{K}_{\beta}\,v=\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F} (v)\big{)}.$ $$

Since we have only defined $\mathcal{F}^{-1}$ implicitly as an operator such that $\mathcal{F}^{-1}\mathcal{F}$ is identity, it is reasonable to ask how one evaluates the function $\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)\big{)}$. To answer this question, let us define $w:=\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)\big{)}$. Since $w$ is defined on a periodic domain $\mathbb{T}^{d}$,
it has a Fourier series representation

$$ $w(y)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i}\left\langle m,x\right \rangle}\,(\mathcal{F}w)(m)=\sum_{m\in\mathbb{Z}^{d}}\,\varphi_{m}(y)\,\Lambda _{\beta}(m)\,(\mathcal{F}v)(m).$ $$

Here, we use the fact that $(\mathcal{F}w)(m)=\left(\Lambda_{\beta}\,\,\mathcal{F}(v)\right)(m)=\Lambda_{
\beta}(m)\,(\mathcal{F}v)(m)$.

We have not specified in what metric the sum on the right-hand side converges. However, the convergence is not really an issue from a practical standpoint. In practice, $\Lambda_{\beta}$ is a trainable parameter, and it has been observed in Li et al. () that parametrizing $\Lambda_{\beta}$ as a function from $\mathbb{Z}^{d}$ to $\mathbb{C}^{q\times p}$ yields sub-optimal results, possibly due to discrete structure of the lattice $\mathbb{Z}^{d}$. So, one picks a large $K>0$ and parametrize $\Lambda_{\beta}$ as a collection of matrices $\{\Lambda_{\beta}(m)\,:\,m\in\mathbb{Z}^{d}\text{ such that }|m|_{\infty}\leq K\}$. In this case, the sum contains $\leq K^{d}$ terms and thus always converges. If one still wants to deal with the infinite sum, a standard assumption would be $\Lambda_{\beta}\in\ell^{1}$ for all $(i,j)$ pairs. That is, $\sum_{m\in\mathbb{Z}^{d}}|[\Lambda_{\beta}(m)]_{ij}|<\infty$ for all $(i,j)$ pairs. Then, the Weirstrass $M$-test implies that the sum above converges uniformly over all $y\in\mathbb{T}^{d}$.

Although the reparameterization of $\mathcal{K}_{\theta}$ to $\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(\cdot)\big{)}$ allows for faster computation, it is unclear when these two parameterizations yield the same operator. Next, we state a simple condition under which the parametrization in terms of
$\theta$ and $\beta$ are equivalent.

###### Proposition 1 .

Let $k_{\theta}:\mathbb{Z}^{d}\to\mathbb{C}^{q\times p}$ be a kernel with decomposition

$$ $[k_{\theta}(y,x)]_{ij}=\sum_{m\in\mathbb{Z}^{d}}\,\,[\Lambda_{\beta}(m)]_{ij} \,\,\varphi_{m}(y)\,\,\varphi_{-m}(x)\quad\quad\forall(i,j)\in[q]\times[p]$ $$

for some $\Lambda_{\beta}:\mathbb{Z}^{d}\to\mathbb{C}^{q\times p}$ such that $\Lambda_{\beta}\in\ell^{1}$. Then, $\mathcal{K}_{\theta}v=\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(
v)\big{)}$ for all $v\in\mathcal{V}$.

The decomposition of $k_{\theta}$ shows that $[\Lambda_{\beta}(k)]_{ij}$ are the eigenvalues of the kernel integral operator specified by $[k_{\theta}]_{ij}$. In particular, note that

$$ $\begin{split}\int_{\mathbb{T}^{d}}[k_{\theta}(y,x)]_{ij}\,\varphi_{k}(x)dx&= \int_{\mathbb{T}^{d}}\left(\sum_{m\in\mathbb{Z}^{d}}\,\,[\Lambda_{\beta}(m)]_{ ij}\,\,\varphi_{m}(y)\,\,\varphi_{-m}(x)\right)\varphi_{k}(x)\,dx\\ &=\sum_{m\in\mathbb{Z}^{d}}\,[\Lambda_{\beta}(m)]_{ij}\,\varphi_{m}(y)\,\int_{ \mathbb{T}^{d}}\,\varphi_{-m}(x)\,\varphi_{k}(x)\,dx\\ &=\sum_{m\in\mathbb{Z}^{d}}\,[\Lambda_{\beta}(m)]_{ij}\,\varphi_{m}(y)\,\, \mathbbm{1}[k=m]\\ &=[\Lambda_{\beta}(k)]_{ij}\,\,\varphi_{k}(y)\,\end{split}$ $$

Swapping integral and sum above using Fubini is justified because $\Lambda_{\beta}\in\ell^{1}$. This calculation suggests that the Fourier layer of FNOs is actually parametrizing the eigenvalues of an operator with eigenvectors being $\varphi_{m}$’s. So, setting $\Lambda_{\beta}(m)=0$ for $m\in\mathbb{Z}^{d}_{>K}$ amounts to parametrizing the low-rank version of such operator. This viewpoint shows that FNO is actually just a special case of a Low-rank Neural Operator defined in (Kovachki et al., , Section 4.2).

More importantly, Lemma 1 provides a very natural way to generalize Fourier Neural Operators. That is, we can consider

$$ $[k_{\theta}(y,x)]_{ij}=\sum_{m\in\mathcal{J}}\,\,[\Lambda_{\beta}(m)]_{ij}\,\, \psi_{m}(y)\,\phi_{m}(x),$ $$

where $\mathcal{J}$ is some countable index-set and $\{\psi_{m}\}_{m\in\mathcal{J}}$, $\{\phi_{m}\}_{m\in\mathcal{J}}$ are some orthonormal sequence. Some common choice of orthonormal sequence that allows similar efficient computation as FFT include the Chebyshev polynomial (with fast cosine transform) and wavelet basis (with fast wavelet transform). In fact, some works have already explored the practical advantage of replacing Fourier basis with wavelet basis in certain problem settings Gupta et al. (); Tripura and Chakraborty ().

###### Proposition 1 .

## 4 Learning Fourier Linear Operators

In this section, we establish excess risk bounds of learning the operator class $\{v\mapsto\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)\big{)}\,:
\,\beta\in\mathcal{B}\}$, where $\mathcal{B}$ is some parameter space. Here, we only consider the case where $\mathcal{V},\mathcal{W}\subseteq L^{2}(\mathbb{T}^{d},\mathbb{R})$. This is different from the usual setting in the literature, where $\mathcal{V}$ and $\mathcal{W}$ are Banach spaces of vector-valued functions. First, a significant number of PDEs of practical interest describe how scalar-valued functions (such as vorticity on $3$-dimensional space) evolve. Since not much is known from a theoretical standpoint even for scalar-valued functions, we believe that this is a good start. Second, assuming $\mathcal{V},\mathcal{W}$ to be a subset of $L^{2}$ (a Hilbert space) does not result in any meaningful loss of generality from a practical standpoint. First, in practice, one must discretize the domain and work with function values over a discrete grid, which requires a bounded domain. Second, computations can only be performed with finite values of the function. This essentially means working with bounded functions on a bounded domain, all of which are $L^{2}$ integrable.

For scalar-valued functions, $\Lambda_{\beta}$ is a scalar-valued function defined on modes $\mathbb{Z}^{d}$. Since the function is only defined on a countable domain, we can also represent it by a scalar-valued sequence $\{\Lambda_{\beta}(m)\}_{m\in\mathbb{Z}^{d}}$. Henceforth, we will drop the $\beta$ and just write $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}}$, denoting $\lambda_{m}$’s to be the parameters themselves. For the convenience of notation, we will also $\lambda$ to denote the sequence $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}}$ and write $\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}$. Fixing some $C>0$, the class of interest can be written as

$$ $\left\{v\mapsto\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}\, :\,|\lambda|_{\ell^{1}}\leq C\right\}.$ $$

A starting point of our work is the following result about the singular value decomposition of Fourier linear operators.

###### Proposition 2 .

If $\lambda\in\ell^{1}$, then

$$ $\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}=\sum_{m\in \mathbb{Z}^{d}}\lambda_{m}\,\,\varphi_{m}\otimes\varphi_{-m},$ (1) $$

where the equality holds for every $u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$.

Here, $\varphi_{m}\otimes\varphi_{-m}$ is a rank-$1$ operator such that $(\varphi_{m}\otimes\varphi_{-m})(u)=\left\langle\varphi_{-m},u\right\rangle_{L
^{2}}\,\varphi_{m}$. The equality in (1) means that $\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(u)\big{)}=\sum_{m\in\mathbb{Z}
^{d}}\lambda_{m}\,\,\varphi_{m}\left\langle\varphi_{-m},u\right\rangle_{L^{2}}$ for every $u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$, where the sum converges uniformly over $x\in\mathbb{T}^{d}$ as $\Lambda_{\beta}\in\ell^{1}$.

Given Proposition 2, we can write our class as $\left\{\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\,\varphi_{m}\otimes\varphi_{-m}
\,:\,|\lambda|_{\ell^{1}}\leq C\right\}$. This representation is preferable for the following reasons. First, it highlights the fact that the Fourier basis is just one of the design choices for singular vectors that may be replaced with any other orthonormal sequences. Second, this representation also allows us to drop the constraint that $\lambda\in\ell^{1}$, which is a rather artificial constraint required only to ensure that the operator $\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}$ is well-defined. However, $\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\,\varphi_{m}\otimes\varphi_{-m}$ is still well-defined even when $\lambda\in\ell^{\infty}$ (in fact, it is a bounded operator). Therefore, for some fixed $C>0$, we will instead study the class of operators

$$ $\mathcal{T}:=\left\{\sum_{m\in\mathbb{Z}^{d}}\,\lambda_{m}\,\,\varphi_{m} \otimes\varphi_{-m}\,\,\Big{|}\,\,|\lambda|_{\ell^{\infty}}\leq C\right\}.$ $$

Since the class $\left\{v\mapsto\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}\,
:\,\,|\lambda|_{\ell^{1}}\leq C\right\}$ is contained in the class $\mathcal{T}$, any guarantee (in terms of upper bound) for $\mathcal{T}$ also holds for the $\ell^{1}$ constrained class.

Remark. The class $\mathcal{T}$ should remind readers of de Hoop et al. (), who also consider the problem of singular value inference of an operator under fixed singular vectors. However, their approach differs from ours in two significant ways. First, they consider only the well-specified setting with an additive noise model, whereas we adopt a fully agnostic viewpoint. Second, they do not account for possible discretization errors, as they assume that their input and output functions are fully available to the learner.

###### Proposition 2 .

### 4.1 Problem Setting and Error Types

We adopt the framework of statistical learning and study the rates of error in learning the class $\mathcal{T}$. In statistical learning, the learner is provided with $n\in\mathbb{N}$ i.i.d samples $S_{n}=\{(v_{i},w_{i})\}_{i=1}^{n}$ from some unknown distribution $\mu$ on $\mathcal{V}\times\mathcal{W}$. We adopt a fully agnostic viewpoint and do not make any assumptions about the data-generating process.
Next, using the sample $S_{n}$ and some prespecified learning rule, the learner then finds an estimator $\widehat{T}\in\mathcal{T}$. We will abuse notation and denote $\widehat{T}$ to be both the learning rule and the estimator output by the learner. For an estimator $\widehat{T}$, we can define its expected excess risk as

$$ $\mathcal{E}_{n}(\widehat{T},\mathcal{T},\mu):=\operatorname*{\mathbb{E}}_{S_{n }\sim\mu^{n}}\left[\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\lVert \widehat{T}v-w\rVert^{2}_{L^{2}}\right]-\inf_{T\in\mathcal{T}}\operatorname*{ \mathbb{E}}_{(v,w)\sim\mu}\left[\left\lVert Tv-w\right\rVert_{L^{2}}^{2}\right ]\right].$ $$

Formally, the goal of the learner is to output the estimator such that $\mathcal{E}_{n}(\widehat{T},\mathcal{T},\mu)\to 0$ as $n\to\infty$. In traditional settings, the excess risk $\mathcal{E}_{n}(\widehat{T},\mathcal{T},\mu)$ is usually referred to as the statistical error of the learner. This error arises because the learner is trying to find the optimal operator in $\mathcal{T}$ for distribution $\mu$ while only having access to finitely many samples from the distribution. However, unlike traditional statistical learning settings, in operator learning, there are two additional errors beyond the statistical error: (I) *Discretization Error* and (II) * Truncation Error*.

The discretization error arises because the learner only has access to $(v_{i},w_{i})\sim\mu$ over some discrete grid of domain points. In this work, we assume that each $v_{i}$ and $w_{i}$ are available on a uniform grid

$$ $\operatorname{G}:=\left\{\frac{m}{N}:m\in\{0,\ldots,N-1\}^{d}\right\}$ $$

of $[0,1]^{d}$ for some prespecified $N\in\mathbb{N}$. That is, the learner only has access to $\{v_{i}(x)\,:x\in\operatorname{G}\}$ and $\{w_{i}(x)\,:x\in\operatorname{G}\}$. Although other grids are also used in practice, the use of FNO requires uniform griding. This is because the main benefit of FNO is its computationally efficient approximation of Fourier transform through fast Fourier transform (FFT) algorithms, which requires uniform grids.

To see where the truncation error comes from, note that the representation of any estimator $T\in\mathcal{T}$ requires specifying an infinite sequence $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}}$. However, the infinite sequence cannot be implemented in a computer. Thus, for a practical implementation (Li et al., ), one picks a large $K\in\mathbb{N}$ and specifies the finite rank operator

$$ $T_{K}=\sum_{m\in\mathbb{Z}^{d}\,:\,|m|_{\infty}\leq K}\lambda_{m}\,\varphi_{m} \otimes\varphi_{-m}=:\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\lambda_{m}\,\varphi_{m }\otimes\varphi_{-m}.$ $$

While the truncation error is specific to our class of interest $\mathcal{T}$, a similar “truncation” error occurs in any model class. Such error arises because operator learning is inherently an infinite-dimensional problem, yet any computation we perform is limited to some finite-dimensional subspace.

#### 4.1.1 Further Connection and Comparison to FDA.

The operator $T_{K}$ is closely related to the functional principal component regression-based estimator commonly used in the FDA literature. Given $n$ i.i.d. pairs of functions $\{(v_{i},w_{i})\}_{i\leq n}$, computing the usual least-squares linear estimator often involves solving the equation $\sum_{i=1}^{n}w_{i}\otimes v_{i}=L\circ\left(\sum_{i=1}^{n}v_{i}\otimes v_{i}\right)$. Typically, this equation is not fully specified when $v_{i}$ and $w_{i}$ belong to infinite-dimensional spaces. To address this, various techniques can be used to compute the pseudo-inverse $\left(\sum_{i=1}^{n}v_{i}\otimes v_{i}\right)^{\dagger}$, resulting in a large family of estimators.
One popular technique for computing this pseudo-inverse involves fixing an orthonormal basis $\{\psi_{t}\}_{t\in\mathbb{N}}$ of the space of $v_{i}$’s. Assuming an eigendecomposition of the form $\sum_{i=1}^{n}v_{i}\otimes v_{i}=\sum_{t\geq 1}\eta_{t}\,\psi_{t}\otimes\psi_{t}$, the pseudo-inverse can be written as $\left(\sum_{i=1}^{n}v_{i}\otimes v_{i}\right)^{\dagger}=\sum_{t\geq 1}\mathbbm
{1}[\eta_{t}>0]\,\eta_{t}^{-1}\,\psi_{t}\otimes\psi_{t}$. This yields the estimator $\widehat{L}$ such that $\widehat{L}v=\left(\sum_{t\geq 1}\mathbbm{1}[\eta_{t}>0]\,\eta_{t}^{-1}\,\psi_
{t}\otimes\psi_{t}\right)\sum_{i=1}^{n}w_{i}\left\langle v_{i},v\right\rangle$.
For practical implementation, one often introduces a parameter $\tau\in\mathbb{N}$, reparameterizes $\mathbbm{1}[\eta_{t}>0]\,\eta_{t}^{-1}$ as $\lambda_{t}$, and learns the $\lambda_{t}$’s from the data. This results in the estimator $\widehat{L}$ such that $\widehat{L}v=\left(\sum_{t=1}^{\tau}\lambda_{t}\,\psi_{t}\otimes\psi_{t}\right
)\sum_{i=1}^{n}w_{i}\left\langle v_{i},v\right\rangle$.

Hörmann and Kidziński () proposed a similar estimator and established its consistency under a well-specified additive noise model. Additionally, both the $\psi_{t}$’s and the truncation parameter must be learned from the observed data to obtain the guarantees established in Hörmann and Kidziński (), which is typically a major computational bottleneck. In contrast, we consider the agnostic setting and the parameter $K$ only needs to depend on the sample size $n$ to achieve $\sqrt{n}$-risk consistency. Finally, they assume that the learner has access to $v_{i}$ and $w_{i}$ in their exact form, which is unrealistic in operator learning. Similar principal component-based estimators have also been studied in Yao et al. () and Reimherr (), but both assume a well-specified additive noise model and access to exact functions. Overall, our work differs fundamentally from the FDA results in two main aspects. First, unlike most of the FDA literature, we consider the agnostic (misspecified) setting. Second, in addition to quantifying statistical error, we are equally interested in quantifying the discretization error of the estimator.

### 4.2 A Constrained Least-Squares Estimator

In this section, we specify our primary estimator of interest. Let $T=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\varphi_{m}\otimes\varphi_{-m}$. For any $v\in\mathcal{V}$, we have $Tv=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\left\langle\varphi_{-m},v\right\rangle
\,\varphi_{m}$. Since we only require $\ell^{\infty}$ norm of $\lambda$ to be bounded by $C$, we only get the convergence of the sum $\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\left\langle\varphi_{-m},v\right\rangle\,
\varphi_{m}$ in $L^{2}$ norm. This is in contrast to the uniform convergence implied by the constraint $\lambda\in\ell^{1}$.

Since $\{\varphi_{m}\}_{m\in\mathbb{Z}^{d}}$ is an orthonormal basis of $L^{2}(\mathbb{T}^{d},\mathbb{R})$, Parseval’s identity gives us that

$$ $\begin{split}\left\lVert Tv-w\right\rVert^{2}_{L^{2}}&=\sum_{m\in\mathbb{Z}^{d }}|\left\langle Tv-w,\varphi_{m}\right\rangle_{L^{2}}|^{2}=\sum_{m\in\mathbb{Z }^{d}}|\lambda_{m}\left\langle\varphi_{-m},v\right\rangle_{L^{2}}-\left\langle \varphi_{-m},w\right\rangle_{L^{2}}|^{2}.\end{split}$ (2) $$

To see why the last equality is true, note that $\left\langle Tv,\varphi_{m}\right\rangle=\lambda_{m}\left\langle\varphi_{-m},v\right\rangle$ and

$$ $\left\langle w,\varphi_{m}\right\rangle_{L^{2}}:=\int_{\mathbb{T}^{d}}w(x)\, \overline{\varphi_{m}(x)}\,dx=\int_{\mathbb{T}^{d}}\varphi_{-m}(x)\,w(x)dx= \int_{\mathbb{T}^{d}}\varphi_{-m}(x)\,\overline{w(x)}dx=\left\langle\varphi_{- m},w\right\rangle_{L^{2}}.$ $$

Here, we use the fact that $w$ is a real-valued function.

Thus, given $\{(v_{1},w_{i})\}_{i=1}^{n}$, the least-squares estimator over the class $\mathcal{T}$ is an operator $T$ specified by the sequence $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}}$, which is in turn obtained by solving the optimization problem

$$ $\min_{\{\lambda_{m}\,:\,m\in\mathbb{Z}^{d}\}}\,\,\frac{1}{n}\sum_{i=1}^{n}\sum _{m\in\mathbb{Z}^{d}}|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle_{ L^{2}}-\left\langle\varphi_{-m},w_{i}\right\rangle_{L^{2}}|^{2}\,\quad\text{ subject to }\sup_{m\in\mathbb{Z}^{d}}|\lambda_{m}|\leq C.$ $$

However, this estimator cannot be implemented for two reasons. First, there is an infinite sum over $\mathbb{Z}^{d}$. Second the learner only has access to $(v_{i},w_{i})$ through $v_{i}^{N}:=\{v_{i}(x)\,:x\in\operatorname{G}\}$ and $w_{i}^{N}:=\{w_{i}(x)\,:x\in\operatorname{G}\}$, and thus the $L^{2}$ inner products cannot be computed exactly. Both of these issues can be resolved by considering the operator specified by the finite length sequence $\widehat{\lambda}(N)=\{\hat{\lambda}_{m}:m\in\mathbb{Z}^{d}_{\leq K}\}$ obtained by solving the optimization problem

$$ $\min_{\{\lambda_{m}\,:\,m\in\mathbb{Z}^{d}_{\leq K}\}}\,\,\frac{1}{n}\sum_{i=1 }^{n}\,\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\left|\lambda_{m}\operatorname{DFT}(v _{i}^{N})(-m)-\operatorname{DFT}(w_{i}^{N})(-m)\right|^{2}\,\,\text{ subject to }\sup_{m\in\mathbb{Z}^{d}_{\leq K}}|\lambda_{m}|\leq C.$ $$

$\operatorname{DFT}$, which stands for Discrete Fourier Transform, is the numerical approximation of $\left\langle\varphi_{-m},u\right\rangle_{L^{2}}$ and is defined formally as

$$ $\operatorname{DFT}(v_{i}^{N})(-m):=\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}v _{i}(x)\,e^{-2\pi\operatorname{i}\left\langle x,m\right\rangle}\quad\text{and} \quad\operatorname{DFT}(w_{i}^{N})(-m):=\frac{1}{N^{d}}\sum_{x\in\operatorname {G}}w_{i}(x)\,e^{-2\pi\operatorname{i}\left\langle x,m\right\rangle}.$ $$

To indicate the dependence of both truncation value $K$ and grid-size $N^{d}$, let us denote the estimator obtained by solving this problem to be $\widehat{T}_{K}^{N}$ where

$$ $\widehat{T}_{K}^{N}:=\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\widehat{\lambda}_{m}(N )\,\,\varphi_{m}\otimes\varphi_{-m}.$ (3) $$

The estimator $\widehat{T}^{N}_{K}$ is the closest implementable version of the least-squares estimator for our setting.

### 4.3 Error Bounds

In this section, we study how $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)$ decay as a function of $n,K$ and $N$. Note that we have only specified that $\mathcal{V}$ and $\mathcal{W}$ are subsets of $L^{2}(\mathbb{T}^{d},\mathbb{R})$, but have not specified their precise form. A natural choice would be $\mathcal{V}=\mathcal{W}=\{u\in L^{2}(\mathbb{T}^{d},\mathbb{R})\,:\,\left
\lVert u\right\rVert_{L^{2}}\leq 1\}$, the unit ball of $L^{2}(\mathbb{T}^{d},\mathbb{R})$. However, it turns out that $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)$ does not vanish under the assumption that $\mathcal{V}$ and $\mathcal{W}$ are the unit ball of $L^{2}$.

To see this, let $K\in\mathbb{N}$ be any truncation parameter chosen by the learner. Define $\mu=\text{Uniform}(\{(\psi_{m},\psi_{m}):\,2^{K}<|m|_{\infty}<2^{K+1}\})$ that is only supported on extremely large modes. Here,

$$ $\psi_{m}=\frac{1}{\sqrt{2}}(\varphi_{m}+\varphi_{-m})$ $$

is the symmetrized, real-valued version of $m$-th Fourier mode. Note that we can choose a distribution as a function of $K$ because the truncation parameter $K$ can depend on the sample size $n$, but not on the exact realization of the samples.

For any sample size $n$ and the estimator $\widehat{T}^{N}_{K}$ produced by the learner, $\widehat{T}^{N}_{K}v=0$ almost surely for $(v,w)\sim\mu$. Thus, we have

$$ $\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\lVert\widehat{T}_{K}^{N}v-w \rVert^{2}_{L^{2}}\right]=\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[ \lVert w\rVert^{2}_{L^{2}}\right]=1,$ $$

as $w=\psi_{m}$ for some $2^{K}<|m|_{\infty}<2^{K+1}$ almost surely and $\left\lVert\psi_{m}\right\rVert_{L^{2}}=1$ for any $m\in\mathbb{Z}^{d}_{>0}$.

Let $C=1$ and define $T^{\star}=\sum_{m\in\mathbb{Z}^{d}}\varphi_{m}\otimes\varphi_{-m}$. Since $T^{\star}\in\mathcal{T}$ and

$$ $T^{\star}\psi_{k}=\frac{1}{\sqrt{2}}(T^{\star}\,\varphi_{k}+T^{\star}\,\varphi _{-k})=\frac{1}{\sqrt{2}}\left(\varphi_{-k}+\varphi_{k}\right)=\psi_{k}\quad \forall k\in\mathbb{Z}^{d}\backslash\{\bf{0}\},$ $$

we obtain

$$ $\inf_{T\in\mathcal{T}}\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\left \lVert Tv-w\right\rVert_{L^{2}}^{2}\right]\leq\operatorname*{\mathbb{E}}_{(v,w )\sim\mu}\left[\left\lVert T^{\star}v-w\right\rVert_{L^{2}}^{2}\right]=0.$ $$

Thus, we have shown that

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)=\operatorname*{\mathbb{E} }_{(v,w)\sim\mu}\left[\lVert\widehat{T}_{K}^{N}v-w\rVert^{2}_{L^{2}}\right]- \inf_{T\in\mathcal{T}}\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\left \lVert Tv-w\right\rVert_{L^{2}}^{2}\right]\geq 1.$ $$

This shows that merely having a bound on $L^{2}$ norm of $v,w$ is not sufficient to achieve a vanishing error.

The inductive bias in FNOs is that the functions are sufficiently smooth so that the higher Fourier modes can be safely ignored. We will also adopt this viewpoint and assume that $\mathcal{V}$ and $\mathcal{W}$ are smooth subsets of $L^{2}(\mathbb{T}^{d},\mathbb{R})$. In particular, we will assume that $\mathcal{V}=\mathcal{W}=\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$, a $(s,d)$-Sobolev space (see Section 2.3). For any $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$, we are guaranteed that $\left\langle\varphi_{-m},u\right\rangle_{L^{2}}\to 0$ sufficiently fast as $|m|_{\infty}\to\infty$. This allows us to ignore higher Fourier modes while only incurring small error.
The following Theorem makes these arguments precise and provides an upper bound on the excess risk of $\widehat{T}_{K}^{N}$ in terms of $n,N,$ and $K$.

###### Theorem 1 (Upper Bound) .

Let $\mathcal{V}=\mathcal{W}=\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ for $s>d/2$ and $\mu$ be any distribution on $\mathcal{V}\times\mathcal{W}$ for which $\exists B>0$ such that $\left\lVert v\right\rVert_{\mathcal{H}^{s}}\leq B$ and $\left\lVert w\right\rVert_{\mathcal{H}^{s}}\leq B$ almost surely. Then, for $n$ iid samples $\{(v_{i},w_{i})\}_{i=1}^{n}\sim\mu^{n}$ accessible to the learner over the $N$-uniform grid of $[0,1]^{d}$, the estimator $\widehat{T}_{K}^{N}$ defined in Equation (3) for $N>\max\{5,2K\}$ satisfies

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)\leq 8B^{2}(C+1)^{2}\left( \frac{1}{\sqrt{n}}+\frac{2^{s}\sqrt{\pi^{d}}}{N^{s}}+\frac{1}{K^{2s}}\right).$ $$

The terms $O(1/\sqrt{n})$, $O(1/N^{s})$, and $O(1/K^{2s})$ are the estimator’s statistical, discretization, and truncation errors respectively. For most practical applications of interest, we have $d=3$ (functions defined on spatial coordinates).
Since $\sqrt{\pi^{d}}\leq 6$ in these cases, the exponential dependence of the discretization error on $d$ is not a significant issue. Finally, we note that choosing $N\geq n^{\frac{1}{2s}}$ and $K\geq n^{\frac{1}{4s}}$, Theorem 1 guarantees the $\sqrt{n}$– risk consistency of the estimator $\widehat{T}^{N}_{K}$.

Our next result provides a lower bound on the rates at which $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)$ decay.

###### Theorem 2 (Lower Bounds) .

Let $\mathcal{V}=\mathcal{W}=\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ for $s>d/2$ and $C=1$. Given $n,N,K\in\mathbb{N}$, there exists a distribution on $\mu$ on $\mathcal{V}\times\mathcal{W}$ for which $\exists B>0$ such that $\left\lVert v\right\rVert_{\mathcal{H}^{s}}\leq B$ and $\left\lVert w\right\rVert_{\mathcal{H}^{s}}\leq B$ almost surely and for $n$ iid samples $\{(v_{i},w_{i})\}_{i=1}^{n}\sim\mu^{n}$ accessible over the $N$-uniform grid of $[0,1]^{d}$, the estimator $\widehat{T}_{K}^{N}$ defined in Equation (3) for $N^{s}\geq\sqrt{2}B$ satisfies

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)\geq\frac{B^{2}}{3(s+1)} \left(\frac{1}{8n}+\frac{1}{N^{2s}}+\frac{2}{(K+2)^{2s}}\right).$ $$

The rate of decay for truncation error matches with the upperbound. However, there is a quadratic gap in the statistical and discretization error rate between our upper and lower bounds. We leave closing this gap for future work.

###### Theorem 1 (Upper Bound) .

###### Theorem 2 (Lower Bounds) .

## 5 Discussion and Future Work

In this work, we established the excess risk error bounds of learning the linear layer of Fourier neural operators $v\mapsto\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)\big{)}$. A natural future direction is to extend these results to single layer Fourier neural operator, $v\mapsto\sigma\left(\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)
\big{)}+b\right)$ and then possibly to multiple layers. Although simple metric entropy-based analysis gives a bound on statistical error even for single layer neural operator, such a bound is vacuous when $K\to\infty$. It would be interesting to see if we can get a meaningful statistical rate even at the limit of $K\to\infty$. From a practical standpoint, one can view $K$ as an analog of the width of traditional neural networks. Thus, analysis of $v\mapsto\sigma\left(\mathcal{F}^{-1}\big{(}\,\Lambda_{\beta}\,\,\mathcal{F}(v)
\big{)}+b\right)$ as $K\to\infty$ can perhaps lead to an analog of infinite width and neural tangent kernel theory (Jacot et al., ) for operator learning. These insights will also help us better understand width vs depth tradeoffs when it comes to operator learning.

As for discretization error, we consider the setup where the training data is available of $N^{d}$ uniform grid but the trained operator is evaluated at full resolution ($N\to\infty$). It would be interesting to understand how the discretization error changes when the training data is available at resolution $N_{1}$, but the trained operator is evaluated at resolution $N_{2}$. Such a theory would help formalize the multi-resolution generalization (operators trained at lower resolution have good generalization even when evaluated in higher resolution) often observed in practice( see (Li et al., , Section 5) and (Gupta et al., , Section 3)).

Finally, with PDEs as an application, it is unclear if the iid-based statistical model is the right framework to study operator learning. For instance, Boullé et al. () demonstrates that using an active learning approach for data collection and training when learning solution operators for elliptic PDEs results in exponential error decay with increasing sample size. Therefore, an important future direction is to define the appropriate active learning model and develop active algorithms for operator learning.

## Appendix A Proofs of Operator Theoretic Properties

### A.1 Proof of Proposition 1

###### Proof.

Let $\lambda_{ij}(m):=[\Lambda_{\beta}(m)]_{ij}$ and assume that

$$ $[k_{\theta}(y,x)]_{ij}=\sum_{m\in\mathbb{Z}^{d}}\lambda_{ij}(m)\,\,\varphi_{m} (y)\,\,\varphi_{-m}(x).$ $$

Using this decomposition, we obtain

$$ $\begin{split}(\mathcal{K}_{\theta}v)_{i}(y)&=\int_{\mathbb{T}^{d}}\,\sum_{j=1} ^{p}\,[k_{\theta}(y,x)]_{ij}\,\,v_{j}(x)\,dx\\ &=\int_{\mathbb{T}^{d}}\,\sum_{j=1}^{p}\,\sum_{m\in\mathbb{Z}^{d}}\lambda_{ij} (m)\,\,\varphi_{m}(y)\,\,\varphi_{-m}(x)\,v_{j}(x)\,dx\\ &=\sum_{m\in\mathbb{Z}^{d}}\,\varphi_{m}(y)\ \sum_{j=1}^{p}\lambda_{ij}(m)\, \int_{\mathbb{T}^{d}}\,\varphi_{-m}(x)\,v_{j}(x)\,dx.\end{split}$ $$

Note that swapping the integral and the summation is justified through Fubini’s because the sum over $\mathbb{Z}^{d}$ converges absolutely (as $\Lambda_{\beta}\in\ell^{1}$) and $\mathbb{T}^{d}$ is a bounded set. Since

$$ $\int_{\mathbb{T}^{d}}\,\varphi_{-m}(x)\,v_{j}(x)\,dx=\int_{\mathbb{T}^{d}}\,e^ {-2\pi\operatorname{i}\left\langle m,x\right\rangle}v_{j}(x)\,dx=\mathcal{F}(v _{j})(m),$ $$

we can write

$$ $(\mathcal{K}_{\theta}v)_{i}(y)=\sum_{m\in\mathbb{Z}^{d}}\varphi_{m}(y)\sum_{j= 1}^{p}\lambda_{ij}(m)\,\,\mathcal{F}(v_{j})(m).$ $$

Next, consider the function $w:=\mathcal{F}^{-1}\left(\sum_{j=1}^{p}\lambda_{ij}\,\mathcal{F}(v_{j})\right)$. Our proof will be complete upon showing that $w(y)=(\mathcal{K}_{\theta}v)_{i}(y)$ for every $y\in\mathbb{T}^{d}$. Since the function $w:\mathbb{T}^{d}\to\mathbb{C}$ is defined on a periodic domain, it has a Fourier series representation. That is,

$$ $w(y)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i}\left\langle m,y\right \rangle}\,\mathcal{F}(w)(m)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i} \left\langle m,y\right\rangle}\sum_{j=1}^{p}\lambda_{ij}(m)\,\mathcal{F}(v_{j} )(m),$ $$

where the final equality follows because $\mathcal{F}\left(\mathcal{F}^{-1}\left(\sum_{j=1}^{p}\lambda_{ij}\,\mathcal{F}
(v_{j})\right)\right)(m)=\sum_{j=1}^{p}\lambda_{ij}(m)\,\mathcal{F}(v_{j})(m)$. As usual, $\Lambda_{\beta}\in\ell^{1}$ implies that the sum above converges uniformly over $y\in\mathbb{T}^{d}$.
Recalling that $\varphi_{m}(y)=e^{2\pi\operatorname{i}\left\langle m,y\right\rangle}$, we have shown that $(\mathcal{K}_{\theta}v)_{i}(y)=w(y)$ for all $y\in\mathbb{T}^{d}$. This subsequently implies that

$$ $(\mathcal{K}_{\theta}v)_{i}=w=\mathcal{F}^{-1}\left(\sum_{j=1}^{p}\lambda_{ij} \,\mathcal{F}(v_{j})\right).$ $$

Finally, using the linearity of the inverse Fourier transform and writing this in the matrix form establishes that $\mathcal{K}_{\theta}v=\mathcal{F}^{-1}(\Lambda_{\beta}\,\mathcal{F}(v))$ for any $v\in\mathcal{V}$.
∎

###### Proof.

### A.2 Proof of Proposition 2

###### Proof.

Fix $v\in\mathcal{V}$ and define $w:=\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(v)\big{)}$. By definition of the operator $\mathcal{F}^{-1}\big{(}\,\lambda\,\,\mathcal{F}(\cdot)\big{)}$, we have

$$ $w=\mathcal{F}^{-1}\left(\lambda\,\mathcal{F}(v)\,\right).$ $$

Using the Fourier series representation of $w$, we have

$$ $w(\cdot)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i}\left\langle m,\cdot \right\rangle}\,(\mathcal{F}w)(m)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi \operatorname{i}\left\langle m,\cdot\right\rangle}\,\lambda_{m}\,\,\,\mathcal{ F}(v)(m).$ $$

This step is rigorously justified because $\lambda\in\ell^{1}$. Noting that

$$ $(\mathcal{F}v)(m)=\int_{\mathbb{T}^{d}}\,e^{-2\pi\operatorname{i}\left\langle m ,x\right\rangle}\,v(x)\,dx=\left\langle\varphi_{-m},v\right\rangle_{L^{2}},$ $$

we can write

$$ $w(\cdot)=\sum_{m\in\mathbb{Z}^{d}}e^{2\pi\operatorname{i}\left\langle m,\cdot \right\rangle}\,\lambda_{m}\,\left\langle\varphi_{-m},v\right\rangle_{L^{2}}.$ $$

Thus, $w=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\left\langle\varphi_{-m},v\right
\rangle_{L^{2}}\,\varphi_{m}$, where the convergence is uniform over $\mathbb{T}^{d}$. This implies that

$$ $\mathcal{F}^{-1}\left(\lambda\,\mathcal{F}(v)\,\right)=\sum_{m\in\mathbb{Z}^{d }}\lambda_{m}\,\left\langle\varphi_{-m},v\right\rangle_{L^{2}}\,\varphi_{m}.$ $$

Since this equality holds for every $v\in\mathcal{V}$, we have

$$ $\mathcal{F}^{-1}\left(\lambda\,\mathcal{F}(\cdot)\,\right)=\sum_{m\in\mathbb{Z }^{d}}\lambda_{m}\,\,\varphi_{m}\otimes\varphi_{-m}.$ $$

∎

###### Proof.

## Appendix B Technical Lemmas

###### Lemma 1 .

For any $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ , we have

$$ $|\left\langle\varphi_{-m},u\right\rangle_{L^{2}}|\leq\frac{\left\lVert u\right \rVert_{\mathcal{H}^{s}}}{(2\pi)^{s}\,|m|_{\infty}^{s}}\quad\quad\forall m\in \mathbb{Z}^{d}\backslash\{\bf{0}\}.$ $$

###### Proof.

Fix $m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}$ and let $|m_{j}|=|m|_{\infty}=\max_{1\leq i\leq d}|m_{i}|$. Clearly, $m_{j}\neq 0$. Integrating by parts $s$ times with respect to variable $x_{j}$ in $x=(x_{1},\ldots,x_{d})$, we obtain

$$ $\left\langle\varphi_{-m},u\right\rangle=\int_{\mathbb{T}^{d}}\,u(x)e^{-2\pi \operatorname{i}\left\langle m,x\right\rangle}\,dx=(-1)^{s}\,\int_{\mathbb{T}^ {d}}\,(\partial^{s}_{j}u)(x)\frac{e^{-2\pi\operatorname{i}\left\langle m,x \right\rangle}}{(-2\pi\operatorname{i}\,m_{j})^{s}}\,dx=\left(\frac{1}{2\pi \operatorname{i}m_{j}}\right)^{s}\left\langle\varphi_{-m},\partial_{j}^{s}\,u \right\rangle.$ $$

Here, all boundary terms vanish because $\mathbb{T}^{d}$ does not have a boundary ([Grafakos et al., , Proof of Theorem 3.3.9]). Taking absolute value on both sides, we obtain that

$$ $|m_{j}|^{s}\,|\left\langle\varphi_{-m},u\right\rangle|=(2\pi)^{-s}\,|\left \langle\varphi_{-m},\partial^{s}_{j}u\right\rangle|$ $$

Finally, using the fact that $\left|\left\langle\varphi_{-m},\partial^{s}_{j}u\right\rangle\right|\leq\left
\lVert u\right\rVert_{\mathcal{H}^{s}}$ completes our proof.
∎

###### Lemma 2 .

For any $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$, we have

$$ $\sum_{m\in\mathbb{Z}^{d}}(1+|m|_{\infty}^{2s})\,\,|\left\langle\varphi_{-m},u \right\rangle|^{2}\leq\left\lVert u\right\rVert_{\mathcal{H}^{s}}^{2}.$ $$

###### Proof.

Fix $m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}$ and let $|m_{j}|=|m|_{\infty}=\max_{1\leq i\leq d}|m_{i}|$. Clearly, $m_{j}\neq 0$. Integrating by parts $s$ times with respect to variable $x_{j}$ in $x=(x_{1},\ldots,x_{d})$, we obtain

$$ $\left\langle\varphi_{-m},u\right\rangle=\int_{\mathbb{T}^{d}}\,u(x)e^{-2\pi \operatorname{i}\left\langle m,x\right\rangle}\,dx=(-1)^{s}\,\int_{\mathbb{T}^ {d}}\,(\partial^{s}_{j}u)(x)\frac{e^{-2\pi\operatorname{i}\left\langle m,x \right\rangle}}{(-2\pi\operatorname{i}\,m_{j})^{s}}\,dx=\left(\frac{1}{2\pi \operatorname{i}m_{j}}\right)^{s}\left\langle\varphi_{-m},\partial_{j}^{s}\,u \right\rangle.$ $$

Here, all boundary terms vanish because $\mathbb{T}^{d}$ does not have a boundary ([Grafakos et al., , Proof of Theorem 3.3.9]). Taking absolute value on both sides, we obtain that

$$ $|m_{j}|^{s}\,|\left\langle\varphi_{-m},u\right\rangle|=(2\pi)^{-s}\,|\left \langle\varphi_{-m},\partial^{s}_{j}u\right\rangle|$ $$

Noting that $|m_{j}|=|m|_{\infty}$, squaring and summing over all $m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}$ to get

$$ $\sum_{m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}|m|_{\infty}^{2s}\,|\left\langle \varphi_{-m},u\right\rangle|^{2}=(2\pi)^{-2s}\sum_{m\in\mathbb{Z}^{d} \backslash\{\bf{0}\}}\,|\left\langle\varphi_{-m},\partial^{s}_{j}u\right \rangle|^{2}\leq(2\pi)^{-2s}\,\left\lVert\partial^{s}_{j}u\right\rVert_{L^{2}} ^{2},$ $$

where the final inequality uses Parseval’s identity and the fact that $\partial^{s}_{j}u\in L^{2}(\mathbb{T}^{d},\mathbb{R})$.
Thus, we obtain

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}}(1+|m|_{\infty}^{2s})\,\,|\left\langle \varphi_{-m},u\right\rangle|^{2}&=\sum_{m\in\mathbb{Z}^{d}}|\left\langle \varphi_{-m},u\right\rangle|^{2}+\sum_{m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}} |m|_{\infty}^{2s}\,|\left\langle\varphi_{-m},u\right\rangle|^{2}\\ &\leq\left\lVert u\right\rVert_{L^{2}}^{2}+(2\pi)^{-2s}\,\left\lVert\partial^{ s}_{j}u\right\rVert_{L^{2}}^{2}\\ &\leq\left\lVert u\right\rVert_{L^{2}}^{2}+\left\lVert\partial^{s}_{j}u\right \rVert_{L^{2}}^{2}\\ &\leq\left\lVert u\right\rVert_{\mathcal{H}^{s}}^{2},\end{split}$ $$

completing our proof.
∎

###### Lemma 3 .

For any $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ such that $s\geq 0$ and $K\in\mathbb{Z}_{>0}$, we have

$$ $\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\left\langle\varphi_{-m},u\right\rangle|^{2} \leq\frac{\left\lVert u\right\rVert_{\mathcal{H}^{s}}^{2}}{K^{2s}}$ $$

###### Proof.

Observe that

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\left\langle\varphi_{-m},u\right \rangle|^{2}&=\sum_{m\in\mathbb{Z}^{d}_{>K}}\,(1+|m|_{\infty}^{2s})\,|\left \langle\varphi_{-m},u\right\rangle|^{2}\,\frac{1}{(1+|m|_{\infty}^{2s})}\\ &\leq\frac{1}{1+K^{2s}}\,\sum_{m\in\mathbb{Z}^{d}_{>K}}\,(1+|m|_{\infty}^{2s}) \,|\left\langle\varphi_{-m},u\right\rangle|^{2}\,\\ &\leq\frac{\left\lVert u\right\rVert_{\mathcal{H}^{s}}^{2}}{K^{2s}},\end{split}$ $$

using Lemma 2.
∎

###### Lemma 4 .

For any $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ such that $s>d/2$, we have

$$ $\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\left\langle\varphi_{-m},u\right\rangle|\leq \left\lVert u\right\rVert_{\mathcal{H}^{s}}\,\sqrt{\frac{3^{d}}{2s-d}}\,\frac{ 1}{\sqrt{K^{2s-d}}},.$ $$

###### Proof.

First, we use Cauchy-Schwarz to get

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\left\langle\varphi_{-m},u\right \rangle|&=\sqrt{\sum_{m\in\mathbb{Z}^{d}_{>K}}\,(1+|m|_{\infty}^{2s})|\left \langle\varphi_{-m},u\right\rangle|^{2}}\,\,\sqrt{\sum_{m\in\mathbb{Z}^{d}_{>K }}\frac{1}{(1+|m|_{\infty}^{2s})}}\end{split}$ $$

Lemma 3 implies that the first term is $\leq\left\lVert u\right\rVert_{\mathcal{H}^{s}}$.
To bound the second term, note that for any $j\in\mathbb{N}$, we have $|\{m\in\mathbb{Z}^{d}\,:\,|m|_{\infty}=j\}|=2(2j+1)^{d-1}$. This is because one of the entry of $m$ has to be $\pm j$ and other $d-1$ entries could be anything in $\{-j\ldots,-1,0,1,\ldots,j\}$. So,

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{>K}}\frac{1}{(1+|m|_{\infty}^{2s})}&= \sum_{j>K}\frac{2\,(2j+1)^{d-1}}{(1+j^{2s})}\leq 3^{d}\sum_{j>K}\frac{1}{j^{2s -d+1}}\leq 3^{d}\int_{K}^{\infty}t^{-2s+d-1}\,dt=\frac{3^{d}}{2s-d}\,\frac{1}{ K^{2s-d}},\end{split}$ $$

for all $s>d/2$. Thus, overall, we obtain

$$ $\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\left\langle\varphi_{-m},u\right\rangle|\leq \left\lVert u\right\rVert_{\mathcal{H}^{s}}\,\sqrt{\frac{3^{d}}{2s-d}}\,\frac{ 1}{\sqrt{K^{2s-d}}},$ $$

completing our proof.
∎

###### Lemma 5 .

Let $\operatorname{G}:=\left\{j/N:j\in\{0,\ldots,N-1\}^{d}\right\}$ be the $N$-uniform grid of $[0,1]^{d}$. Then, for any $m\in\mathbb{Z}^{d}_{<N}$, we have

$$ $\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}e^{2\pi\operatorname{i}\left\langle k -m,x\right\rangle}=\mathbbm{1}[k\equiv m\,(\text{\emph{mod} }N)].$ $$

Here, we say $k\equiv m(\text{mod }N)$ if $\exists\ell\in\mathbb{Z}^{d}$ such that $k=N\ell+m$.

###### Proof.

We first prove it for $d=1$. For this case, we need to show that

$$ $\frac{1}{N}\sum_{j=0}^{N-1}e^{2\pi\operatorname{i}(k-m)\frac{j}{N}}=\mathbbm{1 }[k\equiv m(\text{mod }N)].$ $$

First, consider the case where $k=\tau N+m$ for some $\tau\in\mathbb{Z}$. Then, $e^{2\pi\operatorname{i}(k-m)\frac{j}{N}}=e^{2\pi\operatorname{i}\tau\,j}=1$ by Euler’s identity. Thus, the overall sum must be $1$. Next, assume that $k\not\equiv m$ (mod $N)$. Then, the geometric series formula implies that

$$ $\frac{1}{N}\sum_{j=0}^{N-1}e^{2\pi\operatorname{i}(k-m)\frac{j}{N}}=\frac{1}{N }\,\,\frac{1-e^{2\pi\operatorname{i}(k-m)j}}{1-e^{2\pi\operatorname{i}(k-m) \frac{j}{N}}}=0.$ $$

Here, the final equality holds because $e^{2\pi\operatorname{i}(k-m)j}=1$ by Euler’s identity, whereas $e^{2\pi\operatorname{i}(k-m)\frac{j}{N}}\neq 1$ for every $j\in\{0,1\,\ldots,N-1\}$. Next, to prove it for general $d$, we write the sum as $d$-fold summation

$$ $\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}e^{2\pi\operatorname{i}\left\langle k -m,x\right\rangle}=\frac{1}{N^{d}}\sum_{j_{1}=0}^{N-1}\ldots\sum_{j_{d}=0}^{N- 1}e^{2\pi\operatorname{i}(k_{1}-m_{1})\frac{j_{1}}{N}}\ldots e^{2\pi \operatorname{i}(k_{d}-m_{d})\frac{j_{d}}{N}}=\prod_{t=1}^{d}\frac{1}{N}\sum_{ j_{t}=0}^{N-1}e^{2\pi\operatorname{i}(k_{t}-m_{t})\frac{j_{t}}{N}}.$ $$

Using the result of $d=1$ case for each term in the product, we have

$$ $\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}e^{2\pi\operatorname{i}\left\langle k -m,x\right\rangle}=\prod_{t=1}^{d}\,\mathbbm{1}[k_{t}\equiv m_{t}\,\text{(mod $N$)}]=\mathbbm{1}[k\equiv m\,\,(\text{mod}\,N)].$ $$

∎

###### Lemma 6 .

Let $u\in\mathcal{H}^{s}(\mathbb{T}^{d},\mathbb{R})$ such that $\left\lVert u\right\rVert_{\mathcal{H}^{s}}\leq B$ and $u^{N}:=\{u(x)\,:x\in\operatorname{G}\}$ be its values on the uniform grid $G$. Then, for all $|m|_{\infty}<N$, we have

$$ $|\operatorname{DFT}(u^{N})(-m)-\left\langle\varphi_{-m},u\right\rangle|\,\, \leq\,\,\left|\sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\left\langle \varphi_{-(\ell N+m)},u\right\rangle\right|.$ $$

###### Proof.

Recall that

$$ $\operatorname{DFT}(u^{N})(-m)=\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}\,u(x) \,e^{-2\pi\operatorname{i}\left\langle m,x\right\rangle}.$ $$

Pick some $M>N$ and write

$$ $u(x)=\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle \,e^{2\pi\operatorname{i}\left\langle k,x\right\rangle}+\left(u(x)-\sum_{k\in \mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle\,e^{2\pi \operatorname{i}\left\langle k,x\right\rangle}\right).$ $$

We can then write

$$ $\begin{split}\operatorname{DFT}&(u^{N})(-m)\\ &=\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}\,\left(\sum_{k\in\mathbb{Z}^{d}_{ \leq M}}\left\langle\varphi_{-k},u\right\rangle\,e^{2\pi\operatorname{i}\left \langle k,x\right\rangle}+\left(u(x)-\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left \langle\varphi_{-k},u\right\rangle\,e^{2\pi\operatorname{i}\left\langle k,x \right\rangle}\right)\right)\,e^{-2\pi\operatorname{i}\left\langle m,x\right \rangle}\\ &=\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle\, \left(\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}\,e^{2\pi\operatorname{i}\left \langle k-m,x\right\rangle}\right)+\frac{1}{N^{d}}\sum_{x\in\operatorname{G}} \left(u(x)-\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right \rangle\,e^{2\pi\operatorname{i}\left\langle k,x\right\rangle}\right)\,e^{-2 \pi\operatorname{i}\left\langle m,x\right\rangle}\\ &=\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle\, \mathbbm{1}[k\equiv m(\text{mod }N)]+\frac{1}{N^{d}}\sum_{x\in\operatorname{G} }\left(u(x)-\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right \rangle\,e^{2\pi\operatorname{i}\left\langle k,x\right\rangle}\right)\,e^{-2 \pi\operatorname{i}\left\langle m,x\right\rangle},\end{split}$ $$

where the final equality follows from Lemma 5 as $|m|_{\infty}<N$. Note that we can swap sums over $\operatorname{G}$ and $\mathbb{Z}^{d}$ in the first term because the sums converge absolutely when $s>d/2$ (see Lemma 4). Thus, we obtain

$$ $\begin{split}|\operatorname{DFT}(u^{N})(-m)-\left\langle\varphi_{-m},u\right \rangle|\leq\Bigg{|}\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k} ,u\right\rangle\,&\mathbbm{1}[k\equiv m(\text{mod }N)]-\left\langle\varphi_{-m },u\right\rangle\Bigg{|}\\ &+\left|\frac{1}{N^{d}}\sum_{x\in\operatorname{G}}\left(u(x)-\sum_{k\in\mathbb {Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle\,e^{2\pi\operatorname {i}\left\langle k,x\right\rangle}\right)\,e^{-2\pi\operatorname{i}\left\langle m ,x\right\rangle}\right|\\ \end{split}$ $$

Using the uniform bound over $x\in\operatorname{G}$ for the second term and the following identity for the first term

$$ $\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left\langle\varphi_{-k},u\right\rangle\, \mathbbm{1}[k\equiv m(\text{mod }N)]-\left\langle\varphi_{-m},u\right\rangle= \sum_{k\in\mathbb{Z}^{d}_{\leq M}\backslash\{m\}}\left\langle\varphi_{-k},u \right\rangle\,\mathbbm{1}[k\equiv m(\text{mod }N)],$ $$

we obtain

$$ $\begin{split}|\operatorname{DFT}(u^{N})(-m)&-\left\langle\varphi_{-m},u\right \rangle|\\ &\leq\left|\sum_{k\in\mathbb{Z}^{d}_{\leq M}\backslash\{m\}}\left\langle \varphi_{-k},u\right\rangle\,\mathbbm{1}[k\equiv m(\text{mod }N)]\right|+\sup_ {x\in\operatorname{G}}\,\,\left|u(x)-\sum_{k\in\mathbb{Z}^{d}_{\leq M}}\left \langle\varphi_{-k},u\right\rangle\,e^{2\pi\operatorname{i}\left\langle k,x \right\rangle}\right|\end{split}$ $$

Recall that we have (i) $|\left\langle\varphi_{-k},u\right\rangle\,e^{2\pi\operatorname{i}\left\langle k
,x\right\rangle}|\leq B$ and $\sum_{k\in\mathbb{Z}^{d}}\left|\left\langle\varphi_{-k},u\right\rangle\,e^{2
\pi\operatorname{i}\left\langle k,x\right\rangle}\right|<\infty$ for $s>d/2$ using Lemma 4. The Weierstrass M-test implies that the second term converges to 0 0 uniformly over $x\in\mathbb{T}^{d}$ as $M\to\infty$. Thus, we obtain

$$ $\begin{split}\sum_{k\in\mathbb{Z}^{d}_{\leq M}\backslash\{m\}}\left\langle \varphi_{-k},u\right\rangle\,\mathbbm{1}[k\equiv m(\text{mod }N)]&\xrightarrow [M\to\infty]{}\sum_{k\in\mathbb{Z}^{d}\backslash\{m\}}\left\langle\varphi_{-k} ,u\right\rangle\,\mathbbm{1}[k\equiv m(\text{mod }N)]\\ &=\sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\left\langle\varphi_{-(\ell N +m)},u\right\rangle,\end{split}$ $$

which completes our proof.

###### Lemma 7 .

For any $s\in\mathbb{N}$ such that $s>d/2$, we have

$$ $\sum_{k\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\frac{1}{|k|_{\infty}^{2s}}\leq \pi^{2}\,3^{d-2}.$ $$

###### Proof.

Recall that $|\{m\in\mathbb{Z}^{d}\,:\,|m|_{\infty}=j\}|=2(2j+1)^{d-1}$. This is because one of the entry of $m$ has to be $\pm j$ and other $d-1$ entries could be anything in $\{-j\ldots,-1,0,1,\ldots,j\}$. Thus,

$$ $\sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\frac{1}{|\ell|_{\infty}^{2s}} \leq\sum_{j=1}^{\infty}\frac{2(2j+1)^{d-1}}{j^{2s}}\leq 2\cdot 3^{d-1}\sum_{j= 1}^{\infty}\frac{1}{j^{2s-d+1}}\leq 2\cdot 3^{d-1}\sum_{j=1}^{\infty}\frac{1}{ j^{2}}=\frac{2\cdot 3^{d-1}\pi^{2}}{6}=\pi^{2}\,3^{d-2}.$ $$

The third inequality uses $2s-d\leq 1$ as $s>d/2$ and $s\in\mathbb{N}$.
∎

∎

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Lemma 4 .

###### Proof.

###### Lemma 5 .

###### Proof.

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof.

## Appendix C Proof of Upper Bounds (Theorem 1 )

Before we prove Theorem 1, we need some notation. For any $T\in\mathcal{T}$ such that $T=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\varphi_{m}\otimes\varphi_{-m}$, we define

$$ $\begin{split}r(T)&:=\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\left\lVert Tv -w\right\rVert_{L^{2}}^{2}\right]=\operatorname*{\mathbb{E}}_{(v,w)\sim\mu} \left[\sum_{m\in\mathbb{Z}^{d}}\left|\lambda_{m}\left\langle\varphi_{-m},v \right\rangle-\left\langle\varphi_{-m},w\right\rangle\right|^{2}\right]\\ \widehat{r}(T)&:=\frac{1}{n}\sum_{i=1}^{n}\left\lVert Tv_{i}-w_{i}\right\rVert _{L^{2}}^{2}=\frac{1}{n}\sum_{i=1}^{n}\sum_{m\in\mathbb{Z}^{d}}\left|\lambda_{ m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle\varphi_{-m},w_{i} \right\rangle\right|^{2}\end{split}$ $$

where $\{(v_{i},w_{i})\}_{i=1}^{n}$ is the sample accessible to the learner on a uniform grid of $[0,1]^{d}$.
Then, using these definitions, we can write

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)=\operatorname*{\mathbb{E} }\left[r(\widehat{T}_{K}^{N})-\inf_{T\in\mathcal{T}}r(T)\right]=\operatorname* {\mathbb{E}}\left[r(\widehat{T}_{K}^{N})-\inf_{T\in\mathcal{T}_{K}}r(T)\right] +\inf_{T\in\mathcal{T}_{K}}r(T)-\inf_{T\in\mathcal{T}}\,r(T),$ $$

where $\mathcal{T}_{K}$ is the truncated class defined as

$$ $\mathcal{T}_{K}:=\left\{\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\,\lambda_{m}\,\, \varphi_{m}\otimes\varphi_{-m}\,\Big{|}\,\sup_{m\in\mathbb{Z}^{d}_{\leq K}}| \lambda_{m}|\leq C\right\}.$ $$

Furthermore, defining

$$ $\widehat{T}_{K}\in\operatorname*{arg\,min}_{T\in\mathcal{T}_{K}}\,\widehat{r}( T),$ $$

we can decompose

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)=\underbrace{\operatorname *{\mathbb{E}}\left[r(\widehat{T}_{K}^{N})-r(\widehat{T}_{K})\right]}_{\text{(I )}}+\underbrace{\operatorname*{\mathbb{E}}\left[r(\widehat{T}_{K})-\inf_{T\in \mathcal{T}_{K}}r(T)\right]}_{\text{(II)}}+\underbrace{\inf_{T\in\mathcal{T}_{ K}}r(T)-\inf_{T\in\mathcal{T}}\,r(T)}_{\text{(III)}}.$ $$

First, it is easy to see that

$$ $\text{(III)}\leq\sup_{T\in\mathcal{T}}\,\,\inf_{T_{K}\in\mathcal{T}_{K}}|r(T)- r(T_{K})|.$ $$

To upperbound (II), let $T^{\star}_{K}\in\mathcal{T}_{K}$ such that $r(T^{\star}_{K})=\inf_{T\in\mathcal{T}_{K}}r(T)$. Formally, for every $\varepsilon>0$, we may only be guaranteed the existence of $T^{\star}_{K}$ such that $r(T^{\star}_{K})\leq\inf_{T\in\mathcal{T}_{K}}r(T)+\varepsilon$. However, as $\varepsilon$ can be made arbitrarily small, we can just choose it to be smaller than any error bound we obtain at the end. So, the arguments below are rigorously justified.

Given such $T_{K}^{\star}$, we can write

$$ $\text{(II)}=\operatorname*{\mathbb{E}}[r(\widehat{T}_{K})-r(T_{K}^{\star})]= \operatorname*{\mathbb{E}}[r(\widehat{T}_{K})-\widehat{r}(\widehat{T}_{K})]+ \operatorname*{\mathbb{E}}[\widehat{r}(\widehat{T}_{K})-\widehat{r}(T_{K}^{ \star})]+\operatorname*{\mathbb{E}}[\widehat{r}(T_{K}^{\star})-r(T_{K}^{\star} )].$ $$

The last term of the sum vanishes because $\operatorname*{\mathbb{E}}[\widehat{r}(T_{K}^{\star})]=r(T_{K}^{\star})$. As for the second term, $\widehat{T}_{K}$ minimizes empirical loss over the samples, implying $\widehat{r}(\widehat{T}_{K})\leq\widehat{r}(T_{K}^{\star})$. For the first term, we use the trivial bound $r(\widehat{T}_{K})-\widehat{r}(\widehat{T}_{K})\leq\sup_{T\in\mathcal{T}_{K}}|
r(T)-\widehat{r}(T)|.$
Overall, we obtain

$$ $\text{(II)}\leq\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}_{K}}|r(T) -\widehat{r}(T)|\right].$ $$

Finally, we upper bound the term (I). Given $K$ and $N$, for any $T\in\mathcal{T}_{K}$ such that $T=\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\lambda_{m}\,\varphi_{m}\otimes\varphi_{-m}$, define

$$ $\widehat{r}_{N}(T):=\frac{1}{n}\,\sum_{i=1}^{n}\sum_{\begin{subarray}{c}m\in \mathbb{Z}^{d}_{\leq K}\end{subarray}}\left|\lambda_{m}\operatorname{DFT}(v_{i }^{N})(-m)-\operatorname{DFT}(w_{i}^{N})(-m)\right|^{2}+\frac{1}{n}\,\sum_{i=1 }^{n}\sum_{\begin{subarray}{c}m\in\mathbb{Z}^{d}_{>K}\end{subarray}}|\left \langle\varphi_{-m},w_{i}\right\rangle|^{2}.$ $$

Technically, the term $\widehat{r}_{N}(T)$ also depends on $K$, but we drop $K$ to avoid cluttered notation. Here, the first term above is the empirical DFT-based least squares loss of $T$ define in 4.2. The second term is introduced purely for technical reasons to make our calculations work (see Section C.2). Since the second term does not depend on $T$, our estimator $\widehat{T}_{K}^{N}$ is still the operator obtained by minimizing $\widehat{r}_{N}$. Then, note that

$$ $\text{(I)}=\operatorname*{\mathbb{E}}[r(\widehat{T}_{K}^{N})-\widehat{r}_{N}( \widehat{T}_{K}^{N})]+\operatorname*{\mathbb{E}}[\widehat{r}_{N}(\widehat{T}_{ K}^{N})-\widehat{r}_{N}(\widehat{T}_{K})]\,+\operatorname*{\mathbb{E}}[ \widehat{r}_{N}(\widehat{T}_{K})-r(\widehat{T}_{K})]$ $$

Note that the second term above satisfies $\widehat{r}_{N}(\widehat{T}_{K}^{N})-\widehat{r}_{N}(\widehat{T}_{K})\leq 0$ almost surely because $\widehat{T}_{K}^{N}$ minimizes $\widehat{r}_{N}(T)$ over all $T\in\mathcal{T}_{K}$. For the first and the third term, we use the bound

$$ $\operatorname*{\mathbb{E}}[r(\widehat{T}_{K}^{N})-\widehat{r}_{N}(\widehat{T}_ {K}^{N})]\leq\operatorname*{\mathbb{E}}[\sup_{T\in\mathcal{T}_{K}}|r(T)- \widehat{r}_{N}(T)|]\quad\text{ and }\quad\operatorname*{\mathbb{E}}[\widehat{ r}_{N}(\widehat{T}_{K})-r(\widehat{T}_{K})]\leq\operatorname*{\mathbb{E}}[\sup _{T\in\mathcal{T}_{K}}|r(T)-\widehat{r}_{N}(T)|].$ $$

Thus, we have

$$ $(\text{I})\leq 2\operatorname*{\mathbb{E}}\Big{[}\sup_{T\in\mathcal{T}_{K}}|r( T)-\widehat{r}_{N}(T)|\Big{]}\leq 2\operatorname*{\mathbb{E}}\Big{[}\sup_{T\in \mathcal{T}_{K}}|r(T)-\widehat{r}(T)|\Big{]}+2\operatorname*{\mathbb{E}}\Big{[ }\sup_{T\in\mathcal{T}_{K}}|\widehat{r}(T)-\widehat{r}_{N}(T)|\Big{]},$ $$

where the final step uses the triangle inequality. Combining everything, we have established that

$$ $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu)\leq 3\operatorname*{ \mathbb{E}}\Big{[}\sup_{T\in\mathcal{T}_{K}}|r(T)-\widehat{r}(T)|\Big{]}+2 \operatorname*{\mathbb{E}}\Big{[}\sup_{T\in\mathcal{T}_{K}}|\widehat{r}(T)- \widehat{r}_{N}(T)|\Big{]}+\,\,\sup_{T\in\mathcal{T}}\,\,\inf_{T_{K}\in \mathcal{T}_{K}}|r(T)-r(T_{K})|.$ $$

The first term is the statistical error, the second is the discretization error, and the final is the truncation error. Next, we bound each of these terms individually.

### C.1 Upperbound on the truncation error sup T ∈ 𝒯 inf T K ∈ 𝒯 K | r ⁢ ( T ) − r ⁢ ( T K ) | subscript supremum 𝑇 𝒯 subscript infimum subscript 𝑇 𝐾 subscript 𝒯 𝐾 𝑟 𝑇 𝑟 subscript 𝑇 𝐾 \sup_{T\in\mathcal{T}}\,\inf_{T_{K}\in\mathcal{T}_{K}}|r(T)-r(T_{K})| roman_sup start_POSTSUBSCRIPT italic_T ∈ caligraphic_T end_POSTSUBSCRIPT roman_inf start_POSTSUBSCRIPT italic_T start_POSTSUBSCRIPT italic_K end_POSTSUBSCRIPT ∈ caligraphic_T start_POSTSUBSCRIPT italic_K end_POSTSUBSCRIPT end_POSTSUBSCRIPT | italic_r ( italic_T ) - italic_r ( italic_T start_POSTSUBSCRIPT italic_K end_POSTSUBSCRIPT ) |

Pick any $T\in\mathcal{T}$. Then, there exists a sequence $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}}$ such that $T=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\,\varphi_{m}\otimes\varphi_{-m}$. Define

$$ $T_{K}:=\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\lambda_{m}\,\varphi_{m}\otimes \varphi_{-m}.$ $$

Clearly, $T_{K}\in\mathcal{T}_{K}$.
Then, we have

$$ $\begin{split}r(T)-r(T_{K})&=\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\,[\left \lVert Tv-w\right\rVert_{L^{2}}^{2}-\left\lVert T_{K}v-w\right\rVert_{L^{2}}^{ 2}]\\ &=\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\,[\left\lVert Tv\right\rVert_{L^{2 }}^{2}-\left\lVert T_{K}v\right\rVert_{L^{2}}^{2}+2\left\langle(T_{K}-T)v,w \right\rangle]\\ &\leq\operatorname*{\mathbb{E}}_{(v,w)\sim\mu}\left[\sum_{m\in\mathbb{Z}^{d}_{ >K}}\,|\lambda_{m}|^{2}|\left\langle\varphi_{-m},v\right\rangle|^{2}+2\sum_{m \in\mathbb{Z}^{d}_{>K}}\Big{|}\lambda_{m}\left\langle\varphi_{-m},v\right \rangle\left\langle\varphi_{m},w\right\rangle\Big{|}\right]\\ \end{split}$ $$

The final equality uses the following facts. First, we have $\left\lVert Tv\right\rVert_{L^{2}}^{2}=\left\lVert\sum_{m\in\mathbb{Z}^{d}}\,
\lambda_{m}\left\langle\varphi_{-m},v\right\rangle\varphi_{m}\right\rVert^{2}_
{L^{2}}=\sum_{m\in\mathbb{Z}^{d}}|\lambda_{m}|^{2}|\left\langle\varphi_{-m},v
\right\rangle|^{2}$. Analogously, $\left\lVert T_{K}v\right\rVert_{L^{2}}^{2}=\sum_{m\in\mathbb{Z}^{d}_{\leq K}}|
\lambda_{m}|^{2}|\left\langle\varphi_{-m},v\right\rangle|^{2}$. As for the second term, we use

$$ $\left\langle(T_{K}-T)v,w\right\rangle=\left\langle\sum_{m\in\mathbb{Z}^{d}_{>K }}\lambda_{m}\left\langle\varphi_{-m},v\right\rangle\varphi_{m},w\right\rangle =\sum_{m\in\mathbb{Z}^{d}_{>K}}\lambda_{m}\left\langle\varphi_{-m},v\right \rangle\left\langle\varphi_{m},w\right\rangle.$ $$

Next, using the fact that $|\lambda_{m}|\leq C$ followed by Lemma 3, the first term is

$$ $\sum_{m\in\mathbb{Z}^{d}_{>K}}\,|\lambda_{m}|^{2}|\left\langle\varphi_{-m},v \right\rangle|^{2}\leq\frac{B^{2}C^{2}}{K^{2s}}.$ $$

As for the second term, using $|\lambda_{m}|\leq C$ followed by Cauchy-Schwarz implies

$$ $2\sum_{m\in\mathbb{Z}^{d}_{>K}}|\lambda_{m}\left\langle\varphi_{-m},v\right \rangle\left\langle\varphi_{m},w\right\rangle|\leq 2C\sqrt{\sum_{m\in\mathbb{Z }^{d}_{>K}}|\left\langle\varphi_{-m},v\right\rangle|^{2}}\sqrt{\sum_{m\in \mathbb{Z}^{d}_{>K}}|\left\langle\varphi_{m},w\right\rangle|^{2}}\leq\frac{2CB ^{2}}{K^{2s}},$ $$

where the final inequality holds because of Lemma 3. Since $T\in\mathcal{T}$ is arbitrary, we have shown that

$$ $\sup_{T\in\mathcal{T}}\,\inf_{T_{K}\in\mathcal{T}_{K}}|r(T)-r(T_{K})|\leq\frac {B^{2}C(C+2)}{K^{2s}}\leq\frac{B^{2}(C+1)^{2}}{K^{2s}}.$ $$

### C.2 Upperbound on the discretization error 2 ⁢ 𝔼 [ sup T ∈ 𝒯 K | r ^ ⁢ ( T ) − r ^ N ⁢ ( T ) | ] 2 𝔼 subscript supremum 𝑇 subscript 𝒯 𝐾 ^ 𝑟 𝑇 subscript ^ 𝑟 𝑁 𝑇 2\operatorname*{\mathbb{E}}\Big{[}\sup_{T\in\mathcal{T}_{K}}|\widehat{r}(T)-%
\widehat{r}_{N}(T)|\Big{]} 2 blackboard_E [ roman_sup start_POSTSUBSCRIPT italic_T ∈ caligraphic_T start_POSTSUBSCRIPT italic_K end_POSTSUBSCRIPT end_POSTSUBSCRIPT | over^ start_ARG italic_r end_ARG ( italic_T ) - over^ start_ARG italic_r end_ARG start_POSTSUBSCRIPT italic_N end_POSTSUBSCRIPT ( italic_T ) | ]

Fix $T\in\mathcal{T}_{K}$. Then, there exists $\{\lambda_{m}\}_{m\in\mathbb{Z}^{d}_{\leq K}}$ with $|\lambda_{m}|\leq C$ such that $T=\sum_{\mathbb{Z}^{d}_{\leq K}}\,\lambda_{m}\,\varphi_{m}\otimes\varphi_{-m}$. Then, recall that

$$ $\widehat{r}_{N}(T):=\frac{1}{n}\,\sum_{i=1}^{n}\sum_{\begin{subarray}{c}m\in \mathbb{Z}^{d}_{\leq K}\end{subarray}}\left|\lambda_{m}\operatorname{DFT}(v_{i }^{N})(-m)-\operatorname{DFT}(w_{i}^{N})(-m)\right|^{2}+\frac{1}{n}\,\sum_{i=1 }^{n}\sum_{\begin{subarray}{c}m\in\mathbb{Z}^{d}_{>K}\end{subarray}}|\left \langle\varphi_{-m},w_{i}\right\rangle|^{2}.$ $$

Moreover, we also have

$$ $\widehat{r}(T)=\frac{1}{n}\sum_{i=1}^{n}\sum_{m\in\mathbb{Z}^{d}_{\leq K}} \left|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle \varphi_{-m},w_{i}\right\rangle\right|^{2}+\frac{1}{n}\,\sum_{i=1}^{n}\sum_{ \begin{subarray}{c}m\in\mathbb{Z}^{d}_{>K}\end{subarray}}|\left\langle\varphi_ {-m},w_{i}\right\rangle|^{2},$ $$

which yields

$$ $\widehat{r}_{N}(T)-\widehat{r}(T)=\frac{1}{n}\sum_{i=1}^{n}\sum_{m\in\mathbb{Z }_{\leq K}^{d}}\left(\left|\lambda_{m}\operatorname{DFT}(v_{i}^{N})(-m)- \operatorname{DFT}(w_{i}^{N})(-m)\right|^{2}-\left|\lambda_{m}\left\langle \varphi_{-m},v_{i}\right\rangle-\left\langle\varphi_{-m},w_{i}\right\rangle \right|^{2}\right).$ $$

Next, we define

$$ $\begin{split}\alpha_{im}=\operatorname{DFT}(v_{i}^{N})(-m)-\left\langle\varphi _{-m},v_{i}\right\rangle\quad\text{ and }\quad\beta_{im}=\operatorname{DFT}(w_ {i}^{N})(-m)-\left\langle\varphi_{-m},w_{i}\right\rangle.\end{split}$ $$

We can then write

$$ $\begin{split}&\left|\lambda_{m}\operatorname{DFT}(v_{i}^{N})(-m)-\operatorname {DFT}(w_{i}^{N})(-m)\right|^{2}\\ &=|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle\varphi_ {-m},w_{i}\right\rangle+\lambda_{m}\,\alpha_{im}-\beta_{im}|^{2}\\ &\leq|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle \varphi_{-m},w_{i}\right\rangle|^{2}+2|\lambda_{m}\left\langle\varphi_{-m},v_{ i}\right\rangle-\left\langle\varphi_{-m},w_{i}\right\rangle|\,\,|\lambda_{m} \alpha_{im}-\beta_{im}|\,+|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}.\end{split}$ $$

Thus, we obtain

$$ $\begin{split}|\widehat{r}_{N}(T)-\widehat{r}(T)|&\leq\frac{1}{n}\sum_{i=1}^{n} \sum_{m\in\mathbb{Z}^{d}_{\leq K}}\left(2|\lambda_{m}\left\langle\varphi_{-m}, v_{i}\right\rangle-\left\langle\varphi_{-m},w_{i}\right\rangle|\,|\lambda_{m} \alpha_{im}-\beta_{im}|\,+|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}\right)\\ &\leq\max_{i\in[n]}\sum_{m\in\mathbb{Z}^{d}_{\leq K}}2\,\left(|\lambda_{m} \left\langle\varphi_{-m},v_{i}\right\rangle|+|\left\langle\varphi_{-m},w_{i} \right\rangle|\right)\,|\lambda_{m}\alpha_{im}-\beta_{im}|\,|+|\lambda_{m} \alpha_{im}-\beta_{im}|^{2}.\end{split}$ $$

Next, using Cauchy-Schwarz inequality, the first term of the summand can be bounded as

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{\leq K}}&\left|\lambda_{m}\left\langle \varphi_{-m},v_{i}\right\rangle|\,\,|\lambda_{m}\alpha_{im}-\beta_{im}\right| \\ &\leq\sqrt{\sum_{m\in\mathbb{Z}^{d}_{\leq K}}|\lambda_{m}|^{2}(1+|m|_{\infty}^ {2s})\,|\left\langle\varphi_{-m},v_{i}\right\rangle|^{2}}\sqrt{\sum_{m\in \mathbb{Z}^{d}_{\leq K}}\frac{|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}}{1+|m|_{ \infty}^{2s}}}\\ &\leq B\,C\sqrt{\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\frac{|\lambda_{m}\alpha_{im }-\beta_{im}|^{2}}{1+|m|_{\infty}^{2s}}},\end{split}$ $$

where the final inequality uses Lemma 3 and the fact that $|\lambda_{m}|\leq C$. Similar arguments show that

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{\leq K}}|\left\langle\varphi_{-m},w_{i} \right\rangle|\,\,|(\lambda_{m}\alpha_{im}-\beta_{im})|\leq B\sqrt{\sum_{m\in \mathbb{Z}^{d}_{\leq K}}\frac{|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}}{1+|m|_{ \infty}^{2s}}}.\end{split}$ $$

Overall, we have shown that

$$ $|\widehat{r}_{N}(T)-\widehat{r}(T)|\leq\max_{i\in[n]}\left(2B(C+1)\sqrt{\sum_{ m\in\mathbb{Z}^{d}_{\leq K}}\frac{|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}}{1+| m|_{\infty}^{2s}}}+\sum_{m\in\mathbb{Z}^{d}_{\leq K}}|\lambda_{m}\alpha_{im}- \beta_{im}|^{2}\right).$ $$

Now, recall that Lemma 6 implies

$$ $\max\{|\alpha_{im}|,|\beta_{im}|\}\leq\left|\sum_{\ell\in\mathbb{Z}^{d} \backslash\{\bf{0}\}}\left\langle\varphi_{-(\ell N+m)},u\right\rangle\right|,$ $$

which subsequently yields

$$ $|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}\leq(C+1)^{2}\,\left|\sum_{\ell\in \mathbb{Z}^{d}\backslash\{\bf{0}\}}\left\langle\varphi_{-(\ell N+m)},u\right \rangle\right|^{2}.$ $$

Thus, we have

$$ $\begin{split}\sum_{m\in\mathbb{Z}^{d}_{\leq K}}&|\lambda_{m}\alpha_{im}-\beta_ {im}|^{2}\\ &\leq(C+1)^{2}\,\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\left|\sum_{\ell\in\mathbb{Z }^{d}\backslash\{\bf{0}\}}\left\langle\varphi_{-(\ell N+m)},u\right\rangle \right|^{2}\\ &\leq(C+1)^{2}\left(\sum_{m\in\mathbb{Z}_{\leq K}^{d}}\,\left(\sum_{\ell\in \mathbb{Z}^{d}\backslash\{\bf{0}\}}\frac{1}{1+|m+\ell N|_{\infty}^{2s}}\right) \sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}(1+|m+\ell N|_{\infty}^{2s})\, |\left\langle\varphi_{-(\ell N+m)},u\right\rangle|^{2}\right).\end{split},$ $$

where the final step follows from Cauchy-Schwarz inequality.

To upperbound the first sum within inner parenthesis, note that $|m+\ell N|_{\infty}\geq|\ell N|_{\infty}-|m|_{\infty}\geq N|\ell|_{\infty}-N/2
\geq N/2\,|\ell|_{\infty}$. Here, we use the fact that $|m|_{\infty}\leq K\leq N/2$. So, we have

$$ $\sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\frac{1}{1+|m+\ell N|_{\infty} ^{2s}}\leq\left(\frac{2}{N}\right)^{2s}\sum_{\ell\in\mathbb{Z}^{d}\backslash\{ \bf{0}\}}\frac{1}{|\ell|_{\infty}^{2s}}\leq\frac{2^{2s}\pi^{2}\,3^{d-2}}{N^{2s }},$ $$

where the final inequality uses Lemma 7.
Next, note that

$$ $\sum_{m\in\mathbb{Z}_{\leq K}^{d}}\sum_{\ell\in\mathbb{Z}^{d}\backslash\{\bf{0 }\}}(1+|m+\ell N|_{\infty}^{2s})\,|\left\langle\varphi_{-(\ell N+m)},u\right \rangle|^{2}\leq\sum_{k\in\mathbb{Z}^{d}}(1+|k|_{\infty}^{2s})\,|\left\langle \varphi_{-k},u\right\rangle|^{2}\leq B^{2},$ $$

where the second inequality follows from Lemma 3.
The first inequality holds because for each $k\in\mathbb{Z}^{d}$, we have $|\{(m,\ell)\,:\,m+\ell N=k,\,m\in\mathbb{Z}^{d}_{\leq K}\text{ and }\ell\in
\mathbb{Z}^{d}\backslash\{0\}\}|\leq 1$. That is, for each $k\in\mathbb{Z}^{d}$, there is only one possible pair $(m,\ell)$ such that $k=m+\ell N$. Suppose, for the sake of contradiction, there exists $k\in\mathbb{Z}^{d}$ such that two distinct pairs exist in the set, namely $(m_{1},\ell_{1})$ and $(m_{2},\ell_{2})$. Note that $m_{1}+\ell_{1}N-(m_{2}+\ell_{2}N)=k-k=0$, which implies $(m_{1}-m_{2})=(\ell_{2}-\ell_{1})N$. Clearly, we cannot have $\ell_{2}=\ell_{1}$, otherwise, we will have $m_{2}=m_{1}$, contradicting the fact that there are two distinct pairs. So, we must have $\ell_{2}\neq\ell_{1}$. That is, $|\ell_{2}-\ell_{1}|_{\infty}\geq 1$, and thus $|m_{1}-m_{2}|_{\infty}\geq N$. Moreover, $|m_{1}-m_{2}|_{\infty}\leq|m_{1}|_{\infty}+|m_{2}|_{\infty}\leq 2K$, which implies that $2K\geq N$. This contradicts the fact that $K<N/2$. Therefore, overall, we have shown that

$$ $\sum_{m\in\mathbb{Z}^{d}_{\leq K}}|\lambda_{m}\alpha_{im}-\beta_{im}|^{2}\leq \frac{2^{2s}\pi^{2}\,3^{d-2}\,B^{2}(C+1)^{2}}{N^{2s}}.$ $$

Next, we have

$$ $\sqrt{\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\frac{|\lambda_{m}\alpha_{im}-\beta_{ im}|^{2}}{1+|m|_{\infty}^{2s}}}\leq\sqrt{\sum_{m\in\mathbb{Z}^{d}_{\leq K}}| \lambda_{m}\alpha_{im}-\beta_{im}|^{2}}\leq\frac{2^{s}\pi\sqrt{3^{d-2}}\,B(C+1 )}{N^{s}}.$ $$

Therefore, by combining everything, we have shown that

$$ $|\widehat{r}_{N}(T)-\widehat{r}(T)|\leq\frac{2^{s+1}B^{2}(C+1)^{2}}{N^{s}}\pi \sqrt{3^{d-2}}+\frac{B^{2}(C+1)^{2}4^{s}}{N^{2s}}\,\pi^{2}3^{d-2}\leq 2\,\frac {2^{s+1}B^{2}(C+1)^{2}}{N^{s}}\pi\sqrt{3^{d-2}}.$ $$

The final inequality holds when $N^{s}\geq 2^{s-1}\,\pi\sqrt{3^{d-2}}$, which is satisfied as long as $N\geq 6$. As $T\in\mathcal{T}_{K}$ is arbitrary, we have shown that the discretization error

$$ $2\operatorname*{\mathbb{E}}\Big{[}\sup_{T\in\mathcal{T}_{K}}|\widehat{r}(T)- \widehat{r}_{N}(T)|\Big{]}\leq\frac{2^{s+3}\pi\sqrt{3^{d-2}}B^{2}(C+1)^{2}}{N^ {s}}\leq\frac{2^{s+3}\sqrt{\pi^{d}}B^{2}(C+1)^{2}}{N^{s}}.$ $$

### C.3 Upperbound on the Statistical Error 3 ⁢ 𝔼 [ sup T ∈ 𝒯 K | r ⁢ ( T ) − r ^ ⁢ ( T ) | ] 3 𝔼 subscript supremum 𝑇 subscript 𝒯 𝐾 𝑟 𝑇 ^ 𝑟 𝑇 3\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}_{K}}|r(T)-\widehat{r}(T%
)|\right] 3 blackboard_E [ roman_sup start_POSTSUBSCRIPT italic_T ∈ caligraphic_T start_POSTSUBSCRIPT italic_K end_POSTSUBSCRIPT end_POSTSUBSCRIPT | italic_r ( italic_T ) - over^ start_ARG italic_r end_ARG ( italic_T ) | ]

In fact, we will bound $\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}}|r(T)-\widehat{r}(T)|\right]$. This can be viewed as the limit of the statistical error as $K\to\infty$. To that end, let $\sigma_{1},\ldots,\sigma_{n}$ denote iid random variables such that $\sigma_{i}\sim\text{Uniform}(\{-1,1\})$. Standard symmetrization arguments show that

$$ $\begin{split}\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}}|r(T)- \widehat{r}(T)|\right]&\leq 2\operatorname*{\mathbb{E}}\left[\sup_{T\in \mathcal{T}}\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\left\lVert Tv_{i}-w_{i} \right\rVert_{L^{2}}^{2}\right|\right]\\ &=2\operatorname*{\mathbb{E}}\left[\,\sup_{|\lambda|_{\ell^{\infty}}\leq C}\, \,\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{m\in\mathbb{Z}^{d}}\left| \lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle\varphi_{-m },w_{i}\right\rangle\right|^{2}\right|\right]\\ \end{split}$ $$

Note that

$$ $\begin{split}&\left|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle- \left\langle\varphi_{-m},w_{i}\right\rangle\right|^{2}\\ &=\left(\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle \varphi_{-m},w_{i}\right\rangle\right)\overline{\left(\lambda_{m}\left\langle \varphi_{-m},v_{i}\right\rangle-\left\langle\varphi_{-m},w_{i}\right\rangle \right)}\\ &=\lambda_{m}\,\overline{\lambda_{m}}\,\left\langle\varphi_{-m},v_{i}\right \rangle\overline{\left\langle\varphi_{-m},v_{i}\right\rangle}-\lambda_{m}\left \langle\varphi_{-m},v_{i}\right\rangle\overline{\left\langle\varphi_{-m},w_{i} \right\rangle}-\overline{\lambda_{m}}\left\langle\varphi_{-m},w_{i}\right \rangle\overline{\left\langle\varphi_{-m},v_{i}\right\rangle}+\left\langle \varphi_{-m},w_{i}\right\rangle\overline{\left\langle\varphi_{-m},w_{i}\right \rangle}\,\\ &=|\lambda_{m}|^{2}\,|\left\langle\varphi_{-m},v_{i}\right\rangle|^{2}-\left( \lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle\overline{\left\langle \varphi_{-m},w_{i}\right\rangle}+\overline{\lambda_{m}}\left\langle\varphi_{-m },w_{i}\right\rangle\overline{\left\langle\varphi_{-m},v_{i}\right\rangle} \right)+\,|\left\langle\varphi_{-m},w_{i}\right\rangle|^{2}.\end{split}$ $$

The first and the last term above are real numbers, so the term in the parenthesis must also be a real number. Using triangle inequality, the term Rademacher sum above can be upper-bounded as

$$ $\begin{split}\operatorname*{\mathbb{E}}&\left[\,\sup_{|\lambda|_{\ell^{\infty} }\leq C}\,\,\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{m\in\mathbb{Z}^{d}} \left|\lambda_{m}\left\langle\varphi_{-m},v_{i}\right\rangle-\left\langle \varphi_{-m},w_{i}\right\rangle\right|^{2}\right|\right]\\ &\leq\underbrace{\operatorname*{\mathbb{E}}\left[\,\sup_{|\lambda|_{\ell^{ \infty}}\leq C}\,\,\left|\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{m\in\mathbb{ Z}^{d}}|\lambda_{m}|^{2}\,|\left\langle\varphi_{-m},v_{i}\right\rangle|^{2} \right|\right]}_{\text{(i)}}+\underbrace{\operatorname*{\mathbb{E}}\left[\, \sup_{|\lambda|_{\ell^{\infty}}\leq C}\,\,\Bigg{|}\frac{1}{n}\sum_{i=1}^{n} \sigma_{i}\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\left\langle\varphi_{-m},v_{i} \right\rangle\overline{\left\langle\varphi_{-m},w_{i}\right\rangle}\Bigg{|} \right]}_{\text{(ii)}}\\ &+\underbrace{\operatorname*{\mathbb{E}}\left[\,\sup_{|\lambda|_{\ell^{\infty} }\leq C}\,\,\Bigg{|}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{m\in\mathbb{Z}^{d }}\overline{\lambda_{m}}\left\langle\varphi_{-m},w_{i}\right\rangle\overline{ \left\langle\varphi_{-m},v_{i}\right\rangle}\Bigg{|}\right]}_{\text{(iii)}}+ \underbrace{\operatorname*{\mathbb{E}}\left[\Bigg{|}\frac{1}{n}\sum_{i=1}^{n} \sigma_{i}\sum_{m\in\mathbb{Z}^{d}}|\left\langle\varphi_{-m},w_{i}\right \rangle|^{2}\Bigg{|}\right]}_{\text{(iv)}}.\end{split}$ $$

Let us start with the term (iv) first. Swapping the sum over $m$ and $i$ and using triangle inequality yields

$$ $\begin{split}\text{(iv)}=\operatorname*{\mathbb{E}}\left[\Bigg{|}\frac{1}{n} \sum_{i=1}^{n}\sigma_{i}\sum_{m\in\mathbb{Z}^{d}}|\left\langle\varphi_{-m},w_{ i}\right\rangle|^{2}\Bigg{|}\right]&\leq\sum_{m\in\mathbb{Z}^{d}}\frac{1}{n} \operatorname*{\mathbb{E}}\left[\left|\sum_{i=1}^{n}\sigma_{i}\,|\left\langle \varphi_{-m},w_{i}\right\rangle|^{2}\right|\right]\\ &\leq\sum_{m\in\mathbb{Z}^{d}}\frac{1}{n}\left(\sum_{i=1}^{n}|\left\langle \varphi_{-m},w_{i}\right\rangle|^{4}\right)^{1/2},\end{split}$ $$

where the final step follows from Khintchine’s inequality. Note that swapping the sums is justified because both sums converge absolutely.

For the term (iii), swapping the sum over $m$ and $i$ and using the fact that $|\lambda_{m}|\leq C$ yields

$$ $\begin{split}\text{(iii)}=\operatorname*{\mathbb{E}}&\left[\,\sup_{|\lambda|_{ \ell^{\infty}}\leq C}\,\,\Bigg{|}\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}\sum_{m\in \mathbb{Z}^{d}}\overline{\lambda_{m}}\left\langle\varphi_{-m},w_{i}\right \rangle\overline{\left\langle\varphi_{-m},v_{i}\right\rangle}\Bigg{|}\right]\\ &=\operatorname*{\mathbb{E}}\left[\,\sup_{|\lambda|_{\ell^{\infty}}\leq C}\,\, \Bigg{|}\frac{1}{n}\sum_{m\in\mathbb{Z}^{d}}\overline{\lambda_{m}}\,\sum_{i=1} ^{n}\sigma_{i}\left\langle\varphi_{-m},w_{i}\right\rangle\overline{\left \langle\varphi_{-m},v_{i}\right\rangle}\,\Bigg{|}\right]\\ &\leq C\operatorname*{\mathbb{E}}\left[\sum_{m\in\mathbb{Z}^{d}}\left|\,\frac{ 1}{n}\sum_{i=1}^{n}\sigma_{i}\left\langle\varphi_{-m},w_{i}\right\rangle \overline{\left\langle\varphi_{-m},v_{i}\right\rangle}\,\right|\right]\\ &\leq C\sum_{m\in\mathbb{Z}^{d}}\frac{1}{n}\left(\sum_{i=1}^{n}|\left\langle \varphi_{-m},w_{i}\right\rangle\overline{\left\langle\varphi_{-m},v_{i}\right \rangle}\,|^{2}\right)^{1/2},\end{split}$ $$

where the final step uses Khintchine’s inequality. Since $|\lambda_{m}|\leq C$, we can use the same arguments to show that

$$ $\text{(ii)}\leq C\sum_{m\in\mathbb{Z}^{d}}\frac{1}{n}\left(\sum_{i=1}^{n}| \left\langle\varphi_{-m},v_{i}\right\rangle\overline{\left\langle\varphi_{-m}, w_{i}\right\rangle}\,|^{2}\right)^{1/2},$ $$

and

$$ $\text{(i)}\leq C^{2}\sum_{m\in\mathbb{Z}^{d}}\frac{1}{n}\left(\sum_{i=1}^{n}| \left\langle\varphi_{-m},v_{i}\right\rangle|^{4}\right)^{1/2}.$ $$

Next, note that we can bound $|\left\langle\varphi_{0},u\right\rangle|\leq B$ for all $\left\lVert u\right\rVert_{\mathcal{H}^{s}}\leq B$. Moreover, Lemma 1 implies that $|\left\langle\varphi_{-m},u\right\rangle|\leq\frac{B}{(2\pi)^{s}\,|m|_{\infty}
^{s}}$ for all $m\neq\bf{0}$. Thus, we obtain the bound

$$ $\begin{split}\text{(i)}&\leq\frac{B^{2}C^{2}}{\sqrt{n}}+C^{2}\sum_{m\in\mathbb {Z}^{d}\backslash\{\bf{0}\}}\,\frac{1}{n}\left(\sum_{i=1}^{n}\frac{B^{4}}{(2 \pi)^{4s}}\,\,\frac{1}{|m|_{\infty}^{4s}}\right)^{1/2}\\ &\leq B^{2}C^{2}\frac{1}{\sqrt{n}}+\frac{B^{2}C^{2}}{(2\pi)^{2s}}\,\frac{1}{ \sqrt{n}}\sum_{m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}}\frac{1}{|m|_{\infty}^{2 s}}\\ &\leq B^{2}C^{2}\frac{1}{\sqrt{n}}+\frac{B^{2}C^{2}\pi^{2}3^{d-2}}{(2\pi)^{2s} }\frac{1}{\sqrt{n}},\end{split}$ $$

where the final inequality uses Lemma 7.
Similar calculations can be done to show that

$$ $\text{(ii)},\text{(iii)}\leq B^{2}C\frac{1}{\sqrt{n}}+\frac{B^{2}C\pi^{2}\,3^{ d-2}}{(2\pi)^{2s}}\,\,\frac{1}{\sqrt{n}}\quad\text{ and }\quad\text{(iv)}\leq B ^{2}\frac{1}{\sqrt{n}}+\frac{B^{2}\pi^{2}3^{d-2}}{(2\pi)^{2s}}\frac{1}{\sqrt{n }}.$ $$

Thus, we have overall shown that

$$ $\begin{split}\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}}|r(T)- \widehat{r}(T)|\right]&\leq 2\left(\text{(i)}+\text{(ii)}+\text{(iii)}+\text{( iv)}\right)\\ &\leq 2(B^{2}C^{2}+2B^{2}C+B^{2})\left(1+\frac{\pi^{2}3^{d-2}}{(2\pi)^{2s}} \right)\frac{1}{\sqrt{n}}\\ &=\frac{2B^{2}(C+1)^{2}}{\sqrt{n}}\,\left(1+\frac{\pi^{2}3^{d-2}}{(2\pi)^{2s}} \right)\\ &\leq\frac{5}{2}\,\frac{B^{2}(C+1)^{2}}{\sqrt{n}}\end{split}$ $$

where we use the fact that

$$ $\frac{\pi^{2}3^{d-2}}{(2\pi)^{2s}}\leq\frac{1}{2^{2s}}\,\frac{\pi^{d}}{\pi^{2s }}\leq\frac{1}{2^{2s}}\leq\frac{1}{4}$ $$

as $2s>d$ and $s\geq 1$. Therefore, the overall statistical error is

$$ $3\operatorname*{\mathbb{E}}\left[\sup_{T\in\mathcal{T}}|r(T)-\widehat{r}(T)| \right]\leq\frac{8B^{2}(C+1)^{2}}{\sqrt{n}}.$ $$

## Appendix D Proof of Lowerbounds (Theorem 2 )

###### Proof.

To define a difficult distribution for the learner, we need some notations.
Let

$$ $\psi_{0}=\varphi_{0}\quad\text{ and }\psi_{m}=\frac{1}{\sqrt{2}}\left(\varphi_ {-m}+\varphi_{m}\right)\quad\text{ for }m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}.$ $$

Note that $\psi_{m}:\mathbb{T}^{d}\to\mathbb{R}$ is a *real-valued* function such that $\left\lVert\psi_{m}\right\rVert_{L^{2}}=1$. We work with $\psi_{m}$’s to ensure that the distribution is only supported over real-valued functions. For any $\{\lambda_{k}\}_{k\in\mathbb{Z}^{d}}$ such that $\lambda_{k}=\lambda_{-k}\in\mathbb{R}$, the operator $T=\sum_{m\in\mathbb{Z}^{d}}\lambda_{m}\varphi_{m}\otimes\varphi_{-m}$ satisfies

$$ $T\psi_{m}=\frac{1}{\sqrt{2}}(\lambda_{m}\,\varphi_{m}+\lambda_{-m}\varphi_{-m} )=\frac{\lambda_{m}}{\sqrt{2}}\left(\varphi_{-m}+\varphi_{m}\right)=\lambda_{m }\psi_{m}\quad\forall m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}.$ $$

Clearly, $T\psi_{0}=\lambda_{0}\psi_{0}$.
Next, let us define a sequence $\{\gamma_{m}\}_{m\in\mathbb{Z}^{d}}$ such that

$$ $\gamma_{0}=\frac{B}{\sqrt{s+1}}\quad\text{ and }\quad\gamma_{m}=\frac{B}{\sqrt {s+1}\,|m|_{\infty}^{s}}\quad\forall m\in\mathbb{Z}^{d}\backslash\{\bf{0}\}.$ $$

Finally, define a set

$$ $\mathcal{J}=\{m\in\mathbb{Z}^{d}\,:\,\,m_{1}\in\mathbb{N}\text{ and }m_{j}=0 \quad\forall j\neq 1\}.$ $$

For any $M,N\in\mathbb{N}$, define $\mathcal{J}_{M}^{N}=\{m\in\mathcal{J}\,:\,m_{1}\not\equiv 0\text{ (mod $N$)
and }m_{1}\leq M\}$. Let $r\in\mathbb{Z}^{d}$ such that $r\in\mathcal{J}$ and $r_{1}=1$. That is, $r=(1,0,0,\ldots,0)$. For any $q\in\mathbb{Z}$, we write $qr=(q,0,0,\ldots,0)$.

We now describe a difficult distribution for the learner. To that end, first draw a $\xi:=\{\xi_{m}\}_{m\in\mathbb{Z}^{d}}$ such that $\xi_{m}=\xi_{-m}$ is drawn from $\text{Uniform}(\{-1,1\})$. Then, given such $\xi$, let $\mu_{\xi}$ be any joint distribution on $\mathcal{V}\times\mathcal{W}$ such that its marginal on $\mathcal{V}$ assigns $1/3$ mass uniformly on $\big{\{}\gamma_{m}\psi_{m}\,:\,m\in\mathcal{J}_{M}^{N}\big{\}},$ $1/3$ mass on $\gamma_{0}\psi_{0}$, and the remaining $1/3$ mass on $\gamma_{(K+j)r}\,\psi_{(K+j)r}$ for either $j=1$ or $j=2$ ensuring that $K+j\not\equiv 0$ (mod $N$). Moreover, given a $v=\gamma_{k}\psi_{k}$ drawn from the marginal of $\mu_{\xi}$, assign $w\mid v$ to be $\xi_{k}\gamma_{k}\psi_{k}$ if $k\neq 0$. On the other hand, if $k=0$, then $w\mid v$ is $\xi_{Nr}\,\gamma_{Nr}\,\psi_{Nr}$.

This is a valid distribution as

$$ $\begin{split}\left\lVert v\right\rVert_{\mathcal{H}^{s}}^{2}=\sum_{k\in\mathbb {N}_{0}^{d}\,:\,|k|_{\infty}\leq s}\left\lVert\partial^{k}v\right\rVert_{L^{2} }^{2}&=\sum_{k\in\mathbb{N}_{0}^{d}\,:\,|k|_{\infty}\leq s}(m_{1}^{k_{1}} \gamma_{m})^{2}\mathbbm{1}[k_{j}=0\,\text{ for all }j\neq 1]\\ &=\gamma_{m}^{2}\sum_{k_{1}=0}^{s}|m|_{\infty}^{2k_{1}}\\ &\leq(s+1)\gamma_{m}^{2}|m|_{\infty}^{2s}\\ &\leq B^{2}\end{split}$ $$

Similar arguments show that $\left\lVert w\right\rVert_{\mathcal{H}^{s}}^{2}\leq B^{2}$.

Next, we establish that

$$ $\operatorname*{\mathbb{E}}_{\xi}\left[\mathcal{E}_{n}(\widehat{T}_{K}^{N}, \mathcal{T},\mu_{\xi})\right]\geq\frac{B^{2}}{3(s+1)}\left(\frac{1}{8n}+\frac{ 2}{(K+2)^{2s}}+\frac{1}{N^{2s}}\right).$ $$

Since the lower bound above holds in expectation, we can use the probabilistic method to argue that there must exist a sequence $\xi^{\star}$ such that $\mathcal{E}_{n}(\widehat{T}_{K}^{N},\mathcal{T},\mu_{\xi^{\star}})\geq\frac{B^
{2}}{3(s+1)}\left(\frac{1}{8n}+\frac{2}{(K+2)^{2s}}+\frac{1}{N^{2s}}\right)$.

We now proceed with the proof of the claimed lowerbound. Let $\widehat{T}_{K}^{N}$ denote the estimator produced by the algorithm. Then, there exists $\{\widehat{\lambda}_{m}\}_{m\in\mathbb{Z}^{d}_{\leq K}}$ such that

$$ $\widehat{T}_{K}^{N}=\sum_{m\in\mathbb{Z}^{d}_{\leq K}}\,\widehat{\lambda}_{m} \,\,\varphi_{m}\otimes\varphi_{-m}.$ $$

For convenience, we will extend the sum to the entire $\mathbb{Z}^{d}$ and write $\widehat{T}_{K}^{N}=\sum_{m\in\mathbb{Z}^{d}}\,\widehat{\lambda}_{m}\,\,
\varphi_{m}\otimes\varphi_{-m}$, where $\widehat{\lambda}_{m}=0$ for all $m\in\mathbb{Z}_{>K}^{d}$.

Given a $\xi$, we now lowerbound the expected loss of $\widehat{T}_{K}^{N}$ on $\mu_{\xi}$. Using the definition of the distribution $\mu_{\xi}$, we have

$$ $\begin{split}&\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}}\left[\lVert \widehat{T}_{K}^{N}v-w\rVert^{2}_{L^{2}}\right]\\ &=\frac{1}{3}\,\frac{1}{|\mathcal{J}_{M}^{N}|}\sum_{m\in\mathcal{J}_{M}^{N}}\, \left(\widehat{\lambda}_{m}-\xi_{m}\right)^{2}\gamma_{m}^{2}+\frac{1}{3}\left \lVert\widehat{\lambda}_{0}\gamma_{0}\psi_{0}-\xi_{Nr}\,\gamma_{Nr}\,\psi_{Nr} \,\right\rVert_{L^{2}}^{2}+\frac{1}{3}\left\lVert 0\,\psi_{(K+j)r}-\gamma_{(K+ j)r}\,\psi_{(K+j)r}\right\rVert^{2}_{L^{2}}\\ &\geq\frac{1}{3|\mathcal{J}_{M}^{N}|}\sum_{m\in\mathcal{J}_{M}^{N}}\,\gamma_{m }^{2}\,\mathbbm{1}[\widehat{\lambda}_{m}\xi_{m}\leq 0]+\frac{\widehat{\lambda} _{0}^{2}\gamma_{0}^{2}+\gamma_{Nr}^{2}}{3}\,+\frac{\gamma_{(K+j)r}^{2}}{3}\\ &\geq\frac{\gamma_{r}^{2}}{3|\mathcal{J}_{M}^{N}|}\,\mathbbm{1}[\widehat{ \lambda}_{r}\xi_{r}\leq 0]+\frac{\widehat{\lambda}_{0}^{2}\gamma_{0}^{2}+ \gamma_{Nr}^{2}}{3}\,+\frac{\gamma_{(K+2)r}^{2}}{3}.\end{split}$ $$

Here, the first inequality use the fact that $(\widehat{\lambda}_{m}-\xi_{m})^{2}\geq 1$ whenever $\widehat{\lambda}_{m}\xi_{m}\leq 0$ and $\left\langle e_{0},e_{Nr}\right\rangle_{L^{2}}=0$.
The second inequality uses the fact that $r\in\mathcal{J}_{M}^{N}$ as long as $M,N>1$ and that $\gamma^{2}_{(K+j)r}\geq\gamma^{2}_{(K+2)r}$ for $j\in\{1,2\}$.

Next, we establish the upper bound on the loss of the best-fixed operator. Given $\xi$, define an operator

$$ $T_{\xi}=\sum_{m\in\mathbb{Z}^{d}_{>0}}\xi_{m}\,\varphi_{m}\otimes\varphi_{-m}.$ $$

Clearly,

$$ $\begin{split}\inf_{T\in\mathcal{T}}&\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{ \xi}}\left[\left\lVert Tv-w\rVert^{2}_{L^{2}}\right\rVert\right]\\ &\leq\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}}\left[\left\lVert T_{\xi}v -w\rVert^{2}_{L^{2}}\right\rVert\right]\\ &=\operatorname*{\mathbb{E}}\left[\left\lVert T_{\xi}v-w\rVert^{2}_{L^{2}} \right\rVert\big{|}v=\gamma_{0}\psi_{0}\right]\mathbb{P}[v=\gamma_{0}\psi_{0}] +\operatorname*{\mathbb{E}}\left[\left\lVert T_{\xi}v-w\rVert^{2}_{L^{2}} \right\rVert\big{|}v\neq\gamma_{0}\psi_{0}\right]\mathbb{P}[v\neq\gamma_{0} \psi_{0}]\\ &\leq\left\lVert 0-\xi_{Nr}\,\gamma_{Nr}\,\psi_{Nr}\right\rVert_{L^{2}}^{2}\, \frac{1}{3}\\ &\leq\frac{\gamma_{Nr}^{2}}{3},\end{split}$ $$

where we use the fact that $T_{\xi}v=0$ whenever $v=\gamma_{0}e_{0}$ and $T_{\xi}v=w$ otherwise. Overall, we have shown that

$$ $\begin{split}\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}}&\left[\lVert \widehat{T}_{K}^{N}v-w\rVert^{2}_{L^{2}}\right]-\inf_{T\in\mathcal{T}} \operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}}\left[\left\lVert Tv-w\rVert^{2 }_{L^{2}}\right\rVert\right]\\ &\geq\frac{\gamma_{r}^{2}}{3|\mathcal{J}_{M}^{N}|}\,\mathbbm{1}[\widehat{ \lambda}_{r}\xi_{r}\leq 0]+\frac{\widehat{\lambda}_{0}^{2}\gamma_{0}^{2}+ \gamma_{Nr}^{2}}{3}\,+\frac{\gamma_{t}^{2}}{3}-\frac{\gamma_{Nr}^{2}}{3}\\ &\geq\frac{1}{3(s+1)}\left(\frac{\mathbbm{1}[\widehat{\lambda}_{r}\xi_{r}\leq 0 ]}{|\mathcal{J}_{M}^{N}|}+\widehat{\lambda}_{0}^{2}+\frac{B^{2}}{(K+2)^{2s}} \right),\end{split}$ $$

where the final inequality holds because $\gamma_{0}=\gamma_{r}=\frac{B}{\sqrt{s+1}}$ and $\gamma_{(K+2)r}=\frac{B}{\sqrt{s+1}(K+2)^{2s}}$.

Next, we establish lowerbound of $\widehat{\lambda}_{0}^{2}.$ To that end, let $S_{n}=\{(v_{i},w_{i})\}_{i=1}^{n}$ denote the $n$ samples accessible to the learner over the uniform grid of size $N$. Recall our notation $v_{i}^{N}:=\{v_{i}(x)\,:x\in\operatorname{G}\}$ and $w_{i}^{N}:=\{w_{i}(x)\,:x\in\operatorname{G}\}$ for discretized samples. Take a sample $(v_{i},w_{i})\sim\mu_{\xi}$. Then, we must have $v_{i}=\gamma_{k}\psi_{k}$ for some $k\in\mathbb{Z}^{d}$. Consider the case that $k\neq 0$. Then, by definition of the distribution $\mu_{\xi}$, it must be the case that $k\not\equiv 0\text{ (mod ) N}$. Then, Lemma 5 implies that

$$ $\operatorname{DFT}(v_{i}^{N})(-0)=\frac{1}{N^{d}}\sum_{x\in\operatorname{G}} \gamma_{k}\,\psi_{k}(x)\,e^{-2\pi\operatorname{i}\left\langle x,0\right\rangle }=\frac{\gamma_{k}}{\sqrt{2}N^{d}}\left(\sum_{x\in\operatorname{G}}e^{-2\pi \operatorname{i}\left\langle k,x\right\rangle}+\sum_{x\in\operatorname{G}}e^{2 \pi\operatorname{i}\left\langle k,x\right\rangle}\right)=0.$ $$

On the other hand, if $v_{i}=\gamma_{0}\psi_{0}$, then we have

$$ $\operatorname{DFT}(v_{i}^{N})(-0)=\frac{1}{N^{d}}\sum_{x\in\operatorname{G}} \gamma_{0}\psi_{0}(x)=\frac{\gamma_{0}}{N^{d}}\sum_{x\in\operatorname{G}}1= \gamma_{0}.$ $$

Additionally, when $v_{i}=\gamma_{0}\psi_{0}$, we have $w_{i}=\gamma_{Nr}\,\psi_{Nr}$. In this case, Lemma 5 implies that

$$ $\operatorname{DFT}(w_{i}^{N})(-0)=\frac{\gamma_{Nr}}{N^{d}}\sum_{x\in \operatorname{G}}\psi_{Nr}(x)=\frac{\gamma_{Nr}}{\sqrt{2}N^{d}}\left(\sum_{x \in\operatorname{G}}e^{-2\pi\operatorname{i}\left\langle Nr,x\right\rangle}+ \sum_{x\in\operatorname{G}}e^{2\pi\operatorname{i}\left\langle Nr,x\right \rangle}\right)=\frac{\gamma_{Nr}}{\sqrt{2}}2=\sqrt{2}\gamma_{Nr}.$ $$

Using these facts, we can write the empirical least-square loss as

$$ $\begin{split}&\frac{1}{n}\sum_{i=1}^{n}\,\sum_{m\in\mathbb{Z}^{d}_{\leq K}} \left|\lambda_{m}\operatorname{DFT}(v_{i}^{N})(-m)-\operatorname{DFT}(w_{i}^{N })(-m)\right|^{2}\\ &=\frac{|\lambda_{0}-\sqrt{2}\,\gamma_{Nr}|^{2}}{n}\sum_{i=1}^{n}\mathbbm{1}[v _{i}=\gamma_{0}\psi_{0}]\,\,+\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}[v_{i}\neq \gamma_{0}\psi_{0}]\,\left|\operatorname{DFT}(w_{i}^{N})(-m)\right|^{2}\\ &+\frac{1}{n}\sum_{i=1}^{n}\sum_{m\in\mathbb{Z}^{d}_{\leq K}\backslash\{\bf{0} \}}\left|\lambda_{m}\operatorname{DFT}(v_{i}^{N})(-m)-\operatorname{DFT}(w_{i} ^{N})(-m)\right|^{2}\end{split}$ $$

Thus, the least squares estimator for $\lambda_{0}$ must be $\widehat{\lambda}_{0}=\sqrt{2}\gamma_{Nr}$. That is,

$$ $\widehat{\lambda}_{0}^{2}=2\gamma_{Nr}^{2}=\frac{2B^{2}}{(s+1)|Nr|_{\infty}^{s }}=\frac{2B^{2}}{(s+1)N^{2s}}.$ $$

Note that this choice of $\widehat{\lambda}_{0}$ is valid as $\widehat{\lambda}_{0}\leq 1$.
Thus, so far, we have shown that

$$ $\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}}\left[\lVert\widehat{T}_{K}^{N} v-w\rVert^{2}_{L^{2}}\right]-\operatorname*{\mathbb{E}}_{(v,w)\sim\mu_{\xi}} \left[\left\lVert T_{\xi}v-w\rVert^{2}_{L^{2}}\right\rVert\right]\geq\frac{B^{ 2}}{3(s+1)}\left(\frac{\mathbbm{1}[\widehat{\lambda}_{r}\xi_{r}\leq 0]}{| \mathcal{J}_{M}^{N}|}+\frac{2}{N^{2s}}+\frac{1}{(K+2)^{2s}}\right)$ $$

Our proof will be complete upon establishing that

$$ $\frac{1}{|\mathcal{J}_{M}^{N}|}\,\operatorname*{\mathbb{E}}_{\xi}\left[ \operatorname*{\mathbb{E}}_{S_{n}\sim\mu_{\xi}}\left[\mathbbm{1}[\widehat{ \lambda}_{r}\xi_{r}\leq 0]\right]\right]\geq\frac{1}{8n}$ $$

for an appropriate choice of $M$.
To that end, let $\mu_{\xi}^{\mathcal{V}}$ be the marginal of $\mu_{\xi}$ on $\mathcal{V}$ and $S_{n}^{\mathcal{V}}\in\mathcal{V}^{n}$ denote the restriction of samples $S_{n}\in(\mathcal{V}\times\mathcal{W})^{n}$ to its first arguments. Then, we can change the order of expectations to write

$$ $\operatorname*{\mathbb{E}}_{\xi}\left[\operatorname*{\mathbb{E}}_{S_{n}\sim\mu _{\xi}}\left[\mathbbm{1}[\widehat{\lambda}_{r}\xi_{r}\leq 0]\right]\right]= \operatorname*{\mathbb{E}}_{S_{n}^{\mathcal{V}}\sim\mu_{n}^{\mathcal{V}}}\left [\operatorname*{\mathbb{E}}_{\xi}\left[\mathbbm{1}[\widehat{\lambda}_{r}\xi_{r }\leq 0]\right]\right]\geq\frac{1}{2}\,\mathbb{P}[\gamma_{r}\psi_{r}\notin S_{ n}^{\mathcal{V}}]\,$ $$

To understand why the final inequality holds, observe that when the event $\gamma_{r}\psi_{r}\notin S_{n}^{\mathcal{V}}$ occurs, the learner has no information about $\xi_{r}$. This implies that $\xi_{r}$ and $\widehat{\lambda}_{r}$ are independent. Consequently, given that $\gamma_{r}\psi_{r}\notin S_{n}^{\mathcal{V}}$, the event $\widehat{\lambda}_{r}\xi_{r}\leq 0$ has a probability of at least $1/2$ since $\xi_{r}$ is sampled uniformly from $\{-1,+1\}$.

Next, it remains to pick $M$ such that

$$ $\frac{\mathbb{P}[\gamma_{r}\psi_{r}\notin S_{n}^{\mathcal{V}}]}{|\mathcal{J}_{ M}^{N}|}\geq\frac{1}{4n}.$ $$

To get this, we choose $M=2n$. It is easy to verify that $|\mathcal{J}_{M}^{N}|\geq n$ whenever $N>1$. This is true because no more than half of integers in $\{1,2,\ldots,2n\}$ are divisible by $N$.
Thus, we have

$$ $\mathbb{P}[\gamma_{r}\psi_{r}\notin S_{n}^{\mathcal{V}}]=\left(1-\frac{1}{3| \mathcal{J}_{M}^{N}|}\right)^{n}\geq\left(1-\frac{1}{3n}\right)^{n}\geq\frac{1 }{2}$ $$

for any $n\geq 1$. Noting that $|\mathcal{J}_{M}^{N}|\leq 2n$ completes our proof.
∎

###### Proof.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 1
presentation: 3
questions: I don't have specific questions. I rank this paper mainly based on the problem and setting this paper has.
soundness: 2
strengths: This paper is very well written.
summary: Fourier neural operators (FNO) have been widely using in learning nonlinear operators between function spaces. Motivated by FNO, this paper studies a simple case when the FNO is reduced to the composition of a Fourier transform, a learnable linear transform, and an inverse Fourier transform. The goal is to learn a linear operator using this simplified trainable linear operator network. This paper studies the error analysis of this simplified linear operator learning.
weaknesses: 1) The trainable operator in this paper is too simple to be useful for more general analysis. This is a linear operator and the problem is essentially a linear regression problem in the Fourier domain. This is a well-studied problem. The discretization error related to DFT is a textbook subject in applied harmonic analysis. The generalization error analysis of a linear regression problem is also classical. The only difference is that this paper consider the linear regression with an infinite coefficient vector instead of a finite coefficient vector in textbooks. But the statistical learning error is trivial after the finite truncation with the parameter K in this paper, because after a finite truncation, the infinite coefficient vector is reduced to a finite one and the classical statistical analysis can be directly apply to analyze the error. I don't see any technical challenge to finish the analysis in this paper. It is very straightforward.

2) The proposed method cannot be directly extended to learning nonlinear operators because the main idea is a simple linear regression in the Fourier domain. 

3) The authors missed many important recent development in the error analysis of operator learning. A recent JMLR paper (https://jmlr.org/papers/v25/22-0719.html) has studied a very general error analysis for learning nonlinear operators. When the deep neural network in the JMLR paper is simplied to a linear model, and the encoder and decoder in the JMLR paper is the DFT and inverse DFT, then the analysis there can be directly applied to analyze the problem considered in this paper. 

4) There are other important generalization analysis of operator learning should be dicussed. For examples,
[1] Generalization error guaranteed auto-encoder-based nonlinear model reduction for operator learning, Hao Liu, Biraj Dahal, Rongjie Lai, Wenjing Liao, Applied and Computational Harmonic Analysis Volume 74, January 2025, 101717.
[2] Deep Operator Learning Lessens the Curse of Dimensionality for PDEs. Ke Chen, Chunmei Wang, Haizhao Yang. Transactions on Machine Learning Research, 2023
[3] On the Training and Generalization of Deep Operator Networks. Sanghyun Lee and Yeonjong Shin, SIAM Journal on Scientific ComputingVol. 46, Iss. 4 (2024)

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. See weaknesses above. I think this work is an important step in the right direction, but has certain critical weaknesses and assumptions that are not clearly stated in the work. It would be extremely useful to know whether those hidden assumptions drastically alter the results.

2. Another smaller quibble is the notation in the paper. Could we have a table in the appendix showing all the symbols and their meaning, at least if those symbols are FNO hyperparameters?

3. There is also a minor presentation issue. The three different error terms are all mixed together in the text. The authors should clearly separate them out and show us which is which.

4. The title of the paper says "controlling [various error terms]", but the authors do not specify a practical numerical procedure to control those errors nor do they demonstrate the efficacy of such a procedure. The title probably needs to be changed, or the numerical results I asked for (above) should contain an example demonstrating how to control these errors.
soundness: 3
strengths: This paper represents an important step in the direction of certifiable and trustworthy operator learning by establishing different error bounds for the FNOs. The authors' exposition is mostly clear, and the connection to other works such as functional data analysis (FDA) is well-highlighted. The authors also make a number of other interesting and insightful observations on the way to their main results; for instance, they use the Mercer decomposition of the kernel to suggest that the FNO's Fourier layers simply parametrize the eigenvalues of a kernel while fixing the eigenfunctions to be complex exponentials/ trigonometric polynomials.
summary: This paper is focused on establishing error estimates for operator learning with Fourier neural operators (FNOs). The authors specifically focus on the linear integral operator inherent to the FNO architectures, and establish error estimates for statistical errors (due to finite numbers of samples), truncation errors (from the fact that higher frequency modes are thrown away in the FNO), and a discretization error (arising from the fact that the input functions are sampled on a finite grid). The authors also use the discrete Fourier transform (DFT) to develop a least squares type error estimator that can be bound the other errors both from above and below.
weaknesses: 1. FNOs use lifting and projection operators (via MLPs). Lifted input functions are fed to the Fourier layers. To the best of my knowledge, the authors' error estimates don't take this lifting into account at all; they are agnostic to it. However, as far as I am aware, it is unclear how the (nonlinear) lifting procedure interacts with the smoothness assumptions the authors place on the input functions to the operator learning problem. If it in fact violates the assumptions (since the lift is learned via an MLP), I suspect the authors' results will break down. This needs to be addressed in the work.

2. The authors assume the input and output spaces to the operator learning problem are both in L^2(T^d,R), rather than the general Banach space setting; the choice of R here is to simplify analysis. However, practical operator learning problems are not usually in the convenient setting of periodic domains like T^d. Typically, the problems of interest are in L^2(R^d, R). Then, for non-periodic input functions, one would expect a fourth error term to come into play with the Fourier layer: a Gibbs-type error term that potentially "pollutes" both the truncation and discretization error terms. This also needs to be addressed. I think the setting in the work is too restrictive.

3. I'd like to see at least preliminary results with input functions that have limited smoothness. This will be vital in order to use operator learning for standard problems containing shocks or discontinuities.

4. FNOs are certainly not just used with the FNO integral operators studied in this work. Assume an input function in T^d (should be R^d as in the previous comment, but let's assume T^d!) is lifted by the input MLP to R^p, i.e., there are p channels. Each linear operator acts on p vector-valued input functions, and is augmented with a pointwise convolution operator that mixes information across those p channels. The analysis has completely ignored this, as far as I can tell, but those pointwise convolutions appear to be key in the approximation power of FNOs.

5. The authors should present at least one or two numerical experiments verifying their error bounds even in these restrictive settings (T^d, no pointwise convolution, arbitrary lift and projection). Currently, this work has none, and that is concerning. These numerical experiments would also give practitioners guidance on how to leverage the results from this paper in settings where a practitioner has control over the sampling and discretization procedures.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: **Major concerns:**
1. As I understand, the problem authors consider is, how to estimate the error of a linear functional model with integral kernel diagonal in truncated Fourier basis, fitted with ordinary least squares and discretized on the uniform grid.
   
   This problem allows a succinct formulation on a single page. Can the authors please discuss why they decided to provide excessive details on operator learning, Fourier neural operator, and straightforward results like Proposition 1 and Proposition 2? Would not it be easier (for the authors and the reader) to formulate the problem right away?

2. It does not seem to me that there is a direct relation between the statistical or approximation properties of FNO and the model authors consider. For example, the authors claim "The inductive bias in FNOs is that the functions are sufficiently smooth so that the higher Fourier modes can be safely ignored." Although this is correct that FNO has some bias toward smoother function, the situation is not as simple as the author's frame. FNO contains nonlinear activation functions that are merely continuous. The resulting operator can transform frequencies well above the chosen truncation frequency for the integral kernel. In contrast, the linear model considered by authors can not possibly process high frequencies.
   
   This distinction already compromises the relation between FNO and the linear model. Given that, it is unclear that one should introduce FNO (vaguely related model with completely different properties) in such great detail.

3. The result seems to be straightforward in a way it contains a well-known statistical error, a well-known discretization error, and a well-known truncation error that essentially estimates the convergence rate of Fourier series for the functions from Sobolev space. I can not point to the paper or monograph that contains results proven by authors in the paper, but it looks very unlikely that related results are not already available in the literature. The authors provide some discussion explaining why their results are different from already available ones. For example, they mentioned https://arxiv.org/abs/1208.2895 and claim that the differences are: (i) they consider an "agnostic setting" rather than additive noise model; (ii) parameter $K$ is not learned from the observed data; (iii) basis is not learned from observed data; (iv) functional data is given in a discrete. I would like the authors to extend the discussion of the differences. For example, why is it significant that data is not discretized? Is not it the case that discretization errors (or interpolation errors) are well understood when a particular space
   
   In my opinion, the setup given in https://arxiv.org/abs/1208.2895 is more natural and more general than considered by the authors of the current contribution. The reason for that, in my opinion, is https://arxiv.org/abs/1208.2895 in a standard functional-data analysis, while the setup of a present contribution is in-between operator learning and Functional data analysis. On the one hand, the authors want to keep the structure of the linear operator from FNO, which seems too restrictive from a functional data analysis point of view. On the other hand, authors consider a single linear layer which is again too restrictive from a neural operator point of view.

**Minor issues:**
1. Authors work with functions of $\mathbb{T}$. Intermediate layers of the Fourier neural operator do not produce exclusively periodic functions. Can the authors comment on that discrepancy?
2. On lines 503-504 authors made a strange claim that exponential dependence on $d$ does not matter for $d=3$. This statement is trivial. Perhaps, more importantly, FNO can not be applied for large $d$ because it suffers from exponential increases in memory and computing.
3. Line 423 $v_1$ contains incorrect subscript.
4. It seems that the result obtained by authors can be extended to many families of functions, e.g., $\phi_{m}$ can be replaced with Chebyshev or Legendre polynomials. Can the authors please comment on that?


All in all, I can not point to any significant technical flaw in the article, but I do not find the results surprising and useful for operator learning and functional data analysis. These points can be considered subjective, so I do not think they should significantly affect the decision to accept or reject the paper. I hope this explains the chosen "overall score".
soundness: 2
strengths: The article is easy to read, rigorously written, and provides many details about related topics in functional data analysis and neural operators. Although I only reviewed appendices superficially, I have little doubts about the correctness of the theoretical results.
summary: Authors derived upper and lower bounds on excess risk. Excess risk is formally defined on page 7, but in a gist it is an average of difference between error of selected statistical estimator and the best model in selected class. As a class of models authors consider linear functional model  $g(x) = \sum_{\left\|m\right\|\_{\infty}\leq K}\lambda\_m\phi\_{m}(x)\left<\phi\_{-m}, f\right>_{L_2}$ where  $\phi_m(x) = \exp(2\pi i \left(m^T x)\right)$, $\lambda_m$ are unknown parameters, $f$ and $g$ are input and output functions respectively. As an estimator authors use least squares with functions discretised on the uniform grid and scalar products computed with DFT.
weaknesses: The main weakness is that the problem setup chosen by the authors is too simple (or too convenient) and not directly related to the operator learning problem. Somewhat subjectively, I do not find the results presented by the authors surprising. Given the simplicity of the setup, I am also not entirely sure that related results are not already available in the literature on functional data analysis.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - I worry that the suggestion of selecting N>= n^{1/2s} and K>=n^{1/4s} is only because of the weaknesses of Theorem 1.  The only serious weaknesses between Theorem 1 and Theorem 2 is the 1/sqrt{n} versus the 1/n. 

- In most PDE theory, we don’t assume that V = W. Instead, W is a smoother space than V.  Is it easy to adapt theorem 1 and theorem 2 so that V \neq W? 

- Due to the Sobolev embedding theorem, one would usually imagine that the discretization error goes down like N^{s-d/2}, not N^s. Similarly, the truncation error goes down like K^{2s-d}, not K^{2s}. What’s your main idea for removing the dimension-dependency in the error bounds in Theorem 1?
soundness: 3
strengths: The error bounds for approximation power and training landscapes are poorly understood in the context of FNOs. I enjoyed the analysis of the three types of error: (1) Finite training data (statistical error), (2) Representing continuous input/output on finite grid (Discretization error), and (3) Fourier series truncation (truncation error). 

In this paper, the discretization error and the truncation error are bounded very nicely. It is very welcomed to have both upper and lower bounds on these errors so that one can attempt to balance efficiency with accuracy. The upper bound of the statistical error makes sense as it is just a Monte Carlo rate of convergence, as expected. The lower bound is a little more mysterious because it comes from a particular difficult distribution that the authors have designed.
summary: The authors investigate Fourier operators by analyzing the statistical, discretization, and truncation errors within the Fourier Neural Operator framework. There are error bounds derived from DFT-based least squares estimators and some insights into the efficient approximation of solution operators for PDEs.
weaknesses: The statistical error is decaying only like the square root of the sample size n; however, much faster rates of convergence are usually observed in practice.  Getting at this discrepancy is important, because the analysis right now suggests that a large number of training data samples are needed for accurate FNOs.  One may have to make much bigger assumptions about the PDE to make this work or restrict the function space on which to learn the solution operator. 

The paper’s insights into the model structure only apply to the FNO’s linear core. While that is a first step, the nonlinear layers in an FNO’s architecture is the most important part.

Meta-review: (a) Summarize the scientific claims and findings of the paper based on your own reading and characterizations from the reviewers.

This paper addresses the problem of learning linear operators in the context of Fourier Neural Operators (FNOs). The authors focus on three sources of error: statistical error due to finite sample size, discretization error arising from sampling on a finite grid, and truncation error from approximating operators in a finite Fourier basis. The main contributions are theoretical error bounds (upper and lower) for these components, framed within a DFT-based least squares estimator. The work situates itself within operator learning and functional data analysis (FDA), emphasizing foundational questions about multiresolution generalization.

(b) What are the strengths of the paper?

Rigorous and well-written presentation with detailed mathematical analysis.
Clear contributions to understanding error components in operator learning.
Offers theoretical insights into the limitations and behavior of FNO’s linear core.
Makes connections to FDA, particularly in highlighting multiresolution generalization.

(c) What are the weaknesses of the paper? What might be missing in the submission?

Relevance to Practical Operator Learning: The setup is overly simplistic, focusing on linear models that do not adequately reflect the nonlinear and more general cases typically encountered in practice. This limits the paper's impact on the operator learning community.
Lack of Novelty: Many results appear to be straightforward applications of existing statistical and harmonic analysis tools. Reviewers questioned whether the contributions significantly advance the state of the art.
Omission of Key Components: Critical elements of FNOs, such as lifting/projection operators and pointwise convolutions, are excluded. This restricts the applicability of the results.
Missing Numerical Verification: The absence of empirical experiments to validate the theoretical findings makes it difficult to assess the practical relevance of the results.
Restrictive Assumptions: The focus on periodic domains and smooth functions overlooks practical scenarios involving non-periodic or non-smooth data, which are common in real-world problems.

(d) Provide the most important reasons for your decision to accept/reject.

While the paper is rigorous and provides valuable theoretical insights, the overall contributions are incremental and lack sufficient novelty to warrant acceptance at ICLR. The assumptions and simplified setup significantly limit the paper's practical relevance, and the omission of numerical experiments undermines its potential utility for practitioners. Encouragingly, the authors have demonstrated a clear interest in exploring foundational questions, which could serve as a basis for future, more impactful work.

Decision: Reject