PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximation of Functions: Optimal Sampling and Complexity

David Krieg, Mario Ullrich

arXiv:2602.02066v2math.NAcs.IT

TL;DR

The paper examines how limited function evaluations constrain approximation and recovery. It surveys general sampling strategies, algorithms, and measurement models, reporting sharp sampling-number bounds and often little practical loss versus ideal benchmarks.

  • Problem

    The paper asks how limited measurements compare with idealized approximation benchmarks and what data complexity is required under different admissible measurements.

    Source: §1 · p. 3

  • Method

    The paper surveys general sampling strategies, approximation algorithms, and nonlinear, adaptive, and randomized measurement settings across broad model classes.

    Source: §1 · p. 4, §7 · p. 100

  • Results

    The paper derives several sharp bounds on sampling numbers and reports that practical sampling algorithms often incur no great loss compared with theoretical benchmarks.

    Source: §1 · pp. 4–5

  • Takeaways & Limitations

    The survey provides general results and strategies intended to apply across many function classes without assuming domain structure.

    Source: §1 · p. 4

    Exact adaptive continuous measurements can yield much weaker bounds under noise, even when the noise is very small.

    Source: §10.3 · p. 169

Abstract

from arXiv · show

We consider approximation or recovery of functions based on a finite number of function evaluations. This is a well-studied problem in optimal recovery, machine learning, and numerical analysis in general, but many fundamental insights were obtained only recently. We discuss different aspects of the information-theoretic limit that appears because of the limited amount of data available, as well as algorithms and sampling strategies that come as close to it as possible. We also discuss (optimal) sampling in a broader sense, allowing other types of measurements that may be nonlinear, adaptive and random, and present several relations between the different settings in the spirit of information-based complexity. We hope that this article provides both, a basic introduction to the subject and a contemporary summary of the current state of research.

1. Introduction and overview

The article surveys approximation under finite, costly, and incomplete information, focusing on sampling algorithms, information complexity, and their relation to theoretical approximation benchmarks. It develops general error bounds, sampling strategies, and comparisons across measurement models while emphasizing broad applicability across function classes.

Problem setting

  • Finite-cost measurements provide incomplete information, creating a fundamental limit on the accuracy of any reconstruction.The framework separates data acquisition from reconstruction and treats physical measurements, simulations, and questionnaires as costly sources of information.Source: §1 · p. 3
  • The survey studies sampling schemes near ideal approximation benchmarks alongside lower bounds on the data required for specific model classes.These lower bounds define information complexity and depend on the admissible measurement class.Source: §1 · p. 3

Scope and contribution

  • The article presents a systematic survey connecting numerical analysis, approximation theory, and theoretical data science through admissible-information models.It emphasizes general results applicable to many model classes without assuming domain structure, using examples mainly to illustrate theoretical power and limitations.Source: §1 · pp. 3–4

Core framework

  • Sampling numbers quantify the smallest worst-case error achievable by algorithms using at most n samples, typically measured in L_p spaces or B(D).The article provides theoretical error bounds and constructive or semi-constructive strategies for sampling points.Source: §1 · p. 4

Approximation benchmarks

  • Across linear and nonlinear benchmarks, the survey reports sharp sampling-number bounds, including comparisons with linear, sparse, entropy, and Hilbert approximation.Some nonlinear bounds are nonconstructive, whereas sparse approximation results are partially constructive; the main sampling-number results are collected in Appendix A.1.Source: §1 · p. 5

Article roadmap

  • Later sections analyze i.i.d. random points, randomized algorithms, high-dimensional tractability, adaptive information, and comparisons among linear, continuous, randomized, and general measurements.The roadmap covers probabilistic and randomized methods, the curse of dimensionality, information-based complexity, s-numbers, and the relative power of adaptation and randomization.Source: §1 · pp. 5–6

2. An easy example and some basic concepts

This section introduces sampling-based function approximation through model classes, measurement and reconstruction maps, worst-case error, and optimality notions. It frames guaranteed error analysis under structural prior knowledge, using Lipschitz and Sobolev examples to characterize reconstruction and sampling points.

Basic concepts

  • Sampling algorithms combine function-evaluation measurements with reconstruction maps, and their worst-case error over a model class provides guaranteed a priori approximation bounds.For fixed sampling points, the radius of information is the best achievable worst-case error over all reconstructions using those measurements.Source: §2 · pp. 8–9

Optimal reconstruction

  • Instance-optimal reconstruction minimizes the error separately for every data vector, while any interpolatory reconstruction is instance- and worst-case optimal up to a factor of two.Instance-optimal decoders are Chebyshev centers of the compatible function sets; interpolatory decoders choose any compatible function and inherit the factor-two guarantee.Source: §2 · pp. 9–10

Lipschitz example

  • For Lipschitz functions, piecewise-linear upper and lower interpolants provide an explicit instance-optimal decoder, while standard piecewise-linear interpolation is optimal only up to a factor of two.The distance-to-samples function fools every algorithm based on the same point evaluations, and zero data are the least informative observations for this symmetric example.Source: §2 · pp. 10–12

Information-based complexity

  • The section frames sampling-number bounds as information-theoretic limits: upper bounds establish achievable algorithms, lower bounds rule out smaller errors, and adaptive measurements do not help in the easy example.These concepts connect optimal recovery of reconstructions with information-based complexity focused on optimizing measurement maps.Source: §2 · pp. 13, 17

Lipschitz example

  • Equidistant sampling points are optimal for the periodic Lipschitz example, and the sampling number satisfies 1/(4n) ≤ g_n(F_Lip, L_p) ≤ 1/(2n), with the p=∞ value 1/(2n−1).The example has both optimal reconstruction for every point set and easily implementable optimal measurement maps, although such complete analyses are unusual for complex model classes.Source: §2 · pp. 14–15

