Strongly Efficient Algorithms via Cross Entropy for Heavy- tailed Systems. (with Y. Shi).

Summary:

Cross-Entropy is an adaptive technique, introduced by Reuven Rubinstein, which is used to calibrate an importance sampling distribution for rare event estimation. Not much is known about when the technique works, rigorously. That the technique works means that the iterations can be easily computed and that ultimately the method converges to something that achieves asymptotic optimality in a rare event setting. Now, most studies show that cross-entropy work only empirically and typically in light-tailed settings. This paper shows rigorously that a suitable parametric family works in heavy-tailed settings and it achieves a strong form of asymptotic optimality. What I’ve learned about using cross-entropy is that in order for the technique to work it is really crucial to have a “correct” parametric family to start with and make sure that the iterates explore a set of parameters that are “safe”, just as we do in this paper.

Bibtex:

@Article{BlSh13,

author = { J. Blanchet and Y. Shi},

title = {Strongly Efficient Algorithms via Cross Entropy for Heavy- tailed Systems.},

journal = {Operations Research Letters},

year = {2013},

volume = {41},

pages = {271-276}

}