How many samples are needed to train a deep neural network?
Authors: Pegah Golestaneh
Mahsa Taheri
Johannes Lederer
Venue: ICLR 2025 Poster (2025)
Keywords: Neural networks
Deep learning
generalization error
information theory
mini-max bound
learning theory
Primary area: learning theory
TL;DR: This paper studies the question of how much data are needed to train a ReLU feed-forward neural network.

Abstract: Even though neural networks have become standard tools in many areas, many important statistical questions remain open. This paper studies the question of how much data are needed to train a ReLU feed-forward neural network. Our theoretical and empirical results suggest that the generalization error of ReLU feed-forward neural networks scales at the rate $1/\sqrt{n}$ in the sample size $n$-rather than the "parametric rate"  $1/n$, which might be suggested by traditional statistical theories. Thus, broadly speaking, our results underpin the common belief that neural networks need "many" training samples. Along the way, we also establish new technical insights, such as the first lower bounds of the entropy of ReLU feed-forward networks.

Published as a conference paper at ICLR 2025
HoW MANY SAMPLES ARE NEEDED TO TRAIN A DEEP NEURAL NETWORK?
Pegah Golestaneh, Mahsa Taheri & Johannes Lederer
Department of Mathematics, Computer Science, and Natural Sciences University of Hamburg
(pegah. golestaneii mahsa. taheri, johannes ledelerdrrrr -eanuuuuuuuuuuggggauaueeuuu
ABSTRACT
Although neural networks have become standard tools in many areas, many impor- tant statistical questions remain open. This paper studies the question of how much data are needed to train ReLU feed-forward neural network. Our theoretical and empirical results suggest that the generalization error of ReLU feed-forward neural networks scales at the rate 1/vn. in the sample size n-rather than the "paramet- ric rate" 1/n,, which could be suggested by traditional statistical theories. Thus, broadly speaking, our results underpin the common belief that neural networks need "many" training samples, Along the way, we also establish new technical insights, such as the first lower bounds of the entropy of ReLU feed-forward networks.
INTRODUCTION
Neural networks have ubiquitous applications in science and business (Goodfellow et al. 2016 Graves al., 2013 LeCun al. 2015 (Barrinarayanan al. 2017). However, our understanding of their statistical properties remains incomplete. For example, a basic yet very important open question is: how many training samples are needed train a (non-linear) neural network?
Over the past two decades, significant progress has been made deriving upper bounds for the generalization error of neural networks (Anthony & Bartleti 2009 Arora al.] 2018:: Yarotsky| 2017
Nagarajan & Kolter 2019). Works likehaabbbbur et al. 2015); Bartlett et al. (2017); [ al. (2017] 2018) first highlight the relationship between the complexity of the network space and the generalization eтrоr and then, they bound the corresponding complexity measure. For example, Neyshabur et al. (2015) study the growth of the Rademacher complexity of classes of 4-- constraint neural networks. Additionally, generalization error bounds for networks with spectral norm constraints are proposed by Neyshabur et al. (2018) (employing a PAC-Bayesil framework) and Bartlett et al. (2017) (employing margin-based framework) for Lipschitz activation functions. common limitation of the works mentioned above is that their generalization bounds often exhibit strong dewendence-freeueeeeee
exponential-an either the depth width of the network. Golowich jtt (2018) address this by providing bounds that avoid direct dependence on network depth for norm- constrained neural networks, with rates that grow only polynomially in depth. More recently, Taheri et al. (202T 2022); Mohades & Lederer 2023): Lederer (2023) have proposed generalization bounds for regularized neural networks that show logarithmic growth in the total number of parameters, with the potential to decrease with additional layers, in contrast to exponential growth. For example, (Taheri al. (2021) provides an upper bound for the generalization error of & reeguurard bewwffowwrrd neural networks for general activation functions growing by (L/2)1/2-1 /log( (Pog()) /n). where P corresponds to the total number of parameters in the network, L. is the number of hidden layers, and n is the number of training samples.
While works mentioned above target to upper bound the generalization error of neural networks, another line of research study lower bounds for the mini-max risk of neural networks a parametric setting. The central question here is if improving the rate 1/vri is possible for neural networks in general or not. Klusowski & Barron (2017) provide a mini-max max lower bound for shallow neural networks with Sinusoidal activation, assuming input vectors are uniformly distributed across [-1, 1]d that decays as 1/vn. Du et al. (2018) provide a mini-max lower bound for a CNN with linear activation, where the input domain normally distributed with mean of ( and identity covariance

---

Published as a conference paper at ICLR 2025
matrix. They also determined the sample complexity for convolutional neural network with linear activation functions and asserted that tackling the challenges posed by non-linear activation functions, without convolution structure, remains difficult task.
To make it short, to the best of our knowledge, a mini-max lower bound for deep feed-forward neural networks with non-linear activation functions that match upper bounds have not been established. In this paper, we use a technique from information theory known as Fano's 's inequality to establish such a bound. Our bound scales as /log(d)/n /n (with n as the number of training samples and d as the input dimension) that matches the mehoteementooeed upper bound rate in Taheri al. (202I). We also confirm this rate in several applications for both regression and classification tasks. Thus, we demonstrate that the minimum number of samples needed to train a neural network to achieve prediction error 2² essentially scales as in our proofs is establishing a sharp lower bound for the packing number of deep ReLU neural networks, which, to the best of our knowledge, is being extracted for the first time in our paper (see Lemma 3.2
rathee than 1/c². One of the main challenges
Our key technical contributions are:
1. We establish a mini-max lower bound for the risk of ReL.U ferd-fo networks that depends the input dimensions only through a logarithmic factor and the level of sparsity of the parameter space. The bound decreases as 1/ vn with the number of training samples n, which matches recent upper bounds. is also important to note that the rate of 1/2 in the exponent remains the same across various input dimensions and network configurations (Theorem 2.2).
2. We support this theoretical bound empirically, also beyond feed-forward settings to include CNNs (Section
3. We establish a lower bound for the packing number of deep ReLU networks' spaces
(Lemma 3.2
The main broader implication as follows:
Most practitioners are convinced that deep learning requires "more" data than classical methods. It is well-known that the accuracy of classical methods, like the least- squsr-suures estimator in linear regression, scale like 1/n in the sample size (Wainwright, 2019 Guol ct al. 2024). Our mathematical proof along with the numerical illustrations showing that this is not the case for (non-linear deep learning, are arguably the first confirmation and underpinning of the mentioned practitioners' belief.
More generally, the paper provides rigorous mathematical perspective important aspect of deep learning to complement the much more abundant "engineering perspective" the field. We will come back to the relevance of this perspective in the conclusion section (Section 6).
Other related works: In addition to the aforementioned works, a growing body of research has
emerged focused employing deep ReLU networks to approximate non-parametric regression
& Bos) 2022 Raskutti al. 2012 Schmidt-Hieber 2020 Zhang & Wang 2023 Tsuji (021)) These models
models (Suzuki 2019 Parhi & Nowak 2022 Raskutti et al. 2009; Schmidt-
are characterized by sparse additive structures and specific smoothness properties, such as Hölder,
Besov, or Sobolev functions. These studies investigate the approximation capabilities of deep ReLU networks for non- non-parametric regression functions by establishing mini- max optimal rates. is crucial consider that their mini-max lower bounds for the function classes degrade either with the depth of the network or with the parameters of smoothness.
In this paper, our perspective differs slightly from that of others, such as Schmidt Seamidd--Hieber (2020). as we view deep ReLU networks as fundamental functions of interest in their own right, rather than as approximation methods for other function classes. We explore the statistical properties of deep ReLU networks by establishing mini-max lower bound for these networks. In contrast, they emphasize the distinction between function classes and approximation methods and aim to confirm the superiority of deep learning to other representative methods like wavelet transforms, kernel methods, and spline methods in -arameeeettic settings. Saatings,,cchmit-HHie [Schmidt-Hieber (2020) shows that sparse deep neural networks with ReLUU activation function and well-designed architecture achieve the
2

---

Published as a conference paper at ICLR 2025
mini-max rates of convergence (up to log n-factors) in multivariate non non-parametric regression, under a broad composition assumption on the regression function. They focus on the regression setup and demonstrate that deep ReLU networks can achieve faster rates under hicrarchical composition assumption on the regression function. This assumption encompasses (generalized) additive models as well as the composition models considered in (Juditsky et al., 2009; Kohler & Krzyžak] (017). Furthermore, they demonstrate that, given the composition assumption, wavelet estimators are only able obtain sub-optimal rates. Theoretical analysis in (uzuki (201)) reveals that deep learning with ReLU activation in Besov spaces exhibits superior adaptivity, demonstrating mini-max optimal rates and outperforming non-adaptive estimators such as kernel ridge regression. Furthermore, the study highlights deep learning's s ability to mitigate the curse of dimensionality in mixed smooth Besov spaces, emphasizing its high adaptivity and effectiveness as a feature extractor in capturing the spatial inhomogeneity of target functions. Imaizumi & Fukumizu (2019) provides comprehensive review of prior research related to function estimation using deep neural networks.
Thus, to the best of our knowledge, our work is the first to illustrate, both theoretically and practically, that in the absence of additional assumptions, the rate of 1/ is the "correct rate" in deep learning. It is important to note that works, such as Schmidt- Hieber (2020), obtain a rate of 1 1/n,, but only under very strict assumptions. For instance, to achieve a rate of I/n in their results, it is necessary to assume that the parameters are bounded by one and the network functions bounded.
Organisation: Section 2 provides the problem formulation and establishes a lower bound on the mini-max risk for ReLU feed-forward neural networks (Theorem [.2]. Section 3 provides some technical results that form our main result's foundation including, a lower bound for the packing number of a ReLU network's space (Lemma 3.2). We provide the proof of our main theorem in Section 4 In Section [S] we shift our focus to the empirical findings to support our theories. We conclude our paper in Section 6 deferred to the Appendix.
More technical results, empirical details, and detailed proofs are
2 PROBLEM FORMULATION AND MAIN RESULT
This section provides an outline of the core elements of our study. We introduce the problem setting before presenting our main result. To start, we consider the following regression model
Vi fx;) + un
for i (1......).
(1)
for an unknown neural network f Fd + R and independent and identically distributed noise ~ (0, o²) with a E (0, oo). We observe n independent and identically distributed data samples (æ1, v1), (æ22, y2), (In, Vn) E Rd x R drawn independently from joint distribution Pa.y with fixed marginal distribution Px = (0, Ia). It assumed that u4 and x; are independent and that the
networks are of the form
fe
Rd + R
(2)
x - fe(x) = WL W ( (W"))
indexed by O (WL. Wo) summarizing the weight matrices W E Rh++1 xhi for I E {0. .,................ L}. The number of hidden layers (the depth of the network) denotes as L E (1,2....) and h, denotes the number of nodes in the 1-th layer (the width of the I-th layer), where ho = d and hit11 = 1. The function Ø¹ RR - Rii is the ReL.U activation function of the 1-th layer, and for a vector [21,-... 2he] E Rh is defined as
t' = (maax(0=2 }, max (0, 22),..., max (0, =
We then consider (fi-type) sparse parameter space Br constraints on the parameters of the network. We use -tyyee constraints as opposed to fo-type constraints, primarily because Ło-type constraints tend make the problem hard to optimize and "combinatorial", particularly in high-dimensional settings (Lederer 2022 Chapter 2). Furthermore, although the 4i-tyee constraint is non-smooth, it generally causes few computational issues (see Friedmmn al. (2010). Also, it has recently been successfully applied to encourage sparsity in neural networks (Lemhadri et al.) 202T). Then, we define a function class
FB. = {Te) O = -WL ..... Wo) E Br..
3

---

Published as a conference paper at ICLR 2025
where BL, denotes sparse parameter space for ReLU feed-forward networks and defined
Br = {INe..... Wo) Σ
| $ Us [W I ui for all j E {i, hi...
1=1
for W RRb and 1 , L and define || - وド= kyl-
W
Assumption 2.1 (un = 1) For simplicity in the proof of our technical results (Lemma 3.2 we assume Vo
This assumption is useful for constructing subclass of space Fs, in the proof of Lemma 3.2 to establish lower bound for the packing number a deep ReLU network's 's space. This assumption basically determines the structure of the weight between the input layer and the first hidden layer of neural network. It also guarantees that the number of input dimensions d, matches the width of the constructed subclass of F S..-
The mini-max risk for the function class FB, can be defined as Wainwright 2019 Chapter 15)
dn (F P p) inf sup 3 EFRR,
( (p(F.
where FB. x FB. + 10, oo) is semi metrid and + o0) + [0, c0) is an increasing function. The expectation taken with respect the training data (ær, y1 ys) and the infimum runs over all possible estimators (measurable functions) of I on the training data (æ;, yi M:) Hence, f(x) = f(x, {(0,, 34) 1=1). where x is data point with the same distribution 1'x- We use the notation Rm,))) (FBL, @ o p) to emphasize that the mini-max risk depends on the number training samples n, the input dimension and the space FB.
In this paper, our focus is on the standard setting where represents the L2(Pa) (-nor-oorm,, -norm, and & = t?. Therefore, f(p(f,f") is the squared L2 (PP ) that is our mini-mat maxi-max risk
inf sup E E f EFB
We assume that the distribution Px has a density h(x) with respect to the Lebesgue measure dæ which, implies that
17 - Il ( (f())) f()x))((x))) ((a
We now present our mini mini--max risk lower bound for deep ReLU neural networks. Considering the regression model defined in Equation ( where f E Fs, (a ReL.U neural network with L. hidden layers and & bouuddde weights), then we have:
Theorem 2.2 (Mini-max risk lower bound for ReLU ford-forward networks) Using the .,. En NO, Ia), then for d large enough [0, oo) + [0, oo), it holds that
L2(P x) (olaa-noo -norm underlying semi metric and æi...., and any increasing function
1
log(d) 1/4
Rr, (F B 2 p)
cv
(4)
2
with /Ta/160, where 5 (0) is numerical constant, and Vy (va/L) For
(.)) (-)2, specifically obtain
à² inf sup E [1 - fr 2 (V=) f f'EFs
log(d)
(5)
n
AA semi metric satisfies all properties of a metric, except that there may exist pairs f f for which
pf. (') = 0.
4

---

Published as a conference paper at ICLR 2025
For the technical reasons, assume that the input dimension is large enough, let say E [10, oo). Our mini-max lower bound above reveals essentially a 1 Vn-dderrese in the sample size, and a log(d)- increase in the input dimension, that perfectly aligns with the upper bounds on the generalization emror of deep neural networks with fityye regularization (compare to Taheei et al. (2021)) Additionally, the factor Vy in rates be interpreted product over the ---nrrm bounds of different layers in FB.- This interpretation aligns perfectly with the established upper and lower bounds on the generalization error of regularized neural networks found in the literature (Taheri et al. 2021 Klusowski & Barron| 2017). 7). The presence of Vy in our rate supports the sharpness of our result (compare with Taheri et al. (202I)).
Theorem 2.2 demonstrates that for all possible 7. risk (also called "generalization error") scales at least as VF log(d)/n. Then, by considering an upper bound for the risk
( [I] f1, e
the result of Theorem 2.2 can be reformulated. It implies that one requires minimum of
n ()) 4 (9)(V>))) (og)))
(6)
samples to achieve of most c² for ReLU feed-forward neural networks. Based on this formula, while we can't determine the exact required number of samples in advance, we can still make some useful observations.
1. We need "many" samples based on the rate 1//n.
2. The noisier the data, the more training samples are needed to achieve the desired error level.
This also stands in strong contrast to classical methods (consider, for instance, linear regression with the least squares estimator the quintessential example of traditional pipeline), which usually require of the order 1/e" samples to reach the same accuracy. However, of course, this does not mean that one should not apply deep learning! Deep learning is extremely flexible in approximating functions, which makes the preferred method in many modern applications.
3 TECHNICAL RESULTS
Here, we provide a technical result essential in proving our main theorem 2.2 Since our proof ap- proach is based on classical result from information theory known Fano's incquality (Lemma A. we need to find a lower bound for the packing number of our network's space (Lemma 3.2
The following notation will be used throughout the paper. For vector RRd, 4n-nomm is defined by |loo #(i E (L....,d] d} 0i 0}. & -n-rrmm defined by |u/11 == Ei |oy] and the
Euclidean norm is defined by |w|2 = v ( We recall ||' == Ehu Σ/ IW || loe 1gksh=+1 Σ/n [W kj for matrix W E Bu xh, The cardinality of the 28-packing
ky and
is defined as M M F ). We use the notation DKL (IP Q) to denote the Kullback-Leibler (KL) divergence between two probability distributions IP and Q We define [M] = {I..... M) as
of the corresponding network's s space FB, for ò E (0, oo) and with respect to
the index set. And we define the notation X (æ1,... F.,) and y = (y1, (y1,...,8n)
We now present the definition of the packing number, as given in Vaart& & Wellner 1996).
Definition 3.1 (Packing number) Consider a metric space consisting of a set Fs, and a semi metric p as defined in Section 2 then, an 28-packing of FB, in the semi metric p collection [f fem} C. FB, such that p( p( ) Z 28 for all j, E [M] and j + k. The 2ô-packing number M(28, FB.: p), is the cardinality of the largest 26-packing.
Our next lemma provides lower bound for the packing number of a ReLU network's space.
Lemma 3.2 (Lower bounding the packing numbers of ReLU foed-forward networks' spaces)
For sparse collection of deep ReL.U feed-forward nefworks' spaces By there exist 8 E (0, 20)
5

---

Published as a conference paper at ICLR 2025
such that
[V
log (26, FB,l -ll22) 2
log(d),
200
where 7 E (0) is a numerical constant and Vy (vx/ L.
This lemma provides valuable insights into the capacity and potential complexity of ReLU feed- forward networks. The key components of this bound are twofold: 1. the favorite log(d) factor (and not the huge network size) and 2. the factor Vy, that both are enhanced employing the ---nrrm control over the parameters of the network. In particular, the logarithmic dependence on the input dimension d' and the factor Vy offer perspective on how complexity growth relates to the network size and the sparsity level.
PROOF OF THEOREM 2.2
Here, we provide the proof of our main theorem:
Proof The proof is based on employing a variants of Fano's method well-known as "local packing"
or "rescaling" (Wainwright 2019 Yang & Barron 1999) and our Lemma 3.2
Let's start the proof writing the mutual information in terms of KL divergence (see also Section A assuming a 26-packing is available with centers j E [M]; then, using Wainwright (2019 tion 15.30) we can obtain
Equa-
1 M
I(J;""IX') = M Σ (P
Se: 11
max M.
(KL(PT)) fei
where Q = (1/M) Pjas is the mixture distribution, J is uniformly distributed over the index set [M], and Py,, is the n-product distribution (see Section A). The naive idea of "lo- cal packing" is considering 26-packing within the space FB, (in the semi metric p) such that Maxj, (PP, I| Pia.. S n(2x5)² for a quantity x. E [1). That implies the KL divergence should be bounded by multiple of 5 for all centers in the packing set. In fact, instead of the whole space, we consider just a local area of that (specified as a ball with radius 2nd)). Then, employing our earlier display implies an upper bound for the mutual information.
Following above technique, we focus on a local area of the network's space and call it Fs. consider 28- 26-packing set of that where for two distinct networks fer
Fs with j. k [M') (x)) 2 25. Also, we suppose that p(fe: (x)) (x)) < 2kd for a constant have p(fe, e fe)
(1) for fer. fe Fs with j. E [M'] (note that we can always find such an area just by rescaling across our networks output; exact value of ō be specified later). Then, employing Lemma A.3
obtain
(PT PP (t))
S 202 (2x8)²
for j + [M', where the last inequality is reached using our assumption on Fs, that a ball with radius 2nd. Collecting results above, we can obtain ("J < n(2x5)² /20² (226) (see also Lemma A.5).
In the second step and based on (local) Fano's inequality, we need to specify 25 25-packing set with the largest cardinality to verify ([J:Y"[[")) + log 2)/ log M < 1/2. So we assign the value of 8 to ensure
m2(m))²
An(k88]2 o²
log MM2, IL.))
2log
22
Next step is lower bounding log M(25 F
(1..)) Let recall that Fs is local area of Fs
(Fs C FB.) ). Employing Yang & Barron 1999 Lemma 3), log M(28, Fs. 1 [L,) that is a local- entropy can be lower-bounded on high level by fraction of log MM2, I. |I,)) that is the global entropy. Accordingly, we employ our lower bound on the packing number in Lemma 3.2 as a lower bounding (a fraction of) log M(25, FB, l (le,) that implies
o2 n(K))² = (V/ 2 log(d),
208

---

Published as a conference paper at ICLR 2025
and gives
82 ToVy log(d)
40x
"
Let note that our specified value for above is not exact, because for simplicity we just keep the impact of main factors like n. d and o, while skipping some constants connecting the local and global entropy. We can 1. substitute the obtained value of into "local packing" version of Fano's inequality (Wainwright, 2019 Section 15.3.3), 2. perform some rewriting and plug in the value of (K = 4) (see Appendix Section A) to yield
ToV=
log(d)
1/2
(n, (FBL; o p) 2
$
2
40n
n2
ToVV
1/2
log (d)
1/1
2 +
40n
1
[TOV
1/2
(log(d)
1/4
2
160
We plug the value of c- in the view of Theorem
2.2
into this inequality and get
1
log(d) 1/47
(n, 1
$
which proves our first claim. For the second claim, simply use ((-) (.)² to obtain
log(d)
dn (F FB; 1 To (V=)
Based on our mini-mat max risk setting (Section 2. the above expression can be presented as follows:
c²
log(d)
inf sup 7 EeF
B( [17 1'
(Vr)
n
as desired.
5 EMPIRICAL STUDIES
This section supports our theoretical findings with simulations on benchmark datasets. While our theoretical results were established based on feed-forward ReLU neural networks, this empirical study, extend our investigation to include both ReLU ferwwrd networks and ReLU CNNs. The focus is on understanding whether the generalization error of ReLU neural networks scales more significantly with 1/n-rate 1/ /r-rate. We prediction error of test samples an estimate of the "generalization error" (as defined in Section 2 for the trained ReLU networks.
For experiments, consider both classification and regression tasks. The datasets used include MNIST, Masshion-MiTI and CIFAR10 10 for classification, and the California Housing Prices (CHP) dataset for regression analysis. We Cross entropy (CE) and Reeansquarred (MS) еnror as loss functions for classification and regression datasets, respectively. The implementation of these neural networks was carried out using the TensorF Low library (see Appendix [oo further details). It is also important to note that for none of these real-world datasets do we consider any assumptions such as Gaussian distributions or other assumptions. We conduct our experiments two steps: in the first step, we train the network and compute the error for the test samples. In the second step, we determine the appropriate curve (either l/vn or 1/n scales) that best fits the test error values. To address the impact of various factors like network depth (L), the number of parameters (P) and the width of the hidden layers, we consider two curves (c1 + aa//n) and (c2 + B/n) with a, B, C1, (0, oo) (note that consider the constant terms C1, C2 in the context of approximation error). Optimizing these parameters is achieved through the Sequent ial Least Squares Quadratic Programming ng (SI.QQP) method (Kraft 1988 and the mi nimi ze function from
7

---

Published as a conference paper at ICLR 2025
28000
12:00 Number Thiling Samples
40/00
Nurror Traniing Sermolt
Figure I: Comparative analysis of the strength of two curves (c1 + +a/vi) and (c2 + 8/n) to model the generalization eтror different architectures for the MNIST dataset: (a) Shallow ReLU feed- forward network, width of 128 and (b) nour-hidden-layer network, uniform width of 128 (left to right).
scipy- optimi ze employed for SLSQP implementation. The objective function calculates sum of squared differences between the generalization error of neural network and two separate curves. The optimization process aims to find the values for the coefficients that minimize this sum of squared differences. We investigate the strength of these two curves in fitting the generalization error behavior both visually, through figures (Figure 1 to Figure 5 and numerically, using metrics such as R-squared and MSE values (Table to Table 4 We begin this investigation with the MNIST dataset.
MNIST The MNI ST dataset consists of 60 000 training images and 10 10000 testing images, each with dimensions of 28 28 pixels. We perform experiments by incrementally increasing the number of training samples in steps of 500, evaluating the performance across various neural network architectures, including both shallow and deep ReLU feed-forward networks. We consider two scenarios in our analysis. In the first scenario, we consider the entire dataset and gradually increase the number of training samples intervals of 500. In the second scenario, we focus on larger training samples-vy we begin with 20 000 training samples- and similarly increase the sample size in intervals of 500. Figure [ (a) and Figure 2aa) illustrate the result of our analysis for shallow neural network with width of 128, while Figure 1b) and Figure 2(b) illustrate the result for a four-hidden layer ReLU feed-fore forward neural network with a uniform width of 128.
Table I:
Numerical metrics to compare the strength of two curves (cl + a/v and (c2 + B/n) to model the generalization error in different architectures for the MNIST dataset.
MSE
R-squared
Architectures
(C2 3/n)
(c1 + a/ Vn)
(c2 3/nn
(c1 + a/vn)
Shallow ReLU Network
1.7 10-
5.2 10
-1.4 1.4.10 10"
9.3 1.
Four-hiddeen-lyer ReLU Network
1.1 10-2
2.4 10-4
-7.8 10-1
3.6-10-1
Tastng
Teiling Erer
Barior riaing Saroke
Figure 2: Comparative analysis of the strength of two curves (c2 + 8/n) and (cr +a//n) to model the generalization eтrоr in different architectures for the MNISTS dataset for larger training samples: (a) Shallow ReLU feed-forward network, width of 128 and (b) Four-hidden-layer network, uniform width of 128 (left to right).
The MachionnMNISS dataset contains 60 000 training images and 10 000 testing images, both with dimensions of 28 x 28 pixels. We run the experiments in intervals of 500
Mishion-MNIST
8

---

Published as a conference paper at ICLR 2025
Taang
b:00in Ente
Tecko
6x30
1850
12:00
10000
20800
$000
1000
2008 2018
Wurber Samoles
Puaring
Samples
Figure 3: Comparative analysis of the strength of two curves (ci +a/vn) and (c2 + B/n) model the generalization error in different architectures for the Eashion-MNISS dataset: (a) Shallow ReLU reddffowwrrd network, width of 100, (b) saree-hidden-lan network, uniform width of 100, and (c) CNN ReLU network (left to right).
samples (training samples) and examined with three different architectures. Figure 3a) illustrates the result of our analysis for shallow neural network with a width of 100, while Figure (b) illustrates the result for three-hidden layer ReLU ferdffowward neural network with a uniform width of 100. Additionally, Figure ()) illustrates the result for CNN ReLU.
Table 2:
Numerical metrics to compare the strength of two curves (cI + +////n and (c2 B/n) model the generalization error in different architectures for the Fashi Mo dataset.
MSE
R-squared
Architectures
(c2 + B/n)
(c1 +a/vn)
(c2 + 3/n)
(c) + a/vn)
Shallow ReLU Network
1.3 10-2
6.1 10
-1.6 - 10
8.8 10
Three- siree-hidden-layrr ReLU Network
1.4 10-
8.4- 10
-2.1 10"
8.2 10
CNN ReLUU Network
3.1. 10-2
1.4 10-3
-1.7 10"
8.7. 10-1
CIFAR10 The CIFAR10 dataset contains 50000 training images and 10 000 testing images, both with dimensions of 32 x 32 pixels. We run the experiments in intervals of 500 samples (training samples) and explore various neural network architectures, including both ReLU feed-forward networks and CNN ReLU. Figure 4a) illustrates the result of our analysis for a shallow ReLU neural network with the width of 1000, and Figure (bbb illustrates the result for CNN ReLU network.
Table 3: Numerical metrics to compare the strength two curves (c1 + a/ /n) and (c2 + B/n) to model the generalization error in different architectures for the CIFAR1 dataset.
MSE
R-squared
Architectures
(02 + 3//)
(c) + aa/vv/ Vn)
(o2 + 3/nn
(c) + +t///n)
Shallow ReLU Network
7.9. 10-2
8.1 10-3
-3.5 10"
5.3 10
CNN ReLU Network
2.9- 10-1
3.1 10-2
-3.7 10"
4.8 10-1
California housing prices (CHP) The version considered in this study comprises 8 numeric input attributes and a dataset of 20 640 samples. These samples were randomly divided into 15 000 for the training data and the remaining for the test data. The batch size for the training samples is set to 20. We run the experiments in intervals of 200 samples (training samples).
Table 4: Numerical metrics to compare the strength of two curves (ci + +a/vn) and (c2 + 3/n) to model the generalization error of five-hidden layer network with a uniform width of 300 for the CHP dataset.
Architecture
MSE
R R-squared
(02 + B/n)
(c) + a /n)
(c2 + 8/n)
(c) + a/vn Vn)
Five-hidden-layer ReLU Network
9.9 10
2.1 10
2.1 10
8.4 10
9

---

Published as a conference paper at ICLR 2025
Number Twniing Sample
Narroar of aiThaing SATO
Figure 4: Comparative analysis of the strength of two curves (cr + +a/vn and (c2 + B/n) model the generalization error different architectures for the CIFARIO O dataset: (a) Shallow ReLU feed- forward network, width of 1000 and (b) CNN ReLU network (left right).
3009
0000
12000 1888
Seaving
Figure 5: Comparative analysis of the strength of two curves (cr + vn) and (cy + B/n) to model the generalization error five-hidden layer network with uniform width of 300) for CHP dataset
By analyzing both the numerical results and the figures, it is evident that for both regression and classification tasks, the generalization error scales more significantly rate of 1/ //vn rather than 1/n. These findings consistently hold true for both ReLU feed-forward networks and ReL.U CNNs.
CONCLUSION
This paper uses Fano's inequality to establish a mini-max risk lower bound for ReL.U feed-forward neural networks. The bound scales at the rate //lg(dd)n. Our empirical findings support this conclusion and indicate that for both regression and classification problems, the generalization error of ReLU neural networks scales at the rate 1/ l/vn. More specifically, our theories and empirical results demonstrate that the generalization error of ReLU feed-forward network cannot be improved beyond the rate 1/vT in general. Our theory is also much closer to current practice than earlier works: for example, we focus on deep networks rather than shallow ones (Du al., 2018 Klusowski & Barron| 2017). and we employ ReLU activation functions instead of Sinusoidal (Klusowski & Barron 2017) linear (Du et 2018) activation functions.
The current discussions about large language models (LLMs) illustrate that our research is extremely relevant and timely. The training data for L.MSs have steadily grown over the last years: for example, GPT-3 was trained on about 300 billion tokens (Brown et al. (020), Chinchilla about 1.4 trillion tokens (Hoffmann et al.) 2022), GPT-4 on about 13 trillion tokens (OpenAl (023) and Llama on over 15 trillion tokens (Meta 2024). However, it is believed that this trend will have natural end soon: there will simply not be enough fresh texts any more. A trend is, therefore, the development of smaller models, such as Phi-3-Mini (Abdin et al. 2024). which trained less data in general and on "real" data enriched with synthetic data. But how much data are really needed for such minimal Al-solutions? This paper is a small step toward answering this question.
ACKNOWLEDGMENTS
This research partially funded by grants 50906238, 011$24065B, 543964668 (SPP2298). and 520388526 (TRR391) from the Deutsche Forschungsgemeinschafft (DFG, German Research Founda- tion).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat Behl, Alon Benhaim, Misha Bilenko, Johan Bjorek, Sébastien Bubeck, Martin Caio, Caio César Teodoro Mendes, Weizhu Chen, Vishrav Chaudhary, Parul Chopra, Allie Del Giorno, Gustavo de Rosa, Matthew Dixon, Ronen Eldan, Dan Iter, Amit Garg, Abhishek Goswami, Suriya Gunasekar, Emman Haider, Junheng Hao, Russell Hewett, Jamie Huynh, Mojan Javaheripi, Xin Jin, Piero Kauffmann, Nikos Karampatziakis, Dongwoo Kim, Mahoud Khademi, Lev Kurilenko, James R. Lee, Yin Tat Lee, Yuanzhi Li, Chen Liang, Weishung Liu, Eric Lin, Zeqi Lin, Piyush Madan, Arindam Mitra, Hardik Modi, Anh Nguyen, Brandon Norick, Barun Patra, Daniel PerkerBecker, Thomas Portet, Reid Pryzant, Heyang Qin, Marko Radmilac, Corby Rosset, Sambudha Roy, Olatunji Ruwase, Olli Saarikivi, Amin Saied, Adil Salim, Michael Santacroce, Shital Shah, Ning Shang. Hiteshi Sharma, Xia Song, Masahiro Tanaka, Xinghan Wang, Rachel Ward, Chengruidong Yu, Cyril Zhang, Jianwen Zhang, Li Lyna Zhang, Yi Zhang, Yue Zhang, Yunan Zhang, and Xiren Zhou. Phi-3 technical report: a highly capable language model locally on your phone. axxivorr//4f/2400414411,, 2024.
M. Anthony and Peter Bartlett. Neural network learning: Theoretical foundattios Cambridge Univ. Press, 2009.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang, Stronger generalization bounds for deep nets via a compression approach. ICML, pp. 254-263, 2018.
Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla. SegNet: A deep convolutional encoder- decoder architecture for image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 39(12): 2481-2495, 2017.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spertrzlly-normalzzedd margin bounds for neural networks. In NIPS, volume 30, pp. 6240-6249, 2017.
Lucien Birgé. Approximation dans les espaces metriques et theorie de I'estimation. Wahrsch. Verw: Gebiete, 65:181-237, 1983.
Alexei Botchkarev. Performance metrics (error measures) in machine learning regression, forecasting and prognostics: Properties and typology. arXiv: urXiv:/809.0000 1809003009 2018.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Her- bert Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. arxiv.org/abs22055.111 14165. 2020.
Simon Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov. and Aarti Singh. How many samples needed estimate convolutional neural network? In NIPS, 2018.
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Regularization paths for generalized linear models via coordinate descent. J. Stat. Softw, 33(1):1-22 2010.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size indepenndenn sample complexity of neural networks. In COLT, volume 75, pp. 297-299, 2018.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT Press, 2016.
Alex Graves, AbdeIrahman Mohamed, and Geoffrey.E. Hinton. Speech recognition with deep recurrent neural networks. In ICASSP, pp. 6645-6649, 2013.
Yilin Guol, Shubhangi Ghosh, Haolei Weng, and Arian Maleki. A note on the minimax risk of sparse linear regression. arxiv.orghdf//2055.055 055444 2024.
Satoshi Hayakawa and Taiji Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-361, 2020. 2020.
11

---

Published as a conference paper at ICLR 2025
Mohamed Hebiri, Johannes Lederer, and Mahsa Taheri. Layer sparsity in neural networks. J. Stat. Plan. Inference, 234, 2025.
Yaoshiang Ho and Samuel Wooky. The weal-world- cross-entropy loss function: Modeling the costs of mislabeling. IEEE Access, 8:4806-4813, 2019.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. arxiv.org/abs/2203.1 15556, 2022.
Masaaki Imaizumi and Kenji Fukumizu. Deep neural networks learn non-smooth functions effectively, In AISTATS, volume 89, pp. 869-878, 2019.
Anatoli B. Juditsky, Oleg V. Lepski, and Alexandre B. Tsybakov. Nonparametric estimation of composite functions, Ann. Statist, 3700):130--1404 2009.
Jason.M. Klusowski and Andrew Barron. Mini-max lower bounds for ridge combinations including neural nets. In ISIT, 2017.
Michael Kohler and Adam Krzyžak. Nonparametric regresssioo based on hierarchical interaction models. IEEE Trans. Inform. Theory, 63(3):1620- 2017.
Dieter Kraft, A software package for sequential quadratic programming. Know. Reporting d. DFVLR, 1988.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521:436-444, 2015.
Johannes Lederer. Fundumentals of high-dimenssonal statistics with exercises and R labs. Springer, 2022.
Johannes Lederer. Statistical guarantees for sparse deep learning. AStA Adv. Stat. Anal., 2023.
Ismael Lemhadri, Feng Ruan, Louis Abraham, and Robert Tibshirani. Lassonet: a neural network with feature sparsity. Mach. Learn. Res., 22((17)):-29, 2021.
Meta. Introducing meta Ilama 3: the most capable openly available 11m to date. metps://ai.mett.a www.boooommmaaalllaaaaa- 2024.
Ali Mohades and Johannes Lederer. Reducing computational and statistical complexity in machine learning through cardinality sparsity. arxih.org/abs/230220882. 2023.
Kevin P. Murphy. Machine learning: A probabilistic perspective (adaptive computation and machine learning series). The MIT Press, 2012.
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arxin.oggabx/190000077... 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In COLT, volume 40, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring generaliza- tion in deep learning. In NIPS, pp. 5949-5958. 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach spectrally- normalized margin bounds for neural networks. In ICLR, 2018.
OpenAl. Gpt-4 technical report. axxiv.rrg/od/23333088744 2023.
Rahul Parhi and Robert Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM J. Math. Data Sci., 4(2):464-489, 2022.
Garvesh Raskutti, Bin Yu, and Martin... Wainwright. Lower bounds on minimax rates for nonpara- metric regression with additive sparsity and smoothness. In NIPS, volume 22, 2009.
12

---

Published as a conference paper at ICLR 2025
Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. J. Mach. Learn. Res., 13:389 427, 2012.
Jonathan Scarlett and Volkan Cevher. An introductory guide to tonfo''ss 's inequality with applications in statistical estimation. Cambridge Uni. Press, 2021.
Johannes Schmidt- Nonparametric regression using deep neural networks with relu activation function. Ann. Statist., 48(44)187551189) 2020.
Johannes Schmidt-Hieber and Thijs Bos. Convergence rates of deep relu networks for multiclass classification. Electron. J. Stat., 16(1):2724-2773 2022.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: Optimal rate and curse of dimensionality. In ICRI,, 2019.
Mahsa Taheri, Fang Xie, and Johannes Lederer. Statistical guarantees for approximate stationary points of simple neural networks. arxi..org/ab/22055044999 2022.
Mahsa Taheri, Fang Xie, and Johannes Lederer. Statistical guarantees for regularized neural networks. Neural Networks, 142:148- 142:148- 2021.
Kazuma Tsuji. Estimation error analysis of deep learning on the regression problem on the variable exponent besov space. Electron. J. Stat.,
2021.
Aad W. Vaart and Jon A. Wellner. Weak convergence and empirical processes with applications to statistics. Springer, 1996.
Martin.J. Wainwright. Iligh-dimensional statistics A non-asymptotic viewpoint. Cambridge Uni. Press, 2019.
Yuhong Yang and Andrew Barron. Information theorettc determination of minimax rates of conver- gence. Ann. Statis, (755:1564-1599, 1999.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Kaiqi Zhang and Yu- Yu-Xiang Wang. Deep learning meets nonparametric regression: Are weight decayed dnns locally adaptive? In ICLR, 2023.
13

---

Published as a conference paper at ICLR 2025
A FURTHER TECHNICAL RESULTS
In this section, we present additional technical results from the work others and our own, that are essential for the proof of Theorem 2.2 components but might also be of interest by themselves. We divide the results into two main parts. The first part includes Lemma A.5 and a few other results that contained in the proof of this lemma, and the second part includes few results, both from work and others' to prove Lemma 3.2 Before providing those preliminary results, we provide the general formula for Fano's 's inequality (Wainwright, 2019 Proposition 15.12). Based on the concept packing is family of n-product distributions (as defined in Part 1) number, assume that { "'....... f.
for the corresponding neural networks .e...... Seu which satisfy p e (æ), e (=(()))))))))))))))))))))))))( all j. k E [M] and & k. Then, assume that J is uniformly distributed over the index set [M] and the conditional distribution of (Y*) (X") given J defined by ((Y*)X") = =] PTe. Accordingly, Fano's s inequality can be formalized as:
26 for
Lemma A.1 (Fano's Inequality) Let (Jot....;JMM) E F be 28-packing set with respect to p. Then, for any increasing function + [0, 00) + [0, 00), the mini-max risk is lower bounded by
an (FB,; p) 2 ((8) T(J; (U)") + log
log M
The symbol Y(J ("") represents the mutual information between a random index J, which is drawn uniformly from the index set [M] and the samples (Y*|X") drawn from the prior distribution fea corresponding to fer == fer. The mutual information, measures how much information can be revealed about the index of 25-packing set by drawing the samples (Y" ()"
PART 1: PRELIMINARY RESULTS FOR UPPER BOUNDING THE MUTUAL INFORMATION
We present some auxiliary results that are contained in the proof of Lemma A.5 To follow these results more conveniently, we explain the necessary steps briefly. After defining the KL divergence as a measure of distance between two probability measures, we calculate the KL divergence be- tween two multivariate normal distributions Hayakawa & Suzuki (2020) Lemma A.I). Then, we calculate KT, divergence of n-product of two multivariate normal distributions and finally, we find the connection between the mutual information and KT, divergence.
The KL divergence between two different probability distributions P and Q on domain X' with densities p(x) and q(x), respectively, can be defined as (Wainwright 2019 Equation 3.57)
DKL. Q) = -f p(xx) log p(xx) da. q(x))
Since we deal with n independent samples, the probabilities are defined on a product space of components. Therefore,
need to find the KL divergence between different n-product distributions. Assume that (P'...., IP") be a collection of n probability distributions, and define plm : 8 - P' as the re-rodduct distributions. Define another n-product distribution Q2:T in similar way. For the ease of notation, define pa == pl and Q" Q!:" Then, the connection between the KL divergence of n-product distributions 18 and @ and the KL divergence of the individual pairs (Wainwright 2019 Equation 15.1la), can be formalized as the following lemma:
Lemma A.2 (Decomposition of the KL divergence for n-product distributions) For two n- product distributions p" and Q?", it holds that
DKL (19 Q""
Σ
DKL (IP Q*).
And in the case of i-i-d- product distributions meaning that p = pl and Q² = Q² for all i [1, we have
DKL [P" Q")) = n x DKL (P' || Q²)..
We consider short-hands P and Q for pd and Q respectively. So, the previous equation takes form DKL. [pm [()) DEL. (P Q)
14

---

Published as a conference paper at ICLR 2025
We then proceed calculate the KL divergence between two normal distributions. Consider the regression model defined in Equation [T] and the network model defined in Eguation (2) We assume that the noise terms independent and identically distributed and u, (O, o²). Recall that the explanatory variables æ; follow a fixed distribution P. and have the density h())). Then, we define = (x. yy TRd x IR the joint variable of and y- According to the conditional probability, the joint density can be written as follows:
Pse: (z) py|x((/(x)b(z))
(y (w))
20
h(x),
V2T02
where j E [M] and Pias (z) is the joint density of (æ, y) with regression function fei (æ). And consider Pfaa (z) as another joint density of (ac, y) in the same manner with regression function fer (z) and two distinct corresponding normal distributions Psas and ff such that have densities Pre. (z) and Pfae (z), respectively. Recall that fes and f are any distinct neural networks of the neural network model defined in Section [ which parameterized by @ and @ (j, & E [M] as any distinct indices of the 26-packing set). Then, the KL divergence between any two normal distributions If fs and f can be calculated as the following lemma (Yang & Barron 1999):
Lemma A.3 (The KL divergence between two multivariate normal distributions) Assume any two normal distributions P P/e: and f for all j, [M] and j * k, then it holds that
(P fei || 1 2n / (Jes(x)) Sor (z)) (()))))(())d (xx)
xEx
And that
(PL fer [PP" )= 20 xEE
(fo) (fx))==))(()))) (
h(z))
To fulfill this part's goal, we have just left to find a connection between the KL divergence and the mutual information.
In the next lemma, we are interested to upper bounding the mutual information (Scarlett Cevher 2021) which measures the dependence between the joint distributions and the product of the marginals of two random variables by describing it's connection with the KI. divergence. Assume that under the Markov chain J + fe (Y"l "),, a random index J is drawn uniformly from {I...., M) and samples
are drawn from the prior distributions IP ffe corresponding to
fe fee. Note that if one sample (Y drawn, then we have T(J; Y|X).
There are many tools to upper bounding the mutual information and the most straight forward tools is based on the KL divergence (Wainwright) 2019 Equation 15.34) as follows:
Lemma A.4 (The connection between the mutual information and the KL divergence) For any two distinct normal probability distributions Psai and IP for for all j, k [M], it holds that
I(J:Y(X) < DKL (KL(F/A (e) 1()))
M
J.k=1 J4R
For any two distinct n n--rodduct normal probability distributions Pr, and IPT for holds that
M
(J:Y"[X") S
DKL (P I (P)))))
M
1,k=1
37k
Lemma A.5 (Upper bounding [(): of the 25-packing of network's space FB.) For all
possible pairs of two distinct networks fer: for E FB, satisfy p(fer (æ), fo)( 28, the mutual information I IJJ: (")) is upper bounded by
2n(K6)2
I(J:Y"X")
o²
15

---

Published as a conference paper at ICLR 2025
for suitable (o), such that p(f es (z), fex (x)) I 2kd..
PART 2: RELATIONSHIP BETWEEN GLOBAL AND LOCAL METRIC ENTROPIES
Here, we briefly provide a connection between the global metric entropy and the local metric entropy (Yang & Barron 1999, Section 7). In fact, the global metric entropy ensures the existence of "at least one" local packing set which has the property required for the use of Birgé's argument (Birgé 1983).
Accordingly, in the proof of our main Theorem 2.2 instead of considering the entire space B
we focus on a local area (ball with radius 2kσ) where the "local" Fano's 's method is applied.
The
following Definition [A.6 (Yang & Barron 1999 Section 7) and Lemma A.7 (Yang & Barron
1999
Lemma 3) assist us in determining the value for K. ensuring that there is no concern about being too large. These also allow us to work with a more manageable subset of the function space FB,,, called F in the proof of our Theorem 2.2 By considering the case when d is metric and assuming the global packing entropy of the space S under the distance is (6), the definition of the local metric entropy is as follows (Yang & Barron 1999 Section 7):
Definition A.6 (Local metric entropy) The local d-entropy at 0 E S is the log of the largest (6/2)-
packing set in B(0, 6) {0' S: d(0', 0) < 83. The local 6-entropy at 0 is denoted by M (6)0) and the local 8-entropy of S is defined as M (8) = max (5)0). PES
Based on this definition, the relationship between the global and local entropies can be formulate as follows (Yang& & Barron 1999
Lemma 3):
Lemma A.7 (The relationship between the global and local metric entropies) the global and lo- cal metric entropies have the following relationship:
( - M(8)= S M S M(8/2).
can Value of K Employing Lemma A.7 log MM28, 1. 11.111)) 11.1 that is local entropy- can be lower bounded on high-level by fraction of Nog.M2220 [B, l,2). .. that is global entropy (Lemma 3.2). In the proof of Theorem 2.2 we used the result of Lemma A.7 to bound the local packing. We proceed follows: we begin with 26- 26-packing, meaning that p(J e (z), fe (x)) 2 26 for all j * ke E [M]. is easy to conclude that these centers will be within 46 from 0. By applying the
triangle inequality, we conclude that p(f (æ), o (m)) I 86. As have p(ʃe> (x). e+ (m))
2nō (see Lemma A.5), this gives us k = 4. We use this value directly in the proof Theorem 2.2
PART 3: PRELIMINARY RESULTS FOR DERIVING A LOWER BOUND FOR PACKING NUMBER OF RELU NETWORKS' SPACES
In this section, we present supporting lemmas that are included in the proof of Lemma 3.2 for deriving the lower bound for the packing number of our defined ReLU network's space. We start by calculating the Gaussian integrals over half-space. Assume that æ is realization of random variable X that follows the d-dimensional Gaussian distribution, then we say that for E [1,...S) S}. by > 0 and b,_ < 0 are two half-spaces of hyperplane 6, 0 for ba E IRd. We then can define the probability density function of æ with mean vector μ and the covariance matrix Σ as follows:
m) g t/ m)
pla, μr
e
da
(2 d/2 (2m)d/2
Σ
TEX
where Σ det((2) E), is the determinant of Σ.
If = 0, then we have
x
p( 0x, 0, Σ) =
6
dac
(2T)d//2
d/2
NEX
Accordingly, the probability density function of on either half- by x > or
bj_ x S 0 takes
the form
1
1 dx
p(b x 0, 0, Σ
(2T)
Σ
D%
and can be caleulated as the following lemma:
16

---

Published as a conference paper at ICLR 2025
Lemma A.8 (Gaussian integrals over half-space) Assume that æ, by B for fixed vector by- we define a that
by, x > Then. for the corresponding probability density function it holds
p(b 0,0,E)=
In the next lemma we are motivated to employ the result of Lemma A.8 to calculate [[ (b, x)) which is necessary for the proof of Lemma 3.2
Lemma A.9 (The expectation of squared ReLU functions) Let be a Gaussian random variable and bg æ > O is half-space, then,
1
2
In the following lemma, we present Klusowski & Barron 2017 Lemmal), which concerns the cardinality of a set and is integral the proof of Lemma 3.2 This lemma helps define our desired set with a predefined Hamming weight, and its elements can be interpreted as binary codes. Now, let state the lemma.
Lemma A.10 (Cardinality of a binary set) For integers and d' with [10, oc) and d' [1, d/10//01/11 10), define set
S == (w E (0, |1/|1 d'}
Then, there exists subset A C S with cardinality at least S = ( such that each element has Hamming weight d' and any pairs of elements have minimum Hamming distance d' /5.
B
PROOFS
In this section, we provide the proof of Lemma 3.2 Additionally, the proofs of the lemmas in Appendix A will be included.
B. PROOF OF LEMMA 3.2
Proof The core of this proof involves two steps: first, the construction of a subclass of functions within Fs,, and then finding lower bound for log of the cardinality of the constructed class. Second, using the fact that lower bound for the cardinality of smaller space can serve as lower bound for the cardinality of the larger space. Let us begin by discussing the construction of the subclass function class FB.
STEP 1: THE CONSTRUCTION SUBCLASS FUNCTION CLASS FB
Our first step is to construct subclass of our defined function class Fs, and then to find lower bound for the log of the packing number the constructed class. To achieve this, we begin by defining set of binary vectors C E {0. 1] for d [10, oo) such that each element of this set has Hamming weight d', where d' E [1, d/ 10] and the cardinality of this set is denoted by Recall that, we assume that ve so, that 5 = and we can consider the vector b, E {0, 1] as vector with all the entries equal to zero except for the ith entry, which is set one. It implies that for all + (L.....S)
choose d' = no² 1. Then, anyone
readily conclude
b by = 0.
We can also conclude that for each b; with E {1, (I,...,S), we have
|bl|2 = V ((b.)))² + +... + ((b:)a) 1.
Following the same argument above have
[b:l1 1 (b:)]| +... (ba))
17

---

Published as a conference paper at ICLR 2025
Then, for enumeration b1 ....... by of C, we claim that the function space Fu as defined below can represent a subspace of Fa.
VF s
Fu =
=
W
Φ (bg
x) : w E
with w = (V=/A)w and À = tw E {0, | rA} for VE,T E (0, oo) and an integer E S/10/ (exact values of V and À be specified later in the proof, while the T is a constant depending Uz.) We argue that Fo is representing subspace of deep neural networks FB, with non-negative weight matrices W for E {1,-.. L inspired by Hebiri et al. (2025). To be more precise, we state that for a fixed pair X, T and 4 w E A, there exists a tuple of non-negative weight matrices (W1 ..... Wh with Et= [W S that their product verifies W' w'''-- W w (see Remark B. For example, for large enough Us. we can fix 1, since our network space Ft. can generate binary vectors w with cardinality S employing a suitable tuple of non-negative matrices ) In fact, we are using the property that for non-negative weight matrices, the ReLU activations in deep neural networks (for layers 1 E {1..... [.}) can be ignored and so, deep network for the corresponding layers behaves like a simple matrix product (Hebiri al. 2025). This property gives us the chance to write those specific networks (with non-negative weight matrices) in the form of a shallow neural network as stated in Fu. Let's also note that for the corresponding networks, we can 1. invoke compatible norms L times, 2. use the inequality of arithmetic and geometrie means, 3. definition of our ReLU network's space (defined in Section 2 and 4. invoke the definition of Vy-
in the view of Theorem 2.2 get
| W 1 = IW /illww-..... 1
|
1 Σ Iw'll1) 4
$ U/5 L
L
= Vs.
Some rewriting over the Fu implies
TV=
Fo
w
" x) w E EA
where w (T>=/A)w and A tw E [0,
|w/1 ^} is the set in Lemma A.10
E S/10 is an integer and denotes as the Hamming weight of each element of this set (Klusowski
Barron 2017 7 Theorem 2).
According to the above definition of Fo, we have
S
(w) w/ "h) (b% )
[[L((,,))a)) - S(w 1)) (2])
E
where w, w/ E A.A.
Note that, based the structure of and w', for all le (1....,S), S}. (wy. w()) falls within the set 0, And if (we, w³)) = 0, the value of the expected term on the right-hand side -for the corresponding k- is equal O: thus for the sake of convenience, we consider an integer value S' < S in such way that lw w/,1 = 1 for all & E {1...., S'), S'}. Based on the structure of all pairs w, w' and Lemma A.10 we can conclude that S > X/5. We will use S' for the remainder of the proof.
We then proceed with
9'
E [lllf(w. (x:)
S( ((wr
(T5
2
E
(ww - wh (bTT x²))
k=
18

---

Published as a conference paper at ICLR 2025
Next, we motivated to find lower bound for [l. (2)) - f(w b) (2)))ig)) We can 1. employ the last view, 2. expand the squared over the sum and invoke the linearity of expected value, 3. invoke the linearity of expected value, 4. apply the above assumption that (w3 w()²² 1, use the result of Lemma A.9 which shows (b =))) 1/2, and the properties of function and 6. use the
fact that E Φ (b ) (6] x)] 1/2T, and the properties of sum function to obtain
S'
[[)) - ((wrb)<))iia = (TV=)
(wn wk) (b, æt)) 21
E
=<TVx)
EE
((wx wh/ (b =))²
[wk - w/) wb))'(((T w/) (b, x3)
+
E
i=1
j
5
(TV)))
EF
((wk w/) (b) 21))
E [[(
wh ( (b) x)) w/)) m))
k=
j
9'
(TV>)
E
(Ø (b) x))
E
(w) wh ( ( ()) w/) (b] m))
1=
S' S'
TV5
[wk wh) w/) (bT x))=))² (b) (b x))
2
k=
j=1
j/k
-
(TV)))
S'
S'
[wk w/)(ws -0))
7
2T
k=
jzk
here, we need to analyse the second term. We know that (wg-wwf w/11= = 1. Thus, (wr - (urg-w(). (w;- w w/)) for j,j {l...., S'} can have either the same signs or different signs that result in the corresponding positive or negative terms. The worst case happens when the number of +1 and - cases are equal. 1) number of positive
There, the number of total terms is S' 1), and we have ('((S'/2) terms and the remaining terms are negative (5²2 So, can proceed the lower bounding by employing the last view, 2. considering the worst case scenario as discussed, 3. performing some simplifications, 4. performing some arithmetic math, 5. using the fact that ( 1)/27) > 2/10,
19

---

Published as a conference paper at ICLR 2025
6. applying the conclusion that 5' 2 A/5 and 7. performing simplifications to obtain
TV
2
S
S'
(] ())))
wkk - w - w3))
2
2T
k=
1=1
341
TVF
5'
5 -
82 $
)
S
2
2
TV
5"
S"
2
2T
TVF
S'
2n
TV
2
5')
TV
1
5
(TV=)²
25A
So, a 26-separation implies
(TV))2
TV
(25)²
25
105
Then, we can 1. use the result of Lemma A.10 that log( (o) denotes as the log of the cardinality of Fo is at least log (5) 2 (A/4) (og and 2. plugin the value of S that gives
log(#Fo) 2
log(5)
205
[Vr 2
log(d).
205
Based on the formula À = (TV=/105); when Vz is fixed, is evident that as ó decreases, À increases. Moreover, since S d/10, we need to assume that d large enough, Consequently, for small values of 6, sufficiently wide network becomes necessary. This observation is particularly interesting as it provides valuable insights into selecting an appropriate width for the network based on the input dimension. The larger the input dimension d, the wider the network should be.
STEP 2: DERIVING A LOWER BOUND FOR log( #FB.)
For the second step, our aim to lower bound the log of the cardinality of the function class F using the result of the first step. Since we define Fo subclass of FB., we can conclude that the lower bound established for log(#Fo) in the first step also serves as a lower bound for log( FFB.). We then can get
log MM26, B (1ra) 2
log(d),
205
as desired,
Remark B.1 (Constructing vector in A using non-negative weights) Consider an example where I. width of the network set to four, and X Our aim constructing a binary vector with the length four (where X of those are ones) by factor of T (0)oo) To get our desired final vector, the weights could be as follows:
0
3 = 10 c], 22 W
C
20

---

Published as a conference paper at ICLR 2025
Then
0
0
0
07
0
0
0
07
W = 00
c
c
0
0
0
c
0
0
C
0
=
0
1
1
0
Now, for example if we set c. 1/2, then we ger T 1/8.
B.2 PROOF OF LEMMA A.3
Proof To calculate the KL divergence between two normal distributions // and Pr of continuous random variable, each with the corresponding densities p/as (z) and Pfa+ (z). for all j, E [M] where j k, we can 1. use the definition of the KL divergence, 2. plug the value of Pfes (z) and Pf (z) in, 3. perform some simplification, 4. apply the definition of expected value, the linearity of expected value, 6. use y y (æ) + u, 7. perform further rewriting, apply the linearity of expected value, assuming independence between each ū; and æ; 9, cancel out the second term [[[u] = 0) and 10. recognize that only æ values remain, to get
-xvs Pfes log
Plas dz
(PI(P || P(
Pfac (z)
(1 11/V2T02)e ((x -wV- (oo)()))) h(x)) dz
fx Plas (2)
Jxxy
(1/V2mo02) (1))) h((r))
- Pias (2)
(y S (2)) (y Se- (x²)
20
EE-Pies (x) 202 (u fer fe) (y-fes)
fas (2)) fxx(x)) ))
Ezapi
(y (e- - -
- -e- (x)) 2
20
(x)
1
Ex
(u)²
202
E Barplen
(o) - 2n 2u( (m)) Son (m)))
20
(x)
1
EEzpIio (2)
-
20
-TE E (1 f(r (xx)
E (2) (fer (x) fx)
20
(fei (z) fx) (fxx hxx)dxx.
20 øEx
Furthermore, by combining this result with Lemma A.2 s result, it holds that for all j, k E [M] and
j # k
DKL(PT for
| [P]
(fe: (x) fox (x)) M ((x)dx,
20 WEx
as desired.
Note that we only assume Gaussian noise, and accordingly we define Pfe. (z) as the joint density of (xc, y) with regression function fex (Equation More specifically, the outputs of the network not Gaussian: they are just Gaussian conditional on æ.
21

---

Published as a conference paper at ICLR 2025
B.3 PROOF OF LEMMA
Proof Consider a family of distributions (Ffa....,PPaa... then [X) with respect to - fe + (Y X), can be defined by using the KT. divergence as the underlying measure of distance WWiinwright 2019 Equation 15.29)
X() == DKL (Q(x))) Q(x,r)
where, ((), is the joint distribution of the pair ((X, (X,Y), J). and Q( is the product of their marginals, and assume that Q = Q(x,y) == 1/M M P is the mixture distribution. We can rewrite the joint distribution (X,,Y), as follows:
Q(x,y), Q((, (x, (z, = -,,x,,) j).
Given that J chosen uniformly from (1....,M}, we have:
(J==))- M
So, we can rewrite the joint distribution follows:
Q(x,)), ((x, v), = Q((((,(X))) Y) = (z,8) J IJ= j)
= Po, (x, v) M
We 1. use the definition of KL divergence, 2. plug the value for the joint distribution into it and invoke the definition of KL divergence and perform some rewriting to get
v). log Q( ((r,))))
DKL (Q(,,)) Il Q(x.))))) = Σ ((x.)),((E,,)))...
(r.
Σ
1
1
Prs (2.1) Q (2, 3) x M
P M so (I,
(a.))
M
Σ
(PIe, Q(x,)))
M 1=1
where, Q(x.y) is the mixture distribution. Accordingly, I(J;Y[X) can be written in terms of component distributions ( . E [M] as follows:
1 M
I(JY((X) M
Σ (P [Q).
Intuitively, means the mean the KL divergence between P/es and Q- averaged over the choice of index j j-gives the mutual information. Furthermore, based on the definition of the KL divergence, we can conclude that for
DKL (F 1=)))
Accordingly, we can 1. employ the mixture distribution formula in the above equation, 2. use the convexity of the KL divergence and apply Jensen inequality and 3. use the linearity property of sum to obtain
M
M Σ
IJ;YIX) = M
Σ
DRL.
Pies
|l
Pior
M
Ø=1
k=
M
M
s
DRI.(PP (P (Port))
M
1=1
Σ
DKI. (PP::
|| PP
M
j,k=1
jfk
22

---

Published as a conference paper at ICLR 2025
Consequently, if we construct 28 28-packing set such that all two distinct pairs of distributions F/a, and f are close in average, then the mutual information can be controlled.
For the second claim, employ the previous view with the result of Lemma A.2 to get
M
IJJY S
n
DEL (T
P \//)))
M
J.A=1 JFk
as desired.
B.4 PROOF OF LEMMA A.5
Proof The aim of this proof establish an upper bound on the mutual information [(J; Y I"IX") "x"... for the 25- 25-packing within the neural network's space FB, To achieve this, we invoke the result of Lemma A.4 which establishes a connection between the mutual information and the KL divergence. We then apply the result obtained from Lemma A.3] Finally, we employ the same re-scaling procedure as demonstrated in Wainwright (2019 Example 15. 14) and Wainwright (2019) Example 15. 16) to construct 28-packing in such a way that, for suitable constant
(,),,, we ensure that p(fer e (x), f ex (z)) & 2nd holds for all pairs fex (x) and fex corresponding to j + k E [M].
We can 1. use the result provided by Lemma A.4 2. use the fact that Σ DKI P
(M) sup(((LLL k.j calculation, 5. use the fact that M 2 1, so 0 < (M- - 1)/M < 1, 6. use the view of Lemma A.3 norm, 8. employ the re-scaling procedure and 9. simplify the
(P)x)) )) for all j + E [M]. 3. calculate the permutation, 4. some arithmetic
invoke the definition of p
factor 2 to obtain
n S I(J:Y"Ix")
DKL (Tis || fPa))
M
J.k=1
jfk
n
(M)
(DKI (Pfftt)
sup j. j&k
M
2
n
M!
(DKL(P (P)r))
sup j,E, 5fk
M2 (M 2)1
n(M-1) 1)
(DKL(PI 11 [| j.MEM j7k
sup
M
(P/er 11
$ n sup s.E((M) jfk
a sup j.kE(M
(1 (Jei(a)) - So (x:)) (1)))))
2a
i7k
sup J.KE[M] (e((e(())
20
n(2ko)²
202
2n(R0)²
as desired.
23

---

Published as a conference paper at ICLR 2025
B.5 PROOF OF LEMMA A.8
Proof In this proof, we first define a rotation matrix R E SO(d), which belongs to the special orthogonal group. Then, based the fact that R R_1 write bj x = by R Rx
R (Rbx) Ræ. Accordingly, we can obtain
-RR)) 1 da.
p(b x: > 0,0,))
(2 Σ
(Rbb) Re>0
By defining G := Ra and b Rb; and da (dz/dG) x dG, we get
G Rx
l
dx
p(b 0)
x dG.
(2T)0/2
[ 57
G20
dG
Then, 1. by setting Σ RE (dx/dG)
R R
det(R)) and
by (l 12, 0, ...., 0) 2. by factoring out the term R]. the fact that the probability den-
sity function of Gaussian distribution for a random variable across its domain is I and 4. by noting that R 1, we can obtain
c $ c
pbb x 0) = (2T) d/2 /
R|G
Σ
b, G>0
R
-oTs lo
dG
(2T) d/2
Σ
b, 020
R
2
2
as desired.
B.6 PROOF OF LEMMA A.9
Proof In this proof, our objective is to compute (b x) x) x)), which is a crucial component of the proof presented in Lemma 3.2. helping establish lower bound for ReLU neural network. To achieve this, we can 1. employ the definition of expected value, 2. apply the definition of ReLU function, 3. perform some rewriting, take out b. and by, 5, employing Lemma A.8
6. employ the
definition of expectation, 7. apply the fact that E[(x:: [ Id, 8. apply by Ia by b by and 9. use
24

---

Published as a conference paper at ICLR 2025
bgg by obtain
B [ 2) m)]
(bb (b) a ((x))da
(b[ h( (x)d
==b]a>00 a>0
(b x))
h(x)d
bj
x h(x)dx be
Se:TTa>0
Sxx a.
da
6%
2 bk
E
bR
1
by
Ia
bk
2
by
2
1
2
as desired.
C EMPIRICAL DETAILS
Here, we first explain the two loss functions employed for training the networks in both classification and regression datasets and then we provide more details about the implementation settings.
C.I LOsS FUNCTIONS:
In the training process of ReLU networks, utilize two distinct loss functions implemented in TensorFlow: "mean Lecurre__ "ecureederorr""""""eeeeeeeerrr"" for regression and "categorical_co Seategorica_ccoosseetroyyy for classifica- follows:
tion. The details of these loss functions
Cross-entropy loss it (Murphy 2012
For classification purpose, we use (categorical) Cross-ent and define
Ho & Wooky 2019)
tcg (fe)
(w))))og((f((()))))
where (yi) is the ke-th element of the one-hot vector the target label for the i-th data sample and
(fo()))
pl p(fo(z);
m
((ee
where (fe()))) the k-th output of network indexed by e.
Mean-squared error For regression, we use Mean-squared and define it as (Botchkarev 2018)
(wi)) (fe(x))))
EMS (fe)
m
where (yr) is the k-th element of the target vector and (fe(x)) is the k-th output of a network indexed by @
25

