A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise

Research output: Contribution to journalArticlepeer-review

Abstract

This paper considers complexity bounds for the problem of approximating the global minimum of a univariate function when the function evaluations are corrupted by random noise. We take an average-case point of view, where the objective function is taken to be a sample function of a Wiener process and the noise is independent Gaussian. Previous papers have bounded the convergence rates of some nonadaptive algorithms. We establish a lower bound on the convergence rate of any nonadaptive algorithm.

Original languageEnglish (US)
Pages (from-to)17-27
Number of pages11
JournalJournal of Global Optimization
Volume48
Issue number1
DOIs
StatePublished - Sep 2010

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Keywords

  • Global optimization
  • Noisy information
  • Wiener process

Fingerprint Dive into the research topics of 'A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise'. Together they form a unique fingerprint.

Cite this