Achieving fusion of deep learning with combinatorial algorithms promises transformative changes to artificial intelligence. One possible approach is to introduce combinatorial building blocks into neural networks. Such end-to-end architectures have the potential to tackle combinatorial problems on raw input data such as ensuring global consistency in multi-object tracking or route planning on maps in robotics. In this work, we present a method that implements an efficient backward pass through blackbox implementations of combinatorial solvers with linear objective functions. We provide both theoretical and experimental backing. In particular, we incorporate the Gurobi MIP solver, Blossom V algorithm, and Dijkstra's algorithm into architectures that extract suitable features from raw inputs for the traveling salesman problem, the min-cost perfect matching problem and the shortest path problem.
=== Summary ===
The authors propose a method for efficiently backpropagating through unmodified blackbox implementations of exact combinatorial solvers with linear objective functions. 
The gradient of such exact combinatorial solvers exists almost everywhere but is zero. The authors remark that the loss has the same gradient wrt to the solver's input as its linearization around the solver's input.  They therefore propose to interpolate the loss' linearization with a continuous (piecewise affine) function and use the gradient of this interpolation to backpropagate through the solver. This gradient is obtained efficiently by simply calling the solver on a single perturbed input (the perturbation depends on the incoming gradient, ie the gradient of the loss wrt to the solver's output).
The authors further study the properties of this piecewise affine interpolation and characterize its interpolation behavior as a function of a hyperparameter which controls the trade-off between "how informative the gradient is" and "how faithful the interpolation is to the original solver".
The authors validate their method with experiments on synthetic tasks that have both a visual processing aspect and a combinatorial aspect:
    - Shortest Path on Warcraft II terrain maps
    - TSP between country capitals where the inputs to the convnet are country flags
    - Min-cost perfect matching from Mnist digits.
Specifically, they feed the output of a convnet to the relevant solver (depending on the task) and learn end-to-end by backpropagating through the solver with their proposed method. They show that their method successfully solves the tasks where baseline ConvNet architectures fail.
=== Recommendation ===
This paper addresses an important problem and presents a novel approach.
Methods for combining combinatorial optimization algorithms and machine learning usually rely on modifiying or relaxing the combinatorial problem itself which prevents using solvers as-is. 
In contrast, the presented method allows to efficiently backpropagate through unmodified implementations of blackbox exact solvers with a linear objective. AFAIK this is the first method that allows this.
A weakness of the paper is that the experiments only validate proof of concept (as noted by the authors). They are small-scale and only compare against conventional ConvNets baselines (as opposed to other approaches to backpropagate through relaxed combinatorial problems).
Additionally, the characterization of the interpolation (whose gradient is used) doesn't directly explain why the gradient of the interpolation is a reasonable choice.
Overall, I recommend for acceptance.
=== Questions / Comments ===
- The authors show properties related to the interpolation behavior of the proposed interpolation function. What is the actual point/benefit of satisfying these properties? Are there arguments for why this is important besides the experimental results?  Is the point that since lambda controls how "faithful vs informative" the gradient is , there must be a range of values for lambda for which the method works? 
- It would be interesting to have experiments with non-exact solvers
- It would be interesting to optimize directly for the combinatorial objective in the experiments (using a policy gradient for example) rather than perform supervised learning on the solutions.
- Consider adding related work subsection on argmin optimization and meta-learning.