Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
Authors: Colin Wei
Yining Chen
Tengyu Ma
Venue: NeurIPS 2022 Accept (2022)
Keywords: approximation theory
generalization bounds
sample complexities
learning theory

Abstract: A common lens to theoretically study neural net architectures is to analyze the functions they can approximate. However, the constructions from approximation theory often have unrealistic aspects, for example, reliance on infinite precision to memorize target function values. To address this issue, we propose a formal definition of statistically meaningful approximation which requires the approximating network to exhibit good statistical learnability. We present case studies on statistically meaningful approximation for two classes of functions: boolean circuits and Turing machines. We show that overparameterized feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity depending only polynomially on the circuit size, not the size of the approximating network. In addition, we show that transformers can statistically meaningfully approximate Turing machines with computation time bounded by T, requiring sample complexity polynomial in the alphabet size, state space size, and log(T). Our analysis introduces new tools for generalization bounds that provide much tighter sample complexity guarantees than the typical VC-dimension or norm-based bounds, which may be of independent interest.

Statistically
Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
Colin Wei
Yining Chen
Tengyu Ma
Department of Computer Science Stanford University
{colinwei, cynnjjs, tengyuma)@cs www.eesttttoorereeeoeeeee
Abstract
A common lens theoretically study neural net architectures is to analyze the func- tions they can approximate. However, the constructions from approximation theory often have unrealistic aspects. for example, reliance on infinite precision to memorize target function values. To address this issue, propose formal definition of statisti- cally meaningful approximatoo which the approximating network to exhibit good statistical learnability. We present case studies on statistically meaningful ap- proximation for two classes of functions: boolean eircuits and Turing machines. We show that overparameterized feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity depending only polynomially on the eircuit size, not the size of the approximating network. In addition, we show that transformers can statistically meaningfully approximate Turing machines with computation time bounded by T. requiring sample complexity polynomial in the alphabet size, state space size, and log(T)) Our analysis introduces new tools for gen- eralization bounds that provide much tighter sample complexity guarantees than the typical VC-dimension norm- comm-based bounds, which may be of indepeneent interest.
Introduction
40 31 common way to Dating back the seminal works on universal approximation [16
theoretically study neural nets has been through their expressivity, which measures the ability of neural nets to approximate well-behaved functions. This perspective has shaped how researchers perceive different types of deep learning architectures: a basic way to theoretically justify new architectures is to study their approximation capabilities. This has led to number of analyses studying universal approximation capabilities for various widely-used architectures, such recurrent neural nets (RNNs) [47] graph neural nets (46 convolutional networks 3 64 59 residual networks [32]
transformers 611 and neural ODEs [1 63].
However, approximation theoretic results often misalign with more meaningful end-to-end guaran- tees, because models constructed in the literature often exhibit unrealistic properties. For exam- ple, a common technique in the universal approximation literature is to rely strongly on infinite- precision weights and activations, exponentially many parameters to encode the desired function values 22
44 This issue even arises outside of universal approximation, e.g., various papers demonstrate the ability of RNNs and transformers to simulate various computational models such as Turing machines and automata, but require strong reliance arbitrary precision [48] 42 29]9]
Infinite precision can inflate the expressivity of an architecture (function class) in a unrealistic and misleading way: for example, finite width RNNs with infinite precision can simulate Turing machines, but finite- precision, finite-width RNNs cannot. This is implied by streaming lower bounds [I any finite precisson,,,oon finite-widhh RNN induces finite-space streaming algorithm corresponding to running
36th Conference Neural Information Processing Systems (NeurIPS 2022).

---

the RNN on the inputs. However, streaming lower bounds tell us that finite-space streaming algorithms not powerful enough simulate Turing machines, and hence finite-pree prenee-pecisoon, finite-width RNNs cannot either. As another example, Park et al. [4]] exploit infinite precision in the parameters to show that neural net with parameter count sublinear in n can memorize n arbitrary input-label pairs. How- ever, simple counting argument reveals that this result cannot be proven using finite precision networks there are 2n Input-labeling pairs, but only 20(n) finite precision networks with o(n) parameters.
More broadly, the ideal theoretical perspective should consider not only whether target functions can be expressed, but also whether the approximating functions can plausibly be obtained by fitting a neural network to a finite training sample, as is the case in practical deep learning settings. The latter question can be decomposed into studying optimization and generalization. Unfortunately, rigorous analysis of optimization is unresolved even for simple two-layer nets [55 33 Global optimization
analyses such NTK do exist [8 26 but there is large body of theoretical and empirical work showing that neural networks can generalize much better than NTK analyses can hope to prove 57) 57).
Generalization is more tractable, so we propose to study expressivity and generalization together.
Towards studying more meaningful notions of approximation, this work proposes statistically meaningful (SM) approximation. This definition requires not only the existence of an approximating network, but also that it has good statistical properties. Consider a setting where the aim is to fit the target function G using the approximating family F and finite sample of training data. SM approximation requires existence of loss whose empirical risk minimizer in F leads to model with low approximation error in fitting G. We define the sample complexity of the approximation as the number of training samples needed to guarantee approximation error and study SM approximation with low sample complexity bounds. SM approximation essentially eliminates statistical concerns about fitting the target function with a finite sample (optimization concerns can remain).
We present two case studies on SM approximation. First, we demonstrate that overparameterized feedforward neural nets can SM approximate boolean circuits with low sample complexity that depends only on the intrinsic circuit size. Though it simple to construct neural nets to approximate boolean circuits, bounding the sample complexity of the approximation is challenging, For example, standard norm-based generalization bounds for the naive construction scale exponentially in depth (5 [6. Furthermore, VC dimension- bounds would scale polynomially in the number of parameters in the network [23]. which is problematic because for practical optimization concerns, neural nets are typically overparameterized in terms of width (22) In contrast, our sample complexity bound for SM approximation depends only on the intrinsic circuit size, up to logarithmic factors.
Our second case study is on SM approximating Turing machines with transformers. We consider class of Turing machines with bounded computation time T and construct encoder-decoder transformers [53] which SM approximate these Turing machines. The sample complexity of the approximation depends on a polynomial in logT and the sizes of the state space and the alphabet of the Turing machine. Though constructions for approximating Turing machines from prior work [48 42 have not been formally studied from a sample complexity perspective, existing bounds would depend at least linearly on T. Furthermore, our construction only uses loglog' precision, compared to at least log?' in prior works, resulting in the exponential improvement in the sample complexity.
Proving sample complexity guarantees for our SM approximation results is nontrivial and requires additional insights. To obtain our sample complexity bounds, we leverage a recent generalization bound which depends on data-dependent Lipschitzness [56]. We develop theoretical tools to convert a broad class of neural nets, with possibly large Lipschitzness, into ones with small Lipschitzness on the training data, by introducing a number of new layers that is linear in depth. Our result applies to neural nets where each entry in the hidden representations on the training data takes values from a finite set (e.g., binary entries), and may be of independent interest.
In summary, our conceptual contribution to propose a new notion of statistically meaningful approximation, intended to provide more meaningful guarantees by requiring that the approximating family have good statistical learnability. Technically, 1) we prove that feedforward neural nets can meaningfully approximate boolean circuits with sample complexity that depends polynomially on the width and depth of the circuit; and 2) we show that transformers can meaningfully approximate Turing machines with sample complexity logarithmic in the computation time.
1.1 Related works
Classifical approximation theory for neural networks has a long history. Hornik et al. (25), Cybenko 16). and Leshno et al. (31 show that neural nets with one hidden layer are universal approximators but require the hidden layer size to grow exponentially in input dimension. Barron [4] uses the Fourier
2

---

transform to write target functions as infinite-widhe networks and subsamples neurons to obtain widths which depend only on target function properties. Lee al. (30], Ji et al. [27 prove recent related
developments in this direction of universal approximation.
Many works study benefits of deep networks over shallow ones 8 2
50
19
17
10 Bengio and
Delalleau [8] show separation for exact representation, whereas Telgarsky [50 shows separation for ap- proximate representations with univariate imputs. Eldan and Shamir 19] demonstrate -ign-dimensional
functions that can be approximated by two-layer polynomial-size neural networks, but cannot be approximated by one-layer neural nets with subexponential hidden units. Via reduction to certain com- plexity theoretic questions, Vardi and Shamir [52) show that proving constant depth separations may be hard. Malach et al. [5]] analyze the re relationship between optimization and approximability. showing in various settings that deeper networks cannot be optimized if shallow networks cannot approximate them. This demonstrates that depth separation results (50) from approximation theory can misleading since gradient descent anyways cannot optimize the deep networks used to construct the approximation.
Another area of study is on the ability of deep networks to memorize training data 62 60 al. [60] show that (n) parameters are sufficient to memorize (n)) training points for ReLU nets with at least 3 layers, and Park et al. [41] reduce the parameter requirement to sublinear in n. Similar results
54) Yun
have been proven for residual architectures [22) and convolutional nets [39]. Bartlett el. ( analyze the VC-dimension of neural nets, leading to bounds on the parameter count needed to fit training data. Other
works study expressivity via connections to tensor approximation and sum num-product networks [1] 15.
There is long line of work on studying the ability of neural nets to recognize and represent formal languages. The seminal work of Siegelmann and Sontag [48] shows that RNNs are Turing complete but leverages infinite precision in the hidden activations. Chen et al. 12 extend this result to ReI.U activations and study implications in language modeling. Many variants of transformers are shown to be turing-complete, but these constructions also rely on arbitrary precision 42 Recent works have also proven results for generating or recognizing formal languages with finite- saite-preciiio neural nets [58 29 24], but these results do not consider Turing machines or analyze statistical properties of their constructions. Concurrent work (33 proves Turing completeness of RNNs with finite precision, relying on a dynamically growing memory module in the architecture (which serves the same purpose as the long decoder sequences in our Transformer construction). However, they do not analyze statistical properties, which requires additional complications in both the construction and statistical analysis.
1.2 Notation
Let f o denote the composition of functions f and g. For a family of functions G, let (Jog:g 9) denote the family of compositions between f and functions in G. For set S SJ vector in d dimensions, with the subscripted omitted if clear. For ie [d], let ( denote the one-hot embedding in d-dimensions, which is 1 index and 0 everywhere else. We use the notation Ō()) to hide poly- -oyarrtgai factors in the argument. The notation S.z indicates the existence of a constant factor such that the inequality holds, and = denotes that the ž and & relations simultancously hold. We use p-ly(-) to indicate the existence of a polynomial in the argument which makes the equation true. For a set A (c.g., the of alphabet symbols for a Turing machine) A denote the set of all sequences of elements of A. where sequence length can vary. Let P denote a distribution over a space of inputs X. Let E., be n i.i.d. Rademacher variables sampled from 1-). The expected n-sample Rademacher complexity of F on P is as follows: Radn, (FF) (x)) 'eep [ EE....................... [suprer 1 F
and function f:SS- v let f(S) denote the set (f()): 8E S) e y. We use 1a to denote the all-one's
where (z.) ___ denotes i.i.d. samples from P.
2 Statistically meaningful approximation
We consider settings where we wish to approximate every member G in a real-valued function class G with some function F in function class F. Functions in both G and F map input space X' to R. In this work, F is some family of neural networks. Fix a loss l: C:R x R [0,1]. The classical notion of e-approximation 43 is as follows:
Definition 2.1 (Classical e-approximation), We say a function class F e-approximates a function class 9 with respect to loss and input distribution P. for any given Geg, there exists Fe F such that E (((F)))(((()))) e
3

