Minimax optimality of convolutional neural networks for infinite dimensional input-output problems and separation from kernel methods
Authors: Yuto Nishimura
Taiji Suzuki
Venue: ICLR 2024 poster (2024)
Keywords: neural network
nonlinear operator learning
convolutional network
estimation error analysis
Primary area: learning theory

Abstract: Recent deep learning applications, exemplified by text-to-image tasks, often involve high-dimensional inputs and outputs. While several studies have investigated the function estimation capabilities of deep learning, research on dilated convolutional neural networks (CNNs) has mainly focused on cases where input dimensions are infinite but output dimensions are one-dimensional, similar to many other studies. However, many practical deep learning tasks involve high-dimensional (or even infinite dimensional) inputs and outputs.
In this paper, we investigate the optimality of dilated CNNs for estimating a map between infinite-dimensional input and output spaces 
by analyzing their approximation and estimation abilities. 
For that purpose, we first show that approximation and estimation errors depend only on the smoothness and decay rate with respect to the infinity norm of the output, and their estimation accuracy actually achieve the {\it minimax optimal} rate of convergence.
Second, we demonstrate that the dilated CNNs outperform {\it any} linear estimators including kernel ridge regression and $k$-NN estimators in a minimax error sense, highlighting the usefulness of feature learning realized by deep neural networks.
Our theoretical analysis particularly explains the success of deep learning in recent high-dimensional input-output tasks.

