On the Convergence of the Cross-Entropy Method. Margolin. Annals of OR. 2005


  1. “This method is an iterative stochastic procedure making use of the importance sampling technique.  The stochastic mechanism changes from iteration to iteration according to the K-L cross-entropy approach.”
  2. It is actually used for rare event estimation, and the “rare event” that is trying to be found is a sample from the space that is near the global optimum.  Because presumably these near optimal samples don’t occur frequently, the best way to find samples from there is to modify the distribution so it is as close as possible to the distribution that produces these rare events
  3. This paper takes a proof for ant optimization and uses it on a slightly different version of CE
  4. There is no rule as to how to chose an appropriate distribution to sample from.  Based on ideas from MCMC (which is related to CE at its core), the distribution should have good support at the area of global optimum/where the rare events lie.
  5. I’m not reading this carefully at all.
  6. Convergence is proved, but there are no guarantees about the rate, and coverage has to be adequate, so it is a pretty loose guarantee.
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

%d bloggers like this: