Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: =quality=Proposed method is significantly more practical, both in terms of ease of implementation and speed, than prior related work for minimizing combinatorial losses. The paper's exposition needs to be improved considerably, though (see below).

=originality=The paper draws on advanced concepts from combinatorial optimization that may be unfamiliar to many ICLR readers, but that have the potential for large impact.

= significance=The paper's proposed method is practical for very common ML setups in NLP and computer vision that are used day-to-day.

= Pros = Proposed method is interesting, practical, and relatively easy to implement.

= Cons = Paper writing omits many key details necessary to use the method in practice. Experiments build the method on top of out-
dated models and do not demonstrate that the method could be used with modern models (e.g. attention-based decoders).

==Comments==I appreciate that you provide a very general recipe for constructing the differentiable combinatorial layers. However, the paper provides far too few details for the particular problems (bipartite matching and sequence alignment) that appear in the experiments. The supplementary material does not help. Your method is promising, and practitioners that do not have a background in combinatorial optimization may want to use it. The paper does not provide enough details to do so. I'd replace Algorithm 1 with a box specific to bipartite matching.

You need to provide far more detail/background on differentiable decoding for the secnod set of experiments. It was unclear what Softmax/ Gumbel-Softmax meant. Is Softmax not the same as MLE?

While the second set of experiments provides useful ablation analysis of the impact of your method, it builds on an out-dated model. You write "while this architecture is no longer the top performer in terms of ROUGE metric –currently, large pre-trained self-attention models are the state-of-the-art – it is much more efficient intraining, allowing for experimenting with different loss functions." Is the speed difference really that much? I'm surprised that that makes a difference in terms of which experiments are feasible.

Figure 1: why is cvxpy timing u-shaped?
review_title: Interesting general method, but needs far more details about the resulting algorithm for concrete use-cases.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The authors present a technique to integrate combinatorial optimization sub-problems into a gradient descent based application. The approach they describe relies only on differentiation of the value of the combinatorial program (instead of the solution vector), and can be done with relatively low overhead (compared to techniques that involve modifying combinatorial algorithms to differentiable elements, or the use of differentiable linear/quadratic programming layers)

They motivate and show the advantages of their approach using two natural and useful examples. The experimental results show promise, and the paper is well written, and motivated.


review_title: review for "Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs"

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper shows how to differentiate through combinatorial
losses by differentiating through the ideal formulation LP.
Understanding how to differentiate through combinatorial
optimization so that it can be used as part of the model or
loss is important as it captures many natural operations.
I am giving this a weak accept as it is a novel approach
for differentiation that the community can build on,
but the positioning and relation to prior work and
empirical comparisons could be stronger (more details below).

# Strengths
To the best of my knowledge this is a novel approach that
makes the elegant and natural connections going from
a combinatorial problem to an ILP to an LP
to differentiating through the LP using known methods.

# Weaknesses
The biggest weakness is the lack of a comparison with related
approaches for differentiating through combinatorial losses,
such as some of the approaches discussed in the introduction
as [Pogancic 2020] that consider similar problems.
The experimental settings considered in this paper compare to
baselines that *don't* differentiate through the combinatorial
aspect of the problem. While this is a great step of validating
the power of these approaches, I think that it would be significantly
more convincing to empirically compare to approaches that
differentiate through the combinatorial losses.

I also think it's important to discuss the comparisons to the
related approaches for differentiating through parameterized
combinatorial optimization. Are the approaches using the same
definition of a derivative? [Pogancic 2020] discusses an issue
with the real derivative through combinatorial optimization being
uninformative or near-zero everywhere, is this also an issue in
the setting here?
Can this approach be seen as an approximation or surrogate to
the derivative of the combinatorial problem as the other approaches?

If I understand correctly, this approach requires a known mapping from
the combinatorial problem to the ILP, and from the ILP to the LP,
which could make it more involved to apply than some of the related
methods that don't require knowing this information.

# Other questions and comments
How should the gradients of the continuous baselines (with CVXPY)
compare to the method being proposed in the experiments?
If they're using the ideal formulation LP, should they be the
same in theory (as Figure 1 validates), but in practice due
to solver errors, gives suboptimal directions (as Table 1 shows)?

The last paragraph of the introduction presents a form of the
criterion with a loss and the combinatorial objective value
with notation that's not used later on in the paper.

