Youhei Akimoto
email: youhei.akimoto@lri.fr

Yann Ollivier
email: yann.ollivier@lri.fr

Objective Improvement in Information-Geometric Optimization

Keywords: G.1.6 [Mathematics of Computing]: Numerical Analysis-Optimization Information-Geometric Optimization, Natural Gradient, Quantile Improvement, Step Size, Black Box Optimization

Information-Geometric Optimization (IGO) is a unified framework of stochastic algorithms for optimization problems. Given a family of probability distributions, IGO turns the original optimization problem into a new maximization problem on the parameter space of the probability distributions. IGO updates the parameter of the probability distribution along the natural gradient, taken with respect to the Fisher metric on the parameter manifold, aiming at maximizing an adaptive transform of the objective function. IGO recovers several known algorithms as particular instances: for the family of Bernoulli distributions IGO recovers PBIL, for the family of Gaussian distributions the pure rank-µ CMA-ES update is recovered, and for exponential families in expectation parametrization the cross-entropy/ML method is recovered.

This article provides a theoretical justification for the IGO framework, by proving that any step size not greater than 1 guarantees monotone improvement over the course of optimization, in terms of q-quantile values of the objective function f . The range of admissible step sizes is independent of f and its domain. We extend the result to cover the case of different step sizes for blocks of the parameters in the IGO algorithm. Moreover, we prove that expected fitness improves over time when fitness-proportional selection is applied, in which case the RPP algorithm is recovered.

INTRODUCTION

Information-Geometric Optimization (IGO) [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] is a unified framework of model based stochastic search algorithms for any optimization problem. As typified by Estimation of Distribution Algorithms (EDA) [START_REF] Larrañaga | Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation[END_REF], model based randomized search algorithms build a statistical model P θ on the search space X to generate search points. The parameters θ of the statistical model are updated over time so that the probability distribution hopefully concentrates around the minimum of the objective function. In most model based algorithms such as EDAs and Ant Colony Optimization (ACO) algorithms [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF], parameter calibration is based on the maximum likelihood principle or other intuitive ways. IGO, unlike them, performs a natural gradient ascent of θ in the parameter space Θ, having first adaptively transformed the objective function into a function on Θ. This construction offers maximal robustness guarantees with respect to changes in the representation of the problem (change of parametrization of the search space, of the parameter space, and of the fitness values).

Importantly, the IGO framework recovers several known algorithms [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]Section 4]. When IGO is instantiated using the family of Bernoulli distributions on {0, 1} d , one obtains the population based incremental learning (PBIL) algorithm [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF]. When using the family of Gaussian distributions on R d , IGO instantiates as a variant of covariance matrix adaptation evolution strategies (CMA-ES), the so-called pure rank-µ CMA-ES update [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF]. Moreover, when using an exponential family with the expectation parameters, the IGO instance is equivalent to the cross-entropy method for optimization [START_REF] Boer | A tutorial on the cross-entropy method[END_REF]. Of course, the IGO framework not only provides information-theoretic derivations for existing algorithms but automatically offers new algorithms for possibly complicated optimization problems. For instance, the IGO update rule for the parameters of restricted Boltzmann machines has been derived [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF].

Theoretical justification of the IGO framework, therefore, is important both to provide a theoretical basis for the recovered algorithms and to make the design principle for future algorithms more reliable. Here we focus on providing a measure of "progress" over the course of IGO optimization, in terms of quantile values of the objective function.

Parameter updates by gradient ascent are somewhat justified in general, at least for infinitesimally small steps, because the gradient points to the direction of steepest ascent of a function. However, this argument does not apply to the IGO algorithm: as the objective function is adaptively transformed in a time-dependent way, the function on which the gradient is computed changes over time, so that its increase does not necessarily mean global improvement. Still, the IGO framework comes with a guarantee that an infinitesimally small IGO step along the natural gradient leads to monotone improvement of a specified quantity, for any objective function f [5, Proposition 5]: a result from [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] is that the q-quantile value of the objective function monotonically improves along the natural gradient. This result is limited to the exact IGO flow, i.e., an infinite number of sample points is considered and the step size of the gradient ascent is infinitesimal. Still this ensures that the randomized algorithm with large sample size stays close to the deterministic trajectory with infinite samples with high probability, provided the step size is sufficiently small. Now the question arises whether actual, non-infinitesimal step sizes still ensure monotone q-quantile improvement.

In this article, we prove that any step size not greater than 1 guarantees monotone q-quantile value improvement in the IGO algorithm for an exponential family with a finite step size (Theorem 6), thus extending the previous result from infinitesimal steps with continuous time to more realistic algorithmic situations. For instance, this ensures monotone q-quantile improvement in PBIL (using uniform weights, see below), or in the cross-entropy method for exponential families in expectation parameters. Interestingly, our results show that the admissible step sizes in IGO are independent of the objective function f , at least for large population sizes (this stems from the many invariance properties built into IGO).

We further extend the result by defining blockwise updates in IGO where different blocks of parameters are adjusted one after another with different step sizes. Our motivation is that in practice the pure rank-µ update CMA-ES updates the mean vector and the covariance matrix with different learning rates. We show that the blockwise update rule recovers the pure rank-µ CMA-ES update using different learning rates for the mean vector and the covariance matrix (Proposition 9). We prove that any distinct step sizes less than 1 guarantee monotone q-quantile improvement, which justifies the parameter setting used for the CMA-ES in practice ( Theorem 10).

Other examples fitting into this framework are the Relative Payoff Procedure (RPP, also known as expectationmaximization for reinforcement learning) [START_REF] Dayan | Using expectation-maximization for reinforcement learning[END_REF][START_REF] Hinton | Connectionist learning procedures[END_REF], or situations where fitness-proportional selection is applied using exponential families (Theorem 12). The RPP is considered as an alternative to gradient based methods that allows to use relatively large learning rates. As it turns out, the RPP can be described as a natural gradient based algorithm with step size 1, and our result is an extension of the proof of its monotone improvement to generic natural gradient algorithms.

The article is organized as follows. In Section 2, we explain the IGO framework and its implementation in practice. IGO-maximum likelihood (IGO-ML), a variant of IGO as a maximum likelihood, is presented, followed by the relation between the IGO algorithm, IGO-ML and the cross-entropy method for optimization, for exponential families of distributions. In Section 3, we prove monotone q-quantile improvement in IGO-ML. The result is extended by defining blockwise IGO-ML, and q-quantile improvement in blockwise IGO-ML is proved. We also provide a result with finite but large population sizes. Section 4 is devoted to the nat-ural gradient algorithm with fitness-proportional selection scheme, where monotone improvement of expected fitness is proven. A short discussion in Section 5 closes the article.

INFORMATION-GEOMETRIC OPTIMIZATION

In this article, we consider an objective function f : X → R to be minimized over any search space X. The search space X may be continuous or discrete, finite or infinite.

Let {P θ } be a family of probability distributions on X parametrized by θ ∈ Θ and let p θ be the probability density function induced by P θ w.r.t. an arbitrary reference measure dx on X, namely, P θ (dx) = p θ (x)dx.

Given a family of probability distributions, IGO [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] evolves the probability distribution P θ t at each time t so that higher probabilities are assigned to better regions. To do so, IGO transforms the objective function f (x) into a new one W f θ t (x), defines a function on Θ to be maximized:

J(θ | θ t ) := EP θ [W f θ t (x)]
, and performs the steepest gradient ascent of J(θ | θ t ) on Θ. Hopefully, after some time the distribution P θ t concentrates around minima of the objective function.

IGO is designed to exhibit as many invariance properties as possible [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]Section 2]. The first property is invariance under strictly increasing transformations of f . For any strictly increasing g, IGO minimizes g • f as easily as f . This property is realized by a quantile based mapping of f to W f θ t at each time. The second property is invariance under a change of coordinates in X, provided that this coordinate change globally preserves the family of probability distributions {P θ }. For example, the IGO algorithm for Gaussian distributions on R d is invariant under any affine transformation of the coordinates whereas the IGO algorithm for isotropic Gaussian distribution is only invariant under any translation and rotation. Invariance under Xcoordinate transformation is one of the key properties for the success of the CMA-ES. The last property is invariance under reparametrization of θ. At least for infinitesimal steps of the gradient ascent, IGO follows the same trajectory on the parameter space whatever the parametrization for θ is. This property is obtained by considering the intrinsic (Fisher) metric on the parameter space Θ and defining the steepest ascent on Θ w.r.t. this metric, i.e., by using a natural gradient.

The study of the intrinsic metric on the parameter space of the probability distribution, called a statistical manifold, is the main topic of information geometry [START_REF] Amari | Methods of Information Geometry[END_REF]. The most widely used divergence between two points on the space of probability distributions is the Kullback-Leibler divergence (KL divergence)

DKL(P θ P θ ′ ) := ln p θ (x) p θ ′ (x) P θ (dx) .
The KL divergence is, by definition, independent of the parametrization θ. Let θ ′ = θ+δθ. Then, the KL divergence between P θ and P θ+δθ expands [START_REF] Kullback | Information theory and statistics[END_REF] as

DKL(P θ P θ+δθ ) = 1 2 δθ T I θ δθ + O( δθ 3 ) , ( 1
)
where • is the Euclidean norm and I θ is the Fisher infor-mation matrix at θ defined as

(I θ )ij := ∂ ln p θ (x) ∂θi ∂ ln p θ (x) ∂θj P θ (dx) = - ∂ 2 ln p θ (x) ∂θi∂θj P θ (dx) .
The expansion (1) follows from the well-known fact that the Fisher information matrix is the Hessian of KL divergence. By using the KL divergence, we have the following property of the steepest ascent direction (see [START_REF] Amari | Natural gradient works efficiently in learning[END_REF], Theorem 1, or [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF], Proposition 1).

Statement 1. Let g be a smooth function on the parameter space Θ. Let θ ∈ Θ be a nonsingular point where ∇ θ g(θ) = 0. Then the steepest ascent direction of g is given by the so-called natural gradient ∇θ g(θ)

:= I -1 θ ∇ θ g(θ). More precisely, ∇θ g(θ) ∇θ g(θ) = lim ǫ→0 1 ǫ arg max δθ such that D KL (P θ P θ+δθ )≤ǫ 2 /2 g(θ + δθ) .
Since KL divergence does not depend on parametrization, the natural gradient is invariant under reparametrization of θ. Hence, the natural gradient step-steepest ascent step w.r.t. the Fisher metric-is invariant at least for an infinitesimal step size [5, Section 2.4].

Algorithm Description

For completeness, we include here a short description of the IGO algorithm. We refer to [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] for a more complete presentation.

First, IGO transforms the objective function into an adaptive weighted preference by a quantile based approach. This results in a rank based algorithm, invariant under increasing transformations of the objective function. Define the lower and upper P θ -f -quantiles of x ∈ X as

q < θ (x) := P θ [y : f (y) < f (x)] q ≤ θ (x) := P θ [y : f (y) ≤ f (x)
] . The lower quantile value q < θ (x) is the probability of sampling strictly better points than x under the current distribution P θ , while the upper quantile value q ≤ θ (x) is the probability of sampling points better than or equivalent to x. Given a weight function (selection scheme) w : [0, 1] → R that is non-increasing, the weighted preference W f θ (x) is defined as

W f θ (x) :=    w(q ≤ θ (x)) if q < θ (x) = q ≤ θ (x), 1 q ≤ θ (x)-q < θ (x) q ≤ θ (x) q < θ (x) w(u) du otherwise.
(2) This way, the quality of a point is measured by a function of the P θ -quantile in which it lies. A typical choice of the selection scheme w is w(u) = 1 [u≤q] /q, 0 < q < 1. We call it the q-truncation selection scheme. Using q-truncation amounts, in the final IGO algorithm, to giving the same positive weight to a fraction q of the best samples in a population, and weight 0 to the rest, as is often the case in practice.

Next, IGO turns the original objective function f on the search space X into a function J(θ | θ t ) on the statistical manifold Θ by defining

J(θ | θ t ) := EP θ [W f θ t (x)] . (3)
Note that J(θ | θ t ) depends on the current position θ t . Then, the gradient of J(θ | θ t ) is computed as

∇ θ J(θ | θ t ) = ∇ θ EP θ [W f θ t (x)] = ∇ θ W f θ t (x) p θ (x) dx = W f θ t (x) p θ (x) ∇ θ ln p θ (x) dx = EP θ [W f θ t (x) ∇ θ ln p θ (x)] . (4)
Here we have used the relation ∇p θ (x) = p θ (x)∇ln p θ (x). Finally, IGO uses natural gradient ascent on the parameter space. The natural gradient on the statistical manifold (Θ, I) equipped with the Fisher metric I is given by the product of the inverse of the Fisher information matrix, I -1 θ , and the vanilla gradient. That is, the natural gradient of

J(• | θ t ) at θ is written as ∇θ J(θ | θ t ) = I -1 θ ∇ θ J(θ | θ t ).
According to (4), we can rewrite the natural gradient as

