Maximal gain from randomization with nonadaptive linear measurements
Let $S\colon X \to Y$ be a bounded linear operator between real Banach spaces, to be approximated on the closed unit ball $B_X$. A deterministic nonadaptive algorithm has the form $A(x) = \Phi(\lambda_1(x), \dots, \lambda_n(x))$ with fixed $\lambda_j \in X'$ and an arbitrary map $\Phi\colon \mathbb{R}^n \to Y$. A randomized nonadaptive algorithm $(A_\omega)$ chooses such a list of functionals and a reconstruction from a random seed $\omega$, independently of the input, uses at most $n$ measurements for every $\omega$, and has jointly measurable error. Let $$e_n^{\mathrm{det}}(S) = \inf_A \sup_{x \in B_X} \|Sx - A(x)\|_Y, \qquad e_n^{\mathrm{ran}}(S) = \inf_{(A_\omega)} \sup_{x \in B_X} \mathbb{E}_\omega \|Sx - A_\omega(x)\|_Y,$$ the randomized error being the expected norm, not the root mean square, and for a nonnegative sequence $u = (u_n)$ let $\operatorname{rate}(u) = \sup\{\alpha \ge 0 : u_n = O(n^{-\alpha})\}$. Krieg, Novak and Ullrich proved $\operatorname{rate}(e_n^{\mathrm{det}}(S)) \ge \operatorname{rate}(e_n^{\mathrm{ran}}(S)) - 1$ for every such $S$, even against randomized algorithms that choose their measurements adaptively, with $1/2$ in place of $1$ when $X$ or $Y$ is a Hilbert space. For the embedding of $W^k_2([0,1])$ into $L_\infty([0,1])$, $k > 1/2$, the optimal deterministic error is of order $n^{-k+1/2}$ (Solomjak and Tichomirov), while nonadaptive randomized algorithms achieve $O(n^{-k} \log n)$ (Mathé). Hence $1/2 \le G \le 1$ for the quantity $G$ below, as Krieg and Ullrich record.
Problem. Determine $$G = \sup_S \Bigl[\operatorname{rate}\bigl(e_n^{\mathrm{ran}}(S)\bigr) - \operatorname{rate}\bigl(e_n^{\mathrm{det}}(S)\bigr)\Bigr],$$ the supremum taken over bounded linear operators between real Banach spaces with finite rates. In particular, can nonadaptive randomization improve the polynomial rate by strictly more than $1/2$?
Source: Krieg, Novak and Ullrich (2025), Section 6.1, and Krieg and Ullrich (2026), Section 10.2, equation (10.10), as the maximal gain in rate from randomization for nonadaptive algorithms; stated for unit balls of real Banach spaces by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- FA
- Keywords
- AIM Open Applied Problems, information-based complexity, linear information, randomized algorithms
References
@article{krieg2025power,
author = {Krieg, David and Novak, Erich and Ullrich, Mario},
title = {On the power of adaption and randomization},
journal = {Forum Math. Sigma},
volume = {13},
year = {2025},
pages = {e152},
doi = {10.1017/fms.2025.10101},
eprint = {2406.07108},
archivePrefix = {arXiv},
}
@article{krieg2026acta,
author = {Krieg, David and Ullrich, Mario},
title = {Approximation of functions: optimal sampling and complexity},
journal = {Acta Numer.},
volume = {35},
year = {2026},
pages = {273--457},
doi = {10.1017/S0962492925100287},
eprint = {2602.02066},
archivePrefix = {arXiv},
}
@article{solomjak1967,
author = {Solomjak, M. Z. and Tichomirov, V. M.},
title = {Some geometric characteristics of the embedding map from {$W^\alpha_p$} to {$C$}},
journal = {Izv. Vys\v{s}. U\v{c}ebn. Zaved. Matematika},
number = {10},
year = {1967},
pages = {76--82},
}
@article{mathe1991,
author = {Math{\'e}, Peter},
title = {Random approximation of {S}obolev embeddings},
journal = {J. Complexity},
volume = {7},
number = {3},
year = {1991},
pages = {261--281},
doi = {10.1016/0885-064X(91)90036-W},
}
@misc{aim-nonadaptive-randomization-gain,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Maximal gain from randomization with nonadaptive linear measurements}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/555-nonadaptive-randomization-gain.md},
note = {Entry 555 at commit a153f46, 2026-10-13},
}
Resolution claims
We determine the supremum of the improvement in polynomial convergence rate due to randomization for approximation of bounded linear operators between real Banach spaces using nonadaptive continuous linear measurements. The supremum is one. We construct fixed infinite-dimensional operators whose gains tend to one, with worst-case expected-norm error and at most \(n\) measurements for every random seed. The construction combines a …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00761, "Maximal gain from randomization with nonadaptive linear measurements", clopen.solutions.