---

The issue with this classical notion of approximation is that it allows solutions which use infinite preci- sion (or other potential unrealistic characteristics). Because of these drawbacks, even if J approximates 9, it does not mean that we can use F to fit the target function from G with good sample complexity.
This work studies a stronger notion of approximation, statistically meaningful (SM) approximation, to eliminate statistical issues with fitting G on finite sample. -aappooximatiion requires that G is learnable via empirical risk minimization using models from F, when data is generated from P.
Definition 2.2 (c-MM-aprrxximation) We say a function class F c-SM SMMapproximates a function class G with respect to evaluation loss & and input distribution P with sample complexity if there exists a surrogate loss E:Fx X x R- [0,1,] such that for any given Geg, the following holds:
With probability 0.99 over the randomness of examples (zx)i=1 drawn from P. the empirical risk minimizer of f, F argmin 15 n=i=1 (EE=)1(FFae ((FFF,,,((:))) approximates G:
Definition requires that the empirical risk minimizer of over F on a finite sample (I:)) guaranteed to e-approximate G on the population. Note that the surrogate loss & and evaluation loss f can differ, and that & takes the model F argument, allowing the empirical risk to include regularization.
Though Definition 2.2 may be reminiscent of PAC-learnability. there is major conceptual difference: SM approximation unifies expressivity and generalization, whereas PAC-Icarnability is only concerned with generalization. For example, in the realizable PAC-learning case, there is no notion of an approximating family F- the setting only cares about fundamental Icarnability of G. Furthermore. in agnostic PAC-learning (non-realizable) settings, the main focus is achieving a low loss relative to the best function in the hypothesis class. In contrast, SM approximation also requires proving that the best function in J achieves near-zero loss, whereas there no such requirement in PAC-learning settings.
2.1 Background and tools
To prove SM-approximation guarantees, Definition 2.2 requires loss surrogate such that the empirical risk minimizer of l on the training data can approximate functions in G. The following proposition, which is motivated by classical generalization theory, provides several conditions on i which lead to SM- approximation guarantees.
Proposition 2.3. For loss function E R x R - [0,1] and input distribution P, suppose there exists a surrogate loss e: x X x R- [0,1] satisfying the following properties:
1) For all FE R, ((F.x.y) ((F()).).
2) For any G G, consider the function class La + 1I- (()) Then the n-sample Rademacher complexity of LG is bounded: Rad,, ((C.) SC
3) For any GeG, there exists Fe Fith small surrogate loss: Ee.-
Then, the function class F O F0+ (T) -SM-upproximmatee G with respect to loss l and input distribution
P with sample complexity n.
By Proposition
suffices that l upper bounds the target loss and has low complexity, and F approximates with respect to (E, P) in the classical sense. The proof follows from standard techniques for bounding generalization based on Rademacher complexity and is provided in Section
2.3
All-layer margin loss. We introduce particular construction for used in subsequent sections, which is motivated by the all-r margin generalization bound proposed by (56). This bound based on data data-dependent Lipschitzness measures [3]
(5), and can provide stronger guarantees than classical
norm-based bounds (37 6 38 21
We focus on the binary classification setting, where G(z) E (0.1), and study approximation with respect x)) where yE (0,1) is assumed to be a binary label, and the aim is to output negative prediction for y 0 and positive for y 1. We consider a family of functions F parameterized by p-dimensional parameters 0 θ RP, such that F= {ar F(x,0) : where we abuse notation and let denote a general parameterized function F: x RP R. We sometimes use to identify element of F. Throughout the paper, we define θ as set with ||- n-norm bounded by
to the 0-1 loss 4..1 + (

---

[0]] <a, V. We define the parameter- barameter-based all all-layer margin Pp:RPx
x X'x (0.1) - - as follows:
(r(6,2.)) +min ||||
(2.1)
subject to F(r.5-
We omit F from the subscript of p when is clear from context. This quantity measures the stability of the model around an input in parameter space. As is the case for the standard output margin, larger all-layer margin, or better stability, tends to imply better generalization.
We modified the definition in [56] consider perturbations é in parameter space, whereas Wei and Ma [56] consider perturbations to the hidden layers. The parameter aarameter-space formulation is simpler and subsumes the results in [56]. Our formulation also accounts for weight sharing, which is important for our Turing machine results, whereas the formulation of [56] could not.
key and immediate property of the all-layer margin that is strictly positive if and only F(r,0) predicts the correct label. We can leverage this property to construct a surrogate loss. For some parameter y intended to lowerbound the all-layer margins, we define the loss &, as follows:
if ((0,z,))) 0
(0,0,,))
=
1 p(0,a.y) if0 (0,,,,))
(2.2)
O p(f
Note that E., composes the classical ramp loss, which is used to prove margin- based generalization complexity bounds, with the value of the all-layer margin. By our construction, it immediately follows that (0,x,, 3 fo (F(x,0).G(::)
is required of a surrogate loss.
We show that obtain sample complexity bounds for SM-approximation of & in classification setting, it suffices to prove that functions in F can fit labels of GE 9 with large all-layer margin. Our argument uses E as the loss surrogate in the definition of SM approximation. Though &, is computationally intractable to optimize, Wei and Ma [56] demonstrate that heuristically minimizing &, also leads to improved generalization empirically.
Lemma 2.4. Fix any paraneterizedduncee
F:Xx IR and define Fa (x- ((x.)))066)
where assume θ = IR is such that |10]] & a for O. Fix a O. Suppose that for all GE G, there
exists 0 E O such that the following holds:
Ex (())) <))
(2.3)
Then, F. E-SM-approxinates G with respect PP) with sample complexity Ö (ollog())
+1
Here Ô hides poly-logarithmic factors in the arguments, in this case, polylog( (log(p) 3-
factors. The proof follows (56) and is deferred Section A In Section A we also state generalization bound for 0-1 loss based on (). which may be of independent interest. We use (2.2) and Lemma
prove that neural nets can SM-approximate Boolean circuits and Turing machines.
3 SM approximation of Boolean circuits with feedforward nets
This section shows that feedforward neural nets can SM-approximate Boolean circuits with sample complexity that depends polynomially on the size of the circuit, boolean circuit G: (0.1)). m (0,1) on m inputs bits is described by a directed acyclic graph, with vertices of this graph referred to as "gates". The graph contains m input gates of indegree O. which are identified with the input bits. The remaining gates each compute a boolean function taking values their parents as arguments, and designated output gate produces the output of the entire circuit. We consider boolean circuits consisting of AND, OR, and NOT gates, which compute the corresponding boolean functions on and inputs, respectively and are sufficient to compute any boolean function (55) We also allow identity (ID) gates, which take input and output the same value.
We consider layered circuits, where we can partition the gates into layers such that the only edges in the graph occur from gates in layer i gates in layer i+1 for some Note that we can transform any boolean circuit into a layered one by adding ID gates. Letting denote the number of layers and the maximum number of gates in any layer, we say that the circuit has depth g and width r. We say
5

---

that circuit with total gates has size s. Our convention will be that the set of input gates is considered layer, so 3 m. We consider the following class of boolean circuits:
Go... (G:,0, (0.1): : computed by circuit with depth g, size s, and width r}
We will approximate Gqrr, using family of width w, depth d feedforward ReLU nets pa- rametcrized by linear weights and biases = (Wo, bo:
Wd, ba) computed as follows: (u. f) = Wa Wa<(Wa-10(-- o(Wox + bo) .n))) + ba-1) + ba. where all intermediate layers have width w for simplicity and o denotes the coordinate-wise ReLU activation. The weight parameters are set so that for 1 < i & d - L, W; E IR fuxx Wne R"x", and Wa E R x The bias parameters are such that b, E RR for 0 & i & d 1, and E R. To control the sample complexity, we restrict our attention parameters with total ||- -norm bounded by a, giving the following function class:
Fw,d,a (-- F 0) 0 <a}
The following theorem states that feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity polynomial in the circuit size.
Theorem 3.1. Consider the class g of size-s, s, width-r, and depth-q layered boolean circuits, and the class Fuddd of neural nets above. Suppose w Zr, a= and d== q.
Then, for all e and any input distribution P over (0.1)mm. Fu,d,a s-SM-approximates & with respect to PP) with sample complexity poly(s)ō
log(
We note that the bound in Theorem 3.1 onnly scales logarithmically in the width w of the network, even w is arbitrarily greater than the circuit width r. This ensures that even heavily overparameterized nets will have low sample complexity of the approximation.
2.2b is essential for proving tight sample complexity bounds, as other surrogate losses would give weaker For example, if we choose f0-1 as the surrogate loss, VC-dimension bounds (23) imply that Fu.d.o statistically meaningfully approximates Iyr. with sample complexity scaling in poly under the conditions Theorem 3.1 This suffers pollynoiil dependence on the overparameterized width w, which is not ideal for realistic settings, where neural nets are often wider than necessary to facilitate optimization. In contrast, our dependence on w is logarithmic. Another possible surrogate loss is the output margin- margin-based ramp loss, which can be used to prove norm-based sample complexities [6]. However, these bounds depend on | 1 W; op (or related quantities), which would be exponentially large in d for the naive construction in Section 3.1
For this setting, the all-layer margin loss in
3.1 Proof sketch for Theorem 3.1
There are two key steps in the proof. First, given any layered circuit Ge G, we construct a neural net that directly simulates G by computing the layers of G one-by-one, which is simple to do by directly constructing ReLU and linear layers to simulate the AND, OR, NOT, and ID gates.
Lemma 3.2. In the setting of Theorem 3.7 let G denote the layered boolean circuit, which we aim to compute using a neural net. Let g: (0,1) m 1 (0,1) denote function computed between the i- 1-th and i-th layers GG, which we assume have T;-1 and r gates, respectively, so G= 00--1....011
Then there exist functions f1..---a--1. where each fa is computed by a feedforward ReL.U net with two linear and activation layers, such that for all ie [q-1] and x (0.1 (0.1]mm, 1mm fio... fi (x) = g, o0000ggl (1))).
e
Thus, the composition F(--0)= fq-1 o...o. fi satisfies F(x,0)= = G(z) for all x E {0,1)*' 1 Note that we omitted the dependency of fq-1.....Ji on parameters A for simplicity.
Lower bounding all-layer margin. The next step for proving 3M-approximation is to construct a loss E so that the empirical risk minimizer of on the training data has good sample complexity. This crucially requires the all-layer margin tool developed in Section 2.1 as other complexity measures (e.g. based) would not give good sample complexity bounds.
Recall that the all-layer margin @r(0. xr, G(x)) measures the stability of the output F(x: 0) to perturbations in to 0. and, by Lemma 2.4, it suffices to show that F' has large all-layer margin on E (0. Unfortunately, we cannot guarantee that the naive construction from Lemma 3.2 has large layer margin without further modifications. To remedy this issue. Theorem D.6introduesss a generic way to convert the model F(-.0), with possibly small all-layer margin on a [0,1] m into a new architecture and parameter set F' (-,0",, with provably large all-layer margin on ZE (0,1) such that F' F'(())))) = F (zx.0) on all inputs z E {0.1)m The construction relies on introducing new layers to F to obtain F' and increases the total number of layers by only a constant factor. This step of the proof is formally stated in the following lemma.

---

be the neural net with parameters O constructed to compule the circuit G. There exist "correction computed by neural nel with two activation and linear layers, such that the composition F'(-,") fq-1 2 10--2--00000 o0. o f1 has large all-layer margin: pr (0', x2 (z,)(())= 30 polyle] for all ZE (0,1)"² Here 0' denotes the collection of all parameters, and dependency of ficSa on Of is omitted for simplicity.
Lemma 3.3. In the setting of Lemma 3.2
let "Correctionfunction"" functions" 51,----S--2. where Çi is
We convey the core intuitions for Lemma 3.3 in a simplified toy setting as follows. Consider the 0.5,
case where we start with an initial architecture ff computing (x..(1...... (W1....Waa) = (TT² W. -005 where W; E R. In this simplified setting, we consider W. = Vi. For input = and target y= 1, the all-layer margin is small: (,((I,...,)) 1),1,1) & va where the architecture is in the subscript. Indeed, choosing 6; = 3. we have f(1,(1 - 3 2...,, 1-...,,-1 -1- 9 d 0.5 = exp( - 0 Thus, by the definition of all-layer margin, (f(((..... &
Now will insert ReLU layers in increase the all-layer margin ((1). We use ReLU layers to implement the round function, which has the key property that round 2)) = 1V2 2/3.
0
if=<1/3
Proposition 3.4. For any ee R. we can implement the function roun()) 2)
3z 3z-1
22//3
1
if
via a feedforward ReLU net, as follows: round z) = =30(== 10//2--113--1/01 2/3).
We consider the following function J. which inserts round between every layer f:
f(x.(W.....WWa) = rounnd (oadddaW---oo
(3.1)
For this demonstration, we ignore the parameters of round, though the actual proof considers them. The following claim shows that (3.1) preserves the output of f while increasing the all all-layer margin:
Claim 3.5. In the setting above, f(1.(I......))) ((,, (()) and pf((L.....),I,I1))
This reflects a significant increase in the all-layer margin, while only increasing depth by a constant factor. The proof is simple: we observe that if ó; & 3 for all i, the function output will not change because round(2) = 1 3. This immediately gives the all-layer margin lower bound 3.
To apply this construction more generally, we note that round corrects errors in previous layers. In the more general setting, we insert "correction functions" between each layer satisfying the key property that {(h') = if h is the intended output of the layer and h is any perturbed value satisfying 14' 1 & - Since intended outputs of layers in the function constructed by Lemma 3.2 binary-valued in (0.1) because F simulates boolean cireuit, we can simply apply the function round constructed in Proposition elemmntwise as the correction function. By the construction, this can be implemented by adding two additional feedforward ReLU layers per correction function.
Following the intuition for Claim 3.5 we prove that inserting these correction functions guarantees a large all-layer margin (Theorem D.6 on all re {0.1)mm. This leads to the proof of Lemma 3.3 We
can complete the proof of Theorem 3.1 by invoking Lemma 2.4 as shown in Section B
4 SM approximation of Turing machines with transformers
In this section, we show that transformers -M-approximate Turing machines with computation time bounded by T, using sample complexity polynomial in log(T) and the state space and alphabet sizes of the Turing machine. Constructions from prior work would require the approximation sample complexity to be linear 7 48 12 42 9. Thus, we obtain an exponential improvement the dependency on T.
We briefly describe a Turing machine; see [49] for a more thorough survey. A Turing machine is a model for computation specified by tuple 22 S,
containing set of states 2, a tape alphabet Ax x [-1,+1}, and set of terminal states Zeem indicating accept or reject. For simplicity, we assume the Turing machine has a single tape, as any single-tape Turing machine can simulate a multi-tape one with only quadratic increase in runtime [49]. Given an input .E * recorded on the left-most part of the tape, the Turing machine performs computation in a sequence of timesteps. In each timestep, the machine determines the next state, symbol to write, and direction to move the head via the transition function.
A. transition function : Z A
7

---

We let (Z..A. Zumm denote the function computed by the Turing machine, which produces an output in {0,1] (if the machine halts), Fixing the alphabet A, we consider the class of binary functions computed by Turing machines with at most & states terminating in I steps:
GR.T = {-- (2,2... (T): 2 & k, and V X, TM 2 A,S. 2mm) terminates in T steps) } (4.1)
Note that we can assume the input sequences x also have length at most T, as this is the maximum com- putation time of the Turing machine and the maximum amount of symbols the Turing machine can read.
4.1 Transformer architecture for SM-appoxximating Turing machines
We study approximation of G with a family of architectures consisting of both an encoder and decoder component [53], described as follows. The encoder architecture simple and only performs an embed- ding of the input symbols, using learnable symbol embeddings Ee R x (Al and fixed positional encod- R Given input x A with m symbols, the encoder produces m output vectors in R" via Enc,(x,E)) E.,,, + B(t), where Enc; denotes the output of the encoder at the i-th position.
ings
The decoder iteratively computes an output, running for T steps. We define a transformer layer of the decoder as sequence of modules consisting decoder self-attention, followed by encoder-decoder attention, followed by three feedforward ReLU layers.
Attention layers. Attention layers consist of key, value, and query functions K,V.Q, each, computing linear transformation. We omit parameters here for simplicity. For single decoder timestep, the attention layer takes two types of inputs: a sequence of previously-computed representations hi,...,h, and current imput representation h'. The layer applies the key, value, and query functions follows:
To Q(h)) (o)) T ((h))....QQ(1))) K(he)
Up,01 ....,, Vo, (b)))
where Ky and Vú are fixed "null" key and value vectors which are learned parameters of the layer. Letting I denote the set of indices (]: max the attention layer performs hard-mas -mx attention [2) to compute the output, as follows: Attn(h',(h1,..... (h:).....:)) = 11' [ Ee.
Our theory also applies to the standard softmax attention used in practice, but we focus on the hard-max case for a simpler proof. Let I,,") denote the representation computed by the j-th layer of the decoder at timestep t. At timestep i, decoder self-attention at the (j + 1)-th layer computes Attn(h (,,"), [(h()) ,....!(")) (I(")....??())
Letting Cm denote the encoder outputs, encoder- self-attention at the 1j+1)-th layer and i-th step would compute Attn( h1 ((11...,fm))
Transformer layers, We use feedforward layers which apply 3 standard ReLU layers, as follows: FF(h)= = o( 3(330(W (W and the architecture here chosen mainly to simplify the construction.
b2) +b)). Our theory also allows for residual feedforward layers,
transformer layer applies these constructions in sequence. Letting H.") = (n( (..,,.")))) denote
the output after the j-th transformer layer for timesteps 1 & i, and (15) the parameters, we compute
h (1+1,de)) Attn(h (1) (H((') g0 1. 100+1. dec-armi))
n (++1,em)) Attn(h Attm(h++1,dde (+1,de)))
((11,...,Cm) ).0mmm)mmm .0 1.0+I. l.en--atti)
Tr(n (e""),H((..).....)))) (e1,....mm))0000 (F(+))))=((((+1eeem) (et))(((+t.mm))0--....
Note that we included the explicit dependence of the attention layers on the parameters for completeness. We now set A (++1) ( =Tr(h .H!")) (m0)))))))))
Decoder outputs. We consider d- lalyyer decoders, soo; ((0)) denotes the output of the decoder at time i, which is also inputted to the decoder at time i+ 1 as follows: (1 | (( (d) + 1). The initial decoder input / (0) is a trainable parameter. The decoder runs for a fixed number of timesteps T' and outputs pre- diction 0T 1 For simplicity, we assume T T, the computation time of the Turing machine family.
Note that our architecture allows long (length 7') decoding sequences, whereas typical architectures in practice use decoding sequences with roughly the same length as the input [53] The architecture we study is similar to ones studied by 42 9
8

---

We use - (u, 8) to denote the described transformer architecture with parameters 6, w-dimensional hidden layers, d transformer layers in the decoder, and T decoder steps. This leads to the following class of transformer functions: Fu.dda.7= = {2- F Fw.d.r(z.0) ([0] 1 E a). The following theorem states that this class of transformers SM-approximates the Turing machine family g defined in (4.1) with sample complexity polynomial in logT,, k and |A].
Theorem 4.1. In the setting above, consider the class 9 of functions computed by Turing machines with at most le states, alphabet A, and computation time bounded by T steps for inputs xe X. Suppose that w ž k|A] +logI, d=looT,, and a= poly [k. (.llAA,,oo))).
Then,for for all c> 0 and any input distribution P over X, F... -S-aapproximatts 9 with respect log(wd)
(Po. with sample complexity poly(k:||A|.ooo]])
As with Section 3 we set the surrogate loss l in Definition to to be the all-layer margin loss defined alternatives for the surrogate loss would not suffice for either our construction or ones in prior work [48] 12, 42 [9] First, the VC dimension of F aw.d.a.7 T is at least D(wT). This is because transformer architectures which contain decoder component can express RNNs, which by lower bounds have VC dimension at least wT (28). This indicates that using 4a-1 as the surrogate loss would lead to sample complexities that are suboptimal in both the overparameterized width and the computation T. Second, the correct norm-based Rademacher complexity bound to use for transformers is unclear; however, the RNN-based equivalent would scale with the T -tth power of some parameter norm, or exponentially in T. Thus, as in Section 3 the all-layer margin surrogate is essential for obtaining our sample complexity bounds.
in Section 2.T Commonly-use
loss 2.2
4.2 Proof sketch for Theorem
Following Lemma 2.4 our goal is to construct transformer which can simulate Turing machines with large all-layer margin, namely, ? [oly( The fundamental limitation of prior work 42 towards attaining this is that the positional embeddings are required to store values as small as pT Our construction cannot afford to rely on values this small - informally, if the construction relies on the exact values of these small entries, then the all layer margin would be at most [T] because perturbing the layer by the small entries could change the prediction. Instead, we propose using (in the binary encoding of i in [logT]] bits, as the positional encoding for timestep i. This allows us to use unique positional encodings for each timestep which do not rely on arbitrary precision.
1
We describe the construction. Fix Turing machine Ge G. We first require notation to describe the computation G. For input r X' let (xx), a, (z(z)) denote the Turing machine state and symbol under the tape head at the end of step i. We let (z(x denote the location of the Turing machine head at the conclusion of step i. During the timestep, the Turing machine computes S(2 .a;-1 (x)), writes new symbol under the head at location 4;- 1 (zr), and moves the head either left or right. Let (x( denote the symbol written during timestep i, and q: E (left,right) the movement direction of the head.
Following 42 with several key modifications, we simulate the Turing machine using the transformer as follows. Each timestep will maintain the invariance that o contains an encoding of (z)).. and (xx). Given that this invariance holds until timestep i, the transformer simulates timestep i+ of the Turing machine with the following steps:
1) Use feedforward layers to apply transition S on (z) and (x()), which can be read from O,, to obtain zi+1 (x)) (1)) and movement direction (z+1(z) e (left, right).
2) Using feedforward layers, compute 4+1 from q++ (1) and the encoding of (x) in o,
3) Compute (z). We use decoder self-
search over past timesteps which wrote to 444 (I)) Our aim is to find (z)( where i' = max(, & i+ 1: 1-1-11 (x) = l (z)]. We implement binary search over past timesteps j. which is needed to find the largest j & i+ where (x)) = 444(2)), The binary search performed over the bits of i' and can be implemented with O O(logT decoder self-attention layers, and the construction ensures large all-layer margin.
4) If no such i' from the previous timestep existed, we check whether 4+ (2) (z) contained an input symbol using incode-ddcoode attention and copy this input symbol if so.
5) If no symbols were found in 3) or 4), 4+1(x) must contain the blank symbol (meaning it wasn't visited yet by the head). Thus, we have computed a++1 (I), so we have all the information needed to compute the new embedding 0,+1-
9

---

To lower bound the all-layer margin of the constructed transformer, we use Theorem D.6 which requires existence of "correction function" which can correct outputs in previous layers. Since construct a network with intermediate layer entries in {0,1}. we can use the same correction function as Section 3.1 which rounds to the nearest bit. The full proof is provided in Section C
Conclusion
This work proposes new definition of approximation, statistically meaningful approximation, which ensures that the approximating family not only has sufficient expressivity, but also exhibits good statistical learnability. Towards first analysis with this definition, we show approximability function classes: boolean circuits and Turing machines, with strong sample complexity guarantees depending only on the intrinsic properties of these function classes. There are several interesting directions to extend our study of statistically meaningful approximation, Examples include proving more upper and lower bounds for statistically meaningful approximation for different target functions and neural architectures, and using our definition as lens compare architectures.
two
Limitations
One potential limitation that the "correction function" machinery discussed in Lemma relies the discrete nature of boolean circuits and Turing machines, and so additional work and insight would be required to prove analogous -M-approximation results for continuous functions. One important property of discrete functions, which we suspect may be leveraged more generally, is that it easy to correct errors in intermediate computations discrete functions (by rounding). It would be interesting to see whether this property has a continuous analog which can be analyzed.
Acknowledgements
CW was supported by a NSF Graduate Research Fellowship. YC is supported by Stanford Graduate Fellowship and NSF IIS 2045685. TM acknowledges support of Google Faculty Award, NSF IIS 2045685, and JD.com.
References
[1] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and system sciences, 58(1):137-147, 1999.
[2] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv: 1..00491, 2016.
[3] C. Bao, Q. Li, Z. Shen, C. Tai, L. Wu, and X. Xiang. Approximation analysis of convolutional neural networks. work, 65, 2014.
[4] A. Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930-94) 1993.
[5] P. Bartlett. For valid generalization the size of the weights is more important than the size of the network. Advances in neural information processing systems, 9, 1996.
[6] P. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normalizer margin bounds for neural networks. arXiv preprint arXiv: 1706. 08498, 2017.
[7] P. L. Bartlett, N. Harvey, C. Liaw, and A. Mchrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20 ):2285 22001, 2019.
[8] Y. Bengio and O. Delalleau. On the expressive power of deep architectures. In International conference on algorithmic learning theory, pages 18-36. Springer, 2011.
[9] S. Bhattamishra, A. Patel, and N. Goyal. On the computational power of transform- and its implications in sequence modeling. In Proceedings of the 24th Conference on Computational Natural Language Learning, pages 455-475, Online, Nov. 2020. Association for Computational Linguistics. doi: 10. 10011665//1122220.mmm111333 https://www.acll acwweb. org/ anthalagyyy.a/aeaaaaaaa 2020 http:/222222.11.....1 con1l-1.37
URL
[10] V. Chatziafratis, S. G. Nagarajan, I. Panageas, and X. Wang. Depth-width trade-offs for relu networks via sharkovsky's theorem. arXiv preprint arXiv:1912.04378 2019.
10

---

[11] V. Chatziafratis, S. G. Nagarajan, and I. Panageas. Better depth-width trade-offs for neural networks through the lens of dynamical systems. In International Conference on Machine Learning. pages
PMLR, 2020.
[12] Y. Chen, S. Gilroy, A. Maletti, J. May, and K. Knight. Recurrent neural networks weighted language recognizers. In NAACL-HILT, 2018.
[13] S. Chung and H. Siegelmann. Turing completeness of
recurrent neural
networks. Advances in Neural Information Processing Systems, 34, 2021.
[14] N. Cohen and A. Shashua. Convolutional rectifier networks as generalized tensor decompositions. In International Conference on Machine Learning, pages 955-963. PMI.R, 2016.
[15] N. Cohen, O. Sharir, and A. Shashua. On the expressive power of deep learning: A tensor analysis. In Conference on learning theory. pages 698-728. PMLR, 2016.
[16] G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 244):303-314, 1989.
[17] A. Daniely. Depth separation for neural networks. In S. Kale and O. Shamir, edi- tors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceed- ings of Machine Learning Research, pages 690-696. PMLR, 07-10 Jul 2017. URL http://proceedingg
mlr. www.r.pres///ee v65 htd//ddneelyy..a.li html
[18] S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over- parameterized neural networks, arXiv preprint
2018.
[19] R. Eldan and O. Shamir. The power of depth for feedforward neural networks. In Conference on learning theory. pages 907-940. PMLR, 2016.
[20] B. Ghorbani, S. Mei, Misiakiewicz, and A. Montanari. Limitations of lazy training of two-layers neural network. In Advances in Neural Information Processing Systems, pages 9 9108-9118 2019,
[21] N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theorr, pages 297-299. PMLR, 2018.
[22] M. Hardt and T. Ma. Identity matters in deep learning. arXiv preprint arXiv::611.0000 2016.
[23] N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tight ve- ve-dimension bounds for piecewise linear neural networks. In Conference on Learning Theory, pages 1064-1066 1068. PMLR, 2017.
[24] J. Hewitt, M. Hahn, S. Ganguli, P. Liang, and C. D. Manning. Runs can generate bounded hierarchical languages with optimal memory. arXiv preprint arXiv:2010.07515, 2020.
[25] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366) 1989.
[26] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018.
[27] Z. Ji. M. Telgarsky, and R. Xian. Neural tangent kernels, transportation mappings, and apiversal approximation. In International Conference Learning Representations, 2020. URL
https://openreeiee: www.:eeetfouuieeeeeo Horum2id- Q
[28] P. Koiran and E. D. Sontag, Vapnik-chervonenkis dimension of recurrent neural networks. Discrete Applied Mathematics, 86(1):63-79, 1998.
[29] S. A. Korsky and R. C. Berwick. On the computational power of rnns. arXiv preprint arXiv:1906.c 00090 2019.
[30] H. Lee, R. Ge, T. Ma, A. Risteski, and S. Arora. On the ability of neural nets to express distributions. In S. Kale and Shamir, editors, Proceedings of the 2017 Conference Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1271-1296. PMLR, 07-10 Jul 2017.
www.prees/v//eeee7a..... htt.edddnng......peeess/////eeea html
[31] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):
861-867, 1993.
[32] H. Lin and S. Jegelka. Resnet with one-neuron hidden layers is universal approximator. arXiv preprint arXiv: 1806 2018.
[33] T. Ma. Why do local methods solve nonconvex problems? Beyond the Worst-Case Analysis of Algorithms, page 465, 2020.
[34] E. Malach, G. Yehudai, S. Shalev-Shwartz, and O. Shamir. The connection between approxima-
tion, depth separation and lcarnability in neural networks. arXiv preprint 0210002000002200000444300000000
11

