Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 
Summary: The authors tighten the analysis of the minimum width for universal approximation with relu networks for Lp functions, where they have an exact characterization in terms of the input and output dimensions.

The paper is well written and easy to follow. The review of prior art is quite clear. 

major comments/questions

1. It appears that the main result on Lp functions can be seen as a generalization of Hanin and Sellke (2017)'s result for d_y=1 to arbitrary d_y. Could you contrast the main differences in the proof technique? 

2. It's interesting that uniform approximation is harder to obtain with relu networks, while relu+step works. However, step functions are not ideal from a practical perspective due to the a.e. zero gradient. Is there an optimization-friendly activation that satisfies uniform approximation with minimal width?

3. Does 'relu networks of width m' refer to networks where the number of layers is arbitrary? Could you please clarify?  What is the minimum number of layers required for the results to hold? Are there any implications for relu networks of fixed layers, e.g., two and three layers?

minor comments.
Table 1. Ours (Theorem 2) has max(d_x+1,d_y), but isn't d_y=2 in this case?
review_title: This paper tightens the analysis of the minimum width for universal approximation with relu networks for Lp functions. The paper is well written and provides strong results.

final_score: rating: 7: Good paper, accept
review_content: ==== Summary ====

The paper studies the minimal neural network width needed for universal approximation. While previous papers on the subject merely provided lower and upper bounds, this paper derives exact bounds on the minimal width. The paper considers both ReLU networks, as well as general activation functions, and examines approximation under both uniform norm and $L_p$ norm. In the case of functions with high-dimensional outputs, the derived bounds are better than previously thought ($d_x + d_y + 1$ to $\max(d_x + 1, d_y)$), with possible implications to practical  network design.

==== Detailed Review ====

Main strengths:
* The first exact bounds on the minimal width required for universal approximation, closing the gap between lower and upper bounds of previous results.
* Significant improvement for the case of $L_p$ functions with multi-dimensional output, with possible practical implications. For encoder-decoder style networks, which are common in many vision and language tasks, prior results had suggested a width double the input dimension, whereas here it has been demonstrated to be sufficient to use the same dimension as the input (+1).
* Show that uniform approximation with ReLU networks is slightly weaker than with networks with discontinuous activations (specifically, using both ReLU and step functions).
* The results are very clearly presented, as are their comparisons to previous bounds, including a very intuitive proof sketch.

Main weaknesses:
* For the case of scalar $L_p$ functions, the previous "gap" was merely off by one, i.e., $d_x + 1 \le w_{\min} \le d_x + 2$. In this particular situation, the improvement in absolute terms is quite minimal.
* Even in the general case, the prior lower and upper bounds were already asymptotically tight.

I recommend the paper be accepted, since the paper provides exact bounds that close the gap between lower and upper bounds, and that helps us understand these networks better. Although the gap has already been quite small in some situations, which might be regarded as incremental, in other cases, such as the very common encoder-decoder setting ($d_x = d_y$), the gap is large enough to affect practical considerations when designing compact networks. These improvements should be of interest to the general ML community.
review_title: Review

final_score: rating: 7: Good paper, accept
review_content: This paper wants to establish tight theoretical lower-bounds on the minimum width required by a ReLU neural network to approximate "almost all" functions up to epsilon where the distance of approximation is defined using the Lp-norm. The paper improves the previously known bounds which lied in the range of d+1 and d+4 to exactly d+1. One of the results of this paper is to establish that this bound is exactly d+1 (I am summarizing the result while ignoring some precision/nuances). This result holds only when the distance is measured using the p-norm where p is finite. In the infinity norm setting, they show that this minimum width actually is indeed not a universal approximator. However, to ensure that the claimed minimum width also holds in the infinity-norm setting, they modify the activation functions to also allow for the threshold functions which is 1 if larger than 0 and 0 otherwise.


This is primarily a mathematical paper and the goal is to understand the minimum width required when arbitrary depth is allowed and thus, the results in this paper should be viewed as an interesting way to completely fill the full-understanding in the mathematics of deep neural nets. In general, the insights are unlikely to have any bearing on practice. With that disclaimer, here are my opinions of the paper. The paper provides a very interesting set of results. First, it fully solves the problem and gives exact bounds, where prior works have only given bounds that without getting the precise constants. Although one could argue that improving constants is not as significant, it still is important/interesting to learn that we can indeed find the precise constant (and arguably using a very nice proof/construction). Second, this paper also shows the dichotomy between approximation measured using Lp and L-infinity. In particular, there is no smooth transition between the minimum width required using only RELU activations between finite p and p-> infinity. However, it is also interesting that the fix to obtain the same minimum width is to allow for another additional activation function (and like RELU it is only non-differentiable at 0, Although, unlike RELU it is not continuous at 0 either). Overall the three set of results form an interesting and complete picture of the landscape for the required minimum width. The proof techniques involve viewing the mapping from input to output as a set of encoder, memorizer and decoder steps and implementing each of those using neural nets with RELU and optimal width. Combining the maximum of these widths gives the final required bound. I really like that the proof and construction is clean and simple to understand. Usually getting precise constants involves messy constructions; that is not the case in this paper and that is by far the biggest strength of this paper.

I had a few suggestions on this paper, that I feel could make the results in this paper even better. 

- Even though the goal is to allow arbitrary depth, it is still instructive to add a discussion on the depth required in these bounds. In particular, what is the "cost" of having the width as small as the minimum required one, in terms of how deep the network should be, given a fixed error epsilon (or in terms of K, M if that is convenient)? 


- In the result for p -> infinity, is the number of step activations required optimal? It is clear that you would need some step functions, but how many? Currently you seem to require one for every input coordinate. Is this optimal? A discussion of this and its optimality will make the theorem/result more stronger. 

- It was not directly/quickly obvious to me how Lemma 8 + applying the q_K one for each input coordinate leads to a width of d+1 as opposed to 2d. The answer is that this is because you are mapping identity for all coordinates except one of them and repeating it d_x times. So stating this out, will make it quickly accessible to the reader. Even though this may seem "obvious", it improves the readability. 

- There seems to be a caveat that the neural net uses the target function itself in the construction of its weights. Although this proof is about "information" needed, a discussion surrounding this and/or explaining why this is okay will again make the spirit of the results clear to the reader.


review_title: Clean proofs, optimal bounds

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper studies the problem of universal approximation with networks of bounded width and arbitrary depth. The objective is to understand what's the minimum width necessary to approximate any function in a suitable space. The main results of the paper can be summarized as follows:

(1) ReLU networks approximate functions in $L^p(\mathbb R^{d_x}, \mathbb R^{d_y})$ if and only if the width is at least $\max(d_x+1, d_y)$. This result is tight and improves upon (Kidger and Lyons, 2020), which give an upper bound of $d_x+d_y+1$.

(2) The same result does *not* hold if we look at the approximation in $C(K, \mathbb R^{d_y})$, $K$ being a compact. The author(s) prove that the minimum width is 3 by giving a counterexample. 

(3) In order to maintain the width of $\max(d_x+1, d_y)$ in $C(K, \mathbb R^{d_y})$, it suffices to use ReLU and threshold activations. 

(4) An upper bound on the width of $\max(d_x+2, d_y+1)$ for approximation in $L^p(K, \mathbb R^{d_y})$ is given for a wide class of activation functions. 


The proofs contain two main elements of novelty: 

(a) The upper bounds (results (1)-(3)-(4) above) rely on what the author(s) call a 'coding scheme'. The input is mapped to a one-dimensional codeword by an encoder; the codeword is mapped to a one-dimensional target by a memorizer; and the target is mapped to vector close to the output by the decoder. The idea is that all these three maps (encoder, memorizer and decoder) can be constructed with neural networks of width $\max(d_x+1, d_y)$ by using ideas of prior results, e.g., (Hanin and Sellke, 2017). The point of the coding scheme is to decouple the input and the output dimension: the original mapping from a space of dimension $d_x$ to a space of dimension $d_y$ is broken into (i) a mapping from dimension $d_x$ to dimension 1, (ii) a mapping from dimension 1 to dimension 1, and (iii) a mapping from dimension 1 to dimension $d_y$. This is what allows to improve the bound on the width from  $d_x+d_y+1$ to $\max(d_x+1, d_y)$.

(b) The counterexample on which the lower bound is based (result (2) above) comes from a topological argument. 

The paper is well written, the results are interesting and strong, the proof techniques are novel. Thus, I am generally positive about the submission.

I have a few questions/remarks:

(Q1) This is a general question. The author(s) provide a general upper bound on the width of $\max(d_x+2, d_y+1)$. Is that tight for a sub-class of activations? Any comment on how to improve it beyond ReLU?

(Q2) Lemma 5. Does the set $\mathcal S$ (or, equivalently, the choice of $a_1$, $a_2$, $b_1$, $b_2$) depend on $\phi$? It looks like this is the case, and it would be better to clarify this point.

(Q3) Section 5.2. It is mentioned that "by the definition of $\ell^*$ and Lemma 5, there exists a line intersecting with $\mathcal B$". How do you guarantee the intersection with $\mathcal B$? The set $\mathcal S$ in Lemma 5 is generic (and, in principle, may not give rise to an intersection). 

(Q4) In Lemma 6, the author(s) talk about a bounded path-connected component without defining what path-connected means.  

I spotted a couple of typos:

(T1) Page 6. "memorizer_{K, M}" should be "memorize_{K, M}".

(T2) "differentiable at at least". This occurs several times in the main text and the appendix as well.
review_title: Tight bounds on minimum width needed by ReLU networks for approximation

Meta-review: Two knowledgeable reviewers and one fairly confident reviewer were positive (7) about this submission. The authors' response clarified a few questions and comments from the initial reviews. The paper provides exact bounds that close the gap between lower and upper bounds, and that helps us understand these networks better. With the unanimously positive feedback, I am recommending the paper to be accepted. 
Decision: Accept (Spotlight)