Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an unsupervised method for cardinality-constrained combinatorial problems. By building on previous work on Soft TopK through optimal transport (OT), the authors provide an enhanced Soft TopK framework that includes Gumbel noise in the OT problem. This provides a more complete theoretical bound on the original OT problem but also strong experimental performance on two combinatorial optimization problems.
main_review: ## Strengths:
- Strong experimental results with baselines that include other neural approaches as well as solvers and classical algorithms.
- The paper builds on recent work from the literature.
- The approach provides improved theoretical results for soft TopK through the use Gumbel noise.
- The motivation and the explanation of the theoretical results are clear and well done.

## Comments and weaknesses:
- Minor corrections regarding related work.
You claim "Besides, Paulus et al.
(2020) develop a general framework for generating combinatorial distributions via Gumbel distribution." The work in Paulus et al. can use different
kinds of noise in their optimization program, not just Gumbel.
Regarding the work by Karalias and Loukas, you claim "However, they do not consider the cardinality constraint (at least not
explicitly)." While the paper indeed does not explicitly address cardinality constraints in the examples/experiments, it is fairly straightforward to describe such constraints with their probabilistic penalty approach.

- Just below Equation 13, the optimal solution is denoted with a tilde. Is an asterisk missing there or am I misunderstanding something?
The notation is somewhat confusing at that point. The expectation on the lemma right below has T with both tilde and an asterisk but the 
sentence claims that the optimal is just tilde(T) (well, boldface T to be precise).
More generally, the text contains various typos that need to be fixed, for example:
page 5: "our aim becomes to proof the upper bound"
page 7: "learning two representative problems pf cardinality".


- Regarding the motivation of the paper, the authors explain ties between $x_k$ and $x_{k+1}$ will break the original bound, which is a concern
because those are outputs of a neural network so it is a plausible scenario. Is this really an issue in practice? That is, does the Gumbel noise
end up breaking ties that appear in neural network outputs in your experiments? Or is this mostly a theoretical concern? Furthermore, would you attribute the significant performance gain in experiments compared to Soft TopK to the tie-breaking of the Gumbel noise? Or is it that noise+sampling
provides an effective randomization technique that enables better performance? 

- Can you explain a bit the difference between soft TopK with sampling and without? Does sampling work as in the Gumbel-Sinkhorn case? I would expect 
sampling to improve soft TopK as well, but it doesn't appear to be the case.

- The scope of the approach is somewhat limited as it only addresses cardinality constraints. It also seems to rely on the differentiability of the objective function.
Furthermore, conceptually this is a somewhat incremental improvement over the existing soft TopK algorithm. Therefore I am concerned that the impact of this work might be limited.

- How much does the number of samples affect performance? An ablation study on that would have been nice.

summary_of_the_review: This is overall a solid paper that is theoretically motivated with strong experimental results. However, the scope of the project is somewhat limited and the proposed method is incremental in nature. Furthermore, the writing could be improved and I have some doubts/questions regarding certain experimental details. My starting grade is 6. After the authors' response, I will reconsider my evaluation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to add Gumbel noise to the scores to which differentiable top-k via regularized optimal transport is applied.
This improves theoretical guarantees for the case where the $k$th and the $k+1$th elements are equal.
main_review: The paper proposes a new application for differentiable top-k as well as a variation of a differentiable top-k operator that improves theoretical guarantees, which they also prove. 

