The Cross-Entropy Method

Imagine trying to find the lowest valley in a landscape riddled with hills and false bottoms. Random guessing finds valleys slowly. Gradient descent gets stuck in the nearest dip. What if, instead, you scattered thousands of probes at random, kept only the deepest ones, and then asked: what do the survivors have in common? Rebuild your next batch of probes around that common profile — and repeat.

That is the cross-entropy (CE) method in one sentence. Proposed by Reuven Rubinstein in 1999, it originally solved a technical problem in rare-event simulation — how to estimate the probability of a catastrophic failure that almost never happens. The core insight was to adapt the sampling distribution itself: minimize the Kullback–Leibler divergence (equivalently, the cross-entropy) between the current distribution and the ideal one that concentrates mass on the rare event or the optimal solution.

The resulting loop is elegant:

1. Sample a batch of candidate solutions from a parametric distribution (Gaussian means and variances, Bernoulli probabilities for discrete problems, etc.).
2. Evaluate each candidate with your objective function.
3. Select the elite fraction — the top γ% by score.
4. Refit the distribution to maximize the likelihood of the elites.
5. Go to 1.

Each iteration the distribution tightens around better and better regions. The method is not a gradient method — it never differentiates the objective — yet for many smooth and combinatorial problems it converges to near-optimal solutions reliably. It sits alongside simulated annealing and evolutionary algorithms, but with a probabilistic model at the center.

The demo below runs the CE method on a bumpy one-dimensional function. A Gaussian population (blue dots) is drawn each round, scored, and the top 20 % elites (red dots) are kept. The Gaussian is then refit to those elites — watch the mean and spread collapse toward the global minimum.

<div class="controls">
  <label>{{elite_label}}: <span id="eliteVal">20</span>%
    <input type="range" id="elitePct" min="5" max="40" value="20" step="5">
  </label>
  <div class="btns">
    <button id="btnStep" type="button">{{btn_step}}</button>
    <button id="btnRun" type="button">{{btn_run}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<canvas id="cv" width="560" height="220"></canvas>
<div id="info" class="info">{{info_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; background: #fff; }
.controls { display: flex; align-items: center; flex-wrap: wrap; gap: .7rem 1.2rem; margin-bottom: .5rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 110px; accent-color: #1d3557; }
.btns { display: flex; gap: .4rem; }
button { font: 600 13px system-ui; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border-radius: 8px; background: #f4f7fa;
         border: 1px solid #dde4ec; width: 100%; max-width: 560px; }
.info { font-size: .88rem; font-weight: 600; margin-top: .45rem; min-height: 1.3em; color: #1d3557; }

// Code not found

Notice that the distribution initially covers the whole range and may land on local minima. Within a few iterations it zooms in on the deepest basin. Press Step to advance one generation manually, or Run to animate. Reset starts over from a flat prior. Try adjusting the elite % slider to see how a greedy elite fraction (5 %) converges faster but risks locking onto a local minimum, while a loose one (40 %) explores more but converges slowly.

How well does the cross-entropy method actually work?

• Rare-event estimation: in its original domain the CE method has a provably optimal importance-sampling solution. Given a parametric family, the KL-minimizing update is a closed-form maximum-likelihood fit to the elites — no approximation, just an exact refit.
• Discrete optimization: for problems with a finite state space (permutations, bit strings, graph paths) the CE update is still exact MLE over the elite samples. Convergence to the global optimum is proven for certain problem classes when the temperature parameter is annealed carefully.
• Continuous optimization: on smooth, uni-modal objectives the Gaussian CE method converges geometrically. On multimodal landscapes (like the demo above) convergence to a local minimum is common unless the population is large enough to straddle all basins initially.
• No gradient required: the objective is treated as a black box, so CE handles non-differentiable, noisy, or simulation-based cost functions that defeat gradient methods.
• Complexity per iteration: with N samples and an n-dimensional parameter vector, each iteration costs $O(*Nn*)$ evaluations plus $O(*N* \log *N*)$ for sorting the elites — cheap as long as each evaluation is cheap.

The method belongs to the model-based evolutionary algorithms family, alongside estimation-of-distribution algorithms (EDAs) and CMA-ES. Its relationship to non-convex optimization is direct: CE is one of the few metaheuristics with a clean probabilistic derivation rather than a biological metaphor, which makes its behavior easier to analyze and tune.

"Sample the best, refit the model" turns out to be a surprisingly general recipe:

• Network reliability and rare events: estimating the probability that a telecommunications network fails under heavy load — the original application. CE provides variance-reduced estimators orders of magnitude more efficient than naive Monte Carlo.
• Combinatorial routing: the CE method has been applied to the traveling salesman problem and vehicle routing, encoding tours as distributions over permutations and refitting toward short-tour elites. See also the TSP article.
• Scheduling and planning: job-shop scheduling, project scheduling with uncertain durations, and hardware configuration problems all admit CE formulations with competitive results.
• Reinforcement learning: the CE method is used as a policy search algorithm — parameterize a policy (e.g., a neural network), sample many policy instances, keep the ones that score highest on the task, and refit. It was behind early successes on Atari games and robotics before deep RL dominated.
• Finance: pricing exotic options and estimating value-at-risk for rare loss scenarios — domains where Monte Carlo naively needs billions of samples to see even one catastrophic event.
• Hyperparameter optimization: treating model configurations as samples from a categorical/continuous distribution and applying CE to select architectures.

The cross-entropy method is one of those algorithms with an almost unfair simplicity. Its loop — sample, score, keep the elite, refit — requires no gradient, no hand-crafted neighborhood structure, and no metaphor borrowed from physics or evolution. The only ingredient is a parametric family flexible enough to cover the search space.

Yet the loop hides genuine mathematical depth: it minimizes the Kullback–Leibler divergence between distributions at each step, which gives it a variational interpretation shared with variational inference and modern diffusion models. In that sense the CE method is not just an optimizer; it is a lens on how probability distributions can be steered toward rare or excellent events.

Whether the problem is routing, scheduling, reinforcement learning, or estimating the chance of a one-in-a-million failure, the same feedback loop applies. Sample broadly, learn from the winners, narrow down — and repeat until the distribution has nowhere left to hide but the answer.