Talagrand’s Concentration Inequality

We prove a powerful inequality which provides very tight gaussian tail bounds “$e^{-ct^2}$” for probabilities on product state spaces $\Omega^n$. Talagrand’s Inequality has found lots of applications in probability and combinatorial optimization and, if one can apply it, it generally outperforms inequalities like Azzuma-Hoeffding.

Cross Entropy Method

In the Cross Entropy Method, we wish to estimate the likelihood

Here $X$ is a random variable whose distribution is known and belongs to a parametrized family of densities $f( , v)$. Further $S(X)$ is often a solution to an optimization problem.