Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
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:
1. 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.
2. 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.
3. The authors provided an initial but insightful discussion on utilizing projection as solver relaxation.

Despite the aforementioned strength, this paper can be further improved:
1. 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.
2. 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).
3. Aside from using bar graph in Table 2 and 3, it could be more readable if numbers could be provided.

clarity,_quality,_novelty_and_reproducibility: The writing of the paper is good. I feel very pleased and smooth reading this paper.
Novelty of this paper is also above the average of ICLR.
The authors also provided the code for reproducing part of the experiments.
summary_of_the_review: In general, I vote an acceptance for this paper, taking into account its readability, novelty, theoretical soundness and empirical performance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: ## Pros
- 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.
- Extensive experimental results on discrete samplers, deep graph matching, image retrrival, etc. show the effectiveness of the proposed method.

## Cons
- 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：
1. 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$.
2. 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)$. 
3. 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.
- 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.
clarity,_quality,_novelty_and_reproducibility: The paper said: a curated Github repository for reproducing all other results will be published upon acceptance.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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). 
strength_and_weaknesses: Strengths:
- 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
- consideration for solver invariants is a plus
- empirical evaluation on a wide range of problems is a plus

Weaknesses:
- 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)
- 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 
- 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.
- 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. 
- minor: graphical illustration for the more challenging case (Section 3.3) would increase the accessibility of the paper.
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, and proposes a simple new way of providing an update to the cost vector of a combinatorial problem that aims at achieving lower loss. Ample information for reproducibility is provided in the appendix. 
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

This 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.
strength_and_weaknesses: **Strengths**

- Paper is nicely written, an fairly clear
- A number of experimental setups are considered, I am happy to see a good variety of problems considered. 
- The method is computationally cheap, and general purpose
- 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.

**Weaknesses**
- 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. 
- 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.
clarity,_quality,_novelty_and_reproducibility: **Contribution**

From what I can tell the main contribution is this: 1) if it is known that certain updates do not change a solution quality, then the component of the gradient update in this direction can be safely removed without hurting the loss by using $P \cdot (dl/dy)$, instead of $dl/dy$, and 2) actually it is a good thing to remove this redundant when using an adaptive optimizer like Adam since otherwise the learning rate will be adjusted downwards due to the spuriously big gradient size. 

This is an interesting point, and is intuitive yet novel so far as I am aware. But the paper doesn't focus enough attention on this detail. There re a number of experiments showing the benefits of the projection, but no attempt is made to empirically validate the connection to adaptive training - it would be great to see plots showing the gradient update sizes with and without the projection, and plots showing the learning rate size and so on and so forth. Another interesting experiment would be to run training using non-adaptive SGD and show that there is no difference between the projection and no-projection methods. This would be good evidence to suppose the stated motivation for the projection method. 

**Clarity**

- the paper is sufficiently clear so as to be quite quickly understood 

**Reproducibility**

- the authors commit to releasing code when the paper is accepted. This is adequate in my view. 
summary_of_the_review: 


My 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. 

This 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. 

Although 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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper originally got one 8 (accept, good paper), two 5s (marginally below threshold) and one 3 (reject). The major challenges include insufficient theoretical guarantee on the proposed trick, missing some related works, being possibly difficult to read, missing additional ablation studies, etc. The author rebuttals were more or less successful and two reviewers raised from 5 to 6. However, during the virtual meeting, the reviewers did not fully agree on the difference between Idendity and Strate-Through Estimator but all agreed that the applicable scope of the Idendity+Projection is a bit limited. By the overall scores and discussion with the reviewers, the AC recommended acceptance, although not a strong one.
justification_for_why_not_higher_score: The paper is surely at most a poster as it is indeed a borderline paper as all reviewers agreed. 
justification_for_why_not_lower_score: Anyway, three reviewers gave positive scores and only one was negative towards it. Moreover, the negative reviewer did not object accepting the paper.
Decision: Accept: poster