Combinatorial optimization is a common theme in computer science. While in general such problems are NP-Hard, from a practical point of view, locally optimal solutions can be useful. In some combinatorial problems however, it can be hard to define meaningful solution neighborhoods that connect large portions of the search space, thus hindering methods that search this space directly. We suggest to circumvent such cases by utilizing a policy gradient algorithm that transforms the problem to the continuous domain, and to optimize a new surrogate objective that renders the former as generic stochastic optimizer. This is achieved by producing a surrogate objective whose distribution is fixed and predetermined, thus removing the need to fine-tune various hyper-parameters in a case by case manner. Since we are interested in methods which can successfully recover locally optimal solutions, we use the problem of finding locally maximal cliques as a challenging experimental benchmark, and we report results on a large dataset of graphs that is designed to test clique finding algorithms. Notably, we show in this benchmark that fixing the distribution of the surrogate is key to consistently recovering locally optimal solutions, and that our surrogate objective leads to an algorithm that outperforms other methods we have tested in a number of measures.
## Summary ##
The authors apply policy gradients to combinatorial optimization problems. They suggest a surrogate reward function that mitigates the variance in the reward, and hence the update size. They demonstrate performance on a clique-finding problem.
## Assessment ##
I don't think Cakewalk is different enough from the cross-entropy method to warrant acceptance in ICLR. 
 I also have concerns about the independence assumption in their sampling distribution (Section 3.2), and the fact that their experiments use the same set of (untuned) hyperparameters for each method.
They both approximate the reward CDF from K samples and use this to construct a surrogate reward. The difference is that Cakewalk uses the CDF directly, while CE uses a threshold function on the CDF.
## Specific Comments and Questions ##
1. Cakewalk is *very* closely related to the cross-entropy method. The authors acknowledge this connection, but I think they should begin by introducing CE and then explain how Cakewalk generalizes it. Both Cakewalk and CE approximate the reward CDF from K samples and use this to construct a surrogate reward. The difference is that Cakewalk uses the CDF directly, while CE uses a threshold function on the CDF.
2. The distribution proposed in section 3.2 assumes independence between the elements $x_j$. This seems problematic for some relatively simple problems. Consider $x$ a binary vector and reward equal to the parity $S(x) = \sum{x_j} % 2$.
3. In the experiments, there are large discrepancies between different optimizers on Cakewalk (e.g. SGA vs AdaGrad, Table 4). Is there any explanation for this?
4. How were the hyperparameters (learning rate, AdaGrad $\delta$, Adam $\beta_1, \beta_2$) chosen? It seems like a large assumption that the same learning rate would work for different methods, especially when some of them are normalizing the objective function. I would suggest tuning these values for each method independently.
5. It would be nice to see experimental results on more than one problem. The authors discuss their results on k-medoids in the appendices, but it seems like these results aren't quite complete yet. 
6. In Table 3, the figure in bold is not the lowest (best) in the table. The reason for this is only given in a single sentence at the end of Section 6, so it is a little confusing. I would replace these values with N/A or something similar.