  We present bounds between different widths of convex subsets of Banach
spaces, including Gelfand and Bernstein widths. Using this, and some relations
between widths and minimal errors, we obtain bounds on the maximal gain of
adaptive and randomized algorithms over non-adaptive, deterministic ones for
approximating linear operators on convex sets. Our results also apply to the
approximation of embeddings into the space of bounded functions based on
function evaluations, i.e., to sampling recovery in the uniform norm. We
conclude with a list of open problems.
