Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks

Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 02:58:45

Abstract: Convolutional residual neural networks (ConvResNets), though overparametersized, can achieve remarkable prediction performance in practice, which cannot be well explained by conventional wisdom. To bridge this gap, we study the performance of ConvResNeXts trained with weight decay, which cover ConvResNets as a special case, from the perspective of nonparametric classification. Our analysis allows for infinitely many building blocks in ConvResNeXts, and shows that weight decay implicitly enforces sparsity on these blocks. Specifically, we consider a smooth target function supported on a low-dimensional manifold, then prove that ConvResNeXts can adapt to the function smoothness and low-dimensional structures and efficiently learn the function without suffering from the curse of dimensionality. Our findings partially justify the advantage of overparameterized ConvResNeXts over conventional machine learning models.

Main paper: 
 introduction: 
 Deep learning has achieved significant success in various real-world applications, such as computer vision (Goodfellow et al., 2014; Krizhevsky et al., 2012; Long et al., 2015) , natural language processing (Bahdanau et al., 2014; Graves et al., 2013; Young et al., 2018) , and robotics (Gu et al., 2017) . One notable example of this is in the field of image classification, where the winner of the 2017 ImageNet challenge achieved a top-5 error rate of just 2.25% (Hu et al., 2018) using ConvResNets on a training dataset of 1 million labeled high-resolution images in 1000 categories.Among various deep learning models, ConvResNets have gained widespread popularity in practical applications (Chen et al., 2017; He et al., 2016; Szegedy et al., 2017; Zhang et al., 2017) . Compared to vanilla feedforward neural networks (FNNs), ConvResNets possess two distinct features: convolutional layers and skip connections. Specifically, each block of ConvResNets consists of a subnetwork, called bottleneck, and an identity connection between inconsecutive blocks. The identity connection effectively mitigates the vanishing gradient issue. Each layer of the bottleneck contains several filters (channels) that convolve with the input. Using this ConvResNet architecture, He et al. (2016) won 1st place on the ImageNet classification task with a 3.57% top-5 error in 2015. ConvResNets have various extensions, one of which is ConvResNeXts (Xie et al., 2017) (detailed introductions of ConvResNeXts is deferred to Section 2.3). This structure generalizes ConvResNets and includes them as a special case. Each building block in ConvResNeXts has a parallel architecture that enables multiple "paths" within the block. Figure 1 (b) illustrates the structure of ConvResNeXts.There are few theoretical works about ConvResNet, despite its remarkable empirical success. Previous research has focused on the representation power of FNNs (Barron, 1993; Cybenko, 1989; Kohler & Krzyżak, 2005; Suzuki, 2018; Yarotsky, 2017) , while limited literature exists on ConvResNets. Oono & Suzuki (2019) developed a representation and statistical estimation theory of ConvResNets, and showed that if the network architecture is appropriately designed, ConvResNets with O(n D/(2α+D) ) blocks can achieve a minimax optimal convergence rate Õ(n -2α/(2α+D) ) when approximating a C α function with n samples. Additionally, Liu et al. (2021) proved that ConvResNets can universally approximate any function in the Besov space B α p,q on d-dimensional manifolds with arbitrary accuracy. Here, the Besov space includes functions with spatially heterogeneous smoothness and generalizes more elementary function spaces such as Sobolev and Hölder spaces. Liu et al. (2021) improved the convergence rate to Õ(n -2α/(2α+d) ) for ConvResNets with O(n d/(2α+d) ) blocks. Their results only depend on the intrinsic dimension d, rather than the data dimension D.These previous works, however, could not explain the success of ConvResNets in an overparameterized regime, where the number of blocks can be much larger than the sample size. In practice, the performance of ConvResNets becomes better when they go deeper (He et al., 2016; Wang et al., 2022) and wider (Xie et al., 2017) , but the previous results required the number of blocks to be chosen carefully according to unknown quantities of interest such as intrinsic dimension d, smoothness parameter α and radii of the Besov ball and so on. For instance, Liu et al. (2021) requires the number of blocks for ConvResNets to be O(n d/(2α+d) ), which is smaller than the order of the sample size n. Overparameterized CovResNets with larger number of blocks, if we believe in the existing theory, would result in suboptimal rate and worst results -despite it is the opposite in practice.To bridge this gap, we study ConvResNeXts trained with weight decay under an overparameterization regime (Xie et al., 2017) . The ConvResNeXt is a generalization of the ConvResNet and can cover ConvResNets as a special case. Specifically, we study the same nonparametric classification problem as Liu et al. (2021) , where the target function is supported on a d-dimensional smooth manifold M. We prove that even if ConvResNeXts are overparameterized, i.e., the number of blocks is larger than the order of the sample size n, they can still achieve an asymptotic minimax rate for learning Besov functions. That is, given that the target function belongs to the Besov space B α p,q (M), the risk of the estimator given by the ConvResNeXt class converges to the optimal risk at the rate Õ(n -α/d 2α/d+1 (1-o(1)) ) with n samples. We remark that weight decay, which play an important role in our analysis, is a common method in deep learning to reduce overfitting (Krogh & Hertz, 1991; Smith, 2018) . With this approach, ConvResNeXts can have infinitely many blocks to achieve arbitrary accuracy, which corresponds to the real-world applications (He et al., 2016; Wang et al., 2022) . Moreover, our theory shows that one can scale the number of "paths" M in each block with the depth N as roughly M N ≳ n 1 2α/d+1 , which does not affect the convergence rate. This partially justifies the flexibility of the ConvResNeXt architecture when designing the bottlenecks.Our work is partially motivated by Zhang & Wang (2022) . However, our work distinguishes itself through two new technical advancements. Firstly, we develop approximation theory for ConvResNeXts, while Zhang & Wang (2022) only focuses on (a parallel variant of) FNNs. Secondly, we take into account low-dimensional geometric structures of data. Notably, the statistical rate of convergence in our theory only depends on the intrinsic dimension d, which circumvents the curse of dimensionality in Zhang & Wang (2022) .Another technical highlight of our paper is bounding the covering number of weight-decayed ConvResNeXts, which is essential for computing the critical radius of the local Gaussian complexity. This technique provides a tighter bound than choosing a single radius of the covering number as in Suzuki (2018) ; Zhang & Wang (2022) . To the best of our knowledge, our work is the first to develop approximation theory and statistical estimation results for ConvResNeXts, as well as overparameterized ConvResNets. 
