Venue: NeurIPS 2022 Conference

Reviews:

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 describes a theoretical model based on recurrent and convolutional neural modules that achieves what the authors call "Turing-optimality". 
More specifically, the authors argue that a randomly initialized recurrent and convolutional NN that they introduce, trained with SGD with random restarts is probably algorithmically optimal for the class of algorithms given by constant-sized time-bounded Turing machines.`
strengths_and_weaknesses: Unfortunately, I am very unfamiliar with the literature and problems of this area and can only evaluate this paper in a very shallow manner. 
I found the paper quite unclear and rather hard to follow. It seems to jump to conclusions before building preliminary concepts and sufficient intuition.
Some passages are rather unclear and seem to be contradictory: eg :
*The contribution of this work is showing that a definition
of Turing-optimality is achievable by a simple NN architecture. In future work, it would be interesting
to better understand which architectures, initializations, and learning rates are Turing-optimal.*
I am left to wonder whether one contribution of this paper is indeed that mentioned in the first reported sentence or not.
There are missing links to equations (references to equations point at sections, probably) and a rather free usage of Claims and Observations which make it hard to understand what are the assumptions that the authors do at any point of the paper.

My overall impression is that this papers lack (at the very least) in clarity and coherency, yet because of my lack of expertise in this field, I will only rate it as a weak reject.

questions: See above
limitations: Discussed
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: This paper introduces the notion of Probably Algorithmically Optimal (PAO) learning as a weaker notion than PAC learning, and the concept of a (meta?) learning algorithm being Turing-optimal if it can discover learning algorithms producing classifiers that perform as well as any classifier that can be obtained by another learning algorithm. They illustrate that a particular architecture complies with such a notion.
strengths_and_weaknesses: The paper is reasonably well written and the authors clearly position their proposed notions with respect to other theoretical models on learning algorithms. Given that this is not my area of expertise, at some point the idea that their model is supposed to produce a learning algorithm rather than a classifier gets more difficult to follow. However, my main concern - which may or may not be valid - is whether the RCNN that they study has any practical insight, given that its architecture is not something I would have expected in practice. Perhaps related to that, it is not entirely clear to me if these new notions (PAO and Turing-optimal) are practical or particularly relevant for further studies.

Minor comments on writing:
- Line 41: "innovation" -> contribution?
- Line 52: "to use a use a": remove "a use"
- Line 180: "the a number of examples": remove "a"
- Line 251: "1can" -> "1 can" (add space)
- Line 254: Please repeat that m is the sample size and d is the input size
- Line 272: It is not immediate what the three hyperparameters at the end of the sentence mean; like above, it would be very helpful to repeat that information next to each hyperparameter
questions: 1) Section 1, line 36: Do we really know that "two-layer NNs can compute any Boolean function on d binary inputs? I understand that the following references [1-2] are not restricted to Boolean domains, but I would appreciate an explanation for this statement.

[1] https://arxiv.org/abs/1611.01491

[2] https://proceedings.neurips.cc/paper/2021/hash/1b9812b99fe2672af746cefda86be5f9-Abstract.html

2) Is it reasonable to expect |A| << |C| as mentioned in line 61? Wouldn't it be more likely that the opposite is true, given that each algorithm in A is distinguished from other algorithms by producing a mapping of datasets to classifiers in C?

3) Can you provide an example for the claim in lines 129-130 that "a classifier may be very slow to evaluate, even if the learning algorithm is fast"? Likewise, under what circumstance would the case in lines 133-134 that "time spent on classification is folded into training time" be useful in practice?

4) Isn't it atypical to assume a fully connected layer before a sequence of convolutional layers? Why is this construction needed, and what practical relevance would it have to design architectures in such a way?

5) Likewise, isn't it limiting to assume recurrent weight sharing?

6) My understanding from the first sections is that the strict parameter sharing in the convolutional layers was meant to make the learning algorithm independent of input size, but the initial dense layer breaks that. What am I missing here?

7) Is the output of Algorithm 1 a classifier, a learning algorithm aimed at learning a classifier for a specific dataset, or a generic learning algorithm? 
limitations: The authors are upfront about the practical limitation of their algorithm for realistic cases due to the large constants even if the algorithms are polytime.
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: This paper analyzes recurrent neural networks' ability to learn algorithms. The authors show that the proposed architecture is Turing complete. They also show that the recurrent convolutional models discussed can learn parity functions in polynomial time.
strengths_and_weaknesses: Strengths
- To the best of my knowledge this is an original treatment of recurrent convolutional networks. This touches on an increasingly important field of algorithm learning and reasoning in neural networks.
- The writing is clear.
- The results in this paper are likely interesting to the community. Specifically, much of the recent work on algorithm learning is empirical, and theoretical treatment accompanies this well.
- Additionally, the theoretical grounding for choosing recurrence/weight sharing of this type might motivate the applications-forward researchers as well.

Weaknesses
- As is mentioned by the authors, the bounds/constants are not practical. 
- Given the body of work (cited by the authors) on algorithm learning, it would be nice if there was a little more context as to the scope of the results in this paper. (See the questions below.)
questions: 1. In the empirical work in this space, there are many popular, well-known, algorithms considered. What baring does the theory presented in this paper have on recurrent neural networks' ability to learn in settings outside parity? 
2. In Section 5, the authors state that the constants in the theorems are "too large to be meaningful in practice." I appreciate that this is mentioned and I wonder what, if anything, can be done or where we might look to shrink those constants. Is this a theoretical limitation or an observation about the analysis in this particular paper?
limitations: The limitations are adequately addressed.
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: This paper proposes a notion of turing-optimal learning, which means that a learning algorithm can learn as well as any Turing Machine with s states, m examples, and that terminates in t steps. A neural network with convolution and recurrent layers are designed. This network has only constant number of distinct parameters, but the depth and width grow polynomially in data dimension d, sample size m, and number of turing states s. Using repeated random restart and gradient descent, an algorithm that learns with this architecture is shown to be turing-optimal.
strengths_and_weaknesses: Strengths:
1. The notion of Turing-Optimal Learning is original, intuitive, and interesting.
2. The theoretical part is rigorous and requires significant effort.
3. The exposition is clear, and the proof sketch is informative.

Weaknesses:
The construction is far from practical (and the authors admitted as much). SGD plays nominal part in the picture; the network basically memorizes all training examples, and then uses $s^s$ random guesses for the correct algorithmic parameters (via random restart). Overall constructions like this do not meaningfully inform ML practitioners, as it's unlikely to memorize all training examples and do random guessing in practice, and it's also undesirable that the network size grows with sample size, and undetermined when s isn't known for realistic datasets.
questions: 1. Line 97, did you mean [Wei et al.] doesn't take computational efficiency into account?
2. Can you elaborate how random restarts are different from enumerative program search?
3. Typo in line 272?
limitations: Yes.
review_title: null

Meta-review: metareview: In discussion of this paper, we agree that this paper presents a very novel treatment of learning algorithms and presents a new topic with an original formalization of the problem, which will be of substantial interest to the NeurIPS community.
The reviewers agreed that a formal understanding of RNN is of interest, it is not clear how close is the given framework to reality, and how much insight can be gained: The bounds are huge for practical datasets, and the use if SGD is minimal.
Overall, the significant novelty for the formulation of the question itself warrants acceptance.
confidence: Certain
Decision: Accept