Error Bounds for Learning with Vector-Valued Random Features
Authors: Samuel Lanthaler
Nicholas H. Nelsen
Venue: NeurIPS 2023 spotlight (2023)
Keywords: random features
random feature model
operator learning
vector-valued

Abstract: This paper provides a comprehensive error analysis of learning with vector-valued random features (RF). The theory is developed for RF ridge regression in a fully general infinite-dimensional input-output setting, but nonetheless applies to and improves existing finite-dimensional analyses. In contrast to comparable work in the literature, the approach proposed here relies on a direct analysis of the underlying risk functional and completely avoids the explicit RF ridge regression solution formula in terms of random matrices. This removes the need for concentration results in random matrix theory or their generalizations to random operators. The main results established in this paper include strong consistency of vector-valued RF estimators under model misspecification and minimax optimal convergence rates in the well-specified setting. The parameter complexity (number of random features) and sample complexity (number of labeled data) required to achieve such rates are comparable with Monte Carlo intuition and free from logarithmic factors.

Error Bounds for Learning with Vector-Valuee Random Features
Samuel Lanthaler" California Institute of Technology
Nicholas H. Nelsen" California Institute of Technology mnelsen@caltech. edu
slanthocaltech. edu
Abstract
This paper provides a comprehensive error analysis of learning with vector-valued random features (RF). The theory is developed for RF ridge regression in fully general ciinite-dimensioon input-output setting, but nonetheless applies to and improves existing finite-dimensional analyses. In contrast to comparable work the literature, the approach proposed here relies on direct analysis of the underly- ing risk functional and completely avoids the explicit RF ridge regression solution formula in terms of random matrices. This removes the need for concentration results random matrix theory or their generalizations to random operators. The main results established in this paper include strong consistency of vector-valued RF estimators under model misspecification and minimax optimal convergence rates in the well-specified setting. The parameter complexity (number of random features) and sample complexity (number of labeled data) required to achieve such rates comparable with Monte Carlo intuition and free from logarithmic factors.
Introduction
Supervised learning of an unknown mapping 9: X' + y' is core task in machine learning. The random feature model (RFM), proposed in [36, 37], combines randomization with optimization to accomplish this task. The RFM is based on linear expansion with respect to randomized basis, the random features (RF). The coefficients in this RF expansion are optimized to fit the given data of input-output pairs. For popular loss functions, such as the square loss, the RFM leads to convex optimization problem which can be solved efficiently and reliably.
The RFM provides a scalable approximation of an underlying kernel method [36, 37J. While the for- mer is based on expansion in M random features :.)..... :o( :pp::00m (.r). ), the corresponding kemel method relies on an expansion in values of a positive definite kernel function K(", "1),.... K( ux) dataset of size N. Kernel methods are conceptually appealing. theoretically sound, and have attracted considerable interest [1, 6, 40J. However, they require the storage, manipulation, and often inversion of the kernel matrix K with entries K (u,, u,)). The size of K scales quadratically in the number of samples N, which can be prohibitive for large datasets. When the underlying input-output map is vector-valued with dim p. the often significant computational cost of kernel methods is further exacerbated by the fact that each entry K K(u,, u,) of K is. in general, a p-by-p matrix. Hence, the size of K scales quadratically in both N and p. This severely limits the applicability of kernel methods to problems with -igeh-imensional. or indeed infinite-dimensin
output space. In contrast, learning with RF only requires storage of RF matrices whose size quadratic in the number of features M. When M & Np, this implies substantial computational savings, with the most extreme case being the infiiitediimensionll setting in which = oc.
In the context of operator learning, the underlying target mapping is an operator G: X + ) with infinite-dimensional input and output spaces. Such operators appear naturally scientific computing
"Equal Contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and often arise as solution maps of an underlying partial differential equation. Operator learning has attracted considerable interest, e.g., [3. 16, 20, 25, 27], and in this context, the RFM serves as methods with considerable potential for sound theoretical basis. Indeed, an extension of the RFM to this infiiitediimensional setting has been proposed and implemented in [32]. Although the results show promise, mathematical analysis of this approach including error bounds and rates of convergence has so far been outstanding.
an alternative to neural network-basse
Related work. Several papers have derived error bounds for learning with RF. Early work on the RFM [37] proceeded by direct inspection of the risk functional, demonstrating that M = N random features suffice to achieve squared error D(/VVN for RF ridge regression (RR). This result was considerably improved in [38], where VN log N random features were shown to be sufficient to achieve the same squared error. This improvement in parameter complexity is based on the explicit RF RR solution formula, combined with extensive use of matrix analysis and matrix concentration inequalities. Similar analysis in [26] sharpens the parameter complexity to VN log dā random features. Here dž is the mumber of effective degrees of freedom [2, 6]. with À the RR regularization parameter and K the kernel matrix. In this context, we also mention related analysis in [2]. In all these works, the squared error in terms of sample size N match the minimax optimal rates for kernel RR derived in [6]. Going beyond the above error bounds, [2, 26, 38] also derive fast rates under additional assumptions on the underlying data distribution and/or with improved RF sampling schemes.
Many works also study the interpolatory (M = N) or overparametrized (M >> N) regimes in the scalar output setting [10, 14, 15, 18, 29]. However, when p = ddim()) > 1 or p = 00, such regimes may no longer be relevant. This because the kernel matrix K now has size Np-by-NNp, and is possible that the number of random features M satisfies M < Np even though M > N. In this case, sigh-dimensional vector-valued learning naturally operates in the underparametrized regime.
In the area of operator learning for scientific problems, approximation results are common [11, 13, 19, 17, 22, 24, 39, 41] but statistical guarantees are lacking, the main exceptions being [4, 12, 21, 31, 43] in the linear operator setting and [6] in the nonlinear setting. The RFM also has potential for such nonlinear problems. Indeed, vector-valued random Fourier features have been studied before [5, 30]. However, theory is only provided for kernel approximation, not generalization guarantees.
To summarize, while previous analyses have provided considerable insight into the generalization properties of the RFM, they have almost exclusively focused on the scalar-valued setting. Given the paucity of theoretical work beyond this setting. is priori unclear whether similar estimates continue to hold when the RFM is applied to
vector-valued mappings.
Contributions. The primary purpose of this paper is to extend earlier results on learning with random features to the vector-valued setting. The theory developed in this work unifies sources of еггог stemming from approximation, generalization, misspecification, and noisy observations. We focus on training via ridge regression with the square loss. Our results differ from existing work not only in the scope of applicability, but also in the strategy employed to derive our results. Similar to [37], we do not rely on the explicit random feature ridge regression solution (RF-RR) formula, which is specific to the square loss. One main benefit of this approach is that it entirely avoids the use of matrix concentration inequalities, thereby making the extension to an infinite-din diment-ddi vector-valued setting straightforward. Our main contributions are now listed (see also Table 1).
(CI) Given N training samples, we prove that M V random features and regularization strength I/VN is enough to guarantee that the squared error is O(1/vN) provided that the target operator belongs to a specific reproducing kernel Hilbert space (Thm. 3.7);
(C2) we establish that the vector-valued RF-RR estimator is strongly consistent (Thm. 3.10);
(C3) under additional regularity assumptions, we derive rates of convergence even when the target operator does not belong to the specific reproducing kernel Hilbert space (Thm. 3.12);
(C4) we demonstrate that the approach of Rahimi and Recht [37] can be used to derive of the-art art rates for the RFM which, for the first time, are free from logarithmic factors.
Outline. The remainder of this paper is organized as follows. We set up the ridge regression problem in Sect. 2. The main results are stated in Sect. 3 and their proofs are sketched in Sect. 4.

---

Sect. 5 provides a simulation study and Sect. 6 gives concluding remarks. Detailed proofs are deferred the supplementary material (SM).
Table 1: A summary of available error estimates for the RFM, with regularization parameter A, output space v, and number of random features M. (*): the truth assumed be written as (u) = Ee(a" (0) 0)] with restrictive bound la- (0) I R to avoid explicit regularization.
Paper
Approach
X
dim())
M
Squared Error
Rahimi & Recht [37]
"kitchen sinks"
n/a (*)
1
N
R/VN 1/VN
Rudi & Rosasco [38]
matrix concen.
1/vN
1
VN log(N)
Li et al. [26]
matrix concen.
I/VN
1
Volg(dk VN
1/VN
This work
"kitchen sinks"
1/VN
00
I/VN
Preliminaries
We now set up our vector-valued learning framework by introducing notational conventions, reviewing random features, and formulating the ridge regression problem.
Let F,P) be sufficiently rich probability space on which all random variables in this paper defined. Let X be the input space, Y' the output space, and θ set. We consistently u to denote elements of X' and A for RF parameters in O. The set of probability measures supported on set Q is denoted by g0 (Q). We write expectation (in the sense of Bochner integration) with
Notation.
respect to u ~ V E (X') as [. and similarly for 0 ~ p E (()). Independent and identically distributed (iid) samples W1,.... UN from will be denoted by [un} vBN and similarly for } ~ μ y We write = to mean that there exists a constant C 2 such that C-16 S S Cb and similarly for the one-sided inequalities S b and a Z b. We define A min(a, b).
Random features and reproducing kernel Hilbert spaces. Random features are defined by a pair (p,, p), where 9 X' x θ y and (()). Fixing 0 ~ μ defines map (p:::)); X + V. Considering linear combinations of such maps leads to the following definition.
Definition 2.1 (Random feature model). The map (();)) = o(-;a, {0m))) X' - ) given by
u ト+ (uu
M amip(u; 9m)
1
Σ
(2.1)
is a random feature model (RFM) with coefficients a E R& and fixed realizations {0m} ~ @.
Associated to the pair (yp, n)) is reproducing kernel Hilbert space (RKHS) H of maps from X to y [32, Sect. 2.3]. Under mild assumptions (see SM B) assumed our main results, it holds that
H = f E (x):))
([a(O)p(-;; 0)] and (0;
(2.2)
with RKHS norm
||||| = mina || ||a|l2g. where a ranges over all decompositions of G of the form in (2.2). minimizer ar of this problem always exists [2. Sect. 2.2]. We use this fact to identify any G H. with its minimizing a'h L3 (0; IR) without further comment.
Random feature ridge regression. Let P P(X x V) be the joint data distribution. The goal of RF-RR is to estimate an underlying operator G: X y from finitely many iid input-output pairs {(u, Vn) ]. n=1 ~ pON, where typically the are noisy transformations of the point values ((,,). To describe RF-RR, we first make some definitions.
Definition 2.2 (Empirical risk). Writing Y = {yn } for the collection of observed output data and fixing regularization parameter 0, the regularized Y -empiricaa risk of a E M is given by
N
M
BN a:: Y)
=
1 N
Σ ==1
llv, ((unia))3 Allallar. where ||a|1 = M
Σ
aam
(2.3)
m=1
is scaled Euclidean norm on M The regularized G-empiricul risk, Rd (ax; G), is defined analo- gously with ((u,)) in place of yo. In the absence of regularization, i.e., = 0. these expressions define the Y -empiricaa risk and G-empirical risk, denoted by RN::; Y) and L x (a; 9), respectively.
3

---

RF-RR is the minimization problem min (a; The minimizer, which we denote by a, is referred as trained coefficients and ((-:a) the trained RFM. For M and N sufficiently large and A > 0 sufficiently small, we expect the trained RFM to well approximate G. This intuition is made precise by quantitative error bounds and statistical performance guarantees in the next section.
3
Main results
The main result of this paper is an abstract bound on the population squared error (Sect. 3.2). From this widely applicable theorem, several more specialized results are deduced. These include consistency (Sect. 3.3) and convergence rates (Sect. 3.4) of the RF-RR estimator trained on noisy data. The assumptions under which this theory is developed are provided next in Sect.
3.1 Assumptions
Throughout this paper, we assume that the input space X' is Polish space and the output space Y is a real separable Hilbert space. These are common assumptions in learning theory [6]. We view X² and y measurable spaces equipped with their respective Borel o-algebras.
Next, we make the following minimal assumptions on the random feature pair (p.,u).
Assumption 3.1 (Random feature regularity). Let E (X) be the input distribution and (9, E., p)) be probability space. The random feature map yp: X' x Q - - and the probability measure E (P))) are such that (i) yp is measurable; (ii) y is uniformly bounded; in fact, | = sup (u.0)~u))~r))) [1 0)lly S 1; and (üi) the RKHS H. corresponding to (pp, p)) is separable.
The boundedness assumption y is shared in general theoretical analyses of RF [26, 37, 38]; the unit bound can always be ensured by a simple rescaling. We work in general misspecified setting. Assumption 3.2 (Misspecification).. There exist E L. ()) and Gn E H such that the operator G: X + y satisfies the decomposition G p Gn-
Since Assumption 3.1 implies that H. C L (X: any G GH + P as in Assumption 3.2 is automatically bounded in the sense that G E L (): Conversely, any E L (X) allows such a decomposition. We interpret P as a residual from the operator GH belonging to the RKHS. may be prescribed by the problem, as we will see later in the context of discretization errors in operator learning (Ex. 3.9), or be arbitrary, as is customary in learning theory when the only information about is that it is bounded.
Our main goal is to recover G from iid data {(un, }n)} arising from the following statistical model.
Assumption 3.3 (Joint data distribution). The joint distribution P E P( x Y) of the random variable (u, y) P is given by v with E ((X) and y G(u) + n. Here, G satisfies Assumption 3.2. The additive noise is random variable in Y that is conditionally centered, Ein u| 0, and is subexponential: [[ 3o; see (A.7) for the definition of (1))
Assumption 3.3 implies that ((u) = Ely u]. In contrast to related work [2, 26, 37], we allow for unbounded input-dependent noise. In particular, our results also hold for bounded or subgaussian noise, as well as multiplicatiiee noise (e.g., = (G(u) with Big u] = and || < oo).
3.2 General error bound
For any G, define the G-population risk risk functional or G-population squared error by
((:; = Eu-r) 4 uu a, (0m 1)13 for a E R
(3.1)
The main result of this paper establishes an upper bound for this quantity that holds with high probability, provided that the number of random features and number of data pairs are large enough.
Theorem 3.4 (G (G-population squared error bound). Suppose that G = pp p+ satisfies Assumption 3.2. Fix failure probability d E (0, 1), regularization strength X X (0, 1), and sumple size N. Let (0m) ~ ~ HM be the M random feature parameters and ((un }n)] ~ pan be the data according to Assumption 3.3. For & the RFM (2.1) satisfying Assumption 3.1, let â E B be the minimizer

---

of the regularized Y -eepiriical risk 2 (x-) given by (2.3). M M 2 A 1lg((220)) and N 2
X 1og(16/))) then
(l)))l((u)) क ((u; ã. {0. 1)13 - 79c (1161 + 9H:,
(3.2)
with probability at least 1 - 5, where
B(p, Gn 11) 328| ll + 2023c || - 8X Eu-
B |l(uu)] - 181 (3.3)
is a function of p. X, Gzs and the law of the noise variable 17.
The main elements of the proof of Thm. 3.4 will be explained in Sect. 4.
Remark 3.5 (Excess risk). We note that other work [26, 37, 38] often focuses bounding the excess risk & ==(((:;))) wn (Gx)). where 6 (F) E lly F(u)l 3 F(u) + E Imll.. In particular, this bias-variance decomposition implies that & < ((u; |) [3. Thus, Thm. 3.4 also gives a corresponding bound on the excess risk 8.
Euve [|g(u)
[[[(u) E
Remark 3.6 (The 3 factor). In the well-specified setting, that is, 9 - - = = 0, the factor /3 in Thm. (3.4) satisfies the uniform bound
Bep X, 94. 17) S B = 328||g1| + 2023c (1
(3.4)
In particular, the constant B does not depend on À in this case. Otherwise, 3 in general depends on A. We can characterize this dependence precisely if it is known that 9 E L (x': )). In this case, Assumption 3.2 is satisfied with == G Gn for any Gz H. Choosing GN Go -=> in SM B (which is optimal in the sense described there) and a short calculation deliver the bound
3(p, X, Gn, n) S - (1-r))+
(3.5)
g additionally satisfies a particular r-th order regularity condition (see Lem. B.3 for the details). Here, a+ == max 0) for any E I. Thus, ,3 is uniformly bounded if G E H (r 2 1) and grows algebraically as a power of - otherwise (0 S r 1).
Consequences. The general error bound (3.2) in Thm. 3.4 has several implications for vector-valued learning with the RFM. First, it immediately implies rate of convergence if g E H. Theorem 3.7 (Well-specified). Instantiate the hypotheses and notation Thm. 3.4. Suppose that p p=0 0 so that G H (2.2). If 2 - (ogg(3/5)) 5) and N Z X 2-22-21og 1og(11666 then
Enswy [ (u) (u; a) S 79 (191115- (1911:++BB)) +2B) S
(3.6)
with probability at least 1 - 5, where the constant B 2 0 is defined by (3.4).
Given a number of samples N, Thm. 3.7 shows that RE-RR with regularization À = 1/vN and number of features M Z /N leads to a population squared error of size 1/vN with high probability, This result should be compared to the previous state-of-the-arr convergence rates in the literature for RF-RR with iid sampled features [2, 26, 37, 38]. See Table 1, which indicates that our analysis gives the lowest parameter complexity to date. We emphasize that such a convergence rate rests on the assumption that G E H.. This corresponds to compatibility condition between G and the pair (yp, p)) i.e., the random feature map ş and the probability measure μu, which determine the RKHS H. Designing suitable &p and /a for a given operator G remains an open problem. For an explanation of the poor parameter complexity in Rahimi and Recht's 's original paper [37], see [44, Appendix E].
Thm. 3.4 also implies convergence of A (ā:; 9) when G & H. as we will see in Sect. 3.3 and 3.4. But first, the next corollary shows that the same general bound (3.2) also holds for the Gx-population squared error 28 (ā; Gz), up to enlarged constant factors. The proof is given in SM C.
Corollary 3.8 (Ox-population squared error bound). Instantiate the hypotheses and notation of Thm. 3.4. M 2 X- Xo log(32/8) and N 2 X- log(16/5), then there exists an absolute constant C> 1 such that with probability at least 8, it holds that
E Eusyy (Q(()) - (uu 13 < C(1912 + 23((p x, n)).
(3.7)
Although our main goal is to learn G from noisy data, there are settings instead in which the learning of IN E H as in Cor. 3.8 is of primary interest, but only values of some approximation g E I (X: )) available. The following example illustrates this.
5

---

Example 3.9 (Numerical discretization error). One practically relevant setting to which Cor. 3.8 applies arises when training RFM from functional data generated by a numerical approximation g= I4 of some underlying operator GN E H. Here A > 0 represents a numerical parameter, such as the grid resolution when approximating the solution operator of partial differential equation. In this setting, p = و 9z is non-zero and it is crucial to include the discretization error in the analysis, which we define as Eδ = l = 1وو- - GH l12.p Assume 1j = O, so that á minimizes
(Y) ( Using Cor. 3.8, it follows that for M and N sufficiently large,
Pa (w: 1) & A11 1 +Ea
(3.8)
with high probability. Thus, as suggested by intuition, in addition to the error contribution that is present when training on perfect data (the first term on the right-hand side), there is an additional discretization error of size E.. We also see that the performance of RE-RR is stable with respect to such discretization errors stemming from the training data. Actually obtaining a rate of convergence would require wroblem-specifer information about the particular numerical solver that used.
3.3 Statistical consistency
We now return to the objective of recovering 9 from data. In particular, suppose that G & H; the RKHS, viewed as a hypothesis class, is misspecified. Our analysis demonstrates that statistical guarantees for RF-RR are still possible in this setting.
To this end, assume that G E T (X;3' It follows that Assumption 3.2 is satisfied with p= 9 GH and 9H E H being any element of the RKHS. Applying Thm. 3.4 and minimizing over GH yields
Eusy [I](()) - (uu: 3 S X
inf (Bunol1((u) (n(3))3 + > }
(3.9)
ONER
with probability at least 1 - 8 if M Z (og(2/0) and N 2 x (og((/6) To obtain (3.9), we enlarged constants and used the bound ||ellt,- S 19 + 11 (3.3).
If G is in the Ll-closure of H. then with high probability, the population squared error on the left hand side of (3.9) converges zero as A- 0 (by application of Lem. B.2 the second term on the right). This is statement about the (weak) statistical consistency of the trained RF-RR estimator; it can be upgraded to an almost sure statement, as expressed precisely the next main result.
Theorem 3.10 (Strong consistency). Suppose that G E LE (X:Y) belongs the (7 -lcoouure of H (2.2). Let JAE C (0, 1) be a sequence of positive regularization parameters such that ΣKEN dE < co. For tb the RFM (2.1) satisfying Assumption 3.1 and for each ki let (x)) E R&Me be the trained RFM coefficients that minimize the regularized Yeepiriical risk R (.;Y) given by (2.3) with Mj = Ng log(2/>a) )x)) iid random features and N₂ = Xxe 1og(2/ Ax)) iid data pairs under Assumption 3.3. It holds true that
lim Ensw [[((u) - (w ) = with probability one. k-+00
(3.10)
The proof relies on standard Borel-Cantelli argument. See SM C for the details.
Remark 3.11 (Universal RKHS). The assumption that G belongs to the Lo-closure of the RKHS H is automatically satisfied if 76 is dense in (2(:)) This is equivalent its kernel being universal [7, 9]. In this case, the trained RFM is strongly consistent estimator of any g E L However, we are unaware of any practical characterizations of universality of the kernel in terms of its corresponding random feature pair (e,, (1) for the vector-valued setting studied here.
3.4 Convergence rates
The previous subsection establishes convergence guarantees without any rates, We now establish quantitative bounds. Throughout what follows, we denote by KC: (2; )) - L3 (X:; y) the integral operator (B.5) corresponding to the operator-valuee kernel function of the RKHS H (see SM B).
Theorem 3.12 (Slow rates under misspecification). Suppose that G E L (x; and that As- sumption 3.3 holds. Additionally, assume that G E [m(()r/2) for some r >> O, where K. is the integral operator corresponding to the kernel of RKHS H (2.2). Fix E (0, and X E (0, 1). For

---

& the RFM (2.1) satisfying Assumptiin 3.1, let â E RM minimize (x:)) given by (2.3). If
M 2 > (8g(328)) and N 2x >>> (16(/8)/)) then with probability at least 1 it holds that
Eu- [ - (u a) - am
(3.11)
The implied constant in (3.11) depends only on ||9|| and [
Thm. 3.12 provides a quantitative convergence rate À
For 2 L, i... when H. we recover the linear convergence rate of order from Thm. 3.7. The assumption that 9 E Im(K)//) can be viewed as a "fractional regularity" assumption on the underlying operator; indeed, in specific fractional (Sobolev) regularity of the underlying function. In general, appears difficult to check this condition in practice, which is one limitation of our result.
settings it corresponds
A quantitative analog to the almost sure statement of Thm. 3.10 also holds.
Corollary 3.13 (Strong convergence rate). Instantiate the hypotheses and notation of Thm. 3. 10. Assume in addition that G E Im(Kr/²2) for some > O. Let {Ae]KEN C. (0,1) be a sequence of positive regularization parameters such that EKEN Av < co. For each k, let @(R) E MR be the trained RFM coefficients with Mj
X log(2/ Xxe) and No Xx > 12/(2//a)) It holds true that
Evww ( (u; ā a
lim sup
with probability one.
(3.12)
N
Short proofs of both Thm. 3.12 and Cor. 3.13 may be found in SM C.
4 Proof outline for the main theorem
Our main results are all derived from Thm. 3.4, whose proof, schematically illustrated in Figure 1, we now outline. Following [37], we break the proof into several steps that arise from the error decomposition
La 9 = = 22 (
(xx()) (ā:
(4.1)
Sect. 4.1 estimates the first term on the right hand side of (4.1) while Sect. 4.2 estimates the second.
Theorem 3.4 (ū: G)
((; <
(0, 9)
0 (a; 9) (ū;
Proposition 4.1: 38 s.t. w.h.p., \| S (a: g) < BX
Proposition 4.7: given 3 from 4.1, bounds
(ā; 9) LN: 9)
Lemma D.6 Lemma D.7: for any I, bounds SuPaEA, ((x; - NN 9)
Lemma 4.3 2 N (a*: (Nx
Lemma 4.5 En II Il
Lemma 4.6
Lemma D.4+ Lemma D.5
D==1 (-mn, (2un )
.
E (M., (u,,; aM)
supacA:
Figure 1: Flow chart illustrating the proof of Theorem 3.4.
4.1 Bounding the regularized empirical risk
The main technical contribution of this work is a tight bound on the G-empirical risk &y 9) for the trained RFM. The analysis involves controlling several sources of error and careful truncation arguments to avoid unnecessarily strong assumptions on the problem. The result is the following.
Proposition 4.1 (Regularized G-empirical risk bound). Let Assumptions 3.1 and 3.3 hold. Suppose that G p + Gy satisfies Assumption 3.2. Fix d (0. 1), X (0. M N. and N E N.
7

---

Let ā E RM be the minimizer of the regularized Y -empirical risk B' (:Y) given by (2.3). If
M 2 X 16g(1688)) and N 2 X log(8/ 6), then B 9) S 13(p, X, GH: n)
(4.2)
with probability at least 1 6, where the multiplicative factor B(p, X, Gu. 7) is given by (3.3).
Since X|[@[|3 S (ā: 9). the next corollary controlling the norm (2.3) of ā is immediate. It plays a crucial role in developing an upper bound for the second term on the right side of (4.1).
Corollary 4.2 (Trained RFM norm bound). Instantiate the hypotheses and notation of Prop. 4.1. Fix
5 E (0, 1) and À (0, M 2 x- log(16/8) and N 2 x 2 1og(8/8). then
á E As = {a E R. |||1133 5
(4.3)
with probability at least 1 - 5. The radius 3 = ((p, X, Gu. of the norm bound is given by (3.3).
The core elements of the proof of Prop. 4.1 are provided in the next few subsections, with the full argument in SM D.I. The main idea is to upper bound the G-empirical risk by its regularized counterpart and then decompose the latter into several (coupled) error contributions.
To do this, first fix any a E R. It holds that
(a; 2 (0;9) +
2 N
Σ Im: G(un) ((nn; a))y
1 N
Σ
(4.4)
because Y is a Hilbert space and yn = G (un) + Tn- Using this, short calculation shows that
N
= (a: - (a;
+ (a;g)
Um, P(un; @) - D(u,; au)n
N
n=1
N
N
S (a; +
n-m E5 Un; a)ly
+
(m, ")yy
(4.5)
N ==
N
===1
M is arbitrary. we have the freedom to choose a so that the first term is small (see Sect. 4.1.1 and 4. 4.1.2). With fixed, the second term averages to zero by our assumptions on the noise, and hence, we expect it to be small with high probability (see Sect. 4.1.3).
In the second line, we used the fact that â minimizes 2 (.)). Since a E RRM
The third term in (4.5) exhibits high correlation between the noise The and the trained RFM coefficients a, making more difficult estimate. To control this last term, we first note that it is homogeneous in ||ã|| M. which can be used to derive an upper bound in terms of a supremum over the unit ball with respect to || As- The resulting expression then bounded with empirical process techniques (see SM D.1.3). For the complete details of the required argument we refer the reader to SM D.I.
In the remainder of this subsection, we estimate the first two terms the right hand side of (4.5).
Using the fact that G = p + Gh, the first term can be split into two contributions,
2 Σ (l((,)))3
N (a: 9) S 2 (a; IR) +
(4.6)
These contributions to the first term in (4.5) are bounded in Sect. 4.1.1 and 4.1.2. The second term in (4.5) controlled in Sect. 4.1.3.
4.1.1 Bounding the approximation error
We begin with the term By GH), which may be viewed as an empirical approximation error due a being arbitrary. Its only dependence on the data through {u,} in (2.3). Intuitively, this term should behave like its population counterpart. It is then natural to choose a Monte Carlo approximation a'm ax (8 for a, where ar L (O; R) is identified with Gx as in (2.2). However, our intuition that A ||a|],, should concentrate around X||aœ 1 fails because it is generally
not possible to control the tail of the random variable (0) /2. We next show that this problem can be overcome by carefully tuned truncation argument combined with Bernstein's 's inequality.
8

---

Lemma 4.3 (Construction of approximator, Suppose that Gn. == G E H. Fix E (0, X> 0, N N. and M N. Let {0.. u and {un} V&N Define a* E RM componentwise by
am = orz (fm) ((ax(0m) STY, where T X- Eo-p (0)2
(4.7)
and 9x = Ba-w w (;:0p)p(:))))))) ;]] with 119 Egru oo (0)). 1f 2 X- log(4/6), then with probability at least 8 in the random feature parameters ....... 0M. holds that
U (ax Gx) S 1812||9711
(4.8)
SM D.1.1 provides the proof.
Remark 4.4 (Well-specified and goise-frree). Lem. 4.3 gives a (()) bound on the regularized 9x- empirical risk of RFM trained on well-specified and noise-free iid data {un, GH (un)).
4.1.2 Bounding the misspecification error
The second contribution to (4.6) is easily bounded by Bernstein's inequality because p L. We refer the reader to SM D.1.2 for the detailed proof.
Lemma 4.5 (Concentration of misspecification error). Let be as in Assumption 3.2. Fix 5 E (0, 1).
With probability at least 1 8, it holds that
2 N
Ielu))13 S 4 1 9leeli log(2/0)
Σ N
(4.9)
N
4.1.3 Bounding the noise error
The second term on the right hand side of (4.5) a zero mean error contribution due to the noise corrupting the output training data. By the fact that is subexponential (Assumption 3.3), Bernstein's 's inequality delivers exponential concentration. The proof details are in SM D.1.3.
Lemma 4.6 (Concentration of noise error cross term). Let Assumptions 3.1 and 3.3 hold. Fix E RM {0m} ~ W and E (0, 1). With probability at least 1 - 8, it holds that
2
N
nn D(un; a)ly & 16e Im / 1mllo, log(2/8) N
(4.10)
N
SM D.1.3 also details the techniques used upper bound the third and final term in (4.5).
4.2 Bounding the generalization gap
Having bounded the empirical risk with approximation arguments, remains to control the estimation error H (ā; 9) R (ā: G) due to finite data in (4.1). We call this the generalization gap: the difference between the population test eтror and its empirical version. If â satisfies || S t for some > 0, then one can upper bound the generalization gap by its supremum challenge is to show existence of a (sufficiently small) / that satisfies this inequality. This is handled by Cor. 4.2. As summarized in the following proposition, the resulting supremum of the empirical process defined by the generalization gap shown to be of size 112 with high probability.
this set. The main
Proposition 4.7 (Uniform bound on the generalization gap). Let Assumption 3.1 hold. Suppose G
satisfies Assumption 3.2. Let (9m) μ &M for the RFM & given by (2.1). Fix 8 E (0, 1). For iid input samples }un} ~ 1 define the random variable
S,((un), == sup aEAp
Σ [[ (bnn; 13 En, (n.l)(u) - & (w;aa)) (4.11) #=1
N
where Ag = (a' E RM ||a' < B) and the deterministic radius 3 [ x, Gn. n) is given in
(3.3) with 9 as above. If 2 (og(1/5),
then with probability at least
8 holds that
6 (og(2//)
Es((un), (0m)) < 3/2 (191 + 3(p, X, GH (1))
(4.12)
N

---

The proof of Prop. 4.7 is given in SM D.2. The argument is composed of two steps. The first is to show that Eş] [0m) concentrates around its (conditional) expectation (Lem. D.6). This follows easily using the boundedness of the summands. The second step is to upper bound the expectation of Eg { (Lem. D.7). This is achieved by exploiting the Hilbert space structure of the )'square loss and the linearity of the RFM with respect to its coefficients.
4.3 Combining the bounds
Since we now have control over the G-empirical risk and the generalization gap, the G-population risk is also under control by (4.1). The proof of Thm. 3,4 follows by putting together the pieces (SM C).
5 Numerical experiment
To study how our theory holds up in practice, we numerically implement the vector-valued RE-RR algorithm benchmark operator learning dataset. The data { (u,, ((,,) [( is noise-free, the {u,} are iid Gaussian random fields, and g: (T) + (T; IR) is a nonlinear operator defined the time one flow map of the viscous Burgers' equation on the torus T. SM provides more details about the problem setting and the choice of random feature pair (4)
P 256
25
Relative Bockaet equandd urror
0006
4006
34-1
10
10
10
10
10P
11
M
N
(a) Varying p, M, À for fixed N 1548.
(b) Varying p. N, A for fixed M 10
Figure 2: Squared test error of trained RFM for learning the Burgers' equation solution operator. All shaded bands denote two empirical standard deviations from the empirical mean of the error computed over 10 different models, each with iid sampling of the features and training data indices.
Figure 2a shows the decay of the relative squared test error as M increases (with À 1/M) for fixed N. The error closely follows the rate O(M-) until it begins to saturate at larger M. This is due to either not belonging to the RKHS of (pp, μ)) or the finite data error dominating. As implied by our theory, the eтror does not depend on the discretized output dimension < so. Figure 2b displays similar behavior as N is varied (now with À = 1/VN NN and fixed M). Overall, the observed parameter and sample complexity reasonably validate our theoretical insights.
6 Conclusion
This paper establishes several fundamental results for learning with infiniteddimensional vector- valued random features; these include strong consistency and explicit convergence rates. When the underlying mapping belongs to the RKHS, the rates obtained in this work match minimax optimal rates in the number of samples N, requiring only a number of random features M ~ /N. Despite being derived in a very general setting, to the best of our knowledge, this provides the sharpest parameter complexity in M, which free from logarithmic factors for the first time.
There are several interesting directions for future work. These include deriving fast rates, relaxing the boundedness assumption on the features and the true mapping, and accommodating heavier-tailed or white noise distributions. Obtaining fast rates would require a sharpening of several estimates, and in particular, replacing the global Rademacher complexity-yype estimate, implicit our work, by its local counterpart. As our approach does not make use of an explicit solution formula, which is only available for a square loss, this might pave the way for improved rates for other loss functions, such general -llsoss. We leave such potential extensions of the present approach for future work.
10

---

Acknowledgments and Disclosure of Funding
The work of SL is supported by Dostdoc.Mobillty grant P500PT-206737 from the Swiss National Science Foundation. NHN acknowledges support from the National Science Foundation Graduate Research Fellowship Program under award number DGE-1745301 and from the Amazon/Caltech A14Science Fellowship. and partial support from the Air Force Office of Scientific Research under MURI award number FA9550-200 10:00-20---3355 (Machine Learning and Physics- Based Modeling and Simulation). SL and NHN are also grateful for partial support from the Department of Defense Vannevar Bush Faculty Fellowship held by Andrew M. Stuart under Office of Naval Research award number N00014-22-1-2790.
References
[I] N. Aronszajn. Theory of reproducing kernels. Trunsactions of the American mathematical society, 68(3):337-404, 1950. (Cited page 1)
[2] F. Bach. On the equivalence between kernel quadrature rules and random feature expansions.
The Journal of Machine Leurning Research, 18(1)711-751, 2017. (Cited on pages 2, 3, 4, and 5)
[3] K. Bhattacharya, B. Hosseini, N. B. Kovachki, and A. M. Stuart. Model Reduction And Neural Networks For Parametric PDEs. The SMAI journal of computational mathematics, 7:
121-157, 2021. doi: 10.5802/smai jemm..jjm....... 74. URL https: // semai-jone centre mersenne.
arg/articles// /10. 5800//8802550000 smassmaajjeo cm. 74/. (Cited on page 2)
[4] N. Boullé and A. Townsend. Learning elliptic partial differential equations with randomized linear algebra. Foundations Computational Mathematics, pages 1-31, 2022. (Cited on page 2)
[5] R. Brault, M. Heinonen, and F. Buc. Random fourier features for operator valuee kernels. In Asian Conference on Machine Learning. pages 110-125. PMLR, 2016. (Cited on page 2)
[6] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331 2007. (Cited on pages 1, 4, and 14)
[7] A. Caponnetto, C. A. Micchelli, M. Pontil, and Ying. Universal multi-task kernels. The Journal of Machine Learning Research, 9:1615-1646, 2008. (Cited on page 6)
[8] C. Carmeli, E. De Vito, and A. Toigo. Vector valued reproducing kernel Hilbert spaces of integrable functions and Mercer theorem. Analysis and Applications, 4(04))377-408, 2006. (Cited on pages 16 and 17)
[9] C. Carmeli, E. De Vito, A. Toigo, and Umanitá. Vector valued reproducing kernel hilbert spaces and universality. Analysis and Applications, 8(01):19-61, 2010. (Cited page 6)
[10] Z. Chen, H. Schaeffer, and R. Ward, Concentration of Random Feature Matrices in High- Dimensions. In Mathematical and Scientific Machine Learning, pages 287-302. PMLR, 2022.
(Cited on page 2)
[11] A. Cohen, R. Devore, and C. Schwab. Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's. Analysis and Applications, 9(01):11-47, 2011. (Cited
on page 2)
[12] M. V. de Hoop, N. B. Kovachki, N. H. Nelsen, and M. Stuart. Convergence Rates for Learning Linear Operators from Noisy Data. SIAM/ASA Journal on Uncertainty Quantification, 11(2):400-513, 2023. doi: 10.1137/21M1444242 (Cited on page
[13] B. Deng, Y. Shin, L. Lu, Z. Zhang, and G. E. Kamiadakis. Approximation rates of DeepONets for learning operators arising from advection advection-diffusion equations. Neural Nenworks, 153: 411-426, 2022. (Cited on page
[14] W. E. C. Ma, and L. Wu. The generalization error of the minimum norm solutions for over- parameterized neural networks. Pure and Applied Functional Analysis, 566):1445-1460, 2020. (Cited on page 2)
[15] B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. Ann. Statist. 49:1029-1054, 2021. (Cited on page
[16] C. R. Gin, D. E. Shea, S. L. Brunton, and J. N. Kutz. DeepGreen: deep learning of Green's functions for nonlinear boundary value problems. Scientific reports, 11(1):21614, 2021. (Cited page
11

---

[17] L. Gonon, L. Grigoryeva, and J.-P. Ortega. Approximation bounds for random neural networks and reservoir systems. The Annals of Applied Probability, 33(1):28 69, 2023. (Cited on page 2)
[18] A. Hashemi, H. Schaeffer, R. Shi, U. Topcu, G. Tran, and R. Ward. Generalization bounds for sparse random feature expansions. Applied and Computational Harmonic Analysis, 62:
310-330, 2023. (Cited on page 2)
[19] I.. Herrmann, C. Schwab, and J. Zech. Neural and gpe operator surrogates: construction and expression rate bounds, 2022. (Cited on page 2)
[20] J. Hesthaven and S. Ubbiali. Non-intrusive reduced order modeling of nonlinear problems using neural networks. Journal of Computationall Physics, 363:55-78, 2018. ISSN 0021-9991. doi: https::/ddo..or//10.. o1p.
URL https: //www//wwww.wwo/ www.://ceeneeirect.... com/ (Cited on page 2)
[21] J. Jin, Y. Lu, J. Blanchet, and L. Ying. Minimax Optimal Kernel Operator Learning via Multilevel Training. arXiv preprint arXiv:2209. 140.22400,443, 2022. (Cited on page 2)
[22] N. Kovachki, S. Lanthaler, and S. Mishra. On Universal Approximation and Error Bounds for Fourier Neural Operators. Journal of Machine Learning Research, 22(290):1-76, 2021. URL
http://jmlr.. www.oogggg........ wwwprs//2//222/2/ 0806 html. (Cited on page
[23] N. B. Kovachki, Z. Li, B. Liu, K. Azizzadenesheli, K. Bhattacharya, A. M. Stuart, and A. Anand- kumar. Neural Operator: Learning Maps Between Function Spaces With Applications to PDEs.
J. Mach. Learn. Res., 24(89): 1-97, 2023. (Cited on page 27)
[24] S. LLnthallr, S. Mishra, and G. E. Karniadakis. Error estimates for DeepONets: deep learning framework in infinite dimensions. Transactions of Mathematics and Its Applications, 6(1), 03 2022. ISSN 2398-4945. doi: 1.11099//matmm//ac0001. URL https: //oiii 2tgg/10.1993 imatrm/ tn00001.. tnac001. (Cited on page 2)
[25] Li, N. B. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandku- mar. Fourier Neural Operator for Parametric Partial Differential Equations. In International Conference on Learning Representations, 2021. URL https: //tp:///oppeeeeeeeeeeeeeeeeeeeee /ttpp/rreeieeeee//fforrr id=c8P9NVVtmnO. (Cited on page 2)
[26] Z. Li, J.-F. Ton, D. Oglic, and D. Sejdinovic. Towards a unified analysis of random Fourier features. Journal of Machine Learning Research, 22(108), 2021. (Cited on pages 2, 3, 4, and 5)
[27] L. Lu, P. Jin, G. Pang, Z. Zhang, and G. E. Karniadakis. Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators. Nature Machine Intelligence, 3(3):218-22)) 2298822292222 2021. (Cited on page 2)
[28] A. Maurer and M. Pontil. Concentration inequalities under mub-Gaussian and sub- sub-exponential conditions. Advances in Neural Information Processing Systems, 34:7588-7597, 2021. (Cited on pages 14 and 16)
[29] S. Mci, T. Misiakiewiez, and A. Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022. (Cited on page 2)
[30] H. Q. Minh. Operator-valued Bochner theorem, Fourier feature maps for operator- operator-valued kernels, and vector-valued learning. arXiv preprint arXiv: 05639, 2016. (Cited on page 2)
[31] M. Mollenhauer, N. Mücke, and T. Sullivan. Learning linear operators:
regression as well-behaved non-compact inverse problem. arXiv preprint arXiv:2211.08877 2022. (Cited on pages and 15)
[32] N. H. Nelsen and A. M. Stuart. The random feature model for onput- maps between Banach spaces. SIAM Journal on Scientific Computing, 43(5): 2021. (Cited on pages 2, 3, 16, and 27)
[33] H. Ogawa, An operator pseudo-inversion lemma. SIAM Journal on Applied Mathematics, 48 (6):1527-133, 1988. (Cited on page 17)
[34] H. Owhadi and C. Scovel. Separability of reproducing kernel spaces. Proceedings of the American Mahematical Society, 145(5):111--2138, 2017. (Cited on page 16)
[35] I. Pinelis and A. I. Sakhanenko. Remarks on inequalities for large deviation probabilities. Theory of Probability & Its Applications, 30(1):143-145 1986. (Cited pages 14 and 15)
12

---

[36] A. Rahimi and B. Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007. (Cited on page 1)
[37] A. Rahimi and B. Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in neural information processing systems, 21, 2008. (Cited on pages 3, 4, 5, and 7)
[38] A. Rudi and L. Rosasco. Generalization properties of learning with random features. Advances
in neural information processing systems, 30, 2017. (Cited on pages 2, 3, 4, 5, and 14)
[39] Ryck and Mishra. Generic bounds on the approximation error for physics-informed (and) operator learning. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances Neural Information Processing Systems, 2022. URL htttps:/opeerevieeeee htt////errriee..nne/forrr net/forum?
id=bF4eYy3LTR9. (Cited on page 2)
[40] B. Scholkopf and A. J. Smola. Learning with kemells: support vector machines, regularization, optimization, and beyond. MIT press, 2018. (Cited on page 1)
[41] C. Schwab and J. Zech. Deep learning in high dimension: Neural network expression rates for generalized polynomial chaos expansions in UQ. Analysis and Applications, 17(01):19-55, 2019. (Cited page 2)
[42] S. Smale and D.-X. Zhou. Shannon sampling II: Connections to learning theory. Applied and Computational Harmonic Analysis, 1963)2255-32,, 2005. (Cited on pages 16 and 17)
[43] G. Stepaniants. Learning partial differential equations in reproducing kernel Hilbert spaces. Journal of Machine Learning Research, 24(86): 2023. (Cited on page 2)
[44] Y. Sun, A. Gilbert, and A. Tewari. But how does it work in theory? Linear SVM with random features. Advances in Neural Information Processing Systems, 31, 2018. (Cited page 5)
[45] R. Vershynin. High-dimensional probability: An introduction with applications in data science,
2018. (Cited on page 15)
[46] M. Wainwright. High-dimenssonal statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019. (Cited on page 25)
13

---

Supplementary Material for:
Error Bounds for Learning with Vector- Value Random Features
A Concentration of measure
In this section, we recall two classical results from [35] that estimate the difference between empirical averages and true averages of random vectors taking values in Banach spaces. These are then specialized to the setting of subexponential random variables, which play major role this paper. To set the notation, we use Pr to denote probability with respect to the underlying probability space.
The first result is vector- vector-valued Bernstein concentration inequality with various applications to problems posed in dimens-aa Hilbert spaces [6, 28, 38]. It is used throughout this work.
Theorem A.1 Vector-valued Bernstein inequality in Hilbert space). Let Z be H-valued random variable, where (H, 1, II) is separable Hilbert space. Suppose there exist positive numbers b > 0 and 0 such that
Z EZI S $pplo'00 for all 22
(A.1)
For any 8 (0,1) 1) and N E N, denoting by 1Zn sequence of N iid copies of Z, it holds that
2b (2//6)
V
22o² (og(2/6)
Pr
Σ 1=1
Zn E2
2 1 8.
(A.2)
N
N
N
Proof. The result is direct consequence [35, Cor. 1, p. 144] in the iid Hilbert space setting. In this case, it holds for any / > 0 that
N 2No 2N exp
Nt
Pr(1ISN- ESv 2 t] S 2xxp
20 + 2bt
where S, N Σ Zn Setting the right hand side equal to solving a quadratic equation for t = t()), and using the inequality va Wb+b< 2 Vā vb to bound t(6) from above leads to (A.2).
O
The most common use case of Bernstein's 's inequality is in the following bounded setting.
Lemma A.2. Let Z be (potentially) uncentered random variable such that
||||| S c almost surely and E E 2 < o²
(A.3)
for some 0 and v > O. Then Z satisfies Bernstein's 's moment condition (A.1) with b = 2c and σ = U. EZ = 0, then taking = e suffices.
Proof. It holds that || - E | < |1| + Z|| < 2c almost surely. We compute
B Z E "
[||| Z 1| Z 1 Z (26)
1
s (2c)
2 plu (2c)
because $ pl/2 for all 2 The centered improvement is trivial.
The second classic result we present is one-sided Bernstein-tye -tppe tail bound in general Banach space. We invoke this theorem to control the tails of suprema of empirical processes.
Theorem A.3 (Vector-valuee Bernstein inequality in Banach space). Let Z be Z-valued random variable, where (Z, []] is a separable Banach space. Suppose there exist positive numbers b > and a 0 such that
1
E Z EZI < plo020-2 for all 2.
(A.4)
2
For any 8 E (0, 1) and N E N, denoting by JNN sequence of N iid copies of Z, it holds that
N Pr
28 lolo((1/5)
20 log (1/8)
Σ 20
E
Σ 2n
+
1 8. (A.5)
N
==1
14

---

Proof. The assertion is [35, Cor. 1, 144] in the iid Banach space setting (hence only convergence of norms in (A.5) instead of strong convergence). It is proved the same way as Thm. A.I.
Theorem A.3, a random variable satisfying the Bernstein moment condition (A.4) is subexponen- tial in the sense that || - E Z|| is subexponential on I. i.e., exhibits exponential tail decay. Recall that for real-valued random variable Z, its subexponential norm may be defined by
[ (
7 1v == sup pL
(A.6)
See [45, Sect. 2.7] for equivalent definitions. We say that is subexponential if its subexponential norm is finite. Following [31, Sect. 4.3, pp. 19-20), for random variable Z with values in Banach space (2, 11|2) we define
2B1
1 (2)
|11
sup (1())
(A.7)
P
as its subexponential norm. It is known that random variable has finite subexponential norm if and only if satisfies the Bernstein moment condition (A.4) [see, e.g., 31, Appendix A.2]. Next, we give explicit constants in the Bernstein moment condition that depend on the subexponential norm.
Proposition A.4 (Subexponential implies Bernstein moment condition). Let Z be (2,11-I1-values subexponential random variable, that is, (Z)) < co. Then Z satisfies
1
E Z
E Z
1 & plop 2 for all p p22.
(A.8)
where
== 4e E
E E (2) and b b= 4e 4c| ((l)()))
(A.9)
Proof.
By the Cauchy-Schward inequality.
R Z E 2 = ||| | 2 - EZ| < 2 E 2 (R - IE
The incquality la + 6/d < 2 [|a]0 + 6/9), Jensen's 's inequality, and / (2) < 0 show that
" Next, Stirling's s approximation (q/e)² S g! and q! = 4/g - 1)1 2(4 1) for 2 2 yields
E Z - E z 2p 2 - 2p
2) 2p- 2|
3p-2 (2)
E - 1 2h 2 E 1 (p- - | (
|
(p!/2) 2 E 1
(2))
Rearranging the exponents to the Bernstein moment condition form completes the proof.
This leads to the following corollary, which is useful in the setting that the variance El|Z E 2
| E Z 2 (z(2;22 of random variable Z is not small or hard to compute.
LN Corollary A.5 (Subexponential tail bound Banach space). Fix E Let (Zn) be iid random variables with values in separable Banach space (z, - Suppose that (Z < oo.
Let SN = EN Zn Fix 8 E (0, 1). With probability at least 1 - 6, it holds that
8el Se log(1/8)
8el| E 1200 (1,,2)) log(1/8)
|| [ SE|[Sw] <
N
(A.10)
In particular, N 2 log(1/8), then with probability at least 8 it holds that
64c3 2z 112 (2) log(1/6)
|Sw| E Sw|l <
(A.11)
N
15

---

Proof. Apply Prop. A.4 to Thm. A.3 to obtain the first assertion. For the second assertion, first note
that 2 E 1 < 4 Z1 11? (by triangle inequality and using (a + b)² S 2(a² + b) and
|| (2)) 2 2 (by (A.7)). Since N 2 log(1/o), we have log(1/6)/N & (1/6)//
Combining these facts, it follows that the right hand side (A.10) is bounded above by
64c 21 12 (2) log(1/6)
32e 21 (2) (//(1/5)
64(2c2 + + (z) log(1/6)
N
N
N
We used Va + vb S v b) on the right. Noting that 2e + e S e completes the proof.
Comparing this result to similar result [28, Prop. 7(1), pp. 4-5, the iid case], we note that (A. in Cor. A.5 is sharper in the sense that the constant in the N- term depends on the variance of the summands instead of just its subexponential norm (which can be much larger than the variance).
B Misspecification error with RKHS methods
Let K: x X' + L()) be an operator-valued kernel [32] corresponding to separable RKHS H of functions mapping to y. Here, L()) denotes the set of bounded linear operators from y into itself. In this section, we present general analysis based on [42] for the approximation of elements in (x;; by elements the RKHS H. This problem is relevant to our learning theory framework whenever the true data-ge tata-generatiig map does not belong to the RKHS (2.2) associated to the given random feature pair (e, p)). Specializing to this setting, suppose that (f; μ)) satisfy Assumption 3. 1.1. Let K: (u, 2²) + Eo (u; 8) Gy p(u'; 0)] be the corresponding limit random feature kernel. It holds that (u, u) is trace-class for each u E X' v-almost surely because
(u,Kuu, u)) = Eg tr(p(u; O) By plu; 8)) Eg [ly((;; 0)1] S 11pl2 <
(B.1)
by the Fubini-Tonelli theorem. It follows from [8, Prop. 4.8, p. 394] that H is compactly embedded into L (x;: because
Eu K w)lloa> I Euvu tr(K u)) S 11 <0. We denote the canonical embedding by :: H + (x;;),, Now let & E (x(x)) be an arbitrary operator. We consider an approximation Go to G defined by
(B.2)
Go == arg min ||g - 12: + )1[F PEH
(B.3)
This operator has simple representation.
Lemma B.1. There exists a unique solution Go to (B.3) given by
Go (L" 0 (d) ('..
(B.4)
Proof. The result is consequence of convex optimization on Hilbert spaces and the fact that is bounded linear operator.
The adjoint of the inclusion map, :²: () - H. given by the vector-valued reproducing kernel property as the (Bochner) integral operator
(B.5) Since is compact, so is K. == u² E ((13(x;))). The action of K. is the same as that of the integral operator above. Since convergent expansion K. = E, Agez (2(())) ej. The sequence {Xj} C R2 is a non-increasing rearrangement of the eigenvalues of IC and {e₂} is its corresponding eigenbasis.
F - 1. Rase (K- F())]
also symmetric, the spectral theorem yields the operator norm
Now define the regularized RKHS approximation error
dg(0)= inf {1I9 Flll; F1 FEH
(B.6)
which is parametrized by g E D7) We have the following convergence result for this error.
The assumption separability of the RKHS could be removed if additional conditions are placed on its kernel that would imply separability, the most relevant being continuity- -typetyy--yyyyyyyye assumptions. In the case y = R. it is known that existence of Borel measurable feature map for the kernel suffices for separability of its unaware of similar results for general y. RKHS [34], which is much weaker than continuity. However,
16

---

Lemma B.2 (Convergence of regularized RKHS approximation error). Suppose that G is in the Ly clyccouuree H.
H. Under the prevailing assumptions of this section,
lim dg(() 0. 0-0
(B.7)
Proof. By Lem. B.1 and the Woodbury identity [33, Thm. 11, holds that
19, = u( [dx)) gg KC(A + i Idrz) (K. + 1 +Iddg))
The second equality holds by simultaneous diagonalization. Writing g in the eigenbasis of IC yields
Σ - 9e
g = Id72 - -KK + (e111)))
JEN Aラ
Similarly, using the norm isometry between T. and the RKHS [see, e.g. 8, pp. 403-404) we obtain
Vxy
g 2 = ||- 1/ = ||C1/2(KC 0 (d =
(e,,
A3 +
JEN
Since the infimum in (B.6) is attained at Go (B.3), we deduce that dg = ||
G 122 + 8 g0
02
002 jey, G) + Σ JEN (h, + 012
(ej 92
JEN
XU + (cj, 979.
jEN
Using 0/(1, + 0) < for each j E N and G E ts
(the L -loouue of H), it follows that
0
ds(0)=
Σ
0 -
(B.8)
1570)
by dominated convergence.
The rate of convergence of ag to zero can be quantified under an additional regularity assumption. Lemma B.3 (Convergence rate under Hölder source condition). Suppose 9 E Im(X)/)) for some 2 O. Then for any & > 0, it holds under the prevailing assumptions of this section that
0r, @0
if E 10, if 1.
(c < ||C 1/2 -1
(B.9)
Proof. The proof closely follows the argument of Smale and Zhou [42, Thm. 4, p. 295). By hypothesis, there exists Fg E (² such that G = /2 Then
ag(()) Σ
025
+ (e Fg)
sup JEN X + 1) ]1Foll22
0X5
JEN
For any j N, the argument of the supremum equals 027 Ay +
1 ())
>3
(Ay or x + ) (1, 0 )
(y)
Ag 2
This is bounded above by H" for all j EN 2 and - 1. Otherwise, and
ON;
2 ス 2 < 015
X, + 0 = 0X3
=
Taking the supremum over j E N completes the proof.
In Lem. B.3, G satisfies G E if r 2 1, and the rate of convergence of (b(( at least as fast as ( 0 + 0. When E [0, 1). then G & H and the rate becomes slower than linear in 1.
17

---

C Proofs for section 3
In this section, we prove Thm. 3.4 and its main consequences.
Proof of Theorem 3.4. Under the hypotheses, (4.2) in Prop. 4.1 holds with probability at least 1 - provided that M 2 A- (og(16/)) and N 2 X- log(8/6). That is, Ry g) S L [ā: I 3A, where B 3(p A, Gx. is given by (3.3). In particular, ā E Ag (4.3) on the same event (by Cor. 4.2). follows that, on this event,
* 9) 2x (x: & sup [x(a; (a;
aEAp
Application of Prop. 4.7 shows that the right hand side of the above display is bounded above by
32v6c 3/2 (19)) + 11 B(p, 9n n)) - 79c (119)i;; 11elii-330 X, Iz. 7))
with probability at least because N 2 X (8/0) 2 log(2/6). Recalling (4.1), using 1 < 79e3/2, and applying a union bound completes the proof.
Proof of Corollary 3.8. Since G = + GH. we compute
(a) = || - 4 Φ(-:a))1z; 1.
= -11-ptig-@0--0)11: (
s 22 + +2 o0 :
=2Bw~ollo(u)li 28
By (3.2) and (3.3), that the term p() | also appears in the upper bound for ((;; 9). Collecting like terms and enlarging constants proves the assertion.
Proof of Theorem 3.10. For & E N and 8 E (0, 1). the trained RFM satisfies ||| -0- a(;;((())) lel s Osk for some deterministic constant e >> 0, where the sequence 8n - 0 as n + oo is given by the right hand side of (3.9) with X An for each n N (by Lem. B.2). This inequality holds with probability at least 5 if M A 1og(2/5) and N X 1og(2/8) by Thm. 3.4. Now choose
= dp. Then
Σ KEN
Pr -
> cSk}
Σ A 80.
KEN
The first
lemma establishes that there exists an N-valued random variable ko such that |[ : I сss for all & ku almost surely. This implies the desired result.
Proof of Theorem 3./2. Application of Thm. 3.4 leads the high probability bound (3.9) by the same argument from Sect. 3.3. Using that X $ 1 and Lem. B.3 proves the assertion.
Proof of Corollary 3.13. Apply Thm. 3.12 to get high probability bound. Choose À = ) = 8. Then the proof follows that of Thm. 3.10 except with {sk} replaced by {A (rA1)/23.
D Proofs for section 4
This section provides proofs of the error bounds for the regularized empirical risk (SMD.1) and the generalization gap (SM D.2).
D.1 Proofs for subsection 4.1: Bounding the regularized empirical risk
We now prove Prop. 4.1. Supporting results used the proof appear after the argument in the subsequent subsections (SM D.I.I, D.1.2, and D.1.3).
18

---

Proof of Proposition 4.1. Our starting point is (4.5). We first note by linearity that
N
N
2
Ma. & (un; R) = ||ā||M
Th, Dun
N
N
n=1
N
D (unn a Dio1 ((n )
< ||ālاa
2 sup d'EA
Σ n=1
nn,
N
where A1 = fa' RM
||a'llss I =1}. provided that ||ā|| > 0. Otherwise, the inequality in the above display holds trivially. Next, we define
M
t =
Σ
aml 2m = =Iaali.
(D.1)
M
2
AN,M 2 (a: 9)
Σ ( The punn and
(D.2)
Mn, D(un; )'))))))))>))))))) )
CN,M
2 sup a'EA
(D.3)
N
The inequality in (4.5) and the trithmetic-eean -eatmetti-mmaa--gmmttiiee
inequality imply that
1
At S ():g) I A + VeN.Mt & A + 2² - tN, + At.
(D.4)
2
Subtracting Xt/2 from both sides and multiplying through by 2x yields
1 s 2x-1 A X eN
(D.5)
Substituting (D.5) back into the right-most side of (D.4) gives
(ā; S 2 + X -
CN,
(D.6)
All of the above calculations hold with probability one. To complete our estimate 2 (ā; 9), remains to upper bound the A (D.2) and CN,M (D.3) terms. We begin with the latter. Lemmas D.4 and D.5 (with t = 1) and (A.7) show that
4l 16 3/2
log(1/8) N
VeN,M
VN
(D.7)
< 16e 1/6 ?I (og(2/))
N
with probability least 1 - 8 if log(2/8) log(1/8). We used the inequalities 4 < 1/2 vā+ + vb < 2((a b), and
log (2/6) to get to the last line.
Continuing, we bound A It has several error contributions originating from two terms. The first term (D.2) is B (a; 9), where a RMM, is arbitrary. By Assumption 3.2, = p GH so that
2 N
2 Σ ll 11
N (a: < A||a|3 & + 2 (a;
2. (a: Gx)
(D.8)
By Lem. 4.5, it holds with probability at least 8 that
2 Σ (l())))33 (e(w)) 91ppl2 log(2/8)
(D.9)
N
Next, we bound the first term on the right hand side in (D.8). Since Gu E H. there exists an I (o; IR) such that
GN EB (ex)(0)((::))) and | 1 Eg (ax (0)12.
19

---

With ar as in the above display, choose once and for all a = a" E IR as in (4.7). By Lem. 4.3,
20 N (a"; :ao::999) 9n) & 162X||9H11
(D.10)
with probability at least - 8f A A log(4/6). On the same event,
22/6(2
2 (2g() AM
||a* - Eg (a)(
1+
5 Ja (0) 51|g
AM
by Lem. D.3. This fact and Lem. 4.6 (with a a* as in (4.7)) shows that the second and final term in AN, (D.2) satisfies with probability at least 8 the upper bound
2
N
(2g(2/6)
Σ N
m- Th.
40c |00
(D.11)
Combining the estimates (D.7), (D.8), (D.9), (D.10), and (D.11), recalling (D.6), and invoking the union bound, we deduce that if N 2 X 2 then
S a 9) - CoA + ( + 18|1p|12
with probability at least 46, where
Co 9 2 S0e Imll (2) 1|ell || 1536e |1 11
- (324 + 9) l + 1936c 1 (2)) 11
In the last line, we used Young's 's inequality with 1/8, that is, ab ea²/2 6// (22) with 80e3/2 1e and b || This proves the asserted upper bound.
D.1.1 Proof's for subsection 4.1.1: Bounding the approximation error Given function a E (O; R), we denote its cut-off at level T >> 0 by
0 + agr (0) = a(f)
(D.12)
This subsection devoted to the proof of Lem. 4.3, which based on the following three lemmas.
Lemma D.I. Suppose G H belongs the RKHS H. Let (2 R) be such that g Eola(f))p(::00 ;)]. Let u1..... uN ~ v be iid samples and uN = 1 En 8an be the corresponding empirical measure. Then almast surely,
1| (ES Ja (0) for all T> 0.
||g =
(D.13)
T2
Proof. Fix u E X' and define a>t == aST. The claim follows from
[I (o(agr(())p(() 0]| [[)o(a>((0)((u 0)][ S || (Eo (a>r()))2
and the observation that E, |a>T S E. /T)
The previous lemma controls the error incurred by truncating the coefficient function of elements in the RKHS. The next lemma provides a bound on sample average approximations of these truncations.
Lemma D.2. Let uI.... UN ~ v be iid samples and let VN Ni > 6u., denote the correspond- ing empirical measure. For L (2; let Z = Z() be the L3 ()v random variable defined for 0 u by
Z = ( (
(D.14)
If Zi...., ZM are M iid copies of Z, then it holds with probability at least that
1
327 |1 log l2g2(2/))
411yp1i, 1og(2/0) Es (a()))
7m
EZ
+
(D.15)
M
M2
M
1.3
20

---

Proof. By boundedness of agrrl I T, we have the trivial uniform upper bound T for each m. The variance bounded above as
|| 12mllrgy 1
a² = 1 2 - E E $ 11 Eg la(0))²
By Lem. A.2 and Thm. A, holds with probability least 1 that
M
4T log(2/6)
2 log log(2/6)
7m EZ
M
M
M
M
L2N
Squaring both sides and substitution of the above bound on o² yields the claimed estimate.
The third lemma below develops high probability bound on the empirical approximation of the RKHS norm of truncated elements in the RKHS.
Lemma D.3. Let a E (0; R) and {0m) ~ NaM, With probability at least 6, it holds that
M Σ m==1
logr(( (0m)) E. la(0) 47 log(2/0)
2T Eg (0)) log(2/8)
(D.16)
M
M
Proof. We apply Bernstein's inequality (A.2) to the random variable Z(0) (a)((0)) with and M E N lid copies Zi,... ZM of Z defined by Zm 2(0m) for each m.. We note that Z s T by definition. The variance of Z satisfies the upper bound
a² = Z E 2 2 Eg (arr(())
T Eg (0))
It follows from Lem. A.2 and Thm. A.1 that
M
2 1og(2/6)
2a log(2/6)
Zm I EZ +
+
m
M
M
m=
with probability at least 8. This in turn implics that
M
(asT((mm) E. (a(0) + 4T log(2/6)
27 E aa(0) (2g(2/8)
+
M m==1
M
M
with at least the same probability. This is the claim.
We are now in position to prove Lem. 4.3.
Proof of Lemma 4.3. Write = T(A) and a == az. Next, define agt E (0; R) by
+ agr ()) == (0) ([(())TT) = aa()) if |a())) TT,
0, otherwise.
We define asT == al ([a|> similarly, so that a = aar +a>r holds true. Then for ....... AM, we have at E RM given by a = afm(mm) ) for each m E "L....,,,, We claim that A N (a=;aa:) g) < (74ll<lli, + 7) Eg Ja (0) with high probability, which implies the asserted bound (4.8). To see this, we make the error decomposition
N Σ
M Σ m=
M Σ
1
Na";
((un)
ast (0m):))(((mnn 0m)
+
lasT(0m)
(D.17)
N
M
M m=
1=
2
<
(1() Eg Lolas (f) 0)]11
(I)
Σ
ast (0m):plun 0m) Eolasr (0) (u, 03]
M
M
+
Σ
(agr(em))
(III)
M
21

---

Each of the three terms (IIIIIII) is estimated as follows.
By Lem. D.I, bound
(1) f 21 (Eg [)
21/1s11i Es 2ola(0))
T
Lem. D.2 delivers the bound
64T
101 l2g(2/6)²
8|pp12 log(2/8) Eg la()))
(II) Σ
2
M
64 [641p112 log(2/8)²
811 log (2/))
= AE |a(0))2
+
X2M2
AM
with probability at least -. 8.
Last, Lem. D.3 yields
4XT 1og(2/8)
27 E (a))) log (2/6)
(III) S {
M
M
4log(2/8)
2 22g((2/8)
= A (a())2
1+
AM
AM
with probability at least 1 6. Combining the three estimates, it follows that if
log (2/8)
- 1, XM
then
as (a S (741|p1i,-- + 7) Eg (0))
with probability at least 1 - 26. We used the fact that v2 < 2. This is the claimed upper bound.
D.1.2 Proof for subsection 4.1.2: Bounding the misspecification error
Recall that p Lø under Assumption 3.2. We prove Lem. 4.5.
Proof of Lemma 4.5. Let Zi [|p(u)) ) || which is uncentered. Almost surely, Z1 S Ilelli and
2 2 7 Em (l < |llli Bl-ellp(u)13..
Thus with probability at least
8, Cor. A.2 and Thm. A. provide the bound
Allpliz log(2/6)
2 E., (lllll()) 13 lell 2 log(2/5)
le(())l13 < (ull)(]
N
N
9 ll log(2/8)
22Fulpp()) +
To get the last inequality, we used the arihmetii-meen--cnntiii-n--es inequality Vab & (a +a+ (a/b)/2 obtain
1 1eli log(2/8)
(0E Eullp(w)]1
Multiplying the penultimate chain of incqualities through by two completes the proof.
22

---

D.1.3 Proofs for subsection 4.1.3: Bounding the noise error
This subsection provides proofs for the lemmas used to control the error stemming from iid noise corrupting the output data as in Assumption 3.3. The estimates themselves could improved by using (A.10) instead of (A.11) and by tracking the noise variance El[nll instead of bounding it above by mll (V)y This would be relevant in settings where the noise is small or tends to zero with the sample size. We defer such considerations to future work.
Proof of Lemma 4.6. Define (a) = (~B,, (u a))y for each n. Conditioned on {6. ). it holds that Ze is iid copy of Z1. By the assumption Elm [n] 0, we have
E (a) ((... )( m (uu;
Banre|E((-1)) a)) [u]]
(D.18)
Buj B[m wil, p(u a))xl
0.
Next,
[iaaa S
S |m/ll///aa|aa//|
by two applications of the Cauchy-Schwar inequality, one in y and the other in RM We deduce that [| [le I |/ [yy)ll/yyl//lll ||p|| conditioned on {fm }. Prop. A.4, Thm. A.1 (Bernstein's inequality), and a similar argument to that the proof Cor. A.5 deliver the asserted bound.
The next two lemmas used in the proof of Prop. 4.1 control the third and final term in (4.5).
Lemma D.4 (Linear empirical process: Concentration). Fix I. >> 0 and 5 E (0, 1). Define
N Σ (nn (uu (unn where A = fa ||o 1 st)
Z, sup ncAA.
(D.19)
N 2 log(1/6), then conditioned the realizations {0m} in the family t it holds that
log (1
Z, S ((v [2]] 3/2 1 Im 11070lll
Vt
(D.20)
N
with probability at least 1 5.
Proof. For any E Ac, we compute
M
Km, ((ura)))l
am (n, (uu1; mm))
M
m=1
1
1/2
1
1/2
laml?
1
Σ
(m. (luu (m:;(()):0m)))
M
M
1/2
S
Vt 1m
1
Σ
1ıp(11 0m)113
M
We used the Cauchy-Schward inequality twice. By the boundedness of sp the above display gives
(m (uu1: Mll. (CLA,R)) suu (m, ((u1;)))>/ ||
< |l 11
The iid random variables (n. (u, y)y: a+ (nas ((Unia))> (conditional on (0m)) ) are linear and hence continuous. Application of (A.11) in Cor A.5 to (Nn Φ }) taking value in the separable Banach space C'AA;; R) of continuous functions from compact set A, RM into R. equipped with the supremum norm, completes the proof.
The previous lemma gives a concentration bound for the linear empirical process and the next lemma estimates its expectation.
23

---

Lemma D.5 (Linear empirical process: Expectation). Fixt> 0. Define A as in Lem. D.4. Then
Il Imillazca,))llllll 1o0l Vt.
m()))ma)) sup aeA:
Nn, ((un:a))y s
(D.21)
N
VN
m=1
Proof. For any As, the Cauchy- Scchwar-- inequality in RM delivers the bound
1
Tn, (Unna))y
am
(Te (u 0m))y
M
N
n=1
1/2
)2)
/ 1/2
Σ Tos suunss 0m)))
Otm
M
M
Let the left hand side of (D.21) be denoted by E.. We next note that
B((un [mms (uun 0m))y]] = Eu, E (Mhs pun, 6m 0m))) un]]
Eu,, we [ unl. (un mm))
0.
Using the independence of (un mh) and (un', mae) for any two indices n * n', together with the above observation, thus obtain
(( [9m, (u mm))y (mme soun:: mm))
(u). (yms sp(uni 0m)yy] ((r 1oree sp(wn Om )
0.
This implies that
Vi
1
E S
(mas sp(un; 0m)yy (ma', (pune 0m)
M
R.n'==
N Σ
(((nn [mm spluns )) (Th's slue 0m)))/
M PLA!
M
E ((u;:
M VTA
We used Jensen's inequality in the second line, independence and the zero-mean property of the summands in the third line, and the Cauchy-Schwarz, inequality in y in the final line.
D.2 Proofs for subsection 4.2: Bounding the generalization gap
This subsection upper bounds the generalization gap with suprema techniques. We begin with the following empirical process concentration inequality. It gives uniform control on the difference between the empirical and population risk functionals. The process, as function of its index a, is quadratic because the RFM @ : is linear in a.
Lemma D.6 (Quadratic empirical process: Concentration), Fixt > and e (0, 1). Define
Z sup aeAr
9 (a: ((a
(D.22)
N Elg((n - (uu, a) Ennevl((u)) )(u;a)
1
(D.23)
N
ac
A=1
24

---

where
A fa RM || St..
(D.24)
If 2 log(1/6), then conditioned on the realizations {0m} the family 4, it holds that
Z. S Bin 32e (119122> + l1veli.otyy /100/000)/o00//1/
/og(11/)
(D.25)
N
with probability at least
Proof. For any E Ar and {1...., NJ. let
a) (9(u,) D(un: a) - Euvrllg(u) D(u; a()a)
We compute
[x((t,a) - 21] + 2 E. l + 2/( + +2 Bu [l $ <1 + 1l.
We used the fact that for any X v-almost surely, (1; = on the set Ar (by the Cauchy-Schwarz inequality). This implies that
| (t. )ll MISTAAA))
sup ( (t, I
- <11111 + 41kplli,
The (1, -) do indeed belong to C(A,;; IR) almost surely, as they can be written as sum of affine and quadratic forms on R. the a variable. Application of (A.11) Cor. A.5 (taking the separable Banach space to be C(A,; R) equipped with the supremum norm) completes the proof.
Since the supremum concentrates around its mean, remains to show that mean is small as function of the sample size. The next lemma does this with Rademacher symmetrization.
Lemma D.7 (Quadratic empirical process: Expectation). Fix t > O. Define Ze as in Lem. D.6. Conditioned on the realizations {0m} in the family 4, holds that
1
411p112+
B (v..) [Z]]
(D.26)
VN
VN
Proof. By Giné -inn symmetrization [see, e.g., 46, Sect. 4.2, Prop. 4.11, pp. 107-108).
N
E E(uny [n < 2
sup
1 N
ud Σ &n (u())) - (u.;:a)1 where en ~ ((ii(((1,,1))) 1=
aEA,,
because the original summands (conditioned on {6m})) are independent. The expectation on the right is interpreted the conditional expectation given {0m} (i.c., E( b.f.)) over the data and Rademacher variables only). The right hand side is the Rademacher complexity of the RF model class composed with the square loss. Expanding the square, it is bounded above by
N
E (n. 1.
Σ
En (9(
(I)
N
N
sup + 4E (M..)
Σ n=1
En (u.,) ((,,
(II)
asA.
N
2 (E.)
sup aεA,
E. F..
(III
N
n=1
We now estimate each term. The first term (I) satisfies the standard Monte Carlo bound
1/2
1/2
2
N
2
()) 2
Σ
s..
El(g(u))l3)
N
VN
n=1
n=1
25

---

For the second term (II), we begin by estimating the empirical average on the set A, as
M
N
En (g(n)) a()x
En (U(n), (uun Bm)))/))))))))))))))))
mm
N
M
N
12) 1/2
En (G(u)) (o(un; 0m)) mm))
M
N
12
by the Stuchy-Schwarce inequality in RM We deduce by Jensen's inequality and independence that
4vt
M
N
1/2
(II) S
Σ
Σ
[(((u)), (()
p(uw: (()w);m))))) (m)))]]
N
M
4Vt
M
N
1/2
Enw
E ((;;
N
M
A final application of the Cauchy-Schree inequality in Y in the last line shows that the second term (II) is bounded above by 4v/l|9/log Iippll////// By Young's inequality ab I a² x2/2 b² /2, we further bound
| Lg I|pll
22
(2 vi
2 Bi VN
+ 2
VN
N1/4
N1/4
VN
The third term (III) is estimated in a similar manner. Expanding the empirical average on Ar yields
1
En
Sullo(un;a)
am
Olms
mmmm
where
M
M
N
g(N)
Σ
En (un Om)s (pnun Omd 1m
mm.
N
The first equality in the above display satisfies the upper bound
V
111 M
Σ Σ ame ((N)
1)²²=
1/2
S
Vt
Σ
M
m (2)
I) 1/2
M
M
M
N
Σ
Σ
En Sun Omls spluni Omn ))
N
M
M.
by two applications of the Cauchy-Schwarz/ SwwwSshhwwazzzr inequality inequalll in RM Finally, deduce that
M
N
(II) S
(a.) (il(um 0m,) su(u 9m.)
N
M
m,,
M
Σ
Ey [1sp(u 0m 0m)) (l fm: ml
VN
M
m.m'
=1
12
VN
by Jensen's inequality, the fact that [[snew]] = 6n,n' and the Combining the three estimates completes the proof.
inequality in V.
The proof of the main generalization gap bound (4.12) is now immediate.
26

---

Proof of Proposition 4.7. Lem. D.6 and D.7 (applied with = () show that
(0m. 4( 4(19 + 111112 + 32e (119)) + I1olli. V
log log(1/0) (D.27)
VN
N
with conditional probability (over (0m)) at least - à if N log(1 /6). Since ō does not depend on {0m): ). we deduce by the tower rule of conditional expectation that the event implied by (D.27) has
P-p P-probability at least - 5 as well. Using the inequalities 4 - 32e and vā + vb S /2 + b)
shows that the expression in (D.27) is bounded above by
2(1 log(1/)))
322 32c (199) l|eli,
V)
N
Application of the inequality 1 S log(2/8), valid for d (0, 1), implies (4.12) asserted.
E Numerical experiment details
In this appendix, we detail the setup of the numerical experiment from Sect. and provide additional visualization of the function-values valued RFM's discretization- -nnerteeiie-neeeeedeeneee in Figure 3. All code used to produce the numerical results and figures this paper are available at
bttps://githhnn com http//iccchneeeenn error bounds- worrnnds-------oee
A RFM with M features is trained on N input-output pairs {Un, ((,,))) | according to the vector-valued RF-RR algorithm. The ground truth map G: (T; IR) - (T; a nonlinear operator defined by (00) (.) + u(:, 1), where u = (u(x,, 1),,, solves the partial differential equation
Ou 0 u²
10 10-10- Pu
(c,1) (0,
Öt
Fz
Ox
with initial condition u(., 0) ()) E RT; Here, T (0,2%) per is the 1D torus which comes with periodic boundary conditions. The initial conditions un ~ v are sampled iid from a centered Matérn-lit -ike Gaussian process according to [23, Sect. 6.3, p. 32].
The random features are defined in a similar way the Fourier Space RFs in [32, Sect. 3.1, p. 15]:
(uu (0) 0) 2.6 EEU(F {1 (kmsss) (Fu ) (FF) and 0 ~ p,,
where y is also centered Matérn Gaussian measure with covariance operator 1.8 de In the above display, J maps function its Fourier series coefficients, and F expresses Fourier coefficient sequence as a function expanded in the Fourier basis. The filter x is given by [32, Eqn. 3.6, p. 15] with 0.32 and 3 0.1. We take kmax 64. The feature map y lifts the notion of hidden neuron in neural network architectures to function space.
d= + 15 Id)-
In Figures 2 and 3, the quantity represented the vertical axis is empirical approximation to the relative Bochner squared error:
NO EN' (9( ( a, 10m)) s (uvwllg(u) - (w; ã. (0m DlI 1 N EEE 19(,))
((a (0:0
(E.1)
Ensw [9(u)]
In (E.1), N' = 500 is the size of the test set {M/, (M,,)) where (u, In-i 20N is disjoint from the training input set {un J The input and output spaces are discretized on the same p- point equally spaced grid in (0, 2T). Thus, the discretized version of any input or output function belonging to X' = y = (T; R) may identified with an element of RR. In Figures 2a and 3a, the regularization factor is chosen as = 7- 10- and as À = 3 10 10-6/VN in Figures 2b and 3b.
A priori, it is not clear whether this operator learning benchmark satisfies our theoretical assumptions because we cannot verify that the Burgers' solution operator belongs to the RKHS of (y, ()) (or the range of some power of the RKHS kernel integral operator). At more technical level, the feature map yp uses an unbounded activation function (ELU, the exponential linear unit), while our theory is only developed for bounded RFs (Assumption 3.1). Nevertheless, the empirically obtained parameter and sample complexity in Figure reasonably fit the main result our well-specified theory (Theorem 3.7).
27

---

M
M
M 100
Relative Boehmer squared
M 316
N 124
1000
10-2
N 288
N 668
1548
10-2
10-3
10
10?
P
(a) Varying M, A, for fixed N 1548.
(b) Varying N, A, for fixed M = 10a
Figure 3: Squared test error-which empirically approximates the population risk (ā; 9) -eeruss discretized output space dimension p, where G is the Burgers' equation solution operator (SM E).
28


Reviews:
[{"review_id": "pHGZeBP1Wz", "reviewer": "Reviewer_1g4u", "summary": "The paper proposes a learning theory for ridge regression in random feature models in the setting when the input-output map $\\mathcal{G}: \\mathcal{X} \\mapsto \\mathcal{Y}$ is vector-valued (potentially infinite-dimensional). The model under consideration is a random feature model $\\phi: \\mathcal{X} \\times \\Theta \\mapsto \\mathcal{Y}$, such that the feature map $\\Phi(\\cdot)$ consists of a linear combination of RFs $\\Phi(\\cdot) = \\sum_{m=1}^M \\alpha_m \\phi(\\cdot, \\theta_m)$,  with different random weights sampled from $\\theta_1, \\dots, \\theta_M \\sim \\mu$. The parameters $\\alpha_1, \\dots, \\alpha_M$ are fitted by minimizing the regularized empirical risk $\\frac{1}{N} \\sum_{n=1}^N \\lVert y_n - \\Phi(u_n) \\rVert_{\\mathcal{Y}}^2 + \\frac{\\lambda}{M} \\lVert{\\alpha}\\rVert_2^2$ given data sampled from some data generating distribution $(x_i, y_i) \\sim \\nu$. The assumed hypothesis class is an RKHS that consists of functions $\\mathcal{F} \\in \\mathcal{H}$ given by weighted averages of the RFs $\\mathbb{E}_{\\mathcal{P}(\\Theta)}\\lbrack \\alpha(\\theta) \\phi(\\cdot, \\theta)\\rbrack$ for $\\alpha(\\cdot) \\in L^2_\\mu(\\Theta, \\mathbb{R})$. However, the considered setting also allows for model misspecification $\\mathcal{G} = \\mathcal{G}_\\mathcal{H} + \\rho$, such that $\\mathcal{G}_\\mathcal{H} \\in \\mathcal{H}$ and $\\rho$ is almost surely bounded. The observation noise $y = \\mathcal{G}(u) + \\eta$ is modelled by a subexponential distribution allowing for heavier noise than the subGaussian.\n\nGiven the previous setting, the main result seems to be Theorem 3.4, which bounds the population squared error $\\mathbb{E}_\\nu\\lbrack \\mathcal{G}(u) - \\Phi(u)\\rbrack$ in terms of various quantities relating to the functions $\\mathcal{G}, \\mathcal{G}_\\mathcal{H}, \\rho$, the observation noise $\\eta$ under mild conditions which roughly state that $M$ is of order $\\sqrt{N}$. In contrast to previous work, the parameter complexity $M$ is free from logarithmic factors, which gives the lowest parameter complexity so far. As an application of the previous bound, the authors results regarding 1) strong statistical consistency of the model, that is, almost sure convergence in mean square of $\\Phi(\\cdot)$ to $\\mathcal{G}(\\cdot)$, and 2) corresponding explicit convergence rates. Sketches of the proofs are given in Section 4 to guide the reader along the main steps.", "questions": "- As being familiar with random feature models, I understood the main premise of the paper, but I was still left wondering about how one could construct feature maps into such infinite-dimensional spaces. I think giving some examples about what kind of RFs were used before for operator learning, on what kind of data, etc would go a long way. \n\n- I was wondering if it would be possible to visualize the various hyperparameter complexities and empirically validate the convergence rate appearing in the theorems to have some visual intuition either using synthetic data or one of the datasets appearing in previous work (if the true operator is known)? Another idea which would also help in structuring the results and aid in understanding them is to draw a flowchart about the previous theorems and lemmas showing how they depend on each other.\n\nMinor:\n- In line 32, when the authors state the size of RF matrices is quadratic in the number of features $M$, do they actually mean the covariance matrix that has size $M \\times M$, or the $N \\times M$ feature matrix? In the latter case I am unsure where the quadratic factors comes in.\n- In line 228, there might be a $k$ missing in $\\mathfrak{R}_N^{\\lambda_k}$, otherwise $\\hat \\alpha$ does not actually depend on $k$\n- In Apprendix A, line 489, the authors define the subexponential norm in terms of the moments, which is slightly uncommon, since it's standard to define it in terms of the exponential Orlicz norm. It might be beneficial to state the original definition first, and relate that", "limitations": "As a purely theoretical work, there is no direct societal impact commonly associated with AI models. The authors have addresed the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and coherent. The area, theoretical properties of infinite-dimensional RF models, is relevant to (contemporary) applications in scientific computing, such as learning the solution operator of PDEs using RF or neural models. The presented results are highly technical and non-trivial to derive. In addition to generalizing the theory of RF models to this setting, the RF parameter complexity is also sharper by a logarithmic factor as opposed to previous works, thatworked with stronger assumptions on the output domain. The presentation is good-ish, I think they did a good job in outlining the setting, then the main results, and presenting the key steps of the proofs in section with full proofs deferred to the appendix.", "weaknesses": "As a theoretical work, there is no empirical part to speak of. This, on the one hand is common in these types of papers, but on the other, it makes the paper less accessible to a majority of the NeurIPS community. Although it seems like such RF models do have important applications, I am unsure about the size of the community that is involved in these kinds of niche results, as the main application only seems to be in operator learning.\n\nOne other point is that although there are applications listed, the mathematical objects considered in the paper still seem kind of abstract, I think giving more examples and connecting the dots more to the applications would help in this aspect (see question 1).\n\nLastly, no illustrations are provided whatsoever to support comprehension or visualize the results. Some figures would go a long way to make the paper less dense (see question 2)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We start by thanking the reviewer for your appreciation of the merits of our paper and your welcome suggestions to improve it. Below, we address the concerns raised by the reviewer and thank the reviewer in advance for their patience in reading our detailed reply. \n1. The construction of \"good\" random feature pairs $(\\varphi,\\mu)$ in the infinite-dimensional output space setting is still an open problem. This is partly because there are no ``canonical'' operator-valued kernels (OVKs) $K\\colon\\mathcal{X}\\times\\mathcal{X}\\to\\mathcal{L}(\\mathcal{Y};\\mathcal{Y})$, which the random features approximate. In contrast, canonical kernels in the scalar output setting include squared exponential and Mat\\'ern kernels, which have interpretable hyperparameters such as lengthscales, regularity, and variances that may be adapted to the problem. In the operator learning setting, handcrafted vector-valued random features were designed in [NS21, Sec. 3] for specific PDE problems on a case-by-case basis. In [KDPCRA16], separable OVKs $K(u,u')=k(u,u')T$ were used, where $k$ is a canonical scalar kernel (hence RF approximations of $K$ are then straightforward if one for $k$ is known) and $T$ is a bounded linear operator on $\\mathcal{Y}$. Both papers work with functional data. More general constructions would require novel ways to adapt such features or kernels to data.\n2. To empirically test the validity and sharpness of our theory, we take the reviewer's suggestion and implement a Burgers' equation operator learning benchmark for a range of sample sizes $N$, random features $M$, and data resolutions $p$. The dataset appears in previous work on operator learning. This example does not necessarily satisfy our theoretical assumptions because we cannot verify that the Burgers' solution operator $\\mathcal{G}$ is an element of the RF's RKHS. Also, the feature map uses an unbounded activation function (ELU), while our theory is only developed for bounded RFs. Nevertheless, the observed parameter and sample complexity reasonably validate the theory.\n3. Regarding the reviewer's suggestion of including a flowchart illustrating the interdependency of our results, we agree that this would greatly help in providing a quick overview of our theoretical results. We thank the reviewer for this suggestion, and will include it in a revised version of our paper.\n\nRegarding the minor comments: \n* By quadratic, we do mean the RF ``gram/covariance-like'' matrices $k_{ij}=\\frac{1}{N}\\sum_{n=1}^N\\langle \\varphi(u_n;\\theta_i),\\varphi(u_n;\\theta_j)\\rangle_{\\mathcal{Y}}$ that are of size $M$ by $M$. \n* We thank the reviewer for pointing out the typo in Line 228.\n* In the revision, we will cite the standard definition of exponential Orlicz norm that the reviewer mentions (e.g., Vershynin's book).\n\nWe sincerely hope to have addressed the concerns to your satisfaction and thank the reviewer again for pointing them out to us. \n\n* [NS21] Nelsen, N.H., Stuart, A.M., \"The random feature model for input-output maps between Banach spaces\", *SIAM Journal on Scientific Computing*, **43**(5), A3212--A2343, (2021)\n* [KDPCRA16] Hachem, K., et al., \"Operator-valued kernels for learning from functional response data\", *Journal of Machine Learning Research*, **17**, 1-54, (2016) "}, {"review_id": "MDFWeJFq5S", "reviewer": "Reviewer_ykP5", "summary": "The paper proposes a statistical analysis of the risk associated to learning with vector-valued random features (vv-RF) in the context of ridge regression.\n\nThe analysis shows that $\\sqrt{N}$ random features are enough to attain a $\\mathcal{O}(\\frac{1}{\\sqrt{N}})$ squared error (matching minimax rates) and strong consistency in the well-specified setting, as well as slower convergence rates related to how well the target function can be approximated in the RKHS in case of misspecified setting.", "questions": "In the contributions listing, you mention in (C4) that the proof approach is not specific to RR. While I agree that you make no use of the closed form solution, you still make use of the fact that the loss is the squared loss (e.g. in 4.4), and the analysis would not hold if another loss was chosen. Same remark applies in the conclusion when you mention that future works could focus on general $L^p$ losses. If the analysis is not specific to the RR setting, for which class of losses does it hold ?\n\nAnd more of a remark: it would be good to include a non trivial example of a feature map $\\phi(x, \\theta)$ used to solve a problem where $p = \\infty$.", "limitations": "- Limitations are well discussed in the paper, expect perhaps the point about the specificity to the RR that is mentioned in the \"Questions\" section.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Topic is highly relevant to the machine learning community\n- Paper is remarkably well written despite the technical complexity\n- The paper is mathematically sound\n- Assumptions are mild and very standard", "weaknesses": "Contribution (C4) is a bit exaggerated in my opinion, see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We start by thanking the reviewer for your appreciation of the merits of our paper and your welcome suggestions to improve it. Below, we address the concerns raised by the reviewer and thank the reviewer in advance for their patience in reading our detailed reply.\n1. We believe the reviewer's comment about contribution (C.4) is a very fair criticism, as certain steps in our derivation, including identity (4.4), are indeed specific to a quadratic loss. In view of this, we will tone down the statement of (C.4) in a revised version of the paper. We plan to expand on error bounds for the RFM for more general loss functions in future work. At least in the absence of noise, our intuition is that the RFM estimates should exhibit the same scaling as estimates for Monte-Carlo sampling; based on this intuition, we fully expect generalization to $L^q$-type loss functions to be possible since the Monte-Carlo error is independent of $q$. When allowing for noise, significant adaptations of our arguments may indeed be necessary, as equation (4.4), which is specific to a quadratic loss, is then important to our present approach. \n2. A non-trivial example of a feature map in the $p=\\infty$ infinite-dimensional output space case is given by the Fourier space features [NS21, Eqn. 3.5] for the Burgers' equation solution operator. It leads to a fully correlated (non-diagonal) limiting operator-valued kernel (hence non-trivial), which is important for the setting $p=\\infty$. We include numerical results for this problem in the attached pdf figure file, and will add this concrete example to the revised version of our paper. \n\nWe again thank the reviewer for appreciating the merits of this work, and sincerely hope to have addressed your concerns.\n\n* [NS21] Nelsen, N.H., Stuart, A.M., \"The random feature model for input-output maps between Banach spaces\", *SIAM Journal on Scientific Computing*, **43**(5), A3212--A2343, (2021)"}, {"review_id": "9pIsmRJwfy", "reviewer": "Reviewer_1Snc", "summary": "This paper investigates the theoretical aspects of learning vector-valued operators with random features. Specifically, it studies the convergence of the random feature estimate $\\Phi(u;\\hat{\\alpha})$ to the true underlying function $\\mathcal{G}$. Its main results are:\n\nTheorem 3.4: Error bound for fixed $\\lambda$ and fixed $N$. \n\nTheorem 3.7: The same error bound in the well-specified case $\\mathcal{G}\\in\\mathcal{H}$. \n\nTheorem 3.10: Almost sure consistency of the random feature estimate to the true function $\\mathcal{G}$ as $N\\rightarrow\\infty$ and $\\lambda\\rightarrow0$. \n\nTheorem 3.12: The convergence rate. ", "questions": "Theorem 3.10 and Corollary 3.13: It is, at least in my limited experience, rare to see almost sure statements in statistical learning theory. Could the authors please comment on what made it possible in this case, or whether they believe a simple Borel-Cantelli argument should make all of the results in statistical learning theory almost sure statements?\n\nAlso, none of the results seem to depend on the distribution $\\mu$ of $\\theta$, and always just the number $M$ of them. I could be mistaken, but this is hard to believe - what if $\\mu$ put all mass on one point? I didn't seem to be able to find in Assumptions 3.1, 3.2 and 3.3 that prevented something like this. ", "limitations": "The authors barely discuss the limitations of their work, except as \"future work\" in the Conclusion section. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is entirely a theoretical paper, so the value of the paper should lie in the significance of the results and the correctness of its proofs. I believe that the stated results would be good contributions (although see Questions for Theorem 3.10), but perhaps quite limited in scope. Unfortunately, I have not had time to go through all of the proofs in detail (perhaps I will in the subsequent reviewing process). ", "weaknesses": "The paper is in general well-written, and the mathematics is presented quite clearly. However, its structure makes it rather difficult to read. For example, when reading the main body of the paper, we are led to the appendix several times for definitions that are required to read on in the main body. This happens on L151, L177, L179, L222 and L240. Having proofs in the appendix is fine, and is often done, but the way we are led to the appendix in this paper disrupts the flow a bit in my opinion. Also, the proofs are not in one place - we have to jump back and forth between Section 4 and the Appendix to read the proof of the results. \n\nAlso, the results are very abstract, and I think it would have been much better if some concrete examples of $\\phi$, $\\Phi$, $\\theta$, $\\alpha$ and $\\mathcal{H}$ were given. An example of a learning algorithm to which the results could have been applied would have been even better. \n\nMinor comments:\n\nL228: I think the superscript $\\lambda$ should be $\\lambda_k$. \n\nL614, displayed equation: The squared brackets after $\\mathbb{E}$ are not closed. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We start by thanking the reviewer for reading our paper and for their comments. We have fixed the typos in the revised version of our paper. Regarding the reviewer's criticism of the structure and readability of the paper, we agree that splitting into proofs in appendix and theorem/lemma statements in the main body make a thorough reading difficult. To ease the burden on the reader, in the revision we will: 1) use the ``thm-restate'' LaTeX package that will repeat the full theorem/lemma statements immediately above their proofs in the appendix, so no more need to flip back and forth; and 2) Submit the full paper (main body plus supplement) as the official supplementary materials so that all hyperlinks work as intended when reading results, proofs, and definitions.\n\nAdditionally, we have now included a concrete operator learning benchmark example (Burgers' evolution operator) where our RF ridge regression algorithm is actually implemented. Here, $p=\\infty$ and a nontrivial choice of $\\varphi$, $\\theta$, and $\\Phi$ are used in the regression problem (see the attached pdf figure file for the details).\n\nBelow, we address the specific concerns raised by the reviewer and thank the reviewer in advance for their patience in reading our detailed reply. \n1. Regarding the reviewer's question on Borell-Cantelli, we believe that it is indeed the case that non-asymptotic, high-probability results can often be turned into almost sure asymptotic results. However, there are certain draw-backs to such almost-sure asymptotic results. For example, even though the asymptotic behavior is guaranteed to occur ``eventually'' (with probability 1), it is completely unclear whether we should ever expect to observe such rates at practically relevant numbers of data-pairs and random features. In this sense, we view our asymptotic consistency result as a considerably weaker assertion than the high-probability estimates that it is derived from. \n2. Regarding the reviewer's comment about the dependence on the underlying measure $\\mu$, it is indeed true that our results do not make any specific assumptions on $\\mu$, as such. However, $\\mu$ implicitly determines the underlying reproducing kernel Hilbert space (RKHS), via the random feature map $\\varphi$. In particular, if $\\mu$ is concentrated on a single point, then this RKHS is necessarily at most one-dimensional, and hence our results only imply convergence of the RFM to any operator *belonging to this one-dimensional subspace*, in this specific case. More generally, our results require either that the underlying operator belong to the RKHS or that it at least belong to the $L^2_\\nu$-closure of this RKHS. This can be viewed as a compatibility requirement between the operator and the RFM; the performance of the RFM should absolutely be expected to depend on the \"degree of compatibility between the operator $\\mathcal{G}$, the measure $\\mu$ and the random feature map $\\varphi$\". We thank the reviewer for this pertinent question, and will include a more detailed discussion of this point in our revision.\n\nWe sincerely hope that we have addressed all your concerns and kindly request the reviewer to update their assessment accordingly."}, {"review_id": "R8BhNHwzpx", "reviewer": "Reviewer_efr3", "summary": "This paper presents a theoretical error analysis of infinite-dimensional input-output ridge regression with vector-valued random features. This one is the first analysis adapted to infinite-dimensional outputs and even improves existing results for finite-dimensional outputs. Several by-products come with the main error bound, such as strong consistency in the misspecified setting and minimax optimal convergence rate in the well-specified setting. In addition, in the well-specified setting, the proposed analysis provides the sharpest parameter complexity, that is square root of the sample size. The analysis is based on a new proof technique, which is sketched in the last section.", "questions": "1) Could the authors give some details regarding the relaxation of the independence assumption in light of the proof outline (Section 4)?\n2) Why the notation $\\Phi(u; \\hat \\alpha, \\{\\theta_m\\})$ is preferred to $\\Phi(u; \\hat \\alpha)$ before Example 3.9, and the converse after? Besides, why Theorem 3.7 is named as such rather than as a corollary?\n3) Could the authors explain the assumption $\\mathcal G \\in \\operatorname{Im}(\\mathcal K^{r/2})$ and its implications?", "limitations": "Overall, technical assumptions are discussed. Nevertheless, Societal impact is not addressed.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The subject addressed by the authors is topical since there is a lack of theoretical analysis of random Fourier methods with infinite-dimensional output in the literature, and that the random Fourier technique is definitely the most practical way to speed up kernel methods.\nThe contribution of this work is substantial since, besides providing the first result for infinite-dimensional outputs, it also presents an improved parameter complexity ($\\sqrt N$, where $N$ is the sample size) with respect to the literature ($\\sqrt N \\log N$).\nMoreover, this paper is very well written: there is no typo and a clear effort has been made to present clearly the theoretical analysis. Remarks and examples help understanding the results and generally anticipate the questions that may arise while reading the manuscript.", "weaknesses": "Except for a minor remark (RF-RR Lines 48, 74, 81 is used before being defined Line 112), I think that the paper has no flaw. I must admit that I am used to seeing a numerical experiment confirming the convergence rate obtained theoretically, but I understand that choices have to be made to fit the page limit and I am quite grateful to the authors to try to explain the successive steps of their proof instead. In a way, the paper is more consistent this way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We start by thanking the reviewer for your appreciation of the merits of our paper and your welcome suggestions to improve it. We will fix the use of RF-RR acronym in a revised version of the paper, thank you for catching that. Additionally, based on suggestions from the other reviewers, we have included some numerical experiments to visualize the convergence behavior of vector-valued RF-RR and compare it to our theory (see the attached figures pdf file).\nBelow, we address the specific concerns raised by the reviewer and thank the reviewer in advance for their patience in reading our detailed reply. \n1. Regarding the independence assumption, we thank the reviewer for directing our attention back to this point; in fact, thanks to the reviewer's suggestion, we have now realized that our derivation goes through almost verbatim, with only two minor modifications to the proofs in Appendix D.1, when only assuming that the data pairs $(u,y)$ are of the form $y = \\mathcal{G}(u) + \\eta$, where the noise $\\eta$ is a subexponential random variable such that the condition expectation $\\mathbb{E}[\\eta|u] = 0$. This allows us to completely eliminate the independence assumption in our revised version. Thank you!\n2. We define the equivalence of the two notations in line 104. However, we agree with the reviewer that our use is not consistent. The notation $\\Phi(u;\\alpha,(\\theta_m))$ is introduced to emphasize the dependence of the model on the realizations $\\(\\theta_m)_m\\sim\\mu^{\\otimes M}$, and Thm. 3.4 explicitly mentions the $(\\theta_m)$ in its hypotheses. However, the remaining results do not explicitly mention $(\\theta_m)$ in the theorem statements so we will consistently use $\\Phi(u;\\alpha)$ after Thm. 3.4 in the revision.\nAlso, we choose to name Thm. 3.7 as is instead of Corollary 3.7 because it is the highlight/takeaway result of the paper that is easiest to compare to prior work (as in Table 1) and explain to general audiences. \n3. Regarding the assumption $\\mathcal{G} \\in \\mathrm{Im}(\\mathcal{K}^{r/2})$, we view it as a regularity assumption on the underlying operator. In specific settings, when approximating an underlying function in finite dimensions, it corresponds to a fractional (Sobolev) regularity of the underlying function. In general, it appears difficult to check this condition, which is a definite limitation of this result, and we will point this out more explicitly in our revised version.\n \nWe sincerely hope that we have addressed the concerns of the reviewer to your satisfaction. \n"}, {"review_id": "RY3vrwGb7L", "reviewer": "Reviewer_HQhU", "summary": "This paper presents error analysis for learning with vector-valued random features, where the output takes vector values. Specifically, the paper considers random feature ridge regression and derive a general bound for the population risk functional, based on which the paper gives several results such as convergence rates for well-specified and mis-specified problems, statistical consistency as well as almost sure bounds. The main results show that $O(\\sqrt{N})$ random features are sufficient to derive error bounds of the order $O(1/\\sqrt{N})$, where $N$ is the number of training examples. This extends the existing results from real-valued output to vector-valued outputs.\n", "questions": "Can the analysis here be extended to learning with logistic loss functions. In this case, we also do not have explicit formula for the solution?\n\nCan we derive improved results if $r>1$ to overcome the saturation phenomenon?\n\nHow would the output dimension affect the convergence rates of the learning with vector-valued outputs.\n", "limitations": "I do not see concerns on negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides comprehensive analysis and consider approximation, generalization, misspecification and noisy observations. Furthermore, the paper implies minimax optimal convergence rates in the well-specified setting.\n\nThe paper is very well written, and the analysis seems to be rigorous.\n\nThe technique does not rely on the explicit RF-RR solution formula, and avoids the use of matrix concentration inequalities. ", "weaknesses": "While the technique does not use matrix concentration inequalities, the paper only considers random feature ridge regression with square loss. Therefore, the problem considered in the paper is a bit limited. It is not quite clear to me whether the technique developed here can be extended to learning with other loss functions, e.g., logistic loss. Can we get similar error bounds for vector-valued learning with random features and logistic loss?\n\nIn Theorem 3.12, the error bounds are of the order $\\lambda^{r\\land 1}$. Therefore, the error bounds would improve if we have very nice regularity with $r>1$. In other words, the results suffer from a saturation phenomenon. It is not clear to me whether the technique developed here can overcome this saturation phenomenon.\n\nThe obtained bounds do not show an explicit dependency on the output dimension $p$. It is not clear to me how the output dimension would affect the performance of learning with vector-valued outputs.\n\nTypo:\n\nAbove Eq (3.5): \"optimal the sense\" should be \"optimal in the sense\"\n\nAbove Eq (3.5): \"a short calculation deliver\" should be \"a short calculation delivers\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe start by thanking the reviewer for your appreciation of the merits of our paper and your welcome suggestions to improve it. We will correct the identified typos in the revision. Below, we address the concerns raised by the reviewer and thank the reviewer in advance for their patience in reading our detailed reply. \n1. Closely related analysis can indeed be used to derive bounds for other settings, in particular this has been done for Lipschitz continuous loss functions; relevant results have e.g. been obtained in [SGT18]. However, the available rates for a general Lipschitz loss are significantly worse than the rates we have achieved through our refined analysis in the quadratic (i.e., squared $L^2$ loss) setting. It is unclear to what extent our improved rates may be specific to the quadratic setting. One might conjecture that similarly improved rates (as compared to the general Lipschitz case), could at least be possible when replacing the quadratic loss by e.g. a quartic, or more general $L^q$-loss, instead. We plan to extend our analysis in this direction, in the future. \n2. We thank the reviewer for their comments regarding the saturation phenomenon. We believe that this saturation is inherent to the choice of regularizer in ridge regression, and not a mere artifact of our analysis. We would like to expand on the reason for this intuition in more detail: if we neglect errors due to a finite number of data pairs and random features (i.e. formally take the limit $N,M\\to \\infty$), we arrive at the ridge regression problem (B.6) on the RKHS with $\\vartheta := \\lambda$. This problem is explicitly solvable, with solution ${\\mathcal{G}\\_{\\vartheta}}$ given in (B.4). Following the argument of Lemma B.3, the corresponding $L_{\\nu}^2$ squared approximation error $\\Vert \\mathcal{G} - \\mathcal{G}_{\\vartheta}\\Vert^2$ is generally of order $\\vartheta \\sum_j \\lambda_j^r/(\\lambda_j + \\vartheta) \\ge \\vartheta \\lambda_1^r/(\\lambda_1 + \\vartheta)$. For small $\\vartheta$, say $\\vartheta < \\lambda_1$, this gives a lower bound on $\\Vert \\mathcal{G} - \\mathcal{G}_{\\vartheta}\\Vert^2\\ge C\\vartheta$ with $C = C(\\lambda_1,r)>0$, which decays at best linearly in $\\vartheta$, even if $r>1$. Replacing $\\vartheta$ by $\\lambda$ thus strongly suggests that our upper bound of the form $\\lambda^{r\\wedge 1}$ for the RFM should be accompanied by a (matching) lower bound of order $\\lambda$ for $r>1$.\n\n3. Generically, the output dimension does not affect the convergence rates in the vector-valued setting, only the constants in the bounds (e.g, through the norm on the space $\\mathcal{Y}$). Indeed, when $\\mathcal{Y}$ is even infinite-dimensional, we show in the numerical experiments (attached figure pdf file) that the error is not sensitive to discretized output dimension $p\\gg 1$. However, there exists other problems where the constants may blow up as $p\\to\\infty$, which would lead to a vacuous error bound. The underlying mathematical objects should have a well-defined meaning in this limit (e.g., taking the discretization resolution to infinity) to prevent this from happening.\n\nIn general, as alluded to in the conclusion of our submitted manuscript, we agree with the reviewer that determining conditions under which faster rates can be achieved is a very interesting and practically relevant question, which we plan to follow up on in future work. In particular, we believe faster rates can be achieved in our analysis, under certain conditions on the probability measure on random features, and utilizing the concept of local Rademacher complexity; we would like to mention that the results of our paper could have been obtained by invoking global Rademacher complexity estimates (this is implicit in certain steps of our proofs).\n \nWe sincerely hope that we have addressed the concerns of the reviewer to your satisfaction. \n\n* [SGT18] Sun, Y., et al., \"But how does it work in theory? Linear SVM with random features\", *Advances in Neural Information Processing Systems*, **31**, (2018)\n"}]

Author rebuttal:
At the outset, we would like to thank all five reviewers for their thorough and patient reading of our article. Their fair criticism and constructive suggestions will enable us to improve the quality of our article. If accepted, a revised camera-ready version of the article, with changes as outlined below, will be uploaded. We proceed to answer the points raised by each of the reviewers individually, below. We also attach one page of figures that show the results of numerical experiments suggested by the reviewers (with code to be made publicly available on Github). The literature references in this figures document refer to the two papers below.

Yours sincerely,

Authors of "Error Bounds for Learning with Vector-Valued Random Features".

* [KLLABSA23] Kovachki, N., Li, Z., et al., "Neural operator: Learning maps between function spaces with applications to PDEs", *Journal of Machine Learning Research*, **24**(89), 1--97, (2023)
* [NS21] Nelsen, N.H., Stuart, A.M., "The random feature model for input-output maps between Banach spaces", *SIAM Journal on Scientific Computing*, **43**(5), A3212--A2343, (2021)

Meta-review: The submission is about scaling up kernel methods. The authors consider the random feature (RF) approximation of kernel ridge regression with Polish input space and separable Hilbert output space. They prove a high probability error bound on the population squared error (Theorem 3.4). This result implies (i) O(1/sqrt{N}) convergence rate of the squared error in the well-specified case (Theorem 3.7) with O(\sqrt{N}) RFs where N denotes the sample size, (ii) strong consistency in the misspecified case (Theorem 3.10), and (iii) slower rates in the misspecified setting (Theorem 3.12).

Kernel methods are among the most powerful tools of machine learning; scaling them up in a principled way is of central importance to the community. The established novel tight results in the submission nicely contribute to this endeavor.
Decision: Accept (spotlight)