Finite-Sample Analysis of Information Geometric Optimization With Isotropic Gaussian Distribution on Convex Quadratic Functions
| Autor: | Shinichi Shirakawa, Youhei Akimoto, Kento Uchida |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Hessian matrix
Deterministic algorithm Gaussian 02 engineering and technology Function (mathematics) Quadratic function Standard deviation Square (algebra) Theoretical Computer Science symbols.namesake Computational Theory and Mathematics Sample size determination 0202 electrical engineering electronic engineering information engineering symbols Applied mathematics 020201 artificial intelligence & image processing Software Mathematics |
| Zdroj: | IEEE Transactions on Evolutionary Computation. 24:1035-1049 |
| ISSN: | 1941-0026 1089-778X |
| Popis: | We theoretically analyze the information geometric optimization (IGO), which is a unified framework of stochastic search algorithms for black-box optimization. The IGO framework has two parameters: 1) the learning rate and 2) the sample size, and they influence the behavior of the algorithm. We investigate the strategy parameters of the IGO with the family of isotropic Gaussian distributions on a general convex quadratic function. Compared to the previous theoretical works, where an infinite sample size is assumed and the deterministic algorithm dynamics is studied, we investigate the expected improvement of the algorithm with a finite sample size. The analysis finds that the relative decrease rates of the distance from the distribution mean to the landscape optimum and the distribution standard deviation must be the same, which we observe in practice, while the analysis based on an infinite sample size failed to obtain. We derive these rates explicitly as a function of the eigenvalues of the Hessian of the objective function and the strategy parameters. We also derive the stable value of the ratio of the square distance to the optimum over the distribution variance, as well as the conditions that the stable value exists. These theoretical values coincide with our numerical simulations. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|