Statistically Meaningful Approximation: a Theoretical Analysis for Approximating Turing Machines with Transformers
Authors: Colin Wei
Yining Chen
Tengyu Ma
Venue: ICLR 2022 Submitted (2022)
Keywords: approximation theory
generalization bounds
sample complexity bounds
learning theory

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 $log(T)$. 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.

Under review as a conference paper at ICLR 2022
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, common unrealistic trick 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 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 log(T). We also introduce new tools for analyzing generalization which provide much tighter sample complexities than the typical VC VC-dimension or norm-based bounds, which may be of independent interest.
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 al. 2014] Zhou 2020 Yarotsky 2021). residual networks (1 (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 & Jegelkal 2018 Yun et al. 2019 (annai 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) |érezz et al. 2019 Korsky & Berwick 2019 Bhattamishra et al. 2020). Inlinite 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- precisioen,, finite-width RNNs cannot, as implied by streaming lower bounds (Alon) ct al. 1999). As another example, Park et al. (2020) exploit infinite precision in the parameters to show memorize arbitrary input-label pairs. However,
that neural net with parameter count sublinear in a simple counting argument reveals that this result cannot be proven using finite precision networks - there are 2n input-labeling pairs, but only 20(n) finite precision networks with o(zi) 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. Learability 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 learnailiity can be decomposed into studying optimization and generalization.

---

