On the ultimate convergence rates for isotropic algorithms and the best choices among various forms of isotropy

Sylvain Gelly 1 Jérémie Mary 1 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : In this paper, we show universal lower bounds for isotropic algorithms, that hold for any algorithm such that each new point is the sum of one already visited p oint plus one random isotropic direction multiplied by any step size (whenever the step size is chosen by an oracle with arbitrarily high computational power). The bound is 1 − O(1/d) for the constant in the linear convergence (i.e. the constant C such that the distance to the optimum after n steps is upp er b ounded by C n ), as already seen for some families of evolution strategies in [19, 12], in contrast with 1 − O(1) for the reverse case of a random step size and a direction chosen by an oracle with arbitrary high computational power. We then recall that isotropy does not uniquely determine the distribution of a sample on the sphere and show that the convergence rate in isotropic algorithms is improved by using stratified or antithetic isotropy instead of naive isotropy. We show at the end of the pap er that b eyond the mathematical proof, the result holds on exp eriments. We conclude that one should use antithetic-isotropy or stratified-isotropy, and never standard-isotropy.
Type de document :
Communication dans un congrès
Parallel Problem Solving from Nature, Sep 2006, Reykjavik, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00112816
Contributeur : Sylvain Gelly <>
Soumis le : jeudi 9 novembre 2006 - 17:16:40
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 6 avril 2010 - 22:04:10

Identifiants

  • HAL Id : inria-00112816, version 1

Collections

Citation

Sylvain Gelly, Jérémie Mary, Olivier Teytaud. On the ultimate convergence rates for isotropic algorithms and the best choices among various forms of isotropy. Parallel Problem Solving from Nature, Sep 2006, Reykjavik, 2006. 〈inria-00112816〉

Partager

Métriques

Consultations de la notice

411

Téléchargements de fichiers

98