Rethink Depth Separation with Intra-layer Links
Authors: FENGLEI FAN
Zeyu Li
Huan Xiong
Tieyong Zeng
Venue: Submitted to ICLR 2023 (2023)

Abstract: The depth separation theory is nowadays widely accepted as an effective explanation for the power of depth, which consists of two parts: i) there exists a function representable by a deep network; ii) such a function cannot be represented by a shallow network whose width is lower than a threshold. Here, we report that adding intra-layer links can greatly improve a network's representation capability through the bound estimation, explicit construction, and functional space analysis. Then, we modify the depth separation theory by showing that a shallow network with intra-layer links does not need to go as wide as before to express some hard functions constructed by a deep network. Such functions include the renowned "sawtooth" functions. Our results supplement the existing depth separation theory by examining its limit in a broader domain. Also, our results suggest that once configured with an appropriate structure, a shallow and wide network may have expressive power on a par with a deep network. 

Under review as a conference paper at ICLR 2023
RETHINK DEPTH SEPARATION WITH INTRA-LAYER LINKS
Anonymous authors Paper under double-blind review
ABSTRACT
The depth separation theory is nowadays widely accepted as effective explana- tion for the power of depth, which consists of two parts: i) there exists function representable by deep network; ii) such function cannot be represented by a shallow network whose width is lower than threshold. Here, we report that adding intra-layer links can greatly improve a network's representation capability through the bound estimation, explicit construction, and functional space analysis. Then, we modify the depth separation theory by showing that a shallow network with intra-layer links does not need to go wide before to express some hard functions constructed by a deep network. Such functions include the renowned "sawtooth" functions. Our results supplement the existing depth separation the- ory by examining its limit in a broader domain. Also, our results suggest that once configured with an appropriate structure, shallow and wide network may have expressive power on a par with deep network.
INTRODUCTION
Due to the widespread applications of deep networks in many important fields (LeCun al. 2015), mathematically understanding the power of deep networks has been central problem in deep learn- ing theory (Poggio et al., 2020). The key issue is figuring out how expressive deep network is or how increasing depth promotes the expressivity of neural network better than increasing width. In this regard, there have been plethora of studies on the expressivity of deep networks, which are collectively referred to as the depth separation theory.
popular idea to demonstrate the expressivity of depth is the complexity characterization that intro- duces appropriate complexity measures for functions represented by neural networks (Pascanu et al. 2 et al. [014]] Telgarsky| (2015) Montúfar [217]] [Serra et al., 20188] Hu Zhang 2018
Xiong et al. [2000] Bianchini & Scarselli [014]] Raghu al. 2017), and then reports that increasing depth can greatly boost such complexity measure. In contrast, a more concrete way to show the
power of depth is to construct functions that can be expressed by a small network of a given depth, but cannot be approximated by shallower networks, unless its width is sufficiently large (Telgarsky)
2015 2016 Arora et al. 2016 Eldan & Shamir 2016 Safran & Shamir 2017, Venturi al.. 2021
For example, Eldan & Shamir (016) constructed a radial function and used Fourier spectrum anal-
network can represent it with polynomial number of neurons, but a one-hidden-llyer network needs an exponential number of neurons to achieve the same level of error. Telgarskky (2013) employed ReLU network build mieddnmnnioonal "sawtooth" function whose number of pieces scales exponentially over the depth. As such, a deep network can construct sawtooth function with many pieces. while shallow network cannot unless it very wide. /Arora eet al. (2016) derived the upper bound of the maximal number of pieces for univariate ReL.U net- work, and used this bound to elaborate the separation between deep and a shallow network. In a broad sense, we summarize the elements of establishing depth separation thcorem the following: i) there exists a function representable by a deep network; ii) such a function cannot be represented by shallow network whose width is lower than a threshold.
ysis show that two-hidden-lan
The depth separation theory is nowadays widely accepted as an effective explanation for the power of depth. However, argue that depth separation does not hold when slightly adjust the struc- ture of the shallow networks. Our investigation is on ReLU networks. As shown Figure [c), inspired by ResNet that adds residual connections across layers, we add residual connections within

---

Under review as a conference paper at ICLR 2023
layer, which forces neuron to take the outputs of its neighboring neuron. Then, find that insert- ing intra-layer links can greatly increase the maximum number of pieces represented by a shallow network. As such, wide as before, a shallow network can express as a complicated function as a deep network could. Our result is valuable in two aspects. On the one hand, it non-trivially supplements the depth separation theory. In reality, neural network often is not feedforward but uses shortcuts link distant layers fa- cilitate feature reuse and easy training. Ex- ploring the depth separation in the shortcut paradigm reveals the limit of the existing theory and motivates us to rethink the gen- uine power of depth. On the other hand, the superiority of depth over width nowadays seems become doctrine for most deep Figure I: (a) feedforward, (b) residual, and (c) learning practitioners. However, studies such as width-depth equivalence (Fan et al. (020) and rep- resentation ability of wide networks (Lu al. 2017 Levine al., 2020) show the essential role of width. In the same vein, our work suggests the potential of wide networks in expressivity. Once configured with an appropriate structure, a shallow and wide network may have expressive power on a par with a deep network. Note that adding intra-layer links is not equivalent to increasing depth. The common understanding of increasing depth is to increase the number of layers, while intra-layer links are just to connect neurons in the same layer, which is slight change to the original network.
modify the statement of depth separation: without the need of going as
feedBorword
resichal
(c)
feedEooward
Intra-tiiled
Specifically, our roadmap to the modification of depth separation theorems includes two milestones. 1) Through bound analysis (Theorems 4 6 8). explicit construction (Propositions I and 3), and functional space analysis (Theorem 10p, we substantiate that network with intra-layer links can produce much more pieces than feedforward network, and the gain is at most exponential, i.e., (g) where à is the number of hidden layers. 2) Since intra-layer links can yield more pieces, they can be used to modify depth separation theorems by empowering a shallow network to represent function constructed by deep network, even if the width of this shallow network is lower than the prescribed threshold. The modification is done in the cases of 122 vs 3 (Theorem 12) and 122 vs k (Theorem 13 the famous sawtooth function (Telgarsky) 2015)). Also, we point out that the depth separation cannot be fully accomplished based on the bound analysis, unless the bound is proved to be tight. Thus, Arora et al. (2066)* 's depth separation theorem might need to be re-examined.
To summarize, our contributions are threefold. 1) We point out the limitation of the depth separation and propose to consider inserting intra-layer links in shallow networks. 2) We show via bound estimation, explicit construction, and functional space analysis that intra-layer links can make ReLU network produce more pieces. 3) We modify the depth separation result including the famous Telgarsky (2015)'s 's theorem by demonstrating that a shallow network with intra-layer links does not need to go as wide before to represent function constructed by deep network.
RELATED WORK
Recently, plethora of depth separation studies have shown the superiority of deep networks over shallow ones from the points of view of complexity analysis and constructive analysis.
The complexity analysis is characterize the complexity of the function represented by neu- ral network, thereby demonstrating that increasing depth can greatly maximize such a complexity measure. Currently, one of the most popular complexity measures is the number of linear regions because it conforms to the functional structure of the widely-used ReLU networks, For example,
Pascanu et al. (2013); Montufar al. (2014); Montúfar (2017): Serra al. (2018); Hu & ZZang (2018); Hanin & Rolnick (2019) estimated the bound of the number of linear regions generated by a fully-connected ReLU network by applying Zaslavsky's Theorem (Zaslavsky 1997). Xiong et al. 2020) offered the first upper and lower bounds of the number of linear regions for convolutional networks. Other complexity measures include classification capabilities (Malach & Shalev- Shwarzzz 2019), Betti numbers (Bianchini & Scarselli/ 2014), trajectory lengths (Raghu et al.) 2017), global curvature (Poole et al. (0166), and topological entropy (Bu et al.) 2020). Please note that using complexity measures to justify the power of depth demands tight bound estimation. Otherwise,
2

---

Under review as a conference paper at ICLR 2023
it is insufficient to say that shallow networks cannot be powerful deep networks, since deep networks cannot reach the upper bound.
The construction analysis is to find family of functions that are hard to approximate by a shallow network, but can be efficiently approximated by a deep network. Eldan & Shamir (2016) built a special radial function that is expressible by 3-layer neural network with a polynomial number of neurons, but a 2-layer network can do the same level approximation only with an exponential number of neurons. Later, |Safran & Shamir (2017) extended this result to ball function, which is a more natural separation result. |Venturi et al. (202) |) generalized the construction of this type to a non-radial function. Telgarsky (2015) 2016) used an O network construct a sawtooth function. Given that such function has an exponential number of pieces, it cannot be expressed by an (kk)-ayee network, unless the width is ((exp(k)). [Arora et al. (2016) estimated the maximal number of pieces a network can produce, and established the size-piece relation to advance the depth separation results from (k? k:) to (k:, k'), where k' < k. Other smart constructions include poly- nomials (Rolnick& & Tegmark| 2017). functions of compositional structure (Poggio et al. 2017 Gaussian mixture models (Jalali et al. 2219), and so on. Our work also highlights the construction, and we an intra-linked network to more efficiently build sawtooth function.
NOTATION AND DEFINITION
Notation 1 (Feedforward networks). For an wo - R ReLU DNN with widths Wi,-.., Wk of k p (wo)
= =x E R to denote the input of the network. Let f, (1) s( W = 1,... k, be the vector composed of outputs of all neurons in the i-th layer, for i = 1....,,, k. j 1,.... .....,. Wh
hidden layers, we use fo [66") ................................ 50
a (i) f(-1) + 6(5) to denote the pre-activation of the j-th neuron of the i-th layer, where a. (1) IR 1 (b E IR are parameters. Then f15)) = (gg()) (g.0)) where (-) is the ReLU activation. The output of this network is gk+1 = (ax, f()) + bR. where ag E &R. by E IR are parameters.
9,
Notation 2 (Intra-linked networks). For an R - R ReLU DNN with every 2 paired neu- rons linked in each hidden layer and widths wi,..., Wi of k hidden layers, use fo .o.....,, [(w)]] = R to denote the input of the network. Let f, (()) f be the vector composed of the neurons in the i-th layer, then for = 1,...,,,,,,,,,,,,,,,,,,, k. = 1, Wi, we use -f (1) f.-1) ) + to denote the pre-activation of the j-th neuron in the i-th layer, where (1) E R ((6) E IR are some parameters. In an intra-linked network, the j-th and (j + 1))th neu- rons are linked, and the (j + 2) and (j + 3) neurons are linked, we prescribe f(o)) = a (9.))
p(mns) E R
(1)
(gl (2)+ F(5+3) (g/5+3) f(6+22). Similar with the classical network, the output of the network is 5k+1 āe,, fr. br, where âs E IR "e, dy E TR. are parameters.
fo+)) σ (o( /. f fl5+2)
Notation 3 (Sawtooth function). A piecewise linear (PWL) function sawtooth" shape, if g = (-1)n=1 (z- 1)- b-a) br²), , E [nn - 1). N n. [ for n E [N].
[a, b] + i of "N-
b-a
Definition 1 (Width and depth of feedforward network (Arora et al. 2016 For any number of hidden layers l E N, imput and output dimensions wo, Wk+11 E N, an _00 gg++ feedforward network is given by specifying sequence of k natural numbers W1, W....., wh representing widths of the hidden layers. The depth of the network is defined as 1. The width of the network is max {wi....,wp?
Definition 2 (Width and depth of a shortcut network (an et al. II, we delete the minimum number of links to make the resultant network II' a feedforward network without isolated neurons. Then, we define the width and depth of II as the width and depth of II'.
2020)). Given a shortcut network
Admittedly, defining the width and depth of a network embedded with shortcuts is tricky. A rea- sonably good definition should conform to the customary understanding of depth and width. For
3

---

Under review as a conference paper at ICLR 2023
example, the ResNet (He al., 2016) shall not be taken as wide network in the light of the pro- posed defimition; otherwise. it conflicts with practitioners' common sense. Our definition for width and depth can fit the common sense for the network that is formed by slightly modifying a feed- forward network, 6.g. ResNet, DenseNet (Huang et al. 2017). and S3Net (Fan et al. (018). Per definition, the width and depth of intra-linked networks also max (w1;-..5 wk and k + 1,
respectively, the same as the width and depth of the corresponding feedforward network.
4 RETHINK THE DEPTH SEPARATION WITH INTRA-LAYER LINKS
Since our focus is the network using ReLU activation and related estimation of the number of pieces, the seminal depth separation theorems closest to us are the following:
Theorem 1 (Depth separation k.2 k (Telgassky] 2015 2016). For a natural number k 2 1, there exists a sawtooth function representable by an IR + R (2k² + 1)-layer feedforward ReLU DNN of width 2 such that it is also representable by a (k + ( (k + layer feedforward ReLU DNN should at least have the width of 1.
ReLU DNN, this
Theorem 2 (Depth separation vs k' (Arora et al. 2016).. For every pair of natural numbers k > 1, w 2 2, there exists a function representable by an IR - R (I- - 1y-layer feedforward ReLU DNN of width w such that if it is also representable by a (K'' + +)-llayer feedforward ReLU DNN for
any k S k, this (K' + 11)layee feedforwarr ReLU DNN has width at least f
Despite being one-dimensional, the above results convincingly reveal that increasing depth can make ReLU network express much more complicated function, which is the heart of depth separation. Here, we shed new light on the depth separation problem with intra-layer links. Our primary ar- gument is that if lntra-layer links shown in Figure (c) are inserted, there exist shallow networks that previously cannot express some hard functions constructed by deep networks now can do the job. Our investigation consists of two parts. First, we substantiate that adding intra-layer links can greatly increase the number of pieces via bound estimation, explicit construction, and functional space analysis. Then, adding intra-layer links can empower the shallow networks to represent com- plicated functions such sawtooth functions, without the need of going wide as before.
4.1 INTRA-LAYER LINKS CAN INCREASE THE NUMBER OF PIECES
4.1.1 UPPER BOUND ESTIMATION
Lemma 3. Let IR + be a PWL functin with w + pieces, then the breakpoints of (g) consists of two parts: some old breakpoints of g and at most w + newly produced breakpoints. Furthermore, has w + 1 new breakpoints if and only if g has w + distinct zero points.
Proof. A direct calculus.
Theorem (Upper bound of feedforward networks). Let J : TR be PuI.function represented by an R + TR ReLUU DNN with depth k + 1 and widths w.....; WK of l hidden layers. Then J has at most 1= (w; + 1) number of pieces.
This bound is the univariate case of the bound: Ih Ej= ( derived in Montúfar 2017) for n-dimennional inputs. In Appendix B we offer constructions to show that this bound is achievable in a depth-bounded but width-unbounded network (depth=3) (Proposition 4 and width-bounded (width=3) but Septh-unbbunded network (Proposition 5) in one-dimensional space. Previously many bounds (ascanu et al. (2013): Montufar et al./ (2014); Montúfar (2017): Xiong et al.] (2020) on linear regions were derived, however, it is unknown that these bounds are vacuous or tight, particularly for networks with more than one hidden layer. What makes Propositions and 5 special that
they for the first time substantiate that Montúfar (2017)'s bound is tight over three- layer and deeper networks, although these results are for the one- miedimmnsioonal case.
Remark 1 (Sharpening the bound in (Arora et al. (0166)). Previously, Arora al. (0016) computed the number of pieces produced by a network of depth k 1 and widths W1,... wi as 2 (w1 + 1) Wy. The reason why their bound has exponential term is that when considering how ReLU activation increases the number of pieces, they repetitively computed the old breakpoints generated in the previous layer. Our Lemma 3 implies that the ReL.U activation in fact cannot
4

---

Under review as a conference paper at ICLR 2023
generate many double pieces. Since Arora et al. (2016)'s 's bound is loose, their depth separation theorem needs to be re- ex-amiinddd.
Lemma 5. Let 91. R + IR be two PWL.funciin with totally w breakpoints. Set fi := a (g1) and f22 == = (02 f.). Then the breakpoints of f2 consist of three parts: some breakpoints of 92, some breakpoints of f1. and at most 2w + 2 newly produced breakpoints. Furthermore, f2 has 2w + 2 newly produced breakpoints if and only if 92 - SI has 2w + distinct zero points.
Proof. A direct corollary of Lemma
Let us illustrate why the intra-linked architecture can produce more pieces. Given two PWL fune- tions 91 and 92 which has totally w breakpoints, in the feedforward architecture, (g1) ) and (g2) have totally at most 3w + 2 breakpoints, which contains at most w old breakpoints of g1, 92 and at most 2w 2 newly produced breakpoints. However, in the intra-linked architecture, (g2 0 (g)) can produce more breakpoints because (g)) has two states: activated or deactivated. Then, o (g)) and a (g2 - (g1)) consist of at most w old breakpoints of gt 92 and (w + 1) + (2w + 3w+ newly produced breakpoints.
Theorem 6 (Upper bound of catra-linked networks). Let f R - R be PWL represented by a ReLU DNN with depth k + 1, widths W1. Wk. and every two neurons linked in each hidden
layer as Figure [c). Assuming that Wi,..., Wy are even, f has at most II (2w; + 1) pieces.
Proof. We prove by induction on k. For the base case k we assume for every odd j. the neurons j(,) and _ (()+1) are linked. The number of breakpoints of f( j = 1,..., w1, is at most 2 + (-1)². Hence, the first layer yields at most 3
2 W1 + pieces. For the induction step, we assume that for some & 1, any R - R ReLU DNN with every neurons linked in each hidden layer, depth k and widths WT.... Wi of & hidden layers produces at most I (gw; +1) pieces. Now we consider any R - R ReLU DNN with every two neurons linked in each hidden layer, depth k and widths W1, ..., wk+1 of ls hidden layers. By the induction hypothesis, each 0k41 has at most II ww: 1) breakpoints. Then the breakpoints of a (oh21) consist of some breakpoints of ((4 and at most IT (3w; + 1) newly generated breakpoints. Then g6 - (()
has at most 2- IT. (:w; 1) breakpoints, based on Lemma 5 The breakpoints of 7(++1) -k+1
/k11
(1+1)
- consist of some breakpoints of 9k+1
((++1) Jk+1 and at most 2 1I
(Zw; + 1)
a
newly generated breakpoints. Note that ((4) I.. Ie+1
(2*+1) have totally at most 11 (Zw: + - -1
breakpoints. In all, the number of pieces we can therefore get is at most
1 Wk+1
II
w; +
2
II
(
2 Wi +
+1))
II
3 wi +
1)
k+1
II
2 wi
3
1
2
2
In the following theorems, offer the bound estimation for high-dimensional cases. The detailed proof for Theorem is put into Appendix A
Theorem 7 (Upper Bound of Feedforward Networks (Montúfar 2017)). ). Let f : R" + R be PWL function represented by an R. + R. ReLU DNN with depth k and widths wi.... Wy. of le hidden layers. Then f has at most II Ej=o (19:) linear regions.
Theorem 8 (Upper Bound of Intra-linked Networks). Let f R" + E be a PWL function rep- resented by an In -> IR ReLU DNN with every two neurons linked in each hidden layer, depth k k+1 and widths WI,..., ww of le hidden layers. We assume each wi is even. Then f has at most Surs +1) linear regions.
Ih ET
Remark 2. Although both adding a new layer (going deep) and adding intra-layer links involve composition, their mechanisms of producing pieces are fundamentally different. While the mech- anism of going deep is the repetition effect (multiplication). i.e., the function value of the function being composed is oscillating, and each oscillation can generate corresponding pieces. The mech- anism of intra-layer links is the gating effect (addition). The neuron being embedded have two activation states, and each state is leveraged by the neuron being linked to produce a breakpoint. Such mechanism essentially conforms to the parallelism, which is of width paradigm.
5

---

Under review as a conference paper at ICLR 2023
4.1.2 EXPLICIT CONSTRUCTION.
Despite that the bound estimation offers some light, to convincingly illustrate that intra-layer links can increase the number of pieces, we need to supply the explicit construction for the intra-linked networks. The number of pieces in the construction should be bigger than either the upper bound of feedforward networks or the maximal number feedforward network can achieve. Specifically, the constructions for intra-linked networks Propositions aand have a number of pieces larger than the upper bounds of feedforward networks. In Proposition by enumerating all possible cases, present a construction for an link- network of width and arbitrary depth whose number of pieces is larger than what feedforward network of width 2 and arbitrary depth possibly achieves.
T
Proposition 1 (The bound I (Sws +1) is tight for a two-hidden-layer intra-linked network). Given an R IR Iwo-hidden-layye
2
ReLU network, with every two neurons linked in each hidden layer, for any even W1 2. 6. W22 2 4, there exists a PWL function represented by such network,
whose number of pieces is 1321 + 1) ( + +1.
Proof. To guarantee the bound II,- (Sm + 1) is tight, the following two conditions should be
g(6++1 - f( have as many zero points as possible so that a(o!²) and ao (()) can produce the maximal number of breakpoints; (ii) all old breakpoints of
satisfied:
(i) Di and 93
=(i)
(1(1) (w.) are reserved by 0/41 an affine transform of { (Tt)) ...... f(ws)
99
9;
We first consider the first hidden layer. Let
() = a (gx 27) (x) - f -1 {1
(3) = 0-22 + 2), [(0) (x)= = --x + 2 J (x)
(x) - (-3x - 12), (x) =0
(-2x +8 1 (x)
When w1 = 6, we set g = (()) - 2(2) + 2/11
23)
+ ((1) - - -110)
-4
let ((0) o (-5 - aj 3)), / f(++1)
When W1 6, for each odd j
(- az) f()) where aj 2
19
9 (1 3), then the output of the first layer is
expressed as the following:
(()) 7(2) +
(3)
((4)
(5)
7(6)
W2
( (2 + slt!i).
g - 9
2
7
T= odd
which has w + pieces and whose adjacent pieces have slopes of opposite signs. Note that any line y fills the conditions of Lemma 5
where E (-13/2,-6) can cross all pieces of ğ + b. Thus, g ful-
We divide the breakpoints of ÿ into two parts: B Bupper = {æ is a breakpoint of ğ and g(x) b} and Blower = {x is a breakpoint of ÿ and g(x) S b). We refer to their counts as #B upper and # #Blower, respectively.
J2
2
7(4
W
-5
0
10 -5
0
10
10
-5
5 10
Figure 2: The PWL functions that reach the bound of Proposition 1 when wt = 6, W22 = 4.
Next, we construct the second hidden layer. f == (ī + b,), where by E (-13/2,-44 -6). has
W1 + new breakpoints. Then by choosing some scaling parameter a E (0, bias by to fulfill
Lemma 5
we can also make ağ + ba 1 f((1) has 3wl 2 distinct zero-points, which implies )
6

---

Under review as a conference paper at ICLR 2023
a ( (ag + bg - ) has 3w1 + 2 newly produced breakpoints. Therefore, the affine combination
of 22 and f22) contains all breakpoints of B Bappers and has #B #Bupper + ( w + +1) + (3w) + 2) breakpoints. To reserve all the breakpoints of g. do the similar thing for - gain f/2 and
7 whose affine combination has # Btower + (3 w2 + 1) + (3mm + 2) breakpoints, which contains all breakpoints in Blower, and shares no breakpoints with the affine combination of (22 ((2)
Hence, the affine combination of 2())
7(2) 3 _/ has #Buppr # Blower + 2- ( + 1) +
J2
2 (3w1 + 2) 3um
6
+ 1) breaking points, which contains all the breakpoints of g- visualized in Figure 2 Repeating this procedure by selecting different
3101
{122) 11 22 1
7(4)
bi, a, b2, we can construct the remaining (F22 Jiss such that the affine transformation of ( (()) 1 has pieces of
3
3wz
(3
2 th + +1) +1
[3w'
2 + +1)
(3mz
(
3u2z 2 +
2 11
2
Proposition 2 (Use intra-linked networks to achieve a sawtooth function with IT== (2m pieces).
There exists a [0, 1] + TR function represented by an intra-linked ReLU DNN with depth k + 1 and width Wi...., Wk of k hidden layers, whose number of pieces is at least 3w. 3wn.
2
2
Proof. Let o(x)= defined over [o, A]. The core of the proof is to use one- mee-hidden-laye network of w neurons to create 2
3 pieces from d(z).
p + jC
Fi) + f()) / 700
28
25
8
0
28
36
48
58
68
4
0
8
28
38
45
56 66 4
3
(())
o(x 8)
( a(x (00 7 8)
2
000 d(2x 86)
f(9 0(2x - F(0)
28
28
2A
8
28 38 46
58
4
28 45 55
8 26 38 46 58 65 A'
Figure 3: A schematic illustration of how to use an intra-linked network to generate a sawtooth function.
Let 8- = 2A
3w Set g(2) = 36 - 35, f()) = a (g g(2) = Φ. f(2) = a (g - f(u) + 6).
and ((2i+1) 40 4(3j 1)5, f(2)+1) a (g(2 g(2)+2) 20 -666, f(25+2)
g(22)2) - f(2s+1) for all j = 1, l,..... L,..,,// The output of this one-hidden--ate layer network is
#-1
1 f()) + ((2) - Σ
(-1)) ( -
-x) (x = 3
j=1
......3w// 1. which has 3w pieces on 10, Aj. (x) is of slope (-1)3 on Li,, (j + 1)8). 0 3w/2 and ranges from 0 to on each piece. Figure 3 shows how the affine transformation of [. f(2) f(3), f(4) constructs sawtooth function of pieces. Please note that flipping d(x) or translating d(x) will not prevent (o(z)) from generating 30 pieces.
The targeted intra-linked ReLU network with depth + and width wI...., We of hidden layers is designed as
Esc,w, ESu-1 Esgao (x),
7

---

Under review as a conference paper at ICLR 2023
where A; = 1/ (I Jwr
Proposition (Intra-layer links can greatly increase the number of pieces an R ReLU network with width 2 and arbitrary depth). Let f R - R be PWL function represented by an + R (k + 1)-layer ReLU DNN with widths 2 of all k hidden layers. Then number of pieces of f is at most
if k is even,
if k is odd. There exists an R + R (k+ + 1a-leyer 2-wide ReLU DNN, with neurons linked in each hidden layer, which can produce at least 7 38 - + pieces.
3
Proof. The proof is put in Appendix
4.1.3 FUNCTIONAL SPACE ANALYSIS
The above constructive analyses demonstrate that in the maximal sense, intra-layer links can em- power feedforward network to represent function with more pieces. Now, we move one step forward by showing that intra-layer links can surprisingly expand the functional space of a feed- forward network. The reason why this result is surprising is that one tends to think an intra-linked network produces an exclusively different function from a feedforward network. However, here report that an intra-linked one- mme-iddenn-laee network of two neurons express a feedforward one-hidden-laye network of two neurons (Lemma 9). and the opposite doesn't hold true. Further- more, given arbitrary feedforward ReLU network, adding intra-layer links in the first layer can definitely expand its functional space (Theorem I0p.
f(²) = a (al2)x + ((2)) , = c(0 + c(2) + d, where a (2) (0,01),(0)) (0,), and d E R. there exists some a(1), a(2), BB,, ((2), 20,2), and E I such that z()(()) + cl2) f(2) + d, where f()) a (a + +b(1) f(2) (o00x+b+e b(2) f(i).
Lemma 9. Let f()) a (x + (())),,)))))))))
Proof. Without loss generality, we assume (1) (2)
and
(())
60)
Then is of slope
ats
0, (2)), and (2)) + (2)) on -xx
M2)
and
ata 0 respectively.
a
anyy
Now we choose 20))a (2))) satisfying 0 < (11)
< (2) and set ((0)
a(t) = 1,2. Then a
F(I) is of slope 0 and ((1) (-oc,- 8(4)
and
a00+ respectively, while f(2) is of slope
6(4)
a(l)
O, a(2), and a(2) - ((1) on -000- (())
6(2)
atT 00 respectively. Hence, à a(1))) /a and d d, we have ((2) (a(2)
60 and 601)
203
let ((2) (2) (2(2) a(1)
(c(1) a (1)
(2)
a0)) f()) + ((2) 2 f(2) + d.
Theorem 10. Let f be any R + R PWL representable by a classical (k + 1)-layer ReLU DNN with widths wi > 2...., Wk of hidden layers. Then, can also be represented by (k + 1)-layer ReLU DNN with widths wI...., Wp of hidden layers, with neurons in the first layer linked.
Proof. Let the output of the j-th neuron of the first layer in the feedforward network be f()(x)= (0()))) [a('++D()
1, b....,,,, w1. Since the feedforward network is invariant to permutating neu- rons, we can link the arbitrary j-th and j'tth neuron if af a("")) (3") 0, which directly concludes the proof according to Lemma
Df)).. (("))
4.2 MODIFY THE DEPTH SEPARATION THEOREM WITH INTRA-LAYER LINKS
In a broad sense, the depth separation theorem consists of two elements: i) there exists a function representable by deep network; ii) such function cannot be represented by shallow network whose width is lower than a threshold. Since adding intra-layer links can generally improve the capability of network, if one adds intra-layer links to shallow network, the function constructed
8

---

Under review as a conference paper at ICLR 2023
by a deep network can be represented by a shallow network, even if the width of this shallow network still lower than the threshold. Theorems 12 and 13 modify the depth separation k2 vs and h2 vs k, respectively, by presenting that shallow network with intra-layer links only needs to go times as wide as before to express the same function.
Lemma 11 (A network with width=2 can approximate any univariate PWL function Fan et al. 2018 ). Given a univariate PW with n pieces p(z), there exists a (n + 1y-layer network D with two neurons in each layer such that f(z) = -(z).
Theorem 12 (Modify the depth separation k2 vs 3). For every k 2 2, there exists a function p(x)
that can be represented by (k2 + 1)-layer ReLU DNN with 2 nodes in each layer, such that cannot be represented by a classical 3-layer ReLU DNN Wa(x) with width less than k - 1, but can be represented by 3-layer, 2(k-1) - intra-linked ReLU DNN Wz(x).
Proof. Combining Theorem 4 Proposition and Lemma 11 straightly concludes the proof.
Theorem 13 (Modify the depth separation h22 k). For every 2 1, there is a [0. + R PWL function p(æ) represented by a feedforward 212+1))laye ReLU DNN with at most nodes in each layer, such that it cannot be represented by a classical (k + 1y-layer ReLU DNN Wx(z) with width less than 6*, but can be represented by a (Is + 1lllayer intra-linked ReLU DNN Wx(x) with width no more than 4 6
Proof. Per Telgarsky 2016)'s is construction, a feedforward (2k² + 1)-layer ReLU DNN with at
most 2 nodes in each layer can produce a sawtooth function of 2* pieces. Similarly, a feedforward (2k² + layer ReLU DNN with at most 6 nodes in each layer can have 6*²² pieces. Thus, it follows Theorem that any classical (k: + 1)-layer ReLU DNN (x(x) with width less than 6th generate 6* pieces. However, according to the construction in Proposition | let W1 = W22 =
cannot
Wk= 4 6--1 intra-linked network can exactly express a sawtooth function with 6** pieces.
Remark 3. Theorems 12 and 13 implicate that intra-layer links can reduce the bar of the width
by 1/3, Although it is not an exponential reduction, our highlight is the existence of such shallow networks that can be transformed by intra-layer links to have the representation power on a par with deep network. Such shallow networks go against the predictions of depth separation theory. Furthermore, suppose every n, neurons are intra-linke in the i-th layer, the upper bound of the
number of pieces by a network of & hidden layers with widths wi...., wy is IT (mn+1)w, + 1). Therefore, by intra-linking more neurons, the bar of the width be substantially reduced, and more shallow networks will become counterexamples of the depth separation theory.
2
5 DISCUSSION AND CONCLUSION
Please note that intra-layer links are an extension of residual connections. The former is to link the neurons inside a layer, while the latter is to connect neurons across layers. We take the intra-layer links as vertical residual connections, while the shortcuts of ResNet (He et al.] (016)) are horizon- tal residual connections. It is widely recognized that horizontal residual connections can facilitate networks in the dimension of depth, e.g., the residual connection solves the training issues of deep networks and allows the network to go very deep. In contrast, our theoretical results show that ver- tical residual connections can promote the representation capability of networks in the dimension of width, e.g., the network with intra-layer links does not need go as wide as before represent the same function. By leveraging the capabilities of a network in both width and depth domains, we believe that the synergy of horizontal and vertical links in a network will further contribute to more powerful networks. More favorably, both horizontal and vertical links do not incorporate new parameters; therefore, their synergy is likely to enhance model efficiency.
In this draft, via bound estimation, dedicated construction, and functional space analysis, we have shown that a network with intra-layer links is much more expressive than a feedforward one. Then, we have modified the depth separation results to that a shallow network that previously cannot express some functions constructed by deep networks now can do the job with intra-layer links. Our results supplement the existing depth separation theory, and suggest that the potential of wide networks can be released by an appropriate structure. Future endeavors can be put into training wide networks using intra-layer links to achieve comparable performance with deep networks.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 16 2016.
Monica Bianchini and Franco Scarselli. On the complexity of neural network classifiers: A compar- ison between shallow and deep architectures. IEEE transactions on neural networks and learning systems, 25(8):1553-1565 2014.
Kaifeng Bu, Yaobo Zhang, and Qingxian Luo. Depth-width trade-off's for neural networks via topological entropy. arXiv preprint arXiv:2010.07587, 2020.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. Conference on learning theory, pp. 907-940. PMLR, 2016.
Feng-Lei Fan, Rongjie Lai, and Ge Wang. Quasi-qquivalence of width and depth of neural networks. arXiv preprint arXiv:2002.02515. 2020.
Fenglei Fan, Dayang Wang, Hengtao Guo, Qikui Zhu, Pingkun Yan, Ge Wang, and Hengyong Yu. On a sparse shortcut topology of artificial neural networks, 2018.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, pp. 359-368, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Qiang Hu and Hao Zhang. Nearly-tight bounds on linear regions of piecewise linear neural networks. arXiv preprint 1rXiv:1800.1111 2018.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinherger. Densely connected convolutional networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4700-4708, 2017.
Shirin Jalali, Carl Nuzman, and Iraj Saniee. Efficient deep learning of gmms. arXiv preprint arXiv:1902.05707, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv: 14X2.644/2.6980. 2014.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553))36-444, 2015.
Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua. The depth-to-widd interplay in self-attention. arXiv preprint arXiv:2006. 12467, 2020.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: a view from the width. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6232-6240, 2017.
Eran Malach and Shai Shalev-Shwartz. Is deeper better only when shallow is good? Advances in Neural Information Processing Systems, 32, 2019.
Guido Montúfar. Notes the number of linear regions of deep neural networks. Sampling Theory Appl., Tallinn, Estonia, Tech. Rep, 2017.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Advances in neural information processing systems, pp- 2924-2932, 2014.
Razvan Pascanu, Guido Montufar, and Yoshua Bengio. On the number of response regions of deep feed forward networks with piece-wise wise linear activations. arXiv preprint arXiv: 1312.6603 2013.
10

---

Under review as a conference paper at ICLR 2023
Tomaso Poggio, Hrushikesh Mhaskar, Lorenzo Rosasco, Brando Miranda, and Qianli Liao. Why and when can deep-but but not shallow-networks avoid the curse of dimensionality; a review. Inter- national Journal of Automation and Computing, (4(5):503-519) 2017.
Tomaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceed- ings of the National Academy of Sciences, 1 17(448)33039-30045 2020.
Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein, and Surya Ganguli. Exponen- tial expressivity in deep neural networks through transient chaos. Advances in neural information processing systems, 29, 2016.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On the pressive power deep neural networks. In international conference on machine learning, pp- 2847-2854. PMLR, 2017.
David Rolnick and Max Tegmark. The power of deeper networks for expressing natural functions. arXiv preprint arXiv:1705.0553 2017.
Itay Safran and Ohad Shamir. Wepth-width tradeoffs in approximating natural functions with neural networks. International conference on machine learning, pp. 2979-2987. PMIR, 2017.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pp. 4558- 4566. PMLR, 2018.
Richard P. Stanley. An introduction to hyperplane arrangements. In Lecture Notes, IAS/Park City Mathematics Institute, 2004.
arXiv preprint Matus Telgarsky. Representation benefits of deep feedforward networks.
arXiv:1509.088 08101, 2015.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp- 1517-1539. PMLR, 2016.
Luca Venturi, Samy Jelassi, Tristan Ozuch, and Joan Bruna. Depth separation beyond radial func- tions. Journal of Machine Learning Research, 2021.
Huan Xiong. Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. In International Conference Machine Learning, pp- 10514-10523. PMLR, 2020.
T. Zaslavsky. Facing up to arrangements : face-count formulas for partitions of space by hyper- planes. Number 154 in Memoirs of the American Mathematical Society. American Mathematical Society, 1975.
T Zaslavsky.. Facing up to arrangemenss: face-count formulas for partitions of space by hyperplanes. Memoirs of American Mathematical Society, 154:1-95 1997.
11

---

Under review as a conference paper at ICLR 2023
A PROOF OF THEOREM 8
Lemma (Zaslavsky's Theorem Zaslavsky 1975); Stanley (2004). Let A= (H; CV: s
m) be an arrangement in R Then, the number of regions for the arrangement A satisfies
((A)
(2)
==0
Proof. We prove by induction on For the base case 1, fi 2(21-1) σ []] (g( pro-
duces one hyperplane the input space R". Furthermore, F(20)
(21)) ((21-11)
(g(T0 - अ ()) produces at most two hyperplanes in the input space IR" Therefore, in to-
3em tal, the neurons in the first layer produces (1 + 2) 2 3 hyperplanes in the input space RR.. Then by Zaslavsky's 's Theorem, it will produce at most Σ5=0
(wi+1) linear regions in the input space
R" For the induction step, assume that for some & 2 any R - IR. ReLU DNN with every two neurons linked in each hidden layer, depth l: + 1 and widths Wt, w. of l: hidden layers produces
at most II Eブ=
linear regions. Now we consider any IR" + R ReLU DNN with every two neurons linked in each hidden layer, depth k+ 2 and widths Wi,..., Wk+1 of k hidden layers.
(-+))
Sw:
Then for each linear region produced by the first
layers, again, jk+1
[h+1 pro-
duces one hyperplane S. Furthermore, ((20) = [ F = (g(3) a gh+1
2
produces at most hyperplanes in the S. Therefore, in total, the w neurons in the k layer produces + 2) Wk+1
3wg+1 hyperplanes in S. Then by Zaslavsky's Theorem, it will pro-
2
duce at most Σ/= ( (1)+1+1) linear regions in S. Thus f has most IL Σj= (す) regions.
Bass +1) linear
B SUPPLEMENTARY RESULTS FOR THE TIGHTNESS OF THEOREM 4
Proposition 4 (The bound IT (wi 1) is tight for depth-bounded but width-unbounder net- work). Given an R + R two-hidden-layer ReLU network, for any width wi 2 3, W2 2 2 in the first and second hidden layers, there exists a PWL function represented by such network, whose number of pieces is (w) + 1) (w2 + 1).
Breakpoints
Breakpoints
Breakpoints
0.2
g
-0.2
-0.2
-0.4
-04
-0.2
-0.6
00.6
Figure 4: Construction of PWL functions to reach the bound of Proposition when
3, W22 2.
Proof. To guarantee the bound II (w; + 1) tight, the following two requirements should be met: (i) each (² i 0, 1, j 1, ... wi, has distinct zero points that are much its number of pieces, so that the activation step can produce the most new breakpoints; (ii) the breakpoints of
each g 0, 1, 2, 1,.... 1i+1. as the affine combination of ((()) !.....!!!!! J. contains g (m)) }. so that all the old breakpoints are reserved.
f(w.) }
all the breakpoints g
(1)
Now we give the proof in detail. Let (() o3xx), o(-x +3), 33, 11)((() (3 2). When wi = 3, set
12

---

Under review as a conference paper at ICLR 2023
9
11) (
+ (2) {(3)
3 122
92
(1) (1) + (2) (3)
3 #2+
1
,
When w1 > 3, we let f(5 0 (-2x 2x 2 3)) and
0000 {11) (2)
11 11 (- -3 33- w2+1
0 = f + 222 - (3) + E (-1)r- j(() w2-1 : 2, =2...,, W2.
i
(1) has wh distinct zero points. Hence for 1, ,.... 12, the breakpoints of f Then 9
keeps all breakpoints of 92 (i) and yields wi 1 new breakpoints. Note that f2 and f( do
not share new breakpoints, and f and f( covers all the breakpoints of { (660 12 Therefore, the
j=1
((wa)) total number of pieces via an affine combination of (1)) 12...,12 is (Wi + 1) (w2 + 1) pieces. O
Proposition 5 (The bound IT (w: + 1) is tight for width-bounded but depth-unbounded net- work). Given an - R ReLU network with width w for the first layer and 3 for the other layers, for any depth k > 2, there exists PWLfumctin represented by such network, whose number of pieces is (w + 1) 4
Proof. Let ((D) .... )( be the same as in Proposition
((w)
4 Let
(2)
+ 1( 5 (3)
3,
if w =3
92
(( + (12) 11
1) -
{(8) 3, w
We set
1 (2 1)
f/2) a 92 33) 3) a (2 2
Now we continue our proof by induction. Assume we have constructed f((), -!²²) and f! 1 2. Then we set
9et1 = (1) + ((22)
(3)
6'
and
(1)
4+1 (20+41 50)
(2
a (- 6 (3)
f41 (0++1 + 87)
3
Through a direct caleulus, we know Øi+1 has (w + 1) 44-1 pieces with opposite slope in every two adjoint pieces and ranges from to 3/6' in each piece except the leftmost and rightmost piece, which implied we can totally obtain (w + 1) 4 pieces.
C PROOF OF PROPOSITION 3
Proof. For the first assertion, claim that each pre-activation 0,00) s 1,2, cannot have its every two adjacent pieces of slope with different sign, which implies the activation cannot produce the most breakpoints as in Lemma 3 In fact, 9 j 1,2, has at most 3 pieces. If some g2 has 3 pieces, then by exhaustion, we know either it has a 0-slope, or it has two adjacent pieces with slopes of the same sign (see Figure 5). Hence, f( j 1, has at most 2 newly produced breakpoints. Then the output of the 2-nd layer has at most + 2 x Applying the similar method each piece,
breakpoints, i.c., 7 pieces. get result via simple induction step.
13

---

Under review as a conference paper at ICLR 2023
(9)
(e)
(h)
(b)
(1)
(0)
(9)
Figure Exhaustion all possible shapes of 20
1, Proposition
Now we come to the second assertion. For convenience, we say R - IR PWL function f is of "triangle-trapy wtwe--trapi---iiaaanee shape on [a, b] C R. if there exists a partition of (a. bj a < 21 22 <
T6 < b and positive constant such that
if a, 25, b
flia,1 (z)
c
if æ Ii, 4B
3c
if E [ag, xz
linear connection
otherwise.
Given PWL function f: :R R of "triangl-trapeeziid-tiaaa shape on [a, b), with correspond-
ing partition a < 21 22 < Ta and f(a) = 0, if set
g (L) = 4f
g (2) 2
f(1) (g
f(2) (9(0) f())
then - f(2) + is of respectively.
shape on [a, x2). [m2, æs) and [xs, b]
Using this fact, we can construct PWL. function represented by (k + 1)-layer 2-wide intra-linked ReLU DNN, which has 7 - 2 + pieces. Actually, set
( o (2xx,
((2) = a x ((2) +1 +1) 9 (1) -4 +2,
92 -2
2((2) +
is of "ttiiangl-traapzzidd-iii trrannoli"-rrinee""" shape on [-1, 1]. Using the fact above repeatedly, we can construct PWL function represented by a R. - IR (A: + 1)- layer, 2-wide, intra-linked ReLU DNN, which constant on (-o0, -1] [1, oo) and of "triangle-
then through a direct calculus, ((1 + ((2)
trapezoid-triangle"" triangle" shape on -
-1 ((++1) n 3k.
D VALIDATING THE REPRESENTATION POWER OF INTRA-LINKED LINKS
Inspired by the encouraging theoretical analyses, validate whether the intra-layer links assist a network to deliver superior performance in real-world tasks. The task is to predict if a credit card holder will get churned so that the bank can provide better service to turn holders' decisions. This prediction task has 10,000 raw samples, and each has 18 customers' portfolio features including age, salary, marital status, credit card limit, credit card category, etc. The labels are 'get churned' or 'stay.. The detailed description of data and this task can be referred to in Kaggle
The data are preprocessed as follows: The discrete value assigned to different education levels based on the mapping { "Uneducated': 0, 'High School': 1, 'College": 2, 'Graduate': 3, 'Post- Graduate": 4, 'Doctorate': 5 }. The income situation is assigned with values based on the mapping:
"Les than $40K': 0, 'S40K S60K': "$0K $80K 2, 'S80K $120K: 3, '$120K +': 4
14

---

Under review as a conference paper at ICLR 2023
The female and male mapped to 0 and respectively, All samples with missing attributions deleted. Finally, the processed data have 7,081 data points. Then, the data are randomly split into training and testing sets with ratio of 0.8:0.2.
We build networks with intra-layer links and compare them with the corresponding feedforward networks without intra-layer links. The optimizer is Adam Kingma & Ba (2014) with learning rate of 0.1. The loss function is the binary cross-entropy function. The evaluation metric is the widely used micro-Fl score. The prediction results feedforward and intra-linked networks summarized in T from which we draw two highlights. First, when the same structure is used, the mtra-linked network consistently outperforms the feedforward network. More favorably, the intra-linked network takes the lead by large margin: the minimum gain is 1.68% for the network structure 2-32-2, while the maximum gain 2.66% for the network structure 2-16-166 16-6162. Such superiority corroborates our theoretical analysis that adding intra-layer links can boost the network's representation power. Second, the me-hidden-layer intra-linked network can sometimes perform superbly over the two-hidden-layer feedforward network (22-16-2 vs 22-8-8-2, 22-32-2 22-16- 16-2, 22-64-2 vs 22-32-32-2), when their parameters are comparable. This phenomenon suggests that the representation power of an intra-linked network is different from that of feedforward network with more layers.
Table 1: Credit card customers prediction by feedforward and intra-linked networks.
Feedforward
#Parameters
Micro-F1(%)
Intra-linked
#Parameters
Micro-F1
22-8-2
202
78.24+0.23%
22-8-2
202
80.13+ 0.377 %
22-16-2
402
78.93+0.19%
22-16-2
402
50.83+
22-32-2
802
80.53.10.18%
22-32-2
802
82.21 0.27%
22-64-2
1602
82.03:10.23%
22-64-2
1602
0..52.10.3499
22-8-8-2
274
80.21+00.32%
22-8-8-2
274
82.11+0..22%
22-16-16-2
674
81.14+0..3%%
22-16-16-2
674
83.80+
22-32-32-2
1858
83.14++..28%
22-32-32-2
1858
84.79+0.45%
22-64-64-2
5762
84.35.10.24%
22-64-64-2
5762
85.44.10.25%
E INSERTING INTRA-LAYER LINKS VS STACKING LAYERS
Here, we argue that adding intra intra-layer links is not equivalent to increasing new layer in the follow- ing three aspects:
he M Mechanism of G ener ating M More Pieces
AAN V
10
Adding Layers
g50 o())
Adding Intra Links
aff + a())
g g>0
of + g)
#AA fliee Transform, cttvvation
Adding Layers
a (W, b,) b2)
#Affine Transform, Activation)=2
aW, + b,)
fflnene Transform, Activation)=1
A Adding Intra Links oWW OoWsxx b,))
a (WW)+ + b, + b2)
#(fffine Transform, Activation==
Figure 6: Adding intra- layer links is not equivalent to increasing depth in terms of the mechanism of generating more pieces, the number of (affine transform, activation), and function classes.
As Figure shows, their mechanisms of producing pieces fundamentally different. While the mechanism of adding a new layer is the repetition effect (multiplication) i.e., the function value of the function being composed is oscillating, and each oscillation generate more pieces. The mechanism of intra-layer links the gating effect (addition). The neuron being embedded have two activation states, and each state is leveraged by the
15

---

Under review as a conference paper at ICLR 2023
neuron being linked to produce breakpoint. Two states integrated to generate more pieces.
Although both stacking a new layer and adding intra-layer links involve composition, they involve different numbers of (affine transform, activation). In a feedforward network, adding a new layer means the depth increases by 1, and the characteristic of stacking a new layer is doing the affine transformation followed by activation. As Figure T illustrrae,s, iilsteesllsssssesssss a feedforward network with two layers involves two times of (affine transformation, ac- tivation). In contrast, adding intra-layer links in fully-connected layer actually exerts gating effect. When a (W22 + b2) > O, the output is a(W, + W2)a + b + by); when oW22 + by) = 0, the output is ( z + bz). The number of (affine transformation, activation) is still one for both cases.
The function classes (the set of functions represented by some given neural network archi- tecture) of our intra-linked network and the deeper feedforward network are not the same, and this will make big difference. In some sense, the deeper feedforward network has larger function class, and the function class of our intra-linked network is just a subset of it. However,
network has more expressive power (i.e., number of pieces, VC dimension) per parameter. Also, the experiments showed that intra-linked networks can achieve better accuracy in solving real-world problems. This phenomenon can be as an analog to the comparison between CNNs and fully-connected NNs. The function classes of CNNs are just subsets of the function classes of fully-connected NNs with some further restrictions on the weights. However, CNNs usually have more expressive power per parameter and achieve better results in practice.
Topologically, one can define the depth of a network as the length of the longest path from the input to the output, by regarding a neural network as directed acyclic graph. With this definition, adding the intra-layer links certainly increases the depth by roughly a factor of two. However, we examine the operations along the longest path, based on the above second observation, the number of (affine transformation, activation) remains to be the same with the number of layers. Thus, the depth is defined as the number of (affine transformation, activation) that are actually executed, the depth of the intra-linked network is the same as that of the feedforward network. Since topologically one can make any shallow network deep by making a series of reducible identity layers, we argue that the intrinsic computational operation is more important than the extrinsic topology for the depth separation theory.
F EXTENSION TO MORE INTRA-LAYER LINKS
For an R + RE+t ReLU DNN with depth & + I, widths Wi,..., We of k hidden layers, We now assume that every n, neurons intra-layer linked, where n; can divide w, without remain- der. We use fo = fou fe [wo)
= E R to denote the input of the network. Let f (())) p(w:)] E TR.. then for i = 1, k, = 1,..,, ,,. Wh, we use g. = -(a()) f + to
denote the j-th pre-activation in the i-th layer respectively, where a. E B 1---116 1,60) E R are some parameters. In an intra-linked network, the j -th, ... (j + ny 1)-th neurons in the i-th layer linked, and the (j + n4)-th. ..., ...... (j+ 2n,- - 1) neurons in the i-th layer are linked. We prescribe
(() = -o (0)5)) ()) and f( 20+0 = a (g.5tt) - f(++1-1). for I = 1....,n n - 1. The output of the
axk Fa (1) = 1, WK+1, where a(1) E 1R 1 E R are parameters.
network is FR41
Theorem 15. Let f TR R be a PWI. wwn.ctonii represented by a R + R ReLU DNN with depth k+ I, widths Wi...., wk of k hidden layers and every n, neurons linked in the i-th hidden layer for some positive integer n4 that divides w, without remainder. Then f has at most I1k [1+11 w; + 1) pieces.
Proof. For convenience, we assume in the i-th layer, the j-th, (j n4 1)-th neurons linked, for = 1,.... ki = 1,.... W; 1. For the first layer, f(1) has one breakpoint and each 76) has most newly produced breakpoints and some old breakpoints of g(d) and f(1-1), for
16

---

Under review as a conference paper at ICLR 2023
j ...... M1. Hence, the first layer gives at most mi wo + pieces. Then the rest of the proof is similar to Theorem
Corollary 15.1. Let f R PWL.functin represented by a + ReLU DNN with all the neurons linked in each hidden layer, depth lo + 1, and widths wi..... Wy, of hidden layers. Then has at most I1 (1 w; +) pieces.
Theorem 16 (The bound 11 (w:+1)w
+1) is tight for a nee-hidden-layer intra-linked net- work). Given an -> R one saeehidden-llyee ReLU network with all neurons linked the hidden layer, there exists a functin represented by such a network, whose number of pieces is (an 1)m 1.
2
(()) d(w()x b(1)
f())
( = a(w + b(3) 1(y)
x x + (2)
(()
((0
( = (( + 199 ((2))
70)
w 66)
(()
f(t) = xl + 6:00 - fal)
F(
w b(4)
f(0
Figure The construction demonstrating that the bound II intra-linked network.
1)
is tight ame-hidden-layer
Proof. Without loss of generality, a one-hidden-layer network with all neurons intra- linked is math- ematically formulated as the following:
{
f(a) = x b(4) f6+1) a a(w() + 665) デ(ンg"
To prove that the bound II (wett)) + is tight for one- one-hidden- hiddded-e-lyyer network, the key is
make each fb) produce new breakpoints and have j non-zero pieces that share a point with = O. We use mathematical induction to derive our construction. Figure schematcallly illustrates our construction idea.
First, let 1t)) o(x + 1) and f(2) (0.5 x (I 2 - F()). Note that F()) has non-zero piece that shares point with y 0, and f(2) has 2 non-zero pieces that share common point with y 0.
Then, given (o)) j 2 2, we suppose fli) has j non-zero pieces that share point with 0. Since f6) is continuous, we select its peaks {[ppp (() (rrp:))] by the following conditions: i) f() is not differentiable Tp. ii) f() of 0. Next, let (x", (x*)) be the lowest peak of f6), As long as the slope w and the bias b(++) satisfy
200 (x*)
w(i+1)
++I
(4)
b(+1) =ws+1 (j+1))
17

---

Under review as a conference paper at ICLR 2023
w(++1)+++ bb++)) crosses and only crosses j pieces of f(). These pieces exactly non-zero pieces
that share point with y = Thus, plus the breakpoint w(+ f(++1) generates total of j + new breakpoints. At the same time, fl++1) has j + non-zero pieces that share point with y 0. Figure 7 illustrates the process of induction.
b(++))
Finally, the total number of breakpoints is Σ}=1 (wr wiww which concludes our proof.
Theorem 17
(An arbitrarily deep network of width=4 and with all neurons each layer intra-linked achieve at least 9 pieces). There exists an R - R function represented by intra-linked ReL.U DNN with depth k, width in each layer, and all neurons in each layer intra-linked, whose number of pieces is least gh.
Proof. The core of the proof is to use a one-hidden-laye to create quasi-sawtooth function with many pieces possible, We construct four neurons as follows:
mheuron-intrr-lnnneeeee network of width
fa) o (2x)
f(2) = (x + o (())
(5)
f(3) of ( + 2) f(2)
F(4) (x+ F(3))
The profiles of f()) f(2), f(3) f(I are shown in Figure a).
(a)
7
7:0
10
(- (-1.g)
36
1 5
(-2.g)
70)
2 18
700
- 3,0)
(-20)
(-
.))
(-1,0)
7.0
(0)0)
(1.0)
j(0)
7
1000
p0)
84
(- 2.g'
5
2
(1, 84
504
752
6
7
5
[0,
72
168
Figure 8: A schematic illustration of how to use an intra-linked network to generate a sawtooth function.
By combining f(), f f(3),, F(4) with carefully calibrated coefficients, have the following quasi-sawtooth function that has 9 pieces are
7( ((4)
(()
(2) +0x f().
84
As shown in Figure b), we have marked all breakpoints 17(x)) to validate its correctness.
Next, we just need to let each layer of the intra-linked network represent stretched and down-pulled variant of 17(z), e.g., the k-th layer 7/s (I) ()r)) - Br. where Mş a sufficiently large number and B& > 504 M₁ to ensure that 3, is within the function range of m) (z).
Finally, the constructed network is
Mi 77- 0010001 ..... o (z))
18

---

Under review as a conference paper at ICLR 2023
Theorem 18 (An arbitrarily deep network of width=3 and with all neurons in each layer intra-linked can achieve at least 5 pieces). There exists an - R function represented by an anrrallikkd ReLU DNN with depth k, width in each layer, and all neurons intra-linked in each layer. whose number of pieces is at least 5
Proof. Following the same spirit in proof of Theorem 17
we construct three neurons as follows:
{
f()] o (2x)
f( = (x + o(f(1) f(z) o (x + - f(2))
(8)
The target function that returns us 5 pieces is
{(x)
x (38
f(2) + f().
100
Next, we just need to let each layer of the intra-linked network represent stretched and down-pulled variant of ((r), e.g., the k-th layer (x) = TB mh (z) Ck. where Ti is sufficiently large number
and C2 > 200 Th + ensure that 2, 0] within the function range of (x()..
Finally, the constructed network is
Ex (()).
(10)
Remark 4. Suppose each layer has neurons; = W2 =.... = and = w, the upper bound of the intra-layer linked network is ((w+1)) 1)*, which approximately equals that of feedforward network with width wi of representation power by intra-links O(w) instead constant-level improvement. Thus, the separation is still valid if one allows increasing the width of feedforward networks by a constant factor.
(w++)w At this time, the improvement
...
(a) 2 nearons Intra-linked
(b) intmm-ansstttallliiii (b) all neurons linka
Figure 9: The improvement of representation power by intra-links is O(w) when all neurons layer are intra-linked.
Proposition 6 (Modify the depth separation 1.2 vs 2). For every 1: 2 2, there exists a function p(a)) that can be represented by (k2 + L)-layer ReLU DNN with 2 nodes in each layer, such that cannot be represented by a classical 2-layer ReLU DNN W2(z) with width less than k2 1, but can be represented by a 2-layer, (2k)-wide intra-linked ReLU DNN W2(x).
Proof. Combining Theorem
Theorem 16 and Lemma II straightly concludes the proof.
G ANALYSIS EXTENDED TO ONE-NEURON WIDE RESNET
Our analysis can be extended to ResNet show the power of residual connections. Let us use one-neuron-wiie wide ResNet to demonstrate this point. It is straightforward to see that a one-neuron- wide ReLU DNN represent PWL functions with at most three pieces, matter how deep the network is. However, we add residual connections to the network, which gives a ResNet, it can represent PWL functions with much more pieces.
19

---

Under review as a conference paper at ICLR 2023
Theorem 19. Let f :R R be PuL,function represented by a one-neuron-wide ResNet. Mathe- matically, f= Cx+1fk + 9ki where 91 (z) = z, fi = a (a:9s + b;) ,9+11 = 4.fi + 9s, Ck+1, Og bi, Cj parameters. for I...., k. Then f has most 2k pieces.
Proof. The first claim follows from Lemma and a simple induction step. Following the idea of the construction in Propositions and we set G 2 and a; for all and set b 0, b; = -
2-1++2 -+2 for = 2,...k k
Theorem 19 confirms that adding simple links can greatly improve the representation ability of network. Actually, both ResNet and intra-layer linked networks do not increase the number of parameters, but they can represent more complicated functions than the feedforward of the same neurons used in each layer. Hence, the linked structure can improve the efficiency of parameters. Besides, we can see from the proof of Theorem 19 that the idea and construction in analyzing intra- linked networks can indeed be utilized to analyze other architecture of networks.
20


Reviews:
[{"review_id": "kgmqKjmR4pm", "reviewer": "Reviewer_4Twm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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}$.", "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.", "strength_and_weaknesses": "Strengths:\n- Proposes novel theoretical architecture and does significant theoretical analysis of it's representative power in relation to shallow and deep networks\n\n\nWeaknesses:\n- 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "XWRpHtLDiBB", "reviewer": "Reviewer_EkgR", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.\nThey 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.\n", "summary_of_the_review": "The paper is an extension of existing theoretical results to a seemingly uninteresting architecture.", "strength_and_weaknesses": "Strengths:\n- the paper is clear\n\nWeakness:\n- 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.\n- 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LMQFE42r04", "reviewer": "Reviewer_p5Vt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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.", "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.\n\nUpdate after authors' response: I'm willing to increase my score after authors' response.", "strength_and_weaknesses": "Strength:\n- Studying the depth-separation theory with different architecture is an interesting direction, which may help us to have better understanding of different architectures.\n- The paper is well-motivated and overall is easy to follow.\n- The setup of the theoretical framework is clearly stated, some of the proof ideas are discussed and the proofs are provided.\n\n\nWeaknesses:\n- 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.\n- The improvement using intra-linked networks over standard feedforward networks seems to be not very strong in my opinion. For example, \n  - (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.\n  - (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.\n  - (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.\n  - (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)}$.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JupoRRsnJK", "reviewer": "Reviewer_GyBS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "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. \n2. 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 ", "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.\n\nBy 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. ", "strength_and_weaknesses": "Strengths:\n\nThis 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. \n\nWeaknesses:\n\n1. 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.\n2. 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. \n \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject