the penalty method

“In this paper we will make conceptually simple generalization of Metropolis algorithm, by adjusting the acceptance ratio formula so that the transition probabilities are unaffected by the fluctuations in the estimate of [the acceptance ratio]…”

Last Friday, in Paris-Dauphine, my PhD student Changye Wu showed me a paper of Ceperley and Dewing entitled the penalty method for random walks with uncertain energies. Of which I was unaware of (and which alas pre-dated a recent advance made by Changye).  Despite its physics connections, the paper is actually about estimating a Metropolis-Hastings acceptance ratio and correcting the Metropolis-Hastings move for this estimation. While there is no generic solution to this problem, assuming that the logarithm of the acceptance ratio estimate is Gaussian around the true log acceptance ratio (and hence unbiased) leads to a log-normal correction for the acceptance probability.

“Unfortunately there is a serious complication: the variance needed in the noise penalty is also unknown.”

Even when the Gaussian assumption is acceptable, there is a further issue with this approach, namely that it also depends on an unknown variance term. And replacing it with an estimate induces further bias. So it may be that this method has not met with many followers because of those two penalising factors. Despite precluding the pseudo-marginal approach of Mark Beaumont (2003) by a few years, with the later estimating separately numerator and denominator in the Metropolis-Hastings acceptance ratio. And hence being applicable in a much wider collection of cases. Although I wonder if some generic approaches like path sampling or the exchange algorithm could be applied on a generic basis… [I just realised the title could be confusing in relation with the current football competition!]

2 Responses to “the penalty method”

  1. The penalty method has nice properties; e.g. if the exact noiseless MH is geometrically ergodic then the penalty method is geometrically ergodic. However the penalty method is itself an ideal algorithm that cannot be implemented so it is indeed of limited interest compared to pseudo-marginal techniques.

    However there are algorithms that do mimic the penalty method. In a recent paper with George Deligiannidis and Mike Pitt (, we have introduced the correlated pseudo-marginal algorithm which is a novel version of the pseudo-marginal algorithm correlating the estimators of the numerotor and denominator in the MH acceptance ratio.

    We show in Section 4 of this paper that the correlated pseudo marginal algorithm converges weakly to the penalty method as the number of data T goes to infinity.

  2. Ted Meeds Says:

    Hi Christian,

    In our paper GPS-ABC, we drew some inspiration from Ceperley and Dewing’s paper. Although we didn’t use the expected acceptance probabilty A in our algorithm, we could have by using the synthetic likelihood since the synthetic likelihood estimates the unknown variance term for us. We also minimized the MAD which required estimating the median rather than the mean acceptance.

    There are probably a lot of new algorithms that can be derived from C&P paper, though the correction is fairly straightforward to derive.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s