Sobolev examples

  • For Sobolev classes, equidistant points are optimal up to constants, with minimal worst-case error of order n^(-s+(1/q−1/p)+).When p≥q, optimality is equivalent to fill distance O(1/n); when p<q, a few larger holes can remain acceptable, making typical i.i.d. random points optimal.Source: §2 · p. 16

The worst-case setting

  • Structural a priori knowledge about an unknown target function defines a class F of possible functions, so single-function approximation and worst-case analysis over F are treated equivalently.The worst-case error is the best bound guaranteed under the available prior knowledge.Source: §2 · p. 17
  • Studying abstract and concrete classes F reveals how input structure affects the measurements needed for reasonable approximation and can expose beneficial properties, bottlenecks, or opportunities for new algorithms and improved modeling.This motivation applies even when the proper prior assumptions and function class are difficult to identify.Source: §2 · p. 17
  • Although randomness and average errors offer alternative uncertainty models, this work focuses on worst-case analysis and guaranteed error bounds.Source: §2 · p. 17

3. Least squares and best linear approximation

This section develops least-squares and best linear approximation methods across Hilbert and non-Hilbert settings, relating sampling, approximation spaces, and weighted or oversampled algorithms to stability and error guarantees. It extends these results from L2 to uniform and Lp norms, including bounds based on Kolmogorov widths and applications to tensor-product, exponentially convergent, and Smolyak settings.

3. Least squares and best linear approximation

  • Least squares computes the best approximation from V_m under a sampling-based seminorm and, when unique, is a linear orthogonal projection with the projection property.The approximation space may be any m-dimensional linear space, including polynomial, piecewise-polynomial, or trigonometric spaces.Source: §3 · pp. 18–19

3.1. Least squares, discretization, and a first error bound

  • Discretization inequalities make least squares well-defined and stable, while bounding its error by best approximation in a combined norm involving the target and sampling seminorms.The stability constant is tied to the operator norm of the reconstruction map; the resulting bound can use a chosen approximant in V_m.Source: §3.1 · pp. 21–22
  • Directly bounding deterministic sampling error by best L2-approximation is generally impossible because changing values at sample points can drastically alter the algorithm without changing the L2 error.The section instead points to larger norms, such as the sup-norm or a reproducing-kernel Hilbert-space norm, as routes to useful L2-error bounds.Source: §3.1 · p. 23
  • Noisy measurements can be incorporated into the error bounds by adding the stability constant times the weighted Euclidean norm of the noise.The method’s linearity supports this modification for unknown or random perturbations of the sampled values.Source: §3.1 · pp. 24–25

3.2. Bounds by best uniform approximation

  • Unweighted least squares can achieve bounds relative to best uniform approximation when sampling points satisfy a one-sided discretization inequality with a small factor K.For Y=B(D) and n=m, the condition also makes the sampling map bijective, so least squares coincides with the unique interpolant from V_m.Source: §3.2 · pp. 25–27
  • With n=m samples, least squares achieves ∥f−A_Pn(f)∥∞≤(n+1+ε)·d(f,V_n)_∞, and the constant n+1 is optimal.The bound holds for every n-dimensional V_n⊂B(D), while Novak (1988, 1.2.5) showed sharpness for suitable classes F.Source: §3.2 · p. 28
  • Oversampling improves the uniform-norm factor from order m to order √m, but further improvement generally requires superpolynomially many samples.With n=2m samples, the factor n+1 becomes 4√n; exponentially many samples can reduce the factor to a constant, whereas polynomial sampling cannot improve the √m order in general.Source: §3.2 · pp. 29, 33, 34
  • For every m-dimensional V_m⊂L2 and n>m, unweighted least squares admits point sets whose L2 error is bounded by best uniform approximation, with sharp rates for univariate Sobolev classes.The resulting bounds are sharp up to constants for some classes, and Theorem 3.12 gives the optimal order for the stated Sobolev classes.Source: §3.2 · p. 30
  • For Lp-approximation, the factor n^(1/2−1/p)+ generally cannot be replaced by a lower-order term, and the bound is sharp for all 1≤p≤∞.Source: §3.2 · p. 33

3.3. Bounds by best L2-approximation

  • The L2-approximation scheme instead uses nested subspaces and weighted least squares to obtain errors of the same rate as best L2-approximation for functions with pointwise convergent Fourier series.For 4m samples, if d(f,V_m)_2≲m^−α with α>1/2+ε/2, then ∥f−A_mf∥_2≲m^−α.Source: §3.3 · pp. 34–35
  • When μ is a probability measure and V_m contains constants, the weights can satisfy ∥w∥_1≤C_ε, supporting stability against pointwise inaccuracies.The algorithm responds well to weighted-Euclidean noise, while bounded total weights also provide robustness when noise is measured in the maximum norm.Source: §3.3 · p. 35
  • The weighted algorithm is universal: its sampling points and weights do not depend on the approximation rate α, so one construction is optimal across a family of function classes.For polynomial spaces on an interval, the resulting worst-case error has the optimal rate m^−k for every class C^k(D), k∈N.Source: §3.3 · p. 35

3.3.1. L2-approximation on Hilbert spaces

  • Finite trace is equivalent to square-summable singular values and makes the embedding Hilbert-Schmidt, while the eigenspaces of the largest singular values provide simultaneous best L2- and H-approximation spaces.The analysis assumes an injective RKHS embedding into L2; the resulting projection P_m is optimal in both norms for the selected spaces V_m.Source: §3.3.1 · pp. 37–38
  • Theorem 3.24 combines discretization with weighted least squares to provide L2-error bounds for RKHSs embedded injectively into L2 with finite-trace kernels.For every m and n≥m, suitable sampling points and positive weights exist; if μ is a probability measure and 1∈V_m, the weight sum is also bounded.Source: §3.3.1 · pp. 38, 40
  • When singular values decay exponentially, the interpolatory bound can be better than the least-squares bound and sampling numbers decay exponentially with the same base.This applies, for example, to Hilbert spaces with Gaussian or Hermite kernels; under polynomial decay, the least-squares bound is asymptotically sharp.Source: §3.3.1 · pp. 41–42
  • For tensor-product spaces with approximation rate n^-α, the resulting sampling algorithm attains the optimal rate and can outperform sparse-grid constructions in polynomial time.The rate is asymptotically optimal because sampling numbers dominate linear approximation numbers, although no explicit simple sampling-point construction is known.Source: §3.3.1 · pp. 41–42

