Functional vs. parametric equivalence of ReLU networks
Authors: Mary Phuong
Christoph H. Lampert
Venue:  (2020)
Keywords: ReLU networks
symmetry
functional equivalence
over-parameterization

Abstract: We address the following question: How redundant is the parameterisation of ReLU networks? Specifically, we consider transformations of the weight space which leave the function implemented by the network intact. Two such transformations are known for feed-forward architectures: permutation of neurons within a layer, and positive scaling of all incoming weights of a neuron coupled with inverse scaling of its outgoing weights. In this work, we show for architectures with non-increasing widths that permutation and scaling are in fact the only function-preserving weight transformations. For any eligible architecture we give an explicit construction of a neural network such that any other network that implements the same function can be obtained from the original one by the application of permutations and rescaling. The proof relies on a geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are of independent interest.


Published as a conference paper at ICLR 2020
FUNCTIONAL VS. PARAMETRIC EQUIVALENCE OF RELU NETWORKS
Mary Phuong & Christoph H. Lampert IST Austria
Am Campus 1, Klostemeuburg. Austria
(bphuong, chi j @ist.. ac.at
We address the following question: How redundant is the parameterisation of ReLU net- works? Specifically, we consider transformations of the weight space which leave the func- tion implemented by the network intact. Two such transformations are known for feed- forward architectures: permutation of neurons within a layer. and positive scaling of all incoming weights of neuron coupled with inverse scaling of its outgoing weights, In this work, show for architectures with non-increasing widths that permutation and scaling are fact only function- function-preserving weight transformations. For any eligible architec- ture we give an explicit construction of neural network such that any other network that implements the same function can he obtained from the original one by the application of permutations and rescaling. The proof relies geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are independent interest.
INTRODUCTION
Ever since its early successes, deep learning has been a puzzle for machine learning theorists. Mul- tiple aspects of deep learning seem at first sight to contradict common sense: single-hidden-laye networks suffice to approximate any continuous function (Cybenko 1989; Hornik et al. 1989), yet in practice deeper is better; the loss surface is highly non-convex, yet it can be minimised by first-order methods; the capacity of the model class is immense, yet deep networks tend not to overfit (Zhang et al. 2017).
Recent investigations into these and other questions have emphasised the role of over- is now known that over-
parameterisation, or highly redundant function representation. parameterised networks enjoy both easier training (Allen-Zhu al. 2019 Du al. 2019 Frankle & Carbin 2019), and better generalisation (Belkin et 2019 Neyshabur et al. 2019 Novak et al., 2018). However, the specific mechanism by which over-parameterrisatoon operates is still largely mystery.
In this work, we study one particular aspect of over-paramettrisaaion,, namely the ability of neural networks to represent a target function in many different ways. In other words, we ask whether many different parameter configurations can give rise to the same function. Such a notion of parameteri- sation redundancy has so far remained unexplored, despite its potential connections to the structure of the loss landscape, as well as to the literature on neural network capacity general.
Specifically, we consider feed-forward ReLU networks, with weight matrices WI...., W. and biases b bı.- We study parameter transformations which preserve the output behaviour of the network fzz) W ( 1-10 (. Wiz + bj ... + by-1) + b, for all inputs in some domain Z. Two such transformations are known for feed-forward ReLU architectures:
1. Permutation of units (neurons) within a layer, i.c. for some permutation matrix P,
W < (WW
b + Pb;
(1)
W P-11P-1
(2)
2. Positive scaling of all incoming weights of a unit coupled with inverse scaling of its out- going weights. Applied to a whole layer, with potentially different scaling factors arranged into diagonal matrix M, this can be written as
W MW.
b, Mb;
(3)
W W M-1
(4)

---

Published as a conference paper at ICLR 2020
Our main theorem applies architectures with non-increasing widths, and shows that there no other function-preservve parameter transformations besides permutation and scaling. Stated formally:
Theorem 1. Consider bounded open nonemply domain Z. C TR and any architecture d 2 2. dp = For this architecture, there exists ReLU network he 2 R, or equivalently setting of the weights 0 - bi...... L. bL), such that for any 'general' ReLU network by + R (with the same architecture) satisfying ho(2) hon (z) all E 2, there exist permulation matrices PI.... Pr.-1, and positive diagonal matrices MI,..., Mr.11, such that
(do...., d1) with do 2 d1 2
W1 = M,P.V W
b M.Pib
W. M,P, WIP.WPPT MIP.WWPT.
b, M,P,b/
1E (2...., L -11.
(5)
W = W.PL W
by b'2,
where n WW W2. b'z) are the parameters bup
In the above, 'general' networks is a class of networks meant to exclude degenerate cases. We give more precise definition in Section 3 for now it suffices note that almost all networks are general.
The proof of the result relies on a geometric understanding of prediction surfaces of ReLU networks. These surfaces are piece-wise linear functions, with differrentiabblitiss or 'folds' between linear regions. It turns out that folds carry lot of information about the parameters of a network, so much in fact, that some networks are uniquely identified (up to permutation and scaling) by the function they implement. This is the main insight of the theorem.
In the following sections, we introduce in more detail the concept of a fold-set, and deseribe its geometric structure for subclass of ReLU networks. The paper culminates in proof sketch of the main result. The full proof, including proofs of intermediate results, is included in the Appendix.
2 RELATED WORK
The functional equivalence of neural networks is well- researchhd topic in classical connectionist literature. The problem was first posed by Hecht-Nielsen 1990), and soon resolved for feed-forward networks with the tanh activation function by Chen et al. (1993), who showed that any smooth transformation of the weight space that preserves the function of all neural networks is necessarily a composition of permutations and sign flips. For the same class of networks, Felfermma & Markel (1994) showed a somewhat stronger result: knowledge of the input-output mapping of neural network determines both its architecture and its weights, up to permutations and sign flips. Similar results have been proven for single-layer networks with a saturating activation function such as sigmoid or RBF Kūrková & Kainen| 1994), as well as single-layer recurrent networks with smooth activation function (Albertini & Sontag 1993a b).
To the best of our knowledge, no such theoretical results exist for networks with the ReLU activation, which is non-saturating, asymmetric and non-smooth. Broadly related the recent work by Petersen et al. (2018) () and [Berne et al. (2019) who study whether two neural networks (ReLU or otherwise) that are close the functional space have parameterisations that are close in the weight space. This is called inverse stability. In contrast, we are interested in ReLU networks that are functionally identical, and ask about all their possible parameterisations.
In terms of proof technique, our approach is based on the geometry of piece-wise linear functions, specifically the boundaries between linear regions. The intuition for this kind of analysis has pre- viously been presented by |Raghu et al. (2017) and SSeraa et al. (2018), and somewhat similar proof techniques to ours have been used by Hanin & Rolnick| in the context of counting the number of linear decision regions.
Finally, the sets of equivalent parametrisations can be viewed as symmetries in the weight space, with implications for optimisation. Multiple authors, including e.g. Neyshabur et al. (2015): Badri- marayanan et al. (2016); Stock et al. (2019), have observed that the naive loss gradient is sensitive to reparametrisation by scaling, and proposed alternative, scaling-invariant optimisation procedures.
2

---

Published as a conference paper at ICLR 2020
3 RELU NETWORKS
This section introduces notation and two important classes of ReLU networks that we refer to throughout the manuscript. We denote by the ReLU function: a(u); max (0, u; for i [dim(u)]; the subscript index denotes the corresponding vector element.
Re with do 2 2 be nonempty open set, and let 0 - WL, by) be the network's parameters, with W, Rd 1, b E R4,, and dz = 1. We denote the corresponding ReLU network by he 2 where
ReLU network. Let 2
he - hg oo o h1g o o..
(6)
and h1 (z) Wi 1 bb. For S < L, also introduce notation for truncated networks,
hg
lbk & h h k- ... o hgg
We will omit the subscript 0 when it is clear from the context.
General ReLU network. In this work, we restrict our attention to so-called general ReLU net- works. Intuitively, general network is that satisfies number of non-degeneracy properties, such as all weight matrices having non-zero entries and full rank, no two network units exactly cancelling each other out, etc. It can be showr that almost all ReLU networks are general. In other words, a sufficient condition for ReLU network to be general with probability one is that its weights are sampled from distribution with density.
More formally, general ReLU network is one that satisfies the following three conditions.
1. For any unit (1, i), the local optima of h1 do not have value exactly zero.
2. For all k < and all diagonal matrices (Ia,..., , I)) with entries in {0, 1}.
rI, ... I W&) = min {dx rank(I.)) [Ix),.... rank(I;-1), rank(I.))
(8)
3. For any two units (1, i), (k; any linear region R, C Z. of 112 and any linear region
R2 C 2 of hji the linear functions implemented by h,d on Ri and h on R2 are nor multiples of each other.
General networks are convenient to study, they exclude many degenerate special cases.
The second important class of ReLU networks are so-called transparent networks. Their signifi- cance as well their name will become clear in the next section. For now, state the definition.
Transparent ReLU network. A ReLU network h 2. -> R is called transparent if for all Z. and E [L 1). there exists E [di] such that h (z) 2 0. In words, we require that for any input, at least unit on each layer is active.
FOLD-SETS
In this section we introduce the concept of fold-sets, which is key to our understanding of ReLU networks and their prediction surfaces. Since ReLU networks piece-wise linear functions, great deal about them is revealed by the boundaries between individual linear regions. A network's fold-set is simply the union of all these boundaries.
More formally, is an open set, and : > R is any continuous, piece-wise linear function, we define the fold-set of f. denoted by F(f), the set of all points which f is non-differentiable.
turns out there is a class of networks whose fold-sets are especially easy to understand; these are the ones have termed transparent. For transparent networks, have the following characterisa- tion of the fold-set (which also motivates the name 'transparent'..
See Appendix, Lemmas A.10
A.11 and A.12

---

Published as a conference paper at ICLR 2020
Figure I: piece-wise linear surface of order one, two and three
Lemma 1. Ifh 2 a general and transparent ReLU network, then
F(h) = U (z ( (z) 03.
1,8
To appreciate the significance of the lemma, suppose function h and we want to infer its parameters. This lemma shows that the knowledge the end- to-end mapping & 2 in fact gives us information about the network's hidden units hid' (hence 'transparent'). Moreover, this information is very explicit: observe the units' zero-level sets, which in the case of a linear unit on a full-dimensional space already determines the unit's parame- ters up scaling[] Of course, dealing with piece-wise linearity and disambiguating the union into its constituent zero-level sets remains a challenge for upcoming sections.
given some transparent ReLU network
5 PIECE-WISE LINEAR SURFACES
In this section, provide geometric description of fold-sets of transparent networks. Intuitively, the fold-sets look like the sets shown in Figure The first-layer units of network are linear, so the component U. / = 0} of the fold-set (9) is union of hyperplanes, illustrated by the blue lines in Figure T These hyperplanes partition the input space into a number of regions that each correspond to a different activation pattern. For fixed activation pattern, or equivalently on each region, the second-layer units are linear, so their zero-level sets U, {z h (z]:((z) = 0) are composed of piece-wise hyperplanes on the partition induced by the first-layer units. This shown by the orange lines in Figure]) 1. More generally, the layl zero-level sets U, {z h/ 0} consist of piece-wise hyperplanes on the partition induced by all lower-layer units. This yields a fold-set that looks like the set in the right pane of Figure 1 but potentially much more complicated.
We now define these concepts more precisely.
Piece-wise hyperplane. Let be partition of Z. We say H 2. piece-wise hyperplane with respect to partition P. if H is nonempty and there exist (w, b) o (0,0) and P P such that H (z E P TTz + 03.
Piece-wise linear surface. A set C called a piece-wise linear surface on Z of order it has a representation of the form S = Ule[s) HC, where each Hi is piece-wise hyperplane with respect to the partition induced by Uke Ht and no number smaller than & admits such a representation.
Using these definitions, the following lemma formalises the intuition behind Figure Lemma 2. If h is general and transparent ReLU network, then its fold-set is piece-wise linear surface of order at most L
"See Appendix, Lemma A.19
' similar figure has appeared the work of Raghu al. 2017
4

---

Published as a conference paper at ICLR 2020
Figure 2: A piece-wise linear surface with few intersections be- tween piece-wise hyperplanes. From the fold-set alone (right) it is not possible to determine if hyperplane emerged from the first layer (left, blue) or from the second one (left, orange).
Figure 3: Greedy layer as- signment to the piece-wise linear surface in Figure
The final ingredient we will need to able to reason about the parameterisation of ReLU networks is more precise characterisation of the fold-set, in particular, the dependence structure between individual piece-wise hyperplanes. For example, consider the piece-wise linear surface in Figure] and compare it to the one in Figure 2 Suppose before that the blue hyperplanes come from first-layer units, the orange hyperplanes come from second-layer units, and the black hyperplanes come from third-layer units. The difference between Figure and Figure that if observe only the fold-set, i.e. only the union of the zero-level sets over all layers (as shown in the right pane of Figure then in the case of Figure it impossible know which folds come from which layers. For instance, the blue folds and the orange folds could be assigned to the first and second layer almost arbitrarily; there is not enough information (i.e. intersection) in the fold-set to tell which is which. In contrast, the piece-wise linear surface in the right pane of Figure could in principle be disambiguated into first-, second- and third- layer folds by the following procedure:
1. Take the largest possible union of hyperplanes that is subset of the fold-set, and assign the hyperplanes to layer one.
2. Take all piece-wise hyperplanes with respect to the partition induced by the first-layer folds, and assign them to layer two.
3. Take all piece- wise hyperplanes with respect to the partition induced by the first- and second- layer folds, and assign them to layer three.
This procedure is not guaranteed to assign all folds to their original layers because it ignores how piece-wise hyperplanes connected; for example for the piece-wise linear surface in Figure the procedure yields the layer assignment shown in Figure However, it is sufficient for our purposes, and it easier to work with mathematically.
Formally, for a wisc linear surface S, we denote
g = ( C 8 8 is a piece-wise linear surface order at most R.).
(10)
One can show that S i is itself piece-wise wise linear surface of order at most k. so one can think of SgS the 'largest possible' subset of 8 that is piece- wise linear surface of order at most k. For the piece-wise linear surface in Figure 3 the set 8 consists of the blue hyperplanes, [28 consists of the blue and the orange (piece-wise) hyperplanes, and 138 8.
This definition allows to uniquely decompose 8 into its piece-wise hyperplanes. Let $ = in terms its piece-wise hyperplanes. We say the rep-
Ure|s),<e(m)) Hy be any representation resentation is canonical if each yC} is distinct and Ule JC} S for all k [x]] One can show that such a representation exists and unique up to subscript indexing. Importantly, assigns unique 'layer' to each piece-wise hyperplane, its superscript.
*See Appendix, Lemma A.1
"See Appendix, Lemmas A.5 and A.6
5

