Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains

Anne Auger 1 Nikolaus Hansen 1
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : In this paper, we consider \emph{comparison-based} adaptive stochastic algorithms for solving numerical optimisation problems. We consider a specific subclass of algorithms called comparison-based step-size adaptive randomized search (CB-SARS), where the state variables at a given iteration are a vector of the search space and a positive parameter, the step-size, typically controlling the overall standard deviation of the underlying search distribution. We investigate the linear convergence of CB-SARS on \emph{scaling-invariant} objective functions. Scaling-invariant functions preserve the ordering of points with respect to their function value when the points are scaled with the same positive parameter (the scaling is done w.r.t. a fixed reference point). This class of functions includes norms composed with strictly increasing functions as well as \emph{non quasi-convex} and \emph{non-continuous} functions. On scaling-invariant functions, we show the existence of a homogeneous Markov chain, as a consequence of natural invariance properties of CB-SARS (essentially scale-invariance and invariance to strictly increasing transformation of the objective function). We then derive sufficient conditions for asymptotic \emph{global linear convergence} of CB-SARS, expressed in terms of different stability conditions of the normalised homogeneous Markov chain (irreducibility, positivity, Harris recurrence, geometric ergodicity) and thus define a general methodology for proving global linear convergence of CB-SARS algorithms on scaling-invariant functions.. As a by-product we provide a connexion between comparison-based adaptive stochastic algorithms and Markov chain Monte Carlo algorithms.
Type de document :
Article dans une revue
SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2016
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00877160
Contributeur : Anne Auger <>
Soumis le : jeudi 2 juin 2016 - 16:57:14
Dernière modification le : jeudi 5 avril 2018 - 12:30:12

Fichiers

LinearCVAuger-Hansen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00877160, version 7
  • ARXIV : 1310.7697

Citation

Anne Auger, Nikolaus Hansen. Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2016. 〈hal-00877160v7〉

Partager

Métriques

Consultations de la notice

519

Téléchargements de fichiers

78