Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces a continual-learning architecture that combines elements for sketches, hash functions, modules and routing.
Theoretical guarantees are provided for the performance of the architecture. 
Some experiments seem to support the advantage of the proposed architecture over conventional deep learning ones.
main_review: **Disclaimer**

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

**Strengths**

The authors provide some algorithmic theoretical guarantees in a field where they are mostly absent, namely continual learning

**Weaknesses**

 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. 

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

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

My perspective is that
summary_of_the_review: See Disclaimer above
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

main_review: ## Strengths

1. The paper looks at "lifelong learning" from a theoretical perspective. I think the community will benefit from more works in this research direction.

2. While the paper focuses on theoretical contributions, it does include some empirical results to show that the proposed approach works in practice.

## Areas for improvement

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

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

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

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

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

In 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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

main_review: ############## Strengths ##############

1. The problem at hand, modular lifelong learning, is of interest to the lifelong/continual learning community
2. This is one of the few works that addresses lifelong learning from a theoretical perspective

############## Weaknesses ##############

1. 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
2. The theoretical results appear to be minor
3. The empirical analysis is minimal


############## Arguments ##############

I believe that the line of work proposed in this paper is quite interesting and relevant: modular lifelong learning from a theoretical perspective. 

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

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

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

############## Additional feedback ##############

The following points are provided as feedback to hopefully help better shape the submitted manuscript, but did not impact my recommendation in a major way.

Intro
- So far the proposed problem is intriguing
- Missing cites to PAC lifelong learning [1] and other compositional/modular lifelong learning works [2, 3]

Sec 1.1
- The discussion of memory over programs vs data being artificial seems to be very tangential to the point
- I'm not sure I get the purpose of the comparison to scene segmentation. Many of the cites and remarks seem pretty arbitrary
- 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...

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

Sec 3
- Last paragraph on page 4: shouldn't it be "projects the sketch down to the task descriptor [s_t]"?
- 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. 

Sec 4
- 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

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

Typos and grammar
- Sec 2, par 3: a sketch chat can... --> a sketch that can...
- 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
- Throughout Sec 2 there are missing words and periods, and grammar errors like subject-verb agreement.


[1] Pentina and Lampert. A PAC-Bayesian bound for lifelong learning. ICML 2014

[2] Mendez and Eaton. Lifelong learning of compositional structures. ICLR 2021

[3] Veniat et al. Efficient Continual Learning with Modular Networks and Task-Driven Priors. ICLR 2021

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
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. 

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

"Routing Networks: Adaptive Selection of Non-linear Functions for Multi-Task Learning" Rosenbaum et al., ICLR-18 
"Modular Networks: Learning to Decompose Neural Computation" Kirsch et al., NeurIPS-18
"Automatically Composing Representation Transformations as a Means for Generalization" Chang et al., ICLR-19
"Recursive Routing Networks: Learning to Compose Modules for Language Understanding" Cases et al., NAACL-19 
"Routing Networks and the Challenges of Modular and Compositional Computation" Rosenbaum et al., 2019

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

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.
review_title: null

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