Learning Dynamic Programming with Split-Merge Networks

Alex Nowak, 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: The Challenge of Algorithmic Learning

Traditional neural networks often treat algorithmic tasks, such as sorting or finding a convex hull, as "black-box" regression problems. While models like RNNs or Attention-based networks can learn these mappings, they often suffer from two major flaws:

  1. Complexity Mismatch: A task might inherently require $O(n \log n)$ operations, but a standard attention mechanism might use $O(n^2)$, leading to inefficiency.
  2. Poor Generalization: These models frequently fail when tested on input sizes significantly larger than those seen during training because they haven't truly captured the underlying recursive logic of the algorithm.

Many algorithmic tasks possess scale invariance—the method to solve a small version of the problem is the same as the method for a large one. We introduce a network that exploits this property directly by baking recursive structure into the architecture.

Methods: Divide and Conquer Networks

The Divide and Conquer Network (DiCoNet) consists of two primary, scale-invariant modules that mimic the classic "divide and conquer" strategy.

The Split-Merge architecture of DiCoNet.
  • The Split Module ($S_\theta$): This module takes an input set and learns how to partition it into two smaller, disjoint subsets. This process is applied recursively to create a hierarchical binary tree. To ensure permutation invariance, the model utilizes Graph Neural Networks (GNNs) or Set2set architectures.
  • The Merge Module ($M_\phi$): Once the "leaves" of the tree are reached, this module works upward, learning how to combine two partial solutions into a single, larger solution. This is typically implemented using Pointer Networks or GNNs.

Training Strategy: Because splitting is a discrete process, the split module is trained using Policy Gradient (REINFORCE), while the merge parameters are optimized via standard backpropagation. The model can be trained with "weak supervision" (input-output pairs) or even non-differentiable reward signals.

Key Insights

  • Complexity as Regularization: The dynamic architecture allows for a regularization term that encourages balanced trees. This enables the model to learn $O(n \log n)$ complexity rather than $O(n^2)$.
  • Parameter Sharing: Using the same split and merge blocks at every level allows the model to learn a "universal" atomic operation, similar to parameter sharing in CNNs or RNNs.
  • Inductive Bias: Forcing a divide-and-conquer structure provides a powerful inductive bias, proving more effective for algorithmic tasks than generic black-box models.

Key Results

DiCoNet demonstrates significant improvements in generalization error across various tasks, particularly when testing on problem sizes much larger than those seen during training.

Generalization performance on the Convex Hull task.

In the Convex Hull task, DiCoNet showed massive improvements in generalization. When trained on sizes up to $n=50$ and tested on $n=200$, the baseline Pointer Network's accuracy plummeted to 13.5%, while DiCoNet (with split regularization) maintained 67.2%. Similar trends were observed in the Knapsack and Clustering tasks, where DiCoNet outperformed non-recursive baselines and scaled better with problem size.

Limitations and Future Work

While DiCoNet performed well, its performance on TSP degraded at $n=200$, suggesting a need to relax strict scale-invariance or incorporate more task-specific priors. Additionally, relying on REINFORCE for discrete optimization can introduce high gradient variance. Future work will explore higher-order interactions using GNNs over graph hierarchies and a wider variety of NP-hard problems.

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{nowak2016learning,
  author = {Alex Nowak and Joan Bruna},
  title = {{Learning Dynamic Programming with Split-Merge Networks}},
  year = {2016},
  eprint = {1611.02401},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.02401},
}
Figure