Learning ReLU networks to high uniform accuracy is intractable
Authors: Julius Berner
Philipp Grohs
Felix Voigtlaender
Venue: ICLR 2023 poster (2023)
Keywords: learning theory
ReLU networks
hardness results
sample complexity
teacher-student learning

Abstract: Statistical learning theory provides bounds on the necessary number of training samples needed to reach a prescribed accuracy in a learning problem formulated over a given target class. This accuracy is typically measured in terms of a generalization error, that is, an expected value of a given loss function. However, for several applications --- for example in a security-critical context or for problems in the computational sciences --- accuracy in this sense is not sufficient. In such cases, one would like to have guarantees for high accuracy on every input value, that is, with respect to the uniform norm. In this paper we precisely quantify the number of training samples needed for any conceivable training algorithm to guarantee a given uniform accuracy on any learning problem formulated over target classes containing (or consisting of) ReLU neural networks of a prescribed architecture. We prove that, under very general assumptions, the minimal number of training samples for this task scales exponentially both in the depth and the input dimension of the network architecture.

Published as a conference paper at ICLR 2023
LEARNING RELU NETWORKS TO HIGH UNIFORM ACCURACY IS INTRACTABLE
Julius Berner 1.* Philipp Grohs 1.2.3.+ 1.23. and Felix Voigtlaender
Faculty of Mathematics, University of Vienna, Austria Research Network Data Science @ Uni Vienna, University of Vienna, Austria RIIAM,, Austrian Academy of Sciences, Austria Mattheattcall Institute for Machine Learning and Data Science (MIDS), Catholic University of Bichstätt-Ingolstadee Germany
All authors contributed equally
ABSTRACT
Statistical learning theory provides bounds on the necessary number of training samples needed to reach prescribed accuracy in lcarning problem formulated over a given target class. This accuracy is typically measured in terms of a gen- eralization error, that is, expected value of a given loss function. However, for several applications - for example in security-critical context or for problems in the computational sciences one would like to have guarantees for high accuracy on every input value, that is, with respect to the uniform norm. In this paper we precisely quantify the number of training samples needed for any conceivable training algorithm to guarantee a given uniform accuracy on any learning problem formulated over target classes containing (or consisting of) ReLU neural networks of a prescribed architecture. We prove that, under very general assumptions, the minimal number of training samples for this task scales exponentially both in the depth and the input dimension of the network architecture
accuracy in this sense is not sufficient. In such cases,
INTRODUCTION
The basic goal of supervised learning is to determine a function u u [0, 1] - R from (possibly noisy) samples (u(z1),... ... u(*m)). As the function can take arbitrary values between these samples, this problem is, of course, not solvable without any further information on u. In practice, one typically leverages domain knowledge to estimate the structure and regularity of u priori, for instance, in terms of symmetries, smoothness, or compositionality. Such additional information can be encoded via suitable target class U c C([O, 1] that is known be member of. We are interested in the optimal accuracy for reconstructing u that can be achieved by any algorithm which utilizes point samples. To make this mathematically precise, we assume that this accuracy is measured by a norm | a| of suitable Banach space Y = U. Formally, an algorithm can thus be described by map A U Y that can query the function u at m points x, and that outputs a function A(u with A(u) u (see Section 2.1 for precise definition that incorporates adaptivity and stochasticity). We will be interested upper and lower bounds on the accuracy that can be reached by any such algorithm - -equivalently, we are interested in the minimal number m of point samples needed for any algorithm achieve given accuracy for every E U. This m would then establish fundamental benchmark on the sample complexity (and the algorithmic complexity) of learning functions in U to a given accuracy.
The choice of the Banach space Y y in other words how measure accurucy is very crucial here. For example, statistical learning theory provides upper bounds on the optimal accuracy in terms of an expected loss, i.c., with respect to Y ([0, 1]" dP), where IP is (generally unknown)
In what follows, the input domain [0, 1f could be replaced by more general domains (for example Lipschitz domains) without any change in the later results. The unit cube [0, 1]dd is merely chosen for concreteness.

---

Published as a conference paper at ICLR 2023
M
1.0
0.96
model
target
0.88
sampless
0.9
0.90
0
0.8
0.72
-0.3 0.0
0.3
0.110
0.112
0.114
0.116
0.068
0.072 0.076
Figure 1: Even though the training of neural networks from data samples may achieve small error on average, there are typically regions in the input space where the pointwise error is large. The target function in this plot is given by x log(sin (og(sin(50z)) and the model is a feed-forward neural network. It is trained on m = 1000 uniformly distributed samples according the hyperparameters in Tables I and 2 and achieves final L and L L errors of 2.8 10 and 0.19, respectively. The middle and right plots are zoomed versions of the left plot.
2) + sin(5x)) (based on Adcock & Dexter 2021)
data generating distribution (Devroye al., 2013 Shalev-Shwartz & Ben-David 2014 Mohri et al., 2018; Kim et al. 2021). This offers a powerful approach to ensure a small average reconstruction error. However, there are many important scenarios where such bounds on the accuracy are not sufficient and one would like to obtain an approximation of u that is close to u not only on average, but that can be guaranteed
be close for every x E [0, 17 This includes several applications in the sciences, for example in the context of the numerical solution of partial differential equations (Raissi et al., 2019 Han et al., 2018 Richter & Berner 2022), ) any security-critical application, for example, facial ID) authentication schemes (Guo & Zhang 2019), , as well as any application with a distribution-shipe shift, i... where the data generating distribution is different from the distribution in which the accuracy is measured (Quiioneo-oCami efficiently solved if there exists an efficient algorithm A that achieves uniform accuracy, i.e., a small error supweu [u A(u)) ([u,1])) with respect the uniform norm given by Y = L ([0, 11"), i.e.,
et al. 2008). Such applications can only be
|l [. = esssup:efo.1j=]]f
Inspired by recent successes of deep learning across a plethora of tasks in machine learning (LeCun) et al. 2015) and also increasingly the sciences (Jumper et al., 2021 Pfau et al., 2020). will be particularly interested in the case where the target class U consists of or contains - realizations of forwar) neural networks of specific architecture") Neural networks have been proven and observed to be extremely powerful in terms of their expressivity, that is, their ability to accurately approximate large classes of complicated functions with only relatively few parameters (Elbrächter et al. 2021 Berner et al.) 2022). However, it has also been repeatedly observed that the training of neural networks (e.g., fitting neural network data samples) high uniform accuracy presents a big challenge: conventional training algorithms (such as SGD and its variants) often find neural networks that perform well on average (meaning that they achieve a small generalization error), but there are typically some regions in the input space where the error is large (Fiedler et al. [023); see Figure [] for an illustrative example. This phenomenon has been systematically studied on an empirical level by Adcock & Dexter (021). It is also at the heart of several observed instabilities in the training of deep neural networks, including adversarial examples (Szegedy et al. 2013 Goodfellow et al. 2015) or so-called hallucinations emerging in generative modeling, e.g., tomographic reconstructions (Bhadra et al. 2021 or machine translation (Müller et al.) 2020).
Note that additional knowledge the target functions could potentially help circumvent these issues, see Remark 1.3 However, for many applications, is not possible to precisely describe the regularity of the target functions. We thus analyze the case where no additional information is given besides the fact that one aims to recover a (unknown) neural network of a specified architecture and regularization from given samples- i.e., we assume that U contains a class of neural networks of given architecture, subject to various regularization methods. This is satisfied in several applications of interest, e.g.. model extraction attacks (Tramer et al. 2016;
He He et al. (022) and teacher-student settings (Mirzadch) et al. 2020 Xie et al. 2020). It is also in line with standard settings in the statistical query literature,
By architecture we mean the number of layers I., as well the number of neurons in each layer.
2

---

Published as a conference paper at ICLR 2023
in neural network identification, and in statistical learning theory (Anthony & Bartlett 1999
Mohri
iet al. 2018), see Section 1.1
For such settings we can rigorously show that learning class of neural networks is prone to instabilities. Specifically, any conceivable learning algorithm (in particular, any version of SGD), which recovers the neural network to high uniform accuracy, needs intractably many samples.
Theorem 1.1. Suppose that U contains all neural networks with d-dimensional input, ReLU activa- tion function, I layers of width up to 3d, and coefficients bounded by e in the ea norm. Assume that there exists an algorithm that reconstructs all functions U to uniform accuracy e from m point samples. Then, we have
m
Ω 32d
where
Ω
8.3
ct d'=²
i 2
1 c (3d) (1-1)
if 2.
48
Theorem 1.1 is special case of Theorem 2.2 (covering Y = ["O, 17() for all e [1, 2x). as well
as network architectures with arbitrary width) which will be stated and proven in Section 2.3
To give concrete example, we consider the problem of learning neural networks with ReLUU activation function, I. layers of width at most 3d. and coefficients bounded by e to uniform accuracy 8 1/1024, According to our results we would need at least
m > 2d Cيع . (3d))(L-2)
many samples- the sample complexity thus depends exponentially on the input dimension d, the network width, and the network depth, becoming intractable even for moderate values of d, c, L (for d = 15, c= 2, and == 7, the sample size m would already have to exceed the estimated number of atoms in our universe). If, on the other hand, reconstruction only with respect to the T.2 norm were required, standard results in statistical learning theory (see, for example, [Berner al. 2020) show that m only needs to depend polynomially on d. We conclude that uniform reconstruction is vastly harder than reconstruction with respect the L norm and, in particular, intractable. Our results are further corroborated by numerical experiments presented in Section 3 below.
For other target classes U. uniform reconstruction is tractable (i.e., the number of required samples for recovery does not massively exceed the number of parameters defining the class). A simple example are univariate polynomials of degree less than which can be exactly determined from m samples. One can show similar results for sparse multivariate polynomials using techniques from the field of compressed sensing (Rauhut 2007y. Further, one can show that approximation rates in suitable reproducing kernel Hilbert spaces with bounded kernel can be realized using point samples with respect to the uniform norm (Pozharska & Ullrich 2022). Our results uncover an opposing behavior of neural network classes: There exist functions that can be arbitrarily well approximated (in fact, exactly represented) by small neural networks, but these representations cannot be inferred from samples. Our results are thus highly specific to classes of neural networks.
Remark 1.2.
Remark 1.3. Our results do not rule out the possibility that there exist training algorithums for neural networks that achieve high accuracy on some restricted class of target functions, if the knowledge about the larget class can be incorporated inlo the algorithm design. For example, if it were known that the targel function can be efficiently approximated by polynomials one could first compute an approximating polynomial (using polynomial regression which is tractable) and then represent the approximating polynomial by neural network. The resulting numerical problem would however be very different from the way deep learning used in practice, since most neural network coefficients (namely those corresponding to the approximating polynomial) would be fixed a priori. Our results apply to the situation where such additional information on the target class U not available and no problem specific knowledge is incorporated into the algorithm design besides the network architecture and regularization procedure.
We also complement the lower bounds of Theorem I.I with corresponding upper bounds.
Theorem 1.4. Suppose that U consists of all neural networks with d-dimensional input, ReLU activation fariconfuuttiin function, L. layers of width at most B, and coefficients bounded by e in the l norm. Then, there exists an algorithm that reconstructs all functions in U to uniform accuracy from m point samples with
ifq < 2
m & C'd. where C==
d'' c. -((-11(1-2)
ff 2.
3

---

Published as a conference paper at ICLR 2023
Theorem 1.4 follows from Theorem 2.4 that will be stated in Section 2.4 We refer to Remark B.4 a discussion of the gap between the upper and lower bounds.
Remark 1.5. Our setting allows for an algorithm to choose the sample points (I1,.... Im) in an adaptive way for each u e U; see Section for a precise definition of the class of adaptive (possibly randomized) algorithms. This implies that even a very clever sampling strategy (as would be employed in active learning) cannol break the bounds established in this paper.
Remark 1.6. Our results also shed light on the impact of different regularization methods. While picking a stronger regularizer (e.g. a small value of q) yields quantitative improvements (in the sense of smaller Ωt), the sample size m required for approximation in L can still increase exponentially with the input dimension d. However, this scaling is only visible for very small e.
1.1 RELATED WORK
Several other works have established "hardness" results for neural network training. For example, the seminal works by Blum & Rivest (1992); Vu (1998) show that for certain architectures the training process can be Nocollltee By contrast, our results do not directly consider algorithm runtime at all: our results are stronger in the sense of showing that even if it were possible to efficiently learn a neural network from samples, the necessary number of data points would be too large to be tractable.
We also want to mention a series of hardness results in the setting of statistical query (SQ) algorithms. see, e.g., Chen et al. (2022); Diakonikolas et al.] (2020); [ooe et al.] (2020b); Reyzin (2020): [Song] et al. (2017). For instance, Chen et al. (2022) shows that any SQ algorithm capable of learning ReLU networks with two hidden layers and width poly(d) up to L error 1/poly(d) must use a number of samples that scales superpolynomially in d. or must SQ queries with tolerance smaller than the reciprocal of any polynomial in d. In such SQ algorithms, the learner has access to an oracle that produces approximations (potentially corrupted by adversarial noise) of certain expectations E[h(X, (. where u is the unknown function to be learned, X is a random variable representing the data, and h is function chosen by the learner (potentially subject to some restrictions, e.g. Lips- chitz continuity). The possibility of the oracle to inject adversarial (instead of just stochastic) noise into the learning procedure which does not entirely reflect the typical mathematical formulation of learning problems- is crucial for several of these results. We also mention that due to this possibility of adversarial noise, not every gradient- based optimization method (for instance, SGD) strictly speaking an SQ algorithm; see also the works by Goel et al. (2000a) Page 3) and Abbe et al. (2021) for a more detailed discussion.
There also exist hardness results for learning algorithms based on label queries (i.e., noise-free point samples), which constitutes a setting similar to ours. More precisely. [Chen et al.] (2022) show that ReLU neural networks with constant depth and polynomial size constraints are not efficiently learnable up to small squared loss with respect to a Gaussian distribution. However, the existing hardness results are in terms of runtime of the algorithm and are contingent several (difficult and unproven) conjectures from the area of cryptography (the decisional Diffie-Hellman assumption or the "Learning with Errors" assumption); the correctness of these conjectures in particular would imply that P + NP. By contrast, our results are completely free of such assumptions and show that the considered problem
informatioontheorrticci
hard, not just computationally.
As already hinted at in the introduction, our results further extend the broad literature on statistical learning theory (Anthony & Bartleu 1999; Vapnik| [999; Cucker & Smale, 2002b Bousquet et al. 2003; Vapnik 2013) Mohri et al.) 2018). Specifically, we provide fully explicit upper and lower bounds on the sample complexity of (regularized) neural network hypothesis classes. In the context of PAC learning, we analyze the realizable case, where the target function is contained in the hypothesis class (Mohri et al.) 2018 Theorem 3.20). Contrary to standard results, we do not pose any assumptions, such as IID), on the data distribution, and even allow for adaptive sampling. Moreover, we analyze the complexity for all L norms with p E [1, oo]. whereas classical results mostly deal with the squared loss. As an example of such classical results, we mention that (bounded) hypothesis classes with finite pseudodimension D can be learned to squared L loss with O(De point samples; see e.g.. Moohr et al. (2018) Theorem 11.8). Bounds for the pseudodimension of neural networks are readily available in the literature; see e.g., Bartlet et al. (2019). These bounds imply that learning ReLU networks in 7,2 is tractable, in contrast the 1, setting.
4

---

Published as a conference paper at ICLR 2023
Another related area is the identification of (equivalence classes of) neural network parameters from their input-output maps. While most works focus on scenarios where one has access to an infinite number of queries (Fefferman & Markel, 1993] Vlačíć & Bölcskei 2022), there are recent results employing only finitely many samples RRlnick & Kording, 2020 Fiedler et al., 2023 Robust identification of the neural network parameters is sufficient to guarantee uniform accuracy, but it is not a necessary condition. Specifically, proximity of input-output maps does not necessarily imply proximity of corresponding neural network parameters (Berner al. 2019). More generally, our results show that efficient identification from samples cannot be possible unless (as done in the previously mentioned works) further prior information incorporated. In the same spirit, this restricts the applicability of model extraction attacks, such as model inversion evasion allacks (Tramèr et al. 2016,1 He et al.) 2022).
Our results are most closely related to recent results by Grohs & Voigtlaender (2021) where target classes consisting of neural network approximation spaces are considered. The results of oforros & Voigtlaender 2022), however, are purely asymptotic. Since the asymptotic behavior incurred by the rate is often only visible for very fine accuracies, the results of Grors & Voigtlaender (202T) cannot be applied to obtain concrete lower bounds the required sample size. Our results completely explicit in all parameters and readily yield practically relevant bounds. They also elucidate the role of adaptive sampling and different regularization methods.
1.2 NOTATION
For E N, we denote by C[[0.1]4) the space of continuous functions f: [0, 1J R. For a finite set I and (at)ee E R', we write Y.E/ a; == ExEr a, For m N, we write [m]] == {1..... m). For A Rd, denote by A the set of interior points of A. For any subset A of vector space V. any ee IR, and any y E V, we further define y + c == {y + ca: a A}. For a matrix W RR" xk and q e [1, we write We (E,, (") 1/9 and for q = oo we write [Wlle= == max,, [Well- For vectors E R", we use the analogously defined notation z0.
MAIN RESULTS
This section contains our main theoretical results. We introduce the considered classes of algorithms in Section 2.1 and target classes in Section 2.2 Our main lower and upper bounds are formulated and proven Section 2.3 and Section 2.4, respectively.
2.1 ADAPTIVE (RANDOMIZED) ALGORITHMS BASED ON POINT SAMPLES
As described in the introduction, our goal is to analyze how well one recover unknown function u from a target class in Banach space Y based on point samples. This is one of the main problems in information- seaadd complexity (Trabb. 2003), and in this section we briefly recall the most important related notions.
Given U < C(JO, 17d) o Y for a Banach space Y, we say that map A : U - Y is adaptive deterministic method using m E N point samples if there are fi E [0, 1]d and mappings
f:: (1O, 179)² 1-1
R [0,
i= 2..., ....., m, and Q (IO, 174) m
such that for every u U. using the point sequence x(u) (I1,..., Tm) = [0. 1]s defined as
I1 = fI, x; = f((x),,... Ii u(x1) u();-1)), i i= 2,..,,, m,
(I)
the map A is of the form A(u) =
Im, u(x ( u(zm)) e
The set of all deterministic methods using m point samples is denoted by Alg (U,Y). ). In addition to such deterministic methods, we also study randomized methods defined as follows: A tuple (A, m) called an adaptive random method using m e N point samples on average if A (Aw)ee where (2, F, PP) is probability space, and where m Ω - N is such that the following conditions hold:
1. is measurable, and E. [[m] & m;
2. V E U w Aw(u) is measurable with respect the Borel olalgerra on Y;
5

---

Published as a conference paper at ICLR 2023
3. V E Ω: As (U,Y)
The set of all random methods using point samples on average will be denoted by Algm since such methods are sometimes called Monte-Carlo (MC) algorithms.
MC (U, (U,))
For target class U, we define the optimal (randomized) error as
ert m
MC (U,Y) = (A.m)e M (U.Y) (UAY Net
inf
sup EE E Au(u)l)]
(2)
We note that Alg YU ( Algm randomized method over a trivial probability space.
MMMCCU MC (U, Y), since each deterministic method can interpreted as a
2.2 NEURAL NETWORK CLASSES
We will be concerned with target classes related to ReLU neural networks. These will be defined in the present subsection. Let o I R, e(a:) max(0, ar, be the ReLU activation function. Given depth L E N, an architecture (No, ,,, Nr.) v.)=
E N2+1, and neural network coefficients
((W) b)) L [- E x _ NRNN x xRR))
we define their realization R(Φ) E C(R No, R R as
R( = 0L g 0 o....oo
where is applied componentwise and s²: Ni- - R.N, x Wir + b. for i [L]. Given 0 and E [1, oo], define the class
M. N2). { R(()) $ X (R.NINNI- x RR.)) and |boleer & =c.
where || := maxisiet max maxx||WW'la [ebr)
To study target classes related to neural networks, the following definition will be useful. Definition 2.1. Let U, H c C([0, ). We say that U contains copy H. H. attached to E U with
constant Co (0), uu Cu H U.
2.3 LOWER BOUND
The following result constitutes the main result of the present paper. Theorem 1.1 readily follows from as a special case.
Theorem 2.2. Let L N,3. d, N. p.g e [1, and c E (0, Suppose that the target class U c C(10, 114) contains a copy of H BB.I....B.).. with constant co E (0, c0), where the B in
B d} we have (d, B..., B, 1) appears times. Then, for any e N with s & min 3
Ω
err err (U, I.(((, 11 > co (32s)
where
ch. 1 if <
Ω = 8.3 c (l1-1)(1
1)(-
if
Proof.
This follows by combining Theorem
A.5 with Lemmas
A.2 and A.3 in the appendix.
Remark 2.3. For p & sc, the bound from above does not necessarily imply that an intractable number of training samples is needed. This is reflection of the fact that efficient learning is possible (at least if one only considers the number of training samples and not the runtime of the algorithm) in this regime. Indeed, it well-known in statistical learning theory that one obtains learning bounds based the entropy numbers (w.r.t. the L norm) of the class of target functions, when the error is measured in L?, see, for instance, Cucker Smale of class of neural networks with L. layers and (bounded) weights scale linearly in w, L. and
Smale) (2002al Proposition 7). The E-entropy numbers

---

Published as a conference paper at ICLR 2023
logarithnically in 1/c, that one gets tractable L learning bounds. By interpolation for LP norms (noting that in our case the target functions are bounded. so that the L reconstruction error is bounded, even though the decay with m is very bad), this also implies L learning bounds, but these get worse and worse as c.. We remark that these learning bounds are based on empirical risk minimization, which might be computationally infeasible (Vul 1998); since our lower bounds should hold for any feasible algorithm (irrespective of its computational complexity), this means that one cannot expect to get an intractable lower bound for p < in our setting.
The idea of the proof of Theorem 2.2 (here only presented for uy and d, which implies that B 2 3d) is as follows:
1. We first show (see Lemmas A.2 and A.3 that the neural network set H (d.. B,1).e contains
a large class of ''bump functions" of the form Ả MM Here, 1 M. ay is supported on the set M 4/p, where M E N and y [0, 1] can be
y -+I- - 1d and satisfies |0 M. ([o.,]]] chosen arbitrarily; see Lemma A.1 The size of the scaling factor À X(M, c, q. d, L) depends crucially on the regularization parameters c and This is the main technical part of the proof, requiring construct suitable neural networks adhering the imposed ( restrictions the weights for which À is as big as possible.
2. If one learns using m points samples 21..... Im and if M = (m (m))))) then a volume packing argument shows that there exists y E [0, 1J such that i M.,( = 0 for all E [m]]. This means that the learner cannot distinguish the function A I Oay E H. (d.B....B..). from the zero function and will thus make an error of roughly ||A 1A-0M.ylL=* = X- M ddyp This already implies the lower bound in Theorem 2.2 for the case of deterministic algorithms.
3. To get the lower bound for randomized algorithms using m point samples on average, employ technique from information-base complexity (see, e.g., Heinrich| 1994): We again set M = Om 1/4) and define (ye (EM) as the nodes of a uniform grid on [0, 1 with width 2/M. Using a volume packing argument, we then show that for any choice of m sampling points 3 ... Im, "at least half of the functions 1 M.ye avoid all the sampling points", i.e., for least half of the indices f, it holds that a. (Ira) = for all i E [m]] A learner using the samples I1, ......... Jm Fm can thus not distinguish between the zero function and X UM Hid.B,...B.BU
for at least half the indices f. Therefore, any deterministic algorithm will make an error of Ω(A M-1/p) on average with respect to l.
4. Since each randomized algorithm A (Aw)weR is a collection of deterministic algorithms and since taking an average commutes with taking the expectation, this implies that any randomized algorithm will have an expected error of ?(A . M-4/p) on average with respect to This easily implies the stated bound.
As mentioned in the introduction, we want to emphasize that well-trained neural networks can indeed exhibit such bump functions, see Figure and Adcock & Dexter (202T): Fiedler et al. (2023)
2.4 UPPER BOUND
In this section we present our main upper bound, which directly implies the statement of Theorem Theorem 2.4. Let de N, q E [l, oo], e 00), and Ni....,NL-S N. Then, we have
1.4
Vd..c" ch. m
if < 2 if > 2.
enr (HL
L (101 & cd -.d.N.....M - mm=
Proof. This follows by combining Lemmas B.2 and B.3 in the appendix.
Let us outline the main idea of the proof. We first show that each neural network R()) H.
HoN......NN.. N2). is Lipschitz-coninnuuus, where the Lipschitz constant can be conveniently
bounded in terms of the parameters No...., NN, c, q. Lemma B.2 in the appendix. In Lemma B.3 we then show that any function with moderate Lipschitz constant can be reconstructed from samples by piecewise constant interpolation.
7

---

Published as a conference paper at ICLR 2023
3 NUMERICAL EXPERIMENTS
Having established fundamental bounds on the performance of any learning algorithm, we want to numerically evaluate the performance of commonly used deep learning methods. To illustrate our main result in Theorem 2.2 we estimate the error in (2) by tractable approximation in a student-teacher setting. Specifically, we estimate the minimal error over neural network target functions ("teachers") Ō =H Hid. No.1., for deep learning algorithms À Algm. (U, (?) via Monte-Carlo sampling, i.e.,
cTTm (U.LP; == inf inf (A.))e suPeet Euee (Ineny) (u(X,) - (x3))) 1/2
(3)
where (xz) are independent evaluation samples uniformly distributed on [-0.5, 0.5] and Ω represents the seeds for the algorithms.
We obtain teacher networks u E H N...N. 1.1).e
by sampling their coefficients componentwise according to a uniform distribution on [-c,c]. c]. For every algorithm (A, m) E Å and seed w E î we consider point sequences x(u) s(u) uniformly distributed in [-0.5, 0.5] with m(w)
The
corresponding point samples are used to train the coefficients of neural network ("student") using the Adam optimizer (Kingma & Ba 2015) with exponentially decaying learning rate. We consider input dimensions d = 1 and = 3, for each of which we compute the error in (3) for 4 different sample sizes m over 40 teacher networks u. For each combination, we train student networks with 3 different seeds, 3 different widths, and 3 different batch-sizes. In summary, this yields 2 4 4-000--- 3- 3- 8640 experiments each exccuted on a single GPU. The precise hyperparameters can be found in Tables 1 and 3 in Appendix C
Figure 2 shows that there is a clear gap between the errors errm m (Ū, TP; Å) pe (1,2} and p oc.
Especially in the one-dimensional case, the rate err.. (Ū, L.; A) w.r.t. the number of samples m also seems to stagnate at a precision that might be insufficient for certain applications. Figure 3 iillustrates that the errors are caused by spikes of the teacher network which are not covered by any sample. Note that this is very similar to the construction in the proof of our main result, see Section 2.3
In general, the rates worsen when considering more teacher networks Ô and improve when consider- ing further deep learning algorithms Å, including other architectures or more elaborate training and sampling schemes. Note, however, that each setting needs to be evaluated for a number of teacher net- works, sample sizes, and seeds. We provide extensible implementation"" in PyTorch (Paszke et al. 2019) featuring multi-node experiment execution and hyperparameter tuning using Ray Tune {Liaw al. 2018), experiment tracking using Weights & Biases and TensorBoard, and flexible experiment configuration. Building upon our work, research teams with sufficient computational resources can provide further numerical evidence on an even larger scale.
DISCUSSION AND LIMITATIONS
Discussion. We derived fundamental upper and lower bounds for the number of samples needed for any algorithm to reconstruct an arbitrary function from target class containing realizations of neural networks with ReLU activation function of given architecture and subject Ed regularization constraints on the network coefficients, see Theorems 2.2 and 2.4 These bounds are completely explicit in the network architecture, the type of regularization, and the norm in which the reconstruc- tion error is measured. We observe that our lower bounds are severely more restrictive if the error is measured in the uniform 00 norm rather than the (more commonly studied) L norm. Particularly, learning class of neural networks with ReLU activation function with moderately high accuracy in the 1 norm is intractable for moderate input dimensions, as well as network widths and depths. We anticipate that further investigations into the sample complexity of neural network classes can eventually contribute to a better understanding of possible circumstances under which it is possible to design reliable deep learning algorithms and help explain well-known instability phenomena such
TT have centered input data, we consider the hypereuhe [ 0.5, in our experiments. Note that this does not change any of the theoretical results.
"The code can be found at httpp////ettaa..ccc/////aaaaaeee
8

---

Published as a conference paper at ICLR 2023
d
d
1
10
1.2
12
10
10
10"3
102 10'
102
102
10
10P
Figure 2: Evaluation of the enror in 3 for 21, 90). input dimensions E {1, sample sizes
m E (10?, 10², 10*, 10%), and hyperparameters given in Tables and
0.064
model
0112
target
0.120
0.060
samples
0.08
0.118
0.112
0.022
-0.35
0.200
-0.175
Figure 3: Target function ("teacher"), samples, and model the deep learning algorithm ("student") attaining the min-max value in (3) for m 100 and o0 in the experiment depicted in Figure 2 The middle and right plots are zoomed versions the left plot. The L error (2.7 10-3) is about one magnitude larger than the L and I errors (3.9 10-1 and 2.4 10-1), which is caused by spikes of the teacher network between samples.
adversarial examples. Such understanding can be beneficial in assessing the potential and limitations of machine learning methods applied to security- and safety-critical scenarios.
Limitations and Outlook. We finally discuss some possible implications and also limitations of work. First of all, results are highly specific to neural networks with the ReLU activation func- tion. We expect that obtaining similar results for other activation functions will require substantially new methods. We plan investigate this in future work.
The explicit nature of our results reveal discrepancy between the lower and upper bound, especially for high dimensions. We conjecture that both the current upper and lower bounds not quite optimal. Determining to which extent one can tighten the bounds is an interesting open problem.
Our analysis a worst-case analysis in the sense that show that for any given algorithm A, there exists at least one u in our target class on which A performs poorly. The question of whether this poor behavior is actually generic will be studied in future work. One way establish such generic results could be to prove that our considered target classes contain copies of neural network realizations attached to many different u's.
Finally, we consider target classes U that contain all realizations of neural networks with given architecture subject to different regularizations. This can be justified as follows: Whenever a deep learning method is employed to reconstruct function by representing it approximately by a neural network (without further knowledge about u), natural minimal requirement that the method should perform well if the sought function is in fact equal to a neural network. However, if additional problem information about u can be incorporated into the learning problem it may be possible to overcome the barriers shown in this work. The degree which this is possible, well as the extension of our results to other architectures, such as convolutional neural networks, transformers, and graph neural networks will be the subject of future work.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The research of Julius Berner was supported by the Austrian Science Fund (FWF) under grant 13403-N32 and by the Vienna Science and Technology Fund (WWTF) under grant ICT19-041. The computational results presented have been achieved in part using the Vienna Scientific Cluster (VSC). Felix Voigtlaender acknowledges support by the DFG in the context of the Emmy Noether junior research group VO 2594/1-1.
REFERENCES
E. Abbe, P. Kamath, E. Malach, C. Sandon, and N. Srebro. On the power of differentiable learning versus PAC and SQ learning. Advances in Neural Information Processing Systems, 34:24340- 24351, 2021.
Ben Adcock and Nick Dexter. The gap between theory and practice function approximation with deep neural networks. SIAM Journal on Mathematics of Data Science, 3(2):624 655, 2021.
Martin Anthony and Peter L Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1): 2285-2301, 2019.
Julius Berner, Dennis Maximilian Elbrächter, and Philipp Grohs. How degenerate is the parametriza- tion of neural networks with the relu activation function? Advances in Neural Information Processing Systems, 32, 2019.
Julius Berner, Philipp Grohs, and Arnulf Jentzen. Analysis the generalization error: Empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of
partial differential equations. SIAM Journal on Mathematics of Data Science, 2(3):331-657) 2020.
Julius Berner, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. The Modern Mathematics of Deep Learning, pp. 1-111. Cambridge University Press, 2022.
Sayantan Bhadra, Varun Kelkar, Frank Brooks, and Mark A Anastasio. On hallucinations in tomographic image reconstruction. IEEE transactions medical imaging, 40(11):3249-3266, 2021.
Avrim L Blum and Ronald L Rivest. Training a 3-node neural network is NP-complete. Neural Networks, 5(1):1 17-127, 1992.
Edward K Blum and Leong Kwan Li. Approximation theory and feedforward networks. Neural networks, 4(4):511-515, 1991.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer School Machine Learning, pp. 169-207, 2003.
S. Chen, A. Gollakota, A. R. Klivans, and R. Meka. Hardness of noise-free learning for two-hidden- layer neural networks. arXiv preprint arXivv2202.05255, 2022.
Cucker and S. Smale. On the mathematical foundations of learning. Bull. Amer. Math. Soc. (N.S.), 39(1):1 49, 2002a. ISSN 0273-0979.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American Mathematical Sociery, (9(1):1 2002b.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
I. Diakonikolas, D. Kane, and N. Zarifis. Near-optimal SQ lower bounds for agnostically learning halfspaces and ReLUs under Gaussian marginals. Advances in Neural Information Processing Systems, 33:13586- 33:13586-13566 13596, 2020.
10

---

Published as a conference paper at ICLR 2023
Dennis Elbrüchter, Dmytro Perekrestenko, Philipp Grohs, and Helmut Böleskei. Deep neural network approximation theory. IEEE Transactions on Information Theory, 67(5):2581-2622 2021.
Charles Fefferman and Scott Markel. Recovering ferw-forward net from its output. Advances in neural information processing systems, 6, 1993.
Christian Fiedler, Massimo Forasiier, Timo Klock, and Michael Rauchensteiner. Stable recovery of entangled weights: Towards robust identification of deep neural networks from minimal samples. Applied and Computational Harmonic Analysis, 02:123-172, 2023.
G. B. Folland. Real Analysis: Modern Techniques and Their Applications. Pure and Applied Mathematics. John Wiley Sons, second edition, 1999.
S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pp. 3587-3596, 2020a.
S. Goel, A. Gollakota, and A. Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147-2158, 2020b.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, 2015.
Philipp Grohs and Felix Voigtlaender. Proof of the theory-to-practee gap in deep learning via sampling complexity bounds for neural network approximation spaces. arXiv preprint arXiv:2104.02746, 2021.
Guodong Guo and Na Zhang. A survey deep learning based face recognition. Computer vision and image understanding, 189: 189:102805, 2019.
Jiequn Han, Arnuff Jentzen, and E Weinan. Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34)8800-8811) 2018.
Yingzhe He, Guozhu Meng, Kai Chen, Xingho Hu, and Jinwen He. Towards security threats of deep
learning systems: A survey. IEEE Transactions on Software Engineering, 48(5): 2022.
Heinrich. Random approximation in numerical analysis. In Functional analysis, volume 150 of Lecture Notes in Pure and Appl. Math., pp. 123-171. Dekker, New York, 1994.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, al. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873):83-588) 2021.
Yongdai Kim, Ilsang Ohn, and Dongha Kim. Fast convergence rates of deep neural networks for classification. Neural Networks, 138:179-1111 197, 2021.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference for Learning Representations, 2015.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521((553)):36 444, 2015.
Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Stoica. Tune: A research platform for distributed model selection and training. arXiv preprint arXiv: 1807.0518 2018.
Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5191-5198. 2020.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
11

