Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the depth requirements for exactly representing the maximum of $n$ inputs using networks with integer weights. They show that $\lceil \log_2 n \rceil$ depth is necessary. Note that the simple binary tree construction that computes maximum of two inputs at a time achieves this depth. For this class of integer weight NNs this shows a depth separation result for all depths less than $\lceil \log_2 n \rceil$. The lower bound sheds light on the importance of using max pooling layers to remove depth dependence.
strength_and_weaknesses: **Strengths**: 
- The paper takes a good step towards understanding the depth separation of exact function computation for ReLU networks. Unlike approximation results where one non-linear layer suffices for approximating functions, the question of exact representation is not so straightforward. Though the paper does not solve the question in its generality, understanding even the integer weight constraint is useful, and hopefully helpful for the general setting.
- Showing separation for max of linear functions is insightful since it suggests that adding max-pooling layers (which are popular in practice) might be a computationally useful operation.

**Weaknesses**: 
- Despite being mathematically interesting, exact representability is not the most interesting from the point of learning in-distribution. Approximate approximation suffices for that.
- There is no mention of width of the network. As has been seen in Telgarsky 2015, width and depth do have their interesting trade-offs.
- The overall writing of the paper is not very friendly to readers without a tropical geometry background.
clarity,_quality,_novelty_and_reproducibility: The paper is mostly clear, writing can be improved though (see below). The results are novel, and the proofs seem correct.

Suggestions for improving writing:
- All figures: Add descriptions in the caption to explain the figures, they are not easy for a reader without background to understand
- Better notation for $\tilde{L}$ parallel to $L$ (just above section 2.3)
- Proof of Theorem 3 uses Proposition 17 before it is even defined. Please reorganize to ensure a linear flow. Also add more explanations of the proof, and high level ideas.

Questions:
- How does the integer weight assumption compare to the condition used in Hertrich et al. 2021? Are they comparable?
- Have you explored the width and depth tradeoff for these results?
summary_of_the_review: Overall, I found the problem studied in the paper and the results mathematically interesting. I think they are a nice addition to the rich literature of representation results known for neural networks despite the limitation of exact representability. Therefore, I vote to accept the paper. I encourage the authors to improve the writing.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In (Arora et al. 2018), it was shown that $\lceil \log(n+1) \rceil$-depth was sufficient for representing $n-dim$ CPWL functions. Is this necessary? Authors say yes, under the assumptions that weights are integral. That is, there exists functions that cannot be represented by depth less than $\log(n+1)$, under the conditions that the weights are integral. To show this they exploit the fact that the weights are integral and the hard function is $\text{max}[0,x_1,x_2,\ldots,x_n]$, where $n=2^k$ and this is not expressible by a ReLU with integral weights and depth $k \leq \log(n)$.
strength_and_weaknesses: Strengths:

 It is an open problem to characterize the necessity of $\lceil \log(n+1) \rceil$-depth for dimensions $n \geq 4$ and also to get depth separations in high-dimensions, that are not constant depth, such as depth 3 vs depth 2 as shown in many works such as (Eldan and Shamir 2016, Daniely 2017, Safran et al.2019). This work tries to address this problem and gives a partial resolution and increased evidence for this. It does this by providing connections to the high-dimensional convex geometry of lattices. 

Weakness:
The main weakness is that of the integrality assumption. Now as the author points out that this is impractical in training and that perhaps new techniques are needed to deal with real-valued weights. The main issue is that the separation is argued by saying that a ReLU network of a depth smaller than this threshold does not exactly represent the hard function that is provided. However, results such as (Telgarsky, 2016) focus on L1-inapproximability by networks whose depths are $o(threshold-depth)$ and that have polynomial width. Could the authors clarify if allowed for real-valued weights, if they could still get separation on depths that are say $o(\log(n+1))$ and show a stronger inapproximability result, rather than the exact representation of the function? Could the authors comment if ReLU(k), where $k=\log(n)$ and allowed for real-valued weights can still provide an arbitrarily good approximation of the hard function?
clarity,_quality,_novelty_and_reproducibility: The writing is clear and the problem is important but some of the techniques may be tied to the specific assumption of integral ReLU networks.
summary_of_the_review: Overall, I think it is a good attempt at a big open question w.r.t the depth separation results, but I feel there are some questions as mentioned above, that requires some explanation and probably a bit more work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper aims to provide a non-constant lower bound on the depth of ReLU neural networks without any restriction on the width. Mostly, the authors prove that the conjecture by Hertrich et al. (2021) is true for all n ∈ N with an additional assumption on the weighs of the network to be integer numbers.
strength_and_weaknesses: This general topic is appropriate for the machine learning community and the manuscript’s proofs are well-written. I found the general concept of finding a logarithmic lower bound for the ReLU networks interesting and of value, since finding a lower bound for this seems to be the first and the ReLU networks are the most frequently used activation function in the world right now. While I did find this work interesting, there are several concerns to be addressed before further consideration.

1-	Regarding Theorem 3’s proof, I could not find any precise justification for the used reasoning. It will be better to propose a more systematic procedure for the proof of this theorem and give a more detailed explanation of how “The arguments in Hertrich et al. (2021) can be adapted to show that the equivalence between the two conjectures is also valid in the integer case”

2-	“Translating this result back to the world of CPWL functions computed by neural networks, we obtain that k hidden layers are not sufficent” clause used in the manuscript needs more discussion about how they assumed it. Also, it has a typo. (Sufficient)

3-	The “FURTHER RELATED WORK” section is just naming some papers without a brief description. It would be better if for some cases the author gives a brief description in manuscript.

4-	It would be better if the author adds the proof of Theorem 8 to the appendix, since the paper should be self completed.

5-	The theorem 12 proof is better to be more accurate and complete.

clarity,_quality,_novelty_and_reproducibility: The manuscript’s proofs are well-written and complete. The authors described most of the manuscript with a good quality and clarity. Furthermore, I found the general concept of finding a logarithmic lower bound for the ReLU networks interesting and of value.
summary_of_the_review: Although I found the general concept of finding a logarithmic lower bound for the ReLU networks interesting and of value, there are several concerns needs to be addressed before publication.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper "Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes" derives a theoretical result and proves that log_2(n) hidden layers are necessary to compute the maximum of n input numbers. This is achieved by building on previous theoretical work that links neural networks to tropical geometry, and uses this connection to link neural networks with integer weights to lattice polytopes. Employing subdivisions of these polytopes, Minkowski sums and convex hulls, allows to construct all polytopes corresponding to a neural network of a given depth. Further, by looking at the normalized volume, it shown that not all lattice polytopes can be constructed that way, which implies a lower-bound on the depth of neural network (log_2(n)) to calculate the maximum of n numbers - matching the previously known upper bound.
strength_and_weaknesses: Strengths.
- the paper gives a thorough and long introduction into the preliminaries (until mid of p.7); this is great to give a more self-contained presentation of the topic.
- the paper proposes a novel theoretical insight into neural networks
- limitations of the study are clearly stated

Weaknesses - only minor things:
- as the authors state clearly in the paper the analysis is limited to the case of integer-valued neural networks. It is unclear how to extend the analysis to the general case, but the methods provided might be instructive towards this target.
- p.4. in conv(X): it should probably read 'lambda_i \geq 0 \forall i'?
- the structure of the paper doesn't conform to typical ICLR papers, in particular, a Conclusion section is missing.
clarity,_quality,_novelty_and_reproducibility: - The paper is clearly written, though not completely self-contained (not possible given the topic though)
- The paper is of very high quality and novel to my knowledge
summary_of_the_review: The paper provides a novel theoretical insight into neural networks, and a proof construction that is well laid out.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This is a theory paper on the expressivity of neural networks using lattice polytope perspective. The authors prove that log2(n) hidden layers are necessary to compute the maximum of n input numbers. 

The paper is well-written and manages to do a great job in introducing the preliminaries while being self-contained. 

The integrality assumption is the main weakness of the work. 
justification_for_why_not_higher_score: The assumptions can be quite restrictive (i.e., the integrality) though they provide insights. 
justification_for_why_not_lower_score: The work is a solid theoretical attempt on understanding the expressivity of NNs.
Decision: Accept: poster