Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a theoretical modification of the dense feedforward network whereby each neuron in each layer in a densely connect feed forward network is paired with one other Neurons. The output of one Neuron in each pair is overwritten by the sum of the 2 linear outputs of both Neurons before being passed to the activation function. They demonstrate that for the same depth, intra-linked networks have the linear regions it could possibly represent is high. For $n$ dimensional input, $w$ widths, and $k+1$ layers, they derive a upper bound of $\prod_{i=1}^k{\sum_{j=0}^n\left(\frac{\frac{3w_i}{3} + 1} {j}\right)}$ for intra-linked vs a previous derived upper bound of $\prod_{i=1}^k{\sum_{j=0}^n\left(\frac{w_i} {j}\right)}$ for dense networks. They derive that for networks of width 2 and $k+1$ layers, a regular feed forward network can represent a sawtooth function with at most $\sqrt{6}^k$ if k is even or $3 \cdot \sqrt{7}^{k-1}$ pieces if k is odd. They show that furthermore, a intra-linked network of the same dimensions can produce a sawtooth function of at least $7 \cdot 3^{k-2}$ pieces. They derive a proof for all $k\ge1$, their exists a function represented by a classical network of width 6, and $k^2 +1$ layers that can't be represented by a classical $k+1$ network of width less than $6^k$  that can be represented by some intra-linked network of width less than $4 \cdot 6^{k-1}$. They derive a proof for all $k\ge2$, their exists a function represented by a classical network of width 2, and $k^2 +1$ layers that can't be represented by a classical 3 layer network of width less than $k-1$  that can be represented by some intra-linked network of 2 layers with width of $\frac{2(k-1)}{3}$.
strength_and_weaknesses: Strengths:
- Proposes novel theoretical architecture and does significant theoretical analysis of it's representative power in relation to shallow and deep networks


Weaknesses:
- This theoretical architecture would not be difficult to implement, so the work may benefit from a real implementation and comparison with dense networks on at least a toy example.

clarity,_quality,_novelty_and_reproducibility: I can't adequately judge the clarity of the mathematical theorems and proofs, but the major findings and description of the proposed architecture could be introduced a bit more clearly. I believe the work is quite novel.
summary_of_the_review: This work proposes novel theoretical architecture and does significant theoretical analysis of it's representative power in relation to shallow and deep networks. Unfortunately, I don't believe I can very accurately judge the importance and accuracy of the mathematical theorems and proofs introduced in this paper. The work tackles an important area of furthering our theoretical understanding the expressive power and effectiveness of deep networks and suggest towards further research in the domain of shallow networks. The architecture is not very complicated however, and seems like a basic experimental demonstration should be quite feasible, but is currently not provided.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: In this paper the authors theoretically investigate the representation function of a class of neural networks, which as far as I know is novel, that they call intra-linked ReLU DNN.
They define intra-linked ReLU DNN as a modification of a standard feed-foward ReLU multi-layer perceptron, and they prove variations of the separation theorems of Telgarsky (2015) and Arora et al. (2016) that relate width and depth, showing that their intra-linked ReLU DNN has a small constant multiplicative improvement over a standard ReLU DNN.

strength_and_weaknesses: Strengths:
- the paper is clear

Weakness:
- Contrary to what is claimed in the paper, I think that the architecture being presented is essentially equivalent to a standard ReLU DNN with twice depth and weight matrices in a specific form.
- I fail to see the relevance of this work. It focuses on an unusual network architecture which, as far as I can tell, is not used in practice and seems to have been invented by the authors. There are no obvious benefits in using such architecture, in fact it would likely result in higher implementation complexity and/or a performance loss. The theoretical improvement is small and probably not worth just increasing the depth of a standard implementation of a ReLU DNN.

clarity,_quality,_novelty_and_reproducibility: - I haven't checked the proofs in detail, but the paper is quite clear.
- As far as I can tell the result is novel extension of previously known theorems, albeit this novelty is likely due to the type of architectures being investigated not being useful or interesting.
- Reproducibility doesn't apply since this is a theoretical paper.
summary_of_the_review: The paper is an extension of existing theoretical results to a seemingly uninteresting architecture.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 1. This paper proves that introducing intra-layer links to the neurons of the same layer allows the network to represent piece-wise linear functions with more pieces, via both upper-bound estimation and explicit construction. Furthermore, by introducing intra-links to the first layer, the new network can represent any function representable by the old network, and more. 
2. This paper modified the previous depth separation results by showing that to represent a function constructed by a deep network, a shallow network with intra-layer links only needs 2/3 of the width required for a normal shallow network 
strength_and_weaknesses: Strengths:

This paper is well-written and the theory is sound. It shows that just adding very simple intra-layer links to the neurons (without adding any new parameter) can already significantly increase the representation power of the network. Most previous works on depth separation focus on fully connected neural networks. This work supplements those previous results by considering a network with intra-layer links. 

Weaknesses:

