Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case

Stefan Heinrich

Abstract

This paper addresses a fundamental question in Information-Based Complexity (IBC): whether adaptive strategies can significantly outperform non-adaptive ones for randomized linear problems. By analyzing discrete parametric integration—modeled as vector-valued mean computation—the study demonstrates that for certain parameter regimes ($2 < p < q \leq \infty$), adaptive randomized algorithms can achieve a performance gain of up to $n^{1/8}$ over their non-adaptive counterparts. This result provides a definitive negative answer to the long-standing conjecture that non-adaptive randomized methods are always nearly optimal for linear tasks.

Introduction

In the field of numerical analysis and computational complexity, algorithms are categorized by how they acquire information. Non-adaptive algorithms determine all sample points in advance, whereas adaptive algorithms choose subsequent sample points based on previously observed values.

For deterministic linear problems, such as standard integration or interpolation, it has been established since the 1980s that adaption offers negligible benefits, improving error rates by at most a factor of 2. However, the role of adaption in randomized algorithms remained an open question for decades. Researchers sought to determine if there exists a constant $c$ such that non-adaptive randomized algorithms are always within a constant factor of the best adaptive ones for linear problems. This paper settles the debate by identifying specific conditions where adaptive sampling provides a clear, power-scale advantage.

Problem Formulation: Parametric Integration

The author investigates "vector-valued mean computation," a discrete analogue of parametric integration. In this setting, the goal is to compute the average of a function over one variable while preserving its structure over another. The error is measured using different $L_p$ and $L_q$ norms.

While the operator $S$ itself is linear—satisfying $S(f+g) = S(f) + S(g)$—the paper explores whether the process of gathering information about $S$ can benefit from the non-linear logic inherent in adaptive sampling.

Methodology

The proof utilizes the framework of Information-Based Complexity (IBC) to compare the performance of a specifically constructed adaptive randomized algorithm against the theoretical lower bounds of any non-adaptive algorithm.

The Adaptive Strategy

The proposed adaptive algorithm employs a two-stage sampling approach:

  1. Norm Estimation: The algorithm uses a small portion of its computational budget ($n$ samples) to estimate the norms of different components of the input vector. This stage utilizes sophisticated randomized norm estimation techniques to identify "important" regions of the input space.
  2. Optimal Resource Allocation: In the second stage, the remaining samples are allocated proportionally to the estimated importance of each region. This "importance sampling on the fly" allows the algorithm to focus its resources where the function's values are most significant.

Lower Bound Analysis

To establish the limitations of non-adaptive methods, the author uses product probability measures and Khintchine’s inequality. The analysis demonstrates that without the ability to "hunt" for peaks in the function based on early data, a non-adaptive sampler is statistically likely to miss critical information, leading to higher error rates.

Key Insights and Results

The Critical Domain

The study reveals that the gap between adaptive and non-adaptive methods is not universal but emerges in a specific geometric regime: when $2 < p < q \leq \infty$. In this domain, the geometry of the $L_p$ spaces allows an adaptive algorithm to exploit the function's structure more effectively than a blind sampler.

Quantifying the Efficiency Gain

The paper proves that the ratio between non-adaptive and adaptive randomized minimal errors, denoted as $\gamma(p, q, n)$, can grow as a power of the number of samples $n$.

  • Maximum Gap: For the case where $p=4$ and $q=\infty$, the gap reaches an order of $n^{1/8}$ (ignoring logarithmic factors).
  • Theorem 4.5: This central theorem provides tight upper and lower bounds for $n$-th minimal errors. It confirms that while the gap is a constant for $p \leq 2$ or $p \geq q$, the adaptive method wins decisively in the $2 < p < q$ range.

Conclusion and Future Directions

This work provides a foundational shift in IBC by proving that linearity of the problem does not imply that non-adaptive information gathering is optimal in a randomized setting. While this paper (Part I) focuses on finite-dimensional spaces to answer the core theoretical question, it sets the stage for Part II, which will extend these findings to infinite-dimensional Sobolev spaces. These spaces are more representative of practical problems in physics and engineering, suggesting that adaptive randomized integration may offer significant real-world advantages for complex parametric tasks.

Summary updated

BibTeX
@article{heinrich2024randomized,
  author = {Stefan Heinrich},
  title = {{Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case}},
  journal = {J. Complex.},
  year = {2024},
  doi = {10.1016/j.jco.2023.101821},
}
Figure