Sample from a distribution on ${\mathcal{X}}$ that is $\eta$-close to $\mu^\star(\vx) \propto \exp(-f(\vx))$.

These problems arise naturally in machine learning settings. When $f$ is the negative log likelihood function of a posterior distribution, the optimization problem corresponds to the Maximum A Posteriori (MAP) estimate, whereas the Sampling problem gives us a sample from the posterior. In this work we are interested in the computational complexities of these tasks for specific families of functions. When $f$ and ${\mathcal{X}}$ are both convex, these two problems have a deep connection (see e.g. [@LovaszV06]) and are efficiently reducible to each other in a very general setting. There has been considerable interest in both these problems in the non-convex setting. Given that in practice, we are often able to practically optimize certain non-convex loss functions, it would be appealing to extend this equivalence beyond the convex case. If sampling could be reduced to optimization for our function of interest (e.g. differentiable Lipschitz functions), that might allow us to design sampling algorithms for the function that are usually efficient in practice. @MaCJFJ18 recently showed that in the case when $f$ is not necessarily convex (and ${\mathcal{X}}= \Re^d$), these problems are not equivalent. They exhibit a family 