---

Published as a conference paper at ICLR 2023
Mathias Müller, Annette Rios Gonzales, and Rico Sennrich. Domain robustness in neural machine translation. In Proceedings of the 14th Conference of the Association for Machine Translation in the Americas, pp. 151-164, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopt, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, perforrrfoe deep learning library. In Advances in Neural Information Processing Systems, volume 32, pp. 8024-8035, 2019.
D. Pfau, J. S. Spencer, A. G. D. G. Matthews, and W. M. C. Foulkes. Ab initio solution of the many-electron schrödinger equation with deep neural networks. Phys. Rev. Research, 2:033429, Sep 2020.
Kateryna Pozharska and Tino Ullrich. A note sampling recovery of multivariate functions in the uniform norm. SIAM Journal on Numerical Analysis, 60(3):1363- 1384, 2022.
Joaquin Quinoonro- shift in machine learning. MIT Press, 2008.
Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset
Maziar Raissi, Paris Perdikaris, and George E Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational physics, 378:686-707, 2019.
Holger Rauhut. Random sampling of sparse trigonometric polynomials. Applied and Computational Harmonic Analysis, 22(1):16 12,,11666222222 2007.
L. Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00537, 2020.
Lorenz Richter and Julius Berner. Robust sde-based variational formulations for solving linear pdes via deep learning. In International Conference on Machine Learning, pp. 18649-18666, 2022.
David Rolnick and Konrad Kording. deviree-engineerrng deep relu networks. In International Conference on Machine Learning, pp. 8178-818 7778-8187,08 2020.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
L. Song. S. Vempala, J. Wilmes, and B. Xie. On the complexity of learning neural networks. Advances in neural information processing systems, 30, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6/99, 2013.
Florian Tramèr, Fan Zhang, Ari Juels, Michael K Reiter, and Thomas Ristenpart. Stealing machine learning models via prediction APIs. In 25th USENIX security symposium (USENIX Security 16), pp. 601-618, 2016.
Joseph F Traub. Information-based complexity. In Encyclopedia of Computer Science, pp. 850-854.
John Wiley & Sons, 2003.
Vladimir Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5):988 99088999911111 1999.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Verner Vlašić and Helmut Böleskei. Neural network identifiability for a family of sigmoidal nonlinearities. Constructive Approximation, 55(1):173-224 2022.
V.H. Vu. On the infeasibility of training neural networks with small mean-squared emror IEEE Transactions on Information Theory, 44(7):2822-2900, 1998.
Qizhe Xie, Minh-Thang Thang Luong, Eduard Hovy, and Quoe V Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10687-10698, 2020.
12

