4
$\begingroup$

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's stationary distribution is the distribution produced by normalizing some function. It's a small leap to realize that you can use this to optimize lots of things and you can even keep rejections that happen to be the minimum you've found so far. But further more you could also reshape the cost function so that it rewards the optimum with much higher probability than anything else (say by exponentiation or squaring the function or something). This has the effect of lowering the entropy of the normalized distribution. If we reshape the target distribution too much though our mixing times could be quite bad. We can solve this by gradually reshaping the target distribution to a low entropy distribution however. Further more higher entropy target distributions should (I think? A proof would be appreciated) have lower mixing times so if our actual target function has low entropy and long mixing times we can fix that. After one researches this line of thinking it quickly becomes clear that this is simulated annealing from a different angle than its generally presented.

The notion of entropy used in physics is deeply connected (or so I'm told) to the notion of entropy used in information theory (which is why Shannon named it as such). The physical notion of entropy is deeply connected to temperature. I've never taken thermodynamics so I don't really understand the bridge between information theoretical entropy, and temperature (which has physical entropy in the middle as the bridge).

Can this link be explained? Given a probability distribution can we define the "temperature" of the distribution? Is there an information theoretical way to define temperature? Perhaps only a subset of distributions have a temperature but we can generate probability distributions that correspond to a given temperature? I'm trying to understand the notion of temperature used in simulated annealing without learning about thermodynamics.

To give a better example of what I'm trying to ask I'll ask by analogy. Understanding what a quantum circuit is doesn't require understanding much of anything about quantum physics for a computer scientist. What's the equivalent understanding of temperature for a computer scientist that knows a bit about information theory?

$\endgroup$
  • $\begingroup$ Side note: I've found several upper bounds on mixing time that are seemingly proportional to log(1/2^H(pi)) where H is min-entropy and pi is the stationary distribution. I say seemingly because they all have an additional complicated term that depends on pi and/or the markov chain matrix (like the spectral gap of the matrix, or the Cheeger constant). But if proportionality holds then the claim that lower entropy stationary distributions will be mixed to faster is true at least for min-entropy $\endgroup$ – Jake Oct 29 '19 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.