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 scale-
 invariant 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 Divide-
 and-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.
Dynamic model that learns divide and conquer strategies by weak supervision. Proposes to add new inductive bias to neural network architecture by using a divide and conquer strategy. This paper studies problems that can be solved using a dynamic programming approach, and proposes a neural network architecture to solve such problems that beats sequence to sequence baselines. The paper proposes a unique network architecture that can learn divide-and-conquer strategies to solve algorithmic tasks.