Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?
Authors: Kaiqi Zhang
Yu-Xiang Wang
Venue: NeurIPS 2022 Submitted (2022)
Keywords: neural network
nonparametric regression
local adaptivity

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 \emph{adaptively} estimate functions with \emph{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 $\ell_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.

Deep Learning meets Nonparametric Regression: Are Weight-Decayed DNNs Locally Adaptive?
Anonymous Author(s)
Affiliation
Address
email
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 sizes. We consider "Parallel NN" variant of deep ReLU networks and show that standard weight decay is equivalent to promoting the sp-sparitt (0 p 1) of the coefficient vector of an end-to-end learned function bases, i.c., a dictionary. Using this equiv- alence, 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 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
8
10
12
13
Introduction
15 Why deep neural networks (DNNs) work better? They are universal function approximators [6, but splines and kernels. They learn data-driven representations, but the shallower and 17 linear counterparts such as matrix factorization. There surprisingly little theoretical understanding on why DNNs superior to these classical alternatives.
19 In this paper, we study DNNs in nonparametric regression problems - a classical branch statis- tical theory and methods with more than half century of associated literature [25]
20
46
10
23 37
21
33 Nonparametric regression addresses the following fundamental problem:
22
Let f(x;) + Noise for = 1,..., n. How can we estimate a function f using data points (1), (In, yn.) in conjunction with the knowledge that belongs function class F?
23
24
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.
26 Local adaptivity. subset nonparametric regression techniques were shown to have the property of local adaptivity 24 in both theory and practice. These include wavelet smoothing [TO] locally
27
28 adaptive regression splines (4), trend filtering 40 47 and adaptive local polynomials
We
29 say nonparametric regression technique is locally adaptive if it can cater to local differences in
30 smoothness, hence allowing more accurate estimation of functions with varying smoothness and
abrupt changes.
32 In light of such distinction, is natural to consider the following question.
33
Are NNs locally adaptive, i.e., optimal in learning functions with heterogeneous smoothness?
34
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

35
This is timely question to ask, partly because the bulk of recent theory of NN leverages its asymp- totic Reproducing Kernel Hilbert Space (RKHS) the overparameterized regime [21 S. RKHS- based approaches, e.g., kernel ridge regression with any fixed kernels are suboptimal in estimating functions with heterogeneous smoothness 19]. Therefore, existing deep learning theory based on
36
37
38
RKHS does not satisfactorily explain the advantages of neural networks over kernel methods.
39
40
We build upon the recent work of Suzuki [39] and Parhi and Nowak [29] who provided encouraging
41
first answers to the question above about the local adaptivity of NNs. Specifically, Parhi and Nowak
42
Theorem 8] showed that two-layer truncated power function activated neural network with a non-standard regularization is equivalent to the locally adaptive regression splines (LARS) (24). This connection implies that such non- standard NNs achieve the minimax rate for the (higher order) bounded variation (BV) classes. We provide detailed discussion about this work in Section B Suzuki [39] showed that multilayer ReLU DNNs can achieve minimax rate for the Besov class, but requires the width, depth and an artificially imposed sparsity-level of the DNN weights to be carefully calibrated according to parameters of the Besov class, thus quite different from how
29
43
44
45
46
47
48
19
DNNs are typically trained in practice.
50 In this paper, we aim addressing the same locally adaptivity question for a more commonly used neural network with standard weight decayed training.
51
Parallel neural networks. We restrict attention a special network architecture called parallel neural network [8,13] which learns an ensemble of subnetworks - each being a multilayer ReLU
53
DNNs. Parallel NNs have been shown to be more well-hehaved both theoretically [8 51 16
15
14
55
and empirically 50 44 Moreover, the idea of parallel NNs was used in many successful NN architectures such SqueezeNet, ResNext and Inception (see (15) and the references therein).
57 Weight decay. Weight decay is a common method in deep learning to reduce overfitting. Em- pirically, the regularizer is not necessarily explicit. Many tricks in deep learning, including early stopping [48, quantization [20), and dropout 455 have similar effect as weight decay. In this paper, make no assumption the training method thus there is (implicit) regularizers apart from weight decay.
59
61
62 S Summary of results. Our main contributions are:
63
We prove that the (standard) weight decay in training an I-layer parallel U-actvivveeted neural network is equivalent to sparse lp penalty term (where p 2/ on the linear coefficients of a learned representation.
65
66
2.
We show that neural networks can approximate B-spline basis functions of any order with- out the need of choosing the order parameter manually. In other words, neural networks can adapt to functions of different order of smoothness, and even functions with different smoothness in different regions in their domain.
87
68
89
70
3.
We show that the estimation error of weight decayed parallel ReLU neural network de- creases polynomially with the number of samples up to constant error for estimating functions with heterogeneous smoothness in the both BV and Besov classes, and the ex- ponential term in the етrоr rate is close to the minimax rate. Notably, the method requires tuning only the weight decay parameter.
71
72
74
75
4.
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.
76
The above results separate 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 ("weight decay" and ReLU activation) suffice for DNNs in achieving the optimal rates for estimating BV and Besov functions.
78
80
2
Preliminary
81
82
2.1
Notation and Problem Setup.
83 We denote regular font letters as scalars, bold lower case letters as vectors and bold upper case letters 84 as matrices. a S b means a S Ch for some constant that does not depend on b, and = b
85 denotes a I b and b. S a. See Table for the full list of symbols used.

---

Table Symbols used in this paper
symbol a/d a/a/A A
Meaning
scalars vectors matrices.
a. bj
Besov space.
[T]
{ar E N: S n).
mg.
Besov quasi-norm.
I
Frobenius norm.
Besov norm.
Ep y-norm.
Mm
th order Cardinal B-spline bases. mh order Cardinal B-spline basis function of resolution at position
d
Dimension of input.
Mm Mm.k.
M
# subnetworks in parallel NN.
L
layers in a (parallel) NN.
Width of subnetwork. samples.
of-)) w 600
ReLU activation function.
72
Weight and bias in the E-th layer in the j-th subnetwork.
IR, Z, N
Set of real numbers, integers, and nonnegative integers.
Let fo be the target function be estimated. The training dataset is Dn == {(x,, yr). y, fo 87 e,, i E [n]], where r; are fixed and are zero-mean independent Gaussian noises with variance ²².
86
88 In the following discussion, we assume æ; E [o, 1] fo E [-1, 1], Ví.
We will be comparing estimators under the mean square error (MSE), defined
MSE(F) == ED,
[(((a)) fo(x)))
1=1
The optimal worst-case MSE described by R(F) := miny max MSE(f), we say that is optimal if MSE(f) R(F). The empirical (square error) loss is defined î(f) = E (f(z)) - y.)?. The corresponding population loss is L(f) = El (f(x)) - 1/ where v new data points. It clear that E[L(f)] MSE[f] + o
89
90
91
93
2.2
Besov Spaces and Bound Variation Space
Besov space, denoted as Bo D.g" flexible function class parameterized by a, p. whose definition 95 is deferred to [Section C.I Here a 2 0 determines the smoothness of functions, 1 S S oo determines the averaging (quasi-) -norm over locations,
94
96
S сo determines the averaging (quasi- morm over scale which plays relatively minor role. Smaller p is more forgiving to inhomogeneity and loosely speaking, when the function domain is bounded, smaller p induces a larger function space. On the other hand, it is easy to see from definition that Bp.q C B if < < Without loss of generalizability, the following discussion we will only focus on B&
97
96
100
p.o0
When 1, the Besov space allows higher inhomogeneity, and it is more general than the Sobolev or Hölder space.
102
103
Bounded variation (BV) space is a more interpretable class functions with spatially hetero-
geneous smoothness 100]. It is defined through the total variation (TV) of function. For
105
m + 1)th differentiable function f [0, - RR the mth order total variation defined as TV (m)) = TV( (m)+)) = Jo.1 (f(m+ (x) dx, and the corresponding mth order Bounded
106
Variation class (Vm) = ( (V)(()) < oo). The more general definition is given in Sec-
107
tion C.2 Bounded variation class is tightly connected Besov classes. Specifically [8]:
B C (V C Bm+t1
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 On 2612) and O(n 10(n-(2m))) (2m+2)/(2m+3)) respectively The minimax rate for linear estimators in 1D BV classes is
known to be (2n-(mmm))((2m--m
24 10
3 Main Results: Parallel ReLU DNNs
114 Consider parallel neural network containing M multi layer perceptrons (MLP) with ReLU activa- tion functions called subnetworks. Each subnetwork has width and depth L. The input is fed to

---

W
0
Block diagonal weights
W(L)
W
W
OM
(
W
W
000
W Wil
W
W
000
O00
O00
M
W
W
W
QQQ
W
W
m LOΣ, ()) + + Σnك [W
| 1
min ( L(, azS1) s.t. En- lay 2/L S P..
(b) Sparse Regression with Learned Representation Figure I: Parallel neural network and the equivalent sparse regression model we discovered.
(a) Parallel NN with Weight Decay
all the subnetworks, and the output of the parallel NN is the summation of the output of each sub- 117 network. The architecture of a parallel neural network shown in Figure la This parallel neural
network is equivalent to vanilla neural network with block diagonal weights all but the first and
119 the last layers (Figure ()). Let w and b(t) denote the weight and bias the l-th layer in the
j-th subnetwork respectively. Training this model with weight decay returns:
M
arg min i(f)
(2)
( b
f=1==1
where f(z) ESe (z) denotes the parallel neural network, fz(+) denotes the j-th subnetwork, and À 0 a fixed scaling factor.
121
122
123
124
Theorem 1. For any fixed a a a 1, 1.921.222 1. 3. for any fo B given an L-layer parallel neural network satisfying
125
The width of each subnetwork fixed and large enough: 2 d. See Theorem 9 for the detail.
127
The number of subnetworks is large enough: M Z m b where m aa 1).
128
With proper choice of the parameter of weight decay X, the solution J parameterized by 2 satisfies
129
130
20/411-2/2) MSE()) Ō Iu/441
Const.
where Ô shows the scale up to a logarithmic factor, and the trailing constant term decreases expo- nentially with L.
131
133
We explain the proof idea in the next section, but defer the extended form of the theorem and the full proof to SSeciion F Before that, we comment on few interesting aspects of the result.
134
135
Near optimal rates and the effect of depth. The first term in the MSE bound the estimation error and the second term is (part of) the approximation error of this NN. Recall that the minimax rate of
136
a Besov class is O(n 2o++a) thus as the depth parameter L increases it can get arbitrarily close to the minimax rate. The constant term would be negligible if we choose L Z logn. n.
138
Corollary 2. Under the conditions of Theorem 7 for any fo E B8 there is numerical constant such that when we choose C Clog n & L S 100C log n, MSE(f) Ö(n sald a (1-o())))
where Ô hides only logarithmic factors and the of o(1) factor in the exponent is O(1/ log(n)).

---

140
This result says that deeper parallel neural networks achieves lower error and gets closer to the statistical limit.
141
142
Overparameterization and sparsity. We also note that the result does not depend on M as long M is large enough. This means that the neural network can be arbitrarily overparameterized while not overfitting. The underlying reason is sparsity. As it will become clearer in the proof sketch, weight decayed training of parallel L-layer ReLU NNs is equivalent to a sparse regression problem with an lp penalty assigned to the coefficient vector of learned dictionary. Here = 2 which promotes even sparser solutions than an l penalty.
143
144
145
146
147
148
No architecture tuning, For any fixed L, the required architecture of the model does not depend on the dataset or the target function (n2, a)) expect the number of subnetworks M, for which the only requirement is being large enough. As a result, one can design a model using a large guess on M, and achieve the claimed near-optimal error rate by only tuning the weight decay parameter.
150
152
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.
154
Corollary& 3. If the target function in bounded variation class fo E BV (m). For any fixed L 2 3, for a neural network satisfying the requirements in Theorem 1 with d = 1 and with proper choice of the parameter of weight decay X, the NN parameterized by (5) satisfies
155
156
MSF(f) = Ö(nn
(2m 12:11 2/L)
2m 276
Const.
where Ô shows the scale up logarithmic and the trailing constant term decreases expo- nentially with L.
158
159
is known that any linear estimators such as kernel smoothing and smoothing splines cannot have an error lower than On (2m++12mm/ for (mm) I0]. This partly explains the advantage of DNNs over kernels.
160
162
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 (29]. which achieves the minimax rate of (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 I. to be sufficiently large, such Parallel NN with optimally tuned simultaneously
163
164
186
optimal for m 1,2, 3, .... In fact, even if different regions of the space has different orders of smoothness, the paralle NN will still be able to learn 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.
168
170
171
Synthesis v.s. 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 on constructing appropriate basis functions to encode the contemplated structures and regress the data to such basis, e.g., wavelets [0O. The other is called analyvis framework which uses analysis regularization on the data directly (see, e.g., RKHS methods 37 or trend filtering 40). appears to us that parallel NN is doing both simultaneously. It has a parametric family capable to synthesizing (nn) subset of an exponentially large family of basis, then implicitly use sparsity-inducin analysis regularization to 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.
172
174
175
176
178
180
Proof Overview
181
182
We start by first proving that a parallel neural network trained with weight decay is equivalent to an l, -pasee regression problem with representation learning (Section 4.1); which helps decompose its
183
184
MSE into an estimation error and approxmation error. Then we bound the two terms in SSSectiion 4.2 and Section 4.3 respectively.
185
4.1
Equivalence to Ep Sparse Regression with a Learned Feature Representation
187
is widely known that ReLU function 1-homogeneous: (ar) (z)) Va 2 0. E R. any consecutive two layers in neural network (or subnetwork), one can multiply the weight and bias
5

---

189
in one layer with positive constant, and divide the weight in another layer with the same constant. The neural network after such transformation equivalent to the original one:
190
o ((1) 2w o(w(() cb Vc 0, x.
(4)
191
This property allows us reformulate
to an Ep sparsity constraint problem:
192
Proposition 4. Fix the input dataset D, n and a constant e₁ > There exists an one-to-one mapping
between À >> O and Pt >> such that (2)
is equivalent to the following problem:
M {(
arg min (w.) F80 aa)
I
E(i: y ax)
j=1
(5)
s.t. [ S a.vd [M).
W |l S sav Vj M 1Ka,H S
where (-(-) is subnetwork with parameters
w D00
185
This equivalent model is demonstated in Figure Tb constraint | ||F S vd. [ V ve > 1 is typical in deep learning for better numerical stability. The equivalent model in Proposition i also a parallel neural network, but it appends one layer with parameters }ax} at the end of the neural network and the constraint
The proof can be found in Section D.1 The
197
the Frobenius norm converted to the 2/L norm on the factors {ax} Since L >>>>> 2 in a typical application,
199
2/L L < and this constraint can enforce sparser model than that in Section B
201
There are two useful implications of Proposition First, gives an intuitive explanation on how a weight decayed Parallel NN works. Specifically, it can be viewed as a sparse linear regression with representation learning. Second, the conversion into the constrained form allows us to adapt generic statistical learning machinery (a self-bounding argument) from Suzuki [39 Proposition 4] for studying this constrained ERM problem.
203
205
206
The adaptation is nontrivial because (1) our regression problem has a fixed design (so data points are iid); (2) there is an inconstrained subspace with bounded metric entropy. Specifically, our Proposition 15 shows that the MSE of the regression problem can be bounded by
207
208
MSE(A =o inf MSE(J) FEF
log (FF 6, (1l0) d(F1)
approximation error
estimation error
209 in which F decomposes into Fi xF1,, where F1 is an unconstrained subspace with finite dimension, and Fi is a compact set in the orthogonal complement with d-covering number of A [FFi, 6, || (loa) 211 in -norm. This decomposes MSE into an approximation errorand an estimation error. The novel analysis of these two represents the major technical contribution of this paper.
210
213
4.2
Estimation Error Analysis
214
The decomposition above reveals that to bound the estimation error, it suffices to compute the cov- ering number of the constraint set in the sup-norm of the function represents.
215
216
Previous results that bound the covering number of neural networks 49 39 depends on the width
217
of the neural networks explicitly, which cannot be applied when analysing potentially infinitely wide neural network. In this section, we leverage the εy-norm bounded coefficients to avoid the dependence in M in the covering number bound.
218
219
220
Theorem 5. The covering number of the model defined in (5) apart from the bias in the last layer satisfies
221
2/L logN((FF)) S w (2+2/11-2/1)) 122 b 272 log(wP'/0)
(6)
The proof can be found in Section D.2 It requires the following lemma:

---

223
Lemma 6. logN(G, & k (1/8( for some finite and for any 9 E g, la S 1, we have
224 ag E G. The covering number of F = - a:th 9i E و | < P,O < < for any P > 0
225
satisfies
logNN(F,c) (PP-
log(c3P/0)
226
up to double logarithmic factor.
227
See Section D.3) for the proof of Lemma 6 The covering number in Theorem 5 does not depend on the number of subnetworks M. In other words, provides bound of estimation error for an arbitrarily wide parallel neural network as long as the total Frobenius norm is bounded.
228
230
4.3
Approximation Error Analysis
The approximation error analysis involves two steps. In Section 4.3.1, we analyse how a subnetwork can approximate a B-spline basis. Then in |Section 4.3.2) we show that sparse linear combination of B-spline bases approximates Besov functions. Both add up the total error in approximating
232
233
234
Besov functions with parallel neural network (Theorem 9).
235
4.3.1
Approximation Error of B-spline Basis Function
236
functions in Besov space can be alternatively represented in a sequence space via the coefficients of cardinal B-spline basis. In this section we study the approximation ability of ReLU neural networks B-spline basis function.
As is shown in Section C.I
237
Proposition 7. Let Mm,k, be the B B-spline of order with scale 2 in each dimension and position 238
IR: a == Mm (2 (xx 8)), Mm. is defined in (11) There exists a parallel neural network that has the structure and satisfy the constraint in Proposition 4 d-dimensional input and one outpur, containing M O(m²) subnetworks, each of which has width w = O(d) and depth L OOlog(c(m, d)/c)) for some constant w, c that depends only on m and d, denoted as M (x) x E RRd,, such that
241
243
244
(m) Mm,k, (x)) S if0 2* - st) sm+ -c)
245
248
Mm.k.o = O, otherwise.
The weights in the last layer satisfy ||al 101l//2 & e
2md/
248
The proof can be found in Section E. Note that the product of the coefficients among all the layers are proportional to 2h, instead of 2 when approximating truncated power basis functions. This is because the transformation from Mn, to Mm..k. only scales the domain of the function by 2*, while the codomain of the function is not changed. To apply the transformation to the neural network, one only need to scale weights in the first layer by 2*, which equivalent to scaling the weights in each layer bt / and adjusting the bias according.
249
250
251
252
253
254
4.3.2
Approximation Error in Besov Space
255
With the results given in Section 4.3. we can estimate the approximation error of parallel ReLU neural networks to functions in Besov space.
256
Proposition 8. Let d/p > 1,r > 0. For any function in Besov space fo E Bg and any positive integer M, there is an M M-sparse approximation using B B-spline basis of order m satisfying 0 < < min(m, m - 1/p): J = M 0k,,s; Mm,,,, for any positive integer M such that the approximation error is bounded as
Ilf foll- S M [|ooll and the coefficients satisfy
11 ak..s Iku.e 1p S fl
The proof can be found in Section E.2
Remark 1. The requirement in Proposition 8 - d/p > 1 is stronger than the condition typically
280
found in approximation theorem a d/p 2 [77,, so-called "Boundary of continuity", or the
condition in Suzuki [39] d(1/p- 1/r)+ This is because although the functions in B when
7

---

0 a < 1 can be approximated by B-spline basis, the sum of weighted coefficients may not 282
263
converge. One simple example is the step function faep(a) 1(x 2 2.5), E Bi. Although it can be decomposed using first order B-spline basis as in [10] the summation of the coefficients is infinite. Actually one only needs a ReL.U neural network with one hidden layer and two neurons to
264
265
266
approximate this function to arbitrary precision, but the weight need to go to infinity.
267
Theorem 9. Under the same condition as Proposition 8 for any positive integer M, any function
288
in Besov space fo E Bp-g can be approximated by a parallel neural network with no less than (m M) number of subnetworks satisfying:
270
1. Each subnetwork has width w = (d) and depth L.
2. The weights in each layer satisfy || 1W&ll 2 S O(vw) except the first layer II O(Vd).
IIe S
271
272
273
3. The scaling factors have bounded 2/ L-norm:
[[a3311211 2/1, & mm M1
4. The approximation error is bounded by I fflll- S (c/ + ege
275
where C4, C5 Cg are constants that depend only on m, d and p.
276
Here M is the number of "active" subnetworks, which is not to be confused with the number of subnetworks at initialization. The proof can be found in [Section E.3
Using the estimation error in Theorem 5 and approximation error in Theorem 9| by choosing MM to minimax the total error, we can conclude the sample complexity of parallel neural networks using weight decay, which is the main result (Theorem Ib of this paper. See Sce|Section F for the detail.
278
279
280
Experiment
281
282
We empirically compare a parallel neural network (PNN) and a vanilla ReLU neural network (NN) with smoothing spline. trend filtering (TF) [40]. and wavelet denoising. Trend filtering can be
283
284
viewed as 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 be minimax-optimal for
285
286
the BV classes. The results are shown in Figure 2 We use two target functions: a Doppler function whose frequency is decreasing(Figure 2 a))(c)), and a combination of piecewise linear function and piecewise cubic function, or "vvry" function (Figure 2f))-(f). We repeat each experiment 10 times and take the average. The shallow area in Figure ((b) shows 95% confidence interval by inverting the Wald's test. The degree of freedom (Dof) is computed based on Tibshirani 41
287
288
289
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 in (g)). The prediction of PNN is similar to
292
293
294
TF 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
295
296
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 of-eredoom than smoothing splines.
297
298
In a vanilla NN, weight decay is equivalent to l regularizer in any two successive layers, but to the best of our knowledge it does not lead to sparse representation learning unless some specific sparse structure is enforced. While our theory does not apply to vanilla neural networks, the results seem
289
300
301
to suggest the NN behaves similar smoothing spline and is not locally adaptive.
302
There are some mild drops in the best MSE one can achieve with NN vs TF in both examples. We surprised that the drop is small because NN needs to learn the basis functions that TF essentially hard-coded. The additional price to pay for using a more adaptive and more flexible representation leamning method seems not high at all.
304
305
306
In Figure 2 (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 is much smaller than the initialization. This is because weight decay induces lp sparsity and the weight in most of the subnetworks reduces
308
towards 0 after training. More details are shown in Section G
8

---

Ctoervtice
Prrdee Seurs Netwert
ritwing
0.23
Seoothing Spline
05-
Sevotting "pite
Mixe Dreakinn
Bolld
0.15
10-
6:20
-45-
-100
Doggns of treson
(a) Dopler, DoF=30,
(b) MSE versus DoF.
(c) Active subnetworks.
Cosarvation
Rural Waaze Haoverc
Begas Waasiigg
Wanale: Dureanng
Smazthing Spinna
Band
3.6
Sesoutiing Splind
Mose Durcking
3.4
how inl lemurdk
6.
3.-
-32-
2/6
ide Lis
0.
Dayee of Seeverr
(d) "Vary", DoF=50.
(e) MSE versus DoF
(f) Active subnetworks.
31-
Trun' liter
Smoothing Soline
Trest Fiber
Smoothic Splin
100
015 0d5 050
Rumvee serples
(g) Zoom in to (a)(d)
(h) MSE versus n, Dopler
MSE versus n, "Vary"
Figure 2: Numerical experiment results of the Doppler function (a-c.h), and "vary" function (d-f.g). All the "active" subnetworks are plotted in (f). The horizontal axis in (b) is not linear.
In Figure ()) we plot the MSE versus the number of training samples for "Doppler" and "Vary" respectively. is 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/4), 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,
311
312
313
314
316
vanilla NN seems to converge at the optimal rate too on this example. remains an open question whether vanila NN is merely "lucky" on this example, or it also achieves the minimax rate for all functions in BV (m))
318
6
Conclusion and Discussion
320
In this paper, we show that a deep parallel neural network can be locally adaptive by tuning only the weight decay parameter. This confirms that neural networks can be nearly optimal in learning functions with heterogeneous smoothness which separates them from kernel methods. We prove that training an L layer parallel neural network with weight decay is equivalent to an fgyt-penalized regression model with representation learning. Since in typical application L > 2, weight decay promotes 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 (B space. Our result reveals that one do not need to specify the smoothness parameter
321
322
323
324
325
326
328
(or m). Neural networks can adapt to different degree of smoothness, or choose different parameters for different regions of the domain of the target function. This is a new type of adaptivity not

---

330
possessed by traditional adaptive nonparametric regression methods like locally adaptive regression
331
spline or trend filtering
332
On the other hand, as the depth of neural network L. increases, 2/T. tends to and the error rate moves closer 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.
338
334
335
References
336
[1] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang- On exact computation with an infinitely wide neural net. In Proceedings of the 33rd Interna- tional Conference on Neural Information Processing Systems, pages 8141-8 $141-8150, 2019.
338
340
[2] Dheeraj Baby and Yu-Xiang Wang. Online forecasting of sanl--arraaion-buudeee sequences. In Neural Information Processing Systems (NeurIPS), 2019.
341
[3] Dheeraj Baby and Yu-Xiang Wang. Adaptive online estimation of piecewise polynomial trends. Neural Information Processing Systems (NeurIPS), 2020.
343
344
[4] Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Ma- chine learning, 14(1):115-13) 1994.
348
[5] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541- 549, PMLR, 2018.
347
348
349
[6] George Cybenko.
Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-311 1989.
350
[7] 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.
352
353
(8] Ronald A DeVore and George G Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
354
355
99]
David L Donoho, Richard Liu, and Brenda MacGibbon. Minimax risk over hyperrectangles, and implications. The Annals of Statistics, pages 1416-1437, 1990.
356
357
[10] David L Donoho, lain M Johnstone, et al. Minimax estimation via wavelet shrinkage. The annals of Statistics, 26(3):879-921, 1998.
358
359
[11] Dinh Düng. Optimal adaptive sampling recovery. Advances in Computational Mathematics, 34(1):1-41, 2011.
[12] Tolga Ergen and Mert Pilanei. Implicit convex regularizers of cnn architectures: Con- vex optimization of two-and three-layer networks in polynomial time. arXiv preprint arXiv:2006.15 147998 2020.
362
383
384
[13] Tolga Ergen and Mert Pilanci. Convex geometry and duality of over-parameterizer neural networks. Journal of machine learning research, 2021.
[14] Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu net- works via convex programs. In International Conference on Machine Learning, pages 2993- 3003. PMLR, 2021.
367
[15] Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regular- ization for parallel relu networks. arXiv preprint arXiv:2110.09548, 2021.
370
371
[16] Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex
duality. International Conference on Machine Learning, pages 3004-3014. PMLR, 2021. 372
373
[17] Jerome Friedman, Trevor Hastie, and Rob Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1,2011 2010.
374
10

---

375
[18] Benjamin D Haeffele and René Vidal. Global optimality in neural network training. In Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7331- 7339, 2017.
378
[19] Daniel Hsu, Sham M Kakade, and Tong Zhang. An analysis of random design linear regression. arXiv preprint arXiv: 106.2363. 2011.
379
380
[00] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran EI- Yanianiv, and Yoshua Bengio. Bina- rized neural networks. In Proceedings of the 30th international conference neural informa- tion processing systems, pages 41 14-4222. Citeseer, 2016.
382
383
[21] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: convergence and generalization in neural networks. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pages 8580-8589, 2018.
385
386
[22] Seung-Jean Kim, Kwangmoo Koh, Stephen Boyd, and Dimitry Gorinevsky. \ell_ trend fil- tering. SIAM review, -366660,,,, 2009.
387
388
[23] Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
[24] Enno Mammen and Sara van de Geer. Locally adaptive regression splines. The Annals of Statistics, 25(1):387-413, 1997.
380
[25] Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
392
393
[26]
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 Mechan- ics: Theory and Experiment. (021(12):22400,, 2021.
394
395
396
[27]
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614 2014.
397
398
[28] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. International Conference on Learning Representations, 2019.
399
[29]
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. J. Mach. Learn. Res., 22:43-1, 2021.
402
403
[30] Rahul Parhi and Robert Nowak. What kinds of functions do deep neural networks leam? insights from variational spline theory. arXiv preprint 2rX1v:2005.03361, 2021.
[31] Rahul Parhi and Robert D Nowak. Near-minimax optimal estimation with shallow relu neural networks. arXiv preprint wwXiv:2109008844 2021.
406
407
[32] Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial- time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pages 7695-7705. PMLR, 2020.
409
410
[33] Carl Edward Rasmussen and Christopher KI Williams. Gaussian processes for machine learn- ing. MIT Press. 2006.
411
412
[34]
Veeranjaneyulu Sadhanala, Yu- Yu-Xiang Wang, Addison J Hu, and Ryan Tibshirani. Multivari- ate trend filtering for lattice data. arXiv preprint 1rXiv:2112.1477 2021.
413
414
[35] 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, pages 2667-2690. PMLR, 2019.
415
416
417
[36] Johannes Schmidt-Hieber Nonparametric regression using deep neural networks with relu activation function. The Annals of Statistics, 48(4):1875-187,, 2020.
418
419
[37] Bernhard Scholkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.
11

---

421
[38] Nathan Srebro, Jason DM Rennie, and Tommi S Jaakkola. Maximum margin matrix factor- ization. NIPS, volume 17, pages 13361 Citeseer, 2004.
422
[39] Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse dimensionality. arXiv preprint arXiv: 181000803, 2018.
424
40)
Ryan J Tibshirani. Adaptive piecewise polynomial estimation via trend filtering. The Annals of Statistics, 42(1):288--22 2014.
426
[41] Ryan Tibshirani. Degrees of freedom and model search. Statistica Sinica, pages 1265-1296, 2015.
428
429
[42] Ryan J Tibshirami. Equivalences between sparse models and neural networks. 2021. URL attp://wwx. http://wwwsstttt www.sttat.oo cmu eeriiidddd"rrrra http:///aaaaatlaappppr////////// http://pppprrssppsst..... pdf
[43] Ryan Tibshirani. Personal communication, Jan. 24, 2022.
[44] Andreas Veit, Michael Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. Advances neural information processing systems, 29:5500
433
558, 2016.
435
[45] Stefan Wager, Sida Wang, and Perey Liang. Dropout training as adaptive regularization arXiv preprint 1rXiv:1307.1444 1493, 2013.
437
[46] Grace Wahba. Spline models for observational data, volume 59. Siam, 1990.
[47] Yu-Xiang Wang, Alex Smola, and Ryan Tibshirani. The falling factorial basis and its statistical applications. In International Conference on Machine Learning, pages 730-738. PMLR, 2014.
439
440
[48] Yuan Yao. Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-315 2007.
442
[49] Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94:103-114, 2017. ISSN 0893-6080. doi:
URI.
444
[50] Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
446
16Xiv:1605.07//4 11..:600.....6.62220 2016.
[51] 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, pages 1099-1109, PMLR, 2019.
448
449
Checklist
450
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
459
contributions and scope? [Yes]
454
(b) Did you describe the limitations of your work? [Yes] See Seccion 6
455
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work does not have potential negative societal impacts to the best of our knowledge.
456
457
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
458
459
2. If you are including theoretical results...
460
(a) Did you state full set of assumptions all theoretical results? [Yes]
461
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are in the appendix.
3. If you experiments...
12

---

484
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [No] Although we did not publish the code, the experiments are very simple and can be easily reproduced using the information given in [Section G
485
467
488
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See (eefSeetion Gj
489
470
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We provided the confidence interval in Figure 2 (d) Did you include the total amount of compute and the type of resources used (c.g., type GPUs, internal cluster, or cloud provider)? [No] The experiments are light- weighted and can be finished in ordinary PC in reasonable time.
473
475
4. If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
476
(a) If your work uses existing assets, did you cite the creators? [N/A] We only used synthetic dataset.
477
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
480
(d) Did you discuss whether and how consent was obtained from people whose data you'r re using/curating? [N/A]
482
483
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
484
5. If you used crowdsourcing conducted research with human subjects...
486
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
487
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
489
490
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13

---

A
Other related works
492
498
Besides Parhi and Nowak [29] which we discussed earlier, Parhi and Nowak 30 31 also leveraged the connections between NNs and splines. Parhi and Nowak [0) focused characterizing the variational form of multi- NN. Parhi and Nowak [31] showed that two-layer ReLU activated
485
486
NN achieves minimax rate for BV class of order but did not cover multilayer NNs nor BV class with order >> 1, which is our focus.
487
The connection between weight-decay regularization with sparsity-inducing penalties in two-layer NNs is folklore and used by Neyshabur et al. [27], Savarese et al. [35], Ongic et al. [28], Ergen and Pilanci [13 [6]. Parhi and Nowak (29 31I. Pilanci and Ergen [32.. The key underlying technique an application of the AM-GM inequality (which we used this paper as well) - can be traced back to Srebro et al. [88 (see recent exposition by Tibshirani 422 42) also generalized the result to multi-layered NÑs, but with a simple (element-wisg
499
501
503
connections. 14 generalized the results to three-layer parallel neural network, and proved its equivalence to & sparse model, but this requires a non-standard regularizer. Besides, [12] 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.
505
508
507
The approximation-theorriii and estimation thecoretcc research for neural network has long history too 6 49 36 39]. Most existing work considered the Holder, Sobolev spaces and their exten- sions, which contain only homogeneously smooth functions and cannot demonstrate the advantage of NNs over kernels. The only exception Suzuki (3) which, as we discussed earlier, requires modifications to NN architecture for each class. In contrast, require tuning only the standard weight decay parameter.
509
511
513
514
B
Two-layer Neural Network with Truncated Power Activation Functions
We start by recapping the result of Parhi and Nowak 29 and formalizing its implication in esti- mating BV functions. Parhi and Nowak [29] considered a two layer neural network with truncated power activation function. Let the neural network be
516
M
f(x) = Σ uj0 (wyx + by) + c(x),
1=1
518 where wy, denote the weight in the first and second layer respectively, b, denote the bias in the first layer, c(z) is polynomial of order up to m, 8²h (z) max(æ, 0)mh. Parhi and Nowak (29
520
Theorem 8] showed that when M is large enough, The optimization problem
X 2
min i() w.v
(00y) (
(8)
is equivalent to the locally adaptive regression spline:
min L() + (TV()(
(9)
f
522
which optimizes over arbitrary functions that is m-times weakly differentiable. The latter was
523
studied in Mammen and van de Geer (24). which leads to the following MSE:
Theorem 10. Ler M 2 n m. and f be the function (7) parameterized by the minimizer of B
524
525 then
MSE(f) = O(n (2m 2) (2m++3))
528
We show simpler proof in the univariate case due to Tibshirami 443
527
Proof. As is shown in Parhi and Nowak [29] Theorem 8], the minimizer of ( satisfy
|0yl
|wy| m7 Vk
14

---

528
so the TV of the neural network fNN is
M
TV(m) (JNN) TV c(ar)
>
1 (IT (x))
+
bg may mm
1 M
2 _ (lug 2 + | (2m)
529
which shown that (8)is equivalent to the locally adaptive regression (9) long as the number of knots in (9) is more than M. Furthermore, it is easy check that any spline with knots
more than M can be expressed as two layer neural network (8) It suffices to prove that the solution has no more than n m number of knots.
532
Mammen and van de Geer [24, Proposition 1J showed that there is solution to (9)
f(x) such that
(x) is a math order spline with a finite number of knots but did not give a bound. Let the number of
534
535
knots be M, we can represent using the truncated power basis
M
f(x) f(0)= = Ez t, c(x) = Eajof (mm) (x) c(z)
where to are the knots, c(x) is polynomial of order up to m, and define ((m) (z) (x tT
537
Mammen and van de Geer 24 however did not give a bound on M. Parhi and Nowak [29]'s 's
Theorem 1 implies that M <
Its proof is quite technical and applies more generally to higher dimensional generalization of the BV class.
539
Tibshirani 4 communicated to us the following elegant argument prove the same using elemen- tary convex analysis and linear algebra, which we present below.
541
Define (f) as the (2())) projection of onto polynomials of degree up to m, (1) =
542
mm (f). is easy to see that
543
fx) = Σ a (m) (x)
544
Denote f(11m) := (= ((, E R" as a vector of all the predictions at the sample points.
M
M
M
f(
Σ - (1m) (xIm) e conv ) (m)))) j=1
Σ j=1
|ayl =E conv (mm) (x1m)
> j=1
layl
where conv denotes the convex hull of a set. The convex hull conv (m) (x1m)) En layl is an n-dimensional space, and polynomials of order up to m is an m + dimensional space, the set 1. By Carathéodory's theorem, there is subset of points in
545
546
defined above has dimension
548
this space
(IT
(m) js (II=)) S (TT (Iim)),
(m)
m
such that 549
Σ Tz II m
(m) (x),
lapl S
other word, there exist a subset of knots {t,.j E [n m]} that perfectly recovers II fx) at all the sample points, and the TV of this function no larger than f.
550
551
This shows that
m2m
f(x) = E 0z t s.t f(x.)
15

---

552 for all 2; in n onbservation points.
The MSE of locally adaptivity regressive spline (9) was studied in Mammen and van de Geer
24
554
Section 3), which equals the error rate given in Theorem 10.
This indicates that the neural network 7 is minimax optimal for (m)).
Let us explain a few the key observations behind this equivalence. (a) The truncated power functions
(together with an mth order polynomial) spans the space of an mth order spline. (b) The neural
network in (7 equivalent to a free-knot spline with M knots (up to reparameterization).. (c) A solution to is spline with at most n knots 29
Theorem 8]. (d) Finally, by the AM-GM
inequality
by + |wy1 |uy122m 1 > 2/ | 2|cy1
556
where Cj Uy "y|ير|" 1M is the coefficient of the corresponding jth truncated power basis. The mth order total variation of a spline is equal to Σ, lcyl. It is not hard check that the loss function
557
558
depends only on cj. thus the optimal solution will always take "=" the AM-GM inequality.
C Introduction To Common Function Classes
560
In the following definition define Q be the domain of the function classes, which will be omitted in the definition.
561
582
C.1 Besov Class
563
Definition& 1. Modulus of smoothness: For function f E TP( for some 1 S S oc, the r-th
564
modulus of smoothness is defined by
Wr (f.
sup hE3*:1M/125t
(
A10)= Σ 1(x
if Q + rh 0
0,
otherwise.
Definition 2. Besov space: For 1 S p. 00, 0, [a] 1, define
U (t (f supt 120
dt )
q < 00
IflBg,
t
Wr (f,t),
9 = 00,
587
and define the norm of Besov space as:
IIfll Il + IflBp..
568
function f the Besov space B%, if [lf[l1 is finite.
589
Note that the Besov space for 0 < p.q q < is also defined, but in this case it is quasi-Banach space instead of Banach space and will not be covered in this paper.
570
571
Functions in Besov space can be decomposed using B-spline basis functions. Any function f in Besov space B d/p can be decomposed using B-spline of order m. m a: let Rd.
f(z)= = Σ
(10)
B=ONEJ(M
where J(k) {2-*s: E [- [-m, 2 +m]" 2d), M (z)) M2 ()), and M4(x))
[ M2, is the cardinal B B-spline basis function which can be expressed as a polynomial:
574
m+1
Mm(x)=
Σ 1-1)
+ j
(x -)
m!!
1=1
(11)
1
m + +11 ( x-j
= =(mm + 1)
(-133
(m++1)/2 1)/2
ml
j
16

---

575
Furthermore, the norm of Besov space is equivalent to the sequence norm:
1/2
KK Ilog.,
(aa ((c.o(())))l)))
Ilfllag.
0
576
See e.g. Düng
Theorem 2.2] for the proof.
577
The Besov space is closely connected to other function spaces including the Hölder space (C") and the Sobolev space (.) Specifically, the domain of the functions d-dimensional 39 34
578
579
Va E N. B C W p,o+ and 2 W."
For 0 < oc and a E &N B 80.00
580
a d/p, B CO.
582
C.2
Other Function Spaces
588
Definition 3. Hölder space: let E N, the m-th order Holder class is defined as
C -== s: max
D
f(æ) ) D" f(=)
< oc, Vx, EE
la|=k
x 2 2
where D denotes the weak derivative.
585
Note that fraction order of Hölder space can also be defined. For simplicity, we will not cover that
586 case in this paper.
Definition 4. Sobolev space: let E N,, Sp
the Sobolev norm is defined as
1/P
lfllum=
Σ fID
aa|Sm
588
the Sobolev space is the set of functions with finite Sobolev norm:
W := {f: Illll < c.).
Definition 5. Total Variation (TV): The total variation (TV) of a function f on an interval [a, b] is 590
defined as
np-11
TV()) sup Σ (5(0)1)) f(x:))
where the P is taken among all the partitions of the interval [a, b).
592
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
585
TV(m)() = ()(((-)))
596
Definition 7. Bounded variation (BV): The mh-th order bounded variation class is the set of functions
whose total variation (TV) is bounded.
BV (m))== = (. TV((() < <oc..
D Proof of Estimation Error
598
599
D.1
Equivalence Between Parallel Neural Networks and p-norm Penalized Problems
Fix the input dataset D, and constant e₁ > 0. There exists an one-to-one mapping between X and Pt such that (2) is equivalent to the following problem:
Proposition 4
601
M
arg min (W(9 B a5)
i
(
Σ n
(y: - az)
j=1
IW, (1) || < c vivd. [M].
s.t.
W S [M,2sesA.
11a < p
17

---

where f5(-) is a subnetwork with parameters W 6,²
602
Proof. Using Lagrange's method, one easily find
(2) is equivalent to constrained optimization
604
problem:
M
M
L
arg min i (W) "
f3
s.t.
14
(12)
605
for some constant that depends on and the dataset
606
We make use of the property from (4) to minimize the constraint term in (12) while keeping this
neural network equivalent to the original one. Specifically, let W(1), (1) W(L) ( be the parameters of an I--layer neural network.
608
((x) = w (W(L-)) o(.. (W(())
+b")..... ... ...)..))) +(b())))) t0)
which is equivalent to 609
W(1 oo....oaa W x b (1-11) +5
f(x) o..
610 as long ag > 0, IT a² = Th= // where W = W
w
By the AM-GM inequal-
ity, the &2 regularizer of the latter neural network is
L II
2/L
2/L
Σ la 10
Σ
a
ai
L
(II
612 and equality is reached when an = a2 az consider the network that satisfies
In other word, in the problem (2)
suffices to
I
||F
|
|F
|/ |r, Vj E [M] [4].
(13)
Using (4) again, find that the neural network is also equivalent to
M
f(z) Σ aj W(.
o(., + )..)
+ 111 6,²0)
j=1
615 where
IL W 10)
IF
| /
E 2 W 12//2)
I 3(0)
8(0 ,a,
(14)
(00)
300)
IT ,00)
616
where the last two equality comes from the assumption (13) Choosing g(()
C1 w expect /
where ((1) c1 vd. and scaling (0) accordingly and taking the constraint (12) into (14) finishes the proof.
617
619
D.2
Covering Number of Parallel Neural Networks
620
Theorem 5] The covering number of the model defined in (5) apart from the bias in the last layer satisfies
log (og,N(F8)) S 22+2/(1-21D) 12 /ap' - 8 - bg(wP' /8).
The proof relies on the covering number each subnetwork in a parallel neural network Lemma 11), observing that [s(z) < - under the condition in Lemma 11, and then apply Lemma 6. We argue that our choice of condition on ||6())|2 in Lemma 11 is suf- ficient to analyzing the model apart from the bias in the last layer, because it guarantees that
((() A = [|22 This leads
Ac I (| Ae s Vollb/0122 S (10
18

---

623 If this condition is not met, Ac- - b(e) is either always positive or always negative
624 for all feasible x along at least one dimension. If (W(()) + 6(9); is always negative,
625 one can replace b(O); )5 with max A without changing the output of this model 628 for any feasible æ. If (e- + b(0); is always positive, one can replace b(O),, with maxe ( (2))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, one replace the bias ( with another one with smaller norm while keeping the model equivalent except the bias in the last layer.
627
629
Lemma 11. Let F S {f: : Rd + RR denote the set of L-layer neural network (or subnetwork in parallel neural network) with width in each hidden layen. It has the form
630
f(x) = w (W(1-1) (.....(W()) +b"))..... ++(+)++111) +b(L)
w R | vd ER, 18,11611122 Vdw,
( E B" | P S Vū, (0) v
E ER" (0)) 122 s 2 dw, Ve= 1-1,,
W RIxE || S Vw, b()
(15)
632 and (.) is the ReL. activation function, the input satisfy ||||| S 1, then the supremum norm
633 5-covering number of F obeys
logN((F,) 8) S L2 log((/0) + cs
where CT is a constant depending only on d, and cs is constant that depend on d, w and L. 634
635
Proof. First study two neural networks which differ by only one layer. Let ge, g' be two neural net- works satisfying (15) with parameters W1. WI.bl.... bi.... WL, by and Wi, Wi. b'.... W b/2 respectively. Furthermore, the parameters in these two models are the same except the é-th layer, which satisfy
636
637
I Will S e, llb: b'1l2 SE
Denote the model as
ge (W (W bx), g6(2)) B: (W
+ b2)
where Ax(x) oeWoooWWWW WWW.Wol(....... 1 ) b1 denotes the first f- layers in the neural 640
network, and Ar(x) = Wi. (1+10 be+1) br.) denotes the last L - e- layers. with definition Ai (a) x. (r. x.
Now focus on bounding ||(x))]] Let W E mmm || S Vm x0 Rmm, b E R |b/2 S
643 m
lla + b) < Wa w + bl|2
| ||||==||22111 + ||||
|||r||1 + |b]
v Vml | l|2 + vm
644
where we make use of
||2 < || ||.. Because of that,
[Aa())]22 $ vd+ + Vdw < 2Vdw, [Aa(2)]]2 A (x) ||2 + 2w < Aw
(16)
[[((2)]]2
Ae) s 22w
645 Then focus on B(x). Let W E mm ||||F S im, E RT b E R"" 1271 S vm.
648 Furthermore, | x' ||2 S e, then
Io + b) a (Wa' + b)ll2 < (( 2')12 s ||||F|| -
which indicates that [B(xz) B(x)11l2 < (Vw) (/ -
19

---

648 Finally, for any W, W E Rm 2 Rm -b, b' E R"", one have
(Wx + b) - (W'x b11122 = (W W + (b - b')ll2
< W W 12 x l2 + |b 12
< W | + vmll
b' |000
649
In summary,
(e(x)) - 9((x)) = (5.(W.At(2) + bb) B: (<) + bb)l
S (Vw) (W (e(=)) bb) (W (z( + b))l
S (Vw)* ( (| (1))1 + |lb 11(12)
s w0 // -0
2
Let fxx be two neural networks satisfying (15) with parameters W1, b1 b1.b..... WL, by and Wi. by.... WL, b', respectively, and I|: Will ce. bb 1/IlF S é.. Further define fe be the neural network with parameters W1, bi...., We. W
651
4+1 6/ 111 WT, 8/2 then
15(x) ('x)] (f(x) [1())] + (x) f2(x)) + + ( (x)
2(( 2/22 (++e-3)) 31 + (2
For any 8 6>0 O, one can choose
5 33 2w(L--)/22
c==
653 such that - 5.
On the other hand, the e-covering number of { (We Rmmmm | S vm') on Frobenius norm
654
655 is no larger than (2/m'/e /e + 1)mxm', and the é-covering number of {b E R" |1b1l2 S 1} on infinity norm is no larger than (2/2 1)Th. The entropy of this neural network can be bounded by
log (J;5) & w log(2 2 1 18 1) + wT. (L--1)/22 1)
657
658
D.3 Covering Number of p-Norm Constrained Linear Combination
659
Lemma 6. logN(g, 6) & (1)( for some finite ca, and for any g E 9. S 1, we have
ag E G. The covering number of F SEM= agg. 9i E G, |all < P.O < < } for any P
660
satisfies
log NN c) S (.skkPP///ss (8/ca) Fo P/8)
662
up to double logarithmic factor.
663
Proof. Let c be 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 |as| 2 f S M, and |as] < for > M.
684
By definition, MeP < ΣM lag1 < P so M P/el, and la-1 S P. p1/p for all i. Furthermore,
Diel
667
Σ |al = Σ MaiPlas 1-P < Σ la 1-P < Pet-p
MMM
668
Let 9. = arg min geg llg covering set,
ai 9illoo where 9 is the 8'-convering set of G. By definition of the
689
M
M Σ
M
M
Σ (x)
<
Σ (aig((x) - p2/P
+
Σ
aigs(x)
i=++1
M M + PCt-..
(17)
20

---

670 Choosing
c= (6/2cg P) ~~ ~ P xiーii (5/2ca) /
(18)
671
we have M & PT (5/2ca) - , S 2/2,0xPet72 1 6/2, so (17)
S 6. One can
compute the covering number of F by
log S Mlog 2 (Mllg(1188)
(19)
673
Taking (18) into (19) finishes the proof.
E Proof of Approximation Error
674
E.1
Approximation of Neural Networks to B-spline Basis Functions
Proposition 7. Lef Mm,k, be the B-spline of order m with scale 2-k in each dimension and
676
position E IRd; Mm, := Mm M2 (x= - -s), Mm is defined in (11) There exists parallel neural network that has the structure and satisfy the constraint in Proposition Afor d-dimensional input and one output, containing M O(m²) subnetworks, each of which has width = O
678
and depth = Olog(c((m, d)/e)) () for some constant w, c that depends only on m and d, denoted
680
as Mm (x:), x E TR,", such that
681
Mm.k.e(z)) (x) Mm,k.. S if0 2z, L.)
682
683
Mm.k.o = O, otherwise.
The weights in the last layer satisfy || |a12// 2/L <
2mm 2md/LL
684
685
We follow the method developed in Yarotsky 449, Suzuki (3), while putting our attention on bound- ing the Frobenius norm of the weights.
687
Lemma 12 (Yarotsky [49 Proposition 3D. There exists a neural network with two-dimensional
input and one output fx (I, with constant width and depth O(log(1/8)) and the weight in each layer is bounded by a global constant eı, such that
689
690
|fx(x, - xyl S 6 < x. 11
* (x( 0, V x 0 or = 0.
We first prove special case of Proposition 7on the unscaled, unshifted B-spline basis function by fixing k = 0, 0:
693
Proposition 13. There exists parallel neural network that has the structure and satisfy the
straint in Proposition for d-dimensional input and one output, containing M = [(m + 1)/21d d = (mm) subnetworks, each of which has width w = (d) and depth L (log(c(mm, d) ()) for
695
696
some constant w. c that depends only on m and d, denoted as Mx)xx) x E IR,, such that
697
698
Mm(()) (x)) S e, if0 S x4 S m 1, Vi E [d], while Mm(-) denote m-th order B B-spline basis function, and only depends on m and d.
689
700
Mm = 0, if x, S or x, 2 m + for any E [d].
701 * The weights in the last layer satisfy || |all2/t. Z &
Proof. We first show that one can use a neural network with constant width wp, depth L 2 log(m/c1) and bounded norm | I O(vd), |[ S O(vw), Ve = 2.... L to approximate truncated power basis function up to accuracy 6, in the range [0,1]. 1]. Let m =
703
704
Σ llog2 m] m,2', m, E {0, 1) be the binary digits of m, and define my Ei m,, floga m],
2:=0
21

---

706
then for any
ti 44 ++
2 mhy
x (++
[ +
my
x4
2"
|
m x [++
2
x xx 2
(20)
[ xx1 = 1 [o _2 [
x
mi x
x
to
I+
707
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
708
709
architecture of such neural network approximation. For any z. 00, let (z. zy I
5. - i S ō1, ly gyl S 62, then (T, 0) ry S 5 + d2 + 5. Taking this into (20) shows that
711 61 278 ~ mn, where e the upper bound on approximate error to truncated power basis of
order and 8 is the approximation error to single multiply operator as in Lemma 12
713
A univariate B-spline basis can be expressed using truncated power basis, and observing that it is symmetric around (m + 1)/2:
714
Mm(x)= m! Σ (-1))
m +
j ) (x - j)
1m+1)/21
(-1)² m + +
(m++)
Σ
(min(s, + x)- -j)
m!!
(1m-1)/21
((m + 1)
m+ + (-1)((++))
minn(2; + x)) - 5/m
Σ (-1)
m!
(m + 1)/2
715 A multivariate (d- (d-dimensional) B-spline basis function can be expressed as the product of truncated power basis functions and thus can be decomposed as
(m) II Mm (2,)
((m + 1)/2)md
d [mm+1//2]
(-1)) m +1 min(z;, m + +1==) -2 )m
II
Σ
(ml)d
(m +1//2
(21)
E=1
()++1/22
((m + 1)/2)md
Σ
II
(mst +n++1 ji 1)
(m + 1) mmin( m + 1 x²)
(m!)d
(m + 1)/2
Using Lemma 12 one can construct parallel neural network containing M [mm 1)/27d
718
O(m") subnetworks, and each subnetwork corresponds to one polynomial term in (21) results above, the approximation of this constructed neural network can be bounded by
Using the
719
((m + 1)/2 [(m+1)/2] Σ Ja
[11
m (m++))
)
S md
(m!)d
720
where we applied Stirling's 's approximation and J and ej has the same definition above. Choosing 6 de Vm+1) and recall Ej z mō proves the approximation error.
721
To bound the norm of the factors |a |a/12/1. first observe that
((m + m)
1
II
m + 1)
(ml)d
(m + 1)/2
t=1
((m + 1)/2)md
2md
md)
(md))
(m + 1)/2
22

---

723
where the first inequality is from
(m*+1) I 2m+ the last equality is from Stirling's appropximation.
724
Finally,
2/2 |al| S m" max 2/1 X mee e
725
which finishes the proof.
728
The proof the Proposition for general follows by appending one more layer in the front, as we show below.
727
728
Proof of Proposition 7 Using the neural network proposed in Proposition 13] one can construct neural network for appropximating Mm.k.s by adding one layer before the first layer:
729
o22
730
The unused neurons in the first hidden layer is zero padded. The Frobenius norm the weight is
2* [alll = 2 Vd. Following the proof of Proposition 4 rescaling the weight in this layer by 2-*, and the weight matrix in the last layer by 2*, and scaling the bias properly, one can verify that this neural network satisfy the statement.
731
732
734
E.2
Sparse approximation of Besov functions using B-spline wavelets
Proposition Let a -d/p > 1,r O. For any function in Besov space fo E B.gq and any positive integer M, there is an M M-sparse approximation using B-spline basis of order m satisfying 0 < < min(m, 1 - 1/p): f the approximation error is bounded llf i- ak; a, Mm. k.. for any positive integer M such that >
M
foll, S M a/d allolllllos by.. and the coefficients satisfy
11 ak.. Jhr.e S foll
735
736
The proof is divided into three steps:
737
1. Bound the O-norm and the I-norm of the coefficients of B-spline basis in order approxi- mate an arbitrary function in Besov space up to any > 0.
738
2. Bound p-norm of the coefficients of B-spline basis functions where O < p < using the results above
740
741
3. Add the approximation to neural network to B-spline basis computed Section 4.3. into Step 2
743
Proof.
Lemma 2] proposed an adaptive sampling recovery method that approximates function in Besov space. The method is divided into two cases: when
Düng 11 Theorem 3.1] Suzuki 33
745
2 r, and when < r.
When p 2 there exists sequence of scalars Aj. E (d),,, Pa(n) (i zd lii S Vi
d} for some positive μu, for arbitrary positive integer hi, the linear operator
(+U,x)= = Σ "k (()
ako([)=
Σ
+
mm.))
jEBA,PA(H)
has bounded approximation error
|| IIf 1x-Qu(f.
C2 -2
where f is the extrapolation of f. (Te, m, d) == {s 2t E -7.-m/2 < 2% < 2 + m/2, Vi [d]. See Düng [II. 2.6-2.7] for the detail of the extrapolation as well as references for options of sequence Ag.
749
750
751
Furthermore, (R( E Byg so it can be decomposed in the form (10) with M - m
1)dd < 2 components and Ht.ll & [1Qx()) S |If l where čτ,a the coefficients of the decomposition of (f).. Choosing ie = log, M/ leads to the desired approximation error.
753
23

---

755
On the other hand, when < r, there exists a greedy algorithm that constructs
= =(()= +
Ckio (f)
k= f=1
798 where k x (M), k* = [ log((MM) (AM)) + 1 + 1,m = [AM2-c(k-R)] for some < e
757
a/6 I, d(1/p 1/r), 0, such that
|| G()L S M M-aa/d11ll
and
k²
(2 + m 1)a+
Σ k=k+1
Th S M.
0=0
See Düng 11
Theorem 3.1] for the detail.
780
Finally, since d/p 1,
11 Bnn..RR
2 (c
k=0
k
Σ ((1-(add/p)an) (2(0 Mers
(22)
k=0
2 - (a (a-d//))((lll 11
km0
|l
where the first line is because for arbitrary vectors a; E [n] a.lp S Ei= ||a.lpp- the third line is because the sequence norm of B-spline decomposition is equivalent to the norm in Besov space (Sccionn C.I.
762
784
Note that when a d/p = 1, the sequence norm (22) is bounded (up to a factor of constant) by which can be proven by following (22) except the last line. This adds logarithmic term with respect to M compared with the result Proposition 8 This will add a logarithmic factor to the MSE. We will not focus this case in this paper of simplicity.
k* If Il
786
788
E.3
Sparse approximation of Besov functions using Parallel Neural Networks
789
Theorem 9. Under the same condition as Proposition & for any positive integer M1, any function in Besov space fo E B.g can be approximated by a parallel neural network with no less than (m M) number of subnetworks satisfying:
770
Each subnetwork has width w = (d) and depth
772
2. The weights in each layer satisfy || [ (9) lle s O(vw) except the first layer [[ S O(Va),
773
774
3. The scaling factors have bounded 2/ L-norm: Mag3312/ 2/L S ma d M2-2/((L),
778
4. The approximation error is bounded by
If foll I (c aa/d
o/d + ose "
777
where C4, Cs Cs are constants that depend only on m, d and p.
778
We first prove the following lemma. Lemma 14. For any E IR M 0 p' < it holds that:
|ally/ s M /11l//'
24

---

Proof.
1-4
$
Iall =laip'=1,,aa' =1,
Σ
E(lapp')
M --- "1al|
The first inequality Holder's inequality with conjugate pair T and 1/(1 pf
p
Proof of Theorem 9 Using Proposition 8 one can construct M number of PNN each ((m)) sub-
780
networks according to Proposition and each PNN, such that each PNN represents one B-spline
782
basis function. The weights in the last layer of each PNN is scaled to match the coefficients in Propo- Taking p' in Lemma 14 as 2/ L and combining with Proposition finishes the proof.
783
sition 8
784
F
Proof of the Main Theorem
785
Theorem extended form. For any fixed - d/p 1,q 1, 3, for any fo E Bg given an Layeer parallel neural network satisfying
787
The width of each subnetwork is fixed and large enough: w 2 d. See Theorem 9 for the detail.
2/2 The number of subnetworks is large enough: M 2 man 207441 1007411-27000 276 where m [a 17.
With proper choice of the parameter of weight decay X, the solution f parameterized by (2 satisfies
790
MSE(f) =Ō
2a/d [ ( 20/6-1 2/1p1)
+ -oah
2/-2/L
where Ô shows the scale up to a logarithmic factor, and og is the constant defined Theorem
791
Proof. First recall the relationship between covering number (entropy) and estimation error:
795
Proposition 15. Let C [R + [-,,FF into two orthogonal spaces F = Fi x Fi where Fi is an offine spuce with dimension of N. Let fo {IRd + [-F,F)) F} be the target function and be the least squares estimator in F:
set of functions. Assume that can be decomposed
795
f arg min JEF
Σ (ys
So(o,) + + ((0, [(xs))
796
then holds that
N + (og +2 (F+o))))
MSE(f) S < arg min MSE(f) +
fer
n
797
The proof of PProposition 15) is defered to the section below. We choose F as the set of functions that be represented by parallel neural network as stated, the (null) space F_ {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
799
800
F See Sec-
801
fion 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 a parallel neural network as stated, and further satisfy Σ. f(z.) = 0.
802
803
Because Fi C (F S. N(F, 8) for all
and the latter studied Theorem 5
804
In Theorem I the width each subnetwork is no less than what required in Theorem 9 while the depth and norm constraint are the same, so the approximation error is more that that in heorem 9 Choosing r = 2,p = 2/L, and taking Theorem S and Theorem 9 into this Proposition 15 one gets
808
MSE(f) 2 AM-M2111 20/d 2+2/(1 L2
1-3/(ph) 1-21% 5 1-2/E
2/h (log(M//) M/8) 3) + 8,
M
n
25

---

where |l Vie
m and d taken as constants. The stated MSE is obtained by choosing
8 8 w 1/2 4/4 21
n2- 2/-2/L 4 4/L
M
n² 12-2/LL
Note that there exists weight decay parameter X such that the (2/L) of the coefficients of the parallel neural network satisfy that I| = m I| =ll l1//z. where {ā is the coefficient of the particular M-sparse approximation, although {a₂) is not necessarily M sparse. Empirically, one only need to guarantee that during initialization, the number of subnetworks 810
808
M M such that the M-sparse approximation is feasible, thus the approximation error bound
from Theorem can be applied. Theorem 9 also says that HayHl2// e "I| H H|gf 2 11p2/ thus we can apply the covering number bound from Theorem 5 with p M1-2/pL, Finally, if À is optimally chosen, then it achieves smaller MSE than this particular X, which has been proven to be no more than O(M and completes the proof.
812
813
814
815
Proof of Proposition 15
For any function f F, define fu arg mig, (f
h(x))) be the projection of f to F and define S1 = - fi be the projection to the orthogo- nal complement. Note that /j is not necessarily in Fij. However, if f E F, then J1 E Fii Yi and 819
820
Yall are defined by creating function fy such that (z,) yr. Vi, e.g. via interpolation. Because
Fi and Fi are orthononal, the empirical loss and population loss can be decomposed in the same
822 way:
1 (f(
Σ (z) foll (z)) n-N N 02 n
Li(f)
N n Σ (f((x) (x))
=
n
n
Ln(5) 1
Σ (z) -a11)
L.()) 1 E (x) (x)(2
T
(S) = Ep
(Ji - 1
MSEI (1) = ED Σ (1) (x) Jo (2))
1=1
such that L(F) (f) + (1 = 4 + (f). This can be verified by de- composing fo and y into two orthogonal components shown above, and observing that E - fi (2,) (xx) = 0, f2.
823
825
826
First prove the following claim
Claim 16. Assume that f arg minjer L(f) is the empirical risk minimizer. Then fl arg min SEFI f = arg ser (f), where f. is the projections of f in Fi, and 829 f f - fi respectively.
828
Proof. Since f E F. by definition / E F1. Assume that there exist Pi Pí. and either L (f1) < (, & (f)) < (f)) Then
830
831
i(") = ic + = ( - + B ( +L(1 < ( + (=(((()==nn + fn) + Li + f
which shows that f is not the minimizer of i.( and violates the assumption.
832
26

---

o² 834 Then we bound Mf). We convert this part into a finite dimension least square problem:
f1 = arg min (f)
feFi
arg min feFi
(f(x:)) - foi) =LLL²
π
arg min feFi
(f(x;) for (x =x1 + Eill
n
1
arg min JEFi
Σ (f())) foi( Cil cil)
n
i=1
1 (f(x,) foi( - EG)
arg min
FEFi
1=1
825
The forth line comes from our assumption that Fi is orthogonal to Fii. so 4f E F1, f for +
836 orthogonal to é|1.
837
Let the basis function of Fi be h1, l2,,.................... NN, the above problem can be reparameterized as
arg min - X - yll
BERN 71
where RaxN, X, h,(,),))))) You
+ Vn. (x1). (21). fo. c= = (e le........l .ul.
838
839
This problem has closed-form solution
0 X X) 'x"
840
Observe that for F1, let fous X0 The MSE of this problem can be computed by
1
L(fi)
X0 yoo1 12
(X0" +e) xo
|X(X x) c12
Observing that 11 x X) -1 x is an idempotent and independent projection whose rank is 842
N, and that EEcc"") = I we get
MSE -E]((() _
[[e|| (IlEE"" tr(11)
71
n
n
943
which concludes that
MSE (ʃ) o 002
(23)
844
See also 19 Proposition 1].
Next we study MSF (f). Denote oं = Ei= 21 F. max; |ea]. Using Jensen's inequality and union bound, we have
845
846
(x) E[exp(tE)) E/max exp(te))) Efexp(tle:]] 2n exp((22 /2)
Taking expectation both sides, get
log 2n lo2 2
t
848
maximizing the right hand side over t yields
E E S / 2 log 2n.
27

---

Let Fi be the covering set of Fii = [f] : f F). For any ft Fip.
849
(( - -((ff))
(z,) - [o,12
1
Σ
n
(x)())) ) - Y/s )) 32
N
0²
12 ==1
n
Σ (2)( fol((x)) - -Vall) + N 0²
(2(2 (ax)) fon -Wel)) n - N
Σ
i=1
N 0² 01
(2f (m.) 2fo (2:)) +
n
850 The first term can be bounded using Berssten'' inequality: let h; ((() - (a:)), by definition [hy] 2EF,
Var[h;] [[( (ax) fo (x:()
(f;());) - foll (z; )) )E{e²
(2, forl (xx)) 1)²2
using Bernstein's 's inequality. for any fl F1, with probably at least 1 - 6p.
852
n
(a:) 2fon( = h4
7
8EF 8EFlog log(1/6p)
Σ 2
(f))) - (x)));)) (2 log(1/6p) +
3n
20 log (1/p)) 2/ (L n N 0²)
8FF log(1 (1/pp)
n
n
3n
<e(Li(h))
n - 0²)
8 log(1 (1pp)
8 SEF log(1 (1pp))
The
3n
853 the last inequality holds true for all > The union bound shows that with probably least 1-5. 5, 854 for all J1 E Fi.
n -²) + 8 (og N 77.
SEF log(((FF)) ())5p)
( - (f)) S (L4 (fi)
3n
n
By rearanging the terms and using the definition of L(f)). we get
(1 (1-0((ni()) - n -= S (n)( + 80² log(N((F 5)p)) n o²)
8EF (oFFoo((((F)))))/5
+
3n o1-
ne
Taking the expectation (over D) on both sides, and notice that E[ö?] n-N 0² Furthermore, for 857 any random variable X, E[X] f xdP(X s æ), we get
a56
n
max (11 - c)MM ((L( fiE
< 80²
8Fo / log 2n
(1o, - -f² log( log(O))do)) 18=0
n
o²
(24)
3n
80²
/Fo.22l 2n
(log.N(FF). 5) + 1
n
02
TEE
3n
858
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

---

Similarly, let fi = arg sea Li(s),
880
- Ln( E
(((fii(za)) 2 (a:)) +
N o²
01
im1
a61
with probably at least
8g. for any > 0,
n- 02) +
So² 11g(1/6p)
8EF log (1/pp)
(x:) - (201( S [1] (Fi)
n 1=1
nC
3n
(n) s (1 + e) (FI((T)) " n- - 80 log(1 (1pp)
3oFlog(1/06
+ 1
ne
3n
862
Taking the expectation on both sides,
ELL (fi)) - (1 e)EE (f() + 80
8Fa 8Fov2log 2n
N n
+
0².
(25)
ne
3n
Finally, let J. == arg argming 1f - f(x:))² be the projection of fj in its d-covering space,
863
MSE E 1
(fi)
Σ
n
( fo]l
(fz(z)) - (x,)) 1 - (a:)
+ f...) - 2fo (z,))
E
1=1
1=1
(f. (xx) - (x,))) 4F8
i=1 MSE (f. 4F8,
aes and similarly
(f.(f)) S ((((s)) + (4F 2F))
(26)
866
We can conclude that
([.] + (80²
8Fo 22og 2n
(log.N(F1..0+ +1) n - N 02
(f) <
+
1 1-6
ne
3n
+ 4F8
(E + (4F + +ov log 2n)o
802
&Fov2log 2m
N 02) + 4F8
(log (log.V(F1:: 8) 11
TEE
3n
n
[E]L )1 + (4F + .ov///// 8 log 2n)
80²
8Fo log 2n
(log.N(F1: +1 n g²) + +4F8
ne
3n
1
1 S
/Fo 2n
log log.N (FF 6) +
MSE
1-E
+ (IF + 4F + 008 log 2n
8,
1-c c
857
where the first line comes from (24) and second comes from (26) the thid line because
Ji = arg min īy (J), and the last line comes from (25) We also use that fact that ( S
868
i (f, Noticing that MSF()) = (f) + MSF (f), combining this with (23) finishes the
869
proof.
D
29

---

G
Detailed experimental setup
871
872
G.1
Target Functions
873
The doppler function used in Figure 2[d)-(f) is
f(x) sin(4/(2 + 1.5.
874
The "vary" function used in Figure 2(g)-() is
((x) = M1(x/0.01) + M1 - ( 0.06)/0.03)
M2 + Mi((z 0.12)00.10) + M2((x 0.2)/0.02) + Ma((2 0.28)/0.04)
+ Ma((2 - 0.44)/0.06) + MM((x - 0.68)/0.08),
875
where M1. M3 are first and third order Cardinal B-spline bases functions respectively. We uni- formly take 256 samples from to I in the piecewise cubic function experiment, and uniformly
878
877
1000 samples from O 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
878
879
0.4 in the doppler function experiment and 0. in the "vary" function experiment.
G. Training/Fitting Method
In the piecewise polynomial function ("vary"" experiment, the depth of the PNN L = 10, the width of each subnetwork to = 10, and the model contains M = 500 subnetworks. The depth of NN is also 10, and the width is 200 such that the NN and PNN have almost the same number of parameters. In
882
883
884
the doppler function experiment, the depth of the PNN L = 12. the width of each subnetwork w
885
10, and the model contains M 2000 subnetworks. because this problem requires more complex
886
model to fit. The depth of NN is 12, and the width is 400. We used Adam optimizer with learning rate
887
of 10-3 We first train the neural network layer by layer without weight decay. Specifically, we start with a 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 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 [40] using CVXPY, and use MOSEK to solve the convex optimization problem. We directly call R function spooth.spline to solve smoothing spline.
888
889
891
883
895
G.3
Post Processing
The degree of freedom of smoothing spline is returned by the solver in R, which is 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, we use the definition [T:
898
900
20 = Ellyy - - Elyy 1
(27)
where df denotes the degree of freedom, 0² is the variance of the noise, y are the labels, ý are 902 the predictions and y' are independent copy of y. We find that estimating (27) directly by sampling
901
903 leads to large error when the degree of freedom small. Instead, we compute
20 2 T5 Vo 012 - 1 0113
Blyyy
11
3oll
(28)
where df is the estimated degree of freedom, E denotes the empirical average (sample mean), Do is the target function and yo is the mean of the target function its domain.
905
Proposition 17. The expectation of (28) over the dataset D equals (27)
30

---

Proof.
20
Ep [ Vo 01 Bly 013 + Bly voll3 1l Toll3]
812 E ly -013 + Ep [D yo) + yo 20,)l
33 Moo
ú| E y U12 Σ c2 t 2g0) -
R Vo ú12 E y Ul3 na²
E y 81/ B 011
where D denotes the dataset. In the third line, make of the fact that E|G] 0, 0 = o² and in the last line, we make use of Ele[] Ele o², and e/ are independent of y/: and you E
908
909
One can easily check that a "zero predictor" (a predictor that always predict joo, and it always predicts O if the target function has zero mean) always has estimated degree of freedom of O.
In Figure 2i), we take the minimum MSE over different choices of X, and plot the average over 10 runs. Due to optimization issue, sometimes the neural networks are stuck at bad local minima and the empirical loss is larger than the global minimum by orders of magnitude.
912
deal with this problem, in Figure ()), we manually detect these results by removing the experiments where 915 the MSE is larger than 1.5 times the average MSE under the same setting, and remove them before computing the average.
913
914
G.4
More experimental results
918
G.4.1
Regularization weight vs degree-of-freedon
919
As we explained the previous section, the degree of freedom is the exact information-theorete measure of the generalization gap. A Larger degree-ooffrredom implies more overfitting.
120
Thme Ton
2.0
230
03
1.0
130
10
12
10th
28-4
10
22
12
(b)
330
200
430
Porresdweten
1.00
of
300
(c)
(d)
Figure 3: The relationship between degree of freedom and the scaling factor of the regularizer X. The solid line shows the result after denoising, (a)(b)in NN. (c) In trend filtering. (a)(c): the piecewise cubic function. (b)(d) the doppler function.
321 In figure Figure 3
we show the relationship between the estimated degree of freedom and the scaling factor of the regularizer À in parallel neural network and in trend filtering. As is shown in the
31

---

four newarrc
Sveethrg
Feuld retrore
WOWKT GPAS 633
ousput caem LEEETAO
PROCSE
155
244
0.5
2.4
10
85
0.
00
(d)
(c)
(f)
Figure More experiments results of Doppler function.
lorgut kuiclih
Thans Marreg
Smeetnin 128r
Output of secteteeeterr
-8.4
(d)
(e)
(l)
Figure 5: More experiments results of the "vary" function.
923
figure, generally speaking as X decreases towards 0, the degree of freedom should increase too. However, for parallel neural networks, if À is very close the estimated degree of freedom will not increase although the degree of freedom is much smaller than the number of 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, e.g. trend filtering, which overfits every noisy datapoint perfectly when
924
925
926
927
928
But for the neural networks, even we do not regularize at all, the among of overfitting is still relatively mild 30/256 vs 80/ 00/1000. In our experiments using neural networks, when small, we denoise the estimated degree of freedom using isotonic regression.
929
930
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 under over-parameterizzatin..
We do not know the exact
933
934
935
26
938
G.4.2
Detailed numerical results
337
In order to allow the readers to view our result in detail, we plot the numerical experiment results of each method separately in Figure 4 and Figure 5
32

---

G.4.3
Practical equivalence between the weight-decayed two-layer NN and L1-Trend Filtering
940
941
In this section we investigate the equivalence of two-layer NN and the locally adaptive regression splines from Section In the special case when = 1 the special regularization reduces weight decay and the non-standard truncated power activation becomes ReLU. We compare L1 trend fil- tering [2 (shown to be equivalent to locally adaptive regression splines by Tibshirani [40] and an overparameterized version of the neural network for all regularization parameter > 0, i.e.,
945
945
regularization path. The results are shown in Figure [ It is clear that the weight decay in- creases, it induces sparsity in the number of knots selects similarly to LI-Trend Filtering, and the regularization path matches up nearly perfectly even though NNs are also learning knots locations.
947
10
To eing dit3
6.3
widpttdacay =
350
25
waag1 Uaeyy 2005
wndget dacay
8:00
weaytt Lakcy
wedght decay 2.00
1.05
6.1
-2.75
-250
0.5
0.50
0.75
1.00
0.002
0.301
0.008
6.013
Gronn buth
Thaning cote
0.75
Unoce 122
0.25
oxffcerb
0.25
0.00
0.00
Saicco 255
-0.25
-0.22
0.0
055
075
-0.75 -035
-100
Figure 6: Comparison of 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 [77 of the coefficients of the truncated power basis at individual data points (the free-knots learned by NN snapped to the nearest input æ to be comparable).
33


Reviews:
[{"review_id": "jGqRQn1zWv", "reviewer": "Reviewer_yJWs", "summary": "This submission first shows the equivalence between standard weight decay and sparse penalty in the parallel neural networks. The authors then show that the estimation error rate is close to the minimax one. Finally, simulation results are provided to compare the approximation from different estimators.", "questions": "See above", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This submission first shows the equivalence between standard weight decay and sparse penalty in the parallel neural networks. The authors then show that the estimation error rate is close to the minimax one. Finally, simulation results are provided to compare the approximation from different estimators.\n\n*Strengths And Weaknesses\nFirst I need to say that I am not an expert on the topics of this submission, and hope other reviewers with relevant background can comment more on the significance and novelty for the theoretical results.\n\nStrength:\nOne interesting observation is that the authors proved that deeper models achieve smaller MSE error, and hence is closer to the minimax rate. Although this is only for the special parallel ReLU DNNs, it is still helpful to gain a better understanding on the empirical better performance of deeper models.\n\nWeakness:\nA few parts of this paper are a bit difficult to follow, and some clarification would be helpful, which are listed as follows.\n1. I am not sure how sparsity is shown in the equation in Figure 1 (b). If L \\neq 2 and hence it's not an L-1 norm, how can we still obtain the sparse regression?\n\n2. The purpose of the results in Figure 2 is a bit unclear. For example, the authors claimed parallel NN achieves smaller error with deeper networks. Could you provide any results to support this claim? Furthermore, unlike wavelet denoising, why does NN tend to achieve higher MSE with higher DOF in the end of curves?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "j2wc3NWL1ZK", "reviewer": "Reviewer_D3YQ", "summary": "1. This paper considers the mean regression using the parallel ReLU activated neural networks.\n\n2. This papers observes that the training is equivalent to $\\ell_p$ sparse regression with a learned basis.\n\n3. The paper establishes the error bound for MSE($\\hat f$), which almost achieves the minimax rate of a Besov class when the depth $L$ is large.", "questions": "1. The method highly depends on parallel networks. This is different with general usage of DNNs. So the conclusion of this paper cannot address the success of deep learning in a general way.\n\n2. It is not very intuitive that the $\\ell_p$ sparse regression with a learned basis can adapt to unknown smoothness. Can the authors use the results from Parhi and Nowak (2021) to address further properties of each learned basis?\n\n3. The paper claims that their regression problem has a fixed design, so data points are not iid. Can you clarify the meaning of this? Do iid data points make the problem easier?\n\n4. The numerical experiments are over-simplified and only consider the 1d regression. For example, for an easy MNIST dataset, how large $M$ should we use?\n", "limitations": "There is no potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The connection between deep learning and nonparametric statistics is an important question. The recent papers by Parhi and Nowak (2021) and Suzuki (2018) are inspiring. This paper combines a couple of previous techniques and provides some promising results.\n\nQuality: This is a theoretical paper and it is technical sound. The claims are well supported.\n\nClarity: The submission is clearly written and well organized. \n\nSignificance: The results are important. However, the experiment section is not very convincible. The practical usage of proposed method is questionable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZKMLpE5bSe", "reviewer": "Reviewer_2BVk", "summary": "The paper studies how weight-decayed parallel ReLU networks are able to estimate functions with heterogeneous smoothness in the Bounded Variance and Besov classes. In particular, the authors show that the weight decay in the L-th layer parallel network is equivalent to a sparse $\\ell_{L/2}$ constraint and use this property with an upper bound of the covering number to bound the estimation error. The authors then provide an approximation error bound by using the B-spline basis functions as a proxy. They have shown that for a deep network, the error rate is nearly optimal. ", "questions": "1. In the extended form of theorem 1 in the appendix, the dominant term of the MSE also contains a large dependency over the depth $L$. When $L$ is large, I would assume this term to be linear in $L$. As a result, when $L$ is large, the constant term would decrease exponentially with $L$, but the first and dominant term grows linearly in $L$. I feel this cannot support the statement that deeper parallel networks achieve lower or even optimal error rates. Is there somewhere I was misleading here? \n\n2. Related to the comments above, how large are $\\lambda$ and $P'$? ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work. ", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper provides the first optimal rate approximation results of a weight decay parallel ReLU network over Besov functions. The observation that the weight decay in parallel networks is equivalent to a sparse promoting constraint is interesting. It enables the control of the complexity of the model, which is characterized by the covering number in the paper. This also allows the number of subnetworks $M$ to be large without overfitting. The paper also shows that each subnetwork can adapt to functions with different local smoothness properties (different B-spline basis functions) and thus have the ability to be locally adaptive. \n\nWeakness:\n\n1. The main complaint is that the statements of the theorems and propositions are not provided in a clear and rigorous way. Theorem 1 is confusing in the sense that it does not specify the assumption for the target function $f_0$. There seem to be two sets of function classes considered in section 2.2, the Besov spaces $B_{p, \\infty}^{\\alpha}$ and bounded variation space $BV(m)$. From the statement, I would assume the target function belongs to $B_{p, \\infty}^{\\alpha}$, is that true? And how is $m$ defined in the problem? Is $m$ to be any integer with $m > \\alpha$? $r > 0$ is assumed in the statement but $r$ does not appear anywhere else in the theorem. Also, I find the statement \"with proper choice of the parameter of weight decay $\\lambda$\" to be vague. It would be helpful if how $\\lambda$ depends on other parameters in the theorem can be specified. The authors provided an extension version of theorem 1 in appendix F, but it does not resolve the problems above. For example, the proof also uses \"there exists a weight decay parameter \\lambda'\" in line 775, which causes confusion as I would like to know how large this $\\lambda$ or $\\lambda'$ would be. \n\nThere are similar unclear statements in other parts of the paper. In proposition 3, the authors do not specify how $P'$ depends on the other parameters. In fact, $P'$ would depend on $\\lambda$, and may not be viewed as a constant. Actually, in proposition 6, one can see that $a$ can have a large $2/L$ norm that depends exponential over $m$. In theorem 4, the notation of $\\log \\mathcal N(\\mathcal F, \\delta)$ is confusing as $\\mathcal F$ is used to denote the model defined in (5) apart from the bias in the last layer. In proposition 6, $M_{m, k, s}$ is used but its definition is only shown later in proposition 7. \n\nAll these unclarities in the theorem statement (especially the ones in theorem 1 and proposition 3) make it hard to either examine the theorem or evaluate its contributions appropriately. \n\n2. The paper uses parallel networks instead of typical neural network structures. As authors have pointed out, weight decays in the parallel networks would result in sparse promoting networks, but vanilla neural networks don't seem to have the same behavior. Also, the paper talks about approximation ability instead of that of training, and as the results rely on the homogeneity of ReLU, it is unclear whether a trained weight decay parallel network would also find a sparse solution. \n\n3. The experiments do not support the arguments nicely. In figure 2, the nonsmooth part (the left part in figure (a)(d)) are hard to see clearly and thus impossible to tell which methods perform better. Also, for a highly oscillating function, one would need a larger number of samples to be able to fit it correctly, which may be the reason why figure (b) and (c) looks noisy. It would be helpful in plotting the relationship between the MSE and the sample sizes instead of the degree of freedom. In figure (c)(f), it is hard to see the sparsity of the subnetworks well. From the appendix, there seem to be $M = 2000$ subnetworks. It would be helpful in providing the scale of each subnetwork in total instead of plotting a few of these subnetwork outputs. \n\n\nTypos: \n1. equation (4) missing a parenthesis on the left-hand side\n2. the axis in figure 2 is not shown properly (\"MSE\" in (b)(d) is partially covered)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0aQNb2h4HFC", "reviewer": "Reviewer_RAZ6", "summary": "This paper studies weight decay regularized neural network training problems through the lens of nonparametric regression. The authors particularly consider a parallel architecture that is a weighted combination of multiple standard networks and show that weight decay regularization promotes Lp sparsity for the coefficients of the learned dictionary. Thus, they aim to shed light on why depth matters and the distinction between the expressive power of neural networks and kernel methods.", "questions": "* I don’t see any theoretical reasons for studying a parallel architecture rather than a standard deep neural network. It seems that the authors already allocated a section to prove common usage of this architecture in various theoretical and empirical works. But, I still think they need to explicitly describe the reasons for choosing this specific architecture and explain why analyzing standard networks are challenging if that is the case.\n* Could the authors comment on the impact of regularizing the bias? Even though this is the common practice for numerical experiments, it might make the problem trivial when one aims to globally optimize the objective function rather than using certain optimizers, such as SGD, with benign implicit regularization effect. In other words, if the network is deep enough one can choose arbitrarily small layer weights satisfying the constraints in Proposition 1 and then optimize over biases to exactly fit the training data. \n* It seems that this kind of a sparsity-inducing properties of weight decay regularized NNs have already been studied in [1,2]. I think the authors should comment on these studies and clarify their contributions.\n* Regarding the numerical experiments, I am wondering if the comparison between parallel NN and standard NN is fair. For instance, what is the number of parameters for each architecture? What is the depth of the networks? Which optimizer did you use? I think the authors should provide more details in the numerical experiments section.\n* Is it possible to extend this analysis to different activations, e.g., smooth activations such as tanh, sigmoid or other nonsmooth activations such as leaky ReLU, piecewise linear activations?\n* Do these conclusions apply to other NN architectures such as CNN? It seems that [3] has already proven that two-layer weight decay regularized CNNs also induce a sparsity across filters. Does this work have similar implications possibly for deeper CNNs?\n\n[1] \"Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.\", ICML 2020\n\n[2] \"Global optimality beyond two layers: Training deep relu networks via convex programs.\" ICML 2021\n\n[3] \"Implicit convex regularizers of cnn architectures: Convex optimization of two-and three-layer networks in polynomial time.\" ICLR 2020\n\n", "limitations": "This is mostly a theory paper on neural networks therefore doesn't have any negative societal impacts.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is mostly well written and the results seem theoretically sound, however, there are some point requiring further clarifications as detailed below:", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject