CSAIL Event Calendar

Search Distributions and Natural Gradient Descent

Among the most challenging optimization problems are black-box functions, inaccessible to analysis except through function evaluations. Evolution strategies have become the method of choice in this field, as they combine searching near the best individuals found with replicating mutations that led to improvements.

We transfer these concepts from evolutionary computation to stochastic search by replacing populations with search distributions. This allows us to perform gradient descent (towards highest expected fitness) on the parameters of the distribution. Yet, doing this naïvely fails to deliver robust results, an issue we tackle by instead following the natural gradient, which appropriately normalizes the update step with respect to uncertainty. The resulting family of algorithms, “Natural Evolution Strategies” (NES) is at once well founded and highly versatile; in fact we can employ any parameterized distribution as search distribution.

Improving the method further, we significantly reduce the algorithm’s computational complexity (for Gaussian distributions) through a change of coordinates. Also, we introduce two novel techniques that automatically tune learning rate and batch size to the problem at hand, which increases robustness and reduces the number of required function evaluations.

See other events happening in February 2011