A view of Estimation of Distribution Algorithms through the lens of Expectation-Maximization
This work offers a theoretical foundation for understanding and improving EDAs, which are used in optimization and machine learning, though it is incremental as it connects existing methods rather than introducing new algorithms.
The paper demonstrates that a broad class of Estimation of Distribution Algorithms (EDAs), such as Covariance Matrix Adaptation, can be formulated as Monte Carlo Expectation-Maximization algorithms, with exact EM equivalence in the infinite sample limit, providing a rigorous statistical framework for analyzing EDAs.
We show that a large class of Estimation of Distribution Algorithms, including, but not limited to, Covariance Matrix Adaption, can be written as a Monte Carlo Expectation-Maximization algorithm, and as exact EM in the limit of infinite samples. Because EM sits on a rigorous statistical foundation and has been thoroughly analyzed, this connection provides a new coherent framework with which to reason about EDAs.