Information-geometric optimization algorithms: a unifying picture via invariance principles

MaRDI QIDQ5361281zbMATH OpenFDO

Authors Ludovic Arnold, Anne Auger, Nikolaus Hansen, Y. Ollivier

Publication date 27 September 2017

Full work available at URL https://arxiv.org/abs/1106.3708, http://jmlr.csail.mit.edu/papers/v18/14-467.html

zbMATH Keywords

black-box optimizationevolution strategyinformation-geometric optimizationinvariancenatural gradientrandomized optimizationstochastic optimization

Mathematics Subject Classification ID

Parametric inference (62F99) Stochastic programming (90C15) Derivative-free methods and methods using generalized derivatives (90C56)

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.

Recommendations

• Objective improvement in information-geometric optimization
• Information-geometric optimization: the interest of information theory for discrete and continuous optimization. (Abstract)
• Optimization via Information Geometry
• Principled design of continuous stochastic search: from theory to practice
• Information Geometry of the Gaussian Distribution in View of Stochastic Optimization

Cited in

(34)

• Verifiable conditions for the irreducibility and aperiodicity of Markov chains by analyzing underlying deterministic models
• Online natural gradient as a Kalman filter
• Theoretical foundation for CMA-ES from information geometry perspective
• Optimal transport natural gradient for statistical manifolds with continuous sample space
• An ODE method to prove the geometric convergence of adaptive stochastic algorithms
• Information geometry of physics-informed statistical manifolds and its use in data assimilation
• Laplace approximation and natural gradient for Gaussian process regression with heteroscedastic Student-\(t\) model
• Combinatorial optimization with information geometry: the Newton method
• Natural gradient flow in the mixture geometry of a discrete exponential family
• Information Geometry of the Gaussian Distribution in View of Stochastic Optimization
• Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
• Designing an optimal search algorithm with respect to prior information
• Principled design of continuous stochastic search: from theory to practice
• Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
• Warped Riemannian metrics for location-scale models
• Harmless overfitting: using denoising autoencoders in estimation of distribution algorithms
• scientific article; zbMATH DE number 7306852 (Why is no real title available?)
• Global Sensitivity Analysis for Optimization with Variable Selection
• Optimization via Information Geometry
• Objective improvement in information-geometric optimization
• Information-geometric optimization: the interest of information theory for discrete and continuous optimization. (Abstract)
• Information Geometry and Interior-Point Algorithms
• Global linear convergence of evolution strategies with recombination on scaling-invariant functions
• Entropic Trust Region for Densest Crystallographic Symmetry Group Packings
• Analysis of surrogate-assisted information-geometric optimization algorithms
• Riemannian Natural Gradient Methods
• Natural reweighted wake-sleep
• A framework using nested partitions algorithm for convergence analysis of population distribution-based methods
• The Bayesian central limit theorem for exponential family distributions: a geometric approach
• Learning symmetries and non-Euclidean data representations via collective dynamics of generalized Kuramoto oscillators
• A principle for global optimization with gradients
• Natural variational annealing for multimodal optimization
• Weight adaptation for improving parallel performance of adaptive stochastic natural gradient
• Gradient is all you need? How consensus-based optimization can be interpreted as a stochastic relaxation of gradient descent

This page was built for publication: Information-geometric optimization algorithms: a unifying picture via invariance principles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361281)