3.3.2. The non-Hilbert setting

  • In non-Hilbert settings, an artificial RKHS built from an orthonormal L2 system and square-summable monotone weights transfers the Hilbert-space theorem to nested approximation spaces.Proposition 3.30 yields 4m sampling points and weights for functions with pointwise convergent Fourier series, with bounded weights under additional assumptions.Source: §3.3.2 · pp. 44–46
  • Corollary 3.31 bounds sampling numbers for classes satisfying Assumption A using Kolmogorov widths, with choices of spaces and parameters designed to balance the error terms.The result was obtained by Krieg, Pozharska, Ullrich and Ullrich (2025b), with an earlier slightly less general version by Dolbeault et al. (2023).Source: §3.3.2 · pp. 47–48
  • If d_n(F, L2) ≲ n^-α log^β n with α > 1/2, the resulting sampling numbers have the same decay rate.This establishes that sufficiently fast decay of Kolmogorov numbers transfers directly to sampling numbers.Source: §3.3.2 · pp. 48–49
  • Non-Hilbert classes can behave much worse than RKHS classes: d_n(F, L2) ≍ n^-1/2 log^-1 n may coexist with g_n(F, L2) ≍ 1, whereas RKHS bounds imply decay.For the corresponding Hilbert case, the cited bound gives g_n(F, L2) ≲ n^-1/2 log^-1/2 n.Source: §3.3.2 · p. 49
  • Λ(V_m, B) ∈ Θ(m^1/2) for trigonometric monomials, Chebyshev polynomials, spherical harmonics, and certain Walsh and Haar wavelet spaces.For other spaces, Λ(V_m, B) may be larger; interpolation supplies further bounds for 2 ≤ p ≤ ∞.Source: §3.3.2 · p. 50
  • Under Assumption B, L2 approximation can be lifted to Y-approximation through a seminorm estimate, and Theorem 3.35 converts this mechanism into general sampling-number bounds.The framework includes Lp for 1 ≤ p ≤ ∞, continuous functions, and H1 on compact domains; it can be optimal for surprisingly many examples.Source: §3.3.2 · pp. 49, 51, 52
  • The least-squares algorithm is universal across approximation rates and error norms, achieving the optimal Lp rate for mixed-smoothness Sobolev spaces when α > 1/2 and 1 ≤ p ≤ ∞.For other integrability parameters q ≠ 2, Smolyak is optimal in some regions, least squares in others, and neither has known optimal bounds in remaining regions.Source: §3.3.2 · pp. 52–53

4. Construction of sampling points

This section develops constructive procedures for obtaining sampling points and weights underlying the paper’s discretization and least-squares results. It extends the construction to broader norm, space, and weighting settings while identifying practical assumptions and sampling mechanisms.

4. Construction of sampling points

  • Algorithm 1 constructs points and positive weights sequentially by testing oracle-suggested samples through spectral properties of associated Gram matrices.Numerical feasibility requires a finite, manageable basis and an oracle whose suggestions are accepted at a decent rate.Source: §4 · p. 54, §4.1 · p. 57

4.1. Discretization

  • Theorem 4.2 generalizes discretization to different lower and upper spaces, possibly infinite-dimensional upper spaces, norms beyond L2, and equal weights.Its bounds hold for points and weights returned by Algorithm 1, with the construction based on the framework of Batson et al. (2014).Source: §4.1 · pp. 54–55
  • For n≥2m, Christoffel-density sampling with minimal weights has acceptance probability at least 0.06/m^2, improvable to order 1/m by changing δ.The algorithm may also use intuition or a large candidate set; whenever it terminates, the resulting points satisfy Theorem 4.2’s bounds.Source: §4.1 · p. 57

4.2. Weighted least squares

  • Constructive weighted least squares requires a known nested orthonormal basis and can use candidate sets or Christoffel sampling, with expected O(mn) tested random points.Under the basis condition, rejection sampling from μ has acceptance probability of order m^−(2θ−1).Source: §4.2 · pp. 58–60
  • Under the stated probability-measure, basis, and sampling assumptions, Theorem 4.4 provides constructive weighted least-squares bounds, with optimal L2 approximation rates for sufficiently large smoothness.The construction has polynomial runtime in m when function values of basis elements can be computed in polynomial time.Source: §4.2 · pp. 60–61

5. Optimal sampling and nonlinear approximation

This section examines optimal sampling in relation to nonlinear approximation benchmarks, including best sparse approximation, metric entropy, entropy numbers, and Hilbert numbers. It develops sampling-number bounds while discussing their rates, applicability, limitations, and complementary roles.

5.1. Bounds by best sparse approximation

  • For weighted Fourier classes, nonlinear sampling algorithms can outperform linear algorithms, while bounded Fourier-coefficient sums yield useful high-dimensional tractability bounds.The first error term can be bounded by m^-1/2 independently of dimension, and nonlinear rates or tractability results may be unattainable by linear methods.Source: §5.1 · pp. 67, 70
  • The required discretization is equivalent to a restricted isometry property, and O(m log^2 m log N) random samples satisfy it with high probability, whereas comparable deterministic constructions are unavailable.The sampling guarantee is therefore semi-constructive: random points work probabilistically, but verifying the required property is computationally infeasible.Source: §5.1 · pp. 67–68
  • With O(m log^2 m log N) samples, sampling algorithms approach best m-sparse uniform approximation in an N-dimensional bounded-orthonormal-system space.The result applies only when the space is spanned by a bounded orthonormal basis, making it weaker than bounds for general linear subspaces.Source: §5.1 · pp. 68–69

