Gradient Estimation with Stochastic Softmax Tricks

Chris Maddison, Vector Institute and University of Toronto

Machine Learning Advances and Applications Seminar
http://www.fields.utoronto.ca/activit...

Abstract: Gradient estimation is an important problem in modern machine learning frameworks that rely heavily on gradient-based optimization. For gradient estimation in the presence of discrete random variables, the Gumbel-based relaxed gradient estimators are easy to implement and low variance, but the goal of scaling them comprehensively to large combinatorial distributions is still outstanding. Working within the perturbation model framework, we introduce stochastic softmax tricks, which generalize the Gumbel-Softmax trick to combinatorial spaces. Our framework is a unified perspective on existing relaxed estimators for perturbation models, and it contains many novel relaxations. We design structured relaxations for subset selection, spanning trees, arborescences, and others. We consider an application to helping make machine learning models more explainable.