Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks
Authors: Noam Wies
Yoav Levine
Amnon Shashua
Venue: ICLR 2023 poster (2023)
Keywords: Language Models
Generalization
End-to-End
Composition

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

Published as a conference paper at ICLR 2023
SUB-TASK DECOMPOSITION ENABLES LEARNING IN SEQUENCE TO SEQUENCE TASKS
Noam Wies, Yoay Levine & Amnon Shashua
The Hebrew University of Jerusalem
[noam. wies, levine, shashua ) acss.uuji.ac.
ABSTRACT
The field of Natural Language Processing (NLP) has experienced a dramatic leap in capabilities with the recent introduction of huge Language Models (LMs). De- spite 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 composite problems that were demonstrated in variety of domains. An effective mitigation is to intro- duce intermediate supervision for solving sub-tasks of the compounded problem. Recently, several works have demonstrated high gains by taking straightforward approach for incorporating intermediate supervision in compounded natural lan- guage problems: the sequence-fo-sequeeec LM is fed with an augmented input, in which the decomposed tasks' labels are simply concatenated to the original input (see figure I] In this paper, we prove positive learning result that moti- vates these recent efforts. We show that when concatenating intermediate super- vision to the input and training a input, unlearnable composite problems can become learnable. We show that this is true for any family tasks which on the one hand, are unlearnable, and on the other hand, can be decomposed into polynomial number of simple sub-tasks, each of which depends only on O(1) previous sub-task results. Beyond motivat- ing contemporary empirical efforts for incorporating intermediate supervision in sequence-to-sed to-suueencee language models, our positive theoretical result is the first of its kind in the landscape of results 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 impossible without intermediate su- pervision, while our result is positive, showing that learning is facilitated in the presence of intermediate supervision.
model on this modified
INTRODUCTION
Large-scale language models such BERT (Devlin 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 some problem-faal ffmiliiis 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. (22TT: Press 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 al. (02T) 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- linglinguistic domains. A leading experimental approach for ad- dressing 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 easily solved by anride-anddcooguer strategy. Beyond position papers, specific examples were

---

Published as a conference paper at ICLR 2023
John and split apples between us, he gave son. How many apples does have now?
John and I split 12 apples between How many apples does he have now?
John had apples and he gave to his son. How many apples does he have now? 5
The final answer is:
Sequence=
Question
Evidence
Final answer
An illustrative example of the prominent method for introducing sub-task decomposi- tion and intermediate supervision for math word problems (Ling et al., 2017, Cobbe et al., (021). Intermediate sub-tasks and their labels are concatenated to the original task's input to form new input sequence. At training time, the likelihood of the entire sequence following the original input maximized conditioned on the input, and at test time only the original input is given to the model.
Figure 1:
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. (022), math word problems (Piekos) al. [022]] Wei al., 2022), and programs execution (Nye et al. 2022). The go-to architectures in sequence-to-sequence models over text. 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 imput sequence, on which the sequence-te to to-sequence LM is trained. This approach has recently been widely adopted, e.g., by Rajani et al.
this domain are powerful language models, which are trained
(2019) Cobbe al. (2021); Piękos et al. (2021);
Recchia (2021): :: Nye et al. 2 Wei et al. (2022) Zelikman et al. all. (2022). Figure Iillustrates this approach for math problems, as done in Ling et al.
2017); Cobbe et al. (2021). These works show models with concatenated sub-task decomposition supervision
that training sequence-to-squeene
significantly improves the results when compared to training the same model without the interme- diate supervision. For example, Nye et al. (202)) show > 99% accuracy for 8 digits addition when concatenating intermediate calculations to the input, while the vanilla accuracy without intermediate supervision is around ~ 35%.
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 netral-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 (ec We show our results for sequential models, integrating the intermediate supervision in the language domain. In this formulation, a learner learns predict a sequence composed of the task inputs 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., (202)) and prove that with intermediate sub-task supervision, even a simple sequence-to-sequeece 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-Shward 2016) to show that in the absence of intermediate supervision, there exist efficiently decomposable tasks that are unlearnable with polynomial time learning algorithms.
manner that mimics the above cited successful empirical approaches
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-
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 I's in certain unknown subset of 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
2

---

Published as a conference paper at ICLR 2023
made possible. As result, show an exponential gap between the end-to-end and decomposition- based neural network learnability of the bit subset parity problem.
Next, 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 P time complexity class, 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 (016) 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 present.
Our main result can be stated as follows:
Theorem 1. (Informal) There exists 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 O zero-one loss with number of gradient updates that is polynomial d,
On the other hand, when supervision regarding sub-task is missing, then for any polynomial time learning algorithm and (constant) the zero-one loss will be higher than 1/2
To summarize, the main contributions of this paper are:
1. We show the first positive result that guarantees neural networks learnability in the presence of intermediate supervision for problem that is unlearnable without it.
2. We do in the soquence-to-sqqeene setting that is currently used for applying state-of- the-art language models on complex multi-hop tasks in NLP.
3. We show that with sufficient intermediate supervision this sequence-to-sequere setting allows learning any function in the 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 hypothesis class and proves that it can be learned with our sequence to sequence model. Section 5 concrete example, and demonstrates that the task of learning bit-subset parity with sequence-to-sqqueme models can be Iearned with sub-task decomposition and the corresponding intermediate supervision. Finally, in section 6 we generalize the positive results any function in the P time complexity class, thus establishing main result.
2 RELATED WORK
The concept of how learning can be enhanced by guiding learner through intermediate tasks is an old one, dating back to animal training by shaping (Skinner 1958 Peterson 2004] Krueger & Dayan 2009). Since then, 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. Nosss,Ngettt al. (1999) established necessary and sufficient conditions for reward shaping 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 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- soddto--nd learning of multi-hop problems is un- feasible 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 classi- fication and parity tasks, proving that the end-to-end approach does not converge in a polynomial
3

---

Published as a conference paper at ICLR 2023
number of gradient updates. They do show that when intermediate supervision is provided, the gra- dients have a much higher signal-to-nois 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 (216)) proved an exponential gap between end-to-end-basee plexity and the decomposition-basel verification sample complexity. However, again, explicit setting in which providing intermediate supervision for training actually improves the situation to 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 some compounded cases.
verification sample com-
3 THE ANALYZED
LEARNING ALGORITHM
A recent successful empirical approach for solving compounded natural language problems (Ling
et al. 2017 Rajani et al. 2019) Piekos et al., 2021| Recchia 2021 Cobbe 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 d-bit input string x, with S denoting the string of intermediate step results, we denote the combined input sequence combined output sequence as y, defined in a standard autoregressive fashion by 3/ = 24+1 (see figure 2 for
Concat S}, and the
8 example). Training and testing follow conventional requence-to-sequenne model protocol: At training time, 2ạ for / > d will be the ground-truth sub-task result yt-1 (a practice sometimes referred as "teacher forcing" (Williams & Zipser 1989 ), and at test time, 2t for t >> d will be the model's s prediction at time 1.
We analyze the classical Elman recurrent neural networks (Elman 1990) with ReLU activations as our sequence-to-sequencee model. Given an input sequence z of length T = d + len (S) as defined above, the architecture fRNN computes:
Vt [T] he (z) = ReLU (W + Ae
Vt E [T] JANN (z) = BTTh (z)
(2)
ho (z) ReLU (Mo)
where en, el E IR22 are one-hot vectors, E Rmxx translates the input to the hidden dimension m, W E puxm is the learned hidden weights matrix, B E I is the output weights vector and Mo E RT is the initialization of the hidden state.
We will use the binary cross-entropy loss over output locations for 2 d, i.e., our loss ignores the architecture's 's prediction of x and depends on its prediction of intermediate labels and final outcome:
1 T
(y)s)
log (1 + e vcs))
(4)
Algorithm [ below describes the analyzed training procedure of our sequence-to-sequeeee model. This algorithm describes straightforward SGD training procedure where, for simplicity, we analyze a variant that updates only the hidden W weights while keeping A, B, MM frozen at initialization. This amounts keeping the input, output and the the core recurrence operation to perform the task while complying with these frozen components.
hidden state untrained, and training only
COMPOUNDED SEQUENCE TO SEQUENCE LEARNABILITY
In this section, we present hypothesis class and prove for it that the above described "teacher forcing" (Williams & Zipser 1989) of intermediate supervision at training time with algorithm provably leads to generalization antee 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.
polynomial sample complexity and gradient updates. This guar-
Forr clarity, we wrote Vt zi+1 although the inputs domain in our model was (0. 1) while the output domain was 1- and hence y/ 2- (zt-1 - 1/2)
4

---

Published as a conference paper at ICLR 2023
Algorithm 1: Training fRNN with SGD
Data: Data set D, learning rate Initialization: The entries of W A, Mo are i..d. generated from .N (0, m) The entries of B are i.i.d. generated from (00, )
for i 2, 3...n do
Randomly sample (x,, y4) from the data set D. W = W(+-) - V/V sy((y, fRNN, fRNN,WO-R w (2))).
end
In order to analyze the teacher forcing technique. we begin with an important observation. Essen- tially, 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 zq Yt-1 the ground truth input training time, and by 2 ft-1 FRNN.W (z the iteratively predicted input at test time. Then, for any W the following holds:
Ex [lo- fT FRNN
RNN.W
(z (z()r)
S Ex
Σ
1--1
Jc JeNN (zmmin)
.RN.W
(5)
Proof. Clearly, for any x when fRNN,W (zimin) solves all of the sub-tasks correctly we have that zlest giiin and therefore they have the same zero-one loss. So it is enough to upper bound the probability that fRNN, (z (z!ran) is erroneous in any sub-task. Now by definition, for any t the zero-one loss the f'th location is equal to the probability of wrong prediction at this location. Therefore, by the union bound, we get that the sum the zero-one loss over all the locations is upper bounding the probability of ,RiN, W (zirain) make an error 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 long as I' is polynomial in d.
increase by factor of T - d but this increase is relatively modest as
Lemma D above assures us that it is enough find an hypothesis class for which algorithm con- verges and generalizes when we do have the ground truth results of the previous sub-tasks, in order prove that the teacher forcing technique works. As candidate for such a hypothesis class, we consider tasks for which the output at each location d < t < T can be written as sign of composition of linear functions (represented by below) of at most N < T input locations ji.... S t, with
polynomials activations 2/2 (x) = Ei
deg(()))
C2
w(()
PA SEtST h4 (z) sign
1/2
w())]]
Cany
In order to prove convergence and generalization results, we will measure the complexity of fune- tions in the above hypothesis class by function ó (T, N), described formally in appendix [A] Importantly, @ (T', N) polynomial both T and max,,; (at,al- while exponential in both max, deg (v/2) and N. We will denote by W.NT the hypothesis class described in eq
Now, with this hypothesis class, we can combine lemma with theorem in Wang al. (202 They study the learnability of RNNs for binary classification task task:" without intermediate supervi- sion, and prove that algorithm [ is capable of learning function where the final answer y have low complexity e (T N).
They also discussed the case where y is sequence, however, in their case it was considered part of the task, unlike where add intermediate steps method of supervision.
5

---

Published as a conference paper at ICLR 2023
(a)
1efterightt
tofteright
1 jeft-right
X
X
(b)
1% 1xg
1 1
Sequeeicc Sequerice Model
X1 7/2
Xg
X;
X
1 AAgg
1 Nog +/g
2
3
4
5
6
10
Illustration of the proposed input and output for learning the = bit-subset parity problem with sruuecceto-seqqeence models.
Figure 2:
Theorem 2. Denote by zea RNN,W (2!c1) the iteratively predicted input at test time, and let
(( ((T..),)+)OR( (
2
6, > 0. Assume Algorithm for for δ
iterations with learning
rate myn then there exists m poly (n,8-117 such that if m m² then for any h Ho(T,WNN) with probability least 6 over the randomness in Algorithm 7 the following holds:
Ex lo-1 (U. S BRNN, (z <c
where W denotes the output of Algorithm ! at the i i'th iteration and lo-1 1 is the zero-one loss.
Note that sections of the appendix extends Shooremfor 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 HoCT..NN) with low complexity & (T, 1b N).
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 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 d/2 randomly predefined unique indices i,,..., 14/2s our goal is to
train a predictor mapping x E {0, 11d to y (-1ドE Zig where uniformly distributed, In words, indicates whether the number of I's in the given subset of coordinates of x is odd or even.
We analyze this task "multi-hop" task by decomposing into natural intermediate sub-tasks: parities of subsets of the predefined input subset Z ..... Piazz' Concretely, assuming for simplic- ity that d/2 is power of and beginning with only adjacently indexed input bits at a time, we recursively treat the parity of every two adjacently indexed subgroups as an intermediate task. sub-task decomposition of our parity problem. The leaves of the tree of intermediate labels T are =1 +0 +..,............................ ..... Fidp2-1 trid/2 and each node in the tree represents the sub-task of caleulating the parity function over its descendants.
Figure a illustrates this binary
In order to fit into the sequence-to-ssqquence setting of section 3 we translate our imaginary tree of intermediate labels T into sequence intermediate labels by inverse-BFF like tree traversal, and then concatenate the sequence S after the input x. An exact formulation of the mapping from tree T sequence of intermediate labels S is given in appendix

---

Published as a conference paper at ICLR 2023
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 requence-to-sequees formulation of the bit-subset parity target function, which includes the intermediate labels sequence defined above, can be written as multivariate function where each of its outputs is simple low degree polynomial of at most O (1) inputs bits. We show that this is indeed the case, L.e. that all the parity target functions comprising the intermediate supervision to problem belong to H (see section[4) with N, max, deg (vx); max,, |0t,a| 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 hr (x) clearly depends 4/2 bits, and therefore will require N 4/2, that leads to exponential complexity & (T, v/, N) 5 (e*). 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 d polynomials:
Lemma 2. There exists degree two polynomial vb (x) = u2ax + axæ + ag with bounded coefficients
vi
[g]] < 10 as well as w E RRA such that:
V2 22 E (0,1) # ((1 W
e22 )))
e:1
21 22
[[]]
21 #1
Proof. We will use w to sum the first coordinates of 02 0zg. and use polynomial interpolation to
find a degree two polynomial & that interpolates the 21 22 0, 21 see full details in appendix B
7 22
21
= 22 1 points,
The above lemma implies that all of the target functions in our defined intermediate supervision belong to V.N) for ø (T, v, .N = = (d). Therefore, together with theorem 2 it assures that when intermediate supervision is available, Algorithm can learn bit-subset parities with polyno- mial 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 neural network, will use the results of (Shalev-Shwartz al. (2017) to establish an exponential gap between the end-to-end and decomposition neural network learnability?
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 O zero-one loss with number of gradient updates that is polynomial in d!
* On the other hand, when supervision regarding sub-task is missing, then for any (constant) > with high probability over the target parity, the zero-one loss will be higher than 1/2 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 al. (0017). See full details in section F at the appendix.
5.2 BIT-SUBSET PARITY EXPERIMENTS
In section 5.I 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. (017) architecture. We trained a series of models while varying the input sizes from 8 bits to 256 bits. For each input size,
'Not that the negative result holds only for full gradient descent and does not hold for stochastic gradient descent, for which Abhe & Sandon AAhhe using complex non-random initialization.
Ahhe et al. (021) show that parities are efficiently learnable when

---

Published as a conference paper at ICLR 2023
trained BERT- sized Transformer model for 100k iterations with and without intermedi- ate supervision. The intermediate supervision was introduced exactly as described in the previous subsection, see Figure 2 for illustration. See full technical details of the training apparatus in appendix
Figure clearly shows that in a practical setting, using common Transformer networks, 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 2M steps), while it easily learned the task in the presence of inter- mediate supervision. Overall this experiment, performed on the same task on which we prove our theoretical results, reinforces their relevance to common Transformer architectures.
UNIVERSALITY OF DECOMPOSITION BASED SEQUENCE- SROUENCE-TO-SSAE TO-SEQUENCE LEARNING
In this section, we prove our main result (outlined in the introductory theorem T). On the one hand, we generalize the positive results of section 5.1 by showing that when sufficient intermediate su- pervision is available, neural network class. On the other hand, we rely on existing works (Valiant 1984 Goldreich et al.) 1986 Daniely & Shalev-Shwartz/ 2016) show that under either standard cryptographic assumptions tational complexity hardness assumptions, there exist functions in the P time complexity class that cannot be learned by any polynomial time learning algorithm without intermediate supervision.
efficiently Iearn any function in the P time complexity
compu-
We begin by defining the decomposition of any function ʃ in the 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 boolcan circuit with polynomial size. We will denote by G = =V, F)) the directed acyelic graph associated with such a circuit, and by L. the logic gates of each vertex e. Furthermore, since both the"AANI and "OR" logical gates can be decomposed into boolean circuit with binary-tree like structure, we may assume that the input degree of each vertex is O (1).
Now, in order to fit into the sequence-to- sequence setting of section 3 we define the in- termediate labels sequence for any f. Basi- V will represent cally, each non-leaf vertex an intermediate task with its ground-truth label determined by lu, and will cal sorting of G in order to translate G into sequence of intermediate labels S with length T := |V| (see figure 2 for a concrete exam- ple of this abstract construction strategy). Im- portantly, as in the bit-subsets parity task, T is polynomial in d.
Stops Unatil Tewrning
1004
topologi-
10k
1k
With Inceruedate Supertsion
Without Encemstitte Sapersito
=2 Std
100
32
62
128
256
Number Bits
In order to show our generalized positive re- sult, theorem @ motivates us to prove that our sequence-to-sequeee
Figure 3: The number of steps until 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 arbi- trary, in practice we observed a grokking phe- nomenon (Power ter the accuracy became higher than random level also became almost perfect (accuracy > 95%).
formulation of any func- tion ʃ in the P time complexity class, which includes the intermediate labels sequence S de- fined above, can be written as a multivariate function where each of its outputs is simple low degree polynomial of at most O (1) input bits. Lemma 3 below shows that this is in- deed the case, i.e., that all the target functions comprising the intermediate supervision our problem belong to H HoTT.NNN (see section 3) with N, max; deg (zb2), max,, las,il that do not grow with d.
2222 where very soon af-
'Wit the exception of the 16 and 18 bits tasks without intermediate supervision, for which we increase the number of iterations 300K and 2M respectably in order try and successfully learn the task.
8

---

Published as a conference paper at ICLR 2023
Lemma 3. For any logical gate L. 10, + {0, with N = (1), there exists O (1) degree dey(v)
polynomial &b (x) = 2i=0 a with bounded coefficients max; |a,| = O (1) as well as w IR2N
such that:
, AN E (0.1)
w |wl
tu (2I,...,ZN)
Proof. We will use w to uniquely represent each possible combination of 20: 20..... NN an N bit real value number, and use polynomial interpolation to find a 2 -degree polynomial i that interpolates the = 2N 0 follow from taking maximum over all possible L, logical gates. see full details in appendix B
2N 1 points. Finally the O (1) coefficients boundedness
The above lemma implies that all of the target functions in our defined intermediate supervision belong to N,(T, for @ (T, db, N) O (d). Therefore, together with theorem 2 it assures us that when intermediate supervision is available, Algorithm can learn any function in the 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 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 hard- ness 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 to-sequence model can get arbitrarily low O zero-one loss with number of gradient updates that is polynomial d,
On the other hand, when supervision regarding sub-task is missing. then for any polynomial time learning algorithm and (constant) > 0, the zero-one loss will be higher than 1/2
Proof. Follows directly by combining theorem 2 and lemma 3 with either the negative results in Valiant 1984); Goldrrich al. (1986) or in Daniely & &Shalev-Swwatz/ (016))
7 DISCUSSION
In this paper, we show for broad family of functions an exponential gap between learning algo- rithms that rely on intermediate supervision and algorithms that do not rely on intermediate super- vision. Across domains and architectures, there has been 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 which the core architectures are strong sequence-to-sequenee 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-sequene architecture is feasible expect such simultaneous compounded learning to be useful. In this gard, we view our work as providing timely theoretical feedback to the rapid empirical advances in this field.
models. We show that even with a simple requence-to-sequeee
We proved universal learnability results when sufficient intermediate supervision was provided. A fundamental question is what happens when limit the amount of sub-task supervi- sion. For the task of bit-subset parity, we demonstrated that supervision regarding O (d) sub-tasks can yield an exponential advantage. An interesting question that we leave open for future work is whether there exists similar advantage with only O (1) sub-tasks.
Limitations:
In addition, while our results show an exponential gain, is still unclear which sub-tasks are solvable by end-to-end methods, and which tasks require decomposition? Interestingly, recent study (Abbe) jet al., 2022) addressed exactly this question for lay-r hidden networks the mean-field regime. However, our understanding of this question for practical architectures is still very limited.
TThis maximum exists since there finite number of possihle functions from {0, 13. into {0, 1).

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
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///gthub..oo//HUU Deep/sub_tadd stasubbb__kk____eee llsssaakkcoosssiittiiiii
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
We thank Eran Malach and Shai Shalev-Shwarte for helpful discussion on our stronger negative results, well Lifu Wang for clarifying Wang al. (202T). This research 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
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 Asso- wewpeediiiinnn.e.ir.p.e.. cc pctpppppee/222///1eeee
ciates, Inc., 2020. URL TTeffe-9B22256cccdeeeeee1111...2 Papere..
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, J.d Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
https::/openreviier net forum 1d= TZPid2S3r_2
Emmanuel Abbe, Euric Boix Adsera, and Theodor Misiakiewicz. The merged-stairease property: 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.
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 As- sociates, Inc., 2019. URL BRLLhttps:: //tpe//ee//////////////.. httpg/////nttts///r//eeeieie wwwpeiinnnnnuuuuuueee inpurrpps httppppsc..c/ppeee//////eeeeeee htt.pp/wwwcc.........oooooooooap
pdf
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):2499-2566, 2016.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1876-1900. Curran Asso- ciates, Inc., 2020. URL htttpss:/pproceedingg..t neurips ottp://ccc......e...r.....ooopea 1457c0d6bf cbl.cccc455 967749778 8ofb8accllcc..cc 42 424644-64422 Paper..ppappppp..... pdf
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. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1428 1439. Curran Associates, Inc., 2020. URL 3ee1 34311e133314444455555555 2tt.://00000..............eeeee.
hee.eeeriiiinnn..nneeeeeee.... www.wnnuui..... cc/
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jemy Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint 10.:22100.1418,, 2021.
10

---

Published as a conference paper at ICLR 2023
Amit Daniely and Shai Shalev-Shwarte Complexity theoretic limitations on leamingg dnf's. In Vi- taly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. $15-830. Columbia Uni- versity, New York, New York, USA, 23-26 Jun 2016, PMLR. URL https: /eltsa:/ppi httttp::/pprcceeingge m wwt.peess/v99///niiie
html
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 Linguisties: Human Language Technologies, NAACL-HLT 2019, Minneupolis, MN, USA, June 2-7, 2019, Volume (Long and Short Papers), pp. 4171- 4186. Association for Computational Linguistics. 2019. doi: 10.18653/v1/n199 1423. URL
https: /wi..ii../// www.oo..........o.. ptrg/10.11653... v1 1//nnn 1423
Jeffrey L Elman. Finding structure in time. Cognitive science, 14(2)119--11, 1990.
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. Transac- tions of the Association for Computational Linguisties (TACL.) 2021.
Tobias Glasmachers. Limits of end-to-end learning. In Asian Conference Machine Learning, pp.
17-32. PMLR, 2017.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How construct random functions. Journal of the ACM (JACM), 33(4):792-807, 1986.
Ç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: // /mlr. orc//papers/v17/qgllooe www.heee...ee.....e.eeeee htmml
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemnl: Convergence and gen- cralization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve ar- bitrarily small test error with shallow relu networks. In International Conference on Learning Representations, 2020. URL https://openrevview net. /wteeeeeffruueee Flt.mmmm.--yyyyerrrr
Ashwin Kalyan, Abhinav Kumar, Arjun Chandrasekaran, Ashish Sabharwal, and Peter Clark. How much coffee was consumed during EMNLP 2019? fermi problems: A new reasoning chal- lenge for AI. In Proceedings of the 2021 Conference Empirical Methods in Natural Lan- guage Processing, pp. 7318-7328, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguisties. doi: 10. 122113611222211comm wwwp/ppppeemmm--eemee//mmmm main.582. URL https::/accaanthhloooy
582)
Jonas Karlsson. Task decomposition in reinforcement learning. In Proceedings of the AAAI Spring
Symposium on Goal-Driven Learning, Stanford, CA, 1994.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM
(JACM), 45(6):9331006, 1998.
Kai A Krueger and Peter Dayan. Flexible shaping: How learning in small steps helps. Cognition, 110(3):380-394, 2009.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale gen- eration: Learning 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-100 URL ht http:///aaaaantoooo.oooooooo.. /
1015
Jaachng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannanch Hajishirzi. Generated knowledge prompting for commonsense reasoning. In Proceed- ings 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 Lin- ht
guistics. doi:
acl lll..ng..22 225

---

Published as a conference paper at ICLR 2023
Bhaskara Marthi. Automatic shaping and decomposition of reward functions. In Proceedings of the 24th International Conference on Machine learning. pp. 601-608, 2007.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations:
Theory and application to reward shaping. In Ieml, volume 99, pp. 278- 1999.
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 Au- gustus Odena. Show your work: Scratchpads for intermediate computation with language models. In Deep Learning for Code Workshop, 2022. URL https::/ id HBix2idbbbq
net met/forunt
Gail B Peterson. A day of great illumination: Bf skinner's discovery of shaping. Journal of the experimental analysis of behavior, 8273):317-328, 2004.
Piotr Piçkos, Mateusz Malinowski. and Henryk Michalewski. Mcasuring and improving BERT's s mathematical abilities by predicting the order of reasoning. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 11th International Joint Con- ference on Natural Language Processing (Volume 2: Short Pupers), pp. 383-394, Online, August 2021. Association for Computational Linguistics. doi: 10. 10.183/111/2221 1
acl-shortt.49 URL
htttp::/accaamthooory.cccs wwwpellooy.oog/2000 wwt.:22....1sssoohr....e.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Gener- alization beyond overfitting on small algorithmic datasets. In ICLR MATH-A/ Workshop, 2021.
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: org/abs/ 03350
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 Kun- coro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Men- sch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson 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, Si- 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.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with unified text-to- text transformer. Journal of Machine Learning Research, 1667 2020. URL http:
//jmlr. wwt.llrrog/ppapps//2222 w22.0//0222220000.22200 html
Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. Explain yourself!
leveraging language models for commonsense reasoning. 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. 1..118653/1//11-1111 1487. URL hetps: w/aclaatholooy.orgg////o wwtp://gg//////a/..ppp
Gabriel Recchia. Teaching autoregressive language models complex tasks by demonstration. arXiv preprint arXh::2109.02102. 2021.
Shai Shalev-Shwartz and Shai Ben-David Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
12

---

Published as a conference paper at ICLR 2023
Shai Shalev- Saalar-S and Amnon Shashua. On the sample complexity of end-to-end training semantic abstraction training. arXiv preprint arXiv:1604.06915. 2016.
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.
Ohad Shamir. Distribution-specife hardness of learning neural networks. The Journal of Machine Learning Research, 19(1):1 111-111-1331 2018.
M Sipser. Introduction to the theory of computation. 3th. Cengage Learning, 2013.
Burrhus F Skinner. Reinforcement today. American Psychologist, 13(3):94, 1958.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11): 1984.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Lifu Wang. Bo Shen, Bo Hu, and Xing Cao. On the provable generalization of recurrent neural net- works. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. sociates, Inc., 2021.
Curran As- http:::::s/pppppeeeeee neur ips wttpp/pptp//222//1lee..... Paper.pdl
Po- Po-Wei Wang. Priya Donti, Bryan Wilder, and Zico Kolter. Satnet: Bridging deep learning and log- ical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, pp. 3545-6554 PMLR, 2019.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoe V Le, and Denny Zhou. Chain of thought prompting clicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances in Neural Information Processing Systems, 2022. URLhttps: /ttp:::::///peeeeeieee net. Corum?ld= VJ01MeSB_
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
:ttps:://proceedings www.mrrreeeee.... wtt.ppesssv.////eee.e wttps///ww///weeee.... html
Ronald Williams and David Zipser. learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-220) 2800, 1989.
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 Gug- ger, 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 Online, October 2020. As- sociation for Computational Linguistics. URL httph:tpp/// /wwwww...../....o//// aclweb.
2020. emnlp- demos. 6
Eric Zelikman, Yuhuai Wu, and Noah D. Goodman. Star: Bootstrapping reasoning with reasoning, 2022.
Yuexiang Zhai, Christina Back, Zhengyuan Zhou, Jiantao Jiao, and Yi Ma. Computational bene- fits of intermediate rewards for goal-reaching policy learning. Journal of Artificial Intelligence Research, 73:847-888 896, 2022.
13

---

Published as a conference paper at ICLR 2023
A COMPOUNDED SEQUENCE TO SEQUENCE LEARNABILITY DETAILS
We start by formally defining our sequence-to-sequene functions complexity measure as:
Φ (T, = (riGts deg(vr) C2N C2N max deg (th+) J.
max |ar
(10)
2,2
Where C is some constant.
Now prove lemma I 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 the zero-one loss for miin ie,, the right hand side in eq 5 Clearly, for any when fRNN, W (atii))) solves all the sub-tasks correctly we have that gest
z train and therefore
,RNN.W (z!est) O. So it is enough to upper bound the probability that fRNN,W (z!aan) 10-1 y, JT
makes an error in any sub-task by c. But by the zero-one loss definition, for any we have that:
Px (JRNN,W (zmmi)) o ve 1Ex [lo- (Br.
Jt
.RNNWW W
(z (2!iin)
(11)
And therefore Σt Px (JRNN.W (2train) + (e)) Finally, by the union bound we got that
T Px
Px 3d ESST fe IRNN.W (2!miN) # 1/1 S
(RNNN,W (z.trin) F y1 =E
(12)
t=d
B SUB TASKS LEARNABILITY PROOFS
In this section we prove lemmas 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-sqqueree models. Since sequence-tee geuuence-t--equune io-sequence models expect their inputs be sequences, we will translate the tree described in section into a sequence by inverse BFS like tree traversal, and concatenate the result sequence after x. Therefore, our inputs sequence includes all the d variables in x, together with all the sub-tasks decomposition nodes in the binary tree except the root (that represent y). So will have an input sequence length T that is equal to:
d leaves = dd - 2
T = d + nodes in full binary tree with 4
(13)
And the ground-trus -tuth sub-task results are recursively defined by:
(2 - t < 5d
Vt 2 d Be (-1) "x(-- )+ ( +4) else
(14)
For > d, at training time, & will be the ground-truth sub-task result yt-1. At test time 2 will be the model prediction at time t 1:
1 < d
Yt [T) 2
2 2
sign (JENN 21
24-1
t d A test
(15)
T+
t d A training
Note that fRNN causal model, i.e. f RNN does not depend on 2t, for any to > f1, and therefore eq [5 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 the hypothesis class define in e
14

---

Published as a conference paper at ICLR 2023
1
0
Proof. Define w ==
then
V2
1
0
V2
21 0 22 = 0
w
21 + 22
(16)
||w|]
ez2
V2
0
21 1 A 22
Therefore, is enough to find eb such that
+ (0) v/ (v2)=1
-
1 = =-1
(17)
Finally, we will use Lagrange basis functions to find the required polynomial and get:
3 (2)
v2
z v2
0
v2
+
) / - .)
==-0 0
2 v2
0
v2
1
v2
V2 1
/
v2
V2
v2
(18)
8
1
(= - v2)
+
2 v2
+ +3
1
(19)
/2
V2
2
2 z +
+
+
3z2
(00)
2
v2
v2
9
7
+1
(21)
2
V
Now we prove lemma 3 from the main text. Essentially this lemma shows that also our intermediate steps for any functions the P time complexity class belongs to the hypothesis class define in eq 6
Proof. Denote a (21,..., 2N) = N-1
2
12.=0 the function that converts N bits to their binary
Zi=0
20
0
21
string, and define w V 1-
3
0
then w is unit vector that represents 21. 2N as N
2N
0
Cz
bit numbers
w
a (Zi,..,, ÆN). Now, we can use the Lagrange basis functions
Tw
eax
to find the required polynomial:
(xx)
Σ
So (a EN)
II
x a (21...... EN) a (2) ..,, 2N) - a (21, ;,N
(#i.... (C)....))))
(22)
Finally the O (1) coefficients boundedness follows from taking the maximun over all possible fu functions.
This maximum is exists since there is finite number of possible function from {0, 13.2 into {0, 1}.
15

---

Published as a conference paper at ICLR 2023
C EXTENSION FOR SGD WITH FINITE PRECISION
In this section, we prove theorem from the main text holds also for algorithm 2 which a finite- precision variant of SGD We will follow the proof in Wang et al. (2021) while taking into account the finite precision gradients.
Algorithm 2: Training ,RNN with finite precision SGD (an finite precisio variant of algorithm) 1
Data: Data set D, learning rate 7). finite precision Initialization: The entries of W A, Mo generated i..d from No, )) The entries of B are generated i.i.d. from [00, ).)
for i 1,2,3..... 3...n do Randomly sample (x,, y+) from the data set D. Get arbitrary o-approximation of the gradient:
G( E _ V Vwo-nn(y:: f gRNK,W( (z:)) 0).
Update weights:
W (((+1) - G
end
We begin by stating theorem 2 Wang al. 2021 with our notations:
Theorem 3. Let 5 O, and assume algorithm 7 for iterations with learning rate my
Then there exists m poly (,,8-1T) such that if m > m then for any h E HoOTTWNN) with probability at least 8 over the randomness in algorithm
[ the following hold:
1
ΣΣ 1--1 JE RRNN wo (2)) < (TT,
(T (5 (
log 1
Ex
+0
8
(23)
d)
Vn
where W11 denote the output of algorithm Dat the i i'th iteration and lo-1 is the zero-one loss.
Clearly when using infinite precision SGD theorem follows from theorem 3 and lemma 1 by simple algebraic manipulations. Therefore, for proving theorem - with finite precision gradient based optimization, is enough to modify theorem's 's proof to analyze algorithm 2 that uses finite precision gradients, instead of algorithm that uses full precision gradients.
While complicated, WWan al. (2021)'s h's proof for theorem can be divided into two high-level guments. The first argument measure the complexity of the learned hypothesis class with respect to random initialization of fRNN (lemma 6) And the second argument a generalization bound for al- gorithm 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 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) I and the rest the second argument (lemma in Wang al. (2021) remain unchanged.
Lemma 4. Let E N, and denote by Le (W) = (y(1), PRNN,W (z())) the training loss. Suppose such that R O (poly (T)) Ω (T16) and Le (W*) I=
there exists W* B10 W(0)
R /m
x
Then for any 8 > 0 there exists m * = poly (n, R, T, 1-) such that if m m then with probability at least å algorithm 2 with m and finite precision a = (+) will output:
Ex
) n )
n2 [T
ΣΣ (=d
10-1
(yL.
y/.
RRNNN RNN, Wio
(2)) <
R8
log
(24)
d)
See section D for the extension of the proof to algorithm 3 that is based GD. 'The ball is with respect to the distance that defined by the max matrix norm, i.e. the elementwise distances are most 0T
CCombined with Remark in Wang et al. (2021)'s supplementary materials. In addition, for simplicity, we state a 1/v= convergence rate as opposite to the linear convergence rate in Wang et al. (201)).
The ball is with respect the distance that defined by the Frobenius matrix norm.
16

---

Published as a conference paper at ICLR 2023
Proof. We begin by showing that with high probability the initialization of fRSN any it- eration i S of algorithm 2 the distance of the learned hidden weights matrix W()) from its initialization point W(O) is not too large. As results we will get that the assumption of lemma uphold, and therefore its upper bound of the deviation from linearization valid.
By the triangle inequality for any 0 S < n we have that:
[ Wlo)
W(b+1) - w(lk) F
(25)
Substituting algorithm 2 update rule for W(++1), get that there exist |10:11 such that:
w(++1) W(A) = -n (V (Waa l(yk
f fRNN, w (zx)) + +0x)
(26)
Now, explicitly writing Vwonk(yk. fRNN,WIih) (2x)) with the chain rule we have that:
Vwoellyk. FRNN, (zx)) T d
1
Σ
1+ e whth se (ww) ) (v waa WWNSsNNN, IRNN, (2x))
yt (1) e v-v(") s faan. (aw)
(27)
and since 0 S 145 I for any x 2 O, we conclude that:
x
Vwanklyk. fRNN, (2))
S
max dseST
wa Twoes ARNN, (Ex)
(28)
Now we will use induction over i, to show that [ w(
O
(i+1)
for any
0 I < n. By the induction hypothesis, lemma 10 assure us that for wide enough networks m = 2t (max {T log (zT), vnT*)) }). with probability of at least å over the initialization of pRNN, maxAsisT
V Je JRNN, RNN,
(zx) 1 =0 ===00p0 (To). Therefore, in this case
0
[ wr(h||
m T -0
788
= =0
(29)
m vn
m m
and hence [[+1)) 1 -
(1+1)2 m-ynn
as required.
Now after we showed the assumptions of lemma S uphhods, we can use it to obtain first order Taylor approximation of the training loss:
Lg (w()) L. (W*)= < (Vwol ,
(z.)), W( W
(30)
+ max d
Vt E - J (z.)
O
R
T
/m (logm)
|| W
1 1 Be. (z.)
vm
(31)
Where we assumed that m > and therefore [W() 1(0
0
vm
Using algorithm 2 update rule for W(++1) again (see eq 26). we inequality from in Shalev-
Shwartz & (2014)ss 's lemma 14.1 to get that:
Worllye (RN, (z,)) + o., w(t) - w.)
(32)
||
W
2
17
V Vwoel(ys, fRNN,W(G) (2.)) + o
(33)
21
2
17

---

Published as a conference paper at ICLR 2023
Now combing with Cauchy-Setie Schwarz inequality we have that:
|W(()
1I
||
Li (Wr()) - La (W:))
7
V Wwose(yss fRNN,Wit) (zx)) + o
<
211
2
1=1
(34)
R
$/ T Vmm (log (logm) m) )
| (-1w(--w-111) (35)
Σ
+0
vm
n
w()
-W*
(36)
Substituting the upper bounds from eqs
28
29 and using the assumption that 52 (T!)) we get
that:
O +
Σ Li (wrl))
-
- L. (W*))
+ 7.n 0 (1 + +1)²
-
(37)
21mm
R
+0
T (log m)
(T*) + +0
10(m== ( (n + +nR)
(38)
\ml
((
(R vn) +0
R m
T (logm) (R (R+ (TT) + 0 -0 (m-=8m) 8,²
(39)
To ensure the left hand side is upper bounded by O (R3vn)) we will chose m such that m"
(log" m= > n², note that, as required, m is polynomial in n, T. Then for m > m we have
that Di La (W()) s 0 ( R vn) Therefore,
L. (Wr)) So
R²
(40)
Now, prove generalization bound we will follow lemma 4.3 in Ji & Telgarsky (2020) and use martingale Bernstein bound argument. We begin by showing that during the whole training process, our binary cross entropy loss bounded. Indeed lemma 9 assure us that:
max max X (0(1))) deiST
RNN,
(z) O
T V
n
SO(
(41)
Therefore, their exist a constant C > 0 such that the binary cross entropy loss is bounded by log [1 (1+ (((19) TT4
Now, will define bounded martingle. For any i 2 0, let s; denote (x, and so, denote (so......8) 8:). Importantly, the quantity
Σ(Ex (Ex [[ JRNN. [2))] - (y., (zi)
(42)
C.
ECS
is a martingal w.r.t the filration a (80.5-1). This martingal difference sequence is given by
Ex [1 (y, FRNN, (z)) ((ve. FRNN, (())) (zi) $
(43)
C-114
Moreover, have
Ex (1 (y. FRNN, w (z)) -1 1 (yr, FRNN, (zi))) (80.)-1)
E E
(44)
C2. 728
Exs. [ (y.
(wi) 2 (80.-1))
Ex [1 (y,, pRNN. (2))
(45)
C 28
< Eso,
C.TTa' yy JRNN. (zi) 1o (80,4-1)
1
(46)
Ex [1 (yy JRNNS WC) (z)
(47)
C. T.4"""
18

---

Published as a conference paper at ICLR 2023
Therefore, by lemma C.2 in Ji & Telgarsky (2020) we have that with probability 1 -
Ex (y, pRNN,
[2)) 1 (x JRNN, (zi))
(48)
C T
C. T1 (e -2) Σ Ex (1 (yy, SuNN (x)) In 8
(49)
And hence
Σ Ex ( (x)) t=1
(3 Σ
yis fRNN, (zi)) + 0 (1 10-+)n In i
(50)
i=1
= 0 0 (T) + 10(R)M))) RIm (5))
(51)
Finally, for yt fe FRNN.W (z) < 0 we have that log (1 + e- ve.se (x) > 2. In addition, clearly
(1 fe w...e (x) 0. Therefore, we conclude that T-d Et lo-1 (ee Jt
,RNN, ,RNN,WGO w
log
(z)
(y, pANN,
(z) and thus eq 24 uphold.
log
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 EEstablihhing 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 inter- mediate supervision, presented in section [F] We will follow the proof in section while taking into account the full non-stochastic gradients.
Algorithm 3: Training fRNN with finite precision GD
Data: Data set D, learning rate 7). finite precision Initialization: The entries of (((), A, Mo are generated i.i.d. from NO, A)) The entries of B are generated i.i.d. from (00, 1
for i 3... do
Get arbitrary a-approximation of the gradient:
g E Bx
11
Ex Vwo-njly fRNN, w
(z)) .o).
Update weights:
Wi) W G())
end
We begin by sampling a fake training set denoted by x x1)) xI)),..., x (m), ( ,..,, (()), Essentially, we will apply the same reasoning in section with this fake training points. As in the finite precision SGD case it is enough to prove a lemma that is equivalent to lemma i section C
Lemma 5. Let T N, and denote by Le (W) = L (y((), fRNN,W (z))) the training loss. Suppose
there exists W* 1 (0)
R such that = O (poly (T)) S2 (T16) and L; (W*) S L
Vm
Then for any > 0 there exists m = poly (n, R, T, 8-1) such that if m > m then with probability precision o = = (1) will output:
at least 1 - 8 algorithm with myn
Ex (
ΣΣ lo-1 [U
RRNN, (R Wit
(2)) <00
R² + +logg
(52)
(T d)
f=dizl
The ball is with respect to the distance that defined by the max matrix norm, i.e. the elementwise distances are at most a. 1he ball is with respect the distance that defined by the Frobenius matrix norm.
19

---

Published as a conference paper at ICLR 2023
Proof. We begin by showing that there exists W E B (W
such that:
vm
R² Vn
Ex JRNN, (2) 5O
(53)
Indeed, since the minimum can not be larger than the mean, eq 150 in the proof of lemma assure
us that under the assumptions of lemma 5 for m >> max {n² In (3) }. with probability of at least
1 - 5 algorithm 2 will reach such W during the first max {n, In (1) SGD iteration.
Now we shows that that with high probability over the initialization of f fRNN, at any iteration s of algorithm 3 the distance of the learned hidden weights matrix W(() from its initialization point W is not too large. As a results we will get that the assumption of lemma uphold, and therefore its upper bound of the deviation from linearization is valid.
By the triangle inequality for any 0 S < n we have that:
- -w:t0
w(h+1)) ((())
(54)
F
k=
Substituting algorithm
3 uuddate rule for W(++1), we get that there exist 110:1la0 such that:
((++1) w(k) 17 Ex V
Waally fRNN, (w)) (z)) + ox))
(55)
Now, explicitly writing Vaaskly, fRNN,Wile (z)) with the chain rule we have that:
(RNN,W( (z)) T d Σ Us -u.
1+e-us sost ) (v (VwwnsRNN RRNN, wol0)
Twallly, P
(z)
(56)
and since 0 $ 1+r
x I for any x 2 0, we conclude by Jensen's inequality that:
T Ex
Ex Vwonely, FRNN, w [z))
V WwoeseNN RNN, wab
(z)
(57)
T
d 1=d
Now we will use an induction over i, to show that | - - = O (+11)*
for any S < n. By the induction hypothesis, lemma 10 assure us that for wide enough networks m² 2 (max (T" log (mTT)
n-y/n
, vnr }). with probability of least 1- ô over the initialization of = 0 (T*) for any ststs T. Therefore, this case
PRNN, Ex V Wway RNN, w(k)
(z)
F
| w[(k)
= =n (T +
T
(58)
m vn
mn Vn
and hence [[ 1000 0
1yT
as required.
m-vn
Now after we showed the assumptions of lemma upholds, we can use it to obtain first order Taylor approximation the training loss for any x:
(y, J RNN,
(z) ( FRNN. (z)) s V Wionlly, fRNN, (z)). w( - -w)
(59)
Ue E RRNN (x)
$ 1 Vm
|| w/1 (60)
max dstST
De FRNN.. (x)
Where we assumed that vn* > n and therefore
|
T 7m < 0
20

---

Published as a conference paper at ICLR 2023
Using algorithm 3 upddaee rule for W(++1) again (see eq 55). we can use inequality from Shalev-
Shwartz & Ben-David (2044)ss 's section 14.1.1 to get that
V Wonklly, jRNN. (z)) + to w - -w)
Ex
(61)
W w
Bx (wosely, JRNN, (2)) + 0z 1
(62)
2n
2
Now, we can take expectation over eq above bound and get that:
59 and combine the Cauchy-Schwand inequality with the
W
W
Σ Ex 1=1
pRNN, (z)) -1 (xxxx, FRNN.W (2))
(63)
2n
Ex
V Vwoolly, FRNN, (GG),
(z))
0. 1fe
+0
T
1/4
T vm (logm)
w 11112)
m
(64)
Substituting the upper bounds from eqs 57 58 we get that:
0 (T16)
(yNN, (z) 1 y,
fRNN.W (z)) -
+ n. (T + +)²
Ex
(65)
21mm
2
i=1
7
T (log m) (2nT*) + 0 (m- (m-²(2²TS)
+0
(66)
mm
0 ( vn) + 0 m 't th n² (logm) +0 m -
(67)
To ensure the left hand side is upper bounded by O we will chose m such that (log. m-) > n² note that, as required, m² is polynomial in n, T. Then since eq 53 assure us that
Ex y, fRNN,W (z)) S O for m > m² Therefore,
n² vnn
have that Σm= Ex [1 (y, fRNN, (z)
0 (n
( ,RNN, (x)) 00
(y,
R²
Ex
(68)
Vn
Finally, for ye ft ,RNN.W
< 0 we have that log
+ e- ve (x) > log 2. In addition, clearly
log [ 1 e ve.e. (x)
0. Therefore, we conclude that T-a Ete lo-1 JUNN, (z)
WNN,
<
( FRNN,WKO (z) and thus eq 52 uphold.
log 2
E LEARNABILITY OF RNNS
In this section we state and extend several lemmas from Wang al. (2021) and Allen-Zhu et al. 2019). We will use this lemmas in sections CD for extending theorem in the main text for finite precision SGD and GD.
Following Wang et al. 2021 's notations, for any target function h E Hacr,wiN) and n samples (z 1=1 we will denote:
H == 1 (Vwoo RNN, (z))), V Vwrnff J FRNN, (2)1))
(NN,
(69)
21

---

Published as a conference paper at ICLR 2023
and
he (z(1))
g())
(70)
hg (z (2()))
We start with theorem 4T from Wang et al. 2022 I measuring the complexity of a learned hypothesis class with respect to random initialization fRiNN
Lemma 6. Let > 0 and n E N, then there exist m poly (n, (n, such that if >> m² then for any HÆ(TwN.N) and (z()) m
i=1 with probability least 1 ô over the random initialization
of fRNN there exists matrices H H following holds:
H E R such that for any d S t S T the
1. There exist vlt E BF 0. 100 (stos) (Hr)0 1zf0))
such that H + (v(0)² v(0) 1
is positive semi-definite matrix.
2. V (DO) T - o ((00)=="'00(((T (T.
Now we state lemma 15 from Wang al. (2021). Essentially this lemma state that with high proba- bility over the initialization of fRNn, there exists weights that are not far from the initialization and have low training loss.
Lemma 7. Let y(")) be the training set and denote by L; (W) 1 (yl1), fRNN,W (z()))
the training loss. Then for any ò > 0 there exists m² = =poly (n, R, RRT, such that if m m then with probability at least 1 5, there exist W E B (W(0)
R wm
such that L, (W*) S 1+
and R Ō= ( ( (T
(H1:20)-11)) g(())
Now we state theorem 13 from Wang et al. (202T). Essentially this lemma bounds the finite width deviation of fRNN from its infinite width neural tangent kernel (Jacot et al. 2018).
Lemma 8. Let m, n E and r = o polv(n.T)
Vm ).
then with probability of at least
(n) exp (-2 m3
14
over the initialization of jANN fANN.for all (z( and W. W e B (w()),
for any S 1 < T and
[n]] the following hold:
FRNN. W (2)() - -Jt ..NN.W W.
(2))) - (V W RNNN ) w)
(71)
(0(rr T /m (log m)
1 w||
(72)
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 fRNN with high probability over its initialization.
Lemma 9. Let m E N and W
E
W(O),
polv(T) Vm ). then for a given x and d < st T with
probability of at least 1 - -0
over the random initialization of pRNN the following hold:
RNN, (z) O 8
w |-w +t)
(73)
Moreover, with probability of at least 1 0(1) 12
72
also the following holds:
max max x0(0.114 dREST
WNNNWW
(z) 0
6
W w(
+ +T)
(74)
F
Commined with Remark H.1 in Wang al.
2021 's supplementary materials.
2021 ensure only weaker guarantics of probability 1 O (n) exp (-Q (logm)). but we contirm with the authors that theirs proof proves also our stronger guaranties. The ball is with respect the distance that defined by the Frobenius matrix norm.
Note that lemma 13 from Wang et al.
22

---

Published as a conference paper at ICLR 2023
Proof. We begin by showing that it is enough to bound h4 (z). This is indeed the case since
it is well known that | O (1) with probability of at least 1 - (-((m)) (see for exam-
ple Bandeira & Van Handel 2016)). Now lemma B.3 from Allen- Zhu et al. (209)) assure us that 4
O (t), and finally lemma C.2.a from Allen-Zhu et al. (2019) bounds the deviation
from the initialization | (z) 1 [z) O (T ||
W(0) p). Finally simple union
bound on all the possible d bits configurations prove also equation 74
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 jRNN's gradients. We will use this lemma for bounding P the finite width deviation of fRNN from its infinite width neural tangent kernel (Jacot et al. 2018 Beyond its application for proving our positive results, lemma [0 below also implies that fiNN, 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.
Lemma 10. Let m E N and W
16 W(0),
(Tl((T)
then for a given x and < T with vm ).
probability of at least 1 -
over the random initialization of fRAN the following hold: 8 w
WwSe JRNN,W W (z)
=0
w(0)
F + TT1
(75)
Moreover, with probability of at least 1 e O(T)
m3
T2
it holds sinultaneously for all x's and t's.
Proof. Let D. mm be a diagonal matrix that its diagonal equals to when 1 (z) > 0 and
otherwise 0. Then we can write the gradients of JRNN as:
i+1 (z) = EII(WT (WT BDn (z)
RNN, Vw fs
(76)
1=1
The proof of lemma assure us that | (z) = O (T WWW-wolll + t) with probabil- m
ity of at least - -2
over the random initialization of jRNN, In addition, lemma B.11
together with lemma C.9.d from Allen-Zhu et al. (2019) assure us that (WTD:) =
O (T W w | + T for all i.j with probability of at least well known that BBI, = O (1) with probability of at least 1 - e -Qmm) (see for example Bandeira & Van Handel (2016)) ), and clearly ||lll $ for any t. Therefore, overall we got that equation 75
Now, it is
holds with probability of at least - d bits configurations and T d proves the bound holds simultaneously for all x's and t's. L
T
Finally, a simple union bound on all the possible
Finally, we rely on lemma 8 from Wang et al. from its infinite width neural tangent kernel (Jacot et al., 2018).
2022 to bounds the finite width deviation of RRNN
Lemma 11. Let m E I and r O
poly(TT)) Vm
then with probability of at least
exp (Tlog T) 2 (m²)) over the initialization of JRAN, for all W.W E B (w(0),r) the following hold:
RNNN W (z), W max max (Jeeer.. (z) - F.N.N.W (z) - (VwJ J.NNNN dSeST 2
(z) -w))
(77)
(1 Vm (logm)
W WW W/
(78)
Proof. Simple union bound on all the possible d bits configurations and T d I's proves the bound in lemma 8 holds simultancously for all x's and t's.
The ball is with respect the distance that defined by the Frobenius matrix norm.
23

---

Published as a conference paper at ICLR 2023
F BIT-SUBSET PARITY END-TO-END NEGATIVE RESULT PROOFS
In this section, we present theorem stating that without intermediate supervision, for any neural network with gradients that are polynomially bounded, one must use an exponential number GD steps to achieve non negligible accuracy in the above-presented task of bit subset parity.
Theorem 4. Let fo be any neural-network with Ex [| se so [x)
O (poly (d) (polyno-
mially bounded gradients), and let A be any iterative O (poly (d)) iterations, and at each iteration receives 52 (e (() -approximation
maddiettbbssed optimization algorithm
that runs for
Ex [VI (y. fe (x)) Then, with probability of at least 1-0 (e (e=)) over the target parity function, the loss of A will be higher than 2 O)e
This theorem follows directly from Shalev-Shwartz et al. (017) and Shamir (2018) and from the fact that random guessing has high zero-one loss, see full proof below. Importantly, lemma TT shows that fRNN, for which we proved our positive results when intermediate supervision exists, upholds the polynomially bounded gradients requirement in theorem[4abl above with high probability. Moreover, section shows that our positive results holds also for an fimite-recisioo 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 [Follow.
We will use abuse of notations and sometimes identify a predictor h H with the corresponding vector in {0, 13d that his i'th coordinate equals to if is one of the indices in the subset and
O 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 target function h.
min (w)
(79)
where: Fr. (w) Ex (Pw (1),, (x))]
where / a loss function, x are the stochastic inputs, and Pw is some predictor parametrized by a parameter vector (e.g. neural network of certain architecture). We assume that F is differen- tiable. We measure the variance the gradient of F with respect h, when l is drawn uniformly at random from a collection of candidate target functions H::
Var (H, F. w) = En || (w) - EG [ (w)
(80)
To measure meaningful learnability, we will define the expected loss of random guessing from (0, 1) fraction of the hypothesis class H as:
H.a.d
min KER
E B
Ex [x))
(81)
RCH. 20-11
As a approaches 1, this measure reflects the expected loss to be attained by randomly assigning hypothesis from 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 random- ized), which relies on an e-approximate gradient oracle to optimize Fù, in eq 79 The lemma states that if the number of iterations is not larger than Var (H, F, w) -1/s then with high probability, the algorithm will return the same predictor independent h.
s/su Var (H, w) and let A be any iterative gradient- 19 opti- mization algorithum that runs for n iterations, and at each iteration receives Ω (e) apparoooxinnto of V F2 (w)) Then the following holds:
Lemma 12. Define
P PRo)
[Ex [1 (1 PA (x)) E 2 1- 1-ne ne
(82)
17 For any 0 that reachable by A with itcrations.
18 Sce footnote
19Sce footnote
24

---

Published as a conference paper at ICLR 2023
Lemma 12 above assures that in order prove negative learning results regarding some task, it is enough to show has both exponentially low variance of gradient and high random guessing error. Now will show both of these for the task of learning bit subset parity presented in section [ Following Shalev-Shwartz et al. (217)), we start by showing that different parities functions are uncorrelated, and hence this task has exponentially low gradient variance:
Lemma 13. For any (1y) + (i,) j=1 we have that:
(-1) mys (-1) oi
Ex
(83)
Proof. Denote by h + h E {0, 11a the vectors that corresponding to the (iz) (8)) Then
xx
(-1)Σ oi (ーرحمر
Exx
(-1) (x,))
(-1)
(84)
(- 1) (2.htthi)
Fx
(85)
(-1)
Ex
(86)
Since the coordinates are independent we can swap the order of the expectation and the product:
d
hythi (-1 + (-1)
(
Ex
(87)
2
j=1
1=1
(-1)
-y +1
(88)
2
Finally, since h * there exists some E [d] such that hy + hy and therefore h, + h, = 1 and (-1) +1 0.
II
Now following Shalev-Shwartz Shwartz al. (2017). show that the zero correlation between different parities implies exponentially low gradient variance.
Lemma 14. Assuming that Exx [| Pu (x)] = O (poly (d)) then supw Var (H, F, F, O (1P4)-)) where H denote the hypothesis class of d dimensional parities described in section
Proof. We use theorem I from Shalev-Shwartz et al. 2017). Essentially, this theorem shows that if the functions in the hypothesis class uncorrelated, then the variance is upper bounded by Ex ow Pw (x)] times the inverse of the hypothesis class size.
our case, lemma 13 above shows that:
(1,) (1)) ( Ex (-1) #y (-1)
(89)
And therefore we have that
Var (H, w) I 1711- Ex
Ow Pe (x)
(90)
25

---

Published as a conference paper at ICLR 2023
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 13 establishes this, showing that the task of learning bit-subset parity has non-vanishing random guessing error of θ (1) 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 H. denote the hypothesis class of dimensional parities described section 1--1 denote the zero loss. then the following holds:
and
(1 2
1 a [7
1
Ya (0,1) E
(91)
Proof. Let h E H. we begin by writing the zero-one loss with elementary algebraic operation:
(R) (R)
Ex lo-1 (n (x) h (x))]
= (h-e(((E((.)))))
|xx1 ( (-1)
((-)((xn))
(92)
1- (-1-)) (x.1))
(-1) (x,h))
= ()))((A)
Ex
(93)
2
(1- (A) Ex ((-1) (-I1)(atth))
(94)
Since the coordinates are independent we can swap the order of the expectation and the product:
1
II Rzz (- (-1))x((uthh))
1
E
( ())
(95)
2
1
(-1))cthe (-1191
1
E
( R2)
(96)
2
2d
[=1
Now, in cases where h * h there exists some j E [d] such that hy # hy. Therefore, in such cases
( 0 and we get that:
hy + hy = 1 which implies that II, ==1
E B (2th 11-=n==))) 2
1
(97)
2
(i)ee(A)) [ln=rl)
(98)
2
Now clearly
1
h E H
E ( [1
= 0
[d
(99)
$ H
And therefore
(x) Bx [0-1 (x)),, (x))
1
[
h E H
(100)
2
2
0
E H
Finally, by combining lemmas 14 15 with lemma 12 we prove theorem
4
Proof. By lemma 14 we know that supw Var (H, F, w) o (IM--)) Now since (+) > (2) for
any k < n., we have that [H]
Ω (ed) i.e. have exponentially low variance. Therefore,
lemma 12 assure us that with probability of least 1 n O (e -fa) the loss of A will be higher
do-1 than E H. n-O (121- 30--1 Finally, lemma 15 implies that:
E H. -.1
No-1 )) 2
1
1 1 [7|| max fo (1H1() n, |71 -1)
(101)
-n,17111
26

---

Published as a conference paper at ICLR 2023
Table 1: Learning Bit-Subset Parity with Transformers results. We say that model is better than random when its validation accuracy are higher than 60%. In addition, for each task we also eval- uated the accuracy after 100k training iteration. The reported test accuracies are of the models with the best parpmerrrssttesss according to the validation loss. Each value after the + 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% + 0.0
79 + 21.16
100% + 0.0
185 + 79.89
10 Bits
100% + 0.0
843 + 424.22
12 Bits
100% 0.0
4.049K +1.1
14 Bits
100% + 0.0
31.16K 27.
16 Bits
100% + 0.0
333 = 67.002
51.82% + 1.06%
211.66K +57.9K
18 Bits
50.16% + 2.65%
1.534M #1.04MM
32 Bits
100% + 0.0
1.48K #11.10
49.87% + 0.72%
> 100K
64 Bits
100% + 0.0
11KKt1.154K
49.93% + 0.43%
> 100K
128 Bits
99.96% + 0.06%
58.33K 25.20K
50.71% + 1.26%
100K
256 Bits
48.24% + 2.06%
720.16K 183.17K
50.34% + 0.73%
100K
and the random seed that examined in the experiment of learning bit- subset parity with Transformers.
Table 2:
Learning Rate
10
10-5.
10 5
10 10-4
Weight Decay
0,
10
10
10
Dropout
0
Batch Size
32
Warmup Steps
1A
Total Steps
100%
Number of Layers
12
Hidden Size
768
FEN Inner Hidden Size
3072
Initializer Range
0.02
Adam $1
0.9
Adam $2
0.999
Adam
10-8
Validation Size
min(1024, 12.5% of the data)
Test Size
min 12.5% of the data) 27, 67, 93
Dataset Seed
G BIT-SUBSET PARITY EXPERIMENTS FULL DETAILSS
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. this section, we present the full details of the experiments.
Following the bit-subset parity definition in section 5 we randomly sampled subset of d/2 prede- fined unique indices and then we randomly sampled non-overlapping training, validation and test datasets. For reproducibility purposes, Table reports the random seeds that used for this sampling. Then, we used the standard implementation GPT-2 from the transformers framework (Wolf al.) 2020) and trained a BERT-Base size Transformer decoder model with vocabulary size of 2. Even though the small vocabulary size of our model may indicate that it too shallow for its size (Wies)
For models that converged after less than 5K steps we disabled learning rate warmup.
For models that did not converged after 100K steps continue the training until convergence. Note that even for thus models Table reports the accuracy step 100k.
27

---

Published as a conference paper at ICLR 2023
et al. 2021p, still choose use the standard Transformer-Ban configuration. See full archi- tecture and optimization details in Table 2 While the evaluation of a model without intermediate simply use argmaz over the last token logits. This is no
supervision is straightforward, longer the case when intermediate supervision is used since at evaluation time the model must cre- ate its intermediate steps. As result, in this case, need decoding algorithm that iteratively predicates the intermediate steps. Since we found in preliminary experiments that greedy decoding tends be more efficient for longer sequences than random sampling, we choose to
To complement Figure 3 in the main text, Table shows the first iteration 22 for which the model better than random as well as the test accuracy after 100k training iterations. Though "better than random" could be defined in variety of ways. Figure A illustrates a typical learning tra- jectory and demonstrate the insignificant differences in definitions due to the observed grokking phenomenon (Power et al.) (021). For each task we repeated the task 3 times with different dataset seeds, and perform grid search over the nyper-parameters in Table 2 Table [ reports the mean and standard deviation test accuracy of the best hyper-parametten 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 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.
100%
Almostt Perfect
Accuracy
75%
Random Guessing
50%
20K
40K
60K
100K
Tterations
Figure 4: Illustration of typical bit-subset parity learning trajectory. In these tasks we observed grokking phenomenon (Power et al. (021) 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.
Vaalidationn accuracy was evaluated at K-step intervals, except for models that converged in less than 4K steps for which run the evaluation every 10 steps.
28


Reviews:
[{"review_id": "vZ2iOlZn9M", "reviewer": "Reviewer_f3DQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to address the compounded natural language problems required by introducing sub-task decomposition and concatenating intermediate supervision to the input and training the sequence-to-sequence model on this modified input. \nThe contribution of this paper can be concluded as:\n* proving a positive theoretical result on decomposing compounded tasks with neural networks in an end-to-end manner\n* The above theoretical results can apply to a broad family of tasks, and currently including SOTA  language models on complex multi-hop tasks in NLP\n* generalizing the above results, and demonstrating that sequence-to-sequence tasks with sufficient intermediate supervision  allow learning any function in the P time complexity class\n\n", "summary_of_the_review": "This paper has addressed a valuable problem: sub-task decomposition in sequence-to-sequence learning, and provided theoretical analysis, applied it to tasks and analyzed the time complexity. The paper is easy to follow but the inspiration is imited. ", "strength_and_weaknesses": "#Strength\n* The paper address a valuable problem: the compounded natural language problems requiring introducing sub-task decomposition and concatenating intermediate supervision\n* Sufficient proofs are provided in the appendix\n\n#Weaknesses\n* The theoretical analysis of sequence-to-sequence models seem not strong enough, and many of first-mentioned symbols in equations have inadequate explanation. Maybe it is because you have moved many details to appendix. Analogously, the experiments face the same problem.\n* The inspiration from this paper is limited, and it seems that the theoretical and experimental results are apparent\n* The structure of the paper can be improved. BTW, I think it would be more legible to organize the sequence (1,2,3,4) in a vertical way in Figure 1.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qje8U0wYNd", "reviewer": "Reviewer_iwZz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper theoretically proves that sub-task decomposition can facilitate training of an elmon RNN by reducing the number of gradient updates to polynomial order while undecomposed tasks can't be learned with polynomial updates.", "summary_of_the_review": "The paper provides some interesting theoretical analysis of the usefulness of sub-task decomposition for seq2seq tasks. However, the settings are somewhat oversimplified and deviate significantly from the main motivation of the paper (sub-task decomposition for NLP/reasoning tasks with LLMs.)", "strength_and_weaknesses": "Strengthes:\n1. Decomposing complexe reasoning tasks into subtasks is currently very popular in NLP, and some theoretically analysis of this paradigm can be helpful.\n2. The paper is overall well written and the proofs/theorems looks good to me.\n\nWeaknesses:\n1. The authors motivate their research problem by sub-task decomposition of LLMs. However, most current practice of using sub-task decomposition with LLMs are using in-context learning without gradient updates, which is very dissimilar with the settings analyzed in the paper.\n2. The model architecture analyzed in the paper is elmon RNN, which is also very different in nature compared with Transformer models (i.e., sequential computation in RNN v.s. parallel encoding with Transformers). The paper could be made more interesting if the proof can be generalized to Transformer architectures. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L5qVbLb-WT", "reviewer": "Reviewer_T2bv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper analyzes the learnability of sequence-to-sequence tasks, based on whether or not the answers to sub-tasks are provided as part of the input sequence. It proves a rather general result: That *any* function in the P time complexity class is efficiently learnable by a neural network when sub-task supervision is provided, but there exists functions in P which are not learnable (in polynomial time) without sub-task supervision.\n\nThe paper gives significant attention to the “bit-subset parity” problem: this is the problem of determining whether a bit-string of length d has an even or odd number of ones in an unknown subset of d/2 indices. It shows that this problem is efficiently learnable by an RNN when sub-task supervision is provided, but is not learnable (under standard cryptographic or computational hardness assumptions) in polynomial time without this supervision. In this case, the sub-task supervision is the parity of pairs of the unknown indices, recursively followed by the parity of these sub-task parity answers in a binary-tree like structure: $par(x_i1, x_i2), par(x_i3, x_i4), …, par(par(x_i1, x_i2), par(x_i3, x_i4)), …$ (see Figure 2, Section 5). The paper then uses the hardness results regarding this bit-subset parity problem from Shalev-Shwartz et al. (2017) to prove it is not efficiently learnable.\n\nAlthough the primarily contributions of this paper are theoretical, this paper also provides experiments showing that a powerful transformer network (BERT-base architecture) is unable to learn the bit-subset parity problem for $d \\geq 32$ (within ~2M gradient steps), but can easily learn it when the sub-task supervision is provided (e.g., can learn $d=128$ in  $< 100k$ steps).\n", "summary_of_the_review": "This paper provides important theoretical results regarding the learnability (or unlearnability) of sequence-to-sequence tasks by neural networks, depending on whether or not sub-task supervision is provided. These results are quite general, and provide important insights for future empirical research in sequence to sequence learning.  As a result, I definitely recommend acceptance for this paper (although my review is only medium confidence, given that I am not super familiar with the related work).", "strength_and_weaknesses": "Strengths\n- I was impressed by the generality of their positive results: that any function in P is learnable when suitable sub-task supervision is provided. Their use of boolean circuits to prove this result was very clever.\n- Their use of the bit-subset parity problem throughout the paper was effective at making their theoretical result more concrete and easier to digest.\n- Although the primary results are theoretical, I do feel that these results have important empirical implications regarding the limits of sequence-to-sequence models in solving complicated tasks that require multiple intermediate reasoning steps, when intermediate sub-task supervision is not provided. It also serves as encouragement for empirical work that provides this intermediate supervision to large language models.\n\nWeaknesses\n- It is not immediately clear how the theoretical constructions presented in this paper can be applied to solve real problems in NLP/ML. Perhaps the authors could comment further on how they believe intermediate supervision can be provided in these practical settings.\n- NIT: I felt that the clarity could be improved in a few places. For example, I felt that the hypothesis class defined by equation (6) could have been more carefully explained (for example, what is e_z, and what is w?).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IiAW_UOLti0", "reviewer": "Reviewer_G5w1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies how intermediate supervision (i.e. breaking a task down into steps) can theoretically increase the power of learning complex tasks.\n\nThe authors give a real world motivating example of math problems i.e. \n\"John and I split 12 apples between us, and he gave 1 to his son. How many apples does he have now?\" (5)\n\nwhich can be broken down into:\n\n1. John and I split 12 apples between us. How many apples does he have now (6)\n2. John had 6 apples and he gave 1 to his son. How many apples does he have now? (5)\n\nThis has been empirically observed in the past and has gained recent prominence due to impressive results with large language models (i.e. chain of thought prompting)\n\nThe authors assume a particular model (a simple RNN) and theoretically prove the following:\n\nThere exists a binary classification problem of size d such that with intermediate supervision it is possible for seq2seq model to get an arbitrary low error with a polynomial number of gradient updates in d. However, without intermediate supervision, then for any polynomial time learning algorithm the error will be higher than 1/2 - epsilon. \n\nThey then explore the specific case of bit subset parity, showing learning curves for BERT that demonstrate that without intermediate supervision the number of training steps required grows very rapidly as the size of the problem increases, whereas with intermediate supervision the number of training steps grows at a much more favorable rate.\n", "summary_of_the_review": "I support accepting the paper. It is well motivated, well-written and sheds theoretical insight onto an interesting and relevant problem. ", "strength_and_weaknesses": "Strengths\n-Well written and interesting. \n-Studies a phenomenon that is of great interest to the community right now. \n\nWeaknesses\n-The theory is interesting but does not lead to any new methods. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "AXK6454gar", "reviewer": "Reviewer_Qt7K", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents theoretical and empirical results supporting an exponential gap between a sequence-to-sequence task and its decomposition into many smaller subtasks. In this study, the authors consider a bit parity task where the objective is to determine if the number of ones in a subset of a 0/1 array of length d is odd or even. This is formulated as a binary classification task. \n\nWith this setup, the authors show the following main result:\n\n1) When a task is decomposed into subtasks, a seq2seq model can get a get arbitrarily low zero-one loss (\\epsilon) with a number of gradient updates that is polynomial in d.\n2) When no supervision over subtasks is provided, for any polynomial time learning algorithm, the zero-one loss will be > ½ - \\epsilon.", "summary_of_the_review": "The main novelty of this paper is in proving the exponential gap in the learnability of sequence-to-sequence tasks with and without intermediate supervision. While there are some limitations on the number of sub-tasks with supervision required, it is still a good starting point for future work that seeks to understand why ideas like “chain-of-though” prompting of language models are so effective.", "strength_and_weaknesses": "Strengths:\n\n1. The paper proves a useful result shedding light on the effectiveness of breaking down sequence-to-sequence problems into supervised subtasks.\n2. The paper is well structured - it studies a well-defined problem, proves theoretical results, and verifies them empirically (albeit in a slightly different setting).\n\nWeaknesses\n\n1. As the authors point out, all of their results hold only when the number of subtasks is O(d) rather than O(1) and in most practical cases, O(1) subtasks are more likely.\n2. The theoretical and empirical results use different model architectures.\n\nQuestions:\n\n1. Since most of your theoretical claims are for recurrent networks, did you attempt to empirically validate them with RNNs? How do your conclusions hold for RNNs with activations besides ReLU? Is this assumption mostly a result of the setting used in Wang et al. 2021? ReLU RNNs.\n2/ Why did you leave the input embeddings and initial hidden states untrained?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster