function. In other words, there are functions that can be optimized via gradient descent for which sampling is NP-hard. Conceptually, this separation is a result of the fact that finding one minimizer suffices for optimization whereas sampling intuitively requires finding [*all*]{} minima.

Both the separation result of [@MaCJFJ18], and our small-$\lambda$ result have the property that the sampling algorithm’s complexity increases exponentially in $poly(\lambda)$. Thus as we increase $\lambda$, the problem gradually becomes harder. [*Is there always a smooth transition in the complexity of sampling?*]{}

Our final result gives a surprising negative answer. We exhibit a family of easy-to-optimize functions for which there is a sharp threshold: there is a $\lambda_c$ such that for $\lambda < \lambda_c$, sampling can be done efficiently, whereas for $\lambda > \lambda_c$, sampling becomes NP-hard. In the process, this demonstrates that for some families of functions, efficient sampling algorithms can be very structure-dependent, and do not fall into the usual Langevin-dynamics, or rejection-sampling categories.

Our results show that once we go beyond the convex setting, the problems of sampling and optimization exhibit a rich set of computational behaviors. The connection to the discrete case should help further understand the complexities of these problems.

The rest 