PreprintarXiv licencearXiv
On the power of adaption and randomization 2: Non-symmetric convex sets
Abstract
Let S:X→ Y be a bounded linear operator between real Banach spaces, and let F⊂ X be nonempty, bounded and convex. We prove a2n−1(S,F)≤ 27nmin { erann (S,F), eadan (S,F)}. Here ak is the minimal worst-case error of continuous affine algorithms of rank at most k, and enran and enada 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.
Related
- A HELLY-TYPE THEOREM FOR TWO-COMPONENT CONVEX SETS
- Uniform Continuity of Boundary Crossing for Convex Sets
- On convex bodies with rotationally symmetric planar projections
- Towards Hodge-Riemann relations for non-Archimedean analogs of valuations on convex sets
- An isoperimetric problem for Fourier zeros of centrally symmetric convex bodies
BibTeX
@misc{krieg2026power,
title = {{On the power of adaption and randomization 2: Non-symmetric convex sets}},
author = {David Krieg and Erich Novak and Mario Ullrich},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33733},
eprint = {2610.33733},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33733},
}
RIS
TY - UNPB
TI - On the power of adaption and randomization 2: Non-symmetric convex sets
AU - David Krieg
AU - Erich Novak
AU - Mario Ullrich
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2610.33733
UR - https://arxiv.org/abs/2610.33733
AB - Let S:X→ Y be a bounded linear operator between real Banach spaces, and let F⊂ X be nonempty, bounded and convex. We prove a_2n−1(S,F)≤ 27nmin { e^ran_n (S,F), e^ada_n (S,F)}. Here a_k is the minimal worst-case error of continuous affine algorithms of rank at most k, and e_n^ran and e_n^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.
ER -