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

Abstract

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.

Final published version

References in corpus (2)

• Learning Feature Hierarchies with Centered Deep Boltzmann Machines
• Notes on information geometry and evolutionary processes

Cited by in corpus (48)

• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• CEM-RL: Combining evolutionary and gradient-based methods for policy search
• Turning Statistical Physics Models Into Materials Design Engines
• Learning Feature Hierarchies with Centered Deep Boltzmann Machines
• On the Covariance-Hessian Relation in Evolution Strategies
• Yet another but more efficient black-box adversarial attack: tiling and evolution strategies
• CMA-ES with Learning Rate Adaptation
• On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization
• Global convergence of neuron birth-death dynamics
• CMA-ES with Learning Rate Adaptation: Can CMA-ES with Default Population Size Solve Multimodal and Noisy Problems?
• Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding
• Dynamic Optimization of Neural Network Structures Using Probabilistic Modeling
• Importance mixing: Improving sample reuse in evolutionary policy search methods
• You Only Compress Once: Towards Effective and Elastic BERT Compression via Exploit-Explore Stochastic Nature Gradient
• The Extended Kalman Filter is a Natural Gradient Descent in Trajectory Space
• Information-geometry of physics-informed statistical manifolds and its use in data assimilation
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster
• Optimal transport natural gradient for statistical manifolds with continuous sample space
• Verifiable Conditions for the Irreducibility and Aperiodicity of Markov Chains by Analyzing Underlying Deterministic Models
• An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms
• Limited-Memory Matrix Adaptation for Large Scale Black-box Optimization
• On Entropy Regularized Path Integral Control for Trajectory Optimization
• Distributed Evolution Strategies with Multi-Level Learning for Large-Scale Black-Box Optimization
• The Bayesian Learning Rule
• Information Newton's flow: second-order optimization method in probability space
• Meta Learning Black-Box Population-Based Optimizers
• Kernelized Wasserstein Natural Gradient
• Controlling Model Complexity in Probabilistic Model-Based Dynamic Optimization of Neural Network Structures
• Cooperative Coevolution for Non-Separable Large-Scale Black-Box Optimization: Convergence Analyses and Distributed Accelerations
• Pairwise MRF Calibration by Perturbation of the Bethe Reference Point
• Monotone Improvement of Information-Geometric Optimization Algorithms with a Surrogate Function
• CoNES: Convex Natural Evolutionary Strategies
• The Variational Predictive Natural Gradient
• The gradient flow of the polarization measure. With an appendix
• Challenges of Interaction in Optimizing Mixed Categorical-Continuous Variables
• Information-geometric optimization with natural selection
• Stochastic natural gradient descent draws posterior samples in function space
• Coordinate Descent with Online Adaptation of Coordinate Frequencies
• Black-box optimization using geodesics in statistical manifolds
• A Mathematical Walkthrough and Discussion of the Free Energy Principle
• Sample Reuse via Importance Sampling in Information Geometric Optimization
• Adaptive Risk Sensitive Model Predictive Control with Stochastic Search
• Non-local Optimization: Imposing Structure on Optimization Problems by Relaxation
• Black-box Optimizer with Implicit Natural Gradient
• Mirror Natural Evolution Strategies
• Parameterless Stochastic Natural Gradient Method for Discrete Optimization and its Application to Hyper-Parameter Optimization for Neural Network
• Diagonal Acceleration for Covariance Matrix Adaptation Evolution Strategies
• Feature selection based on cluster assumption in PU learning