Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
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. 

Weakness:

1. 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. 

There 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. 

All 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. 

2. 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. 

3. 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. 


Typos: 
1. equation (4) missing a parenthesis on the left-hand side
2. the axis in figure 2 is not shown properly ("MSE" in (b)(d) is partially covered)
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? 

2. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

*Strengths And Weaknesses
First 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.

Strength:
One 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.

Weakness:
A few parts of this paper are a bit difficult to follow, and some clarification would be helpful, which are listed as follows.
1. 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?

2. 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?
questions: See above
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
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:
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.
* 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. 
* 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.
* 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.
* 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?
* 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?

[1] "Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks.", ICML 2020

[2] "Global optimality beyond two layers: Training deep relu networks via convex programs." ICML 2021

[3] "Implicit convex regularizers of cnn architectures: Convex optimization of two-and three-layer networks in polynomial time." ICLR 2020


limitations: This is mostly a theory paper on neural networks therefore doesn't have any negative societal impacts.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 1. This paper considers the mean regression using the parallel ReLU activated neural networks.

2. This papers observes that the training is equivalent to $\ell_p$ sparse regression with a learned basis.

3. 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.
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.

Quality: This is a theoretical paper and it is technical sound. The claims are well supported.

Clarity: The submission is clearly written and well organized. 

Significance: The results are important. However, the experiment section is not very convincible. The practical usage of proposed method is questionable.
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.

2. 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?

3. 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?

4. 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?

limitations: There is no potential negative societal impact of their work.
review_title: null

Meta-review: metareview: This paper considers the generalization error of neural networks when approximating a specific set of functions. The main contribution of this paper is showing a rate of neural network generalization error which is better than linear functions. 


The major problems of this paper are 

(1). Missing an important sequence of works on separating the power of neural networks from kernel methods, for example, "what can ResNet efficiently learn, going beyond kernels". The authors do not seem to be aware of this line of work that already separates the neural network learning power from any linear learners.  

(2). Assuming that the training can minimize the objective function up to global optimal. While it is true that the neural network can fit all the training data in practice, it is very unclear whether they can actually find the global optimal of the regularized objective. This is quite an unrealistic assumption. The authors should at least extend their results to the case when the objective is <= some value, instead of only talking about the global optimal. 


(3). Parallel architecture. The parallel network considered in this paper has all the intermediate layers being completely disjoint. This version of the parallel network is not what is used in practice. For example in ResNext, the parallel is layer-wise. The authors should at least clarify this difference instead of trying to present the result like "we consider the parallel networks as used in practice"



confidence: Certain
Decision: Reject