Computational Separations between Sampling and Optimization
  Two commonly arising computational tasks in Bayesian learning are
Optimization (Maximum A Posteriori estimation) and Sampling (from the posterior
distribution). In the convex case these two problems are efficiently reducible
to each other. Recent work (Ma et al. 2019) shows that in the non-convex case,
sampling can sometimes be provably faster. We present a simpler and stronger
separation. We then compare sampling and optimization in more detail and show
that they are provably incomparable: there are families of continuous functions
for which optimization is easy but sampling is NP-hard, and vice versa.
Further, we show function families that exhibit a sharp phase transition in the
computational complexity of sampling, as one varies the natural temperature
parameter. Our results draw on a connection to analogous separations in the
discrete setting which are well-studied.
