PaperlayerView exact revision on arXiv

Source-linked AI summary

Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles

Yann Ollivier, Ludovic Arnold, Anne Auger, Nikolaus Hansen

arXiv:1106.3708v4math.OC

TL;DR

The paper addresses how to optimize arbitrary objectives with probability distributions while limiting arbitrary encoding choices and preserving invariance. It defines the IGO flow from invariance principles, recovers several established algorithms, and finds theoretical and preliminary experimental support for limited diversity loss.

  • Problem

    Expectation-based distribution fitness is sensitive to extreme objective values and is not invariant under increasing transformations of the objective function.

  • Method

    The IGO framework defines an invariant natural-gradient flow for distribution families, with discretization producing algorithms and an infinitesimal weighted maximum-likelihood interpretation yielding IGO-ML.

  • Results

    IGO recovers versions of CMA-ES, NES, PBIL, and cGA, while theoretical arguments and preliminary restricted-Boltzmann-machine experiments support minimal diversity loss during optimization.

  • Takeaways & Limitations

    Starting with high diversity and using multimodal distributions may enable simultaneous exploration of multiple optima within a single run.

  • Takeaways & Limitations

    Monotonicity is proved only for the infinite-population, infinitesimal-step flow, while finite-population dynamics are random; large steps can also cause premature diversity loss.

Abstract

from arXiv · show

We present a canonical way to turn any smooth parametric family of probability distributions on an arbitrary search space $X$ into a continuous-time black-box optimization method on $X$, the \emph{information-geometric optimization} (IGO) method. Invariance as a design principle minimizes the number of arbitrary choices. The resulting \emph{IGO flow} conducts the natural gradient ascent of an adaptive, time-dependent, quantile-based transformation of the objective function. It makes no assumptions on the objective function to be optimized. The IGO method produces explicit IGO algorithms through time discretization. It naturally recovers versions of known algorithms and offers a systematic way to derive new ones. The cross-entropy method is recovered in a particular case, and can be extended into a smoothed, parametrization-independent maximum likelihood update (IGO-ML). For Gaussian distributions on $\mathbb{R}^d$, IGO is related to natural evolution strategies (NES) and recovers a version of the CMA-ES algorithm. For Bernoulli distributions on $\{0,1\}^d$, we recover the PBIL algorithm. From restricted Boltzmann machines, we obtain a novel algorithm for optimization on $\{0,1\}^d$. All these algorithms are unified under a single information-geometric optimization framework. Thanks to its intrinsic formulation, the IGO method achieves invariance under reparametrization of the search space $X$, under a change of parameters of the probability distributions, and under increasing transformations of the objective function. Theory strongly suggests that IGO algorithms have minimal loss in diversity during optimization, provided the initial diversity is high. First experiments using restricted Boltzmann machines confirm this insight. Thus IGO seems to provide, from information theory, an elegant way to spontaneously explore several valleys of a fitness landscape in a single run.

1. Introduction

The paper develops IGO as an invariant, information-geometric framework for black-box optimization over arbitrary search spaces and distribution families. It unifies existing stochastic optimizers while providing principled updates and a route to new algorithms.

  • Motivation: Black-box optimization often updates a probability distribution over candidate solutions, but existing distribution updates may rely on heuristics.The distribution represents current beliefs about where low objective values lie and is updated using sampled evaluations.
  • Framework: IGO uses invariance principles to define a unified optimization method for arbitrary discrete or continuous search spaces and smooth parametric distribution families.The framework reduces dependence on arbitrary representations of the search space, objective, and distribution parameters.
  • Framework: The IGO flow follows the natural gradient of a quantile-based transformation of the objective, then yields explicit algorithms through time discretization and sampling.Its sampling procedure is proved consistent, and the flow is invariant under strictly increasing transformations of the objective.
  • Recovered algorithms: The framework recovers NES, versions of CMA-ES, PBIL, and cGA as instances of IGO for Gaussian and Bernoulli distribution families.The Bernoulli derivation highlights common structure between continuous and discrete optimization.
  • Maximum likelihood: IGO admits an infinitesimal maximum-likelihood interpretation, recovers the cross-entropy method in a particular setting, and defines a parametrization-independent smoothed update called IGO-ML.This connects natural-gradient optimization with weighted log-likelihood maximization and cross-entropy updates.
  • New algorithms: Restricted Boltzmann machine distributions produce a new discrete optimizer that can model bit dependencies and, in a simple setup, reach multiple optima simultaneously.RBM distributions are multimodal, while IGO’s information-theoretic properties favor minimal diversity change during optimization.

