Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on approximation of NNs in the narrow regime, i.e, when the width of the network less than the input dimension ($n_0$) and asks the question:
What compact subsets M of $R^{n_0}$ still allow universal approximation or exact interpolation for all functions that map from M to R.?

It first shows the existence of compact subsets that do not allow for such universal approximation guarantee.

Then the paper presents sufficient conditions on certain compact subsets so that some universal approximation/exact interpolation guarantee can be attained and these results are targeted for clustering/classification applications. The functions here are piecewise-constant on disjoint compact sets.

The assumptions on the activation functions are general which includes most of the commonly used ones in practice as well.
main_review: Strengths :

The narrow network regime is not as well studied and is a useful pursuit to obtain a complete characterization of NNs and this paper definitely takes some steps in that direction. 

Section 3, which describes the maximum principle is interesting as it talks about the existence of compact subsets that cannot have an universal approximation guarantee when the activation functions are monotonic and continuous, even if you consider classes of NNs with arbitrary depth!

Section 4, talks about subsets that can guarantee exact interpolation and universal approximation guarantees. They specifically consider subsets that are disjoint union of a finite number of compact sets and functions that are constant in each disjoint piece. This can be considered a large class of functions that are used for clustering/classification applications. They provide some sufficient conditions that these sets need to satisfy in order for exact interpolation by a constant depth ReLU network (for two compact sets and for more than two, there exists some depth (input dependent) that can give exact interpolation.

Finally, they show that an arbitrary finite sample set can be exactly interpolated by a constant width and depth network that has a cosine activation function.

Weaknesses:

Theoretical:

My main issues is about the approximable subsets. The authors consider studying functions that are constant over disjoint compact sets, akin to clustering/classification type applications. They present results that target exact interpolation in Theorem 2 and Corollary 2. Now can the assumptions on mutual locations be removed if targeting universal approximation and allowing the depth to be arbitrarily large ? Or is it that in this case exact interpolation is as hard as universal approximation? 

In addition, I was wondering about the applicability of theorems in Sections 3 and 4 with a cosine activation function which is not a monotonic function, but does well on an arbitrary finite set (Theorem 3)? It would be nice to have a discussion to consider the applicability of non-monotonic activations as well.

As a general comment, when using NN($n_0$) to represent the class of functions, if possible it would be useful to mention the depth (which may be input dependent) to understand the dependence on the depth which is able to approximate/interpolate the target functions.


Presentation and minor issues:

Another issue is about the presentation of results. I think the paper would be much better with illustrations of sets that help reader visualize the geometry, as these sets are interesting examples/counter-examples. 

Minor suggestions:
1) In the Introduction ..."An important results states that a width larger..", is stated without mentioning where the result appeared (which is mentioned in the next section though).
2) In  page 4, when the authors mean $\sigma$ is partially constant, do they mean piecewise monotonic? It would be nice to have the statements of all the auxiliary theorems and lemmas that are not common to be in the appendix for easy reference.
summary_of_the_review: I think the problem is definitely interesting, to understand the limitations of narrow networks and of course the extent of positive results that can be extracted from it. I think this work takes some steps in that direction, but definitely requires a bit more investigation (as specified above) and also the presentation could be made better with some illustrations/visualization of the sets in the main results, which may help communicate the ideas in a better way.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In the mathematical theory of neural networks, universal approximation theorems typically establish the density of a class of neural networks within a certain function space. In recent years, it has been shown that a width larger than the input dimension is needed to allow universal approximation theorems for continuous function spaces defined on arbitrary compact sets.  In this paper, the authors investigate what kind of subsets of R^n allow for a universal approximation theory with neural networks that have a width <= input dimension. 


main_review: The manuscript has three main contributions: (1) A maximum principle when the activation function is continuous and monotonic (such as ReLU), showing that the neural networks must be at least n_0 + 1 wide, (2) An interesting condition on two compact sets (one of them being contained in a cone-like sector that doesn’t intersect with the other) that is sufficient to allow exact fits of piecewise constant functions, and (3) A width 1 and depth 3 neural network with cosine activation is a universal approximator for a finite sample set. 

Strengths: 
 - The paper is well written and easy to follow. The discussion regarding prior work is quite clear and extensive.
 - The authors are investigating an unusual question by restricting the types of compact sets to prove universal approximation theorems. Therefore, I think the manuscript has significant merit in the way that it is investigating universal approximation theorems. 
-  I agree with the authors that universal approximation on certain subsets is often what is needed in practice. 

Weakness:  
 - Some of the theoretical results only apply to monotonic activation functions, which covers many important activation functions, but certainly not as general as related recent papers on deep narrow neural networks.  
summary_of_the_review: In my opinion, the article is asking an interesting question by restricting to certain compact sets. I believe that the manuscript is making a reasonable theoretical contribution to the analysis of deep narrow neural networks.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the question of expressivity of neural networks that have restricted width. Specifically, the main question is "what happens when the maximum (among all layers) width is less or equal to the input dimension?" 

From prior works, it is known that such width-restricted networks cannot possibly express all continuous functions on arbitrary compact sets. So the next natural question is what kind of functions/subsets M of R^n are amenable to approximation via such networks?

The main contribution is the derivation of certain topological conditions on compact sets M in R^{input dimension} that allow or exclude universal approximation by such networks. 

First, the authors derive a maximum principle stated as Theorem 1: If M is a compact subset of R^{input dimension}, then a neural network of width at most the input dimension, equipped with any continuous monotonic activation function  will necessarily attain its maximum value on the boundary of M. As a consequence, the authors show how previous lower bounds on width (w\ge n_0 +1) are tight by providing several tight examples.

Second, the authors investigate the case where the domain consists of two disjoint compact sets and the goal is to approximate functions that take constant values on each of these sets. They give a sufficient condition under which shallow ReLU nets of width $w=n_0$ (the input dimension) and depth 4 can expreess them.

Third, they also consider some expressivity properties of simple networks with cosine activations that have width only 1 and depth 3.


main_review: The reviewer finds the topic studied in the paper very interesting. Expressivity bounds have been studied to understand benefits of depth. However, the case of width is also interesting and appears to be less studied in the literature. The basic fact here is that universal approximation is impossible if the width of a network is severely restricted to be less than the input dimension $n_0$. Given this, I find the question studied in this work well-motivated and natural.

The only concern with the present work is the novelty. Even though it is technical, its main message is not too strong. The reviewer does not follow how their "results give theoretical insights on the kind of feature extraction earlier layers need to implement in order to allow the later layers to solve a givem machine learning task", as they state in Section 2. Moreover, the reviewer thinks that the paper has an overall nice collection of (relatively) small results, but none of them is particularly strong. The maximum principle derived is perhaps the most interesting; however, it seems incremental given the Beise et al. (2021) studying the decision regions of narrow deep NNs and Johnson (2018). The other two contributions about width-restricted ReLU nets of depth 4 and cosine nets of depth 3 are nice but not in par with an ICLR paper.


summary_of_the_review: Nice motivation about the question, but the results presented are relatively weak. There is not a "main" message of the paper that is in par with ICLR standards.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents three results concerning the universal approximation of functions on compact sets under a width regime for which universal approximation in general is not possible. The authors make a convincing case that this represents an important frontier both for applications and for a better understanding of what neural networks can represent. While I appreciate the first result, I am confused with the second and I do not think the third is relevant.

These results are the following:

1) The maximum principle

This is an interesting observation about the maximum (and minimum) value achieved by neural network with continuous monotonic activation and width bounded by the input layer on a compact domain is always at the boundary of such domain. Trying to break their result made me understand and agree with their claim that this could be understood as a "root cause why universal approximation with functions from NNσ(n0) on arbitrary compact sets is impossible".

2) The result on disjoint domains

In Section 4, the authors claim through Theorem 2 a result applicable to a "finite collection of disjoint n0-dimensional compact sets". Notably, most of their work there focuses on exact representation, which reflects the fact that they are considering functions that are constant on each disjoint set. We can reasonably associate that to classification tasks, but then we cannot assume any probabilistic meaning with something like a softmax layer.

3) The result on harmonic activations

The authors shows that universal approximation can be achieved on a finite and discrete domain with the composition of cosine functions. This result lies entirely on the domain being discrete and finite, which actually breaks any dependence to the width of the input layer. For that reason, I do not think that it is that relevant because it has nothing to do with the main theme of the paper.
main_review: # Major observations

In Section 4, repeating what I said above, the authors claim through Theorem 2 a result applicable to a "finite collection of disjoint n0-dimensional compact sets" However, except for Corollary 2, which is not explicitly linked to Theorem 2, the entire discussion for the second contribution focuses on only 2 sets. Hence, in Section 6, it is not clear how they claim to be validating the result by using domains consisting of more than 2 disjoint sets.

In Theorem 2, do the authors really mean $K_2 \subset \mathbb{R}^{n_0} \setminus \overline{S}$ instead of $K_2 \subset \mathbb{R}^{n_0} \setminus S$? 

# Minor observations

1) Introducion

", we refer to (DeVore et al., 2020) for an overview on recent developments": use semicolon (;)

"‖·‖is the Euclidean norm": do not start a sentence with something other than a word

"j-te coordinate axis": j-th

I can follow your notation, but I strongly encourage you to describe what L is at the begining instead of at the end, at which point you have already used it to define a number of other things.

Additional references:
- On the discussion of expressiveness in terms of depth and width: [1] (figure 5)
- On the ability of memorization in terms of expressiveness: [2] (figure 5, left)

2) Related work

The meaning of $C$ and $L_p$ is never mentioned; neither what exactly each term is in the notation that you start using here. For example, that the first term in the tuple is the domain and the second is the image encompassing the family of functions.

"multiply pairwise compact components": multiple

3) Maximum principle

Remind the reader what "NNσ(n0)" stands for.

"on arbitrary compact sets is impossible:": does not seem to be the right place to use a comma

Briefly repeating the meaning of technical terms can make wonders to accessibility.
In Theorem 1, I would recommend expaning the statement as "takes its maximum value *at the boundary* ∂M".

"to network function of width larger than the input dimensions": confusing; please rewrite

"straight forward": straightforward 

"In Theorem 1 show that": Theorem 1 shows that

4) Approximation properties on subsets

"on such kind of sets": that seems to imply whether it applies to each set individually; perhaps something like "on such domains" would be better here

7) Conclusion

"haven shown": have shown

"with cos as activation function": with cosine as activation function

A) Appendix

Proof of Corollary 2: what do you mean by "Proposition 1.2"?

# References cited

[1] https://arxiv.org/abs/1711.02114

[2] https://arxiv.org/abs/1906.00904
summary_of_the_review: In full disclosure, I am curious to know what the other reviewers think of the first contribution, but at this point this is the most positive part of the paper in my view.

However, the organization and discussion of the second contribution really confuses me. I am not comfortable with the current organization of the results related to Theorem 2 and the corresponding experiments in Section 6.
review_title: null

Meta-review: *Summary:* Study expressive power of narrow networks. 

*Strengths:*
- Study the narrow setting, which is not as well studied as the wide setting. 
- Some reviewers found the paper well written. 

*Weaknesses:*
- Restricted class of targets and activations. 
- Similar results have appeared in previous works. 

*Discussion:* 

99iL asked about the possibility to remove certain assumptions and the extension to other activations. Authors answer negatively to both. 99iL acknowledges the response and concludes the so-called maximum principle is the most interesting result, but also points out that similar results appear in previous work and that it would have been good to see some extensions. qHTG indicates that the paper is well written and has interesting contributions but that some of the theoretical results only apply in settings that are more restrictive than in other recent related works. Authors agree that generalizations deserve to be investigated in the context of the presented results, but point out that their principle does not apply in that case, and hence that such generalizations are out of scope. Although qHTG identifies several good aspects in this work, they maintain the overall assessment of just marginally above the threshold. PCRn finds the work very interesting but is concerned about the novelty and points out that although the work is technical, the main message is not very strong and that the extraction of insights to solve tasks is not as clear. PCRn concludes that the paper presents various relatively weak results but not a sufficiently significant message. Authors remark that some of their results constitute a mathematical tool for future works. 

*Conclusion:* 

One reviewer rated this work marginally below the acceptance threshold and three other marginally above. Considering the reviews and the discussion, I conclude that this paper obtains a few interesting results but leaves much for future work. Further development of the current results would make the article significantly stronger. In view of the very high quality of other submissions to the conference, I find that this article tightly misses the bar for acceptance. Therefore I recommend to reject this article. I encourage the authors to revise and resubmit.
Decision: Reject