Backpropagation through Combinatorial Algorithms: Identity with Projection Works
Authors: Subham Sekhar Sahoo
Anselm Paulus
Marin Vlastelica
Vít Musil
Volodymyr Kuleshov
Georg Martius
Venue: ICLR 2023 poster (2023)
Keywords: combinatorial optimization
deep learning
representation learning
gradient descent
backpropagation
argmin differentiation
deep graph matching
retrieval

Abstract: Embedding discrete solvers as differentiable layers has given modern deep learning architectures combinatorial expressivity and discrete reasoning capabilities. The derivative of these solvers is zero or undefined, therefore a meaningful replacement is crucial for effective gradient-based learning. Prior works rely on smoothing the solver with input perturbations, relaxing the solver to continuous problems, or interpolating the loss landscape with techniques that typically require additional solver calls, introduce extra hyper-parameters, or compromise performance. We propose a principled approach to exploit the geometry of the discrete solution space to treat the solver as a negative identity on the backward pass and further provide a theoretical justification. Our experiments demonstrate that such a straightforward hyper-parameter-free approach is able to compete with previous more complex methods on numerous experiments such as backpropagation through discrete samplers, deep graph matching, and image retrieval. Furthermore, we substitute the previously proposed problem-specific and label-dependent margin with a generic regularization procedure that prevents cost collapse and increases robustness.

Published as a conference paper at ICLR 2023
BACKPROPAGATION THROUGH COMBINATORIAL ALGORITHMS: IDENTITY WITH PROJECTION WORKS
Subham Sekhar Sahoo'
Anselm Paulus"
Marin Vlastelica
Cornell University Ithaca, USA waahoo@cs.come co..oeleccccomll.cuuu
MPI Intelligent Systems Tübingen, Germany anselm. maselmmpauuuseee @ tu..mpg.de
MPI Intelligent Systems
Tübingen, Germany
marin. vlastelica mpg.de
Vít Musil
Volodymyr Kuleshov Cornell Tech
Georg Martius
Masaryk University, FI Brno, Czech Republic musil @ fi.muni.cz
MPI Intelligent Systems Tübingen, Germany seorg.martiusee @ mpg.ee
NYC. USA kuleshov cornell.edu
ABSTRACT
Embedding discrete solvers as differentiable layers has given modern deep learning architectures combinatorial expressivity and discrete reasoning capabilities. The derivative of these solvers is zero or undefined, therefore a meaningful replacement is crucial for effective gradient-basee learning. Prior works rely on smoothing the solver with input perturbations, relaxing the solver to continuous problems, or inter- polating the loss landscape with techniques that typically require additional solver calls, introduce extra hyper-parameter parameters, or compromise performance. We propose a principled approach to exploit the geometry of the discrete solution space to treat the solver negative identity on the backward pass and further provide a theoret- ical justification. Our experiments demonstrate that such a straightforward hyper- parameter-five free approach is able to compete with previous more complex methods on numerous experiments such as backpropagation through discrete samplers, deep graph matching, and image retrieval. Furthermore, substitute the previously pro- posed problem-specife and abbl-deepnndett margin with a generic regularization procedure that prevents cost collapse and increases robustness. Code available
INTRODUCTION
Deep neural networks have achieved astonishing results in solving problems on raw inputs. However, in key domains such planning or reasoning, deep networks need to make discrete decisions, which can be naturally formulated via constrained combinatorial optimization problems. In many settings- including shortest path finding (Vlastelica et al., 2020; Berthet et al., 2020), optimizing rank-based objective functions (Rolinek et al., 2020a), keypoint matching (Rolinek et al., 2020b; Paulus et al., 2021), Sudoku solving (Amos and Kolter, 2017; Wang al., 2019), solving the knapsack problem from sentence descriptions (Paulus et al., (0021)-neurs) models that embed optimization modules as part of their layers achieve improved performance, data-efficiency, and generalization (Vlastelica et al., 2020; Amos and Kolter, 2017; Ferber et al., 2020; P. et al., 202
This paper explores the end-to-end training of deep neural network models with embedded discrete combinatorial algorithms (solvers, for short) and derives simple and efficient gradient estimators for these architectures. Deriving an informative gradient through the solver constitutes the main challenge, since the true gradient is, due to the discreteness, zero almost everywhere. Most notably, Blackbox Backpropagation (BB) by Vlastelica et al. (2020) introduces simple method that yields an informative gradient by applying an informed perturbation to the solver input and calling the solver one additional time. This results in gradient an implicit piecewise- loss interpolation, whose locality is controlled by hyperparameter.
"These authors contributed equally

---

Published as a conference paper at ICLR 2023
neural net layers
Blackbox combinatorial solver
neural net layers (optional)
learned representation
solver output
Input
arg miny (w vi s.t. ?
roopoofoot
Loss
W
((w)
negative identity
Figure I:
Hybrid architecture with blackbox combinatorial solver and Identity module (green dotted line) with the projection of cost w and negative identity on the backward pass.
We propose a fundamentally different strategy by dropping constraints on the solver solutions and simply propagating the incoming gradient through the solver, effectively treating the discrete block as a negative identity on the backward pass. While our gradient replacement simple and cheap to compute, it comes with important considerations, as its naive application can result in unstable learning behavior, as described in the following.
Our considerations are focused invariances of typical combinatorial problems under specific transformations of the cost vector. These transformations usually manifest as projections or nor- malizations, e.g. as an immediate consequence of the linearity of the objective, the combinatorial solver is agnostic to normalization of the cost vector. Such invariances, if unattended, can hinder fast convergence due the noise of spurious irrelevant updates, can result in divergence and cost collapse (Rolinek et al., 2020a). We propose to exploit the knowledge of such invariances by including the respective transformations in the computation graph. On the forward pass this leaves the solution unchanged, but on the backward pass removes the malicious part of the update. We also provide an intuitive view on this as differentiating through a relaxation of the solver. In our experiments, we show that this technique is crucial to the success of our proposed method.
In addition, we improve the robustness of our method by adding noise to the cost vector, which induces a margin on the learned solutions and thereby subsumes previously proposed ground-truth- informed margins (Rolinck et al., 2020a). With these considerations taken into account, our simple method achieves strong empirical performance. Moreover, it avoids costly call to the solver on the backward pass and does not introduce additional hyperparameters in contrast to previous methods.
Our contributions can be summarized as follows:
ii) A hyperparameter free method for linear-cost solver differentiation that does not require any additional calls the solver the backward pass.
(ii) Exploiting invariances via cost projections tailored to the combinatorial problem.
(iii) Increasing robustness and preventing cost collapse by replacing the previously proposed in- formed margin with a noise perturbation.
(iv) Analysis of the robustness of differentiation methods to perturbations during training.
2 RELATED WORK
Optimizers as Model Building Blocks. has been shown in various application domains that optimization on prediction is beneficial for model performance and generalization. One such area is meta-learning, where methods backpropagate through multiple steps of gradient descent for few-shot adaptation in multi-task setting (Finn et al., 2017; Raghu et al., 2020). Along these lines, algorithms that effectively embed more general optimizers into differentiable architectures have been proposed such convex optimization (Agrawal et al., 2019a; Lee al., 2019), quadratic programs (Amos and Kolter, 2017), conic optimization layers (Agrawal et al., 2019b), and more.
Combinatorial Solver Differentiation. Many important problems require discrete decisions and hence, using combinatorial solvers as layers have sparked research interest (Domke, 2012; Elmach- toub and Grigas, 2022). Methods, such as SPO (Elmachtoub and Grigas, 2022) and MIPaaL Ferber et al. (2020), assume access to true target costs, a scenario we are not considering. Berthet et al. (2020) differentiate through discrete solvers by sample-based smoothing. Blackbox Backpropagation
2

---

Published as a conference paper at ICLR 2023
(BB) by Vlastelica al. (2020) returns the gradient of implicitly constructed piecewise-linest in- terpolation. Modified instances of this approach have been applied in various settings such as ranking (Rolinek al., 2020a), keypoint matching (Rolinek et al., 2020b), and imitation learning (Vlastelica et al., 2020). I-MLE by Niepert et al. (2021) adds noise to the solver to model a discrete probability distribution and uses the BB update to compute informative gradients. Previous works have also considered adding a regularization to the linear program, including differentiable top-k-selection (Amos et al., 2019) and differentiable ranking and sorting (Blondel al., 2020). Another common approach is to differentiate softened solver, for instance in (Wilder et al., 2019) or (Wang et al., 2019) for MAXSAT. Finally, Paulus et al. (2021) extend approaches for learning the cost coefficients to learning also the constraints of integer linear programs.
Learning to Solve Combinatorial Problems. An orthogonal line of work to ours is differentiable learning of combinatorial algorithms or their improvement by data-driven methods. Examples of such algorithms include learning branching strategies for MIPs (Balcan et al., 2018; Khalil et al., 2016; Alvarez al., 2017), learning to solve SMT formulas (Balunovic et al., 2018), and learning to solve linear programs (Mandi and Guns, 2020; Tan et al., 2020). A natural way of dealing with the lack of gradient information combinatorial problems is reinforcement learning which is prevalent among these methods (Khalil et al., 2016; Bello al., 2017; Nazari et al., 2018; Zhang and Dietterich, 2000). Further progress has been made in applying graph neural networks for learning classical programming algorithms (Velickovic al., 2018; 2020) and latent value iteration (Deac et al., 2020). Further work in this direction can be found in the review Li et al. (2022). Another interesting related area of work is program synthesis, or "learning to program" (Ellis et al., 2018; Inala al., 2020).
Straight-through Estimator (STE). The STE (Bengio et al., 2013; Hinton, 2012; Rosenblatt, 1958) differentiates the thresholding function by treating as an identity function. Jang et al. (2017) extended the STE differentiating through samples from parametrized discrete distributions. The term STE has also been used more loosely to describe the replacement of any computational block with an identity function (Bengio et al., 2013) or other differentiable replacements (Yin al., 2019) on the backward pass. Our proposed method can be seen as generalization of differentiating through the thresholding function to general arg max/arg min problems with linear objectives, and it is therefore closely connected to the STE. We give a detailed discussion of the relationship in Suppl. A.
3 METHOD
We consider architectures that contain differentiable blocks, such as neural network layers, and combinatorial blocks, as sketched in Fig. 1. In this work, combinatorial block uses an algorithm (called solver) to solve an optimization problem of the form
y(w) = arg min v). yEY
where w W R is the cost vector produced by a previous block, Y R is any finite set of possible solutions and y(w) Y is the solver's 's output. Without loss of generality, Y consists only of extremal points of its convex hull, as no other point can be a solution of optimization (1). This formulation covers linear programs as well as integer linear programs.
3.1 D THROUGH COMBINATORIAL SOLVERS
We consider the case in which the solver embedded inside the neural network, meaning that the costs w are predicted by a backbone, the solver is called, and the solution y(w) is post-processed before the final loss L is computed. For instance, this the case when a specific choice of loss is crucial, or the solver is followed by additional learnable components.
We aim to train the entire architecture end-to-end, which requires computing gradients in a layer-wise manner during backpropagation. However, the true derivative of the solver y(w) is either zero or undefined, as the relation between the optimal solution y(w) and the cost vector w is piecewise constant. Thus, it is crucial to contrive meaningful replacement for the true zero Jacobian of the combinatorial block. See Fig. for an illustration.
Note, that the linearity of the objective in (1) makes differentiating the optimization problem more challenging than the non-linear counterparts considered in Amos and Kolter (2017); Agrawal et al. (2019 9a), due to the inherent discreteness of y. See Suppl. C.1 for discussion.
3

---

Published as a conference paper at ICLR 2023
M(
At dg
g
y(w)
y
VA
((4)
updasted
updated
di dy
updated
(a) Id update neighboring solution
(b) Id update final solution
(c) BB update (identical for some A)
Intuitive illustration of the Identity (Id) gradient and its equivalence to Blackbox Backprop- agation (BB) when -d//dy points directly to target y". The cost and solution spaces are overlayed; the cost space partitions resulting in the same solution are drawn in blue. Note that the drawn updates to w are only of illustrative nature, the updates are typically applied to the weights of a backbone.
Figure 2:
3.2 IDENTITY UPDATE: INTUITION IN SIMPLE CASE
On the backward pass, the negated incoming gradient -d//dy gives us the local information of where we expect solver solutions with a lower loss. We first consider the simple scenario in which -d /df/dy points directly toward another solution y", referred to as the "target". This means that there some 17 > 0 such that -17 -
dé y" y(w). This happens, for instance, if the final layer coincides with the &g loss (then 17 = 1/2), or for & loss with Y being a subset of {0, 1 (then = 1).
Our aim is to update in manner which decreases the objective value associated with y², i.c. (w,y"), and increases the objective value associated with the current solution y(w), i.e. (w, (W)). Therefore, y" will be favoured y(w) the solution in the updated optimization problem. This motivates us to set the replacement for the true zero gradient dl/dw to
dw (w.y" y(w)) = y y(w)
df dy
(2)
The scaling factor 17 is subsumed into the learning rate, therefore propose the update
Al de
(3)
dg
This corresponds to simply treating the solver negated identity the backward pass, hence call our method "Identity". An illustration of how the repeated application of this update leads to the correct solution is provided in Figures 2a and 2b.
Comparison Blackbox Backpropagation. in sensible update, we offer a comparison to BB by Vlastelica et al. (2020) that proposes an update
To strengthen the intuition of why update (3) results
BB
(y^(w) y(w)),
where y(w) is the solution from the forward pass and, on the backward pass, the solver called again on perturbed cost get y)(w (w) y(w + AdÉ/dy) Here, À > 0 is a hyperparameter that controls the locality of the implicit linear interpolation the loss landscape.
Observe that yı (w) serves target for our current y(w), similar to the role of y²* in computation (2). If in BB coincides with a steps size that Identity needs to reach the target y with update Aw, then
1p + x v(w)) = - - v(w)) - d
17 de d...
AB
(5)
Therefore, if dé/dy points directly toward neighboring solution, the Identity update is equivalent to the BB update with the smallest À that results a non-zero gradient (4). This situation
illustrated in Fig, 2c (cf. Fig. 2a). However, Identity does not require additional call to the solver on the backward pass, nor does it have an additional hyperparameter that needs to be tuned.
3.3 IDENTITY UPDATE: GENERAL CASE
We will now consider the general case, in which we do not expect the solver find better solution in the direction A' = -dé/ -dd/dy due to the constraints on Y. We show that we ignore the constraints on y and simply apply the Identity method, still achieve sensible update.
4

---

Published as a conference paper at ICLR 2023
Let wy be a fixed initial cost. For fixed step size O, we iteratively update the cost using Identity, i.c. we set wk+1 = Wi adWw for E N. We aim to show that performing these updates leads solution with a lower loss. As gradient-based methods cannot distinguish between nonlinear loss l and its linearization f(v) = f(y(w)) ) + {y y(w), dl/ dl/dy) at the point y(w), we can safely work with f in our considerations. We desire to find solutions with lower linearized loss than our current solution y(w), i.e. points in the set
Y" (v(ww) {y eyeY: f(v) < f(v(w)))
(6)
Our result guarantees that solution with lower linearized loss is always found if one exists. The proof is in Suppl. C.
Theorem 1. For sufficiently small > O, either Y (v(W)) is empty and y(wx) = y(w) for every k E N. there is E NN such that y(w)) Y (y(w)) and y(wx) = y(w) for all k <
3.4 EXPLOITING SOLVER INVARIANTS
In practice, Identity can lead to problematic cost updates when the optimization problem is invariant to certain transformation of the cost vector W. For instance, adding the same constant to every component of w will not affect its rank or top-k indices. Formally, this means that there exists mapping P: I" + Rn of the cost vector w that does not change the optimal solver solution, i.c.
arg min migmmngeess yEY (w, y) = arg min (P(w), y) for every w E W.
Linear Transforms. Let us demonstrate why invariants can be problematic in a simplified case assuming that P linear. Consider an incoming gradient dl/dy, for which the Identity method suggests the cost update NWw = -d//dy. We can uniquely decompose Alw into Aw Ali + Alwo where A'', P(Alw) E Tm P and Alwo = (I - P) ker P. Now observe that only the parallel update Alwi affects the updated optimization problem,
arg min(w - a.w, y) = argmin ((w -adw), y) yEY
wEY
(8)
arg aargmin(Peg (&ww)) ), v) arg min adwwi,y) yEY
yEY
for every w E W and for any step size > 0. In the second equality, we used
P(w ( P(w adww)) aP(Aw)) P(w adww),
exploiting linearity and idempotency of P.
In the case when user has control about the incoming gradient Aww dd//dy, the update Alwo in ker P can be much larger in magnitude than A'w, in Im P. In theory, updates were applied directly in cost space, this would not be very problematic, as updates in ker P do not affect the optimization problem. However, in practice, the gradient is further backpropagated to update the weights in the components before the solver. Spurious irrelevant components in the gradient can therefore easily overshadow the relevant part of the update, which especially problematic as the gradient is computed from stochastic mini-batch samples.
Therefore, it is desirable to discard the irrelevant part of the update. Consequently. for a given incoming gradient dl/ /dyy, we remove the irrelevant part (ker P) and return only its projected part
Ali
d dy
(10)
Nonlinear Transforms. For general P. we use the chain rule to differentiate the composed function y e P and set the solver's Jacobian identity. Therefore, for given w and an incoming gradient dé/dg, we return
de de
(11)
If P is linear, then ('(w) P and hence update (11) is consistent with linear case (10). Intuitively, we replace P(w aAw the above-mentioned considerations by its affine approximation P(w) (P) the term ('(w) plays locally the role of the linear projection.
Another view on invariant transforms is the following. Consider our combinatorial layer as a composition of sublayers. First, given w, we simply perform the map Pww:) and then pass it to
5

---

Published as a conference paper at ICLR 2023
the arg min solver. Clearly, on the forward pass the transform P does not affect the solution y(w). However, the derivative of the combinatorial layer is the composition the derivatives its sublayers, Le. (ww)) for the transform and negative identity for the arg min. Consequently, we get the very same gradient (11) on the backward pass. In conclusion, enforeing guarantees on the forward pass by mapping P is in this sense dual to projecting gradients onto Im P'.
Examples. In our experiments, we encounter two types of invariant mappings. The first one is the standard projection onto a hyperplane. It is always applicable when all the solutions in Y are contained in a hyperplane, i.e. there exists a unit vector a E IR" and a scalar b E IR such that (a. y) = b for all y E Y. Consider the projection of w onto the subspace orthogonal Pplane (w)a) = w (a, w)a. This results in
given by
arg min (aain(plaanc plane (w)))) v) arg min(w: v) (a, w)b = arg min(w, for every w E W, (12) NEY
VEY
NEY
thereby fulfilling assumption (7). This projection is relevant for the ranking and top-k experiment, in which the solutions live hyperplane with the normal vector a 1/v Therefore, the projection
P Pmean (w) = Plaaee (w 1/vR) = w 1/n
(13)
is applied on the forward pass which simply amounts to subtracting the mean from the cost vector.
The other invariant mapping arises from the stability of the arg min solution to the magnitude of
the cost vector. Due to this invariance, the projection onto the unit sphere (w) = w/ |/|| also
fulfills assumption (7). As the invariance the cost magnitude is independent of the solutions Y. normalization Poom is always applicable and we, therefore, test it in every experiment. Observe that
I
w & w
P norm (w) =
(14)
|wwll
|
and the first order approximation of Poomn corresponds to the projection onto the tangent hyperplane given by a = w and 1. When both P momm and Pmean are applicable, we speak about standardization Pau Prom o P Pameun- An illustration of how differentiating through projections affects the resulting gradients is provided in Fig. 9 in Suppl. D. An experimental comparison of the incoming gradient -dé/ dy and the Identity update Alw P'de/dy is examined in Suppl. B.1.
3.5 IDENTITY METHOD AS SOLVER RELAXATION
The Identity method can also be viewed as differentiating a continuous relaxation of the combinatorial solver on the backward pass. To see this connection, we relax the solver by a) relaxing the polytope Y to another smooth set Y containing Y and b) adding a quadratic regularizer in case Y is unbounded:
y(w) = arg min(w:y)
J(w.c) = arg min y) + |lull??.
(15)
yEYCE
,EÝ
Using this viewpoint, we can interpret the vanilla Identity method the loosest possible relaxation Y = R", and the projections Pmean: P and Pad relaxations of Y to hyperplane, sphere, and an intersection thereof, respectively. For a more detailed discussion, see Suppl. C.2.
3.6 PREVENTING COST COLLAPSE AND INDUCING MARGIN
Any arg min solver (1) is piecewise constant mapping that induces a partitioning of the cost space W into convex cones W, y = {w E W v(w) = y). Y, on which the solution does not change. The backbone network attempts to suggest a cost w E Wy y that leads if the predicted cost E W y lies close to the boundary of W,, it is potentially sensitive to small perturbations. The more partition sets (Wy..... Wy,) } meet at given boundary point w, the more brittle such a prediction w is, since all the solutions {v1 ........ 4 of w. For example, the zero cost w = is one of the most prominent points, as it belongs to the boundary of all partition sets. However, the origin is not the only problematic point, for example in the ranking problem, every point w = A1, À > 0, is equally bad as the origin.
correct solution y. However,
are attainable in any neighbourhood
The goal is to achieve predictions that are far from the boundaries of these partition sets. For Y = (0, 1 Rolínek et al. (2020a) propose modifying the cost to w' = w + Zy" g y²) before the solver to induce an informed margin a. However, this requires access the ground-truth solution y".

---

Published as a conference paper at ICLR 2023
We propose to instead add a symmetric noise p(E) to the predicted cost before feeding it to the solver. Since all the partition sets' boundaries have zero measure (as they are of a lower dimension), this almost surely induces margin from the boundary of the size [. Indeed, if the cost is closer to the boundary, the expected outcome will be influenced by the injected noise and incorrect solutions will increase the expected loss giving an incentive push the cost further away from the boundary. In experiments, the noise is sampled uniformly from { 2 2 ] where a > 0 is a hyperparameter.
In principle, careful design of the projection map P from Sec. 3.4 can also prevent instabilities. This would require that Im P avoids the boundaries of the partition sets, which is difficult to fully achieve in practice. However, even reducing the size of the problematic set by projection is beneficial. For example, the normalization Poorm avoids brittleness around the origin, and Pmean avoids instabilities around every w Al for ranking. For the other-less significant, but still wmobeematie-boundariet the noise injection still works in general without any knowledge about the structure of the solution set.
4 EXPERIMENTS
We present multiple experiments that show under which circumstances Identity achieves performance that is on par with or better than competing methods. The experiments include backpropagating through discrete sampling processes, differentiating through a quadratic assignment solver in deep graph matching, optimizing for rank-based metries in image retrieval, and synthetic problem including a traveling salesman solver. The runtimes for all experiments are reported in Sec. B.6.
4.1 BACKPROPAGATING THROUGH DISCRETE SAMPLERS
The sampling process of distributions of discrete random variables can often be reparameterized approximately as the solution to a noisy arg max optimization problem, see e.g. Paulus et al. (2020).
Sampling from the discrete probability distribution ~ p(y;w) can then be formulated as
= arg max yEY (w + c.y)
(16)
with appropriate noise distribution e. Typically a Gumbel distribution is used for e, but in certain situations, other distributions may be more suitable, e.g. Niepert et al. (2021) use a sum-of -f-gama-amma noise distribution model a top-k distribution on the solutions. Therefore, sampling fits our general hybrid architecture as illustrated in Fig. 1.
Discrete Variational Auto-Encoder (DVAE). In DVAE (Rolfe, 2017), the network layers before the sampling solver represent the encoder and the layers after the sampling solver the decoder. We consider the task of training a DVAE on the MNIST dataset where the encoder maps the input image to discrete distribution of k-hot binary vector of length 20 in the latent space and the decoder reconstructs the image.
The loss is the Negative Evidence Lower Bound (N- ELBO), which is computed as the sum of the reconstruc- tion losses (binary cross-entropy loss on output pixels) and the KL divergence between the marginals of the discrete latent variables and the uniform distribution. We use the same setup as Jang et al. (2017) and Niepert et al. (2021), details can be found in Suppl. I. Figure shows com- parison of Identity to I-MLE (Niepert et al., 2021), which uses the BB update. We observe that Identity (with stan- dardization Pas) achieves a significantly lower N-ELBO.
M-LEE
75
(Pand)
20
80
100
Figure 3: N-ELBO training progress on the MNIST train-set (k: = 10).
Learning to Explain. We consider the BeerAdvocate dataset (McAuley et al., 2012) that con- sists of reviews of different aspects of beer: appearance, aroma, taste, and palate and their rating scores. The goal is to identify a subset & of the words in the text that best explains a given as- pect rating (Chen et al., 2018: Sahoo et al., 2021). We follow the experimental setup of Niepert et al. (2021), details can be found in Suppl. B.I. As in the DVAE experiment, the problem is modeled as hoh binary latent representation with = 5, 10, 15. Identity also uses the Pua-
7

---

Published as a conference paper at ICLR 2023
We compare Identity against I-MLE, L2X (Chen
Table BeerAdvocate (Aroma) statistics over 10
et al., 2018), and Softsub (Xie and Ermon, 2019) in Tab. 1. Softsub is relaxation-based method designed specifically for subset sampling, in con- trast Identity and I-MLE which generie. We observe that Identity outperforms I-MLE and L2X, and is on par with Softsub for all Eval- uating Identity without projection shows that pro- jection is indispensable this experiment.
restarts. Projection is indispensable for Identity. Baselines results' are from Niepert et al. (2021).
Test MSE x100 1
Method
k:
k: 10
Id. (Pai)
2.62 + 0.14
2.47 0.11
2.39 = 0.04
Id. (no P)
4.75 + 0.06
4.43 0.09
4.20 0.11
I-MLE!
2.62 0.05
2.71
2.91 0.18
L2X
5.75
6.68 1.08
7.71 = 0.64
Softsubl
2.57 0.12
2.67 0.14
2.52 = 0.07
4.2 DEEP GRAPH MATCHING
Given a source and a target image showing an object of the same class (e.g. cat), each annotated with set of keypoints (e.g. right ear), the task is to match the keypoints from visual information without any access to the true keypoint annotation. We follow the standard experimental setup from Rolínek al. (2020b), in which the cost matrices are predicted by a neural network from the visual information around the keypoints, for details see Suppl. B.2. We report results for the two benchmark datasets Pascal VOC (with Berkeley annotations) (Ev- eringham et al., 2010) and SPair-71k (Min et al., 2019).
Table 2: Matching accuracy for Deep Graph Matching on Pascal VOC. Statistics over 5 restarts.
BB
Identity
P margin
Matching accuracy
0.01
noise
0.1
%
1.0
10.0
Table 2 lists the average matching accuracy across classes. We see that the use of margin is important for the success of both evaluated methods, which agrees with observations by Rolínek et al. (2020b). We observe that the induued margin achieves a similar effect the informed margin from Rolínek et al. (2020b). Analogous results for SPair-71k k are in the Suppl. B.2.
0.01
0.1
informed
1.0
10.0
0.01
0.1
Our results show that Identity without the projection step yields performance that is on par with BB, while Identity with the normalization step performs worse. Such behaviour is not surprising. Since the Hamming loss between the true and predicted matching is used for training, the incoming gradient for the solver di- rectly points toward the desired solution, as discussed in 3.2. Consequently, any projection step is rendered unnecessary, and possibly even harmful. Interestingly, the evaluation of BB with normalization, combination of methods that we only evaluated for completeness, appears to produce results that slightly outperform the standard BB.
noise
1.0
Promn
10.0
0.01
0.1
informed
1.0
10.0
4.3 OPTIMIZING RANK BASED METRICS IMAGE RETRIEVAL
In image retrieval, the task is to return images from a database that relevant a given query. The performance is typically measured with the recall metric, which involves computing the ranking of predicted scores that measure the similarity of image pairs. However, directly optimizing for the recall challenging, as the ranking operation non-differentiable.
Table 3: Recall R@l for CUB-
200-2011 with noise-induced margin.
BB Identity
P
Recall RØ1
0.001
0.01
We follow Rolinek et al. (2020a) in formulating ranking as an arg min optimization problem with linear cost, i.e. rk(w) = arg min (w, y). where II, is the set of all rank permutations and w RR the vector of scores. This allows us to use Identity to directly optimize an architecture for recall. We perform experiments the image retrieval
0.1
0.001
Pud
0.01
0.1
TT+
8

---

Published as a conference paper at ICLR 2023
accuracy (%)
100
100
norm of w
accuracy
50
25
25
0.0
0.1
0.25
0.5
0.75
0.0
0.1
0.25
0.5
0.75
0
25
50
75
100
Gradient noise level
Corrupt ratio
epochs
(a) Gradient noise
(b) Label corruption p
(c) Cost norm ||]]|
Figure 4: Susceptibility to perturbations and cost collapse in TSP(20).
BB
Identity
(a) Adding noise to the gradient dl/dg with std a affects Identity much less than BB. (b) Cornupting
labels y" with probability p/k: (c) Average cost norm with gradient noise = 0.25. The markers indicate the best validation performance.
benchmark CUB-200-2011 (Welinder et al., 2010), and follow the experimental setup used by Rolínek et al. (2020a). Details are provided in Suppl. B.3.
The results shown in Tab. 3. We report only the noise-induced margin: the informed one performed similarly, see Suppl. B.3. Note that without the standardization Pst.. Identity exhibits extremely low performance, demonstrating that the projection step crucial element of the pipeline. The explanation is that, for ranking- baseed loss, the incoming gradient does not point toward achievable solutions, discussed in Sec. 3.2. For more details, including additional evaluation of other applicable projections, see Suppl. B.3. We conclude that for the retrieval experiment, Identity does not match the BB performance. Presumably, this because the crude approximation of the permutahedron by sphere ignores too much structural information.
4.4 GLOBE TRAVELING SALESMAN PROBLEM
Finally, we consider the Traveling salesman Problem (TSP) experiment from Vlastelica et al. (2020). Given set of k country flags, the goal for TSP(k) is to predict the optimal tour on the globe through the corresponding country capitals, without access to the ground-truth location of the capitals. A neural network predicts the location of set of capitals on the globe, and after computing the pairwise distances of the countries, TSP solver is used to compute the predicted optimal TSP tour, which is then compared to the ground-truth optimal tour. Setup details can be found in Suppl. B.4.
Corrupting Gradients. We study the robustness of Identity and BB to potential perturbations during training in two scenarios: noisy gradients and corrupted labels. We inflict the gradient with noise to simulate additional layers after the solver. In this setting we add N/O,, o²) to dé/dy. In real-world scenarios, incorrect labels are inevitably occurring. We study random fixed corruptions of labels in the training data, by flipping entries in y" with probability p/k:
In Fig. 4a and 4b we observe that Identity performs on par with BB for the standard non-corrupted setting, and outperforms it in the presence of gradient perturbations and label corruptions. Figure 4c shows the average norm of the cost w in the course of training under gradient noise with o = 0.25. After epoch 50, as soon as is set to zero, cost collapse occurs quickly for BB, but not for Identity. In the TSP experiments Identity uses standardization Pad-
CONCLUSION
We present a simple approach for gradient backpropagation through discrete combinatorial solvers with linear cost function, by treating the solver as negative identity mapping during the backward pass. This approach, in conjunction with the exploitation of invariances of the solver via projections, makes up the Identity method. additional computationally expensive call to the solver on the backward pass. We demonstrate in numerous experiments from various application areas that Identity achieves performance that is competitive with more complicated methods and is thereby viable alternative. We also propose and experimentally verify the use of noise to induce a margin on the solutions and find that noise in conjunction with the projection step effectively increases robustness and prevents cost collapse. Finally, we analyze the robustness of methods to perturbations during training that can come from subsequent layers incorrect labels and find that Identity is more robust than competing methods.
hyperparameter-free and does not require any

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This work was supported from Operational Programme Research, Development and Education Project Postdoc2MUNI (No. 10000...9/0.000.0//15 053/0016952). We thank the International Max Planck Research School for Intelligent Systems (IMPRS-IS) for supporting Anselm Paulus. We acknowledge the support from the German Federal Ministry of Education and Research (BMBF) through the Tübingen AI Center. This work was supported by the Cyber Valley Research Fund.
REPRODUCIBILITY STATEMENT
We provide extensive experimental details and all used hyperparameters for Discrete Samplers in Suppl. B.I, Deep Graph Matching in Suppl. B.2, Rank Based Metrics Suppl. B.3, Globe TSP in Suppl. B.4, and Warcraft Shortest Path in Suppl. B.5. The datasets used in the experiments, i.e. BeerAdvocate (McAuley et al., 2012), MNIST (LeCun et al., 2010), SPair-71k (Min et al., 2019), Globe TSP and Warcraft Shortest Path (Vlastelica et al., 2020), CUB-200-2011 (Welinder al., 2010) are publicly available, A curated Github repository for reproducing all results is available at -idetiitt...entty....
REFERENCES
Marin Vlastelica, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolínek. Differentiation of blackbox combinatorial solvers. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: //openreview.oo net/ formm? B=BkvvoSS.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9508-9519. Curran Associates, Inc., 2020. URL https: httttp::/pproeeediinn new.iiinnnn......ooooor..... cc cc/paper/ 2atpperr/220////0
Michal Rolínek, Vít Musil, Anselm Paulus, Marin Vlastelica P., Claudio Michaelis, and Georg Martius. Optimizing rank-based metries with blackbox differentiation. In 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 7617-7627. Computer Vision Foundation IEEE, 2020a. doi: (L109/CVVR42200.202000
URL bttps:://penacceee theevf.com content_cvee http:////tnnn/ooooonooreooo/ Wi thtthhhBlckbbocccmc www.:/efeeeeiiaaiionoccccc
html.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In Andrea Vedaldi, Horst Bischof. Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision - ECCV 2020 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XXVIII, volume 12373 of Lecture Notes in Computer Science, pages 407-424 Springer, 2020b. doi: 10. 1007/ 100-3-030-58604-- 25. URL https::t///c....... /doei..///..////// org / 10. 00w.111077770000----555 25.
Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius. Comboptnet: Fit the right np-hard problem by learning integer programming constraints. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Re- search, pages 8443 8453. PMLR, 2021. URL http: proceedineeeesseeee mll. mwr.press// paulus21a. html.
Brandon Amos and J. Zico Kolter. Optnet: Differentiable optimization as layer in neural networks.
In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning. ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 136-145. PMLR, 2017. URL http:// proceedi ngs ml www..s.sssvee...........e. amos 17 7 html.
10

---

Published as a conference paper at ICLR 2023
Po- Wei Wang, Priya L. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6545-6554 PMLR, 2019. URL http:: Utthttp::/pprrceed nggs mlr. wwwpppessseeeeeeee v97 //wg//agggggg...o//a 9e .html.
Aaron M. Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as a layer. In The Thirty-Fourly AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 1504-1511 AAAI Press, 2020. URL httph::t///oooot aaai.
org/ hte/indexx..o php/ AAAI (AAI/araa wtt.eaattieeeeeeeeeeeeeeeeeeeeee /wwee/ii///////////e// 5509.
Marin Vlastelica P., Michal Rolínek, and Georg Martius. Neuro- algorialgoi policies enable fast combinatorial generalization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 19575-10585. PMLR, 2021. html.
URL http:////// httpp/ppoceee...eeoee mir. wtt.:mmww.p.p..eeeememmmmmmeeese
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th Interna- tional Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1126-1135. PMLR, 2017. URL http:/ ptwppeeineeng...eeeeepppppp...se mlrr prwss v finn 7 html.
Aniruddh Raghu, Maithra Raghu, Samy Bengio, and Oriol Vinyals. Rapid learning or feature reuse? towards understanding the effectiveness of MAML. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. / opwnreviee.eeeeeeeee/ee net/ forum? rdt.gg
URL https:tt/////
Akshay Agrawal, Brandon Amos, Shane T. Barratt, Stephen P. Boyd, Steven Diamond, and J. Zico Kolter. Differentiable convex optimization layers. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bucc Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2019a. URL https: http::::////cceeeeeeeeeee neurips cctpaper/2019 hash/ Abstract. html.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 10657-10665.
Computer Vision Foundation IEEE, 2019, doi: 10. httpt//mmmmeeeeeeeeeeeeeee Meta Maeeeeea--eeeennee Learning openaccess. thecvf.ssss.eestteeeeeeee wwwpeeewwcccooceeeeoooeooeeeeeee com wttp:////cccooooccoooo/ooooccot. wwweeeentneeeeeeeeeeeeee With_DDifferrettabbee__coove ottp://www...araaaaaaaoooooooor.
URL http://
html.
Akshay Agrawal, Shane Barratt, Stephen Boyd, Enzo Busseti, and Walaa M Moursi. Differentiating through cone program. J. Appl. Numer. Optim, 1(2):107-115, 2019b. URL https://///// //doi. org/10.23300 jano 2019........0
Justin Domke. Generic methods for optimization based modeling. In Neil D. Lawrence and Mark A. Girolami, editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012, volume 22 of JMLR Proceedings, pages 318-326. JMLR.org, 2012. URL / htttt:::/procceennngg ml press/ / domke 2, html.
Adam N. Elmachtoub and Paul Grigas. Smart "predict, then optimize". Manag, Sci., 68(1):9-26, 2022. doi: 10.12277mmss.2220.399 URL https: wtwp/iorrr1.1.1 wttrg//..118/////
Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit MLE: backpropagat-
ing through discrete exponential family distributions. In Mare Aurelio Ranzato, Alina
11

---

Published as a conference paper at ICLR 2023
Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural In- formation Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 14567-14579, 2021. URL 7a43033 9c130033111000
wwwiing...nnneuuneeeee cetarrppsccc....... cc/ wwwp/paper/aae /202/h/hh2/// Abst .html.
Brandon Amos, Vladlen Koltun, and J. Zico Kolter. The limited multi-label projection layer. CoRR, abs/1906.08807, URL http: / www.v..oro......oo..... abs/ 110.//96.000000 08707.
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In Pruceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 950-959. PMLR, 2020. URL http:/ http:://proeee http:://ppocceeding. mlr. www.r.pees//vee /v119 bblondee20e html.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In The Thirty-Third AAAI Conference on Artificial Intelligence AAAI 2019. The Thirty-First Innovative Applications of Artificial In- telligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- February 1, 2019, pages 1658-1663 AAAI Press, 2019. doi: 10. wtt////a...33/011.... 1333300113301111000 1658. URL https: //doi. 10. 609 /ww./aaaaa...//////...aa.a..aa.. 133.01.33011111111..1.
Marii-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 353-362. PMLR, 2018. URL http:/ / prwceedings...ccee mlr. press / v00 caallcanlle 8a html.
Elias Boutros Khalil, Pierre Le Bodic, Le Song. George L. Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 724-731. Press, 2016. URL http:/ /twww//wwww/////////////. aaai .rg/ ocs/ bess/indxx..m php AAAI/ AAAII 6/ pwppr/viww//eepetpppppttea 12514.
Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-base based approximation of strong branching. INFORMS J. Comput., 185-1199,99, 2017. URL https: //doi. 10. 1 / joc 2016 0723.
Mislav Balunovic, Pavol Bielik, and Martin T. Vechev. Learning to solve SMT formulas. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 10338-10349 10349, 2018. URL https: http:::://ppooceedee.m neuriiseuipp... wwtpcc/ppaaa cc/pappr//// 2018/hase 683368333600 2aaaah/663300000075556681l 7ww511669161111eb36222 htw.:eeeeeeeeeebbaaaaatttt.tt.ee
Jayanta Mandi and Tias Guns. Interior point solving for lp-based prediction-oopiimisttio. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7272-7282. Curran Asso- ieciinngs.nuuuu wwt.n/ps...pppprreeeeeeppp cc/ pwtpppppe///////e/.eep /020/file/
ciates, Inc., 2020. URL wtw.dddccceeeffffeeeeeeeeeeeeeee Papere pdf. 51311013es 3e0111511100 adeec333342ccc5511
Yingeong Tan, Daria Terekhov, and Andrew Delong. Learning linear programs from opti- mal decisions. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, ed- itors, Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 19738-19749, 2020. URL https: httpas:///oocceeeeeeeeeeeo neurips htc/papper2022/FF12 e 11448875c12109e444
Pawp:e04408---Pe..d.d. pdf.
Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net, 2017. URL https:
htt.httss://opeeeeeeee http:///peeeeeeeeee net. forrmmormmm B= 9mx SFx.
12

---

Published as a conference paper at ICLR 2023
MohammadReza Nazari, Afshin Oroojlooy, Lawrence V. Snyder, and Martin Takác. Reinforce- ment learning for solving the vehicle routing problem. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò vances in Neural Information Processing Systems 31: Annual Conference on Neural Informa- fion Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages neurips cc 2aap///0088hhhh/////
and Roman Garnett, editors, Ad-
9861-9871, 2018. URL ottpl///5222e/taaaaaaaaeeoeeeee Absttsgaaaas-s-aatttttct html.
Wei Zhang and Thomas G Dietterich. Solving combinatorial optimization tasks by reinforcement learning: A general methodology applied to resource- constraied scheduling, Journal of Artificial Intelligence Research, 1(1):1-38, 2000.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL https:/ wowooepeeevveeeeeeeeeeeeeeeeevee ew. net. forum?ide TXr kCZ.
Petar Velickovic, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In 8th International Conference on Learning Representa- lions, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
https::/openreet wwt.wwiwwwweeeeeee.......e..e httt:/oormmiidd-kkteee
Andreea Deac, Petar Velickovic, Ognjen Milinkovic, Pierre-Luc Bacon, Jian Tang, and Mladen Nikolic. XLVIN: executed latent value iteration nets. CoRR, abs/2010.13146, 2020. URL
https://arxiv org/ awws//0//0 13146.
Bingjie Li, Guohua Wu, Yongming He, Mingfeng Fan, and Witold Pedrycz. An overview and experimental study of learning-based optimization algorithms for the vehicle routing problem. JEEE CAA J. Autom. Sinica, ((7):1115-11333 2022. doi: 10.1109/JAS 202...022...2.... URL
https:/ /tt///doo //o...o..////////// www.oogg............ 11090....1111....... 201///AAS.222222...222222
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnet, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 1062-6071, 2018. URL https: /ttpas:///roceeee http///occeeenngseeeeeeeeee wweerrpsscc//eeeee wwtppppe//01/..... 20tp///0/18hhhh///// / 67880768420188 3cedadbe 6b0ba0314 Abstract. htmll.
Jeevana Priya Inala, Osbert Bastani, Zenna Tavares, and Armando Solar-
Synthesizing programmatic policies that inductively generalize. In 8th International Conference on Learning Representutions, ICLR 2020, Addis Abuba, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https:://ppp//eee
net forum? i d= 80ANFDH.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating propagating gradients through stochastic neurons for conditional computation. CoRR, abs/1308.3432, 2013. URL
http://arxiv.
wwogor/aaooo abs/1308 3432.
Geoffrey Hinton. Neural networks for machine learning, coursera. Coursera, video lectures, 2012.
Frank Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):388 1958. ISSN 0033-295X. doi: 10.1039/h0042519. URL http:// /xtp:://xx.. doi. wtt./o..o//1111111 /ttp//...37//002255500
Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax, In 5th International Conference on Learning Representutions, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL sttpp::/opennae net/
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley J. Osher, Yingyong Qi, and Jack Xin. Under- standing ttraight-througe estimator in training activation quantized neural nets. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL https:tt////c /tttps://openrevvieet net wtwp/oorre//ieeeee 4 RccKQ.
13

---

Published as a conference paper at ICLR 2023
Max B. Paulus. Dami Choi, Daniel Tarlow, Andreas Krause, and Chris J. Maddison. Gradient estimation with stochastic softmax tricks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florine Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. https: /procceee/////e////// ngs. neuri wwt.rrpp..ccpppppeeeeeeee Abstract htmll.
2020/hash//
Jason Tyler Rolfe. Discrete variational autoencoders, In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: opwneeeeeeeeeeeeee
/eeetffrummmm htt.//oooommnnnooioooi d=ryMxXPFex
Julian McAuley, Jure Leskovec, and Dan Jurafsky. Learning attitudes and attributes from multi-aspect reviews. In 2012 IEEE 12th International Conference on Data Mining, pages 1020-1025. IEEE, 2012.
Jianbo Chen, Le Song, Martin J. Wainwright, and Michael I. Jordan. Learning to explain: An theeooa perspective on model interpretation. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Ma- mlr.
Machine Learning. ICML 2018,
chine Learning Research, pages 882-891. PMLR, 2018. URL press / /v80/ chen18 8 hhmml.
Subham Sekhar Sahoo, Subhashini Venugopalan, Li Li, Rishabh Singh, and Patrick Riley. Scaling symbolic methods using gradients for neural model explanation. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nes, 2021. URL https: opwnreview. n forum?ideee - jddDDDP
Sang Michael Xie and Stefano Ermon. Reparameterizable subset sampling via continuous relaxations.
In Sarit Kraus, editor, Proceedings the Errenty-Eighhi International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 3919-3925. ijcai.org, 2019. doi: 10.24963/ijcai.ii 201 9/544. URL httpst / doi org/10 2496349334 / jcai 201 9/44.
Mark Everingham, Luc Van Gool, Christopher K. I. Williams, John M. Winn, and Andrew Zisserman. The pascal visual object classes (VOC) challenge. Int. J. Comput. Vis., 88(2): doi: 120007//112330000-022777 303-338, 2010.
URL https:/ http:///doo.oog///////
Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho. Spair-71k: A large-scale benchmark for semantic correspondence. CoRR, abs/1908. 105543, 2019. URL http:p::/wa.w.....//o. 1908. 10543.
Peter Welinder, Steve Branson, Takeshi Mita, Catherine Wah, Florian Schroff, Serge Belongie, and Pietro Perona. Caltech-UCSD Birds 200. Technical Report CNS-TR-2010-001, California Institute of Technology, 2010.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. att labs, 2010.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neu- ral networks. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Ro- man Garnett, editors, Advances Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 4107-4115, 2016. URL https: http://:///p/peppeeeeeeeeeeeeeee nww.ipu....... wtcppaper/2000 6 /ashh/ Abstract
Aot html.
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relax- ation of discrete random variables. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, net www.oooiddiniiisse......
2017. URL https: http::///pppeevveeeeeeee
Paul Swoboda, Carsten Rother, Hassan Abu Alhaija, Dagmar Kainmüller, and Bogdan Savchynskyy. A study of lagrangean decompositions and dual ascent solvers for graph matching. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA. July 21-26, 2017, pages 7072-7071. IEEE Computer Society, 2017. doi: 10.1 URL https:tpp/.. / org 10. 11 /9///P/ 2017. 747.
14

---

Published as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas. NV, USA, Jume 27-30. 2016, pages 770-778. IEEE Computer Society, 2016. doi: 10.1 109/CVPR.2016.90 URL. ht.ps:///// /oi. wtwpiiorg/..... 11.90.11 2016 90.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022. URL https: /www. gurobi com.
Mathieu Blondel. Structured prediction with projection oracles. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alcch-BBuc, Emily B. Fox, and Roman Garett, editors, Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages neurips cc/paper/2013 9/hash/ 4 355 Abbttttracbbbbttteeeeetec .tt.raattthtt..... html.
22145-12155 2019. URL http:: / 7990ec4
15

---

Published as a conference paper at ICLR 2023
A STRAIGHT THROUGH ESTIMATOR AND IDENTITY
The origins of the Straight-through estimator (STE) are in the perceptron algorithm (Rosenblatt, 1958) for learning single-layer perceptrons. If the output function is a binary variable, the authors use the identity function as proxy for the zero derivative of the hard thresholding function. Hinton (2012) extended this concept to train multi-layer neural networks with binary activations, and Hubara et al. (2016) 6) used the identity to backpropagate through the sign function, which is known as the saturated STE.
Bengio et al. (2013) considered training neural networks with stochastic binary neurons modelled as random Bernoulli variables v()) E {0. 1}, with p E [0. 1]. which are active (equal to one) with probability p and inactive (equal to zero) with probability 1 p. This can be reparametrized using the c), with c Unif([O, 1)). In the next step, Bengio et al. (2013) follow previous work by employing the identity as replacement for the uninformative Jacobian of the hard thresholding function, and coin the term Straight- through estimator for it.
hard thresholding function as (p) =0)
This application of the STE for differentiating through discrete sampling process allows for an interesting probabilistic interpretation of the STE. To see this, note that the same Jacobian replacement as the one suggested by the STE, i.c. the identity function, is computed by treating the sample on the backward pass as if it were the expected value of the stochastic neuron, i.e.
d dp
d dp
((t)
I.
(17)
dp
This interpretation has also been considered by Niepert al. (2021); Jang et al. (2017), as it allows the extension of the STE concept to more complicated distributions. Most prominently, it has been applied in the setting of categorical distributions by Jang et al. (2017). Encoding classes as one hot vectors Y = =fe 1d distribution
1 they first define a distribution over classes as discrete exponential family
exp((y, w)) (y) Ejer exp( (ū.
(18)
Following the STE assumption, we now want to sample from the distribution on the forward pass, and treat it on the backward pass as if it were the expectation of the distribution. We can easily calculate the expectation as
E Eyrop lv] =
Σ (y) = softmax(w),
(19)
YEY
and therefore the generalization of the STE gives the Jacobian replacement
d dw ((w)
d
d softmax(w)
dw Ey-pulll
(20)
du
Jang et al. (2017) arrive at this result through different reasoning by using the Gumbel-Argmax trick to reparametrize the categorical distribution as a stochastic argmax problem, and then relax the argmax to softmax (see Paulus et al. (2020) for more detailed discussion). Due to the derivation involving the Gumbel distribution, they refer to this estimator as the Straight-throus throuuh Gumbel Estimator.
Note, that for general distributions, the expectation involved in applying an STE according to the previously described scheme is unfortunately intractable to compute, as exponentially many structures need to be considered in the expectation. This is the case even for distributions top-k distribution considered in Sec. 4.1. Note, that this is the starting point for the motivation of Niepert al. (2021), 1), who proceed by applying the concepts observed in Vlastelica al. (2020) to differentiating through general constrained discrete exponential family distributions.
simple as the
From the previous examples, we that our Identity method and the STE are closely related. In fact, treating a hard thresholding function as identity on the backward pass is a special case of our method. To see this, we only need to phrase the thresholding function as the solution an optimization problem
(w) arg max(y, w)) vE(0.13d
(21)
16

---

Published as a conference paper at ICLR 2023
for which the Identity method suggests the identity function Jacobian replacement, thereby matching the STE. From the discussion above, we know that this can also be interpreted in a probabilistic way for sampling from stochastic Bernoulli processes.
However, it is also apparent that this correspondence does not extend to other distributions. To see this, we reconsider the case of a discrete exponential family distribution over the set of one-hot vectors Y. Following Jang et al. (2017) and Maddison et al. (2017), we can simulate the sampling process by computing the solutions to stochastic argmax problem, i.e.
y Pw
y arg max(w + E,, e~ (0.1).
(22)
DEY
Here, (0, 1) denotes the d-dimensional Gumbel distribution. As described above, applying the STE yields the Jacobian of the softmax function as the replacement for the true zero Jacobian. In contrast, the Identity method (without projections), still returns the identity as the replacement. The benefit of this simplicity is that can still apply our method to general distributions, where computing the expectation over all structures is intractable.
As final remark, note that the term STE is somewhat overloaded, as in addition the formulation above, it has been used to refer to any kind of operation in which some block is treated as an identity function on the backward pass. For example, Bengio al. (2013) also consider the case of replacing on the backward pass not only the thresholding function, but also a preceding sigmoid computation with the identity function. Yin al. (2019) even refer to the STE for cases of replacing a thresholding function with a leaky relu function on the backward pass. In this much looser sense, our Identity method also falls into the category of STEs, as we also replace a computational block with the identity function on the backward pass.
B EXPERIMENTAL DETAILS
B. BACKPROPAGATING THROUGH DISCRETE SAMPLERS
DVAE on MNIST. Consider the models described by the equations 0 fa(x), ply: 0), fa(y) where x E X' is the input, E O is the output, and fe: X' + 0 is the encoder neural network that maps the input x to the logits and fa: y + Z is the decoder neural network, and where }' is the set of all k-hot vectors. Following Niepert et al. (2021), we set in sampling (16) as the Sum-of-Gamme distribution given by
T
(1 k T 7)
SoG(k, s)
Gamma
- loggs)
(23)
k
where s a positive integer and Gamma(a, 3) is the Gamma distribution with (a, 3) as the shape and scale parameters.
We follow the same training procedure as Niepert et al. (2021). The encoder and the decoder were feedforward neural networks with the architectures: 512-256-20 x 20 and 256-512-784 respectively. We used MNIST (LeCun et al., 2010) dataset for the problem which consisted of 50, 000 training examples and 10, 000 validation and test examples each. We train the model for 100 epochs and record the loss on the test data. In this experiment, we use
Id (no P)
210
(Fieen)
k = 10 i.e. sample 10-hot binary vectors from the latent space. We sample the noise from SoG with s = 10 and 10.
90
Id. (Phorm)
70
Idl. (Pars)
Additional Experimental Results. To assess the effect of the individual projections that make up Pad. we eval- uate our method using only Pmean or Paem- The results reported in Fig. 5 show that both projections increase the performance individually (with a much larger effect of Promm than P P, but combined they perform the best.
20
100
Figure 5: N-ELBO over training epoch for DVAE MNIST (k: 10), com- paring I-MLE with Identity for different projections.
17

---

Published as a conference paper at ICLR 2023
This is intuitively understandable in terms of viewing projections as solver relaxations (as described in Suppl. C.2). No projection, mean projection. normalization, and standardization correspond to relaxations of Y to R", hyperplane H, hypersphere S, and the intersection S H, respectively, which increasingly better approximate the true Y.
Additionally, examine how the spurious irrelevant part of the update direction returned by the Identity method without projection can lead to problematic behaviour. First, we test whether adaptive optimizers contribute to the problematic behaviour by adapting the learning rate to the irrelevant component of the update. As reported in Fig. 5, we observe a large performance gap between using projections and not using projections in the DVAE experiment. Therefore we rerun this experiment with an SGD optimizer instead of Adam, to check whether a non-adaptive optimizer is able to outperform the adaptive one. The results are reported Fig. 6, where we observe a slightly improved performance from the SGD optimizer, but no major difference between the the optimizers.
Next, we examine how much differentiating through the projection affects the returned gradient in terms of magnitude and direction. In Fig. 7 we compare the incoming gradient -de ddd/dy and the returned update direction A'w after differentiating through the projection in terms of norm ratio and cosine similarity. We observe that the gradient is significantly altered by the projection, i.e. the cosine similarity between the original and the projected gradient is smaller than 0.05. Given that with the projection the loss is optimized well (in contrast to not using projections), we conclude that relevant information indeed retained whereas spurious directions are removed.
90
230
80
220
Adam
Adam
210
SGD
SGD
0
60
80
100
40
80
100
(a) Identity using Pad
(b) Identity with no transform P.
Figure 6: Training progress of DVAE experiment on the MNIST train-set (A: 10), comparing the Identity method for different optimizers. Reported is N-ELBO over training epoch.
Learning to Explain. The entire dataset consists of 80k reviews for the aspect Appearance and 70k reviews for all the remaining aspects. Following the experimental setup of Niepert al. (2021), the dataset was divided into 10 different evenly sized validation/test splits of the 10k held out set. For this experiment, the neural network from Chen et al. (2018) was used which had 4 convolutional and I dense layer. The neural network outputs the parameters 0 of the pdf ply; 0) over h-hot binary latent masks with & = 5, 10, 15. The same hyperparameter configuration was the same as that of Niepert et al. (2021). We compute mean and standard deviation over 10 models, each trained on one split.
10a
norm ratio
10-1
cosine similarity
10-2
0
50
100
Figure 7: Training progress of DVAE on MNIST (A: 10), comparing the incoming gradient dd/dy with the up- date direction computed by the Identity method with projec- tion Pad- Reported are the norm ratio and cosine similar- ity over training epoch.
B.2 DEEP GRAPH MATCHING
We closely follow the experimental setup in Rolínek et al. (2020b), including the architecture of the neural network and the hyperparam- eter configuration to train the network.
The architecture consists of pre-trained backbone that, based on the visual information, predicts feature vectors for each of the keypoints in image. The keypoints are then treated nodes of a graph, which is computed via Delauney triangulation. A graph neural network then refines the keypoint features by employing geometry-aware message passing scheme the graph. A matching instance established by computing similarity scores between the edges and nodes of the keypoint graphs of two images via a learnable affinity layer. The negated similarity scores are then used as inputs to
18

