On Learning to Solve Cardinality Constrained Combinatorial Optimization in One-Shot: A Re-parameterization Approach via Gumbel-Sinkhorn-TopK
Authors: Runzhong Wang
Li Shen
Yiting Chen
Junchi Yan
Xiaokang Yang
Dacheng Tao
Venue: ICLR 2022 Submitted (2022)
Keywords: Combinatorial Problems
Gumbel Re-parameterization
Optimal Transport
Machine Learning

Abstract: Cardinality constrained combinatorial optimization requires selecting an optimal subset of $k$ elements, and it will be appealing to design data-driven algorithms that perform TopK selection over a probability distribution predicted by a neural network. However, the existing differentiable TopK operator suffers from an unbounded gap between the soft prediction and the discrete solution, leading to inaccurate estimation of the combinatorial objective score. In this paper, we present a self-supervised learning pipeline for cardinality constrained combinatorial optimization, which incorporates with Gumbel-Sinkhorn-TopK (GS-TopK) for near-discrete TopK predictions and the re-parameterization trick resolving the non-differentiable challenge. Theoretically, we characterize a bounded gap between the Maximum-A-Posteriori (MAP) inference and our proposed method, resolving the divergence issue in the previous differentiable TopK operator and also providing a more accurate estimation of the objective score given a provable tightened bound to the discrete decision variables. Experiments on max covering and discrete clustering problems show that our method outperforms state-of-the-art Gurobi solver and the novel one-shot learning method Erdos Goes Neural.


Under review as a conference paper at ICLR 2022
ON LEARNING TO SOLVE CARDINALITY CON- STRAINED COMBINATORIAL OPTIMIZATION IN ONE- SHOt: A RE-PARAMETERIIATTON APPROACH VIA GUMBEL-SINKHORN-TORR
Anonymous authors Paper under double-blind review
ABSTRACT
Cardinality constrained combinatorial optimization requires selecting an optimal subset of k elements, and it will be appealing design data-driven algorithms that perform TopK selection over a probability distribution predicted by a neu- ral network. However, the existing differentiable TopK operator suffers from an unbounded gap between the soft prediction and the discrete solution, leading to in- accurate estimation of the combinatorial objective score. In this paper, we present a self-supervised learning pipeline for cardinality constrained combinatorial opti- mization, which incorporates with Coumbel-Snnhoong discrete TopK predictions and the re-parameterization trick resolving the non- differentiable challenge. Theoretically, we characterize a bounded gap between the Maximum-A A-Posterior (MAP) inference and our proposed method, resolving the divergence issue in the previous differentiable TopK operator and also provid- ing more accurate estimation of the objective score given a provable tightened bound to the discrete decision variables. Experiments on max covering and dis- crete clustering problems show that under comparative time budget, our method outperforms state-of-thh-aa Gurobi solver and the novel one-shot learning method Erdos Goes Neural.
(GS-TopK) for near-
INTRODUCTION
In this paper, we aim to solve a family of cardinality constrained combinatorial optimization: given the cardinality budget k, aim is to find the optimal set with size k which minimizes the objective function fxx). Denote ||x|oo & as the cardinality constraint, we have:
min
(x)
s.l.
||x||o S
Extensive applications these problems can found in machine learning and operations research, for example, discovering coresets for dataset summarization and continual learning (Borsos al., 2020), discovering the most influential seed users in social networks (Chen et al., 2021), and plan- ning facility locations in operation research (Liu, 2009). Although there has been a success in discovering the important submodularity (Fujishige, 1991) for a family of these problems with a bounded approximation ratio of greedy algorithms, the ubiquitous NP-hard challenge is always mo- tivating us to develop improved algorithms with better efficiency- success of machine learning has inspired researchers to develop learning baased algorithms for com- binatorial optimizations (Vinyals et al., 2015; Dai et al., 2016; Karalias & Loukas, 2020; Wang et al., 202 1b), and this paper falls in line with these works.
trade-off. The recent
According to the taxonomy by recent survey (Peng et al., 2021), existing machine learning meth- ods for combinatorial optimization can be mainly categorized into two groups: multi-step meth- ods (Vinyals et al., 2015; Dai et al., 2016; Lu et al., 2019; Wang et al., 2021a) and one-shot meth- ods (Wang et al., 2019; Karalias & Loukas, 2020; et al., 2019). The former line of works usually Markov Decision Process (MDP) and refers to novel reinforcement learning methods (Mnih et al., 2013; Schulman et al., 2017) to tackle the MDP. Perhaps the largest drawback of such multi-step pipeline is that the training and
formulates the combinatorial optimization solving procedure

---

Under review as a conference paper at ICLR 2022
inference procedures can be inefficient. Based on some previous efforts (Wang al., 2019; Li et al., 2019), there is a recent seminal work (Karalias & Loukas, 2020) aiming to develop a one-shot pipeline for general combinatorial problems. Although being a fast and general pipeline, Karalias & Loukas (2020) do not encode constraint in the model prediction and thus the estimation of the combinatorial objective score may be inaccurate.
In this paper, we aim to facilitate the one-shot learning pipeline with cardinality constraints, such that the constraints can be softly encoded by the output of neural network. Regarding the input to (MAP) inference is done by sorting all
TopK as a probability distribution, the maximum-a-posteri probabilities and selecting the K K-largest ones, however, this process is non-differentiable. Though appealing, it is non-trivial to encode the constraint in a differentiable manner with bounded gap w.r.t the MAP inference and the bound of the existing SOFT-TopK algorithm (Xie et al., 2020) diverges the k-th and (A: + Y-th probabilities are equal. Unfortunately, such a dilemma is possible because the probabilities are outputs from a neural network. Besides, concerning the discrete decision variables in combinatorial optimization, it is also non-trivial to build an accurate estimation of the objective score with neural network output (which has to be continuous in order to preserve the gradient).
To tackle the non-differentiable challenge and the ill-estimated objective score, we refer to the sem- inal reparameterization technique with Gumbel noise, which can mimic the sampling procedure from the continuous probability distributions to near-discrete decision variables, while still pre- serving the gradient. Such a technique has been found successful for Top-1 (Jang et al., 2017), permutation (Mena et al., 2018), and sorting (Grover et al., 2019) distributions, and in this paper, improve the SOFT-TopK operator (Xie et al., 2020) by introducing the Gumbel se-parameterization trick, and we theoretically prove that its gap can be bounded with the existence of the Gumbel noise, in contrast to the gap of SOFT-TopK (Xie et al., 2020) that may turn diverged.
To this end, we present Guubel--Sikhool TopK (GS-TopK) to facilitate the one-shot self- supervised learning pipeline (Karalias & Loukas, 2020) with constrained neural network output. The proposed Go-TopK operator improves the SOFT-TopK (Xie al., 2020), where we theoreti- cally characterize a bounded gap by introducing non-zero noise factors. Besides, we show how to integrate the proposed GS-Topk method into the combinatorial optimization pipeline, with an ac- curate estimation of the objective score, formulating a self-supervised learning pipeline following (Karalias& & Loukas, 2020). The contributions of this paper are summarized as follows:
1) We propose self-supervised learning approach to solve cardinality constrained combinatorial optimizations in one shot. The cardinality constraints are encoded in the model output via our pro- posed Go-TopK, and pipeline is differentiable via the ce-parameterizationn trick.
2) We theoretically characterize a bounded gap between the MAP inference and the approximate solution by
-ii---iiiinoooookk without requiring the large gap of k-tth and (k: + 1) probabil- ities, which improves the result of the state-of-the-ar SOFT-TopK algorithm (Xie et al., 2020). This property is crucial for an accurate estimation of the combinatorial objective score in learning.
3) Experiments on max covering and discrete clustering problems show that under a comparative or smaller inference time budget, our method surpasses the state-of-the-an one-shot learning methods e.g. (Karalias & Loukas, 2020), and also surpasses the sire--of-he--utt Gurobi and SCIP solvers.
RELATED WORK
2.1 LEARNING OF COMBINATORIAL OPTIMIZATION
Recently it is a trending topic of developing machine learning based combinatorial optimization methods to achieve better trade-off between time and accuracy by modern data-driven approaches. Here we follow the taxonomy by Peng et (2021) and discuss some representative works.
Multi-step methods predict the solution by multi-step decision process. Since the fundamental work (Vinyals et al., 2015) that proposes an encoding-decodiin architecture, researchers have ex- plored this general pipeline to various real-world combinatorial optimization problems. The most popular framework follows the reinforcement learning pipeline introduced by Khalil et al. (2017), where the state is encoded by graph neural network, and multi-step actions are taken to sequentially construct the solution. Applications have been explored on job scheduling (Zhang et al., 2020), com- puter resource allocation (Mao et al., 2019), quadratic assignment programming (Liu et al., 2020), bin tankkacking (Duan et al., 2019),je just to name a few. The advantage of multi-step methods is that they can handle combinatorial constraints that are non-trivial to be encoded in differentiable manner, by
2