There are also other soft top-k operators. 
Very influential for the work by Xie et al. is the optimal transport based differentiable sorting and ranking (https://arxiv.org/abs/1905.11885).
There are also differentiable sorting networks, which provide differentiable sorting and ranking (https://arxiv.org/abs/2105.04019).
Both of these works include differentiable top-k operators and include experiments demonstrating their utility. 
I suggest adding and discussing these references and elaborating the choice of using the formulation of Xie et al. 
(At the moment, it seems like the paper implies that the choice was because this would be "the" or the only soft top-k operator, which is not the case.)

In the toy example in Figure 1, there is not a unique solution of the top-k operation.
Therefore: why is it beneficial that one specific solution is selected over a 50% / 50% mixture of both 0.6 entries?
The algorithm 2 would result in a 50% / 50% mixture for the two 0.6 entries. 
Differentiable sorting networks for top-k achieve a 50% / 50% mixture without sampling.
This should be discussed.

In algorithm 3, there is a $T$ in line 7. The $ \mathbf{\tilde T}_i$s are not used, so maybe there is a typo? 

The citation for "The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables" by Maddison et al. is missing, which was published simultaneously to Jang et al. Please add it respectively.

Is the difference between the "SOFT-TopK w/ sampling" method and the "GS-TopK" method that sampling for "SOFT-TopK w/ sampling" is done only during inference, while for "GS-TopK" sampling is done during both inference and training?

What are the differences to the Gumbel-Sinkhorn method by Mena et al.? From "However, these existing methods do not study the application in combinatorial optimization learning, and the gap between the MAP inference and the result after Gumbel re-parameterization is not well characterized in (Mena et al., 2018).", I understand that they are fairly similar, and the main difference is application and theoretical guarantees.

I did not check the validity of the theoretical results.

I appreciate the application and experiments. However, I wonder how the hyper-parameters were selected. 
From the current draft, it seems like an "empirical selection" was done for your proposed method, but there is not a clear procedure to have a meaningful comparison between all methods.
Optimizing only your hyperparameters would lead to a significant bias in the results. 
There is no grid specified over which you perform grid search to give each method a fair chance.
At a time cost of seconds for each method, it should be very feasible to do even a quite extensive grid search. 


### TYPOs:
Overall, the grammar should be reworked, e.g., using a tool like LanguageTool or Grammarly, would point out various typos that I did not cover below.

p.2: and pipeline is differentiable -> and the / our pipeline is differentiable

p.2: taxonomy by (Peng et al., 2021) -> taxonomy by Peng et al. (2021)    (This TYPO is also at other locations, e.g., Inspired by
(Jang et al., 2017),)

p.3: parametreization. 

gradient ascend -> gradient ascent

p.7 problems pf cardinality -> problems of cardinality

p.9 Directly applying Gumbel sampling to SOFT-TopK seems either an effective improvement, and satisfying
results are achieved when exploiting the Gumbel re-parameterization trick and enabling gradient-
based optimization over the combinatorial objective score.  (This sentence is grammatically incorrect, which makes it not understandable.)

at various occasions, you write SOTF-TopK instead of SOFT-TopK
summary_of_the_review: Overall, I see that the paper has theoretical strengths and presents an interesting application for the method.
However, the methodological contribution is small.
The experimental evaluation is or seems to be flawed, as it is questionable whether the comparison is fair. 
Grammatically, the paper should be reworked. (which does not impact my score, as I expect this to be fixed in the final paper.)

For these reasons, I suggest rejecting this work in its current form. 

Improving and extending the comparison to related work (e.g., Mena et al.) and making the comparison explicit would improve the paper. It is important to explicitly state the differences if there are any. 
The empirical evaluation should be more rigorous.

---

I appreciate the response and revision; however, I still have concerns as per my last response.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper advances one-shot solution generation methods for cardinality constrained optimization problems. The recently developed SOFT-TopK algorithm suffers from an optimality bound discontinuity. This paper introduces a Gumbel randomization trick to the algorithm, prove that this removes the discontinuity in the bound, and implement their algorithm in two combinatorial problems, where they demonstrating achieving better solutions in less time than baselines.

main_review: Overall, I enjoyed the paper. It introduces a simple trick, provides nice theory to justify the technique, and contains several experiments. I have a few comments.


- It would be nice to include a bit more math up front in Sections 1/2/3 about the combinatorial optimization problem being solved. Specifically in Section 3.1, $\mathbf{s}$ is not introduced, making it confusing to jump into the problem.
- I am confused that the proposed methods beat Gurobi/SCIP. I assume this is because of the runtime limit on the solver (100 sec). If so, I find 100 sec arbitrary. It would be more useful to let the solvers run to completion and report those results in addition to the current—I would describe that setting as “accurate” Gurobi/SCIP rather than the current.
- As a result, it is also difficult to say that the current approach “outperforms state-of-the-art Gurobi” without specifying that this is under runtime constraints. Outperforming the solvers would make sense if the current methods can find *provably optimal* solutions faster than the solvers, or if the solvers cannot obtain solutions within their understanding of reasonable time (e.g., ~hours)
- It is hard to determine the effectiveness of the approach by comparing raw objective function value. Given a full-runtime globally optimal solution, we can then evaluate in terms of the relative suboptimality gap of each method. This would give a clearer picture of how much better the current method is over baselines.
- I am surprised that the discontinuity in the optimality gap can incur such a high sub-optimality, since it seems like a small problem. I appreciate the numerical toy example, but it is still not fully clear. Is the reason because in training $x_k$ and $x_{k+1}$ can repeatedly cycle in training, e.g., one increases over the other then the other increases in each iteration? A bit more intuition to the reasoning would be appreciated.

summary_of_the_review: I emphasize that I like the paper and my main concerns are on fair comparisons. I would be happy to increase my score if the authors include an additional Gurobi/SCIP baseline where they let the solvers run for sufficiently long to solve the problems to global optimality, and then compare against the relative optimality gap from the global solution.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This submission studies the learning-based formulation of cardinality constrained combinatorial optimization using probabilistic methods, specifically using Gumble-Sinkhorn method. By introducing Gumble noise into the existing Soft-TopK (Xie et al., 2020) formulation, the authors claimed that the bound of the difference between approximate objective function value and the ground-truth value is tightened, compared to the results in Xie et al., 2020. The authors presented Gumbel-Sinkhorn-TopK (GS-TopK) and its application in TopK combinatorial optimization problems. Experimental results for max covering and k-means clustering were presented to demonstrate the claim. 
main_review: This submission studies the learning-based formulation of cardinality constrained combinatorial optimization using probabilistic methods, specifically using Gumble-Sinkhorn method. By introducing Gumble noise into the existing Soft-TopK (Xie et al., 2020) formulation, the authors claimed that the bound of the difference between approximate objective function value and the ground-truth value is tightened, compared to the results in Xie et al., 2020. The authors presented Gumbel-Sinkhorn-TopK (GS-TopK) and its application in TopK combinatorial optimization problems. Experimental results for max covering and k-means clustering were presented to demonstrate the claim. 

Strengths: 

1. The introduction of Gumble noise addresses potential issues using deep network based optimal transport for learning-based combinatorial optimization, in particular, the diverging gap of Soft-TopK prediction and the optimal combinatorial solution, when the sorted approximate probabilities (of assignment) at the boundary are the same. 

2. Following the previous theoretical analyses in the literature, the authors provided the proofs of the derived bounds in the appendix. 

3. Both simple illustration (Figure 1) and empirical evaluations (Tables 1 and 2) for max covering and k-means clustering have validated the claim that the proposed GK-TopK improves Soft-TopK and outperforms other greedy and combinatorial optimization solutions, with respect to the achieved approximate objective function values. 

Weaknesses: 

1. It is not clear how the proposed formulation may change the derived combinatorial solutions besides the tightened gap for objective function values. This is related to the computation of objective function values in Algorithms 2 and 3 (in appendix), which basically took the best derived objective function values among the sampled transport maps for the GK-TopK formulation. Are the reported objective function values in Tables 1 and 2 based on these values? To access how this changes the solution quality, should the authors also provide the actual objective values with the derived combinatorial solutions? For now, it is difficult to tell whether the proposed method will have meaningful improvement in derived solution in practice. 

2. It is not clear to me how significant is this proposed improvement over Soft-TopK. Based on the presentation, in particular, Theorem 1 and Remarks on page 6, by introducing Gumble noise, the derived bounds now have two terms. It may address the diverging gap issue when the sorted probabilities at the boundary are the same ($x_K = x_{K+1}$). But why when GS-TopK will always have tighter bounds than Soft-TopK even when $x_K \neq x_{K+1}$? Why adding Gumble noise to the original optimal transport formulation of Soft-TopK can always improve the bounds? In Figure 1, I assume that the actual optimal objective value is 2.4 while Soft-TopK has the gap at 2.0. What is the actual objective value for the derived solution by Soft-TopK? What about GS-TopK? Also, it seems the choice of $\tau$ does not affect the gap by Soft-TopK in this simple illustrative example but it does change GS-TopK gaps. But $\tau$ appears in the derived bounds for both formulations. Why? 

3. For real applications, will different $\tau$ and $\sigma$ change the performances significantly? 

4. Mathematical notations and the proofs have numerous issues. Here are a few examples: 1) In equation (6), $x_k$ and $x_{k+1}$ have not been defined yet. They were explained until the beginning of page 5. 2) Below equation (13) and the text after that, should "the optimal solution to Eq. (12)" $\tilde{T}$ be $\tilde{T}*$ instead? 3) In equations (17) and (18), is $\mathbf{x}_i$ a vector? Please make sure about the meaning of bold and regular fonts in these equations. Also, regular font $x$'s have been used for sorted probabilities. Different notations may need to be used to avoid confusion here. 4) In Appendix A.1 above equation (30), "By Lemma 1..." but this part is to prove Lemma 1. Do the authors mean by "Lemma 3" instead? Even that is the case, there appear to lack some steps to connect Lemma 3 with equation (30). 5) On page 19 above "Condition 1", "... except for the following condition: $x_i = x_k, x_i= x_k$." There must be typos for these two same equations. 6) Figure 4 and the proof for Theorem 2, do we need to worry about the cases with $x_i \leq x_j$ for Conditions 3 and 4? 

5. There are missing information. For example, it is not clear what sample size #G was used in the experiments. It is not clear how exactly shrinking procedure was scheduled for homotopy GS-TopK as there is no detail provided in Algorithm 2. It would be also nice to discuss more why in Figure 3, the approximate formulations always have lower bounds. The lemmas, theorems or their proofs do not seems to indicate that will always happen? 

6. Presentation can be improved significantly. For example, Figure 2 appears to be a general illustration instead of being the "overview of our pipeline" for max covering as indicated on page 6. There are also numerous typos, for example, "... important **hcardinality** constrained ..." in the last line of the paper on page 9. 






summary_of_the_review: The authors presented Gumbel-Sinkhorn-TopK (GS-TopK) to improve Soft-TopK. But there are concerns on the meaningful improvement for the actual derived approximate optimal solutions. The presentation of the submission can be improved significantly.
review_title: null

Meta-review: The authors propose a random perturbation on top of a soft top-k operator that builds upon entropic regularized optimal transport (when applied to a 1D problem). The motivation of the paper is built around an approximation bound (proposed in the Xie et al '20 paper) that compares the true OT matrix from the regularized OT matrix in the case where some of the 1D entries from which one wishes to extract top-k values are very close (eg. x_{t} ~ x_{t+1}). The authors argue that this bound, with inverse dependencies in the closest element in the list, diverges.

The authors state that this possible divergence is an issue, because values to be sorted/top-ked can be very close in practice. To solve this issue, the authors introduce instead a Gumbel noise mechanism that no longer makes the bound diverge, through a fairly long theoretical analysis. The approach now requires the recomputation for several noisy inputs of the same regularized OT estimator. The authors propose then to use these soft-top-k approaches to solve a combinatorial problem using gradient descent, namely a capacity constrained problem and clustering, including some tricks on controlling both entropy regularization and Gumbel noise magnitude.

The paper has generated a long discussion among the AC and reviewers. While the paper has a few strong points that were appreciated (interest of empirical validation which seems to suggest some improvements over commercial solvers on considered setups), there remain a few issues. 

The theoretical side of the paper is bit blurry. The idea of introducing Gumbel noise on top of an already soft operator is not completely clear, since these perturbations are there to add differentiability to something (reg-OT) that was introduced itself to be differentiable. The theoretical motivation is unclear: the noise is introduced because the _upper bound_ diverges (and not the gap between the "true" OT and entropic OT, since it is always bounded). The perturbation mechanism is only motivated to improve the limitations of an upper bound, not of the original algorithm itself. What's more, it's not entirely clear why that gap should be decreased (between true and regularized OT) since it has to exist to obtain some differentiability. While the study of the gap itself was added during the discussion phase in Fig. 1"A toy example to explain Lemma 2", one would expect better foundations for this idea.

With a somewhat unclear theoretical motivation, the experiments should be very convincing. Reviewers have noted some issues related to comparing CPU/GPU times. While I am sympathetic to the problems encountered by the authors when running such comparisons, these issues should be properly reflected in their initial claims, and not appear in the rebuttal only. I also think experiments are still lacking in diversity. For instance, the k-means problem is studied in 2D (begging the natural question of whether such an improvement would remain in higher dimensions). I could not find a clear statement on the number of repeats carried out to obtain error bars. Since I don't envision either of the max-covering problem nor k-means to become the "killer app" of this paper, I would encourage the authors to consider problems that are less synthetic.
Decision: Reject