∇θ J(θ | θ t ) = EP θ [W f θ t (x) ∇θ ln p θ (x)] . (5)
Introducing a finite step size δt, IGO finally updates the parameter as follows

θ t+δt = θ t + δt ∇θ J(θ | θ t ) θ=θ t . (6)

Implementation and Recovering Algorithms

When implementing IGO in practice, it is necessary to estimate the expectation in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]. The approximation is done by the Monte Carlo method using λ samples taken from P θ t . Let x1, . . . , x λ be independent samples from P θ t .

First, we need to approximate

W f θ t (xi) for each i = 1, . . . , λ. Define rk < (xi) := #{j, f (xj) < f (xi)} rk ≤ (xi) := #{j, f (xj) ≤ f (xi)} , let wi := i/λ (i-1)/λ w(q) dq, ∀i ∈ 1, λ , and set wi = 1 rk ≤ (xi) -rk < (xi) rk ≤ (x i ) j=rk < (x i )+1 wj . (7)
Then λ wi is a consistent estimator of W f θ t (xi), in other words, lim λ→∞ λ wi = W f θ t (xi) with probability one. (See the proof of Theorem 4 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF].) If there are no ties in our sample, i.e. f (xi) = f (xj) for any i = j, then rk ≤ (xi) = rk < (xi) + 1 and ( 7) simply reads wi = wrk ≤ (x i ) , but ( 7) is a mathematically neater definition of rank based weights accounting for possible ties. In practice we just design the λ weight values w1, . . . , wλ , instead of the selection scheme w.

In the rest of this article, we assume for simplicity that the selection weights wi are non-negative and sum to 1. This is the case, for instance, if the selection scheme w is q-truncation as above.

Next, Monte Carlo sampling is applied to the expectation (5), using wi and xi. Replacing the expectation with a sample average 1 λ λ i=1 and W f θ t (xi) with λ wi, we get

G t := λ i=1 wi ∇θ ln p θ (xi)| θ=θ t . (8)
Again, G t is a consistent estimator of the IGO step at θ t , i.e., of ∇θ J(θ | θ t )| θ=θ t . See Theorem 4 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]. Now the practical IGO algorithm implementation can be written in the form of a black-box search algorithm as 1. Sample xi, i = 1, . . . , λ, independently from P θ t ; 2. Evaluate f (xi) and compute rk ≤ (xi) and rk < (xi);

3. Evaluate G t = λ i=1 wi ∇θ ln p θ (xi)| θ=θ t ;
4. Update the parameter:

θ t+δt = θ t + δt • G t .
Finally, to obtain an explicit form of the parameter update equation, we need to know the explicit form of the natural gradient of the log-likelihood, which depends on a family of probability distributions and its parametrization. Explicit forms of ∇θ ln p θ (x) are known for some specific families of probability distributions with specific parametrizations, and the above algorithm sometimes coincides with several known algorithms.

Example 1. The family of Bernoulli distributions on X = {0, 1} d is defined as P θ (x) = d j=1 θ

x j j (1 -θj ) 1-x j . The natural gradient of the log-likelihood is readily computed as ∇θ ln p θ (x) = x -θ (Section 4.1 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]). The natural gradient update reads

θ t+δt = θ t + δt λ i=1 wi xi -θ t .
This is equivalent to so-called PBIL (population based incremental learning, [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF]).See Section 4.1 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] for details.

Example 2. The probability density function of a multivariate Gaussian distribution on = R d with mean vector m and covariance matrix C, is defined as

p θ (x) = det(2πC) -1/2 exp -(x -m) T C -1 (x -m)/2 . When θ = (m, C), the explicit form of ∇ ln p θ (x) is known to be ∇ ln p θ (x) = x-m (x-m)(x-m) T -C
(see [START_REF] Akimoto | Bidirectional relation between CMA evolution strategies and natural evolution strategies[END_REF]). Then, the natural gradient update reads

θ t+δt = θ t + δt λ i=1 wi x -m t (x -m t )(x -m t ) T -C t .
This is equivalent to the pure rank-µ CMA-ES update [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF]

m t+1 = m t + ηm λ i=1 wi(xi -m t ) C t+1 = C t + ηC λ i=1 wi (xi -m t )(xi -m t ) T -C t except that ηm = ηC = δt in the natural gradient update.

Maximum likelihood, IGO-ML, and crossentropy

In the sequel, we prove monotone improvement of the objective function for a variant of IGO known as IGO-maximum likelihood (IGO-ML, introduced in [5, Section 3]). The result is then transferred to IGO because the two algorithms exactly coincide in an important class of cases, namely, exponential families using mean value parametrization.

The IGO-ML algorithm [5, Section 3] updates the current parameter value θ t by taking a weighted maximum likelihood of the current distribution and the best sampled points. Assume as above that wi = 1. Then the IGO-ML update is defined as

θ t+δt = arg max θ (1 -δt) EP θ t [ln p θ (x)] + δt i wi ln p θ (xi) (9)
where we note that the first part is the cross-entropy of P θ t and P θ , and thus, taken alone, is maximized for θ = θ t . Taking the limit λ → ∞, we also define the infinitepopulation IGO-ML update as

θ t+δt = arg max θ (1 -δt) EP θ t [ln p θ (x)] + δtHt(θ) (10)
where we set Ht(θ) := EP θ t W f θ t (x) ln p θ (x) a "weighted cross-entropy" of θ and θ t .

Note that the finite-and infinite-population IGO-ML updates only make sense when there is a unique maximizer θ in ( 9) and [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF], respectively. This assumption is always satisfied, for instance, for exponential families of probability distributions, as considered below (Statement 2).

The IGO-ML update is compatible with the IGO update, in the sense that for δt → 0 the direction and magnitude of these updates coincide [5, Section 3].

The IGO-ML method is also related to the cross-entropy (CE) or maximum-likelihood (ML) method for optimization [START_REF] Boer | A tutorial on the cross-entropy method[END_REF], which can be written as

θ t+1 = arg max θ λ i=1 wi ln p θ (xi)
and its smoothed version which reads [START_REF] Boer | A tutorial on the cross-entropy method[END_REF]

θ t+δt = (1 -δt)θ t + δt arg max θ λ i=1 wi ln p θ (xi) . (11)
Note that IGO-ML is parametrization-independent whereas for δt = 1 the smoothed CE/ML method is not. Consequently, in general these updates will differ.

IGO and IGO-ML for Exponential Families

An exponential family is a set {p θ ; θ ∈ Θ} of probability density functions p θ with respect to an arbitrary measure dx on X defined as