2. Algorithm Description

IGO constructs an ideal continuous-time flow by transforming objective values into adaptive quantile-based scores and following their Fisher natural gradient. A finite-step, sample-based algorithm approximates this flow while balancing objective improvement against diversity loss.

  • Objective transformation: IGO replaces raw objective values with an adaptive transformation based on their relative quality under the current distribution, ensuring invariance to increasing objective transformations.This avoids relying directly on scale-sensitive or extreme objective values.
  • Natural gradient: IGO uses the Fisher natural gradient rather than the vanilla parameter gradient, making updates intrinsic to the probability-distribution family and reducing diversity change.The Fisher metric selects the direction that maximizes objective increase for a given Kullback–Leibler distance.
  • Algorithm construction: The algorithm first defines an ideal continuous-time evolution of distribution parameters by an ordinary differential equation, then discretizes it and estimates expectations with Monte Carlo samples.The practical method uses finite time steps and sampled points instead of exact distribution averages.
  • Diversity: Starting from a broad or uniform distribution, the natural-gradient interpretation links optimization progress to minimal loss of diversity, though the strongest interpretation applies near the initial high-diversity regime.Relative to a uniform initialization, KL divergence measures diversity loss.
  • Discretization: For sufficiently small time steps, different IGO discretizations of the same flow differ by only O(δt^2), whereas larger steps can produce substantially different behaviors.The maximum-likelihood update with δt = 1 is reported to exhibit premature diversity loss in the Gaussian setting.

3. First Properties of IGO

The section establishes consistency, monotonicity, invariance, and practical properties of the IGO flow, including its links to rank-based optimization algorithms. It also describes how exponential-family structure simplifies computation and how selection choices affect progress.

  • 3.1 Consistency of Sampling: As N →∞, the sample-based IGO update converges with probability 1 to the IGO update rule under mild regularity assumptions.The convergence proof handles weights that depend non-continuously on the entire sample.
  • 3.1 Consistency of Sampling: For large N, CMA-ES and NES follow the gradient flow of EPθW f, giving a rigorous interpretation of their rank-based updates.This connects the algorithms’ rank-based weights to optimization of an inverse-quantile-reweighted expectation.
  • 3.2 Monotonicity: Quantile Improvement: With w(u) = 1u⩽q, the q-quantile of f improves over time along the infinite-population IGO flow.For q = 1/2, this is median improvement; on discrete spaces, quantile changes occur through successive jumps because of plateaus.
  • 3.2 Monotonicity: Quantile Improvement: The monotonicity guarantee applies only to the IGO flow with N = ∞ and δt →0, not generally to finite-population stochastic algorithms.Large finite populations can nevertheless remain close to the infinite-population trajectory with high probability.
  • 3.3 IGO Flow for Exponential Families: For exponential families, the IGO update can be expressed through covariances and simulated without explicitly computing Fisher matrices, gradients, or parameter derivatives.Gaussian and Bernoulli distributions are examples covered by this simplification.
  • 3.4 Further Mathematical Properties of IGO: The IGO flow is invariant to strictly increasing objective transformations, distribution reparameterizations, and suitable invertible changes of variables in X.The latter two invariances arise from the natural gradient; discretized IGO algorithms inherit f- and X-invariance directly, while θ-invariance is approximate.

4. IGO, Maximum Likelihood, and the Cross-Entropy Method

