Analysis of Information Geometric Optimization
with Isotropic Gaussian Distribution Under Finite Samples
Kento Uchida

Youhei Akimoto

Shinichi Shirakawa

Yokohama National University
Yokohama, Japanuchida-kento-nc@ynu.jp

University of Tsukuba
Tsukuba, Japanakimoto@cs.tsukuba.ac.jp

Yokohama National University
Yokohama, Japanshirakawa-shinichi-bg@ynu.ac.jp

ABSTRACTIn this article, we theoretically investigate the convergence properties of the information geometric optimization (IGO) algorithm
given the family of isotropic Gaussian distributions on the spherefunction. Differently from previous studies, where the exact natural
gradient is taken, i.e., the infinite samples are assumed, we consider
the case that the natural gradient is estimated from finite samples.
We derive the rates of the expected decrease of the squared distanceto the optimum and the variance parameter as functions of thelearning rates, dimension, and sample size. From the rates of decrease deduces that the rates of decreases of the squared distance tothe optimum and the variance parameter must agree for geometricconvergence of the algorithm. In other words, the ratio between thesquared distance to the optimum and the variance must be stable,
which is observed empirically but is not derived in the previous
theoretical studies. We further derive the condition on the learning
rates that the rates of decreases agree and derive the stable valueof the ratio. We confirm in simulation that the derived rates ofdecreases and the stable value of the ratio well approximate thebehavior of the IGO algorithm.

CCS CONCEPTS• Theory of computation → Stochastic control and optimization; Stochastic approximation;

KEYWORDS
Natural Gradient, Finite Samples, Convergence Property, Information Geometric Optimization, Theory
ACM Reference Format:
Kento Uchida, Youhei Akimoto, and Shinichi Shirakawa. 2018. Analysis ofInformation Geometric Optimization with Isotropic Gaussian Distribution
Under Finite Samples. In GECCO ’18: Genetic and Evolutionary Computation
Conference, July 15–19, 2018, Kyoto, Japan. ACM, New York, NY, USA, 8 pages.
https://doi.org/10.1145/3205455.3205487

1

INTRODUCTION

Information geometric optimization (IGO) [14] is a unified framework of stochastic search algorithms for optimization problems
on an arbitrary domain. The IGO algorithm takes a parametrizedfamily of probability distributions as sampling distributions. Starting from a given initial distribution, the IGO algorithm repeats
GECCO ’18, July 15–19, 2018, Kyoto, Japan© 2018 Association for Computing Machinery.
This is the author’s version of the work. It is posted here for your personal use.
Not for redistribution. The definitive Version of Record was published in GECCO’18: Genetic and Evolutionary Computation Conference, July 15–19, 2018, Kyoto, Japan,
https://doi.org/10.1145/3205455.3205487.

sampling candidate solutions, evaluating them on an objective, andupdating the distribution parameters until it finds a satisfactory
solution. The parameter update follows the steepest ascent stepin the parameter space of the probability distributions equippedwith the Fisher metric. The steepest ascent direction in such a space
is known to be computed by the inverse Fisher information matrix times the vanilla gradient, called the natural gradient [5]. The
natural gradient is estimated by Monte Carlo using the candidate
solutions. The IGO framework recovers several known evolutionary
algorithms such as the pure rank-𝜇 update covariance matrix adaptation evolution strategy (CMA-ES) [12] and the population-based
incremental learning (PBIL) [8].
The objective of this paper is to investigate the effect of theparameters of the IGO algorithm on its behavior. When instantiating an IGO algorithm, we have two important parameters, thesample size (aka population size, number of candidate solutions at
each iteration) and the learning rates for the distribution parameter updates. However, the design principle of the IGO algorithm
does not include the guide for these parameter settings. Since theseparameters are critical in the performance of the algorithm, it isimportant to understand the influence of these parameters on the
distribution parameter update.
Some variants of the IGO algorithm with a family of multivariate
Gaussian distribution in continuous domain has been analyzed in
the literature [1, 2, 9, 11]. Since the analysis of stochastic algorithms
in continuous domain in general is usually mathematically intricate,different levels of approximations have been applied to model the
dynamics of the real algorithms. One way is to consider the deterministic ordinary differential equation associated with the infinite
sample size and the infinitesimal learning rate of the distribution
parameter update [2, 9, 11]. Another way is to consider the deterministic difference equation associated with the infinite sample
size but a finite learning rate [1]. In the latter case, the geometricconvergence of the mean vector and the covariance matrix of thesampling distribution is derived. However, these theoretical results
do not well describe the behavior of the real IGO algorithm. Moreprecisely, it is observed that the convergence rate of the standard
deviation of the sampling distribution is the same as that of the
distance between the optimal solution and the mean vector, while
the theoretical results under the infinite samples tell that theseconvergence speeds can be different. It indicates that we need toincorporate the stochastic property of the algorithm in some way
into the analysis.
Different analysis methodologies show that the rates of geometric convergence of the standard deviation and the distance to the
optimum must be the same. Markov chain analysis [7], for example,
shows that the ratio between the distance to the optimum and theGECCO ’18, July 15–19, 2018, Kyoto, Japan

Kento Uchida, Youhei Akimoto, and Shinichi Shirakawa

standard deviation admits a stationary distribution, meaning thatthe distance to the optimum and the standard deviation converges
at the same rate. However, it is very complicated and difficult to derive the influence of the strategy parameters such as the sample size
and the learning rates on the rate of convergence and the stationary
distribution of the ratio explicitly. Quality gain or progress rate
analysis, which considers a single step expected behavior, provides
the optimal step-size given a mean vector in an explicit form andshows the optimal recombination weights in the evolution strategy in the limit of search space dimension to infinity [3, 6]. The
analysis methodology most related to this paper is probably theso-called dynamical systems approach [13]. Roughly speaking, it
describes the algorithm dynamics by a lower number of parametersand studies the steady-state behavior. Nonetheless, these analysis
has not been applied to the IGO algorithms.
In this paper, we analyze the IGO algorithm given the family of
isotropic Gaussian distributions solving the sphere function. Differently from the previous theoretical studies of the IGO algorithms
where the infinite samples are assumed, we consider the expected
dynamics of the IGO algorithm with finite samples. Taking into account the variance and covariance of the estimated natural gradient
under finite samples, we show that the rate of the expected decreaseof the squared distance to the optimum depends on the ratio of
the squared distance from the distribution mean to the optimum
and the distribution variance. This implies that the ratio needs tobe stable for the algorithm to converge geometrically, which isempirically observed but is not derived in the previous analysis
assuming the infinite samples. Then, we derive the stable valueof the ratio and the conditions on the learning rates such that theratio admits a stable value. The simulation results show that thetheoretical results derived in this paper well describe the behaviorof the real algorithm.
The rest of this paper is organized as follows. In Section 2, we
describe the IGO framework. In Section 3, we investigate the convergence properties under infinite samples as well as under finite
samples on the sphere function. In Section 4, we study the conditionon the learning rates that the expected decrease of the squared distance from the distribution mean to the optimum and the expected
decrease of the distribution variance agree. In Section 5, the derived
results are compared to the behavior of the real IGO algorithm insimulation, and we confirm that they match precisely. Finally, we
discuss the simulation results and the future works in Section 6 andconclude this paper in Section 7.