1. I cannot agree with the authors' definition of network depth. If we view a neural network as a directed acyclic graph, then I think its depth is just the length of the longest path from the input to the output. With this definition, adding the intra-layer links certainly increases the depth of the network by roughly a factor of two. Therefore, I view the addition of intra-layer links as a particular way of increasing depth, which is still different from stacking more layers in feed-forward networks. From this perspective, I think this paper shows that increasing the network depth in a very simple and restricted manner (intra-layer links) can still increase the network's representation power. This paper mentioned that adding intra-layer links and stacking more layers though both increase the representation power, have a very different mechanism for doing so. Although a short remark was given, it might be better to explain more and maybe add figures to illustrate the different effects between intra-layer links and stacking more layers on the piece-wise linear function.
2. I found the motivation of this paper not very clear. There are many different ways to increase the network depth other than simply stacking more layers, why do we want to analyze the addition of intra-layer links? This kind of intra-layer link is not used in practice. 
 



clarity,_quality,_novelty_and_reproducibility: Clarity:
This paper is well-written. The definitions, assumptions, and theorems are clearly stated.

Novelty:
As far as I know, this paper is the first to analyze the effects of intra-layer links in representation power.

Reproducibility:
I think the theoretical results are sound and reproducible. 
summary_of_the_review: This paper shows that adding intra-layer links to a network can increase its representation power. Since most previous works on depth separation have focused on feed-forward networks, this paper supplements the literature by considering a different architecture.

By a standard definition of network depth, adding intra-layer links does increase network depth. Since there are so many different ways to increase network depth other than stacking more layers, the motivation for considering the addition of intra-layer links is unclear to me.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, authors revisited the depth separation theory of deep neural networks. While most of the previous paper focused on feedforward networks, this paper studied feedforward networks with intra-layer links. The authors showed that such ReLU networks with intra-layer links can increase its representation power compared with standard ReLU feedforward networks, in the sense that the required width to represent certain function could be reduced.
strength_and_weaknesses: Strength:
- Studying the depth-separation theory with different architecture is an interesting direction, which may help us to have better understanding of different architectures.
- The paper is well-motivated and overall is easy to follow.
- The setup of the theoretical framework is clearly stated, some of the proof ideas are discussed and the proofs are provided.


Weaknesses:
- The studied intra-linked networks are different from commonly used network architectures like feedforward networks and ResNet-type networks with shortcuts. It is not clear to me whether such analysis could be used on more commonly used networks in practice.
- The improvement using intra-linked networks over standard feedforward networks seems to be not very strong in my opinion. For example, 
  - (1) the results in Section 4.4.1 are all upper bounds on the number of linear pieces for ReLU networks with or without intra-links. Since they are only upper bounds, I don’t think these could give a valid separation. Moreover, even these upper bounds are tight, the separation seems to be not strong, since we are comparing $\Pi_i (3w_i/2 +1)$ with $\Pi _i(w_i +1)$ (the number of linear pieces), which means it is possible that a slightly wider feedforward network has the same representation power as network with intra-links.
  - (2) In Section 4.1.2, the separation only applies to feedforward ReLU networks and ReLU networks with intra-links under the *exact same* depth and width. It is not clear to me whether the separation is still valid if one allows to increase the width of feedforward networks by a constant factor (say 2). I currently tend to believe that the separation does not hold in such cases, which makes me to view the separation not strong enough. Please correct me if I am wrong.
  - (3) In Section 4.1.3, it is only shown that every standard feedforward ReLU networks can also be represented with a network with intra-links and same depth and width. I would not view this as a valid separation result.
  - (4) In Section 4.2, Theorem 12 and 13 show that the improvement on width from using feedforward networks to intra-linked networks are from $k-1$ to $2(k-1)/3$ and from $6^k$ to $4*6^{(k-1)}$. These improvement does not significantly change the representation power of networks in the sense of the order remains to be $O(k)$ or $e^{O(k)}$.

clarity,_quality,_novelty_and_reproducibility: Clarity:
- The paper is overall well-written and easy to follow.
- Minor question: in the end of remark 1, I was wondering if further elaboration could be made to clarify what exactly “needs to be re-examined”.

Quality:
- The theoretical results are clearly stated with full proof provided in the appendix.


Novelty:
- Study the representation power of deep networks with different architectures is an interesting direction. The intra-linked networks studied in this paper seems to be new in the literature.


Reproducibility:
- This is a theoretical work so there are no experiments to reproduce. Full proofs are provided in the appendix, but I didn’t check them.

summary_of_the_review: In summary, this paper studied the representation power of the intra-linked deep networks and showed certain separation results with standard ReLU networks, which I believe is an interesting result. However, as mentioned in the weakness part, the separation results do not seem to be very strong, which is my main concern. Therefore, I’m currently leaning towards rejection.

Update after authors' response: I'm willing to increase my score after authors' response.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers neural networks with intra-layer connections and how they change the results of depth separation. The main result of the paper shows that for a network with some intra-layer connections (in particular, for pairs of nodes in a layer, connect one to another), even though the number of parameters is not larger, it can represent some functions (used in depth separation constructions) with fewer layers/neurons compared to standard fully connected neural networks. After the author response period, the authors added some results extending intra-layer connections to a more general setting, some basic results for resnet (with 1 neuron per layer) and some empirical justifications for the architecture. The reviewers agree that there are some new ideas in the architecture and results. However, the improvement in depth/number of neurons is not very significant especially in the original setting (for example the gaps in Theorem 12/13 are not more than a constant factor). It would be interesting to see if there is possibility for a larger gap, or if there can be results for resnet which is widely used.
justification_for_why_not_higher_score: The theoretical results are not particularly strong - the improvements are only in terms of constant factors in width.
Decision: Reject