---

Published as a conference paper at ICLR 2025
C.2 EXPERIMENTAL SETTING:
Here we provide further details about our implementations. We itemized these properties such as accessing the dataset, the computer resources, the environment, splitting data and on.
1. Computer resources: we conducted some of the experiments in Python using Google Colab and some them using the basic plan of deepnote (https://deppooe..com regression dataset, used the basic plan of them that utilizes a machine with 5GB RAM and 2vCPU. For the CIFARI0 dataset, we used one of the deepnote's ' plans that utilizes a machine with 16GB RAM and 4 vCPUs. It took about 8 hours. In fact, the computation time taken not great importance for this paper.
For the
2. Test and train splitting: for classification, we have worked with well-known datasets like MNIST, CIFARI0, and Fashion MNIST, MMSii, utilizing the packages that import
those datasets. Accordingly, our test and training data are exactly those provided by these datasets. For example, tensorf flosrrllow keras seaas.daten datasets package. For the housing dataset, we randomly di- vided the whole dataset, using 15 000 samples for training and the remaining samples for testing. Apart from this, as our aim this paper is to determine which of these curves can better model the generalization error as the number training data increases, we run the experiments (for example for NNSST dataset) in intervals of 500 samples, that is, we first use 500 samples, then 1000 samples, then 1500 samples, and forth. This choice of intervals gives us a detailed yet computationally feasible curve of the networks' performance as function of the sample size. ensure a significant amount of randomness multiple times, we randomly selected the required subset from our full training data. In our paper, the main trend of the test error as the number of training data increases is much more important than the specific eиrоr values themselves.
imported the Pashion-MNIST dataset from
3. Optimization method: in the training procedure for our experiments, we have used Adam optimization method.
4. Finding the values for the two curves (c2 3/n) and (01 + a/ nD): we use SLSQP method to find the parameters of those curves.
26


Reviews:
[{"review_id": "Cyi2TmnPRC", "reviewer": "Reviewer_ABGY", "summary": "This paper proposes to bound by below the minimax risk of a sub-class of ReLU Multi-Layer Perceptrons (MLP). This sub-class, denoted by $\\mathcal{B}\\_{\\mathrm{L}}$, is built as the $\\mathcal{L}^1$-ball of a given radius $v\\_{\\mathrm{s}}$ of the full space of parameters. The lower bound is obtained by using the packing number of $\\mathcal{B}\\_{\\mathrm{L}}$.", "questions": "There is little discussion about the number $n$ of samples that are needed to train a NN (only at lines 233-238). What are typical values for $n$?\n\nSee above:\n * experiments on toy datasets matching the assumptions?\n * motivation for finding a lower bound?\n * relevance of the comparison with [Taheri et al., 2021]?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "# Originality\n\nThis paper attempts to find a lower bound for the minimax risk, which is not common in the literature.\n\n# Clarity\n\nThe paper is easy to ready.\n\n# Quality\n\nThe proof seems to be sound (I did not check everything).", "weaknesses": "# Originality\n\nThe paper uses almost the same tools as in [1], including the $\\mathcal{L}^1$ regularization (which becomes the $\\mathcal{L}^1$ ball in the space of parameters). The covering number is replaced with the packing number.\n\n# Clarity\n\nThe motivation of finding such a lower bound is unclear: why would it be useful to get a lower bound on the minimax risk? What kind of information does it provide on the dataset, the function to approximate and the NN architecture?\n\nExcept it fits the framework of [1], what is the motivation for studying a subspace of MLPs defined by the $\\mathcal{L}^1$ ball in the space of parameters? Why not choosing another metric?\n\n# Significance\n\nUnclear motivation (see Clarity).\n\n# Quality\n\n## Sharpness of the bound\n\nAccording to the authors (see paragraph starting line 216), the lower bound is sharp, since it contains the same factors as the upper bound in [1]. Please note that the similarity between the two bounds is easily explained by the similarity of tools used.\n\nBut, very importantly, the bound in [1] is obtained with a loss with a strong $\\mathcal{L}^1$ regularization term. Why would it be relevant to compare the two bounds?\n\n## Interpretation of $V\\_{\\mathcal{F}}$\n\nIn paragraph starting line 216, the authors interpret $V\\_{\\mathcal{F}} = (v\\_{\\mathrm{s}} / L)^L$ as \"a product over the $\\mathcal{L}^1$-norm bounds of different layers in $\\mathcal{F}\\_{\\mathcal{B}\\_{\\mathrm{L}}}$\". This bound is obtained by performing an AM-GM inequality, which is known to be tighter when all the weight matrices have a similar $\\mathcal{L}^1$ norm. However, it may be very loose otherwise, and the proposed interpretation tends to become inaccurate.\n\n## Experiments\n\nThe authors have chosen to focus on experiments related to real-world data. This is undeniably useful, but the conditions of Theorem 2.2 are not fulfilled with such datasets. It would have been very useful to have results with a toy dataset, whose data are distributed in accordance to the assumptions (Gaussian inputs, outputs generated by a MLP, Gaussian noise...).\n\n\n# References\n\n[1] *Statistical guarantees for regularized neural networks*, Taheri et al., 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2kW5GGjC1l", "reviewer": "Reviewer_BYd5", "summary": "The paper establishes minimax lower bounds for deep ReLU feedforward neural networks in the context of regression. Of note, to establish such lower bounds, the paper establishes a lower bound on the packing number of a ReLU network function class.", "questions": "* Is it possible to get similar minimax rates if the input $x_i$ are subgaussian random vectors and/or noise are subgaussian?\n\n* In view of lemma 5 of [1] (an upper bound on the generalization error) and theorem 2.2 in the paper, could a similar minimax lower bound be established for a function class consisting of more general architecture (e.g. other lipschitz activations, containing convolutions, etc) where the norm of the layers are bounded and the entire model is lipschitz?\n\n[1] Mahsa Taheri, Fang Xie, & Johannes Lederer. (2020). Statistical Guarantees for Regularized Neural Networks.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The minimax lower bound for deep ReLU networks and the lower bound for the packing number of deep ReLU neural networks is novel and interesting.", "weaknesses": "*", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NOOI3ljba4", "reviewer": "Reviewer_R7Hh", "summary": "The paper focuses on analyzing the sample complexity of learning deep ReLU feed-forward networks that have a bounded elementwise $\\ell_1$ norm. The authors show that the minimax rate scales as $1/\\sqrt{n}$, where $n$ is the sample size, and back up their theoretical claims with experimental results.", "questions": "See weakness section above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-\tThe problem of understanding the sample complexity of learning neural networks is an Important research topic.\n-\tThe research presents a minimax lower bound for deep neural networks, which seems to be new.", "weaknesses": "-\tIt is not very clear to me why one should compare the results with $1/n$ rate. Based on my understanding, to achieve $1/n$ rate one often needs more structural assumptions on the target function, such as the ground-truth is spare in spare linear regression setting. Given that there is no such structural assumption in the paper, I’m not sure why one would expect such $1/n$ rate to happen.\n-\tThe considered function space is elementwise $\\ell_1$ norm bounded, which is not a very commonly considered setting.\n-\tThe lower bound has an exponential dependency on $L$, which is not ideal though it is understandable that there might be technical difficulties to remove this.\n-\tIt is not very clear to me the experiment setup is the right way to verify the correctness of the bound. These bounds are asymptotic bounds, meaning that the rate are only meaningful when $n$ is large enough. \nFirst, in the current scale of $n$, the difference between $\\sqrt{n}$ and $n$ are not very significant. \nSecond, the way of fitting the curve seems to consider all the data points, including those relatively small $n$. I believe such curve could not correctly represent the correct decaying rate.\nMoreover, I believe these bounds in fact also depend on the norm of weight matrices.  It is possible the norm increases when $n$ increases, which could also affect the rate.\n-\tThe experiment results many also affect by the optimization-related factors, for example converging to a local minima. These factors related to optimization are not considered in the theory, so it seems hard to draw conclusions from experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "chh2tARcJn", "reviewer": "Reviewer_5XLe", "summary": "The authors establish a lower bound on the packing number for deep ReLU networks with L1 constraints on the weights. Then they use the packing number bound and Fano’s inequality to provide a minimax risk lower bound that scale as sqrt(log(d)/n). \n\nThe rate of 1/sqrt(n) has been established in a few other settings for neural networks (shallow feedforward networks, linear networks), but not for deep neural networks with non-linear activations.\n\nOne of the main implications is the separation between this bound and the known minimax rates for linear methods which scale as 1/n. \n\n The authors provide some empirical support to their analysis, by experimenting with small datasets and networks, fitting O(1/n) and O(1/sqrt(n)) curves and showins that the latter achieves smaller residuals.\n\nThe question remains open on whether with specific data-dependent and algorithm-dependent assumptions 1/n is feasible in practical applications of neural networks.", "questions": "1. Can you come up with some conditions under which the lower bound O(1/sqrt(n)) is actually not valid? For example, what is your intuition about the optimal rate for different architectures? What do you expect for the case when \\sigma=0?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Importantly the bound depends on the logarithm of the input dimension, d, and scales as 1/sqrt(n) matching comparable upper bounds. While this type of bound exists before, it had not been established for deep, non-linear networks. \n\nGreat clarity, organization and writing.", "weaknesses": "1. Some of the writing is missing clarity and could be rewritten in a more straightforward fashion. \n- The sentences in lines 38-43\n- The sentences in lines 120-123.\n\n2. [Minor] In your proof sketch of Section 4, please properly introduce random variable J (it is only introduce in the appendix).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)