Controlling Statistical, Discretization, and Truncation Errors in Learning Fourier Linear Operators
Authors: Unique Subedi
Ambuj Tewari
Venue: Accepted by TMLR ()

Abstract: We study learning-theoretic foundations of operator learning,  using the linear layer of the Fourier Neural Operator architecture as a model problem. 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.

Published in Transactions on Machine Learning Research (08/2025)
Controlling Statistical, Discretization, and Truncation Errors in Learning Fourier Linear Operators
Unique Subedi
subedi@numich. edu
Ambuj Tewari
Lewario@umicck edu
Department of Statistics, University of Michigan
Reviewed on OpenReview:
Abstract
We study learning- foundations of operator learning, using the linear layer of the Fourier Neural Operator architecture model problem. First, 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 alorementioned errors.
1 Introduction
In operator learning, the goal is to use statistical methods to estimate 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 (PDFs) (Li et al. 2021 Kovachki et al. 2023 For example, consider the heat equation
du 0l
V2u,
where u: 1] + R vanishes the boundary. The solution operator for this equation is linear operator exp(r(V²) == E (T /kd. Fixing some time point (say / = 1), our objective is to learn the solution operator L == e2)(
Given the training data (e), wi), (Un, wa) where = Cvs, operator learning entails using statistical methods to estimate the solution operator C.. Then, given a new input v, one can get the approximate solution w = C.v. The goal is to develop the estimation rule such that & is close to the actual solution w = Le under some appropriate metric.
Traditionally, given an input function v, one would use numerical methods such as finite differences get a numerical solution. The solver starts from scratch for every new function v of interest and can be computationally slow and expensive. This can be limiting in some applications such 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 small degree of accuracy.
In this work, rather than focusing on specific PDEs, we adopt a broader perspective and study the learning- thcoretic foundations of operator learning. For this task, we use the lincar layer the influential Fourier Neural Operator (FNO) architecture proposed by Li (2021) as our model problem. While our results offer some practical and theoretical insights into the FNO, it. important to emphasize that primary

---

Published in Transactions on Machine Learning Research (08/2025)
objective is neither to advance the practical implementation of operator learning to develop deeper insights into the FNO architecture itself. Instead, our objective is to rigorously understand the statistical learning aspects of the operator learning paradigm. Our primary goal is to understand how operator learning differs from traditional machine learning scttings and to identify the now techniques required to build a rigorous learning-Cheoretic Toundation for this emerging area.
To this end, we start by identifying the distinct types of errors that are unique operator learning. In addition the standard statistical error arising from finite sample size, operator learning introduces discretization error due to the functional data being available only finite grid of domain points, Furthermore, ignoring high-frequency Fourier modes lead to truncation error. Lastly, we introduce a Discrete Fourier Transform (DFT))based estimator for our model problem and demonstrate how these errors can be systematically quantified for this estimator.
1.1 Neural Operators
To formally define our problem setting, we need to introduce neural operators from (Kovachki et al. 2023) Let V be a vector space of functions from a bounded subset X' C Rd to RP, and W to be a vector space of functions from y S Rdd to Rt, Given function v E V. a single layer of neural operator N₁ : + W is a mapping such that
(N.v)(w) = a (KC,, (v) b((())
Vy Ey,
where (Ka,v) (v) = Jx-aa, ka (v, v(x) da. The function be y - R is bias function in W, the function a R + 19 is a point-wise non-linear activation, and the transformation v + Ka, is an integral kernel transform of v using some kernel ko, x x Roxp. These layers are then composed to get a ncural operator architecture.
Parametrizing Ke, in terms of ka, can be impractical due the computational cost of calculating the integral in for each layer. Thus, significant area of rescarch in neural operators focuses on developing innovalive parametrizations of Ke, that facilitate more elficient compulation. One such parametrization gives rise to well-known architecture called the Fourier Neural Operator.
1.2 Fourier Neural Operator (FNO)
In this section, we present brief, non-rigorous overview of the FNO. A more formal treatment, along with new insights into its parametrization, is provided in Appendix B
We consider the setup from the work Li et al. 22021). Let X' = periodic torus. Assume the kernel ke translation invariant that is, ko (o, = koly - w). This implies that Ke is a convolution operator. Then, the Convolution Theorem implies that
y =
[0, be d-dimensional
FF ((()))
where F and F-1 are Fourier and Inverse Fourier transform respectively. The key insight in FNO is that instead of parametrizing the kernel kg, we parametrize its Fourier transform F(ke) directly. That is, we parametrize the kernel transform operator as
Kav= = F-1 (Ag Flo)).
This a linear operator and will be referred to as Fourier linear operator. When (Aa()le < oc, we can write this
(K)r))())=
Σ 2n k(mw)) Ag(m) (Fu)(m) Vy e.
mEZ4
There are two practical challenges in implementing the operator Kgg. First, the implementation involves an infinite over Zd, Second, the Fourier transform Fo cannot. be computed exactly since the function v is
2

---

Published in Transactions on Machine Learning Research (08/2025)
only available a finite grid of domain points. To address the first challenge, large K E N is fixed and we sum only over yn E dd such that |m]er S K. The second challenge is addressed by approximating Fu using the Discrete Fourier Transform (DFT) of v over the fimite 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, study the error bounds of learning the operator class B is some parameter space that will be specified later. We study this simple setup to conceptually separate the paradigm of operator learning from its commonly used instantiation using 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 thcorctical analysis.
(As F(u)) 3 E B), where
We assume that V w HM(T", R), a (s, 2)-Soolle space of real-valued functions defined on the d- dimensional periodic torus. See Section 3.3 for explanation why V and W need to be function space with higher-order smoothness to achieve a vanishing crror. We work in the agnostic (misspecificd) setting and analyze the DFT-based least-squares estimator (see Section 3.2 for more details). Specifically, for some universal constant C > O, we show that the excess risk of the DF DFT-based least-squares estimator is at most
122 N K25
The term 1/v2 is the usual truncation error incurred because the learner only works with the low Fourier modes m such that [m/e= S K. Finally, the term 1/N* is the discretization error due to functions being accessible to the learner only on the uniform grid of size Ná of [0, 1j.. This error quantifies the generalization error of an estimator trained on a grid of size Nd but evaluated at full resolution (N + 00). formalizes the concept of multiresolution generalization (operators trained at lower resolution have good generalization even when evaluated in higher resolution) phenomenon frequently observed in practice [Li et al 2021 Section 5).
estimatiio error due to finite sample size. The term 1/K2* is the
Additionally, we establish the lower bound on excess risk, showing that it is at least
+
N2s
K2s
for some 02 > 0. Our analysis is non-asymptotic and the precise form of the constants and d2 are provided
in Theorems 3.2 and 3.3 respectively.
1.4 Related Works
After Li et al. (221)) proposed Fourier Neural Operators (FNOs), there has been surge of interest in this architecture. The number of applied works is too vast and not entirely relevant to list here, so we focus on related theoretical works. One of the earliest theoretical analyses of FNOs was the universal approximation
result by Kovachki et al. 22021).
More closely related our work a recent study on the sample complexity of various operator classes, including FNOs, by KKovachi et al. (2024a). 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 part of the model rather than variable that the learning algorithm based on metric entropy analysis, which leads to suboptimal dependence on K and the input dimension d. Specifically, their bounds break down as K + oo and suller from the curse of dimensionality in d. In rast, 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 dircction based analysis to capture function classes at the level of generality considered in Kovachki et al. (2024a) We also note that Rademacher-baee based analysis has also been used by Raman et al. (002)) Tabaghi et. al.
choose. Their error bounds are
extend our Rademacher-
3

---

Published in Transactions on Machine Learning Research (08/2025)
2019 to study Schatten operators between Hilbert spaces. Kim & Kang (2024) also bound the Rademacher complexity of FNOs, but the bound is rather loose and even non-vanishing in some cases. Finally, the analysis by Liu et al. (2024) and Liu et al. (2025) also share our motivation of quantifying the statistical error in operator learning.
A recent work by Lanthaler et al. (2024] aligns with our goal of quantifying the discretization error of FNOs. In fact, the key ideas used in the proof of lemmas D.5 and D.6 in discretization error analysis is drawn from their work. However, the nature of their results differs from ours. To discuss the difference precisely, let V be trained Fourier Neural Operator and be input function available to the learner only over a discrete grid of domain points of size N. Denote n.a as the set of discrete values of v available to the learner. Lanthaler et al. (2024) bound the term I| - Vo 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 focus is on quantifying the generalization error of an operator trained on a grid of size N but evaluatod full resolution (N - xe); lype of multiresolution generalization (Li et al., 2021 Section 5).
Finally, also note that setup is closely related to the function-to-fuucctio regression often studied in the functional data analysis (FDA) literature. For example, the linear layer of a neural operator v + Ke b is a well-studied model in FDA (Wang et al. 2016, Equation 15). Even a single layer of a neural operator v + a (Kv + 6) has been examined in FDA literature as multi-indes functional models (Wang et al. 2016 Equation 13), (Chen et al. 2011). 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- frameworks under some assumptions about the data-generating process. As 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. 2021 Kovachki et al.) (024b). The emphasis is on creating computationally efficient methods that can be used to train large models and handle large datasots. However, we believe that the interscction of these two fields can benefit both. The theoretical tools developed in FDA literature can be applied to the analysis operator learning methods, while the computational advances in operator learning can help scale FDA methods.
2 Preliminaries
2.1
Notation
Let N be natural numbers and be integers. Define No := N U (0). R and C denote real and complex numbers respectively. For any 77 E Rdd, we let |m/p == maxigisa 1v denote the erD norm. For any complex number z E C such that z a+bi, we use |z| v=l=vo= 62 and v, E Rd, the term (I,9) denotes the Euclidean inner product Occasionally, the inner products on other Hilbert spaces such as 2 will be distinguished from the Euclidean one with the subscript such as (+)) However, when the context is clear, we will use (5.) to denote canonical inner products on the respective Hilbert spaces.
a ib denotes complex conjugate, For any
Given K E N, we define = fm E 2d lm/ I K} and 2 := Z Z K. For a sequence s := {sk (sk)ek keze, we will also use |s|E to denote the 0o norm of s. Morcover, we let T ~ [0, 1]d denote d-dimensional periodic torus. See (Grafakos et al. 2008 Chapter 3) for more details on the torus. Throughout the paper, for any m E Zd, we use Pm T + C to denote the function Pm = 2n k(m.a) The sequence (fmm mmzz will be referred to as Fourier basis.
2.2 I 2 Spa-cs and Fourier Analysis
Define
L'(T R) = {
f |u(x))2 dr < <o0
uu T +
Recall that (T RR) is Hilbert space with inner-product (u, u) Sru u(x) oxx) dz. The norm induced by this inner product will be denoted as I1l The sequence (pm) forms orthonormal basis for
4

---

Published in Transactions on Machine Learning Research (08/2025)
(T R). That is, for any (TM, R), can write Emez" (u, (mm) La Pm, where the convergence is in no-morm. The colebrated Parseval's identity then implics that ||u| = Emeza (u, (m)) 2a 12
Since T identified with a bounded set [0, 1J6 the condition w E 1.2 IR) implies that u is integrable. That is, So [u(x)] dx < cc. For integrable functions, F denotes the Fourier transform operator such that Fu: z + C is a complex-valued function on 2d defined as
(Fu)(m)= = for. e(x)e= 22 dx.
Note that we have (m) (u, pm). We let J= denote the operator that satisfies (F-1F) u F will be referred to as inverse Fourier transform. Note that even when is real-valued function, (u, (m)) may lie in C.
2.3 Sobolev Spaces
Fix E N and define
HT, R)
{u E L3 0² E L'(TT, R) for all & E NO & 1k/ S s}.
Here, Jhu is the t partial derivatives. The space H (T [)), also referred to as (s, (s.bo-br space, is a Hilbert space with an inner product
(), =
Σ
(otu,0'o)
KENS Me
which naturally induces the norm |lul|w- = Vl, u) In this paper, we often assume that & > d/2. This ensures that (see Lemma D.4 Σmeza (u, (pm) < oo, which implies uniform convergence the Fourier series over TV
Note that is more common to define Sobolev spaces with multi-indices such that | S 8. We chose the restriction |/ S simply for the convenience computation. However, as d is finite and all lp norms on d-dimensional space are equivalent up to factor of d.
3 Learning Fourier Linear Operators
In this section, we establish excess risk bounds of learning the operator class {u F- F(u)) e B), where B is some parameter space. Here, only consider the case where V, W C (TT. R). This is different from the usual setting in the literature, where V and W are Banach spaces of vector-valued functions. First, significant number of PDEs of practical interest describe how scalar-valued functions evolve. Since not much known from a thcoretical standpoint even for scalar-valued functions, we believe that this a good start. Second, assuming V, W to be a subset of L (a Hilbert space) does not result in any meaningful loss of generality from a practical standpoint. In practice, one must discretize the domain and work with function values over discrete grid, which effectively requires bounded domain. This essentially means working with bounded functions
bounded domain, all of which are 2 integrable.
For scalar-valued functions, Ag is scalar-valued function defined on modes zd. Since the function is only defined on a countable domain, we can also represent it by a scalar-valued sequence { mezz. Henceforth, we will drop the 3 and just write {>m) } denoting Am 's to be the parameters themselves. For the convenience of notation, we will also use to denote the sequence {Am}meza and write J- (()).. Fixing some C 0, the class of interest can be written as
{U-FF(AA()) iale SCJ.
A starting point of our work is the following result on the decomposition of Fourier linear operators.
5

---

Published in Transactions on Machine Learning Research (08/2025)
Proposition 3.1. If X (z"), then
F (Aull( = Σ
Am (m (p-mi 1)
(1)
mE2
where the equality holds for every (2
Here, Pm pm is rank-1 operator such that (pm pp-m) (u) (0-m- m- u) Pm The equality in 1 means F-1 (X [())) Emezs Am 9m (p-m, "), for all u E 1.2 IR), where the sum converges uniformly over E We provide the proof of Proposition 3.1 in Appendix C
Given Proposition 3.1 we can write our class as {Emeza Am Pm @ p-m Mele S CJ. This representation is preferable for the tollowing 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 E L", which is a rather artificial constraint required only ensure that the operator F- X F())) is a well-defined object. However, Σmeza Am Pm @ 9-m is still well-defined even when 6o (in fact, it is a bounded operator). Therefore, for some fixed C 0, we will instead study the class of operators
Am Pm 3 p-m Ma uesscc sc.
T
mEZd
Since the class upper bound) for T also holds for the constrained class.
Miee S <C} is contained in the class T, any guarantee (in terms of
Remark. The class T should remind readers of de Hoop et al. 2023 who also consider the problem of singular value inference of an operator under fixed singular vectors. However, their setting differs from ours in two significant ways. First, they only consider the well-specified sctting with an additive noise model, whereas we adopt fully agnostic viewpoint. Second, they do not account for possible discretization errors, assuming that their input and output functions are fully available to the learner.
3.1 Problem Setting and Error Types
We adopt the framework of statistical learning and study the rates of error in learning the class T. In statistical learning, the learner is provided with n E N i.id samples S, = {(v, wx)) from some unknown distribution on V x W. We adopt a fully agnostic viewpoint and do not make any assumptions about the data-generating process. Next, using the sample Sn and some prespecified learning rule, the learner then finds an estimator T T. We will abuse notation and denote T' to be both the learning rule and the estimator output by the learner. For an estimator T, can define its expected excess risk
E, (T,T =
E Samua (1,0))up
E
Tu --122
inf E TET (o,w)>u
[ - w0l(2)
Formally, the goal of the learner is to output the estimator such that (T, traditional settings, the excess risk E, T...T. p)) usually referred as the statistical error of the learner. This error arises because the learner trying find the optimal operator in T for distribution μ 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: discretization error and truncation Error.
as
In
The discretization error arises because the learner only has access to (e,, wy) ~ p over some discrcte grid of domain points. In this work, we assume that cach vn and w, are available on a uniform grid
Discretization Error:
G {m/N : (O....,N. N 13d}

---

Published in Transactions on Machine Learning Research (08/2025)
of [0, 1 for some prespecified N N. That is, the learner only has access to {u;(2) G} and {wx(z) a E 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.
Truncation Error: To see where the truncation error comes from, note that the representation of any estimator T T requires specifying an infinite sequence {Am However, the infinite sequence cannot be implemented in computer. Thus, for practical implementation (Li al. 2021 one picks large K N and specifies the finite rank operator
Tk =
Σ MERS SE SK
Am Pm 8 p-
While the truncation error is specific to our class of interest T, similar "truncation' error occurs in any model class. Such error arises because operator learning is inherently infiniteddimensional problem, yet any computation perform is limited to some finite-dimensional subspace.
3.1.1 Further Connection to FDA.
The operator Tk related functional PCA-based estimators common in the FDA literature. Given n ii.d. function pairs {(0,, w:)lsm the least-squares estimator solves Σ W; & U; which under-specified in infiniteddimensionall spaces. To address this, one computes pseudo-inverse (Ein vs @ wi) by fixing an orthonormal basis [WrTEeN. With eigendeccompocitoon Σn 2/ @ v Een the @ the, the pseudo-inverse becomes E [m > O)n th @ th, yielding the estimator EL uy v4) EE Ain 0] me the 2 v.). In practice, the sum is truncated some S
(E= 8 v;),
Estimators of this type have been studied in works such Hörmann & Kidziński 2015 Reimherr 2015 Yao et al. 22055) under well-specified models. These approaches generally require learning the basis functions iy's and the truncation parameter from the data to achieve the guarantees established in these studies, which often introduces significant computational challenges. In contrast, we work in the potentially misspecified (agnostic) setting, and depends only on the sample size n to achieve vi-risk consistency. Additionally, FDA-based approaches typically assume exact access the functions, which is unrealistic in practice. In- stead, we explicitly account for the discretization error that arises when functions are only available on a finite grid.
3.2 A Constrained Squares Estimator
In this section, we specily our primary estimator interest. Let T = =>mzzz Am im p-m For any u E V, we have To Emeza Am (p-m. v) 4m. As we only require foD norm of be bounded by C, we only get the convergence of the sum Emery Am (9-m, v) &mu in L norm rather than uniform. Since (im mmzz is an orthonormal basis of L 2T ,R), Parseval's identity implies
[To w11
Σ
(Te-wa - w, w.
meZd
Σ meZd
Am (y--my 1) - (p-m, w)) L2
To see why the last equality is true, note that (Tvppm) = Am (p-m, u) and (w, (m))p = (pmm w) 1.2 = (p-m: w) 12 as w is real-valued. Thus, given {(v, w the least-squares estimator over the class T an operator T specified by the sequence {Am meze, which obtainod by solving the optimization problem
min 1 Σ Σ (Am mEZ4) n 1=1 meza
12
Am (4-mm: (p-m wi)
subject to sup 1mml S C.
mezu

---

Published in Transactions on Machine Learning Research (08/2025)
However, this estimator cannot be implemented for two reasons. First, there is an infinite sum over 2 Second the learner only has access to (e,, w:) through uf" == (1s(2) I E GJ and wa := {mi(() x E G): and thus the L inner products cannot be computed exactly. Both of these issues can be resolved by considcring the operator specified by the finite length sequence X(N) = {Am m E zd _ obtained by minimizing
Σ
D -DFT(,))(
== mEZ
subject to supmezz 1m I C. DFT, which stands for Discrete Fourier Transform, is the numerical approx- imation of (p-m: 4) La and defined formally
(F Ná
Σ e 2n knfmm)
ZEG
To indicate the dependence of both truncation value K and grid Nd, let us denote the estimator obtained by solving this problem to TN where
TW
(m(N) Pm 9-m
(2)
MEZA
The estimator 7N is the closest implementable version the least-squares estimator for our setting.
3.3 Error Bounds
In this section, we study how & ( T.,)) decay as a function of n, K and N. Note that we have only specified that V and W are subsets of (TT, (R), but have not specified their precise form. A natural choice would be W = {u E LP(T IR) ||]]| S 1}, the unit ball of L² R). However, it turns out that K T, 14) docs not vanish under such V and W. E, ET
To see this, let K E N be a truncation parameter chosen by the learner. Define = Uniform([[Wms vm) 2 < |m/ < 2x+1J) that only supported on large modes. Here, Vmn = 2 2-1 + (-m) is the symmetrized, real-valued version of m-th Fourier mode. Note that we can choose a distribution as 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 TN produced by the learner, IN = 0 almost surcly for (v, w) ~ μ.. K
Thus, we have [(,,)>~ [ w
wli2a] ((,,w)~
[| = 1, as Vmm for some 2 < |m/ < k
almost surely and I1 = 1 for any 2
Next, let C and define T Emeza Pm 2 p-m. It is easy to see that T 2 (7' spk +
T kp)))= - (1-x tik) the Vk e 2 As T T,, we obtain infrer E (v,,n)= ||Te: w w S
E (v, |
- w ul = 0. Thus, we have established
T,), T,(
This shows that merely bounding the L norm of v, w not sufficient achieve a vanishing crror. So, we need a stronger assumption on the input and output functions.
The inductive bias in FNOs is that the functions are sufficiently smooth that the higher Fourier modes can be safcly ignored. We will also adopt this viewpoint and assume that V and W are smooth subsets of (Td, IR. In particular, we will assune that y = W = H HTd, RR, a (s, 2)-Sobolev space (see Section 2.3 For any u e HTTT RR), we are guaranteed that (p-m. u)z= + sufficiently fast as |m/ + sc. This allows us ignore higher Fourier modes while only incurring small error. The following Theorem, whose proof is deferred to Apendix E makes these arguments precise and provides an upper bound on the excess risk of i.N in terms of n, N, and K.
8

---

Published in Transactions on Machine Learning Research (08/2025)
Theorem 3.2 (Upper Bound). Let V- = W = H*(,,R) RR) for d/2 and μ be any distribution V
W for which 3B > 0 such that 1| s B and || I B almost surely. Then, for iid samples (vr, w Ri pº accessible to the learner over the N N-uniform grid of [0, 1]², the estimator TN defined in 2 for N m5x 2 salisfies
1 vn
2 V N
SBB
K2a
The terms D(I/Vn), O(1/N*), and (l1/K²*) are the estimator's statistical, discretization, and truncation errors respectively. For most practical applications of interest, we have = 3 (functions defined on spatial coordinates). Since V < 6 in these cases, the exponential dependence of the discretization error on d is not an issue. Finally, choosing N 2 n and K 2 n Theorem 3.2 guarantees the vn risk consistency of the estimator TN
Proof Technique for Upper Bound: Here, we highlight here the key technical novelties of our proof techniques and the implications of our results. To establish the upper bound, we first decompose the excess risk into three components: (1) the risk gap between the optimal operator in T for the distribution μ and truncated counterpart, (2) the uniform deviation between the true empirical risk on the sample and its numerical approximation
the discrete grid, and (3) the uniform deviation ween the empirical risk and the actual risk. This decomposition, introduced at the beginning of Appendix L is not limited to the linear setting and can also be applied to analyze general non-lincar operator classes. Given such decomposition, bounding the truncation error is straightforward using standard Fourier series properties for Sobolev spaces. The discretization error, however, requires nontrivial analysis to show that controlling the error DFT suffices. Importantly, while the lower bound on the DFT error likely bounds the discretization error below, an upper bound on the DFT error does not always translate to an upper bound for the trained operator. For example, this is not true one adds non-smooth activation such as RELU to our model. For statistical error, standard techniques yield bound of v v=,,, which does not allow taking K - co. Our key contribution is a refined analysis that achieves a + bound independent of Kd. The K-independent bound is especially notable because K in FNOs analogous to the width in standard neural networks, where generalization bounds are known be width-independent (Golowich et al. 2018). Our results provide initial evidence that similar K-free generalization bounds may be achievable for FNOs.
Our next result, proved in Appendix F provides a lower bound on the rates at which E,, CTT,, T,H) decay.
Theorem 3.3 (Lower Bound). Let V - W H* R) for s > d/2 and C = 1. Given N. K E N, there exists distribution on on V x W for which 3B > 0 such that || I B and |/l S B almost surely and for iid samples {(Vi, w:)) 4²' accessible over the N-uniform grid of [0, [0,1] the estimator T.N defined in (2 for N 2 /2B satisfies
B²
1 [++ 8n
1
2
E, ( N
+
3(8
+ +1
N2:
(K + 2)22
Although the lower bound on truncation error matches with the upper bound, there is a gap in the statistical and discretization error. We leave closing this gap for future work.
3.4 On Possible Extensions and Refinements of our Error Bounds
The smoothness assumptions in our work are primarily needed to control truncation and discretization crrors. The lower bound in Section 3.3 shows that some regularily, specifically & >> 0, is necessary for achieving a vanishing truncation error. This condition is also sufficient for our upper bound on the truncation error. The stronger requirement $ > d/2 is required to ensure that the DFT-based estimator approximates the true Fourier coefficients. Moreover, even when 0, a statistical rate of 1/ /n independent of can still be obtained under alternative assumptions. For example, if the operator's spectrum lies in e² ((Z)), making it

---

Published in Transactions on Machine Learning Research (08/2025)
Hilbert-Schmidt, results from Tabaghi et al. (2019 Raman et al. (0224 imply that such rate is possible without any smoothness assumptions.
Additionally, in our analysis of the discretization error (Appendix E. the key quantity we control is the difference between the DFT approximation and the true Fourier coeficiinn,, namely
(-FT())((mm) - (p-m, u)}-
The assumption of uniform grid is used only to bound the numerical integration error introduced by the DFT. In principle, any numerical integration method can be applied to non-uniform grid, and long its error vanishes with increasing grid resolution. For non-umiform grids with structure, such as those based on the roots of orthogonal polynomials, Gaussian quadrature rules may be used with standard accuracy guarantees. unstructured grids, Monte Carlo methods with estimated importance weights can be used, although their convergence can be slow or the error may not vanish if the estimated weights have high variance.
4 Experiments
In this section, we present experiments demonstrating that our estimator achieves vanishing errors. We pick d 2, and the input functions e are sampled i.i.d. from (O, 10 + +)))), a widely used distribution for generating training data in the operator learning literature (see Li et al. (2021); Kovachki et al. (2023) Since 7 governs the decay rate of the eigenvalues of the covariance operator for this distribution, it directly controls the average smoothness of the samples For experiments, set y 2 as this is the smallest integer value that ensures 7 > d/2 for d 2.
To generate training data, we define a random operalor
T
Σ mEZd
Am fm 2 p-m
where im' 's are Fourier modes and Am Unif(-2,22 For given input u, the corresponding output is Noise is sampled from higher-order smooth space
generated as T' where (- to ensure that its addition does not alter the smoothness of w. In actual implementation, the transformation Tho is implemented on some N x N grid using Fast Fourier Transform (FFT) and Inverse Fast Fourier Transform (IFFT). The sum over 2d is truncated at a Nyquist limit of N/2.
Recall that, our estimator in Section 3.2 is obtained by solving a convex optimization problem for Am 's for E Zd So, we implement the optimization routine for our estimator using stochastic gradient descent with a projection step to ensure [5ml <
Figures and show the statistical, truncation, and discretization errors, respectively. The y-axis in all these figures represents the relative mean-squared testing error:
Phast
true
predicted
Ritest
true
evaluated using Nust 100 i.i.d. samples. Additional experimental results are presented Appendix The correspouding code is available at httppp///tchhhoo.oooo/mmuuuuuuap
4.1 Statistical Error
Both training and lesting are carried out on a 128 x 128 grid, with the estimator implemented using K = 64 modes. Error bands are included to account for fluctuations in the estimated parameters at small sample sizes, showing results from 5 independent runs. The model is trained and tested the same resolution at the Nyquist limit of 32 modes to ensure that the reported error isolates statistical error with the minimum possible truncation and discretization errors. The smallest. error is 6 10-4 for the sample size of 500.
10

---

Published in Transactions on Machine Learning Research (08/2025)
0.8
Mcan Tosting Erar Standard Deviation
0.7
0.6
Tosting Eror
04-
0.3
0.2
0.1
100
training Sample
Figure Statistical error of the estimator.
1.0
Testing Error
0.6
0.4
0.0
Truncation Mode
Figure 2: Truncation error of the estimator.
4.2 Truncation Error
Training and testing data are generated on a 128 x 128 grid, with the estimator trained using n 500 samples. Error bands are omilted as the estimates are almost identical due a large sample size. Both training and testing are conducted at the same resolution remove discretization error, with the sample size selected to minimize statistical error, ensuring that the reported error isolates the truncation error effectively. The lesting error converges to around 7.9 x 10-4 at the Nyquist limit of K = 64.
4.3 Discretization Error
Testing data is generaled on a 512 x 512 grid. The estimator is trained using n 500 samples on grids of varying sizes N x N, where N E {1,2, 4, 8, 16, 32, 64, 128, 256, 512}. For each training grid of size x N, truncation performed at the Nyquist limit (K = N/2).. The trained estimators are subsoquently evaluated the higher testing resolution of 512 x 512 quantify discretization error. The testing error converges around 10-4 when the estimator trained at full grid size of 512 x 512 with 500 training samples.
11

---

Published in Transactions on Machine Learning Research (08/2025)
0.8
0.6
Testing Error
0.4
100
200
300
400
500
Grid Size (N)
Figure 3: Discretization error of the estimator.
4.4 Summary of Experimental Findings
Our experiments in this section confirm that all three sources of error- crror-statisticl,, truncation, and discretiza- tion can be independently reduced by increasing the respective parameters n, K, and N.
However, the observed convergence rates, as reported in Appendix G reveal some gaps compared our theoretical predictions. In particular, the statistical error appears to decay faster than expected, and may depend on the smoothness parameter 7. This suggests that refined, distributtionddeeedeent analysis could yield sharper bounds beyond the worst-case setting. The largest discrepancy arises in the discretization error, where we observed almost uniform rate for all smoothness parameters. While our theory assumes the test resolution .22- + oc, the experiments use a fixed resolution N₂ = 512 for computational reasons. This mismatch may account for the unexpectedly uniform decay rate across different smoothness levels. more detailed analysis under finite resolutions could help explain this gap.
5 Discussion and Future Work
In this work, we established the excess risk error bounds of learning the core linear layer v + F- F(v)) of Fourier neural operators. natural future direction is extend these results single layer Fourier neural operator,
(F-1(A, (AA F(u)) b) and then to multiple layers. Although simple metric entropy-based analysis gives bound on statistical error even for single layer neural operator, such bound is vacuous when K + co. It would be interesting to see if we can get meaningful statistical rate even at the limit of K + co. One can view K as an analog of the width of traditional neural networks. Thus, analysis of u L (Ag F(u)) b) as K + oo can lead to a neural tangent kernel theory (Jacot et al. 2018) for operator learning. These insights will help us better understand width vs depth tradeolis operator lcarning. One approach to extending our statistical rates to nonlincar operator could be to carry out a Rademacher analysis similar to that of Golowich et. al. (2018) for finite-dimensionll neural networks. The main technical challenge arises from the nature of the pointwise nonlinearity a. In finite dimensions, for E IR,, Golowich et al. (2018) exploit the identity av)) = o((,,((V ey))e,, where {ez} is the standard basis. However, this identity no longer holds in the difnnte-dimensionall setting considered in Kovachki et al. 2023 where a is applied pointwise in the spatial domain rather than in the spectral domain.
For discrctization error, we consider the sotup where the training data available on grid of size A but the trained operator is evaluated full resolution (N + oo). would be interesting study the discretization error when the training data is available at resolution Ni, but the trained operator is evaluated at resolution
12

---

Published in Transactions on Machine Learning Research (08/2025)
N2. Such theory would provide more fine-grained quantification of multi-resolution generalization error observed in practices (Li et al. 202T Additionally, key practical limitation of our analysis is its reliance on uniform grids. As discussed in Section 3.4 the uniform grid assumption is used solely to bound the numerical integration error from the DFT. In principle, any integration scheme on a non-uniform grid could replace the DFT, as long as the approximation error vanishes with grid refinement. For structured grids (e.g., nodes from orthogonal polynomials), Gaussian quadrature can be used directly. For unstructured grids, one could apply Monte Carlo methods with importance weights, though these may exhibit slow convergence or non- vanishing bias when the weight variance is high. Extending how discretization error interacts with other sources of error remains interesting future direction.
analysis such general grids and formalize
Finally, with PDEs as an application, it is unclear if the iid-based statistical model is the right framework for operator learning. For instance, [oullé et al. (2023); Subedi Tewari (2025) show that an active learning approach for data collection and training for solution operators of elliptic PDEs yields exponential error docay with increasing sample size. Therefore, an important future direction define the appropriate aclive learning model and develop aclive algorithms for operator learning.
Acknowledgements
We acknowledge the support of NSF via grant DMS-2413089.
References
Nicolas Boullé, Diana Halikias, and Alex Townsend. Elliptic pde learning is provably data-efficient. Proceed- ings of the National Academy of Sciences, c23339912,, 2023.
Dong Chen, Peter Hall, and Hans-Goorg Müller. Single and multiple index functional regression models with nonparametric link. The Annals of Slatistics, pp. 1720 1747, 2011.
Maarten V de Hoop, Nikola B Kovachki, Nicholas H. Nelsen, and Andrew M Stuart. Convergence rates for learning linear operators from noisy data. SIAM/ASA Journal on Uncertainty Quantification, 11(2): 480-513, 2023.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural net- works. In Conference On Learning Theory, pp. 297 299. PMLR, 2018
Loukas Grafakos et al. Classical fourier analysis, volume 2. Springer, 2008
Gaurav Gupta, Xiongye Xiao, and Paul Bogdan. Multiwavelet- based operator learning for differential equa- tions. Advances in neural information processing systems, 34:24048-24D0 2021.
Siegfried Hörmann and Lukasz Kidziński. A note on estimation in hilbertian lincar models. Scandinavian journal of statistics, 42(1):43 62, 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Taeyoung Kim and Myungjoo Kang. Bounding the rademacher complexity of fourier neural operators. Machine Learning, 113(5):2467 2498, 2024.
Nikola Kovachki, Samuel Lanthaler, and Siddhartha Mishra. On universal approximation and error bounds for fourier neural operators. Journal of Machine Learning Research, 22(290):1-76, 2021.
Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Azizzadenesheli, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkunar. Neural operator: Learning maps between function spaces with applications to pdes. Journal of Machine Learning Research, 24(89):1-97, 2023.
Nikola B Kovachki, Samuel Lanthaler, and Hrushikesh Mhaskar. Data complexity estimates for operator learning. Xixio preprint 10.24455.1992 2024a.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Nikola B Kovachki, Samuel Lanthaler, and Andrew M Stuart. Operator learning: Algorithms and analysis.
arXiv preprint arXin:2422 15715, 2024b.
Samuel Lanthaler, Andrew M Stuart, and Margaret Trautner. Discretization error of fourier neural operators. arXiv preprint arXio:24005 05. 02.2222, 2024.
Zongyi Li, Nikola Kovachki, Kamyar Arizadeneshelli Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. Interna- tional Conference on Learning Representations, 2021.
Hao Liu, Haizhao Yang, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Deep nonparametric estimation of operators between infinite dimensional spaces. Journal of Machine Learning Research, 25(24):1 67, 2024.
Hao Liu, Biraj Dahal, Rongie Lai, and Wenjing Liao. Generalization error guaranteed auto-encoder-basee nonlinear model reduction for operator learning. Applied and Compulational Hormonic Analysis, 74: 101717, 2025.
Vinod Raman, Unique Subedi, and Ambuj Tewari. Online infinite-dimensional regression: Learning linear operators. In International Conference Algorithmic Learning Theory, pp. 1113-1133. PMLR, 2024.
Matthew Reimherr. Functional regression with repeated eigenvalues. Statistics & Probability Letters, 107: 62 70, 2015.
Unique Subedi and Ambuj Tewari. On the benefits of active data collection in operator learning. International Conference on Machine Learning (ICML), 2025.
Puoya Tabaghi, Maarten de Hoop, and Ivan Dokmanić. Learning schatten-von neumann operators. arXiv preprint XrXte:190111007, 2019.
Tapas Tripura and Souvik Chakraborty. Wavelet neural operator for solving parametric partial differential equations in computational mechanics problems. Computer Methods in Applied Mechanics and Engineer- ing, 404:115783, 2023.
Jane-Ling Wang, Jeng-Min Chion, and Hans-Georg Müller. Functional data analysis. Annual Review of Statistics and its application, 3(1):257 295, 2016.
Fang Yao, Hlans-Georg Müller, and Janc-Ling Wang. Functional lincar regression analysis for longitudinal data. The Annals of Statistics, (3(6))287332908 2005.
14

---

Published in Transactions on Machine Learning Research (08/2025)
A
Appendix
B Fourier Linear Operators
In this section, we provide a formal treatment of Fourier linear operators and the corresponding parametriza- tion in FNOs. Recall that, in the Fourier Neural operator, one assumes that X' = T and the kernel is translation invariant. This implies that Ko defined in Section 1.1 is convolution operator. That is,
(kg v) = J ko - x) v(x) dr.
Kg v = kip U,
where
The convolution is done elementwise, (K) EE= (Molyy * myy) (v), where [Koliy T + R is the scalar- valued kernel defined by the (th component of ke and (Kav)); is the 7th component of a R9-valued function. Similarly, V/ TT + IR is the jth component function of IRR-valued function v. Next, using the linearity of the Fourier transform and the Convolution Theorem, we can write
(Fov),=F1 Σ F(hool) ((Hols)F(v))
where F is Fourier transform operator, and F-1 is the inverse Fourier transform.
Here, F([kely) zd + C and F(wy)= : Zd + C are Fourier transforms of [Kolig and "y respectively. Note that only discrete Fourier modes are defined because all the functions are defined on a periodic domain T
The key insight in FNO is that instead of parametrizing the kernel ke, we parametrize its Fourier transform F(ka) directly. That is, we parametrize the kernel transform operator as (Kzu), = F-1 (Ein [Arlú F(v;)) for some Ag zd + CPxp that maps Fourier modes to complex-valued matrix. Using the linearity of the inverse Fourier transform, we can write this more succinetly in a matrix form as K. e F- F(ri).
Since F- (AA F(v)) is function defined periodic domain T it has a Fourier series representation. So, we can write
FAs F(v))()= = Σ (m(()) (Fe)(m),
mEZ4
(m 22x (mm.)) and the mh Fourier coefficient of F- F(v)) is Ag(m) (Fo) (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 practical standpoint. In practice, Ag is a trainable parameter, and it has been observed in Li et al. (2021) that parametrizing Ag as a function from Zd to Cvxp yields sub-optimal results, possibly due to discrete structure of the lattice 2d, So, one picks a large K > 0 and parametrize Ag as a collection of matrices (As(m) : m E zd such that |m// S K). In this case, the sum contains S K'd terms and thus always converges, If one still wants to deal with the infinite sum, a standard assumption would be [Ayli E el (2d) for all (i,5) pairs. That is, Emezi (m))sl)) < for all (i, pairs. Then, the Weirstrass M-test implies that the sum above converges uniformly over all y E T
Reparametrizing K. F-g F(v)) was proposed by Li ct al. (202)) from the perspective of the convo- lution theorem, as discussed earlier. However, more natural way derive F F-'(AB F(v)) from Ko is assume that hp has Mercer-type decomposition.
Proposition B.1. Let kg zd CopP be kernel with decomposition.
[bo(,
Σ [Aa(m))is (m(()) ( v(i,)) mezg
for some Ag Ap:Z* 2d CPxp such that Ag E (Zd)). Then, Kov FF- F(u)) for all e V.
Given such decomposition, a simple algebra shows that [ooy, x)ay sP (x)(x [Ag(k)]s (a()). In other words, (k)(k) are the eigenvalues of the integral operator defined by the kernel [Kolij- This suggests that
15

---

Published in Transactions on Machine Learning Research (08/2025)
the Fourier layer of FNOs is parametrizing the eigenvalues of operator while fixing the cigenfunctions to be 99''.. So, setting As(m) = 0 for m E & k amounts to parametrizing the low-rank version of such operator. This viewpoint shows that FNO is just a special case of a Low-rank Neural Operator defined in Kovachki et al.
2023 Section 4.2).
More importantly, Proposition B. (see Appendix B.1 for the proof) provides a natural way generalize Fourier Neural Operators. That is, can consider (kv(y, x)lis Emez [As(m)]is (y) (x), where J is some countable index-set and {#mm {6m me.T are some orthonormal sequences. Some common orthonormal sequences that allow efficient computation like FFT include the Chebyshev polynomial and wavelet basis. Some works have already explored the practical advantage of replacing Fourier basis with wavelet basis in certain problem settings Gupta et al. 2021 Tripura & Chakraborty (2023)
B.1 Proof of Proposition B.1
We now end this section by proving Proposition B.1
Proof. Let Au((m= == [Aa(m)] and assume that
<))x = Σ
{ms(m)) 5m (m(()) (1)) @ (m()x).
mE24
Using this decomposition, obtain
(Kov).(y)
Σ [ka(,, (z(x) dr
(ms(m) pmll)) (m) (x(2) de
mezd
Σ (m)( /nv (=)()) de.
Σ mEZd
(m)
j=1
Note that swapping the integral and the summation justified through Fubini's because the sum over 2d converges absolutely (as Ag E (1) and T is a bounded set. Since
JN 4 g-m(x)) (2))))) dr fra u =
can write
(Kov);())= Σ (m(l)) Sy F(v;)(m).
mezd 1=1
Next, consider the function w ;= F- (Ei Ary F(y))) Our proof will be complete upon showing that w(y) (K) for every E T Since the function T C is defined on periodic domain, it has Fourier series representation. That is,
w(y)= = Σ 2 (mmam))) F(w)(m)
Σ 2n Kmmyy
Σ F(z;)(m).
mEZd
mE24
j=1
(E Xi F(e;)) (m) = Ei dis(m) Fm)))(m). As usual, Ag E El implics that the sum above converges uniformly over y E T Recalling that (m) = e ((m.)))) we have shown that (Kor):(y) w(y) for all E Td. This subsequently implies that
where the final oquality follows because F F
Σ Ais Fles) Flo)))
(Kou), = = F-1
16

---

Published in Transactions on Machine Learning Research (08/2025)
Finally, using the linearity of the inverse Fourier transform and writing this in the matrix form establishes that Kov (Ag F(v)) for any E V.
C Proof of Proposition 3.1
Proof. Fix E V and define == (A F(o)). By definition of the operator F= F())), have
w = (AF(u)).
Using the Fourier series representation of wo, we have
w(+)
Σ 2m (Fw)(m)= mE2d
Σ
2 Am F(v)(m).
mE24
This step is rigorously justified because A E ll. Noting that
(Fv)(m)= = f
e 2n Rmma) v(x) dx = (p-m, 1)
write
w(.) Σ
2 t(m,)) Am (p-mi L2
mezd
Thus, w = Emmgz Am (p-m, 12 Pm: where the convergence is uniform over Td. This implies that
(FF()))
Σ
Am (p-m, u) Pm.
mEZ4
Since this equality holds for every V, have
F ((F()) Σ
Am im @ P-m-
mEZ4
D Technical Lemmas
In this section, state and derive some technical Lemmas that we use prove Theorems 3.2 and 3.3
Lemma D.1. For any HT RR) we have
| (2 |m
(4- u)
Vm E Zd (0))
Proof. Fix m E 10) and let |myl = mm/0 = maxisied [m/]. Clearly, my * 0. Integrating by parts times with respect to variable xy in x = (I1,..., Fz), we obtain
(0-m; u) f u(x)e 2mi(maa) === (-1) / (0) i my) dr 1 1 2t i imm)
-2n 1(m,x)
) (4- 05 0,
Here, all boundary terms vanish because Td does not have a boundary ( Grafakos et al. Theorem 3.3.9)). Taking absolute value on both sides, we obtain that
2008
Proof of
|myl" 1 (yp u) (2m) ( (p-m 07
Finally, using the fact that m. 0gu31 < |1lly completes our proof.
17

---

Published in Transactions on Machine Learning Research (08/2025)
Lemma D.2. For any HT ((T,,)) we have
Σ (1+ (m+1m (p-m, u) 15 | mEZ4
Proof. Fix m E {0) and let |myl = |m/ = maxisisa [mm]. Clearly, mj * O. Integrating by parts 5 times with respect to variable zj in x (EI....,Ia)) we obtain
((u))--2n((mat f u(x)e a) de = (-1)² / (z) Tu
e 2n 1(m,a)
1 2T immm 1mmm)) (p-m: 07 u)
(0-m; u)
dx
(-2 my)*
Here, all boundary terms vanish because T does not have a boundary ( Grafakos et al. 2008 Proof of Theorem 3.3.9)). Taking absolute value on both sides, we obtain that
|myl" (p-mi u) | (2x)* -* (p-m;
Noting that |mm] = |mo squaring and summing over all m E (0) to get
Σ
|m|
22 (p-m u) | (2x)*
Σ
1(8 03)) 12 (2 110gu|
(0)
mEZ
where the final inequality uses Parseval's identity and the fact that ozu E L2(TT, IR). Thus, we obtain
Σ (1+ (ml (4--m; u² 2
Σ (1p-m, u) p+
|m 12 (p-m, u) 1
me74
meZ4
mE
< || + (2T) -2 ||aj ul
||ul + 1107 ull2
||
completing our proof.
Lemma D.3. For any u E Ht" (To, IR) such that 8 2 O and K E Zoyo, we have
160 12 |u| A
Σ
K2
mEZU
Proof. Observe that
Σ
1p-mi u)
Σ
(1+ [m[ (p- u)
(1 + |m (2x)
mEZd
mEZd 2
Σ
(1 + |ml (pp m u) 1
1 K25
mEZ
||ul
<
K2s
using Lemma D.2
Lemma D.4. For any E HTd, IR) such that s > d/2, we have
3d
1 u) 15 1/
2s - d VK20-1
18

---

Published in Transactions on Machine Learning Research (08/2025)
Proof. First, use Cauchy-Schward to get
Σ mEBS
11--m; u)
Σ me2
(1+ [m|2a]] (p-m; 2) p
Σ mEZ
(1
+
m 2
n.. To bound the second term, note that for any j E N, we have (m E zd |m/x =i = 2(2j + 1)d-1 This is because one of the entry of m has to be #ÿ and other
Lemma D.3 implies that the first term is <
||||
d -1 entries could be anything in {-j -1,00,,,,111 1............ So,
22j
jaa-d1 5dd (00
f 22otd-1 di 2s d K2s-d
3
Σ mEzg
3d Σ j>k
m
2$
(2+)
jsk
for all s > d/2. Thus, overall, we obtain
3
Σ mEZ
160 u)l 11l|xx V 2s - v KK2a-d'
completing proof.
Lemma D.5. Let {j/N: j 1O,..., -1]d be the N-uniform grid of 10, 179. Then, for any m e
zd NN have
1
2x i(k m(k-m))))
1[k m (mod N)).
Nd
EG
Here, we say m(mod N) 36 zd such that k Nē m.
Proof. We first prove it for d = 1. For this case, we need to show that
1
2x i(k m) 1 mmmod N)).
N
First, consider the case where = TN + m for some T E Z. Then, 2 ( e = by Euler's identity. Thus, the overall sum must be Next, assume that * m (mod N). Then, the geometric series formula implies that
- 2 iiii i(kk
Σ 2x mk
N
2x 1(k-
Here, the final equality holds because 2x i(k-m) by Euler's identity, whereas 2 i(k-m)) & + for every {0, ...,... N 1}. This completes our proof for the case d Next, to prove it for general d, we write the sum as d-fold summation
N-1 N
d
Ad Σ 2ri kirkk-m,))
Σ
2n i mi ... 2 i(ka (kka-aa))
Σ 0=
20
Nd
ZEG
Using the result of d = 1 case for each term in the product, we have
2x isk m.z)
1 [k, = my (mod N)] 1[k (mod N)).
Nd
ZEG
[=1
19

---

Published in Transactions on Machine Learning Research (08/2025)
Lemma D.6. Let HT IR) such that ||ll B and u. = {u(x) x G} be its volues the uniform grid G. Then, for all pml N, we have
DFT(u M(m() - (10-m, u) 5
Σ (P-ceNtm)iu))
(E22
Proof. Recall that
DFT(w>)(mm)
1
Σ
u(z)e
2n i(m.a)
Na ZEG
Pick some M N and write
u(x) Σ u) @2ri(kaa) + u(xx - E
(p-ks u) eZ o2tr((e,e)
kEZ
kE2d
We can then write
DF (-m)
(0-ks 21) e ((te) ))
Σ
(p-k. u) 22 + u(x)-
Σ
2x t(m,ax)
Nd
REG
KEZ
KEZd
Σ
(5- u)
Nd
2x fariikk-ann m,x)
+
Na
u(z)
Σ (p-x, u) e (2tilbhae)
e
2x i(m,a))
kEzd
DEG
zEG
RE
kead
Σ REEd
u))
1[k m mmod N)]
+
u(x)
Σ kEad SM
(v- u) 2tikk
i(m,a))
Nd
DEG
SM
where the final equality follows from Lemma D.5 as |m/oo < N. Note that we can swap sums over G and Zd
in the first term because the sums converge absolutely when s > d/2 (see Lemma D.4. Thus, we obtain
DFT(u (FF(())(-m)) (-m)) - (p-m.u)15
Σ kEZd
(0- 1 mmod N)] - (4--m, u)
1
u(x)
Σ
(4-ks u) c2n i(k,a)
2x i(m,a)
Nd
kERd AM
Using the uniform bound over e G for the second term and the following identity for the first term
Σ
(p_ u) 1[k = mmmodd N)] - (1p-mm u) = Σ
(p-x: u) 1 = mmmod N)},
kEZ4 SM
kead KE
Sar Mm)
we obtain
(FF((M)(-N)) - (p-mm u)
Σ
(p-k, u) 1[k: = m(mod N)]
+ sup
u(x) Σ
ke u) 2x (01())))
#EG
Mm) {m)
KEBy
20

---

Published in Transactions on Machine Learning Research (08/2025)
Recall that we have (i) (p-k; u) e2 - B and Exeza ((p=: u) c oc for d/2 using Lemma The Weierstrass M-test implies that the second term converges 0 uniformly over æ E Td as M op. Thus, obtain
D.4
Σ kEEd SM Mmm
(0- 1[k = m(mod N)] M
Σ kEZ* (m)
(p- 1 = mmmod N)]
Σ (P-((N+m)))
(02")(0)
which completes our proof.
Lemma D.7. For any E N such that & > d/2, we have
Σ
S 3
kez*/o
Proof. Recall that Im E Zd
|m/ = | = =2(2j + +1)211 This because one of the entry of m has to be
+j and other entries could be anything in
1...,. Thus,
2(2j +1)-11
2 1d=
3d
-+ 3
nT² gd-2
j2z
12 6
REZ"((0) (0)
The third inequality uses 2s d < 1 as d/2 and s sEN.
E Proof of Upper Bound (Theorem 3.2)
Before we prove Theorem 3.2 define
we need some notation. For any T E such that T Emeza Am im 2 m-
r(T)
E (aww)pp
[Tv FTu--1123
E (w,w))yus
Σ mezd
Im (4-m; v) (1--my w))
F(T) = 1
Σ Te: -a:--lllft will?
Am (p- Ui) - (m- will?
mEZd
where {(,,, w is the sample accessible to the learner on a uniform grid of [o, 17d. Then, using these definitions, we can write
E, C. T.P) = (
((T))
inf TET ((T)
E
(((T))
inf
r(T)
+ inf r(T) inf r(T),
TETK
TETK
TET
where Tx the truncated class defined as
Tk =
Σ mEZd
Am Fm 1 pm
sup
Pm SC
meZd K
Furthermore, defining
Tx E argmin F(T), TETK
21

---

Published in Transactions on Machine Learning Research (08/2025)
can decompose
En ET T. () = E r(TK) - r(Tk)
=
+E r(Tx)
inf r(T)
+
inf
r(T)
- inf r(T)
TETK
TETK
TET
(11)
(II)
First, is easy see that
(III) S sup inf
r(T) - r((k)l
TET TKETk
To upper bound (II), let T TK such that r(Tk) = infrETx r()). Formally, for every 6 0, we may only be guaranteed the existence of T such that r(Tx) I infretx r(7) However, 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 we can write
(II = E(r(Tk) -[+]) + -[T -((T))
The last term of the vanishes because B r(Tk) As for the second term, Tx minimizes empirical loss over the samples, implying ?(Tk) - 7(Tk). For the first term, we use the trivial bound r(Tx) F(Tx) I supreTи Ir(T) - F( Overall, we obtain
Ir(T) -(T)
(I) S E
sup
TETK
Finally, we upper bound the term (I). Given K and N, for any T E Tk such that = T=E Emerg Am Pm 0p-m: define
FN (T)
Am DFT(u))(-m) (-TT(w))(mm)
1p-m w;) 12
n
MEZZ
mEZZ
Technically, the term (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 3.2
The second term is introducod purely for technical reasons make our calculations work (see Section E.2 Since the second term does not depend on T, our estimator TN is still the operator obtained by minimizing Fx- Then, note that
(T = - Fxx ( E(Fx (T (fx)) + E(Fx
rr(fx)](
Note that the second term above satisfies FN (T - FN (Tx) S almost surely because TN minimizes Fx over all T' Tk. For the first and the third term, we use the bound
Elr(TR)) - (T < E sup |r(T) - (T)I and [FFx(Tk) - r(Tx) < El sup |r(Z) (T)]].
TETK
TeTK
Thus, we have
(1) 2
sup [r(7) FN (T)
2
sup (r(T) - -F(T)] + 2
sup [i(T) - Fxx (T))
TETk
TETK
TETK
where the final step uses the triangle inequality. Combining everything, we have established that
(T K T. p) < 3E
sup |r(T)- ((7)-f(1)) F(T)) + +2E TETK
sup [(T) - Fx(()]]] + sup inf Ir(T) - r((k)] TET TRETk
TETK
The first term is the statistical error, the second is the discretization error, and the final the truncation error. Next, bound each of these terms individually.
22

---

Published in Transactions on Machine Learning Research (08/2025)
E.1 Upper bound the truncation error supreT inf eTx Ir(T) - r(Tx)]
Pick any T E T. Then, there exists sequence such that T = Emeza Am Pm Q-m- Define
Tk = Σ
Am Pm 2 p-
mEZZ 5K
Clearly, Tx E Tk. Then, we have
r(T) r(Tx)) = E
1|TT wlli \TKU - w11[.a]
(w:ar)~u
[|TT|l || + + 2(T(TK T), w)l
(v.ar)--u
Σ MEZZ K
(1p-mi 1) R22
Σ
Im (4- o) (fmms w)
(1:4))eju
meZd 2
The final equality the following facts. First, have |Tulll 11Emezu Am (p-me 1) 4m I2= Emez' (40-m, u) 12 Analogously, ||Txvl22> Emezy |mml 2 (4-m,, u) 12. As for the second term,
we use
Am (p- 1) pms w ) Σ
-Uk-TTuuu
Σ
Am (p- v) (P W)
mER
Next, using the fact that am S C' followed by Lemma D.3 the first term is
BCC K2s
Σ
|mm ( RS
mEZ4 K
As for the second term, using |mml I C followed by Cauchy-Schware implics
2CB2
Σ Am (m-mm, u) (pmm w) 2C
2C
Σ
160 u)
Σ mEZd
1pm, p2
k
MEZZ K
mE K
where the final inequality holds because of Lemma
D.3
Since T T is arbitrary, we have shown that
TET TxETk (T(T) r(Tx)) < B²C + 2)
(²
sup inf
K2s
K2s
E.2 Upper bound on the discretization error 2E supreTx (P(T) - Px
Fix T Tk- Then, there exists (Am) ] with Amm s C such that Ezg recall that
An Pm Pm @ p-m Then,
FN (T)
Am DFT((( (FT(w;))(mm)
2+ 1 n
Σ
Σ
1m wi) 12.
7
mezd k
m
Moreover, we also have
F(T)
Dm (p-mm vi) (p-m ws))
Σ
14 wi) 1?,
1=
mEZZ
i=1 m mEzd
23

---

Published in Transactions on Machine Learning Research (08/2025)
which yields
(F())-(()
Σ Σ
(IAm DF DFT(W;) (-m)) - amm (m- Uz) - (p-mm wi)1?)
1=1 7d
Next, we define
0im (FF(())(( (p)-m: and fam (FT(w;") (-m) (10-my wi)
We can then write
Pm DFT DF:(2: (-m)) -DF (w:") (-m))²
mmm (p-m; 0i) (p--m; wi) + Am Orim Biml
$ Dm (p-mi vi) - (p-m; wi) 12 + 2m (p-mm vs) 10- wi) Am Bamll + Am -8mml
Thus, we obtain
1 n
(N(T) F(T) S
(2 Am (p-m; Us) (m- wi) Am Bamll + Am Olarn Biim 12)
n2
mEZ4
S K
< max ME
2 (1mm (p-m,, Uz)) + (p-m- wi) 1) Dm - Bimll + Pm - Bim
mEZ4
Next, using Cauchy-Schhee Schehay inequality, the first term of the summand can be bounded as
Σ
Dm (5--m Ui) Pmmaim Beml
WERd SK
Dmm B.ml 1
Σ
Pmm (21 + /m122) (p-m,, vi) 12
+ mm 2g
mE2d SK
mEZd
Am
Biml
BC
1 m 2s
mEZd MER SX
where the final inequality uses Lemma D.3 and the fact that |mll S C. Similar arguments show that
Am Bim
1 wi) 10mmam Bimm) S B
|m
2g
mezd
MERC
Overall, we have shown that
Dm Olim
Bim
(N((T) - -(T) < max
2B +1)
Pm -Bm
xE mn]
1
m
mEZU
mEZo
Now, recall that Lemma D.6 implies
max max{/amm 18ml 5
Σ
(e=(eN+m):u))
RE2d)(0)
24

---

Published in Transactions on Machine Learning Research (08/2025)
which subsequently yields
2
Am0 Biml S (C 1)2
E (e)(
(E2
Thus, we have
Σ
Am Biml
MEZ SK
< (C+1)
Σ
Σ (/22
(00 (e-((eNm)::1)
mER
(C++))
Σ
1 1 m + EN (E2
Σ
Σ (ET*((0)
(1+ Im + (p-
mEZ Sx
where the final step follows from Sahwhy-Schwarz inequality.
To upper bound the first sum within inner parenthesis, note that | 2 1 2 -i11o-N11 N/2 1f Here, we use the fact that |m/ox K S N/2. So, we have
Σ (E2
2
2s
Σ
2 T² 3dd-2 3d-2
m EN
183
N
where the final inequality uses Lemma D.7 Next, note that
Σ Σ (1+ ++|m+ m 2 (V-(eN+m)) u) 125 E (M MEZA
(sp (,) B²
LEZAN/0}
REZ
where the second inequality follows from Lemma D.3 The first inequality holds because for each k E gd, we have ((m,e)= L) m + +NN = k, m E Z and č E 2dd MOOH I That is, for each E Zd, there is only one possible pair (m, C) such that k m+NN. Suppose, for the sake of contradiction, there exists & E 2d such that two distinct pairs exist in the set, namely (m1,6) and (m266), Note that mı N (m²+ = h- k = 0, which implies (m) m2) = (E2 N. Clearly, we cannot have l2 = E1, otherwise, we will have m2 = m1; contradicting the fact that there are two distinct pairs. So, we must have la o l,. That is, 16/ f1/00 2 1, and thus |m, mol 2 N. Morcover, [m, m2/ I |m |ma 2K, which implics that 2K 2 N. This contradicts the fact that K N/2. Therefore, overall, have shown that
Pmmaimm Biml 2 2d B² 1)²
Σ
N2*
MET SK
Next, we have
Dm Olim
Bim 12
2T//3d-2 B(C +1)
Pmm - Bim 12
m 28
No
mEZZ
mEZa
Therefore, by combining everything, we have shown that
(x( F(Z)) 20+1 B² + 1)2
N TV30-2 B²C 1)24"
20+ 1C(1BB(C' + 1)²
23d <2
TT 3V33-2
N2s
No
The final inequality holds when N 2 2--1 3 which is satisfied long as N As T E Tk is arbitrary, we have shown that the discretization error
20+3 T / (C 1)2 S
2043 2T
sup [(T) Fx(TT) 2F
TETK
N
N
25

---

Published in Transactions on Machine Learning Research (08/2025)
E.3 Upper Bound on the Statistical Error 3E (SuPreTx Ir(T) f(T)]]
In fact, we will bound (supreT (r(T)- F[T) This can be viewed the limit of the statistical error - xc. To that end, let o. on symmctrization arguments show that
denote iid random variables such that og Uniform((-1,1] Standard
1
sup (r( F(T))
2E
sup TET
1
Tu;
we P.
TET
n
2
sup /Alpe SC
Σ
Dm (50 (1--m: Us) - (60-ms wi)l
n i=1
Note that
Am (4-m: Us)) (40 wiy??
(Am (p-m, Uz)) - (p--m Wi)) (mm (p-m m. Us) - (60 m wi))
Am Am (p-m; U1) (p- Am (p--m vi) m, Wa) Am (p-m ws) (0- vz) + (4--my ws) (4--m; wz)
Amm 2 (p-ms v2) | (Am (p--m Us) mm-m wi) + Am (p--ms wi) (p- 13)) + (p-mm wi) 1?
The first and the last term above are real numbers, so the term in the parenthesis must also a real number. Using triangle inequality, the term Rademacher sum above can be upper-boundee as
Σ
Am (p-m, 01)) - (m: w2)12
sup
n
mEZU
12 ai
n
E
sup
|m 1 (1p-mm v2) 12
+E
sup
Am (xp (p-mm my Uz) (8- wi)
SC
mEZa
SC
n
i=1
mEZ#
(1))
n
+
sup
Σ
Am (p-ms wi) (p-mm: Us)
+E
O
(60 -m: w. 12
[Nle0
n1
m
mEZa
(ii))
(iv)
Let us start with the term (iv) first. Swapping the sum over m and and using triangle incquality yields
(iv) E
Σ (p-m,, wi) 12
Σ
E
(1p m. wi) 12
22
meza
Σ
(p-m, wi) 18)
(vc
mE24
where the final step follows from Khintchine's incquality. Note that swapping the sums justified because both sums converge absolutely.
26

---

Published in Transactions on Machine Learning Research (08/2025)
For the term (iii), swapping the over and i and using the fact that 1mml C' yields
(iii) E
sup
Am (p-m, wi) (p--m Uz))
i=
mEzd
=E
sup
Am
Ji (0- wis (p (m-mm Us)
SC
mE24
S CE
Σ
ai 60 m. wi) (p-mm= Us}
mEZ2
1/2
SC Σ
(p-m m, wi) (p-m; Uz) 12
mEZ
where the final step uses Khintchine's incquality. Since Mml S C, we can use the same arguments to show that
1/2
c Σ
Σ (p-m, 2i) (40- wz} 12)
72
mEZ
and
1/2 (p-mm 24) +)
5 Σ mEzd
Next, note that we can bound (Po, u) | S B for all ||l||æ S B.
Moreover, Lemma D.1 implies that
(p-m; u) S (2x)* lm] for all + O. Thus, obtain the bound
B
1/2
(i)
BCC² vn
+
Σ
1
(2Th
m oc
mEzai (0)
S C²C
B²C²
1
1
Vn
(2Th
24
Vn
mE? (0)
B²C² 23d-2
< CBC
Vn
(2
Vn
where the final inequality uses Lemma
D.7
Similar calculations can be done to show that
(ii) < BCC 1 + Bd
Bdd
Vn and (iv) S B² Vn
+
(2x)
(2t 28
Vni
Thus, we have overall shown that
E sup |r(T) - -F(TI] 22 + (ii) + (iii) + (iv))
TET
233d-2 2
1
C2 + 2B + B2)
11
(2T))
Vn
(B²
n 233d-2
1+
Vn
(2
5 B² + 1)²
<
2
Vn
where we use the fact that
7 2dd-2
T"
1
<
(2T 228
228
726
225
4
27

---

Published in Transactions on Machine Learning Research (08/2025)
2s > d and 2 1. Therefore, the overall statistical error is
3 sup (r(T) - -(T)
8B (C++1) 1)
vn
TET
F
Proof of Lower Bound (Theorem 3.3)
Proof. To define difficult distribution for the learner, we need some notations. Let
1
tho so and Vm v2 (p-m + pm) for m E (0).
Note that 1m T + R is real-valued function such that llumllzz = 1. We work with v/m 's to ensure that the distribution is only supported over valuev functions. For any Aarkeez such that d = A E R, the operator 7 =mmzza AmPm 8 m- satisfies
1 Tum / (Am Pm + X A- m)
Am
(4- m + pm)) Am Vm zoo(o)
V2
V2
Clearly, Telo Aotio Next, let us define sequence {Tmm finme such that
B and 7m V8 + 1 mm]
B
Vm E 10).
70
+
Finally, define set
{m zd my E N and m, =0 Vj + 1}.
For any M, E N. define IN {m E J my # 0 (mod N) and m S M). Lot r E 2d such that r E J and ri 1. That is, r (1.0,0....,000 0). For any g E 2, we write gr (g, 0, ............ 0).
We now describe difficult distribution for the learner. To that end, first draw : {mm Jmzz such that S. = C-m is drawn from Uniform({- 11, 1)). Then, given such &, let μe be any joint distribution on V x W such that its marginal on V assigns 1/3 mass uniformly on { {Tm tm m E JN }. 1/3 mass on 7o%o, and the remaining 1/3 mass on *K+H)r ())+))r for either j = or j = 2 ensuring that K + j * 0 (mod N). Moreover, given a yath drawn from the marginal of Pę, assign w to be EuTuth k o O. On the other hand, if 0, then w Enr INr Nrr-
This is valid distribution
||01
E
|
Σ
(m Tm ) = for all j +
KENd S0
kENd 14
pm
|m
24g
< (s + 1)²² |m|² 12
B²
Similar arguments show that 11 s B Next, we establish that
B2
1
2
1
E E
+
3(8
+
8n
(K
+
2)2x
N2:
Since the lower bound above holds in expectation, use the probabilistic method to argue that there must exist a sequence g* such that & ( (T 2
n²
3(+1]
Sn
(K
+ N
28

---

Published in Transactions on Machine Learning Research (08/2025)
We now proceed with the proof of the claimed lowerbound. Let TW denote the estimator produced by the algorithm. Then, there exists {Am)meze gx
such that
Σ
Am Pm @ p-m-
mE
For convenience, we will extend the sum to the entire zd and write TH Emeza dm Pm 2 p-m, where Am O for all m k
Given a &, we now loverbound the expected loss T on peg. Using the definition of the distribution pe: we have
E (oyeo)yuae
| U wllia|
Amm - Em
2 2/2 +
1
ENr YNr that
1 12a
+
110 ((K+))r - -((+2) ((K+s)) 1t
3
JMM
3
3
mEXN
2b1 + +
2
Σ
Im 1m 50]+
+
3
3
3
mETy
7/ 3
1 50
22 + 1
3 +
+2K+2
2
3
Here, the first incquality use the fact that (nm {m) whenever Xm 0 and (eo, 0. The second inequality uses the fact that E IE as long as N > 1 and that ((K+s)r 2 (K42) for E (1,2).
Next, we establish the upper bound on the loss of the best-fixed fixed operator. Given &, define an operator
T
Σ
5m Pm @ P-m
mEZy 50
Clearly,
E TET (0.w)~u
inf
[[ w|12=11]
S (0,w)~ii
[|[Te - -w1
= E [| - w/l 1|22| |0= rovool = 7000l + [[]T0 - wl12e11 1 * rovo] Plu # rot
S 110 EN, 7N. 2Nr112
NNr
3
where we use the fact that Teu = whenever == YoCo and Tgv otherwise. Overall, we have shown that
E (w.w)rM
|iT
w11/2]]
inf TET
T| w w/1b |||
(v.w)~p
22
2a-2 + 7Nr
2
22,
16 50 +
3
3
(1[7,55 50
B2
|T (1113))
+ +000
3(s + 1)
(K + 2)22
where the final inequality holds because 70 7/
B and ([++2)r Vo+1(K+2]=
B
Veti
Next, we establish loverbound of N2 To that end, let S, = ((v, w. | denote the samples accessible
the learner over the uniform grid of size N. Recall notation uf" (v:(2)) i G} and w." [w:(x:)
29

---

Published in Transactions on Machine Learning Research (08/2025)
E G} for discretized samples. Take sample (o, wy) Mg- Then, must have U/ nollle for some k E zd. Consider the case that k + 0. Then, by definition of the distribution Mg. it must be the case that k * 0 (mod) N. Then, Lemma D.5 implies that
(F-(x))(-0)- Na
Σ ZEG
7h (x(()) e 1(2,0)
Th v2N
Σ ZEG
Ee-2righe
Σ
(k,,e) 0.
On the other hand, if v; - yov0, then we have
DFT(O))(-0) = Nd
Σ 100)(() = Σ
70 Nd
-0-
ZEG
ZEG
Additionally, when v; 7000, we have W4 YNr N'r In this case, Lemma D.5 implies that
DFT(w))
'Nr Na
Σ (2)
YNr V2Nd
25r (ora))
2x ((NiN))))))
2Nr V
V2
LE
Using these facts, we can write the empirical least-square loss as
Σ
7m
(FT("")) (-mm) DFT(W; (-m))
mEZE
Ao
Σ 1[00=000ooo + Σ 1lu * rov'ol [FF((u;)( (-mm)
n
Σ
Σ
Am
mE7d
(0)
Thus, the least squares estimator for Ao must be No = V2YNr. That is,
2B² X 27 (s Nrl
2B
(s 1)N2s
Note that this choice of To is valid as 2o s 1. Thus, far, have shown that
(1,00)-riig [ v - will wl122]
E (0,w)~pe
[| w w12
B²
1Rre S
1
3(8 +
(K + 2) N2s
Our proof will be complete upon establishing that
[
oi]
E
E Samue
> 8n
J
for an appropriate choice of M. To that end, let uy be the marginal of मę on V and SY E y denote the restriction of samples S,, E (V x Win to its first arguments. Then, we can change the order of expectations to write
E [ive s oI] = sx-ux [e
[ s si]] 2 ž Pla $ SK]
SAree
To understand why the final inequality holds, observe that when the event 7/4/ & Sy occurs, the learner has no information about & This implics that & and 7 are independent. Consequently, given that 7, & sy the event X,Gr < 0 has probability of at least 1/2 since &, is sampled uniformly from (11,+1).
Next, it remains to pick M such that
Pla th $ SV
2
JN
4n
30

---

Published in Transactions on Machine Learning Research (08/2025)
To get this, choose M 2n. It is easy to verify that [ 2 whenever N> 1. This is true because more than half of integers in (1, 2n} are divisible by N. Thus, we have
Phiti & s (1
1 3|J
1
1
2
3n
2
for any n 2 1. Noting that |J S 2n completes our proof.
G Additional Experiments
In this section, we present additional experiments with y-axis on log scale to illustrate the docay rate. Each plot includes the fitted slope and the corresponding smoothness parameter 7, The data generation, training, and evaluation setup follow Section
4 For each input. function e sampled at smoothness 7, the noise term is sampled smoothness 1.5 y. Figures
and 0 plot the statistical, truncation, and discretization errors, respectively. In each panel the reported value m is the slope of line fitted to log(error) versus log n, log K, or log N, appropriate.
5
The statistical error decays faster than our predicted 1/v2 rate, with slopes close to or better than -.0,, even better than our lower bound. This may be due to the Gaussian distribution used in experiments, rather than worst-case inputs. Additionally, the error appears to vary slightly with 7, suggesting that smoother inputs might allow sharper statistical rates, least for well-behaved distributions.
For truncation error, the observed rates generally faster than predicted for 7 1.5, 2, and slightly slower (but close) for 7 = Recall that our theory predicts m to be 27y
Interestingly, the discretization error remains nearly constant with a slope around -1.1 across all values of whereas the theory predicts the estimated slope to be This discrepancy may stem from the experimental setup: our theory considers the test resolution N2 + oc, while the experiments fix a finite N2 = 512. A more detailed analysis under finite training and testing resolution could help clarify this behavior.
1=1
2=2m-=1165
m=25
y=3,m=-179
10a1
Yosting Emor
30-2
10-3
800
1000
Training Sample Size (n)
Figure Statistical error decay across sample sizes for different smoothness values 7.
31

---

Published in Transactions on Machine Learning Research (08/2025)
y=15,m=-500
10"1
y=2
2=
y=3,m=-566
Testing Emro
10
10"--
20
40
60
Truncation
Figure 5: Truncation error plotted against truncation mode for various values of 7.
10a
1=13,m=-1.2
y=2,m=-115
Testing
10
50
100
150
200
250
Figure 6: Discretization error a function of grid resolution for various smoothness levels 7.
32


Reviews:
[{"review_id": "py6sh8ssRS", "reviewer": "Reviewer_Fggu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weakness:\n1. I don't see how the section 4 connects to previous sections. What is the conclusion of section 4 and how does that help to enhance the main message of the paper?\n2. The information density in Figure 1/2/3 is relatively low. The conclusion draw from the three figures seems well known. Considering plotting the statistic error under different resolution or truncation by different lines under the same coordinate systems, which can give reader a more intuitive understanding of the relationship between error and K/N/training sample size\n3. The paper deliberately avoids dealing with nonlinearity, focusing only on the linear core of the FNO. While this simplifies the analysis and provides foundational insight, it limits direct implications for practical, multi-layer neural operators used in real applications\n4. The discretization error analysis is tailored to functions sampled on uniform grids. This excludes many real-world cases where data is irregular or unstructured, which restricts the estimator's utility in practical operator learning settings\n\nstrength:\n1. The paper makes contribution by formally identifying and separating the three major sources of error in operator learning (statistical, truncation, and discretization) which provides conceptual clarity and guides future work on neural operator analysis.\n2. The statistical error bound is derived using a refined Rademacher complexity approach, giving bounds that are independent of the truncation level.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper develops a theoretical framework for understanding operator learning through the lens of a simplified linear within FNO. The authors identify and analyze three key sources of error—statistical, truncation, and discretization—and provide precise upper and lower bounds for each. Their results offer new insights into multiresolution generalization and lay groundwork for a deeper statistical understanding of neural operator architectures.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Explicitly explain in Section 4 how the empirical results relate back to the theoretical error bounds (e.g., do they validate the predicted convergence rates? Do they expose gaps in the bounds?). Please summarize the key takeaway and its implications for the broader theoretical message\n\n2. Add a discussion (possibly in Section 5) that more explicitly outlines how the linear results might extend to nonlinear operators and multi-layer FNOs, and what technical obstacles exist\n\n3. Acknowledge the restriction to uniform grids more explicitly and suggest potential strategies for handling non-uniform or unstructured data (e.g., quadrature, random sampling, interpolation)", "broader_impact_concerns": "Like previously said, the focus on linearality core of FNO and assumption on uniform grid significantly limits the paper for broader impact. How does this prevent the community from apply to a broader use cases will significantly help reader to understand the contribution of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rvsUZ4YU0S", "reviewer": "Reviewer_LPXe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nI do not have much background in working in operator learning, but I am convinced that the problem that the authors are trying to tackle is an important and interesting question. The authors do a great job of introducing the problem, and pitching it against existing works. Although I didn't have time to go through the proofs in detail, the results are very believable, and are in line with standard results. \n\nThe lower bound does not quite match the upper bound, but I do not see this as a weakness. The authors didn't have to report the lower bound, and I think the fact that they put in the effort to derive it and reported it should be commended. \n\nI also love how thorough the preliminary section is. It really makes the paper self-contained and easy to follow. In general, the whole paper is written in a way that is a pleasure to read. Thank you very much. \n\n**Weaknesses** \n\nSee \"Requested Changes\" section.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is a theoretical analysis of learning linear operators between function spaces. The authors divide the error into statistical, discretisation and truncation errors, and analyse them separately, obtaining upper and lower bounds (not quite matching).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Page 3, \"Our work aligns with the historical development of neural networks theory where the statistical properties of the linear core $x\\mapsto Wx+b$ (a linear regression problem) were fully understood before studying deep neural networks.\" This is quite a bold yet simplifying statement. There are still many unsolved problems in linear regression, many unrelated to the analysis of deep neural networks, and moreover, much of the analysis of deep learning is not inspired by linear regression. Of course I see the point that the authors are trying to make but I would change or remove this sentence. \n\nPage 4, Section 2.2: The complex conjugate notation was already introduced in Section 2.1. Also I'm a bit confused here - the codomain of $L^2(\\mathbb{T}^d,\\mathbb{R})$ is specified to be the space of real numbers, so why are you considering complex conjugates at all? Or should you change the codomain to $\\mathbb{C}$? I think you should - in fact, the Fourier basis functions $\\varphi_m$ map to $\\mathbb{C}$ by definition. You should also change the codomain of $\\varphi_m$ in Section 2.1 to $\\mathbb{C}$ as well. Please have a look at this throughout the paper. \n\n**Minor Comments**\n\nPage 2, Section 1.1, two lines below the displayed equation: a integral kernel -> an integral kernel\n\nPage 2, Section 1.2: \"When $|\\Lambda_\\beta(m)|_{\\ell_1}$\" technically this should be something like the $\\ell_1$ norm of a sequence indexed by $m\\in\\mathbb{Z}^d$. As currently written, you are taking the $\\ell_1$ norm of a single number for a single $m$. \n\nPage 5, section 2.3: In the definition of Sobolev spaces, I think it would be better to replace the \"s.t.\" with \"for all\". Also, in the last paragraph of section 2.3, you say that sometimes one takes the 2-norm of k? I've never seen this, I've only ever seen the 1-norm of k in the definition of Sobolev spaces. \n\nPage 5, section 3, second paragraph: we will also $\\lambda$ -> we will also use $\\lambda$. \n\nPage 5, equation (1): I think it would be better to write $(\\cdot)$ on the right-hand side too, or even $(u)$ on both sides, since you say \"for every $u$\" afterwards. \n\nPage 7, Section 3.2, paragraph beginning with \"To see why\", second line: $v_1$ should be $v_i$.", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "wgq7LOcvRH", "reviewer": "Reviewer_WNfE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is clearly written, self-contained, and highlights both connections to and differences from prior work. While I only reviewed the appendices superficially due to their length and time constraints, the main technical development appears sound. \n\n- To the best of my knowledge, this is the first attempt of statistical learning properties in FNO, even if in a simplified setting. As such, it may serve as a useful foundation for future work. The authors are upfront about the limitations of their analysis, including the restriction to linear operators, periodic domains, and scalar-valued functions.\n\nWeakness:\n- The numerical experiments are limited in value. They show monotonic error decay but do not demonstrate the convergence rates predicted by theory. \n\n- A bound that depends on N and K is valuable, as it helps clarify whether increasing grid resolution or spectral bandwidth is more effective under a fixed computational budget. The paper would be more impactful with a discussion of the computational trade-offs between N and K, along with simple experiments to validate and illustrate this comparison.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Fourier Neural Operators (FNOs) are widely used for operator learning, but their theoretical understanding remains limited. This paper focuses on the linear transform core of FNOs—analogous to the affine layer Wx + b in MLPs—and analyzes its statistical learning properties. The authors study the excess risk and derive bounds for three key sources of error: statistical error (from finite sample size), truncation error (from discarding high-frequency modes), and discretization error (from evaluating functions on a finite grid)", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The claim that “some of our proof techniques are inspired by their work Lanthaler et al. (2024)” is too vague. The manuscript should specify exactly which lemmas or arguments are reused or adapted.\n\n- Reproduce the error plots on log–log scales and report the slope of fitted lines. See Lanthaler et al. (2024) for examples.\n\n- Plot the curves for a few different smoothness parameter s.", "broader_impact_concerns": "I do not foresee any ethical risks associated with this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)