Skip to yearly menu bar Skip to main content

Oral Poster

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

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

Great Hall & Hall B1+B2 (level 1) #1805
[ ]
Thu 14 Dec 8:45 a.m. PST — 10:45 a.m. PST
Oral presentation: Oral 5C Probability/Sampling
Thu 14 Dec 8 a.m. PST — 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.