Combinatorial Optimization

Deep learning has shown remarkable success in solving problems from high-dimensional raw input, such as image recognition or speech-to-text translation. However, deep learning is not particularly good when it comes to problems with a combinatorial nature, such as solving a puzzle, finding the shortest path or matching two sets of items. For each of these problems, computer scientists have developed highly optimized algorithms with correspondingly fast implementations in the field of combinatorial optimization. These methods require a perfect input representation and cannot be used on raw inputs as such.

In this work, we bring deep learning and combinatorial optimization together. Ideally, we would like to have the best of both worlds: having rich feature representations through deep neural networks and efficient algorithm implementations that enable combinatorial generalization.  We have developed a method with which such algorithms can indeed be used as building blocks in deep neural networks. The original implementations do not need to be known or modified. Instead, it is enough to invoke them one time during the gradient computation on a modified input to obtain an informative gradient.

Equipped with our new method, called Blackbox differentiation, we tackled two real-world problems in computer vision: the keypoint correspondence problem and optimizing rank-based functions. The keypoint correspondence problem is about finding matching pairs of points in two or more images. Our architecture embedding a strong graph-matching solver, is able to outperform the state of the art in this domain on several benchmarks. Another remarkable success of our method is that it allows computing gradients for ranking-based functions  --  commonly used in, e.g., object-retrieval. Our paper was nominated for the best-paper award at CVPR. 

Enhancing reinforcement learning agents with planning algorithms as part of their policy networks is another exciting application.

Recently, we conceptually enhanced our method with the ability to learn the type of combinatorial algorithm that should be solved. This is achieved by learning the constraints of an integer linear program.