\sim \pi}[\|\vx - \vx'\|_2]$, where the $\inf$ is taken over all couplings $\pi$ between $P$ and $Q$. We remark that our results are not sensitive to the choice of distance between distributions and extend in a straightforward way to other distances. As is common in literature on sampling from continuous distributions, we will for the most part assume that we can sample from a real-valued distribution such as a Gaussian and ignore bit-precision issues. Statements such as our NP-hardness results usually require finite precision arithmetic. This issue is discussed at length by [@ToshD19] and following them, we will discuss using Wasserstein distance in those settings. An $\eps$-optimizer of $f$ is a point $\vx \in {\mathcal{X}}$ such that $f(\vx) \leq f(\vx') + \eps$ for any $\vx' \in {\mathcal{X}}$.

In Appendix \[app:folklore\], we quantify the folklore results showing that sampling for high $\lambda$ implies approximate optimization. Quantitatively, they say that for $L$-Lipschitz functions over a ball of radius $R$, sampling implies $\eps$-approximate optimization if $\lambda \geq \Omega(d \ln \frac{LR}{\eps} / \eps)$. Similarly, for $\beta$-smooth functions over a ball of radius $R$, $\lambda \geq \Omega(d \ln \frac{\beta R}{\eps} / \eps)$ suffices to get $\eps$-close to an optimum.

A Simple separation {#sec:simple_sep}
===================

We 