Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space
Year: 2022

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-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.

heading: 1 Introduction
text: Based on the recent literature pertaining to machine learning, deep learning has exhibited superior performance in several tasks such as image recognition (Krizhevsky et al., 2012), natural language processing (Devlin et al., 2018), and image synthesis (Radford et al., 2015). In particular, its superiority is remarkable for complicated and high-dimensional data like images. This is mainly due to its high flexibility and superior feature-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, optimization, and generalization error.
Amongst representation ability analysis of deep neural networks such as universal approximation ability (Cybenko, 1989; Hornik, 1991; Sonoda & Murata, 2017), approximation theory of deep neural networks on typical function classes such as Hölder, Sobolev, and Besov spaces have been extensively studied. In particular, analyses of 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 Hö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 (NeurIPS 2021).
Besov space by utilizing the techniques developed in approximation theories (Temlyakov, 1993; DeVore, 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; DeVore et al., 1993; Dũ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 unavoidable. 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.e., data are distributed on a low dimensional sub-manifold of the input space (Tenenbaum et al., 2000; Belkin & Niyogi, 2003). Recently, Nakada & Imaizumi (2020); Schmidt-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 if the intrinsic dimensionality is small. However, one drawback is that they assumed exact low dimensionality of the input data. This could be a strong assumption because practically observed data are always noisy, and injecting noise immediately destroys the low-dimensional structure. Therefore, 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 a so called mixed smooth Besov space (m-Besov). However, m-Besov space assumes strong smoothness toward all directions uniformly and does not include the ordinary Besov space as a special case. Moreover, the convergence rate includes heavy poly-log term which is not negligible (see Table 1).
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 example, in image-recognition tasks, the target function must be invariant against the spatial shift of 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 learning on anisotropic Besov spaces (Nikol’skii, 1975; Vybiral, 2006; Triebel, 2011) (also called dominated mixed-smooth Besov spaces). An anisotropic Besov space is a set of functions that have “direction-dependent” smoothness, whereas ordinary function spaces such as Hölder, Sobolev, and Besov spaces assume isotropic smoothness that is uniform in all directions. We consider a composition of functions included in an anisotropic Besov space, including several existing settings as special cases; it includes analyses of the Hölder space Schmidt-Hieber (2020) and Besov space 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)1. By considering such a space, we can show that deep learning can alleviate curse of dimensionality if the smoothness in each direction 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:
• We consider a situation in which the target function is included in a class of anisotropic Besov spaces and show that deep learning can avoid the curse of dimensionality even if the input data
1We 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 a 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.

heading: 2 Problem setting and the model
text: In this section, we describe the problem setting considered in this work. We consider the following nonparametric regression model:
yi = f o(xi) + ξi (i = 1, . . . , n),
where xi is generated from a probability distribution PX on [0, 1]d, ξi ∼ N(0, σ2), and the data Dn = (xi, yi)ni=1 are independently identically distributed. f
o is the true function that we want to estimate. We are interested in the mean squared estimation error of an estimator f̂ : EDn [‖f̂ − fo‖2L2(PX)], where EDn [·] indicates the expectation with respect to the training data Dn. We consider a 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.

heading: 2.1 Anisotropic Besov space
text: In this section, we introduce the anisotropic Besov which was investigated as the model of the true function in this paper. Throughout this paper, we set the domain of the input to Ω = [0, 1]d. For a function f : Ω → R, let ‖f‖p := ‖f‖Lp(Ω) := ( ∫ Ω |f |pdx)1/p for 0 < p < ∞. For p = ∞, we
define ‖f‖∞ := ‖f‖L∞(Ω) := supx∈Ω |f(x)|. For β ∈ Rd++, let |β| = ∑d j=1 |βj |2.
For a function f : Rd → R, we define the rth difference of f in the direction h ∈ Rd as
∆rh(f)(x) := ∆ r−1 h (f)(x+ h)−∆ r−1 h (f)(x), ∆ 0 h(f)(x) := f(x),
for x ∈ Ω with x+ rh ∈ Ω, otherwise, let ∆rh(f)(x) = 0. Definition 1. For a function f ∈ Lp(Ω) where p ∈ (0,∞], the r-th modulus of smoothness of f is defined by wr,p(f, t) = suph∈Rd:|hi|≤ti ‖∆ r h(f)‖p, for t = (t1, . . . , td), ti > 0.
With this modulus of smoothness, we define the anisotropic Besov space Bβp,q(Ω) for β = (β1, . . . , βd)
> ∈ Rd++ as follows. Definition 2 (Anisotropic Besov space (Bβp,q(Ω))). For 0 < p, q ≤ ∞, β = (β1, . . . , βd)> ∈ Rd++, r := maxibβic+ 1, let the seminorm | · |Bαp,q be
|f |Bβp,q :=  ( ∞∑ k=0 [2kwr,p(f, (2 −k/β1 , . . . , 2−k/βd))]q )1/q (q <∞),
supk≥0 2 kwr,p(f, (2 −k/β1 , . . . , 2−k/βd)) (q =∞).
The norm of the anisotropic Besov space Bβp,q(Ω) is defined by ‖f‖Bβp,q := ‖f‖p + |f |Bβp,q , and Bβp,q(Ω) = {f ∈ Lp(Ω) | ‖f‖Bβp,q <∞}.
Roughly speaking β represents the smoothness in each direction. If βi is large, then a function in Bβp,q 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 β1 = β2 = · · · = βd, then the definition is equivalent to the usual Besov space (DeVore & Popov, 1988; DeVore et al., 1993). Suzuki (2019) analyzed curse of dimensionality of deep learning through a so-called mixed smooth Besov (m-Besov) space which imposes a stronger condition toward all directions uniformly.
2We let N := {1, 2, 3, . . . }, Z+ := {0, 1, 2, 3, . . . }, Zd+ := {(z1, . . . , zd) | zi ∈ Z+}, R+ := {x ≥ 0 | x ∈ R}, and R++ := {x > 0 | x ∈ R}. We let [N ] := {1, . . . , N} for N ∈ N.
Particularly, it imposes stronger smoothness toward non-coordinate axis directions. Moreover, mBesov 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 β = (β1, . . . , βd)> ∈ Rd++, we write β := mini βi (smallest smoothness) and β := maxi βi (largest smoothness). The approximation error of a function in anisotropic Besov spaces is characterized by the harmonic mean of (βj)dj=1, which corresponds to the average smoothness, and thus we define
β̃ := (∑d
j=1 1/βj
)−1 . (1)
The Besov space is closely related to other function spaces such as Hölder space. Let ∂αf(x) = ∂|α|f ∂α1x1...∂ αdxd (x).
Definition 3 (Hölder space (Cβ(Ω))). For a smoothness paraemter β ∈ R++ with β 6∈ N, consider an m times differentiable function f : Rd → R where m = bβc (the largest integer less than β), and let the norm of the Hölder space Cβ(Ω) be ‖f‖Cβ := max|α|≤m ∥∥∂αf‖∞ + max|α|=m supx,y∈Ω |∂αf(x)−∂αf(y)| ‖x−y‖β−m . Then, (β-)Hölder space C
β(Ω) is defined as Cβ(Ω) = {f | ‖f‖Cβ <∞}.
Let C0(Ω) be the set of continuous functions equipped with L∞-norm: C0(Ω) := {f : Ω → R | f is continuous and ‖f‖∞ <∞}. These function spaces are closely related to each other. Proposition 1 (Triebel (2011)). There exist the following relations between the spaces:
1. For β = (β0, . . . , β0)> ∈ Rd with β0 6∈ N, it holds that Cβ0(Ω) = Bβ∞,∞(Ω). 2. For 0 < p1, p2, q ≤ ∞, p1 ≤ p2 and β ∈ Rd++ with β̃ > (1/p1 − 1/p2)+3, it holds that4
Bβp1,q(Ω) ↪→ B γβ p2,q(Ω) for γ = 1− (1/p1 − 1/p2)+/β̃.
3. For 0 < p, q1, q2 ≤ ∞, q1 < q2, and β ∈ Rd++, it holds that Bβp,q1 ↪→ B β p,q2 . In particular,
with properties 1 and 2, if β̃ > 1/p, it holds that Bβp,q(Ω) ↪→ Cγβ(Ω) where γ = 1− 1/(β̃p). 4. For 0 < p, q ≤ ∞ and β ∈ Rd++, if β̃ > 1/p, then Bβp,q(Ω) ↪→ C0(Ω).
This result is basically proven by Triebel (2011). For completeness, we provide its derivation in Appendix D. If the average smoothness β̃ is sufficiently large (β̃ > 1/p), then the functions in Bβp,q are continuous; however, if it is small (β̃ < 1/p), then they are no longer continuous. Small p indicates spatially inhomogeneous smoothness; thus, spikes and jumps appear (see Donoho & Johnstone (1998) for this perspective, from the viewpoint of wavelet analysis).

heading: 2.2 Model of the true function
text: As a model of the true function fo, we consider two types of models: Affien composition model and deep composition model. For a Banach spaceH, we let U(H) be the unit ball ofH. (a) Affine composition model: The first model we introduced is a very naive model which is just a composition of an affine transformation and a function in the anisotropic Besov space:
Haff := {h(Ax+ b) | h ∈ U(Bβp,q([0, 1]d̃)), A ∈ Rd̃×d, b ∈ Rb s.t. Ax+ b ∈ [0, 1]d̃ (∀x ∈ Ω)},
where we assume d̃ ≤ d. Here, we assumed that the affine transformation has an appropriate scaling such that Ax + b is included in the domain of h for all x ∈ Ω. This is a quite naive model but provides an instructive example to 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 to a composition of nonlinear functions. Let m1 = d, mL+1 = 1, m` be the dimension of the
3Here, we let (x)+ := max{x, 0}. 4The symbol ↪→ means continuous embedding.
`th layer, and let β(`) ∈ Rm`++ be the smoothness parameter in the `th layer. The deep composition model is defined as
Hdeep := {hH ◦ · · · ◦ h1(x) | h` : [0, 1]m`→ [0, 1]m`+1 , h`,k ∈ U(Bβ (`) p,q ([0, 1] m`)) (∀k ∈ [m`+1])}.
Here, the interval [0, 1] can be replaced by another compact interval, such as [a`, b`], but this difference can be absorbed by changing a scaling factor. The assumption ‖h`,k‖
Bβ (`)
p,q ≤ 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 on 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: fo(x) = g(w>x) where g ∈ Cβ([0, 1]) and w ∈ Rd. In 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 x is distributed on a low-dimensional smooth manifold embedded in Ω, and the smoothness of the true function fo is anisotropic along a coordinate direction on the manifold. We suppose that the low dimensional manifold is d̃-dimensional and d̃ d. In this situation, the true function can be written as fo(x) = h(φ(x)) where φ : Rd → Rd̃ is a map that returns the coordinate of x on the manifold and h is an element in an anisotropic Besov space on Rd̃. This situation appears if data is distributed on a 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 is a function invariant with data augmentation (Simard et al., 2003; Krizhevsky et al., 2012). Even if the noise injection destroys low dimensionality of the data distribution (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 more related work and discuss their relation to our analysis. The statistical analysis on an anisotropic Besov space can be back to Ibragimov & Khas’minskii (1984) who considered density estimation, where the density is assumed to be included in an anisotropic Sobolev space with p ≥ 2, and derived the minimax optimal rate n−rβ̃/(2β̃+1) with respect to Lr-norm. Nyssbaum (1983, 1987) analyzed a nonparametric regression problem on an anisotropic Besov space. Following these results, several studied have been conducted in the literature pertaining to nonparametric statistics, such as nonlinear kernel estimator Kerkyacharian et al. (2001), adaptive confidence band construction Hoffman & Lepski (2002), optimal aggregation Gaiffas & 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) considered a dimension reduction model; that is, the target function is dependent on only a 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 (2016); Bickel & Li
(2007); Yang & Tokdar (2015). Such a model can be considered as a specific example of the deep composition model. In this sense, our analysis is a significant extension of these analyses.

heading: 3 Approximation error analysis
text: Here, we consider approximating the true function fo via a deep neural network and derive the approximation error. As the activation function, we consider the ReLU activation denoted by η(x) = max{x, 0} (x ∈ R). For a vector x, η(x) is operated in an element-wise manner. The model of neural networks with height L, width W , sparsity constraint S, and norm constraint B as Φ(L,W,S,B) := {(W(L)η(·) + b(L)) ◦ · · · ◦ (W(1)x+ b(1)) | W(L) ∈ R1×W , b(L) ∈ R, W(1) ∈ RW×d, b(1) ∈ RW ,W(`) ∈ RW×W , b(`) ∈ RW (1 < ` < L), ∑L `=1(‖W(`)‖0 + ‖b(`)‖0) ≤ S,max` ‖W(`)‖∞ ∨ ‖b(`)‖∞ ≤ B}, where ‖ · ‖0 is the `0-norm of the matrix (the number of nonzero elements of the matrix), and ‖ · ‖∞ is the `∞-norm of the matrix (maximum of the absolute values of the elements). The sparsity constraint and norm bounds are required to obtain the nearoptimal 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
Rr(F ,H) := supf∗∈H inff∈F ‖f∗ − f‖Lr(Ω), where F is the set of functions used for approximation, andH is the set of target functions. Proposition 2 (Approximation ability for anisotropic Besov space). Suppose that 0 < p, q, r ≤ ∞ and β ∈ Rd++ satisfy the following condition: β̃ > (1/p − 1/r)+. Assume that m ∈ N satisfies 0 < β < min(m,m − 1 + 1/p). Let δ = (1/p − 1/r)+, ν = (β̃ − δ)/(2δ) and W0(d) := 6dm(m+ 2) + 2d. Then, for N ∈ N, we can bound the approximation error as
Rr(Φ(L1,W1, S1, B1), U(B β p,q(Ω))) . N −β̃ ,
by setting
L1(d) := 3 + 2dlog2 ( 3d∨m
c(d,m)
) + 5edlog2(d ∨m)e, W1(d) := NW0, (2)
S1(d) := [(L− 1)W 20 + 1]N, B1(d) := O(Nd(1+ν −1)(1/p−β̃)+), (3)
for = N−β̃ log(N)−1 and a constant c(d,m) depending only on d 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 between adaptive and non-adaptive methods is 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 we can avoid the curse of dimensionality if the average smoothness β̃ is small. This means that if 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 an isotropic Besov space where β1 = · · · = βd(= β), then β̃ = β/d, which directly depends on the dimensionality d, and we need an exponentially large number of parameters in this situation to achieve -accuracy. Therefore, the anisotropic smoothness has a significant impact on the approximation error rate. The assumption β̃ > (1/p − 1/r)+ ensures the Lr-integrability of the target function, and the inequality (without equality) admits a near-optimal wavelet approximation of the target function in terms of Lr-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 it to Appendix A.
Theorem 1 (Deep composition model). Assume that β̃(`) > 1/p for all ` = 1, . . . ,H . Then, the estimation error on the deep composition model is bounded as
R∞(Φ(L,W,S,B),Hdeep) . max `∈[H]
N−β̃ ∗(`) , (4)
where β̃∗(`) = β̃(`) ∏H k=`+1[(β (k)−1/p)∧1], and L = ∑H `=1(L1(m`)+1),W = max`(W1(m`)∨
m`+1), S = ∑H `=1(S1(m`) + 3m`+1), B = max`B1(m`).
The proof can be found in Appendix B.1. Since the model is more general than the vanilla anisotropic Besov space, we require a stronger assumption β̃(`) > 1/p on β̃(`) than the condition in Proposition 2. This is because we need to bound the Hölder smoothness of the remaining layers to bound the influence of the approximation error in the internal layers to the entire function. Hölder smoothness is ensured according to the embedding property under this condition (Proposition 1). This Hölder smoothness assumption affects the approximation error rate. The convergence rate β̃∗(`) in Eq. (4) is different from that in Eq. (8). This is because the approximation error in the internal layers are propagated through the remaining layers with Hölder smoothness and its amplitude is controlled by the Hö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 a 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−(β̃−( 1 p− 1 min{2,r} )+) (Myronyuk, 2015, 2016, 2017), which is slower than the approximation error rate of deep neural networks especially for small p.

heading: 4 Estimation error analysis
text: In this section, we analyze the accuracy of deep learning in estimating a function in compositions of anisotropic Besov spaces. We consider a least-squares estimator in the deep neural network model:
f̂ = argminf̄ :f∈Φ(L,W,S,B) ∑n i=1(yi − f̄(xi))2 (5)
where f̄ is the clipping of f defined by f̄ = min{max{f,−F}, F} for a constant F > 0 which is realized by ReLU units. The network parameters (L,W, S,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 log(n)-factor in the estimation error bound. This estimator can be seen as a sparsely regularized estimator because there are constraints on S. In terms of optimization, this requires a 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 The following theorem provides an upper bound of the estimation error for the affine composition model. Theorem 2. Assume the same condition as in Theorem 6; in particular, suppose 0 < p, q ≤ ∞ and β̃ > (1/p − 1/2)+ for β̃ ∈ Rd̃++. Moreover, we assume that the distribution PX has a density pX such that ‖pX‖∞ ≤ R for a constant R > 0. If fo ∈ Haff ∩ L∞(Ω), and ‖fo‖∞ ≤ F for F ≥ 1; then, letting (W,L, S,B) = (L1(d̃),W1(d̃), S1(d̃), (d̃C + 1)B1(d̃)) as in Theorem 6 with N n 1 2β̃+1 , we obtain
EDn [‖fo − f̂‖2L2(PX)] . n − 2β̃ 2β̃+1 log(n)3,
where EDn [·] 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−2β̃/(2β̃+1) is minimax optimal in Section 5 (see also Kerkyacharian & Picard (1992); Donoho et al. (1996); Donoho & Johnstone (1998); Giné & Nickl (2015) for ordinary Besov spaces). The L∞-norm constraint ‖fo‖∞ ≤ F is used to derive a uniform bound on the discrepancy between the population and the empirical L2-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 a stronger assumption on the smoothness.
Theorem 3. Suppose that 0 < p, q ≤ ∞ and β̃(`) > 1/p for all ` ∈ [H]. If fo ∈ Hdeep ∩ L∞(Ω), and ‖f‖∞ ≤ F for F ≥ 1, then we obtain
EDn [‖fo − f̂‖2L2(PX)] . max`∈[H] n −2β̃∗(`)/(2β̃∗(`)+1) log(n)3,
where β̃∗(`) is defined in Theorem 1, and (L,W, S,B) is as given in Theorem 1 with N max`∈[L] n 1 2β̃∗(`)+1 .
The proof is provided in Appendix C. We will show that this is also minimax optimal in Theorem 4. Because of the Hölder continuity, the convergence rate becomes slower than the affine composition model (that is, β̃∗(`) ≤ β̃(`)). However, this slower rate is unavoidable in terms of the minimax optimal rate. Schmidt-Hieber (2020) analyzed the same situation for the Hölder class which corresponds to β(`)1 = · · · = β (`) d (∀`) and p = q = ∞. Our analysis far extends their analysis to the setting of anisotropic Besov spaces in which the parameters β(`), p, q have much more freedom.
From these two bounds (Theorems 2 and 3), we can see that as the smoothness β̃ becomes large, the convergence rates faster. If the target function is included in the isotropic Besov space with smoothness β1 = · · · = βd(= β), then the estimation error becomes
(Isotropic Besov) n−2β/(2β+d).
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 β̃ does not depend on d, our obtained rate
(Anisotropic Besov) n−2β̃/(2β̃+1)
avoids the curse of dimensionality. For high-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 a 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.

heading: 5 Minimax optimal rate
text: 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 F◦ of the true function is the smallest worst case error over all estimators:
R∗(F◦) := inf f̂ supfo∈F◦ EDn [‖f̂ − f o‖2L2(PX)],
where f̂ runs over all estimators. The convergence rate of the minimax optimal risk is 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 < p, q ≤ ∞ and β ∈ Rd++, assume that β̃ > max {1/p− 1/2, 1/p− 1, 0} . Then, the minimax optimal risk of the affine composition model
is lower bounded as R∗(Haff) & n − 2β̃
2β̃+1 . (b) Deep composition model: For 0 < p, q ≤ ∞ and β(`) ∈ Rd++ (` = 1, . . . ,H), assume that β̃(`) > 1/p. Let > 0 be arbitrarily small for q <∞, and let = 0 for q = 0. Let β̃∗(`) = β̃(`) ∏H k=`+1[(β (k)−1/p+ )∧1], and β̃∗∗ := min` β̃∗(`). Then, the minimax optimal risk of the deep composition model is lower bounded as R∗(Hdeep) & n − 2β̃ ∗∗ 2β̃∗∗+1 .
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 Theorems 2 and 3 indeed achieve the minimax optimal rate up to a poly-log(n) factor.

heading: 6 Suboptimality of linear estimators
text: In this section, we give the minimax optimal rate in the class of linear estimators. The linear estimator is a class of estimators that can be written as
f̂(x) = ∑n i=1 yiϕi(x;X n),
where Xn = (x1, . . . , xn) and ϕi(x;Xn) (i = 1, . . . , n) are (measurable) functions that only depend on x and Xn. This is linearly dependent on Y n = (y1, . . . , yn). We notice that the kernel
ridge regression is included in this class because it can be written as f̂(x) = kx,Xn(kXn,Xn + λI)−1Y n, which linearly depends on Y n. This class includes other important estimators, such as the Nadaraya–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:
R (lin) ∗ (F◦) := inf
f̂ : linear sup fo∈F◦
EDn [‖fo − f̂‖2L2(PX)],
where f̂ 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 of dimensionality.
Theorem 5. (i) Suppose that the input distribution PX is the uniform distribution on Ω = [0, 1]d and assume that β̃ > 1/p and 1 ≤ p, q ≤ ∞. Then, the minimax optimal rate of the linear estimators is lower bounded as
R (lin) ∗ (U(B β p,q)) & n
− 2β̃−v 2β̃+1−v , (6)
where v = 2(1/p− 1/2)+. (ii) In addition to the above conditions, we assume that the true function is included in the affine composition model with d̃ ≤ d, β = β1 = · · · = βd̃ and 0 < p ≤ 2. Let ad = 1 + κ with arbitrary small κ > 0 when d̃ < d/2, and let ad = 0 when d̃ ≥ d/2. Then, the minimax rate of the linear estimators on the affine composition model is lower bounded by
R (lin) ∗ (Haff) & n − 2(β−d̃/p+d/2+ad) 2(β−d̃/p+d/2+ad)+d . (7)
The proof is provided in Appendix F. (i) The lower bound (7) reveals the suboptimality of linear estimators in terms of input dimensionality. Actually, if we consider a particular case where d̃ = 1, p = 1 and d d̃, then the obtained minimax rate of linear estimators and the estimation error rate of deep learning can be summarized as
linear : n− 2β+d 2β+2d , deep : n− 2β 2β+1 ,
by Theorem 2 when β > 1 (which can be checked by noticing d̃ = β/β̃ = 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 to the intrinsic dimensionality of data. Actually, as d becomes large, the rate for the linear estimator approaches to 1/ √ n but that for the deep learning is not affected by d and still faster than 1/ √ n. To show the theorem, we used the “convex-hull 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 is 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 is outperformed by that of deep learning (Theorem 2). This is due to the “adaptivity” of deep leaning. When p is small, the smoothness of the target function is less homogeneous, and it requires an adaptive approximation scheme to achieve the best estimation error. Linear estimators do not have adaptivity and thus fail to achieve the minimax optimal rate. Our bound (6) extends the result by Zhang et al. (2002) to a multivariate anisotropic Besov space while Zhang et al. (2002) investigated the univariate space (d = 1).

heading: 7 Conclusion
text: We investigated the approximation error and estimation error of deep learning in the anisotropic Besov spaces. It was proved that the convergence rate is determined by the average of the anisotropic smoothness, which results in milder dependence on the input dimensionality. If the smoothness is
highly anisotropic, 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 a theoretical perspective.
Limitations of this work Our work does not cover the optimization aspect of deep learning. It 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 a direct negative societal impact. However, revealing detailed properties of the deep learning could promote an opportunity to pervert deep learning.

heading: Acknowledgment
text: 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.

Review summaries:
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.

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.

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.  Some 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.  The paper is well organized and relatively easy to follow.