preliminaries: 
 In this section, we introduce some concepts on manifolds. Details can be found in (Tu, 2011) and (Lee, 2006) . Then we provide a detailed definition of the Besov space on smooth manifolds and the ConvResNeXt architecture.Firstly, we briefly introduce manifolds, the partition of unity and reach. Let M be a d-dimensional Riemannian manifold isometrically embedded in R D with d much smaller than D.Definition 1 (Chart). A chart on M is a pair (U, ϕ) such that U ⊂ M is open and ϕ : U → R d ,where ϕ is a homeomorphism (i.e., bijective, ϕ and ϕ -1 are both continuous).In a chart (U, ϕ), U is called a coordinate neighborhood, and ϕ is a coordinate system on U . Essentially, a chart is a local coordinate system on M. A collection of charts that covers M is called an atlas of M. Definition 2 (C k Atlas). A C k atlas for M is a collection of charts {(U i , ϕ i )} i∈A which satisfies i∈A U i = M, and are pairwise C k compatible:ϕ i • ϕ -1 β : ϕ β (U i ∩ U β ) → ϕ i (U i ∩ U β ) and ϕ β • ϕ -1 i : ϕ i (U i ∩ U β ) → ϕ β (U i ∩ U β ) are both C k for any i, β ∈ A.An atlas is called finite if it contains finitely many charts.Definition 3 (Smooth Manifold). A smooth manifold is a manifold M together with a C ∞ atlas.Classical examples of smooth manifolds are the Euclidean space, the torus, and the unit sphere. Furthermore, we define C s functions on a smooth manifold M as follows:Definition 4 (C s functions on M). Let M be a smooth manifold and f : M → R be a function onM. A function f : M → R is C s if for any chart (U, ϕ) on M, the composition f • ϕ -1 : ϕ(U ) → R is a continuously differentiable up to order s.We next define the C ∞ partition of unity, which is an important tool for studying functions on manifolds.Definition 5 (Partition of Unity, Definition 13.4 in Tu ( 2011)). A C ∞ partition of unity on a manifold M is a collection of C ∞ functions {ρ i } i∈A with ρ i : M → [0, 1] such that for any x ∈ M,1. there is a neighbourhood of x where only a finite number of the functions in {ρ i } i∈A are nonzero;2.i∈A ρ i (x) = 1.An open cover of a manifold M is called locally finite if every x ∈ M has a neighborhood that intersects with a finite number of sets in the cover. The following proposition shows that a C ∞ partition of unity for a smooth manifold always exists.Proposition 1 (Existence of a C ∞ partition of unity, Theorem 13.7 in Tu ( 2011)). Let {U i } i∈A be a locally finite cover of a smooth manifold M. Then there is a C ∞ partition of unity {ρ i } ∞ i=1 where every ρ i has a compact support such that supp(ρ i ) ⊂ U i .Let {(U i , ϕ i )} i∈A be a C ∞ atlas of M. Proposition 1 guarantees the existence of a partition of unity {ρ i } i∈A such that ρ i is supported on U i . To characterize the curvature of a manifold, we adopt the geometric concept: reach.Definition 6 (Reach (Federer, 1959; Niyogi et al., 2008) ). DenoteG = x ∈ R D : ∃ p ̸ = q ∈ M such that ∥x -p∥ 2 = ∥x -q∥ 2 = inf y∈M ∥x -y∥ 2 .as the set of points with at least two nearest neighbors on M. The closure of G is called the medial axis of M. Then the reach of M is defined asτ = inf x∈M inf y∈G ∥x -y∥ 2 .Reach has a simple geometrical interpretation: for every point x ∈ M, the osculating circle's radius is at least τ . A large reach for M indicates that the manifold changes slowly.We next define the Besov function space on the smooth manifold M, which generalizes more elementary function spaces such as the Sobolev and Hölder spaces. Roughly speaking, functions in the Besov space are only required to have weak derivatives with bounded total variation. Notably, this includes functions with spatially heterogeneous smoothness, which requires more locally adaptive methods to achieve optimal estimation errors Donoho et al. (1998) . Please see Appendix A for examples and how kernel ridge regressions, including the Neural Tangent Kernels, cannot be optimal on Besov functions. To define Besov functions rigorously, we first introduce the modulus of smoothness.Definition 7 (Modulus of Smoothness (DeVore & Lorentz, 1993; Suzuki, 2018) ). Let Ω ⊂ R D . For a function f : R D → R be in L p (Ω) for p > 0, the r-th modulus of smoothness of f is defined byw r,p (f, t) = sup ∥h∥2≤t ∥∆ r h (f )∥ L p , where ∆ r h (f )(x) = r j=0 r j (-1) r-j f (x + jh) if x ∈ Ω, x + rh ∈ Ω, 0 otherwise.Definition 8 (Besov Space B α p,q (Ω)). For 0 < p, q ≤ ∞, α > 0, r = ⌊α⌋ + 1, define the seminorm| • | B α p,q as |f | B α p,q (Ω) :=      ∞ 0 (t -α w r,p (f, t)) q dt t 1 q if q < ∞, sup t>0 t -α w r,p (f, t) if q = ∞.The norm of the Besov space B s p,q (Ω) is defined as ∥f ∥ B α p,q (Ω) := ∥f ∥ L p (Ω) + |f | B α p,q (Ω) . Then the Besov space is defined as B α p,q (Ω) = {f ∈ L p (Ω)|∥f ∥ B α p,q < ∞}.Moreover, we show that functions in the Besov space can be decomposed using B-spline basis functions in the following proposition.Proposition 2 (Decomposition of Besov functions). Any function f in the Besov space B α p,q , α > d/p can be decomposed using B-spline of order m, m > α: for any x ∈ R d , we haveEQUATIONwhereJ(k) := {2 -k s : s ∈ [-m, 2 k + m] d ⊂ Z d }, M m,k,s (x) := M m (2 k (x -s)), and M k (x) = d i=1 M k (x i )is the cardinal B-spline basis function which can be expressed as a polynomial:EQUATIONWe next define B α p,q functions on M. Definition 9 (B α p,q Functions on M (Geller & Pesenson, 2011; Tribel, 1992) ). Let M be a compact smooth manifold of dimension d. Let {(U i , ϕ i )} C M i=1 be a finite atlas on M and {ρ i } C M i=1 be a partition of unity on M such that supp(ρ i )⊂ U i . A function f : M → R is in B α p,q (M) if ∥f ∥ B α p,q (M) := C M i=1 ∥(f ρ i ) • ϕ -1 i ∥ B α p,q (R d ) < ∞. (3) Since ρ i is supported on U i , the function (f ρ i )•ϕ -1 i is supported on ϕ(U i ). We can extend (f ρ i )•ϕ -1 i from ϕ(U i ) to R d by setting the function to be 0 on R d \ ϕ(U i ).The extended function lies in the Besov space B s p,q (R d ) (Tribel, 1992, Chapter 7 ).We introduce the architecture of ConvResNeXts. ConvResNeXts have three main features: convolution kernel, residual connections, and parallel architecture.Consider one-sided stride-one convolution in our network. Let W = {W j,k,l } ∈ R w ′ ×K×w be a convolution kernel with output channel size w ′ , kernel size K and input channel size w. For z ∈ R D×w , the convolution of W with z gives y ∈ R D×w ′ such thatEQUATIONwhere 1 ≤ i ≤ D, 1 ≤ j ≤ w ′ and we set z i+k-1,l = 0 for i + k -1 > D, as demonstrated in Figure 1 (a).The building blocks of ConvResNeXts are residual blocks. Given an input x, each residual block computes x + F (x), where F is a subnetwork called bottleneck, consisting of convolutional layers.In ConvResNeXts, a parallel architecture is introduced to each building block, which enables multiple "paths" in each block. In this paper, we study the ConvResNeXts with rectified linear unit (ReLU) activation function, i.e., ReLU(z) = max{z, 0}. We next provide the detailed definition of ConvResNeXts as follows: Definition 10. Let the neural network comprise N residual blocks, each residual block has a parallel architecture with M building blocks, and each building block contains L layers. The number of channels is w, and the convolution kernel size is K. Given an input x ∈ R D , a ConvResNeXt with ReLU activation function can be represented asf (x) = W out • M m=1 f N,m + id • • • • • M m=1 f 1,m + id • P (x), f n,m = W (n,m) L ⋆ ReLU W (n,m) L-1 ⋆ • • • ⋆ ReLU W (n,m) 1 ⋆ x ,where id is the identity operator, P : R D → R D×w0 is the padding operator satisfyingP (x) = [x, 0 . . . 0] ∈ R D×w , {W (n,m) l } Ll=1 is a collection of convolution kernels for n = 1, . . . , N, m = 1, . . . , M , W out ∈ R w L denotes the linear operator for the last layer, and ⋆ is the convolution operation defined in (4).The structure of ConvResNeXts is shown in Figure 1(b) . When M = 1, the ConvResNeXt defined in Definition 10 reduces to a ConvResNet. For notational simplicity, we omit biases in the neural network structure by extending the input dimension and padding the input with a scalar 1 (See Proposition 18 for more details). The channel with 0's is used to accumulate the output. 
theory: 
 In this section, we study a binary classification problem on M ⊆ [-1, 1] D . Specifically, we are given i.i.d. samples {x i , y i } n i=1 ∼ D where x i ∈ M and y i ∈ {0, 1} is the label. The label y follows the Bernoulli-type distributionP(y = 1|x) = exp(f * (x)) 1 + exp(f * (x))andP(y = 0|x) = 1 1 + exp(f * (x))for some f * : M → R belonging to the Besov space. More specifically, we make the following assumption on f * .Assumption 1. Let 0 < p, q ≤ ∞, d/p < α < ∞. Assume f * ∈ B α p,q (M) and ∥f * ∥ B α p,q (M) ≤ C F for some constant C F > 0.To learn f * , we minimize the empirical logistic risk over the training data:EQUATIONwhere F Conv is some neural network class specified later. For notational simplicity, we denote the empirical logistic risk function in (5) as L n (f ), and denote the population logistic risk asE D [L(f )] = E (x,y)∼D y log(1 + exp(-f (x))) + (1 -y) log(1 + exp(f (x))).We next specify the class of ConvResNeXts for learning f * : 10) with N residual blocks. Every residual block has M building blocks with each building block containing L layers. Each layer has kernel size bounded by K, number of channels bounded by w,F Conv (N, M, L, K, w, B res , B out ) = f | f is in the form of (N n=1 M m=1 L ℓ=1 ∥W (n,m) ℓ ∥ 2 F ≤ B res , ∥W out ∥ 2 F ≤ B out , f (x) ∈ [0, 1] for any x ∈ M. .Note that the hyperparameters of F Conv will be specified in our theoretical analysis later.As can be seen, F Conv contains the Frobenius norm constraints of the weights. For the sake of computational convenience in practice, such constraints can be replaced with weight decay regularization the residual blocks and the last fully connected layer separately. More specifically, we can use the following alternative formulation:f = arg min f ∈F Conv (N,M,L,K,w,∞,∞) L n (f ) + λ 1 N n=1 M m=1 L ℓ=1 ∥W (n,m) ℓ ∥ 2 F + λ 2 ∥W out ∥ 2 F ,where λ 1 , λ 2 > 0 are properly chosen regularization parameters.In this section, we provide a universal approximation theory of ConvResNeXts for Besov functions on a smooth manifold: Theorem 3. For any Besov function f 0 on a smooth manifold satisfyingEQUATIONEQUATIONEQUATIONwhere C 1 , C 2 , C 3 are universal constants and C 4 , C 5 , C 6 are constants that only depends on d and m, d is the intrinsic dimension of the manifold and m is an integer satisfying 0 < α < min(m, m -1 + 1/p).The approximation error of the network is bounded by the sum of two terms. The first term is a polynomial decay term that decreases with the size of the neural network and represents the trailing term of the B-spline approximation. The second term reflects the approximation error of neural networks to piecewise polynomials, decreasing exponentially with the number of layers. The proof is deferred to Section 4.1 and the appendix.Theorem 4. Suppose Assumption 1 holds. SetEQUATIONM N ≥ C M P, P = O(n 1-2/L 2α/d(1-1/L)+1-2/pL ), w ≥ C 1 (dm + D).Let f be the global minimizer given in (5) with the function class F = F Conv (N, M, L, K, w, B res , B out ). Then we haveE D [L( f (x), y)] ≤ E D [L(f * (x), y)] + C 7 K -2 L-2 w 3L-4 L-2 L 3L-2 L-2 n α/d(1-2/L) 2α/d(1-1/L)+1-2/(pL) + C 8 exp(-C 6 L ′ ),where the logarithmic terms are omitted. C 1 is the constant defined in Theorem 3, C 7 , C 8 are constants that depend on C F , C M , d, m, K is the size of the convolution kernel.We would like to make the following remarks about the results:• Strong adaptivity: By setting the width of the neural network to w = 2C 1 D, the model can adapt to any Besov functions on any smooth manifold, provided that dm ≤ D. This remarkable flexibility can be achieved simply by tuning the regularization parameter. The cost of overestimating the width is a slight increase in the estimation error. Considering the immense advantages of this more adaptive approach, this mild price is well worth paying.• No curse of dimensionality: the above error rate only depends polynomially on the ambient dimension D and exponentially on the hidden dimension d. Since in real data, the hidden dimension d can be much smaller than the ambient dimension D, this result shows that neural networks can explore the low-dimension structure of data to overcome the curse of dimensionality.• Overparameterization is fine: the number of building blocks in a ConvResNeXt does not influence the estimation error as long as it is large enough. In other words, this matches the empirical observations that neural networks generalize well despite overparameterization.• Close to minimax rate: The lower bound of the 1-Lipschitz error for any estimator θ ismin θ max f * ∈B α p,q L(θ(D), f * ) ≳ n -α/d 2α/d+1 .where ≳ notation hides a factor of constant. The proof can be found in Appendix E. Comparing to the minimax rate, we can see that as L → ∞, the above error rate converges to the minimax rate up to a constant term. In other words, overparameterized ConvResNeXt can achieve close to the minimax rate in estimating functions in Besov class. In comparison, all kernel ridge regression including any NTKs will have a suboptimal rate lower bounded by 2α-d 2α , which is suboptimal. • Deeper is better: with larger L, the error rate decays faster with n and get closer to the minimax rate. This indicates that deeper model can achieve better performance than shallower models when the training set is large enough.• Tradeoff between width and depth: With a fixed budget in the number of parameters, the tradeoff between width and depth is crucial for achieving the best performance, and this often requires repeated, time-consuming experiments. On the other hand, our results suggests that such a tradeoff less important in a ResNeXt. The lower bound of error does not depend on the arrangements of the residual blocks M and N , as long as their product is large enough. This can partly explain the benefit of ResNeXt over other architecture.By choosing L = O(log(n)), the second term in the error can be merged with the first term, and close to the minimax rate can be achieved: Corollary 5. Given the conditions in Theorem 4, set the depth of each block is L = O(log(n)) and then the estimation error of the empirical risk minimizer f satisfiesE D [L( f (x), y)] ≤ E D [L(f * )] + Õ(n -α/d 2α/d+1 (1-o(1)) ),where Õ(•) omits the logarithmic term.  
approximation error: 
 We follow the method in Liu et al. (2021) to construct a neural network that achieves the approximation error we claim. It is divided into the following steps:• Step 1: Decompose the target function into the sum of locally supported functions.In this work, we adopt a similar approach to (Liu et al., 2021) and partition M using a finite number of open balls on R D . Specifically, we define B(c i , r) as the set of unit balls with center c i and radius r such that their union covers the manifold of interest, i.e., M ⊆ ∪ C M i=1 B(c i , r). This allows us to partition the manifold into subregions U i = B(c i , r) ∩ M, and further decompose a smooth function on the manifold into the sum of locally supported smooth functions with linear projections. The existence of function decomposition is guaranteed by the existence of partition of unity stated in Proposition 1. See Section C.1 for the detail.•Step 2: Locally approximate the decomposed functions using cardinal B-spline basis functions.In the second step, we decompose the locally supported Besov functions achieved in the first step using B-spline basis functions. The existence of the decomposition was proven by Dũng (2011) , and was applied in a series of works (Zhang & Wang, 2022; Suzuki, 2018; Liu et al., 2021) . The difference between our result and previous work is that we define a norm on the coefficients and bound this norm, instead of bounding the maximum value. The detail is deferred to Section C.2. EQUATIONWe first demonstrate that a ReLU neural network taking two scalars a, b as the input, denoted as a ×b, can approximate y × 1(x ∈ B r,i ), where × satisfy that y ×1 = y for all y, and y ×x = 0 if any of x or y is 0, and the soft indicator function 1(x ∈ B r,i ) satisfy 1(x ∈ B r,i ) = 1 when x ∈ B r,i , and 1(x ∈ B r,i ) = 0 when x / ∈ B r+∆,i . The detail is deferred to Section C.3.Then, we show that it is possible to construct M N = C M P number of building blocks, such that each building block is a feedforward neural network with width C 1 (md + D) and depth L, where m is an integer satisfying 0 < α < min(m, m -1 + 1/p). The k-th building block (the position of the block does not matter) approximatesa i,kj ,sj M m,kj ,sj • ϕ i × 1(x ∈ B(c i , r)), where i = ceiling(k/N ), j = rem(k, N ). Each building block has where a sub-block with width D and depth L -1 approximates the chart selection, a sub-block with width md and depth L -1 approximates the B-spline function, and the last layer approximates the multiply function. The norm of this block is bounded byEQUATION)Making use of the 1-homogeneous property of the ReLU function, by scaling all the weights in the neural network, these building blocks can be combined into a neural network with residual connections, that approximate the target function and satisfy our constraint on the norm of weights. See Section C.4 for the detail.By applying Lemma 12, which shows that any L-layer feedforward neural network can be reformulated as an L + L 0 -1-layer convolution neural network, the neural network constructed above can be converted into a ConvResNeXt that satisfies the conditions in Theorem 3.We first prove the covering number of an overparameterized ConvResNeXt with norm-constraint as in Lemma 6, then compute the critical radius of this function class using the covering number as in Corollary 19. The critical radius can be used to bound the estimation error as in Theorem 14.20 in Wainwright (2019) . The proof is deferred to Section D.2.Lemma 6. Consider a neural network defined in Definition 10. Let the last layer of this neural network is a single linear layer with norm ∥W out ∥ 2 F ≤ B out . Let the input of this neural network satisfy ∥x∥ 2 ≤ 1, ∀x, and is concatenated with 1 before feeding into this neural network so that part of the weight plays the role of the bias. The covering number of this neural network is bounded byEQUATION) where the logarithmic term is omitted.The key idea of the proof is to split the building block into two types ("small blocks" and "large blocks") depending on whether the total norm of the weights in the building block is smaller than ϵ or not. By properly choosing ϵ, we prove that if all the "small blocks" in this neural network are removed, the perturbation to the output for any input ∥x∥ ≤ 1 is no more than δ/2, so the covering number of the ConvResNeXt is only determined by the number of "large blocks", which is no more than B res /ϵ.Proof. Using the inequality of arithmetic and geometric means, from Proposition 20, Proposition 22 and Proposition 23, if any residual block is removed, the perturbation to the output is no more than(KB m /L) L/2 B 1/2 out exp((KB res /L) L/2), where B m is the total norm of parameters in this block. Because of that, the residual blocks can be divided into two kinds depending on the norm of the weights B m < ϵ ("small blocks") and B m ≥ ϵ ("large blocks"). If all the "small blocks" are removed, the perturbation to the output for any input∥x∥ 2 ≤ 1 is no more than exp((KB res /L) L/2 )B 1/2 out m:Bm<ϵ (KB m /L) L/2 ≤ exp((KB res /L) L/2 )B 1/2 out m:Bm<ϵ (KB m /L)(Kϵ/L) L/2-1 ≤ exp((KB res /L) L/2 )K L/2 B res B 1/2 out (ϵ/L) L/2-1 /L. Choosing ϵ = L δL 2 exp((Bres/L) L/2 )K L/2 BresB 1/2 out 1 L/2-1, the perturbation above is no more than δ/2. The covering number can be determined by the number of the "large blocks" in the neural network, which is no more than B res /ϵ.As for any block, B in L post ≤ B 1/2 out exp((KB res /L) L/2 ), taking our chosen ϵ finishes the proof, where B in is the upper bound of the input to this block defined in Proposition 13, and L post is the Lipschitz constant of all the layers following the block.Remark 1. The proof of Lemma 6 shows that under weight decay, the building blocks in a Con-vResNeXt are sparse, i.e. only a finite number of blocks contribute non-trivially to the network even though the model can be overparameterized. This explains why a ConvResNeXt can generalize well despite overparameterization, and provide a new perspective in explaining why residual connections improve the performance of deep neural networks. 
discussions: 
 We compare the Besov space with the Hölder and Sobolev spaces, which are also popular in existing literature. The Hölder space H s,α requires the functions to be differentiable everywhere up to the s-th order. The Sobolev space slightly generalizes the Hölder space, but still requires high order (weak) differentiability. In contrast, the Besov space B s p,q does not require weak differentiability, and therefore is more general and desirable than the Hölder and Sobolev spaces. Existing work has shown that the Besov space can capture important features, such as edges in image processing (Jaffard et al., 2001) . In particular, the Hölder and Sobolev spaces are special cases of the Besov space:H s,α = W s+α,∞ ⊆ B s+α ∞,∞ ⊆ B s+α p,qfor any 0 < p, q ≤ ∞, s ∈ N and α ∈ (0, 1]. Due to the generality of the Besov space, existing literature has been shown that that kernel ridge estimators, including neural tangent kernel only attain a sub-optimal rate for learning Besov functions (Suzuki & Nitanda, 2021) A WHY BESOV CLASSES?In this section, we discuss why we choose to consider the Besov class of functions and why this makes our results particularly interesting.To see this, we need to first define two smaller function classes: the Holder class and the Sobolev class. Instead of giving fully general definitions for these function classes let us illustrate their main differences using univariate functions defined on [0, 1]. We also introduce the so-called Total Variation class -which is sandwiched in between Besov(p = 1, q = 1) and Besov(p = 1, q = ∞).• Holder class functions satisfy |f (α) (x)| < C for all x.• Sobolev class functions satisfy[0,1] |f (α) (x)| 2 dx < C • Total Variation class functions satisfy [0,1] |f (α) (x)|dx < CThe allows This means that f (α) (x) can be very large at some places, e.g., Dirac delta functions, while Holder and Sobolev class functions cannot contain such spikes (no longer integrable in Sobolev norm above).Generically speaking under the appropriate scaling: Holder ⊂ Sobolev ⊂ Besov. The Besov space contains functions with heterogeneous smoothness while Holder and Sobolev classes contain functions with homogeneous smoothness. Despite the Besov space being larger, it has the same minimax rate of n -(2α)/(2α+d) as the smaller Holder and Sobolev class.A new perspective on overparameterized NN. We study the adaptivity of deep networks in overparameterized regimes. The most popular method for understanding overparameterization is through the neural tangent kernel (NTK) regime. However, based on the classical linear smoother lower-bound for estimating functions in Besov classes with p = 1 Donoho et al. (1990; 1998) , all kernel ridge regression including any NTKs will have a suboptimal rate lower bounded by n -2α-d 2α . To say it differently, there is a formal separation between NTKs and the optimal method. The same separation does not exist in smaller function classes such as Sobolev and Holders because they are more homogeneously smooth.Examples of Besov class functions include piecewise linear functions and piecewise quadratic functions that are smoother in some regions and more wiggly in other regions; see e.g., Figure 2 and Figure 4 of Mammen & van de Geer (1997) .In summary, in order to study what neural networks can achieve that is not achievable by kernels, e.g., NTK; we had to define and approximate Besov class functions. Our results show that ConvResNeXT not only overcomes the curse of dimensionality of the ambient space, but also has nearly optimal dependence in the intrinsic dimension d -in contrast to the kernel-based approaches.We believe this offers a new perspective to understand overparameterization and is more fine-grained that of NTK.In this section, we validate our theoretical findings with numerical experiments. We focus on nonparametric regression problems for simplicity and consider the following function f 0 : R D → R:f 0 (x) = f0 (U x) = f0 (x)where U ∈ R D×D is a randomly-chosen rotation matrix and x = U x ∈ R D satisfies that for t ∈ [0, 1], the first three coordinatesx1 = t sin(4πt), x2 = t cos(4πt), x3 = t(1 -t),and the remaining coordinates of x are irrelevant features iid sampled from a uniform distribution. Note that the first three coordinates of x are completely determined by a scalar t, and the corresponding label y is determined by t via a piecewise linear function, i.e., for a bag of t 1 , ..., t n ∈ [0, 1], we can generate a labeled dataset by y i = g 0 (t i ) + N (0, 1). An illustration of the function f 0 is given in Figure 2 where colors indicate the value.Role of irrelevant features and rotation. The purpose of irrelevant features and rotation is to make the problem harder and more interesting.x i,1 = t i sin(4πt i ), x i,2 = t i cos(4πt i ), x i,3 = t i (1 -t i ),where t i , i = 1, . . . , n are evenly spaced over [0, 1] . This process generates a 1-dimensional manifold in R 3 which does not intersect with itself, as shown in Figure 2 .Baseline methods To estimate the underlying function on a manifold, we conducted experiments with ConvResNeXts (this paper), as well as a mix of popular off-the-shelf methods including kernel ridge regression, XGBoost, Decision tree, Lasso regression, and Gaussian Processes. For off-the-shelf methods, their hyperparameters are either tuned automatically or avoided using tools provided from the package, e.g., GP. For GP, a Matern kernel is used, and for ridge regression, the standard Gaussian RBF kernel is used.Results. Our results are reported in Figure 3 , 4, 5 which reports the mean square error (MSE) as a function of the effective degree-of-freedom of each method, ambient dimension D and also the number of data points n respectively.As we can see in Figure 3 , ConvResNeXt is able to achieve the lowest MSE at a relatively smaller degree of freedom. It outperforms the competing methods with notable margins despite using a simpler hypothesis.Figure 4 illustrates that standard non-parametric methods such as kernel ridge regression and Gaussian processes deteriorate quickly as the ambient dimension gets bigger. On the contrary, ConvResNeXt and PNN obtain results that are almost dimension-independent due to the representation learning that helps identify the low-dimensional manifold.Finally, the log-log plot in Figure 5demonstrates that there is a substantially different rate of convergence between our methods and kernel ridge regression and GPs, indicating the same formal separation that we have established in the theoretical part -kernels must be suboptimal for estimating Besov classes while the neural architectures we considered can be locally adaptive and nearly optimal for Besov classes. Lemma 7. Approximating Besov function on a smooth manifold using B-spline: Let f ∈ B α p,q (M). There exists a decomposition of f :f (x) = C M i=1 fi • ϕ i (x) × 1(x ∈ B(c i , r)),EQUATIONM) , ϕ i : M → R d are linear projections, B(c i , r) denotes the unit ball with radius r and center c i . Proposition 8. For any function in the Besov space on a compact smooth manifold f * ∈ B s p,q (M), any N ≥ 0, there exists an approximated to f * using cardinal B-spline basis functions:f = C M i=1 P j=1 a i,kj ,sj M m,kj ,sj • ϕ i × 1(x ∈ B(c i , r)),where m is the integer satisfying0 < α < min(m, m -1 + 1/p), M m,k,s = M m (2 k (• -s)), M m denotes the B-spline basis function defined in (2), the approximation error is bounded by ∥f -f ∥ ∞ ≤ C 9 C M P -α/d and the coefficients satisfy ∥{2 kj a i,kj ,sj } i,j ∥ p ≤ C 10 ∥f ∥ B α p,q (M)for some constant C 9 , C 10 that only depends on α.As will be shown below, the scaled coefficients 2 kj a i,kj ,sj corresponds to the total norm of the parameters in the neural network to approximate the B-spline basis function, so this lemma is the key to get the bound of norm of parameters in (11).Proof. From the definition of B α p,q (M), and applying Proposition 1, there exists a decomposition of f * asf * = C M i=1 (f i ) = C M i=1 (f i • ϕ -1 i ) • ϕ i × 1 Ui ,where f i := f * •ρ i , ρ i satisfy the condition in Definition 5, andf i •ϕ -1 i ∈ B α p,q .Using Proposition 16, for any i, one can approximate f i • ϕ -1 i with fi :fi = P j=1 a i,kj ,sj M m,kj ,sj such that ∥f i • ϕ -1 i ∥ ∞ ≤ C 1 M -α/d, and the coefficients satisfy∥{2 kj a kj ,sj } j ∥ p ≤ C 10 ∥f i • ϕ -1 i ∥ B α p,q . Define f = C M i=1 fi • ϕ i × 1 Ui . one can verify that ∥f -f ∥ ∞ ≤ C 9 C M N -α/d. On the other hand, using triangular inequality (and padding the vectors with 0),∥{2 kj a i,kj ,sj } i,j ∥ p ≤ C M i=1 ∥{2 kj a i,kj ,sj } j ∥ p ≤ C M i=1 C 10 ∥f i • ϕ -1 i ∥ B α p,q = C 10 ∥f * ∥ B α p,q (M) ,which finishes the proof.In this section, we demonstrate that a feedforward neural network can approximate the chart selection function z × 1(x ∈ B(c i , r)), and it is error-free as long as z = 0 when r < d(x, c i ) < R. We start by proving the following supporting lemma: Proposition 9. Fix some constant B > 0. = O(d) that approximates d 2 (x; c) = D i=1 (x i -c i ) 2 such that | d2 (x; c) -d 2 (x; c)| ≤ 8DB 2 exp(-C 11 L) with an absolute constant C 11 > 0 when d(x; c) < τ , and d2 (x; c) ≥ τ 2 when d(x; c) ≥ τ , and the norm of the neural network is bounded byL ℓ=1 ∥W ℓ ∥ 2 F + ∥b ℓ ∥ 2 2 ≤ C 12 DL.Proof. The proof is given by construction. By Proposition 2 in Yarotsky(2017) , the function f (x) = x 2 on the segment [0, 2B] can be approximated with any error ϵ > 0 by a ReLU network g having depth and the number of neurons and weight parameters no more than c log(4B 2 /ϵ) with an absolute constant c. The width of the network g is an absolute constant. We also consider a single layer ReLU neural network h(t) = ReLU(t) -ReLU(-t), which is equal to the absolute value of the input.G(x; c) = D i=1 g • h(x i -c i ). Then for any x, c ∈ R D satisfying |x i | ≤ B and |c i | ≤ B for i = 1, . . . , D, we have |G(x; c) -d 2 (x; c)| ≤ D i=1 g • h(x i -c i ) - D i=1 (x i -c i ) 2 ≤ D i=1 g • h(x i -c i ) -(x i -c i ) 2 ≤ Dϵ.Moreover, define another neural networkF (x; c) = -ReLU(τ 2 -Dϵ -G(x; c)) + τ 2 = G(x; c) + Dϵ if G(x; c) < τ 2 -Dϵ, τ 2 if G(x; c) ≥ τ 2 -Dϵ, which has depth and the number of neurons no more than c ′ log(4B 2 /ϵ) with an absolute constant c ′ . The weight parameters of G are upper bounded by max{τ 2 , Dϵ, c log(4B 2 /ϵ)} and the width of G is O(D).If d 2 (x; c) < τ 2 , we have |F (x; c) -d 2 (x; c)| = | -ReLU(τ 2 -Dϵ -G(x; c)) + τ 2 -d 2 (x; c)| = |G(x; c) -d 2 (x; c) + Dϵ| if G(x; c) < τ 2 -Dϵ, τ 2 -d 2 (x; c) if G(x; c) ≥ τ 2 -Dϵ. For the first case when G(x; c) < τ 2 -Dϵ, |F (x; c) -d 2 (x; c)| ≤ 2Dϵ since d 2 (x; c)can be approximated by G(x; c) up to an error ϵ. For the second case when G(x; c) ≥ τ 2 -Dϵ, we have d 2 (x; c) ≥ G(x; c) -Dϵ ≥ τ 2 -2Dϵ and . Thereby we also have |F (x; c) -d 2 (x; c)| ≤ 2Dϵ. If d 2 (x; c) ≥ τ 2 instead, we will obtain G(x; c) ≥ d 2 (x; c) -Dϵ ≥ τ 2 -Dϵ. This gives that F (x; c) = τ 2 in this case.Finally, we take ϵ = 4B 2 exp(-L/c ′ ). Then F (x; c) is an L-layer neural network with O(L) neurons. The weight parameters of G are upper bounded by max{τ 2 , 4DB 2 exp(-L/c ′ ), cL/c ′ } and the width ofG is O(D). Moreover, F (x; c) satisfies |F (x; c) -d 2 (x; c)| < 8DB 2 exp(-L/c ′ ) if d 2 (x; c) ≤ τ 2 and F (x; c) = τ 2 if d 2 (x; c) ≥ τ 2 .Proposition 10. There exists a single layer ReLU neural network that approximates ×, such that for all 0 ≤ x ≤ C, y ∈ {0, 1}, x ×y = x when y = 1, and x ×y = 0 when either x = 0 or y = 0.Proof. Consider a single layer neural network g(x, y) := A 2 ReLU(A 1 (x, y) ⊤ ) with no bias, whereA 1 = -1 C 1 0 1 , A 2 = -C C .Then we can rewrite the neural network g as g(x, y) = -CReLU(-x/C + y) + CReLU(y). If y = 1, we will have g(x, y) = -CReLU(-x/C + 1) + C = x, since x ≤ C. If y = 0, we will have g(x, y) = -CReLU(-x/C) = 0, since x ≥ 0. Thereby we can conclude the proof.By adding a single linear layery = 1 R -r -2∆ (ReLU(R -∆ -x) -ReLU(r + ∆ -x))after the one shown in Proposition 9, where ∆ = 8DB 2 exp(-CL) denotes the error in Proposition 9, one can approximate the indicator function 1(x ∈ B(c i , r)) such that it is error-free when d(x, c i ) ≤ r or ≥ R. Choosing R ≤ τ /2, r < R -2∆, and combining with Proposition 10, the proof is finished.Considering that f i is locally supported on B(c i , r) for all i by our method of construction, the chart selection part does not incur any error in the output.In this section, we focus on the neural network with the same architecture as a ResNeXt in Definition 10 but replacing each building block with a feedforward neural network, and prove that it can achieve the same approximation error as in Theorem 3. For technical simplicity, we assume that the target function f * ∈ [0, 1] without loss of generality. Then our analysis automatically holds for any bounded function.Theorem 11. For any f * under the same condition as Theorem 3, any neural network architecture with residual connections containing N number of residual blocks and each residual block contains M number of feedforward neural networks in parallel, where the depth of each feedforward neural networks is L, width is w:f = W out • 1 + M m=1 f N,m • • • • • 1 + M m=1 f 1,m f n,m = W (n,m) L ReLU(W (n,m) L-1 . . . ReLU(W (n,m) 1 x)) • P (x),whereEQUATIONthere exists an instance f of this ResNeXt class, such thatEQUATIONwhere C 1 , C 2 , C 3 , C 4 , C 5 , C 6 are the same constants as in Theorem 3.Proof. We first construct a parallel neural network to approximate the target function, then scale the weights to meet the norm constraint while keeping the model equivalent to the one constructed in the first step, and finally transform this parallel neural network into the ConvResNeXt as claimed.Combining Lemma 17, Proposition 9 and Proposition 10, by putting the neural network in Lemma 17 and Proposition 9 in parallel and adding the one in Proposition 10 after them, one can construct a feedforward neural network with bias with depth L,width w = O(d) + O(D) = O(d), that approximates M m,kj ,sj (x) × 1(x ∈ B(c i , r)) for any i, j.To construct the neural network with residual connections that approximates f * , we follow the method in Oono & Suzuki (2019) ; Liu et al. (2021) . This network uses separate channels for the inputs and outputs. Let the input to one residual layer be [x 1 , y 1 ], the output is [x 1 , y 1 + f (x 1 )]. As a result, if one scale the outputs of all the building blocks by any scalar a, then the last channel of the output of the entire network is also scaled by a. This property allows us to scale the weights in each building block while keeping the model equivalent. To compensate for the bias term, Proposition 18 can be applied. This only increases the total norm of each building block by no larger than a constant term that depends only L, which is no more than a factor of constant.Let the neural network constructed above has parameterW(i,j) 1 , b(i,j) 1 , . . . , W(i,j) L , b (i,j) Lin each layer, one can construct a building block without bias asW (i,j) 1 = W(i,j) 1 b(i,j) 1 0 0 1 0 , W (i,j) ℓ = W(i,j) ℓ b(i,j) ℓ 0 1 W (i,j) L =   0 0 0 0 W(i,j) L b(i,j) L   .Remind that the input is padded with the scalar 1 before feeding into the neural network, the above construction provide an equivalent representation to the neural network including the bias, and route the output to the last channel. From Lemma 17, it can be seen that the total square norm of this block is bounded by (9). Finally, we scale the weights in the each block, including the "1" terms to meet the norm constraint. Thanks to the 1-homogeneous property of ReLU layer, and considering that the network we construct use separate channels for the inputs and outputs, the model is equivalent after scaling. Actually the property above allows the tradeoff between B res and B out . If all the weights in the residual blocks are scaled by an arbitrary positive constant c, and the weight in the last layer W out is scaled by c -L , the model is still equivalent. We only need to scale the all the weights in this block with |a i,kj ,sj | 1/L , setting the sign of the weight in the last layer as sign(a i,kj ,sj ), and place C M P number of these building blocks in this neural network with residual connections. Since this block always output 0 in the first D + 1 channels, the order and the placement of the building blocks does not change the output. The last fully connected layer can be simply set toW out = [0, . . . , 0, 1], b out = 0.Combining Proposition 16 and Lemma 15, the norm of this ResNeXt we construct satisfyBres ≤ C M i=1 P j=1 a 2/L i,kj ,sj (2 2k/L C 14 dmL + C 12 DL) ≤ C M i=1 P j=1(2 k a i,kj ,sj ) 2/L (C 14 dmL + C 12 DL)≤ (C M P ) 1-2/(pL) ∥{2 k a i,kj ,sj }∥ 2/L p (C 14 dmL + C 12 DL) ≤ (C 10 C F ) 2/L (C M P ) 1-2/(pL) (C 14 dmL + C 12 DL), Bout ≤ 1.By scaling all the weights in the residual blocks by B-1/2 res , and scaling the output layer by BL/2 res , the network that satisfy (11) can be constructed.Notice that the chart selection part does not introduce error by our way of construction, we only need to sum over the error in Section 4.1 and Section 4.1, and notice that for any x, for any linear projection ϕ i , the number of B-spline basis functions M m,k,s that is nonzero on x is no more than m d log P , the approximation error of the constructed neural network can be proved.In this section, we prove that any feedforward neural network can be realized by a convolution neural network with similar size and norm of parameters. The proof is similar to Theorem 5 in (Oono & Suzuki, 2019) . Lemma 12. For any feedforward neural network with depth L ′ , width w ′ , input dimension h and output dimension h ′ , for any kernel size K > 1, there exists a convolution neural network with depthL = L ′ + L 0 -1, where L 0 = ⌈ h-1K-1 ⌉ number of channels w = 4w ′ , and the first dimension of the output equals the output of the feedforward neural network for all inputs, and the norm of the convolution neural network is bounded asL ℓ=1 ∥W ℓ ∥ 2 F ≤ 4 L ′ ℓ=1 ∥W ′ ℓ ∥ 2 F + 4w ′ L 0 , where W ′ 1 ∈ R w ′ ×h ′ ; W ′ ℓ ∈ R w ′ ×w ′ , ℓ = 2, . . . , L ′ -1; W ′ L ′ ∈ R h ′ ×w ′ arethe weights in the feedforward neural network, and W 1 ∈ R K×w×h , W ℓ ∈ R K×w×w , ℓ = 2, . . . , L -1; W L ∈ R K×h×w are the weights in the convolution neural network.Proof. We follow the same method as Oono & Suzuki (2019) to construct the CNN that is equivalent to the feedforward neural network. By combining Oono & Suzuki (2019) lemma 1 and lemma 2, for any linear transformation, one can construct a convolution neural network with at most L 0 = ⌈ h-1 K-1 ⌉ convolution layers and 4 channels, where h is the dimension of input, which equals D + 1 in our case, such that the first dimension in the output equals the linear transformation, and the norm of all the weights is no more thanEQUATIONwhere W ℓ is the weight of the linear transformation. Putting w number of such convolution neural networks in parallel, a convolution neural network with L 0 layers and 4w channels can be constructed to implement the first layer in the feedforward neural network.To implement the remaining layers, one choose the convolution kernel W ℓ+L0-1 [:, i, j] = [0, . . . , W ′ [i, j], . . . , 0], ∀1 ≤ i, j ≤ w, and pad the remaining parts with 0, such that this convolution layer is equivalent to the linear layer applied on the dimension of channels. Noticing that this conversion does not change the norm of the parameters in each layer. Adding both sides of (13) by the norm of the 2 -L ′ -th layer in both models finishes the proof.Proposition 13. If the input to a ReLU neural network is bounded by ∥x∥ 2 ≤ B in , the covering number of the ReLU neural network defined in Proposition 20 is bounded byN (F N N , δ, ∥ • ∥ 2 ) ≤ B in (B/L) L/2 wL δ w 2 L .Proof. Similar to Proposition 20, we only consider the case ∥W ℓ ∥ F ≤ B/L. For any 1 ≤ ℓ ≤ L, for any W 1 , . . . W ℓ-1 , W ℓ , W ′ ℓ , W ℓ+1 , . . . W L that satisfy the above constraint and ∥W ℓ -W ′ ℓ ∥ F ≤ ϵ, define g(. . . ; W 1 , . . . W L ) as the neural network with parameters W 1 , . . . W L , we can see ∥g(x; W 1 , . . . W ℓ-1 , W ℓ , W ℓ+1 , . . . W L ) -g(x; W 1 , . . . W ℓ-1 , W ℓ , W ℓ+1 , . . . W L )∥ 2 ≤ (B/L) (L-ℓ)/2 ∥W ℓ -W ′ ℓ ∥ 2 ∥ReLU (W ℓ-1 . . . ReLU (W 1 (x)))∥ 2 ≤ (B/L) (L-1)/2 B in ϵ.Choosing ϵ = δ L(B/L) (L-1)/2 , the above inequality is no larger than δ/L. Taking the sum over ℓ, we can see that for any W1 , W ′ 1 , . . . , W L , W ′ L such that ∥W ℓ -W ′ ℓ ∥ F ≤ ϵ, ∥g(x; W 1 , . . . W L ) -g(x; W ′ 1 , . . . W ′ L ))∥ 2 ≤ δ.Finally, observe that the covering number of W ℓ is bounded byEQUATION)Substituting B and ϵ and taking the product over ℓ finishes the proof.Proposition 14. If the input to a ReLU convolution neural network is bounded by ∥x∥ 2 ≤ B in , the covering number of the ReLU neural network defined in Definition 10 is bounded by N (F NN , δ, ∥ • ∥ 2 ) ≤ B in (BK/L), . . . W ℓ-1 , W ℓ , W ℓ+1 , . . . W L ) -g(x; W 1 , . . . W ℓ-1 , W ℓ , W ℓ+1 , . . . W L )∥ 2 ≤ K L/2 (B/L) (L-ℓ)/2 ∥W ℓ -W ′ ℓ ∥ 2 ∥ReLU (W ℓ-1 . . . ReLU (W 1 (x)))∥ 2 ≤ K L/2 (B/L) (L-1)/2 B in ϵ,where the first inequality comes from Proposition 24. Choosing ϵ = δ K L/2 BinL(B/L) (L-1)/2 , the above inequality is no larger than δ/L. Taking this into (14) finishes the proof. EQUATIONwith probability at least 1 -c 1 exp(-c 2 nδ 2 n ) for any δ n that satisfy (19), where c 1 , c 2 are universal constants.The function of neural networks is not star-shaped, but can be covered by a star-shaped function class. Specifically, let {f -f :f ∈ F Conv } ⊂ {f 1 -f 2 : f 1 , f 2 ∈ F Conv } := ∂F.Any function in ∂F can be represented using a ResNeXt: one can put two neural networks of the same structure in parallel, adjusting the sign of parameters in one of the neural networks and summing up the result, which increases M, B res and B out by a factor of 2. This only increases the log covering number in (10) by a factor of constant (remind that B res = O(1) by assumption).Taking the log covering number of the ResNeXt (10), the sufficient condition for the critical radius as in ( 19) isEQUATIONwhere ≲ hides the logarithmic term.Because L is 1-Lipschitz, we haveL(f ) ≤ L( f ) + ∥f -f ∥ ∞ . Choosing P = O   K -2 L-2 w 3L-4 L-2 L 3L-2 L-2 n - 1-2/L 2α/d(1-1/L)+1-2/pL   ,and taking Theorem 3 and ( 16) into (15) finishes the proof.In this section, we study the minimax lower bound of any estimator for Besov functions on a ddimensional manifold. It suffices to consider the manifold M as a d-dimensional hypersurface. Without the loss of generalization, assume that ∂L(y) ∂y ≥ 0.5 for -ϵ ≤ y ≤ ϵ. Define the function spaceEQUATIONwhere M (m) denotes the Cardinal B-spline basis function that is supported on (0, 1) d , j = [j 1 , . . . , j d ]. The support of each B-spline basis function splits the space into s d number of blocks, where the target function in each block has two choices (positive or negative), so the total number of different functions in this function class is |F| = 2 s d . Using Dũng (2011, Theorm 2.2), we can see that for anyf ∈ F, ∥f ∥ B α p,q ≤ ϵ s α s α-d/p s d/p = ϵ. For a fixed f * ∈ F, let D = {(x i , y i )} ni=1 be a set of noisy observations with y i = f * (x i ) + ϵ i , ϵ i ∼ SubGaussian(0, σ 2 I). Further assume that x i are evenly distributed in (0, 1) d such that in all regions as defined in ( 17), the number of samples is n j := O(n/s d ). Using Le Cam's inequality, we get that in any region, any estimator θ satisfy F SUPPORTING THEOREM Lemma 15. [Lemma 14 in Zhang & Wang (2022) ] For any a ∈ R M , 0 < p ′ < p, it holds that: ∥a∥ p ′ p ′ ≤ M 1-p ′ /p ∥a∥ p ′ p . Proposition 16 (Proposition 7 in Zhang & Wang (2022) ). Let α -d/p > 1, r > 0. For any function in Besov space f * ∈ B α p,q and any positive integer M , there is an M -sparse approximation using B-spline basis of order m satisfying 0 < α < min(m, m -1 + 1/p): f M = M i=1 a ki,si M m,ki,si for any positive integer M such that the approximation error is bounded as ∥ f M -f * ∥ r ≲ M -α/d ∥f * ∥ B α p,q , and the coefficients satisfy ∥{2 ki a ki,si } ki,si ∥ p ≲ ∥f * ∥ B α p,q . Lemma 17 (Lemma 11 in (Zhang & Wang, 2022) ). Let M m,k,s be the B-spline of order m with scale 2 -k in each dimension and position s ∈ R d : M m,k,s (x) := M m (2 k (x -s)), M m is defined in (2). There exists a neural network with d-dimensional input and one output, with width w d,m = O(dm) and depth L ≲ log(C 13 /ϵ) for some constant C 13 that depends only on m and d, approximates the B spline basis function M m,k,s (x) := M m (2 k (x -s)). This neural network, denoted as Mm,k,s (x), x ∈ R d , satisfy• | Mm,k,s (x) -M m,k,s (x)| ≤ ϵ, if 0 ≤ 2 k (x i -s i ) ≤ m + 1, ∀i ∈ [d],• Mm,k,s (x) = 0, otherwise.• The total square norm of the weights is bounded by 2 2k/L C 14 dmL for some universal constant C 14 .Proposition 18. For any feedforward neural network f with width w and depth L with bias, there exists a feedforward neural network f ′ with width w ′ = w + 1 and depth L ′ = L, such that for any x, f (x) = f ′ ([x T , 1] T )Proof. Proof by construction: let the weights in the ℓ-th layer in f be W ℓ , and the bias be b ℓ , and choose the weight in the corresponding layer in f ′ be Proof. Notice that ReLU function is 1-homogeneous, similar to Proposition 4 in (Zhang & Wang, 2022) , for any neural network there exists an equivalent model satisfying ∥W ℓ ∥ F = ∥W ℓ ′ ∥ F for any ℓ, ℓ ′ , and its total norm of parameters is no larger than the original model. Because of that, it suffices to consider the neural network satisfying ∥W ℓ ∥ F ≤ B/L for all ℓ. The Lipschitz constant of such linear layer is ∥W ℓ |∥ 2 ≤ ∥W ℓ |∥ F ≤ B/L, and the Lipschitz constant of ReLU layer is 1. Taking the product over all layers finishes the proof.W ′ ℓ =Proposition 21. An L-layer ReLU convolution neural network with convolution kernel size K, no bias and bounded norm  
 
 Appendix:  