2

INFORMATION GEOMETRIC
OPTIMIZATION

Information geometric optimization (IGO) is a unified frameworkof stochastic algorithms for black-box optimization on an arbitrary
search space 𝑋 . We assume an objective function 𝑓 : 𝑋 → R to
be minimized on the search space 𝑋 . Given a family of probability
distributions {𝑃𝜃 } on 𝑋 , IGO transforms the original minimization
problem into the maximization of the expected value of a utility
function 𝑢 over the parameter space of {𝑃𝜃 } asarg max E𝑃𝜃 [𝑢 (𝑥 )] .
𝜃The utility function 𝑢 is a strictly decreasing transformation of 𝑓 ,that means 𝑢 (𝑥 ) > 𝑢 (𝑥 ′ ) for all 𝑓 (𝑥 ) < 𝑓 (𝑥 ′ ).
IGO updates the parameter of the probability distribution along
the natural gradient direction which is the steepest direction withrespect to the Fisher metric [5]. The Fisher metric is a Riemannian
metric defined by the Fisher information matrix. Let 𝑝𝜃 be theprobability density function induced by 𝑃𝜃 , the Fisher information
matrix is defined as∫ 𝜕 ln 𝑝𝜃 (𝑥 ) 𝜕 ln 𝑝𝜃 (𝑥 ) T
𝐹 (𝜃 ) =𝑝𝜃 (𝑥 )d𝑥 .
(2)
𝜕𝜃
𝜕𝜃
The natural gradient is given by the product of the inverse of theFisher information matrix 𝐹 and the vanilla gradient, derived as
˜ 𝑃 [𝑢 (𝑥 )] = 𝐹 −1 (𝜃 )∇E𝑃 [𝑢 (𝑥 )]
∇E
𝜃
𝜃
∫
=
𝑢 (𝑥 )( ∇˜ ln 𝑝𝜃 (𝑥 ))𝑝𝜃 (𝑥 )d𝑥

(3)
(4)

where ∇˜ ln 𝑝𝜃 (𝑥 ) = 𝐹 −1 (𝜃 )∇ ln 𝑝𝜃 (𝑥 ). However, the above integral
cannot be performed analytically since 𝑓 is black-box in our setting.
Instead, we take the Monte Carlo estimate using 𝑛 i.i.d. samples
drawn from probability distribution 𝑃𝜃 , namely,𝑛Õ˜ 𝑃 [𝑢 (𝑥 )] ≈ 1∇E𝑢 (𝑥𝑖 ) ∇˜ ln 𝑝𝜃 (𝑥𝑖 ) .
𝜃
𝑛 𝑖=1

(5)

Introducing the learning rate 𝜂 𝑡 at iteration 𝑡, the update rule of
IGO reads𝑛𝜃 𝑡 +1 = 𝜃 𝑡 +𝜂𝑡 Õ
𝑢 (𝑥𝑖 ) ∇˜ ln 𝑝𝜃 (𝑥𝑖 ) .
𝑛 𝑖=1

(6)

In this paper, we analyze the IGO algorithm given the family of
isotropic Gaussian distributions on 𝑋 = R𝑑 . The isotropic Gaussian
distribution, N (𝑚, 𝛽 ), is a multivariate Gaussian distribution where
the covariance matrix is the identity times a scalar. We parametrize
it by its mean vector 𝑚 ∈ R𝑑 and the variance parameter 𝛽 ∈ R>0 ,i.e., 𝜃 = (𝑚 T, 𝛽 ) T . The probability density function is written as1∥𝑥 − 𝑚 ∥ 2
𝑝𝜃 (𝑥 ) = p
exp −
.
(7)
2𝛽
( 2𝜋 𝛽 )𝑑In the analysis we set the utility function as the negative of
the objective function, 𝑢 = −𝑓 , which is also used in previous
theoretical studies [1, 9]. The estimated negative natural gradientof each parameter at iteration 𝑡 is written as𝑛Õd𝑡 = 1∇˜ 𝑚 E𝑃𝜃 [𝑓 (𝑥 )] ≈ 𝛿𝑚𝑓 (𝑥𝑖 )(𝑥𝑖 − 𝑚𝑡 )
𝑛 𝑖=1


𝑛
Õ
∥𝑥𝑖 − 𝑚𝑡 ∥ 2
d𝑡 = 1∇˜ 𝛽 E𝑃𝜃 [𝑓 (𝑥 )] ≈ 𝛿𝛽𝑓 (𝑥𝑖 )
− 𝛽𝑡
𝑛 𝑖=1
𝑑

(8)

(9)

and the update rules read𝑡 d𝑡
𝑚𝑡 +1 = 𝑚𝑡 − 𝜂 𝑚
𝛿𝑚

(10)

d𝑡 ,
𝛽 𝑡 +1 = 𝛽 𝑡 − 𝜂 𝑡𝛽 𝛿𝛽

(11)

(1)
𝑡 , 𝜂𝑡 ∈ R
where 𝜂 𝑚
>0 are the learning rates.
𝛽Analysis of Information Geometric Optimization
with Isotropic Gaussian Distribution Under Finite Samples

3

GECCO ’18, July 15–19, 2018, Kyoto, JapanCONVERGENCE ANALYSIS

We investigate the convergence properties of the IGO algorithm (10)and (11) on a convex quadratic function 𝑓 (𝑥 ) = (𝑥 − 𝑥 ∗ ) T𝐴(𝑥 − 𝑥 ∗ ),where 𝐴 is a positive definite symmetric matrix and 𝑥 ∗ is global
optimum solution, with a special focus on the sphere function𝑓 (𝑥 ) = ∥𝑥 − 𝑥 ∗ ∥ 2 . Under the isotropic Gaussian distribution, theexpected objective function value is
E𝑃𝜃 [𝑓 (𝑥 )] = 𝛽 Tr(𝐴) + (𝑚 − 𝑥 ∗ ) T𝐴(𝑚 − 𝑥 ∗ ) .

(12)

