Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper examines training a specific neural network (namely parallel neural net) using weight decay and shows that the error rate matches the minimax bound for a specific class of functions (i.e., functions with bounded variation). 

It looks like a quite interesting effort and the result also appears to be significant. But I worry the paper is not presented at the level for general audience in ICLR. For example, I have a few questions/confusions after reading the submission: 

1. What exactly is weight decay? I actually could not find its definition/elaboration except for eq. 2, which is just L2 regularization? I was guessing it could relate to learning rate, momentum, some dynamic shrinkage on the fly...
2. Do we assume that Eq.2 can be optimally solved? It is a minimax result related to sample complexity so I believe the authors assume that Eq. can be optimally solved --- I think sometimes ignoring computational tractability is fine (and perhaps had been a standard practice in statistics) but it would be helpful to bring this upfront. 
3. What's so special about parallel NN? I think most audience wants to understand at a higher level where the magic happens and why the magic wont happen for the standard MLP, e.g., only limit of existing theoretical tools or parallel NN possesses some special structure? 
----
Thank you for addressing the presentation concern. I have raised my scores to 6 -- do not feel am an expert in this area so no confidence to move to 7. 




strength_and_weaknesses: Strength: The authors can show that a specific kind of neural net achieves minimax rate for an interesting function family. Some of the techniques appear to be significant (e.g., hacking into covering numbers). 

Weakness: there is room for improvement in presentation. 
clarity,_quality,_novelty_and_reproducibility: I can mostly follow the paper but was confused by some details from time to time. 
summary_of_the_review: I think the substance is above the bar of ICLR; the revision addressed my presentation concern.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to analyze the theory of deep neural network from the perspective of non-parametric regression. The authors show that training an $L$ layer neural network with weight decay is basically the same as penalized regression. And in the case of functions in the Besov space and bounded variation space, neural networks achieves almost near-optimal rates. When the number of layers increase, the error decreases and thus explains why deep networks performs better than shallow ones. The authors also validate some of their claims using experiments.
strength_and_weaknesses: Strength:
  1. The paper is well-written and mostly clear.
  2. The theoretical analysis provided by the authors are, as far as I am aware of, novel and interesting.
  3. The obtained results do provide some insights on, for example, why deep networks do no overfit and why deep networks perform better than shallow networks.

Weaknesses:
  
 First off, I want to say that I am very new to the area of non-parametric regression and the function spaces the authors use in this paper. I have some experience with deep learning theory but this direction is completely new to me. Therefore, I might not be the best reviewer for this paper. Some of my comments might be unfair/wrong and I hope the authors and the other reviewers can help me understand this paper a little more during the discussion period. 

  Now back to this paper, I do have some questions about the setting and the results the authors provide. 
  
  1. The authors have chosen to optimize a set of parallel feedforward networks with $L_2$ regularization (I don't really like using the word "weight decay" here because there is no mentioning of the optimizer, e.g. SGD/Adam, and thus weight decay does not really exist). I wonder why the authors didn't include the regularization for the bias in Eqn. (2)? After looking at the Appendix, I think the authors do analyze the network with the bias term, so why is the regularization for bias missing? I think in practice, people have both regularization for weights and bias.

  2. In Theorem 1, I am confused by the statement "with proper choice of the parameter of weight decay $\lambda$". How large does the parameter need to be? Does it need to be time-varying, for example? If the choice of $\lambda$ needs to depend on the other parameters such as $M, L, p, q$, please state it explicitly in the theorems so that we can understand it more clearly.
  
  3. I am a little confused by the results in Corollary 2 and 3. For example, in Cor 2, although the $o(1)$ term is negligible, does it mean that the rate of deep neural network is worse than that of traditional nonparametric regression models? Are there models that can achieve the minimax rates that the authors have state Page 3? I think it might be better to have a table to compare the results in this paper with the results in the literature. Also, what is going to happen if $L > 100 C \log n$? For very deep neural networks, do the theorems still hold?

  4. For Cor 3, although I know that most of the paper is focused on $L\gg 2$, the authors might want to mention that the results here fail for $L=1, 2$. Also, the claim that "DNN has an advantage over kernels" is a little confusing, shouldn't there be an assumption on $L$ (L> some function of m) so that the bound for DNN is strictly better than that of kernels? I hope the authors can state it more clearly.

  I do not have enough time to go through all the proof details, but the proof overview section does give me enough intuition of how the theorems are derived. The experimental results are a good supplement to the theory.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear, novel, and reproducible with the appendix.
summary_of_the_review: Overall, this seems to be a good paper with nice contributions. However, I am confused by some settings and theoretical results of the authors. Again, I am no expert in this field, and if there is anything wrong in my review, please correct me and I am happy to increase my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper analyzes parallel neural networks for nonparametric regression (including approximation error and regression error analysis). Suppose the regression function has nonhomogeneous regularities, e.g., Besov functions or functions of bounded variation. Parallel neural networks trained with weight decay achieves near optimal estimation, indicating the adaptability of parallel neural networks.
strength_and_weaknesses: ============= Strength =============

The paper is clearly written with both theoretical and empirical results. The theoretical results are correct and empirical results are supportive.

The adaptability of neural networks is studied in many recent works, including its adaptability to data geometry and adaptability to structures in function spaces. This paper considers parallel neural networks and uses weight decay for controlling the complexity of the network, which circumvents sparsity constraints in many existing network approximation results.

============= Weakness =============

There is no related work section. Some of papers share similar ideas to parallel neural networks, for example, "Approximation and Non-parametric Estimation of ResNet-type Convolutional Neural Networks" and "Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks" both rely on implementing block sparse feedforward networks. The resulting (residual) convolutional network does not need a sparsity constraint in training.

The obtained rate of estimation is slightly slower than the optimal rate, which is attainable (up to log factors) in many recent works on using ReLU neural networks for nonparametric regression.

From experiments, parallel neural networks seem to achieve comparable performance to neural networks and conventional methods.
  
clarity,_quality,_novelty_and_reproducibility: Some of the technical contributions need highlighting. For example, the conversion of weight decay objective to the constraint form in Equation (5) can be highlighted as a contribution -- if it does not appear in Parhi & Nowak (2021a). Another example is the decomposition of \mathcal{F}_{\parallel} and \mathcal{F}_{\perp}.

A discussion on why parallel neural networks can only achieve the optimal rate in the asymptotic sense ($L \to \infty$) is helpful. Is it because the weight decay introduces additional bias?

In Theorem 1, it is good to state how to choose weight decay $\lambda$.

Lemma 6 is relative difficult to understand, mainly because the first sentence begins with an equation.

Overall, the paper is well written. There are some typos and typeset issues, for example, "errorand" --> "error and" above Section 4.2
summary_of_the_review: I think the paper is interesting. I am currently giving a slightly negative rating, due to some concerns of the results and missing references. I am happy to raise to a positive rating after paper revision and an effective author feedback.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper extends Suzuki’s work (ICLR2018) to parallel neural networks in the Besov space as well as BV functions, studies the generalization properties in terms of approximation error via B-spline basis and estimation error via covering number, and demonstrates the $\ell_2$ norm (weight decay) in parallel ReLU neural networks is equivalent to a certain sparse regularization term.

strength_and_weaknesses: 
**Pros:** 

1. This work allows for over-parameterization without the extra sparsity condition
The obtained bound of the covering number is independent of the number of subnetworks, which is substituted by the Frobenius norm.  

**Cons:**
 
1. The motivation on locally adaptivity makes sense, comparing linear estimators and DNNs. Nevertheless, the motivation on the comparison of (Suzuki ICLR2019)  is relatively weak. The authors claim that Suzuki’s work requires certain conditions on the width, the depth, the sparsity to achieve the minimax rate on deep ReLU networks, which is different from practical uses. Nevertheless, this work does not focus on this issue but centers around another architecture, i.e., parallel neural networks. Even though parallel neural networks have theoretical and empirical applications as the authors suggested, the “correct” motivation is to solve certain conditions in Suzuki’s work under the same architecture.

More importantly, this work also requires several conditions on the width, the depth, etc. In the “No architecture tuning” part, the required architecture of the model still depends on $\alpha$, see Theorem 1. It is hard for me to accept the authors’ motivation.


2. In theorem 1, the number of subnetworks is exponentially large enough w.r.t the input dimension $d$. This is unacceptable in both theory and practice.


3. In Proposition 4, the equivalence between Eq. (2) and Eq. (12) is imprecise via the Lagrangian’s method in optimization. The constraint value P doesn't appear in Eq. (2) and it is also not clear how the dual variable is handled. In fact P (as well as P’) is unknown or uncomputable, which also makes the upper bound of the covering number appear infeasible in Theorem 5 depending on P’. It is ok for ease of description but is not rigorous in a theory paper corresponding to the first contribution.

4. After reading this paper, I think the technical contribution is to derive the covering number bound of the parallel neural networks for the estimation error, i.e., Theorem 5 and Lemma 6. The proof for approximation error follows Yarotsky (2017); Suzuki (2018). However, this paper works under a fixed design, which is much easier to derive the estimation error.

clarity,_quality,_novelty_and_reproducibility: This paper is well-written. Apart from the above mentioned issues, I have other questions that

1. I agree with the authors that kernel methods, e.g., NTK, lacks local adaptivity to some extent due to RKHS. I’m wondering that, the mean field regime (instead of NTK) is also suboptimal to local adaptivity?


2. For the random design, the proof of estimation error can be similarly established by [1]?

[1] Schmidt-Hieber, Johannes. "Nonparametric regression using deep neural networks with ReLU activation function." The Annals of Statistics 48, no. 4 (2020): 1875-1897.

summary_of_the_review: This work has some good results on the sparsity, the separation between linear estimators and DNNs in Besov spaces as well as BV functions. Nevertheless, the derived results appear vacuous in terms of imprecise Lagrangian dual and curse of dimensionality of the input dimension.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper gives a new nonparametric estimation error bound of deep learning where the true function is included in the Besov or BV space. This paper considers a model of a parallel NN and shows that the L2-norm regularized empirical risk minimizer achieves the optimal rate without sparsity constraint that has been imposed by several existing work. 

**Strength:** This paper explicitly shows the near minimax optimal rate without sparsity constraint when $L^2$ regularization is imposed. This is because the layer-wise $L^2$ regularization yields a sparse regularization on the coefficient of each block sub-network. In other words, the network size has mild dependency on the smoothness parameter and the optimal structure is automatically obtained without cross validation. This kind of automatic model selection ability has not been exploited in the existing literature. It somehow justifies why deep learning rarely overfit in practice. The theoretical characterization is well justified by numerical experiments.  

**Weakness:** The technical tools heavily depends on previous work such as Yarotsky (2017), Suzuki (2018) and Schmidt-Hieber (2020). Indeed, their proof essentially utilizes the parallel NN structure and does not require sparsity constraint (see also [1]). I also would like to point out that a non-sparse fully connected network structure is also investigated by [2]. It would be better that a comparison to this study is included.  
Another concern is that the regularization formulation and constraint formulation are not justified in a completely rigorous way.  

[1] Bolcskei, H., Grohs, P., Kutyniok, G., and Petersen, P. Optimal approximation with sparsely connected deep neural networks. SIAM Journal on Mathematics of Data Science, 1(1):8–45, 2019.   
[2] Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang: Deep Network Approximation for Smooth Functions. SIAM Journal on Mathematical Analysis, vol 53, number 5, pp.5465--5506, 2021. 

Although this paper has weakness as described above, this paper's main focus is in a different point, that is, the automatic sparse model selection which is a novel view point. The concern about the relation between penalty and constraint is addressed during the rebuttal period. Although it still requires some technical assumptions, the limitation of the analysis is well discussed by referring some experimental observation.  

In summary, this paper's novelty and significance are more valuable than the drawbacks. This paper's contribution is informative for the community. Hence, I recommend acceptance. 
justification_for_why_not_higher_score: As I wrote in the summary section, this paper's novelty is rather limited. The parallel structure has been implicitly exploited by Yarotsky (2017), Suzuki (2018) and Schmidt-Hieber (2020). There are some theoretical ambiguity in the connection between the regularization formulation and constraint formulation. 
justification_for_why_not_lower_score: This paper's main message is novel. The automatic model tuning and its statistical optimality is an important topic in the literature. The theoretical finding is well justified by the numerical experiments.  
The original submission had some minor issues as pointed out by the reviewers, but they were mostly addressed during the rebuttal. Then, the paper's quality became sufficiently good for acceptance.
Decision: Accept: poster