# Sub-Task Decomposition Enables Learning
in Sequence to Sequence Tasks

Noam Wies, Yoav Levine & Amnon Shashua
The Hebrew University of Jerusalem
<EMAIL_ADDRESS>

###### Abstract

The field of Natural Language Processing (NLP) has experienced a dramatic leap
in capabilities with the recent introduction of huge Language Models (LMs).
Despite this success, natural language problems that involve several
compounded steps are still practically unlearnable, even by the largest LMs.
This complies with experimental failures for end-to-end learning of composite
problems that were demonstrated in a variety of domains. An effective
mitigation is to introduce intermediate supervision for solving sub-tasks of
the compounded problem. Recently, several works have demonstrated high gains
by taking a straightforward approach for incorporating intermediate
supervision in compounded natural language problems: the sequence-to-sequence
LM is fed with an augmented input, in which the decomposed tasks’ labels are
simply concatenated to the original input (see figure 1). In this paper, we
prove a positive learning result that motivates these recent efforts. We show
that when concatenating intermediate supervision to the input and training a
sequence-to-sequence model on this modified input, unlearnable composite
problems can become learnable. We show that this is true for any family of
tasks which on the one hand, are unlearnable, and on the other hand, can be
decomposed into a polynomial number of simple sub-tasks, each of which depends
only on $O(1)$ previous sub-task results. Beyond motivating contemporary
empirical efforts for incorporating intermediate supervision in sequence-to-
sequence language models, our positive theoretical result is the first of its
kind in the landscape of results on the benefits of intermediate supervision
for neural-network learning: Until now, all theoretical results on the subject
are negative, _i.e._ , show cases where learning is impossible without
intermediate supervision, while our result is positive, showing that learning
is facilitated in the presence of intermediate supervision.

##  1 Introduction

Large-scale language models such as BERT (Devlin et al., 2019), T5 (Raffel et
al., 2020), and GPT-3 (Brown et al., 2020) have recently pushed the envelope
in many NLP tasks. Nevertheless, there are some problem-families that even the
largest models do not seem to be capable of solving. One such family is that
of “multi-hop" reasoning problems (see, e.g., Geva et al. (2021); Kalyan et
al. (2021); Press et al. (2022)) that require compounding operations in order
to produce an answer. For example, Gopher (Rae et al., 2021), one of the
largest available language models, achieves $61\%$ accuracy in the StrategyQA
benchmark (Geva et al., 2021) that requires implicit decomposition into
reasoning steps, while human level performance is around $87\%$ accuracy.

The limitations of learning compounded tasks with neural networks in an end-
to-end manner have been observed in a variety of non-linguistic domains. A
leading experimental approach for addressing these is to first explicitly
break the compounded operations into more basic “single-hop” operations and
then combine the results. Gülçehre & Bengio (2016), one of the earliest works
on this subject, propose that supervision for the single-hop intermediate
steps is crucial for avoiding bad local minima in the optimization of neural
networks. Afterward, Glasmachers (2017) demonstrated that gradient-based end-
to-end multi-hop learning is inefficient for solving complex problems that are
easily solved by a divide-and-conquer strategy. Beyond position papers,
specific examples were shown, e.g., Chang et al. (2020) showed that SATNet
(Wang et al., 2019) could not solve visual Sudoku without using intermediate
labels to identify individual Sudoku digit images.

Similar limitations were observed in language related compounded tasks,
including commonsense reasoning (Liu et al., 2022; Wei et al., 2022; Zelikman
et al., 2022), math word problems (Piękos et al., 2021; Wei et al., 2022), and
programs execution (Nye et al., 2022). The go-to architectures in this domain
are powerful language models, which are trained as sequence-to-sequence models
over text. In this setting, a particular form of introducing intermediate
supervision for compounded tasks has emerged: intermediate sub-tasks and their
labels are concatenated to the original task’s input to form a new input
sequence, on which the sequence-to-sequence LM is trained. This approach has
recently been widely adopted, _e.g._ , by Rajani et al. (2019); Cobbe et al.
(2021); Piękos et al. (2021); Recchia (2021); Nye et al. (2022); Wei et al.
(2022); Zelikman et al. (2022). Figure 1 illustrates this approach for math
problems, as done in Ling et al. (2017); Cobbe et al. (2021). These works show
that training sequence-to-sequence models with concatenated sub-task
decomposition supervision significantly improves the results when compared to
training the same model without the intermediate supervision. For example, Nye
et al. (2022) show $>99\%$ accuracy for $8$ digits addition when concatenating
intermediate calculations to the input, while the vanilla accuracy without
intermediate supervision is around $\sim 35\%$.

Figure 1:  An illustrative example of the prominent method for introducing
sub-task decomposition and intermediate supervision for math word problems
(Ling et al., 2017; Cobbe et al., 2021). Intermediate sub-tasks and their
labels are concatenated to the original task’s input to form a new input
sequence. At training time, the likelihood of the entire sequence following
the original input is maximized conditioned on the input, and at test time
only the original input is given to the model.

While such decomposition based approaches are intuitive, we are not aware of
theoretical results that motivate and formulate their benefits for learning
composite problems with neural-networks. In this paper, we provide positive
theoretical results in this domain, which are in fact the first of their kind
(see related work in section 2). We show our results for sequential models,
integrating the intermediate supervision in a manner that mimics the above
cited successful empirical approaches in the language domain. In this
formulation, a learner learns to predict a sequence composed of the task
inputs ${\mathbf{x}}$, followed by the single-hop reasoning steps referred to
as the _evidence_ , and finally, the final answer $y$. We extend provable
guarantees for the convergence of overparameterized recurrent neural networks
(Wang et al., 2021) and prove that with intermediate sub-task supervision,
even a simple sequence-to-sequence model provably learns any task that obeys
an efficient decomposition into simpler subtasks that depend only on a small
fraction of the input. Importantly, both the sample complexity and the
required number of gradient updates are polynomial. In contrast, we rely on
existing works (Valiant, 1984; Goldreich et al., 1986; Daniely & Shalev-
Shwartz, 2016) to show that in the absence of intermediate supervision, there
exist efficiently decomposable tasks that are unlearnable with polynomial time
learning algorithms.

Our results apply to a broad family of tasks. As a first exemplifying step, we
show a positive result for learning bit subset parity, a setting that is
notoriously not amenable to gradient-based algorithms in an efficient way
without intermediate supervision (Kearns, 1998; Shalev-Shwartz et al., 2017;
Abbe & Sandon, 2020; Abbe et al., 2021). In this setting, the family of target
functions consists of parities over subsets of unknown input bits.
Specifically, the input is $d$ bits and the task is to predict whether the
number of $1$’s in certain unknown subset of $\nicefrac{{d}}{{2}}$ bits is odd
or even. The corresponding sub-tasks we consider are the parities of subsets
of the unknown input subset. We prove a theorem guaranteeing that, when
intermediate supervision is available, efficient neural network learning is
made possible. As a result, we show an exponential gap between the end-to-end
and decomposition-based neural network learnability of the bit subset parity
problem.

Next, we generalize the above result, and show that when sufficient
intermediate supervision is available, any family of functions with a
polynomial time complexity, _i.e._ , functions that belong to the
${\mathbf{P}}$ time complexity class, are efficiently learnable by neural
networks. Accordingly, based on either standard cryptographic assumptions
(Valiant, 1984; Goldreich et al., 1986) or computational complexity hardness
assumptions (Daniely & Shalev-Shwartz, 2016) we prove that there exist tasks
that, on the one hand, cannot be learned by any polynomial time algorithm and,
on the other hand, can be efficiently learned by neural networks when
intermediate supervision is present.

Our main result can be stated as follows:

######  Theorem 1.

(Informal) There exists a binary classification problem parameterized by size
$d$, such that the following holds:

  * •

On one hand, when equipped with sub-task decomposition supervision, a simple
sequence-to-sequence model can get arbitrarily low $\epsilon>0$ zero-one loss
with number of gradient updates that is polynomial in $d,\epsilon^{-1}$.

  * •

On the other hand, when supervision regarding sub-task is missing, then for
any polynomial time learning algorithm and (constant) $\epsilon>0$, the zero-
one loss will be higher than $\nicefrac{{1}}{{2}}-\epsilon$.

To summarize, the main contributions of this paper are:

  1. 1.

We show the first positive result that guarantees neural networks learnability
in the presence of intermediate supervision for a problem that is unlearnable
without it.

  2. 2.

We do so in the sequence-to-sequence setting that is currently used for
applying state-of-the-art language models on complex multi-hop tasks in NLP.

  3. 3.

We show that with sufficient intermediate supervision this sequence-to-
sequence setting allows learning any function in the ${\mathbf{P}}$ time
complexity class.

The remainder of this paper is organized as follows. Section 3 presents the
sequence to sequence model we analyzed. Section 4 presents a hypothesis class
and proves that it can be learned with our sequence to sequence model. Section
5 presents a concrete example, and demonstrates that the task of learning bit-
subset parity with sequence-to-sequence models can be learned with sub-task
decomposition and the corresponding intermediate supervision. Finally, in
section 6 we generalize the positive results to any function in the
${\mathbf{P}}$ time complexity class, thus establishing our main result.

##  2 Related Work

The concept of how learning can be enhanced by guiding a learner through
intermediate tasks is an old one, dating back to animal training by shaping
(Skinner, 1958; Peterson, 2004; Krueger & Dayan, 2009). Since then, a large
body of work has shown its practical benefits for various machine learning
tasks. For example, there exists a rich line of work on the importance of
shaping rewards and adding sub-goals in reinforcement learning tasks. Karlsson
(1994) introduced the methodology of using knowledge in the reward function,
in order to decompose a holistic task into several sub-tasks. Ng et al. (1999)
established necessary and sufficient conditions for reward shaping to reserved
optimal policies. Marthi (2007) investigate the problem of automatically
learning a decomposition of the reward function. All these work intuitively
rely on benefits of adding intermediate supervision. Recently, Zhai et al.
(2022) showed that adding sub-goal rewards provably reduces the complexity of
the synchronous value iteration algorithm. However, this reduction is linear
in the number of the sub-goals, unlike our work that proves exponential gap in
the supervised learning setting. Moreover, several of the notions in their
analysis are unique to the reinforcement leaning setup and cannot be easily
translated into the supervised learning setting (_e.g._ , One-Way Intermediate
States).

Negative theoretical results exist, showing that end-to-end learning of multi-
hop problems is unfeasible without decomposition. Shalev-Shwartz et al. (2017)
explored the theoretical limitations of end-to-end gradients based learning,
studying learnability of tasks that are composed of classification and parity
tasks, proving that the end-to-end approach does not converge in a polynomial
number of gradient updates. They do show that when intermediate supervision is
provided, the gradients have a much higher signal-to-noise ratio. However,
they provide no guarantees that in this case learning is possible in a
polynomial number of gradient updates. In addition, Shalev-Shwartz & Shashua
(2016) proved an exponential gap between end-to-end-based verification sample
complexity and the decomposition-based verification sample complexity.
However, again, an explicit setting in which providing intermediate
supervision for training actually improves the situation to a point that
learning is feasible, is lacking. We provide the first theoretical result
proving that neural networks also benefit from sub-task decomposition, while
earlier theoretical works in this space only prove that end-to-end learning is
unfeasible in some compounded cases.

##  3 The analyzed sequence-to-sequence learning algorithm

A recent successful empirical approach for solving compounded natural language
problems (Ling et al., 2017; Rajani et al., 2019; Piękos et al., 2021;
Recchia, 2021; Cobbe et al., 2021; Nye et al., 2022; Wei et al., 2022;
Zelikman et al., 2022) is to concatenate intermediate supervision labels to
the input. This way, the language model receives a sequence composed of the
input followed by the labels of the intermediate tasks, before emitting the
final compounded answer. For a compounded binary classification task which
consists of a $d$-bit input string ${\mathbf{x}}$, with $\mathcal{S}$ denoting
the string of intermediate step results, we denote the combined input sequence
as ${\mathbf{z}}=\textrm{Concat}\\{{\mathbf{x}};\mathcal{S}\\}$, and the
combined output sequence as ${\mathbf{y}}$, defined in a standard
autoregressive fashion by111For clarity, we wrote $y_{t}=z_{t+1}$ although the
inputs domain in our model was $\left\\{0,1\right\\}$ while the output domain
was $\left\\{-1,1\right\\}$ and hence
$y_{t}=2\cdot\left(z_{t+1}-\nicefrac{{1}}{{2}}\right)$ $y_{t}=z_{t+1}$ (see
figure 2 for a $d=8$ example). Training and testing follow conventional
sequence-to-sequence model protocol: At training time, $z_{t}$ for $t>d$ will
be the ground-truth sub-task result $y_{t-1}$ (a practice sometimes referred
to as “teacher forcing" (Williams & Zipser, 1989)), and at test time, $z_{t}$
for $t>d$ will be the model’s prediction at time $t-1$.

We analyze the classical Elman recurrent neural networks (Elman, 1990) with
ReLU activations as our sequence-to-sequence model. Given an input sequence
${\mathbf{z}}$ of length $T=d+\textrm{len}\left(\mathcal{S}\right)$ as defined
above, the architecture $f^{\text{RNN}}$ computes:

$\displaystyle\forall t\in\left[T\right]\quad
h_{t}\left({\mathbf{z}}\right)=\text{ReLU}\left(Wh_{t-1}+A{\mathbf{e}}_{z_{t}}\right)$
(1) $\displaystyle\forall t\in\left[T\right]\quad
f^{\text{RNN}}_{t}\left({\mathbf{z}}\right)=B^{T}h_{t}\left({\mathbf{z}}\right)$
(2) $\displaystyle
h_{0}\left({\mathbf{z}}\right)=\text{ReLU}\left(M_{0}\right)$ (3)

where ${\mathbf{e}}_{0},{\mathbf{e}}_{1}\in\mathbb{R}^{2}$ are one-hot
vectors, $A\in\mathbb{R}^{m\times 2}$ translates the input to the hidden
dimension $m$, $W\in\mathbb{R}^{m\times m}$ is the learned hidden weights
matrix, $B\in\mathbb{R}^{m}$ is the output weights vector and
$M_{0}\in\mathbb{R}^{m}$ is the initialization of the hidden state.

We will use the binary cross-entropy loss over output locations for $t\geq d$,
_i.e._ , our loss ignores the architecture’s prediction of ${\mathbf{x}}$ and
depends on its prediction of intermediate labels and final outcome:

$\displaystyle
l\left({\mathbf{y}},{\mathbf{s}}\right)=\left(\frac{1}{T-d}\right)\sum_{t=d}^{T}\log\left(1+e^{-y_{t}\cdot
s_{t}}\right)$ (4)

Algorithm 1 below describes the analyzed training procedure of our sequence-
to-sequence model. This algorithm describes a straightforward SGD training
procedure where, for simplicity, we analyze a variant that updates only the
hidden $W$ weights while keeping $A,B,M_{0}$ frozen at initialization. This
amounts to keeping the input, output and the $t=0$ hidden state untrained, and
training only the core recurrence operation to perform the task while
complying with these frozen components.

Data: Data set $\mathcal{D}$, learning rate $\eta$.

Initialization: The entries of $W^{\left(0\right)},A,M_{0}$ are i.i.d.
generated from $N(0,\frac{2}{m})$. The entries of $B$ are i.i.d. generated
from $N(0,\frac{1}{m})$.

for  _$i=1,2,3...n$_ do

Randomly sample $({\mathbf{x}}_{i},{\mathbf{y}}_{i})$ from the data set
$\mathcal{D}$.

$W^{\left(i\right)}=W^{\left(i-1\right)}-\eta\nabla_{W^{\left(i-1\right)}}\ell({\mathbf{y}}_{i}\,,\,f^{\text{RNN},W^{\left(i-1\right)}}({\mathbf{z}}_{i}))$.

end for

Algorithm 1 Training $f^{\text{RNN}}$ with SGD

##  4 Compounded Sequence to Sequence Learnability

In this section, we present a hypothesis class and prove for it that the above
described “teacher forcing" (Williams & Zipser, 1989) of intermediate
supervision at training time with algorithm 1 provably leads to generalization
in polynomial sample complexity and gradient updates. This guarantee will
allow us to prove our positive results in the following sections, as we will
show that interesting function families belong to this hypothesis class.

In order to analyze the teacher forcing technique, we begin with an important
observation. Essentially, we show that when the zero-one loss of all the
single-hop sub-tasks is low, then it implies that also at test time, when the
model does not have the ground truth results of the previous sub-tasks and the
errors might accumulate, the zero-one loss on the final answer is still low:

######  Lemma 1.

Denote by $z_{t}^{\text{train}}\coloneqq y_{t-1}$ the ground truth input at
training time, and by $z_{t}^{\text{test}}\coloneqq
f_{t-1}^{\text{RNN},W}\left({\mathbf{z}}^{\text{test}}\right)$ the iteratively
predicted input at test time. Then, for any $W$ the following holds:

$\mathbb{E}_{{\mathbf{x}}}\left[l_{0-1}\left(y,f_{T}^{\text{RNN},W}\left({\mathbf{z}}^{\text{test}}\right)\right)\right]\leq\mathbb{E}_{{\mathbf{x}}}\left[\sum_{t=d}^{T}l_{0-1}\left(y_{t},f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\right)\right]$
(5)

###### Proof.

Clearly, for any ${\mathbf{x}}$ when
$f^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)$ solves all of the
sub-tasks correctly we have that
${\mathbf{z}}^{\text{test}}={\mathbf{z}}^{\text{train}}$ and therefore they
have the same zero zero-one loss. So it is enough to upper bound the
probability that $f^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)$ is
erroneous in any sub-task. Now by definition, for any $t$ the zero-one loss at
the $t$’th location is equal to the probability of wrong prediction at this
location. Therefore, by the union bound, we get that the sum of the zero-one
loss over all the locations is upper bounding the probability of
$f^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)$ make an error in
any sub-task. See full details in section A at the appendix. ∎

As expected, due to a union bound, when the model does not have the ground
truth results of the previous sub-task the error can increase by a factor of
$T-d$ but this increase is relatively modest as long as $T$ is polynomial in
$d$.

Lemma 1 above assures us that it is enough to find an hypothesis class for
which algorithm 1 converges and generalizes when we do have the ground truth
results of the previous sub-tasks, in order to prove that the teacher forcing
technique works. As a candidate for such a hypothesis class, we consider tasks
for which the output at each location $d\leq t\leq T$ can be written as sign
of composition of linear functions (represented by ${\mathbf{w}}$ below) of at
most $N<T$ input locations $j_{1},\dots,j_{N}\leq t$, with polynomials
activations
$\psi_{t}\left(x\right)=\sum_{i=0}^{\deg\left(\psi_{t}\right)}a_{t,i}x^{i}$:

$\displaystyle\forall d\leq t\leq T\quad
h_{t}\left({\mathbf{z}}\right)=\text{sign}\left(\psi_{t}\left(\left\langle\frac{{\mathbf{w}}^{\left(t\right)}}{\left\|{\mathbf{w}}^{\left(t\right)}\right\|},\left(\begin{array}[]{c}{\mathbf{e}}_{z_{j_{1}}}\\\
\vdots\\\
{\mathbf{e}}_{z_{j_{N}}}\end{array}\right)\right\rangle\right)\right)$ (9)

In order to prove convergence and generalization results, we will measure the
complexity of functions in the above hypothesis class by a function
$\phi\left(T,\psi,N\right)$, described formally in appendix A. Importantly,
$\phi\left(T,\psi,N\right)$ is polynomial in both $T$ and
$\max_{t,i}\left|a_{t,i}\right|$, while exponential in both
$\max_{t}\deg\left(\psi_{t}\right)$ and $N$. We will denote by
$\mathcal{H}_{\phi\left(T,\psi,N\right)}$ the hypothesis class described in eq
9.

Now, with this hypothesis class, we can combine lemma 1 with theorem 2 in Wang
et al. (2021). They study the learnability of RNNs for binary classification
tasks222They also discussed the case where $y$ is a sequence, however, in
their case it was considered part of the task, unlike our case where we add
intermediate steps as a method of supervision. without intermediate
supervision, and prove that algorithm 1 is capable of learning function where
the final answer $y$ have low complexity $\phi\left(T,\psi,N\right)$.

######  Theorem 2.

Denote by $z_{t}^{\text{test}}\coloneqq
f_{t-1}^{\text{RNN},W}\left({\mathbf{z}}^{\text{test}}\right)$ the iteratively
predicted input at test time, and let $\epsilon,\delta>0$. Assume we run
Algorithm 1 for
$n>\tilde{O}\left(\left(\frac{\phi\left(T,\psi,N\right)+\log\left(\frac{1}{\delta}\right)}{\epsilon}\right)^{2}\right)$
iterations with learning rate $\eta=\frac{1}{m\sqrt{n}}$, then there exists
$m^{\star}=\text{poly}\left(n,\delta^{-1},T\right)$ such that if $m>m^{\star}$
then for any $h\in\mathcal{H}_{\phi\left(T,\psi,N\right)}$ with probability at
least $1-\delta$ over the randomness in Algorithm 1, the following holds:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{{\mathbf{x}}}\left[l_{0-1}\left(y,f_{T}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}^{test}\right)\right)\right]<\epsilon$
(10)

where $W^{\left(i\right)}$ denotes the output of Algorithm 1 at the $i$’th
iteration and $l_{0-1}$ is the zero-one loss.

Note that sections C,D of the appendix extends theorem 2 for both SGD and GD
with finite precision.

In the next sections, we will prove our positive results by showing the
intermediate single-hop sub-tasks of the analyzed tasks belong to
$\mathcal{H}_{\phi\left(T,\psi,N\right)}$ with low complexity
${\phi\left(T,\psi,N\right)}$.

##  5 Learning Bit-Subset Parity With Sequence to Sequence Models

As a concrete demonstration, in this section we show that unlike the end-to-
end case, bit-subset parity can be learned with neural networks when
intermediate supervision is provided. We begin by defining the challenging
task of learning parities over unknown subsets of input bits. Specifically,
for a $d$-bit string with a subset of $\nicefrac{{d}}{{2}}$ randomly
predefined unique indices $i_{1},\dots,i_{\nicefrac{{d}}{{2}}}$, our goal is
to train a predictor mapping ${\mathbf{x}}\in\left\\{0,1\right\\}^{d}$ to
$y=\left(-1\right)^{\sum_{j=1}^{\nicefrac{{d}}{{2}}}x_{i_{j}}}$ where
${\mathbf{x}}$ is uniformly distributed. In words, $y$ indicates whether the
number of $1$’s in the given subset of coordinates of ${\mathbf{x}}$ is odd or
even.

We analyze this task as a “multi-hop" task by decomposing it into natural
intermediate sub-tasks: parities of subsets of the predefined input subset
$x_{i_{1}},...,x_{i_{\nicefrac{{d}}{{2}}}}$. Concretely, assuming for
simplicity that $\nicefrac{{d}}{{2}}$ is a power of $2$, and beginning with
only two adjacently indexed input bits at a time, we recursively treat the
parity of every two adjacently indexed subgroups as an intermediate task.
Figure 2(a) illustrates this binary tree sub-task decomposition of our parity
problem. The leaves of the tree of intermediate labels $\mathcal{T}$ are
${-1}^{x_{i_{1}}+x_{i_{2}}},\dots,{-1}^{x_{i_{\nicefrac{{d}}{{2}}-1}}+x_{i_{\nicefrac{{d}}{{2}}}}}$
and each node in the tree represents the sub-task of calculating the parity
function over its descendants.

In order to fit into the sequence-to-sequence setting of section 3, we
translate our imaginary tree of intermediate labels $\mathcal{T}$ into a
sequence of intermediate labels $\mathcal{S}$ by inverse-BFS like tree
traversal, and then concatenate the sequence $\mathcal{S}$ after the input
${\mathbf{x}}$. An exact formulation of the mapping from tree $\mathcal{T}$ to
sequence of intermediate labels $\mathcal{S}$ is given in appendix B.

Figure 2:  Illustration of the proposed input and output for learning the
$d=8$ bit-subset parity problem with sequence-to-sequence models.

###  5.1 Learnability of Bit-Subset Parity With and Without Intermediate
Supervision

In this section we show that the sub-tasks of learning bit-subset parity are
simple enough to be covered by the result in theorem 2, _i.e._ , we prove that
our sequence-to-sequence formulation of the bit-subset parity target function,
which includes the intermediate labels sequence $\mathcal{S}$ defined above,
can be written as a multivariate function where each of its outputs is a
simple low degree polynomial of at most $O\left(1\right)$ inputs bits. We show
that this is indeed the case, _i.e._ , that all the parity target functions
comprising the intermediate supervision to our problem belong to
$\mathcal{H}_{\phi\left(T,\psi,N\right)}$ (see section 4) with $N$,
$\max_{t}\deg\left(\psi_{t}\right),\,\max_{t,i}\left|a_{t,i}\right|$ that do
not grow with $d$. Importantly, when defining the input sequence to be only
the original input, without the concatenated sub-task decomposition labels,
then the function $h_{T}\left({\mathbf{x}}\right)$ clearly depends on
$\nicefrac{{d}}{{2}}$ bits, and therefore will require
$N=\nicefrac{{d}}{{2}}$, that leads to exponential complexity
$\phi\left(T,\psi,N\right)=\Omega\left(e^{d}\right)$. Thus, no efficient
learning is guaranteed for the original compounded task.

We begin by showing that our single-hop tasks of parities over two bits (see
illustration in figure 2(a)) are simple degree-$2$ polynomials:

######  Lemma 2.

There exists degree two polynomial
$\psi\left(x\right)=a_{2}x^{2}+a_{1}x+a_{0}$ with bounded coefficients
$\forall i\quad\left|a_{i}\right|<10$ as well as
${\mathbf{w}}\in\mathbb{R}^{4}$ such that:

$\forall
z_{1},z_{2}\in\left\\{0,1\right\\}\quad\psi\left(\left\langle\frac{{\mathbf{w}}}{\left\|{\mathbf{w}}\right\|},\left(\begin{array}[]{c}{\mathbf{e}}_{z_{1}}\\\
{\mathbf{e}}_{z_{2}}\end{array}\right)\right\rangle\right)=\begin{cases}1&z_{1}=z_{2}\\\
-1&z_{1}\neq z_{2}\end{cases}$ (11)

###### Proof.

We will use ${\mathbf{w}}$ to sum the first coordinates of
${\mathbf{e}}_{z_{1}},{\mathbf{e}}_{z_{2}}$, and use polynomial interpolation
to find a degree two polynomial $\psi$ that interpolates the
$z_{1}=z_{2}=0\,,\,z_{1}\neq z_{2}\,,\,z_{1}=z_{2}=1$ points, see full details
in appendix B. ∎

The above lemma implies that all of the target functions in our defined
intermediate supervision belong to $\mathcal{H}_{\phi\left(T,\psi,N\right)}$
for $\phi\left(T,\psi,N\right)=O\left(d\right)$. Therefore, together with
theorem 2, it assures us that when intermediate supervision is available,
Algorithm 1 can learn bit-subset parities with polynomial network size, sample
complexity and number of gradient updates.

Now, after we showed that when incorporating intermediate supervision bit-
subset parities can be learned by a neural network, we will use the results of
Shalev-Shwartz et al. (2017) to establish an exponential gap between the end-
to-end and decomposition-based neural network learnability333Note that the
negative result holds only for full gradient descent and does not hold for
stochastic gradient descent, for which Abbe & Sandon (2020); Abbe et al.
(2021) show that parities are efficiently learnable when using complex non-
random initialization.:

######  Corollary 1.

When learning bit-subset parities using neural networks, the following holds:

  * •

On one hand, when equipped with sub-task decomposition supervision, a simple
sequence-to-sequence model can get arbitrarily low $\epsilon>0$ zero-one loss
with number of gradient updates that is polynomial in $d,\epsilon^{-1}$.

  * •

On the other hand, when supervision regarding sub-task is missing, then for
any (constant) $\epsilon>0$ with high probability over the target parity, the
zero-one loss will be higher than $\nicefrac{{1}}{{2}}-\epsilon$ unless the
number of gradient updates is exponential in $d$.

###### Proof.

Follows directly by combining theorem 2 and lemma 2 with the the negative
results in Shalev-Shwartz et al. (2017). See full details in section F at the
appendix. ∎

###  5.2 Bit-Subset Parity Experiments

In section 5.1 we proved an exponential gap when using Elman RNNs (Elman,
1990) to learn bit-subset parity with and without sub-task decomposition. This
section empirically demonstrates that the same gap exists with the commonly
used Transformer (Vaswani et al., 2017) architecture. We trained a series of
models while varying the input sizes from $8$ bits to $256$ bits. For each
input size, we trained a BERT-base sized Transformer model for $100k$
iterations444With the exception of the $16$ and $18$ bits tasks without
intermediate supervision, for which we increase the number of iterations to
$300$K and $2$M respectably in order to try and successfully learn the task.
with and without intermediate supervision. The intermediate supervision was
introduced exactly as described in the previous subsection, see Figure 2 for
an illustration. See full technical details of the training apparatus in
appendix G.

Figure 3 clearly shows that in a practical setting, using common Transformer
networks, a very large gap quickly opens between the settings with and without
intermediate supervision. The employed BERT base sized Transformer
architecture is a strong network that pushed the envelope on very challenging
NLP tasks, and is much stronger than the theoretically analyzed RNN. Still,
learning even the 32 bit subset parity task without supervision proved to be
too challenging even for this network (no learning after over $2$M steps),
while it easily learned the task in the presence of intermediate supervision.
Overall this experiment, performed on the same task on which we prove our
theoretical results, reinforces their relevance to common Transformer
architectures.

##  6 Universality of Decomposition Based Sequence-To-Sequence Learning