---

Under review as a conference paper at ICLR 2022
adding constraints on the feasible actions in the multi-step roll-out procedure. However, the training of reinforcement learning may be inefficient and vulnerable, and there are also some recent efforts on developing one-shot combinatorial optimization learning methods.
One-shot methods predict the solution by a single forward pass. Despite the challenges in encoding general constraints, one-shot learning methods have been successful on certain problems where the constraint can be encoded by the neural network. For example, in graph matching ( (Wang et al., 2019; 202 the constraint can be encoded by Sinkhorn algorithm (Sinkhorn & Rangarajan, 1964), and also for graph similarity regression problems (Bai et al., 2019; Li et al., 2019) that are unconstrained. The seminal work (Karalias & Loukas, 2020) aims to develop general pipeline for one-shot learn- ing of combinatorial optimization, by encoding the violation of the constraint as part of its objective score. However, our experimental results show that compared to Karalias & Loukas (2020), will be more appealing if we can explicitly encode the constraint in the neural network output.
2.2 OPTIMAL TRANSPORT AND GUMBEL RE-PARRAETTERIZATIN
Optimal Transport. The optimal transport (OT) is a linear programming problem that aims to find the optimal transportation plan with minimal cost. Though the development of the Sinkhorn algorithm can be date back to 1960s (Sinkhorn & Rangarajan, 1964), it has drawn increasing at- tention from the machine learning community since the pioneering work (Cuturi, 2013) which in- troduces the entropic-regguarizztio for the optimal transport problem. Since the Sinkhorn algo- rithm (Sinkhorn & Rangarajan, 1964) incorporates row- and column-wise normalization which is differentiable, OT can be incorporated within any end-to- and-to-end deep learning pipelines. Thus, OT has been found successful for deep generative models (Arjovsky et al., 2017; Patrini et al., 2019), solv- ing jigsaw puzzles (Santa Cruz et al., 2018), and deep graph matching (Fey et al., 2020; Yu et al., 2020). In complement to the recent line of differentiable sorting papers (Petersen et al., 2021; Cuturi et al., 2019), Xie et al. (2020) develop the differentiable Topk algorithm namely SOFT-TopK, by formulating the TopK problem as an OT problem. However, the theoretical gap between the pre- diction of SOFT-TopK and the result obtained by sorting diverges if the k-th and (k + 1)-th largest items are equal. In this paper, we prove that this gap can be bounded by introducing Gumbel noise.
The Gumbel distribution with the pe-aaaameterization trick is shown effective to mimic the sampling procedure from a given distribution in a differentiable man- ner. Jang et al. (2017); Maddison et al. (2017) take the initiative to develop Gumbel-Softmax, where one-hot vectors are sampled from a softmax probability distribution. The non-differentiable sampling procedure turned to be differentiable by the namely re- re-prammttrrizatoon trick (Kingma & Welling, 2013). Inspired by Jang et al. (2017), Mena et al. (2018) propose a Gumbel-Sinkhorn method learn the latent permutations, which is relevant to the GS-TopK method developed in this paper. Besides, Paulus et al. (2020) develop general framework for generating combinatorial distributions via random distributions. However, these existing methods do not study the applica- tion in combinatorial optimization learning, and the gap between the MAP inference and the result after Gumbel re- peraaeettrriztiion is not well characterized in Mena et al. (2018). In this paper, we explore the application of the re-parameterization trick with Gumbel noise in combinatorial opti- mization, also we theoretically characterize the gap between the MAP inference and the proposed Gumbel method.
Gumbel Re-parameterization
3 THE PROPOSED GUMBEL-SINKHORN-TO
3.1 PRELIMINARY: SOFT-TOPK ALGORITHM
The TopK problems are ubiquitous in machine learning, yet the MAP inference approach (perform- ing sorting the time cost of O(m log m) and selecting the first & items) is unfriendly for current gradient-based deep neural networks. To introduce differentiable TopK for machine learning, Xie et al. (2020) formulate the TopK problem selecting the & largest items from the probability vector s of size m (k- < m)) the OT problem refers moving k items to one destination (selected), and the other m - k elements to another destination (not selected). Thus, the marginal distributions of the OT are:
optimal transport (OT) problem. Specifically, for
m K
}}
c
1
r
k
destinations
(2)
m items
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Gumbel-Sinkhon-TTopk (GS-TopK) for Solving Cardinality Constrained Combinatorial Optimization
Input: List with m items; TopK size k; Sinkhorn factor noise factor σ; sample size #G.
for a E {1, 21.,.... #G} do
for all 8; a log( (rg(,)), where u; is sampled from (0, 1) uniform distribution; Sm min(s) max(s) 8m
min(s)
1 k
D max(s) - Si
T. exp(-
while not converged do
D. = diag T @r);
T. = D. To:
D diag [ 1
c);
Ta TTD
Output: A list of transport matrices (Ti, T2, Tag.
We can design the destinations to be the min/max values of such that the TopK items are moved max(s), and the other items are moved to min(s). Then, the distance matrix of OT given as:
$1 min $2
min(s) max $2
Sm min(s))
D
max
max(s) Sm
While the OT is formulated as an integer linear programming problem:
min DD)
s.t. T (0,1) mxx T1 TT=
(4)
where the transportation plan which also corresponds to the TopK solution of the problem, and is column vector whose all elements 1s. The optimal solution T should be equivalent to the solution by firstly sorting all items and then selecting the Topk items. It is also equivalent to the MAP inference by regarding S1,.., Sm probabilities. Following the differentiable Sinkhorn algorithm for OT (Cuturi, 2013; Sinkhorn & Rangarajan, 1964), the binary constraint on T is relaxed continuous values [0, 1), and Eq. (4) is modified with entropic regularization:
min (T D) Th(T") T
s.t.
T E [0, m) T' = -. 1
(5)
where ((TT)) = Eig Tú, Ty, is the entropic regularizer (Cuturi, 2013). Given any real-valued matrix D, Eq. (5) is solved by firstly enforcing the regularization factor r: T exp(-D/T). Then T row- and column- normalized alternatively:
D, = diag T @r),
T = D D. = - 10 = T'D (6)
where 0 means element-wise division. We denote T as the converged solution, which is the optimal solution Eq. (5).
Theorem (Xie et al., 2020). Denote Fy. 2x+1 as the k-th (k + 1)-th largest items, we have
2mr log
- S
F4+1l
where the gap is controlled by r if lark - sa+il > However, the above bound diverges ær Tk+1, which is unavoidable because Tx+1 are outputs by neural network. It motivates to develop our improved version Humbel-Sinkhonl TopK by introducing the Gumbel noise.
3.2
SUNKHORN-TOPE (GS-TOPK) ALGORITHM
In this section, present proposed Cumbee-SSnkhorm- TopK (GS-TopK) summarized in Alg. I and we theoretically characterize the gap between the MAP inference and the prediction by GS-TopK. As the re-parameterization trick (Jang et al., 2017), instead of sampling from dis- tribution that is non-differentiable, we add random variables to probabilities predicted by neural networks, The Gumbel distribution characterized as:
Je (u) log(- ((o[(olo())))
(8)
4

---

Under review as a conference paper at ICLR 2022
where a controls the variance and u is from (0, uniform distribution. We update and D as:
S = S; + 9o (u,)
(9)
D Si min ss) max
S2 min(s) max(s) $2
Sm min max(s) Sm
(10)
Again we formulate the integer linear programming version of the OT with Gumbel noise:
min tr ( DD s.t. T E (0.1) mxx T r. --r
1=c.
(11)
T
where the optimal solution Eq. (11) denoted T Without loss of generality, in the following
we sort $1, $2, S....., Sy in descending order. into X' = 21; Z2 T3, 2m. and 2 Fk+1 are the k-th and (k + 1)-th largest items, respectively. We characterize the gap between T and T under the expectation over Gumbel distribution.
Now we present the following two lemmas to help establish our theoretical results, in terms of bounded gap between the MAP inference and the approximate solution by Gumbel-Sinkhorn- TopkK,
Lemma 1 (Bias by the Gumbel Noise). For the integer linear programming solutions with and without Gumbel noises, have
4m
E. IT -
(12)
exp
Proof sketch: The gap between T Tox is derived by counting the expected number of times that, after adding the Gumbel noise, element may become larger than or smaller than 2 For the top l elements, the probability that will become smaller than Tk+1 is upper bounded by 1/(1 + exp #t =+++))))) For the last (m k) elements, the probability that it will become larger than Iy is also upper bounded by 1/(1 + exp =x- Since T - I changes at most by 4 an item becomes larger/smaller than 22/24411 and we have items, then we can proof the upper bound of this gap. The detailed proof is referred to Appendix A.I.
To make the integer linear programming problem feasible for gradient- based deep learning methods, we also relax the integer constraint and add the entropic regularization term:
min t D) (T)
s.t. T j0, 1]mx2 TI T
(13)
T
which is solved by Sinkhorn algorithm on D: firstly T = exp( -D/r- then
D, = diag T1 2 r), T D-
D. diag T 1 1 c), T=TD-1
(14)
Here denote the optimal solution Eq. (13) T We theoretically characterize the gap between TØx and T which corresponds to the optimal solutions of Eq. (11) and Eq. (13), respectively. Lemma 2 (Gap to Discrete Solution). Under probability (1 E), have
Ey
|
[|] s (log 2) Σ 0(,,),
(15)
where
2x log (a 1220 |2: xzyl (1 + arctan R--0;
log(1-4
20
Xz, = (1 c) 322)2 20 exp Be=mk (1 exp Fe+s
(16)
Proof sketch: The gap between T and T is a generalization from the Theorem 2 of Xie et al. (2020). We denote T Taze1 as the k-th and (k: + 1)-th largest items af- aim becomes to prove the upper bound
ter disturbed by the Gumbel noise, and of E, [1(( + 9o (uT,) Irees - 9o (Mm,_)))). where the probability density function of g. (ur,) 9o (u(uu,))) ) can be bounded by f(y) = 1/(y² + 4). Thus we can compute the upper bound under probability (1 e) by integration. The detailed proof is referred Appendix A.2. n
5

---

Under review as a conference paper at ICLR 2022
Graph Modeling of the Problem
Graph Neural
Add Gumbel Noise
Network
Input graph
graph with probubilittes
Contae wake
SOFT-TopK (k=2)
Objective score
Forward pas
Dackwort
probabilitiee with Gumbel noise
Topk solution
Figure 2: Our proposed self-supervised learning pipeline for combinatorial optimization. The prob- ability of selecting each element is predicted by graph neural network, and an accurate estimation of the combinatorial objective score achieved via near-discrete TopK solution by our GS-TopK.
Theorem 1. For the proposed Gumbel TopK solver, denote T as the solution by deterministic TopK algorithm, T as the solution of Hombeel-Snnhorn-ee With probability (1 e), we have
Eu -T S
4m
52+1l + (log 2)
Σ i#
(17)
1+ exp
where a is the noise factor and T is the lemperature of Sinkhorn algorithm. m is the number of candidates be selected. Mz 0, is defined in Eq. (16).
Proof: Based on Lemma and Lemma 2, Theorem is proved by triangle inequality:
E
T
T
E. I T
11 By
T T'
Remarks. As derived above, the gap between T and T is composed of two parts: the bias by the Gumbel noise (in Lemma 1) and the gap to a discrete solution (in Lemma 2). Interest- ingly, the first term becomes smaller given smaller a, and the second term is smaller given a larger
2.00
1.75
1.50
1.25
smaller т. See the toy example in Fig. 1, a larger a can tighten the gap of GS- Topk to discrete solution, which is welcomed in our combinatorial optimization learning see- nario where T is used to compute the objective score in a self-supervised learning pipeline.
Gap Diarete
1.00
65 Toyk 0.050)
0.P5
G5-Tepk (700.0
65-Tapk (r-0.005)
0.50
65 Topk (1- 0.002)
TopK (T- 0.030)
I-Tosk (T- 0.005)
0.00
c.0033
If [z 2*+1| > 0, with + 0+, Eq. (17) degenerates the bound derived by (Xie al., 2020) and only differs by constant factor (see Appendix A.3 for details):
Olgg scale)
Figure 1: A toy example to explain Lemma 2: se- lect top-3 items from [1.0, 0.8, 0.601. 0.6, 0.4, 0.2) and we compare GSSToppK, and SOFT-TopK con- cerning the gap discrete solution w.r.t. differ- ent configurations. Here the gap to discrete solutions tighten by larger a and a smaller for GS-TopK, compared to SOFT-TopK whose gap is larger and can only be controlled by т.
T -T'll]] (1 (TT log 2)mr
lim Ey a-50
c) 1 rk+1
It makes strong assumption that - 0, and the bound diverges I4 = F&+1. Un- fortunately, Fy,, 24+1 predictions by neural network, whereby such an assumption may not be satisfied. In comparison, given a > 0, our conclusion in Eq. (17) is bounded for any Dk, I++1-
3.3 APPLICATION TO
COMBINATORIAL OPTIMIZATION LEARNING
In the following, discuss the application of GS- Go-TopK to sulf-super combinatorial optimiza- tion learning. by taking the max covering problem as an example. We consider the max covering problem with sets and objects. Each set may cover any number of objects, and each object is

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Gumbel-Sinkhonn-Tpp Learnnn Learning for Solving the Max Covering Problem
bipartite adjacency A; values v; learning rate o; GS- GS-TopK parameters k, T, #G. if Training then
Input:
Randomly initialize neural network weights 0:
if Inference then
Load pretrained neural network weights 0; Joest = O;
while not converged do
S = GraphSagee@AA (A): 1T T2,... Taol GS-TopK #G); for all i, i, min (T, [2,]AAJ v; mean([]1, J2. ..., J+ol); if Training then
L update with respect to the gradient
8J and learning rate or by gradient ascent; by
10
Inference then update with respect to the gradient for all i, J, Topk (T.2:)))
@J and learning rate a by gradient ascent; d
11
Joest max([ .... Jacl, Jbest);
if Homotopy Inference then Shrink the values of T, a and jump to line 5;
14
Output: Learned network weights 9 (if training)/The best objective Jbest (if inference).
associated with value. We aim to find k sets (where k < m) such that the covered objects have the maximum sum of values. The general illustration of our pipeline can be found in Fig.
Firstly, we build bipartite graph whose two disjoint sets of vertices are the sets and the objects. edge is defined an object is covered by set. Denote v E R² as the value of each object, and A E (0, mmx as the adjacency matrix, the problem is formulated as
max Σ
Σ x A
s.t.
x E 10,
|| S k
(18)
==1
where I(x) is an indicator I(x); = if 2 1 else I(x); = O. To encode the bipartite graph, we exploit three layers of GraphSage (Hamilton et al., 2017) followed by a fully-connected layer with sigmoid to predict the probability of selecting each set, which is denoted as s E 00 The probabilities s are fed into the Go-TopK algorithm, which outputs a batch of near-discrete trans- portation matrices [TΙ, T2.... THul. whose second row is regarded as a continuous approximation of the decision variables. The objective value estimated
minn
J= mean ([J,, J2, JHa])
(19)
For the discrete clustering problem, we aim to select & objects from the full set of m objects, by minimizing the sum of distance for each object between itself and its nearest selected object. differs from the k-means clustering by adding the "discrete" constraint that cluster centers have to be a subset of objects, which also known as facility location problem in operations research (Liu, 2009). Denote A E m as the distance matrix for each pair of objects, we formulate the discrete clustering problem as follows (please refer to Appendix B for details):
m
min Σ
min({ (aiin(A,,)))) Vx; = 1}) s.l. x (0,1)", 1,oloo
(20)
As illustrated in Alg. 2, during training, the Adam optimizer (Kingma & Ba, 2014) is applied for learning the neural network weights. During inference, the neural network prediction is regarded initialization, and we again optimize the distribution w.r.t. the combinatorial objective score by Adam, during which search procedure is also performed among all Gumbel samples.
Homotopy GS-TopK. Based on our Theorem the gap between T and T can be tightened by shrinking т and o, which motivates us to develop a homotopy variant (Xiao Zhang, 2012;
Xu et al., 2016) of GS- GS-TopK with gradually decreased T, a. such that T and J can provide more accurate estimation during inference. See line 13 in Alg. 2 for details.

---

Under review as a conference paper at ICLR 2022
Tuc
013
21.6
12.5
12.5
80
(a) Erdos Goes Neural
(b) SOFT-Topk w/ sampling
(c) Homotopy GS-Topk
Figure 3: In discrete clustering, comparison of the estimated objective score (red) and the real one (blue). Our GS-TopK achieves the best accurate estimation of the objective score.
4 EXPERIMENTS AND DISCUSSION
4.1 PROTOCOLS AND BASELINES
We apply the proposed Go-TopK algorithm learning two representative problems of cardinality constrained NP-hard combinatorial optimization: i) max covering and ii) discrete clustering prob- lem. For each problem, both a smaller-sized case and a larger-sized case are considered, and build separate training/testing datasets for learning methods. In this paper, we referred to randomly gen- erated datasets following previous machine learning for combinatorial optimization papers (Khalil et al., 2017; Kool et al., 2019) concerning the limited large-scale open-source dataset. For the max covering problem, our data distribution follows the distribution ORLIB' For the discrete cluster- ing problem, the data points uniformly generated in a 2D plane.
We compare the following representative and diverse baselines with our proposed method:
Classic Algorithms. Classic algorithms are well-developed strong baselines with theoretical guar- antees. In our experiment, we consider the greedy algorithm as the baseline for the max covering problem, which has the worst-case approximation ratio of (1 1/e) due to the submodularity of the max covering problem (Fujishige, 1991). For the discrete clustering problem, we resort to the classic kmeans (Macqueen, 1967) and kmeans++ (Arthur & Vassilvitskii, 2007) with improved ini- tialization techniques. These algorithms are fast but effective, even surpassing commercial solvers with only 1/1000 inference time certain test cases.
General Purpose Solvers. We also compare two general-purpose purpose solvers Gurobi 9.0 (under educa- tional license) (Gurobi Optimization, LLC, 2021) and SCIP 7.0 (Gamrath et al., 2020). Gurobi is the state-of-the-art commercial solver for general combinatorial optimization tasks, and it is known heavily engineered by various speedup techniques. SCIP the stute-of-the-are open-source solver, which is also regarded as baseline. We formulate the combinatorial problems as integer program- ming and then call the solver to solve the problems, with a limited time budget. Our implementation of the solvers is with the Google ORTools API
One-shot Learning Baselines. We compare with the general Erdos Goes Neural (EGN) (Karalias & Loukas, 2020) framework that models each decision variable as a Bernoulli distribution and encodes the constraint as part of the learning objective. Since the authors of (Karalias Loukas, 2020) do not consider cardinality constrained problems in their experiment, we re-implement and tune the EGN model based on their official implementation? We also compare with SOFT-TopK (Xic ct al., 2020), special case of proposed GS- when o 0. Also
which is theoretically characterized to ensure the effectiveness of the re- re-parameterization trick, we facilitate SOFT-TopK with Gumbel sampling during inference. All one-shot learning methods with the same model structure for fair comparison and are trained and tested on separate datasets. Besides, we empirically find the learning process of one-shot methods converges within of minutes. Since the reinforcement learning methods (Khalil et al., 2017; Chen & Tian, 2019) require significantly more training time, we only include shot methods for fair comparison.
http://pppe..ttuu........aa/aaaa hnttps://devell http///eeeeeoe..seeeeeeeeeeeeeee wwwpr..ooggl............oooooo.. com in zation iniztaionn Phttps://gi thub. com/ /taataaal lence/errcc__ee
http://tttt/ioooooo//t/ html
8