5.2. Bounds by entropy numbers

  • Metric entropy numbers measure the smallest radius of a 2^n-ball cover, serving as an ultimate compression benchmark and translating into Kolmogorov-width bounds through Carl’s inequality.Their decay reflects the compactness of the model class, and entropy-based bounds are presented non-constructively for linear sampling numbers.Source: §5.2 · p. 73
  • Theorem 5.8 bounds sampling numbers for convex symmetric function classes in L_p using entropy numbers, with high-probability i.i.d. sampling from μ.The result applies for 1 ≤ p < ∞ and s ≠ 1/2, and is based on L_p-norm discretization and Dudley’s entropy bound.Source: §5.2 · p. 74
  • The entropy-number bound guarantees convergence for every finite p under weak entropy assumptions, but cannot improve beyond n^-1/(2p) and gives no rate for p = ∞.For L_1-approximation with s ∈ (0, 1/2), its decay rate is at least the entropy-number rate.Source: §5.2 · p. 74
  • For univariate Hölder classes, Theorem 5.8 is sharp exactly when s < 1/2 and p = 1, while Sobolev examples show unresolved optimality for p > 2.For Sobolev classes, the discussed bounds are optimal only for p = 2, leaving extension to the full family as an open problem.Source: §5.2 · p. 75
  • Ullrich’s Theorem 5.12 gives a comparatively elementary approximation result and specializes it to the unit ball of a real p-Banach space with 0 < p ≤ 1, saving factor 2 for real-valued functions.Source: §5.2 · p. 76

5.3. Bounds by other benchmarks

  • Theorem 5.15 bounds sampling numbers through Hilbert numbers, the smallest s-numbers, thereby transferring bounds to other benchmarks such as Kolmogorov widths, entropy numbers, and manifold widths.The resulting geometric-mean bound is often of the same order as the Hilbert numbers when they have polynomial decay, although no explicit achieving algorithm is known.Source: §5.3 · pp. 78–80
  • For unit balls of Banach spaces, Theorem 5.15 improves the factor (n + 1)^3/2, while the claimed Hilbert-space improvement remains open because its proof transfer is incorrect.The real-valued setting does not require the factor 2.Source: §5.3 · p. 80
  • Direct bounds through Kolmogorov, entropy, and Hilbert numbers are each stronger than indirect conversions, so the three approaches have no strict hierarchy.Although each benchmark can be bounded using the others, the resulting indirect sampling-number bounds are worse than the direct ones.Source: §5.3 · p. 81

6. Almost-optimality of i.i.d. sampling

This section examines when i.i.d. sampling approaches optimally chosen sampling across different approximation settings. It develops one-dimensional results and broader least-squares guarantees, while identifying how approximation norms, sampling densities, model classes, geometry, and measurement type govern near-optimality and the need for logarithmic oversampling.

6. Almost-optimality of i.i.d. sampling

  • The section studies i.i.d. samples both as a feasible near-optimal sampling strategy and as a model for data whose sampling locations cannot be chosen freely.The setting uses noiseless random data, although many results can extend to noisy data; randomized algorithms that redraw samples for each input are treated separately.Source: §6 · pp. 82–83

6.1. The easy example revisited

  • For univariate periodic Lipschitz functions, uniform i.i.d. points are optimal up to a constant in L_p for p<∞ and up to a logarithmic factor in L_∞.The logarithmic loss reflects the coupon-collector requirement of hitting all domain boxes for uniform approximation, whereas L_p approximation can tolerate missing some boxes.Source: §6.1 · p. 85

6.2. Least squares and i.i.d. sampling

  • An optimal sampling density for an m-dimensional least-squares space yields error of order σ_m with O(m log m) samples, although the density may be difficult to compute.For general densities, the required sample count is roughly O(M_m log(M_m)) and depends on a characteristic M that can be hard to determine.Source: §6.2 · pp. 86–87
  • With high probability, weighted least squares using i.i.d. samples achieves the best-approximation order on nested spaces when the sampling complexity is controlled by R_m.The guarantee holds uniformly for all functions in the approximation classes, so one fixed random sample works across the class rather than requiring a new sample for each function.Source: §6.2 · pp. 90–91
  • For trigonometric polynomials and spherical harmonics, O(m log m) uniform i.i.d. samples achieve the optimal approximation order.For trigonometric polynomials the hidden constant is dimension-independent, while the correct dimension dependence is not known for spherical harmonics.Source: §6.2 · p. 91
  • For polynomial least squares, O(m^2 log m) uniform samples ensure optimal approximation with dimension-independent constants, while Chebyshev sampling requires O(m log m) samples with a dimension-dependent constant or O(m^ln 3/ln 2 log m) with a dimension-independent constant.These bounds apply to algebraic polynomial spaces indexed by lower sets.Source: §6.2 · p. 91

6.3. Do we need the logarithmic oversampling?

  • i.i.d. uniformly distributed points achieve the same convergence order as optimal points exactly when p<q, whereas p≥q requires logarithmic oversampling.This holds for Sobolev spaces on bounded convex domains and connected compact Riemannian manifolds.Source: §6.3 · p. 93
  • Theorem 6.10 characterizes sampling error geometrically: p≥q uses the covering radius, while p<q uses the smaller Lγ norm of the distance to the sampling set.The latter is an average empty-ball radius, also called the distortion of the point set, and is crucial because random points have much smaller distortion than covering radius.Source: §6.3 · p. 93
  • In the Hilbert case p=q=2, at least Ω(n log n) i.i.d. samples are necessary, for any sampling distribution, to achieve the covering-radius order of n optimal points.The lower bound follows from the coupon collector problem applied to n disjoint balls.Source: §6.3 · p. 94
  • A cube-splitting, piecewise-polynomial algorithm achieves the optimal bounds for uniformly sampled points on (0,1)^d while avoiding the impractical domain decomposition used in the earlier proof.The construction is easy to implement in principle, but its number of cubes is exponential in d, making it unsuitable in high dimensions.Source: §6.3 · pp. 94, 95, 98
  • O(m) i.i.d. Gaussian measurements can match m optimal measurements for polynomially decaying singular values, so Gaussian information outperforms i.i.d. function-value sampling in the Hilbert setting.This removes the logarithmic oversampling required for i.i.d. function evaluations.Source: §6.3 · p. 98