---

Published as a conference paper at ICLR 2023
the graph matching solver, which produces binary vector denoting the predicted matching. This matching is finally compared to the ground truth matching via the Hamming loss. For a more detailed description of the architecture, Rolinck et al. (2020b).
We rum experiments on SPair- (Min et al., 2019) and Pascal VOC (with Berkeley annotations) (Ev- eringham et al., 2010). The Pascal VOC dataset consists of images from 20 classes with up to 23 annotated keypoints. To prepare the matching instances we use intersection filtering of keypoints, i.e. we only consider keypoints that visible in both images of pair. For more details on this, refer the reader to Rolínek et al. (2020b). The SPair-7Ik dataset consists of 70, 958 annotated image pairs, with images from the Pascal VOC 2012 and Pascal 3D+ datasets. It comes with a pre-defined train-valicee rrin-validation-tee test split of 53, 340-5,25 184-12, 234.
We train all models for 10 epochs of 2000 training iterations each, with image pairs processed in batches of 8. As reported in Rolínek et al. (2020b), we set the BB hyperparameter À = 80. We use the Adam optimizer with an initial learning rate of 2 x 10-3 which halved every epochs. The learning rate for finetuning the VGG weights is multiplied by 10-2 As in Rolínek et al. (2020b) use a state-of-the-arr dual block coordinate ascent solver (Swoboda et al., 2017) based on Lagrange decomposition to solve the combinatorial graph matching problem.
We report the results from Tab. again with their corresponding numbers in Tab.
Table 4: Matching accuracy (f) for Deep Graph Matching.
Pascal VOC
SPair-71k
P
margin
Identity
BB
Identity
BB
77.2 0.7
74.9 + 0.9
78.6 0.4
78.1 0.4
0.01
77.6
0.7
74.6 + 0.8
dl
78.7 + 0.3
77.9 + 0.5
noise
0.1
78.6 0.4
78.0 + 0.9
%
79. + 0.6
78.8 0.7
1.0
80.1 90.1 0.8
79.0
0.4
%)
10.0
0.6 78.8
79.8 0.4
77.7
78.2 0.4
0.01
78.5 + 0.5
76.8 + 0.6
+8.
78.7 0.3
0.1
0.6
79.3
78.9 7..1
0.4
informed
1.0
80.1 0.6
78.6 0.2
10.0
77.9
78.7 0.6
0.5
68.6 + 20
72.6 1.0
63.5 + 0.8
75.9 0.8
66.7
0.6
0.01
76.3 0.1
76.3
78.9 + 0.5
7..1
78.2
0.1
80.1 78.1
77.3
7.2
noise
1.0
79.1
81.2
0.2
0.3
P nomm
10.0
79.0 0.7
81.1+0.3
77.6+0.4
80.3+0.3 0.3
0.01
76.9
7 1.0
0.3
78.5 0.2 0.2
0.1
1.11
79.7
77.7
78.7
informed
1.0
73.7
80.8
7..4
80.2 + 0.4
HU
4H
10.0
74.2 + 0.9
79.7 0.6
74.4
80.1 + 0.2
66
76
80
70
76
80
B.3 RANK-BASED METRICS - IMAGE RETRIEVAL EXPERIMENTS
Ranking as Solver. Ranking can be cast combinatorial arg min optimization problem with linear cost by simple application of the permutation inequality as described in Rolínek et al. (2020a). holds that
rk (w) = arg min(w,y): yEll.
(24)
where II, is the set of all rank permutations and w E R is the vector of individual scores.
popular metric in the retrieval literature recall at K, denoted by r@K, which can be formulated using ranking
rK(wwy") [ if there is E rel(y") with rk(w), S K
(25)
otherwise,
where E N. w R" are the scores, y" E {0, 13" are the ground-truth labels and rel(y") = {i: o =1 is the of relevant label indices (positive labels). Consequently, r K is going to be
19

---

Published as a conference paper at ICLR 2023
positively labeled element is among the predicted top K ranked elements. Due computational restrictions, at training time, instead of computing r@k over the whole dataset a sample- based version is used.
sample-based
Recall Loss. Since r K depends only on the top-ranked element from y², the supervision for r is very sparse. To circumvent this, Rolínek et al. (2020a) propose loss
(w, (w))")))))--))))))>")))) rell (1)
log(1 + log + rk(w); rk(w))))
(26)
sErelty")
where rk(w)) denotes the rank of the i-th element only within the relevant ones. This loss is called loglog in the paper that proposed it. We follow their approach and use this loss in all image retrieval experiments.
Experimental Configuration. We closely follow the training setup and procedure reported in Rolínek et al. (2020a). The model consists of pre-trained ResNet50 (He et al., 2016) backbone in which the final softmax is replaced with a fully connected embedding layer, producing a 512- dimensional embedding vector for each batch element. These vectors then used to compute pairwise similarities between batch elements. The ranking of these similarities is then used to compute the recall loss (26), for additional details we refer the reader Rolínek et al. (2020a).
We train all models for 80 epochs using the Adam optimizer, using a learning rate of 5 x 10-7, which was the best performing learning rate for both Identity and BB out of a grid search over 5 learning rates. In all experiments a weight decay of 4 x 10 is used, as well as drop of the learning rate by 70% after 35 epochs. The learning rate of the embedding layer is multiplied by following previous work. The BB parameter À was set to 0.2 for all retrieval experiments. Images are processed in batches of 128, and three previous batches are always kept in memory to compute the recall to better approximate the recall over the whole dataset, see Rolínek et al. (2020a) for more details.
Sparse Gradient & Difference between Identity and BB. As described in Sec. 4.3, Identity performs worse than BB in the retrieval experiments. The reason is the sparsity of the gradient generated from the loss (26): it only yields nonzero gradient for the relevant images (positive labels), and provides no information for the images irrelevant to the query. This sparseness makes training very inefficient.
The BB update circumvents this by producing a new ranking for a perturbed input. The difference between the two rankings is then returned as the gradient, which contains information for both positive and negative examples. This process is illustrated in Figure 8a.
Ablations. To assess the effect of the individual projections that make up Psd. also evaluate our method using only Pmean or Poom and report them in Tab. 5. We observe the same trend as for the DVAE ablations reported in Fig. 1. and therefore refer to the same explanation in terms of increasingly tight relaxations of the solution set.
B.4 GLOBE TSP
Dataset. The training dataset for TSP(k) consists of 10 000 examples where each datapoint has element subset sampled from 100 country flags as input and the output is the optimal TSP tour represented by an adjacency matrix. We consider datasets for k: 5, 10, 20. For additional details, see Vlastelica et al. (2020).
Architecture. A set of l flags is presented to a convolutional neural network that outputs k 3- dimensional coordinates. These points are then projected onto 3D unit sphere and then used to construct the & & distance matrix which is fed to TSP solver. Then the solver outputs the adjacency matrix indicating the edges present in the TSP tour. The loss function an LI loss between the predicted tour and the true tour. The neural network is expected to learn the correct coordinates of the countries' capitals on Earth, up to rotations of the sphere. We use the gurobi (Gurobi Optimization, LLC, 2022) solver for the MIP formulation of TSP.
For the Globe TSP experiment we use a convolutional neural network with 2 conv. layers ((channels, kernel_size stride) [[20, 4, 2), [50, 4, 2]]) and 1 fully connected layer of size 500 that predicts
20