---

Under review as a conference paper at ICLR 2022
Table 1: Objective score and inference time (in seconds) I comparison of the max covering prob- lem, including mean and standard deviation. Under cardinality constraint k. the problem is to select from m sets to cover a fraction of n objects. Gurobi solver fails to return the optimal solution within 24 hours, thus reported as out-of-time. Our GS- Tos-TopK outperforms all competing methods, with comparable or smaller time costs. The performance is further improved by Homotopy GS-TopK.
50 500, n=1000
k=100, m=0000, n=2000
ToNs are one-shot solvers
objective
time & (sec)
objective
time 4 (sec)
greedy
44812.8+888.44
0.024:10.000
12697.
0.089+100001
SCIP 7.0 (fuster)
43034,7::8992 2
30.05811.0017
16269.9111256.3
59,916.:1.752
SCIP 7.0 (slower)
43497.41175.6
100. 136=0,097
86269.9:11256.
120.105 105
Gurobi 9.0 (faster)
6-666.66
30.078=0.004
85992.4- 1643.7
60. 168 +0004
Gurobi 9.0 (slower)
43937.2.1711.5
0.000
86862.1111600.5
120.277:10.139
Gurobi 9.0 (optimal)
O0T
O0T
OOT
OOT
EGN (efficient) (Karalias & Loukas, 2020)
36423.7 122.4
0,244=0.107
103
0.525==0229
EGN (accurate) (Karalias & Loukas, 2020)
36937.34+:163.0
40.54214.056
11487.5+1552..
93.670:18.79 7.77
SOFT-TopK (Xie al., 2020)
41959.9::03.4
48.605
8322..
45.252=0.713
SOFT-Topk (w/ sampling)
39684.8+665.6
44.960
77285. 11285.2+1123.9
59,488=0.145
GS- To-TopK (ours)
44710.3++77.9
32.839+3.227
89264.8+ 1232.1
60.685+0.045
Homotopy GS-Topk TopK (ours)
44718.2:1745.2
47.627
89294.312211.2
89.764++0128
Table 2: Objective score 4. optimal gap + and inference time (in seconds) \ comparison of the discrete clustering problem, with mean and standard deviation. The problem is to select & clustering centers from m data points. GS-TopK and Homotopy GS-TopK surpasses all competing methods with less time compared to general purpose solvers and other one-shot methods.
k=50,, m=000
k=50, m=000
Tupkoorss are one-shot sulvers
objective 1
optimal gap
time (sec)
objective 1
optinal gap
time (sec)
kmeans (Macqueen,
3.020+00.000
0.214-0.049
0.033-0.074
2.905+0.159
0:233-0:002
0.065:20.144
kmeanse+ (Arthur& Vassilvitkkii, 2007)
2.854#0.166
0.109=0.044
0.042:10.007
2.695=0.101
0.174=0.027
0.504+0.234
SCIP 7.0 (faster)
4.84111880
0.377_00288
71.738 192
5:45010.674
0.587_10.016
218.426:157.50
SCIP 7,0 (slower)
1.87011.918
0 033880229
118. 106616888.00 055
5.25811.0118
0.552.10.14 146
213.9191511.15
Gurobi
3,365:0).411
0.200000072
80.582::08861
3.532:10.358
Garobi 9.0 (slower)
2
0033-00042
125.
3.362+00.26
0.335-0.055
214.360+33.5 3,785
Gurobi 9.0 (optimal)
2.36510.063
0.000.0.0000
314.7981 16.858
2.221110.011
0.000.0.000
618.21331191.186
EGN (ollicient) (Karalias & Lonkas, 2020)
3,852H0 195
0217-00088
D 308
2.865-0.138
0.223-0.0056
0.988+0.144
EGN (accurate) (Karalias Loukas, 2020)
2.795+0.144
0.152-0055
123.559+12.22
2.815+0.124
0.209-0
191,091=13.00
TopK (Xle 2020)
2.719=0.136
0.299-0.07
97.147=6.565
2.600=0.104
0.545=0.022
120.835=12200
SOFI-TopK (w/ sampling)
2.71710.118
0.129_0.027
129.856:17,256
2.593:10.086
0,142-100026
166, 136.132:18.01
GS-Topk (ours)
2.120.1.0022
0.023_0..09
76.53116.3211
2.283.10.050
0.027100000
220.6891.2.. 105
Homotopy GS- (omrs)
2.418=00.076
0.022::0.010
103.74 703.742=-4.778
2.273::00004
0.023-1-0.07
158. 158.400=:3.499 1498
4.2 EXPERIMENTAL RESULTS
Table 1 and Table 2 report results on max covering and discrete clustering problems, respectively. An interesting finding is that the classic algorithms are efficient but also very effective. However, can afford higher time budget, there seems universal approach to improve the results of the classic algorithms. In comparison, Gurobi and SCIP solvers can trade-off time for better accuracy, but they are less effective than our learning methods when considering the objective scores under the same time budget. Among one-shot learning methods, Erdos Goes Neural (Karalias & Loukas, 2020) is the only method that does not encode the constraint in the model output, and the experimen- tal results suggest that it is appealing if we can encode the constraint in the model output. Directly applying Gumbel sampling to SOFT-TopK seems either an effective improvement, and satisfying results are achieved when exploiting the Gumbel re- pe-armmtterizaiion trick and enabling gradient- based optimization over the combinatorial objective score. We further validate the effectiveness of Homotopy To-Ko, where the objective scores are improved at the cost of more inference time.
Further Discussions. Our insight for the effectiveness of GS-TopK over other state-of-the-art one- shot learning methods (Karalias & Loukas, 2020; Xie et al., 2020) is that it can provide a more accurate estimation of the combinatorial objective score with discrete decision variables. Fig. shows that GS- GooTopK estimates lower bound of the true objective score at the beginning 200 iterations while providing an accurate estimation afterward. Besides, the Homotopy version of our algorithm can gradually reduce the variance and help converge to a better solution.

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
The following efforts are made to ensure the reproducibility of this paper:
We provide a complete proof about our Lemmas and Theorems in the Appendix, see Ap- pendix A;
We discuss the hyper-parameter configurations and the experiment setup in Sec 4.1;
We provide the implementation details on max covering problem in Sec. 3.3, and the im- plementation details on discrete problem problem in Appendix B;
We discuss the way generating random dataset Sec 4.1;
The code will be made publicly available once this paper is accepted.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. arXiv e-prints, art. arXiv:1701.07877 January 2017.
David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. Proceed- ings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '07, pp. 1037-1035, USA, 2007. ISBN 9780898716245..
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neu- ral network approach to fast graph similarity computation. Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pp. 384-392, 2019.
Zalán Borsos, Mojmír Mutný, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Neural Info. Process. Systems, 2020.
Wei Chen, Xiaoming Sun, Jialin Zhang, and Zhijie Zhang. Network inference and influence maxi- mization from samples. In Int. Conf. Mach. Learn., July 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. Neural Info. Process. Systems, 32:6281-6292 2019.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Neural Info.
Process. Systems, pp. 2292-2300, 2013.
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. In Advances in Neural Information Processing Systems, volume 32, pp. 6858- 6868, 2019.
Hanjun Dai, Bo Dai, and Le Song. Diseriminative embeddings of latent variable models for struc- tured data. In Int. Conf. Mach. Learn., pp. 2702-2711. PMLR, 2016.
Lu Duan, Haoyuan Hu, Yu Qian, Yu Gong, Xiaodong Zhang. Jiangwen Wei, and Yinghui Xu. A multi-task selected learning approach for solving 3d flexible bin packing problem. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, pp. 1386- 1394, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. SplineCNN: Fast geometric deep learning with continuous b-spline kernels. Comput. Vis. Pattern Recog., pp. 869-877, 2018.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In Int. Conf. Learn. Rep., 2020.
Satoru Fujishige. Submodular Functions and Optimization. Elsevier, 1991.
10

