Provable hierarchical lifelong learning with a sketch-based modular architecture
Authors: Rina Panigrahy
Brendan Juba
Zihao Deng
Xin Wang
Zee Fryer
Venue: ICLR 2022 Submitted (2022)

Abstract: We propose a modular architecture for lifelong learning of hierarchically structured tasks. Specifically, we prove that our architecture is theoretically able to learn tasks that can be solved by functions that are learnable given access to functions for other, previously learned tasks as subroutines. We show that some tasks that we can learn in this way are not learned by standard training methods in practice; indeed, prior work suggests that some such tasks cannot be learned by \emph{any} efficient method without the aid of the simpler tasks. We also consider methods for identifying the tasks automatically, without relying on explicitly given indicators.

Under review as a conference paper at ICLR 2022
PROVABLE HIERARCHICAL LIFELONG LEARNING WITH A SKETCH-BASED MODULAR ARCHITECTURE
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a modular architecture for lifelong learning of hierarchically struc- tured tasks. Specifically, we prove that our architecture is theoretically able learn tasks that can be solved by functions that are learnable given access to func- tions for other, previously learned tasks as subroutines. We empirically show that some tasks that we can learn in this way are not learned by standard training methods in practice; indeed, prior work suggests that some such tasks cannot be learned by any efficient method without the aid of the simpler tasks. We also con- sider methods for identifying the tasks automatically, without relying on explicitly given indicators.
INTRODUCTION
How can complex concepts be learned? Human experience suggests that hierarchical structure is key: the complex concepts we use are no more than simple combinations of slightly less complex concepts that we have already learned, and so on. This intuition suggests that the learning of complex concepts is most tractably approached in setting where multiple tasks present, where it is possible to leverage what was learned from one task in another. Lifelong learning (Silver et al.) 2013 Chen & Liu 2018) captures such setting: are presented with sequence of learning tasks and wish to understand how to (selectively) transfer what was learned on previous tasks to novel tasks. We seek a method that can analyze and prove leverages what it learns on simple tasks to efficiently learn complex tasks; in particular, tasks that could not be learned without the help provided by learning the simple tasks first.
In this work, we propose an architecture for addressing such problems based on creating new mod- ules to represent the various tasks. Indeed, other modular approaches lifelong learning Yoonn et al. 2018 Rusu et al. 2016) have been proposed previously. But, these works did not consider what we view as the main advantage of such architectures: their suitability for theoretical analysis. We prove that our architecture is capable of efficiently learning complex tasks by utilizing the func- tions learned to solve previous tasks as components in an algorithm for the more complex task. In addition to analysis proving that the complex tasks may be learned, such an approach can learn functions that standard training methods fail to learn in practice, includ- ing some that are believed not be learnable, even in principle (Klivans & Sherstov 2009). We also consider methods for automatically identifying whether a learning task posed to the agent matches previously learned task is novel task.
also demonstrate that
We note briefly that a few other works considered lifelong learning from a theoretical perspective. An early approach by Solomonoff (1989) did not seriously consider computational complexity as- pects. Ruvolo & Eaton (2013) gave the first provable lifelong learning algorithm with such an anal- ysis. But, the transfer knowledge across tasks their framework was limited to feature learning. In particular, they did not consider the kind of deep hierarchies of tasks that we seek to learn.
1.1 OVERVIEW OF THE ARCHITECTURE
The main technical novelty in our architecture over previous modular lifelong learners is that ours uses particular type of internal data structure called sketches GGhazi et al. 2019 Panigraby 2019). All such data, including inputs from the environment, outputs from a module for another task, de- cisions such as choosing an action to take, even descriptions of the modules themselves,

---

Under review as a conference paper at ICLR 2022
Enviorment Input
Envhramment
phenomonn
skotch
context
bucket
phenomera
Bucest cor programn co sg shishes.
Rouding Module (OB)
LSH Table (modduiee)
Figure I: (left) The Routing-module (OS) routes sketches to the programs the LSH table, which in turn produces sketches that are fed back to the OS in addition to sketches of inputs from the environment. The OS, while shown here as a distinct module, could itself be a module (program) in the LSH hash table. (right) Sketch of hand of cards during a card game. The (cards-in in-hand- sketch jis a tuple of sub-sketches (one for each card), and each (card-i-sketch \is itself compound sketch: for example, (card- 1-sketh )consists of the AARD-DESCRIPTION label/type and three sub-sketches describing the card's number, color, and symbol.
encoded as such sketches. Although sketches have dense (vector) representation, they can also be interpreted as kind of structured representation (Ghazi et al. 2019. Theorem 9) and are recursive; that is, they point to the previous modules/events that they arose from (Figure [ right). However, in order to construct these sketches in Ghazi et al. (2019), the structure of the network is assumed to be given. No algorithms for constructing such a hierarchical network of modules from training data were known. In this work we show a method to construct such hierarchical network from training data. We provide architecture and algorithms for learning from stream of training inputs that produces such a network of modules over time. This includes challenges of identifying each module, and discovering which other modules it depends on.
Our architecture can be viewed as a variant of the Transformer architecture (Radford et al.) 2021 Shazeer al. 2017), particularly the Switch Transformer (Fedus a [202]] in conjunction with the idea of Neural Memory (Wang et al. (021). Instead of having a single feedforward layer, the Switch Transformer has an array of feedforward layers that an input can be routed to at each layer. Neural Memory on the other hand is large table of values, and one or a few locations of the memory can be accessed each layer of deep network. In a sense the Switch Transfomer can be viewed having memory of possible feedforward layers (although they use very few) to read from. is viewing the memory as holding "parts of a deep network" as opposed to data, although this difference between program and data is artificial: for example, embedding table entries can be viewed "data" but are also used to alter the computation of the rest of the network, and in this sense act as a "program modifier".
The key component of our architecture is a locality sensitive hash (LSH) table based memory (see Wang et al. (202I)) that holds sketches of data (such as inputs) and modules or programs (think of an encoding of a small deep network) that handles such sketches (Figure [ left). The "operating system" of our architecture executes the basic loop of taking sketches (either from the environment or from internal modules) and routing/hashing them to the LSH table to execute the next module that processes these sketches. These modules produce new sketches that are fed back into the loop.
New modules (or concepts) are formed simply by instantiating new hash bucket whenever new frequently-occuringg context arises, i.e. whenever several sketches hash to the same place; the con- text can be viewed as a function-pointe that function. Frequent subsets of sketches may be combined to produce compound sketches. Fi- nally we include pointers among sketches based on co-occurrence and co-reference in the sketches themselves. These pointers form a knowledge graph: for example if the inputs are images of pairs of people where the pairs are drawn from some latent social network, then assuming sufficient sam- pling of the network, this network will arise as a subgraph of the graph given by these pointers. The main loop allows these pointers to be dereferenced by passing them through the memory table, so they indeed serve the intended purpose.
and the sketch can be viewed as arguments for a call to
The main idea of the architecture is that all events produce sketches, which can intuitively be thought of as the "mind-state" of the system when that event occurs. The sketch-to-sketer similarity property (see below) combined with similarity pressrving hash function ensures that similar sketches go
2

---

Under review as a conference paper at ICLR 2022
to the same hash bucket (Appendix By; thus the hash table can be viewed content addressed memory. See Figure for an illustration of this. We remark that the distances between embeddings of scene representations were used to automatically segment video into discrete events by Franklin et al. (2020), and obtained strong agreement with human annotators. The thresholded distance used to obtain the segmentation is analogous to locality-sensitive hashes, which we use context sketches.
A sketch can be viewed different levels of granularity before using access the hash table; this becomes the context of the sketch. Each bucket contains program that is executed when a sketch arises that indexes into that bucket. The program in turn produces outputs and new sketches that are routed back to the hash table. The system works in a continuous loop where sketches are coming in from the environment and also from previous iterations; the main structure of the loop is:
produces
Phenomene
impout
sketch
context
bucket
program
unipput Phenomena
Thus external and internal imputs arrive as sketches that are converted into a coarser representation using function f (see Section 2.T below) and then hashed bucket using locality-sensitive hash function h. The program at that bucket is executed to produce an output-sketch that fed back into the system and may also produce external outputs. This basic loop (described in Algorithm I is executed by the routing module, which can be thought of as the operating system of the architecture.
SKETCHES REVIEW
Our architecture relies on the properties of the sketches introduced in Ghazi et al. (2019). In this section we briefly describe the key properties of these sketches; the interested reader is referred to Ghazi et al. (2019); Wang et al. (2021) for details.
sketch a compact representation of a possibly exponentially-wide (d x N) matrix in which only a small number & of the columns are nonzero, that supports efficient computation of inner products, and for which encoding and decoding are performed by linear transformations. For concreteness, we note that sketches may be computed by random projections to Rd for d' 2 kd log N; the Johnson- Lindenstrauss Lemma then guarantees that inner- anner-products are preserved.
For our purposes, we suppose modules MI...., MN produce vectors .I E Id as output, where only & of the modules produce (nonzero) outputs. We view the sparse collection of module outputs as a small set of pairs of the form {[M, 24, I........MMM.... ..M Fi }: For example an input image has sketch that can be thought of as a tuple [IMAGE, (bit- Ditt-map-sketc)).. An output by an image recognition module that finds a person in the image can be represented as [PERSON, [person- sketch), ponssttionin-mmma---seehhe If the outputs of these modules are vector embeddings in the usual sense, then indeed the inner products measure the similarity of the objects represented by the output embeddings.
here IMAGE and PERSON can be thought of "labels".
Observe that the constituent individual vectors I, in a sketch may themselves be sketches. For example, (person-sketch) could in turn be set of such pairs and an image consisting of multi-
[FACIAL-
FEATURES, (facial-sketch/)) [POSTURE, possture-ssetch/]] ple people could be mapped by our recognition module to a set (person-IIsketth)) (person-2- sketch).... (pr....ppprooo--ssetteee the sketch of each of its members but only get a "average" or summary of all the sketches how- ever if member has high enough relative weight (see (Ghazi et al., 2019, Section 3.3)) it can be recovered. Appendix discusses how large objects can be stored as sketches hierarchically.
Note if the if the tuple is very large, we will not be able to recover
Indeed, following Ghazi et al. (2019), the outputs of modules in our architecture will be tuples that, in addition to an "output" component, represent the input sketches which, in turn, represent the mod- ules that produced those inputs, e.g.. [IMODULE-ID, (DD.UULEE-D.mmouee-eeie.eee (module-id)), (OUTPUT-SKETCH. (ouputt (recursive-input -iptt---c-tt-tch))) By recursively unpacking
sketch)]. J. [RECURSIVE-INPUTE the input sketch, it is possible reconstruct the history of computation that produced the sketch.
3

---

Under review as a conference paper at ICLR 2022
Algorithm Informal presentation of the main execution loop
Input: imput sketch I (this sketch may contain desired output for training)
current- skeet - {
while current-sketchhe
not empry:
cuzrent-programe + 0
foreach sketch www.enttseeeeateee do
extract context C f(S)
update creess-rrquency-ccur of bucket li(C)
if bucket h(C)) has a program P:
append (S, P) to curzent proograms
else:
10
if bucket h(C) is frequently accessed:
initialize program at l(()) with some random program and mark it for training.
Fetch programs P. (possibly by some similarity criterion), append those (S, P:) to cuzrent-progia ars
13
Routing module chooses some subset current- sociated sketch, appends outputs to peerent-sxeecche
runs each program on its as-
14
Append sketches on outgoing edges of accessed buckets to current-sket.nn if any of the programs are marked for training:
16
routing module picks one or some of them and trains them, and may choose to stop execution loop
17
if any of the sketches is of (a special) type OUTPUT sketch: routing module picks one such, outputs that sketch or performs that action, and may choose to stop execution loop any of the sketches is of type REWARD sketch (say for correct prediction or action): updates the reward for this bucket and propagates those rewards to prior buckets Routing module picks ls combinations of sketches in current mentt-sketches. and combine them into compound sketches: Si...., Sy (may produce O sketches) current sket ches +-
18
19
21
22
2.1 PRINCIPLES OF THE ARCHITECTURE
The following are the guiding principles behind the architecture.
1. Sketches. All phenomena (inputs, outputs, commonly co-occurring events, etc) repre- sented as sketches. There is a function from sketch to context J = S - C' that gives a coarse grained version of the sketch. This is obtained by looking at the fields in the sketch S that are high level labels and dropping fine details with high variance such as attribute values; it essentially extracts the "high-level bits" in the sketch S.
2. Hash table indexed by context that is robust to noise. (more details in Appendix C.2 The hash function : C' + bucket is "locality sensitive" the sense that similar contexts hashed the same bucket with high probability. Each hash bucket may tain a trainable program P, and summary statistics as described in Figure We don't start train P until the hash bucket has been visited a sufficient number of times. (Note: A pro- gram may not have to be an explicit interpretable program but could just be an "embedding" that represents (or modifies) a neural network.)
3. Routing-module (can be implemented by Alg Given set of sketches from the previous iteration, the routing module identifies the top ones, applics the context function f followed by the hash function h route them their corresponding buckets. Before feeding these to f. the routing module picks a subset of sketches and combines them into compound sketches. The routing module makes all subset-choosing decisions
In addition, we also keep associations of frequently co-occuring sketch contexts as edges across buckets forming knowledge graph. Please see Appendix and for details.
Thus modules (or concepts) formed simply by frequently occurring context (see earlier papers on how sketches are stored in LSH based sketch memory). Since sketches are fed to the programs indexed by their context, the context can be viewed as function-pointer and the
4

---

Under review as a conference paper at ICLR 2022
sketch can be viewed arguments for a call to that function; multiple arguments can be passed by using a compound sketch. Programs that call other modules can be represented as a computation DAG over modules at the nodes.
INDEPENDENT TASKS AND ARCHITECTURE vO
Our learning problem follows formulation similar to Ruvolo & Hatoon (2013). In lifelong learning ..... system, we are facing sequence of supervised learning tasks: zo....., Z (Tmmo)) In contrast
to Ruvolo & Eaton at each step we will generally obtain a single input (in the form of sketch (81,x(),
that contains DATA (1) E x TARGET y(t) E )x()) and task descriptor sketch (vector) St. where the tth task is given by a hidden function g(()) x(()) + ))(()) that we want to learn, and (x(1))))) = n² We assume that that the tasks are uniformly distributed, and the distributions over task data are stationary: i.c.. at each step, the task is sampled uniformly at random, and for the sampled task t, the data sampled independently from fixed distribution ('))) for t. In this setting, we assume the task functions are all members of common, known class of functions M for which there exists an efficient learning algorithm AM, i.e., AM satisfies standard PAC-learning guarantee: when provided with sufficiently large number of training examples M, with probability 8 AM returns function that agrees with the task function with probability at least 1 on the task distribution. For example, SGD learns certain class of neural networks M with a small constant depth. Indeed, we stress that this setting does not require transfer across tasks.
Our architectures are instantiated by choice of hash function h and a context function f. Archi- tecture vÔ uses very simple context function f: it projects the sketch down to the task descriptor t, dropping the DATA x(t) and TARGET ( components. (Other combinatorial decisions in the routing module are NO-OPs.) Each time we receive an input learning sample, we will call Alg. (input is a single sketch).
and confidence parameter ō > 0 and N independent tasks, each of which require at most M = M (c. 5) examples to learn to accuracy 1 1-6 E with probability 1-8, 8, and training data as described above, with probability 1 (N 1)8, Architecture vO learns to perform all N tasks accuracy at least 1 in (M log N steps.
Claim 3.1. Given an error rale
HIERARCHICAL LIFELONG LEARNING AND ARCHITECTURE V1
We follow a similar problem formulation as in Sec 3 but in this case task can depend on other tasks. We assume that the structure of dependencies can be described by degree-d d directed acyclic graph (DAG), in which the nodes correspond tasks. Each task t depends on at most d other tasks 1' indicated by the nodes in the DAG with edges to its node, and the task is to compute the ((G)) where (i(1) E MMM If f4,
........4 l'2 are sources in the DAG (no incoming edges) then ((()) M. We assume that all tasks share a common input distribution. We will call the functions from M atomic modules, since they are the building blocks of this hierarchy. We will call functions that call other functions in the DAG, such 2(0)) above, compound module. As before, we assume M is learnable function class. However, g(t) might not belong to learnable function class due to its higher complexity. Here, we will assume moreover that the algorithm AM for learning M is robust to label noise. Concretely, we will assume that if an c-fraction of the labels are corrupted by an adversary, then AM produces an (ccuaacera function. We note that methods are known to provide SGD with such robustness for strongly convex loss functions, even if the features are corrupted during training (Diakonikolas et al. 2019) (see also, e.g., [i et al. 20200;; Shah et al. (2020). In this setting, we assume that the tasks are again sampled uniformly at random, and that the data is sampled independently from a common, fixed distribution for all tasks.
corresponding function g(0)) g(0) (00) (3(6)
As with the architecture vO, v1 uses any locality sensitive hash function h and context function that projects the input sketch down to the task descriptor, discarding other components. The primary modifications are that
1. v1 tracks whether tasks are "well-trained," freezing their parameters when they reach a given accuracy for their level of the hierarchy, and
5

---

Under review as a conference paper at ICLR 2022
2. until "well-trained" model is found, we train candidate models for the task in parallel that use the outputs of each possible subset of up to d well-trained modules as auxiliary inputs.
We will maintain a global task level L, initially O. We define the target accuracy for level-L tasks to be Et. = (2dC') where C' is the constant under the big-O for the guarantee provided by our robust training method; we let Mr denote the sample complexity of robustly learning members of our class M to accuracy 1 -Cdc, with confidence 1 -- when a 1 - -accurate model exists. We check if any tasks became well-trained in level L 1, and if so, for all tasks that are not yet well-trained, we initialize models for all combinations of up to d - 1 other well-trained tasks for each such new task. Each model is of the form á(Ø;; (z),..., ....,,, (a:)), where i1 ... is (k S d) is the corresponding subset of well-trained tasks such that at least one has level I. 1. On each iteration, the arriving example is hashed to bucket for task t. We track the number of examples that have arrived for t thus far at this level. For the first M' examples that arrive in a bucket, we pass the example to the training algorithms for each model for this task, which for example completes another step of SGD. Once Mr examples have arrived, we count the fraction of the next O 2 log ) examples that are classified correctly by each of the models. We thus check if its empirical accuracy is guaranteed to be at least 1 - EL with high probability. If the empirical accuracy is sufficiently high, we mark the task as well-trained and use this model for the task, discarding the rest of the candidates. Once all log ) examples since the global level of the tasks are well-trained or have obtained ML O eL incremented to L, we increment the global level to L + 1.
Lemma 4.1. Suppose at each step, task I is chosen uniformly random from the set of lasks {ti..... .........] .ty} } in a DAG of height& f, along with one random sample (x. y) where (z) =y. Then after LMN (n(1/8) steps all the tasks will be well-trained (training error rate S for each module at level L) w.h.p. We will call SGD OEE (2+d)) In(1/5)) times during the training. Here, M is the upper bound of all ML.
In the above discussion we argued at an algorithmic level and ignored the specific architecture details of which buckets the (2) candidate modules are trained and how eventually a single compound module gets programmed in the bucket h(s)). See Appendix E for those details.
5 ARCHITECTURE V2: TASKS WITHOUT PRECISE EXPLICIT DESCRIPTIONS
We follow a similar problem formulation as in Sec. 4 However now clear task descriptors may not be provided externally, but may implicitly depend on the output of a previous module. (detailed examples in Appendix D The following definitions and assumption differ from Sec.
Definition 5.1 (Tasks). Let 24 be a space of all (potentially recursive) sketches that include the input and output of all modules. (ll can be polymorphic, that is, it can contain multiple different data types). Each task 4 is a mapping: : U - U. The input distribution of 1,, D;, is supported on U.
Definition 5.2 (Latent dependency DAG). The latent dependency DAG a DAG with nodes corre- sponding to tasks 1,, .., 'N and edges indicating dependencies. Each task at an internal node depends on at most d other tasks (d may not be known to the learner, but is a small quantity).
Definition 5.3 (Latent circuit). Given a dependency DAG, for each task t, there latent circuit with gates (nodes) corresponding to the tasks E that it depends on. In this circuit for 4, there are (potentially) multiple sinks (nodes with no outgoing edges). The output of these sinks will be the inputs to some atomic module, which gives the output of t, There are multiple atomic internal modules for each f; and the circuit routes each example to one of these modules. Each t; is "vague" in the sense that there are multiple modules that can cater an example of this task.
Definition 5.4 (Hidden task description / Context). Given the circuit of each f, there is a fixed (unknown) subset of the outputs of the circuit that give a context value that uniquely identifies 4;- There exists bound d on the number of context values for 4, There is one atomic module for each context. We let G be an integer such that Σ, 9: G.
Assumption 5.5 (No distribution shift). For a latent dependency DAG and circuit for task t;, sup- pose t; is one of the nodes in the circuit of task f;, and let x ~ DD be the input to t,. For each x; computed as an input to 1, when the circuit is evaluated on x, we assume x, belongs to D,.
Given the problem set-up above, we present our main result for this section:

---

Under review as a conference paper at ICLR 2022
Theorem 5.6 (Leaming DAG using v2). Given latent dependency DAG of tasks over N nodes and height l, and a circuit per internal node in the DAG, there exists an architecture v2 that learns all these tasks (up to error rate as defined in Sec with at most (all steps.
5.1 CONTEXT FUNCTION AS A DECISION TREE
In architecture v2 we use a more complicated context function f extract the stable context for each task. The context function can be implemented as modular decision tree where each node separate module. We are given compound sketch [S,,.., where we assume the sketches are ordered by importance (e.g., based on frequency: if there are hash buckets we will only track contexts that appear at least (11/m) fraction of the time, while others get "timed out" - we assume m 2 (220lt+dlog((
We apply f recursively and then over f(S1). f., f(kk from left to right in a decision tree where each branch either keeps or drops each item and stops or continues based on what obtains the highest rewards, tracked at each node (subtree) of the decision tree. Thus the context function can be implemented as recursive call to a decision tree [(S),.., Sk)) Decision (reisionTree(((SS]]]] ( ((...((())). (see Alg.2 each node of the decision tree will be implemented in a separate module (hash bucket).
Algorithm 2 Decision Tree
DecisionTrre(((,..C...) Wrlk(a) [C1, ..kl)
Walkl,, [C,, ... C branch-based based-on- -nnargaax (
reward(b(TTREE- -ALK.. (.ppend(CC)DD :Tree Walkeaaa...pppnnCCC [C++1..., C+1) / keep C2 in 1 and proceed to next field
reward(t(TREEE-WALK I])]): TreeWalk(1, [C,+1,.., C+)) / drop C₁ and proceed to next field
*/
teward(t(TTREE-WALK
) TreeWalk((, (]) / exit the
walk and output */
) 1* I is the subset of fields from the sketch from the prefix processed far, C., Cg is the remaining
part of the sketch. is used as the context for this current decision tree node and [C1..., C ] is the input sketch. Each distinet value of / separate decision tree node */
The branch statement is branching (ULKK. ID), or h(TRREE-WLLK, Lappend(END-WALR BEEEND-WAL--YMBBOLL SYMOL)) based on the re- wards; each bucket continues the decision tree walk with the rest of the entries in the list of con- texts. Note that during training the branch will be probabilistic softmax rather than a deterministic argmax, with a temperature parameter T that controls the exploration of the branches and decreases eventually to
of the three buckets: h(TTREE-W WALK,, Lappend(C.)))
0: thus the probability of each branch is proportional to e Raranch/T where Roranch is the reward of the branch. Initially all rewards are 0 and so all branching probabilities are all equal 1/3 (but there could be some other priors). Over time the temperature is lowered, the probability concentrates gradually on the bucket with maximum reward. See Appendix (F for full details.
Claim 5.7. P is the initial probability of taking the optimal reward path to the leaf in the De- cisionTree algorithm above, there is a schedule for the temperature in Algorithm 2 so that in O(1/plog log 1/6) tree walk steps the modules at the nodes the tree will converge that the de- cision tree achieves optimal rewards with high probability 1
Proof. We will keep very high initial temperature T (say oo) for ((1/p) log(1/6)) tree walk steps and then suddenly freeze it to near zero (which converts the softmax to max) after these steps are finished. In these initial steps with high probability been visited at least 1/5 times. Since each node is tracking the optimal rewards in its subtree, the recorded best path from root will have tracked at least this optimal reward.
8 the optimal path to the leaf will have
5.2 INCREMENTALLY LEARNING A NEW NODE (IMPLICIT TASK)
In this subsection provide an induction proof sketch for Theorem 5.6 In the previous subsection, we saw how the context function can be implemented as a probabilistic decision tree. Other func- tions of the routing module that involve making subset-choosing decisions (such Lines 13 & 21
7

---

Under review as a conference paper at ICLR 2022
in Alg. Ih: for example, selecting subset of d pre-existing modules children of new task in vl can be done using a separate decision tree (e.g. Alg. 2) where one needs to select a subset of at most d. This again becomes very similar to the operation of the context function: we just need to input all matured modules of the previous layer to Alg. 2 and find the I d child modules. In architecture v2 any subset-choosing decision in architecture
be done by using Alg. 2.
The learning algorithm follows the framework of Alg The circuit routing is also done by Alg 2 we feed all the (()))()) candidate edges of the eircuit to Alg. 2 which finds the correct subset. The inductive guarantee that lower-level tasks are well-trained comes from the bottom-up online algorithm of Modules are marked as mature based on performance, and new modules are only built on top of mature previous nodes. The probability of picking the right sequence of decisions for perform the new task is p 1/20(d +d (Ng(4) (including which identifying which previous possibly implicit tasks it depends on and wiring them correctly with the right contexts) and it takes M examples to train the task, then the task can be learned in O (o steps per atomic module (see Appendix(Ffoor full details).
6 EXPERIMENTS
We empirically examine two tasks for which learning benefits from using a modular architecture in this section. We compare an "end to end" learning approach to modular learning approach which explores a DAG of previously learned tasks probabilistically.
6.1 LEARNING INTERSECTIONS HALFSPACES
Learning intersections of halfspaces has been studied extensively, see for example (Klivans & Sherstov 2009). We first describe the experiment setting. Let K be the number of hyperplanes, 1 feature space dimension, generate the following data: hyperplane coefficients wi R k 1, 2, ..., K whose components are independent and follow standard normal distribution; 2. ture 2. E RDD
1,2, N. independently chosen uniformly from 1-, And we have = [E[]K]] wwn x;), where sgn is the sign function.
While learning single halfspacc K = 1 is easily solved by a two-layer network with ReLU ac- tivation, it becomes much more difficult for neural networks learn when K grows. This can be observed in Figure-Z] where a 3-layer neural network is used to learn the intersections.
For modular approach, we follow Algorithm 3 which a simplified version of Algorithm | and it probabilistically route to sub-modules. The input data are batches of triplets (kk, vt hej))
where B is the batch size, [K + 1] is the task id, ot ... ΠkEE(1] vL and we maintain a task list T and module list d
K +1 Ta. 2/² sgn(ww 22)) for x
l [K] and y k+1
The results are plotted in Figure 2 with K = 1,2, .... 10. D 100, Patomic 0.5 and Peompound 0.75. For the modular approach, all the modules are 3 layer fully-connected network of the same size and are trained for 10 epochs. For the end-to-end approach, single 3 layer fully-connected network with 10x hidden units of the modular models and is trained until convergence. We observe for large K (K 2 in the figure), the end-to-end approach fails at the task while the modular approach continues to have good performance. See appendix for more details.
6.2 FIVE DIGIT RECOGNITION
In this experiment, we compare the "end to end" approach and a modular approach for the task of recognizing 5-digit numbers, where the input is image that contains 5 digits from left to right, and the expected output is the number that is formed from concatenating the 5 digits. This task is described in Example 2 of Appendix F. Note in this task, have 3 sub-tasks: task-1 is single digit recognition, task-2 is image segmentation, and task-3 is 5 digit recognition.
For the "end end" approach, we train a convolutional neural network to predict the digit number (see appendix for more details), For the modular approach, the input data are batches of triplets
((k, x Mi )E(BB) where B is the batch size, l [3], x xx.2) x
(k) (k)
I; is the image.
8

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Probabilistic routing algorithm
Input: Batches of {(k, zx :. ())))) k the same within batch.
Constants: Patomic: Poompound-
Initialization: Set of modules + 0,
set of task ids [K +
Repeat the following steps:
1. w.p. Patomic, train an atomic mod- ule Φk that maps æę to y (note we keep separate copy of Ob for each different DAG structure based on iteration choices in step 2 from the original input to 2.)). ). If training succeeds, set 6R to be the DAG upto Φx and add it to 4.
10-
e2e modular
accuracy
0.8
0.7
2. w.p. 1 Patomics for each E Φ, w.p. Prompound, set x. +- concat(x; ())+)).
0.5
Return M.
number halfspaces
Figure 2: Intersection of halfspaces Left: Pseudocodes for the modular approach ("w.p." is abbrevi- ation for "with probability"). Right: Modular approach continuous to have good performance while end-to-end approach fails learn for K 2
method
accuracy 74.5 + 4.5 %
steps (1-digit) steps (segmentation)
steps (5-digits) 18760 18760 + 9380
end-to-end
NA
NA
modular
92.0 0.5%
2560
640
Table 1: Comparison of end-to-end and modular algorithms for 5-digits recognition: accuracy and number of training steps for different tasks to succeed. Note here each step is processing one batch with batch size of 128, and we consider a task successful if the accuracy above 90%.
Vi is the single digit label, (2) is segmentation coordinate pairs (upper-left and lower-right coordinates), and y/ the 5 digit number label. We also maintain a task list and module list 6. For training atomic module in Algorithm-3] we only allow the module to take inputs of the same modality (i.c. either only image or only digits, discarding the others).
We construct the training and test datasets by concatenating images from the MNIST dataset. The results of the two approaches are compared in Table We observe the modular approach achieves higher accuracy and has less variance with the same training steps.
7 DISCUSSION AND FUTURE WORK
We saw uniform continual learning architecture that learns tasks hierarchically based sketches, LSH, and modules. We also show how a knowledge graph formed across hash buckets as nodes and formally show its utility (for e.g. for finding common friends in social network) in Ap- pendix Extensions the decision tree learning to solve reinforcement learning tasks are shown in Appendix H Although our architecture works even with noisy but well-separated contexts (see Appendix DD. A weakness of our work is that we have ignored how logic language could be handled in this architecture while perhaps there could be separate compound modules for those kinds of tasks, we leave that topic open.
inputs
labeled with unique task description vector,
REFERENCES
Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate neighbors. In Proceedings of the sevet-seventh annual ACM symposium on Theory of computing, pp. 793-801, 2015.

---

Under review as a conference paper at ICLR 2022
Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond hashing. In Proceedings of the twenty-fifi annual ACM-SIAM symposium on Discrete algorithms, pp. 1018-1028. SIAM, 2014.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in neural information processing systems, pp- 2015.
2015.
Andrei Z Broder.
On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB 170111, pp. 21-29, IEEE, 1997.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388, 2002.
Zhiyuan Chen and Bing Liu. Lifelong machine learning. Synthesis Lectures on Artificial Intelligence and Machine Learning, 12(3):1 1077 2018.
Tlass Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: A robust meta-algorithm for stochastic optimization. In International Conference Machine Learning, pp. 1596-1606. PMLR, 2019.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.33661 2021.
Nicholas T Franklin, Kenneth A Norman, Charan Ranganath, Jeffrey M Zacks, and Samuel J Ger- shman. Structured event memory: A neuro-symbolic model of event cognition. Psychological Review, 127(3):327, 2020.
Badih Ghazi, Rina Panigrahy, and Joshua Wang. Recursive sketches for modular deep learning. In International Conference Machine Learning, pp. 2211-2220, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi cient? arXiv preprint arXiv: 2018.
Adam R Klivans and Alexander A Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, -51:22-1 2009.
Mingehen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust label noise for overparameeterized neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 4313-4324. PMLR, 2020.
Rina Panigrahy. How does the mind store information?, 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual 2021.
models from natural language supervision. arXiv preprint
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv:1606.04671 2016.
Paul Ruvolo and Eric Eaton. Ella: An efficient lifelong learning algorithm. In International Confer- ence on Machine Learning, pp. 507-515. PMLR, 2013.
Vatsal Shah, Xiaoxia Wu, and Sujay Sanghavi. Choosing the sample with lowest loss makes sgd bust. In International Conference on Artificial Intelligence and Statistics, pp. 2120-2130. PMLR, 2020.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gate mixture-of-experts layer. arXiv preprint arXiv: 1701006700. 2017.
Daniel L Silver, Qiang Yang, and Lianghao Li. Lifelong machine learning systems: Beyond learning algorithms. In 2013 AAAI spring symposium series, 2013.
10

---

Under review as a conference paper at ICLR 2022
Ray J. Solomonoff. A system for incremental learning based algorithmic probability. In Pro- ceedings of the Sixth Israeli Conference on Artificial Intelligence, Computer Vision and Pattern Recognition, pp. 515-527, 1989.
Xin Wang. Rina Panigrahy, and Manzil Zaheer. Sketch based neural memory for deep networks. In AISTATS, pp. 2211-2220, 2021.
Jaehong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. In International Conference on Learning Representations, 2018.


Reviews:
[{"review_id": "tUVlbjU3E6", "reviewer": "Reviewer_yxwW", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The major selling point of this paper for me is that the authors actually provide theoretical analysis and error bounds for the learning of a modular learning strategy. While there are a number of modular approaches in the literature, I am not aware of any that have provided this type of analysis. I also appreciate that the authors try to provide analysis for more challenging settings including those where tasks depend on other tasks and no task boundaries are directly provided. \n\nOn the other hand, one negative for me about this paper was the lack of clarity, particularly when explaining what a sketch actually is. The authors try to use very general wording in some places, but for me it began to really loose any meaning. I think it would be nice to at least walk through exactly how this all works in one example. Another thing that could really improve the paper in this regard would be to provide concrete connections to past modular architectures in the literature. In particular the following papers seem relevant to contrast with:\n\n\"Routing Networks: Adaptive Selection of Non-linear Functions for Multi-Task Learning\" Rosenbaum et al., ICLR-18 \n\"Modular Networks: Learning to Decompose Neural Computation\" Kirsch et al., NeurIPS-18\n\"Automatically Composing Representation Transformations as a Means for Generalization\" Chang et al., ICLR-19\n\"Recursive Routing Networks: Learning to Compose Modules for Language Understanding\" Cases et al., NAACL-19 \n\"Routing Networks and the Challenges of Modular and Compositional Computation\" Rosenbaum et al., 2019\n\nIn comparison to the above papers, for example, the domains considered in this paper are quite toy and minimal. While I appreciate that the authors also provide theoretical results, it is hard to get much out of these experiments. Additionally, even beyond the environment complexity considered and variety of domains, there are not many interesting models considered in each experiment either. There are a bunch of potential modular learning baselines that could be considered. Moreover, even just considering ablations of the proposed approach i.e. the choice of hashing etc would be an improvement. \n", "summary_of_the_paper": "The authors propose a modular architecture for multitask learning in the presence of hierarchically structured tasks leveraging sketches and locally sensitive hashing. They further provide proofs and error bounds about how the proposed architecture can learn tasks while leveraging access to previously learned subroutines. The authors additionally provide extensions to the proposed architecture in the case of tasks depending on other tasks and lack of clear task boundaries. Empirical studies are conducted for this modular approach in comparison to end-to-end models on synthetic domains related to learning the intersection of half-spaces and MNIST digits. ", "summary_of_the_review": "I think there are some major positive aspects to this paper including that the authors provide theoretical analysis of their modular approach, which is rare in the literature. Additionally, the authors discuss extensions of the approach to more ambitious settings. On the other hand, there is lack of clarity in the writing in some places and the paper lacks positioning with respect to existing modular approaches in the literature. The empirical evaluation of the approach is very limited in comparison to prior modular architectures, which makes me question if there are some undisclosed scalability concerns. As such, I lean towards rejection at this time. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZMu23zRnkhn", "reviewer": "Reviewer_kTWq", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "## Strengths\n\n1. The paper looks at \"lifelong learning\" from a theoretical perspective. I think the community will benefit from more works in this research direction.\n\n2. While the paper focuses on theoretical contributions, it does include some empirical results to show that the proposed approach works in practice.\n\n## Areas for improvement\n\n1. The problem is not well scooped. The paper is focusing on the sequential multi-task learning where the agent can come across a task multiple times. One can argue that this is also a form of lifelong learning (and while I do not have a strong opinion here, I am okay if the paper wants to consider this setup as a lifelong learning setup). Contrast this with the more common lifelong learning setup where the agent does not see the same task multiple times and has to deal with challenges like catastrophic forgetting. Note that I am not arguing that one problem (instance) is better/more important than the other. I am highlighting that it is important to highlight the setup (instead of pitching the work as the general lifelong learning setting).\n\n2. Very limited related work - I understand that the paper is focusing on hierarchical task distributions but there is much more relevant work than just the 2 papers cited on page . eg https://sites.google.com/view/cl-theory-icml2021 Similarly, RL has a rich literature on hierarchical learning (eg Options framework, Feudal Networks etc). Work on modular networks should be cited eg https://arxiv.org/abs/2012.12631. Other works on lifelong learning should also be cited eg: https://www.sciencedirect.com/science/article/pii/S1364661320302199 (these are pretty much the first works that came up on a quick google search). \n\n3. The paper is hard to understand with many important details/definitions missing. It will help with Section 2 is moved before section 1.1 There are several assumptions/statements but their role is not clear. For example, it is assumed that the tasks are sampled uniformly and datapoints are sampled using a fixed distribution from the task. What is the nature of this \"fixed distribution\" Does the nature matter or it can be any fixed distribution? What parts of the algorithm depend on this assumption. What happens if the task distribution is not stationary (but data distribution within each task is stationary) or the other way round. Since the paper is focusing on the theoretical aspects, it is important to explain/outline the effect of these asumptions.\n\n4. I am not sure of the novelty and significance of the paper. A lot of previous works have looked at the idea of using modularity for in context of hierarchal/multi-task/compositional learning https://arxiv.org/pdf/1611.01796.pdf, learning composable modules/representations https://arxiv.org/abs/1807.04640 or routing information/representation through modules / using modules recursively: https://openreview.net/forum?id=mLcmdlEUxy-\n\n5. It is not clear how to use the proposed approach in practice. I understand that the work is focusing on theory (and I am not asking for non-toyyish experiments) but it is not clear as to how obtain the atomic tasks (to train the atomic modules) given standard tasks. Moreover, for half-spaces and five digit recognition, it is not clear how well do standard modular networks perform, just limiting the value of empirical results.", "summary_of_the_paper": "The paper proposes a modular architecture for lifelong learning of hierarchically structured tasks with some theoretically guarantees. The paper includes some experiments, on simple domains, with a single baseline.\n", "summary_of_the_review": "Please note that my initial review of the paper is based on what I understood so far. I look forward to the author's response and interacting with them to understand their approach better. I encourage them to initiate a conversation sooner rather than later. I would be very happy to change my scores as I better understand the contribution/significance of the work.\n\nIn the current stage, the paper is missing several important details, making it hard to understand if the paper is novel/significant or not. Several important references are missing and it is not clear how does the method compare against standard modular networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9QKfInxSg7", "reviewer": "Reviewer_GsU1", "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": "**Disclaimer**\n\nAlthough I have built quite an expertise in continual and deep learning, my understanding of learning theory and theoretical computer science is still pretty shallow. For this reason, I did not fully understand the ideas presented in the paper. I will thus provide a pretty superficial review along with a low confidence score.\n\n**Strengths**\n\nThe authors provide some algorithmic theoretical guarantees in a field where they are mostly absent, namely continual learning\n\n**Weaknesses**\n\n I have found the architecture quite involved to understand. If the paper is addressed to researchers working on learning theory and/or sketches, then this is probably fine. \n\nIf however, the intended audience is your average continual-learning researcher, I think that the manuscript need works. Although most of the introduction was easy to follow, I found the remaining sections cumbersome (again, it could be because of my background). I found that section 3,4,5 bombards the reader with a plethora of architectural components, without ever providing some kind of intuitions on why any of them are important for a continual-learning system. My perspective is thus: if the main subject is continual learning, then the manuscript needs a major revision.\n\nLastly, the continual-learning aspect of the experiments escapes me. If they are continual-learning experiments, the authors should clearly explain the how the data distribution is non-stationary.\n \n\nMy perspective is that", "summary_of_the_paper": "This work introduces a continual-learning architecture that combines elements for sketches, hash functions, modules and routing.\nTheoretical guarantees are provided for the performance of the architecture. \nSome experiments seem to support the advantage of the proposed architecture over conventional deep learning ones.", "summary_of_the_review": "See Disclaimer above", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4Umtxr-w3kl", "reviewer": "Reviewer_RKp7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "############## Strengths ##############\n\n1. The problem at hand, modular lifelong learning, is of interest to the lifelong/continual learning community\n2. This is one of the few works that addresses lifelong learning from a theoretical perspective\n\n############## Weaknesses ##############\n\n1. The paper is organized in a way that is very hard to follow, and in particular the majority of the technical details are left to an 18-page appendix\n2. The theoretical results appear to be minor\n3. The empirical analysis is minimal\n\n\n############## Arguments ##############\n\nI believe that the line of work proposed in this paper is quite interesting and relevant: modular lifelong learning from a theoretical perspective. \n\nHowever, I had a very difficult time following the submission. The authors start with a subsection of the introduction providing a large set of detailed technical descriptions of the approach before even introducing the concepts or the motivation behind them. I think it would be best if this section instead started with just high-level explanations based on \"functions\", \"pointers\", and \"arguments\", with only a mention about how sketches and LSH are the mechanisms to implement these ideas. Then, after the reader is comfortable with the overall ideas, the formal concepts may be introduced and then the technical description can be made in terms of these formal concepts. In particular, a one sentence summary of (my understanding of) the approach is that each input is hashed and this hash is used to select the module that will be used to process the input. This is not fundamentally different than e.g. gating nets or any sort of clustering-based routing. The whole paper could be made much clearer by providing intuitive descriptions ahead of the technical details. More critically, the manuscript repeatedly uses technical descriptions of e.g. sketches as a means for providing intuition about the approach, but I believe that sketches should be used as only a tool for deriving results and the concrete architecture, but not as a means for providing intuitive descriptions: modularity can be understood very well without the introduction of sketches. Moreover, this repeated use of sketches takes up a lot of space for explaining insights and intuitions that are _not_ part of the contributions of this work, but of Ghazi et al. (2019). Instead, a concrete, brief definition of sketches should be given, and then the intuitions be built more broadly. Incidentally, for all the details, properties, and examples given, sketches are never actually defined. I thought they were their dense representations, but the end of Section 2 indicates that they are _converted_ into dense representations. It seems like therefore they are actually data structures like sets, trees, tuples... Or maybe I'm wrong and sketches are indeed vectors and the compound structures are built as described in the recursive computation.\n\nIn terms of the actual contributions, I am concerned that the theoretical results obtained are very minor. At a high level, in my understanding, the authors make a large set of assumptions that in summary enable the agent to learn near-perfect models for each task and perfect combinations of modules via exhaustive search. It is unclear how much insight this provides, and the technical tools used for showing these results (sketches) are not a contribution of this paper. More concretely:\n- From the problem definition, it seems that if there are N possible tasks, then at each time step one of these N tasks is uniformly sampled. This means that over the O(MN log N/delta) steps, each tasks is seen ~M log N/delta times. This doesn't really seem to match any common lifelong learning formulation, but instead seems closer to an interleaved version of multi-task learning. While Ruvolo and Eaton (2013) also assumed that tasks were drawn in some stationary fashion from a distribution over tasks, they did _not_ assume a fixed set of N tasks, and therefore the probability of task repetitions was negligible (and, in practice, in their experiments tasks were never repeated). \n- In case of the DAGs, the authors show that if the tasks indeed form a DAG and the agent is allowed to keep track of all possible DAGs with hashing and context functions that perfectly capture task relations, then the agent is able to provably learn to solve the tasks. Plus, there is not even a true lifelong setting. These assumptions seem to oversimplify the problem to the point that any insights gained from these results are not really useful for any realistic setting. \n\nThis wouldn't necessarily be a problem if the submission included substantial empirical evaluations that validated the proposed approach. However, the experiments fall short from a proper empirical evaluation for a lifelong/continual learning paper. The authors consider only two toy problems and show that their method is capable of working better than a vanilla non-modular approach. Given the fact that the theoretical results appear to be relatively minor, I would encourage the authors to carry out a more complete empirical evaluation, similar to that of other lifelong learning works.\n\n############## Additional feedback ##############\n\nThe following points are provided as feedback to hopefully help better shape the submitted manuscript, but did not impact my recommendation in a major way.\n\nIntro\n- So far the proposed problem is intriguing\n- Missing cites to PAC lifelong learning [1] and other compositional/modular lifelong learning works [2, 3]\n\nSec 1.1\n- The discussion of memory over programs vs data being artificial seems to be very tangential to the point\n- I'm not sure I get the purpose of the comparison to scene segmentation. Many of the cites and remarks seem pretty arbitrary\n- I have a lot of faith in the contributions this paper will produce so far, but it almost feels like it was written deliberately to confuse readers. It's not poor language or grammar at all, just completely unclear structure and a level of technicality that seems to bury intuitions and motivations so deep that they're almost impossible to uncover. Should have started with the \"overall loop\" intuition, then inputs/outputs, then hashes... but it's all flipped around, there's a lot of back and forth, ideas repeated in different orders at different points...\n\nSec 2.1\n- No intuition is given here about how sketches to combine into a compound sketch might be chosen. This is likely chosen somehow based on \"frequent subsets\" as suggested in the penultimate paragraph of page 2, but this is so far not explained or motivated.\n\nSec 3\n- Last paragraph on page 4: shouldn't it be \"projects the sketch down to the task descriptor [s_t]\"?\n- Before stating the algorithm and claim, the authors should describe in plain language what the meaning of choosing f(x_t,y_t,s_t) = s_t is. I believe it simply says that there will be one independent function per task (as suggested by the Section heading), but this is never stated explicitly. This is particularly unclear because the hash function and the task descriptor are not defined, so it's unclear whether \"similar\" tasks would also be mapped to the same function, nor what \"similar\" tasks would even mean in this context. \n\nSec 4\n- Authors state that \"like in section 3\" they use any LSH, so one might assume that this is also the case in Sec 3, although it wasn't stated\n\nAppendices\n- The appendices are incredibly long (18 pages!) and the authors claim that they contain most of the details omitted in the main paper (like what the actual architectures are and so on). I did not read the appendices in detail. \n- Beside these, they include seemingly tangential sections like the knowledge graph, connections to RL, a card-game case study, and even a \"Misc\" appendix. Given the overall length of the paper+appendices, it would perhaps be useful to consider cutting these tangential discussions. \n\nTypos and grammar\n- Sec 2, par 3: a sketch chat can... --> a sketch that can...\n- Sec 2, par 3: \"However the sketch may be more complicated like an object for example the <person-sketch>could in turn be set of such pairs f[NAME,<name-sketch>], [FACIAL-FEATURES,<facial-sketch>], [POSTURE,<posturesketch>]g.\" --> this is a run-on sentence and has missing words and spaces\n- Throughout Sec 2 there are missing words and periods, and grammar errors like subject-verb agreement.\n\n\n[1] Pentina and Lampert. A PAC-Bayesian bound for lifelong learning. ICML 2014\n\n[2] Mendez and Eaton. Lifelong learning of compositional structures. ICLR 2021\n\n[3] Veniat et al. Efficient Continual Learning with Modular Networks and Task-Driven Priors. ICLR 2021\n", "summary_of_the_paper": "The submission proposes an approach to lifelong learning using a sketch-based modular architecture. The primary contributions of the paper are proofs of the learnability of certain classes of tasks with three different choices of modular architectures. The algorithms are also evaluated empirically on toy supervised learning tasks. \n", "summary_of_the_review": "Unfortunately, I recommend the rejection of this work. The submission lies at the intersection of theoretical and empirical research, yet falls short in both these axes in terms of results. In particular, the theoretical results seem sufficient for an approach that is empirically applicable to realistic problems, yet is evaluated on a set of simple toy problems only. On the other hand, the empirical results on toy data seem sufficient for an approach for which there are major theoretical results, but the theorems in the submission are, in my understanding, fairly minor. The manuscript's structure is quite odd, which makes it hard to follow and contextualize the contributions, so substantial editing might change my overall perception of the work. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper develops an approach to modular lifelong learning over hierarchical tasks, proving the learnability of certain task classes under different modular architectures, with empirical evaluations on toy supervised tasks. The authors are to be commended for being one of the few works that develop lifelong learning theory. However, the reviewers found the theoretical contributions to be relatively minimal and that the empirical work needs to provide more substantial insight before it is ready for publication. Moreover, the reviewers had substantial concerns with the paper's overall presentation, in many cases finding the paper's organization confusing with many asides and critical details relegated to the appendices. The confusing presentation especially needs to be remedied, and the authors are advised to take the reviewers' concerns into consideration when preparing future versions of their manuscript.

On a minor point, the reviewers identified several places where the paper didn't cite or develop connections to relevant current literature. The authors might also be interested in connections to some much earlier work by Utgoff and Stracuzzi on many-layered learning (Neural Computation 14.10, 2002), which shares some high-level similarities to ideas explored in this paper.
Decision: Reject