Let $X\subset Y$ be Banach spaces and $B_X:=\{x\in X: \|x\|_X\le1\}$ be the unit ball of $X$.
The goal is to find an approximation of every element from $B_X$ with error measured in $Y$ by using at most $n$ linear measurements, i.e., functionals on $X$.
That is, given an info map $N_n:X\to\Bbb{R}^n$ (linear and bounded) and a reconstruction map $\varphi:\Bbb{R}^n\to Y$ (arbitrary), we call $A_n:= \varphi\circ N_n: X\to Y$ a deterministic (non-adaptive) algorithm. We define the minimal worst-case error of such algorithms by $$ e_n^{\rm det}(X,Y) := \inf_{A_n}\ \sup_{x\in B_X} \|x-A_n(x)\|_Y, $$ where the infimum is over all deterministic algorithms.
Now, a randomized algorithm $R_n$ is a random variable whose realizations are deterministic algorithms, i.e., $R_n\colon \Omega\times X \to Y$ is specified by a family of deterministic algorithms $(R_n^\omega)_{\omega\in\Omega}$ and a probability space $(\Omega,\mathcal{A},\Bbb{P})$. We define the minimal worst-case error of randomized algorithms by $$ e_n^{\rm ran}(X,Y) := \inf_{R_n}\ \sup_{x\in B_X} \Bbb{E}\|x-R_n(x)\|_Y, $$ where the infimum is over all $R_n$ and all corresponding probability spaces.
It might be intuitively clear that always $e_n^{\rm ran}(X,Y) \le e_n^{\rm det}(X,Y)$, because one has more algorithms and a weaker error criterion in the randomized setting. (There are some mild issues with measurability, see the ref. below.)
The question is: How much smaller can it be?
To be precise, what is the largest $\alpha\ge0$ such that for some "example" of $X$ and $Y$ we have
$$
e_n^{\rm ran}(X,Y) \le n^{-\alpha}\cdot e_n^{\rm det}(X,Y) \qquad \text{ for all}\quad n\in\Bbb{N}?
$$
Some things are known:
- If $X$ and $Y$ are both Hilbert spaces, then randomization does not help, and we have $\alpha =0$.
- For $X=W_2^k([0,1])$, i.e., the Sobolev space on the interval, and $Y=L_\infty([0,1])$, we have $e_n^{\rm det}(X,Y) \asymp n^{-k+1/2}$ and $e_n^{\rm ran}(X,Y) \lesssim n^{-k} \log(n)$, proving that $\alpha=\frac12$ is possible (up to log-factors).
- By a recent general result, we get that $\alpha>1$ is not possible, at least if $(e_n^{\rm ran})$ is regularly decaying, e.g. like $n^{-s}$.
Hence, there remains a gap for $\alpha$ that could be narrowed, e.g., by providing a better example than the one given in 2. above.
These results, the corresponding references and some more details can be found in arXiv:2406.07108.
Btw, note that $e_n^{\rm det}(X,Y)$ corresponds, up to a factor of 2, to the Gelfand numbers of the embedding $I:X\hookrightarrow Y$, defined by $c_n(I):=\inf\{\sup_{x\in B_X\cap M}\|x\|_Y: M\subset X, {\rm codim}(M)\le n\}$, a well-studied quantity in Banach space geometry.
