Adaptive algorithms for problems involving black-box Lipschitz functions

Suppose we are given a black-box evaluator (an oracle that returns the function value at a given point) for a Lipschitz function with a known Lipschitz constant. We consider queries that can be answered about the function by using a finite number of black-box evaluations. Specifically, we study the problems of approximating a Lipschitz function, approximately integrating a Lipschitz function, approximately minimizing a Lipschitz function, and computing the winding number of a Lipschitz curve in R² around a point. The goal is to minimize the number of evaluations used for answering a query. Because the complexity of the problem instances varies widely, depending on the actual function, we wish to design adaptive algorithms whose performance is close to the best possible on every problem instance. We give optimally adaptive algorithms for winding number computation and univariate approximation and integration. We also give a near-optimal adaptive algorithm for univariate approximation when the output of function evaluations is corrupted by random noise. For optimization over higher dimensional domains, we prove that good adaptive algorithms are impossible.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2004

Author dc:creator

• Baran, Ilya, 1981-

Advisor dc:contributor.advisor

• Erik D. Demaine.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/17934

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/17934