Randomized Complexity of Vector-Valued Approximation

Stefan HeinricharXiv 2023 · DOI · arXiv

Introduction

In the field of Information-Based Complexity (IBC), a central theoretical question concerns the "power of adaption." When approximating a function or computing an integral, does an algorithm gain a significant advantage by choosing its sampling points based on previously acquired data? For deterministic linear problems, the answer has long been established: adaptive strategies offer at most a factor-of-two improvement over non-adaptive ones. However, the randomized setting has remained more elusive.

In "Randomized Complexity of Vector-Valued Approximation" (June 2023), Stefan Heinrich demonstrates that for randomized algorithms, the advantage of adaption is not merely marginal but can be substantial. Specifically, the paper proves that for vector-valued approximation, adaptive algorithms can achieve an accuracy $O(\sqrt{n})$ times greater than non-adaptive counterparts, fundamentally shifting our understanding of randomized complexity.

Problem Setting: Vector-Valued Approximation

The research focuses on the linear problem of approximating functions $f$ that map from a two-dimensional grid to a scalar field, effectively treating them as matrices. The input set is defined as the unit ball within specific function spaces, namely $L_p^{N_1}(L_u^{N_2})$.

The primary challenge in this context is reconstructing a matrix-like function where the "importance" or "weight" of different rows is unknown a priori. In a non-adaptive approach, an algorithm must distribute its sampling budget across the entire domain. If the function is sparse—meaning it is mostly zero except for a few highly active rows—a non-adaptive strategy wastes significant resources on uninformative regions.

The Adaptive Randomized Algorithm

Heinrich introduces a novel adaptive randomized algorithm, denoted as $A^2_{n,m,\omega}$ (and its iterated version $A^3$), designed to exploit the structural properties of vector-valued functions. The algorithm operates in two distinct stages:

  1. Randomized Norm Estimation: The algorithm utilizes a small portion of its sampling budget to take initial random samples. These samples are used to estimate the norm (the relative importance or magnitude) of each row in the matrix.
  2. Adaptive Allocation: Based on the initial estimates, the algorithm identifies "heavy" rows. It then concentrates the remaining sampling budget on these specific areas, effectively performing an optimal resource allocation under uncertainty.

To establish the superiority of this approach, the author employs average-case analysis. By constructing specific probability distributions of "difficult" functions and utilizing tools such as Bernoulli random variables and the median-of-means technique, the paper provides rigorous lower bounds that non-adaptive algorithms cannot surpass.

Key Insights and Results

The core realization of the research is that vector-valued problems provide the structural "room" necessary for adaption to thrive. While previous work had identified a small gap of $n^{1/8}$, Heinrich shows that by selecting appropriate function spaces (specifically where $p < q$ and $u > v$), the gap can be expanded to $n^{1/2}$.

The main result, summarized in Corollary 1, compares the $n$-th minimal error of non-adaptive ($e_n^{ran-non}$) and adaptive ($e_n^{ran}$) randomized algorithms. The findings indicate:

  • The Gap: The ratio between non-adaptive and adaptive errors is of the order $n^{1/2}$ (ignoring logarithmic factors).
  • Quantitative Bounds: The paper provides tight upper and lower bounds for specific $L_p$ space configurations. The adaptive advantage is most pronounced when the objective is to minimize "peak" errors (high $q, v$) relative to "average" errors (low $p, u$).
  • Complexity: The paper determines the exact order of randomized $n$-th minimal errors for these vector-valued problems, filling a significant gap in IBC theory.

Conclusion and Future Work

This work demonstrates that adaption can be a powerful tool for resource management in randomized algorithms. However, several questions remain. It is not yet known if $1/2$ is the absolute limit for the gap in linear problems, or if there exist problems where the adaptive advantage is even larger. Furthermore, the extent to which this $n^{1/2}$ gap manifests in other linear problems, such as high-dimensional integration or differential equations, remains a subject for future exploration.

Summary updated

Abstract

We study the randomized $n$-th minimal errors (and hence the complexity) of vector valued approximation. In a recent paper by the author [Randomized complexity of parametric integration and the role of adaption I. Finite dimensional case (preprint)] a long-standing problem of Information-Based Complexity was solved: Is there a constant $c>0$ such that for all linear problems $\mathcal{P}$ the randomized non-adaptive and adaptive $n$-th minimal errors can deviate at most by a factor of $c$? That is, does the following hold for all linear $\mathcal{P}$ and $n\in {\mathbb N}$ \begin{equation*} e_n^{\rm ran-non} (\mathcal{P})\le ce_n^{\rm ran} (\mathcal{P}) \, {\bf ?} \end{equation*} The analysis of vector-valued mean computation showed that the answer is negative. More precisely, there are instances of this problem where the gap between non-adaptive and adaptive randomized minimal errors can be (up to log factors) of the order $n^{1/8}$. This raises the question about the maximal possible deviation. In this paper we show that for certain instances of vector valued approximation the gap is $n^{1/2}$ (again, up to log factors).
BibTeX
@misc{heinrich2023randomized,
  author = {Stefan Heinrich},
  title = {{Randomized Complexity of Vector-Valued Approximation}},
  year = {2023},
  eprint = {2306.13697},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.13697},
}
Figure