A lower bound on complexity of optimization on the Wiener space

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper is a study of the complexity of optimization of continuous univariate functions using a fixed number of sequentially selected function evaluations. The complexity is studied in the average case under a conditioned Wiener measure. We show that to obtain an error of at most ε{lunate}, on the order of log log (1 / ε{lunate}) log (1 / ε{lunate}) function evaluations are required.

Original languageEnglish (US)
Pages (from-to)132-139
Number of pages8
JournalTheoretical Computer Science
Issue number2-3
StatePublished - Sep 18 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Average-case complexity
  • Global optimization
  • Wiener measure


Dive into the research topics of 'A lower bound on complexity of optimization on the Wiener space'. Together they form a unique fingerprint.

Cite this