---

Under review as a conference paper at ICLR 2022
Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christo- pher Hojny, Thorsten Koch, Pierre Le Bodic. Stephen J. Maher, Frederic Matter, Matthias Mil- tenberger, Erik Mühmer, Benjamin Müller, Marc F. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL http:// / www. opt imi iomizaatinn onlonnnine org/De BIIBBHHMLL/S http///220000/000 html.
Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon. Stochastic optimization of sorting networks via continuous relaxations. In Int. Conf. Learn. Rep., 2019.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL https://www.
gurobi ccm.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Neural Info. Process. Systems, 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In Int. Conf. Learn. Rep., 2017.
Nikolaos Karalias and Andreas Loukas. Erdos goes neural: unsupervised learning framework for combinatorial optimization on graphs. In Neural Info. Process. Systems, 2020.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. Neural Info. Process. Systems, pp. 6351-6361, 2017.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. Ini. Conf. Learn Rep., Dec 2014.
Diederik P Kingma and Max Welling. arXiv:1312.6114 December 2013.
Auto-Encoding Variational Bayes. arXiv e-prints, art.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In Int. Conf. Learn. Rep., pp. 1-25, 2019.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In International Conference Machine Learning, pp. 3835 3835-3845,10 2019.
Baoding Liu. Facility Location Problem, pp. 157-165. Springer Berlin Heidelberg, Berlin, Heidel- berg, 2009. ISBN 778-3-540-894844 doi: 000077978-3-540-844844444
Chang Liu, Runzhong Wang, Zetian Jiang, and Junchi Yan. Deep reinforcement learning of graph matching. arXiv preprint arXhv:2012.089500 2020.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning- based iterative method for solving vehicle routing problems. In Int. Conf. Learn. Rep., 2019.
J. Macqueen. Some methods for classification and analysis of multivariate observations. In In 5-th Berkeley Symposium on Mathematical Statisties and Probability, pp. 281-297, 1967.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. Int. Conf. Learn. Rep., 2017.
Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group on Data Communication, pp. 270-288, 2019.
G. Mena, Belanger, S. Linderman, and Snoek. Learning latent permutations with gumbel- sinkhorn networks. Inf. Conf. Learn. Rep., 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 132.5602, 2013.
11

