El Mehdi Achour

Armand Foucault

François Sébastien Gerchinovitz

El Mehdi Achour

François Malgouyres

A general approximation lower bound in L p norm, with applications to feed-forward neural networks

Introduction

Neural networks are known for their great expressive power: in classification, they can interpolate arbitrary labels [ZBH + 21], while in regression they have universal approximation properties [Cyb89, Hor91, LLPS93, KL20], with approximation rates that can outperform those of linear approximation methods [START_REF] Yarotsky | Optimal approximation of continuous functions by very deep relu networks[END_REF][START_REF] Devore | Neural network approximation[END_REF]. 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 to 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 in the next sections). Let G be the set of all functions g w : X ⊂ R d → R that can be represented by tuning the weights w ∈ R W of a feed-forward neural network with a fixed architecture, and let F be any set of real-valued functions on X . A natural question is: how well can functions f ∈ F be approximated by functions g w ∈ 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 f ∈F inf gw∈G f -g w , (1)
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

and how small can it be given the numbers W , L of weights and layers, and some properties of F ?

Lower bounds on the approximation error (1) can be useful in several ways. They provide a 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 a lower bound on the minimal number of weights or layers to include in a network in order to approximate any function in F with a given accuracy ε.

The case when • is the sup norm (defined by f ∞ = sup x∈X |f (x)|) is rather well understood at least in some special cases. For example, when F is a Hölder ball of smoothness s > 0 (a.k.a. Hölder exponent) and the network uses the ReLU activation function, Yarotsky [START_REF] Yarotsky | Error bounds for approximations with deep relu networks[END_REF] derived a lower bound on (1) of the order of W -2s/d , later refined to (LW ) -s/d (up to log factors) by [START_REF] Yarotsky | Optimal approximation of continuous functions by very deep relu networks[END_REF][START_REF] Yarotsky | The phase diagram of approximation rates for deep neural networks[END_REF] when the depth of the network varies from L = 1 to L ≈ W . Using the bit extraction technique, these authors showed that these lower bounds are achievable (up to log factors) with a carefully designed ReLU network architecture. Refined results in terms of width and depth were obtained by [START_REF] Shen | Optimal approximation rate of relu networks in terms of width and depth[END_REF] when s ≤ 1, while some other activation functions were also studied in [START_REF] Yarotsky | The phase diagram of approximation rates for deep neural networks[END_REF].

In this paper, we study (1) with the L p (µ) norm, defined by f L p (µ) = X |f (x)| p dµ(x) 1/p , for 1 ≤ p < +∞ and some probability measure µ on X . There is a qualitative difference between measuring the error in sup norm or in L p (µ) norm, p < +∞. 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 L p (µ) approximation problem corresponds to approximating functions in F in a 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 [Yar17, Yar18, YZ20, SYZ22] are specific to the sup norm (see Remark 1 in Section 3 for details). DeVore et al. [START_REF] Devore | Neural network approximation[END_REF] indeed commented: "When we move to the case p < ∞, the situation is even less clear [...] we cannot use the VC dimension theory for L p (Ω) approximation. [...] What is missing vis-à-vis Problem 8.13 is what the best bounds are and how we prove lower bounds for approximation rates in L p (Ω), p = ∞."

Existing lower bounds in L 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 ) ∈ R W .

When F is a space of smoothness s, a first result which is based on [START_REF] Ronald A Devore | Optimal nonlinear approximation[END_REF] 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 -s d . For the same F , another result for p = 2 and for activation functions which are continuous ( [START_REF] Vitaly | On best approximation by ridge functions[END_REF][START_REF] Vitaly | On the approximation of functional classes equipped with a uniform measure using ridge functions[END_REF]) proves a lower bound on the approximation of functions of smoothness s on a compact of R d , by one hidden-layer neural networks, of order W -s d-1 . A matching upper bound is proven for a particular activation function, which is sigmoidal but pathological ( [START_REF] Vitaly | Lower bounds for approximation by mlp neural networks[END_REF]). For this same activation function, they prove that contrary to the one-hidden-layer case, there is no lower bound in the case of two-hidden-layer networks. The result is based on the Kolmogorov-Arnold superposition theorem.

In [START_REF] Siegel | Sharp bounds on the approximation rates, metric entropy, and n-widths of shallow neural networks[END_REF], the authors study approximation by shallow neural networks with bounded weights and activations of the form ReLU k for an integer k. They approximate the closure of the convex hull of shallow ReLU k -neural networks with constrained weights. They obtain optimal lower bounds of order W -1 2 -2k+1 2d in any norm • X , where X is a Banach space to which the approximation functions belong and such that these functions are uniformly bounded w.r.t. • X . Although we only consider approximation in L 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 L p (µ) norm, p ≥ 1, have also been studied in the quantized neural networks setting (networks with weights encoded with a fixed number of bits). In [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF], 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 a class of binary classifiers with L p error at most ε. They show that W is at least of the order ε -p(d-1) β log -1 2 (1/ε), where β is a smoothness parameter. Later works including [START_REF] Voigtlander | Approximation in L p (µ) with deep ReLU neural networks[END_REF][START_REF] Gühring | Approximation rates for neural networks with encodable weights in smoothness spaces[END_REF] derive lower bounds for approximation by quantized networks in various norms.

Main contributions and outline of the paper. We prove lower bounds on the approximation error (1) in any L p (µ) 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 1). 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 piecewise-polynomial feed-forward neural network (Corollary 1), solving the question by DeVore et al. [START_REF] Devore | Neural network approximation[END_REF]. 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 [START_REF] Mendelson | Rademacher averages and phase transitions in glivenko-cantelli classes[END_REF], to relate approximation in L p (µ) norm with the fat-shattering dimension of G.

In Sections 3-4 we apply this corollary to the approximation of two sets: 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. In particular, with ReLU networks, Hölder balls are not easier to approximate in L p 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 1) 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 as easily approximated by shallower networks (e.g., [START_REF] Telgarsky | Benefits of depth in neural networks[END_REF][START_REF] Vardi | Size and depth separation in approximating benign functions with neural networks[END_REF]). Let us also mention the general results of [START_REF] Yang | Information-theoretic determination of minimax rates of convergence[END_REF], 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 is 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, 2, . . .} by N * and let N := N * ∪ {0}. All sets considered in this paper will be assumed to be nonempty. We will not explicitly mention σalgebras; for instance, by "Let X be a measurable space" we mean that X is a set implicitly endowed with a σ-algebra.

Let p ∈ [1, +∞] and X be any measurable space endowed with a probability measure µ.

For any measurable function

f : X → R, the L p (µ) norm of f is defined by f L p (µ) = X |f (x)| p dµ(x)
1/p (possibly infinite) if p < +∞, and f L ∞ (µ) = ess sup x∈X |f (x)|. We will write λ for the Lebesgue measure on [0, 1] d .

For any ε > 0, two functions

f 1 , f 2 are said to be ε-distant in • if f 1 -f 2 > ε. Let F be a set of functions from X to R. A set {f 1 , . . . , f N } ⊂ F is said to be an ε-packing of F in • (or just an ε-packing for short) if for any i = j ∈ {1, . . . , N }, f i and f j are ε-distant in • . The ε-packing number M (ε, F, • ) is the largest cardinality of ε-packings (possibly infinite).
For γ > 0, we say that a set S = {x 1 . . . , x N } ⊂ X is γ-shattered by F if there exists r : S → R such that for any E ⊂ S, there exists f ∈ F satisfying for all i = 1, . . . , N , f

(x i ) ≥ r(x i ) + γ if x i ∈ E, and f (x i ) ≤ r(x i ) -γ if x i / ∈ E.
The γ-fat-shattering dimension of F , denoted by fat γ (F ), is the largest number N ≥ 1 for which there exists S ⊂ X of cardinality N that is γshattered by F (by convention, fat γ (F ) = 0 if no such set S exists, while fat γ (F ) = +∞ if there exist sets S of unbounded cardinality N ). Similarly, we say that S is pseudo-shattered by F if there exists r : S → R such that for any E ⊂ S, there exists f ∈ F satisfying for all i = 1, . . . , N , f

(x i ) ≥ r(x i ) if x i ∈ E, and f (x i ) < r i if x i / ∈ E.
The pseudo-dimension Pdim(F ) is the largest number N ≥ 1 for which there exists S ⊂ X of cardinality N that is pseudo-shattered by F (same conventions). 1 A formal definition of feed-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), and an output layer with only one neuron. Skip connections are allowed, i.e., there can be connections between non-consecutive layers. Given an activation function σ : R → R, a feed-forward neural network architecture A, and a vector w ∈ R W of weights assigned to all edges and non-input neurons (linear coefficients and biases), the network computes a function g w : R d → R defined by recursively computing affine transformations for each hidden or output neuron, and then applying the activation function σ for hidden neurons only (see Appendix A for more details). Finally, we define H A := {g w : w ∈ R W } to be the set of all functions that can be represented by tuning all the weights assigned to the network.

A function σ : R → R is piecewise-polynomial on K ≥ 2 pieces, with maximal degree ν ∈ N, if there exists a partition I 1 , . . . , I K of R into K nonempty intervals, such that σ restricted on each I j is polynomial with degree at most ν (in particular, σ can be discontinuous).

A general approximation lower bound in L p (µ) norm

In this section, we provide our two main results: a general lower bound on the L p (µ) approximation error of F by G, i.e., sup f ∈F inf g∈G fg L p (µ) , and a corollary when G corresponds to a feedforward neural network with a piecewise-polynomial activation function. The weak assumptions on F make the last result applicable to a wide range of cases of interest, as shown in Sections 3-5.

Main results

Our generic lower bound reads as follows, and is proved in Section 2.2. We follow the conventions 0 × log2 (0) = 0 and P -1 α log -2 α (P ) = +∞ when P = 1.

Theorem 1. Let 1 ≤ p < +∞ and X be a measurable space endowed with a 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, b] for some a < b, and such that fat γ (G) < +∞ for all γ > 0. Then, there exists a constant c > 0 depending only on p such that

sup f ∈F inf g∈G f -g L p (µ) ≥ inf ε > 0 : log M 3ε, F, • L p (µ) ≤ c fat ε 32 (G) log 2 2 fat ε 32 (G) ε/(b -a)
.

(2)

In particular, if log M ε, F, • L p (µ) ≥ c 0 ε -α for some c 0 , ε 0 , α > 0 and all ε ≤ ε 0 , and if Pdim(G) < +∞, then there exist constants c 1 , ε 1 > 0 depending only on ba, p, c 0 , ε 0 and α such that

sup f ∈F inf g∈G f -g L p (µ) ≥ min ε 1 , c 1 Pdim(G) -1 α log -2 α Pdim(G) . (3)
The first lower bound (2) is generic but requires solving an inequation. 2 In (3) we solve this inequation when log M ε, F, • L p (µ) grows at least polynomially in 1/ε (which is typical of nonparametric sets) and when G has finite pseudo-dimension 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) = +∞ but fat γ (G) < +∞ for all γ > 0 (e.g., for RKHS [START_REF] Belkin | Approximation beats concentration? an approximation view on inference with smooth radial kernels[END_REF]). The first bound should also be useful to prove (slightly) tighter lower bounds when log M ε, F, • L p (µ) has a (slightly) different dependency on 1/ε (e.g., of the order of ε -α log β (1/ε) as when F is the set of all multivariate cumulative distribution functions [START_REF] Blei | Metric entropy of high dimensional distributions[END_REF]).

In the rest of the paper, we focus on the important special case when the approximation set G is the set H 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 piecewise-polynomial activation function. By combining Theorem 1 with known bounds on the pseudo-dimension [START_REF] Peter | Nearlytight vc-dimension and pseudodimension bounds for piecewise linear neural networks[END_REF], 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 is postponed to Appendix B.4.

Corollary 1. Let 1 ≤ p < +∞, d ≥ 1 and X be a measurable subset of R d endowed with a probability measure µ. Let F be a set of measurable functions from X to [a, b] (for some real numbers a < b), such that log M ε, F, • L p (µ) ≥ c 0 ε -α for some c 0 , ε 0 , α > 0 and all ε ≤ ε 0 .

