Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs
Authors: Xi Gao
Han Zhang
Aliakbar Panahi
Tom Arodz
Venue:  (2021)
Keywords: combinatorial optimization
linear programs
generalized gradient

Abstract: Combinatorial problems with linear objective function play a central role in many computer science applications, and efficient algorithms for solving them are well known. However, the solutions to these problems are not differentiable with respect to the parameters specifying the problem instance – for example, shortest distance between two nodes in a graph is not a differentiable function of graph edge weights. Recently, attempts to integrate combinatorial and, more broadly, convex optimization solvers into gradient-trained models resulted in several approaches for differentiating over the solution vector to the optimization problem. However, in many cases, the interest is in differentiating over only the objective value, not the solution vector, and using existing approaches introduces unnecessary overhead. Here, we show how to perform gradient descent directly over the objective value of the solution to combinatorial problems. We demonstrate advantage of the approach in examples involving sequence-to-sequence modeling using differentiable encoder-decoder architecture with softmax or Gumbel-softmax, and in weakly supervised learning involving a convolutional, residual feed-forward network for image classification.


network for Under review as a conference paper at ICLR 2021
DIFFERENTIABLE COMBINATORIAL LOSSES THROUGH GENERALIZED GRADIENTS OF LINEAR PROGRAMS
Anonymous authors
Paper under double-blind review
ABSTRACT
Combinatorial problems with linear objective function play central role in many computer science applications, and efficient algorithms for solving them are well known. However, the solutions to these problems are not differentiable with re- spect to the parameters specifying the problem instance for example, shortest distance between two nodes in graph is not differentiable function of graph edge weights. Recently, attempts to integrate combinatorial and, more broadly, convex optimization solvers into gradient- trained models resulted in several approaches for differentiating over the solution vector to the optimization problem. However, many cases, the interest is in differentiating over only the objective value, not the solution vector, and using existing approaches introduces unnecessary overhead. Here, we show how perform gradient descent directly over the objective value of the solution to combinatorial problems. We demonstrate advantage of the ap- proach in examples involving teuseuee-- modeling using differentiable encoder-decoder architecture with softmax or Gumbel-softman and in weakly supervised learning involving a convolutional, residual image classification.
INTRODUCTION
Combinatorial optimization problems, such as shortest path in weighted directed graph, minimum spanning tree weighted undirected graph, or optimal assignment of tasks workers, play central role in many computer science applications. We have highly refined, efficient algorithms for solving these fundamental problems (Cormen et al. 2009 Schrijver 2003). However, while we can easily find, for example, the minimal spanning tree in a graph, the total weight of the tree as function of graph edge weights is not differentiable. This problem hinders using solutions to combinatorial problems as criteria in training models that rely on differentiability of the objective function with respect to the model parameters.
Losses that defined by objective value of some feasible solution to combinatorial problem, not the optimal one, have been recently proposed for image segmentation using deep models (Zheng et al.) 2in et al. 2016). These focus problem where some pixels in the image have segmentation labels, and the goal is to train a convolutional network that predicts segmentation labels for all pixels. For pixels with labels, a classification loss can be used. For the remaining pixels, criterion based on a combinatorial problem - for example the maximum flow / minimal cut problem in a regular, lattice graph connecting all pixels (Boykov et al. 200T) or derived, higher-level super-pixels (Lin et al. 2016) is often used as loss, in an iterative process of improving discrete segmentation labels (Zheng al. 2015) Marin et al.) 2019). In this approach, the instance of the combinatorial problem either fixed, or depends only on the input to the network; for example, similarity of neighboring pixel colors defines edge weights. The output of the neural network gives rise to feasible, but rarely optimal, solution to that fixed instance combinatorial problem, and its quality is used loss. For example, pixel labeling proposed by the network is interpreted as a cut in pre-defined graph connecting then pixels. Training the network should result in improved cuts, but attempt to use solver to find an optimal cut made.
considering different setup, in which each output of the neural network gives rise to a new instance of a combinatorial problem. A combinatorial algorithm then used to find the optimal solution to the problem defined by the output, and the value of the objective function of
Here,

---

Under review as a conference paper at ICLR 2021
the optimal solution is used as loss. After each gradient update, the network will produce combinatorial problem instance, even for the same input sample. Iteratively, the network is expected to learn to produce combinatorial problem instances that have low optimal objective function value. modeling, the network will output a new sentence that is supposed to closely match the desired sentence, leading to to be solved. Initially, the optimal alignment will be poor, but as the network improves and the quality of the output sentences get higher, the optimal alignment scores will be lower.
For example, in requence-to-sequene
optimal sequence alignment problem
Recently, progress in integrating combinatorial problems into differentiable models have been made by modifyyin combinatorial algorithms use only differentiable elements (Tschiatschek al.) 2018; Mensch & Blondel 2018 Chang et al. (019), for example smoothed max instead of max in dynamic programming. Another approach involves executing two runs of non-differentiable. black-box combinatorial algorithm and uses the two solutions to define differentiable interpolation (Vlastelica Pogančić et al., 22200, Rolínek et al., 2020). Finally, differentiable linear programming and quadratic programming layers, which can be used to model many combinatorial problems, have
been proposed recently (Amos & Kolter 2017 2019).
Agrawal et al. 2019
Wilder et al. 2019 Ferber et al.
The approaches above allow for differentiating through optimal solution vectors. In many cases, are interested only in the optimal objective value, not the solution vector, and the approaches above introduce unnecessary overhead. We propose an approach for gradient-descent based training of network (a; (8) for supervised learning problems involving samples (1:, y) with the objective criterion involving loss term of the form L(B) ((OptSolutioOOjeettti Soeoonnveeievveeleeeeeeee Value
3), y)), where h IR- R some differentiable function, and II is combinatorial solver for a problem instance defined by the output of the 3-parameterized network F for feature vector I and by the true label y. We show that broad class of combinatorial problems can be integrated into models trained using variants of gradient descent. Specifically, we show that for an efficiently solvable combinatorial problem that can be efficiently expressed as an integer linear program, generalized gradients of the problem's 's objective value with respect to real-valued parameters defining the problem exist and can be efficiently computed from a single run of a black-box combinatorial algorithm. Using the above result, we show how generalized gradients of combinatorial problems provide sentence-level loss for text summarization using differentiable mncoder-decoder models that involve softmax or Gumbel softmax (Jang et al., 2016), and multi-element loss for training classification models when only weakly supervised, bagged training data is available.
DIFFERENTIABLE COMBINATORIAL LOSSES
2.1 BACKGROUND ON GENERALIZED GRADIENTS
A function f T:X' R defined over convex, bounded open set X E R is Lipschitz continuous an open set E X' there is a finite K IR such that Vz, y E If(z) - f(w)] < K|| y/|. A function is locally Lipschitz-continuuus if for every point 2g in its domain, there is neighborhood Bo, an open ball centered at &o. on which the function is Lipschitz-comtimouus For such functions, a generalized gradient can be defined.
Definition 1. (Clarke 1975) Let f X - be Lipschitt-contimuuus in the neighborhood of X. Then, the Clarke subdifferential (f))) of f at x is defined as
0f(z) = conv lim mx-
Vf(cx))
where the limit is over all convergent sequences involving those Ink for which gradient exists, and conv denotes convex hull, that is, the smallest polyhedron that contains all vectors from a given set. Each element of the set ff(x) is called a generalized gradient of f at x.
The Rademacher theorem (see e.g. (Eans 1992) )) states that for any locally Lipschitz-comtinuous
function the gradient exists almost everywhere; convergent sequences can be found.
In optimization algorithms, generalized gradients can be used in the same way as subgradients (Redding& & Downs 1992), that is, nondifferentiabiliyy may affect convergence in certain cases.
2

---

Under review as a conference paper at ICLR 2021
2.2 GRADIENT DESCENT OVER COMBINATORIAL OPTIMIZATION
Many combinatorial problems have linear objective function and can be intuitively expressed as integer linear programs (ILP), that is, linear programs with additional constraint that the solution vector involves only integers. Any ILP can be reduced to a linear program. Consider an ILP
(c, b)) = min, d'uu s.t. A'u = D', u 2 0, u E Zp,
with an optimal solution vector u" and optimal objective value z². Then, there exists a corresponding linear program (c, b)
LP(c,A,b) min, o'u s.t. = a 020,
called ideal formulation /Wolsey 1989,, for which u" is also optimal solution vector, with the same objective value z" For a feasible, bounded p-dimensional integer program, we can view the pair (A',8) 6)) as convex polyhedron A', the set of all feasible solutions. Then, the pair (A, in the ideal formulation LP is defined as the set of constraints specifying the feasible set A = conv { n )²). Convex hull of a subset of convex set A' cannot extend beyond A', thus, A is convex, contains all integer solutions from A', and no other integer solutions. The number of linear constraints in the ideal formulation may be exponential p. and/or in m, the number of the original constraints in A'. Thus, the existence of the ideal formulation LP for an ILP may not have practical utility for solving the ILP.
For combinatorial problem and its corresponding ILP, we use the ideal formulation of the ILP as a conceptual tool to define generalized gradient of the objective value of the optimal solution to the combinatorial problem with respect the parameters defining the combinatorial problem. Specifically, our approach first uses a single run of an efficient, black-box combinatorial algorithm to produce the optimal solution vector and the associated objective value. Then, the combinatorial problem is conceptually viewed as an instance of an II.. A possibly exponentially large linear program (LP) equivalent to the IIP is then used, without actually being spelled out solved, to derive generalized gradients based on the solution vector returned by the combinatorial algorithm.
First, introduce several notions of efficiency of transforming combinatorial problem into linear integer program that will be convenient in defining the generalized gradients of combinatorial problems.
Definition 2. Les P(w) be a combinatorial problem that is parameterized by continuous vector w E W C IR,, where W is simply connected and n the problem size, and let E Z be a constant that may depend on the problem type but not on its size. Then, a combinatorial problem is
primal-dual d-efficient if can be phrased as integer linear program involving n variables, with kn constraints in an I.P formulation equivalent to the IIP,, and the parameters ( (A, c) of the LP formulation depend on w through (sub) difffrreiete functions, c(w), A(w), = b(w).
primal d-efficient if can be phrased as an integer linear program involving n. variables, the parameters of the problem influence the cost vector e through (sub) jiffediffreentiable function c = o(w), and do not influence the constraints A.b.
dual d-efficient if it can be phrased as an integer linear program in which the number of constraints in the equivalent LP formulation is kn, the parameters of problem inftuence b through (sub (aadddiffreetiable function b = b(w), and do no influence the constraint matrix A nor the cost vector c.
The class of d-efficient problems includes polynomially solvable combinatorial problems with objective function that is linear in terms of problem parameters. Typically, the functions c(w), b = b(w) and A maximum network flow, the cost vector is composed directly of edge capacities, and A an b are constant for a given flow network topology, and do not depend on capacities.
(w) are either identity mapping or are constant; for example, in the LP for
For any polynomially solvable combinatorial problem, we can construct voly(n)-sizer Boolean circuit for the algorithm solving it. For each poly(n)-sizze circuit, there is a linear program with (nly(n) variables and constraints that gives the same solution (see (Daggupta et al. 2008), Chap.
3

---

Under review as a conference paper at ICLR 2021
7). For example, for MST in graph with V vertices and E edges, the Martin's ILP formulation (Martin 1991) has only poly(V + E) constraints, but is an extended formulation that involves VE additional variables top of the typical E variables used in the standard ILP formulations for MST. Thus, we cannot use it to construct an IIP formulation that would make MST primal-dual O-efficient. Altematively, there is IIP for MST with one binary variable per edge, and the weight of the edge only influences the cost vector but to prohibit cycles in the solution there is constraint for each cycle in the graph, thus the number of constraints is not poly(n) for arbitrary graphs. These constraints are specified fully by the topology of the graph, not by the edge weights, so does not influence A nor b, meeting the conditions for primal d-efficiencc. The MST example shows that there are problems that are primal 8-efficient and not primal-dual d-efficient.
Some polynomially solvable combinatorial problems are not d-efficient any of the above sense. For example, fixed-rank combinatorial problems with interaction costs (Lendl et al. (219)) can be phrased succinctly as a bilinear program, but lead to prohibitively large linear programs both in terms of the number of variables and the number of constraints.
For d-efficient problems, we can efficiently obtain generalized gradients of the objective value.
Theorem 1. Consider a combinatorial problem P(w) of size n, a parameter vector w from the interior of the parameter domain W, and an algorithm IIw) for solving it in time poly(n). Let x be the optimal objective value returned by II. Then,
if P is primal θ-efficient, then the generalized grudients (z)(w) exist, and can be efficiently computed from U*, the set of primal solution of the ideal formulation of integer program corresponding to P;
if P is dual O-efficient, then the generalized gradients of Oz (w) exist, and can be efficiently computed V*, the set of all dual solution to the ideal formulation of the integer program corresponding to P;
if P is primal-dual Ö-efficient, then the generalized gradients of over w exist, and can be efficiently computed from U* and V*, as defined above.
Proof. A series of results (Gal 1975 Freund 1985 De Wolf & Smeers 2000) shows that the optimal objective value 2" LP(c, A. b) for linear program is finite at (c, A) and in some neighborhood of (c, A, b), then generalized gradients of =² with respect to b, and A exist and are
0z = U", (b) =V, V*, (A) = { {-vu" (u, E V X U
We build on these results to obtain generalized gradients of the linear program corresponding to the combinatorial problem. For the first case in the theorem, definition 2 states that in the linear program corresponding to P. only the cost vector c depends on w, through a diffeeerrret function c(w). Since w is in the interior of the parameter domain W, the objective value is finite over some neighborhood of w. Then,
Oz (2*(w) (c) dc dc U* Dw Ow where the generalized gradient =" (c) exists and is equal to U* For the second case, the ideal formulation LP exists. Then, from definition 2 we have that
ab ab
dz (w) oz du
Fw V*
The third case a direct extension of the first two cases.
Theorem I indicates that black-box combinatorial algorithms can be used to expand the range of transformations that can be efficiently utilized neural networks. One immediate area of application is using them to specify a loss function. Consider a network ((I;3) parameterized by a vector of tunable parameters 3. The network transforms a batch of input samples x into batch of outputs x F(x; 3). Then, in the broadest primal-dual O-efficient case, is used, possibly with the true classes y. to formulate parameters (c, A, b) = g(x, y) of a linear program corresponding to the combinatorial problem, through some dsffeiiffeeettiable function g. For
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Minimization of combinatorial loss
Input: batch C X, y C y. network Fax; (3), functions g, h, combinatorial algorithm IT Output: Loss and its generalized gradient, L(3), aL(3)
1: procedure COMBLOSSMINGE, y, B, F,g, II)
2: forward pass X F(x:
3: forward pass Ac = g(x.)) y)
4: run combinatorial solver to find optimal objective value 2" II[(c, b) and optimal primal and/or dual solution vectors u², u²
5: forward pass T(3) = h(=²)
6: backward pass through h: 0L/0z*
7:
backward pass through II: 02" (c) u² 02= =v', 0²) = -v"u"
8:
backward pass through 9 and F
9:
(L(
OL
uc"
dc
2² um="""7 A.
0r ab
08
08
8g
10: return ((9),0L(B)
11: end procedure
a given / and given batch samples (z, v). we can then define loss as function of the optimal objective value of the linear program corresponding to the combinatorial problem resulting from (( B). y). L(B)= = hc="(c, A, b)). This approach, summarized in Algorithm 1, allows us to obtain the generalized gradient of the loss with respect to 3 as long as functions g and h are differentiable. For clarity, in Algorithm 1, we did not consider functions h depending not just on but also on x or y. but the extension straightforward.
EXAMPLE USE CASES AND EXPERIMENTAL VALIDATION
3.1 DIFFERENTIATING OVER BIPARTITE MATCHING FOR WEAKLY-SUPERVIE LEARNING
To illustrate gradient descent over a combinatorial loss, we first focus on simple image recognition problem. Consider a photo of a group of people with a caption listing each of the persons in the picture, but missing the "from left right" part. Given collection of such labeled photos, model learn to recognize individual faces? Similarly, consider a shopping cart and a printout from the register. Given collection of unordered shopping carts together with matching receipts, learn to recognize individual shopping items? These are example of a weakly superis-peeee learning where the goal is to learn classify previously unseen feature vectors, but training sample is bag of feature vectors accompanied by a bag of correct labels, instead of a feature-vector and a correct label. We are not told which class belongs which sample, which prevents us from directly using the standard cross-entropy loss.
model
More formally, consider d-class classification problem, and a model F(zy; 8) that for sample 2; returns a d-dimensional vector of class probabilities, Pj. with pf denoting the predicted conditional probability of class e given feature vector 2y. Let y denote a dddimmenional,, one-hot representation of the true class label of sample zy, with vf = if sample j is of class c, and zero otherwise. In weakly
supervised learning involving bags of size b, we are given a tuple of feature vectors, X = =(x;))
and tuple of permuted labels Y (y)())
will refer to the j-th element of the tuple as Y. The permutation o is unknown, thus using loss E(p5 Y2) E(jj. Mo(s)) compare predicted distribution over classes for sample j with one-hot representation of j-th element the randomly ordered set of true classes Y, makes no sense, since most likely + j: Y, (i) is the class for some other sample i, not for sample j.
one-hot-vectory for some permutation
While the permutation is unknown, with repeated presentation of bags samples and bags of corre- sponding labels, do have some information connecting the feature vector to classes. Intuitively, we can try to match model's outputs for feature vectors in the bag to the class labels using the information in the probability distribution p; over classes provided by the model for each feature vector 2y. That is, we can aim to find permutation â optimal in the average loss sense mina > E(p,, oYY))) If the class conditional probabilities p, resulting from the model perfectly match the one-hot vectors, the optimal ē will be the inverse of the permutation a, that is, o(Y); = y/-
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Loss based on bipartite matching for weakly-superrissed image classification
Input: X = ( bag of b input images; Y (==) - set of b sample classes match, in
one-hot representation, in arbitrary order; 3 8 network weights.
Output: Loss (optimal matching cost) and its generalized gradient, L(3), (L(
1: procedure MATCHBAG(X, (39)
2: forward pass, class probabilities - softmaxx(RssNeellttee B)) for = -....,b
p;=
3: forward pass, cross-entropy for all image-label pairs Cja = (logPj. Pj, Yx) for j. k = 1,
4: optimal matching cost and matching matrix: 2", .M OptMatchingg(CC C)),
i..., M = arg ming (C, (C.M)). =1)==22= (C, M))
5: final loss: cost of optimal matching L(3) =
6: backward pass through bipartite matching (C) = M
7: backward pass through cross-entropy, softmax and ResNet18: OL(3) = M ac
8/
8: return ((9).8((B))
9: end procedure
A b-element permutation can be represented by b x b permutation matrix M. To find M, we define a x 6 matrix C' with CyA=- {(p,, Ys), where l' represents cross-entropy loss {(p, y) = - (log p. y). with the logarithm applied element-wise. The elements Cy& correspond to edge weight a bipartite graph with the feature vectors processed by the neural network on one side, and labels on the other side. We use a combinatorial solver, for example the Hungarian method with computational complexity O (b²), to find the the permutation matrix M = arg min Mi, (C, M) minimizing the Frobenius inner product of C' and M. The procedure is outlined in Algorithm 2
To test the approach, we used the 11FAR100 benchmark image dataset. As baseline, we trained 5 independent fully supervised models with ResNet18 architecture (Zagoruyko & Komodakis 2016) (see Supplementary Material for details), that is, models where each image separate sample with its true class available for loss calculation. To evaluate the ability of our method to provide gradients of combinatorial loss defined by weighted matching, during training we explored image bags of samples consisting of 0=4, 8, 12, 16, 24, or 32 images, and including correct but shuffled image labels. We trained 5 independent models for each bag size with the loss and its gradient provided using Algorithm 2. To avoid situations where the combinatorial loss is superficially aided by bags with mostly one class, we ignored any bag that has less than 75% of different classes, that is, for bag of size 8, we only consider bags that consist of at least 6 different classes. During testing, same as in the baseline model experiments, each image had the matching label available for test error calculations. For comparison, we trained a model with the same setup of image bags using cvxpylayers (Agrawal jt al., 2019). a recently proposed methods for differentiable layers defined by conic programs. In contrast to our approach, which uses combinatorial algorithm and relies on the LP formulation of the weighted bipartite matching only conceptually, for the definition of gradients, cvxpylayers solve the linear program in order obtain gradients. We also trained the same model using recently proposed approach to approximate gradicnts of the optimal solution vector, not the optimal objective value, of a combinatorial problem (Vlastelica Pogančié et al., 2020); used the same combinatorial solver as in the experiments with our method.
Test error for CIFAR100 of the training set reshuffled into bags after each epoch (Fig. D left) shows that for bag sizes up to twelve elements, weak supervision through weighted bipartite graph matching is almost as effective as supervised learning with true label available for each individual image, that is, bag of size one. Training using the bipartite matching loss was implemented in three different ways: through interpolated combinatorial gradients proposed in (Vlastelica Pogančié al. 2020). through differentiable LP approach (cvxpylayers). and through the proposed approach for obtaining gradients of the objective value. All three approaches lead to very similar error rates (Fig. T left), indicating these three ways of obtaining gradients provide similar training signal to the network. The two methods that use combinatorial solvers are much more efficient than LP solver-based evxpylayers (Fig. [ right). The performance of the LP-based method decreases for very small bag sizes, where each epoch has large number of individual problems to solve, as well as for large bag sizes, where each problem to be solved involves more computation. Among the two methods using the same combinatorial solver, our proposed method is twice as fast as the interpolation method of (Vlastelica Pogančić al. 2020), which requires solving a combinatorial problem not only in the

---

Under review as a conference paper at ICLR 2021
20000
method
method
combinttoiia
contirattriall
evapstayers
35.0
bags combinateriu
10000
Intee polated combinatorial
n1 bags base line
Theining Time [s]
32.5
5000
27.5
25.0
2000
20.0
1000
bag
bag
Figure I: Test set error (left) and total training time (right) for increasing bag sizes for classifiers trained using the proposed bipartite matching loss with gradients calculated using the proposed approach and, for comparison, using cvxpylayers (Agrawal et al.) (2019) and using an interpolation approach for obtaining gradients of the solution vector of combinatorial problems (Vlastelica Pogančid et al. 2020). A supervised model with true label available for each individual sample, which corresponds bag of size one, is used as a baseline lower bound on the error that the bag-trained models should attempt to match. Mean, and the 95% confidence interval of the mean, are shown.
forward pass, but also in the backwards pass order to obtain gradients of the solution vector. These results show that the generalized gradient over combinatorial optimization is effective in providing training signal to train a large neural network, and can do it much faster than the state-of-the-ar alternative approaches.
3.2
DIFFERENTIATING OVER GLOBAL SEQUENCE ALIGNMENT FOR SENTENCE-LEVEI Loss IN SEQUENCE-TO TO-SEQUENCE MODELS
Another case where a combinatorial loss is advantageous occurs in sequence-to--eqqencee natural language models. We used standard encoder-decoder architecture for the model (see Supplementary Material for details). The encoder takes the source sequence on input and prepares context vector capturing the source sequence. The decoder is recurrent network that outputs the predicted sequence one token at a time, based on the context vector and the output of the previous step. The output of the decoder at a step is vector of probabilities, Pt over the set of all possible output tokens.
Existing encoder-decoder models use cross-entropy loss to compare predicted probabilities pr the target word at position I, encoded as one-hot vector yt. Instead sequence-level optimization, dusition-specing cross entropy loss results in averaged token-level optimization. We hypothesize this has detrimental effect on the training process of differentiable ecquence-to-sequenee models that involve softmax Gumbel-softman (Jag al. 2016) the mechanism for feeding the output of the previous step of the decoder as input for the next step. For example, a recurrent model that learned to output almost all the target sentence correctly but is still making the mistake of missing one word early in the sentence will have very high loss at all the words following the missing word correcting the mistake should involve keeping most of the model and focusing on the missing word, but with position-specitte loss, all the outputs are considered wrong and in need of correction.
Gaps or spurious words in the output sequence can be treated naturally we consider global sequence alignment (GSA) as the loss. Global sequence alignment (Needleman & Wunsch 1970) combinatorial problem in which two sequences are aligned by choosing, at each position, to either match token from one sequence to a token from the other, to introduce gap in one the other sequence; each choice has cost (see Fig. 2}. In eequence-to-sequenne modeling, the cost of matching the decoder's output from position i to the target sequence token position & will be given by (- log Ps. yt.). The cost of a gap, that is, of horizontal or a vertical move in Fig. is specified in way that promotes closing of the gap; the cost of the gap, multiplied by a scalar 7 > 1 to prioritize closing the gaps over improving the matchings. In experiments, used 7 1.5. The GSA problem can stated linear program
the cost of diagonal move from that position as
7

---

Under review as a conference paper at ICLR 2021
Target sentence: one-hot representation y, for word /
Predicted sentence: log p for word
we
can
now
have
some
gaps
</>
<olog p
fog Po
we
Togur O
can
108
have a
10g Ps.
gap
</>
Figure 2: A directed acyclic graph (DAG) corresponding to the global sequence aligument between the target sequence and the sequence predicted by the RNN model. Each node, except the end of sequence indicator < / >>, has out-degree of three: a diagonal edge corresponding to a match between the predicted and the target sequence. a horizontal edge corresponding to a gap in the predicted sequence, and a vertical edge corresponding to a gap in the target sequence. Optimal sequence alignment is depicted in red, with the weights the alignment costs of the selected edges in blue.
with variables and m + 1 constraints, with the costs of the moves forming the right-hand side of the constraints. Thus, by Theorem [ the generalized gradient of the minimum global sequence alignment with respect to matching and gap costs is efficiently available.
In experiments involving global sequence alignment in suuuence-to-eeqenne models, we used architecture with bidirectional
an encoder-decoder eequencce-t--sequeee encoder and an attention-base RNN decoder (Luong et al. 2015), as implemented in PyTorch-Texee (Hu et al., 2018). While this architecture is longer the top performer in terms of ROUGE metric- currently, large pre-trained self- attentien models are the state-of-the-and training, allowing for experimenting with different loss functions. During inference, we used beam search. During training, to have a differentiable decoder, we use two alternative approaches. First, we feed the probabilities resulting from the softmax layer applied to the outputs the RNN directly as the recursive inputs to the RNN. Second, inputs to the RNN are provided by the straight-through Cuubee--offtax distribution (Jang al., 2016) based on the outputs of the RNN, which is an approximation of the categorical distribution from which one-hot, single-token outputs are sampled. In both cases, as a baseline for comparisons with the GSA-based loss, we use word-level maximum likelihood, that is, cross-entropy between the probability vector output of the softmax layer of the RNN and the desired target word at that position. In evaluating the combinatorial GSA loss, we used text summarization task involving the GIGAWORD dataset (Graff & Cieri 2003) as example of a sequence- to to-sequence problem. We used test set ROUGE 1, 2, and scores (Lin 2004) as the measure of quality of the summarizations.
RNN
it is much more efficient in
The results in Table T show that the GSA-based loss leads to improved text summarization results in all three ROUGE metrics compared to position-speciff cross-entrope maximum likelihood training, both for the softmax and the Gumbel-softnax approach for providing the recursive input to the RNN in differentiable way. The increase in accuracy comes at the cost of doubling the training time when our method is used to provide gradients of the optimal alignment score. A similar increased accuracy can be observed when the interpolation approach (Vlastelica Pogančić al. (020) for gradients of optimal alignment path is used instead, but the interpolation method further increases the training time, by a factor two compared to our method. The proposed combinatorial approach is much more accurate and efficient than the recently proposed evxpylayers method. The running time for the cvxpylayers approach is orders of magnitude slower. The evxpylayers solver managed to reduce the training loss for several initial epochs, after which solver errors start to occur and the learning process diverges. In order to confirm this behavior, we performed 3 additional runs of the cvxpylayers- based training for the softmax model. In all cases, the loss dropped from the initial value in the 90-95 range to above 50, after which it increased to 500 or more. For comparison, the proposed combinatorial loss approach and the standard cross-entropy approach reach loss in the 30-32 range by epoch 10.
8

---

Under review as a conference paper at ICLR 2021
Table 1: Results for the GIGAWORD text summarization task using ROUGE-1, ROUGE-2, and ROUGE-L metrics. For the position-specific cross-entropy loss (MLE), for the interpolated combina- torial gradient (GSA-I) (Vlastelica Pogančić al. 2020) applied to global sequence alignment, and for our combinatorial method (GSA-L), results are given as mean(std.dev. over five independent runs with different random seed. For the method involving evxpylayers (GSA-C) (Agrawal et al. 2019) applied to GSA, we only performed one run. We report test set values for the epoch that minimizes the total ROUGE score on a separate validation set. Time is per one epoch.
Loss Type
ROUGE-Total
ROUGE-1
ROUGE-2
ROUGE-L
Epoch
Time
Softmax
MLE
72.80(0.38)
32.45(0.15)
11.95(0.22)
28.39(0.20)
18.4(1.5)
min hr
GSA C
32.18
17.04
2.49
12.65
3
GSA I
75.87(0.82)
33.94(0.31)
12.03(0.35)
29.90(0.32)
13.4(3.4)
32 min
GSA L
76.36(0.60)
34.05(0.21)
12.31(0.20)
29.99(0.24)
15.4(2.5)
17 min
Gumbel-softmax
MLE
67.50(0.20)
31.25(0.18)
9.72(0.26)
26.52(0.08)
18.0(2.8)
min
GSA I
73.36(0.33)
33.44(0.16)
10.90(0.05)
29.01(0.14)
14.8(2.3)
32 min 17 min
GSA L
72.62(0.51)
33.25(0.15)
10.60(0.22)
28.77(0.17))
14.0(1.9)
4 RELATED WORK
Recently, (Tschiatschek et al. 2018) proposed an approximate solver for submodular function maximization that uses differentiable elements and allows for differentiating through the solver. Differentiable solvers are also considered in (Mensch & Blondel 2018). where dynamic programming solver is re- re-implemented with the maximum operation replaced by smoothed max. Similar approach is used in differentiable dynamic time warping (Chang et al. 2019). Several authors used differential approximation to linear program solutions instead of introducing differentiable operations into combinatorial algorithms. WGAN-TS (Liu et al., 2018) solves LP obtain the exact empirical Wasserstein distance. Then, to circumvent lack of differentiability of linear programs, WGAN-TS proceeds by training a neural network approximate the LP solution in order obtain gradients. In seq2seq- OT (Chen et al.) 2019). an approximation is used to model optimal transport between word embeddings serving as a regularizer training sequence-to-ssqqeeeee to-sequncc models. These approximation approaches are limited to specific problems and preclude using off-the-shelf combinatorial solvers.
Recently, an approach that relies on interpolation to obtain gradients of the optimal solution vector not optimal objective value as in our method produced by combinatorial solvers has been proposed (Vlastelica Pogančić et al.) 2020 Rolínek al.) (020). Similar to our approach, it allows for using off-the-shelf, black-box implementations of combinatorial algorithms. However, unlike approach, requires two executions of the solver, one in the forward phase, and a second execution for slightly perturbed problem for the backward phase. As can be seen in our experiments, this results in doubling the performance overhead compared to our approach.
An alternative approach is to use mathematical programming solvers in gradient-trained trained neural networks. OptNet (Amos & Kolter 2017) provides differentiable quadratic programming layers, and efficient GPU-based batch solver, qpth. Cvxpylayers (Agrawal et al., 2019) generalizes this approach to a broad class of convex optimization problems expressed as cone programs, which include QP and LP as special cases, using conic solver based on ADMM, providing general-purpose package based on the easy-to-use interface of cvxpy, with speed comparable to qpth for QP problems. Other authors (Wilder al.) 2019 Ferber al. 2019) focus on LP problems, regularize them by adding the quadratic term, and use QP solver as in OptNet to obtain the optimal solution vector and its gradient. Quadratic smoothing is also used in (Djolonga Krause (017) in submodular set function minimization. While these methods can handle broader class of problems than our method, the reliance on quadratic or linear programming solvers translates to increased solving time. In the approach proposed here, linear programming is used only as a theoretical tool that allows for defining a mapping from the solution to a combinatorial problem to the gradient of its objective value. experiments
The solution is obtained by single run of combinatorial algorithm, which, confirm, is faster than using mathematical programming and not affected by numerical instability and convergence problems.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in Neural Information Processing Systems, pp. 9558-9558555 95700,0700000 2019.
Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning, pp. 136-145, 2017.
Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. IEFE Transactions on Pattern Analysis and Machine Intelligence, 23(11):1222-1239, 2001.
Chien-Y Yi Chang, De-An Huang, Yanan Sui, Li Fei-Fei, and Juan Carlos Niebles. D3TW: Discrimina- tive differentiable dynamic time warping for weakly supervised action alignment and segmentation. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Liqun Chen, Yizhe Zhang, Ruiyi Zhang, Chenyang Tao, Zhe Gan, Haichao Zhang, Bai Li, Dinghan Shen, Changyou Chen, and Lawrence Carin. Improving sequence-to peatenncett--qquuuee sequence learning via optimal transport. In International Conference on Learning Representations, pp. urXiv:1901.06288 2019.
Frank H Clarke. Generalized gradients and applications. Transactions of the American Mathematical Society, 205:247-262, 1975.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
Sanjoy Dasgupta, Christos H Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. McGraw- Hill Higher Education, 2008
Daniel De Wolf and Yves Smeers. Generalized derivatives of the optimal value of a linear program with respect matrix coefficients. Technical report. Université Catholique de Louvain, 2000.
Josip Djolonga and Andreas Krause, Differentiable learning of submodular models. Advances in Neural Information Processing Systems, pp. 1013-1023, 2017.
LawrenceCraig Evans. Measure theory and fine properties of functions. Routledge, 1992.
Aaron Ferber, Bryan Wilder, Bistra Dilina, and Milind Tambe. MIPaaL: Mixed integer program as layer. arXiv preprint arXiv: urXiv:1907.055: 1907009977..... 2019.
Robert M Freund. Postoptimal analysis of linear program under simultaneous changes in matrix coefficients. In Mathematical Programming Essays in Honor of George B. Danizig Part I, pp. 1-13. Springer, 1985.
Tomas Gal. Rim multiparametric linear programming. Management Science, 21(5):567-575, 1975.
David Graff and C Cieri. English Gigaword corpus. Linguistic Data Consortium, 2003.
Zhiting Hu, Haoran Shi, Bowen Tan, Wentao Wang. Zichao Yang, Tiancheng Zhao, Junxian He, Lianhui Qin, Wang, et al. Texar; A modularized, versatile, and extensible toolkit for text generation. arXiv preprint arXiv: 1009.000099099 2018.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with Gumbel-softmax. In International Conference Learning Representations ICLR" 17. arXiv: /6/ 1.0/ 2016.
Stefan Lendl, Ante Čustié, and Abraham P Punnen. Combinatorial optimization with interaction costs: Complexity and solvable cases. Discrete Optimization, 33:101-117, 2019.
Chin-Yes Yew Lin. Rouge: A package for automatic evaluation of summaries. Text summarization branches out, pp. 74-81, 2004.
Di Lin, Jifeng Dai. Jiaya Jia, Kaiming He, and Jian Sun. Scribblesup: Scribble-supervise convolu- tional networks for semantic segmentation. Proceedings of the IEEE Conference on Computer Vision and Pottern Recognition, pp. 3159-3167, 2016.
10

---

Under review as a conference paper at ICLR 2021
Huidong Liu, Xianfeng Gu. and Dimitris Samaras. A two-step computation of the exact GAN Wasserstein distance. International Conference on Machine Learning, pp. 3165-3174, 2018.
Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention- neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1512-1421,, 2015.
Dmitrii Marin, Meng Tang, Ismail Ben Ayed, and Yuri Boykov. Beyond gradient descent for regularized segmentation losses. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
R Kipp Martin. Using separation algorithms generate mixed integer model reformulations. Operations Research Letters, 1063):11--228, 1991.
Arthur Mensch and Mathieu Blondel. Differentiable dynamic programming for structured prediction and attention. In Proceedings of the 35th International Conference on Machine Learning, pp. 3462-3471, 2018.
Saul B Needleman and Christian D Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443-433, 1970.
Nicholas J Redding and Tom Downs. Learning in feedforward networks with nonsmooth functions. In Advances in Neural Information Processing Systems, pp. 1056- 10661063,11 1992.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Mar- tius. Deep graph matching via blackbox differentiation of combinatorial solvers. arXiv preprint arXiv:2003.11657 2020.
Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003.
Sebastian Tschiatschek, Aytune Sahin, and Andreas Krause. Differentiable submodular maximization. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI'18, pp. 2731-2738 AAAI Press, 2018. ISBN 9780999241127.
Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differenti- ation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2020.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In The Thirty-This Conference on Artificial Intelligence (AAAI), pp. 1658-1665, 2019.
Laurence Wolsey. Strong formulations for mixed integer programming: a survey, Mathematical Programming, 45(1):173-199) 1989.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. International Conference on Learning Representations ICLR' 17. 160.0066000714 2016.
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes Vibhav Vincet, Zhizhong Su, Dalong
Du, Chang Huang, and Philip HS Torr. Conditional random fields as recurrent neural networks. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1529-1537, 2015.


Reviews:
[{"review_id": "sOfvPLz93I", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\n\nThe authors propose a simple method to optimize objective values defined as the\noptimal value of a combinatorial integer linear program, whose parameter depends on the\noutput of a certain model. \n\nFor this, they note that generalized gradient of such objective values are\nefficiently computed using the primal and dual solution of the ILP itself. In\nparticular, the ILP can be solved using specialized and efficient solver,\ninstead of solving a generic LP, as proposed in concurrent work.\n\nThe 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.\n\nReview\n------\n\nThe paper is well written and well organized. The theoretical aspects are well documented, and the examples are introduced precisely and pedagogically.\n\nThe method itself is interesting as it ensures that the generalized gradient of\nmany ILP problems are computable efficiently. Theorem 1 states those guarantees, and many examples are discussed.\n\nOn the other hand, the novelty of the method may be a little overstated. In\nparticular, it is known that using a generic LP solver is oftentimes not the\nmost efficient way of computing the gradient, and that specialized combinatorial\nsolver should be used. \n\nFor the problem of GSA, which corresponds to using a dynamic time warping loss,\nsolving the small LP is done using dynamic programming. Using a DTW loss on top\nof a deep neural network has already been studied (see e.g. the cited Mensch and\nBlondel paper, where the authors solve the LP using DP). Using a generic LP\nsolver such as the one in cvxpy is a little naive in that case, and it not\nsurprising that it performs poorly. \n\nIn this example, we only require the gradient with respect to the cost (P is\n\"primal-pdfiff-efficient\"). Arguably, this manuscript also enable us to\nbackpropagate through parametrized constraints, using the formula proposed in\nTheorem 1, which is little known in this community.", "extra_scores": {}, "extra_text": {}}, {"review_id": "a3fg_-gk_oR", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows how to differentiate through combinatorial\nlosses by differentiating through the ideal formulation LP.\nUnderstanding how to differentiate through combinatorial\noptimization so that it can be used as part of the model or\nloss is important as it captures many natural operations.\nI am giving this a weak accept as it is a novel approach\nfor differentiation that the community can build on,\nbut the positioning and relation to prior work and\nempirical comparisons could be stronger (more details below).\n\n# Strengths\nTo the best of my knowledge this is a novel approach that\nmakes the elegant and natural connections going from\na combinatorial problem to an ILP to an LP\nto differentiating through the LP using known methods.\n\n# Weaknesses\nThe biggest weakness is the lack of a comparison with related\napproaches for differentiating through combinatorial losses,\nsuch as some of the approaches discussed in the introduction\nas [Pogancic 2020] that consider similar problems.\nThe experimental settings considered in this paper compare to\nbaselines that *don't* differentiate through the combinatorial\naspect of the problem. While this is a great step of validating\nthe power of these approaches, I think that it would be significantly\nmore convincing to empirically compare to approaches that\ndifferentiate through the combinatorial losses.\n\nI also think it's important to discuss the comparisons to the\nrelated approaches for differentiating through parameterized\ncombinatorial optimization. Are the approaches using the same\ndefinition of a derivative? [Pogancic 2020] discusses an issue\nwith the real derivative through combinatorial optimization being\nuninformative or near-zero everywhere, is this also an issue in\nthe setting here?\nCan this approach be seen as an approximation or surrogate to\nthe derivative of the combinatorial problem as the other approaches?\n\nIf I understand correctly, this approach requires a known mapping from\nthe combinatorial problem to the ILP, and from the ILP to the LP,\nwhich could make it more involved to apply than some of the related\nmethods that don't require knowing this information.\n\n# Other questions and comments\nHow should the gradients of the continuous baselines (with CVXPY)\ncompare to the method being proposed in the experiments?\nIf they're using the ideal formulation LP, should they be the\nsame in theory (as Figure 1 validates), but in practice due\nto solver errors, gives suboptimal directions (as Table 1 shows)?\n\nThe last paragraph of the introduction presents a form of the\ncriterion with a loss and the combinatorial objective value\nwith notation that's not used later on in the paper.\n\nPage 2, second paragraph: The last sentence on differentiable\ncontinuous LPs/QPs seems separate from the rest of paragraph\non combinatorial solvers.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Y_4QitrxrTY", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "=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).\n\n=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.\n\n= significance=The paper's proposed method is practical for very common ML setups in NLP and computer vision that are used day-to-day.\n\n= Pros = Proposed method is interesting, practical, and relatively easy to implement.\n\n= Cons = Paper writing omits many key details necessary to use the method in practice. Experiments build the method on top of out-\ndated models and do not demonstrate that the method could be used with modern models (e.g. attention-based decoders).\n\n==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.\n\nYou 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?\n\nWhile 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.\n\nFigure 1: why is cvxpy timing u-shaped?", "extra_scores": {}, "extra_text": {}}, {"review_id": "O1D80eB4gwi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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)\n\nThey 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MOJj-92FseJ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nCan 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.\n\nIs 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.\n\nThe 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.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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