Uniform approximation of vectors using adaptive randomized information
<|reference_start|>Uniform approximation of vectors using adaptive randomized information: We study approximation of the embedding $\ell_p^m \rightarrow \ell_{\infty}^m$, $1 \leq p \leq 2$, based on randomized adaptive algorithms that use arbitrary linear functionals as information on a problem instance. We show upper bounds for which the complexity $n$ exhibits only a $(\log\log m)$-dependence. Our results for $p=1$ lead to an example of a gap of order $n$ (up to logarithmic factors) for the error between best adaptive and non-adaptive Monte Carlo methods. This is the largest possible gap for linear problems.<|reference_end|>
@article{kunsch2024uniform,
    title={Uniform approximation of vectors using adaptive randomized information},
    author={Robert J. Kunsch and Marcin Wnuk},
    journal={arXiv preprint arXiv:2408.01098},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.01098},
    primaryClass={math.NA cs.NA}
}