# STATISTICALLY MEANINGFUL APPROXIMATION: A THE## ORETICAL ANALYSIS FOR APPROXIMATING TURING
# MACHINES WITH TRANSFORMERS

**Anonymous authors**
Paper under double-blind review

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 logpT q. 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.

1 INTRODUCTION

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 2[n] input-labeling pairs, but only 2[o][p][n][q] 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 function G 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 fitting G. 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.

1.1 RELATED WORKS

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.

1.2 NOTATION

Let f ˝g denote the composition of functions f and g. For a family of functions G, let f ˝G fitf ˝g :g PGu
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_ : _s_ P _SuĎ_ _Y. We use 1d to denote the all-one’s vector in d dimensions, with_
the subscripted omitted if clear. For i _d_, we let 1d _i_ denote the one-hot embedding in d-dimensions,
Pr s p q
which is 1 at index i and 0 everywhere else. We use the notation _Op¨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 poly to indicate the existence of a
— Á À [r] p¨q
polynomial in the argument which makes the equation true. For a set A (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 1, 1 . The expected n-sample Rademacher complexity of on P is as follows: Radn,P fi
t´ ` u 1 _n_ _F_ pFq
Epxiqni“1i.i.d„ P Eξ1,...,ξn supF PF _n_ _i“1[ξ][i][F]_ [p][x][i][q], where pxiqi[n]“1 [denotes][ n][ i.i.d. samples from][ P] [.]
“ “ ř ‰‰

2 STATISTICALLY MEANINGFUL APPROXIMATION

We consider settings where we wish to approximate every member G in a real-valued function class G
with some function F in function class F. 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 all G, there exists F such that Ex _P_ _ℓ_ _F_ _x_ _,G_ _x_ _ϵ._
PG PF „ r p p q p qqsď

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: _xi,G_ _xi_ _i_ 1[. If]
p p qq[n]“
we disregard this fact, we could end up constructing functions F which approximate G, 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 fitting G 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 loss_ [s]ℓ:F ˆX ˆRÑr0,1s such that the following holds for all GPG:


-----

_Defineof n examples labeled byF P_ _F to be the empirical minimizer of the loss G:_ _F fiargminF_ PF _n1_ _ni“1[s]ℓpF,xℓ_ _for fittingi,Gpxiqq G. Then with probability on an i.i.d. sample p 0xi.99,G over thepxiqqi[n]“1_
_draw of[p]xi_ _i_ 1[,][ p]F approximates G in the classical sense:[s] Ex _P_ _ℓ_ _F_ _x_ _,G_ _x_ _ϵ._
p q[n]“ ř „ r p[p]p q p qqsď

[p]

Definition 2.1 eases the statistical concerns associated with classical approximation theory: given a finite
sample _xi,G_ _xi_ _i_ 1[, the empirical risk minimizer of] [s]ℓ over is guaranteed to ϵ-approximate G on the
p p qq[n]“ _F_
population distribution. It is important that the losses [s]ℓ (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.

2.1 BACKGROUND AND TOOLS


To prove SM-approximation guarantees, Definition 2.1 requires a loss surrogate [s]ℓ such that the empirical
risk minimizer of _ℓ_ on the training data can approximate functions in G. The following proposition
provides several conditions on [s]ℓ which lead to SM approximation guarantees.

**Proposition 2.2. For loss function[s]** _ℓ_ : R ˆ R Ñ r0,1s and distribution P _, suppose there exists a loss_
_ℓ:F_ ˆX ˆRÑr0,1s, intended as a surrogate loss for ℓ, satisfying the following properties:

_1) For all F_ _, x_ _, y_ R, [s]ℓ _F,x,y_ _ℓ_ _F_ _x_ _,y_ _._

s PF PX P p qě p p q q

_2) For all G P G, consider the function class LG fi tx ÞÑ_ _ℓpF,x,Gpxqq : F P Fu. Then the n-sample_
_Rademacher complexity of LG is bounded: Radn,P_ pLGqďϵ.

_3) For all G_ _, there exists F_ _with small surrogate loss:[s] Ex_ _P_ _ℓ_ _F,x,G_ _x_ _ϵ._
PG PF „ r[s]p p qqsď

_Then_ _O_ _ϵ_ ?[1]n _-SM approximates_ _with respect to ℓ,P with sample complexity n._
_F_ ` _G_
´ ¯

By Proposition 2.2, it suffices that _ℓ_ upper bounds the target loss ℓ and has low complexity, and F
approximates G with respect to _ℓ, P in the classical sense. The proof follows from standard techniques_
for bounding generalization based on Rademacher complexity and is provided in Section A.

[s]

**All-layer margin loss. We introduce one particular construction for[s]** _ℓ_ 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

[s]
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, whereto the 0-1 loss ℓ0-1pz,yqfi1ppy´0.5qz ď0q where y Pt G0px,1qPtu is assumed to be a binary label. We consider a0,1u, and study approximation with respect
family of functions F parameterized by p-dimensional parameters θ PΘĎR[p], with a general architecture
function F :X ˆR[p] ÑR. Thus, F “txÞÑF px,θq:θ PΘu, and we sometimes use θ to identify an element
of . Throughout the paper, we define Θ as a 1-norm bounded set: _θ_ 1 _α,_ _θ_ Θ. We define the
parameter-based all-layer margin F _ρF :R[p]ˆX ˆt }¨}0,1uÑR as follows:_ } } ď @ P

_ρF_ pθ,x,yqfimin }δ}2 (2.1)
subject to py´0.5q¨F px,θ`δqď0

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 F px,θ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 loss_ [s]ℓγ as follows:

1 if ρpθ,x,yqď0

_ℓγ_ _θ,x,y_ $ 1 _[ρ][p][θ,x,y]γ_ [q] if 0 _ρ_ _θ,x,y_ _γ_ (2.2)
p q“ ´ ă p qď

’& 0 if ρ _θ,x,y_ _γ_

p qě

s

Note that _ℓγ composes the classical ramp loss, which is used to prove margin-based generalization’%_
complexity bounds, with the value of the all-layer margin. By our construction, it immediately follows
that [s]ℓγ _θ,x,G_ _x_ _ℓ0-1_ _F_ _x,θ_ _,G_ _x_, as is required of a surrogate loss.
p [s] p qqě p p q p qq

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 of GPG with large all-layer margin.
**Lemma 2.3. Fix any neural net architecture F : X ˆR[p]** Ñ R, and define Fα fi tx ÞÑ F px,θq : θ P Θu,
_where we assumeexists θ_ PΘ such that the following holds: ΘĎR[p] _is such that }θ}1 ďα for all θ_ PΘ. Fix ϵě0. Suppose that for all GPG, there
Ex _P_ 1 _ρ_ _θ,x,G_ _x_ _γ_ _ϵ_ (2.3)
„ r p p p qqă qsď

_Then_ _α ϵ-SM approximates_ _with respect to ℓ0-1,P with sample complexity_ _O_ _ϵ1[2]_ _α[2]logγ[2]ppq_ 1 _._
_F_ _G_ `
´ ´ ¯¯

We note that _O hides poly-logarithmic factors in the arguments, in this case,[r] polylog_ _γ[2]ϵ[2]_ factors.
p _[α][2][log][p][p][q]q_

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

[r]

Lemma 2.3 to prove that neural nets can SM approximate Boolean circuits and Turing machines.

3 SM APPROXIMATION OF BOOLEAN CIRCUITS WITH FEEDFORWARD NETS

This section shows that feedforward neural nets can SM approximate Boolean circuits with sample
complexity that depends polynomially on the size of the circuit. A boolean circuit G : t0,1u[m] Ñt0,1u
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 (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:
_q,r,s_ _G:_ 0,1 0,1 :G computed by circuit with depth q, size s, and width r
_G_ “t t u[m] Ñt u u
We will approximate Gq,r,s using a family of width w, depth d feedforward ReLU nets parameterized by linear weights and biases θ _W0, b0, ..., Wd, bd_ computed as follows:
“ p q
_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 forthatthe set of parameters with total bi P R[w] for 1 0 ďď i ďi ď dd´´11, W, andi P b R1-norm bounded byd[w] P[ˆ]R[w]. To control the sample complexity, we restrict our attention to, W0 P R[w][ˆ][m] α, and, giving the following function class: Wd P R[1][ˆ][w]. The bias parameters are such
}¨}
_w,d,α_ _x_ _Fw,d_ _x,θ_ : _θ_ 1 _α_
_F_ “t ÞÑ p q } } ď 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 allto ℓ0-1,P with sample complexity ϵ_ ą 0 and any input distribution poly _s_ _O_ log Pϵ overp[2]wdq t. 0,1u[m], Fw,d,α ϵ-SM approximates G with respect

p q[r]
´ ¯


-----

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 losses [s]ℓ 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 _i_ 1[}][W][i][}][op][ (or]
“
related quantities), which would be exponentially large in d for the naive construction in Section 3.1.

[ś][d]

3.1 PROOF SKETCH FOR THEOREM 3.1

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,1u[r][i][´][1] Ñt0,1u[r][i] _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,1u[m]_

_fi_ _f1_ _x_ _gi_ _g1_ _x_
˝¨¨¨˝ p q“ ˝¨¨¨˝ p q

_Thus, the composition F_ _,θ_ fi fq 1 _f1 satisfies F_ _x,θ_ _G_ _x_ _for all x_ 0,1 _. Note that we_
p¨ q ´ ˝¨¨¨˝ p q “ p q P t u[m]
_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**
_ℓ_ so that the empirical risk minimizer of _ℓ_ on the training data has good sample complexity. This crucially
requires the all-layer margin tool developed in Section 2.1, as other complexity measures (e.g. norm-based)
would not give good sample complexity bounds.
s [s]

Recall that the all-layer margin ρF _θ,x,G_ _x_ measures the stability of the output F _x,θ_ to perturbations
p p qq p q
in to θ, and, by Lemma 2.3, it suffices to show that F has large all-layer margin on x P t0, 1u[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 p¨,θq, with possibly small all-layer margin on xPt0,1u[m], into a new architecture and parameter
set F [1]p¨,θ[1]q, with provably large all-layer margin on xPt0,1u[m], such that F [1]px,θ[1]q“F px,θq on all inputs
_x_ Pt0,1u[m]. 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 F** _,θ_ _fq_ 1 _f1 be the neural net with parameters θ_
p¨ q“ ´ ˝¨¨¨˝
_constructed to compute the circuit G. 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_ [1]p¨,θ[1]qfifq´1˝ζq´2˝fq´2˝¨¨¨˝ζ1˝f1

_has large all-layer margin. Here θ[1]_ _denotes the collection of all parameters. Concretely, ρF 1_ _θ[1],x,G_ _x_
1 p p qqě

poly _s_ _[for all][ x][Pt][0][,][1][u][m][. Note that we omitted the dependency of][ f][i][,ζ][i][ on parameters][ θ][1][ for simplicity.]_
p q

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“ _di“1[W][i]_ _x´0.5, where_
_Wi_ R. In this simplified setting, we consider Wi 1 _i. For input x_ 1 and target y ¯1, the all-layer
margin is small: P _ρf_ pp1,...,1q,1,1qÀ ?[1]d[, where the architecture is in the subscript. Indeed, choosing] “ @ “ ´ś “ _[ δ][i]_ [“][ 3]d[,]

we have fp1,p1´ _d[3]_ _[,...,][1][´][ 3]d[qq“p][1][´][ 3]d[q][d]_ [´][0][.][5] [«] [exp][p´][3][q´][0][.][5] [ă] [0][. Thus, by the definition of all-layer]

margin, ρf pp1,...,1q,1,1qď _i[δ]i[2]_ [À][ 1]?d[.]

Now we will insert ReLU layers inař _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.


-----

0 _if z_ ă1{3

**Proposition 3.4. For any z** R, we can implement the function round _z_ 3x 1 _if 1_ 3 _z_ 2 3
P p q“ $ ´ { ď ă {

& 1 _if z_ 2 3

ě {
_via a feedforward ReLU net, as follows: roundpzq“3φpz´1{3q´3φpz´2{3%q._

We consider the following function _f, which inserts round between every layer in f:_

_fpx,pW1,...,Wdqq“[r]_ 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 thatr (3.1) preserves the output of f while increasing the all-layer margin:

**Claim 3.5. In the setting above, it holds that** _fp1,p1,...,1qq“fp1,p1,...,1qq and ρf_ [pp][1][,...,][1][q][,][1][,][1][qě][ 1]3[.]

This reflects a significant increase in the all-layer margin, while only increasing depth by a constantr

[r]

factor. The proof is simple: we observe that if δi ď [1]3 [for all][ i][, the function output will not change because]

roundpzq“1 @z ě 3[2][. 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 ζph[1]q “ h if h is the intended output of the layer and h[1] is any perturbed value satisfying
}h[1]´h}2 ď [1]3[. Since intended outputs of layers in the function constructed by Lemma 3.2 are binary-valued]

in t0,1u[w] 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 Pt0,1u[m]. 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.

4 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 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 TM _,_ _,S,_ term denote the function computed by the Turing machine, which produces an output
pZ _A_ _Z_ q
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)

4.1 TRANSFORMER ARCHITECTURE FOR SM-APPROXIMATING TURING MACHINES

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 embeddings E PR[w][ˆ|][A][|] and fixed positional
encodings βp1q,βp2q,...PR[w]. Given input xPA[˚] with m symbols, the encoder produces m output vectors
in R[w] 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 functions K,V,Q, each of which com-**
putes 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 h[1]. The layer first applies the key, value, and query functions as follows:

_τ0,τ1,...,τi_ _Q_ _h[1]_ _K0,Q_ _h[1]_ _K_ _h1_ _,...,Q_ _h[1]_ _K_ _hi_
“ p q[J] p q[J] p q p q[J] p q
_v0,v1,...,vi_ _V0,V_ _h1_ _,...,V_ _hi_
“ p q p q

where K0 and V0 are fixed “null” key and value vectors which are learned parameters of the layer. Letting
denote the set of indices _j_ :τj max _τ0,...,τi_, the attention layer performs hard-max attention (Pérez
_Jet al., 2019) to compute the output, as follows: t_ “ t uu

Attn _h[1],_ _h1,...,hi_ _h[1]_ [1] _vj_
p p qq“ `

_j_

|J | ÿPJ

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 ht[p][j][q] denote the representation computed by the j-th layer of the decoder at
timestepLetting e t1. At timestep,...,em denote the encoder outputs, encoder-decoder self-attention at the i, decoder self-attention at the pj`1q-th layer computes Attn pphji[p]`[j][q]1[,][p]q[h]-th layer and1[p][j][q][,...,h]i[p][j][q][qq][.]
_i-th step would compute Attnphi[p][j][q][,][p][e][1][,...,e][m][qq][.]_

**Transformer layers. We use feedforward layers which apply 3 standard ReLU layers, as follows:**
FF _h_ _φ_ _W3φ_ _W2φ_ _W1h_ _b1_ _b2_ _b3_ . Our theory also allows for residual feedforward layers, and
p q“ p p p ` q` q` q
the architecture here is chosen mainly to simplify the construction.

A transformer layer applies these constructions in sequence. Lettingafter the j-th transformer layer for timesteps 1ďtďi, and θ[p][j][q] the parameters of the layer, we compute Hi[p][j][q] “ph[p]1[j][q][,...,h]i[p][j][q][q][ denote the output]

_hi[p][j][`][1][,][dec][q]_ “Attnphi[p][j][q][,H]i[p][j][q][,θ][(j + 1, dec-attn)][q]

_hi[p][j][`][1][,][enc][q]_ Attn _hi[p][j][`][1][,][dec][q],_ _e1,...,em_ _,θ[(j + 1, enc-attn)]_
“ p p q q

Trphi[p][j][q][,H]i[p][j][q][,][p][e][1][,...,e][m][q][,θ][p][j][`][1][q][q“][FF][p][h][p][j][`][1][,][enc][q][,θ][p][j + 1, ff][q][q]

Note that we included the explicit dependence of the attention layers on the parameters for completeness.
We now set hi[p][j][`][1][q] “Trphi[p][j][q][,H]i[p][j][q][,][p][e][1][,...,e][m][q][,θ][p][j][`][1][q][q][.]

**Decoder outputs. We consider d-layer decoders, so oi fi** _hi[p][d][q]_ denotes the output of the decoder at time
_i, which is also inputted to the decoder at time i`1 as follows: hi[p]`[0][q]1_ [“][h]i[p][d][q]`βpi`1q. The initial decoder

input h[p]0[0][q] is a trainable parameter. The decoder runs for a fixed number of timesteps T [1] and produces the
prediction θcls[J] _[h]T[p][d][1][q][ . 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_ _x,θ_ to denote the described transformer architecture with parameters θ, w-dimensional
ÞÑ p q
hidden layers, d transformer layers in the decoder, and T decoder steps. This leads to the following class
of transformer functions: _w,d,α,T_ _x_ _Fw,d,T_ _x,θ_ : _θ_ 1 _α_ . The following theorem states that
this class of transformers SM approximates the Turing machine family F “ t ÞÑ p q } } ď u _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 x_ P _X_ _. Suppose that_
_w_ Ák|A|`logT _, d—logT_ _, and α“polypk,|A|,logT_ q.

_Then for allℓ0-1,P with sample complexity ϵ_ ą 0 and any input distribution poly _k,_ _,log PT_ _overO_ log Xϵp[2]wd, Fq _w,d,α,T._ _ϵ-SM approximates G with respect to_

p |A| q[r]
´ ¯

As with Section 3, we set the surrogate loss [s]ℓ 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 ΩpwT q. 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 com-_
plexities that are suboptimal in both the overparameterized width w 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.

4.2 PROOF SKETCH FOR THEOREM 4.1

Following Lemma 2.3, our goal is to construct a transformer which can simulate Turing machines with
large all-layer margin, namely, Ω polypk,|A1 |,logT q . 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

on the exact values of these small entries, then the all layer margin would be at mostpolypT q[. Our construction cannot afford to rely on values this small – informally, if the construction relies]poly1 _T_ [because]

p q
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 machine GPG. We first require notation to
describe the computation of G. For input x, we define zi _x_, ai _x_ to be the Turing machine state and
PX p q p q
symbol under the tape head at the conclusion of step i. We let li _x_ denote the location of the Turing machine
p q
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 qi _x_ left,right the movement direction of the head.
p qPt u

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
_zi_ _x_ _,ai_ _x_, and li _x_ . Given that this invariance holds until timestep i, the transformer simulates timestep
p q p q p q
_i`1 of the Turing machine with the following steps:_

1) Use feedforward layers to apply transition S on zi _x_ and ai _x_, which can be read from oi,
p q p q
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 i[1]_ “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_ 1 _x_ _li_ 1 _x_ . The binary search can be implemented with O rlogT s decoder self-attention
´ p q“ ` p q p q
layers, and the construction ensures large all-layer margin.

4) If no such i[1] 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`1pxq must 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.

5 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.


-----

6 ETHICS AND REPRODUCIBILITY STATEMENTS

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.

REFERENCES

Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency
moments. Journal of Computer and system sciences, 58(1):137–147, 1999.

Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural
networks with rectified linear units. arXiv preprint arXiv:1611.01491, 2016.

Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approximation
analysis of convolutional neural networks. work, 65, 2014.

Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE
_Transactions on Information theory, 39(3):930–945, 1993._

Peter Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally-normalized margin bounds for neural
networks. arXiv preprint arXiv:1706.08498, 2017.

Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and
pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning
_Research, 20(1):2285–2301, 2019._

Yoshua Bengio and Olivier Delalleau. On the expressive power of deep architectures. In International
_conference on algorithmic learning theory, pp. 18–36. Springer, 2011._

Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Con_ference on Computational Natural Language Learning,_ pp. 455–475, Online, November
2020. Association for Computational Linguistics. doi: 10.18653/v1/2020.conll-1.37. URL
[https://www.aclweb.org/anthology/2020.conll-1.37.](https://www.aclweb.org/anthology/2020.conll-1.37)

Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Depth-width trade-offs
for relu networks via sharkovsky’s theorem. arXiv preprint arXiv:1912.04378, 2019.

Vaggos Chatziafratis, Sai Ganesh Nagarajan, and Ioannis Panageas. Better depth-width trade-offs for
neural networks through the lens of dynamical systems. In International Conference on Machine
_Learning, pp. 1469–1478. PMLR, 2020._

Yining Chen, Sorcha Gilroy, A. Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks
as weighted language recognizers. In NAACL-HLT, 2018.

Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor decompositions.
In International Conference on Machine Learning, pp. 955–963. PMLR, 2016.

Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: A tensor
analysis. In Conference on learning theory, pp. 698–728. PMLR, 2016.

George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control,
_signals and systems, 2(4):303–314, 1989._

Amit Daniely. Depth separation for neural networks. In Satyen Kale and Ohad Shamir
(eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Pro_ceedings of Machine Learning Research, pp. 690–696. PMLR, 07–10 Jul 2017._ URL
[http://proceedings.mlr.press/v65/daniely17a.html.](http://proceedings.mlr.press/v65/daniely17a.html)

Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference
_on learning theory, pp. 907–940. PMLR, 2016._


-----

Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural
networks. In Conference On Learning Theory, pp. 297–299. PMLR, 2018.

Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.04231, 2016.

Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piecewise
linear neural networks. In Conference on Learning Theory, pp. 1064–1068. PMLR, 2017.

John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D Manning. Rnns can generate
bounded hierarchical languages with optimal memory. arXiv preprint arXiv:2010.07515, 2020.

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal
approximators. Neural networks, 2(5):359–366, 1989.

Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and
universal approximation. In International Conference on Learning Representations, 2020. URL
[https://openreview.net/forum?id=HklQYxBKwS.](https://openreview.net/forum?id=HklQYxBKwS)

Pascal Koiran and Eduardo D Sontag. Vapnik-chervonenkis dimension of recurrent neural networks.
_Discrete Applied Mathematics, 86(1):63–79, 1998._

Samuel A Korsky and Robert C Berwick. On the computational power of rnns. _arXiv preprint_
_arXiv:1906.06349, 2019._

Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. On the ability of neural nets
to express distributions. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference
_on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1271–1296. PMLR,_
[07–10 Jul 2017. URL http://proceedings.mlr.press/v65/lee17a.html.](http://proceedings.mlr.press/v65/lee17a.html)

Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks
with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):
861–867, 1993.

Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is a universal approximator.
_arXiv preprint arXiv:1806.10909, 2018._

Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir. The connection between approximation, depth separation and learnability in neural networks. arXiv preprint arXiv:2102.00434, 2021.

Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layers
neural networks. Proceedings of the National Academy of Sciences, pp. E7665–E7671, 2018.

Vaishnavh Nagarajan and J Zico Kolter. Deterministic pac-bayesian generalization bounds for deep
networks via generalizing noise-resilience. arXiv preprint arXiv:1905.13344, 2019.

Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks.
In Conference on Learning Theory, pp. 1376–1401. PMLR, 2015.

Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to
spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 2017.

Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep cnns. In International
_conference on machine learning, pp. 3730–3739. PMLR, 2018._

Jooyoung Park and Irwin W Sandberg. Universal approximation using radial-basis-function networks.
_Neural computation, 3(2):246–257, 1991._

Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks
using sub-linear parameters. arXiv preprint arXiv:2010.13363, 2020.

Jorge Pérez, Javier Marinkovi´c, and Pablo Barceló. On the turing completeness of modern neural network
architectures. arXiv preprint arXiv:1901.03429, 2019.

Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation
invariant/equivariant functions by deep neural networks. arXiv preprint arXiv:1903.01939, 2019.

J. Savage. Models of computation - exploring the power of computing. 1998.


-----

Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20(1):
81–102, 2008.

Anton Maximilian Schäfer and Hans-Georg Zimmermann. Recurrent neural networks are universal
approximators. International journal of neural systems, 17(04):253–263, 2007.

Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. Journal of
_computer and system sciences, 50(1):132–150, 1995._

Michael Sipser. Introduction to the Theory of Computation. Course Technology, Boston, MA, third
edition, 2013. ISBN 113318779X.

Matus Telgarsky. benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad
Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine
_Learning Research, pp. 1517–1539, Columbia University, New York, New York, USA, 23–26 Jun 2016._
[PMLR. URL http://proceedings.mlr.press/v49/telgarsky16.html.](http://proceedings.mlr.press/v49/telgarsky16.html)

Takeshi Teshima, Koichi Tojo, Masahiro Ikeda, Isao Ishikawa, and Kenta Oono. Universal approximation
property of neural ordinary differential equations. arXiv preprint arXiv:2012.02414, 2020.

Gal Vardi and Ohad Shamir. Neural networks with small weights and depth-separation barriers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances
_in Neural Information Processing Systems,_ volume 33, pp. 19433–19442. Curran Associates, Inc., 2020. [URL https://proceedings.neurips.cc/paper/2020/file/](https://proceedings.neurips.cc/paper/2020/file/e1fe6165cad3f7f3f57d409f78e4415f-Paper.pdf)
[e1fe6165cad3f7f3f57d409f78e4415f-Paper.pdf.](https://proceedings.neurips.cc/paper/2020/file/e1fe6165cad3f7f3f57d409f78e4415f-Paper.pdf)

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz
Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.03762, 2017.

Roman Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint
_arXiv:2001.06938, 2020._

Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz
augmentation. arXiv preprint arXiv:1905.03684, 2019a.

Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification
via an all-layer margin. arXiv preprint arXiv:1910.04284, 2019b.

Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision
rnns for language recognition. arXiv preprint arXiv:1805.04908, 2018.

Dmitry Yarotsky. Universal approximations of invariant maps by neural networks. _Constructive_
_Approximation, pp. 1–68, 2021._

Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis
of memorization capacity. arXiv preprint arXiv:1810.07770, 2018.

Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? arXiv preprint arXiv:1912.10077, 2019.

Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep
learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016.

Han Zhang, Xi Gao, Jacob Unterman, and Tom Arodz. Approximation capabilities of neural odes and
invertible residual networks. In International Conference on Machine Learning, pp. 11086–11095.
PMLR, 2020.

Ding-Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational
_harmonic analysis, 48(2):787–794, 2020._


-----

A PROOFS FOR SECTION 2

We prove Proposition 2.2 and Lemma 2.3.

_Proof of Proposition 2.2. Let_ _xi_ _i_ 1 [denote a][ n][ i.i.d. training examples drawn from][ P][ and fix][ G][P][G][. De-]
fine LpF qfiEx„P r[s]ℓpF,x,Gpx pqqsq and[n]“ _LpF_ qfi _n[1]_ _ni“1[s]ℓpF,xi,Gpxiqq. Let_ _F PF denote argminF_ PFLpF q,

the empirical risk minimizer of _L, which we aim to show has population loss for fitting G bounded by_
ř
_O_ _ϵ_ ?[1]n . By standard arguments using Rademacher complexity, we have with probability[p] [p] 1 _δ,_ [p]
p ` q ´

[p]

log 2 _δ_

sup _L_ _F_ _L_ _F_ 2Radn,P _G_ p { q
_F_ | p q´[p]p q|ď pL q` _n_
PF c

log 2 _δ_

2ϵ p { q (A.1)
ď ` _n_

c

Now note that by the condition 3) on [s]ℓ, there exists F [‹] with LpF [‹]qďϵ. Now we have

_L_ _F_ _L_ _F_ _L_ _F_ _L_ _F_ _L_ _F_ _L_ _F_ _L_ _F_ _L_ _F_
p[p]q´ p [‹]qďp p[p]q´[p]p[p]qq`p[p]p[p]q´[p]p [‹]qq`p[p]p [‹]q´ p [‹]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 _F_ . It follows that

log 2 _δ_

_L_ _F_ _L_ _F_ 4ϵ 2 p { q

[p] p[p]q´ p [‹]qď ` _n_

c

log 2 _δ_

_L_ _F_ 5ϵ 2 p { q
ùñ p[p]qď ` _n_

c

where we used LpF [‹]qďϵ. Finally, we use the fact that [s]ℓ upper bounds ℓ, so Ex„P rℓpF[p]pxq,GpxqqsďLpF[p]q.
Plugging in δ “0.01 gives the desired result.

_Proof of Lemma 2.3. We first observe that_ _ℓγ_ _θ,x,y_ 1 _ρ_ _θ,x,y_ _γ_ by definition, so by (2.3), for all
p qď p p qă q
_GPG we have_
inf _ℓ_ _θ,x,G_ _x_ _ϵ_
_θ_ Θ[E][s][x][„][P] [r][s]p p qqsď
P

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 θ,θ[1] R[p]. Let 2 _ε,Θ_ denote the ε-covering number of Θ in 2-norm, and _ε,_ _G_ the εP _N}¨}_ p q }¨} _N}¨}8p_ _L_ q
covering number of _G in the norm defined by_ _H_ _H[1]_ maxx _H_ _x_ _H[1]_ _x_ for any H,H[1] _G._
The arguments of (Wei & Ma, 2019b) imply that L } log´ _N}}¨}8_ 8“pε,LGqďPX |logpNq´}¨}2pγε,p Θq|qď _O_ _α[2]γlog[2]ε[2]pPpqL_,

where the last inequality is from standard covering number bounds for }¨}1 balls. Now we can apply´Y ]¯
this covering number bound in the Dudley entropy integral, another standard step to bound Rademacher

complexity, to obtain that for all n, Radn,P _G_ _αlognγ[?][?]nlogppq_ (see arguments in (Wei & Ma, 2019b) for
pL qÀ

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, let Q denote a distribution over px,yq pairs, with pxi,yiqi[n]“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 F_ p¨,θqPF which achieve zero 0-1 training loss satisfy


logppq
?n


Ex _Q_ _ℓ0-1_ _F_ _x,θ_ _,y_ _O_
„ r p p q qsď ¨

log 1 _δ_ log _n_ ˝[α]
_where ξ_ _O_ p { ?q`n p q _is a low-order term._
À
´ ¯


gn
f
f
e [1]


`ξ (A.2)


_ρ_ _θ,xi,yi_
p q[2]


_i“1_


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).


-----

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.
**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. Let Gi :_ t0,1u[r][i][´][1] Ñt0,1u[r][i] _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 θ_ _W1,b1,W2,b2_ _:_
“p q
_f_ _h,θ_ _φ_ _W2φ_ _W1h_ _b1_ _b2_
p q“ p p ` q` q

_Then there exist θ with_ _θ_ 1 _O_ _ri_ _such that for any h_ 0,1 _,_
} } “ p q Pt u[r][i][´][1]

_f_ _h,θ_ _Gi_ _h_
p[r] q“ [Č]p q

_where_ _h takes h and appends w_ _ri_ 1 zeros, and likewise for _Gi_ _h_ _._
´ ´ p q

We note that the proof of Lemma 3.2 follows by applying Lemma B.1we can complete the proof of Theorem 3.1.[r] [Ă] _q_ ´1 times. Using Lemma B.1,

_Proof of Theorem 3.1. Our proof will construct a neural network to compute any boolean circuit with_
all-layer margin lower bound poly1pr,qq[. By Lemma 2.3, this will be sufficient to guarantee meaningful]

approximation.

There are two steps in our construction: first, given any layered circuit G _q,r,s, we construct a neural net_
PG
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 _F computing G,_
but with possibly small all-layer margin. The next step is to convert _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

[p]
every group of layers in _F_ . These correction layers leverage the knowledge that unperturbed outputs of

[p]
these layers should be contained in t0,1u[w] and perform elementwise rounding to map perturbed values
back to 0,1 . Theorem D.6 formally shows that by introducing these correction layers can guarantee a
t u[w] [p]
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 _F_
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_

[p]
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 most O _s_ .
}¨} p q

Note that at this point, minor modifications are still required in order to apply Theorem D.6. The neural
net output is in t0,1u[w], 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
}¨}
_O_ _s_ _d_, so that the set of constructed functions is contained in _w,d,α. Thus, we showed that for_
p ` q _F_
_G_ _q,r,s, there exists θ such that F_ _x,θ_ 2G _x_ 1 for all x 0,1 .
PG p q“ p q´ Pt u[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
boundLemma 2.3 usingγ “ poly1pr,q γq [ě]“polyγ to obtain the desired result.1psq [on the all-layer margin for every input][ x][Pt][0][,][1][u][m][. Finally, we directly apply]
p

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

p

ReLU network.

**Proposition B.2. Let x** _x1_ 0, 1 _be binary inputs to AND and OR gates. The following_
“ _x2_ P t u[2]
„ 

_feedforward ReLU networks compute the AND and OR functions: FAND_ _x_ _φ_ _x1_ _x2_ 1 _, and_
_FOR_ _x_ 1 _φ_ 1 _x1_ _x2_ _._ p q “ p ` ´ q
p q“ ´ p ´ ´ q


-----

_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 in W1,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 NOT _z_ 1 _z for z_ 0,1 on coordinate j, we can set the j-th row of W1
p q“ ´ Pt u
to have -1 on the diagonal and 0 everywhere else, _b1_ _j_ 1, _b2_ _j_ 0, and _W2_ _j,j_ 1. It is easy to check
that _θ_ 1 _O_ _ri_ with this construction. p q “ p q “ p q “
} } “ p q

C PROOF OF THEOREM 4.1

C.1 ADDITIONAL SETUP AND NOTATION

We fix any Turing machine G P _G 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 rlog2 _T_ 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 P R[w][pos] to be the vector containing the binary encoding of i:
Bin _i_ _j_ 1 if the binary representation of i contains 1 in the j-th bit and 0 otherwise.
p q “

For simplicity, the proof will focus on the setting without overparameterization, where we choose the dimension w “wTM fi|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 of wTM coordinates. We group the wTM 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 hPR[w], we can index its coordinates via the groups as follows:

_h[st]_ PR[|][Z][|]

_h[sym][1]_ R[|][A][|]

» P fi

_h_ — _hh[sym][pos][1][2]_ PRR[w][|][A][pos][|] ffi
“—— _h[pos][2]_ PR[w][pos]ffiffi

— _h[pos][3]_ PR[w][pos]ffi
— P ffi
— _h[scr]_ R[w][scr] ffi
— P 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 βpiq[pos][1] “ Binpiq, and βpiq is 0 in all other
coordinates. The encoder embedding matrix E is such that

Encipxq[sym][1] “1|A|pxq (C.1)

Enci _x_ Bin _i_
p q[pos][1] “ p q

where Encipxq has 0’s at all other coordinates. embedding function e:AÑR[d] for the encoder is defined
such that epxq[sym][1] “ **1|A|pxq, the one-hot encoding for x** P _A, 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

_oi[st]_ [“][1]|Z|[p][z][i][p][x][qq]

_oi[sym][1]_ “1|A|paipxqq (C.2)

_oi[pos][2]_ Bin _li_ _x_
“ p p qq


-----

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`1qq[st] “1|Z|pzipxqq

poi`βpi`1qq[sym][1] “1|A|paipxqq (C.3)

_oi_ _β_ _i_ 1 Bin _i_
p ` p ` qq[pos][1] “ p q
_oi_ _β_ _i_ 1 Bin _li_ _x_
p ` p ` qq[pos][2] “ p p qq

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** _denote the set of decoder inputs in the form (C.3) encoding zi_ 1 _x_ _, ai_ 1 _x_ _, li_ 1 _x_
_O_ ´ p q ´ p q ´ p q
_for some timestep i. For parameters θ_ _W1,b1,W2,b2_ _, consider the following function computing a_
“ p q
_sequence of two feedforward ReLU layers: f_ _h,θ_ _φ_ _W2φ_ _W1h_ _b1_ _b2_ _. There exist parameters_
p q “ p p ` q` q
_θ such that for decoder inputs hPO,_
_fph,θq[st]_ “1|Z|pzipxqq

_fph,θq[sym][2]_ “1|A|puipxqq (C.4)

_fph,θq[pos][1]_ “Binpiq
_fph,θq[pos][2]_ “Binpli´1pxqq

_Furthermore, f_ _h,θ_ _will contain a one-hot encoding for qi_ _x_ _, and besides this, f_ _h,θ_ _is 0 at all other_
p q[scr] p q p q
_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 choose W1 :R[w][TM] ÑR[|][Z][||][A][|`][w][TM] so that the first
|Z|A| rows are described by:

_W1_ _z,a_ _,:_ [“][1][|][Z][|][p][z][q]
p qp[st] q

pW1qp[sym]z,a[1]q,: [“][1][|][A][|][p][a][q]

and 0 everywhere else. The remaining rows of wTM rows of W1 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,

_φ_ _W1h_ _b1_ **1|Z||A|ppzi´1pxq,ai´1pxqqq**
p ` q“ _h_
„ 

This is because before the ReLU, the first |Z||A| entries of W1h 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 O_ _wpos_ _feedforward ReLU layers such that for any h computed by the function in_
p q
_Lemma C.1 in the form (C.4) at timestep i,_
_fph,θq[st]_ “1|Z|pzipxqq

_fph,θq[sym][2]_ “1|A|puipxqq

_fph,θq[pos][1]_ “Binpiq (C.5)
_fph,θq[pos][2]_ “Binpli´1pxqq
_f_ _h,θ_ Bin _li_ _x_
p q[pos][3] “ p p qq

_At all other coordinates,_ _F_ ph, θq takes value 0. _Furthermore,_ _the parameters satisfy_
}θ}1 “Opwposp|Z|`|A|`wposqq.


-----

_Proof. As the construction of Lemma C.1 encoded qi_ _x_, the movement direction of the head, we can use
p q
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 use O _wpos_ feedforward ReLU layers to
“ “ p q
compute li´1pxq´v1, and then Opwposq additional feedforward ReLU layers to compute li´1pxq´v1`v2.
Note that the output would always be li _x_ by the definition of v1,v2.
p q