p θ (x) = 1 Z(θ) exp n i=1 βi(θ)Ti(x) , (12)
where β = (βi) 1≤i≤n is the so-called natural (i.e. canonical) parameter; each Ti, We will repeatedly and implicitly make use of the following well-known fact for exponential families.

1 ≤ i ≤ n is a map Ti : X → R such that {T1, . . . ,
Statement 2. Let x1, . . . , x k be k points in X and let α1, . . . , α k be non-negative numbers with αi = 1. Then the value θ of the parameter such that the associated expectation parameter satisfies η(θ) = αiT (xi), if it belongs to the statistical manifold, is the unique maximizer of the weighted log-likelihood: θ = arg max αi ln p θ (xi). An analogous statement holds if the finite sum is replaced with an integral or a combination of both.

(Uniqueness boils down to strict concavity of ln p θ (x) as a function of θ. The restriction placed on η to belong to the statistical manifold is necessary: for instance, for Gaussian distributions, if the number of points k is not greater than the dimension of the ambient space, a degenerate distribution θ will result.)

The following statement from [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] shows that the natural gradient of a function in the expectation parametrization is given by the vanilla gradient of the function w.r.t. the normal parameter, and vice versa.

Statement 3 (Proposition 22 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]). Let g be a function on the statistical manifold of an exponential family as above. Then the components of the natural gradient w.r.t. the expectation parameters are given by the vanilla gradient w.r.t. the natural parameters and vice versa, that is,

∇η i g = ∂g ∂βi and ∇β i g = ∂g ∂ηi .
According to Statement 3, each component of the natural gradient of the log likelihood ln p θ (x) under the exponential parametrization θ = η is equivalent to each component of the vanilla gradient, i.e.,

∇η i ln p θ (x) = ∂ ln p θ (x) ∂βi = Ti(x) -ηi , (14)
where the latter equality is well-known, e.g., [4, (2.33)]. The IGO update (6) under the expectation parametrization thus reads

η t+δt = η t + δt EP θ t [W f θ t (x)(T (x) -η t )] (15)
and the natural gradient update with finite sample size reads

η t+δt = η t + δt λ i=1 wi T (xi) -η t . ( 16
)
Suppose as above that the selection weights sum to one:

EP θ [W f θ (x)] = 1
0 w(q)dq = 1 and thus wi = 1. Then, IGO has a close relation with the CE/ML for optimization. As is stated in Theorem 15 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF], for an exponential family the CE/ML method [START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF] and the IGO instance [START_REF] Malagò | Towards the geometry of estimation of distribution algorithms based on the exponential family[END_REF], when expressed with the expectation parametrization (θ = η), coincide with IGO-ML [START_REF] Dayan | Using expectation-maximization for reinforcement learning[END_REF].

Statement 4 (Theorem 15 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]). For optimization using an exponential family {P θ }, these three algorithms coincide: IGO-ML; the IGO expressed in expectation parameters; the CE/ML expressed in expectation parameters. That is, for an exponential family with the expectation parametrization, for 0 ≤ δt ≤ 1 we have (writing in turn IGO, CE/ML and IGO-ML)

θ t+δt = θ t + δt λ i=1 wi T (xi) -θ t = (1 -δt)θ t + δt arg max θ λ i=1 wi ln p θ (xi) = arg max θ (1 -δt)EP θ t [ln p θ (x)] + δt λ i=1 wi ln p θ (xi) . (17)
In the limit of infinite sample size λ → ∞ this rewrites

θ t+δt = θ t + δt EP θ t W f θ t (x) T (x) -θ t = (1 -δt)θ t + δt arg max θ Ht(θ) = arg max θ (1 -δt)EP θ t [ln p θ (x)] + δtHt(θ) (18)
where we recall that Ht(θ) = EP θ t W f θ t (x) ln p θ (x) .

Remark 1. Malagò et al. [START_REF] Malagò | Towards the geometry of estimation of distribution algorithms based on the exponential family[END_REF] study information-geometric aspects of exponential families for optimization. One difference from the IGO framework is that the optimization problem is defined as the minimization of the expectation of the objective function over P θ , namely

min θ EP θ [f (x)],
which they call the stochastic relaxation of the original optimization problem. They study this for an exponential family on a discrete search space with the natural parametrization (θ = β) and propose the natural gradient descent algorithm. Note that this requires computation of the empirical Fisher information matrix to perform natural gradient descent. However, if the algorithm is modified to use the expectation parameters instead, one can compute the natural gradient descent directly as

η t+δt = η t -δt λ i=1 f (xi) T (xi) -η t . ( 19
)
We study this algorithm in Section 4.

QUANTILE IMPROVEMENT

One possible way to provide theoretical backing for an optimization algorithm is to show monotonic improvement at each step of the algorithm (although this is by no means necessary: e.g., for stochastic algorithms, this is not expected to hold at each step). For example, consider the sphere function f : x → x 2 . Then, it is easy to show that the gradient steps x t+δt = x t -δt ∇xf (x t ) generate a monotonically decreasing sequence {f (x t )} t≥0 provided 0 < δt ≤ 1/2. For any smooth function, infinitesimal gradient steps are guaranteed to improve the objective function values; but in general the admissible step size strongly depends on the function and has to be adjusted by the user.

When it comes to the counterpart in IGO, however, we follow the gradient of the function J(θ | θ t ), which depends on θ t , so that step-by-step improvement in the objective, J(θ t+1 | θ t ) > J(θ t | θ t ), does not necessarily mean improvement. (It might happen that J(θ t | θ t+1 ) > J(θ t+1 | θ t+1 ) and J(θ t+1 | θ t ) > J(θ t | θ t ) at the same time.)

A key feature of the IGO framework is its invariance under changing the objective function f by an increasing transformation (e.g. optimizing f 3 instead of f ). Thus, any measure of progress that is not compatible with such transformations (e.g. the expectation EP θ t f ) is not a good candidate to always improve over the course of IGO optimization.

As a measure of improvement, Arnold et al. [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] use the notion of q-quantile of f . The q-quantile Q q P (f ) of f under a probability distribution P is any number m such that P [x : f (x) ≤ m] ≥ q and P [x : f (x) ≥ m] ≥ 1 -q. For instance, Q q P (f ) is the median value of f under P if q = 1/2. For smooth distributions and continuous f there is only one such number m, but in general the set of such m may be a closed interval, for instance if f has "jumps". For the sake of definiteness let us use the largest such value:

Q q P (f ) := sup m ∈ R : P [x : f (x) ≤ m] ≥ q and P [x : f (x) ≥ m] ≥ 1 -q .
(This is because we want to minimize the objective function f ; when IGO is used for maximization instead, Theorem 6 has to be written using an infimum in the definition of

Q q P (f ) instead.)
It is proven in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF] that when using the q-truncation selection scheme, the q-quantile value of f monotonically decreases along infinitesimal IGO steps.

Statement 5 (Proposition 5 in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]). Consider the qtruncation selection scheme w(u) = 1 [u≤q] /q where 0 < q < 1 is fixed. Then each infinitesimal IGO step [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF] where δt is infinitesimal leads to monotonic improvement in the qquantile of f : Q q P θ t+δt (f ) ≤ Q q P θ t (f ).

Quantile Improvement in IGO-ML

In practice, explicit algorithms do not use continuous time with infinitesimal time steps: the time step δt may be quite large and its calibration may be an important issue. It is more interesting and important to see how long steps we can take along the natural gradient, i.e. how large a δt we can choose while guaranteeing q-quantile improvement.

When using IGO-ML (and thus when using IGO or CE/ML on an exponential family with the expectation parametrization), we can obtain such a conclusion; the size of the steps may even be chosen independently of the objective function. Theorem 6. Let the selection scheme be w(u) = 1 [u≤q] /q where 0 < q < 1. Assume that the arg max defining the IGO-ML step (10) is uniquely determined. Then for 0 < δt ≤ 1, each infinite-population IGO-ML step (10) leads to q-quantile improvement: Q q P θ t+δt (f ) ≤ Q q P θ t (f ). Moreover, equality can hold only if P θ t+δt = P θ t or if

P θ t+δt [x : f (x) = Q q P θ t (f )] > 0.
Corollary 7. For exponential families written in expectation parameters, on any search space, the same holds for the CE/ML method and for the IGO algorithm.

Note that the first condition for equality means the algorithm has reached a stable point.

The second condition for equality typically happens for discrete search spaces: on such spaces, the q-quantile evolves in time by discrete jumps even when θ t moves smoothly, so we cannot expect strict quantile improvement at each step. On the other hand, with continuous distributions on continuous search spaces, the second equality condition can only occur if the objective function has a plateau (a level set with non-zero measure).

Proof. If P θ t+δt = P θ t , obviously Q q P θ t+δt (f ) = Q q P θ t (f ). Hereunder, we assume P θ t+δt = P θ t .

Consider the function J(θ | θ t ) defining the expected P θ tadjusted fitness of a random point under P θ :

J(θ | θ t ) = EP θ W f θ t (x)
and remember that J(θ t | θ t ) = 1. The idea is as follows: letting Y be the set of points with P θ t (Y ) = q at which the objective function f is smallest (the sublevel set of f with P θ t -mass q), then with our choice of w, W f θ t (x) is (up to technicalities) equal to 1/q on Y and 0 elsewhere, so that J(θ | θ t ) represents 1/q times the P θ -probability of falling into Y (hence J(θ t | θ t ) = 1). Thus J(θ | θ t ) > 1 will mean that the P θ -probability of falling into Y is larger than q, so that P θ improves over P θ t and the q-quantile has decreased.

We are going to prove that the IGO-ML update satisfies J(θ t+δt | θ t ) > 1 if P θ t = P θ t+δt . More precisely we prove that

J(θ t+δt | θ t ) > exp 1 -δt δt DKL(P θ t P θ t+δt ) .
This will imply quantile improvement, thanks to the following lemma, the proof of which is postponed.

Lemma 8. Let the selection scheme w be as above. If

J(θ t+δt | θ t ) > 1, then Q q P θ t+δt (f ) ≤ Q q P θ t (f ). If moreover P θ t+δt [x : f (x) = Q q P θ t (f )] = 0, then Q q P θ t+δt (f ) < Q q P θ t (f ).
The lower bound on J(θ t+δt | θ t ) is obtained as follows. Since W f θ t (x)p θ t (x)dx = 1 and W f θ t (x)p θ t (x) ≥ 0 for any x, W f θ t (x)p θ t (x) can be viewed as a probability density function. Since ln is concave, by Jensen's inequality we have

ln J(θ | θ t ) = ln p θ (x) p θ t (x) W f θ t (x)p θ t (x)dx ≥ ln p θ (x) p θ t (x) W f θ t (x)p θ t (x)dx = Ht(θ) -Ht(θ t ) . (20)
Thus, if Ht(θ) > Ht(θ t ) we have J(θ | θ t ) > 1. Now, according to [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF], θ t+δt uniquely maximizes the quantity (1-δt)EP θ t ln p θ (x) +δtHt(θ). Therefore, if θ t+δt = θ t , we have

(1 -δt)EP θ t ln p θ t+δt (x) + δtHt(θ t+δt ) > (1 -δt)EP θ t ln p θ t (x) + δtHt(θ t )
and rearranging we get

Ht(θ t+δt ) -Ht(θ t ) > 1 -δt δt EP θ t ln p θ t (x) -EP θ t ln p θ t+δt (x) = 1 -δt δt DKL(P θ t P θ t+δt ) . (21)
The right-hand side of this inequality is non-negative for 0 < δt ≤ 1. This will prove the theorem once Lemma 8 is proved, which we now proceed to do.

Proof of Lemma 8. Hereunder, we abbreviate m for the q-quantile value Q q P θ t (f ) of f under P θ t . Let us compute the weighted preference W f θ t (x). Since the selection scheme w satisfies 0 ≤ w(u) ≤ 1/q for all u ∈ [0; 1], we have 0 ≤ W f θ t (x) ≤ 1/q for any x. We claim that f (x) > m implies W f θ t (x) = 0. Indeed, suppose that x is such that f (x) > m. Since by definition m is the largest value such that P θ t [y : f (y) ≥ m] ≥ 1 -q, we must have P θ t [y : f (y) ≥ f (x)] < 1-q. Hence P θ t [y : f (y) < f (x)] > q, i.e., q < θ t (x) > q. Now this implies W f θ t (x) = 0 for our choice of selection scheme w.

Thus W f θ t (x) is at most 1/q and vanishes if f (x) > m. For any probability distribution P θ , this implies that

J(θ | θ t ) = EP θ [W f θ t (x)] ≤ 1 q P θ [x : f (x) ≤ m] .
Therefore,

