Venue: ICLR 2017 conference

Reviews:

final_score: rating: null
review_content: How do you backpropagate through the sampling procedures? Are the gradient estimates biased?

review_title: Backpropagation through the sampling operation

final_score: rating: 4: Ok but not good enough - rejection
review_content: I was holding off on this review hoping to get the missing details from the code at https://github.com/alexnowakvilla/DP, but at this time it's still missing. After going over this paper couple of times I'm still missing the details necessary to reproduce the experiments. I think this would be a common problem for readers of this paper, so the paper needs to be improved, perhaps with a toy example going through all the stages of learning.

As an example of the difficulty, take section 4.3. It talks about training "split block" which is a function that can assign each element to either partition 0 or partition 1. At this point I'm looking at it as a binary classification problem and looking for the parameters, loss, and how this loss is minimized. Instead I get a lot of unexpected information, such as "we must create artificial targets at every node of the generated tree from the available final target partition". What are these artificial targets, and how do they relate to the problem of training the splitter? An example that explicitly goes through this construction would help with understanding.

review_title: Promising idea but hard-to-reproduce in current state

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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

review_title: Nice problem statement, nut too immature to publish

final_score: rating: null
review_content: The paper begins with great desiderata, but even after several reads (Sorry for the delay) I still fail to see how much is hardcoded and much supervision the models receive. Am I correct that for sorting  you hardcode the architecture to the the extent that a perfect solution only requires the splitter to split by the first element and the merger to select all elements?

Please describe in more detail the implementation of he network on the tasks:
- what is the supervision at each level for each task, maybe provide examples for sorting?
- for sorting do you prevent the model from creating overlapping or incomplete partitions (the paper says that you sample, but you can essentially put an element to x1 or x2 depending on a binary variable, or make two tests, one whether the sample is in x1 and another that it is in x2). The first variant simplifies the task a lot.
- do you train the basis of the recursion? You train the sorter up to 8 splits, not until sets of 1 element are produced. Do you simply fire quicksort and sort the subsets? Does this mean that if the net provides 8 very unbalanced splits you will feed it with a properly sorted sequence of 256-8 = 246 numbers?
- can you explain why the weakly supervised convex hull network seems to be better than the strongly supervised one? 
- for sorting you implement the merger in a way that favors quicksort. Can you compare the performance on partially sorted data (in both directions) which is the true adversarial case for quicksort, rather than test the uniform and exponential distributions, that do not change the expected complexity of quicksort? The trivial solution of splitting on the first element of the set would work optimally under your dataset generation.



review_title: Please clearly state what parts of the models are trained

final_score: rating: 3: Clear rejection
review_content: I find this paper extremely hard to read. The main promise of the paper is to train models for combinatorial search procedures, especially for dynamic programming to learn where to split and merge. The present methodology is supposed to make use of some form of scale invariance property which is scarcely motivated for most problems this approach should be relevant for. However, the general research direction is fruitful and important.

The paper would be much more readable if it would start with a clear, formal problem formulation, followed by some schematic view on the overall flow and description on which parts are supervised, which parts are not. Also a tabular form and sample of the various kinds problems solved by this method could be listed in the beginning as a motivation with some clear description on how they fit the central paradigm and motivate the rest of the paper in a more concrete manner.

Instead, the paper is quite chaotic, switching between low-level and high level details, problem formulations and their solutions in a somewhat random, hard to parse order.

Both split and merge phases seem to make a lot of discrete choices in a hierarchical manner during training. The paper does not explain how those discrete choices are backpropagated through the network in an unbiased manner, if that is the case at all.

In general, the direction this paper is exciting, but the paper itself is a frustrating read in its present form. I have spent several hours on it without having to manage to achieve a clear mental image on how all the presented pieces fit together. I would revise my score if the paper would be improved greatly from a readability perspective, but I think it would require a major rewrite.
review_title: Interesting but extremely difficult read

Meta-review: The area chair agrees with the reviewers that this paper is not ready for ICLR yet. There are significant issues with the writing, making it difficult to follow the technical details. Writing aside, the technique seems somewhat limited in its applicability. The authors also promised an updated version, but this version was never delivered (latest version is from Nov 13).
Decision: Reject