On the power of adaption and randomization

Abstract We present bounds on the maximal gain of adaptive and randomized algorithms over nonadaptive, deterministic ones for approximating linear operators on convex sets. If the sets are additionally symmetric, then our results are optimal. For nonsymmetric sets, we unify some notions of n -widths and s-numbers, and show their connection to minimal errors. We also discuss extensions to nonlinear widths and approximation based on function values, and conclude with a list of open problems.