Under review as a conference paper at ICLR 2022
Unfortunately, rigorous analysis of optimization is unresolved even for simple two-layer nets (Mei 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 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 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 learabiliity (optimization renllttttio-elllteed concers can remain).
We present two case studies on SM approximation. First, we demonstrate that overparameterrzeed feed- forward 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 depth (Bartlett et al. 2017). Furthermore, VC lumension-based bounds would scale polynomially in the number of parameters in the network (Harvey al. 2017), which is problematic because for practical optimization concemn,, neural nets are typically overparameterized 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-bee transformers (Vaswani et al. 2017) which SM approximate these Turing machines. The sample complexity of the approximation depends on a polynomial in logTI 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.] [019]] Bhattamishra et al. (020)) have not been formally studied from 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 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 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, 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 lcarnabliiy;; 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. HHrnik al. (989); 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. BBrron (993) uses the Fourier transform write target functions as infinite- anfittte-widthh networks and subsamples neurons obtain widths
which depend only on target function properties. [ee 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 201 Arora et al. 2016 Telgarsky 2016) [Eldan & Shamir! 2016) Daniely 2017 Chatziatratis et al.) 22020) 2019). |eeggio & Delalleau 2 show separation for exact representation. whereas Telgarsky (2016) shows separation for approximate representations with univariate inputs. [Fldan & Shamir (2016) demonstrate high-dimensional functions that can be approximated by two-layer polynomaal -iioial--izedd neural networks, but cannot be approx- imated by lne-layer neural nets with subexponential hidden units. Via reduction to certain complexity theo-
2

---

Under review as a conference paper at ICLR 2022
retic questions, Vardi & Shamir (2020) show that proving constant depth separations may be hard. Malach al. (202T) 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] (0166) 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 al. (2018) show that (n) parameters are sufhcient to memorize θ n) 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 al. (20T9) 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 & Shashual [2066] 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 (Siggelmann & Sontagl (1995) shows that RNNs are Turing complete but leverages in- finite precision in the hidden activations. Chen al. (2018) extend this result to ReL.U activations and study implications in language modeling. Many variants of transformers are shown to be Turing-complest these constructions also rely on arbitrary precision (Pérez et al. 2019 Bhattamishra al. 2020). A number of recent works have also proven results for generating or recognizing formal languages with finite- preccsson neural nets (Weiss et al, 2018 Korsky & Berwick [209 Hewitt et al. 2020), but these results do not con- sider Turing machines or analyze statistical properties of their constructions. Bounding the sample complex- ity of SM approximation requires additional complications in both the construction and statistical analysis.
but
1.2 NOTATION
Let fog denote the composition of functions f and g. For family of functions G. let fog + (fog:ge]) [fgg(fg g) denote the family of compositions between and functions in G. For set S and function f f:S- let f(S) denote the set [f((): : EE S) E.. We use 1, to denote the all-one's vector in dimensions, with the subscripted omitted if clear. For iE [d]. we let La(i) denote the one-hot embedding in d-dimensions, which is at index i and 0 everywhere else. We use the notation Ö(-) to hide voly-logarithmic factors in the argument. The notation S indicates the existence of a constant factor such that the inequality holds. = denotes that the 2 and & relations simultancously hold. We use poly(-) to indicate the existence of polynomial in the argument which makes the equation true. For a set A (e.g.. the set of alphabet symbols for a Turing machine) lct A denote the set of all sequences of elements of A, where sequence length can vary.
Let P denote distribution over a space of inputs X. Let En be n ii.d. Rademacher variables sampled from (-1,+1), 1). The expected n-sample Rademacher complexity F on is as follows: (ad (or))_.. A2:pp [E........ [sup I E ((F()(( where (a;) 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 IR - [0.1]. The classical definition of e-approximation states that F e-approximates G with respect to E,P if for all GEG, there exists FE F such that P ((x)) E
The issue with this classical notion of approximation is that in machine learning settings, we only have access G, the function we wish to Ieam, through its values on a finite training set: (z,,G(zz, ) If we disregard this fact, we could end up constructing functions F which approximate G. but could have number of unrealistic characteristics such 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 elim- inate statistical concems related to fitting G on a finite sample. SM approximation. defined below, requires that G learnable via empirical risk minimization using models from F, when data is generated from P.
Definition 2.1 (SM approximation). F c-SM approximates with respect to f.P with sample complexity if there exists loss Fx x R [0,1] such that the following holds for all GeG:
3

---

Under review as a conference paper at ICLR 2022
Define Fe F to be the empirical minimizer of the loss f G on an i.i.d. sample (z,,))())))) (2.))= of examples labeled by G: F draw of (1=)==1, F approximates G in the classical sense: E2 (e (x))) <c.
Then with probability 0.99 over the
Definition 2.1 eases the statistical concems associated with classical approximation theory: given finite sample (2g (er,)(r))) the empirical risk minimizer of l over F is guaranteed e-approximate G on the population distribution. It is important that the losses / (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. may be reminiscent of PAC-learnability, there is a major conceptual difference: SM approximation unifies expressivity and generalization, whereas PAC-leamabilltyy is only concemed with generalization. The main focus of PAC-leamability 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 such that the empirical risk minimizer of ? on the training data can approximate functions in G. The following proposition provides several conditions on & which lead to SM approximation guarantees.
Proposition 2.2. For loss function é R. x R - [0,1] and distribution P, suppose there exists a loss ExFxX x RR [0,1], interuled as a surrogate loss for i, satisfying the following properties:
For all FeF, xE yETR, ((F (((()))))
2) For all Ge G, consider the function class LG A 1x- ((F,((FF : Rademacher complexity of LG bounded: Radn, (Cc) EC
Then the n-sample
3) For all GeG, there exists FEF with small surrogate loss: Eg- BLF.a((E
Then F o(et
SM approximates G with respect to t.P with sample complexity Vn
1
By Proposition 2.2 suffices that ? upper bounds the target loss l and has low complexity, and FF approximates g with respect to f, P in the classical sense. The proof follows from standard techniques for bounding generalization based on Rademacher complexity and is provided in Section
All-layer margin loss. We introduce one particular construction for used in subsequent sections, which
is motivated by the all-layer margin generalization bound proposed by (Wei & Ma (019b)) This bound
is based on data-dependent Lipschitzness measures (Nagarajan & Kolter [219 Wei & Ma 201 and provide stronger guarantees than classical norm-based bounds (Neyshabur
Bartlett et al.
2017 Neyshabur et al. 2017 Golowich et al. 2018).
We focus on the binary classification setting, where G(xr) (0,1), and study approximation with respect the 0-1 loss f.-1 (2.y)
0. 0) where yE [0,1) is assumed to be binary label. We consider a family of functions F parameterized by p-dimensional parameters AE fE θ TRP, with a general architecture function FiX's x Rº R. Thus, F= {a- Fzz,0) 0E }), and we sometimes use to identify element of F.. Throughout the paper, we define θ as a -norm bounded set: ||0]] < a, V. We define the parameter-basee all-layer margin PF: :R" x X' x {0,1) - R as follows:
PF (0 mmi ||1||
(2.1)
subject to (y F(r,
We omit the architecture from the subscript when 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, larger all-r margin, better stability, implies better generalization.
We modified the definition in (Wei & Ma 2019b) to consider perturbations 8 in parameter space, whereas Wei & Ma (019b)) consider perturbations to the hidden layers. The parameter-space formulation is simpler and subsumes the results in (Wei & Ma 20196). 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(z,0) predicts the correct label. We can leverage this property to construct surrogate loss. For some parameter
4

---

Under review as a conference paper at ICLR 2022
y intended to lower bound the all-layer margins, we define the loss l, follows:
1 if p(0.I,y) <
(0,r,,))
1 p(d. if ((0,..)) 5
(2.2)
Of p(0,a.y)
Note that E,, composes the classical ramp loss, which is used to prove margin- generalization complexity bounds, with the value of the all-layer margin. By our construction, it immediately follows that ((x)), > (Fxz))) as is required of a surrogate loss.
We show that to obtain sample complexity bounds for SM approximation of G in classification setting, it suffices to prove that functions in F can fit labels of Geg with large all- all-layer margin.
Lemma 2.3. Fix any neural net architecture F X x TRP - IR, and define Fa a {xx F(x,0)= :00000000 O) where assume θ c R2 is such that |0]|1 S. a all dE O. e O. Suppose that for all GE G. there exists O θ such that the following holds:
E Ex-r((((((0x, <C
(2.3)
Then Fa e-SM approximates 9 with respect to . with sample complexity Ō
<Plogg(e) + +1))
We note that Ö hides poly-logarithmic factors in the arguments, in this case, polylog( or a'log(p) factors. -0 The proof closely follows (Wei & Ma 2019b), deferred to Section A Section [ we also state a generalization bound for 0- loss based on (2.). which may be of independent interest. We use (2.2) and Lemma 2.3 to prove that neural nets can SM approximate Boolean circuits and Turing machines.
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: {0.1)" - - [0.1] on inputs bits is described by directed acyelic graph, with vertices of this graph referred to "gates" The graph contains m input gates of indegree O. which are identified with the input bits. The remaining gates each compute boolean function taking values at their parents as arguments, and designated output gate produces the output of the entire circuit. We consider boolean circuits consisting of AND, OR, and NOT gates, which compute the corres corresponding boolean functions on 2, 2, and inputs, respectively and are sufficient to compute any boolean function (Savage 1998). We also allow identity (ID) gates, which take I 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 to gates in layer i+1 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 & and width r. We say that a circuit with total gates has size Our convention will be that the set of input gates is considered layer, r m. We consider the following class of boolean circuits:
Syr. (0,1) - (0,1):G :G computed by circuit with depth q, size s, and width r)
We will approximate Gyr,s using family of width depth d feedforward ReLU nets pa- rameterized by linear weights and biases 0 (Wo, bo
Wa, ba) computed as follows: o( (Woz + by))..) ) + 64-1) + by where all intermediate layers have width for simplicity and & denotes the coordinate-wise ReI.U activation. The weight parameters are set so that for & i o d 1, W,E R Wo 12 and Wa E R gxx
(2, ()) = WWoo(a-100
xw The bias parameters are such that by E "h" for @ x d-1, 1, and b R.. To control the sample complexity, we restrict our attention to the set of parameters with total ||- nnor bounded by a, giving the following function class:
Fudda (x= (z, |00| & {a)
The following theorem states that feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity polynomial in the circuit size.
Theorem 3.1. Consider the class Gyr. of size-s, widthhr and depth-q layered boolean circuits, and the class Fundoa of neural nets above. Suppose w 2 r, 0228, and d=q.
Then for all >>0 O and any input distribution P over 10,13TT Funda e-SM approximates G with respect to Po.1P with sample complexity p log(wd)
5

---

Under review as a conference paper at ICLR 2022
We note that the bound in Theorem 3.1 only scales logarithmically in the width w of the network, even if is arbitrarily greater than the circuit width 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) is essential for proving tight sample complexity bounds, as other surrogate losses would give weaker results. For example, if we choose fo-1 as the surrogate loss, VC- dimension bounds (Harvey al. 2017) imply that Fuudd statistically meaningfully approximates Ge.r with sample complexity scaling ın poly(ug) under the conditions of Theorem 3.1 This suffers polynomial dependence on the overparameterized width w. which is not ideal for realistic setrings, where neural nets are often wider than necessary facilitate optimization. In contrast, our dependence on is logarithmic. Another possible surrogate loss is the outpur margin-based ramp loss, which can be used to prove norm- based sample complexities (Bartlett et al. 2017). However, these bounds depend on [ |Wallep (or related quantities), which would be exponentially large in d for the naive construction in Section 3.1
3.1 PROOF SKETCH FOR THEOREM 3.1
There are two key steps in the proof. First, given any layered circuit G 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 simulate the AND, OR, NOT, and ID gates.
Lemma 3.2. In the setting of Theorem 3.7 let G denote the layered boolean circuit, which we aim to denote function computed between the i-1-th and i-th layers of G, which we assume have r and ri gates, respectively, so G = 9g-10-..0.. or..gg- Then there exist functions fu--- where each f. is computed by feedforward ReLU net with two linear and activation layers, such that for all ie [q-1] and x (0.1)
compute using a neural net. Let g:: :4: 1
foo f
Thus, the composition F(-00) = fq-1 o-.o f1 satisfies F(x,0) 9) G(zz) for all zE (0,1)" Note that we omitted the dependency of 5q-15- on parameters 0 for simplicity.
Lower bounding all-layer margin. The next step for proving SM approximation is to construct a loss Z 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.
Recall that the all-layer margin ((()), measures the stability of the output F(z,0) to perturbations in to 6, and, by Lemma 2.3 it suffices to show that F has large all- margin on {0, 1)m Unfortunately, we cannot guarantee that the naive construction from Lemma 3.2 has large all-layer margin without further modifications. To remedy this issue, Theorem D.6 introuurss a generic way to convert the model F(..)) with possibly small all-layer margin on E 10.15TM into new architecture and parameter set F'((.('.. with provably large lll-layer margin on ze (0.1] (..1),m such that F'(xr.f)= = F (xx,6) on all inputs IE {0,1)T² The construction relies on introducing new layers to F to obtain F" and increases the total number of layers by only a constant factor. This step of the proof is formally stated in the following lemma.
Lemma 3.3. In the setting of Lemma 3.2 let =(.0)) o f1 be the neural net with parameters constructed compute the circuit G. There exist "correction functions" " S1 where Si is computed by a neural net with two activation and linear layers, such that the composition
F'(-0')+ S 20-20- fi
has large all-layer margin. Here 6' denotes the collection of all parameters. Concretely, pr (0',,, (e,,G((a))) pulyc for all xE 1 Note that we omitted the dependency of fuLi on parameters Of for simplicity.
We convey the core intuitions for Lemma 3.3 in simplified toy setting as follows. Consider the case where we start with an initial architecture f computing f(r,(W1.... Wa) = (TT-, W.) x 0.5, where W R. In this simplified setting, we consider W; w Vi. For input x = 1 and target y= 1, the all-layer margin is small: (1,,1) tt. where the architecture is in the subscript. Indeed, choosing à; 3
we have f(1 - -)) 2 d 0.5 exp3)) -0.5 155<00 0. Thus, by the definition of all-layer margin, ((((1,...1),.1..1
Now we will insert ReLU layers in f to increase the all-layer margin to 2(1). We use ReLU layers to implement the round function, which has the key property that round 2) 1 V2 2/3.

---

Under review as a conference paper at ICLR 2022
0
if
Proposition 3.4. For any ZER, R, we can implement the function round(=)
3x
f/1/3<2<2/3
if232/3
via a feedforwarr ReLU net, as follows: = = - 22333.
We consider the following function J. which inserts round between every layer in
((r,WW,,.,,Wa)) = roundd W Waround (
(3.1)
For this demonstration, we ignore the parameters of round, though the actual proof considers these param- eters. The following claim shows that B.1 preserves the output of f while increasing the all-layer margin:
Claim 3.5. In the setting above, holds that f(1.(1.....1)) ( f(1.(I.....1)) and py((1....1,,1.11) >
This reflects a significant increase in the all-layer margin, while only increasing depth by a constant factor. The proof is simple: we observe that if 6, < / for all i, the function output will not change because rzund(z)= = V= 3. This immediately gives the all-layer margin lower bound 5
To apply this construction more generally, we note that round corrects errors in previous layers. In the more general setting, we insert "correction functions" between each layer satisfying the key property that ((h' h if h is the intended output of the layer and h' is any perturbed value satisfying 1 3- Since intended outputs of layers in the function constructed by Lemma 3.2 are binary-valued in [0.1] because F simulates a boolean circuit, we can simply apply the function round constructed in Proposition P3oposstion c.eeettettt 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 large all-layer margin
(Theorem D.6 on all x (0.1)'M. This leads to the proof of Lemma 3.3
We can complete the proof of
Theorem 5. 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 log? 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 al. 2018 Pérez al.. 2019 Bhattamishra et al.) 2020). Thus, we obtain an exponential improvement in the dependency on T.
We briefly describe Turing machine; see (Sipser 2013) for a more thorough survey. A Turing machine a model for computation specified by tuple A.5,,.Z containing A, a transition function S: A 2 Ax 1-,,+1), and set of terminal states Z 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 runtime (Sipser 2013). Given an input xe xe.4" 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.
of states Z, a tape alphabet
We let TM (.S...s....m) denote the function computed by the Turing machine, which produces an output in {0.1) (if the machine halts). Fixing the alphabet A. we consider the class of binary functions computed by Turing machines with at most & states terminating in T steps:
GR.T d (-- (M (1) (x)::[]) kk and Vue X,TM (2.A,,,2.m) terminates in 7 steps
(4.1)
4.1 TRANSFORMER ARCUITECTURE FOR SM-APPROXIMATING TURING MACHINES
We study approximation of with a family of architectures consisting of both an encoder and decoder com- ponent (Vaswani et al. 2017), described as follows. The encoder architecture simple and only performs an embedding of the input symbols, using learnable symbol embeddings Ee [ and fixed positional encodings ((2). R Given input A* with m symbols, the encoder produces m output vectors in IR" T0 via Ex, E.z. + 3(i), where Enc; denotes the output of the encoder the i-th position.
The decoder iteratively computes an output, running for steps. We define a transformer layer the decoder as a sequence of modules consisting of decoder self-attention, followed by encoder-decoder attention, followed by three feedforward ReI.U layers.
7

---

Under review as a conference paper at ICLR 2022
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-conputed representations hy ......./ and current input representation h'. The layer first applies the key, value, and query functions as follows:
Tu. Q(1) Qo,)( ((b))....Q(M))) K(h:)
1. Vo, (h.,V(h)....V(bb))
where Ko and Vo are fixed "null" key and value vectors which are learned parameters of the layer. Letting J denote the set of indices [j:Ty- = max To....Ts)) the attention layer performs hard-max attention (Pérez
ct al. 2019) to compute the output, as follows:
Atta(h' (h))...,.)))= = h1'
Σ JEJJ
U/
Our theory also applies to the standard softmax attention used in practice, but we focus on the hard- max case for simpler proof. Let h1 denote the representation computed by the j-th layer of the decoder at timestep At timestep i, decoder self-attention at the (j+1)-th layer computes Aum (1(2) .(, ...,.h, ())). Letting em denote the encoder outputs, encoder-decoder self-attention at the (j + 1)-th layer and i-th step would compute Attn(h (e))...,Cm)).
Transformer layers. We use feedforward layers which apply 3 standard ReLU layers, as follows: FF(h) & (Wgd( W2d(WW2 (22d(W (ebb() +b2)))))+++++++) bb). Our theory also allows for residual feedforward layers, and the architecture here is chosen mainly simplify the construction.
A transformer layer applies these constructions in sequence. Letting H.") -14 (..,",,,!,1)))
denote the output ())
after the j-th transformer layer for timesteps 1 ttt i, and (66 the parameters of the layer, we compute
n6i+ 1 Attn (3) _,,,0,,00 "07,00++100 1.dc--mmm))
h1 ((+1ea)) Attn((h (+1,dkc)) ((),..,,mm 000 t.mesal))
Tr(h _H(" "e (m).....mm) F1(1 .00+
Note that we included the explicit dependence of the attention layers on the parameters for completeness. We now set n. (0+1) = =Tr(n?) _H!") (61t).)))))B(++1))).
Decoder outputs. We consider d-layer decoders, so o, h (d) denotes the output of the decoder at time i, which is also inputted the decoder time i+ 1 follows: (0 n, + + 1). The initial decoder input hg (0) is trainable parameter. The decoder runs for a fixed number of timesteps T' and produces the prediction T (4)) For simplicity, we assume T' TT, T,T,00 the computation time of the Turing machine family.
Note that our architecture allows long (length 7) decoding sequences, whereas typical architectures in practice use decoding sequences with roughly the same length as the input (Vaswani et al. (017). The architecture we study is similar to ones studied by (Pérez. et al. 2019 [hhattamishra et al., 2020).
We use -ー (r. to denote the described transformer architecture with parameters 0, wi-dimensional hidden layers, d transformer layers in the decoder, and T decoder steps. This leads the following class of transformer functions: Fund,a, = {x~~ (xr,0) [|0)] & az). The following theorem states that this class of transformers SM approximates the Turing machine family G defined in (4.l) with sample complexity polynomial in logT, Ie and |A].
Theorem 4.1. In the setting above, consider the class & of functions computed by Turing machines with most lo states, alphabet A, and computation time bounded by T steps for inputs DE X. Suppose that ž A| + HogTT, d=log[, and a (plly(k.)AAlloog..
Then for all >- 0 and any input distribution P over X, F FuddTT 6-SM approximates G with respect to fa,.P with sample complexity poly (kg])
loglwe)
As with Section we set the surrogate loss E in Definition 2.1 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. 20188) Pérez et al. 2019 Bhattamishra et al.
2020). First, the VC dimension of J F at least u/T This is because transformer architectures
8

---

Under review as a conference paper at ICLR 2022
which contain decoder component can express RNNs, which by lower bounds have VC dimension at least wT (Koiran& & Sontag, 1998). This indicates that using &..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 cor- rect norm-basse 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 the all-layer margin surrogate loss 2.2 is essential for obtaining our sample complexity bounds.
Section 3]
4.2 PROOF SKETCII FOR THEBRRM
Following Lemma 2.3 our goal is to construct transformer which can simulate Turing machines with large all-layer margin, namely, 52 pol((A,[[[]ooTT)) The fundamental limitation of prior work (Pérez et al. 2019) towards attaining this is that the positional embedddings are required to store values as small as
p Our construction cannot afford to rely on values this small informally, if the construction relies
on the exact values of these small entries, then the all layer margin would be at most (T) because perturbing the layer by the small entries could change the prediction. Instead, we propose using Bin(i),
the binary encoding of i in [logT'] bits, as the positional encoding for timestep i. This allows us to use unique positional encodings for each timestep which do not rely on arbitrary precision.
We describe the construction of the transformers. Fix a Turing machine Ge We first require notation to describe the computation of G. For input x X, we define (x), (,(2)) to be the Turing machine state and symbol under the tape head at the conclusion of step i. We let (2)) denote the location of the Turing machine head at the conclusion of step i. During the timestep, the Turing machine computes S(z (x) ,a;- (ar)), writes a new symbol under the head at location I, (z), and moves the head either left or right. Let u, (2) denote the symbol written during timestep and (x()) right, the movement direction of the head.
Following (Pérez et al., 2019) with several key modifications, we simulate the Turing machine using the transformer as follows. Each timestep will maintain the invariance that on contains an encoding of 2,()), and (xr. Given that this invariance holds until timestep i, the transformer simulates timestep ++1 1 of the Turing machine with the following steps:
1) Use feedforward layers to apply transition S on 2x(2) and a,(x), which can be read from ot. to obtain 2641 1 (Ir), Uh+ (1)) and movement direction (x)) E (left, right).
2) Using feedforward layers, compute 4++122) (z) from (++(xx) and the encoding of ((x) in og.
3) Compute 4++ (xr) We use decoder self-attention to search over past timesteps which wrote to 4+)(x). Our aim is to find uy (1)), where i' = max(j o i :t:::::11((===-//////
We implement
a binary search over past timesteps j. which is needed to find the largest j & i + I where The binary search can be implemented with O(log(')) decoder self-attention layers, and the construction ensures large all-layer margin.
4) If no such i' from the previous timestep existed, we check whether (x) 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), (+1(x) must contain the blank symbol (meaning it wasn't ' visited yet by the head). Thus, we have computed 0++ 1 (I), have all the information needed
to compute the new embedding 0++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 network with intermediate layer entries in (0.1), we can use the same correction function as Section 3.1
which rounds to the nearest bit. The full proof is provided in Section C
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 leamability. 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 Ae of statistically meaningful approximation. Fxamples include proving more upper and lower bounds for statistically meaningful approximation for different target functions and neural net architectures, and using our definition as lens to compare architectures.

---

Under review as a conference paper at ICLR 2022
6 ETHICS AND REPRODUCIBILITY STATEMENTS
An ethics statement not applicable for this work this work is mainly theoretical and is several layers removed from empirical applications.
Section A containss the proofs for Section 2 Section B contains the formal construction and proof for
boolean circuits. PrationnCcontainss 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):337-147, 1999.
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee, Understanding deep neural networks with rectified linear units. arXiv preprint L.0491, 2016.
Chenglong Bao, Qianxiao Li, Zuowei Shen, Cheng Tai, Lei Wu, and Xueshuang Xiang. Approximation analysis of convolutional neural networks. work, 65, 2014.
Andrew Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information theory, 39(3):930-99)) 1993.
Peter Bartlett, Dylan J Foster, and Matus Telgarsky. ppectrallynnormalize margin bounds for neural networks, arXiv preprint
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):2855-301. 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 trans- formers 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: (0.18653/v1/2020.ommll 1.377 URL http//20020.cc11111.3.
https://www. ac www.ww...ccom org www.ee/.rrr/atttooooo///0.......
Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Depth-width trade-offs 2019.
for relu networks via sharkovsky's 's theorem. arXiv preprint
Vaggos Chatziafratis, Sai Ganesh Nagarajan, and Ioamnis 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-HIT, 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: 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. 696. PMLR, 07-10 Jul 2017. URL
.ll.. citess//v5//anielle at...a...mm..
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pp. 907-940. PMLR, 2016.
10

---

Under review as a conference paper at ICLR 2022
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- 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: 1.022331,, 2016.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-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. Runs can generate bounded hierarchical languages with optimal memory. arXiv preprint arXiv:2010.07515, 2020.
Kurt Homik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 2(5):359-36 366, 1989.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kemels, transportation mappings, and universal approximation. In International Conference on Learning Representations, 2020. URL
Pascal Koiran and Eduardo D Sontag. Vapnik-chervonenke dimension of recurrent neural networks.
Discrete Applied Mathematicss 86(1):63-79 1998.
Samuel A Korsky and Robert C Berwick. On the computational power of mns. arXiv preprint 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
.mmggggmmmm......mmm. wwwps/wwsss......p /etee//////1//111ee Leeleeellll 7a html
Moshe Leshno. Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with 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 a universal approximator. arXiv preprint arXiv:/806 10909, 2018.
Eran Malach, Gilad Ychudai, Shai Shalev-Shwartz, and Ohad Shamir. The connection between approx- imation, depth separation and leamability in neural networks. arXiv preprint 1rXiv: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 Acudemy of Sciences, pp. E7665-E7671, 2018.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep 2019.
networks via generalizing noiseeres arXiv preprint /905
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-normalizee margin bounds for neural networks. arXiv preprint (eXiv:1707.09555 2017.
Quynh Nguyen and Matthis 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 andial-basis-fume networks. Neural computcatoo, 3(2):246-257 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.1336 2020.
Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. arXiv preprint arXiv:1901.03422 2019.
Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier. Universal approximations of permutation invariant/equivariant functions by deep neural networks. arXiv preprint 1rXiv:1903.01999, 2019.
J. Savage. Models of computation exploring the power of computing. 1998.
11

---

Under review as a conference paper at ICLR 2022
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. Recurrett neural networks are universal approximators. International journal of neural systems, 17(04):253-663, 2007.
Hava T Siegelmann and Eduardo D Sontag. On the computational power of neural nets. Journal of computer and system sciences, 50(1):132-11 150, 1995.
Michael Sipser. Introduction 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. L
PMLR. URL http: http::ttpp.orceeeddiicee pwwpeedineengg.mmm ml wtt.:sssmw..pp.s//eeeeeeeee 9/te garsky! 6. ht.ml
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 barri- ers. 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 Asso- nww. pttpppp/////ppp//////////.
ciates, Inc., 2020. URL ptttps://proceettt el f.fee61
Ashish Vaswani. Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv: 706.03766, 2017.
Roman Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint arXiv:2001.06923 066938 2020.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. arXiv preprint 19X5v:1905.03684, 2019a.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification 2019b.
via an all-layer margin. arXiv preprint arXiv:
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite precision mns for language recognition. arXiv preprint arXiv: 1805.8005..40 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 powerful memorizers: tight analysis of memorization capacity. arXiv preprint 18110:1110 2018
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transform- ers universal approximators of sequence-tor toe--tt----ggeee sequence functions? arXiv preprint 11Xiv:1912.10077. 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint ar 1.030350, 2016.
Han Zhang, Xi Gao, Jacob Unterman, and Tom Arodz. Approximation capabilities of neural odes and invertible residual networks. In International Conference on Machine Leurning, pp. 11086-1 1095. PMLR, 2020.
Ding-Xuuc Xuan Zhou. Universality of deep convolutional neural networks. Applied and computational harmonic analysis, 48(2),787-794, 2020.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS FOR SECTION 2
We prove Proposition 2.2
and Lemma 2.3
Proof of Proposition 2.2
Let (2:) denote n i..d. training examples drawn from P and fix Geg. De- fine [(F) a Rg ((x)) and T((F) a " ((,,,, Let Fe denote argmin FEF (.)... the empirical risk minimizer of L, which we aim to show has population loss fitting G bounded by O(e+ v.) By standard arguments using Rademacher complexity, have with probability 1-ô,
log(2/6)
sups (FF)L(F) & 2Rad,, pl p(Ca)+ FeF
n
log (2(()
< 2e
(A.1)
Now note that by the condition 3) on f, there exists F with L(F*) c. Now we have
L(F) (L(F) ( ((F))))) L(F))
We bound the first and last term in parenthesis by applying A.I. and the middle term bounded by O, by definition of F. It follows that
log(2/5)
L(F))L(F") 4c++2
n
log(2/8)
T.(F)) $ 5c
n
where we used L(F*)((( <. Finally, we use the fact that l upper bounds E, so Eur P(( Plugging in 5 0.01 gives the desired result.
Proof of Lemma 2.3 GeG we have
We first observe that (1(0))))<((((pp..)))) <n) by definition, so by 22. for all
inf E ((0,,
Thus, it remains to check the Rademacher complexity condition for applying Proposition 2.2 Fixing any GeG, define the function class LG 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), pp....y) p( ,2,y) & 10-0'112 for any 0,0' IRP. Let Nft.V (e, denote the e-covering number of θ in | 1| and N Hle (e,LG) the covering number of LG in the norm defined by H H' max
H(x) H (x)) for any H.H's Lo. The arguments of (Wei & Ma 2019h) imply that log/ (e,Lo) log/ (7e,0) & o(1 (oggg(p))
where the last inequality is from standard covering number bounds for || 11 balls. Now we can apply this covering number bound in the Dudley entropy integral, another standard step bound Rademacher
aloggn/log(e))
complexity, to obtain that for all n, Rad,,p(Co $ 7//n
(see arguments (Wei & Ma 2019b for
more detail). Solving for n such that the r.h.s. of this equation is bounded by gives the desired result.
Note that from the proof of Lemma 2.3 would also obtain the following parameter-space all-layer margin generalization bound as a corollary, which may of independent interest:
Corollary A.1. In the setting of Lemma 2.3 let Q denote a distribution over (a:2)) pairs, with (acalk Yi=1 denoting a set of n i...d. training samples from Q. With probability 1 1- over the draw of the training samples, all classifiers F(.0))JJ which achieve zero 0-1 training loss satisfy
a log(((p) Vn
1
Ex (p=o))or(((220)..))
+
(A.2)
p(0,2..0)
where & ( log( log(1/6) log())) is a low-order term.
The proof of Corollary A.I 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).
13

---

Under review as a conference paper at ICLR 2022
B PROOFS FOR SECTION 3
This section completes the proof of Section 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 G;: 10,1I--- ( denote function computed between the i 1-1tth and i-th layers of G. which we assume have 7;-1 and r; gates, respectively. Let denote the following 2-layer neural net architecture, parameterized by 0
f(h,0) = ( W (1)b))+++ bb2)
Then there exist 0 with = such that for any he (0,1)"
f(h,))
where takes ht and appends w p--r--1 zeros, and likewise for (,())..
We note that the proof of Lemma 3.2 follows by applying Lemma B.1 q times. Using Lemma B.1
we can complete the proof of Theorem 3.1
Proof of Theorem 3.7
Our proof will construct a neural network to compute any boolean circuit with all-layer margin lower bound poly(ra)) By Lemma 2.3 this will be sufficient to guarantee meaningful approximation.
There are two steps in our construction: first, given any layered circuit Ge Ggg:r. we construct a neural net that directly simulates G by computing the layers of G one-by-one. Our construction shows that we can compute every layer in G using two feedforward ReLU layers, and results in 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 I Lemma 3.3 To do this, we insert "correction functions" (Definition D.1) between every group of layers in F. These correction layers leverage the knowledge that unperturbed outputs of these layers should be contained in (0,1)* and perform elementwise rounding to map perturbed values back to {0.1)". Theorem D.6 D66 formally shows that by introducing these correction layers can guarantee a lower bound on the all-layer margin roughly depending Furthermore, each correction layer can be computed via two feedforward ReLU layers, so introducing the correction layers only increases depth by a constant factor.
the Lipschitz constants of each individual layer.
We implement the proof plan by first applying Lemma B.1 g times in order to obtain the function F computing G (with padding) mentioned above. The total 1 -norm the parameters so far most 8. Now we use the correction function described in Proposition (3.4, which we apply coordinate-wis on non-padding coordinates. We apply the correction functions after each layer constructed in Lemma B.I 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 |-||: -norm at most (ss).
still required in order to apply Theorem D.6 The neural net output is in {0,1)%m , not { [1,,1]; we can remedy this by setting the last layer to compute the linear transformation - 22 - 1 on the single non-padding coordinate corresponding to the output. Second, 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 || I-I| -norm bound O(s d). so that the set of constructed functions contained in Funddo. Thus, we showed that for GeGgrr.. there exists 0 such that F Fxx 2G 1 for all Ze {0.1)m.
Note that at this point, minor modifications
Finally, it is straightforward to check that Condition D.3 for Theorem D.6 satisfied for Lipschitzness parameters which are polynomial in the circuit width r. Thus, we apply Theorem D.6 obtain a lower bound 9 poly(r.g] poly(s) on the all-layer margin for every input zE (0.1)" m Finally, we directly apply
Lemma 2.3
using ? f to obtain the desired result.
The following proposition will be used to construct basic gates in the circuit with simple feedforward ReL.U network.
Proposition B.2. Let
Φ Z2
E {0, 1)2 be binary inputs to AND and OR gates. The following
feedforward ReLU networks compute the AND and OR functions: FAND(Z) = Φ(I1 + 22 - 1), and FOR (x) 1- 6(1 -1 22).
14

---

Under review as a conference paper at ICLR 2022
Each row of W1 and value in b1 will correspond to single entry in the output of G.. The same applies for b2. W2 will be set to diagonal matrix with entries in (-1,0.13. For the O entries which only serve to pad the dimension, we set corresponding values in W1 ,2,, to be
Proof of Lemmaa B.1
O. For the remainder of the entries of G; corresponding to actual gates in the circuit, in the case that the gates compute AND or OR, we fill the values of corresponding rows in W1 W1,bg. W2 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(=) = 1- for EE [0.1] I on coordinate we can set the j-th row of Wi have -1 on the diagonal and everywhere else, (b1), = (b2) = O. and (W2) = 1. It easy check that ||0|] = (r;) with this construction.
C PROOF OF THEOREM
C.I ADDITIONAL SETUP AND NOTATION
We fix any Turing machine Ge 9 and construct a transformer which 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 fixed initial state Zint We let { A denote the blank symbol, which initially fills all positions on the tape which aren't 't part of the input. We construct a transformer that simulates the Turing machine up until it reaches terminal state in Zeemm at which the transformer will loop in that state until it hits computation time T.
We introduce some notation which will appear throughout the construction. Define Upos + [log, T7. We use pas to denote the effective dimension of the position embedding, as only Upos coordinates will be non-zero. For 0 & < T, define Bin(i) E Tges to be the vector containing the binary encoding of d: Bin(t), 1 if
the binary representation of contains I in the j-th bit and 0 otherwise.
For simplicity, the proof will focus on the setting without overparameterrizaton, where we choose the di- mension w = WTM + | + - + 33p + Wser for storing all the hidden representations of the model, where uxr== Upss + |A| ()). We can extend our analysis allow for arbitrary over-pavanee parameterization using w> WTM by designating certain subset of the coordinates to always equal Ó, and performing calculations using only subset of ιTM coordinates. We group the WIM coordinates using the following symbols: st for encoding the state, sym,, sym, for encoding symbols, pos, and pos pos3 for encoding position, and scr, which is used as scratch space. Thus, for I",, we can index its coordinates via the groups as follows:
ha
R |
h
ERA
R
h
R
R M/po
E IR
When the meaning is clear from context, use the superscript index coordinate groups as described.
The position embedding 3(1) defined formally so that ((j)pt) = Bin(i), and ((i)) is in all other coordinates. The encoder embedding matrix E is such that
(nc;(ar) sym 1 (x)
(C.I)
) Bin(i)
where (2) has 0's all other coordinates. embedding function e: Rd for the encoder is defined such that e(z:)>m, [1)(((), the one-hot encoding for Z A, and 0 everywhere else. We use Or to refer to the output embeddings of the decoder. Our construction maintains the invariant that the output embedding o encodes 2, (z), a, (x).) 4(x) for each i. To achieve this, maintain
0f (z)(2(()))
sym, [(((((())
(C.2)
pos Bin(L(x))
15

---

Under review as a conference paper at ICLR 2022
and o, has 0 at all other coordinates. Thus, the imput + to the decoder step i+ is of the form (o++,((t11)==1111(11
(o++,((++1))))) / (1)
(C.3)
(o -)) Bin( (0++ ((++((())))))))))))))))) Bi)(4(2:))
C.2 COMPLETING THE PROOF
We implement the first step 1) in Section 4.2 consecutive feedforward ReLU layers, but layers where the attention parameters are O, and only the feedforward layers are instantiated.
usinn the following lemma. Note that the lemma uses two actual proof we will simulate this using two transformer
Lemma C.1. Let O denote the set of decoder inputs in the form (C.3) encoding 2-1( az (z). (x)
for some timestep i. For parameters 0 (W1,ba ,b, W2,b2). consider the following function computing sequence of two feedforward ReLU layers: (h,0) Φ (W220(W 0 such that for decoder imputs heO,
(Wa Wih+ b1) b2). There exist parameters
= = (z)))(
[(h,0)smm Ln (s;())
(C.4)
[(h,0)mt Bin(1)
[(h,0) = Bin(4i-n(ar)
Furthermore, fh. will contain one-hot encoding for (I)). and besides this, f(h,0) is at all other
coordinates. The parameters satisfy [0]] 0( Wpas).
Proof. We follow the construction used in Lemma B.2 of (Pérez et al 2019). The first layer computes + so that the first
a one-hot encoding of the state, symbol input pair. We choose W1 R RWIM |ZA rows are described by:
(Wi) = (1) (Wi (W))).m) (a)(a)
and everywhere else. The remaining rows of WTM rows of W1 simply implement the identity mapping. We choose by that its first ||| entries are -1, and all other entries are O. We observe that from this construction, for all he where encodes 24- (z).
1
(Wih+b1)=
h
This because before the ReLU, the first ||||A| entries of Wih will have on the (z--((x) (1))),;a,))) 1 (-)) entry and be bounded by everywhere else, so adding an and applying the activation will zero out all but one entry.
Now is simple to pick W2 so that ((h,0) is as desired because we can construct to exactly encode the output of S(z,a) for each of its first (2,a) columns and copy over the other necessary entries of needed by C.4)
The next lemma demonstrates that we can use an additional sequence of feedforward ReLUU layers to produce Bin(4(x)), given Bin(4-1(z)) and (ız)).
Lemma C.2. In the setling Theorem 4. and Lemma C.I above, there is Sunction I parameterized by 8 composed of (wrg)) feedforward ReLU layers such that for any h computed by the function in
Lemma C.I in the form C.4 at timestep i,
f(h,0) = (z)()(
f(h,0)990 sy00 1 LAi (u,(x))
f(h,0) = Bin(1)
(C.5)
f(h,0)mm Bin(4;-2(2))
1(h.0)o0% - Bi)(2((x)
At all other coordinates. Fhh, 0) takes value 0.
Furthermore, the parameters satisfy
|00|| 1 Owrppl [2|+ |A| Wpws)).
16

---

Under review as a conference paper at ICLR 2022
Proof. As the construction of Lemma C.1 encoded (x(x), the movement direction of the head, feedforward ReLU layers to implement binary addition to either add or subtract 1 from (z). Let i) 3ا denote the bits in the scratch dimensions indicating the head movement, where indicates right. Then more specifically, first use O (2pps) feedforward ReLU layers to
1,0g = indicates left
and V1 = 0,00 compute (-1 (-) 01, and then (uppos) additional feedforward ReLU layers to compute (4-1(x) 01 + Note that the output would always ((x) by the definition 01.22.
It remains to implement a module which computes Bin(j- v2) given 01 Bin(j), and Bin(j + 02) given 22 Bin(j) for any jE [7]. We can express the binary addition by a depth- (wpp)) binary circuit, which can in turn be expressed by neural net with (wpp)) layers where each weight matrix has ||- -norm (12) [A| + Wpos) (which is required to implement the identity mapping to copy forward the other dimensions of which aren't tt involved in the binary addition). This gives the desired total ||| -norm bound.
The next lemmas implement steps 3), 4), 5) in Section For the following lemmas, it will be helpful further index the scratch dimensions as follows: for vector he Wsers
h ER h e e IR
h STT
h e Ri
1,200 e IR33
Lemma C.3. In the setting of Theorem 4.1 and Lemma C.2 above, fix any timestep i and define 4.))). If such that 1-1(x) (x) exists, we define i' otherwise. Consider any H, = ha), where he is computed by the layer in Lemma Lemma for timestep t, and in the form (C.). There is a fiancton parameterized by 0 consisting of (Wips)) total self-attention and linear layers such that for all such Hi, the following holds:
max & t i::::: (
[(h,,H,00** (2)(2;(²))
f(,,HH (2)()))
H4,,,H = Bin(i)
H,, = Bin(4-1(x:))
(C.6)
H(,,,H,,0000 = (in(4(x))
H(h,,H; = LAl (1y (u)))))
ff=0 otherwise
0
F() 1 0)
At all other coordinates, 1 1 (1 Wpos))
F(H, 0) takes value 0.
Furthermore, the parameters satisfy
The proof plan will roughly implement binary search to find i', leveraging the attention layers. The first step in the binary search is to verify whether i'>00 O, described below.
Claim C.4. In the setting of Lemmaa C.3 let H,= hi....:; be the input representations for timesteps 1....,.. Suppose that each for 1 itti salisfies the following:
hp Bin(t)
(C.7)
h, Bin(4-1(x))
Additionally, suppose that h2 of the form such that
Then there is a function f(0) parameterized by
f(0) H,, =0
(h, =0
(C.8)
()
The function f(0) can be computed by single decoder self- atteentttnno layer with ||0]] = O ((ppo))
Next, we implement the binary search itself, using wpes self-attention layers. Each step the binary search reveals single bit of L. so the j-th attention layer will compute representation storing the j most
17

---

Under review as a conference paper at ICLR 2022
(0.1) denote the binary encoding of the most significant bits significant bits of f' We let (
of (Bin,())) (Bin())) for و Ej and (Bin for j. We also (in = We use the superscript ( to indicate the j-th set of layers the binary search. The following claim implements
each step of the binary search rigorously.
Claim C.S. In the setting above and of Lemma computed after the j-th group of layers for timesteps through for 0 = upes 1. Suppose that each hy for i t i satisfies the following:
C.3 let 11!0)
11)) ,..,,h
h( be the representations
h 100 Bin(t)
(C.9)
h 111lpps Bin(4-i(22))
In addition, suppose that 1 satisfies:
n ())aaa
(in
it' otherwise
(C.10)
(h. (1( 1= 1((=00)
with all other coordinates matching the quantities prescribed in (C.5) parameterized by 0 such that
Then there is function f(++1)
(ot 11S00.000 0) =0
pott H 0)sas Bin
if'' otherwise
(C.11)
go+t H 0)10h 1(1>00
with all other coordinates matching those prescribed (C.5) We note that f(5+1) consists of a single
decoder self-attention layer followed by single feedforward ReLU layer, with |
|A Wpos).
At the end of the Whoc-th application of the binary search, we would have found Bin(F") exactly. It remains to apply another attention layer which attends directly to timestep i' and copies uz().
Claim C.. In the setting above and of Lemma C.3 let H = bii....ly be the representations computed
after the Wpos-th th group of layers constructed Claim C.3 for timesteps through Suppose that each for 1 & & i satisfies the following:
h, 1 | (ux())
N, = Bin(t)
(C.12)
1/00 (x))
In addition, suppose that h; satisfies:
hmm
Bin(t')
if'=0 otherwise
MTT
(C.13)
(h (0T4 - 1
with all other coordinates matching the quantities prescribed in CC.)) Then there is a function f(up+(1) parameterized by 0 such that f H,,, computes the desired output in (C.6). Furthermore, f( consists of a single decoder self-attention layer followed by single feedforward ReLU layer, and [0] 0( A|| Wpx)).
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 avoid confusion with indexing timesteps. We f()) to be the function defined in Claim C.4 We note that
18

---

Under review as a conference paper at ICLR 2022
inductively to obtain layers (()) f(u).))()))) where their applying their composition results in representations satisfying (C.12 and (C.13). Now we set f("m=+1) to be the function constructed in Claim C.5 which gives the desired output. Finally, note that by summing the I-Il1 bounds for the parameters constructed in each layer, we can finally obtain | 1 = (ppo ( [A| + )p.s))
layers output by f(0) satisfy the condition of Claim C.5 so apply Claim C.5
We fill in the proofs of Claims C.4
and C.6 below.
Proof of Claim C.4 To construct the decoder self-attention, the query function will be of the form Q(h) Woh + by and (hh) Wkh + bx. where Wo, Wx IR (x)x and bo, E Rd We
choose the parameters such that the following equations hold:
Q(h) 1:rpp
2/
Q(h) 11 =1
and
((h) 1:00po
2//pos
(m=))m++100
The value function (h) is such that V(h)a = 1, and V(h)e 0 on all other coordinates L, which can be implemented by a linear transformer. Finally, we the null key Kg and value Vo such that (Ko)mw = Wpos 1, with O everywhere else, and Vo = O. Letting 0am denote the attention parameters, the layer is of the form
(
To see that f(0) satisfies (C8). observe that if 1' 0, Q(h,) ((h,)T((hh)) wiss by and construction of Q,K. On the other hand, Qhh.) Ko upos - 1. Thus, argmax, Q(h,) K (ha) [i]. which implies by the construction of V. In the other case where i' = O, we note that Q(h,) K(hy) & Upos for all 1 & i, so the null position is attended to. By construction of Vo, this implies ((0) (1) = 0. As V.V. are on all other coordinates, follows that (C.8) holds. It's also easy to observe that the |@]] is as desired.
that ((,, 0)
Proof of Claim C.S W Wih++ bag and the key function is of the form K K(h) Wxhh bn. where Wq, Wxe (0 +j x and bq +j+2) We choose the parameters so that the following equations hold:
The first layer in f(++t) computes decoder self-attention. The query function is of
the form Q())
Q(h))::ppp 27,
Q(h) 1: 2/111)
Q upoti++1 =1
Q(h) Mpo
and
K(h) 2/.0000 -1
K K(h) hep 1:mpp +j+1 21 1./+1 -1
K(h) mpo =
Both of these functions can be constructed via linear transformations of h, with [Wel++ |W ||| +bb2
and V(h)), = 0 on all other coordinates, which is also easily implemented by linear layer. For the attention, the last quantities to construct are the null key Ko and value Vo. Ko will satisfy (Ko) + +++ = wpos +j, with O everywhere else. Vo will simply be 0 on all coordinates. Letting 0mn = -Wo W bk. ....bb.WW.. Ko. Vo) denote the attention parameters, the first layer will now be in the form
| (wppss) Now we construct the value function V(h) Wy by such that v(h).
f ( H..') 9mmn) Attn(h D Pamm)
19

---

Under review as a conference paper at ICLR 2022
where Attn uses the constructed key, value, and query functions. We claim that ((++)) ,H(² 0am) satisfies the following:
5 ()) ,H! 0am)) sern {{
1 and has bit
(C.14)
otherwise
For all other coordinates l, f _1 Oamee (n To see this, we first observe that Q(1)))) ) TKo Wpos + j. Next, we observe that Q(h) )isupo produces the encoding of (<x) using binary (-1, +1} bits, and ((h(i)) produces the encoding of 111(2)) using binary {-1, +1] bits by C.9 In addition, Q(h())) hup +1:wpot/ (d") 1 if i' > and all O's otherwise, and 11p + 1i+1 2Bin 1 (1) -1. Note that by our construction, the maximum possible value of Q(h) TK(() (3)) is upps +J+ + and the next largest possible value is upps + 1. Now there are 3 cases:
K(hb)) (1)
Case 1: 1' O. In this case, we note that [((x)) never matches 1 for & É Thus, by construction
of the first Wpos coordinates of Q and K, the largest possible value of ((
K(h))))
is wpos +j-
so the attention will always only attend to the null position, so the layer adds Vo - 0 to h preserving its value. Note that (h: ())))))))))))) 3a= O in this case, which matches the desired behavior.
Case 2: 1' O, and has (j + 1) bit O. In this case, we note that for all t> Y', Q(h())) K(1,)) upss +j- 1, because by definition such must satisfy 4-1(2) * l(xx), so the first Upos coordinates contribute at most Uppos to the dot product. On the other hand, if & t must have 1j+1)-th 1h bit O, so K(h) 10pm +i+1
& Upos + 1 again. Thus, in this case, the null position is attended to again. The same reasoning as Case then applies.
-1. This doesn't match the (upps + 1)-th bit of the query, so (( (OKTKK(G K(h()))
"ppn + j+ for example, (= i' achieves this maximum by our construction. As a result, the null position is not attended to. All the values in the positions attended to satisfy ((n(")) ( = 1, which matches the (j+ 1) bit of V' Thus, (C.14) holds.
Case 3: v' >00 0 and has (j+ 1) bit 1. In this case, max,Q(h,)) k(N)"))
Finally, to complete the proof we simply append an additional feedforward ReIU layer which copies the value f(i+1))1 (n(() (n("),11, ,,I(55 ( to the output bit correspondigg to the position indexed by "J+1- This layer will also set the output bit corresponding to gat4 to 0. Note that these operations can be implemented with linear layer, and applying ReLU activation after won't 't change the output, which is in {0.1)". By (C.10).
the constructed function will thus satisfy (C.TT). It's also easy to observe that [0]] is as desired.
Proof of Claim C.6 The attention layer uses key and query functions which each compute linear transformations from R" to R2 The value function is also linear. We choose parameters such that
20
Q (1) upp 1:20r 8,5 1
(h))2mppo
and
K(h) 1:00pp
= 1:0g.
-210055 -1
K (h) Wyo 1:200
21/000
K(h) 22pm+11 +1= =0
and
v(h)*m) = =
Furthermore, we choose null keys and positions such that (Ko) the attention layer, we construct linear layer which simply zeros out coordinates indexed by sets and pre- serves all other coordinates. Note that because all outputs are either 0 or I, applying a ReLU activation won't change the result. To see that this construction computes (C.6). we observe that if i -'>00 O, Q(h.) K(hz)= 2tiposs Otherwise, if d' 0, Q(h.) T K 20p for all 1 Et i. On the other hand, it always hold
2wpos 11, and Vo= 0. To follow
and
that Q(h:) T Ko 21ppes 1. Thus, if / 0, the attention attends exactly to i", so the value function satisfies
20

---

Under review as a conference paper at ICLR 2022
(4) which would produce the output in (C. desired. On the other hand, i' = 0, the attention attends to the null position, so the attention layer sets ( (. y Thus, f( also produces the desired output in this case. It's also easy to observe that the ||0| is as desired.
The next step complete step 4) in Section 4.2 using encoder-decoder attention. The following lemma provides this construction.
Lemma C.7. the setting of Theorem 4.1 and Lemmaa C.3 consider any timestep and denote an ouiput of the function constructed in Lemma C.3 in the Jorm (C.). Let fm denote the oulputs of the encoder, in the form (C.I. There is function I with parameter O consisting of single meoder-decodee attention layer such that for all such in the form (C6). the following holds:
f(..(e)....em..0 1 (z((2(())
[h, -..,... 0))mmm (((((((z))
((.,(E1.... ),0)00 Bin(i)
f(, ((..(c1.....mm m.0) = Bin(4 (6m(4-1(z))
f [h,((e),..,,ml) 0) (in(4((x)
|AI (uv
if'z0 otherwise
(C.15)
((h((E)..,,em)..
(m)( [aa
if((x) &m
otherwise
f(h.(e)n..,,mm)) (()'=0)
f(..(e1..,,em)00) 100=11(44 1(4(z) <m)
Ar all other coordinates, f(,, (E1, em), 0) takes value Furthermore, the parameters satisfy |00| = [[|A Wpps).
Proof. We choose the encoder-decoder attention layer that the key, value, and query functions are linear transforationss. The key and query functions map IR." to lR up and compute the following:
Q 1:1 P0s
and
K(h) 1:1g0
-2hpp0s
k(h)uma+1=
The value function computes
V(h) 02 =11)) V(h) v( =1
with O's all other coordinates. The null key Kg satisfies (Ko) (oo) coordinates. The null value Vo satisfies Vi O. We set
Ulpos 1, with O's in all other
f(h.(e2.....mm...))) Attn(tt
where Attn is the decoder-encoder attention using the key, value, and query described above. Now we observe that from this construction, if In addition, we have K(e;) K(e,)1.u,, = /
the form provided (C.6). then Q(h) Bin(4())).. pux, = Bin(j) for j & m. Thus, by construction V. Ky, Vo. 4(x) & m, the attention attends to position 4(x)) in the embedding. The value function for this position satisfies (((t,o))) = 4, (m)
sym, = (1(()))()))) Thus, in this case F(h,f) computes the desired
output in (C.15). On the other hand. if (xx)) m, then the attention will attend to the null position, as Q(h) Kg Wpas - 1, and the largest possible score for all other positions is upos -2 2. In this case, C.15
holds again. It is also easy to check that the desired bound on [0]] would hold.
Finally, we implement step 5) of the outline in Section 4.2 the following lemma.
21

---

Under review as a conference paper at ICLR 2022
Lemma C.8. In the setting of Theorem 4.1 and Lemmna C.7 consider any timestep and any h outpur
by the function in Lemma C.7 taking the form in (C.15). Then there a function f with parameters consisting of constant rumber of feedforward ReLU layers satisfying the following:
f(h,0)" - (z(((()))
= [aa(((
(C.16)
- (x)
As all other coordinates. F(h, 0) takes values O. ||0| = 01|2+ upa.).
Furthermore, the parameters satisfy
Proof. It suffices construct sequence of layers which performs the following operations:
1) Compute the following vector de R
if h S074
1
v=
3eT h12
if 11 =0
1- f22
Note that u encodes the location of the symbol a;()), as (z(2)) - (p()) if > (;(x)= (x) if 00 and (xx) & m, and (,(x)) = [Ø] otherwise. The vector is one-hot vector indicating which these three cases holds.
2) We can take and compute AND with all bits of hmm, which computes
1 LA (j( (ax()) if 0, and 0 otherwise.
3) We take 22 and compute AND with all bits of h which computes || if U2 = 1, and
0 otherwise.
4) We take vi and compute AND with all bits of . ([2)), which computes 1 (a:(z)) if 03 1.
5) We add the outputs of 2), 3), and 4) together, which gives (a:))) We copy this quantity into the output coordinates indexed by .sm, Then we set coordinates not listed in (C.16) to producing the desired output.
Each of these operations be computed by constant number of feedforward ReLU layers, with total parameter norm satisfying [ [[ Wpon).
Proof of Theorem 4.
We construct neural net compute any Turing machine with all-layer margin lower bound (M and apply Lemma 2.3 to turn this into a statement about statistically meaningful
approximation.
For our Turing machine construction, we follow the outline laid out in Section 4.2
Fix any Ge 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 O. We construct a transformer F to compute G. First, we note that Lemma C.T constructs layer compute the functionality described in 1). Next, the layer in Lemma C.2 performs the functionality in 2). Likewise, Lemmas C.3 C.7 C.8 construct layers which perform 3), 4), and 5). Thus, by applying the layers constructed from these lemmas in sequence,
obtain
transformer such that the output Or contains an onehot encoding for (x)): 1|z] (x)). We can now
apply a linear weight vector 0as on the output to obtain or.,, where (0as)== for accept states 2 Z and (0ax) = - for reject states. For inputs .rE X,, by our construction this computes the desired TM(xr). Next. following Theorem 3.1 we insert correction functions (Definition DDI) between every group of constructed layers, which can be implemented via two feedforward ReLU layers following Proposition 3.4
The parameters for all correction functions add total ||-||--norm at most poly(k, (A,,k,,,A,,oog))) logT). Let F(z,0)
denote the transformer constructed this way, with parameters 0. Note that for all xe X,, ((x.0) 2G(x)) -1.
22

---

Under review as a conference paper at ICLR 2022
Next, there are several steps remaining convert F into the fixed architecture FW. w.d.T- 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 feedforward ReLU module can be converted into transformer layer by setting the two unused modules in the transformer layer to implement the identity function. This only increases the --llr-norm by (oog Note that in particular, we can perform this conversion such that the correction functions form the last feedforward ReLU layers in every transformer layer. The first 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 O, without affecting any of the ||orl 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 = O(Tlo'T)) 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 [D6] The correction function corresponds to the last 2 feedforward ReI.U layers in the transformer layer. (We observe that there are actually m layers which depend on the input z, not a single layer fo as in the setting of Theorem [.6] but this is a minor difference where the same argument of Theorem [D6 easily applics.) 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 holds for X= = poly(| (T,A logT), because all of the intermediate layers are sparse binary vectors with at most Z + [A| +ogT nonzero entries.
Finally, remains to check that Condition D.3 can hold for all of the defined layers for parameters that are polynomial in |Z| .lo''. This is straightforward to check for transformer layers where the attention layers have parameters O, 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 IE X. the largest attention score is always greater than the second largest by margin of 1. Furthermore, ties only occur when all of the value vectors for the attended positions are already the same. As result, the positions attended to by the layer will not change unless we perturb the parameters and inputs by O(poly (opply-~(((2))))) ()2), logT)) This reasoning can be used to conclude that Condition D.3 with Lipschitz constants (|
and distance parameters ((poly (log holds. As a result, the all-layer margin bound from applying Theorem D.6 will also be 2ppoly ((2,,,AA),..)) as desired. Finally, applying Lemma [.3 with y= Spoly ((Z). 1.. |.IAA), and using the fact that the parameter Il-ll-norms -orms are bounded by a 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 fo :o x O - RR" map space of inputs Ze X and parameters 0 Oo to w-dimensional space. For simplicity we assume all intermediate layers have dimension w, and let f: : R + - Roth be the i-th function in the neural net for d' i 1. We define fa to output values in R. Let 0 = (fp...,(a) O2) E O denote the full vector of parameters. The i-th hidden layer h; computes the following value, defined recursively:
ho(22,6) = (o(z.))=fu(z,66)
- = (2
The model computes output (z,00. We will assume the existence of "correction" functions ( parame- terized by { (5nv...fa-1) E E Definition D.1 (Conrection functions). Let F - R be a model defined by layer functions fo..... Sa. - R is a set of correction functions and parameters for F", 0 with radius oc if for all ie [d-1] -] X and TR. setisfying (a-hh(a, Eo.,
x- x which correct errors in the model output for inputs X::
Then So :R "
-( hx(x.))
We now define the fanction output F with correction layers recursively by g0(2,0.g)=
((l vo
(D.1)
-(0..0g)-f(hh(00000 010.0-3--faaa0000.......00.0.000 (
23

---

Under review as a conference paper at ICLR 2022
We note that for all DE x,,, F(x.B.))=ha(z.a))
The key observation is that by adding correction layers to the model, we can transform a model with possibly small all 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 f(-0)) : Dout is (H0.)1,0,.00 Oo)-ccc on H = D with respect to III if the following hold:
(1 - f(h,0)l = kollo 2maaxx( 11
A 0 <
(11,0)--(hh0)) h-
| A E 0h 0-1 op.
We will focus on the following norm tuples of inputs (x),....x), where E for all jE
(e........ max[|1y
(D.2)
We analyze the function F output by a model with correction layers satislying the following assumptions: Condition D.3. There are constants N9. such that the following hold.
For i 1, suppose that fü is (6o.)44hh.00)-iicc at 0g on (No....hi-1)(22) with respect to II--II-
In addition, suppose that fo satisfies fo(x,00 fo(2, < 00-0 for all xe 2
Furthermore, suppose that for all i, 4. satisfies (h, (1. < Kemax [h 2. Ella for all & with && - & og and R..
These conditions are all standard Lipschitzness- conditions on the individual layer functions. Our lower bound for the all-layer margin will be expressed in terms of the constants here.
We will also need to assume bound À the norms of each of the layers computed by h4- Condition D.4. The norms of the true layer values are bounded, that is, 3λ such that for all 0 0 is d and xe
(D.3)
We will also consider models with weight sharing, which allows analysis apply architectures such as the transformer in Section 4
Definition D.5 (Layer- based weight sharing). Let e'r''R'' RR' O ....,.. ".. D...RRR Re be some spaces of real-valued parameters. Suppose we wish to perform copying on parameters Of e to produce parameters θ= (1fu....d)ee θ = Og x -.. where 0, is the set of parameters given layer function fr. We say that a tuple of functions T (To....,Ta) : + is a layer-based weight sharing scheme if eacch Tę of the form
T,(0') ) = (On, ('......O'''
(D.4)
where тI Tb. is a set of distinct indices taking values in [w']. Note that this ensures that parameters not duplicated within layer.
We will now prove our main lower bound for the all all-layer margin based on inserting correction functions every layer.
Theorem D.6. In the above setting, suppose that Conditions D.3 and D.4 hold for function F in the form given by (D.I) parametrized by @ with correction layers Sou..Ka- parameterized by & with correction radius oe < 1. Suppose that F(x) E (-1,+13 VxE X. Then for all x X, we can bound the all-layer margin of F (defined in (2.1) follows::
(=((0.)).,,1(F(2266)
min!
À ac 00, 2:gg"
2ng 2ng 2xxx 4xprie 4uuss }
OC
Oh
Oc
1
(D.5)
po "m
Here the subscript F' makes it explicit that the all-layer margin is for the architecture F. Furthermore, consider any layer-based weight-sht weight-shared shared model F'x2,8") + (()), for valid weight-rying mappings n(1), 7(2) (Definition D.5). the same bound holds for p00 (0' (F'((( >
24

---

Under review as a conference paper at ICLR 2022
Our proof will first consider the case without weight sharing. We use =0 (.)....Ba) and 6= Ed denote a perturbed set parameter vectors. Furthermore, define the partially perturbed parameter sets 8, 0.e....0,,,++1..--... and & (Go.-- We also use 0_ 1 and Ç- + & when convenient.
We consider perturbations such that the following norm bounds hold:
À _
0 00012 $ minf
(D.6)
140 μo
0 0.11 a mmin
OC
(D.7)
2no 2ke
1 - Edll & min (8 2nE DAuuNie 4uung }
OC
(D.8)
We show that such perturbations won't change the label predicted by the model, and so therefore the minimum of these quantities immediately gives 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:
h ho(
[g (2. ho(2.00ll2$ min(A.oc}
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 isi d. Suppose that for all 0 j.j& < i, it holds that for all x X.
(D.9)
and
(x,00.))) h (x,(0,)) min()
In addition, suppose that 0.0 satisfy
D.7 and
D.8.
Then it follows that for all x X,
(1 (x < min(Xgce
Furthermore, for 1 additionally have
11( (x.0))
Combined, the two lemmas above allow us to inductively show that the prediction of the model not changed whenever the perturbations are bounded by (D66). (D.7), and (D8). Next, we show that this translates directly an all-layer margin lower bound.
Lemma D.9. In the setting of Theorem D.6, suppose there exist norm bounds agy...0ag bs- such
that whenever [10 0 & and [[E, - E &b, [F(x,0.))- ((),) for all xE Then we obtain the following lower bound on the all-layer margin, for all xe:
0)) >
The same lower bound applies if we consider models that use layer-hased weight sharing, defined by (x(00))== (0"), ())))) for valid weight-tying mappings (1), 7(2) (Definition D.5
We can combine these steps 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 and Lemma D.8 the inductive step to conclude that
(F(200,)) Fxx (x)0.)) oc for all Xe We now apply Lemma D.9 to obtain the desired bound on the all-layer margin.
We fill in the proofs of the supporting lemmas below.
25

---

Under review as a conference paper at ICLR 2022
Proof of Lemma D.7 By definitions and Condition D33 have
(0,0(r,0,)) (o( (3, fo(22,0))l2 & 101100-001 0o12 minn
Now we can apply the Definition D. of the correction functiin to get
= 000000 (z,2,))
Proof of Lemma
D.&
By expanding the expression for h;3 we observe that h,(x.0)) -
=
(D.10)
We obtained the equality via (D9). Now we write
-xr,0,2) f( ,).. (1
(D.11)
We subtract the two expressions and add and subtract Si (af. obtain
where
Ej 1..
- +fffcacccchhhcccEEe........1..33
Eg
We first bound Ej. We note that for all 0
1h,(x,0.3) (,, 1l12 Ic (0s (1)
Kemax 90 (1.0)))2211 -Eil2
The last inequality used Condition D.3 and E Eslle o... Now defining H' + and H a (Fa(2,00g) (z,00
/ (xr, 2)) )), it follows that
max 11 H 02
Plugging in [1g (x,00,)))) & (1)((,,)|l2++ (r, (2, 22, A A and 1 obtain H /7" oa- Furthermore, note that H (io 1) can apply Condition D.3 and Definition D.2 2 to obtain
2
on
we
E 2= [ -
< M||| HHH'I|
(since 10:-0.112 Sop and || - HI' <ow)
$ 2xuxemaxllE, - Eslla
Next, we bound Fg by applying Condition
D.3 and Definition D.2 again, using |00 10,-0,12 az:
E2l12 Il. 0,) fo (H,0)]2
< < 0 2mmx [|]11]}
kol | [h (100))))
Ke 00.00.122
where applied Condition D.4 By triangle inequality, follows that
(r.
{x(r,0)22 |
= 0, 22l2+ 1 1 Ayusemaax(/)
26

---

Under review as a conference paper at ICLR 2022
Now by the assumptions on ||0, 0:l12 and [|, E1ll. can check that the r.h.s. is bounded by min(X,arg). Finally, we note that by Definition D.1 of the correction function, we have
(,,,,,6, =
where we used the fact that 19. h, (2
then by the conditions of the lemma, ((xx,.))) <1. However, because F (-1,++))))+))+)) for xE X. the sign of the output is unchanged, which means (xx,0,)) 0. This means that we must perturb (0.E) by (1-12--none -norm least â to satisfy the constraint in the all-layer margin definition, giving the lower bound. We note that similar argument applies to layer-based weight sharing because there are no parameters shared within a layer, the perturbation H' has Eg norm less than a the parameters in (1) (())))))())))) will also have perturbation of at most ā in each layer. The same reasoning as before then applies.
Proof of Lemmal D.9 Note that if [0. (0.5) as ai
27


Reviews:
[{"review_id": "zc9EwkUwOyz", "reviewer": "Reviewer_eLwz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Regarding the notion of SM approximation, it seems a ``re-branding'' of the classical generalization theory. Specifically, as shown in the Proof of Proposition 2.2, the trick is to (i) find a surrogate loss function $\\bar \\ell$ that dominates the loss function $\\ell$ and (ii) apply the standard generalization theory to $ \\bar \\ell$. Here the surrogate loss function is a ramp loss combined with the all-layer margin. I would suggest modifying the claim and giving more credit to the classical generalization theory. \n\n2. The theoretical results and the proofs seem not sufficiently rigorous. For example, in theorem 4.1, the statement requires $d \\asymp \\log T$, it seems unclear how large the hidden constant is. In the proof, there are a lot of $O(\\cdot)$ and $\\mathrm{poly}$ notations that might hide very large constants. \n\n3. The authors treat the Turing machine as a binary classification problem and uses transformer layers to represent the Turing machine. However, such a classification perspective seems to neglect the fact that the Turing machine actually involves a sequence of input and outputs, and thus using a single binary output might be problematic. \n\n4. The all-layer margin and the margin loss in (2.2) seem hard to compute. Also, it seems intractable to find the global minimizer of the empirical risk. Thus, it is not clear how this work is relevant to practical deep learning. It would be great to have empirical results that approximately compute the global minimizer of the empirical loss. \n\n5. In terms of the contribution, it seems that the major contribution of this work is to represent the Turing machine using neural networks, compute its all-layer margin, and apply the standard generalization theory. Maybe it is better to downplay the first point in the summary of contributions in introduction:\n> our contributions are: 1) we propose a new notion of statistically meaningful approximation,\nintended to provide more meaningful approximation guarantees by requiring that the approximating family\nhave good statistical learnability;\n\n6. Related works:\n\n   a. Nonparametric regression using deep neural networks with ReLU activation function\n\n   b. Sparse-Input Neural Networks for High-dimensional Nonparametric Regression and Classification\n\n   c. Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks\n\n   d. Generalization error bounds of gradient descent for learning over-parameterized deep ReLU networks\n", "summary_of_the_paper": "This paper studies the approximation of boolean circuits and Turing machines using neural networks. To this end, the authors propose a new notion of approximation criteria -- statistically meaningful (SM) approximation -- that specifies that the function class is both learnable and has a small bias in the sense of classical approximation theory. For both the boolean circuits and Turing machines, the authors explicitly construct two classes of neural networks, based on feedforward network and transformers respectively, that achieve SM approximation. ", "summary_of_the_review": "This work seems to only establish a generalization theory for using neural networks to learn boolean functions and Turing machines. The main contribution is showing that proper neural network structures can represent the target functions and the networks have large margins However, the estimator (and even the surrogate loss function) are not easy to compute, which limits the practicality of this work. In addition, treating Turing machine as a classifier seems restrictive. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "leds70P-tTi", "reviewer": "Reviewer_VpYu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There are already many proofs that functions and programs can be represented by various classes of neural networks (\"universality theorems\", notably classical work by Cybenko/Barron which approximate arbitrary functions by depth 2 non-linear networks and recent work by Eldan-Shamir/Telgarsky showing the trade-offs between depth and width). This paper argues that some existing results rely in infinite precision and are thus undesirable. (It seems to me the latter objection only holds for specific universality theorems). The proposed criterion gets around this by saying that the representation should come with a loss function whose empirical minimizer captures the function of interest. This is simple, intuitive and perhaps obvious so far. Is it useful? I am not sure.\n\nSo, to demonstrate its value, they show that Boolean circuits can be represented \"statistically meaningfully\", i.e., they provide a loss function and a proof that an empirical minimum on a finite sample must give an honest representation. What this comes down to is showing that the representation parametrization can be done with a large margin, and the loss function focus on finding a large margin, so that empritical minima must find valid solutions. I was able to follow the construction for Boolean circuits (note, these are layered Boolean circuits, this should be mentioned up front) by relying on ReLUs and a simple trick to lift into higher-dimensional non-linear features and create a significant margin even if one doesn't exist in the first place. The particular loss function proposed is apparently a variant of a recent proposal (but was new to me).\n\nI could not follow the second application (transformers can represent Turing machines). Unfortunately, while I understand the latter is a hot topic, at the least the authors should define the class of functions they are dealing with, explain their representation power and advantages before going to their statistically meaningful construction.", "summary_of_the_paper": "This paper proposes a new criterion for learnable representations of Boolean circuits and Turing machines. The criterion \"statistically meaningful\" is the main contribution along with its application to the above two classes. ", "summary_of_the_review": "Presumably the value of this paper is conceptual; I don't see any benefits to ML algorithms (e.g., the loss function proposed is not robust, i.e., some errors in the data labels will cause it fail). While the definition is simple and natural, I am afraid I don't see the conceptual advantages. There are already existing, more powerful definitions that provide some insight into computation, e.g., Statistical-Query Learnable, where every query is answered empirically up to some tolerance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "l_9xRCSmT-o", "reviewer": "Reviewer_Lqbr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n\n1. The concept of SM approximation unifies approximation and generalization, which is novel and maybe interesting. \n\n2. The paper actually shows that when optimizing the all-layer margin loss, both fully connected nets and transformers would \"prefer\" to learn some simple function class using a relatively small number of samples. This is interesting because we may expect different surrogate losses for different network structures.  \n\n\nBelow are my concerns:\n\n- If we already know that $\\mathcal{F}$ can exactly represent $\\mathcal{G}$, then we can choose the surrogate loss $\\bar{l}$ such that it outputs infinite loss when $F \\notin \\mathcal{G}$. In this sense, optimizing the surrogate loss would be just doing empirical risk minimization within $\\mathcal{G}$. Using this somewhat cheating trick, showing SM approximation reduces to (1). show that $\\mathcal{F}$ can exactly represent $\\mathcal{G}$, and (2). provide a generalization bound for $\\mathcal{G}$. Therefore, to some extent, the nice sample complexity results in the paper are not that surprising.\n\n- minor point: It would be good if the surrogate loss (all-layer-margin loss as proposed in the paper) is actually computationally tractable. In other words, a good future direction would be to try to show GD/SGD intrinsically optimize this loss.", "summary_of_the_paper": "The paper proposes a novel concept called statistically meaningful approximation. Roughly speaking, SM approximation means that performing empirical risk minimization over some properly chosen surrogate loss would result in a hypothesis with small population risk. Then the paper develops necessary tools and proves two results: (1). fully-connected neural networks can SM approximate boolean circuits with a sample size that is poly in the number of gates and $\\log$ in the width and depth of the circuit; (2). transformers can SM approximate Turing machines with a sample size that is poly in the number of states, alphabet size, and the log of the computation steps.", "summary_of_the_review": "The theory of the paper is novel and interesting. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Qs4t7gAtEEl", "reviewer": "Reviewer_RNAM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presentation is clear and the proofs seem adequately proven.  \nBut the novelty and importance of the new definition is not adequately demonstrated for this reviewer.\nStatistical learning theory is a vast field and the ingredients of the definition are not new.\nThe two examples are improvements on previous work which, it appears, \ncould have been applied with previous phrasings of generalization and approximation accuracy.\nAlso the definition is only constructive on the existence side (F SM-approximates G if \"there exists a loss ...\")\nand not on the non-existence side.  It would be reassuring to see the proof of a negative example.\nI think much more discussion is required as well as much more review of previous related work for this to become more than just another definition added to a long list.", "summary_of_the_paper": "This paper proposes a definition of \"statistically meaningful approximation\" or SM-approximation which combines learnability, generalization ability and expressivity (approximation accuracy) in a straightforward way.  Two theorems on SM-approximation are formulated and proven, one for approximating Boolean circuits and one for approximating a general Turing machine computation with a transformer network.  It is argued that the new definition has technical advantages.", "summary_of_the_review": "Interesting proposal but not given enough motivation or set in enough context to be convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an extremely interesting and timely paper regarding the approximation ability, with statistical consequences, of circuits and (computation-bounded) Turing machines by feedforward networks and transformers. The paper has an interesting and valuable setting, and also many unusual ideas, together which can inspire a lot of future work.  Unfortunately, the reviewers had significant difficulties with the presentation and setting; the Transformer material in particular lacks clarity.  As such, the paper could use more time and polish.

Separately, I will recommend in the future that authors consider making use of the rebuttal and revision phase.  While it is not strictly required, it seems that in ICLR, scores shift quite a lot in those phase, and it has (for better or worse) become standard to have a thorough involvement in this phase.  It was difficult to cause score changes after the initial phase due to the lack of review responses.  That said, I sincerely hope the authors continue with this valuable line of work.
Decision: Reject