18
$\begingroup$

From any generic sampling algorithm, one can derive an optimization algorithm.

Indeed, to maximize an arbitrary function $f: \textbf{x} \rightarrow f(\textbf{x})$, it suffices to draw samples from $g \sim e^{f/T}$. For $T$ small enough, these samples will fall near the global maximum (or local maxima in practice) of the function $f$.

By "sampling" I mean, drawing a pseudo-random sample from a distribution given a log-likelihood function known up to a constant. For instance, MCMC sampling, Gibbs sampling, Beam Sampling, etc. By "optimization" I mean the attempt to find parameters maximizing the value of a given function.

Is the reverse possible? Given a heuristic to find the maximum of a function or a combinatorial expression, can we extract an efficient sampling procedure?

HMC for instance seems to take advantage of gradient information. Can we construct a sampling procedure that takes advantage of a BFGS-like approximation of the Hessian? (edit: apparently yes: http://papers.nips.cc/paper/4464-quasi-newton-methods-for-markov-chain-monte-carlo.pdf) We can use MCTS in combinatorial problems, can we translate that into a sampling procedure?

Context: a difficulty in sampling is often that most of the mass of the probability distribution lies within a very small region. There are interesting techniques to find such regions, but they do not directly translate into unbiased sampling procedures.

Edit: I now have a lingering feeling that the answer to that question is somewhat equivalent to the equality of complexity classes #P and NP, making the answer a likely "no". It does explain why every sampling technique yields an optimization technique but not vice versa.

Improve this question
$\endgroup$
19
  • $\begingroup$ Although I think I have a conventional understanding of most of the words in this question, I'm unsure what it's getting after. Could you state a little more precisely what you mean by "sampling" and what exactly would be "optimized"? You seem to assume implicitly that your readers have in mind a particular setting in which a "distribution" (or family thereof?) is involved and in which a particular objective is assumed, but one can only guess at what you really intend when you make such broad statements as those appearing in the last paragraph. $\endgroup$
    – whuber ♦
    Commented Aug 19, 2014 at 17:34
  • $\begingroup$ By "sampling" I mean, drawing a pseudo-random sample from a distribution given a log-likelihood function known up to a constant. For instance, MCMC sampling, Gibbs sampling, Beam Sampling, etc. By "optimization" I mean the attempt to find parameters maximizing the value of a given function. For example, gradient descent, the simplex algorithm, simulated annealing are optimization techniques. $\endgroup$
    – Arthur B.
    Commented Aug 19, 2014 at 17:52
  • $\begingroup$ There's a natural mapping between Simulated annealing and MCMC sampling. There's a less direct mapping between HMC and gradient descent (if you squint). My question is whether this can be made more systematic. A difficulty in sampling is often that most of the mass of the probability distribution lies within a very small region. There are interesting techniques to find this region, but they do not directly translate into unbiased sampling procedures. $\endgroup$
    – Arthur B.
    Commented Aug 19, 2014 at 17:56
  • $\begingroup$ Please edit your question to include these clarifications. That is crucial because your (somewhat specialized) use of the word "sampling," although appropriate in your context, differs from what many readers may understand. Also, your explanation of "optimization," although correct, does not appear to be helpful in making its meaning sufficiently precise here: characterizing what the "given function" is and how it might be related to "sampling" would be useful additions. $\endgroup$
    – whuber ♦
    Commented Aug 19, 2014 at 18:02
  • $\begingroup$ Is it better now? $\endgroup$
    – Arthur B.
    Commented Aug 19, 2014 at 18:13

3 Answers 3

Reset to default
4
$\begingroup$

One connection has been brought up by Max Welling and friends in these two papers:

The gist is that the "learning", ie. optimisation of a model smoothly transitions into sampling from the posterior.

Improve this answer
$\endgroup$
3
$\begingroup$

There is a link, it's the Gumbel-Max trick !

http://www.cs.toronto.edu/~cmaddis/pubs/astar.pdf

Improve this answer
$\endgroup$
0
$\begingroup$

One possibility is to find the CDF of the heuristic. Then from monte carlo theory we know that for $ U \sim unif[0,1]$ that $F^{-1}(U) \sim F$ where F is the cdf of the distribution you are after. If you cannot find the cdf exactly, you could use a simple acceptemce-rejection based heuristic.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.