---

Under review as a conference paper at ICLR 2022
Giorgio Patrini, Rianne van den Berg, Patrick Forré, Marcello Carioni, Samarth Bhargav, Max Welling, Tim Genewein, and Frank Nielsen. Sinkhorn autoencoders. In Amir Globerson and Ricardo Silva (eds.), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial In- telligence, UAI 2019, pp. 253, 2019.
Max В Paulus, Dami Choi, Daniel Tarlow, Andreas Krause, and Chris Maddison. Gradient esti- mation with stochastic softmax tricks. Neural Info. Process. Systems, 2020.
Yun Peng, Byron Choi, and Jianliang Xu. Graph learning for combinatorial optimization: A survey of state-of-the-art. Data Science and Engineering, 6(2):119-141, 2021. ISSN 2364-1185, 2364- 1541. doi: 1010000/0019-02-0000000000000000
Felix Petersen, Christian Borgelt, Hilde Kuehne, and Oliver Deussen. Differentiable sorting net- works for scalable sorting and ranking supervision. In International Conference Machine Learning (ICML), 2021.
R. Santa Cruz, B. Fernando, A. Cherian, and S. Gould. Visual permutation learning. Trans. Pattern Anal. Mach. Intell., 41(12):110031111 -11444 2018.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
R. Sinkhorn and A. Rangarajan. A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statisties, 1964.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Neural Info. Process. Systems, pp. 2692-2700, 2700, 2015.
R. Wang, J. Yan, and X. Yang. Learning combinatorial embedding networks for deep graph match- ing. In Int. Conf. Comput. Vis., pp. 3056-3065, 2019.
Runzhong Wang. Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang, Jun Zhou, and Xiaokang Yang. A bi-level framework for learning to solve combinatorial optimization on graphs. In Neural Info. Process. Systems, 2021a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and multiplc-graph match- ing. Trans. Pattern Anal. Mach. Intell., 2021b.
Lin Xiao and Tong Zhang- A problem, 2012.
homotopy method for the sparse least-squares
Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha, Wei Wei, and Tomas Pfister. Differentiable top-k with optimal transport. In Neural Info. Process. Systems, volume 33, pp. 20520-20531. Curran Associates, Inc., 2020.
Yi Xu, Yan Yan, Qihang Lin, and Tianbao Yang. Homotopy smoothing for non-smooth problems with lower complexity than (1/c).. Neural Info. Process. Systems, 2016.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with chameel-independent embedding and hungarian attention. In Int. Conf. Learn. Rep., 2020.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. Neural Info. Process. Systems, 33, 2020.
12

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREMS
Before starting the detailed proof of the lemmas and theorems, firstly we recall the notations used in this paper:
T (D) is the optimal solution of the integer linear programming form of the OT problem Eq. (4), which is equivalent to the solution by firstly sorting all items and then select the Topk items;
T = Sinkhorn(D) the optimal solution of the entropic regularized form of the OT problem Eq. (5) solved by Sinkhorn algorithm. It is also the output by SOFT-TopK (Xie et al., 2020);
T = (D) is the optimal solution of the integer linear programming form the OT problem after disturbed by the Gumbel noise Eq. (11), which is equivalent to the solution by firstly adding the Gumbel noise, then sorting all items and finally select the TopK items;
T Sinkhorn(D) the optimal solution of the entropic regularized form of the OT problem after disturbed by the Gumbel noise Eq. (13) solved by Sinkhorn algorithm. It is also the output by our proposed GS-TopK.
Lemma 3. Given real numbers Tz, Tj, and u, új are from i.i.d. (0, 1) uniform distribution. After Gumbel perturbation, the probability that x, Do (u,) 2j + 90 (u,) is:
P(x; + 9o (u:) 23 + go 1 + exp Zi-zi
(21)
Proof. Since go (u:) a log(-looog log(u))), P(x; (us) Bj go (u,)) is equivalent to the probability that the following inequality holds:
x; a log( - log(u:)) > I - ooglloo(- ((o(-()))
(22)
And we have
2, 2j > log( Loeg--loger llo(--))))))----- log( (og(-))
(23)
Ij
log(u;)
log
(24)
log(uy)
4:
log(u; (11)
(25)
log(u))
Since Uj E 10. log(u,) < 0. Then we have
log(u,) < log(u,))
3imzi
(26)
log (u₂) < log
u;
exp
(27)
Uj u
exp
(28)
Since ui, uy are i.i.d. uniform distributions, the probability when the above formula holds
duž du, 1-'
exp u1
dug
(9))
+ exp 21-z,
Thus the probability that x; + go (u:) xj + Ge (Uz) after Gumbel perturbation is:
P(z; go (u:) > xzj gn (u;))
(30)
1 + exp 34 1.
13