Published as a conference paper at ICLR 2024
MINIMAX OPTIMALITY OF CONVOLUTIONAL NEU- RAL NETWORKS FOR INFINITE DIMENSIONAL INPUT- OUTPUT PROBLEMS AND SEPARATION FROM KERNEL METHODS
Yuto Nishimura
Taiji Suzuki University of Tokyo RIKEN AIP
University of Tokyo
putonishimuran ecc. ucc.u-tokyo.ac.
tai (0mmmt.t......mmmmm.mm.mmm.m...t wtw.is....tttko.aaee
ABSTRACT
Recent deep learning applications, exemplified by text-to-image tasks, often in- volve high-dimensional inputs and outputs. While several studies have investi- gated the function estimation capabilities of deep learning, research on dilated convolutional neural networks (CNNs) has mainly focused on cases where in- put dimensions infinite but output dimensions many other studies. However, many practical deep learning tasks involve high- dimensional (or even infinite dimensional) inputs and outputs. In this paper, we investigate the optimality of dilated CNNs for estimating a map between infinite- dimensional input and output spaces by analyzing their approximation and estima- tion abilities. For that purpose, we first show that approximation and estimation errors depend only on the smoothness and decay rate with respect the infinity norm of the output, and their estimation accuracy actually achieve the minimax optimal rate of convergence. Second, we demonstrate that the dilated CNNs out- perform any linear estimators including kernel ridge regression and k-NN esti- mators in a minimax eπror sense, highlighting the usefulness of feature learning realized by deep neural networks. Our theoretical analysis provide theoretical basis for understanding the success of deep learning in recent high-dimensional input-output tasks.
one-dimensional, similar
INTRODUCTION
In recent years, deep learning has found applications in a wide array of fields, leading to remarkable progress. Some noteworthy breakthroughs include Stable Diffusion (Rombach et al. (2022h) for text- to-image applications, and Whisper (Radford et al. (2022) for speech-to-text applications. Despite their distinctiveness, these technologies have thing in common: They handle high-dimensional inputs and outputs. This is quite different from the early days of deep learning, which began with AlexNet (Krizhevsky al, (2017) and mainly focused classification tasks with figh-dimensional inputs but only one-dimensional outputs.
The theoretical research of deep learning has studied the approximation and estimation capabili- ties of neural networks. It is well-established that two-layer neural networks can approximate any continuous function with compact support to arbitrary precision (Cybenko (1989); Hornik (199T)) while multi-layer networks have been investigated under more practical conditions, such as functions belonging Hölder or Besov spaces (Petersen & Voigtlaender (2018); [uzuki (2019)). Estimation capabilities of multi-layer networks have also been examined using finite number of samples, with some studies showing nearly minimax optimal convergence rates (Schmidt-Hieber (2020)).
However, these studies often assume fixed input dimension significantly smaller than the size of training data, resulting in the curse dimensionality where convergence rates depend on the input data dimension. This limitation is particularly relevant for recent deep learning tasks, such as processing very long textual, image and audio data, where input dimensions can be extremely large even regarded as infinite-dimensionn

---

Published as a conference paper at ICLR 2024
To overcome this challenge, researchers have focused settings where the data distribution's 's sup-
port exhibits owwddimensional structures (Chen et al. (2019 2022); Nakada & Imaizumi (2020). )- These studies demonstrate that neural networks low-dimensional data structures. (uzuki & Nitanda (022)) demonstrated the ability to overcome the curse of dimensionality even when the input data does not lie on low-dimensional manifold by considering Besov spaces with durection-dependen smoothness, referred to as anisotropic Besov spaces. Nevertheless, the performance of neural networks in extremely high-dimensional or infinite- dimensional settings is still an open question that warrants further investigation.
avoid the curse of dimensionality by exploiting
Okumoto & Suzuki (2021) considered y-smooth space (Def. [ demonstrating that dilated CNNs can achieve approximation and estimation errors that depend only on smoothness, not dimension- ality, for -nfnnse-diimnsiionll inputs. The 7-smooth space is a function space where different coor- dinates exhibit different smoothness, which is inspired by the settings in Düng & Griebel (2016); Ingster& & Stepanova (201T). This research partially explains the great success of dilated CNNS in tasks involving nigh-dimensional inputs. However, including this study, theoretical research on deep learning has primarily focused on one-dimensional outputs, neglecting the situation with high- dimensional outputs. Given that many recent deep learning applications involve nigh-dimensional inputs and outputs, it is essential to conduct theoretical analyses of neural networks in problem settings where both input and output dimensions are high.
In recent research, while there has been limited investigation on deep learning in the context of infinite-dimensionall inputs and outputs, the study of linear operators in such settings has been exten- sively explored. For example, Oliva et al. (2013) 2014) proposed a method for estimating mappings with inputs and outputs as functions or distributions, and showed their convergence rates. In Talwai iet al. (2022). the authors provided convergence rates for estimating linear operators with input and output spaces being reproducing kernel Hilbert spaces, extending the results of Fischer & Steinwart (2020) for one-imeesioonl outputs. Jiin et al.] (222) demonstrated a more general form of linear operator estimation errors by changing the norm used in TTlwai et al. (002),, reflecting the structure of output data spaces. Research on learning a linear operator in intinie-dimennionall input-output settings has also been widely studied in the literature of numerical analysis (Lu et al. (2021) | Li
et al. (b)2 de Hoop et al. (202 ) Li et al. (2018 2021a)) and econometrics (Singh et al. (2019)
Muandet et al. (2020); Dikkala aa et al. (2020).
Additionally, there several studies that have conducted analysis using neural networks targeting nonlinear operators with dimenii-dd input and output spaces. [Cen & Chen (1995) proved that neural networks have the capability of approximating nonlinear functionals defined on some compact set of a Banach space and nonlinear operators. Then, Lu et al. (202T) extended the theory to deep neural networks and proposed DeepONet based on the theory. Lanthaler et al. (2022) conducted a theoretical analysis of DeepONet, providing its approximation and estimation errors. However, their analysis is contingent upon the architecture of DeepONet and is confined limited scope, specifically focusing on learning operators between functions.
Our contributions. In this study, we show the optimality of dilated CNNs by analyzing their approximation and estimation errors in problem setting where the input and output dimensions are both infinite, while existing work did not show the statistical optimality of this problem. We deal with the problem as nonparametric regression problem with infinite dimensional input-output spaces where the true function is a nonlinear operator consisting of an infinite sequence of functions belonging to the so-called 7-smooth space (Dūng & Griebel, 2016 Ingster & Stepanova 2011 Okumoto & Suzuki 2021). The intuition behind this function class can be explained via practical applications such as audio-data conversion. When we convert audio-data, the input and output audio data usually decomposed into the frequency domain (or other audio features such as Mel- frequency cepstrum) and the onput-output relation is often highly sensitive to some frequency bands, which can be formalized by the non-uniform smoothness with respect each frequency component. The 7-smooth space provides a mathematical abstraction of this notion. Then, our purpose is to explicitly verify how advantagcous the CNN structure is to estimate this kind of infinite dimensional non-linear dependency. More specifically, our contributions can be summarized as follows:
1.
We consider nonlinear operator as true function with infinit-ddimension inputs and outputs. In the aforementioned setup, we demonstrate that dilated CNNs achieve approximation and es- timation errors that depend only on the smoothness and decay rate of the output. Furthermore,
2

---

Published as a conference paper at ICLR 2024
we show that the estimation errors minimax optimal. To the best of our knowledge, this is the first study that establishes the minimax optimality of deep learning models in the setting of input and output. Technically, mal rate by providing a covering number of spaces that have decay in its 1.2 norms of the outputs, and this framework can be applicable to other function classes well.
show lower bounds on the minimax opti-
2. We show that dilated CNNs are adaptive to the unknown smoothness structure, that is, it auto- matically achieves the minimax rate without the knowledge of the smoothness structure of the true target functional. To show how crucial this adaptivity is terms of the predictive error, we compare the predictive performance with the class of linear estimators as a counter part of non- feature learning methods including kernel ridge regression and k-NN estimator. Indeed, we show that the worst case enror of any linear estimator is outperformed by dilated CNNs. This result highlights the usefulness of neural network- -base feature extraction.
These results demonstrate that dilated CNNs achieve the minimax optimality with polynomial order sample complexity, even when both the input and output dimensions are dimniteddimessional. Fur- thermore, dilated CNNs are found to be superior to linear estimators. These findings underscore the significance of dilated CNNs' feature extraction abilities. This theoretical analysis partially explains the success of deep learning in recent high-dimensional input-output tasks.
2 PROBLEM SETTING AND NOTATIONS
In this section, we set up our problem setting of the nonlinear operator learning. First, we explain the notation used throughout this paper. Let Ry0 == {s R s 0}. and for set D, let D := ((81,..., Si,.
8; D). For E D we define supp (a) == # E 8; OO. We then define No == E (0) supp (1) < 5o) and similarly define TR zz. Furthermore, for s E N6. we let 2" = 2 81 For a E I. [a] is the largest integer less than or equal to a, and [a] is the smallest integer greater than or equal to a. Additionally, for L E N, we let [2] := (1......4 L).
Problem setting Let À be the Lehesgue measure on ([0, ([0 12). where B ((.. 1]) is the Borel o-field on [0, 1]. Let 1 be the product measure defined on ([0, 1] _jj" II B ([0, 1})) obtained as
the countably infinite product of X. Such measures exist uniquely by the Kolmogorov extension theorem. Let M == j0, 1 Let Px be probability measure defined on M that is absolutely
continuous with respect to X and let its Radon Nikodyy derivative satisfy || 1 1 (M))
< co.
Then, we assume that there exists a true nonlinear operator fo M + R such that the in- put and output have the following nonlinear relation: (1) Y (X) + &, where X is ran- dom variable that takes values in M obeying the distribution Px. and 5 E R is an observation noise such that each component is independently following a Gaussian distribution with mean 0 and bounded variance. In this study, we discuss (i) how efficiently neural networks can approxi- mate the true operator fo, and (ii) how accurately neural networks can estimate the true operator fo from n observation data Dn (z y ( )= C MMxB 18
We use the mean squared er- ror Ilf - 1- == Ep [Ilf (x) - f 12 = Ep (1)) fj (z))²] as performance metric for learning operators. Here, P denotes the joint distribution of the random variables X and Y.
Notations. Next, we define the 7-smooth space (Okumoto & Suzuki 2021)) ). For l E 20, x (rr),= E MM, we define
V2 cos (2mT |4| x:)
(4 < 0),
w/ (x) = 1I t4 (I:), Ui, (zx) = V2 sin (2T 14 x4)
(4 > 0),
(4: = ()-
Then, let La (M) = Mf: Lu f dx (x) < oo) equipped with an inner product (f.g) = (z) (z) for f.g E La (M). Here, the set (VI)) forms an orthonor- mal basis of this space (Ingster& & Stepanoval 2011, and thus any f E L (M) can be expanded as f()) = EiERy (i For s E No. we define 5, (f) R + R by 5, (-) == ( (J, th) (.), which can be interpreted as the frequency components of f
corresponding to frequency of [4] ~ 2 Let J (8) (1 E Zg | & |44 2%%
3

---

Published as a conference paper at ICLR 2024
For 2 1, if we define I|ʃl = (JM dxx)), ,, then y-smooth space can he defined as follows: Definition (7-smooth space). Let p, & 2 1, and 7 : No + I be a monotonically increasing function for each component. Then, the y-smooth space is defined Fp.
(M) IIf < <00), whose norm is [1, = (Ioety (2n(.) 16 (fII,)
We can see that the function 7 plays a kind of penalty on each frequency component of the functions in the class; that is, a frequency component with large 7(s) should be suppressed so that the norm is bounded. In that sense, the design of 7(s) is crucial to control their smoothness. In this study, we focus on two types of y functions as in Okumoto & Suzuki (202T).
Definition 2 (Mixed smoothness and anisotropic smoothness). Given sequence a (a:); R50- mixed smoothness is defined as 7 (s) = (a, where (a, 8) anisotropic smoothness defined as 7 (8) = maxie {a,81).
000 0,8,. Moreover,
Intuitively, a represents the strength of penality on each frequency. Indeed, each dg can be interpreted as the smoothness toward the i-th coordinate. More technically, it known that when y has mixed smoothness or anisotropic smoothness, the 7-ssmooth space becomes an extension of mixed Besov space (Schmeisser (1877) or anisotropic Besov space (Nikol skii (1755) to an infinite dimensional settings, respectively (Okumoto & Suzuki (202T))
Based on the y-smooth function class, we define a class of nonlinear operators from M to R First, let (L2 (L2 (M)) oc : =f;:M
SM llf (x)]l dA (x) < xo equipped with inner (x) by an abuse of notation. Then we define class of operators (F7.4) )000 as follows: (=%)))= E (L2 (M)) Vie N, Ilfill,y, c0)
product (f.9) IM
(1))))
which is an extension of the 7-smooth space to an infinite dimensional output setting. In this study, we mainly discuss nonlinear operators that belong to this space.
Assumptions. Next, we impose assumptions on the true nonlinear operator for theoretical analysis in this study. The following assumption imposes a norm control on each component f of the target function:
Assumption 3. We assume that the true nonlinear operator fo satisfies the following condition for some p 2 1, 2
f = (i)) E (F))))
(F..g)
(2)
where 7 is the mixed or anisotropic smoothness. Furthermore, there exist constants B3 > 0, Bo O and 0 < r < 1 such that
>
11 S B |1 S Bo
(NEEN).
(3)
We let B, be the subset of (M)) satisfying the condition 3
Here, we define the T.-normm as || =
di (x)) for f : R by an abuse
when p co. Note that 11:112 < |1 Since Px satisfies the assumption of absolute continuity and the finiteness of the Radon-Nikodym derivative with respect A we have 11-11 11-111 Okumoto & Suzuki (022)). Suzuki We also impose the following assumption on the observation noise:
of notation. In particular, we set || = >m [|
Assumption 4. Each component of the observation noise & (E)) R is assumed to be independent and follow Gaussian distribution as ~ V (0, of) where of is uniformly bounded by /² 00.
These assumptions posit that the true function values tend to approach zero as the index increases. Without such assumptions, there would be issues such as the accumulation of estimation errors in the outputs corresponding to each index leading to divergence. It is still a future task to weaken the assumptions by changing the norm used for evaluation, in Din et al. (2022). , An intuition behind this assumption can be obtained by considering speech synthesis task, for example. Suppose that the output data is decomposed into the frequency components. Then, the index corresponds i-th
frequency. The assumptions above corresponds to situation where the amplitude of the true signal decreases as the frequency increases.
We denote by U(X') the unit ball of normed vector space X.
4

---

Published as a conference paper at ICLR 2024
3 APPROXIMATION AND ESTIMATION ERRORS OF DILATED CNNS
In this section, we analyze the approximation and estimation errors in learning nonlinear operators using dilated convolutional neural networks (CNNs). First, we define the dilated CNNs, which is model that consists of convolutional layers followed by fully connected layerss.. We begin by defining the fully connected neural network (FNNs).
Definition 5 (Fully connected neural network (FNNs)). Let L E N be the depth of the network, and i 1, 1.2..... . + 1, d E N be the width of the i-th layer. Then, the model defined by (z) (A (.) + by) 0...0 (Am (-) (+)+00 o.)..... (A1 + b1). where 17 (+) is the ReLU activation function and A, E I Rd4+ixd b, E [R4,,,, (z) = max {x, 03. This model is called the fully
connected neural network (FNNs).
We also consider the following collection of FNNs using some constants W E N, S SEN, N, B >
① (L, W, W) = {f()) (x) (ALT (+) + bb) o (Am (-) + b....... (A1r + b1)
max i=I..., L || V |belloo S B, Σ |A:llo + 11b:l0 I S,
max d $ W i=I...,L+ L+1
where I1- returns the maximum absolute value of a vector/matrix and |1-Il, returns the number of nonzero elements of a vector/matrix.
This collection of FNNs is an extension of the collection of FNNs for one-dimensional output an- alyzed in Bölcskei et al. (2019). Suzuki (219)) and Schmidt-Hiebeud (2020) to the case of multi- dimensional output. Therefore, unlike these previous studies, the assumption that dL+1 = is not made, and is treated similarly to other variables.
Next, we define the dilated CNNs. Let C E N be the number of channels. We define Rx == RC]. Let W E N be the filter width, and w RCWW" be filter and X = (1 E Cxx0 be the input. Then, for an interval h E N, we define the dilated W
(#1..... Ii....): D4
convolution * X E R as (w k X)x =- E Ej=1 Wi.Jia,MGG))+ Note that this coincides with the usual convolution when h = 1. Here, let C' N be the number of output channels, and F IR C3'''XXW' be filter. Then, we detine COnvA,F CCx - Cxxx Convi, (X) (Fi., th ,.....Fe *h x)² Using these notations, we define the dilated CNNs as follows.
Definition 6 (dilated CNNs). Given constants L', W E N. and filters Fi E XCx4 with channel numbers Ci E N for / E [L'], where C₁ = 1. Then, we define the dilated CNNs as f = JENN o (Convwi''-1,F; .F,, o... Conv o... Conv1.F, o xx); where JPNN E ① (L. S, B) is FNNs with input RC and output gENN (I) E RdL11, In other words, it is important to note that / is function from the input space M to Rdu+1,
We also define the set of dilated CNNs with constant B' > C CE as follows:
PLI, W,C.B,WWWCWWWWW S, B) =
- {JENN o Fi E RCXCXW (12 2), Fi EEER RCIIIW" ||F S B', 9ENN E 1 (L, W. W.)
(Conv WIZW11 FFF .... Conv o xX)
where we assumed C = (1 2) to fix the number of channels in each layer.
When considering estimation errors, becomes important to make use of boundedness of the esti- mated function in terms of ||+ Therefore, we define the set of bounded CNNs with Bg > 0 as P = P P==P(
(B2, I', B', W', C. I, W.S, B), where
P (1(0)) = {-
- BBi v ( (1 d(+1) :SpP (de+1 <)
where P = PL', B',W', ",, ,CC, B)S.B.. Here, f E is a function f : M + R which naturally extends the output of / P from d xc.
5

---

Published as a conference paper at ICLR 2024
3.1 APPROXIMATION ERROR OF DILATED CNNS
Here, we analyze the approximation error of nonlinear operators using dilated CNNs. In the case of the learning of functions with one-dimensional output (ʃ E F...). the approximation error is shown in Okumoto & Suzuki] (202T). Here, we extend their results to infinite dimensions.
Before doing so, we introduce the following definition for a.
Definition 7 (Definition of smoothness). (i) A sequence a is said to increase in polynomial order a (as) is a monotonically increasing sequence of positive real numbers, and there cxists a constant 7) 0 such that a, S2 (i"), and a1 < 0g. (ii) Furthermore, is said to have sparsity = (==) is a sequence of positive real numbers satisfying a; = -2 (log i), and there exists constant > 0 such that the sequence (a,,);== obtained by sorting {a: f== in ascending order satisfies ||a] == sup, j",a," 1.
The first setting is the casiest setting where the "importance" of each coordinate monotonically increases as the index increase, where the importance is measured by the smoothness a;, On the other hand, the second setting is more challenge where we need to find important features with small a, from wide range of coordinates. The theorem including this assumption for the approximation error is shown below.
Theorem 1 (Approximation error of nonlinear operators by dilated CNNs). Suppose the true non- linear operator f & (Fra) @ satisfies Assumption If a increase in polynomial order, we set =, B' = 1, W ~ T C T and if a has sparsity, we set L' ~ T. B' = 1, W = 3, C ~ Tē. (i) (mixed smoothness) If y has mixed smoothness, let at = 0g where i' = when increases in polynomial order, and = i when a has sparsity; (ii) (anisotropic smooth- ness) If y has anisotropic smoothness, let at
)))) Let = max 2 0 and assume at. Then, for any T > O, we set L (T) max [ T2 r2 (T)
max {T 21(1-317 (T) T T J. B (T) 2(T/2)7 Then, there exists
dilated CNNs /' E P (B2, L', B', W C,L,
(T), B (T)) such that the following
evaluation obtained:
- S 2 (1-r/ -1-
Unlike existing results such as Okumoto & Suzuki (2021), this theorem covers a setting with infinite dimensional output. As a result, there appears following difference: (i) The first difference is the rate of convergence. For example, the result in Okumoto Suzuki (2021) || fll2 S 2 (1-0/al)T) while in this study it is || f < 2 (1111//2(11-/// which increases by factor r. (ii) The second difference is the setting of the parameters W and S in the neural network, where the number of weights in the output layer, 2r(1-u/a')r is newly included compared to Okumoto & Suzuki (2021) In both cases, these differences arise from the requirement to increase the output dimension d++1 significantly, such that Ei [| can be negligible in comparison to the other errors. Despite these differences, the core message from the theory remains the same: by assuming the decay of the output, the approximation error can be of polynomial order even when the output is in an dimnitt-dimensionall space.
We also discuss the differences between existing work on estimating linear operators and our ap- proach. According to Fischer & Steinwart (2020), the rate of approximation error for function in a certain RKHS with respect to the true function fü == E [Y = æ]] defined on the data space X XxX Y is given as 8-7 (Lemma 14 of Fischer & Steinwart (020)). On the other hand, Talwai et al. 2022) extended this result to the case where the true function represented by linear operator Cyix HK + Hy, In this case, the approximation error given as - (Lemma
Talwai et al. (2022)). Here, it is assumed that À is sufficiently smaller than 1 and B - > O. Therefore, it can be said that the rate deterioration due to the extension to infinite dimensions occurs in the case of linear operators, similar to results. Although the specific changes may differ due to vary- ing assumptions and problem settings, the shared characteristic of deterioration in both cases is an intriguing implication.

---

Published as a conference paper at ICLR 2024
3.2 ESTIMATION ERROR OF DILATED CNNS
Here, we analyze the estimation error of dilated CNNs based on the approximation error anal- ysis in the last section. Now, suppose that we given observation data points D, (xl0, = following the model (L. We consider the following empirical risk minimization (ERM) estimator: f E argmin t Ei (z;) - 3:1f²= As mentioned earlier, we use the mean squared error - as the evaluation metric for this estimator. Since f depends
on the data D.. we calculate the expected value with respect to Dn: Epn [|] - 1
E ((0))) - - f(
First, we give lower bound of the minimax optimal rate in the following theorem.
Theorem 2 (Minimax optimal rate for estimating a function in the (FE.g) ") Assume that 2 2, Px is uniform distribution over M. accordance with the definition used in Theorem I the same notation. Then, the minimax optimal rate is lower bounded as follows:
we use
E.D.. [|I - 1 2 n 201
12 mia!
inf sup ((((()))))))
where "inf" is taken over all estimators based on D, and the expectation is taken for the sample distribution.
We see that the minimax rate is merely characterized by the smoothness parameter a² and the decay rate r. To prove this theorem, we utilized the classic information theoretic lower bound (Yang & Barron 1999 Raskutti et al. 2012). To do so, we carefully evaluated the covering number of the function space by taking the decay of L (Ilff (22) into account, which very unique to our problem. We believe that this framework can be extended to Cartesian product spaces consisting of other function spaces as well.
Then, we derive the upper bound of the estimation error of the ERM estimator on the class of dilated CNNs and see its optimality.
Theorem 3 (Estimation eπror of nonlinear operators by dilated CNN). Assume that the true nonlinear operator f (Fr.)) satisfies Assumption 3 If increases in polynomial order, set T'' = 1, B'
W (logn)², C ()ogn) = Otherwise, if has sparsity, set L' ~ log n, B' = 1, W = 3, C ~ (log n) In accordance with the definition used in The- orem 1 we use the same notation for at, ut LTT), W (T),, S(T). and B(T). For log, n, let (L, W,S, B) =)==( (T), (T) ( (T), ( (T)). Then, the ERM estimator f achieves the following estimation error:
(at-))
Ep [ 1 Px S 2(ut-o)42 (log +2 max { (log ,log m)*
Because of this theorem, we can see that dilated CNNs can achieve the minimax optimal rate in the regime of 2 2 (i.e., v = 0) up to poly-log order. Comparing with the single output setting (The- that there appears r in the rate of convergence
orem 10 in Okumoto & Suzuki (222I), we -00 while that for the single output achieves -2(a" (e)at=a)(((""" -1)+1 polyloooy)g()) As increases (i.e., the decay is slower), the rate becomes slower, which is intuitively natural because we need to estimate more output functions accurately leading to more difficult problem. We emphasize that our result shows the minimax optimality of dilated CNNs including the effect of which is not trivial.
Lanthaler et al. (2022) provided an upper bound on the estimation error using DeepONet, solving dimentiondi problems based on the assumption of Lipschitz continuity, with the additional condition of input decay. Their approach relies on the assumption of the DeepONet model. In contrast, demonstrated estimation errors in more general and widely applicable context using dilated CNNs. Importantly, we established that our approach shows the minimax optimality.
According to these theorems, found that, dilated CNNs can achieve dimension independent timation error depending only on at. It means that dilated CNNs can extract the feature whose direction has small values of a even when (a:) is not monotonically sorted. This is due to the
7

---

Published as a conference paper at ICLR 2024
feature extraction abilitty of dilated CNNs that can adatipvely find important features by training data. In the following section, we will discuss how this intuition serves to contrast dilated CNNs with linear estimators such as kernel ridge regression.
Limitations. One of the limitations of our research is that all of the aforementioned theorems de- pend on the assumption that p 2 2. This arises directly from the proof of Lemma 11 in Appendix B.2, specifically from the evaluation of (.))). The difficulty in evaluating 6x()) has also impacted prior research. For instance, in Okumoto & Suzuki (20TT, which presented the approximation error of one-dimensional output in dilated CNNs, the term e used in our study is incorporated due to this evaluation. In this study, we consistently used the assumption p 2 align with previous research, but revisiting this assumption will be part of our future work.
4 COMPARISON WITH LINEAR ESTIMATORS
In this section, we compare the estimation error of the dilated CNNs obtained in the previous sec- tion with those of the linear estimators (Korostelev & Tsybakov (1993); Immaiuum & Fukumizu 2019)). ). An estimator f based on (x', y )==1 is said to be linear if it can be expressed in the form of (f)), >h= My pys (z;=") (Vj E N). This estimator class includes several practical es- timators such as kernel ridge regression and the Nadaraya- Watson estimator; indeed, kernel ridge estimator is given as f(x) = (K(K + A which is linear to Y. Then, we demonstrate that under certain conditions, the dilated CNNs outperforms linear estimators.
The biggest drawback of linear estimators is that they cannot perform feature learning. To investigate this properly rigorously, we parameterize the range of important features and how it affects the estimation accuracy. It is expected that the range of important features becomes wider, the linear estimator suffers sub-optimality due to their disability of feature learning. To justify this intuition, we introduce the following set of a, denoted by r.
Definition 8. Let 0 < 6 < and > be given and fixed. (i) For mixed smoothness, suppose that and be constants such that 21 0 < 2g- 1, and define
Q.T = a(a 1/2)/ (eloggc"))
(4)
(ii) For anisotropic smoothness, suppose that constants and e satisfy 20 (11) < and 0 < <c< a/2 1 where à : g=n(((n) and ((1) =- >m== n "1 Then, we define
Q- = =2njaa ((211+ c) (nā + -1 logg e -1 + a 1-1//1 (log2 é -1
(2
(5)
For Q = Q. or Q = Qa, we define the set of possible values of a as (Q) {a: a, 2 Q log, i, ||alludn S a-1).
This definition extends the concept of sparsity for (see Definition 7. In essence, I' represents a set of a values that exhibit sparsity and are greater than specific minimum value. We can see that the parameter& e controls the minimum value of through Q(= Q Q?). Indeed, as becomes large, the lower bound of a; becomes smaller, which indicates that the range of coordinates with small smoothness parameter a, (in other words, important features) is widely spread out. Such a situation is more difficult for the linear estimators while deep learning approach can adaptively specify important features from wide range of coordinates. This yields separation between deep learning and linear estimators.
Using the I' defined above, we define the union of 7-smooth spaces over the choice of in l'. By considering such a set as the space containing the true function, it is expected that the feature extraction abilities of dilated CNNs will be demonstrated.
Definition 9. Let the set of possible values for a be I, and define (Fp. (T)) as follows: (Fn. (T)) 0 := Uner (F%)) 00 Also, let U ((F p.n (T)) = Uner (U (F), p.g
It is known that the minimax rate in the class of linear estimators is same as that on the conver hull of the target function class (Theorem 3.3 of Hayakawa & Suzuki (0220). Since the union of y-smooth spaces over different values of a becomes highly non-convex, it is expected that the linear estimators suffer from sub-optimal rate on the space (F, p.g (T)) Indeed, we obtain the following lower bound of estimation errors for linear estimators.
8

---

Published as a conference paper at ICLR 2024
Theorem 4 (Estimation error of linear estimators in (F2, (T)) Let r = = (Q")) and a" when Y is mixed smoothness (7 (s) = (a, s)), and let = (Q+) and a = ā when is anisotropic smoothness (y (s) max; )). Then, the minimax rate over the class of linear estimators is given as follows:
sup ED. [ 1 1112(())) n 20 fdinear (EU)((F,)( ,nB
inf
This result achieves rate that is larger by factor of which has not been in existing analyses such as for Besov spaces (Donoho & Johnstone 1998| Zhang et al., 2002). . As we have mentioned, this is due to the fact that the linear estimators cannot perform feature learning. More technically, the convex hull of the class ((F2,2 (T))²² become much larger than it as becomes larger.
Remark 5. In the finite dimensional Besov space setting, it has been shown that DNN approach achieves the rate independent of due the adaptivity of DNNs to local smoothness structure while the linear estimator suffers from sub-optimal rate due to the term (Suzuki 2019) Suzuki & Nitanda 2021). However, is still an open problem whether DNNs can achieve the rate without the term 2 in our infinite dimensional setting. Then, we employed different strategy to show the separation between the dilated CNNs and linear estimators, that is, we considered a larger function class by controlling r.
As in Theorem
we can easily show the following upper bound for the extended class (F2,2 (T)
Corollary 6 (Estimation error of extended CNNs for (F2.2 (T)) )) In accordance with the definition used Theorem 4 we define and utilize r, % (s). and at. Also, the true nonlinear operator f
satisfies f E U ((F2,2 (T)) (T)) and Eq 3 the estimation error of dilated CNNs is given as follows:
Epn [1 10-
S n
(2-ria"
(logn)
Px
From the above corollary, we can compare with the estimation error of linear estimators obtained in Theorem 4 The following theorem states this comparison.
Theorem (Superiority of dilated CNNs over linear estimators). Assuming the same conditions as
Corollary when condition e However, note that is necessary for 20"-1 a exist such for I = I (Q""), .o (s) a 2 to exist such e for I
(2a" +1)r is satisfied, dilated CNNs outperform linear estimators.
2-r
(a, s) and a* = a. Also, it is necessary for r I' (Q2)) Ta (s) max, {a,s:). and a*
In previous studies, the superiority of deep learning over linear estimators, among others, has been attributed to the adaptivity of deep learning to spatial inhomogeneity (Imaizumi & Fukumizu (2kumiiuu(2019)) mentioned at the beginning of Section 4.1, the approximation error of dilated CNNs is derived using a non-adaptive approach in this work. Even in such cases, demon- strating the superiority by leveraging the feature extraction abilities of dilated CNNs represents novel perspective to highlight the advantages of deep learning.
Suzuki 2019)). However,
5 CONCLUSION
In this study, investigated the performance of dilated CNNs in infinite-dimensional input and out- put spaces. Our primary findings revealed that the convergence rates of dilated CNNs depend solely on the smoothness and decay rate of the output, when considering nonlinear operators composed of a countably infinite sequence of functions belonging to the y-smooth space, and the convergence rate achieves minimax optimality. Additionally, we showed that dilated CNNs outperform linear methods in cases where the smoothness of the 7-smooth space varies, emphasizing the advantages of neural krtwork-based feature extraction. These results provide a theoretical basis for the success of deep learning in high-dimensional input-output tasks and highlight the potential of dilated CNNs in handling complex data. As for future work, several directions can be pursued, including: (i) demonstrating the rate of approximation errors for dilated CNNs using adaptive methods, and (ii) extending the analysis to models other than dilated CNNs, exploring their performance in similar ciinite-dimensiona input and output settings.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
YN was partially supported by JST CREST (IPMJCR2115). TS was partially supported by JSPS KAKENHI (20H00576) and JST CREST (JPMUCR2115).
REFERENCES
Helmut Böleskei, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 1(1): 45, 2019.
Minshuo Chen, Haoming Jiang. Wenjing Liao, and Tuo Zhao. Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. Advances in Neural Information Processing Systems, 32, 2019.
Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. Nonparametric regression on low- dimensional manifolds using deep ReLU networks: function approximation and statistical recov- ery. Information and Inference: A Journal of the IMA, 11(4):1203-125 1253, 03 2022.
Tianping Chen and Hong Chen. Universal approximation to nonlinear operators by neural networks with arbitrary activation functions and its application to dynamical systems. IEEE Transactions Neural Networks, 6(4):91 01999111911, 1995.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Con- trol, Signals and Systems, 2(4):303-314, 1989.
Maarten V de Hoop, Nikola B Kovachki, Nicholas H Nelsen, and Andrew M Stuart. Convergence rates for learning linear operators from noisy data. arXiv preprint arXiv:2108. 12515, 2021.
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation con- ditional moment models. Advances in Neural Information Processing Systems, 33:12248-12262, 2020.
David L Donoho and lain M Johnstone. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879-922 9219,992111111 1998.
D. Yarotsky, Error bounds for approximations with deep relu networks. Neural Networks, 94:103- 114, 2017.
Dinh Düng and Michael Griebel. Hyperbolic cross approximation in infinite dimensions. Journal of Complexity, 33:55-88, 2016.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algo- rithms. The Journal of Machine Learning Research, 21(1):846488001 2020.
Satoshi Hayakawa and Taiji Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-361, 2020. 2020.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, (2):251-257, 1991.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effec- tively. In International Conference on Artificial Intelligence and Statistics, pp. 869-878. PMLR, 2019.
Yuri Ingster and Natalia Stepanova. Estimation and detection of functions from anisotropic sobolev classes. Electronic Journal of Statistics, 5:484-506, 2011.
Jikai Jin, Yiping Lu, Jose Blanchet, and Lexing Ying. Minimax optimal kernel operator learning via multilevel training. arXiv preprint arXiv:2209.14438 2022.
Alcksandr Petrovich Korostelev and Alexandre B Tsybakov. Minimax Theory of Image Reconstruc- tion, volume 82. Springer Science & Business Media, 1993.
10

---

Published as a conference paper at ICLR 2024
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84 90, 2017.
Samuel Lanthaler, Siddhartha Mishra, and George Karniadakis. Error estimates for DeepONets: deep learning framework in infinite dimensions. Transactions of Mathematics and Its Applica- tions, 6(1).maa001,, 03 2022.
Zhi-Zhou Li, Yi-Chen Tao, Xue-Dong Wang, and Liang-Sheng Liao. Organic nanophotonics: self- assembled single-crystalline homo-/hhterostruccuurss for optical waveguides. ACS Photonics, (9):3763-3771, 2018.
Zhizhou Li, Chun Yan Gao, Dingkai Su, Chuancheng Jia, and Xuefeng Guo. Principles molecular machines at the single-molecule scale. ACS Materials Letters, 3(10):1444-1000 2021a.
Zongyi Li, Nikola Borislavov Kovachki, Kamyar Azizzadenesheli, Burigede liu, Kaushik Bhat- tacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differential equations. In International Conference on Learning Representations, 2021b.
Lu Lu, Pengzhan Jin, Guofei Pang, Zhongqiang Zhang, and George Em Karniadakis. Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators. Nature Machine Intelligence, 313)2218-22, 2021.
Yves Meyer. Wavelets and Operators, volume 1 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1993.
Krikamol Muandet, Arash Mehrjou, Si Kai Lee, and Anant Raj. Dual instrumental variable regres- sion. Advances in Neural Information Processing Systems, 33:2710-22222 2020.
Ryumei Nakada and Masaaki Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality. The Journal of Machine Learning Research, 21(1):7018- 7055, 2020.
Sergei Mihailovic Nikol'skii. Approximation of Functions of Several Variables and Imbedding The- orems, volume 205. Springer-Verlag Berlin Heidelberg, 1975.
Sho Okumoto and Tajji Suzuki. Learnability of convolutional neural networks for infinite dimen- sional input via mixed and anisotropic smoothness. In International Conference Learning Representations, 2021.
Junier Oliva, Barnabás Póczos, and Jeff Schneider. Distribution to distribution regression. In Inter- national Conference on Machine Learning, pp. 1049-1057. PMLR, 2013.
Junier Oliva, Willie Neiswanger, Barnabas Poczos, Eric Xing, and Jeff Schneider. Fast function to function regression. arXiv preprint arXiv:1410.7414 2014.
Dmytro Perekrestenko, Philipp Grohs, Dennis Elbrächter, and Helmut Bölcskei. The universal ap- proximation power of finite-width deep relu networks. arXiv preprint
2018.
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep ReLU neural networks. Neural Networks, (08:296-330, 2018
Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. arXiv preprint arX1v:2212.04356, 2022.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of Machine Learning Research, 13 (2), 2012.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 10684-10695, 2022.
H. J. Schmeisser. An unconditional basis in periodic spaces with dominating mixed smoothness properties. Analysis Mathematica, 13(2),153-168, 1987.

---

Published as a conference paper at ICLR 2024
Johannes Schmidt-Hiebel Nonparametric regression using deep neural networks with ReLU acti- vation function. The Annals of Statistics, 48(4):1875-1897, 2020.
Rahul Singh, Maneesh Sahani, and Arthur Gretton. Kernel instrumental variable regression. Ad- vances Neural Information Processing Systems, 32, 2019.
Taiji Suzuki. Adaptivity of deep ReLU network for learning Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Rep- resentations, 2019.
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. Advances in Neural Information Processing Systems, 34: 3609-3621, 2021.
Prem Talwai, Ali Shameli, and David Simchi-Levi. Sobolev norm learning rates for conditional mean embeddings. In International Conference on Artificial Intelligncee and Statistics, pp- 10422-10447. PMLR, 2022.
Martin J. Wainwright. Vigh-DDmensiooal Statistics: A Non-Asymplotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Yuhong Yang and Andrew Barron. theoroi determination of minimax rates of conver- gence. The Annals of Staristics, 27(5): 1999.
S. Zhang, M.-Y. Wong, and Z. Zheng. Wavelet threshold estimation of a regression function with random design. Journal of Multivariate Analysis, 80(2):256-284, 2002.
12

---

Published as a conference paper at ICLR 2024
A PROOFS OF THEOREM AND 3
Here, we present the proof of the theorem that provides an approximation error and estimation error using dilated CNNs. These proofs are essentially extension of the results in Okumoto & Suzuki (022), which demonstrate the approximation error and estimation error in one-dimensional output, to the case of unfnite-dimensionn output.
A.1 PROOF OF THEOREM
We begin by showing the proof of Theorem T which demonstrates the approximation error of di- lated CNNs. Before delving into the main topic, we introduce several symbols and provide their definitions.
Definition 10 (Axial complexity and frequency direction complexity). Let T' be a constant and 7 No + IR>o be a smoothness function. We define the set
I [TT, == (i E N: 3s E N5: & + 0, 7 (8) < <),
and we define the axial complexity for I(T, 7) as follows:
drnax (T,7) = 17 (T)
Furthermore, the frequency direction complexity defined as: fma (T,7) SENS <T) KEN
max max 8t.
The axial complexity represents the number of necessary inputs when evaluating the restricted infiniteddimensional space where >(s) < T. Similarly, the frequency direction complexity indi- cates how far the evaluation needs extend in terms of frequency when the space is restricted.
Furthermore, we introduce the following symbols:
2
- p
(7)
= sup E G(T,)) >ENG 7()
Σ
2",
SEND
ST
where (x)+ max {x, 03.
Now, in order to provide proof for Theorem T we show the following theorem:
Theorem 8 (Approximation error of FNNs). Let y, 7 No R satisfy
7 (s) (s), ea (7) < 1, va (7') <
0c satisfies Assumption and assume that the true nonlinear operator 1 E (F7,))
For any T > 0.
define (dmax Smax: G) as follows:
(dmax, J Smax, G) (dmaxx (T,7), Sunx G(T,), (15452), (2<
(dmax (T,7), (T,7",
And for constants K, K' > 0 depending on B2 and r, we set:
2K max & 2 (log G)² llog lllgg fmax]. W = max 21dmax (Bz)" 2r(1 27(1-
1764K (B2)" & max { (de (dmaxx T2, (log G)2 log fmax, 21(1- } G, B
(V2) daax
K'.
In this case, there exists an FNNs Ar 4 (L, W, S. that takes dimxenimmnsional inputs and returns d dimensimnnoo outputs, and for x = (x:;), E M, we define I" (x) : M + g as follows:
(f' (1())), = = { (mm)eraa)) (1 (ii))
(d1+1 < i),
where dr+1 = =((B)² 2r(1-va)) J. Then, we obtain the following inequality:
2 (1 (1-5)(1-ww)) ())0)))))
(1
If' - 1f 5
2 (1- ;) (1-va())))
21" 1/2-1/9 (2<9)
13

---

Published as a conference paper at ICLR 2024
The proof of this theorem is given in A.1.1
Note that, in Theorem the symbols L', B', W', C, at should be defined depending on the conditions and 7. Indeed, remember that there two different settings regarding to (i) cannomial-order-nneeeee
setting, and (ii) sparse setting; and as for 7, there are two settings: (i) mixed smoothness and (ii) anisotropic smoothness. Then, each quantity should have different definition according to the combination of the conditions on a and y.
However, it is worth noting that the proof itself is nearly identical to that presented in Okumoto & Suzuki 2202T) with the only difference being the use of Theorem g instead of Theorem 7 in Okumoto & Suzuki (202T). Therefore, in this paper, provide only the proof for the case where increases in polynomial order and y is of mixed smoothness. The same argument is also applied to the other settings.
Proof of Theorem 7 (In the case where increases in polynomial order and is of mixed smooth- ness). First, we discuss the case 1 I < 2. According to Lemma in Okumoto & Suzuki 2021, obtain the following bound:
00
G (T,,))
Σ
2
Σ
2
2
sENg <
SEND (
x aj
Furthermore, since a is monotonically increasing and aj = !(i)),. we obtain:
E
81 dmax T fuax T. (a.s)
sup N
01
Now, by using the filter w E gxx1xw" with the width W = dmax the number of output channels C' dmax and the number of input channels C" 1 given by
{
1 (i ii=)) f)
Wi...
(i f)
for i,j E [dmax], we can see that
21
(Conv1,w (X))
Ldmaa
By Theorem
8 if we set
T T:2) r²].
L = 2K max
1
T22 (Bz)" (2))22((1-20) (1(===)
W max 21
-(a;-a1)
1=2
1
2
T (12n(1-a;) (1-2))
S = 1764K (B2)"
(6,
41)
1=2
2
n K'
B = (2)
where K, K" > are constants, for true function f (U (Fra)) satisfying Assumption 3 there exists an FNNs îr (L, W, B) such that
-{ R (Conv1, (x))),
(1 (isi d1+1), (d <i),
where dr = [(B2)" 2r(1-va)T J. satisfies
115" - - (1-))=)(--=
14

---

Published as a conference paper at ICLR 2024
Here, by defining (f' (X)), == (= -B (f" N), f can be represented as a dilated CNNs f' E P (B,, ,', W C, W. S, where = B' 1, and W =
dmax-
Furthermore, from Assumption we obtain a following relationship:
Ilf' - fl12 s Ilf" f012 (1-
Thus, the theorem's statement is proven.
Next, we consider the case of > 2. In this case, let a1 = 8: = d2 01 (where > 0 by 2
definition of a), and a constant u satisfying 2 < < 2 + 26 For i 2 1, we define of d: Then,
as shown in the proof of Theorem 9 in Okumoto & Suzuki (2021). we have: 1/2-1/4
2 2 (+(0))
2 (2-)TT) 1/2-1/0 -2 (1-
(+)
Therefore, similarly to the case of S q S 2, using Theorem we can conclude that for true function f satisfying Assumption 3
there exists f' E P such that.
1/2-1/9
1f - f (1-
2 (7(()))
<2-2(1-)((--)))
TS*((s)
where (7/) 2 Now, using Lemma 18 from Okumoto & Suzuki
2021 again, have:
GT, 88
1
2
< 8
II
1
2TT
2r
Eo
[4 -9
1 1
2 1
Therefore, by setting T < 27, we can establish the result for the case of S S 2.
A.1.1 PROOF OF THEOREM g
To prove this theorem, we first introduce the following function as an approximation of j Flai
(xeNg (x))) 6.()) (
Re(()) = E.ENg- 85(f) (2<
Based this notation, also define RT (f) M R for any dout E N an approximation of (F).))
as
(Rr (1) (x)); { Rr (z) i dout).
(dout <i).
To establish the proof of Theorem
we present the following lemma.
Lemma 9, Assume that 7, > No Rso satisfy:
7' (8) < > va (7) < 1, va (7') < 1,
and true nonlinear operator (Fr..) satisfies Assumption
Under these conditions, we obtain the following inequality:
1 g 2
|lf Rr (fll2 2 -1 (1-va(1)) dout + BBy 2 - r d
2 K
1-2/9
|l - Rr (f)ll2 2 (11100(()))
Σ
2 (v(6))=((0)
V /oou + Bey
r
d
2
TS)(()
15

---

but with an Published as a conference paper at ICLR 2024
This proof is provided in A.1.2
Now, using this lemma, we proceed with the proof of Theorem g The strategy as follows: since Lemma 9 gives the error when approximating the true function f by Rr (f*), aim to obtain the approximation error when approximating Rr (f)) using FNNs. By summing up these errors, can obtain the approximation error when approximating fo using FNNs.
Now, according to Theorem 4.1 in Perekrestenko et al. (018), for any >> and some constants C1, C2 > 0, if we let
Proof of Theorem g
L3 -3= (1108")) !)² + log (Fmax)
there exists neural network bú E (T,,3. 21, C22 2g) that approximates tht with the following accuracy:
11.. V% 2r Se.
For such vi. we define:
bb. max { 2-22, min {V2, wr }} Tije = c ( 1og 1) + log (Jmax) ) 2.
Moreover, according to Proposition 3 in D. Yarotsky (2017). for any >> 0 and a constant Bx > 0, we let
3dmax
b) log dmax], 1, Wx = 6dmaxx Sx = Lx W
Lx = log
5
there exists neural network Øx E L(Lx,, Wx. Bx, Sx) satisfying:
dmax
Φx
F2
S.
1 (,111,1]mmm
Now, according to the proof of Theorem 7 in Okumoto & Suzuki
(022)) for ft E Fo.y we define:
RI (ft) Σ Σ
(V2) dmax
(fr.
V
22"
/2
*(t) (EJ(s)
where (()) = (1 Zg0 : 12a- 11,1 < 22.) Then, we obtain that
[TT (fi) - Rr (fi) (10.))mmm))))))
< B2i t (V2) dmnx
(dmax + 1) e,
where we used the fact (fi, 1/1) S [[filp S B2i Therefore, as a approximation of Rrr (f), for any dout N. we define Ri (f) [0, 1amax - Rods as follows:
Vi [douc] (R) = Rr f (f.)
This yields neural network with the same intermediate layer dx
output dimension increased from one dout dr+11-
Then, by using this Ao (f), for (x:) M, we define I' (x) M + oo as follows:
(f' (x)), = ( (ftr (mm))ere):) (1 i dout),
(dout < i).
16

---

Published as a conference paper at ICLR 2024
With this f', the approximation of Ry (f) results in the following emror:
|R (f) - f'll (10.1]6max
$
dout
Bui GT. (v2)
Awax (dmax + 1)
dmax (dmax + +)e.
dout B2G (T, 7)
(2)
Therefore, in the case $ 9 S 2, with the result of Lemma
9 we get the following inequality:
|f - -'1l2 - |lf - Rr (f)ll2 + Rr (f) - -f'11 (10.)=((0
s 2 22-vaa dout + BB 2 - out dout (2G (V2) dmax
r d
(dmax 1) c.
Here, we put
2 2-(1-ua)T Vouut B2y
2-,
domt B2G (T, (V2) diua
(dinax
From the condition of E O, dout need satisfy the following inequality:
2-(1-va)2 dout Bey 2 - dout > 0 = dout (Be 2-r)
2r(1-va)T
Now, since 0 <r< we have 0 < I- < 1. Then, we define dout as
dout (B2)* 2
Then, obtain the following inequality:
|lf f'll S 2- Vdout I 2- (1-5)(1-wa)T
The case of 2 < q can be proved in the same manner.
Finally, we evaluate the size of the neural network. As mentioned carlier, since Ry (f) is linear combination of the neural network Øx
Vidmax v2
we let
122
L = Lig + Lxx + 1,
W max (21dmmxx G (T,7), douth:
21 L + Lx W dout)) GTT.)).
max Cz, Bx: (V2) dmax BBJ.
RT (f) satisfies RT (f) E & (L, W. B).
First, we evaluate Lg as follows:
bg -ci ( (10022) )) + log (Fmax) +
dmax
-C
log B2 + r vox) Tlog + log B₂ + log G (T,7) +
log
2
2
+ log (dmax 1) + (1- (1 - Tog + log
1
log (Fmax) +2
Z-r
Now, considering that 0 < r < 1, we note that:
r /r r)
2
<
2(1-1
1 1-
1 r-r
2-r
17

---

Published as a conference paper at ICLR 2024
Using this, we can obtain the following upper bound for Lg:
L3 - Ci (7max log B2, log I |--) (2r))
2
max { (oaass 72, (T) log fmaxs 2]
Similarly, we can evaluate Lx as:
Lx $ 7 max { log B2, log
2 1-r'
logo }/ max {dmax: T, log G (T, [log dmax
Then, if we let
{|o (C(7max (7max |c((mmax
2 2-21 log B2, log })
2 2
K max
7 max log B2, log 1 -
log {1
1 -
we can obtain the following upper bound for L:
L 2K max { (L (dhaax T2, (log G (T) log fmax H
Similarly, we can evaluate S as:
1212dmaxLi + Lxx W dout) (TT,7)
< maxx (4xx 21 K K max max (maxx T2, (log G (T, (T) log fmax (B2)' 2:(1 20(1-00)T G(T,7) }
< 4 212K (B2)* & max (laax I2, (log G (T, 7))² log fmax, 20(1-10)1) (TT.)).
A.1.2 PROOF LEMMA 9
Proof of Lemma 9 Now.
/ |lf
|lf - Rr (f112
dx
M
Σ (z)()) - (Rr (1) (x))) (x)
M
dont
Σ
(fi(8) (x) Rs (ft) (x)
+ Σ
((())) ai (2) (x)
M
iiml
doutt
daut
fe Ro (F:)11 + +(B))
imduut
holds. Here, the last inequality is derived using Eq 33. Now, with regard Jr Rr (fi) ? Lemma 17 from Okumoto & Suzuki 2021) states that, for example, when - S 2,
f Rr (f.) || < 20) |
valid. Combining this with Eq in Assumption 3 we have
dout Σ
dous
/ Rr (f))
2 21- 2- 2(1 dout-
This is also true for q > 2. Additionally, in general,
Σ
dr
m
2
M=##1
18

---

Published as a conference paper at ICLR 2024
can be obtained through simple integration calculations. Thus,
7
out
i=dout +1
obtained. Hence, in the case of 1 S S 2, we obtain the following inequalities:
Ilf - Rr (f)ll2 S 2 2-2(1 -22( dout + +B22)
r
2
2 2--(11 2(1(TT dout + (B2)² :-Il - Ro (f)12 S
r
r dou
$ (1-raa) V dout + BBy 2 - dout" #
The desired inequality can be obtained in a similar manner for the case when q > 2.
A.2 PROOF OF THEOREM 2
Proof of Theorem 2. First, Pm
[|f - fol follrn.
px
can be decomposed into two partial sums as follows:
E pm |||
1o11
Epm
Epx
[XF( (
Px
EPx Σ (f) - (xx)))(((x)) 2
Epm
20
1x [fF(()) (((())-3(
(fx) (x))
Ep
Σ Epm [[I - rill 1111pp]
i=1
dout
Epn
[l - 5: 111 Px
Σ
Epm
[I fi [1]]
dout+11
where we utilize the assumption of the Radon-Nikodym derivative, which implies || 11 A 11:112-
First, for the second term, according to Assumption 3 we can evaluate it as follows:
80
Epm -
11
Ep (B2))
S 2 - (B2) 2 d
Aout
dout
This provides upper bound for the second term
For the first term, we can utilize the results from Theorem 10 and 14 in Okumoto & Suzuki (02T) Thus, have:
donn
domt 2(at-o)
Epn [1 - 111122
$ n
((al-))+1
(log 3 +2 max (logn)² S (logn)*)
1=1
2(21-o) [(o--))+1 (log n) +2 max (logn) (logn)
S dout n
Here.
Okumoto & Suzuki (2021) choose such that T 2( -1 log, n. Furthermore, from
we have dout (B2)² 2r(11 (1- ) Substituting these values into the above equation,
Theorem
we obtain:
(at Sn n 2(ut-o)+3 (log n) +2 max { (logn)* (log (ogg))) }.
E pm [| - -
19

---

Published as a conference paper at ICLR 2024
B PROOF OF THEOREM 2
To prove this theorem, we first define several concepts. First, consider a totally bounded metric space (F, p) consisting of set J and metric p F x F - Rt, We define set in F that satisfies the following condition: for any > O, there exists collection of functions {f',.... f such that for any F. there exists k [N] satisfying p(f, fk) S We refer to such collection as an e-covering set of F, and the e-covering number N (e, F, is defined as the size of the smallest e-covering set.
f c F such that p(S', 2 for all i # j. The 6-packing number M(e,F, is defined as the size of the largest e-packing set.
Furthermore, an e-packing set of F is a collection of functions {f',....
Now, with the definition of the e-packing number, we can establish the following lemma.
Lemma 10. Consider (U (F%,))) c (U (FP.g)) 20 for any d 2 4. In accordance with the defini-
tion used in Theorem
we define and utilize a!. For any E (U (P.g)) dd subject to the constraint
I1Aill2 I B2t (Vi E [d]) the following inequality holds for any & I 11 P22
d +
logM (s, (U (Fra)) .Il-lla) Z log + sd
1 log
8
The proof of this lemma is provided in B.
Now, by utilizing this lemma, we can establish the proof of Theorem 2 However, it important to note that the following proof is an extension of the proofs presented in Suzuki (2019; Raskutti et al. (2012) adapted to the the setting in this paper.
Proof of Theorem 2 Now, considering that Px the uniform distribution, note that [+)l22(px)) = 11.1 Furthermore, for any d 2 4, 8n > 0, and en > O, we define:
M: M (nn (U (FA))) .1H11))
N
Σ 1=1
oeen (U (F% I1-112
Here, the covering set gg. is constructed such that for any E (UFF)))) there ex- ists & E [N] satisfying (U(F,,)))
[ st ll2 < 0z6n. Moreover, let IMM be a 8, 8a.packkng of
Now, according to the proof of Theorem 2 in Raskutti et al. (012)) we let θ be a random uniformly distributed over the index set [MV] and let X = (x()) i= and Y := {)))) V we can obtain the following lower bound:
inf sup ED, [|| ( f ()(U(F
[||i - S 1
2 inf sup ED, f ET
82
2 inf sup
p ( 2 62/2
f J-
2
82
Exp [xx; (0; Yr'] + log 2
log M
where, for simplicity, define F = (F )²
Here, evaluate the mutual information Ix. (e; Y This can be done by considering the KL- divergence, as discussed in Yang & Barron [1999): Raskutti et al. (2012):
| (k) f! ll.
log N + nd 2
Ixp (0; YT
M
log N +
o
2 6
20

---

Published as a conference paper at ICLR 2024
where (2(K) argmin |1gt f 2 and Il the following lower bound:
1
- (x Therefore, obtain
82
2 1 log N + nd c + log
inf sup f (E
Ep, |1l I (
2
log M
Thus, as shown in the proof of Theorem in Suzuki (2019), by taking 6n and e, to satisfy
nd 2 S log N, 8 log N < log M, 4 log 2 & log M,
2
the minimax rate is lower bounded by 4
To choose on and en satisfying this condition, let us first consider maXield 0s, and we have
nd 2 E S log N. For simplicity, let
(1 Loper i=1
log.N
of F, F,11-11 log.V F,,oen;F,llll.
F,
Now, since 2 2 by assumption, according to Lemma 10 we have
F,1+1l2) log.N (Vioren: (1+11) 2 log d
d dd vd
+ sdinr log
Thus, obtain
nde, ~ s slog d
d d Vs
+ sd
log
vde
2
1 s log
s d
rot log
d V$
d
We want to choose o that satisfies this equation. Let's consider first. A larger gives better lower bound, so we set ~ d. In this case, we have
1 n
En
d log
Therefore, Cn ~ n 24141, Gp ~ n would be the optimal choice.
Finally, we need determine the relationship between en and 8, satisfy log N log M, which
(1 5) )u!
can be achieved by setting v EE ofen 6n. Thus, we obtain ón 201+1 In conclusion, the lower bound is given follows:
Ep,, [|I ('(AA())) Zn 2u
(2-e)at
inf sup f ))
B. PROOF OF LEMMA T0
This theorem an extension of Lemma 4 (a) from Raskutti et al. (2012) to our settings. In order to prove this lemma, make of the following lemma.
Lemma 11. In accordance with the definition used Theorem we define and utilize a² For any i [d] and p 2 2, we have
log.V
(U -1-11) 2 d log
8 (6,, (U(F))));
d +
3i
/
where (U (Fr denotes the space U (Fr with the constraint
[| S Bzi B2
21

---

Published as a conference paper at ICLR 2024
The proof of this lemma is provided in B.2
Lemma provides an evaluation of the covering number for constrained y-smooth space. On the other hand, Lemma 10 provides evaluation for the product space formed by combining multiple such spaces. The proof of Lemma i0 is more general, allowing for evaluations in various settings. Therefore, it is reasonable to expect that by providing the corresponding evaluations appearing in Lemma other settings, similar evaluations can be obtained for product spaces.
Proof of Lemma 10 First, we define
8 (Fra) .11-112) 1. V5
N; = M
(F
Next, we introduce I, = 1,, } and define
u 4 [=j
Nullo og.
where we set 8 = maX;e]]]] 8i-
Now, from Lemma 11 obtain
N₂ = M 8 Vsi
d= /s
(Faa).
2 drat log
Therefore, 8; d implies that we can set
N₂ z d log
-1=NN
which results in value independent of i. Note that s max; d holds.
Now, we have |G| R .d.
s For = [d]. we select {0, (0,f, s [.N] as Va,
packing of (Fr.), and for any E G, we
define
9 = (g) 92 gdd E (FP.)"
where if u, * O, then g." = f. and if u, = O, then g," = 0. Next, let's consider g" and h" that belong {g" G). From the definition, have
8
11g" - 12 111 Σ 115
I + md
[us + vi]
==1
Moving forward, we can follow the same reasoning as in the proof of Lemma (a) Raskutti et al. 2012), and obtain the following bound for < $
log.N (5. (F).)) (1:11) Z log d sd Fot log
d : V
Here, we substitute d into N obtain this result.
B.2 PROOF LEMMA
Proof of Lemma 77 First, we choose the value to satisfy 27(x) (B2) dt, Then, for this value of 8, we consider the corresponding ball:
{ (f) (f)lEz, $1}
22

---

Published as a conference paper at ICLR 2024
This ball satisfies the decay assumption ||fall Bzi In fact,
Σ (2) 16, (6% (1>)11)) -27(0) 16, ())lpp <
|16, (1)11
holds because of f E U (F% Therefore, if 2 2,
|| (f) < ||o, (f 2 2- Byd : Bzi Because this ball is topologically equivalent Euclidean ball with dimension and radius B2d 7, we have
N 8 (Fra), .1-11) 2 N Vsi
8 V8i
B2d
B ,1-111112
N
B .1-1112
B2d Vi
B2d 1 V
2
Next, let consider specific value for In the case of mixed smoothness, assign values only for the index corresponding to the minimum value of a, while setting the rest of the indices to 8; 0 in order to maximize the right-hand side of the inequality. In this scenario, obtain
(2)(e) +
(B2) + d
Similarly, in the case anisotropic smoothness, by choosing as the index corresponding to the minimum value of a, we set Sy oz to maximize 2", Therefore, we have oz
2 2 Ex
= 2142
which coincides with the case of mixed smoothness. Thus, conclude that
B2d /
d 1 /Bg
log.N N
(. V8;
2 2 log
2 d log
8
C PROOF OF THEOREM 4
Before delving into the discussion of this theorem, we present here the precise definition of linear estimators briefly introduced the beginning of Section 4.
Definition 11 (Definition of Linear Estimators). Let D, = (L(()),) (')) be the data set. An estimator f based on D, is said be a linear estimator it can be expressed in the following form:
ViEN: (f(=))
(1) yi Pas (x;
Here, assume E [|yp (1]" 80.
The theorem is grounded in the notion that, stated at the outset of Section 4.1, the non-convex nature of the union of y-smooth spaces for varying values of a implies that linear estimators are likely to experience sub-optimal performance. This intuition is based on Theorem 3.3 in Hayakawal & Suzuki (2020). Here, we present this theorem as an extension applicable to the setting of linear estimators in this paper.
23

---

Published as a conference paper at ICLR 2024
Theorem 12 (Extension of Theorem 3.3 in Hayakawa & Suzuki 2020)) For linear estimators (Definition 11 in certain space F the estimation error has the following relationship:
inf fllinear Fe
sup
R (f. f = inf sup
R (f. f*)
filnear (eConv(Fs)
where (f. (1) = Ep ||| - 8
Px
The proof is provided C.I
In order to utilize this theorem in the current proof, we require the result of taking the Convex Hull of the space U ((F2,2 (I)) The following lemma presents the result that provides it.
Lemma 13. The Convex Hull of U (F2,2 (T)) is given by:
Conv (U (F2,2 (T))) = (F (Jminuer 7a
Here, 7 = ein Yo is denoted as y (s) == min %a (s), indicating that the minimum is taken over for each 8.
The proof is provided in C.2
This lemma provides a result for the space (F2,2 (T)), but the space of interest in our discussion, U ((F222 ())) is simply Cartesian product of the space U (F2,2 (I)). Therefore, observe that
),
Conv (U ((F (T)) -(u
(u (F )) ))
Furthermore, following the approach used in the proof of Theorem we also seek to establish a lower bound using the techniques from Suzuki (2019); Raskutti et al. (2012). To this end, we require a lower bound on the covering number for the space under consideration, and we present the following lemma regarding that.
Lemma 14 (Covering Number of F2,)) From Definition let r r (Q."), and let Ya (s) = (a, s) and a* a. Also, let (Q+). 7a (s) max; {a:8; and = Here, 7 = minaer 7a- In this case, the lower bound on the covering number of F7 is given by:
log. N (e, (F21) 1H122 - Lt
The proof is provided in C.3
By combining these lemmas and theorem, we can prove Theorem as follows.
Proof of Theorem First, the estimation error we want to evaluate can be transformed follows:
inf sup fllinar ((a
ED., ||I. f 1i0--111lac [[ceece
inf sup
EDD [[] - Mllaape)
filinear f (CCon(UU((P
=inf f:linear (oE(U(F2,)))
sup
Ep. ||| 80 1
> inf sup (
ED, - -
where in the second line used Theorem 12 and in the third line we used Lemmal 13
In other words, we ultimately need evaluate inf yuu ED,, [|]s - r [l To eval-
uate this, first let
M := M (6n. U (FE.).
NN (c.. (
(F%,),
24

---

Published as a conference paper at ICLR 2024
Then, according to Suzuki 20199, have:
82 (
log
20 c + log 2
inf sup (F2,)
ED, [1[ f (((((())) 2
1
2
log M
we select ons 6n satisfying
n
20 n S log N, 8log N s log M, 4 log S log M,
the minimax rate is lower bounded by T
Here, from Lemma 14 we have:
log.V (c, (F2, 211122) -
Therefore, by choosing 6n and 5n such that:
on 2n"+1+E
we ultimately obtain:
inf sup f (FE)
ED.
||Is 10 LP(Px)
2V
66 n
20
C.I PROOF OF THEOREM 12
Proof of Theorem
Now, we define
R (f. f*) = Epm || - 1 1011pp]] R (fr. fi) = -Ep [llf - 1:11pa]
In this case, obtain:
R [, 10) = Epn
[ - 1
=Epm
EPx r (x)
Px
Σ (x) (x
27
= Σ Epn Tepx
20
(FAx 12 (x1)
Epm
Exx
i==
R f.. fi)
Here, represents a one-dimensional output linear estimator, defined in Hayakawa & Suzuki 2020 Therefore, proven in the proof of Theorem 3.3 in Hayakawa & Suzuki (020)) i [fo a convex function. In other words, for 1", go E F and ht == =1ʃ" +(1 l) we have:
(1- R (fs, hg $ t for f2) + - t) R frr 9:)
Hence,
R (f, = Σ R (fo ng)
St > R ER
(f.
+ (1- Σ 1=1
R (fo 9.)
==1
t=1
-tR (f, +11
holds. Therefore, R (f. is a convex Kunetion.Thereffre,
inf sup R (f, Aliinar f
2 inf sup R (f Sr) filinear CeEConv(
can be asserted. And since the converse is evident, we can conclude the statement of this theorem.
25

---

Published as a conference paper at ICLR 2024
C.2 PROOF OF LEMMA 13
In order to prove this lemma, we consider an alternative representation of the y-smooth space using method similar the employed in describing Besov spaces based wavelet expansions, as demonstrated in Donoho & Johnstone (1998) and Meyer (193).. Here, we adapt a similar approach redefine the y-smooth space.
Theorem 15 (Altemative representation of y-smooth space). For the norm |1-11,g, of the y-smooth space D. the following relationship holds:
Il x
Σ SEN
27(0) (3-))
Σ
10e1"
(EJ(s)
where J (s) = (1 28 12--1] S |4 < 2 and 0: (f. v1).
In other words, by considering the following space, we obtain an alternative representation of the --smooth space F7
P.q (C) = =0: =0:11011E,, scJ.
|101e
Σ
22(0)-($-
18:1 (EJ(s)
Σ
BEND
The proof is provided in C.2.1
Hereafter, based on this theorem, we treat U (Fr.g) as 0% = 07 (1)-
Proof of Lemma
13 First, the parameter representation of U (F2.2 (I')) is described as follows:
U
= U aeT
0:
Σ
(7)(1)
Σ
10,12
oET
(EJ(s)
Now, let us define 0, (0 ((.) Next, us consider fixing particular and setting 0z (0)e))y) for all * 8. Then, we have
(x) (5) 10al22 -
On the other hand, since are considering U as the set of endpoints, we can consider:
2minaer (a()) |10.112 < 1.
Now, let us vary and consider taking the convex hull over all 0, that satisfy the above condi- tion. Specifically, we consider convex combination = EEENg 8.0, using 8, E R satisfying
EOENS 8, and 8, O. For this 6, we consider the ||-II ||-Il 7a norm, and we have:
|||| min
2miuaer 7a(+) 11,001l2
SEN
Σ
8, er 7a()) ||0,112
sEN
Σ
1
SEN
Thus, obtain the relationship stated in the theorem.
26

---

Published as a conference paper at ICLR 2024
C.2.1
PROOF OF THEOREM 15
Proof of Lemma 15 F is
The proof utilizes the technique presented in Meyer (993). Now, the norm of
||
Σ (2x(0)
16o, (/)1)))
SENO
Thereeore, let proceed evaluate 110, (f) Let define 0: th). Then, express
5g (ff as
8. (.) Σ (f.r)) E 014i. LEJ(s)
(EJ(s)
Here, since the following inequality holds:
0 = (6. (f) v2) 1 8. (z)
(1)
we set + + 1, then
10:1 S Jmm 8& (J) (x)) (x) luba (z)) (xx())
( 16, ()) Wh (2) (w)
(nn W (x)) (o)
is obtained. Now, by the definition of thz (x), we obtain following evaluation:
S /2 V22l 1 = =
Juln
W (x)) =
vh, (1;)
Therefore, |0:] is evaluated as follows:
2 l2l0 1|o, (f)llp-
0:1
1
Σ IEJ(s)
10,1"
2 plella
16, (nII JJ (o))
:
= 1ادn
[+) 16, (f)l,,-
Furthermore, regarding |J (s)l, considering all possible choices for each 4, which amounts to 2 possibilities, we can conclude that [J (s) 2.. Combining the above observations, we can ulti- mately evaluate it follows:
$
Σ (EJ(s)
10.1"
2
Iillo + 116, If)
(6)
We now proceed to establish the reverse inequality in a similar manner. By employing similar evaluation as before, we can derive the following inequality:
16. (f) Σ
1il (x)1
Σ (EJ(s)
10 1ob (o)
Σ
l (x))
(EJ(s)
(EJ(s)
< 2 1ela
Σ 10cl
Uvila (2
-
to
1
2
Nlllo 2p
1 (cl0+s)
Σ
10,10
(EJ(s)
(EJ(s)
[| 2 2p
+11- 1) +11=) (2le+
Σ 10:1
<
Lale E+
Σ
10,1
(E)(s)
(EJ(s)
27

---

Published as a conference paper at ICLR 2024
Then, ||6, (f)l,p is evaluated as follows:
166 (111pp ( (8(00)))))))
< 2
Jeln
+
Σ
10:1"
(EJ(s)
By combining equations Eq (6) and Eq
we obtain the following relationship:
2 Nello
Σ
1011"
$ 16 (f)llp 2 1xlo
-
+
Σ
10.1"
(EJ(s)
(EJ(s)
:: 11,, (f)llp x #
Σ
10:
P
(EJ(s)
Substituting this into the initial expression for ||
allows us to establish the desired relationship.
C.3 PROOF OF LEMMA 14
Proof of Lemma 14
Let consider the case where we define r (Q("), 7a (s) (a, s), and a' a.. For simplicity, we denote Q = Q.
Now, we define the set (Q.) as follows:
I
i
(Q²) = No 8,
2
We now evaluate the restricted subspace corresponding the coordinates associated with belong- ing to this set. In other words, for 8 & 7 (Q+), we set the coordinates 0s corresponding to 8 and to be O. The dimension of this subspace, denoted as is given by:
= Σ
Σ
Σ
2
(ERQ)EEEEE SET(Q.)
Then, the restricted subspace of U (F) can be expressed as:
27(
Σ
10.1
SET(Q.)
(EJ(s)
On the other hand, by using Schwarz inequality, we obtain
$
Σ 27(+)
Σ
1011
Σ
27(0)
Σ (EJ(s)
10:1
.EI(Q.)
(EJ(o)
.EI(Q.)
sEI(e.)
Then, if we define d' ExEr(e.) 1, the space
A: Σ 22)(0) d' Σ
10.1 <
SET(Q.)
lEJ(s)
also be subspace of the restricted subspace of U (F2,))
28

---

Published as a conference paper at ICLR 2024
Next, consider the covering number of this space. To achieve this, want to determine the value of 'I' such that ball with radius e can inside this space. Based on the assumption that 2- 2-2x(6) > 2-22" we have:
2 27
d' 2 e.
We need choose the largest possible value of T'' that satisfies this inequality.
Here, can derived from the definition (Q.) as = [2 s 2 Therefore, we obtain:
2 2-27
21 C..
By setting
2a-1-c -g-1
logg
-1 and substituting this and the definition of Qes we have:
2 2-2T
2
2T G. 22 22
loga e.
d'
This shows that by setting in this way, a ball with radius is guaranteed to be contained within the subspace.
The remaining task is to evaluate the covering number of the ball with radius e, According to (5.9)
in Wainwright 2019), have:
log (5.B"(6 (t).
2 d log
Here, d can be expressed as follows based on the definition:
d Σ 2 Σ
2 2
SEI(Q.)
.EI(Q.)
By substituting the values of T and Qc, we obtain:
d 2 + 2( 2--1= logge
= 1ts
Thus, obtain the desired result.
In addition, let us consider the case where I = r (Q?). 7a (s) max, {a,s;) }, and a" = ā. Now, in order to analyze min.er(Q.). it suffices to consider the when a,, aÿ" because the following condition
|la/ La = o; " (Vj = 1,2....)
holds. Now, let consider the following setting specific example of satisfying 7(8) T:
T
.0, ......
Q2
a39
a
where
2
In this case, for each s, the that achieves the minimum of 7(s) min.er(Q.) (s) corresponds to a mapping between the elements of in descending order and the elements of in ascending order. Therefore, we have (s) max, 0i, Sj. Furthermore, considering that
T
a
T
(Vi =00=1,, 1,2...).
the defined satisfies the condition r(s) T. Moreover, such 8 can be rearranged by changing the indices. If we denote the index corresponding to the minimum value of it, is sufficient for 1 to be within the range where a 2 Q. log, i holds. Therefore, there are at least 2 possible rearrangements. Let I ((Q.) represent the set of 2 कt rearranged s.
Under this setting, following the previous discussion, we choose the largest that satisfies:
2 27
d'
29

---

Published as a conference paper at ICLR 2024
Now, since d' < 2 holds based on its definition, have x- 2 2-27-- d. Therefore, substi-
tuting T
2(1+c)
log2 along with the definition of Qe we obtain:
2 2-2r 2f
2 2 27 a d'
2 xhe (n())= 20 -1) logg e ++ttt1///mmmm 1/1000/2 -1)
Now, considering the definition of c, we have 2(++)) 1 < Additionally, when is sufficiently small, the value of log2 E can be considered sufficiently large compared to (loge=1)) There- fore, we have (-67) (1 + c) + 20++c) 1) log2 e + a'-1/n (log2 E = 1)1// < 0. Therefore, we obtain:
2 2-27 Furthermore, for the evaluation of d, have:
2nd ((yaā ((nāā-6((+e)++ 20+0) -1) logs c-' (000// ( 2 2- 2oogo 6²
d ==
Σ
2 2 2 Lat 2 2 1
I
1-(T/2)
> 2
28
Then, we obtain
(1((T/2) -2
d 2 26
(2(1t))n++112 2(1te) -1) log, - +o 1-1/0 (1-01//11111111111111111111 2 (log2 11)
2 2na
where we have utilized the fact that 0 < Consequently, obtain the desired result in this case well.
2(++) < 1, which follows from the definition of c.
D PROOFS OF COROLLARY AND THEOREM
D.1 PROOF OF COROLLARY
Let us consider the case where we define (Q Ta (s) (a, s). and a' a. For simplicity, we denote Q = Q.
Proof of Corollary 6
In this study, we consider Qe as value that varies and taken be Q. 11/ll1llgg log c. Because we compare the results with those of linear estimators, following the definition in Theorem we set C~n n 2, Consequently, we have 1/Q. log n in this case.
Now, the rates for (UF2)) 0o are provided Theorem 3 By examining its proof, we can observe
that it utilizes Theorem 10 and 14 from Okumoto & Suzuki (2021). which results concerning one-dimensional outputs. However, the proof presented in Okumoto & Suzuki (2021). Q. is treated constant and ignored. Therefore, it is necessary consider the impact Qe not being a constant in this case.
Specifically, Qe is used in the definition of the number of layers L' = To-1 Here, T takes the value 7 ~ log n, meaning that in our setup, we have L' ~ (log n2) which differs from the value of L' log mentioned in Theorem 14 of Okumoto & Suzuki 2021
Therefore, we need to consider the influence of the change in L' on the rate of estimation error. In Okumoto Suzuki (202I), the authors obtained an upper bound on the covering number of the class to which dilated CNNs belong by substituting the values of each neural network's parameters into the expression:
LL' (B (BVB)BBWW))))) CWW)
(S + W'C) (I. T') log
8
30

---

Published as a conference paper at ICLR 2024
By using L max { ,T, T2) it can be seen that even with the modification L' as in our case, L+ L' remains of the same order. Also, the term log LL' only undergoes constant scaling. Hence, the change in T,' in this case does not affect the rate of estimation error for dilated CNNs.
Therefore, the rate for (U (F22)) is already known from Theorem Hence, to determine the rate for U ((F2,2 (T)))", only need to consider the max of the rate for (U (F22))
From Theorem we have:
E pm |
2 Px
(2 r)- 201 11
(log n) 46
2
max (Q.)
(2-rla 2
(log n) -
where, in the last step, we have used the fact that ai 2 aj based on the definition of T.
The same reasoning can be applied when considering r r (Q²). Ta (s) max; {a,s: and
a' = a.
D.2 PROOF OF THEOREM 7
Let us consider the case where we define I r (QTh), ) Naa (s) = (a, s), and a' a. The proof for the other case follows similar argument and is omitted.
Proof of Theorem 7
First, based on the assumptions of this theorem, Theorem and Corollary 6 Ghold. This means that the convergence of the estimation error using the linear estimator n 2e-1ec, while for the dilated
+hm However, only consider the polynomial order part of for comparison with the linear estimator, as the polylogarithmic order terms can be neglected when n is sufficiently large.
CNNs, it is 32+1
Now, for the extended CNN to dominate the linear estimator, the following condition must hold:
2a
1g+1+c
By elementary algebraic manipulations, we can derive >
(2 However, note that the assump- 2-r
tion 0 < < 2a imposes constraint on c. From this, we can infer that in order for c to exist, we need (2c+1)r
2-r < 2a -
= 2a-1 to hold.
31


Reviews:
[{"review_id": "G6QUCRh4ov", "reviewer": "Reviewer_qUYW", "summary": "In this paper, the authors consider the regression problem with infinite dimensional input and output. This setting  is motivated by recent applications such as image to text mapping.  For their target function, they assume that it belongs to certain gamma smooth spaces, which can be thought as extensions of mixed Besov spaces and anisotropic Besov spaces to infinite dimension output.  They consider learning this class of functions using dilated CNNs, which consists of multilayer convolutions followed by fully connected neural networks. Assuming that the ERM can be constructed, they characterize the approximation and estimation rates, and show that dilated CNNs achieve the minimax optimal rate for norm $p \\geq 2$. They further prove a lower bound for linear estimator, which shows that dilated CNNs have better rates under some conditions.", "questions": "- Is there no activation in the convolutional layer?\n- What does non-adaptive approach/adaptive approach refer to in section 4.1 and in the conclusion? I guess, this would improve the dependency over the width.\n- As a personal taste, I would replace the last line of the abstract \"explains the success of deep learning\", by a sentence of the type \"provide a theoretical basis for understanding the success\".", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- This paper belongs to a long tradition that has sought to study neural networks by decoupling the statistical from the computational aspects. By considering directly the properties of the empirical risk minimizers, one can probe the adaptivity property of neural networks by studying their decay rates for different function classes.  Within this context, the authors do a serious job in carefully constructing the function target class and deriving tight statistical rates.\n- The paper is well written and clear despite the amount of technical notations.", "weaknesses": "- As a general criticism of this line of work (not particular to this paper), it is unclear how much it informs practical neural networks. However, one can consider these results to be an important background for the study of neural networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "J8ae7Uudhp", "reviewer": "Reviewer_Ex9R", "summary": "The paper explores the optimality of dilated CNNs in estimating mappings between infinite-dimensional input and output spaces. Through analysis of their approximation and estimation capabilities, the authors establish that the accuracy of approximation and estimation errors is influenced by the smoothness and decay rate of the output relative to the infinity norm. They also provide evidence showing that dilated CNNs outperform linear estimators like kernel ridge regression and k-NN estimators in terms of minimizing estimation errors. This finding emphasizes the efficacy of feature learning accomplished by deep neural networks.", "questions": "1. Assumption 3 seems to be a little bit strong. Could you provide a specific example to illustrate it more concretely?\n\n2. The computational aspect can pose challenges due to the infinite-dimensional nature of both the input and output, particularly when dealing with large-scale data.\n\n3. Can the dilated CNN be used to learn linear operator? Will the estimation rate be improved?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a thorough analysis of the approximation and estimation abilities of dilated CNNs for estimating mappings between infinite-dimensional input and output spaces.\n\n2. The authors demonstrate that the estimation accuracy achieved by dilated CNNs aligns with the minimax optimal rate of convergence.\n\n3. The authors show that dilated CNNs are adaptive to the unknown smoothness structure.", "weaknesses": "1. The absence of empirical validation on real-world datasets weakens the practical relevance of the findings\n\n2. The paper briefly mentions potential future directions for research but does not thoroughly discuss the limitations of the study", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2oFTLrVGGs", "reviewer": "Reviewer_DeXd", "summary": "In this paper, the authors study the setting of estimation in infinite dimensional input and output using dilated CNNs. They derive approximation and estimation errors when the true function satisfies certain smoothness type conditions. Additionally, they show that these CNNs achieve the minimax optimal rate for estimation accuracy. Finally, they also show that dilated CNNs outperform other models for infinite dimensional estimation like kernel ridge regression and k-NN again in a minimax sense.", "questions": "1. Can the authors provide some more intuition and insight on how the parameter $r$ affects the class of functions being studied? \n2. As a followup, what is the motivation behind where assumption 3 comes from, and can you say anything about example problems in practice that satisfy this assumption?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The main theoretical results appear to be novel, and are a significant improvement over previous results.\n2. The convergence rate of the estimation error of the dilated CNNs is also shown to be minimax optimal up to poly-log factors under a specific regime.\n3. Further, the paper also contains theoretical results which show that dilated CNNs outperform linear estimators, which seems to provide some theoretical justification for the successes of deep learning in high-dimensional spaces.\n4. The paper is well written and the proofs seem correct.", "weaknesses": "1. The results are specific to the dilated CNN model, and it is not clear how to extend them other model classes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)