The paper characterizes IGO as a smooth, weighted maximum-likelihood evolution and develops IGO-ML as a parametrization-independent finite-step update. For exponential families, IGO, IGO-ML, and smoothed cross-entropy updates coincide in expectation parameters, while other parametrizations can change smoothed CEM behavior.

  • IGO as a Smooth-time Maximum Likelihood Estimate: The IGO flow is uniquely characterized as continuously changing the distribution to maximize the log-likelihood of points preferred by f.The weights are updated from quantilized f-preferences as optimization proceeds.
  • IGO-ML: IGO-ML extends this interpretation to finite step sizes by maximizing a weighted likelihood formed from current and previous likelihood contributions.Unlike smoothed CEM, it remains independent of the parametrization of the distribution family.
  • Exponential Families: For exponential families, IGO-ML, IGO in expectation parameters, and smoothed CEM with α = δt coincide.Expectation parameters make maximum-likelihood estimation an empirical averaging operation, so the two averaging orders commute.
  • Cross-Entropy Method: The standard CEM/ML update is recovered when δt = 1, and equals the IGO algorithm in expectation parameters.The standard update is parametrization-independent, whereas smoothed CEM with α < 1 generally is not.
  • Gaussian Example: For Gaussian distributions, IGO-ML and smoothed CEM can produce substantially different variance updates, with smoothed CEM often reducing variance and causing premature convergence.IGO-ML includes an additional variance term arising from averaging likelihoods before taking the maximum-likelihood estimate.
  • Caveat: Large δt can be undesirable because maximum-likelihood updates may converge prematurely, whereas δt = 1 does not match the continuous-time IGO flow after time 1.This is a caution against interpreting a full maximum-likelihood step as the ideal continuous-time evolution.

5. CMA-ES, NES, EDAs and PBIL from the IGO Framework

The IGO framework recovers established optimization algorithms from suitable distribution families and parametrizations, including PBIL, cGA, CMA-ES, and related NES variants. Its natural-gradient structure also clarifies diversity preservation and exposes step-size conditions under which some Gaussian updates prematurely converge.

  • PBIL and cGA: Bernoulli IGO recovers cGA with N = 2 and w1 = −w2, and recovers PBIL under corresponding elite-sample weights and learning rate.PBIL is also both a smoothed CEM and an IGO-ML algorithm in Bernoulli expectation parameters.
  • PBIL and cGA: The best-sample Bernoulli update recovers the PBIL/EGA rule with δt equal to PBIL's learning rate and no random mutation.Different selection schemes yield different PBIL variants.
  • CMA-ES and NES: For Gaussian distributions, the IGO update in mean-and-covariance parametrization coincides with the CMA-ES rank-µ update when ηc = ηm.The update uses weights based on ranked objective values.
  • CMA-ES and NES: CMA-ES deviates from IGO through separate learning rates when N ≪ dim Θ and through path cumulation for step-size control.The Fisher matrix's block structure makes the different learning rates commute with its inverse, but path cumulation is outside IGO.
  • Gaussian Update Variants: As j varies, j = 0 gives rank-µ CMA-ES, j = 1 gives IGO-ML, and j = ∞ gives smoothed CEM; larger finite j yields smaller covariance updates for 0 < δt < 1.As δt approaches zero, all finite-j updates agree to first order, but smoothed CEM does not share this compatibility.
  • Premature Convergence: Above a critical δt, IGO-ML and smoothed CEM can stall on linear functions because variance shrinks to zero before reaching the optimum.The continuous-time IGO flow corresponding to δt → 0 does not stall in this setting.
  • Premature Convergence: For q < 1/2, CMA-ES has infinite critical δt while CEM has critical δt equal to zero; for q above 1/2, all algorithms have critical δt equal to zero.The critical value therefore depends strongly on both the selection ratio and the update family.
  • Restricted Boltzmann Machines: RBM-based IGO supplies a new discrete optimizer that can model dependencies between bits and, on a bimodal objective, retains weight on both optima.A vanilla-gradient descent instead concentrates around only one optimum in the reported experiment.

6. Summary and Conclusion

