Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the representation cost of linear neural networks. Considering a target linear function with parameter matrix $B$, the authors investigate the effect of $\ell_2$ regularization in the predictor space. It is shown that a fully connected network regularizes the trace norm of $B$, diagonal network regularizes the $\ell_{1,2}$ norm of $B$, convolutional network regularizes a certain norm of the discrete Fourier transform of B, etc. The authors also discuss how one can design a linear neural network architecture to achieve certain regularization effects.

main_review: I think this paper offers some valuable insights into the effect of different neural network architectures. Although I did not check all the proof details, the results look solid. However, I think this paper still has some weaknesses that could be addressed. I have the following detailed comments.

1. The analysis in this paper stops at the calculation of the representation cost. However, it is not discussed how representation cost affects learning efficiency. It would be very helpful if the authors can give some examples of how the differences in representation cost affect the learning efficiency of linear networks.

2. The paper does not offer sufficient discussions. For example, homogeneity has been mentioned many times in the paper and seems to be quite essential. The non-homogeneous cases are also highlighted in the title. However, there seems to be no discussion on how homogeneity affects the analysis.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative social impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the induced regularization in predictor space of linear neural networks as a result of the weight decay (or $\ell_2$) regularization on the network parameters. The authors also identify the impact of the choice of architecture and parameterization on the induced regularization.
main_review: The paper is well written and seems theoretically sound. I also believe the paper contains valuable insights to better understand the impact of architectural choices on the induced regularizers. However, there are some issues that need to be addressed as detailed below:

- The paper only focuses on linear neural networks. I admit that most papers in the deep learning literature use linear networks as the theoretical surrogates of their nonlinear counterparts, however, I still believe that the authors should at least comment on the implications of this analysis for the architectures with nonlinear activations, e.g., ReLU. 

- I understand that this is a theory paper but I still wonder if the authors can verify some of their results via simple numerical experiments.

- There are several missing references that are closely relevant and require in depth discussion. First of all, [1] extends (Gunasekar, 2018) to multi channel cases and allows arbitrary kernel sizes. Also, [2] discusses linear convolutional networks and shows that the regularized training problem can be cast as a convex optimization problem with certain regularization penalties. Similarly, [3-5] discuss the analyze the structural choices such as the number of outputs, depth, the choice of architecture and derive the induced regularization for the conventional weight decay regularized training problem. Can the authors comment on these papers and discuss the similarities/differences?

__Minor comments:__

- Notation: use the standard notation: $W_l$ for layer weights, $n$: number of samples, $d$: feature dim, and $L$: depth of the network.

- I couldn’t find an explicit definition for $B$. Is it simply the multiplication of all layer weights?

[1] Jagadeesan M et al. "Inductive Bias of Multi-Channel Linear Convolutional Networks with Bounded Weight Norm" 

[2] Pilanci M, Ergen T “Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks” 

[3] Ergen T, Pilanci M “Revealing the Structure of Deep Neural Networks via Convex Duality”

[4] Ergen T, and Pilanci M. " Implicit Convex Regularizers of CNN Architectures: Convex Optimization of Two- and Three-Layer Networks in Polynomial Time." 

[5] Sahiner A et al. "Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms." 

===Post-Rebuttal Update===

I have read the authors’ responses carefully. I appreciate the responses. The responses clarify some of my minor concerns, however, I still think that the main contribution of this paper is incremental due to analyzing only linear networks and considering the prior works I mentioned. Therefore, I'd like to keep my assessment.

limitations_and_societal_impact: The authors adequately discussed the limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies various ways to parameterize linear neural nets and explore the regularization on the linear mapping (in terms of the final function obtained by multiplying all weight layers in the linear net) induced by l2 regularization in parameter space. 

A large number of architectures are studied -- fully connected deep networks, diagonal networks, convolutional networks, and residual nets, with a characterization of the induced regularization for each of these settings. In addition, the paper also studies how to construct architectures to induce a particular desired regularizer. First, they study \ell_p norms and show that the \ell_p norm can be the induced regularizer if and only if p = 1, 2, with structural requirements on the architecture of the network. They also analyze which architectures can induce \ell_{p, q} group norms. All of the results in this paper are for linear neural nets.
main_review: The strength of the paper is its thoroughness and attention to detail in terms of deriving precise theoretical results which characterize a variety of different settings. However, the clarity of the presentation could be improved, and the significance of these results are also unclear, since they only apply to linear networks. 

Originality: The results in Section 3.1 and 3.2, which focus on characterizing the induced regularizers of various architectures, are mild generalizations of the results of [Gunasekar et al. '18], and are thus not very surprising. The results in Section 4 are, to my best knowledge, novel. 

Quality: The theoretical claims are sound. 

Clarity: The paper is somewhat lacking in clarity. There is a lot of (perhaps unnecessary) complexity which probably detracts from the overall presentation of the paper; for example, Definition 1.1 appears overly complicated -- it's not quite clear why the equivalence classes are necessary. In another example of this, Section 4.2 is written abstractly in terms of general $\ell_p$ norms, but the positive results in Theorem 10 only apply to $\ell_1$ and $\ell_2$ norms anyways -- it's likely more clear if the Theorem were written explicitly in terms of these norms. In addition, the results rely on abstract concepts such as mixing depths (Definition 4.2) and grouping layers (Definition 4.3). Some intuitive examples or figures would go a long way in helping convey these definitions better. 

Significance: The impact of this work is limited because [Gunasekar et al. '18] already characterized a lot of the models in Sections 3.1 and 3.2 (with less generality), so the contributions in these sections alone are incremental and not enough for a strong paper. While the results in Section 4 are more novel, the stated motivation of developing architectures to induce various regularizers is not very convincing, because 1. there are probably more important concerns for architecture design, such as optimization and expressivity, and 2. an easier approach seems to be to directly regularize the desired induced regularizer. Thus, while the theory in this paper is nice, it's not clear how impactful it'll be.

================================================================================================

Thanks to the authors for the responses to this and other reviews. My assessment of this paper is the same. 
limitations_and_societal_impact: The authors do not address negative societal impact of their work -- this seems reasonable, given the theoretical nature of the work. However, the discussion of the limitations is quite lacking. The authors say that limitations are discussed in the conclusion, but the discussion appears to mostly be about extensions and future work, and not limitations of the current work.
review_title: null

Meta-review: There is consensus among reviewers that this paper sets out in an interesting direction, and that it is thorough and precise in its analysis, but that ultimately arrives at results of limited significance. I second several of the reviewers' suggestions for work that could improve the paper in a future revision, including relating representation cost to statistical efficiency and extending its scope beyond linear networks (at least in discussion or experiments, and even if focused on specific nonlinear activations such a ReLUs).

More generally providing some experimental verification may offer another promising avenue for this work. The paper ultimately explores the regularization effects induced by architectures, but as reviewer Hyxs highlights, it is not clear how this interacts with effects induced on optimization, and exploring that empirically may clarify natural questions from the reader about practical implications of this work. Finally, I'll underscore the suggestion from reviewer Hyxs to simplify what may be unnecessarily complex definitions.
Decision: Accept (Poster)