J(θ | θ t ) > 1 =⇒ P θ [x : f (x) ≤ m] > q =⇒ Q q P θ (f ) ≤ m . If moreover P θ [x : f (x) = m] = 0, we have P θ [x : f (x) ≤ m] = P θ [x : f (x) < m] hence J(θ | θ t ) > 1 =⇒ P θ [x : f (x) < m] > q ⇐⇒ P θ [x : f (x) ≥ m] < 1 -q =⇒ Q q P θ (f ) < m . Altogether, J(θ t+δt | θ t ) > 1 implies quantile improve- ment Q q P θ t+δt (f ) ≤ Q q P θ t (f ). Moreover, if P θ t+δt [x : f (x) = m] = 0, we have strict quantile improvement Q q P θ t+δt (f ) < Q q P θ t (f ).
This completes the proof of Theorem 6.

Example 3. Bernoulli distributions constitute an exponential family where the sufficient statistics Ti(x) are xi. The parameter θ used in PBIL (Example 1) is indeed the expectation parameter. Thus, PBIL is an instance of IGO-ML and can be viewed as a CE/ML method at the same time. Hence, by Theorem 6, each infinite-population PBIL step leads to q-quantile improvement if we employ q-truncation selection, which is not the same as the exponential weights introduced in [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF].

Remark 2. The proof of the theorem is quantitative: the Kullback-Leibler divergence DKL(P θ t P θ t+δt ) indicates how much progress was made. More precisely (assuming for simplicity a continuous situation with no plateaus), while the probability under P θ t to fall into the best q percent of points for P θ t is q by definition, the probability under P θ t+δt to fall into the best q percent of points for P θ t is at least q exp 1-δt δt DKL(P θ t P θ t+δt ) .

Blockwise IGO-ML

The expectation parameter is not always the most obvious one. When it comes to multivariate Gaussian distributions, the expectation parameter is the mean vector and second moment, (m, mm T + C). Meanwhile, the CMA-ES and the CE/ML method for continuous optimization parametrize the mean vector and covariance matrix, hence they differ from the IGO-ML algorithm. Moreover, sometimes different step sizes (learning rates) are employed for each parameter, which makes the direction of parameter update different from that of the natural gradient. Here, we justify some of these settings by guaranteeing q-quantile improvement in an extended framework.

We define an extension of IGO-ML, blockwise IGO-ML, that recovers the pure rank-µ CMA-ES update with different learning rates for m and C. Definition 1. Let θ = (θ1, . . . , θ k ) be any decomposition of the parameter θ into k blocks, and let {δt1, . . . , δt k } be a step size for each block. For 1 ≤ j ≤ k, define the j-th block partial IGO-ML update with step size δtj as the map sending a parameter value θ to Φj (θ) where Φj (θ) := arg max

θ * θ * i =θ i for all i =j (1 -δtj)EP θ [ln p θ * (x)] + δtj i wi ln p θ * (xi) . ( 22
)
The blockwise IGO-ML updates the parameter θ as follows.

Given a current parameter value θ t , update the first block of θ t , then the second block, etc., in that order; explicitly, set

θ t+1 := (Φ k • • • • • Φ2 • Φ1)(θ t ) , (23)
where we note that the same Monte Carlo sample {xi} from P θ t is used throughout the whole range of block updates Φ1, . . . , Φ k .

The infinite-population step (λ = ∞) reads the same with Φj (θ) := arg max

θ * θ * i =θ i for all i =j (1 -δtj)EP θ [ln p θ * (x)] + δtj EP θ t W f θ t (x) ln p θ * (x) . (24)
As before, the finite-and infinite-population blockwise IGO-ML updates only make sense if the arg max in ( 22) or ( 24) is uniquely determined.

Note that the blockwise IGO-ML depends on the decomposition of the parameters into blocks and their update order, while it is independent of the parametrization inside each block. Blockwise IGO-ML is not necessarily equivalent to IGO-ML even when all δti are equal to δt. Proposition 9. The pure rank-µ CMA-ES update (Example 2) is an instance of blockwise IGO-ML for Gaussian distributions, with parameter decomposition θ = (θ1, θ2) where θ1 = C, the covariance matrix, and θ2 = m, the mean vector.

Proof. Given θ t = (C t , m t ), blockwise IGO-ML first updates C as follows:

C * = arg max C (1 -δtC )EP (C t ,m t ) ln p (C,m t ) (x) + δtC i wi ln p (C,m t ) (xi) . (25)
Considering {P (C,m t ) } as an exponential family of Gaussian distributions whose mean vector is fixed to m t , (25) can be viewed as an ordinary IGO-ML step for this restricted model. Then, since (after shifting the origin of the coordinate system to m t ) C is the expectation parameter of the restricted model, the update is given by [START_REF] Sehnke | Parameter-exploring policy gradients[END_REF] namely

C * = C t + δtC λ i=1 wi (xi -m t )(xi -m t ) T -C t .
Next, m is updated as

m * = arg max m (1 -δtm)EP (C * ,m t ) ln p (C * ,m) (x) + δtm i wi ln p (C * ,m) (xi) .
To derive m * , let us differentiate the inside of arg max w.r.t. m and derive the zero point of the derivative. Seeing that ∇m ln p (C * ,m) (x) = (C * ) -1 (x -m), we find the condition

(1-δtm)(C * ) -1 (m t -m * )+δtm i wi(C * ) -1 (xi-m * ) = 0 ,
which holds if and only if

m * = m t + δtm λ i=1 wi(xi -m t ) .
This is equivalent to the pure rank-µ CMA-ES update.

Quantile improvement as in Theorem 6 readily extends to this setting as follows.

Theorem 10. Let the selection scheme be w(u) = 1 [u≤q] /q where 0 < q < 1. Assume that the arg max defining each partial infinite-population IGO-ML update (24) is uniquely determined. Then for 0 < δtj ≤ 1 (j ∈ 1; k ), each infinitepopulation blockwise IGO-ML step (23) leads to q-quantile improvement: Q q P θ t+1 (f ) ≤ Q q P θ t (f ). Moreover, equality can hold only if P θ t+1 = P θ t or if

P θ t+1 [x : f (x) = Q q P θ t (f )] > 0.
Consequently, each infinite-population step of the pure rank-µ CMA-ES update guarantees q-quantile improvement. Indeed, from Proposition 9 this variant of the CMA-ES is an instance of blockwise IGO-ML. Moreover, if each level set of f has zero Lebesgue measure, which often holds for continuous optimization, we have strict q-quantile improvement.

Proof. If P θ t+1 = P θ t , obviously Q q P θ t+1 (f ) = Q q P θ t (f ). We assume P θ t+1 = P θ t in the following.