Decision: The paper investigates the performance of an overparameterized convolutional residual network architecture (ConvResNeXt) on a nonparametric classification problem trained with weight decay. This model generalizes other ConvResNets, including ConvResNet [He et al., 2016] and aggregated ResNet [Xie et al., 2017].

ConvResNeXt consists of N residual blocks, each with a parallel structure of M building blocks, and each building block containing L layers. The analysis focuses on the scenario with infinitely many building blocks.

Authors show that weight decay promotes sparsity in these blocks, leveraging the fact that the optimal classifier resides on a low-dimensional smooth manifold. This allows the model to learn the target function class efficiently, avoiding the curse of dimensionality.

All reviewers agreed on the merits of the paper.

Reviews: review: paper_summary: paper_summary: The paper provide theoretical analysis for the good prediction performance of convolutional residual neural networks, even overparameterized.
strength_weakness: strength_weakness: In line 71, 72, the overparameterization is defined as " the number of blocks is larger than the order of the sample size n". Where is this definition comes from?
questions: questions: 1. Can you generalize from  the empirical logistic risk to other risks? How will the choice of loss change the bound?
2. Can you explain in details about the extra effort (underlying theoretical techinique) you made in this paper to differentiate from  Liu et al. 2021 (Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks)? How do you generalize it to over-parameterized setting and ConvResNeXt?
limitations: limitations: The analysis is limited to convolutional networks. It's interensting to see if it can be further generalized to other architectures like transformers.
paper_summary: paper_summary: This paper builds the deep learning theory for studying convolutional residual neural networks with data lying on an embedded lower-dimensional manifold. Theoretical results on both approximation error and estimation error are provided, and interesting implications from the theory are discussed.
strength_weakness: strength_weakness: 1. This paper avoids the curse of dimensionality through assuming that the data lies in a low-dimensional manifold embedded in the ambient space. While real world data typically exhibit manifold structure, they commonly don't lie precisely on a manifold, but instead are surrounding a manifold (i.e. + noise). The theory of this paper highly depends on the exact manifold assumption since it needs the associated partition of unity to split the problem into local charts.
2. Among the remarks/implications made on page 7, it is said that overparameterization is fine. However, to my understanding, the problem of overparameterization is not about an overparameterized model not being expressive enough (which this paper addresses), but really about the difficulty in finding a good enough local minimizer for it during optimization. To this regard, Theorem 3.3 based on the global minimizer doesn't really answer it.
questions: questions: 1. The remarks on tradeoff between width and depth are very interesting. Have you tried this in numerical experiments to see if this theoretical driven intuition actually appears in experiments?
2. Other than the analysis being more general, what are the theoretical benefits of adding the identity map (i.e. the residual network) and multiple CNN blocks together compared to just using a CNN block?
limitations: limitations: See weaknesses and limitations.
paper_summary: paper_summary: The paper studies the performance of an overparametrized convolutional residual network architecture on a nonparametric classification problem trained with weight decay. This model, known as ConvResNeXt, involves N residual blocks, where each residual block has a parallel architecture of M building blocks, and each building block with L layers. As such it generalizes alternative ConvResNets in the literature and includes them as a special case, e.g., ConvResNet [He et al 2016] when M=1 and aggregated Resnet [Xie et at 2017] when N=1. Specifically, the analysis results consider infinitely many building blocks and shows that weight decay training implicitly enforces sparsity of these blocks considering that the optimal classifier is supported on a low dimensional smooth manifold. As such, they show that this model can efficiently learn the assumed function class without suffering from the  curse of dimensionality.
strength_weakness: strength_weakness: 1) The actual benefit of having parallel paths in the proposed ConvResNeXt model was not addressed fully. Indeed, the results stating that only the product of number of parallel paths M and depth N determines the convergence rate, and one may not need parallel blocks when residual connections are present contradict with some of the earlier findings in the literature. For example, in [Xie et at 2017]. In the mentioned prior work, several experimental results focus on the posive effect of having higher cardinality (more multiple parallel paths) than increased depth and width. 
2) If there is no additional benefit of having additional parallel paths, and an equivalent performance can be achieved by increasing the depth only, this will limit the capability of the proposed ConvResNeXt over the ConvResNets unline the claimed benefits of the former.
questions: questions: 1)	This new architecture introduce significantly more complex nested function form, but similar performance in both approximation and estimation errors can be achieved by rather simpler one. The provided bounds on the two errors do not suggest any practical benefit of ConvResNeXts over ConvResNets. If so, what would be the motivation to generalize for the former?
2)	In Sec 3.2, it was stated that the number of building blocks M does not influence the estimation error as long as it is large enough. This must be contrasted with the earlier findings about the cardinality of the parallel paths, and any difference must be clearly stated.
3)	In Sec 3.2, the tradeoff between width and depth was mentioned to be less important in ResNext. In particular, it was stated that the lower bound on the error does not depend on the arrangements of the blocks M and N as long as their product remains same and large enough. One should further address the reason behind this and compare it with the literature again. Moreover, if that’s so, does this suggest that an equivalent model that can achieve equivalent performance without parallel paths?
limitations: limitations: No, authors did not adequately address the limitations of their work, and no potential negative societal impact of their work is identified.
paper_summary: paper_summary: The authors study the performance of ConvResNets trained with weight decay from the perspective of nonparametric classification. Specifically, the authors consider a smooth target function supported on a low-dimensional manifold, then prove that ConvResNets can adapt to the function smoothness and low-dimensional structures and efficiently learn the function without suffering from the curse of
dimensionality.
strength_weakness: strength_weakness: Literature review is not sufficient. Minimax optimal nonparametric classification using DNN has been recently studied by other authors, though the current paper consider another novel neural network, the ConvResNets, which is different from the traditional DNN.
questions: questions: Nonparametric classification can be done in different frameworks such as (1) smooth decision boundary, (2) smooth conditional class probability or (3) smooth margin. The minimax optimal rates in the above settings are different. For instance, some authors find that DNN classification in (1) and (2) yield different minimax rates.  In particular, the minimax optimal rate under (1) is an open problem (see Kim's work) which was recently addressed by Hu et al. The minimax rate under (2) has been recently established for ultrahigh-dimensional case for DNN classification by Wang's work. The minimax rates under (1) and (2) may have different expressions.

I guess that this paper considers the setting of smooth conditional class probability, and the manifold dimension D is fixed. It would be great to comment on its extension to ultrahigh-dimensional case as in Wang's work.
limitations: limitations: NA

Comments: title: Thanks for responses!
comment: Thank you for your reply and letting us know your concerns! We understand your main arguments and would like to explain our motivations here. As noted in Section 1.1 and our answer to Q1, our biggest motivation is to provide new theoretical understanding of **overparameterized** networks. Specifically, we establish representation theory and statistical rate for the **overparameterized** ResNeXts (or ResNets as a special case) when learning Besov functions on low-dimensional manifolds, rather than merely generalizing ResNets to ResNeXts. In comparison, existing results such as Liu et. al. 2021 can only work for ResNets with exact-parameterization, and fails in overparameterized regimes for either ResNeXts or ResNets.

Moreover, we would like to clarify that we are **not** motivated to either propose new architectures or demonstrate the marginal benefits of parallel paths in ResNeXts. Instead, we focus on “overparameterization”, and attain the equivalent representation and generalization power of ResNeXts with the same $MN$ as a **side product**. Therefore, our results do not ***“induce a contradiction to initial motivation”***. To demonstrate this equivalence observed in ResNeXts, we ran some CIFAR10 experiments with a number of $M,N$ combinations and got the following results:

| # of Blocks $M$ | # of paths $N$ | Width | Epochs | CIFAR10 Accuracy |
|--------------------|-------------------|--------|----------|-----------------------|
| 8           | 3 | 64 |   450 | 96.38|
| 4 | 6 | 64 | 320 | 96.37|
| 3 | 8 | 64 | 300 | 96.35 (Table 7, Xie et. al. 2017)|

Our experiments show that ResNeXts with more blocks, if allowed more training efforts, can achieve comparable performance. This also evidentiates that ResNeXts with less parallel paths, though likely harder to be optimized, can possess the same representation and generalization power.

We hope the reviewer can value our contributions and see the practical implications of our theoretical findings.
I thank the authors for detailed response in the rebuttal. After reading all the comments and the paper again, I still have the same concerns regarding the novelty and the contribution of this work. 
The authors claim that they focus on the representation and generalization abilities of overparameterized ConvResNeXts (which is not sufficiently motivated over the ConvResNets), and not their optimization. However, they state that the potential practical benefits of parallel paths does not stem from improved representation or generalization capabilities, but likely from optimization aspects which they do not cover. I believe this induces a contradiction to their initial motivation if not misinterpretation. Moreover, their theoretical results also reflect the same argument that as long as the product of number of paths and the depth remains the same, the architecture can be reduced down to ConvResNets (with residual connections but no parallel paths). Although I find the discussion and the results interesting, I think it needs further clarification on the motivation and the actual benefit of the proposed model over the existing one by exploring the optimization aspects of their architecture with parallel paths. As such, I would keep my initial rating.
Thank you to the authors for the detailed reply. Most of my concerns and questions have been addressed, and I will increase my rating accordingly.
Thank you for the references! We will cite these works and add further discussions in our next version.
My concerns were well addressed unless some other references in DNN classification are still missing. For instance, I notice the following works are relevant:

Minimax optimal deep neural network classifiers under smooth decision boundary

Sharp rate of convergence for deep neural network classifiers under the teacher-student setting

Deep neural network classifier for multidimensional functional data

Minimax optimal high‐dimensional classification using deep neural networks
Dear Reviewer,

Thank you again for the detailed review. As there are only two days left in the discussion period, we wanted to ask if you have any further comments or questions for us to consider.

If our rebuttal discussing our result's novelty and contributions addressed your concerns, we would really appreciate it if you would consider raising your score.

Best,

Submission7950 Authors
Dear Reviewer,

Thank you again for the detailed review. As there are only two days left in the discussion period, we wanted to ask if you have any further comments or questions for us to consider.

If our rebuttal discussing our result's generality and contributions addressed your concerns, we would really appreciate it if you would consider raising your score.

Best,

Submission7950 Authors
Dear Reviewer,

Thank you again for the detailed review. As there are only two days left in the discussion period, we wanted to ask if you have any further comments or questions for us to consider.

If our rebuttal discussing our result's novelty and generality addressed your concerns, we would really appreciate it if you would consider raising your score.

Best,

Submission7950 Authors