The IGO framework uses invariance principles to derive a unified optimization flow and algorithms across probability families and search spaces. It recovers established methods, introduces new algorithms, and links natural-gradient updates to diversity preservation.

  • Framework: IGO derives a uniquely defined flow from invariance principles and builds algorithms by discretizing time and space for arbitrary distribution families and search spaces.The framework applies to both discrete and continuous optimization.
  • Algorithms: Gaussian and Bernoulli instantiations recover versions of CMA-ES, NES, PBIL, and cGA, while RBM distributions yield a new discrete optimizer handling dependencies between bits.RBMs provide richer, multimodal models than Bernoulli distributions.
  • Framework: A quantile-based, time-dependent objective transformation rigorously derives rank-based update rules and identifies their infinite-population limit.The flow uses decreasing transformations of objective quantiles under the current distribution.
  • Algorithms: IGO is equivalent to an infinitesimal weighted maximum-likelihood update; with step size 1 in a particular parametrization, it recovers the cross-entropy method and motivates invariant IGO-ML.IGO-ML performs maximum-likelihood updates with arbitrary learning rates while preserving reparametrization invariance.
  • Diversity: Theory suggests IGO minimizes diversity change for a given objective improvement, and preliminary RBM experiments confirm this effect.High initial diversity and multimodal distributions may support simultaneous exploration of multiple optima.
  • Implications: The framework connects continuous and discrete optimization and explains how invariance reduces arbitrary design choices while generalizing behavior across problem classes.This generalization depends on choosing the initial algorithm state appropriately.
  • Limitations: IGO algorithms remain dependent on parameterization after discretization, although their differences are smaller for small learning rates than those of vanilla-gradient methods.Richer models such as RBMs also require larger samples or smaller learning rates for stability.

A.6 IGO, Maximum Likelihood and Cross-Entropy

This section relates maximum-likelihood optimization and cross-entropy updates to IGO while examining learning rates, diversity, and parameterization. It presents IGO-ML as an invariant smoothing alternative and connects diversity preservation to exploration of multiple optima.

  • Cross-Entropy and IGO-ML: Standard CEM is an IGO algorithm in a particular parametrization with learning rate δt equal to 1, but it can lose diversity too quickly.Reducing the learning rate produces smoothed CEM but breaks reparametrization invariance.
  • Cross-Entropy and IGO-ML: IGO-ML performs maximum-likelihood updates with arbitrary learning rates while retaining reparametrization invariance.It coincides with CEM at learning rate 1 and with the IGO flow for small learning rates.
  • Learning Rates: Limited samples make elite points dependent on the current distribution, supporting gradual updates rather than direct jumps to their maximum-likelihood estimate.Successive elite samples may occupy new regions after each update.
  • Diversity: IGO is argued to achieve minimal diversity change for a given objective improvement, with experiments in RBMs showing the theoretical relationship.The framework relates this property to exploration–exploitation balance.
  • Diversity: Natural-gradient updates can outperform vanilla gradients in preserving a balanced distribution between multiple optima by avoiding parameter-space-dependent choices.The vanilla gradient introduces hidden arbitrary choices through its Euclidean parameter metric.
  • Learning-Rate Adaptation: A Fisher-metric cosine between successive parameter updates can guide learning-rate adaptation: positive values suggest increasing and negative values decreasing the rate.The cosine may be noisy, so cumulation over several time steps can be advisable.
  • Parameterization: Although the IGO flow is fully parameterization-invariant, practical discretized IGO algorithms depend on parameterization, especially at larger learning rates.Geodesic discretization offers a parameterization-independent approximation, while IGO-ML is another intrinsic option.

A.10 Finite Sample Size and Noisy IGO Flow

