Christoffel Adaptive Sampling for Sparse Random Feature Expansions

Ben Adcock, Khiem Can, Xuemeng Wang · 2026

Read Christoffel Adaptive Sampling for Sparse Random Feature Expansions by Ben Adcock, Khiem Can, Xuemeng Wang (2026) 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-2603-18251.txt.

Introduction

Adcock, Can, and Wang add Christoffel adaptive sampling to sparse random feature expansions. Random feature models fit multivariate functions and solve PDEs with low cost. Sparse versions help when data is scarce, but sample choice still matters. The Christoffel function guides picks toward points that inform the current basis most. Tests show adaptive sampling keeps high accuracy with fewer samples across approximation tasks.

Catalog record

CREATORBen Adcock, Khiem Can, Xuemeng Wang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59899
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.18251

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Christoffel Adaptive Sampling for Sparse Random Feature Expansions Thanks: Submitted to the editors August 10, 2026. Ben Adcock, Khiem Can, Xuemeng Wang Abstract Random Feature Models (RFMs) have become a powerful tool for approximating multivariate functions and solving partial differential equations efficiently. Sparse Random Feature Expansions (SRFE) improve traditional RFMs by incorporating sparsity, making it particularly effective in data-scarce settings. In this work, we integrate active learning with sparse random feature approximations to improve sampling efficiency. Specifically, we incorporate the Christoffel function to guide an adaptive sampling process, dynamically selecting informative sample points based on their contribution to the function space. This approach optimizes the distribution of sample points by leveraging the Christoffel function associated with an iteratively-chosen basis obtained by the sparse recovery solver. We conduct numerical experiments comparing adaptive and non-adaptive sampling strategies with the SRFE framework and examine their accuracy for various function approximation tasks. Overall, our results demonstrate the advantages of adaptive sampling in maintaining high accuracy while reducing sample complexity for SRFE, highlighting its potential for scientific computing tasks where data is expensive to acquire. keywords sparse recovery; sparse random features; multidimensional function approximation; sampling strategies; adaptive sampling; Christoffel functions Funding. BA acknowledges support from the Natural Sciences and Engineering Research Council of Canada (NSERC) through grant RGPIN/2470-2021. BA & XW acknowledge the support of FRQ (Fonds de recherche du Québec) – Nature et Technologies through grant 359708. † † runningheads: Christoffel Adaptive Sampling for Sparse Random Feature Model / MSC 41A46, 41A63, 65D15, 94A20 1 Introduction Many scientific computing processes require approximating complex functions in more than one dimension, where obtaining data is difficult and uniform sampling quickly becomes inefficient. We provide an adaptive approach to improve the sampling process. In contrast to the standard machine learning setting, which draws a single fixed dataset, this approach allows the training data to be selected strategically and then reused to refine the sampling strategy. Such a setting is reasonable in many applications where data acquisition is expensive or limited, such as numerical simulations, physical experiments, or scientific computing tasks that require function evaluations at high computational cost. 1.1 Overview The goal of this work is to improve multivariate function approximation through an adaptive sampling process guided by a designed selection criterion. Here adaptive sampling refers to the process in which samples are selected dynamically across iterations: existing samples are reused, and new samples are chosen based on the function approximation obtained in the previous iteration. Throughout this work, we consider a domain D\subset\mathbb{R}^{d},d\geq 1 , with underlying probability measure \rho , and an unknown target function f:D\rightarrow\mathbb{R} . Given numbers 1\leq m_{1}<m_{2}<\cdots , we approximate the function using a nested collection of sample points (previous samples are retained across iterations): \{x_{k}\}_{k=1}^{m_{1}}\subseteq\{x_{k}\}_{k=1}^{m_{2}}\subseteq\cdots (1) Using the training data \{(x_{k},f(x_{k}))\}_{k=1}^{m_{i}} , i=1,2,\ldots , we compute a sequence of approximations \hat{f}_{1},\hat{f}_{2},\ldots . The procedure we implement involves both adaptive approximation and adaptive sampling . At step i , given the approximation \hat{f}_{i} is used to compute new sample points \{x_{k}\}^{m_{i+1}}_{k=1} (adaptive sampling), which are then used to compute the new approximation \hat{f}_{i+1} (adaptive approximation). In doing so, we aim to achieve rapid decrease of the approximation error \|f-\hat{f_{i}}\|_{L^{2}_{\rho}(D)} as the number of iterations i\rightarrow\infty . In particular, we aim for faster decrease over standard nonadaptive sample procedures – specifically, Monte Carlo (MC) sampling, where sample points x_{k} are drawn i.i.d. from the underlying probability measure \rho . 1.2 Main contributions In scientific machine learning, data scarcity arises in many applications, such as Physics-Informed Neural Networks (PINNs) for PDEs [ 20 , 29 , 37 , 47 ] , operator learning [ 9 , 26 , 1 , 15 , 16 , 22 , 24 , 25 , 49 ] , image recovery [ 7 , 27 , 30 , 35 , 38 , 45 ] and physical system modeling [ 43 , 11 , 10 ] . It is therefore imperative to design highly sample-efficient algorithms. To cope with the issue of data scarcity, we implement a representation framework that is effective in approximating functions in the low-data regime. The Random Feature Model (RFM) is a well-known and increasingly widely-used technique approximating multivariate functions in scientific machine learning. However, for high accuracy, RFM usually requires a large dataset – in particular, more data than trainable parameters. Sparse Random Feature Expansion (SRFE) was introduced in [ 21 ] to address the issue of limited data by incorporating sparsity to improve data efficiency. However, prior work on SRFE considers only nonadaptive, MC sampling. Our main contribution in this work is to enhance the accuracy of SRFE in the limited data regime through adaptive sampling. Our procedure is based on Christoffel Adaptive Sampling (CAS), which is an extension of so-called Christoffel Sampling (CS) to nonlinear approximation spaces. CS is an active learning technique for (weighted) least-squares approximation in linear approximation spaces. While CS provides near-optimal recovery guarantees for linear spaces, many machine learning tasks involve nonlinear spaces. CAS facilitates the use of CS for nonlinear spaces, by dynamically implementing CS as part of an adaptive sampling process. We combine CAS and SRFE in this work, introducing Christoffel Adaptive Sampling for Sparse Random Feature Expansions (CAS-SRFE). A major challenge we address is efficiently computing the samples generated by CAS. Differing from previous work, which uses inefficient constructions based on finite grids, we implement a novel method which combines a suitable Gram matrix and an efficient sampler based on the Metropolis–Hastings (MH) algorithm. Finally, we present a series of numerical experiments to showcase the efficiency of CAS-SRFE, demonstrating throughout a consistent benefit of adaptive sampling over that of nonadaptive, MC sampling. Overall, we demonstrate how the CAS-SRFE framework unites sparsity, adaptivity and active learning to effectively address data-scarce problems in scientific computing. 1.3 Relevant literature The foundation for this paper is the well-known RFM. RFM uses simple functions with randomized parameters to approximate functions, and can be viewed as an ensemble average of randomly parameterized functions [ 33 ] . Rahimi and Recht [ 36 ] originally introduced RFM as an efficient approximation to kernel methods, offering better scalability with respect to the size of the training dataset [ 36 ] . It was later shown to be successful for many machine learning tasks, with the benefits of numerical efficiency and theoretical accuracy bounds [ 21 ] . For instance, this approximation is also used downstream for kernel regression tasks [ 21 ] . The most common form of RFM is the Random Fourier Feature (RFF) method, which uses trigonometric functions as features. In our numerical experiments, we only consider RFF, although CAS-SRFE can be readily applied to other features. While effective, RFM relies on large datasets, as it requires more samples than trainable parameters. SRFE was introduced by Hashemi et al. [ 21 ] to address this limitation. SRFE incorporates sparse recovery into RFM. It constructs a sparse representation using a large set of candidate features from a given set. By doing so, one can allow the number of features to significantly exceed the dataset size. This provides better representation capabilities than RFM and reasonable generalization bounds, even in the highly data-scarce setting. The original SRFE framework solved a convex \ell^{1} -minimization problem, which

Read the complete text