Set θ t,0 := θ t and θ t,j := Φj (θ t,j-1 ) so that θ t+1 = θ t,k . According to Lemma 8, to prove quantile improvement it is enough to show that J(θ t+1 | θ t ) > 1. Moreover, this implies strict quantile improvement provided P θ t+1 [x : f (x) = Q q P θ t (f )] = 0. According to (20), if Ht(θ t+1 ) > Ht(θ t ) we have that J(θ t+1 | θ t ) > 1. To show that Ht(θ t+1 ) > Ht(θ t ) we decompose Ht(θ t+1 ) -Ht(θ t ) into the sum of partial differences, namely,

Ht(θ t+1 ) -Ht(θ t ) = k j=1
Ht(θ t,j ) -Ht(θ t,j-1 ) , and we will prove that each term is non-negative. Moreover, if P θ t,j = P θ t,j-1 for some j ∈ 1; k , we will have Ht(θ t,j ) -Ht(θ t,j-1 ) > 0 for this j. Since P θ t+1 = P θ t implies P θ t,j = P θ t,j-1 for at least one j ∈ 1; k , we will have that Ht(θ t+1 ) -Ht(θ t ) > 0, resulting in J(θ t+1 | θ t ) > 1.

We proceed as in Theorem 6. Since θ t,j = Φj (θ t,j-1 ) is the only maximizer of (24), we have (1 -δtj )EP θ t,j-1 [ln p θ t,j (x)] + δtj Ht(θ t,j ) ≥ (1 -δtj )EP θ t,j-1 [ln p θ t,j-1 (x)] + δtj Ht(θ t,j-1 ) with equality holding if and only if θ t,j = θ t,j-1 . Rearranging, we get Ht(θ t,j ) -Ht(θ t,j-1 ) > 1 -δtj δtj DKL(P θ t,j-1 P θ t,j ) if θ t,j = θ t,j-1 , and Ht(θ t,j ) = Ht(θ t,j-1 ) if θ t,j = θ t,j-1 . The right-hand side of the above inequality is non-negative for 0 < δt ≤ 1. Therefore, Ht(θ t,j ) -Ht(θ t,j-1 ) ≥ 0 for all j ∈ 1; k . Moreover, since P θ t+1 = P θ t , for at least one j ∈ 1; k we have θ t,j = θ t,j-1 and thus Ht(θ t,j ) -Ht(θ t,j-1 ) > 0 for this j, implying that Ht(θ t+1 ) -Ht(θ t ) > 0. This completes the proof.

Finite Population Sizes

The results above are valid for "ideal" updates with infinite sample size. With finite sample size, the update (9) defines a stochastic sequence (depending on the random sample {xi}) and so one cannot expect monotone q-quantile improvement at each step. Still, we can expect q-quantile improvement with high probability when the population size is sufficiently large.

We provide an analogue of Theorem 6 for finite but large population size. A similar statement holds for blockwise IGO-ML. The proof follows a standard probabilistic approximation argument.

Proposition 11. Let w(•) be the q-truncation selection scheme: w(u) = 1 [u≤q] /q where 0 < q < 1. Let {P θ } be an exponential family of probability distributions, parametrized by its expectation parameter. Assume that the arg max defining the infinite-population IGO-ML step (10) is uniquely defined.

Assume that for all θ ∈ Θ, the derivative ∂ ln P θ (x)/∂θ exists for P θ -almost all x ∈ X and has finite second moment:

EP θ |∂ ln P θ (x)/∂θ| 2 < ∞.
Let 0 < δt ≤ 1. Let θ t+δt λ be the IGO-ML update (9) with sample size λ, and let θ t+δt ∞ be the infinite-population IGO-ML update [START_REF] Dorigo | The ant system: Optimization by a colony of cooperating agents[END_REF]. Assume that θ t+δt ∞ = θ t . Then, with probability tending to 1 as λ → ∞, the finitepopulation update θ t+δt λ results in q-quantile improvement:

Q q P θ t+δt λ (f ) ≤ Q q P θ t (f ) .
Consequently, the same holds for the CE/ML method and the IGO algorithm when they are applied to an exponential family using the expectation parameters.

Note the assumption that the ideal dynamics has not reached equilibrium yet: θ t+δt ∞ = θ t . If θ t+δt ∞ = θ t , the finitepopulation dynamics will just randomly wander around this equilibrium value with some noise, resulting in either improvement or deterioration at each step. Also note that the population size λ needed may depend on the current location θ t in parameter space, as well as the objective function f . For instance, highly oscillating functions f likely require higher population sizes for a consistent estimation of the IGO-ML update.

Proof. For exponential families, the IGO and IGO-ML updates coincide. Under the conditions of the theorem, the finite-population IGO update ( 8) is a consistent estimator of the infinite-population IGO update (5) [5, Proposition 18], implying that θ t+δt λ converges with probability one to θ t+δt ∞ . Under our regularity assumptions on P θ , this implies pointwise convergence of p θ t+δt Gradient based methods with fitness-proportional selection are often employed, especially in reinforcement learning, e.g. policy gradient with parameter based exploration (PGPE) [START_REF] Sehnke | Parameter-exploring policy gradients[END_REF]. One disadvantage of gradient based methods is that the step size has to be calibrated by the user depending on the problem at hand. Alternative methods such as expectation-maximization [START_REF] Dayan | Using expectation-maximization for reinforcement learning[END_REF], including the RPP below, are sometimes employed to avoid this issue. Theorem 12, however, ensures that each natural gradient step improves the expected fitness for 0 < δt ≤ 1 when an exponential family is used with its expectation parameters.

Example 4. The Relative Payoff Procedure (RPP) [START_REF] Hinton | Connectionist learning procedures[END_REF] is a reinforcement learning algorithm, also known as expectationmaximization (EM) algorithm for reinforcement learning [START_REF] Dayan | Using expectation-maximization for reinforcement learning[END_REF]. The RPP expresses a policy on the action space X = {0, 1} d by a Bernoulli distribution P θ (x) parametrized by the expectation parameter. The objective to be maximized is the expectation EP θ [r(x)] of non-negative reward r(x) after taking action x ∈ X. The RPP updates the parameters to Remember the sufficient statistics T (x) for Bernoulli distributions are Ti(x) = xi. Thus the RPP is equivalent to (26) with g • f (x) = r(x) and δt = 1 and can be viewed as a natural gradient ascent with large step.

The RPP is known from [START_REF] Dayan | Using expectation-maximization for reinforcement learning[END_REF] to monotonically improve expected reward, thanks to its expectation-maximization interpretation. Theorem 12 can be thought of as an extension of this result, and also shows monotone improvement for the smoothed RPP, where a step size 0 < δt ≤ 1 is introduced.

