Function recovery and optimal sampling in the presence of nonuniform evaluation costs
Ben Adcock 1 · 2025
Read Function recovery and optimal sampling in the presence of nonuniform evaluation costs by Ben Adcock 1 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-10613.txt.
Introduction
Rebuilding a function from sampled points gets tricky when some points cost far more to measure than others. Ben Adcock works out the sampling math for that case in a 2025 paper. Samples are drawn at random and fitted by weighted least squares. The cost of each point follows a cost map that may spike at some spots. The goal is a sampling plan that keeps total expected cost low.
A recovery guarantee ties accuracy to two known shape functions of the space. The recipe adapts to general cost maps. Polynomial spaces get two concrete plans, proven near-best for fast-growing costs. The work suits pricey simulations and experiments alike.
Catalog record
| CREATOR | Ben Adcock 1 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-10613
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Function recovery and optimal sampling in the presence of nonuniform evaluation costs Ben Adcock 1 Abstract We consider recovering a function f : D → ℂ f:D\rightarrow{\mathbb{C}} in an n n -dimensional linear subspace 𝒫 \mathcal{P} from i.i.d. pointwise samples via (weighted) least-squares estimators. Different from most works, we assume the cost of evaluating f f is potentially nonuniform, and governed by a cost function c : D → ( 0 , ∞ ) c:D\rightarrow(0,\infty) which may blow up at certain points. We therefore strive to choose the sampling measure in a way that minimizes the expected total cost. We provide a recovery guarantee which asserts accurate and stable recovery with an expected cost depending on the Christoffel function and Remez constant of the space 𝒫 \mathcal{P} . This leads to a general recipe for finding a good sampling measure for general c c . As an example, we consider one-dimensional polynomial spaces. Here, we provide two strategies for choosing the sampling measure, which we prove are optimal (up to constants and log factors) in the case of algebraically-growing cost functions. † † tocauthor: Ben Adcock † † institute: Simon Fraser University, Burnaby, BC, Canada 1 Introduction Countless applications require one to construct an accurate estimator of an unknown function f:D\rightarrow{\mathbb{C}} defined over a domain D (typically D\subseteq{\mathbb{R}}^{d} ) from noisy samples y_{i}=f(x_{i})+e_{i},\quad i=1,\ldots,m. (1) In many such applications, data is expensive to acquire, yet there is significant freedom in choosing the sample points x_{i} . The construction of good points has spurred a vast amount of research across different fields, such as optimal design of experiments in statistics, active learning in machine learning, and optimal information in information-based complexity. In recent years, this question has been essentially settled in the case where one strives to construct an estimator \hat{f} in a fixed, but arbitrary n -dimensional subspace \mathcal{P}\subseteq L^{2}_{\varrho}(D) . Drawing the samples x_{1},\ldots,x_{m} i.i.d. according to the probability measure \mu whose density is proportional to the Christoffel function of \mathcal{P} (so-called Christoffel sampling ) is a near-optimal random sampling strategy [ 8 , 12 ] (see [ 1 ] for a review). Specifically, the estimator \hat{f} obtained via a weighted least-squares fit to the data ( 1 ) yields a near-best recovery of f from \mathcal{P} provided the number of samples m\gtrsim n\log(n) scales log-linearly in n=\dim(\mathcal{P}) . Refinements of this approach can also further reduce the sampling budget by removing the \log(n) term (see [ 6 , 10 , 13 , 14 ] and references therein). 1.1 Optimal sampling with nonuniform evaluation costs It is common in applications to assume a fixed cost-per-evaluation model, i.e., evaluating f(x_{i}) involves the same amount of resources (computational, physical, or otherwise) regardless of the choice of x_{i} . However, in practice evaluation costs may be highly variable depending on the location of x_{i} . Nonuniform evaluation costs are problematic when any sampling strategy optimized for a uniform cost model strives to place more samples at locations with higher evaluation costs. In the case of Christoffel sampling, for instance, this in effect means regions where the Christoffel function is large. While Christoffel sampling is optimal (up to constants and log factors) for reducing the total number of samples, it may be highly suboptimal in terms of the total evaluation cost. With this in mind, in this paper we consider function recovery in the setting of nonuniform evaluation costs and, specifically, how this affects the choice of sampling measure. We consider a cost function c:D\rightarrow(0,\infty) and, rather than the problem of optimizing the x_{i} for a fixed maximum sampling budget m , we consider the problem of optimizing the x_{i} subject to a fixed total cost C_{\mathsf{tot}}=c(x_{1})+\cdots+c(x_{m}) . We focus on weighted least-squares estimators in arbitrary n -dimensional subspaces \mathcal{P} with sample points x_{1},\ldots,x_{m} chosen i.i.d. with respect to some probability measure \mu . Thus, the matter at hand is how to chose \mu judiciously in terms of \mathcal{P} and c to ensure as accurate an approximation to f as possible. 1.2 Setup We now describe our setup in more detail. This is based on [ 1 ] . Let (D,\mathcal{D},\varrho) be a probability space and L^{2}_{\varrho}(D) be the Lebesgue space of square-integrable functions f:D\rightarrow{\mathbb{C}} with respect to \varrho . Suppose that \mu that is absolutely continuous with respect to \varrho , let v=\,\mathrm{d}\mu/\,\mathrm{d}\varrho and define the weight function w:D\rightarrow[0,\infty] as w(x)=1/v(x),\quad x\in D. (2) Let f\in L^{2}_{\varrho}(D) be the function to recover, x_{1},\ldots,x_{m}\sim_{\mathrm{i.i.d.}}\mu and consider samples ( 1 ). Let \mathcal{P}\subset L^{2}_{\varrho}(D) be an arbitrary n -dimensional subspace, termed the approximation space . We make the mild, but convenient assumption that 1\in\mathcal{P} , where 1 is the constant function equal to one almost everywhere. We then consider weighted least-squares fit \min_{p\in\mathcal{P}}\frac{1}{m}\sum^{m}_{i=1}w(x_{i})|y_{i}-p(x_{i})|^{2}. (3) Despite involving L^{2} functions, this problem is well-defined with probability one, since the sample points x_{i} are drawn randomly from \mu\ll\varrho . Let c and C_{\mathsf{tot}} be as above. Since C_{\mathsf{tot}} is a random variable, we define the expected cost C_{\mathsf{exp}}={\mathbb{E}}(C_{\mathsf{tot}})=m\cdot\int_{D}c(x)\,\mathrm{d}\mu(x) (4) (we write C_{\mathsf{exp}}=+\infty if c is not integrable with respect to \mu ). In this paper, we are interested in conditions that ensure the approximation \hat{f} given by ( 3 ) is quasi-best in the sense that the L^{2}_{\varrho} -norm error {\|f-\hat{f}\|}_{L^{2}_{\varrho}(D)} is proportional (up to the noise e_{i} ) to the best approximation error \inf_{p\in\mathcal{P}}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|f-p\right|\kern-1.07639pt\right|\kern-1.07639pt\right|} measured in some suitable norm {\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|} . With this in hand, the main questions we address in this paper are: (i) Given a measure \mu and cost function c , how large should the expected cost C_{\mathsf{exp}} be to ensure a quasi-best approximation? (ii) How should we choose \mu to minimize C_{\mathsf{exp}} ? We remark in passing that the noise terms e_{i} in ( 1 ) are not the focus of this paper. For concreteness, we assume the noise is deterministic and bounded, and aim to show that the error of the estimator \hat{f} scales linearly in {\|e\|}_{2} , where e=(e_{i})^{m}_{i=1} . Other noise models, including statistical models, could readily be considered instead. 1.3 Motivations and related work This work is motivated by surrogate model construction in UQ. Here, f is typically a (quantity-of-interest) of a parametric PDE, with x\in D representing the parameters. A black-box numerical simulation is used to evaluate f(x) , which often involves significant computational cost. It is common to assume constant cost for any x\in D . However, in practice, the cost may vary significantly with x . For instance, certain parameter values may lead to PDE solutions involving shocks, oscillations, boundary layers or other behaviours, all of which require finer meshes in any (adaptive) PDE discretization. This problem has commonly been tackled by multi-level and multi-fidelity methods [ 11 , 18 ] . In these approaches, one is able to access approximations f_{h}(x)\approx f(x) with different accuracies (fidelities) and different evaluation costs, which are then combined to design accurate estimators given a fixed cost budget. In this work, we take a different perspective. We assume f is evaluated by a single model, represented as a true black-box, where the cost of an evaluation is determined solely by the only input x . Our work is also inspired by [ 17 ] , although it addresses a