Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper provides an improved way for constructing combinatorial optimization networks for problems that involve cardinality constraints.
strength_and_weaknesses: The main strength of the paper is providing an extension to combinatorial optimization network framework that allows for bounding the constraint violation, for the case of cardinality constraints. This is achieved by incorporating SOFT top-k approach (Xie et al., NeurIPS'20) and adding a perturbation with Gumbel distribution. The paper is somewhat limited in its scope by the narrow focus on cardinality constraint - it would be stronger if it offered at least one simple example of how the approach can be extended to another constraint type.
clarity,_quality,_novelty_and_reproducibility: The paper provides a novel, though somewhat incremental, method for handling top-k in combinatorial optimization networks. Instead of just optimal transport with entropy regularization smoothing solved via Sinkhorn algorithm, as in (Xie et al., NeurIPS'20), the authors add perturbation using Gumbel distribution. The authors show that their method, CardNN-GS, has lower theoretical bound on constrain violation than CardNN-S that relies on Xie et al.'s approach. They also show that the advantage holds empirically. The method outperforms the baseline CO approach, EGN by Karalias and Loukas, and performs on par with Gurobi. The paper is written clearly, though figures 3 & 4 are very small and hard to read.
summary_of_the_review: The paper is concerned with combinatorial optimization networks, a field of growing recent interest. It focuses on a single type of constraints - cardinality constraint - and introduces an improved method for handling it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The submission studies combinatorial optimization (CO) with cardinality constraints by neural networks. Different from the methods incorporating the constraints as penalties in to the objective function, the submission incorporates the constraints into the network architecture such that these constraints are guaranteed to be satisfied. The performance of the proposed method is demonstrated in several tasks including the facility location problem, max covering problem and portfolio optimization.  
strength_and_weaknesses: Strength

1. The motivation of the submission is clear. CO is a challenging and important problem. It is a motivating question to solve CO while forcing the constraints are satisfied. 

2. The empirical performance of the proposed method is thoroughly studied in three different tasks. 

Weaknesses 

1. The notations of the submission are confusing. Many notations first appear without any definitions. For example the notations in figure 1 appear without definitions. I cannot find the definition of $i$ anywhere in the submission. The definitions of $\mu^{gt}$ and $\Sigma^{gt}$ are also missing. Then, there are notions like $[2,:]$ and $sum(softmax(...))$ which are not like math equations but codes. 

2. Many concepts in the submission appear without or with very little definition or explanation. For example, the problem encoder is a key component of the method, but first appears in the figure 1, simply described as a model to predict $\bm{s}$. However, the definition of $\bm{s}$, how it connects to the CO, and why we need to estimate a probability like this is not provided, making the submission not self-contained   

It would be great if authors can clarify these confusions. 

3. Would it be possible for authors to explain why the CO problem is equivalent to an optimal transport problem on $\bm{s}$? It seems that this is taken for granted without further explanation. 

4. Does the gradient flow to the problem encoder part? If so, in the portfolio optimization task, this means that the the gradient flows to the price prediction part. As a result, the stock prediction may learn a prediction not so good at prediction but just to make the CO objective higher. But in the portfolio optimization, the problem setup is to fix the $\mu$ and $\sigma$ to as close as possible to the ground-truth ones. 

5. For the portfolio optimization, a yearly return as 40% seems to be overly high in practice. Would it be possible for authors to provide some intuitions behind such a high number. Also, when calculating the efficient frontier, I am wondering what is the return and volatility used. What is  $\mu^{gt}$ and $\Sigma^{gt}$? I also find this application not very suitable, since it does not matter whether the cardinality constraint is absolutely satisfied or just "mostly" satisfied in portfolio optimization. 

clarity,_quality,_novelty_and_reproducibility: Clarity

The submission is hard to follow to me. First, the submission is not self-contained, with some components deferred to existing works not specified. Second, some notations are not well defined or not defined when first used.  

Novelty

The proposed methodology seems to be novel. 

Reproducibility

The experiment setup of the submission is provided in the submission. 
summary_of_the_review: The submission considers a challenging and motivational problem. The proposed solution is novel and thoroughly demonstrated on three different tasks. However, for now, there are too many confusing part for me to evaluate the correctness and contribution of the methodology.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers how to build a cardinality constraint into neural network architectures being trained to solve combinatorial optimization tasks. This work builds on the Erdos Goes Neural approach of Karalias & Loukas, which uses a loss penalization term to enforce constrains. While Karalias & Loukas do provide high probability guarantees on constraint satisfaction for the penalization approach, in practice it requires careful selection of the weighting of the penalization loss. 

This paper takes a different approach, and design a differentiable output layer based on solving a Sinkhorn problem with added Gumbel noise. Whilst still only softly enforcing the constraint, the source of the relaxation is very different from Karalias & Loukas since it is not in the loss function itself. Empirical results suggest that in practice the approach doers a pretty good job at enforcing the constraint.
strength_and_weaknesses: **Strengths**

- A good amount of technical novelty. The OT with Gumbel noise approach is interesting to me and is an attractive wya to recast the top-k selection problem. 
- the paper is well written in my opinion.
- I am satisfied with the empirical results---a number of problems are considered including facility location, finding max covers, and a portfolio optimization problem. I am not convinced that portfolio optimization really needs cardinality constraints in practice (but definitely a whole bunch of other constraints!), but as a proof of concept I am willing to accept the setup. 

**Weaknesses:**

- I am a little concerned at the limited impact of the approach. Cardinality constraints are fairly specific, and I cannot foresee too many people needing to use this method. I am, however, strongly against rejection based on impact. I just believe it important to at least raise the point. 
- The method still only softly enforces the constraint. Perhaps some more discussion explaining why hard enforcement is a difficult problem would help myself and other readers understand why we should feel satisfied with soft enforcement. 
clarity,_quality,_novelty_and_reproducibility: - The paper is well written and engaging (at least to me!!).
- The Gumbel-Sinkhorn approach to cardinality constraints makes sense, and as far as I know has not been tried before.
- Paper contains some details on the implementation, and the authors promise that "Source code and pretrained models will be made publicly available.".
summary_of_the_review: Congratulations on a nice paper, I enjoyed reading it. The differentiable k subset selection approach is novel and interesting to me. I am also very much in favor of further exploration of neural combinatorial optimization approaches, and I think this paper plays a role in deepening the literature on this subject. In all I am broadly positive in my recommendation. 


Some questions and comments:

- While I agree that the naive top-k selection will not work as a training approach, I am not sure it is actually because of non-differentiability. The function in question is a map $f$ from the probability simplex to the family of k-cardinality sets. This function is differentiable almost everywhere, besides the case where the k and k+1 probability are equal. I think the real reason why this $f$ does not suit gradient based training is that it is piecewise constant, and so gradient based training will not see any useful gradient directions with which to update the model. I would like to ask the authors to consider this and either explain to me any misconception I have, or to adjust the motivation given in the paper accordingly. 
- Prop 3.4 is a high probability result. What is the randomness over? The LHS already takes an expectation over the Gumbel variable so I am not sure what other randomness it left.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a specific relaxation of "combinatorial" solvers. Instead, what is mostly described here is a solver for binary optimization. 

The solver is proposed to solver binary problems in an amortized way (and compared with, e.g. gurobi) in Section 3, but also to handle end-to-end learning problems, in which the representation/prediction for data are learned in the inner loop, on a portfolio selection task in Section 4. 

The paper suffers from a few issues (writing is not clear and clumsy in several places, cosmetically the paper is quite ugly, e.g. Fig. 1 provided with a low res definition and tiny fonts, the title is ridiculously long and not so informative, what paper claims to consist in "notes"??) and the application to portfolio selection is not exciting (validation on financial is always rife with issue, where the signal-to-noise ratio is usually very low; there's low interest of the ICLR community for these problems).

). In particular, one wonders how much of hyperparameter tuning was needed to reach these performances, this is not mentioned in the main body of the paper.

The paper has received a mild appreciation from reviewers, but no enthusiasm. I do, however, suggest acceptance as a poster, because the experiments are substantial, notably Fig. 3 and I find the idea overall interesting. If accepted, I expect the authors to put a significant amount of work into improving presentation.
justification_for_why_not_higher_score: The paper is clearly on the fence, borderline.
justification_for_why_not_lower_score: Although I find the main idea of this work original (the concept of integrating soft top-k in a binary selection problem), and I think Figure 3 in particular is interesting, this paper could be rejected because of poor presentation standards and an experimental section in 4 that's questionable (using financial data for portfolio selection) given the low interest of the ICLR community for these problems.
Decision: Accept: poster