Markov Chain Monte Carlo: Burn-In Is Unnecessary | Hacker News Reader

Markov Chain Monte Carlo: Burn-In Is Unnecessary

users.stat.umn.edu

62 pointsspekcular24 comments

This is plain silly.

If you don't have burn in, you bias your estimate. Sure, in the long run the bias becomes smaller and smaller, but, as the saying goes, in the long run we are all dead.

MCMC is generally slow, any way to speed it up a bit is good. Throwing away the burn-in part of the chain is just such a way to speed it up.

A helpful way to think about burn-in is that you probably don't care about bias as such but rather error which is a combination of bias and variance. Burn-in reduces bias at the cost of variance (since you have fewer points in your final estimates).

My intuition is you want to be somewhere in the middle of the tradeoff. You want to tolerate some bias -- use burn-in to get partway but only partway to the stationary distribution. Here's a paper that advances this way of thinking: http://web.stanford.edu/~ngoodman/papers/LiederGriffithsGood...

The author's proposal to start at a high-probability-density (HPD) point reduces the bias that you get from not doing burn-in, but it still creates a bias.

In order to get a reasonable answer from MCMC, you need to run for many correlation times. Burn-in should only last a few correlation times, so you don't lose that large a fraction of your chain by throwing it away. And the part of the chain you're using is biased, so you're probably not gaining anything by keeping it.

I think Geyer's point is that if you generate samples X_0, ..., X_b where b>0 is a burn-in time, and start collecting estimates at time t>b, then that's not somehow better than starting at X_b and not burning in (the two are equal in distribution).

The problem there is that (assuming a source of true noise) X_b is a random variable, in fact if b is sufficiently high its distribution approximates your target distribution pretty well. So if you're arguing "instead of burn-in you can also use an approximate sample of your target distribution" then that's technically correct.

However generating an approximate sample is the exact problem that a MCMC process is trying to solve.

Of course, you are right. I recall Geyer at some point writing some people thought there was a difference between having a burn-in period that happened to have X_b = x_b, and simply starting with X_0 = x_b. I can't find that on this page though.

I see, you're right that those two are entirely equivalent (it's what makes the Markov chain 'Markov'). And using an approximate sample instead of burn-in isn't entirely without merit, though I think I've only seen that being used with things like Brownian motion where the trajectory is the thing of interest, rather than the samples themselves.

Yes, he writes "If you start at x and I start at x then your MCMC run is no better than mine." and surrounding text is making this point.

At that point, though, isn't it just semantics?

If you have a chain, and throw out the beginning fraction, is that any more burnin than starting with X_b, which you probably had to find using some period of... burnin?

This is really all about time series heterogeneity which is a topic unto itself. Eventually the chain reaches some stationary distribution but in the meantime there will be some shift in the distribution potentially. Seems like you could model the chain to do some test of where the distribution shifts, if at all.

I imagine this is in the literature. Giving it a brief look I can't find anything but I haven't looked hard enough.

I think I generally agree with the majority of the comments here that burn in can serve a useful purpose (especially if you can't find a high probability density point to start from), but I also wonder: if burn-in vs no burn-in makes a large difference in your outcome, aren't you likely just not running your chain long enough? Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?). People tend to have a cognitive bais towards distributions looking pretty (eg not having random chains off to the side as in the article), but I'm not sure it makes a real difference.

That said, I do think burn in is a pretty reasonable way to find a good starting point if you don't have existing knowledge about the distribution. From a practical standpoint, has anyone actually seen a massive difference between runs with/without burn in? kinda curious how often it really matters

> Sure, if you choose a bad starting point, your initial samples might not be representative of the overall distribution, but if a handful of non-representative points can massively impact your result, then I'm not sure how stable your result was to begin with (how do you know there isn't some other set of low-probability high-impact points that your sampler just missed through luck?).

You're right, and most comments I've seen over the years on the post conveniently miss that he addresses that:

> This unbiasedness argument is rubbish. If you start at x and I start at x then your MCMC run is no better than mine. If you used burn-in and I didn't, then you are entitled to woof about approximate unbiasedness and I am not. But that woof does not make your estimator any better.

My interpretation has always been this, and I think it's correct: You need a good starting point. There's no reason to think burn-in gives you a good starting point. Instead, use something that's actually intended to give a good starting point, like the mode.

For difficult problems, find the mode may (a) be as hard to find, or harder, as doing an MCMC sampling run, (b) be completely unrepresentative of the overall distribution.

I agree, but his argument is that in general doing a burn-in is still not going to be a substitute for good starting values, and if anything it's even easier to get a bad starting value using burn-in on a difficult problem.

If you have some nice idea of how to find a good starting value, then you should certainly use it, not just rely on burn-in.

