Cakewalk Sampling
  We study the task of finding good local optima in combinatorial optimization
problems. Although combinatorial optimization is NP-hard in general, locally
optimal solutions are frequently used in practice. Local search methods however
typically converge to a limited set of optima that depend on their
initialization. Sampling methods on the other hand can access any valid
solution, and thus can be used either directly or alongside methods of the
former type as a way for finding good local optima. Since the effectiveness of
this strategy depends on the sampling distribution, we derive a robust learning
algorithm that adapts sampling distributions towards good local optima of
arbitrary objective functions. As a first use case, we empirically study the
efficiency in which sampling methods can recover locally maximal cliques in
undirected graphs. Not only do we show how our adaptive sampler outperforms
related methods, we also show how it can even approach the performance of
established clique algorithms. As a second use case, we consider how greedy
algorithms can be combined with our adaptive sampler, and we demonstrate how
this leads to superior performance in k-medoid clustering. Together, these
findings suggest that our adaptive sampler can provide an effective strategy to
combinatorial optimization problems that arise in practice.
