---
abstract: '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 [@MaCJFJ18] 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.'
author:
- |
    Kunal Talwar\
    Google Brain\
    Mountain View, CA\
    `kunal@google.com`\
bibliography:
- 'refs.bib'
title: Computational Separations between Sampling and Optimization
---

Introduction
============

Given a a compact set ${\mathcal{X}}\subseteq \Re^d$ and function $f : {\mathcal{X}}\rightarrow \Re$, one can define two natural problems:

Optimize($f, {\mathcal{X}}, \eps$)

:   : Find $\vx \in {\mathcal{X}}$ such that $f(\vx) \leq f(\vx') + \eps$ for all $\vx' \in {\mathcal{X}}$.

Sample($f, {\mathcal{X}}, \eta$)

:   : 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 of continuous, differentiable functions for which approximate sampling can be done efficiently, but where approximate optimization requires exponential time (in an oracle model [*à la*]{} @NemiroskiY). In this work, we study the relationship of these two problems in more detail.

To aid the discussion, it will be convenient to consider a more general sampling problem where we want to sample with probability proportional to $\exp(-\lambda f(\vx))$ for a parameter $\lambda>0$. Such a scaling has no effect on the optimization problem, up to scaling of $\eps$. However changing $\lambda$ can signifcantly change the distribution for the sampling problem. In statistical physics literature, this parameter is the inverse temperature. For families ${\ensuremath{\mathcal{F}}}$ that are invariant to multiplication by a positive scalar (such as the family of convex functions), this $\lambda$ parameter has no impact on the complexity of sampling from the family. We will however be looking at families of functions that are controlled in some way (e.g. bounded, Lipschitz, or Smooth) and do not enjoy such an invariance to scale. E.g. in some Bayesian settings, each sample may give us a $1$-smooth negative log likelihood function, so we may want to consider the family $\mathcal{F}_{smooth}$ of $1$-smooth functions. Given $n$ i.i.d. samples, the posterior log likelihood would be $-n \overline{f}$, where $\overline{f}=\frac{1}{n} \sum_i f_i$ is in $\mathcal{F}_{smooth}$. The parameter $\lambda$ then corresponds naturally to the number of samples $n$.

This phenomenon of sampling being easier than optimization is primarily a “high temperature” or “low signal” phenomenon. As $\lambda$ approaches infinity, the distribution $\exp(-\lambda f)$ approaches a point mass at the minimizer of $f$. This connection goes back to at least [@KirkpatrickGV83] and one can easily derive a quantitative finite-$\lambda$ version of this statement for many function families. @MaCJFJ18 reconcile this with their separation by pointing out that their sampling algorithm becomes inefficient as $\lambda$ increases.

We first show a more elementary and stronger separation. We give a simple family of continuous Lipschitz functions which are efficiently samplable but hard even to approximately optimize. This improves on the separation in @MaCJFJ18 since our sampler is exact (modulo representation issues), and much simpler. The hardness of optimization here is in the oracle model, where the complexity is measured in terms of number of point evaluations of the function or its gradients.

While these oracle model separations rule out black-box optimization, they leave open the possibility of efficient algorithms that access the function in a different way. We next show that this hardness can be strengthened to an NP-hardness for an efficiently computable $f$. This allows for the implementation of any oracle for $f$ or its derivatives. Thus assuming the Exponential Time Hypothesis [@ImpagliazzoP01], our result implies the oracle model lower bounds. Additionally, it rules out efficient non-blackbox algorithms that could examine the implementation of $f$ beyond point evaluations. We leave open the question of whether other oracle lower bounds [@NemiroskiY; @Nesterov14; @Bubeck15; @Hazan16] in optimization can be strengthened to NP-hardness results.

We next look at the large $\lambda$ case. As discussed above, for large enough $\lambda$ sampling must be hard if optimization is. [*Is hardness of optimization the only obstruction to efficient sampling?*]{} We answer this question in the negative. We exhibit a family of functions for which optimization is easy, but where sampling is NP-hard for large enough $\lambda$. We draw on extensive work on the discrete analogs of these questions, where $f$ is simple (e.g. linear) but ${\mathcal{X}}$ is a discrete set.

Our upper bound on optimization for this family can be strengthened to work under weaker models of access to the function, where we only have blackbox access to the 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 of the paper is organized as follows. We start with some preliminaries in Section \[sec:prelims\]. We give a simple separation between optimization and sampling in Section \[sec:simple\_sep\] and derive a computational version of this separation. Section \[sec:discrete\_to\_cont\] relates the discrete sampling/optimization problems on the hypercube to their continuous counterparts, and uses this connection to derive NP-hardness results for sampling for function families where optimization is easy. In Section \[sec:sharp\_threshold\], we prove the sharp threshold for $\lambda$. We describe additional related work in Section \[sec:related\]. Some missing proofs and strengthenings of our results are deferred to the Appendix.

Preliminaries {#sec:prelims}
=============

We consider real-valued functions $f : \Re^d \rightarrow  \Re$. We will be restricting ourselves to functions that are continuous and bounded. We say a function $f$ is $L$-Lipschitz if $f(\vx) - f(\vx') \leq L \cdot \|\vx - \vx'\|$ for all $\vx, \vx' \in \Re^d$. In this work, $\|\cdot\|$ will denote the Euclidean norm.

We will look at specific families of functions which have compact representations, and ask questions about efficiency of optimization and sampling. We will think of $d$ as a parameter, and look at function families such that at any function in the family can be computed in $poly(d)$ time and space.

We will look at constrained optimization in this work and our constraint set ${\mathcal{X}}$ will be a Euclidean ball. Our hardness results however do not stem from the constraint set, and nearly all of our results can be extended easily to the unconstrained case.

Given $\lambda >0$ and a function $f$, we let ${{\mathcal{D}}_f^{\lambda, {\mathcal{X}}}}$ denote the distribution on ${\mathcal{X}}$ with $\Pr[\vx] \propto \exp(-\lambda f(\vx))$. When ${\mathcal{X}}$ is obvious from context, we will usually omit it and write ${{\mathcal{D}}_f^{\lambda}}$. We will $Z_f^{\lambda, {\mathcal{X}}}$ for the [*partition function*]{} $\int_{{\mathcal{X}}} \exp(-\lambda f(\vx)) {\mathrm{d}}\vx$.

We will also look at real-valued functions $h : {\mathbb{H}_{d}} \rightarrow \Re$, where ${\mathbb{H}_{d}} = \{-1, 1\}^d$ is the $d$-dimensional hypercube. We will often think of a $\vy \in {\mathbb{H}_{d}}$ as being contained in $\Re^d$. Analagous to the Euclidean space case, we define ${\mathcal{D}}_{h}^{\lambda,{\mathbb{H}_{d}}}$ as the distribution over the hypercube with $\Pr[\vy] \propto \exp(-\lambda h(\vy))$, and define $Z_{h}^{\lambda,{\mathbb{H}_{d}}}$ to be $\sum_{\vy \in {\mathbb{H}_{d}}} \exp(-\lambda h(\vy))$.

We say that an algorithm $\eta$-samples from ${{\mathcal{D}}_f^{\lambda}}$ if it samples from a distribution that is $\eta$-close to ${{\mathcal{D}}_f^{\lambda}}$ in statistical distance. We will also use the [*Wasserstein*]{} distance between distributions on $\Re^d$, defined as $\mathcal{W}(P, Q) \stackrel{eq}= \inf_{\pi} \Ex_{(\vx, \vx') \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 consider the case when ${\mathcal{X}}= B_d(\mathbf{0}, 1)$ is the unit norm Euclidean ball in $d$ dimensions. We let $\mathcal{F}_{Lip}$ be the family of all $1$-lipschitz functions from ${\mathcal{X}}$ to $\Re$. We show that for any $f \in \mathcal{F}_{Lip}$, exact sampling can be done in time $\exp(O(\lambda))$. On the other hand, for any algorithm, there is an $f \in\mathcal{F}_{Lip}$ that forces the algorithm to use $\Omega(\lambda/\eps)^d$ queries to $f$ to get an $\eps$-approximate optimal solution. Thus, e.g., for constant $\lambda$, sampling can be done in $poly(d)$ time, whereas optimization requires time exponential in the dimension. Moreover, for any $\lambda \leq d$, there is an exponential gap between the complexities of these two problems. Our lower bound proof is similar to the analagous claim in [@MaCJFJ18], but has better parameters due to the simpler setting. Our upper bound proof is signifantly simpler and gives an exact sampler.

There is an algorithm that for any $f \in \mathcal{F}_{Lip}$, outputs a sample from ${{\mathcal{D}}_f^{\lambda}}$ and makes an expected $O(\exp(2\lambda))$ oracle calls to computing $f$.

The algorithm is based on rejection sampling. We first compute $f(\mathbf{0})$ and let $M = f(\mathbf{0}) - 1$. By the Lipschitzness assumption, $f(\vx) \in  [M, M+2]$ for all $\vx$ in the unit ball. The algorithm now repeatedly samples a random point $\vx$ from the unit ball. With probability $\exp(\lambda(M-f(\vx)))$, this point is accepted and we output it. Otherwise we continue.

Since $\exp(\lambda(M-f(\vx))) \in [\exp(-2\lambda), 1]$, this is a rejection sampling algorithm, and it outputs an exact sample from ${{\mathcal{D}}_f^{\lambda}}$. Each step accepts with probability at least $\exp(-\lambda)$. Thus the algorithm terminates in an expected $O(\exp(2\lambda))$ many steps, each of which requires one evaluation of $f$.

The above algorithm assumes access to an oracle to sample from $B_d(\mathbf{0}, 1)$ to arbitrary precision. This can be replaced by sampling from a grid of finite precision points in the ball. This creates two sources of error. Firstly, the function is not constant in the grid cell. This error is easily bounded since $f$ is Lipschitz. Secondly, some grid cells may cross the boundary of $B_d(\mathbf{0}, 1)$. This is a probability $d 2^{-b}$ event when sampling a grid point with $b$ bits of precision. Taking these errors into account gives us a sample within Wasserstein distance at most $O((d+\lambda) 2^{-b})$.

The above is a Las Vegas algorithm. One can similarly derive a Monte Carlo algorithm by aborting and outputting a random $\vx$ after $\exp(2\lambda) \log \frac 1 \eta$ steps.

Under the assumptions in [@MaCJFJ18] ($\beta$-smooth $f$, $\nabla(\mathbf{0})=\mathbf{0}$, $\kappa\beta$-strong convexity outside a ball of radius $R$), a direct reduction to our setting will be lossy and a rejection-sampling-based approach will not be efficient. The Langevin dynamics based sampler in that work is more efficient under their assumptions.

\[thm:no\_fast\_opt\] For any algorithm ${\mathcal{A}}$ that queries $f$ or any of its derivatives at less than $(1/4\eps)^d$ points, there is an $f \in \mathcal{F}_{Lip}$ for which ${\mathcal{A}}$ fails to output an $\eps$-optimizer of $f$ except with negligible probability.

Consider the function $f_{\vx}$ that is zero everywhere, except for a small ball of radius $2\eps$ around $\vx$, where it is $f(\vy) = \|\vy - \vx\| - 2\eps$. i.e. the function[^1] is $f_{\vx}(\vy) = \min(0, \|\vy - \vx\| - 2\eps)$. This function has optimum $-2\eps$. Let $g$ be the zero function.

Let ${\mathcal{A}}$ be an algorithm (possibly randomized) that queries $f$ or its derivatives at $T \leq (1/4\eps)^d$ points. Consider running ${\mathcal{A}}$ on a function $f$ chosen randomly as: $$\begin{aligned}
    f &= \left\{ \begin{array}{ll}
    g & \mbox{ with probability $\frac 1 2$}\\
    f_{\vx} & \mbox{ for a $\vx$ chosen u.a.r. from $B(\mathbf{0}, 1)$ otherwise.}\\
  \end{array}\right.
    \end{aligned}$$ Until ${\mathcal{A}}$ has queried a point in $B(\vx, 2\eps)$, the behavior of the algorithm on $f_{\vx}$ and $g$ is identical, since the functions and all their derivatives agree outside this ball. Since an $\eps$-approximation must distinguish these two cases, for ${\mathcal{A}}$ to succeed, it must query this ball. The probability that ${\mathcal{A}}$ queries in this ball in any given step is at most $\frac{{\mathrm{vol}}(B(\vx, 2\eps))}{{\mathrm{vol}}(B(\mathbf{0}, 1))} = (2\eps)^d$. As ${\mathcal{A}}$ makes only $(1/4\eps)^d$ queries in total, the expected number of queries ${\mathcal{A}}$ makes to the ball $B(\vx, 2\eps)$ is at most $2^{-d}$. Thus with probability at least $1 - \frac{1}{2^d}$, the algorithm fails to distinguish $g$ from $f_\vx$, and hence cannot succeed.

Making the Separation Computational
-----------------------------------

The oracle-hardness of Theorem \[thm:no\_fast\_opt\] stems from possibly “hiding” a minimizer $\vx$ of $f$. The computational version of this hardness result will instead possibly hide an appropriate encoding of a satisfying assignment to a 3SAT formula.

There is a constant $\eps > 0$ such that it is NP-hard to $\eps$-optimize an efficiently computable Lipschitz function over the unit ball.

Let $\phi : \{0, 1\}^d \rightarrow {B_d(\mathbf{0}, 1)}$ be a map such that $\phi$ is efficiently computable, $\|\phi(\vy) - \phi(\vy')\| \geq 4\eps$ and such that given $\vx \in {B_d(\phi(\vy), 2\eps)}$, we can efficiently recover $\vy$. For a small enough absolute constant $\eps$, such maps can be easily constructed using error correcting codes and we defer details to Appendix \[app:eccs\].

We start with an an instance $I$ of 3SAT on $d$ variables, and define $f$ as follows. Given a point $\vx$, we first find a $\vy \in \{0, 1\}^d$, if any, such that $\vx \in {B_d(\phi(\vy), 2\eps)}$. If no such $\vy$ exists, $f(\vx)$ is set to $0$. If such a $\vy$ exists, we interpret it as an assignment to the variables in the 3SAT instance $I$ and set $f(\vx)$ to be $\min(0, \|\phi(\vy) - \vx\| - 2\eps)$ if $\vy$ is a satisfying assignment to instance $I$, and to $0$ otherwise.

It is clear from definition that $f$ as defined is efficiently computable. Moreover, the minimum attained value for $f$ is $-2\eps$ if $I$ is satsifiable, and $0$ otherwise. Since distinguishing between these two cases is NP-hard, so is $\eps$-optimization of $f$.

We note that assuming the exponential time hypothesis, this implies the $\exp(\Omega(d))$ oracle complexity lower bound of Theorem \[thm:no\_fast\_opt\].

Relating Discrete and Continuous Settings {#sec:discrete_to_cont}
=========================================

For any function $h$ on the hypercube, we can construct a function on $f$ on $\Re^d$ such that optimization of $f$ and $h$ are reducible to each other, and similarly sampling from $f$ and $h$ are reducible to each other. This would allow us to use separation results for the hypercube case to establish analagous separation results for the continuous case.

![image](figures/function_h.pdf){width=".48\textwidth"} ![image](figures/function_f.pdf){width=".48\textwidth"}

\[thm:discrete\_to\_cont\_v1\] Let $h : {\mathbb{H}_{d}} \rightarrow \Re$ have range $[0, d]$. Fix $M \geq 2d, R \geq 2\sqrt{d}$. Then there is a funtion $f : {B_d(0, R)}\rightarrow \Re$ satisfying the following properties:

Efficiency:

:   Given $\vx \in {B_d(0, R)}$ and oracle access to $h$, $f$ can computed in polynomial time.

Lipschitzness:

:   $f$ is continuous and $L$-Lipschitz for $L= 2M$.

Sampler Equivalence:

:   Fix $\lambda \geq \frac{4d \ln 24R}{M}$. Given access to an $\eta$-sampler for ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$, there is an efficient $\eta'$-sampler for ${{\mathcal{D}}_f^{\lambda}}$, for $\eta' = \eta + \exp(-\Omega(d))$. Conversely, given access to an $\eta$-sampler for ${{\mathcal{D}}_f^{\lambda}}$, there is an efficient $\eta'$-sampler for ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$ for $\eta' = \eta + \exp(-\Omega(d))$.

The function $f$ is fairly natural: it takes a large value $M \geq 2d$ at most points, except in small balls around the hypercube vertices. At each hypercube vertex, $f$ is equal to the $h$ value at the vertex, and we interpolate linearly in a small ball. See Figure \[fig:functions\_h\_f\] for an illustration.

Formally, let ${\texttt{round}}: \Re \rightarrow \{-1, 1\}$ be the function that takes the value $1$ for $x \geq 0$ and $-1$ otherwise, and let ${\texttt{round}}: \Re^d \rightarrow {\mathbb{H}_{d}}$ be its natural vectorized form that applies the function coordinate-wise. Let $g(\vx) = \|\vx - {\texttt{round}}(\vx)\|$ denote the Euclidean distance from $\vx$ to ${\texttt{round}}(\vx)$. Let ${s}= 2M$. The function $f$ is defined as follows: $$\begin{aligned}
    f(\vx) &= \left\{\begin{array}{ll}
                                                  h({\texttt{round}}(\vx)) + {s}\cdot g(\vx) & \mbox{ if }  g(\vx) \leq \frac{M - h({\texttt{round}}(\vx))}{{s}}\\
                          M & \mbox{ if } g(\vx) \geq \frac{M - h({\texttt{round}}(\vx))}{{s}}\\
                     \end{array}
              \right.
  \end{aligned}$$ It is easy to verify that $f$ is continuous. Moreover, since $M \geq 2d$, and $h$ has range $[0,d]$, the value $\frac{M - h({\texttt{round}}(\vx))}{{s}}$ is in the range $[\frac 1 4, \frac 1 2]$. It follows that $f$ takes the value $M$ outside balls of radius $\frac 1 2$ around the hypercube vertices, and is strictly smaller than $M$ in balls for radius $\frac 1 4$.

Since ${\texttt{round}}(\vx)$ is easy to compute, this implies that $f$ can be computed in polynomial time, using a single oracle call to $h$. Moreover it is immediate from the definition that the function $f$ has Lipschitz constant $s$.

Note that $f(\vy) = h(\vy)$ for $\vy \in {\mathbb{H}_{d}}$ and $f(\vx) \geq h({\texttt{round}}(\vx))$ for all $\vx \in {B_d(0, R)}$. This implies that the minimum value of $f$ is the same as the minimum value of $h$, and indeed any ($\eps$-)minimizer $\vy$ of $h$ also ($\eps$-)minimizes $f$. Conversely, let $\vx$ be an $\eps$-minimizer of $f$. Since $h({\texttt{round}}(\vx)) \leq f(\vx)$, it follows that ${\texttt{round}}(\vx)$ is an $\eps$-minimizer of $h$.

Finally we prove the equivalence of approximate sampling. Towards that goal, we define an intermediate distribution on ${B_d(0, R)}$. Let $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ be the distribution ${{\mathcal{D}}_f^{\lambda}}$ conditioned on being in $\cup_{\vy \in {\mathbb{H}_{d}}} {B_d(\vy, \frac 1 4)}$.

We first argue that $\eta$-samplability of $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ is equivalent to $\eta$-samplability of ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$. Suppose that $X$ is a sample from $\widehat{{{\mathcal{D}}_f^{\lambda}}}$. Then for any $\vy^\star \in {\mathbb{H}_{d}}$, $$\begin{aligned}
\Pr[X \in {B_d(\vy^\star, \frac 1 4)}] &= \frac{\int_{{B_d(\vy^\star, \frac 1 4)}} \exp(-\lambda f(\vx))\;{\mathrm{d}}\vx}{ \sum_{\vy \in {\mathbb{H}_{d}}}\int_{{B_d(\vy, \frac 1 4)}} \exp(-\lambda f(\vx))\;{\mathrm{d}}\vx}\\
&= \frac{\exp(-\lambda h(\vy^\star)) \cdot \int_{{B_d(\vy^\star, \frac 1 4)}} \exp(-{s}\lambda g(\vx)) \;{\mathrm{d}}\vx}{\sum_{\vy \in {\mathbb{H}_{d}}} \exp(-\lambda h(\vy)) \cdot \int_{{B_d(\vy, \frac 1 4)}} \exp(-{s}\lambda g(\vx)) \;{\mathrm{d}}\vx}\\
&= \frac{\exp(-\lambda h(\vy^\star))}{\sum_{\vy \in {\mathbb{H}_{d}}}\exp(-\lambda h(\vy))}\end{aligned}$$ Thus ${\texttt{round}}(X)$ is a sample from ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$. Conversely, the same calculation implies that given a sample $Y$ from ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$, and a vector $Z \in {B_d(\mathbf{0}, \frac 1 4)}$ sampled proportional to $\exp(-s\lambda \|\vz\|)$, $Y + Z$ is a sample from $\widehat{{{\mathcal{D}}_f^{\lambda}}}$. Noting that $Z$ is a sample from a efficiently sample-able log-concave distribution completes the equivalence.

We next argue that ${{\mathcal{D}}_f^{\lambda}}$ and $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ are $\exp(-\Omega(d))$-close as distributions. Since $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ is a conditioning of ${{\mathcal{D}}_f^{\lambda}}$, this is equivalent to showing that nearly all of the mass of ${{\mathcal{D}}_f^{\lambda}}$ lies in $\cup_{\vy \in {\mathbb{H}_{d}}} {B_d(\vy, \frac 1 4)}$. We write $$\begin{aligned}
  Z_{\lambda}^f &= \int_{{B_d(0, R)}} \exp(-\lambda f(\vx)) \;{\mathrm{d}}\vx\nonumber\\
  &\geq \sum_{\vy \in {\mathbb{H}_{d}}} \int_{{B_d(\vy, \frac 1 4)}} \exp(-\lambda f(\vx)) \;{\mathrm{d}}\vx \nonumber\\
  &= \sum_{\vy \in {\mathbb{H}_{d}}} \exp(-\lambda h(\vy)) \cdot \int_{{B_d(\vy, \frac 1 4)}} \exp(-{s}\lambda g(\vx)) \;{\mathrm{d}}\vx\nonumber\\\end{aligned}$$ Let $\widehat{Z_{\lambda}^f}$ denote this last expression. We will argue that $Z_{\lambda}^f \leq (1+\exp(-\Omega(d)))\widehat{Z_{\lambda}^f}$. We write $Z_{\lambda}^f$ as $$\begin{aligned}
  \int_{{B_d(0, R)}} \exp(-\lambda f(\vx)) \;{\mathrm{d}}\vx
  &\leq \sum_{\vy \in {\mathbb{H}_{d}}} \int_{{B_d(\vy, \frac 1 2)}} \exp(-\lambda f(\vx)) \;{\mathrm{d}}\vx + \int_{{B_d(0, R)}} \exp(-\lambda M) \;{\mathrm{d}}\vx \\
    &\leq \underbrace{\sum_{\vy \in {\mathbb{H}_{d}}} \exp(-\lambda h(\vy))\cdot \int_{{{B_d(\vy, \frac 1 2)}}} \exp(-{s}\lambda g(\vx)) \;{\mathrm{d}}\vx}_{\text{(A)}} + \underbrace{\int_{{B_d(0, R)}} \exp(-\lambda M) \;{\mathrm{d}}\vx}_{\text{(B)}} \\\end{aligned}$$ A simple calculation, formalized as Lemma \[lem:incomplete\_gamma\] in Appendix \[app:incomplete\_gamma\] shows that the integral $\int_{{{B_d(\vy, \frac 1 2)}}} \exp(-{s}\lambda g(\vx))\;{\mathrm{d}}\vx$ is within $(1+ 2\exp(-d))$ of $\int_{{{B_d(\vy, \frac 1 4)}}} \exp(-{s}\lambda g(\vx))\;{\mathrm{d}}\vx$ for ${s}\lambda > 16d$. This implies that the term $(A)$ above is at most $(1+2\exp(-d))\widehat{Z_{\lambda}^f}$. To bound the second term $(B)$ above, we argue that a ball of radius $\frac 1 8$ around any single vertex $\vy$ of the hypercube contributes significantly more than than the term $(B)$. Indeed $$\begin{aligned}
  \int_{{B_d(\vy, \frac 1 8)}} \exp(-\lambda f(\vx)) \;{\mathrm{d}}\vx &\geq \int_{{B_d(\vy, \frac 1 8)}} \exp(-\lambda (h(\vy) + \frac{{s}}{8})) \;{\mathrm{d}}\vx\\
  &\geq \exp(-\lambda (d+\frac{M}{4})) \cdot (\frac 1 8)^d \int_{{B_d(\mathbf{0}, 1)}} \;{\mathrm{d}}\vx
  &\geq \exp(-\lambda (\frac{3M}{4})) \cdot (\frac 1 8)^d \int_{{B_d(\mathbf{0}, 1)}} \;{\mathrm{d}}\vx\end{aligned}$$ Whereas, $$\begin{aligned}
  \int_{{B_d(0, R)}} \exp(-\lambda M) \;{\mathrm{d}}\vx &= \exp(-\lambda M) \cdot R^d \cdot \int_{{B_d(\mathbf{0}, 1)}} \;{\mathrm{d}}\vx.\end{aligned}$$ Thus $(B)/\widehat{Z_{\lambda}^f}$ is at most $\exp(-\lambda M/4 + d \ln 8R)$. Under the assumptions on $\lambda$, it follows that (B) is at most $\exp(-\Omega(d))$ times $\widehat{Z_\lambda^h}$. In other words, we have shown that $Z_{\lambda}^f$ is at most $(1+\exp(-\Omega(d))) \widehat{Z_{\lambda}^h}$.

\[rem:sampling\_wasserstein\] The equivalence of sampling extends immediately to Wasserstein distance. Indeed given a sampler for ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$, one gets a Wasserstein sampler for $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ by sampling from a simple isotropic log-concave distribution. A Wasserstein sampler for a ball suffices for this. Since $\mathcal{W}(P, Q)$ is bounded by the diameter times the statistical distance, this gives a $\eta + \exp(-\Omega(d))$ Wasserstein sampler for ${{\mathcal{D}}_f^{\lambda}}$. Similarly, a $\eta$ Wasserstein sampler for ${{\mathcal{D}}_f^{\lambda}}$ conditioned on the support of $\widehat{{{\mathcal{D}}_f^{\lambda}}}$ immediately yields an $O(\eta)$-sampler for ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$. Moreover, it is easy to check that this conditioning is on a constant probability event as long as $\eta < \frac 1 {16}$.

Optimization can be Easier than Sampling
----------------------------------------

Given the reduction from the previous section, there are many options for a starting discrete problem to apply the reduction. We will start from one of the most celebrated NP-hard problems. The NP-hardness of Hamiltonian Cycle dates back to @Karp72.

\[thm:hamcycle\_hardness\] Given a constant-degree graph $G = (V, E)$, it is NP-hard to distinguish the following two cases.

[Yes]{} Case:

:   $G$ has a Hamiltonian Cycle.

[No]{} Case:

:   $G$ has no Hamiltonian Cycle.

We can then amplify the gap between the number of long cycles in the two cases.

\[thm:count\_gap\_amplification\] Given a constant-degree graph $G = (V, E)$ and for $L= |V|/2$, it is NP-hard to distinguish the following two cases.

[Yes]{} Case:

:   $G$ has at least $1 + 2^{L}$ simple cycles of length $L$.

[No]{} Case:

:   $G$ has exactly one simple cycle $C^{(planted)}$ of length $L$, and no longer simple cycle.

Moreover, $C^{(planted)}$ can be efficiently found in polynomial time.

The proof of the above uses a simple extension of a relatively standard reduction (see e.g. @Vadhan02) from Hamiltonian Cycle. Starting with an instance $G_1$ of Hamiltonian Cycle, we replace each edge by a two-connected path of length $t$, for some integer $t$. For $L=nt$, this gives us $2^{L}$ cycles of length $L$ for every Hamiltonian cycle in $G_1$. Moreover, any simple cycle of length $L$ must correspond to a Hamiltonian Cycle in $G_1$. We add to $G$ a simple cycle of length $L$ on a separate set of $L$ vertices. This “planted” cycle is easy to find, since it forms its own connected component of size $L$. A full proof is deferred to Appendix \[app:count\_gap\_amplification\].

Armed with these, we form a function on the hypercube in $d = |E'|$ dimensions such that optimizing it is easy, but sampling is hard.

\[thm:cycle\_h\] There exists a function $h : {\mathbb{H}_{d}} \rightarrow [0, d]$ satisfying the following properties.

Efficiency:

:   $h$ can be computed efficiently on ${\mathbb{H}_{d}}$.

Easy Optimization:

:   One can efficiently find a particular minimizer $\vy^{(planted)}$ of $h$ on ${\mathbb{H}_{d}}$.

Sampling is hard:

:   Let $\lambda \geq 2d$. It is NP-hard to distinguish the following two cases, for $L = \Omega(d)$:

    [Yes]{} Case:

    :   $\Pr_{\vy \sim {\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}}[\vy = \vy^{(planted)}] \leq \frac 1 {2^L}$

    [No]{} Case:

    :   $\Pr_{\vy \sim {\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}}[\vy = \vy^{(planted)}] \geq 1 - \frac 1 {2^L}$

    In particular this implies that $1-\frac{1}{2^{L-2}}$-sampling from ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$ is NP-hard.

Let $G = (V, E)$ a graph produced by Theorem \[thm:count\_gap\_amplification\] and let $d = |E|$. A vertex $\vy$ of the hypercube ${\mathbb{H}_{d}}$ is easily identified with a set $E_{\vy} \subset E$ consisting of the edges $\{e \in E : y_{e'} = 1\}$. The function $h_1(\vy)$ is equal to zero if $E_\vy$ does not define a simple cycle and is equal to the length of the cycle otherwise. To convert this into a minimization problem, we define $h(\vy) = d - h_1(\vy)$. It is immediate that a minimizer of $h$ corresponds to a longest simple cycle in $G$.

Given a vertex $\vy$, testing whether $E_{\vy}$ is a simple cycle can done efficiently, and the length of the cycle is simply $|E_{\vy}|$. This implies that $h$ can be efficiently computed on ${\mathbb{H}_{d}}$. Further, since we can find the planted cycle in $G$ efficiently, we can efficiently construct a minimizer $\vy^{(planted)}$ of $h$.

Suppose that $G$ has at least $(2^L+1)$ cycles of length $L$. In this case, the distribution ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$ restricted to the minimizers is uniform, and thus the probability mass on a specific minimizer $\vy^{(planted)}$ is at most $\frac 1 {2^{L}+1}$. This also therefore upper bounds the probability mass on $\vy^{(planted)}$ in the ${\mathcal{D}}_h^{\lambda, {\mathbb{H}_{d}}}$.

On the other hand, suppose that planted cycle is the unique longest simple cycle in $G$. Thus the probability mass on $\vy^{(planted)}$ is at least $\exp(\lambda(d-L)) / Z_{h}^{\lambda, {\mathbb{H}_{d}}}$. Since every other cycle is of length at most $L-1$, and there are at most $2^d$ cycles, it follows that $\frac{Z_{h}^{\lambda, {\mathbb{H}_{d}}}}{\exp(\lambda(d-L))} \leq 1 + \frac{2^d}{\exp(\lambda)}$. For $\lambda \geq 2d$, this ratio is $(1+\exp(-d)) \leq (1 - \frac{1}{2^d})^{-1}$. The claim follows.

We can now apply Theorem \[thm:discrete\_to\_cont\_v1\] to derive the following result.

\[thm:opt\_easier\] There is a family ${\ensuremath{\mathcal{F}}}$ of functions $f : {B_d(0, R)}\rightarrow \Re$ such that the following hold.

Efficiency: 

:   Every $f \in {\ensuremath{\mathcal{F}}}$ is computable in time $poly(d)$.

Easy Optimization: 

:   An optimizer of $f$ can be found in time $poly(d)$

Sampling is NP-hard: 

:   For $\lambda \geq 2d$ and $\eta < 1 - \exp(-\Omega(d))$, there is no efficient $\eta$-sampler for ${{\mathcal{D}}_f^{\lambda}}$ unless $NP=RP$.

In the statement above, efficiently computable means that given a $t$-bit representation of $\vx$, one can compute $f(\vx)$ to $t$ bits of accuracy in time $poly(d, t)$.

The easy optimization result above can be considerably strengthened. We can ensure that $\mathbf{0}$ is the optimizer of $f$ and that except with negligible probability, gradient descent starting at a random point will converge to this minimizer. Further, one can ensure that all local minima are global and that $f$ is strict-saddle. Thus not only is the function easy to optimize given the representation, black box oracle access to $f$ and its gradients suffices to optimize $f$. We defer details to the Appendix \[app:stronger\_optimizability\].

The hardness of sampling holds also for Wasserstein distance $\frac 1 {16}$, given Remark \[rem:sampling\_wasserstein\].

A Sharp Threshold for $\lambda$ {#sec:sharp_threshold}
===============================

We start with the following threshold result for sampling from the Gibb’s distribution on independent sets due to [@Weitz06; @SlyS12].

For any $\Delta \geq 6$, there is a threshold $\lambda_c(\Delta) > 0$ such that the following are true.

FPRAS for small $\lambda$:

:   For any $\lambda < \lambda_c(\Delta)$, the problem of sampling independent sets with $\Pr[I] \propto \exp(\lambda|I|)$ on $\Delta$-regular graphs has a fully polynomial time approximation scheme.

NP-hard for large $\lambda$:

:   For any $\lambda >\lambda_c(\Delta)$, unless $NP=RP$, there is no fully polynomial time randomized approximation scheme for the problem of sampling independent sets with $\Pr[I] \propto \exp(\lambda|I|)$ on $\Delta$-regular graphs.

There is a family ${\ensuremath{\mathcal{F}}}$ of functions $f : {B_d(0, R)}\rightarrow \Re$ such that the following hold.

Efficiency: 

:   Every $f \in {\ensuremath{\mathcal{F}}}$ is computable in time $poly(d)$.

Sampling has a threshold:

:   There is a constant $\lambda_c > 0$ such that for any $\frac 1 d < \lambda < \lambda_c$, there is a $poly(d/\eta)$-time $\eta$-sampler from from the distribution ${{\mathcal{D}}_f^{\lambda}}$. On the other hand, for $\lambda > \lambda_c$, there is a constant $\eta' >0$ such that no polynomial time algorithm $\eta'$-samples from ${{\mathcal{D}}_f^{\lambda}}$ unless $NP=RP$.

For a graph $G = (V, E)$, the function $h$ on the hypercube ${\mathbb{H}_{d}}$ is defined in the natural way for $d=|V|$. We identify $\vy$ with $V_{\vy} = \{v_i : \vy_i = 1\}$, and set $h(\vy)=d - |V_\vy|$ if $V_{\vy}$ is an independent set in $G$ and to $d$ otherwise. We then apply Theorem \[thm:discrete\_to\_cont\_v1\], with $R=2\sqrt{d}$ and $M = 4d^2 \ln 24R$. For this value of $M$, the approximate equivalence between sampling from $\exp(\lambda |I|)$ and sampling from $\exp(-\lambda f)$ holds for $\lambda \geq \frac{1}{d}$. The claim follows.

Related Work {#sec:related}
============

The problems of counting solutions and sampling solutions are intimately related, and well-studied in the discrete case. The class \#P was defined in @Valiant79, where he showed that the problem of computing the permanenet of matrix was complete for this class. This class has been well-studied, and [@Toda91] showed efficient exact algorithms for any \#P-complete problem would imply a collapse of the polynomial hierarchy. Many common problems in \#P however admit efficient approximation schemes, that for any $\eps>0$, allow for a randomized $(1+\eps)$-approximation in time polynomial in $n/\eps$. Such [*Fully Polynomial Randomized Approximation Schemes*]{} (FPRASes) are known for many problems in \#P, perhaps the most celebrated of them being that for the permananet of a non-negative matrix [@JerrumSV04].

These FPRASes are nearly always based on Markov Chain methods, and their Metropolis-Hastings [@MetropolisRRTT53; @Hastings70] variants. These techniques have been used both in the discrete case (e.g. @JerrumSV04) and the continuous case (e.g. @LovaszV06). The closely related technique of Langevin dynamics [@RosskyDF78; @RobertsS02; @DurmusM17] and its Metropolis-adjusted variant are often faster in practice and have only recently been analyzed.

Efficient Net Construction {#app:eccs}
==========================

We start with the existence of error correcting codes for worst case error (e.g. @Justesen72).

There exists a universal constant $\alpha > 0$, and an efficiently computable mapping $\psi : \{0, 1\}^d \rightarrow \{0, 1\}^{4d}$ such that for any $\vy \neq \vy' \in \{0, 1\}^d$, the Hamming distance $d_H(\psi(\vy), \psi(\vy')) \geq 4\alpha d$. Further, there is an efficiently computable mapping $\texttt{Decode} : \{0, 1\}^{4d} \rightarrow \{0, 1\}^d$ such that for any $\vy \in \{0, 1\}^D$ and any $\vw$ satisfying $d_H(\psi(\vy), \vw) \leq \alpha d$, $\texttt{Decode}(\vw)$ returns $\vy$. \[thm:eccs\]

Armed with this, we prove the desired net construction.

There is an absolute constant $\eps > 0$ and an efficiently computable map $\phi : \{0, 1\}^d \rightarrow {B_d(\mathbf{0}, 1)}$ such that (a) $\|\phi(\vy) - \phi(\vy')\| \geq 4\eps$ and (b) $\vx \in {B_d(\phi(\vy), 2\eps)}$, we can efficiently recover $\vy$.

The map $\phi(\vy)$ will be constructed by embedding $\psi(\vy)$ into ${B_d(\mathbf{0}, 1)}$. We first interpret $\psi(\vy)$ as a vector $\hat{\vy}$ in $\{0, 1, \ldots, 15\}^d$, with the $i$th co-ordinate of $\hat{\vy}$ being defined by the 4 bits $\psi(\vy)_{4i-3}, \psi(\vy)_{4i-2}, \psi(\vy)_{4i-1}, \psi(\vy)_{4i}$. The $i$th co-ordinate of $\phi(\vy)$ is set to $\hat{\vy}_i / 15\sqrt{d}$. It is easy to check that $\phi(\vy)$ as defined lies in the unit ball. Consider $\vy, \vy' \in \{0, 1\}^d$ such that $d_H(\psi(\vy), \psi(\vy')) \geq 4\alpha d$. This means that $\hat{\vy}$ and $\hat{\vy'}$ differ in at least $\alpha d$ locations. This in turn means that $\|\phi(\vy) - \phi(\vy')\| \geq \sqrt{\alpha}/15$.

Let $\vx \in {B_d(\phi(\vy), \eps)}$. By Markov’s inequality, $|\{i : |\phi(\vy)_i - \vx_i| \geq \frac{1}{30\sqrt{d}}\}|$ is at most $900\eps^2 d$. Thus if we greedily decode each co-ordinate of $\vx$ and expand that to a $4d$-bit vector, the decoding will be correct except in $3600\eps^2 d$ locations. Letting $\eps = \sqrt{\alpha} / 120$, and using properties of $\psi$, the claim follows.

Sampling to Optimization {#app:folklore}
========================

The following folklore theorem shows that sampling for high $\lambda$ implies approximate optimization.

\[thm:sampling\_to\_opt\] \[Sampling Implies Optimization: Generic\] Let $f : {B_d(0, R)}\rightarrow \Re$ and suppose that for some $a \in \Re$, the level set $L_a = \{\vx \in {B_d(0, R)}: f(\vx) \geq a\}$ is measurable. Then for any $\eps>0$, and for $\lambda \geq \frac{\ln \frac 1 \delta + \ln \frac {{\mathrm{vol}}_d({B_d(0, R)})}{{\mathrm{vol}}_d(L_a)}}{\eps}$, $$\begin{aligned}
    \Pr_{\vx \sim {\mathcal{D}}_{\lambda}^f}[f(\vx) \geq a + \eps] \leq \delta.
  \end{aligned}$$

We write $$\begin{aligned}
    \Pr_{\vx \sim {\mathcal{D}}_{\lambda}^f}[f(\vx) \geq a + \eps] &\leq \frac{\exp(-\lambda(a+\eps))\cdot {\mathrm{vol}}_d({B_d(0, R)})}{Z_f^{\lambda}}\\
    &\leq \frac{\exp(-\lambda(a+\eps))\cdot {\mathrm{vol}}_d({B_d(0, R)})}{\exp(\lambda a)\cdot {\mathrm{vol}}_d(L_a)}\\
    &= \frac{\exp(-\lambda\eps)}{\frac{{\mathrm{vol}}_d(L_a)}{{\mathrm{vol}}_d({B_d(0, R)})}}\\
    &\leq \delta.
  \end{aligned}$$

\[thm:sampling\_to\_opt\_lip\] \[Sampling Implies Optimization: Lipschitz $f$\] Let $f : {B_d(0, R)}\rightarrow \Re$ be $L$-Lipschitz and let $f^\star = \min_{\vx \in {B_d(0, R)}} f(\vx)$. Then for any $\eps>0$ and for $\lambda \geq \frac{2d\ln \frac{4LR}{\eps} + 2\ln \frac 1 \delta}{\eps}$, $$\begin{aligned}
    \Pr_{\vx \sim {\mathcal{D}}_)f^{\lambda}}[f(\vx) \geq f^\star + \eps] \leq \delta.
  \end{aligned}$$

Set $a = \eps / 2$, and note that by Lipschitz-ness of $f$, the level set $L_a$ contains a ball of radius $\eps/2L$ around the optimizer, so that $\frac{{\mathrm{vol}}_d(L_a)}{{\mathrm{vol}}_d({B_d(0, R)})}$ is at least $(\eps/4LR)^d$. Applying Theorem \[thm:sampling\_to\_opt\], the claim follows.

\[Sampling Implies Optimization: Smooth $f$\] Let $f : {B_d(0, R)}\rightarrow \Re$ be $\beta$-smooth and let $f^\star = \min_{\vx \in {B_d(0, R)}} f(\vx)$ be attained in the interior of ${B_d(0, R)}$. Then for any $\eps>0$ and for $\lambda \geq \frac{d\ln \frac {\beta R^2}{\eps} + 2\ln \frac 1 \delta}{\eps}$, $$\begin{aligned}
    \Pr_{\vx \sim {\mathcal{D}}_)f^{\lambda}}[f(\vx) \geq f^\star + \eps] \leq \delta.
  \end{aligned}$$

Let the mimimum $f^\star$ be attained at $\vx^\star$; by assumption ${\nabla}f$ at $\vx^\star$ is zero, and by $\beta$-smoothness, the level set $L_{\eps/2}$ contains a ball of radius $(2\eps/\beta)^\frac{1}{2}$ around $\vx^\star$. The claim follows.

We note that $\delta = \frac 1 2$ suffices to ensure that efficient samplability implies efficient approximate optimization, since we can run the sampler multiple times.

Deferred Proofs
===============

Incomplete Gamma Functions {#app:incomplete_gamma}
--------------------------

The following was used in the proof of Theorem \[thm:discrete\_to\_cont\_v1\].

\[lem:incomplete\_gamma\] Let $d$ be a positive integer and $\alpha \geq 16d$. Then $$\begin{aligned}
    \int_{0}^{\frac 1 2} \exp(-\alpha r) r^{d-1}\;{\mathrm{d}}r &\leq (1+2\exp(-d))\int_{0}^{\frac 1 4} \exp(-\alpha r) r^{d-1}\;{\mathrm{d}}r
  \end{aligned}$$

By definition of the Incomplete Gamma function, for any $a \geq 0$, $$\begin{aligned}
    \int_{0}^{a} \exp(-\alpha r) r^{d-1}\;{\mathrm{d}}r &=     \frac{1}{\alpha^d} \cdot \int_{0}^{a\alpha} \exp(-s) s^{d-1}\;{\mathrm{d}}s\\
    &= \frac{\gamma(d, a\alpha)}{\alpha^d}.
  \end{aligned}$$ Translated to this language, we wish to bound $$\begin{aligned}
    \frac{\gamma(d, \alpha/2)}{\gamma(d, \alpha/4)}.
  \end{aligned}$$

We now bound $$\begin{aligned}
  1 - \frac{\gamma(d, \alpha/4)}{\gamma(d, \alpha/2)} &\leq
  1 - \frac{\gamma(d, \alpha/4)}{\Gamma(d)} \\
  &= \Pr_{X \sim \Gamma(d, 1)}[X \geq \alpha/4]\\
  &\leq \Pr_{X \sim \Gamma(d, 1)}[X \geq d + 3d]\\
  &\leq \exp(-d).\end{aligned}$$ Here in the first step, we have used the fact that the Incomplete Gamma function is the cdf of the corresponding Gamma distribution. The last step uses standard tail inequalities for sub-gamma distributions from @BoucheronLM13 [Section 2.4].

We have thus shown that $\frac{\gamma(d, \alpha/4)}{\gamma(d, \alpha/2)} \geq 1 - \exp(-d)$. Thus $\gamma(d, \alpha/2) \leq (1-\exp(-d))^{-1} \gamma(d, \alpha/4)$. For $d \geq 1$, $(1-\exp(d))^{-1} \leq (1+2\exp(-d))$ and the claim follows.

Count Gap Amplification for Cycles {#app:count_gap_amplification}
==================================

Theorem \[thm:count\_gap\_amplification\] follows from the NP-hardness of Hamiltonian cycle and the following reduction.

Given a graph $G = (V, E)$ and an integer $k$, there is a polynomial time algorithm that outputs a graph $G' = (V', E')$ such that

“Completeness”:

:   If $G$ has a Hamiltonian cycle, then $G'$ has at least $1+ 2^{tn}$ simple cycles of length $nt$.

“Soundness”:

:   If $G$ has no Hamiltonian cycle, then $G'$ has exactly one cycle of length $nt$, and no longer simple cycles.

Efficiency:

:   It is easy to find one cycle of length $nt$ in $G'$.

The reduction replaces each edge of $G$ by a path of length $t$ with each edge on the path being duplicated. In addition, we add a new set of $tn$ vertices that form a cycle, to ensure that we always have once cycle of length $tn$. We give more details next.

Let $G=(V,E)$ and let $e=(u,v) \in E$. Our new vertex set $V' = V_1 \cup V_2$, where $V_1 = V \cup \{e_i : e \in E, i \in [t-1]\}$ and $V_2 = \{w_1,\ldots, w_{nt}\}$. The vertices in $V_2$ form a simple cycle, i.e. $E_2 = \{(w_i, w_{i+1} : i \in [nt-1])\} \cup \{(w_{nt}, w_1)\}$. For every edge $e = (u, v)\in E$, $E'$ contains two copies of each edge set $E_1^e = \{(u, e_1), (e_t, v)\} \cup \{(e_i, e_{i+1}) : i \in [t-1]\}$.

It is easy to see that $G'$ always has one cycle of length $nt$ consisting of $E_2$ that can be found efficiently. Whenever $G$ has a Hamiltonian cycle, we can form a cycle of length $nt$, by following the paths corresponding to the edges used in the Hamilitonian cycle in $G$. At each step, we have a choice of two edges to choose from, since $E'$ has parallel edges. This gives us $2^{nt}$ such cycles, proving the “completeness” part of the theorem.

Finally note that for any simple cycle of length $nt$ on $V_1$, the projection of the cycle onto the vertices in $V$ is a simple cycle of length $n$, i.e. a Hamiltonian cycle. This completes the proof of the “soundness” part of the theorem.

Stronger Optimizability {#app:stronger_optimizability}
=======================

In this section, we show that the separation between optimization and sampling holds even for stronger notions of $f$ being optimizable.

![image](figures/function_hnew.pdf){width=".48\textwidth"} ![image](figures/function_fnew.pdf){width=".48\textwidth"}

There is a family ${\ensuremath{\mathcal{F}}}$ of functions $f : \Re^d \rightarrow \Re$ such that the following hold.

Efficiency: 

:   Each $f \in {\ensuremath{\mathcal{F}}}$ is computable in time $poly(d)$.

Easy Optimization: 

:   The zero vector $\mathbf{0}$ is a global optimizer of $f$. Further, $f$ satisfies strict saddle, and a randomly initialized gradient descent algorithm will converge to $\mathbf{0}$ with high probability.

Hard to Sample: 

:   For $\lambda \geq 2d$, there is no $1 - \exp(-\Omega(d))$-sampler for ${{\mathcal{D}}_f^{\lambda}}$ unless $NP=RP$.

\[thm:discrete\_to\_cont\_v2\]

The proof is very similar to that of Theorem \[thm:opt\_easier\]. We will highlight the relevant changes. First, we redefine $h$ slightly: $h$ now takes the value $0$ whenever $E_{\vy}$ defines a simple cycle of length $L$, and takes the value $d$ otherwise. Note that it is NP-hard to determines if $h^{-1}(0)$ has size $1$ or $2^L+1$.

The construction from $h$ to $f$ is similar to that in Theorem \[thm:discrete\_to\_cont\_v1\] with some variation. The function $f_1$ takes the value $M$, except in small balls around $h^{-1}(0)$ and a new minima at $0$. In addition, we add a linear term. Recalling the definition of ${\texttt{round}}(\vx)$ and $g(\vx)$ from the proof of Theorem \[thm:discrete\_to\_cont\_v1\], we define $f(\vx)$ : $$\begin{aligned}
    f(\vx) &= \left\{\begin{array}{ll}
                          \|\vx\| - \sqrt{d} + 16(M+\sqrt{d})\cdot g(\vx) & \mbox{ if } h({\texttt{round}}(\vx))=0 \mbox{ and } g(\vx) \leq  \frac 1 {16}\\
                          \|\vx\| + 16M\cdot \|\vx\| & \mbox{ if }  \|\vx\| \leq  \frac 1 {16}\\
                          \|\vx\| + M & \mbox{ otherwise }\\
                     \end{array}
              \right.
  \end{aligned}$$ It is easy to verify that $f$ satisfies the following properties:

-   $f(\mathbf{0})$ = 0. For $\vy \in {\mathbb{H}_{d}}$, $h(\vy) =  0 \Leftrightarrow f(\vy) = 0$.

-   $f$ is efficiently computable.

-   $f$ is continuous and $O(M)$-Lipschitz.

-   Outside of $\cup_{\vy : h(\vy = 0) \wedge \vy = \mathbf{0}} B_{d}(\vy, \frac 1 {16})$, $f$ is equal to $M+\|\vx\|$.

It follows that the gradient at most points points towards the origin. Thus if the line joining the initial point of a gradient descent and $\mathbf{0}$ avoids hitting $\cup_{\vy : h(\vy = 0) } B_{d}(\vy, \frac 1 {16})$, gradient descent will converge to the origin. Since this happens with high probability, it follows that GD will succeed on $f$ w.h.p. While $f$ as defined is not twice differentiable, convolving $f$ with a small Gaussian gives us a function that is infinitely differentiable, and whose Lipschitz constant, and behavior with respect to gradient descent does not significantly change.

The hardness of sampling proof is essentially unchanged, and thus omitted.

Improving the Lipschitz constant
================================

The Lipschitz constant of the construction in Theorems \[thm:discrete\_to\_cont\_v1\] and \[thm:discrete\_to\_cont\_v2\] is $O(M)$, as the function value must change by $M$ in a ball of constant radius around ${\texttt{round}}(\vx)$. We next argue how we can improve the Lipschitz constant to $O(M/\sqrt{d})$.

Towards that goal, we will use error correcting codes to embed the Hypercube in to a set of points that are at distance $\Omega(\sqrt{d})$ from each other. Recall that by Theeorem \[thm:eccs\] there are maps $\psi : {\mathbb{H}_{d}} \rightarrow {\mathbb{H}_{4d}}$ and $Decode :: {\mathbb{H}_{4d}} \rightarrow {\mathbb{H}_{d}}$ such that for a constant $\alpha > 0$, (a) For all $\vy \neq \vy' \in {\mathbb{H}_{d}}$, the Hamming distance $|\psi(\vy) - \psi(\vy')| \geq 4\alpha d$, and (b) For any $\vy \in {\mathbb{H}_{d}}$, and any $\vz \in {\mathbb{H}_{4d}}$ such that $|\vz - \psi(\vy)| \leq \alpha d$, we have $Decode(\vz) = \vy$.

Armed with this, we will now refine our function ${\texttt{round}}$. For $\vx \in \Re^{4d}$, define $$\begin{aligned}
  \overline{{\texttt{round}}}(\vx) = Decode({\texttt{round}}(\vx)).\end{aligned}$$ Thus $\overline{{\texttt{round}}}(\vx) \in {\mathbb{H}_{d}}$. Moreover, there is a constant $\overline{\alpha}>0$ such that if $\vx \in B(\phi(\vy), \overline{\alpha}\sqrt{d})$, then $\overline{{\texttt{round}}}(\vx) = \vy$.

Let $\overline{g}(\vx) = \|\vx - \overline{{\texttt{round}}}(\vx)\| / (\overline{\alpha}\sqrt{d})$ denote the scaled Euclidean distance from $\vx$ to $\overline{{\texttt{round}}}(\vx)$. Let ${s}= 2M$. We now define the function $\overline{f}$ as follows: $$\begin{aligned}
    \overline{f}(\vx) &= \left\{\begin{array}{ll}
                                                  h(\overline{{\texttt{round}}}(\vx)) + {s}\cdot \overline{g}(\vx) & \mbox{ if }  \overline{g}(\vx) \leq \frac{M - h(\overline{{\texttt{round}}}(\vx))}{{s}}\\
                          M & \mbox{ if } \overline{g}(\vx) \geq \frac{M - h(\overline{{\texttt{round}}}(\vx))}{{s}}\\
                     \end{array}
              \right.
  \end{aligned}$$ Since $M \geq 2d$, and $h$ has range $[0,d]$, the value $\frac{M - h(\overline{{\texttt{round}}}(\vx))}{\overline{{s}}}$ is in the range $[\frac 1 4, \frac 1 2]$. It follows that $f$ takes the value $M$ outside balls of radius $\overline{\alpha} \sqrt{d} / 2$ around the $\psi(\vy)$ vertices, and is strictly smaller than $M$ in balls for radius $\overline{\alpha}\sqrt{d} / 4$. Further, the Lipschitz constant of $\overline{f}$ is now $M/\sqrt{d}$. The rest of the proof is as before.

In particular, this implies that assuming the Exponential Time Hypothesis [@ImpagliazzoP01], approximate sampling need $\exp(\Omega(d)$ time for continuous Lipschitz functions from $B_d(0, \sqrt{d})$ to $[0, O(d)]$, with Lipschitz constant $O(\sqrt{d})$, and $\lambda = O(\ln d)$.

[^1]: As defined, this function is Lipschitz but not smooth. It can be easily modified to a $2$-Lipschitz, $2/\eps$-smooth function by replacing its linear behavior in the ball by an appropriately Huberized version.
