Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers

Introduction

Dating back to the seminal works on universal approximation , 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) , graph neural nets , convolutional networks , residual networks , transformers , and neural ODEs .

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 . 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 . 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 – any finite-precision, finite-width RNN induces a finite-space streaming algorithm corresponding to running the RNN on the inputs. However, streaming lower bounds tell us that finite-space streaming algorithms are not powerful enough to simulate Turing machines, and hence finite-precision, finite-width RNNs cannot either. As another example, Park et al. 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 $2^{n}$ input-labeling pairs, but only $2^{o(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, a rigorous analysis of optimization is unresolved even for simple two-layer nets . Global optimization analyses such as NTK do exist , but there is a large body of theoretical and empirical work showing that neural networks can generalize much better than NTK analyses can hope to prove . 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 ${\mathcal{F}}$ and a finite sample of training data. SM approximation requires existence of a loss whose empirical risk minimizer in ${\mathcal{F}}$ leads to a 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 $\epsilon$ 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 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 . Furthermore, VC dimension-based bounds would scale polynomially in the number of parameters in the network , which is problematic because for practical optimization concerns, neural nets are typically overparameterized in terms of width . 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 transformers which SM approximate these Turing machines. The sample complexity of the approximation depends on a polynomial in $\log T$ and the sizes of the state space and the alphabet of the Turing machine. Though constructions for approximating Turing machines from prior work have not been formally studied from a sample complexity perspective, existing bounds would depend at least linearly on $T$. Furthermore, our construction only uses $\log\log T$ precision, compared to at least $\log T$ 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 . 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 is 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.

Classifical approximation theory for neural networks has a long history. Hornik et al. , Cybenko , and Leshno et al. show that neural nets with one hidden layer are universal approximators but require the hidden layer size to grow exponentially in input dimension. Barron 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. , Ji et al. prove recent related developments in this direction of universal approximation.

Many works study benefits of deep networks over shallow ones . Bengio and Delalleau show separation for exact representation, whereas Telgarsky shows separation for approximate representations with univariate inputs. Eldan and Shamir 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 theoretic questions, Vardi and Shamir show that proving constant depth separations may be hard. Malach et al. 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 from approximation theory can be 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 . Yun et al. show that $\Theta(n)$ parameters are sufficient to memorize $\Theta(n)$ training points for ReLU nets with at least 3 layers, and Park et al. reduce the parameter requirement to sublinear in $n$. Similar results have been proven for residual architectures and convolutional nets . Bartlett et al. 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-product networks .

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 and Sontag shows that RNNs are Turing complete but leverages infinite precision in the hidden activations. Chen et al. 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 . Recent works have also proven results for generating or recognizing formal languages with finite-precision neural nets , but these results do not consider Turing machines or analyze statistical properties of their constructions. Concurrent work 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.

2 Notation

Statistically meaningful approximation

The issue with this classical notion of approximation is that it allows solutions which use infinite precision (or other potential unrealistic characteristics). Because of these drawbacks, even if ${\mathcal{F}}$ approximates ${\mathcal{G}}$, it does not mean that we can use ${\mathcal{F}}$ to fit the target function from ${\mathcal{G}}$ with a good sample complexity.

This work studies a stronger notion of approximation, statistically meaningful (SM) approximation, to eliminate statistical issues with fitting $G$ on a finite sample. SM-approximation requires that ${\mathcal{G}}$ is learnable via empirical risk minimization using models from ${\mathcal{F}}$, when data is generated from $P$.

Though Definition 2.2 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. For example, in the realizable PAC-learning case, there is no notion of an approximating family ${\mathcal{F}}$ – the setting only cares about fundamental learnability of ${\mathcal{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 ${\mathcal{F}}$ achieves near-zero loss, whereas there is no such requirement in PAC-learning settings.

We modified the definition in to consider perturbations $\delta$ in parameter space, whereas Wei and Ma consider perturbations to the hidden layers. The parameter-space formulation is simpler and subsumes the results in . Our formulation also accounts for weight sharing, which is important for our Turing machine results, whereas the formulation of could not.

Here $\widetilde{O}$ hides poly-logarithmic factors in the arguments, in this case, $\textup{poly}\log(\frac{\alpha^{2}\log(p)}{\gamma^{2}\epsilon^{2}})$ factors. The proof follows and 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.4 to prove that neural nets can SM-approximate Boolean circuits and Turing machines.

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. A boolean circuit $G:\{0,1\}^{m}\to\{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 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 . 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\geq m$. We consider the following class of boolean circuits:

The following theorem states that feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity polynomial in the circuit size.

Consider the class ${\mathcal{G}}_{q,r,s}$ of size-$s$,width-$r$, and depth-$q$ layered boolean circuits, and the class ${\mathcal{F}}_{0pt,0pt,\alpha}$ of neural nets above. Suppose $0pt\gtrsim r$, $\alpha\asymp s$, and $0pt\asymp q$.

We note that the bound in Theorem 3.1 only scales logarithmically in the width $0pt$ of the network, even if $0pt$ is arbitrarily greater than the circuit width $r$. This ensures that even heavily overparameterized nets will have low sample complexity of the approximation.

There are two key steps in the proof. First, given any layered circuit $G\in{\mathcal{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.

In the setting of Theorem 3.1, let $G$ denote the layered boolean circuit, which we aim to compute using a neural net. Let $g_{i}:\{0,1\}^{r_{i-1}}\to\{0,1\}^{r_{i}}$ denote function computed between the $i-1$-th and $i$-th layers of $G$, which we assume have $r_{i-1}$ and $r_{i}$ gates, respectively, so $G=g_{q-1}\circ\cdots\circ g_{1}$.

Then there exist functions $f_{1},\ldots,f_{q-1}$, where each $f_{i}$ is computed by a feedforward ReLU net with two linear and activation layers, such that for all $i\in[q-1]$ and $x\in\{0,1\}^{m}$, $f_{i}\circ\cdots\circ f_{1}(x)=g_{i}\circ\cdots\circ g_{1}(x)$. Thus, the composition $F(\cdot,\theta)\triangleq f_{q-1}\circ\cdots\circ f_{1}$ satisfies $F(x,\theta)=G(x)$ for all $x\in\{0,1\}^{m}$. Note that we omitted the dependency of $f_{q-1},\ldots,f_{1}$ on parameters $\theta$ for simplicity.

Recall that the all-layer margin $\rho_{F}(\theta,x,G(x))$ measures the stability of the output $F(x,\theta)$ to perturbations in to $\theta$, and, by Lemma 2.4, it suffices to show that $F$ has large all-layer margin on $x\in\{0,1\}^{m}$. 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 $F(\cdot,\theta)$, with possibly small all-layer margin on $x\in\{0,1\}^{m}$, into a new architecture and parameter set $F^{\prime}(\cdot,\theta^{\prime})$, with provably large all-layer margin on $x\in\{0,1\}^{m}$, such that $F^{\prime}(x,\theta^{\prime})=F(x,\theta)$ on all inputs $x\in\{0,1\}^{m}$. The construction relies on introducing new layers to $F$ to obtain $F^{\prime}$ and increases the total number of layers by only a constant factor. This step of the proof is formally stated in the following lemma.

In the setting of Lemma 3.2, let $F(\cdot,\theta)=f_{q-1}\circ\cdots\circ f_{1}$ be the neural net with parameters $\theta$ constructed to compute the circuit $G$. There exist “correction functions” $\zeta_{1},\ldots,\zeta_{q-2}$, where $\zeta_{i}$ is computed by a neural net with two activation and linear layers, such that the composition $F^{\prime}(\cdot,\theta^{\prime})\triangleq f_{q-1}\circ\zeta_{q-2}\circ f_{q-2}\circ\cdots\circ\zeta_{1}\circ f_{1}$ has large all-layer margin:$\rho_{F^{\prime}}(\theta^{\prime},x,G(x))\geq\frac{1}{\textup{poly}(s)}$ for all $x\in\{0,1\}^{m}$. Here $\theta^{\prime}$ denotes the collection of all parameters, and dependency of $f_{i},\zeta_{i}$ on $\theta^{\prime}$ is omitted for simplicity.

Now we will insert ReLU layers in $f$ to increase the all-layer margin to $\Omega(1)$. We use ReLU layers to implement the round function, which has the key property that $\textup{round}(z)=1\ \forall z\geq 2/3$.

We consider the following function $\widetilde{f}$, which inserts round between every layer in $f$:

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-layer margin:

In the setting above, $\widetilde{f}(1,(1,\ldots,1))=f(1,(1,\ldots,1))$ and $\rho_{\widetilde{f}}((1,\ldots,1),1,1)\geq\frac{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 $\delta_{i}\leq\frac{1}{3}$ for all $i$, the function output will not change because $\textup{round}(z)=1\ \forall z\geq\frac{2}{3}$. This immediately gives the all-layer margin lower bound $\frac{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” $\zeta$ between each layer satisfying the key property that $\zeta(h^{\prime})=h$ if $h$ is the intended output of the layer and $h^{\prime}$ is any perturbed value satisfying $\|h^{\prime}-h\|_{2}\leq\frac{1}{3}$. Since intended outputs of layers in the function constructed by Lemma 3.2 are binary-valued in $\{0,1\}^{0pt}$ 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 $x\in\{0,1\}^{m}$. 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.

SM approximation of Turing machines with transformers

In this section, we show that transformers SM-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 in $T$ . Thus, we obtain an exponential improvement in the dependency on $T$.

We briefly describe a Turing machine; see for a more thorough survey. A Turing machine is a model for computation specified by a tuple $({\mathcal{Z}},{\mathcal{A}},S,{\mathcal{Z}}_{\textup{term}})$ containing a set of states ${\mathcal{Z}}$, a tape alphabet ${\mathcal{A}}$, a transition function $S:{\mathcal{Z}}\times{\mathcal{A}}\to{\mathcal{Z}}\times{\mathcal{A}}\times\{-1,+1\}$, and set of terminal states ${\mathcal{Z}}_{\textup{term}}$ 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 . Given an input $x\in{\mathcal{A}}^{*}$ 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 $\textup{TM}_{({\mathcal{Z}},{\mathcal{A}},S,{\mathcal{Z}}_{\textup{term}})}$ denote the function computed by the Turing machine, which produces an output in $\{0,1\}$ (if the machine halts). Fixing the alphabet ${\mathcal{A}}$, we consider the class of binary functions computed by Turing machines with at most $k$ states terminating in $T$ steps:

Note that we can assume the input sequences $x$ also have length at most $T$, as this is the maximum computation time of the Turing machine and the maximum amount of symbols the Turing machine can read.

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 functions $K,V,Q$, each, computing a linear transformation. We omit parameters here for simplicity. For a single decoder timestep, the attention layer takes two types of inputs: a sequence of previously-computed representations $h_{1},\ldots,h_{i}$, and a current input representation $h^{\prime}$. The layer applies the key, value, and query functions as follows:

where $K_{0}$ and $V_{0}$ are fixed “null” key and value vectors which are learned parameters of the layer. Letting ${\mathcal{J}}$ denote the set of indices $\{j:\tau_{j}=\max\{\tau_{0},\ldots,\tau_{i}\}\}$, the attention layer performs hard-max attention to compute the output, as follows: $\textup{Attn}(h^{\prime},(h_{1},\ldots,h_{i}))=h^{\prime}+\frac{1}{|{\mathcal{J}}|}\sum_{j\in{\mathcal{J}}}v_{j}$.

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 $h^{(j)}_{t}$ 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 $\textup{Attn}(h^{(j)}_{i},(h^{(j)}_{1},\ldots,h^{(j)}_{i}))$. Letting $e_{1},\ldots,e_{m}$ denote the encoder outputs, encoder-decoder self-attention at the $(j+1)$-th layer and $i$-th step would compute $\textup{Attn}(h^{(j)}_{i},(e_{1},\ldots,e_{m}))$.

Transformer layers. We use feedforward layers which apply 3 standard ReLU layers, as follows: $\textup{FF}(h)=\phi(W_{3}\phi(W_{2}\phi(W_{1}h+b_{1})+b_{2})+b_{3})$. 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. Letting $H^{(j)}_{i}=(h^{(j)}_{1},\ldots,h^{(j)}_{i})$ denote the output after the $j$-th transformer layer for timesteps $1\leq t\leq i$, and $\theta^{(j)}$ the parameters, we compute

Note that we included the explicit dependence of the attention layers on the parameters for completeness. We now set $h^{(j+1)}_{i}=\textup{Tr}(h^{(j)}_{i},H^{(j)}_{i},(e_{1},\ldots,e_{m}),\theta^{(j+1)})$.

Decoder outputs. We consider $0pt$-layer decoders, so $o_{i}\triangleq h^{(0pt)}_{i}$ denotes the output of the decoder at time $i$, which is also inputted to the decoder at time $i+1$ as follows: $h^{(0)}_{i+1}=h^{(0pt)}_{i}+\beta(i+1)$. The initial decoder input $h^{(0)}_{0}$ is a trainable parameter. The decoder runs for a fixed number of timesteps $T^{\prime}$ and outputs prediction $\theta_{\textup{cls}}^{\top}h^{(0pt)}_{T^{\prime}}$. For simplicity, we assume $T^{\prime}=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 . The architecture we study is similar to ones studied by .

We use $x\mapsto F_{0pt,0pt,T}(x,\theta)$ to denote the described transformer architecture with parameters $\theta$, $0pt$-dimensional hidden layers, $0pt$ transformer layers in the decoder, and $T$ decoder steps. This leads to the following class of transformer functions: ${\mathcal{F}}_{0pt,0pt,\alpha,T}=\{x\mapsto F_{0pt,0pt,T}(x,\theta):\|\theta\|_{1}\leq\alpha\}$. The following theorem states that this class of transformers SM-approximates the Turing machine family ${\mathcal{G}}$ defined in (4.1) with sample complexity polynomial in $\log T$, $k$ and $|{\mathcal{A}}|$.

In the setting above, consider the class ${\mathcal{G}}$ of functions computed by Turing machines with at most $k$ states, alphabet ${\mathcal{A}}$, and computation time bounded by $T$ steps for inputs $x\in{\mathcal{X}}$. Suppose that $0pt\gtrsim k|{\mathcal{A}}|+\log T$, $0pt\asymp\log T$, and $\alpha=\textup{poly}(k,|{\mathcal{A}}|,\log T)$.

2 Proof sketch for Theorem 4.1

Following Lemma 2.4, our goal is to construct a transformer which can simulate Turing machines with large all-layer margin, namely, $\Omega\left(\frac{1}{\textup{poly}(k,|{\mathcal{A}}|,\log T)}\right)$. The fundamental limitation of prior work towards attaining this is that the positional embeddings are required to store values as small as $\frac{1}{\textup{poly}(T)}$. 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 $\frac{1}{\textup{poly}(T)}$ because perturbing the layer by the small entries could change the prediction. Instead, we propose using $\textup{Bin}(i)$, the binary encoding of $i$ in $\lceil\log T\rceil$ 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. Fix a Turing machine $G\in{\mathcal{G}}$. We first require notation to describe the computation of $G$. For input $x\in{\mathcal{X}}$, let $z_{i}(x)$, $a_{i}(x)$ denote the Turing machine state and symbol under the tape head at the end of step $i$. We let $l_{i}(x)$ denote the location of the Turing machine head at the conclusion of step $i$. During the timestep, the Turing machine computes $S(z_{i-1}(x),a_{i-1}(x))$, writes a new symbol under the head at location $l_{i-1}(x)$, and moves the head either left or right. Let $u_{i}(x)$ denote the symbol written during timestep $i$, and $q_{i}(x)\in\{\textup{left},\textup{right}\}$ the movement direction of the head.

Following with several key modifications, we simulate the Turing machine using the transformer as follows. Each timestep will maintain the invariance that $o_{i}$ contains an encoding of $z_{i}(x),a_{i}(x)$, and $l_{i}(x)$. Given that this invariance holds until timestep $i$, the transformer simulates timestep $i+1$ of the Turing machine with the following steps:

Use feedforward layers to apply transition $S$ on $z_{i}(x)$ and $a_{i}(x)$, which can be read from $o_{i}$, to obtain $z_{i+1}(x)$, $u_{i+1}(x)$, and movement direction $q_{i+1}(x)\in\{\textup{left, right}\}$.

Using feedforward layers, compute $l_{i+1}(x)$ from $q_{i+1}(x)$ and the encoding of $l_{i}(x)$ in $o_{i}$.

Compute $a_{i+1}(x)$. We use decoder self-attention to search over past timesteps which wrote to $l_{i+1}(x)$. Our aim is to find $u_{i^{\prime}}(x)$, where $i^{\prime}=\max\{j\leq i+1:l_{j-1}(x)=l_{i+1}(x)\}$. We implement a binary search over past timesteps $j$, which is needed to find the largest $j\leq i+1$ where $l_{j-1}(x)=l_{i+1}(x)$. The binary search is performed over the bits of $i^{\prime}$ and can be implemented with $O(\lceil\log T\rceil)$ decoder self-attention layers, and the construction ensures large all-layer margin.

If no such $i^{\prime}$ from the previous timestep existed, we check whether $l_{i+1}(x)$ contained an input symbol using encoder-decoder attention and copy this input symbol if so.

If no symbols were found in 3) or 4), $l_{i+1}(x)$ must contain the blank symbol (meaning it wasn’t visited yet by the head). Thus, we have computed $a_{i+1}(x)$, so we have all the information needed to compute the new embedding $o_{i+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 $\{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 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.

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

Appendix A Proofs for Section 2

We bound the first and last term in parenthesis by applying (A.1), and the middle term is bounded by 0, by definition of $\widehat{F}$. It follows that

Thus, it remains to check the Rademacher complexity condition for applying Proposition 2.3. Fixing any $G\in{\mathcal{G}}$, define the function class ${\mathcal{L}}_{G}$ as in Definition 2.2.

Note that from the proof of Lemma 2.4, we would also obtain the following parameter-space all-layer margin generalization bound as a corollary, which may be of independent interest:

In the setting of Lemma 2.4, let $Q$ denote a distribution over $(x,y)$ pairs, with $(x_{i},y_{i})_{i=1}^{n}$ denoting a set of $n$ i.i.d. training samples from $Q$. With probability $1-\delta$ over the draw of the training samples, all classifiers $F(\cdot,\theta)\in{\mathcal{F}}$ which achieve zero 0-1 training loss satisfy

where $\xi\lesssim O\left(\frac{\log(1/\delta)+\log(n)}{\sqrt{n}}\right)$ is a low-order term.

The proof of Corollary A.1 simply follows by plugging in the coverning number bound on $\rho$ derived in the proof of Lemma 2.4 into Lemma 2.2 of .

Appendix B Proofs for Section 3

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.

In the setting of Theorem 3.1, let $G$ denote the layered boolean circuit, which we aim to compute using a neural net. Let $G_{i}:\{0,1\}^{r_{i-1}}\to\{0,1\}^{r_{i}}$ denote function computed between the $i-1$-th and $i$-th layers of $G$, which we assume have $r_{i-1}$ and $r_{i}$ gates, respectively. Let $f$ denote the following 2-layer neural net architecture, parameterized by $\theta=(W_{1},b_{1},W_{2},b_{2})$:

Then there exist $\theta$ with $\|\theta\|_{1}=O(r_{i})$ such that for any $h\in\{0,1\}^{r_{i-1}}$,

where $\widetilde{h}$ takes $h$ and appends $0pt-r_{i-1}$ zeros, and likewise for $\widetilde{G_{i}}(h)$.

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.

Our proof will construct a neural network to compute any boolean circuit with all-layer margin lower bound $\frac{1}{\textup{poly}(r,q)}$. By Lemma 2.4, this will be sufficient to guarantee meaningful approximation.

There are two steps in our construction: first, given any layered circuit $G\in{\mathcal{G}}_{q,r,s}$, we construct a neural net that directly simulates $G$ by computing the layers of $G$ one-by-one. Our construction shows that we can compute every layer in $G$ using two feedforward ReLU layers, and results in a neural net $\widehat{F}$ computing $G$, but with possibly small all-layer margin. The next step is to convert $\widehat{F}$ 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 $\widehat{F}$. These correction layers leverage the knowledge that unperturbed outputs of these layers should be contained in $\{0,1\}^{0pt}$ and perform elementwise rounding to map perturbed values back to $\{0,1\}^{0pt}$. 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 $\widehat{F}$ computing $G$ (with padding) mentioned above. The total $\|\cdot\|_{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 $\|\cdot\|_{1}$-norm at most $O(s)$.

Note that at this point, minor modifications are still required in order to apply Theorem D.6. The neural net output is in $\{0,1\}^{0pt}$, not $\{-1,1\}$; we can remedy this by setting the last layer to compute the linear transformation $z\mapsto 2z-1$ on the single non-padding coordinate corresponding to the output. Second, to make the depth of the architecture consistently $0pt$, 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 $0pt$. This finally gives us parameters $\theta$ with $\|\cdot\|_{1}$-norm bound $O(s+0pt)$, so that the set of constructed functions is contained in ${\mathcal{F}}_{0pt,0pt,\alpha}$. Thus, we showed that for $G\in{\mathcal{G}}_{q,r,s}$, there exists $\theta$ such that $F(x,\theta)=2G(x)-1$ for all $x\in\{0,1\}^{m}$.

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 $\widehat{\gamma}=\frac{1}{\textup{poly}(r,q)}\geq\frac{1}{\textup{poly}(s)}$ on the all-layer margin for every input $x\in\{0,1\}^{m}$. Finally, we directly apply Lemma 2.4 using $\gamma=\widehat{\gamma}$ to obtain the desired result. ∎

The following proposition will be used to construct basic gates in the circuit with a simple feedforward ReLU network.

Let $x=\begin{bmatrix}x_{1}\\ x_{2}\end{bmatrix}\in\{0,1\}^{2}$ be binary inputs to AND and OR gates. The following feedforward ReLU networks compute the AND and OR functions: $F_{\textup{AND}}(x)=\phi(x_{1}+x_{2}-1)$, and $F_{\textup{OR}}(x)=1-\phi(1-x_{1}-x_{2})$.

Each row of $W_{1}$ and value in $b_{1}$ will correspond to a single entry in the output of $\widetilde{G_{i}}$. The same applies for $W_{2},b_{2}$. $W_{2}$ will be set to a diagonal matrix with entries in $\{-1,0,1\}$. For the 0 entries which only serve to pad the dimension, we set corresponding values in $W_{1},b_{1},W_{2},b_{2}$ to be 0. For the remainder of the entries of $\widetilde{G_{i}}$ 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 $W_{1},b_{1},W_{2},b_{2}$ 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 $\textup{NOT}(z)=1-z$ for $z\in\{0,1\}$ on coordinate $j$, we can set the $j$-th row of $W_{1}$ to have -1 on the diagonal and 0 everywhere else, $(b_{1})_{j}=1$, $(b_{2})_{j}=0$, and $(W_{2})_{j,j}=1$. It is easy to check that $\|\theta\|_{1}=O(r_{i})$ with this construction. ∎

Appendix C Proof of Theorem 4.1

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 $z_{\textup{init}}$. We let $[\varnothing]\in{\mathcal{A}}$ 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 ${\mathcal{Z}}_{\textup{term}}$, at which the transformer will loop in that state until it hits a computation time $T$.

The position embedding $\beta(i)$ is defined formally so that $\beta(i)^{\textup{pos}_{1}}=\textup{Bin}(i)$, and $\beta(i)$ is 0 in all other coordinates. The encoder embedding matrix $E$ is such that

and $o_{i}$ has 0 at all other coordinates. Thus, the input $o_{i}+\beta(i+1)$ to the decoder at step $i+1$ is of the form

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 $\mathbf{0}$, and only the feedforward layers are instantiated.

Let ${\mathcal{O}}$ denote the set of decoder inputs in the form (C.3) encoding $z_{i-1}(x)$, $a_{i-1}(x)$, $l_{i-1}(x)$ for some timestep $i$. For parameters $\theta=(W_{1},b_{1},W_{2},b_{2})$, consider the following function computing a sequence of two feedforward ReLU layers: $f(h,\theta)=\phi(W_{2}\phi(W_{1}h+b_{1})+b_{2})$. There exist parameters $\theta$ such that for decoder inputs $h\in{\mathcal{O}}$,

Furthermore, $f(h,\theta)^{\textup{scr}}$ will contain a one-hot encoding for $q_{i}(x)$, and besides this, $f(h,\theta)$ is 0 at all other coordinates. The parameters satisfy $\|\theta\|_{1}=O(|{\mathcal{Z}}||{\mathcal{A}}|+w_{\textup{pos}})$.

and 0 everywhere else. The remaining rows of $w_{\textup{TM}}$ rows of $W_{1}$ simply implement the identity mapping. We choose $b_{1}$ so that its first $|{\mathcal{Z}}||{\mathcal{A}}|$ entries are -1, and all other entries are 0. We observe that from this construction, for all $h\in{\mathcal{O}}$ where $h$ encodes $z_{i-1}(x),a_{i-1}(x)$,

This is because before the ReLU, the first $|{\mathcal{Z}}||{\mathcal{A}}|$ entries of $W_{1}h$ will have 2 on the $(z_{i-1}(x),a_{i-1}(x))$-th entry and be bounded by 1 everywhere else, so adding $\alpha_{1}$ and applying the activation will zero out all but one entry.

Now it is simple to pick $W_{2}$ so that $f(h,\theta)$ is as desired because we can construct it to exactly encode the output of $S(z,a)$ for each of its first $(z,a)$ 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 $\textup{Bin}(l_{i}(x))$, given $\textup{Bin}(l_{i-1}(x))$ and $q_{i}(x)$.

In the setting of Theorem 4.1 and Lemma C.1 above, there is a function $f$ parameterized by $\theta$ composed of $O(w_{\textup{pos}})$ feedforward ReLU layers such that for any $h$ computed by the function in Lemma C.1 in the form (C.4) at timestep $i$,

At all other coordinates, $F(h,\theta)$ takes value 0. Furthermore, the parameters satisfy $\|\theta\|_{1}=O(w_{\textup{pos}}(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}}))$.

As the construction of Lemma C.1 encoded $q_{i}(x)$, the movement direction of the head, we can use feedforward ReLU layers to implement binary addition to either add or subtract 1 from $l_{i-1}(x)$. Let $v_{1},v_{2}$ denote the bits in the scratch dimensions indicating the head movement, where $v_{1}=1,v_{2}=0$ indicates left and $v_{1}=0,v_{2}=1$ indicates right. Then more specifically, we first use $O(w_{\textup{pos}})$ feedforward ReLU layers to compute $l_{i-1}(x)-v_{1}$, and then $O(w_{\textup{pos}})$ additional feedforward ReLU layers to compute $l_{i-1}(x)-v_{1}+v_{2}$. Note that the output would always be $l_{i}(x)$ by the definition of $v_{1},v_{2}$.

It remains to implement a module which computes $\textup{Bin}(j-v_{1})$ given $v_{1},\textup{Bin}(j)$, and $\textup{Bin}(j+v_{2})$ given $v_{2},\textup{Bin}(j)$ for any $j\in[T]$. We can express the binary addition by a depth-$O(w_{\textup{pos}})$ binary circuit, which can in turn be expressed by a neural net with $O(w_{\textup{pos}})$ layers where each weight matrix has $\|\cdot\|_{1}$-norm $(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}})$ (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 $\|\cdot\|_{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 $h\in w_{\textup{scr}}$,

In the setting of Theorem 4.1 and Lemma C.2 above, fix any timestep $i$ and define $i^{\prime}=\max\{1\leq t\leq i:l_{t-1}(x)=l_{i}(x)\}$. If $j$ such that $l_{t-1}(x)=l_{i}(x)$ exists, we define $i^{\prime}=0$ otherwise. Consider any $H_{i}=(h_{1},\ldots,h_{i})$, where $h_{t}$ 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 $\theta$ consisting of $O(w_{\textup{pos}})$ total self-attention and linear layers such that for all such $H_{i}$, the following holds:

At all other coordinates, $F(H,\theta)$ takes value . Furthermore, the parameters satisfy $\|\theta\|_{1}=O(w_{\textup{pos}}(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}}))$.

The proof plan will roughly implement a binary search to find $i^{\prime}$, leveraging the attention layers. The first step in the binary search is to verify whether $i^{\prime}>0$, described below.

In the setting of Lemma C.3, let $H_{i}=h_{1},\ldots,h_{i}$ be the input representations for timesteps $1,\ldots,i$. Suppose that each $h_{t}$ for $1\leq t\leq i$ satisfies the following:

Additionally, suppose that $h_{i}$ is of the form in (C.5). Then there is a function $f^{(0)}$ parameterized by $\theta$ such that

The function $f^{(0)}$ can be computed by a single decoder self-attention layer with $\|\theta\|_{1}=O(w_{\textup{pos}})$.

In the setting above and of Lemma C.3, let $H_{i}^{(j)}=h^{(j)}_{1},\ldots,h^{(j)}_{i}$ be the representations computed after the $j$-th group of layers for timesteps $1$ through $i$, for $0\leq j\leq w_{\textup{pos}}-1$. Suppose that each $h^{(j)}_{t}$ for $1\leq t\leq i$ satisfies the following:

In addition, suppose that $h^{(j)}_{i}$ satisfies:

with all other coordinates matching the quantities prescribed in (C.5). Then there is a function $f^{(j+1)}$ parameterized by $\theta$ such that

with all other coordinates matching those prescribed in (C.5). We note that $f^{(j+1)}$ consists of a single decoder self-attention layer followed by single feedforward ReLU layer, with $\|\theta\|_{1}=O(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}})$.

At the end of the $w_{\textup{pos}}$-th application of the binary search, we would have found $\textup{Bin}(i^{\prime})$ exactly. It remains to apply another attention layer which attends directly to timestep $i^{\prime}$ and copies $u_{i^{\prime}}(x)$.

In the setting above and of Lemma C.3, let $H_{i}=h_{1},\ldots,h_{i}$ be the representations computed after the $w_{\textup{pos}}$-th group of layers constructed in Claim C.5 for timesteps $1$ through $i$. Suppose that each $h_{t}$ for $1\leq t\leq i$ satisfies the following:

In addition, suppose that $h_{i}$ satisfies:

with all other coordinates matching the quantities prescribed in (C.5). Then there is a function $f^{(w_{\textup{pos}}+1)}$ parameterized by $\theta$ such that $f^{(w_{\textup{pos}}+1)}(h_{i},H_{i},\theta)$ computes the desired output in (C.6). Furthermore, $f^{(w_{\textup{pos}}+1)}$ consists of a single decoder self-attention layer followed by a single feedforward ReLU layer, and $\|\theta\|_{1}=O(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}})$.

Putting these together, we complete the proof of Lemma C.3.

We fill in the proofs of Claims C.4, C.5, and C.6 below.

To see that $f^{(0)}$ satisfies (C.8), observe that if $i^{\prime}>0$, $Q(h_{i})^{\top}K(h_{i^{\prime}})=w_{\textup{pos}}$ by (C.7) and construction of $Q,K$. On the other hand, $Q(h_{i})^{\top}K_{0}=w_{\textup{pos}}-1$. Thus, $\operatorname*{arg\,max}_{t}Q(h_{i})^{\top}K(h_{t})\in[i]$, which implies that $f^{(0)}(h_{i},H_{i},\theta)^{\textup{scr}_{4}}_{1}=1$ by the construction of $V$. In the other case where $i^{\prime}=0$, we note that $Q(h_{i})^{\top}K(h_{t})\leq w_{\textup{pos}}-2$ for all $1\leq t\leq i$, so the null position is attended to. By construction of $V_{0}$, this implies $f^{(0)}(h_{i},H_{i},\theta)^{\textup{scr}_{4}}_{1}=0$. As $V,V_{0}$ are 0 on all other coordinates, it follows that (C.8) holds. It’s also easy to observe that the $\|\theta\|_{1}$ is as desired. ∎

where Attn uses the constructed key, value, and query functions. We claim that $f^{(j+1),1}(h^{(j)}_{i},H^{(j)}_{i},\theta_{\textup{attn}})$ satisfies the following:

Case 1: $i^{\prime}=0$. In this case, we note that $l_{i}(x)$ never matches $l_{t-1}(x)$ for $1\leq t\leq i$. Thus, by construction of the first $w_{\textup{pos}}$ coordinates of $Q$ and $K$, the largest possible value of $Q(h^{(j)}_{i})^{\top}K(h^{(j)}_{t})$ is $w_{\textup{pos}}+j-1$, so the attention will always only attend to the null position, so the layer adds $V_{0}=\mathbf{0}$ to $h^{(j)}_{i}$, preserving its value. Note that $(h^{(j),\textup{scr}_{4}}_{i})_{3}=0$ in this case, which matches the desired behavior.

Case 2: $i^{\prime}>0$, and has $(j+1)$-th bit 0. In this case, we note that for all $t>i^{\prime}$, $Q(h^{(j)}_{i})^{\top}K(h^{(j)}_{t})\leq w_{\textup{pos}}+j-1$, because by definition such $t$ must satisfy $l_{t-1}(x)\neq l_{i}(x)$, so the first $w_{\textup{pos}}$ coordinates contribute at most $w_{\textup{pos}}-2$ to the dot product. On the other hand, if $t\leq i^{\prime}$, $t$ must have $(j+1)$-th bit 0, so $K(h^{(j)}_{t})_{w_{\textup{pos}}+j+1}=-1$. This doesn’t match the $(w_{\textup{pos}}+j+1)$-th bit of the query, so $Q(h^{(j)}_{i})^{\top}K(h^{(j)}_{t})\leq w_{\textup{pos}}+j-1$ again. Thus, in this case, the null position is attended to again. The same reasoning as Case 1 then applies.

Case 3: $i^{\prime}>0$ and has $(j+1)$-th bit 1. In this case, $\max_{t}Q(h^{(j)}_{i})^{\top}K(h^{(j)}_{t})=w_{\textup{pos}}+j+1$: for example, $t=i^{\prime}$ 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(h^{(j)}_{t})^{\textup{scr}_{4}}_{3}=1$, which matches the $(j+1)$-th bit of $i^{\prime}$. Thus, (C.14) holds.

Finally, to complete the proof we simply append an additional feedforward ReLU layer which copies the value $f^{(j+1),1}(h^{(j)}_{i},H^{(j)}_{i},\theta_{\textup{attn}})^{\textup{scr}_{4}}_{3}$ to the output bit corresponding to the position indexed by $\cdot^{\textup{scr}_{3}}_{j+1}$. This layer will also set the output bit corresponding to $\cdot^{\textup{scr}_{4}}_{3}$ 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 $\{0,1\}^{w}$. By (C.10), the constructed function will thus satisfy (C.11). It’s also easy to observe that $\|\theta\|_{1}$ is as desired. ∎

Furthermore, we choose null keys and positions such that $(K_{0})_{2w_{\textup{pos}}+1}=2w_{\textup{pos}}-1$, and $V_{0}=\mathbf{0}$. To follow the attention layer, we construct a linear layer which simply zeros out coordinates indexed by $\cdot^{\textup{scr}_{3}}$ 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 $i^{\prime}>0$, $Q(h_{i})^{\top}K(h_{i^{\prime}})=2w_{\textup{pos}}$. Otherwise, if $i^{\prime}=0$, $Q(h_{i})^{\top}K(h_{t})\leq 2w_{\textup{pos}}-2$ for all $1\leq t\leq i$. On the other hand, it always hold that $Q(h_{i})^{\top}K_{0}=2w_{\textup{pos}}-1$. Thus, if $i^{\prime}>0$, the attention attends exactly to $i^{\prime}$, so the value function satisfies $V(h_{i^{\prime}})=\mathbf{1}_{|{\mathcal{A}}|}(u_{i^{\prime}}(x))$, which would produce the output in (C.6), as desired. On the other hand, if $i^{\prime}=0$, the attention attends to the null position, so the attention layer sets $f^{(w_{\textup{pos}}+1)}(h_{i},H_{i},\theta)^{\textup{scr}_{1}}=\mathbf{0}$. Thus, $f^{(w_{\textup{pos}}+1)}$ also produces the desired output in this case. It’s also easy to observe that the $\|\theta\|_{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.

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 $e_{1},\ldots,e_{m}$ denote the outputs of the encoder, in the form (C.1). There is a function $f$ with parameter $\theta$ consisting of a single encoder-decoder attention layer such that for all such $h$ in the form (C.6), the following holds:

At all other coordinates, $f(h,(e_{1},\ldots,e_{m}),\theta)$ takes value . Furthermore, the parameters satisfy $\|\theta\|_{1}=O(|{\mathcal{A}}|+w_{\textup{pos}})$.

with 0’s in all other coordinates. The null key $K_{0}$ satisfies $(K_{0})_{w_{\textup{pos}}+1}=w_{\textup{pos}}-1$, with 0’s in all other coordinates. The null value $V_{0}$ satisfies $V_{0}=\mathbf{0}$. We set

Finally, we implement step 5) of the outline in Section 4.2 in the following lemma.

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 $\theta$ consisting of a constant number of feedforward ReLU layers satisfying the following:

At all other coordinates, $F(h,\theta)$ takes values . Furthermore, the parameters satisfy $\|\theta\|_{1}=O(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}})$.