---

Published as a conference paper at ICLR 2023
BB
Identity
rk
7 3 1
3
train loss
w + A de
rk
dy
df dw
dt dw
dy
yy
100
Identity
BB
epochs
Visualization of the different ranking gradients.
(b) Training for TSP(5) for gradient noise level 0.5.
Figure 8: (a) Left: the scores w, with rel(y") in green and their shifted counterparts below. The grey arrows correspond the Identity-gres -rriiiittt Right: BB performs another ranking μд with the shifted which yields a denser gradient. (b) To check for the robustness of the methods, we apply gradient noise during the entire training time (100 epochs). The shaded grey region highlights the epochs for which margin-inducing noise (g) was applied to the inputs to prevent cost collapse. The dots on the training curve represent early stopping epochs.
Table 5: Recall R@1 (1) for CUB-200-2011 with various projections and margin types.
Noise-induced margin
Informed margin
Identity
Identity
BB
13.9 +
62.6 + 0.4
13.9 0.9
62.6 + U.4
0.001
14.5
62.6 : 0.3
16.2 1.7
63.0
0.01
0.8
62.6 + 0.5
25.3 1.2
63.0
0.1
13.4 1.0
62.0 0.2
28.9
6
0
44.6
62.9 0.5
44.6 0.8
62.9 +: 0.5
0.001
44.0 1.0
62.9 + 0.2
4
62.9 + 0.5
Pmmm
0.01
4.4
62.9 0.5
45.9 1.0
62.7 0.2
0.1
44.9 0.4
61.9 0.6
49.9 0.5
62.1 0.3
59.0
60.8 0.3
59.0
60.8 0.3
0.001
59.3 0.5
62.6
58.7+ 0.5
62.7
P norm
0.01
58.9+0.33 0.5
6.4
58.3 0.6
62.3
0.1
59.3 0.6
60.1
0.5
50.4 0.4
0.6
0.6
62.4 0.6
0.001
62.7 0.6
0.1
63.0 1
Pon
0.01
0.5
63.0 0.5
0.4
63.2 +
60.5 + 0.4
62.1 0.2
50.3 1.1
61.3 + 0.4
vector of dimension 3k containing the A: 3-dimensional representations of the respective countries' capital cities. These representations are projected onto the unit sphere and the matrix of pairwise distances is fed the TSP solver. The network was trained using Adam optimizer with a learning rate 10-4 for 100 epochs and a batch size of 50. For BB, the hyper-paramett parameter À was set to 20.
As described in Sec. 3.6 adding noise the cost vector can avoid cost collapse and inducing procedure. We apply noise, & 0.1, 0.2, 0.5, for the first 50 epochs (of 100 in total) to prevent cost collapse. For this dataset, it was observed that finetuning the weights after applying noise helped improve the accuracy. Margin is only important initially as it allows not getting stuck in a local optimum around zero cost. Once avoided, margin does not play a useful role anymore because there no large distribution shifts between the train and test set. Hence. noise not applied for the entirety of the training phase. We verified the benefits adding noise experimentally in Tab.
margin-
A difference between BB and Identity can be observed when applying gradient noise, simulating larger architectures where the combinatorial layer is followed by further learnable layers. In Fig. 8b, present the training loss curves in this case. As noise is not added anymore ie. after epoch 50. However, Identity converges as the training progresses.
BB starts to diverge right after the
21

---

Published as a conference paper at ICLR 2023
==
5 = 0.1
{ = 0.2
- 0.5
TSP(5)
91.09
0.07
99.67 + 0.10
99.67 + 0.10
99.68 + 0.09
TSP(10)
85.31 + 0.15
99.72
0.04
99.76 + 0.07
99.76 + 0.04
TSP(20)
88.45 = 0.88
99.78 + 0.04
94.50 + 10.53
99.80 + 0.06
Table 6: Adding noise during the initial 50 epochs of training prevents cost collapse and therefore improves the test accuracy.
B.5 WARCRAFT SHORTEST PATH
We additionally present an evaluation of the War- craft Shortest Path experiment from Vlastelica al. (2020). Here the aim to predict the short- est path between the top-left and bottom-right vertex in a x Warcraft terrain map. The path is represented by an indicator matrix of vertices that appear along the path.
Table 7: Cost ratio (suggested vs. true path costs) for Warcraft Shortest Path 32 32. BB and Identity work similarly well. Normalization Poomn noise does not affect the performance significantly.
Cost ratio x x000_
OH
BB
Identity
The non-negative vertex costs of the k l grid are computed by a modified Resnet18 (He et al., 2016) architecture using softplus the output. The network receives supervision in form of L1 loss between predicted and target paths. We consider only the hardest case from the dataset with map sizes 32 x 32.
100.9 = 0.1
101.0 + 0.1
P Pnom
0
100.9 0.1
101.2 + 0.1
0.2
101.1 = 0.1
101.0 = 0.1
Due to the non-uniqueness of solutions, we the ratio between true and predicted path costs an evaluation metric: "v("))(()))))))))) (w",
"ww,""" y²),, with wn being the ground truth cost vector. Note that lower scores are better and 1.0 the perfect score. Table shows that Identity performs comparatively to BB.
We follow the same experimental design as Vlastelica al. (2020) and do the same modification to the ResNet18 8 architecture, except that we use softplus to make the network output positive. The model is trained with Adam for 50 epochs with learning rate 5 10 The learning rate is divided by 10 after 30 epochs. For the BB method we use À = 20. The noise, when used, is applied for the whole duration of training.
B.6 RUNTIMES
We report the runtimes of our method and BB for all experiments in Table 8. Without surprise, we see the largest improvement of Identity over BB in terms of runtime when the underlying combinatorial problem is difficult. Finding the top-k indices the ranking of vector is extremely simple, and therefore this procedure is typically not the computational bottleneck of the architecture. Consequently, we do not see any difference between the methods in terms of runtime for the discrete sampling experiments (DVAE and L2X) and the retrieval experiment. In the matching experiment, the matching procedure makes up for relevant portion of training, which also observed in the runtime, as Identity requires less training time for the same number of training iterations. The runtime of the quadratic assignment solver scales with the number of keypoints in the image pairs, which between between 9 and 30 in experiments, and therefore the difference in runtime between the methods will also increase for instances with more keypoints to match. Finally, the TSP problem poses the hardest of the considered combinatorial problems, which is reflected in the almost halved runtime of the architecture employing Identity compared to using BB
Overall, conclude that choosing between Identity and BB depends both on the difficulty of the combinatorial problem, and the performance of the two methods, which is affected by the quality of the incoming gradient discussed in 3.3.
22

