On the Statistical Learning Ability of Evolution Strategies

ABSTRACT

We explore the ability of Evolution Strategies (ESs) to statistically learn the local landscape. Specifically, we consider ESs operating only with isotropic Gaussian mutations near the optimum and investigate the covariance matrix when constructed out of selected individuals by truncation. Unlike previous studies, we do not assume a Derandomization adaptation scheme, nor do we use Information Geometric Optimization in our proofs. We prove that the statistically constructed covariance matrix over such selected decision vectors has the same eigenvectors as the Hessian matrix. We further prove that when the population size is increased, the covariance becomes proportional to the inverse of the Hessian. We also devise and corroborate an analytic approximation of this covariance matrix. In the framework we consider, this confirms the classical hypothesis that learning the landscape is an inherent property of standard ESs, and that this capability stems only from the usage of isotropic Gaussian mutations and rank-based selection.

References

1. Y. Akimoto. Analysis of a natural gradient algorithm on monotonic convex-quadratic-composite functions. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO '12, pages 1293--1300, New York, NY, USA, 2012. ACM.
2. S.-I. Amari and H. Nagaoka. Methods of Information Geometry, volume 191 of Translations of Mathematical Monographs. American Mathematical Society, 2000.
3. T. B\"ack, C. Foussette, and P. Krause. Contemporary Evolution Strategies. Natural Computing Series. Springer-Verlag Berlin Heidelberg, 2013.
4. H.-G. Beyer. Convergence analysis of evolutionary algorithms that are based on the paradigm of information geometry. Evolutionary Computation, 22(4):679--709, Dec. 2014.
5. E. Castillo, A. S. Hadi, N. Balakrishnan, and J. M. Sarabia. Extreme Value and Related Models with Applications in Engineering and Science. John Wiley and Sons, 2004.
6. P. Embrechts, C. Klüppelberg, and T. Mikosch. Modelling Extremal Events for Insurance and Finance. Springer-Verlag, 1997.
7. A. H. Feiveson and F. C. Delaney. The distribution and properties of a weighted sum of chi squares. Technical report, National Aeronautics and Space Administration, 1968.
8. R. Fisher and L. Tippett. Limiting forms of the frequency distribution of the largest or smallest member of a sample. Proc. Cambridge Philos. Soc., 24:180--190, 1928.
9. S. S. Gupta. Order Statistics from the Gamma Distribution. Technometrics, 2, May 1960.
10. N. Hansen and A. Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation, 9(2):159--195, 2001.
11. P. Moschopoulos and W. Canada. The distribution function of a linear combination of chi-squares. Computers & Mathematics with Applications, 10(4):383--386, 1984.
12. Y. Ollivier, L. Arnold, A. Auger, and N. Hansen. Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles. arXiv:1106.3708v3, 2014.
13. G. Rudolph. On Correlated Mutations in Evolution Strategies. In Parallel Problem Solving from Nature - PPSN II, pages 105--114, Amsterdam, 1992. Elsevier.
14. G. Rudolph. Convergence rates of evolutionary algorithms for a class of convex objective functions. Control and Cybernetics, 26(3), 1997.
15. G. Rudolph. Handbook of Natural Computing: Theory, Experiments, and Applications, chapter Evolutionary Strategies, pages 673--698. Springer-Verlag, Berlin-Heidelberg, Germany, 2012.
16. O. M. Shir, J. Roslund, D. Whitley, and H. Rabitz. Efficient retrieval of landscape hessian: Forced optimal covariance adaptive learning. Physical Review E, 89:063306, Jun 2014.
17. D. Wierstra, T. Schaul, T. Glasmachers, Y. Sun, J. Peters, and J. Schmidhuber. Natural evolution strategies. J. Mach. Learn. Res., 15(1):949--980, Jan. 2014.
18. A. Zhigljavsky and A.vZilinskas. Stochastic Global Optimization. Springer Optimization and Its Applications. Springer US, 2007.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

      • Unsupervised learning

        • Dimensionality reduction and manifold learning

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

  • Probability and statistics

    • Statistical paradigms

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

      • Discrete optimization

        • Optimization with randomized search heuristics

          • Evolutionary algorithms