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.
Strengths
1. The relevance of the work is well defended in the introduction.
2. The results concern a large pool of predictors, considering a regression task.
3. The results concern more than one way of ensuring networks to be sparse.
4. 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.
5. 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_
1.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.
1.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.
2. 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.
3. 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.
4. 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.
_Typos / Minor_
1. Line 126 : « agrees with $\mathbf{A}$ on rows in $S_{\underline{r}}$ (resp. columns in in $S_{\underline{c}}$) »
2. 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.
3. 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.
4. Line 261 : « Consider scalar-val\underline{u}ed ».
5. Line 359 : « cf\underline{.} »
6. 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.
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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
I feel like the authors downplayed the importance of some limitations of their work (see Weaknesses – Major).