Finite-sample IGO updates are stochastic approximations to a noisy IGO flow, whose noise depends on sample size and step size. In RBMs, Monte Carlo implementation and latent-variable Fisher information affect stability and estimability.

  • Finite-sample dynamics: Finite-sample IGO updates can be viewed as weak approximations to a stochastic differential equation whose drift approaches the IGO flow as N increases.The noise term is determined by the covariance of the update and scales with the step size.
  • Finite-sample dynamics: With fixed N, letting δt approach zero is expected to make the noise disappear.This motivates comparing stochastic algorithms with a noisy rather than ideal noiseless IGO flow.
  • Sample-size scaling: For large N, the update variance is expected to scale as 1/N, making the noise term scale as δt/N.The analysis suggests jointly scaling N and δt can preserve similar behavior at comparable function-call cost.
  • RBM implementation: Applying IGO to RBMs requires Monte Carlo estimates because the relevant expectations and Fisher information are not fully explicit.The implementation uses Gibbs sampling and can optimize either the joint distribution over (x,h) or the marginal distribution over x.
  • RBM implementation: The joint (x,h) formulation is numerically more stable and needs fewer samples for a reliable, invertible Fisher estimate than the marginal formulation.The joint Fisher matrix is at least as informative as the marginal one, and the marginal matrix can be non-invertible for some parameters.

B.3 An Experiment with Two Optima: IGO, Diversity, and Multimodal Optimization.

The RBM experiment compares IGO with a vanilla-gradient variant on a bimodal binary objective. IGO generally preserves positive mass near both optima, whereas the vanilla gradient converges to only one.

  • Experimental setup: The experiment uses a two-optimum objective on {0,1}^d, with randomized complement-related optima and both natural- and vanilla-gradient updates.The main setting is d = 40 with one latent variable; experiments used N = 10,000 and also N = 10.
  • Two-optimum behavior: Over 300 runs, IGO usually converges to a distribution assigning positive mass to both optima, while vanilla gradient converges to only one.Figure 3 visualizes ten representative runs using nearest-sample distances to each optimum.
  • Diversity: IGO preserves the balance between the two hidden modes, whereas vanilla gradient optimization loses the zero mode.Figure 4 reports the median average hidden-variable value over 300 runs with 16th- and 84th-quantile error bars.
  • Diversity: The results illustrate the prediction that IGO favors preserving distributional entropy for a given objective improvement.Using richer multimodal distributions could support simultaneous exploration of multiple valleys or nearly equally deep valleys.

B.4 Breach of Symmetry by the Vanilla Gradient.

The RBM experiment exposes an asymmetry in the vanilla gradient: it favors one hidden-state encoding and loses multimodality. The natural gradient compensates for this parametrization-dependent asymmetry.

  • Observed asymmetry: Vanilla gradient optimization loses multimodality by consistently setting the hidden variable h to 1.The observed preference is not inherent to exchanging the labels 0 and 1 in the RBM representation.
  • Geometric origin: Exchanging hidden-state labels changes the RBM parameters without changing the represented distribution class, but it does not preserve the vanilla gradient’s Euclidean metric.Consequently, the vanilla gradient produces different ascent trajectories under equivalent hidden-variable encodings.
  • Natural-gradient correction: The natural gradient is invariant to this hidden-variable relabeling and offers a systematic way to restore symmetry to the update.The two implementations differ specifically by inclusion of the Fisher matrix.
  • Interpretation: Symmetry preservation alone does not explain simultaneous convergence to both optima; the diversity-preserving property of IGO provides the additional interpretation.A symmetry-preserving stochastic method could still select either single optimum across separate runs.

C.1 Invariance Properties

IGO’s intrinsic construction yields exact flow-level invariance under objective transformations, parameter reparametrization, and suitable search-space transformations. Discretized algorithms retain these properties approximately, with errors governed by the step size and family-preservation conditions.

  • Objective invariance: IGO flow trajectories are unchanged by strictly increasing transformations of the objective function.This makes optimization independent of the numerical scale or monotone re-expression of f.
  • Parameter invariance: Under a smooth bijective parameter transformation, the reparametrized IGO trajectory is exactly the corresponding transformed original trajectory.For finite N and positive δt, parameter-reparametrization invariance holds only approximately as δt approaches zero.
  • Discretization effects: IGO updates under different parameterizations coincide to first order in δt, differing generally by O(δt^2), whereas vanilla-gradient trajectories can diverge by O(δt) per step.The smaller discrepancy is the basis for describing IGO algorithms as more parametrization-invariant.
  • Search-space invariance: For affine-invariant distribution families, IGO optimizes a function and its affine-transformed image equally well after the corresponding initialization change.This generalizes the analogous invariance property known for CMA-ES.
  • Search-space invariance: Search-space invariance requires a one-to-one transformation that globally preserves the chosen distribution family.Under that condition, the transformed IGO flow is the pushforward of the original flow; discretization adds an O(δt^2) per-iteration error.