Therefore, the optimal parameter is 𝜃 ∗ = (𝑥 ∗ T, 0) T and we aregoing to investigate how 𝜃 𝑡 approaches the optimal parameter.
Since the following result is invariant under any translation, we
assume without loss of generality (w.l.g.) that the optimum of theobjective function 𝑓 is located at 𝑥 ∗ = 0.

3.1

Analysis of Infinite Sample Model

The Monte Carlo estimates of the component-wise natural gradients, (8) and (9), are both unbiased and consistent. Therefore, in thelimit of the sample size 𝑛 to infinity leads the estimates (8) and (9)to converge to∇˜ 𝑚 E𝑃𝜃 [𝑓 (𝑥 )] = 2𝛽 𝑡 𝐴𝑚𝑡

(13)

Tr(𝐴)
∇˜ 𝛽 E𝑃𝜃 [𝑓 (𝑥 )] = 2(𝛽 𝑡 ) 2
,
𝑑

(14)

𝑐𝑚
,
2𝜆1 (𝐴)𝛽 𝑡𝑐𝛽,
𝜂 𝑡𝛽 =
2𝜆1 (𝐴)𝛽 𝑡

(15)
(16)

where 𝑐𝑚 and 𝑐 𝛽 are constant values and 𝜆𝑘 (𝐴) is the 𝑘-th largest
eigenvalue of 𝐴. This setting serves as the normalization of theobjective function values by 2𝜆1 (𝐴)𝛽 𝑡 . In other words, our utility
is 𝑢 (𝑥) = −𝑓 (𝑥)/(2𝜆1 (𝐴)𝛽 𝑡 ) instead of 𝑢 (𝑥) = −𝑓 (𝑥) and the𝑡 and 𝜂 𝑡 , respectively.
learning rates are 𝑐𝑚 and 𝑐 𝛽 instead of 𝜂 𝑚𝛽Similar settings are found in [1, 9].
The following proposition proves the geometric convergenceof each parameter with the rate of convergence depending on thelearning rate.
Proposition 3.1. Consider the deterministic sequence of 𝑚𝑡 andd𝑡 replaced by (13) andd𝑡 and 𝛿𝛽𝛽 𝑡 defined by (10) and (11) with 𝛿𝑚(14), respectively. Then, for 0 < 𝑐𝑚 < 2 and 0 < 𝑐 𝛽 < 1, both ∥𝑚𝑡 ∥ 2and 𝛽 𝑡 converge towards zero with the rates of convergence∥𝑚𝑡 +1 ∥ 2≤∥𝑚𝑡 ∥ 2≤ max (1 − 𝑐𝑚 ) 2, (1 − 𝑐𝑚 Cond−1 (𝐴)) 2

𝜆 (𝐴)min 1 − 𝑐𝑚 𝑘
𝜆1 (𝐴)
𝑘

2

(17)

and
𝛽 𝑡 +1
Tr(𝐴)/𝑑= 1 − 𝑐𝛽,𝛽𝑡𝜆1 (𝐴)
where Cond(𝐴) = 𝜆1 (𝐴)/𝜆𝑑 (𝐴) is the condition number of 𝐴.

Since 𝜆1 (𝐴) ≥ Tr(𝐴)/𝑑, the variance parameter always converges
when 0 < 𝑐 𝛽 < 1 is satisfied.
The square norm of the updated mean vector is𝑡 𝑡∥𝑚𝑡 +1 ∥ 2 = 𝑚𝑡 − 2𝜂 𝑚
𝛽 𝐴𝑚𝑡

2
𝑐𝑚
𝑡 T
= (𝑚 ) I𝑑 −𝐴 𝑚𝑡 .
𝜆1 (𝐴)
2

(18)

(20)
(21)

The eigenvalues of the matrix inside the parentheses are upperbounded by the larger of 1 − 𝑐𝑚 and 1 − 𝑐𝑚 /Cond(𝐴), which leadsto
∥𝑚𝑡 +1 ∥ 2≤ max (1 − 𝑐𝑚 ) 2, (1 − 𝑐𝑚 Cond−1 (𝐴)) 2 .
(22)∥𝑚𝑡 ∥ 2
Note that the right-hand side is strictly smaller than 1, implying
geometric convergence. Moreover, the lower bound is
2!



∥𝑚𝑡 +1 ∥ 2
𝜆𝑘 (𝐴) 2
𝑐𝑚
𝐴
=
min
1
−
𝑐
. (23)
≥
𝜆
I
−
𝑚
𝑑
𝑑
𝜆1 (𝐴)𝜆1 (𝐴)∥𝑚𝑡 ∥ 2𝑘□This ends the proof.

respectively. In this section, we set the learning rates as𝑡𝜂𝑚=Proof. The convergence rate of the variance parameter 𝛽 𝑡 is asfollows:𝑡𝑡 ˜
𝛽 𝑡 +1 𝛽 − 𝜂 𝛽 ∇𝛽 E𝑃𝜃 [𝑓 (𝑥 )]Tr(𝐴)/𝑑== 1 − 𝑐𝛽
.
(19)
𝛽𝑡
𝛽𝑡
𝜆1 (𝐴)

Proposition 3.1 implies that both 𝑐𝑚 and 𝑐 𝛽 must be strictly𝑡greater than zero for geometric convergence. In other words, 𝜂 𝑚𝑡𝑡
and 𝜂 𝛽 must be in Θ(1/𝛽 ). Therefore, the scaling of the learning
rates introduced in (15) and (16) are necessary for geometric convergence of the IGO algorithm. This is explained as follows. The
function value 𝑓 (𝑥) is proportional to 𝛽 𝑡 (given that ∥𝑚𝑡 ∥ 2 ∝ 𝛽 𝑡 )and the length of the natural gradient scales down as 𝑓 (𝑥) does
if 𝑢 = −𝑓 . The Θ(1/𝛽 𝑡 ) learning rates are necessary to preventthe natural gradient from scaling down depending on the function
value scale. Utility transformations such as truncation selection
keep the utility values constant and itself serves as the normalization of the natural gradient [9]. Therefore, we observe geometricconvergence of IGO algorithms with truncation selection utility𝑡 and 𝜂 𝑡 in practice.
and constant 𝜂 𝑚𝛽
If we consider the case 𝐴 = I𝑑 , i.e., the sphere function 𝑓 (𝑥 ) =∥𝑥 ∥ 2 , then the rate of convergence of each parameter reads∥𝑚𝑡 +1 ∥ 2= (1 − 𝑐𝑚 ) 2∥𝑚𝑡 ∥ 2𝛽 𝑡 +1= 1 − 𝑐𝛽 .
𝛽𝑡