---

Published as a conference paper at ICLR 2023
Sampling
Graph Matching
Retrieval
TSP
1.2X
Pascal VOC
SPair-71k
CUB-220-2011
== 10
Identity BB
38.0 + 0.6
97.0 + 2.5
93.5 + 1.9
99.7 + 4.0
53.1 + 2.5
train
37.6 + 1.5
104.4 + 2.2
101.7 2.0
99.5 + 3.4
84.6 + 0.7
eval
Identity BB
0.3 0
7.5 0.3
7.0 + 0.2
87.1 + 3.8
0.1 =
0.3 = 0
7.5 0.3
7.3 + 0.2
88.0 + 5.5
0.1 0
Table 8: Runtimes (in minutes) for performed exeperiments.
C
METHOD
C.I RELATION TO NON-LINEAR IMPLICIT DIFFERENTIATION
In the case of linear program (1), the optimal solution always located at one of the corners of the conex hull of the possible solutions, where the Jacobian of the optimal solution with respect to the ocost vector zero. Note, that this is in contrast to the case of optimization problems with non-linear objectives over convex regions, such OptNet (Amos and Kolter, 2017) and Cvxpy (Agrawal et al., 2019a). Intuitively, here the non-linearity often leads to solutions that are not located at such problematic corner points, and therefore the optimal solution usually has continuously differentiable dependence on the objective parameters with non-zero Jacobian. This Jacobian can be calculated by solving the KKT system the backward pass, and therefore informative gradient replacement is required, given a sufficiently strong regularization through the non-linearity.
C.2 PROJECTION AS SOLVER RELAXATION
As described in Sec. 3.5, we can also view the Identity method in terms of relaxations of the combinatorial solver. From this perspective, the approach is to use the unmodified discrete solver on the forward pass but differentiate through a continuous relaxation on the backward pass, see this connection, we modify the solver by a) relaxing the polytope Y to another smooth set Y containing Y and b) adding a quadratic regularizer in case Y is unbounded, i.e.
- =
y (w) arg min(w, v)
By (w, e)
arg min(w, v) VEF
(27)
yEY
The loosest possible relaxation is to set Y R This gives
Tiz (w, arg min (40, v) 11ll yER"
(28)
as the closed form solution of the relaxed problem, and differentiating through it corresponds to the re-scaled vanilla Identity method. We can improve upon this by making the relaxation tighter. As an example, we restrict the solution space a hyperplane H {y E R RT y) b} for some unit vector a E IR" and scalar E IR, and setting Y H leads to the closed-form solution
P UH (w. e) = arg min v) + |1ul12 = - (w, a)a) + b - Planee (w a) + b.
1
(29)
The Jacobian of this expression matches that of Identity with Pplaee up to scale. practice, we also often encounter the case in which Y is a subset of sphere S = + r for some E R" > 0. This is the case all of our experiments, as both the binary hypercube and the permutahedron are subsets of certain spheres. Specifically, that is
n 1, C
vn 2
==
r
(30)
2
for the binary hypercube, and
n +
n(n²
1)
1,
(31)
2
12
23

