Search Distributions and Natural Gradient Descent
Speaker: Tom Schaul,
Date: Thursday, February 17 2011
Time: 1:00PM to 2:00PM
Location: Kiva, 32-G449
Host: Leslie Kaelbling, MIT CSAIL
Contact: Teresa Cataldo, email@example.com
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