Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms
Authors: Surbhi Goel
Sham M. Kakade
Adam Tauman Kalai
Cyril Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: recurrent convolutional neural networks
Turing completeness
universality
learning algorithms

Abstract: Neural networks (NNs) struggle to efficiently solve certain problems, such as learning parities, even when there are simple learning algorithms for those problems. Can NNs discover learning algorithms on their own? We exhibit a NN architecture that, in polynomial time, learns as well as any efficient learning algorithm describable by a constant-sized program. For example, on parity problems, the NN learns as well as Gaussian elimination, an efficient algorithm that can be succinctly described. Our architecture combines both recurrent weight sharing between layers and convolutional weight sharing to reduce the number of parameters down to a constant, even though the network itself may have trillions of nodes. While in practice the constants in our analysis are too large to be directly meaningful, our work suggests that the synergy of Recurrent and Convolutional NNs (RCNNs) may be more natural and powerful than either alone, particularly for concisely parameterizing discrete algorithms.

Recurrent Convolutional Neural Networks Learn Succinct Learning Algorithms
Surbhi Goel Microsoft Research & University of Pennsylvania surbhigècis upenn. edu
Sham Kakade
Harvard University sham@seas. hwwvaarddd...................... edu
Adam Tauman Kalai Microsoft Research adam@kal. ai
Cyril Zhang
Microsoft Research syrilzhang@mie www.:ft..coooooooocooooooooo.. com
Abstract
Neural networks (NNs) struggle to efficiently solve certain problems, such as learn- ing parities, even when there are simple learning algorithms for those problems. Can NNs discover learning algorithms on their own? We exhibit NN architec- ture that, in polynomial time, learns as well as any efficient learning algorithm describable by constant-sized program. For example, on parity problems, the NN learns as well as Gaussian elimination, an efficient algorithm that can be succinctly described. Our architecture combines both recurrent weight sharing between layers and convolutional weight sharing to reduce
number of parameters down to constant, even though the network itself may have trillions of nodes. While in practice the constants in our analysis are too large to be directly meaningful, our work suggests that the synergy of Recurrent and Convolutional NNs (RCNNs) may be more natural and powerful than either alone, particularly for concisely parameterizing discrete algorithms.
Introduction
Neural networks (NNs) can seem magical in what they can learn. Yet, humans have designed simple learning algorithms, even for binary classification, which they cannot match. A well-known example is the class of parity functions over the d-dimensional hypercube, i.c., d-bit strings. In that problem. there is an unknown subset of the bits, and the label of each example x if x has an odd number of I's in S. While tradient-based learning struggles to learn parity functions (Kearns and Valiant 1993) even over uniformly random æ, row reduction (i.e. Gaussian elimination) can be used to find S using only (dd) examples and (dd)) runtime.
tantalizing question is whether NN can discover an efficient learning algorithmn itself, thereby learning classes such as parities. We refer to this as Turing-optimality, since algorithms can be described by Turing machines. More specifically, we will give an example of a simple NN architecture that achieves Turinng-ptimmality In particular, this is the first NN architecture that provably discovers a efficient parity learning algorithm in polynomial time. The parity learning algorithm is efficient, like row reduction, requiring O(d) examples and O (dd)) runtime. Our learning architecture would be quite simple to describe with a modern library such as PyTorch. However, we do not expect our specific architecture to be especially good in practice, the constants in analysis are much too large to be practical. Nonetheless, it does suggest that the ingredients used in the architecture, especially the combination of recurrent weight-sharing across layers and convolutional weight-sharing within layers, may be useful in designing practical architectures for NNs to learn algorithms.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

.00%
Succinct learning
Ixport scipy.1inalg
Ioputs
(repeated)
Output
Turing opt
algorithms
uo C Aecunaa
reduction
Import formers
P, L, U. 1a.1u(K)
tokenizer
transformers Bent
All classifiers
Leamable
fran sklearn.
skleam..nsemble ensemble import RandonforestClassiffer
Randonf (rstiiisooest)leeffeeer))
50%
Figure 1: (Left) A simple RCNN, in which one small set of parameters is repeated within each layer and across layers. (Right) A Turing-optine future examples from D, as that which is output by any other succinct efficient learning algorithm. Such classifiers are only tiny subset of the set of all classifiers, some of which may be more accurate but cannot even be stored in a computer. Moreover, even competing with the best poly-sized NN is intractable, assuming the existence of one-way functions (Kearns and Valiant 1994); it is not possible for any learning algorithm efficiently compete with the region depicted in green.
algorithm must output classifier that is as accurate, on
Figure illlustrates the difference between classifiers, such as NNs, and the learning algorithms that learn their parameters, such as Stochastic Gradient Descent (SGD) with a given architecture (we use the term architecture broadly to include other algorithmic features including learning random initialization, learning rate schedule, restarts, and hyperparameter search). As classifiers, two-layer NNs compute any Boolean function on d binary inputs, including parity functions. However, is unclear whether these architectures can learn such functions efficiently using gradient- approaches without any priors encoded in the architectures.
More formally, a ourinal learning algorithm one which learns as well as any bounded learning algorithm, specifically a constant-sized Turing machine that outputs binary classifier in polynomial time, such as row reduction for parity learning. Our key contribution is simple recurrent convolutional (RCNN) architecture which combines recurrent weight-sharing across layers and convolutional weight-sharing within each layer. The number of weights in the convolutional filter can be very few, a constant, but these weights network. We show that any algorithm A represented by a constant-sized TM has a corresponding constant-sized convolutional filter for which the RCNN computes the same function A. Because the convolutional filter is constant-sized, with constant probability random initialization will find (or something even better, assuming reduction is not optimal). Thus, using a validation set and random restarts, the RCNN will find a filter which performs as well as A, with high probability.
determine the activations of very wide and deep
Unfortunately, the above argument would apply to an RCNN architecture that strangely takes the entire training set as input at once, and outputs a classifier. Fortunately, Abbe and Sandon (2020) show how to use a few additional simple NN components and SGD updates to memorize relevant information in the weights of these components. Similarly, we add a few extra non-convolutional layers our architecture that it can be learned "normally" with SGD rather than requiring the entire dataset at once. Fortunately, the implementation of this functionality is compatible with the RCNN with only a constant overhead in terms of size.
Probably Algorithmically Optimal (PAO) learning. To define Turing-optimality, it is convenient formalize weaker requirement than PAC learning which we call PAO learning, that in sense turns PAC learning on its head. Rather than requiring optimality among the space of all classifiers E C, it requires only optimality compared classifiers output by learning algorithms A E A. In many cases CC > [A], as log (C] and log [A] are the number of bits required to encode the parameters (modern models approaching terabytes) and the learning program source code (e.g., kilobytes), respectively (see AArora and Zhang] (22T)) for more detailed discussion). In these cases, matching the performance of the classifier output by the best learning algorithm (within some family) may be more reasonable matching the performance of the best overall classifier. (uring-optimalin is the special case of A consisting of the set of succinet programs, specifically constant-size Turing machines. In Section 5 we also discuss how this approach can be used across multiple problems to discover a learning algorithm that can be reused on future problems, so the search need not be repeated for each learning problem.
bime-bounded

---

Like any asymptotic notion, Turing optimmlitt does not guarantee efficient learning. Just as polynomial-tine time algorithm is not guaranteed be faster than an sxponential-time algorithm on inputs of interest, such notions can still provide a useful lens to understand algorithms. If learning algorithm A₁ is Turing-optimal and A2 is not, then A can nearly match (or exceed) the performance of A2 on any distribution, with polynomial overhead. Data distributions where Ag requires super- polynomially resources to match As's 's performance would need to be examined to see if they are important. We show that Recurrent Convolutional Neural Network (RCNN) architecture, with random initialization, is Turing-optimal The contribution of this work is showing that a definition of Muring-optimmaity is achievable by simple NN architecture. In future work, it would be interesting to better understand which other combinations of architectures, initializations, and learning rates are Turing-optimal.
1.1
Related work
We review some prior lines of work which establish or use other notions of computational universality. We note that most of the notions defined in these works apply to representations rather than algorithms.
Universal function approximation. The first line of work relevant to our results is the basic theory of universal function approximation, which guantifies the ability to fit any sufficiently well-behaved function for neural networks (Hornik et al.) 1989 Cybenko 1989, Funahashi 1989), nearest neighbors (Devroye ct al. insight, e.g., lookup tables are universal over X'
1994) and SVMs with RBF kernel (Wang al. 2004). However, they lack statistical 1, I but offer little statistical power. Further refinements (Barron 1993 1994 Lee et al., 2017 consider Fourier-analytoe criteria for functions to be representable by smaller neural networks. The goal of subsequent lines of work described in this section, well the present work, is to investigate the computationally efficient approximation of functions-in other words, the ability of neural networks to emulate efficient learning algorithms.
of neural architectures. Siegelmann and Sontag (9955) establish that re- current neural networks are Turing-complete, using a trick to store the entire TMM tape in a single rational number, therefore requiring an extreme amount of bit precision. More recently, Graves al. 2014) construct a differentiable TM-inspired architecture. A number of recent works establish Turplgg-omplettensss (a classical and weaker notion) for variants of the Transformer architecture (De hgghan et al. 2018 Yun et al. 2019 Bhhttamishra et al. 2020a b). motivated by empirical advances in discrete reasoning tasks found in natural language processing, theorem proving, and program synthesis. Recently, Wei et al. (2021) propose notion of statistically meaningful (SM) approximation which requires the approximation to be statistically learnable as well. They show that Transformer architectures can "SM-approximate" time bounded TMs with sample complexity logarithmic in the time. Unlike our notion, compleeesss does not take computational efficiency into account.
Enumerative program search. A folklore argument, similar to Levin's 's classic universal search Levin 1973), states that one can achieve Turing-optimall by enumerating all Turing machines of a hxxed size, run them all on a training set, and choose the one which performs best on validation set. The algorithm, however, is also completely infeasible in normal programming languages because the probability of even generating a single program that compiles minuscule.
Efficient universality of deep learning. Most closely related our work is that of Abbe and Sandon (2020), which shows how, given any circuit e.g. encoding a learning algorithm for parity, one can initialize the weights of a NN so that emulates C when the NN is trained by SGD. This emulator requires C to be given as input. Now, row reduction, like any polynomial-tin -imee algorithm, can be converted to a circuit C. However, the size of this circuit is polynomial in the runtime of the algorithm. This is why C is required as input, e.g., one has no hope of discovering the Gaussian elimination algorithm by random initialization as probability would be exponentially small in the dataset size. Thus, their algorithm does not "discover" the learning algorithm itself-it is hard-coded into the network. As they discuss, they could encode in the circuit C an enumerative program search, but this is also parity learning algorithm that needs to be encoded into the network (and is in fact significantly more involved to encode as a circuit). Their work was recently extended to mini-batch SGD by Abbe et al. (202I). and it would be interesting to see if our result could be similarly extended.
3

---

