Simple and Cumulative Regret for Continuous Noisy Optimization

Sandra Astete-Morales 1, 2 Marie-Liesse Cauwet 1, 2 Jialin Liu 1, 2 Olivier Teytaud 1, 2
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 : Various papers have analyzed the noisy optimization of convex functions. This analysis has been made according to several criteria used to evaluate the performance of algorithms: uniform rate, simple regret and cumulative regret. We propose an iterative optimization framework, a particular instance of which, using Hessian approximations, provably (i) reaches the same rate as Kiefer-Wolfowitz algorithm when the noise has constant variance (ii) reaches the same rate as Evolution Strategies when the noise variance decreases quadratically as a function of the simple regret (iii) reaches the same rate as Bernstein-races optimization algorithms when the noise variance decreases linearly as a function of the simple regret.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 617, pp.12-27
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01194564
Contributeur : Olivier Teytaud <>
Soumis le : dimanche 20 septembre 2015 - 03:26:32
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : lundi 28 décembre 2015 - 22:49:57

Fichier

noc3re.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01194564, version 1

Citation

Sandra Astete-Morales, Marie-Liesse Cauwet, Jialin Liu, Olivier Teytaud. Simple and Cumulative Regret for Continuous Noisy Optimization. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 617, pp.12-27. 〈hal-01194564〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

175