---

Under review as a conference paper at ICLR 2022
A.1 PROOF OF LEMMA 1
Proof of Lemma 1. If one of the top-k items becomes smaller than Tx+1 after distorted by the Gum- bel noise, then || T increases most by Without loss of generality, here we assume x; as one of the top-k items i.c. i s k. According to Lemma 3, the probability that z; becomes smaller than Fx+11 after perturbation
P(x; (u() #8+1 + Gar (ux+1)) 1 1+ exp
(31)
#k-1 -
Similarly, if one of the last-(m k) items becomes larger than Fy. after distorted by the Gumbel noise, then ||TH - Tp also increases at most by 2. Without loss of generality, here we assume Iy of the last-(m k) items i.e. j 2 k 1. According to Lemma 3, the probability that zz becomes larger than 2y after perturbation is
P(a, + go > o& + 90 (ux))
(32)
1 + exp
To compute the expectation of T - TT ||. we sum all probabilities and we have
4
4
E
(33)
exp S++1
+ exp 5.-ux
where the constant 4 appears because ||T crosses the boundary. Since for all i < k and 2 k 1, we have
T will change at most by 4 if one more item
Tk-1 S Tk+1 Tk
(34)
Ij 2g S xb+1 - IK
(35)
Thus we have
4
m
Eq. (33)
Σ
(36)
1 exp
+ exp
1b 14
m
(37)
21+1 BBk
exp
4m
(38)
1 exp
F2 -1+1
Since E, I T 1| I /
Bu
T
To. 1|]
we have
4m Ln
-
(39)
1 exp
21+11
A.2 PROOF OF LEMMA 2
Proof of Lemma 2. By disturbing X with i.i.d. Gumbel noise, we have
X' = 21 + go (u1): x2 + go (u2), 23 + go (ug).... Lm + go (um)
(40)
where (u) = -a log( (w) the Gumbel noise modulated by noise factor a, and U1 U2 ....... Um are i..dd uniform distribution. We define descending order, i.c zz, + go (u Daz + go (2 Izs + (u ) ..., Irm + 9r (ur)) are in descending order.
the permutation of sorting X' in
14

---

Under review as a conference paper at ICLR 2022
Recall Theorem 2 in (Xie et al., 2020), for 21, 02, 43, ... Zm have
2mr log 2
T
S
(41)
2 I++1
By substituting X' with X" and taking the expected value, we have
2m log 2
Eu
|
& En
(42)
(T + go (M(TT) FT&+1 Jo (MT441)
Based on Lemma 3, the probability that = i, TT-1 = is
1
P(TK =i = =) 1 + exp
VT
+ eep
Smg
b=k+2
+ exp
2y Zy-Fry
(43)
where the first term denotes v; Do (u:) > 23 + 9o (uz). the second term denotes all conditions that there are (A: 1) items larger than x; + (u,),) and the rest items are smaller than T, + 9o (uz).
In the following we derive the upper bound of E,
We denote
Fre (ur,) -2 Be (M
Ai, as
U4 2y E Aig s.t. x, + go(u)) - Ij (n;()) >
(44)
where e is a sufficiently small number. Then we have
Em
TTTy Do (Uxz) Toati Io (Moe+1)
P(TTe- = -x41 = j) BuguyEAis
(45)
(ri + go( - I, (1z)
m
1 exp exp
VIT
1 exp
Feo -Is
k+2
exp
2y
1
En
(46)
[: + 9o (u;) - 2y go (o,
m
1 + exp
Ni 1i-or
VT
1 exp
b=k+2
exp
1
Eu Edis
(47)
1x:- - lolg(
(1g(
Fi + log( log(
1004-21.000 22) -21,00))
Σ
1-1
m
1
(48)
+ exp
b=
+ exp
We denote / (6, o, as:
1 exp Euruy S.t. 8 o log( (u.)) + a (o(((o)g(,)))))))))))((()))))))) > =>0 0 For the probability terms Eq. (48), for all permutations म. there must exist Tay The such that
(6,0,2)
E
(49)
[ o log( log(u:)) + a log( log(u;)))
(50)
(51)
+ exp
1 1 exp Fa-di
(52)
1 1 exp
3 Jz
1 + exp Jt 2611
15

---

Under review as a conference paper at ICLR 2022
Thus have
1
Eq. (48) -
Σ
[(1 - T,²
(53)
1 exp
exexp
1 exp
Pk+1
#j
f(z; 2j.
(54)
(1 exp
(11 + exp 1k41-2
ifj
By transforming Eq. (21) in Lemma 3, and substituting zy by y, we have
Eq. (21) P(g.(uu Jo (uy) zj - xx;)
(55)
1 + exp 3i-2)
1
P(go(ui 9o (2y) y) = 1 exp
(56)
1
P(gg(u: Jo (uy) 3) 1 exp 2
(57)
1 cxp cxx y
where the right side is the form of the cumulative distribution function (CDF) of standard Logistic distribution by setting a 1:
CDF(g) 1 exp (-y)
(58)
Thus - log(-- log(u;))+ +lo[[- is equivalent to the Logistic distribution whose probability density function (PDF) is
dCDF())
PDF(g)
(59)
dy
exp (-1) + exp y +
and in this proof exploit upper bound of PDF(y):
PDF(v) exp (-1) exp
(60)
822 +
Based on the Logistic distribution, we can replace -a log(- log(;)) + a log(- log(-log(u,)) by oy where y is from the Logistic distribution. Thus can derive the upper bound of f(ō, 0, as
16

---

Under review as a conference paper at ICLR 2022
follows
( -y) y+2 dy
dao kotg //otz 8/
(6,
(61)
1 expp
(h-) dxe 16/042
+xxp 2 dy
exp kotg ( (-y)+ y+2 dy
1
= 1 exp
(62)
I#exp (0/0-1
-0/0+z
booy expl +xxp y+2 dy
(63)
14 +xexp
exp (8/0-2)
1oxpp (6/0
[6/002 stoy expl 8) exp 4+
(64)
1 1 expp-
1texp (-6/0==
1 exp(
(x +22
000
1
-8/042 8 8+ oy Oyyexp (xp(-1) + exp +2 dy
(65)
1 1+exp exp-pp2 -
+ exeepp- (-p +2)
00
1 8 oy 112 +
dy
(66)
1+ exp
-6/0+z 8
+ exp
+
20 20 ((20 - -)2 + 40 25 arctan
=-6/0 2
44 log + n8
+ ++ep--
482 + 1662
(67)
14 exp
(-pp-3 (-
2)
2o log ((zo + 181)2 + 40²) 20 arctan
2-5/0
4a log z 5
1 + exp
402 + 16o²
(68)
+ (-
2o log ((zor + +0))2 + 40²)
26 aretan
3-8/0
2o log z² + T
1 exx
48 + 16o2
(69)
+ exp (-p +))
(-)
2o log
|1)+ 400
25 arctan
2-0/0
+ Tō
2²
(70)
1+ ++xp--
48
16o2
1 exe --2))
2o log
(sx 161+11)+207)
25 arctan
3-0/0 2
+ π
2²
(71)
1+exp-
45
166²
+ 1exxp( (-a + 2)
4a log
161-6
28 arctan
3-000 2
+ +x0
(72)
1+ 1+exp- +xxp--
482 + 16g2
1 1 1xexp(-A
+2)
4a log
| [6] 2n 2
2
+ π 2 arctan
3-0//0
2
(73)
1+ 1xexp-
482
1602
<
+ 1- +2)
4a log
2 16/+ 2n
2
|8| (T 2 arctan
2-8/00
2
(74)
1 1+exp-
482 + 1672
+ exp (-g +2)
4a log
200+001200 20
|8| (TT 2 2arctan
()))
2
< 1+ -+exp-
(75)
482 + 16o2
1 1 (-g
5 + 2)
4o log
30 20+161-20 20
|0| (π + 2arrrtan (é)
(76)
1xexp-
482 + 16
17

---

Under review as a conference paper at ICLR 2022
where Eq. (66) is because exp (-1) +exp v+2
4² and Eq. (74) is because π - arctan
2-810)
With probability (1 - e), we have
+ +eexpp
2 = log
2 log (1 - -c)
(77)
-
exp
+2 1
(78)
+ exp
1 c
Thus
4a log
20+-161+22
+ |6| (TT + 22 aarctan 2
1
f(0,0,2) s Eq. (76)
(79)
1-
482 + 166²
4o log
(a
+ |6| (π + arctan (6)
1
log(1
-r)
<
(80)
462
16o
Thus we have
40 log (a Ixs -r, +
log(1 (1-c) + 22 - xzح
T + 2 arctan
20
Eq. (54) S
(81)
(1 (4((x; - xz )2 1602)(1 + exp 2i (1 + exp
#x+1-R
In conclusion, with the probability (1 <). we have
(2 log mmT 44 log (a -0, ToRl
18,--x;1+22 +22 + | Tzy (T + Partaan
Eg
T - -
20
(1 - ()(4(r;; - 22, 2- + 160 exp Fe (1 + exp
*t+1 -t:
(82)
(log 2)mr log (a 12,-2,144 122
+ [4 - xzyl + arctan
Z1-2,
log(1 (-g(
20
(1-c)((1i - x2))² + 40 (1 + exp
2i-21 [1 + exp
#1-1-2
(83)
= (log mm
Σ M(xi,
(84)
And we denote Mxx, a, c) as
MI,,ZH,0,E) 20 log (
lm; 12,00 + [r; -2yl (3 arctan
z:-2,
log(1-e)
20
(85)
() - 32 20 exp 8.-22 (( exp
Zt+1 2z
Finally, Theorem 1 proved by triangle inequality jointly considering Lemma and Lemma 2.
A.3 REMARKS W.R.T. SOFT-TOPK
In the following, we add some remarks about the relationship between our conclusion of GS- TopK and the conclusion derived by the authors of SOFT-TopK (Xie et al., 2020): the SOFT-TopK is special case of our proposed algorithm when we set = 0. We have the following conclusion:
Theorem 2. Assume the values of Ik: Tx+1 are unique", under probability (1 c). we have
(x log 2)T
lim 0
E. |T T S (1-e) e) xk++1
(86)
'For the ease of a compact proof, we make this assumption that the values of I', #x+1 are unique. If there are duplicate values of Ts+1, the bound only differs by constant multipler therefore does not affect our conclusion: SOFT-TopK (Xic al., 2020) is special case of proposed approach when
18

---

Under review as a conference paper at ICLR 2022
Condition
Xk+1
Condition 2
X
Xk
Xk+1
Condition 3
Xi
X]
Xk
Xk+1
Condition 4
Xk
Xk++
Xj
Figure 4: Four conditions considered in our proof. is worth noting that 24, must not lie between
Tk. 1k+1, because define 1k++ two adjacent items in the original sorted list.
which differs from the conclusion in (Xie et al., 2020) by only a constant factor.
Proof. Since a 0+, the first term becomes 0. For the second term, discuss four conditions as shown in Fig. 4, except for the following condition: H; = TRi Iy Tk+1-
Condition If 24 2 The 2k+11 (equalities do hold the same time), we have least 2; Ik > 0 or Fk+1 Ij > 0. Then we have
lim -+ (1 + exp z1-8k (1 exp #k+1-2,
(87)
lim MZ,, 0,) =0
(88)
--0
Condition 2. For any case that x; < Ij, we have x; Ij < 0, thus
lim arctan - Iı --
π
(89)
2
Iy - Fj
lim arctan a a 2
(90)
lim 2f,,,,,000 --0
0,
(91)
Condition 3. If 2 x2 2 Fy (equalities do not hold at the same time), we have x; 2x > 0. Then we have
lim - + exp
3--21 0
(92)
lim 0Zi,, 0 --
(93)
Condition 4. F6++1 2 x4 2 x, (equalities do not hold at the same time), we have Ft+11 - x, > 0.
Then we have
lim o -
(94)
1 + exp #6t1-1
= lim 2(I,, 0. =
(95)
0-50
19

---

Under review as a conference paper at ICLR 2022
Therefore, if 2, Ia and Zj * 2x+1, the second term M22 o, degenerates to 0 when o + 0*. Thus we have the following conclusion by only considering 24 = 2k, Ijj = 2k+12
(log m) (IZz (1 (3 arctan #2 #
lim En T 0
[1
(96)
(1 (1-e) =1- - xx+1)²
(at log 2)mT
(97)
c)(2% 2k+1|
B IMPLEMENTATION DETAILS ON DISCRETE CLUSTERING PROBLEM
For the discrete clustering problem, recall that we aim select subset of objects as cluster centers. It differs from the k-means clustering problem whose cluster centers may not have to be subset of the objects, and the constraint for discrete clustering is more welcomed for real-world facility location planning applications. Denote E R R+ -+*mxm as the distance matrix for each pair of objects.
Following our implementation of the max covering problem, we can also derive GPU-friendly formulation of the discrete clustering problem using PyTorch syntax:
min sum sum (min( xx :], dim = 0)) s.t. x (0, ||=||0 S k
(98)
We also model the discrete clustering problem as a graph and encode the problem structure by graph neural network. Specifically, for points that lie on the 2D plane, we define there is an edge between two points their distance smaller than a predefined threshold. Then the geometric information is encoded by 3-layer SplineCNN (Fey et al., 2018) which was found successful for geometric feature learning. Similar to the max covering problem, we rewrite the fru-nriendly form of the objective score in a differentiable manner, being estimated by the output of Go-TopK algorithm:
J, cannssoftaax(TTAA_ :), dim keepdim True) @ A)
(99)
J mcan([ J2, J2..... Jwal)
where we use a softmax operator with temperature T to approximate the min operator in a differ- entiable way. @ means the tensor-product operator in PyTorch. The GS-TopK learning algorithm is summarized in Alg.3. 3.
C EXPERIMENT SETUP
Our algorithms are implemented by PyTorch and the graph neural network modules are based on (Fey & Lenssen, 2019). our paper. we optimize the hyperparameters by greedy search on a small subset of problem instances (~5) and set the best configuration of hyperparam- eters for both GS-TopK, SOFT-TopK. For the max covering problem, we empirically set learning rate 0.1,7 = 0.05, 0.15 for GS-TopK,
0.05 for SOFT-TopK, and (7, (0.05, 0.15), (0.04, 0.10), (0.03, 0.05) for Homotopy Go-TopK. For the discrete clustering problem, set learning rate 0.1, 0.05, 0.25 for To-To 5 0.05 for SOFT-TopK, and we set (T,o) = (0.05, 0.25), (0.04, 0.15), (0.03, 0.05) for Homotopy GS-TopK. We set #G = 1000 for max covering, #G 500 for discrete clustering. All experiments are done workstation with 17-9700K @ 3.60GHz, 16GB memory, and 2080Ti GPU.
D ABLATION STUDY ON HYPERPARAMETERS
Firstly, we want to add some remarks about the selection of hyperparameters:
# G (number of Gumbel samples): #G affects how many samples are taken during train- ing and inference for GS-TopK. A larger #G (i.e. more samples) will be more appealing.
20

---

Under review as a conference paper at ICLR 2022
Algorithm 3: Gumbel-Sinkhom--Topp Learning for Solving the Discrete Clustering Prob-
lem
Input:
the distance matrix A; learning rate a; softmax temperature T;; GS-TopK parameters
T, J, #G.
Training then
Randomly initialize neural network weights 8;
Inference then
Load pretrained neural network weights 0; Joest +00;
while not converged do
SplineCNNN (A); [T,, T2, Tua] Gs- o, for all i,
J. = sum (smfssftmax( - -TA dim keepdim True) + | [2::), = mean (J],,
Jsal):
if Training then
update with respect to the gradient 0. and learning rate by gradient descend; if Inference then update with respect to the gradient aJ and learning rate a by gradient descend; ds
00
11
12
for all i, J, (2. v; Jbest min([]1, J2, ... Jua], Jbest);
13
14 Homotopy Inference then
15
Decline the values of and jump to line 5;
Output: Learned network weights 9 (if training)/The best objective Jbest (if inference).
because GS-TopK will have a more accurate estimation of the objective score, and it will have higher probability of discovering better solutions. However, #G cannot be arbitrar- ily large because we are running GS-TopK in parallel on GPU, and the GPU has limited memory. Therefore, in experiments, we set a large enough #G (e.g. #G 1000) and ensure that it can fit into the GPU memory of our workstation (2080Ti, 11G).
(entropic regularization factor of Sinkhorn): Theoretically, controls the gap of the continuous Sinkhorn solution to the discrete solution, and a smaller 7 will lead to a tight- ened gap. This property is validated by our theoretical findings in Lemmal 2. Unfortunately, I cannot be arbitrarily small, because smaller T requires more Sinkhorn iterations to con- verge. Therefore, given fixed number of Sinkhorn iterations (100) to ensure the efficiency our algorithm, we need trial-and-error to discover the suitable т for both COFT-Toph and GS-TopK. The grid search results below show that our selection of fairly balances the performances of both SOFT-TopK and GS-Top..
(Gumbel noise factor): As derived in Theorem 1, we need to balance between the two gaps (Lemma 1 and Lemma by suitable a. Since |a 1ra-aa - is unknown, we cannot directly find the theoretically optimal given In the experiments, we firstly determine т. and then find suitable a by greedy search on a small subset (~~5) of problem instances.
We conduct an ablation study about the sensitivity of hyperparameters by performing an exten- sive grid search near the configuration used in our max covering experiments (r = 0.05, #G = 1000). We choose the k=50, m=500, n=1000 max covering problem, and we have the following results for GS-TopK (ours) and SOFT-TopK (Xie et al., 2020) (higher is better):
Table 3: Ablation study result of GS-TopK with #G 1000.
0.01
0.05
0.1
0.1
42513.4
44759.2
45039.5
0.15
41456.5
44713.2
44837.2
0.2
41264.3
44638.1
44748.2
21

---

Under review as a conference paper at ICLR 2022
Table 4: Ablation study result of GS-TopK with #G 800.
0.01
0.05
0.1
0.1
42511.6
44754.6
45037.6
0.15
41421.4
44705.8
4.841.5
0.2
41235.9
44651.5
44748.6
Table 5: Ablation study result of SOFT-TopK.
0.001
0.005
0.01
0.05
0.1
objective score
35956.6
42013.3
42520.8
41004.3
40721.2
Under the configuration used in our paper, both SOFT-TopK and GS-TopK have relatively good results. By grid search, we also discover better hyperparameters for both GS-TopK and SOFT- TopK, but is worth noting that SOFT-TopK still inferior to GS-TopK with the best-discovered hyperparameters. Our grid search result shows that our GS-TopK is not very sensitive to if we have - = 0.05 or 0.1, and the result of T 0.01 inferior because the Sinkhorn algorithm may not converge. The results of #G 1000 are all better than #G 800, suggesting that a larger #G is appealing if we have enough GPU memory. It is also discovered that SOFT-Tope TopK seems to be able to accept smaller value of compared to GS-TopK, probably because adding the Gumbel noise will increase the divergence of elements thus performs a sense similar to decreasing т when considering the convergence of Sinkhorn.
22


Reviews:
[{"review_id": "utnGL02nCRH", "reviewer": "Reviewer_fJUe", "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": "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.\n\n\n- 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.\n- 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.\n- 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)\n- 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.\n- 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.\n", "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.\n", "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. \n", "strength_and_weaknesses": "", "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": {}}, {"review_id": "o5JoDPZozed", "reviewer": "Reviewer_J7pw", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. \n\nThere are also other soft top-k operators. \nVery influential for the work by Xie et al. is the optimal transport based differentiable sorting and ranking (https://arxiv.org/abs/1905.11885).\nThere are also differentiable sorting networks, which provide differentiable sorting and ranking (https://arxiv.org/abs/2105.04019).\nBoth of these works include differentiable top-k operators and include experiments demonstrating their utility. \nI suggest adding and discussing these references and elaborating the choice of using the formulation of Xie et al. \n(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.)\n\nIn the toy example in Figure 1, there is not a unique solution of the top-k operation.\nTherefore: why is it beneficial that one specific solution is selected over a 50% / 50% mixture of both 0.6 entries?\nThe algorithm 2 would result in a 50% / 50% mixture for the two 0.6 entries. \nDifferentiable sorting networks for top-k achieve a 50% / 50% mixture without sampling.\nThis should be discussed.\n\nIn algorithm 3, there is a $T$ in line 7. The $ \\mathbf{\\tilde T}_i$s are not used, so maybe there is a typo? \n\nThe 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.\n\nIs 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?\n\nWhat 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.\n\nI did not check the validity of the theoretical results.\n\nI appreciate the application and experiments. However, I wonder how the hyper-parameters were selected. \nFrom 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.\nOptimizing only your hyperparameters would lead to a significant bias in the results. \nThere is no grid specified over which you perform grid search to give each method a fair chance.\nAt a time cost of seconds for each method, it should be very feasible to do even a quite extensive grid search. \n\n\n### TYPOs:\nOverall, 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.\n\np.2: and pipeline is differentiable -> and the / our pipeline is differentiable\n\np.2: taxonomy by (Peng et al., 2021) -> taxonomy by Peng et al. (2021)    (This TYPO is also at other locations, e.g., Inspired by\n(Jang et al., 2017),)\n\np.3: parametreization. \n\ngradient ascend -> gradient ascent\n\np.7 problems pf cardinality -> problems of cardinality\n\np.9 Directly applying Gumbel sampling to SOFT-TopK seems either an effective improvement, and satisfying\nresults are achieved when exploiting the Gumbel re-parameterization trick and enabling gradient-\nbased optimization over the combinatorial objective score.  (This sentence is grammatically incorrect, which makes it not understandable.)\n\nat various occasions, you write SOTF-TopK instead of SOFT-TopK", "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.\nThis improves theoretical guarantees for the case where the $k$th and the $k+1$th elements are equal.", "summary_of_the_review": "Overall, I see that the paper has theoretical strengths and presents an interesting application for the method.\nHowever, the methodological contribution is small.\nThe experimental evaluation is or seems to be flawed, as it is questionable whether the comparison is fair. \nGrammatically, the paper should be reworked. (which does not impact my score, as I expect this to be fixed in the final paper.)\n\nFor these reasons, I suggest rejecting this work in its current form. \n\nImproving 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. \nThe empirical evaluation should be more rigorous.\n\n---\n\nI appreciate the response and revision; however, I still have concerns as per my last response.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SC3k60uzxqI", "reviewer": "Reviewer_BoAG", "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": "## Strengths:\n- Strong experimental results with baselines that include other neural approaches as well as solvers and classical algorithms.\n- The paper builds on recent work from the literature.\n- The approach provides improved theoretical results for soft TopK through the use Gumbel noise.\n- The motivation and the explanation of the theoretical results are clear and well done.\n\n## Comments and weaknesses:\n- Minor corrections regarding related work.\nYou claim \"Besides, Paulus et al.\n(2020) develop a general framework for generating combinatorial distributions via Gumbel distribution.\" The work in Paulus et al. can use different\nkinds of noise in their optimization program, not just Gumbel.\nRegarding the work by Karalias and Loukas, you claim \"However, they do not consider the cardinality constraint (at least not\nexplicitly).\" 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.\n\n- Just below Equation 13, the optimal solution is denoted with a tilde. Is an asterisk missing there or am I misunderstanding something?\nThe notation is somewhat confusing at that point. The expectation on the lemma right below has T with both tilde and an asterisk but the \nsentence claims that the optimal is just tilde(T) (well, boldface T to be precise).\nMore generally, the text contains various typos that need to be fixed, for example:\npage 5: \"our aim becomes to proof the upper bound\"\npage 7: \"learning two representative problems pf cardinality\".\n\n\n- 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\nbecause 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\nend 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\nprovides an effective randomization technique that enables better performance? \n\n- 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 \nsampling to improve soft TopK as well, but it doesn't appear to be the case.\n\n- 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.\nFurthermore, 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.\n\n- How much does the number of samples affect performance? An ablation study on that would have been nice.\n", "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.", "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.\n\n", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "748XNpwcLmk", "reviewer": "Reviewer_mjiu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. \n\nStrengths: \n\n1. 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. \n\n2. Following the previous theoretical analyses in the literature, the authors provided the proofs of the derived bounds in the appendix. \n\n3. 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. \n\nWeaknesses: \n\n1. 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. \n\n2. 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? \n\n3. For real applications, will different $\\tau$ and $\\sigma$ change the performances significantly? \n\n4. 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? \n\n5. 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? \n\n6. 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. \n\n\n\n\n\n", "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. ", "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. ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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