Skip to yearly menu bar Skip to main content


Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method

Constantine Caramanis · Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos

Room R02-R05 (level 2)
[ ] [ Livestream: Visit Oral 5C Probability/Sampling ]
Thu 14 Dec 8:30 a.m. — 8:45 a.m. PST

Abstract: 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.

Chat is not available.