Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper focuses on neural networks with ReLU activations. For these networks, the paper proposes bounds on the number of neurons needed to represent continuous piecewise linear functions (CPWL). These bounds are derived in terms of the number of linear pieces and the number of distinct linear components of the CPWL. In contrast to prior work, which proposed exponential bounds, the paper shows that quadratic bounds in the number of pieces are enough.
strengths_and_weaknesses: ### Strengths
* The paper significantly improves previous bounds, which enables much more accurate estimates of the number of neurons needed.

### Weaknesses
* It is unclear whether Algorithm 1 can be used in practice. Also, the run time and the computational complexity of the algorithm are unclear.
**Clarity**
* Definition 4: ReLU network should be called ReLU-Multi Layer Perceptron. A general ReLU network is a network with only ReLU activations. A ResNet can also be a ReLU network. Hence, in the Broader impact chapter, it’s confusing that the text says “We focus on ReLU networks in this paper, but it is possible to derive bounds with similar asymptotic growth rates for other neural network architectures such as … residual networks …, densely connected networks …

questions: **For the rebuttal**
* Can Algorithm 1 be used in practice? What is the computational complexity of the algorithm?

**Questions**
* L11: Why is the invariance wrt the input dimension more important than the quadratic bounds?
* L100: “q is always not less than k” -> $k \leq q$

limitations: Theoretical work, no direct negative societal impact.
review_title: null

final_score: 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.
review_content: summary: In this paper the authors provide bounds for approximating a continuous piecewise linear function by a ReLU function. 

When compared to previous work, the bounds provided by the authors are tighter. Furthermore, the bounds provided by the authors only depend upon the total number of linear components in the CPWL (unlike previous work). This helps when the growth in the number of dimensions is faster than the number of linear components. The authors are able to do this because they make use of a different representation of a CPWL function (as mentioned in equation 13). 

The authors also provide an algorithm for finding a ReLU network that computes the given a CPWL. However, this algorithm requires one to know how many linear components are present in the function beforehand, and uses the fact that the final function is a combination of smaller ReLU function approximating the linear components.
strengths_and_weaknesses: The paper is very well written and motivated and provides a rigorous proof for improving of bounds for approximating CPWL functions with neural network. The authors have done an amazing job at motivating and explaining their results as well as placing their work with the related work (which is very well explained). I really enjoyed reading the paper. 

A possible drawback is that Algorithm 1 assumes that the number of linear components in the function is known beforehand. Is there a way that this assumption could be relaxed in a way? 
questions: I think giving a sketch of what Algorithms 2, 3 and 4 do in the main text—even if it is just a sketch will improve the readability of the paper. 
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Summary. The authors study the representation of continuous piecewise linear (CPWL) functions using neural networks with ReLU activations. They showed that, for Any CPWL function with q pieces or k linear components, it can be represented by a ReLU network
with certain layers l, maximum width w, and the number of hidden neurons h. The bounds in this paper are much better than in previous papers. The algorithm for constructing such networks is also given.
strengths_and_weaknesses: Originality: The related works are adequately cited. The novelty of this paper is high. The results on the sharp bound of number of hidden neurons needed to representing CPWL functions in this paper, will certainly help us have a better understating of representation power of 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 machine learning immunity. 

Quality: This paper is technically sound.

Clarity: This paper is clearly written and well organized. I find it easy to follow.

Significance: I think the results in this paper is significant, as explained above.  
questions: It would be interesting to extend the results to more general network architectures.
limitations: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: Three reviewers agree that this work meets the bar for acceptance, rating it weak accept, weak accept, and accept. The work provides bounds for approximating continuous piecewise linear functions by ReLU networks and an algorithm. Reviewers praised the novelty and significance, and were positive about clarifications offered during the discussion period, particularly about the time complexity of the algorithm. Hence I am recommending accept. I encourage the authors to still work on the items of the discussion and the promised additions such as the open source implementation of their algorithm for the final version of the manuscript. 
confidence: Certain
Decision: Accept