Divide and Conquer Networks

Alex Nowak-Vila, David Folqué, Joan Bruna

Abstract

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.

Introduction

Standard neural architectures like RNNs or CNNs often struggle with discrete algorithmic tasks such as sorting, finding a convex hull, or solving the Traveling Salesman Problem (TSP). These models typically face two main hurdles: complexity mismatch, where fixed architectures may be inefficient or insufficient for varying task scales, and poor generalization, where models trained on small input sizes fail when tested on larger ones.

Divide and Conquer Networks (DiCoNet) address these issues by moving away from black-box regression. Instead, they hard-code a recursive "divide and conquer" inductive bias, assuming that many algorithmic tasks are inherently self-similar. By learning how to solve small sub-problems and combine their solutions, the model can theoretically scale to problems of any size.

Methodology

The DiCoNet architecture is defined by two trainable, scale-invariant modules that operate recursively:

  • The Split Module ($S_\theta$): This module partitions an input set into two disjoint subsets. To ensure permutation invariance, the authors utilize architectures like Set2set or Graph Neural Networks (GNNs).
  • The Merge Module ($M_\phi$): This module takes two partial solutions and synthesizes them into a single, larger solution, often implemented using Pointer Networks or GNNs.
The DiCoNet architecture utilizes a recursive split-and-merge process to solve algorithmic tasks.

Training and Complexity

The workflow involves a top-down split phase to create a dynamic binary tree, followed by a bottom-up merge phase. Since the split operation is discrete and non-differentiable, the authors employ Reinforcement Learning (REINFORCE) for training. A key innovation is the introduction of a computational complexity regularization term. By penalizing unbalanced trees in the loss function, the model is explicitly pushed toward $O(n \log n)$ efficiency.

Experiments and Results

The model was evaluated on several classic combinatorial tasks, including Convex Hull, 0-1 Knapsack, and Euclidean TSP.

Generalization Performance

DiCoNet demonstrated superior generalization compared to standard baselines. For the Convex Hull task, while a baseline Pointer Network's accuracy plummeted as input size $n$ increased, DiCoNet maintained high performance. At $n=200$, DiCoNet with split regularization achieved 67.2% accuracy, significantly outperforming the baseline's 13.5%.

Performance comparison on the Convex Hull task across different input sizes (n).

In other tasks, DiCoNet scaled more gracefully than non-recursive GNN baselines for the Knapsack problem and showed better scalability for TSP when moving from $n=20$ to $n=80$, despite the inherent difficulty of merging partial TSP paths.

Conclusion

By leveraging the divide-and-conquer principle as a powerful inductive bias, DiCoNet enables neural networks to learn the underlying logic of scale-invariant algorithms. This approach not only improves accuracy on large-scale problems but also allows for the explicit optimization of computational complexity. Future work may explore more complex NP-hard tasks and refine the split mechanisms for problems requiring more global information.

Summary updated

Abstract

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.
BibTeX
@misc{nowakvila2016divide,
  author = {Alex Nowak-Vila and David Folqué and Joan Bruna},
  title = {{Divide and Conquer Networks}},
  year = {2016},
  eprint = {1611.02401},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.02401},
}
Figure