7. Randomized sampling algorithms

This section examines randomized sampling algorithms based on function-dependent random measurements, assessing their worst-case root-mean-square error and approximation guarantees. It covers randomized least-squares and multilevel Monte Carlo constructions, including their sampling complexity, stability assumptions, and runtime trade-offs.

7. Randomized sampling algorithms

  • Randomized algorithms use new random sampling points for each input function and measure performance by worst-case root-mean-square error.This permits better bounds or larger input classes than deterministic algorithms, but error guarantees hold only probabilistically and need not succeed simultaneously for every function.Source: §7 · p. 99

7.3. Randomized least squares algorithms

  • Randomized weighted least squares relies on reconstructional stability and observational stability, and supports sampling designs including i.i.d., subsampling, greedy, and volume sampling.These algorithms can attain the theoretical bounds from Section 7.2; multilevel Monte Carlo with hierarchical Christoffel sampling is less general but may be computationally advantageous.Source: §7 · p. 100, §7.3 · p. 107

7.1. The easy example revisited

  • For Lipschitz-function L_p approximation, Monte Carlo sampling is not superior to deterministic approximation, whereas for a Fourier-defined class randomization helps when s≤1/2.In the latter regime randomized algorithms retain small error while deterministic algorithms are useless; for s>1/2, randomization is not helpful.Source: §7.1 · pp. 100, 101, 103
  • Lower bounds for randomized algorithms use Bakhvalov’s technique, or Yao’s principle, comparing randomized worst-case error with deterministic average-case error.Random sampling can distinguish function pairs that fool deterministic algorithms, so the usual fooling-function argument does not directly apply.Source: §7.1 · pp. 101–102

7.2. How good are optimal random samples?

  • Theorem 7.3 gives universal randomized sampling bounds for every square-integrable function class and sample size, without decay or mild assumptions on Kolmogorov numbers.For compactly embedded reproducing kernel Hilbert spaces, measurable randomized sampling errors are characterized up to universal constants by Kolmogorov numbers; general classes retain a Bernstein-width gap.Source: §7.2 · pp. 104–105

7.3. Randomized least squares algorithms

  • Christoffel sampling uses n=10 m log(4m) points and accepted Gram matrices to ensure reconstructional stability, with the procedure terminating after two draws on average.The resulting least squares algorithm provides the guarantee stated in Theorem 7.6.Source: §7.3 · pp. 109–110
  • n≤b m random samples and weights suffice for any m-dimensional V_m⊂L2, with least squares error bounded by universal constants.This existence result is due to Dolbeault and Cohen (2022a), but the construction is nonconstructive.Source: §7.3 · p. 111
  • For every n≥m, Dolbeault and Chkifa (2024) construct randomized points and weights achieving the least squares guarantee, including oversampling factor b=1.The constructive method substantially improves constants and supports very small oversampling factors, including interpolation.Source: §7.3 · p. 111
  • With oversampling factor r=4, the constructive method matches Theorem 7.6 using 4(m−1) samples instead of 10 m log(4m), while using greedy sampling.The points and weights are selected sequentially by Algorithm 3.Source: §7.3 · p. 111
  • Determinantal sampling avoids sample clustering and may fill data gaps faster than i.i.d. Christoffel sampling, but its proven error guarantees remain worse.The comparison is reported in Belhadji, Bardenet and Chainais (2025, Table 2), and the benefit remains uncertain.Source: §7.3 · pp. 111–112

7.4. Multilevel Monte Carlo methods

  • Multilevel Monte Carlo reaches best approximation from V_m up to a factor using 2 r m samples, provided a hierarchy of approximation spaces is available.The method uses hierarchical Christoffel sampling and stronger assumptions than weighted least squares, but has lower runtime.Source: §7.4 · pp. 113–114
  • If d(f,V_m)∈O(m^-α), multilevel Monte Carlo yields e_n(f)∈O(n^-α) for all α≤log2(r)−1, without an a priori approximation bound.The statement applies to every f∈L2 under the specified oversampling condition.Source: §7.4 · p. 114
  • For constant oversampling, multilevel runtime is O(m t+m^2), versus O(m^4 t) for the optimal weighted least squares construction, favoring multilevel methods when sampling is expensive.Here t denotes the relevant Christoffel-sample generation cost.Source: §7.4 · p. 116

8. The curse of dimensionality

This section examines the curse of dimensionality through sampling complexity and tractability, including the roles of randomization and approximation benchmarks. It also considers structural assumptions such as separability, weights, sparsity, and symmetry that can mitigate or avoid the curse.

8. The curse of dimensionality

  • The curse of dimensionality means that achieving a fixed error requires exponentially many samples in the dimension, whereas tractability requires controlled dependence on dimension and error.Sampling complexity is the minimum number of samples needed to guarantee error below ε; polynomial tractability allows polynomial dependence on dimension and ε^-1, and strong polynomial tractability removes dimension dependence from that bound.Source: §8 · pp. 117–118

8.1. The easy example revisited

  • L^p-approximation of Lipschitz functions suffers from the curse for every 1 ≤ p ≤ ∞, making worst-case approximation practically infeasible in high dimensions.The same curse already occurs for the simpler numerical-integration problem, and enlarging the Lipschitz class by using finite-q norms preserves the lower bound.Source: §8.1 · pp. 119, 122

