Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
Authors: Taiji Suzuki
Atsushi Nitanda
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: deep learning
Besov space
minimax optimality

Abstract: Deep learning has exhibited superior performance for various tasks, especially for high-dimensional datasets, such as images. 
To understand this property, we investigate the approximation and estimation ability of deep learning on {\it anisotropic Besov spaces}.
The anisotropic Besov space is characterized by direction-dependent smoothness and includes several function classes that have been investigated thus far.
We demonstrate that the approximation error and estimation error of deep learning only depend on the average value of the smoothness parameters in all directions. Consequently, the curse of dimensionality can be avoided if the smoothness of the target function is highly anisotropic.
Unlike existing studies, our analysis does not require a low-dimensional structure of the input data.
We also investigate the minimax optimality of deep learning and compare its performance with that of the kernel method (more generally, linear estimators).
The results show that deep learning has better dependence on the input dimensionality if the target function possesses anisotropic smoothness, and it achieves an adaptive rate for functions with spatially inhomogeneous smoothness.


Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
Taiji Suzuki
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan RIKEN Center for Advanced Intelligence Project, Tokyo, Japan tai j @mist. i. u-tokko. ac.yoo..c..J
Atsushi Nitanda
Kyushu Institute of Technology, Fukuoka, Japan RIKEN Center for Advanced Intelligence Project, Tokyo, Japan nitanda@ai www.kky..cc.c..... jc.
Abstract
Deep learning has exhibited superior performance for various tasks, especially for high-dimensional datasets, such as images. To understand this property. we investigate the approximation and estimation ability of deep learning on anisotropic Besov spaces. The anisotropic Besov space is characterized by direction-dependennt smoothness and includes several function classes that have been investigated thus far. We demonstrate that the approximation error and es- timation error of deep learning only depend on the average value of the smooth- ness parameters in all directions. Consequently, the curse of dimensionality can avoided if the smoothness of the target function highly anisotropic. Un- analysis does not require a -ww-dimensional structure of
like existing studies, the input data. We also investigate the minimax optimality of deep learning and compare its performance with that of the kernel method (more generally, linear estimators). The results show that deep learning has better dependence on the in- put dimensionality if the target function possesses anisotropic smoothness, and it achieves an adaptive rate for functions with spatially inhomogeneous smoothness.
Introduction
Based on the recent literature pertaining to machine learning, deep learning has exhibited superior performance in several tasks such image recognition (Krizhevsky et al., 2012), natural language processing (Devlin et al., 2018), and image synthesis (Radford et al., 2015). In particular, its superi- ority is remarkable for complicated and high-dimensional data like images. This is mainly due its extraction ability for effectively extracting the intrinsic structure of data. Its theoretical analysis also has been extensively developed considering several aspects such as expressive ability, optinization, and generalization error.
high flexibility and superior feature-extraation
Amongst representation ability analysis of deep neural networks such universal approximation ability (Cybenko, 1989; Hornik, 1991; Sonoda & Murata, 2017), approximation theory of deep neural networks typical function classes such as Hölder, Sobolev, and Besov spaces have been extensively studied. In particular, analyses deep neural networks with the ReLU activation (Nair & Hinton, 2010; Glorot et al., 2011) have been recently developed. Schmidt-Hieber (2020) showed that the deep learning with ReLU activations can achieve the minimax optimal estimation accuracy to estimate composite functions in Hölder spaces by using the approximation theory of Yarotsky (2017). Suzuki (2019) generalized this analysis to those on the Besov space and the mixed smooth
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Relationship between existing research and our work. / indicates the smoothness of the target function, is the dimensionality of input x, D is the dimensionality of a low-dimensional structure on which the data are distributed, and / is the average smoothness of an anisotropic Besov space (Eq. (1)).
Function
Hölder
Besov
mixed smooth
Hölder on low- anisotropic
class
Besov
dimensional set
Besov
Author
Schmidt- Hieber (2020)
Suzuki (2019)
Suzuki (2019)
Nakada & Imaizumi (2020): Schmidt-Hieber (2019); Chen et al. (2019)
This work
Estimation
Ön zurz)
Ón zūru)
Ó(n
x
Ö 201
39 Ö(1 20+1)
error
2(d- x
log(n)
Besov space by utilizing the techniques developed in approximation theories (Temlyakov, 1993; Dorer, 1998). It was shown that deep learning can achieve an adaptive approximation error rate that is faster than that of (non-adaptive) linear approximation methods (DeVore & Popov, 1988; De et al., 1993; Düng, 2011), and it outperforms any linear estimators (including kernel ridge regression) in terms of the minimax optimal rate.
From these analyses, one can see that the approximation errors and estimation errors are strongly influenced by two factors, i.e., the smoothness of the target function and the dimensionality of the input (see Table 1). In particular, they suffer from the curse of dimensionality, which is unavoid- able. However, these analyses are about the worst case errors and do not exploit specific intrinsic properties of the true distributions. For example, practically encountered data usually possess low intrinsic dimensionality, i.c., data are distributed on a low dimensional sub-manifold of the input space (Tenenbaum et al., 2000; Belkin & Niyogi, 2003). Recently, Nakada & Imaizumi (2020); Sehmidt-Hieber (2019): Chen et al. (2019); Chen et al. (2019) have shown that deep ReLU network has adaptivity to the intrinsic dimensionality of data and can avoid curse of dimensionality the intrinsic dimensionality is small. However, one drawback is that they assumed exact low dimen- sionality of the input data. This could be strong assumption because practically observed data are always noisy, and injecting noise immediately destroys the low-dimensional structure. There- fore, we consider another direction in this paper. In terms of curse of dimensionality, Suzuki (2019) showed that deep learning can alleviate the curse of dimensionality to estimate functions in so called mixed smooth Besov space (m- (m-Besov). However, m- m-Besov space assumes strong smoothness toward all directions uniformly and does not include the ordinary Besov space as special case. Moreover, the convergence rate includes heavy poly-log term which is not negligible (see Table I).
In practice, one of the typically expected properties of a true function on high-dimensional data is that it is invariant against perturbations of an input in some specific directions (Figure 1). For ex- ample, in an input image, which is utilized by data-augmentation techniques (Simard et al., 2003; Krizhevsky et al., 2012). In this paper, we investigate the approximation and estimation abilities of deep learn- ing on anisotropic Besov spaces (Nikol'skii. 1975; Vybiral, 2006; Triebel, 2011) 1) (also called dom- inated mixed-smoole Besov spaces). An anisotropic Besov space is a set of functions that have "direction-dependeen" smoothness, whereas ordinary function spaces such as Hölder, Sobolev, and Besov spaces assume isotropic smoothness that is uniform in all directions. We consider a com- position of functions included in an anisotropic Besov space, including several existing settings as special cases; it includes analyses of the Hölder space Schmidt- Suzuki (2019), as well as the low-dimensional sub-manifold setting (Nakada & Imaizumi, 2020; Schmidt-Hieber 2019; Chen et al., 2019; Chen et al., 2019)'. By considering such space, can show that deep learning can alleviate curse of dimensionality if the smoothness in each direc- tion is highly anisotropic. Interestingly, any linear estimator (including kernel ridge regression) has worse dependence on the dimensionality than deep learning. Our contributions can be summarized as follows:
tasks, the target function must be invariant against the spatial shift of
(2020) and Besov space
We consider a situation in which the target function included in a class of anisotropic Besov spaces and show that deep learning can avoid the curse of dimensionality even if the input data
We would like to remark that the analysis of Nakada & Imaizumi (2020) does not require smoothness of the embedded manifold that is not covered in this paper.

---

do not lie on low-dimensional manifold. Moreover, deep learning can achieve the optimal adaptive approximation error rate and minimax optimal estimation error rate.
We compare deep learning with general linear estimators (including kernel methods) and show that deep learning has better dependence on the input dimensionality than linear estimators.
2 Problem setting and the model
In this section, we describe the problem setting considered in this work. We consider the following nonparametric regression model:
y: = (x,) + & (1=1......
where F; is generated from a probability distribution Px on [0, & ~ (00 o²). and the data Dn (2i, wi)i== independently identically distributed. f is the true function that we want to estimate. We are interested the mean squared estimation error of an estimator f: Ep, و 1 where E.,. indicates the expectation with respect to the training data D,-
We consider least-squares estimator in the deep neural network model as f (see Eq. (5)) and discuss its optimality. More specifically, we investigate how the "intrinsic dimensionality" of data affects the estimation accuracy of deep learning. For this purpose, we consider an anisotropic Besov space as a model of the target function.
2.1 Anisotropic Besov space
In this section, we introduce the anisotropic Besov which was investigated as the model of the true function in this paper. Throughout this paper, set the domain of the input Ω [0, 1]d For function f Ω R, let I| |lf == (Jn [fl'd)) Vp for 0 p co. For p oc, define oo = [[ 1 (O) == sup.en [f()). For B E R let | = Σ 13,1².
For function d R. define the rth difference of f in the direction h Rd
(1)))) = (f)x + h) (f)xx,, (R(f(=):= := f(x), for x E Ω with rh Ω. otherwise, let (x) = 0.
Definition 1. For function E LP()) where E (0, co]. the r-th modulus of smoothness of f is
defined by wr = suphER<: (.)
(I,,...,lu 44
With this modulus of smoothness, we define the anisotropic Besov space Bpgg for B =
(B,,..., Ba)T E B44 follows.
Definition (Anisotropic Besov space (B. (1))). For < p. 5..5500 0o, r max.mm.....m. [ + 1, let the seminorm
E Rd
p.q
lBy be
1/9
Σ k=
2 wr (f. k/8, ( 2/1/81))]0
(g < o0),
Ifl fl.g..
sup 20
2* wr (f. (2 k/B f2/2///B. ..... 2-k/8a))
(9= = o0).
(f) is defined by II ||/l| + 1/ and The norm of the anisotropic Besov space ( BR (2) = LP(2) I I1/1l <o0).
Roughly speaking 3 represents the smoothness in each direction. If [, is large, then function in p.y is smooth to the ith coordinate direction, otherwise, it is non-smooth to that direction. p is also an important quantity that controls the spatial inhomogeneity of the smoothness. If 832
3a. then the definition equivalent to the usual Besov space (DeVore & Popov, 1988; De Vore et al., 1993). Suzuki (2019) analyzed curse of dimensionality of deep learning through so-called mixed smooth Besov (m-Besor Besov) space which imposes a stronger condition toward all directions uniformly.
We let N = (1,,, 3,............... 1............ 24 1, ......, 24 = {(z...... 2d) 2 E 24). = {o 2 E ].), and R++ := far 0 E IR. We let [N] = {1, (1...., N) for N E.
3

---

Particularly, it imposes stronger smoothness toward non non-coordinate axis directions. Moreover, m- Besov space does not include the vanilla Besov space as a special case and thus cannot capture the situation that we consider in this paper.
Throughout this paper, for given B (31 (B1...., Ba) TR. +++ write 3 min; Pg (smallest smoothness) and 3 == max; 8. (largest smoothness). The approximation error of a function in anisotropic Besov spaces is characterized by the harmonic mean of (B3) which corresponds to the average smoothness, and thus we define
3 11))))111))
(1)
The Besov space is closely related to other function spaces such as Hölder space. Let 8 f(r) g
=
8"101....PP (z).
Definition 3 (Hölder space (2)).. For smoothness paraemter 3 R++ with B & N, con-
sider an m times differentiable function f Red R where m. = [8] (the largest integer less than 3), and let the norm of the Hölder space (22) be lIflica == max Sm 0 fle + max sup, yen ||llea < co).
18" [(x) 8" f(w)l Then, (3-)Hölder space (2I) defined as ( = {f
12--1p
Let (I2) be the set of continuous functions equipped with _ norm: (12 = {f : 8 - R
is continuous and |l loe 50}. These function spaces are closely related to each other.
Proposition 1 (Triebel (201 There exist the following relations between the spaces:
1. For B (Bo,.... 86) E IRd with 30 $ N, it holds that C (9t) B (S))
2. For 0 P1,P2,4 cc, Pı S P2 and R. with 3 (1/p1 11/p1-1/p111 1/p2)+ it holds thar
B PL (92) + Byg ( = 1- (1/p1 1/B2)+/B.
3. For 0 p, 42 20, ạ1 q2, and 3 TR it holds that BB B Bp In particular,
with properties 1 and 2, if 3 > 1/p, it holds that B (92) + ( where = 1- 1/(5p).
4. For 0 < p, < do and B E R4+ if 3 > 1/p. then p.g (9) + (9)).
This result is basically proven by Triebel (2011). For completeness, we provide its derivation in Appendix D. If the average smoothness is sufficiently large (3 > 1/p), then the functions in B continuous; however, if it is small (3 < 1/p), then they are longer continuous. Small p indicates spatially inhomogencous smoothness; thus, spikes and jumps appear (see Donoho & Johnstone (1998) for this perspective, from the viewpoint of wavelet analysis).
2.2 Model of the true function
As model of the true function fo, we consider two types of models: Affien composition model and deep composition model. For Banach space H. we let U (H) be the unit ball of H.
(a) Affine composition model: The first model introduced is very naive model which is just composition an affine transformation and function in the anisotropic Besov space:
Hatf = (4(Ax + 6) h E UBB p.q ((0, 119),, A E dddd b R s.t. Ax + b E [o, 1J (Va E {)}}
where we assume d < d. Here, we assumed that the affine transformation has an appropriate scaling such that Ar + b included in the domain of h for all x E Ω. This is a quite naive model but provides an instructive example understand how the estimation error of deep learning behaves under the anisotropic setting.
(b) Deep composition model: The deep composition model generalizes the affine composition model a composition of nonlinear functions. Let m, d, m 1, me be the dimension of the
3 Here, we let (æ)+ := max(a, (z. 0}.
'The symbol + means continuous embedding.

---

2
Figure 1: Near low dimensional data distribution with anisotropic smoothness of the target func- tion. The target function has less smoothness (s1, $2) toward the first two coordinates on the manifold while it is almost constant toward the third coordinate (large 83).
Smooth direction
1
Non-smooth direction
(th layer, and let ((9) m be the smoothness parameter in the éth layer. The deep composition model is defined as
Hdeep= == (ha o... hy (x) he : [0, 1 1 |0, 1| de, E U(B (00, 1)(²)) (vk E [me+1])
Here, the interval [0. 1] can be replaced by another compact interval, such as [ag. bel. but this dif- ference can be absorbed by changing a scaling factor. The assumption || 8 S 1 can also be relaxed, but we do not pursue that direction due to presentation simplicity. This model includes the affine composition model as a special case. However, it requires a stronger assumption to properly evaluate the estimation error this model.
Examples The model we have introduced includes some instructive examples as listed below:
(a) Linear projection Schmidt-Hieber (2020) analyzed estimation of the following model by deep learning: (x) (w x)) where E (TO, 1)) and w Rd. this example, the function fo varies along only one direction, w. Apparently, this is an example of the affine composition model.
(b) Distribution on low dimensional smooth manifold Assume that the input is distributed on a low-dimensional smooth manifold embedded in Ω and the smoothness of the true function oo is anisotropic along coordinate direction the manifold. We suppose that the low dimen- sional manifold is d-dimensional and d < d. In this situation, the true function can be written as (x) h((())) where Rdd Rd is map that returns the coordinate of x on the manifold and is an element in an anisotropic Besov space on Rd. This situation appears if data is distributed on low-dimensional sub-manifold of Ω and the target function is invariant against noise injection to some direction on the manifold at each input point x (Figure 1 illustrates this situation). One typical example of this situation a function invariant with data augmentation (Simard al., 2003; Krizhevsky et al., 2012). Even if the noise injection destroys low dimensionality of the data distribu- tion (i.e., d = d), an anisotropic smoothness of the target function eases the curse of dimensionality as analyzed below, which is quite different from existing works (Yang & Dunson, 2016; Bickel & Li, 2007; Nakada & Imaizumi, 2020; Schmidt- Hieber,,, 2019; Chen et al., 2019; Chen et al., 2019).
Related work Here, we introduce some related work and discuss their relation sis. The statistical analysis on an anisotropic Besov space can be back to Ibragimov & Khas minskii (1984) who considered density estimation, where the density assumed to be included in an anisotropic Sobolev space with 2 2, and derived the minimax optimal rate (23/2233+1) with respect to Lo-norm. Nyssbaum (1983, 1987) analyzed nonparametric regression problem an anisotropic Besov space. Following these results, several studied have been conducted in the liter- ature pertaining to nonparametric statistics, such as nonlinear kernel estimator Kerkyacharian et al. (2001), adaptive confidence band construction Hoffmman & Lepski (2002), optimal aggregation Gaif- fas & Lecue (2011), Gaussian process estimator Bhattacharya et al. (2011, 2014), and kernel ridge regression Hang & Steinwart (2018). Basically, these studies investigated estimation problems in which the target function is in anisotropic Besov spaces, but the composition models considered in this paper have not been analyzed. Hoffman & Lepski (2002); Bhattacharya et al. (2011) consid- ered dimension reduction model; that is, the target function is dependent on only few variables of x, but they did not deal with more general models, such as the affine/deep composition models. The nonparametric regression problems where the input data are distributed on a low-dimensional smooth manifold has been studied as a "manifold regression" Yang & Dunson (201 6); Bickel & Li
analy-
5

---

(2007); Yang & Tokdar (2015). Such model can be considered as specific example of the deep composition model. In this sense, our analysis is significant extension of these analyses.
Approximation error analysis
Here, we consider approximating the true function f via deep neural network and derive the approximation error. As the activation function, we consider the ReLU activation denoted by
((ar) = max (x, 0} (xr E IR). For vector I, n7(x)) is operated in an element-wise manner. The
model of neural networks with height I,, width W, sparsity constraint S, and norm constraint B as (LL, W, S, B) == ((V(L))()) (()) + ((5)) o... (WO(z + b(U) W(L) E RIIW b(L) E R, W(1)
RWxd xd 8()) E IR HWW W(0 E I WxW ((0) E RWW (1 < L), E. (IMV0)
+ ((100)) 1160%))
S S, max, || V ||600) I B}. where || llo is the fo-norm of the matrix (the number of non- zero elements of the matrix), and || 1l is the &o -norm of the matrix (maximum of the absolute values of the elements). The sparsity constraint and norm bounds are required to obtain the near- optimal rate of the estimation error. To evaluate the accuracy of the deep neural network model in approximating target functions, we define the worst-case approximation error as
(T, H) == y EH y= Ilf fll (2)))
where F is the set of functions used for approximation, and H. is the set of target functions.
Proposition 2 (Approximation ability for anisotropic Besov space). Suppose that 0 < p,q," S oo and B E 144+ satisfy the following condition: > (1/p - 1/r)+- Assume that m E N satisfies 0 < 3 < min(m, 6dm(m + 2) + 2d. Then, for E N. we can bound the approximation error as
1/p). Let d (1/p 1/r)+,
(3 5))(25) and Wo(d)
R W1, W1, S1, BI), (9))) x N
by setting
reca, ) (og m]], Wi(d) == NW.. (1 = [[L - 1) + I]N, (i = O 2)0/--0), :))
(dd) = 2[0g2
gdvmm
(2)
(3)
for N N 3 loogoN and a constant c(d.m) depending only on and m.
The proof of this proposition is provided in Appendix B. The rate N is the optimal adaptive approximation error rate that can be achieved by a model with N parameters (the difference be- tween adaptive and non-adaptive methods explained in the discussion below). Note that this is an approximation error in an oracle setting and no sample complexity appears here. We notice that
avoid the curse of dimensionality if the average smoothness B is small. This means that the target function is non-smooth in only a few directions and smooth in other directions, we can avoid the curse of dimensionality. In contrast, if we consider isotropic Besov space where
31 = 3a(== 3), then 3 3/d, which directly depends on the dimensionality d, and we need an exponentially large number of parameters in this situation to achieve e-accuracy. Therefore, the anisotropic smoothness has a significant impact on the approximation error rate. The assumption > (1/p- - 1/r)+ ensures the L.piinterrbbiliyy of the target function, and the inequality (without equality) admits near-optimal wavelet approximation of the target function in terms of L,-norm.
Using this evaluation as a basic tool, we can obtain the approximation error for the deep composition models. We can also obtain the approximation error for the affine composition models, but it is almost identical to Proposition 2. Therefore, we defer to Appendix A.
....,. H. Then, the Theorem 1 (Deep composition model). Assume that T(0) > 1/p for all l = I,...,H estimation error on the deep composition model is bounded as
Roo ( (4 Hdeep) S max N -8
(4)
8E[H]
where (z(()= =3(( I [13 (0)()) 1/p) and I'' 1), W maxe(Wi (me))
m S S=
+ 3me+1), B max, Bi (me).

---

The proof can be found in Appendix B.I. Since the model is more general than the vanilla anisotropic Besov space, require stronger assumption ( > 1/p on 3(0) than the condi- tion in Proposition 2. This is because we need to bound the Hölder smoothness of the remaining layers to bound the influence of the approximation error in the internal layers to the entire function. Hölder smoothness is ensured according to the embedding property under this condition (Proposi- tion 1). This Hölder smoothness assumption affects the approximation enror rate. The convergence rate 3+(6) in Eq. (4) different from that in Eq. (8). This is because the approximation error in the internal layers are propagated through the remaining layers with Hölder smoothness and its amplitude is controlled by the Hölder smoothness.
Approximation error by non-adaptive method The approximation error obtained in the previous section is called an adaptive error rate in the literature regarding approximation theory (DeVore, 1998). If we fix N bases beforehand and approximate the target function by linear combination of the N bases (which is called the non-adaptive method), then we cannot achieve the adaptive error rate obtained in the previous section. Roughly speaking, the approximation error of non-adaptive methods is lower bounded by N (3-(p ( (Myronyuk, 2015, 2016, 201 7), which is slower than the approximation error rate of deep neural networks especially for small p.
Estimation error analysis
In this section, we analyze the accuracy of deep learning in estimating function in compositions of anisotropic Besov spaces. We consider a least-squares estimator in the deep neural network model:
i -= argminn (.s.:,,W..... Σi= (v: - f(x:)))
(5)
where f is the clipping of f defined by f = min ( ff -F}. F} for a constant F >> O which is realized by ReLU units. The network parameters (L, W, B) should be specified appropriately as indicated in Theorems 2 and 3. In practice, these parameters can be specified by cross validation. Indeed, we can theoretically show that cross validation can provide the appropriate choice of these parameters in compensation to an additional ( in the estimation error bound. This esti- mator can be seen as sparsely regularized estimator because there are constraints on S. In terms of optimization, this requires combinatorial optimization, but we do not pursue the computational aspect. The estimation error that we derive in this section can involve the optimization error, but for simplicity, we only demonstrate the estimation error of the ideal situation where there is no optimization error.
Affine composition model for the affine composition model.
The following theorem provides upper bound of the estimation error
Theorem 2. Assume the same condition as in Theorem 6; in particular, suppose < P. S oo and B > (1/p- 1/2)+ + for E 14++. Moreover, we assume that the distribution Px has a density px such that ||px 1|=0 so I R for constant R O. If fo E Hatt O 1 (2), and |1 F for
(d) as in Theorem 6 with F > 1; then, letting (W, L. B) (Li(d), W Wi (d), S (d), (dC + (d))
N 28-1, we obtain
23 Ep. Illf M(Z S 20 log(n)3,
where E.D...) [.] indicates the expectation with respect to the training data Dn-
The proof is provided in Appendix C. We will show that the convergence rate n (25(()++1) is min- imax optimal in Section 5 (see also Kerkyacharian & Picard (1992); Donoho et al. (1996); Donoho & Johnstone (1998); Giné & Nickl (2015) for ordinary Besov spaces). The L -orm constraint || < F is used to derive uniform bound on the discrepancy between the population and the empirical n.2-norm. Without this condition, the convergence rate could be slower.
Deep composition model For the deep composition model, we obtain the following convergence rate. This is an extension of Theorem 2 but requires stronger assumption on the smoothness.
Theorem 3. Suppose that 0 < p.q S co and ()() 1/p all & E [H]. If f E HHdeep O I I, (?),
and || I F for F 2 1, then we obtain
Ep. IlI M1ZApp max n -23-10 -23-10/(23--01 log(n)3,
7

---

where 3-(0) is defined in Theorem 1, and (L, B) is as given in Theorem with N X
maxzelL] n 11.
The proof is provided in Appendix C. We will show that this also minimax optimal Theorem 4. Because of the Hölder continuity, the convergence rate becomes slower than the affine composition model (that is, (*(() < B()). However, this slower rate is unavoidable in terms of the minimax optimal rate. Schmidt--Heebe (2020) analyzed the same situation for the Hölder class which corre- sponds to 8
Our analysis far extends their analysis to the setting of anisotropic Besov spaces in which the parameters B(6), p, q have much more freedom.
/ (VE) and p
From these bounds (Theorems 2 and 3), we can that the smoothness / becomes large, the convergence rates faster. If the target function included in the isotropic Besov space with smoothness B1 =... Ba(= B), then the estimation error becomes
(Isotropic Besov)
2,8 28/(20+4),
In the exponent, the dimensionality d appears, which causes the curse of dimensionality, In contrast, if the target function is in the anisotropic Besov space, and the smoothness in each direction is sufficiently imbalanced such that 3 does not depend on d, obtained rate
(Anisotropic Besov)
n 22/(2
avoids the curse of dimensionality. For nigh-dimensional settings, there would be several redundant directions in which the true function does not change. Deep learning is adaptive to this redundancy and achieves better estimation error. However, in Section 6, we prove that linear estimators are affected by the dimensionality more strongly than deep learning. This indicates the superiority of deep learning.
5 Minimax optimal rate
Here, we show that the estimation error rate, that we have presented, of deep learning achieves the minimax optimal rate. Roughly speaking the minimax optimal risk on a model _ of the true function is the smallest worst case eтror over all estimators:
R. (F)) == sup F.D,, [Il] - (0)E
where f runs over all estimators. The convergence rate of the minimax optimal risk referred to as minimax optimal rate. We obtain the following minimax optimal rate for anisotropic Besov spaces.
Theorem 4. (a) Affine composition model: For 0 < S oc and B E 144 assume that 3 max {L/p 1/2.1/2 1,0} Then, the minimax optimal risk of the affine composition model is lower bounded R. (Haft Z n 28+1 (b) Deep composition model: For 0 < P,q S oo and ((0) Rd (E .,..., H), assume that 300) 1/p. Let >> 0 be arbitrarily small for q < oo, and O. Let g=(() 3(0) II 1/p+t)A1], and 3 = min, (1) Then, the minimax optimal risk of the deep composition model is lower bounded as R. (HHsep) 2
= =
23-
The proof is provided in Appendix E (see also Ibragimov Khas' minskii (1984); Nyssbaum (1987)). From this theorem, we can see that the estimation error of deep learning shown in The- orems 2 and indeed achieve the minimax optimal rate up to poly-log(n) factor.
Suboptimality of linear estimators
In this section, we give the minimax optimal rate in the class of linear estimators. The linear estimator a class of estimators that can be written as
f(x) = Ei Wap:e;;; X"),
where X (æi,... ..)) and (a; X²) (i = 1,...,n) n) are (measurable) functions that only depend and X This is linearly dependent on y (y1,..., Vo). We notice that the kernel

---

ridge regression is included in this class because it can be written as f(z) kz.x" (kx",."" + AT)- which linearly depends on Y This class includes other important estimators, such as the Madaraya-Watson estimator, the k-nearest neighbor estimator, and the sieve estimator. We compare deep learning with the linear estimators in terms of minimax risk. For this purpose, we define the minimax risk of the class of linear estimators:
(lin)
inf f: linear foe
sup E.p,,
where J runs over all linear estimators. We can see that linear estimators suffer from the sub-optimal rate because of the following two points: (i) they do not have adaptivity, and (ii) they significantly suffer from the curse dimensionality.
Theorem 5. (i) Suppose that the input distribution Px is the uniform distribution on = [0, 1] and
assume that B > 1/p and 1 S P.q S co. Then, the minimax optimal rate of the linear estimators is lower bounded as
R!!in) (U(())) 2
28 2011
(6)
where u = 1/1)p-
(ii) In addition to the above conditions, assume that the true function is included in the affine
composition model with d S d, 3 = B1 =... 33 and 0 p 2. Let a, = 1 + with arbitrary small k > O when < d/2, and let aa O when à 2 d/2. Then, the minimax rate of the linear estimators on the affine composition model is lower bounded by
212 (18-A/otd/2ted)
R(lin) (Haft) Z
2(8-6/p4d/24aj/))
The proof is provided Appendix F. (i) The lower bound (7) reveals the suboptimality of linear estimators in terms of imput dimensionality. Actually, if we consider a particular case where d 1, p and >> d, then the obtained minimax rate linear estimators and the estimation error rate of deep learning can be summarized as
20+d
23
linear: : 22-22
deep n 1241
by Theorem 2 when (which be checked by noticing d 3/3 =1 in this situation). We can see that the dependence on the dimensionality of linear estimators is significantly worse than that of deep leaning. This indicates poor adaptivity of linear estimators the intrinsic dimensionality of data. Actually, as d becomes large, the rate for the linear estimator approaches to 1/v2 but that for the deep learning is not affected by d and still faster than 1/vn.. To show the theorem, used the "convex-hur argument" developed by Hayakawa & Suzuki (2019); Donoho & Johnstone (1998). We combined this technique with the so-called Irie-Miyake's integral representation (Irie & Miyake, 1988; Hornik et al., 1990). Note that this difference appears because there is an affine transformation in the first layer of the affine composition model. Deep learning flexible against such a coordinate transform so that it can find directions to which the target function is smooth. In contrast, kernel methods do not have such adaptivity because there is no feature extraction layer. (ii) The lower bound (6) states that when p 2 (that is, v > 0). the minimax rate of the linear estimators outperformed by that of deep learning (Theorem 2). This due to the "adaptivity" of deep leaning, When p is small, the smoothness of the target function is less homogencous, and it requires an adaptive approximation scheme to achieve the best estimation error. Linear estimators do not have adaptivity and thus fail achieve the minimax optimal rate. Our bound (6) extends the result by Zhang et al. (2002) to multivariate anisotropic Besov space while Zhang et al. (2002) investigated the univariate space (d 1).
7 Conclusion
We investigated the approximation error and estimation error of deep learning in the anisotropic Besov spaces. was proved that the convergence rate determined by the average of the anisotropic smoothness, which results in milder dependence on the input dimensionality. If the smoothness is

---

highly amisotropic, deep learning can avoid overfitting. We also compared the error rate of deep learning with that of linear estimators and showed that deep learning has better dependence on the input dimensionality. Moreover, it was shown that deep learning can achieve the adaptive rate and outperform non-adaptive approximation methods and linear estimators if the homogeneity p of smoothness is small. These analyses strongly support the practical success of deep learning from theoretical perspective.
Limitations of this work Our work does not cover the optimization aspect of deep learning. is assumed that the regularized least squares (5) can be executed. It would be nice to combine our study with recent developments of non-convex optimization techniques (Vempala & Wibisono, 2019; Suzuki & Akiyama, 2021).
Potential negative societal impact Since this is purely theoretical result, it is not expected that there is direct negative societal impact. However, revealing detailed properties of the deep learning could promote an opportunity to pervert deep learning.
Acknowledgment
TS was partially supported by JSPS KAKENHI (18H03201), Japan Digital Design and JST CREST. AN was partially supported by JSPS Kakenhi (19K20337) and JST-PRESTO.
References
M. Belkin and Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-1399 2003.
A. Bhattacharya, D. Pati, and D. B. Dunson. Adaptive dimension reduction with a gaussian process prior. arXiv preprint arXiv:1111. 1445, 2011.
A. Bhattacharya, D. Pati, and D. Dunson. Anisotropic function estimation using multi-bandwidth gaussian processes. Annals of statistics, 42(1):352, 2014.
J. Bickel and B. Li. Local polynomial regression on unknown manifolds. In Complex datasets and inverse problems, pp. 177-186. Institute of Mathematical Statistics, 2007.
M. Chen, H. Jiang, W. Liao, and T. Zhao. Nonparametric Regression on Low-Dimensiona. Mani- folds using Deep ReLU Networks. arXiv e-prints, art. arXiv: 1908.0184. Aug 2019.
M. Chen, H. Jiang. W. Liao, and T. Zhao, Efficient approximation deep relu networks for functions on low dimensional manifolds. In Advances in Neural Information Processing Systems, pp. 8 8172- 8182, 2019.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303-314, 1989.
J. Devlin, M.-W. Chang. K. Lee, and K. Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, arXiv e-prints, art. arXiv:1810.0488 Oct 2018
R. A. DeVore. Nonlinear approximation. Acta Numerica, 7:51-150, 1998.
R. A. DeVore and Popov. Interpolation of Besov spaces. Transactions of the American Mathematical Society, 305(1):397-414, 1988.
R. DeVore, G. Kyriazis, D. Leviatan, and V. M. Tikhomirov. Wavelet compression and nonlinearn-widthe Advances in Computational Mathematics. 1(2):197-114, 1993.
D. L. Donoho and I. M. Johnstone. Minimax estimation via wavelet shrinkage. The Annals of Statistics, 26(3):879-921) 1998.
D. I.. Donoho, Johnstone, Kerkyacharian, and D. Picard. Density estimation by wavelet thresholding, The Annals of Statistics, 24(2):508-539 1996.
10

---

D. Düng, Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34(1): 1-41, 2011.
Gaiffas and G. Leeue, Hpper-sparse optimal aggregation. Journal of Machine Learning Research, (8)Jun):1813-188) 2011.
E. Giné and R. Nickl. Mathematical Foundations Lnfinite-iimnnsionaal Statistical Models. Cam- bridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2015.
X. Glorot, A. Bordes, and Y. Bengio. Deep sparse rectifier neural networks. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 315-323, 2011.
H. Hang and I. Steinwart. Optimal learning with anisotropic gaussian svms. arXiv:1810.023211 2018.
arXiv preprint
Hayakawa and T. Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. arXiv preprint arXiv: 2019.
M. Hoffmman and O. Lepski. Random rates in anisotropic regression (with discussion and rejoin- der by the authors). The Annals of Statistics, 30(2):225-396, 04 2002.
K. Hornik, Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251-257, 1991.
K. Hornik, M. Stinchcombe, and H. White. Universal approximation of unknown mapping and its derivatives using multilayer feedforward networks. Newral Networks, 3(5)551--560, 1990.
I. Ibragimov and R. Khas minskii. More on the estimation of distribution densities. Journal of Soviet Mathematics, 25(3):1155-115 1984.
B. Irie and Miyake. Capabilities of three-layered perceptrons. In JEEE 1988 International Con- ference on Neural Networks, pp. 641-648, 1988.
G. Kerkyacharian and D. Picard. Density estimation in Besov spaces. Letters, 13:15-24, 1992.
Statistics & Probability
G. Kerkyacharian, O. Lepski, and D. Picard. Nonlinear estimation in anisotropic multi-index de- noising. Probability Theory and Related Fields, 121(2):137-770, Oct 2001.
A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
V. Myronyuk. Trigonometric approximations and kolmogorov widths of anisotropic besov classes of periodic functions of several variables. Ukrainian Mathematical Journal, 66(8), 2015.
Myronyuk. Kolmogorov widths of the anisotropic besov classes of periodic functions of many variables. Ukrainian Mathematical Journal, (8(55:788-72,, Oct 2016.
V. V. Myronyuk. Widths of the anisotropic besov classes of periodic functions of several variables. Ukrainian Mathematical Journal, 68(8) Jan 2017. ISSN 1573-9376. doi: 10.1007/ 10tp://11..0000/1111/0 1ttp://111122001-1121111-0
111223-017-129011 URL https:
V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceed- ings of the 27th International Conference on Machine Learning, pp. 807-814, 2010.
R. Nakada and M. Imaizumi. Adaptive approximation and generalization of deep neural network with intrinsic dimensionality, Journal of Machine Learning Research, 21(174):1-38, 2020. URL http:// http://iinrr.oooppprreeeee wttp:/appre////1/2000000 html.
S. M. Nikol skii. Approximation of functions of several variables and imbedding theorems, volume 205. Springer-Verte Verlag Berlin Heidelberg, 1975.
M. Nysshaum. Optimal filtration of a function of many variables in white gaussian noise. Problems of Information Transmission, 19:23-29, 1983.

---

M. Nyssbaum. Nonparametric estimation of a regression function that is smooth in domain in R Theory of Probability Its Applications, 31(1):108-115, 1987.
A. Radford, L. Metz, and Chintala. Unsupervised Representation Learning with Deep Convolu- tional Generative Adversarial Networks. arXiv e-prints, art. arXiv:1511. 1.06434, Nov 2015.
J. Schmidt-Hieber. Deep ReLU network approximation of functions manifold. arXiv preprint /:Xi::/908.00695, 2019.
J. Schmidt-Hieber, Nonparametric regression using deep neural networks with relu activation func- tion. The Annals of Statistics, 18(4):1875-188) 2020.
Y. Simard, D. Steinkraus, and J. C. Platt. Best practices for convolutional neural networks applied to visual document analysis. In Proceedings of the Seventh International Conference on Document Analysis and Recognition- Volume 2, pp. 958. IEFE Computer Society, 2003.
Sonoda and N. Murata. Neural network with unbounded activation functions is universal approx- imator. Applied and Computational Harmonic Analysis, 43(2):233-263 2017.
T. Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learming Representa- tions (ICLR2019), 2019. URL https: httpe////pppeeeeeeeeeeeeeeee
Suzuki and S. Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Prov- able excess risk bound and superiority to kernel methods. In International Conference on Learn- ing Representations, 2021. URL
Temlyakov. Approximation of Periodic Functions. Nova Science Publishers, 1993.
B. Tenenbaum, V. De Silva, and C. Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-33333 2323, 2000.
H. Triebel. Entropy numbers in function spaces with mixed integrability, Revista matemática com- plutense,
2011.
S. Vempala and A. Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. In Advances in Neural Information Processing Systems, pp. 8094 8106, 2019.
Vybiral. Function spaces with dominating mixed smoothness. Dissertationes Math. (Rozprawy Mat.), 436:3-73,2000
Y. Yang and D. B. Dunson. Bayesian manifold regression. The Annals of Statistics, 44(2):876-905, 2016.
Y. Yang and S. T. Tokdar. Minimax-optimal nonparametric regression in high dimensions. The Annals of Statisties, 43(2):652-674, 2015.
D. Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 114-114,7 2017.
S. Zhang, M.-Y. Wong, and 7. Zheng. Wavelet threshold estimation of a regression function with random design. Journal of Multivariate Analysis, 80(2):256-284, 2002.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Each theorem explicitly describes assumptions which the theorem is established.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix in the supplementary material. All proofs are included there.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report enror bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "B-NQdDykfjA", "reviewer": "Reviewer_p9g3", "summary": "In this paper, the authors investigate the approximation and estimation error of deep neural networks on anisotropic Besov spaces. It has been shown that Holder and Sobolev function spaces are plagued by an unavoidable curse of dimensionality, and a line of research has focused on showing how deep neural network can adaptively beat this curse on restricted classes of functions, such as compositorial functions or functions that depend on a low dimension subspace. This work focuses on Besov spaces, but with anisotropic smoothness requirements (which do not require for the data to lie exactly on a low dimensional subspace) and consider deep composition model similarly to Schmidt-Hieber (2018), but with functions in the anisotropic Besov spaces (they don’t need to be low-dimensional). They show that the rate of approximation/estimation depends on the harmonic mean of the directional smoothness parameters, instead of the worst case. In particular, this harmonic mean is independent of the dimension if the function is non smooth in only a few directions. Their results require bounds on the width, depth, sparsity, and infinity norm of the weights. They further show that the estimation error rates are minmax optimal. Finally they consider linear estimators and show a lower bound on their minimax rate, that is larger than the minimax rate of neural networks, which illustrates the poor adaptivity of linear estimators to the intrinsic dimensionality of the data.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper present new strong results which combines expressivity and generalization bounds on deep neural networks. The adaptivity to the average smoothness instead of the worst case smoothness is particularly interesting. For these reasons, I recommend the paper to be accepted. \n\nIt would be great to comment more on the dependency of the different quantities on $n,d$ and other parameters. The current theorems are difficult to parse. For example, $N$ is proportional to the number of non zero parameters? For $\\tilde{\\beta}$ to not be of order $1/d$, $m$ needs to scale with $d$, is $L_1(d)$ linear in $d$ then? I think adding a few remarks would go a long way in improving the readability of these results.\n\nWhile I think this represents an interesting theoretical work for the approximation/function space estimation community, I wonder how much this approach can help understand practical success of deep learning (in particular, I disagree with the last sentence of the conclusion ``''these analyses strongly support the practical success of deep learning from a theoretical perspective’’). In particular, numerous work have demonstrated that one cannot disentangle computational and statistical aspects in deep learning. Furthermore, the theorems have a sparsity requirement, which is usually not the case for practically trained neural networks. \n\nTypos: reference to Theorem 6 in Theorem 2? Reference to equation 8 bottom of page 6?\n\n\n-------- update after rebuttal -------\n\nThank you to the authors for the response. I am satisfied with the paper and the updates mentioned by the authors. I keep the same rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7u0wStwKTBf", "reviewer": "Reviewer_DZ84", "summary": "The paper studies adaptivity of deep neural network models to anisotropic smoothness properties of target functions. Namely, when the target function belongs to an anisotropic Besov space (i.e. it has different levels of smoothness in different input directions), certain classes of deep networks may provide a rate that only depends on the average smoothness (i.e. the harmonic mean of certain smoothness parameters in each direction), instead of the worst-case smoothness. This is also studied for target functions that consist of compositions of such anisotropic Besov functions and compositions with an affine function. The authors also provide minimax lower bounds showing that linear estimators (such as kernel methods) may not adapt to such structures, and may provide exponentially worse sample complexity for some specific models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper studies adaptivity properties of deep networks, a topic which has recently gained a lot of attention, as it can yield an understanding of what kind of functions deep learning can learn efficiently, and more efficiently than other standard procedures such as kernels. It provides a comprehensive study of adaptivity of neural networks to anisotropic smoothness, which is a useful prior, and has not been previously studied in this context. In this sense, I find the paper significant and novel. It is also very well written. I thus recommend acceptance.\n\nA few minor comments:\n* the authors briefly mention a motivation for anisotropic smoothness in the context of invariances on image problems. This seems quite interesting but the current explanation is very brief - I encourage the authors to expand further on this, and perhaps on other motivating examples.\n* why is tilde{beta} in (1) defined like this instead of just as the harmonic mean? I find that this makes the rates with +1 instead of +d a bit puzzling to parse, and would find it more natural to just have the harmonic mean, so that you immediately recognize the usual rate when all the betas are equal (but I leave this choice to the authors).\n* some typos: L199: d beta -> beta / d? L301: why the red text?\n\n\n-------- update after rebuttal -------\n\nThank you for the response. I think these additional comments on motivating examples would be useful in the paper, so please do include them in the final version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1vd11rr2XxP", "reviewer": "Reviewer_PyLN", "summary": "This paper provides a constructive approximation results of deep neural networks for approximating functions in anisotropic Besov spaces. The approximation result is further used to show the statistical convergence of using neural networks in a nonparametric regression problem. The highlights of the work fall in the circumvent of the curse of data dimensionality, when the anisotropic Besov space is not homogeneous in every canonical direction.\n\nSome recent works study the adaptivity of neural networks to the intrinsic structures in data (Nakada & Imaizumi, 2020; Schmidt-Hieber, 2019; Chen et al., 2019), which can partially explain the practical success of neural networks in high-dimensional data applications. This work takes a different perspective: rather than considering the low-dimensional structures in the data manifold, the authors focus on \"low-dimensional\" structures in the function space. Intuitively, the \"low-dimensional\" structures in the function space refers to functions having very mild fluctuations in certain directions. This is a relatively less explored direction, yet of importance.\n\nThe paper is well organized and relatively easy to follow.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am tending positive on the paper. There are a few questions.\n\n1) Is it true that the composition of two anisotropic Besov functions is still an anisotropic Besov function? If so, I don't see the merit of considering two models of the true functions in Section 2.2, as deep composition can also be viewed as a special case of affine composition model, and vice versa.\n\n2) Per definition of $\\tilde{\\beta}$ in Equation (1), when $\\beta_j$ is approximately equal, there is still the curse of data dimensionality. However, when only a small fraction of $\\beta_j$'s are small (severe fluctuation of the target function in these directions), the result is free of the curse. In such a case, is it possible that the target function may be approximated first by a function only supported on those significant coordinates, and then approximate the function on those significant coordinates? It seems that this argument translates finally to some low-dimensional structures in data. Can the authors kindly comment on this?\n\n3) A practical motivation of studying anisotropic Besov spaces seems missing.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discussed the limitations in Section 7. No direct negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a theory paper that analyzes deep neural networks through the lens of anisotropic Besov space. The paper provides a comprehensive study of adaptivity of neural networks to anisotropic (=direction-dependent) smoothness. The paper is clearly written and the authors have carefully positioned their work relative to prior works.
Decision: Accept (Spotlight)