Perturb-and-MAP offers an elegant approach to approximately sample from a energy-based model (EBM) by computing the maximum-a-posteriori (MAP) configuration of a perturbed version of the model. Sampling in turn enables learning. However, this line of research has been hindered by the general intractability of the MAP computation. In fact, very few works venture outside tractable models, and when they do, they use linear-programming approaches, which as we will show, have several limitations. In…