8.1.1. Does more smoothness help?

  • Higher classical smoothness generally does not restore tractability: even infinitely smooth classes can retain the curse, although particular modified smoothness classes can be quasi-polynomially or weakly tractable.For s-times continuously differentiable functions, a super-exponential-in-d lower bound is known; mixed smoothness can yield dimension-independent error rates without necessarily making the problem tractable, while Vybíral (2020) shows that at least 2^d−1 samples may be needed for a specified quadrature error.Source: §8.1.1 · pp. 122–124

8.1.2. Does randomization help?

  • Randomization yields strong polynomial tractability for integration on any model class contained in the unit ball of L2(D, μ), because Monte Carlo error is dimension-independent.For full function recovery, randomization has situation-dependent effects, and Kunsch (2017, Corollary 2.20) proves that uniform approximation can still suffer from the curse on C∞ classes.Source: §8.1.2 · p. 125
  • For uniform approximation of infinitely smooth functions, the curse of dimensionality persists even for randomized algorithms using arbitrary adaptive linear measurements.For L2-approximation, randomization can instead mitigate the curse; in the mixed-smoothness example, O(d^q) random samples suffice for any fixed ε>0, with q=ln ε^-1, yielding quasi-polynomial tractability.Source: §8.1.2 · pp. 125–126

8.2. Sufficient criteria for tractability

  • Sampling recovery is polynomially or strongly polynomially tractable when the relevant approximation benchmark grows as O(d^s) or O(1), respectively, with analogous criteria for L2, Lp, and uniform norms.For reproducing kernel Hilbert spaces, the corresponding criterion uses W_d; for Lp-approximation it uses R_d, and for uniform approximation it uses V_d.Source: §8.2 · pp. 126, 128, 129
  • Uniform summability of Gelfand widths implies strong polynomial tractability, while uniform square-summability suffices for reproducing kernel Hilbert spaces.These transference criteria shift tractability questions from sampling recovery to more accessible approximation benchmarks such as widths and entropy-related quantities.Source: §8.2 · p. 127

8.3. A collection of tractable problems

  • Structural assumptions can restore tractability: partially separable functions yield polynomial tractability when m∈O(log d) and strong polynomial tractability for constant m under additional assumptions.Other examples include sufficiently fast-decaying weighted spaces, summable Fourier coefficients, ridge functions, symmetric functions, rank-one tensors, and bounded variation; symmetry improves mixed-smoothness recovery from quasi-polynomial to strong polynomial tractability.Source: §8.3 · pp. 130–132
  • Equivalent norms can have a huge effect on tractability even when they preserve the order of convergence of minimal errors.Weighted and unweighted Sobolev spaces of dominating mixed smoothness one illustrate that changing the norm can alter high-dimensional tractability despite equivalent underlying Hilbert spaces.Source: §8.3 · pp. 130–131
  • Summable-Fourier-coefficient methods may provide stronger tractability than weighted spaces, but their square-root Lasso implementation requires a space of dimension N≥2^d and may not have polynomial runtime.Further research is needed to determine whether the tractability results can be matched by an algorithm with polynomial runtime.Source: §8.3 · p. 131

9. A general framework for optimal algorithms

This section develops a general information-based framework for optimal algorithms, encompassing diverse measurements, reconstruction procedures, adaptivity, randomization, and nonlinear methods. It organizes complexity through worst-case errors, widths, s-numbers, entropy properties, and related bounds across specified algorithmic settings.

9. A general framework for optimal algorithms

  • The framework compares optimal algorithms across measurement and reconstruction classes, including arbitrary, continuous, and linear settings, with adaptive or non-adaptive information assembly.It is presented as a unified perspective linking information-based complexity and approximation theory, with comparisons developed further in Section 10.Source: §9 · p. 134, §9.1 · pp. 136–137

9.1. Concepts of optimal algorithms

  • An algorithm approximates a solution map S on a model class F by composing a measurement map with a reconstruction map, and its worst-case error is minimized within prescribed classes.The formulation covers functionals, differential-equation solutions, optimization problems, and function approximation; standard sampling is the special case S = id.Source: §9.1 · p. 135
  • Adaptive measurements may depend on previous observations, whereas non-adaptive methods use the same measurements for every input; adaptive maps can become nonlinear or discontinuous even from linear measurements.Adaptive procedures include methods such as bisection and Newton’s method, while information complexity gives the minimum measurements needed to reach a target error.Source: §9.1 · pp. 137–138
  • For monotone-root finding with function evaluations, non-adaptive methods have minimal error 1/(2(n+1)), while bisection achieves error at most 1/2^(n+1).The adaptive lower bound is noted as more involved and is attributed to Kung (1976) for a similar model class.Source: §9.1 · p. 139
  • The framework recovers sampling numbers, Kolmogorov widths, manifold widths, best m-term approximation, and entropy numbers as optimal errors for suitable measurement and reconstruction classes.The section stresses that the benefit of adaptation depends strongly on the problem S and admissible information; adaptive approximation theory remains incomplete (Novak 1995a, 1996).Source: §9.1 · pp. 140–141
  • For convex symmetric model classes with linear measurements, adaptive algorithms improve worst-case error by at most a factor of two, with equality in several Hilbert-space cases.A corresponding fixed-measurement non-adaptive algorithm can achieve error at most twice that of the adaptive method; in some cases, the factor two disappears.Source: §9.1 · p. 142
  • Under the same convex-symmetric assumptions, nonlinear reconstruction can often be replaced by linear reconstruction for non-adaptive measurements, while continuous reconstruction can similarly suffice for compact domains up to factor 2.The continuous-reconstruction statement is presented for continuous solution maps on compact metric spaces; the necessity of compactness and the factor 2 is unresolved in general.Source: §9.1 · pp. 142–143
  • Randomized algorithms are modeled as measurable probability-indexed families of adaptive deterministic algorithms, with expected error chosen to compare randomization against deterministic methods.Expected error is smaller than root-mean-square error, so it yields stronger upper bounds on the maximal gain from randomization.Source: §9.1 · p. 144
  • Sampling-number bounds for convex symmetric function classes also transfer, up to constant factors, to global optimization based on function evaluations.This applies to computing the minimum and, with residual error, the argmin over compact domains.Source: §9.1 · p. 145

