# Cross-entropy method The cross-entropy method (CEM) is an iterative stochastic optimization technique for rare-event estimation and combinatorial or continuous optimization, using importance sampling and parameter updates based on elite samples. The cross-entropy method (CEM) is a general-purpose Monte Carlo technique for solving difficult optimization and rare-event estimation problems. It was introduced by Reuven Rubinstein in 1997 as a method for estimating probabilities of rare events, and was soon extended to combinatorial and continuous optimization. The method iteratively generates random samples from a parameterized probability distribution, evaluates them, and updates the distribution parameters to concentrate on the best-performing samples, known as the elite set. This approach is particularly effective for problems where the objective function is noisy, non-differentiable, or has many local optima. The core idea of CEM is to minimize the cross-entropy between the sampling distribution and an ideal distribution that places all probability mass on the optimal solution. In practice, this is achieved by repeatedly performing two steps: sampling from the current distribution, and updating the distribution using the maximum likelihood estimate of the elite samples. The method is simple to implement, requires few hyperparameters, and often converges quickly, making it a popular choice in fields such as reinforcement learning, robotics, and operations research. ## Algorithmic Framework The cross-entropy method operates in an iterative loop. Initially, a probability distribution (often a multivariate Gaussian or a categorical distribution) is defined over the solution space. At each iteration, a batch of candidate solutions is drawn from this distribution. Each candidate is evaluated using a scoring function, and the top-performing fraction (typically 10% to 20%) is selected as the elite set. The distribution parameters are then updated to fit these elite samples, typically by computing the sample mean and variance for Gaussian distributions or the empirical frequencies for categorical distributions. To prevent premature convergence, a smoothing parameter is often introduced, blending the new parameters with the previous ones. This smoothing helps maintain exploration and avoids getting stuck in local optima. The process repeats until a stopping criterion is met, such as a maximum number of iterations or a negligible change in the best score. ## Applications in Machine Learning In [machine-learning](https://www.wikiprompt.org/wiki/machine-learning), CEM has been used for hyperparameter optimization, neural architecture search, and training policies in [reinforcement-learning](https://www.wikiprompt.org/wiki/reinforcement-learning) contexts. For example, in [deep-learning](https://www.wikiprompt.org/wiki/deep-learning), CEM can optimize the weights of a small [neural-network](https://www.wikiprompt.org/wiki/neural-network) without backpropagation, which is useful when gradients are unavailable or expensive. It has also been applied to [large-language-model](https://www.wikiprompt.org/wiki/large-language-model) fine-tuning for discrete prompt optimization, where the search space is combinatorial. In [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) research, CEM is often compared with evolutionary strategies and [sgd-variants](https://www.wikiprompt.org/wiki/sgd-variants). Unlike gradient-based methods, CEM does not require the objective to be differentiable, making it suitable for black-box optimization. It has been used in [robotics](https://www.wikiprompt.org/wiki/robotics) for trajectory optimization and in autonomous-driving systems for parameter tuning. ## Relation to Rare-Event Estimation The original motivation for CEM was estimating the probability of rare events, such as system failures or extreme financial losses. In this context, the method uses importance sampling to reduce variance. The algorithm adaptively constructs a sampling distribution that emphasizes the region of interest, allowing accurate estimates with far fewer samples than naive Monte Carlo. This dual use - optimization and estimation - stems from the same mathematical foundation: minimizing the Kullback-Leibler divergence between the sampling distribution and an optimal importance sampling distribution. ## Extensions and Variants Several extensions of CEM have been developed. The continuous version uses Gaussian or mixture-of-Gaussians distributions, while the discrete version handles combinatorial problems like the traveling salesman problem. A notable variant is the improved cross-entropy method, which incorporates a memory of past elite samples to stabilize updates. Another extension is the use of CEM in model-based reinforcement learning, where it plans actions by optimizing a sequence over a learned world model. This approach has been popularized in recent [deep-reinforcement-learning](https://www.wikiprompt.org/wiki/deep-reinforcement-learning) algorithms, such as the Model-Based Policy Optimization (MBPO) framework. CEM has also been combined with [curriculum-learning](https://www.wikiprompt.org/wiki/curriculum-learning), where the difficulty of samples is gradually increased, and with [data-augmentation](https://www.wikiprompt.org/wiki/data-augmentation) for robust optimization. In [bayesian-optimization](https://www.wikiprompt.org/wiki/bayesian-optimization), CEM can serve as an acquisition function optimizer. ## Practical Considerations When applying CEM, the choice of distribution family and the elite fraction are critical. A too-small elite fraction can lead to premature convergence, while a too-large one slows progress. The smoothing parameter, often set between 0.5 and 0.9, balances exploration and exploitation. For high-dimensional problems, the number of samples per iteration must scale accordingly, which can become computationally expensive. Despite these challenges, CEM's simplicity and robustness have made it a staple in the optimization toolbox. In practice, CEM is often used as a baseline in research papers, and its performance is comparable to more complex methods like [bayesian-optimization](https://www.wikiprompt.org/wiki/bayesian-optimization) on many benchmark problems. It is implemented in several open-source libraries, including the `cma` package for Python, though the classic CEM is distinct from CMA-ES (Covariance Matrix Adaptation Evolution Strategy), which is a related but separate algorithm. ## See Also - evolutionary-algorithm - monte-carlo-method - [reinforcement-learning](https://www.wikiprompt.org/wiki/reinforcement-learning) - black-box-optimization --- Source: https://www.wikiprompt.org/wiki/cross-entropy-method License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/) Last updated: 2026-09-14T04:27:49.742807+00:00