Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides some interesting and tighter spare approximation bounds for two-layer ReLU neural networks. The authors generalize the results for $\mathbb{R}^d$ to a bounded open set $\mathcal{U}\subset\mathbb{R}^d$ by defining the Radon-based $\mathcal{R},\mathcal{U}$-norms of functions. They also show that the representation of infinite width neural networks on $\mathcal{U}$ are not unique.
main_review: The presented tighter sparse approximation bounds for two-layer ReLU neural networks are of interest. Theorem 1 tells that there exists a neural network representation for a function defined on a bounded open set $\mathcal{U}$ if its $\mathcal{R}$, $\mathcal{U}$-norm is finite, which generalizes the results for functions on $\mathbb{R}^d$ in the literature and yields the sparse approximation bound in Theorem 2. Moreover, the authors discuss its tightness and links with Fourier sparse approximation bounds in Theorems 3 and 4. The non-uniqueness of neural network representations is studied in Theorem 5. I have one concern that how to check the finiteness of the $\mathcal{R}$, $\mathcal{U}$-norm for general functions?


Other minor comments/typos:
- rows above (1) and (2). Should $n$ be used instead of $m$?
-Proposition 2, $n$ or $m$ in the approximation bound?

summary_of_the_review: The paper is well organized and technically sound. The results should be interesting to the community of theoretical deep learning.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the approximation bounds for the 2-layer  ReLU network.  The authors extend the analysis framework of Ongie et al. (2019) and show the approximation bounds for the infinite-width network on a bounded open set as well as the bounds for sparse (i.e., finite-width) network that refine the similar results in the literature. At last, the authors show that the infinite-width neural network representations may not be unique on bounded open sets and provide a functional view of the mode connectivity. In particular, the authors refine the R-norm introduced by Ongie et al. (2019) to R, U-norm to tickle the bounded open set case.

 
main_review: Strength:

This paper uses the novel analysis tool based on Ongie et al. (2019) to consider the bounded open set case. It is technically solid. I check the detailed proof and don't find the major flaws. (I need to admit I am not very familiar with the Fourier-based approximation bounds, so it is possible my judgment on novelty is wrong. And this is why I rate my confidence as 2.)

Weakness:

Clarify: It is still room to improve the technical part of the paper. 5 theorems and 4 propositions are shown in the 9-page main paper and more discussions on the Theorems/Proposition may be needed to make the paper easier to follow. I also suggest the authors add some discussions to further highlight the technical difference/significance of the Theorem/Proposition. 

summary_of_the_review: This paper uses the novel analysis tool to study the approximation bounds for 2-layers ReLU networks and is technically solid. However, the presentation of the paper is a little bit hard to follow and I've spent about 15 hours checking technical details of the main paper and supplyments...
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The main result of this paper is a representation theorem for functions on a bounded set U by two-layer neural networks with bounded width and bounded weights, via a semi-norm ||_{R,U} based on the Radon transform. Prior work [OWSS19] used the Radon transform to get a representation theorem for functions on R^d, but the bounded-domain setting is more realistic and allows for stronger results, since the semi-norm ||_{R,R^d} will naturally be larger than ||_{R,U}. Moreover, this paper shows that when U is a Euclidean ball, the semi-norm ||_{R,U} can be upper bounded in terms of the Barron norm, so this paper's representation theorem strengthens Barron's Theorem.
main_review: I recommend acceptance.

STRENGTHS: The Radon semi-norm is a potentially useful way of understanding representation, and as the paper shows, there are examples where it can provide a much better bound than the Barron norm.

WEAKNESSES: None that I am aware of.

QUESTIONS:
- Are there examples where ||_{R,U} is substantially smaller than ||_R (e.g. is this true for Example 1)? Should we expect it to be much smaller for many reasonable functions? More discussion on when/why this bound is better than the prior bounds would be helpful.
summary_of_the_review: This paper extends prior work on infinite-width NN approximability for bounded Radon semi-norm to finite-width NN approximability on bounded sets, which is a more reasonable setting and strengthens the classical Barron norm bounds.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the class of functions that coincide with an infinite width two-layer neural network on a fixed bounded open set. First, they introduce a Radon-based R, U-norms for functions defined on a bounded open set U. Then they prove tighter sparse approximation bounds for two-layer ReLU neural networks. They also prove that the representation of infinite width neural networks on bounded open sets are not unique. 
main_review: The novelty of this paper is high. By the introduction of R, U-norms the authors show that their approximation bound is tighter than bounds in the previous papers, and meaningful in more instances such as finite-width neural networks. This result will certainly help us have a better understating of deep neural networks from a theoretical way. I have checked the technique parts and find that the proofs are solid. I think this is a significant contribution to the deep learning community. The theoretical results in this paper are about two-layer ReLU neural networks. It will be interesting to see extended results on more widely used architectures in the future. Overall,  I think the results in this paper are important, as explained above.
summary_of_the_review: By the introduction of R, U-norms the authors show that their approximation bound is tighter than bounds in the previous papers, and meaningful in more instances such as finite-width neural networks. The novelty of this paper is high. Overall,  I think the results in this paper are significant.
review_title: null

Meta-review: The authors extend the result of Ongie et al. (2019)  and derive sparseneural network approximation bounds that refine previous results. The reuslts are quite ineteresting and relevant to ICLR. All the reviewers were positive about this paper.
Decision: Accept (Spotlight)