Erich Novak: On the power of adaption

A recent survey with this title appeared in J. of Complexity 12 (1996), 199-237.
This paper has 140 references.




Abstract

Optimal error bounds for adaptive and nonadaptive numerical methods are compared. Since the class of adaptive methods is much larger, a well-chosen adaptive method might seem to be better than any nonadaptive method. Nevertheless there are several results saying that under natural assumptions adaptive methods are not better than nonadaptive ones. There are also other results, however, saying that adaptive methods can be significantly better than nonadaptive ones as well as bounds on how much better they can be. It turns out that the answer to the ``adaption problem'' depends very much on the a priori knowledge about the problem in question; even a seemingly small change of the assumptions can lead to a different answer.

Keywords

adaptive methods, numerical integration, optimal recovery, zero finding, global optimization, worst case error bounds, average case error bounds, error bounds for randomized (Monte Carlo) methods, complexity of numerical problems, information-based complexity

The adaption problem

One of the more controversial issues in numerical analysis concerns adaptive algorithms. The use of such algorithms is widespread and many people believe that well-chosen adaptive algorithms are much better than nonadaptive methods in most situations. Such a belief is usually based on numerical experimentation. In this paper we survey what is known theoretically regarding the power of adaption. We will present some results which state that under natural assumptions adaptive methods are not better than nonadaptive ones. There are also other results, however, saying that adaptive methods can be significantly superior to nonadaptive ones. As we will see, the power of adaption is critically dependent on our a priori knowledge concerning the problem being studied; even a seemingly small change in the assumptions can lead to a different answer.