Natural gradient, fitness modelling and model selection: A unifying perspective

The geometric framework based on Stochastic Relaxation allows to describe from a common perspective different model-based optimization algorithms that make use of statistical models to guide the search for the optimum. In this paper Stochastic Relaxation is used to provide theoretical results on Estimation of Distribution Algorithms (EDAs). By the use of Stochastic Relaxation we show how the estimation of the fitness model by least squares linear regression corresponds to the estimation of the natural gradient. This equivalence allows to simultaneously perform model selection and robust estimation of the natural gradient. Finally, we interpet Linear Programming relaxation as an example of Stochastic Relaxation, with respect to the regular gradient.