---

Published as a conference paper at ICLR 2023
for the permutahedron. Setting Y S gives the closed form solution
Us (w,, c = 0) = arg (w y) = c r
W
= c - norm (w).
(32)
||
yEs
The Jacobian of this relaxed solution proportional to that of Identity with projection P In our experiments, we also encounter the case in which the solutions located on the intersection of hyperplane H and sphere S. We can therefore tighten the relaxation further by Y S H.
Assuming without loss of generality that the sphere center is located on the hyperplane, we get the closed form solution
(ws a.a
Ysnu (w, c 0) arg min (w. , y) =c-r
=c r perm (P plane (w (W))).
(33)
||w - (w, a}all
yES
In the case of y being the set of k-hot vectors or the permutahedron, we have a 1/ Vn. which amounts
1 ( 0) = r (w]aa (nn -c-
(34)
The Jacobian of this expression matches that of Identity using Pau projection, which we derived originally by considering solver invariants in Sec. 3.4. This further strengthens the intuitive connection between projections in cost-space and relaxations in solution-space.
This view of Identity is also related to existing work structured prediction with projection oracles (Blondel, 2019), which uses (potentially non-differentiable) projections onto convex super-sets on both the forward- and backwards pass.
C.3 PROOF OF THEOREM 1
For an initial cost w and a step size a > O, we set
Wo and Wk+1 wT adwa for k N,
(35)
in which Aww denotes the Identity update at the solution point y(wk). i.e.
Al de dy (v(wr)).
(36)
We shall simply write dl/dy when no confusion is likely happen. Recall that the set of better solutions is defined as
(²) {v' E E f(v') < (w)) where f is the linearization of the loss l at the point defined by dl
(37)
Sw'') = ((v) ( y: dy
(38)
In principle, ties in the solver may occur and hence the mapping w + y(w) is not well-defined for all cost unless specify, how the ties resolved. Typically, this is not issue in most of the considerations. However, in our exposition, we need to avoid certain rare discrepancies. Therefore, we assume that the solver will always favour the solution from the previous iteration if possible, i.c. from (y(w)), wa) = 1), it follows that y(w+) = y(wk-1).
Theorem 2. Assume that (wx) ) is the sequence in (35) for some initial cost and step size a > Then the following holds:
(i) Either Y (y(w)) is non-empty and there is some 0'aax > 0 such that for every a < Gmax there is N such that y(w,) E Y (y(w)) and y(wx) v(w) for all k < n,
(ii) Y (u(w)) is empty and for every or it is v(wx) v(w) for all k E N.
We prove this statement in multiple parts.
Proposition Let and (wx) be in (35). If (y(w)) is non-empty, then there exists N such that y(w,) # y(w).
24

