Year: 2021

Abstract:
A common lens to theoretically study neural net architectures is to analyze the functions they can approximate. However, constructions from approximation theory may be unrealistic and therefore less meaningful. For example, a common unrealistic trick is to encode target function values using infinite precision. To address these issues, this work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: boolean circuits and Turing machines. We show that overparameterized feedforward neural nets can SM approximate boolean circuits with sample complexity depending only polynomially on the circuit size, not the size of the network. In addition, we show that transformers can SM approximate Turing machines with computation time bounded by T with sample complexity polynomial in the alphabet size, state space size, and logpTq. We also introduce new tools for analyzing generalization which provide much tighter sample complexities than the typical VC-dimension or norm-based bounds, which may be of independent interest.

heading: 1 INTRODUCTION
text: Dating back to the seminal works on universal approximation (Cybenko, 1989; Hornik et al., 1989; Park & Sandberg, 1991; Leshno et al., 1993), a common way to 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 a number of analyses studying universal approximation capabilities for various widely-used architectures, such as recurrent neural nets (RNNs) (Schäfer & Zimmermann, 2007), graph neural nets (Scarselli et al., 2008), convolutional networks (Bao et al., 2014; Zhou, 2020; Yarotsky, 2021), residual networks (Lin & Jegelka, 2018), transformers (Yun et al., 2019), and neural ODEs (Teshima et al., 2020; Zhang et al., 2020).
However, approximation theoretic results often misalign with more meaningful end-to-end guarantees, because models constructed in the literature often exhibit unrealistic properties. For example, a common technique in the universal approximation literature is to rely strongly on infinite-precision weights and activations, or exponentially many parameters to encode the desired function values (Hornik et al., 1989; Cybenko, 1989; Leshno et al., 1993; Lin & Jegelka, 2018; Yun et al., 2019; Sannai et al., 2019). 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 on arbitrary precision (Siegelmann & Sontag, 1995; Pérez et al., 2019; Korsky & Berwick, 2019; Bhattamishra et al., 2020). Infinite precision can inflate the expressivity of an architecture 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, as implied by streaming lower bounds (Alon et al., 1999). As another example, Park et al. (2020) exploit infinite precision in the parameters to show that a neural net with parameter count sublinear in n can memorize n arbitrary input-label pairs. However, a simple counting argument reveals that this result cannot be proven using finite precision networks – there are 2n input-labeling pairs, but only 2opnq finite precision networks with opnq parameters. More broadly, the ideal theoretical perspective should consider not only whether target functions can be expressed, but also whether the constructed networks are plausibly learnable. Learnability is important because empirical settings do not operate in the infinite data, unbounded computation regime – they require fitting the target function with access to limited number of samples from an empirical distribution. The question of studying learnability can be decomposed into studying optimization and generalization.
Unfortunately, a rigorous analysis of optimization is unresolved even for simple two-layer nets (Mei et al., 2018). Generalization is more tractable, so we propose to study expressivity and generalization together.
Towards the goal of studying more meaningful notions of approximation, this work proposes the notion of statistically meaningful (SM) approximation. This definition requires not only the existence of an approximating network, but also that it has good statistical learnability. Consider a setting where the aim is to fit the target functionG using the approximating family F and a finite sample of training data. SM approximation requires existence of a loss whose empirical risk minimizer in F leads to a model with low approximation error in fittingG. We define the sample complexity of the approximation as the number of training samples needed to guarantee at most approximation error and study SM approximation with low sample complexity bounds. SM approximation essentially eliminates all statistical concerns for learnability (optimization-related 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 a low sample complexity that depends only on the intrinsic circuit size. Though it is 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 (Bartlett et al., 2017). Furthermore, VC dimension-based bounds would scale polynomially in the number of parameters in the network (Harvey et al., 2017), which is problematic because for practical optimization concerns, neural nets are typically overparameterized in terms of width (Zhang et al., 2016). 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 a class of Turing machines with bounded computation time T and construct encoder-decoder-based transformers (Vaswani et al., 2017) 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 (Siegelmann & Sontag, 1995; Pérez et al., 2019; Bhattamishra et al., 2020) have not been formally studied from a sample complexity perspective, existing bounds would depend at least linearly on T . Furthermore, our construction only uses loglogT precision, compared to at least logT in prior works, allowing us to achieve the exponential improvement in the sample complexity.
Proving sample complexity guarantees for our statistically meaningful approximation results is nontrivial and requires additional insights, for both the constructions and the generalization analyses. To obtain our sample complexity bounds, we leverage a recent approach to bound generalization in terms of data-dependent notions of Lipschitzness (Wei & Ma, 2019b). 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 contributions are: 1) we propose a new notion of statistically meaningful approximation, intended to provide more meaningful approximation guarantees by requiring that the approximating family have good statistical learnability; 2) 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 3) we show that transformers can meaningfully approximate Turing machines with sample complexity logarithmic in the computation time.

heading: 1.1 RELATED WORKS
text: Classifical approximation theory for neural networks has a long history. Hornik et al. (1989); Cybenko (1989), and Leshno et al. (1993) show that neural nets with one hidden layer are universal approximators but require the hidden layer size to grow exponentially in input dimension. Barron (1993) uses the Fourier transform to write target functions as infinite-width networks and subsamples neurons to obtain widths which depend only on target function properties. Lee et al. (2017); Ji et al. (2020) prove recent related developments in this direction of universal approximation.
Many works study benefits of deep networks over shallow ones (Bengio & Delalleau, 2011; Arora et al., 2016; Telgarsky, 2016; Eldan & Shamir, 2016; Daniely, 2017; Chatziafratis et al., 2020; 2019). Bengio & Delalleau (2011) show separation for exact representation, whereas Telgarsky (2016) shows separation for approximate representations with univariate inputs. Eldan & Shamir (2016) demonstrate high-dimensional functions that can be approximated by two-layer polynomial-sized neural networks, but cannot be approximated by one-layer neural nets with subexponential hidden units. Via reduction to certain complexity theo-
retic questions, Vardi & Shamir (2020) show that proving constant depth separations may be hard. Malach et al. (2021) analyze the 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 (Telgarsky, 2016) from approximation theory can be misleading in the sense that 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 (Zhang et al., 2016; Yun et al., 2018; Park et al., 2020; Vershynin, 2020). Yun et al. (2018) show that Θpnq parameters are sufficient to memorize Θpnq training points for ReLU nets with at least 3 layers, and Park et al. (2020) reduce the parameter requirement to sublinear in n. Similar results have been proven for residual architectures (Hardt & Ma, 2016) and convolutional nets (Nguyen & Hein, 2018). Bartlett et al. (2019) analyze the VC-dimension of neural nets, leading to upper and lower bounds on the parameter count needed to fit training data. Other works study expressivity via connections to tensor approximation and sum-product networks (Cohen & Shashua, 2016; Cohen et al., 2016).
There is a long line of work on studying the ability of neural nets to recognize and represent formal languages. The seminal work of Siegelmann & Sontag (1995) shows that RNNs are Turing complete but leverages infinite precision in the hidden activations. Chen et al. (2018) extend this result to ReLU 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 (Pérez et al., 2019; Bhattamishra et al., 2020). A number of recent works have also proven results for generating or recognizing formal languages with finite-precision neural nets (Weiss et al., 2018; Korsky & Berwick, 2019; Hewitt et al., 2020), but these results do not consider Turing machines or analyze statistical properties of their constructions. Bounding the sample complexity of SM approximation requires additional complications in both the construction and statistical analysis.

heading: 1.2 NOTATION
text: Let f˝g denote the composition of functions f and g. For a family of functions G, let f˝Gfitf˝g :gPGu denote the family of compositions between f and functions in G. For a set S and function f :SÑY, let fpSq denote the set tfpsq : sPSuĎY. We use 1d to denote the all-one’s vector in d dimensions, with the subscripted omitted if clear. For iPrds, we let 1dpiq denote the one-hot embedding in d-dimensions, which is 1 at index i and 0 everywhere else. We use the notation rOp¨q to hide poly-logarithmic factors in the argument. The notationÀ,Á indicates the existence of a constant factor such that the inequality holds. — denotes that theÁ andÀ relations simultaneously hold. We use polyp¨q to indicate the existence of a polynomial in the argument which makes the equation true. For a setA (e.g., the set of alphabet symbols for a Turing machine) let 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 ξ1,...,ξn be n i.i.d. Rademacher variables sampled from t´1,`1u. The expected n-sample Rademacher complexity of F on P is as follows: Radn,P pFqfi E pxiqni“1 i.i.d„ P “ Eξ1,...,ξn “ supFPF 1 n řn i“1ξiFpxiq ‰‰ , where pxiqni“1 denotes n i.i.d. samples from P .

heading: 2 STATISTICALLY MEANINGFUL APPROXIMATION
text: 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. In this work, F is some family of neural networks. Fix a loss ` :RˆRÑr0,1s. The classical definition of -approximation states that F -approximates G with respect to `,P if for allGPG, there exists F PF such that Ex„P r`pFpxq,Gpxqqsď . The issue with this classical notion of approximation is that in machine learning settings, we only have access to G, the function we wish to learn, through its values on a finite training set: pxi,Gpxiqqni“1. If we disregard this fact, we could end up constructing functions F which approximateG, but could have a number of unrealistic characteristics such as infinite precision. These drawbacks would mean that F cannnot be realistically learned from the training sample.
This work studies a stronger notion of approximation, statistically meaningful (SM) approximation, to eliminate statistical concerns related to fittingG on a finite sample. SM approximation, defined below, requires that G is learnable via empirical risk minimization using models from F, when data is generated from P .
Definition 2.1 (SM approximation). F -SM approximates G with respect to `,P with sample complexity n if there exists a losss` :FˆXˆRÑr0,1s such that the following holds for allGPG:
Define pF PF to be the empirical minimizer of the losss` for fitting G on an i.i.d. sample pxi,Gpxiqqni“1 of n examples labeled byG: pFfiargminFPF 1n řn i“1
s`pF,xi,Gpxiqq. Then with probability 0.99 over the draw of pxiqni“1, pF approximatesG in the classical sense: Ex„P r`ppFpxq,Gpxqqsď .
Definition 2.1 eases the statistical concerns associated with classical approximation theory: given a finite sample pxi,Gpxiqqni“1, the empirical risk minimizer ofs` over F is guaranteed to -approximateG on the population distribution. It is important that the lossess` (which can be interpreted as a training surrogate loss) and ` can be different, as this allows the empirical risk to include regularization.
Though Definition 2.1 may be reminiscent of PAC-learnability, there is a major conceptual difference: SM approximation unifies expressivity and generalization, whereas PAC-learnability is only concerned with generalization. The main focus of PAC-learnability is achieving a low loss relative to the best function in the hypothesis class, which is assumed to have 0 loss in the realizable case. SM approximation also requires proving that the best function in F achieves near-zero loss.

heading: 2.1 BACKGROUND AND TOOLS
text: To prove SM-approximation guarantees, Definition 2.1 requires a loss surrogates` such that the empirical risk minimizer of s` on the training data can approximate functions in G. The following proposition provides several conditions ons` which lead to SM approximation guarantees. Proposition 2.2. For loss function ` : RˆRÑ r0,1s and distribution P , suppose there exists a loss s` :FˆXˆRÑr0,1s, intended as a surrogate loss for `, satisfying the following properties:
1) For all F PF, xPX , yPR,s`pF,x,yqě`pFpxq,yq.
2) For all G P G, consider the function class LG fi tx ÞÑs`pF,x,Gpxqq : F P Fu. Then the n-sample Rademacher complexity of LG is bounded: Radn,P pLGqď .
3) For allGPG, there exists F PF with small surrogate loss: Ex„P rs`pF,x,Gpxqqsď .
Then F O ´
` 1? n
¯
-SM approximates G with respect to `,P with sample complexity n.
By Proposition 2.2, it suffices that s` upper bounds the target loss ` and has low complexity, and F approximates G with respect tos`, P in the classical sense. The proof follows from standard techniques for bounding generalization based on Rademacher complexity and is provided in Section A.
All-layer margin loss. We introduce one particular construction fors` used in subsequent sections, which is motivated by the all-layer margin generalization bound proposed by (Wei & Ma, 2019b). This bound is based on data-dependent Lipschitzness measures (Nagarajan & Kolter, 2019; Wei & Ma, 2019a), and can provide stronger guarantees than classical norm-based bounds (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2017; Golowich et al., 2018).
We focus on the binary classification setting, whereGpxqPt0,1u, and study approximation with respect to the 0-1 loss `0-1pz,yqfi1ppy´0.5qzď0q where yPt0,1u is assumed to be a binary label. We consider a family of functions F parameterized by p-dimensional parameters θPΘĎRp, with a general architecture function F :XˆRpÑR. Thus, F“tx ÞÑFpx,θq :θPΘu, and we sometimes use θ to identify an element of F. Throughout the paper, we define Θ as a }¨}1-norm bounded set: }θ}1ďα, @θPΘ. We define the parameter-based all-layer margin ρF :RpˆXˆt0,1uÑR as follows:
ρF pθ,x,yqfimin }δ}2 subject to py´0.5q¨Fpx,θ`δqď0
(2.1)
We omit the architecture from the subscript when it is clear from context. This quantity measures the stability of the model around an input x in parameter space. As is the case for the standard output margin, a larger all-layer margin, or better stability, implies better generalization.
We modified the definition in (Wei & Ma, 2019b) to consider perturbations δ in parameter space, whereas Wei & Ma (2019b) consider perturbations to the hidden layers. The parameter-space formulation is simpler and subsumes the results in (Wei & Ma, 2019b). Our formulation also accounts for weight sharing, which is important for our Turing machine results, whereas the formulation of (Wei & Ma, 2019b) could not.
A key and immediate property of the all-layer margin is that it is strictly positive if and only if Fpx,θq predicts the correct label. We can leverage this property to construct a surrogate loss. For some parameter
γ intended to lower bound the all-layer margins, we define the losss`γ as follows:
s`γpθ,x,yq“
$
’ &
’ % 1 if ρpθ,x,yqď0 1´ ρpθ,x,yqγ if 0ăρpθ,x,yqďγ 0 if ρpθ,x,yqěγ
(2.2)
Note that s`γ 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 thats`γpθ,x,Gpxqqě`0-1pFpx,θq,Gpxqq, as is required of a surrogate loss. We show that to obtain sample complexity bounds for SM approximation of G in a classification setting, it suffices to prove that functions in F can fit labels ofGPG with large all-layer margin. Lemma 2.3. Fix any neural net architecture F :X ˆRpÑR, and define Fαfi tx ÞÑFpx,θq : θ PΘu, where we assume ΘĎRp is such that }θ}1ďα for all θPΘ. Fix ě0. Suppose that for allGPG, there exists θPΘ such that the following holds:
Ex„P r1pρpθ,x,Gpxqqăγqsď (2.3)
Then Fα -SM approximates G with respect to `0-1,P with sample complexity rO ´ 1 2 ´ α2logppq γ2 `1 ¯¯ .
We note that rO hides poly-logarithmic factors in the arguments, in this case, polylogpα 2logppq γ2 2 q factors. The proof closely follows (Wei & Ma, 2019b), is deferred to Section A. In Section A, we also state a generalization bound for 0-1 loss based on (2.1), which may be of independent interest. We use (2.2) and Lemma 2.3 to prove that neural nets can SM approximate Boolean circuits and Turing machines.

heading: 3 SM APPROXIMATION OF BOOLEAN CIRCUITS WITH FEEDFORWARD NETS
text: This section shows that feedforward neural nets can SM approximate Boolean circuits with sample complexity that depends polynomially on the size of the circuit. A boolean circuit G : t0,1umÑt0,1u onm inputs bits is described by a directed acyclic graph, with vertices of this graph referred to as “gates”. The graph containsm input gates of indegree 0, which are identified with the input bits. The remaining gates each compute a boolean function taking values at their parents as arguments, and a 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 2, 2, and 1 inputs, respectively and are sufficient to compute any boolean function (Savage, 1998). We also allow identity (ID) gates, which take 1 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 to gates in layer i`1 for some i. Note that we can transform any boolean circuit into a layered one by adding ID gates. Letting q denote the number of layers and r the maximum number of gates in any layer, we say that the circuit has depth q and width r. We say that a circuit with s total gates has size s. Our convention will be that the set of input gates is considered a layer, so rěm. We consider the following class of boolean circuits:
Gq,r,s“tG :t0,1umÑt0,1u :G computed by circuit with depth q, size s, and width ru We will approximate Gq,r,s using a family of width w, depth d feedforward ReLU nets parameterized by linear weights and biases θ “ pW0, b0, ... , Wd, bdq computed as follows: Fw,dpx, θq “ WdφpWd´1φp¨¨¨ φpW0x ` b0q ¨¨¨ q ` bd´1q ` bd, where all intermediate layers have width w for simplicity and φ denotes the coordinate-wise ReLU activation. The weight parameters are set so that for 1ď iď d´1, Wi PRwˆw, W0 PRwˆm, and Wd PR1ˆw. The bias parameters are such that bi PRw for 0ď iďd´1, and bd PR. To control the sample complexity, we restrict our attention to the set of parameters with total }¨}1-norm bounded by α, giving the following function class:
Fw,d,α“tx ÞÑFw,dpx,θq :}θ}1ďαu
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 Gq,r,s of size-s,width-r, and depth-q layered boolean circuits, and the class Fw,d,α of neural nets above. Suppose wÁr, α—s, and d—q. Then for all ą0 and any input distribution P over t0,1um, Fw,d,α -SM approximates G with respect to `0-1,P with sample complexity polypsqrO ´ logpwdq 2 ¯ .
We note that the bound in Theorem 3.1 only scales logarithmically in the width w of the network, even if w is arbitrarily greater than the circuit width r. This ensures that even heavily overparameterized nets will have low sample complexity of the approximation.
For this setting, the all-layer margin loss in (2.2) is essential for proving tight sample complexity bounds, as other surrogate lossess`would give weaker results. For example, if we choose `0-1 as the surrogate loss, VCdimension bounds (Harvey et al., 2017) imply that Fw,d,α statistically meaningfully approximates Gq,r,s with sample complexity scaling in polypwqq under the conditions of Theorem 3.1. This suffers a polynomial 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-based ramp loss, which can be used to prove normbased sample complexities (Bartlett et al., 2017). However, these bounds depend on
śd i“1}Wi}op (or
related quantities), which would be exponentially large in d for the naive construction in Section 3.1.

heading: 3.1 PROOF SKETCH FOR THEOREM 3.1
text: There are two key steps in the proof. First, given any layered circuit G P 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.1, let G denote the layered boolean circuit, which we aim to compute using a neural net. Let gi :t0,1uri´1Ñt0,1uri denote function computed between the i´1-th and i-th layers of G, which we assume have ri´1 and ri gates, respectively, so G“gq´1˝¨¨¨˝g1. Then there exist functions f1,...,fq´1, where each fi is computed by a feedforward ReLU net with two linear and activation layers, such that for all iPrq´1s and xPt0,1um
fi˝¨¨¨˝f1pxq“gi˝¨¨¨˝g1pxq
Thus, the composition Fp¨,θqfi fq´1˝¨¨¨˝f1 satisfies Fpx,θq“Gpxq for all x P t0,1um. Note that we omitted the dependency of fq´1,...,f1 on parameters θ for simplicity.
Lower bounding all-layer margin. The next step for proving SM approximation is to construct a loss s` so that the empirical risk minimizer ofs` 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. norm-based) would not give good sample complexity bounds.
Recall that the all-layer margin ρF pθ,x,Gpxqqmeasures the stability of the output Fpx,θq to perturbations in to θ, and, by Lemma 2.3, it suffices to show that F has large all-layer margin on x P t0,1um. Unfortunately, we cannot guarantee that the naive construction from Lemma 3.2 has large all-layer margin without further modifications. To remedy this issue, Theorem D.6 introduces a generic way to convert the model Fp¨,θq, with possibly small all-layer margin on xPt0,1um, into a new architecture and parameter set F 1p¨,θ1q, with provably large all-layer margin on xPt0,1um, such that F 1px,θ1q“Fpx,θq on all inputs xPt0,1um. The construction relies on introducing new layers to F to obtain F 1 and increases the total number of layers by only a constant factor. This step of the proof is formally stated in the following lemma. Lemma 3.3. In the setting of Lemma 3.2, let Fp¨,θq“fq´1˝¨¨¨˝f1 be the neural net with parameters θ constructed to compute the circuitG. There exist “correction functions” ζ1,...,ζq´2, where ζi is computed by a neural net with two activation and linear layers, such that the composition
F 1p¨,θ1qfifq´1˝ζq´2˝fq´2˝¨¨¨˝ζ1˝f1 has large all-layer margin. Here θ1 denotes the collection of all parameters. Concretely, ρF 1pθ1,x,Gpxqqě
1 polypsq for all xPt0,1u m. Note that we omitted the dependency of fi,ζi on parameters θ1 for simplicity.
We convey the core intuitions for Lemma 3.3 in a simplified toy setting as follows. Consider the case where we start with an initial architecture f computing fpx,pW1,...,Wdqq“ ´ śd i“1Wi ¯
x´0.5, where Wi PR. In this simplified setting, we consider Wi“1 @i. For input x“1 and target y“1, the all-layer margin is small: ρfpp1,...,1q,1,1qÀ 1?d , where the architecture is in the subscript. Indeed, choosing δi“ 3 d , we have fp1,p1´ 3d ,...,1´ 3 dqq“p1´ 3 dq d´0.5«expp´3q´0.5ă0. Thus, by the definition of all-layer margin, ρfpp1,...,1q,1,1qď a ř
iδ 2 i À 1?d .
Now we will insert ReLU layers in f to increase the all-layer margin to Ωp1q. We use ReLU layers to implement the round function, which has the key property that roundpzq“1 @zě2{3.
Proposition 3.4. For any zPR, we can implement the function roundpzq“
$
&
% 0 if ză1{3 3x´1 if 1{3ďză2{3 1 if zě2{3
via a feedforward ReLU net, as follows: roundpzq“3φpz´1{3q´3φpz´2{3q.
We consider the following function rf , which inserts round between every layer in f:
rfpx,pW1,...,Wdqq“roundpWdroundpWd´1¨¨¨roundpW1xq¨¨¨qq´0.5 (3.1) For this demonstration, we ignore the parameters of round, though the actual proof considers these parameters. The following claim shows that (3.1) preserves the output of f while increasing the all-layer margin:
Claim 3.5. In the setting above, it holds that rfp1,p1,...,1qq“fp1,p1,...,1qq and ρ rfpp1,...,1q,1,1qě 1 3 .
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 δiď 13 for all i, the function output will not change because roundpzq“1 @zě 23 . This immediately gives the all-layer margin lower bound 1 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 ζph1q“h if h is the intended output of the layer and h1 is any perturbed value satisfying }h1´h}2ď 13 . Since intended outputs of layers in the function constructed by Lemma 3.2 are binary-valued in t0,1uw because F simulates a boolean circuit, we can simply apply the function round constructed in Proposition 3.4 elementwise 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 xPt0,1um. This leads to the proof of Lemma 3.3. We can complete the proof of Theorem 3.1 by invoking Lemma 2.3, as shown in Section B.

heading: 4 SM APPROXIMATION OF TURING MACHINES WITH TRANSFORMERS
text: In this section, we show that transformers SM approximate Turing machines with computation time bounded by T , using sample complexity polynomial in logT and the state space and alphabet sizes of the Turing machine. Constructions from prior work would require the sample complexity of the approximation to be linear in T (Siegelmann & Sontag, 1995; Chen et al., 2018; Pérez et al., 2019; Bhattamishra et al., 2020). Thus, we obtain an exponential improvement in the dependency on T .
We briefly describe a Turing machine; see (Sipser, 2013) for a more thorough survey. A Turing machine is a model for computation specified by a tuple pZ,A,S,Ztermq containing a set of states Z, a tape alphabet A, a transition function S :ZˆAÑZˆAˆt´1,`1u, and set of terminal states Zterm 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 (Sipser, 2013). Given an input xPA˚ 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.
We let TMpZ,A,S,Ztermq denote the function computed by the Turing machine, which produces an output in t0,1u (if the machine halts). Fixing the alphabet A, we consider the class of binary functions computed by Turing machines with at most k states terminating in T steps:
Gk,T fitx ÞÑTMpZ,A,S,Ztermqpxq : |Z|ďk, and @xPX ,TMpZ,A,S,Ztermq terminates in T steps u (4.1)

heading: 4.1 TRANSFORMER ARCHITECTURE FOR SM-APPROXIMATING TURING MACHINES
text: We study approximation of G with a family of architectures consisting of both an encoder and decoder component (Vaswani et al., 2017), described as follows. The encoder architecture is simple and only performs an embedding of the input symbols, using learnable symbol embeddingsEPRwˆ|A| and fixed positional encodings βp1q,βp2q,...PRw. Given input xPA˚ withm symbols, the encoder producesm output vectors in Rw via Encipx,Eq“E:,xi`βpiq, where Enci denotes the output of the encoder at the i-th position. The decoder iteratively computes an output, running for T steps. We define a transformer layer of the decoder as a sequence of modules consisting of decoder self-attention, followed by encoder-decoder attention, followed by three feedforward ReLU layers.
Attention layers. Attention layers consist of key, value, and query functionsK,V,Q, each of which computes a linear transformation. We omit parameters here for simplicity. Restricted to a single decoder timestep, the attention layer takes two types of inputs: a sequence of previously-computed representations h1,...,hi, and a current input representation h1. The layer first applies the key, value, and query functions as follows:
τ0,τ1,...,τi“Qph1qJK0,Qph1qJKph1q,...,Qph1qJKphiq v0,v1,...,vi“V0,V ph1q,...,V phiq
whereK0 and V0 are fixed “null” key and value vectors which are learned parameters of the layer. Letting J denote the set of indices tj :τj“maxtτ0,...,τiuu, the attention layer performs hard-max attention (Pérez et al., 2019) to compute the output, as follows:
Attnph1,ph1,...,hiqq“h1` 1 |J | ÿ
jPJ vj
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 hpjqt denote the representation computed by the j-th layer of the decoder at timestep t. At timestep i, decoder self-attention at the pj`1q-th layer computes Attnphpjqi ,ph pjq 1 ,...,h pjq i qq. Letting e1,...,em denote the encoder outputs, encoder-decoder self-attention at the pj`1q-th layer and i-th step would compute Attnphpjqi ,pe1,...,emqq. Transformer layers. We use feedforward layers which apply 3 standard ReLU layers, as follows: FFphq“φpW3φpW2φpW1h`b1q`b2q`b3q. Our theory also allows for residual feedforward layers, and the architecture here is chosen mainly to simplify the construction.
A transformer layer applies these constructions in sequence. LettingHpjqi “ph pjq 1 ,...,h pjq i q denote the output after the j-th transformer layer for timesteps 1ďtďi, and θpjq the parameters of the layer, we compute
h pj`1,decq i “Attnph pjq i ,H pjq i ,θ (j + 1, dec-attn)q h pj`1,encq i “Attnph pj`1,decq i ,pe1,...,emq,θ (j + 1, enc-attn)q
Trphpjqi ,H pjq i ,pe1,...,emq,θ pj`1qq“FFphpj`1,encq,θpj + 1, ffqq Note that we included the explicit dependence of the attention layers on the parameters for completeness. We now set hpj`1qi “Trph pjq i ,H pjq i ,pe1,...,emq,θpj`1qq.
Decoder outputs. We consider d-layer decoders, so oifih pdq i denotes the output of the decoder at time i, which is also inputted to the decoder at time i`1 as follows: hp0qi`1“h pdq i `βpi`1q. The initial decoder input hp0q0 is a trainable parameter. The decoder runs for a fixed number of timesteps T 1 and produces the prediction θJclsh pdq T 1 . For simplicity, we assume T
1“T , the computation time of the Turing machine family. Note that our architecture allows long (length T ) decoding sequences, whereas typical architectures in practice use decoding sequences with roughly the same length as the input (Vaswani et al., 2017). The architecture we study is similar to ones studied by (Pérez et al., 2019; Bhattamishra et al., 2020).
We use x ÞÑFw,d,T px,θq to denote the described transformer architecture with parameters θ,w-dimensional hidden layers, d transformer layers in the decoder, and T decoder steps. This leads to the following class of transformer functions: Fw,d,α,T “tx ÞÑFw,d,T px,θq : }θ}1ďαu. 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 G of functions computed by Turing machines with at most k states, alphabet A, and computation time bounded by T steps for inputs xPX . Suppose that wÁk|A|`logT , d— logT , and α“polypk,|A|,logTq. Then for all ą0 and any input distribution P over X , Fw,d,α,T -SM approximates G with respect to `0-1,P with sample complexity polypk,|A|,logTqrO ´ logpwdq 2 ¯ .
As with Section 3, we set the surrogate losss` in Definition 2.1 to be the all-layer margin loss defined in Section 2.1. Commonly-used alternatives for the surrogate loss would not suffice for either our construction or ones in prior work (Siegelmann & Sontag, 1995; Chen et al., 2018; Pérez et al., 2019; Bhattamishra et al., 2020). First, the VC dimension of Fw,d,α,T is at least ΩpwTq. This is because transformer architectures
which contain a decoder component can express RNNs, which by lower bounds have VC dimension at least wT (Koiran & Sontag, 1998). This indicates that using `0-1 as the surrogate loss would lead to sample complexities that are suboptimal in both the overparameterized widthw 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 -th power of some parameter norm, or exponentially in T . Thus, as in Section 3, the all-layer margin surrogate loss (2.2) is essential for obtaining our sample complexity bounds.

heading: 4.2 PROOF SKETCH FOR THEOREM 4.1
text: Following Lemma 2.3, our goal is to construct a transformer which can simulate Turing machines with large all-layer margin, namely, Ω ´
1 polypk,|A|,logTq
¯
. The fundamental limitation of prior work (Pérez et al., 2019) towards attaining this is that the positional embeddings are required to store values as small as
1 polypTq . 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 1polypTq because perturbing the layer by the small entries could change the prediction. Instead, we propose using Binpiq, the binary encoding of i in rlogT s 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.
We describe the construction of the transformers. Fix a Turing machineGPG. We first require notation to describe the computation ofG. For input xPX , we define zipxq, aipxq to be the Turing machine state and symbol under the tape head at the conclusion of step i. We let lipxq denote the location of the Turing machine head at the conclusion of step i. During the timestep, the Turing machine computes Spzi´1pxq,ai´1pxqq, writes a new symbol under the head at location li´1pxq, and moves the head either left or right. Let uipxq denote the symbol written during timestep i, and qipxqPtleft,rightu the movement direction of the head. Following (Pérez et al., 2019) with several key modifications, we simulate the Turing machine using the transformer as follows. Each timestep will maintain the invariance that oi contains an encoding of zipxq,aipxq, and lipxq. Given that this invariance holds until timestep i, the transformer simulates timestep i`1 of the Turing machine with the following steps:
1) Use feedforward layers to apply transition S on zipxq and aipxq, which can be read from oi, to obtain zi`1pxq, ui`1pxq, and movement direction qi`1pxqPtleft, rightu.
2) Using feedforward layers, compute li`1pxq from qi`1pxq and the encoding of lipxq in oi. 3) Compute ai`1pxq. We use decoder self-attention to search over past timesteps which wrote to li`1pxq. Our aim is to find ui1pxq, where i1“maxtjďi`1:lj´1pxq“li`1pxqu. We implement a binary search over past timesteps j, which is needed to find the largest j ď i` 1 where lj´1pxq“li`1pxq. The binary search can be implemented withOprlogT sq decoder self-attention layers, and the construction ensures large all-layer margin.
4) If no such i1 from the previous timestep existed, we check whether li`1pxq contained an input symbol using encoder-decoder attention and copy this input symbol if so.
5) If no symbols were found in 3) or 4), li`1pxqmust contain the blank symbol (meaning it wasn’t visited yet by the head). Thus, we have computed ai`1pxq, so we have all the information needed to compute the new embedding oi`1.
To lower bound the all-layer margin of the constructed transformer, we use Theorem D.6, which requires existence of a “correction function” which can correct outputs in previous layers. Since we construct a network with intermediate layer entries in t0,1u, 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.

heading: 5 CONCLUSION
text: This work proposes a 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 a first analysis with this definition, we show approximability of two 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 net architectures, and using our definition as a lens to compare architectures.

heading: 6 ETHICS AND REPRODUCIBILITY STATEMENTS
text: An ethics statement is not applicable for this work – this work is mainly theoretical and is several layers removed from empirical applications.
Section A contains the proofs for Section 2. Section B contains the formal construction and proof for boolean circuits. Section C contains the formal construction and proof for Turing machines. Section D rigorously introduces the correction function machinery and lower bounds the all-layer margin in terms of properties of the correction functions.

heading: A PROOFS FOR SECTION 2
text: We prove Proposition 2.2 and Lemma 2.3.
Proof of Proposition 2.2. Let pxiqni“1 denote a n i.i.d. training examples drawn from P and fixGPG. DefineLpFqfiEx„P rs`pF,x,Gpxqqs and pLpFqfi 1n řn i“1
s`pF,xi,Gpxiqq. Let pF PF denote argminFPFpLpFq, the empirical risk minimizer of pL, which we aim to show has population loss for fitting G bounded by Op ` 1?
n q. By standard arguments using Rademacher complexity, we have with probability 1´δ,
sup FPF
|LpFq´pLpFq|ď2Radn,P pLGq` c logp2{δq n
ď2 ` c logp2{δq n
(A.1)
Now note that by the condition 3) ons`, there exists F‹ with LpF‹qď . Now we have LppFq´LpF‹qďpLppFq´pLppFqq`ppLppFq´pLpF‹qq`ppLpF‹q´LpF‹qq
We bound the first and last term in parenthesis by applying (A.1), and the middle term is bounded by 0, by definition of pF . It follows that
LppFq´LpF‹qď4 `2 c logp2{δq n
ùñLppFqď5 `2 c logp2{δq n
where we usedLpF‹qď . Finally, we use the fact thats` upper bounds `, so Ex„P r`ppFpxq,GpxqqsďLppFq. Plugging in δ“0.01 gives the desired result.
Proof of Lemma 2.3. We first observe thats`γpθ,x,yqď1pρpθ,x,yqăγq by definition, so by (2.3), for all GPG we have
inf θPΘ
Ex„P rs`pθ,x,Gpxqqsď
Thus, it remains to check the Rademacher complexity condition for applying Proposition 2.2. Fixing any GPG, define the function class LG as in Definition 2.1. We first observe that following the same argument as Claim A.4 of (Wei & Ma, 2019b) (except we apply the perturbations to the parameters, rather than the hidden layers), |ρpθ,x,yq´ρpθ1,x,yq|ď}θ´θ1}2 for any θ,θ1PRp. Let N}¨}2pε,Θq denote the ε-covering number of Θ in }¨}2-norm, and N}¨}8pε,LGq the εcovering number of LG in the norm defined by }H´H1}8“maxxPX |Hpxq´H1pxq| for anyH,H1PLG. The arguments of (Wei & Ma, 2019b) imply that logN}¨}8pε,LGqď logN}¨}2pγε,ΘqďO ´Y α2logppq γ2ε2 ]¯
, where the last inequality is from standard covering number bounds for } ¨}1 balls. Now we can apply this covering number bound in the Dudley entropy integral, another standard step to bound Rademacher
complexity, to obtain that for all n, Radn,P pLGqÀ αlogn
? logppq
γ ? n (see arguments in (Wei & Ma, 2019b) for more detail). Solving for n such that the r.h.s. of this equation is bounded by gives the desired result.
Note that from the proof of Lemma 2.3, we would also obtain the following parameter-space all-layer margin generalization bound as a corollary, which may be of independent interest: Corollary A.1. In the setting of Lemma 2.3, letQ denote a distribution over px,yq pairs, with pxi,yiqni“1 denoting a set of n i.i.d. training samples from Q. With probability 1´δ over the draw of the training samples, all classifiers Fp¨,θqPF which achieve zero 0-1 training loss satisfy
Ex„Qr`0-1pFpx,θq,yqsďO
¨
˝
α a
logppq? n
g
f
f
e
1
n
n ÿ
i“1
1
ρpθ,xi,yiq2
˛
‚`ξ (A.2)
where ξÀO ´ logp1{δq`logpnq? n ¯ is a low-order term.
The proof of Corollary A.1 simply follows by plugging in the coverning number bound on ρ derived in the proof of Lemma 2.3 into Lemma 2.2 of (Wei & Ma, 2019b).

heading: B PROOFS FOR SECTION 3
text: This section completes the proof of Section 3. The following lemma formally states that we can construct the neural net to simulate the circuit layerwise. Lemma B.1. In the setting of Theorem 3.1, let G denote the layered boolean circuit, which we aim to compute using a neural net. LetGi :t0,1uri´1Ñt0,1uri denote function computed between the i´1-th and i-th layers of G, which we assume have ri´1 and ri gates, respectively. Let f denote the following 2-layer neural net architecture, parameterized by θ“pW1,b1,W2,b2q:
fph,θq“φpW2φpW1h`b1q`b2q Then there exist θ with }θ}1“Opriq such that for any hPt0,1uri´1 ,
fprh,θq“ČGiphq
where rh takes h and appends w´ri´1 zeros, and likewise for ĂGiphq.
We note that the proof of Lemma 3.2 follows by applying Lemma B.1 q´1 times. Using Lemma B.1, we can complete the proof of Theorem 3.1.
Proof of Theorem 3.1. Our proof will construct a neural network to compute any boolean circuit with all-layer margin lower bound 1polypr,qq . By Lemma 2.3, this will be sufficient to guarantee meaningful approximation.
There are two steps in our construction: first, given any layered circuitGPGq,r,s, we construct a neural net that directly simulatesG by computing the layers ofG one-by-one. Our construction shows that we can compute every layer inG using two feedforward ReLU layers, and results in a neural net pF computingG, but with possibly small all-layer margin. The next step is to convert pF into a neural net with large all-layer margin, i.e., implement Lemma 3.3. To do this, we insert “correction functions” (Definition D.1) between every group of layers in pF . These correction layers leverage the knowledge that unperturbed outputs of these layers should be contained in t0,1uw and perform elementwise rounding to map perturbed values back to t0,1uw. Theorem D.6 formally shows that by introducing these correction layers can guarantee a lower bound on the all-layer margin roughly depending on the Lipschitz constants of each individual layer. Furthermore, each correction layer can be computed via two feedforward ReLU layers, so introducing the correction layers only increases depth by a constant factor.
We implement the proof plan by first applying Lemma B.1 q times in order to obtain the function pF computing G (with padding) mentioned above. The total }¨}1-norm of the parameters so far is at most s. Now we use the correction function described in Proposition 3.4, which we apply coordinate-wise on non-padding coordinates. We apply the correction functions after each layer constructed in Lemma B.1. Note that each correction function requires at most double the width of the corresponding layer in the circuit, and the parameters for all correction functions add total }¨}1-norm at mostOpsq. Note that at this point, minor modifications are still required in order to apply Theorem D.6. The neural net output is in t0,1uw, not t´1,1u; we can remedy this by setting the last layer to compute the linear transformation z ÞÑ 2z´1 on the single non-padding coordinate corresponding to the output. Second, to make the depth of the architecture consistently d, we can add sequences of identity functions before this last linear layer just constructed, followed by correction layers, until each of the constructed approximating functions reaches the desired fixed depth d. This finally gives us parameters θ with } ¨}1-norm bound Ops` dq, so that the set of constructed functions is contained in Fw,d,α. Thus, we showed that for GPGq,r,s, there exists θ such that Fpx,θq“2Gpxq´1 for all xPt0,1um. Finally, it is straightforward to check that Condition D.3 for Theorem D.6 is satisfied for Lipschitzness parameters which are polynomial in the circuit width r. Thus, we apply Theorem D.6 to obtain a lower bound pγ“ 1polypr,qqě 1 polypsq on the all-layer margin for every input xPt0,1u
m. Finally, we directly apply Lemma 2.3 using γ“pγ to obtain the desired result.
The following proposition will be used to construct basic gates in the circuit with a simple feedforward ReLU network. Proposition B.2. Let x “ „
x1 x2

P t0,1u2 be binary inputs to AND and OR gates. The following
feedforward ReLU networks compute the AND and OR functions: FANDpxq “ φpx1 ` x2 ´ 1q, and FORpxq“1´φp1´x1´x2q.
Proof of Lemma B.1. Each row of W1 and value in b1 will correspond to a single entry in the output of ĂGi. The same applies for W2,b2. W2 will be set to a diagonal matrix with entries in t´1,0,1u. For the 0 entries which only serve to pad the dimension, we set corresponding values inW1,b1,W2,b2 to be 0. For the remainder of the entries of ĂGi corresponding to actual gates in the circuit, in the case that the gates compute AND or OR, we fill in the values of corresponding rows in W1,b1,W2,b2 to implement the constructions for AND and OR in Proposition B.2. The construction for ID and NOT are even simpler. For example, to implement NOTpzq“1´z for zPt0,1u on coordinate j, we can set the j-th row ofW1 to have -1 on the diagonal and 0 everywhere else, pb1qj“1, pb2qj“0, and pW2qj,j“1. It is easy to check that }θ}1“Opriq with this construction.

heading: C PROOF OF THEOREM 4.1
text: C.1 ADDITIONAL SETUP AND NOTATION
We fix any Turing machine GPG and construct a transformer which can simulate G. Throughout this section, a superscript will be used to index layer indices, and a subscript to index timesteps.
We assume that the initial state of the tape has the input written at the left-most positions. The Turing machine always starts at a fixed initial state zinit. We let r∅sPA denote the blank symbol, which initially fills all positions on the tape which aren’t part of the input. We construct a transformer that simulates the Turing machine up until it reaches a terminal state in Zterm, at which the transformer will loop in that state until it hits a computation time T .
We introduce some notation which will appear throughout the construction. Define wpos fi rlog2T s. We use wpos to denote the effective dimension of the position embedding, as only wpos coordinates will be non-zero. For 0ď iďT , define Binpiq PRwpos to be the vector containing the binary encoding of i: Binpiqj“1 if the binary representation of i contains 1 in the j-th bit and 0 otherwise. For simplicity, the proof will focus on the setting without overparameterization, where we choose the dimensionw“wTMfi |Z|`2|A|`3wpos`wscr for storing all the hidden representations of the model, where wscr“Opwpos`|A|`|Z|q. We can extend our analysis to allow for arbitrary over-parameterization using wąwTM by designating a certain subset of the coordinates to always equal 0, and performing calculations using only a subset ofwTM coordinates. We group thewTM coordinates using the following symbols: st for encoding the state, sym1, sym2 for encoding symbols, pos1 and pos2, pos3 for encoding position, and scr, which is used as scratch space. Thus, for hPRw, we can index its coordinates via the groups as follows:
h“
»
—
—
—
—
—
—
—
– hst PR|Z| hsym1 PR|A| hsym2 PR|A| hpos1 PRwpos hpos2 PRwpos hpos3 PRwpos hscr PRwscr
fi
ffi
ffi
ffi
ffi
ffi
ffi
ffi
fl
When the meaning is clear from context, we use the superscript to index coordinate groups as described.
The position embedding βpiq is defined formally so that βpiqpos1 “ Binpiq, and βpiq is 0 in all other coordinates. The encoder embedding matrixE is such that
Encipxqsym1“1|A|pxq Encipxqpos1“Binpiq
(C.1)
where Encipxq has 0’s at all other coordinates. embedding function e :AÑRd for the encoder is defined such that epxqsym1 “1|A|pxq, the one-hot encoding for xPA, and 0 everywhere else. We use o1,...,oT to refer to the output embeddings of the decoder. Our construction maintains the invariant that the output embedding oi encodes zipxq, aipxq, lipxq for each i. To achieve this, we maintain
osti “1|Z|pzipxqq o
sym1 i “1|A|paipxqq o
pos2 i “Binplipxqq
(C.2)
and oi has 0 at all other coordinates. Thus, the input oi`βpi`1q to the decoder at step i`1 is of the form poi`βpi`1qqst“1|Z|pzipxqq
poi`βpi`1qqsym1“1|A|paipxqq poi`βpi`1qqpos1“Binpiq poi`βpi`1qqpos2“Binplipxqq
(C.3)
C.2 COMPLETING THE PROOF
We implement the first step 1) in Section 4.2 using the following lemma. Note that the lemma uses two consecutive feedforward ReLU layers, but in our actual proof we will simulate this using two transformer layers where the attention parameters are all 0, and only the feedforward layers are instantiated. Lemma C.1. Let O denote the set of decoder inputs in the form (C.3) encoding zi´1pxq, ai´1pxq, li´1pxq for some timestep i. For parameters θ“pW1,b1,W2,b2q, consider the following function computing a sequence of two feedforward ReLU layers: fph,θq“φpW2φpW1h`b1q`b2q. There exist parameters θ such that for decoder inputs hPO,
fph,θqst“1|Z|pzipxqq fph,θqsym2“1|A|puipxqq fph,θqpos1“Binpiq fph,θqpos2“Binpli´1pxqq
(C.4)
Furthermore, fph,θqscr will contain a one-hot encoding for qipxq, and besides this, fph,θq is 0 at all other coordinates. The parameters satisfy }θ}1“Op|Z||A|`wposq.
Proof. We follow the construction used in Lemma B.2 of (Pérez et al., 2019). The first layer computes a one-hot encoding of the state, symbol input pair. We chooseW1 :RwTMÑR|Z||A|`wTM so that the first |Z|A| rows are described by:
pW1qstpz,aq,:“1|Z|pzq pW1q sym1 pz,aq,:“1|A|paq
and 0 everywhere else. The remaining rows of wTM rows ofW1 simply implement the identity mapping. We choose b1 so that its first |Z||A| entries are -1, and all other entries are 0. We observe that from this construction, for all hPO where h encodes zi´1pxq,ai´1pxq,
φpW1h`b1q“ „ 1|Z||A|ppzi´1pxq,ai´1pxqqq h 
This is because before the ReLU, the first |Z||A| entries ofW1h will have 2 on the pzi´1pxq,ai´1pxqq-th entry and be bounded by 1 everywhere else, so adding α1 and applying the activation will zero out all but one entry.
Now it is simple to pick W2 so that fph,θq is as desired because we can construct it to exactly encode the output of Spz,aq for each of its first pz,aq columns and copy over the other necessary entries of h as needed by (C.4).
The next lemma demonstrates that we can use an additional sequence of feedforward ReLU layers to produce Binplipxqq, given Binpli´1pxqq and qipxq. Lemma C.2. In the setting of Theorem 4.1 and Lemma C.1 above, there is a function f parameterized by θ composed of Opwposq feedforward ReLU layers such that for any h computed by the function in Lemma C.1 in the form (C.4) at timestep i,
fph,θqst“1|Z|pzipxqq fph,θqsym2“1|A|puipxqq fph,θqpos1“Binpiq fph,θqpos2“Binpli´1pxqq fph,θqpos3“Binplipxqq
(C.5)
At all other coordinates, Fph, θq takes value 0. Furthermore, the parameters satisfy }θ}1“Opwposp|Z|`|A|`wposqq.
Proof. As the construction of Lemma C.1 encoded qipxq, the movement direction of the head, we can use feedforward ReLU layers to implement binary addition to either add or subtract 1 from li´1pxq. Let v1,v2 denote the bits in the scratch dimensions indicating the head movement, where v1“1,v2“0 indicates left and v1“0,v2“1 indicates right. Then more specifically, we first useOpwposq feedforward ReLU layers to compute li´1pxq´v1, and thenOpwposq additional feedforward ReLU layers to compute li´1pxq´v1`v2. Note that the output would always be lipxq by the definition of v1,v2. It remains to implement a module which computes Binpj´v1q given v1,Binpjq, and Binpj`v2q given v2,Binpjq for any jPrT s. We can express the binary addition by a depth-Opwposq binary circuit, which can in turn be expressed by a neural net withOpwposq layers where each weight matrix has }¨}1-norm p|Z|` |A|`wposq (which is required to implement the identity mapping to copy forward the other dimensions of h which aren’t involved in the binary addition). This gives the desired total }¨}1-norm bound.
The next lemmas implement steps 3), 4), 5) in Section 4.2. For the following lemmas, it will be helpful to further index the scratch dimensions as follows: for a vector hPwscr,
hscr“
»
—
– hscr1 PR|A| hscr2 PR|A| hscr3 PRwpos hscr4 PR3 fi ffi fl
Lemma C.3. In the setting of Theorem 4.1 and Lemma C.2 above, fix any timestep i and define i1 “maxt1ď tď i : lt´1pxq “ lipxqu. If j such that lt´1pxq “ lipxq exists, we define i1 “ 0 otherwise. Consider any Hi“ph1,...,hiq, where ht is computed by the layer in Lemma C.2 for timestep t, and in the form (C.5). There is a function f parameterized by θ consisting of Opwposq total self-attention and linear layers such that for all suchHi, the following holds:
fphi,Hi,θqst“1|Z|pzipxqq fphi,Hi,θqsym2“1|A|puipxqq fphi,Hi,θqpos1“Binpiq fphi,Hi,θqpos2“Binpli´1pxqq fphi,Hi,θqpos3“Binplipxqq
fphi,Hi,θqscr1“ " 1|A|pui1pxqq if i1ą0 0 otherwise
Fphi,Hi,θqscr41 “1pi1ą0q
(C.6)
At all other coordinates, FpH, θq takes value 0. Furthermore, the parameters satisfy }θ}1“Opwposp|Z|`|A|`wposqq.
The proof plan will roughly implement a binary search to find i1, leveraging the attention layers. The first step in the binary search is to verify whether i1ą0, described below. Claim C.4. In the setting of Lemma C.3, letHi“h1,...,hi be the input representations for timesteps 1,...,i. Suppose that each ht for 1ďtďi satisfies the following:
h pos1 t “Binptq h
pos2 t “Binplt´1pxqq
(C.7)
Additionally, suppose that hi is of the form in (C.5). Then there is a function fp0q parameterized by θ such that
fp0qphi,Hi,θqscr1“0 fp0qphi,Hi,θqscr3“0 fp0qphi,Hi,θqscr41 “1pi1ą0q
(C.8)
The function fp0q can be computed by a single decoder self-attention layer with }θ}1“Opwposq.
Next, we implement the binary search itself, using wpos self-attention layers. Each step of the binary search reveals a single bit of i1, so the j-th attention layer will compute a representation storing the j most
significant bits of i1. We let BinjplqPt0,1uwpos to denote the binary encoding of the j most significant bits of l: pBinjplqqj1“pBinplqqj1 for 1ďj1ďj, and pBinjplqqj1“0 for j1ąj. We also set Bin0plq“0. We use the superscript pjq to indicate the j-th set of layers in the binary search. The following claim implements each step of the binary search rigorously.
Claim C.5. In the setting above and of Lemma C.3, let Hpjqi “ h pjq 1 , ... ,h pjq i be the representations computed after the j-th group of layers for timesteps 1 through i, for 0ďjďwpos´1. Suppose that each h pjq t for 1ďtďi satisfies the following:
h pjq,pos1 t “Binptq
h pjq,pos2 t “Binplt´1pxqq
(C.9)
In addition, suppose that hpjqi satisfies:
h pjq,scr1 i “0
h pjq,scr3 i “
" Binjpi1q if i1ą0 0 otherwise
phpjq,scr4i q1“1pi 1ą0q
(C.10)
with all other coordinates matching the quantities prescribed in (C.5). Then there is a function fpj`1q parameterized by θ such that
fpj`1qphpjqi ,H pjq i ,θq scr1“0
fpj`1qphpjqi ,H pjq i ,θq
scr3“ " Binj`1pi1q if i1ą0 0 otherwise
fpj`1qphpjqi ,H pjq i ,θq scr4 1 “1pi1ą0q
(C.11)
with all other coordinates matching those prescribed in (C.5). We note that fpj`1q consists of a single decoder self-attention layer followed by single feedforward ReLU layer, with }θ}1“Op|Z|`|A|`wposq.
At the end of the wpos-th application of the binary search, we would have found Binpi1q exactly. It remains to apply another attention layer which attends directly to timestep i1 and copies ui1pxq. Claim C.6. In the setting above and of Lemma C.3, let Hi“h1,...,hi be the representations computed after the wpos-th group of layers constructed in Claim C.5 for timesteps 1 through i. Suppose that each ht for 1ďtďi satisfies the following:
h sym2 t “1|A|putpxqq h
pos1 t “Binptq h
pos2 t “Binplt´1pxqq
(C.12)
In addition, suppose that hi satisfies:
hscr1i “0 hscr3i “ " Binpi1q if i1ą0 0 otherwise
phscr4i q1“1pi 1ą0q
(C.13)
with all other coordinates matching the quantities prescribed in (C.5). Then there is a function fpwpos`1q parameterized by θ such that fpwpos`1qphi,Hi,θq computes the desired output in (C.6). Furthermore, fpwpos`1q consists of a single decoder self-attention layer followed by a single feedforward ReLU layer, and }θ}1“Op|Z|`|A|`wposq.
Putting these together, we complete the proof of Lemma C.3.
Proof of Lemma C.3. For the purposes of this proof, we index the layers by a superscript to avoid confusion with indexing timesteps. We set fp0q to be the function defined in Claim C.4. We note that
layers output by fp0q satisfy the condition of Claim C.5, so we can apply Claim C.5 inductively to obtain layers fp1q,...,fpwposq where their applying their composition results in representations satisfying (C.12) and (C.13). Now we set fpwpos`1q to be the function constructed in Claim C.5, which gives the desired output. Finally, we note that by summing the }¨}1 bounds for the parameters constructed in each layer, we can finally obtain }θ}1“Opwposp|Z|`|A|`wposqq.
We fill in the proofs of Claims C.4, C.5, and C.6 below.
Proof of Claim C.4. To construct the decoder self-attention, the query function will be of the form Qphq“WQh`bQ and Kphq“WKh`bK, where WQ,WK PRpwpos`1qˆw and bQ,bK PRwpos`1. We choose the parameters such that the following equations hold:
Qphq1:wpos“2hpos3´1 Qphqwpos`1“1
and
Kphq1:wpos“2hpos2´1 Kphqwpos`1“0
The value function V phq is such that V phqscr41 “ 1, and V phq` “ 0 on all other coordinates `, which can be implemented by a linear transformer. Finally, we set the null key K0 and value V0 such that pK0qwpos`1“wpos´1, with 0 everywhere else, and V0“0. Letting θattn denote the attention parameters, the layer is of the form
fp0qphi,Hi,θq“Attnphi,Hi,θq
To see that fp0q satisfies (C.8), observe that if i1 ą 0, QphiqJKphi1q “wpos by (C.7) and construction of Q,K. On the other hand, QphiqJK0“wpos´1. Thus, argmaxtQphiqJKphtq P ris, which implies that fp0qphi,Hi, θqscr41 “ 1 by the construction of V . In the other case where i1 “ 0, we note that QphiqJKphtqďwpos´2 for all 1ď tď i, so the null position is attended to. By construction of V0, this implies fp0qphi,Hi,θqscr41 “0. As V,V0 are 0 on all other coordinates, it follows that (C.8) holds. It’s also easy to observe that the }θ}1 is as desired.
Proof of Claim C.5. The first layer in fpj`1q computes decoder self-attention. The query function is of the form Qphq“WQh`bQ, and the key function is of the form Kphq“WKh`bh, where WQ,WK P Rpwpos`j`2qˆw and bQ,bK PRpwpos`j`2q. We choose the parameters so that the following equations hold:
Qphq1:wpos“2hpos3´1 Qphqwpos`1:wpos`j“2h scr3 1:j ´1
Qphqwpos`j`1“1 Qphqwpos`j`2“1
and
Kphq1:wpos“2hpos2´1 Kphqwpos`1:wpos`j`1“2h pos1 1:j`1´1
Kphqwpos`j`2“0
Both of these functions can be constructed via linear transformations of h, with }WQ}1`}WK}1`}bQ}1` }bK}1“Opwposq. Now we construct the value function V phq“WV h`bV such that V phqscr43 “1 and V phq`“0 on all other coordinates, which is also easily implemented by a linear layer. For the attention, the last quantities to construct are the null keyK0 and value V0. K0 will satisfy pK0qwpos`j`2“wpos`j, with 0 everywhere else. V0 will simply be 0 on all coordinates. Letting θattn“pWQ,bQ,WK,bK,WV ,bV ,K0,V0q denote the attention parameters, the first layer will now be in the form
fpj`1q,1phpjqi ,H pjq i ,θattnq“Attnph pjq i ,H pjq i ,θattnq
where Attn uses the constructed key, value, and query functions. We claim that fpj`1q,1phpjqi ,H pjq i ,θattnq satisfies the following:
fpj`1q,1phpjqi ,H pjq i ,θattnq scr4 3 “
" 1 if i1ą0 and has pj`1q-th bit 1 0 otherwise
(C.14)
For all other coordinates `, fpj`1q,1phpjqi ,H pjq i , θattnq` “ ph pjq i q`. To see this, we first observe that Qphpjqi qJK0 “ wpos ` j. Next, we observe that Qph pjq i q1:wpos produces the encoding of lipxq using binary t´1,`1u bits, and Kphpjqt q1:wpos produces the encoding of lt´1pxq using binary t´1,`1u bits by (C.9). In addition, Qphpjqi qwpos`1:wpos`j “ 2Binjpi1q ´ 1 if i1 ą 0 and all 0’s otherwise, and Kphpjqt qwpos`1:wpos`j`1“2Binj`1ptq´1. Note that by our construction, the maximum possible value of Qphpjqi qJKph pjq t q is wpos`j`1, and the next largest possible value is wpos`j´1. Now there are 3 cases:
Case 1: i1“0. In this case, we note that lipxq never matches lt´1pxq for 1ďtďi. Thus, by construction of the first wpos coordinates of Q and K, the largest possible value of Qphpjqi qJKph pjq t q is wpos`j´1, so the attention will always only attend to the null position, so the layer adds V0“0 to hpjqi , preserving its value. Note that phpjq,scr4i q3“0 in this case, which matches the desired behavior.
Case 2: i1ą0, and has pj`1q-th bit 0. In this case, we note that for all tąi1,Qphpjqi qJKph pjq t qďwpos`j´ 1, because by definition such tmust satisfy lt´1pxq‰lipxq, so the first wpos coordinates contribute at most wpos´2 to the dot product. On the other hand, if tďi1, tmust have pj`1q-th bit 0, soKphpjqt qwpos`j`1“ ´1. This doesn’t match the pwpos`j`1q-th bit of the query, so Qphpjqi qJKph pjq t qďwpos`j´1 again. Thus, in this case, the null position is attended to again. The same reasoning as Case 1 then applies.
Case 3: i1ą0 and has pj`1q-th bit 1. In this case, maxtQphpjqi qJKph pjq t q“wpos`j`1: for example, t“ i1 achieves this maximum by our construction. As a result, the null position is not attended to. All the values in the positions attended to satisfy V phpjqt q scr4 3 “1, which matches the pj`1q-th bit of i1. Thus, (C.14) holds.
Finally, to complete the proof we simply append an additional feedforward ReLU layer which copies the value fpj`1q,1phpjqi ,H pjq i ,θattnq scr4 3 to the output bit corresponding to the position indexed by ¨ scr3 j`1. This layer will also set the output bit corresponding to ¨scr43 to 0. Note that these operations can be implemented with a linear layer, and applying a ReLU activation after won’t change the output, which is in t0,1uw. By (C.10), the constructed function will thus satisfy (C.11). It’s also easy to observe that }θ}1 is as desired.
Proof of Claim C.6. The attention layer uses key and query functions which each compute linear transformations from Rw to R2wpos`1. The value function is also linear. We choose parameters such that
Qphq1:wpos“2hpos3´1 Qphqwpos`1:2wpos“2hscr3´1
Qphq2wpos`1“1
and
Kphq1:wpos“2hpos2´1 Kphqwpos`1:2wpos“2hpos1´1 Kphq2wpos`1“0
and
V phqscr1“hsym2
Furthermore, we choose null keys and positions such that pK0q2wpos`1“2wpos´1, and V0“0. To follow the attention layer, we construct a linear layer which simply zeros out coordinates indexed by ¨scr3 and preserves all other coordinates. Note that because all outputs are either 0 or 1, applying a ReLU activation won’t change the result. To see that this construction computes (C.6), we observe that if i1ą0,QphiqJKphi1q“ 2wpos. Otherwise, if i1“0,QphiqJKphtqď2wpos´2 for all 1ďtďi. On the other hand, it always hold thatQphiqJK0“2wpos´1. Thus, if i1ą0, the attention attends exactly to i1, so the value function satisfies
V phi1q“1|A|pui1pxqq, which would produce the output in (C.6), as desired. On the other hand, if i1“0, the attention attends to the null position, so the attention layer sets fpwpos`1qphi,Hi,θqscr1“0. Thus, fpwpos`1q also produces the desired output in this case. It’s also easy to observe that the }θ}1 is as desired.
The next step is to complete step 4) in Section 4.2 using encoder-decoder attention. The following lemma provides this construction. Lemma C.7. In the setting of Theorem 4.1 and Lemma C.3, consider any timestep i and let h denote an output of the function constructed in Lemma C.3, in the form (C.6). Let e1,...,em denote the outputs of the encoder, in the form (C.1). There is a function f with parameter θ consisting of a single encoder-decoder attention layer such that for all such h in the form (C.6), the following holds:
fph,pe1,...,emq,θqst“1|Z|pzipxqq fph,pe1,...,emq,θqsym2“1|A|puipxqq fph,pe1,...,emq,θqpos1“Binpiq fph,pe1,...,emq,θqpos2“Binpli´1pxqq fph,pe1,...,emq,θqpos3“Binplipxqq
fph,pe1,...,emq,θqscr1“ " 1|A|pui1pxqq if i1ą0 0 otherwise
fph,pe1,...,emq,θqscr2“ " 1|A|pxlipxqq if lipxqďm 0 otherwise
fph,pe1,...,emq,θqscr41 “1pi1ą0q fph,pe1,...,emq,θqscr42 “1plipxqďmq
(C.15)
At all other coordinates, fph, pe1, ... , emq, θq takes value 0. Furthermore, the parameters satisfy }θ}1“Op|A|`wposq.
Proof. We choose the encoder-decoder attention layer so that the key, value, and query functions are linear transformations. The key and query functions map Rw to Rwpos`1 and compute the following:
Qphq1:wpos“2hpos3´1 Qphqwpos`1“1
and
Kphq1:wpos“2hpos1´1 Kphqwpos`1“0
The value function computes
V phqscr2“hsym1 V phqscr42 “1
with 0’s in all other coordinates. The null key K0 satisfies pK0qwpos`1“wpos´1, with 0’s in all other coordinates. The null value V0 satisfies V0“0. We set
fph,pe1,...,emq,θq“Attnph,pe1,...,emq,θq
where Attn is the decoder-encoder attention using the key, value, and query described above. Now we observe that from this construction, if h is in the form provided in (C.6), then Qphq1:wpos “Binplipxqq. In addition, we have Kpejq1:wpos “ e pos1 j “ Binpjq for 1ď j ďm. Thus, by construction of V,K0,V0, if lipxq ď m, the attention attends to position lipxq in the embedding. The value function for this position satisfies V pelipxqqscr2 “ e sym1 lipxq “ 1|A|pxlipxqq. Thus, in this case Fph,θq computes the desired output in (C.15). On the other hand, if lipxqąm, then the attention will attend to the null position, as QphqJK0“wpos´1, and the largest possible score for all other positions is wpos´2. In this case, (C.15) holds again. It is also easy to check that the desired bound on }θ}1 would hold.
Finally, we implement step 5) of the outline in Section 4.2 in the following lemma.
Lemma C.8. In the setting of Theorem 4.1 and Lemma C.7, consider any timestep i and any h output by the function in Lemma C.7 taking the form in (C.15). Then there is a function f with parameters θ consisting of a constant number of feedforward ReLU layers satisfying the following:
fph,θqst“1|Z|pzipxqq fph,θqsym1“1|A|paipxqq fph,θqpos2“Binplipxqq
(C.16)
At all other coordinates, Fph, θq takes values 0. Furthermore, the parameters satisfy }θ}1“Op|Z|`|A|`wposq.
Proof. It suffices to construct a sequence of layers which performs the following operations:
1) Compute the following vector vPR3:
v“
$
’ ’ ’ ’ ’ ’ &
’ ’ ’ ’ ’ ’ %
»
–
1
0
0
fi
fl if hscr41 “1
»
–
0
hscr42 1´hscr42
fi
fl if hscr41 “0
Note that v encodes the location of the symbol aipxq, as aipxq“ui1pxq if i1ą0, aipxq“xlipxq if i1“0 and lipxqďm, and aipxq“r∅s otherwise. The vector v is a one-hot vector indicating which of these three cases holds.
2) We can take v1 and compute AND with all bits of hscr1 , which computes 1|A|pui1pxqq“1|A|paipxqq if i1ą0, and 0 otherwise.
3) We take v2 and compute AND with all bits of hscr2 , which computes 1|A|pxlipxqq if v2“1, and 0 otherwise.
4) We take v3 and compute AND with all bits of 1|A|pr∅sq, which computes 1|A|paipxqq if v3“1.
5) We add the outputs of 2), 3), and 4) together, which gives 1|A|paipxqq. We copy this quantity into the output coordinates indexed by ¨sym1 . Then we set coordinates not listed in (C.16) to 0, producing the desired output.
Each of these operations can be computed by a constant number of feedforward ReLU layers, with total parameter norm satisfying }θ}1“Op|Z|`|A|`wposq.
Proof of Theorem 4.1. We construct a neural net to compute any Turing machine with all-layer margin lower bound 1polypk,|A|,logTq and apply Lemma 2.3 to turn this into a statement about statistically meaningful approximation.
For our Turing machine construction, we follow the outline laid out in Section 4.2. Fix any GPG. As mentioned, we first consider the case where w“wTM exactly, as overparameterization is easy to deal with by always designating some subset of extra coordinates to be 0. We construct a transformer pF to computeG. First, we note that Lemma C.1 constructs a layer to compute the functionality described in 1). Next, the layer in Lemma C.2 performs the functionality in 2). Likewise, Lemmas C.3, C.7, C.8 construct layers which perform 3), 4), and 5). Thus, by applying the layers constructed from these lemmas in sequence, we obtain a transformer such that the output oT contains an onehot encoding for zT pxq: 1|Z|pzT pxqq. We can now apply a linear weight vector θcls on the output to obtain θJclsoT , where pθclsqz“1 for accept states zPZterm and pθclsqz“´1 for reject states. For inputs xPX , by our construction this computes the desired TMpxq. Next, following Theorem 3.1, we insert correction functions (Definition D.1) between every group of constructed layers, which can be implemented via two feedforward ReLU layers following Proposition 3.4. The parameters for all correction functions add total }¨}1-norm at most polypk,|A|,logTq. Let pFpx,pθq denote the transformer constructed this way, with parameterspθ. Note that for all xPX , pFpx,pθq“2Gpxq´1.
Next, there are several steps remaining to convert pF into the fixed architecture F trw,d,T . First, we need to convert the layers in pF into transformer layers. This is achievable because every single decoder self-attention or encoder-decoder attention layer or feedforward ReLU module can be converted into a transformer layer by setting the two unused modules in the transformer layer to implement the identity function. This only increases the }¨}1-norm by polypk,|A|,logTq. Note that in particular, we can perform this conversion such that the correction functions form the last 2 feedforward ReLU layers in every transformer layer. The first 3 layers in the transformer layer correspond to ones constructed in the lemmas. Second, we need to expand the dimension to a consistent width w. This is achievable by padding each layer with coordinates designated to be 0, without affecting any of the }¨}1-norm bounds on the parameters. Third, we need to expand the depth to a fixed depth d. We can achieve this by appending transformer layers which compute the identity function (and also include correction functions) as needed.
Now we aim to apply Theorem D.6 by viewing the transformer as a very deep network with depth d“OpT logTq, by applying each of the steps in the transformer computation in sequence. Note that our construction for the transformer layers is such that we can view the self-attention, encoder-decoder attention, and single feedforward ReLU layer as a single function in the setting of Theorem D.6. The correction function corresponds to the last 2 feedforward ReLU layers in the transformer layer. (We observe that there are actually m layers which depend on the input x, not a single layer f0 as in the setting of Theorem D.6, but this is a minor difference where the same argument of Theorem D.6 still easily applies.) Note that this network uses layer-based weight sharing, which is handled by Theorem D.6. Furthermore, the depth of this network doesn’t affect the all-layer margin because Theorem D.6 doesn’t depend on the number of layers. We also observe that Condition D.4 holds for λ“polyp|Z|,|A|,logTq, because all of the intermediate layers are sparse binary vectors with at most |Z|`|A|`logT nonzero entries. Finally, it remains to check that Condition D.3 can hold for all of the defined layers for parameters that are polynomial in |Z|,|A|,logT . This is straightforward to check for transformer layers where the attention layers have parameters 0, as standard results on the Lipschitzness of a single ReLU network would apply. For layers where the functionality comes from the attention mechanism, we observe that for valid inputs xPX , the largest attention score is always greater than the second largest by a margin of 1. Furthermore, ties only occur when all of the value vectors for the attended positions are already the same. As a result, the positions attended to by the layer will not change unless we perturb the parameters and inputs by Ωppoly´1p|Z|,|A|,logTqq. This reasoning can be used to conclude that Condition D.3 with Lipschitz constants polyp|Z|,|A|,logTq, and distance parameters Ωppoly´1p|Z|,|A|,logTqq holds. As a result, the all-layer margin bound from applying Theorem D.6 will also be Ωppoly´1p|Z|,|A|,logTqq, as desired. Finally, applying Lemma 2.3 with γ“Ωppoly´1p|Z|,|A|,logTqq and using the fact that the parameter }¨}1-norms are bounded by α gives the desired result.

heading: D ALL-LAYER MARGIN LOWER BOUNDS VIA CORRECTION FUNCTIONS
text: We consider a generalized architecture for a d-layer network as follows. Let f0 :XˆΘ0ÑRw map space of inputs xPX and parameters θPΘ0 to w-dimensional space. For simplicity we assume all intermediate layers have dimension w, and let fi :RwˆΘiÑRw be the i-th function in the neural net for dą iě1. We define fd to output values in R. Let θ“pθ0,...,θdqPΘ denote the full vector of parameters. The i-th hidden layer hi computes the following value, defined recursively:
h0px,θq“f0px,θ0q hipx,θq“fiph0px,θq,...,hi´1px,θq,θiq
The model computes output hdpx,θq. We will assume the existence of “correction” functions ζ parameterized by ξ“pξ0,...,ξd´1qPΞ0ˆ¨ˆΞd´1 which correct errors in the model output for inputs X : Definition D.1 (Correction functions). Let F 1 :XÑR be a model defined by layer functions f0,...,fd. Then ζ0,...,ζd´1 :RwÑRw, ξ is a set of correction functions and parameters for F 1, θ with radius σζ if for all iPrd´1s,xPX and phPRX satisfying }ph´hipx,θq}2ďσζ,
ζipph,ξiq“hipx,θq We now define the function output F with correction layers recursively by
g0px,θ,ξq“f0px,θ0q rhipx,θ,ξq“ζipgi´1px,θ,ξq,ξiq @0ďiďd´1 gipx,θ,ξq“fiprh0px,θ,ξq,...,rhi´1px,θ,ξq,θi,ξiq @1ďiďd Fpx,θ,ξq“gdpx,θ,ξq
(D.1)
We note that for all xPX , Fpx,θ,ξq“hdpx,θq.
The key observation is that by adding correction layers to the model, we can transform a model with possibly small all-layer margin on the input data to one with large all-layer margin. We first need to characterize the Lipschitzness of the individual layers. Definition D.2. We say that a function fp¨,θq :DÑDout is pκθ,µ,σh,σθq-nice on HĎD with respect to |||¨||| if the following hold:
}fph,θq´fph,pθq}2ďκθ}θ´pθ}2maxt|||h|||,1u @}θ´pθ}ďσθ,hPH
}fph,pθq´fpph,pθq}2ďµ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ h´ph ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ @ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ h´ph ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ˇ ďσh,}θ´pθ}ďσθ,hPH
We will focus on the following norm on tuples of inputs pv1,...,viq, where hj PRw for all jPris:
|||pv1,...,viq|||“max j }vj}2 (D.2)
We analyze the function F output by a model with correction layers satisfying the following assumptions: Condition D.3. There are constants κθ,κξ,µ,σh,σθ,σζ such that the following hold.
For iě1, suppose that fi is pκθ,µ,σh,σθq-nice at θi on ph0,...,hi´1qpX q with respect to |||¨|||.
In addition, suppose that f0 satisfies }f0px,θq´f0px,pθq}2ďµ0}θ´pθ}2 for all xPX ,θPΘ0.
Furthermore, suppose that for all i, ζi satisfies }ζiph,ξiq´ζiph,pξq}2ďκξmaxt}h}2,1u}ξi´pξ}2 for all pξ with }ξi´pξ}2ďσξ and hPRw.
These conditions are all standard Lipschitzness-based conditions on the individual layer functions. Our lower bound for the all-layer margin will be expressed in terms of the constants here.
We will also need to assume a bound λ on the norms of each of the layers computed by hi. Condition D.4. The norms of the true layer values are bounded, that is, Dλ such that for all 0ď iďd and xPX ,
maxt}hipx,θq}2,1uďλ (D.3)
We will also consider models with weight sharing, which allows our analysis to apply to architectures such as the transformer in Section 4. Definition D.5 (Layer-based weight sharing). Let Θ1ĎRw1 , Θ0ĎRw0,...,ΘdĎRwd be some spaces of real-valued parameters. Suppose we wish to perform copying on parameters θ1PΘ1 to produce parameters θ“pθ0,...θdqPΘ“Θ0ˆ¨¨¨Θd, where θi is the set of parameters given to layer function fi. We say that a tuple of functions τ“pτ0,...,τdq :Θ1ÑΘ is a layer-based weight sharing scheme if each τi is of the form
τipθ1q“pθ1π1,...,θ 1 πbi q (D.4)
where π1,...,πbi is a set of distinct indices taking values in rw1s. Note that this ensures that parameters are not duplicated within a layer.
We will now prove our main lower bound for the all-layer margin based on inserting correction functions at every layer. Theorem D.6. In the above setting, suppose that Conditions D.3 and D.4 hold for a function F in the form given by (D.1) parametrized by θ with correction layers ζ0,...ζd´1 parameterized by ξ with correction radius σζ ă 1. Suppose that Fpxq P t´1,`1u @x PX . Then for all x PX , we can bound the all-layer margin of F (defined in (2.1))as follows:
ρF ppθ,ξq,x,1pFpx,θ,ξqě0qqěmint λ µ0 , σζ µ0 ,σθ,σξ, 1 2κθ , σζ 2κθλ , σh 2κξλ , σζ 4λµκξ , 1 4µκξ u (D.5)
Here the subscript F makes it explicit that the all-layer margin is for the architecture F . Furthermore, if we consider any layer-based weight-shared model F 1px,θ1qfiFpx,τp1qpθ1q,τp2qpθ1qq for valid weight-tying mappings τp1q, τp2q (Definition D.5), the same bound holds for ρF 1pθ1,x,1pF 1px,θ1qě0qq.
Our proof will first consider the case without weight sharing. We use pθ“ppθ0,...,pθdq and pξ“ppξ0,...,pξd´1q to denote a perturbed set of parameter vectors. Furthermore, define the partially perturbed parameter sets pθifippθ0,...,pθi,θi`1,...,θdq andpξifippξ0,...,pξi,ξi`1,...,ξdq. We also usepθ´1fiθ andpξ´1fiξ when convenient. We consider perturbations such that the following norm bounds hold:
}pθ0´θ0}2ďmint λ µ0 , σζ µ0 u (D.6)
}pθi´θi}2ďmintσθ, 1 2κθ , σζ 2κθλ u (D.7)
}pξi´pξi}2ďmintσξ, σh 2κξλ , σζ 4λµκξ , 1 4µκξ u (D.8)
We show that such perturbations won’t change the label predicted by the model, and so therefore the minimum of these quantities immediately gives a lower bound on the all-layer margin. Our proof will be by induction, with the following lemma providing the base case. Lemma D.7. In the setting of Theorem D.6, suppose that (D.6) holds. Then the following hold:
rh0px,pθ,ξq“h0px,θq }g0px,pθ,pξq´h0px,θq}2ďmintλ,σζu
The next lemma provides the inductive step. Starting with the base case, we show that because of the presence of the correction functions, the perturbations with our given bounds won’t change the next layer output by too much. This allows the correction function to fix the output of the next layer, and this argument can extend inductively. Lemma D.8. In the setting of Theorem D.6, fix some 1ď iďd. Suppose that for all 0ď jă i, it holds that for all xPX ,
rhjpx,pθ,pξj´1q“hjpx,θq (D.9) and
}gjpx,pθ,pξq´hjpx,θq}2ďmintλ,σζu
In addition, suppose that pθ,θ,pξ,ξ satisfy (D.7) and (D.8). Then it follows that for all xPX ,
}gipx,pθ,pξq´hipx,θq}2ďmintλ,σζu Furthermore, for 1ďiďd´1, we additionally have
rhipx,pθ,pξi´1q“hipx,θq
Combined, the two lemmas above allow us to inductively show that the prediction of the model is not changed whenever the perturbations are bounded by (D.6), (D.7), and (D.8). Next, we show that this translates directly to an all-layer margin lower bound. Lemma D.9. In the setting of Theorem D.6, suppose there exist norm bounds a0,...,ad, b0,...,bd´1 such that whenever }pθi´θi}2ďai and }pξi´ξi}2ďbi, |Fpx,θ,ξq´Fpx,pθ,pξq|ă1 for all xPX . Then we obtain the following lower bound on the all-layer margin, for all xPX :
ρF ppθ,ξq,x,1pFpx,θ,ξqě0qqěminta0,...,ad,b0,...,bd´1u The same lower bound applies if we consider models that use layer-based weight sharing, defined by F 1px,θ1qfiFpx,τp1qpθ1q,τp2qpθ1qq for valid weight-tying mappings τp1q, τp2q (Definition D.5).
We can combine these steps to formally complete the proof of Theorem D.6.
Proof of Theorem D.6. Assuming the perturbation bounds (D.6) (D.7), and (D.8) hold, we can apply induction with Lemma D.7 as the base case and Lemma D.8 as the inductive step to conclude that |Fpx,pθ,pξq´Fpx,θ,ξq|ďσζă1 for all xPX . We can now apply Lemma D.9 to obtain the desired bound on the all-layer margin.
We fill in the proofs of the supporting lemmas below.
Proof of Lemma D.7. By our definitions and Condition D.3, we have
}g0px,pθ,pξq´h0px,θq}2“}f0px,pθ0q´f0px,θ0q}2ďµ0}θ0´pθ0}2ďmintλ,σζu Now we can apply the Definition D.1 of the correction function to get
rh0px,pθ,ξq“ζ0pg0px,pθ,pξq,ξ0q“h0px,θq
Proof of Lemma D.8. By expanding the expression for hi, we observe that
hipx,θq“fiph0px,θq,...,hi´1px,θq,θiq “fiprh0px,pθ,ξq,rh1px,pθ,pξ0q...,rhi´1px,pθ,pξi´2q,θiq (D.10)
We obtained the equality via (D.9). Now we write
gipx,pθ,pξq“fiprh0px,pθ,pξq,...,rhi´1px,pθ,pξq,pθiq (D.11)
We subtract the two expressions and add and subtract fiprh0px,pθ,ξq,rh1px,pθ,ξ0q...,rhi´1px,pθ,ξi´1q,pθiq to obtain
gipx,pθ,pξq´hipx,θq“E1`E2 where
E1fifiprh0px,pθ,pξq,...,rhi´1px,pθ,pξq,pθiq ´fiprh0px,pθ,ξq,rh1px,pθ,pξ0q...,rhi´1px,pθ,pξi´2q,pθiq
E2fifiprh0px,pθ,ξq,rh1px,pθ,pξ0q...,rhi´1px,pθ,pξi´2q,pθiq ´fiprh0px,pθ,ξq,rh1px,pθ,pξ0q...,rhi´1px,pθ,pξi´2q,θiq
We first boundE1. We note that for all 0ďjďi´1
}rhjpx,pθ,pξq´rhjpx,pθ,pξj´1q}2“}ζjpgjpx,pθ,pξq,pξjq´ζjpgjpx,pθ,pξq,ξjq}2 ďκξmaxt}gjpx,pθ,pξq}2,1u}pξj´ξj}2
The last inequality used Condition D.3 and }pξj´ξj}2ďσξ. Now definingH1fiprh0px,pθ,pξq,...,rhi´1px,pθ,pξqq andHfiprh0px,pθ,ξq,rh1px,pθ,pξ0q...,rhi´1px,pθ,pξi´2qq, it follows that
ˇ
ˇ
ˇ
ˇ
ˇ ˇH´H1 ˇ ˇ ˇ ˇ ˇ
ˇ“ max 0ďjďi´1 κξmaxt}gjpx,pθ,pξq}2,1u}pξj´ξj}2
Plugging in }gjpx,pθ,pξq}2ď}hjpx,θq}2`}gjpx,pθ,pξq´hjpx,θq}2ď2λ, λě1, and }pξj´ξj}2ď σh2κξλ , we obtain |||H´H1|||ďσh. Furthermore, we note thatH Pph0,...,hi´1qpX q, so we can apply Condition D.3 and Definition D.2 to obtain
}E1}2“}fipH1,pθiq´fipH,pθiq}2 ďµ ˇ ˇ ˇ ˇ ˇ ˇH´H1 ˇ ˇ ˇ ˇ ˇ ˇ (since }pθi´θi}2ďσθ and |||H´H1|||ďσh)
ď2λµκξmax j }pξj´ξj}2
Next, we boundE2 by applying Condition D.3 and Definition D.2 again, using }pθi´θi}2ďσθ:
}E2}2“}fipH,pθiq´fipH,θiq}2 ďκθ}pθi´θi}2maxt|||H|||,1u “κθ}pθi´θi}2maxt}hjpx,θq}2ujYt1u ďκθ}pθi´θi}2λ
where we applied Condition D.4. By triangle inequality, follows that
}gipx,pθ,pξq´hipx,θq}2ď}E1}2`}E2}2 ďκθ}pθi´θi}2λ`2λµκξmax
j }pξj´ξj}2
Now by the assumptions on }pθi´θi}2 and }pξj´ξj}2, we can check that the r.h.s. is bounded by mintλ,σζu. Finally, we note that by Definition D.1 of the correction function, we have
rhipx,pθ,pξi´1q“ζipgipx,pθ,pξq,ξiq“hipx,θq
where we used the fact that }gipx,pθ,pξq´hipx,θq}2ďσζ.
Proof of Lemma D.9. Note that if }pθ,ξq´ppθ,pξq}2ă āfiminta0,...,ad,b0,...,bd´1u, then by the conditions of the lemma, |Fpx,θ,ξq´Fpx,pθ,pξq|ă1. However, because Fpx,θ,ξqPt´1,`1u for all xPX , the sign of the output is unchanged, which means Fpx,θ,ξqFpx,pθ,pξqą0. This means that we must perturb pθ,ξq by }¨}2-norm at least ā to satisfy the constraint in the all-layer margin definition, giving us the lower bound. We note that a similar argument applies to layer-based weight sharing because there are no parameters shared within a layer, so if the perturbation to θ1 has `2 norm less than ā, the parameters in τp1qpθ1q, τp2qpθ1q will also have a perturbation of at most ā in each layer. The same reasoning as before then applies.

Review summaries:
This paper studies the approximation of boolean circuits and Turing machines using neural networks. To this end, the authors propose a new notion of approximation criteria -- statistically meaningful (SM) approximation -- that specifies that the function class is both learnable and has a small bias in the sense of classical approximation theory. For both the boolean circuits and Turing machines, the authors explicitly construct two classes of neural networks, based on feedforward network and transformers respectively, that achieve SM approximation. 

This paper proposes a definition of "statistically meaningful approximation" or SM-approximation which combines learnability, generalization ability and expressivity (approximation accuracy) in a straightforward way.  Two theorems on SM-approximation are formulated and proven, one for approximating Boolean circuits and one for approximating a general Turing machine computation with a transformer network.  It is argued that the new definition has technical advantages.

The paper proposes a novel concept called statistically meaningful approximation. Roughly speaking, SM approximation means that performing empirical risk minimization over some properly chosen surrogate loss would result in a hypothesis with small population risk. Then the paper develops necessary tools and proves two results: (1). fully-connected neural networks can SM approximate boolean circuits with a sample size that is poly in the number of gates and $\log$ in the width and depth of the circuit; (2). transformers can SM approximate Turing machines with a sample size that is poly in the number of states, alphabet size, and the log of the computation steps.