(24)
(25)

This result corresponds what is derived in [1], where an arbitrary
symmetric positive definite covariance matrix is considered insteadof 𝛽 . It says that we can control the convergence rates of 𝑚𝑡 and 𝛽 𝑡
independently by setting different values for 𝑐𝑚 and 𝑐 𝛽 . However,this is not true for a real algorithm with a finite sample size, as we
will observe in simulation in Section 5. More precisely, ∥𝑚 ∥ 2 /𝛽must be stable, which is not only observed in empirical studies but
also implied by theoretical results such as Markov chain analysis[7] and progress rate and quality gain analysis [3, 4, 6]. This is notachieved in the analysis of the infinite sample size model of the
IGO algorithm.

GECCO ’18, July 15–19, 2018, Kyoto, Japan

3.2

Kento Uchida, Youhei Akimoto, and Shinichi Shirakawa

Estimation Variance of Monte CarloIn the infinite sample model, the estimation variance of the natural
gradient ((8) and (9)) due to a finite sample size, 𝑛, is not taken
into account. This is considered one of the reasons that we fail toobtain a result that describes the behavior of a real algorithm. The
following lemma shows the covariance matrix and the varianceof the components of the natural gradient estimates, which areproportional to 1/𝑛.
Lemma 3.2. The covariance and the variance of the components of
estimated negative natural gradient, (8) and (9), on a convex quadratic
function 𝑓 (𝑥 ) = 𝑥 T𝐴𝑥 ared𝑡 ] = 1 𝑉𝑚 (𝑚𝑡 , 𝛽 𝑡 , 𝐴)
Cov[𝛿𝑚𝑛1d𝑡Var[𝛿𝛽 ] = 2 𝑉𝛽 (𝑚𝑡 , 𝛽 𝑡 , 𝐴) ,𝑛𝑑
where 𝑉𝑚 and 𝑉𝛽 are defined as

Next, we consider the expected dynamics of the mean vector∥𝑚𝑡 ∥ 2 . Note that the expected value of ∥𝑚𝑡 ∥ decreases when the
expected value of ∥𝑚𝑡 ∥ 2 decreases. When updating the mean vector
along (10), the expected value of ∥𝑚𝑡 +1 ∥ 2 is written asE[∥𝑚𝑡 +1 ∥ 2 ] =
h
i
h
i
𝑡
d𝑡 + (𝜂 𝑡 ) 2 E ∥𝛿𝑚d𝑡 ∥ 2 .
∥𝑚𝑡 ∥ 2 −2𝜂 𝑚(𝑚𝑡 ) T E 𝛿𝑚𝑚

The next theorem shows the rate of decrease of the expected squared
distance between the mean vector to the optimum.
Theorem 3.4. Consider the single update of 𝑚 in (10) given 𝑚𝑡
and 𝛽 𝑡 on the sphere function. The expected decrease of ∥𝑚 ∥ 2 is given
by

(26)

𝑐2
E[∥𝑚𝑡 +1 ∥ 2 ]= (1 − 𝑐𝑚 ) 2 + 𝑚 𝐾 ,
𝑡
2
4𝑛
∥𝑚 ∥

(27)

𝑉𝑚 (𝑚, 𝛽, 𝐴) =4𝛽 3 Tr(𝐴)𝐴 + 8𝛽 3𝐴2+ 𝛽 3 2Tr(𝐴2 ) + Tr2 (𝐴) I𝑑(28)+ 𝛽 𝑡 I𝑑 (𝑚 T𝐴𝑚) 2𝑉𝛽 (𝑚, 𝛽, 𝐴) =2𝛽 4 (𝑑 + 12) Tr2 (𝐴) + 2Tr(𝐴2 )+ 4𝛽 3 (𝑑 + 4) Tr(𝐴)𝑚 T𝐴𝑚 + 2∥𝐴𝑚 ∥ 2𝛽𝑡∥𝑚𝑡 ∥ 2
2
.
+
2(𝑑
+
4𝑑
+
2)
+
𝑑
𝛽𝑡
∥𝑚𝑡 ∥ 2T

+ 2𝛽 𝑑 (𝑚 𝐴𝑚)(36)

Note the decreasing rate depends on the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 .
The right-hand side of (35) is less than 1 if and only if the following
two conditions hold:• Condition on ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡p1 𝑀 (𝑑, 𝑛) − 𝑀 2 (𝑑, 𝑛) − 𝑑 2 (𝑑 + 2)(𝑑 + 4)
𝑑

p
1 
∥𝑚𝑡 ∥ 2<𝑀 (𝑑, 𝑛) + 𝑀 2 (𝑑, 𝑛) − 𝑑 2 (𝑑 + 2) (𝑑 + 4) ,
<
𝑡
𝛽
𝑑
(37)
where

(29)
2

(35)

where
𝐾 = (𝑑 + 4)(𝑑 + 2)𝑑+ 2𝛽 2 (Tr(𝐴) I𝑑 + 2𝐴)𝑚 T𝐴𝑚
+ 4𝛽 2 ∥𝐴𝑚 ∥ 2 I𝑑 + (𝐴𝑚)(𝐴𝑚) T

(34)

2


𝑀 (𝑑, 𝑛) = 2𝑛2
− 1 − (𝑑 2 + 4𝑑 + 2) .

(38)

𝑐𝑚
4

2

− 4𝛽 Tr (𝐴)3.3

Analysis of Finite Sample Algorithm

In the following, we focus on the case 𝐴 = I𝑑 . This means theobjective function is the sphere function 𝑓 (𝑥 ) = ∥𝑥 ∥ 2 . Moreover,
we define 𝑐𝑚 , 𝑐 𝛽 ∈ R>0 similarly to Section 3.1,𝑡𝜂𝑚=

𝜂 𝑡𝛽 =𝑐𝑚2𝛽 𝑡
𝑐𝛽• Condition on learning rate coefficient 𝑐𝑚 (necessary and sufficient condition for (37) to have a nonzero interval)
4𝑛
0 < 𝑐𝑚 <,(39)𝑠 (𝑑, 𝑛)wherep𝑠 (𝑑, 𝑛) = 𝑑 2 + 4𝑑 + 2 + 𝑑 (𝑑 + 2)(𝑑 + 4) + 2𝑛 .
(40)

(30)
Proof. On the sphere function, 𝑉𝑚 in Lemma 3.2 is
.

(31)

2𝛽 𝑡

Then, we consider the expected progress of ∥𝑚𝑡 +1 ∥ 2 and 𝛽 𝑡 +1 given
𝑚𝑡 and 𝛽 𝑡 .
First, we consider the expected dynamics of the variance parameter 𝛽 𝑡 . The expected value of 𝛽 𝑡 +1 is simply
E[𝛽 𝑡 +1 ] = 𝛽 𝑡 (1 − 𝑐 𝛽 ) ,(32)

and the rate of decrease of the variance parameter is given in thenext theorem.

𝑉𝑚 (𝑚𝑡 , 𝛽 𝑡 , I𝑑 ) =(𝛽 𝑡 ) 3 (𝑑 + 4)(𝑑 + 2) I𝑑+ 2(𝛽 𝑡 ) 2 ∥𝑚𝑡 ∥ 2 (𝑑 + 4) I𝑑 + 2𝑚𝑡 (𝑚𝑡 ) T+ 𝛽 𝑡 ∥𝑚𝑡 ∥ 4 I𝑑and the last term in (34) can be derived from (26) ashid𝑡 ∥ 2 = Tr Cov[𝛿𝑚d𝑡 ] + E[𝛿𝑚d𝑡 ]E[𝛿𝑚d𝑡 ] TE ∥𝛿𝑚
2d𝑡 ] + E[𝛿𝑚d𝑡 ]= Tr Cov[𝛿𝑚E[𝛽 𝑡 +1 ]= 1 − 𝑐𝛽 .
𝛽𝑡

(33)

(42)

𝐾 𝑡 2 𝑡 2(𝛽 ) ∥𝑚 ∥ + 4(𝛽 𝑡 ) 2 ∥𝑚𝑡 ∥ 2 .
𝑛
The right-hand side of (35) is derived from (34) and the above
equations.
Considering the inequality that the right-hand side of (35) isless than 1 as a second order inequality of the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 , we=

Theorem 3.3. Consider the single update of 𝛽 in (11) given 𝑚𝑡
and 𝛽 𝑡 on the sphere function. The expected decrease of 𝛽 is given by(41)

Analysis of Information Geometric Optimization
with Isotropic Gaussian Distribution Under Finite Samples

GECCO ’18, July 15–19, 2018, Kyoto, Japan

can verify that (37) is the necessary and sufficient condition for theinequality to be satisfied.
Finally we consider the condition for the interval (37) to benonempty. It is clear that the interval is nonempty if
𝑀 2 (𝑑, 𝑛) − 𝑑 2 (𝑑 + 4)(𝑑 + 2) ≤ 0 .
It is satisfied if one of the following holds:p𝑀 (𝑑, 𝑛) ≤ −𝑑 (𝑑 + 2)(𝑑 + 4)p
𝑀 (𝑑, 𝑛) ≥ 𝑑 (𝑑 + 2)(𝑑 + 4) .

(43)

(44)
(45)

Since the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 is nonnegative, so is 𝑀 (𝑑, 𝑛). Therefore,
only (45) can be the necessary and sufficient condition for (37) to benonempty, and we derive the upper bound of (39) from (45). This
ends the proof.
□
Theorems 3.3 and 3.4 imply that the rates of geometric convergence of ∥𝑚𝑡 ∥ 2 and 𝛽 𝑡 towards zero must be the same, which iswhat we observe in practice and what we cannot derive from theanalysis of the infinite sample model of the IGO algorithm. To see
this, we assume the rates of geometric convergence of ∥𝑚𝑡 ∥ 2 and𝛽 𝑡 are different. Then, it is easy to see that ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 tends toeither ∞ or 0, both of which lead to divergence of 𝐾. Theorem 3.4
then tells that the expected change rate of the squared distanceof the mean vector will be greater than 1, meaning that it fails toconverge. To prevent the divergence, one needs to decrease 𝑐𝑚
towards zero as 𝐾 increases, such that8𝑛
0 < 𝑐𝑚 <,(46)
4𝑛 + 𝐾
which is necessary for (35) to be smaller than 1. However, it leads to
the rate of convergence to 1, i.e., it fails to converge geometrically.
By taking into account a finite sample size, we manage to derive
such an important criterion.

where 𝑠 and 𝑀 are defined in Theorem 3.4.
Proof. Since the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 is nonnegative, we can transform (47) into quadratic equation
 𝑡 2 2𝑐 𝛽 ∥𝑚𝑡 ∥ 2∥𝑚 ∥𝑑− 2 𝑀 (𝑑, 𝑛) − 2𝑛 2
+ 𝑑 (𝑑 + 2) (𝑑 + 4) = 0 ,
𝛽𝑡
𝛽𝑡
𝑐𝑚
(51)
and the discriminant of the equation is
𝑐𝛽 2− 𝑑 2 (𝑑 + 2)(𝑑 + 4) .
(52)
𝐷 = 𝑀 (𝑑, 𝑛) − 2𝑛 2𝑐𝑚
Condition 𝐷 ≥ 0 is satisfied if and only if one of the followings
holds
p
𝑐𝛽
(53)
𝑀 (𝑑, 𝑛) − 2𝑛 2 ≤ −𝑑 (𝑑 + 2)(𝑑 + 4)𝑐𝑚p𝑐𝛽
𝑀 (𝑑, 𝑛) − 2𝑛 2 ≥ 𝑑 (𝑑 + 2)(𝑑 + 4) .
(54)
𝑐𝑚
When either (53) or (54) is satisfied, the solutions to the above
quadratic equation are given by (50). Note that both solutions in (50)
become negative if the left-hand side of (53) or (54) is negative. Since
the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 must be nonnegative but (53) does not accept
a positive solution, (54) is the necessary and sufficient condition
for (50). Conditions (48) and (49) derive from (54). This ends theproof.
□In (50) we have two candidate values of a stationary point of
the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 . Let 𝑅small and 𝑅large denote the smaller andgreater values in (50), respectively. We expect that only 𝑅small canbe the stable stationary point of ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 . The reason is describedas follows. If ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 ∈ (𝑅small, 𝑅large ), we have

In this section, we study the condition on the learning rate coefficients 𝑐𝑚 and 𝑐 𝛽 for the rates of expected progress of 𝑚𝑡 and 𝛽 𝑡 to
be the same on the sphere function. Moreover, we derive the stablevalue of ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 .

E[𝛽 𝑡 +1 ]E[∥𝑚𝑡 +1 ∥ 2 ]
<
,
(55)
𝛽𝑡
∥𝑚𝑡 ∥ 2hence the ratio will become smaller. If not, the ratio will become
greater. This implies that 𝑅small is attractive for ∥𝑚 ∥ 2 /𝛽 < 𝑅large ,and ∥𝑚 ∥ 2 /𝛽 tends to diverge if ∥𝑚 ∥ 2 /𝛽 > 𝑅large .
If we consider the case when 𝑐𝑚 , 𝑐 𝛽 violate the condition (48)and (49), we always have

Theorem 4.1. Consider the single updates of 𝑚 and 𝛽 in (10) and(11). We have𝑐2
E[𝛽 𝑡 +1 ]E[∥𝑚𝑡 +1 ∥ 2 ]= 1 − 𝑐 𝛽 < (1 − 𝑐𝑚 ) 2 + 𝑚 𝐾min ≤, (56)𝑡𝛽4𝑛∥𝑚𝑡 ∥ 2

4

STABLE VALUE OF THE RATIO

E[∥𝑚𝑡 +1 ∥ 2 ] E[𝛽 𝑡 +1 ]== 1 − 𝑐𝛽 < 1𝛽𝑡∥𝑚𝑡 ∥ 2
if and only if the following three conditions hold2𝑛
0 < 𝑐𝛽 ≤𝑠 (𝑑, 𝑛)qq
2𝑛 + 4𝑛 2 − 2𝑛𝑐 𝛽 𝑠 (𝑑, 𝑛)2𝑛 − 4𝑛 2 − 2𝑛𝑐 𝛽 𝑠 (𝑑, 𝑛)≤ 𝑐𝑚 ≤𝑠 (𝑑, 𝑛)𝑠 (𝑑, 𝑛)𝑐𝛽∥𝑚𝑡 ∥ 2 1=
𝑀 (𝑑, 𝑛) − 2𝑛 2
𝑡
𝛽
𝑑
𝑐𝑚
s

𝑐𝛽 2
ª
±
𝑀 (𝑑, 𝑛) − 2𝑛 2
− 𝑑 2 (𝑑 + 2)(𝑑 + 4) ® ,
𝑐𝑚
¬

(47)

where 𝐾min is the minimal possible 𝐾 in (36) given byp𝐾min = min 𝐾 = 2 (𝑑 2 + 4𝑑 + 2) + 𝑑 (𝑑 + 2)(𝑑 + 4) . (57)∥𝑚 ∥ 2 /𝛽

(48)

(49)

(50)

This means the ratio is expected to diverge when 𝑐𝑚 , 𝑐 𝛽 violate (48)and (49).
When the decreasing rates of ∥𝑚𝑡 ∥ 2 and 𝛽 𝑡 satisfy (47), thedecreasing rate of the expected objective function value is given by
E[𝑓 (𝑥 )|𝑚 = 𝑚𝑡 +1, 𝛽 = 𝛽 𝑡 +1 ]= 1 − 𝑐𝛽 .
E[𝑓 (𝑥 )|𝑚 = 𝑚𝑡 , 𝛽 = 𝛽 𝑡 ](58)

It is intuitive that it is the same as those of ∥𝑚 ∥ 2 and 𝛽 , however,it cannot be derived by the analysis with the infinite samples.
Note that the interval of 𝑐𝑚 in (49) depends on 𝑐 𝛽 . In particular,
2𝑛 as 𝑐 is set greater. Boththe interval becomes shorter around 𝑠 (𝑑,𝑛)𝛽intervals of 𝑐𝑚 and 𝑐 𝛽 depend heavily on the sample size 𝑛 and theGECCO ’18, July 15–19, 2018, Kyoto, Japan

Kento Uchida, Youhei Akimoto, and Shinichi Shirakawa

dimension 𝑑 of the search space. If we take the limit for the sample
size to infinity, we obtainq
2𝑛 − 4𝑛 2 − 2𝑛𝑐 𝛽 𝑠 (𝑑, 𝑛)
q
(59)
lim
= 1 − 1 − 𝑐𝛽𝑛→∞𝑠 (𝑑, 𝑛)q
2𝑛 + 4𝑛 2 − 2𝑛𝑐 𝛽 𝑠 (𝑑, 𝑛)
q
lim
(60)
= 1 + 1 − 𝑐𝛽 .
𝑛→∞𝑠 (𝑑, 𝑛)Therefore, (48) and (49) read0 < 𝑐𝛽 ≤ 1
qq
1 − 1 − 𝑐 𝛽 ≤ 𝑐𝑚 ≤ 1 + 1 − 𝑐 𝛽 .

(61)

5

(62)

5.1
These are different from the conditions given in Proposition 3.1,
where the infinite sample size is assumed from the beginning of
the derivation. Moreover, given 𝑐𝑚 and 𝑐 𝛽 ,𝑅largelim𝑛→∞=2 −𝑐 )
4(2𝑐𝑚 − 𝑐𝑚
𝛽

𝑛

(63)
2 𝑑
𝑐𝑚

𝑐 2 𝑑 (𝑑 + 2)(𝑑 + 4)
lim 𝑛𝑅small = 𝑚.
2 −𝑐 )𝑛→∞
4(2𝑐𝑚 − 𝑐𝑚𝛽(64)These limit values imply that, with Landau’s O-notation, the stableratio 𝑅small of ∥𝑚 ∥ 2 /𝛽 becomes smaller in O (1/𝑛) and its regionof attraction, [0, 𝑅large ], becomes wider as 𝑅large ∈ O (𝑛).
When we consider the case 𝑑 ≫ 1, we can easily see that theintervals (48) and (49) tend to zero. In other words, the learning
rates satisfying these conditions need to be infinitesimally small if
𝑑 ≫ 1 while 𝑛 is fixed. Now we introduce 𝛼𝑚 , 𝛼 𝛽 as
𝑐𝑚 = 𝛼𝑚2𝑛,𝑠 (𝑑, 𝑛)𝑐𝛽 = 𝛼𝛽2𝑛.
𝑠 (𝑑, 𝑛)(65)

The variables 𝛼𝑚 , 𝛼 𝛽 represent the proportion of 𝑐𝑚 , 𝑐 𝛽 to thevalue 2𝑛/𝑠 (𝑑, 𝑛), which is the maximum value in (48) and the center value in (49). Note that when the dimension 𝑑 is sufficiently
large, 2𝑛/𝑠 (𝑑, 𝑛) is approximated by 𝑛/𝑑 2 . The ranges of 𝑐𝑚 and 𝑐 𝛽satisfying (48) and (49) in Theorem 4.1 reads



1−

q

0 < 𝛼𝛽 ≤ 1 q
1 − 𝛼 𝛽 ≤ 𝛼𝑚 ≤ 1 + 1 − 𝛼 𝛽 ,NUMERICAL SIMULATION

The analysis in the previous sections studies the expected single step
behavior and it does not guarantee the long-term behavior itself.
In this section, we perform the IGO algorithm given the isotropic
Gaussian distribution on the sphere function, and see how precisely
the results derived in the previous sections describe the behaviorof the long-term behavior of the real algorithm. Particularly, weobserve that the rate of convergence is approximated by (47) andthe ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 tends to the value derived in Theorem 4.1 under
the conditions on the learning rate coefficients derived there. We
also check what happens if the conditions on the learning rate
coefficients are not satisfied.

(66)



(67)

and the limit values of 𝑅large and 𝑅small divided by 𝑑 are derived as

 s
2
2𝛼 𝛽
2𝛼 𝛽
𝑅large44=− 2 −1 +− 2 −1 −1 ,
lim
𝛼𝑚
𝛼𝑚
𝑑→∞ 𝑑
𝛼𝑚
𝛼𝑚
(68)

 s
2
2𝛼 𝛽
2𝛼 𝛽
𝑅
4
4
− 2 −1 −− 2 −1 −1 .
lim small =
𝛼𝑚
𝛼𝑚
𝑑→∞ 𝑑
𝛼𝑚
𝛼𝑚
(69)
It implies that the stable value of the ratio ∥𝑚 ∥ 2 /𝛽 scales as O (𝑑).
This agrees with our empirical knowledge and the theoretical factthat the optimal step-size on the sphere function is proportional tothe distance to the optimum times 𝑑 [3, 6].

Experiment Setting

We run the IGO algorithm described by (10) and (11) with thenatural gradients (8) and (9) estimated from the finite samples on
the sphere function with dimension 𝑑 = 10. The sample size is𝑛 = 10 in this simulation. The learning rates are set as (30) and (31)with different 𝑐𝑚 and 𝑐 𝛽 values. The initial variance parameter isfixed to 𝛽 0 = 1 and the distance of the mean vector to the origin(optimum) is set in different values as ∥𝑚 0 ∥ 2 = 10−1, 100, 101, 102 .
We remark that the domain of 𝛽 𝑡 is a positive real space R>0 ,but the update (11) with (9) sometimes leads to a negative value,
especially when 𝑐 𝛽 is relatively large. To prevent 𝛽 𝑡 from being
negative, we replace (11) byd𝑡 .
𝛽 𝑡 +1 = 𝛽 𝑡 − 𝜂 𝑡𝛽 𝛿𝛽(70)

The artificial effect of this modification is discussed later.

5.2

Simulation Results

First, we set 𝑐𝑚 = 0.1 and 𝑐 𝛽 = 0.01, which satisfy the conditions (48) and (49). Figure 1 shows the median values and 25th and75th percentile ranges of the transitions of the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 , theminimum function value at each iteration, ∥𝑚𝑡 ∥ 2 and 𝛽 𝑡 in 1000
trials for each setting. We plot them on first 100 iterations, which
is sufficient for the ratio to reach the stable state. In Figure 1 we
observe that the rates of geometric convergence of ∥𝑚𝑡 ∥ 2 and 𝛽 𝑡
and the decreasing rate of minimum evaluation value were wellapproximated by 1 − 𝑐 𝛽 if the initial ratio is smaller than 𝑅large , andobserve that the ratio, minimum evaluation value, ∥𝑚𝑡 ∥ 2 and 𝛽 𝑡 all
diverged if not. Moreover, the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 tended to 𝑅small in(50) if the initial ratio is smaller than 𝑅large . The simulation results
matched the theoretical results presented in the previous section
and the discussion.
Next, we investigate the setting 𝑐𝑚 = 𝑐 𝛽 = 0.1, which do notsatisfy (49). The result is shown in Figure 2. In this setting, ∥𝑚 ∥ 2
did not increase when the ratio ∥𝑚 ∥ 2 /𝛽 was satisfying (37) and it
started diverging once (37) was violated. This behavior is explainedby Theorem 3.4, however, the variance parameter 𝛽 also diverged
unlike the result of Theorem 3.3. Moreover, the ratio ∥𝑚 ∥ 2 /𝛽 fluctuates around some value. The fluctuation is due to unstable updateof 𝛽 . This may be because of the modification (70): too large updateof 𝛽 in a negative direction sometimes results in increasing 𝛽 . Thisis discussed in the next section.

Analysis of Information Geometric Optimization
with Isotropic Gaussian Distribution Under Finite Samples||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
inequality (37)equation (50)

102
101
100

0

20

40

60

iteration

80

102
101
100
0

||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
theory (finite)theory (infinite)103||mt||2

103

100

104

102

||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
theory (58)

20

40

60

iteration

80

100

102

||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
theory(finite and infinite)101t||mt||2/ t

103

104

best f(x) at each iteration

104

GECCO ’18, July 15–19, 2018, Kyoto, Japan

101
100

100
10 1
0

20

40

60

iteration

80

100

0

20

40

60

iteration

80

100

Figure 1: The transitions of each value when 𝑐𝑚 and 𝑐 𝛽 satisfy the conditions (48), (49). These figures show the transitions of
the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 , the minimum evaluation, the mean vector ∥𝑚𝑡 ∥ 2 and the variance parameter 𝛽 𝑡 . We plot the median values
and 25th and 75th percentile ranges of 1000 trials in each setting.

6

FURTHER DISCUSSIONFirst, we discuss the effect of the modified update rule (70). As we
mentioned, the ratio ∥𝑚 ∥ 2 /𝛽 theoretically continues to be greater
the whole time if it does not satisfy the stability condition (49).
However, we did not observe such a behavior. The reason may bedescribed as follows. The variance of the 𝛽 -update on the spherefunction is 𝑡 +1 
𝑐 𝛽2
𝛽
Var
=
𝑑 (𝑑 2 + 12𝑑 + 24)
𝛽𝑡
2𝑛𝑑 2
 𝑡 2 2 !
∥𝑚 ∥∥𝑚𝑡 ∥ 2+ 2(𝑑 + 4)(𝑑 + 2)
+𝑑
,
𝛽𝑡
𝛽𝑡

(71)

which increases to the plus infinity as the ratio ∥𝑚 ∥ 2 /𝛽 increases.
Once the ratio becomes large, there is high chance that the varianceparameter is updated in the negative direction and the modified
update rule (70) results in increasing the variance parameter. Therefore, the variance parameter 𝛽 increases and the ratio ∥𝑚 ∥ 2 /𝛽
fluctuates in the case of Figure 2.
Remark that we employed the −𝑓 -proportional utility in our
analysis as it has been employed in the previous works. In practice,
however, we employ a ranking-based utility. Under a proper utility
function and a proper learning rate, the variance parameter is guaranteed to be positive. Moreover, in the CMA-ES, the covariancematrix is guaranteed to be positive definite. When using a rankingbased utility such as the truncation selection [10], we observedthat the ratio tends to be a stable value when the learning rates

are reasonable, and that it tends to diverge if the learning rates
are improper. These behaviors are similar to the simulation results
described in Section 5, and the analysis with a ranking-based utility
makes our understanding even better. It is an important directionof a future work.
Next, we discuss the optimal sample size 𝑛 ∗ . The optimal sample
size is defined ass𝑛 E𝑛 [∥𝑚𝑡 +1 ∥ 2 ]∗𝑛 = arg min,(72)∥𝑚𝑡 ∥ 2𝑛 ≥1where E𝑛 [∥𝑚𝑡 +1 ∥ 2 ] is the expected value of ∥𝑚𝑡 +1 ∥ 2 under the
sample size 𝑛. Note that the optimal value depends on 𝑐𝑚 and 𝑐 𝛽 .
If we consider the case where the learning rates are set to the maximal values that admits a stable value of the ratio ∥𝑚 ∥ 2 /𝛽 , derived
in Theorem 4.1, we have 𝑛 ∗ = 1. It is natural from the stochastic
approximation perspective: smaller samples with a smaller learning
rate tend to be faster than larger samples with a greater learning
rate because of a small but frequent update of the parameter. Note,however, that it is not necessarily optimal on other functions. Moreover, it is not possible to set 𝑛 = 1 when a ranking-based utility 𝑢
is employed.

7

CONCLUSION

We have studied the convergence properties of the IGO algorithm
given the family of isotropic Gaussian distributions under finite
samples on the sphere function. We have derived the variance andcovariance of estimated natural gradients and derived the rate ofGECCO ’18, July 15–19, 2018, Kyoto, Japan

Kento Uchida, Youhei Akimoto, and Shinichi Shirakawa||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
inequality (37)||mt||2/ t

103
102
101
100

0

20

40

60

iteration

80

100

104

101

103
102
101
100
10 1

0

20

40

60

iteration

80

100||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
theory (infinite)

101
100
t

||mt||2102||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102102||m0||2 = 10 1||m0||2 = 100||m0||2 = 101||m0||2 = 102
theory (infinite)

103

10 1

100

10 2

10 1
10 2

104

best f(x) at each iteration

104

0

20

40

60

iteration

80

100

10 3

0

20

40

60

iteration

80

100

Figure 2: The transitions of each value when 𝑐𝑚 and 𝑐 𝛽 do not satisfy the condition (49). These figures show the transitions of
the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 , the minimum evaluation, the mean vector ∥𝑚𝑡 ∥ 2 and the variance parameter 𝛽 𝑡 .

decrease of the expected squared distance to the optimum andthe expectation of the variance parameter. We have shown thatthe rate of decrease of the expected squared distance to the optimum depends on the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 , which is empirically observed
but is not derived in the previous analysis assuming the infinite
samples. We have derived the stable value of the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡
and the conditions on the learning rates that admit a stable value.
The simulation results show that the ratio ∥𝑚𝑡 ∥ 2 /𝛽 𝑡 tends to thetheoretically derived stable value, and the rate of decrease of the
expected squared distance to the optimum and the expectation of
the variance parameter is well approximated by the theoreticallyderived value.
We consider our analysis can be expanded to more general algorithms such as the CMA-ES. A generalization of our analysis to the
IGO with a family of Gaussian distribution with arbitrary positive
definite covariance matrix is an ongoing future work. Moreover, we
would like to investigate the convergence of the covariance matrix
to the inverse Hessian of the objective function times a scalar factor,
which is derived with its rate of convergence under the infinite
samples [1]. This part is also left for the future work.

REFERENCES[1] Youhei Akimoto. 2012. Analysis of a Natural Gradient Algorithm on Monotonic Convex-Quadratic-Composite Functions. In Proceedings of the Genetic andEvolutionary Computation Conference (GECCO) 2012. 1293–1300.
[2] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2012. Convergence of theContinuous Time Trajectories of Isotropic Evolution Strategies on MonotonicCˆ2-composite Functions. In Parallel Problem Solving from Nature - PPSN XII, PartI (Lecture Notes in Computer Science), Vol. 7491. Springer, 42–51.

[3] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2017. Quality Gain Analysisof the Weighted Recombination Evolution Strategy on General Convex Quadratic Functions. In Proceedings of the 14th Conference on Foundations of Genetic
Algorithms (FOGA) 2017. 111–126.
[4] Youhei Akimoto, Anne Auger, and Nikolaus Hansen. 2017. Quality Gain Analysisof the Weighted Recombination Evolution Strategy on General Convex Quadratic
Functions. arXiv:1604.00772 (2017). arXiv:1608.04813 https://arxiv.org/pdf/1608.
04813.pdf[5] Shun-ichi Amari. 1998. Natural Gradient Works Efficiently in Learning. NeuralComputation 10 (1998), 251–276.
[6] Dirk V. Arnold. 2005. Optimal Weighted Recombination. In Proceedings of the 8th
Conference on Foundations of Genetic Algorithms (FOGA) 2005. Springer, 215–237.
[7] Anne Auger. 2005. Convergence results for the (1,𝜆 )-SA-ES using the theoryof 𝜑 -irreducible Markov chains. Theoretical Computer Science 334, 1–3 (2005),
35–69.
[8] Shummet Baluja. 1994. Population-Based Incremental Learning: A Method forIntegrating Genetic Search Based Function Optimization and Competitive Learning.
Technical Report. Carnegie Mellon University Pittsburgh.
[9] Hans Georg Beyer. 2014. Convergence Analysis of Evolutionary Algorithms That
Are Based on the Paradigm of Information Geometry. Evolutionary Computation
22, 4 (2014), 679–709.
[10] James F. Crow and Motoo Kimura. 1979. Efficiency of Truncation Selection. In
Proceedings of the National Academy of Sciences of the United States of America,
Vol. 76. 396–399.
[11] Tobias Glasmachers. 2012. Convergence of the IGO-Flow of Isotropic GaussianDistributions on Convex Quadratic Problems. In Parallel Problem Solving fromNature - PPSN XII, Part I (Lecture Notes in Computer Science), Vol. 7491. Springer,
1–10.
[12] Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. 2003. Reducing
the Time Complexity of the Derandomized Evolution Strategy with CovarianceMatrix Adaptation (CMA-ES). Evolutionary Computation 11, 1 (2003), 1–18.
[13] Silja Meyer-Nieberg and Hans-Georg Beyer. 2012. The Dynamical Systems Approach — Progress Measures and Convergence Properties. Springer-Verlag Berlin
Heidelberg, 741–814.
[14] Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. 2017.
Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles. Journal of Machine Learning Research 18, 1 (2017), 564–628.