Divide and Conquer with Neural Networks
We consider the learning of algorithmic tasks by mere observation of input-output pairs. Rather than studying this as a black-box discrete regression problem with no assumption whatsoever on the input-output mapping, we concentrate on tasks that are amenable to the principle of divide and conquer, and study what are its implications in terms of learning. This principle creates a powerful inductive bias that we exploit with neural architectures that are defined recursively, by learning two scale-invariant atomic operators: how to split a given input into two disjoint sets, and how to merge two partially solved tasks into a larger partial solution. The scale invariance creates parameter sharing across all stages of the architecture, and the dynamic design creates architectures whose complexity can be tuned in a differentiable manner. As a result, our model is trained by backpropagation not only to minimize the errors at the output, but also to do so as efficiently as possible, by enforcing shallower computation graphs. Moreover, thanks to the scale invariance, the model can be trained only with only input/output pairs, removing the need to know oracle intermediate split and merge decisions. As it turns out, accuracy and complexity are not independent qualities, and we verify empirically that when the learnt complexity matches the underlying complexity of the task, this results in higher accuracy and better generalization in two paradigmatic problems: sorting and finding planar convex hulls.
The basic idea of this contribution is very nice and worth pursuing: how to use the powerful “divide and conquer” algorithm design strategy to learn better programs for tasks such as sorting or planar convex hull. However, the execution of this idea is not convincing and needs polishing before acceptance. As it is right now, the paper has a proof-of-concept feel that makes it great for a workshop contribution. My main concern is that the method presented is currently not easily applicable to other tasks. Typically, demonstrations of program induction from input-output examples on well known tasks serves the purpose of proving, that a generic learning machine is able to solve some well known tasks, and will be useful on other tasks due to its generality. This contribution, however, presents a learning machine that is very hand-tailored to the two chosen tasks. The paper essentially demonstrates that with enough engineering (hardcoding the recurrency structure, designing problem-specific rules of supervision at lower recurrency levels) one can get a partially trainable sorter or convex hull solver. I found the contribution relatively hard to understand. High level ideas are mixed with low-level tricks required to get the model to work and it is not clear either how the models operate, nor how much of them was actually learned, and how much was designed. The answer to the questions did hep, nut didn*t make it into the paper. Mixing the descriptions of the tricks required to solve the two tasks makes things even more confusing. I believe that the paper would be much more accessible if instead of promising a general solution it clearly stated the challenges faced by the authors and the possible solutions. Highlights: + Proof-of-concept of a partially-trainable implementation of the important “divide and conquer” paradigm ++ Explicit reasoning about complexity of induced programs - The solution isn’t generic enough to be applicable to unknown problems - the networks require tricks specific to each problem - The writing style pictures the method as very general, but falls back on very low level details specific to each task
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Divide and Conquer with Neural Networks
We consider the learning of algorithmic tasks by mere observation of input-output pairs. Rather than studying this as a black-box discrete regression problem with no assumption whatsoever on the input-output mapping, we concentrate on tasks that are amenable to the principle of divide and conquer, and study what are its implications in terms of learning. This principle creates a powerful inductive bias that we exploit with neural architectures that are defined recursively, by learning two scale-invariant atomic operators: how to split a given input into two disjoint sets, and how to merge two partially solved tasks into a larger partial solution. The scale invariance creates parameter sharing across all stages of the architecture, and the dynamic design creates architectures whose complexity can be tuned in a differentiable manner. As a result, our model is trained by backpropagation not only to minimize the errors at the output, but also to do so as efficiently as possible, by enforcing shallower computation graphs. Moreover, thanks to the scale invariance, the model can be trained only with only input/output pairs, removing the need to know oracle intermediate split and merge decisions. As it turns out, accuracy and complexity are not independent qualities, and we verify empirically that when the learnt complexity matches the underlying complexity of the task, this results in higher accuracy and better generalization in two paradigmatic problems: sorting and finding planar convex hulls.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



The basic idea of this contribution is very nice and worth pursuing: how to use the powerful “divide and conquer” algorithm design strategy to learn better programs for tasks such as sorting or planar convex hull. However, the execution of this idea is not convincing and needs polishing before acceptance. As it is right now, the paper has a proof-of-concept feel that makes it great for a workshop contribution. My main concern is that the method presented is currently not easily applicable to other tasks. Typically, demonstrations of program induction from input-output examples on well known tasks serves the purpose of proving, that a generic learning machine is able to solve some well known tasks, and will be useful on other tasks due to its generality. This contribution, however, presents a learning machine that is very hand-tailored to the two chosen tasks. The paper essentially demonstrates that with enough engineering (hardcoding the recurrency structure, designing problem-specific rules of supervision at lower recurrency levels) one can get a partially trainable sorter or convex hull solver. I found the contribution relatively hard to understand. High level ideas are mixed with low-level tricks required to get the model to work and it is not clear either how the models operate, nor how much of them was actually learned, and how much was designed. The answer to the questions did hep, nut didn*t make it into the paper. Mixing the descriptions of the tricks required to solve the two tasks makes things even more confusing. I believe that the paper would be much more accessible if instead of promising a general solution it clearly stated the challenges faced by the authors and the possible solutions. Highlights: + Proof-of-concept of a partially-trainable implementation of the important “divide and conquer” paradigm ++ Explicit reasoning about complexity of induced programs - The solution isn’t generic enough to be applicable to unknown problems - the networks require tricks specific to each problem - The writing style pictures the method as very general, but falls back on very low level details specific to each task
assistant
The basic idea of this contribution is very nice and worth pursuing: how to use the powerful “divide and conquer” algorithm design strategy to learn better programs for tasks such as sorting or planar convex hull. However, the execution of this idea is not convincing and needs polishing before acceptance. As it is right now, the paper has a proof-of-concept feel that makes it great for a workshop contribution. My main concern is that the method presented is currently not easily applicable to other tasks. Typically, demonstrations of program induction from input-output examples on well known tasks serves the purpose of proving, that a generic learning machine is able to solve some well known tasks, and will be useful on other tasks due to its generality. This contribution, however, presents a learning machine that is very hand-tailored to the two chosen tasks. The paper essentially demonstrates that with enough engineering (hardcoding the recurrency structure, designing problem-specific rules of supervision at lower recurrency levels) one can get a partially trainable sorter or convex hull solver. I found the contribution relatively hard to understand. High level ideas are mixed with low-level tricks required to get the model to work and it is not clear either how the models operate, nor how much of them was actually learned, and how much was designed. The answer to the questions did hep, nut didn*t make it into the paper. Mixing the descriptions of the tricks required to solve the two tasks makes things even more confusing. I believe that the paper would be much more accessible if instead of promising a general solution it clearly stated the challenges faced by the authors and the possible solutions. Highlights: + Proof-of-concept of a partially-trainable implementation of the important “divide and conquer” paradigm ++ Explicit reasoning about complexity of induced programs - The solution isn’t generic enough to be applicable to unknown problems - the networks require tricks specific to each problem - The writing style pictures the method as very general, but falls back on very low level details specific to each task