It suffices to construct a sequence of layers which performs the following operations:

Note that $v$ encodes the location of the symbol $a_{i}(x)$, as $a_{i}(x)=u_{i^{\prime}}(x)$ if $i^{\prime}>0$, $a_{i}(x)=x_{l_{i}(x)}$ if $i^{\prime}=0$ and $l_{i}(x)\leq m$, and $a_{i}(x)=[\varnothing]$ otherwise. The vector $v$ is a one-hot vector indicating which of these three cases holds.

We can take $v_{1}$ and compute AND with all bits of $h^{\textup{scr}_{1}}$, which computes $\mathbf{1}_{|{\mathcal{A}}|}(u_{i^{\prime}}(x))=\mathbf{1}_{|{\mathcal{A}}|}(a_{i}(x))$ if $i^{\prime}>0$, and $\mathbf{0}$ otherwise.

We take $v_{2}$ and compute AND with all bits of $h^{\textup{scr}_{2}}$, which computes $\mathbf{1}_{|{\mathcal{A}}|}(x_{l_{i}(x)})$ if $v_{2}=1$, and $\mathbf{0}$ otherwise.

We take $v_{3}$ and compute AND with all bits of $\mathbf{1}_{|{\mathcal{A}}|}([\varnothing])$, which computes $\mathbf{1}_{|{\mathcal{A}}|}(a_{i}(x))$ if $v_{3}=1$.

We add the outputs of 2), 3), and 4) together, which gives $\mathbf{1}_{|{\mathcal{A}}|}(a_{i}(x))$. We copy this quantity into the output coordinates indexed by $\cdot^{\textup{sym}_{1}}$. 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 $\|\theta\|_{1}=O(|{\mathcal{Z}}|+|{\mathcal{A}}|+w_{\textup{pos}})$. ∎

We construct a neural net to compute any Turing machine with all-layer margin lower bound $\frac{1}{\textup{poly}(k,|{\mathcal{A}}|,\log T)}$ and apply Lemma 2.4 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 $G\in{\mathcal{G}}$. As mentioned, we first consider the case where $w=w_{\textup{TM}}$ exactly, as overparameterization is easy to deal with by always designating some subset of extra coordinates to be 0. We construct a transformer $\widehat{F}$ to compute $G$. 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 $o_{T}$ contains an onehot encoding for $z_{T}(x)$: $\mathbf{1}_{|{\mathcal{Z}}|}(z_{T}(x))$. We can now apply a linear weight vector $\theta_{\textup{cls}}$ on the output to obtain $\theta_{\textup{cls}}^{\top}o_{T}$, where $(\theta_{\textup{cls}})_{z}=1$ for accept states $z\in{\mathcal{Z}}_{\textup{term}}$ and $(\theta_{\textup{cls}})_{z}=-1$ for reject states. For inputs $x\in{\mathcal{X}}$, by our construction this computes the desired $\textup{TM}(x)$. 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 $\|\cdot\|_{1}$-norm at most $\textup{poly}(k,|{\mathcal{A}}|,\log T)$. Let $\widehat{F}(x,\widehat{\theta})$ denote the transformer constructed this way, with parameters $\widehat{\theta}$. Note that for all $x\in{\mathcal{X}}$, $\widehat{F}(x,\widehat{\theta})=2G(x)-1$.

Next, there are several steps remaining to convert $\widehat{F}$ into the fixed architecture $F^{\textup{tr}}_{0pt,0pt,T}$. First, we need to convert the layers in $\widehat{F}$ 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 $\|\cdot\|_{1}$-norm by $\textup{poly}(k,|{\mathcal{A}}|,\log T)$. 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 $0pt$. This is achievable by padding each layer with coordinates designated to be 0, without affecting any of the $\|\cdot\|_{1}$-norm bounds on the parameters. Third, we need to expand the depth to a fixed depth $0pt$. We can achieve this by appending transformer layers which compute the identity function (and also include correction functions) as needed.