Does a sparse ReLU network training problem always admit an optimum ?
Authors: TUNG QUOC LE
Rémi Gribonval
Elisa Riccietti
Venue: NeurIPS 2023 poster (2023)
Keywords: Topology
best approximation property
closedness
function space
sparse neural networks

Abstract: Given a training set, a loss function, and a neural network architecture, it is often taken for granted that optimal network parameters exist, and a common practice is to apply available optimization algorithms to search for them. In this work, we show that the existence of an optimal solution is not always guaranteed, especially in the context of sparse ReLU neural networks.
In particular, we first show that optimization problems involving deep networks with certain sparsity patterns do not always have optimal parameters, and that optimization algorithms may then diverge. Via a new topological relation between sparse ReLU neural networks and their linear counterparts, we derive --using existing tools from real algebraic geometry-- an algorithm to verify that a given sparsity pattern suffers from this issue. Then, the existence of a global optimum is proved for every concrete optimization problem involving 
a shallow sparse ReLU neural network of output dimension one. Overall, the analysis is based on the investigation of two topological properties of the space of functions implementable as sparse ReLU neural networks: a best approximation property, and a closedness property, both in the uniform norm. This is studied both for (finite) domains corresponding to practical training on finite training sets, and for more general domains such as the unit cube. This allows us to provide conditions for the guaranteed existence of an optimum given a sparsity pattern. The results apply not only to several sparsity patterns proposed in recent works on network pruning/sparsification, but also to classical dense neural networks, including architectures not covered by existing results.

Does a sparse ReLU network training problem always admit an optimum?
Quoc-Tung Le
Elisa Riccietti
Rémi Gribonval
Univ. Lyon, Inria, CNRS, ENS de Lyon, UCB Lyon LIP UMR 5668, F-69342 Lyon, France
Abstract
Given training set, loss function, and neural network architecture, it is often taken for granted that optimal network parameters exist, and common practice is to apply available optimization algorithms to search for them. In this work, we show that the existence of an optimal solution is not always guaranteed, especially in the context of sparse ReLU neural networks. In particular, we first show that optimization problems involving deep networks with certain sparsity patterns do not always have optimal parameters, and that optimization algorithms may then diverge. Via new topological relation between sparse ReLU neural networks and their linear counterparts, geometry- an algorithm to verify that a given sparsity pattern suffers from this issue. Then, the existence of global optimum is proved for every concrete optimization problem involving one-hidden-layer sparse ReLU neural network output dimension
derive -using existing tools from real algebraic
10
12
Overall, the analysis is based the investigation of two topological properties of the space of functions implementable as sparse ReLU neural networks: best approximation property, and a closedness property, both in the uniform norm. This is studied both for (finite) domains corresponding to practical training finite training sets, and for more general domains such the unit cube. This allows us to provide conditions for the guaranteed existence of an optimum given sparsity pattern. The results apply only several sparsity patterns proposed in recent works on network pruning/sparsification but also to classical dense neural networks, including architectures not covered by existing results.
14
16
18
19
20
21
22
Introduction
23
24
The optimization phase in deep learning consists in minimizing objective function w.r.t the set of parameters 0 of a neural network (NN), While it is arguably sufficient for optimization algorithms to find local minima in practice, training is also expected to achieve the infimum in many situations (for example, in overparameterized regimes networks are trained to zero learning error).
25
27
28 In this work, we take step back and study rather fundamental question: Given deep learning architecture possibly with sparsity constraints, does its corresponding optimization problem actually admit an optimal f" The question is important for at least two reasons:
29
30
Practical viewpoint: If the problem does not admit an optimal solution, optimized parameters 31
necessarily diverge to infinity to approximate the infimum (which always exists). This phenomenon has been studied thoroughly in previous works other contexts such as tensor decomposition (7]. robust principal component analysis [30], sparse matrix factorization [18] and also deep learning causes inherent numerical instability for optimization algorithms. Moreover,
33
34
35
itself (26] 23
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

36
the answer to this question depends on the architecture of the neural networks (specified by the number of layers. layers width, activation function, and so forth). response to this question might suggest a guideline for model and architecture selection.
37
38
39
2.
Theoretical viewpoint: the existence of optimal solutions is crucial for the analysis of algo- rithms and their properties (for example. the properties of convergence, or the characterization of properties of the optimum, related to the notion of implicit bias).
40
41
42
One usual practical (and also theoretical) trick to bypass the question of the existence of optimal solutions is add regularization term, which is usually coercive, e.g., the 1 norm of the parameters. The existence of optimal solutions then follows by a classical argument on the extrema of a continuous function in compact domain. Nevertheless, there are many settings where minimizing the regularized version might result in a high value of the loss since the algorithm has to make a trade-off between the loss and the regularizer. Such a scenario is discussed in Example 3.1 Therefore, studying the existence of optimal solutions without (explicit) regularization is also question of interest.
43
44
45
48
47
48
Given a training set {( ) the problem of the existence of optimal solutions can be studied from the point of view of the set of functions implementalle by the considered network architecture on the finite input domain $ - {-r))=1- This is the case since the loss is usually of the form ((o((r)) Vi) where Se is the realization of the neural network with parameters 0. Therefore, the loss involves directly the image of {-:)== under the function fe- For theoretical purposes, we
50
51
52
53
54 also study the function space the domain s [- B, BJd B O. In particular, we investigate two topologiaal properties of these function spaces, both w.r.t. the infinity norm || oloo the best approximation property (BAP), i.e., the guaranteed existence of an optimal solution 0", and the closedness, a necessary property for the BAP. These properties are studied in Section alddd Section 4 respectively. Most of our analysis is dedicated the case of regression problems. We do make some links to the case of classification problems in Section 3
55
56
57
58
59
80
We particularly focus analyzing the function space associated with (structured) sparse ReLU neural networks, which is motivated by recent advances in machine learning witnessing a compelling empirical success of sparsity based methods in NNs and deep learning techniques, such as pruning
61
62
69
32 14, sparse designed NN 4 5) or the lottery ticket hypothesis [10] to name a few. Our approach exploits the notion of networks either with fixed sparsity level or with fixed sparsity pattern (or support). This allows us to establish results covering both classical NNs (whose weights are not contrained to be sparse) and sparse NNs architectures. Our main contributions are:
65
66
67 To study the BAP (i.e., the existence of optimal solutions) in practical problems (finite Q2): we provide a necessary condition and a sufficient one on the architecture (embodied by a sparsity pattern) to guarantee such existence. As a particular consequence of our results, we show that: a) for one-hidden--layr NNs with fixed sparsity level, the training problem on finite data set always admits an optimal solution (cf. Theorem and Corollary 3.T); b) however, practitioners should be cautious since there also exist fixed sparsity patterns that do not guarantee the existence of optimal solutions (cf. Theorem 3.1 and Example[3.1 In the context of an emerging emphasis on structured sparsity (c.g. for GFU-friendlinness) this highlights the importance of choosing adequate sparsity patterns.
68
69
70
71
73
74
75
76
2.
To study the closedness of the function space on Ω = [- BJa. As in the finite case, we provide a necessary condition and sufficient one for the closedness of the function space of ReLU NNs with fixed sparsity pattern. In particular, our sufficient condition on one-hidden--lyer networks generalizes the closedness results of (26] Theorem 3.8] on "dense" one-hidden-layer ReLU NNs to the case of sparse ones, either with fixed sparsity pattern (cf. Theorem 4.2
77
78
79
80
81
Corollary 1. and Corollary 4.2) or fixed sparsity level (Corollary 4.3). Moreover, our necessary condition [Theorem[4.] which is also applicable to deep architectures, exhibits sparsity structures failing the closedness property.
82
83
84
Table and Table 2 summarize our results and their positioning with respect to existing ones. Somewhat surprisingly, ly, the necessary conditions in both domains (52 finite and f = [-B, B are identical. Our necessary/sufficient conditions also suggest relation between sparse ReLU neural networks and their linear counterparts.
85
87
discusses related works and introduces 89 notations; the two technical sections, Section 3 and Section presents the results for the case ? finite
88 The rest of this paper is organized as follows: Section 2
set and Ω = [- B, BJd respectively.
2

---

Activation functions
Works
Architecture
Function space
BAP
Theorem Corollary 5.1
Sparse food-forward
ReLU
linite
(E (xdo | arbitrary ||
network
[6] [5]
Food-forward network
Heavyside
[0, 1|"
(L"(0)) (I.)). vp (c)
Feed forward network.
(9). | ).
Residual feed forward
ReLU
I
measure with compact support and continuous warl Lebesgue meusure
target function continuous)
network
26
Feodforward network
ReLU, PReLU
[- B, B)
(C) II (bo))
X
Corellary 4.1
Food-forward network
ReLU
[- B, B)
(C" || Ils)
X
Corollary
Sparse foed-forward
ReLU
BJ
(C) Ilx))
X
Corollary 4.3
network
Table I: Closddeess results. All results are established for one-hidden-layer architectures with scalar-valued output, except (which is valid for one-hidden-layer architectures with vector-valued output). In o, if the architecture is simply a feed-forward network, then the result is valid for any p >
Works
Architecture
Activation
Function space
Assumptions are valid for any
f-11
P
Feedforward
Sigmoid
(C" Iloo)
X
X
(L = 2)
(Nz 2 2)
(Nr 1)
20
Feedforward
ReLU
(RNEXP -II-I1).
X (L 2)
X (Nr = 2)
network
P=6
(Nu-1 2)
sigmoid, tanh, arctan, ISRLU, ISRU
(C" 11- (loc)
Feedforward netwoek
26
sigmoid, tanh, aretan, ISRLU, ISRU, ReLU, přtLU
(L"( (1a))
x (Nr 1)
(W)),, II (
ELU, softsign
(N₂ 1 2)
Feedforward
(W*+(R), || [EP)
ISRLU
Vp [1.
sigmoid, arctan
(W*F(()), || [PP)
Vh. oo]
Sparse feedforward
Theorem 4.1
RtLU
(C) Ilxc)
network
Sparse
Theorem
3.1
feedforward
ReLU
NxP, II-
network
Table 2: Non-closedness results (notations in Section
Previous results consider Ω = |- B,B. B
ours cover: o a finite Ω with P points; a bounded with non-empty interior (this includes Ω B, A)
91 2
Related works
82
The fact that optimal solutions may not exist in tensor decomposition problems is well-documented 77). The cause of this phenomenon (also referred to ill-posedness (7]) is the non-closedness of
94 the set of tensors order at least three and of rank at least two. Similar phenomena were shown to happen in various settings such as matrix completion [I]] Example 2), robust principal component analysis (0 and sparse matrix factorization [18, Remark A. Our work indeed establishes bridges between the phenomenon sparse matrix factorization
96
[88 and sparse ReLU NNs.
38 There also an active line of research on best approximation property and closedness of function spaces of neural networks. Existing results can be classified into two categories: negative results, which demonstrate the non-closedness and positive results for those showing the closedness or best approximation property of function spaces of NNs. Negative results notably be found in
100

---

102
showing that the set of functions implemented as conventional multilayer perceptrons with various activation functions such as Inverse Square Root Linear Unit (ISRLU), Inverse Square
12 26 23].
103
Root Unit (ISRU), parametric ReLU (pReI.U), Exponential Linear Unit (ELU) 126 Table 1] is not a closed subset of classical function spaces (e-g. the Lehesgue spaces I.", the set of continuous
104
105
functions Co equipped with the sup-norm, or Sobolev spaces W In more practical setting. [20]
106
107
hand-crafts a dataset of six points which makes the training problem of a dense mne-hidden-layrr
neural network not admit any solution. Positive results are proved in [26 16 [5]. which establish both the closedness and/or the BAP. The BAP implies closedness 12 Proposition [21] Section
109
3] (but the converse is not true, see Appendix D) hence the BAP can be more difficult to prove than closedness. So far, the only architecture proved to admit the best approximation property (and thus, also closedness) is one-hidden-lee layer neural networks with heavyside activation function and scalar-valued outpul (i.e., output dimension equal to one) [5] in (22) Vp E [1, oo]. If one allows additional assumptions such as the target function f being continuous, then BAP is also established for one-hidden layer and residual oeehiddeen-lay NNs with ReLU activation function 9. In all other settings, to the best of our knowledge, the only property proved in the literature is closedness, but the BAP remains elusive. We compare our results with existing works in Tables
111
113
114
115
116
117
and 2
118
In machine learning, there is an ongoing endeavour to explore sparse deep neural networks, prominent approach to reduce memory and computation overheads inherent in deep learning. One of its most well-knoww methods is Iterative Magnitude Pruning (IMP), which iteratively trains and prunes conmections/neurons to achieve a certain level of sparsity. This method is employed in various
119
121
122
works 14 32), and is related to the so-called Lottery Ticket Hypothesis (LTH) [IO]. The main issue
129
of IMP is its running time: one typically needs to perform many steps of pruning and retraining to achieve good trade-off between sparsity and performance. To address this issue, many works attempt to identify the sparsity patterns of the network before training. Once they are found, is sufficient train the sparse neural networks once. These pre-trained sparsity patterns can be found
124
125
126
127
through algorithms [29 31 19] or leveraging the sparse structure of well-known fast linear operators such the Discrete Fourier Transform [5] 4 21l 3 Regardless of the approaches, these methods are bound to train neural network with fixed sparsity pattern at some points. This is particular motivation for our work and our study on the best approximation property of sparse ReLU neural
128
129
130
131
networks with fixed sparsity pattern.
132
In this work, [n]] := (1, m. For a matrix A E mxx, Ali denotes the coefficient the index (): for subsets S, S [[m]] S. S [n]. A [S,. :] (resp. A(:. S.). is a matrix of the same size as A and agrees with A on rows in S. (resp. columns in S.) of A while its remaining coefficients are zero The operator (A)) := k()k) A k] # 0} returns the support of the matrix A. We denote mx (resp. 0mxn) an all-one (resp. all-zero) matrix of size m X n.
Notations
133
134
135
136
137 An architecture with fixed sparsity pattern is specified via I = (Jz,...; I1), collection of binary masks/ I E f0, 1 M < < L, where the tuple (Nz...., No) denotes the dimensions of the input layer No d, hidden layers (Nz-1,..... Ni) and output layer (Nr.), respectively. The binary mask I, encodes the support constraints on the ith weight matrix W., i.e. I:[e, k] = O implies think of I, the set {(t,k) I k] = 1}. subset of [N.] x [N.-1] We will use these two interpretations (binary mask and subset) interchangeably and the meaning should be clear from context. We will even abuse notations by denoting 1 S _N Because the support constraint I can be thought as a binary matrix, the notation L[S,, :] (resp. 1[: ScD)
138
139
140
141
W, k) 0. It is also convenient
142
143
144
represents the support constraint of SO x [n]]] (resp. I [n] x Sc).
145
146
The space of parameters on the sparse architecture I is denoted Ni, and for each A E Ni. Ro R + NE is the function implemented by the ReLU network with parameter B:
147
No + Ro(x)= = Wia(...o + +,)) - by-1) + by E No. Rs : x E R2
(1)
148
where (x) max(O. (0. x)) is the ReLU activation.
149 Finally, for given architecture I, we define
4 =
X1 (X.p S 4, E [4]} C NNNNN
XNo
(2)
150 the set of matrices factorized into L factors respecting the support constraints Te, E [L]. In fact, L1
151 the set of linear operators implementable as linear neural networks (i.e., with a = id instead of
152 the ReLU in ( and no biases) with parameters 0 E Ni.
4

---

153
3
Analysis of fixed support ReLU neural networks for finite 2
The setting of finite set Ω { is common in many practical machine learning tasks:
154
155
models such as (sparse) neural networks are trained on often large (but finite) annotated dataset
D [1 v:)] The optimization/training problem usually takes the form:
156
Minimize 9
[(0) -(0)= - Σ ((Ro
under sparsity constraints on 0
(3)
157
where l is a loss function measuring the similarity between Re(z;) and yt. A natural question that we would like to address for this task is:
158
Question 3.1. Under which conditions on I, the prescribed sparsity pattern for 8 does the training problem of sparse neural networks admil an optimal solution for any finite data set DD?
180
181
We investigate this question both for parameters 0 constrained to satisfy fixed sparsity pattern I, and in the case of a fixed sparsity level, see e.g. Corollary
162
163
After showing in Section 3.1 that the answer to Question 3.1 is intimately connected with the closedness of the function space of neural networks with architecture I, we establish in Section 3.2 that this closedness implies the closedness of the matrix set L1 (a property that can be checked using algorithms from real algebraic geometry, see Section (.3) We also provide concrete examples
165
166
167
of support patterns where closedness provably fails, and neural network training can diverge. Section 3.4 presents sufficient conditions for closedness that enable us to show that optimal
168
189
solution al always exists on scalar-valued one-hidden-layer networks under a constraint on the sparsity
170
level of each layer.
3.1
Equivalence between closedness and best approximation property
172
To answer Question 3.1
is convenient to view Ω as the matrix [. xpl E RRxP and to consider the function space implemented by neural networks with the given architecture I on the input domain
178
174
Q in dimension d = Ng, with output dimension Nz, defined as the set
Fi( = (R) 0 E AG) C R
where the matrix (2)) = [Ro (2)) Ro(r))))..,RR())) Ro()) E N2XP the image under Ro of Ω
175
We study the closedness of (12) under the usual topology induced by any norm || of R N.P This property is interesting because if (S2) is closed for any Ω = {ar | then an optimal solution guaranteed to exist for any D under classical assumptions of f(-.-). ). The following result is not difficult to prove, we nevertheless provide a proof in Appendix B. for completeness.
178
177
178
179
Proposition 3.1. Assume that, for any fixed y E NR,, f(.yy) .R. + R is continuous, coercive and that y = arg miny Ely', y). For any sparsity pattern with input dimension No = d the the following properties are equivalent:
180
181
182
183
1. irrespective of the training set, problem B under the constraint E Nı has an optimal solution;
2. for every P and every Ω Rd the function space Fi(St) is a closed subspace of N.XPP.
184
105
The assumption on is natural and realistic in regression problems: any loss function based on any norm on Rd (e.g. f(g',3) = llg/ - yll). such as the quadratic loss, satisfies this assumption. In the classification case, using the soft-max after the last layer together with the cross-entropy loss function indeed leads to an optimization problem with no optimum (regardless of the architecture) when given a single training pair. This due to the fact that changing either the bias or the scales of the last layer can lead the output of the soft-max arbitrarily close to an ideal Dirac mass. It is an interesting challenge to identify whether sufficiently many and diverse training samples (as in concrete learning scenarios) make the problem better posed, and amenable to relevant closedness analysis.
186
187
189
190
191
192
In light of Proposition 3.1 we investigate next the closedness of (12) for finite Q. 193
3.2
A necessary closedness condition for fixed support ReLU networks
195
Our next result reveals connections between the closedness of Fi() for finite Q and the closedness of L1, the space of sparse matrix products with sparsity pattern I.
5

---

197
Theorem 3.1. FF is closed every finite Ω then L1 is closed.
Theorem is direct consequence of (and in fact logically equivalent to) the following lemma:
Lemma 3.2. If LI is not closed then there exists a set Q C IR. d = No. of cardinality at most
199
P == (3No422 N. + 1) such that ((1) is not closed.
Sketch of the proof. Since L1 is not closed, there exists A E L \ Li (C is the closure of the set
202
L). Considering f(z) = Ar, we construct a set f2 { such that [f(z))..... f(r)) e
203
(2) (i)).. Therefore, Fi) is not closed.
L
The proof is in Appendix B.2 Besides showing topological connection between Fi (NNs with ReLU activation) and L (lnear NNs), (. to a simple example where Fi is not closed.
205
Example 3.1 (LU architecture). Consider I = (I2, I1) E (0, 1), x {0, 1] where I1 ((i.5)
1 < i S S d) and 12 {(i, 5) S S S d). Any pair of matrices X2, X1 E Raxd such that XX.) i = 1,2 are respectively lower and upper triangular matrices. Therefore, L1 is the inporitattin/decoooositttt
208
That explains its name: LU architecture. This set is well known to a) contain an open and dense subset of Raxdd b) be strictly contained in Rdxd [13 Theorem 3.2.1] A25 Theorem 1). Therefore, Lı is not closed and by
set of matrices that admit an exact lower upper (LU)
210
212
the contraposition of Theorem
3.1
we conclude that there exists a finite set Si such that Fi(22) is not
closed.
2)
bJ
-
0000005
0.0005
Norm of weigght metricts
000.0055
A 0.001
A 0.001
A 0.001
loss
Volidation loss
Empericall
0.4
200
3030
eporths
opochs
opachs
Figure 1: Training one mne-hideen-layer fixed support (LU architecture) neural network with different regularization hyperparameters À (we use weight decay, i.c., an L regularizer). Subfigures a)-b) show the relative loss (the lower, the better) for training (empirical loss) and testing (validation loss) respectively. Subfigure c) shows the norm of two weight matrices. The experiments are conducted 10 times produce the error bars in all figures (almost invisible due small variability).
214 Let us illustrate the impact of the non-closedness in Example via the behavior during the training of fixed support one-hidden-layer neural network with the LU support constraint I. This network is trained to learn the linear function [x) == Aar where E R is an anti-diagonal identity matrix. Using the necessary and sufficient condition of LU decomposition existence [25] Theorem 1], we
216
have that A E Li LI as in the sketch proof of Lemma 3.2 Given network parameters 0 and training +
218
set, approximation quality can be measured by the relative loss:
P [R,, vi /l//ll
Figure Figure[[illusrratee illustrates the behavior of the relative errors of the training set, validation set and the sum of weight matrices norm along epochs, using Stochastic Gradient Descent (SGD) with batch size 3000, learning rate 0. momentum 0.9 and four different weight decays (the hyperparameter controlling the L regularizer) À x {0, 10 4, 5 x 10 10-4, 10 $3. The case À = 0 corresponds to the unregularized case Our training and testing sets contain each P = 10a samples generated independently as J; u([-1, 1]4) (d 100) and y; ;= Az.
220
222
224
Example 3.1 and Figure 1 also lead to two interesting remarks: while the I regularizer (weight decay) does prevent the parameter divergence phenomenon, the empirical loss is improved when using the non-regularized version. This is the situation where adding a regularization term might be detrimental, as stated earlier. More interestingly, the size of the dataset is 105, which is much smaller than the theoretical P in Lemma 3.2 It thus interesting to see we can reduce the theoretical value of P. which is currently exponential w.r.t. to the input dimension.
226
227
228
230

---

232
3.3 The closedness of L1 is algorithmically decidable
233
Theorem 3.1 leads to a natural question: given how check the closedness of L1, a subset of
R RNL NNxNN No. . To the best of our knowledge, there is not any study the closedness of L1 in the literature. known whether deciding on the closedness of L for given is polynomially tractable. In this work, we show it is at least decidable with a -eubhy-exponetiil algorithm. This algorithm is
234
235 is. thus,
237
an application of quantifier elimination, an algorithm from real algebraic geometry 2
Lemma 3.3. Given I (JI.-.., I1), the closedness of Li is decidable with algorithm of complexity ((44))**) where
N 1+ 2 Li] and is a universal constant.
239
We prove Lemma 3.3 in Appendix B.4 Since the knowledge of I is usually available (either fixed before training 19,31 21 3 or discovered by a procedure before re-training [10 14 32 )) the algorithm in Lemma 3.3 able to verify whether the training problem might not admit optimum.
241
243
While such a doubly exponential algorithm in Lemma 3.3] is seemingly impractical in practice, small toy examples (for example, Example 3.1 with d 2) can be verified using Z3Prover software implementing exactly the algorithm in Lemma 3.3 However, Z3Prover is already unable to terminate when the LU architecture of Example 3.1 with d = This calls for more efficient algorithms
245
247
to determine the closedness of Lı given I. The same algorithmic question can be also asked for Fi- We leave these problems (in this general form) open questions.
248
249
In fact, if such a polynomial algorithm (to decide the closedness of LT) exists, can be used to answer the following interesting question:
251
Question 3.2. If the supports of the weight matrices are randomly sampled a distribution, what the probability that the corresponding training problem potentially admits no optimal solutions?
252
253
While simple, this setting does happen in practice since random supports/binary masks are considered strong and common baseline for sparse DNNs training 22 Thanks to Theorem 3.1 if L1 is not closed then the support is "bad". Thus, to have an estimation of a lower bound on the probability of "bad" supports, we could sample the supports from the given distribution and use the polynomial algorithm in question to decide if Li is closed. Unfortunately, the algorithm in Lemma 3.3 has doubly exponential complexity, thus hindering its practical use. However, for one-hidden-layer NNs, there is a polynomial algorithm to detect non-closedness: intuitively, if the support constraint is "locally similar" to the LU structure, then L1 is not closed. This result is elaborated in Appendix Bnd and Lemma B.8 The resulting detection algorithm can have false negatives (i.e., can fail to detect more complex configurations where L not closed) but no false positive.
254
255
256
258
280
282
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
1
1
0.99
0.67
0.17
0.01
0.75
0.01
0
O
0.8
0.85
0
0.4
0.6
0.5
0.8
0.71
0
O
O
0.7
0.14
O
O
O
O
0.8
0.01
0
0
0.2
0.9
1.0
0.0
Figure 2: Probability of detectable "bad" support constraints sampled from uniform distribution over 100 samples.
TThe package is developed by Microsoft research and it can be found https:/gsthubb.oom//PPPeerz
7

---

263
We test this algorithm on a one-hidden layer ReLU network with two 100 x 100 weight matrices. We randomly choose their supports whose cardinality are p1 1002 and p2 1002 respectively, with (pI, P2) E {0.1,0% 0.2, ... 1.0 For each pair P2). we sample 100 instances. Using the detection algorithm, we obtain 2 The numbers in Figure inniicate the probability that a random support
284
265
266
267
constraint JJ) has E, non-closed (as detected by the algorithm). This figure shows two things:
268 1) "Bad" architectures such as LU are not rare and one can (randomly) generate plenty of them. 2)
At sparse regime (a1,00 a2 < 0.2), most of the random supports might lead to training problems without optimal solutions. We remind that the detection algorithm may give some false negatives.
270
Thus, for less sparse regimes, it is possible that our heuristic fails to detect the con-closedness. The algorithm indeed gives a lower bound on the probability of finding non-closed instances. The code for Example 3.1 Question 3.2 and the algorithm in Lemma 3.3 provided in [17.
272
274
3.4
Best approximation property of scalar-valued one-hidden-layer sparse networks
275 So far, we introduced a necessary condition for the closedness (and thus, by Proposition 3.1 the best approximation property) of sparse ReLU networks, and we provided an example of an architecture I whose training problem might not admit any optimal solution. One might wonder if there are architectures I that avoid the issue caused by the non-closedness of Fr. Indeed, we show that for onehhiddenllayrr sparse ReI.U neural networks with scalar output dimension (i.e., I= N2 = 1), the existence of optimal solutions is guaranteed, regardless of the sparsity pattern.
278
277
278
279
280
281
Theorem 3.4. Consider scalar-valued, one-hidden-low layeer ReLU neural networks (i.e., I= 2, N2 =
282
1). For any support pairs I = (J2, I1) and any finite set Q == (x1,..., Jr),, Fi(22) is closed.
283
The proof of Theorem 3.4 is deferred to Appendix B.3 As a sanity check, observe that when L
2, 2₂ 1, the necessary condition in Theorem 3.1 is satisfied. Indeed, since N₂ L1 C R RIx No.
294
can be thought as a subset of IR No. Any X E L can be written as sum: X = Lier, W W [f,
285
decomposition of the product W₂ 2 W1. where W2li] E R, Wi[i, E R No, supp W [il S 4 f :]. Define H := U1 S [No] the union of row supports of the first weight matrix. It is
287
easy to verify that L1 is isomorphic to IR 1M which closed. In fact, this argument only works for scalar-valued output, N₂ 1. Thus, there is conffict between Theorem 3.1 and Theorem 3.4
286
290
In practice, many approaches search for the best support I among a collection of possible supports. for example, the approach of pruning and training [1] 32 or the lottery ticket hypothesis [[O]. Our result for fixed support in Theorem 3.4 can be also applied in this case and is stated in Corollary 33. In particular, we consider a set of supports such that the support sizes (or sparsity ratios) of the layers
291
292
293
294
are kept below certain threshold K2 i = I,.... L. This constraint on the sparsity level of each layer is widely used in many works sparse neural networks 14 32
296
Corollary 3.1. Consider scalar-valued, one-hidden-lan layer ReLU neural networks. For any finite data set D = (Iz, y. problem 33 under the constraints WWllo S K, i == 1,2 has minimizer.
297
298
Denote I the collection of sparsity patterns satisfying |//l S K, 1,2, so that a set of parameters satisfies the sparsity constraints ||W S K, 1, if and only if the supports of the
Proof.
299
300
weight matrices belong to I. Therefore. to solve the optimization problem under sparsity constraints
301
W Ilo < K2, 2 = 1, 2, it is sufficient to solve the same problem for every sparsity pattern in I.
302
For each I I, we solve a training problem with architecture on a given finite dataset DD Thanks to Theorem and Proposition 3.1 the infimum is attained. We take the optimal solution corresponding
303
304
to that yields the smallest value of the loss function L. This is possible because the set I has a finite number of elements (the total number of possible sparsity patterns finite).
305
Analysis of fixed support ReLU networks on continuous domains
306
We now investigate closedness properties when the domain C Rdd is no longer finite. Denoting
307
F (Ra I No + NN 0 E N1 (with No = d) the functions that can be implemented on a
308
309
given ReLU network architecture I, we are interested in F1() = {fi f Fi). the restriction of
310
elements of Fi to 2. This a natural extension of the set (1) studied in the case of finite Ω.
Notice that 27 contains both input vectors 2; and targets yi unlike Z which only contains the inputs.
8

---

Specifically, we investigate the closedness of Fi( in (C), 1x) (the set of continuous functions on S2 equipped with the supremum norm [f co == supren l Contrary to the previous section, we can no longer exploit Proposition G.1 to deduce that the closedness property and the BAP are equivalent. The results in this section can be seen as a continuation (and also generalization) of the line of research on the topological property of function space of neural networks 126] 12 16 [5 23]. In Section [. and Section 4.2 we provide a necessary and a sufficient condition on I for the closedness of Fi())) in (2,, loo) respectively. The condition of the former is valid for any depth, while that of the latter is applicable for one-hiddennlayer networks
311
312
314
315
316
318
(L 2). These results established under various assumptions St (such as Ω [- B, B) or S
being bounded with non-empty interior) that will be specified in each result.
320
321
4.1
A necessary condition for closedness of fixed support ReLU network
322
Theorem 4.1 states our result on the necessary condition for the closedness. Interestingly, observe that this result (which is proved in Appendix C.I) naturally generalizes Theorem 3.1 Again, closedness
323
of L1 in R. Nu No is with respect to the usual topology defined by any norm.
324
Theorem 4.1. Consider 52 C R.d a bounded set with non-empty interior, and I sparse architecture with input dimension No- d. If (S())) is closed in (9), || llso) then L1 is closed in N
325
327
Theorem 4.1 applies for any 52 which bounded and has non-empty interior. Thus, it encompasses
328
not only the hypercubes [-B, 33 B > 0 but also many other domains such as closed or open R balls. Similar to Theorem 3.1 Theorem 4.1 is interesting
329
the non-closedness of the function space Fi (a subset of the the sense that it allows us check
space (S2) by checking that of & S R.NL.No (a finite-dimensional space). The latter can be checked using the algorithm presented in Lemma 3.3 Moreover, the LU architecture presented in Example 3.1 1 is also an example of I whose function space is not closed in (C), || lox))
330
331
333
334
4.2
A sufficient condition for closedness of fixed support ReLU network
335
The following theorem is the main result of this section. It provides a sufficient condition to verify the closedness of Fi1) for Ω [-B, BJd, B > 0 with one-hidden-layer sparse ReLU neural networks.
336
Theorem 4.2. Consider Ω = [- B, B] No d and sparsity pattern I (I2, I1) such that:
338
1. There is no support constraint for the weight matrix of the second layer. W 1g = 1NaxNii
For each non-empty set of hidden neurons, S S [[N1]. Lis is closed in R where Is == (12l:, S) (S,:)) is the support constraint restricted to the sub-network with hidden neurons in S.
339
340
Then the set Fi( is closed in (S)), I| 1lo)).
341
342
Both conditions in Theorem 4.2 can be verified algorithmically; while the first one is trivial to check, the second one requires to check the closedness of most 2 sets L1s (because there
most
2 subsets of [Ni]]) which is still algorithmically possible (although perhaps practically intractable) with the algorithm of Lemma 3.3] Apart from its algorithmic aspect, we present two interesting corollrris of Theorem 4.2 The first one, Corollary [. is about the closedness of the function space of fully connected (i.e., with sparsity constraint) one-hidden-laye neural networks.
344
346
347
348
Corollary 4.1 (Closedness of fully connected one me-hidden-llyer ReLU networks of any output di-
B. B)), llxc) where mension). Given I (1NxxN, 1N xN)), the set Fi is closed in (C
349
350
d= = No.
351
The result follows from Theorem 4.2 once we check if its assumptions hold. The first one is trivial. To check the second, observe that for every non-empty set of hidden neurons S C [[ the
Proof.
352
set Lig C N2x is simply the set of matrices of rank at most (S), which closed for any S. O
353
354
Corollary 4.2 states the closedness of scalar-valued, ene-hidden-layee sparse ReLU NNs. In way, it can be seen as the analog of Theorem 3.4 for Ω [-B, B)d
355
Corollary 4.2 (Closedness of fixed support one-hidden-layer ReLU networks with scalar output).
357
Given any input dimension d = No 2 1, any number of hidden neurons N₂ 2 1, scalar output dimen- sion N₂ 1, and any prescribed supports I (I2, 11), the set Fi is closed in (C. BJ),, llo))

---

359
Sketch of the proof. If there exists hidden neuron i E [Ni] such that 12 = 0 (i.e., i I2: i not
360
connected to the only output of the network), we have: Ji Fr. where I' Is. [[]]]] {i}.
By repeating this process, we can assume without loss of generality that T2 = N1 That is the first condition of Theorem 4.2
362
383
Therefore, it is sufficient to verify the second condition of Theorem 4.2 Consider any non-emply set of hidden neurons S _ [[Vi]] and define H. UiEs [i,:]] S [[No] the union of row supports of
384
S It is easy verify that Lıg is isomorphic to RR which is closed. The result follows by Theorem For a more formal proof, readers can find an inductive one in Appendix C.3
365
366
367
In fact, both Corollary and Corollary 4.2 generalize 226 Theorem 3.8], which proves the
368
closedness of Fi(1-B, BJ when 12 = 1 N; 1 1N, XNN, (classical fully connected one-hidden-
369
layer ReLU networks with output dimension equal to one).
370
To conclude, let us consider the analog to Corollary [.I] we study the function space implementable as sparse one-hidden-layer network with constraints the sparsity level of each layer (i.e., wllo S Kg 1,2.
371
372
375
Corollary 4.3. Consider scalar-valued, one-hidden-layer ReLU networks (L = 2, N2 = 1, N1, No)
with e constraints |illoo S K1, (i2l/o K2 for some constants K2 E N. The function space F([ B, B] associated with this architecture is closed in (C B, B No || l1so).
375
Proof. Denote I : ((12, 11) 1/ S [] x [N S [N x [No] |4| S K1, 12, S K2} the set of sparsity patterns respecting the ldD constraints, so that F(-B, B, BJ Ulez -i B, B) Since
376
377
is finite and VI E Ir B, B) is closed (Corollary 4.2 the result is proved.
378
Conclusion
379
In this paper, study the somewhat overlooked question of the existence of optimal solution to sparse neural network training problems. The study is accomplished by adopting the point of view of topological properties of the function spaces of such networks on types of domains:
381
382
383
finite domain Ω or (typically) a hypercube. On the one hand, our investigation of the BAP and the closedness of these function spaces reveals the existence of pathological sparsity patterns that fail to have optimal solutions on some instances (cf Theorem 3.1 and Theorem 1 and thus possibly cause instabilities in optimization algorithms (see Example 3.1 and Figure D On the other hand, we also ReLU neural networks (cf. Theorem 3.4 and Theorem 4.2) These results provide new instances of network architectures where the BAP is proved (cf Theorem
384
385
386
387
prove several positive results on the BAP and closedness, notably for sparse one-hidden-laye
386
3.4 and substantially generalize existing ones
389
390
(cf. Theorem 4.2)
381 In the future, a particular theoretical challenge is to propose necessary and sufficient conditions for the BAP and closedness of (I2).. if possible covering in single framework both types of domains
382
383
Ω considered here. The fact that the conditions established on these two types of domains are very similar (cf. the similarity between Theorem 3.1 and Theorem [.1] as well as between Theorem 3.4
394
385
and Corollary 4.2) is encouraging, Another interesting algorithmic challenge is to substantially reduce the complexity of the algorithm decide the closedness of L1 in Lemma 3.3 which is currently doubly exponential. It calls for a more efficient algorithm to make this check more practical.
396
387
398
Achieving practically tractable algorithm would for instance allow check if a support selected
389
e.g. by IMP is pathological or not. This would certainly consolidate the algorithmic robustness and theoretical foundations of pruning techniques to sparsity deep neural networks. From a more theoretical perspective, the existence of an optimum solution in the context of classical linear inverse problems has been widely used to analyze the desirable properties of certain cost functions, e-g. el minimization for sparse recovery. Knowing that an optimal solution exists for a given sparse neural network training problem is thus likely to open the door to further fruitful insights.
400
402
404
10

---

405
Acknowledgement
406
This project was supported by the AssagroAssai ANR project ANR-I9-CHIA-0009, The authors thank the Blaise Pascal Center (CBP) for the computational means. It uses the SIDUS [27 solution developed by Emmanuel Quemener. Q-T. Le wants to personally thank M-I.Ngguyen for his enlightenment the non-equivalence between BAP and closedness in infinite dimension space in Appendix D
408
410
References
412
[1] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Represen- tations, 2018.
413
414
415
[2] Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag, Berlin, Heidelberg, 2006.
417
[3] Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang. Zhao Song, Atri Rudra, and Christopher Ré. Pixelated butterfly: Simple and efficient sparse training for neural network models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April
419
421
25-29, 2022. OpenReview.net, 2022.
422
[4] Tri Dao, Beidi Chen, Nimit Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In 39th International Conference on Machine Learning, 2022.
423
424
425
[5] Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algo- rithms for linear transforms using butterfly factorizations. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 1517-1527. PMLR, 09-15 Jun 2019.
426
428
430
[6]
Tri Dao, Nimit Sharad Sohoni, Albert Gu, Matthew Eichhor,, Amit Blonder, Megan Leszczyn- ski, Atri Rudra, and Christopher Ré. Kaleidoscope: An efficient, learnable representation for all structured linear maps. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.nee, 2020.
432
433
434
[7] Vin de Silva and Lek-Heng Lim. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM Journal on Matrix Analysis and Applications, 30:1084- 1127, 08 2006.
435
438
437
[8] Steffen Dereich, Arnulf Jentzen, and Sebastian Kassing, the existence of minimizers in shallow residual relu neural network optimization landscapes, 2023.
439
99] Steffen Dereich and Sebastian Kassing. On the existence of optimal shallow feedforward networks with relu activation, 2023.
441
[10] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis:
Finding sparse, trainable neural networks. In International Conference Learning Representation, 2019.
443
Nicolas Gillis and François Glineur. Low-rank matrix approximation with weights or missing data np-hard. SIAM Journal on Matrix Analysis and Applications, 32, 12 2010.
444
445
[12] Federico Girosi and Tomaso Poggio. Networks and the best approximation property. Biological
446
Cybernetics, 63, 08 2002.
[13] Gene H. Golub and Charles F. Van Loan, Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
448

---

449
[14] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
450
452
453
[15] P. Kainen, V. Kúrková, and A. Vogt. Best approximation by heaviside perceptron networks. Neural Networks, 13(7):695-697, 2000.
454
455
[16] Véra Kúrková. Approximation of functions by perceptron networks with bounded number of hidden units. Neural Networks, 8(5):745-750, 1995.
457
[17] Quoc-Tune Tung Le, Rémi Gribonval, and Elisa Riccietti. Code for reproducible research: Does a sparse ReLU network training problemalways admit an optimum? Code repository available at https://hal: www.encneeenooonae9900911
458
459
October 2023.
480
[18] Quoc-Tung Le, Elisa Riccietti, and Rémi Gribonval. Spurious Valleys, NP-hardness, and Tractability of Sparse Matrix Factorization With Fixed Support. SIAM Journal on Matrix Analysis and Applications, 2022.
462
[19] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. SNIP: single-shot network pruning based on connection sensitivity. ICLR, 2019.
464
485
[20] Lek-Heng Lim, Mateusz Michalek, and Yang Qi. Best k-layer neural network approximations. Constructive Approximation, June 2021.
468
467
[21] Rui Lin, Jie Ran, King Hung Chiu, Graziano Chesi, and Ngai Wong. Deformable butterfly; A highly structured and sparse linear transform. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 16145-16157. Curran Associates, Inc., 2021.
469
471
[22] Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. arXiv preprint wrXiv:2202.026433 2022.
472
473
474
[23] Scott Mahan, Emily J. King, and Alex Cloninger. Nonclosedness of sets of neural networks in sobolev spaces. Neural Networks, 137:85-96, may 2021.
475
476
[24] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Volume 2, NIPS' 14, page 2924-2932, Cambridge, MA, USA, 2014. MIT Press.
478
480
[25]
Pavel Okunev and Charles R. Johnson. Necessary and sufficient conditions for existence of the lu factorization of an arbitrary matrix, 2005.
481
482
26 Philipp Petersen, Mones Raslan, and Felix Voigtlaender. Topological properties of the set of functions generated by neural networks of fixed size. Found. Comput. Math., 21(2):375-444 apr 2021.
489
484
485
[27]
E. Quemener and M. Corvellec. SIDUS -the Solution for Extreme Deduplication of an Operating System. Linux Journal, 2013.
487
[28] Pierre Stock and Rémi Gribonval. An Embedding of ReLU Networks and an Analysis of their
4B8
Identifiability. Constructive Approximation, 2022.
[29] Hidenori Tanaka, Daniel Kumin, Daniel L. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc.
490
482
[30] Jared Tanner, Andrew Thompson, and Simon Vary. Matrix rigidity and the ill-posedness of robust pea and matrix completion. SIAM Journal on Mathematics of Data Science, 13):5537-554, 2019.
494
12

---

[31] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
497
496
[32]
Michael Zhu and Suyog Gupta. To prune, or not to prune: Exploring the efficacy of pruning for model compression. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings. OpenReview.net, 2018.
500
13

---

502
A
Additional notations
503
In this work, matrices are writtenn in bold uppercase letters. Vectors are written in bold lowercase letters only if they indicate network parameters (such as bias). For matrix A E _=*"" we use A : E 1x (resp. A F. i] Imxx) to denote the row (resp. column) vector corresponding the write A v to denote the scalar product between A li. :] and the vector v E RR. This notation will be used regularly when we decompose the functions of one- seee-hddee-nneeee
505
ith row (resp. column) of A. To ease the notation,
507
networks into sum of functions corresponding to hidden neurons.
For vector V E Rd u[4] E IR 41 is the vector v restricted to coefficients in I S [[]]. If / = {i} singleton, v E the ith coefficient of v. We also use 1m and On denote an all-one (resp. all-zero) vector of size m.
509
510
511
For dense (fully connected) feedforward architecture, we denote N (N No) the dimensions of the input layer No = d, hidden layers (N.-1...., N1) and output layer (NL.), respectively. The parameters space of the dense architecture N is denoted by NN:: is the set of all coefficients of the
513
weight matrices W; E Ii N and bias vectors b, E RR,, ; 1,.... L. It is easy to verify that
515
NN is isomorphic to R. where N = El N;-1N; Ei=1 N, is the total number of parameters
516
517
of the architecture.
518
Clearly, NG S NN since:
N1 == (0 = ((W,, b:)),, supp W.) S 1,... I.........
(5)
A special subset of Ni is the set of network parameters with zero biases,
M (0 ((W,, s, ON;))== supp(W,)) 4 Vi 1,...,
(6)
520
Given an activation function v, the realization Ry of a neural network 0 E Nin is the function
Ry E Ro R²)()) = W (( (Wi i + bi)... ..... by-1) + b E RR
We denote R": : + R% the functional mapping from a of parameters @ to its realization. The function space associated a sparse architecture and activation function // is the image Ni under R":
522
Fr = (M1).
(8)
When the ReLU activation function, we recover the definition of realization in Equation (I.
525
We use the shorthands
RΦ == Rg
(9)
Fi Fr.
as in the main text. This allows us to define L1 (cf. Equation 2 as L1 = (NP) where v/ = Id is the identity map, which is subset of linear maps R No + Nt.
528
527
B Proofs for results in Section 3
528
529
B.1 Proof of Proposition 3.1
530
Proof. First, we remind the problem of the training of a sparse neural network on a finite data set
D = [11, P
Minimize #ENi
(()) = Σ ((o((:)).)),
(10)
532
which shares the same optimal value as the following optimization problem:
P L(D)
Minimize (E)((9)
= 1=1
E(Di:
(11)
533 where Ω ( This is simply a change of variables: from R (x:) to the ith column of
D R2). We prove two implications as follows:
14

---

535
1. Assume the closedness of F1( for every finite Ω. Then an optimal solution of the optimization
problem (10) exists for every finite data set {(2,, 9:) )=1 Consider a training set { yi b=
536
537
and Ω == i= Since D Px (1t (by setting all parameters in 0 equal to zero), the set (12 is non-empty. The optimal value of (II) is thus upper bounded by (()), Since the
538
539
function ((,, 31) is coercive for every yi in the training set, there exists constant C' (dependent on the training set and the loss) such that minimizing (TI) on Fi( or on FI(22 n [(0,, C)) (with (00, C) the _ ball of radius C' centered at zero) yields the same infimum. The function C is continuous, since each { 34) is continuous by assumption, and the set Fi(22) n (000, C)) is compact, since closed (as an intersection of two closed sets) and bounded (since ((0, C)) is bounded). As result there exists matrix D E Fi( n (00,, C) yielding the optimal value for Thus, the parameters 0 such that Ro (Q) = D is an optimal solution of (T).
540
541
542
543
544
545
Assume that an optimal solution of problem 10 exists for every finite data set (1i, W)) Then Fi( is closed for every Q. finite. We prove the contraposition of this claim. Assume there exists 2.
a finite set Ω = { such that Fi(22) is not closed. Then, there exists a matrix D E RNX such that D E Fi( \ Fi().. Consider the dataset { M)) where YA E RN is the ith column of D. We prove that the infimum value of (1O) is V : Σi= ((gt.)())) Indeed, since D E Fi(22), there exists a sequence {6% JEEN such that lim Ro (9) = D. Therefore, by continuity of y:), we have:
P
lim C(0s)= 100
Σ lim E(Ro, (I)). = Σ Cln vk) = V.
546
Moreover, the infimum cannot be smaller than V because the ith summand is at least {(y, yi) (due to the assumption on é in Proposition 3.1). Therefore, the infimum value is indeed V. Since we assume that y is the only minimizer of y + E(y', yy. this value can be achieved only if there exists parameter 0 E I such that (22) = D. This is impossible due to our choice of D which does not belong to (12). We conclude that with our constructed data set D, an optimal solution does not exist for (TO).
547
548
549
550
551
552
B.2
Proof of Lemma 3.2
553
The proof of Lemma 3.2 (and thus, as discussed in the main text, of Theorem 3.1 use four technical
lemmas. Lemma B.I is proved in Appendix C.1 since it involves Theorem 4.1 The other lemmas
555
proved right after the proof of Lemma 3.2
No then the function f x + f(x) Ax satisfies f (1)) Fi(()) for every subset Q of No that is bounded with non-empty interior.
Lemma B.1. A INC C. IR No
557
Lemma B.2. Consider Ω2 = {o:)p= finite subset Re and St' = [-B such that S2 S S', If
558
Fi'))) (under the topology induced by ||. |1,c), then D = (((a))...((())) Fi()).
Lemma B.3, Consider Rg, the realization of ReLU neural network with parameter 0 E L This function is continuous and piecewise linear. On the interior of each piece, its Jacobian matrix is constant and satisfies J E LT.
561
Lemma B.4. For p, N E N, consider the following set of points (a discretized grid for [0, 1}
iN Ω= Q= ON = (# ..... p
ERSispiENNN 1osi,
If H E N satisfies 2 H, then for any collection of H hyperplanes, there exists x E 2. such that the elementary hypercube whose vertices are of the form
{xr
iN 16 (0, 1..1
lies entirely inside polytope delimited by these hyperplanes.
We are now ready prove Lemma 3.2
15

---

Proof of Lemma 3.2
Since L1 is not closed, there exists matrix A Li \ L1, and we consider
f(x) = Ar. Setting p 3 No construct Q as the grid:
Noo Ω = { 11 1.... p
--
10 Sp,d EN, 1A S No
so that the cardinality of Ω = (mi) is := (p + 1) Similar to the sketch proof, consider
885
566 D = [f(x), ((=)).....ffxp))))) Our goal is to prove that D E Fi((t) (9))..
First, notice that D E FF2(
immediate consequence of Lemma B.2 and Lemma B.1
568
remains to show that D & Fi()). We proceed by contradiction, assuming that there exists Ni
such that Ro( = D.
570 To show the contradiction, we start by showing that, as consequence of Lemma B.4 there exists E Z such that the hypercube whose vertices are the 2o points
x
i1 (
Noo p
| (0.1). No _ EΩ,
(12)
572
lies entirely inside a linear region P of the continuous piecewise linear function Rg [. Denote
K = 2 N. a bound on the number of such linear regions, see e.g. [24] Each frontier between
579
574
pair of linear regions can be completed into hyperplane, leading at most = K2 hyperplanes. Since p 3
H., by Lemma B.4 there exists E Z such that the claimed hypercube lies
576
entirely inside a polytope delimited by these hyperplanes. As this polytope itself included some linear region P of Ra. this establishes our intermediate claim.
Now, define u1 x and U; I + (1/p)e,, i [No]] where e, is the ith canonical vector. Denote P E RN N the matrix such that the restriction of Rg to the piece P is fr(x) Px + b. Since P the Jacobian matrix of R4 in the linear region P. we deduce from Lemma B.3 that P E Cr. Since the points 0; belong to the hypercube which is both included in P and in Ω we have for each i:
P P(vo 22) fe( fr(1,)
Ro(vv)
- Ro(vs)
f(vo) f(v))
-A(uo v.).
where the third equality follows from the definition of D and the fact that assume R2( D. Since Up U; = ei/p, , = 1, are linearly independent, we conclude that p=A. A. This implies
579
A E LI, hence the contradiction. This concludes the proof.
581 We now prove the intermediate technical lemmas.
Proof of Lemma B.2 Since f (I"",, there exists sequence (0x JREN such that:
lim sup [x Re, (x)] = k rest'
582 Denoting D = RRa (XI) Ro, (2,)]. since x; Ω C M' i I,..., P. it follows that D converges to D. Since Da Fi2) by construction, we get that D E FI()..
Proof of Lemma B.3 For any 0 E Rg is a continuous piecewise linear function since it is the realization of a ReI.U neural network [1] Consider P a linear region of R, with non-empty interior. The Jacobian matrix of P has the following form 28 Lemma 9]:
W.DD
D,W1
584 where D, is a binary diagonal matrix (diagonal matrix whose coefficients are either one or zero). Since supp(D.W.). supp(W.). C 1, we have: J W. !I=-] (D.W.) LT.
16

---

Proof of Lemma B.4 Every edge of an elementary hypercube can be written as:
x; x + -ei 2 2
where e; is the ith canonical vector, 1 i S N. The points and x + (1/p)e; are two endpoints. Note that in this proof we use the notation (a,6) to denote the line segment whose endpoints are and b. By construction, D contains pd such elementary hypereubes. Given collection of H hyperplanes, we say that an elementary hypereube is an intersecting hypercube if it does not lic entirely inside polytope generated by the hyperplanes, meaning that there exists a hyperplane that intersects at least one of its edges. More specifically, an edge and hyperplane intersect if they have
587
588
589
590
exactly one common point. We exclude the case where there are more than two common points since that implies that the edge lies completely in the hyperplane. The edges that are intersected by at least 583
592
594
one hyperplane are called intersecting edges. Note that a hypercube can have intersecting edges, but
it may not be an intersecting one. A visual illustration of this idea is presented in Figure 3
b)
c)
non-intersecting edge
intersecting edge
hyperplane
Figure 3: Illustration of definitions in R2: a) an intersecting hypercube with two intersecting edges; b) not an intersecting hypercube, but it has two intersecting edges; c) not an intersecting hypercube and it only has two intersecting edges (not three according to our definitions: the bottom edge not intersecting..
596 Formally, a hyperplane (w Tuuxr x + = 0} for w E RRN and b E IR intersects an edge (x, x + Jee)) if:
(w I b) 10 (xr ee) b) 0
and
(13)
w x + b 0r (x + e. +6+0
397 We further illustrate these notions in Figure 4
We emphasize that according Equation 13 Lg in Figure does not intersect any edge along its direction.
e
l2
intersecting hypercube
non-intersecting hypercube
Lz
intersocting edge
hyperplane
Figure 4: Illustration of intersecting hypercubes and hyperplanes in R?.
598
Clearly, the number of intersecting hypercubes is upper bounded by the number of intersecting edges. The rest of the proof devoted showing that this number is strictly smaller than n ifp 2 3N H, as this will imply the existence of at least one non- non-intersecting hypercube.
600
17

---

To estimate the maximum number of intersecting edges, we analyze the maximum number of edges that a given hyperplane can intersect. For fixed index S I N, we count the number of edges of the form (z, x + p ee:) intersected by single hyperplane. The key observation is: if we fix all the
coordinates of æ except the ith one, then the edges (x, + e form line in the ambient space. Among those edges, there are at most two intersecting edges with respect to the given hyperplane. This happens only when the hyperplane intersects an edge one of its endpoints (c.g., the hyperplane l and the second vertical line in Figure In total, for each S i I and each given hyperplane, there are at most 2(p + 1) N-1 intersecting edges of the form (I. + ee)). For given hyperplane, there are thus at most (N + 1)--1 intersecting edges in total (since i E [[]]). Since the number of hyperplanes is at most H. there are most 2N ( 1) intersecting edges, and this quantity also bounds the number of intersecting cubes as we have seen. With the assumption 2 3N H, we conclude by proving that pM 2N H (p+ 1)8-1 Indeed, we have:
HN 1)N-1
2NH
p p 1) N-1 2NH 1+
N-1
2NH ( 1+ 1) p
NH
P
p
P
p
2NH
2/3/3
1 3NH
S
0.93 < 1
3NH
3
602
where we used that 1/n) S = 2.71828, the Euler number.
B.3
Proof of Theorem 3.4
Proof. We denote X = 21 [p]] E NoxP, the matrix representation of Ω Our proof has three
604
605
main steps:
606
Step 1:
We show that we can reduce the study of the closedness of FT(2) to that of the closedness of union of subsets of R associated to the vectors W2. To do this, we prove that for any element
608
f FI2). there exists a set of parameters E Ni such that the matrix of the second layer W₂ belongs to {-1, 0, 1 (since we assume N2 1). This idea is reused from the proof of [I]
610
Theorem 4.1].
For 0 = ((W,,
i, b.) b E N1, the function R(0) has the form:
N₂
Rs Rs(x) = W2o b2
1 + bI.)) + b2
where Wi, W [ 1x W2,2 = Wo/1] E ER, = bli] E R. Moreover, if W2,i is different from zero, we have:
W2. (W1,52 + b1)
W2,1
a 22, |1, + |W2, b1.)).
W2.1
611 In that case, one can assume that W2,5 can be equal to either -1 or 1. Thus, we can assume
612 W2,2 E 03. For a vector v E 1- 1 1xN, we define:
Fy = ((Ro(1)),... Ro(xp)) 0 E Ni,)
(14)
where Mi, WG is the set of 0 ((W,, b:) with W₂ E (0, 10111, .ie., in words, Fv is 614 the image of Q through the function Ro,0 0 E NN
Define V = {v supp(v) S [2] n (0. +1) IxN1, Clearly, for E V, Fy (1)) Therefore.
U CF(.). VEV
Moreover, by our previous argument, we also have:
Fi(2) C U Fv.
VEV
Therefore,
Fi( U Pv.
VEV
18

---

615
Step 2: Using the first step. to prove that (1( is closed, it is sufficient to prove that Fv is closed,
VV E This can be accomplished by further decomposing Fv into smaller closed sets. We denote
616
O' the set of parameters W1, by and b2. In the following, only the parameters of 0' are varied since
618
W2 now fixed to v.
619
Due to the activation function o, for given data point zj E Ω we have:
a (Wa v b1) D, (wa, + b1)
(15)
620 where Dj E D, the set of binary diagonal matrices, and its diagonal coefficients Dyli, are determined by:
d -1 So if W (i, Jry + b S 0 if W L. |1, + bi 2 0
(16)
bb( Note that Dj i] can take both values or if W + activation matrix of 2y. Therefore, for (15) to hold, the N₂ constraints of the form (16) must hold simultaneously. It is important notice that all these constraints are linear w.r.t. 0'. We denote
We call the matrix Dj the
vectorized version of 0' (i.e., we concatenate all coefficients whose indices are in 1 of W and b b
into a long vector), and we write all the constraints in (15) in a compact form:
A(D F3 ) S ON
where A(D),rr) is constant matrix that depend on Dj and Tij-
Set 0 (v, z). Given that (15) holds, deduce that:
Ro(2,) = vo (Wa, + b1) + b = vD, (Wa, b1) + b2 V(D,, 2y, v)z
where V(Dj. -ij, v) is a constant matrix that depends on Dj, V, In particular, Ro(w;) is also a linear function w.r. the parameters z Assume that the activation matrices of (x1,...,e TpP) are
(D D...... Dp), then we have:
(2)) = (V(D), #1, v)z,..., V(Dr, Tp, v)2) E IIP.
To emphasize that (2)) depends linearly z, for the rest of the proof, will write Ro( vector of size P (instead of a row matrix x P) as follows:
V(D,, v)
(9) = V(D..... ..... Dr)z where V(DI... Dp)
V(Dr, xp.
Moreover, to have (Di...., Dp) activation matrices, the parameters z need satisfy:
Dr)z < 0q
where Q PN,, and
21)
A(D...... Dp. =
A(D p. pP)))
Thus, the set of Ro( given the activation matrices (Di,..., Dr) has the following compact form:
F.D DP) (V(D1........................... Dr)z A(D1, Dr)z < 0).
Clearly, p (D DP) C Fv since each element equal to Ra with 0 (v,2) for some z. On the other hand, each element of F, is element of F (DD....DD) for some (D,.... Dp) E DP since the set of activation matrices corresponding to any DP. Therefore,
Fy =
U
Dr.....Dr)
(D Dr)EDP
19

---

Step 3: Using the previous step, it is sufficient to prove that FV F(D...DD)) is closed, for any V. DI....,,DD .p. DP. To do so, we write F.D F(DD...DP) in more general form:
624
(Az Cz yy..
(17)
625
Therefore, it is sufficient to prove that set as in Equation 17) is closed. These sets are linear
626
transformations of an intersection of finite number of half-spaces. Since the intersection of
627
finite number of halfspaces is stable under linear transformations (cf. Lemma ( and the
intersection of finite number of half-spaces is closed set itself, the proof can be concluded. D
Lemma B.5 (Closure of intersection of half-spaces under linear transformations). For any A E
Rmxa C E Rixa, y R,, there exists C' RR x b' R such that:
{Ax Cx 5 = (C'z b'}.
Proof. The proof uses Fourier Mottkin elimination + This method is quantifier elimination In fact, the LHS can be written as: {t t= Ax, Cx S yy, or more
algorithm for linear functions generally,
t Ex R" s.t. B
x
RD
629 where (?) is the concatenation of two vectors (x, t) and the linear constraints imposed by B S 630 replace the two linear constraints Cx $ and t Ax. The idea is to show that:
f1IEE S.L.
x
= t 1 R s.t. B'
Rn
x
(18)
for some matrix B' and vector v'. By doing so, we reduce the dimension the quantified parameter 632 x by one. By repeating this procedure until there is no more quantifier, we prove the lemma. The
633
rest of this proof thus devoted to show that B', v' as (T8) do exist.
634
We will show how to eliminate the first coordinate of x[]]. First, we partition the set of linear constraints of LHS of (18) into three groups:
635
So == ( J 1] 0}: In this case, x|1] does not appear this constraint, there is nothing to do.
636
2. S+ = {j
B 1 > 0}. for E S+, we can rewrite the constraints B S vijl as:
x[1] - vD + Σ a||x|1 + Σ B| == B (x',
638
for some suitable >b3] a[i], B[i] where x' is the last (n 1) coordinate the vector x.
3. S_ = | < 0}: for j E S_, we can rewrite the constraints Bli+I(*) S v, as:
x 2 vb + Σ a|ix[[+ + Σ 3 = Bj (x',t).
For the existence of such x(1], it is necessary and sufficient that:
B (x',) B) tx',t), Wk E S4.j S_.
(19)
Thus, we form the matrix B' and the vector v' such that the linear constraints written in the following form:
B'
v
640 represent all the linear constraints in the set So and those in the form of (19 Using this procedure recursively, one can eliminate all quantifiers and prove the lemma.
More detail about this method can found in this link
"I fact, the algorithm determining the closedness of Li is also quantifier elimination one, but it can be used in more general setting: polynomials
20

---

642
B.4
Proofs for Lemma 3.3
643
Since we use tools of real algebraic geometry, this section provides basic notions of real algebraic geometry for readers who are not familiar with this domain. It is organized and presented as in the textbook 2 (with slight modifications to better suit our needs). For a more complete presentation.
644
645
we refer readers to (2) Chapter 21.
Definition B.1 (Semi-algebraic sets). A semi-algebraic set of R has the form:
4, UlDER" | (x)
j=1
where P: F.... RR R are polynomials and is the "and" logic.
The following theorem is known as the projection theorem of semi-algebree sets, In words, the theorem states that: The projection of semi-algebraic set to lower dimension is still semi-algebraic 650 set (of lower dimension).
648
Theorem B.6 (Projection theorem of semi-algebraic sets algebraic set of I2" and define:
Theorem 2.92]). Let be a semi-
B ( 1n- Ban (21,.... In E AA}
651 then B is a semi-algebraic set of 1R-11
652
Theorem B.6 is powerful result. Its proof (2 Section 2.4] (which is constructive) shows a way to express B (in Theorem B.6 by using only the first n 1 variables "e1....,Tn-11.
653
654
Next, we introduce the language of an ordered field and sentence. Readers which are not familiar to the notion of ordered field can simply think of it as R and its subring as Q. Example for fields that is not ordered is C (we cannot compare two arbitrary complex number). Therefore, the notion of semi-algebraic set in Definition B.I (which contains Qi,5 0) does not make sense when the underlying field is not ordered.
655
656
658
The central definition of the language of R is formula, an abstraction of semi-algebraic sets. In particular, the definition of formula is recursive: formula is built from atoms equalities and inequalities of polynomials whose coefficients are in a subring Q of R. It be also formed by combining with logical connectives "and". "or", and "negation" (A, V.-) and existential/umiveraal quantifiers (=, v). Formula has variables, which those of atoms in the formula itself. Free variables of a frrmula are those which are not preceded by a quantifier (3, V). The definitions of a formula and its free variables given recursively follow:
660
662
664
685
686
Definition B.2 (Language of the ordered field with coefficients in ring). Consider R an ordered field and Q C subring, a formula &b and its set of free variables Free(X) are defined recursively as:
687
1. An atom: if P E Q[X] (where Q[X] is the set of polynomials with coefficients in Q) then &b := (P = 0) (resp. + == (P > 0)) is formula and its set of free variables is Free (4b) == [X1,.... Xn3 where n is the number of variables.
689
670
671
672
2. If 21 and 22 are formulas, then so are 4 V 22 D1 A D2 and -1, The set of free variables is defined as:
673
674
(a) Free 11 V )2) = Free (1) Free
675
(b) Free 4 A 22) = Free( (1) U Free (2)).
678
(c) Free( 1)) = Free(41).
677
3. 4 is formula and X E Free((),, then D' = (3X) and x" = (VX) d are also formulas and Free((') == Free( ( (X), and Free((")) == Free(() (X).
678
679
Definition B.3 (Sentence). A sentence is a formula of an ordered field with no free variable.
Example B.l. Consider two formulas:
Φ = 13,,, + X3 0}
Φ = -X, X2 0) 0}
21

---

680
While D1 is normal formula, D2 is a sentence and given an underlying field (R., for instance), D2 is either correct or not. Here, 22 is correct (since Xi X2 has a root (0, 0)). Nevertheless, if one consider 2 = 1 X1 + X = then 2 is not correct.
681
An algorithm deciding whether sentence is correct not is very tempting since formula and sentence can be used to express many theorems in the language of an ordered field. The proof or disproof will be then given by algorithm. Such an algorithm does exist, as follow:
684
686
Theorem B.7 (Decision problem 22 Algorithm 11.36)). There exists an algorithm to decide whether
given sentence is correct is not with complexity (ssd)01))== where s is the bound on the number of polynomials in d is the bound on the degrees of the polynomials & and is the number of variables.
687
688
689
680
A full description of 2 Algorithm 11 11.36] (quantifier elimination algorithm) is totally out of the scope of this paper. Nevertheless, we will try to explain it in a concise way. The key observation is Theorem B.6 the central result of real algebraic geometry. As discussed right after Theorem [B.6] its proof implies that one can replace a sentence by another whose number of quantifiers is reduced by
891
693
one such that both sentences agree (both are true or false). Applying this procedure iteratively will result into a sentence without any variable (and the remain are only coefficients in the subring). We check the correctness of this final sentence by trivially verifying all the equalittesinequalitiss and obtain the answer for the original one.
695
687
Proof of Lemma 3.3 To decide whether L1 is closed or not, is equivalent to decide if the following sentence (see Definition B.3) is true or false:
AA,(VX L, L, X1, P(A, X X1) 0)A
(Ve > 0, 0, L. ................................ X P(A, X L....... X1) - 0)
where P(A, XI,....... Xx) = E(s)) (At)) PL (X...... X1))
688
689
This sentence basically asks whether there exists matrix A E Fi \ Fi or not. It can be proved that this sentence can be decided to true or false using real algebraic geometry tools (see Theorem [B.7]
700
with a complexity O (s))) where C' is universal constant and d, le are the number of polynomials, the maximum degree of the polynomials and the number of variables in the sentence,
702
respectively. Applying this to our case, we have s 2, d = 2T, k = No + + 2 Et Td (remind that [[]] is the total number of unmasked coefficients of X²).
703
704
705
B.5
Polynomial algorithm to detect support constraints I JI, with non-closed LT.
706
The following sufficient condition for non-closedness is based on the existence in the support
constraint of 2 x 2 blocks sharing the essential properties of 2 2 LU support constraint.
Lemma B.S. Consider a pair = (I E {0, 1mmxr x (0, 1]rxa of support constraints for the weight matrices of one-hidden-layer neural network. If there exists four indices 1 S i i2 S m, 1 S f1,32 I n and two indices k + #1,15 5 k, S r such that:
708
710
1. For each pair (i,j) E ((11.11) (2), (12,51)} we have:
(1.1) E supp(/ [:; [) :I) and (i,j) & [upp(I[; Ve + k. 2. The pair (12, belongs to supp(7 [|: Jk, :)) and to supp(7[:;
711
712 then Li is non-closed.
Proof. First, it is easy see that the assumptions of this lemma are equivalent those of [18
Theorem 4.20] since supp(7]: &JJ(k, :]) is precisely the kth rank-one support of the pair (I.
18
Definition 3.1]. Without loss of generality, one can assume that i1.f1 1, 2 and
k 1,1=2 2. We will prove that A L LT where
A'
m with A' = ()) 0) RR2X2
A
This can be shown in two steps:
22

---

1. Proof that A E Lj: For any > 0, consider two factors:
X :) Y. Y !!)
X.
where x Y. R2x2 respect the support constraints corresponding to the LU architecture. not hard to see that such construction of (X,, Y.) satisfies the support constraints (J, (due to the assumption of the lemma and the value of indices). Moreover, we also have:
|| - X.Y.
A X|Y,llF
714
Thus, to have || - Yele I e, it sufficient to choose a pair of factors (X,, Y)) respecting the LU architecture of size x 2 such that ||A' X,Y,ll Such pair exists, since the set of matrices admitting the exact LU decomposition is dense in R2x2, This holds for any > Therefore, A ZT.
716
717
2. Proof that A Lr: Assume there exist a pair of factors (X, Y) whose product XY A and supports are included in JJ. Due to the assumptions on the pairs (i1, (2), (12. we must have:
X 1|, 1] = A[1, 1]
1 = =A 1[ =1
X[1,, =[1,2] =1
718
is easy to see that is impossible. Therefore, & 41-
719
Given pair of support constraints I, it is possible to check in time polynomial in m, r, whether the conditions of Lemma B.8 hold. A brute force algorithm has complexity O(m2n?r). A more clever implementation with careful book-marking can reduce this complexity to O(min(m. n)mnr).
720
C
Proofs for results in Section
722
C.1 Proof of Theorem
724
In fact, Theorem is a corollary Lemma B.I Thus, we will give a proof for Lemma B. in the following.
728
Proof of Lemma B.
Since A E I C N x.o, we have:
NNN,
1. A $ L1.
x - A| 0 for any 2. There exists sequence ((X)) IE such that lime |X norm defined on R,,,
728
729
We will prove that the linear function: f(x) Ax satisfies / E Fi Fr (where Fi is the closure of Fi in (C), || lloc), that to say f is not the realization of any neural network but it is the uniform limit of the realizations of sequence of neural networks). Firstly, (W,, b E Mi such that RS = f. Since Rs is the realization of ReLU neural network, it is continuous piecewise linear function. Therefore, since Ω has non-empty interior, there exist a non-empty open subset ! of TRd such that S2' C and Rs is linear S i.e., there A' E N x b R such that RØ(x) A'r + b', Vr E Ω Since Rg. we have: A' = A and also equal to the Jacobian matrix of R. on Lt. Using Lemma B.3 and the fact that A $ LI. conclude that $ Fr.
731
prove that & Fi. For the
733
sake of contradiction, assume there cxists
735
737
738
There remains to construct a sequence {0*) JAN, 0+ = (W 8: b E such that limg- Rg k)
fll = 0. We will rely on the sequence ((X* 1= JAEN for our construction. Given we simply define the weight matrices W X < L. The biases are built recursively. Starting from at = supxen
Wf and bj = ct N₁ iteratively define for 2 < i
(x) = : bb
ct == sup || o... o (x)
sen
by = ct I
23

---

The boundedness of S2 ensures that of is well-defined with a finite supremum. For = L we define:
by = Σ II wj)b
i=1 j=it1
We will prove that Rg (a) = (X x x, vo E Ω. As consequence, it is immediate that:
lim 10000
|gg - f1100 = lim sup Rg (xr f(x)]12 k-000 zei
lim
XX
x - A 1 sup |0||| zEil
where used that all matrix norms equivalent and denoted || 1122-2 the operator associated to Euclidean vector norms. Back to the proof that Rg (x)
(X), x Vo Ω due to our
choice of ct have for - L 1:
T o... (x)) 2 0, Vo EQ
where 2 is taken in coordinate wise manner. Therefore, easy induction yields:
Rg (x) 7 oo o0o xi-1 oooooo
o0.000
= 2 - -o.
Wh( (W + b(t) + bb) +
= (X x
w I
s=i+1
= (Xf )
739
740
C.2
Proof of Theorem 4.2
Given the involvement of Theorem 4.2, we decompose its proof and present it in two subsections: the first one establishes general results that do not use the assumption of Theorem 4.2 The second one combines the established results with the assumption of Theorem to provide a full proof.
742
743
C.2.1
Properties of the limit function of fixed support one-hidden-layer NNs
745
The main results of this parts are summarized Lemma and Lemma It important to emphasize that all results in this section do not make any assumption on I.
746
We first introduce the following technical results.
Lemma C.1 (Normalization of the rows of the first layer (6)). Consider Ωt bounded subset of R Ro.
748
Given any 0 = ((W,, b,) E Nr and any norm || || IR-No, there exists 0 = (WW, b, )
NG such that the matrix W1 has unit norm rows, ||b | S C.= supzen sup (ullg] (u, x) and Ra (x: Rg(w), Ω
752
We report this proof for self-completeness of this work. It is not contribution, as it merely combines ideas from the proof of (26] Lemma D.2] and [26 Theorem 3.8, Steps 1-2).
Proof.
753
754
AG we can find another set weights 0' Note that b Iloc can be larger than C. Indeed, given 0 E Ni, the function Rs can be written as: (Wo :|z + bili)) denotes the contribution of the jth hidden neuron. For hidden neurons corresponding nonzero rows of W of W the columns of W and b such that the realization of hy is invari- ((w1/ wa Il) Tx (b/l[will) for any W1 0 IR W2 I Na b R. Neurons corresponding to null rows of W are handled similarly.
first show that for each set weights (W), 2: b } E Mi such that Rg Rø on No and Wi has unit norm
756
757 Ro x No + hy hy(x) + b2 where (x(
758
rescale the
ant. This is due to the fact that (w + b) [w | (aggo((w

---

762
in an iterative manner, by setting them to an arbitrary normalized row, setting the corresponding column of W to zero, and changing the bias b to keep the function RS unchanged on IR No, using
783
that (2 + b) + b = (v + b) + (b2 + (2)(()) for any normalized vector v E No Thus, we obtain 0' whose matrix of the first layer, W', has normalized rows and Rg = Rg on R
784
785
To construct 0 with ||b||/00 S C' we see that, by definition of C, if [|wa]] = 1 and b 2 C' then
786
w x - b 2 - C C+b20 0,
Vx E Q
(20)
Thus, the function ( x + b) = w x + b) is linear on S and
W20 x + b) - b2 = ww x C) + ((b ( C) + b2)
Ww x C) + ((b- + b2)
767
Thus, for any hidden neuron with a bias exceeding C, the bias can be saturated to C' by changing accordingly the output bias b2, keeping the function R2 unchanged on the bounded domain S2 (but
768
not on the whole space Ro Hidden neurons with a bias S -C can be similarly modified.
789
Sequentially saturating each hidden neuron yields 0 which satisfies all conditions of Lemma C.1
770
Lemma C.2. Consider Qi a bounded subset of No. for any (12, 11), given a continuous
771
I Fi()),, there exists a sequence {0h JKEN, 0h = (W. bt) E Ni such that:
772
773
1. The sequence Rgx admits f as its uniform limit, i.e., limg- Rg fllo = 0.
2. The sequence {(W},bf)) bi) has a finite limit (Wi, bj) where Wi has unit norm rows and supp( 11
774
775
Proof. Given a function f E (i2), by definition, there exists sequence (0) ) 0h E Ni
776
vk E I such that limg- Rpp - fl O. We can assume that W has normalized rows and by
777
778
bounded using Lemma C.T We can also assume WLOG that the parameters of the first layer (i.e
WT. , b have finite limits Wi and bj Indeed, since both W and by are bounded (by construction
779
from Lemma there exists a subsequence {p*]keN such that W and bf have finite limits and
780
Rø + f as Ry + f. Replacing the sequence {0t) Finally, since Wi = lim Wt. Wi obviously has normalized rows and supp (Wi) S I1. O
{0")EE JEEN by {0 JeEN yields the desired sequence.
781
782
Definition C.I. Consider Q bounded subset of 12, a function f E (1) and a sequence { Jeen as given by Lemma C.2 We define (a,,b;) = (Wili,:), bil the limit parameters of the first layer corresponding to the ith neuron. We partition the set of neurons into two subsets (one of them may be empty):
785
785
787
1. Set of active neurons: J == {i] (Ex E 0,0 + by > 0) A (Ex E 22, 0, + < <)}
788
2. Set of non-active neurons: J= [Ni]] \ J.
For i.j E J, we write i = if (Wil. bIDI) + (W1l.:))b;00) The relation = is an equivalence relation.
790
781 We define (Je)t=i....r the equivalence classes induced by ~ and we use (at, Be) ;= (as, bi). for some i E Jq as the representative limit of the Eth equivalence class. For i E Jj, we have: (a,, by) e: Be), ei E {+1]. We define J {i Je e; = 1) + @ and Jj = Je Jt.
782
793
794
For each equivalence class Je, define He == {x E S2 aşx + Be = 0} the boundary generated by neurons in Je and the positive (resp. negative) half-space partitioned by He, H == (a E St
795
796
ag + 3g > 0} (resp. H; = {u E Ω 04 + 3, < 0}). For any > we also define the open
half spaces H(eet) fx Rd | + Bt > c) and H(--) for E Rd a x 3 < -c).
798
Definition C.I groups neurons sharing the same "linear boundary" (or "singular hyperplane" as in
26). This concept is related to "twin neurons" (28) which also groups neurons with the same active zone. This partition somehow allows us to treat classes independently. Observe also that
800
supp(az) C N I A
(21)
ieJi
25

---

Definition C.2 (Contribution of an equivalence class), In the setting of Definition C.1 contribution of the ith neuron S Ni (resp. of the Eth (1 S r) equivalence class) of th as:
we define the
h No + IR N2 x De NR
w 1 [2 bb(1))
TR. N2 Σ (x))
SEJz
Lemma C.3. Consider Ω -B, I (12) and sequence {0") JEEN as given by Lemma C.2
and ag, Be, 1 < l S r, E J as given by Definition C.1 I. N Nox such that:
There exist some Ye: b E RM A
[(x)
rea (ate Be) Ar Ab Ar
(22)
lim
< Wi [i, = Yeke, v2
(23)
k-+00
KEJ:
lim
c,by W yeBe, A1
(24)
R-000
ieJe
supp (1e)
U 12 iEJr
vi
(25)
Proof. The proof is divided into three parts:
We first show that there exist Ye, b E R and A E No such that Equation (2 holds. The last two parts will be devoted prove that
802
equations
23
25 hold.
804
Proof Equation (22): Our proof is based on a result of 26) which deals with the case of
scalar output (i.e, N₂ T). It is proved in (26] Theorem 3.8, Steps 3, 6, 7] and states the following:
806
Lemma C.4 (Analytical form of limit function with scalar output (26). In case N₂ (i.e., output dimension equal to one), consider [-B, BJd, a scalar-valued function f +2 R, E Fi(2)) and a sequence given by Lemma C.2
807
there exist E R.No Te,, v E R such that:
[(x) = Σ realas + Bc) + p uut EQ
(26)
Back to our proof, one can write f = "/1....,Ni where fj Ω C No + IR is the function f restricted the jth coordinate. Clearly, fj is also uniform limit Q of JRa for sequence (Ø+ Jeen which shares the same W with {0t Jeen but W is the jth row of w Therefore, {Ø*) Jen also satisfies the assumptions of Lemma C.4 which gives us:
fz(z) Σ Mejo + 3e) + 1
for some H4 E 1 they are defined directly from the considered sequence. Therefore, the function. f (which is the concatenation of fj coordinate by coordinate) is:
M., Vj E R. Note that az, 8r and r are not dependent on the index j since
f(x)
Σ 1=1
rea (ars + 3e) Ar b, Va
%9.1
21
with 78 =
A
b
Nc,N2
MN2
2. Proof for Equations 23 24
With the construction of we will prove Equation 23 and
811 Equation (44.. We consider an arbitrary < l S r. Denoting f2 the interior of Ω and H.
{a E Ω agT + Bg 0} the hyperplane defined by the input weights and bias of the f-th class of
26

---

neurons, we take point x' E (Ωt n HH)) \ Uupe Hp and fixed scalar r > 0 such that the open ball ((a',)) S Ω2 Uppe Hp. Notice that x' is well-defined due to the definition of J (Definition C.I.. In addition, also exists because !2 \ Uppe Hp is an open set. Thus, there exists two constants 0 < 8 < B and such that:
(()',r) S 1- B 6)4.
For each p E, the ball r))',)) is either included in the half-space H3 fx E Rd x
+ 3p > <} or in the half-space H == fo E IRd a x + Pp < -c}.
819
The intersection of B(x', with H! and H ()))) are empty.
820
For the remaining of the proof, we will use Lemma C.5 another result taken from (26
We only state
822
the lemma. Its formal proof can be found in the proof of 26 Theorem 3.8, Steps 4-5].
Lemma C,5 (Affine linear area 26 Given sequence { heeN satisfying the second condition of Lemma
824
C.2 we have:
(a) For any 0 ô B, there exists a constant Ki such that Vi E J, h are affine linear on ( B), B No for all k 2 Kgg-
825
826
827
(b) For any O, there exists a constant Ke such that for each S & < r and each e Jr the
function hy is affine linear on H(e,t) U H((-) for all k 2 K.-
828
The lemma implies the existence of K max(Ks, ne) such that for all k 2 K, we have:
Σ (x) B"x + Vo E B(x',)) r),
pzf
for some B E ER N2x bith
R No, Therefore, for & 2 K, we have:
Ron (x) = Bº v Σ ( 11, A2 + bli,),, ve e B(d', H(
NEJT
Ro (x) Bdr + Σ
W
bl), Vo B(d',) nH
iEJ
Since we proved that ff has the form Equation 22 there exist C E No E Rz such that
f(x) (C ((a)) ) + (u+ + Be),), Vo E B(x', r) H feet)
f(x) Ca + 11,
Va E B(a', (c.-)
829 As both B(x',r) n (e(tt) and B(x', n H!! are open sets, and given our hypothesis of uniform
830 convergence of Rgz + we obtain,
lim B
C 7800
lim
B
(1i. w
C
iEJ?
(27)
lim b
b + yeB
k 100
lim
Σ
b = p.
k-v0c
IEJ
831 Proof for Equation
27 can be found in Appendix
C.4 Equations
23 and 24 follow directly from
Equation (77.
3. Proof of Equation
Since ag # (remember that ||ael| = 1), this is an immediate conse- 23 each vector W.. Je is supported in 42 j] S U2i,, D
25
quence of Equation
27

---

835
We state an immediate corollary of Lemma C3 which characterizes the limit of the sequence of contributions (gr KENN of the 2th equivalence class with [Jz] = 1.
836
Corollary C.1. Consider f E Fi(l-B
B.
Bld) that admits the analytical form in Equation 22).
sequence {0t JREN as given by Lemma C.2 and Definition C.I For all singleton equivalence classes
838
Jj = (i), < & v, we have limmg=po
W = and ling- || Tea ( x + ++))l= = 0.
839
Proof. We first prove that W ( 8]
has a finite limit. In fact, applying the second point of Lemma C.3
for Jt {i}, we have:
lim W
Yeae
where Ye: Og defined in Lemma C.3 Because lim Wild :1 = ag and | 1, it follows
that V/- lim Ie, s]. To conclude, since we also have Br = limg_ by [1] we obtain h/ (.) Wile - (b] + mor + Be) as claimed.
842
The nice thing about Corollary C.I is that the contribution of = n admits a (uniform) limit Jr {i]. Moreover, this limit is even implementable by using only the ith neuron because supp S [i and supp(?e) S 121t, i].
843
844
845
It would be tempting to believe that, for each P {J} U (Je 1 = ...... r the sequence of functions Eiep of (x) must admit limit (when & tends to oo) and that this limit is implementable using only neurons in P. This would obviously imply that FI(52) is closed. This intuition is however wrong. For non-singless singleton equivalence class (i.e., for cases not covered by Corollary C.T). , the limit
848
849
850
function does not necessarily exist as we show in the following example.
Example C.I. Consider the case where N = (1,3, 1) and no support constraint, Ω = [-1, 1), take the sequence {0" JKEN which satisfies:
)
(
W
by
W (k -k b² K
Then for x E Q2 it easy to verify that Rgg O. Indeed,
Ryp (z)
Σ Wol.ooWWHH [. + bl(l)) + by
= (x) k- ko xz + 1) k
= <(((()) x-x))) ) k(x + + k (since x + 1 2 0, Vor E S
kar - k(x + 1) k
Thus, this sequence converges (uniformly) to = 0. Moreover, this sequence also satisfies the 852
assumptions of Lemma C.2 Using the classification in Definition C.I we have one class equivalence
J1 = (1,2) and J = 33. The function oi (x) kxx ko kx, however, does not have 854 any limit.
C.2.2 Actual proof of Theorem 4.2
Therefore, analysis cannot treat each equivalence class entirely separately. The last result in this section is about a property of the matrix A in Equation (22p. This is one of our key technical contributions in this work.
857
Lemma C.6. Consider Ω = [,B,
Fi(S)) that admits the analytical form in Equa-
lion
22 a sequence [ given by Lemma C.2 then the matrix A E Lx where
1 S), 4[S,:), = JU (UigegrJā)) J are defined as in Definition C.1
881
862
Combining Lemma C.6land the assumptions of Theorem 4.2 we can prove Theorem 4.2 immediately
863
as follow:
Proof of Theorem 4.2
we deduce that there exists a sequence of [0*) that satisfics the properties of Lemma C.2 This allows us to define J and equivalence classes
Consider f E Fi(2.
28

---

J r as well as (ag. (e) as in Definition C.1 analytical formula for f as in Equation (22)
Using Lemma
C.3
we can also deduce an
((x)
=
(ast + Br) + Ar b, Ve E Ω 1=1
Finally, Lemma C.6 states that matrix A in Equation 22
satisfies: A Lp with I'
865 (I2 51, [S :II> where S = JJ (1)=1J))- ) To prove that f E FI, we construct the parame-
ters ((W,, ba) the limit network as follows:
866
1. For each 1 I l r, choose one index E Jt (which is possible since J is non-empty). We set:
868
(ax,, Ye, B1)
i
(W (.. W2[1 (. d), bill)
(28)
(az, 0, otherwise
869
This satisfies the support constraint because supp(oz) E [ (by 21
of
limg-+oo Wi Without supp (7/)
and I2 = N, This is where 871 might not be a subset of 12|:,]]-
the first assumption of Theorem
4.2
2. For i E S: Since A E Lp Lemma C.6) and Lr is closed (second assumptions of Theorem 4.2
there exist two matrices W1, W2 such that: supp(W11) S [1 supp (Wp) S I2[S, :]. and
874
A W2 W1. We set:
(W [i.: Wals: (i) (Wi(k:), Wa(s+1]CC
(29)
875 where C sup Wi This satisfies the support constraints due our choice of W,, W2.
876 The choice of C ensures that the function (x)) := W2 (W Wi + b, [i]) is linear on Q.
3. For b2: Let b2 b C (Eres Wa(s (b is the bias in Equation 22
Verifying Rs { on Q thus trivial since:
Rx(x)=
W Wo b1) + b2
W
+ WW by(()) b2
i
Σ (arz + Be) + Σ
Wel::1)
jES
YES
2asz + + + W +b b Σ
2ara Be) + Ar + b= f. m
t=1
No 0 8 B. The choice of Proof of Lemma C.6 In this proof, we define 22 (-B B, No, 879 is not important in this proof (any 0 < < B will do).
The proof of this lemma revolves around the following idea: We will construct sequence of functions 881 { JEEN such that, for large enough, f has the following analytical form:
(x(x)) Σ rea (aex + Be) A + bd Vr 2
(30)
and lime-soo (xx = [(x)
(U) (or equivalently n converges pointwise to
Ω (U]_1 and A admits factorization into factors A = x satisfying supp X C
L t. S1, supp ( C :S. that A E Lv. Comparing Equation (22) and Equation (30).
deduce that the sequence of affine functions A + by converges pointwise to the affine function
Ar + b on the open set 2 (Ug_, Hz). Therefore, limg- A A by Lemma C.7 hence the conclusion.
886
29

---

The rest of this proof is devoted to the construction of ft = Rga where 6 E NN are parameters of neural network of the same dimension those in Ni but only partially satisfying the support constraint I. To guarantee that f converges pointwise to f, we construct @ based on d and harness their relation.
889
880
Choice of parameters. We Oh ((W b E .N where W R W 8: R x No are defined as follows, where C == sup |
882
For inactive neurons i J, simply set (Wi(:.) W W b1() (Wil: i), W : b((()
For each equivalence class of active neurons 1 < & S r. we choose some je E J (note that Ji is non-empty due to Definition C.1 and set the parameters (W w] by [i] i Je as:
(Wila,), W C* (Wi].:).o. C*),
EjEJ E Jr Vi J \\ {ie}
(WiL.)) W bf
(31)
(ae, Te, Bt),
i=
For Je \ {je), clearly have: supp(Wili.)) & [i, and supp W [2[;,]]. The 888 jeth column of W is the only one that does not necessarily satisfy the support constraint, as 857 supp( & 72 je] in general.
Finally, the output bias b is set as:
6 = by
(bfld - ck
(32)
t=
iEJi
=
Proof that f* == Rg. converges pointwise to f on Ω (Ug=1 He). We introduce notations analog
to Definition C.2 for every E No we define:
(x) w fo
Dl i= = N1; (x)
Eit()),
e= 1=1...,,7
iEJe
By construction
h h2 vi J, Ak.
(33)
889 and we further explicit the form of ht E Je for x E Ω (but not on R No) as:
(
ViE Jj
T (x)
0. valaa + 3e),
Vi J (ie)
(34)
i=
900
We justify our formula in Equation as follow:
901 1. For E J since C* = suPaee | | by construction, W :/r + bb[ = Wf
902 bt 2 0. The activation a acts simply as an identity function.
For E J Because we choose W |] 0.
903
904 3. For = je: Obvious due to the construction in Equation
31
Given E Ω (UE=, Ht), now prove that this construction ensures that for each E {1, f1....,,r)
r)
lim (gf(x) (x) gt (x: + 0.
(35)
100
30

---

This will imply the claimed poinwise convergence since
lim (xx)
lim 10000
Rga (x))
lim
Σ (x)
Σ t=1
9e (x) 63
80000
k-000
iEJ
lim ko
Σ NEJ
h (x) Σ
g (z) Σ c. D
lim
Σ LEJ
1 (x)
Σ
gt (x) by
lim Rg (x) (xx)
k-000
906
To establish 35
observe that as x E EQ) (V/=1 we have x & Hz. We thus distinguish two cases:
907
Case x E H
908
Using we show below that for & large enough and E Hj we have
(1 i J ie J
- - (x)x)) = 10
(36)
and thus
( - (x) + +
Σ REJe
( + + (1(()))
-ft 1) + = O.
iEJ,
909
We indeed obtain (36) as follows. Since x H agz + Bt < i.., -a 3e Therefore.
910
given the definitions of Jē (ef Definition C.1 we have:
For E J so (Wili, :]. bf(t)) (ax, Be), hence for large enough, we have :ili,
b > 0 so that a (WW [i, x + bf(i)) w -|a b [i] and, as expressed in (36):
h (x) h
W i| (W c w (WT.. + bbll) (C* bt( w/ i].
* For i : similarly, we have W + b for & large enough. Therefore, h 0 912 for l large enough. The fact that we also have (x)) 0 immediate from Equation (34) if + jr.
913 and for i = je we also get from Equation 34 that h (z) = Ne + (ee) = since a,d + 3 < 0.
914 Case x H An analog to Equation (36) for x E H is
Wh.. (. C*), bfll),
i Jr i J (D). i=j
((()) =
- i Ma(a + Be) W (Wili blll),
(37)
915 We establish it before concluding for this case.
For i Jj: by reasoning analog to the x H;, deduce that for ls large enough
(+(() (x) W1 O*).
+ blll)) for le large enough, 917 while Equation (34) yields htt (a) = 7 3e) = re(axx+ 3e) (since agz + 3e > 0 H and (x) if * je-
For i : similar reasoning yields h1(2))
31

---

Using 37 we obtain for le large enough
-
$ Σ
(x)
(x) hy (x)) + Et
iEJ
Σ w
- [1
ch) E
Wel: Vll:i, + bf(l)) + velaxx + Br) + E
vEJi
iEVī
E W +
IEJT
JEJF
$
Σ
W
Σ
wil, + 7x33)
iEJT
iEV
EiEU7 WiL.s
where in the last line we used the expression t from (32.. 920 follows that lim (z) of (x) + E = O. vz E H
919
Due to Equations 23 and 24
921 Thus combining both cases, we conclude that limg- of (2) de (z) + C 0, Var é He, as desired.
Proof of the expression
30 with A E Ly for large enough k. From 34 first deduce that
N1 (x) = Σ
realas + (e) + Σ (x) + b Vo ER.. (x) + B3
111
SES
where we recall that = = JU (UISeS)))) There only remains to show that, for k large enough, have Evesh
A + bb for every in the restricted domain Z3. where A Lr and b RR,, Note that for E Jr, our construction assures that hę is affine on Q. Moreover, in the restricted domain 22g, for k 2 Ks large enough, Teft E also behave like affine functions (cf Lemma Therefore,
Σ {+( = Σ of W (wT..:)) -c, Va 23 2 Ks RES
EES
for some vector c and binary scalars 8%. fact, 8 =iifie =-j Wi s 0, Vo E 22} and o = 1 otherwise. Thus, one chooses A Eies Wh i i c and the construction is complete. This construction allows to write A W!Wi W with:
W [
W = W S]aiag( (u) i= i NI))
where (ia i== 1..., N:)) NNN is diagonal matrix, oft 8% for S and otherwise. It is also evident that supp W ST) S T2[:,S], supp (WT[S,:) S [S. (since the multiplication with diagonal matrix does not increase the support of matrix). This concludes the proof.
923
925
926
C.3
Proof for Corollary
927
Proof. The proof is inductive on the number of hidden neurons N₁:
1. Basic case N₁ 1: Consider 0 = {(W:: b.) E Nr. the function Rs has the form:
Rx(x) = W20 b,) + b
928 where W1 [1 E = W2(1, 1] E R. There are two possibilities:
(a) 1g 0: then w2 = 0, F, is simply set of constant functions Ω, which is closed.
32

---

930
(b) 12 1]], We have 12 11xN, which makes the first assumption of Theorem 4.2 satisfied.
931
To check that the second assumption of Theorem 4.2 also holds, we consider all the possible non-empty subsets S of [T]] there is only one non-empty subset of 12, which is S = [1]]. In that case, L1g = (We RIxNo supp( W) C 1 which closed (since Lig is isomorphic to
933
R!( The result thus follows using Theorem 4.2
934
935
Assume the conclusion of the theorem holds for < N₁ S k (and any No 2 1). We need to prove the result for N1 = k + 1. Define H = {i 72(1, = }] the set of hidden neurons that are allowed to be connected the output via a nonzero weight. Consider two cases:
937
938
If H S k. we have Fi Fixz which is closed due to the induction hypothesis.
939
(b)
If H = Lk + II. we can apply Theorem 4.2 Indeed, since 1y = 11x the first condition of Theorem 4.2 is satisfied. In addition, for any non-empty S [[1]]] define H. == Uies/[i,
[No]] the union of row supports of 1 [] It is easy to verify that Lig is isomorphic to R H|| which is closed. As such, Theorem 4.2 can be applied.
942
943
C.4
Other technical lemmas
Lemma C.7 (Convergence of affine function). Let Q be non-empty interior subset R" If the sequence ( JKEN, fr R" + R x + A x + b where A E R=x" ba E R converges pointwise to a function on 92 then f is affine (i.e., Ar + b for some A E Rm b b R").
945
Moreover, limg A A and lims- by b.
947
Proof. Consider To E Oz an open subset of Ω (S'' exists since Q is non-empty interior subset of I.). Define 9 (z) = (x) - ft (zo) and g(x) = f(z) g(zo). The function g is linear and g converges pointwise g on & (and thus, on Ω2), We first prove that g linear. Indeed, for any y E Q a. B E IR such that az + By Ω we have:
g(ax + By)
lim ga(xx + By)
k
= lim ag" (x) + 3g (v)
1-000
lim g²(x) lim g²(v)
k-v
k0
ag(a)) + 3g(y)
948 Therefore, there must exist A E Rmxx such that g(Ø) = Ar. Choosing b = g(zo). we have f()) (xx) + g(z)) Ar b.
Moreover, since !2' open, there exists positive such that the ball B(x,r) Ω Choosing 4; To + (r/2)e; with the ith canonical vector, we have:
lim 9 (x.)
lim (r/2)A*ee (r/2)Aes, k-000
950 or, equivalently, the ith column of A the limit of the sequence generated by the ith column of
A Repeating this argument for all 1 <
we have lim A A. This also implies
lim b² b immediately. 952
D Closedness does not imply the best approximation property
953
954
Since couldn't find any source discussing the fact that closedness does not imply the BAP, provide an example to show this fact.
955
Consider 1]) the set of continuous functions on the interval [-1, 1]. equipped with the norm sup || 20 = max [.())), and define S. the subset of all functions f ([-1,1) such that:
['Sa dr Sr
dr =1
956
easy to verify that S closed. We show that the constant function ʃ does not have projection in S (i.c., a function g S such that || glloo infres |lf hlloo).
33

---

958 First we observe that since f O, we have Ilf - Al |l for each h E S, and we show that 95e infnes Ilf follo= 2 1/2. Indeed, for we have:
1= S.¹ dx [ dx s
///0 d [[ h dæ s 211A/l = 2 holoo-
(38)
Secondly, we show sequence of (hi JREN such that hn E S and lima-too || 1/2. Consider the odd function hn (i.c. hn(z) = - (x)) such that:
-cc Cnn
x 1E/1/n
hn (n())= (x)
E 1/n1)n)
where Cn n2((2n 1). is evident that hn because:
S.¹ Nn dx Sr nn dx S Nn dr =2
2//1 Nn dx (" hn dx
On
Ca(n - 11) Cn (2n -1
2n
n
n
960
Moreover, we also have lim, ||0,|1 lima- Gn = 1/2.
961
Finally, we show that 1/2 cannot be attained. By contradiction, assume that there exists E S such
that I glooo so 1/2, i.e., as we have seen, || 1/2. Using Equation (38), the equality will only hold if g(x) = 1/2 in [0, 1] and g(z) = -1/2 in [-1, 0j. However, is not continuous, contradiction.
982
963
34


Reviews:
[{"review_id": "ozVHRnjQBI", "reviewer": "Reviewer_5AbX", "summary": "The paper studies the existence of an optimal solution to the objective of training a ReLU neural network under certain sparsity patterns. They consider two topological properties of the input function space (the best approximation property, and closedness). They provided series of results on scalar-valued neural networks, shallow neural networks, neural network with one hidden layer. Specifically, they provide necessary and sufficient conditions on the sparsity (e.g., fixed sparsity level or pattern) of the neural network to guarantee existence of an optimal solution to the training loss function.", "questions": "- For corollary 3.1, what is the dimension of the hidden layer?\n\n- Could you clarify in simple words the term number 2 on line 305 (addition of this will improve clarity).", "limitations": "Addressed properly.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper studies an interesting problem which relates to the stability of the neural network training due to the non-existence of an optimal solution given a sparsity pattern. The paper covers a good literature review and stand themselves very well compared to prior works. Their contribution is clear.\n\nThe title of the paper is very related to the goal of the paper. The paper is coherent in studying the problem of interest.\n\nThe paper is written clearly. Each theorem/proposition is followed by lemma/corollary and informal proof sketch which makes it very easy to follow. For examples, the paper contains a numerical example very early on in the paper to further give intuition on the importance of the problem and a plausible scenario where an optimal solution does not exist.\n\nThe results provide new insights on if a neural network will have an optimal solution. Table 1 and 2 clearly state how their work differs from prior work.", "weaknesses": "It would be nice in the main paper to provide more tangible examples on what sparsity examples on what architectures may/may not result in existence of an optimal solution. NeurIPS has a broad range of audiences from theory and application (addition of this can attract more application-based deep learning researchers).\n\n\n- minor: corollary 3.1, valed --> valued", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for his/her comments on our work.\n\n**Comment on the weakness** Our work allows to answer the following question: if the supports of the weight matrices are randomly sampled from a distribution, what is the probability that the corresponding training problem potentially admits no optimal solutions? While simple, this setting does happen in practice since random supports/binary masks are considered a strong and common baseline for sparse DNNs training [1].\n\nIndeed, thanks to Theorem 3.1, if $\\mathcal{L}\\_\\mathbf{I}$ is not closed then the support is *bad*. Although the algorithm of Lemma 3.3 to *decide* if $\\mathcal{L}\\_\\mathbf{I}$ is closed is not polynomial, for one-hidden-layer NNs, there is a polynomial algorithm to *detect* non-closedness: if the support constraint is *locally similar* to the LU structure (precisely, if it satisfies the condition of Theorem 4.20 of [2]), then $\\mathcal{L}\\_{\\mathbf{I}}$ \nis not closed. The resulting detection algorithm can have false positives (i.e., it can fail to detect more complex configurations where $\\mathcal{L}\\_\\mathbf{I}$ is not closed) but not false negative.\n\nWhen testing it on a one-hidden layer ReLU network with two $100 \\times 100$ weight matrices, drawing uniformly at random two supports of respective cardinality\n$|I_1| = 3000$ and $|I_2|=2000$ (i.e. 30\\% of nonzero coefficients on the first layer, and 20\\% on the second one) and averaging over 100 draws, the algorithm estimates the probability of \"bad\" supports to 85\\%. For sparser random supports (when $|I_1|=|I_2|=2000$), the estimated probability is nearly 100\\%.\n\nWe will add a brief description of these consequences of our work in the final version, thank you for this opportunity.\n\n**Answer for questions**\n\n1. The dimension of the hidden layer is arbitrary (there is no assumption on it). This will be clarified in the final version.\n\n2. An equivalent (and probably simpler) way to state the second point is: for each fixed binary diagonal matrix $D$, the set $\\\\{W_2DW_1 \\mid \\text{supp}(W_1) \\subseteq I_1, \\text{supp}(W_2) \\subseteq I_2\\\\}$ is closed. This will be clarified in the final version.\n\n**References**\n\n[1] S. Liu, T. Chen, X. Chen, L. Shen, D.-C. Mocanu, Z. Wang, M. Pechenizkiy, The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training, International Conference on Learning Representations, ICLR, 2022.\n\n[2] Q.-T. Le, E. Riccietti, R. Gribonval. Spurious Valleys, NP-hardness, and Tractability of Sparse Matrix Factorization With Fixed Support. SIAM Journal on Matrix Analysis and Applications.\n"}, {"review_id": "AzuZmFu8lj", "reviewer": "Reviewer_7u6K", "summary": "This paper provides necessary and sufficient conditions for whether a neural network training problem admits an optimal solution, that is, whether weights and biases exist such that the infimum of the loss function is actually attained. This is done for the classical case of empirical risk minimization on a finite training set as well as for function approximation on a continuous input domain.", "questions": "- Is there any chance to obtain a hardness result for the computational problem considered in Section 3.3? NP-hardness? Hardness for the existential theory of the reals (which is always a good candidate if the best known solution uses quantifier elimination)? See related results for NN training: https://arxiv.org/abs/2102.09798; https://arxiv.org/abs/2204.01368.\n- Pushing the relation to the existential theory of the reals even further, I find it very interesting that you obtain such a sharp difference between the scalar-valued output case and the multi-dimensional output case (Section 3.4). The same seems to be true for the training complexity of such shallow networks: while scalar-output networks can be trained with a combinatorial search algorithm, certifying that the problem is in NP, it turns out that training a shallow network with multi-dimensional output is ER-complete and therefore much harder (https://arxiv.org/abs/2204.01368). Again I wonder: is there any relation to your results?", "limitations": "The paper properly states under which circumstances (mathematical assumptions) the results are valid.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- I think the investigated question is highly interesting already for purely theoretical reasons: the existence of an optimal solution is such a fundamental property of an optimization problem. We should be able to answer this question for our \"favorite\" optimization problem, namely training a neural network. This work seems to play a crucial role in (i) posing this question and (ii) providing results for some cases.\n- Apparently the non-existence of an optimal solution can also explain divergence in practical settings, which I find compelling. Still, I would like to emphasize that the paper is a theory paper and should be judged as such.\n- The paper involves quite some amount of non-trivial mathematics. Although the tight reviewing schedule does not allow me to verify all details, the parts I read seem to be mathematically sound.", "weaknesses": "- Many cases for the posed question remain open. In particular, most of the results are concerned with 2-layer NNs only.\n- The presentation of the results in the intro could be improved. Some definitions could be made earlier (or at all). See my detailed comments below. Also I find it quite difficult to read the Tables 1 and 2. One basically has to read the rest of the paper in order to truely understand what these tables are about.\n\nComments for the authors to improve the paper (not meant as true weaknesses):\n\n- title: remove the space between \"optimum\" and the question mark\n- line 54: \"the best approximation property (BAP), which guarantees the existence of an optimal solution\" -> Is this the definition of BAP or just a consequence? Please make this clear. You might want to define BAP in a proper definition environment.\n- lines 57-79: for readers unfamiliar with sparsity in neural networks, it is quite hard to understand your contributions without reading the \"notations\" part later. You should spend some efforts in explaining terms like \"(structured) sparse networks\", \"fixed sparsity level\" vs. \"fixed sparsity pattern\", etc. already in the introduction. I think \"sparsity level\" is only implicitly defined very late in the paper.\n- line 67: Here (and at some other places in the paper) you use the term \"learning problem\" as a synonym to \"training problem\". Some people understand \"learning problem\" as the problem to minimize the generalization error, as opposed to the \"training problem\", which only aims to minimize the training error. At least in the finite domain case you are definitely in the latter regime, so I suggest to use \"training problem\" consistently.\n- Tables 1 and 2: the relation to the sparsity constraints is not really clear in the tables. In particular, what does the \"sparse\" adjective in brackets in the architecture column mean? Why is it in brackets?\n- caption of table 2: there is an extra space after the opening bracket\n- line 124: it is a bit weird that the \"notations\" section is part of the \"related work\" section.\n- line 195: contains -> contain\n- line 261: valed -> valued\n- line 293: a bit redundant \"many other domains such as [...] and much more\".\n- line 301: \"(in the whole paper we naturally assume B > 0)\" -> state this earlier in the paper when you use B for the first time.\n- line 303: provide a reference to the proof of this theorem in the appendix.\n- line 312: what you call \"plain\" here is what I would call \"fully connected\". You should maybe use this term here and elsewhere in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for his/her comments and questions.\n\n**Comments on weakness** We really appreciate the comments on the overall organization and presentation of the paper and will implement them correspondingly in the final version. \n\nRegarding the *limitation to 2-layers only*, all our *negative results* (sufficient conditions for non-closedness, based on Theorem 3.1) are valid for any depth.  Several technical lemmas for our *positive results* (e.g.  Lemma C1 and Lemma C2 in the Appendix) also hold for MLPs with arbitrary depths. These results could be re-used to analyze more completely the deeper case, which is however left for future work. Moreover, our positive results apply to non-scalar outputs and take into account the effect of sparsity constraint, while (to the best of our knowledge) existing positive closedness results were limited to one-hidden-layer, scalar-valued outputs, with no support constraint.\n\n**Answer to question**\n\n1. The question is indeed interesting. We found several links between the papers mentioned by the referee and our setting in Section 3.3. Indeed, in the proof of the main result of the first paper, the constructed ``hard'' neural network does not have all the connections (i.e., the support is not full), it is assumed to have the identity activation function (Theorem 2) and all biases can be assumed to be zero (Observation 5). This is very similar to the setting of sparse matrix factorization. Nevertheless, it remains non-trivial to adapt the techniques used in the articles mentioned by the referee to the problem of deciding on the closedness of the semi-algebraic set $\\mathcal{L}_\\mathbf{I}$. Still, we believe this interesting question is worth investigating further.\n\n2. We think the two results are somewhat related. In fact, our proof of Theorem 3.4 uses the normalization technique from Algorithm~1 [1]. The exact same algorithm is used in the paper mentioned by the referee to argue that the training of scalar-valued output, one-hidden layer NNs is NP (if the input and hidden-layer dimensions are constant). We believe it is interesting to exploit this observation and further study the separation between the cases of scalar-valued and vector-valued output.\n\n**References**\n\n[1] R. Arora, A. Basu, P. Mianjy, A. Mukherjee, Understanding Deep Neural Networks with Rectified Linear Units, International Conference on Learning Representations, ICLR, 2018."}, {"review_id": "z8TCMcz2KH", "reviewer": "Reviewer_oxZZ", "summary": "This work studies the existence of global minimum in a sparse deep learning setting", "questions": "See weakness", "limitations": "I think the work discussed the limitations well", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think this work touches on a very important problem that is understudied in the field: the existence of the global minimum for deep nonlinear networks. It is easy to image toy examples for which the global minimum does not exist, but until this work, there does not exist a formal study of this problem\n\nThe problem is important and novel. Linking this problem to training a sparse network is novel, I thus support its publication, though with some reservation", "weaknesses": "To me, I think the main problem is that the results are quite weak, and that the main example is not quite convincing or relevant. The example of a LU network is quite artificial and it is hard to imagine that this situation arises in deep learning. I think this work can benefit greatly if it identifies a more relevant and convincing example (and it should not be difficult to achieve). This is the main reason I give this work a weak accept\n\nThere is one minor problem that I do not find serious but is worth some attention. While the paper mostly motivates from the viewpoint of the popular pruning literature, this work can benefit from discussing more about regularization-based methods for compressing neural networks. For example, see the recent work in https://arxiv.org/abs/2210.01212, which also discusses the existence of the global minimum. At its face value, the results in this work seems to motivate and advocate the use of regularization-based compression methods in deep learning; is this interpretation correct? If not, why? I think discussing this point can better clarify the implication of this work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for his/her comments.\n\n**Comments on the weakness**\n\nFor the *first* point, our Example 3.1 about the \"LU architecture\" is meant to be pedagogical, and its ultimate goal is to show that even in pretty simple cases there may be actual issues related to non-closedness. In our response to Reviewer 5AbX (https://openreview.net/forum?id=dTj5tH94xv&noteId=ozVHRnjQBI), we highlight that our results can also be used more concretely to detect supports leading to a non-closedness problem and that this occurs frequently for randomly pruned MLPs which serve as a baseline for sparse DNNs training [1].\n\nFor the *second* point,  our main message is not to advocate the use of regularization-based compression, but rather to suggest that it is worth detecting supports leading to non-closedness. \n\nWhile regularization with a coercive function indeed ensures the existence of a minimizer, this however implies tradeoffs between the data fitting term and the penalty, usually tuned via a parameter $\\lambda$.\nUnfortunately, there may not be any satisfying tradeoff in non-closed cases, as is illustrated in Figure 1 (in the pdf of the global response) under the setting of Example 3.1 (in our submitted paper). Four curves display the concrete tradeoffs obtained along the training trajectory, when optimizing a regularized loss with four values of $\\lambda$. In addition, we display random (yellow) and optimum (black) \"oracle\" tradeoffs obtained using approximate LU factorizations of the matrix $A$ of Example 3.1. These oracles are built as (exact) LU factorizations of perturbed matrices $A+N$, where $N$ is a noise matrix scaled to achieve prescribed approximation levels (and therefore specified empirical losses). Even though arbitrarily small empirical loss is theoretically possible, reaching an empirical loss below $0.1$ with an oracle approximate LU factorization requires LU factors with a norm of the order of $10^3$. The required norm quickly increases when improving the precision of the oracle LU approximation.\n\n**References**\n\n[1] S. Liu, T. Chen, X. Chen, L. Shen, D.-C. Mocanu, Z. Wang, M. Pechenizkiy, The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training, International Conference on Learning Representations, ICLR, 2022."}, {"review_id": "kbUMGaaKnl", "reviewer": "Reviewer_ay34", "summary": "The authors are interested in the following question : « Given a deep learning architecture possibly with sparsity constraints, does its corresponding optimisation problem actually admit an optimal $\\theta^*$? » While it is mostly taken for granted that the answer is « yes », the author proves it to be true in some cases, and false in others. They derive an algorithm in order to verify a sufficient condition in order for there to exist. More then a single way the sparseness of the considered network in ensured is considered in the article.", "questions": "1. If the practical interest in studying problems with finite $\\Omega$ is clear, I have a hard time understanding the interest of studying non-closed $\\Omega$ and how it applies to real-world situations.", "limitations": "I feel like the authors downplayed the importance of some limitations of their work (see Weaknesses – Major).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The relevance of the work is well defended in the introduction.\n\n2. The results concern a large pool of predictors, considering a regression task.\n\n3. The results concern more than one way of ensuring networks to be sparse.\n\n4. The results seem to be a significant add-on to the literature concerning closeness and non-closeness of problems involving the training of (sometimes sparse) neural networks.\n\n5. Example 3.1., though having some flaws (see Weaknesses - Major - 1.2.), is really important for illustrating what might otherwise be a bit hard to grasp for the reader, and proving the issues that might be encountered when not considering the initial question : « Given a deep learning architecture possibly with sparsity constraints, does its corresponding optimisation problem actually admit an optimal $\\theta^*$? ».", "weaknesses": "_Major_\n\n1.1. Regularisation is indeed (lines 41-42) a common way to bypass this question, but the notion of regularisation in itself is, especially when it comes to neural networks, mostly important for limiting over-fitting. I didn’t find the arguments regarding the discarding of regularisation for neural networks training really compelling (lines 44-47), especially since it wasn’t supported by any work from the literature.\n\n1.2. Concerning Example 3.1 and the discussion that follows (lines 216-221), the discussion is based on what's displayed on Figure 1 only, forgetting about validation / test loss; saying that $L^2$ regularisation « might be detrimental » thus forget about validation / test loss. And if the goal is simply to over-fit a problem, then even smallest regularisation would make the parameter converge to certain values, practically not affecting the obtained error in train, which probably wasn't the case, since a single (and arbitrary) regularisation parameter was applied for each training.\n\n2. The assumptions required for having Proposition 3.1. to hold (continuous, coercive) are limiting, making the use of 0-1 loss impossible (and cross-entropy as well, if I’m correct). The way the networks are defined too, since no soft-max activation function can be used on the output layer. Those loss functions (and the soft-max) being crucial when it comes to classifications, the results are mostly relevant only for regression, which is really not the most popular type of task when it comes to neural networks. Though it has been briefly mentioned on lines 176-177, I feel like the authors were not honest enough regarding how limiting the assumptions and the way the networks are defined are. For example, a sentence such as « Though our study theoretically applies to classification schemes, it more naturally suites regression schemes, considering the assumptions made in [...] » in the abstract, or at least in the Introduction section would be sufficient.\n\n3. The motivations of the work are partially theoretical and mostly practical, but the results, though interesting, for it proves not every network has an optimal set of parameters in different settings, are mostly inapplicable in practice, limiting the impact of the work.\n\n4. The terminology in Table 1 might be misleading, since the term « shallow » is vague and that when it comes to Theorem 3.4 and Corollaries 3.1, 4.1, 4.2 and 4.3, « shallow » stands for « 1-hidden-layer ». What are the limitations for the works from the literature with regards to the depth of the networks? If it is 1-hidden-layer, then the whole table should refer to « 1-hidden-layers architecture », and not « shallow architecture »; if it is deeper than 1-hidden-layer in at least one case, than the underlying maximum depth should be displayed in the table.\n\n\n\n_Typos / Minor_\n\n1. Line 126 : « agrees with $\\mathbf{A}$ on rows in $S_{\\underline{r}}$ (resp. columns in in $S_{\\underline{c}}$) »\n\n2. I expect Lemma 3.2. of the main paper to be coherent with what is stated on lines 505-506 for a camera-ready version of the article.\n\n3. Lines 259 and 260 : The statement « This constraint on the sparsity level of each 260 layer is widely used in many works on sparse neural networks » is not supported by any citation.\n\n4. Line 261 : « Consider scalar-val\\underline{u}ed ».\n\n5. Line 359 : « cf\\underline{.} »\n\n6. Using $\\Omega$ for both the finite and the non-close cases is a bit confusing; it might be more convenient to differentiate these two cases with a separate notation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for his/her comments and questions.\n\n**Comments on the weakness**\n\n1.1. While regularization with a coercive function indeed ensures the existence of a minimizer, this however implies tradeoffs between the data fitting term and the penalty, usually tuned via a parameter $\\lambda$.\nUnfortunately, there may not be any satisfying tradeoff in non-closed cases, as is illustrated in Figure 1 (in the pdf of the global response) under the setting of Example 3.1 (in our submitted paper). Four curves display the concrete tradeoffs obtained along the training trajectory, when optimizing a regularized loss with four values of $\\lambda$. In addition, we display random (yellow) and optimum (black) \"oracle\" tradeoffs obtained using approximate LU factorizations of the matrix $A$ of Example 3.1. These oracles are built as (exact) LU factorizations of perturbed matrices $A+N$, where $N$ is a noise matrix scaled to achieve prescribed approximation levels (and therefore specified empirical losses). Even though arbitrarily small empirical loss is theoretically possible, reaching an empirical loss below $0.1$ with an oracle approximate LU factorization requires LU factors with a norm of the order of $10^3$. The required norm quickly increases when improving the precision of the oracle LU approximation.\n\n1.2. We thank the referee for this remark.  The validation error is indeed important. Choosing to display the Jacobian loss was motivated by the fact that it is indeed essentially proportional to the validation loss, as illustrated in Figure 2 in the pdf of the global response (with more values of $\\lambda$ than in Figure 1 in the submitted paper, as a sanity check). This can also be proved theoretically under some assumptions. This was however too implicit and we will replace the Jacobian loss in Figure 1 (of the submitted paper) by the validation loss.\n\n2. The assumptions made in Proposition 3.1 are indeed natural for the regression case but not for the classification case, and we agree with the referee that it is worth making the remark more visible since the beginning of the paper, this will be fixed in the final version. In the classification case, using the soft-max after the last layer together with the cross-entropy loss function indeed leads to an optimization problem with no optimum (regardless of the architecture) when given a *single* training pair $(x,y)$. This is due to the fact that changing either the bias or the scales of the last layer can lead the output of the soft-max arbitrarily close to an ideal Dirac mass. It is an interesting challenge to identify whether sufficiently many and diverse training samples (as in concrete learning scenarios) make the problem better posed, and amenable to a relevant closedness analysis. This point will be highlighted after Proposition 3.1.\n\n3. The main contribution of the paper is to shed light on a phenomenon (absence of an optimum) that appears even in the simplest MLP architecture, which was mostly overlooked before (with the exception of few specialized papers, presenting results based on stronger assumptions). The first concrete consequence of our work is the possibility of detecting if a pruned MLP support poses a potential problem. A more general study of closedness for other architectures is left for future work, as this would require different tools. For MLPs, indeed the analysis is based on known results of matrix factorization. It seems possible for instance to generalize this analysis to the case of skip connections, because networks with skip connections can be modeled as larger ReLU networks with blocks of identity matrices as weights, so that their presence would add a further linear term in the Equation (27) (Lemma C.4, Appendix), which could be treated in the same way as the one that is already there. Convolutive layers are also likely to be amenable to an adapted analysis. \n\n4. We will consistently use \"one-hidden-layer\".\n\n**Answer for question**\n\nWe agree that the case of a finite $\\Omega$ is the one encountered in practice when learning from actual training sets. Considering a domain $\\Omega$ such as the unit cube, with non-empty interior, is indeed mostly of theoretical interest, but seems, for example, crucial when analyzing generalization properties, as the \"optimal target function\" is traditionally expressed as the minimizer of an expected risk defined as an integral on such domains or even on the whole space. Understanding whether this optimum target function exists is thus of interest."}]

Author rebuttal:
Dear reviewers,

In this global response, we attach a pdf file containing figures for our rebuttal.

Meta-review: This paper shows that optimization problems involving deep networks with certain sparsity patterns do not always have optimal parameters, and that optimization algorithms may then diverge. The results are interesting and all reviewers recommended acceptance. Some of the reviewers have pointed out some typos, and I suggest that the authors should revise the paper accordingly.
Decision: Accept (poster)