Let σ : R → R be any piecewise-polynomial activation function of maximal degree ν ∈ N on K ≥ 2 pieces. Then, there exist W min ∈ N * and c 1 , c 2 , c 3 > 0 such that, for any W ≥ W min , any L ≥ 1, and any fixed feed-forward neural network architecture A of depth L with W weights, the set H A of all real-valued functions on X that can be represented by the network (cf. Section 1) satisfies

sup f ∈F inf g∈HA f -g L p (µ) ≥      c 1 W -2 α log -2 α (W ) if ν ≥ 2 , c 2 (LW ) -1 α log -3 α (W ) if ν = 1 , c 3 W -1 α log -3 α (W ) if ν = 0 . (4)
There are equivalent ways to write the above corollary. For example, given a target accuracy ε > 0 and a depth L ≥ 1, (4) yields a lower bound on the minimum number W of weights that are needed to get sup f ∈F inf g∈HA fg L p (µ) ≤ ε. Some earlier approximation results were written this way (e.g., [START_REF] Yarotsky | Error bounds for approximations with deep relu networks[END_REF][START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF]).

Proof of Theorem 1

In order to prove Theorem 1, we need two inequalities. The first one is straightforward (and appeared within proofs, e.g., in [START_REF] Yarotsky | The phase diagram of approximation rates for deep neural networks[END_REF]), but formalizes the key idea that if G approximates F with error ε, then G has to be at least as large as F . We use the conventions log(+∞) = +∞ and +∞ ≤ +∞.

Lemma 1. Let p ≥ 1 and X be a measurable space endowed with a probability measure µ. Let F , G be two sets of measurable functions from X to R.

If sup f ∈F inf g∈G f -g L p (µ) < ε, then log M 3ε, F, • L p (µ) ≤ log M ε, G, • L p (µ) .
Proof. Let P F = {f 1 , . . . , f N } be a 3ε-packing of F , with N ≥ 1. Let P G = {g 1 , . . . , g N } be a subset of G such that f ig i L p (µ) ≤ ε for all i. Note that the existence of such a P G is guaranteed by the assumption sup f ∈F inf g∈G f -g L p (µ) < ε. Since the f i 's are pairwise 3ε-distant in L p (µ), the triangle inequality entails that the g i 's are also at least pairwise ε-distant in L p (µ). Therefore, P G is an ε-packing of G, and the result follows.

The next inequality is a fundamental probability result due to Mendelson [START_REF] Mendelson | Rademacher averages and phase transitions in glivenko-cantelli classes[END_REF]. It bounds from above the ε-packing number in L p (µ) norm of any uniformly bounded function set in terms of its fat-shattering dimension. Crucially, the inequality holds for finite p ≥ 1, as opposed to the lower bound strategy of Yarotsky [START_REF] Yarotsky | Error bounds for approximations with deep relu networks[END_REF][START_REF] Yarotsky | Optimal approximation of continuous functions by very deep relu networks[END_REF] (see also [START_REF] Devore | Neural network approximation[END_REF]), that relates the VC-dimension with the approximation error in sup norm. The next statement is a slight generalization of a result of [START_REF] Mendelson | Rademacher averages and phase transitions in glivenko-cantelli classes[END_REF] initially stated for [a, b] = [0, 1] and for Glivenko-Cantelli classes G (see Appendix B.1 for details).

Proposition 1 ([Men02], Corollary 3.12). Let G be a set of measurable functions from a measurable space X to [a, b] (for some real numbers a < b), and such that fat γ (G) < +∞ for all γ > 0. Then for any 1 ≤ p < +∞, there exists c > 0 depending only on p such that for every probability measure µ on X and every ε > 0,

log M ε, G, • L p (µ) ≤ c fat ε 32 (G) log 2 2(b -a) fat ε 32 (G) ε . (5)
Refinements of this inequality were proved in specific cases such as the L 2 (µ) norm [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] (see also [START_REF] Guermeur | Lp-norm sauer-shelah lemma for margin multi-category classifiers[END_REF] for empirical L p (µ n ) norms). However, using the result of [START_REF] Mendelson | Entropy and the combinatorial dimension[END_REF] when p = 2 would only yield a minor logarithmic improvement in the lower bound of Theorem 1.

Proof (of Theorem 1). Part 1. We start by proving (2), using Proposition 1 as a key argument. Since functions in G are not necessarily uniformly bounded, we will apply Proposition 1 to the "clipped version of G". More precisely, for any function g ∈ G, we define its clipping (truncature) to [a, b] as the function g : X → R given by g(x) = min(max(a, g(x)), b) for all x ∈ X . We then set G [a,b] = {g : g ∈ G}, which by construction consists of functions that are all [a, b]-valued.

Noting that clipping can only help since elements of F are [a, b]-valued (see Lemma 4 in the supplement, Appendix B.2), we have

sup f ∈F inf g∈G f -g L p (µ) ≥ sup f ∈F inf g∈G [a,b] f -g L p (µ) . (6)
Setting

∆ := sup f ∈F inf g∈G [a,b] f -g L p (µ)
, we now show that ∆ is bounded from below by the right-hand side of (2). To that end, it suffices to show that every ε > ∆ is a solution to the inequation

log M 3ε, F, • L p (µ) ≤ c fat ε 32 (G) log 2 2(b -a) fat ε 32 (G) ε . (7)
The last inequality is true whenever ε ≥ (ba)/3 (see Footnote 2). We only need to prove (7) when ∆ < ε < (ba)/3. In this case, by definition of ∆ and by Lemma 1 applied to G [a,b] , we have

log M 3ε, F, • L p (µ) ≤ log M ε, G [a,b] , • L p (µ) ≤ c fat ε 32 (G [a,b] ) log 2 2(b -a) fat ε 32 (G [a,b] ) ε ≤ c fat ε 32 (G) log 2 2(b -a) fat ε 32 (G) ε , (8)
where the second inequality follows from Proposition 1 (note from Lemma 3 in the supplement, Appendix B.2 that fat γ (G [a,b] ) ≤ fat γ (G) for all γ > 0, which is finite by assumption), and where (8) follows from the next remark. Either fat ε 32 (G [a,b] ) = 0, and (8) is true by the convention 0 × log 2 (0) = 0 and c fat ε

32 (G) ≥ 0. Either fat ε 32 (G [a,b] ) ≥ 1, and (8) follows from t → ct log 2 2(b-a)t ε being non-decreasing on [ε/(2(b -a)), +∞) and ε/(2(b -a)) ≤ 1/6 ≤ 1 ≤ fat ε 32 (G [a,b] ) ≤ fat ε 32 (G).
To conclude, every ε > ∆ satisfies (7), which implies that ∆ is bounded from below by the right-hand side of (2). Combining with (6) concludes the proof of (2).

Part 2. Set ε ′ 1 = min ε0 3 , 2(b-a) . We now derive (3) from (2). To that end, setting P = Pdim(G), we show that every ε > 0 satisfying (7) is such that ε ≥ min ε 1 , c 1 P -1 α log -2 α (P ) , where ε 1 ∈ (0, ε ′ 1 ] and c 1 > 0 will be defined later. Since the claimed lower bound on ε is true when ε ≥ ε ′ 1 , in the sequel we consider any solution ε to (7) such that 0 < ε < ε ′ 1 (if such a solution exists).

By the assumption on log M u, F, • L p (µ) for u = 3ε ≤ ε 0 , and then using (7), we have, setting

r = 2(b -a), c 0 (3ε) -α ≤ log M 3ε, F, • L p (µ) ≤ c fat ε 32 (G) log 2 r fat ε 32 (G) ε ≤ cP log 2 rP ε ,
where the last inequality is because t → ct log 2 rt ε is non-decreasing on [ε/r, +∞), with ε/r ≤ 1, and

1 ≤ fat ε 32 (G) ≤ Pdim(G) = P (the lower bound of 1 follows from c 0 (3ε) -α > 0). Solving the inequation c 0 (3ε) -α ≤ cP log 2 (rP/ε) for ε (see Appendix B.3 for details), we get ε ≥ min ε ′′ 1 , c 1 P -1 α log -2 α P , (9)
for some constants ε ′′ 1 , c 1 > 0 depending only on p, c 0 , ba and α. Setting ε 1 = min{ε ′′ 1 , ε ′ 1 } and noting that ε ′ 1 only depends on ε 0 and ba, we conclude the proof.

Approximation of Hölder balls by feed-forward neural networks

In this section, we apply Corollary 1 to establish nearly-tight lower bounds for the approximation of unit Hölder balls by feed-forward neural networks. Our main result is Proposition 3, which solves an open question by [START_REF] Devore | Neural network approximation[END_REF].

Throughout the section, for any s > 0, we denote by n and α the unique members of the decomposition s = n + α such that n ∈ N and 0 < α ≤ 1.

For a set X ⊂ R d , we follow [START_REF] Yarotsky | The phase diagram of approximation rates for deep neural networks[END_REF] and define the Hölder space C n,α (X ) as the space of n times continuously differentiable functions with finite norm

f C n,α = max max n:|n|≤n D n f ∞ , max n:|n|=n sup x =y |D n f (x) -D n f (y)| x -y α 2 , where, for n = (n 1 , • • • , n d ) ∈ N d , D n f = ∂ ∂x1 n1 • • • ∂ ∂x d n d
f denotes the |n|-order partial derivative of f . We denote

F s,d = {f ∈ C n,α ([0, 1] d ) : f C n,α ≤ 1}.
Let λ denote the Lebesgue measure over [0, 1] d . In this section, we provide nearly matching upper and lower bounds for the L p (λ) approximation error of elements of F s,d by feed-forward ReLU neural networks. The bounds are expressed in terms of the number of weights of the network.

Known bounds on the sup norm approximation error

[YZ20] gives matching (up to a certain constant) lower and upper bounds of the sup norm approximation error of the elements of F s,d by feed-forward ReLU neural networks.

Proposition 2 ([YZ20]). Let d ∈ N * , s > 0, γ ∈ s d , 2s d . Consider n ∈ N and α ∈ (0, 1] such that s = n + α.
There exist positive constants W min and c 1 , depending only on d and n, such that for any integer W ≥ W min , there exists a feed-forward ReLU neural network architecture A with L = O(W γ d s -1 ) layers and W weights such that

sup f ∈F s,d inf g∈HA f -g ∞ ≤ c 1 W -γ . ( 10
)
In the meantime, there exists a constant c 2 > 0 depending only on d and n such that, for any feedforward neural network architecture A with W weights and L = o(W γ d s -1 / log W ) layers and for the ReLU activation function,

sup f ∈F s,d inf g∈HA f -g ∞ ≥ c 2 W -γ . ( 11
)
It is worth stressing that, for any probability measure µ on [0, 1] d , the upper bound (10) is automatically generalized to any smaller L p (µ) norm, when 1 ≤ p < +∞. However, the lower bound (11) does not immediately apply when • ∞ is replaced with

• L p (µ) , 1 ≤ p < +∞.
The lower bound of the next subsection shows that, in this setting, approximation in L p (λ) norm is not easier than in sup norm, solving an open question of DeVore et al. [START_REF] Devore | Neural network approximation[END_REF].

Nearly-matching lower bounds of the L p (λ) approximation error

We first state a lower bound on the packing number of F s,d , which is rather classical though hard to find in this specific form (see [START_REF] Mikhail Š Birman | Piecewise-polynomial approximation of functions of the classes w α p[END_REF] for the L ∞ norm, or [START_REF] Edmunds | Function Spaces, Entropy Numbers, Differential Operators[END_REF] for other Sobolev-type norms).

For the sake of completeness, we give a proof of Lemma 2 in the supplement, Appendix D.1.

Lemma 2. Let s > 0, d ∈ N * and 1 ≤ p < +∞. There exist constants ε 0 , c 0 > 0 such that for any

0 < ε ≤ ε 0 , log M ε, F s,d , • L p (λ) ≥ c 0 ε -d s . ( 12
)
Given Lemma 2, we can use Corollary 1 to establish the next proposition and obtain the lower bound on the L p (λ) approximation error.

Proposition 3. Let d ∈ N * , s > 0, γ ∈ s d , 2s d and 1 ≤ p < +∞. Consider n ∈ N and α ∈ (0, 1] such that s = n + α.
Let σ : R → R be a piecewise-affine function, and c > 0. Then, there exist c 1 > 0 and W min ∈ N * (depending only on s, d, p, σ and c) such that for any architecture A of depth 1 ≤ L ≤ cW γ d s -1 with W ≥ W min weights, and for the activation σ, the set H A (cf. Section 1) satisfies

sup f ∈F s,d inf g∈HA f -g L p (λ) ≥ c 1 W -γ log -3s d (W ) . (13)
Note that the rate of the lower bound does not depend on p. Note also that, when the activation function is ReLU (which is piecewise-affine), we obtain a lower bound which matches the upper bound of the previous subsection up to logarithmic factors.

Proof. From Lemma 2, there exist

ε 0 , c 0 > 0 such that log M ε, F s,d , • L p (λ) ≥ c 0 ε -d s for all 0 < ε ≤ ε 0 .
Combining with Corollary 1 and using L ≤ cW γ d s -1 concludes the proof.

Remark 1 (Comparison with existing proof strategies in sup norm.). We would like to highlight a key difference between the proof of Proposition 3 and the lower bound proof strategies of [Yar17, Yar18, YZ20, SYZ22] that are specific to the sup norm. Their overall argument is roughly the following: if G can approximate any f ∈ F in sup norm at accuracy ε > 0, since F contains many "oscillating" functions with oscillation amplitude roughly ε, then so must be the case for G (the sup norm is key here: all oscillations of any f ∈ F are well approximated). Therefore, a small ε implies a large VCdim(G), which by contrapositive enables to lower bound the approximation error (1) with a decreasing function of VCdim(G), and therefore as a function of L and W . In contrast, in the proof of Theorem 1, the key probability result of Mendelson (Proposition 1) enables us to show that, even if the oscillations of any f ∈ F are only well approximated on average (in L p (µ) norm) by G, then Pdim(G) must be large when ε 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. [START_REF] Devore | Neural network approximation[END_REF] mentioned in the introduction, showing in particular that VC dimension theory can (surprisingly) be useful to prove L p approximation lower bounds.

Approximation of monotonic functions by feed-forward neural networks

In this section, we consider the problem of approximating the set M d of all non-decreasing functions from [0, 1] d to [0, 1]. These are functions f : [0, 1] d → [0, 1] that are non-decreasing along any line parallel to an axis, i.e., such that, for all x, y ∈ [0, 1] d ,

x i ≤ y i , ∀i = 1, . . . , d =⇒ f (x) ≤ f (y) .
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 a vehicle as a 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, 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 L p (λ) norm.

Next we focus on the approximation of M d with Heaviside feed-forward neural networks. After proving an impossibility result for the sup norm, we show that the weaker goal of approximating M d in L p (λ) norm is feasible, and derive nearly matching lower and upper bounds. Interestingly, the approximation rates depend on p ≥ 1, which is in sharp contrast with the case of Hölder balls, that are not easier to approximate in L p (λ) norm than in sup norm (see Section 3).

Warmup: an impossibility result in sup norm

We start this section by showing that approximating monotonic functions of d ≥ 2 variables in sup norm is impossible with Heaviside neural networks.

Proposition 4. For any neural network architecture A with the Heaviside activation, the set H A (cf. Section 1) satisfies

sup f ∈M d inf g∈HA f -g ∞ ≥ 1 2 .
The proof of Proposition 4 is postponed to the supplement, Appendix E.2. We show a slightly stronger result, by exhibiting a single function f ∈ M d such that the lower bound of 1 2 holds simultaneously for all network architectures.

Next we study the approximation of M d in L p (λ) norm.

Lower bound in L p (λ) norm

We start by proving a lower bound, as a direct consequence of Corollary 1 and a lower bound on the packing number due to [START_REF] Gao | Entropy estimate for high-dimensional monotonic functions[END_REF].

Proposition 5. Let 1 ≤ p < +∞, d ≥ 1, and let α = max{d, (d -1)p}. Let σ : R → R be a piecewise-polynomial function having maximal degree ν ∈ N. Then, there exist positive constants c 1 , c 2 , c 3 , W min (depending only on d, p, and σ) such that for any architecture A of depth L ≥ 1 with W ≥ W min weights, and for the activation σ, the set H A (cf. Section 1) satisfies

sup f ∈M d inf g∈HA f -g L p (λ) ≥      c 1 W -2 α log -2 α (W ) if ν ≥ 2 , c 2 (LW ) -1 α log -3 α (W ) if ν = 1 , c 3 W -1 α log -3 α (W ) if ν = 0 . ( 14
)
Note that, contrary to the case of Hölder balls (Section 3), the rate of the lower bound depends on p through α = max{d, (d -1)p}.

Proof. From [GW07], there exist constants ε 0 , c 0 > 0 such that for ε ≤ ε 0 , log M ε, M d , • L p (λ) ≥ c 0 ε -α .
Using Corollary 1, we obtain the result.

Nearly-matching upper bound in L p (λ) norm

To the best of our knowledge, there does not exist any upper-bound of the L p (λ) approximation error of M d 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 research3 . However, we establish in the next proposition upper-bounds of the L p (λ) approximation error of M d with feedforward neural networks with the Heaviside activation function. This shows that, for the L p (λ) approximation error, the lower-bound obtained in (14), for ν = 0, is tight up to logarithmic factors. The next proposition follows by reinterpreting a metric entropy upper bound of [START_REF] Gao | Entropy estimate for high-dimensional monotonic functions[END_REF] in terms of Heaviside neural networks. The proof is postponed to Appendix E.1 in the supplement.

Proposition 6. Let 1 ≤ p < +∞, d ∈ N \ {0, 1} and let α = max{d, (d -1)p}. There exist positive constants W min and c, depending only on d and p, such that for any integer W ≥ W min , there exists a feed-forward architecture A with two hidden layers, W weights and the Heaviside activation function such that the set

H A satisfies sup f ∈M d inf g∈HA f -g L p (λ) ≤ cW -1 α if p(d -1) = d , cW -1 d log(W ) if p(d -1) = d . ( 15
)

Conclusion and other possible applications

We proved a general lower bound on the approximation error of F by G in L p (µ) norm (Theorem 1), in terms of generic properties of F and G (packing number of F , range of F , fat-shattering 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 ([Men02], see Proposition 1), solving a question raised by DeVore et al. [START_REF] Devore | Neural network approximation[END_REF].

In Sections 3 and 4 we detailed two applications, where Corollary 1 yields nearly optimal approximation lower bounds in L p norm, and which correspond to two examples where the approximation rate may depend or not depend on p.

Theorem 1 and Corollary 1 can be used to derive approximation lower bounds for many other cases. Corollary 1 only requires a (tight) lower bound on the packing number of F , for which approximation theory provides several examples. For instance, for the Barron space introduced in [Bar93], Petersen and Voigtlaender [START_REF] Petersen | Optimal learning of high-dimensional classification problems using deep neural networks[END_REF] showed a tight lower bound on the log packing number in L p (λ, [0, 1] d ) norm, of order ε -2d/(d+2) . Applying Corollary 1, this yields an approximation lower bound of (LW )

-( 1 2 + 1 d ) log -3( 1 2 + 1 d ) (W )
for ReLU networks (see Appendix F in 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 [START_REF] Blei | Metric entropy of high dimensional distributions[END_REF], multivariate convex functions [START_REF] Guntuboyina | Covering numbers for convex functions[END_REF], and functions with other shape constraints [START_REF] Groeneboom | Nonparametric Estimation under Shape Constraints: Estimators, Algorithms and Asymptotics[END_REF].

Piecewise-polynomial activation functions are not essential for the current derivation. Indeed, Theorem 1 can also be applied to the case where G corresponds to a neural network with other activation functions such as the sigmoid. In the sigmoid case, the pseudo-dimension is known to be at most of the order of W 4 (see [START_REF] Karpinski | Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks[END_REF][START_REF] Anthony | Neural Network learning: Theoretical Foundations[END_REF]), which we can use to derive an approximation lower bound similar to that of Corollary 1, with a smaller right-hand side for large W . However, to the best of our knowledge, it is not known whether the O(W 4 ) VC bound is tight (only a lower bound of the order of W 2 is known), so the resulting approximation lower bound could be loose. We leave this interesting question for future work.

Theorem 1 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 [START_REF] Wang | Vc dimension of partially quantized neural networks in the overparametrized regime[END_REF] on the VC dimension of partially quantized networks, while [START_REF] Belkin | Approximation beats concentration? an approximation view on inference with smooth radial kernels[END_REF] derived bounds on the fat-shattering dimension of some RKHS. Investigating such applications and whether the obtained approximation lower bounds are rate-optimal is a natural research direction for the future.

A general approximation lower bound in L p norm, with applications to feed-forward neural networks Supplementary Material This is the appendix for "A general approximation lower bound in L p norm, with applications to feed-forward neural networks".

A Feed-forward neural networks: formal definition

In all this paper, we use the following classical graph-theoretic definitions for feed-forward neural networks given, e.g., in [START_REF] Peter | Nearlytight vc-dimension and pseudodimension bounds for piecewise linear neural networks[END_REF] (with slightly different terms and notation).

A feed-forward neural network architecture A of depth L ≥ 1 is a directed acyclic graph (V, E) with d ≥ 1 nodes with in-degree 0 (also called the input neurons), a single node with out-degree 0 (also called the output neuron), and such that the longest path in the graph has length L.

We define layers ℓ = 0, 1, . . . , L recursively as follows:

• layer 0 is the set V 0 of all input neurons; we assume that V 0 = {1, . . . , d} without loss of generality.

• for any ℓ = 1, . . . , L, layer ℓ is the set V ℓ of all nodes that have one or several predecessors5 in layer ℓ-1, possibly other predecessors in layers 0, 1, . . . , ℓ-2, but no other predecessors.

Layer L consists of a single node: the output neuron. Layers 1, . . . , L -1 are called the hidden layers (if L ≥ 2). Note that skip connections are allowed, i.e., there can be connections between non-consecutive layers.

Given a feed-forward neural network architecture A of depth L ≥ 1, we associate real numbers w e ∈ R to all edges e ∈ E and w v ∈ R to all nodes v ∈ V 1 ∪ . . . ∪ V L . These real numbers are called weights (they correspond to linear coefficients and biases) and are concatenated in a weight vector w ∈ R W , where W = Card(E) + L ℓ=1 Card(V ℓ ) is the total number of weights. Given A, an associated weight vector w ∈ R W , and a function σ : R → R (called activation function), the network represents the function g w : R d → R defined recursively as follows. We write P v ⊂ V for the set of all predecessors of any node v ∈ V , and w u→v for the weight on the edge from u to v. The recursion from layer ℓ = 0 to layer ℓ = L reads: given

x = (x 1 , . . . , x d ) ∈ R d ,
• each input neuron v ∈ {1, . . . , d} outputs the value

y v := x v ; • for any ℓ = 1, . . . , L -1, each neuron v ∈ V ℓ outputs y v := σ u∈Pv w u→v y u + w v ; • the unique output neuron v ∈ V L outputs g w (x) := u∈Pv w u→v y u + w v .
Finally, we define H A := {g w : w ∈ R W } to be the set of all functions that can be represented by tuning all the weights assigned to the network (the dependency on the activation function σ is not written explicitly).

B Main results: technical details

We provide technical details that were missing to establish Proposition 1, Theorem 1 and Corollary 1.

B.1 Proof of Proposition 1

Proposition 1 is a direct extension of [Men02, Corollary 3.12] to any range [a, b]. We first recall this result but in slightly different terms (see the comments afterwards).

Proposition 7 (Corollary 3.12 in [START_REF] Mendelson | Rademacher averages and phase transitions in glivenko-cantelli classes[END_REF], "almost equivalent" statement). Let G be a set of measurable functions from a measurable space X to [0, 1], such that fat γ (G) < +∞ for all γ > 0. Then, for every 1 ≤ p < +∞, there is some constant c p > 0 depending only on p such that, for every probability measure µ on X and every ε > 0,

log M ε, G, • L p (µ) ≤ c p fat ε 32 (G) log 2 2 fat ε 32 (G) ε .
To be precise, [Men02, Corollary 3.12] was stated a little differently. Instead of the assumption on fat γ (G), there were two conditions on G: (i) G satisfies a weak measurability assumption such as the "image admissible Suslin" property, and (ii) G is a uniform Glivenko-Cantelli class. Fortunately, note that assumption (i) could easily be checked in special cases such as the setting of Corollary 1, and that assumption (ii) is equivalent to fat γ (G) < +∞ for all γ > 0 when (i) holds and when G only consists of [0, 1]-valued functions (see [START_REF] Noga Alon | Scale-sensitive dimensions, uniform convergence, and learnability[END_REF], Theorem 2.5). The two statements are thus "almost equivalent". However, we stress that (i) and (ii) are not necessary (assuming fat γ (G) < +∞ for all γ > 0). To see why, it suffices to adapt the proof of [Men02, Corollary 3.12] as follows: instead of starting from an ε-packing of G in empirical L p (µ n ) norm and showing that it is also an ε ′ -covering of G in L p (µ) norm, with ε ′ > ε, we can start from an ε-packing of G in L p (µ) norm and show that it is also an ε-packing of G in empirical L p (µ n ) norm for some large integer n (with positive probability). This last statement directly follows from the Hoeffding inequality: no uniform law of large numbers is required, since we only need to compare empirical averages to their expectations for a finite number of bounded functions. 6We now explain how to derive Proposition 1 (with an arbitrary range [a, b]) as a straightforward consequence of Proposition 7.

Proof (of Proposition 1). In order to apply Proposition 7, we reduce the problem from Note that every g ∈ G is indeed [0, 1]-valued.

We now note that translation does not affect packing numbers nor the fat-shattering dimension, while rescaling only changes the scale ε by a factor of ba. More precisely, we have the following two properties:

Property 1: For all u > 0, fat u b-a ( G) = fat u (G). Property 2: For all u > 0, M u b-a , G, • L p (µ) = M u, G, • L p (µ)
. Before proving the two properties (see below), we first conclude the proof of Proposition 1. By Property 1, fat γ ( G) = fat γ(b-a) (G), which by assumption is finite for all γ > 0. Since every

g ∈ G is [0, 1]-valued, we can thus apply Proposition 7. Using it with ε = ε/(b -a), we get log M ε, G, • L p (µ) ≤ c p fat ε 32 ( G) log 2 2 fat ε 32 ( G) ε .
Combining with the two equalities in Properties 1 and 2, we obtain

log M ε, G, • L p (µ) ≤ c p fat ε 32 (G) log 2 2(b -a) fat ε 32 (G) ε ,
which concludes the proof of Proposition 1.

We now prove the two properties.

Proof of Property 1. We first show that fat u b-a ( G) ≥ fat u (G). To that end, let S = {x 1 , . . . , x m } and r : S → R be such that for any E ⊂ S, there exists g ∈ G such that g(x) ≥ r(x) + u if x ∈ E and g(x) ≤ r(x)-u otherwise. Setting r(x) = r(x)-a b-a , we can see that g(x) ≥ r(x)+ u b-a if x ∈ E and g(x) ≤ r(x) -u b-a otherwise, which proves fat u b-a ( G) ≥ fat u (G). The reverse inequality is proved similarly.

Proof of Property 2. Let {g 1 , . . . , g m } be a u-packing of G in L p (µ) norm. This means that g ig j L p (µ) > u and therefore gigj L p (µ) > u b-a for all i = j ∈ {1, . . . , m}, so that

{g 1 , . . . , gm } ⊂ G is a u b-a -packing of G. This proves M u b-a , G, • L p (µ) ≥ M u, G, • L p (µ)
. The reverse inequality is proved similarly.

B.2 Clipping can only help

The next two lemmas indicate that clipping (truncature) to a known range can only help. These are key to apply Proposition 1 in our setting. In the sequel, for a set G of functions from a set X to R, and for a < b in R, we denote by G is also γ-shattered by G. Let us consider such a subset A = {x 1 , . . . , x N } ⊂ X, with cardinality N ≥ 1. Hence, there exists {r 1 , . . . , r N } ⊂ R such that for any

E ⊂ A, there exists g ∈ G [a,b] such that g(x i ) -r i ≥ γ if x i ∈ E and g(x i ) -r i ≤ -γ otherwise.
Note that this must imply that r i ∈]a, b[ for all i = 1, . . . , N (indeed, by choosing E such that x i ∈ E or not, we have either r i +γ ≤ g(x i ) ≤ b or r i -γ ≥ g(x i ) ≥ a). Now fix i ∈ {1, . . . , N } and let us assume g(x i )-r i ≥ γ (by symmetry, the reversed case g(x i )r i ≤ -γ is treated the same way). Because r i > a, this implies that g(x i ) > a and thus g(x i ) ≥ g(x i ) (by definition of g), which entails g(x i )r i ≥ γ. It follows that if G [a,b] γ-shatters A, then G also γ-shatters A, and the result follows.

The following lemma formalizes the well-known idea that it is easier to approach a function with values in a finite range by a function with values in the same range.

Lemma 4. Let G be a set of measurable functions from a measurable space X to R, and let G [a,b] be defined as above. Assume F is a set of measurable functions from X to [a, b]. Then, for any probability measure µ on X , sup

f ∈F inf g∈G f -g L p (µ) ≥ sup f ∈F inf g∈G [a,b] f -g L p (µ) .
Proof. To prove the above result, it is enough to show that for any f ∈ F and g ∈ G, the function g is pointwise at least as close to f as g is, which for all f ∈ F yields inf g∈G f -

g L p (µ) ≥ inf g∈G [a,b] f -g L p (µ) . By definition of G [a,b] , for any x ∈ X , if g(x) ∈ [a, b], then |f (x)-g(x)| = |f (x) -g(x)|. And if g(x) / ∈ [a, b], then |f (x) -g(x)| < |f (x) -g(x)| since f (x) ∈ [a, b].
It follows that the discrepancy |f -g| is everywhere bounded by |f -g|, and the result follows.

B.3 Missing details in the proof of Theorem 1

We provide all details that were missing to derive (9), which is a direct consequence of Lemma 5 below. We follow the convention aP -1 α log -2 α (P ) = +∞ when P = 1. Lemma 5. Let P ∈ N * and c, α, r > 0. There exist constants a, ε ′′ 1 > 0 depending only on c, α and r such that, for all ε ∈ (0, r) satisfying

ε -α ≤ cP log 2 rP ε , (16)
we have

ε ≥ min ε ′′ 1 , aP -1 α log -2 α (P ) .
Proof. Assume ε ∈ (0, r) is such that (16) holds. To show the result, we study the function f :

(1/r, +∞) → R defined for all x > 1/r by f (x) = x α log 2 (rP x) .

Note that (16) implies that f (1/ε) ≤ cP . For all P ≥ 2, we set

ε P = P -1 α log -2 α (P ) . (17)
Let P 1 ≥ 2 be such that P

1 α 1 log 2 α (P 1 ) ≥ exp( 2 α ) r
. For all P ≥ P 1 , we have

1 εP ≥ exp( 2 α ) r > 1/r and f 1 ε P = P log 2 (P ) log 2 rP 1+ 1 α log 2 α (P ) . Since lim Q→+∞ log 2 (Q) log 2 rQ 1+ 1 α log 2 α (Q) = 1 (1 + 1 α ) 2 =: c 1 ,
there exists P 2 such that for all Q ≥ P 2 , we have

log 2 (Q) log 2 rQ 1+ 1 α log 2 α (Q) ≥ c1 2 .
Below we distinguish the cases P ≥ max(P 1 , P 2 ) and P < max(P 1 , P 2 ).

1st case: P ≥ max(P 1 , P 2 ).

We have f 1 εP ≥ c1P 2 and P ≥ 1 c f 1 ε (by ( 16)), so that f 1 εP ≥ c1 2c f 1 ε . We now use Lemma 6 below with b = c1 2c : setting a := (b/2) 1/α = (c 1 /(4c)) 1/α , there exists x 1 > max 1 r , 1 ar depending only on r, b, α such that bf (x) ≥ f (ax) for all x ≥ x 1 .

Therefore, if ε < 1 x1 =: ε 1 , then c1 2c f 1 ε ≥ f a ε . Therefore f ( 1 εP ) ≥ f a ε .
Recall from (17) and

P ≥ P 1 that 1 εP ≥ exp( 2 α ) r . If ε < ar exp( 2 α ) =: ε 2 , then we also have a ε ≥ exp( 2 α ) r . Therefore, using Lemma 6 again, f ( 1 εP ) ≥ f ( a ε ) implies that 1 εP ≥ a ε , that is, ε ≥ a ε P .
Summarizing, when ε ∈ (0, r) satisfies ( 16) and when P ≥ max(P 1 , P 2 ),

either ε ≥ ε 1 or ε ≥ ε 2 or ε ≥ a ε P . Put differently, ε ≥ min(ε 1 , ε 2 , a ε P ) . ( 18
)
2nd case: P < max(P 1 , P 2 ) =: P 3 . Using (16) and the fact that t → ct log 2 rt ε is non-decreasing on [ε/r, +∞), together with ε/r ≤ 1 ≤ P ≤ P 3 yields ε -α ≤ cP 3 log 2 (rP 3 /ε). This entails that, for some ε 3 > 0 depending only on α, c, P 3 , r, ε ≥ ε 3 .

Conclusion: combining the two cases, when ε ∈ (0, r) satisfies (16), whatever P ∈ N * , we have (18) or (19). Setting ε ′′ 1 = min(ε 1 , ε 2 , ε 3 ), we obtain

ε ≥ min ε ′′ 1 , a P -1 α log -2 α (P ) .
(Note that this is also true in the case P = 1, by the convention aP -1 α log -2 α (P ) = +∞.) Since ε 1 , ε 2 , ε 3 and a only depend on c, α, r, this concludes the proof. Lemma 6. Let α, r > 0 and P ∈ N * . We define f (x) =

x α log 2 (rP x) for all x > 1/r. Then:

i) f is increasing on I := exp( 2 α ) r
, +∞ and lim x→+∞ f (x) = +∞.

ii) for all b > 0, setting a := (b/2) 1/α , there exists x 1 > max 1 r , 1 ar depending only on r, b, α such that, ∀x ≥ x 1 , bf (x) ≥ f (ax) .

Proof. Proof of i): The fact that lim x→+∞ f (x) = +∞ is because α > 0. To see why f is increasing on I, note that

f ′ (x) = αx α-1 log 2 (rP x) -x α 2 log(rP x) 1 x log 4 (rP x) = x α-1 log(rP x)(α log(rP x) -2) log 4 (rP x) , so that f ′ (x) > 0 for all x > exp( 2 α )
rP , and in particular for all x > exp( 2 α ) r (since P ≥ 1). This proves that f is increasing on I.

Proof of ii): Let b > 0 and set a := (b/2) 1/α . Let x 1 > max 1 r , 1 ar depending only on r, b, α such that, for all u ≥ x 1 , log 2 (ru) log 2 (rau) ≤ 2 .

(Such an x 1 exists since the ratio converges to 1 as u → +∞, and we can choose x 1 as a function of r, a only.) Now, for all x ≥ x 1 , using the above inequality with u = P x ≥ x (since P 1), we get

f (ax) f (x) = a α log 2 (rP x) log 2 (rP ax) ≤ 2a α = b ,
where the last equality is because a := (b/2) 1/α . This proves that bf (x) ≥ f (ax) for all x ≥ x 1 .

B.4 Proof of Corollary 1

We first recall some definitions and two key bounds on the VC-dimension of piecewise-polynomial feed-forward neural networks, proved by [START_REF] Goldberg | Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers[END_REF] and [START_REF] Peter | Nearlytight vc-dimension and pseudodimension bounds for piecewise linear neural networks[END_REF].

For a set F of functions from X to {-1, 1}, we say that a set S = {x 1 . . . , x N } ⊂ X is shattered by F if for any E ⊂ S, there exists f ∈ F satisfying for all i = 1, . . . , N , f

(x i ) = 1 if x i ∈ E, and f (x i ) = -1 if x i / ∈ E.
The VC-dimension of F , denoted by VCdim(F ), is defined as the largest number N ≥ 1 such that there exists S ⊂ X of cardinality N which is shattered by F (by convention, VCdim(F ) = 0 if no such set S exists, while VCdim(F ) = +∞ if there exist sets S of unbounded cardinality N ).

Let B be any feed-forward neural network architecture of depth L ≥ 1 with W ≥ 1 weights, d ≥ 1 input neurons, and U ≥ 1 hidden or output neurons. Let σ : R → R be any piecewise-polynomial activation function on K ≥ 2 pieces, with maximal degree ν ∈ N. Denote by sgn(H B ) = {sgn(g w ) : w ∈ R W } the set of all classifiers obtained by looking at the sign of the network's output, that is, the classifiers defined by sgn(g w )(x) = 1 {gw(x)>0} for all x ∈ R d .

Goldberg and Jerrum [START_REF] Goldberg | Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers[END_REF] showed that, for some constant c ′ 1 > 0 depending only on d, ν and K, the VC-dimension of sgn(H B ) is bounded as follows (see also Theorem 8.7 in [START_REF] Anthony | Neural Network learning: Theoretical Foundations[END_REF]):

VCdim(sgn(H B )) ≤ c ′ 1 W 2 . ( 20
)
This bound was refined for piecewise-affine activation functions. Namely, Bartlett et al. [START_REF] Peter | Nearlytight vc-dimension and pseudodimension bounds for piecewise linear neural networks[END_REF]Theorem 7] proved that, if U ≥ 3, then, for some

R ≤ U + U (L -1)ν L-1 , VCdim(sgn(H B )) ≤ L + LW log 2 4e(K -1)R log 2 2e(K -1)R ,
where L = 1 if ν = 0, and L ≤ L otherwise. Therefore, for some constants W ′ min ≥ 1 and c ′ 2 , c ′ 3 > 0 depending only on d and K, we have, for all W ≥ W ′ min (which in particular implies

U ≥ 3), VCdim(sgn(H B )) ≤ c ′ 2 LW log(W ) if ν = 1 , c ′ 3 W log(W ) if ν = 0 . ( 21
)
We are now ready to prove Corollary 1 from Theorem 1.

Proof (of Corollary 1). In order to apply Theorem 1, we first bound P := Pdim(H A ) from above. The bounds (20) and ( 21) were on the VC-dimension of sgn(H B ), for any feed-forward neural network architecture B, while we need a bound on the pseudo-dimension. However, by a wellknown trick (e.g., Theorem 14.1 in [START_REF] Anthony | Neural Network learning: Theoretical Foundations[END_REF]), the pseudo-dimension of H A is upper bounded by the VC-dimension of (the sign of) an augmented network architecture of depth L, with d + 1 input neurons and W + 1 weights.7 Therefore, replacing (d, W ) with (d + 1, W + 1) in ( 20) and ( 21), we get that, for some constants Wmin ≥ 1 and c1 , c2 , c3 > 0 depending only on d, ν and K, for all W ≥ Wmin ,

P ≤    c1 W 2 if ν ≥ 2 , c2 LW log(W ) if ν = 1 , c3 W log(W ) if ν = 0 . ( 22
)
Now, by Theorem 1, we have, for some constants c 1 , ε 1 > 0 depending only on ba, p, c 0 , ε 0 , α,

sup f ∈F inf g∈HA f -g L p (µ) ≥ min ε 1 , c 1 P -1 α log -2 α (P ) . ( 23
)
Noting that P → min ε 1 , c 1 P -1 α log -2 α (P ) is non-increasing and plugging ( 22) into (23), we get, for W ≥ W min ,

sup f ∈F inf g∈HA f -g L p (µ) ≥ min      ε 1 ,    c 4 W -2 α log -2 α (W 2 ) if ν ≥ 2 c 5 (LW log(W )) -1 α log -2 α (LW log(W )) if ν = 1 c 6 (W log(W )) -1 α log -2 α (W log(W )) if ν = 0        
for some constants W min ≥ 1 and c 4 , c 5 , c 6 > 0 depending only on d, ν, K, ba, p, c 0 , ε 0 and α.

Taking W min large enough, the first term ε 1 is always larger than the second term in the above minimum, and the logarithmic terms log(W log(W )) and log(LW log(W )) can be upper bounded by a constant times log(W ) (since L ≤ W ). Rearranging concludes the proof.

C Earlier works: two other lower bound proof strategies

Approximation lower bounds in a sense similar to ours have been obtained in other recent works. In the purpose of highlighting the differences between the different approaches, we describe the lower bound proof strategies of Yarotsky [START_REF] Yarotsky | Error bounds for approximations with deep relu networks[END_REF] and of Petersen and Voigtlaender [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF].

C.1 Approximation in sup norm of Sobolev unit balls with ReLU networks [START_REF] Yarotsky | Error bounds for approximations with deep relu networks[END_REF] Recall that the Sobolev space W n,∞ ([0, 1] d ) is defined as the set of functions on [0, 1] d lying in L ∞ along with all their weak derivatives up to order n. We equip this space with the norm

f W n,∞ ([0,1] d ) = max n∈N d :|n|≤n ess sup x∈[0,1] d |D n f (x)|,
and we let F n,d be the unit ball of this space.

We first state the sup norm lower bound and then we give a synthesized version of the proof.

Proposition 8 ([Yar17]

). There exists positive constants W min , c > 0 such that for any feed-forward neural network with architecture A, ReLU activation and W ≥ W min weights,

sup f ∈F n,d inf g∈HA f -g ∞ ≥ cW -2n d .
Details aside, the proof reads as follows.

) ≤ c ′ W 2 for some constant c ′ .
It is worth stressing that in this proof, it is paramount to assume that H A approximates F n,d in sup norm, rather than any L p norm with p < +∞. The reason is that only this choice of norm allows to bound the discrepancy between f ∈ F n,d and g f ∈ H A chosen optimally with respect to f at any chosen points. Our proof strategy relying on Proposition 1 allows to circumvent this issue by relating the pseudo-dimension to the metric entropy with respect to any L p norm, 1 ≤ p < +∞.

C.2 Approximation in L p norm of Horizon functions with quantized networks [PV18]

The authors study quantized neural networks, that is, networks with weights constrained to be representable with a fixed number of bits. They obtain a lower bound on the minimal number of weights in a quantized neural network that can approximate a set of Horizon functions in L p norm, p > 0, with error ε > 0. This lower bound is easily invertible to a bound on the approximation error and is thus comparable to the results we obtain in this paper.

Textually, the authors introduce the set of horizon functions as follows: "These are {0, 1}-valued functions with a jump along a hypersurface and such that the jump surface is the graph of a smooth function" [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF]. Denoting by H the indicator function of the set [0, +∞) × R d-1 , the set of horizon functions reads as

HF β,d,B = f • T ∈ L ∞ - 1 2 , 1 2 d : f (x) = H(x 1 + γ(x 2 , . . . , x d ), x 2 , . . . , x d ), γ ∈ F β,d-1,B , T ∈ Π(d, R) ,
where F β,d-1,B denotes the set of Hölder functions over [-1/2, 1/2] d-1 whith smoothness parameter β and with norm . C n,α bounded by B (see Section 3), and Π(d, R) denotes the group of d-dimensional permutation matrices.

In the following, for any nonzero integer K and any neural network architecture A, we denote by H K A ⊂ H A the set of K-quantized functions in H A ; namely, the functions in H A with weights representable using at most K bits. The lower bound in [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF] (Theorem 4.2) reads as follow: Proposition 9 ([PV18]). Let d ≥ 2. Let p, β, B, c 0 > 0 and let σ : R → R be such that σ(0) = 0. There exist positive constants ε 0 , c > 0 depending only on d, p, β, B and c 0 such that, for any ε ≤ ε 0 , setting K = ⌈c 0 log(1/ε)⌉, for any feed-forward neural network architecture A with W weights and activation σ such that H K A approximates HF β,d,B in L p norm with error less than ε, we have

W ≥ cε -p(d-1) β log -1 (1/ε).
The proof of this result is based on a lemma giving a lower bound on the minimal number of bits ℓ necessary for a binary encoder-decoder pair to achieve an error less than ε > 0 in approximating HF := HF β,d,B in L p norm. Formally, given an integer ℓ > 0, a binary encoder E ℓ : HF → {0, 1} ℓ and given a decoder D ℓ : {0, 1} ℓ → HF , one can measure an approximation error sup

f ∈HF f -D ℓ (E ℓ (f )) L p ,
which quantifies the loss of information due to the encoding E ℓ . Clearly, for an optimal choice of encoder, one can reduce this loss of information by increasing ℓ. In particular, for ε > 0, it is possible to estimate

ℓ ε = min ℓ > 0 : inf E ℓ ,D ℓ sup f ∈HF f -D ℓ (E ℓ (f )) L p ≤ ε ,
with the convention that ℓ ε = ∞ if the above set is empty. The authors show in their Lemma B.3 that for ε small enough (smaller than some ε 0 > 0), it holds that

ℓ ε ≥ cε -p(d-1) β (24)
for some constant c > 0 depending only on d, p, β and B. In other words, one can not achieve a loss of information smaller than ε by encoding functions in HF over less than cε -p(d-1) β bits.

The rest of the proof consists in showing that for an integer K > 0, given a neural network architecture A with W weight that can approximate HF in L p norm with error less than ε > 0, one can encode exactly (without loss of information, and for a given activation function) any function in H K A over a string of ℓ = c 1 W (K + ⌈log 2 W ⌉) bits. This generates a natural encoder-decoder system where any function f ∈ HF is encoded as the bit string of length ℓ associated to g f ∈ H K A chosen to approximate f . It remains to observe that if we fix K, this automatically yields a lower bound on ℓ using inequality (24), and thus on W by expressing W through ℓ and K.

Remark. The authors in [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF] study the neural network approximation in a setting slightly different from ours, since they focus on the approximation by quantized neural networks. This partly explains why their proof strategy differs from ours. However, it is worth pointing out that the proof of their lower bound on the minimal number of bits required to accurately encode a function in HF relies on a lower bound of the packing number of HF, just like the lower bound of the packing number of the set to approximate is key in our proof strategy. An interesting question for the future would be to see whether our general lower bound (Theorem 1) yields lower bounds of the same order as those in [START_REF] Petersen | Optimal approximation of piecewise smooth functions using deep relu neural networks[END_REF] for quantized neural networks.

D Hölder balls D.1 Proof of Lemma 2

Though not necessarily stated this way, many arguments below are classical (see, e.g., Theorem 3.2 by [START_REF] Györfi | A Distribution-Free Theory of Nonparametric Regression[END_REF] with a similar construction for lower bounds in nonparametric regression).

Let N ∈ N * . For m = (m 1 , . . . , m d ) ∈ {0, . . . , N -1} d , we let x m := 1 N (m 1 +1/2, . . . , m d +1/2) and we denote by C m the cube of side-length 1 N centered at x m , with sides parallel to the axes. We see that the N d cubes C m decompose the cube [0, 1] d in smaller parts which, up to negligible sets which will not be problematic, form a partition of [0, 1] d . We will use this decomposition to construct a packing of F s,d . Denoting • the sup norm in R d , we define the C ∞ test function φ : R d → R by:

φ(x) = exp - x 2 1 -x 2 ,
for any x ∈ R d such that x < 1, and φ(x) = 0 otherwise. Recalling that n ∈ N and α ∈ (0, 1] are such that s = n + α, and since all the high-order partial derivatives of φ are uniformly bounded on [0, 1] d , φ C n,α is thus finite and is nonzero.

Let c s = 1 2 (2N ) -s φ -1 C n,α and consider, for any tensor of signs σ = (σ m ) m∈{0,••• ,N -1} d ∈ {-1, 1} N d ,
the function f σ defined as follows:

f σ (x) = c s m∈{0,...,N -1} d σ m φ (2N (x -x m )) , for all x ∈ [0, 1] d . There are 2 N d different functions f σ .
Let us prove that, for all σ ∈ {-1, 1} N d , f σ ∈ F s,d . To do so, we study the constituents of f σ C n,α separately and show that they are all bounded by 1. For m ∈ {0, • • • , N -1} d , we define the function g m (x) = c s σ m φ (2N (xx m )). Note that because φ vanishes outside (-1, 1) d , we have that g m vanishes everywhere outside the interior of C m , and the same holds for D n g m for all n ∈ N d such that |n| ≤ n. For any such n, we have

D n g m ∞ = c s (2N ) |n| D n φ ∞ ≤ c s (2N ) s φ C n,α ≤ 1 2 .
Therefore,

max n:|n|≤n D n f σ ∞ ≤ 1. Now for any n ∈ N d such that |n| = n, any x, y ∈ [0, 1] d , we have |D n f σ (x) -D n f σ (y)| x -y α 2 = |D n g m (x) -D n g m ′ (y)| x -y α 2 ,
where x ∈ C m and y ∈ C m ′ for some multi-indexes m and m ′ . We have to distinguish between the cases m = m ′ and m = m ′ . In the former case, we have

|D n f σ (x) -D n f σ (y)| x -y α 2 = c s (2N ) n+α |D n φ(2N (x -x m )) -D n φ(2N (y -x m ))| 2N (x -x m ) -2N (y -x m ) α 2 = c s (2N ) s |D n φ(x ′ ) -D n φ(y ′ )| x ′ -y ′ α 2 ≤ c s (2N ) s φ C n,α = 1 2 ,
where at the second line, we used the changes of variables x ′ = 2N (xx m ) and y ′ = 2N (yx m ).

In the case m = m ′ (x and y belong to the same cube), we thus have

|D n f σ (x) -D n f σ (y)| x -y α 2 ≤ 1.
In the case m = m ′ , observe that we have

|D n g m (x) -D n g m ′ (y)| ≤ 2 max{|D n g m (x)|, |D n g m ′ (y)|}. (25)
Besides, recall that D n g m and D n g m ′ both vanish outside of the interiors of C m and C m ′ respectively. We can thus rewrite (25) as

|D n g m (x) -D n g m ′ (y)| ≤ 2 max{|D n g m (x) -D n g m (y)|, |D n g m ′ (x) -D n g m ′ (y)|} ≤ 2c s (2N ) n max{|D n φ(2N (x -x m )) -D n φ(2N (y -x m ))|, |D n φ(2N (y -x m ′ )) -D n φ(2N (y -y m ′ ))|}.
This entails

|D n f σ (x) -D n f σ (y)| x -y α 2 ≤ c s 2(2N ) s max |D n φ(x ′ ) -D n φ(y ′ )| x ′ -y ′ α 2 , |D n φ(x ′′ ) -D n φ(y ′′ )| x ′′ -y ′′ α 2 ≤ c s 2(2N ) s φ C n,α = 1,
where x ′ = 2N (xx m ) and y ′ = 2N (yx m ), and x ′′ = 2N (xx m ′ ) and y ′′ = 2N (yx m ′ ).

Summarizing, we showed that for all σ ∈ {-1,

1} N d max n:|n|≤n D n f σ ∞ ≤ 1 and max n:|n|=n sup x =y |D n f σ (x) -D n f σ (y)| x -y α 2 ≤ 1.
We conclude that for all σ ∈ {-1,

1} N d f σ C n,α ≤ 1,
and therefore {f σ : σ ∈ {-1, 1} N d } ⊂ F s,d .
Let us now evaluate the distance between distinct elements of {f σ :

σ ∈ {-1, 1} N d }. Let σ 1 , σ 2 ∈ {-1, 1} N d , with σ 1 = σ 2
, and let m ∈ {0, . . . , N -1} d be such that σ 1 m = -σ 2 m . Let us estimate ∆ p the L p (λ) discrepancy between f σ 1 and f σ 2 on the cube C m , that is

∆ p p = Cm |f σ 1 (x) -f σ 2 (x)| p dx = 2 p c p s Cm |φ (2N (x -x m )) | p dx = 2 p c p s (2N ) -d φ p L p (λ) .
It remains to find a subset among the functions f σ such that any two functions of this set differ on a significant number of cubes C m . According to the Varshamov-Gilbert Lemma [Yu97], there exists Γ ⊂ {-1, 1} N d with cardinal at least exp(N d /8) such that for any σ 1 , σ 2 ∈ Γ, such that σ 1 = σ 2 , σ 1 and σ 2 differ on at least one fourth of their coordinates; i.e.,

N d k=1 1 σ 1 k =σ 2 k ≥ N d 4 . We thus fix such a set Γ ⊂ {-1, 1} N d . For any σ 1 , σ 2 ∈ Γ, with σ 1 = σ 2 , f σ 1 -f σ 2 p L p (λ) = m:σ 1 m =σ 2 m Cm |f σ 1 (x) -f σ 2 (x)| p dx ≥ N d 4 ∆ p p = 2 p-d c p s 4 φ p L p (λ)
. Finally, recalling the definition of c s , we have for any

σ 1 , σ 2 ∈ Γ, with σ 1 = σ 2 , f σ 1 -f σ 2 L p (λ) ≥ 2 1-d+2 p 1 2 (2N ) -s φ -1 C n,α φ L p (λ) = cN -s , where c = 2 -s-d+2 p φ L p (λ) φ C n,α . It follows that {f σ : σ ∈ Γ} is a cN -s -packing of F s,d . Given the lower bound on the size of Γ, this implies M cN -s , F s,d , • L p (λ) ≥ exp(N d /8), for all N ∈ N * .
Set ε 0 = c and c 0 = 2 -d c d s /8. Consider ε > 0, with ε ≤ ε 0 . To conclude the proof, we need to show that (12) holds for ε. To do so, we consider N : the smallest integer such that cN -s ≥ ε ≥ c(2N ) -s . This N ∈ N * exists because 0 < ε ≤ ε 0 = c and s > 0. On one side, we have

M ε, F s,d , • L p (λ) ≥ M cN -s , F s,d , • L p (λ) ,
and on the other side, since 2N ≥ c

1 s ε -1 s , exp(N d /8) ≥ exp(2 -d c d s ε -d s /8) = exp(c 0 ε -d s ).
Combining the last three inequalities, we finally obtain log M ε, F s,d , • L p (λ) ≥ c 0 ε -d/s , for all 0 < ε ≤ ε 0 .

E Monotonic functions

This section contains the proofs of the results stated in Section 4. More precisely, in Section E.1 we provide the proof of Proposition 6 and in Section E.2 we provide the proof of Proposition 4.

E.1 Proof of Proposition 6

The section contains two sub-sections. In the first sub-section, we provide a proposition on the representation of piecewise-constant functions with Heaviside neural-networks. Section E.1.2 contains the main part of the proof of Proposition 6.

E.1.1 Representing piecewise-constant functions with Heaviside neural networks

We first describe a neural network architecture which, with the Heaviside activation function, is able to represent functions that are piecewise-constant on cubes.

Proposition 10. Let d ∈ N * , M ∈ N * . There exists an architecture A with two-hidden layers, 2(d + 1) 2 M weights and the Heaviside activation function, such that for any We allow the faces to belong to the cube or not. To distinguish them, we denote J i ∈ {1, . . . , 2d} the number of faces that belong to C i . We index the J i faces that belong to the cube from 1 to J i , and the other faces from J i + 1 to 2d. Thus, for all i ∈ {1, . . . , M } and all j ∈ {1, . . . , 2d}, there exist

(α i ) 1≤i≤M ∈ R M , any collection (C i ) 1≤i≤M of mutually disjoint hypercubes of R d the function f : R d → [0, 1] defined by ∀x ∈ R d , f (x) = M i=1 α i 1 Ci (x) satisfies f ∈ H A .
w i j ∈ R d , b i j ∈ R such that C i = Ji j=1 {x ∈ R d : w i j , x + b i j ≥ 0} ∩ 2d j=Ji+1 {x ∈ R d : w i j , x + b i j > 0} .
We rewrite:

C i =    x ∈ R d : Ji j=1 1 { w i j ,x +b i j ≥0} + 2d j=Ji+1 1 { w i j ,x +b i j >0} ≥ 2d    . (26)
Denoting for all i ∈ {1, . . . , M } and all j ∈ {1, . . . , 2d} and for all x ∈ R d ,

p i j (x) = σ w i j , x + b i j if j ≤ J i 1 -σ -w i j , x -b i j otherwise,
we have, see Figure 1 and (26), for all x ∈ R d

1 Ci (x) = 1 if 2d j=1 p i j (x) ≥ 2d, 0 otherwise, = σ   2d j=1 p i j (x) -2d   .
Since the hypercubes are mutually disjoints, for all x ∈ [0, 1] d , we have

f (x) = M i=1 α i σ   Ji j=1 σ w i j , x + b i j + 2d j=Ji+1 1 -σ -w i j , x -b i j -2d   = M i=1 α i σ   2d j=1 ε i j σ wi j , x + bi j -J i   , (27)
where

ε i j = +1 if j ≤ J i -1 otherwise, wi j = w i j if j ≤ J i -w i j otherwise, bi j = b i j if j ≤ J i -b i j otherwise.
Equation ( 27) is the action of the Heaviside neural network with two hidden layers whose architecture is on • the architecture has M edges going to the output layer, due to the α i ;

• it has M biases associated to the neurons of the second hidden layer (they correspond to the terms -J i );

• between the second and the first hidden layer, the architecture has M × 2d edges (corresponding to the ε i,j );

• it has M × 2d biases associated to the neurons of the first hidden layer (the bi j );

• it has M × 2d × d edges between the first hidden layer and the entry (the wi j ).

Thus there are 2M + 2M × 2d + M × 2d × d = 2(d 2 + 2d + 1)M = 2(d + 1) 2 M weights and biases in total.

E.1.2 Main developments of the proof of Proposition 6

Let N ∈ N * and f ∈ M d . In this section, we partition [0, 1) d into cubes whose sizes depend on the maximal variation of f . Then we use this partition to construct a piecewise constant approximation f of f ; we will bound from above the L p (λ) approximation error f -f L p (λ) by a function of N . This part is a direct reinterpretation of the proof of Proposition 3.1 in [START_REF] Gao | Entropy estimate for high-dimensional monotonic functions[END_REF]. We then apply Proposition 10 to f and obtain the announced result.

We first define some notation that will be used in the rest of the section, then we explain the algorithm used to divide [0, 1) d into cubes. We fix the constant K > 1 the following way:

K := 2 d if p = 1, 2 β otherwise, where β = 1 2 (d -1 + 1 p-1
). We also define an integer l that corresponds to the number of cube decompositions:

l := N log 2 log K = N d if p = 1, N β otherwise . (28)
It is worth noting that this implies

K -l ≤ 2 -N < K -l+1 . Now we partition [0, 1) d into dyadic cubes of the form [a 1 , b 1 ) × • • • × [a d , b d ).
If C is such a cube, we use the following convenient notation:

C := (a 1 , . . . , a d ) ∈ R d , C := (b 1 , . . . , b d ) ∈ R d ,
to refer to the smallest and largest vertices of C. The cube decompositions process reads as follow:

• First we partition [0, 1) d into 2 N d cubes of side-length 2 -N . We denote by S 0 the set of these cubes C such that f (C)f (C) ≤ K2 -N and by R 0 the set of the remaining cubes. • For 1 ≤ i < l, we partition each cube in the set R i-1 (the remaining cubes at the step i -1) into 2 d cubes of equal size, and we denote by S i the set of obtained cubes C of side-length

2 -(i+N ) such that f (C) -f (C) ≤ K i+1 2 -N .
(29) Again, the set of remaining cubes is denoted by R i .

• Lastly, we partition each cube in the set R l-1 into 2 d cubes of equal size, and we denote by S l the set of obtained cubes of side-length 2 -(l+N ) .

Once the algorithm is done, each point in [0, 1) d clearly belongs to one single cube of ∪ l i=0 S i . For i ∈ {0, . . . , l}, we let Si = ∪ C∈Si C.

We now define the piecewise constant approximation of f by

∀x ∈ [0, 1] d , f (x) = C∈ 0≤i≤l Si f (C)1 x∈C ,
where 1 x∈C denotes the indicator function of the cube C. We do not make the dependence explicit, but f depends on the parameters N , d and p. The number of cubes over which f is constant is l i=0 |S i |. This quantity is key when constructing the neural network according to Proposition 10; in the next lemma, we bound from above |S i | for all i = 0, . . . , l. Then, we will estimate the error f -f L p (λ) . Lemma 7. With the above notation:

∀i ∈ {0, . . . , l}, |S i | ≤ dK -i 2 i(d-1)+N d+1
Moreover,

λ( Si ) ≤ 1 if i = 0, 2d(2K) -i , otherwise. (30)
Proof. By construction, we have ∀i ∈ {1, . . . , l},

|S i | + |R i | = 2 d |R i-1 |,
since the set S i ∪ R i contains all the cubes of side-length 2 -(i+N ) , that have been constructed from the cubes of R i-1 . In particular, ∀i ∈ {1, . . . , l},

|S i | ≤ 2 d |R i-1 |. (31)
It remains to bound |R i-1 | from above for i ≥ 1. Define V := {C : C ∈ R i-1 } the set of the smallest vertices of the cubes in R i-1 . We consider the classes of these vertices under the "laying on the same extended diagonal" equivalence relation. Since the cubes have side-length 2 -(i-1+N ) , there are less than d2 (i-1+N )(d-1) equivalence classes. According to the pigeonhole principle, the largest class has at least

|V | d2 (i-1+N )(d-1
) elements; let us refer to this class as D. Let (C j ) 1≤j≤J be the set of cubes in R i-1 having a point in D as lowest vertex. Since f is non-decreasing and according to (29), we have:

1 ≥ f (1, . . . , 1) -f (0, . . . , 0) ≥ J j=1 f (C j ) -f (C j ) ≥ JK i 2 -N ≥ |V | d2 (i-1+N )(d-1) K i 2 -N = |R i-1 | d2 (i-1+N )(d-1) K i 2 -N .
• Suppose that p(d -1) < d. In this case, we can have p = 1 or p > 1. If p = 1, we have

K p-1 2 = 1 2 < 1 and 1 2K < K -p . If p > 1, we have: p(d -1) < d ⇐⇒ dp -p -d + 1 < 1 ⇐⇒ d -1 < 1 p -1 .
Thus, β being the arithmetic mean of d -1 and 1 p-1 , we have d -1 < β < 1 p-1 . Then K = 2 β < 2 1/(p-1) and hence K p-1 2 < 1 and 1 2K < K -p . Therefore, both for p = 1 and p > 1,

l-1 i=1 K p-1 2 i ≤ K p-1 2 -K p-1 and (2K) -l ≤ K -pl . Since K -l ≤ 2 -N , this leads to f -f p L p (λ) ≤ (2 -N K) p + 2 1-N p K p d K p-1 2 -K p-1 + 2dK -pl ≤ K p + 2K p d K p-1 2 -K p-1 + 2d 2 -N p .
We thus have, setting c

1 := K p + 2K p d K p-1 2 -K p-1 + 2d 1 p , f -f L p (λ) ≤ c 1 2 -N .
Notice c 1 only depends on d and p.

• Suppose that p(d-1) > d. We have p > 1 andd

-1 > β > 1 p-1 . Then K = 2 β > 2 1/(p-1) and hence K p-1 2 > 1, which entails using (37) f -f p L p (λ) ≤ (2 -N K) p + 2 1-N p K p d (K p-1 /2) l K p-1 /2 -1 + 2d(2K) -l ≤ 2 -N p K p + 2 -N p K pl 2K p d K p-1 /2 -1 (2K) -l + 2d(2K) -l . Since p > 1 + 1 β , we have 2 -N p ≤ 2 -N (1+ 1 β ) . Also, since K = 2 β , (2K) -l = 2 -l(β+1) , and since l ≥ N log(2) log(K) = N β , we have (2K) -l ≤ 2 -N β (β+1) = 2 -N (1+ 1 β ) . Finally, since 2 -N K l < K, f -f p L p (λ) ≤ K p + K p 2K p d K p-1 /2 -1 + 2d 2 -N (1+1/β)
We thus have, setting c

2 := K p + 2K 2p d K p-1 /2-1 + 2d 1 p , f -f L p (λ) ≤ c 2 2 -N (1+1/β) p .
Notice c 2 only depends on d and p.

• Suppose that p(d -1) = d. It implies p > 1 and p -1 = 1 d-1 , then β = d -1. We thus have K p-1 = 2 (d-1)(p-1) = 2. Therefore, (37) becomes f -f p L p (λ) ≤ 2 -N p K p + 2 -N p 2K p d(l -1) + 2d(K p ) -l .
On the one hand, we have K -l ≤ 2 -N . On the other, we have 2

-N < K -l+1 , so l -1 < N log 2 log K = N d-1 . Putting it all together, we get f -f p L p (λ) ≤ 2 -N p K p + 2 -N p 2K p d(l -1) + 2d2 -N p ≤ K p + 2K p d d -1 + 2d N 2 -N p .
We thus have, setting c 3 :=

K p + 2K p d d-1 + 2d 1 p , f -f L p (λ) ≤ c 3 N 1 p 2 -N .
Notice c 3 only depends on d and p.

Letting c d,p = max{c 1 , c 2 , c 3 } yields the result.

According to Proposition 10, the function f constructed for a given N ∈ N * can be implemented by a Heaviside neural network with two hidden layers and W = 2(d + 1) 2 l i=0 |S i | weights. Using Lemma 7, we obtain

W = 2(d + 1) 2 l i=0 |S i | ≤ 2(d + 1) 2 l i=0 dK -i 2 i(d-1)+N d+1 = 2 N d+2 d(d + 1) 2 l i=0 2 d-1 K i .
We let, for all N ∈ N * ,

W N := 2 N d+2 d(d + 1) 2 l i=0 2 d-1 K i . (38)
Although we do not make the dependence explicit, W N also depends on d and p. Observe that for all d ≥ 1: (W N ) N ∈N * is non-decreasing and lim N →+∞ W N = +∞.

Lemma 9. With the above notation: For any +∞ > p ≥ 1, there exist constants W ′ min , c ′ d,p > 0 depending only on d and p ≥ 1 such that for all N satisfying

W N ≥ W ′ min f -f L p (λ) ≤ c ′ d,p g(W N +1 )
where f is constructed for the parameters N , p and d, and where for all W ≥ 1,

g(W ) =      W -1/d if (d -1)p < d, W -1 p(d-1) if (d -1)p > d, W -1/d log W if (d -1)p = d.
Proof. Again, we distinguish three cases depending on the values of p and d.

• Suppose that p(d-1) < d: if p = 1, 2 d-1 K = 1 2 < 1; if p > 1, since 1 p-1 > d-1, β > d-1 and 2 d-1 K = 2 d-1-β < 1. Thus, in both cases 2 d-1 K < 1 and for all N ≥ 1, W N ≤ 2 N d 4d(d + 1) 2 1 -2 d-1-β =: 2 N d c ′′ d,p .
Writing the inequality for N + 1, we obtain

W N +1 ≤ 2 N d 2 d c ′′ d,p . That is: 2 -N ≤ 2 c ′′ d,p WN+1 1/d
. Combined with (32), this provides

f -f L p (λ) ≤ 2c d,p c ′′ d,p W N +1 1/d = d d,p W -1/d N +1 , for d d,p = 2c d,p (c ′′ d,p ) 1/d and all N ∈ N * . • If p(d -1) > d, then β < d -1 and 2 d-1 K = 2 d-1-β > 1.
Thus, reminding the definition of l in (28), we have for all N ≥ 1

W N ≤ 2 N d 2 (d-1-β)(l+1) 4d(d + 1) 2 2 d-1-β -1 ≤ 2 N d 2 (d-1-β)(N/β+2) 4d(d + 1) 2 2 d-1-β -1 = 2 N (d+(d-1)/β-1) 4d(d + 1) 2 2 2(d-1-β) 2 d-1-β -1 =: 2 N (1+ 1 β )(d-1) c ′′ d,p ,
for a different constant c ′′ d,p . Writing again this inequality for N + 1, we obtain

W N +1 ≤ c ′′ d,p 2 (1+ 1 β )(d-1) 2 N (1+ 1 β )(d-1) , which we can write 2 -N (1+ 1 β ) ≤ 2 (1+ 1 β ) c ′′ d,p WN+1 1 d-1 . This provides 2 -N (1+1/β) p ≤ 2 (1+1/β) p c ′′ d,p W N +1 1 p(d-1)
. Therefore, using (32), we obtain

f -f L p (λ) ≤ c d,p 2 (1+1/β) p c ′′ d,p W N +1 1 p(d-1) = d ′ d,p W -1 p(d-1) N +1 , for d ′ d,p = c d,p 2 (1+1/β) p (c ′′ d,p ) 1 p(d-1) and all N ∈ N * . • If p(d -1) = d, then β = d -1 and 2 d-1 K = 1.
Thus, reminding the definition of l in (28), we have for all N ≥ 1

W N = 2 N d+2 d(d + 1) 2 (l + 1) ≤ 2 N d+2 d(d + 1) 2 N β + 2 = 2 N d N β + 2 4d(d + 1) 2 =: 2 N d N d -1 + 2 c ′′ d,p ≤ 2 d(d-1)( N d-1 +2) N d -1 + 2 c ′′ d,p = exp d(d -1) N d -1 + 2 log 2 N d -1 + 2 c ′′ d,p (39)
where c ′′ d,p = 4d(d + 1) 2 . Setting

WN := d(d -1)W N log 2 c ′′ d,p and
Ñ := d(d -1) N d -1 + 2 log 2,
we can rewrite (39) as:

WN ≤ Ñ exp( Ñ ) . (40) Since d ≥ 2, c ′′ d,p > 0, (W N ) N ∈N * is non-decreasing and lim N →+∞ W N = +∞, there exists W ′ min such that, for all N satisfying W N ≥ W ′ min , we have the following:            log( WN ) > 1 log( WN+1 ) > 2 log(2) d(d -1) log( WN+1) d log(2) -log log( WN+1) d log(2) -2(d -1) > 1 p log(2) log W N +1 ≥ log d(d-1) log 2 c ′′ d,p . (41)
These inequalities will be used latter in the proof and, from now on, we always consider N such that W N ≥ W ′ min . Let us first show by contradiction that, for all N satisfying W N ≥ W ′ min , (40) implies that Ñ ≥ log WNlog log WN .

Using (32), we obtain:

f -f L p (λ) ≤ c d,p N 1 p 2 -N ≤ 2c d,p (N + 1) 1 p 2 -(N +1) .
Since, for t > 1 p log(2) , the function t -→ t 1 p 2 -t is non-increasing, using (43) and ( 41) and the fact thatlog log WN+1 and so does the supremum over f in M d .

This concludes the proof of Proposition 6.

E.2 Proof of Proposition 4

Step 1: we prove the result in dimension d = 2. We consider the closed disk of radius 1, centered at (1, 1),

C = x ∈ R 2 : 2 i=1 (x i -1) 2 ≤ 1 .
The intersection between (0, 1) 2 and the topological boundary ∂C of C is the quarter of circle:

∂C ∩ (0, 1) 2 = x ∈ (0, 1) 2 :

2 i=1 (x i -1) 2 = 1 .
We denote by f : [0, 1] 2 → {0, 1} the indicator function of the set C ∩ [0, 1] 2 . The set C ∩ [0, 1] 2 , the set ∂C ∩ (0, 1) 2 and the function f are represented on Figure 3.