In this section, we prove our main result (outlined in the introductory
theorem 1). On the one hand, we generalize the positive results of section 5.1
by showing that when sufficient intermediate supervision is available, a
neural network can efficiently learn any function in the ${\mathbf{P}}$ time
complexity class. On the other hand, we rely on existing works (Valiant, 1984;
Goldreich et al., 1986; Daniely & Shalev-Shwartz, 2016) to show that under
either standard cryptographic assumptions or computational complexity hardness
assumptions, there exist functions in the ${\mathbf{P}}$ time complexity class
that cannot be learned by any polynomial time learning algorithm without
intermediate supervision.

We begin by defining the decomposition of any function $f$ in the
${\mathbf{P}}$ time complexity class into sub tasks. For that, we will use the
fact that any such $f$ has polynomial circuit complexity (see for example
theorem 9.30 in Sipser (2013)), and therefore can be computed by a boolean
circuit with polynomial size. We will denote by $G=\left(V,E\right)$ the
directed acyclic graph associated with such a circuit, and by $l_{v}$ the
logic gates of each vertex $v$. Furthermore, since both the“AND" and “OR"
logical gates can be decomposed into a boolean circuit with binary-tree like
structure, we may assume that the input degree of each vertex is
$O\left(1\right)$.

Figure 3:  The number of steps until a BERT-base sized Transformer learns bit-
subset parities with and without intermediate supervision. By learning we mean
validation accuracy higher than $60\%$. While this definition is somehow
arbitrary, in practice we observed a grokking phenomenon (Power et al., 2021)
where very soon after the accuracy became higher than random level it also
became almost perfect (accuracy $>95\%$).

Now, in order to fit into the sequence-to-sequence setting of section 3, we
define the intermediate labels sequence $\mathcal{S}$ for any $f$. Basically,
each non-leaf vertex $v\in V$ will represent an intermediate task with its
ground-truth label determined by $l_{v}$, and we will use a topological
sorting of $G$ in order to translate $G$ into a sequence of intermediate
labels $\mathcal{S}$ with length $T\coloneqq\left|V\right|$ (see figure 2 for
a concrete example of this abstract construction strategy). Importantly, as in
the bit-subsets parity task, $T$ is polynomial in $d$.

In order to show our generalized positive result, theorem 2 motivates us to
prove that our sequence-to-sequence formulation of any function $f$ in the
${\mathbf{P}}$ time complexity class, which includes the intermediate labels
sequence $\mathcal{S}$ defined above, can be written as a multivariate
function where each of its outputs is a simple low degree polynomial of at
most $O\left(1\right)$ input bits. Lemma 3 below shows that this is indeed the
case, _i.e._ , that all the target functions comprising the intermediate
supervision to our problem belong to $\mathcal{H}_{\phi\left(T,\psi,N\right)}$
(see section 3) with $N$,
$\max_{t}\deg\left(\psi_{t}\right),\,\max_{t,i}\left|a_{t,i}\right|$ that do
not grow with $d$.

######  Lemma 3.

For any logical gate
$l_{v}:\left\\{0,1\right\\}^{N}\rightarrow\left\\{0,1\right\\}$ with
$N=O\left(1\right)$, there exists $O\left(1\right)$ degree polynomial
$\psi\left(x\right)=\sum_{i=0}^{\text{deg}\left(\psi\right)}a_{i}x^{i}$ with
bounded coefficients $\max_{i}\left|a_{i}\right|=O\left(1\right)$ as well as
${\mathbf{w}}\in\mathbb{R}^{2N}$ such that:

$\forall
z_{1},\dots,z_{N}\in\left\\{0,1\right\\}\quad\psi\left(\left\langle\frac{{\mathbf{w}}}{\left\|{\mathbf{w}}\right\|},\left(\begin{array}[]{c}{\mathbf{e}}_{z_{1}}\\\
\vdots\\\
{\mathbf{e}}_{z_{N}}\end{array}\right)\right\rangle\right)=l_{v}\left(z_{1},\dots,z_{N}\right)$
(12)

###### Proof.

We will use ${\mathbf{w}}$ to uniquely represent each possible combination of
$z_{0},\dots,z_{N}$ as an $N$ bit real value number, and use polynomial
interpolation to find a $2^{N}$-degree polynomial $\psi$ that interpolates the
$z_{1}=\dots=z_{N}=0\,,\dots,z_{1}=\dots=z_{N}=1$ points. Finally the
$O\left(1\right)$ coefficients boundedness follow from taking maximum555This
maximum exists since there is a finite number of possible functions from
$\left\\{0,1\right\\}^{N}$ into $\left\\{0,1\right\\}$. over all possible
$l_{v}$ logical gates. see full details in appendix B. ∎

The above lemma implies that all of the target functions in our defined
intermediate supervision belong to $\mathcal{H}_{\phi\left(T,\psi,N\right)}$
for $\phi\left(T,\psi,N\right)=O\left(d\right)$. Therefore, together with
theorem 2, it assures us that when intermediate supervision is available,
Algorithm 1 can learn any function in the ${\mathbf{P}}$ time complexity class
with polynomial network size, sample complexity and number of gradient
updates.

Now, after we showed that when incorporating intermediate supervision any
function in the ${\mathbf{P}}$ time complexity class can be learned by a
neural network, our main results is a simple corollary of the above results:

######  Corollary 2.

Under either standard cryptographic assumptions or computational complexity
hardness assumptions, there exists a binary classification problem
parameterized by size $d$, such that the following holds:

  * •

On one hand, when equipped with sub-task decomposition supervision, a simple
sequence-to-sequence model can get arbitrarily low $\epsilon>0$ zero-one loss
with number of gradient updates that is polynomial in $d,\epsilon^{-1}$.

  * •

On the other hand, when supervision regarding sub-task is missing, then for
any polynomial time learning algorithm and (constant) $\epsilon>0$, the zero-
one loss will be higher than $\nicefrac{{1}}{{2}}-\epsilon$.

###### Proof.

Follows directly by combining theorem 2 and lemma 3 with either the negative
results in Valiant (1984); Goldreich et al. (1986) or in Daniely & Shalev-
Shwartz (2016). ∎

##  7 Discussion

In this paper, we show for a broad family of functions an exponential gap
between learning algorithms that rely on intermediate supervision and
algorithms that do not rely on intermediate supervision. Across domains and
architectures, there has been a wide range of proposed methods for introducing
intermediate supervision. Some design specialized architectures, some add
relevant loss terms, etc. The method that is taking over in the NLP domain is
straightforward, and is particularly natural for this domain in which the core
architectures are strong sequence-to-sequence Language Models: Concatenate the
intermediate supervision to the input, and thus jointly train the model to
maximize the likelihood of all the intermediate labels as well as the overall
output. Our analysis is framed in this space, and motivates this intuitive
incorporation of intermediate supervision in the framework of sequence-to-
sequence models. We show that even with a simple sequence-to-sequence
architecture it is feasible to expect such simultaneous compounded learning to
be useful. In this regard, we view our work as providing timely theoretical
feedback to the rapid empirical advances in this field.

Limitations: We proved universal learnability results when sufficient
intermediate supervision was provided. A fundamental question is what happens
when we limit the amount of sub-task supervision. For the task of bit-subset
parity, we demonstrated that supervision regarding $O\left(d\right)$ sub-tasks
can yield an exponential advantage. An interesting question that we leave open
for future work is whether there exists a similar advantage with only
$O\left(1\right)$ sub-tasks.

In addition, while our results show an exponential gain, it is still unclear
which sub-tasks are solvable by end-to-end methods, and which tasks require
decomposition? Interestingly, a recent study (Abbe et al., 2022) addressed
exactly this question for one-layer hidden networks in the mean-field regime.
However, our understanding of this question for practical architectures is
still very limited.

## Reproducibility Statement

A complete proof of all the theoretical claims was included in the appendix.
We also provide the source code for the bit-subset parity experiment in
https://github.com/HUJI-Deep/sub_task_decomposition.

## Acknowledgments and Disclosure of Funding

We thank Eran Malach and Shai Shalev-Shwartz for a helpful discussion on our
stronger negative results, as well as Lifu Wang for clarifying Wang et al.
(2021). This research was supported by the ERC (European Research Council) and
the ISF (Israel Science Foundation). Yoav Levine was supported by the Israel
Academy of Sciences Adams fellowship.

## References

  * Abbe & Sandon (2020) Emmanuel Abbe and Colin Sandon.  On the universality of deep learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 20061–20072. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/e7e8f8e5982b3298c8addedf6811d500-Paper.pdf.
  * Abbe et al. (2021) Emmanuel Abbe, Pritish Kamath, eran malach, Colin Sandon, and Nathan Srebro.  On the power of differentiable learning versus PAC and SQ learning.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=TZPidZS3r_z.
  * Abbe et al. (2022) Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz.  The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks.  In _Conference on Learning Theory_ , pp. 4782–4887. PMLR, 2022\.
  * Allen-Zhu et al. (2019) Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  On the convergence rate of training recurrent neural networks.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/0ee8b85a85a49346fdff9665312a5cc4-Paper.pdf.
  * Bandeira & Van Handel (2016) Afonso S Bandeira and Ramon Van Handel.  Sharp nonasymptotic bounds on the norm of random matrices with independent entries.  _The Annals of Probability_ , 44(4):2479–2506, 2016.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1876–1900. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1457c0d6bfcb4967418bfb8ac142f64a-Paper.pdf.
  * Chang et al. (2020) Oscar Chang, Lampros Flokas, Hod Lipson, and Michael Spranger.  Assessing satnet's ability to solve the symbol grounding problem.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 1428–1439. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/0ff8033cf9437c213ee13937b1c4c455-Paper.pdf.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  _arXiv preprint arXiv:2110.14168_ , 2021.
  * Daniely & Shalev-Shwartz (2016) Amit Daniely and Shai Shalev-Shwartz.  Complexity theoretic limitations on learning dnf’s.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pp. 815–830, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.  URL https://proceedings.mlr.press/v49/daniely16.html.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In Jill Burstein, Christy Doran, and Thamar Solorio (eds.), _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers)_ , pp. 4171–4186. Association for Computational Linguistics, 2019\.  doi: 10.18653/v1/n19-1423.  URL https://doi.org/10.18653/v1/n19-1423.
  * Elman (1990) Jeffrey L Elman.  Finding structure in time.  _Cognitive science_ , 14(2):179–211, 1990.
  * Geva et al. (2021) Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant.  Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies.  _Transactions of the Association for Computational Linguistics (TACL)_ , 2021.
  * Glasmachers (2017) Tobias Glasmachers.  Limits of end-to-end learning.  In _Asian Conference on Machine Learning_ , pp. 17–32. PMLR, 2017\.
  * Goldreich et al. (1986) Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  _Journal of the ACM (JACM)_ , 33(4):792–807, 1986\.
  * Gülçehre & Bengio (2016) Çağlar Gülçehre and Yoshua Bengio.  Knowledge matters: Importance of prior information for optimization.  _Journal of Machine Learning Research_ , 17(8):1–32, 2016.  URL http://jmlr.org/papers/v17/gulchere16a.html.
  * Jacot et al. (2018) Arthur Jacot, Franck Gabriel, and Clément Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Ji & Telgarsky (2020) Ziwei Ji and Matus Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HygegyrYwH.
  * Kalyan et al. (2021) Ashwin Kalyan, Abhinav Kumar, Arjun Chandrasekaran, Ashish Sabharwal, and Peter Clark.  How much coffee was consumed during EMNLP 2019? fermi problems: A new reasoning challenge for AI.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 7318–7328, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.582.  URL https://aclanthology.org/2021.emnlp-main.582.
  * Karlsson (1994) Jonas Karlsson.  Task decomposition in reinforcement learning.  In _Proceedings of the AAAI Spring Symposium on Goal-Driven Learning, Stanford, CA_ , 1994.
  * Kearns (1998) Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  _Journal of the ACM (JACM)_ , 45(6):983–1006, 1998.
  * Krueger & Dayan (2009) Kai A Krueger and Peter Dayan.  Flexible shaping: How learning in small steps helps.  _Cognition_ , 110(3):380–394, 2009.
  * Ling et al. (2017) Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom.  Program induction by rationale generation: Learning to solve and explain algebraic word problems.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 158–167, Vancouver, Canada, July 2017. Association for Computational Linguistics.  doi: 10.18653/v1/P17-1015.  URL https://aclanthology.org/P17-1015.
  * Liu et al. (2022) Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannaneh Hajishirzi.  Generated knowledge prompting for commonsense reasoning.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 3154–3169, Dublin, Ireland, May 2022. Association for Computational Linguistics.  doi: 10.18653/v1/2022.acl-long.225.  URL https://aclanthology.org/2022.acl-long.225.
  * Marthi (2007) Bhaskara Marthi.  Automatic shaping and decomposition of reward functions.  In _Proceedings of the 24th International Conference on Machine learning_ , pp. 601–608, 2007.
  * Ng et al. (1999) Andrew Y Ng, Daishi Harada, and Stuart Russell.  Policy invariance under reward transformations: Theory and application to reward shaping.  In _Icml_ , volume 99, pp. 278–287, 1999.
  * Nye et al. (2022) Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena.  Show your work: Scratchpads for intermediate computation with language models.  In _Deep Learning for Code Workshop_ , 2022.  URL https://openreview.net/forum?id=HBlx2idbkbq.
  * Peterson (2004) Gail B Peterson.  A day of great illumination: Bf skinner’s discovery of shaping.  _Journal of the experimental analysis of behavior_ , 82(3):317–328, 2004.
  * Piękos et al. (2021) Piotr Piękos, Mateusz Malinowski, and Henryk Michalewski.  Measuring and improving BERT’s mathematical abilities by predicting the order of reasoning.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pp. 383–394, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-short.49.  URL https://aclanthology.org/2021.acl-short.49.
  * Power et al. (2021) Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra.  Grokking: Generalization beyond overfitting on small algorithmic datasets.  In _ICLR MATH-AI Workshop_ , 2021.
  * Press et al. (2022) Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis.  Measuring and narrowing the compositionality gap in language models, 2022\.  URL https://arxiv.org/abs/2210.03350.
  * Rae et al. (2021) Jack Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, James Bradbury, Matthew Johnson, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving.  Scaling language models: Methods, analysis & insights from training Gopher.  _arXiv submission_ , 2021.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _Journal of Machine Learning Research_ , 21(140):1–67, 2020.  URL http://jmlr.org/papers/v21/20-074.html.
  * Rajani et al. (2019) Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher.  Explain yourself! leveraging language models for commonsense reasoning.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pp. 4932–4942, Florence, Italy, July 2019. Association for Computational Linguistics.  doi: 10.18653/v1/P19-1487.  URL https://aclanthology.org/P19-1487.
  * Recchia (2021) Gabriel Recchia.  Teaching autoregressive language models complex tasks by demonstration.  _arXiv preprint arXiv:2109.02102_ , 2021.
  * Shalev-Shwartz & Ben-David (2014) Shai Shalev-Shwartz and Shai Ben-David.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Shalev-Shwartz & Shashua (2016) Shai Shalev-Shwartz and Amnon Shashua.  On the sample complexity of end-to-end training vs. semantic abstraction training.  _arXiv preprint arXiv:1604.06915_ , 2016.
  * Shalev-Shwartz et al. (2017) Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah.  Failures of gradient-based deep learning.  In _International Conference on Machine Learning_ , pp. 3067–3075. PMLR, 2017.
  * Shamir (2018) Ohad Shamir.  Distribution-specific hardness of learning neural networks.  _The Journal of Machine Learning Research_ , 19(1):1135–1163, 2018.
  * Sipser (2013) M Sipser.  Introduction to the theory of computation. 3th.  _Cengage Learning_ , 2013.
  * Skinner (1958) Burrhus F Skinner.  Reinforcement today.  _American Psychologist_ , 13(3):94, 1958.
  * Valiant (1984) Leslie G Valiant.  A theory of the learnable.  _Communications of the ACM_ , 27(11):1134–1142, 1984.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang et al. (2021) Lifu Wang, Bo Shen, Bo Hu, and Xing Cao.  On the provable generalization of recurrent neural networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 20258–20269. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/a928731e103dfc64c0027fa84709689e-Paper.pdf.
  * Wang et al. (2019) Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter.  Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.  In _International Conference on Machine Learning_ , pp. 6545–6554. PMLR, 2019.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou.  Chain of thought prompting elicits reasoning in large language models.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=_VjQlMeSB_J.
  * Wies et al. (2021) Noam Wies, Yoav Levine, Daniel Jannai, and Amnon Shashua.  Which transformer architecture fits my data? a vocabulary bottleneck in self-attention.  In Marina Meila and Tong Zhang (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 11170–11181. PMLR, 18–24 Jul 2021.  URL https://proceedings.mlr.press/v139/wies21a.html.
  * Williams & Zipser (1989) Ronald J Williams and David Zipser.  A learning algorithm for continually running fully recurrent neural networks.  _Neural computation_ , 1(2):270–280, 1989.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, October 2020. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/2020.emnlp-demos.6.
  * Zelikman et al. (2022) Eric Zelikman, Yuhuai Wu, and Noah D. Goodman.  Star: Bootstrapping reasoning with reasoning, 2022.  URL https://arxiv.org/abs/2203.14465.
  * Zhai et al. (2022) Yuexiang Zhai, Christina Baek, Zhengyuan Zhou, Jiantao Jiao, and Yi Ma.  Computational benefits of intermediate rewards for goal-reaching policy learning.  _Journal of Artificial Intelligence Research_ , 73:847–896, 2022.

##  Appendix A Compounded Sequence to Sequence Learnability Details

We start by formally defining our sequence-to-sequence functions complexity
measure as:

$\displaystyle\phi\left(T,\psi,N\right)\coloneqq\tilde{O}\left(T^{16+3N+\max_{t}\deg\left(\psi_{t}\right)}C^{2N}\max_{t}\deg\left(\psi_{t}\right)^{3N}\max_{t,i}\left|a_{t,i}\right|^{2}\right)$
(13)

Where $C>0$ is some constant.

Now we prove lemma 1 from the main text. Essentially this lemma applies the
union bound to show that when the zero-one loss of all the single-hop sub-
tasks is low, then also at test time — when the model does not have the ground
truth results of the previous sub-task and errors may accumulate — the zero-
one loss on the final answer is still low.

###### Proof.

Denote by $\epsilon$ the zero-one loss for ${\mathbf{z}}^{\text{train}}$,
_i.e._ , the right hand side in eq 5. Clearly, for any ${\mathbf{x}}$ when
$f^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)$ solves all the sub-
tasks correctly we have that
${\mathbf{z}}^{\text{test}}={\mathbf{z}}^{\text{train}}$ and therefore
$l_{0-1}\left(y,f_{T}^{\text{RNN},W}\left({\mathbf{z}}^{\text{test}}\right)\right)=0$.
So it is enough to upper bound the probability that
$f^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)$ makes an error in
any sub-task by $\epsilon$. But by the zero-one loss definition, for any $t$
we have that:

$\displaystyle
P_{{\mathbf{x}}}\left(f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\neq
y_{t}\right)=\mathbb{E}_{{\mathbf{x}}}\left[l_{0-1}\left(y_{t},f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\right)\right]$
(14)

And therefore
$\sum_{t=d}^{T}P_{{\mathbf{x}}}\left(f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\neq
y_{t}\right)=\epsilon$. Finally, by the union bound we got that

$\displaystyle P_{{\mathbf{x}}}\left(\exists d\leq t\leq T\quad
f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\neq
y_{t}\right)\leq\sum_{t=d}^{T}P_{{\mathbf{x}}}\left(f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\text{train}}\right)\neq
y_{t}\right)=\epsilon$ (15)

∎

##  Appendix B Sub Tasks Learnability Proofs

In this section we prove lemmas 2,3 from the main text, _i.e._ , we prove that
our intermediate steps are simple enough to be covered by theorem 2.

We begin by formally describing the details of learning parities with
sequence-to-sequence models. Since sequence-to-sequence models expect their
inputs to be sequences, we will translate the tree described in section 5 into
a sequence by inverse BFS like tree traversal, and concatenate the result
sequence after ${\mathbf{x}}$. Therefore, our inputs sequence includes all the
$d$ variables in ${\mathbf{x}}$, together with all the sub-tasks decomposition
nodes in the binary tree except the root (that represent $y$). So we will have
an input sequence length $T$ that is equal to:

$\displaystyle T\coloneqq d+\text{nodes in full binary tree
with}\,\frac{d}{4}\,\text{leaves}-1=\frac{3}{2}d-2$ (16)

And the ground-truth sub-task results are recursively defined by:

$\displaystyle\forall t\geq d\quad
y_{t}=\begin{cases}\left(-1\right)^{x_{i_{2\left(t-d\right)+1}}+x_{i_{2\left(t-d\right)+2}}}&t<\frac{5}{4}d\\\
\left(-1\right)^{y_{2\left(t-\frac{5d}{4}\right)+d}+y_{2\left(t-\frac{5d}{4}\right)+d+1}}&\text{else}\end{cases}$
(17)

For $t>d$, at training time, $z_{t}$ will be the ground-truth sub-task result
$y_{t-1}$. At test time $z_{t}$ will be the model prediction at time $t-1$:

$\displaystyle\forall t\in\left[T\right]\quad z_{t}=\begin{cases}x_{t}&t\leq
d\\\
\frac{1}{2}+\frac{1}{2}\text{sign}\left(f_{t-1}^{\text{RNN}}\left(\begin{array}[]{ccc}z_{1},&\cdots&,z_{t-1}\end{array}\right)\right)&t>d\,\wedge\,\text{test}\\\
\frac{1+y_{t-1}}{2}&t>d\,\wedge\,\text{training}\end{cases}$ (18)

Note that $f^{\text{RNN}}$ is causal model, _i.e._ $f^{\text{RNN}}_{t_{1}}$
does not depend on ${\mathbf{z}}_{t_{2}}$ for any $t_{2}>t_{1}$, and therefore
eq 18 is well defined.

Now, we prove lemma 2 from the main text. Essentially this lemma shows that
the intermediate steps of length $2$ parities belong to the hypothesis class
define in eq 9.

###### Proof.

Define ${\mathbf{w}}\coloneqq\frac{1}{\sqrt{2}}\left(\begin{array}[]{c}1\\\
0\\\ 1\\\ 0\end{array}\right)$, then

$\displaystyle\left\langle\frac{{\mathbf{w}}}{\left\|{\mathbf{w}}\right\|},\left(\begin{array}[]{c}{\mathbf{e}}_{z_{1}}\\\
{\mathbf{e}}_{z_{2}}\end{array}\right)\right\rangle=\begin{cases}\sqrt{2}&z_{1}=0\wedge
z_{2}=0\\\ \frac{1}{\sqrt{2}}&z_{1}\neq z_{2}\\\ 0&z_{1}=1\wedge
z_{2}=1\end{cases}$ (21)

Therefore, it is enough to find $\psi$ such that

$\displaystyle\psi\left(0\right)=\psi\left(\sqrt{2}\right)=1\,\wedge\,\psi\left(\frac{1}{\sqrt{2}}\right)=-1$
(22)

Finally, we will use Lagrange basis functions to find the required polynomial
and get:

$\displaystyle\psi\left(z\right)$
$\displaystyle=\left(\frac{z-\frac{1}{\sqrt{2}}}{0-\frac{1}{\sqrt{2}}}\right)\left(\frac{z-\sqrt{2}}{0-\sqrt{2}}\right)-\left(\frac{z-0}{\frac{1}{\sqrt{2}}-0}\right)\left(\frac{z-\sqrt{2}}{\frac{1}{\sqrt{2}}-\sqrt{2}}\right)+\left(\frac{z-0}{\sqrt{2}-0}\right)\left(\frac{z-\frac{1}{\sqrt{2}}}{\sqrt{2}-\frac{1}{\sqrt{2}}}\right)$
(23)
$\displaystyle=1\cdot\left(z-\frac{1}{\sqrt{2}}\right)\left(z-\sqrt{2}\right)+\frac{z}{2}\left(z-\sqrt{2}\right)+3z\left(z-\frac{1}{\sqrt{2}}\right)$
(24)
$\displaystyle=\left(z^{2}-\frac{3}{\sqrt{2}}z+1\right)+\left(\frac{z^{2}}{2}-\frac{1}{\sqrt{2}}z\right)+\left(3z^{2}-\frac{3z}{\sqrt{2}}\right)$
(25) $\displaystyle=\frac{9}{2}z^{2}-\frac{7}{\sqrt{2}}z+1$ (26)

∎

Now we prove lemma 3 from the main text. Essentially this lemma shows that
also our intermediate steps for any functions in the ${\mathbf{P}}$ time
complexity class belongs to the hypothesis class define in eq 9.

###### Proof.

Denote
$\alpha\left(z_{1},\dots,z_{N}\right)\coloneqq\sum_{i=0}^{N-1}2^{i}\cdot
1_{z_{i}=0}$ the function that converts $N$ bits to their binary string, and
define
${\mathbf{w}}\coloneqq\sqrt{\frac{3}{4^{N}-1}}\left(\begin{array}[]{c}2^{0}\\\
0\\\ 2^{1}\\\ 0\\\ \vdots\\\ 2^{N-1}\\\ 0\end{array}\right)$, then
${\mathbf{w}}$ is a unit vector that represents $z_{1},\dots,z_{N}$ as $N$ bit
numbers
$\left\langle\frac{{\mathbf{w}}}{\left\|{\mathbf{w}}\right\|},\left(\begin{array}[]{c}{\mathbf{e}}_{z_{1}}\\\
\vdots\\\
{\mathbf{e}}_{z_{N}}\end{array}\right)\right\rangle=\alpha\left(z_{1},\dots,z_{N}\right)$.
Now, we can use the Lagrange basis functions to find the required polynomial:

$\displaystyle\psi\left(x\right)=\sum_{z_{1},\dots,z_{N}=0}^{1}\left(f_{v}\left(z_{1},\dots,z_{N}\right)\prod_{\left(\tilde{z}_{1},\dots,\tilde{z}_{N}\right)\neq\left(z_{1},\dots,z_{N}\right)}\left(\frac{x-\alpha\left(\tilde{z}_{1},\dots,\tilde{z}_{N}\right)}{\alpha\left(z_{1},\dots,z_{N}\right)-\alpha\left(\tilde{z}_{1},\dots,\tilde{z}_{N}\right)}\right)\right)$
(27)

Finally the $O\left(1\right)$ coefficients boundedness follows from taking the
maximum666This maximum is exists since there is a finite number of possible
function from $\left\\{0,1\right\\}^{N}$ into $\left\\{0,1\right\\}$. over all
possible $f_{v}$ functions. ∎

##  Appendix C Extension for SGD with finite precision

In this section, we prove theorem 2 from the main text holds also for
algorithm 2 which is a finite-precision variant of SGD777See section D for the
extension of the proof to algorithm 3 that is based on GD.. . We will follow
the proof in Wang et al. (2021) while taking into account the finite precision
gradients.

Data: Data set $\mathcal{D}$, learning rate $\eta$, finite precision $\sigma$.

Initialization: The entries of $W^{\left(0\right)},A,M_{0}$ are generated
i.i.d. from $N(0,\frac{2}{m})$. The entries of $B$ are generated i.i.d. from
$N(0,\frac{1}{m})$.

for  _$i=1,2,3...n$_ do

Randomly sample $({\mathbf{x}}_{i},{\mathbf{y}}_{i})$ from the data set
$\mathcal{D}$.

Get arbitrary $\sigma$-approximation of the gradient:

$G^{\left(i\right)}\in\mathcal{B}_{\infty}\left(\nabla_{W^{\left(i-1\right)}}\ell({\mathbf{y}}_{i}\,,\,f^{\text{RNN},W^{\left(i-1\right)}}({\mathbf{z}}_{i}))\,,\,\sigma\right)$888The
ball is with respect to the distance that defined by the max matrix norm,
_i.e._ the elementwise distances are at most $\sigma$..

Update weights:

$W^{\left(i\right)}=W^{\left(i-1\right)}-\eta G^{\left(i\right)}$.

end for

Algorithm 2 Training $f^{\text{RNN}}$ with finite precision SGD (an finite
precisio variant of algorithm 1)

We begin by stating theorem 2999Combined with Remark H.1 in Wang et al.
(2021)’s supplementary materials. In addition, for simplicity, we state a
$\nicefrac{{1}}{{\sqrt{n}}}$ convergence rate as opposite to the linear
convergence rate in Wang et al. (2021). in Wang et al. (2021) with our
notations:

######  Theorem 3.

Let $\delta>0$, and assume we run algorithm 1 for $n$ iterations with learning
rate $\eta=\frac{1}{m\sqrt{n}}$. Then there exists
$m^{\star}=\text{poly}\left(n,\delta^{-1},T\right)$ such that if $m>m^{\star}$
then for any $h\in\mathcal{H}_{\phi\left(T,\psi,N\right)}$ with probability at
least $1-\delta$ over the randomness in algorithm 1, the following hold:

