Skip to Main content Skip to Navigation
Poster communications

Sampling-based optimization with mixtures

R. Bardenet 1 Balázs Kégl 1, 2, 3
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Sampling-based Evolutionary Algorithms (EA) are of great use when dealing with a highly non-convex and/or noisy optimization task, which is the kind of task we often have to solve in Machine Learning. Two derivative-free examples of such methods are Estimation of Distribution Algorithms (EDA) and techniques based on the Cross-Entropy Method (CEM). One of the main problems these algorithms have to solve is finding a good surrogate model for the normalized target function, that is, a model which has sufficient complexity to fit this target function, but which keeps the computations simple enough. Gaussian mixture models have been applied in practice with great success, but most of these approaches lacked a solid theoretical founding. In this paper we describe a sound mathematical justification for Gaussian mixture surrogate models, more precisely we propose a proper derivation of an EDA/CEM algorithm with mixture updates using Expectation Maximization techniques. It will appear that this algorithm resembles the recent Population MCMC schemes, thus reinforcing the link between Monte- Carlo integration methods and sampling-based optimization. We will concentrate throughout this paper on continuous optimization.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Sabine Starita <>
Submitted on : Monday, March 28, 2011 - 3:41:49 PM
Last modification on : Thursday, July 8, 2021 - 3:48:15 AM
Long-term archiving on: : Wednesday, June 29, 2011 - 2:57:57 AM


Files produced by the author(s)


  • HAL Id : in2p3-00580580, version 1


R. Bardenet, Balázs Kégl. Sampling-based optimization with mixtures. OPT 2009: 2nd NIPS Workshop on Optimization for Machine Learning, Dec 2009, Whistler, Canada. ⟨in2p3-00580580⟩



Record views


Files downloads