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 authors propose a novel neural network architecture that adds a new "height" dimension through a recursive construction. The authors show that their proposed network has better asymptotic error than standard ReLU networks when accounting for similar $O(n)$ number of parameters, and on a class on Lipschitz continuous function in $[0,1]^d$. 
strengths_and_weaknesses: Originality:\
(+) To the best of my knowledge this recursive "height" network architecture is novel. 

Quality: \
I looked at the proof but am unfamiliar field.

Clarity:\
(+) The paper is well written and easy to understand, even for someone not up to date on theory of NN.

Significance: \
(+) To my limited understanding the approximation error that these proposed networks achieve is meaningfully better than standard NNs.
questions: To be clear I come from an applied ML perspective, which colors my questions. My main question is understanding the value of this work. Is the value: \
A) Primarily theoretical in understanding a new class of NNs which can achieve better approximation error? \
B) Also applied in that the authors expect their proposed class of NNs to be used on modern ML tasks?

If A), then I think the work is valuable. If B), then I am concerned about the addition of hyper-parameters and the lack of experiments on any real task. 
limitations: The authors describe theoretical limitations in their analysis, which I think are reasonable and am unconcerned about.
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: The paper proposes a new family of neural architectures which is given not just by width and depth but also by 'height', a newly introduced dimension. Such models are allowed to have activations that are themselves realized by other networks, resulting in an implicit parameter sharing scheme. Results on approximation theory are shown for such family of models, where they have better approximation properties than standard 'width/depth' networks.
strengths_and_weaknesses: The paper is quite rigorous and the definitions are precise and formal. There is some minor repetition in the text (abstract / introduction), which could be removed to open up some space.

Two weaknesses in my opinion:

1) There is no discussion / intuition / sketch of the proof of Theorem 2.1 in the main text. The construction given in the Appendix is important as it plays a major role in the theoretical results given in the paper, and a brief description of it would be valuable to have in the main text (and I believe enough space could be opened up by removing repeated text, wrapping Fig 3, etc). The organization of the Appendix could also be improved, since a reader looking for details on the construction used to prove Theorem 2.1 would go to Appendix A, then to B.1 and it is only in B.2 that the construction is given. This is a minor weakness as it is mostly regarding the organization of the manuscript, and had no impact on my final rating.

2) The discussion on how NestNets relate to models that have been previously proposed and adopted could be greatly expanded and improved. As the paper states, NestNets can be seen as 'standard' networks but with a specific parameter sharing scheme (this point could be given more significance in the text, as parameter sharing seems to be the main ingredient of NestNets and the cause of their expressive power). The scheme is given by activation layers consisting of element-wise operations on the input, and a repetition of these activation layers throughout the network.

As for the first property (element-wise maps), there is a connection to convolutions which doesn't seem to be mentioned: a stack of 1d convolutions with a kernel size of 1 also results in a module that maps an input x = (x1, x2, ..., xk) to u = (f(x1,w), f(x2,w), ..., f(xk,w)) where f will be a deep network that maps R -> R. For image data, we have a similar relationship with stacks of 2d convolutions with 1x1 kernels and with stacks of depthwise separable 2d convolutions. Note that stacks of 1x1 or depthwise convolutions are used in some CNN models and, to some extent, also in transformers (the ReLU MLP blocks following attention layers can be framed as convolutions). To summarize, this type of parameter sharing has been widely explored in the literature and a more rigorous and complete discussion on it is required.

For the second property (layer repetition throughout the network), there is also a missing connection to models that re-use parameters across different layers of the network, most notably models that can be seen as hybrids between recurrent and non-recurrent networks. Some methods aim to train the recurrence scheme itself, learning how and when to re-use layer-wise parameters across a deep network. Some examples that should be discussed are:

[1] - Learning Implicitly Recurrent CNNs through Parameter Sharing
[2] - ACDC: Weight Sharing in Atom-Coefficient Decomposed Convolution
[3] - Neural Parameter Allocation Search

Lastly, a discussion with Maxout would be valuable, as it can be seen as a learnable activation function but considerably more expressive than the mentioned ReLU variants.
questions: Suggestions are listed in the previous section (Strengths And Weaknesses).

My main question is regarding the practical aspects of NestNets. The construction used to prove Theorem 2.1 seems to have an effective depth of approximately $3 n^{s+1}$, where by 'effective depth' I mean the diameter of the unrolled computational graph of the network. For n=10 and s=5, this results in a model that requires 3 million sequential operations to compute its forward pass (i.e. evaluate the model on a batch of samples), which is on a completely different scale than the depth of 'standard' networks used in practice and simply impractical. Is it the case that the approximation power of NestNets indeed rely on networks with an effective depth that outscales the number of parameters (as n and s increase) and even a single forward pass becomes unfeasible, or is the construction used for Theorem 2.1 extremely inefficient in terms of effective depth? I understand if a conclusive answer is not possible at this time but some I'd like to know the authors' thoughts on this.
limitations: A discussion on the practical limitations would be valuable (see 'Questions' comments regarding effective depth and evaluation cost).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper presents a novel three-dimensional NN architecture. An additional dimension called height is introduced to empower the capacity of neural networks. A simple 257 experiment demonstrates the numerical advantages of the proposed method. The proof seems to be solid. However, I am not an expert in theory so I cannot judge the contribution of the proof. Overall, I think the idea of the paper is novel.
strengths_and_weaknesses: Strengths
- The three-dimensional NN architecture is a novel concept. The authors present theoretical proof to show their advantage with ReLu activations. The proof seems to be solid.

Weaknesses
- Although the method does not add extra parameters, the proposed three-dimensional NN significantly introduces an extra computational burden to iteratively activate the neurons (e.g., FLOPs during inference). It is good to present the computational burden of training and inference, and compare the performance against the computational burden.
- The results of commonly-used benchmarks are preferred such as mnist, cifar, and ImageNet.


questions: See Weakness
limitations: There is no computational cost analysis and comparison, or experiments on real-world datasets.
review_title: null

Meta-review: metareview: The authors propose a new architecture which has superior approximation rates for a given number of parameters; this is a very interesting notion that is shown on a simple example to be quite effective.  The reviewers are supportive of the paper with their main concerns being the added computational cost and the lack of any examples on real world data sets, even small ones such as MNIST.  The authors should include a small experimental section showing the text accuracy for MNIST or similar, along with the computational time for both training and applying the network.
confidence: Certain
Decision: Accept