---

Published as a conference paper at ICLR 2020
JC
JC2
HC
3C
H2
HC
J
JC
H
JC
J-2
HC
HQ
Hi
H
Figure 4: A picce-wise linear surface in canonical form and its dependency graph.
The dependency graph (see also Figure is way formally describe the dependencies between piece-wise hyperplanes.
Dependency graph. Let Ulelk) H. the canonical representation of The depen- dency graph of is the directed graph that has the piece-wise hyperplanes {3C 1,a vertices, and has an edge 3C + DCh iff I < k and relint HC cll & 0. That is, there is and edge HC + JC if H& 'depends on' 'bends at' HC.
MAIN RESULT
With all the necessary concepts in place, now put the pieces together and explain the proof idea behind the main result. We restate the theorem here for the reader's convenience.
Theorem 1. Consider bounded open nonempty domain Z C iR and any architecture (du...., de) with du 2 d1 ... 2 d 2 2, dj = 1. For this architecture, there exists ReLU network he 2 + such that for any general ReLU network h, chitecture) satisfying hz(z) = hz,(z) for all z E 2, there exist permutation matrices P.....P. PI.-1. and positive diagonal matrices MI,..., M such that
R (with the same ar-
W1 M,P,W;
b M,P,b/. b: M,P,b/.
Wi P.P.WPP.MM
1E (2...,, L-
(11)
Wr = WTP, M
by =by.
where (W1, bi...., Wr, by) are the parameters of ha. and (W1 .,.... W', b'y) are the pa- rameters of hm:
In other words, for architectures with non-increasing widths, there exists ReLU network such that knowledge of the input-output mapping determines the network's parameters uniquely up to permutation and scaling.
The idea behind the proof is follows. Suppose we are given the function h. Then also know its fold-set Fhh), and if h is general and transparent, the fold-set a piece-wise linear surface (by Lemma the form Fhh U, {z [A. = 0}. As we have mentioned earlier, this union of zero-level sets contains a lot information about the network's parameters, provided we can disambiguate the union to obtain the zero-level sets of individual units.
This disambiguation the union crucial, is impossible in general. To see why, con- sider the first-layer units: given F(h). want to identify U, {zl h! (z) 0}. We know that U. [1.1(() = 0) union of di hyperplanes that is subset of DiF(h) union of dj hyperplanes, planes, such as for example in Figure In such a setting it is impossible to tell which hyperplanes come from the first layer.
if D)F(h) is are done. In general however, F(h) may contain more than di hyper-

---

Published as a conference paper at ICLR 2020
The key insight here is the following: even though. say, last-layer unit can create fold that looks like a hyperplane, this hyperplane cannot have any dependencies, or descendants in the dependency graph. This follows from the fact that the layer is the last. More generally, if (piece-wise) hyper- plane has a chain of descendants of length m, it must come from a layer that is at least m layers below the last one. Formally, have the following lemma.
Lemma 3. Let h 2 + R be general ReLU network. Denote S := UIE(A)aE(a and let 8 = Uxe(x)see(m.) HC be the canonical representation S. Then for all Ky there exists unit (1, with i k such that Hy S (2) (z) 0}. Moreover, the dependency graph of contains a directed path of length m starting at J.y then --m. m.
0}
Main proof idea. This lemma motivates the main idea of the proof. We explicitly construct network h such that the dependency graph of its fold-set is well connected. More precisely, we ensure that each of the hyperplanes corresponding to first-layer units has chain of descendants of length I, - 2. This implies by Lemma 3 that the first-layer hyperplanes can be identified as such, using only the information contained in the fold-set. One can show that this is sufficient to recover the parameters W1, b1, up to permutation and scaling. To extend the argument to higher-layers, we then consider the truncated network 1LL,, In h 1 layer becomes the first layer, and we apply the same reasoning above to recover Wi, bj.
The next lemma shows that network with a 'well connected' dependency graph exists. In what follows, fA denotes the restriction function f to a domain A, and 2/g - (h( / E } is the set of all possible inputs to the truncated network 11 For notational convenience, we define 20 A 2.
Lemma 4. For a bounded open nonempty domain Z and architecture (do.....dy d1) with do 2 d1 2 dz-1 2, dp 1, there exists general transparent ReLU network h. 2 R such that for I E [L. - 11. the the fold-set Fhhh lin22-1) ) is a piece-wise linear surface whose dependency graph contains d, directed paths of length (L - 1) with distinct starting vertices.
Theorem then follows by the inductive argument outlined above.
Let ho be the network from Lemma 4 One can show that if he is transparent, and hy (z) (z) for all networks h124, 1iy2 are transparent.
Proof sketch of Theorem
|
2, then also hn is transparent, and all the truncated
We proceed by induction. Let 1.
Then we have
h14 lint 2/- ho = hy = h12 lint 2/-1
(12)
which implies F(h lint 2/-1) J(h lint 23-1). (For notational convenience, will omit the domain restriction for now.) Because both networks are general and transparent, the fold-sets are representable as unions of the respective zero-level sets, and we obtain
U
{z 11 1+h (((z) = 0}
U kE[r.-I]jee [.E)44))
{ [f((z) = 0}
(13)
AE[T.-I],j(M [.E
This is a piece-wise linear surface, whose dependency graph by Lemma 4 contains di directed paths
of length (L-1-1) with distinct starting vertices. Denote these vertices . Hag By Lemma
H, C 1 (1]()) 0} for some (2, with À < (L. -) 1) (L. T--11 1) 1. We thus obtain Uleja) H, S Useja] {z [[]l[(2) =)) = 0}. where on the left-hand side we have a union of d hyperplanes, and on the right-hand side we have a union of most de hyperplanes. It follows that the two sides are equal, and by applying the same argument to hy, we get
U
Z [() 0} = U {z [1] - 0}.
(14)
EE [i)
=E[4]]
Therefore there must exist a permutation [d]] + [dt] such that
{z) {2|1/[]((>)
0} { n (1))()) = 0}
(15)

