---
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$)

:   : 