On the power of adaption and randomization 2: Non-symmetric convex sets

Abstract

Let $S:X\to Y$ be a bounded linear operator between real Banach spaces, and let $F\subset X$ be nonempty, bounded and convex. We prove $$a_{2n-1}(S,F)\le 27n\min \{e_n^{\mathrm{ran}}(S,F),e_n^{\mathrm{ada}}(S,F)\}.$$ Here $a_k$ is the minimal worst-case error of continuous affine algorithms of rank at most $k$, and $e_n^{\mathrm{ran}}$ and $e_n^{\mathrm{ada}}$ are the minimal errors of adaptive randomized and deterministic algorithms using at most $n$ continuous linear measurements. This shows that the gain of adaption and randomization, and even nonlinearity, is limited by a factor $27n$ for approximation in convex sets. We discuss the optimality of the result by examples.