$\displaystyle\mathbb{E}_{{\mathbf{x}}}\left[\left(\frac{1}{n\left(T-d\right)}\right)\sum_{t=d}^{T}\sum_{i=1}^{n}l_{0-1}\left(y_{t},f_{t}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]<\tilde{O}\left(\frac{\phi\left(T,\psi,N\right)}{\sqrt{n}}\right)+O\left(\frac{\log{\frac{1}{\delta}}}{\sqrt{n}}\right)$
(28)

where $W^{\left[i\right]}$ denote the output of algorithm 1 at the $i$’th
iteration and $l_{0-1}$ is the zero-one loss.

Clearly when using infinite precision SGD theorem 2 follows from theorem 3 and
lemma 1 by simple algebraic manipulations. Therefore, for proving theorem 2
with finite precision gradient based optimization, it is enough to modify
theorem’s 3 proof to analyze algorithm 2 that uses finite precision gradients,
instead of algorithm 1 that uses full precision gradients.

While complicated, Wang et al. (2021)’s proof for theorem 3 can be divided
into two high-level arguments. The first argument measure the _complexity_ of
the learned hypothesis class with respect to random initialization of
$f^{\text{RNN}}$ (lemma 6). And the second argument is a generalization bound
for algorithm 1 with networks that are overparameterized enough. Since the
first argument is independent of the gradients, the proof of the first
argument still holds and we only need to prove a generalization bound for
algorithm 2. More specifically we only need to prove a lemma that is
equivalent to lemma 14 in Wang et al. (2021) and the rest of the second
argument (lemma 7 in Wang et al. (2021)) remain unchanged.

######  Lemma 4.

Let $n\in\mathbb{N}$, and denote by $L_{i}\left(W\right)\coloneqq
l\left({\mathbf{y}}^{\left(i\right)},f^{\text{RNN},W}\left({\mathbf{z}}^{\left(i\right)}\right)\right)$
the training loss. Suppose there exists
$W^{\star}\in\mathcal{B}\left(W^{\left(0\right)},\frac{R}{\sqrt{m}}\right)$101010The
ball is with respect to the distance that defined by the Frobenius matrix
norm. such that
$R=O\left(\text{poly}\left(T\right)\right)=\Omega\left(T^{16}\right)$ and
$L_{i}\left(W^{\star}\right)\leq\frac{1+R^{2}}{n}$. Then for any $\delta>0$
there exists $m^{\star}=\text{poly}\left(n,R,T,\delta^{-1}\right)$ such that
if $m>m^{\star}$ then with probability at least $1-\delta$ algorithm 2 with
$\eta=\frac{1}{m\sqrt{n}}$ and finite precision
$\sigma=O\left(\frac{1}{m}\right)$ will output:

$\displaystyle\mathbb{E}_{{\mathbf{x}}}\left[\left(\frac{1}{n\left(T-d\right)}\right)\sum_{t=d}^{T}\sum_{i=1}^{n}l_{0-1}\left(y_{t},f_{t}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]<O\left(\frac{R^{2}+\log{\frac{1}{\delta}}}{\sqrt{n}}\right)$
(29)

###### Proof.

We begin by showing that with high probability over the initialization of
$f^{\text{RNN}}$, at any iteration $i\leq n$ of algorithm 2, the distance of
the learned hidden weights matrix $W^{\left(i\right)}$ from its initialization
point $W^{\left(0\right)}$ is not too large. As a results we will get that the
assumption of lemma 8 uphold, and therefore its upper bound of the deviation
from linearization is valid.

By the triangle inequality for any $0\leq i<n$ we have that:

$\displaystyle\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}\leq\sum_{k=0}^{i}\left\|W^{\left(k+1\right)}-W^{\left(k\right)}\right\|_{F}$
(30)

Substituting algorithm 2 update rule for $W^{\left(k+1\right)}$, we get that
there exist $\left\|\sigma{}_{i}\right\|_{\infty}<\sigma$ such that:

$\displaystyle
W^{\left(k+1\right)}-W^{\left(k\right)}=-\eta\left(\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}_{k}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k}))+\sigma{}_{k}\right)$
(31)

Now, explicitly writing
$\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}_{k}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k}))$
with the chain rule we have that:

$\displaystyle\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}_{k}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k}))=\frac{1}{T-d}\left(\sum_{t=d}^{T}\left(\frac{-y_{t}^{\left(k\right)}\cdot
e^{-y_{t}^{\left(k\right)}f_{t}^{\text{RNN},W}\left({\mathbf{z}}_{k}\right)}}{1+e^{-y_{t}^{\left(k\right)}f_{t}^{\text{RNN},W}\left({\mathbf{z}}_{k}\right)}}\right)\cdot\left(\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k})\right)\right)$
(32)

and since $0\leq\frac{x}{1+x}\leq 1$ for any $x\geq 0$, we conclude that:

$\displaystyle\left\|\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}_{k}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k}))\right\|_{F}\leq\max_{d\leq
t\leq
T}\left\|\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k})\right\|_{F}$
(33)

Now we will use an induction over $i$, to show that
$\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}=O\left(\frac{\left(i+1\right)T^{8}}{m\cdot\sqrt{n}}\right)$
for any $0\leq i<n$. By the induction hypothesis, lemma 10 assure us that for
wide enough networks
$m^{\star}=\Omega\left(\max\left\\{T^{6}\log^{3}\left(\frac{n\cdot
T}{\delta}\right),\sqrt{n}T^{8}\right\\}\right)$, with probability of at least
$1-\delta$ over the initialization of $f^{\text{RNN}}$, $\max_{d\leq t\leq
T}\left\|\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k})\right\|_{F}=O\left(T^{8}\right)$.
Therefore, in this case

$\displaystyle\left\|W^{\left(k+1\right)}-W^{\left(k\right)}\right\|_{F}=\eta
O\left(T^{8}+\frac{1}{m}\right)=O\left(\frac{T^{8}}{m\cdot\sqrt{n}}+\frac{1}{m^{2}\sqrt{n}}\right)$
(34)

and hence
$\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}=O\left(\frac{\left(i+1\right)T^{8}}{m\cdot\sqrt{n}}\right)$
as required.

Now after we showed the assumptions of lemma 8 upholds, we can use it to
obtain first order Taylor approximation of the training loss:

$\displaystyle
L_{i}\left(W^{\left(i\right)}\right)-L_{i}\left(W^{\star}\right)$
$\displaystyle\leq\left\langle\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}_{i}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}_{i})),W^{\left(i\right)}-W^{\star}\right\rangle$
(35) $\displaystyle+\max_{d\leq t\leq T}\underbrace{\left|\frac{y_{t}\cdot
e^{-y_{t}f^{\text{RNN},W}\left({\mathbf{z}}_{i}\right)}}{1+e^{-y_{t}f^{\text{RNN},W}\left({\mathbf{z}}_{i}\right)}}\right|}_{\leq
1}\cdot
O\left(\left(\frac{R}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left\|W^{\left(i\right)}-W^{\star}\right\|_{F}$ (36)

Where we assumed that $m^{\star}>n$ and therefore
$\left\|W^{\left(i\right)}-W^{\left(0\right)}\right\|_{F}<O\left(\frac{R}{\sqrt{m}}\right)$.

Using algorithm 2 update rule for $W^{\left(i+1\right)}$ again (see eq 31), we
can use an inequality from in Shalev-Shwartz & Ben-David (2014)’s lemma 14.1
to get that:

$\displaystyle\sum_{i=1}^{n}\left\langle\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}_{i}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}_{i}))+\sigma{}_{i},W^{\left(i\right)}-W^{\star}\right\rangle$
(37)
$\displaystyle\leq\frac{\left\|W^{\left(1\right)}-W^{\star}\right\|_{F}^{2}}{2\eta}+\frac{\eta}{2}\sum_{i=1}^{n}\left\|\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}_{i}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}_{i}))+\sigma{}_{i}\right\|_{F}^{2}$
(38)

Now combing with Cauchy–Schwarz inequality we have that:

$\displaystyle\sum_{i=1}^{n}\left(L_{i}\left(W^{\left(i\right)}\right)-L_{i}\left(W^{\star}\right)\right)$
$\displaystyle\leq\frac{\left\|W^{\left(1\right)}-W^{\star}\right\|_{F}^{2}}{2\eta}+\frac{\eta}{2}\sum_{i=1}^{n}\left\|\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}_{k}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}_{k}))+\sigma{}_{k}\right\|_{F}^{2}$
(39)
$\displaystyle+O\left(\left(\frac{R}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left(\sum_{i=1}^{n}\left\|W^{\left(i\right)}-W^{\star}\right\|_{F}\right)$
(40)
$\displaystyle-\sum_{i=1}^{n}\left\langle\sigma{}_{i},W^{\left(i\right)}-W^{\star}\right\rangle$
(41)

Substituting the upper bounds from eqs 33, 34 and using the assumption that
$R=\Omega\left(T^{16}\right)$ we get that:

$\displaystyle\sum_{i=1}^{n}\left(L_{i}\left(W^{\left(i\right)}\right)-L_{i}\left(W^{\star}\right)\right)\leq\frac{O\left(R^{2}+T^{16}\right)}{2\eta
m}+\frac{\eta\cdot n}{2}O\left(T^{8}+1\right)^{2}$ (42)
$\displaystyle+O\left(\left(\frac{R}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}n\left(\log
m\right)\right)\left(R+nT^{8}\right)+O\left(m^{-\frac{3}{2}}\left(n^{2}T^{8}+nR\right)\right)$
(43) $\displaystyle\leq
O\left(R^{2}\sqrt{n}\right)+O\left(\left(\frac{R}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}n\left(\log
m\right)\right)\left(R+nT^{8}\right)+O\left(m^{-\frac{3}{2}}n^{2}R\right)$
(44)

To ensure the left hand side is upper bounded by $O\left(R^{2}\sqrt{n}\right)$
we will chose $m^{\star}$ such that
$\frac{m^{\star}}{\left(\log^{3}m^{\star}\right)}>n^{\frac{9}{2}}$, note that,
as required, $m^{\star}$ is polynomial in $n,T$. Then for $m>m^{\star}$ we
have that $\sum_{i=1}^{n}L_{i}\left(W^{\left(i\right)}\right)\leq
O\left(R^{2}\sqrt{n}\right)$. Therefore,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}L_{i}\left(W^{\left(i\right)}\right)\leq
O\left(\frac{R^{2}}{\sqrt{n}}\right)$ (45)

Now, to prove generalization bound we will follow lemma 4.3 in Ji & Telgarsky
(2020) and use a martingale Bernstein bound argument. We begin by showing that
during the whole training process, our binary cross entropy loss is bounded.
Indeed lemma 9 assure us that :

$\displaystyle\max_{{\mathbf{x}}\in\left\\{0,1\right\\}^{d}}\max_{d<t\leq
T}\left|f_{t}^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}})\right|=O\left(T^{14}\cdot\sqrt{\frac{n}{m}}+T\right)\leq
O\left(T^{14}\right)$ (46)

Therefore, their exist a constant $C>0$ such that the binary cross entropy
loss is bounded by $\log\left(1+e^{O\left(T^{14}\right)}\right)\leq C\cdot
T^{14}$.

Now, we will define a bounded martingle. For any $i\geq 0$, let $s_{i}$ denote
$\left({\mathbf{x}}_{i},{\mathbf{y}}_{i}\right)$ and $s_{0,i}$ denote
$\left(s_{0},\dots,s_{i}\right)$. Importantly, the quantity

$\displaystyle\frac{1}{C\cdot
T^{14}}\left(\sum_{t<i}\left(\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]-l\left({\mathbf{y}}_{t},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}_{t}\right)\right)\right)\right)$
(47)

is a martingal w.r.t the filration $\sigma\left(s_{0,i-1}\right)$. This
martingal difference sequence is given by

$\displaystyle\frac{1}{C\cdot
T^{14}}\left(\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]-l\left({\mathbf{y}}_{t},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}_{t}\right)\right)\right)\leq
1$ (48)

Moreover, we have

$\displaystyle\mathbb{E}_{s_{0,t}}\left[\frac{1}{C^{2}\cdot
T^{28}}\left(\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]-l\left({\mathbf{y}}_{t},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}_{t}\right)\right)\right)^{2}|\sigma\left(s_{0,i-1}\right)\right]$
(49) $\displaystyle=\frac{1}{C^{2}\cdot
T^{28}}\left(\mathbb{E}_{s_{0,t}}\left[l\left({\mathbf{y}}_{t},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}_{t}\right)\right)^{2}|\sigma\left(s_{0,i-1}\right)\right]-\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]^{2}\right)$
(50) $\displaystyle\leq\mathbb{E}_{s_{0,t}}\left[\frac{1}{C\cdot
T^{14}}l\left({\mathbf{y}}_{t},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}_{t}\right)\right)|\sigma\left(s_{0,i-1}\right)\right]$
(51) $\displaystyle=\frac{1}{C\cdot
T^{14}}\cdot\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]$
(52)

Therefore, by lemma C.2 in Ji & Telgarsky (2020) we have that with probability
$1-\delta$

$\displaystyle\frac{1}{C\cdot
T^{14}}\sum_{i=1}^{n}\left(\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]-l\left({\mathbf{y}}_{i},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}_{i}\right)\right)\right)$
(53) $\displaystyle\leq\frac{1}{C\cdot
T^{14}}\left(e-2\right)\cdot\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]+\ln\left(\frac{1}{\delta}\right)$
(54)

And hence

$\displaystyle\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(t\right)}}\left({\mathbf{z}}\right)\right)\right]$
$\displaystyle\leq\frac{1}{\left(3-e\right)}\sum_{i=1}^{n}l\left({\mathbf{y}}_{i},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}_{i}\right)\right)+O\left(T^{14}\right)\ln\left(\frac{1}{\delta}\right)$
(55)
$\displaystyle=O\left(R^{2}\sqrt{n}\right)+O\left(R\ln\left(\frac{1}{\delta}\right)\right)$
(56)

Finally, for $y_{t}\cdot f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)<0$ we
have that $\log\left(1+e^{-y_{t}\cdot
f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}\right)>\log 2$. In addition,
clearly $\log\left(1+e^{-y_{t}\cdot
f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}\right)>0$. Therefore, we
conclude that
$\frac{1}{T-d}\sum_{t=d}^{T}l_{o-1}\left(y_{t},f_{t}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)<\frac{1}{\log
2}l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)$
and thus eq 29 uphold. ∎

##  Appendix D Extension for GD with finite precision

In this section, we prove theorem 2 from the main text still holds when using
the gradient descent based algorithm 3, instead of the stochastic gradient
descent based algorithm 2. . Establishing our positive results that the
parities task is efficiently learnable with sub-task decomposition supervision
in the exact same setting of the negative results that show that learning is
impossible without intermediate supervision, presented in section F. We will
follow the proof in section C while taking into account the full non-
stochastic gradients.

Data: Data set $\mathcal{D}$, learning rate $\eta$, finite precision $\sigma$.

Initialization: The entries of $W^{\left(0\right)},A,M_{0}$ are generated
i.i.d. from $N(0,\frac{2}{m})$. The entries of $B$ are generated i.i.d. from
$N(0,\frac{1}{m})$.

for  _$i=1,2,3...n$_ do

Get arbitrary $\sigma$-approximation of the gradient:

$G^{\left(i\right)}\in\mathcal{B}_{\infty}\left(\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(i-1\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(i-1\right)}}({\mathbf{z}}))\right]\,,\,\sigma\right)$111111The
ball is with respect to the distance that defined by the max matrix norm,
_i.e._ the elementwise distances are at most $\sigma$..

Update weights:

$W^{\left(i\right)}=W^{\left(i-1\right)}-\eta G^{\left(i\right)}$.

end for

Algorithm 3 Training $f^{\text{RNN}}$ with finite precision GD

We begin by sampling a fake training set denoted by
${\mathbf{x}}^{\left(1\right)},\dots,{\mathbf{x}}^{\left(n\right)},{\mathbf{y}}^{\left(1\right)},\dots,{\mathbf{y}}^{\left(n\right)}$.
Essentially, we will apply the same reasoning as in section C with this fake
training points. As in the finite precision SGD case it is enough to prove a
lemma that is equivalent to lemma 4 in section C.

######  Lemma 5.

