A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks
Authors: El Mehdi Achour
Armand Foucault
Sébastien Gerchinovitz
Francois Malgouyres
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural networks
approximation theory
lower bounds

Abstract: We study the fundamental limits to the expressive power of neural networks. Given two sets $F$, $G$ of real-valued functions, we first prove a general lower bound on how well functions in $F$ can be approximated in $L^p(\mu)$ norm by functions in $G$, for any $p \geq 1$ and any probability measure $\mu$. The lower bound depends on the packing number of $F$, the range of $F$, and the fat-shattering dimension of $G$. We then instantiate this bound to the case where $G$ corresponds to a piecewise-polynomial feedforward neural network, and describe in details the application to two sets $F$: Hölder balls and multivariate monotonic functions. Beside matching (known or new) upper bounds up to log factors, our lower bounds shed some light on the similarities or differences between approximation in $L^p$ norm or in sup norm, solving an open question by DeVore et al. (2021). Our proof strategy differs from the sup norm case and uses a key probability result of Mendelson (2002).

A general approximation lower bound in L' norm, with applications to feed-forward neural networks
El Mehdi Achour', Armand Foucault', Sébastien Gerchinovitz",, and François Malgouyres!
Institut de Mathématiques de Toulouse : UMR5219, Université de Toulouse; CNRS, UPS IMT
F-31062 Toulouse Cedex 9, France
IRT Saint Exupéry, 3 rue Tarfaya, 31400 Toulouse, France
achour, armand francois francoiss.alggourrees AT
math. watt.uuutttuouus....... sebastien gerrhiiovizgr AT irt-saintexupery.o com
Abstract
We study the fundamental limits to the expressive power of neural networks. Given two sets F, G real-valued functions, we first prove a general lower bound on how well functions in F can be approximated in (P(()) norm by functions in G, for any p 2 1 and any probability measure μ.. The lower bound depends on the packing number of F, the range of F, and the fat-shattering dimension of G. We then instantiate this bound the case where G corresponds to a feed-forwart neural network, and describe in details the application to two sets F: Hölder balls and multivariate monotonic functions. Beside matching (known new) upper bounds up to log factors, our lower bounds shed some light on the similarities or differences between approximation in L" norm or in sup norm, solving open question by Vore al. (DHP21]. Our proof strategy differs from the sup norm case and uses key probability result Mendelson [Mnn2].
Introduction
Neural networks are known for their great expressive power: in classification, they can interpolate
arbitrary labels (ZBH*2) 21). while in regression they have universal approximation properties [Cyb89
Hor
LLPS93 KL with approximation rates that can outperform those of linear approximation
methods Yar 18 DHP2I] Though the approximation problem is often only one part of the underlying
learning problem (where generalization and optimization properties are also at stake), understanding
the fundamental limits the approximation properties of neural networks is key, both conceptually and for practical issues such as designing the right network architecture for the right problem.
Setting and related works. One way to quantify the expressive power of neural networks is through the following problem (some informal statements will be made more precise the next sections). Let G be the set of all functions Iw X' C Rd - IR that be represented by tuning the weights w E RRW a feedffo neural network with a fixed architecture, and let F be any set of real-valued functions
X. A natural question is: how well can functions F be approximated by functions E G? More precisely, given a norm || on functions, what is the order of magnitude of the (worst-case) approximation error of F by G defined by
sup inf |l - gw feF SwEG
(1)
and how small can it be given the numbers W, L of weights and layers, and some properties of F?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Lower bounds on the approximation eтror ① can be useful in several ways. They provide limit to the best approximation accuracy that one can hope to achieve if the number of weights or layers of the network is constrained, and help design optimal architectures under these constraints. They also imply lower bound on the minimal number of weights or layers to include a network in order to approximate any function in F with a given accuracy e.
The case when || is the sup norm (defined by |I = suprex [f()) is rather well understood at least in some special cases. For example, when F' is a Hölder ball of smoothness >> 0 (a.k.a. Hölder exponent) and the network uses the ReLU activation function. Yarotsky | derived lower bound on (T of the order of W-2s/d, later refined (LW))s/d (up log factors) by [Yar18] YZ20 when the depth of the network varies from = to ~ W. Using the bit extraction technique, these authors showed that these lower bounds are achievable (up to log factors) with carefully designed ReLU network architecture, Refined results in terms of width and depth were obtained by [SYZ22) when s S I, while some other activation functions were also studied in YYZ20).
In this paper, we study [ with the (P()) norm, defined by [[f = (Jx ((x)) V/2 for 1 p < too and some probability measure μ on X. There is qualitative difference between measuring the error in sup norm or in (P()) norm, p < +00. In the former case, the error is small only if the approximation is good over the whole domain. In the latter case, the error can be small even if the approximation is inaccurate over a small portion of the domain. Since the [P(N) approximation problem corresponds to approximating functions in F in more "average" sense than in sup norm, a natural question is whether the same accuracy can be achieved with a smaller network or not. Unfortunately, however, the proof strategies behind the lower bounds of 1 Yarl8, Y720 SYZ22] are specific to the sup norm (see Remark in Section 3 for details). Vore al. DHP21 indeed commented: "When
move to the case p oo, the situation is even less clear [...] we cannot use the VC dimension theory for (P( approximation. [...] What missing vis-à-vis Problem 8.13 is what the best bounds are and how we prove lower bounds for approximation rates in (I(),,, P + oc."
Existing lower bounds in (p) norm. Several papers provided lower bounds in some special cases, under some restrictions on the set to approximate F, the neural network, the approximation metric, or the encoding map f F + w(f) E RRW
When F is a space of smoothness 8, a first result which is based on [HM89] states that when imposing the weights to depend continuously on the function to be approximated, one can not achieve a better approximation rate than W-3.
For the same F', another result for 2 and for activation functions which are continuous (Mai99 MMR99) proves lower bound on the approximation of functions of smoothness on a compact of Rd. by one hidden-layer neural networks. of order W æंx matching upper bound is proven for a particular activation function, which is sigmoidal but pathological ([P99)). For this same activation function, they prove that contrary to the mme-hidennllaer case, there is no lower bound in the case of two-hidden-layer networks. The result is based on the Kolmogorov-Aie Arnold superposition theorem.
In [SX21, the authors study approximation by shallow neural networks with bounded weights and o activations of the form ReLU* for an integer k. They approximate the closure of the convex hull of shallow ReLU*=neural networks with constrained weights. They obtain optimal lower bounds of order 4- 2k+1 in any norm || llx, where X is a Banach space to which the approximation functions belong and such that these functions are uniformly bounded w.r.t || llx. Although we only consider approximation in (p) norm, our results complement the latter by addressing neural networks with unbounded weights and arbitrary depth, and general sets F.
Approximation lower bounds in (²( norm, p 2 1, have also been studied in the quantized neural networks setting (networks with weights encoded with fixed number of bits). In [PVI8], under weak assumptions on the activation function, the authors prove a lower bound on the minimal number of nonzero weights W that are required for a network to approximate class of binary classifiers
with L error at most e. They show that W is at least of the order e r(d-1) log, (1/e), where / is a smoothness parameter. Later works including (V119 GR20 derive lower bounds for approximation by quantized networks in various norms.
2

---

Main contributions and outline of the paper. We prove lower bounds on the approximation error ① in any (2) norm, for non-quantized networks of arbitrary depth, and general sets F. Our main contributions are the following.
In Section 2 we first prove a general lower bound for any two sets F, G of real-valued functions on a set X' (Theorem [). The lower bound depends on the packing number of F. the range of F, and the fat-shattering dimension of G. We then derive a versatile corollary when G corresponds to a piccewise-pollnomiall feed-forward neural network (Corollary I solving the question by DeVore et al. [DH22]] Importantly, our proof strategy still relies on VC dimension theory, but differs from the sup norm case in using a key probability result of Mendelson [Men02], to relate approximation in [P(n) norm with the fat-shattering dimension of G.
In Sections 3 a we apply this corollary to the approximation of two sets: Hölder halls and multivariate monotonie functions. Beside matching (known new) upper bounds up to log factors, our lower bounds shed some light on the similarities or differences between approximation in IP norm or in sup norm. In particular, with ReLU networks, Hölder balls are not easier to approximate in L norm than in sup norm. On the contrary, the approximation rate for multivariate monotonic functions depends on p. In Section 5 we outline several other examples of function sets F and G for which the general lower bound (Theorem [T] can also be easily applied. Finally, some proofs are postponed to the supplement, while some details on other existing lower bound proof strategies are provided in the supplement, in Appendix C
Additional bibliographical remarks There are many other related results that we did not mention to keep the focus on our specific approximation problem. For instance, depth separation results show that deep neural networks can approximate functions that cannot be easily approximated by shallower networks (e.g.. (Tll6) (VRPS2I).. Let us also mention the general results of (YB99), which characterize minimax rates of estimation based on metric entropy conditions. Understanding the precise connections between these statistical results and our general approximation lower bound an interesting question for the future.
Definitions and notation. We provide below some definitions and notation that will be used throughout the paper. We denote the set of positive integers (1, by N and let N : No U (0). All sets considered in this paper will be assumed to be nonempty. We will not explicitly mention o-algebras; for instance, by "Let X' be measurable space" we mean that X is a set implicitly endowed with a o-algebra.
Let p E [1, +oo and X' be any measurable space endowed with probability measure μ.. For any mea- surable function f: X' + R, the [²(μ)) norm of f is defined by [[fllem()) = (fx (dx))d) 1/p (possibly infinite) ifp < +00, and [| = ess suP [f()). We will write x for the Lebesgue measure on [0, 1|a.
For any e >>>>>>>00 0, two functions SI, J2 are said to be e-distant in || if S2ll 8. Let F be set of functions from X to R. A set (/1,... ................ [N) C F is said to be an e-packing of F in -|| (or just an e-packing for short) if for any * j E (1, (1,...,
[1,...,N], N}. J and ʃ, are e-distant in || ||. The e-packing number (s, F. || II) is the largest cardinality of e-packings (possibly infinite).
For > O, we say that set S = (21 .N., C. X is y-shattered by F' if there exists r S - IR such that for any E C S, there exists f F satisfying for all 1,..., .N. fx;) 2 r(a;) ((a;)+% + if I; E, and fx; S r(z:) -ry if x; & E. The r-fat-shattering dimension of F, denoted by fat,, is the largest number N 2 1 for which there exists 5 C X of cardinality N that is 7-shattered by F (by convention, fat, (F) 0 if such set S exists, while (F)
+oc if there exist sets S of unbounded cardinality N). Similarly, we say that S is pseudo-shattered by F if there exists r: + IR such that for any E C S. there exists E F satisfying for all i = 1, 1,..., N. fxxx) 2 r(x.) a; E F, and f(x)) < rg if xt & F. The pseudo-dimension Pdim is the largest number N > for which there exists S C X of cardinality N that pseudo-shatteres by F' (same conventions) |
formal definition of forward neural networks is recalled in Appendix A In short, in this paper, a feed-forward neural network architecture A of depth L > 1 is a directed acyclic graph with d > 1 input neurons, L - 1 hidden layers (if L 2 2), and an output layer with only one neuron. Skip connections are allowed, i.e., there can be connections between con-conseeutive layers. Given an
By definition, note that y + fat, (F') is non -occrancaas and that (Ft) I Pdim(F) for all 7 > 0.
3

---

activation function Ø R + R, of weights assigned to all edges and non-input neurons (linear coefficients and biases), the network computes function Iw : R - R defined by recursively computing affine transformations for each hidden or output neuron, and then applying the activation function a for hidden neurons only (see Appendix for more details). Finally, we define H == {Iw w R") } to be the set of all functions that can be represented by tuning all the weights assigned to the network.
neural network architecture A, and a vector w E R
A function RR + R is piecewise-polynmmia on K 2 2 pieces, with maximal degree v E N, if there exists partition I,.... Is of R into K nonempty intervals, such that a restricted on each 1 is polynomial with degree at most v (in particular, can be discontinuous).
2 A general approximation lower bound in LP(μ)) norm
In this section, we provide our two main results: general lower bound on the (²) approximation error of F by G, i.e., su inf |lf g]]== and corollary when G corresponds to feed- forward neural network with a plecewise-polynonin F make the last result applicable to wide range of cases of interest, as shown in Sections 3
activation function. The weak assumptions on
2.1 Main results
Our generic lower bound reads follows, and is proved in Section 2.2 We follow the conventions 0 x log" (0) = 0 and P log a (P) = +o0 when P =
Theorem 1. Let 1 Sp< +00 and X be a measurable space endowed with probability measure Let F, G be two sets of measurable functions from X' to R, such that all functions in F have the same range (a, bj for some a < b, and such that (G) < -00 for all y > 0. Then, there exists constant e depending only on p such that
sup inf Ilf -9llerm) inf { JEF gEG
0: log (3e, (1)(()) sfat (G) E <=>0:
22 (G) 32 E/(b - 0)
}
(2)
In particular, log (e, F. .1 (())() 2 ens for some co, Eo: a > and all e S eo, and if PC) < +00, then there exist constants C1 E1 depending only on b a, p. co, Eo and a such that
sup inf |lf - all 2 min {EL, e₁ Pdim(G) log (Pdim(G))
(3)
JEF gEG
The first lower bound (2) is generic but requires solving an inequation In we solve this inequation when log M Fs, (L)( grows at least polynomially in 1/s (which is typical of nonparametric sets) and when G has finite pseudo-ding dimeedd-n Pdim(G). Though we will restrict our attention to such cases in all subsequent sections, we stress that the first bound should have broader applications. A first example is when Pdim(G) +oo but (G) < +oo for all 7 > 0 (e.g., for RKHS (Bel18)) The first bound should also be useful to prove (slightly) tighter lower bounds when log M(, F, (1)))))))) has a (slightly) different dependency on 1/s (e.g., of the order of e log" (1/E) as when F is the set of multivariate cumulative distribution functions (BGL07)
In the rest of the paper, we focus on the important special case when the approximation set G is the set A of all real-valued functions that can be represented by tuning the weights of a feed-forward neural network with fixed architecture A and a piccewise-polynomial activation function. By combining Theorem [ with known bounds on the pseudo-dimension (BHLM19), we obtain the following corollary, which bounds the approximation error in terms of the number W of weights and the depth L (i.e., the number of hidden and output layers). The proof postponed Appendix B.4
Note that any 2 (b a)/3 is solution to this incquation, since log (3e, F, (I(e))) log(1) = (because all functions in F are (a, b)-valued) and e fat Tz most (b- /3.
(G) Therefore, the right-hand side 2

---

Corollary 1. Let 1 S < +00, d2 and X be a measurable subset of Rd endowed with probability measure μ. Let F be set of measurable f X to (a, b] (for some real numbers a 6), such that log M F, (I(G()) 2 CoE " for some co, co, a > 0 and all E S ED-
Let a : IR- + R be any deecewise-polynomin activation function of maximal degree V/ E N on K 2 2 pieces. Then, there exist W NN' and c1, C2 O such that, for any W 2 W any L 2 1, and any fixed feed forward neural network architecture A of depth L with W weights, the set H of all valuvd functions X that can be represented by the network (cf. Section satisfies
ei W log (W) Cz(LW) log à (W)
ifv 2 2,
sup inf Ilf - -9llp(()) 2 SEF
if 1,
(4)
03 W- log log-- (W)
ifv = 0.
There are equivalent ways write the above corollary. For example, given a target accuracy e 0 and a depth L 2 1, yields lower bound on the minimum number W of weights that are needed to get sup F F inf H. Ilf gllxsw)) I E. Some earlier approximation results were written this way
(e.g., Yarl7 PV18).
2.2 Proof of Theorem
In order to prove Theorem I we need two inequalities. The first one is straightforward (and appeared within proofs, c.g., in (YZ20), but formalizes the key idea that G approximates with error E. then G has to be at least as large as F. We use the conventions log(+oo) = too and too S +00. Lemma 1. Let 2 1 and X' be a measurable space endowed with probability measure p. Let F, G be two sets of measurable functions from X to R. Ifsup yer infgeG Il - gllLp(m) < e, then
log (3e, F, ((EPG)) I log (s, (e (1l.p()))))
Proof. Let PF = (fi...... fN} } be a 35 3s-packing of F, with 2 1. Let Pg (gi.... IN be a subset of G such that flf 9i (x(()) S E for all i. Note that the existence of such a Pa is guaranteed by the assumption supyer inf |] g (P(H) < E. Since the fi's are pairwise 3e-distant in (M)), the triangle inequality entails that the g. 's are also at least pairwise e-distant in (p)... Therefore, Pa an e-packing of G. and the result follows.
The next inequality is a fundamental probability result due to Mendelson Men02]. It bounds from above the e-packing number in (2(()) norm of any uniformly bounded function set in terms of its fat-shattering dimension. Crucially, the inequality holds for finite 2 1, opposed to the lower bound strategy of Yarotsky [ Yar (see also [DHP2T]) that relates the VC-dimension with the approximation error in sup norm. The next statement is slight generalization of result of [Mn022] initially stated for (a. b] = [0, 1] and for Glivenko-Cantell classes G (see Appendix B.I for details).
Proposition 1 (Menn02), Corollary 3.12). Let G be set of measurable functions from a measurable space X (a, b) (for some real numbers a < b), and such that fat, (G) < +00 for all y >> Then for any 1 < p < +00, there exists e >> O depending only on p such that for every probability measure Iu on X and every e > O,
log M (e, II (lrrw) S efat d2 (G) log? (2 a) fat fz (G)
(5)
E
Refinements of this inequality were proved in specific cases such as the L (2(p)) norm [MV03] (see
also [Guel7] for empirical (P,) norms). However, using the result of [MV03 when p = 2 would
only yield a minor logarithmic improvement in the lower bound of Theorem 1
Proof (of Theorem 7). Part 1. We start by proving 2). using Proposition I a key argument. Since functions in G are not necessarily uniformly bounded, we will apply Proposition to the "clipped version of G". More precisely, for any function g E G. we define its clipping (truncature) to Ja, b) as the function ğ X - given by g(x) min(maxx(a, (a, g(x)), b) for all æ E X. We then set Gla.)] = (ō g G}, which by construction consists of functions that are all [a, vjluud
5

---

Noting that clipping can only help since elements of F are [a, bl-auud (see Lemma in the supplement, Appendix we have
sup inf II - gllzp( 2 sup inf |If - gl(x)(1)) JEF SEO
(6)
JEF SEG
Setting A := suppeee inf gnG Il ())))( we now show that A is bounded from below by the right-hand side of (2. To that end, it suffices to show that every E > A is a solution to the inequation
2(b a) fai (G) 82
log M F3e, ([LGG)) S cfat 32 (G) log"
The last inequality is true whenever 2 (b a3/3 (see Footnote 2)
We only need to prove 7 when applied to Gia,b), we have
< E (6 a)/3. R In this case, by definition of and by Lemma
log M (3e, F, (IL(()) s log M (e, Gla.)), || (1<F(W))
2(b - a) fat 53
(Gla.))
S cfat = (G)a.t) log²
2(b a) fat 32
(G)
<fat (G) log²
(8)
where the second inequality follows from Proposition 1 (note from Lemma the supplement, Appendix B.2 that (Gt,(G(a.)) I (G) for all y > 0, which is finite by assumption), and where (8) follows from the next remark. Either fat, f (G(a,t) = O, and (8) is true by the convention 82 (G(a,t))
0 log" (0)
and e fat 32 (G) O. Either fat
1, and g follows from
ot log" 2(b-a)t) being non-decreasing on [=/(2(b a)), +o0) and e/(2(b a)) I 1/6 < 1 <
fat 52 (G)a.)) < fat (G). To conclude, every > A satisfies (7). which implies that A is bounded
from below by the right-hand side of ( Combining with (6) concludes the proof of (
32
Part 2. Set = min 50, 2)b-a)} We now derive (3) from (2). To that end, setting P = Pdimm().
we show that every > satisfying (7) such that 2 min(f1, eq P- log 2 (P)). where
E1 E e1) and e will be defined later. Since the claimed lower bound on is true when e 2 ef. in the sequel we consider any solution E to 7 such that 0 < of (if such solution exists).
By the assumption on log M F, ((L)()) for u = 35 S Eu. and then using we have, setting r 2(b a).
(rfal,, d2 (G)
(PP)
co(3E) a S log M M3ce, F, ((be()) S e fat (G) log
cPlog?
E
where the last inequality is because t +> et log" (rl) is non-decreasing on [e/r, too), with 2/r S and < fat 32 (G) < Pd) P (the lower bound of follows from (3(3) 0).
Solving the inequation (3=) ~ < cP log (rP/E) for (see Appendix B.3 for details), we get
E 2 min (="l, c p- log P}.
for constants e², e > noting that e' only depends on Eo and a, we conclude the proof.
0 depending only p, Co, b and a. Setting 61 min(e" e and
3 Approximation of Hölder balls by feed-forward neural networks
In this section, we apply Corollary to establish nearly-tight lower bounds for the approximation of unit Hölder balls by ford-forward neural networks. Our main result is Proposition 3 which solves an open question by (DH21.)
Throughout the section, for any 8 >> 0, we denote by n and a the unique members of the decomposi- tion s n + a such that n E N and <

---

For set &' C R", we follow [YZ00] and define the Hölder space C (X²' as the space of times continuously differentiable functions with finite norm
D f(x) - D"f(u)
|l max
max sup n. = aY
n:|n|Sn
x 1/ 1
where, for (n1,-.. ,aa) Nd, D=S
8
Ad
denotes the |n in-drreer partial
derivative of f. We denote
Fsdd {f E C ([0, 17 Iilleen 1
Let denote the Lebesgue measure over [0, 1jst In this section, provide nearly matching upper and lower bounds for the (*(A) approximation error of elements of Fe,d by feed-forward ReLU neural networks. The bounds are expressed in terms of the number of weights of the network.
3.1 Known bounds on the sup norm approximation error
Y720 gives matching (up certain constant) lower and upper bounds of the sup norm approxima- tion error of the elements of F..d by feed-forward ReLU neural networks.
Proposition 2 (YY720)). Ler N", > y (5. 2x]. Consider +
and a E (0, 1] such that
There exist positive constants Wiin and C1 depending only on and n, such that for any integer
W 2 Wmins there exists a seed-forward ReLU neural network architecture with L -(W
layers and W weights such that
sup inf I|5 -gloo S SoW-?.
(10)
fEF A
In the meantime, there exists a constant 02 > depending only on and n such that, for any feed-forward neural network architecture A with W weights and -W /olo W) layers and for the ReLU activation function,
sup inf Ilf - glooo 2 c-W>>
(1I)
JEP g
It is worth stressing that, for any probability measure μ [0, 1 the upper bound 10 is automati- cally generalized to any smaller (p))) norm, when I p < +00. However, the lower bound [II does not immediately apply when || |l is replaced with || || S p +00. The lower bound of the next subsection shows that, in this setting, approximation in (P) norm is not easier than in sup norm, solving an open question Devore et al. [DHP21]
3.2 Nearly-matching lower bounds of the TP(A) approximation error
We first state a lower bound on the packing number of Fs.d, which is rather classical though hard find in this specific form (see (BS67) for the 0 norm, or [ET%) for other Sobolev-type norms). For the sake of completeness, we give a proof of Lemma in the supplement, Appendix [.
any Lemma 2. Let > 0, d E NN and < +00. There exist constants Ep, > 0 such that for any <<ESS Eg.
log M (c, Fs.a, ((x(())) 2 OoE
(12)
Given Lemma 2 we can use Corollary to establish the next proposition and obtain the lower bound on the (A) approximation error.
Proposition 3. Let N*, > 0, 0,70 (ú, a.
2s and S < too. Consider n E N and a E (0.1) d
such that
a R - be a piecewise-afinee function, and > Then, there exist e₁ > 0 and W Wnin IN* (depending only on s. d, p. a and c) such that for any architecture A of depth < L S c with W Wmin weights, and for the activation o, the set HA (cf. Section 7 satisfies
inf |I - olle=()) 2 1- log (W).
(13)
fEF g
7

---

Note that the rate of the lower bound does not depend on p. Note also that, when the activation function is ReLU (which piecewise-afine), we obtain lower bound which matches the upper bound of the previous subsection up to logarithmic factors.
Proof. From Lemma there exist éo, co > O such that log M (e, Fe,ds || |lle(()) 2 cae for all 0 <<E Eg- Combining with Corollary and using L I cW> concludes the proof.
Remark 1 (Comparison with existing proof strategies in sup norm.). We would like to highlight key the lower bound proof strategies of [Yar77 Yar18 YZ20 SYZ22) that are specific to the sup norm. Their overall argument is roughly the following: if G can approximate any f E F in sup norm at accuracy >> 0, since F contains many "oscillating" functions with oscillation amplitude roughly s, then so must be the case for G (the sup norm is key here: all oscillations of any f E F are well approximated) Therefore, a small e implies a large VCdim which by contrapositive enables to lower bound the approximation error (I) with decreasing function of VVdimm (),, and therefore as function of L and W. In contrast, in the proof of Theorem 1
difference between the proof of Proposition and and
the key probability result of Mendelson (Proposition) [ enables us to show that, even if the oscillations of any f E F are only well approximated on average (in (p) norm) by G, then Pdim(G) must be large when E is small. The conclusion is then the same: the approximation error in L (P)) norm can be lower bounded as a function of Pdim(G), and therefore in terms of L, W. This solves the question of DeVore et al. (DHP2I]) mentioned in the introduction, showing in particular that VC dimension theory can (surprisingly) be useful to prove L approximation lower bounds.
4 Approximation of monotonic functions by feed-forward neural networks
In this section, we consider the problem of approximating the set Ma of all non-decreasing functions from [0, 1]d to [0, 1]. These functions f ||0 [00,1] - [0, 1] that non-decreasing along any line parallel to axis, i... such that, for all 2, y E [0, 1]d.
2; S Vk.
...... d = (()))))))))
Monotonic functions are an interesting case study for at least two reasons. First, they naturally appear in physics or engineering applications (consider for instance the braking distance of vehicle as function of variables such as the speed, the total load or the drag coefficient). Second, as will be shown in this section, because their sets of discontinuities can have "complex" shapes in dimension d 2 2, monotonic functions provide a good example for which the approximation by feed-forward neural networks is hopeless in sup norm, but can be achieved in (*(A) norm.
Next we focus on the approximation of Md with Heaviside feed-forward neural networks. After proving an impossibility result for the sup norm, we show that the weaker goal of approximating M in (A)) norm is feasible, and derive nearly matching lower and upper bounds. Interestingly, the approximation rates depend on p 2 1, which sharp contrast with the case of Hölder balls, that not easier to approximate in L (*) norm than in sup norm (see Section 3
4.1 Warmup: an impossibility result in sup norm
We start this section by showing that approximating monotonic functions of variables in sup norm is impossible with Heaviside neural networks.
Proposition 4. For any neural nefwork architecture A with the Heaviside activation, the set HA (cf. Section 7 satisfies
sup inf SEM4 gEHA
Ilf gl100 2 2
The proof of Proposition is postponed to the supplement, Appendix E.2 We show a slightly stronger result, by exhibiting single function f E Md such that the lower bound of holds simultaneously for all network architectures.
Next study the approximation of Md in (P()) norm.
8

---

4.2 Lower bound in (*) norm
We start by proving a lower bound, as direct consequence Corollary and a lower bound on the packing number due to [GW07].
Proposition 5. Let s +o0, d 2 1, and let a [a (d ()-1))) Let R - R be function having maximal degree v N. Then, there exist positive constants C1, C2, Cs. W (depending only on d, p. and σ)) such that for any architecture A of depth L 2 1 with W 2 Wmin min weights, and for the activation o, the set HA (cf. Section D satisfies
srecewise-polynonne
W log - log- (W)
if 2, if = 1,
sup inf Ilf -0ll JEMa
c2 (LW) log (W) W log a (W)
(14)
if 0.
Note that, contrary to the case of Hölder balls (Section 3), the rate of the lower bound depends on through a = max/d, (d 1)p).
Proof. From GW077,
there exist constants Co > such that for E
Eo-
log M (a, || (()P()) 2 cos " Using Corollary
|
we obtain the result.
4.3
Nearly-matching upper bound in (P))) norm
To the best of our knowledge, there does not exist any upper-bound of the T.P(A) approximation error of Md with feed-forward neural networks. Checking that all the lower-bounds of Proposition 5 are tight is out of the scope of this paper and we leave it for future researct However, we establish in the next proposition upper-bounds of the L approximation error of .Md with feed-forward neural networks with the Heaviside activation function. This shows that, for the (*(A) approximation error, the fower-bound obtained in (14), for v = O, is tight up logarithmic factors. The next proposition follows by reinterpreting a metric entropy upper bound of [GW07) in terms of Heaviside neural networks. The proof is postponed to Appendix [.. in the supplement.
Proposition 6. Let 1 S +00, d E N {0, 1} and let a = max (d- 1)p}. There exist positive constants W min and e, depending only on d and p. such that for any integer W min there exists fordaforward architecture A with two hidden layers, W weights and the Heaviside activation function such that the set HA satisfies
sup inf |lf - g9llEr S { JEM gEHA
c cW log(W)
Tpld $ d, ip(d 1) d.
(15)
5 Conclusion and other possible applications
We proved general lower bound on the approximation error of F by G in ("()) norm (Theorem terms of generic properties of F and G (packing number of F, range of F, fat-shatteiing dimension of G). The proof relies on VC dimension theory as in the sup norm case, but uses an additional key probabilistic argument due to Mendelson (Men() see Proposition solving a question raised by Vore et al. [НP221]
In Sections 3 and 4 we detailed two applications, where Corollary D yields nearly optimal approxima- tion lower bounds in LE norm, and which correspond to two examples where the approximation rate may depend or depend on p.
Theorem and Corollary can be used to derive approximation lower bounds for many other cases.
Corollary only requires (tight) lower bound on the packing number of F, for which approximation
theory provides several examples. For instance, for the Barron space introduced in [Br93]] Petersen and Voigtlaender (PV21) showed tight lower bound on the log packing number in TP(A, (,, [0, 1)4) norm, of order 224/(d+2), Applying Corollary 1 this yields an approximation lower bound of
'Obtaining an upper- bound bound for ReLU networks seems challenging. For example, the bit extraction technique used in [Yar88] to find sharp upper bound heavily relies on the local smoothness assumption of the function to approximate, which is not satisfied in general for monotonic functions.

---

(LW) (1+1) (LW)-(3++) log (og-3(++)))()))) (W) for ReLU networks (see Appendix the supplement for details). Other examples of sets F for which tight lower bounds on the packing number (or metric entropy) are available include: multivariate cumulative distribution functions [BGL07]. multivariate convex functions [ST3], and functions with other shape constraints [JI4.
not essential for the current derivation. Indeed, Theorem [ can also be applied to the case where G corresponds to a neural network with other activation functions such the sigmoid. In the sigmoid case, the pseudo-dimension known be at most of the order of W (see [KM97 )B99)), ). which we can use to derive an approximation lower bound similar to that of Corollary 1, with smaller right-hand side for large W. However, the best of our knowledge, it is not known whether the (Ww)) VC bound is tight (only a lower bound of the order of 2 is known). so the resulting approximation lower bound could be loose. We leave this interesting question for future work.
Hiccewise-polyoomil activation functions
Theorem can also be applied to other approximating sets G, beyond classical feed-forward neural networks, as soon as a (tight) upper bound on the fat-shattering dimension of G is available. For example, upper bounds were derived by [WS22] the VC dimension of partially quantized networks, while [Bel18] derived bounds on the fat-shattering dimension of some RKHS. Investigating such applications and whether the obtained approximation lower bounds rate-optimal natural research direction for the future.
Acknowledgements
The authors would like to thank Keridwen Codet for contributing to the results of Sections 4.1 and 4.3
This work has benefited from the Al Interdisciplinary Institute ANITI, which funded by the French "Investing for the Future PIA3" program under the Grant agreement ANR-19-P3IA-000 The authors gratefully acknowledge the support of IRT Saint Exupéry and the DEEL project
References
[AB99]
Martin Anthony and Peter L. Bartlett. Neural Network learning: Theoretical Founda- tions. Cambridge University Press, Cambridge, 1999.
[ABDCBH97] Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale- sensitive dimensions, uniform convergence, and learnability. J. ACM, 41(4)661 jul 1997.
[Bar93]
Andrew Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information Theory, 39:930 945, 06 1993.
[Bel18]
Mikhail Belkin. Approximation beats concentration? an approximation view on inference with smooth radial kernels. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31 Conference Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 13661136. PMLR, 06-09 Jul 2018
[BGLO7]
Ron Blei, Fuchang Gao, and Wenbo V. Li. Metric entropy of high dimensional distributions. Proceedings of the American Mathematical Society, 135(12):4009- 4018, 2007.
[BHLM19]
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
[BS67]
Mikhail Š Birman and M Z Solomjak. Piecewise- -olyniiap approximation of functions of the classes w.. Muthematics The Ussr-sbornik, 2(3):295-317, apr 1967.
[Cyb89]
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathe- matics of Control, Signal and Systems, 2:303-314, 1989.
fttps://www..r ai/
10

---

[DHM89]
Ronald A DeVore. Ralph Howard, and Charles Micchelli. Optimal nonlinear approx- imation. Manuscripta mathematica, 63(4)):69.477 1989.
[DHP21]
Ronald Verore, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numerica, 30:327-444, 2021.
[ET96]
David Edmunds and Hans Triebel. Function Spaces, Entropy Numbers, Differential Operators. Cambridge Tracts in Mathematics. Cambridge University Press, 1996.
[GJ95]
Paul W. Goldberg and Mark Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning, 18:131-143 february 1995.
[GJ14]
Piet Groeneboom and Geurt Jongbloed. Nonparametric Estimation under Shape Constraints: Estimators, Algorithms and Asymptotics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2014.
[GKKWO2]
László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk, Distribution-Free Theory of Nonpurametric Regression. Springer Series in Statistics. Springer- Verlag, New York, 2002.
[GR20]
Ingo Gühring and Mones Raslan. Approximation rates for neural networks with encodable weights in smoothness spaces. Neural Networks, 134:107-130 11 2020.
[GS13]
Adityanand Guntuboyina and Bodhisattva Sen. Covering numbers for convex func- tions. IEEE Transactions Information Theory, 59(4):1957-1965, 2013.
[Gue17]
Yann Guermeur. Lp-norm sauer-shelah lemma for margin multi-category classifiers.
Journal of Computer and System Sciences, 89:450-473, 2017.
[GW07]
Fuchang Gao and Jon A. Wellner. Entropy estimate for high-dimensional monotonic functions. Journal of Multivariate Analysis, 98(9): 2007.
[Hor91]
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2):251-257, 1991.
[KL20]
Patrick Kidger and Terry Lyons. Universal Approximation with Deep Narrow Net- works. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 2306-2327. PMLR, 09-12 Jul 2020.
(KM97)
Marek Karpinski and Angus Macintyre. Polynomial bounds for dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169-176, 1997.
[LLPS93)
Moshe Leshno, Vladimir Y. Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with nonpolynomial activation function can approximate any function. Neural Networks, 6(6):861-867, 1993.
[Mai99]
Vitaly E. Maiorov. On best approximation by ridge functions. Journal of Approxima- tion Theory, 99())=6894, 1999.
[Men02]
Shahar Mendelson. Rademacher averages and phase transitions in glivenko-cantell classes. IEEE Transactions on Information Theory, 48, 2002.
[MMR99]
Vitaly F. Maiorov, Ron Meir, and Joel Ratsaby. On the approximation of func- tional classes equipped with uniform measure using ridge functions. Journal of Approximation Theory, 99:95-111, 1999.
[MP99]
Vitaly E. Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. Neurocomputing, 25(1):81-9) 1999.
[MV03]
Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones mathematicae, 152:37-55, 2003.
[PV18]
Philipp Petersen and Felix Voigtlaender. Optimal approximation of piecewise smooth functions using deep relu neural networks. Neural Networks, 108:296-330, 2018.
[PV21]
Philipp Petersen and Felix Voigtlaender. Optimal learning of high-dimensional classification problems using deep neural networks, 2021. arXiv:21 12555..
[SX21]
Jonathan Siegel and Jinchao Xu. Sharp bounds on the approximation rates, metric entropy, and widths of shallow neural networks. 2021.
11

---

[SYZ22]
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Optimal approximation rate of relu networks in terms of width and depth. Journal de Mathématiques Pures et Appliquées, 157:101-135, feb 2022.
[Tel16]
Matus Telgarsky. Benefits of depth in neural networks. In 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, Jun 2016.
[VP19]
Felix Voigtlander and Philipp Petersen. Approximation [P(p) with deep ReLU neural networks. In 13th International conference on Sampling Theory and Applica- tions (SampTA), 2019. arXiv:1904.0479:
[VRPS21]
Gal Vardi, Daniel Reichman, Toniann Pitassi, and Ohad Shamir. Size and depth separation in approximating benign functions with neural networks, 2021.
[WS22]
Yutong Wang and Clayton D. Scott. Ve dimension of partially quantized neural networks in the overparametrized regime. In International Conference on Learning Representations, 2022.
[Yar17]
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 14:1011,,, 2017.
[Yar18]
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 Proceedings of Machine Learning Research, pages 639-649, 2018.
[YB99]
Yuhong Yang and Andrew Barron. Information -htoorrtticccciicccccco determination of minimax rates of convergence. The Annals of Statistics, 27(5):1564-1555 1559,, 1999.
[Yu97]
Bin Yu. Assouad, Fano, and Le Cam, pages 423-435. Springer New York, New York,
NY, 1997.
[YZ20]
Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. Advances in neural information processing systems, 33:13005-13015, 2020.
[ZBH+21]
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Un- derstanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We describe several possible extensions our work in Section We also acknowledge, the paragraph above Proposition 6, that extending Proposition 6 to other activation functions (such as ReI.U) would be interesting and describe what we think is the main difficulty in Footnote We also state several times that our lower bounds match the upper bounds up logarithmic factor, not exactly.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work purely theoretical and we do not anticipate any negative impact to it.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes] The main notations and hypotheses are in Section 1. The functional spaces are defined at the beginning of the section concerning them. All the details concerning the networks architecture are always described in the theorems and propositions.
(b) Did you include complete proofs of all theoretical results? [Yes] The proof of the main result is in the article, Section 2.2 The main corollary proved in the supplement,
Appendix B The proofs of the statements obtained when applying the main result
12

---

in the supplement. The proof of the upper bound described in Proposition 6 is also in the supplement.
3. If you experiments.. The article does not contain experiments.
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new as- sets... We do not use any existing asset.
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects... We did not use crowdsoureing nor conducted research with human subjects.
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "iFCmux5p9no", "reviewer": "Reviewer_voDQ", "summary": "This paper proves a new lower bound on the worst-case approximation error of functions in a set $F$ using functions in another set $G$. The bound is then instantiated in the specific case where $G$ is a piecewise-polynomial feedforward neural network. The approximation is considered in $L^p(\\mu)$ norm for any $p \\geq 1$.", "questions": "If possible, I would consider clarifying whether there would be any practical application of the lower bounds proved in the paper.\n\nA small correction: in line 132, \"finite\" -> \"compact\" (or \"finite-length\", or something else)", "limitations": "I don't see any issues here.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is original, clear, well written. Although I haven't checked all details, the authors appear to have done a good job at carrying out precise arguments.\n\nThe significance on this paper is however not clear. The results are very theoretical and there is no evidence that they would be relevant for any practical application.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "eV_-nuq7CE", "reviewer": "Reviewer_S7Xf", "summary": "The paper considers the problem of approximating functions in a family F by functions in another family G. More precisely, they consider the lower bound of the best approximation error $\\sup_{f \\in F}\\inf_{g\\in G} \\Vert f - g\\Vert_{L_p(X,\\mu)}$ for real-valued functions, where $X$ is subset of $\\mathbb{R}^n$ and $\\mu$ is a probability measure on $X$.\n\nThe paper obtains a lower bound for bounded functions in terms of an inequality constraint which is expressed in terms of the packing number of $F$ and the fat-shattering dimension of $G$. The paper then uses this result to derive the lower bounds for the approximation of Hölder-continuous functions and multivariate monotonic functions by piecewise polynomial feedforward neural networks.\n\nThe main technical argument is heavily built upon a previous result by Mendelson. Still, it is nice work to employ it to solve the problem here, which was an open problem and believed to require new machinery other than the VC dimension theory, and proving a lower bound of the packing number of different families of functions is also nontrivial.\n", "questions": "I do not have any major questions. It would be good if the authors could give some comments on the tightness of their lower bounds.\n\nThe following are some minor points on writing:\n- Line 25: “functions f in F can” -> “can functions f in F”\n- Line 29: sup norm -> supremum norm (or just write L_infty norm if space is an issue). This has multiple occurrences throughout the paper.\n- Line 29: the definition of sup norm is incorrect - it should be the essential supremum instead of supremum. The definition in Line 97 is correct though.\n- Lines 49 and 53: how is the smoothness of a function defined? I don’t see this in the ‘Main definitions and notation’ section, either. Do you mean the Hölder exponent?\n- Line 53: prove -> proves\n- Line 61: add a comma before “where”\n- Line 102: the usual notation of the packing number is like $M(F, \\Vert \\cdot \\Vert, \\epsilon)$, where the parameters are in a different order.\n- Line 137 and footnote on the same page: inequation -> inequality; inequation is a word that is rarely used or used only when the direction of the inequality is unknown\n- Line 158: above corollary -> corollary above\n- Line 194: “$\\leq \\operatorname{fat}\\_{\\epsilon/32}(G)$” should be “$\\leq \\operatorname{fat}\\_{\\gamma}(G)$”\n- Line 219: the measure lambda has been defined in Line 97, so the sentence can be omitted.\n- Lines 679 and 680: “cancels” - I think the correct English word is “vanishes” if you mean the functions are zero outside the region\n", "limitations": "N.A.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Earlier results only concern the approximation in the L_infinity norm and the approximation in the L_p norm was an open problem, which was previously believed not within the reach of the VC dimension theory. This paper solves the open problem with VC dimension theory.\n\nWeaknesses: The lower bound is still quite messy and it is not known how tight it is. The techniques of the core result was largely done in the previous works, but I don’t think this per se should be evaluated against the acceptance of the paper.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8LDtZ1CEXE", "reviewer": "Reviewer_GfMK", "summary": "This paper provides a general approximation lower bound result in the $L^p$ norm, and its applications to the neural-network setting. This result is built upon a probability result in [1], which relates the packing number in the $L^p$ norm of a function set $G$ and the fat-shattering dimension of $G$. Given this result, one can derive the approximation in the $L^p$ norm in a relatively straightforward way. Combining existing results on the pseudo-dimension of neural networks, the authors apply the result of $L^p$ norm approximation between two function classes to the neural-network setting. \n\nThe authors further apply the neural-network approximation result to the Hölder-ball and monotonic-function settings, to demonstrate the similarity and difference of approximation in the sup norm and the $L^p$ norm.\n\n[1]S. Mendelson. Rademacher averages and phase transitions in glivenko-cantelli classes. IEEE Transactions on Information Theory, 48, 2002.", "questions": "Could the authors explain what practical ramifications this new approximation in $L^p$ norm result can bring given the known sup norm approximation results?", "limitations": "No major concens. One notational suggestion: I believe that the constants $c_1$ in Equations (10) and (11) are different. You might consider changing $c_1$ in Equation (11) to $c_3$. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. Studying the approximation in the $L^p$ norm is a theoretically interesting problem in its own. Though the approximation result does not appear very surprising given the existing results provided by the authors, the approximation in the $L^p$ norm is a necessary complement to our current understanding of the approximation problem.\n2. This paper is well-written. The results are technical, however, the authors have presented the paper in a quite accessible way.\n\nWeaknesses:\nMoving from sup norm to $L^p$ norm is an interesting mathematical and theoretical problem. However, it is not obvious how in practice these two norms can make a difference. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "64j6HtAqFGA", "reviewer": "Reviewer_qRrC", "summary": "This paper studies the lower bound of the approximation error with respect to Lp norm. The approximation error means how well functions f can be approximated by functions g_w with parameters w. Besides the general case, the authors also provide results for some special cases where g_w is to a feed-forward neural network, f is Holder balls and monotonic functions. Matching upper bounds of the approximation error for those special cases are also provided to show that these bounds are relatively tight.", "questions": "1. In Section 4, the authors study the situation of monotonic functions. I wonder why monotonic functions are special/important in the sense of approximation performance.\n\n2. It is not easy to see the effect of p in most of theorems and corollaries. Maybe the authors can provide some explanation on how different p affects the bound of the approximation error.\n\n3. When considering the feed-forward neural network, the activation functions are limited to piecewise-polynomial ones (e.g., ReLU). Maybe the authors can discuss why piecewise-polynomial activation functions are essential for the current derivation, or, how other types of activation functions (e.g., sigmoid) make the estimation of approximation error difficult.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength (dominating): The result and contributions are clearly stated. Besides, this paper has good writing quality and most of the contents are easy to follow.\n\nWeaknesses: Some details need more explanation. See my questions below.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept