Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?
Authors: Kaiqi Zhang
Yu-Xiang Wang
Venue: ICLR 2023 poster (2023)
Keywords: Neural network
nonparametric regression
minimax optimal

Abstract: We study the theory of neural network (NN) from the lens of classical nonparametric regression problems with a focus on NN’s ability to adaptively estimate functions with heterogeneous smoothness — a property of functions in Besov or Bounded Variation (BV) classes. Existing work on this problem requires tuning the NN architecture based on the function spaces and sample sizes. We consider a “Parallel NN” variant of deep ReLU networks and show that the standard weight decay is equivalent to promoting the ℓp -sparsity (0 < p < 1) of the coefficient vector of an end-to-end learned function bases, i.e., a dictionary. Using this equivalence, we further establish that by tuning only the weight decay, such Parallel NN achieves an estimation error arbitrarily close to the minimax rates for both the Besov and BV classes. Notably, it gets exponentially closer to minimax optimal as the NN gets deeper. Our research sheds new lights on why depth matters and how NNs are more powerful than kernel methods

Published as a conference paper at ICLR 2023
DEEP LEARNING MEETS NONPARAMETRIC REGRES- SION: ARE WEIGHT DECAYED DNNS LOCALLY ADAPTIVE?
Kaiqi Zhang
Yu-Xiang Wang
Department of Electrical and Computer Engineering University of California, Santa Barbara kchang70@ ucsb.edu
Department of Computer Science University California, Santa Barbara yuxiangw @ cs. cs.ucsb.edu
ABSTRACT
We study the theory of neural network (NN) from the lens of classical nonpara- metric regression problems with focus on NN's ability to adaptively estimate functions with heterogeneous smoothness Bounded Variation (BV) classes. Existing work on this problem requires tuning the NN architecture based on the function spaces and sample size. We consider a "Parallel NN" variant of deep ReI.U networks and show that the standard l regularization is equivalent promoting the fp-sparsity (0 p < 1) in the efficient vector of an end-to-end learned function bases, i.c., a dictionary. Using this equivalence, tor, such parallel NN achieves an estimation error arbitrarily close to the minimax rates for both the Besov and BV classes. Notably, it gets exponentially closer minimax optimal as the NN gets deeper. Our research sheds new lights on why depth matters and how NNs are more powerful than kernel methods.
property of functions in Besov or
further establish that by tuning only the regularization fac-
INTRODUCTION
Why do deep neural networks (DNNs) work better? They universal function approximators (Cy- benko, 1989), but so are splines and kernels. They learn data-driven representations, but so are the shallower and linear counterparts such matrix factorization. The theoretical understanding on why DNNs are superior to these classical alternatives is surprisingly limited.
In this paper, we study DNNs in nonparametric regression problems tical theory and methods with more than half a century of associated literatures (Nadaraya, 1964; De Boor al., 1978; Wahba, 1990; Donoho et al., 1998; Mallat, 1999; Scholkopf & Smola, 2001; Rasmussen & Williams, 2006). Nonparametric regression addresses the fundamental problem:
classical branch of statis-
Let 3ı fxx Noise for 1,..., n. How we estimate a function using data points (11, (In, yn) in conjunction with the knowledge that belongs to function class F?
Function class FF typically imposes only weak regularity assumptions such as smoothness, which makes nonparametric regression widely applicable to real-life applications under weak assumptions.
Local adaptivity. We say nonparametric regression technique is locally adaptive if it can cater to local differences in smoothness, hence allowing more accurate estimation of functions with vary- ing smoothness and abrupt changes. A subset of nonparametric regression techniques were shown to have the property of local adaptivity (Mammen & van de Geer, 1997) in both theory and prac- tice. These include wavelet smoothing (Donoho et al., 1998), locally adaptive regression splines (LARS, Mammen & van de Geer, 1997), trend filtering (Tibshirani, 2014; Wang et al., 2014) and adaptive local polynomials (Baby & Wang, 2019; 2020). light of such a distinction, is natural to consider the following question: Are NNs locally adaptive, i.e., optimal in learning functions with heterogeneous smoothness?
This is timely question to ask, partly because the bulk of recent theory of NN leverages its asymp- totic Reproducing Kernel Hilbert Space (RKHS) in the overparameterized regime (Jacot et al., 2018; Belkin et al., 2018: Arora al., 2019). RKHS-based approaches, e.g., kernel ridge regression with

---

Published as a conference paper at ICLR 2023
Table 1: Comparison with the results in the literature
# layers
Activation
Function
Minimax rate
Remark
space
Parhi & Nowak (2021a;c)
truncated
BV"
Yes
Non-standard activation and regularization (when m > 1), With sparsity constraint.
power ReLU
Schmidt- Hieber
23 3
Hölder
Up to a log
(2020)
factor
Suzuki (2018)
IV W
3
ReLU
Besov & m-
Up to a log
With sparsity constraint.
Besov
factor
Ours
3
ReI.U
Besov & BV
Up to mo(1) factor
Requires only & regulariza- tion.
any fixed kernels are suboptimal in estimating functions with heterogeneous smoothness (Donoho et al., 1990). Therefore, existing deep learning theory based on RKHS does not satisfactorily explain the advantages of neural networks over kernel methods.
We build upon the recent work of Suzuki (2018) 8) and Parhi & Nowak (2021a) who provided encouraging first answers to the question above. Specifically, Parhi & Nowak (2021a, Theorem 8) showed that a
Flylat [r] = f(x)
Yaaa
M
two-layer truncated power function activated neural network with a non-standard regularization is equiv- alent the LARS. This connection implies that such NNs achieve the minimax rate for the (high order) bounded variation (BV) classes. A detailed discus- sion is provided in Section B. Suzuki (2018) showed that multilayer ReLU DNNS can achieve minimax rate for the Besov class, but requires the artificially imposed sparsity-level of the DNN weights to be calibrated according to parameters of the Besov class, thus is quite difficult to implement in practice. (Oono & Suzuki, 2019; Liu et al., 2021) replaced the sparse neural network with Resnet-style CNN and achieved the same rate, but they sim- ilarly require carefully choosing the number of parameters for each nonparametric class. We show that & regularization suffices for mildly overparaneterized DNNs to achieve the optimal "local adaptive" rates for many nonparametric classes at the same time.
Despber Nhd fanchions
Free knott Spinns with wnhhadpptveerdee
Can Weight Decayed ReLU DNN octimate suctifunctionss with heterogenesuu smoothness optiaaty (using mony observatioss?
Figure 1: Illustration of function with het- erogeneous smoothness and the problem of locally adaptive nonparametric regression.
Parallel neural networks. We restrict our attention on a special network architecture called par- allel neural network (Haeffele & Vidal, 2017; Ergen & Pilanci, 2021c) which learns ensemble of subnetworks - each being multilayer ReLU DNNs. Parallel NNs have been shown to be more well-behaved both theoretically (Haeffele & Vidal, 2017: Zhang et al., 2019; Ergen & Pi- lanci, 202 2021b;e;d) and empirically (Zagoruyko & Komodakis, 2016; Veit et al., 2016). On the other hand, many successful NN architectures such as SqueezeNet, ResNext and Inception (see (Ergen & Pilanci, 2021c) and the references therein) use the idea similar to parallel NN.
Weight decay, also known as square & regularization, is one of the most popular regularization techniques for preventing overfitting in DNNs. It is called "weight decay" because each iteration of the gradient descent (or SGD) shrinks the parameter towards 0 multiplicatively. Many tricks in deep learning, including early stopping (Yao et al., 2007), quantization (Hubara et al., 2016), and dropout (Wager et al., 2013) behaves like le regularization. Thus even though we focus on the exact minimizer of the regularized objective, it may explain the behavior of SGD in practice.
Summary of results. Our main contributions are:
1. We prove that the (standard) l2 regularization in training an L-layer parallel ReLU- activated neural network equivalent sparse lp penalty term (where p 2/L) on the linear coefficients of a learned representation (Proposition 4).
2. We show that the estimation error of & regularized parallel NN can be close to the minimax rate for estimating functions in Besov space. Notably, the method can adapt to different smoothness parameter, which is not the case for many other methods.
3. We find that deeper models achieve closer to the optimal error rate. This result helps explain why deep neural networks can achieve better performance than shallow ones empirically.
Besides, we have the following technical contributions which could be of separate interest:
2

---

Published as a conference paper at ICLR 2023
We provide way bound the complexity of overparameterized neural network. Specif- ically, we bound the metric entropy of a parallel neural network in Theorem 5, and the bound does not depend on the number of subnetworks.
We propose a method handle unconstrained function subspace when bounding the esti- mation error as in Equation (4).
The above results separate parallel NNs with any linear methods such as kernel ridge regression. To the best of our knowledge, we are the first to demonstrate that standard techniques (&2 regularization and ReLU activation) suffice for DNNs in achieving the optimal rates for estimating BV and Besov functions. The comparison with previous works is shown in Table More discussion about related works are shown in Section A.
PRELIMINARY
2.1 NOTATION AND PROBLEM SETUP.
We denote regular font letters as scalars, bold lower case letters vectors and bold upper case letters as matrices. a S means a S Ch for some constant that does not depend on or b, and = denotes a S b and S See Table 2 for the full list of symbols used.
Let fo be the target function to be estimated. The training dataset is Dn == ((x:, 3i), y: fo( + e,, i [n]]. where x, are fixed and E; are zero-mean, independent Gaussian noises with variance o². In the following discussion, we assume I, E [0, fo E [-1, Vi.
We will be comparing estimators under the mean square error (MSE), defined as MSE()) ED, (f=r((())) fo( The optimal worst-case MSE is described by R(F)
ming max MSE(f). We say that f is optimal if MSE(f) S R(F). The empirical (square er- ror) loss is defined as L(f) := +/b Ei=r((())) - y. The corresponding population loss L(f) = B (f y/)² [f] where s/ are new data points. It is clear that B[L(f)] MSE o².
2.2 BESOV SPACES AND BOUND VARIATION SPACE
Besov space, denoted Bo p... is flexible function class parameterized by P; whose definition is deferred to Section C.1. Here a 2 O determines the smoothness of functions, < S oo determines the averaging (quasi-)norm over locations, 1 1 S oo determines the averaging (quasi- mnorm over scale which plays a relatively minor role. Smaller p is more forgiving to inhomogeneity and loosely speaking, when the function domain is bounded, smaller p induces larger function space. On the other hand, it is easy to see from definition that B C Ba if < d' Without loss of generalizability, the following discussion we will only focus on B When p 1, the Besov space allows higher inhomogeneity, and it is more general than the Sobolev or Hölder space.
Bounded variation (BV) space more interpretable class of functions with spatially heteroge- neous smoothness (Donoho et al., 1998). It is defined through the total variation (TV) of function.
Table 2: Symbols used in this paper
symbol a/ la/ A Bog
Meaning
scalars vectors matrices. Besov space.
aa, b)
[ x
[n]
{I [
< n).
| Ing.
Besov quasi-norm.
-
-||
Frobenius norm.
|| B
Besov norm.
ly-norm.
Mm
th order Cardinal B-spline bases. mh order Cardinal B-spline basis function of resolution À at position s.
d
Dimension of input.
M (m.k.o(-)
M
# subnetworks in parallel NN.
L
layers in (parallel) NN.
Width of a subnetwork. samples.
W
o(-)
ReLU activation function.
n
(1) 6/2
Weight and bias in the f-th layer in the j-th subnetwork.
IR, 2, NN
Set of real numbers, integers, and nonnegative integers.

---

Published as a conference paper at ICLR 2023
W
w
W
(c) Block diagonal weights
O
W
M
@1
BM
(
W
W
L
W
W
W
000
O0O
000
W
W
W
WiL
Mr
M
000
000
000
W
w
(
W
W
? A
M
Q0Q
W
(
a
miny, LE, ()) + Σ/ IB.
min (ag.1)) LC, a, ΣM |ay12/4. 2/4
(a) Parallel NN with &a regularization
(b) Sparse Regression with Learned Representation
Figure 2: Parallel neural network and the equivalent sparse regression model we discovered.
For (m + 1)th differentiable function f [0 + I, the mith order total variation is defined as TV(m) (f) = (m((m+))) S1.11 (f(m+)) (x) dxx and the corresponding mth order Bounded Variation class (m) == {f (f(())) < 0o). The more general definition is given in Sec- tion C.2. Bounded variation class is tightly connected to Besov classes. Specifically (De & Lorentz, 1993):
BTT C (V)) C B
This allows the results derived for the Besov space to be easily applied to BV space.
Minimax MSE It is well known that minimax rate for Besov and ID BV classes are O 2674) and (n (2m (2mm+) respectively. The minimax rate for linear estimators in ID BV classes is (2m++ (1)m+))//(2))) (2m(+)))) (Mammen & van de Geer, 1997; Donoho et al., 1998).
known to be OOn-(2mm
MAIN RESULTS: PARALLEL RELU DNNS
Consider parallel neural network containing M multi layer perceptrons (MLP) with ReLU activa- tion functions called subnetworks. Each subnetwork has width w and depth L. The input is fed to all the subnetworks, and the output of the parallel NN is the summation of the output of each sub- network. The architecture of a parallel neural network shown in Figure 2a. This parallel neural network is equivalent to vanilla neural network with block diagonal weights in all but the first and the last layers (Figure 2(c)). Let w and 6/² denote the weight and bias the l-th layer in the j-th subnetwork respectively. Training this model with & regularization returns:
M arg min L(f) (w))) .(0))
11
t=1
where f(x) Eje fa( denotes the parallel neural network, fz(-) denotes the j-th subnetwork,
and À 0 is a fixed scaling factor. We choose not to regularize the bias terms (((0) to provide cleaner equivalent model (Proposition 4). If the bias terms are regularized, the result will be similar. Besides. we ignore the computation issue and focus on the global optimal solution to this problem. In practice, in deep neural network. the solution obtained using gradient descent-style methods are often close the global optimal solution (Choromanska et al., 2015).
Theorem 1. For any fixed a d/p > 1, 2 1, 3, define m la- 17. For any fo B given an L-layer parallel neural network satisfying
The width of each subnetwork is fixed satisfying w 2 ((md). See Theorem 8 for the detail.
4

---

Published as a conference paper at ICLR 2023
The number of subnetworks is large enough: M 2 n (,377041-2711)) 27(p))
Under the assumption as in Lemma 17, with proper choice of the parameter of regularizaton that depends on D, Ox d, L, the solution f parameterized by (2) satisfies
MSE(f)- C(w, L)O(n 20/d-1 27(02) te-cub
20/d0122411
where Ô shows the scale up a logarithmic factor, cs > i numerical constant Theorem 8, (ww, L.) (wa-4// (ud--//13--ALyyaaaa------- 20/841-2/0z) depends polynomially on T..
2u/d
We explain the proof idea in the next section, but defer the extended form of the theorem and the full proof Section F. Before that, we comment on few interesting aspects of the result.
Near optimal rates and the effect of depth. The first term in the MSE bound is the estimation error and the second term is (part of) the approximation error of this NN. Recall that the minimax rate of a Besov class O(n 3o+4d
). The gap between the estimation error and the minimax rate is because the minimax rate be achieved by lo sparse model, while the parallel NN is equivalent to lp sparse model (will be shown in Proposition 4), which is an approximation to lg. As the depth parameter increases, p 2/ gets closer O, the MSE can get arbitrarily close to the minimax rate and the trailing constant term in (3) can be arbitrarily small. Close to the optimal rate can be achieved if we choose L Z logn: n:
Corollary 2. Under the conditions of Theorem 1, for any fo E Bg.. there is numerical constant C' such that when we choose C Colog n. S L S 100C log n,
MSE(F) = Ö(n where Ô hides only logarithmic and the factor the exponent is O(1/ log(n)).
2n 2 (1-o(1))).
Sparsity and comparison with standard NN. We also note that the result does not depend on M as long as M is large enough. This means that the neural network can be arbitrarily overparameterizee while not overfitting. The underlying reason is sparsity. As it will become clearer in Section 4.1, l2 regularized training of a parallel I-layer ReL.U NNs is equivalent to a sparse regression problem with b penalty assigned the coefficient vector of learned dictionary. Here p 2/T. which promotes even sparser solutions than an L penalty. Such Ep sparsity does not exist in standard deep neural networks to the best of our knowledge, which indicates that parallel neural networks may be superior over standard neural networks in local adaptivity.
Adaptivity function spaces. For any fixed L, m, our result shows the parallel neural network with width w ((md) can achieve close to the minimax rate for any Besov class as long as S m. In other words, neural networks can adapt to smoothness parameter by tuning only the regularizaton parameter. As will be shown in Theorem 5, overestimating a with m only changes the logarithmic terms in the MSE bound - a mild price to pay for more adaptive method.
Hyperparameter tuning. We provide explicit choice of X in Lemma 17 underlying our theoret- ical result. Empirically, can be determined empirically, e.g. using cross validation.
Fixed design v.s. random design. We mainly focus on bounding the error at sample covariates (the fixed design problem) to be comparable classical nonparameteric regression results. For complete- ness, we also state results for the random design version of the problem (bounding EpE,,ME(() in Theorem 19, to be compatible with the standard statistical learning setting (e.g., Suzuki, 2018).
More discussion about this result can be found Section G.
Bounded variation classes. Thanks to the Besov space embedding of the BV class (1), our theorem also implies the result for the BV class in 1D.
bounded variation class fo E BV (m). For any fixed 2 3, for a neural network satisfying the requirements in Theorem I with d = 1 and with proper choice of the regularization factor X, the NN f parameterized by (6) satisfies
Corollary 3. If the target function
MSE(f) = C(w, L)O(n
(2m=2)(1 (2/11
O(E
where C(w, T.) is the same as in (3) except replacing with m.
5

---

Published as a conference paper at ICLR 2023
It is known that any linear estimators such kernel smoothing and smoothing splines cannot have an enror lower than 0(n=(2m++1)/(mm42) for (V(m) (Donoho et al., 1998). When T. > O(m²), the first term the MSE of NN decreases with n. faster than that of the linear methods. When n large enough, there exists L such that the MSE of NN is strictly smaller than that of any linear method. This partly explains the advantage of DNNs over kernels.
PROOF OVERVIEW
We start by first proving that parallel neural network trained with & regularization is equivalent to an l ep-spase regression problem with representation learning (Section 4.1); which helps decompose its MSE into an estimation error and approxmation error. Then we bound the two terms under an l Sparse constrained problem setting in Section 4.2 and Section 4.3 respectively.
Notably, we adapted the generic statistical learning machinery (a boundinu argument) for study- ing this constrained ERM problem (Suzuki, 2018, Proposition 4) to bound the estimation error. This adaption is non-trival because there is an unconstrained subspace with no bounded metric entropy. Specifically, Proposition 15 shows that the MSE of the regression problem can be bounded by
(F 5, [|l)) d(Fi)
MSE(F) =0 inf MSE(F) FEF
72
(4)
apgroximation enTLE
estimation error
in which F decomposes into Fi xFF,, where FL is unconstrained subspace with finite dimension, and Fi is a compact set in the orthogonal complement with d-covering number of (Fii,, 6, I|- Ilol) in -llo--oom norm. This decomposes MSE into an approximation error and an estimation error. The novel analysis of these represents the major technical contribution of this paper.
4.1 EQUIVALENCE TO SPARSE REGRESSION
It is widely known that ReLU function is I-homogeneous: o(rr) ao Va > 0, E R. In any consecutive two layers neural network (or subnetwork), one can multiply the weight and bias in one layer with positive constant, and divide the weight in another layer with the same constant. The neural network after such transformation is equivalent to the original one:
or (2) w (C cb Vc 0,
(5)
This property be applied each subnetwork (instead of the entire model in standard NN), problem:
and we can reformulate (2) to an Ep
Proposition There exists an one-to-one mapping between > and X > such that (2) is equivalent to the following problem:
arg min
i (
([aJ))) *1HHa,
(w)) 5 .a)) 8.1. IW Ir Sava [M]: W S EM
where (5(-) is subnetwork with parameters (0 66
This equivalent model is demonstrated in Figure 2b. The proof, which we defer to Section D.I, uses AM-GM inequality and the observation that the optimal solution will have norm-equalized weights
layer. The constraint | I|r & vd, / [| S Vw. AÊ > is typical in deep learning for better numerical stability. The equivalent model in Proposition 4 is also a parallel neural network, but it appends one layer with parameters {ax} } at the end of the neural network, and the constraint on the Frobenius norm is converted to the 2/L norm on the factors {ax}- Since L > 2 in a typical application, 2/L < 1 and this regularizer same technique can also be used to prove that an lg constrained neural network is equivalent to the le/L constrained model as in (7).
enforce sparser model than that in Section B. The

---

Published as a conference paper at ICLR 2023
There are two useful implications of Proposition 4. First, it gives intuitive explanation how a regularized Parallel NN works. Specifically, it can be viewed as a sparse linear regression with representation learning. Secondly, the conversion into the constrained form allows to decompose the MSE into two terms as in (4) and bound them separately.
We emphasize that Proposition by itself is not new. The same result was previously obtained by Savarese et al. (2019, Appendix C) (see Section for more details) and the key proof techniques date back to least Burer & Monteiro (2003). Our novel contribution is leverage this folklore equivalence for proving new learning bounds.
4.2 ESTIMATION ERROR ANALYSIS
Previous results that bound the covering number of neural networks (Yarotsky, 2017; Suzuki, 2018) depends the width of the neural networks explicitly, which cannot be applied when analysing a potentially infinitely wide neural network. In this section, we leverage the fn-nrmm bounded coefficients to avoid the dependence in M in the covering number bound, and focus on a constrained optimization problem:
arg min (W 5
i (( j=1
a.).
s.t.lHa, H2// P.
and (W() ((0)) satisfy the same constraint as in (6). The connection between the regularized problem and the constrained problem defered to Lemma 17.
Theorem 5. The covering number of the model defined in (7) apart from the bias in the last layer
satisfies
log.N(F.0) w -/d 1- log(wP'/8)
This theorem provides bound of estimation error for arbitrarily wide parallel neural network as long as the total Frobenius norm is bounded. The proof can be found in Section D.2. requires the following lemma, whose proof is deferred Section D.3:
Lemma 6. Let g S [RR + [-c3, ca]} b be set with covering number satisfying log logN((,0) S k (log(1/8) for some finite Cz, and for any g E 9, |a| S 1, we have ag G. The covering number of p for any satisfies
F DM aggi E G, [|alE
log c) S kP (6/cs) - F-r log(csP/8)
up double logarithmic factor.
4.3 APPROXIMATION ERROR ANALYSIS
The approximation error analysis involves two steps. We first analyse how a subnetwork can ap- proximate B-spline basis, which is defered to Section E. Then we show that a sparse linear combination of B-spline bases approximates Besov functions. Both add up to the total error in approximating Besov functions with a parallel neural network (Theorem 8).
Proposition 7. Let
d/p > 1,r > O. For any function in Besov space fo E By. and any positive integer M, there is an M -sparse approximation using B-spline basis of order m satisfying i=
0 < < min(m, m - -1 - 1/p): f = EMd ak, a. Mm k. for any positive integer M such that the approximation error is bounded as || foll, S M Maadddly a
foll and the coefficients satisfy
|1 ak JN.. lp S [olll
The proof as well as the remark can be found in Section E.2.
Theorem 8. Under the same condition as Proposition 7, for any positive integer M, any function in Besov space fo E Big can be approximated by a parallel neural network with more than ( number of subnetworks satisfying:
1. Each subnetwork has width (md) and depth T..
7

---

Published as a conference paper at ICLR 2023
chservstinn
Foral lenusl
begee funatio
Noural bitwort
20-
Bond tttatin
Band
(eeadting Sprine
Moxer ef Dcnebinng
Pais Rerson
0.-
45-
6:19-
3.-
0:75
-10
3.0
0.2
2.6
0.8
10
30
75
100 125 15017200
0.2
0.2
0.4
3.5
2.0
15
(a) Dopler, DoF=30.
(b) MSE versus DoF.
(c) Active subnetworks.
Chsemvtion
Fara Seazel
Wilannn
bend Milee
Movcle Domoing
Smaothing Sptnic
64
Sepadiing
Donebing
ofl Nimmood
3.-
6.2
3.0
Bagnn of Bender
(d) "Vary", DoF=50.
(c) MSE versus DoF
(f) Active subnetworks.
Paiviel lenrd Nerwis
Hear Retwors
M
Sireemiing
0.36
0.55
Rodl Seural Metwor
Neuii Senwork
Smoothing
Uhen Hinmaax
Melrax
800 815 033 635
6.20
0.00 0.6 0ão
0ds 320
207 (i) MSE versis 12, "Vary"
107
(g) Zoom in to (a)
(h) MSE versis nI, Dopler
Figure 3: Numerical experiment results of the Doppler function (a-c,h), and "vary" function (d-f.g). All the "active" subnetworks are plotted in (f)(f). The horizontal axis in (b) is not linear.
2. The weights in each layer satisfy ([W('lr s Olvw) except the first layer ( ||| O(va).
3. The scaling factors have bounded 2/ L-norm: P == ||aa, 2/1 S 1/11)/(11)
4. The approximation error is bounded by
| - - S (c/M-a/d
+ ege cood -o By
where Ca, Cs, Cs are constants that depend only m, d and p.
Here M is the number of "active" subnetworks, which is not to be confused with the number of subnetworks initialization. The proof can be found in Section E.3.
Using the estimation error in Theorem 5 and approximation error in Theorem 8, by choosing M to minimax the total error, we can conclude the sample complexity of parallel neural networks using l regularization, which is the main result (Theorem 1) of this paper. See Section F for the detail.
5 EXPERIMENT
We empirically compare a parallel neural network (PNN) and a vanilla ReLU neural network (NN) with smoothing spline, trend filtering (TF) (Tibshirani, 2014), and wavelet denoising. Trend filtering
8

---

Published as a conference paper at ICLR 2023
can be viewed more efficient discrete spline version of locally adaptive regression spline and enjoys the same optimal rates for the BV classes Wavelet denoising is also known to be minimax- optimal for the BV classes. The results shown in Figure 3. We use two target functions: Doppler function whose frequency is decreasing ((a)- and a combination of piecewise linear function and piecewise cubic function, or "vary" function (Figure ((d)-(f((i) We repeat each experiment 10 times and take the average. The shallow area in Figure 3(b)() shows 95% confidence interval by inverting the Wald's test. The degree of freedom (DoF) is computed based on Tibshirani (2015).
As can be shown in the figure, both TF and wavelet denoising can adapt to the different levels of smoothness in the target function, while smoothing splines tend to be oversmoothed where the target function is less smooth (the left side in (a)(d), enlarged (g)). The prediction of PNN is similar to TFF and wavelet denoising and shows local adaptivity. Besides, the MSE of PNN almost follows the same trend as TF and wavelet denoising which is consistent with our theoretical understanding that the error rate of neural network is closer to locally adaptive methods. Notably PNN, TF and wavelet denoising achieve lower error at a much smaller degree-of-freedom than smoothing splines.
There are some mild drops in the best MSE one can achieve with Parallel NN vs TF in both examples. We are surprised that the drop is small because Parallel NN needs to learn the basis functions that TF essentially hard-coded. The additional price to pay for using more adaptive and more flexible representation learning method seems not high at all.
In Figure (f)) we give the output all the "active" subnetwork, i.e. the subnetworks whose output is not a constant. Notice that the number of active subnetworks much smaller than the initializa- tion. This is because & regularization in weights induces Ep sparsity and the weight in most of the subnetworks reduces towards O after training. More details are shown in Section H.
In Figure (())i), we plot the MSE versus the number of training samples for "Doppler" and "Vary" respectively. It clear that parallel NN works the best overall. In (i), we further compare the scaling of the MSE against the minimax rate (n (n-4/5) and the minimax linear rate (n 3/44), i.e., the best rate kernel methods could achieve. As is predicted by our theory, when is large, the MSE of parallel neural networks and trend filtering decreases at almost the same rate as the minimax rate, while smoothing splines, as expected, is converging at the (suboptimal) minimax linear rate. Interestingly, vanilla NN seems to converge at the optimal rate too on this examplc. It remains an open question whether vanila NN is merely "lucky" on this example, or also achieves the minimax rate for all functions in B (m))
CONCLUSION AND DISCUSSION
In this paper, we show that a deep parallel neural network can be locally adaptive with standard & regularization. This confirms that neural networks can be nearly optimal in learning functions with heterogeneous smoothness which separates them from kernel methods.
Specifically, we prove that training an L layer parallel neural network with standard Eg regularization is equivalent to an fe/a-penllized regression model with representation learning. Since in typical application L >> 2, standard regularization promotes a sparse linear combination of the learned bases. Using this method, we proved that parallel neural network can achieve close to the minimax rate in the Besov space and bounded variation (BV) space by tuning the regularization factor.
Our result reveals that one do not need to specify the smoothness parameter (or m) when training a parallel neural network. With only an estimation of the upper bound of a (or m), parallel neural networks adapt to different degree of smoothness, choose different parameters for different regions of the domain of the target function. This property shows the strong adaptivity of deep neural networks.
On the other hand, as the depth of neural network L increases, 2/L tends to 0 and the error rate moves closer to the minimax rate of Besov and BV space. This indicates that when the sample size is large enough, deeper models have smaller error than shallower models, and helps explain why empirically deep neural networks has better performance than shallow neural networks.
9

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The work partially supported by NSF Award #2134214. The authors thank Alden Green for references Besov-space embedding of BV classes, Dheeraj Baby for helpful discussion B- splines as well as Ryan Tibshirani on connections to (Tibshirani, 2021) and for sharing with us simpler proof of the Theorem of (Parhi & Nowak, 2021a) based on Caratheorodory's Theorem (used in the proof of Theorem 9 on two-layer NNs).
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Ad- vances in Neural Information Processing Systems, 32, 2019.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 8141-8150, 2019.
Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation-bounded sequences. In
Neural Information Processing Systems (NeurIPS), 2019.
Dheeraj Baby and Yu-Xiang Wang. Adaptive online estimation of piecewise polynomial trends.
Neural Information Processing Systems (NeurIPS), 2020.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 15-333, 1994.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference Machine Learning, pp. 541-549. PMLR, 2018.
Samuel Burer and Renato DC Monteiro. A nonlinear programming algorithm for solving semidefi- nite programs via low-rank factorization. Mathematical Programming, 95(2):329-357, 2003.
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204, PMLR, 2015.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Carl De Boor, Carl De Boor, Etats-Unis Mathématicien, Carl De Boor, and Carl De Boor. A practical guide to splines, volume 27. Springer- Verlag New York, 1978.
Ronald A Deee and George Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
David L Donoho, Richard C Liu, and Brenda MacGibbon. Minimax risk over hyperrectangles, and implications. The Annals of Statisties, pp. 1416-1437, 1990.
David I. Donoho, Iain M Johnstone, al. Minimax estimation via wavelet shrinkage. The annals of Statistics, 26(3):879-921, 1998.
Dinh Düng. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34(1): 1-41, 2011.
Tolga Ergen and Mert Pilanci. Implicit convex regularizers of enn architectures: Convex optimiza- tion of two-and three-layer networks in polynomial time. arXiv preprint arXiv:2006. 2020.
Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterrized neural networks. Journal of machine learning research, 2021a.
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. International Conference on Machine Learning, pp. 2993-3003, PMLR, 2021b.
10

---

Published as a conference paper at ICLR 2023
Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regularization for parallel relu networks. arXiv preprint arXiv:2110.09548,, 2021c.
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In International Conference on Machine Learning, pp. 3004-3014. PMLR, 2021d.
Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 14820-14830, 2020.
Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7331-7339, 2017.
Daniel Hsu, Sham M Kakade, and Tong Zhang. An analysis of random design linear regression. arXiv preprint arXiv: / 206.0006.,, 2011.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Proceedings of the 30th international conference on neural information pro- cessing systems, pp. 41 14 4122. Citeseer, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and gen- eralization in neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 8580 85800,858,.11 2018.
Seung-Jean Kim, Kwangmoo Koh, Stephen Boyd, and Dimitry Gorinevsky. \ell_1 trend filtering. SIAM review, 51(2)3339-60, 2009.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022/8, 2020.
Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensional manifolds using convolutional residual networks. Interna- tional Conference on Machine Learning, pp. 6770-6780. PMLR, 2021.
Stéphane Mallat. wavelet tour of signal processing. Elsevier, 1999.
Enno Mammen and Sara van de Geer. Locally adaptive regression splines. The Annals of Statistics, 25(1):387-413, 1997.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 202141)) 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: 1.1666114 2014.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations, 2019.
Kenta Oono and Taiji Suzuki. Approximation and non-parametric estimation of resnet-type con- volutional neural networks. In International conference on machine learning. pp. 4922-4931. PMLR, 2019.
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. Mach. Learn. Res., 22:43-1, 2021a.
11

---

Published as a conference paper at ICLR 2023
Rahul Parhi and Robert D Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. arXiv preprint vrXiv:2105.03361, 2021b.
Rahul Parhi and Robert D Nowak. Near-minimax optimal estimation with shallow relu neural net- works. arXiv preprint arXiv:2109.08844, 2021c.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial time con- vex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Carl Edward Rasmussen and Christopher KI Williams. Gaussian processes for machine learning. MIT Press, 2006.
Veeranjaneyulu Sadhanala, Yu-Xiang Wang, Addison Hu, and Ryan Tibshirani. Multivariate trend filtering for lattice data, arXiv preprint arXiv:21 2021.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pp. 2667-2690. PMLR, 2019.
Johannes Schmidt-Hieber. Nonparametric regressson using deep neural networks with relu activation function. The Annals of Statistics, 48(4): 875-18977 2020.
Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optinization, and beyond. MIT press, 2001.
Nathan Srebro, Jason DM Rennie, and Tommi S Jaakkola. Maximum-margin matrix factorization. In NIPS, volume 17, pp.
Citeseer, 2004.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv: w/X..08//000803. 2018.
Ryan J Tibshirani. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(())285-322 323, 2014.
Ryan Tibshirani. Degrees of freedom and model search. Statistica Sinica, pp. 1265-1296, 2015.
Ryan Tibshirani. Equivalences between sparse models and neural networks. 2021, URL http: wtwersppppppppppppppppaae..esssp http/pppaasstttt pdf.
//www. stat. cmu.
Ryan Tibshirani. Personal communication, Jan. 24, 2022.
Andreas Veit, Michael J Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. Advances in neural information processing systems, 29:550-558, 2016.
Stefan Wager, Sida Wang, and Percy Liang. Dropout training as adaptive regularization. arXiv preprint arXiv: 130.1113 2013.
Grace Wahba. Spline models for observational data, volume 59. Siam, 1990.
Yu-Xiang Wang, Alex Smola, and Ryan Tibshirani. The falling factorial basis and statistical applications. In International Conference Machine Learning, pp. 730-738. PMLR, 2014.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent Iearn- ing. Constructive Approximation, 26(2):289-315 2007.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114, 2017. ISSN 0893-6080.
doi: http::/6bi.or//1..116jj... http///wwwiinneiieiettt.t.
2017.07.002. URL httpps//www..eiiineeeeeee..ooooo $0893608017301545.
Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
arXiv:1605.07146, 2016.
Hongyang Zhang, Junru Shao. and Ruslan Salakhutdinov. Deep neural networks with multi branch architectures are intrinsically less non-convex. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1109- PMLR, 2019.
12

---

Published as a conference paper at ICLR 2023
A OTHER RELATED WORKS
NN and kernel methods. Jacot et al. (2018) draws the connection between neural networks and kernel methods. However, it has been found that neural networks often outperform any kernel method, especially when the learning rate is relatively large (Lewkowyez et al., 2020). series of work tried to distinguish NN from kemell methods by providing examples of function spaces that NN provably outperform kernel methods (Allen-Zht Zhu & Li, 2019; Ghorbani et al., 2020). However, these papers did not consider the local adaptivity of nerual networks, which provides more systematic explanation.
NN and splines. Besides Parhi & Nowak (2021a) which we discussed earlier, Parhi & Nowak (2021b;c) also leveraged the connections between NNs and splines. Parhi & Nowak (2021b) fo- cused characterizing the variational form of multi-layer NN. Parhi & Nowak (2021c) showed that two-layer ReL.U activated NN achieves minimax rate for a BV class of order but did not cover multilayer NNs nor BV class with order > which is our focus.
Weight-decay regularization with sparsity-inducing penalties. The connection between weight- decay regularization with sparsity-inducing penalties in two-layer NNs is folklore and used by Neyshabur et al. (2014); Savarese et al. (2019); Ongie et al. (2019); Ergen & Pilanci (2021 302la;d); Parhi & Nowak (2021a:c); Pilanci & Ergen (2020). The key underlying technique of the AM-GM inequality (which we used in this paper as well) can be traced back to Srebro et al. (2004) (see a recent exposition by Tibshirani (2021)). Tibshirani (2021) also generalized the result to multi-layered NNs. but with a simple (element-wise) connections. Besides, Ergen & Pi- lanci (2020) proved that training a two-layer convolution neural network (CNN) with weight decay induces sparsity, and points to potential extension to these works including our work.
an application
Finally, it was brought to our attention that while Savarese et al. (2019) mainly consider two-layer NNs, set of results about L-layer parallel NNs presented in Appendix C of their paper, which essentially contains same arguments we used for proving the equivalence to an l2 regularized optimization problem in Proposition 4. The difference is they applied the insight understand the interpolation regime while we focused on analyzing MSE in the noisy case.
Proposition 4, is the Savarese al. (2019) showed that parallel networks of depth L have an inductive bias for the L2/L sparse model, and explicit weight decay causes the solutions of these networks to have a sparse last layer with most nonzero weights.
Resnet-type convolution neural networks. A recent series of work (Oono & Suzuki, 2019; Liu al., 2021) proves that an arbitrary parallel neural network can be approximated by resnet-type convolution neural networks. These works do not require the model to be sparse, thus are easier to train, yet they still require the architecture (the width and depth of each residual block, the number of residual blocks) to be tuned based on the dataset, and the estimation error analysis is based on the number of parameters. Besides, the number of residual block need to increase with n, making the entire too deep to train in practice.
Approximation and estimation. The approximation-thhorere and estimation-theoretic research for neural network has a long history too (Cybenko, 1989; Barron, 1994; Yarotsky, 2017: Schmidt- Hicber, 2020: Suzuki, 2018). Most existing work considered the Holder, Sobolev spaces and their extensions, which contain only homogencously smooth functions and cannot demonstrate the ad- vantage of NNs over kernels. The exceptions including Suzuki (2018); Oono & Suzuki (2019); discussed earlier, requires modifications to NN architecture for each
Liu et al. (2021) which, class. In contrast, we require tuning only the standard weight decay parameter. Most importantly, in all previously works, the estimation error of the model (eg. the covering number) depends on the number of nonzero parameters in the model, while our work provides a bound that depends on the norm of the weights instead of the number of subnetworks.
B TWO-LAYER NEURAL NETWORK WITH TRUNCATED POWER ACTIVATION FUNCTIONS
We start by recapping the result of Parhi & Nowak (2021a) and formalizing its implication in esti- mating BV functions. Parhi & Nowak (2021a) considered two layer neural network with truncated
13

---

Published as a conference paper at ICLR 2023
power activation function. Let the neural network be
f(x)=
Σ uojo" (wsx by) + c(x),
where wij, U4 denote the weight in the first and second layer respectively, by denote the bias in the first layer, c(z) is polynomial of order up to (z) := max(2, 0yrh. Parhi & Nowak (2021a, prriiiiaaioooooolmmmmmm
Theorem 8) showed that when M is large enough, The optimization problem
A Σ (1,y1
min i(f) 30,0
+
+ |mo )
(10)
2
j=1
equivalent the locally adaptive regression spline:
min L(f) + XTV(F(m
(11)
which optimizes arbitrary functions that is m-times weakly differentiable. The latter was studied in Mammen & van de Geer (1997), which leads to the following MSE:
Theorem 9. Let M 2 m, and f be the function (9) parameterized by the minimizer of (10), then
MSE(f) On (2m44)222)))))))
We show a simpler proof in the univariate case due to Tibshirani (2022):
Proof. As shown in Parhi Nowak (2021a, Theorem 8), the minimizer of (10) satisfy
leyl |wyl"* vk
so the TV of the neural network JNN is
M
TV(m) (JNN) = (V(m) c(())(()) +
|uylluy m (m (x:)
/=1
1
Σ (10y + | (mm)
2
which shown that (10) equivalent to the locally adaptive regression spline (11) as long as the number of knots in (11) is no more than M. Furthermore, it is easy to check that any spline with knots no more than M can be expressed as a two layer neural network (10). It suffices prove that the solution in (11) has more than m number of knots.
Mammen & van de Geer (1997, Proposition 1) showed that there is a solution to (11) f(x) such that f(x) is mth order spline with finite number of knots but did not give bound. Let the number of knots be M, we can represent f using the truncated power basis
M
f(x) = 2aj(=- az -2) c(x) = Σ ago (mm) (x) + c(x)
where t, are the knots, c(x) is polynomial of order up to m, and define f (2) = (x t.
Mammen & de Geer (1997) however did not give bound on M. Parhi & Nowak (2021a)² a)'s Theorem 1 implies that M < n m. Its proof is quite technical and applies more generally to a higher dimensional generalization of the BV class.
Tibshirani (2022) communicated to us the following elegant argument to prove the same using ele- mentary convex analysis and linear algebra, which we present below.
14

---

Published as a conference paper at ICLR 2023
Define (f) the (Pn) projection of onto polynomials of degree up m, (f) Im (f). is easy to see that
M f+x = > 2=1
o (m)) (z)
Denote f(11m) = (f(1)).... f(In) E R as vector of all the predictions at the sample points.
M
M
11 (x1m)) = Σ ayll o (IIn) E 11 conv (=o, (m) _
(rim))
layl
M
E conv (m))
(Iim)
Σ ayl
(z1:n)) Σ/= layl is an ne-dimensional space, and polynomials of order up to m is an m + dimensional space, so the set defined above has dimension this space
where conv denotes the convex hull of a set. The convex hull conv(+o (mm)
By Carathéodory's theorem, there is subset of points in
(m) (I J j. (f o (mm)
(a1m)), (
m
such that
f+) Σ az o
(m) (z);
lapl S
other word, there exist a subset of knots {. E [n m]} that perfectly recovers II fz) at all the sample points, and the TV of this function is no larger than f.
This shows that
11 f(x) = Σ āz(2 f.), 5=1
s.t.f(z,) = f(x;)
for all in onbservation points.
The MSE of locally adaptivity regressive spline (11) was studied Mammen & van de Geer (1997,
Section 3), which equals the error rate given in Theorem 9.
This indicates that the neural network (9) is minimax optimal for BV(m).
Let us explain a few the key observations behind this equivalence. (a) The truncated power functions
(together with mith order polynomial) spans the space of an mth order spline. (b) The neural
network in (9) is equivalent to a free-knot spline with M knots (up to reparameterization). (c) A
solution (11) is a spline with most m knots (Parhi & Nowak, 2021a, Theorem 8). (d)
Finally, by the AM-GM inequality
My |wy| 2m 2 2/1y|lw,11* 2|cy1
where с uy|wy|" m is the coefficient of the corresponding jth truncated power basis. The mth order total variation of a spline is equal to E, |cyl. It is not hard to check that loss function depends only on cz, thus the optimal solution will always take "=" in the AM-GM inequality.
C INTRODUCTION To COMMON FUNCTION CLASSES
In the following definition define Q be the domain of the function classes, which will be omitted in the definition.
15

---

Published as a conference paper at ICLR 2023
C.I BESOV CLASS
Definition 1. Modulus of smoothness: For function f E LP(St) some 1 S S xc, the r-th modulus of smoothness is defined by
Wr,
sup heRd:|Allast
|4
A,00= = Σ G)1-1)
if E E Ω
0,
otherwise.
Definition 2. Besov space: For $p 00, 0, [a] 1, define
VL (t 1 (f)t))
q < 00
Ifles,
supt 020
wr, (fitt,
9 = 00;
and define the norm of Besov space as:
llfll Ilfllp + Iflep..
function the Besov space Bp. if [1llll finite.
Note that the Besov space for 0 p is also defined, but in this case it is quasi-Banach space instead of Banach space and will not be covered this paper.
Functions in Besov space can be decomposed using B-spline basis functions. Any function / in Besov space p.g. a d/p can decomposed using B-spline order m, m > at let Rd
f(x)= Σ Σ (m..(F)),,
(12)
km omO
where J(k) : (2~ks: : [-m, 2 +m] c 2d,, (m) == (x -)) and M4 (x)
I Mx(x;)) is the cardinal B-spline basis function which be expressed a polynomial:
Mm(x)= Σ
1-1))
m +1
(x 5)
j
(13)
= (m + 1)
m++1 1
Σ
m7 + 1)
z-j (m + 1)/2
ml j=1
Furthermore, the norm of Besov space equivalent to the sequence norm:
1/9 = |1 (2la-d/p) ((tp))))())..)//))))))ll))))
McC,, =
R=
See e.g. Düng (2011, Theorem 2.2) for the proof.
The Besov space is closely connected to other function spaces including the Hölder space (C*) and the Sobolev space ). Specifically, if the domain of the functions is d-dimensional (Suzuki, 2018; Sadhanala et al., 2021),
Va E N, B% C WO C Bo p, and B = WT.
For 0 < a and a E N, Ca Ba B
If d/p, Ba Co
16

---

Published as a conference paper at ICLR 2023
C.2
OTHER FUNCTION SPACES
Definition 3. Hölder space: let m E N, the m-th order Holder class is defined as
(
C - s max la|=k
D f(x) - < oc, Vx, E
x =1/2
where D denotes the weak derivative.
Note that fraction order of Hölder space can also be defined. For simplicity, we will not cover that case in this paper.
Definition 4. Sobolev space: let m E EN, S S cc, the Sobolev norm is defined as
1/P
Σ
11D
1/ mm
the Sobolev space is the set of functions with finite Sobolev norm:
W II c0))-
Definition 5. Total Variation (TV): The total variation (TV) of a function f on an interval [a, b] is defined as
np
TV())
sup Σ (f(++1) f(x:)]
where the P is taken among all the partitions the interval (a, b).
In many applications. functions with stronger smoothness conditions are needed, which can be mea- sured by high order total variation.
Definition 6. High order total variation: the m-th order total variation is the total variation of the (m 1)-th order derivative
TV() = TV((m>
Definition 7. Bounded variation (BV): The m-thh order bounded variation class is the set of functions whose total variation (TV) is bounded.
(V == {f (V(((m)) < <00
D PROOF OF ESTIMATION ERROR
D.1 EQUIVALENCE BETWEEN PARALLEL NEURAL NETWORKS AND P-NORM PENALIZED PROBLEMS
Proposition 4. There exists one-to-one mapping between X 0 and X such that (2) is equivalent to the following problem:
i 1Eas)) + X1HHa,
arg min (W B .
s.1. | I le S Sava.vje [M]; / || S save, ( L.
where [5(-) is subnetwork with parameters w(O (()
Proof. We make use of the property from (5) minimize the constraint term in (7) while keeping this neural network equivalent to the original one. Specifically, let W(1) (1) .... W(L) (L) be the parameters of an T-layer neural network.
f(x) ((4), a W((-)) ((..-))(...WWW()) (w(1),
b()) .... b(L-11) b())
17

---

Published as a conference paper at ICLR 2023
which is equivalent to
f(x) az OaL- 1 o o(an W x+ b..)).))))))) +b b² +6² (L)
as long as ag > 0, I af - |r where W(0 = w
By the AM-GM inequal-
ity, the &g regularizer of the latter neural network is
2/L.
2/L
III
Σ I| 1
Σ
at
0i II
=
f=1
and equality is reached when 01 02 consider the network that satisfies
In other word, in the problem (2), it suffices to O.
(1) ||F
[|
|| |I=...-= | Vj E [M] E [4].
(14)
Using (5) again, one can find that the neural network is also equivalent
M
f(x) Σ aj
W W
o( (( x+ ) b,
b((-1))
1=1
where
I1 1
E
W (6) L2//2)1112
IW S a0
(15)
11 300
I1 300
Il 3(0)
where the last two equality comes from the assumption (14). Choosing g(() = c1 ccv/ expect / =
where g(1) C1 vd, and scaling ( accordingly and taking the regularizer in (2) into (15) finishes
the proof.
D.2 COVERING NUMBER OF PARALLEL NEURAL NETWORKS
Theorem 5. The covering number of the model defined in (7) apart from the bias in the last layer satisfies
logNN(F.)) $ 2 THE log(wP'/8)
The proof relies on the covering number of each subnetwork in a parallel neural network (Lemmaa 10), observing that If(z) < 2'-1 under the condition in Lemma 10, and then apply Lemma 6. We argue that our choice of condition ||6 in Lemma 10 is suf- ficient to analyzing the model apart from the bias in the last layer, because it guarantees that Viol ((() A (2)]l2 < 1|2 This leads to
I [
I vTlbb S 1loo
If this condition is not met, Ae-) - b(0) is either always positive or always negative for all feasible æ along at least one dimension. If (W(')) + b(()) is always negative, one can replace b(0)) )₂ with max Ar-1x)ll without changing the output of this model for any feasible æ. If (c-() + b(4)), is always positive, one can replace b(t)), with max (c-1 (loo, and adjust the bias in the next layer such that the output of this model is not changed for any feasible In either cases,
replace the bias (c) with another one with smaller norm while keeping the model equivalent except the bias in the last layer.
Lemma 10. Let F {f Rdd RR denote the set of L-layer neural network (or subnetwork in a parallel neural network) with width w in each hidden layer. It has the form
f(x) ( (WL(1))) () oo....(((()
b())....) ...) )) + (L1-1)) + (()) || s (1) E RR,"" 11, (1 < 2/5oo ddw,
(11)_ E ad
( 1 W(0 || F VT, (0) ( ER" (1)00) 2 Vdw, 2....
((4) plxw
| 1 Vw, b(4) 0
(16)
18

---

Published as a conference paper at ICLR 2023
and o(-) is the ReLU activation function, the input satisfy |2]|| I 1, then the supremum norm 5-covering number of F obeys
log.V(F.8) I Lz log +
where C7 is constant depending only d, and is constant that depend on d, w and L.
Proof. First study two neural networks which differ by only one layer. Let ge, g' be two neural net- works satisfying (16) with parameters W I..b..... W., L, by and W1, "i."b..... WT, bj, respectively. Furthermore, the parameters in these two models are the same except the 6-th layer, which satisfy
W Welle - b|, b/ll2 S.
Denote the model as
ge(z) B2 (W ((())))))))))))))) +z). (/(z) (w(((()) +
where Ax(x) = σ (W o ( .+))) network, and Ag(x)
denotes the first é 1 layers in the neural b(+1) ...)) ) denotes the last L f layers,
(Lo(...o(WeH))
with definition A1 (z) = x, (z) x.
Now focus on bounding |A(x))] Let W E mmxm || S Vmd, E Rm' b E R", 1 S ym
Ilo b)ll2
|W + bll2
|W| |||| + |b||
[ 2 + |
< Vmm | 222 + m
where we make use of] ||
1l2 1 || ||r. Because of that,
A2(x))l 2 S vd + vdw S 2V dw,
[Aas())]2 $ (22x)) l2 + zwvdw S Awe
(17)
[x)]2 v A (z)]l2 S 2V dwo
Then focus on B(x). Let W E Rmxm' |/ S Vm' x. xt E Rm b TR"" |b/22 s mm. Furthermore, | x ||2 S then
|ooWw + b) - o (Wa' + b)1l2 - W a - x 222 S | ø'1l2
which indicates that (z))) - B(x)|12 S (vw) b- f x' ll
Finally, for any W, W E mm Rm b. b' E m one have
[Wa + b) - (W'x x + b1)122 [[ - W') + (b - b'>ll2
< W W l2 + ||b 1|2-
< W |/ + / bb b' b'll ||x
In summary,
ge(x) g(xx) (B.(W by) ((( +b)l
$ (VD) (W Ae(x) + bz) (W A(()) + b/)1
$ (Vw) (/ - (e + b b(112)
< (l1-1) (L4E3)) 1/2 (L-1)/2
Let f(x) be two neural networks satisfying (16) with parameters W1, WL, by and Wi. bg...., W7, by, respectively, and I[W Will p S <e, bb 1/rl r & Tt. Further define fe be the neural network with parameters W1, by...., We, be, W W/+1 14411 WL. bg then
If(x) -'(=) < fx)) fxx)) + (x) fa(a)) + .... +... +1f2-1 f((2)
1
2 2)-22 122
(L+E-3) + w (2-1/22
19

---

Published as a conference paper at ICLR 2023
For any 8 >> O, one can choose
8
c
2w(L--1/22
such that
8.
On the other hand, the e-covering number of {W Rmxm', W I Vm on Frobenius norm is no larger than (2vm'/e 1)mxm' and the E-covering number of {b E R ||61|2 I 1) on infinity norm is no larger than (2/6 1)m The entropy of this neural network can be bounded by
log (V; < w log(2" (2 w 11/-1//// + 1) + wL log(2" 1)/2 1/
D.3 COVERING NUMBER OF p-NORM CONSTRAINED LINEAR COMBINATION
Lemma 6. Let G S (R. i-c cal) be set with covering number satisfying log.V x k 1og(1/8) for some finite ca2 and for any E 9, |a| S 1, we have ag E g. The covering number of satisfies
F E agils E G, |al|B - P. <
for any
F log Nog,((Fe c) S kP kPT (6/ca)) - log(csP/8)
up double logarithmic factor.
Proof. Let e be a positive constant. Without the loss of generality, we can sort the coefficients in descending order terms of their absolute values. There exists a positive integer M (as a function of e), such that |os] 2 e for S M, and |asl < e for >> M.
By definition, MeP < Furthermore,
EM
M
lai S so M P/cl, and lai1 s Po pl/p for all i.
Σ |all = Σ lail la 1 1-P << Σ 1- P P Pm
M2M
1..M
Let g, arg min covering set,
geg llg
a, gilloo where & is the o'-convering of G. By definition of the
M
M
M
M
Σ
(x) Σ
pl/rg(())
<
Σ (x) - (aaee)-pP/00 pl/rg((z)) im1
+
Σ i+
(,g:(z)
< MPP1/8'' PctPttPp
(18)
Choosing
(5/2c3 T 8' P কা- (8/2ca) 22322)) T T-7 /2,
(19)
we have M < (822c)))ca)) 1 Cr,MP1/1 MPI/18' S 6/2,c3Pe--P - 8/2, so (18) < compute the covering number of F by
One can
log.N((F S MMog 8') ) $ kMlog(1/8")
(20)
Taking (19) into (20) finishes the proof.
E PROOF OF APPROXIMATION ERROR
E. APPROXIMATION NEURAL NETWORKS B-SPLINE BASIS FUNCTIONS
Lemma 11. Let Mm.k. be the B-spline of order m with scale 2 in each dimension and position E IRd; Mm. := Mm (2 s)), Mm. is defined in (13). There exists neural network with d-dimensional input and one output, with width Wa.m = O(dm) and depth I. S log(ca, /)) for some constant Cd.m that depends only on and d, approximates the B spline basis func- tion Mm,k, = Mm (2 8)) defined in Section C.I. This neural network, denoted as M (m), Rdd. satisfy
20

---

Published as a conference paper at ICLR 2023
(M,k,o(z)) Mm,k. c, if0 2", -4) m 1, [d].
(m) O, otherwise.
The weight in each layer has bounded norm where || /d.
|| S 2 fue, except the first layer
Note that the product of the coefficients among all the layers are proportional to 24, instead of 2 when approximating truncated power basis functions. This is because the transformation from Mn. to Mm.k.s only scales the domain of the function by 2-, while the codomain the function is not changed. To apply the transformation the neural network, one only need scale weights in the first layer by 2", which is equivalent to scaling the weights in each layer bt 2 and adjusting the bias according.
As for the proof, follow the method developed in Yarotsky (2017); Suzuki (2018), while putting our attention on bounding the Frobenius norm of the weights.
Lemma 12 (Yarotsky (2017, Proposition 3)). There exists neural network with two-dimensional input and one output fx (x, y), with constant width and depth ((log(//))), and the weight in each layer is bounded by a global constant e1, such that
1fx(z, - zyl - 6 S x. 1.
fx(x,)) 0, x or
We first prove a special case of Lemma 11 on the unscaled, unshifted B-spline basis function by fixing & 0, s 0:
Proposition 13. There exists neural network with d-cimmensionll input and one output, with width w = w(, m) x dm and depth S log(e(m, d)/e) )) for some constant w, c that depends only on m and d, denoted as Mm(x)). x E Rd, such that
(m)()) Mm (x)) I e, if0 S x4 IAS m m
1 m
[d]. while Mm denote m-th order
B-spline basis function,
Mm (x:) 0, if or foor any i E [d].
The weight in each layer has bounded norm |W00 S Vo.
Proof. We first show that one can use a neural network with constant width wn, depth L 2
log(m/ez) and bounded norm || < O(vd), [| < O(vw), Ve = 2.... L to approximate truncated power basis function up to accuracy 61 in the range [0, 1]. Let m
[log, m;2', m, E (0.1) 1) be the binary digits of m, and define my Σÿ= ma, 7 flog, m], then for any x
r4
x+ X
The
(1+
27 my
my 27
my x (x 27-1 my-1
27-1
27-1
[++
x
x4
(21)
[x f2
x11
(x
mi
x
2
[x 22
[
x
mi
x+]
Notice that each line of equation only depends on the line immediately below. Replacing the multiply operator x with the neural network approximation shown in Lemma 12 demonstrates the architecture of such neural network approximation. For any ø. E [0, 1), let (x, - xy < 5, lz il 61, ly Syl I 6g. then (ā, ū) xyl I & + 82 + 8. Taking this into (21) shows that E ~ 278 8 = mo, where é is the upper bound on the approximate error to truncated power basis of order and 5 is the approximation error to single multiply operator in Lemma 12.
21

---

Published as a conference paper at ICLR 2023
A univariate B-spline basis can be expressed using truncated power basis, and observing that it is symmetric around (m + 1)/2:
m2+1
m + 1
(x)
j )
(xr 11)
j=1
(m++1)/2]
m (m++1
Σ
(-1)²
(nin(a,,m+ m x) -])
=m!
[(m-1)/
((m + 1)/2)
(-1) m (m=+)) (-1)("+)))
min((, ( m + x) + 11/2
Σ
m!
1=1
multivariate (d-dimensional) B-spline basis function can be expressed the product of truncated power basis functions and thus can be decomposed as
(m))) II M Mm(x)) (xi)
-(Im+ 1)/2)md (ml)d
[mm+1)/2]
(-1)² m +11 minn( m mn++1 11=x) - m (22)
!)
Σ
(m 1)/2
Using Lemma 12, one can construct m + number of neural networks, and each of them has width =-
wo and depth = O(log(m/e1), such that the (j + 1)-th neural network approximates 11m+11/2 ) with more than for any 0 S subnetworks can approximate the univariate B-spline basis function with error no more than
(m + 1)/2. The weighted summation of these
d((m + 1)/2)"
1
Σ
m +
2m
E1
El
m.!
m
where we applied Stirling's 's approximation.
A multivariate B-spline basis is the product of univariate B-spline basis along each dimension
M (ar) = II (xr)
2=1
We can construct neural network to approximate this function by parallizing d number of neural networks to approximate each B-spline basis function along each dimension, and use the last L R log(d/8) layers to approximate their product. The totol approximation error of this function is bounded by
a (m + 1) mit1
m +
2.
c + (d - 1)8
de + dō
m!
vm
where 6 and é has the same definition as above. Choosing å Metm 1m11 and recall ej md proves the approximation error.
The proof of the Lemma 11 for general k, follows by appending one more layer in the front, as we show below.
Proof of Lemma II. Using the neural network proposed in Proposition 13, one can construct a neu- ral network for appropximating Mm.k.a by adding one layer before the first layer:
012 2 s)
22

---

Published as a conference paper at ICLR 2023
The unused neurons in the first hidden layer is zero padded. The Frobenius norm of the weight is 2* |Lale 2* Vd. Following the proof of Proposition 4, rescaling the weight in this layer by 2 2 and the weight matrix in the last layer by 2h, and scaling the bias properly, one can verify that this neural network satisfy the statement.
E.2 SPARSE APPROXIMATION OF BESOV FUNCTIONS USING B-SPLINE WAVELETS
Proposition 7. Let a d/p > 1,r > O. For any function in Besov space fo E B and any positive integer M, there is an M- M-sparse approximation using B-spline basis of order m satisfying < < min(mm, m 1n-+
m- +++11 1/p): JM >i=1 0kt,s: M Mm.ks... for any positive integer M such that the approximation error is bounded as Ilf MM follr S M a/d follBByy,, and the coefficients satisfy
11 0k s: Jk lp S So mg..
Remark 1. The requirement in Proposition 7: a d/p > 1 is stronger than the condition rypically found in approximation theorem - dip 2 0 (Däng, 2011), so-called "Boundary of continuity" or the condition Suzuki (2018) a > d(1/p- 1/r)+ This because although the functions By when 0 S a d/p < 1 can be approximated by B-spline basis, the sum of weighted coefficients may not converge. One simple example is the step function [sep(()) = 1(x 2 0.5), E Bl.so. Although can be decomposed using first order B-spline basis as in (12), the summation of the coefficients is infinite. Aciually one only needs ReLU neural network with one hidden layer and two neurons to approximate this function to arbitrary precision, but the weight need to go to infinity.
Proof. Düng (2011, Theorem 3.1) Suzuki (2018, Lemma 2) proposed an adaptive sampling recovery method that approximates a function in Besov space. The method is divided into two cases: when p 2 r, and when p < r.
When 2 r, there exists sequence of scalars Ay: E (d), == (i Zd lill S S.ViE d} for some positive μ., for arbitrary positive integer k, the linear operator
()( = Σ (f)
(
E
a (k)
jE84,P9())
has bounded approximation error
Il I Qz-
C2-ak -1
where f is the extrapolation of f. J[k,, m, d) == {s: 2 E 2d, . mm/ 2 2² + m/2, Vi e [d]] See Düng 2.6-277) for the detail of the extrapolation as well as references for options of sequence Az.
Furthermore, (f) E Byg so it can be decomposed in the form (12) with M = +m 1)d $ 2nd components and a S [1Qx()) By, X || | where čτ,a is the coefficients of the decomposition of (&) Choosing 1: ~ logz M/d leads to the desired approximation error.
On the other hand, when p < r, there exists a greedy algorithm that constructs
+
Ck.o, (f)Mr.e,
k=b+1i=1
6 log (AM) + Te + 1,n [AM for some 0 < < a/8 1, = 1(11p-1/1p) 0, such that
where &e = log, (M), k*
- -(f < M of
and
k
Σ f2t + 1)d + Σ
n M.
k=
k=b+1
23

---

Published as a conference paper at ICLR 2023
See Düng (2011, Theorem 3.1) for the detail. Finally, since a d/p 1.
|1(2% CR. o. Jh. S
2
2 (a ///1////////////
(2 (H te.ll)
(23)
k=0
k
2 (1 - (a d/
l/p)) |
k=0
|1 ng.
where the first line because for arbitrary vectors a;, E [n] a:llp S Σ. ||aillp- the third line is because the sequence norm of B-spline decomposition is equivalent to the norm in Besov space (see Section C.I).
Note that when d/p k* llg." which can be proven by following (23) except the last line. This adds logarithmic term with respect to M compared with the result in Proposition 7. This will add a logarithmic factor to the MSE. We will not focus on this case in this paper of simplicity.
the sequence norm (23) is bounded (up factor of constant) by
E.3 SPARSE APPROXIMATION OF BESOV FUNCTIONS USING PARALLEL NEURAL NETWORKS
Theorem 8. Under the same condition Proposition for any positive integer M, any function in Besov space so E B% can be approximated by a parallel neural network with no more than ((M) number of subnetworks satisfying:
1. Each subnetwork has width w = (mdd) and depth L.
2. The weights in each layer satisfy ([ || & O(Vw) except the first layer ([ O(yd).
11 S
2/L 3. The scaling factors have bounded 2/ L-norm: P || 12/2. 2 2/(1)
4. The approximation error is bounded by
| foll, S Mc/ + osE so )1l col)
where C4. Cs C6 are constants that depend only on m, d and
The proof is divided into three steps:
1. Bound the O-norm and the p-norm of the coefficients of B-spline basis in order approxi- mate arbitrary function in Besov space up to any 0.
2. Bound p' p'nnorm of the coefficients of B-spline basis functions where p' = -2 < p' < using the results above
3. Add the approximation of neural network to B-spline basis computed in Lemma 11 into Step 2.
We first prove the following lemma.
Lemma 14. For any a E RM, 0 p' < p. holds that:
|aally S M 17 /1/01//
Proof.
1-2
z
Σ la, 1 =
< Σ1
Σ (1as (lasp1') 13)
N7 1 ||a
24

---

Published as a conference paper at ICLR 2023
The first inequality uses Holder's inequality with conjugate pair & and 1/(1 p
Proof of Theorem 8. Using Proposition 7, one can construct M number of NN according to Lemma 11, such that each NN represents one B-spline basis function. The weights in the last layer of each NN is scaled to match the coefficients in Proposition 7. Taking p' in Lemma 14 as 2/T. and combining with Lemma 11 finishes the proof.
F PROOF OF THE MAIN THEOREM
Theorem extended form. For any fixed d/p 1,9 1, define m [a 17. For any fo E B p.s given an L-layer parallel neural network satisfying
The width of each subnetwork is fixed satisfying w 2 O(md). See Theorem 8 for the detail.
1-2/h
The number of subnetworks is large enough: M 2
Under the assumption as in Lemma 17, with proper choice of the parameter of regularizaton X that depends on D. a. d, L, the solution f parameterized by (2) satisfies
MSF()) Ō =Ō
112-1//1 1/-1/4
2nid
20/8-1-2/(p1
+ -coL
n2 2/L
where Ô shows the scale up a logarithmic factor, and os is the constant defined in Theorem 8.
Proof. First recall the relationship between covering number (entropy) and estimation eroor
Proposition 15. Let S (R. - be set of functions. Assume that can be decomposed into two orthogonal spaces F = = where F is an affine space with dimension of N. Let fo (TR: [-F, F)} be the target function and be the least squares estimator
= arg min
Σ (ys - ((x))) v fo(o,) + tGi ~ o'i.dd)
FEF
1=1
then it holds that
N + log Wo11 + + (F + o)o).
MSE(f) 2
arg min MSE(F) + fEF
7
The proof of Proposition 15 is defered to the section below. We choose F as the set of functions that can be represented by a parallel neural network as stated, the (null) space F1 {f f(x) constant) be the set of functions with constant output, which has dimension 1. This space captures the bias in the last layer, while the other parameters contributes to the projection tion D.2 for how we handle the bias in the other layers. One can find that Fi is the set of functions that can be represented by parallel neural network stated, and further satisfy Σ f(x:; 0.
F See Sec-
Because Fi S F. (F - (FF 5) for all > O, and the latter is studied Theorem 5.
In Theorem the width of each subnetwork is no less than what is required in Theorem 8, while the depth and norm constraint are the same, so the approximation error is no more that that in Theorem 8. Choosing 2,p p 2/ L, and taking Theorem 5 and Theorem 8 into this Proposition 15, one gets
w 2+2((1 2/1) 1 Vdp' T 8 1-2jE log W (//WP/// +8
2/1.
MSE(f) < min MSE(f) + feF
(24)
2a/d
2a/d
2 2222/(1-211D2
M
1-2/221 2/6 --...
т- (log(M/0) + +3) +
"
where || p.
and d taken constants. By choosing
4-4/ 1,2-1/1--1111 L/L 1 2/(L))
n 1-21
M =
2n 2n/441-2/(01)
n 1-12/1 1/
4-44/
2-44/I
25

---

Published as a conference paper at ICLR 2023
get
- 1/4
20/d id
MSE() =ō
2n/ 11/2-1-2/(p1
+ cco
(25)
n1-2/L
where MSE(f) shows the MSE of the solution to constrained optimization problem (7) by optimally choosing M (or P').
Finally, under the assumption in Lemma 17, for any constrained optimization problem, there exists a regularized optimzation problem, whose MSE is not larger than the MSE of the constrained opti- mization problem up to factor of a constant. This closes the connection between (6) and (7) and finishes the proof.
Note that the empirical risk minimizer (ERM) of the parallel nerual network satisfy that the (2/L)- norm of the coefficients of the parallel neural network satisfy that || 1122/ IK H22/ where (āg.u) } is the coefficient of the particular M-sparse approximation, although {a,) not necessarily M sparse. Empirically, one only need to guarantee that during initialization, the number of sub- networks M 2 M such that the M -sspare approximation is feasible, thus the approximation error bound from Theorem can be applied. Theorem also says that I1fa, } 1///
(110,,,31/// & M1-2/pL, thus we can apply the covering number bound from Theorem 5 with f' M 2-p//pL, Finally, if A is optimally chosen, then it achieves a smaller MSE than this particular X', which has been proven to be no more than O(M-a/c and completes the proof.
Proof of Proposition 15. For any function f E F, define f1 arg m Ef=(((a;)
)² 2 be the projection of f to Fi, and define J1 = f fu be the projection to the orthogo- nal complement. Note that f is not necessarily
Fi. However, f F, then JiI E Fii- Peu and yal are defined by creating function fy such that fx;) yı. Vi, e.g. via interpolation. Because Fi and Fi are orthogonal, the empirical loss and population loss can be decomposed in the same way:
[f((f)
Σ
(f(())) (x))
0²,
Li(f) = SE (f((x) - fol( +
N 0²,
=
n i=1
Ln(f)
1
Σ
(f (x) 3:
Li(f) 1 n1 Σ (f)(x) - (x))
n1
MSE Ep [
1
Σ (z) fun(()))
MSE.(F) ED - Σ (z)()) for (2))
i=1
such that L(f) (i( L1()),(f)) Ln( + L1()). This can be verified by de- composing fo and y into two orthogonal components as shown above, and observing that Ei (2,)) (z,) 0, f2.
First prove the following claim
Claim 16. Assume that f = arg min Jer L(f) is the empirical risk minimizer. Then fl arg min JiF L = arg minser (f), where fi is the projections of in Fi. and Ju f- respectively.
Proof. Since i f by definition f F1. Assume that there exist fi, Si. and either (f)) L (i(F)), i (p)) < (f)) Then
i(") = i(i + - -2 (()
< ( +
+ f1)=
which shows that f is not the minimizer of i.()) and violates the assumption.
26

---

Published as a conference paper at ICLR 2023
Then we bound M MSE We convert this part into a finite dimension least square problem:
f1
arg min [J) fefi
1
arg min fEFi
(f(a)) fol (x:) =2112
arg min feFi
1
=E (f(;)) foi( - =Ei1)2 + Eil
i=1
E (J(x;) for (x:) 6/8 - -6o1)
arg min feFi
n
arg min
E (f( foi (x:) c;)2
JEFi
n
The forth line comes from our assumption that Fi is orthogonal to Fii, so Vʃ E FL, f for tel orthogonal ElI-
Let the basis function of Fi be h1 he..... hw, the above problem can be reparameterized as
1
arg min
X yl1²
BERN 71
where X E RAXN, x h Tou + 6, Vo.1 (21), for (rn)), (e,,...,,n) mn)
This problem has closed-form solution
0 xx -x"
Observe that foi F1, let Hoo
X00 The MSE of this problem can be computed by
I(f1)= = X8 Yo 1-- X 1
(Xo* +c) - x0
XX x -xx c|2
_ n
Observing that II = X(X X) -1x" is an idempotent and independent projection whose rank N, and that E[cc?' II get
MSE MSE,(f)) = _ [T]| = 1 tr (II)
a²
which concludes that
MSE -
N -02
(26)
n
See also (Hsu et al., 2011, Proposition 1).
Next study MSE (f). Denote of Σn Ep E max, |g]. Using Jensen's inequality and union bound, we have
( Elexp(LE))
E max exp()ee))
Elexp([|e<DD 2nexp((2
Taking expectation over both sides, we get
log
to² + t
E
<
2
maximizing the right hand side over yields
F S a / 2 2n.
27

---

Published as a conference paper at ICLR 2023
Let Fi be the covering set of Fi (fi f E F). For any fl Fi,
N
- - b1(())) =
(2s)) - (a;1))))))
Σ
([](ars) - 1111)2
n ==1
n
==1
Σ (1(2f((a:)) foo((a)) -Val)) + N o²
7
n
(22 (ax)) -2,) -Val) n N o²
(2 (m.) (z0] + n N o² oî
The first term can be bounded using Bernstein's inequality: let h; = c (ffs(((2;)) - (a;)), by
definition [h,] S 2EF.
Var[h;] = [F (xx) fo (xx))
(f) foll (x: B
= (x.) - for (x:))
using Bernstein's inequality, for any 8 E F1. with probably at least 1 6p.
(x:) - 25o = Σ hi
1=1
8EF (og((165))
2
>
(Fi(z); fo1(2;)) 02 log(1/6p)) +
3n
i=1
= 2/ (LI(FT) N-N 0²
N
20 200 (L)6p))
SEF log (1/pp)
n1
3n SEF log (1/8p)
sc <e(Li n n-N
N
S log( (16pp)
T1E
3n
the last inequality holds true for all c > 0. The union bound shows that with probably at least 6, for all fl E F,
- (Fi) S (L1 (fi) n ==N 02) S0² (o SEF (F) 8)/6p)
-
3n
N o² o7.
By rearanging the terms and using the definition of T(J we get
(1-c)( n (1- < (n)( 802 (F) 6)/bp)
8EF (og o..
+
mE
3n
a-N 0², Furthermore, for Taking the expectation (over D) on both sides, and notice that E[a any random variable X, [[ = -_ xdP(X S x), we get
(1 - (1- M)EE (Ft) ((LL
max EiFF
802
/ 2m
)
(1og.V(F)::0) - -f" 1og(5))dāp)
n N 0²
<
+
(27)
ne
3n
-8=0
8
8Fo /2o log 2n
n N 2
(log
3n
where the integration can be computed by replacing with e Though it is not integrable under Riemann integral, it is integrable under Lebesgue integration.
28

---

Published as a conference paper at ICLR 2023
Similarly, let fi arg meg L((l),
- 1 Σ (22f(((z))) 2fo (a:))
2 N
01
n
with probably at least - 6g. for any > O.
Σ 6(2f (an:) - (5on( S < [zp (Fi) n- N o²) No²) 80² log(1165g
8EF 8EFlog(1 (1)p)
ne
3n
( s (1 + c) (LI(A)) -²= - 1og(1/6p)
o2)
8EF log(1/6g)
+ o
ne
3n
Taking the expectation on both sides,
BLL (FD) S (1+ MMSE (fi) + 80²
8Fov2log 2n
n N 0².
(28)
n1
3n
Finally, let f. == arg Ei (f(xt)) - f(x:))² be the projection of fl in its 8-covering space,
12
MSE
(fi) E n
(f (x:) (2:)) - (2:)))
E
(fx (o,))) + :=1
( +x, D (a,)
+ f. (((.)))-((())))(((((())))))) 2So (x,))
E
- fo + 4F8
-
MSE (f+ (x:)) 4F8,
and similarly
(f(f=) S + +(FF)++44)))))
(29)
We can conclude that
1
1802
/Fov2 2n
(log.N(F),.0) +1) n N 2
(f) <
(f+)] +
+
1-e
ME
3n
4F8
[ELLI + (4F + / 8 2n)6
802
/ 2n
(lggN(FFi:))+ +1 N --No?) + +FF
3n
n
(ELL + (4F +oV log 2n)o
80²
+
8Fo 2n
(log.N(FF). 5) +1
n - 0²) + 448
3n
802
8F log 2n
log (FF F 6) + 2
MSE
+ 11
1-6
+ (FF + 4F + +oy8 log 2n
8
1-c
where the first line comes from (27), and second comes from (29), the thid line is because fi = arg min L (f). and the last line comes from (28). We also use that fact that ( s
(f), Vf. Noticing that MSE(f) = MSE + MSE, (f), combining this with (26) finishes the proof.
n
29

---

Published as a conference paper at ICLR 2023
Lemma 17. Assume that these exists C1. C2 > 1 (which may depend on the target function), for
all P >> O, there exists > O, such that the soltion to the regularized optimization problem (6),
denoted as f. satisfy
C,P' S Há, 2/1 S C2P,
then the MSE of the regularized optimization problem satisfy
MSE(}) S CMSE())
where C' is a constant that depends C1, C2. f is the solution to the constrained optimzation problem (7), and
MSF(f) P (n-211)
A
Proof. The MSE of the regularized problem can be achieved by taking our assumtion into (4). We only need prove the selection of X. We apply the decomposition in Proposition 15, and only need to consider Fij, as FL. is not imfluenced by regularization or constrained. From the definition of f and X, have
i(F) (l 11 s i(f + Al163
(n + *1[ M| 2/L - 41( + A1H(1))11/1 2/L
From Proposition 15, get
log. 1og. (1, || 2/L 6)
(1 M))S(()( -
+ {11
(30)
log.N(1l(g)) 1
< (1+ ()++))ME(f)++ +0
+ >11
Observing that MSF(J) 2 0, and log A
3/L 272
MSF(f) for the optimally chosen Pl. taking the assumtion into the inequality proves the choice of X.
Remark 2. Define R(A) R( min L(f)+ where R(f) I( H12/. is the regularizer term of a parallel NN (f). Notice that R(A) is a non-increasing function of lambda (as proved below), the assumption in Lemma 17 is equivalent that R(A) contains any uncontinuous points, then the uncontinuous points should not be larger than C2 C in ratio. On the other hand, if X is chosen
as X = 0 (MMEA MSEL)) then from (30), we get
pr
< O(MSE( +O log ((1 2/L 2/L
A| 1
2/L
2//11
+ 2/4 rb)
<((SE(() OO
If the constant term in X is large enough, the above inequality yields sets of solutions:
2/2 < so (11 +
{MSE(()
O(I -1116,
and
MagH11/44 2 Ō((2)) (
In the first case, one can easily see from (30) that MSE()) S O(MSE())). which says that the MSE of the regularized problem is close to the minimax rate; in the later case, the generalization gap of the regularized problem is bounded by O(n 2/5 X112), which is much larger than the former case. So sufficient condition of the above assumption is that the model does not overfit significantly (by
30

---

Representation learning and adaptivity. The results also shed a light on the role of representation learning in DNN's ability to adapt. Specifically, different from the two-layer NN in (Parhi & Nowak, 2021a), which achieves the minimax rate of BV (m) by choosing appropriate activation functions using each m, each subnetwork of a parallel NN can learn to approximate the spline basis of an arbitrary order, which means that if we choose T. to be sufficiently large, such Parallel NN with optimally tuned À is simultaneously near optimal for m 1, .... ...... In fact, even if different regions of the space has different orders of smoothness, the paralle NN will still be able to learn Published as a conference paper at ICLR 2023
orders of magnitude) more than the constrained version. In experiment, we find that the latter case is very difficult to happen, possibly because of the implicit regularization during training, and the connection between X and effective degree of freedom is actually smooth. Notably, L gets larger, in the second case [| 3 H2// increases exponentially with L (the constant terms depends at most polynomially on L,), which suggests that the latter case is less likely to happen for deep neural networks.
Claim 18. For fixed D, the regularized problem satisfy that R(2) as defined above is strictly non- increasing with X.
Proof. We provide short proof by contradiction: suppose that there exists lambdaa < A2, and the solution satisfy (fi) R(f2) where R(f) || {a,} 1 the regularizer term of parallel NN, fi, fz are the solution to the regularized problem with = >1 respectively. Then by definition
of f1, f2, we have L(fi)+
s [(f)+> so R(fa)-
((f))i((a); L(f2)((2 s
i(Л)) + A2R((1), so Ao < ((f))-J1
-(fi)-((aa) which is controversal to our assumption that λ < X2. O
G MORE DISCUSSION ABOUT THE MAIN RESULT
appropriate basis functions in each local region. To the best of our knowledge, this is property that none of the classical nonparametric regression methods possess.
Synthesis analysis methods. Our result could also inspire new ideas in estimator design. There are two families of methods in non-parametric estimation. One called synthesis framework which focuses constructing appropriate basis functions encode the contemplated structures and regress the data to such basis, e.g., wavelets (Donoho et al., 1998). The other is called anal- ysis framework which uses analysis regularization on the data directly (see, e.g., RKHS methods (Scholkopf & Smola, 2001) or trend filtering (Tibshirani, 2014)). It appears to us that parallel NN doing both simultaneously. It has parametric family capable to synthesizing an (n) subset of an exponentially large family of basis, then implicitly use select the relevant basis functions. In this way the estimator does not actually have to explicitly represent that exponentially large set of basis functions, thus computationally more efficient.
analysis regularization
Random design problem. This paper focuses on the fixed design problem such that the results are comparable to that in nonparametic regression. One can easily apply the technique in this paper to achieve the estimation error bound on the random design problem:
Theorem 19. Under the same condition Theorem I, the solution î parameterized by (2) satisfies
EDE, Sō
w 4/ 4/1.
2a/d1l 2/(22) + e -co
L
where Ô shows the scale up logarithmic factor, and C9 is the constant defined in Theorem 8, Ep indicates that the expectation is taken with respect to the training set DD E, indicates that the expectation is taken with respect to the domain of f.
The proof is similar to that of Theorem 1. The main difference lays in the proof of the estimation error. For f_ part, the estimation error can be bounded using VC-dimension, which is 1. For f part, the estimation error can be bounded using its covering number, e.g. Lemma in Schmidt-Hichbe (2020).
31

---

Published as a conference paper at ICLR 2023
H DETAILED EXPERIMENTAL SETUP
H.1 TARGET FUNCTIONS
The doppler function used in Figure 3(d)-(f) is
f(z) = 0.01)) + 1.5.
The "vary" function used in Figure 3(g) is
f(x) = M1(1/0.011+ + M1 ((x 0.02)/0.02) + M1((1 0.06)/0.03) M1((2 0.12))0..1) + Ms[(1 0.2)/0.02) + M2 0.28)
+ M2((2 0.44)/0.06) + M2((x - 0.68)/0.08),
where M1, M3 are first and third order Cardinal B-spline bases functions respectively. We uni- formly take 256 samples from to 1 in the piecewise cubic function experiment, and uniformly 1000 samples from 0 to 1 in the doppler function and "vary" function experiment. We add zero mean independent (white) Gaussian noise the observations. The standard derivation of noise is 0.4 in the doppler function experiment and 0.1 in the "vary" function experiment.
H.2 TRAINING/FITTING METHOD
In the piecewise polynomial function ("vary") experiment, the depth of the PNN L 10, the width of each subnetwork w 10, and the model contains M 500 subnetworks. The depth of NN is also 10, and the width 240 such that NN and PNN have almost the same number of parameters. In the doppler function experiment, the depth of the PNN L 12, the width of each subnetwork 2000 subnetworks, because this problem requires more complex model fit. The depth of NN is 12, and the width is 470. We used Adam optimizer with learning rate of 10-3 We first train the neural network layer by layer without weight decay. Specifically, we start with two-layer neural network with the same number of subnetworks and the same width in each subnetwork, then train three layer neural network by initializing the first layer using the trained two layer one, until the desired depth is reached. After that, we turn the weight decay parameter and train it until convergence. In both trend filtering and smoothing spline experiment, the order is 3, and in wavelet denoising experiment, we use sym4 wavelet with soft thresholding. We implement the trend filtering problem according to Tibshirani (2014) using CVXPY, and use MOSEK to solve the convex optimization problem. We directly call function amooth.spline to solve smoothing spline.
10, and the model contains
H.3 POST PROCESSING
The degree of freedom smoothing spline is returned by the solver in R. which rounded to the nearest integer when plotting. To estimate the degree of freedom of trend filtering, for each choice of X, we repeated the experiment for 10 times and compute the average number of nonzero knots as estimated degree of freedom. For neural networks, use the definition (Tibshirani, 2015):
20 E -011
Elyy 001
(31)
where df denotes the degree of freedom, x² is the variance the noise, y are the labels, ÿ are the predictions and y' independent copy of y. We find that estimating (31) directly by sampling leads to large error when the degree of freedom is small. Instead, we compute
20 E 9
El
112
E
Jol1
11 voll
(32)
where df the estimated degree of freedom, denotes the empirical average (sample mean), Do is the target function and Zo is the mean of the target function in its domain.
Proposition 20. The expectation of (32) over the dataset D equals (31).
32

---

Published as a conference paper at ICLR 2023
Proof.
2f
Ep|
yo
011 -Bll u12 B1yy Doll2 133 Boll2
1///y/ - U12 Ely -012 ED (D - yo) + yo 20o)]]
Bl
E Ely 012 E Σ (2 + 200)
E| Vo Ú E y
31
no²
E D b11 Fly أ1ا
where DD denotes the dataset. In the third line, we make use of the fact that [E[c]] = 0, E(c]] = o² and in the last line, we make use of Ele]] = E[: = o², and e/ are independent of and you C
One can easily check that a "zero predictor" (a predictor that always predict Yo. and it always predicts O if the target function has zero mean) always has estimated degree of freedom of 0.
In Figure 3(h)(), we take the minimum MSE over different choices of A, and plot the average over 10 runs. Due optimization issue, sometimes the neural networks stuck bad local minima and the empirical loss is larger than the global minimum by orders of magnitude. To deal with this problem, in Figure 3())(), we manually detect these results by removing the experiments where the MSE is larger than 1.5 times the average MSE under the same setting, and remove them before computing the average.
H.4 MORE EXPERIMENTAL RESULTS
H.4.1 REGULARIZATION WEIGHT VS SEGRRE--OF-REEDDEE
As we explained in the previous section, the degree of freedom is the exact information-theoree measure of the generalization gap. A Larger degree-of offree-of-fiee offffreeom implies more overfitting.
320
100
250
233
1.00
100
25-
90-
0-
12
(a)
(b)
250
530
230
430
Dipre Booken.
Drqree Beoder.
130
10:43
12
10
22
30
20
10.7
12:4
164
(d)
Figure 4: The relationship between degree of freedom and the scaling factor of the regularizer A. The solid line shows the result after denoising. (a)(b)in parallel NN. (c) In trend filtering. (a)(c): the "vary" function. (b) the doppler function.
In figure Figure 4, we show the relationship between the estimated degree of freedom and the scaling factor of the regularizer X in parallel neural network and in trend filtering. As is shown in the
33

---

Published as a conference paper at ICLR 2023
arger Lundis
(c)
Tront Stries
Weeke dwss
(d)
Figure 5: More experiments results of Doppler function.
redweric
denelann
Obemmatce
Oustratton
-52
13
(a)
(b)
12
Faation
244
(d)
(e)
Figure 6: More experiments results of the "vary" function.
figure, generally speaking as X decreases towards 0, the degree of freedom should increase too. However, for parallel neural networks, if À is very close to 0. the estimated degree of freedom will not increase although the degree of freedom much smaller than the number parameters actually even smaller than the number of subnetworks. Instead, it actually decreases little. This effect has not been observed in other nonparametic regression methods, c.g. trend filtering, which overfits every noisy datapoint perfectly when À + O. But for the neural networks, not regularize at all, the among of overfitting is still relatively mild 30 30/256 vs 80/ 00/1000, our experiments using neural networks, when À is small, denoise the estimated degree of freedom using isotonic regression.
if we do
of this curious observation. Our hypothesis is that it might be related to issues with optimization, i.e., the optimizer ends up at a local minimum that generalizes better than a global minimum; it could be connected to the "double descent" behavior of DNN (Nakkiran et al., 2021) under wwee-paraatttrzzation...
We do not know the exact
H.4.2 DETAILED NUMERICAL. RESULTS
In order to allow the readers to view our result in detail, we plot the numerical experiment results of each method separately in Figure 5 and Figure 6.
34

---

Published as a conference paper at ICLR 2023
H.4.3 PRACTICAL EQUIVALENCE BETWEEN THE WEIGHT-DECAYED TWO-LAYER NN AND LI-TREND FILTERING
In this section we investigate the equivalence of two-layer NN and the locally adaptive regression splines from Section B. In the special case when m 1 the special regularization reduces weight decay and the non- non-standard truncated power activation becomes ReLU. We compare L1 trend filter- ing (Kim al., 2009) (shown be equivalent to locally adaptive regression splines by Tibshirani (2014)) and an overparameterized version of the neural network for all regularization parameter i.e., a regularization path. The results are shown Figure 7. It is clear that as the weight decay increases, it induces sparsity in the number of knots it selects similarly to LI-Trene Filtering, and the regularization path matches up nearly perfectly even though NNs are also learning knots locations.
130
wodptthccay
wegp1 dacay
wey dacy
5.05
wwwprddecy
wagg1 dacay 007
welght dicayy 1.00
-375
-0.30
1.75
-232
222
0.00
025
0.50
0.75
1.00
0.002
0.304
0.006
0.003
0.112
weEgh decsy
1.40
0.3
Tnstero 1833
knnce +
0.75
knnze
0.50
0.25
0.20
0.00
Lrroco 7779
025
benzc 42
-0.35
-0.10
6.1
11.00
1.00
Figure 7: Comparison of the weight decayed ReLU neural networks (Top row) and L1 Trend Filtering (Bottom row) with different regularization parameters. The left column shows the fitted functions and the right column shows the regularization path (in the flavor of Friedman et al. (2010) of the coefficients of the truncated power basis individual data points (the free-knot learned by NN are snapped to the nearest input to be comparable).
35


Reviews:
[{"review_id": "b9IG_Hd9mS", "reviewer": "Reviewer_UB7m", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper examines training a specific neural network (namely parallel neural net) using weight decay and shows that the error rate matches the minimax bound for a specific class of functions (i.e., functions with bounded variation). \n\nIt looks like a quite interesting effort and the result also appears to be significant. But I worry the paper is not presented at the level for general audience in ICLR. For example, I have a few questions/confusions after reading the submission: \n\n1. What exactly is weight decay? I actually could not find its definition/elaboration except for eq. 2, which is just L2 regularization? I was guessing it could relate to learning rate, momentum, some dynamic shrinkage on the fly...\n2. Do we assume that Eq.2 can be optimally solved? It is a minimax result related to sample complexity so I believe the authors assume that Eq. can be optimally solved --- I think sometimes ignoring computational tractability is fine (and perhaps had been a standard practice in statistics) but it would be helpful to bring this upfront. \n3. What's so special about parallel NN? I think most audience wants to understand at a higher level where the magic happens and why the magic wont happen for the standard MLP, e.g., only limit of existing theoretical tools or parallel NN possesses some special structure? \n----\nThank you for addressing the presentation concern. I have raised my scores to 6 -- do not feel am an expert in this area so no confidence to move to 7. \n\n\n\n", "summary_of_the_review": "I think the substance is above the bar of ICLR; the revision addressed my presentation concern. ", "strength_and_weaknesses": "Strength: The authors can show that a specific kind of neural net achieves minimax rate for an interesting function family. Some of the techniques appear to be significant (e.g., hacking into covering numbers). \n\nWeakness: there is room for improvement in presentation. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X2z4YR6hdwK", "reviewer": "Reviewer_ikZk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper extends Suzuki’s work (ICLR2018) to parallel neural networks in the Besov space as well as BV functions, studies the generalization properties in terms of approximation error via B-spline basis and estimation error via covering number, and demonstrates the $\\ell_2$ norm (weight decay) in parallel ReLU neural networks is equivalent to a certain sparse regularization term.\n", "summary_of_the_review": "This work has some good results on the sparsity, the separation between linear estimators and DNNs in Besov spaces as well as BV functions. Nevertheless, the derived results appear vacuous in terms of imprecise Lagrangian dual and curse of dimensionality of the input dimension. \n", "strength_and_weaknesses": "\n**Pros:** \n\n1. This work allows for over-parameterization without the extra sparsity condition\nThe obtained bound of the covering number is independent of the number of subnetworks, which is substituted by the Frobenius norm.  \n\n**Cons:**\n \n1. The motivation on locally adaptivity makes sense, comparing linear estimators and DNNs. Nevertheless, the motivation on the comparison of (Suzuki ICLR2019)  is relatively weak. The authors claim that Suzuki’s work requires certain conditions on the width, the depth, the sparsity to achieve the minimax rate on deep ReLU networks, which is different from practical uses. Nevertheless, this work does not focus on this issue but centers around another architecture, i.e., parallel neural networks. Even though parallel neural networks have theoretical and empirical applications as the authors suggested, the “correct” motivation is to solve certain conditions in Suzuki’s work under the same architecture.\n\nMore importantly, this work also requires several conditions on the width, the depth, etc. In the “No architecture tuning” part, the required architecture of the model still depends on $\\alpha$, see Theorem 1. It is hard for me to accept the authors’ motivation.\n\n\n2. In theorem 1, the number of subnetworks is exponentially large enough w.r.t the input dimension $d$. This is unacceptable in both theory and practice.\n\n\n3. In Proposition 4, the equivalence between Eq. (2) and Eq. (12) is imprecise via the Lagrangian’s method in optimization. The constraint value P doesn't appear in Eq. (2) and it is also not clear how the dual variable is handled. In fact P (as well as P’) is unknown or uncomputable, which also makes the upper bound of the covering number appear infeasible in Theorem 5 depending on P’. It is ok for ease of description but is not rigorous in a theory paper corresponding to the first contribution.\n\n4. After reading this paper, I think the technical contribution is to derive the covering number bound of the parallel neural networks for the estimation error, i.e., Theorem 5 and Lemma 6. The proof for approximation error follows Yarotsky (2017); Suzuki (2018). However, this paper works under a fixed design, which is much easier to derive the estimation error.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CYiRC0glX8", "reviewer": "Reviewer_YNWp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to analyze the theory of deep neural network from the perspective of non-parametric regression. The authors show that training an $L$ layer neural network with weight decay is basically the same as penalized regression. And in the case of functions in the Besov space and bounded variation space, neural networks achieves almost near-optimal rates. When the number of layers increase, the error decreases and thus explains why deep networks performs better than shallow ones. The authors also validate some of their claims using experiments.", "summary_of_the_review": "Overall, this seems to be a good paper with nice contributions. However, I am confused by some settings and theoretical results of the authors. Again, I am no expert in this field, and if there is anything wrong in my review, please correct me and I am happy to increase my score.", "strength_and_weaknesses": "Strength:\n  1. The paper is well-written and mostly clear.\n  2. The theoretical analysis provided by the authors are, as far as I am aware of, novel and interesting.\n  3. The obtained results do provide some insights on, for example, why deep networks do no overfit and why deep networks perform better than shallow networks.\n\nWeaknesses:\n  \n First off, I want to say that I am very new to the area of non-parametric regression and the function spaces the authors use in this paper. I have some experience with deep learning theory but this direction is completely new to me. Therefore, I might not be the best reviewer for this paper. Some of my comments might be unfair/wrong and I hope the authors and the other reviewers can help me understand this paper a little more during the discussion period. \n\n  Now back to this paper, I do have some questions about the setting and the results the authors provide. \n  \n  1. The authors have chosen to optimize a set of parallel feedforward networks with $L_2$ regularization (I don't really like using the word \"weight decay\" here because there is no mentioning of the optimizer, e.g. SGD/Adam, and thus weight decay does not really exist). I wonder why the authors didn't include the regularization for the bias in Eqn. (2)? After looking at the Appendix, I think the authors do analyze the network with the bias term, so why is the regularization for bias missing? I think in practice, people have both regularization for weights and bias.\n\n  2. In Theorem 1, I am confused by the statement \"with proper choice of the parameter of weight decay $\\lambda$\". How large does the parameter need to be? Does it need to be time-varying, for example? If the choice of $\\lambda$ needs to depend on the other parameters such as $M, L, p, q$, please state it explicitly in the theorems so that we can understand it more clearly.\n  \n  3. I am a little confused by the results in Corollary 2 and 3. For example, in Cor 2, although the $o(1)$ term is negligible, does it mean that the rate of deep neural network is worse than that of traditional nonparametric regression models? Are there models that can achieve the minimax rates that the authors have state Page 3? I think it might be better to have a table to compare the results in this paper with the results in the literature. Also, what is going to happen if $L > 100 C \\log n$? For very deep neural networks, do the theorems still hold?\n\n  4. For Cor 3, although I know that most of the paper is focused on $L\\gg 2$, the authors might want to mention that the results here fail for $L=1, 2$. Also, the claim that \"DNN has an advantage over kernels\" is a little confusing, shouldn't there be an assumption on $L$ (L> some function of m) so that the bound for DNN is strictly better than that of kernels? I hope the authors can state it more clearly.\n\n  I do not have enough time to go through all the proof details, but the proof overview section does give me enough intuition of how the theorems are derived. The experimental results are a good supplement to the theory.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A4eBv7FSV6", "reviewer": "Reviewer_wKTh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes parallel neural networks for nonparametric regression (including approximation error and regression error analysis). Suppose the regression function has nonhomogeneous regularities, e.g., Besov functions or functions of bounded variation. Parallel neural networks trained with weight decay achieves near optimal estimation, indicating the adaptability of parallel neural networks.", "summary_of_the_review": "I think the paper is interesting. I am currently giving a slightly negative rating, due to some concerns of the results and missing references. I am happy to raise to a positive rating after paper revision and an effective author feedback.", "strength_and_weaknesses": "============= Strength =============\n\nThe paper is clearly written with both theoretical and empirical results. The theoretical results are correct and empirical results are supportive.\n\nThe adaptability of neural networks is studied in many recent works, including its adaptability to data geometry and adaptability to structures in function spaces. This paper considers parallel neural networks and uses weight decay for controlling the complexity of the network, which circumvents sparsity constraints in many existing network approximation results.\n\n============= Weakness =============\n\nThere is no related work section. Some of papers share similar ideas to parallel neural networks, for example, \"Approximation and Non-parametric Estimation of ResNet-type Convolutional Neural Networks\" and \"Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks\" both rely on implementing block sparse feedforward networks. The resulting (residual) convolutional network does not need a sparsity constraint in training.\n\nThe obtained rate of estimation is slightly slower than the optimal rate, which is attainable (up to log factors) in many recent works on using ReLU neural networks for nonparametric regression.\n\nFrom experiments, parallel neural networks seem to achieve comparable performance to neural networks and conventional methods.\n  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster