Minimax Optimal Kernel Operator Learning via Multilevel Training
Authors: Jikai Jin
Yiping Lu
Jose Blanchet
Lexing Ying
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Learning mappings between infinite-dimensional function spaces have achieved empirical success in many disciplines of machine learning, including generative modeling, functional data analysis, causal inference, and multi-agent reinforcement learning. In this paper, we study the statistical limit of learning a Hilbert-Schmidt operator between two infinite-dimensional Sobolev reproducing kernel Hilbert spaces. We establish the information-theoretic lower bound in terms of the Sobolev Hilbert-Schmidt norm and show that a regularization that learns the spectral components below the bias contour and ignores the ones above the variance contour can achieve the optimal learning rate. At the same time, the spectral components between the bias and variance contours give us flexibility in designing computationally feasible machine learning algorithms. Based on this observation, we develop a multilevel kernel operator learning algorithm that is optimal when learning linear operators between infinite-dimensional function spaces.

Published as a conference paper at ICLR 2023
MINIMAX OPTIMAL KERNEL OPERATOR LEARNING VIA MULTILEVEL TRAINING
Jikai Jin
Yiping Lu
School Mathematical Sciences Peking University
Institute for Computational & Mathematical Engineering Stanford University Stanford, CA, US uplu@stanford.ed.
Beijing, China
jkjinêpku.edu. on
Jose Blanchet
Lexing Ying
Management Science and Engineering Stanford University
Department of Mathematics
Stanford University Stanford, CA. US lexing@st edu
Stanford, CA, US
jose. www..blaccceettttafooo.. edu
ABSTRACT
Learning mappings between infinite cimiitedimenssonall function spaces have achieved empirical success in many disciplines of machine learning, including generative modeling. functional data analysis, causal inference, and multi-agent reinforce- ment learning. In this paper, we study the statistical limit of learning Hilbert- Schmidt operator between two infinite-dimensional Sobolev reproducing kernel Hilbert spaces (RKHSs). We establish the coormation-theorette lower bound in terms of the Sobolev Hilbert-Schmidt norm and show that a regularization that learns the spectral components below the bias contour and ignores the ones above the variance contour can achieve the optimal learning rate. At the same time, the spectral components between the bias and variance contours give us flexibil- ity in designing computationally feasible machine learning algorithms. Based on this observation, we develop a multilevel kernel operator learning algorithm that is optimal when learning linear operators between mnfinie-dimensionn function spaces.
INTRODUCTION
Supervised learning of operators between two sinnite-dimensionaa spaces has attracted attention in several areas application machine learning, including, scientific computing (Lu et al., 2019; Li et al., 2020; de Hoop et al., 2021; Li et al., 2018; 2021b), functional data analysis (Crambes & Mas, 2013; Hörmann & Kidziński, 2015; Wang et al., 2020a), mean-field games (Guo et al., 2019; Wang al., 2020b), conditional kernel mean embedding (Song al., 2009; 2013; Muandet et al., 2017) and econometrics (Singh et al., 2019; Muandet et al., 2020; Dikkala et al., 2020; Singh al., 2020). Despite the empirical success of operator learning, the statistical limit of learning an infiniteddimensional operator has not been investigated studied. In this paper, we study the problem of learning Hilbert Schmidt operators between mnfnite-dimensinn with given kernels i and respectively with 3, [0, 1) (Adams & Fournier, 2003; Christmann & Steinwart, 2008; Fischer & Steinwart, 2020). Our goal is to derive the optimal sample complexity for linear operator learning, iee. how much data is required to achieve a certain performance level.
Sobolev RKHSs H and H7
We first establish an information-theoreti lower bound for learning Hilbert-Schmidt operator be- tween Sobolev spaces with respect to a general Sobolev norm. Our information-theone theoretic lower bound indicates that the optimal learning rate is determined by the minimum of two polynomial rates: one is purely decided by the input Sobolev reproducing kernel Hilbert space and its evaluating norm, while the other one is purely determined by the output space along with its evaluating norm. The rate is novel in that all existing results (Fischer & Steinwart, 2020; Li et al., 2022; de Hoop et al., 2021) only establish rates that depend the parameter of input space. The reason is all previous

---

Published as a conference paper at ICLR 2023
works (Talwai et al., 2022; Li et al., 2022; de Hoop et al., 2021) only consider the case of the output space as a subspace of a trace bounded reproducing kernel Hilbert space but not a general Sobolev space. We refer to Remark 2.1 for detailed comparisons.
To design a learning algorithm for approximating an infiniteddimensional operator, we need to learn fiite-dimensional restriction instead of the whole operator, the latter would result in infinite variance. The mnite-dimensional selection leads to bias error but decreases the variance. A natural task is then to study the shape of regularization that can lead the optimal bias-variance trade-off and achieve the optimal learning rate. In this paper, we consider the bias and variance contour at the scale of optimal learning. Once the regularization enables one to learn all the spectral parts above the bias contour and below the variance contour, the learning is optimal. Finally, utilizing the region between the bias contour and variance contour, we developed multilevel training algorithm (Lye et al., 2021; Li et al., 2021a) which first learns the mapping on low frequency and then successively fine-tunes the machine learning models to fit the fighfrreuency output. The intuition of our algo- rithm aligns with the original motivation of multilevel Monte Carlo (Giles, 2008; 2015): we use the next level to reduce bias while keeping the variance at the same scale. We demonstrate that such a multilevel algorithm can achieve an optimal non con-parmettric rate for linear operator learning.
1.1 RELATED WORK
Machine Learning Based PDE Solver Solving partial differential equations (PDEs) plays prominent role in many scientific and engineering disciplines, such as physics, chemistry, opera- tion management, macro-economy, etc. The recent deep learning breakthrough has drawn attention to solving PDEs via machine learning methods (Raissi et al., 2019; Han et al., 2018; Sirignano & Spiliopoulos, 2018; Yu et al., 2018; Khoo et al., 2019; Chen et al., 2021). The statistical power and computational cost of these problem is well-studied by recent papers (Lu et al., 2021; 2022; Nickl al., 2020; Nickl & Wang, 2020). This paper focuses on operator learning (Chen & Chen, 1995; Long et al., 2018; 2019; Feliu-Faba et al., 2020; Khoo et al., 2021; Lu et al., 2019; Li et al., 2020; Kovachki et al., 2021; Stepaniants, 2021), i.e. learning a map between two diinite-dimessionall function spaces. For example, one can learn a PDE solver that maps from the boundary condition to the solution or an inverse problem that maps from the boundary measurement to the coefficient field. Regarding the mathematical foundation of operator learning, (Liu et al., 2022) considers the learning rate of non-paruree paraameetteic operator learning. However, non con-aarmettric functional data analy- sis often suffers from slower-than- than-oolooomiial convergence rates (Mas, 2012) due the small ball probability problem for the probability distributions in infinite dimensional spaces (Delaigle & Hall, 2010). The most relevant works (Lin et al., 2011 1; Reimherr, 2015; de Hoop al., 2021), which consider the rates for learning a linear operator. For the comparison between our work and (de Hoop al., 2021), see Remark 2.
Learning with Kernel. Supervised least square regression in RKHS and its generalization capa- bility have been thoroughly studied (Caponnetto & De Vito, 2007; Smale & Zhou, 2007; De Vito al., 2005; Rosasco al., 2010; Mendelson & Neeman, 2010). The minimax optimality with re- spect to the Sobolev norm has been discussed recently in (Fischer & Steinwart, 2020; Liu & Li, 2020: Lu et al., 2022). Our paper is highly related to recent works (Schuster et al., 2020; Mol- lenhauer & Koltai, 2020; Talwai et al., 2022: Li et al., 2022; Park & Muandet, 2020; Singh et al., 2019: 2020) on identifying the Sobolev norm learning rate for the kernel mean embedding(Song et al., 2009; 2013; Muandet et al., 2017), which can also formulated as learning an operator. The difference between our work and (Talwai et al., 2022; Li et al., 2022) sees Remark 2.1. A concurrent paper (Balasubramanian et al., 2022) considers unified RKHS methodology for functional data analysis. Our paper provided a refined analysis and provided information theortical optimal rates for this problem.
Multilevel Monte Carlo By combining biased estimators with multiple stepsizes, multilevel Monte Carlo (MLMC) (Giles, 2008; 2015) dramatically improves the rate of convergence and achieves in many settings the canonical square root convergence rate associated with unbiased Monte Carlo (Rhee& & Glynn, 2015; Blanchet & Glynn, 2015). Multilevel Monte Carlo can also be used for random variable with infinite variance (Blanchet & Liu, 2016; Chen et al., 2020). To the best of our knowledge, this is the first paper that provides optimal sample complexity for multilevel Monte Carlo type algorithm for infinite variance problems in the non-parametric regime. Very recently,
2

---

Published as a conference paper at ICLR 2023
(Lye al., 2021; Li et al., 2021a) developed a multilevel machine learning Monte Carlo algorithm (ML2MC)/ multilevel fine-tuning algorithm for learning solution maps by first learning the map on the coarsest grid and then successively fine-tuning the network on samples generated at finer grids. 'Tee authors also showed that, following the telescoping in MLMC, the multilevel training procedure could reduce the generalization enror without spending more time on generating training samples. (Schäfer & Owhadi, 2021; Boullé et al., 2022) consider such multi-scale algorithm for learning Green's 's function. However, the statistical power of such an algorithm is still under investi- gation. Another difference with (Boullé et al., 2022) is that we consider the Green function in H norm rather than the [ norm used in (Boullé al., 2022). In this paper, we qualify a specific setting where this multilevel procedure can and is necessary to achieve the minimax optimal learning rate.
1.2
CONTRIBUTION
We derive novel information theoreetc lower bound of learning a linear operator between two dimenio-dimensionall Sobolev reproducing kernel Hilbert spaces. The optimal learning rate is a minimum of two polynomial rates, one only dependent on the parameters of the input space while the other only the parameters of the output space. The first rate aligns with the previous works (Li et al., 2022), while the second is novel to the literature.
We study the shape of regularization that can lead to the optimal learning rate. One should learn all the spectral parts under the bias contour the level of the optimal learning rate but not the spectral components above the variance contour at the level of the learning rate. This enables the estimator to enjoy an optimal balance of bias-variance.
We qualify specific setting where multilevel training procedure (Lye et al., 2021; Li et al., 2021a) is necessary and capable of achieving a minimax optimal learning rate for learning linear operator. We perform the optimal learning via OIn In ensemble of ridge regression models. This differs from finite-dimensional operator learning, where a single-level estimator can be optimal.
PROBLEM FORMULATION
2.1 PRELIMINARY
Let Px be a distribution over the input space HK and define covariance operator CKK = Eu~ u Consider its spectral decomposition CKK Etr piee; 0 ei, where {ur ) is an orthogonal eigenbasis and {u.} is the corresponding eigenvalues of CKK (here the g @ h is an operator defined h) g). In the typical machine learning applications, the test distribution is the same as the training distribution, we can assume that H {Σ, a.fee; e; {a &2 without loss of generality. Note that this automatically holds in the context of learning the condi- tional mean embedding (CME) (Fischer & Steinwart, 2020; Talwai et al., 2022; Li et al., 2022).
as g @ h gh"
Following Christmann Steinwart (2008); Fischer & Steinwart (2020), we define the interpolation e4) far 12) for any > O, equipped with Sobolev
Sobolev space H {
-= {
norm defined by the inner product (I (I, a,a( ct). E, be ee))
E, a.bb For the output
H
space, we fix a user-specified distribution Qr and a reproducing Kernel Hilbert Space. We can similarly define the covariance operator Co2 and the Sobolev space H7.- Natural choices Qr. include some distribution on kernel functions {E(y,) :) ): E Y) of Hr, induced by some distribution QL on Y, so that Co. is a kernel integral operator with respect to Q2 and H. is an interpolation space between Hr and (²( see Example 2.1 for specific example.
Following Li et al. (2022), in this paper we consider the Hilbert-Schmine norm between two Sobolev Spaces for all the operators, which is defined as following.
Definition 2.1 ((3 -nomm) Let 11,8,Pk HK + H&, B E (0,1) is the canonical embedding mapping that takes u E HK to the same element in the larger space HR and h Hr. + His5 v < 1 is similarly defined.
HK + Hy be a possibly unbounded linear operator:
3

---

Published as a conference paper at ICLR 2023
Then the (B, -noomm of T is defined as
I ) To P. H (12 Piw.e..lllssssege...
= c0(1-)122 o I c(2-81/2
CK
HS(HR Hz)
where we omit the dependence of I1-1a,,, on Px and Qr. since it will always be clear from context.
2.2 PROBLEM FORMULATION
We consider the problem of learning unknown linear operator Ao : HK H He between two reproducing kernel Hilbert spaces corresponding to kernl and I respectively. We are given N noisy data pairs (ua, vz), 1 & i N related by
= Agu: +
(1)
where us Ltd. Pk for some unknown distribution Px and E; is the noise drawn from some distri- bution with zero mean that may depend u,. We use PKL for the joint distribution of (u,, 0t)- Denote CKK = Eu u @ u, CKE = E(u,o) @ and its adjoint CLK = Ckz be uncen- tered cross-covariance operators associated with PKt. Then we can reformulate the ground turth operator Ag CLKC where is the pscudo-inverse (Talwai et al., 2022: Li et al., 2022). With the goal of understanding the relative difficulty of learning different types of linear operators, we investigate the sample efficiency of learning Ag under certain source assumptions imposed on the data model (I). Source condition (Caponnetto & De Vito, 2007; Mendelson & Neeman, 2010; Steinwart et al., 2009; Rosasco et al., 2010; Fischer Steinwart, 2020) assumes that the learning target lies in parameterized function class and study the learning rate for different problems with different hardness. Specifically, the source condition assume that the learning target is bounded in certain Sobolev norm. In this paper, we consider learning an operator with bounded (1, nnrm,, which is the Hilbert-Schmine norm that maps from Hi to HZ. We consider the generalization er- ror/convergence rate under another (3', >')-norm as in Fischer & Steinwart (2020); Lu et al. (2022); Talwai et al. (2022); et (2022).
Remark 2.1 Although recent works have considered similar problems in the context of conditional mean embedding (Talwai et al., 2022; Li et al., 2022) and functional data analysis (de Hoop et al., 2021), in all these papers, the output space is a trace bounded RKHS (de Hoop al., 2021, As- sumption 2.14 (vi)) rather than the general parameterized Sobolev space in our paper.
We then list all the assumptions imposed on the underlying kernel for our theoretical results. We fol- low the standard capacity assumptions and embedding properties used in kernel regression (Fischer & Steinwart, 2020; Talwai et al., 2022; Li et al., 2022).
Assumption 2.1 (Capacity Condition of the Covariance) The eigenvalues (1é312a of the covari- ance operator Cr = Eu-PPx @ satisfies μ4; x 5 for some p E (0, 1). Similarly, the eigenval- ues (pehia of the covariance operator Cq. Egnqq v @ satisfies ps x i for some q E (0, 1).
Assumption 2.2 (fxc Embedding Property of the Input RKHS) There exists smallest (0, 1) such that (If.o.Px) f|]
< Ai a.s. under Pk for some AІ < to0.
Assumption 2.3 (foc Embedding Property of the Output RKHS) There exists Ag < too such that |19 & AA holds for all in the range of Ag, except from Q null set.
Assumption 2.4 (Moment Condition) There exists an operator V : Hr + Hy with tr (V) & o² such that for every E HK. We have Em Pae. [(V- Abu) & (v - Auu)) = (28) holds for all l 2 2.
Assumption 2.5 (Source Condition) An is bounded under (B, (2,7))nomm i.e. ||olll,, & B.
4

---

Published as a conference paper at ICLR 2023
2.3 EXAMPLES
In this section, we will introduce two examples of our theory. The first one is about learning a differ- ential operator, for example inferring an advection-diffusion model Portone & Moser (2022) from observations or predicting the future Long et al. (2018); Lu et al. (2019); Li et al. (2020); Feliu-Faba al. (2020); Huang et al. (2021). The second example is about learning conditional mean embed- ding Song et al. (2009; 2013); Muandet et al. (2017), which represents a conditional distribution as an RKHS element. Thus conditional distribution regression can be reduced to kernel operator learning. Our theory can also be used for linear inverse problems such as radial electrical impedance tomography (EIT) Mueller & Siltanen (2012), and the severely ill-posed inverse boundary prob- lem for the Helmholtz equation with unknown wave-number parameter Agapiou et al. (2014). For detailed discussion, we refer to (de Hoop et al., 2021, Section 1.3)
Example 2.1 (Learning differential operators) Suppose that the ground-Irath operator Ao A where A is the Laplacian and L E Z. Let HK = Hm*+2 1]) be the Sobolev space with smooth- ness m 21. on [0, 1] and Hy 7T ([0, 1]). then Ag is bounded operator from Hg to Hy which corresponds to the B3 = 7 = 1 case. However, we will see below that we can obtain a better characterization of the learning error using our theory.
Consider for example that the input has mean zero and the Matérn-type covariance operator CKK = a² (-A+
Its eigenvalues satisfy Pr, n n25, On the other hand, we choose Qy be distribution supported (E(y.)): is the kernel function of Ht. Then Cov is essentially the kernel integral operator on Hr, w.nt.
2s_ ::: y E [O, 1]} induced by uniform distribution [0, 1]. where
the uniform distribution, and its eigenvalues are Pn. O n -2m, The assumption ||Aoll 400
satisfied if and only if (1 (1-7)m- < (1 B)s fi.e. 7 > 2(1-8)=-11,
2m
Example 2.2 (Conditional mean embedding) Suppose that we would like learn the conditional distribution Píy x) from data set {(ri, & N} C X Y where ~ Pk. Let HK and H be two RKHSs on X and Y respectively, with measurable kernel k(.,,) and ). Then we can define conditional mean embedding (CME) operator Cyjx that satisfies
Cyixk(æ,-) -EI,e((,)) = 1Y|2: and EY)= (g. Vx E
We choose Ao Cy|z- In this case, CKK k(X,) @ k(X,)). Assumption 2.2 states that supzex ka (xx,x) = Ad, while Assumption 2.3 equivalent supaex || < Aq (for simplicity we only focus on the case (= 1). According to Assumption 2.5, we assume that [Cyixllan & B.
The mis miisspecified setting where B < 1 has been studied in previous work (Fischer & Steinwart, 2020; Talwai et al., 2022; li et al., 2022). However, they only consider the case 7 1. Our results also cover the case 7 <, 1, which allows us to obtain theoretical guarantee for computing conditional expectation of the larger function class H.
INFORMATION THEORETIC LOWER BOUND
In this section, provide information-theoreet lower bound via the Fano method for the vergence rate of the operator learning problem formulated in Section 2.
Theorem 3.1 Suppose that Px and QL are probability distributions on Hilbert spaces Hk and Hy respectively such that Assumptions 2.1 and 2.2 hold. Then for any estimator L (HH x HH.)) @N +
HS (H& H.). there exists a linear operator Ag and a joint data distribution Pkl with marginal distribution Px Hx satisfying Assumptions 2.3 2.5, such that with probability 0.99 over
(us, vs) hid. PRI we have || ([(u,, m)) - -oolla Z N min
max(o.8)-3 max
max Co.
Remark 3.1 Our lower bound is composed of minimum of two parts. The first rate N the minimax optimal Soboley learning rate for kernel regression (Fischer & Steinwart, 2020; Tal- wai al., 2022; Li al., 2022; Lu el al., 2022) and is fully determined by the parameter of the input Sobolev reproducing kernel Hilbert space. Our second rate N- x is novel to the literature.
maxe (o 1
5

---

Published as a conference paper at ICLR 2023
This bound shows how the infinite- lineete-dimmnsionnal problem is different from the finite cnite-dimensionll gression problem and is fully determined by the output Sobolev reproducing kernel Hilbert space parameter. Our lower bound shows that the hardness of learning linear operator is determined by the harder part between the input and output spaces. We will explain why the lower bound has such structure in Remark 4.2 and Figure? 2.
ON THE SHAPE OF REGULARIZATION
In this section, we aim to understand the shape of regularization so that the constructed estimator A based on N i.idd data v;)] PKL for 1 < N enjoys an optimal learning rate.
Compared with existing approaches where regularized least-qquares estimator can achieve statisti- cal optimality (Fischer & Steinwart, 2020; Talwai al., 2022; Li et al., 2022; de Hoop et al., 2021) under (8, 1) normm we study the learning rate under the (8, 7) -nom (3' E (), (7, which
Cq. I-n/ (A (A-AD)
defined in Definition 2.1 as
[A-Ann Au
C
The norm
[SS(Hx :H)
of the additional Cor term is unbounded which make our setting harder than the convergence in
(3, norm in existing works. Since Co.. 1 is bounded when restricted to the finite ditee-dimensional
space span (p. fs: < & n we should also include another birs-variance trade-off via regular- izing in the output shape. As a result, we are interested in answering the following question
What is the optimal way combine the regularization in the input space and regularization in the output space? i.e. What is the optimal shape of regularization?
To answer this question, we investigate the problem the spectral space, i.e. considering the spec- tral representation of operator Ag = Σiz= azyl4 ex & Pj 1-3 fz- The problem of estimating A then reduces to learning the coefficients "matrix" (aiz Aiz=1- The source condition Assumption 2.5 enforces Σij= a < B. We show in Appendix B.1.1 that regularizing the basis & f, will
1- introduce bias of order |ossuu PJ
8- 8-8' 03 x
under the D-n
W
(8', On the other hand, when a < B + p. we show in Appendix B.1.2 that the vari- ance of learning (i.j) from noisy data scales as 11, Pj p -(1-7') x 1 ميد Since the variance
would accumulate for a fixed j. learning (i.j) for & imx results in a variance of x N Imax J مي (Similar analysis can be carried out for the a > 3 + p case as well, but the variance now scales g'in-2 1_يL
as t imas" j
see Appendix for detailed derivations.) In summary, we need to make bias- variance trade off in the (i.j)- i.e. decide whether we should learn or regularize over the basis e & fj-
4.1 REGULARIZATION VIA VARIANCE CONTOUR
The underlying idea of regularization that some components are intrinsically hard to learn due to large variance; these components are then neglected by adding regularization and are counted as bias. Thus, the remaining components are easy learn due controllable variance. This intuition works well when the estimation error results from the noise of the data and is well-studied in a line of works (Fischer & Steinwart, 2020; Hoop et al., 2021: Talwai al., 2022; et al., 2022). This idea still works in setting, but need to re-evaluate the bias and variance of each component. Since work with the Hilbert-Schmidt norm, this can be done in a coordinate-wis. manner, meaning that can look at each d.j separately and decide whether neglect it (contribute bias) or to learn it from data (contribute to variance).
Since the variance term measures the hardness of learning, naturally introduce the notion of variance contour, which a curve on the R2 plane on which all points induce the same order of variance (here work with real coordinates for convenience, although we only care about integer

---

Published as a conference paper at ICLR 2023
variance Contour
ouspit Space
ousput
input reguloraaation
Irpurt space regulorization
Ingut Space
Input Space
Figure 1: An illustration of our proposed regularization scheme. Left: the regularized least-squares estimator studied in previous works (Fischer & Steinwart, 2020; de Hoop et al., 2021; Talwai et al., 2022) which only regularizes on the input space. Right: our double regularization scheme via variance contour can achieve the optimal convergence rate in our setting.
points). Formally, we fix an arbitrary constant > 0 and define
Car (z.g) E R p'+max D.
c
y
reasonable regularization scheme then to learn all coordinates (i,j) L3 below the curve frr and 'regularize out' the remaining coordinates that are difficult to learn due large variances. This can gives us the estimator with smallest estimator at give variance level. This observation motivates us construct estimator
UN Σ
1 CLK (CKK+ foox+\,)) +X,1"
A
where ČLK- =
E @ ug 1y(1 < < un = CT are the regularization coefficients
imposed on different dimensions the output space. According to (2) and noting that μu xx i define
(5-ta² mmmaaf
a-d max
N log N
Xy max
cco
with C² max
a- [a.
(2). The additional N term in (4) is needed for control-
ling the error of approximating CKK via CKK (ef. Theorem D.3) which is standard in the Sobolev learning literature Fischer & Steinwart (2020); Talwai et al. (2022); Lu et al. (2022). The following theorem describes the convergence rate of our estimator defined by (3) and (4).
Theorem 4.1 Consider the estimator À defined by (3) and (4). Suppose that Assumptions 2. 2.5 hold, then there exists a universal constant C such that with probability e- we
have A Ao 1' & C² log
log N.
Remark 4.1 Compared with Theorem 3.1, our upper bound is optimal up to logarithmic factors when o & B. The optimal learning rale in the a >> 3 regime an outstanding problem for decades, parameters 7 (see e.g. the discussions following
even without the additional problem-dependen (Fischer & Steinwart, 2020, Theorem 2)). In this paper, we do not address this problem either.
4.2 REGULARIZATION VIA BIAS CONTOUR
We have showed that if we learn all the spectral components under certain variance contour and reg- ularize all other component can achieve optimal rate. In this section, introduce another scheme to design the optimal estimator via learning all the spectral component under a certain bias contour. Specifically, we consider deciding the regularization strength according to the spectral elements
duce certain level of bias i.c. the bias contour lo bise
{2. (z. R2
y = }
does not coincide with fora for any C² up constant scaling. Thus, there exists point

---

Published as a conference paper at ICLR 2023
(1.8%4
output space
N
Varianue
Dls contous
bis contout
inpit space
most space
Figure 2: The plot of the bias contour and the variance contour. For simplicity, we only plot the case a & 3 + p here. The variance contour is always above the bias contour. Left: When 4'
1-
8+p > 1-7?
ee max Mapp
the two yields O .
convergence rate. It is the same learning rate the two kernel
regression curves meet when y = 1. Right: When B'+p
> 1=x²- the two contours yield the same
p+P
regularization on the output space leading to a convergence rate of O (N
(x",y") on the variance contour with maximal contribution bias. Naturally, we can also con- struct our estimator using bias contour that passes through (I",""). In this case, we may define
A = max (1- min ma
log for similar reasons as Sec-
tion 4.1, which also yields optimal rate as stated in Theorem 4.2 below.
Remark 4.2 (On the optimal shape of regularization) The discussion in Sections 4.1 and 4.2 reveals another understanding of our information theoretic lower bound. Firstly, should learn all the spectral components under the bias contour otherwise the bias will should not learn any spectral component
exceed the lower bound. Secondly, the variance contour since otherwise the variance will exceed the lower bound. Thus the bias contour should always be under the variance contour, otherwise no estimator can be de- signed. The bias and variance contours the level of optimal learning rate are plotted in Figure 2. They only meet at (x",y" :y") with x² = 1 or y" = 1, which has the largest contribution to the bias (resp. variance) among all points on the variance (resp. bias) contour, thus dominating the estima- tion error. When the two curves meet at y² 1, it reduces to the original kernel regression case. When the two curves meet at x² 1, il leads to our new rate that depends on the output space.
Theorem 4.2 Consider the estimator Å defined by (3) with >S defined above. Suppose that As- sumptions 2.1 to 2.5 hold, then there exists a universal constant C, such that || Au
31,7" <
8-8 min mpx
C+²
N log N
log" N holds with probability > 1 1-
5 MULTILEVEL KERNEL OPERATOR LEARNING
In this section, we study a multilevel machine learning algorithm Lye et al. (2021); Li et al. (2021a); Boullé et al. (2022) but at each level we consider a cost-accuracy trade-off De Hoop et al. (2022) to control the variance at proper scale. We show that the multilevel level algorithm can cover all the spectral component below the bias contour and achieve the optimal learning rate. Our idea is similar to the multilevel Monte Carlo Giles (2008; 2015), which reduces bias from multilevel algorithm. Our multilevel estimator differs from the DeepONet (Lu et al., 2019) and the PCA-Net (Bhattacharya al., 2020) since we add different regularizations for each level. Our theory indicates that the multilevel approach outperforms previous ones and achieves the optimal learning rate.
The basic idea is to design a minimum number of machine learning estimators that cover all the spectral elements under the bias contour but do not exceed the variance contour at the same time. To achieve this, we choose sequences {a:} and {y:} for & < LN where yi denotes the i-th level
and F; controls the corresponding regularization via the regularization coefficient X = x;
The sequences chosen in staircase manner as plotted in Figure 3 (for formal definitions
8

---

Published as a conference paper at ICLR 2023
Mb)
irput space
input space
Figure 3: Construction the sequence {(T 9:)}. Left: the case
8-9 max(a.B-p)
* Y-y 1-y Right: the
case max I-7" where the bias and variance contours overlap and we set In+1 zan-
8-8¹
Each rectangular represents certain level of regularization.
Appendix C). The eigenbasis [3 fo of the output space is divided into defferent levels by {ur)
The main idea behind multilevel method is that different levels of the output need to be learned with different regularization. Formally, we define our multilevel estimator as
An
Σ
CLK (CKK+>/<0))
(5)
1=0
The following theorem shows that the estimator (5) can achieve the optimal convergence rate with LN OIn In N) when max(a, + 1-7. We also show that (In estimator is needed for the case when 8-8'
8-8'
max(a..-pp 1-y (Figure Right) Appendix
Theorem 5.1 Suppose that Assumptions 2.1 to 2.5 hold, then there exists a sequence {yi (ucheigLN 9-8'
with LN 0(I N) when
z/-2 and O(In In Nn otherwise, such that the estimator
max (a.Btp]
1-7
Au satisfies |m -oaa-ooll B 1 ET, where universal constant.
< C+2
min
- log" N with probability >
log
Our multilevel algorithm first apply the regression algorithm on low-frequency pro- jections of the output samples with small regularization and then successively fine-tune the regres- sion model on freu-fryy projections of the output samples with stronger regularization, which matches the empirical use (Li et al., 202 la; Lye et al., 2021).
Remark 5.1
CONCLUSION AND DISCUSSION
We considered the sample complexity of learning an operator between two Sobolev kernel Hilbert spaces. We provided an information theoretical lower bound for this problem along with a multi-level machine learning algorithm. Our lower bound is determined by the harder rate of two polynomial rates: one is fully determined by the hardness of the input space, while the other fully controlled by the hardness the output space. The second rate is new to the literature. We explained our bound from the viewpoint of variance and bias counters in Remark 4.2 and Figure 2. The optimal estimator should learn all the spectral elements under the bias contour but learn information above the variance contour. To meet this requirement, idea of multi-level Monte Carlo with kernel operator learning, using successive levels to fit higher frequency information while keeping the variance the same scale reduce the bias. Our paper is the first on the paraamametticc statistical optimality for multi-level algorithms. We leave estimation from discretely observed functional covariates with noise as future work (Zhou et al.; 2022).
combined the
ACKNOWLEDGMENTS
Jikai Jin is partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University. Yiping Lu is supported by the Stanford Interdisciplinary Graduate Fellowship (SIGF). Jose Blanchet is supported in part by the Air Force Office of Scientific Research under award number FA9550-20- 1-0397. Lexing Ying supported is supported by National Science Foundation under award DMS-2208163

---

Published as a conference paper at ICLR 2023
REFERENCES
Robert A Adams and John JF Fournier. Sobolev spaces. Elsevier, 2003.
Sergios Agapiou, Andrew M Stuart, and Yuan-Xiang Zhang. Bayesian posterior contraction rates for linear severely ill iol-posed inverse problems. Journal of Inverse and Ill-posed Problems, 22(3): 297-321, 2014.
Krishnakumar Balasubramanian, Hans-Georg Müller, and Bharath K Sriperumbudur. Unified rkhs methodology and analysis for functional linear and single-index models. arXiv preprint arXiv:2206.0397. 2022.
Kaushik Bhattacharya, Bamdad Hosseini, Nikola B Kovachki, and Andrew M Stuart. Model reduc- tion and neural networks for parametric pdes. arXiv preprint arXiv:2005.03180 2020.
Jose Blanchet and Zhipeng Liu. Malliavin-based multilevel monte carlo estimators for densities of max-stable processes. In International Conference Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, pp- 75-97. Springer, 2016.
Jose H Blanchet and Peter W Glynn. Unbiased monte carlo for optimization and functions of expec- tations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pp- 3656- 3667. IEFE, 2015.
Nicolas Boullé, Seick Kim, Tianyi Shi, and Alex Townsend. Learning green's functions associated with time-dependent partial differential equations. Journal of Machine Learning Research, 23 (238):1-34, 2022.
Andrea Caponnetto and Emesto De Vito. Optimal rates for the regularized cautrssuares algorithm. Foundations of Computational Mathematics, 7(3):331-368; 2007.
Guanting Chen, Alex Shkolnik, and Kay Giesecke. Unbiased simulation estimators for path integrals of diffusions. In 2020 Winter Simulation Conference (WSC), pp. 277-288. IEEE, 2020.
Tianping Chen and Hong Chen. Universal approximation to nonlinear operators by neural networks with arbitrary activation functions and its application to dynamical systems. IEEE Transactions on Neural Networks, 6(4):911-917, 1995.
Yifan Chen, Bamdad Hosseini, Houman Owhadi, and Andrew M Stuart. Solving and learning nonlinear pdes with gaussian processes. Journal of Computational Physics, 447:1 10668, 2021.
Andreas Christmann and Ingo Steinwart. Support vector machines. 2008
Christophe Crambes and André Mas. Asymptotics of prediction in functional linear regression with functional outputs. Bernoulli, pp. 2627-2651, 2013.
2013.
Maarten De Hoop, Daniel Zhengyu Huang. Elizabeth Qian, and Andrew M Stuart. The cost- accuracy trade-off in operator learning with neural networks. arXiv preprint arXiv:2203. 13181, 2022.
Maarten V de Hoop, Nikola B Kovachki, Nicholas Nelsen, and Andrew M Stuart. Convergence rates for learning linear operators from noisy data. arXiv preprint arXiv:2108. 12515, 2021.
Ernesto De Vito, Lorenzo Rosasco, Andrea Caponnetto, Umberto De Giovannini, Francesca Odone, and Peter Bartlett. Learning from examples as inverse problem. Journal of Machine Learning Research, 6(5), 2005.
Aurore Delaigle and Peter Hall Defining probability density for distribution of random functions. The Annals of Statistics, 38(2):111--1193, 2010.
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation con-
ditional moment models. Advances in Neural Information Processing Systems, 12:12448-12266 2020.
Jordi Feliu-Faba, Yuwei Fan, and Lexing Ying. Meta-learning pseudo-differentia operators with deep neural networks. Journal of Computational Physics, 408: 109309, 2020.
10

---

Published as a conference paper at ICLR 2023
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algo- rithms. J. Mach. Learn. Res., 21:205-1, 2020.
Michael B Giles. Multilevel monte carlo path simulation. Operations research, 56(3):607-617, 2008.
Michael B Giles. Multilevel monte carlo methods. Acta numerica, 24:259-328, 2015,
Xin Guo, Anran Hu, Renyuan Xu, and Junzi Zhang. Learning mean-field games. Advances in Neural Information Processing Systems, 32, 2019.
Jiequn Han, Arnulf Jentzen, and E Weinan. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34):8505-8510, 2018.
Siegfried Hörmann and Lukasz Kidziński. A note on estimation in hilbertian linear models. Scan- dinavian journal of statistics, 42(1))433-6,, 2015.
Xiang Huang, Zhanhong Ye, Hongsheng Liu, Beiji Shi, Zidong Wang. Kang Yang, Yang Li, Bingya Weng, Min Wang. Haotian Chu, et al. Meta-auto-decoder for solving parametric partial differen- tial equations. arXiv preprint arXiv:21/1.0885 2021.
Yuehaw Khoo, Jianfeng Lu, and Lexing Ying. Solving for high-dimensional committor functions using artificial neural networks. Research the Mathematical Sciences, 6(1):1-13, 2019.
Yuehaw Khoo, Jianfeng Lu, and Lexing Ying. Solving parametric pde problems with artificial neural networks. European Journal of Applied Mathematics, 32(3):421-435, 2021.
Nikola Kovachki, Zongyi Li, Burigede Liu, Kamyar Arizzadenesheli, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Neural operator: Learning maps between function spaces. arXiv preprint arXiv:2108.0844 2021.
Zhi-Zhou Li, Yi-Chen Tao, Xue-Dong Wang, and Liang-Sheng Liao. Organic nanophotonics: self- assembled single-crystalline homoo//neterostuucuurss for optical waveguides. ACS Photonics, (9):3763-3771, 2018.
Zhihan Li, Yuwei Fan, and Lexing Ying. Multilevel fine-tuning: Closing generalization gaps in approximation of solution maps under limited budget for training data, Multiscale Modeling & Simulation, 19(1):344-773, 2021a.
Zhizhou Li, Chun Yan Gao, Dingkai Su, Chuancheng Jia, and Xuefeng Guo. Principles of molecular machines at the singlc-molecule seale. ACS Materials Letters, 3(10): 1484-1552, 2021b.
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning. arXiv preprint arXiv:2208.01711, 2022.
Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, An- drew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. arXiv preprint arXiv:2010.08895, 2020.
Lin Lin, Jianfeng Lu, and Lexing Ying. Fast construction of hierarchical matrix representation from matrix-vector multiplication. Journal of Computational Physics, 230(10):4011-4087, 201
Hao Liu, Haizhao Yang, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Deep nonparametric estima- tion of operators between infinite dimensional spaces. arXiv preprint arXiv:2201.00211. 2022.
Zejian Liu and Meng Li. On the estimation of derivatives using plug-in krr estimators. arXiv preprint 2xXiv:2006.01350 2020.
Zichao Long, Yiping Lu, Xianzhong Ma, and Bin Dong. Pde-net: Learning pdes from data. In International Conference on Machine Learning, pp. 3208-3216. PMIR, 2018.
Zichao Long, Yiping Lu, and Bin Dong. Pde-net 2.0: Learning pdes from data with a numeric- symbolic hybrid deep network. Journal of Computational Physics, 399: 108925, 2019.

---

Published as a conference paper at ICLR 2023
Lu Lu, Pengzhan Jin, and George Em Karniadakis. Deeponet: Learning nonlinear operators for iden- tifying differential equations based on the universal approximation theorem operators. arXiv preprint ar arXiv:1910.03111 2019.
Yiping Lu, Haoxuan Chen, Jianfeng Lu, Lexing Ying, and Jose Blanchet. Machine learning for elliptic pdes: Fast generalization bound, neural scaling law and minimax optimality. arXiv preprint arXiv:21 10.-069770. 2021.
Yiping Lu, Jose Blanchet, and Lexing Ying. Sobolev acceleration and statistical optimality for learning elliptic equations via gradient descent. arXiv preprint arXiv:2205.0733/ 2022.
Kjetil O Lye, Siddhartha Mishra, and Roberto Molinaro. A multi-level procedure for enhancing accuracy of machine learning algorithms. European Journal of Applied Mathematics, 32(3):436- 469, 2021.
André Mas. Lower bound in regression for functional data by representation of small ball probabil- ities. Electronic Journal of Statistics, 6:1745-1778, 2012.
Shahar Mendelson and Joseph Neeman. Regularization in kernel learning. The Annals of Statistics, 38(1))526-565, 2010.
Mattes Mollenhauer and Péter Koltai. Nonparametric approximation of conditional expectation operators. arXiv preprint wrXiv:202..1291/ 2020.
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf, al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends@ in Machine Learning, 10(1-2):1-141, 2017.
Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj. Dual instrumental variable regres- sion. Advances Neural Information Processing Systems, 13:2710-27221 2020.
Jennifer L Mueller and Samuli Siltanen. Linear and nonlinear inverse problems with practical applications. SIAM, 2012.
Richard Nickl and Sven Wang. On polynomial-time computation of high-dimensional posterior measures by langevin-type algorithms. arXiv preprint urXiv:2009.05295 2020.
Richard Nickl, Sara van de Geer, and Sven Wang. Convergence rates for penalized least squares estimators in pde constrained regression problems. SIAM/ASA Journal on Uncertainty Quantifi- cation, 8(1):374-413, 2020.
Junhyung Park and Krikamol Muandet. measure-theoretic approach to kernel conditional mean embeddings. Advances neural information processing systems, 33:21247-21259, 2020.
Teresa Portone and Robert D Moser. Bayesian inference of an uncertain generalized diffusion oper- ator. SIAM/ASA Journal Uncertainty Quantification, 10(1):111-178 2022.
Maziar Raissi, Paris Perdikaris, and George E Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics, 378:686-707, 2019.
Matthew Reimherr. Functional regression with repeated eigenvalues. Statistics Probubility Let- lers, 107:62-70, 2015.
Chang-han Rhee and Peter Glynn. Unbiased estimation with square root convergence for sde models. Operations Research. (15))1026-0433 2015.
Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11(2). 2010.
Florian Schäfer and Houman Owhadi. Sparse recovery of elliptic solvers from matrix vector prod- ucts. arXiv preprint 10.0522 2021.
12

---

Published as a conference paper at ICLR 2023
Ingmar Schuster, Mattes Mollenhauer, Stefan Klus, and Krikamol Muandet. Kernel conditional density operators. International Conference on Artificial Intelligence and Statistics, pp. 993- 1004. PMLR. 2020.
Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. Ad- vances in Neural Information Processing Systems, 32, 2019.
Rahul Singh, Liyuan Xu, and Arthur Gretton. Kernel methods for causal functions: Dose, heteroge- neous, and incremental response curves. arXiv preprint arXiv:2010.04855 2020.
Justin Sirigmano and Konstantinos Spiliopoulos. Dgm: A deep learning algorithm for solving partial differential equations. Journal of computational physics, 375:1339-1364 2018.
Steve Smale and Ding-Xuan Zhou. Learning theory estimates via integral operators and their ap- proximations. Constructive approximation, 26(2):153-172, 2007.
Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space embeddings of condi- tional distributions with applications to dynamical systems. Proceedings of the 26th Annual International Conference Machine Learning, pp. 961-968, 2009.
Le Song, Kenji Fukumizu, and Arthur Gretton. Kernel embeddings of conditional distributions: A unified kernel framework for nonparametric inference in graphical models. IEEE Signal Process- ing Magazine, 30(4):98-111 111, 2013.
Ingo Steinwart, Don Hush, Clint Scovel, al. Optimal rates for regularized least squares regres- sion. In COLT, pp. 79-93, 2009.
George Stepaniants. Learning partial differential equations in reproducing kernel hilbert spaces. arXiv preprint arXiv:2108. 11580, 2021.
Prem Talwai, Ali Shameli, and David Simchi-Levi. Sobolev norm learning rates for conditional mean embeddings. In International Conference Artificial Intelligence and Statistics, pp- 10422-10447. PMLR, 2022.
Alexandre B Tsybakov. Introduction to nonparametric estimation. Springer Science & Business Media, 2008
Daren Wang, Zifeng Zhao, Yu, and Rebecca Willett. Functional linear regression with mixed predictors. arXiv preprint arXiv:2012.00460, 2020a.
Lingxiao Wang. Zhuoran Yang, and Zhaoran Wang. Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning. International Conference Machine Learning, pp. 10092-10103 PMLR, 2020b.
Bing Yu al. The deep ritz method: deep learning-based numerical algorithm for solving varia- tional problems. Communications in Mathematics and Statistics, 1(1):1-12, 2018.
Hang Zhou, Fang Yao, and Huiming Zhang. Functional linear regression for discretely observed data: From ideal to reality.
Hang Zhou, Dongyi Wei, and Fang Yao. Theory of functional principal components analysis for discretely observed data. arXiv preprint 200.02200. 2022.
13

---

Published as a conference paper at ICLR 2023
A PROOF OF THE LOWER BOUND
In this section, we follow the lower bound proof in Fischer & Steinwart (2020) to give a lower bound of the convergence rate in operator learning setting.
A.1 PRELIMINARIES ON TOOLS FOR LOWER BOUNDS
In this section, we repeat the standard tools we use to establish the lower bound. The main tool we use the Fano's inequality and the Varshamov-Gilber Lemma.
Lemma A.1 (Fano's methods) Assume that V is uniform random variable set V. then for any Markov chain V + X + V. we always have
I(V:X) + log
P(V * 2 2
log(
In our proof we will use a version from Fischer & Steinwart (2020).
Lemma A.2 (Fischer & Steinwart, 2020, Theorem 20) Let > 2, (9, be a measurable space,
Po. PI...., Pas be probability measures on (2, with Pj < Po for all j 1,..., M, and
0 < aa < 00 with
1 (L a a..
Then, for all measurable functiios V : + {0, .,.1.....10 M). the following bound is satisfied
VM
(1 (1- 3a.
max PS( ((W) + +
j=0,l,.., M
1 VM
log(M) 2 2log(M))
Lemma A.3 Perrshmmv--iillbee exists subset V = {-("), , 7(20/)) of D D-dimensional hypercube HD 10.1DD
(2008) Theorem 2.9) Let 2 8. There
such that
-()) = (0, 0, ... 0) and the & distance between every two elements is larger than D 8
for Σ (| - - 2 _ for all 0 S 2/8
8
A.2 PROOF OF THE LOWER BOUND
To prove our lower bound, we construct a sequence of linear operators as follows:
32c
mi
8212 1- Wiflitm Pj+mu fs+ms & Gi+mis Wi E {0,
A
mik-
K
where my and m2 hyper-paramette (scale as poly(N) and will be selected later) and K is constant that will be specified afterwards. It's easy to check that
32s
m
K
|1Am - A
(wij
w(y)
K
t=1 Ø=
By
K/8 binary strings Lemma it is possible to select Mj > 2m 2m18/8
(1)) (2) (M.)) E {0, 1m
such that ||ا(+) - w1 _
4s. Let Ω be the collection of this strings. We now select the hyper- parameters to satisfies the assumptions made in Scction 2. First we have
1ww 12
32
MI
(3-9')) ((7-->)
Pjtma S e (2m1) 3-3"
(2m2) Y--
Pitm
m
K
=
14

---

Published as a conference paper at ICLR 2023
where the last step follows from Assumption 2.1. Similarly, have |
x
e (2m1)= o-d' x/-1
(2m2) <
To the assumptions made in Section 2, we should make
smaa (.
(2m1)
(2m²
S
(6)
be satisfied. To be specific, with the previous selection of hhppey-ppaaeeee parameters, we can have ||Alll = (1) and
sup Illl < sup ||Aullaa ((F..)))' /
+00
gErange(A.)
where the last step follows from our assumption on the input distribution Assumption 2.2. This verifies that Assumptions 2.3 and 2.5 hold for A.,, Ve E Ω.
We now construct the hypothesis (probability distributions) as follows: for Veu E 10, define
(u(df. dg) = aN (C (g) dPx(f)
where the covariance operator Σ = o² Σ5= Pstma 8 fs+mz for some constant o > 0. It's then easy to see that tr (E) = o². which satisfies Assumption 2.4 .Nte that the range of A span(fma) and Σ is non-degenerate on this subspace. As result, we can view Pw: E as distributions on HK span (fi+m² :1 & & K), and we have for Vue w/ E Q that
KL (Pw)) EySPK [KL (Pw IfllP A)D
= =ESNPK (N W f.
ByNPK ((A - -w E (A - Aw)
RK PK ((A A (A Ar)f))
K (ws - why 8 12 (fs estmil fs+ma
32g
m2o²
BynPK
pmm Pj+ma
1=1
H2
m2o²
32c
E BynPk
K
P
1-7
(wis) - why))1mmmm 8/12 (f, (frectmi) Σ
5ml
32c
K
8r 1-
(wig - w//) (
Hltmm Pftins Z 50 2m,
m2
mio²
where the last step follows from Epp uuu CKK = Eis Se and recall that K is constant. Hence deduce that
8¹ 1-x Σ KL 5 So - nem, m2 =: a*
M
W'En
Applying Lemma A.2, we find that when
a" log Me + 8 Snnnnnn n' mm m2 I-d
there exists hypothesis Par, such that for any estimator Awe.
f1l.m0 Amo
-
Amo
{
wo * arg min || - Auo looll
wEn
holds with high probability.
Finally, we need to choose optimal m, and my under the constraint (6). It turns out that either mi = 1 or me 1, and the resulting lower bound is
A A
All 3'
2
min m
Aimas(a 211
15

---

Published as a conference paper at ICLR 2023
B PROOF OF THE UPPER BOUND
In this section, we upper-bound the learning error of estimator (3) which defined as
NN
À
Σ
CLK (CxK + +2,1) pg 2 15)))
are regularization coefficients that we impose different dimensions of the output space. In this section, we consider the following two ways to select regularization coefficients Section
where A,, 1 < < VN N
We regularize all spectral component below certain variance contour, i.e. we set regulariza- max
I-n!
1/4
tion strength X5 = max
max
00
Jog
(4).
We regularize all spectral component below certain bias contour, i.e. we set regularization strength A, = max
(
2/-2
mine
d- max
( )
(19).
log
To obtain the upper bound for our estimator, we decompose the learning error E(A) A
in bias and variance via Ao W,n
E(A) & A AA 1/.0"
+IAA Aoll
bias
variance term
where
NN
A Σ 1=1
p3 2 1331)/)) CKi (CKK + +A₂T)=1
(8)
B. REGULARIZATION VIA VARIANCE COUNTER
In the following, we separately bound the bias term and the variance term. We first assume & B+p in Appendix 1. and Appendix 1.2, then the case ++pis treated in Appendix 1.1. Finally in Appendix B.2, we establish the same convergence rate for regularization via bias contour.
B.1.1 BIAS
Lemma B.1 ||AD Ax $ N min
8- BEp 11
Proof sketch: Since |Aolla, & B, we can write Ao -+0 +00
4 50- @ e, where the -==1 a:sl Pj
coefficient matrix Ao = (aij) satisfies Aoll. & B². The definition (8) implies that for E < UN and i we have
As.dee [i (CK + -11) u² mfei)
# L
= -pp (s Ss, (CKK + A1 14/ utei)
Pj 1 aij.
ps + X3
16

---

Published as a conference paper at ICLR 2023
The bias term can be bounded as follows:
+.00
C 1 1 }
2
|140 - Auller
Pj
EffyCo Qx (Ao
KK Mi ei
UN
+00
X3
8'
(1s + X1)² az
X3
8-8
max 131
P4
(1i+ + 23)2
1=1
UN
+00
(3-8")
ai < 2
max
X (8-88)
18y
1=1
i=1
We now prove that
3-- p¹
2
min
A1 " UN.
(10)
Case 1. 1 cu
then
log
X5-
> 15-0"
2
2 3-3²
N
where we use a & 3 + p the final step.
(a d'=p 1=3 )
) )
Case 2. If 2₂
we need to consider two sub-cases:
II I'+p
1-t' 1-7
then we have A, = (N
and thus
3+p
0
d'op La -
R-dd 1-
d-s'
N F+F j
N
F+F
If D' 3+p
< then similarly we have \o= = (N لبيد
and
j 3 x--00 = -0 (Ntr'
8-8¹ 3/4
( N
i ?
= N 1
7 V/
UN
Hence, in all cases (10) holds and we have that
|1A0 ANl S N
min
of A+P
(11)
17

---

Published as a conference paper at ICLR 2023
B.1.2
VARIANCE
The variance term can be rewritten in the following way:
v
A
AA
12
1000
(A-AN)
KK
8/,7"
118
400
- (A-Aa)
Lmll
2
CKK m/ees
(12a)
Σ j=1
nN
Pj fir CLK (CKR + xxx)++ CLK (CKK + )z1) -1
Pj
M4
i=1
(12b)
Σ j=1
NN
Pj
(1-7')
+00
(CKk + 211) [CxL - (OXK + 2;1) (CKK + 2,1) CKE 2
oj f3
1-4
2
CKK + 21) (CxX+ + +,,1)
(CxK + +2y)
Mi
et
(12c)
Vus + d3
nN
100
2-0'
Σ Dj j=1
(1-7)
Un03Si.Cs
Σ
0e
Mit
nN
||G,|| E 12,, 8 ||00
(12d)
In (12), (12a) uses the definition of the Hilbert-Schmidl norm; (12b) follows from the definition of Á
(3) and the fact that for any j > UN. we have (p) fz, (A (A- A1A1)) p e.
0: (12c) is obtained
from re-arranging and (12d) follows from
Ete 2 2-00 M+, & e, max431
2 2-
S 2, 8" and
Ma+
Pj S
Note that
U. = (CKK + 111)=
[CKL-
[CKL - CKL - (CKK- CKK) (CKK + X11) -1 CKL)
1 N
[CKK+ - U/ @ Uh - -Exx, Us & Auu - (ux & u4 - EP ux @ us) (CKK + (CKX+ =111) Axx
N
Σ [CKK + A11) (ux @ (vu Aoux))
N
=0
N
CKK + 1 uk 2 Agus EPKs us @ Aguk - (uy 2 uk - EE uy @ ux) (CKK + +2y)) CKKAN
N
=13ートソ + (exx 3 (1x8A)(((xxx551) lux Lug-Erxz un An tua)
The U7 term is the variance of observational noise and U3 term is the variance of regularized bias. Thus the UJ term is the dominating term. Plugging the above decomposition into (12), deduce
18

---

Published as a conference paper at ICLR 2023
that V < 2V/ + V2) where
V1 < 1
max
nx ||Gy||
1-7
g
1 N
Koz Aoux: 13)) f3) (CKK + 2z1) mb
N
j=1
Aom
nN Σ
1/2 ~ max 1EjERN
||
Aj
2-
( (
Ao (Cx* + )31) un,
un, 03 13) (Cxx + );1)= uk
j=1
2,
(13)
where E[x]
= N Ek=1 Xx denotes the empirical mean. Define the event
1
E1,5 { G,
c, =
(0,=|1P, |IP,,
(Cxk)]& [Ps, (Cxx)] [Pe, (Cxx)) < <2van
Ev by Theorem D.3, we know that Ei, holds with probability >
Recall that my < 00
log N
2e As result Ej = nタ Ei, holds with probability > 2nne We assume event
E₁ holds in all the following proof.
Bounding V1. Let
x,,k = j 23 -4 (vx- Anun. f.) (CKK + Xy1) up E HK
and X₂ (X,x: : j nN) HK Then we have Vi $ N Ex= Xx | where the norm here
defined for H 68x is induced by (a, b) = >i (as, bi) Note that X2, = 1,2, NN are i.idd random variables with mean zero, and
AN Σ
E | 11 = EPKC.
nx
2 8¹ U1 Aou1, .3 1:)² [CKK + + 11?)
Eprc
1-1
sup EJ SUN wEsupp(Pk)
max
j j is
|[CCK + 2g1) u
=:G
nx
E Pu,
-10- - 2t
A 8¹
Aou, po) > + 2z1) tul
j=1
=:
By Lemma D.2 we have
G1 أ L_
أ X, (8)
For G2, note that for fixed u, Assumption 2.4 implies that
NNN Σ
6' (v-
Aou, ||Cc + 25T) +u)+"(l r1())
Epju
||0 - Anull 20-2
17
1=1
(26) 2
Σ
X 8
|CKK+ + 291)=
j=1
19

---

Published as a conference paper at ICLR 2023
where 03 = f3. Votts) Vot As a result, we have
G2 & Epx
122)11222 2
Σ
o
1j |[CKK+ +2,1)* u11
< 2 (20)1
0²
max 1EjEnN
j ,3
2
j=1
where in the second step we use
Σ
03 ttr (V) 0² and
||(CKX+ + 1,1) 111) 3 u0
[CKK 2,1) 3 u (CKK + X11) à au) u
Epx
< tr
Epx
+00
= tr
Ci 8 6i
Mi + x2
#=1
P4
#4 + A3
S 177.
We have shown that for some constant c > 0,
j ز" 2 1-1
| 2 < (26)10²
max 1
j غ² , --
R2
max iEjEny
By Bernstein's 's inequality, the event
1
0² maaxxjelxx]]
X;
7-(8't1) +p)
RR maxi<ienn j L Ag
(8'+a)
F2g
Xx
< 602
N
N2
(14)
holds with probability > 1 1 2e 22, By our definition of Xj. have
18' (8'+p)
+p) S N mmx 340 1=2
max 1
and X, 2 - (which implies that the Noz term is dominated by the 3/4 term). Hence, under E1 nEg we have
V1 S Q1a20 N mine d-a! 345 T )
with probability > 1 22nee 02
Bounding V2. For any j E Z+ we have
BuNPx (Ab + Aa1) u. 1.)
= BRNPK (p) [Ao (Cox + xzT)=² [Ax(
0 Ao (CKK + (51) u2 13 1;)
- -(p3 (p3 Ay (CKK + >11) Ckk (CKR + +1z1)= Aip) 15)
(15a)
13- (CaT Aoc ا )
o f, (CKK + 2y1) CKK (CKK + x111)=
(cat AoC
1-
p3 f
(15b)
S - x (2-0)
(2-8)
1=n 1-dl C
A
P3. fz
(15c)
=:,,
where (15a) follows from BpguSu CKK, (15b) uses the fact that CKK and CKK + Xy commute, and lastly (15c) follows from
[CKK + - cxx (CKK + Ay1) 11 α 1, (2-1)
7x
20

---

Published as a conference paper at ICLR 2023
Let
Yg,== (Ao (CxK + 2,1)²² uk, 1 1 (CKK XyT) us HK
and
Yv = (Y
E & yN) E Hk
Then we have
1 N
V22 S
Σ
YK
N
Note that Yx, h = 1,2, .N are i...d random variables, and
1 )
B
EE
Σ
EPx
X3 2-8
(Ao (CRK + 211))) un 11) || Tis (un) (mmi)]
1-1
N.N
j q X3 12 (Ao (CKK + +2y)) u, 11. )) 2 |[ + 211)) =u] m
Σ /=1
sup (Esupp(Pk)
nx
E
Ao + 191) u, p f;)
sup
[CKK + 191) 2
2
uEsupp(Pk)
sup PPs)
Σ
ny
X3
ft' 2- -a (Ao (CRK + \11)) u, P3 03)) 2
NN
-
-88' +a 3) D32-
/=1
(16)
For any j E.p. and u E supp(Pk) we have
N
(0'+0) (Ao + 211)== (,) syu, * 11)²
BN
I-y' X (10++0) (2 (A 12 + +22 (car= Ao (CKK + Ag1)) " )²
j=l
(17a)
| AnC 1=2 )
2
max 16J
j
1-1/
X (33++o) +
- (80 +00) X3 max
03
(17b)
max j 4 X, +a) 18JEyN
Ln'
Xj -(8'+aa) -mx max0a
+ max
(17c)
where (17a) uses the AM-GM inequality, (17b) follows from the assumption that ||Aouu|| < Ag is uniformly bounded, and that
CRKu = |ll (Cxx + +11))= (CKR² - w) S2, max max 8.0)
CKK (CKK + >yT)
by Assumption 2.2, and lastly (17c) follows from || p.y & B.
Plugging into (16), we deduce that
E||y!] 2t
t-1 1-y' 2, (8'+a00
sup wEsupp(Px)
max 1EjEnx (xx)
jo a A7
I-y
-(1'+a))
+
max 16jEnN
X +a) (a (00--)))0000--000
18) D3.2
j=1
I 2, (18'ta)
X, maxxaa)
-3' (3' ta-
sup nEsupp(Pk)
max 1g
max 18j5
max 15EAN
21

---

Published as a conference paper at ICLR 2023
where the last step follows from ΣØ= +00 By Bernstein's 's inequality, there exists constant C3 such that the event
D3.2 ||Aull
1-7
x 10'
+)
max b3 (8'+aa i / + 23
max B.0)
E3 { V2 < 6a3C3
N
N2
(18)
holds with probability > 1 - 2s
The definition of An implies that the Ny term dominated by the N term,
max j o X (3' (#' x N min ( I&
1/2 S 0103
holds under Ej n Ez. To summarize, under Eσ n Eg n Eg which holds with probability > 1 2nye -a 2e az 2e as, we have
V 201 max a (V) + V2) S N min
Recall that the bias term is upper bounded in (11). This gives the final upper bound
x N min a- = | Ao A
2(54p)12(11) ((11)))
B.1.3 THE HARD-LEARNING REGIME
In the previous sections, we focus on the case where a & B + p and establish an upper bound for the convergence rate via an optimal bias-variance trade-off. The opposite case, > + is referred to as the hard-leaming regime, for which the optimal rate is not known for several decades even in the case of 1 (cf. the discussion following (Fischer & Steinwart, 2020, Theorem 2)). In the hard learning regime the V/2 term becomes the leading terms.
In this section, we use the technique developed in previous sections to obtain an upper bound in the hard-learning regime. To do this, we need re-define the truncation set Syy as follows:
SN
(z. v) Z
s'+0-6
<
and x & co log N
N
The definition implies that the variance can be controlled by N min e 0¹ -2111) and remains to focus on the bias term.
Similar to the derivations in Appendix B.1.1, we have
Al TN (Ab)) S max
(KJ)
The maximum value of the right hand side can be achieved in either of the following two cases:
* i (()). Then we have 2 N (1-minf أوو x14)) so that
B-
(--minf 2-ي4 xي })
< N 1
= O11. In this case we must have S N m-min 2 2. g by definition. Hence we have
p Yー
otherwise it falls into Sy
8-
B-dd
N mind 2 (
Z'tz and 1/3 <
On the other hand, for the variance term we still have V S 1 N maxisjeny 1
L t1
N maxi EiEnn
so that
I-ay 8'-a-d
R-gl min
Bap Aap 1'=7)
V V
max N 1EJERN
N
22

---

Published as a conference paper at ICLR 2023
As result, obtain the following convergence rate:
A - Ao Aol
S N min A
B.2 REGULARIZATION VIA BIAS CONTOUR
In this subsection, analyze the convergence rate of regularization via bias contour (cf. Figure 2). Specifically, we consider the estimator (3) with the choice
> = max (
minn
cco
N
(19)
log N
now remains to plug the above Xy into our bounds for bias and variance derived in the previous subsections.
Bounding the bias term. follows from (9) that
|| - Axllay S
max j Eg
Xo 8-B8
min
a g
N log N
2A max
mart p
.00
min
Bounding the variance term It follows from (14) and (18) that the variance is bounded by
A Ax
I N 1EIEUN
max
(o' + (a-.)))).))
8',
As before, we consider the cases a & B + p and
B + separately.
a & B + p. then it follows that
-- ((''t))
A
AA
max j j& X, EEJEUN
8' 8/
dig
y-min
R-
Atp 1
max N 1&J
g'
Z'zg
min
max LEJ
j
N
1
L d'in 4-y
max N jE(LNN)
min STF
max
d'+p
+
N min
8-8 Div 1==)
a-2" Y57 } ع/ا min where use VN
34p by definition.
. If > B + then similarly we have
Á A1
j X 0'+a03
max 18j
d'
j 1-Y
- N minf e {2)) {
max
N 16
j س-سسي mi {+])) Lyge
max
N
JE(L,N)
< N min 8-
23

---

Published as a conference paper at ICLR 2023
Hence deduce that
| | 2 N
Anl Bi,
mine p=md
desired.
B.3 IMPLICATION OF THE UPPER BOUND
In this section, we discuss the implications of our upper bounds under the (8', -norm.
Note that C
= |1 for all v E L2(Qk) (if one side of the equation is too then
Hz
so is the other), we have that
ExpPx ((A- Ao)
-is" (A - Ao)
ull ue Htee
BuTPk CER
tr CQx
- 2
(A- - Ao) Be u su
Cqx
2 (A- AA))
A Ao 12
(20)
where the last step follows from Eu @ u Cpx- Note that the above derivations hold for any O & 3' < 33 so choosing 3 = 0 yields the best upper bound. We can see from (20) that our analysis implies upper bound of the expected error of the learned solution evaluated under the H2- norm. On the other hand, it is also possible to obtain uniform convergence rate when 3' > az
( - Ao) u H!7
(A Ao)
CQK
u
Mr.
A - Au
A
Au A
C PROOFS FOR THE MULTI-LEVEL OPERATOR LEARNING ALGORITHM
In this section, we analyze the convergence rate of our multi-level algorithm described in Section 5. 8-3' 1
We define v min 8-8'
mux Y and 1/2 max {1 max
?) We
first restrict ourselves to the when maxta. * 2'=7; the special case when the two terms are equal will be separately treated in Appendix C.I. For the optimal bias and variance contours l f bias and fCr with Ci = N and C2 = N we define sequence { as follows:
8-9
1-7;
1 N i
N
max
2
No
92
co
log N
(21a)
8'mmax(a-A.11
Vn the solution of Fn
N
n
(21b)
--
En+1 the solution of x yn
N
0.
(21c)
We first derive explicit recursive formula for {
Lemma C.1 Let u
8' +maxfa- 8.pl
2'-3 > 0, then
B-B
(1). if > then
N F.P Ent1
NN tfr (frrn)) xm))
(2). if < 1, then
Fn41 x/
24

---

Published as a conference paper at ICLR 2023
Proof:
(1). Suppose that u 1, then have 7/ and (21c) that
8-8 max(o,0+0)
and 7/ 7/1- It follows from (21b)
x'-" 3-
Tn+1 N ma. (a.d pl yn
o¹ | Axl
N max(a.d-pp
2
N (eed mox 2p
(2). Suppose that < 1, then we have 711 and 1/2 I-
1-y
that
1-
and it follows
122
s'+maxla-hp 8.pp)
2-8¹
from (21b) and (21c) that 2n
nt1 thus In+1
x
Lemma C.I implies that when u o 1, the sequence { decreases super-expomentially Thus, there exists LN Ollog log N) such that win. & 2 for all 2 LN-
Let x(x) =x b and 1 =
then we construct the following estimator:
LN
An
Σ
13 êrx (Cok + x(²)))
(22)
where y-1 := O. Note that each summand in the above equation is essentially regularized least- squares estimator and learns a rectangular region. The following theorem states that the estimator Au1 can achieve minimax optimal convergence rate.
Theorem C.1 Consider the estimator An defined by (5). Suppose that Assumptions 2. to 2.5 hold, then there exists a universal constant C, such that
min
8
A - Au A B',
CCT
N
log N
log N
holds with probability > 1_
Proof: The proof of Theorem 5.1 is similar that of Theorems 4.1 and 4.2. We consider the bias-variance decomposition of the estimation error
Am - Ao B/
<
Am
- Ad
+ AA. - Aollery/
where
1
Σ
p3 p
Crx (CKK + 2 x(111)) +2
(23)
i=0
Bounding the bias term. Since || B,7
B, we can write
1- anyi Pj f
Ao =
where the coefficient matrix Ag = (ar)) satisfies | < B². We fix (i.j) E Z and assume WLOG that Ym < y/m for some m O. where 1/EN+1 +00. It follows from (23) that
LN
(p)
12 fz
Ani
Σ
Σ
p f
1f (CKK + x(0))) mre
k=n
1
μ4i
1-2
1-2
#4: + x(k)
(K)
Ps"
14
Aij.
25

---

Published as a conference paper at ICLR 2023
Thus
Ao
An
Q1
7
(Ai - -Ab)
CK
1-n'
1
HHS
Pj Cj, Lييn" (A) AAo)
1-8
C
kk 2i Co
+00
Am,
2
8-8 8 of
-
2
11
Xm,
Amy
(K)
2
(24)
Σ
azj
max u.g 1321
1-00' 88
(K)
1=1
14 +
Xms
B-D'
0-8
Σ j=1
P3
(Alkk)
ij
2
Bd max p3 1>l
(mm)
< B² max Pj
Ims
B²
max j
Imy
13
32
1/-7
B² Umy
Tmy
S N m
where we recall that ?/1 min
3-8
and the last step follows from (21c).
max(o,
Bounding the variance term. The variance term can be rewritten in the following way:
2
V
An
A
CQ.
(As
15--A Ab
CKK
I-d'
118
(Arl - -Ahi)
I-
qr
CKK
14
ci
4==1
(1-71)
Σ
03 13 (exx (CKR + Ams ) -1
Cyx (CKK + \m -1] 1- o'
ei )²
Pj
Mi
1=1
-2 1=1
(CKK + D) [CxL= (CKK + sms (Cxc + Amy 1) CxL p3 si.
Pj
=:Umg
2
(CKK + Am
(Cxx + +dmss)
-1 (Cxx dans 1)
14
Ci
v #4 +
Aj
-.mg
NN
20
2-
(1-7))
Umip Jy,Grm Gms
es es
Umg
Mi Amy
j=1
2N
j I-r! |Gm, ||²
Un, fyl"
1=1
for reasons similar to (12). It now remains to bound ||Gm,) and Um, p3 fr for 14 & Lx. Note that these quantities have already been bounded in Appendix B.1.2 with Am, replaced with >, (there we use a different regularization for each j). Hence, those bounds can directly applied here, so there exists constant C > 0 such that
V & Ca² 1
I- -03' -mxx(aa-8.p)
max j Am
N
16JELN
26

---

Published as a conference paper at ICLR 2023
with probability > 1 Ne Since & Vmy by (21b) we have
ma' (.p)) 2 ymn Im;
1- o -
Am,
N
Hence
(0'' +
V
max L
Am,
< NNp-1= N
N
Combining the bias and variance bounds, the conclusion directly follows.
C.I
SPECIAL CASE:
8-8 max (p.
Note that Lemma C.I does not cover the case a = 1, or equivalently max(a.8+p) case is special since the bias contour coincides with the variance contour, and we need to modify our construction of the multilevel estimator.
8-8
x'22 This
1-7
We define two sequences {aa}: } [un] } as follows:
N=
N
2u = max
log N
(25)
En In-1
-/-2 Yn the solution of Yn
Fn
N
where we recall that ?)1
8-g' \ In this case, there exists Ln O(In N) such that
max (K)
En < 1 for all > Ln. Let
X
then we construct the following estimator:
Ln
A
Σ
p f1 BBppi
CLK (CxK + + +2(+50)
(26)
1=0
Similar to Theorem C.I, we can establish the following result:
Theorem C.2 Consider the estimator Aa defined by (26). Suppose that Assumptions 2.1 to 2.5 hold, then there exists a universal constant C, such that
min
| - Au B'
CT?
log N
log N
holds with probability >
1T
Proof: The proof of Theorem C.2 is similar that of Theorems 4.1 and 4.2. We consider the bias-variance decomposition
Am Aol 0'.7'
& Ama
Aia lor + || sollory
where
0f p3 bi-1
Σ
CLK (C + x(()11)
(27)
as defined in (26).
7 1- fr Se with coefficient matrix Ag = Bounding the bias term. Let Ag == Σta j==1 azj4 P,
(ag))tye such that A 113 & B², We fix (i, z and assume WLOG that Um & < Vmn
for some m, 3 O, where 1Lx+1 = +o0. It follows from (27) that
(0) lor Ahuiees
#4
[KT P3
P4
Oij-
+
X
27

---

Published as a conference paper at ICLR 2023
Thus proceed as in (24) to deduce that
(X(1)) 8-8
|1Ao
Ab
11 o
& max
/3
121
B--
X max
max LEjELN
Imy
B-8
max
max 1EjELN
Um--1
Ims
The definition (25) implies that
3-28
8-8 -/-3 8-gt
mmg 2m,
< 2 P
Vmn
mm
< 2 F N
On the other hand, since ILN
< 1, by (25) implies that VLN
S No Therefore, for the bias
term | - A1 8 N
Bounding the variance term. Repeating the arguments in (25), we can deduce that there exists constant C such that
1
j -' Am,
((''mmax/aaB))) Caa N LEGELN
1_ (0' mmxx( 0.)))
V Ca N LEJELN
max
Vm Imz
N 91
with probability > 1 Ne
Combining the bias and variance bounds, we arrive at the desired conclusion.
The conclusion of Theorem 5.1 then follows from Theorems C.I and C.2.
D AUXILIARY RESULTS
Lemma D.1 We have | = ||020
(1- (1- T c HS(H
c/2
Proof: We recall from the definition that || - (Tim.e)) o To Pooiige li H9)
so that
|T B,y = (1)m)e) o oTo oi (HS(H)
2
P3 fj. (Li.. ) oT K.
247
2
pj زز (Tim
TTT 1-
76
Σ
p3 fg, TH, 1- Fes)
74
=
Σ
( fy, CoL
1// T C
cl1-8)/2
m/ee) HL
2
coll o T' o KK HS
(1-////
c(1-8)/2|
as desired.
Lemma D.2 Under Assumption 2.2, we have
|| [CKK+ + 21) xx-= Ai Px-as.
28

---

Published as a conference paper at ICLR 2023
Proof: By Assumption 2.2 we have | 1
& A1, so that
Hx
[[CKK +1) u
|CKK + -11==
| u < -
as desired.
D.I CONCENTRATION INEQUALITIES
Theorem D.1 (Fischer & Steinwart, 2020, Theorem 27) Let (Ω, P) be probability space, H be a separable Hilbert space and X Q + HS H) be a random variable with self- adjoint values. Furthermore, assume that [|X & B, P.P a.s. and V be positive semi- definite matrix with Ep (x2) & V, i.e. V Ep (X2) is positive semi-definite. Then, for g(V) = log (2e (2e(r(V) T 1, and 1, the following concentration inequality satis- fied
pm (WI,..., EΩ"
x (w:) Ep (w:) EpX(w)) -
4TBg(V)
2T V
< 2e
3n
Theorem D.2 (Fischer & Steinwart, 2020, Theorem 26) Let (9,, B, P) be probability space, H be a separable Hilbert space, and 5 92 - be a random variable with
E < 2 mllo - m.
for all m 3 2. Then, for 2 1 and n 2 1, the following concentration inequality is satisfied
72 32
L2 1
pa (wI,..., wn) E
c (wxi) Epf
>
0²
2
n
The following theorem shows that the regularized covariance CKK + XI can be estimated with small eπror when is above a certain threshold. Although it well-known (Fischer & Steinwart, 2020; Talwai et al., 2022), we still recall it below for completeness.
Theorem D.3 Recall that CKK EP u & and ČKK NV. E u, u, where u, ii.d. Pk. Suppose that Assumption 2.2 holds and N Z AlTgxd-a, where gx log (2eNrxx (A) and Nr (A) = =v ((Crk > the effective dimension, then with probability at least 1 T we have
[[Cxxel++A [[xxxl] ||
[[CKK+>))* (CkK-CKK) (CKK + 3
ARTgA N\a
< 0.1.
(28)
Proof: Let (u) = (COK + 2 u u (CKK + AT) where E Hk. then the LHS of (28) can be expressed as > Em X(u:) - EEW X We hope to apply Theorem D.1 and start with verifying the assumptions.
Since Epx X
(CKK + CKK (CKK + A and [X = [I(())l
[CKK + +X1= ull & AF||ICKK xX) 1-0 S APX-9, so that there exists V
O (X-a (CKk + -I (CKK + +X)- such that Ep & V. It's easy to see that
| < x and tr(V) S NNw (A). The conclusion then follows from Theorem D.1 with
B = O(X and g(V) 9x.
Corollary D.1 Under the notations and ussumptions of Theorem D.3, there exists constant C₁ > with probability 2 -- we have
(CKK + +1)= (CxK+ Bek+>1)
(CKX + 27) EC-
(29)
29

---

Published as a conference paper at ICLR 2023
Proof: By Theorem D.3 we have
(CK + A1)² (CKK Sack-Crit -CKK) (CKK + +x)=
(1 (Cxx + 3 CKK))C + A1) -1
2
with probability > 1 e as desired.
30


Reviews:
[{"review_id": "v66IDkczqQ", "reviewer": "Reviewer_B1fn", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of learning a linear operator from one RKHS to another RKHS (hereafter from an input RKHS to an output RKHS). In this literature, it is common to study a certain kind of mis-specification: what if the ground truth belongs to an interpolation space between the RKHS and L2. Whereas previous works on the problem consider the mis-specification with respect to the input RKHS, this work considers mis-specification with respect to both the input RKHS and the output RKHS, which is a generalization. The authors characterize the learning lower bound in generalized Hilbert-Schmidt norm and analyze a new multilevel estimator that attains it.", "summary_of_the_review": "This paper joins a mature literature, but I think that its study of the output RKHS mis-specification is significant. The lack of simulations raises the question of how feasible the multilevel estimator actually is. If the authors implement the minor improvements suggested above, I will raise the score.", "strength_and_weaknesses": "See below", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "rHOGdJ912f", "reviewer": "Reviewer_Zt4i", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of learning a linear operator between two infinite-dimensional Sobolev reproducing kernel Hilbert spaces, which includes learning differential operators and condition mean embedding as special examples. A novel information-theoretical lower bound is derived, which implies that the minimax learning rate depends on both the smoothness of input and output spaces. This paper proposes a multi-level kernel operator learning algorithm that can achieve the optimal learning rate.", "summary_of_the_review": "The paper studies the optimal convergence rate of learning a linear operator between two infinite-dimensional spaces, which should be of interest to a broader audience in the field of machine learning and scientific computing.", "strength_and_weaknesses": "$\\textbf{Strength}$\n\n1. This is a novel contribution that provides insights into the understanding of operator learning between two infinite-dimensional spaces, a topic with various applications in scientific computing, machine learning, and statistics.\n\n2. The minimax lower bound for learning a linear operator is interesting and novel, which characterized the difficulty of this problem.\n\n3. The proposed multi-level kernel operator learning algorithm also makes a solid contribution and the insights are valuable for the design of other operator learning algorithms.\n\n4. The mathematical analysis of this paper is rigorous and sound, which extends the previous results for learning differential operators and conditional mean embedding.\n\n$\\textbf{Concerns}$\n\n1. Can the analysis (or lower bound) be extended to nonlinear operator learning?\n\n2. The definitions of $\\hat{C}_{LK}$ in (3) and (5) are not given. It is also a little confusing how $\\hat{A}$ can be calculated in practice as $\\rho_j$ and $f_j$ are not easy to obtain.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TRnEZVAJHQ", "reviewer": "Reviewer_7Ap7", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of deriving theoretical learning rate for learning mappings between infinite-dimensional function spaces. As noted by the authors, it is an important topic to understand how much training data is needed to approximate linear operators within a prescribed accuracy. After reviewing existing theoretical works on operator learning connected to PDEs, the authors derive a lower bound for learning linear operators between infinite-dimensional Sobolev reproducing kernel Hilbert spaces.", "summary_of_the_review": "While the paper contains novel and significant results on the sample complexity of Hilbert-Schmidt operators, its technicality and density prevent the readability. I believe that a revised version of the paper, including the proofs in the main text and expanding on the background material and interpretation of the results, would be more suitable for a top machine learning journal like Journal of Machine Learning Research (with a longer review time allowing for a careful check of correctness) rather than a short conference paper with a long supplementary material.\n\n--\nI have updated my score following the authors' response.", "strength_and_weaknesses": "### Strengths\n\n1. The problem of deriving theoretical learning rates for Hilbert-Schmidt operators addressed by this paper is a significant topic with applications to understand performance of state-of-the-art neural operators approach for learning solutions operators of PDEs.\n2. The authors derive a novel lower bound for learning linear operators between Sobolev reproducing kernel Hilbert spaces, generalizing existing works by Li et al (2022) which takes into account the output space (as opposed to prior works).\n3. The lower bound on the learning rate is optimal as shown by the authors who introduces a scheme achieving a near-optimal learning rate.\n\n### Weaknesses\n\n1. The paper is very technical and dense which makes its understanding very difficult beyond section 1. More backbround material should be provided in section 2 on reproducing kernel Hilbert spaces and Hilbert-Schmidt operators along with concrete examples connection to operator learning associated with PDEs.\n2. The lower bound provided by the authors in Theorem 3.1 is the main result for the paper but little explanation and interpretation is provided in the section and no comment on the proof techniques.\n3. The multilevel kernel operator learning scheme of section 5 seems interesting (based on the theoretical results in Theorem 5.1) but I don't understand the method, which is essentially described in one sentence by Eq. (5). I would suggest rewriting the section to describe the method extensively, eventually adding a simple illustrative examples.\n\n### Minor comments\n\n1. End of page 3: \"kernl\" -> \"kernels\"\n2. Could the authors add some interpretation on the assumptions for the kernel in section 2.2?\n3. Some equations are missing punctuations, e.g. Lemma A.1, A.3...", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "N0VRzPO6Ofv", "reviewer": "Reviewer_v7T2", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of learning trace-class operators between Sobolev reproducing kernel Hilbert spaces. Information theoretical lower bound of convergence rates are derived. The machine learning problem is characterized by bias contour and variance contour on spectral spaces. Three regularization schemes are proposed inspired by the bias and variance contours. All three schemes are proven to achieve the minimax lower bound subject to a logarithmic factor.", "summary_of_the_review": "Inspiring characterization of bias and variance contours. Neat convergence analysis with the estimations achieving minimax optimal rate.", "strength_and_weaknesses": "Strength\n1. Clear insights provided by bias and variance contours\n2. Important mathematical problem well motivated by many applications, including generative modeling, functional linear models, causal inference, multi-agent reinforcement learning, and so on.\n3. Analysis achieves minimax optimal rates\n\nWeaknesses:\nNo significant weakness has been identified.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "0XFORg-Orb", "reviewer": "Reviewer_EtQp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper analyses the problem of constructing maps netween infinite dim function spaces.  The paper claims 3 contributions:\n\n1. An information-theoretic lower bound of learning a linear operator between two infinite-dimensional Sobolev RKHSs consisting of two polynomial rates, the first of which depends on the input space and is consistent with known results, the second of which depends on the output space and is novel.\n\n2. A study of the shape of regularization needed to obtain the optimal learning rate.\n\n3. A setting where a multilevel training procedure is needed to achieve the optimal learning rate, which is distinct from the finite-dimensional case where a single-level estimator suffices.", "summary_of_the_review": "The paper presents novel results in what appears to be a thorough and informative manner.", "strength_and_weaknesses": "The paper is soundly written and to the best of my knowledge the theoretical contributions are novel and provide insight into the problem.  Examples are given to motivate the mathematical development and there is commentary describing salient points.\n\nMy one complaint is the lack of any summary of proofs in the body of the paper.  While obviously it is not practical to include the actual proofs, it is useful to include some indication of the important steps or interesting methods required in the body of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%