Let $n\in\mathbb{N}$, and denote by $L_{i}\left(W\right)\coloneqq
l\left({\mathbf{y}}^{\left(i\right)},f^{\text{RNN},W}\left({\mathbf{z}}^{\left(i\right)}\right)\right)$
the training loss. Suppose there exists
$W^{\star}\in\mathcal{B}\left(W^{\left(0\right)},\frac{R}{\sqrt{m}}\right)$121212The
ball is with respect to the distance that defined by the Frobenius matrix
norm. such that
$R=O\left(\text{poly}\left(T\right)\right)=\Omega\left(T^{16}\right)$ and
$L_{i}\left(W^{\star}\right)\leq\frac{1+R^{2}}{n}$. Then for any $\delta>0$
there exists $m^{\star}=\text{poly}\left(n,R,T,\delta^{-1}\right)$ such that
if $m>m^{\star}$ then with probability at least $1-\delta$ algorithm 3 with
$\eta=\frac{1}{m\sqrt{n}}$ and finite precision
$\sigma=O\left(\frac{1}{m}\right)$ will output:

$\displaystyle\mathbb{E}_{{\mathbf{x}}}\left[\left(\frac{1}{n\left(T-d\right)}\right)\sum_{t=d}^{T}\sum_{i=1}^{n}l_{0-1}\left(y_{t},f_{t}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]<O\left(\frac{R^{2}+\log{\frac{1}{\delta}}}{\sqrt{n}}\right)$
(57)

###### Proof.

We begin by showing that there exists
$\tilde{W}\in\mathcal{B}\left(W^{\left(0\right)},\frac{T^{8}}{\sqrt{m}}\right)$
such that:

$\displaystyle\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},\tilde{W}}\left({\mathbf{z}}\right)\right)\right]\leq
O\left(\frac{R^{2}}{\sqrt{n}}\right)$ (58)

Indeed, since the minimum can not be larger than the mean, eq‘55 in the proof
of lemma 4 assure us that under the assumptions of lemma 5, for
$m>\max\left\\{n^{2},\ln^{4}\left(\frac{1}{\delta}\right)\right\\}$, with
probability of at least $1-\delta$ algorithm 2 will reach such $\tilde{W}$
during the first $\max\left\\{n,\ln^{2}\left(\frac{1}{\delta}\right)\right\\}$
SGD iteration.

Now we shows that that with high probability over the initialization of
$f^{\text{RNN}}$, at any iteration $i\leq n$ of algorithm 3, the distance of
the learned hidden weights matrix $W^{\left(i\right)}$ from its initialization
point $W^{\left(0\right)}$ is not too large. As a results we will get that the
assumption of lemma 8 uphold, and therefore its upper bound of the deviation
from linearization is valid.

By the triangle inequality for any $0\leq i<n$ we have that:

$\displaystyle\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}\leq\sum_{k=0}^{i}\left\|W^{\left(k+1\right)}-W^{\left(k\right)}\right\|_{F}$
(59)

Substituting algorithm 3 update rule for $W^{\left(k+1\right)}$, we get that
there exist $\left\|\sigma{}_{i}\right\|_{\infty}<\sigma$ such that:

$\displaystyle
W^{\left(k+1\right)}-W^{\left(k\right)}=-\eta\left(\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}))\right]+\sigma{}_{k}\right)$
(60)

Now, explicitly writing
$\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}))$
with the chain rule we have that:

$\displaystyle\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}))=\frac{1}{T-d}\left(\sum_{t=d}^{T}\left(\frac{-y_{t}\cdot
e^{-y_{t}f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}}{1+e^{-y_{t}f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}}\right)\cdot\left(\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}})\right)\right)$
(61)

and since $0\leq\frac{x}{1+x}\leq 1$ for any $x\geq 0$, we conclude by
Jensen’s inequality that:

$\displaystyle\left\|\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(k\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}}))\right]\right\|_{F}\leq\frac{1}{T-d}\sum_{t=d}^{T}\mathbb{E}_{{\mathbf{x}}}\left[\left\|\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}})\right\|_{F}\right]$
(62)

Now we will use an induction over $i$, to show that
$\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}=O\left(\frac{\left(i+1\right)T^{8}}{m\cdot\sqrt{n}}\right)$
for any $0\leq i<n$. By the induction hypothesis, lemma 10 assure us that for
wide enough networks
$m^{\star}=\Omega\left(\max\left\\{T^{7}\log^{3}\left(\frac{n\cdot
T}{\delta}\right),\sqrt{n}T^{8}\right\\}\right)$, with probability of at least
$1-\delta$ over the initialization of $f^{\text{RNN}}$,
$\mathbb{E}_{{\mathbf{x}}}\left[\left\|\nabla_{W^{\left(k\right)}}f_{t}^{\text{RNN},W^{\left(k\right)}}({\mathbf{z}})\right\|_{F}\right]=O\left(T^{8}\right)$
for any $d\leq t\leq T$. Therefore, in this case

$\displaystyle\left\|W^{\left(k+1\right)}-W^{\left(k\right)}\right\|_{F}=\eta
O\left(T^{8}+1\right)=O\left(\frac{T^{8}}{m\cdot\sqrt{n}}+\frac{1}{m^{2}\sqrt{n}}\right)$
(63)

and hence
$\left\|W^{\left(i+1\right)}-W^{\left(0\right)}\right\|_{F}=O\left(\frac{\left(i+1\right)T^{8}}{m\cdot\sqrt{n}}\right)$
as required.

Now after we showed the assumptions of lemma 11 upholds, we can use it to
obtain first order Taylor approximation of the training loss for any
${\mathbf{x}}$:

$\displaystyle
l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)-l\left({\mathbf{y}},f^{\text{RNN},\tilde{W}}\left({\mathbf{z}}\right)\right)\leq\left\langle\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}})),W^{\left(i\right)}-\tilde{W}\right\rangle$
(64) $\displaystyle+\max_{d\leq t\leq T}\underbrace{\left|\frac{y_{t}\cdot
e^{-y_{t}f^{\text{RNN},W}\left({\mathbf{z}}\right)}}{1+e^{-y_{t}f^{\text{RNN},W}\left({\mathbf{z}}\right)}}\right|}_{\leq
1}\cdot
O\left(\left(\frac{T^{8}}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left\|W^{\left(i\right)}-\tilde{W}\right\|_{F}$ (65)

Where we assumed that $m^{\star}>n$ and therefore
$\left\|W^{\left(i\right)}-W^{\left(0\right)}\right\|_{F}<O\left(\frac{T^{8}}{\sqrt{m}}\right)$.

Using algorithm 3 update rule for $W^{\left(k+1\right)}$ again (see eq 60), we
can use an inequality from Shalev-Shwartz & Ben-David (2014)’s section 14.1.1
to get that

$\displaystyle\sum_{i=1}^{n}\left\langle\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}))\right]+\sigma_{i},W^{\left(i\right)}-\tilde{W}\right\rangle$
(66)
$\displaystyle\frac{\left\|W^{\left(1\right)}-\tilde{W}\right\|_{F}^{2}}{2\eta}+\frac{\eta}{2}\sum_{i=1}^{n}\left\|\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}))\right]+\sigma{}_{i}\right\|_{F}^{2}$
(67)

Now, we can take expectation over eq 64, and combine the Cauchy–Schwarz
inequality with the above bound and get that:

$\displaystyle\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)-l\left({\mathbf{y}},f^{\text{RNN},\tilde{W}}\left({\mathbf{z}}\right)\right)\right]$
$\displaystyle\leq\frac{\left\|W^{\left(1\right)}-\tilde{W}\right\|_{F}^{2}}{2\eta}$
(68)
$\displaystyle+\frac{\eta}{2}\sum_{i=1}^{n}\left\|\mathbb{E}_{{\mathbf{x}}}\left[\nabla_{W^{\left(i\right)}}\ell({\mathbf{y}}\,,\,f^{\text{RNN},W^{\left(i\right)}}({\mathbf{z}}))\right]+\sigma{}_{i}\right\|_{F}^{2}$
$\displaystyle+O\left(\left(\frac{T^{8}}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left(\sum_{i=1}^{n}\left\|W^{\left(i\right)}-\tilde{W}\right\|_{F}\right)$
(69)

Substituting the upper bounds from eqs 62, 63 we get that:

$\displaystyle\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)-l\left({\mathbf{y}},f^{\text{RNN},W^{\star}}\left({\mathbf{z}}\right)\right)\right]\leq\frac{O\left(T^{16}\right)}{2\eta
m}+\frac{\eta\cdot n}{2}O\left(T^{8}+1\right)^{2}$ (70)
$\displaystyle+O\left(\left(\frac{T^{8}}{\sqrt{m}}\right)^{\frac{1}{3}}T^{10}n\left(\log
m\right)\right)\left(2nT^{8}\right)+O\left(m^{-\frac{3}{2}}\left(n^{2}T^{8}\right)\right)$
(71) $\displaystyle\leq
O\left(T^{16}\sqrt{n}\right)+O\left(m^{-\frac{1}{6}}T^{\frac{62}{3}}n^{2}\left(\log
m\right)\right)+O\left(m^{-\frac{3}{2}}n^{2}T^{8}\right)$ (72)

To ensure the left hand side is upper bounded by $O\left(R^{2}\sqrt{n}\right)$
we will chose $m^{\star}$ such that
$\frac{m^{\star}}{\left(\log^{3}m^{\star}\right)}>n^{\frac{9}{2}}$, note that,
as required, $m^{\star}$ is polynomial in $n,T$. Then since eq 58 assure us
that
$\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},\tilde{W}}\left({\mathbf{z}}\right)\right)\right]\leq
O\left(\frac{R^{2}}{\sqrt{n}}\right)$, we have that
$\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]\leq
O\left(R^{2}\sqrt{n}\right)$ for $m>m^{\star}$ . Therefore,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbb{E_{{\mathbf{x}}}}\left[l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)\right]\leq
O\left(\frac{R^{2}}{\sqrt{n}}\right)$ (73)

Finally, for $y_{t}\cdot f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)<0$ we
have that $\log\left(1+e^{-y_{t}\cdot
f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}\right)>\log 2$. In addition,
clearly $\log\left(1+e^{-y_{t}\cdot
f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)}\right)>0$. Therefore, we
conclude that
$\frac{1}{T-d}\sum_{t=d}^{T}l_{o-1}\left(y_{t},f_{t}^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)<\frac{1}{\log
2}l\left({\mathbf{y}},f^{\text{RNN},W^{\left(i\right)}}\left({\mathbf{z}}\right)\right)$
and thus eq 57 uphold.

∎

##  Appendix E Learnability Of RNNs

In this section we state and extend several lemmas from Wang et al. (2021) and
Allen-Zhu et al. (2019). We will use this lemmas in sections C,D for extending
theorem 2 in the main text for finite precision SGD and GD.

Following Wang et al. (2021)’s notations, for any target function
$h\in\mathcal{H}_{\phi\left(T,\psi,N\right)}$ and $n$ samples
$\left({\mathbf{z}}^{\left(i\right)}\right)_{i=1}^{n}$ we will denote:

$\displaystyle\mathbf{H}_{i,j}^{t}\coloneqq\frac{1}{m}\left\langle\nabla_{W^{\left(0\right)}}f_{t}^{\text{RNN},W^{\left(0\right)}}({\mathbf{z}}^{\left(i\right)}),\nabla_{W^{\left(0\right)}}f_{t}^{\text{RNN},W^{\left(0\right)}}({\mathbf{z}}^{\left(j\right)})\right\rangle$
(74)

and

$\displaystyle\tilde{y}^{\left(t\right)}=\left(\begin{array}[]{c}h_{t}\left({\mathbf{z}}^{\left(1\right)}\right)\\\
\vdots\\\ h_{t}\left({\mathbf{z}}^{\left(n\right)}\right)\end{array}\right)$
(78)

We start with theorem 4131313Combined with Remark H.1 in Wang et al. (2021)’s
supplementary materials. from Wang et al. (2021) measuring the _complexity_ of
a learned hypothesis class with respect to random initialization of
$f^{\text{RNN}}$.

######  Lemma 6.

Let $\delta>0$ and $n\in\mathbb{N}$, then there exist
$m^{\star}=\text{poly}\left(n,\delta^{-1},T\right)$ such that if $m>m^{\star}$
then for any $h\in\mathcal{H}_{\phi\left(T,\psi,N\right)}$ and
$\left({\mathbf{z}}^{\left(i\right)}\right)_{i=1}^{n}$ with probability at
least $1-\delta$ over the random initialization of $f^{\text{RNN}}$ there
exists matrices
$\mathbf{H}^{d,\infty},\mathbf{H}^{d+1,\infty},\dots,\mathbf{H}^{T,\infty}\in\mathbb{R}^{n\times
n}$ such that for any $d\leq t\leq T$ the following holds:

  1. 1.

There exist
$\mathbf{v}^{\left(t\right)}\in\mathcal{B}_{F}\left(0,\frac{1}{100\sqrt{\left(\tilde{y}^{\left(t\right)}\right)^{T}\left(\mathbf{H}^{t,\infty}\right)^{-1}\tilde{y}^{\left(t\right)}}}\right)$
such that
$\mathbf{H}^{t}+\left(\mathbf{v}^{\left(t\right)}\right)^{T}\mathbf{v}^{\left(t\right)}-\mathbf{H}^{t,\infty}$
is positive semi-definite matrix.

  2. 2.

$\sqrt{\left(\tilde{y}^{\left(t\right)}\right)^{T}\left(\mathbf{H}^{t,\infty}\right)^{-1}\tilde{y}^{\left(t\right)}}=O\left(\sqrt{\phi\left(T,\psi,N\right)}\right)$.

Now we state lemma 15 from Wang et al. (2021). Essentially this lemma state
that with high probability over the initialization of $f^{\text{RNN}}$, there
exists weights that are not far from the initialization and have low training
loss.

######  Lemma 7.

Let
$\left({\mathbf{z}}^{\left(i\right)},{\mathbf{y}}^{\left(i\right)}\right)_{i=1}^{n}$
be the training set and denote by $L_{i}\left(W\right)\coloneqq
l\left({\mathbf{y}}^{\left(i\right)},f^{\text{RNN},W}\left({\mathbf{z}}^{\left(i\right)}\right)\right)$
the training loss. Then for any $\delta>0$ there exists
$m^{\star}=\text{poly}\left(n,R,T,\delta^{-1}\right)$ such that if
$m>m^{\star}$ then with probability at least $1-\delta$, there exist
$W^{\star}\in\mathcal{B}\left(W^{\left(0\right)},\frac{R}{\sqrt{m}}\right)$
such that $L_{i}\left(W^{\star}\right)\leq\frac{1+R^{2}}{n}$ and
$R=\tilde{O}\left(T\sum_{t=d}^{T}\sqrt{\left(\tilde{y}^{\left(t\right)}\right)^{T}\left(\mathbf{H}^{t,\infty}\right)^{-1}\tilde{y}^{\left(t\right)}}\right)$.

Now we state theorem 13 from Wang et al. (2021). Essentially this lemma bounds
the finite width deviation of $f^{\text{RNN}}$ from its infinite width neural
tangent kernel (Jacot et al., 2018).

######  Lemma 8.

Let $m,n\in\mathbb{N}$ and
$r=O\left(\frac{\text{poly}\left(n,T\right)}{\sqrt{m}}\right)$, then with
probability of at least
$1-O\left(n\right)\exp\left(-\Omega\left(m^{\frac{1}{3}}\right)\right)$141414Note
that lemma 13 from Wang et al. (2021) ensure only weaker guaranties of
probability $1-O\left(n\right)\exp\left(-\Omega\left(\log m\right)\right)$,
but we confirm with the authors that theirs proof proves also our stronger
guaranties. over the initialization of $f^{\text{RNN}}$, for all
$\left({\mathbf{z}}^{\left(i\right)}\right)_{i=1}^{n}$ and
$W,\tilde{W}\in\mathcal{B}\left(W^{\left(0\right)},r\right)$ for any $d\leq
t\leq T$ and $i\in\left[n\right]$ the following hold:

$\displaystyle\left|f_{t}^{\text{RNN},\tilde{W}}\left({\mathbf{z}}^{\left(i\right)}\right)-f_{t}^{\text{RNN},W}\left({\mathbf{z}}^{\left(i\right)}\right)-\left\langle\nabla_{W}f_{t}^{\text{RNN},W}({\mathbf{z}}^{\left(i\right)}),\tilde{W}-W\right\rangle\right|$
(79) $\displaystyle=O\left(r^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left\|\tilde{W}-W\right\|_{F}$ (80)

Now we state a simple corollary of lemmas B.3 and C.2.a in Allen-Zhu et al.
(2019). Essentially this corollary bound the output of $f^{\text{RNN}}$ with
high probability over its initialization.

######  Lemma 9.

Let $m\in\mathbb{N}$ and
$W\in\mathcal{B}\left(W^{\left(0\right)},\frac{\text{poly}\left(T\right)}{\sqrt{m}}\right)$151515The
ball is with respect to the distance that defined by the Frobenius matrix
norm., then for a given ${\mathbf{x}}$ and $d<t\leq T$ with probability of at
least $1-e^{-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$ over the
random initialization of $f^{\text{RNN}}$ the following hold:

$\displaystyle\left|f_{t}^{\text{RNN},W}({\mathbf{z}})\right|=O\left(T^{6}\left\|W-W^{\left(0\right)}\right\|_{F}+t\right)$
(81)

Moreover, with probability of at least
$1-e^{O\left(T\right)-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$ also
the following holds:

$\displaystyle\max_{{\mathbf{x}}\in\left\\{0,1\right\\}^{d}}\max_{d<t\leq
T}\left|f_{t}^{\text{RNN},W}({\mathbf{z}})\right|=O\left(T^{6}\left\|W-W^{\left(0\right)}\right\|_{F}+T\right)$
(82)

###### Proof.

We begin by showing that it is enough to bound
$h_{t}\left({\mathbf{z}}\right)$. This is indeed the case since it is well
known that $\left\|B\right\|_{2}=O\left(1\right)$ with probability of at least
$1-e^{-\Omega\left(m\right)}$ (see for example Bandeira & Van Handel (2016)).
Now lemma B.3 from Allen-Zhu et al. (2019) assure us that
$\left\|h_{t}^{W^{\left(0\right)}}({\mathbf{z}})\right\|=O\left(t\right)$, and
finally lemma C.2.a from Allen-Zhu et al. (2019) bounds the deviation from the
initialization
$\left\|h_{t}^{W}({\mathbf{z}})-h_{t}^{W^{\left(0\right)}}({\mathbf{z}})\right\|=O\left(T^{6}\left\|W-W^{\left(0\right)}\right\|_{F}\right)$.
Finally a simple union bound on all the possible $d$ bits configurations prove
also equation 82. ∎

Now, we use lemma 9 proof together with lemmas B.11 and C.9 from Allen-Zhu et
al. (2019) to prove a lemma that bounds the magnitudes of $f^{\text{RNN}}$’s
gradients. We will use this lemma for bounding the finite width deviation of
$f^{\text{RNN}}$ from its infinite width neural tangent kernel (Jacot et al.,
2018). Beyond its application for proving our positive results, lemma 10 below
also implies that $f^{\text{RNN}}$, for which we proved our positive results
when intermediate supervision exists, upholds the polynomially bounded
gradients requirement in the parities negative results with high probability.
Thus proving the actual factor enabling efficient learning is, therefore,
intermediate supervision. 4

######  Lemma 10.

Let $m\in\mathbb{N}$ and
$W\in\mathcal{B}\left(W^{\left(0\right)},\frac{\text{poly}\left(T\right)}{\sqrt{m}}\right)$161616The
ball is with respect to the distance that defined by the Frobenius matrix
norm., then for a given ${\mathbf{x}}$ and $d<t\leq T$ with probability of at
least $1-e^{-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$ over the
random initialization of $f^{\text{RNN}}$ the following hold:

$\displaystyle\left\|\nabla_{W}f_{t}^{\text{RNN},W}({\mathbf{z}})\right\|_{F}=O\left(T^{8}\left\|W-W^{\left(0\right)}\right\|_{F}+T^{4}\right)$
(83)

Moreover, with probability of at least
$1-e^{O\left(T\right)-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$ it
holds simultaneously for all ${\mathbf{x}}$’s and $t$’s.

###### Proof.

Let $D_{t}\in\mathbb{R}^{m\times m}$ be a diagonal matrix that its diagonal
equals to $1$ when $h_{t}^{W}({\mathbf{z}})>0$ and otherwise $0$. Then we can
write the gradients of $f^{\text{RNN}}$ as:

$\displaystyle\nabla_{W}f_{t}^{\text{RNN},W}({\mathbf{z}})=\sum_{i=1}^{t}\prod_{j=t}^{i+1}\left(W^{T}D_{t}\right)BD_{i}h_{i}^{W}({\mathbf{z}})$
(84)

The proof of lemma 9 assure us that
$\left\|h_{t}^{W}({\mathbf{z}})\right\|=O\left(T^{6}\left\|W-W^{\left(0\right)}\right\|_{F}+t\right)$
with probability of at least
$1-e^{-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$ over the random
initialization of $f^{\text{RNN}}$. In addition, lemma B.11 together with
lemma C.9.d from Allen-Zhu et al. (2019) assure us that
$\left\|\prod_{j=t}^{i+1}\left(W^{T}D_{t}\right)\right\|_{2}=O\left(T^{7}\left\|W-W^{\left(0\right)}\right\|_{F}+T^{3}\right)$
for all $i,j$ with probability of at least
$1-e^{-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$. Now, it is well
known that $\left\|B\right\|_{2}=O\left(1\right)$ with probability of at least
$1-e^{-\Omega\left(m\right)}$ (see for example Bandeira & Van Handel (2016)),
and clearly $\left\|D_{t}\right\|_{2}\leq 1$ for any $t$. Therefore, overall
we got that equation 83 holds with probability of at least
$1-e^{-\Omega\left(\frac{m^{\frac{1}{3}}}{T^{2}}\right)}$. Finally, a simple
union bound on all the possible $d$ bits configurations and $T-d$ $t$’s proves
the bound holds simultaneously for all ${\mathbf{x}}$’s and $t$’s. ∎

Finally, we rely on lemma 8 from Wang et al. (2021) to bounds the finite width
deviation of $f^{\text{RNN}}$ from its infinite width neural tangent kernel
(Jacot et al., 2018).

######  Lemma 11.

Let $m\in\mathbb{N}$ and
$r=O\left(\frac{\text{poly}\left(T\right)}{\sqrt{m}}\right)$, then with
probability of at least $1-\exp\left(O\left(T\log
T\right)-\Omega\left(m^{\frac{1}{3}}\right)\right)$ over the initialization of
$f^{\text{RNN}}$, for all
$W,\tilde{W}\in\mathcal{B}\left(W^{\left(0\right)},r\right)$ the following
hold:

$\displaystyle\max_{d\leq t\leq
T}\max_{{\mathbf{z}}}\left(\left|f_{t}^{\text{RNN},\tilde{W}}\left({\mathbf{z}}\right)-f_{t}^{\text{RNN},W}\left({\mathbf{z}}\right)-\left\langle\nabla_{W}f_{t}^{\text{RNN},W}({\mathbf{z}}),\tilde{W}-W\right\rangle\right|\right)$
(85) $\displaystyle=O\left(r^{\frac{1}{3}}T^{10}\sqrt{m}\left(\log
m\right)\right)\left\|\tilde{W}-W\right\|_{F}$ (86)

###### Proof.

Simple union bound on all the possible $d$ bits configurations and $T-d$ $t$’s
proves the bound in lemma 8 holds simultaneously for all ${\mathbf{x}}$’s and
$t$’s. ∎

##  Appendix F Bit-Subset Parity End-To-End Negative Result Proofs

In this section, we present a theorem stating that without intermediate
supervision, for any neural network with gradients that are polynomially
bounded, one must use an exponential number of GD steps to achieve non
negligible accuracy in the above-presented task of bit subset parity.

######  Theorem 4.

Let $f_{\theta}$ be any neural-network with
$\mathbb{E}_{{\mathbf{x}}}\left[\left\|\frac{\partial}{\partial\theta}f_{\theta}\left({\mathbf{x}}\right)\right\|^{2}\right]\,=\,O\left(\text{poly}\left(d\right)\right)$171717For
any $\theta$ that is reachable by $\mathcal{A}$ with $n$ iterations.
(polynomially bounded gradients), and let $\mathcal{A}$ be any iterative
gradient-based181818See footnote 3. optimization algorithm that runs for
$n=O\left(\text{poly}\left(d\right)\right)$ iterations, and at each iteration
receives $\Omega\left(e^{-\nicefrac{{d}}{{3}}}\right)$-approximation of
$\mathbb{E}_{{\mathbf{x}}}\left[\nabla
l\left(y,f_{\theta}\left({\mathbf{x}}\right)\right)\right]$. Then, with
probability of at least $1-O\left(e^{-\nicefrac{{d}}{{3}}}\right)$ over the
target parity function, the loss of $\mathcal{A}$ will be higher than
$\frac{1}{2}-O(e^{-d})$.

This theorem follows directly from Shalev-Shwartz et al. (2017) and Shamir
(2018) and from the fact that random guessing has high zero-one loss, see full
proof below. Importantly, lemma 10 shows that $f^{\text{RNN}}$, for which we
proved our positive results when intermediate supervision exists, upholds the
polynomially bounded gradients requirement in theorem 4 above with high
probability. Moreover, section D shows that our positive results holds also
for an finite-precision gradient descent optimization algorithm, for with
theorem 4 proves the negative results. So overall both the positive and
negative proof are on the exact same setup and hence corollary 1follows.

We will use abuse of notations and sometimes identify a predictor
$h\in\mathcal{H}$ with the corresponding vector in $\left\\{0,1\right\\}^{d}$
that his $i$’th coordinate equals to $1$ if $i$ is one of the indices in the
subset and $0$ otherwise. We start by describing a measure from Shalev-Shwartz
et al. (2017) that quantifies the amount of “signal” on the underlying target
function contained in the gradient. Consider the stochastic optimization
problem associated with learning a target function $h$.

$\displaystyle\min_{{\mathbf{w}}}$ $\displaystyle
F_{h}\left({\mathbf{w}}\right)$ (87)
$\displaystyle\textrm{where:}~{}~{}F_{h}\left({\mathbf{w}}\right)$
$\displaystyle\coloneqq\mathbb{E}_{{\mathbf{x}}}\left[l\left(p_{{\mathbf{w}}}\left(x\right),h\left({\mathbf{x}}\right)\right)\right]$

where $l$ is a loss function, ${\mathbf{x}}$ are the stochastic inputs, and
$p_{{\mathbf{w}}}$ is some predictor parametrized by a parameter vector
${\mathbf{w}}$ (e.g. a neural network of a certain architecture). We assume
that $F$ is differentiable. We measure the _variance_ of the gradient of $F$
with respect to $h$, when $h$ is drawn uniformly at random from a collection
of candidate target functions $\mathcal{H}$:

$\displaystyle\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)\coloneqq\mathbb{E}_{h}\left[\left\|\nabla
F_{h}\left({\mathbf{w}}\right)-\mathbb{E}_{\tilde{h}}\left[\nabla
F_{\tilde{h}}\left({\mathbf{w}}\right)\right]\right\|^{2}\right]$ (88)

To measure meaningful learnability, we will define the expected loss of random
guessing from $\alpha\in\left(0,1\right)$ fraction of the hypothesis class
$\mathcal{H}$ as:

$\displaystyle
E^{\mathcal{H},\alpha,l}\coloneqq\min_{\begin{subarray}{c}h\in\mathcal{H}\\\
\tilde{\mathcal{H}}\subseteq
H,\left|\tilde{\mathcal{H}}\right|\geq\alpha\cdot\left|\mathcal{H}\right|\end{subarray}}\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\tilde{\mathcal{H}}\right)}\left[\mathbb{E}_{{\mathbf{x}}}\left[l\left(h\left({\mathbf{x}}\right),\tilde{h}\left({\mathbf{x}}\right)\right)\right]\right]$
(89)

As $\alpha$ approaches $1$, this measure reflects the expected loss to be
attained by randomly assigning a hypothesis from $\mathcal{H}$. We will use
this measure in the following lemma, which is a direct corollary of theorem 4
in Shamir (2018). Essentially, this addresses any iterative algorithm
(possibly randomized), which relies on an $\epsilon$-approximate gradient
oracle to optimize $F_{h}$ in eq 87. The lemma states that if the number of
iterations is not larger than
$\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)^{\nicefrac{{-1}}{{3}}}$
then with high probability, the algorithm will return the same predictor
independent of $h$.

######  Lemma 12.

Define
$\epsilon=\sqrt[3]{\sup_{{\mathbf{w}}}\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)}$
and let $\mathcal{A}$ be any iterative gradient-based191919See footnote 3.
optimization algorithm that runs for $n$ iterations, and at each iteration
receives $\Omega\left(\epsilon\right)$-approximation of $\nabla
F_{h}\left(w\right)$. Then the following holds:

$\displaystyle
P_{h\sim\mathcal{U}\left(\mathcal{H}\right)}\left[\mathbb{E}_{{\mathbf{x}}}\left[l\left(h\left({\mathbf{x}}\right),p_{\mathcal{A}}\left({\mathbf{x}}\right)\right)\right]\geq
E^{\mathcal{H},1-n\epsilon,l}\right]\geq 1-n\epsilon$ (90)

Lemma 12 above assures us that in order to prove negative learning results
regarding some task, it is enough to show it has both exponentially low
variance of gradient and high random guessing error. Now we will show both of
these for the task of learning bit subset parity presented in section 5.
Following Shalev-Shwartz et al. (2017), we start by showing that different
parities functions are uncorrelated, and hence this task has exponentially low
gradient variance:

######  Lemma 13.

For any
$\left(i_{j}\right)_{j=1}^{\frac{d}{2}}\neq\left(\tilde{i}_{j}\right)_{j=1}^{\frac{d}{2}}$
we have that:

$\displaystyle\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{i_{j}}}\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{\tilde{i}_{j}}}\right]=0$
(91)

###### Proof.

Denote by $h\neq\tilde{h}\in\left\\{0,1\right\\}^{d}$ the vectors that
corresponding to the
$\left(i_{j}\right)_{j=1}^{\frac{d}{2}},\left(\tilde{i}_{j}\right)_{j=1}^{\frac{d}{2}}$.
Then

$\displaystyle\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{i_{j}}}\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{\tilde{i}_{j}}}\right]$
$\displaystyle=\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{\left\langle{\mathbf{x}},h\right\rangle}\left(-1\right)^{\left\langle{\mathbf{x}},\tilde{h}\right\rangle}\right]$
(92)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{\left\langle{\mathbf{x}},h+\tilde{h}\right\rangle}\right]$
(93)
$\displaystyle=\mathbb{E}_{{\mathbf{x}}}\left[\prod_{j=1}^{d}\left(-1\right)^{x_{j}\left(h_{j}+\tilde{h}_{j}\right)}\right]$
(94)

Since the coordinates are independent we can swap the order of the expectation
and the product:

$\displaystyle=\prod_{j=1}^{d}\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{x_{j}\left(h_{j}+\tilde{h}_{j}\right)}\right]=\prod_{j=1}^{d}\frac{\left(-1\right)^{h_{j}+\tilde{h}_{j}}+\left(-1\right)^{0}}{2}$
(95)
$\displaystyle=\prod_{j=1}^{d}\frac{\left(-1\right)^{h_{j}+\tilde{h}_{j}}+1}{2}$
(96)

Finally, since $h\neq\tilde{h}$ there exists some $j\in\left[d\right]$ such
that $h_{j}\neq\tilde{h}_{j}$ and therefore $h_{j}+\tilde{h}_{j}=1$ and
$\prod_{j=1}^{d}\frac{\left(-1\right)^{h_{j}+\tilde{h}_{j}}+1}{2}=0$. ∎

Now following Shalev-Shwartz et al. (2017), we show that the zero correlation
between different parities implies exponentially low gradient variance.

######  Lemma 14.

Assuming that
$\mathbb{E}_{{\mathbf{x}}}\left[\left\|\frac{\partial}{\partial{\mathbf{w}}}p_{{\mathbf{w}}}\left({\mathbf{x}}\right)\right\|^{2}\right]\,=\,O\left(\text{poly}\left(d\right)\right)$
, then
$\sup_{{\mathbf{w}}}\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)=O\left(\left|\mathcal{H}\right|^{-1}\right)$
where $\mathcal{H}$ denote the hypothesis class of $d$ dimensional parities
described in section 5.

###### Proof.

We use theorem 1 from Shalev-Shwartz et al. (2017). Essentially, this theorem
shows that if the functions in the hypothesis class are uncorrelated, then the
variance is upper bounded by
$\mathbb{E}_{{\mathbf{x}}}\left[\left\|\frac{\partial}{\partial{\mathbf{w}}}p_{{\mathbf{w}}}\left({\mathbf{x}}\right)\right\|^{2}\right]$
times the inverse of the hypothesis class size.

In our case, lemma 13 above shows that:

$\displaystyle\left(i_{j}\right)_{j=1}^{\frac{d}{2}}\neq\left(\tilde{i}_{j}\right)_{j=1}^{\frac{d}{2}}\implies\mathbb{E}_{{\mathbf{x}}}\left[\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{i_{j}}}\left(-1\right)^{\sum_{j=1}^{\frac{d}{2}}x_{\tilde{i}_{j}}}\right]=0$
(97)

And therefore we have that

$\displaystyle\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)\leq\left|\mathcal{H}\right|^{-1}\mathbb{E}_{{\mathbf{x}}}\left[\left\|\frac{\partial}{\partial{\mathbf{w}}}p_{{\mathbf{w}}}\left({\mathbf{x}}\right)\right\|^{2}\right].$
(98)

. ∎

Having low gradient variance alone does not imply that learning is impossible,
it only implies that all hypotheses perform similarly. To show the negative
result for our parity problem, we must also show that the random guessing
error is high. Lemma 15 establishes this, showing that the task of learning
bit-subset parity has non-vanishing random guessing error of
$\Theta\left(1\right)$ with respect to the dimension $d$, and linear with
respect to the fraction of the hypothesis class from which the guessing
occurs.

######  Lemma 15.

Let $\mathcal{H}$ denote the hypothesis class of $d$ dimensional parities
described in section 5, and $l_{0-1}$ denote the zero one loss. then the
following holds:

$\displaystyle\forall\alpha\in\left(0,1\right)\quad
E^{\mathcal{H},\alpha,l_{0-1}}=\frac{1}{2}\left(1-\frac{1}{\alpha\left|\mathcal{H}\right|}\right)$
(99)

###### Proof.

Let $h\in\mathcal{H}$, we begin by writing the zero-one loss with elementary
algebraic operation:

$\displaystyle\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[\mathbb{E}_{{\mathbf{x}}}\left[l_{0-1}\left(h\left({\mathbf{x}}\right),\tilde{h}\left({\mathbf{x}}\right)\right)\right]\right]$
$\displaystyle=\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\subseteq\left\\{0,1\right\\}^{d}\right)}\left[\mathbb{E}_{{\mathbf{x}}}1_{\left(-1\right)^{\left\langle{\mathbf{x}},h\right\rangle}\neq\left(-1\right)^{\left\langle{\mathbf{x}},\tilde{h}\right\rangle}}\right]$
(100)
$\displaystyle=\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[\mathbb{E}_{{\mathbf{x}}}\left(\frac{1-\left(-1\right)^{\left\langle{\mathbf{x}},h\right\rangle}\cdot\left(-1\right)^{\left\langle{\mathbf{x}},\tilde{h}\right\rangle}}{2}\right)\right]$
(101)
$\displaystyle=\frac{1}{2}\left(1-\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\mathbb{E}_{{\mathbf{x}}}\left(\left(-1\right)^{\left\langle{\mathbf{x}},h+\tilde{h}\right\rangle}\right)\right)$
(102)

Since the coordinates are independent we can swap the order of the expectation
and the product:

$\displaystyle=\frac{1}{2}\left(1-\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left(\prod_{i=1}^{d}\mathbb{E}_{x_{i}}\left(-1\right)^{x_{i}\left(h_{i}+\tilde{h}_{i}\right)}\right)\right)$
(103)
$\displaystyle=\frac{1}{2}\left(1-\frac{1}{2^{d}}\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[\prod_{i=1}^{d}\left[\left(-1\right)^{h_{i}+\tilde{h}_{i}}+\left(-1\right)^{0}\right]\right]\right)$
(104)

Now, in cases where $h\neq\tilde{h}$ there exists some $j\in\left[d\right]$
such that $h_{j}\neq\tilde{h}_{j}$ . Therefore, in such cases
$h_{j}+\tilde{h}_{j}=1$ which implies that
$\prod_{j=1}^{d}\frac{\left(-1\right)^{h_{j}+\tilde{h}_{j}}+1}{2}=0$ and we
get that:

$\displaystyle=\frac{1}{2}\left(1-\frac{1}{2^{d}}\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[2^{d}\cdot
1_{h=\tilde{h}}\right]\right)$ (105)
$\displaystyle=\frac{1}{2}\left(1-\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[1_{h=\tilde{h}}\right]\right)$
(106)

Now clearly

$\displaystyle\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[1_{h=\tilde{h}}\right]=\begin{cases}\frac{1}{\left|\mathcal{\tilde{H}}\right|}&h\in\mathcal{\tilde{H}}\\\
0&h\notin\mathcal{\tilde{H}}\end{cases}$ (107)

And therefore

$\displaystyle\mathbb{E}_{\tilde{h}\sim\mathcal{U}\left(\mathcal{\tilde{H}}\right)}\left[\mathbb{E}_{{\mathbf{x}}}\left[l_{0-1}\left(h\left({\mathbf{x}}\right),\tilde{h}\left({\mathbf{x}}\right)\right)\right]\right]=\frac{1}{2}-\frac{1}{2}\cdot\begin{cases}\frac{1}{\left|\mathcal{\tilde{H}}\right|}&h\in\mathcal{\tilde{H}}\\\
0&h\notin\mathcal{\tilde{H}}\end{cases}$ (108)

∎

Finally, by combining lemmas 14,15 with lemma 12 we prove theorem 4.

###### Proof.

By lemma 14 we know that
$\sup_{{\mathbf{w}}}\text{Var}\left(\mathcal{H},F,{\mathbf{w}}\right)=O\left(\left|\mathcal{H}\right|^{-1}\right)$.
Now since $\binom{n}{k}>\left(\frac{n}{k}\right)^{k}$ for any $k<n$, we have
that
$\left|\mathcal{H}\right|=\binom{d}{\frac{d}{2}}=\Omega\left(e^{d}\right)$
_i.e._ we have exponentially low variance. Therefore, lemma 12 assure us that
with probability of at least $1-n\cdot O\left(e^{-\nicefrac{{d}}{{3}}}\right)$
the loss of $\mathcal{A}$ will be higher than $E^{\mathcal{H},1-n\cdot
O\left(\left|\mathcal{H}\right|^{-\frac{1}{3}}\right),l_{0-1}}$. Finally,
lemma 15 implies that:

$\displaystyle E^{\mathcal{H},1-n\cdot
O\left(\left|\mathcal{H}\right|^{-\frac{1}{3}}\right),l_{0-1}}$
$\displaystyle=\frac{1}{2}\left(1-\frac{1}{\left|\mathcal{H}\right|-\max\left\\{O\left(\left|\mathcal{H}\right|^{\frac{2}{3}}\right)\cdot
n,\left|\mathcal{H}\right|-1\right\\}}\right)$ (109)

∎

##  Appendix G Bit-Subset Parity Experiments Full Details

Section 5.2 in the main text empirically demonstrates that there exists a
large gap when using the commonly used Transformer architecture for learning
bit subset parity with and without intermediate supervision. In this section,
we present the full details of the experiments.

Table 1: Learning Bit-Subset Parity with Transformers results. We say that a model is better than random when its validation accuracy are higher than $60\%$. In addition, for each task we also evaluated the test accuracy after $100k$ training iteration. The reported test accuracies are of the models with the best hyper-parameters according to the validation loss. Each value after the $\pm$ sign indicates the two standard deviations over three different random seeds. | With Intermediate Supervision | Without Intermediate Supervision
---|---|---
Task Size | Test Accuracy |  Iterations until better than random | Test Accuracy |  Iterations until better than random
$8$ Bits | $100\%\pm 0.0$ | $79\pm 21.16$ | $100\%\pm 0.0$ | $185\pm 79.89$
$10$ Bits |  |  | $100\%\pm 0.0$ | $843\pm 424.22$
$12$ Bits |  |  | $100\%\pm 0.0$ |  $4.049$K $\pm 1.132$K
$14$ Bits |  |  | $100\%\pm 0.0$ |  $31.16$K $\pm 7.23$K
$16$ Bits | $100\%\pm 0.0$ | $333\pm 67.002$ | $51.82\%\pm 1.06\%$ |  $211.66$K $\pm 57.9$K
$18$ Bits |  |  | $50.16\%\pm 2.65\%$ |  $1.534$M $\pm 1.094$M
$32$ Bits | $100\%\pm 0.0$ |  $1.48$K $\pm 61.101$ | $49.87\%\pm 0.72\%$ |  $>100$K
$64$ Bits | $100\%\pm 0.0$ |  $11$K$\pm 1.154$K | $49.93\%\pm 0.43\%$ |  $>100$K
$128$ Bits | $99.96\%\pm 0.06\%$ |  $58.33$K $\pm 5.20$K | $50.71\%\pm 1.26\%$ |  $>100$K
$256$ Bits | $48.24\%\pm 2.06\%$ |  $720.16$K $\pm 83.17$K | $50.34\%\pm 0.73\%$ |  $>100$K
Table 2: Hyper-Parameters and the random seed that examined in the experiment of learning bit-subset parity with Transformers. Learning Rate |  $10^{-6}$, $10^{-5}$, $10^{-4}$
---|---
Weight Decay |  $0$, $10^{-6}$, $10^{-4}$, $10^{-2}$
Dropout | $0$
Batch Size | $32$
Warmup Steps |  $1k$2020footnotemark: 20
Total Steps |  $100k$212121For models that converged after less than $5K$ steps we disabled the learning rate warmup.
Number of Layers | $12$
Hidden Size | $768$
FFN Inner Hidden Size | $3072$
Initializer Range | $0.02$
Adam $\beta_{1}$ | $0.9$
Adam $\beta_{2}$ | $0.999$
Adam $\epsilon$ | $10^{-8}$
Validation Size | $\min(1024,12.5\%\text{ of the data})$
Test Size | $\min(1024,12.5\%\text{ of the data})$
Dataset Seed |  $27$, $67$, $93$
2121footnotetext: For models that did not converged after $100K$ steps we
continue the training until convergence. Note that even for thus models Table
1 reports the test accuracy at step $100k$.

Following the bit-subset parity definition in section 5, we randomly sampled a
subset of $\nicefrac{{d}}{{2}}$ predefined unique indices and then we randomly
sampled non-overlapping training, validation and test datasets. For
reproducibility purposes, Table 2 reports the random seeds that used for this
sampling. Then, we used the standard implementation of GPT-2 from the
transformers framework (Wolf et al., 2020) and trained a BERT-Base size
Transformer decoder model with a vocabulary size of $2$. Even though the small
vocabulary size of our model may indicate that it is too shallow for its size
(Wies et al., 2021), we still choose to use the standard Transformer-Base
configuration. See full architecture and optimization details in Table 2.
While the evaluation of a model without intermediate supervision is
straightforward, we can simply use $argmax$ over the last token logits. This
is no longer the case when intermediate supervision is used since at
evaluation time the model must create its own intermediate steps. As a result,
in this case, we need a decoding algorithm that iteratively predicates the
intermediate steps. Since we found in preliminary experiments that greedy
decoding tends to be more efficient for longer sequences than random sampling,
we choose to use it.

To complement Figure 3 in the main text, Table 1 shows the first
iteration222222Validation accuracy was evaluated at $1$K-step intervals,
except for models that converged in less than $4$K steps for which we run the
evaluation every $10$ steps. for which the model is better than random as well
as the test accuracy after $100k$ training iterations. Though “better than
random" could be defined in a variety of ways. Figure 4 illustrates a typical
learning trajectory and demonstrate the insignificant differences in
definitions due to the observed grokking phenomenon (Power et al., 2021). For
each task we repeated the task $3$ times with different dataset seeds, and
perform grid search over the hyper-parameters in Table 2. Table 1 reports the
mean and standard deviation test accuracy of the best hyper-parameters
according to the validation binary cross-entropy loss, where we break ties by
choosing the model that converged faster. As excepted, without intermediate
supervision, the Transformer models can not learn beyond random guessing tasks
with more than $18$ bits. In contrast, with intermediate supervision, the test
accuracy is almost perfect even at $128$ bits.

Figure 4: Illustration of a typical bit-subset parity learning trajectory. In
these tasks we observed a grokking phenomenon (Power et al., 2021) where very
soon after the validation accuracy became higher than random level it also
became almost flawless (accuracy $>95\%$). Therefore, successful learning is
not sensitive to the exact cutoff.