2 Preliminaries
For simplicity, we focus binary classification with y :- {-1,1]. For domain X, (binary)
classifier is a function : X + For any distribution D over X' x V. the error of c is, erTp(c) := Pr( [e(z) # y) E [o, 1]. A learning algorithm takes input 2 1 labeled training examples in (X x y)+ 2 (X' x mm and outputs a classifier. For further simplicity, we focus data on the hypercube X2 := {-1,1}". The powers of 2 less than are denoted by 2 N (2- | E N}. We say an algorithm is poly-time if it runs in time polynomial in its input length, which is poly (dm) for a learning algorithm when run on m examples in dimensions.
2.1 Turing machines, circuits, and efficient computability
Since our main results require the simulation of an arbitrary efficient learning algorithm, we will need to establish formal notation for relevant concepts from the theory of computation. Various notions of computational efficiency may be used. To be concrete, we may use a 2-tape Turing Machine (TM) where the input is on the first tape and the 2nd tape is used for computation (e.g. see HHoperoft et al. (00T)) for a standard reference on Turing machines).
One issue that complicates runtime analysis of learning algorithms is that classifier may be very slow to evaluate, even if the learning algorithm is fast I There are two solutions to this issue, which are equivalent up to polynomial time. The first is learning algorithms that output classifiers, which rep- resent as Boolean circuits. Circuits circumvent this technicality because they can be evaluated in time nearly linear in the time it takes to output them. Thus time spent classification is folded into training time. Moreover, any binary classifier on X₂ can be represented as a circuit, and it is straightforward to convert NN to circuit with linear blowup. It is also well-known that other universal representations such as (imeebounded) TMs can be converted to Boolean circuits in polynomial time using unrolling. Other succinet representations could be used, but this choice simplifies runtime analysis.
Formally, we assume that each classifier output by a learning algorithm e Xa - y is represented as Boolean circuit, with False representing - and True representing 1. If the output of the learner is not a valid circuit classifier, then by default we assume it classifies everything as I. We also consider learners that can be simulated by TM with size I s in time t using only m labeled examples.
Definition 1 ((s m, boundedd learner). learner A a s-bounded learner which outputs a classifier circuit in at most i steps on any dataset consisting of at most m labeled examples.
2.2 Components of deep learning
In this section, we establish some notation for the building blocks of common deep learning pipelines.
Feedforward layers. A folle-connected feedforward layer R + Rd with activation function : RR + R is parameterized by matrix W E Rdoa Xdia and bias b E Rdo., specifying the map x + o (Wx+b) b), where a-)) is applied entrywise. A feedforward network is the iterative composition of feedforward layers, possibly omitting application of at the final layer.
Convolutional layers. Our main construction will apply the same constant depth feedforward network repeatedly to each x 3 patch of 2-dimensional "image"" This can be viewed as applying multi-channel convolutional layers followed by non-linear activation consecutively. Due to weight sharing across patches, the number of parameters do not depend on the input dimension but rather on the patch dimension and the number of channels. Often in practice, to ensure same output dimension as input, it is common to add a constant padding (say p) around the boundaries. This is crucial for our construction. More formally, convolutional layer specifies & x & patch-wise linear maps from x to Couu: in particular, when l 1, a convolutional layer specifies a pixel-wise linear map from RCin to CCatt We let Conv2D be the application of the linear maps extended to the entire input. We overload Conv2D to also allow for patch-wise fully-connected feedforward layers.
Natural examples where inference is more computationally expensive than learning arise in nonparametric models such neirhotss Gaussian processes.

---