9.2. s-numbers and widths

  • s-numbers generalize singular values from Hilbert-space operators to Banach spaces, where multiple sequences quantify widths, minimal errors, or compactness.The axiomatic framework characterizes smallest and largest s-numbers, bounds different s-numbers against one another, and places minimal errors within the resulting scale.Source: §9.2 · pp. 146, 148, 149
  • Entropy numbers satisfy only conditions (S1)–(S3) and (S5), never vanish, and belong among the smaller s-numbers through Carl’s inequality.For finite-dimensional X with dim(X)=m, ε_n(id_X)=2^-n/m; also, ε_n(id_R)=2^-n.Source: §9.2 · p. 153
  • The axiomatic framework identifies Gelfand numbers as the largest injective s-numbers, Kolmogorov numbers as the largest surjective ones, and Bernstein numbers as the smallest strict injective s-numbers.These properties explain the prominence of several s-numbers and widths independently of approximation theory.Source: §9.2 · p. 153
  • Bounds between s-number scales remain available, but comparable bounds using only s_n are open; a conjecture proposes a_c_n(S) ≤ c_n h_n(S).The weaker width conjecture d_c_n(S) ≤ c_n b_n(S) remains unresolved beyond the known d_n(S) ≤ n^2 b_n(S) bound.Source: §9.2 · p. 153

9.3. Minimal errors and s-numbers

  • For unit balls and linear reconstruction, minimal errors equal s-numbers in key cases: d_n(S)=e_n(S|B_X, Λarb, Ψlin), with analogous identifications for linear measurements.For compact S, minimal errors with linear reconstruction and linear, continuous, or arbitrary measurements are themselves s-numbers.Source: §9.3 · p. 154
  • The general lower-bound theory weakens for adaptive or randomized algorithms on non-symmetric sets, whereas for Hilbert-space operators many s-numbers and deterministic minimal errors coincide.Continuous adaptive algorithms can achieve exponential speed-ups over all s-numbers, and general lower bounds remain open for n≥2.Source: §9.3 · pp. 155–156
  • For arbitrary sets, Gelfand numbers characterize non-adaptive deterministic errors with arbitrary linear measurements up to a factor of two, while Bernstein numbers provide lower bounds for broader algorithms.Theorem 9.23 gives e_n(S|F,Λlin) ≥ 1/30 · b_2n−1(S,F).Source: §9.3 · pp. 155–156

10. Comparison of different types of measurements

This section compares function evaluations with adaptive, randomized, linear, and continuous measurements, examining when these alternatives improve sampling and identifying conditions under which sampling is optimal. It also discusses exponential speed-ups for adaptive continuous measurements and open questions and limitations concerning adaptivity and randomization for linear measurements.

10. Comparison of different types of measurements

  • Adaptive continuous measurements can yield an infinite rate gain, while adaptation, randomness, and general linear measurements individually change polynomial rates by at most a constant for convex classes.The infinite gain is theoretical because all continuous measurements are too broad for practical relevance.Source: §10 · p. 158
  • An m-dimensional vector can theoretically be approximated with arbitrary precision using only O(log m) adaptive and piecewise linear measurements.This result concerns the rather unrealistic power of adaptive continuous measurements.Source: §10 · pp. 158–159
  • The comparison is formulated mainly through polynomial convergence rates for convex symmetric classes, while non-symmetric classes and logarithmic factors remain important open issues.Several bounds are sharp up to logarithmic factors, but more general model classes remain widely open.Source: §10 · p. 159

10.1. Function values vs other measurements

  • For L2- and uniform approximation, non-adaptive deterministic sampling is generally optimal in rate up to a loss of at most 1/2 against broader measurement classes.For Hilbert-space L2-approximation, the sampling rate matches adaptive randomized linear methods; for broader Banach settings and uniform approximation, the loss bound is at most 1/2 and is sharp in examples.Source: §10.1 · pp. 160–162
  • For smooth classes with super-polynomial error decay, randomization, adaptation, and general linear information offer at most an oversampling factor c over deterministic non-adaptive function evaluations.The stated comparison applies for Y∈{L2, B(D)} and compact convex F; whether it extends to other Lp spaces remains open.Source: §10.1 · p. 164

10.2. Power of adaption and randomization for linear measurements

  • For arbitrary linear operators between Banach spaces, adaptation and randomization together have limited rate gains, although fixed-n improvements can be as large as n/log n and yield polynomial-order examples.For Hilbert-to-Hilbert operators, all linear-information algorithm types have equal power; the larger finite-n gains lead to infinite-dimensional rate gaps of order one or one half.Source: §10.2 · pp. 165–166
  • Whether randomization benefits non-adaptive linear algorithms remains open, including whether some class achieves a power gain α > 1/2.For W_2^k([0,1]) into L∞([0,1]), deterministic algorithms have rate n^−k+1/2, while non-adaptive randomized algorithms have upper bound n^−k log n (Solomjak and Tichomirov, 1967; Mathé, 1991).Source: §10.2 · p. 166
  • Adaptive and/or randomized gains on convex non-symmetric sets are bounded above by 3/2, but no example exceeding 1 is known.Thus, the maximal gain may still be 1 for all convex model sets.Source: §10.2 · p. 167
  • For ℓ∞-approximation, adaptivity improves the deterministic non-adaptive lower bound c(√n log n)^−1 to the adaptive upper bound (n + 3)^−1, yielding polynomial gain order 1/2.The maximal adaptive gain on convex non-symmetric sets remains unknown even in the deterministic setting.Source: §10.2 · p. 167

10.3. Power of adaption for continuous measurements

  • Adaptive continuous measurements always provide an exponential speed-up over non-adaptive continuous measurements with continuous reconstruction, although the comparison permits different reconstruction classes.The general result concerns larger manifold numbers for mappings S: F→Y, with F topological and Y metric spaces, and does not fully resolve equal reconstruction classes.Source: §10.3 · pp. 167–168
  • For bounded linear operators between Hilbert spaces, continuous adaptive measurements also yield exponential speed-ups; for Banach spaces, this follows under a rate assumption larger than one.The Hilbert-space conclusion uses coincidence of the relevant s-numbers.Source: §10.3 · p. 168
  • For vector recovery in R^m, worst-case error ε requires only O(log m) adaptively chosen Lipschitz-continuous measurements, independent of ε and the norm.The construction uses a coloring with m + 1 colors and bisection; Figure 10.1 illustrates the planar coloring idea.Source: §10.3 · pp. 168–170, Figure 10.1 · p. 171
  • Linear or adaptive linear measurements and non-adaptive continuous measurements require m measurements for the same worst-case target, making adaptive continuous measurements theoretically far more powerful.The algorithm is not considered practical, and its optimality is unknown; one continuous measurement is insufficient for m > 1 by the Borsuk-Ulam theorem.Source: §10.3 · p. 169
  • Exact knowledge of measurements is essential: even very small noise yields much weaker bounds, though noisy adaptive continuous methods can still outperform non-adaptive methods in some examples.The embedding ℓ_2^m ↪ ℓ_∞^m is cited as an example.Source: §10.3 · p. 169

A. Collection of some bounds

This section summarizes general bounds on sampling numbers, followed by known width and corresponding sampling-number results for univariate Sobolev spaces.

Collection of some bounds

  • The section first collects general sampling-number bounds from Sections 3 and 5, then lists known widths and corresponding sampling numbers for univariate Sobolev spaces.The bounds concern the survey’s running examples and use asymptotic comparisons such as ≍, ≲, and ≳.Source: A. Collection of some bounds · p. 172

A.1. General bounds on sampling numbers

This subsection states sharp general sampling bounds under compactness, convexity, and finite-measure assumptions, using approximation by nested finite-dimensional subspaces. It also identifies a Banach-space unit-ball case covered by Theorem 5.15.

A.1. General bounds on sampling numbers

  • The bounds assume compact D, compact convex F⊂C(D), a finite Borel measure μ, 1≤p≤∞, and an absolute constant c∈N.Only results known to be sharp for some F and Y are stated.Source: §A.1 · p. 172
  • The framework uses nested subspaces V_k⊂L2 with dim(V_k)=k, the approximation error d(F,V_k)_2, and the quantity Λ_m defined through the Y-norm on L2-normalized elements of V_m.The construction applies for any Y satisfying Assumption B.Source: §A.1 · p. 172
  • Theorem 5.15 treats the case where F is the unit ball of a Banach space and states bounds for all s>1.The supplied passage does not include the theorem’s explicit bound.Source: §A.1 · p. 172

A.2. Widths of Sobolev spaces 

This section states piecewise width estimates for Sobolev spaces, covering approximation, Bernstein, Gelfand, Kolmogorov, manifold, entropy, and sampling numbers. The formulas apply for s∈N\{1}, with references and a limitation at s=1.

Notation and scope

  • The section considers approximation, Bernstein, Gelfand, Kolmogorov, manifold, entropy, and sampling numbers, with L∞ identified with B([0,1]) in these cases.The notation s_n(X,Y):=s_n(id) is used for the identity operator from X to Y.Source: §A.2 · p. 173

Theorem A.1

  • Theorem A.1 gives piecewise asymptotic formulas for the listed widths of Sobolev spaces, depending on the relations among p, q, and their conjugates.The estimates include exponents such as n^-s, n^-s+1/q−1/p, n^-s+1/q−1/2, and n^-s+1/2−1/p across the stated parameter regimes.Source: §A.2 · p. 173

References and limitations

  • Known sources are cited for the different width estimates, while fractional smoothness s>0 is covered by Vybíral (2008) and related references.The cited literature includes Pinkus (1985, VII), Tikhomirov (1986, III.2.1), Stesin (1975),, and Novak and Triebel (2006).Source: §A.2 · p. 173
  • Some displayed formulas are not correct for s=1; for example, Malykhin (2025) gives a result for d_n(W_1...).The supplied passage truncates the specific Sobolev-space notation and formula after W_1.Source: §A.2 · p. 173

Index

The index maps the paper’s main concepts, methods, spaces, and complexity notions to their locations. It spans approximation, sampling, information-based complexity, reconstruction, and related analytical tools.

Approximation

  • The index covers approximation concepts including best m-term approximation, best approximation, and hyperinterpolation.It also distinguishes best approximation in L2 and in the uniform norm.Source: Index · p. 190

Function spaces and structure

  • The index lists Hilbert spaces, reproducing kernel Hilbert spaces, bounded orthonormal systems, and restricted isometry properties as relevant function-space and structural settings.It also includes bounded functions and pointwise convergence.Source: Index · pp. 190–191

Sampling and information

  • Sampling and information topics include compressive sensing, leverage score sampling, D-optimal designs, and the radius of information.The index also lists covering numbers, covering radius, and the curse of dimensionality.Source: Index · pp. 190–191

Reconstruction

  • Reconstruction-related entries include decoders, reconstruction maps, measurement maps, encoders, discretization, and expected reconstruction.These entries connect measurement procedures with the maps used to recover functions.Source: Index · pp. 190–191

Complexity and analysis

  • Information-based complexity entries include IBC, complexity, standard information, identity and inclusion maps, Hilbert numbers, and universal discretization.The index also records probabilistic methods, noise, normal equations, and numerical entropy-related terminology.Source: Index · pp. 190–191

Related papers

Loading 2602.02066v2…