It remains to implement a module which computes Bin _j_ _v1_ given v1,Bin _j_, and Bin _j_ _v2_ given
p ´ q p q p ` q
_v2,Bin_ _j_ for any j _T_ . We can express the binary addition by a depth-O _wpos_ binary circuit, which can
p q Pr s p q
in turn be expressed by a neural net with Opwposq 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 h _wscr,_
P

_h[scr][1]_ PR[|][A][|]

_h[scr]_ “»hh[scr][scr][3][2]PPRR[w][|][A][pos][|] fi

— _h[scr][4]_ PR[3] ffi
– fl

**Lemma C.3. In the setting of Theorem 4.1 and Lemma C.2 above, fix any timestep i and define**
_i[1]_ “ maxt1 ď t ď i : lt´1pxq “ lipxqu. If j such that lt´1pxq “ lipxq exists, we define i[1] “ 0 otherwise.
_Consider anythe form (C.5) H. There is a functioni “ph1,...,hiq, where f parameterized by ht is computed by the layer in Lemma C.2 for timestep θ consisting of O_ _wpos_ _total self-attention and t, and in_
p q
_linear layers such that for all such Hi, the following holds:_

_fphi,Hi,θq[st]_ “1|Z|pzipxqq

_fphi,Hi,θq[sym][2]_ “1|A|puipxqq

_f_ _hi,Hi,θ_ Bin _i_
p q[pos][1] “ p q
_fphi,Hi,θq[pos][2]_ “Binpli´1pxqq (C.6)
_f_ _hi,Hi,θ_ Bin _li_ _x_
p q[pos][3] “ p p qq

_f_ _hi,Hi,θ_ **1|A|pui1pxqq** _if i[1]_ ą0
p q[scr][1] “ **0** _otherwise_
"

_F_ _hi,Hi,θ_ 1 1 _i[1]_ 0
p q[scr][4] “ p ą q

_At all other coordinates,_ _F_ pH, θq takes value 0. _Furthermore,_ _the parameters satisfy_
}θ}1 “Opwposp|Z|`|A|`wposqq.

The proof plan will roughly implement a binary search to find i[1], leveraging the attention layers. The
first step in the binary search is to verify whether i[1] ą0, described below.
**Claim C.4. In the setting of Lemma C.3, let Hi** “h1,...,hi be the input representations for timesteps 1,...,i.
_Suppose that each ht for 1ďtďi satisfies the following:_

_ht[pos][1]_ Bin _t_
“ p q (C.7)

_ht[pos][2]_ “Binplt´1pxqq

_Additionally, suppose that hi is of the form in (C.5). Then there is a function f_ [p][0][q] _parameterized by θ_
_such that_


_f_ [p][0][q] _hi,Hi,θ_ **0**
p q[scr][1] “

_f_ [p][0][q] _hi,Hi,θ_ **0**
p q[scr][3] “

_f_ [p][0][q] _hi,Hi,θ_ 1 1 _i[1]_ 0
p q[scr][4] “ p ą q

_The function f_ [p][0][q] _can be computed by a single decoder self-attention layer with_ _θ_ 1 _O_ _wpos_ _._
} } “ p q


(C.8)


Next, we implement the binary search itself, using wpos self-attention layers. Each step of the binary
search reveals a single bit of i[1], so the j-th attention layer will compute a representation storing the j most


-----

significant bits of i[1]. We let Binj _l_ 0,1 to denote the binary encoding of the j most significant bits
p qPt u[w][pos]
of l: Binj _l_ _j1_ Bin _l_ _j1 for 1_ _j[1]_ _j, and_ Binj _l_ _j1_ 0 for j[1] _j. We also set Bin0_ _l_ **0. We use**
p p qq “p p qq ď ď p p qq “ ą p q“
the superscript [p][j][q] 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 Hi[p][j][q]** “ h[p]1[j][q][,...,h]i[p][j][q] _be the representations_
_computed after the j-th group of layers for timesteps 1 through i, for 0_ _j_ _wpos_ 1. Suppose that each
ď ď ´
_ht[p][j][q]_ _for 1_ _t_ _i satisfies the following:_
ď ď

_ht[p][j][q][,][pos][1]_ Bin _t_
“ p q (C.9)

_ht[p][j][q][,][pos][2]_ “Binplt´1pxqq

_In addition, suppose that hi[p][j][q]_ _satisfies:_

_hi[p][j][q][,][scr][1]_ **0**
“

_hi[p][j][q][,][scr][3]_ “ Bin0 _jpi1q_ _ifotherwise i[1]_ ą0 (C.10)
"

_hi[p][j][q][,][scr][4]_ 1 1 _i[1]_ 0
p q “ p ą q

_with all other coordinates matching the quantities prescribed in (C.5). Then there is a function f_ [p][j][`][1][q]
_parameterized by θ such that_

_f_ [p][j][`][1][q]phi[p][j][q][,H]i[p][j][q][,θ][q][scr][1][ “][0]

_f_ [p][j][`][1][q] _hi[p][j][q][,H]i[p][j][q][,θ][q][scr][3][ “]_ Binj`1pi1q _if i[1]_ ą0 (C.11)
p **0** _otherwise_
"

_f_ [p][j][`][1][q]phi[p][j][q][,H]i[p][j][q][,θ][q]1[scr][4] “1pi[1] ą0q

_with all other coordinates matching those prescribed in (C.5). We note that f_ [p][j][`][1][q] _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 Bin _i[1]_ exactly. It remains
p q
to apply another attention layer which attends directly to timestep i[1] and copies ui1 _x_ .
p q
**Claim C.6.after the wpos In the setting above and of Lemma C.3, let-th group of layers constructed in Claim C.5 for timesteps Hi “** _h1,...,hi be the representations computed 1 through i. Suppose that each_
_ht for 1ďtďi satisfies the following:_

_ht[sym][2]_ “1|A|putpxqq

_ht[pos][1]_ Bin _t_ (C.12)
“ p q

_ht[pos][2]_ “Binplt´1pxqq

_In addition, suppose that hi satisfies:_

_hi[scr][1]_ 0
“

Bin _i1_ _if i[1]_ 0
_hi[scr][3]_ “ **0** p q _otherwiseą_ (C.13)
"

_hi[scr][4]_ 1 1 _i[1]_ 0
p q “ p ą q

_with all other coordinates matching the quantities prescribed in (C.5). Then there is a function f_ [p][w][pos][`][1][q]

_parameterized by θ such that f_ [p][w][pos][`][1][q] _hi,Hi,θ_ _computes the desired output in (C.6). Furthermore,_
p q
_f_ [p][w][pos][`][1][q] _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 f [p][0][q] to be the function defined in Claim C.4. We note that


-----

layers output by f [p][0][q] satisfy the condition of Claim C.5, so we can apply Claim C.5 inductively to obtain
layers f [p][1][q],...,f [p][w][pos][q] where their applying their composition results in representations satisfying (C.12)
and (C.13). Now we set f [p][w][pos][`][1][q] 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_
_Qchoose the parameters such that the following equations hold:phq “ WQh`bQ and Kphq “ WKh`bK, where WQ,WK P R[p][w][pos][`][1][qˆ][w]_ and bQ,bK P R[w][pos][`][1]. We


_Q_ _h_ 1:wpos 2h[pos][3] 1
p q “ ´

_Q_ _h_ _wpos_ 1 1
p q ` “


and


_K_ _h_ 1:wpos 2h[pos][2] 1
p q “ ´

_K_ _h_ _wpos_ 1 0
p q ` “

The value function V _h_ is such that V _h_ 1 1, and V _h_ _ℓ_ 0 on all other coordinates ℓ, which
p q p q[scr][4] “ p q “
can be implemented by a linear transformer. Finally, we set the null key K0 and value V0 such that
_K0_ _wpos_ 1 _wpos_ 1, with 0 everywhere else, and V0 **0. Letting θattn denote the attention parameters,**
p q ` “ ´ “
the layer is of the form

_f_ [p][0][q] _hi,Hi,θ_ Attn _hi,Hi,θ_
p q“ p q

To see that f [p][0][q] satisfies (C.8), observe that if i[1] ą 0, Qphiq[J]Kphi1q “ wpos by (C.7) and construction
of Q,K. On the other hand, Q _hi_ _K0_ _wpos_ 1. Thus, argmaxtQ _hi_ _K_ _ht_ _i_, which implies
p q[J] “ ´ p q[J] p q P r s
that f [p][0][q] _hi,Hi,θ_ 1 1 by the construction of V . In the other case where i[1] 0, we note that
p q[scr][4] “ “
_Q_ _hi_ _K_ _ht_ _wpos_ 2 for all 1 _t_ _i, so the null position is attended to. By construction of V0, this_
p q[J] p qď ´ ď ď
implies f [p][0][q] _hi,Hi,θ_ 1 0. As V,V0 are 0 on all other coordinates, it follows that (C.8) holds. It’s also
p q[scr][4] “
easy to observe that the }θ}1 is as desired.

_Proof of Claim C.5. The first layer in f_ [p][j][`][1][q] computes decoder self-attention. The query function is of
the form Q _h_ _WQh_ _bQ, and the key function is of the form K_ _h_ _WKh_ _bh, where WQ,WK_
p q“ ` p q“ ` P
R[p][w][pos][`][j][`][2][qˆ][w] and bQ,bK PR[p][w][pos][`][j][`][2][q]. We choose the parameters so that the following equations hold:

_Q_ _h_ 1:wpos 2h[pos][3] 1
p q “ ´

_Qphqwpos`1:wpos`j “2h1:[scr]j[3]_ [´][1]

_Q_ _h_ _wpos_ _j_ 1 1
p q ` ` “

_Q_ _h_ _wpos_ _j_ 2 1
p q ` ` “

and

_K_ _h_ 1:wpos 2h[pos][2] 1
p q “ ´

_Kphqwpos`1:wpos`j`1_ “2h1:[pos]j[1]`1[´][1]

_K_ _h_ _wpos_ _j_ 2 0
p q ` ` “


Both of these functions can be constructed via linear transformations of h, with _WQ_ 1 _WK_ 1 _bQ_ 1
} } `} } `} } `
_bK_ 1 _O_ _wpos_ . Now we construct the value function V _h_ _WV h_ _bV such that V_ _h_ 3 1 and
_V}_ _h}_ _ℓ “0 on all other coordinates, which is also easily implemented by a linear layer. For the attention, thep_ q p q“ ` p q[scr][4] “
p q “
last quantities to construct are the null key K0 and value V0. K0 will satisfy _K0_ _wpos_ _j_ 2 _wpos_ _j, with_
p q ` ` “ `
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

_f_ [p][j][`][1][q][,][1]phi[p][j][q][,H]i[p][j][q][,θ][attn][q“][Attn][p][h]i[p][j][q][,H]i[p][j][q][,θ][attn][q]


-----

where Attn uses the constructed key, value, and query functions. We claim that f [p][j][`][1][q][,][1]phi[p][j][q][,H]i[p][j][q][,θ][attn][q]
satisfies the following:

1 if i1 0 and has _j_ 1 -th bit 1
_f_ [p][j][`][1][q][,][1] _hi[p][j][q][,H]i[p][j][q][,θ][attn][q]3[scr][4]_ ą p ` q (C.14)
p “ 0 otherwise
"

For all other coordinates ℓ, f [p][j][`][1][q][,][1]phi[p][j][q][,H]i[p][j][q][,θ][attn][q][ℓ] [“ p][h]i[p][j][q][q][ℓ][. To see this, we first observe that]
_Qphi[p][j][q][q][J][K][0][ “][ w][pos][ `][ j][. Next, we observe that][ Q][p][h]i[p][j][q][q][1:][w]pos_ [produces the encoding of][ l][i][p][x][q][ using]
binary t´1, `1u bits, and Kpht[p][j][q][q][1:][w]pos [produces the encoding of][ l][t][´][1][p][x][q][ using binary][ t´][1][,][ `][1][u]
bits by (C.9). In addition, Q _hi[p][j][q]_ pos[`][1:][w]pos[`][j][ “][ 2][Bin][j][p][i][1][q ´][ 1][ if][ i][1][ ą][ 0][ and all 0’s otherwise, and]
p [q][w]

_K_ _ht[p][j][q]_ pos[`][1:][w]pos[`][j][`][1] [“][2][Bin][j][`][1][p][t][q´][1][. Note that by our construction, the maximum possible value of]
p [q][w]

_Q_ _hi[p][j][q]_ _t_
p [q][J][K][p][h][p][j][q][q][ is][ w][pos][`][j][`][1][, and the next largest possible value is][ w][pos][`][j][´][1][. Now there are 3 cases:]

**Case 1: i[1]** 0. In this case, we note that li _x_ never matches lt 1 _x_ for 1 _t_ _i. Thus, by construction_
“ p q ´ p q ď ď
of the first wpos coordinates of Q and K, the largest possible value of Q _hi[p][j][q]_ _t_
p [q][J][K][p][h][p][j][q][q][ is][ w][pos] [`][j] [´][1][,]
so the attention will always only attend to the null position, so the layer adds V0 “ **0 to hi[p][j][q][, preserving]**
its value. Note that _hi[p][j][q][,][scr][4]_ 3 0 in this case, which matches the desired behavior.
p q “

**Case 2: i[1]** 0, and has _j_ 1 -th bit 0. In this case, we note that for all t _i[1], Q_ _hi[p][j][q]_ _t_
1, because by definition suchą p ` q t must satisfy lt 1 _x_ _li_ _x_, so the firstą wpos coordinates contribute at mostp [q][J][K][p][h][p][j][q][qď][w][pos][`][j][´]
´ p q‰ p q
_wpos_ 2 to the dot product. On the other hand, if t _i[1], t must have_ _j_ 1 -th bit 0, so K _ht[p][j][q]_ pos[`][j][`][1] [“]
´ ď p ` q p [q][w]

1. This doesn’t match the _wpos_ _j_ 1 -th bit of the query, so Q _hi[p][j][q]_ _t_
Thus, in this case, the null position is attended to again. The same reasoning as Case 1 then applies.´ p ` ` q p [q][J][K][p][h][p][j][q][qď] _[w][pos]_ [`][j] [´][1][ again.]

**Case 3: i[1]** 0 and has _j_ 1 -th bit 1. In this case, maxtQ _hi[p][j][q]_ _t_
_i[1]_ achieves this maximum by our construction. As a result, the null position is not attended to. All the valuesą p ` q p [q][J][K][p][h][p][j][q][q“][w][pos][`][j][`][1][: for example,][ t][“]
in the positions attended to satisfy V _ht[p][j][q]_ 3 1, which matches the _j_ 1 -th bit of i[1]. Thus, (C.14) holds.
p [q][scr][4] “ p ` q

Finally, to complete the proof we simply append an additional feedforward ReLU layer which copies the
value f [p][j][`][1][q][,][1] _hi[p][j][q][,H]i[p][j][q][,θ][attn][q]3[scr][4]_ to the output bit corresponding to the position indexed by _j_ 1[. This layer]
p ¨[scr]`[3]
will also set the output bit corresponding to 3 to 0. Note that these operations can be implemented with a
¨[scr][4]
linear layer, and applying a ReLU activation after won’t change the output, which is in t0,1u[w]. 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 R[w] to R[2][w][pos][`][1]. The value function is also linear. We choose parameters such that


_Q_ _h_ 1:wpos 2h[pos][3] 1
p q “ ´

_Q_ _h_ _wpos_ 1:2wpos 2h[scr][3] 1
p q ` “ ´

_Q_ _h_ 2wpos 1 1
p q ` “

_K_ _h_ 1:wpos 2h[pos][2] 1
p q “ ´

_K_ _h_ _wpos_ 1:2wpos 2h[pos][1] 1
p q ` “ ´

_K_ _h_ 2wpos 1 0
p q ` “


and

and


_V_ _h_ _h[sym][2]_
p q[scr][1] “

Furthermore, we choose null keys and positions such that _K0_ 2wpos 1 2wpos 1, and V0 **0. To follow**
p q ` “ ´ “
the attention layer, we construct a linear layer which simply zeros out coordinates indexed by ¨[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[1] 0, Q _hi_ _K_ _hi1_
ą p q[J] p q“
2wpos. Otherwise, if i[1] 0, Q _hi_ _K_ _ht_ 2wpos 2 for all 1 _t_ _i. On the other hand, it always hold_
“ p q[J] p qď ´ ď ď
that Q _hi_ _K0_ 2wpos 1. Thus, if i[1] 0, the attention attends exactly to i[1], so the value function satisfies
p q[J] “ ´ ą


-----

_V phi1q“1|A|pui1pxqq, which would produce the output in (C.6), as desired. On the other hand, if i[1]_ “0, the
attention attends to the null position, so the attention layer sets f [p][w][pos][`][1][q] _hi,Hi,θ_ **0. Thus, f** [p][w][pos][`][1][q]
p q[scr][1] “
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,θq[st]_ “1|Z|pzipxqq

_fph,pe1,...,emq,θq[sym][2]_ “1|A|puipxqq

_f_ _h,_ _e1,...,em_ _,θ_ Bin _i_
p p q q[pos][1] “ p q
_fph,pe1,...,emq,θq[pos][2]_ “Binpli´1pxqq
_f_ _h,_ _e1,...,em_ _,θ_ Bin _li_ _x_
p p q q[pos][3] “ p p qq

_f_ _h,_ _e1,...,em_ _,θ_ **1|A|pui1pxqq** _if i[1]_ ą0 (C.15)
p p q q[scr][1] “ 0 _otherwise_
"

_f_ _h,_ _e1,...,em_ _,θ_ **1|A|pxlipxqq** _if lipxqďm_
p p q q[scr][2] “ **0** _otherwise_
"

_f_ _h,_ _e1,...,em_ _,θ_ 1 1 _i[1]_ 0
p p q q[scr][4] “ p ą q
_f_ _h,_ _e1,...,em_ _,θ_ 2 1 _li_ _x_ _m_
p p q q[scr][4] “ p p qď q

_At all other coordinates, f_ _h,_ _e1, ..., em_ _, θ_ _takes value 0._ _Furthermore, the parameters satisfy_
p p q q
}θ}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 R[w] to R[w][pos][`][1] and compute the following:


_Q_ _h_ 1:wpos 2h[pos][3] 1
p q “ ´

_Q_ _h_ _wpos_ 1 1
p q ` “

_K_ _h_ 1:wpos 2h[pos][1] 1
p q “ ´

_K_ _h_ _wpos_ 1 0
p q ` “


and

The value function computes


_V_ _h_ _h[sym][1]_
p q[scr][2] “

_V_ _h_ 2 1
p q[scr][4] “

with 0’s in all other coordinates. The null key K0 satisfies _K0_ _wpos_ 1 _wpos_ 1, with 0’s in all other
coordinates. The null value V0 satisfies V0 “0. We set p q ` “ ´

_f_ _h,_ _e1,...,em_ _,θ_ Attn _h,_ _e1,...,em_ _,θ_
p p q q“ p p q 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 Q _h_ 1:wpos Bin _li_ _x_ .
p q “ p p qq
In addition, we have K _ej_ 1:wpos _ej[pos][1]_ Bin _j_ for 1 _j_ _m. Thus, by construction of V,K0,V0,_
if li _x_ _m, the attention attends to positionp_ q “ “ p liq _x_ in the embedding. The value function for this ď ď
p q ď p q
position satisfies V pelipxqq[scr][2] “ el[sym]ipx[1]q [“][ 1][|][A][|][p][x][l][i][p][x][q][q][. Thus, in this case][ F] [p][h,θ][q][ computes the desired]
output in (C.15). On the other hand, if li _x_ _m, then the attention will attend to the null position, as_
p q ą
_Q_ _h_ _K0_ _wpos_ 1, and the largest possible score for all other positions is wpos 2. In this case, (C.15)
p q[J] “ ´ ´
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,θq[st]_ “1|Z|pzipxqq

_fph,θq[sym][1]_ “1|A|paipxqq

_f_ _h,θ_ Bin _li_ _x_
p q[pos][2] “ p p qq


(C.16)


_At all other coordinates,_ _F_ ph, θ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 v PR[3]:

1
0 if h1[scr][4] 1

$ » fi “

0

_v_ “’’’’’’& – fl0

_h2[scr][4]_ if h1[scr][4] 0

» fi “

Note that v encodes the location of the symbol’’’’’’% –1´h2[scr][4] aflipxq, as aipxq“ui1pxq if i[1] ą0, aipxq“xlipxq
if i[1] “ 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 _h[scr][1],_ which computes
**1|A|pui[1]pxqq“1|A|paipxqq if i[1]** ą0, and 0 otherwise.

3) We take v2 and compute AND with all bits of h[scr][2], which computes 1 _xli_ _x_ if v2 1, and
|A|p p qq “
**0 otherwise.**

4) We take v3 and compute AND with all bits of 1 ∅, which computes 1 _ai_ _x_ if v3 1.
|A|pr sq |A|p p qq “

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 ¨[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 }θ}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 poly _k,_ 1 _,logT_ [and apply Lemma 2.3 to turn this into a statement about statistically meaningful]

