Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
This work addresses the theoretical underpinnings of deep learning methods for combinatorial problems, offering insights for researchers in optimization and AI, though it is incremental in providing a formal analysis rather than a new paradigm.
The authors tackled the theoretical analysis of policy-gradient methods for combinatorial optimization by introducing a framework to assess whether generative models can produce near-optimal solutions with tractable parameters and benign optimization landscapes, and they provided a positive result for problems like Max-Cut and TSP, along with a regularization method to mitigate vanishing gradients.
Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network is used as a solution generator which is then trained by gradient-based methods (e.g., policy gradient) to successively obtain better solution distributions. In this work we introduce a novel theoretical framework for analyzing the effectiveness of such methods. We ask whether there exist generative models that (i) are expressive enough to generate approximately optimal solutions; (ii) have a tractable, i.e, polynomial in the size of the input, number of parameters; (iii) their optimization landscape is benign in the sense that it does not contain sub-optimal stationary points. Our main contribution is a positive answer to this question. Our result holds for a broad class of combinatorial problems including Max- and Min-Cut, Max-$k$-CSP, Maximum-Weight-Bipartite-Matching, and the Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla gradient descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.