Optimization connection to sampling theory

Optimization: Connection to sampling theory

Gaussian Adaptation is a powerful and flexible framework for black-box optimization that was developed since the late 1960’s. We have recently presented the connections between Gaussian Adaptation and the leading black-box optimization method on the market today, the CMA Evolution Strategy.


Gaussian Adaptation is rooted in the theory of Maximum Entropy estimation. The newly discovered connection to CMA might thus contribute to understanding the theoretical basis of this powerful optimization strategy.


Moreover, we have recently discovered a connection between Gaussian Adaptation and adaptive Monte Carlo sampling. Monte Carlo methods are at the heart of scientific computing since the seminal works of Metropolis and Hastings. Sampling from distorted, non-linear probability distributions as they occur in complex real-world applications, however, remains challenging. We have recently presented a novel adaptive Monte Carlo sampling algorithm based on Gaussian Adaptation. This new algorithm outperforms the so far best adaptive Monte Carlo sampler, the Adaptive Proposal (AP) algorithm, on the original test problems.


Finally, the newly unraveled connections between CMA, Gaussian Adaptation, and adaptive Monte Carlo sampling might contribute toward a more general theory that links the domains of sampling and black-box optimization. This could provide the missing theoretical results, performance guarantees, and higher-order information.


 

C. L. Müller and I. F. Sbalzarini. Gaussian adaptation revisited — an entropic view on covariance matrix adaptation. In Proc. EvoStar, volume 6024 of Lecture Notes in Computer Science, pages 432–441, Istanbul, Turkey, April 2010. Springer. (Best paper award)

C. L. Müller and I. F. Sbalzarini. Gaussian Adaptation as a unifying framework for continuous black-box optimization and adaptive Monte Carlo sampling. In Proc. IEEE Congress on Evolutionary Computation (CEC), Barcelona, Spain, July 2010.