p |A| q
approximation.

For our Turing machine construction, we follow the outline laid out in Section 4.2. Fix any G P _G. 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 _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

[p]
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 _x_ : 1 _zT_ _x_ . We can now
p q |Z|p p qq
apply a linear weight vector θcls on the output to obtain θcls[J] _[o][T]_ [, where][ p][θ][cls][q][z][ “][1][ for accept states][ z] [P][Z][term]
andNext, following Theorem 3.1, we insert correction functions (Definition D.1) between every group of pθclsqz “´1 for reject states. For inputs xPX, by our construction this computes the desired TMpxq.
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 poly _k,_ _,logT_ . Let _F_ _x,[p]θ_
}¨} p |A| q p q
denote the transformer constructed this way, with parameters _θ. Note that for all xPX_, _F_ px,[p]θq“2Gpxq´1.

[p]

[p] [p]


-----

Next, there are several steps remaining to convert _F into the fixed architecture Fw,d,T[tr]_ [. First, we need]
to convert the layers in _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[p]
transformer layer by setting the two unused modules in the transformer layer to implement the identity

[p]
function. This only increases the 1-norm by poly _k,_ _,logT_ . Note that in particular, we can perform
}¨} p |A| q
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 logT_ q, 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|,logT q, 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[´][1]p|Z|,|A|,logT qq. This reasoning can be used to conclude that Condition D.3 with Lipschitz
constants polyp|Z|,|A|,logT q, and distance parameters Ωppoly[´][1]p|Z|,|A|,logT qq holds. As a result, the
all-layer margin bound from applying Theorem D.6 will also be Ωppoly[´][1]p|Z|,|A|,logT qq, as desired.
Finally, applying Lemma 2.3 with γ “ Ωppoly[´][1]p|Z|,|A|,logT qq and using the fact that the parameter
1-norms are bounded by α gives the desired result.
}¨}

D ALL-LAYER MARGIN LOWER BOUNDS VIA CORRECTION FUNCTIONS

We consider a generalized architecture for a d-layer network as follows. Let f0 :X ˆΘ0 ÑR[w] map space
of inputs xPX and parameters θ PΘ0 to w-dimensional space. For simplicity we assume all intermediate
We definelayers have dimension fd to output values in w, and let R f. Leti : R[w] θˆ“pΘθi Ñ0,...,θR[w]dqPbe theΘ denote the full vector of parameters. The i-th function in the neural net for d ą _i iě-th1._
hidden layer hi computes the following value, defined recursively:
_h0_ _x,θ_ _f0_ _x,θ0_
p q“ p q
_hipx,θq“fiph0px,θq,...,hi´1px,θq,θiq_
The model computes output hd _x,θ_ . We will assume the existence of “correction” functions ζ paramep q
terized by ξ _ξ0,...,ξd_ 1 Ξ0 Ξd 1 which correct errors in the model output for inputs :
“p ´ qP ˆ¨ˆ ´ _X_
**Definition D.1 (Correction functions). Let F** [1] : X Ñ R be a model defined by layer functions f0,...,fd.
_Then ζ0,...,ζd´1 :_ R[w] Ñ R[w], ξ is a set of correction functions and parameters for F [1], θ with radius σζ
_if for all iPrd´1s,xPX and_ _hPR[X]_ _satisfying }h[p]´hipx,θq}2_ ďσζ,

_ζi_ _h,ξi_ _hi_ _x,θ_
p[p] q“ p q
_We now define the function output[p]_ _F with correction layers recursively by_
_g0_ _x,θ,ξ_ _f0_ _x,θ0_
p q“ p q
_hipx,θ,ξq“ζipgi´1px,θ,ξq,ξiq @0ďiďd´1_ (D.1)
rgipx,θ,ξq“fiph[r]0px,θ,ξq,...,h[r]i´1px,θ,ξq,θi,ξiq @1ďiďd

_F_ _x,θ,ξ_ _gd_ _x,θ,ξ_
p q“ p q


-----

_We note that for all x_ _, F_ _x,θ,ξ_ _hd_ _x,θ_ _._
PX p q“ p 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:_

_f_ _h,θ_ _f_ _h,[p]θ_ 2 _κθ_ _θ_ _θ_ 2max _h_ _,1_ _θ_ _θ_ _σθ,h_
} p q´ p q} ď } ´[p]} t||| ||| u @} ´[p]}ď PH

_f_ _h,[p]θ_ _f_ _h,[p]θ_ 2 _µ_ _h_ _h_ _h_ _h_ _σh,_ _θ_ _θ_ _σθ,h_
} p q´ p[p] q} ď ´[p] @ ´[p] ď } ´[p]}ď PH
ˇˇˇ ˇˇˇ ˇˇˇ ˇˇˇ
ˇˇˇ ˇˇˇ ˇˇˇ ˇˇˇ

We will focus on the following norm on tuples of inputsˇˇˇ ˇˇˇ pv1,...,vˇiˇˇq, whereˇˇˇ _hj PR[w]_ for all j Pris:

_v1,...,vi_ max (D.2)
|||p q|||“ _j_ [}][v][j][}][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 _κθ,µ,σh,σθ_ _-nice at θi on_ _h0,...,hi_ 1 _with respect to_ _._
ě p q p ´ qpX q |||¨|||

_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
_ξ with }ξi´[p]ξ}2_ ďσξ and hPR[w].

These conditions are all standard Lipschitzness-based conditions on the individual layer functions. Our

p

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_ _,_

max _hi_ _x,θ_ 2,1 _λ_ (D.3)
t} p q} uď

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.5real-valued parameters. Suppose we wish to perform copying on parameters (Layer-based weight sharing). Let Θ[1]** ĎR[w][1], Θ0 ĎR[w][0],..., θΘ[1]dP ĎΘR[1] _to produce parameters[w][d]_ _be some spaces of_
_θ_ “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θ[1]q“pθπ[1]_ 1[,...,θ]π[1] _bi_ [q] (D.4)

_where π1,...,πbi is a set of distinct indices taking values in rw[1]s. 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 F _x_ 1, 1 _x_ _. Then for all x_ _, we can bound the all-layer_
_margin of ă F (defined in (2.1))as follows:p_ q P t´ ` u @ P X P X


_ρF_ _θ,ξ_ _,x,1_ _F_ _x,θ,ξ_ 0 min _[λ]_ _,_ _[σ][ζ]_ _,σθ,σξ,_ [1] _, [σ][ζ]_ _σζ_
pp q p p qě qqě tµ0 _µ0_ 2κθ 2κθλ[, σ]2κ[h]ξλ[,]4λµκξ


1

(D.5)
4µκξ u


_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 modelmappings τ_ [p][1][q], τ [p][2][q] _(Definition D.5), the same bound holds for F_ [1]px,θ[1]qfiF p ρx,τF 1p[p][1]θ[q][1]p,x,θ[1]q1,τpF[p][2][1][q]ppx,θθ[1]qq[1]qě for valid weight-tying0qq.


-----

Our proof will first consider the case without weight sharing. We use _θ_ “p[p]θ0,...,[p]θdq and _ξ_ “p[p]ξ0,...,[p]ξd´1q
to denote a perturbed set of parameter vectors. Furthermore, define the partially perturbed parameter sets
_θi_ fip[p]θ0,...,[p]θi,θi`1,...,θdq and _ξi_ fip[p]ξ0,...,[p]ξi,ξi`1,...,ξdq. We also use _θ´[p]1_ fiθ and _ξ´1_ fiξ when convenient.[p]

We consider perturbations such that the following norm bounds hold:

p [p] [p] [p]

_θ0_ _θ0_ 2 min _[λ]_ _,_ _[σ][ζ]_ (D.6)
}[p] ´ } ď tµ0 _µ0_ u

_θi_ _θi_ 2 min _σθ,_ [1] _, [σ][ζ]_ (D.7)
}[p] ´ } ď t 2κθ 2κθλ[u]

_σζ_ 1

_ξi_ _ξi_ 2 min _σξ, [σ][h]_ _,_ (D.8)
}[p] ´[p] } ď t 2κξλ[,]4λµκξ 4µκξ u

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:**

_h0_ _x,[p]θ,ξ_ _h0_ _x,θ_
p q“ p q

_g0_ _x,[p]θ,[p]ξ_ _h0_ _x,θ_ 2 min _λ,σζ_
} p q´ r p q} ď t 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_ _,_

_hjpx,[p]θ,[p]ξj´1q“hjpx,θq_ (D.9)

_and_

r

_gj_ _x,[p]θ,[p]ξ_ _hj_ _x,θ_ 2 min _λ,σζ_
} p q´ p q} ď t u

_In addition, suppose that_ _θ,θ,[p]ξ,ξ satisfy (D.7) and (D.8). Then it follows that for all xPX_ _,_

_gi_ _x,[p]θ,[p]ξ_ _hi_ _x,θ_ 2 min _λ,σζ_

[p] } p q´ p q} ď t u

_Furthermore, for 1ďiďd´1, we additionally have_

_hipx,[p]θ,[p]ξi´1q“hipx,θq_

Combined, the two lemmas above allow us to inductively show that the prediction of the model is notr
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, |F px,θ,ξq´F px,[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,1pF px,θ,ξ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_ [1]px,θ[1]qfiF px,τ [p][1][q]pθ[1]q,τ [p][2][q]pθ[1]qq for valid weight-tying mappings τ [p][1][q], τ [p][2][q] _(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
_F_ _x,[p]θ,[p]ξ_ _F_ _x,θ,ξ_ _σζ_ 1 for all x . We can now apply Lemma D.9 to obtain the desired bound
|on the all-layer margin.p q´ p q|ď ă PX

We fill in the proofs of the supporting lemmas below.


-----

_Proof of Lemma D.7. By our definitions and Condition D.3, we have_

_g0_ _x,[p]θ,[p]ξ_ _h0_ _x,θ_ 2 _f0_ _x,[p]θ0_ _f0_ _x,θ0_ 2 _µ0_ _θ0_ _θ0_ 2 min _λ,σζ_
} p q´ p q} “} p q´ p q} ď } ´[p] } ď t u

Now we can apply the Definition D.1 of the correction function to get

_h0_ _x,[p]θ,ξ_ _ζ0_ _g0_ _x,[p]θ,[p]ξ_ _,ξ0_ _h0_ _x,θ_
r p q“ p p q q“ p q


_Proof of Lemma D.8. By expanding the expression for hi, we observe that_

_hipx,θq“fiph0px,θq,...,hi´1px,θq,θiq_

“fiph[r]0px,[p]θ,ξq,h[r]1px,[p]θ,[p]ξ0q...,h[r]i´1px,[p]θ,[p]ξi´2q,θiq (D.10)

We obtained the equality via (D.9). Now we write

_gipx,[p]θ,[p]ξq“fiph[r]0px,[p]θ,[p]ξq,...,h[r]i´1px,[p]θ,[p]ξq,[p]θiq_ (D.11)

We subtract the two expressions and add and subtract fiph[r]0px,[p]θ,ξq,h[r]1px,[p]θ,ξ0q...,h[r]i´1px,[p]θ,ξi´1q,[p]θiq to
obtain

_gi_ _x,[p]θ,[p]ξ_ _hi_ _x,θ_ _E1_ _E2_
p q´ p q“ `
where

_E1_ fifi _h0_ _x,[p]θ,[p]ξ_ _,...,h[r]i_ 1 _x,[p]θ,[p]ξ_ _,[p]θi_
p[r] p q ´ p q q

´fiph[r]0px,[p]θ,ξq,h[r]1px,[p]θ,[p]ξ0q...,h[r]i´1px,[p]θ,[p]ξi´2q,[p]θiq

_E2_ fifi _h0_ _x,[p]θ,ξ_ _,h[r]1_ _x,[p]θ,[p]ξ0_ _...,h[r]i_ 1 _x,[p]θ,[p]ξi_ 2 _,[p]θi_
p[r] p q p q ´ p ´ q q

´fiph[r]0px,[p]θ,ξq,h[r]1px,[p]θ,[p]ξ0q...,h[r]i´1px,[p]θ,[p]ξi´2q,θiq

We first bound E1. We note that for all 0 _j_ _i_ 1
ď ď ´

}h[r]jpx,[p]θ,[p]ξq´h[r]jpx,[p]θ,[p]ξj´1q}2 “}ζjpgjpx,[p]θ,[p]ξq,[p]ξjq´ζjpgjpx,[p]θ,[p]ξq,ξjq}2

_κξmax_ _gj_ _x,[p]θ,[p]ξ_ 2,1 _ξj_ _ξj_ 2
ď t} p q} u}[p] ´ }

The last inequality used Condition D.3 and _ξj_ _ξj_ 2 _σξ. Now defining H[1]_ fi _h0_ _x,[p]θ,[p]ξ_ _,...,h[r]i_ 1 _x,[p]θ,[p]ξ_
}[p] ´ } ď p[r] p q ´ p qq
and H fi _h0_ _x,[p]θ,ξ_ _,h[r]1_ _x,[p]θ,[p]ξ0_ _...,h[r]i_ 1 _x,[p]θ,[p]ξi_ 2, it follows that
p[r] p q p q ´ p ´ qq
_H_ _H[1][ˇ]_ max _θ,[p]ξ_ 2,1 _ξj_ _ξj_ 2
´ “ 0 _j_ _i_ 1[κ][ξ][max][t}][g][j][p][x,][p] q} u}[p] ´ }
ď ď ´
ˇ _σh_

Plugging in _gj_ _x,[p]θ,[p]ξ_ 2ˇ[ˇ]ˇ[ˇ]ˇ _hj_ _x,θˇ[ˇ]ˇ[ˇ]ˇ_ 2 _gj_ _x,[p]θ,[p]ξ_ _hj_ _x,θ_ 2 2λ, λ 1, and _ξj_ _ξj_ 2 2κξλ[, we]
} p q} ď} p q} `} p q´ p q} ď ě }[p] ´ } ď

obtain |||H ´H[1]|||ďσh. Furthermore, we note that H Pph0,...,hi´1qpX q, so we can apply Condition D.3
and Definition D.2 to obtain

_E1_ 2 _fi_ _H[1],[p]θi_ _fi_ _H,[p]θi_ 2
} } “} p q´ p q}

ďµ _H_ ´H[1][ˇ] (since }[p]θi´θi}2 ďσθ and |||H ´H[1]|||ďσh)

2λµκˇ _ξmax_ _ξj_ _ξj_ 2
ď ˇ[ˇ]ˇ[ˇ]ˇ _j_ ˇ[ˇ]ˇ[ˇ]ˇ ´ }

[}][p]

Next, we bound E2 by applying Condition D.3 and Definition D.2 again, using }[p]θi´θi}2 ďσθ:

_E2_ 2 _fi_ _H,[p]θi_ _fi_ _H,θi_ 2
} } “} p q´ p q}

_κθ_ _θi_ _θi_ 2max _H_ _,1_
ď }[p] ´ } t||| ||| u

_κθ_ _θi_ _θi_ 2max _hj_ _x,θ_ 2 _j_ 1
“ }[p] ´ } t} p q} u Yt u

_κθ_ _θi_ _θi_ 2λ
ď }[p] ´ }

where we applied Condition D.4. By triangle inequality, follows that

_gi_ _x,[p]θ,[p]ξ_ _hi_ _x,θ_ 2 _E1_ 2 _E2_ 2
} p q´ p q} ď} } `} }

_κθ_ _θi_ _θi_ 2λ 2λµκξmax _ξj_ _ξj_ 2
ď }[p] ´ } ` _j_ [}][p] ´ }


-----

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

_hipx,[p]θ,[p]ξi´1q“ζipgipx,[p]θ,[p]ξq,ξiq“hipx,θq_

where we used the fact that _gi_ _x,r_ [p]θ,[p]ξ _hi_ _x,θ_ 2 _σζ._
} p q´ p q} ď

_Proof of Lemma D.9. Note that if_ _θ,ξ_ _θ,[p]ξ_ 2 _a¯_ fimin _a0,...,ad,b0,...,bd_ 1, then by the conditions
}p q´p[p] q} ă t ´ u
of the lemma, |F px,θ,ξq´F px,[p]θ,[p]ξq|ă 1. However, because F px,θ,ξqPt´1,`1u for all x P _X_, the sign
of the output is unchanged, which means F px,θ,ξqF px,[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 τ [p][1][q]pθ[1]q, τ [p][2][q]pθ[1]q
will also have a perturbation of at most ¯a in each layer. The same reasoning as before then applies.


-----