---

[35] S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view of the landscape of two-layers neural networks. Proceedings of the National Academy of Sciences, pages E7665-E7671, 2018.
[36] V. Nagarajan and J. Z. Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arxiv: 2019,
[37] B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks.
In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
[38) B. Neyshabur, S. Bhojanapalli,, and N. Srebro. A pac-hayesian approach to spectrally-normalized margin bounds for neural networks. arXiv preprint 1rxXiv:707..000 1707009644, 2017.
[39] Q. Nguyen and M. Hein. Optimization landscape and expressivity of deep cnns. In International conference on machine learning, pages 3730-3739, 373...9RR 2018
[40] J. Park and I. W. Sandberg. Universal approximation using madia-bbaiisffnctte networks. Neural computation. 3(2):246227,, 1991.
[41] S. Park, J. Lee, C. Yun, and J. Shin. Provable memorization via deep neural networks using sub- sub-linear parameters. arXiv preprint arXiv:2010..3363 2020.
[42] J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv: /01./999...9922.. 2019.
[43] M.J. D. Powell et al. Approximation theory and methods. Cambridge university press, 1981.
[44] A. Sannai, Y. Takai, and M. Cordonnier. Universal approximations of permutation invari- ant/equivariant functions by deep neural networks. arXiv preprint arXiv: 1903.0/93,, 2019.
[45] J. Savage. Models of computation exploring the power of computing. 1998.
[46] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. Computational capa- bilities of graph neural networks. IEEE Transactions on Neural Networks, 20(1):81-100 2008.
[47] A. M. Schäfer and H.-G. Zimmermann. Recurrent neural networks are universal approximators. International journal of neural systems, 17(04))253-266 2007.
[48] H. T. Siegelmann and E. D. Sontag. On the computational power of neural nets. Journal of computer and system sciences, (00()))332115):) 1995.
[49] M. Sipser. Introduction to the Theory of Computation. Course Technology, Boston, MA, third edition, 2013. ISBN 133118779X.
[50] M. Telgarsky. benefits of depth in neural networks. In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1537- Columbia University, New York, New York, USA. 23 Jun 2016. PMLR.
mlr wwwpppppseseeeeeeeeepee v49/ wttpe/////////lllleeeeeeeeeeee/ gerlgyryrylleee httmml html
[51] T. Teshima, K. Tojo, M. Ikeda, Ishikawa, and K. Oono. Universal approximation property of neural ordinary differential equations. arXiv preprint arXiv:20/2.022114 2020.
[52] G. Vardi and O. Shamir. Neural networks with small weights and depth-separation barriers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14433-19443 Curran As- sociates, Inc., 2020. URL httpps:/ppooceddiie .pff
neurips weerips.cc/ppate wwtpppppppp//2///1eee.e.e
[53] A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L. Jones, N. Gomez, L. Kaiser, and
I. Polosukhin. Attention is all you need. arXiv preprint arXiv: 03762, 2017.
[54] R. Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint arXii:2001.0699. 2020.
[55] C. Wei and T. Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. arXiv preprint arXiv: 03684, 2019."
[56] C. Wei and T. Ma. Improved sample complexities for deep networks and robust classification via an lll-r margin. arXiv preprint arXiv: 140.024990004224,. 2019.
[57] C. Wei, J. D. Lee, Q. Liu, and T. Ma. Regularization matters: Generalization and optimization of
neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
[58] G. Weiss, Y. Goldberg, and E. Yahav. On the practical computational power of finite precision mns for language recognition. arXiv preprint / 089000 2018.
[59] D. Yarotsky. Universal approximations of invariant maps by neural networks. Constructive Approximation, pages 1-68.
12

---

[60] C. Yun, S. Sra, and A. Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. arXiv preprini 1rXiv:1810.0777: 2018.
[61] C. Yun, S. Bhojanapalli, A. S. Rawat, S. J. Reddi, and S. Kumar. Are transformers universal approximators of sequencc-----sequeeee functions? arXiv preprint arXiv: 1et.: 2019.
[62] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1.03530, 2016.
[63] H. Zhang. X. Gao, J. Unterman, and T. Arodz. Approximation capabilities of neural odes and invertible residual networks. In International Conference on Machine Learning, pages
1 11086-1 1095. PMLR, 2020.
[64] D.-X. Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 4882)7777779, 2020.
13


Reviews:
[{"review_id": "m5eLf0au2J4", "reviewer": "Reviewer_i8t1", "summary": "This paper studies the approximation power of neural networks under the constraint of finite-precision weights and activations. Many classical results touting the expressive power of neural networks have a strong reliance on infinite precision weights and activations whereas the more practical finite-precision networks are nearly not as expressive. \n\nIn this paper, authors propose a different take on how one should evaluate expressivity. Instead of focusing on whether a target function can be expressed by the class of neural networks in question, one should focus on the statistical properties exhibited by the class. To that effect, authors propose the notion of statistically meaningful (SM) approximation which looks at how well ERM can approximate a given function.   \n\nUnder this notion of approximation, authors first show  that neural networks can approximate boolean circuits where the sample complexity only depends on the polynomial of the circuit size and only have a logarithmic dependence on the parameters of the neural network. Secondly, authors show that that with the transformers can approximate turning machine that run for at most $T$ steps.\n\nThe main technical contribution of this paper is the proof technique used by the authors to derive the approximation results. \n\nThe first main contribution is the all-layer margin loss that allows one to reason about finite precision weights. \n\nSecond contribution is Lemma 2.4 that, at a high level, says that for any $G\\in \\mathcal{G}$ one can find a function $F$ in the approximating class $\\mathcal{F}$ with large all-layer margin approximates , then the $\\mathcal{F}$  $\\epsilon$-SM approximates $\\mathcal{G}$ with sample complexity depends on the margin and on $\\log$ of the number of parameters.\n\nAs a high-level proof technique for both boolean circuits and Turing machines, authors first showed by construction a neural network that approximate a given boolean circuit/Turning machine. To get the appropriate sample complexity result, the approximating function needs large margin. To get large margin, authors introduce “correction” functions that needs to be added to the constructed neural network. Due to the discrete nature of operations in both TM and boolean circuits, the correction functions are implemented by $\\text{round}$ operations.", "questions": "I am not entirely sure how the reading operation at location $l_i(x)$ is achieved. How can one binary search over the past steps when the $l_j(x)$ for $j\\leq i$ are not sorted? ", "limitations": "Authors have addressed limitations of their work. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- This is a well motivated paper that studies the expressivity of neural networks from a statistical lens.\n- To the best of my knowledge, the technique proposed in the paper is novel and the ideas are original which can be applied to study approximation power of different neural network architecture.\n- Lemma 2.4 also has implications for studying generalization properties of neural networks where all-layer margin loss depends on $\\ell_2$ stability of the neural network.\n\n**Weaknesses:**\n\n- The construction of self-attention network to simulate Turing machine is a bit hard to follow from the body of the paper. It’s still not clear to me how the reading at location $l_i$ is achieved by the transformers.\n- As far as I understand, authors are able to construct correction functions due to the discrete nature of boolean circuits and TM. Constructing for other class of functions is probably more challenging thus it’ll be difficult to adapt this proof technique.", "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": "YzLvzsv5bao", "reviewer": "Reviewer_FoEE", "summary": "This paper presents an alternative to expressivity (which is muddied by issues like unbounded precision), SM-approximation, which combines both expressivity and generalization. It then shows that FFNNs SM-approximate Boolean circuits and Transformers SM-approximate bounded-time Turing machines.\n\n", "questions": "lines 145-149. I was troubled by the appearance of the number 0.99 in a formal definition. Would there be any negative consequence of using 1-\\delta instead?\n\nline 186: How hard is it to compute \\rho_F? What would the implications be if it were very hard?\n", "limitations": "I did not see an explicit discussion of weaknesses.\n\nThere isn't a statement about potential negative societal impact, and I don't think one is needed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThe new definition of SM-approximation is reasonable. I think the paper makes a good case for considering expressivity and generalization together.\n\n# Weaknesses\n\nThere are no negative results, e.g., “function class \\mathcal{G} is not SM-approximable by FFNNs,” or \"if function class \\mathclass{G} has (some property), it is not SM-approximable by FFNNs.\" To me such results would be equally interesting, if not more interesting. This is mentioned in the future work section, but I don't have a good sense for how difficult it would be to obtain such results. I don't consider lack of such results a weakness in this paper, but if the definition of SM-approximation made it infeasible to obtain such results, I'd consider that a major weakness of the definition.\n\n# Minor Comments\n\nlines 133-159. Please state that functions in \\mathcal{F}, \\mathcal{G} are from \\mathcal{X} to \\mathbb{R}.\n\nline 186: \\min_\\delta\n\nline 326-265. There are a number of assumptions made about the Transformer, most of which are very mild.\n\nThe paper claims that the following could be dispensed with in favor of standard Transformers:\n- hardmax attention (distributing attention equally among ties)\n- no residual connections\n\nThe paper makes no claim about:\n- positional encodings are binary representation of integer position\n- no layer normalization\n- FFNNs have 3 layers and the last one also has a ReLU\n\nThe only important fact is:\n- the number of layers is O(log T)\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": "Q1BEzBEofoQ", "reviewer": "Reviewer_k6X3", "summary": "The paper introduces the novel notion of statistically meaningful approximation, which requires that a function family can be approximated with high probability based on the empirical risk minimizer obtained from $n$ samples. This notion combines both approximation and generalization and does not allow for infinite precision (as used by prior work), which can inflate the expressivity of an architecture. The paper demonstrates that feedforward neural networks can statistically meaningfully approximate boolean circuits and that transformers can statistically meaningfully approximate Turing machines.", "questions": "Are the sequences in $\\mathcal{A}^\\ast$ on line 127 of finite length?", "limitations": "The paper does not address limitations or potential negative societal impacts.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe paper introduces a novel notion of approximation and generalization for neural networks, which can potentially open up a fruitful line of future research. Indeed, the paper shows that this notion of statistically meaningful approximation allows for improved bounds over prior work for approximating boolean circuits with feedforward neural networks and for approximating bounded-time Turing machines with transformers. Concretely, the paper improves the sample complexity from exponential depth scaling and polynomial parameter scaling to scaling in the circuit size for the approximation of boolean circuits. Similarly, the paper presents an exponential scaling improvement for approximation of Turing machines with bounded computation time $T$ (sample complexity polynomial in $\\log T$ instead of $T$). Importantly, statistically meaningful approximation does not allow for infinite precision, which is known to inflate the expressivity of neural network architectures. Finally, the paper is very well-written and well-placed in the literature.\n\n**Weaknesses**\n\nThe definition of the 0-1 loss on line 181 is incorrect. Consider, e.g., $y = z = 0$, which corresponds to a loss of $0$ but yields $\\mathbb{1}((0 - 0.5)0 \\leq 0) = \\mathbb{1}(0 \\leq 0) = 1$. Similarly, the definition of the all-layer margin is incorrect (e.g., $y = 0$ and $F(x, \\theta) = 0$ yields $\\rho = 0$, which is not strictly positive). Since all other proofs in the paper hinge on this definition, I do not know whether they are also incorrect.\n\n\nI am happy to increase my score if the above concerns are addressed.\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": "4j82CjhKks", "reviewer": "Reviewer_AqPm", "summary": "This paper introduces a notion of statistical meaningful approximation and applies it to studying how NN models can approximate Boolean circuit and Turing Machines. One aspect of their definition is using two families of functions: One family F (e.g., NN) approximating a second family (e.g., Turing machines). Various generalization bounds are given with respect to this new notion. ", "questions": "\"finite width RNNs with infinite precision can simulate Turing machines,\nbut finite-precision, finite-width RNNs cannot, as implied by streaming lower bounds\"\n\nCan you prove this statement of back it up with a paper proving it?", "limitations": "With many parts of the paper the feeling is that authors are using sub optimal phrasing and references. \n\"Unfortunately, a rigorous analysis of optimization is unresolved even for simple two-layer nets\"\nThe reference for this is very strange. There are many much more relevant works I would cite. \n\nThe discussion of infinite precision also does not mention the large body of work dealing with weight-restricted NN as well \nas results showing how to avoid large weights by increasing depth. And there are more such examples. I would probably cite\n\"For valid generalization the size of the weights is more important than the size of the network\"\n\nThere are many other improvements: for example replace \"boolean\" by Boolean. I recommend a though pass improving the language and the presentation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Long story short I find this paper to be weak accept: I support acceptance provided the authors can demonstrate they can deal with the (many) issues in this paper. \n\nI'm less convinced by the SM definition. To me it feels similar to other notions of learnability and also the choice of a specific loss function as opposed to a family of loss functions (which seems to be necessary for the definition to go through) is another disadvantage. \nRather, the strength of the paper is in the simulation results of Turing machines and Boolean circuit by NN models. These simulation results are needed and could find multiple uses.", "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