---

Published as a conference paper at ICLR 2023
Proof. We proceed by contradiction. Assume that Y (y(w)) is non-empty and y(wx) y(w) for all E N.
Take any y² Y (v(w)), By definition of Y (y(w)), we have that de O.
{ {=(v y(w), dy
(39)
As y(wx) y(w) for all N, is
Wi kaAw w + ka de
(40)
dy
and therefore
(w" w(w), = (w" - -ww)), w) ka(lv -w(w,, y(w),
dy dy)
de (y" y(w), + kag.
(41)
Since & < 0, the latter term tends minus infinity. Consequently, there exists some E N for which (y' w.p) < (y(w),
(42)
contradicting the fact that ylw) is the minimizer for wn.
Let us now make a simple auxiliary observation about arg min solvers. The mapping
- y(w) arg (is yEY
(43)
a piecewise constant function and hence induces a partitioning of its domain W into non- overlapping sets on which the solver is constant. Let us denote the pieces by
Wy {w W v(w) = y} for E Y.
(44)
We claim that W, is a convex cone. Indeed, if w Wy clearly Aw E Wy for any X > 0. Next, if w1 Wy, and À 10, then v(Awi) y and y((1 - A)w2) = y and hence y also minimizer for Awa + (1- A)w2.
Proposition 2. Assume that (wx) the sequence in (35) for some initial cost and step size Then either for every a it is y(wx) = y(w) for all k E N, or there is some amax > 0 such that for every Qmax there is N such that y(wn) y(w) for all k < n and yuwn) # y(w).
Proof. Let define w: [0, oc) + W and y: [0, 00) + Y
(45) respectively. As y is a composition of an affine function w and piecewise constant solver, is itself piecewise constant function. Therefore, y induces partitioning of its domain co) into disjoint sets on which 7 is constant. In fact, these sets are intervals, say /,,..., Im as intersections of the line segment (w(a) a > 0} and convex cones Wy. Consequently, S |Y|.
w(a) = w - aww and 7(a)= = y (wo(a) for E W,
Now, If m 1, then 41 [0, oc) and y(wy) is constant y(w) for all k E N whatever > 0 is. In the rest of the proof, we assume that m 2 2. Assume that the intervals Ii....,,,, Im are labeled along increasing a, i.e. if a1 E 7; and
1 then 01 < 022 if and only if i < j.
We define the upper bound on the step size to amax = [Zz]. Assume that a < amax and (w)) is given. Let n = min & E N. : w(ak) E I2), i.e. the first index when the sequence y(wk) switches. and y(w..) = 7(am) & y(w).
Clearly y(wx)) = <(ak) = v(w) for lo = .n.....--
Proposition 3. Let a > and (w)) be as in (35). Assume that y(wx) v(w) for all k < n and y(w,) # y(w). Also assume that from (y(ww), wa) (u(wx-1).wg it follows that y(wk) = y(Wx-11. Then
[y(wm)) < (x(w)),
(46)
where f is the linerarized loss y(w).
25

---

Published as a conference paper at ICLR 2023
Proof. As y((w)) (w) for all &s < it
de
= w na = + na
(47)
dy
Therefore, as y(wn) ) is the minimizer for the cost we, we have
s (y(w) - y(wn), - (w/(w) - y(wn); w) + na na(p(w) - y(wn); |y
(48)
Now, since y(w) the minimizer for w, is (v(w) - v(wn), S 0 and therefore
de
0 S (((w) - y(wn), dy
(49)
Consequently,
I (v(wn)) = ((((W)) + (v(wn) y(w), de
Ty S {(v(w)) [(((W).
(50)
Equality is attained only if
(u(wn) y(wn-1)) wm) 0.
(51)
This together with y(w.)) * y(w) y(wn-1) violates the assumption that the solver ties are broken in favour of the previously attained solution, therefore the inequality in (50) is strict.
Proof of Theorem 2. Assume Y (v(()) is non-empty. It follows from Proposition that there exists m such that y(wm) + y(w). It follows from Proposition that there some Omax such that for every a < Omax there is n E N such that y(wx) = y(w) for all & < n and y(w,) * y(w). From Proposition it also follows that f (1(w)) < ()((w)) Combining these results we have (w,)) Y (y(w)) by definition. This proves the first part of the theorem.
We prove the second part of the theorem by contradiction. Assume that Y (y((w) is empty and there exists some such that y(wx) y(w) for all h < n E N and y(wn) o y(w). From Proposition 3 we know that f ()(w,)) < (v(W)) and therefore y(wn) E Y (y(w). This is in contradiction to Y (y(==)) being empty.
D ADDITIONAL ILLUSTRATIONS
In addition to the illustrations for the 'simple' case in Fig. 2, provide additional illustrations for the more challenging case in Fig. 9, in which the incoming gradient does not point towards an attainable solution. The illustrations compare the resulting update directions for Identity without projection, Identity with Pau projection, and Blackbox Backpropagation.
26

---

Published as a conference paper at ICLR 2023
updated
dt dy (ww)
(a) update without projection: large part of the resulting update does not affect the optimal solution. Note that the illustration shows a two vo-dimensional sphere embedded in a third dimension, with the incoming gradient pointing into the third dimension.
dt dy (w)
updated
(w)
P(w)
('(w) dy
(b) Id update with projection Pas: The invariant part the update is removed by diffcrentiating through the projection. It has the effect of first projecting onto the hyperplane, and then projecting onto the tangent of the spherc.
yx
dt dy (w)
updatedd
(W))
(c) BB update: The invariant part of the update also removed, at the cost of an additional call to the solver. Shown is an update resulting from an appropriate choice of X, which is in general not available priori.
Figure 9: Intuitive illustration of the Identity (Id) gradient and Blackbox Backpropagation (BB) gradient when -dl/ds does not point directly to target. Illustrated is the case of differentiating an argmax problem. The cost and solution spaces are overlayed; the cost space partitions resulting in the same solution drawn in blue. Note that the direct updates the cost vector only of illustrative nature, as the final updates are typically applied to the weights of the backbone.
27


Reviews:
[{"review_id": "jBcgHg_s9R", "reviewer": "Reviewer_MfHU", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a surrogate gradient for differentiating through combinatorial solvers with linear objective function, for which gradient is not informative (either null or does not exist). ", "summary_of_the_review": "The paper presents a novel way to perform updates over combinatorial solvers. The approach is simpler compared to prior approaches, yet in some cases empirically competitive. While well-argued and well-written, the paper could benefit from a more in-depth theoretical analysis, and from more information in the experimental section. ", "strength_and_weaknesses": "Strengths:\n- simplicity and computational efficiency of the \"negative identity\" approach compared to e.g. Vlastelica's approach, which requires two calls to the solver per gradient iteration\n- consideration for solver invariants is a plus\n- empirical evaluation on a wide range of problems is a plus\n\nWeaknesses:\n- intuition and theory in 3.2 and 3.3 shows that the update leads to a lower-loss solution. It would be helpful to have some estimate/indication of how does the update compare with the best possible update (of some limited magnitude)\n- empirical evaluation is rather limited in terms of competing methods. It would be interesting to see how the proposed method compares with e.g. cvxpylayers and similar approaches on combinatorial problems equivalent to convex optimization problems, where these methods can be applied \n- it would be helpful to have some complexity/run-time information provided for all the methods/runs in Section 4, to allow for judging the tradeoff between accuracy and speed.\n- the relative comparisons show somewhat mixed results, e.g. no improvement over Softsub and small over I-MLE in Table 1, similar results to BB in Table 2, lower performance than BB in Table 3, similar performance but higher robustness than BB in Fig. 4. \n- minor: graphical illustration for the more challenging case (Section 3.3) would increase the accessibility of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "hk8xz6KEm-t", "reviewer": "Reviewer_NUvG", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper considers the problem of inserting combinatorial solvers into neural network architectures. Since combinatorial solvers have discrete outputs the gradient is zero or non-existent, meaning that an alternative \"gradient\" must be used on the backwards pass in order to provide directional information to update the model parameters. \n\nThis paper proposes a method that uses the identity function for the gradient, with an additional projection matrix applied in cases where these is a known invariance in the solution space. The projection is motivated by arguing that irrelevant gradient components interfere with adaptive methods such as Adam during training. This point is also empirically checked in several experiments. Other experiments show that the overall method is competitive and sometime better than representative methods in the related literature, e.g., the work of Vlastelica et al.", "summary_of_the_review": "\n\n\nMy main concern for rebuttal is this: can the authors please provide further clarification on the differences between their identity method and the Straight-Through estimator? I appreciate the efforts given in Appendix A to explain the differences, but unfortunately I still do not see what the difference is? For instance, Figure 5, which is used to explain the differences instantiates the proposed method for differentiation through a sampler. But the only non-differentiable part is the argmax, which uses the identity. Isn't this exactly what the straight through estimator would use too? I am very keen not to mis-accuse this work of being \"the same\" as the straight through estimator, but until I understand the difference I cannot advocate acceptance. \n\nThis paper has some interesting ideas, namely the projection method, but the emphasis of the paper is on the identity update, and secondarily on the projection. Consequently there is too little time spent discussing and studying the consequences of the projection idea. I really think this manuscript will make a nice paper eventually, but my suggestion to the authors would be to focus on the projection idea and the connection to adaptive methods. If you can show in more detail that this connection exists and is important to performance then this could be really helpful to practitioners. \n\nAlthough I see a lot of promise in this work, in it's current state I cannot advocate for acceptance. I will pay very close attention to your rebuttal to make sure that I haven't made some terrible misunderstanding about the identity idea vs the straight through estimator. ", "strength_and_weaknesses": "**Strengths**\n\n- Paper is nicely written, an fairly clear\n- A number of experimental setups are considered, I am happy to see a good variety of problems considered. \n- The method is computationally cheap, and general purpose\n- The argument that the identity is guaranteed not to find worse solutions is solid (e.g., Theorem 1), although of course the \"there exists. gradient step such that the loss is better\" doesn't say anything about how long before that useful step happens.\n\n**Weaknesses**\n- the identity method does appear to be very similar to the straight through estimator. Efforts are made in the paper to explain the difference but I currently fail to understand the differences. \n- the projection idea is discussed in detail, and is motivated via the connection to adaptive methods. But no experiments are provided empirically validating this connection.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QZ9F8nY1H9", "reviewer": "Reviewer_cnD6", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This paper proposed a principled method to approximate the gradient of a combinatorial solver, which could be readily integrated into an end-to-end learning pipeline. To achieve this, the authors studied the behavior of linear combinatorial solvers and proposed \"Identity\" as the surrogate gradient over the coefficients, with further added perturbation to avoid the cost collapse. Experiments were conducted on various combinatorial tasks, showing its superior performance over existing gradient estimators. The idea of utilizing identity as a gradient is interesting and novel, with some theoretical guarantee.", "summary_of_the_review": "In general, I vote an acceptance for this paper, taking into account its readability, novelty, theoretical soundness and empirical performance.", "strength_and_weaknesses": "In general, I like reading this paper since it was well-written and very easy to follow. All the necessary details were presented and the idea was insightful. To me, the strength is as follows:\n1. The idea of utilizing identity as a gradient estimator for linear combinatorial solvers is very interesting and neat. This is without any extra calling of the solvers and can be easily extended to a large variety of downstream tasks.\n2. Although the technical part of the proof of Theorem 1 is not so complicated, I think Theorem 1 can support the claims about the applicability suggested by the authors.\n3. The authors provided an initial but insightful discussion on utilizing projection as solver relaxation.\n\nDespite the aforementioned strength, this paper can be further improved:\n1. The discussion of projection as solver relaxation seems not so thorough and solid. More detailed and theoretically guaranteed discussion can greatly strenghened the contribution of this paper.\n2. There have been several previous works approximating gradient of linear combinatorial solvers. I suggest the authors to give some discussion on the non-linear cases (say, quadratic).\n3. Aside from using bar graph in Table 2 and 3, it could be more readable if numbers could be provided.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7_tp9KVgWI5", "reviewer": "Reviewer_bT3d", "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": "This paper proposes a straightforward hyper-parameter-free approach to embed discrete solvers as differentiable layers into neural networks. In detail, during the backward pass, the Jacobian $\\frac{\\partial y(\\omega)}{\\partial \\omega}$ is simply treated as a negative identity matrix and a theoretical justification is provided. As the identity method alone can result in unstable learning behavior, two transformations (i.e. mean and norm) are applied to the cost vector $\\omega$ to exploit invariants. Noise is added to the cost vector to improve the robustness. Experiments on discrete samplers, deep graph matching, and image retrieval show the proposed method is competitive against previous more complex methods.", "summary_of_the_review": "I would to reconsider my rating based upon authors' feedback and clarification. Currently it is hard for me to fully understand the paper.", "strength_and_weaknesses": "## Pros\n- The motivation of this work is clear and the proposed method seems simple and efficitive. It is suprising that the identity method, which is similar to Straight-through estimator for samples drawn, can be applied to optimization operation.\n- Extensive experimental results on discrete samplers, deep graph matching, image retrrival, etc. show the effectiveness of the proposed method.\n\n## Cons\n- The paper is not easy to read and some place is hard to decipher. Some derivations are not very clear due to omissions or inappropriate notation usage：\n1. I think  that Equation (2) should be something like $\\frac{d}{d\\omega}\\langle\\omega, y^* - y(\\omega^0)\\rangle$ where $y(\\omega^0)$ is a fixed vector rather than a function of $\\omega$.\n2. In Equation (6), the linearization $f(y)$ can be viewed as the Taylor expansion of $l(y)$ around $y(\\omega)$, which means $f(y)$ can only approximate $l(y)$ in the small region around $y(\\omega)$. However, for the more wide region $y \\in Y$, a lower linearized loss doesn't mean a lower true loss. For instance, assume $y \\in \\mathbb R^2$ and the feasible region is the polygon with extreme points $\\{(0, -1), (0,10),(-10,0), (10,0)\\}$, and the nonlinear loss $l(y) = ||y||^2$. If $y(\\omega) = (0, -1)$, by the defination of Equation (6) $Y^*(y(\\omega)) = \\{(0,10),(-10,0), (10,0)\\}$. All points in this set have a lower linearized loss but higher true loss than $y(\\omega)$. \n3. In the Linear Transforms part of Section 3.4, $\\Delta^I\\omega$ is decomposed into $\\Delta^I\\omega = \\Delta^I\\omega_1 + \\Delta^I\\omega_2$, where $\\Delta^I\\omega_1 = P\\Delta^I\\omega, \\Delta^I\\omega_2 = \\Delta^I\\omega - \\Delta^I\\omega_1$. It is clear if $P$ is a projection matrix (e.g. the $P_{mean}$ in Equation (13)), then $\\Delta^I\\omega_2 \\in \\text{ker } P$. But for general $P$, which is not a projection matrix, whether $\\Delta^I\\omega_2 \\in \\text{ker } P$ still holds? This may affect the derivation of Nonlinear Transforms.\n- Some additional ablation studies about invariant mappings should be conducted: In Table 1 and Table 3, $P_{norm}$ cooperate with $P_{mean}$ to improve the performance. In Table 2 and Table 4, the performance of Identity with $P_{norm}$ alone is worse than that without projection. Therefore, the ablation study is needed to find out whether $P_{norm}$ is useful. For example, in Table 1, besides $Id. (P_{std})$ and $Id. (\\text{no } P)$, $Id. (P_{mean})$ and  $Id. (P_{norm})$ should also be evaluated to find out whether these two mappings alone help to improve model performance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster