Venue: ICLR 2020 Conference

Reviews:

final_score: rating: null
review_content: After reading the author's replies, I have changed my score to 8 as I believe this paper is a clear accept.

I still think the paper is a bit weak experimentally (for example, the authors could have applied the method presented in Bello et al with a small convnet to extract (x,y,z) from the country flags) but the authors have presented their work in a fair and honest light and addressed potential concerns.

- Meaning of theoretical guarantees: I am also not aware of techniques to evaluate such gradients. I believe the presentation could be a bit improved: the flow of the paper (during my first pass) made me expect some sort of theoretical guarantee.
- My comments on the type of supervision and related work are suggested as potential improvements of the paper.
- I recommend adding results with non-exact solvers as they show that the feature extraction process also works with non-exact solvers
review_title: Addressing the authors' replies

final_score: rating: 8: Accept
review_content: This paper shows how end-to-end learning can be done through
combinatorial solvers by using the derivative of
continuous surrogate function in the backward pass.
One elegant part of the method is that no modification
or relaxation is done to the combinatorial solver in
the forward pass and that the backward pass just requires
another call to the blackbox solver.

The idea of constructing continuous surrogate functions
and using them for differentiating through solvers with
piecewise-constant output spaces is thought-provoking and
I can see it inspiring many new directions of work.
For example looking at Figure 2 for intuition, one could
imagine other ways of making the solution space continuous.
The solution space of linear programs over continuous spaces,
as considered in [Elmachtoub & Grigas], the Sudoku example in
[Amos & Kolter], and related papers, is also piecewise constant and
it seems like a similar method could be used to bring more
informative derivative information to linear programs ---
have you considered this as a future direction?

One of my concerns with this work is that the ResNet baseline in the
experimental results seems like too much of a straw man for the tasks.
I do not see why they should have the capacity to generalize well.
This paper shows the ResNet baseline achieve near-zero
test accuracy but doesn't compare to other relevant baselines
that are mentioned in the related work section:
for example [Bello et al, Deudon et al., Kool et al.] for the TSP.

And one smaller comment: If one wanted to squeeze the performance even
more, would starting the training process with a large \lamdba
and annealing it to zero help?

----

Elmachtoub, A. N., & Grigas, P. Smart "predict, then optimize". arXiv 2017.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This paper proposes a straightforward method for training black box solvers of a restricted kind (namely those with inputs in R^n and linear cost functions). The proposed algorithm is tested on path finding, the travelling salesman problem, and a min-cost-perfect-matching problem, with promising results.

I would recommend accepting this paper. It is a well written paper with a novel idea supported by good experimental results.

The caveat is that I did not have the time to thoroughly review all the mathematical details. From a high-level they looked correct, and the math is sufficiently illustrated with figures and examples that it is easy for a reader to follow in detail given enough time.

The main shortcomings I see are that there are no experimental results comparing this method against any existing results; the authors do compare against their own ResNet18 implementation, but this is not ideal.

I found the discussion a bit cryptic: Why are approximate solvers needed for real-world problems? Are there no real-world problems where exact solvers are still applicable?
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: === 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.





review_title: Official Blind Review #3

Meta-review: This paper proposes a method for efficiently training neural networks combined with blackbox implementations of exact combinatorial solvers.

Reviewers and AC agree that it is a well written paper with a novel idea supported by good experimental results. Experimental results are of small scale and can be further improved, but the authors acknowledged this aspect well.

Hence, I recommend acceptance.
Decision: Accept (Spotlight)