- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies an important question in expressivity: whether there is a depth separation in the expressivity of finite-width ReLU networks. It provides a upper bound for the number of hidden layers required to express a -dimensional CPWL function, significantly improving upon the previous upper bound, although a lower bound better than 2 remains unaddressed.
Critical strengths
The studied problem is long-open and this work presents a solid progress on the upper bound. No major proof mistake is identified during review. The approach is well-described and readable, the idea of using symmetry to reduce candidates is elegant, and the proof cleverly combines computer-aided solving in small dimensions with theoretical argument to scale to large dimensions.
Critical weaknesses
The main weakness is a still open lower bound, which does not present a reason for rejection, since it is commonly believed to be substantially harder. The existing result already gounds its importance.
Questions for authors
It seems there is no specific reason to stop at and perhaps the restricted candidate family excludes too many possible solutions. Is there any potential future direction that authors may believe to be helpful, in particular to resolve the conjecture proposed in this work?
2 comments
Dear authors,
Thanks for the reply. I have also seen the new work on establishing lack of depth separation. I am happy to have rated this positively to support this work.
We thank the reviewer for the positive review.
There is no mathematical reason to stop at n=12. As the size of the linear system of equations undergoes a combinatorial explosion, for n≥13 we weren't able to find a solution due to computational limits. Using more time and more computational resources, together with some algorithmic improvements, it might be feasible to push this limit a bit, but we would only expect very small incremental increases. You are right that the candidate family may exclude valid representations. We need a candidate family that is expressive enough while keeping the search computationally feasible.
We point out that our conjecture has been resolved for all n after the submission by Brunck, Hertrich, Rueß, Stade and Yehudayoff in arXiv:2610.28587. Their combinatorial proof builds on several ideas from this paper and we believe our intermediate result provided a useful step towards resolving the conjecture for all n. In particular, our paper established that the earlier discovery of a two-hidden-layer construction for max5 by Bakaev et al. was not a low-dimensional exception.