Proof. Most of the proof of Theorem 6 carries over. Replacing W f θ t in (18) with g • f /EP θ t [g • f (x)], (18) still holds and we have [START_REF] Malagò | Towards the geometry of estimation of distribution algorithms based on the exponential family[END_REF] propose the natural gradient algorithm for discrete optimization using exponential distributions. However, as they parametrize the exponential distributions by the natural parameters θ = β, Theorem 12 does not guarantee expected fitness improvement for their algorithms, whereas it does so for the algorithm (19) using the expectation parameters.

θ t+δt = θ t + δt EP θ t g • f (x) EP θ t [g • f (x)] T (

FURTHER DISCUSSION

These results contribute to bringing theory closer to practice, by waiving the need for infinitesimal step sizes in gradient ascent. Still, they cover only the "ideal" situation with infinite population size, as well as finite but very large population sizes (by a standard probabilistic approximation argument). Finite population sizes lead to stochastic behavior and so monotone objective improvement at each step occurs only with high probability.

In practice, population sizes used can be quite small, λ ≤ 10, with medium to small step sizes [START_REF] Baluja | Removing the genetics from the standard genetic algorithm[END_REF][START_REF] Hansen | Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES)[END_REF]. It has been shown in [START_REF] Akimoto | Convergence of the continuous time trajectories of isotropic evolution strategies on monotonic C 2 -composite functions[END_REF]Remark 2] that when population size does not tend to infinity, the expectation of the natural gradient estimate [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF] is the natural gradient (5) with a different selection scheme w. So using the truncation weight w(u) = 1 [u≥q] with a small population size and very small step sizes will result, by the machinery of stochastic approximation [START_REF] Borkar | Stochastic approximation: a dynamical systems viewpoint[END_REF][START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], in simulating an infinite-population IGO step with another selection scheme, a situation outside the scope of this article. Our results, on the contrary, suggest using larger populations and larger step sizes instead.

Finally, let us stress that objective improvement is not, by itself, a sufficient guarantee that optimization performs well: in situations of premature convergence, the objective still improves at each step. Premature convergence can occur for large values of the learning rate in some instantiations of IGO and IGO-ML (see the study in [START_REF] Arnold | Information-Geometric Optimization algorithms: A unifying picture via invariance principles[END_REF]); our results say nothing about this phenomenon.

  θ t+1 = EP θ t [xr(x)] EP θ t [r(x)] .

  1≤i≤n is the so-called expectation parameter. For example, the expectation parameter for the multivariate Gaussian distribution encodes the first moment EP θ [x] and the second moment EP θ [xx T ]. Other examples can be found in [4, Section 3.5].

	distributions, are expressed as exponential families. See [4,
	Section 2.3] for examples.
	If we define
	Tn, x → 1} are linearly independent; Z(θ) is
	the normalization factor. This linear independence ensures
	that the manifold of the exponential family is nonsingular.
	Many probability models, including multivariate Gaussian

η(θ) := EP θ [T (x)] = T (x) p θ (x) dx ,

(13)

η = (ηi)

  Because of the second equality of (27), we have the counterpart of (21) asEP θ t [g • f (x) ln p θ t+δt (x)] EP θ t [g • f (x)] -EP θ t [g • f (x) ln p θ t (x)] EP θ t [g • f (x)] ≥ 1 -δt δt DKL(P θ t P θ t+δt ),and moreover, since the maximizer in (27) is unique, the inequality is strict unless θ t = θ t+δt . Hence, since the righthand side is non-negative, by (28) we have lnEP θ [g • f (x)] ≥ ln EP θ t [g • f (x)]with equality only if P θ t = P θ t+δt . This completes the proof. Remark 3. As mentioned in Remark 1, Malagò et al.

			(27)
	+ δtEP θ t	g • f (x) EP θ t [g • f (x)]	ln p θ (x)
	Thanks to Jensen's inequality, we have the counterpart of
	(20) as
	ln EP (28)

x) -θ t = arg max θ (1 -δt)EP θ t [ln p θ (x)] θ [g • f (x)] -ln EP θ t [g • f (x)] ≥ EP θ t [g • f (x) ln p θ (x)] EP θ t [g • f (x)] -EP θ t [g • f (x) ln p θ t (x)] EP θ t [g • f (x)] .


Paul Morel

Mark Van Horn

Francois Budin

Terry Van Dyke

Weili Lin

Elizabeth Bullitt

Brain Stripping Magnetic Resonance Angiographic Images of Tumor-Bearing Mice

Brain stripping is a difficult task in mice with brain tumors. No group has described a fully effective method. We present a new method of defining the brain envelope from magnetic resonance angiographic (MRA) images of both healthy and tumorbearing mice.

METHODS BACKGROUND

 : determine the clusters by merging basins of attractions

CONCLUSIONS RESULTS

UNC CASILAB

Results Evaluation

! Snake [START_REF] Kass | Snakes:Active Contour Models[END_REF] : active contour 1. Initialization of the snake from the final snake of the previous slice 2. Determination of snake parameters automatically 3. Run the snake until final snake to obtain the stripped brain of this slice " On the initial slice ( "desirable" slice) :

1. Initialization of the snake from the contour of the selected region.

!

  Mean shift segmentation: Based on 3 parameters : " h s : spatial domain " h r : range domain " M : minimum number of pixel per region ! Choice "desirable" slice : "Desirable" slice " Brain well delineated by mean shift segmentation " Area of the brain: one of the highest of all slices Choice " Manually : find a "desirable" slice, select the region of the brain. " Automatically : 1. selection of 1 region on each 2. Selection of 1 slice based on shape of the selected region and position of slice in the image. Original image Segmented image Snake of initialization Different steps of the snake Final snake Use of a snake on an image ! Snake-based segmentation " On the other slices :

2. Determination of snake parameters automatically 3 .

 3 Run the snake until final snake to obtain the stripped brain of this slice " Propagation of the snake throughout the image stake on a slice-by-slice basis Diagram of the brain stripping method Brain Stripping Evaluation : the gold standard a manual segmentation of the brain from each MRA image.We compared our results for both speed and accuracy to the semi-automated mode and the snakebased segmentation provided by ITK-Snap. Segmented image of a normal mice Segmented image of a tumor-bearing mice ! Our method gives good results for brain stripping of MRA images of tumor-bearing mice ! The same approach could be employed for T1 or T2 images ! A fully automated approach is under development 3 parameters : " hs : spatial domain " hr : range domain " M : minimum number of pixel per region