Page 2, second paragraph: The last sentence on differentiable
continuous LPs/QPs seems separate from the rest of paragraph
on combinatorial solvers.
review_title: Novel approach, comparisons don't compare to other combinatorial optimization differentiation methods

final_score: rating: 7: Good paper, accept
review_content: Summary
-------

The authors propose a simple method to optimize objective values defined as the
optimal value of a combinatorial integer linear program, whose parameter depends on the
output of a certain model. 

For this, they note that generalized gradient of such objective values are
efficiently computed using the primal and dual solution of the ILP itself. In
particular, the ILP can be solved using specialized and efficient solver,
instead of solving a generic LP, as proposed in concurrent work.

The authors propose two example applications, that are described precisely, and validated against generic LP solving approaches. Using combinatorial specialized solvers outperform generic LP solving approaches in term of computation, and in term of validation metrics, as generic LP solving is hindered by errors which makes the learning process diverge.

Review
------

The paper is well written and well organized. The theoretical aspects are well documented, and the examples are introduced precisely and pedagogically.

The method itself is interesting as it ensures that the generalized gradient of
many ILP problems are computable efficiently. Theorem 1 states those guarantees, and many examples are discussed.

On the other hand, the novelty of the method may be a little overstated. In
particular, it is known that using a generic LP solver is oftentimes not the
most efficient way of computing the gradient, and that specialized combinatorial
solver should be used. 

For the problem of GSA, which corresponds to using a dynamic time warping loss,
solving the small LP is done using dynamic programming. Using a DTW loss on top
of a deep neural network has already been studied (see e.g. the cited Mensch and
Blondel paper, where the authors solve the LP using DP). Using a generic LP
solver such as the one in cvxpy is a little naive in that case, and it not
surprising that it performs poorly. 

In this example, we only require the gradient with respect to the cost (P is
"primal-pdfiff-efficient"). Arguably, this manuscript also enable us to
backpropagate through parametrized constraints, using the formula proposed in
Theorem 1, which is little known in this community.
review_title: Well presented generic method for efficiently using combinatorial LP layers - albeit not completely novel

final_score: rating: 3: Clear rejection
review_content: The value of the optimal objective as a function of the cost vector $c$ can be written as $z^*(c) = c^T u^*(c)$ where the optimal solution $u^*$ also depends on $c$. The function $u^*(c)$ is piecewise constant -- there are finitely (resp. countably) many feasible solutions; candidates for $u^*$ -- and so the function $z^*(c)$ is a piecewise linear function of $c$, with gradient $u^*(c)$, wherever it exists (otherwise there is analogous subgradient). Obviously, all it takes for computing $u^*(c)$ is solving -- anyhow -- the combinatorial problem. This is all trivial and well-known, yet the authors do precisely that.

Can it be saved by proposing gradients also of w.r.t. constraints? No. These results are (slightly) less trivial but -- as authors admit -- are known since 1975. Moreover, the gradient with respect to $c$ is the only one used in experiments, as far as I understand.

Is there independent value in Theorem 1? I do not see it. It seems to be a bulky wrapper around the classical result. It only introduces some sort of transition from a vector specifying a combinatorial problem to a collection of vectors/matrices specifying an integer program. Also, the central concept of generalized gradient merely provides a formal framework to talk about non-unique gradients at boundary regions -- similarly to subgradient, subdifferential -- for the method itself, it has no specific relevance.

The claims of better performance compared to cvxpy are also absolutely non-surprising -- cvxpy currently uses a slightly suboptimal -- and a very expensive -- solver for linear programs. That is all.

review_title: Differentiating over the objective of a linear (integer) program is not an interesting problem

Meta-review: This paper received high variance in the reviews.

I personally agree with AnonReviewer4 that the theoretical results presented in this paper are well-known results on the sensitivity analysis of linear programs. See for instance "Introduction to linear optimization" by Bertsimas and Tsitsiklis, Chapter 5.

More generally, these results are a special case of Danskin's theorem and the envelope theorem:
https://en.wikipedia.org/wiki/Danskin%27s_theorem
https://en.wikipedia.org/wiki/Envelope_theorem

Clarke's generalized gradients are just subgradients in the case of convex functions, which is the case here.

My recommentation to the authors if they want to publish their work is to focus on the applications and to stop claiming novelty on the theoretical side.
Decision: Reject