---

Published as a conference paper at ICLR 2020
for all i. One can show that this implies the existence of scalars ma,... May such that
(Wi[t, (n(()) - m. (W]
(16)
We know that m, * 0 because the folds {zl [1( = 0}. {z (1 0}, are nonempty; oth- erwise Uietat Hg could not be a union of d: hyperplanes. We have thus shown that there exists
a permutation matrix Pt E Rdxxd: and a nonzero-entry diagonal matrix M, E Rdxxd such that Wi- M,P,W, W and by = M,, One can also show that the scalars m, are positive
For the inductive step, let I E ( .,....,,, 1), and assume that there exist permutation matrices P1 Pi..... .......P-II.. and positive-entry diagonal matrices MI...., - such that (65) holds up to layer 1- Then h/g11 P Since the end-to-end mappings are the same, h122 22:4 it follows that the truncated mappings satisfy
2/ 1 int 2/=1 = (n/t o P. iin 2/-1 = 1171 lint 2/=1;
(17)
where vj := (W b/, W/41 b'....... W2, b(). We therefore apply the same argu-
ment to 1,224 lit 2 and 4 lint 2 1 as we presented above for the case / = 1. We obtain that there exists permutation matrix P1 E R4xd and positive-entry diagonal matrix M, E Bdexd such that
W = MPP.WPP.MMM.
b M/P.b/
(18)
Finally, consider the last layer. We know that hg h1:1-1 = - L h 1 which implies hy = hy o Pi- i.c. hg and h o PT-,M are identical linear functions supported on the dill-dimensional domain 2/-1 It follows that WL = Ww,.Pi,,MT and b, = b'y.
Discussion of assumptions. Most of the theorem's 's assumptions have their origin in Lemma 4 The reason we restrict the domain of I to the interior of 2/- is that we want 1 to be defined on an open set (otherwise fold-sets become unwieldy). For similar reasons, with non-increasing widths; otherwise int 2 may be empty. We conjecture that the theorem does not hold for more general architectures. If it does, the proof will likely go beyond fold-sets.
study only architectures
To guarantee transparency, our construction is such that for each input E 2 and layer E [L- - 1], either (1)(2) > 0 or h!? (z) O. Transparency could in principle be achieved with just a single unit but would have to be positive everywhere. This is why we impose d, 2 2. Guaranteeing transparency for the first layer (whose inputs are not constrained to the positive quadrant) also ne- cessitates boundedness of 2. Boundedness can be lifted we consider a slightly modified definition of transparency; proofs become more complicated though and we do not consider this crucial.
Almost all of the proof carries over to the case of leaky ReLU activations (where a is defined as (u): max (aru, w:} for some small a > 0). The part that does not carry over is our proof that M, has only positive entries on the diagonal: In this part, we compare the slope of h/z for inputs on the positive and negative side of a given ReLU unit, and notice that the negative-side slope is 'singular' in the sense that some basis directions have zero magnitude. This particular argument does not work for the leaky ReLU, though we cannot rule out that a simple workaround exists.
DISCUSSION & FUTURE WORK
In this work, we have shown that for architectures with non-increasing widths, certain ReLU net- works are almost uniquely identified by the function they implement. The result suggests that the (unction-equivalenee classes of ReLU networks are surprisingly small, i.. there may be only little redundancy in the way ReLU networks are parameterised, contrary to what is commonly believed.
This apparent contradiction could be explained in a number of ways:
It could be the case that even though exact equivalence classes are small, approximate equivalence is much easier to achieve. That is, it could be that ||اe - hnll S e is satisfied
"See Appendix, Lemma A.19
"See Appendix, Theorem A.I
8

---

Published as a conference paper at ICLR 2020
by disproportionately larger class of parameters 77 than Ilhe h, = 0. This issue is related to the so-called inverse stability of the realisation map of neural nets, which is not yet well understood.
Another possibility is that the kind of networks consider in this paper is not represen- tative of networks typically encountered in practice, i.c. could be that "typical networks' do not have well connected dependency graphs, and are therefore not easily identifiable.
Finally, have considered only architectures with non-increasing widths, whereas some previous theoretical work has assumed much wider intermediate layers compared to the input dimension. It is possible that parameterisation redundancy is much larger in such a regime compared to ours. However, gains from pre--paramttrriaation have also been observed in practical settings with architectures not unlike those considered here.
We consider these questions important directions for further research. We also hypothesise that our analysis could be extended to convolutional and recurrent networks, and to other piece-wise linear activation functions such leaky ReLU.
REFERENCES
Francesca Albertini and Eduardo D. Sontag. For neural networks, function determines form. Neural networks, 6(7):975-990, 1993a.
Francesca Albertini and Eduardo D. Sontag. Identifiability of discrete-time neural networks. In European Control Conference, 1993b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-
parameterization. In International Conference on Machine Learing (ICML). 2019.
Vijay Badrinarayanan, Bamdev Mishra, and Roberto Cipolla. Symmetry-invariant optimization in deep networks. International Conference on Learning Representations (ICLR), 2016.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. In Proceedings of the National Academy of Sciences (PNAS), 2019.
Julius Berner, Dennis Elbrächter, and Philipp Grohs. How degenerate the parametrization of ral networks with the ReLU activation function? In Conference on Neural Information Processing Systems (NeurIPS), 2019.
An Mei Chen, Haw-minn Lu, and Robert Hecht-Nielsen. On the geometry of feedforward neural network error surfaces. Neural computation, 5(6):910-922) 1993.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learing (ICML), 2019.
Charles Fefferman and Scott Markel. Recovering feed-forward net from its output. In Conference on Neural Information Processing Systems (NIPS), 1994.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations (ICLR), 2019.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. In International Conference on Machine Learing (ICMI.,, 2019.
Robert Hecht-Nielsen. On the algebraic structure of feedforward network weight spaces. In Ad- vanced Neural Computers, pp. 129-135. Elsevier, 1990.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural nefworks, 2(5):359-366, 1989.

---

Published as a conference paper at ICLR 2020
Véra Kürková and Paul C. Kainen. Functionally equivalent feedforward neural networks. Neural Computation, 6(3):543-558 1994.
Behnam Neyshabur, Ruslan R. Salakhutdinov, and Nati Srebro. Path-SGD: Path-normalized op- timization in deep neural networks. In Conference on Neural Information Processing Systems (NIPS), 2015.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of peeeraaramttiiitioon in generalization of neural networks. Interna- lional Conference on Learning Representations (ICLR), 2019.
Roman Novak, Yasaman Bahri, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization neural networks: an empirical study. In International Conference Learning Representations (ICLR), 2018.
Philipp Petersen, Mones Raslan, and Felix Voigtlaender. Topological properties of the of func- tions generated by neural networks of fixed size. In arXiv: 08459, 2018.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl Dickstein. On the expressive power of deep neural networks. International Conference on Machine Learing (ICML), 2017.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learing (ICML), 2018.
Pierre Stock, Benjamin Graham, Rémi Gribonval, and Hervé Jégou. Equi-normmalzzttoon of neural networks. In International Conference on Learning Representations (ICLR), 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations (ICLR), 2017.
10

---

Published as a conference paper at ICLR 2020
A APPENDIX
Use the following look-up table to find a particular lemma or theorem and its proof.
Lemma
Lemma A.15
Lemma
Corollary A.
Lemma
Lemma A.T8
Lemma
+
Lemma A.17
Theorem
Theorem A.1
A.1 PIRCE-WISE LINEAR SURFACES
Definition A.1 (Partition). Ler 8 S 2. We define the partition of 2 induced by S, denoted P2 as the set of connected components of 2.
Definition A.2 (Piece-wise hyperplane). Let P be a partition of 2. We say H. C 2. is a piece-wise hyperplane with respect to partition P, if H # 0 and there exist (w,b) b) & (0,0) and P E P such that J {z P|wTz b 0}.
Definition A.3 (Piece-wise linear surface / pwl. surface). set 8 C 2. is called a piece-wise linear surface on 2 of order & if it can be written as 8 -Ue(ee H where each H is a piece-wise hyperplane with respect to Pz P=(Uke(-1))EEnu) Hty), and number smaller than admits such representation.
Lemma A.1. If 11,82 piece-wise linear surfaces 2 of order kn and 22, then S1 U2 is piece-wise linear surface on of order at most max {kr, )
Proof. Lj (.E( HC; and 82 UIE(ka))E(maa) 9 be the pwl. surface representations of S2. Given Hc, consider the partition
:= Pz
Ky
U
st)
(I)
kE(1- []-E[l]))
kE[max (1- (e=
We can write HC UPE H. P and denote the nonempty intersections H n P as {H Similarly, decompose 9 = U Then 81 U Ul max (k,, (U. HC U Riy), where each Hi and Ri a piece-wise hyperplane wrt. P = P=(URE(I- UU H Ur 35 ").
Given sets and 8 C 2, we introduce the notation
8' is pwl. surface on Z of order at most i}. 0 U 8
(2)
(The dependence on suppressed.) By Lemma A.I D itself pwl. surface on 2 of order at most
Lemma A.2. For i < and any set 8, we have D D, = 0,8.
Proof. We will need these definitions:
8 U (8" 8 is pwl. surface of order most i};
D U {8" [S|s" a pwl. surface of order at most j);
(4)
D,0,8 U {8" C S 8 is pwl. surface of order at most i),
(5)
D
U {8"
C 5 8" is pwl. surface of order at most j}.
Consider first the equality D, D.S. We know that D D because the square operator
always yields a subset. At the same time, S C D,D,S S. because S satisfies the condition for membership in (6).
11

---

Published as a conference paper at ICLR 2020
To prove the equality D, S use the inclusion 8 S 8 to deduce D C D,8. Now let 8" S S be one of the sets under the union in 3 i.e. is pwl. surface of order at most i. Then is also pwl. surface of order at most j. implying 8" D This means 8" is also one of the sets under the union in (5) proving that 8 ,,,
IT
Lemma A.3. Let 2 and S 2. be sets. Then one can write 1 Cg U, H, where H, are piece-wise hyperplanes wrr. Pz (0)
Proof. Let Ck+18 UIe(s).E(m) HC be the pwl. surface representation of C If K S k, then k++18 8 and we done. Otherwise, Ule(M) JC, S S implying
k+118 C C
U H
:E(ne+1]
At the same time, 8 U uil HQ++ is pwl. surface of order at most A + because g is a pwl. surface of order at most & and JC!- can be decomposed into piece-wise hyperplanes wrt. Pz. 8.) Therefore, a U (se H6+1 C CK+18 implying in fact equality.
Definition A.4 (Canonical representation of pwl. surface). Let S be a pwl. surface on 2. The pwl.
surface representation = Uie(w)ie((m) HC is called canonical if Ule(s] HQ D for all
k E [s), and each Ht is distinct.
Lemma A.4. I Ulelw)iEtm Hi is pwl. surface in canonical form, then is the order of
Proof. Denote the order of by A. By the definition of order, S K, and 0x8. Then, since S = Ulele).eema HC is a canonical representation, we have
U (E(A).iE(m]]
ce| = D,8 = S
U
(8)
[E(M],AE|m]
It follows that K.
A.
Lemma A.5. Every pwl. surface has a canonical representation.
Proof. The inclusion Ule(M),EE(m)) HQ C 8 holds for any representation. We will show the other inclusion by induction the order of S. If S is order one, 0 C 8 = -ie((, KC holds for any representation and we are done. Now assume the lemma holds up to order x - 1, and let S be order k. Then by Lemma A.3 S - - 8 Hy where H piece-wise hyperplanes wrt. Pz (D.-888)) By the inductive assumption, 1 has canonical representation, [],E[m]) HQ. We claim that s Ule xl),e[mm.] HC canonical representation HC. If k: E [ts 11, then by Lemma A.2
say x 8-
of 8. If h = 66, then clearly S C 8 Urenw),ee(mu)
S 0 UlEMM)iE((.) JQ. where we have used the canonical representation of 1
Finally, distinctness of HC} can be ensured by throwing away duplicates.
Lemma A.6. Let Z be an open set. If S is piece-wise linear surface on Z, and if S Ulels),sE(M.) Ht. and 8 Uiels)jE(mm) 9 are two canonical representations of S, then for all I E [s), ny = and there exists a permutation π [m]] + [md] such that HC S In other words, the canonical representation is unique up to within-order indexing.
Proof. Let l E [k]]. Because both representations are canonical, we have
S
U
K = S D U 95,
iE[ng]
jE[me]
where HC and 9 are piece-wise hyperplanes wrt. Pz ( 18). Then for each PE P2((k=18))
18),
Pn
U .C = P U 9
(10)
(E(Nu]
]E(ma]
where both sides above have union of hyperplanes open set. The claim follows. n
12

---

Published as a conference paper at ICLR 2020
Definition A.5 (Dependency graph of pwl. surface). Let 8 be piece-wise linear surface on 2, and let = UIEWw))E(mm) Hi be its canonical representation. We define the dependency graph of 8 the directed graph that has the piece-wise hyperplanes (3G) vertices, and has edge HQ + 3C iff < k and HC ncl.c) + D.
A.2 RELU NETWORKS AND FOLDS
We denote by a the ReLU function: ou); = max {0, us} for [dim(u)]-
Definition A.6 (ReLU network). Let Id with do 2 be a nonempty open set, and let
& (W1, Wi.bi.... WL,bL) bt) be the network's parameters, with W, Rdxxd-1, b Rd, and
dr = A ReLU network parameterised by 0 is the function he 2 + R. defined by
hg - hgg a h
L-1 o o.. lig.
(11)
where hz(2)) Wi- + by. For < 1 < k < L, we also denote
likk & h o h 0o hig.
(12)
hi*k o l
(13)
For ReLU network he + R and E [ 1], denote 2//- & (1) E 2... Also, for convenience, define 2g A 2. (We will omit the subscript 0 when is clear from the context.) We write flA to denote the restriction of the function f to the domain A.
Definition A.7 (Activation indicator). A tuple I 2 (II,..., (1....,II-1)) called an activation indicator if I diag(i:) 14 x and i {0, 13th for 1 E [L 1). It is called non non-trivial if i * 0 for all i e [L and non-trivial up to k i + for all E [k]]
Given a parameter vector A (W1, bi.... Wz, by) and an activation indicator I, we introduce the notation
(e W W.-1.-WWW LW,
(14)
(0 I) of Σ WI W.
(15)
km1
(We will omit the argument when it is clear from the context.) These quantities characterise the dif- ferent linear pieces implemented by the network's 's units. Also define (z) & (I)(z),... ..
(2)1
as the activation indicator for specific input: (2) A (n) (z) 2 0} for all (1,
Lemma A.7. In ReLU network with parameters O (W bi,..., W.., W.,,br br.), the pre-activations satisfy h2dt (z) E (w. + (,(0,)), where the indexing runs over all possible activation indicators I. More precisely, 1..((2) w/(0, (0 + (0 (z)).
Proof. Left exercise.
Definition A.8 (Fold-set), Let Z be an open set, and f Z - R a continuous, piece-wise linear function. We define the fold-set of J, denoted by F(J), the set of all points which is differentiable.
Definition A.9 (Positive negative in neighbourhood).
be an open set. The function f 2- IR. is positive (negative) in the neighbourhood of 2. for any >> O there exists x' E Bz such that f(z') > 0 (f(z)) < 0).
Definition A.10 (Unit fold-set). Let ho 2. + R be ReLU network. We define the unit (I, fold-set heg denoted F. (h(h)) as the set of all z E 2 where 1: (1] = O and h [i) is positive in the neighbourhood of z.
Lemma A.8. Let Z be open set, and f 2. - R continuous piece-wise linear function. Then F(a f) consists of those z E 2 that satisfy
f(z) > 0 and E F()). or
13

---

Published as a conference paper at ICLR 2020
f(z) 0 and is positive in the neighbourhood of
Proof. We will prove that if z satisfies any of the two conditions, then z E F(ro and if violates both, then z E F(o f).. We begin with the latter implication.
Let z be such that f() > and z & F(),, i.e. f is differentiable at z. Since f is piece-wise linear, there exists e >> 0 such that all of (z)z) lies inside a single linear region of f and (B,())) C (0, oo]. Then, on (z). the ReLU behaves like an identity, implying a o is differentiable at z, proving that z E F(a f)s. Next, consider z such that f(z) = O. For violate the second condition, there must exist ball (z) around z such that fz). S (-o0, 0J. (This is also true if f(z) < 0.) Then, on B, (z), the ReLU behaves like a constant zero, implying that or o f is differentiable at z.
We now prove the other implication. If fz) > 0 and I(f), then there exists > 0 such that (BB (z)) ) _ (0, sc), which guarantees that the ReLU behaves like an identity on (z). In this ball, we have f = f. so z E F(or o f).
If fzz = 0 and f is positive in the neighbourhood z, we distinguish several cases. If $ F(f), then there exists ball (z) which / behaves linearly, i.e. (f(()) ar (wTz Tz + b), implying z E F(o o s). If E FJ) and, addition, there exists a ball Bx(z) such that (BB(z)) C [0, oo),
then the ReLU behaves like an identity on (z) and z E F(oo f). The final case is E F(f) such that if attains both positive and negative values in its neighbourhood. Since f is piece-wise linear, there exist p, n such that f(z + en) 0 f(z + cp), and cp, en & F(f) for all E (0, 1]. Then Va o fz + (p) + O and Via o () + (n) = O. yielding z E F(o o f).
Lemma A.9. Let be an open set, and let f fn - R be continuous, piece-wise linear functions. For any wi,..., Wn E R, define f = Ei= Wrfi. Then F(f) S Ui=3((f)
Proof. Left as exercise.
A.3 GENERAL AND TRANSPARENT RELU NETWORKS
Lemma A.10. For all 9 except a closed zero-measure set,
rank [W ... 1, W&) = min {dx-1, (I)), (I),...... rank((i-)) ( I W min (dx-1, rank(T.), ................................ (ank raa
(16) (17)
for all activation indicators and all ls S I.
Proof. First, notice that (66) is just a special case of 17 with I, equal to the identity matrix. It therefore suffices to prove 117.
To further simplify, we will prove the statement for single fixed activation indicator I. Then if (I) is the set of networks for which (17 holds given I, and (I) contains all networks except a closed zero-measure set, then also Or T contains all networks except closed zero-measure set, proving the lemma.
Let us hence fix I. and let k E [L]. We proceed by induction. For the initial step, notice that the matrix L We is just WA with some rows replaced by zeroes. The rank of such a matrix is the same the matrix obtained by removing the zero rows, which has size (rank(Is), d1-1). For all Wx except a closed vero-measure set, this matrix has rank min (de-1, rank(I))).
For the inductive step, denote W, : I,W, Wx and
rj min {da-1, raan((L (.......aak(......
(18)
We assume that rank W,-1) = r and want prove the same for Notice that for all W; except a closed zero-measure set, any rows of W; are linearly independent and their span intersects with ker( [ only at O. To see this. recall that by the inductive assumption, rank (W])) = 7/-1, so ker(N WT 1-1) has dimension d;- d -- We can concatenate any subsub rows of W, ; to the basis of ker WT,) to obtain a matrix of size (r: + d - r;- d)-1), which is wide matrix, because ry S T 1- Hence, its rows linearly independent for all W, except closed zero-measure
14

---

Published as a conference paper at ICLR 2020
We now prove that rank(I, W, WWW,11) = min (.-. _ r.. The "S" direction is immediate. For the "2" direction, distinguish between cases. If rank(T;) S rank :-.)). let VL.... Vr, be the (linearly independent) nonzero rows of I,W. We want to show that {v] W are linearly independent, i.e. that I,W,W, W- has at least v, linearly independent rows. Σ5=1 A,v, = O, then Σj=1 Xyv; E ker(W (--)), which by assumption implies E = O. By the independence of {vz}, we obtain R3 0. i.e. [v]W.-1), are linearly independent, and rank(I, (WWW) =
If rLn rank W;-)), we can reduce the problem to the case rank(I;) S rrank (W--) by observing that rank(I, W, Wi-1 2 rank(JJ, W.W:)1) if J. equals I, only with some I's replaced by O's. We can thus take any such J, and apply the argument from the previous paragraph to obtain rank(I, W,W,WWW,,.. W-1) 2 rank(J, J,W,W,WW W.-1) 2 ri.
Lemma A.11. For all O except a closed zero-measure set, the following holds. Let (1, (k.)) be any units, let be an activation indicator non-trivial up to 1, and let J be an activation indicator non-trivial up to lo 1, such that (1, (14-1)== + J.:k Then. for all scalars E R, it holds that (w:
1), (, + clw
(0. (0. (O,J))
(W1. bI.b..... WL, by) such that e, W- Wi-1... I W&R; 0 for some I, k; i, and some non-trivial up to 7 1. Since for any fixed i.J)), the set of A satisfying the above is the set of roots of non-trivial poly- nomial in 0, it is vero-measure and closed. Because there are only finitely many configurations of (1, k, j. I), we have thus excluded a closed zero-measure set of parameters. We will denote its complement O
Proof. First, we exclude from consideration all 0
From now on, we assume O E O". Notice that the case = O of the lemma is thus automatically satisfied, since (0, 2 e W Wi-1 ... I W, + by the definition of O". In the following, we can therefore assume 7 and treat (1, I) and jk symmetrically.
Denote by θ C O the set of parameters 0 for which the lemma does not hold; we need to show that θ is closed and zero meroumeau We start by showing the latter property by contradiction.
Suppose + is positive-meastee as stated in the lemma, and scalar e R such that [w: 1), (),(((,,1) = (w, J), 6),6)))6.... (). Let denote the set of all trplet--pirs ((1, i, I), (k. satisfying the conditions of the lemma; then the previous statement can be written as
We know that for all 0 E O there exist triples (4, i, I), (k.j. J)
C
U
{0 E 0*
Be E R: [w](0, (W. D) dw)
(19)
(K.J)e
Since e is finite, there exist (k, (k) E for which the set under the union (call it O') is mositive-measure.
We now consider two cases. If (1, * (k.j), then observe that e' must contain some 0, such that 0- (W1, bi...., WL, L, by) and 0' = (W1, 1W,,B bi...., Wi, byee WL, by), where 8 o and 2 k. By membership in O', there exist c, E R such that
/ b). (w 1), (/ 1I] = <'w") (0' JJ, (0', J)].
(20)
(21)
Notice that wh, w/ do not depend on the boli]-componett of O, and neither does by because k < and (k, * i). It follows that (0, (0, = (w ( J), 6) J)] =: v. Notice also that [w] 1), 1)] = (0 I), (0 + 6). Putting everything together, we have that
cv [w ( I). (e. c'v = ( 6. (0. + +5],
(22)
(23)
which implies (d' c)v J0, and in particular w² (0.J) 0. This contradicts the assumption that O E O and completes the proof for the case (1, i) # (k:
15

---

Published as a conference paper at ICLR 2020
If i) (k..),, then it must be that 1 * J1:-1. Wlog, let (A.1) 1 -] x [dx] be such that
IA 1.4 d = 1 and JAle, AAl.4=1 = O. Then there exist 0, 0' E O' such that 0 = (W1, bi....; Ww, b1) and
0'
W by doe..... W., br)) where ō # O. Then there exist c, E R such that
[w] 1), (0 = clw J). () (,,,
(24)
(w 60'0 1)] = d'(wi J), (,(0',)),,
(25)
where as before, w does not depend on the bx[s]-compe component. For by we now have (OO
(0,), J) and (0', I) (0 + d, where d òe! W W Wx+ie, and by membership in @²,d d # O. From here, we can proceed as in the case (1 # (k, completing the proof for + being zero-measure,
Finally, we show that O is closed. Let 0 E O* O i.. for all (11, i, D, j.) E C, the vectors (w:(0, 1), (, I)] and [w) by [O] are non-colinear. Since w bb, w bf are continuous functions in 0, there exists a small enough 6 > 0 such that (0', I], (0 ((O,T)) I] and [w] (0', (0',, are non-colinear for all O' E (0) and all ((,,,))) (.) E C. Hence, o θ is open, and @ is closed.
Lemma A.12. For all ReLU nets h: 2 + I. except a closed mero-measure set,
f!(h) = {z E 2 22/h = =}} = Zz E 2 2 is positive and negative in the neighbourhood of z)
(26)
(27)
for all units (1,
Proof. We provide a proof for a single unit (1, i): the extension to all units follows from the finite number of units.
Let 9, H. denote the sets defined on the right-hand sides of (26) and (2 respectively. Clearly, HC S (())) S 9. We will show that S H. Let y S denote the set of all local optima of the function z + Wili::] 1z). Due to piece-wise linearity of the function, and the finite number of pieces. y is finite. It follows that for all ReLU networks except a closed zero-measure set, [i] E y. It is thus guaranteed that h!d never attains a local maximum or minimum at zero. No z 9 can therefore be local maximum or minimum, implying that h! is both positive and negative in the neighbourhood of z. Hence, z E H.
Definition A.11 (General ReLU network). A ReLU network is general if it satisfies Lemmas A.10 A.77 a.7aanA.... A.7
All ReLU networks except a closed zero-measure set are general.
Lemma A.13, If is a general ReLU network, then F(h?'t) = U ((h)"11) for all (1,
Proof. The inclusion F(h!'t) S U 5(h)"-1 follows from Lemma A.9 For the other inclu- sion, let z E F(hh--1) for some E [d. Then there exist sequences of points z (c), e (z) U J(h - such that [(z) (e)) I and I(z)(E)) =: J are independent of and Vik Id (z)( # vh ( We consider three cases based on the (non-)triviality of I and J.
First, suppose both I and J are trivial up l 1. Then by Lemma A.7
V -i & ( = I, k) - = O,
(28)
and similarly
= 0, which contradicts Vh 1-1- (Z((E) * least one of J, must be non-trivial up to 1.
Hence, at
Second, say both and J are non-trivial up to 1 1. From 1i (2) + - (z)(s)) it follows that I1411 * J J1 we can therefore apply Lemma A. to (1, 1) and J)). We obtain (I) * (J), implying Vn (z)( # Vh, (z). Thus, z must be a fold fold-point of n!!
Finally, say I is trivial up to and is non-tiivial up to I - 1. Then Vhl (z)( = w!(T) O, w((J) A 0. Hence,
whereas Lemma A.11 applied to iI, with 0 yields Vh2:((z2(e) Vh! (c)) # Vi. (22(e)) and must be a fold-point of n.d.
16

---

Published as a conference paper at ICLR 2020
Definition A.12 (Transparent ReLU network). A ReLU network h 2 - R is called transparent up to layer m, for all z E 2 and I E [m], there exists i E [d] such that h 2 0, or in other words, (z)) 2 1. If is transparent up layer L 1, say it is transparent.
Lemma A.14. Let h 2 - R be a ReLU network. and let X [L]. If is general, then h line 2A-1 is general. If h transparent, then ht liut 2>-1
1 is transparent.
Proof. We will abbreviate A: lint 2A-1 as hA-L Assume h is general. Then h= clearly satisfies Lemma A.10 and for all i). : * OT, Next, we prove that h satisfies Lemma A.11 Suppose this was nor the case; then there exist units (A 1 + 1,,,, (A - + k. j). , and non- trivial (Jx..... Ix-1+ with (1, 1) o (k, and
activation indicators scalar C' E R such that
(Ix...., II,,II-- I+)
I W. C. Cew.We-HHJJ.--- ... WAW
(29)
and
A-I+1
e!
Wx-1=d1-241 We
(30)
A-1+
c.e.
Σ
W W2-1+4J2-244 Wetllgbe
(31)
M'
Then for any non-trivial indicator (I,.... I-1) (J,..... JA-1); we obtain by post-multiplying
29
e W 241 .. W CC C.ee WiW,,
(32)
and for all & E [A 1]. e W 240 W W.+1I,b C WA-144J-221 W.tJJ.b,
(33)
The first equality means that w²( C. w) and the second equality implies (/(1) - C Cb However, that contradicts the fact that h satisfies Lemma A.11
The last condition of generality Lemma A.12 Suppose h does not satisfy the lemma. Then there exists unit (1, i) such that
{z int - (x) 0} g
{z E int 1 | is positive and negative in the neighbourhood of 2
Le. there exists int 2!-1 such that (z) O, and for some
either (B. S
(-o0, 0] or (B)()( C [0, oc). However, then there exists z' E 2 such that h (z') 2,
and for x' we obtain h2 (x') 0. and by continuity, there is 8 >> 0 such that either (B, C
(-x0, 0] or h (2)( C [0, oo). This contradicts the fact that h satisfies Lemma A.12 We have thus shown that if h is general, then /.*: lintt 2 is general.
Finally, assume is transparent, i.e. for all 2 and I E [L 1), there exists i E [dg] such that (.)(()) 2 0. Then also for all z E int 2 and I E (A.... L - 1}. there exists i E [di] such that h
2 0. Hence, A is transparent.
Lemma A.15. a) For all ReLU networks h 2 - R and all E [L]. [di), we have F(h!-t) S
UNe (h). In particular, F(h) C URe(t- (h).
b) For all general ReLU networks h 2. R transparent up to layer 1 - 1, we have T(h UKER- (h). In particular, for all general transparent ReLU networks, I(h) UkE(L 3 (h).
Proof. We give proof of b) only. A proof of a) can be obtained by replacing some equalities by inclusions. We will prove by induction that F(hl2)) = Uke J (h) if h is general and
transparent up layer 1 For = the function h.-d is linear, so F(h) 0 and the claim holds
17

---

Published as a conference paper at ICLR 2020
trivially. Now assume that (h!!")) Usett-1).eed (h) for 1 + 1. By Lemma A.8 and Lemma A.13 we have
holds; we will prove the same statement
F(h!")) (1 0) (F(()))) (F)(M)
(34)
((2E2)1"(0)00} AE]t-11,jEda]
U sy(h)) UF!(M),
(35)
di F(1!*t)) = U (1)E2)1"(0)000
U s2 UF((M)
(36)
i=1
di
= (( 0f
U
st(n))
u U (h)...
(37)
kE 1.jEdd)
==1
Since U (z E 14 0} S 2, we obtain
J(h!at))
U ( U J(())
U
(y)).
(38)
SELL]
ke
It remains to show the reverse inclusion; we do so by contradiction.
Suppose 2 USE (h) \ I(h!t+1), or equivalently
ž
U g) 2 U { (2))
(39)
[e((-1))E(dd)
:E[d]]
U
(h) n n (ZEZ)N (z) 50.
(40)
kE([-1],EE(4)
iE(dd
Because & is transparent, there exists [d]] : h))(z) so for this i we have h! (z)
0.
However, by Lemma A.12 this implies (h) C F(h
Lemma A.16. Let h 2 R be ReLU network. Then - (h) is union of piece-wise hyper- planes wrt. Pz (Ukepp.eela)) (h)).
Proof. Since Pz( (1 is the partition of the input space into the linear regions of h h2: and F(A C Ukeln.e(da) FJ (h) by Lemma A.1ma...15.. 15 the function 111++1 is also linear on the regions of
Pa Pa(UkeM)jeedu) (h)). For any P Pz P2( (+))) denote the slope and bias of h 1:++1 on P by w(P), b(P). Then
Pno (h) = [Z L (P))T++6(P)
(41)
and 1:4+1 is positive in the neighbourhood of z).
(42)
The positivity condition guarantees that piece-wied wise hyperplane.
+ (0, so P Pngtt! is either an empty set
Corollary A.1. Let h 2 + R be a ReLU network. Then the set Uleln) F((h) is a pwl. surface of order at most k. In particular, h is general and transparent, then F(h) = -1e F((h) a pwl. surface of order at most L 1.
A.4 MAIN RESULT
Lemma A.17. For any bounded domain X and any architecture (di,... dr, with do > di >
2 d 2 2, there exists a nonempty open set of transparent ReLU networks h : X ++ B such that for l E 1).
dim z! di, and
18

---

Published as a conference paper at ICLR 2020
the set F(h!: lint3-1) is a pwl. surface whose dependency graph contains dj directed paths of length (L - 1- 1) with distinct starting vertices.
Proof. We give an explicit construction; we first state it and then we prove its properties. For / 1, we choose the parameters (Wi, by) as follows. Let P1 be some nonempty open convex subset of X, and define
Wi =
- (w. E R x
inf w + < 0 < sup xEP
w + bb. ZEP:
(43)
Since Pt has at least two elements, the strict separation thcorem implies that W is nonempty. It is also open. We can therefore choose [.] from W,, and define
W² == [(w,)) w/ w + b > 0 for all E z
(44)
such that Wi[1, :|z bı[1] s 03.
The set A := {a E conv 2 Wi[L, + bı[1] S 0} is nonempty, convex and compact, and by construction there exists E Pi \ A. Again, the strict separation theorem implies w/ is nonempty. It is also open by the boundedness of A. We then choose (W,[2, :], bz[2]) from W/, and define
Q. - E P WiL,, :|2 + bi 2 0 for all i [d]]
(45)
Note that int Q2 is nonempty, open and convex. Also, there exist 21, 22 Q2 such that
Wi l/z + [ = 0, W :/. + br > 0 for +
(46)
(47)
For E (3,...,de d we then choose (W, byll)) as follows. Let A := cznv Z
and let z E int Qi \ A. Such z exists because dim Qi-1 = dim Pt = d:-1. and dim I i 2 I di 2 d 2. By strict separation and boundedness, there exists nonempty open set of hyperplanes that strictly separate A and z. Let (W. (i) be any of them, oriented such that Wili, :/2 + bi > for j li 1). Then denote by 2, E int Qi-1 any point that satisfies Wili, Jz. + by[d] 0; it exists by convexity. Then int Q is nonempty and convex, and the construction for +i+ 1,... 1,....d, di goes through.
For layers / E f2....,IL 1},
similar construction as for = Denote
P = (Wi- b: n > 0},
(48)
P =
2z 0}.
(49)
Pt is nonempty (because int Qd, is nonempty), open (because Wi-1 is wide) and convex. We assume Wi-1 is full-rank; this holds for all choices W,- except closed zero-measure set. By the construction of Qá_,, there exist Z1,
Zd:-1 E Qui C P1-1 such that or E [d]-1].
W - il b-1111]
(50)
W Wiiii + b--155] > 0 for j *
(51)
Denote their images z/= such that
W Wi-12 12, + b Then by openness, there exists ball around each z/
(z.) S (Wi-1P-1+ + by-1) {2'[i] > 0 for j #i), implying that each z has -idee--iimiiiina. relatively open neighbourhood B, Bz(z) 0} S Pt whose elements satisfy 2' [i] and 2'[j] > for j * i. It follows that the set
(52)
w/ = { (w, b) E Rdd inf TTz + <000 sup T + b, and P:
zERt
for j + i, and TTz + 00
vi [d-1] Ez E P 2 = 0, xزح]
(53)
contains nonempty open subset. We can therefore choose WW[1, :]. by [1]) from W For the choice of of(W (W, (1]) for E (...... dy we use the same procedure as in the first layer. Finally, choose (Wr,bz, arbitrarily.
19

---

Published as a conference paper at ICLR 2020
We will show that this construction satisfies the lemma. The networks are transparent because of how we define Wiz: for all x E X and E [L - 11, either h)"(x) > or h2 (x) > 0. Also, dim 2' di because z' contains int Qd.. which is nonempty and open.
Now let 1 E [I]. We can think of the function h lint 2 as an (L 1--1 1 + 1) >-laerr ReLU network parameterised by (Wi, bi,..., Wr, br.). Because h is transparent, also 1 liut 21-1 is transpar- ent. Corollary A.1 then implies that 8 =- "
Uxe( 3y (1 21-1 is a pwl. surface. Let 8 = Ukej Jty be its canonical representation, and let G denote its dependency graph.
To find the required paths in G. we first identify some important vertices. For À E [T. - 1], denote
xx = {2 E P/ [1 (z) > O for l E []-
(54)
This set is nonempty and open because Pi+A is nonempty and open. Next, for any unit (A,+),
Fd (1 line (mm n 2 = (z E P/ 1 ( (2) = 0,
(55)
1 (z) > 0 for h E E - [1]
By the definition of W and the fact that h 12x)) = P1+x. the set A == (h line 22-1) n 2 is nonempty. Also, by the definition of {Pr hat++111 is in fact linear on 2x. so A is a hyperplane on 2 Therefore there exists piece-wise hyperplane H4(2)) from the canonical representation of S that contains A; by Lemma A.11 all { 1x, are distinct from each other.
((,,)
We now show that G contains the edge H + H ((+1.)) ((++.() for X -L-1--11- 1] and all (i, By the definition of W there exists 2 PI+A such that E[1] = 0, æ > 0 for j * i, and W W (a, :|z +
(A.6)
be+x[1] = O. There also exists a ball (z) S (W1+2-1 P14A-1 b1+2-1) -1) (= > 0 for j + i). Then because of how {Pv) by are defined, there exists z' E Pi such that 111 (2') 2, so it satisfies
1 M (z') = 0,
(56)
h b (z') > 0, for l E [A], (ks,5) # (2,
(57)
h hitt> (z') =0.
(58)
follows that z' E (h int 2111) n 2 S. S(2.) At the same time, the preimage
(h (B. (z)) is open by continuity, and contains z'. So there exists a ball Bz'z') S P. such that all z' E (z') satisfy
(z)+ 0, for k [A], (),,) ().
(59)
On this ball, h/ 1 is linear, so the set A = Bz)) n (1. (1(+t>1((22) > 0} is an open half-ball. On A, hd++ is linear as well, and the set {x' (2'= = 0} intersects the center of the half-ball, z'. Therefore there exists a sequence of points { S Pt such that z'2 + z and
h1*++-1(22) (z') > 0, for k [A], N: 11:+t(2')) = O.
(60)
(61)
We obtain that z' cl(F)++ (1/ int 11 n 2 S cl 1ok((+1.0)) j(A+1,)) which implies
clcck(A.)) ((x.))
ccl 1.)+1.)) (A+1,1)
* 0.
(62)
remains to show that k(A, < k(A+1, r). Consider again the ball B. (z'). By Lemma A.
h/++
is a different linear function on (z(z') n hh ( > 0} and on (z') n (h + (z')
< 0).
Hence, H. (x++))) We obtain that k(,, i) < 1(A + 1,4), proving that G contains the edge 3r + 1
((++aa) not a piece-wise hyperplane wrt. any partition that does not include Hck(A.)) ((A,))
3(+1.0)
Finally, observe that the di paths 3 3r + H k(2.1) ...._ ((2.1)
He ((1-111)) have length (L - 1-1-1) 1), ((L-1,1)
and distinct starting vertices. This proves the theorem.
20

---

Published as a conference paper at ICLR 2020
Lemma A.18. For all general ReLU networks h 2. + R. the following holds. Denote S Ule(n)NEtds) (h) and let = [Rein]JE(mm) HC be the canonical representation of Then HC _ (h for some (1, with 2 k. Moreover, if the dependency graph of contains directed path of length m starting at Ky, then I x
Proof. Because the representation canonical, we have
K g k
U F((1,,,
(63)
LE [(iE4]
which implies Ky S U12e, (h). By piece-wise linearity, we can write
U Ti(h) 12
U P U {ze P Pl = =0). (64) 12
12R.6P
where P runs over the linear regions of h! Moreover, by the definition of (h)) all (P) + O.
Combined with Lemma A. we obtain that each nonempty set on the right-hand side of (64 is
different hyperplane on open set. Therefore there exists one for which Hi C (h) C.))
Now assume that the dependeney graph of 8 contains directed path of length starting Hy Joho denote the path Jchh + ich + .... - ach. By the first part of the lemma, we know that H.. F (l) for some 4, Let c. E [m]] we will show that 4,-1 < 4.
Because of the edge K + H.. know that j and el cf intersect, and that Kye is piece-wise hyperplane wrt. some partition P for which J is boundary. Let å be any point of intersection. By openness, there exists ball (2) such that H Ji-1 is hyperplane on B,
and H-. is a hyperplane on one half-ball defined by (2) and H If it was the case that J. 4-1 2 4, then J.: (h) would be a hyperplane on (ž)) i.c. there would have exist some piece- wise hyperplane on the opposite half-ball as Jch. but included in the same hyperplane. However, by Lemma A.
j.-1"
piece-wise hyperplanes in 8 are included in single hyperplane, we get
a contradiction.
Hence, we obtain lo 4 < < Im X, which yields S X
Lemma A.19. Let (w, b): (c, a) E Rdd x and let F C IRd with dim F == d 1f w b and cTz + a for all z F, then either (w, b) (0,0), (c, a) = (0, or there exists BER: (c,a) = 3(w,b) b).
Proof. Since dim F = d there exist d affinely independent vectors fo...., fa- in F. Hence there are d - 1 linearly independent vectors V1 := fi fo. Va-1 := f fo. such that wTv; cTv, 0. In other words, both w and e lie in the orthogonal complement of the span of Vi,..., Vd-1- If w = 0, then necessarily b = 0, and similarly for (c. If w * 0 a c, then because the orthogonal complement one one- dimensional, there exists B E R such that e fw. Then cTz + a 3lwTz b)
3b = 0 and the lemma follows.
Theorem A.1. Consider a bounded domain X and any architecture (di..... dL-1) with dg 2 d1 2 d > 2. Let be : R be general ReLU network satisfying Lemma A.17 and let hn : X + R be any general ReLU network such that hx(x) = (x) for all x X. Denote A (W,, 1, by,...,W'; W., Then there exist permutation matrices PI....P PL-1, and positive- entry diagonal matrices MI.... ML-1, such that
W1 = M,P.W. W
b = M,P.b/,
Wi = M,P, (MP.WPP/MME
b, = M,P.b//
LE (2..... L-
(65)
Wr = W.P
by. i/
21

---

Published as a conference paper at ICLR 2020
Proof. First, notice that bn is transparent. To this, observe that he is transparent, i.. rank(Iς 2 for all / [L 1] and x E X. By Lemma A.10 V Vxhn(x) Vxho(x) * OT, implying that hn is transparent.
We proceed by induction. Let la 1. Then we have
ho lin 2// = ho hi = lint 2/-1
(66)
which implies F lint 2/-1) = F1ih (int22-)). (For notational convenience, we will omit the domain restriction for now.) Because both networks are general and transparent, Corollary A.1 implies that the set
U (E(L-1),EE(AA)
) -(hh5)= = F(1)4))
U (h
(67)
a pwl. surface of order most L-1. By Lemma A.17 its graph contains directed paths of length (L 1-
1)) 1) with distinct starting vertices. Denote these vertices HI...., Ha. By Lemma A.18
H. (. for some (A, i) with X < (L-1) - (L ---13 1- 1) 1. We thus obtain Uve(aj] H, S
Usetaa (h2z2) where on the left-hand side we have a union of di hyperplanes, and on the right- hand side we have union of at most de hyperplanes. It follows that Uleja H+ = Uselan F. (hb and by applying the same argument to hy, we get Uketaj F. = Uie(aj 31 Therefore there must exist permutation [[d]] - [di] such that Ii (hgh)) F (h for all i. Then by Lemma A.19 there exist scalars mi,-- -M. such that
(Wi :], (d)) = m.
(())
(68)
We know that m, * because the folds J! (, (,)) nonempty; otherwise Use[a,) HG could not be a union of di hyperplanes. We have thus shown that there exists a permutation matrix P. E IR x and nonzero-entry diagonal matrix M2 E Idd xde such that W = M,P, Wi and b, M/P.b/-
Next, we show that the diagonal entries of M, are positive. Let z 2_, E int 2--1 be such that (z)) and (z+ differ only in If [īí i]. Wlog, let 18 (f(i(((z)) = 0 and 18 d[(t)(()))))))))))))) = 1, and denote the row span of 12 W, by W. Then
Veliblz = Wr W 1 ... Wit1 WW E.W,, Vall (z+)= = (2t)-1(2t)... ... W4+
(2 E span(W Wi(i,
Since ho is general and de S dr-1, the matrix W, has full row rank. This means that the rows of W form basis, in which the representation of Vehg I. (z has one more zero coefficient compared In other words, for two points = z E int 2/-- whose indicators differ only in [f i). the point for which 1 (z)) = 0 is also the one for which Va (z) has more zero coeffi- cients when expressed in the row basis of W, Now, observe that if I (z and (x( differ only in 1 i i). then ("(z-) and (z differ only in 4," [ (i), ) π (i)). Because W. = M,P, W/. the number of zero coefficients of Vzh (z = V v (z in the row basis of W is the same as the number of zero coefficients of V 22h (z in the row basis of W.. It follows that 1," (i), m (i)((z) and 1"" (i), a (z)](z+) = Hence, m, is positive.
to V (
For the inductive step, let 1 f2..... L 1), and assume that there exist permutation matrices Pi..... P1-1, and positive-entry diagonal matrices MI...., M, such that (65) holds up to layer 1 1. Then hog 1 M, P 1 Since h1g = hi. follows that
int 2 = (hin P M I
I.L. int = hh
lint 2/
(69)
where r = (WPP.MM, b/. W/ b/+ W'. We can therefore apply the same ar- presented above for the case I = 1. We obtain that there exists permutation matrix P. E R4 and positive-entry diagonal matrix M, E R4x4 such that
gument 11/4 liot 2-- and 1 ? litt 24-
W, = MPMPPPPMMM
b M,P/b/.
(70)
22

---

Published as a conference paper at ICLR 2020
Finally, consider the last layer. We know that hg 1 ML-1Pu-1hh 1 which implies hlp- hy o P i.e. ng and hy PT-,M are identical linear functions supported on the full-dimensional domain 2--1 It follows that W. = W and by. = 8/-- n
23


Reviews:
[{"review_id": "SJxkVFSoKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nIn this paper, the authors studied the equivalence class of ReLU networks with non-increasing weights, and proved that permutation and scaling are the only function preserving weight transformations. The proof technique is novel, and provides some insights in the geometry space of the loss surface. I think the proof technique could have its general implications to some other research, however, the direct value of this paper is not very clear.\n\n1)\tThe paper starts with the discussions on the redundancy introduced by over-parametrization, as one of its motivations. However, what is discussed in this paper is actually far distant from over-parametrization. The redundancy in over-parametrized networks and the redundancy in ReLU networks are different concepts and the connection between them is not well established. The over-parametrization is talking about the smooth information flow brought by wide intermediate layers, however, the equivalence class in this paper is more about the mathematical properties of the activation functions and the topological connections of the neural networks. I feel that the authors have some confusing understanding on these two concepts.\n\n2)\tThe theory was established regarding restrictive types of ReLU networks (feedforward, with non-increasing width). However, many widely used networks are not of this kind. Without extensions to other shapes of the networks, convolutional and recurrent structures, and many kind of normalization transformations (e.g., batch norm and layer norm), the practical value of this paper is limited. \n\n3)\tSome important references are missing. The following paper has in-depth theoretical analysis on ReLU networks, and characterizes the redundancy brought by positive-scale invariant properties of ReLU networks. It is strange that the authors did not cite it.  It would be necessary for the authors to discuss their additional technical contributions given this ICLR 2019 paper.\n-  Q. Meng, et al. G-SGD: Optimizing ReLU Neural Networks in its Positively Scale-Invariant Space, ICLR 2019\n\n4)\tThe practical implication of the theories in this paper is not clearly discussed. What if we know there are only these two kinds of redundancies? What kind of new algorithms and practices can be inspired by such theoretical understandings.\n\n\n** I read the author rebuttal. Different people may have different criteria on evaluating a paper and my criterion is not only about \"what\", but more importantly about \"so what\". I still think the authors should think harder about the implications of their work, either theoretically or practically. Furthermore, I understand that some published papers also use restricted settings to ease their proofs, however, I personally do not think this is well justified. I think for top conference like ICLR, more solid and less restrictive works are preferred.  I could at most adjust my score to weak reject.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HygiRiyRtB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper shows that for ReLU networks satisfying certain conditions, the weights and biases leading to the exact functional form are the ones obtained by neuron permutations and rescalings, and that no other reparametrizations preserving the function exist. The authors provide an explicit algorithm applying these symmetries.\n\nDisclaimer: My knowledge in this particular subfield is limit and I therefore cannot assess the novelty of the approach.\n\nI find the topic very interesting and the authors’ approach reasonable. I appreciate that they clearly qualify the assumptions used. The apparent tensions between the intuition that many different reparametrizations can exist and their result suggesting that in fact only very few weight space points lead to the same function is also discussed in the conclusion, which I really appreciate.\n\nIt would be interesting to study the regime where the functions are not exactly the same. In particular, this is very relevant because we only care about answers on a discrete set of points (train set / test set), and on top of that we only care about the argmax of the logits, rather than the actual detailed answer. I believe such a result would be significantly stronger and more relevant to the practical applications of DNNs, however, I understand that it might be more difficult to obtain.\n\nOverall, I enjoyed this paper and I think it deals with an important problem.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bygn2z2nYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves that, modulo permutation and scaling, ReLU networks with non-increasing widths are uniquely characterized by the function they induce (excepting some degenerate cases).  This result is not apriori obvious and is of interest.\n\nAuthors are commended for balancing brevity, intelligibility, and precision.  However, it is not clear which elements of the proof technique are inapplicable to leaky ReLUs.  It would be helpful to include a brief discussion on this.\n\nI recommend acceptance, since I didn't find any proof errors and the contribution is clear.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proves that the weights of feed-forward ReLU networks are determined, up to a specified set of symmetries, by the functions they define. Reviewers found the paper easy to read and the proof technically sound. There was some debate over the motivation for the paper, Reviewer 1 argues that there is no practical significance for the result, a point that the authors do not deny. I appreciate the concerns raised by Reviewer 1, theorists in machine learning should think carefully about the motivation for their work. However, while there is no clear practical significance of this work, I believe there is value to accepting it. Because the considered question concerns a sufficiently fundamental property of neural networks, and the proof is both easy to read and provides insights into a well studied class of models, I believe many researchers will find value in reading this paper.
Decision: Accept (Poster)