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

Research output: Contribution to journalArticle


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
Issue number1
StatePublished - Sep 1 2010


All Science Journal Classification (ASJC) codes

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


  • Global optimization
  • Noisy information
  • Wiener process

Cite this