Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions

Combining discrete probability distributions and combinatorial optimization\nproblems with neural network components has numerous applications but poses\nseveral challenges. We propose Implicit Maximum Likelihood Estimation (I-MLE),\na framework for end-to-end learning of models combining discrete exponential\nfamily distributions and differentiable neural components. I-MLE is widely\napplicable as it only requires the ability to compute the most probable states\nand does not rely on smooth relaxations. The framework encompasses several\napproaches such as perturbation-based implicit differentiation and recent\nmethods to differentiate through black-box combinatorial solvers. We introduce\na novel class of noise distributions for approximating marginals via\nperturb-and-MAP. Moreover, we show that I-MLE simplifies to maximum likelihood\nestimation when used in some recently studied learning settings that involve\ncombinatorial solvers. Experiments on several datasets suggest that I-MLE is\ncompetitive with and often outperforms existing approaches which rely on\nproblem-specific relaxations.\n