Alex Nowak, David FolquÃ©, Joan Bruna

https://arxiv.org/abs/1611.02401

Problem:

Approach:

Demonstrated on convex hull, clustering, knapsack, others, Accuracies in the range of 0.8-0.9 for convex hull.

Problem:

- Learn an algorithm from its inputs and outputs
- Approximation algorithm based on neural nets

Approach:

- Limited to Divide and Conquer algorithms. DiCoNets
- Invariance in size of input, e.g. Problems that can be solved via Recursion, Dynamic Programming
- Learn two scale invariant operations:
- Split
- Merge
- Split:
- Neural network work, trained via policy gradient
- Rewards:External black box function, calculates cost based on problem constraints
- Set2Set model, R layers
- Model applied recursively until split size is less than predetermined value
- Regularize split operation to control computation complexity
- Merge:
- Neural Network trained via back prop
- Uses Pointer Networks (autoregressive model, where outputs are permutation of subsequence of inputs) or Graph Neural Networks (for graph problems)

Demonstrated on convex hull, clustering, knapsack, others, Accuracies in the range of 0.8-0.9 for convex hull.