On the power of adaption and randomization

Abstract

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

References in corpus (6)

• Optimal pointwise sampling for $L^2$ approximation
• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• Exponential tractability of $L_2$-approximation with function values
• Sampling projections in the uniform norm
• Monte Carlo Methods for Uniform Approximation on Periodic Sobolev Spaces with Mixed Smoothness
• Inequalities between s-numbers

Cited by in corpus (2)

• Approximation of Functions: Optimal Sampling and Complexity
• Sampling and entropy numbers in the uniform norm