C.2 Speed of the IGO Flow

The IGO flow has bounded, Fisher-metric speed, while finite-step algorithms can deviate through discretization and sampling noise. The step size has an intrinsic information-theoretic interpretation, and inconsistent selection directions reduce progress.

  • Speed and stability: Bounded IGO-flow speed prevents finite-time explosion and, on complete Fisher manifolds, leaving the valid distribution family.The corresponding finite-step algorithm may not inherit this property because of O(δt^2) approximation terms.
  • Information rate: At most 1/2 δt^2 q0(1 − q0) bits are introduced per iteration for truncation selection w(q) = 1q⩽q0, neglecting error terms.This gives δt an intrinsic interpretation as a control on information introduced into Pθ.
  • Information rate: The Kullback–Leibler divergence provides an external measure of learning rate because it matches the Fisher metric locally up to a factor 1/2.For small steps, KL(Pθt+δt || Pθt) can be estimated from old and new log-likelihoods on Monte Carlo samples.
  • Selection geometry: Speed reaches its upper bound only when good points suggest a common direction; inconsistent directions make updates smaller.Such inconsistency is expected when N < dim Θ and may also indicate noisy signals or an inadequate distribution family.
  • Examples: For Gaussian distributions with fixed identity variance, linear optimization moves at constant speed 1/√(2π) ≈ 0.4, whereas rapidly varying objectives move much more slowly.The slower motion occurs because good and bad points occur in all directions.
  • Noisy objectives: For noisy objectives, the infinite-sample update becomes deterministic after averaging noise, but the effective average weight is generally flatter than the noiseless weight.Noisy IGO can equivalently be modeled as ordinary IGO on X×[0,1] with an independent noise coordinate.

C.4 The IGO Flow for Linear Functions on {0, 1}d and Rd

For linear objectives, the IGO flow yields convergence results for Bernoulli distributions and explicit behavior for isotropic Gaussian distributions. The Gaussian dynamics depend critically on the truncation fraction, while Bernoulli convergence requires nondegenerate initialization.

  • Bernoulli distributions: For linear functions on {0,1}^d, the Bernoulli IGO flow is the δt → 0 limit of the IGO-PBIL update.This connects the continuous-time flow directly to the discrete PBIL algorithm.
  • Bernoulli distributions: Starting any Bernoulli coordinate at θi = 0 permanently prevents sampling value 1 there, so the flow effectively operates in a lower-dimensional space.The convergence statement therefore requires initial coordinates in (0, 1].
  • Bernoulli distributions: Under bounded, nonincreasing, nonconstant selection weights, θ = (1, …, 1) is stable and every trajectory starting in (0, 1]^d converges to it.A Lyapunov function decreases strictly away from the target.
  • Gaussian distributions: The Gaussian linear-function solution is obtained after reducing the objective by invariance to f(x) = x1 and simplifying the flow using a standard normal coordinate.The resulting coefficients determine whether the step size grows or shrinks.
  • Gaussian distributions: For isotropic Gaussian distributions on linear objectives, truncation selection with q0 < 1/2 makes the step size grow exponentially while the mean moves toward −∞.When q0 ≥ 1/2, the step size instead shrinks exponentially and the mean becomes stuck.

D.2 Proof of Theorem 6 (Convergence of Empirical Means and Quantiles)

Theorem 6 is established by showing that empirical averages and rank-based quantile estimates converge almost surely as the sample size grows. Strong-law and Glivenko–Cantelli arguments control the two approximation components.

  • Empirical means: As N → ∞, independent samples from Pθ yield almost-sure convergence of empirical averages to their Pθ expectations.The argument applies the strong law of large numbers to the relevant summands.
  • Empirical quantiles: Rank-based weights are handled by comparing sample ranks with empirical quantiles, including averaging over possible rankings when fitness ties occur.The tie convention averages w((r + 1/2)/N) over admissible ranks.
  • Error control: Boundedness of the selection scheme supplies the error bounds needed to control the weighted empirical terms.The proof denotes the bound on |w| by B and bounds each resulting component.
  • Empirical quantiles: The Glivenko–Cantelli theorem gives uniform convergence of empirical distribution functions, causing the relevant quantile errors to tend to zero almost surely.The proof bounds rank and quantile discrepancies by ε for sufficiently large N.

D.3 Proof of Proposition 7 (Quantile Improvement)

The quantile-improvement proof shows that a sufficiently small IGO ascent step lowers the selected quantile unless the gradient vanishes. The argument accommodates plateaus through separate strict and non-strict quantile statements.

  • Quantile improvement: For truncation weights, the selected quantile cannot increase after a sufficiently small IGO step and becomes strictly smaller without objective plateaus.The proof uses the increase of the transformed objective under gradient ascent.
  • Quantile improvement: If the gradient vanishes, the flow is stationary and the quantiles remain unchanged.Thus strict improvement is excluded precisely at stationary points in the argument.
  • Quantile improvement: The proof handles ties at the quantile by separating the probabilities below, at, and above the quantile threshold.This introduces p−, pm, and p+ and yields the non-strict inequality when pm ≠ 0.
  • Regularity conditions: The theorem relies on a smooth, nonredundant parameterized distribution family with sufficient regularity in θ.The assumptions include a one-to-one parameter-to-distribution map and smoothness of the relevant expectation.

Proof

The proof establishes natural-gradient identities for exponential families and derives the IGO update in expectation parameters. It also relates Fisher-metric quantities to covariance expressions used in the update.

  • The covariance of sufficient-statistic terms equals the Fisher information entries, linking the covariance expression to I_ij.
  • The parameter-sum identity converts the weighted Fisher-information expression into the variation of the expected sufficient statistics.
  • Proposition 29 identifies the natural-gradient components with the vanilla gradient components in the corresponding natural parameters.
  • The natural-gradient identity does not imply that vanilla gradient ascent is identical across arbitrary parameterizations.
  • The Fisher matrix in expectation-parameter coordinates is obtained as the inverse Fisher matrix by substituting the corresponding parameter variation.
  • The proof concludes that the first statement of Theorem 12 gives the IGO update’s form in expectation parameters.

D.6 Proof of Proposition 20 and Corollary 21 (Speed of IGO)

The proof bounds the IGO flow’s speed using variance and covariance inequalities, then connects finite-population updates to the continuous flow and extends the construction to randomized objectives.

  • Proof of Proposition 20 and Corollary 21 (Speed of IGO): For a centered L2 random vector, the relevant variance is bounded by the largest covariance-matrix eigenvalue times the squared norm of the coefficient vector.
  • Proof of Proposition 20 and Corollary 21 (Speed of IGO): Quantile-based transformed fitness can be represented as a conditional expectation, yielding Var W_fθ(x) ≤ Var_[0,1] w through Jensen’s inequality.
  • Proof of Proposition 20 and Corollary 21 (Speed of IGO): In Fisher-orthonormal coordinates, the covariance of the score gradient is the identity, whose largest eigenvalue is 1.
  • Proof of Proposition 20 and Corollary 21 (Speed of IGO): The finite-population IGO update’s speed differs from the continuous IGO flow speed by o(1) as population size N tends to infinity.
  • Proof of Proposition 20 and Corollary 21 (Speed of IGO): Randomized objectives are handled by augmenting the search space with an independent uniform variable and applying IGO to the resulting deterministic function.
Loading 1106.3708v4…