The Cakewalk Method
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.
 The authors argue that not knowing the distribution of rewards observed in the policy gradient algorithm hinders learning (and the tuning process). They propose to replace the reward term in the policy gradient algorithm with its centered empirical cumulative distribution, which has a fixed and known U[-1, 1] distribution. They test their methods on a toy task that consists in finding inclusion maximal cliques (which tests for local optimality) against REINFORCE (including their variants: centering the rewards with a mean baseline or normalizing them), the cross-entropy method and Exp3. I think that the current draft lacks strong experimental results to properly demonstrate the usefulness of the method. The method is only evaluated on a single task and many confounding variables (the design of the reward function, factorizing the parametric distribution into marginals, reporting results for a single (non-tuned?) learning rate, etc.) make evaluation difficult. The usefulness of the approach is also lessened by the greater importance of the choice of the optimizer. I would like the method to be applied on other domains such as continuous non-convex optimization and reinforcement learning. Additionally, I find the motivation for caring about local optimality unconvincing. I take exception that people care more about local optimality than the actual objective. From a practical point of view, local optimality is a mean (that can be achieved via heuristic algorithms) to an end (the objective itself). This also holds for k-means, which is usually run multiple times with different starting conditions. Some comments: - Table 3 is a bit confusing as-is (lower is only better when controlling on the quality of the best sample. e.g: REINFORCE has lower best-sample to total-sample ratio but its solutions are worse) - It isn*t clear from the tables that OCE_0.1 outperforms REINFORCE_Z (as is mentioned in the discussion). - The paper should refer to 1) the reward shaping literature, 2) the growing line of works concerned with control variates for REINFORCE (such as VIMCO, MuProp, REBAR) and 3) the growing line of works concerned about combinatorial optimization with reinforcement learning (Neural Combinatorial Optimization with Reinforcement Learning, etc.) - I would also encourage the authors to come up with a more descriptive name for the approach.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
The Cakewalk Method
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.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



 The authors argue that not knowing the distribution of rewards observed in the policy gradient algorithm hinders learning (and the tuning process). They propose to replace the reward term in the policy gradient algorithm with its centered empirical cumulative distribution, which has a fixed and known U[-1, 1] distribution. They test their methods on a toy task that consists in finding inclusion maximal cliques (which tests for local optimality) against REINFORCE (including their variants: centering the rewards with a mean baseline or normalizing them), the cross-entropy method and Exp3. I think that the current draft lacks strong experimental results to properly demonstrate the usefulness of the method. The method is only evaluated on a single task and many confounding variables (the design of the reward function, factorizing the parametric distribution into marginals, reporting results for a single (non-tuned?) learning rate, etc.) make evaluation difficult. The usefulness of the approach is also lessened by the greater importance of the choice of the optimizer. I would like the method to be applied on other domains such as continuous non-convex optimization and reinforcement learning. Additionally, I find the motivation for caring about local optimality unconvincing. I take exception that people care more about local optimality than the actual objective. From a practical point of view, local optimality is a mean (that can be achieved via heuristic algorithms) to an end (the objective itself). This also holds for k-means, which is usually run multiple times with different starting conditions. Some comments: - Table 3 is a bit confusing as-is (lower is only better when controlling on the quality of the best sample. e.g: REINFORCE has lower best-sample to total-sample ratio but its solutions are worse) - It isn*t clear from the tables that OCE_0.1 outperforms REINFORCE_Z (as is mentioned in the discussion). - The paper should refer to 1) the reward shaping literature, 2) the growing line of works concerned with control variates for REINFORCE (such as VIMCO, MuProp, REBAR) and 3) the growing line of works concerned about combinatorial optimization with reinforcement learning (Neural Combinatorial Optimization with Reinforcement Learning, etc.) - I would also encourage the authors to come up with a more descriptive name for the approach.
assistant
 The authors argue that not knowing the distribution of rewards observed in the policy gradient algorithm hinders learning (and the tuning process). They propose to replace the reward term in the policy gradient algorithm with its centered empirical cumulative distribution, which has a fixed and known U[-1, 1] distribution. They test their methods on a toy task that consists in finding inclusion maximal cliques (which tests for local optimality) against REINFORCE (including their variants: centering the rewards with a mean baseline or normalizing them), the cross-entropy method and Exp3. I think that the current draft lacks strong experimental results to properly demonstrate the usefulness of the method. The method is only evaluated on a single task and many confounding variables (the design of the reward function, factorizing the parametric distribution into marginals, reporting results for a single (non-tuned?) learning rate, etc.) make evaluation difficult. The usefulness of the approach is also lessened by the greater importance of the choice of the optimizer. I would like the method to be applied on other domains such as continuous non-convex optimization and reinforcement learning. Additionally, I find the motivation for caring about local optimality unconvincing. I take exception that people care more about local optimality than the actual objective. From a practical point of view, local optimality is a mean (that can be achieved via heuristic algorithms) to an end (the objective itself). This also holds for k-means, which is usually run multiple times with different starting conditions. Some comments: - Table 3 is a bit confusing as-is (lower is only better when controlling on the quality of the best sample. e.g: REINFORCE has lower best-sample to total-sample ratio but its solutions are worse) - It isn*t clear from the tables that OCE_0.1 outperforms REINFORCE_Z (as is mentioned in the discussion). - The paper should refer to 1) the reward shaping literature, 2) the growing line of works concerned with control variates for REINFORCE (such as VIMCO, MuProp, REBAR) and 3) the growing line of works concerned about combinatorial optimization with reinforcement learning (Neural Combinatorial Optimization with Reinforcement Learning, etc.) - I would also encourage the authors to come up with a more descriptive name for the approach.