---

Published as a conference paper at ICLR 2023
An,
A4a
0
A
-1
-3
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
Figure 4: Plots of the function AM,a in Equation
for (M, ((2, 1), (4, (4, 9)
A PROOF OF THE LOWER BOUND IN SECTION 2
A.1 CONSTRUCTION OF HAT FUNCTIONS IMPLEMENTED BY RELU NETWORKS
For de M> 0,
s E [d]. and y R define
0
ift 0 M
AMo: R- (-00,11 1]. t 11 M.
(4)
if 0 M
and furthermore
(+)
Rd - (-00, 1],
Σ AMsss 1);
M,y
M.y Rdd - [0,1], x - M.y (x)),
where, as before, 2 IR R, r - max x). denotes the ReLU activation function. A plot of M, is shown Figure
With these definitions, the function
((+) M.y satisfies the following properties:
Lemma A.1. For de N,
[d]. M 1, y [0, 1]d, and (0, o0). have
supp 0(0) M. c + (M- [] x R
and
1
2 (/5) M 1/p
( & 20/0 M-D
Proof. Let first give quick overview of the proof. The statement on the support of ((s) M.y follows Mgy &
by observing that A (+) M.y (x) > can only happen A (a,) for [s]. As & (()) the upper bound on the ([0, 1)d) norm can then be estimated by the Lebesgue measure of the
intersection of the support of g(() and the hypereube [o. 1]d For the lower bound we compute the
measure the intersection with subset of the support on which it holds that v(*)
M.y 2
We start by proving the statement on the support of ((e) M.y If of ((() May (x), then A (a)
May (x)
meaning Σ M (r:) > 1. Because of AMa (#t) E (-o0, 1] for all i [s]. this only
possible if AMMM (z²) for all [s]. Directly from the definition of AM. (see also Figure 4p.
this implies Jx, 3el & M for all [s]. meaning E y + (M-*[-1, 1]3 Ed- This proves the
first claim.
Regarding the second claim, define y* == (y1,... U.) E R", and, for k E N, denote by A the Lebesgue measure on R Then, since [0, 1]d n supp M. (y* + + - [0. 1] and see that
(()
0 M.y
s/p
(0(e) (/ & (>, [-1
25/p s/P
M
13

---

Published as a conference paper at ICLR 2023
For the converse estimate, let us also write x (Z1,..., v.) for R Then, if x R satisfies x= E y* + 2M [_,11]" we see
1
D)
M E Ub
& $ + 2Ms
for [+]]
2Ms
By definition of Aa this implies AM.., (1i) 1 - M |xs
Mil
1 - L and hence
2x
Myy (a)
Σ Aa (zi) - (s 1) >
1
(s - 1) =
2
so that 062 M.y (o) >
Finally, it is not difficult to show, that
Aa(E= [0. x y -M -..1-1,1133 (10, (v* - > (2Ms)
see Grohs & Voigtlaender [2021
Equation (A.1)) for the details. Overall, thus
|01b)) Mig M.y lI
1 (2Ms) s/p
Note that a compactly supported (non-trivial) function such as M,y can only be represented by ReLU networks with more than two layers, see Blum & Li [1991 Section 3). For this reason, we focus on the case L Na3 in this paper. Next, we show that scaled versions of the hat functions a(e) can be represented using neural networks of suitable architecture and with a suitable bound on the magnitude of the coefficients. We begin with the (more interesting) case where the exponent that determines the regularization of the weights satisfies > 2.
Lemma A.2. Let d E N, L E Naa, B E No3. 0, q co]. and e N with minn 3 d).
Then, there exists a constant
>> ch ((L-1)(1
1) 3) /12
such that
X
Myy H2 (,.. Bd.......
EM and y e [o, 17d,
Ms
where the B in (d, B, B...., B, 1) appears L times.
Proof. Let M E N. y [o, 11 and {+1} be fixed. We will now construct the coefficients ((W), .b'.......... (W (b)) of neural network with the following properties:
1. The first two layers ((W1. 8t), (W2,6% (2)) output at any of their B output dimensions the function C A (a) for suitable scaling factor Ci Ci(c, M, s, B,g) 0.
M.
2. The following activation function yields C1
((0) M. e(Cr A for all output dimensions.
3. Each of the layers ((W3, (,"),,...... 1oyT.-1,b--11 scales the previous output by another factor ((s) C2 = Cz(c, B,q) > 0, leading to the output C, Mr in any of the B output dimensions. This construction uses the fact that all intermediate outputs are positive by construction such that the intermediate ReLU activation functions just act as identities.
4. The last layer (W2,44 now computes the sum of the previous outputs scaled by another factor C3 Cc B,q) q) > and multiplied by v, such that the final one-dimensional output equals CBC,C C3- (x)
M.y The result follows by setting À = BC; o C s and choosing the scaling factors C₁ C2. and C3 as large as possible, constrained by the width B and the regularization given by and q.
14

---

Published as a conference paper at ICLR 2023
Define |, noting that 3 since Σ 3/3. We first introduce few notations: We write ORxn for the k n matrix with all entries being zero; similarly, we write 1xxn for the n matrix with all entries being one. Furthermore, we denote by (Ci....,ed) the standard basis of R and define
1 = (el ... Cx)
Rdxx
a: M 1 y1
M
1/2
E
IR 1x8
2
(5)
B = 1/1
V/
...
-96)
lixs E R2xx
y: = 2M
2M
8
2M
We note that all entries of these matrices and vectors clements of [1, Using these matrices and vectors, we now define
T Bxd
W (3
Is/ ....0...........
(0xx(B-3rs)
blocks of (4,/2)4,
a 8 r | 10)" E
b'
(3sr) 1/9
blocks of (a((8))
and furthermore
w²:- (3srB)Lvv
Bxs -lxx
- Bxs
1 Bxs -Bxss -Bxx (Bx(B-3rs) 3ro) ER BBBBB
blocks (1axal-1axa -1xx))
8² = (0) 0)² B
[B3) It is straightforward verify that |[ le, || lla [|6 lles 16 < Furthermore, we define
where we note that B 3rs 0 since r
W
1x and b' = (0)... 10) E
3iiii 1,
B2/q
and finally WL vic. (1).... 11) RIxB and 6z (0) E RR. Again, is straightforward to verify that |W*llee, [/'l|e. for 3 & i L 1 and also that [W,,, l c & c. Therefore,
setting & = ((W2 b²),,..,(( (W b4)), we have R(Φ)= H Hid.B....BBBB it thus remains verify that R(D) V- Ms M.y
((0) for constant as in the statement of the lemma.
To see this, we note for any E Rd and j E [d] that
e 112 + M -1 elar; wi} _ Mi + M- e(2rg M/j)
if x < y - M-
1
(1 M |x,, Uz|)
if Uز M-1 | < x. E (6)
2M
EM (1 M |x,, msl)
if > y/
2M AM.us (Iz).
For notational convenience we further define (x(x)) = e( (i'x + b¹) for E [4]. Then, we observe for x IR and i E [B] that
(x)],
Fasb-j Tasb+atj 13ab+2243)
(3rsB)
b- 0-11
Therefore, we see for arbitrary E Rdd and i e [B]
that
[ o (0000))22))
e (
M- M e( -y1) -e(==l - ))
(3r
AMsss (21) s=1
2M(3rs) 2/ 1/0
2M(3rs) (x).
15

---

Published as a conference paper at ICLR 2023
Hence, it holds that
dr
(0o o 0 0 (x)')(x)= 2M(3rs)2luBuu MMy (2) (1/-..11)) E R.a
Next, for 3 & i & - 1, we see for arbitrary x: >/ 0 and j [B] that
[(e 23) (1x (1).-. 11))- e(Ei_[ [ lg.e (cBBI-aR) cB²-2mn 2m,
meaning
( ... ... 1..-)))))) = cBI ix. (1....11)
Therefore, we conclude
(oo og d-i, (B' (B' 3 4 0 My(()
(x)
(a) (1 .... 1)? R
2M(3rs)3iaB) B//
All in all, this easily implies
B c (B (B
B/ /y (x) = V. -t (B2 (3-33) 1-3 1-
(x)
V
My (2).
Bij
(Mr3r
6.ss
It therefore remains to recall that r = |B/(3s) > 1, so that 2r 11+>>
B and hence 3rs >
B
3s
2
Since also 1 2 > 0, this implies (3rs) 1 > (B/2) 1- B1- /2, which finally shows
(B' (3
ط² B (r 1)(12)
12
Now, we also consider the case & 2. We remark that in the case = 2, the next lemma only agrees with Lemma up to a constant factor. This is a proof artifact and is inconsequential for the questions we are interested in.
Lemma A.3. Let d E N, LE N23, Be Nas. > 0, E [1,2]. and s e N with & min(d, }. Then, we have
V. s 3 (2-33//9)
glo) My E H. (...,...B..).. A M MMENN (+1), and y e [0, 17
Ms
where the B in (d, B...., B) appears
times.
Proof. The proof idea similar to the one of Lemma A.2 However, we only realize a scaled version of the function M,y in the first coordinate of the outputs after the first two layers. As in the proof of Lemma A.2 we denote by (ei....,ed) ed) the standard basis of Rd, and write ORxn and 1 for the k x v matrices which have all entries equal to zero or one, respectively. Moreover, we use the matrices and vectors I. a, 8,7 defined in Equation (5. With this setup, define
W
(Ts/2 T, (dx(B- E RR Bxd
(35)a/g
1/2
ba
(a B 01x(B-3))
T e B
(3s) 1/
Note that these definitions make sense since 2s & 3s & B. Further, define 6² := (0]...-0)) and
T e e
lixs
-1 01x(B-36) 36) (B-1)x(B-34) - E g and
22 = (3s)2/4 O[B-1ixe
E BxB
0(B-1)x2e
Next, for 3 E & L 1, define 6² == (0)
1 0
0 0
W c-
CRBBB BxB
0
16

---

Published as a conference paper at ICLR 2023
and finally let W. v. (1|0) ... [0] e R and by (0) R'. It is straightforward to verify that Wel & and | a c for all & j & L. Therefore, R(Φ) E H (d. B,I,,, for
(WW, ()) (W b²)). It therefore remains to show that R($)
(2 (s) Ms
M,y
For notational convenience we define d'(x) = e(W'r x + b*) for i E [4].
Then we note for
3 x i x that ( (I) (c. e(x1) 10)" This easily implies
@0o o 00 0 o (x) = (c--3 e(x1) 10)0
and therefore
(z) o0 1- e(x1) for x
oo o...oo
Finally, application of Equation (6) shows that
N - e(2x; -v1) ee( 2M ))
[(e 2 0o 0 (2)]
(3s)210 2
ee(
ti +
(E)
As (25)
( -1)
(s
2M - (3s)2/d
2
2M (3s) 2/4 (44 (..)(())))) (x))
2M (3s)2/4 M.y((1).
(10)
Overall, thus claimed that
2
ch
--8--//1 (2. 32/9)
R(D)(z)= = v. ch-2
1
M.g (x)
M.y
2M (3s)2/1
Ms
Remark A... A straightforward adaptation of the proof shows that the same statement holds for (d, (d,,,NN2nie Ne.....NN-...... instead of (d. B. for arbitrary N2....,N1. Nr-1, N.
A.2 A GENERAL LOWER BOUND
We now show that any target class containing large number of (shifted) hat functions has a large optimal error.
Theorem A.S. Let d, m s [d]. and M = 8// Assume that U c C(LO, 1J satisfies
+ v.
و(م) M8 M.y
EU
VUE {+1) and y E [0, 1]d
for certain X > 0 and uo E C([0, 1. Then,
err (U, (L0, 115) >
A/4 (32s)
m --3
Vpe [1,
l+7
The general idea of the proof sketched in Section details.
2.3 In what follows we provide the technical
Proof.
The proof is divided into five steps.
Step Define :m [m///]] and let of (I....)) (-((.....)) [0, 1]d for E [4k]4. Furthermore, let = [4k]* x {(1..... 1)} = [4k]d. With
8k
4k
A Ms Ma for ( (+1),
((o)
fe, = uo + v
it holds by assumption that
E V(E e (+1).
(8)
Furthermore, since M = 8k, Lemma A.I and a moment's 's thought reveal that
V ((, l e supp(ft.- uo) supp(Seww u²) Ø,
(9)
17

---

Published as a conference paper at ICLR 2023
where we note that Sup uo) supp g(a) M,y"
Step 2: Le E Alg2m (U. TP) be arbitrary and x(uo) (f1,..., (10, 1]d) 2m as
described before Equation T Put
I = fee:: Vie [2m] 06e) Myye
= 0}
We now show that
[x] (4k)* 2m.
(10)
To see this will estimate the cardinality of the complement set 1 1 from above. For
i E 1 there must exist ie [2m] with / (ma,) O and hence 2i, supp (D!s) The map
M,y
I - [2m], > ig, is thus injective due to (9) Therefore | & 2m and thus [xx |T| 2m, which is (IO). Furthermore, the definition of Ix. combined with the definition of fr., in 7 and the condition that A can only depend the samples x and the values of the input function these samples, directly imply that
((,,))TXX [+13: LE 1x = A(fev) = A(uo).
(11)
Step 3: Recalling our notation for the average in Section 1.2 it holds that
Σ FET
Me - A(Jew)llz
1 [
+ 2 21le1 A(teiller)
(4k)*
EE
Σ
fi, - + 2 f1fe1 A(fe))ller)
1
(12)
(4
[x|
X
1 f15e--1 - -((fe- + 2 fe,1 A(fe,))loo)
(4))*
1 X
1
1 E1le,1 A(Je1)llo))
[ A(fe-1)) +
(13)
2 reTx
2
1
Σ
[ ft.-1 A(uo)lle> + - A(vo)lle>)
1
1
(14)
2
EElx
((a)
(15)
2 8E1x
Ms
M.yl
LP
1
2 (2x) #-1 X =
(16)
1
(28)-
$ A 16-5-1 3-----mm---
(17)
2
X
m -
2 (32s) ++1
Here, 112 follows since Tx = T: (3) follows from [m and (T): 14h follows from 1T 15) follows from the triangle inequality and (7): (66) follows from Lemma A.1 and (17) follows from the definition of M, which implies that M & 8/a + + & 16m! 1/2
Step 4: Let (A, m) E Alg MC (U, LP) be arbitrary with A = (Aw) for a probability space
(Ω, F, Put So (w Q: m(w) & 2m}. Since the Markov inequality implies that
> E[m] 2m F(R)))
follows that
P()))) 1
(18)
For notational convenience, we abhreviate T/ ([0 13() by T," in this proof.
18

---

Published as a conference paper at ICLR 2023
Step 5: We finally estimate for (A, m) as in Step 4 that
sup E[Iu A [e] >
I
E
[1fe - (e(eelll
(19)
FE ME(
E
L0 (w)
Ilfe, Aff
EEl we(#1)
> P(Oo)
m -
(20)
2 (32s)
++1
A/4
(21)
(328)
Here, 19) follows from 8
20 and 21) follows from 18].
follows from Step 3 (note that A E A Alg2m (U, IP) for w E Ωo);
Since (A, m) AU, L") arbitrary, this implies the desired statement.
Remark A.6. Close inspection of the proof of Theorem 2 shows that one can replace the point any local operator Since any differential operator is a local operator, our lower bounds also hold if we measure point samples of a differential operator applied to u, as it is commonly done in the context of so-called physics-informed neural networks (Raissi et al. 2019).
samples u(æ:) by Tu(æ)), where I U C((O, 1)ah
B PROOF OF THE UPPER BOUND IN SECTION 2.4
We first provide an auxiliary result which bounds the spectral norm W le of a matrix W by its entry-wise 8 norm.
Lemma B.I. Let W E N and E 20]. Then it holds that
[
if <
Wi &
( (WMM)
ifg > 2.
Proof. We first note that W 11 = | the Frobenius norm of the matrix W. It is well-known that the Frobenius norm satisfies [W 0² & || Since we could not locate a convenient reference, we reproduce the elementary proof: The Cauchy-Schwarz inequality implies that
M
Wallea
Σ
W Wi
W
bzy
2
|W
|
which implies the claim. Thus, we see for 2 that [| & W < [ Clearly, the same estimate holds for complex-value matrices and vectors as well.
Now, to handle the case > 2, we first note for q ap and W E CNXM and x E C that
W
W
Zz
Σ 1r, 12
2 2
|W NM.
This proves the claim in case == co. Finally, for q (2, o0), we choose 0 2, so that 6 Thus, applying the Riesz-Thorte interpolation theorem (see, e.g., Folland 1999 Theorem 6.27) the linear map (CN XM [le>) - (CN, le), W - W x. shows for each & E M that
[ 2 & (v (VMM) 1-8 || = (VNM)* # |W]ler,
which completes the proo
This means that if f = on neighborhood of x E [0, 1] then (Tf( = (T)))x).
We consider complex matrices and vectors, since the Riesz-Thorin theorem applies as stated only for the complex setting.
19

---

Published as a conference paper at ICLR 2023
Next, let define the Lipschitz constant Lipeo (0) of a function Φ F. - I with respect to the e norm by
lØ(z) Φ(y))ee
Liper(0)
sup
| - y/ y/leo
Note that the Lipschitz constant of an affine-linear mapping - Wa + b equals the spectral norm [[W]|e= Thus, we can use the previous lemma to bound the Lipschitz constant of neural network realizations R(() H (NNo....Ni... in terms of their architecture (No...., NL) and the regularization on their weights (given by maxigiet. max Wi lee, 116 & c).
Lemma B.2. Lei N. g E [1, c> and No...., Nr. N. Then, each R(Φ) E H (No....NNJee satisfies
fet ctt -VNoNN . N---NN if 2> 2.
if < 2
(i(P()(()) &
Proof. Let R($) E H No.... Na).e be arbitrary. By definition, this means
R( = 0² go /- o ooo''.'''
where @ acts componentwise, and where the affine-linest maps Ø' RNN:1 R.N: are of the form ('(x) = W b', with W E N and [e & c.
The ReLU activation function o: R R. x max z), is easily seen to satisfy (e(x) e(v) < [x - yl for e R.. This implies that
Lip (R(()) Lip -oo 0
o 0²) <
(d'))
(22)
1=1
Lemma B.1 establishes for i [L] that
{ (c. (VN
Fc
if < 2
(dp &
if 2,
which, together with 22 proves the claim.
Note that we can estimate the error of reconstructing Lipschitz continuous functions from samples by piecewise constant interpolation. Together with Lemma B.2] this allows us to construct a (non- adaptive, deterministic) algorithm for reconstructing neural networks from samples.
Lemma B.3. Let d E N. Then, for every N, there exist points 2T. .1...., [0, 1]a and a map Om m 0 ([0, 1]d) satisfying
| (u(x1), ..... )((m))))).. u|| (=00,11))))
& Lipea(u) 2vd m 1/4
(23)
for every function [0, 1] IR with Lippz(u)
Proof. Let m E be arbitrary and choose K = |d] > 1. Write
Rd
Ur....,,kgdl (1....1)
f K
K-1
noting that
[0, 1]d
2 + [ 2k 2 1d.
2K
K
Hence, choosing Q; = (x; +
[- 2
1
(xg + [- 2k
1 1d), we get [0. 1jd
U Qi.
where the union is disjoint.
Note that Kd < and choose arbitrary points Igd+1: Um [0, 1]d Furthermore, define
Kd
IT - L ([0,
(ai....,,m)) ~ Σ i-1
aj
1Q.
20

---

Published as a conference paper at ICLR 2023
To prove Equation let [0, 1l R be arbitrary with Lipes (u) sc. For arbitrary I [0, 1] there then exists unique [Kd] satisfying a E Qi c 2z [- 2k 2k
d and in
particular | x:le vd/(2K). Therefore,
10m (u(z1)..... (....,,.aalll u(z=)))(z u(x) = lu(a;) u(x)
vd 2K
< Lipp ||=; xlee & Lipa(u)
Since x E [0, 1]d was arbitrary, this implies
1m (1(x1)).,....... u(xm)) u/ ([0.11] (u) vd
2K
Finally, we note that K [m! > implies 2K > 1 K> m/d, which proves the claim.
Note that the proof above requires to convert a Lipschitz constant with respect to the l norm to an Eo estimate which costs a factor vd and contributes to the gap between our lower and upper bound.
Remark B.4. Note that our upper and lower bounds Theorems 1.1 and 1.4 are asymptotically sharp with respect to the number of samples m, the regularization parameter c, and the network depth L but not fully sharp with respect to the multiplicatiie factor depending on d and q only. Given many samples, combination of Theorems [I.] and 1.4 shows that the optimal achievable 1 reconstruction error & for reconstructing neural networks with L layers to width 3d and coefficients bounded by in the 8a norm satisfies
256-3444 ct d - 1636-d ch. (3d) (1-11111 3) m
Vd. ct. m2 E
if <
ch. (3d))4---)))))) m
ifq 1 2.)
For moderate input dimensions d the upper and lower bounds quite tight. but larger d there remains a gap. However, in that case the lower bound for m is already intractable (at least if & 1/d or if >> 1 and T, large) that the upper bound is merely of academic interest.
21

---

Published as a conference paper at ICLR 2023
C HYPERPARAMETERS USED IN THE NUMERICAL EXPERIMENTS
Table I: General hyperparameters for the experiments in Figure and Section
Description
Value
Variable
Experiment
precision
float64
GPUs per training
(NVIDIA GTX-1080, RTX-2080Ti, A40, or A100)
Deep learning algorithms
optimizer
Adam
initialization of coefficients (W3, ,8)
activation function learning rate scheduler initial final learning rate decay frequency Evaluation
ReLU
exponential decay
10~$/10-*
every epoch
number of samples
2
J
distribution of samples evaluation norm number of evaluations
U(|-0.5, 0.5)*)
{1,2, oo)
5 (evenly spaced over all epochs)
Table 2: Hyperparameters specific to the experiment in Figure
Description
Value
Variable
Experiment
samples
103
m
dimension
1
Target function
sinusoidal function
2: log log(sin(50x) 2) sin(5x)
Deep learning algorithm
depth of architecture
22
L
width of architecture
50
N Nr-1
batch-size
20
number of epochs
5000
Table 3: Hyperparameters specific to the experiments in Section
Description
Value
Variable
Experiment
samples
{102 [1,3]
10 10 10")
dimension
d
Target functions
number of teachers
40
i
depth of teacher architecture
5
L
width of teacher architecture
32
Ni,.., N
activation of teacher teacher coefficient norm teacher coefficient norm bound
ReLU
0
q
0.5
c
distribution of coefficients Deep learning algorithms number of seeds
u([-0.5,0.3
3
depth of student architecture
5
L
width of student architecture batch-size
{32, 512, 2048)
N₁, Nu-1
1100, m/5, m/50)
number of epochs
500 (if batch-size = 100), 5000 (else)
22


Reviews:
[{"review_id": "tJawMVu3Xo9", "reviewer": "Reviewer_Jti4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Motivated by robustness of trained models, the paper studies the statistical complexity of learning the class of ReLU networks up to $\\ell_\\infty$-error (uniform error). In particular, they show that the sample complexity required for learning ReLU neural networks with $L $ layers each with width at most $3d$ (where $d$ is the input dimension) and bounded norm coefficients requires exponential in $d$ and $L $ samples. In contrast, learning to $\\ell_2$-error requires polynomially on $d$. They also give (almost) matching upper bounds. The results in the paper allow for the underlying algorithm to be adaptive in the selection of the data points, that is, it can query the points necessary to give the required guarantee. The key idea is to use the flatness of ReLU to show that the NN class contains functions of the following form: for any $y\\in \\mathbb{R}^d$ the function is non-zero only for a small ball around point $y$ in the space. Therefore, to learn the function from samples to $\\ell_\\infty$ accuracy, one needs to sample a point in every small ball, that is, cover the entire space which requires exponential in $d $ samples. The norm bounds on the weights governs the radius of these balls and the base of the exponent.", "summary_of_the_review": "Overall, in my opinion, the worst-case nature of the result makes it not very interesting. The requirement of $\\ell_\\infty$-bounded error becomes extremely strong, and not very insightful for realistic models. As the authors point out in the limitations, studying this in a more reasonable sub-class of neural networks or understanding uniform error restricted to some manifold or under some perturbation model would be more useful and interesting.\n\nPost rebuttal: Increased the score from 3-> 5.", "strength_and_weaknesses": "Strengths: \n- The paper makes progress towards understanding the information theoretic limits of robust learning, which is an important problem in the light of adversarial vulnerabilities in current ML models. The lower bounds hold for all algorithms and not restricted to some computational models.\n- The paper is well-written and easy to follow. The authors do a good job of thoroughly discussing the theorem statements and their implications.\n\nWeaknesses:\n- I am not convinced by the technical depth of the main result and more generally the setting. It is worst-case in nature and for a very general class. This makes the lower bound weaker, since getting $\\ell_\\infty$ bounded error in such a setting seems naturally hard. The examples in Remark 1.3 where such a goal is tractable are restricted to polynomials/linear functions which have special structure in terms of interpolation.\n- Experiments are in very low dimensions. Trends for different errors also seem similar. Hence, it is unclear what the reader should take away from the experiments.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ePqDX740kyY", "reviewer": "Reviewer_eNk7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of learning classes of deep, feedfoward neural\nnetworks with ReLU activations through with guarantees in terms of $L^\\infty$\naccuracy, through the angle of sample complexity requirements. More precisely,\nthey consider a rather general model where a learner can adaptively query\npoints of the solid cube $[0, 1]^d$ for evaluations of an unknown deep ReLU\nnetwork $f$, and provide lower bounds on the number of queries necessary for\nany (possibly randomized) such algorithm to output an $\\varepsilon$\napproximation to $f$, for all possible choices of the network $f$ in a\nrestricted class (bounded number of neurons, bounded depth, and norm-bounded\nweights). The obtained lower bound grows exponentially in the dimension $d$ and\nthe network depth, demonstrating a strong barrier to learning in this setting.\nUpper bounds are derived in the same algorithmic setting (as before,\ncomputational complexity is not considered)\n\n", "summary_of_the_review": "\nThe paper presents a solid contribution to the understanding of teacher-student\nlearning of neural networks to a high degree of uniform accuracy. I am unsure\nof the general implications of the theory given the student-teacher setting,\nbut I think the work may lead to many interesting follow-up investigations, as\nthe authors mention in the conclusion.\n", "strength_and_weaknesses": "## Strengths\n\n- The lower bound holds very generally and without conditions associated with\n  other SQ-type lower bounds that apply to more natural algorithms like GD/SGD.\n- The focus on $L^\\infty$ estimation has possible connections to\n  security-critical settings where one is interested in the ability to recover\n  the parameters of a neural network model.\n- The paper is very clearly written and well-referenced. It is possible to\n  understand the paper's main results at a technical level without having to\n  reference notation/etc. in the appendices because background information is\n  explained completely.\n\n## Weaknesses\n\nAlthough I have not checked the proofs, the authors' results seem reasonable to\nme. Therefore most of my comments here will not be weaknesses with the\n(well-written) paper per se, but rather questions about the motivation and\nimplications for practice of the theory.\n\n- The requirement $B \\leq 3d$ in Theorem 2.2 seems unnatural -- can this be\n  improved? Is there a \"functional\" description (e.g. from the proof) of what\n  this constraint implies?\n- The exponential dependence on dimension may be seen as not too\n  surprising: one needs a number of points exponential in dimension just to\n  cover the input space, and the class seems complex enough that it is really\n  necessary to have such a dense covering. What seems more interesting is\n  that it is also necessary to sample exponential in depth. However, one is\n  naturally curious about the extent to which this is simply because the\n  learning problem is extremely hard -- arbitrary depth-L networks can\n  parameterize very complex functions, with many linear regions (e.g.\n  following Montúfar's work) -- and whether the same exponential dependencies\n  would appear for learning e.g. a Sobolev or a Besov class. Another angle\n  on this question would be to consider how the bound would look for learning a\n  \"smoothed\" class of ReLU networks, e.g. those with a bounded number of\n  linear regions, or the like. The behavior that may be most interesting as a\n  theory for the practical successes of deep learning would be one that\n  captures the ability of deeper networks to *adaptively* represent complex\n  functions, when it is necessary, given sufficient samples -- and it seems\n  this kind of explanation is out of reach of the present theory, given that\n  the class being learned contains extremely complex functions implemented by\n  general depth-$L$ networks. (The authors mention this as a direction for\n  future work in the conclusion; it would be nice to hear some thoughts in this\n  context in the response.)\n- Similarly to the previous point, I am not completely convinced about the\n  connection the authors make between their result and adversarial robustness\n  -- although indeed in the setting of adversarial robustness one is interested\n  in $L^\\infty$ stability guarantees, these are generally not in the\n  teacher-student setting where the training labels are generated by some deep\n  neural network, but rather by some dataset with certain structures\n  (statistical, geometric, etc.). In this latter setting, the requirements to\n  be robust to worst-case corruptions may be quite different from the setting\n  that is considered here. I think this is especially pertinent with regards to\n  the $\\exp(L)$ dependence in the authors' lower bound -- how would the\n  corresponding lower bound look in the setting of a structured, labelled\n  dataset?\n\n\n## Minor / Questions / Comments\n- Is there a version of Theorem 1.1 that applies to networks of arbitrary\n  intermediate widths (like Theorem 1.4)?\n- In Theorem 1.1, when $q \\leq 2$ the result seems to be vacuous in high\n  dimensions unless $\\varepsilon$ goes to zero; on the other hand, it seems\n  that working through the corresponding bound in Theorem 2.2 implies a\n  nonvacuous result in high dimensions (it seems the dependence on width $B$\n  has been worst-cased to a dimension dependence in Theorem 1.1). Would it\n  make sense to state the result differently? Reading Theorem 1.1, I have the\n  sense that the bound is very loose with respect to Theorem 1.4 for \"mild\n  regularization\" (whereas with the actual dependence, the gap between the\n  bounds becomes much clearer).\n- Some comments on *what the class of functions implemented by the\n  architectures considered is* would be helpful here in assessing the degree\n  of difficulty of the learning problem, relative to some of the other\n  classes mentioned in Remark 1.3 -- e.g. in the proof idea section describing\n  the bump function, can we also know Sobolev estimates for these functions (to\n  better understand what the class being embedded is, effectively)? \n  - The proof sketch of the lower bound reminds of some of the description of\n  Bubeck and Sellke's work on robustness is there any connection here?\n  (Keywords like Baum's construction of memorizing networks and its\n  generalization by Bubeck et al., etc...)\n- Could the authors provide a proof sketch for the upper bound in Theorem 2.4?\n  Given that this upper bound applies to an adaptive, potentially randomized\n  algorithm, is it safe to assume that this upper bound applies to an algorithm\n  that is \"stronger\" than e.g. empirical risk minimization under a\n  distributional assumption, which as the authors mention in related work has\n  been considered in works with a similar flavor? I am just interested in how\n  to compare this upper bound to results I have seen in related work on $L^p$\n  $p \\ll +\\infty$ learning of ReLUs with certain algorithms.\n- It might be more correct to say that the \"minimal error over neural network\n  target functions\" is estimated/approximated, rather than \"computed\", on page 8.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BBmGP4rEvS-", "reviewer": "Reviewer_8e6q", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a theoretical study on the difficulty of learning an unknown ReLU network with a fixed number of layers by another ReLU network with the same number of layers. While previous attempts usually look at NP-hardness of the optimization process of this task, even allowing for known data distribution, the paper tackles the problem from a learnability/information theoretic point of view and studies bounds on sample complexity that any learning algorithm can achieve. The end result is a separation between L-infinity learnability and Lp learnability when p is finite. In particular, when requiring that the learned network is close in L-infinity norm, the sample complexity scales at least exponentially in depth and input dimension, even if one allows for arbitrary runtime in the learning algorithm.\n\n\n\n\n\n\n", "summary_of_the_review": "Despite the limited setting under which the main results are proven (learning under L-infinity) and slightly unrealistic counterexample for the lower bound (which is rather common in the literature, in fact), the paper is very clearly written (even in the proof), gives concrete, quantitative, and comprehensive results under mild assumptions and is, in general, an interesting and well-conceived theoretical paper. Therefore, I recommend acceptance. ", "strength_and_weaknesses": "Strengths\n\n1. The results are quantitative where both the upper and lower bound are non-asymptotic. The proof is clean and constructive. \nThe paper is very clearly written. Special care was given to compare to existing work and to discuss specific results in order to avoid over-claiming.\n2. Assumptions made are natural and rather weak. The learning problem is also natural and relevant (teacher-student learning).\nRelevant empirical study to substantiate theoretical claims.\n\nWeaknesses\n\n1. The results are not very surprising as learning in L-infinity is known to be hard. \n2. Some discussions can be useful regarding the upper bound result (of Theorem 2.4). \n3. The results are only truly novel in the L-infinity setting, which is a restrictive setting (mainly for security, safety-critical applications), as learning is known to be tractable in L-p where p is finite. (This is acknowledged by the authors.) \n4. The constructed hard function for the lower bound proof makes use of sharp bumpy hat functions, which is not natural in real-world settings.\n5. I would really appreciate a more in depth comparison to SQ learnability literature since they share the common setting of studying sample complexity (as opposed to runtime complexity under fixed sample size). The authors, however, did a good job comparing their results in the PAC learnability setting.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "79ySqW3zS6Q", "reviewer": "Reviewer_81vF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides sample complexity upper bound and lower bound for learning high uniform accuracy ReLU networks. It shows that any learning algorithm recovers neural networks to achieve high uniform accuracy needs intractably many samples (exponentially depending on the input dimension, network width and network depth).\n", "summary_of_the_review": "Overall, I believe this is an interesting paper with good contribution that considers the sample complexity of neural networks for uniform accuracy.", "strength_and_weaknesses": "Strength:  This paper study the sample complexity of learning high uniform accuracy neural networks. Uniform accuracy is not a common criterion that people analyze in statistical learning theory, but it can help to understand the stability of the network, which I believe is an important contribution to the deep learning community.\n\n\nWeakness:  While I’m not familiar with uniform accuracy-related work, I feel some of the important lines of literature are missing. For example, I’m wondering whether the author can first provide some detailed literature results regarding the difference between sample complexity of average accuracy vs uniform accuracy on simpler hypothesis classes, such as linear classifier, polynomial classifier, etc? Moreover, I believe how neural network approximate function is another line of related work related to this paper, which should be discussed and compared with the results.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6641F3EZFy", "reviewer": "Reviewer_zxQe", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper aims to show that for any learning problem formulated over target classes containing ReLU neural networks of a prescribed architecture, the number of training samples needed for an adaptive randomized algorithm to guarantee a given uniform accuracy scales exponentially both in the depth and the input dimension of the network architecture.", "summary_of_the_review": "The paper rigorously addresses a meaningful question in applied machine learning. The work provides novel insights into the learning problem, and its technical contributions might be of broad interest.", "strength_and_weaknesses": "### Strengths\n\n- The paper considers an unorthodox (but important and impactful) statistical learning problem: sample complexity for uniform accuracy (instead of expected accuracy). The motivation and impact of such an analysis are discussed carefully throughout the manuscript. The main ideas and techniques of the work were developed based on well-founded rationales and in general, the paper is well-written with a sufficient literature review.\n- One of the important (and maybe novel) insights of the work about neural networks in this learning setting is that while there exist functions that can be exactly represented by small neural networks, these representations cannot be inferred from samples because of the network’s expressiveness.\n- The mathematical analyses of the work are rigorous, intuitive, and seem correct.\n- One main technical contribution of the work is to explicitly show that neural network models contain a large class of “bump functions” with estimable L^p norms and disjoint supports. Thus, with a “small” number of observations, no algorithm would be able to distinguish those functions from the zero function, or one another. The sample complexity depends on p, and when p=\\infty (uniform accuracy), the dependency is exponential.\n- Beyond this direct application of the analysis, several components of its explicit computations would be of great interest to a broader audience. For example, the bump functions, which have support in B(y, 1/M) and are greater than 1/2 in B(y, 1/(2Ms)), are very similar in spirit to the concept of mollifiers and approximation of the Delta Dirac function. The fact that they can be represented by a standard feed-forward ReLU network could be a useful tool in other contexts.\n\n### Weaknesses\n\n- None noted.\n\n### Additional comments\n\n- As stated in the comments, I think the explicitness of Lemmas A.1 and A.2 are technically interesting, and some detailed descriptions of the insights of those constructions would be appreciated. For example, the steps (and the constructions of the layers) in the proof of Lemma A.2 have their own meaning (representing the hat functions, representing the bump functions, controlling the norms), and some verbal descriptions of what they do would make the parts more accessible. (I want to note that it’s just an optional comment and will not affect my review decision.)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5v8AeFP4Ws", "reviewer": "Reviewer_VFv9", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a fundamental impossibility result associated with the neural network function class. It is proven that given a specific network architecture (e.g., depth and width) with ReLU activation function and norm-bounded parameters, there exists a neural network function u such that u cannot be determined *efficiently* from (possibly adaptive) input-output sample pairs, where the needed sample size to determine u can be lower bounded by a term that scales exponential in the input dimension d. This result is equivalent to the following one: given a specific network architecture with ReLU activation function and norm-bounded parameters, to learn a target function uniformly well with error $\\epsilon$ (where the error is measured to be the $L^\\infty$ distance between the learned function and the target), the sample complexity must scale like $\\Omega(\\epsilon^{-d})$.\n\nThe paper discussed a quite general setting with the error defined to be $L^p$ distance for any $p\\in [1,\\infty]$. The above exponential bound happens exactly when $p=\\infty$, which contrasts the common squared-error setting $p=2$, for which sample-efficient learning is possible.\n\nMoreover, the dependency of several problem-dependent parameters is made explicit in the bound, such as the network layer $L$, the hidden dimension $B$, and the scale of the parameters $c$ under $\\ell_q$-norm. The authors gave a fruitful discussion of their results and also presented an upper bound. They finally conducted experiments to verify the theoretical results.", "summary_of_the_review": "Overall, I think this paper is interesting. The result is well-presented, and the writing is clear. Nevertheless, there are several weaknesses raised above. I hope the authors can clarify them and I will reevaluate this paper based on authors' response.", "strength_and_weaknesses": "**Strength**:\n\nI feel the presented theoretical result is interesting. The result gives us a better understanding of the complicated nature of the neural network function class which is fundamentally different from classic function classes, such as linear models or polynomials. It shows that the representation of a neural network cannot be inferred from a tractable number of input-output samples even if the number of network parameters is small. I partially agree with the authors that the result may be useful for future works in understanding several important topics, e.g., why modern neural networks are vulnerable to adversarial examples. I also agree that learning functions to minimize the uniform error $L^\\infty$ instead of $L^2$ is *necessary* for some applications such as solving partial differential equations. So in this respect, I think the present theoretical result is significant.\n\nThis paper is well-written and clear. Although the theoretical bound involves many problem-dependent parameters in a complicated manner, it is well-explained using carefully presented remarks. Moreover, the simplified version (Theorem 1.1) gives readers an overall picture of the more advanced result, while being easy to understand. The authors also present a proof sketch that is helpful in gaining insights into why the result holds. The discussions in this paper are particularly comprehensive.\n\n**Weaknesses**:\n1. I think there is a mismatch between the setting in this paper and the commonly used settings in learning real-world function classes. In practice, it is unlikely that the target function is represented by a neural network similar to the counterexample in this paper. If I understand correctly, the reason why the sample complexity must scale like $\\Omega(\\epsilon^{-d})$ is that neural networks can represent ''bump functions'' which are highly local. Therefore, if there are no samples in the ``bump'' area, the target function clearly cannot be learned. However, such non-smoothness may hardly appear in practice. Therefore, the current theory may not shed light on practical settings. I think it is an important and natural assumption that the target function to be learned is ''smooth'' (rather than all functions that can be represented by neural networks).\\\n Although the authors said that ''this is satisfied in several applications of interest, e.g., model extraction attacks (Tramèr et al., 2016; He et al., 2022) and teacher-student settings (Mirzadeh et al., 2020; Xie et al., 2020)'', the target functions there are *well-trained* neural networks rather than any possible one in the neural network function class. Therefore, these cases may not be the same as the one studied in this paper.\n\n2. The authors also said that the result is related to the adversarial vulnerability of neural networks. While I partially agree with the potential implications of the result in this paper, I think the current setting is still quite different from the setting of adversarial examples. In particular, Theorem 1.1 may only show that neural networks can represent highly non-smooth functions with many spikes, for which adversarial examples exist. However, given finite samples, why are neural networks prone to learn bump/spike functions rather than smooth functions? It is because of the inductive bias or training algorithms? I think currently it is still not clear how the result in this paper relates to the adversarial vulnerability of neural networks.\n\n3. While I am generally satisfied with the case when $q=\\infty$ (i.e., the setting of bounded weight coefficients), I think the current bound for $q<2$ may be vacuous and unreasonable. In particular, in this case $\\Omega$ scales like $d^{-d}$, which means that when fixing $\\epsilon$, the bound $\\left(\\frac {\\Omega}{64d\\epsilon}\\right)^d$ vanishes as $d\\to \\infty$. Namely, the lower bound becomes trivial when $d$ is large. This is clearly impossible since the problem becomes harder when $d$ is larger. Therefore, the bound for the case of $q<2$ is very loose and may not really make sense. Note that there is a large gap between the lower bound and the upper bound for $q\\le 2$ (Theorem 2.4, which does not vanish when $d$ is large). In another way, the main theorem only applies when $\\epsilon=o(1/d)$. For the high dimensional setting which usually occurs in practice, the bound becomes vacuous.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster