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

David Krieg; Erich Novak; Mario Ullrich

Source-linked AI summary

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

David Krieg, Erich Novak, Mario Ullrich

arXiv:2610.33733v1Oct 24, 2026math.FAcs.NAmath.NA

TL;DR

For non-symmetric convex sets, known comparisons between approximation methods were weaker by a factor √n than for symmetric sets. The paper uses affine determinants to improve the comparison, obtaining order-n bounds, or order-√n bounds for Hilbert targets, with examples showing sharpness up to logarithmic factors.

Problem
For non-symmetric convex sets, known comparisons between nonadaptive, adaptive, and randomized approximation errors were weaker by a factor √n than for symmetric sets.
Source: §1 · p. 1
Method
The paper introduces affine determinants to compare affine approximation errors with the minimal errors of randomized and adaptive algorithms.
Source: §1 · p. 2
Results
The comparison factor is reduced to order n, or order √n for Hilbert targets, and examples show both bounds are sharp up to logarithmic factors.
Source: §1 · p. 2
Takeaways & Limitations
The comparisons apply uniformly to arbitrary convex input sets, while stronger estimates can remain available for special spaces.
Source: §1 · p. 2
The uniform bound does not replace stronger lower bounds available for special spaces; for Hilbert spaces with F the unit ball, the constant 27n can be replaced by 2.
Source: §1 · p. 2

Abstract

from arXiv · show

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 in convex sets. We discuss the optimality of the result by examples.

1. Introduction and main result

For non-symmetric convex input sets, previously known comparisons were weaker by a factor √n than those for symmetric sets. The paper closes this gap by comparing affine approximation errors with adaptive and randomized errors, using affine determinants.

1. Introduction and main result

For symmetric input sets, earlier bounds were stronger; without symmetry, known bounds lost a factor √n, which this work closes.The paper also notes that adaptive randomized algorithms can outperform nonadaptive randomized ones in examples, including in the setting of measurements from X′.Source: §1 · pp. 1–3
The comparison factor is reduced to order n, and to order √n when the target space is Hilbert.The proof obtains a coefficient below 27; both comparisons are reported as sharp up to logarithmic factors, even for symmetric input sets.Source: §1 · p. 2
The proof compares affine approximation and algorithm errors through affine determinants, after establishing a new lower bound for randomized and adaptive algorithms.It uses a simplex in the input set and a contraction whose image simplex has maximal volume; the determinant quantity is D_k.Source: §1 · pp. 2–3
The deterministic comparison holds without measurability, while the randomized comparison also applies to the larger root mean square error.For measurable randomized algorithms, the proof applies a common input distribution to each deterministic algorithm and averages over the randomness.Source: §1 · pp. 2–3
Examples show that the bounds are sharp up to logarithmic factors, even for symmetric sets; the optimal logarithmic factors and need for oversampling remain open.For identities ℓ_m^1 → ℓ_m^2 with suitable m=m(n), the stated ratios are at least cn/log(n+1) and c√n/log(n+1), respectively.Source: §1 · p. 2
The result is uniform over arbitrary convex input sets, but does not replace stronger estimates available for special spaces.For Hilbert spaces with F the unit ball of X, the constant 27n can be replaced by 2; other problem-dependent estimates are also noted.Source: §1 · p. 2

2. Affine determinants and the choice of the simplex

The section uses maximal contracted simplex volumes to relate affine approximation error to geometric quantities of the image of F. It selects a large simplex whose determinant information also supports lower bounds for algorithmic errors.

2. Affine determinants and the choice of the simplex

D_k is finite, and D_k > 0 exactly when aff S(F) has dimension at least k.When D_2n = 0, a bounded projection yields an exact affine algorithm with rank at most 2n − 1.Source: §2 · pp. 3–4
Multiplying the determinant-ratio inequalities for k = n + 1 through 2n makes their factors telescope.This combines the successive rank bounds into the comparison used in the theorem.Source: §2 · p. 4
For Hilbert targets, contracted determinants equal the volume of the image parallelotope, and the base-times-height identity converts this into an affine-error bound.The equality follows by choosing a contraction that is isometric on the span of the vectors.Source: §2 · pp. 4–5
For Hilbert targets, the determinant recurrence has θ_k = 1, removing the 2√n factor from the resulting bound.The proof obtains the recurrence from the distance of the residual to the span of the previously selected image vectors.Source: §2 · pp. 4–5
The quotients of D_k are bounded using G_n(T), a quantity that also appears as a lower bound for errors in Section 3.The argument chooses a simplex in F and a contraction with determinant close to D_2n; the simplex is fixed before the algorithm or random seed.Source: §2 · p. 5

3. A lower bound for uniform input

This section establishes lower bounds for algorithms on a convex body in Euclidean space, using uniform input for measurable adaptive algorithms and a centered-body condition for arbitrary deterministic algorithms. The bounds are then applied in the coefficient space of the selected simplex.

3. A lower bound for uniform input

The lower-bound estimates are established in finite-dimensional Euclidean spaces and later applied in the coefficient space of the chosen simplex.The section states both an average-case bound for uniform inputs and a corresponding worst-case bound for arbitrary deterministic algorithms.Source: §3 · p. 6
For a convex body K in R^2n, every measurable adaptive algorithm using at most n linear measurements satisfies the stated uniform-input lower bound.The proposition expresses the bound using G_n(T) and the body’s volume and second-moment quantities.Source: §3 · p. 7
If K has center of mass zero, every deterministic adaptive algorithm without measurability assumptions satisfies the stated worst-case lower bound.The proof fixes the measurements chosen at input 0 and uses a central slice on which the algorithm gives the same reconstruction.Source: §3 · pp. 7–9
For measurable adaptive algorithms, conditioning uniform input on each measurement path reduces the error bound to a lower bound on the corresponding section.The conditional input is uniform on K intersected with the affine information fiber, and the transformed section has volume controlled by G_n(T).Source: §3 · pp. 7–8

4. The uniform distribution on the simplex

The section fixes a uniform probability measure on a simplex independently of any algorithm or random seed, then centers its coefficient-space representation for applying the preceding bounds.

4. The uniform distribution on the simplex

The uniform measure on the selected simplex is normalized affine volume and does not depend on a choice of coordinates or Euclidean structure.Once the simplex is fixed, this probability measure is fixed independently of the algorithm and its random seed.Source: §4 · p. 9
Centering the coefficient simplex produces a body K with center of mass zero.This supplies the centered-body condition needed for the deterministic worst-case bound.Source: §4 · p. 9
The simplex’s volume and second-moment quantities are computed from its barycentric coordinates.The coordinate symmetry gives Eλ_j = 1/N, and the section also records the formula for Eλ_j².Source: §4 · p. 9
The constant C_n in the section is less than 27 for every n ≥ 1.The paper states that Appendix A proves this using Stirling bounds and two direct small-dimension calculations.Source: §4 · pp. 9–10

5. Proof of the main result

The proof reduces algorithm errors to a simplex-based lower bound and combines it with geometric estimates to prove Theorem 1.1. For Hilbert targets, the coefficient improves to (Cn/2)√n.

If D2n = 0, the exact affine algorithm applies; otherwise the proof chooses a near-maximal simplex and its uniform measure.Source: §5 · p. 10
On the simplex parametrization, each measurement becomes a known constant plus a linear functional, while contraction B bounds the reduced error by the original error.Source: §5 · p. 10
For measurable deterministic algorithms the proof invokes Proposition 3.2, then extends the lower bound to randomized algorithms by applying it per seed and using Tonelli.Source: §5 · p. 10
For arbitrary deterministic algorithms, the center of mass of K is zero, allowing the same lower bound for worst-case error before the geometric estimates are combined.Source: §5 · p. 10
For Hilbert targets, Lemma 2.2 removes 2√n, giving coefficient (Cn/2)√n; Cn < 27 completes Theorem 1.1.Source: §5 · p. 10

Remark 5.1 (A possible improvement of the constant)

A more involved randomized argument may improve the constant to 16 using a different simplex measure with Gaussian weights on its vertices.Source: §5 · p. 10

Appendix A. The constant 27

Appendix A verifies the numerical bound Cn < 27 analytically, using substitutions, standard Stirling bounds, and auxiliary inequalities.

Appendix A. The constant 27

The appendix substitutes expressions involving N = 2n+1 and ωn into the bound, then applies standard Stirling bounds.Source: Appendix A · p. 11
An auxiliary inequality is proved by induction from n = 1, alongside direct checks for n = 1 and 2.Source: Appendix A · pp. 11–12
Cn < 27 for every n ≥ 1, establishing the constant used in the main result.Source: Appendix A · p. 12