On the power of adaption and randomization 2: Non-symmetric convex sets
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^{\rm ran}_n (S,F), e^{\rm 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^{\rm ran}$ and $e_n^{\rm 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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.33733
curl -X POST /api/v1/records/arxiv/2610.33733/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.33733/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'