But having used your good starting value, you should still discard some burn-in iterations. This is certainly true if you're running more than one chain, since including them all with this same starting value will bias the results (in a real, not just theoretical sense, though the magnitude of the bias will of course vary with your problem). Even if you're running just one chain, you should discard at least some burn-in (say 5%) even if you have no evidence that it is necessary, because you really don't know that your supposed good starting point is actually representative. (That is, you don't know this a difficult problems, which are the ones I'm discussing.)

I don't understand how the mode can be unrepresentative of the overall distribution. It seems like it's one of the finest representatives.

This can happen easily in Bayesian hierarchical models, where there is a hyperparameter that controls the variance of many lower-level parameters. When the variance is small, the probability density for these parameters is high (their distribution is sharply peaked), when the variance is large, the density is smaller (maybe many, many orders of magnitude smaller). So the mode will be where the variance is small, even if the data make this a much less probable region of the parameter space. (Note: the probability of a region is the product of its volume and its probability density - the total probability can be low even if the density is extremely high.)

You'll also typically get an unrepresentative mode for a neural network or other ML-type model, since the mode will be a highly-overfitted point.

For the interested, here is a classic article that goes into more depth: _Practical Markov Chain Monte Carlo_ [1].

[1]: https://projecteuclid.org/euclid.ss/1177011137

This rant is rather misguided.

For easy problems, it doesn't much matter what you do, as long as you don't limit your computation time to some unnecessarily-small amount. So let's assume you're trying to sample from some complicated distribution that you don't know much about, and for which you don't know how well your Markov Chain mixes.

It is then highly likely that whatever point you start at, regardless of good intentions, is not representative of the distribution (saying it's a possible point is obtuse). You don't want to include that point in your estimates. Hence you want to discard burn-in.

By the way, a kernel of truth in the rant (though not actually mentioned) is that if you are using just one chain, you should not discard more than about 20% as burn in. If you are tempted to discard 50%, then you don't really know that the chain has come close to convergence. You may say, "this function of state is near 20 for the first half, then drops to around 10 for the second half, so I'll discard the first half as burn-in". But you're fooling yourself. For all you know, if you ran the chain longer, it might go back to a state where the value is 20, moving back and forth between these two modes, and by discarding the first half, you're throwing out half the distribution, getting drastically wrong results. (The longer the chain stays at around 10, the less chance of this being true, which is why discarding 20% as burn-in could make sense.) An exception would be if you had good prior reason to think the first 50% couldn't be representative of the distribution, but in that case too you'd be better off running for longer (if at all possible) to make sure the second half isn't also unrepresentative.

However, if you're trying to be as sure as you can that you're getting the right result, you should be running more than one chain, even though they'll have to be shorter (given a fixed budget). Geyer rants against this too, on the basis that using all your computational budget for one run gives the greatest chance of convergence, but this makes no practical sense. At a minimum, along with your long run, you'd want to to do a few extra short runs to see if they end up going to radically different values that are never visited in the long run - in which case you'll have to rethink the whole thing. A good general guide would be to run something like 5 to 10 chains, for equal time, and checking whether they seem to have converged to the same distribution. (If not, you need a better Markov chain, or a faster computer.) Of course, doing a huge number of short runs is also bad. Moderation is good.

Wow! Thank you professor Neal!

Inspiring that the father of modern MCMC techniques takes the time to correct bad takes on hacker news!

I particularly like the suggestion of not doing burn-in and instead starting your chain where the last one ended.

Is that not simply doing a burn-in of many thousands?

Fully agree with everyone else. The argument "asymptotically the burn in doesn't matter so don't do it" misses a few key points -- like about how I'm not going to get to the limit, and I certainly won't _know_ I get to the limit.

NO! The point of multiple chains is to test for convergence. If you start four chains at four random points in probability space and they all converge to same distribution, you can be confident in the result, but many times that fails to occur. This is what the rhat diagnostic shows. If you calculate rhat with one big chain it will mislead you. This is terrible advice.

I disagree with Geyer on this.

Burn-in may not be necessary but often is for the type of inference that most people are familiar with.

But these days, who cares? I can fit a highly parameter used model on my 6 year old MacBook Pro with Stan just fine. If I want some extra juice I can rent an EC2 or Droplet.

I'm not too sure about this. Isn't the usual derivation of MCMC methods based on equilibrium distribution of the chain? So you either need to run the chain for a (unknowably) long time to achieve equilibrium (hence burn-in) or start from an equilibrium distribution - but if you knew that, you wouldn't be running MCMC. And sure, we can never tell the chain has achieved equilibrium, but that's better than calling any odd point 'equilibrium'.

He does mention this stream of thought but dismisses it out of hand, without an explanation.

Interesting theory. So does this mean that quasi-supervised learning can be quicker than unsupervised ML when using Monte-Carlo methods?

Reply on news.ycombinator.com