Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks
Authors: Zixuan Zhang
Kaiqi Zhang
Minshuo Chen
Yuma Takeda
Mengdi Wang
Tuo Zhao
Yu-Xiang Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: Nonparametric Classification
Low Dimensional Manifolds
Overparameterized ResNets
Function Approximation.
Primary area: learning_theory
TL;DR: We prove that an overparameterized ResNeXts achieves close-to-minimax rate in learning Besov funtions on a low dimension manifold under weight decay.

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.

Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks
Zixuan Zhang"
Kaiqi Zhang" UC Santa Barbara kzhang70@ucsb.. edu
Georgia Tech zzhang31050gatech. edu
Minshuo Chen Northwestern University minshuo. wwwn@northwesterree.. edu
Yuma Takeda
University of Tokyo utklav15110mmall. com
Mengdi Wang Princeton University mengdiw@princeton.. edu
Tuo Zhao
Yu-Xiang Wang
Georgia Tech
UC San Diego
tourzhao@gatech..de
yuxiangweucsd.cm edu
Abstract
Convolutional residual neural networks (ConvResNets)), though overparameter- sized, can achieve remarkable prediction performance practice, which cannot be well explained by conventional wisdom. To bridge this gap, we study the perfor- mance of ConxResNeXts trained with weight decay, which cover CestResNets special case, from the perspective of nonparametric classification. Our analy- sis allows for infinitely many building blocks in ConvRes and shows that weight decay implicitly enforces sparsity these blocks. Specifically, consider a smooth target function supported on dow-dimensional manifold, then prove that Nex structures and efficiently learn the function without suffering from the curse of dimensionality. Our findings partially justify the advantage of overparameterizzd ConvResNe over conventional machine learning models.
adapt to the function smoothness and low-dimensional
Introduction
Deep learning has achieved significant success in various real-worke applications, such as computer
vision [4 23 26),, natural language processing 15 42 and robotics [16]. 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% 19 using Convolutational Residual Network (ConvResNets) on training dataset of million labeled high-resolution images in 1000 categories.
Researchers have attributed the remarkable performance of deep learning to its great flexibility in modeling complex functions, which has motivated many works on investigating the representation power of deep neural networks. For instance, early work such as Barron 3 Cybenko [7]. Kohler and Krzyžak [22] initialized this line of research for simple feedforward neural networks (FNNs) 19 20 33 37 More recently, Suzuki [32. Yarotsky [1] gave more precise bounds on the model sizes in terms of the approximation error, and Oono and Suzuki (30) further established bound for more advanced architectures Nets Based on these function approximation theories,
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

one can further establish generalization bounds of deep neural networks with finite samples. Taking Oono and Suzuki [30] as an example again, they showed that ConvResNets with O(nD/(aaD)) D) parameters can achieve a minimax optimal convergence rate o(n=2a/(2a+D) while approximating a Oa nonparametric regression function with n samples. Unfortunately, these theoretical results cannot well explain the empirical successes of deep learning well, as they require the model size to be no larger than (n) (the generalization bounds become vacuous otherwise). However, in real applications, practical deep learning models are often overparmameterized, that is the model size can greatly exceeds the sample size.
1.1 Main Results
Overparamettrization of neural networks has been considered research problems in deep learning theories, where parameters can significantly exceed training samples. There has been substantial empirical evidence showing that overparamettrrizaton can help fit the training data, ease the challenging nonconvex optimization, and gain robustness. However, existing literature on deep learning theories under such an overparameterized regime is very limited. To the best of our knowledge, we are only aware of Zhang and Wang [43], which attempts to analyze overparameterized neural networks trained with weight decay. However, their work still suffers from two major restrictions: (1) They consider parallel FNN, which is rarely used in practice. Whether similar results hold for more practical architectures remains unclear; (2) Their generalization bound from the curse of dimensionality, where the sample size is require to scale exponentially with the input dimension.
of the most fundamental
To address (1), we propose to develop a new theory for nonparametric classification using overparam- eterized Nes trained with weight decay [4). The NentResNeXt generalizes ResvResNets and includes them as special case [8 33 Compared with FNNs, NonyResNe exhibit three features: (i) Instead of using dense weight matrices, they use convolutional filters, which can naturally investigate the underlying structures of the input data such as images and acoustic signals; (ii) They are equipped with skip-layer connections, which divides the entire network into blocks. The skip-layer connection can effectively address the vanishing gradient issue and therefore allow the networks be significantly deeper; (iii) They are equipped with parallel architectures, which enable multiple "paths" within each block of the network, and allows the network to learn a more diverse set of features. Figure Tb illustrates the structure of RenxResNeXts (detailed introductions of Cen is deferred to Section 2.3 This architecture introduces significantly more complex nested function form, presenting us with the challenge of addressing novel issues in bounding the metric entropy of the function class.
To address (2), our proposed theory considers the optimal classifier is supported on d-dimensional smooth manifold M isometrically embedded in IR' with d < D. The low-dimensional manifold assumption is highly practical, since it aligns with the inherent nature of many real-world datasets. For example, images typically represent projections of 3-dimensional objects subject to various transformations like rotation, translation, and skeletal adjustments. Such a generating mechanism inherently involves a limited set of intrinsic parameters. More broadly, various forms of data, including visual, acoustic, and textual, often exhibit low dimensional structures due to rich local regularities, global symmetries, repetitive patterns, or redundant sampling. It is reasonable to model these data as samples residing in proximity to a low dimensional manifold.
Our theoretical results can be summarized as follows:
We prove that when ConvResNeXts are overparameterrzed, 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 when trained with weight decay. That is, given that the target function belongs to the Besov space B (M the risk of the estimator given by the ConvResNeX: class converges to the optimal o/d
risk at the rate Ö(n za/2f7 (1-o(1))) with samples. Notably, the statistical rate of convergence in our theory only depends on the intrinsic dimension d, which circumvents the curse of dimensionality in Zhang and Wang [33
'The Besov space includes functions with spatially heterogeneous smoothness and generalizes more elemen- tary function spaces such Sobolev and Hölder spaces.
2

---

Moreover, our theory shows that one can scale the number of "paths" M in each block with the depth N as roughly MN Z n 3 which does not affect the convergence rate. This partially justifies the flexibility of the ConvResNeXt architecture when designing the bottlenecks, which simple structures like FNNs cannot achieve. Moreover, we can exchange the number of "paths" M and depth N as long as their product remains the same. This further provides the architectural insight that we don't necessarily need parallel blocks when we have residual connections. To say differently, we provide new insight into why "residual connection" and "parallel blocks" in RtsNeXts are useful in both approximation and generalization.
Another technical highlight of our paper is bounding the covering number of weight-decayen Ces which is essential for computing the critical radius of the local Gaussian complexity, Specifically, we adopted a more advanced method that leverages the Dudley's 's chaining of the metric entropy 4 This technique provides a tighter bound than choosing a single radius of the covering number as in Zhang and Wang 43).
To the best of our knowledge, our work is the first develop approximation and statistical theories for Nons as well as overparameterized ContResNets.
1.2 Related Works
Our work is closely related to Liu et al. (25). which studies nonparametric classification under similar setup the optimal classifier belongs to the Besov space supported on a low dimensional manifold. Despite they develop similar theoretical results to ours, their analysis does not allow the model to be overparameterized, and therefore is not applicable to practical neural networks. Moreover, they investigate ConvResNets, which is a special case of NonxResNeXt in our work.
Our work is closely related the reproducing kernel methods, which are also often used for nonparametric regression. However, existing literature has shown that the reproducing kernel methods lack the adaptivity to handle the heterogeneous smoothness in estimating Besov space functions, and only achieve suboptimal rate of convergence in statistical estimation 32].
Our work is closely related neural tangent kernel theories [ which study overparameterized neu- ral networks. Specifically, under certain regularity conditions, they establish the equivalence between overparameterrize neural networks and reproducing kernel methods, and therefore the generalization bounds of overparameterized networks can be derived based on the associated reproducing kernel Hilbert space. Note that neural tangent kernel theories be viewed special cases of the theories for general reproducing kernel methods. Therefore, they also lack the adaptivity to be successful in the Besov space thus do not capture the properties of overparameterized neural networks.
2 Preliminaries
In this section, we introduce some concepts on manifolds. Details can be found in 35 and 24). Then provide detailed definition of the Besov space smooth manifolds and the CenNResNeXt architecture.
2.1 Smooth manifold
Firstly, we briefly introduce manifolds, the partition of unity and reach. Let M be a d-dimensional Riemannian manifold isometrically embedded in R. with d much smaller than D.
Definition 2.1 (Chart). A chart on M is a pair (U, σ) such that U C .M is open and Φ U + R4, where Φ is homeomorphism (i.e., bijective, & and @ are both continuous).
In a chart (U, is called coordinate neighborhood, and ø coordinate system on U. Essentially, chart is a local coordinate system on M. A collection of charts that covers M is called an atlas M.
Definition 2.2 (C* Atlas). A C* atlas for M is collection of charts ((U,, (e) which satisfies USe Us = M, and are pairwise O compatible:
ài o 25 (S(U (g))) @. n U3) and 03 (((Un (z(U, are both C* for any i E A. An atlas is called finite if it contains finitely many charts.
3

---

Definition 2.3 (Smooth Manifold), A smooth manifold is manifold M together with C atlas.
Classical examples of smooth manifolds are the Euclidean space, the torus, and the unit sphere. Furthermore, we define C* functions
smooth manifold M as follows:
Definition 2.4 (C* functions on M). Let M be smooth manifold and M R be function on
M. A function f : .M- - R is C if for any chart (U, () on M, the composition for 2- ((U) - R continuously differentiable up order
We next define the C partition of unity, which is an important tool for studying functions on manifolds.
Definition 2.5 (Partition of Unity, Definition 13.4 in (35). A C partition of unity on a manifold M is a collection of C functions hieA with A: M + [0, such that for any æ E M, there a neighbourhood of where only finite number of the functions in fpilee are nonzero, and
Σ px(2)) = 1.
VEAA
An open cover of manifold MM is called locally finite if every x .M has neighborhood that intersects with finite number sets in the cover. The following proposition shows that a O partition of unity for smooth manifold always exists.
Proposition 2.6 (Existence of C partition of unity, Theorem 13.7 in (35). Let (UiJiEA be locally finite cover of a smooth manifold M. Then there is a C partition of unity {pi)-=1 where every Pi has compact support such that supp(p:) C Uj.
Let {(U;, di) be C atlas of M. Proposition 2.6 guarantees the existence of a partition of unity (pitiEA such that p; is supported on U,. To characterize the curvature of manifold, we adopt the geometric concept: reach.
Definition 2.7 (Reach 12
Denote
G = a App q E M such that ||
-pl12 = ||
2/12 = inf
||
vll2
yEM
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 inf #EM VEG
| y112.
Reach has a simple geometrical interpretation: for every point M, the osculating circle's radius is at least T. A large reach for M indicates that the manifold changes slowly.
2.2 Besoy l'unctions on a smooth manifold
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 [TO]. 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 and Figure 4 of Mammen and van de Geer (27..
To define Besov functions rigorously, we first introduce the modulus of smoothness.
Definition 2.8 (Modulus of Smoothness 8 32 ). Let Ω C. RD_ For a function f FR + R be in (P( for p > 0, the r-th modulus of smoothness of f defined by
Wr,p
sup 2
|| (f)
Σ (-1) f(x + jih)
1æ e S
where (z))(z)
otherwise.

---

D, as demonstrated in Definition 2.9 (Besov Space B (2)). For 0 p.9. 00,00 0,r= [a] - 1, define the seminorm
1- as
if < 0c,
Ifl F.g (9)
supiso t wrp(
=0.
The norm of the Besov space B (St) is defined as || 13, || + 1lB Then the Besov space is defined as p, (S2) (s ( Bg.. < 00).
Moreover, we show that functions in the Besov space can be decomposed using B-spline basis functions the following proposition.
Proposition 2.10 (Decomposition of Besov functions). Any function in the Besov space paay > d/p can be decomposed using B-spline of order m.m for any Rd,, have
f(x) - - Σ
C.. (f)
(1)
8 OBE((N)
where (lk) == {2~*2 (-m, 2 + mm C ) Mm,kk, == (2 s)), and M²(x)) =
I Mg(x;) is the cardinal B-spline basis function which can be expressed as polynomial:
m++1
m + ) (2-
Mm)
(2)
m.!
1=1
We next define Bg functions on M. Definition 2.11 (B% Functions M 13
34
Let.M be compact smooth manifold of dimension
d. Let (UU, dx)) CM be a finite atlas on M and {pr
Cm be a partition of unity on M such that i=1
supp(p;) Ug. function M R is in Bg (MM
CM
Ilfleg, (M) = 0 (lg, < cc.
(3)
Since pt supported on U4, the function (fp supported on (U.)). We can extend (fpx)oo)- from (U,)) Rdd by setting the function to be on Rdd (UU)). The extended function lies in the Chapter 7J.
Besov space p.q (12 3
2.3 Architecture of ContResNeXt
We introduce the architecture of ConvResNeX's ConxResNeXts have three main features: convolu- tion kernel, residual connections, and parallel architecture.
Consider one-sided stride-one convolution in our network. Let W = [Wjaa]} E Re' xxx be a convolution kernel with output channel size w', kernel size K and input channel size w. For E Dx the convolution of W with gives y E DD such that
w
y = W*z,
Vi
W W3R12i4k-111
where 1 D, w/ and 244-111 0 for i Figure Ia
The building blocks of ConvResNeXis are residual blocks. Given an input each residual block computes F(xr), where F is a subnetwork called bottleneck, consisting of convolutional layers. ConvResNe 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 (ReL.) activation function, i.e., o (z) = max max(2,00 0}. We next provide the detailed definition of ConvResNeXts follows:
5

---

j-th column
id
K
W jiss
id
2
D
W
D
Wj
id
JN.
IN.
(x)
Figure 1: (a) Demonstration of the convolution operation W 2, where the input is E RDxx, and the output is W Dxw', Here W1.,; is D x matrix for the j-th output channel. (b) Demonstration of the ConvResNeXt. f111... fN.M are the building blocks, each building block is convolution neural network.
Definition 2.12. Let the neural network comprise N residual blocks, each residual block has parallel architecture with M building blocks, and each building block contains L layers. The number of channels w, and the convolution kernel size K. Given an input R ConvResNeXt with ReLU activation function can be represented as
f(x)= = out Σ fN.m + +idjo...
EEE fi.m + id o P(x))
(5)
fnm w (n.m)
W 1-1 *o (m.m)) *
(n.m))
where is the identity operator, P RDD + Dx
padding operator satisfying P(æ)
[x. 0 0) RDx [ (m.m) ).f is collection of convolution kernels for I,..., .N. N, 1...., M, W out E ger denotes the linear operator for the last layer, and the convolution operation defined in (4)
The structure Con shown Figure lb] When M = 1, the ConvResNeXt defined in reduces CenvResNet. For notational simplicity, omit biases in the neural network structure by extending the input dimension and padding the input with a scalar (See Proposition F4 for more details). The channel with O's is used to accumulate the output.
3 Theory
In this section, we study binary classification problem on M C [-1, Specifically, we are given i.i.d. samples (æi, ye 12 DD where æ; M and y; {0,1) 3 is the label. The label y {0, 1) follows the Bernoulli-type distribution
exp(uf((x)) P(y|=) 1 + exx((f((x))
for some f* .M- + IR belonging the Besov space. More specifically, make the following assumption on fr
Assumption 3.1. Let < p.q oa, d/p < < co. Assume f (M) and ||f IIf""lla, S Cp for some constant Op 0.
To learn fr, we minimize the empirical logistic risk over the training data:
f arg min Fooy
Σ [M log(1 exp(-f(xx)) + (1 y.) log(1 + exp(f(x:)))),
(6)
where Cony some neural network class specified later. For notational simplicity, we denote empirical logistic risk function in (6) as L.. (J), and denote the population logistic risk as
Ep([(f)] E( log(1 + exp( f()))) + (1 y) log(1 + exp(f(x))))

---

We next specify the class of Xons for learning f*:
Cono (N, M, L, K, w, Bres, Bout) = { f is in the form of (5) with N residual blocks. Every
residual block has building blocks with each building block containing L layers. Each layer has kernel size bounded by K, number of channels bounded
Σ
(n.m) lB S
Bress Wout |l S out f(x) [0. 1] for any a E M.J. (7)
Note that the hyperparameters FCoo will be specified in our theoretical analysis later.
As can be seen, FFee contains the Frobenius norm constraints of the weights. For the sake of com- putational convenience 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:
N
M
arg min JEFCouy L, (o,,.,,) f
(n +
Σ
11
X2 W Woutllf ll
==1 m=1 8m1
where ' A2 > are properly chosen regularization parameters.
3.1 Approximation theory
In this section, we provide a universal approximation theory of ConvResNeXts for Besov functions on smooth manifold:
Theorem 3.2. For any Besov function fo on a smooth manifold satisfying q 2 a - d/p > 1,
(ffllay,,(4 S Cr.
for any P > O and any ConvResNeXt class Foom L, Bres Bout) satisfying L L' Lo - 1,, 2 3, where Lo = [ and
MN 2 CMP,w 2 Cim + +D), Bres I CCL//K, Bout S CC30f((dm D)
there exists f FCom (N, M, L, K, w, Bress Bous) such that
|| - Soll CCCM (Cap-ald + Cs exp(-CoL' log P)),
(8)
where C₁ C2 C3 are universal constants and C4. Cs. Cs are constants that only depends on d and m, the intrinsic dimension of the manifold and m an integer satisfying a min(m, 1 1+
The approximation error of the network is bounded by the sum of two terms. The first term is 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 layers. The proof is deferred to Section 4.1 and the appendix.
3.2 Estimation theory
Theorem 3.3. Suppose Assumption 3.1 holds. Set L L' + Lo 1, 2 3, where Lo 1 and
1-2/1 MN2CA P= -
w 2 Cildm + D)-
Let i be the global minimizer given in (6) with the function class F F (N, M, L, K,w, Bres Bow)). Then we have
1/1013/1 20/4(1 1//40-111441-/000
ED En(c((()),)) Eo((((()).)) SCT
+ C's eCsexp((CCr exp(-CoL'),
where the logarithmic terms are omitted. Cr the constant defined Theorem 3.2 CT, C3 are constants that depend on Cp, CM, d, K. is the size of the convolution kernel.
7

---

We would like to make the following remarks about the results:
Strong adaptivity: By setting the width of the neural network to any Besov functions on any smooth manifold, provided that dm S 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.
2C1 D, the model adapt
No curse of dimensionality: the above error rate only depends polynomially on the ambient dimension D and exponentially on the hidden dimension d. Since 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.
O Dverparameterization is fine: the number of building blocks in ConvResNeXt does not influence the estimation error as long as large enough. other words, this matches the empirical observations that neural networks generalize well despite overparameterization.
Close minimax rate: The lower bound of the I-Lipschitz error for any estimator 0 is
o/d
min max E
(O(D), N
Za/d
Comparing to the minimax rate, we can see that as L + oc, the above error rate converges to the minimax rate up to constant term. In other words, overparameterized CenvResNeXt can achieve close to the minimax rate in estimating functions Besov class. In comparison, all kernel ridge regression including any NTKs will have suboptimal rate lower bounded by 2a-d, which is suboptimal.
where 2 notation hides a factor of constant. The proof can be found in Appendix E.
2a
Deeper is better: with larger I., the error rate decays faster and gets closer to the minimax rate. This indicates that deeper model can achieve better performance than shallower models.
Tradeoff between width and depth: With a fixed budget in the number of parameters, the tradcoff between width and depth is crucial for achieving the best performance, and this often requires repeated, cone-consuming experiments. On the other hand, our results suggests that such a tradeoff less important in ResNeXt. The lower bound of error does not depend on the arrangements of the residual blocks M and N, as long as their product large enough. This can partly explain the benefit of ResNeXt over other architecture.
By choosing L. O(lg((n) in Theorem 3.3 the second term the error can be merged with the first term, and close to the minimax rate can be achieved:
Corollary 3.4. Given the conditions in Theorem 3.3 set the depth of each block is L = (log(n)) and then the estimation error of the empirical risk minimizer satisfies
Ed(C(f()) v)1 s Ex[[((*)) + Ö(n 2-/a-I (1-0()))
where Ō(-) omits the logarithmic term.
The proof of Theorem 3.3 deferred Section 4.2 and Section D.2 The key technique is computing the critical radius of the local Gaussian complexity by bounding the covering number of weight- decayed ConyResNeXts. This technique provides a tighter bound than choosing single radius of the covering number as in Suzuki [32], Zhang and Wang [43] The covering number of an overparameterized ConvResNeXt with norm constraint (Lemma 4.1 is one of our key contributions.
4 Proof overview
4.1 Approximation error
We follow the method in Liu al. (25) to construct a neural network that achieves the approximation eиror we claim. It 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 (25] and partition M using a finite number of open balls on IR" ? Specifically, we define B(c;, r) as the set of unit balls with center c; and radius r such
that their union covers the manifold of interest, i.c., M C UM ().,.)) This allows us to partition
8

---

the manifold into subregions U; = B(c,, r) n.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 2.6 See Section C for the detail.
Step 2: Locally approximate the decomposed functiinn 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 M. and The difference between our result and previous work is
was applied in a series of works 43 that we define norm on the coefficients and bound this norm, instead of bounding the maximum value. The detail is deferred Section C22
32 25
Step 3: Approximate the polynomial functions using neural networks. In this section, we follow the method in Zhang and Wang 443, Suzuki [32], Liu et al. (25) and show that neural networks can be used to approximate polynomial functions, including B-spline basis functions and the distance function. The key technique to use neural network approximate square function and multiply
function [3]. The detail is deferred to the appendix. Specifically, [emma F.3 proves that neural network with width w (dd)) and depth L can approximate B-spline basis functions, and the error decreases exponentially with L; Similarly, Prrppsition C.3 shows that neural network with width w ODD can approximately calculate the distance between two points dl (2; c). with precision decreasing exponentially with the depth.
Step 4: Use ConvResNeXI to Approximate the target function. Using the results above, the target function can be (approximately) decomposed as
CM
P
Ki,ky,ng Mm,k, ss o o x 1(x E B(c,r)).
We first demonstrate that a ReLU neural network taking two scalars a, b as the input, denoted as axb, can approximate x 1(x E Br where x satisfy that y = for all y, and y = 0 if any of x or y is 0, and the soft indicator function i(x E Br,;) satisfy i(x E Br = when B,,.. and ( E Br,)) = O when x & BT The detail is deferred to Section
Then, we show that it is possible to construct MN CMP number of building blocks, such that each building block is feedforward neural network with width Ci + D) and depth L, where m is an integer satisfying 0 a min(m, m 1 1+ I/p). The k-th building block (the position of the block does not matter) approximates oj,ky. Mm.ky.e; Ø; x 1(x E B(c,r)), where = rem(k, N). Each building block has where a sub-block with width D and depth L. 1 approximates the chart selection, sub-block with width md and depth L. approximates the B-spline function, and the last layer approximates the multiply function. The norm of this block is bounded by
i = reiling(k/N).
W 11 S 00222k/4 DL.).
(10)
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 C.6 which shows that any L-layer feedforward neural network can be reformu- lated as an L + Lo 1-layer convolution neural network, the neural network constructed above can be converted into a Cen that satisfies the conditions in Theorem 3.2
4.2 Estimation error
We first prove the covering number of an overparameterized ConyResNeXt with norm-constraint as Lemmaa 4.1 then compute the critical radius of this function class using the covering number as in Corollary E5 The critical radius can be used to bound the estimation error as in Theorem 14.20 in
Wainwright [36.. The proof is deferred to Section D.2
Lemma 4.1. Consider a neural network defined in Definition 2.12
Let the last layer of this neural network is single linear layer with norm | S Bout. Let the input of this neural network

---

satisfy || S 1, Vx, 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 by
log.N(;,8) S w LB K (Bole exp((K Bres/ L)) 1-212 1- 8 11288-1211 277
2/2
(11)
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 c. 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 ||=]|| S 1 is more than 8/2, the covering number of the ConvResNeXt is only determined by the number of "large blocks", which is no more than Byes/C cc
Proof. Using the inequality of arithmetic and geometric means, from Propossiion F.6 Proposition F8 and Proposition F.9 if any residual block is removed, the perturbation the output no more than
L) 1/22 exp((K (re/BBr//) L))
Pm
where B, 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,, < 6 ("small blocks") and Bn 2 ("Marge blocks"). If all the "small blocks" are removed, the perturbation to the output for any input ||al| S is no more than
Σ m:: Bm <t
Pm S exp((K Bress/ L)) ) kL/2 Bres Bul B (c/L)//2-1/I.
1/(L/2-1)
the perturbation above is more than 5/2. The covering number can be determined by the number of the "large blocks" in the neural network, which is no more than Bres/e. As for any block, Bin < Bul? exp( Bres/ 2//2), taking our chosen finishes the proof, where Bm is the upper bound of the input to this block defined in Proposition D.1 and past is the Lipschitz constant of all the layers following the block.
Choosing - (
8L
Remark 4.2. The proof of Lemma 4.1 shows that under weight decay, the building blocks in CentResNeXt are sparse, T.e. only finite number of blocks contribute non-trivially to the network even though the model can be overparameterized. This explains why ConvResNeXt can generalize well despite overparameterization, and provide a new perspective in explaining why residual connections improve the performance of deep neural networks.
Discussions
This paper focuses on developing insightful generalization bounds for the regularized empirical risk minimizer. We opt not to delve into the end-to-end analysis of optimization algorithms in order to explore the adaptivity of complex architectures such as ConvResNeXts, while works on optimization
behaviour of neural networks are limited to simple network structures (88
39 Notably, this approach
to decouple learning and optimization has been widely adopted 3
31
6 25
We made the same
choice in the interest of getting more fine- grained learning theory. However, our paper considers weight decay and overparameterization which are tightly connected to real-world training of neural networks, and can be the most promising work to bridge the gap between optimization and statistical guarantees. We defer more details to the appendix, including discussions on the Besov space and numerical experiments for supporting our theories well as supplementary technical proof.
Acknowledgments
The work was partially supported by NSF Award No 2134214. KZ and YW were with UCSB and MC was with Princeton when the work was completed. YT contributed to the project during his summer 2023 visit to UCSB. We appreciate anonymous reviewers and ACs for their input.
10

---

References
[1] Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over- parameterization. In International conference machine learning, pages 242-252. PMLR. 2019.
[2] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: (.Kiv:/409.000 447,0473, 2014.
[3] A. R. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):93--945, 1993.
[4] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local rademacher complexities. Annals of Statistics, pages 1497-1537, 2005.
[5] L.-C. Chen, Papandreou, Kokkinos, K. Murphy, and A. L. Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE transactions on pattern analysis and machine intelligence, 40(4):834 848, 2017.
[6] M. Chen, Jiang. W. Liao, and T. Zhao. Nonparametric regression on low-dimensional mani- folds using deep relu networks: Function approximation and statistical recovery. Information and Inference: A Journal of the IMA, 11(4)) 2022.
[7] G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
[8] R. A. DeVore and G. G. Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
[9] D. L. Donoho, R. C. Liu, and B. MacGibbon, Minimax risk over hyperrectangles, and implica- tions. The Annals of Statistics, pages 1416-1437, 1990.
[10] D. L. Donoho, M. Johnstone, et al. Minimax estimation via wavelet shrinkage. The annals of Statistics, 26(3):879-921, 1998.
[11] D. Düng. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34 (1):1-41, 2011.
[12] H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3): 418 0984491, 1959.
[13] D. Geller and I. Z. Pesenson. Band-limited localized parseval frames and besov spaces on compact homogeneous manifolds. Journal of Geometric Analysis, 21(2):334-371, 2011.
[14] I. Goodfellow, J. Pouget-Abbale Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.
[15] A. Graves, A.-r. Mohamed, and G. Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pages (645-6649. IEEF, 2013.
[16] S. Gu, E. Holly, T. Lillicrap, and S. Levine. Deep reinforcement learning for robotic manipula- tion with asynchronous off-policy updates. In 20/7 IEEE international conference on robotics and automation (ICRA), pages 3389-3396. IEEE, 2017.
[17] M. Hamers and M. Kohler. Nonasymptotic bounds on the 12 error of neural network regression estimates. Annals of the Institute of Statistical Mathematics, 58:131-151 2006.
[18] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[19] Hu, Shen, and Sun. Squee7e-and-excitati networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 7132-7141, 2018.

---

[20] T. Hu, Z. Shang, and G. Cheng. Sharp rate of convergence for deep neural network classifiers under the teacher-student setting, arXiv preprint arXiv:2001.06822 2020.
[21] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[22] M. Kohler and Krzyžak. Adaptive regression estimation with multilayer feedforward neural networks. Nonparametric Statistics, 17(8):891-913, 2005.
[23] A. Krizhevsky, L. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, pages 1097-1105, 2012.
[24] M. Lee. Riemannian manifolds: an introduction to curvature, volume 176. Springer Science & Business Media, 2006.
[25] H. Liu, M. Chen, T. Zhao, and W. Liao. Besov function approximation and binary classifica- tion on low-dimensional manifolds using convolutional residual networks. In International Conference Machine Learning, pages 6770. PMLR, 2021.
[26] Long, E. Shelhamer, and T. Darrell. Fully convolutional networks for semantic segmentation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3431-3440, 2015.
[27] E. Mammen and S. van de Geer. Locally adaptive regression splines. The Annals of Statistics, 25(1):387-413, 1997.
[28] E. Nichani, A. Damian, and J. D. Lee. Provable guarantees for nonlinear feature learning in three-layer neural networks. Advances in Neural Information Processing Systems. 36, 2024.
[29] P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39:419 4411, 2008.
[30] K. Oono and T. Suzuki. Approximation and conpparaecttic estimation of resnet-type convolu- tional neural networks. In International conference on machine learning, pages 4922-4931. PMLR, 2019.
[31] J. Schmidt-Hieber Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 18:111851897 2020.
[32] T. Suzuki. Adaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality, International Conference on Learning Representations, 2019.
[33] C. Szegedy, S. loffe, V. Vanhoucke, and A. Alemi Inception-v4, inception-resne and the impact of residual connections on learning. In Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
[34] H. Tribel. Theory of function space ii Monographs in Mathematics, 78, 1992.
[35] L. W. Tu. Manifolds. In An Introduction to Munifolds, pages 47-83. Springer, 2011.
[36] M. J. Wainwright. High--Dimnssiona Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/971 108627771.00
[37] S. Wang and Z. Shang. Minimax optimal high-dimensional classification using deep neural networks. Stat, 11()):482, 2022.
[38] S. Wang, G. Cao, 2. Shang, and A. D. N. Initiative. Deep neural network classifier for multidimensional functional data. Scandinavian Journal of Statistics, 50(4):1667-1686, 2023.
[39] Z. Wang, F. Nichani, and D. Lee. Learning hierarchical polynomials with three-layer neural networks. In International Conference Learning Representations, 2024.
12

---

[40] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492-1500, 2017.
[41] D. Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-18 114, 2017.
[42] T. Young, D. Hazarika, S. Poria, and E. Cambria. Recent trends in deep learning based natural language processing. IEEE Computational Intelligence Magazine, 13:55-75, 2018.
[43] K. Zhang and Y.-.. Wang. Deep learning meets nonparametric regression: Are weight-decayed DNNs locally adaptive? In International Conference on Learning Representations, 2023,
[44] Q. Zhang, Z. Cui, X. Niu, S. Geng, and Y. Qiao. Image segmentation with pyramid dilated convolution based on resnet and u-net. Neural Information Processing, pages 364-372. Springer, 2017.
13

---

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 [0, 1]. We also introduce the so-called Total Variation class which sandwiched in between Besov = 1,4 = 1) and Besov (p = 1, oo).
Holder class functions satisfy (()) < C for all
Sobolev class functions satisfy Jo.1I ( (x) <C
Total Variation class functions satisfy Jo.n (x) <C
The L1 Ll-norm used in defining total variation class makes it the most flexible of the three. It allows functions with a order derivative fz)(() to be very large at some places, c.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 C Sobolev C 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, has the same minimax rate of (2a)/(2a+d)) the smaller Holder and Sobolev class.
new perspective on overparameterizet NN. We study the adaptivity 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 9 TO], all kernel ridge regression
including any NTKs will have a suboptimal rate lower bounded by n 2n_d To say differently, there is 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.
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 kemel-based approaches.
We believe this offers perspective understand overparameteriiztion and is more fine-grained that NTK.
B Numerical Simulation
In this section, we validate our theoretical findings with numerical experiments. We focus on nonparametric regression problems for simplicity and consider the following function fo RDD 4 R:
fo(x) fo(Ux)) To(ā)
where U E DxD is andomly-chosse rotation matrix and ā Ux Rd satisfies that for t e [0, 1], the first three coordinates
3 f sin(4 52 coss(4t)) Σ3 = t(1 t).
and the remaining coordinates of ā are irrelevant features iid sampled from uniform distribution. Note that the first three coordinates of ă are completely determined by a scalar t, and the corresponding label y is determined by t via piecewise linear function, i.e., for bag of f1. fi....,t, tn [0, 1]. we can generate a labeled dataset by = go (t,) + (O, 1). An illustration of the function fo is given in Figure 2 where colors indicate the value.
Role of irrelevant features and rotation. The purpose irrelevant features and rotation make the problem harder and more interesting.
14

---

7.5
0.25
2.5
0.0
1.00
04
6.25
92
-5.0
0.00
-0.5
04
-0.30
20.
-7.
Figure 2: Illustration of Besov function on 1-dimensional manifold embedded in 3-dimensional ambient space.
21, = t, sin(Arte), 01,2 = t, cos(4At)), 21,3 = t,(1 t,),
where 4, i 1,.... evenly spaced over (0, 1]. This process generates I 1-dimensional manifold in I which does not intersect with itself, as shown in Figure
Baseline methods To estimate the underlying function with CextRsss (this paper), as well as a mix popular off-the-shelf methods including kernel ridge regression, XGBoost, Decision tree, Lasso regression, and Gaussian Processes.
manifold, conducted experiments
Hyperparameter choices. In all the experiments the following architecture was used for PNN: = 6, L = 10, M = 4, batch_sipp size = 128, Icarning_ran rate 1c 3
In all the experiments the following architecture was used for ConvResNeXt: = 6, K M = 2, N 2. Batch_size and learning_rate were adjusted for each task.
For off-the-sheef methods, their hyperparameters are either tuned automatically or avoided using tools provided from the package, c.g., GP. For GP, a Matern kernel is used, and for ridge regression, the standard Gaussian RBF kernel used.
Results. Our results are reported in Figure function of the effective cofrree-offfeeedee of each method, ambient dimension D and also the number of data points respectively.
which reports the mean square error (MSE) as
As we can see in Figure 3] Nes able to achieve the lowest MSE at a relatively smaller degree of freedom. It outperforms the competing methods with notable margins despite using simpler hypothesis.
Figure Iillustrates that standard non-pann non-parametric methods such 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-independerr due to the representation learning that helps identify the low-dimensional manifold.
Finally, the log-log plot in Figure 5 demonstrates that there is 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.
15

---

dof Vs mse
lasso regression kemel decision tree sgboest
9P
500
1000
1500
2000
Figure 3: MSE as function of the effective degree of freedom (dof) of different methods.
ze graicason indgg aighoos @p Cettereteett
Nighoost
Dkmondaoon
Number
Figure 4: MSE function of dimension D.
Figure 5: MSE function of sample size
C Proof of the approximation theory
C.1 Decompose the target function into the sum of locally supported functions.
Lemma C.1. Approximating Besov function on a smooth manifold using B-spline: Let f E B (M). There exists a decomposition of f:
CM f(x) Σ foo(()) x 1(x E B(c,r)),,
and J. = Pt Bp.q B(c,rr) r) denotes the unit ball with radius r and center C,.
(M)) di M Rd are linear projections, [[ B
The lemma is inferred by the existence the partition unity, which given in Proposition 2.6
C.2 Locally approximate the decomposed functions using cardinal B-spline basis functions.
Proposition C.2. For any function the Besov space on a compact smooth manifold f E BiggM) any N 2 0, there exists an approximated to f using cardinal B B-spline basis functions:
Cs
P
aikky,a Mm , ob 1(x B(c,T)),
16

---

where m is the integer satisfying 0 < min(m,m- 1/p), Mm,ks = Mm (2 8)), Mm denotes the B-spline basis function defined [2] the approximation envor is bounded by
|lf - flloo S CaCMP~oja
and the coefficients satisfy
11 Kikk, hellp S Ciollfll
for some constant Cg. Cio that only depends
As will be shown below, the scaled coefficients 2 di,k,, corresponds to the total norm of the parameters in the neural network to approximate the B-spline basis function, so this lemma the key to get the bound of norm of parameters in (12)
Proof. From the definition of Bp.g (M), and applying Proposition 2.6 there exists a decomposition of f as
CM
CM
Σ (f.)
Σ oo x 10:
where fi : f" Pe. Ps satisfy the condition in Definition 2.5 and fo 0, p.g- Using Proposition F.2 for any one can approximate fi o; with ft:
f. Σ , B, Mm,k, 8, j=1
such that 1, S C o/d and the coefficients satisfy
|| ak 23 Islle Ciollft or 11gg.
Define
CM Jo 1u.
one can verify that ||ʃ - Álloo S N-CCM On the other hand, using triangular inequality (and padding the vectors with 0),
CM
CM
( ky,yy higlpp $ >
11 a a bilp -
Ciol life o 0, 1 = -Ciollf"Ilngg (M))
which finishes the proof.
C.3 Neural network for chart selection
In this section, we demonstrate that feedforward neural network can approximate the chart selection function (ax B(c,r)), and is error-free as long as z 0 when r < d(x, c.) We start by proving the following supporting lemma:
Proposition C.3. Fix some constant B > O. For any x, E RD satisfyüng |r: < B and [cs1 S B for i= 1, D, there exists an L-luyer neural network d((x; c) with width Od) that approximates d c) Eb (x, c;)2 such that (d
d2 e) 8DB2 exp(- with an absolute constant Cn > 0 when d( xx; c) < J, and d' d(x;c) 2 7² when d(x; c) 2 т, and the norm of the neural network is bounded by
We |bbl < CtzDL.
17

---

Proof. The proof is given by construction. By Proposition 2 in Yarotsky(2017), the function f(z) x² on the segment [0, 2B] can be approximated with any error e 0 by a ReLU network g having depth and the number of neurons and weight parameters no more than clog( (4B²/4 /t) with absolute constant c. The width of the network g an absolute constant. We also consider a single layer ReI.U
neural network htt) (t) - a(-)), which is equal to the absolute value of the input.
Now we consider neural network G(æ;c) Ei=1g y h(r; c). Then for any a, E R satisfying x & B and |c|| < for I,.... D, we have
D go h(r; -G) Σ
[G(z; c) - d(<xc)) s
Σ
(x; ci)
i=
i=1
$
g h(r, -4) - -sx; (
$ DE.
Moreover, define another neural network
F(x;;) = -0 - De - G(;-e();))) + +
G(x;;) + De if G( c) < - -De,
72
if Gf; c) 2 2- De,
which has depth and the number of neurons no more than /' (oo((4////)) /e) with an absolute constant e/. The weight parameters of G are upper bounded by max(7? De, clog 4B² 4B3/ and the width of G is O()).
If (x; < <2, we have
F((;;) -(x,e)==|- o(7² De G(x; c)) --,((z;))
((r;:c) d(x;;)) + Del if c) < De, if 2 De.
-d((x;))
For the first case when G(æ; c) < 7² De, c( (x c)l < 2De since dl c) can be approximated by G(æ; c) up to error For the second case when G(æ; c) 2 T² De, we have
d(x;c) 2 G(æ:c)- - De 2 T2 2D and Thereby we also have [F(x; c) - d' c)l $ 2Dc.
If df; > 72 instead, we will obtain G( 2 (x;;)) De 2 T2 De. This gives that F(x;
in this case.
Finally, we take c = 4B2 (L/c' Then F(x;;) is an I-layer neural network with O(L) neurons. The weight parameters of G are upper bounded by max(72, 4DB² (sp)) cL/c) and the width of G'is O(D). Moreover, F(x; c) satisfies |F ((;;e) c) - df (x; < 8DB expl L//c)
if dR e) S 7² and F(x;;) c) 72 if dx; C) 2 72.
Proposition C.4. There exists single layer ReLU neural network that approximates x, such that for all 0 < x < C.y E (0. 1), a xxy when 1, and xxy = 0 when either x = 0 or y = 0.
Proof. Consider single layer neural network g(x, y) A2d (A1 T) with bias, where
A2 = [
A
Then we can rewrite the neural network g as g(r,y) = Co(-z/CC + + Coly). If =
we will have g( v) = -Ca(-I/C + 1) + C I, since S C. If 0, we will have g(a, y) = - Ca(-2/C) = 0, since r 2 0. Thereby we can conclude the proof.
By adding a single linear layer
1
y R-r-2 21
(a
A x) o(r + A -)))
18

---

after the one shown in Proposition C.3 where A - 8DB² exp(-CL) denotes the error in Proposi tion C.3 one can approximate the indicator function 1(x r)), such that error-free when d(n, C:) < r or 2 R. Choosing R < T/ / R 2A, and combining with Proposition C.4 the proof finished. Considering that fi is locally supported on B(c,,7) r) for all by our method of construction, the chart selection part does not incur any enror in the output.
C.4 Constructing the neural network to Approximate the target function
In this section, focus the neural network with the same architecture as a ResNeXt Defini- tion 2.12 but replacing each building block with feedforward neural network, and prove that it can achieve the same approximation error as in Theoremm 3.2 For technical simplicity, assume that the larget function f [0, 1] without loss of generality. Then our analysis automatically holds for any bounded function.
Theorem C.5. For any f under the same condition as Theorem 3.2
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:
M
M
f Wout
(1+
Σ fN.m
o...0
1+1
Σ
fi.
m==
m=1
fn.m w (Woo
(22,)) L-1
(W)) (n.m))
x)) P(x),
where P(x) = [x"" 1, 1, is the padding operation, satisfying
MN 2 CMP,
w 2 C1(dm + DD,
M L
Bres ΣΣΣ
W mm))
11 1
C2L,
(12)
Bout == || out 11? I C3C7((dm + (C,)
there exists an instance f of this ResNeXt class, such that
|l 1 S CFCM (Cap-a/a + Cs exp((CoL log where C1, C2, O3 C4, Cs, Co are the same constants as Theorem 3.2
(13)
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 the first step, and finally transform this parallel neural network into the ConvResNeXi as claimed.
Combining Lemma F.3 Proposition C.3 and Proposition C.4 by putting the neural network in Lemma F.3 and Proposition C.3 in parallel and adding the one in Proposition C.4 after them, one can construct a feedforward neural network with bias with depth L. width w O(d) + O(D) (d). that approximates Mm,k,.a, (x) x 1(x E B(),,r) for any i,j.
To construct the neural network with residual connections that approximates f", follow the method in Oono and Suzuki [30], Liu et al. [25]. This network uses separate channels for the inputs and outputs. Let the input to one residual layer be y1), the output is [æ1, 91 (xx)) As 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 also scaled by a. This property allows block while keeping the model equivalent. To compensate for the bias term, Propositton F.4 can be applied. This only increases the total norm of each building block by no larger than constant term that depends only L, which is no more than a factor of constant.
scale the weights in each building
Let the neural network constructed above has parameter w (1.5) layer, one can construct building block without bias
b
((.)))
6
(15) in each
w (J))
w
(4d)
(b.f)
0
(1.)
W
b
(3,5)
W
0
W
(1,)
19

---

Remind that the input is padded with the scalar before feeding into the neural network, the above construction provide an equivalent representation the neural network including the bias, and route the output to the last channel. From Lemma F.3 bounded by (10)
it can be seen that the total square norm of this block
Finally, we scale the weights in the each block, including the "1" terms to meet the norm constraint. Thanks the J-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 Bies and Bou. If all the weights in the residual blocks are scaled by an arbitrary positive constant c, and the weight in the last layer W is scaled by c 7. the model is still equivalent. We only need to scale the all the weights in this block with [0i.ky.s, 1//2 setting the sign of the weight in the last layer as sign(a;,,,, .,),, ) and place CMP number of these building blocks in this neural network with residual connections. Since this block always output 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 to
W out = 00...., O, 1], bout = 0.
Combining Proposition F.2 and Lemma F.1 the norm of this ResNeXt we construct satisfy
Cm P
Byes 5
2/L. 1,kj,0;
(22h/ C15dmL+ C12DL)
CM
P
22 Ki
+ C12DL)
$ (CmP)1 2/ //bb) 111" ,,, (Crdm C12DL)
< (C/ 1-2/-///pp 2/( +
Bout 1
By scaling all the weights in the residual blocks by B and scaling the output layer by B the network that satisfy (12) can be constructed.
Notice that the chart selection part does introduce error by our way of construction, we only need to sum over the error in Sc and Section 4.1 and notice that for any for any linear projection oi, the number of B-spline basis functions Mm.k. that is nonzero on æ is no more than md log P. the approximation error of the constructed neural network can be proved.
C.5 Constructing a convolution neural network to approximate the target function
In this section, we prove that any feedforward neural network can be realized by convolution neural network with similar size and norm of parameters. The proof is similar to Theorem 5 in (30].
Lemma C.6. For any feedforward neural network with depth L', width w', input dimension h and output dimension h', for any kernel size K > L. there exists a convolution neural network with depth
L = L' Lo 1, where Lo k-1 number of channels the oulput equals the output of the feedforward neural network for all inputs, and the norm of the convolution neural network is bounded as
4w', and the first dimension of
Σ DIWile
S
Σ t=1
Wi + 4w' To:
Rw'xw', 2 1 1; W RR'''' are the weights in the feedforward neural network, and W1 kxxxh We R kxxx 2,..,, 1; W;W g xhxw are the weights in the convolution neural network.
where Wi E Re R W
Proof. We follow the same method as Oono and Suzuki 30 to construct the CNN that equivalent to the feedforward neural network. By combining Oono and Suzuki [30] lemma I and lemma 2, for
20

---

any linear transformation, one can construct a convolution neural network with at most Lu = A=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 than
Lo
Σ WI S 4Lo.
(14)
A=1
where We is the weight of the linear transformation. Putting number of such convolution neural networks in parallel, convolution neural network with Lo 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 We+Lo-1(:,,. [O....: [i], ................................ 0j. A1 I i,j w, and pad the remaining parts with such that this con- volution layer is equivalent to the linear layer applied on the dimension of channels. Noticing that this conversion does change the norm of the parameters in each layer. Adding both sides of by the norm of the 2 - L' layer in both models finishes the proof.
D Proof of the estimation theory
D.1 Covering number of neural network block
Proposition D.1. If the input to a ReLU neural network is bounded by || S B the covering number of the ReLU neural network defined in Prropostiin F.6lis bounded by
Bin (in(B/BB (B/BB/)) (B
w²t
N(FFN, 8, 11
8
only consider the case Well S BBTT. For any 1 < f S L, for any W1,- W Wi-1. 1, We, v,, Wg W..,,.. W, that satisfy the above constraint and [W:
Proof. Similar Proposition F.6,
define (-..; W1.... WL) the neural network with parameters W WL, - -Willr S e,
(>; Wi,... We-1, We, Wet1... WWE) g( WT,.. We-1, We, We+t.... Wz)lla (c))(W(()))Ilz
$ (B/L)
(B/L) Bm...
Choosing 6 = T(B/EJLL 1172, the above inequality is no larger than 5/T. Taking the sum over f, we can see that for any W1, Wi..... WZ, Wi, such that || WillF S 6,
11,(;; W1,.. ... WL) g(æ; W W2)) s Finally, observe that the covering number of W, is bounded by
w²
2Bw
N(W
||]|| < e) 1|- (1e)
(15)
Substituting B and and taking the product over finishes the proof.
Proposition D.2. If the input to a ReLU convolution neural network is bounded by || ll2 S B the covering number of the ReLU neural network defined in [S] bounded by
w² W²KL
Biu (KKL) wL
N(FNN, 8, 1112) S
8
Proof. Similar to Proposiiion D.I for any 1 S f < L, for any Wi..., W.-1. We, W/. We+1.... WL that satisfy the above constraint and ||We W/llp S e, define g(...; W1.... WL) as the neural network with parameters Wi.... WL. we can see
(0 W,.... "......W..... We, We41....W - g(: WT, We-1, We, Wet1,... Wz)lla k2 (B/))((B))
... (=))
< (B3)
21

---

where the first inequality comes from Proposition F.10 Choosing k Br, L(BLLLBBBLB))) ((B) the above inequality no larger than 6/L. Taking this into (15) finishes the proof.
D.2 Proof of Theorem 3.3
Define f = arg y Ep [C()]. From Theorem 14.20 in Wainwright [36], for any function class OF that star-shaped around f. the empirical risk minimizer arg yer (f() satisfy
Ex([(ʃ)) < [D(((}) 105, 5,,)
(16)
with probability at least 01 exp(-c2n0)) for any 6n that satisfy (20) where C₁ 0g are universal constants.
The function of neural networks is star-shaped, but can be covered by star-shaped function class. Specifically, let {f f E FComy {fi f2 f1, f2 FCooy) == OFF
Any function in 0J can be represented using 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, Bres and Bout by factor 2. This only increases the log covering number in by factor of constant (remind that Bres
(1) by assumption).
Taking the log covering number of the ResNeXt (TI) the sufficient condition for the critical radius as in (20) is
1-8/C
n 1/2 w/ 1/2 B2- K 2/2 (Bou exp( Bres/ L) LT).12)) I 27L on
2--
A
4
(17)
6n 2 K (w² L) م Bres Br (B exp((K 1/2))
1/2 1-1/6 n
ト/
where S hides the logarithmic term. Because C is I-Lipschitz, we have
+ I| 81xx-
Choosing
1-
K 1-2
2a 20/d(1 1/2)
P=O
and taking Theorem 3.2 and (17) into (16) finishes the proof.
E Lower bound of error
In this section, we study the minimax lower bound of any estimator for Besov functions on d- dimensional manifold. It suffices consider the manifold M as d-dimensional hypersurface. Without the loss of generalization, assume that acizl space
> 0.5 for e S y S e. Define the function
By
x M( ((x (((o--j)1 -1)ss) }
F
E
f-
ع Ji....ja=1 sa
Σ
(18)
where (m) denotes the Cardinal B-spline basis function that is supported on (), [j]]. The support of each B-spline basis function splits the space into s 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= Using Düng for any f F.
||| Theorm 2.2], we can see that
| |
& e a-d/v d/p dir =c.
so
For fixed f E F, let D {(x,, y 1 be set of noisy observations with yı fxx, +1, SubGaussian o² I)). Further assume that æ; are evenly distributed in (0, 1)d such that in all
22

---

regions as defined in (18) the number of samples is ny == (m//s"). Using Le Cam's inequality, we get that in any region, any estimator satisfy
sup ED]1(((D) 1'1 Cm JEF
16sa
as long as (050) ? block indexed by i, Om is constant that depends only on m. Choosing (( we get
sd n. where || 111=== S
1 E -=<=--))e [e [f())
denotes the norm defined in the
ni
sup ED(l0(D) [*1b]] 20rn -E
Observing 1 E. (2)) If(x)) f ~ ts EyEloe Ilf 11f--f1) f"1 finishes the proof.
Supporting theorem
Lemma F.1. (Lemma 14 in Zhang and Wang (43)] For any E RM 0 <d < it holds that:
Bally S M /p |aal
Proposition F.2 (Proposition 7 in Zhang and Wang 43 Let d/p 1,r > For any function in Besov space f E Bp.q and any positive integer M, there is an M Mssparee approximation using B-spline basis of order m satisfying O < < min(m, m - 1 + 1/p):
-M f' - ak,,; k, a for any positive integer M such that the approximation error is bounded as [ f'1lo S M- M-aa/d ( (lBg. and the coefficients satisfy
11 ak &e 11p S |1
Lemma F.3 (Lemma 11 in [43] Let Mm.k.a be the B-spline of order m with scale 2 k in each dimension and position Rdd am.k.a Mm. (2 (a: - =)), Mm is defined in (2) There exists a neural network with d-dimensional input and one output, with width wd.m = O(dm) and depth Z log(C1a/e) for some constant C13 that depends only on m and d, approximates the spline basis function Mm.k..(x)) = Mm M2 (2 s))). This neural network, denoted as Mm.k. x Rd..
satisfy
Mm.k.e Mm,k. (2)) S e, if0 2* -4) S 5m++1 <m+1,iied
(m) 0,, otherwise.
The total square norm of the weights is bounded by 22k/L C dradmL for some universal constant Cin-
Proposition F.4. For any feedforward neural network with width and depth T. with bias, there exists a feedforward neural network f' with width w' = 10 + and depth L' L,, such that for any x, f(x)= = ['( ,1]²)
Proof. Proof by construction: let the weights in the f-th layer in f be We, and the bias be be, and choose the weight in the corresponding layer in be
W
b 1
W
v4
< L; W = [W bz].
The constructed neural network gives the same output as the original one.
Corollary F.5 (Corollary 13.7 and Corollary 14.3 in Wainwright [36]). Let
G.,55, F) = Em,; sup gEF.llsl
wig(an ai))
R., (6, E.;
sup gEF.llall.
55
72
23

---

denotes the local Gaussian complexity and local Rademacher complexity respectively, where ~ (O 1) are the i..dd Gaussian random variables, and e u | are the Rademacher random variables. Suppose that the function class F is star-shaped, for any >> 0, any E (0, a) such that
16 6n
8²
VlogN(FF 14, 110 )d -
V1i 8,/40
40
satisfies
Fn S 8²
(19)
20 Furthermore, F is uniformly bounded by b, i.e. Aʃ E F, a: a(f(a)) s < <baay 8 > 0 such that
64 A
8
Vlog 14, 11x S
vn 62/22010
satisfies
8²
(,,
(20)
Proposition F6. An L-layer ReLU neural network with no bias and bounded norm
Σ
Wilk
t=1
is Lipschitz continuous with Lipschitz constant (B/L)
Proof. Notice that ReLU function is I-homogencous, similar to Proposition 4 in [43] for any neural network there exists an equivalent model satisfying |WWlll ||Weell e for any e, f', and its total
norm of parameters is no larger than the original model. Because of that, it suffices to consider the neural network satisfying |Welle S / /B/L L for all f. The Lipschitz constant of such linear layer is |Welll v B/ T., and the Lipschitz constant of ReLU layer is 1. Taking the product
[Welll2 S
over all layers finishes the proof.
L
Proposition F.7. An L-layer ReLU convolution neural network with convolution kernel size K, no bias and bounded norm
We B. Σ
is Lipschitz continuous with Lipschitz constant (K (KB/L)
This proposition be proved by taking Proposition F.10 into the proof of Proposition F.6
Proposition F.8. Let f = fpost o (1 + JNN + fother) fpee be a ResNeXt, where 1 + fNN + fother denotes a residual block, fpre and fpost denotes the part of the neural network before and after this residual block, respectively. JNN denotes one of the building block in this residual block and fother denotes the other residual blocks. Assume Spres JNN, Fpost. are Lipschitz continuous with Lipschitz constant Lxpes LNN, Lipost respectively. Let the inpul be if the residual block is removed, the perturbation to the output is no more than Loy Lpost! x]]
Proof.
|Sost o (1 + fNN + fother) o Spre(x) - Spost o (1 + fother) o Spre
< Lpost (1 + SNN + fother) fpee(x) + fother) fpre(z))
Ippstt JNN o fpre(x))
S Lypre LAN =/11
Proposition F99. The neural network defined in Lemma 4. with arbitrary number of blocks has Lipschitz constant exp( ( [K Bres/ L)2/2), where K = when the feedforward neural network is the building blocks and K the size of the convolution kernel when the convolution neural network is the building blocks.
24

---

Proof. Note that the m-th block in the neural network defined in Lemma 4.1 can be represented
as y fm (x: wm)) + æ. where fm is an L-layer feedforward neural network with no bias. By
Proposition F.6 and Proposition F.7] such block is Lipschitz continuous with Lipschitz constant
1+(BBm/l L2)/22 where the weight parameters of the m-th block satisfy that Σ [[W(m)) | Bm
and Em=1 Bm & Brss.
Since the neural network defined in Lemma 4.1 is composition of M blocks, it is Lipschitz with Lipschitz constant Lyes. We have
M
KBm L
L/2
M
K B L/2
L Tres
II m=1
1
S exp
Σ m==1
L
where we use the inequality - 2 I exp(x) for any E R. Furthermore, notice that
Em=1 (K 2/2 is convex with respect to (B1, B2...... Bar) when L > 2. Since Σ Bm S Bres and Bn 2 0, then we have EnI (K Bm/ L))222 S (K OrresL)//1 by convexity. Therefore, we obtain that Tres I exp(( K /,es/L))//2)
Proposition F.10. For any E R E R K S ||Conv(z, w)ll2 S v K 2 2
Proof. For simplicity, denote x; = 0 for & 0r i d.
||Conv(æ, w)ll
d i= (ali K-1
: 2 k_ w)
< x
K-1 :it K-
w 2
2
< K
where the second line comes from Cauchy-Schwer inequality, the third line comes by expanding
|
K-1 +it K- 1-11l1 by definition and observing that each element in appears at most K
times.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main theories are presented in Section 3. Section 4 presents the proof sketch the main results and highlights our technical contributions.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our work in Section
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are presented in Section We outline the proof sketch in Section 4 and defer proof details to Appendix C, D, E and F.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experiment details given in Appendix B.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Our experiments simulated data and do require any datasets. The experiment implementation is simple and clearly described in Appendix B, so we feel there is need to publish data and code.
Justification:
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We provide our experimental results and details in Appendix B.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars are included in experiments in Appendix B. See Figure 3 for illustration.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
26

---

Justification: Our experiments do not require large compute resources and can be reproduced on laptops.
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp////aaapp...cooa/aai/aaaaaa
Answer: [Yes]
Justification: This research conforms to the NeurlPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
27


Reviews:
[{"review_id": "coeIpVUd0T", "reviewer": "Reviewer_UzhH", "summary": "The paper provide theoretical analysis for the good prediction performance of convolutional residual neural networks, even overparameterized.", "questions": "1. Can you generalize from  the empirical logistic risk to other risks? How will the choice of loss change the bound?\n2. 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": "The analysis is limited to convolutional networks. It's interensting to see if it can be further generalized to other architectures like transformers.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theory they developed with overparamterized ConvResNeXts trained with weight decay is novel. \n2. their theory does not suffer from the curse of dimensionality.", "weaknesses": "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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review the paper. I would like to address the questions you've raised with the following responses.\n\n**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 from?**\n\nThank you for this question. The definition in lines 71-72 is specific to our analysis, not drawn from an existing source. We define overparameterization as 'the number of blocks larger than the order of the sample size' because:\n\n1. It aligns with the general concept of overparameterization in deep learning, where parameters significantly exceed training samples. This concept is central to recent groundbreaking work [1, 2].\n\n2. In our ConvResNeXt setting, each block has nearly constant parameters. Thus, when blocks exceed sample size order, total parameters do too.\n\n3. This definition enables our theoretical analysis of highly expressive models relative to available data.\n\nWhile not a standard definition, it provides a clear, quantifiable criterion for our work on ConvResNeXts. We'll clarify this in our revised manuscript.\n\nReference:\n\n[1] Zhang et al. (2017). Understanding deep learning requires rethinking generalization. ICLR. \n\n[2] Belkin et al. (2019). Reconciling modern machine learning practice and the bias-variance trade-off. PNAS.\n\n**Q1: Can you generalize from the empirical logistic risk to other risks? How will the choice of loss change the bound?**\n\nA1: Yes, our findings generalize to other risk functions that exhibit Lipschitz continuity in a bounded domain with respect to model outputs.  While our paper predominantly uses the logistic loss due to its popularity in classification tasks, our results can be extended to a broader range of loss functions. The statistical rate remains the same, differing only by a constant factor that depends on the Lipschitz constant of the chosen loss. \n\n**Q2: Can you explain in details about the extra effort (underlying theoretical technique) you made in this paper to differentiate from Liu et al. 2021? How do you generalize it to over-parameterized settings and ConvResNeXt?**\n\nA2: Our paper extends beyond Liu et al. 2021 in several key ways. We study overparameterized settings and the more complex ConvResNeXt architecture, allowing for flexible network block design. Unlike traditional approaches as adopted by Liu et. al. 2021, we **avoid cardinality constraints** on block numbers through weight decay training, enabling highly parameterized networks. Our analysis of weight decay's effects (line 254 and Lemma 4.1) shows it induces weak sparsity, where only a finite number of blocks significantly contribute. This allows us to bound complexity in overparameterized ConvResNeXts without explicit structural constraints.\n\nA major theoretical challenge we address is **bounding metric entropy** in complex, overparameterized network settings. We employ an advanced method using Dudley's chaining of metric entropy via critical radius / local Gaussian/Rademacher complexity (Bartlett et al., 2005; see our Corollary F.5, Line 1100, Page 21). These innovations enable us to achieve optimal estimation error for overparameterized ConvResNeXts, extending beyond traditional neural network analysis techniques.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6gLkkYiXmw", "reviewer": "Reviewer_QKy6", "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.", "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?\n2. 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": "See weaknesses and limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and I have enjoyed reading it.\n2. The theory is well-developed and clear.\n3. Good contributions are made to the deep learning theory.", "weaknesses": "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.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review the paper and for your positive feedback. I'm grateful for your engagement and would like to address the question you've raised with the following response.\n\n**Weakness 1: 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.**\n\nWhile our paper focuses on the exact manifold setting for clarity, our data assumptions can be relaxed in two significant ways:\n\n1. Our findings extend to settings where data concentrate on the manifold with orthogonal noise, as suggested by [1].\n\n2. Further, our results apply to data not necessarily near a manifold, but concentrated around a subset of $\\mathrm{R}^D$ with effective Minkowski dimension [2]. In this case, the statistical rate depends only on this effective dimension.\n\nThese extensions demonstrate the broader applicability of our theoretical framework beyond the exact manifold assumption, encompassing more general data structures found in practical scenarios.\n\nReference: \n\n[1] Cloninger, Alexander, and Timo Klock. \"A deep network construction that adapts to intrinsic dimensionality beyond the domain.\" Neural Networks 141 (2021): 404-419.\n\n[2] Zhang, Z., Chen, M., Wang, M., Liao, W., & Zhao, T. (2023, July). Effective minkowski dimension of deep nonparametric regression: function approximation and statistical theories. In International Conference on Machine Learning (pp. 40911-40931). PMLR.\n\n\n**Weakness 2: 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.**\n\nOur paper focuses on **approximation** and **generalization** aspects of overparameterized ConvResNeXts, rather than optimization. We demonstrate that overparameterized ConvResNeXts can adapt to Besov functions on low-dimensional manifolds, achieving near-optimal convergence rates.\n\nWhile optimization is crucial, existing research [1-4] on this aspect is limited to **simpler networks** or specific function classes. Considering optimization for deep networks often leads to NTK analysis, which suffers from the curse of dimensionality as mentioned in Line 260-261.\n\nOur approach, decoupling learning and optimization, follows the tradition of Vapnik, Bartlett, and other learning theorists. It allows for a more fine-grained learning theory, complementing optimization-focused studies. We develop generalization bounds for regularized ERM, explaining how these mitigate **overfitting**. \n\nWe acknowledge that addressing all aspects (approximation, generalization, optimization) for complex networks adapting to Besov functions on low-dimensional structures remains an open challenge. Even so, among all existing works that focus on approximation and generalization, our work is the most closely aligned with real-world practice, considering weight-decay training, overparameterization setting and practical network architectures.\n\nReference:\n\n[1] Nichani, Eshaan, Alex Damian, and Jason D. Lee. \"Provable guarantees for nonlinear feature learning in three-layer neural networks.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2] Wang, Zihao, Eshaan Nichani, and Jason D. Lee. \"Learning Hierarchical Polynomials with Three-Layer Neural Networks.\" The Twelfth International Conference on Learning Representations. 2023.\n\n[3] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"What can resnet learn efficiently, going beyond kernels?.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[4] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"Backward feature correction: How deep learning performs deep (hierarchical) learning.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n\n**Q1: 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?**\n\nA1: Thank you for this insightful question. Our paper focuses on theoretical analysis, demonstrating that representation and generalization abilities are equivalent for increasing either depth ($M$) or width ($N$), given a sufficiently large product $MN$.\n\nOur findings align with experimental observations in Xie et al. 2017 (Table 3,4), where ResNeXts with similar MN values achieve comparable performance. While they noted slightly better performance for networks with more paths, our theory suggests this advantage doesn't stem from improved representation or generalization capabilities, but may instead be related to optimization aspects.\n\n\n**Q2: 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?**\n\nA2: Identity maps address vanishing gradients, enabling deeper networks and easier optimization (Xie et. al. 2017). Multiple CNN blocks allow learning hierarchical features at different scales. While we don't prove their theoretical benefits directly, these components are crucial in state-of-the-art architectures (He et al. 2016, Xie et al. 2017). Our work contributes by establishing a close-to-optimal convergence rate for a setting that closely mimics real applications: practical architectures with overparameterization, training with weight decay, and data exhibiting low-dimensional structures, bridging theory and practical success of these complex structures.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nF2AUZmT3d", "reviewer": "Reviewer_xShA", "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.", "questions": "1)\tThis 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?\n2)\tIn 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.\n3)\tIn 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": "No, authors did not adequately address the limitations of their work, and no potential negative societal impact of their work is identified.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1)\tThe paper shows that for learning Besov functions trained with weight decay out of n samples, the rate of convergence depends only on the intrinsic low dimension enabling the curse of dimensionality.\n2)\tThey also provide a tighter bound for the weight-decayed ConvResNeXt in computing the critical radius of local Gaussian complexity.", "weaknesses": "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. \n2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review the paper. I would like to address the concerns you raised in your review.\n\n**Weakness: The actual benefit of having parallel paths was not addressed fully… In Xie et at 2017, several experimental results focus on the positive effect of having higher cardinality (more multiple parallel paths)... this will limit the capability of the proposed ConvResNeXt over the ConvResNets unline the claimed benefits of the former.**\n\nWe would like to emphasize that our paper focuses on the representation and generalization abilities of overparameterized ConvResNeXts, not their optimization. We demonstrate that **the statistical rate and representation power are equivalent** whether increasing the number of blocks (M) or paths (N), as long as MN exceeds a certain threshold (Theorem 3.3). This novel finding from approximation and generalization theory perspectives explains the practical success of overparameterized ConvResNeXts.\n\nPractical performance involves factors beyond our theoretical scope, including optimization aspects and techniques like layer normalization which are barely considered by theorists. Xie et al. 2017 used FLOPs as a complexity measure, while we consider $MN$ values. Notably, their results showing comparable performance for ResNeXts with similar MN values still align with our findings.\n\nWe acknowledge the potential practical benefits of parallel paths. Our theories suggest this advantage does **not** stem from improved representation or generalization capabilities, but likely from optimization aspects. ResNeXts with more parallel paths may be easier to learn with certain algorithms, but this warrants further investigation. Our approach, decoupling learning and optimization, follows the tradition of Vapnik, Bartlett, and other learning theorists. It allows for a more fine-grained learning theory, complementing optimization-focused studies. We develop generalization bounds for regularized ERM, which address overfitting and potentially unifying optimization and statistical theories in future research.\n\n**Q1: This new architecture introduces significantly more complex nested function form... 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?**\n\nA1: Our paper not only generalizes ConvResNets to ConvResNeXts, but more importantly, we address the ***overparameterization*** regime where parameters can significantly outnumber samples. This contrasts with previous work like Liu et al., which imposes unavoidable cardinality constraints on block numbers, limiting their ability to explain the success of overparameterized networks in practice.\n\nAnalyzing overparameterized ConvResNeXts presents unique theoretical challenges, particularly in ***bounding metric entropy***. We tackle this using an advanced method leveraging Dudley's chaining of metric entropy (via critical radius / local Gaussian/Rademacher complexity, Bartlett et al., 2005; see Corollary F.5, Line 1100, Page 21). \n\nUnderstanding complex networks is inherently difficult. Our theory takes significant steps towards explaining real-world applications, bridging the gap between theoretical analysis and practical success of ***overparameterized*** models. While our bounds don't suggest immediate practical benefits of ConvResNeXts over ConvResNets, they provide crucial insights into the behavior of complex, highly parameterized architectures that dominate modern deep learning practice.\n\n**Q2: 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.**\n\nA2: Our findings differ from previous work like Liu et al. 2021, where network complexity and optimal estimation error required careful bounding of cardinality. In our paper, we don't constrain the number of blocks or paths in ConvResNeXts, thanks to ***weight decay*** training.\n\nWeight decay effectively bounds the weights' norms (line 254). As shown in Lemma 4.1, this induces weak sparsity in ConvResNeXt architectures, where many blocks have negligible influence on the network output post-training. Consequently, only a finite number of blocks with significant weight norms contribute meaningfully, allowing us to bound the complexity of overparameterized ConvResNeXts.\n\nThis approach enables us to achieve optimal estimation error **without** explicit constraints on network structure. We'll elaborate on the benefits of weight decay in our revised version.\n\n**Q3: In Sec 3.2, the tradeoff between width and depth was mentioned to be less important in ResNext... 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?**\n\nA3: Our analysis shows that the arrangements of blocks ($M$) and paths ($N$) don't affect the representation and generalization ability of overparameterized ConvResNeXts, as long as their product ($MN$) remains sufficiently large. Theoretically, this is because:\n\n1. ConvResNeXts with the same MN have equivalent representation power, regardless of M and N arrangements.\n\n2. These arrangements don't significantly influence network complexity or generalization capability.\n\nOur findings suggest that an equivalent model without parallel paths could achieve similar ***representation*** and ***generalization*** results. However, practical performance also depends on optimization aspects, which our paper doesn't address directly.\nOur work provides valuable insights into approximation and generalization that can't be obtained solely from an optimization perspective.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ntgOSi42pt", "reviewer": "Reviewer_giSF", "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\ndimensionality.", "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.\n\nI 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": "NA", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This is an excellent, novel and strong work. The paper provides theoretical guarantees for the ConvResNets in the setting of nonparametric classification. The minimax optimal rate under ConvResNets has been an open problem which was successfully resolved by the authors in the conditional class probability.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review the paper and for your positive feedback. I'm grateful for your engagement and would like to address the question you've raised with the following response.\n\n\n**Weaknesses: Literature review is not sufficient. Minimax optimal nonparametric classification using DNN has been recently studied by other authors, though the current paper considers another novel neural network, the ConvResNets, which is different from the traditional DNN.**\n\nDue to space limits, we are only able to briefly mention the existing literature on FNNs/DNNs in Line 23-26. We will add more details of literature in the next version. \n\n\n**Q: 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 rate under (2) has been recently established for ultrahigh-dimensional case for DNN classification by Wang's work… 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.**\n\nA: Thank you for the reference [1] and your insightful question! You are correct that our paper focuses on the setting of smooth conditional class probability (2), with a fixed manifold dimension. We will add further discussions about [1] in our next version.\n\nThe ultrahigh-dimensional case would be an interesting extension of our work! Regarding the specific Wang’s paper you mentioned, we’re currently reviewing [2] and [3] as they appear relevant. While neither paper explicitly defines \"ultrahigh-dimension,\" [3] characterizes it as a scenario where the dimension $D$ grows at a non-polynomial rate relative to the sample size $n$, though it does not establish a minimax convergence rate. Our statistical rate avoids exponential dependence in $D$. However, to achieve a convergence rate that logarithmically depends on $D$, additional assumptions on input features are required, such as having only a small fraction of the variables active for the outputs.\n\nWe would greatly appreciate any further clarification on the reference and the definition of ultrahigh-dimension. We are eager to delve deeper into this topic and discuss it further.\n\nReference:\n\n[1] Kim, Yongdai, Ilsang Ohn, and Dongha Kim. \"Fast convergence rates of deep neural networks for classification.\" Neural Networks 138 (2021): 179-197.\n\n[2] Wang H, Jin X, Wang J, Hao H. Nonparametric Estimation for High-Dimensional Space Models Based on a Deep Neural Network. Mathematics. 2023; 11(18):3899. \n\n[3] Li, K., Wang, F., Yang, L., & Liu, R. (2023). Deep feature screening: Feature selection for ultra high-dimensional data via deep neural networks. Neurocomputing, 538, 126186.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper 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.
Decision: Accept (poster)