Stochastic search using the natural gradient

ABSTRACT

To optimize unknown 'fitness' functions, we present Natural Evolution Strategies, a novel algorithm that constitutes a principled alternative to standard stochastic search methods. It maintains a multinormal distribution on the set of solution candidates. The Natural Gradient is used to update the distribution's parameters in the direction of higher expected fitness, by efficiently calculating the inverse of the exact Fisher information matrix whereas previous methods had to use approximations. Other novel aspects of our method include optimal fitness baselines and importance mixing, a procedure adjusting batches with minimal numbers of fitness evaluations. The algorithm yields competitive results on a number of benchmarks.

REFERENCES

• 1: Shun-Ichi Amari, Natural gradient works efficiently in learning, Neural Computation, v.10 n.2, p.251-276, Feb. 15, 1998 [doi>10.1162/089976698300017746]
• 2: Amari, S., Cichocki, A., & Yang, H. (1995). A new learning algorithm for blind signal separation. Advances in Neural Information Processing Systems (NIPS95), 8, 757--763.
• 3: Amari, S., & Douglas, S. C. (1998). Why natural gradient? Proceedings of the 1998 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP98), 2, 1213--1216.
• 4: Faustino Gomez , Risto Mikkulainen, Incremental evolution of complex general behavior, Adaptive Behavior, v.5 n.3-4, p.317-342, Winter/Spring 1997 [doi>10.1177/105971239700500305]
• 5: Gomez, F., Schmidhuber, J., & Miikkulainen, R. (2006). Efficient non-linear control through neu-roevolution. Proceedings of the 16th European Conference on Machine Learning (ECML06), 4212, 654--662.
• 6: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 7: Kakade, S. (2001). A natural policy gradient. In Advances in neural information processing systems (NIPS01), 12, 1531--1538.
• 8: David E. Moriarty , Risto Mikkulainen, Efficient reinforcement learning through symbiotic evolution, Machine Learning, v.22 n.1-3, p.11-32, Jan./Feb./March 1996 [doi>10.1007/BF00114722]
• 9: Jan Peters , Stefan Schaal, Natural Actor-Critic, Neurocomputing, v.71 n.7-9, p.1180-1190, March, 2008 [doi>10.1016/j.neucom.2007.11.026]
• 10: Jan Reinhard Peters , Stefan Schaal, Machine learning of motor skills for robotics, University of Southern California, Los Angeles, CA, 2007
• 11: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 12: Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K., Chen, Y. P., Auger, A., & Tiwari, S. (2005). Problem definitions and evaluation criteria for the cec 2005 special session on real-parameter optimization (Technical Report). Nanyang Technological University, Singapore.
• 13: Sun, Y., Wierstra, D., Schaul, T., & Schmidhuber, J. (2009). Efficient natural evolution strategies. To appear in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO09).
• 14: Wieland, A. (1991). Evolving neural network controllers for unstable systems. Proceedings of the International Joint Conference on Neural Networks (IJCNN91), 2, 667--673.
• 15: Daan Wierstra , Tom Schaul , Jan Peters , Jürgen Schmidhuber, Fitness Expectation Maximization, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_34]
• 16: Wierstra, D., Schaul, T., Peters, J., & Schmidhuber, J. (2008b). Natural evolution strategies. Proceedings of the Congress on Evolutionary Computation (CEC08), Hongkong, 3381--3387.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Stochastic programming

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory