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. Algorithmic tasks can be described as discrete input-output mappings defined over variable-sized inputs, but this "black-box" vision hides all the fundamental questions that explain how the task can be optimally solved and generalized to arbitrary inputs. Indeed, many tasks have some degree of scale invariance or self-similarity, meaning that there is a mechanism to solve it that is somehow independent of the input size. This principle is the basis of recursive solutions and dynamic programming, and is ubiquitous in most areas of discrete mathematics, from geometry to graph theory. In the case of images and audio signals, invariance principles are also critical for success: CNNs exploit both translation invariance and scale separation with multilayer, localized convolutional operators. In our scenario of discrete algorithmic tasks, we build our model on the principle of divide and conquer, which provides us with a form of parameter sharing across scales akin to that of CNNs across space or RNNs across time.Whereas CNN and RNN models define algorithms with linear complexity, attention mechanisms BID1 generally correspond to quadratic complexity, with notable exceptions BID0 . This can result in a mismatch between the intrinsic complexity required to solve a given task and the complexity that is given to the neural network to solve it, which Figure 1: Divide and Conquer Network. The split phase is determined by a dynamic neural network S θ that splits each incoming set into two disjoint sets: {X j+1,l , X j+1,l+1 } = S θ (X j,m ), with X j,m = X j+1,l X j+1,l+1 . The merge phase is carried out by another neural network M φ that combines two partial solutions into a solution of the coarser scale: Y j,m = M φ (Y j+1,l , Y j+1,l+1 ); see Section 3 for more details. may impact its generalization performance. Our motivation is that learning cannot be 'complete' until these complexities match, and we start this quest by first focusing on problems for which the intrinsic complexity is well known and understood.Our Divide-and-Conquer Networks (DiCoNet ) contain two modules: a split phase that is applied recursively and dynamically to the input in a coarse-to-fine way to create a hierarchical partition encoded as a binary tree; and a merge phase that traces back that binary tree in a fine-to-coarse way by progressively combining partial solutions; see Figure 1 . Each of these phases is parametrized by a single neural network that is applied recursively at each node of the tree, enabling parameter sharing across different scales and leading to good sample complexity and generalisation.In this paper, we attempt to incorporate the scale-invariance prior with the desiderata to only require weak supervision. In particular, we consider two setups: learning from input-output pairs, and learning from a non-differentiable reward signal. Since our split block is inherently discrete, we resort to policy gradient to train the split parameters, while using standard backpropagation for the merge phase; see Section 5. An important benefit of our framework is that the architecture is dynamically determined, which suggests using the computational complexity as a regularization term. As shown in the experiments, computational complexity is a good proxy for generalisation error in the context of discrete algorithmic tasks. We demonstrate our model on algorithmic and geometric tasks with some degree of scale self-similarity: planar convex-hull, k-means clustering, Knapsack Problem and euclidean TSP. Our numerical results on these tasks reaffirm the fact that whenever the structure of the problem has scale invariance, exploiting it leads to improved generalization and computational complexity over non-recursive approaches. We have presented a novel neural architecture that can discover and exploit scale invariance in discrete algorithmic tasks, and can be trained with weak supervision. Our model learns how to split large inputs recursively, then learns how to solve each subproblem and finally how to merge partial solutions. The resulting parameter sharing across multiple scales yields improved generalization and sample complexity.Due to the generality of the DiCoNet , several very different problems have been tackled, some with large and others with weak scale invariance. In all cases, our inductive bias leads to better generalization and computational complexity. An interesting perspective is to relate our scale invariance with the growing paradigm of meta-learning; that is, to what extent one could supervise the generalization across problem sizes.In future work, we plan to extend the results of the TSP by increasing the number of splits J, by refining the supervised DiCoNet model with the non-differentiable TSP cost, and by exploring higher-order interactions using Graph Neural Networks defined over graph hierarchies BID17 . We also plan to experiment on other NP-hard combinatorial tasks.
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.