Since no point in C c ∩ [0, 1] 2 has all its coordinates strictly larger than those of a point in C, we have f ∈ M 2 (monotonic functions of 2 variables). We consider an arbitrary neural network architecture A and g ∈ H A .

Let W ≥ 1 be the number of weights in the architecture A. As is well known for Heaviside neural networks, there exist K ∈ N with K ≤ 2 W , reals α j and polygons A j ⊂ [0, 1] 2 , for j ∈ {1, . . . , K}, such that for all x ∈ [0, 1] 2 g(x) = K j=1 α j 1 Aj (x). |f (x 1 , x 2 , 1 . . . , 1)g(x 1 , x 2 , 1 . . . , 1)|

≥ 1 2 ,
where the last inequality is by the result of Step 1, since (x 1 , x 2 ) ∈ [0, 1] 2 → f (x 1 , x 2 , 1 . . . , 1) is the indicator function of Step 1, and (x 1 , x 2 ) ∈ [0, 1] 2 → g(x 1 , x 2 , 1 . . . , 1) can be represented by a Heaviside neural network with 2 input neurons. This concludes the proof.

Remark. Note from the above proof that, though we only stated the impossibility result for piecewise-constant activation functions, an analogue statement in fact holds more generally for piecewise-affine activation functions.

F Barron space

In Section 5 we mentioned that the Barron space introduced in [Bar93] is one among several examples for which approximation theory provides ready-to-use lower bounds on the packing number. This space has received renewed attention recently in the deep learning community, in particular because its "size" is sufficiently small to avoid approximation rates depending exponentially on the input dimension d. Next we detail how to apply Corollary 1 in this case.

Definition of the Barron space. We start by introducing the Barron space, as defined in

inf g∈HA f -g L p (λ) ≥      c 1 W -1-2 d log -1-2 d (W ) if ν ≥ 2 , c 2 (LW ) -1 2 -1 d log -3 2 -3 d (W ) if ν = 1 , c 3 W -1 2 -1 d log -3 2 -3 d (W ) if ν = 0 . (45)

  [a, b] to [0, 1] by translating and rescaling every function in G. For g ∈ G, we define g : X → [0, 1] by g(x) = g(x)-a b-a , and we set G = {g : g ∈ G} .

  [a,b] the set of all functions in G whose values are truncated (clipped) to the segment [a, b], that is, G [a,b] = {g : g ∈ G}, where g : X → R is given by ∀x ∈ X , g(x) = min(max(a, g(x)), b) . Lemma 3. Let G be a set of functions defined on a set X , and with values in R. Let G [a,b] be defined as above. Then, for any γ > 0, fat γ (G) ≥ fat γ (G [a,b] ) . Proof. Let γ > 0. The case when fat γ (G [a,b] ) = 0 is straightforward. We thus assume that fat γ (G [a,b] ) ≥ 1. To prove the result, we show that any subset A of X that is γ-shattered by G [a,b]

Figure 1 :

 1 Figure 1: Values of the sum of the perceptrons p i j (x) around a hypercube C i in dimension 2.

Figure 2 :

 2 Figure 2: The function f represented as a neural network.

  the latter does not hold Ñ < log WNlog log WN , exp( Ñ ) < WN log WN , and therefore, multiplying the two inequalities, since (41) implies that WN > 0, log WN > 0 and log(log( WN )) > 0, Ñ exp( Ñ ) < WN .The latter being in contradiction with (40), we have proved that, for all N satisfying W N ≥ W ′ min , (42) holds. Using the definition of Ñ , we deduceN ≥ log WNlog log WN d(d -1) log(2) -2 (dfor the constant c = -2(d -1) < 0. Since (W N ) N ∈N is non-decreasing, for all N satisfying W N ≥ W ′ min , W N +1 ≥ W ′min and the inequality also holds for N + 1. That is N + 1 ≥ log( WN+1 ) d log(2) -log log WN+1 d log(2) + c.

d 1 dN 1 dNFigure 3 :

 113 Figure 3: The set C, the set ∂C ∩ (0, 1) 2 and the indicator function f .

  [START_REF] Petersen | Optimal learning of high-dimensional classification problems using deep neural networks[END_REF]. Let d ∈ N * . For any constant C > 0, the Barron space B d (C) is the set of all functions f : [0, 1] d → [0, 1] for which there exist a measurable functionF : R d → C and some c ∈ [-C, C] such that, for all x ∈ [0, 1] d , f (x) = c + R d (e ix•ξ -1)F (ξ)dξ and R d ξ 2 |F (ξ)|dξ ≤ C,where x • ξ denotes the standard scalar product in between x and ξ.Known lower bound on the packing number. Petersen and Voigtlaender[START_REF] Petersen | Optimal learning of high-dimensional classification problems using deep neural networks[END_REF] showed a tight lower bound on the log packing number in L p (λ, [0, 1] d ) norm, which we recall below.Proposition 11 (Proposition 4.6 in[START_REF] Petersen | Optimal learning of high-dimensional classification problems using deep neural networks[END_REF]). Let 1 ≤ p ≤ +∞. There exist constants ε 0 , c 0 > 0 depending only on d and C such that for any ε ≤ ε 0 ,log M (ε, B d (C), • L p ) ≥ c 0 ε -1/( 1 2 + 1 d ) .(44)Consequence on the approximation rate by piecewise-polynomial neural networks. Plugging the lower bound of Proposition 11 in Corollary 1, we obtain the following lower bound on the approximation error of the Barron space by piecewise-polynomial neural networks. Proposition 12. Let 1 ≤ p < +∞, d ≥ 1. Let σ : R → R be a piecewise-polynomial function on K ≥ 2 pieces, with maximal degree ν ∈ N. Consider the Barron space B d (C) defined above, with C > 0. There exist positive constants c 1 , c 2 , c 3 , W min depending only on d, p, C, K and ν such that, for any architecture A of depth L ≥ 1 with W ≥ W min weights, and for the activation σ, the set H A (cf. Section 1) satisfies sup f ∈B d (C)

  n,d that can shatter a grid of N d points x 1 , . . . , x N d evenly distributed over [0, 1] d . The assumption that H A approximates F n,d in sup norm with error ε allows to conclude that H A also shatters {x 1 , . . . , x N d }, and hence, VCdim(H A ) ≥ N d = c ′ n,d ε -d n , for a properly chosen constant c ′ n,d > 0. The author concludes using the upper bound on VCdim(H A ) with respect to W from [AB99] which yields VCdim(H A

The author assumes that H A approximates F n,d with error ε. Fixing N = c n,d (3ε) -1/n for a properly chosen constant c n,d > 0, he constructs a set of functions in F

  Consider an arbitrary neural network architecture A and g ∈ H A . That is, g can be represented by a Heaviside neural network with d input neurons. Note thatsup x1,x2,x3...,x d ∈[0,1] |f (x 1 , x 2 , x 3 . . . , x d )g(x 1 , x 2 , x 3 . . . , x d )|

	≥ sup
	x1,x2∈[0,1]

By definition, note that γ → fatγ (F ) is non-increasing and that fatγ (F ) ≤ Pdim(F ) for all γ > 0.

Note that any ε ≥ (b -a)/3 is a solution to this inequation, since log M

3ε, F, • L p (µ) = log(1) = 0 (because all functions in F are [a, b]-valued) and c fat ε 32 (G) ≥ 0. Therefore, the right-hand side of (2) is at most (b -a)/3.

Obtaining an upper-bound for ReLU networks seems challenging. For example, the bit extraction technique used in[START_REF] Yarotsky | Optimal approximation of continuous functions by very deep relu networks[END_REF] to find a sharp upper bound heavily relies on the local smoothness assumption of the function to approximate, which is not satisfied in general for monotonic functions.

A node u ∈ V is a predecessor of another node v ∈ V if there is a directed edge from u to v.

In passing, all occurrences of fat ε 32 (G) could be replaced with fat ε 8 (G).

This is because Pdim(HA) = VCdim {(x, r) ∈ R d ×R → 1 {g(x)-r>0} : g ∈ HA} , the output neuron of A is linear, and we allow skip connections.

is larger or smaller than 1.

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 AI Interdisciplinary Institute ANITI, which is funded by the French "Investing for the Future -PIA3" program under the Grant agreement ANR-19-P3IA-0004. The authors gratefully acknowledge the support of IRT Saint Exupéry and the DEEL project. 4

The first statement of Lemma 7 follows from (31).

For i = 0, λ( S0 ) ≤ 1. For 1 ≤ i ≤ l, using the first statement of this lemma, we bound from above the measure of Si :

To show that f is close to f in L p (λ) norm, let us use the fact that ( Si ) 0≤i≤l is a partition of [0, 1) d and decompose the error in three parts:

In the next lemma, we control each term of the above sum to bound from above f -f L p (λ) by a function of N that is independent of f and tends to 0 when N tends to +∞.

Lemma 8. For any 1 ≤ p < +∞, there exists a constant c d,p > 0 depending only on d and p such that for all

where f is the function constructed for the parameters N , d and p.

Proof. For 0 ≤ i < l, on any cube C ∈ S i , we have

since f is non-decreasing, and by definition of f and S i .

• Using the fact that λ( S0 ) ≤ 1 and by (33):

• Using (30) and (33), we get for all i ∈ {1, . . . , l -

• On any C ∈ S l , we have, for all

, and we get, using (30):

Combining (34), ( 35) and (36) we get:

It remains to bound the right-hand side of (37), depending on the value of p and d. Note that the behavior of this term depends on whether K p-1

Moreover, (A j ) 1≤j≤K form a partition of [0, 1] 2 .

The proof relies on the fact (proved afterwards) that, if fg ∞ < 1 2 then ∂C ∩ (0, 1) 2 is finite. The latter being false, we conclude that fg ∞ ≥ 1 2 . Assume from now on that fg ∞ < 1 2 . This implies that g > 1 2 on C, and g < 1 2 elsewhere. Let us first show that we then have

Indeed, if the latter were not true, then there would exist x ∈ ∂C ∩ (0, 1) 2 and j ∈ {1, . . . , K} such that x ∈ Åj . Since C is closed, x ∈ C. Let ǫ > 0 be such that B(x, ǫ) ⊂ Åj . We have B(x, ǫ) ⊂ C (otherwise, x belongs to the interior of C which contradicts x ∈ ∂C). Thus there exists z ∈ B(x, ǫ) \ C. Since g > 1 2 on C, and g < 1 2 elsewhere, we have

This is not possible since x, z ∈ Åj and g is constant on A j . This concludes the proof of the following fact: if fg ∞ < 1 2 then ∂C ∩ (0, 1) 2 ⊂ 1≤j≤K ∂A j . Since the A j are polygons (recall that we work in dimension 2), their boundaries are finite unions of closed line segments. Then ∂C ∩ (0, 1) 2 is included in a finite union of closed line segments which we denote S m , for m ∈ {1, . . . , M }. The reader may already see that this is in contradiction with the fact that ∂C ∩ (0, 1) 2 is a quarter circle. To detail this argument and complete the announced proof, we show that ∂C ∩ (0, 1) 2 ⊂ M m=1 S m implies that ∂C ∩ (0, 1) 2 is finite. To do so, since when ∂C ∩ (0, 1) 2 ⊂ M m=1 S m we have

∂C ∩ (0, 1) 2 ∩ S m = ∂C ∩ (0, 1) 2 , it suffices to prove that the intersection of any closed line segment S with ∂C ∩ (0, 1) 2 contains at most 2 points.

Denote by S a closed line segment: C and S are convex and hence connected, thus C ∩ S is either empty, a singleton or a line segment, as a connected compact subset of S. If it is empty, then a fortiori, ∂C ∩ (0, 1) 2 ∩ S = ∅. If it is not, denote by y and z its extremities (assuming z = y in the case of a singleton). By strict convexity of the function x →

In any case, we have |∂C ∩ (0, 1) 2 ∩ S| ≤ 2.

This concludes the proof of the fact: if fg ∞ < 1 2 then ∂C ∩ (0, 1) 2 is finite and concludes the proof in the case d = 2.

Step 2: we prove the result in any dimension d ≥ 2, by a reduction to dimension 2. We define