Published as a conference paper at ICLR 2018 DIVIDE AND CONQUER 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 leverage with neural architectures that are defined recursively and dynamically, by learning two scaleinvariant atomic operations: how to split a given input into smaller sets, and how to merge two partially solved tasks into a larger partial solution. Our model can be trained in weakly supervised environments, namely by just observing input-output pairs, and in even weaker environments, using a non-differentiable reward signal. Moreover, thanks to the dynamic aspect of our architecture, we can incorporate the computational complexity as a regularization term that can be optimized by backpropagation. We demonstrate the flexibility and efficiency of the Divideand-Conquer Network on several combinatorial and geometric tasks: convex hull, clustering, knapsack and euclidean TSP. Thanks to the dynamic programming nature of our model, we show significant improvements in terms of generalization error and computational complexity.
This paper proposes to add new inductive bias to neural network architecture - namely a divide and conquer strategy know from algorithmics. Since introduced model has to split data into subsets, it leads to non-differentiable paths in the graph, which authors propose to tackle with RL and policy gradients. The whole model can be seen as an RL agent, trained to do splitting action on a set of instances in such a way, that jointly trained predictor T quality is maximised (and thus its current log prob: log p(Y|P(X)) becomes a reward for an RL agent). Authors claim that model like this (strengthened with pointer networks/graph nets etc. depending on the application) leads to empirical improvement on three tasks - convex hull finding, k-means clustering and on TSP.  However, while results on convex hull task are good, k-means ones use a single, artificial problem (and do not test DCN, but rather a part of it), and on TSP DCN performs significantly worse than baselines in-distribution, and is better when tested on bigger problems than it is trained on. However the generalisation scores themselves are pretty bad thus it is not clear if this can be called a success story.
I will be happy to revisit the rating if the experimental section is enriched.
Pros:
- very easy to follow idea and model
- simple merge or RL and SL in an end-to-end trainable model
- improvements over previous solutions
Cons:
- K-means experiments should not be run on artificial dataset, there are plenty of benchmarking datasets out there. In current form it is just a proof of concept experiment rather than evaluation (+ if is only for splitting, not for the entire architecture proposed). It would be also beneficial to see the score normalised by the cost found by k-means itself (say using Lloyd's method), as otherwise numbers are impossible to interpret. With normalisation, claiming that it finds 20% worse solution than k-means is indeed meaningful. 
- TSP experiments show that "in distribution" DCN perform worse than baselines, and when generalising to bigger problems they fail more gracefully, however the accuracies on higher problem are pretty bad, thus it is not clear if they are significant enough to claim success. Maybe TSP is not the best application of this kind of approach (as authors state in the paper - it is not clear how merging would be applied in the first place). 
- in general - experimental section should be extended, as currently the only convincing success story lies in convex hull experiments
Side notes:
- DCN is already quite commonly used abbreviation for "Deep Classifier Network" as well as "Dynamic Capacity Network", thus might be a good idea to find different name.
- please fix \cite calls to \citep, when authors name is not used as part of the sentence, for example:
Graph Neural Network Nowak et al. (2017) 
should be
Graph Neural Network (Nowak et al. (2017))
# After the update
Evaluation section has been updated threefold:
- TSP experiments are now in the appendix rather than main part of the paper
- k-means experiments are Lloyd-score normalised and involve one Cifar10 clustering
- Knapsack problem has been added
Paper significantly benefited from these changes, however experimental section is still based purely on toy datasets (clustering cifar10 patches is the least toy problem, but if one claims that proposed method is a good clusterer one would have to beat actual clustering techniques to show that), and in both cases simple problem-specific baseline (Lloyd for k-means, greedy knapsack solver) beats proposed method. I can see the benefit of trainable approach here, the fact that one could in principle move towards other objectives, where deriving Lloyd alternative might be hard; however current version of the paper still does not show that.
I increased rating for the paper, however in order to put the "clear accept" mark I would expect to see at least one problem where proposed method beats all basic baselines (thus it has to either be the problem where we do not have simple algorithms for it, and then beating ML baseline is fine; or a problem where one can beat the typical heuristic approaches).