Recurrent layers. Finally, our construction will use recurrent weight sharing: for function f: 3 x - + 2 and positive integer L, we use f(L); Z é - Z to denote the L-times iterated composition of f. sharing the parameters 0 θ between iterations; for example,
( 000000000
The training pipeline: SGD with random initialization. Finally, we establish some notation for stochastic gradient descent, whose variants form the predominant class of methods for training neural networks. Given continuously differentiable 2 loss function é: 3 x y R and continuously differentiable function / X + ) where O Rd a step of stochastic gradient descent (SGD) on single example (z, v) E X x VW with learning rate E R, maps the current iterate 0 to
= 0
(x,
SGD on a sequence examples { y/ ) defined by applying this recurrence iteratively from an initialization Oo (usually selected randomly from specified distribution), giving sequence of iterates (0:) -- It is routine to specify a subset S S [d] of the parameters to be optimized; this case, the parameters in S are updated according to the above equation, while the rest are unchanged.
3 Algorithm learning and Turing-optimality
In this section, we adopt a model of learning which turns PAC learning upside down. A learning algorithum is function A that, for any d, m 2 1, outputs classifier A(Z) Xa + y for any dataset Z = ((x(1) ))m (Ka x 7 of m labeled d-dimensional examples. Recall that X₂ 1], and y' [-1,1}.
The following definition captures efficient learnability of class of learning algorithms A. The run-time of the algorithm is required to be polynomial in its input size feature of this definition is that it requires the number of examples be polynomial in the dimension d, avoiding the curse of dimensionality. Since we will soon consider 6 as inputs, we consider only powers of to avoid having to represent arbitrary real numbers.
An important
Definition 2 (PAO-learner) Poly-time learning algorithm A is Probably Algorithmically Optimal (PAO) learner for family A if there is a polynomial p such that for any c, 5 E 2-N, for any Z 1, any distribution D over Ng x y, and any dataset sizes > 1, M 2 p(d, m, 1/c, 1/6).
Pr Z.-Di ZDM
eer S min err (B(Z)) + + 2 1 5, BEA
where Z; Z' is the concatenation of the two datasets Z.Z' Z'. We further assume that d, and M can be determined from the PAO-learner's input.
We now observe that can equivalently design learning algorithm that has e, Observation 1 (e, 8-PAO-learner reduction). Let Ac be an "e, 8-PAO learner" for A meaning that is a poly-time learning algorithm that takes additional inputs e, 6, and there exists some constant such that: for any e,8 2 -N
inputs.
any dataset sizes m 2 1, M (dm/e8)².
Pr ZNDm 2' DDM
err (A,D((,,(2;2'))) < min errp (B()) +6 2 1 - BEA
Then, for 21- 3. log MJ, A is a PAO-leamee for A.
The proof is straightforward and can be found in Appendix A The M 2 (dm/e6)* requirement is convenient equivalent polynomial bound M 2 pp(d, m, T/c,,1//)
Although we only analyze PAO learning for the family AA of bounded Turing machines, it can be analyzed even for continuous classes A. For instance, it would be straightforward to show that grid search can PAO learn constant number of bounded hyperparameters of a given algorithm the
Itt is routine to extend these definitions to continuous functions which are piecewise continuously differen- tiable, such as neural networks with ReLU activations. We omit the details in this paper, as our constructions will never evaluate gradient of f at discontinuity.
5

---

algorithm's 's enror is Lipschitz continuous in those hyperparameters, using a separate validation set to choose the best hyperparameters. PAO learning, as defined, does not specify how classifiers are represented, and could apply to any classifier representation. Recall that we represent classifiers by Boolean circuits as discussed in Section 2
We next define Turing-optimal learners, which are PAO-learners for the class of bounded TMs (constant size, run in polynomial time, and output a eircuit classifier).
Definition 3 (Turing-optimal) Fix constants 8, k E N. Let the set Ba.k be the set of Turing machines which have I states and, run in time I (2dm)* on dataset Z E (Na x ym and output circuit. Learning algorithum
(s. ke)-k -Tuing-oppiiml if A PAO-learns (or equivalently c, 6-P.OO learns) B..k. Learning algorithm A is Turing-optimal if A is (8, -iTriniin-lllll for all constants 8, k E N.
Note that a Turing-optimnn learner must run in poly-time but the number of examples required to learn each B., can be different, i.e., it will learn B., using M 2 (dm/c8)=* additional examples, for a different constant esk for each 8 and k. Similar to Observation [ Turing-optimal learner can be constructed from an (s, --Tuuinn optimal learner. The claim below, together with Observation [ imply that (e, 8, - -i)TTTrnnn--ptinne learner can be converted to a Turing optimal learner. Algorithm
2 and its proof are presented in Appendix A
Claim ((s, 33-TTrrnn-ooptinee reduction). Let Ag.k be an algorithm that takes inputs 8, k and is (s, k) -TTriig optimal for each pair of constants 8, k E N. Then, Algorithm 2 (A.,k) is TTrring-ppimal.
Finally, it is not difficult to see that a Turing-optiman learner also PAC-learns any concept class that is PAC-learnable. Following standard conventions, the PAC learning algorithm is given target accuracy and failure probability 5 as inputs. Also, say a distribution 'D is said to be consistent with set C. of classifiers if there is some c C with (rrp(c)= (c)==))
Definition 4 (PAC-learning), Let C = Uaz1 Cs. where : Xd + y for each E Ca. oly-time learning algorithm Ar,8 PAC-learns C Ar,8 and there is polynomial p such that, for any e, 8 E 2 d LEN N4 m 2 p(d, l/c, 1/5) and distribution D consistent with Ca:
Pr ZmD
(Ar, (Z)) S 2 1-
The computational polynomial-tin time efficiency requirement on A..5 means that its runtime is polyno- mial in its input size, poly(dm + log 1/e8), because it takes Ollog 1/7) bits to describe E 2
Claim 2. Suppose there is some learning algorithm that PAC-learns C and suppose that A is polynomial-tine -imee Kuring-optimet learner. Then A PAC-learns as well.
We defer the proof to the Appendix
A
4 Turing-optimality of SGD on randomly initialized RCNNS
In this section, we will design a Turing-optimal leaner in the form of a NN and a corresponding training pipeline. Our NN will be of the form of RCNN (see Figure 2 with very few trainable parameters and our training pipeline (see Algorithm [ will use random initialization, and random restarts to find good parameters. Let us present our main result.
Theorem 1. There exists constants C1, C22 C3 > 0 such that the following holds. For any d, 8, m, t E N. there exists learning rate n E R. = ct + m d), and U2 C where: for any probability measure D on Xa x 11, (s. m. t) t)-oopuuta learner A, and training set S E (Xa x (1,, drawn i..dd from D, Algorithm returns function f such that with probability at least s c226
crr((f) S (A)
The bit precision required by Algorithm is [log(s) + c3.
'The standard PAC learning definition requires the learner to run in time also g(d, 1/e, 1/8) for some polynomial 9. which would admit an algorithm that is not poly-time, e.g., if it uses I examples but runs in time q(d, I/c, e, 1/8). However. such an algorithm can trivially be converted to a poly-time algorithm by padding its input with an additional q(d, 1/e, 1/8) examples.
This set can be constructed with knowledge of only s.

---

Algorithm SGD on randomly initialized RCNN
Input: training set = (xx11) ()) =- size 8, initialization set Uss depth I,, learning rate r)
Create dummy sample (x(m++1, 1)+ (Ila,
(see Definition 50 with parameters O θr. h such that W = 0, and all entries of V1, V2, V3, Va, Vs, U1, U2 are sampled uniformly from U, for 1 = to m + do
Initialize f E RCNN
F=+1Im+11100e,100
Update parameters in the memory layer:
(T(ato 1] W. Orc. Ghead) .1(
((++) = W Vwl
W==W()
where L: R. R IR is the squared loss, that is, l(ú, v) 3 -1) Output: function f(; ((m++)) θr. hhedd)
apply L times
5-layer NN
padding
2-layer NN
weight W
Σ
output
Figure 2: Recurrent convolutional neural network from our construction. A dense weight matrix W applied the input to convert it into 2D followed by adding padding of to the right. This is followed by L applications of a 3 3 convolutional layer where each layer applies a 5-layer NN to each patch. This followed by pixel-wise convolutional layer consisting 2-layer NN. Lastly, the output corresponding to the main grid is summed.
Remark. Our Algorithm sets the learning rate of 0 for the shared weights in the RCNN part of the NN and updates only the dense memory layer. Since result is constructive, it is entirely possible that a search for an optimal-leaming rate may perform better practice.
Finally, we will use Theorem I to create (s, k)-Turing optimal learner with the help of random restarts and an additional validation set,
Corollary 2. For fixed constants Cı, 02 Algorithm 1 can be converted to an (e, 8, -TTrinn optimal learner for any fixed s, k, time bound t (2dm)* s and (0, 1) by running it s log (1 times with random restarts, and selecting the classifier that performs best on validation set of size 028 log s log(1/5)/e2.
Claim D converts this to a Turing-optimal learner. Because our formal definition of Turing-optimality applies only deterministic circuit classifiers, must also convert the NN circuit and derandomize the algorithm (which can be done using random bits extracted from additional iid random labeled examples (Kearns and Vazirani 1994)).
Next we give detailed description of the architecture and proof overview of Theorem The proof of Corollary 2 and the complete proof of Theorem can be found in Appendix B
4.1 Network architecture: RCNN with memory layer
Let us first describe the neural network architecture that Algorithm uses in more detail. The archi- tecture comprises of a dense layer of size linear in m (the number of samples) and d (the dimension

---

of the input) as the first layer. The output of this layer is padded with 1s on the right, and then fed into a RCNN (recurrent weight-sharing across depth and convolutional weight sharing across width). The RCNN has only poly(s) shared parameters, due to its recurrent and convolutional nature. 'hheee shared parameters are in the form of 5-layer NN applied as a convolutional layer to 3 patches of the input This convolutional layer is applied recurrently I. = p(t, d, m) times for some polynomial p (with the same parameters) where is the bound on the runtime of the TM. The final outputs from the RCNN are then passed through pixel-wise 2-layer NN and finally summed to give a scalar prediction.
Definition (RCNN with a memory layer). For diny dmem: die: Chead, I > O, define the function class Shes the is parameterized by memory layer F cran dre dredss of RCNNS where each f E FFRNN
RCNN
parameters Ome = {W} } with W E cheee x RC layer parameters O == {V,, V2, V2, V4, V/5 ] with V1 E Rdd X9 122, V3, V42 E Rd Xdhe, Vs E =Rd, and head layer parameters @head = {U1, U2} with U1 E R.dres x1, U22 E RIxdman), The local convolutional operation is denoted by SConv2D R3x3 + R. and is applied on the 3 x 3 grid centered at each coordinate of the dmmm x (din + 1) input (with padding for the edge coordinates). We overload the notation fComv2 to denote the dmem X (din + () output post the local application on the input.
f f2; mme.: ORCNN: hhead) sum (needd (FEOmDD (fmem (2: mmem); ORCNN)..d.) @head))
where Smem (z; O = {W}) = [ Wding(=) Ild ]
fnead (z: O = {U1, U2} = U10(U22)
SConvaD (z; θ (V1, V2, Va, Va, V/H)) ViO (oo(VVss((VVivve(3))
with a being the ReLU activation.
Remark. If our architecture did not have both recurrent and convolutional weight sharing, then the number of parameters would have dependence on din, dmem and I, which depend on m, d, and T.
4.2 Proof sketch for Theorem
Here we present a proof sketch for Theorem D Our proof follows by construction, that is, we show that for each TM A of size s, there exists parameters O,e and Onead that ensure that (1) for the first m + 1 steps, when mem is trained with SGD, the gradients assist with memorizing the training set in the values of W mem. and (2) given the memorized training set, the RCNN computes the roll-out of A with the input tape having the training set and the test example giving the prediction of A on the test example as the output. We finally show that the parameters θre and Ohead in our construction for all TM of fixed size and runtime belong to a fixed finite set of size O(s) that can be constructed with knowledge of only s. The following lemma summarizes the aforementioned properties:
Lemma 1. For any d, 8, m, E N, 5 E (0, 1), and any (s, m, -)compuutable learner A, there exists
Pc.: heedd with each parameter belonging to fixed set Us of size ((s) (that can be constructed with the knowledge of only 8) such that Algorithm] 7 with I, satisfies:
Fy ( (a)
if Tasi d if S i, d + 1. otherwise.
1. Memorization: For 1 Sis S m + W00 =
fa())
ab
([T) x
2. Computation: For all (=1]4,
(m++)) O... Ohead A(S)
Theorem I follows from the above the computation property of Lemma I since implies that the error of Algorithm I will be exactly equal to the error of A.
What remains is prove the existence of parameters that satisfy Lemma Let now briefly describe the key functionality we require the RCNN to implement for this:
Computation. Each roll-out step of the TM is local update around the head of the TM. To implement one step of the TM, we need to compute the transition function of at the location of the
$ Note that we did not optimize our construction. is quite possible to improve this a shallower network. 'For ease of presentation, we hide the biases from the parameters. We can assume that the input is padded with I account for biases.
8

---

head, update the new head and state, and copy the inputs of the rest of the tape. Our first observation that this local update can be implemented using a convolutional layer if we interpret the input as the tape of A (input and working concatenated) with the head and state information stored along with the tape value. Composing these layers t times (with the same parameters) allows us to simulate steps of the TM. More importantly, the convolutional layer requires only ((s) parameters since A only has s states. In order to decode the tape content, head position, and state from the values fed to the layers of the RCNN, we interpret the input in base 3 and use different positions to encode the desired information (see Appendix B. for more details).
Memorization. Given that we can simulate the TM, we need to ensure that the input to the RCNN has the training set and the test example encoded onto it. Similar to [bbe and Sandon (222)) we can use SGD to memorize the training examples into the weights of the memory layer. with each row storing one example. We do this by ensuring that the gradient at iteration i through the RCNN is 1 for exactly the ith row and O for every other row. We also ensure that the output is O through the memorization phase. By using chain rule, this gives us a gradient of (0(0)))()) y y for the ith row of W Wemm and otherwise. We can this in a local manner using the RCNN. Note that the memory layer has (dm) parameters, however we can learn these parameters from 0 initialization.
Communication. Lastly, need to ensure that the network can differentiate between memorization phase (passing meaningful gradients) and computation phase (implementing the roll-out of the TM) using the local operations in the RCNN layers. We do this by implementing local communication protocol: we broadcast a message based on certain conditions, where each RCNN layer implements a step of the broadcast. In order to broadcast the entire input, we require d + m overhead in terms of the depth of the network.
Finally, show that the above mentioned functionality can be achieved by 5-layer NN with O(s²) parameters. To do so, we first describe the exact function we require the network to compute and its Jacobian all inputs that bit precision allows (see Appendix [B.2 for the exact function). Given the function and its Jacobian on a finite set, we prove a general representational theorem (see Appendix B.4.1) that constructs 5-layer NN with weights from fixed set that be constructed with knowledge of only s. We refer the reader to Appendix B for the complete proof.
5 Discussion
In this section, we discuss potential practical implications of TTuring-optimality, and broadly discuss corroborations and tensions with empirical trends.
Discovering reusable algorithms. Our analysis is wasteful in that, if one has multiple learning problems, e.g., multiple parity problems, one has to relearn the learning algorithm for each one. In fact, arguably the NN may not have learned algorithm for parity problems in general, but rather a specialized algorithm that works on just one. To find a reusable algorithm, one needs multiple prob- lems, say drawn from meta-distribution jr over learning problems. The idea is simple: viewing the constant number of weights of the RCNN filter as hyperparameters, one tries multiple such hyperpa- rameters on log 1/8 learning problems, and finally selecting the hyperparameters that perform best on average. With constant-sizee random sample of hyperparameters, with high probability, one of them will perform nearly as well as the best constant-sized TM not only on these few training problems, but also on future problems drawn from μ.. This is the setting considered by the literature on meta- meta-learning (Hospedales et al. 202T) and data-driven algorithm design (Balcan, 2020). Recently, Garg et al. (022) show empirically that Transformer architectures can meta- and execute simple learning algorithms in-context. We leave this and numerous other interesting directions for future work.
Concise architectures. Many practice. The lens of Turing-optimality may help us understand what architectures are minimally adequate from a theoretical perspective. In particular, it has been popular to report ever- wer-growing parameter counts for state-of thethe-rrt art models domains such as natural language processing (Brown) et al. 2020 Fedus et al. [021 Lin et al. 202T). Although the other benefits of over- parameterization are at play, this work suggests that very parameter-efficient architectures are sufficient to simulate any computationally efficient learning algorithm. In light of the above, one concrete direction for further investigation to develop practical variants of our RCNN construction, in domains dominated by other architectures. Although our analysis is too pessimistic to be of immediate practical use, it
architectures have been proposed and used in

---

highlights the computational power of an architecture that has occasionally appeared in applications- focused research (Pinheiro and Colloberi 2014 Liang and Hu 2013 Spoerer al. 2017; Alom
et al. 2021 Significantly closer to our work. Schwarzschild et al. (2021) conduct an empirical study on the ability of RCNNS to extrapolate from easier to harder tasks (thus "learn an algorithm" "); our work shows that it is possible for these architectures to learn any computationally efficient algorithm. Similarly, RCNNs have been investigated for planning in RL (aamar et al. [0166; other empirical works which take "computation time" view of depth include (Graves et al. 2014: Banino et al.
2021; Kaiser and Sutskever 2013). RCNNs have not seen widespread adoption in state-of-the-art deep learning compared to their non-recurrent and/or non-convolutional counterparts
Beyond local search for recurrent models. The proliferation of non-recurrent attention-based models in domains previously dominated by recurrent networks, along with the underrrepresentatioo of RCNNs, is perhaps due to instabilities in training recurrent networks with SGD (Pascanu et al. 2013). Indeed. Kasai et al. (202T) demonstrate that carefully designed training procedure can convert a trained Transformer into a more parameter-efficien RNN. There may be undiscovered practical training algorithms which can bridge the gap in favor of recurrent models. Although our Turing-complete algorithm uses SGD, uses the gradients in a way that far from making local greedy progress objective; the as-efficienntas as-posiibee search for the correct TM is implemented by random initialization.
Exhaustive search. Our Turing-optimal training pipeline relies upon exhaustively comparing classifiers trained from different random initializations to choose the best classifier within the class of concise Turing machines. This runs counter to the classical viewpoint from continuous optimization, where gradient descent is seen as a local search method. In problem settings or algorithmic nature, we posit that exhaustive search may be unavoidable; indeed, state-of-the-an pipelines already include forms of exhaustive search such as beam search and its variants (Redyy
combinatorial
al. 1977 Leblond et al. 2021 well as chain-of-thought generation (Wang al.
2022
Memory modules. There have been many attempts to build practical memory modules into neural
networks (Graves et al. 2014 (Sukhbattar et al., 2013 Grave et al.) 2016: Dai et al., 2019). Our construction proposes an integrated memory mechanism: use SGD to store samples the first layer's trainable parameters, ahead of the deep (RCNN) computation layers, by carefully ensuring that the gradient signal pack-propagates through the RCNN layers correctly.
Conclusion
In this paper, we present a simple NN architecture, combining recurrent and convolutional weight sharing, that achieves Turing-optimalityy Among other things. it learns the well-studied class of parity functions in polynomial time, whereas prior NN analyses of parity require time exponential in the size of the parity function (or require a parity learning algorithm to be initialized into the networks weights). Our proposed architecture has connections to the deep learning literature and observed empirical trends, discussed in Section 5 Immediate improvements to make the architecture more concise and natural include: (1) reducing the size of the dense parameters to depend on the algorithm's 's memory usage instead of the training sample size, and (2) using SGD beyond memorization. In future work, it would be interesting understand which other architectures are Turing-optimal. answering questions such as: are 2D convolutions necessary, and are there natural Transformer-based training pipelines which are furing-optimat
Limitations and broader impact. The primary limitation of this work is that the constant factors in our analysis are much too large to be meaningful in practice. Nonetheless, we hope that idea of combining recurrent and convolutional weight sharing will have impact. Also, the algorithms found using enumerative program search would be, by default, difficult to interpret. Using such algorithms carries risks, especially if the algorithm is not doing what one expects it to do.
Acknowledgments. We thank Santosh Vempala for useful discussions. Sham Kakade acknowl- edges funding from the Office of Naval Research under award N00014-22-1-2377 and the National Science Foundation Grant under award #CCF-1703574
Note that the popular R-CNN of Girshick al.
2014 is not recurrent; the "R" stands for region.
10

---

References
Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro. 2021. On the Power of Differentiable Learning versus PAC and SQ Learning. Advances in Neural Information Processing Systems 34 (2021).
Emmanuel Abbe and Colin Sandon. 2020. On the universality of deep learning. Advances in Neural Information Processing Systems 33 (2020), 20061-20072.
Md Zahangir Alom, Mahmudul Hasan, Chris Yakopeic, Tarek M Taha, and Vijayan K Asari. 2021. Inception recurrent convolutional neural network for object recognition. Machine Vision and Applications 32, 1 (2021), 1-14.
Sanjeev Arora and Yi Zhang. 2021. Rip van Winkle's Razor: A Simple Estimate of Overfit to Test Data, arXiv preprint 11Xiv:2102.13189 (2021).
Maria-Florina Balcan. 2020. Data-driven algorithm design. arXiv preprint arXiv:2011.07777 (2020).
Andrea Banino, Jan Balaguer, and Charles Blundell. 2021. Pondernet: Learning to ponder. arXiv preprint arXiv:2107.05400 (2021).
Andrew R Barron. 1993. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory 39, (1993), 930-945.
Andrew R Barron. 1994. Approximation and estimation bounds for artificial neural networks. Machine learning 14, I (1994), 115-133.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020a. On the ability and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009. 11264 (2020).
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. 2020b. On the computational power of trans- formers and its implications in sequence modeling. arXiv preprint 220::22000002888 (2020).
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. 2020. Language models are few-shot learners. arXiv preprint arXiv:2005.14165 (2020).
George Cybenko. 1989. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems 2, (1989), 303-314.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov. 2019. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901.02861 (2019).
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Fukasz Kaiser. 2018. Universal transformers. arXiv preprint arXiv: /807.0381 (2018).
Luc Devroye, Laszlo Gyorfi, Adam Krzyzak, and Gábor Lugosi. 1994. On the strong universal consistency of nearest neighbor regression function estimates. The Annals of Statistics (1994), 1371-1385.
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. 2021. Inductive Biases and Variable Creation in Self-Attention Mechanisms. arXiv preprint arXiv:2110.10090 (2021).
William Fedus, Barret Zoph, and Noam Shazeer. 2021. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.0396) (2021).
Ken-Ichi Funahashi. 1989. On the approximate realization of continuous mappings by neural networks. Neural networks 2, (1989), 183-192.
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. 2022. What Can Transformers Learn In-Context? Case Study of Simple Function Classes. arXiv preprint arXiv:2208. 01066 (2022).

---

Ross Girshick, Jeff Donahue. Trevor Darrell, and Jitendra Malik. 2014. Rich Feature Hierarchies for Accurate Object Detection and Semantic Segmentation. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR).
Edouard Grave, Armand Joulin, and Nicolas Usunier. 2016. Improving neural language models with continuous cache. arXiv preprint
(2016).
Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural turing machines. arXiv preprint arXiv:1410.5401 (2014).
John Hoperoft, Rajeev Motwani, and Jeffrey D Ullman. 2001. Introduction to automata theory, languages, and computation. Acm Sigact News 32, (2001), 60-65.
Kurt Hornik, Maxwell Stinchcomhe, and Halbert White. 1989. Multilayer feedforward networks are universal approximators. Neural networks 2,5 (1989), 359-366.
Timothy M Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J Storkey, 2021. Meta-learning in neural networks: survey. IEEE transactions on pattern analysis and machine intelligence (2021).
Eukasz Kaiser and Ilya Sutskever. 2015. Neural gpus learn algorithms. arXiv preprint 0rXiv:1511.08228 (2015).
Jungo Kasai, Hao Peng, Yizhe Zhang, Dani Yogatama, Gabriel Ilharco, Nikolaos Pappas, Yi Mao, Weizhu Chen, and Noah A Smith. 2021. Finetuning Pretrained Transformers into RNNs. arXiv preprint arXiv:2103, 13076 (2021).
Michael Kearns and Leslie Valiant. 1994. Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. ACM 41, 1 (jan 1994), 67-95. https://doi. org/10 1145/174644
174647
Michael J Kearns and Leslie G Valiant. 1993. Cryptographic limitations on learning boolean formulae and finite automata. Machine Learning: From Theory Applications. Springer, 29-49.
M. J. Kearns and U. V. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA.
Rémi Leblond, Jean- Sann-Bapistt Alayrac, Laurent Sifre, Miruna Pislar, Jean- Sran-Baptiste Lespiau, Ioannis Antonoglou, Karen Simonyan, and Oriol Vinyals. 2021. Machine translation decoding beyond beam search. arXiv preprint
(2021).
Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. 2017. On the ability of neural nets to express distributions. In Conference Learning Theory. PMLR, 1271-1296.
Leonid A. Levin. 1973. Universal Sequential Search Problems. Problems of Information Transmission 9,3 (1973).
Ming Liang and Xiaolin Hu. 2015. Recurrent convolutional neural network for object recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. 3367-3375.
Junyang Lin, An Yang, Jinze Bai, Chang Zhou, Le Jiang, Xianyan Jia, Ang Wang, Jie Zhang, Yong Li, Wei Lin, et al. 2021. M6-10t: A sharing-delinking paradigm for efficient multi-trillion parameter pretraining. arXiv preprint arXiv:21 10.03888 (2021).
Michael Nielsen. 2015, Neural networks and deep learning. Vol. 25. Determination press San
Francisco, CA.
Razvan Pascanu, Tomas Mikoloy, and Yoshua Bengio. 2013. On the difficulty of training recurrent neural networks. In International conference machine learning. PMLR, 1310-1318.
Pedro Pinheiro and Ronan Collobert. 2014. Recurrent convolutional neural networks for scene labeling. In International conference machine learning. PMLR, 82-90.
12

---

D Raj Reddy et al. 1977. Speech understanding systems: A summary of results of the feve-year research effort. Department of Computer Science. Camegie-Med Mell University, Pittsburgh, PA 17 (1977), 138.
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. 2021. Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks. arXiv preprint arXiv:2106.0455: (2021).
Hava Siegelmann and Eduardo Sontag. 1995. On the computational power of neural nets. Journal of computer and system sciences 50, 1 (1995), 132-150.
Courtney J Spoerer, Patrick McClure, and Nikolaus Kriegeskorte. 2017. Recurrent convolutional neural networks: better model of biological object recognition. Frontiers in psychology 8 (2017), 1551.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. 2015. End-to-end memory networks. arXiv preprint
503.08895 (2015).
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. 2016. Value iteration networks. In Proceedings of the 30th International Conference Neural Information Processing Systems. 2154-2162.
Junping Wang, Quanshi Chen, and Yong Chen. 2004. RBF kernel based support vector machine with universal approximation and its application. International symposium on neural networks. Springer, 512-517.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le. Ed Chi, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171 (2022).
Colin Wei, Yining Chen, and Tengyu Ma. 2021. Statistically meaningful approximation: a case study on approximating turing machines with transformers. arXiv preprint UrXiv:2107.13161 (2021).
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. 2019. Are transformers universal approximators of seueenceet--seuencee functions? arXiv preprint arXiv:1912.10077 (2019).
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Last paragraph of Section 5
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Last paragraph of Section 5
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Many proof are in the appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
13

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "cmgvkSdu09H", "reviewer": "Reviewer_Jx5f", "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.", "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.\n\n[1] https://arxiv.org/abs/1611.01491\n\n[2] https://proceedings.neurips.cc/paper/2021/hash/1b9812b99fe2672af746cefda86be5f9-Abstract.html\n\n2) 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?\n\n3) 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?\n\n4) 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?\n\n5) Likewise, isn't it limiting to assume recurrent weight sharing?\n\n6) 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?\n\n7) 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.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nMinor comments on writing:\n- Line 41: \"innovation\" -> contribution?\n- Line 52: \"to use a use a\": remove \"a use\"\n- Line 180: \"the a number of examples\": remove \"a\"\n- Line 251: \"1can\" -> \"1 can\" (add space)\n- Line 254: Please repeat that m is the sample size and d is the input size\n- 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", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MxKeMyb9qH7", "reviewer": "Reviewer_ZUm5", "summary": "The paper describes a theoretical model based on recurrent and convolutional neural modules that achieves what the authors call \"Turing-optimality\". \nMore 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.`", "questions": "See above", "limitations": "Discussed", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \nI found the paper quite unclear and rather hard to follow. It seems to jump to conclusions before building preliminary concepts and sufficient intuition.\nSome passages are rather unclear and seem to be contradictory: eg :\n*The contribution of this work is showing that a definition\nof Turing-optimality is achievable by a simple NN architecture. In future work, it would be interesting\nto better understand which architectures, initializations, and learning rates are Turing-optimal.*\nI am left to wonder whether one contribution of this paper is indeed that mentioned in the first reported sentence or not.\nThere 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.\n\nMy 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Ke3_8zIDgNS", "reviewer": "Reviewer_UfCN", "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.", "questions": "1. Line 97, did you mean [Wei et al.] doesn't take computational efficiency into account?\n2. Can you elaborate how random restarts are different from enumerative program search?\n3. Typo in line 272?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The notion of Turing-Optimal Learning is original, intuitive, and interesting.\n2. The theoretical part is rigorous and requires significant effort.\n3. The exposition is clear, and the proof sketch is informative.\n\nWeaknesses:\nThe 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JSYuPxq1HqE", "reviewer": "Reviewer_AW8a", "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.", "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? \n2. 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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- 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.\n- The writing is clear.\n- 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.\n- Additionally, the theoretical grounding for choosing recurrence/weight sharing of this type might motivate the applications-forward researchers as well.\n\nWeaknesses\n- As is mentioned by the authors, the bounds/constants are not practical. \n- 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.)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept