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. Combinatorial optimization is one of the foundational problems of computer science. Though in general such problems are NP-hard BID20 , it is often the case that locally optimal solutions can be useful in practice. In clustering for example, a common objective is to divide a given set of examples into a fixed number of groups in a manner that would minimize the distances between group members. As enumerating all the possible groupings is usually intractable, local search methods such as k-means BID16 are frequently used to approach such problems. We find the persistent use of k-means in a wide variety of applications as convincing evidence that from a practical perspective, locally optimal solutions can be useful.In the combinatorial setting however, solution neighborhoods are not always available, and even when they are, in many interesting cases they only connect small parts of the search space. For example, when the search space involves computer programs, it is not clear how replacing one operation with another (for example, an if clause with an addition operation) impacts the program behavior even if the program validity is preserved. Though one can define a limited but sensible set of neighboring solutions (e.g., replace an addition with a multiplication), neighborhoods that build on those usually connect only a tiny fraction of the search space. Another interesting case involves natural language sentences where replacing one word with another (say, 'very' to 'not'), or changing clauses order can completely change the meaning of a sentence. A third popular scenario involves sequential decision making as is the case in reinforcement learning problems with discrete action spaces, where it is not always clear that two action sequences can be related if the initial actions are different. In such combinatorial problems, methods that transforms one solution to another (either directly or through smoothing) might be confined to a small sub-space, and therefore in such problems, searching the solution space directly is unfavorable.One type of algorithms which are suitable to such combinatorial problems, and have drawn considerable interest in the last few years are policy gradient methods BID25 . The general strategy these methods adopt is to construct a parametric sampling distribution over the search space, and to optimize the expected value of some given objective function by applying gradient updates in the parameters' space. In spite of their apparent generality, these gradient updates require special attention. In particular, the sampled objective values affect both the sign and the magnitude of the gradient step size. On the one hand, such dependence on the objective values is what allows these algorithms to give higher likelihood to examples which achieve better objective values. On the other hand, such direct dependence makes it hard to tune the step sizes by means of predetermined hyper-parameters. As our goal is to extend such constructions to any objective in a generic fashion, we seek to transform the construction so that it will only be sensitive to the order relation the objective induces. In this construction however, the objective is essentially a random variable whose distribution changes from one problem to another, and not only that, it keeps on changing throughout the optimization. As a result, it seems that finding a generic rule for tuning various hyper-parameters in a manner that fits all scenarios seems impractical.Following this understanding, we purpose to utilize a generic surrogate objective function that has the following two properties. First, the surrogate should preserve the set of locally optimal solutions if solution neighborhoods can be defined. Second, the surrogate should have a fixed and predetermined distribution for every possible objective, and this distribution should remain fixed throughout the optimization. Once in this form, generic rules for setting various hyper-parameters can be found, and that can provide us with a generic stochastic optimizer. Though it might seem that such general purpose surrogate objectives could be hard to find, we show that by utilizing the empirical cumulative distribution function (CDF henceforth) of the original objective, these can be easily constructed. We discuss few possible surrogate objectives, and purpose one such version which makes the basis our method. Since the crux of our method is based on capitalizing on the CDF of the original objective, we refer to our method as CAkEWaLK which stands for CumulAtivEly Weighted LiKelihood.We start by considering policy gradient methods as stochastic optimization algorithms for combinatorial problems in section 2, and proceed to present the Cakewalk method in section 3. In section 4 we discuss how Cakewalk is related to the cross-entropy (CE henceforth) method, to policy-gradient methods in reinforcement learning, and to multi-arm bandit algorithms. Since we are interested in methods that can recover locally optimal solutions when these can be defined, we use the problem of finding inclusion maximal cliques in undirected graphs as a controlled experiment for testing this property in a non-trivial setting. For that matter, in section 6 we investigate how to apply such methods to the clique problem, and in section 7 we report experimental results on a dataset of graphs on which results are regularly published. Lastly, as an additional experimental task, we show in appendix section B how Cakewalk can be used to produce an algorithm that outperforms the most commonly used algorithms for k-medoids clustering, the combinatorial counterpart of k-means. Notably, we use this task to demonstrate that Cakewalk can also be used to optimize the starting point of greedy algorithms that search the input space directly, thus providing empirical evidence that supports Cakewalk's effectivity in a greater variety of combinatorial problems. The results in tables 1 and 2 clearly support our main proposition that in the considered setting, a surrogate objective whose distribution is fixed and predetermined significantly improves the rate in which locally optimal solutions are recovered. Both CWŵ and OCE 0.1 rely on such surrogates, and both outperform Exp3 and all versions of REINFORCE which do not employ such surrogates. Interestingly, it appears that having a surrogate whose distribution is fixed is more effective than to normalize the objective values as the previous comparison also includes REINF Z . Nonetheless, not all distributions are as effective (OCE 0.01 and CWF didn't perform as well), and of the ones that we have tested, uniform on [−1, 1] seems to be favorable. CWŵ clearly outperforms OCE 0.1 in table 1, and the latter only comes close in the more permissive comparison which selects the best result out of 11 different executions (different values of κ) as reported in table 2. In terms of sample efficiency, the results in table 3 show that even though OCE 0.1 can recover locally optimal solutions, it is not as efficient as CWŵ which finds the best solution considerably faster. When considering the various gradient updates, it appears that CWŵ with AdaGrad produces the best combination as it outperforms all others methods in almost all measures (CWŵ with Adam converges slightly faster, though at the cost of worse optimality rates). Lastly, the comparisons to the best known results in table 4 show that the recovered solutions are far from trivial, and that Cakewalk might even approach the performance of problem specific algorithms which have access to a complete specification of the problem. Overall, we find these results are a strong indication that Cakewalk is a highly effective optimization method, and we believe that future research will prove its effectiveness in other domains such as continuous non-convex optimization, and in reinforcement learning problems. Following the analysis presented in section B.1, we conclude that combining Cakewalk with a greedy algorithm produces a clustering method that outperforms the two most commonly used algorithms for the k-medoids problem. Notably, here we combined Cakewalk with the Voronoi iteration, the weaker of the two in terms of performance, and that already produced a method that outperforms PAM. This suggests that probably combining Cakewalk with PAM can produce an even better clustering method, though we leave this to future research. Furthermore, it seems that applying Cakewalk without any greedy method already outperforms the Voronoi iteration, showing that vanilla Cakewalk can outperform some greedy algorithms as these might be limited by the neighborhood function they rely on, a limitation that doesn't apply to a sampling algorithm such as Cakewalk. In terms of function evaluations, it appears that PAM and Cakewalk perform about the same number of function evaluations (the difference is not statistically significant), and both perform more evaluations than the combination of Cakewalk+Voronoi. Taken together, these results not only show that combining Cakewalk with a greedy method can produce an optimizer that outperforms the components that make it up, it also leads to a combined algorithm that converges faster.
A new policy gradient algorithm designed to approach black-box combinatorial optimization problems. The algorithm relies only on function evaluations, and returns locally optimal solutions with high probability. The paper proposes an approach to construct surrogate objectives for the application of policy gradient methods to combinatorial optimization with the goal of reducing the need of hyper-parameter tuning. The paper propose to replace the reward term in the policy gradient algorithm with its centered empirical cumulative distribution. 