Optimal deep learning of holomorphic operators between Banach spaces
Authors: Ben Adcock
Nick Dexter
Sebastian Moraga
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Deep learning
operator learning
parametric PDEs
deep neural networks
generalization error
optimal algorithms
Primary area: learning_theory
TL;DR: We show that deep learning with fully-connected deep neural networks is optimal for learning holomorphic operators

Abstract: Operator learning problems arise in many key areas of scientific computing where Partial Differential Equations (PDEs) are used to model physical systems. In such scenarios, the operators map between Banach or Hilbert spaces. In this work, we tackle the problem of learning operators between Banach spaces, in contrast to the vast majority of past works considering only Hilbert spaces. We focus on learning holomorphic operators -- an important class of problems with many applications. We combine arbitrary approximate encoders and decoders with standard feedforward Deep Neural Network (DNN) architectures -- specifically, those with constant width exceeding the depth -- under standard $\ell^2$-loss minimization. We first identify a family of  DNNs such that the resulting Deep Learning (DL) procedure achieves optimal generalization bounds for such operators. For standard fully-connected architectures, we then show that there are uncountably many minimizers of the training problem that yield equivalent optimal performance. The DNN architectures we consider are `problem agnostic', with width and depth only depending on the amount of training data $m$ and not on regularity assumptions of the target operator. Next, we show that DL is optimal for this problem: no recovery procedure can surpass these generalization bounds up to log terms. Finally, we present numerical results demonstrating the practical performance on challenging problems including the parametric diffusion, Navier-Stokes-Brinkman and Boussinesq PDEs.

Optimal deep learning of holomorphic operators between Banach spaces
Ben Adcock Department of Mathematics Simon Fraser University Canada
Nick Dexter
Department of Scientific Computing Florida State University
USA
Sebastian Moraga Department of Mathematics Simon Fraser University Canada
Abstract
Operator learning problems arise in many key areas of scientific computing where Partial Differential Equations (PDEs) are used to model physical systems. In such scenarios, the operators map between Banach Hilbert spaces. In this work, we tackle the problem of learning operators between Banach spaces, in contrast to the vast majority of past works considering only Hilbert spaces. We focus learning holomorphic operators an important class of problems with many applications. We combine arbitrary approximate encoders and decoders with standard feedfor- ward Deep Neural Network (DNN) architectures specificalll. those with constant width exceeding the depth under standard (2-soss minimization. We first identify family of DNNs such that the resulting Deep Learning (DL) procedure achieves optimal generalization bounds for such operators. For standard colneccon architectures, we then show that there are uncountably many minimizers of the training problem that yield equivalent optimal performance. The DNN architectures we consider are 'problem agnostic', with width and depth only depending on the amount of training data m and not on regularity assumptions of the target operator. Next, we show that DL is optimal for this problem: no recovery procedure can surpass these generalization bounds up to log terms. Finally, we present numerical results demonstrating the practical performance challenging problems including the parametric diffusion, Havier-Stokes Brinkman and Boussinesq PDEs.
Introduction
Operator learning is increasingly being investigated for problems arising in computational science and engineering. These problems are often posed in terms Partial Differential Equations (PDEs), which be viewed operators mapping function spaces function spaces. Depending the requirements for well-posedness of the PDE, both the input and solution spaces are often Hilbert, or, more generally, Banach spaces. The aim of operator learning is efficiently capture the dynamic behavior these operators using surrogate models, typically based on Deep Neural Networks (DNNs). Specifically, we want to learn
(1.1) where ) is the PDE solution space, X represents the data supplied to the PDE, i.e., possibly multiple functions describing initial and boundary conditions or forcing terms or, equivalently, a vector of parameters defining such functions.
F
X F(X) y
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Let be a probability measure on X. Given noisy training data
{(X,, ((X,) + E.))=
(1.2)
where X1,...,X,, widd I and E, is noise, a typical operator learning methodology consists of three objects: approximate encoder Ex X Rdxx, an approximate decoder Dy R y and
DNN N [dx Rdy, It then approximates /' as
F F= Dy NoEx
(1.3)
The encoder and decoder are either specified by the problem, learned separately from data, or learned concurrently with N. The goal, as in all supervised learning problems, is to ensure good generalization via the learned operator F from little training data m as possible.
1.1 Contributions
As noted in, e.g., [6 66], the theory deep operator learning is still in its infancy. We contribute to this growth in the following ways. We consider learning classes of holomorphic operators (Assumption 2.2 with arbitrary approximate encoders Ex and decoders Dy. As we explain in $2.3 (see also [52] $5.21, [53] $3.4] and [41]) these operators are relevant in many applications, notably those involving parametric PDEs. The main contributions of this work are as follows.
1. We consider operators taking values in general Banach spaces. As noted, the vast majority of existing work (with the notable exception of (16) considers Hilbert spaces.
We consider standard feedforward DNN architectures (constant width, width exceeds depth) and training procedures (E2-loss minimization).
3. (Theorem 3.1 We construct family of DNNs such that any approximate minimizer of the corresponding training problem satisfies a generalization bound that is explicit in the various error sources:
namely, an approximation error, which decays algebraically in the amount of training data m; encoding-decoding decoding errors, which depend on the accuracy the learned encoders and decoders; an optimization error, and; sampling error, which depends on the noise E; in (1.2). These DNN architectures are problem agnostic; they depend on m only. In particular, the architectures are completely independent on the regularity assumptions of target operator.
5. (Theorem 3.2)
We show that training problems based any family of fully-connected DNNS possess uncountably many minimizers that achieve the same generalization bounds.
6. (Theorems 3.1
We provide bounds in both the L and - -nrms that hold in high probability, rather than just expectation.
3.2
7. (Theorems 4.1 4.2
We show that the generalization bound is optimal with respect to m: no learning procedure (not necessarily DL-based) achieve better rates in up to log terms. Finally, we present a series of experiments demonstrating the efficacy of DL on challenging problems such as the parametric diffusion, Siiii--Stoke-Brinkkmee and Boussinesq PDEs, the latter two of which involve operators whose codomains are Banach, as opposed to Hilbert, spaces.
1.2 Relation previous work
Approximating operator between function spaces with training data obtained through numerical PDEs solves presents formidable challenge. Nevertheless, in recent years, significant advances have been made through the development of DL techniques, leading to the field of operator learning [15
83 93 [03]. These approaches often leverage intricate DNN architectures to approximate the complex mappings inherent in physical modelling scenarios. Many works have also focused on the practical aspects of operator learning in real-world applications
40 51 53 56, 58 60
62 69
13 24 35
48 49
59
61
64
65
70
73
77
80
8[
84
96 18- [04] [05].
On the theoretical side, universal approximation theorems for operator learning have been developed 55 68 69 and elsewhere. Such bounds are typically not quantitative in the size of the DNN needed to achieve certain error. For this, one typically either restricts to specific operators (e.g.. certain PDEs) or imposes regularity conditions. One such assumption is Lipschitz regularity see 66 87 and references therein. However, learning Lipschitz operators suffers from curse of parametric complexity [54], meaning that algebraic rates may not be achievable. Another
in [50
10 16 55

---

common assumption is holomorphy, While stronger, it is, as noted, very relevant to operator learning problems involving parametric PDEs. Quantitative approximation results for holomorphic operators have been shown in 26 31
55
and elsewhere.
However, these works do not consider the generalization error, i.e., the error incurred when learning the approximation I.3 from the finite training data (1.)) This is particularly important in applica- tions of operator learning where data obtained through expensive numerical PDE solves, since such problems are highly data-starved. Several works have tackled this question from the perspective of statistical learning theory and nonparametric estimation [6 55 66], but only for Lipschitz operators. As observed in [6, $9.5), this approach generally leads to a best (mm)1/22 decay of the T -orm error with respect to m. Theorem 4.1 shows that such a rate is strictly suboptimal for learning the classes of holomorphic operators we consider. Our generalization bounds in Theorems 3.1 3.2 do not use such techniques, and yield near-optimal rates in both the - and - -norms. See also [0 for some related work in this direction for reduced-order modelling with convolutional autoencoders.
Our work is inspired by recent research on learning holomorphic, Manach-valuce functions [2] 6). We extend both these works, in particular, [5], to learning holomorphic operators. We also significantly improve the error decay rates in [5] with respect to m and show they can be achieved using substantially smaller DNNs with standard training (i.e., lo-soss minimization). See Remarks Our theoretical guarantees fall into the category of encoder-decoder--eet [52), which includes the well-known PCA-Ner [10] and DeepONei (68) frameworks. As in other recent works
C.1 C.2
16 30, 55 66), in Theorems 3.1 3.2 we assume the encoder-decoder pair (Ex; Dy. in (13) have
been learned, and focus on the generalization error when training the DNN N.
2 Notation, assumptions, setup and examples
2.1 Notation
Let (X,, || Ilxx) and (D), 11 Ily)) be Banach spaces and μ be probability measure on X. Let (D"" -|ll [ly-) ) be the dual of y and B()") be its unit ball. The Bochner and Petris L of a (strongly and weakly, respectively) measurable operator F : X - y are defined as
1/P
|| |F (1(())1BB
(/ (F)(()))P) 1/2
|| [| = sup V*E(O")
respectively, for 1 < p < co, and analogously for p = ao (see, e.g.,
) Notice that
[[ & || [| for p co, while I| = || L (X:)))
Throughout this work, (N), 0 < p S xo denotes the standard e space with (quasi-)norm || llp. (2) R whose
We also define the monotone s space C (N) as the space of all sequences
minimal monotone majorant å E ( (N). Here z (ž,) is defined as ă = sup,2i 1zyl-
Given (componentwise) activation function we consider feedforward DNNs of the form
N R R. z N(2) (o
(2.1)
where A: R. + R N are affine maps, and N₂ = n and NL+2 = k. We define width(NV) = max (N NI..... .., N } and depth(N) L. We denote class of DNNs of the form (2.1) with fixed architecture (i.e., fixed activation function, depth and widths) as N, and write width(A) = max LoxxNN,,... NN41)., and dcpth(AV) = L.
2.2 Assumptions and setup
Let F X + y be the unknown operator we seek to learn and
: X - gdx, Dx Rd + X, Ey : y - R2 Dy Rdy + y
be approximate encoders and decoders for X' and D, respectively. As mentioned, we assume that these maps have already been learned, and focus the training of the DNN Ñ in L.3 Our main
3

---

results allow for arbitrary encoders and decoders (subject to the assumptions detailed below), and provide generalization bounds that are explicit in these terms: specifically, they depend on how well each encoder-decoder pair approximates the respective identity map on X' or y.
In order to formulate the precise notion holomorphy for the operator F, require the following. Let D = 1 1 and @ be the uniform probability measure on D. Given > 1, we define the Bernstein ellipse E(p) = {I + x 1/2 E C, 1 |x| S p} C C, and, for convenience, we let E(1) - [-1, Next, for p = (pi)ien 2 1, we define the Bernstein polyellipse as the product {()) {pi) E(22) X... C
Definition 2.1 (Holomorphic map). Let 0, E E (N) with b 2 0. A Banach-valued function f: - y (b. E) (lleee--hlomoon hholomorphic it is holomorphic in the region
=) - -U : P21 1, Σ ((ps + + 1/2 1) by I CC. b b= (by)seN- (2.2)
See, e.g., 17 85 As noted in 7 can, by rescaling b, assume that e 1. For convenience,
define the following unit ball, consisting of all such functions of norm at most one over R(b, 1):
H(b) (f D - V (b, 1)- h-hlomoorphic (z) 1 1, Vx E (R(b, 1)}-
(2.3)
Assumption 2.2. Let D = [-1, and e be the uniform probability measure on D.
(A.I) There is a measurable mapping L: X + R such that pushforward ; (2 is a quasi-uniform measure supported D and L) (aupp(n) X - (N) is Lipschitz with constant L, 2 0.
(A.II) The operator F has the form F = f 1, where E H(b) for some b (% (N) and 0 < p < 1. Idxx o Dx o εx is measurable (here Ldx : X + IRdx is the restriction of i.e., 6dx (X) = (<()))) and the pushforward == Extr is absolutely continuous with respect to 0-
(A.III) The map Ex ==idx
dxx
(A.IV) The maps Dy and Ey are linear and bounded.
Now let XI,...,X,, midd. and consider the training data
{(,, Y) C (X x y)"", where Y; = =(x,())) + E, E y
(2.4)
and E, E y represents noise. Let N be class of DNNs N RRdx - RRdy, and define
F P = Dy o N Ex, where Ñ E argmin 1 m |Y; Dy o N Ex
(2.5)
NEW m
2.3 Discussion of assumptions
We now discuss (A.I)(A.IV). In $6 we describe future work on relaxing these assumptions.
(A.I) is weak assumption. It asserts that there is Lipschitz map under which the pushforward of μ is a quasi-uniform measure supported in D. As we discuss in Example 2.3 this notably the case when is the law of some random field with affine parametrization involving bounded random variables- - a situation that occurs frequently in parametric and stochastic PDE problems. (A.II) describes the specific holomorphy of the operator F require E Eg (N), not just b E (N). It is known 7 that one cannot learn holomorphic functions (and hence operators) from finite data if b (P only. (A.III) is relatively weak assumption. In view of (A.I), we expect it to hold as long as the Dx o Ex Rs Ix sufficiently well. Finally, (A.IV) is a standard assumption, which holds for instance in the case of PCA-Net and DeepONet. The former also enforces the learned encoder Ex to be linear, which is not needed in our setup. Moreover, both approaches usually only deal with the case where both X' and y are Hilbert spaces.
Remark 2.4 for details. Note that
Example 2.3 (Parametric PDEs) A common operator learning problem involves learning the map F a E X + u(a) E y,, where u(a) satisfies F,u
(2.6)
and Fa specifies a certain PDE depending on parameter or function a. A standard example is the elliptic diffusion equation over domain Ω C R". Here a a(x: I ( =; X' is the diffusion coefficient and u = u(=;a) a) is the solution of the PDE
v (aVu(z;a) 9, Ω u(z;a) = 0, x E 02
(2.7)

---

Problems such as (2.6) are ubiquitous in scientific computing, with many applications in engineering. biology, physics, finance and beyond. In many such applications, it is common to assume that the measure jr on A' is the law of random field
a(æ) - a(=;)) - ao(+)) + Σ ca)
(2.8)
for functions ag, O; E X, where the x; are random variables and c; 2 0 are scalars that ensure that E L (92). Under some mild assumptions, (2.8) is then the Sarhumen-Loèye (KL) expansion of the measure See, e.g. [9] (see also [55] $3.5.1J) The 2; are typically independent. While in some settings, they may have infinite support, it is also common in practice to assume they range between finite maxima and minima. After rescaling, one may therefore assume that x E D = [-1.
p. The measure is then given as the pushforward μ = ote and f D + y is the parametric solution map f: D - u(; a(x)) E Y. If needed, the map can be defined in a number of different ways. Suppose, for instance, that X' is a Hilbert space, e.g., X' = L²()), and {0r is Riesz system (this holds, for instance, in the case of KL expansion, in which case { basis). Then fØr 1 has a unique biorthogonal dual Riesz system { We may therefore define a:0 > ((a 0o, (2)) i=1" Notice that is bounded linear map and F(X) f (X) f(x) for X a(x) ~ However, evaluating is often not required for computations (see $A.Ip
Problems of this type fits into our framework. Suppose that x (2..)),...)
00 is an orthonormal
This example considers an affine parametrization (2.8) inducing the measure μ., Note that other parametrizations can be considered. Common examples include the quadratic x(2;)) = au(2) +
(E (z)) and transfoadf a(2, x)) exp (>:=1 (,,;6((2)) parametrizations [17]
i=
Remark 2.4 (Holomorphy assumption) In the previous example, the operator F stems from the solution map f D + y' of a parametric PDE. The regularity of solution maps of parametric PDEs has been intensively studied, and it is known that many such maps are (b, é) e)-holomorphic (hence the resulting operator satisfies (A.II)). Consider, for instance, the affine diffusion problem (2.7)- (2.). Under a mild uniform ellipticity condition, the solution map of the standard weak form of the PDE f D + u(a(=:))) E H. (12) is (b,=)-bu -holomopphic with b (b.),- and b, c:|00x 1| (2)) See, e.g.. Prop. 4.91, as well as |B.3] Similar results are known for other parametric PDEs. This includes parabolic PDEs, various types of nonlinear, elliptic PDEs, PDEs over parametrized domains,
parametric hyperbolic problems and parametric control problems. See 19 or 3 Chpt. 4] for reviews.
3 Main results I: upper bounds
We now present our first two main results. In these results, given an optimization problem min, f(),,
we say that is a 7-approximate minimizer for some T 2 if f()) S min, [(1) +
Theorem 3.1 (Existence of good DNN architectures). Let m 2 3, 5 0, 0 e and
L L(m,et e) log" (m) log(1/e). Then there exists class N of hyperbolic tangent (tanh) and only with width(NN & (m/T.)15. depth(A) & log(m/L.), such that following holds. Suppose that Assumption 2.2 holds and
DNNs N ddx + Rd depending
(3.1)
dx 2 [m/L],
L. Dx Ex 1x S. Lm/L)-1/2
(3.2)
where Ix X > X is the identity map and c. > 0 is universal constant. Let XI,..., Xm lid. l and consider the noisy training data (2.4) with arbitrary noise E, E V. Then, with probability at
least 1 1- c, every T T-minimizer N of 2.5 where t 2 0 is arbitrary, yields an approximation F that satisfies
F - -Fllez(x)) S Expo.2 + Ex + Ey.2 + Eopt.2 + Esamp,
(3.3)
|F (x S Expp,oc Ex Ey,oo + Ex + Esamp,ocs
(3.4)
and, y is Hilbert space,
|| F Fll Flleg(x:0) S Expp.2 + Ex + Ex.2 + Fopt,2 + Esamp.2-
(3.5)
5

---

Here, the approximation error terms Eapp.q q q= 2, 00, are given by
Eapp.g = ay Cbb, p. E) (m/L))42-1//0111)
(3.6)
where ay = y Eylly bylly- C.) > 0 depends on b, and only and 0 = 0 if is Hilbert
space (as in 3.5 or 0 = 1/2 otherwise (as in (3.3 3.4
J. The other terms are given by
Ex,2 = ay L. v /L() IIx - Dx Ex Exllegussa
Ex,00 ay L. mm/L (Vm/L. IIx -Dx Ex (xa2Z + +IIx Dx o ExIl(x
Ey.2 |Ty - Dy o Ey E3 (orn/Ve
Eylle
Fyy 1 - Dy o Ey 19 (na) vm/L. T. Iay - Dy Eylle,,,,
(3.7)
where Iy: : + y is the identity map and, if El 2 Di=1 E
9= 2
E E /2y//// VL
Vm
q= ==2
Eopt mm//LT+2 +2 q 00
Esamp.n
(3.8)
q 00
(Proofs of this and all other theorems are in Gf the supplemental material.) This theorem shows that there is a family of tanh DNNs that yield provable bounds for learning holomorphic operators.
The error (.3) 3 (-.5) decomposes into an approximation error (3.6), which decays algebraically in the amount of training data m. Later, in Theorems 4.22 we show that these rates are optimal when )' is a Hilbert space, up to log factors. Next, are the encoding-decodii
errors (3.7). which depend on how well the approximate encoder-decoder pairs (Ex, Dx) and (Ey. Dy) approximate the identity maps on X' and )/, respectively. Observe that these terms are increasing in m for fixed encoders and decoders. Therefore, as one expects, the accuracy of the encoder-decoder approximations Dx o Ex = Ix and Dy o Ey R Iy should increase with increasing m to ensure decay to zero of the generalization error as m + CO. The specific terms (3.7) (for g = 2) are quite standard in operator learning. See, e.g., 53 55 When the encoders and decoders are computed via PCA, as in PCA-Net,
standard bounds can be derived for these terms 53 For similar analysis in the case of DeepONets,
see (55]. Finally, the error (3. 3.55 involves an optimization error Fopt. which primarily depends
on how accurately the optimization problem (255 is solved (i.e., the term T), and a sampling error Esamp, which depends the error in the training data 2.4).
Theorem 3.1 allows V be a Banach or a Hilbert space. Overall, when y only Banach space, we obtain a weaker L2 norm bound involving the Pettis norm (3.3) and, moreover, the approximation eтror Expo.y is worse by factor of 1/2 than when ) is Hilbert space. (Note that one can establish a bound for the Bochner noo-norm error when y is a Banach space via (3.4) and the inequality || [g(x,))> S ||- (x:3))- However, we do not believe the resulting bound is sharp). As we discuss in Remark D.18 the discrepancies between the two cases stem from the lack of an inner product structure and, in particular, the absence of Parseval's 's identity when y is a Banach space.
Observe that the DNN architecture in Theorem 3.1 is independent of the smoothness of the operator being learned. We term such an architecture problem agnostic. This theorem considers tanh activations only. However, as we discuss in (emark[D.1] other activations can be readily used instead. Other key facets of Theorem 3.T are the width and depth bounds (3.T). Qualitatively, these agree with empirical practice:
namely, better performing DNNs tend to be wider than they are deep, and relatively shallow DNNs perform well in practice (see [24 25 and references therein). We also see this later in $5)
On the other hand, the family A is not fully connected. As we describe in $C.2. while the weights on the final layer can be arbitrary real numbers, the weights and biases in the hidden layers come from a finite (but large) set: they are handcrafted to approximately emulate certain multivariate orthogonal polynomials. Since fulle-connected DNNs are typically used in practice, Theorem 3.1 is essentially a theoretical contribution. In our next result, we consider the more practical scenario of fully-connected DNNs.
Theorem 3.2 (Fully-connected DNN architectures are good). There are universal constants C1 C2 C32 C1 2 such that the following holds. Let m. 6, e and L be as in Theorem 3.1
dx 2 (m + log(1/e)),
L. I[I Dx ExIle3(x00) S <(()) (m + log(1/e)) -1/2 1/2 (3.9)

---

where c(0) > 0 depends on ó only, consider any class N' fflly DNNs satisfying (0o:"L+2) (dx, dy),
NI.-..,N44 2 02 (m + log(1/e)) (m/L)) I. 2 cg log (m/ L.).
(3.10)
Suppose that Assumption 2.2 holds and that the pushforward ş in (A.I) is the tensor-produce of univariate probability distribution with mean zero and variance w Z 1. Let Xi...,, ., <i.id. and consider
2.4) with arbitrary E, y. Then the following hold with probability least C.
(A) Uncountably many 'good' minimizers. The problem (25) has uncountably many minimizers that satisfy (3.3) with T 0 (3.5) with т 0 y is Hilbert space. They also satisfy (3.4) with 0 and the modified right-hand side /L app. + + + LLEE,, Eopt, + L
(B) Good minimizers are stable. Suppose that Ex (X; Bxx) and let To > O be arbitrary. Then there is neighbourhood of DNN parameters around the parameters of each minimizer in (A) for which the approximation corresponding to any parameters in this neigbourhood also satisfies the same bounds as in (A) with r To-
(C) Good minimizers can be far apart in parameter space. For sufficiently large m, there are at least (n// L)) 26m minimizers satisfying the bounds in (A) such that, for any two such minimizers,
their parameters satisfy ||0||| = ||0] and O 01 ž 1.
This theorem states that DL with fully-connected DNN architectures of sufficient width and depth (3.10) can succeed, since there are minimizers that yield the optimal bounds of Theorem 3.1 Such minimizers are uncountably many in number (A), stable to perturbations (B) and many of them (exponentially in m)) have sufficiently distinct and
parameters (C). This
'good' issue we discuss further in 6 but our numerical results in Suggeest that (approximate) minimizers obtained through training do, at least for the experiments considered, achieve the rates specified in Theorem 3.1
theorem does not imply that all minimizers
4 Main results II: lower bounds
We now show that the various approximation errors are nearly optimal. For this, we ignore the optimization and sampling errors and proceed as follows. Let C(X;; )") be the Banach space of continuous operators. We term an (adaptive) sampling map as any map
L: (:C(X,)) + y F L(F) = (F(X.))
(4.1)
where X1 E X X2 (x(1(X)) E X potentially depends the previous evaluation F(X1), X3 = X3( ((1)), (F))))()(X))))) F(x2)) E X. and so forth. Next, we term a reconstruction map as any map R: ym + )x) Given this, we let H(b,i) (F' = fol:fe H(bb) and define
(b) = inf sup L.R. FEH(b.)
|| - R C(P) 12300007
(4.2)
where the infimum is taken over all such and R. In other words, 6n (b) measures how well one can learn holomorphic operators using arbitrary training data and an arbitrary reconstruction procedure. Theorem 4.1 (Optimal L error rates). Suppose that (A.I) holds. Then, for any 0 < p < 1 there is constant e(p) > 0 such that the following hold.
(i) For each m E N. there a b E Eh (M,(N), 2 O. ||b] p.M = 1 such that mm)( 2 c(p) m 1/2 1/p
(ii) There is a b E ( 2 O, ||b|lp.. p.M = 1 such that (b) 2 c(p)
m. 1/2-1/v log2/P(2m)
Vm E N.
This theorem shows that the error Eapp. in Theorems 3.1 3.2 is optimal, up to log terms, whenever Y is a Hilbert space: there does not exist a reconstruction map surpasses the rate m112-11pp for learning holomorphic operators. Note that this result applies not only DL-based procedures, but any procedure that learns such operators from m samples. Another consequence of this result is that adaptive sampling, i.c., active learning, of benefit. As shown by Theorems 3.22 the optimal rate m 1/2-1/p can, up to log terms, be achieved through inactive learning, i.e., i.i.d. sampling from μ.
Theorem 4.1 considers L²-norm. For the L -nrm, we present a somewhat weaker result. Let
0m (b) = (Ex, Xmoop sup FEH(b.))
|| ((X,)) (x:))
(4.3)
7

---

where the infimum is taken over all reconstruction maps R (X x X)" L only.
Theorem 4.2 (Optimal L error rates). Suppose that (A.I) holds and that the pushforward ç the tensor-product of a univariate probability distribution with mean zero and variance w 2 1. Then, for any 0 < p there a constant c(p) > 0 such that the following hold.
(i) For each m E N, there is a b E Ex (N), b 2 0, [[b] P.M = such that mm)(b) 2 d(p
m 1-1
log(m)
(ii) There is a b E (N), b 0, ||6|| lbllp.. p.M = 1 such that mm (b) 2 c(p)
m m'-1/p Vm E N. log2/r41(m)) (2m3)
As with the previous theorem, this result asserts that the rate m m 111p is optimal in the L when y is a Hilbert space. However, it is strictly weaker than Theorem [4. as it only considers ii.dd random sampling from as opposed to arbitrary (adaptive) samples. Note that Theorem 4.1 is an extension of [ Thm. 4.4]. Theorem 4.2 is new, and of independent interest since it partially addresses an open problem of [7] about deriving lower bounds in the L -norm, opposed to just
the -nrm. See C.2.3 C.2.4 for more discussion.
5 Numerical experiments
We now present numerical results for DL. applied to various different parametric PDE problems, as in Example 2.3 For full description of our experimental setup, see $A B
Since the main objective of this work is examine the approximation error, we follow a standard setup and fix the encoder and decoders for each experiment, so that Ex and Dy in (I.3) do not change
for different choices of N. We also set up our experiments so that encoding-decoding 3.7 and sampling (3.8) errors are zero. We this standard way. To ensure that Ex.q = 0, we truncate the parametric expansions (2.8) after d terms (henceforth termed the parametric dimension) and define the encoder Ex accordingly. This means we effectively consider a parametric PDE depending on finitely-many parameters. We use Finite Element Methods (FEMs) to both solve the PDE (for generating training and testing data) and define the decoder Dy (see (A.2). To ensure that Ey. = 0, we compute errors with respect to the Bochner 1,2 (X: -orm where ) Dy((d is the FEM discretization of y In other words, we use the same FEM code to generate test data and compute the errors as we do to construct the operator approximation F. See $A.1 for further details.
The DNNs in our experiments are fully-connected and of the form (2.1. We denote by a L x N DNN a DNN Ñ with activation function width N and depth L. To solve (2.5) we Adam [47] with early stopping and an exponentially decaying learning rate. We train our DNN architectures for 60,000 epochs and results averaged
number of trials. See $A.2 for further details.
Parametric elliptic diffusion equation. Our first example is the parametric elliptic diffusion equation 2.7 This PDE arises in many scientific computing applications, such groundwater flow modelling, see, e.g., (95) We describe the full PDE and its FE discretization in $B.3] our experiments, we consider both affine [B.]) and log- oogtrrnnforrmed
(B.2) diffusion coefficients. The latter is particularly useful the groundwater flow problem as the permeability of various layers of sediment can vary on logarithmic scales. Differing from most prior work, consider novel mixed variational formulation [32] of (2.7). which has a number of key practical benefits (see $B.3.I). In this case, ) = (22 is Hilbert space. Fig. compares the error versus the amount of training data for various DNN architectures for learning the solution map of this PDE = 4 and d = 8 parametric dimensions with these two diffusion coefficients. We observe that architectures with the Exponential Linear Unit (ELU) or hyperbolic tangent (tanh) activation generally outperform similar architectures with the Rectified Linear Unit (ReLU) activation (as we diseuss in Remark D this difference is in agreement with our theoretical analysis). Overall, the best performing DNNs appear to roughly match the plotted rate m m- As we explain further in $B.3.2 this rate is precisely that predicted by our theory. In particular, the parametric solution map (recall Remark (.4) is (b,e) ---holomorphic with b E e (N) for any p < 2/3, giving an effective convergent rate 1/ 1/211/p that is arbitrarily close to m Another important fact that we observe is that despite the parametric dimension doubling from 4 to 8, there is little change in the error behaviour.
Parametric Seiie--ttooe---iinnaaa equations. We next consider the parametric Navier-Stokes- Brinkman (NSB) equations. See (B.4 and (B.14) for the full definition. Here the solution is pair
8

---

20
Figure 1: Elliiptic diffusion equation. Average relative (X:; 5) - norm error versus m for different DNNs approximating the solution operator for the elliptic diffusion equation (B.9. The first two plots use the affine coefficient a1,d
B.1 with d = 4, 8, respectively. The rest use the log transformed coefficient a2 B.2
Allar cud 1100.
Alla colf NE 1155..
Loght call NZI 1
Legft.coof ICD D
1353
12
Figure 2: NSB equations. Average relative L (x:: ) norm error versus m different DNNs approximating the velocity field u of the NSB problem in (B.14). See Fig. 7 for results for the pressure component p. The
diffusion coefficients a1,d; 22,d and d = 4,8 are as in Fig.
(u, where u is the velocity field and p is the pressure. These equations describe the dynamics of a viscous fluid flowing through porous media with random viscosity. See, e.g., 28 43 46 94]. We use mixed variational formulation (44] to discretize the PDE. This formulation is more sophisticated that standard variational formulations, but conveys various practical advantages. Unlike the previous example, it leads to y being either y = L²( for or y L2( for p. See $ for details. Fig. 2 compares a variety of DNN architectures for approximating the velocity field component in d 4 and d = 8 parametric dimensions. Here again we observe the ELU and tanh DNN architectures outperform similar sized ReLU architectures. We also observe a rate close to m Note that it is currently unknown whether this or the next example possess the same (b, hholoomory guarantee as that of the previous example. Yet we observe the same rate, and therefore conjecture that such property does indeed hold in these cases. Similar to the previous example, there is also no deterioration of the rate when moving from d = 4 to d 8.
Parametric stationary Boussinesq equation. Our final example is parametric stationary Boussi- nesq PDE. See $B.5 and (B.16) for the full definition. Here the solution is a triplet (u, (p, p). where u is the velocity field, şo is the temperature and p is the pressure of the solution. The Boussinesq model arises in a variety of engineering, fluid dynamics and natural convection problems where changes in temperature affect the velocity of a fluid [14 39 Similar to the previous example, we consider a fully mixed variational formulation (see IBS.II. D. which leads to y = L L (for u), y = L²(2) (for (p) y (1)) (for p). Fig. provides numerical results. Our observations the previous two examples, with the ELU and the smaller tanh networks being most often the best performers in this problem. Once more, the errors roughly correspond to the rate -1 and there is no deterioration with increasing d.
in line with
Conclusions and limitations
The purpose of this work was to derive near-optimal generalization bounds for learning certain classes of holomorphic operators that arise frequently in operator learning tasks involving PDEs. Complementing and extending previous works [26 RT
41
55 71 on the approximation of such
operators via DNNs, we showing sharp algebraic rates of convergence in m, thus confirming that

---

Figure 3: Boussinesq equation. Average relative (X:; norm error versus m for different DNNs approxi- mating the temperature of the Boussinesq problem in (B.16) (see for u and p). The diffusion coefficients d1,d, 02 and d 4, 8 in Fig. In this example, also consider an additional parametric dependence in the tensor K K describing the thermal conductivity of the fluid. See BB.S and (B.17).
such operators can be learned efficiently and without the curse of dimensionaliry. It is notable that the sizes of the various DNNs in Theorems 3.1 3.2 also do not succumb to the so-called curse of parametric complexity [54], since the width and depth bounds are at most algebraic in m.
We end by discussing a number of limitations. First, assumption (A.I) may not hold in some applications. The domain D can easily be replaced by bounded hyperrectangle through rescaling and the condition that be quasi-uniform relaxed to guasi-ultrapherrical (by considering ultraspherical polynomials). However, it is currently an open problem whether our results can be extended to the case where p is Gaussian, in which case ç would typically be a tensor-product Gaussian measure on RN and the relevant polynomials would be the Hermite polynomials. Second, the reader may have noticed that the encoder Ex defined in (A.III) and used construct the approximation (2.5) involves the pair (Ex, Dx) and the map xdx- This technical requirement - also found other theoretical works operator learning- needed to obtain encoding-decoding errors of the form Ex.q. q = 2, oC. is unknown whether it can be relaxed. It is also unknown whether the assumption on ç in (A.III) can be relaxed. We believe this can be done, at least if the L norm in (3.2) is replaced by the L -norm. Whether this is possible without modifying (3.2) is currently unknown.
Third, a limitation of Theorem 3.2 is that it only asserts that some minimizers are 'good', not all. Techniques from statistical learning theory can provide stronger bounds that hold for all minimizers. Yet, as noted in 1.2 these tools typically produce slower rates of decay in m. Overcoming this limitation e-g. by refining these tools for the holomorphic setting or showing that the 'good' minimizers can indeed be obtained via standard training- is topic of future work.
Finally, as noted, our theorems provided worse generalization bounds when y is Banach space than when y is a Hilbert space. Our numerical results in Figs. 3 suggest that this factor is an artefact of the proofs. Whether it can be removed is an interesting open problem.
10

---

Acknowledgments and Disclosure of Funding
BA acknowledges the support of the Natural Sciences and Engineering Research Council of Canada of Canada (NSERC) through grant RGPIN-202 DEPPN-2021-6116777 1675. ND acknowledges the support of Florida State University through the CRC 2022-2023 FYAP grant program. The authors would like thank Gregor Maier for helpful comments and feedback.
References
[1] B. Adcock and N. Dexter. The gap between theory and practice in function approximation with deep neural networks. SIAM J. Math. Data Sci., 3(2):624-655, 2021.
[2] Adcock, S. Brugiapaglia, N. Dexter, and S. Moraga. Deep neural networks are effective at learning high-dimensional Hilbert-valued functions from limited data. In J. Bruna, J. S. Hesthaven, and L. Zdeborová, editors, Proceedings of The Second Annual Conference on Mathematical and Scientific Machine Learning. volume 145 of Proc. Mach. Learn. Res. (PMLR), pages 1-36. PMLR, 2021.
[3] B. Adcock, S. Brugiapaglia, and C. G. Webster. Sparse Polynomial Approximation of High- Dimensional Functions. Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2022.
[4] B. Adcock, N. Dexter, and S. Moraga. Optimal approximation of dnfinite-dimensional holo- morphic functions II: recovery from i.i.d. pointwise samples. arXiv:2310. 1.X1::2310.66400 2023.
[5] B. Adcock, S. Brugiapaglia, N. Dexter, and S. Moraga. Near-optimal learning of Banach- valued, high-dimensional functions via deep neural networks. Neural Networks (in press), 2024.
[6] Adcock, S. Brugiapaglia, Dexter, and Moraga. Learning smooth functions in high dimensions: from sparse polynomials deep neural networks. In S. Mishra and A. Townsend, editors, Numerical Analysis Meets Machine Learning, volume 25 of Handbook of Numerical Analysis, pages 1-52. Flsevier, 2024.
[7] B. Adcock, N. Dexter, and S. Moraga. Optimal approximation of infiiie-diimesional holo- morphic functions. Calcolo, 61):::1, 2024.
[8] C. D. Aliprantis and K. C. Border. Infinite Dimensional Analysis: Hitchhiker's 's Guide. Springer Springer-Verlag, Berlin, Heidelberg, 3rd edition, 2006.
[9] S. Alnæs, J. Blechta, J. Hake, A. Johansson, B. Kehlet, A. Logg, C. Richardson, J. Ring, M. Rognes, and G. N. Wells. The FEniCS Project Version 1.5. Archive of Numerical Software, (100), 2015.
[10] Bhattacharya, B. Hosseini, N. B. Kovachki, and M. Stuart. Model reduction and neural networks for parametric PDEs. SMAI J. Comput. Math., 7:121-157, 2021.
[11] D. Boffi, F. Brezzi, and M. Fortin. Mixed Finite Element Methods and Applications. Springer, Berlin, Heidelberg, 1st edition, 2013.
[12] S. Brugiapaglia, S. Dirksen, H. C. Jung, and H. Rauhut. Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Appl. Comput. Harmon. Anal., 53: 231 231-269, 2021.
[13] S. Cai, Z. Wang, L. Lu, T. A. Zaki, and G. E. Karniadakis. DeepM&Mnet: Inferring the electroconvection multiphysics fields based on operator approximation by neural networks. J. Comput. Phys., 436:1 10296, 2021.
[14] C. Cao and J. Wu. Global regularity for the two-dimensional anisotropic Boussinesq equations with vertical dissipation. Arch. Rational Mech. Anal., 208:985-1000 1004, 2013.
[15] Q. Cao, S. Goswami, and G. E. Karniadakis. LNO: Laplace neural operator for solving differential equations. arXiv:2303.10528 2023.

---

[16] K. Chen, C. Wang, and H. Yang. Deep operator learning lessens the curse of dimensionality for pdes. vrXiv:2301.12277, 2023.
[17] A. Chkifa, A. Cohen, and C. Schwab. Breaking the curse of dimensionality in sparse polyno- mial approximation of parametric PDEs. Math. Pures Appl., 103(2):400-428, 2015.
[18] P. G. Ciarlet. The Finite Element Method for Elliptic Problems. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2002.
[19] A. Cohen and R. A. DeVore. Approximation of high-dimensional parametric PDEs, Acta Numer, 24:1-159, 2015.
[20] E. Colmenares, G. Gatiea, and S. Moraga. Banach spaces-based analysis of new fully-mixed finite element method for the Boussinesq problem. ESAIM Math. Model. Numer. Anal., 54(5):1525-1168 2020.
[21] D. Düng, V. K. Nguyen, and D. T. Pham. Deep ReLU neural network approximation in Bochner spaces and applications to parametric PDEs. J. Complexity, 79:101779, 2023.
[22] I. Danaila, R. Moglan, F. Hecht, and S. Le Masson. A newton method with adaptive finite elements for solving phase-change problems with natural convection. Comput. Phys., 274: 826-840, 2014.
[23] J. Daws and C. Webster. Analysis of deep neural networks with quasi-optimal polynomial approximation rates. 1rXiv: 2019.
[24] M. De Hoop, D. Z. Huang, E. Qian, and A. Stuart. The cost-accuracy trade-off in operator learning with neural networks. Mach. Learn. 1:299-341, 2022.
[25] T. De Ryck, S. Lanthaler, and S. Mishra. On the approximation of functions by tanh neural networks. Neural Networks, 13:733-750,, 2021.
[26] B. Deng, Y. Shin, L. Lu, Z. Zhang, and G. E. Karniadakis. Approximation rates of DeepONets for learning operators arising from advection-diffusion equations. Neural Networks, 153: 411 2022.
[27] N. Dexter, H. Tran, and C. Webster. A mixed & regularization approach for sparse simultaneous approximation of parameterized PDEs. ESAIM Math. Model. Numer. Anal., 53:2025-2045, 2019.
[28] Y. Dutil, D. R. Rousse, N. B. Salah, S. Lassue, and L. Zalewski. A review on phase-change materials: Mathematical modeling and simulations. Renew. Sustain. Energy Rev., 15(1): 112-130, 2011.
[29] S. Foucart and H. Rauhut. Mathematical Introduction to Compressive Sensing. Appl. Numer. Harmon. Anal. Birkhäuser, New York, NY, 2013.
[30] N. R. Franco and S. Brugiapaglia. A practical existence theorem for reduced order models based on convolutional autoencoders. T4t::2402200433 2024.
[31] N. R. Franco, S. Fresca, A. Manzoni, and P. Zunino. Approximation bounds for convolutional neural networks in operator learning. Neural Networks, 161:129-141, 2023.
[32] G. N. Gatica. Simple Introduction to the Mixed Finite Element Method. SpringerBrieffs Math. Springer, Cham, Switzerland, 2014.
[33] G. N. Gatica, R. Oyarzúa, R. Ruiz-Baier, and Y. D. Sobral. Banach spaces- spaces-based analysis of a fully-mixed finite element method for the steady-state model of fluidized beds. Comput, Math. Appl., 84:244-276, 2021.
[34] G. N. Gatica, N. Nuñez, and R. Ruiz-Baier. New non-augmented mixed finite element methods for the Sovier-Stokes-Brikkee equations using Banach spaces. Numer. Math., 31)4 343-373. 2022.
12

---

[35] S. Goswami, K. Kontolati, M. D. Shields, and G. E. Karniadakis. Deep transfer operator learning for partial differential equations under conditional shift. Nat. Mach. Intell., 4(12): 1155-1164, 2022.
[36] S. Goswami, D. S. Li, B. V. Rego, M. Latorre, J. D. Humphrey, and G. E. Kamiadakis. Neural operator learning of heterogeneous mechanobiological insults contributing to aortic aneurysms. J. R. Soc. Interface, 19(193):00220410, 2022.
[37] S. Goswami, A. D. Jagtap, H. Babaee, B. T. Susi, and G. E. Kariiadakis. Learning stiff chemical kinetics using extended deep neural operators. arXiv:2302. /2645, 2023.
[38] I. Gühhing and M. Raslan. Approximation rates for neural networks with encodable weights in smoothness spaces. Neural Networks, 134:107-130, 2021.
[39] Z. Guo, B. Shi, and C. Zheng. A coupled lattice BGK model for the Boussinesq equations. Int. J. Numer. Meth. Fluids, 39:325-342, 2002.
[40] Z. Hao, Z. Wang, H. Su, C. Ying, Dong. S. Liu, Cheng, J. Song, and Zhu. GNOT: General Neural Operator Transformer for Operator Learning. In International Conference on Muchine Learning, pages 12556-12569. PMLR, 2023.
[41] L.
Herrmann, C. Schwab, and J. Zech. Neural and spectral operator surrogates: unified construction and expression rate bounds. Adv. Comput. Math., 50:72, 2024.
[42] A. A. Howard, M. Perego, G. E. Karniadakis. and P. Stinis. Multifidelity deep operator networks for data-driven and physics-informed problems. Comput. Phys., 493: 12462, 2024.
[43] W. R. Hwang and S. G. Advani. Numerical simulations of permeability prediction of dual scale fibrous porous media. Phys. Fluids., 22:1 13101, 2010.
equations for
[44] T. Hytönen, van Neerven, M. Veraar, and Weis. Analysis Banach Spaces, Volume Martingales and Littlewood-Patd Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. Springer, Cham, 2016.
[45] Karniadakis, G. Kevrekidis, L. Lu, Perdikaris, S. Wang, and L.. Yang. Physics- informed machine learning. Nature Reviews Physics, 3(6):422 440, 2021.
[46] K. Khadra, P. Angot, S. Parneix, and J. P. Caltagirone. Fictitious domain approach for numerical modelling of Navier-Stokes equations. Int. Numer. Meth. Fluids, 34:651-684 2000.
[47] D. P. Kingma and J. Ba. Adam: a method for stochastic optimization. arXiv:1412.6980 2017.
[48] K. Kontolati, S. Goswami, M. D. Shields, and G. E. Karniadakis. On the influence of over- parameterization in manifold based surrogates and deep neural operators. J. Comput. Phys., 479:1 179:112008, 2023.
[49] S. Koric, A. Viswantah, D. W. Abueidda, N. A. Sobh, and K. Khan. Deep learning operator network for plastic deformation with variable loads and material properties. Eng. Comput., pages 1-13, 2023.
[50] N. Kovachki, S. Lanthaler, and S. Mishra. On universal approximation and error bounds for Fourier neural operators. J. Mach. Learn. Res., 2237:11333 2021.
[51] N. B. Kovachki, Z. Li, B. Liu, K. Azizzadenesheli, K. Bhattacharya, A. M. Stuart, and A. Anandkumar. Neural operator: learning maps between function spaces with applications to PDEs. J. Mach. Learn. Res., 24(89):1-97, 2023.
[52] N. B. Kovachki, S. Lanthaler, and A. M. Stuart. Operator learning: algorithms and analysis. In S. Mishra and A. Townsend, editors, Numerical Analysis Meets Machine Learning, volume 25 of Handbook of Numerical Analysis, pages 419-467. Elsevier, 2024.
[53] S. Lanthaler. Operator learning with PCA-Net: upper and lower complexity bounds. arXiv:2303.163177 2023.
13

---

[54] S. Lanthaler and A. M. Stuart. The parametric complexity of operator learning. 7rXi:2336.15924 2024.
[55] S. Lanthaler, S. Mishra, and G. E. Karniadakis. Error estimates for DeepONets: A deep learning framework in infinite dimensions. Trans. Math. Appl., 6(1):taa0001, 2022.
[56] S. Lanthaler, Z. Li, and A. M. Stuart. The nonlocal neural operator: universal approximation. 2XXi:2334.13222 2023.
[57] B. Li, S. Tang, and H. Yu. Better approximations of high dimensional smooth functions by deep neural networks with rectified power units. Commun. Comput. Phys., 27:379-411, 2020.
[58] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, Stuart, and A. Anand- kumar. Neural operator: graph kernel network for partial differential equations. In ICLR, 2020.
[59] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, A. Stuart, K. Bhattacharya, and A. Anandku- mar. Multipole graph neural operator for parametric partial differential equations. Advances in Neural Information Processing Systems, 33:6755 33:6755-6766, 2020.
[60] Z. Li, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandku- mar. Fourier neural operator for parametric partial differential equations. In ICLR, 2021.
[61] Z. Li, M. Liu-Schiaffini, N. Kovachki, K. Azizzadenesheli, B. Liu, K. Bhattacharya, A. Stuart, and A. Anandkumar. Learning chaotic dynamics in dissipative systems. Advances in Neural Information Processing Systems, 15:16768-1677 2022.
[62] Z. Li, N. B. Kovachki, C. Choy, B. Li, J. Kossaifi, S. Otta, M. A. Nabian, M. Stadler, C. Hundt, K. Azizzadenesheli, and A. Anandkumar. Geometry-informed neural operator for large-scale 3D PDEs. arXiv:2309.00550 2023.
[63] S. Liang and R. Srikant. Why deep neural networks for function approximation? In ICLR, 2017.
[64] C. Lin, Z. Li, Lu, S. Cai, M. Maxey, and G. E. Karniadakis. Operator learning for predicting multiscale bubble growth dynamics. Chem. Phys., 154(10), 2021.
[65] C. Lin, M. Maxey, Z. Li, and G. E. Karniadakis. A seamless multiscale operator neural network for inferring bubble dynamies. Fluid Mech., 929:A18, 2021.
[66] H. Liu, H. Yang, M. Chen, T. Zhao, and W. Liao. Deep nonparametric estimation of operators between infinite dimensional spaces. J. Mach. Learn. Res., 25:1-67, 2024.
[67] J. Lu, Shen, H. Yang, and Zhang. Deep network approximation for smooth functions. SIAM J. Math. Anal., 53(5):5465-5506, 2021.
[68] L. Lu, P. Jin, and G. Karniadakis. DeepONet: Learning nonlinear operators for iden- tifying differential equations based on the universal approximation theorem of operators. 2019.
[69] 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. Nat. Mach. Intell., (3):218-229, 2021.
[70] I. Lu, X. Meng, S. Cai, 7. Mao, S. Goswami, Z. Zhang, and G. E. Karniadakis. A comprehen- sive and fair comparison of two neural operators (with practical extensions) based on fair data. Comput. Methods Appl. Mech. Engrg.. 393: 14777, 2022.
[71] C. Marcati and C. Schwab. Exponential convergence of deep operator networks for elliptic partial differential equations. SIAM J. Numer. Anal., 6113):1513-1555 2023.
[72] Mhaskar. Neural networks for optimal approximation of smooth and analytic functions.
Neural Comput., 8(1):164-177, 1996.
14

---

[73] K. -Michalosska, S. Goswami, G. E. Karniadakis, and S. Riemer-Sorensen. Neural opera- tor learning for long-timg time integration in dynamical systems with recurrent neural networks. arXiv:2303.022453 2023.
[74] S. Moraga. Optimal and efficient algorithms for learning high-dimensional,, Banach-valued functions from limited samples. PhD thesis, Simon Fraser University, 2024.
[75] H. H. Nguyen and V. H. Vu. Normal vector of a random hyperplane. Int. Math. Res. Not. IMRN, 2018(6):1754 1778, 2018.
[76] F. Nobile, R. Tempone, and C. G. Webster. A sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal., 46(5):2309-22 2345, 2008.
[77] V. Oommen, K. Shukla, S. Goswami, R. Dingreville, and G. E. Karniadakis. Learning two- phase microstructure evolution using neural operators and autoencoder architectures. uрj Comput. Mater., 8(1):190, 2022.
[78] J. A. A. Opschoor and C. Schwab. Deep ReLU networks and high-order finite element methods II: Chebyshev emulation. arXiv:2310.07261, 2023.
[79] J. A. A. Opschoor, C. Schwab, and J. Zech. Exponential ReLU DNN expression of holomorphic maps in high dimension. Constr. Approx., 55(1):537-582, 2022.
[80] J. D. Osorio, Z. Wang, G. Karniadakis, S. Cai, C. Chryssostomiiiss M. Panwar, and R. Hov- sapian. Forecasting solar-thermal systems performance under transient operation using data-driven machine learning approach based on the deep operator network architecture. Energy Conversion and Management, 252: 1 15063, 2022.
[81] W. Peng, Z. Yuan, Z. Li, and J. Wang. Linear attention coupled fourier neural operator for simulation of dinee-dimensional turbulence. Physics of Fluids, 35(1), 2023.
[82] M. Pinkus. N-widths in Approximation Theory. Springer- Verlag, Berlin, 1968.
[83] B. Raonić, R. Molinaro, T. Rohner, S. Mishra, and E. de Bezenac. Convolutional neural operators. In ICLR, 2023.
[84] P. I. Renn, C. Wang, S. Lale, Z. Li, A. Anandkumar, and M. Gharib. Forecasting subcritical cylinder wakes with Fourier neural operators. arXiv:2301.0820 082290, 2023.
[85] C. Schwab and J. Zech. Deep learning in high dimension: neural network expression rates for generalized polynomial chaos expansions UQ Anal. Appl. (Singap.). 17(1):1-55, 2019.
[86] C. Schwab and J. Zech. Deep learning in high dimension: neural network expression rates for analytic functions in (RR,, na). SIAM/ASA J. Uncertain. Quantif., 11(1):199-22 2023,
[87] C. Schwab, A. Stein, and Zech. Deep operator network approximation rates for Lipschitz operators. 0rXiv:2307.009833 2023.
[88] M. Stoyanov. User manual: Tasmanian sparse grids. Technical Report ORNL/TM-20155599, Oak Ridge National Laboratory, One Bethel Valley Road, Oak Ridge, TN, 2015.
[89] M. Stoyanov, D. Lebrun-Grandie, J. Burkardt, and D. Munster. Tasmanian, 9 2013. URL https://github. wttp:l.ccooo///// Coom/ORRL/Tasaaiiaa
[90] M. K. Stoyanov and C. G. Webster. A dynamically adaptive sparse grid method for quasi- optimal interpolation of multidimensional functions. Comput. Math. Appl., 71(11):4499-2455 2016.
[91] A. M. Stuart. Inverse problems: a Bayesian perspective. Acta Numer. 19:451-559, 2010.
[92] S. Tang, B. Li, and Y. Haijun. ChebNet: efficient and stable constructions of deep neural networks with rectified power units via Chebyshev approximation. Commun. Math. Stat. (In press), 2024.
15

---

[93] T. Tripura and S. Chakraborty. Wavelet neural operator for solving parametric partial differen- tial equations in computational mechanics problems. Comput. Methods Appl. Mech. Engrg. 404:1 115783, 2023.
[94] S. Wang, A. Faghri, and T. L. Bergman. A comprehensive numerical model for melting with natural convection. Int. J. Heat Mass Transfer, 53(9-10):1196-22) 200, 2010.
[95] C. L. Winter and D. M. Tartakovsky. Groundwater flow heterogeneous composite aquifers. Water Resour. Res., 38(8), 2002.
[96] K. Wu, (LLear-RRosbbrry P. Chen, and O. Ghattas. Large-scale Bayesian optimal experimental design with derivative-informed projected neural network. J. Sci. Comput., 95 (I):30, 2023.
[97] Yarotsky. Error bounds for approximations with deep ReL.U networks. Neural Networks, 94:103-114, 2017.
[98] E. Yeung. S. Kundu, and N. Hodas. Learning deep neural network representations for Koopman operators of nonlinear dynamical systems. 2019 American Control Conference (ACC), pages
IEEE, 2019.
[99] M. Yin, E. Ban, B. V. Rego, E. Zhang. C. Cavinato, J. Humphrey, and G. Em Karniadakis. Simulating progressive intramural damage leading to aortic dissection using DeepONet: an operator-regression neural network. Journal of the Royal Society Interface, 19(187):00216670, 2022.
[100] M. Yin, E. Zhang, Y. Yu, and G. E. Karniadakis. Interfacing finite elements with deep neural operators for fast multiscale modeling of mechanics problems. Comput. Methods Appl. Mech. Engrg., 402: 15027, 2022.
[101] E. Zappala, A. H. d. O. Fonseca, A. H. Moberly, M. J. Higley, C. Abdallah, J. A. Cardin, and van Dijk. Neural integro-differrental equations. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 11104-11112, 2023.
[102] J. Zech. Sparse-grit grid approximation of high-dimensional parametric PDEs. PhD thesis, ETH Zurich, 2018.
[103] Z. Zhang, L. Wing Tat, and H. Schaeffer. Belnet: basis enhanced learning, mesh-free neural operator. Proc. Soc. A, 479(2276):2020044) 2023.
[104] M. Zhu, Zhang, A. Jiao, G. E. Karniadakis, and Lu. Reliable extrapolation of deep neural operators informed by physics or sparse observations. Comput. Methods Appl. Mech. Engrg., 412:1 16064, 2023.
[105] Z. Zou, X. Meng, A. F. Psaros, and G. E. Karniadakis. NeuralUQ: A comprehensive library for uncertainty quantification in neural differential equations and operators. SIAM Rev., 66(1): 161-190, 2024.
16

---

A Experimental setup
In this section, we describe our experimental setup.
A.1 Formulation of the learning problems
We first explain how all our experiments are formulated as operator learning problems. We do this in standard way, by first truncating the random field which generates the measure μa, and then using FEM to discretize the output space.
All our examples follow Example 2.3 and involve operators of the form 2.6 where Fa represents a different type of PDE each case (specifically, either an elliptic diffusion, Navier-Stokes, Stone---rinnnm or Boussinesq PDE). We consider both affine (2.8) and log-transformed parametrizations of the random field (x)) Thus, in general we write
a(x) = al;; = a.l()) + (ana)i()))
(A.1)
where g IR + R is (measurable) map. In the affine case g(t) 1. In the log-transformed case g(t) = exp(t).
As discussed, since the main objective of this work to examine the approximation error, we set up experiments that we fix a parametric dimension d and truncate the expansion in (A.I) after d terms, giving a map aa 1, 1j X and measure μ = astea, where ga the uniform probability measure [-1, We then define the operator F as F(aa(æ)) = f(Ø) = u(- (x))) where u(:aa is the solution of the PDE Fau 0.
errors are zero. We do this as follows. First,
In alignment with our theorems, we focus on the in-distribution performance of the learned approx- imation F. This means we define the encoder only on supp(u), as (x( æ when X = aa(œ) with æ E [-1, 1] As a result, the
error Ex.q in (377) satisfies Ex,q = 0.
To perform our simulations, we use FEMs to solve the PDE and discretize the output space y. Let ( c y/ be FEM basis and set dy = K. Then we define the decoder as
K
Dy RK +V, Dy(c)=
(A.2)
and set 5 = (K) as the discretization of y
With this in hand, now describe the simulation of training data in general terms. First, draw æ1,.... Fm Wiidd Qa- Then, for each training sample æs, we compute Y; by using the FEM to solve the PDE with parameter X, = az,).). Notice that Y, E y' in this setup.
We consider DNN architecture with input dimension no d and output dimension nL42 K. After training, evaluate the learned approximation F Dy N o εx over supp(n) as F(X)
Dy o No ( = Dy o Nx for X = aa(x) with æ E [-1, 1]d Finally, as noted, we us the same FEM discretization to generate testing data, which allows us measure the error with respect to the (2) This effectively means that the encoding-decodinng error Ey,, in (3.7) satisfies Ey.1 = 0 as well.
A.2 Computational setup for the numerical experiments
In this work, we investigate the trade-off between the accuracy of the learned operator and the number of samples m used training. Our methodology is summarized as follows.
Implementation. We use the open-source finite element library FEniCS, specifically version 2019. 1.0 19] and Google's TensorFlow version 2.12.0. More information about TemsorFlow can be found /https://wwwtt (ii) Hardware. We train the DNN models in single precision on the Digital Research Alliance of Canada's Cedar compute cluster (see https::/doce alliancecan Se/wikii/eeda. using
tensorflow.c oorg//
17

---

Intel Xenon Processor E5-2683 v4 CPUs with either 125GB or 250GB per node. The setup for each of our PDEs is as follows. For each experiment we consider training with 14 sets of points of size m E (10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500] and for 6 different architectures (4x 40 and 10 100 with ReI.U, ELU, and tanh activations) over two parametric dimensions (d = 4 and d = 8) and two coefficients (#1,d from (B.I) and 02,d from (..2), giving 336 DNNs to be trained for each trial. For the Poisson PDE and Gavier-Stokes Brink--Br PDEs we run 12 trials. For the Boussinesq PDE we run 8 trials due to the larger problem size. For the Poisson PDE, we allocate 336 nodes with 1 x 32 core CPUs running threads (totalling 1344 threads, 6.8 GB RAM per node) each running 3 trials, taking approximately 4 hours and 15 minutes to complete. For the Navier- Stoiker-toks---ee Brinkman PDE, we use the same setup allocating 9.88 GB RAM per node and the runs take approximately 9 hours and 13 minutes for each of the two components of the solution to complete. For the Boussinesq PDE, we allocate 336 nodes with X 32 core CPUs running 4 threads per node (totaling 1344 threads, 10 GB RAM per node) each running 2 trials, taking approximately 12 hours and 32 minutes for each of the 3 components to complete. Given this, the total time required to reproduce the results in parallel with the above setup is approximately 60 hours or 2.5 days. Results were stored locally on the cluster and the estimated total space used store the data for testing and training and results from computation approximately 50 GB. Trained models were not retained due to space limitations on the cluster.
(iii) Choice of architectures and initialization. Based on the strategies in (1, we fix the number of nodes per layer N and depth L such that the ratio 3 == L/N is , = 0.5. In addition, we initialize the weights and biases using the HeUnif form initializer from keras setting the seed to the trial number. We consider the Rectified Linear Unit (ReLU)
(z) == max (0, 2),
hyperbolic tangent (tanh)
e -
02(2)
e + 8-
or Exponential Linear Unit (ELU)
2> 0, a3(2) -ea-1 2 200
activation functions in our experiments.
(iv) Optimizers for training and parametrization. To train the DNNs, we use the Adam optimizer learning rate. We train our models for 60,000 epochs
47). incorporating an exponentially-dccan or until converging to a tolerance level of 6vll = 5 10-7 7 in single precision. In light of the nonmonotonic convergence behavior observed during the minimization of the nonconvex loss (see, e.g., 2), we implement early stopping. More precisely, we save the weights and biases of the partially trained network once the ratio between the current loss and the last checkpoint loss is reduced below 1/8, or the current weights and biases produce the best loss value observed in training. We then restore these weights after training only if the loss value of the current weights is larger than that of the saved checkpoint.
(v) Training data and design of experiments. First, we define a 'trial' as a complete training run for a DNN approximating specific functionn initialized as mentioned above. Following the setup of $A.I we run several trials solving the problem:
Given training data {X,, HO) C (X 1ym X; Midd n. Y; F(X.) + E, E
approximate F E L. ))
We generate the measurements Y; using mixed variational formulations of the parametric ellip- tic, Seeee-Sttoe---rinmaaa and Boussinesq PDEs discretized using FEniCS with input data X,. The noise F. E y encompasses the discretization errors from numerical solution. Further details of the diseretization can be found in $ Each of our architectures is trained across range of datasets with increasing sizes. This involves using set of training data consisting of values {X2, Y=)) where m denotes the size of the training data and belongs the set {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500}. After training we calculate the testing error for each trial and run statistics across all trials for each dataset.
(vi) Testing data and error metric. The testing data is generated similarly to the training data, obtaining solutions at different points X; E X for i = 1,..., Mestt However, the testing data
18

---

= is generated using deterministic high-order sparse grid collocation method [7].. In particular, we use sparse grid quadrature rules to compute approximations the Bochner norms
|| (ll0)))) ((II(()) 1/2
Monnrr
1/2
Σ
[IF
where μ autea is the pushforward measure defined in (A.1) and W,, 1, ...., Miest the quadrature weights. We use these approximations compute the relative E (x:3) error
Menss [[((X,) - 11 1/2
Test o
1/2
E 1I((3))133
We use a high order isotropic Clenshaw Curtis sparse grid quadrature rule to evaluate et as described in (2). This method shows superior convergence over Monte Carlo integration to evaluate the global Bochner error. The sparse grid rule gives Miest points at a level for d dimensions. We rely the TASMANIAN sparse grid toolkit [88190) for the generation of the isotropic rule study the generalization performance the DNN.
(vii) Visualization. The graphs in Figs. 1-3 show the geometric mean (the main curve) and plus/minus one (geometric) standard deviation (the shaded region). We use the geometric mean because our errors are plotted in logarithmic scale on the y-axis. See [3 Sec. A.1] for further discussion about this choice.
B Description of the parametric PDEs used in the numerical experiments and their discretization
In this section, we provide full details of the parametric PDEs considered in our numerical experiments. We also describe their variational formulations and numerical solution using FEM.
B.1 Parametric coefficients
We consider two parametric coefficients of the form (A.1) in our numerical experiments. Our first coefficient is
sin(1211)
01 (z, x)) 2.62
Zj
j3/2
Vz E
(B.1)
Ø=1
where 2j E [-1, Vj. Our second example involves a log-transformed coefficient, which is rescaling of an example from (76) of diffusion coefficient with one-dimensional (layered) spatial dependence given by
VTB
1/2
a2(2, x) exp
1+x1 +1
+
Σ
G0)(())os)
Vz E S
2
(15/2 mT)²
4 = (V7 exp
(B.2)
0,(2) = sin (li/2]=21/B)
if is even
cos (lj/2 222 /Bp) if is odd
where xy E [-1, 1j. Vj. Here let B. 1/8, and 3, max (1,23,). max
Be/Bp.
In both cases we consider truncation of the expansion after d terms, giving the map aj.d [-1, X, with = 1 corresponding to I) and j 2 corresponding to (B.2). Our input samples are then (X; a (a:)a(()))) C X' with æ; (-11, 1] drawn identically and independently from and j E (1, Note the Boussinesq problem we also consider an additional parametric dependence
in the tensor K describing the thermal conductivity of the fluid. See BB5 and (B.17).
19

---

B.2 Relevant spaces
We require several function space definitions for the development of the mixed variation formulations of the Poisson, Savier-Stokes Stre----r----nmmannn and Boussinesq PDEs. Let ? C R=, {2,3), be the physical domain with respect to the ebeeguee measure (to avoid confusion with the Bochner space 7.2, (Xx;))) We denote the standard Sobolev spaces W*I(SS) for E R and p > 1, and write H when 2 and 8 = k. Additionally, we consider the space of traces of functions in (92), denoted by (a))) and its dual, (=1/2(82) (see, e.g., 11 Sec. 1.2] for further details). We also define the following closed subspace of (
PDE. We write L"(Ω), < p S co, for the L space of scalar-valued functions
(9) Co (S)) 1H
1 denotes the closure of Co (S2) (i.e., the space C (S2) functions with compact support) with respect the norm || |1a,2, which, for any H (22), is given by
Here Co (9)
1/2 | == (1R, + [lol(a(0))) }
where |1/1, == |/e]l
For scalar functions and vector fields v, we use Vu and div(v) to denote their gradient and divergence, respectively. For tensor fields a and т, represented by (oug)ii=1 and (Tag))=) respectively, we define div((r) as the divergence operator div acting along the rows of or, and we define the trace and the tensor inner- inner-product
ir(o) = Σ oid and 7 a
T.j:
f,f=1
respectively. Furthermore, we introduce the notation L?( and IP((2) to represent the vectorial and tensorial counterparts of (S2),, respectively, and H (92) and H. for the vectorial and tensorial counterparts of H (S2), respectively. Keeping this in mind, we introduce the Banach spaces
H(div,; 52) = v E (2) div(o) L
(B.3)
[[(divg:))) = [ LL()) div(T) e L)(())
with norms
|1l| [||ll((dvvv;000 = ||]||>( + [
| [|| = [[]]] + ||div(T) [L(())
The cases of q 4/3 and g 2 appear in the mixed variational formulations of the considered PDEs, and for the latter we simply write H(div; (t).
Often, under certain conditions, such as incompressibility conditions 33 e2.(4.4) it is convenient to define variants of these spaces. For example, we define
( { E (2) ir(r) 0).
(B.4)
which represents the space of integrable functions with zero trace over Ω. Furthermore, given the decomposition (see, e.g., (32)
H = Hu(diva/s:: + RI,
(B.5)
we may also consider
Ho (div = { E [[(diva/3:0) (r(T) (((T)=00)
(B.6)
the space of elements in H H(div4//3; ?2) with mean trace. Finally, define
2 (?) {n L 1/" = 0),
(B.7)
and the space of (?) functions with zero integral over Ω
L2(0)) { ( (yEL((())
/ f v== y=0
(B.8)
20

---

B.3 The parametric diffusion equation
We now describe our first example, which the parametric elliptic diffusion equation. Let 52 R² be bounded Lipschitz domain, An be the boundary of J2 (22 and g E (a)) Given [-1, 1J", consider the PDE
div(a(x)VVu(z)) = f. u(x:) 9, an.
(B.9)
Here a(x) - ((=;)) ( =: is the parametric diffusion coefficient. The terms f and are parametric.
B.3.1 Mixed variational formulation
Our first step in precisely defining the problem is to identify sufficient conditions for the solution map + u((:) to be well-defined. To do this, we diverge from the standard variational formulation in- volving the space y = (22) (see Remark B.3 and instead consider mixed variational formulation of (B.9). Using a mixed formulation to study the solution of PDEs offers several benefits over the standard variational formulation. One key advantage is that allows us to introduce additional vari- ables that can be of physical interest. Additionally, mixed formulations can naturally accommodate different types of boundary conditions and introduce Dirichlet boundary conditions directly into the formulation rather than imposing them on the search space. For further details on mixed formulations, we refer to 32 and references within.
Assume that there exists .M 0 such that, for all [-,,
0 < S essinf=ena z, x)) =: (2) and amax (æ) == esssupzenazz.0 S M.
(B.10)
Then the problem can be recast as first-order system: given [-1,1] find (a, (x) H(div; x (?2 such that
( (x), b(T u(x)) G(T), Yr E H(dv,
(B.11)
b(o,v) F(o), e
Here d and b are the bilinear forms defined by
o T. In a(x)
/
da(m)(o,TT)
V(T,or H(div; x H(div; M),
b(T,0)= / div(T)u, V(T,e) E ((iv; L2())
and the functionals G (H(div; and J e (I.) are defined
((0) -00==-((u Sv. Ve E and G(T) = (T(T) n. n,.9)1/2.0. VT E H(div; (B.
For the experiments in this work, we consider !2 = (0, 1)2 and f f= 10. For the boundary condition, consider constant value u(2, x) 0.5 on the bottom of the boundary (0. {0), and zero boundary conditions on the remainder of the boundary.
B.3.2 Holomorphy assumption
Consider the affine parametrization
B.I. Setting M 2.7 and observing that
sin(T211)
Σ JEN
= 2.61238 = 2.62 -
(B.13)
j3/5
53/5 JeN
for some r < 0.00762, we deduce that (0. holds, which makes the mixed variational formulation B.11) well defined, i.e., for each E 1|0 there exists unique solution (ar (x) E H(div; ②2 x L22)).. Moreover, one can show that the parametric solution map (a, (w) is (b, holoomopphii for 0 < 0.00762 and where b = (bx) is given by
b, || //n ((((0)) --33 See 774 Prop. A.3.2].
21

---

08
6.23
0.2
6.0
0.7
4.1
0.60
40.0
0.55
Y 0.5
0.5 VAd
0.45
0.45
0.35
0.3
4.15
08
0.5
Figure 4: The domain f and FE mesh for the parametric diffusion equation.
00
06
04 00
07
84
00
06
49
06
0A
YAu
OSY
05Y
04
04
C4
04
03
03
DI
04.05
6.3
Figure 5: The solution u(x) of the parametric Poisson problem in (B.9) for given parameter x 01, with affine coefficient 01.d and d 4, using total of K 2622 DoF. The left plot shows the solution given by the FEM solver. The right plot show the ELU 4 x 40 DNN approximation after 60, 000 epochs of training with m = 500 sample points for training.
In view of this property, this example falls within theory. Note that b E 6g (N) for every p 2/3. Thus, we expect a theoretical rate of convergence with respect to the amount of training data that is arbitrarily close to m 1/2-3/2 m This holomorphy result applies to the affine diffusion (B. I).
not the log-tran traassfffrrrd diffusion B.2). However, expect that it is possible extend [74 Prop. A.3.2] to the latter case.
B.3.3 Finite element discretization
We so-called conforming Finite Element (FE) discretizations 118 Chp. 3]. Given number of Degrees of Freedom (DoF) K, this results in finite-dimensional spaces H C Hddiv; S2) and QK C (2)) Specifically, we consider a regular triangulation Tx of 52 made up of triangles of minimum diameter hiii 0.0844 and maximum diameter Ammux 0.1.46. This corresponds total number of DoF K = 2622. See Fig. for an illustration of the FE mesh.
Fig. 5 shows comparison between reference solution computed by the FEniCS FEM solver and the approximation obtained by an ELU x 40 DNN.
B.4 Parametric Savier--Stoke--rinnkee equations
We next consider a parametric model describing the dynamics of viscous fluid through porous media. Consider a bounded and Lipschitz physical domain TR2.. Given æ 1]1, we consider the incompressible nonlinear stationary Navier-Stokes, -rankkmmn (NSB) equations: find
22

---

u: [-,11 x2 - - 2 and p: [-1, x Ω + R such that
nn - -==ii((((())e((())) + (u(x) V)u(x) + Vp(x)= = div(u(x:)) = 0 in f2
in
(B.14)
up 0
on in on wall
u
(a(x) - p1) = 0
on Nontt
1 p =0 0,
where = Re- and Re is the Reynolds number, a(x:) = a(:; x) E X =- (2) and 1-1 x Ω + R+ the random viscosity of the fluid, 17 E R is the scaled inverse permeability of the porous media, is the velocity of the fluid, e(u) 1 (Vu + (Vu)*) ) is the symmetric part of the gradient, p is the pressure of the fluid and f f2 - R Is an external force independent of the parameters. Here, the fourth condition imposes zero normal Cauchy stress
Ve(x) plly 0
for the output boundary on addition, the incoppressibility of the fluid imposes the following compatibility condition on up:
J uD n 0 on Mi
The third condition also imposes a no-slip condition on the walls Dwall 34 (2.3).
B.4.1 Mixed variational formulation
The analysis of the detailed mixed formulation used for this problem in the nonparametric be found in [4 Over the last decade, many works have used a mixed formulation employing a Banach space framework, allowing one solve different PDEs in continuum mechanics in suitable Banach spaces. The advantage of this formulation is that no augmentation required, the spaces are simpler and closer the original model, and it allows to obtain more direct approximations of the variables of physical interest (34, Sec. 1].
Based on the analysis in [34], the mixed variational formulation of the parametric NSB equations in 14) becomes: given x E 1-,,1] find (u, t, ()), E (2)) L2()) x Hn (2) x
skow (22) such that
A L a (x)(((()))))) :8 8:0(()) - ()) 0,
2
t(x):T++ + / 7xx): :T + / ((z))div(r = (Tn, uploam.
(B.15)
1 8: 0
[ v.div(o(x))
m)(()))
[s-0.
for all (v, s, S, 8) E L*( x 1 (i) Ho a/1: 12) x L2 Now (I)). Numerically, the symwesymmetry of ry is imposed by searching for y E I. I?? and setting
- 0
Moreover, we impose the Neumann boundary condition via Nietsche method as in [34 See. 5.2]. Specifically, we add
"((a a + u & u)n) on) =
the second equation where > 1 is large constant (e.g., 10²). As usual in this formulation, the pressure E L?( can be computed according to the post-processing formula
p tr(o (u
23

---

01 02
02
00
32
68
00
0V
06
VAM 55
64
04
04
42
03
03
c2
42
9 on
KAMI DA
12-0z
C.000000 00000001200000000
35500
02 4.1
01 02 03 04 2.6400
011 02 0. 05 Co 08 09
07
47
05Y
02
42
01
AL
01
2. Hew
02 05 25
09 09
Figure 6: The solution (u, (a)) of the parametric NSB problem (B.14) for a given parameter x: = 01,0,0,0) with affine coefficient 01,d and d using total of 1464 DoF for and 244 DoF for p. The top row shows solution given by the FEM solver, and the bottom row shows the ELU 60, 000 epochs of training with m = 500 sample points. The left plots show the vector field u. The right plots show the points of highest pressure p.
DNN approximation after
Note that above we omitted the term x for simplicity.
In our experiments, we consider approximating solutions to the parametric NSB problem with 0.1, scaled inverse permeability of 17 10 + 2 22,, an external force f (0, 12) and random viscosity aj.d as in [.I] BB.2 with j {1.2].
We consider the unit square
(0, 1)2 as the domain, an inlet boundary 02 (0. 1) x {1), an outlet boundary 82ott {1} x (0, 1) and walls 02wall {0} (0. (0, 1) {0}. For simplicity, we use the same mesh as that the previous example. See Fig. 4 On the Neumann boundary dgout we consider zero normal Cauchy stress, Dirichlet condition un (.0622))-1(4 0.5)
22), 0) on 22n, and a no-slip velocity on dlwall-
Fig. provides comparison between reference solution of the vector field u and pressure computed by the FEniCS FEM solver and the approximation generated by ELU 4 40 DNN.
Remark B.1 (Other auxiliary variables) We report the performance the DNNs approximating (x) ( x I.2( Note that any solver based on the above formulation outputs several other variables, e.g., (t, a (x) ) e T x (ddviv4// 92) 2 2ee (1)). One could also approximate these auxiliary variables using DNNs. However, we restrict our experiments (u. p) as these are the primary variables of interest in the problem.
To conclude this discussion. in Fig. 7 we plot the numerical results for the approximation of the pressure p in the above problem. This complements Fig. which showed results for the velocity field u. We once more observe similar results: ELU and tanh DNNs outperform ReLU DNNs, the rate of convergence appears be close to O(m -1) and there is no degradation with increasing parametric dimension d.
B.5 Parametric stationary Boussinesq equation
To recap, in our first example, we considered a mixed formulation parametric diffusion equation that provably satisfies the (b, -holomooyyh assumption. Using this formulation, considered

---

Figure 7: The same Fig. except showing results for the pressure
problems with nonzero Dirichlet boundary conditions, whereas previous works 22 19 27 study the more restrictive case of homogeneous Dirichlet boundary conditions, where u E (S2). In our next example, we studied more complicated parametric PDE, namely, the parametric NSB equations. While this example currently lacks a holomorphy guarantee, we observe a convergence rate that aligns with what expect. We conjecture that the m rate holds both for this and for even more complicated problems. To illustrate this claim with an example, we now consider a parametric coupled partial differential equation in three dimensions (S2 R$) with two random coefficients affecting different parts of the coupled problem. The nonparametric version of this problem is based on (20).
Specifically, we consider the Boussinesq formulation in 20 that combines parametric incompress- ible Navier-Stokes equation with a parametric heat equation. The parametric dependence affects both equations. The Navier-Stokes equation affected by a parametric variable multiplying the demperaturee-deeeddett viscosity, and the equation for heat flow is affected directly by the thermal conductivity of the fluid. To be more precise, given æ E [-1, 1] our goal is to find the velocity
: 1, 52 -> IR2 pressure p: [-1, + R and temperature yp [-1, 1] x f - of fluid such that
div(2(())
(u(z) V)u(z) Vp(x) ((x)g in Ω div(u(x)) = in ?
(B.16)
vi(()())Vp()))) + u(x) v 0 in ?
u uD on 89,
6 PD 82,
p(x) 0.
92
Here g = (0, - a gravitational force and [k(::) = K(;a)) (l where K: [-1, x Ω 3x3 is parametric uniformly-posinn tensor describing the thermal conductivity of the fluid. is given explicitly by
sin (ZZa))
(exp(-21)
0
K(2,2)) = 1.89 +
TJ
exp(- -22)
0
Vz Es, (B.17)
j9/5
JEN
0
0
exp( -23)
for x 1]. The term / : R is a cemperature-dependeen viscosity given by ((p)
0.1 exp(-i) and the term a(x) a(-;x) E LO)), where [-1, 1]4 4 52 + R parametric
variable affecting the viscosity of the fluid. As in the previous example e(u) is the symmetric part of Vu. Note that in this case, have (a(æ), K(x)) X L - (S2 - (n).
B.5.1 Fully mixed variational formulation
The complete derivation of fully-mixed variational formulation for the non non-parametric Boussinesq equation in Banach spaces can be found in (20, Sec. 3.1]. To make the presentation simpler we rewrite it for the parametric case. Given x E [-1, [-1,1] 11d, find (u, t, ar p, (,) L ( x (2) x
25

---

Ho(diva/3: (2) x (2) x (2)) x H(diva/3:: S2) such that
-/o div(((())) + / t(xr)((x)) :
(0 =
12
(u) / o(x) i
2a(z) (x( (x) n
(aym
1 T:((a) + u(x:) div(T) (TV,UD)r
3 ddvv(o((:)) + [ 1 (x)e(()) . =
(B.18)
1
| o(x)
[(())((x)
5 p(x)u(x)
22
F f(. + ((z)ddv(FF) (F.U,4D)
tr(20r + u u)(x)) = 0,
for all (,,8,T,4,, F) E L(()) x (2) x (div x (2(2) x L2(2)) x H(diva//:
Here E L)(() can be recovered as
p tr( + 2cll u), where c 6 / tr(u @ @u).
(B.19)
As in the previous example, we omitted the term æ from this equation for simplicity. For further details on this formulation we refer to 20 and references within.
Given x E 1]4, we approximate the solution (u, p. (x) E (L+(2) x LQ(2) x (2()) of (B.18) by using DNNs and study the approximation capabilities samples m. As in the previous example (see Remark B.T we do not aim to approximate the other
increase the number of training
variables (t, r (ax) (22) Hl (div. 92) L (22) H(div4/3; S2).
In our experiments, consider the unit cube Ω (0, 1)a as the domain in R We consider nonzero boundary condition up = (1, 1, 0) on the bottom face of the cube Mesttoo = (0, 1) x (0, x (0), and zero the other faces. We set yD exp(4(-(2)
0.5)² (22 0.5) on Mobottom and zero otherwise. For simplicity, we consider the same parametric coefficients a1,d and a2, given by [B.1 and (B.2), respectively. See Fig. 8 for example of the solution (u, p. (p) (a:) for given a 11
To conclude this section, provide comparison of the performance of the DNN architectures in approximating the velocity field u and pressure for the Boussinesq PDE. This complements Fig. 3 which showed results for the temperature y. As with sp the convergence rate for agrees roughly with the rate m 11 and does not appear to deteriorate with the parametric dimension d. On the other hand, the convergence rate for the velocity field is somewhat slower.
C Overview of the proofs
In this section, first introduce additional notation that is needed for the proofs of the main results. We then give a brief overview of the proofs.
C.1
Additional notation
C.1.1 Lipschitz constants
Let (X, || (Ixx) and (J, Ily) be Banach spaces, G - y and B C X. We define the Lipschitz constant as T= Lip(G;; B, J/) as the smallest constant 2 such that
||G(X') G(X)Ily L|| XXlxx VX, e B.
26

---

06
06
06
20
20
0.4
04
04
Da
04
ZA
04
02
02
VAut
1
22
O2
01
10
02
00
92-0
1ex00
100
ce
7000z 06
12 100-00
Figure 8: The solution (u, p. (z) to the parametric Boussinesq problem in (.188) for given parameter (1, 0) with affine coefficient 61.d and d using total of 18, 480 DoF for a and 528 DoF for both y and p. The top row shows the solution given by the FEM solver and the bottom row shows the x 40 ELU-DNN approximation after 60, 000 epochs of training with m = 500 sample points. The left plots show streamlines of the vector field and their directions indicated with coloured arrows. The middle plots visualize the temperature distribution inside the cube using coloured spheres, with the hottest region at the centre of the cubc. The right plots illustrate the points highest pressure p.
SM0 10- CES
327
Figure 9: The Fig. where (22).
except showing results for the velocity field where (L)),, and pressure
C.1.2 Sequence spaces
We require some notation for sequences. Let (Z, || (lz) be a Banach space, d = NU foo} and write (vx) for an arbitrary multi-index in Ny. If A C Ng is a finite or countable set of multi-indices and < <p S oo we define the space E (A; 2) as the set of all Z-valued sequences e = (Cw)DEA for
which |cclpp <
where
(EVEn (1col12) 1/P
0 < < 0o, p= = 0o.
||||| p:
suppes l|cullz
27

---

When (2, [1z) = -RR,1- 1.1.). )), we just write (A) and || Ilp- We also define the following:
|| | = sup 5* eBEB))
(c) Ve E (A(A;
where =²(c) (=*(cc))uEA E R for e = (Co)NES. Notice that || I l|||lp:2
Given a sequence e = (Gy)vEA, we write
supp(c) (UEA # CA.
For d E N (2o), we write ej. = 1,...,,, d, for the canonical basis vectors in Rd We also write 0 for the multi-index of zeros and 1 for the multi-inder of ones. Finally, for multi-indice (1))k=1 and J (u=) we write v 2 mean v 2 Mks Vk and likewise for v > μ.
C.1.3 Weights and weighted sequence spaces
Let d E NU (oo), S Ný and (Wy)PEA 2 0 be a sequence of nonnegative weights. We define the weighted cardinality of set S [ A as
S Σ w
(C.1)
Given sequence (Cx) (Cy)EE write
||llo, = (supp(c))w-
Next, for Banach space (z, |l [ll)) and 0 < < 2. we define the weighted L (A; 2) space as the space of Z-valued sequences (Cr)vEA for which |c|| cclp, < cc, where
1/p
||c|p
Σ 2 Pllc WEA
Notice that || |/2.2 coincides with the unweighted norm ||
1|2,2.
C.1.4 Legendre polynomials
We write {Px JnENo for the classical Legendre polynomials on [-1, with normalization (1) = 1. Since 1" (x) dr (n 1/2)-3 we define the orthonormal (with respect the uniform probability measure) Legendre polynomials as
(x)xx) 2n + 1P,(s), x (-1,1, n E No-
Let D = 1-,, before,
F= = (4:) E No [supp()) < cc}
be the set of multi-ine inttii-inicess with finitely-man many nonzero terms and define the multivariate Legendre polynomials
V (x)
II Meo (v:)
(xx), Vo D, (v:) F.F (εsupp(w)
II
Here, the second equality follows from the fact that tho = Then it known that the set
{V LD)
(C.2)
constitutes orthonormal basis for I2((D) 19 $3). For later use, also define the sequences
(uy)vEF, where u |Wullz<(D)
II KEN
2uk II, VVEF
(C.3)
and
v (Nw)eer, where iu u 5+5 Vv F. Here & 2 0 will be chosen later in the proof.
(C.4)
28

---

C.1.5 Miscellaneous
Given an optimization problem min; f(t), we say that is a -4prr--ppox minimizer for some 2 and 2 0 if f() I o² min; f(t) + (In the main paper, we consider only a = 1, but for the proofs is useful allow
Finally, for convenience, given XI,..., Xm E X, we define the semi-norm
G disc.j
|G(X)||
of an operator G + y and
1
l || = Ilg o Ex Exilldisc,n
l Ex(x:))
of function IR + V. Here, as in (A.III), č denotes the pushforward measure #x
C.2 Overview of the proofs
C.2.1 Theorem
3.
Theorems 3.1 3.2 are based on polynomials, and specifically, procedures for learning efficient
Legendre polynomial approximations to holomorphic operators. As observed, these results are based on recent work on learning holomorphic, Banach-valued functions 2 5 below.
See also Remark
The proof of Theorem 3.1 involves three mains steps.
(a) Formulation ($ D.1 and analysis ( D.4 of suitable polynomial learning procedure.
(b) Construction of family of DNNs that approximately emulates the Legendre polynomials ($D.5).
(c) Analysis of the corresponding training problem (2.5) ($D.6 D.8.
Since our goal in this work is 'agnostic' DNN architectures (i.e., independent of the smoothness of the underlying operator), in step (a) we first define a nonlinear set (D.2) spanned by Legendre polynomials with nonzero indices in certain sets of bounded weighted cardinality. This is effectively a form of sparse polynomial approximation, and the analysis of the resulting learning procedure (D.3) relies heavily techniques from compressed sensing. In order to bound the encoding -eclodnng error, we also require several results on Lipschitz continuity (Lemma D.2) and norm equivalences (Lemma D.4 for multivariate polynomials.
Step (b) relies on what have now become fairly standard results DNN approximation theory: namely, the approximate emulation of orthogonal polynomials via DNNs of given width and depth. present such a result Lemma D.9 then use this to define the DNN family N in (D.19).
We then analyze the DNN training problem 2.5) in step (c). Using the emulation result of step (b), we first show that any approximate minimizer N of (2.5) yields a polynomial that is also an approximate minimizer of the polynomial training problem (D.3) (Lemma D.12 We may then apply the results shown in Step (a) to prove generalization bound (Theorem D.13) Up this point, we have not used the holomorphy assumption. We now use this assumption bound the various best polynomial approximation errors that arise in the previouslydderive generalization bound (.7). Finally, in <D.8 we put all these estimates together to complete the proof.
Remark C.1 Theorem 3.1 is a generalization and improvement of 5 Thms. 4.1 & 4.2], which deals with the case of learning Banach-valued functions rather than operators. Specifically, the setting of [5] can be considered a special case of this paper where X' (N) and the encoding error Σx,, =
Moreover, Theorem 3.1 improves the main results of [5] in three key ways. First, the the DNN architectures bounds are much narrower: width(A) X (m/ (n/LL)2+ versus width(AV S (m+ the latter. Second, Theorem 3.1 considers standard training. i.e., (2-loss minimization, whereas [5) Thms. 4.1 & 4.2] requires regularization. Third, for Banach spaces, the error decay rate with respect
29

---

to m is roughly doubled: Eapp.2 = O0 in Theorem 3.1 versus Om (m/ 1/211111))) in S Thm.
4.1]. Finally, Theorem 3.1 also provides bounds in the D -norm, whereas the results in [ only consider the Li norm.
C.2.2 Theorem
The proof of Theorem 3.2 relies of three key steps.
(a) Using a minimizer of the polynomial training problem (D3) to construct family of minimizers of the DNN training problem (2.5).
(b) Analysis of the corresponding minimizers using the periiossly-deriven bound for polynomial
minimizers.
(c) Using the Lipschitz continuity of DNNs to show stability of the DNN minimizer and permutation argument to show the existence of many parameters that lead to equally 'good' minimizers.
Given any minimizer the polynomial training problem (D.3), with the desired generalization bound. Unfortunately, this will generally not be minimizer of (25) To achieve the aims step (a) we proceed as follows. First, we note that DNN will be a minimizer if the corresponding approximation satisfies F(X;) = Yú where Y, are the closest points to the Y; from y Dy (IRd)) ). To achieve this, we take the existing DNN then add on suitable number of additional terms corresponding to the first > m order-one Legendre polynomials (SE.I). We show that by doing this, we can construct a DNN for which (X,,) = (Lemma E.1
straightforward to define a DNN
In Step (b), we first bound this DNN minimizer in terms of the polynomial minimizer plus the contributions these additional terms (Lemma E.2). The latter involves the minimal singular value of a certain x r matrix B, which is the matrix of the linear system that enforces the condition F(X,) Y, We bound this minimal singular value in $E.3
We then use this to complete the proof of part (A) of Theorem 3.2 complete step (c) to establish parts (B) and (C).
SE.4 In this section, we also
Remark C.2 Like Theorem 3.1 Theorem 3.2 also relies ideas from [5]. However, [5] does not address fully-connected DNN architectures. To address this challenge, the proof of Theorem 3.2 involves the technical construction described above.
C.2.3 Theorem
Theorems 4.1 is based on 7 Thm. 4.4]. The basic idea is to consider a family affine, holomorphic This allows us to lower bound the quantity Om (b) by the so-called Gelfand width (TT) of certain weighted unit ball in a finite-dimensional space. Bounds for such Gelfand widths are known, and this allows to derive the corresponding result. The main difference between this and 7 Thm. 4.4] is the setup leading to the construction in (F4).
operators (.4
C.2.4 Theorem
Theorems 4.2 employs similar ideas, but in a more technical manner. We consider family of linear, holomorphic operators (G.2). which involves sum over groups of m coefficients. We restrict to coefficients that lie in the null space of the corresponding sampling operator. Then, through series of inequalities, we can lower bound fm (b) by sum over terms, each involving the el ---norms of certain vectors in the null space of the matrix of the corresponding sampling operator (G.3). This matrix is subgaussian random matrix. We now use technical estimate from (75) for vectors in the null space of subgaussian random matrices, which shows that they cannot 'spiky". Applying this and series of further inequalities yields the result.
D Proof of Theorem 3.1
D.1 Formulation of approximate polynomial training problem
Let C F with supp(v) S (1,...,dx] Yu E A, and write N = =|A]. Let and define the set S SA. ( A S|| < k).
(D.1)
30

---

Both A and & will be chosen later in the proof. For any Banach space (2, |l l| define the space
Ps.2 =
Evwi: cu e 2,5 2.S
(D.2)
WES
Then, given the training data 2.4 consider the problem
min P
1
Σ It, - Pox-poExXXiIl i=1
(D.3)
where y = (Rdy). Here and throughout the proofs, we slightly abuse notation: the polynomial p: IR + R. whereas Ex has codomain Rdx, However, by construction, is independent of all function Rdx - IR. This aside, if is an
but the first dx variables, Hence we may consider approximate minimizer of (D3)). then we define the approximation to F as
Fz P po Ex
(D.4)
Notice that p o Ex = Dy Po Ex. where P Fd + Rdy is vector-valued polynomial, since, by (A.IV), the map Dy is linear. The idea exploited in this proof is to construct a class of DNNs V such that (i) all such polynomials P are approximated by members of N and (ii) the polynomial training problem (D.3) is approximated by the DNN training problem 2.5). The first step in this analysis is therefore to analyze the polynomial training problem (D.3)
D.2 Supporting lemmas
We require several lemmas. The first relates the -. nnrm of a polynomial to its Pettis n Lemma D.1 (Nikolskii inequality for polynomials). Let (2, ll l12) be any Banach space and p =Eves Cy vn for some finite set C F, where cu E Then
I1ll) v1s (0SuullPlllz((0022)
Proof. By definition
sup 12l1,,(D122 = |||||| (1P1) ='B((z))
||2 (p)ill)
Fix x" E B(Z*) and write 2" (p) = Eves 2" (c.) By the triangle inequality and the definition of the weights CC.)) we have
||= (p)llag(p) &
Σ [lw((l)llMlllrrr = Σ upl (cx)).
wES
WES
We now apply the Cauchy-Schwarz inequality,
CC.I and Parseval's 's identity to get
||2 (+)llll)))))) & VIST.,
1 (c,)))
PES
Since = was arbitrary, we deduce that
[1:l V/s
|| |=*(W]ll23()) [Swwllllllegcp.a
sup eB
required.
Next, we require the following bound on the Lipschitz constant of a multivariate polynomial. Lemma D.2 (Lipsehitz. continuity for polynomials). Let (Z, || 2|] be any Banach space and suppose that p = Eves Cu Ni, for some finite S C F, where Cy 2. Then satisfies
1 Lip(p; B (N), < 2 VIST . [Il.)
where (N) (x E N ||0||| - 1} is the unit ball of e (N).
31

---

Proof. Fix 2" E B(2)) and let p= 2p) = Eves= 2" =: Eves EN Vu be the correspond- ing scalar-valued polynomial. Let x, x' E D. Then the mean value theorem gives that
Op
f(x') - -((x)) Σ (1)
(tæ + (1 (1-t)a²)
Or,
for some $ L & 1. Since B (N) = D, this and the fact that is convex give that
0p
[0xx) - [()) s || al100
Σ
(D.55
dr:
(P)
We now consider the terms in the sum separately. Using the definition of the Legendre polynomials (see SC.1.4. we have
Op
Σ
ue Pi, (2x4
II P,g(tr))
WES
jØi
The unnormalized Legendre polynomials satisy 1 (1(
|| (1 and n(n + 1)/2
(1( = || L=((-11)) Hence
Op 0x:
(D)
WES
We deduce that
Pp
Σ
uu
Σ
vilu + 1)/2.
(D)
WES
i=1
Now, by definition of the weights the and U2 (see
C..3 and C.4
we have
(ni + 1) < II
(2ug
+ 1) = "
JEN
and
< II
(2vg + 1) = nzz
1=1
jEN
Hence
up 1) S u S vv.
Here we also used the fact that u Parseval's 's identity to get
We now apply this, the Cauchy- inequality and
ap
$ 1 | L3 S/
Σ
0x;
2
(D)
Substituting this into D.5 now gives
[ī(x') x(x) 2 | v // allooo
We now recall that 5 = 2" (p) and x B(z*) was arbitrary to get
Ilp(x') - p(=)l12 (p(z')-p(z)l2=
sup
(p'(p(z) - p(z))
EEB(Z2)
s 2 EE(E))
sup
||>0(p) (p))Lg(()) v [S)olla x11.0
(llllggD: /S x'' x: a:lbact
required.
32

---

We now show that this result can be used to imply norn equivalence for polynomials. For this we first require the following lemma. Note that in this and subsequent results, we abuse notation and write č for both the measure on [11.1 defined in (A.III) and the measure on D [-1, 1, 1 defined by tensoring this measure (corresponding the first dx variables Fi,...,Idy. with the uniform measure on DV 1]xx (corresponding to the remaining variables Idx+1, Tdx+
Lemma D.3 (Closeness of I,2 norms). Let (2, l1 be any Banach space, Ç be the measure defined in (A.I) and & be the measure defined in (A.III). Suppose that E (D; 2) is Lipschitz continuous with constant = Lip(f: Bx 2) < oo and that f depends only on its first dx variables. Then
LD, 2) and
IQ( - 8 s IIIf (2(D.2) S I +
where
8 = L. -1ldx - ldx Dx o Ex Ingex
Proof. Fix B(z)), let g 2f) LD( and set
||9ll1g(1) b= +=119111((D)-
Notice that
(g(ar) g(x')l S ||= ([(=) - f(x')) Il| S T1|l a'looo> Vx, x' E B (N)..
Now, with slight abuse of notation, g(u(X)) = g(1xx (X)) due to the assumption on f. Therefore, using this and the Cauchy-
Cauchy-Schwarz Schwarz inequality,
a² - 62 = I (olueN o Dx o Ex())) - (g(4ax (X))) du(X)
$ J [Ixxx() ldx Dx (x) (l9(1ax (X))I + Io(1ax o Dx o Exi1) dp(x)
< Llldax ldx o Dx Ex (x( (a + b).
We deduce that a a b < 8. Since 2n was arbitrary, we get
II (0))))))) sup E=B((2)
|| [()(()))))))) S sup =*B((2))
|| [1=((())))())) + + =11flll + 6
which gives the upper bound. The same argument applied to 12 12- a² also gives the lower bound.
Lemma D.4 (Norm equivalences for polynomials). Let (2, 11-111 2 be any Banach space, s be the measure defined in (A.I), & be the measure defined in (A.III) and S C F with supp(v) E (1..... .l....,dhh..
Vv S. Suppose that
[1xxx ldx Dx Ex Exl1 Sc, S
(D.6)
for some sufficiently small universal constant <> 0. Then the norm equivalence
IIlll S |Illll & |Ile|l
holds for all p == Eves Co Vr, where Gp E
Proof. Combining Lemmas D.2 and D.3 see that
I plll) 8 < || |1ll & |Iel ||ll +
where 5 = 1 lellllll1 l1llllll.... v [STwllca uxx o Dx (xlleg(x))=0)) S ellpll / By (A.I),
there constants 2 02 such that
ea allle|llg/D.2 & [l I colllll 13(0.2))
We now take c1/2.
33

---

D.3 Analysis of D.3)
We now analyze D.3 Our analysis relies on the following result, which shows an error bound subject to certain discrete metric inequality (D.7).
Lemma D.5 (Discrete metric inequality implies error bounds). Let y (R.s)) be bounded linear operator and = = 11 y-y- Suppose that
1p dilsss..s 2 a max (Ilp 4 <1ll llp bll-ollggDD.)) Vpge (D.7)
for some O. Then, for any F' 1 (2: p P ss and q Ps.y,, we have
|| - p Ex (0x11g((x0) 1 || Q (バ +a +a- Q
+ Ex 13(x2))
and
- PP-ppExllup(xa))
S S F - F bg (x:3) + v 22//ollp - Q gllaise,s
+ TellF q 8x (p
Proof. By the triangle inequality and properties of Q, have
|| po Ex -xxxxllg(x))
< || - Q F..Fllllzz ( + lp Ex - Q Qog &x 12(0 + I
oo 1lo Ex
S F| Q Q Flll ((ll1g(x:>>) + o - o &x (g( + Toll F - qo -
Now, since p, Q o o P P..j. the second term can be bounded by
||l Ex Q Q o &x ([(())) = - 2 Dolll Sa aa-1pp Q dlsc.
(D.8)
This yields the first result. For the second result, we once more write
| - po Ex ExIl I || Q F Pllla -o
+ mg
F o Ex (x:0)
For the second term, we use (A.III) to write
|lp o Ex - Q o q Ex 1g (x:y) = -lp Q ( S 1p - -loll (Day)
Notice that @ is a polynomial supported in a set S with 1S - 2k. We now apply Lemma D.I and (D.7) obtain
||pp o Ex Qogo
Exllag o
I <22lllp - Q o @ogll I /kk/allpp 2 Allaaiees. (D.9)
This gives the result.
Theorem D.6 (Error bound for polynomial minimizers). Let Q: y + +5= DD be a bounded linear operator, Te = I and suppose that D.7 holds. Let F be as in D.4 for some
(a, -apppprxiimatee minimizer á of D.3). Then
a+1 || 1 Qo F F'lldisc,
|| F ( 5 ||
2o F ()]))(())0)
a
+ ++1 || q Ex lldiiss...)
+ + [|
- q o ExIlla((aa0
a
I 0+1
E E1
a a/m
34

---

and
V2h(o + 1)
|F - Fll (x s S - fl1g +
|| Qo o F F'lliisc.
v2k(o - 12
+ n
|P go Ex Ex1lep(x:31
|| Ex lldiioo
2kt
V2k + 1)
+
a
aym
for all q E Ps.ys where E (F E ym the (Banach-valuedd) vector of noise terms.
Proof. We apply the previous lemma with p p. This gives
F - Flll 11113()))
$ F F Q F 1,((0:1 + - Q
+ + qo o e 12(2:3)
(D.10)
|| F (1:3)(1)))
- | - Q (x + V2k/allp- Q Q glldise,
+ + F q Ex. Lx
Consider the second term. We have
|| Q dll. Ill Ex gogor &x
Ex di S || F- Qog Exlllxl + || po Exilddis,,n
Consider the second term of this expression. By the triangle inequality and the facts that p is a (o, r) mimimiizee and is feasible, obtain
po Ex didisss
Σ
v - po Ex + vm
m
m
S
||s - 2oqoExli +
Ellay
m
vm
1=1
[ - Q Ex Ilaise, +
E 22
m
Therefore, we get
| Q Allaises S + 1)]l Qoq Ex Exliiisc, + + mm
Ellzy
We now estimate the first term in this expression as follows:
Q oogo Ex lilassc
S F Q Flll disc,, +
g o Exildisc.
| Q F dis. + Tell qo Ex disc.
Therefore, we conclude that
| Q gllaises (a+1)|] Q Flll ii + qo Ex Ilaiss, + o + 1
E 1
vm
Combining this with (D.10) now gives the result.
D.4 Ensuring D.7 holds with high probability
For the proof of the next lemma and subsequent steps of the proof, we let A {ui,... UN) and define the matrix
Ue, (Xx))
m.N
A =
E m
Vm
ij=1
35

---

Lemma D.7. Let 0 <
0 and suppose that
m m00 0 6- k (log(cN) log2(k/ + log(2/c))
(D.11)
for some universal constant Co > 0. Ler T = fcr R ||c|2 = 1, ||cllo, I k) and
0+ = sup E Ac 2 c 0_ inf El || 123 c CETJ. 7
Then
|| 2 (0- (1+ 04) || VC V ||cllo.v I
with probability at least where ej > 0 a universal constant.
Proof. The proof is based on 12 Thm. 2.13]. Since ||c||,, Vilello.ullel12 S Vk, we see that
T fefeER* ||c|l1,0 $ Vk..
Define the random vector X E RN by X = (Un, (Ex(((()) for X ~ μ. Observe that Kx,,;))
e;)l = (Ex(()) up: S vp:
almost surely, by (A.III) and the definition of the weights. Therefore, by [2 Thm. 2.13], if
co 0- k log(eN)) (k:(())),
(D.12)
it holds that
1 Σ
(c. X,) - x)12 S sa0 1 1+ sup (c, xy(²) cET
sup cET
m7
1=1
with probability least observe that
2 2exp(=xpppe 22x Here co, C1, 02 are universal constants. Now
m
Kc, x,) x ||c|
El = B(IAcl))
m7
Therefore, have shown that
||al 2 -- 04)0
Vc e T,
with probability at least 2 exp( (-20p 222mmm m/ m/k), provided m satisfies D.12p. To conclude the result, we observe that (D.11) implies (D.12 up to possible change in the universal constant Cp. Moreover, also implies that
2 pexp(-c20²mg 6.
Hence we obtain the result.
Lemma D.8. There exist universal constants co, C2 such that the following holds. Suppose that
m 2 co k (log(eN) log log) + log(2/e))
(D.13)
and
Vk: F1-l ldx o Dx o Exll (10) S C1.
(D.14)
Then D.7 holds with probability least and constant 2 Cz.
Proof. We shall apply the previous lemma with & replaced by 2k. First, we estimate 04 and 0_. Let E T, with T defined therein with 2 in place of k. Write p EvEa Co V for the corresponding (scalar-valued) polynomial. Then
m p o Ex(X:)
|Acl2
m
and therefore
E
Ac 1
|| L3(D)-
36

---

Since ||clo,, - 2k, D.14 implies D.6. We now apply Lemma D.4 and the fact that ||Pll =
||e||| = to get
C3 E Ac|2 S
for universal constants C1 C3
0. Since c was arbitrary to deduce that
I 0_ v 0+ S C1.
(D.15)
now show that D.7 holds with the desired probability. Let p. q E Ps. be arbitrary. Then their difference h = p - can be expressed as
h Σ dvV.vv
(D.16)
VEA
where d = (du)uEA E 5AN satisfies
o. |id|lo.v 2kk.
Now, this, D.14 and Lemma
D.4 imply that
|| I| 13(D.)) S call cellaalle
Therefore, in order to prove (D.7
suffices show that ||| (lgg(D)))) S | disc
Observe that
|| disc. ||Ad|1
Ad 2. v'B((r))
sup
|1w/ (Ad)ll2
where we recall that for a vector 2 = (2:) E YN,, we write (²() = -2((2)))= E ERN, By linearity, have y" (Ad) (d). Therefore, by Lemma D.7
| | =
|| ||Add|
||y (d)li
sup w (B)))
sup g" EA)))
(0_ - (1 0+)c5)) (ly
2 (c3 (1 + c))05) sup
11 (h) 2 13))
''EB(r")
(cs (1 + c))c5)) ||AlIl
for universal constant Cs O, provided satisfies D.11 We set ca/(2(1 ca)es)
to get
|| ca/ LO(D
provided m satisfies (D.IT) with this value of 8. However, this implied by the condition D.13 We deduce the result.
D.5 Construction of the DNN family N
Recall that F, |A| N is an arbitrary set and S is defined by (D.I). In this and what follows, slightly abuse notation and consider DNN N Rd - R. as function R IR which depends on only the first variables.
Lemma D.9 (Approximating Legendre polynomials with tanh DNNs). Let with supp(v) S (l...., d}, Yu E I, and m{T) = max,er | < co. There exists a a.fully collycconnected family No of tanh DNNs N:, I + RR with
width(N.)) S m(T), depth(N.)) S log(m(T)),
such that, for any 0 < 8 < 1 and v E there is a DNN N2 E No with
| Vulleg 5.
(D.17)
Moreover, the network 0 + 0 also belongs to No (trivially, since tanh(0) = 0).
37

---

Proof. We follow the argument of [S] Thm. 7.4], which is based on 79 Prop. 2.6]. Let v E r. Then via the fundamental theorem algebra we can write (x)) as a product of ||||| numbers
V (=))=
II
I d (tt)
(Esupp())
Here (ra are the roots of the univariate Legendre polynomial Pa.- We append m(T) - ||/||| ones and write v (a) as product of exactly m(T)) numbers. Now define the affine map
Av R RM())
(D.18)
so that (z) is the vector consisting of the values d; Tey) for = 1,..., 2/ and i supp(v) and otherwise. To complete the proof, need construct tanh DNN mapping Rm(F) -> R that approximately multiplies these numbers. To do this, we argue as in the proof of [5] Thm. 7.4] to see that there is tanh DNN N2 with
width(No)) S (T), depth(NN.) S log(m([))
that satisfies the desired bound D.17 Since these width and depth bounds are independent of v, we deduce the result.
L.
Fix 8 > 0, let = UsesS, d dx and consider the corresponding family No and DNNs No. r, asserted by this lemma. For any E I, we have E S for some S E S, and any such S satisfies 15% S Therefore up
2(5+E) 2 I k for any v E S and we deduce that
1 - II (2 +1) un S 1/5+E)
1=1
This implies that mT) < k1/(5+5) and therefore
width(AV.) S A/((49) depth(AV.) S log(k).
With this in hand, we now define the family A of DNNs N Rdx - Rd by
No.
Neys
N =
:S Msst E, C R
(D.19)
0
Here also the fact that |S| 18), < k. Notice that this family satisfies
width(W) < +1+1/()+)) depth(A) S log(k))
(D.20)
due to the bounds for No.
Now let N e and write C= = C=([all -.. |c where c, E Ry. Then
Is|
[s]
Dyo N
Σ
Dy(c,)Nn = Σ N.N.s
where a E 5.
Therefore, we can associate N with the space of functions P Ps. where, for any arbitrary Banach space (Z, (l1z),
88.2 C : c. E 2, S SES
WES
We now require the following lemma, which relates the distance between a function in Ps.z and the corresponding polynomial in Ps.z.
38

---

Lemma D.10 (Discrete norms of polynomials and their approximating DNNs), Let S C F, (Z. 11))) be any Banach space and suppose that p Eves Cu Vn where cy Z. Define
p = Σ No.NN.
WES
Then
1p Pllaisc.s S 1pp (D.2) I 28 8 1
(D.21)
Moreover, if = S S and D.7 holds with satisfying ó óv V/Stu// then
|| Eg(Da))
p disc, a 8 5
Proof. By (A.IIf) and the definition of the No have
Ip Plldise,s S ||p 1g
= sup || - 1)
==
< sup
(c)))l (D)l.gg
E=(()) WES
S d||||||
We now apply the Cauchy-Schwan inequality and Parseval's identity to obtain
lp - P dis, S <8//S]]||clla, = 5V15) W/Iss//llllllacc.... 23(1.2)
which gives the first result.
For the second result, we apply D.7 with to get
Eg S a || S a (Ir- - Pldisc disc, + lItilaisa.)
Using [D21)) and the fact that /v //ST/a < now gives the result.
Remark D.11 (Other activation functions) As seen in this section, a key step in our proofs is emulating the polynomials via DNNs of quantifiable width and depth. There is an extensive literature on this topic. See, e.g., [ 21 23 25
38
57
63
72
78
79
85
86 92 97 and references multiplication operation
therein. The proof of Lemma D.9 reduces this to the task emulating
(#1,..., Faa E Rdd + I1 Za E IR via a DNN. As shown in the proof of [5] Thm. 7.4] (which is based on [79] Prop. 2.6]), this can in turn be achieved using binary tree of [log(d)) DNNs that approximately compute the multiplication of two numbers (x, y) E IR² + zy E IR. Further, this task can be achieved via the identity zy ((x + y)² - (I - 3)4 by using a DNN that approximately computes the squaring function E R
R. To summarize, provide DNN of quantifiable width and depth can approximately compute the squaring function, it can also approximately emulate the multivariate Legendre polynomials.
In view of this, we can adapt our main theorems various other activation functions without change. This includes Rectified Polynomial Units (RePUs), where the emulation is, in fact, exact (see, e.g., (57 Lem. 2.11 2). also includes the Exponential Linear Unit (ELU) used in our numerical experiments and many others. See, for instance, Proposition 4.7 of (38) and the ensuing discussion. Rectified Linear Units (ReLUs) are slightly different, as in this case the depth of the DNN that performs the approximation multiplication depends the desired accuracy (see, e.g., [79 Prop. 2.6]). One could modify Theorem 3.T to consider ReLU DNNs, with result being a worse depth bound than that presented for tanh DNNs.
D.6 Analysis of (2.
Lemma D.12 (Approximate minimizers of (2.5) yield approximate minimizers of (D3)). Suppose that (D7) holds, let N be the family of DNNs defined in D.5 and Ñ be any (a, r) apprrxxmia Lei
minimizer of 2.5
Dy N ENN P PS.
DES
39

---

where S E S and & E V, and define
ÿ Σ Vu.
WES
Then P is ('', -apppriixi minimizer of D.3 where
o' S s + +8///o)
(D.22)
, s (Fllaggx0 + Vm Blla,1)
+ +ovkillillzcoa 13(0
Proof. Let p Eves Cu Ps:ÿ be arbitrary and N N be the corresponding DNN so that Dy NNoN= EpesCoNi Then by the triangle inequality and the fact that N is approximate minimizer, we have
Y Ex
| Dy N 11B Dy o Mlldise,
==1
5 o
| No + 11p - Dy o Ñ Mlddsscs
5
- poxx + Dy Nlldssc + 11B - Dy o Mllaisss
We now apply Lemma D.10 the last terms, noting that |S| SS) S k since S S, obtain
| -ox-0oxx())) so L Ex
oō AiVlllllllllge.. 8 8 @illllllll
Consider the third term. We first apply (D.7) with -= get
[|pll23.D.>) S I|Plaais.. = a - 'Ilp p Ex Illissc
We then use the triangle inequality to get
I| o Ex Illaisc,
I F p Ex Exllldisc,y + || si
m
r po Ex + (1
Vm E F2
m
Therefore, we obtain
Y - po Ex s0 a
Y po Ex(x:)11 +r
o8Vh/a
(1lleg)()1))
+ vm
E El1222)
+ @vkklllll
Since p E Ps.5 was arbitrary get the result.
40

---

Theorem D.13 (Error bound for DNN minimizers). Les - linear operator, To 1 and suppose that (.7 holds with 2 and óv 2 eı for suitable universal constants Co. C1 > 0. Let N be the family of DNNs defined in DD. and Ñ be any
be bounded
(o.7)-approximate minimizer of (.5). Then the approximation F = =Dy N Ex satisfies
P| (
x F O P (2(00 + f F 2 F disc
+ To (II o Ex (2(2)))) + oll y Ex Exildize.1)
+ t + oovk] (x:))
E 2.
and
|F - (x) S |F
Qo Fll Lx + Vkoll Q F disc,a
+ - (IF qo e up 1
+ Vko F - Ex Ilaiio..))
+ ook| ookl + V ko
2,
m
for all q E Pssy.
Proof. Let ý be as in Lemma D.12 Then
F F11 $ F 6o Ex Ex1l - 11 Dy o N Exxlla(00))
(D.23)
|F - 1F-F1lege 2 $ 1| uP-poo Ex E + 1 Ex Dy N (x111
For the second term, we have, by (A.III) and Lemma D.10
0 Dy N Exll 133001 S I Ex -D N o Ex (x:0))
1 o Ñ (1
- |1 - Dy Ñ 1. (D:))
We now apply this, Lemma D.12 Theorem D.6 and the facts that a S and o' 2 to obtain
I Flll 1
F Qo Flll 1 +' 20
-Q F Ilaiec.
a (IIF
qo Ex (1 of d Ex Illatsc..))
o'
E 12
mm
and
2o |F Fllep(20)) & F| -0 F (x
F disc. Vio'll| q Ex Exllass,,a)
to (ILF - 9o Ex Ex1le
Vkr Vioo
E El2y,
22
for any q E Ps.y, where af and r' are in (.22
Due to the various assumptions, these satisfy
d'Sa
E 2.
5v
m
We deduce that F Flll & = Fll 1|11) + a -Q F dil
+ + (ILF - (1 + F Ex lid
+ + oo +
σ
-1 &vAlll (ell)ll(g(p))
Fm
41

---

and
||F -Fllpp - + V 20 F aiiis
t (IF goxxllx + Vko q Ex (ldssc..))
Vko B 2 + 5k ||l [3
+ + + 1okk +
We now bound the final term. Using Lemma D.10 once more, in combination with the fact that 8vk 2 1, we see that
|1 11lll - a-ō Dy o N Mlasscs& S Dy o N Maaiscss
m
1 Dy Nox + vm
1ll2 2.
m
1=1
< 0
|| 01
+
Y
12
m
vm
S (1++)
[1 +
Vm
E
2:3
+
Here, we also used the fact that N is an approximate minimizer in the fourth step, as well as the facts that the zero network 0 E N and that Dy is linear map. Plugging this into the previous expressions now gives the result.
D.7
Bounding the best polynomial approximation error terms
When (as will be the case when we come to prove Theorem 3.1 the error bounds in Theorem D.I3 involve best polynomial approximation error terms of the form
F q &x (22000) ||
q Ex Ilaise,,
||
&x Exll (x))) + VAlFF q Ex diddsii
for arbitrary g Ps.y. By the triangle inequality, these are bounded by
(2 = || q - <ll1z(x:>> + F| g 1 dil.dic.,
+ ||| o o Ex (3(xy) + Illg o qo Ex
(D.24)
Eco (F) = F go 1 (x + Vk|l 0 elllaise,H
||g o L - q Ex (x:)) Villlq o g Ex disc,
In this section, we construct a suitable polynomial in the case where (A.II) holds and thereby derive a bound for these term. We first require the following lemma.
Lemma D.14. Let G E 1 (X;3) and O < 6 1. Then the following hold.
(a) With probability at least on the draw of the X,, we have
||G ||G]] ||Gll1g(xes) Ve.
(b) Suppose that m 2 2r log(2/e) for some > Then, with probability least on the draw of the X,, we have
||G di disc,
S 2 (I + ([G())2(00)))
Proof. Observe that the random variable || satisfies
E G disc,j
||G|
22 (x::))
42

---

For (a), we use Markov's inequality to get
B G disc.
|| Metiso.. 2 ||Gllggax: /Ve -
E,
| (alligoppp/
as required.
The proof of (b) is based on Lem. 7.11]. We repeat it here for convenience. Define the random
variable Z, = |[G(X))]] y and observe that
(Z.)) E Ex- [x=xxI
||G [Gllag(0))) a.
Let X; Z; - (2,) so that
1
G disc
Zi
X;
i=1
i=1
Now let b = | and observe that
X; S Zi
b.
-X
S [B22)
I b, a.s.
We also have
Σ
((X))
E E < b
B B(Z,) = alm.
1=1
1=1
Therefore, Bernstein's 's inequality for bounded random variables (see, e.g., that
29
Cor. 7.31)) implies
1
(-
tmm/2
P
X
2t
s 2exp
ab bt/3
m
for any & 0. We now a + b/r and notice that
Rm/2 abtbt/3
2 2 log(2/c). Therefore,
Σ X < a b/r
t=1
with probability at least e. It follows that
| S 2/a v2 (Va+ vb/r)
with the same probability. Substituting the values for and b now gives the result.
Lemma D.15. Let F L (X;3), Ps. be arbitrary and 2 2r log(6/e) for some and 0 < E 1. Then
E2 (2 & F go all ug (2:)) /F + 1 (0
/k/e|lllll p3(.))))))))>))>)). |Iax - ldx Dx (x
and
Foc S(1 + /k/r)
go 90 (II + V q -0
+ +bllellezuooslllla Ldx Dx (x
+ + / /k/rillllllegggaas)la.. 114xx tax Dx o Ex (2,
with probability at least 1 -
43

---

Proof. We apply part (b) of Lemma D.14 with replaced by e/3 to the term F| g Alloisc and parts (a) and (b) of Lemma D.14 with replaced by e/3 to the term lll o Ex Ill disc, Using the union bound, this gives that
F Illl Illaiisc, X -
q 00 +IF 1 -00e-ollllxxxa////
q - Ex Illiisc.
< - -00=---xxllgge:1///
q o o Ex I| -
- -0 h/tpa///l/llllolll////////////// 11 -o
with probability at least - e. This yields
F22F..) g) x |F - q cll 1l12330 + F| q goolly
+ e| qo Ex
(x) S (1 + - goll: Vk|FF q ellgg(x)))
+ + -0 + vhllg o 1 q Ex 0 13(101)))))
with the same probability. It remains bound the terms involving q - go Ex. Using (A.III), Lemma D.2 and the fact that q depends on its first dx variables only, we see that
l1g o (X) 9o Ex(x)lly - Vk
V ||l (X) Ex(x))
Therefore
llq o g0 X
V V - Ex -xx111z(x0000000
0l qo o Ex (x v V ( 1xxx -xxlla
Substituting this into the previous bounds and using the definition of Ex from (A.III) now gives the result.
We are now ready to choose the polynomial g. First, we require the following technical lemma, which shows the existence of multi-index sets of weighted cardinality & which achieve the desired algebraic rates of convergence.
Lemma D.16. Let f= f Cu V satisfy f E H(b) for some b E ( with b 2 0. Then there are index sets S1 C F with [Sile, 122 S such that
| csi I C.).p..) 12/21//p, ||c cs, So--ssllleyyyCCC S C(b,p. 111//p
where C(b, 2 0 depends b, p and & only.
Proof. We first show that E (FF By definition of H((b) (see (2.3), f holomorphic every
Bernstein polyellipse (p) for which P satisfies
Pj + Dj
1,
-1 by < 1.
(D.25)
Using 4 Lem. 5.3] (which is based on 102 Cor. B.2.7l) with a = =B= = =00, we get that l|colly S 1 and
Pk -ctt
||ally> 1
II
(px - 10)2 (vx +1) DE
kET(w.p)
for all such p. where T(U, p) ssupp(v) O { Pk > 1}. Define the sequence do and
Pk 2
2/p 1-/p-110 inf d, = -
(ps - 1)2 (px + 1): satisfies (D25
v E (()).
kEI(u.p)
44

---

Using
C.3
C.4
we see that
II kEsupp(v)
(2ux + 1)(5+2)/2
and therefore
Pk vx+1
du S
kEI(P p)) (pk- 1)2 (2 + 1)7
II
for all satisfying (D.25) and some 7 (p, {) O. We now use 4 Lem. 5.4] to deduce that
= (dy)NEF E (N) with ||d|l v C(b. p. {) for some C(b, E) 2 depending on b, p and
only, Returning to c, this gives
||e|| |cllpp.
p.u.y
Σ 1/ 22-1 PIcl
S
Σ ld S c(b.p.E).. DEF
DEF
Hence c (F))) with || S C(b,,, p, E), as required.
The second step involves the application of the weighted Stechkin's inequality (see 3 Lem. 3.12 This gives that
min fllc -a--sssll..y.. S F. S1, sk] (x(g)), & [|cllp..: 1//11/p
for any q (p. 2] and k > 0. Applying this result with g implies the existence the S
(recall that || e12, = || l12.y) and applying it with q = implies the existence of the set S2.
We now define the set
HHI
HCI
V = (WWRE FF: II
(vx + 1)+ v =0 = CF.
(D.26)
Notice that HCI| isomorphic to an index set No by the natural restriction map.
Lemma D.17. Let k > 0 and suppose that A AHCI for some E N. Let f Ever Mn satisfy E H(b) for some b E e (N) with b 2 0. Then there exists an index set S E S such that
|| fsll (D.) I C(b,p,E) (K--1/P + m1pp/p))
(D.27)
where Is = Eves Cu V.. Moreover, y is Hilbert space, then we also have that
|l - fsll S C.b, (12/2-1/p + n 1/1p
(D.28)
Here C(b, P. > is constant depending on b, p and & only.
Proof of Lemma D.17 The previous lemma implies that there exist index sets St, S2 C F with
|St 6: S2 S k/2 such that
|c - es 11yy I C.b. 12/211/p, ||c - cs. 1l S Cbb, p,g) - 11p1/p
Now define S, US2 n and notice that S and [S I [S v + 1S2 S k. Hence S E Since U2 2 Uv [ we have (using [5] Lem. 5.1))
If - (f-fsllay I ||c esll w. I Ic cs, cs + ||ee calli,u.y
Hence, complete the proof of the first result, we need only show that
||c - -x S C(b.p) 1-11/p
for some constant C(b, p) 2 O. First, by construction, AHCI contains every anchored of size at most n. See, e.g.. Therefore ||c- (fc-cally calli,uy & ||c cs u. for any such set S. The result now follows from [5] Cor. 8.2].
Now suppose that y is a Hilbert space. Then Parseval's identity gives that f fsll = ||c cs csll2.y I ||c cs + lc cs callay-
As before, it suffices to show that
||c- cA 2la S C(b,p) p) n 1/2-1/p
This follows from the same approach and [5] Cor. 8.2] once more.
45

---

D.8 Final arguments
We are now, finally, ready to prove Theorem 3.1 We first consider the case where y is a Banach space, then treat the case where y is Hilbert space afterwards.
Proof of Theorem 3.7 when a Banach space. We divide the proof into a series of steps.
Step 1: Setup and DNN width/depth bounds. Let m, 6, c and L be as in the theorem statement. We may without loss of generality assume that 6 I 1/5. Now let
S dx
(D.29)
T
and
AHC
where AHCI is as in (D.66) We also set
{ = 1/6 - 5 220 0
(D.30)
and
k
(D.31)
eT.'
where c 2 is a universal constant that will be chosen in the next step. Finally, let 2- /m and N by the tanh DNN family (D.19), where the N₂ are as in Lemma D.9 this A and value of 5.
By (D200 and the definition of & and k, we immediately see that
width(N) x (m/L)²++,
depth(A) & log(m/L).
This yields the width and depth bounds 3.1 The rest of the proof is therefore devoted to showing the error bounds (3.3)-0 -3.4).
Step 2: Ensuring D.7 holds with probability at least e/2. A standard bound (see, e.g., the proof
of Lemma 6.4 in gives that N |A] satisfies
log(eN) I 4 log (en) < log 1mg)
(D.32)
Here, in the final step we used the fact that m 2 3 and L(m.e) e) 2 1. This and the fact that e 2 also implies that & S m. Therefore, the right-hand side of (D.13) with replaced by c/2 satisfies
co k- (log(eN) log²(k) (4/e)4 K L(m,e).
(D.33)
Hence, for sufficiently large e 2 1, we deduce that (3.13) holds with e/th Using (A.I), we see that ||xx
ldx o Dx Exll Exll1g(000<<>) L. Dx Ex Ex q= 2, co.
(D.34)
Hence D.14) is implied by (3.2). We conclude from Lemma D.8 that D.7 holds with probability at least 1 e/2 and 1.
Step 3: Error analysis. Let f E Hb) the function asserted by (A.II) and define y = I's as the polynomial asserted by Lemma D.17 with in (D29). We also observe that
(x = [1fllz S lIf lg (D.) S 1,
(D.35)
since f E H(b). We now apply Theorem D.13 with and use (D31)) the definition of 5 and to see that
3.8
F - Fllla(X,)) X F - Flll + F - O F II
+ n F2(FF Fopt.2 Feaap.22
(D.36)
|F Fl1 < F - Q Fll F (x)))) + V Q F disc.jt
+ ग T E.c (F. + Expt,co + Esamp.cc
with probability at least e/2, where Ez FF and E (F. q) are as in D.24 (y(R) is any bounded linear operator and TQ 11ly-
Q +
46

---

Notice that Parseval's identity and D.35 imply that
|I (3(,)) $ II 13(0))) & ( 2
Hence, this, the previous bounds, Lemma D.15 with replaced by c/4 and the union bound yield
|| F Flll Fl12z((0)) $ F -
Fl113(())) 2
Q F
+ F| F Q Filldisc.,
To (11- - Po--goullan
|| go go g0
T Trevk/ellua ldx Dx o (xx111(()000(040)
+ E + Esamp,2
and
| Fll (x:0)) F Fll27(x00 f VFIIF F disc,p
+ to (11 + -o + VkIlF' (0ll1g(0))))))
+ koklle Ldx Dxx (x
+ ToVi(1 + / /k/rr)llsss - lix o Dx o Ex (x000
+ Liopt.o Esamp.co
with probability at least 1 - -3//4, for any such that m 2 2r 1og(24/c)). In particular, we may choose r due the definition of (D.II) We next bound the discrete error | 2 Fllliie, Applying Lemma D.14 with replaced by e/8 and the union bound, we see that
F Q Flldis,, 2 | - 2 Fl Flagee//
F Q Fll Flldisc,f 2 F Q F (1g
Qo 2
with probability least 1 - c/4, provided 2 2r log(16/c). In particular, we may take k once more. Substituting this into the previous expressions, setting r = k throughout, using the union bound once more and recalling (3.7). (D.3I) and (D.34), deduce that
F F (1)())))) $ || Q F Flligxxnn/V
+ mo (IFF q qo 1 h//////mLLL/// q (ll2())))) [|I--Fo (mg/ay) Ex,2 Foopt Fsamp,22
and
|| (x & F Q 100Fll1,eee F111p(2)))) + Vm/L[FF Q Fll Fl1
Te (IFF go goellep(x)) Wm/LllF-qQaaa go (1((00)))))
( Exx,x Fopt, + Esamp.
with probability at least 1 e. This holds for any bounded linear operator Q: 2: + ÿ = Dy
We now set Q Dy Ey, which linear and bounded by (A.IV) with To = =y Eylly ay by definition. Using this, we observe that
|F Q L((x))) [T DD o Ey E
== 0.0
Substituting this into the previous expressions and recalling 3.7 now gives
|| F 1F-F1llz(x.0) S ay (IF qo -VF--olllzzue /lll:px.o/////LL - (((()))))))
+ Ex + Ey.2 + Espt.2 + Esamp,2
(D.37)
| - ( S ay (IF qo (llx((x)) + F g0
+ Ex + Ey,00 + Eopt,o + Esamp,
47

---

Step 4: Bounding the polynomial enror terms. It remains to bound the error terms F - 90 in D.37
Using (A.I, (A.II) and Lemma D.17 we now notice that
|P - qo <ll (x:0)) = Il - وI (Da)) E fl 9 (Da)) & C(b.p. (k2-1/2 n2-11/z).
Recall that n 2 Therefore, using this, D331 and (36p. we see that
(1F-gooll (g0ll///..//////LL /otiia////mmLL I| go - 2 ayll go cp
- go (IF-
ay
S ay C(b.p.)) (m/L) L) (mm/)/-1// 1111/p
Eapp.
and likewise for the L -norm bound. Combining this with D.37 now completes the proof.
Proof of Theorem 3.7 when y is a Hilbert space. The two differences in theorem statement when y is a Hilbert space (i) the I.2-norm error with respect to the stronger Bochner norm, and (ii) the approximation error terms Eapp.g: = 2, oo, are smaller by a factor of 1/2 in the exponent (recall (3.6). We treat both issues separately.
First, we note that Lemmas D. and D.2 also hold in the Bochner norm, since these results already give upper bounds involving the Petris n.2-norm. Next, we observe that the proof of Lemma D.3 readily adapted yield an equivalent result in the Bochner norm with the same constant ö. The same therefore applies to Lemma D.4
For the (i), we commence with the supporting results D.2
We next consider the analysis of D.3 D.3 If we replace (D.7p by the condition
1p glldisc. max p 9 Lg(D: llp allzg(Da))) Vp.q E Ps:5
(D.38)
then the proof of Lemma D.5 yields the by the Bochner n.2mn Theorem D.6 is likewise modified to provide a bound in the Bochner T.2-norm.
bounds, except with the Pettis 7.2-norm replaced
Up to this point, we have not used the fact that y is a Hilbert space. We now need this property. As in $D.4 the next step is to establish that (D.38) holds with high probability. Lemma D.7 is unchanged, therefore our focus is on Lemma D.8] We now describe the steps needed to modify the proof of this lemma assert (D.38) subject the same conditions (D13 -D144. First, let
( be an orthonormal basis of y and write each coefficient cn2 of the function h in (D.16) as
co: = Σi byjpy for scalars bij. Then it is short exercise to write
2
|MI| = ||Ac|225
Abb 1|
where b, (bry) Since bij = 0, Vj, whenever cn = O, this vector also satisfies [ib]ll,, S 2k. Hence, by Lemma D.7 and Parseval's s identity twice.
dy
Σ (0_ (1+00c50)lbb; ==1
N
=(0 - (1+ + 0505
Σ
|1c 112
(0_ (1 0+ c5)) 110111111222)))
We now the bounds (D.15) (which unchanged) and set 5 ca/ (2(1+ once get
[Mll 2 ///2|/1|2
This gives the desired result.
This completes the changes needed order to analyze the polynomial training problem (D.3). We next consider the DNN training problem (2.5). $D.5 remains unchanged. After reviewing their proofs,
48

---

we see that Lemma b.12and and Theorem D.13 both hold with Pettis norms replaced by Bochner norms whenever (D.38) holds instead of (D.7). Finally, we also observe that Lemma D.15 also holds with Pettis norms replaced by Bochner norms, both in the bound and in the definition (D.24) of (F(,)) and (F.
Having completed the changes needed in all the preparatory results, we now follow the same steps as above in the Banach space case. Steps and 2 are unchanged. For Step 3, go through and replace Pettis norms by Bochner norms throughout. Using this, we obtain (D.77. except with the Bochner norm on the left-hand side the first inequality, i.e.,
|F PP1-Plag(E:D)) S ay (IL- - -0-0-q0llaa -000ll1z(x00 Vm mm/L ||F - qo00llg(0)))
Ex, + Ey,2 Eopt. + Esamp.
(D.39)
| FI) S ay (IF -I -q0lllep(x:) + Vm/L (0
+ Ex,00 + Ey.00 + Eo + Esamp,co
This concludes the changes needed to address (i). To address (ii), we bound the terms F - q L. Using (A.D), (A.II), Lemma (.17 the fact that 3 is Hilbert space and the definitions (D.3 and D.29 of k and we see that
| - q all ( = Ilf - - (1.2 & llf (ll & C(b,p.E) (m/ L)1
and
- g0- 12(x00))) ||ʃ 9 (((D)))))) & V -1laADD) & C(b,p,)) (m/T.)1/2 1/p
Substituting this into (D39) and recalling 3.6 now completes the proof.
Remark D.18 (Differences between the Banach and Hilbert space case) Having seen the proof, summarize these differences follows. First, the matter of whether the Pettis versus Bochner norm can be used reduces to the choice of such norm in the discrete metric inequality (D.7). When ) is Banach space, we are able to establish this in terms of the Pettis norm subject scaling between m and & (see Lemma D.8 and (D.3)). However, when y is also a Hilbert space, we can establish the stronger version (D38) of this inequality by exploiting the additional structure. This, in short, is what leads to the stronger norm bound in this case.
log-linear
Second, in the Hilbert space case, get improved approximation error. This stems from (D177 and, specifically, the fact that when y is a Hilhert space we may use Parseval's identity in the Bochner space T.2 D; ))) to bound the n.3-norm error term via (D.28). This is not possible when y is Banach space, so we settle for bounding this term via (D.27) instead.
E
Proof of Theorem 3.2
E.1
Setup
As in D.1 let A c F with supp(v) C (L...., dx.). Vu E A, and write N = [A]. Let S be as in
D.I. N. > max(m, k} (its precise value will be chosen later in the proof) and define the set
r r= USCF, SES
where I. {e: == I....,
(E.1)
Finally, let 0 8 and consider the family No and the tanh DNNs {NuJuer whose existence is implied by Lemma D.9 We will specify A. k, r and d later in the proof.
Next, let
Σ Vv
be any minimizer of D.3) where [S|o S k and define
p Σ
No.
WES
49

---

Let
B 1 (Ne, Ex(()))
Now, 3 = () is finite-dimensonall subspace of the Banach space V Hence, for any Y E y there exists closest point Y 5i, i.e., point satisfying
||Y Ylly inf {iLY Z 2 2 {..
Given YI....,ym let Y, ..... Ym y be the corresponding closest points. Now define
v, - ( " i=1 e = Vr
E E
and
p+ p+
B + Ne)
(E.2)
i=1
where 2 E (())(() and E v. Iluly by assumption. Notice that
1, are arbitrary. Note that such exists, since >> m
Σ N
VESUD.
for coefficients & D. Therefore, write
p= D N,
(E.3)
where
N
N Mauurl
Ñ c
(E.4)
0
and C E [dyx((A)+r) Finally, we define the approximation
F= Dy Ñ Ex
(E.5)
and, for convenience,
F= ==po Ex.
E.2 Estimation of the DNN minimizer
Lemma E.1 (N is minimizer). If B is full rank, then
F(X:) = Yi,
Vi 1, 1...,,
Therefore, N is a minimizer of 2.5
Proof. Observe that
F(X,) =xoxxx)
=xoEx(X)) + VF Σ (B) (B yz),
=x0Ex(X,) + V e
=x0Ex(X,) + Vi(e),
= P.
50

---

Here, in the penultimate step we use the facts that Byz = yBz = 0 since (B) and BB I since m and B full rank by assumption. This gives the first result.
For the second result, recall that Y, is closest point Y, from V Dy Therefore, for any DNN N,
E || Dyo No
m
1 2 m Σ |
Yilly
11 Dy Dy ox m Σ
as required.
Lemma E.2 (Bounding in terms of F). Suppose that D.7 holds with a 2 and a - 5vk 2 c and also that
Villodx ldx Dx Ex (2(0)0(())) S C2
where Co, C2, are suitable universal constants. Then the approximation F satisfies
F
Fll 1 $ F| Fillzgx00
vm
)
1
+ (1+ 14
| (I +
E 2.
Via (B)
vm
ml oVT)
Y F(X))ly> + - E Ellay
Vro (B)
==1
+ (1+
and
| (2 F F1122(x0:))
vm
1
+ (1 (1+8)/FövR
1
| (x:0))
+
E
Elyyy
vro B
mm + mmiu (B)
1 Σ
1 F(X))ly 2
E
Ell22
mm
1=1
+ +1+8)VTT|z
Proof. By the triangle inequality,
FF Fll (2(00))) F Flleg(x)) + - -f
(E.6)
||- - -- Flage & F - (1 + 1 - (11g((000)
Consider the second term. We have
M - Flllg((00) = |llp Dy o Ñ (lllg(Da)) 5 || p ( + |1 (
(E.7)
||F- 1F-FF11, =11-- -1p- 1 Nll ((.))) S | p [ (D:)) + |(])
where q - - p= El= (Bie+h e + yz). Lemma D.10 and (A.IIl) give that
||B ill [((::)) = || - 7 ممlا (D:)) S 8v L3(D->>
(E.8)
Now consider the other term in E.7 Define q = E wz), Ve,- Then Lemma D.10 and (A.III) once more give that
(B
|| r3(D:>) < || (3().))))) + lll alll ( 5 |1 ( + ó
( (1:3) S
+ llq - 71 ((::))
S | + o
51

---

Here, we also used the fact that [To = We now apply Lemmas D.I and and get
and (A.III) once more
Mall & (1+ (1+ Eg(De
| S (1 (1++iiiilllll (E.9)
We next analyze the term
|| |0l Lety" v.. Since y ((Ble (e))(())
we have
5 v"())
Σ ==
Hence, by Parseval's identity,
M rg(na)
sup rE)(")
||1/ (i)laa))))
| y (e) + y (1)=112
sup (EB((")
sup y'E((P')
||l (e)ll+
sup EE
ly (v(1)||=112
m (
|| delllyy> + ||=1|2-
Omin
(B)
We now use the definition of e and the inequality |/ellla. S ||ellyy to obtain
l rg(Da))
S
m
1
Σ 1=1
1& po Ex(x))) + 11
mi (B)
We next apply the triangle inequality and Lemma D.10 once more get
mm
| 13 S Vromin (B)
Y - po + 11 Plldrccs + 11/111
Vm
- (x + +ork &VVilllllegcc.o) + ||
Fr (B)
==1
Combining this with
E.7 and
B.9
deduce that
F - Fllegaa:0 (1 (1+ (1+8V)
8VT
1+
m
|| || |لم + 1|
B
m
1
po Ex + 1 fm
1
E Bllay
Tommin
(
1=1
and
Vm
| F (1 2 (1+
8v
1+
I1 (1ell13(DO)) + ||
Vra
B
1
Y po Ex(xx))
vm Ell2.>>
Vramin (B)
52

---

It remains to bound the term 23: Using (.7) and the fact that ç is minimizer of D. and that the zero polynomial is feasible for (.3)). we get
|I Eg(D.>) 2 disc3
1 vm
Iy, (x-x)
+
Y 12222
2
12
Vm
- 2 ( +
E
2.
Vm
Combining this with the previous bound and (E.6) now completes the proof.
E.3 Estimation of Jmin B
Recall that a matrix A m is subgaussian random matrix if its entries are i.id. subgaussian random variables with mean zero and variance one (see, e.g.. 29 Def. 9.1]). The following result can be found in, e.g., (29 Ex. 9.3].
Lemma E.3 (Smallest singular value of subgaussian random matrix). Let A E R be subgaussian random matrix and Omin be the smallest singular value of 1 A. Then, for all < t < 1,
ym
(omin & 11 -1-44 c1 n/mm n/m -t) s 2 2exp(-o2mt)
where C1, 02 0 are universal constants.
Lemma E.4 (Bounding Quin( (B)). Suppose that /md S vw/8,
3(5+5)/2 VF lixx 1ax Dx Ex (x,e
(E.10)
2
where w is the variance of the univariate probability measure as specified in Theorem 3.2 and
dx 2 c + log(2/e))
(E.11)
for some universal constant c 2 1. Then, with probability at least - e, the matrix B is full rank and
miin (B) 2 Vw/4
Proof. Define the matrices
B" = 1 Vr
B'= (Ve o Ex(())) mar
(Ve
lax (X:)) mr
i-=1
Then, since r 2 m,
mmin B = inf {1I d|2 d E Cm |d]| = =]
2 Tmin (B')
[| B') ll2
minn
BB)
B B'
(B") B B'l,, IB' B=
min
Now, for any e E C"
1 Σ (B - B')el =
Ne, (2x;) - De, (2::) cj
im
m
< Σ
8² ||||
< m8² ||
53

---

We deduce that | B B'll S mmd I ww/8. Hence
mmin BB) 2 min (B") Vw/8- -B
Now let c E C" and p Ei=ı ce, be the corresponding polynomial. Then, by (A.I), (A.III) and
Lemma D.2
! m
[I(B' - -D cc12
p Lax (X,) po lax Dx o (x,)
S Lip(p, D (N)), Rillaax - ldx o Dx Exllage
3(5+5)/2
VT
|P (1ll1g(1)llaxx - lux o Dx Ex
2
8 |cl|2
Here, in the third step we used the fact that |oopo 35thr, since un, = v3. We deduce that
B' - BBll S vw/8 and therefore
miin B miin (B") vw/4.
It remains to show that min B") /w/2 with high probability. By construction, V (œ) v.n... Now recall that the pushforward is a tensor-product of a univariate probability measure supported in [-1, 1] with mean zero and variance w 0. Therefore
B"" T v3 V
A.
Vr
where A ((Xx))//V\); E Rrxm By construction, the entries of A are i.i.d. subgaussian random variables with mean zero and variance one. Hence A is subgaussian random matrix. We now apply Lemma E.3
Let t = 1/4 and observe that
16
N 4cmm,
log (2/c),
C2
by assumption. Therefore,
P(aamin (²") vw/2) S P( (A/V)) Se.
This gives the result.
E,4 Final arguments
We are now ready complete the proof of Theorem 3.2
Proof of Theorem 3.2 Statement (A). We divide the proof into series of steps.
Step 1: Setup. Let m, 8, and L be in the theorem statement, We once more assume without loss of generality that 8 < 1/5. Let n be as in (D29) and A = HCI let & be as in (D.0)) and
m
k
(E.
T.
where 2 1 is a constant that will be chosen in the next step. Let
min {2 m /r2 (w/(8mm))
where w is the variance of the univariate probability measure and
= [c2(m + log(1/e))1,
(E.13)
where 02 2 2 will also chosen in the next step. Note that dx >>> by assumption. Finally, let be as in (D.I). I be as in (E.I) and ]Nu be the corresponding family of tanh DNNs ensured by Lemma D.9 Finally, let F be given by E.5 with DNN Ñ in E..4)
54

---

Step 2: Ñ is minimizer. By construction,
width(N) I (k r) m) depth(() (N x log(k).
v e,, then |||||, 1. Hence m(T) S ++ maxses m(s) k1/(5-5) =1 k ( (see D.5). Using the values of l and r, we see that
width((N S (m + loggoo/)))((ool (mm(L/)))m/LL)), depth(N) S (og(m/L).
Therefore, N E N is feasible for (255p. Lemma E.I now implies that N is a minimizer, provided B full rank. We will show that this holds in the next step.
Step 3: Ensuring that min! B) 2 Ww/4 with probability at least 1 e/4 We seek to use Lemma E.4 By definition of 8, have that /mo I /w/8. Now (D34). (E.13) and (3.9) imply that
10
(E.II) hold, the latter with replaced by c/4. Hence Lemma E.4 implies the result.
Step 4: Ensuring (D7)) holds with probability at least e/4. This step is very similar to Step 2 of the proof of Theorem 3.1 The only difference comes in the estimation of N in (D.32), since now N = | S |A|+ + Since 2 3, we have
log(eN) - log(e]A[(r + 1)) S log)(m) + +og(m + log(1/c)).
If m & log(1/e) then
log(eN) x log" (m) + log & log (m) + /lg(1//e)
where in the second step we use the fact that log(t) I for for t > 0. Conversely, if m 2 log(1/c), then
log(eN) S (m) s log? Vlog(1/e).
Therefore, D.33 with e/4 reads
co k- (log(eN) log" (k) + log(6/e)) S k- (log" (m) (oog (m) + v log(1/e)) + log(1/e))
< k (log((m))))))) + log(1/e)).
k. T(m,e).. e).
Hence, due the definition of k. we get that (D.13) holds once more with probability at least c/4. The remainder of this step is identical to Step 2 of the proof of Theorem 3.1
Step 5: Error analysis. We now apply Lemma E.2 to the approximation F. Since miiu (B)
2
Vw
5 S 8 < and r 2 m, we deduce that
|| F Flll (X(:0))) $ ||F - F (R(0))) + +8V (111L277X00) +
1
E
Vm
1
11 F(X))ll 2
1
|| +
|
vm
and
|| -
-1--Fll (1))) $1 -11E-Flle + Vrovi
+
Ellay
E
Vm
1 1 - F(X))
Vr|2111 + vm
E
2:
with probability at least - c/2, where F= & Ex and f the corresponding minimizer of (D3)
We now appeal to Theorem D.6 with = and = O, recalling that a 2 and ov S 1, to get that
|II F (x) S || Q o F Fll1g(xx:)) + F Q Flllaise,p
+ Te
[ q Ex (x]1( + III g Ex di
1 mm
Ell2, 8v Fl (x:))
+ ||=1||
Y - F(X,)lly
m
55

---

and, since 8vF 2 1,
F F1 S 1|FF -Qo L + Vkll - Q o Fll Filldisc,i
+ 2 (IF - -o + v - o Ex Illaioa.))
+ b - /ToVA|IFll 111))))))))))
+ Vrl1z112 + Vm
Σ I|Y F(X))
for any E Ps.y and linear operator 2 + 5 = (y(( with To = 11 Consider the final term. Since Y; V is the closest point to Y, = F(X;) + F. we have
||
y,ly S [F()) Q F(X,)lly ||Eily
We now use this, the fact that P is minimizer and Q q is feasible in combination with triangle inequality to get
Y F(X))>
I 2x + +II F- - Q GoFlll Fildiss,
E 2.y
m
1=1
2
S | Q o Ex Ildisc... + F'llaisc.u
2 +
|
v'n
2
T F - go Ex Exilldisc, + + - =
F disscic.. F +
E
2.y"
vm
Now let f E H(b) be the function asserted by (A.II) and fs be the polynomial asserted by Lemma D.17 Substituting this into the previous expression, recalling (D.35) and using the definition of 8, we deduce that
|F FIlLZ00000 & 1I 2
Qo F (112000000 + F
Q - Fllaiis
T2 || +
m + Esamp.2
|F - FI $ |F Q F Fl Lx + /mlll F Q o Filldisc,
E (F,9) vr vr|1z112 + 22m E'amp.
with probability at least - e/2. Here F2( as in D.24. Eoo (F, g) is as in D.24 with replaced by m and Faamp, 1| |l VLL
Now observe that the first bound is identical to the corresponding bound in (D36). except with Egnt, replaced by ||2||2 + 2 mm Following the same arguments as in Step 3 of the proof of Theorem 3.1 this gives the corresponding bound in (D.37) which is
||I F ( & ay (11-- - qo pollll (x ///L/////LLL/// - q ellgg(xx)))
(E.
Ex,2 + Ey.2 + ||=1| + - m + Esamp.
The second bound above is identical to the corresponding bound in D.36). except with Eopt, replaced by /r||=/12 [|2 +2- Examp,oc and Exs (F, 4) replaced by Fy Fs and E.so Exo g). respectively, and with vie replaced by vm. We once follow the same arguments in Step 3, with these changes. This yields the corresponding version of (D.7)) which is
F (1 Say ay (VLIIF 9o ell (oll VmlIF q elleg(xe))
(E.15)
+ Exx,o + E'y + vrll2112 +2 2 Examp.co
Here Ex LEx and Ey,00 VLEy.o.
56

---

Having done this, we then use the bounds from Step 4 of the proof of Theorem 3.1 to get
F FIlez((A:)) & Eapp.2 Ex + Ey. ||21|| + 2m + Esamp.2
|F F S Eapp.oo + Ex,00 + Eji + Vr|1z112 +2 T + Ey Esamp,
where Fappo VT..app.co.
Step 6: Existence of uncountably many minimizers. Let = (2:) E (BB)) be any vector and consider 21 01 and 22 02 for 01, 02 E [[11, 1, with 81 + 02. Then these vectors define functions Pi and P2 as in (F.2) and DNNs N₁ and N₂ as in (E.3). Suppose that Ni = N2. Then, since Dy is linear, we have that P1 = P2. But then, by definition and the fact that y E f') we must have
0
E (z1 Ne) (01 02) 2NN..
Suppose that 02 without loss of generality and let æ E be the vector (sign(2+)) Then, e. (x) /3sign(2; (2) and therefore
(0) 02) (v3||=11 - 5r) 2 (0, -0)) [v3|2=112 - -8r) = (0) - 02) (v3||=11> - -2 2-1
since ||Ne, - Ve Ve, (D)) I 6 and s 2 2 by definition. We now choose x with ||=||2 =
2 m /r < m Note that this choice does not change the error bound, except for constant. also yields
0 (01 (2)(v32 -
which is a contradiction. Hence N1 * No Thus, we have shown that any 0 E [-1, 1] leads to distinct DNN minimizer that satisfies the desired bounds. We get the result.
Step 7: Modifications when y is a Hilbert space. The modifications required when ) is Hilbert
space identical to those needed in the proof of Theorem 3.1 (see $D.8 We omit the details. Li
Proof of Theorem 3.2 Statement (B). Let N = No Rdx + Ry be tanh DNN, where O E R are the network parameters (weights and biases). Let || -1(axx>> (laay) and || (l(D) be arbitrary norms on Rdx, RR and R respectively. Then, since the activation function is Lipschitz function, we have
| (x) No(z))l(a,) colle' -
+ 1),
where co > is constant depending on 0.
Now let N Na and F Dy Ñ Ex and consider Dy N o Ex x for N No. Since Dy: Rd + linear and therefore bounded, we have
[F() - F(X)lly - co collDylk(s>> M...lll....
( Ol((D) (1Ex(X))((xx) +1).
We deduce that
F Fll Fllez(()))
S F| 11 (g
S cgl Dy Ia Il (1ll - ØlleD (IExIlLy + +1).
Therefore, there exists neighhourhood around á for which
||
F F11220000)
< || Flez S To
for all parameters 0 in the neighbourhood. The result now follows.
Proof of Theorem 3.2 Statement (C). By construction, the DNN Ñ defined in (F.4) contains sub- networks that compute the DNNs Ne,, i = 1, ......,, which themselves are approximations to the Legendre polynomials Ve.- The construction of these subnetworks was described in the proof of
57

---

Lemma D.9 as the composition of an affine map defined by the fundamental theorem of algebra and tanh DNN that approximately multiplies m(T) numbers. In this specific case, we have
V (x) xz--
Therefore, the corresponding affine map (D.88) Ae. Rá RT((T) has bias vector that is all ones, except for a single entry that has value zero. We deduce that the bias vector of the full DNN (E.4) contains a subblock of size rma(T) that is all ones, except for zeroes. There are rearrangements of this subblock, each of which leading to a bias vector with | 1-b-bj b'll 2 1. Moreover, b' leads to the same DNN, after permuting the various weight matrices in the corresponding way. Indeed, if P is permutation matrix, then a (Wa x + b) = P P-lat (PWx: + Ph), since acts componentwise.
(Tm)(T)
remains bound ("m( from below. We have
(rm(T))
(rm(T)) m(D)"
pr
By E.13). we have that 2 2m. Now, by the definition
E.. of
m(T)
max m(S),
SES
where S is as in (D.I) for k as in E. 12 and A AHCI as in (.26 with in D.29) Now consider
the set = {leı] for some I
N. Then
[S = 2 (21 1)5+$ = (21 + 1)
Therefore, S S provided (21 1)1/3 < l and / n. Set L(k 1)/2] and observe that / S since h: Σ n and 5 < 1/5 by assumption. Therefore S E S. Using the definition k, we get that
m(T) 2 m(S) = 12 (m)(c²L))
for sufficiently large m. The result now follows.
Proof of Theorem 4.1
The proof of Theorem
4.1 will follow consequence of the following result. For this, require the following notation. Given 0 < I co, s E and a sequence c = (c:) we let
(c(c)p min z E (supp(z) S {s}.
where supp(=) (i E N 2, # 0) for (z.)ieN E N Theorem F.1. For any
then term 6m (b) defined in (4. satisfies
pm (b) om
vb ed (N), 0, |bb] S
As noted, the proof of this theorem is based on 77 Thm. 4.4]. We recap the details as they will also be
needed the proof of the next result. First, we recall some basic definitions. See [82 or [29 Ch. 10] for more details. Let K. be subset of normed space (X', || x1x) Then its Gelfand m- width is
dth (K, inf sup LekKnt
| n subspace of X' with codim(L") m
(F.I)
An equivalent representation is
dth (K, = inf
sup =EKnker(A)
| A: X:X: + m linear
The Gelfand width related to the following quantity:
F. (C,, X') inf sup ||x A(T(x)))l T: X Rmm adaptive, A Rm x (F.2)
58

---

where A is an arbitrary (potentially nonlinear) reconstruction map and I' is an adaptive sampling map. By this, mean that
[1(x)
T2(1,T((x))
r(x)=
( [1 I (x)]
where ri X' + IR linear and, for = 2,..., m, : X x Ri-1 + IR linear first
component.
Proof of Theorem F.
We proceed in a series of steps.
Step I: Setup. Define the functions
(x(x)= 3z,, x D,
1=
Notice that these functions form an orthonormal system in L2( (A.I) implies that these functions
form Riesz system in (D), with Riesz constants that are 1. Hence they have (unique)
biorthogonal Riesz system { L2(D). Now define 4 Φ. and v; t O. L. Let E 1 (X; IR) be arbitrary. Then
(G. (. (G, 4.
E KG, V. ()) IE V, L.) V (2()))
||G| (3(())))
EE (G, VI)LE v. (((3)
Consider the denominator. Using (A.II) and fact that the eù form a Riesz system, we see that
(G, L.)
G, 1.)
S
KG, 11)
(2(3RR
LE(D)
We deduce that
[G]|
(G. 12) AG (X;
(F3)
Now let b 2 0 with b (NN and / c N with N. Using 7 Lem. 5.2] see that the function
f=c)
cyyo E H(b),
(F.4)
REI
for any E y. Ilvll = and e = (ci)iEN C C with |c| S b (i.e., |ed < b, Vi), where > is universal constant.
Step 2: Reduction to a discrete problem. Let and be arbitrary sampling and reconstruction maps in 4.2). Following [7] Lem. 5.3], let F f and observe that
F(X) cy Σ (x)
iE!
and therefore
= =
where I' P! m is given by
Ci (X1)
T(=)=
c Eier 2 (Xmm)
due to
Notice that is an adaptive sampling map of the form defined above. Now let be such that ly" (y) lllly Then, by (F
y² B
F - R ((F)
( C(F)
2 (F - Ro C(F)) LA(
Σ
(F RO L(F)), 11)
Kel
59

---

By biorthogonality, (F), (.) (1) = clullyy = c. ci, which implies that
R || - L(F) [() 2 A
(F.5)
where
R Th R.V, y (w0 ((9 (R(y U)). v.) 1)1g SEI
Therefore,
sup FER(b,))
|| 1F-RR -F-RoL(R Ro
inf
sup cER supp(c)Er
(c-AoT(c)ly)
F.A
Se
where the infimum taken over all adaptive sampling maps and reconstruction maps Since and R were arbitrary, we get
mm 2 F [B( T). Cy),
where B(b, 1) = E |a/1 bb E /) and ey (R.,, 112))
Step 3: Derivation of the lower bounds. The next step is identical to the proof of Theorem 4.4 in This gives F.I
Proof of Theorem 4.1
We use Theorem F.1 For (i), we let b [= by defined by
b, = -2m) 1/p i 1, .,... 2m,
b; = 0, i 2m.
This sequence b E EM (N) with |lb|lp.M M |bbllp 1. Moreover, we have
om (b)2 = 2 2-1/pm=/2-11
For (ii) we let b = (b,), be defined by b, = cp(1log2()) (1))-1/, where Cp =
-1/ This sequence b E EN (N) with | = 1bblpp = 1. Moreover, EE log (i)))
Tm (b))
lolo (i)) cg (2mlog (2m)) (2mm)
m=++
as required.
G Proof of Theorem 4.2
Much as the previous section, the proof of Theorem 4.2 is a consequence of the following result.
Theorem G.1. Suppose that the pushforward in (A.I) is tensor-product of univariate probability measure. Then the term O, (b) defined in (4.3) satisfies
mm 2 Fm (b)1 log(m),
vb e ll (N). b 0, |||| S 1.
Proof of Theorem G.1 We proceed in a similar series of steps to those of the last proof.
Step 1: Setup. Let N N be bijection that gives nonincreasing rearrangement of b, i.c.,
bn(1) 2 bx(2) 2 .... Now, let r e N be arbitrary and consider the index set
11 U...UU, It = (=((1 - 1)(m 1) 1), ................................ 7l(m 1))}.
Notice that |/| = r(m 1). Define the matrix
= (()( 1-1=1
m.r(m+1)
and notice that we may write
A = [A
m.++1 m A,J, where A: (L(XX))((- 1
Let be the one-dimensional probability measure associated with s. Then notice that each A is random matrix whose entries are drawn i..dd from Since is supported in [-1, 1]. we deduce that
60

---

the A are independent subgaussian random matrices with the same distribution. Write y for this distribution. Let f1............... ......... ,, and Er,,, be the event
Ei 3u E ((A) ||ull2 11 vt/[mm1ll.. 1= 1....... (G.1)
will make suitable choice (,...., b later.
Step 2: Reduction to discrete problem. Let
C= CER |al by Viel.
c E ((A)), 1=
Notice that any c C also satisfies c E ((A). Now let = fo be as dependence on explicit now for convenience). Let æ E D. Then
F.4 (we make the
fe(x))
v3cy Σ TE!
(G.2)
We deduce that
(Fe(X,)) V3ey
where Fe = fc t. This implies that
|F - R [( || - R( () (x:3))
where, for convenience, we let C + (X,, [(,) 1 Therefore,
sup || R L(F) (x:))) 2 sup F. () FEH(b.))
CEl
Now observe that Fo = and 0 C. Hence
sup FER((..)
|| R [(F)))2g)(
{ [|R((Xx, 0| [ (m sup aEC
max
sup | (ell2g -
For > 0, the function x + maxf2, a x} is minimized at x = a/2 and takes value a/2 there. We deduce that
sup FEH(b.))
|F - (FFRRo(F)llgg 2 sup | (xx0))
2 cEc
Now, by (A.I)
Fe Fellay (2:0) ( 2 (lfelley(D.))
/3c sup
Σ ie!
ca,
[
With this in hand, we conclude that
E Ex X
sup
| F(X))=) (2 2 EA
sup ||]|| eEC
FEH(b.
We now use the definition of C to write
Ex Xm rpp
sup FEH(b.e)
F - F(x)),
(G.3)
EArry
sup CEN(A) Wihh
||a]
Step 3: Bounding the expected error. Fix 1 = I,...,r and suppose the event E defined G. occurs. Let un be the corresponding vector and define
(((+))))
C
ui I r.
61

---

By construction, we have that E (A)) and [(c:)) S bi, E It We deduce that
ba((m+1)) 1
sup C(N((A)) Kayissh.Wie
||cll1
2
Now observe that
1 |ull - |1
Therefore, we get that
|cll| 2 (]]
Da +
sup OLE (() (t..
|
4
whenever the event Ei,, occurs. Using the law of total expectation, we deduce that
(z(((+11)) + 11 PP ((E).)))
E E
sup C(NN(A))
|cal 2
4
for any fixed > O. We now appeal to 775 Thm. 1.4). This shows that
P(E S cym² exp(-t//o2) vtz 2 c1 log(m 1),
where C1, 02 > 0 are universal constants. We may without loss of generality assume that 02 2 01 2 Now set fj 02 log( (2cmm²) ) 2 log(m 1). Hence
) 1/2.
We deduce that P(E,.)) 1/2 and therefore
ba ((((++))) (m + 1) 20² log m2c
E E
sup CEN((A) Kee
|all 2
Now observe that
bx((m+1)) (m + +1) 2 (n(1(++1)) + bx(l(m+1)=m)
Substituting this into
G.3 deduce that
1)++1mmm
Ex
p
sup FEH(b.))
|F - R((X;, 1l)
log (m))
Σ
ba(1)-
m1
Since r was arbitrary, we may take the limit + co. We now use the fact that
mm (b)1 = ba(m+1) + br(m+)) + .....
obtain the result.
Proof of Theorem 4.2 Using Theorem G. statements (i) and (ii) are derived in exactly the same way as in the proof of Theorem
62

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We thoroughly discuss the main claims made in the abstract and introduction and the necessary assumptions to show them. Our main theoretical contributions directly address these claims. We also have several further remarks after these results provide further context for work. We also provide detailed numerical experiments showing that DNN architectures compatible with the setup for the theoretical results actually achieve the presented rates of approximation for challenging operator learning problems posed in Banach spaces in terms of the number of samples needed achieve given tolerance.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss our main assumptions and their relative strengths in detail in a separate section, 2..3 We also end the paper with a section discussing limitations. See $
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have a detailed discussion of the assumptions needed show our theoretical results in 2.3 We provide further discussion of the results themselves in $3 to place the theoretical advancements in this work in the broader context of the operator learning literature. We provide full proofs of our results in the supplemental material.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all of the necessary source code in the supplemental material. Further- more, we provide detailed discussion of the setup for the numerical experiments in B of the supplemental material. Given the code and description of the experiments, reproducing the experiments is straightforward.
Open access data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all the necessary software reproduce our experiments along with instructions for running the code to generate the results.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type optimizer, etc.) necessary to understand results?
Answer: [Yes]
Justification:
We specify all of the necessary byperparameters to obtain our experimental results as well as the optimizers used for training and the software used to generate our training and testing data. All of these are open source, no proprietary data was used in this work.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We plot not just the average error over all of the trials but also the (corrected) sample standard deviation of the transformed sample with shaded plots to provide an estimate of the variability in the runs.
63

---

8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Ye]]
Justification: The experimental details are provided in the Appendix $A.2 All computational resources are reported, including the type of workers, memory requirements, storage requirements, and time of execution.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics
Answer: [Yes]
Justification: We have complied with the NeurIPS Code of Ethics in the preparation of this manuscript. No human subject data was used to generate the results for our numerical experiments and data-related concerns are not relevant to this work.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily foundational, and the examples considered do not directly impact society.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g.. pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This work does not release any data or models that have a high risk for misuse, All code is open source and no proprietary data was used in this work.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The code submitttd in the supplemental material to both generate the data for training and testing our models and generate the experimental results was written by the authors. No other code or datasets were used in the production of this work.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: New code and data is included zip file supplemental material. 14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: We do not use crowdsourcing for our experiments and no research was conducted with human subjects.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
64

---

Answer: [NA] Justification: We do not use crowdsoureing for our experiments and no research was conducted with human subjects.
65


Reviews:
[{"review_id": "iNHi4ezPOV", "reviewer": "Reviewer_ZpED", "summary": "The paper addresses the challenge of learning operators between Banach spaces, focusing on holomorphic operators which have many applications. The authors employ standard (DNN) architectures with constant width greater than depth and $\\ell_2$-loss minimization. They identify a family of DNNs that achieve optimal generalization bounds for such operators. For fully-connected architectures, they show there are infinitely many solutions that offer optimal performance. The results demonstrate that deep learning achieves the best possible generalization bounds, and no method can surpass these bounds, up to logarithmic terms.", "questions": "No questions.", "limitations": "Theorem 3.2 only asserts that some minimizers are ‘good’, not all.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This work presents powerful and well-formulated theorems. The techniques used on holomorphic operators are interesting, and thanks to them, a generalization bound can be demonstrated. The work is novel, highly original, and I believe it could have a fruitful impact in the context of deep learning.", "weaknesses": "I think some of the figures of the experiments results are too small, making it a bit difficult to recognize the results. It would be good if the authors could review this issue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the effort you have put into reviewing our paper and are delighted by your positive opinion of the work. Here we address the comment(s) in your report.\n\n## `I think some of the figures...'\n\nGood point. We will use the additional page allowed in the camera-ready version to enlarge the figures in the final version of the paper.\n\n## `Theorem 3.2 only asserts...'\n\nWe very much agree. As we say in Section 6 (lines 340-344), we are actively looking into whether we can prove stronger results, either about all minimizers or by showing that `good' minimizers can be obtained through standard training.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "964y9Pe3gw", "reviewer": "Reviewer_XKAz", "summary": "Authors provide theoretical results on sample efficiency for learning holomorphic neural operators $\\mathcal{X}\\rightarrow\\mathcal{Y}$ (results are available for both Hilbert and Banach spaces) with a neural network of a particular structure. The structure of the network is encoder $\\mathcal{X}\\rightarrow\\mathbb{R}^{d_1}$, decoder $\\mathcal{Y}\\rightarrow\\mathbb{R}^{d_2}$ and DNN $\\mathbb{R}^{d_1}\\rightarrow \\mathbb{R}^{d_2}$, with both encoder and decoder considered to be given and DNN trained on $l_2$ loss in a usual supervised manner.\n\nBesides the upper bound on approximation error, authors also provide lower bound and conclude that active learning (deliberate collection of data used to train neural operator) is not justified, since non-adaptive training is already optimal up to log terms.\n\nAuthors illustrate their theoretical results (relative test error vs number of samples for selected DNN configurations) with several numerical experiments, including diffusion equation in $D=2$, Navier-Stokes-Brinkman equation in $D=2$ and Boussinesq equation in $D=3$.", "questions": "1. After line 102 there is a definition of Bochner and Pettis $L^p$ norms. Presumably, the later expression is a definition of $|||F|||$ which is not apparent.\n2. I want to clarify several statements on the encoder and decoder. \n   1. In (1.3) authors introduce encoder $\\mathcal{E}$ and decoder $\\mathcal{D}$, and later approximate encoder and decoder $\\widetilde{\\mathcal{E}}$, $\\widetilde{\\mathcal{D}}$ after line 114. What is the difference between those?\n   2. In particular, in the discussion (lines 145, 146) of assumption A.IV (line 131) that requires both $\\mathcal{E}$ and $\\mathcal{D}$ to be linear and bounded, authors claim that $\\widetilde{\\mathcal{E}}$ is not required to be linear. It is not clear to me how this agrees with the fact that $\\mathcal{E}_{\\mathcal{X}}$ is defined in A.III as a composition of approximate encoder and decoder. Can the authors please clarify that?\n   3. According to (1.3) encoder and decoder are defined for the approximate operator $\\hat{F}$. This means, as I understand, they are not rigidly fixed by $F$ since presumably $F$ can be approximated with many different encoders and decoders. Approximate encoders and decoders are not formally defined, so it is not clear what they approximate. Does it all mean that authors consider not a continuous operator learning problem but suppose that discretization (of the space of parameters and $\\mathcal{Y}$) is already performed ($\\mathcal{E}$ and $\\mathcal{D}$ are selected) and $\\widetilde{\\mathcal{E}}$ and $\\widetilde{\\mathcal{D}}$ approximate $\\mathcal{E}$ and $\\mathcal{D}$?\n   4. Why there are $\\widetilde{\\mathcal{E}}\\_{\\mathcal{X}}$ and $\\widetilde{\\mathcal{D}}\\_{\\mathcal{X}}$ but not the approximate encoder and decoder for $\\mathcal{Y}$?\n3. Several questions on Theorem 3.1:\n   1. Why $a_{\\mathcal{Y}}$ is called approximation error? What is the meaning of this term (it looks like some kind of volume)? In the ideal setting $\\mathcal{D}\\_{\\mathcal{Y}}\\circ\\mathcal{E}\\_{\\mathcal{Y}} = I$, so we have a perfect approximation that has nonzero approximation error.\n   2. Since $\\lim_{m\\rightarrow\\infty}m \\big/ L(m) = \\infty$ many terms in the upper bound will diverge unless the encoder and decoder are of sufficient quality. More specifically, the encoder and decoder should improve their accuracy as $\\sim m^{-1/2}$ for u.b. to be useful in case of $2$ norm and as $\\sim m^{-1}$ in case of Chebyshev norm. Can the authors please discuss this consequence of their result in more detail?\n   3. Can the authors also explain the consequence of the optimization error term? It seems that $\\tau$ that appears in it is to some extent beyond control and completely independent of $m$.\n4. Questions about experiments:\n   1. In experiments authors strive to confirm theoretical scaling $m^{-1}$. Since the encoder and decoder are perfect, and noise is absent, the only two sources of error are approximation error and optimization error. In my opinion, one can clearly see the signs of saturation for larger $m$. This is also clear from operator learning literature that relative error rarely fell below $10^{-3}$. Can the authors please comment on that? Is it because optimization error prevails for large $m$?\n   2. Dimensions $d=4,8$ in Figures 1, 2, 3 and in the text (e.g., lines 296, 297: \"PDE in $d=4$ and $d=8$ dimensions\") are slightly misleading because they refer to the dimension of the parameter space and can be confused with the number of spatial dimensions.\n   3. All results are given for perfect encoder and decoder. Can the authors share some thoughts on whether it is possible to test their upper bound with an imperfect decoder and encoder? What are those experiments might be? Is it possible to create a controllable setting to test terms in ub that contain encoder and decoder errors?", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Operator learning is a relatively recent DL setup, so novel theoretical results are of considerable interest. Authors managed to significantly improve previously known bounds and show that DNN can obtain near-optimal performance (in terms of the number of samples needed) in non-adaptive iid settings.\n\nThe contribution is primarily theoretical, but formal statements are well explained, supplemented with discussions and examples which significantly simplifies understanding of the results.", "weaknesses": "Overall, in my opinion, the research is of excellent quality, so I can not point to any major weaknesses.\n\nThe two main issues that can be relevant are: (i) the requirements for the encoder and decoder are not sufficiently discussed, and I find restricting the assumption that they are already available, and (ii) the significance of the numerical confirmation is not apparent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your effort in reviewing our paper and are delighted by the positive assessment. Here we address the comments in your report.\n\n## '1. After line 102...'\n\nSorry. The term $||| F |||$ was missing. **We will correct the equation.**\n\n## '2. I want to...'\n\n## '1. In (1.3) authors...'\n\nExcellent point. We define $\\mathcal{E}_{\\mathcal{X}}$ in (A.III) in this way is so we can get error terms in our theorems that depend on $\\mathcal{I}\\_{\\mathcal{X}}  - \\widetilde{\\mathcal{D}}\\_{\\mathcal{X}} \\circ \\widetilde{\\mathcal{E}}\\_{\\mathcal{X}}$. This term is standard in operator learning, and says that the encoder-decoder pair approximates the identity. For PCA-Net or DeepONet, there are standard estimates for it (see lines 198-201). However, if we were to set $\\mathcal{E}\\_{\\mathcal{X}} = \\widetilde{\\mathcal{E}}\\_{\\mathcal{X}}$, then the best we can prove is an error term involving $\\iota\\_{d\\_{\\mathcal{X}}} - \\mathcal{E}\\_{\\mathcal{X}}$, which may not be small. For instance, in PCA-Net $\\mathcal{I}\\_{\\mathcal{X}} - \\widetilde{\\mathcal{D}}\\_{\\mathcal{X}} \\circ \\widetilde{\\mathcal{E}}\\_{\\mathcal{X}}$ is small because the empirical PCA eigenspace approximates the true PCA eigenspace. However, for $\\iota\\_{d\\_{\\mathcal{X}}} - \\mathcal{E}\\_{\\mathcal{X}}$ to be small, one would need the empirical PCA eigenvectors to approximate the true PCA eigenvectors, which is a much more stringent condition.\n\nWe agree this should be mentioned. **We will add a short discussion to lines 198-201**, where we discuss the encoding-decoding errors. **We will also mention this as a limitation of our analysis in our conclusion.**\n\n## '2. In particular, in...'\n\nApologies. What we meant to say is that in PCA-Net, the encoder $\\mathcal{E}\\_{\\mathcal{X}}$ is linear. In our setup $\\mathcal{E}\\_{\\mathcal{X}}$ may be nonlinear. We only require $\\mathcal{D}\\_{\\mathcal{Y}}$ and $\\mathcal{E}\\_{\\mathcal{Y}}$ to be linear, not the encoder and decoders on $\\mathcal{X}$. **We will rephrase lines 145-146.**\n\n## '3. According to (1.3)...'\n\nThis is correct. We assume the approximate encoders/decoders have already been learned, and focus only on training the DNN $\\widehat{N}$ in (1.3). As we mention in lines 96-97, this is standard for other recent works on generalization error analysis for operator learning. Crucially, our theorems allow for arbitrary encoders and decoders, subject to mild restrictions, and show error bounds based on how well the each such pair approximates the identity map. So, to answer the question, the encoder-decoder should give a good approximation of the identity map. Specifically, see the terms $E\\_{\\mathcal{X},q}$ and $E\\_{\\mathcal{Y},q}$ in (3.7). As noted above (see also lines 198-201), these are standard terms in operator learning analysis.\n\nWe agree this could be clearer. **We will add a comment below line 116 where the encoders/decoders are first introduced.**\n\n## '4. Why there are...'\n\nWe think we understand the confusion. The tilde notation is just for convenience, as we later define the encoder $\\mathcal{E}\\_{\\mathcal{X}}$ used in (2.5) in (A.III) in terms of $\\widetilde{\\mathcal{E}}\\_{\\mathcal{X}}$ and $\\widetilde{\\mathcal{D}}\\_{\\mathcal{X}}$. In particular, the encoders and decoders $\\mathcal{E}\\_{\\mathcal{Y}}$ and $\\mathcal{D}\\_{\\mathcal{Y}}$ on $\\mathcal{Y}$ are also approximate.\n\n## '3. Several questions...'\n\n## '1. Why $a\\_{\\mathcal{Y}}$ is...'\n\nWe use the term 'approximation error' to refer to the whole expression (3.6). The term $a\\_{\\mathcal{Y}}$ is just one component of this error. As you point out, $a\\_{\\mathcal{Y}}\\approx 1$. But the essence of the approximation error is the factor involving $m/L$ raised to the negative power, which $\\rightarrow 0$ as $m \\rightarrow \\infty$.\n\n## '2. Since $\\lim_{m\\rightarrow\\infty} m / L(m) = \\infty$...'\n\nGood point. Similar factors also come up in other recent analyses of operator learning. But it is relevant as it means the encoder and decoder pairs must be learned to sufficient accuracy. **We will add a short comment on this to lines 199-201.**\n\n## '3. Can the authors...'\n\nYes, it is independent of $m$. Basically, this term accounts for inexact solution of the optimization problem. It says that if one minimizes the loss function to within $\\tau^2$ of the optimum (regardless of the method used) then the overall error will be proportional to $\\tau$. See line 181 and the definition of $E\\_{\\mathsf{opt}}$ in (3.8). The discrepancy between $\\tau$ and $\\tau^2$ is because we do not consider the squared error in our error bounds (3.3)-(3.5).\n**We will add a short remark about this to line 202-203.**\n\n## '4. Questions about...'\n\n## '1. In experiments...'\n\nGood point. We agree it is uncommon in operator learning to achieve more than 2-3 digits of accuracy. Some of our plots show this type of saturation. This may be related to the tradeoff between model class capacity and the complexity of the optimization procedure for larger values of $m$. Many previous works observed increases in testing error as models are given more training data up to an ``interpolation threshold,'' after which the testing error resumes decreasing, a.k.a. the *double-descent phenomenon*. It is difficult to say whether our results exhibit this phenomenon. Our training setup is not designed to explore this relationship, but rather to ensure the models are trained for sufficiently long (within budget limitations) and saving and restoring the best parameters to obtain as close as possible to a consistent learning procedure. However, we agree that optimization error for larger values of $m$ may be contributing to saturation. A more expansive numerical study would be necessary to fully investigate this issue. We plan to include such findings in future works.\n\n## '2. Dimensions $d = 4,8$...'\n\nGood point. **We will clarify this.**\n\n## '3. All results are...'\n\nYes, we think this is possible and are looking into doing it. However, we feel a full study of this type is beyond the scope of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bjWJhLxska", "reviewer": "Reviewer_4yPo", "summary": "This work examines learning holomorphic operators between Banach spaces. It shows that these learning tasks can be tackled using encoder-decoder approaches with deep neural networks (DNNs), achieving optimal approximation rates up to log factors. The architectures used are problem-agnostic and depend only on the amount of available training data. The study also delves into theoretical aspects of the associated training problem for standard feed-forward networks and presents numerical findings to support its claims.", "questions": "* Perhaps I missed it, but I could not locate a precise reference discussing the holomorphicity of the Navier-Stokes-Brinkman and Boussinesq equations, similar to Section B.3.2. for the Diffusion problem. It would be helpful if such a discussion could be included in the manuscript.\n\n* Could you briefly summarize to what extent Theorems 4.1 and 4.2 require different techniques compared to those used in [7]? How does the use of a general Banach space $\\mathcal{X}$ complicate the analysis?\n\n* Regarding the experimental results, do you have any insights into why different activation functions perform differently across individual tasks? Can this behavior be explained using the results from Theorems 3.1 and 3.2?\n\n* Do the authors think the results from Theorem 3.2 could be extended to include information on optimization procedures used for solving (2.5) (e.g., stochastic gradient descent and variants thereof)? Such an extension would enhance the practical relevance of the result. I am only seeking an educated guess or a high-level opinion, without expecting detailed analysis.\n\n* I would appreciate it if the authors could briefly summarize the differences between the Banach space and Hilbert space cases for $\\mathcal{Y}$. Specifically, could you indicate precisely where the inner product structure is utilized in the proofs to achieve better rates?  Also please double check formulas (3.3) and (3.5) in this context, currently it seems that they are the same.", "limitations": "Limitations and social impact have been discussed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper is well-written and includes a thorough review of current research on learning holomorphic operators.\n* The results are new and interesting, expanding on previous work by addressing holomorphic mappings between arbitrary Banach spaces and allowing standard training methods for the DNNs utilized.\n* Although some assumptions and results are technical, I appreciate how the authors provide a clear overview of their meaning and interpretation. The proof techniques are explained well and summarized in the appendix, making them accessible without diving into deep details.\n* The theoretical findings are also backed up by practical experiments.", "weaknesses": "Overall I do not have any serious concerns about this work and consider it to be a valuable contribution. Some questions are listed below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful review our paper and your positive assessment of it. Here we address the comments in your report.\n\n## 'Perhaps I missed...'\n\nGood point. Right now, we do not have a proof that the NSB and Boussinesq problems satisfy the same holomorphy assumption as the diffusion equation. However, we strongly suspect this to be the case and intend to look into this in future work. **We will add a brief comment about this theoretical gap to the discussion of these equations in Section 5.**\n\n## 'Could you briefly...'\n\nGood question. The proof of Theorem 4.1 is quite similar to that of [7]. The main difference is in the setup leading to the construction in (F.4). The fact that $\\mathcal{X}$ is a Banach space does not substantially complicate the proof, as we make use of the map $\\iota$ to push everything from $\\mathcal{X}$ to $D$.\n\nThe proof of Theorem 4.2 builds on the ideas from [7], but is quite different and more technical. The issue is that the approach of [7] cannot be easily extended to the $L^{\\infty}$-norm. Like in the proof of Theorem 4.1, Theorem 4.2 considers holomorphic functions that are linear in the variables $x_i$, thereby reducing the problem to a discrete one (see Step 2). However, it now deviates in two key ways. First, it uses a more involved splitting -- see the set $I$ defined below line 1623. Second, it now assumes the coefficients in the expansion (G.2) come from the null spaces of certain matrices $\\boldsymbol{A}\\_l$. See the set $\\mathcal{C}$ defined below line 1631. This is done to exploit the following properties: (i) $\\boldsymbol{A}\\_l$ is a subgaussian random matrix, and (ii) vectors in the null space of a subgaussian random matrix are 'flat'. In particular, for (ii) we rely on a result of [77]. We need this more technical argument in order to obtain the lower bound $m^{1-1/p}$. The nonsharp lower bound $m^{1/2-1/p}$ follows immediately from Theorem 4.1.\n\n**We will add some more comments in Section C.2 to explain these differences.** Also, Theorem 4.2 is also of independent interest, since it partially answers an open problem in [7] about proving results in the $L^{\\infty}$-norm. **We will mention this in Section 4.**\n\n\n## 'Regarding the experimental...'\n\nWe generally observe that networks with smooth activation functions (e.g., tanh and ELU) perform better than ReLU networks when approximating smooth target functions such as the mappings considered in this work. In all experiments, we see the ReLU networks perform poorly relative to the best performing ELU ($4\\times 40$ and $10\\times 100$) and tanh ($4\\times 40$) networks. Theorems 3.1 and 3.2 pertain only to tanh networks. However, as we discuss in Remark D.11, a key step of the proof involves emulating polynomials and in particular the multiplication operation in emulating the multivariate Legendre polynomials. Our main theorems can therefore be adapted to other activation functions without change, so long as this emulation is possible.\n\nAs we discuss after Remark D.11, one can also show similar results for ReLU networks, albeit with worse bounds in the depth. This is due to the relation between the depth of such networks and the accuracy of approximate multiplication in the polynomial emulation step.  These worse theoretical bounds broadly agree with worse empirical results, although we do not claim they fully explain them.\n\nOn the other hand, the poor performance of the larger $10\\times 100$ tanh networks is not explained by our theoretical results. Any number of issues could result in poor practical performance. We choose standard optimizers and initializations in this work, however there may be better choices in particular for larger tanh networks. We leave investigation of the best parameterization for such networks to a future work.\n\n**We will add short discussions along these lines to Sections 5 and 6.**\n\n## 'Do the authors...'\n\nWe think this could potentially be done, but this is essentially an educated guess. It is something we intend to look into in the future.\n\n## 'I would appreciate...'\n\nExcellent question. In general, the differences are: (i) when $\\mathcal{Y}$ is a Banach space, we obtain $L^2$-error bounds in the Pettis norm, as opposed to the Bochner norm; and (ii) the approximation error rate is a factor of $(m/L)^{1/2}$ slower than in the Hilbert space case. See equations (3.3)-(3.6). We agree this discussion could have been clearer. **We will modify and expand lines 204-206 along these lines.**\n\nTo explain further. When $\\mathcal{Y}$ is a Banach space, the Bochner $L^2$-space does not have an inner product structure. However, by switching to the Pettis $L^2$-space, we can restore an inner-product-type structure and a Parseval's identity. To be more precise, if $g = \\sum\\_{\\boldsymbol{\\mathbf{\\nu}} \\in \\Lambda} c\\_{\\boldsymbol{\\mathbf{\\nu}}} \\Psi\\_{\\boldsymbol{\\mathbf{\\nu}}}$ with coefficients $c\\_{\\boldsymbol{\\mathbf{\\nu}}} \\in \\mathcal{Y}$ then in the Pettis norm one has the Parseval-type identity $|||g|||\\_{L^2\\_{\\varrho}(D;\\mathcal{Y})} = |||\\boldsymbol{c}|||\\_{2;\\mathcal{Y}}$, whereas an analogous property does not hold in the Bochner norm. This property is crucial to all our analysis.\n **We will add a short discussion of this in Section C.2.**\n\nYou are correct that (3.3) and (3.5) are very similar. The difference is the norm on the LHS, which is the Pettis norm in (3.3) and the Bochner norm in (3.5). So the result for the Hilbert space case is stronger. We already discussed this in lines 204-206, but it could be clearer. **We will amend these lines.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents some results on learning holomorphic operators between Banach spaces using deep neural networks. Theoretical results about generalization bounds and optimality of these bounds are given along with some numerical experiments relating to several different parametric PDEs. Based on the reviews, it is agreed that the strengths of the paper are its powerful, well-formulated theoretical results, its rigorous presentation, and its originality. All reviews furthermore indicated no major weaknesses in the paper, indicating that the results are technically sound and interesting to the community.

Regarding the rebuttal, as all reviews were quite positive, there was little to discuss besides superficial changes (figure sizes, minor clarifications/rewordings). The authors responded to all questions and criticisms of the reviewers sufficiently and the reviewers participated in the discussion as necessary.

Since all reviewers were in agreement with respect to the quality of the submission, I did not see it necessary to have a post-rebuttal discussion.

I recommend accepting the paper.
Decision: Accept (spotlight)